消防监督检查箱:无线传感器网络的节点自定位技术

摘要:文章对无线传感器网络的节点定位机制与算法进行了介绍，并对基于测距的和不基于测距的两大类方法进行了分析对比。文章认为节点定位是无线传感器网络的一项关键技术，对于无线传感器网络的许多应用来说节点位置信息都是必须的基本信息，虽然目前已有不少节点定位技术，但仅仅是一些初步的研究成果，距离无线传感器网络的整体优化目标还很不够，需要继续深入研究开发，提出更多的高效算法，促进无线传感器网络进一步的普及应用。
关键字:无线传感器网络；自组织网络；定位算法
英文摘要:The paper introduces the self-localization mechanism and some algorithms for Wireless Sensor Network (WSN). Moreover, it analyzes and compares the range-based and range-free localization algorithms. It thinks that node location is a key technology for WSN and the information about node location is indispensable to many applications of WSM. Existing node location technologies are the primary research achievements, which are far from the goal of the whole WSN optimization. Therefore, further research and development of more high-efficient algorithms is necessary for popularization of WSN applications.
英文关键字:wireless sensor network; Ad hoc network; localization algorithm
基金项目：国家自然科学基金项目(60372097)
人类进入信息社会的一个主要标志就是因特网的迅速普及应用。因特网是信息传输网络与信息处理计算机相互融合的产物。当前的因特网使人类社会进入了“网络即计算机”的网络时代，人们可以在网上找到资源，进行网络计算和存储资料。而传感器网络将是信息获取(传感)、信息传输与信息处理三大子领域技术又一次相互融合的产物，人们可以通过传感网络直接感知真实客观世界的一切，从而极大地扩展网络的功能和人类认识世界的能力，必将极大地推动相关学科的发展，并带来社会的深刻变革。因此、传感器网络将逐渐引领人类步入“网络即传感器”的传感时代。
无线传感器网络典型的网络结构和工作方式如下：
将大量传感器节点布置或抛洒到感兴趣的区域，节点通过自组织快速形成一个无线网络。每个节点都有自己控制的一个区域，通过感知设备，如温度、湿度、声音或光学设备，化学分析装置，电磁感应装置等，来对周围的物理环境进行监控，也可以通过配置一些专用的功能单元来实现与特定环境交互的功能。节点的通信距离一般较短，只能与自己通信范围内的其他传感器节点(称作邻居节点或邻居)交换数据。要访问通信范围以外的节点，必须使用多跳路由。因此，节点既是信息的采集和发出者，也是信息的转发传输者，采集的数据通过多跳路由到达汇聚节点(一些文献也称作网关)，汇聚节点是一个特殊的节点，可以通过Internet、移动通信网络、卫星等与监控中心通信。也可以利用飞机飞越网络上空，通过无线通信采集网关数据。为了保证网络内大多数节点都可以与网关建立无线链路，并且保证传感器节点对目标区域有很好的覆盖，节点的分布要相当的密集。高密度分布还可以在某些传感器节点能量耗尽或者出现故障时不影响网络的连通性和整体的工作。无线传感器网络典型的体系结构如图1所示。节点具有传感、信号处理和无线通信功能。

