定位算法调研

1、定位算法调研一、 定位算法的研究意义对于大多数应用，不知道传感器位置而感知的数据是没有意义的。传感器节点必须明确自身位置才能详细说明在什么位置或区域发生了特定事件,实现对外部目标的定位和追踪。用无线传感器网络进行目标的跟踪定位，就是综合传感器自身位置信息和网络节点与目标的关系信息，确定目标所处的地理位置。对于移动目标而言，连续不断的定位就是跟踪。传感器自身的位置信息，是实现目标定位跟踪的基础,而网络节点与目标的关系信息，则是实现目标定位跟踪的关键。另一方面，了解传感器节点位置信息还可以提高路由效率,可以为网络提供命名空间,向部署者报告网络的覆盖质量,实现网络的负载均衡以及网络拓扑的自配置等。尽

2、管现有的许多定位系统和算法能够较好的解决WSN自身定位问题。但依然存在如下一些问题: (1) 未知节点必须与锚点直接相邻,从而导致锚点密度过高。(2) 定位精度依赖于网络部署条件。(3) 没有对距离/角度测量误差采取抑制措施,造成误差传播和误差积累,定位精度依赖于距离/角度测量的精度。(4) 依靠循环求精过程抑制测距误差和提高定位精度，虽然循环求精过程可以明显地减小测距误差的影响,但不仅产生了大量的通信和计算开销,而且因无法预估循环的次数而增加了算法的不确定性。(5) 算法收敛速度较慢。因此必须采用一定的机制改进或者避免以上问题，从而实现更高精度的WSN自身定位。二、 定位算法的研究现状从19

3、92年AT&T Laboratories Cambridge开发出室内定位系统Active Badge至今,研究者们一直致力于这一领域的研究。事实上,每种定位系统和算法都用来解决不同的问题或支持不同的应用,它们在用于定位的物理现象、网络组成、能量需求、基础设施和时空的复杂性等许多方面有所不同。根据定位算法中对节点位置的不同计算方式，可以分为集中式定位算法以及分布式定位算法。集中式定位算法把所需信息传送到某个中心节点,并在那里进行节点定位计算的方式。Doherty等1假定网络中存在一定比例的锚点，根据凸规划(convex optimization)来估计不确定节点的位置。MDS-MAP2则采用了

4、多维定标的方法来提高定位精度。这两种算法都是典型的集中式定位算法，其后一系列的算法对该算法进行改进以提高节点定位精度。分布式定位算法是指依赖节点间的信息交换和协调,由节点自行进行定位计算的方式。质心算法中3，每个节点通过计算它所侦听到的锚点的中心位置来确定自身位置，如果锚点布置的比较好，则定位误差能够得到很好的改善。APIT算法4中的节点侦听自己附近锚点的信号，根据这些信号，APIT算法把临近这个节点的区域划分为一个个相互重叠的三角形区域。然后采用划分网格的方法找出自己所在的区域，如果能够侦听到足够多的锚点信息，这个区域可以变得很小，从而提高算法的定位精度。根据定位算法中节点获取信息的不同方式

5、，可以分为基于测距技术的定位和无须测距技术的定位(range-based versus range-free)两大类。Range-Based定位通过测量节点间点到点的距离或角度信息,使用三边测量(trilateration)、三角测量(triangulation)或最大似然估计(multilateration)定位法计算节点位置；Range-Free定位则无须距离和角度信息,仅根据网络连通性等信息即可实现。Range-Based定位常用的测距技术有RSSI,TOA,TDOA和AOA。RSSI(received signal strength indicator)虽然符合低功率、低成本的要求,但

6、有可能产生50%的测距误差5。TOA(time of arrival)需要节点间精确的时间同步,无法用于分布式定位；TDOA(time difference on arrival)技术受限于超声波传播距离有限(WSN所使用的超声波信号通常传播距离仅为2030英尺,因而网络需要密集部署)和NLOS问题对超声波信号传播的影响；AOA(angle of arrival)也受外界环境影响,而且需要额外硬件,在硬件尺寸和功耗上可能无法用于传感器节点。除上述测距技术的局限性以外,range-based定位机制使用各种算法来减小测距误差对定位的影响,包括多次测量6,循环定位求精7,这些都要产生大量计算和通信

7、开销。所以,range-based定位机制虽然在定位精度上有可取之处,但并不适用于低功耗、低成本的应用领域。因功耗和成本因素以及粗精度定位对大多数应用已足够(当定位误差小于传感器节点无线通信半径的40时,定位误差对路由性能和目标追踪精确度的影响分别小于15%和7%8),range-free定位方案倍受关注。DV-Hop9，10、凸规划1和MDS-MAP2等就是典型的range-free定位算法,其中MDS-MAP还可以在range-based条件下实现更精确的定位。在国内，彭刚等14提出了一种低成本的实用的定位策略。该策略只是增加了少量的信标节点，通过节点之间的跳数信息，来估算出各节点到信标节

