【作者】 王继春；

【导师】 黄刘生；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2009， 博士

【摘要】 微机电系统的快速发展孕育了无线传感器网络这项先进技术。无线传感器网络作为一种由大量结构简单、廉价的传感器集成无线通信接口所组成的网络,它在环境监测、灾难救助、目标跟踪等领域都有广泛的应用前景。在这些应用中,传感节点的自我定位非常重要,因为没有和具体的坐标联系在一起的环境监测信息通常是没有意义的。同时,无线传感器网络的一些协议比如基于地理信息的路由也需要定位信息作为支撑。因此节点定位问题是无线传感器网络的重要研究内容之一。由于定位问题如此重要,在过去几年中,各国学者提出了很多不同的定位算法。这些定位算法虽然针对网络模型、节点密度、硬件能力等等都进行不同的假设,但是它们都存在以下一项或多项缺点:需要特殊硬件支持、非分布式、可扩展性差、计算复杂度和通信复杂度高等等。针对这种现状,本文在对定位算法进行了广泛的调研和研究的基础上,提出了基于Voronoi图的定位算法VBLS(Voronoi Diagrams Based Localization Scheme)和基于连通性和节点协作的定位算法CLFC(Collaborative Localization Scheme FromConnectivity)。在上述理论工作和中科院知识创新工程的支持下,最后本文开发了一个基于MicaZ节点的定位原型系统,对实用化的定位技术进行探索。本文的主要内容如下:首先,我们提出了一种基于Voronoi图的定位算法VBLS。该算法的优点是分布式、精确且可靠。它首先对收集到的锚节点的接收信号强度(RSSI)进行从大到小的排序,然后利用UDG图依次计算每个锚节点的Voronoi区域,最后将所有Voronoi区域交集的质心输出作为定位结果。在仿真模拟中,本文将VBLS和另外两种无需测距的定位算法(Centroid算法和W-Centroid算法)进行了比较。仿真结果表明,对于锚节点随机摆放的情况,VBLS的定位误差比Centroid算法和W-Centroid算法分别降低了18%和13%;对于锚节点均匀摆放的情况,VBLS的定位误差比Centroid算法降低了7%,比W-Centroid算法增加了2%。接下来,本文提出了一种基于连通性和节点协作的节点定位算法。通常基于连通性和通信跳数的定位算法由于并不考虑待定位节点之间的连通性约束,因此定位精度通常较差。针对这种情况,本文设计了利用节点之间连通性约束来提高定位精度的算法CLFC。该算法主要分为2个阶段,第一阶段利用DV-Hop算法得到每个待定位节点的粗略定位;第二阶段利用一个分布式的迭代算法提高节点的定位精度。通过仿真结果表明,对于随机锚节点摆放和固定锚节点摆放的情况,CFLC算法比DV-Hop算法的定位误差分别减少了14%和20%。同时CFLC算法比传统的基于质量-弹簧模型(Mass-Spring Model)的定位算法AFL(AnchorFree Localization Scheme)大大提高了收敛速度,这使得算法的消息复杂度和计算复杂度大大降低。最后,在上述理论工作的基础上,本文开发了基于MicaZ节点的无线传感器网络节点定位原型系统。首先,本文将CLFC算法在定位原型系统中加以实现,通过实验表明,应用待定位节点之间的连通性约束条件降低节点的定位误差的有效性。在规则网络拓扑和随机网络拓扑下,CLFC算法比DV-Hop算法定位精度分别提高了4%和8%。同时,在实验过程中,我们发现了RSSI在各个方向上分布的不规则性。通过对这种不规则性进行仔细的研究,我们发现RSSI信息不但取决于发送节点和接收节点之间欧几里德距离,同时也取决于它们之间的天线夹角。为了降低这种各向异性对定位精度的影响,本文设计了一个基于距离和角度进行插值的定位算法,并在MicaZ节点上加以实现。通过实验检测,可以发现该方法可以有效降低RSSI不规则的网络的定位误差。更多还原

【Abstract】 Advances in micro-electro-mechanical-system have triggered an enormous interest in wireless sensor networks(WSNs),which consists of a large number of simple and inexpensive sensor device equipped with wireless communication interface.WSNs have been proposed for various applications including environment monitoring,disaster relief、surveillance and target tracking,so on and so forth.In these applications,sensed data is always meaningless without relating to its physical location.Furthmore,some middle ware services such as location aided routing need location information.So,it is very important to gain location of sensor node automatically.Because of the importance of localization,many localization procedures have been proposed in this field recently.All of these localization schemes are based on different assumptions,such as node desity,special hardware etc.They all have one or several shortcomings listed as below:special hardware devices are needed, non-distributed,poor scalability and high computation and communication complexity.Considering all these shortcomings,we first study localization problem for wireless sensor networks carefully,then we propose voronoi diagram based localization scheme VBLS and a collaborative localization scheme from connectivity (CLFC) for wireless sensor networks.Finally,we develop a prototype localization system for wireless sensor networks.The main research contents of this paper are listed as follows:First of all,we introduce a distributed,accurate and reliable Voronoi diagrams based localization scheme(VBLS),which makes use of received signal strength indicator(RSSI) from anchors.First,VBLS sorts received signal strength indicator in descending order.Then,we use unit disk graph to calculate the Voronoi area of anchors in turn.Finally,the overlapping region of different anchors’ Voronoi area is identified as the possible region where sensor resides in.We compare our work via simulation with two other range-free localization schemes(W-Centroid and Centroid) to show the efficiency of VBLS.For random anchor placement,VBLS outperforms centroid scheme and W-centroid scheme significantly,estimation error decreases by 18%and 13%,respectively.For uniform anchor placement,VBLS gets a gain of 7% decrease and 2%increase of estimation error,respectively. Then,we present a collaborative localization scheme from connectivity(called CLFC) for wireless sensor networks.In this scheme,the connectivity information is used to improve the accuracy of position estimation.Relative positions between sensors are corrected to satisfy the constraints of connectivity.The scheme is composed by two phases:initial setup phase and collaborative refinement phase.In initial setup phase,DV-Hop is run once to get a coarse location estimation of each unlocalized sensor.In collaborative refinement phase,a refinement algorithm is run iteratively to improve the accuracy of position estimation.We compare our work via simulation with two classical localization schemes:DV-Hop and AFL.The results show the efficiency of our localization scheme.When compared with DV-Hop, estimation error of CLFC is reduced by 14%and 20%for random beacon deployment and fixed beacon deployment respectively.Furthermore,the proposed method CLFC is much better than the traditional mass-spring optimization based scheme AFL(Anchor Free Localization Scheme) in terms of convergence rate.This results in significant saving in message complexity and computation complexity.Finally,we design and implement a prototype localization system for wireless sensor network.First,we realize CLFC algorithm on MicaZ motes.The experiment results show that the use of connectivity information of unlocalized sensors can reduce location estimation error by 4%and 8%for fixed topology and random topology respectively.During the test of CLFC,we discover the irrigurity of RSSI information.After exploring the irrigurity carefully,we find that RSSI information not only depends on euclidean distance between sensor nodes,but it also depends on angle between sensor nodes.In order to reduce the effect of anisotropy on location accuracy,we design an interpolation-based localization scheme and implement it on MicaZ motes.Then,we test this localization scheme and show its efficiency.更多还原