与传统的无线网络相比，无线传感器网络具有以下特点：
(1)电源容量有限。无线传感器网络节点一般由电池供电，而且在使用过程中也不能给电池充电或更换电池。因此无线传感器网络设计的基本原则就是都要以节能为前提。
(2)传感器节点由于受到低成本、小体积和低功耗的限制，其硬件、软件资源非常有限。
(3)无中心。无线传感器网络一般是一个对等式的网络。
(4)自组织。无线传感器网络的布设和展开无需依赖于任何预设的基础设施。
(5)多跳路由。网络中节点通信距离有限，如果希望与较远的节点进行通信，则需要通过中间节点多跳路由来实现。
(6)动态拓扑。无线传感器网络是一个动态的网络，节点可以随处移动；网络的拓扑结构会随时发生变化，因此网络应该具有动态拓扑组织功能。
(7)节点数量众多，分布密集。为了对一个区域执行监测任务，传感器节点往往分布得非常密集，利用节点之间高度连接性来保证系统的容错性和抗毁性。
无线传感器网络属于一种特殊的Ad hoc网络[1—5]，它虽然与传统的Ad hoc网络有很多相似的地方，但是与传统的Ad hoc网络相比，无线传感器网络的节点分布更加密集，能量更加有限，无线传感器网络中的传感器节点在大多数情况下是静止的。在无线传感器网络中，数据是被分散处理的，系统会根据需要尽早对数据进行处理，这样可以减少网络的流量，降低功耗并提高系统利用率。由于成本和功耗的限制，无线传感器网络节点的硬件设备资源十分有限，数据的处理能力和存储能力都比较弱。这就决定了在设计无线传感器网络各层技术标准的时候都要以简单和节能为最重要的前提条件。
无线传感器网络的协议分层结构基本采用传统网络的分层结构，即包括物理层、数据链路层、网络层、传输层和应用层。另外，能量、移动、任务等管理平台用于监控网络中的能量利用、节点移动和任务分配。这些平台能够帮助传感器节点在较低能耗下协作完成某些监控任务。图2所示为无线传感器网络的协议栈结构。

能量管理平台用来管理一个节点如何使用它的能量。例如，当一个节点收到一个邻居节点发来的消息之后，它可以将它的接收机关闭，避免接收到重复的消息。同样，当一个节点的能量极低时，它会向邻节点广播一条消息，告诉邻节点自己已经没有多少能量，不能再用来对消息进行传递了，这样它就可以不再接收邻节点发来的需要传递的消息，将能量都留给自己的消息发送。移动管理平台能够监测并记录节点的移动。任务管理平台用来平衡和规划某个区域的感知任务，安排哪些节点执行哪些感知任务，能量高的节点可以比那些能量低的节点多承担一些任务。有了这些管理平台，节点能够低能耗地协调工作，能够在移动的情况下传递数据，能够在节点之间共享资源。
无线传感器网络自身的特点决定了它不能使用目前已经存在的一些标准协议，国外的研究工作者为无线传感器网络的各个层次都提出了一些解决方案，但是总的来说，到目前为止还没有形成可被广泛认同的标准。
1 无线传感器网络的节点定位机制
关于无线传感器网络的定位问题分为两类，一类是无线传感器网络对自身传感器节点的定位，另一类是无线传感器网络对外部目标的定位。本文主要讨论前者。
节点准确地进行自身定位是无线传感器网络应用的重要条件。由于节点工作区域或者是人类不适合进入的区域，或者是敌对区域，传感器节点有时甚至需要通过飞行器抛撒于工作区域，因此节点的位置都是随机并且未知的。然而在许多应用中，节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意义，否则，如果不知道数据所对应的地理位置，数据就失去意义。除此之外，无线传感器网络节点自身的定位还可以在外部目标的定位和追踪以及提高路由效率等方面发挥作用。因此，实现节点的自身定位对无线传感器网络有重要的意义。
获得节点位置的一个直接想法是利用全球定位系统(GPS)来实现。但是，在无线传感器网络中使用GPS来获得所有节点的位置受到价格、体积、功耗以及可扩展性等因素限制，存在着一些困难。因此目前主要的研究工作是利用传感器网络中少量已知位置的节点来获得其他未知位置节点的位置信息。已知位置的节点称作锚节点，它们可能是被预先放置好的，或者采用GPS或其他方法得知自己的位置。未知位置的节点称作未知节点，它们需要被定位。锚节点根据自身位置建立本地坐标系，未知节点根据锚节点计算出自己在本地坐标系里的相对位置。
根据具体的定位机制，可以将现有的无线传感器网络自身定位方法分为两类：基于测距的(Range-based)方法和不基于测距的(Range-free)方法[6]。基于测距的定位机制需要测量未知节点与锚节点之间的距离或者角度信息，然后使用三边测量法、三角测量法或最大似然估计法计算未知节点的位置。而不基于测距的定位机制无需距离或角度信息，或者不用直接测量这些信息，仅根据网络的连通性等信息实现节点的定位。
1.1  基于测距的定位方法
常用的定位方法是基于测距定位方法，在这种定位机制中需要先得到两个节点之间的距离或者角度信息，通常采用以下方法。
1.1.1  信号强度测距法
已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为距离。例如，在自由空间中，距发射机d 处的天线接收到的信号强度由下面的公式给出：
Pr(d )=PtGtGrλ2/(4π)2d 2L      (1)
其中，Pt为发射机功率；Pr(d )是在距离d 处的接收功率；Gt、Gr分别是发射天线和接收天线的增益；d 是距离，单位为米；L为与传播无关的系统损耗因子；λ是波长，单位为米。由公式可知，在自由空间中，接收机功率随发射机与接收机距离的平方衰减。这样，通过测量接收信号的强度，再利用式(1)就能计算出收发节点间的大概距离。
得到锚节点与未知节点之间的距离信息后，采用三边测量法或最大似然估计法可计算出未知节点的位置。三边计算的理论依据是，在三维空间中，知道了一个未知节点到三个以上锚节点的距离，就可以确定该点的坐标。
三边测量法在二维平面上用几何图形表示出来的意义是：当得到未知节点到一个锚节点的距离时，就可以确定此未知节点在以此锚节点为圆心、以距离为半径的圆上；得到未知节点到3个锚节点的距离时，3个圆的交点就是未知节点的位置。如图3所示。

