无线传感器网络中的自身定位系统
卢倩 2012330301127
（浙江理工大学测控技术与仪器专业，浙江杭州 310018）
摘 要： 无线传感器网络可以在广泛的应用领域内实现复杂的大规模监测和追踪任务，而网络自身定位是大多数应用的基础。本文主要介绍了无线传感器网络自身定位系统和算法，探讨了基于测距和基于预留的定位协议。
关键词： 无线传感器网络；定位系统；自身定位
Self-Localization Systems for Wireless Sensor Networks
Lu Qian 2012330301127
(Zhejiang Sci-tech University,Hangzhou,Zhejiang 310018)
Abstract: Wireless Sensor Networks have been propod for a multitude of diver applic
ations. The problem of lf-localization, that is, determining where a given node is physically or relatively located in the networks, is a challenging one, and yet extremely crucial for many applications.
Key words: wireless nsor network;lf-localization systems ;lf-localization
1 引言
无线传感器网络(Wireless Sensor Networks, WSN)是一种分布式传感网络，它的末梢是可以感知和检查外部世界的传感器。WSN中的传感器通过无线方式通信，因此网络设置灵活，设备位置可以随时更改，还可以跟互联网进行有线或无线方式的连接。通过无线通信方式形成的一个多跳自组织网络。微机电系统（Micro-Electro-Mechanism System，MEMS）、片上系统（SOC，System on Chip）、无线通信和低功耗嵌入式技术的飞速发展，孕育出无线传感器网络（Wireless Sensor Networks，WSN），并以其低功耗、低成本、分布式和自组织的特点带来了信息感知的一场变革。无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络。其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察
者。传感器、感知对象和观察者构成了无线传感器网络的三个要素。广泛用于安全监控、智能交通、智能家居、环境监测等需要多媒体信息的场合。对于这些应用，不知道传感器位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件发生的具体位置。因此必须采用一定的机制与算法实现WSN的自身定位。
湘行散记读书笔记
2 定位中的挑战
定位系统在分布式的定位估计上面还面临着许多挑战，如物理层的测量误差、计算上的约束、GPS的不足、低端的传感器节点和架构。另外，WSN的应用对定位协议的可扩展性、鲁棒性和定位精度等方面提出了不同的需求。结合这些需求，定位协议需要解决WSN中独特的挑战。
3 WSN中的自身定位系统与算法
3.1 基于测距的定位系统(range-bad)[1]
基于测距的定位协议利用多对距离测量来估计节点位置。可以测量节点与它的不同邻节点之间的多个距离以提高定位精度。定位技术可以根据测距技术的变化而变化。
Range-Bad定位通过测量节点间点到点的距离或角度信息，使用三边测量(trilateration)、三角测量(triangulation)或最大似然估计(multilateration)定位法计算节点位置；Range-Free 定位则无须距离和角度信息，仅根据网络连通性等信息即可实现。Range-Bad定位常用的测距技术有RSSI[2]。RSSI(received signal strength indicator)虽然符合低功率、低成本的要求，但有可能产生±50%的测距误差；range-bad 定位机制虽然在定位精度上有可取之处，但并不适用于低功耗、低成本的应用领域。因功耗和成本因素以及粗精度定位对大多数应用已足够(当定位误差小于传感器节点无线通信半径的40%时，定位误差对路由性能和目标追踪精确度的影响不会很大[1])，range-free定位方案倍受关注。DV-Hop、凸规划和MDS-MAP等就是典型的range-free 定位算法。
3.1.1 AHLos定位算法[3,7]
Ad Hoc好用的散粉定位系统（AHLoS）采用基于接收信号强度或基于到达时间的测距技术来提供定位服务。AHLoS的定位分两个阶段：首先，每个节点进行距离测量，然后根据已知位置节点的距离测量进行定位估计。
AHLos算法中定义了3种定位方式——原子式、协作式和重复式最大似然估计定位(atom,co
llaborative和iterative multilateration).其中atom multilateration就是传统的最大似然估计定位，如图1(a)所示。
图1 最大似然估计定位示意
Collaborative multilateration是指假如一个节点可以获得足够多的信息来形成一个由多个方程式组成并拥有唯一解的超限制条件(over-determined)或限制条件完整(well-determined)的系统，那么就可以同时定位跨越多跳的一组节点。图1(b)就展示了collaborative multilate
整容的好处ration的一个二维拓扑示例，未知节点2和4都有3个邻居节点，且1，3，5和6都是锚节点，根据拓扑中的5条边建立拥有4个未知数(节点2和节点世纪骗局4的二维坐标)的5个二次方程式，利用节点间协作计算出节点2和节点4的位置。
Iterative multilateration 就是首先使用原子式和协作式定位，当部分未知节点成功定位自身后,将其升级为锚节点，并进入下一次循环，直到所有节点定位或没有满足原子和协作式定位条件的节点存在时结束。
3.2基于预留的定位协议
基于测距的定位协议依赖于对分布式定位估计的距离测量。基于测距的定位精度高，距离测量的额外能量消耗就高。然而，一些WSN应用不需要非常精确的定位信息并且低精度的定位可能就足够了。这里介绍两种基于预留的定位系统：凸位置估计和基于球壳定位的APIS算法。
3.2.1 凸规划定位算法[4,7]
将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从
而将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，确定节点位置。同时也给出了一种计算未知节点有可能存在的矩形区域的方法。如图2所示，根据未知节点与锚节点之间的通信连接和节点无线射程，计算出未知节点可能存在的区域(图中阴影部分)，并得到相应矩形区域,然后以矩形的质心作为未知节点的位置。
图2 凸规划算法示意
凸规划是一种集中式定位算法，在锚节点比例为10%的条件下，定位精度大约为100%喜剧电影推荐。为
了高效工作，锚节点必须部署在网络边缘，否则节点的位置估算会向网络中心偏移。作为对凸规划算法的改进，文献[5]中提出了将节点间没有通信连接但同样视为节点位置约束的思想来提高定位精度。
琥珀还睛丸
APIT算法具有较高的定位精度和较低的硬件复杂度，被公认为一种适用于传感器网络结点定位的较好算法。
3.2.2APIS算法的原理
文献[ 6]将APIT算法从二维扩展到了三维空间，提出了一种基于球壳交集的三维定位算法APIS。APIS是一种距离无关的定位算法，其基本思想是：以一个锚节点为球心，分别以其到邻近锚节点之间的距离为半径画球，把整个空间划分为大大小小的同心球体。待定位的节点通过判断自己是否在这些同心球体区域内，最终找到包含自己的最薄的一层球壳。以不同的锚节点作球心找到一系列这样最薄的球壳，最后将这些球壳的交集作为待定位节点最可能存在的小区域，取这个小区域的重心坐标作为这个节点的位置，如图 2 所示。
APIS算法的优点是只需要锚节点广播消息，其他节点不需要通信，因此减少了网络通信的开销，节省了能量；只需要两点间的相对大小关系，无须测距，无须额外的硬件支持。但APIS算法也存在着一些不足，如节点采用本地存储信息，每个节点都维持着三个表，加大了节点的成本；与锚节点的密度密切相关，如果锚节点密度小，将导致定位 精度下降；对锚节点的要求较高，要具有很高的能量储备以及通信能力 定位精度还有待提高。
该算法不需要普通结点广播信息，只需要锚结点进行2次广播。在传感器网络中有成百上千个普通结点.不需要普通结点间互相通信，无疑大大节省了能量，能够延长整个网络的生存期.这样该算法就比DV2hop算法和APIT算法要节能，该算法只需要利用两点之间的相对距
离大小关系，并不需要准确测量两点间的绝对距离，因此这种算法是一种Range Free算法,定位精度比Range Bad要高。
4 小结
正方体的折法
根据以上论述可知，每种系统和算法都有各自的特点和适用范围，没有哪一种是绝对最优的。从整体上看，近年来提出的一些循环求精算法，更加充分发挥了WSN的特点，即利用节点间的协同工作实现单个节点无法完成的任务。它们在初始阶段着重于获得节点位置的粗略估算，并在求精阶段根据用户预设的精度门限循环求精；甚至还可根据应用需求，将整个求精阶段作为一个可选阶段。这些算法不仅提高了定位精度，还给予用户更大的自由度，正逐渐形成一个新的类别。但我们还应看到，现有的定位系统和算法还存在如下一些问题：(1) 未知节点必须与锚节点直接相邻柔弱,锚节点密度过高。(2) 定位精度依赖于网络部署条件。例如，凸规划算法要求锚节点必须部署在网络的边缘。(3) 没有对距离、角度测量误差采取抑制措施，造成误差传播和误差积累，定位精度依赖于距离、角度测量的精度。(4) 依靠循环求精过程抑制测距误差和提高定位精度。虽然循环求精过程可以明显地减小测距误差的影响，但不仅产生了大量的通信和计算开销，而且因无法预估循环的次数而增加了算法的不确定性。
普遍网络化孕育的无线传感器网络是一种新的信息获取和处理技术。作为重要的共性支撑技术之一，节点自定位问题极具研究价值。
References:
[1] He T, Huang CD, Blum BM, Stankovic JA, Abdelzaher T. Range-Free localization schemes in large scale nsor networks. In:Proc. of the 9th Annual Int’l Conf. on Mobile Computing and Networking. San Diego: ACM Press, 2003. 81−95. www.cs.virginia. edu/~th7c/paper/APIT_CS-2003-06.pdf
