传感器网络结点定位的研究问题

1）基本概念和算法

（1）传感器网络结点定位的基本概念

在传感器网络结点定位技术中，根据结点是否已知自身的位置，把传感器结点分为信标结点（beacon node）和未知结点（unknown node）。信标结点在传感器结点中所占的比例很小，可以通过携带GPS定位设备等手段获得自身的精确位置。信标结点是未知结点定位的参考点。除了信标结点外，其他传感器结点就是未知结点，它们通过信标结点的位置信息来确定自身位置。

（2）基本术语

·邻居结点（neighbor node）：传感器结点通信半径内的所有其他结点称为该结点的邻居结点；

·跳数（hop count）：两个结点之间间隔的跳段总数称为两个结点间的跳数；

·跳段距离（hop distance）：两个结点之间间隔的各跳段距离之和称为两结点间的跳段距离；

·基础设施（infrastructure）：指协助传感器结点定位的已知自身位置的固定设备，如卫星、基站等；

·到达时间（Time of Arrival，TOA）：信号从一个结点传播到另一结点所需要的时间称为信号的到达时间；

·到达时间差（Time Difference Of Arrival，TDOA）：两种不同传播速度的信号从一个结点传播到另一个结点所需要的时间之差称为信号的到达时间差；

·接收信号强度指示（Received Signal Strength Indicator，RSSI）：结点接收到的无线信号的强度大小称为接收信号的强度指示；

·到达角度（Angle of Arrival，AOA）：结点接收到的信号相对于自身轴线的角度称为信号相对接收结点的到达角度；

·视线关系（Line of Sight，LOS）：两个结点间没有障碍物间隔，能够直接通信，称为两个结点间存在视线关系；

·非视线关系（NLOS，no LOS）：指两个结点之间存在障碍物。

（3）定位性能的评价指标

衡量定位性能有多个指标，除了一般性的位置精度指标以外，对于资源受到限制的传感器网络，还有覆盖范围、刷新速度和功耗等其他指标。

位置精度是定位系统最重要的指标，精度越高，则技术要求越严，成本也越高。位置精度分为绝对精度和相对精度。绝对精度指以长度为单位度量的精度，例如GPS的精度为1～10m，现在使用的GPS导航系统的精度约为5m。一些商用室内定位系统提供30cm的精度，可以用于工业环境、物流仓储等场合。

相对精度通常以结点之间距离的百分比来定义。例如，若两结点之间的距离是20m，定位精度为2m，则相对定位精度为10%。由于有些定位方法的绝对精度会随着距离的变化而变化，因而使用相对精度可以很好地表示精度指标。

设结点i的估计坐标与真实坐标在二维情况下的距离差值为Δdi，则N个未知位置结点的网络平均定位误差为

覆盖范围和位置精度是一对矛盾性的指标。例如超声波可以达到分米级精度，但是它的覆盖范围只有十多米；Wi－Fi和蓝牙的定位精度为3m左右，覆盖范围达到100m左右；GSM系统能覆盖千米级范围，但精度只能达到100m。由此可见，覆盖范围越大，提供的精度就越低。如果希望提供大范围内的高精度，通常是难以实现的。

刷新速度是指提供位置信息的频率。例如，如果GPS每秒刷新1次，则对于车辆而言已经足够了，让人能体验到实时服务的感觉。对于移动的物体，若位置信息刷新较慢，则会出现严重的位置信息滞后，直观上感觉已经前进了很长距离，提供的位置却还是以前的位置。因此，刷新速度影响了定位系统实际工作提供的精度，还影响位置控制者的现场操作。如果刷新速度太低，可能使操作者无法实施实时控制。

传感器网络通常是由电池供电的自组织多跳网络，电能和有效带宽受到很大限制，因而在定位服务方面有一些特有的技术指标，如功耗、容错性和实时性等。

功耗作为传感器网络设计的一项重要指标，对于定位这项服务功能，人们需要计算为此所消耗的能量。采用的定位方法不同，则功耗差别会很大，主要原因是定位算法的复杂度不同，需要为定位提供的计算和通信开销方面存在数量上的差别，因而导致完成定位服务的功耗有所不同。

传感器网络定位系统需要比较理想的无线通信环境和可靠的网络结点设备。但是真实应用场合通常会存在许多干扰因素。因此，传感器网络定位系统的软硬件必须具有很强的容错性，能够通过自动纠正错误，克服外界的干扰因素，减小各种误差的影响。

定位实时性更多体现在对动态目标的位置跟踪。由于动态目标具有一定的运动速度和加速度并且不断地变换位置，因此在运用传感器网络实时定位时，需要尽量缩短定位计算过程的时间间隔。这就要求定位系统能以更高的频率采集和传输数据，定位算法能在较少信息的辅助下，输出满足精度要求的定位结果。