然而，公式(1)只是电磁波在理想的自由空间中传播的数学模型，实际应用中的情况要复杂的多，尤其是在分布密集的无线传感器网络中。反射、多径传播、非视距(NLOS)、天线增益等问题都会对相同距离产生显著不同的传播损耗。因此这种方法的主要误差来源是环境影响所造成的信号传播模型的复杂性。信号强度测距法通常属于一种粗糙的测距技术。
还有一些其他算法：如文献[7]提出了一种节点位置推测算法，该算法通过一种判决节点，利用收集到的锚节点的位置信息和节点间的距离信息，执行节点位置推测算法，推测出所有位置可确定的待测节点的位置。
1.1.2  到达时间及时间差测距法
到达时间(TOA)技术通过测量信号传播时间来测量距离。在TOA方法中，若电波从锚节点到未知节点的传播时间为t，电波传播速度为c，则锚节点到未知节点的距离为t×c。TOA要求接收信号的锚节点或未知节点知道信号开始传输的时刻，并要求节点有非常精确的时钟。
使用TOA技术比较典型的定位系统是GPS，GPS系统需要昂贵高能耗的电子设备来精确同步卫星时钟。在无线传感器网络中，节点间的距离较小，采用TOA测距难度较大，同时节点硬件尺寸、价格和功耗的限制也决定了TOA技术对无线传感器网络是不可行的。
时间差(TDOA)测距技术在无线传感器网络定位方案中得到了较多的应用[8]。通过记录两种不同信号(常使用无线电信号和超声波信号)的到达时间差异，根据已知的两种信号的传播速度，直接把时间差转化为距离。该技术受到超声波传播距离的限制和非视距问题对超声波信号传播的影响，不仅需要精确的时钟记录两种信号的到达时间差异，还需要传感器节点同时具备感知两种不同信号的能力。
1.1.3  时间差定位法
TDOA测距是通过计算两种不同无线信号到达未知节点的时间差，再根据两种信号传播速度来计算得到未知节点与锚节点之间的距离。TDOA定位与TDOA测距不同，TDOA定位计算两个锚节点信号到达未知节点的时间差，将其转换成到两个锚节点的距离之差，未知节点通过到多组锚节点的距离之差得出自身的位置。
在二维平面上的，双曲线的几何意义是到两个定点的距离之差为一个常数的所有点的集合，两个定点称作焦点。因此TDOA定位在二维平面上的几何意义为：得到未知节点与两个锚节点的距离之差，即可知未知节点定位于以两个锚节点为焦点的双曲线方程上，通过测量得到未知节点所属的两个以上双曲线方程时，这些双曲线唯一的交点即为未知节点的位置。由于这种方法不是采用到达的绝对时间来确定节点的位置，降低了对时间同步的要求，但是仍然需要较精确的计时功能，同时由于无线传感器网络具有分布密集和无线通信范围小的特点，这种方法实现起来难度较大。
1.1.4  到达角定位法
到达角(AOA)定位法通过阵列天线或多个接收器结合来得到相邻节点发送信号的方向，从而构成一根从接收机到发射机的方位线。两根方位线的交点即为未知节点的位置。
图4所示为基本的AOA定位法，未知节点得到与锚节点N1和N2所构成的角度之后就可以确定自身位置。另外，AOA信息还可以与TOA、TDOA信息一起使用成为混合定位法。采用混合定位法或者可以实现更高的精确度，减小误差，或者可以降低对某一种测量参数数量的需求。AOA定位法的硬件系统设备复杂，并且需要两节点之间存在视距(LOS)传输，因此不适合用于无线传感器网络的定位。