8、点的距离，通过三角测距的原理，确定各个节点的具体位置。在众多的定位算法中，存在一些比较典型的算法，如： 凸规划定位算法1加州大学伯克利分校的Doherty等人将节点间点到点的通信连接视为节点位置的几何约束,把整个网络模型化为一个凸集,从而将节点定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全局优化的解决方案,确定节点位置。同时也给出了一种计算未知节点有可能存在的矩形区域的方法。如图1所示,根据未知节点与锚节点之间的通信连接和节点无线射程,计算出未知节点可能存在的区域(图中阴影部分),并得到相应矩形区域,然后以矩形的质心作为未知节点的位置。Anchor nodeUnknow

9、n node图1 凸规划算法示意图凸规划是一种集中式定位算法,在锚节点比例为10%的条件下,定位精度大约为100%。为了高效工作,锚节点必须部署在网络边缘,否则节点的位置估算会向网络中心偏移。 N-hop multilateration primitive定位算法11加州大学洛杉矶分校的在AHLos算法12的基础上,Andreas Savvides等人提出了n-hop multilateration primitive定位算法。它不仅给出了判定节点是否可参与collaborative multilateration的充分条件,并使用卡尔曼滤波技术循环定位求精,减小了误差积累。该算法分为3个阶段

10、。(1) 生成协作子树:根据判定条件,在网络中生成多个由未知节点和锚节点组成的限制条件完整或超限制条件的构形,称为协作子树.每个构形包括n个未知变量(未知节点的坐标)和至少n个非线性方程式,并确保每个未知变量拥有唯一解。未被协作子树包含的节点在整个算法的后处理阶段进行定位。(2) 计算节点位置的初始估算:根据锚节点位置、节点间距离和网络连通性信息对每个节点的位置进行粗略估算,结果作为第3阶段的输入。如图2所示,图中A,B为锚节点,C,D为未知节点,测得节点间距a,b,c,可推算出节点C的x坐标取值范围为。但该方法有一个明显的缺点就是要求锚节点必须被部署在网络边缘。(3) 位置求精:根据预设的定

11、位精度,使用卡尔曼滤波技术在每个协作子树范围内(每个节点位置有唯一解)对第2阶段的结果进行循环求精,可选用分布式或集中式两种计算模式。实验显示,该算法的定位精度可达3cm(节点测距误差为1cm,锚节点比例为20%)。 图2 n-hop multilateration primitive中节点位置的初始估算 MDS-MAP定位算法2MDS-MAP是一种集中式定位算法,可在range-free和range-based两种情况下运行,并可根据情况实现相对定位和绝对定位。它采用了一种源自心理测量学和精神物理学的数据分析技术多维定标(multidimensional scaling),该技术常用于探索性

12、数据分析或信息可视化。MDS-MAP算法由3个步骤组成:(1) 首先从全局角度生成网络拓扑连通图,并为图中每条边赋予距离值。当节点具有测距能力时,该值就是测距结果。当仅拥有连通性信息时,所有边赋值为1。然后使用最短路径算法,如Dijkstra或Floyd算法,生成节点间距矩阵。(2) 对节点间距矩阵应用MDS技术,生成整个网络的2维或3维相对坐标系统。(3) 当拥有足够的锚节点时(2维最少3个,3维最少4个),将相对坐标系统转化为绝对坐标系统。实验显示,当网络的节点密度减小时,定位误差增大,并且无法定位的节点数量增加；而当网络连通度达到12.2时,几乎全部节点都可实现定位；在拥有200个节点(

13、其中4个锚节点),平均连通度为12.1的网络中,在range-free条件下,定位误差约为30%；而在range-based条件下,定位误差为16%(测距误差为5%)。 APIT定位算法4APIT算法是一种无须测距技术的定位算法。其基本思想是利用一些束缚条件把未知节点的位置确定在一块尽量小的区域内，然后取这块区域内的一点作为节点的位置（通常是该区域的质心位置）。APIT算法中节点侦听自己附近锚点的信号，根据这些信号，APIT算法把临近这个节点的区域划分为一个个相互重叠的三角形区域。然后采用划分网格的方法找出自己所在的区域，如果能够侦听到足够多的锚点信息，这个区域可以变得很小，从而提高算法的定位

14、精度。结果表明，该算法比其他基于锚点的算法需要更少的计算量以及更少的通信量。 质心定位算法13质心算法是由南加州大学的Bulusu N等提出的一种仅基于网络连通性的室外定位算法。该算法的核心思想是：锚点周期性的向邻居节点广播Beacon信号，信号包括节点ID及位置信息。当未知节点收到来自不同锚点的Beacon的数量超过预定门限值或者接收一定时间后，该节点就确定自身位置为这些锚点所组成的多边形的质心。实验表明，大约90%的未知节点的定位精度小于锚节点间距的1/3。三、 定位算法发展趋势从前面的现状我们可以看出无线传感器网络中定位算法的发展趋势是越来越面向应用，早起的定位算法试图寻找一种通用的定位

