无线传感网络

1、WSN距离无关定位算法许星星（先进制造学院,S151301015）摘要无线传感器网络是一种集成了传感器、微机电系统和网络三大技术而形成全新的信息获取和处理技术,在许多领域有着重要的科研和使用价值,节点定位技术是传感器网络关键技术之一,具有十分重要的地位.目前已有较为成熟的无线传感网定位技术可以被分为需要测距的定位技术和与测距无关的定位技术.本文作者分别介绍了基于测距的定位技术的基本原理,然后在此基础上着重综述了近年来该领域具有代表性的算法及系统的原理和特点,并指出未来的研究方向.关键词:无线传感网络;节点定位;距离无关Introduction on location algorithms in

2、 wireless sensor networks (Institute of advanced manufacturing，S151301015)AbstractWireless sensor network (WSN) is a kind of integrated with sensor, micro-electro-mechanical system and network technology and the formation of a new information acquisition and processing technology, has important scie

3、ntific research in many fields and use value, is a key technology of sensor network node localization technology, plays a very important position. There are relatively mature wireless sensor network positioning technology can be divided into needs ranging positioning technology and has nothing to do

4、 with the distance positioning technology. Respectively in this paper, the author introduces the positioning technology based on distance and without the basic principle of ranging localization algorithm, analysis and comparison of these two kinds of algorithm, and then on the basis of the focus on

5、the typical algorithms in this field in recent years were reviewed and the principle and characteristics of system, and points out the future research direction.Keywords: WSN; node location algorithm; range-free目录0 引言41 算法性能评价标准42 距离无关(range-free)定位算法62.1 典型的算法63结论9参考文献100 引言近年来,无线传感网络(Wireless Sens

6、or Networks, WSNS)已经获得了广泛的关注,特别是微机电系统(Micro-Electro-Mechanical Systems, MEMS)技术的不断涌现,推动了智能传感器的发展。 无线传感网络综合了传感器技术、计算技术、现代网络及无线通信技术、分布式信息处理技术等,能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息。 无线传感器网络的定位技术在许多领域具有重要的应用价值,无线传感器网络节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意义。在定位领域中,无线传感网络的节点可以分为两类:一类是己知自身坐标的节点,被称为信标节点或销节点,该节点通

7、常是通过GPS或人工部署的方式得到节点坐标的;另一类是位置坐标节点,被称为未知节点(Unknow Node),该类节点则是需要我们通过周围的描节点所提供的信息来估算出自身节点的坐标信息。目前无线传感网络的节点定位算法有许多不同的分类的原则,如:基于有无锚点可以分为有锚点算法和无锚点算法;基于测距方式可以分为距离相关算法和距离无关算法;基于计算方式可以分为集中式算法和分布式算法;基于计算次数可以分为一次计算算法和循环求精算法。因为节点的定位算法就是为了确定各个节点的位置信息,因此主要研究基于测距方式的分类:距离相关(range-based)算法和距离无关(range-free)算法。本文研究了距

8、离相关(range-based)算法,分析这算法中的典型定位算法,对这算法原理、性能和优缺点进行了的分析,并指出现有算法存在的问题。最后总结全文,对未来无线传感网络定位技术进行了展望。1 算法性能评价标准a) 定位精度:通常也可以成为定位误差。该标准是评价定位算法的主要标准之一,它是通过估算位置与实际位置间的差值和节点通信半径之间的比例得到的。b) 规模:不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实现定位。另外,给定一定数量的基础设施或在一段时间内,一种技术可以定位多少目标也是一个重要的评价指标。c) 锚节点密度:锚节点定位通常依赖人工部署或 GPS 实现。人工

9、部署锚节点的方式不仅受网络部署环境的限制,还严重制约了网络和应用的可扩展性。而使用 GPS 定位,锚节点的费用会比普通节点高两个数量级,这意味着即使仅有10%的节点是锚节点,整个网络的价格也将增加10倍。因此,锚节点密度也是评价定位系统和算法性能的重要指标之一。d) 节点密度:在 WSN 中,虽然在一定范围内,定位算法的精度与节点密度成正相关关系,但与此同时,也造成用来进行网络部署的开销。此外,节点密度过大将增加网络内定位数据包的发送,这将较少网络的利用率。因此,在实际中要参考实际应用的需求在定位精度和节点密度直接做出权衡。e) 容错性和自适应性:本论文以及相关文献中研究的算法大都是在理想环境

10、下的仿真。但是在现实中,总会出现各种无法预料的情境：比如多径传播以及通信盲区等会影响测量精度；同时网络节点的安全性以及电能的供应也会对测量精度造成影响；而且高精度的测量方法或替换节点一般是不可行的。所以,良好的自适应性和容错性对定位算法来说至关重要,它能进一步提高定位精度。f) 功耗:通常传感器网络中的节点大都分布于交通不便、人烟稀少的地方,并且节点的规模都较大,能源耗尽也就表示节点失效,大规模的节点失效会造成网络瘫痪,导致网络丧失基本功能。所以,传感器的功耗也应该作为重要的考虑因素之一。g) 代价:定位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系统的安装时间、配置时间、定位所需