1.2  不基于测距的定位算法
基于测量距离和角度的算法的缺点是使传感器节点造价增高，消耗了有限的电池资源，而且在测量距离和角度的准确性方面需要大量的研究。下面介绍不基于测距的定位算法。不基于测距的算法不需要知道未知节点到锚节点的距离或者不需要直接测量此距离，在成本和功耗方面比基于测距的方法具有优势。
下面先介绍4种重要的分布式不基于测距的算法，它们分别为质心法、基于距离矢量计算跳数的算法(DV-Hop)、无定形的(Amorphous)算法和以三角形内的点近似定位(APIT)算法，然后对这4种算法进行分析对比。
1.2.1  质心法
质心法[9]是南加州大学Nirupama Bulusu等学者提出的一种仅基于网络连通性的室外定位算法。该算法的中心思想是：未知节点以所有在其通信范围内的锚节点的几何质心作为自己的估计位置。具体过程为：锚节点每隔一段时间向邻居节点广播一个信标信号，信号中包含有锚节点自身的ID和位置信息。当未知节点在一段侦听时间内接收到来自锚节点的信标信号数量超过某一个预设的门限后，该节点认为与此锚节点连通，并将自身位置确定为所有与之连通的锚节点所组成的多边形的质心。
质心定位算法的最大优点是它非常简单，计算量小，完全基于网络的连通性，但是需要较多的锚节点。
1.2.2  DV-Hop算法
DV-Hop算法[10]是由D.Niculescu和B.Nath等人提出的。DV-Hop定位算法的原理与经典的距离矢量路由算法比较相似。在DV-Hop算法中，锚节点向网络广播一个信标，信标中包含有此锚节点的位置信息和一个初始值为1的表示跳数的参数。此信标在网络中被以泛洪的方式传播出去，信标每次被转发时跳数都增加1。接收节点在它收到的关于某一个锚节点的所有信标中保存具有最小跳数值的信标，丢弃具有较大跳数值的同一锚节点的信标。通过这一机制，网络中所有节点(包括其他锚节点)都获得了到每一个锚节点的最小跳数值。图5为一个示意图[6]，表示了网络中的节点到锚节点A的跳数值。

为了将跳数值转换成物理距离，系统需要估计网络中平均每跳的距离。锚节点具有到网络内部其他锚节点的跳数值以及这些锚节点的位置信息，因此锚节点可以通过计算得到距其他锚节点的实际距离。经过计算，一个锚节点得到网络的平均每跳距离，并将此估计值广播到网络中，称作校正值，任何节点一旦接收到此校正值，就可以估计自己到这个锚节点的距离。
如果一个节点能够获得到3个以上锚节点的估计距离，它就可以利用三边法估计其自身的位置。
DV-Hop算法与基于测距算法具有相似之处，就是都需要获得未知节点到锚节点的距离，但是DV-Hop获得距离的方法是通过网络中拓扑结构信息的计算而不是通过无线电波信号的测量。
在基于测距的方法中，未知节点只能获得到自己射频覆盖范围内的锚节点的距离，而DV-Hop算法可以获得到未知节点无线射程以外的锚节点的距离，这样就可以获得更多的有用数据，提高定位精度。
1.2.3  Amorphous算法
Amorphous定位算法[11]与DV-Hop算法类似。首先，采用与DV-Hop算法类似的方法获得距锚节点的跳数，称为梯度值。未知节点收集邻居节点的梯度值，计算关于某个锚节点的局部梯度平均值。与DV-Hop算法不同的是：Amorphous算法假定预先知道网络的密度，然后离线计算网络的平均每跳距离，最后当获得3个或更多锚节点的梯度值后，未知节点计算与每个锚节点的距离，并使用三边测量法和最大似然估计法估算自身位置。
1.2.4  APIT算法
在APIT算法[6]中，一个未知节点从它所有能够与之通信的锚节点中选择3个节点，测试它自身是在这3个锚节点所组成的三角形内部还是在其外部；然后再选择另外3个锚节点进行同样的测试，直到穷尽所有的组合或者达到所需的精度。如果未知节点在某三角形内部，称此三角形包含未知节点；最后，未知节点将包含自己的所有三角形的相交区域的质心作为自己的估计位置。
APIT算法最关键的步骤是测试未知节点是在3个锚节点所组成的三角形内部还是外部，这一测试的理论基础是三角形内的点(PIT)测试。PIT测试用来测试一个节点是在其他3个节点所组成的三角形内部还是在其外部，其原理如图6所示：假如存在一个方向，沿着这个方向M点会同时远离或者同时接近A、B、C 3个点，那么M位于△ABC外；否则，M位于△ABC内。这就是PIT测试的原理，其证明可以在文献[6]中找到。