（4）计算结点位置的基本方法

传感器结点定位过程中，未知结点在获得相对于邻近信标结点的距离，或获得邻近的信标结点与未知结点之间的相对角度后，通常使用下列方法计算自己的位置。

①三边测量法

三边测量法（trilaberation）原理如图4－4所示，已知A、B、C三个结点的坐标分别为（xa，ya）、（xb，yb）、（xc，yc），它们到未知结点D的距离分为da、db、dc，假设结点D的坐标为（x，y）。那么存在下列公式：

图4－4　三边测量法原理图示

(www.xing528.com)

由式（4－9）、（4－10）、（4－11）可以得到结点D的坐标为：

②三角测量法

三角测量法（triangulation）原理如图4－5所示，已知A、B、C三个结点的坐标分别为（xa，ya）、（xb，yb）、（xc，yc），结点D相对于结点A、B、C的角度分别为∠ADB、∠ADC、∠BDC，假设结点D的坐标为（x，y）。

对于结点A、C和∠ADC，如果弧段AC在△ABC内，那么能够唯一确定一个圆，设圆心为O1（xO1，yO1），半径为r1，那么α＝∠AO1C＝（2π－2∠ADC），并存在下列公式：

图4－5　三角测量法原理图示

由式（4－13）、（4－14）、（4－15）能够确定圆心O1点的坐标和半径r1。同理，对结点A、B和∠ADB以及结点B、C和∠BDC分别确定相应的圆心O2（xO2，yO2）、半径r2以及圆心O3（xO3，yO3）、半径r3。

最后利用三边测量法，由点D（x，y），O1（xO1，yO1），O2（xO2，yO2），O3（xO3，yO3）确定D点的坐标。

③极大似然估计法

极大似然估计法（Maximum Likelihood Estimation）原理如图4－6所示，已知1，2，3等n个结点的坐标分别为（x1，y1），（x1，y2），（x3，y3），…，（xn，yn），它们到结点D的距离分别为d1，d2，d3，…，dn，假设结点D的坐标为（x，y）。那么存在下列公式：

图4－6　极大似然估计法原理图示

从第一个方程开始分别减去最后一个方程，得：

使用标准的最小均方差估计方法可以得到结点D的坐标为：。

④Min－max定位法

多边定位法的浮点运算量大，计算代价高。Min－max定位法是根据若干锚点位置和至待定位结点的测距值，创建多个正方开边界框，所有边界框的交集为一矩形，取此矩形的质心作为待定位结点的坐标。这种定位方法计算简单，许多研究人员以此为基础衍生出自己的定位方案。

图4－7为采用三个锚点进行定位的Min－max法示例，即以某锚点i（i＝1，2，3）的坐标（xi，yi）为基础，加上或减去测距值d，得到锚点i的边界框：［xi－di，yi－di］×［xi＋di，yi＋di］。

图4－7　Min－max定位法原理图示

在所有位置点［xi＋di，yi＋di］中取最小值、所有［xi－di，yi－di］中取最大值，则交集矩形取作：［max（xi－di），max（yi－di）］×［min（xi＋di），min（yi＋di）］。三个锚点共同形成交叉矩形，矩形质心即为待定位结点的估计位置。

2）定位算法分类

在传感器网络中，定位算法通常有以下几种分类：

（1）基于距离的定位算法和距离无关的定位算法

根据定位过程中是否测量实际结点间的距离，把定位算法分为：基于距离的（rangebased）定位算法和距离无关的（range－free）定位算法［5］。前者需要测量相邻结点间的绝对距离或方位，并利用结点间的实际距离来计算未知结点的位置；后者无需测量结点间的绝对距离或方位，而是利用结点间的估计距离计算结点位置。本章将以此种分类为线索介绍各种定位算法。

（2）递增式定位算法和并发式定位算法

根据结点定位的先后次序不同，把定位算法分为：递增式（incremental）定位算法和并发式（concurrent）定位算法［6］。递增式定位算法通常从信标结点开始，信标结点附近的结点首先开始定位，依次向外延伸，各结点逐次进行定位。这类算法的主要缺点是定位过程中累积和传播测量误差。并发式定位算法中所有的结点同时进行位置计算。

（3）基于信标结点的定位算法和无信标结点的定位算法

根据定位过程中是否使用信标结点，把定位算法分为：基于信标结点的（beacon－based）定位算法和无信标结点的（beacon－free）定位算法。前者在定位过程中，以信标结点作为定位中的参考点，各结点定位后产生整体绝对坐标系统；后者只关心结点间的相对位置，在定位过程中无需信标结点，各结点先以自身作为参考点，将邻近的结点纳入自己定义的坐标系中，相邻的坐标系统依次转换合并，最后产生整体相对坐标系统。