15、算法，如今的定位算法不再采用一种通用的算法，而是针对特定的应用采用更有效的算法。另一方面，移动WSN的定位算法也越来越受到关注，然而这类算法也是一般采用额外的硬件设备协助定位。四、 定位算法的研究目标从是否需要额外测距设备以及算法对传感器节点处理能力要求高低这两方面比较国内外相关算法的性能，选择其中最优的定位算法并加以改进。本项目不打算采用额外的测距设备，因为这样导致高昂的费用，然而其他不需要额外设备的算法对传感器的处理能力要求比较高，计算的复杂度比较大，很容易导致传感器失效。我们考虑到节点的处理能力有限，节点计算自身位置的算法应该避免过于复杂，这样同时也节省了节点的能量，从而采用了一种较为简

16、单的定位算法，尽量避免节点间采用泛洪方式进行位置信息传送时给网络带来的额外负载，并且采用分布式定位算法以减少通信开销，从相关的文献结果表明，我们的算法最终定位误差将会控制在35%以下（前面的文献表明，当定位误差小于传感器节点无线通信半径的40时,定位误差对路由性能和目标追踪精确度的影响分别小于15%和7%）。五、 技术路线 图3 WSN节点定位模块 图4 WSN节点定位信息传播图图5 WSN节点定位算法从图3可以看出，无线传感器网络(WSN)节点定位模块由3部分组成：接口单元、数据存储单元以及节点定位运算单元。接口单元对外负责与节点定位模块外的其他模块进行数据交换，对内与其他单元进行数据交换以

17、获取自身定位，对外主要是以get_position()函数提供给其它模块获取自身位置的服务，该函数的原型为：bool get_positon(ID id, POSITION * pos);并获取用户对定位算法参数的配置信息，该函数原型为： void set_parm(int T, float eta);数据存储单元从接口单元获取原始数据并将数据传递为节点定位运算单元以及将其计算结果保存作为自身定位信息；节点定位运算单元负责将数据存储单元传送过来的数据进行运算，并将结果向接口单元和数据存储单元输出。由于文献13所述的质心算法仅适用于室外环境，并且要求锚节点比例要求较高(20%)，在我们的算法中，

18、由于允许获得位置后的未知节点充当锚节点，因此可以有效减小网络中锚节点的比例，其算法描述为：锚节点周期性地在向邻居节点广播Beacon信号，该Beacon信号中包含锚节点自身ID和位置信息；未知节点必须维护一张邻居锚点表，每个表项可以表示为(ID，Beacon_Num)，表示从标识为ID的邻居锚点接收到Beacon_Num个Beacon信号。当未知节点接收到Beacon信号时，它将按图5所示流程进行操作。首先未知节点查找自己的邻居表，发现该ID是新的邻居锚点，则将该ID加入自己的邻居锚点表中，并开启一个定时器T；否则它将邻居表中该ID对应的Beacon_Num加一，然后继续等待接收Beacon信

19、号或者定时器T的超时。如图4所示，一旦定时器T超时，未知节点就选取邻居锚点表中Beacon_Num大于的节点所组成的多边形的质心作为自己的位置。也即，假设该定位参考节点表中各节点的坐标为(X1,Y1),(X2,Y2),(Xn,Yn),则未知节点将定位自身位置为： 一旦未知节点确定了自身位置，那么它也将以自己的ID和位置信息作为参数向它的邻居节点广播Beacon信号，也即，它也将起到锚点的作用以作为其它未知节点的参考节点。六、 参考文献1. Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless senso

20、r networks. In: Proc. of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 1655-1663.2. Shang Y, Ruml W, Zhang Y, Fromherz MPJ. Localization from mere connectivity. In: Proc. of the 4th ACM Intl Symp. on Mobile Ad Hoc Networking & Computing. Annapolis: ACM Pr

21、ess, 2003.3. Nirupama Bulusu, John Heidemann and Deborah Estrin. GPS-less Low Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications Magazine. October 2000.4. Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, Tarek Abdelzaher. Range-free Localization Schemes for Large

22、 Scale Sensor Networks. MobiCom 2003.5. Meguerdichian S, Slijepcevic S, Karayan V, Potkonjak M. Localized algorithms in wireless ad-hoc networks: Location discovery and sensor exposure. In: Proc. of the 2nd ACM Intl Symp. on Mobile Ad Hoc Networking & Computing. Long Beach: ACM Press, 2001.6. Bergam

23、o P, Mazzini G. Localization in sensor networks with fading and mobility. In: Proc. of the 13th IEEE Intl Symp. on Personal, Indoor and Mobile Radio Communications. Lisbon: IEEE Communications Society, 2002,2:750-7547. Savarese C, Rabay J, Langendoen K. Robust positioning algorithms for distributed

24、ad-hoc wireless sensor networks. In: Ellis CS, ed. Proc. of the USENIX Technical Annual Conf. Monterey: USENIX Press, 2002.8. He T, Huang CD, Blum BM, Stankovic JA, Abdelzaher T. Range-Free localization schemes in large scale sensor networks. In: Proc. of the 9th Annual Intl Conf. on Mobile Computing and Networking. San Diego: ACM Press, 2003. 81-959. Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. Vol.5, San Antonio: IEEE Communications Society, 2001. 2926-2931.10. Nicul