在静态网络中，M点固定，不能朝着不同的方向移动，此时无法执行PIT测试，为此定义APIT测试(Approximate PIT)：假如节点M的邻居节点中没有同时远离或同时靠近3个锚节点A、B、C的节点，那么M就在△ABC之内；否则M就在△ABC外，如图7所示。

这种方法是利用网络较高的节点密度来模拟节点移动，根据给定方向上一个节点距离锚节点越远接收信号强度越弱的无线传播特性来判断距锚节点的远近。在无线传感器网络中，邻居节点间互相交换信息，仿效PIT测试的节点移动。如图7中左图所示，节点M通过与邻居节点1交换信息，得知自身如果运动至节点1，将远离锚节点B和C，但会接近锚节点A，与邻居节点2、3、4的通信和判断过程类似，最终确定自身位于△ABC内，而在图7的右图中，节点M可知假如自身运动至邻居节点2处，将同时远离锚节点A、B、C，故判断自身不在△ABC中。
当节点M比较靠近△ABC的一条边，或者M周围的邻居节点分布不均匀时，APIT的判断可能会发生错误，当未知节点密度较大时，APIT判断发生错误的概率较小。
1.2.5  几种不基于测距的定位算法的比较
节点之间的无线通信所消耗的电能比其他部件所消耗的电能要大很多，所以应尽量减少节点之间的无线通信量。由于每个节点的能量十分有限，也不宜将大量的通信和计算固定于某个或者某些节点，否则，这些节点的电能会很快耗尽，出现网络中节点不均衡的情况。因此，在无线传感器网络中，要求尽量采用分布式的节点定位算法，即定位的计算过程分散在每个未知节点上而不是依赖于在某个中心节点进行集中计算。前边介绍的4种不基于测距的定位算法都属于分布式算法，此外，还有很少的几种集中式不基于测距的定位算法，它们的定位精度与分布式算法没有明显区别，并且需要进行集中计算。
质心、DV-Hop、Amorphous和APIT算法是完全分布式的，仅需要少量通信和简单计算，具有良好的扩展性。无线传感器网络自身定位算法的性能对其可用性有直接的影响，如何评价定位算法是一个需要研究的问题。目前已有几个常用的标准，如定位精度、锚节点密度、未知节点密度、计算量、节点之间的通信量等，但这些标准还没有达到完善和统一的程度，需要进一步地模型化和量化。文献[6]中经过大量实验对比了4种分布式不基于测距的定位算法，其结果见表1。表1可以帮助加强对不基于测距的定位算法的理解以及促进完整评估体系的建立。