11、时间。空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系统或算法的基础设施、节点设备的总费用。2 距离无关(range-free)定位算法2.1 典型的算法（1）Bounding-Box 定位算法Bounding-Box算法是目前定位系统中应用最为广泛的算法之一,它有着精度高、计算容易和扩展性好等优点。Bounding-Box算法类似于三边定位算法,通过传输距离损耗模型分别计算出铺节点到被定位点的距离di。以di为半径,锚节点为圆心做圆,并进一步做出该圆形区域的外接正方形,从而获得被定位点所在的一个二维正方形区域,如图2-1-1所示。图2-1

12、-1定位系统中通常会有大于两个铺节点存在,所以会得到至少两个被定位点所在的二维正方形区域。由子被定位点同时在两个二维正方形区域中,故被定位点必然在两个正方形区域的公共区域中,如图2-1-2所示。图2-1-2Bounding-Box定位算法的优势在于其易于扩展,并且描节点的包含被定位点的正方形越多得到的公共正方形的区域就越小,则估算就越精确。除此之外,该算法的计算过程与圆没有关系,相比三边定位算法更加方便计算。得到公共区域的公式后,用质心法取公共区域的质心,即被定位点X的估计坐标。（2）质心算法质心算法的原理是通过获取网络中节点间的连通关系来估算连通节点问的距离,从而进一步利用连通节点组成的几何

13、图形质心来估算H标节点坐标2。在一个系统通信环境内部署锚节点,锚节点周期性的广播自身信息,信息包括本身的ID和其坐标。其周围的未知节点收到这些信标节点发来的信号后,即可确定自己处于那几个信标节点周围。在一段时间后,未知节点将搜集到的信标信号进行统计,当其个数超过阈值后,则可以判断其周围有哪些信标节点。求得连通节点位置坐标点组合起来形成的几何图形的质心,即为未知节点的估算坐标,如图2-1-3所示。图2-1-3（3）APIT定位算法类似于测距定位算法,APIT也需要有自己的铺节点,区别是APIT算法使用的是基于区域的节点定位技术,其原理是将错节点的区域划分成一个个三角形区域,通过判断未知节点位于哪

14、些三角形区域内,进一步缩小定位范围。利用描节点本身的坐标即可进一步得出目标点的位置。图2-1-4其中常用于减小目标节点所在区域范围的算法叫PIT测试。该方法每次判断目标节点是否在由信标节点所组成的三角形内,从而利用信标节点的坐标,即三角形的定点坐标,缩小目标点所在范围。最后可以得到一个较小的多边形范围,然后在利用质心算法计算目标节点的坐标。（4）基于移动锚节点的距离无关定位算法从前面的分析可以看出成本和锚节点稀疏问题是目前定位算法最需要进一步解决的问题。如何以较少的成本获得较多的锚节点位置信息,同时处理锚节点稀疏问题是定位算法的一个重要的课题,有学者提出利用移动锚节点来进行定位。在这些方案中,

15、一个移动锚节点在网络中移动并周期地发送含有锚节点位置信息的信标信号,未知节点接受这些信标信号并通过特定的算法估算自己的位置。距离无关的移动锚节点定位方法,无需测距。目前对基于邻近关系研究的较多,因为移动锚节点可以解决锚节点稀疏问题。而在锚节点大密度均匀分布时,邻近关系算法精度高同时计算和通信开销都较小,要求的节点密度也低。Sangho等提出了一种基于几何约束的移动锚节点定位算法,当位置节点接收到足够多的信息之后,就可以通过一定的几何约束条件,从而估计出自己的位置信息。Hu中也提出了一种基于三边测量方法的移动锚节点定位算法。3结论无线传感器网络在军事和民用领域都具有极大的应用前景,怎样快速准确定

16、位无线传感器的位置一直是近年来的研究热点。对现有的无线传感网络定位算法距离无关定位算法进行了对比分析,从各种性能指标来看, 距离无关定位算法的问题在于锚节点稀疏问题和算法的通信与计算开销,因此研究趋势集中在低复杂度、低开销、低能耗和能够解决锚节点稀疏问题的节点定位算法。与此同时,研究提出基于移动锚节点定位技术,对于解决锚节点稀疏问题有一定得效果,但是还需要进一步的研究其移动路径问题以及不适合使用移动锚节点环境下的解决方案。参考文献1 王福豹,史龙,任丰原.无线传感器网络中的白定位系统和算法J.软件学报,2005,16(5):857-868.2 Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):11481157 (in Chinese with English abstract)3 龙婧，无线传感器网络节点定位算法研究，D大连海事大学，硕士论文，20134 郭明杰，无线传感器网络自身定位算法研