无线传感器网络节点的定位算法

《无线传感器网络节点的定位算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

维普资讯http://www.cqvip.com第3O卷第7期计算机工程2004年4月April2004ComputerEngineeringo|．3o乜7．博士论文．文章编号：lIl0Il428(2004107lll32文献标识码：A中圈分类号：TN92无线传感器网络节点的定位算法马祖长，孙怡宁’(1中科院合肥智能机械研究所，合肥230031；2中国科学技术大学精密仪器系，合肥230026)任何额外的硬篝件支持节点问通信翥开销少。仿真实验显示，”在网络连接度为8、篓参喜考霉节点乏数誓量为20的嚣情况，瞿*-m囊芷1袭误左小警-j-嚣l鋈总羽翥捌趔，信距离的21％。关健词：无线传感器网络；定位；平均每跳距离PositioningAlgorithms0fWirelessSensorsNetworkNodeMAZuchang1．z-SUNYining’f1InstofIntelligentMachinesChineseAcademyofSciences、Hefei230031；2DcDt．ofPrecisionMaChineryandInst~umcntation，UniversityofScienccandl’echnologyofChina．Iqefei230026)【Abstract]Thepaperreseal‘chespositioningaIgol‘ithmsofwil．elessSelSOl‘swOIkandproposesaleWposltmnmgalgol‘ithmlhcbaprinciplandtheimplementingapproachesofthealgol’ithmarcintr(~ucedl、hcalger。ithmdocsn’tI1equi~’el1)eXCeSShal’dwareandmessagebetweennodeslove．Simulationsshowthatavel’agepositioningelTOrlessthan2f％ofnodes’radiorangeinascenal’iowhereanaverageconleCtlⅥtyIS8andalCnonodcsS2O．IKeywordslWirelesssensorsnetwork；Positioning：AⅧ’agehopdistance无线传感器网络可应用于线和电源供给困难的区域、r—————————■———————————_p．=4(xl—)+(l—J)人员不能到达的区域和一些临n寸场。由于其17．作区域人p!=(x2一)!+(_v：一_L1)(1)类不适合进入或者是敌对区域，节点需要通过飞行器抛撒十_[作区域，其位置是随机的。无线传感器网络婴在这些特殊p=√(3一)+(y一J’)区域应用，首先要解决的问题是以最小的通信开销和硬件代方程组(1)中，Y，是未知量，这是非线性方程组，可价实现节点定位。Niculescu等人提出7r"DVhop定位算法0，基本思想是以采用线性化方法来求解。将其真实位置(Y)和近似位将待定位节点到参考节点之间的距离用网络平均每跳距离和置()之间的偏离用(△，，，)来标记，按泰勒级数绕近两者之间跳数乘积表示，使用三角计算获得节点位置信息。虽然待定位节点通信范围内的参考节点数量不多，但是采用似位置展开，便可将位置偏移()表示为已知坐标和上述方法可以获得通信范围外多个参考节点的估计距离，利距离测量值的线性函数，最后得到单一方程用大量的冗余信息实现节点定位。在网络平均连接度为8，Ap，d+a△(2)t,参考节点比例5％情况下，算法平均定位误差大约是节点射其中，频通信距离的1／3左右。该算法不需要进行节点之间的距离测量，节点不需要任何附加硬件支持，是无线传感器网络节点定位的一个理想方kpi=p孚，案。但是通过研究发现这种算法有一些不足之处：在获得平在传感器网络中，节点之间连接很多，大多数节点都町均每跳距离的计算过程中，节点之间通信量过大；没有考虑以直接或间接获得3个以上参考点的不精确距离。当参考节不良节点(本质上无法定位的节点)的影响，导致平均定位点数量超过3时，就是过定义方程组，利用这样的冗余能够误差较大。获得更高的定位精度。在文献【4】中，作者收集的数据显示我们对这个算法进行了改进，剔除了不良节点，利用多了在距离测量误差较大的情况下(超过标准50％)，在二维参考节点的冗余信息实现节点定位。与DV—hop算法相比，空阅内定位被5个或更多的参考节点包围的节点，平均定位极大地降低了网络通信量并提高了平均定位精度。误差小于射频距离的5％。l节点定位基本原理通过定义方程组可以使用最／l~-_乘法求解，获得△在二维空间中，知道一个点N3个已知参考点的距离，Ay,，。如果精度不满足要求，将矫正后的坐标代替估计坐标就可以确定该点的坐。假设3个参考点的坐标分别为进一步矫正，直~,JzXxAy,A~于规定的门限值结束。，t)、(2，Y!)、(，3)，待确定位置节点的坐标是)，该节点到3个参考节点的距离分别是，根据二维空作者简介：马祖长(I975一)，男，工程师、博士生，主研方向阅距离计算公式，可以获得方程组无线通信网络，智能传感器系统；孙怡宁，研究员、博导收稿日期：2003—04—25E-mail：zcma@sohucorn一13— 维普资讯http://www.cqvip.com2不良节点特征分析只有信息符合下列两个条件，节点才会记录并转发这个信通过对无线传感器网络定位特点的分析，发现『叫络内不息：(I)信息是最新的；(2)信息中的跳数小f转发节点曾经能确定位置的点(不良节点)，除了不可达节点之外，主发出信息的最小跳数，比如节点A曾经广播了一个信息表示到参考节点B为3跳，这个信息被邻居节点F接受，那么它以后要有以下几种：(1)不良节点只一一个可以确定位置的节点直接连接，广播的到参考节点c为4跳的信息就再被邻居丢弃；如果节如图1所示。节点A是可以确定位置的节点，节点B的一跳邻点A以后又转发了一个跳数为2的信息，则邻居节点F删除已居内只有这个节点可以定位，那么节点B就是不良连接节经记录的3跳信息，将这个跳数为2的信息记录下来并转发。点。它可以在图中的B1、B2、B3等位置任意存在，因此本通过这样的约束，节点转发的信息只有跳数最小的一个质上是不能确定位置的节点。被自己的邻居接受，其它的转发信息就被自己的邻居丢弃。(2)不良节点是一跳邻居内只有2个节点可以定位，那么这样不良节点不会获得足够的参考节点信息，无法进行定位这个节点的位置也是无法确定的。如图2所示，节点B的一计算，减少了平均定位误差。跳邻居内只有节点A、C的位置可以确定，那么节点B的位置4算法性能评估也可以在BI，这样节点B的位置不唯一，属于不良节点。为了检验算法的性能，使用0MNET+仿真工具进行了一系列实验，所有仿真条件都设置为150×150m的正方形区域，节点通信距离10m。0MNET++是布达佩斯技术大学电信学院开发的面向对象的分布事件仿真工具，它可用于通信协议、计算机网络多处理器和分布式系统、管理系统等的建模和仿真。J3o⋯。4．1通信量圈1第1种不良连接节点圈圈2第2种不良连接节点在仿真区域内随机分布一定数量的节点，其中2O个为参(3)不良节点是一个节点群，如果该群通过一个可以确考节点。分别观察了本文的算法~[IDV—hop算法在网络内所定位置的节点与网络相连接，而群内没有参考节点，那么这引起的总的节点信息包数量。结果如图4所示，可以看出，个群可以围绕着这个节点旋转，群内所有的节点都是不良连采用本文算法，信息包数量大约为DV—hop算法的信息包数接节点，如图3所示。量的1／3。I4()()0I20O0舞1000{}}兽()}西6【xl()r4000}圈3ill3种不良连接节点3无线传盛暑摹节点定位算法算法开始时，每个参考节点发出一个包括自己位置信息、地址和跳数值为0的广播信息，它们周围所有跳数为1的邻居收到该信息将参考节点位置信息和跳数记录下来，并将收到信息包的跳数+1，再向自己的邻居广播。这个过程一直持续下去，直到网络中每个节点都获得每个参考节点的位置信息和相应的跳数值。为了防止广播信息的无限循环，只有最新收到的信息才被重新广播。信息不是最新的指该节点已经收到某个参考节点的广播，而且最近收到的信息包中的跳数大于或等于存储器中存储的到该参考节点的跳数。参考节点从其它参考位置节点收到足够数量的跳数信息，就可以估计平均每跳距离，并向整个网络广播该信息。参考节点i的平均每跳距离的计算公式为∑√(，～，)!+(，一Yj)!∑。一。：。；其为其它参考节点，为节点i和节之间的跳数。姜嚣导-T．苎麓景暑三嚣!竹t数：·}J一个节点收到了平均每跳距离和3个以上参考节点的跳数，就可以执行三角计算，估计自己的位置。如果该节点进圈5节点敦量一节点平均定位误差行三角计算后，又收到新的参考节点信息，或者是到一个参4．3定位误差与参考节点数的关系考节点的较小跳数，则执行包括最新信息的三角计算。在仿真区域内随机分布了400个节点，变化参考节点的使用这样的算法，无法判断出不良节点，网络中所有的数量，比较两个算法在不同参考节点数量的平均定位误差。可达节点都会收到每个参考节点的位置信息。为了克服上述实验结果如图6所示，从图中可以看出，本文算法的平均定不足，我们在算法设计中，使广播信息包括转发节点地址。(下转第48页) 维普资讯http://www.cqvip.com3．1共享式局墨同下口g主动防范措施经过的路径进行检查，并与备份的合法路径作比较，如果任由于共享式网络下的窃听是基于网卡的混杂模式，那么默认网关前出现其他主机的IP地址，说明已经被修改rARP只要将局域网中设置为混杂模式的网卡找出来就可以知道是表。根据此lP地址也可以确定是哪一台主机正在窃听自己。谁在窃听，常用方法有以下几种：(3)使用SNMP定期轮询ARP表。由于SNMP协议得到操(1)伪造数据包。网卡在正常模式下对于目标非自己作系统的广泛支持，而且目前的网络没备都支持MlB2。MAC地址或广播地址的数据包直接丢弃，只有混杂模式的MIB2信息库中的AT分组包含有当前网段中网络设备的lP地网卡会将这些数据包接收，并返回响应数据包。因此可以构址和MAC地址，因此可以在此基础上定期轮询各t机的AT造一个含有正确目标IP地址和一个不存在目标MAC地址(或分组中的内容并与正确数据库作比较，一出现者一个本网段内没有的MAC地址)的数据包并将它发送出不一致，就可以在纠正ARP表的前提下提取这条虚假信息，去，然后根据收到的响应数据包中所包含的MAC地址或IP定位窃听主机。地址就可以将窃听主机找出来。由于各个操作系统针对无效在发现了窃听主机之后首先应报告网管人员，由网管的MAC地址有不同的定义，所以这种探测方法具有很强的人员出砸进行=F预。在没有人管理的情况F也l1丁以采取针对性。些反击措施，如向窃听主机发送大量无效数据包，发送虚假(2)性能分析。当向网络上发送大量包含无效MAC地址ARP应答包，发送ICMP目标不可达包等方法，干扰其窃听的数据包，窃听主机会因处理大量信息而导致性能下降，如的正常进行，达到保护自己的目的。果在发送前和发送后对主机的响应时间作比较(如采用ICMP4总结的echodelay方法)，就可以判断出这台主机是否真的在窃基于网络窃听的间接性和隐蔽性，长期情况F，用户容听。这种方法最有效，但是很容易对网络的运行产生影响，易放松警惕，导致网络窃听的死灰复燃，重新威胁个人或组因此不能经常使用。织的信息安全。因此应当在实施被动防御的基础上加强主动当然还有一些其他的探测方法如DNS测试等，由于其探发现的长期实时监控，一旦有人进行网络窃听就可以有效地测结果的可信度不够高，故只能当作一种辅助手段，来对探警示用户，达到防患于未然的目的。与局域网类似，广域网测的结果进行进一步的验证。下同样存在着诸~I：IIP欺骗、DNS欺骗、路由欺骗等网络窃听3．2交换式局壤同下螅主动防范措施的手段，应加强对这一方面防范措施的研究工作，使攻击者交换式网络下的窃听手法主要是ARP改向。这是因为基无机可乘。于端口映射的方法需要对交换机进行设置，而一般攻击者是从总的趋势来看，由于硬件技术的不断发展，网络窃听很难有机会接触到交换机。所以只要加强对硬件设备的管已经不得不由共享式网络下的被动方式转为交换式网络下的理，就可以阻止端口映射这一窃听途径。发现ARP改向可以主动方式，同时也有朝着网络欺骗方向发展的可能。因此，从以下几个角度来考虑：在做好当前成熟网络环境下反窃听技术研究的同时，也要对(1)监听ARP数据包。监听通过交换机或者网关的所有局域网下实现网络欺骗的方法进行分析，力争在新技术领域ARP数据包，与合法的地址对数据库相比较，中从根源上杜绝网络窃听的存在。如果数据包中所含的内容与库内内容不一致，可以确定为发参考文献送此数据包的主机正在进行ARP欺骗，根据数据包中所含的1L0phtHeavyIndustries．AntisnifUserGuide．htp：／／www．10phtCOI'RMAC地址可以很容易对窃听主机进行定位。这种方法需要2TanenbaumAS．计算机网络(第三版)．北京：清华大学出版社，19983罗勇辉英特网网络侦听、协议分析的研究和应用I学位论文济交换机的支持，即能够对数据包进行过滤，当检测到这种欺南：济南大学，2001骗正在进行时，可以通过发送正确的ARP数据包将受害主机4熊春山．交换式设备和网络的安全缺陷与改进措施．计算机工程，的ARP表改正回来，使窃听的企图无法得逞。2000，26(10)：60(2)定期探测数据包传送路径。“准”受害主机可以定5RoseM．RFC1213：ManagementInformationBaseforNetworkMan-期使用路径探测程序如tracen、tmceroute等对发出数据包所agementofTCP／IP-BasedInternets：MIB．11．http：／／wwwietf．org※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※(上接第l4页)多参考节点的冗余位置信息，实现了节点的可靠定位。采用位误差小于DV—hop算法。这种方法，在网络连接度为8，参考节点数量为2O的情况下，平均定位误差小于射频通信距离的2l％。这种算法的特点是无须任何额外的硬件支持，需要的通信量少，是无线传感器网络节点定位的一种可选方案。参考文献lSohrabiK，GaoJ，AilawadhiV，eta1ProtocolsforSell-organizationofaWirelessSensorNetwork．IEEEPersonalCommunications，2000．7f51：I6-272NiculescuD，NathB．Ad-hocPositioningSystem．InIEEEGlobeConl，2001．1】3KaplanED．丘至和，王万义译．GPS原理与应用．北京：电子工业出版社，20025结束语4BeutelJ．GeolocationinaPicoRadioEnvironment(Master’sThesis)．本文介绍了无线传感器网络的一种节点定位算法，使用ETHZ”urich．1999．125VargarA．0MNET++Version2．2UserManua1．http：／1www．hit．bme．平均每跳距离x节点之间的跳数代替实际的距离测量，利用hu，2002一48一