不规则性的程度(DOI)表示节点无线传播模型的不规则性。当它为0时，无线传播模型为球型，DOI值越大表示节点无线传播模型越不规则。
总的来说，不基于测距的定位机制属于粗精度的定位机制，然而粗精度定位对大多数无线传感器网络的应用已经足够，研究表明，当定位误差小于传感器节点无线通信半径的40%时，定位误差对路由性能和目标追踪精确度的影响不会很大。
2 结束语
与传统的无线网络相比，无线传感器网络电源容量有限，传感器节点由于受到低成本、小体积和低功耗的限制，其硬件软件资源非常有限。无线传感器网络一般是一个对等的、自组织、多跳路由的、动态的网络。而且节点数量众多，分布密集，利用节点之间高度连接性来保证系统的容错性和抗毁性。因此、对于无线传感器网络这种资源极度受限的特殊系统而言，如果仍然依据原有的网络通信7层协议的模型来进行设计，将是很不适合的，需要做较大的变革。需要采用一种整体优化的方法，即是要跨越物理层、网络层、应用层，以及跨越嵌入式操作系统、网络节点的业务类型、网络节点的协同处理和特殊应用需求等多个层次，进行系统整体的优化设计，才能满足无线传感器网络的特殊要求。
节点定位是无线传感器网络的一项关键技术，对于无线传感器网络的许多应用来说节点位置信息都是必须的基本信息；而且节点定位的一些算法也从一定程度上反映了无线传感器网络的特殊性。目前已有的节点定位技术还仅仅是一些初步的研究成果，距离无线传感器网络的整体优化目标还有很多工作要做；相信随着研究开发的继续深入，还会有更多的高效算法出现，从而促进无线传感器网络进一步的普及应用。
3 参考文献
[1] Zhao Feng, Guibas L J. Wireless Sensor Networks: An Information Processing Approach [M]. Amsterdam (Netherlands): Morgan Kaufmann Publishers, 2004.
[2]Callaway E H J. Wireless Sensor Networks: Architectures and Protocols [M]. Boca Raton (FL, USA): CRC Press, 2003.
[3] Raghavendra C S, Sivalingam K M, Znati T. Wireless Sensor Networks [M]. Boston (MA, USA): Kluwer Acadenic Publishers, 2004.
[4] 朱近康. 无线传感器网络技术 [J]. 中兴通讯技术, 2004,10(S0):14—15.
[5] 朱林, 袁晓, 葛利嘉, 等. 超宽带无线传感器网络综述 [J]. 测控技术, 2004,23(12): 1—4.
[6] He Tian, Huang Chengdu, Blum B M, et al. Range-free Localization Schemes in Large Scale Sensor Networks [A]. Proceedings of the 9th Annual International Conference on Mobile Computing and Networking,MOBICOM′ 2003 [C]. San Diego (CA, USA), 2003. New York (NY, USA): ACM Press, 2003.81—95.
[7] 孙学斌, 王汇源, 周正. 自组网中节点位置推测算法的研究 [J]. 山东大学学报 (工学版), 2003,34(3):55—59.
[8] 史龙, 王福豹, 段渭军, 等. 无线传感器网络Range-Free自身定位机制与算法 [J]. 计算机工程与应用, 2004,40(23):127—130,151.
[9] Bulusu N, Heidemann J, Estrin D. GPS-less Low- cost Outdoor Localization for Very Small Devices [J]. IEEE Personal Communications, 2000,7(5):28—34.
[10] Niculescu D, Nath B. Ad hoc Positioning System [A]. Conference Record of IEEE Global Telecommunications Conference, GLOBECOM′2001, Vol 5 [C]. San Antonio (TX, USA), 2001. Piscataway (NJ, USA): IEEE, 2001.2926—2931.
[11] Priyantha N B, Miu A K L, Balakrishnan H, et al. The Cricket Compass for Context-aware Mobile Applications [A]. Proceedings of 7th ACM International Conference on Mobile Computing and Networking, MOBICOM′ 2001 [C]. Rome (Italy), 2001.New York (NY,USA): ACM Press, 2001.1—14.
收稿日期：2005-05-15
周正，北京邮电大学工学博士。北京邮电大学教授、博士生导师。长期从事通信电路与系统、信号处理的教学与科研工作。近年来主持和参加了多项国家教育部博士点基金、国家自然科学基金、国家“863”计划及原邮电部重点科研项目的研究。在国内外学术会议及学术刊物上已发表论文80多篇，出版译著3部。现从事宽带无线通信、短距离无线通信、智能信号处理及通信网络优化等方面的研究。