1. 引言
无线传感器网络作为一种新型的数据采集、分发手段，在战场侦查、环境监测、事故救援和人员定位等方面有广泛的应用 [1] 。节点位置是各项应用的基础支撑，传感器节点监测、感知的信息只有与特定的位置相结合才能为相关应用提供有效的决策支持。然而由于节点自身的体积、资源严重受限，节点定位成为一个颇具挑战的问题 [2] [3] 。
现有的节点定位算法依据是否需要测量距离可以分为两类：1) 基于测距的定位；2) 测距无关的定位。前者可以达到较高的定位精度，但需要每个节点配备精确测距的硬件或细致的系统校准和环境建模过程 [4] [5] ，硬件成本大、实现复杂性高，在大规模传感器网络中不适用；后者在定位节点时仅基于简单的感知和邻接信息，例如无线连通性等，不需要额外的硬件支持，系统整体开销小、定位算法简单易行，但定位精度也相对较低 [6] 。
典型的测距无关的定位算法基于节点的邻接信息，以跳数为距离的衡量单位。假设信号的单跳传播半径为R，那么物理距离在区间[0,R]的锚节点在距离估计中具有相同的跳数1，单跳误差可达R，这导致节点的定位精度很低。
传感器节点通过收发无线报文获得邻接信息时，没有充分利用无线节点的感知能力，无线电接收信号强度RSS (Radio Signal Received)可以在报文接收的同时测量获得，不需要额外的硬件和通信开销。由于RSS随距离呈现衰减的趋势，因此可以定性标示距离的远近，对单跳范围内的邻居锚节点进行更细粒度的区分，并将锚节点的远近信息用于待定位节点的位置估计过程。
基于此，本文提出了信号强度辅助的定位算法SAL (Strength Assisted Localization)，利用RSS的衰减规律进行锚节点距离远近的定性区分，并与三角形内点PIT (Point In Triangle)判断相结合，选择距离最近且满足PIT判断的三个锚节点来进行位置的估计，较质心法 [6] 而言可以有效缩小待定位节点所处的位置范围，对此更小的范围求质心，可以大大提高节点的定位精度；由于SAL不需要对邻居锚节点进行穷尽式判断，因此计算复杂度较APIT有很大降低。另一方面，APIT的有效运行依赖于PIT判断是否成功，若不成功，APIT将会失效，这导致定位结束时，仍有部分节点的位置未确定，为确保100%的定位覆盖率，SAL针对APIT失效的情形专门设计了定位策略，将最近的三个锚节点的质心作为待定位节点的估计位置。
本文其余部分的组织如下：第二部分介绍了相关工作；第三部分提出了信号强度辅助的定位算法SAL；第四部分通过仿真和现场实验对SAL的定位精度和计算复杂度进行了分析比较；第五部分总结并指出了下一步的研究方向。
2. 相关工作
2.1. 测距无关定位算法
最经典的测距无关定位算法是质心法 [6] 和DV-Hop算法 [7] [8] [9] [10] ，在该算法中锚节点周期性地广播信标报文，报文中包含自身的ID号和位置信息。当待定位节点接收到不同锚节点的信标数量超过某一预设门限或超时发生后，该节点就将锚节点的质心作为自身的估计位置。质心法基于网络连通性，实现简单，由于完全以跳数作为距离的度量单位，没有对一跳范围内的锚节点进行细粒度区分，因而定位精度很低。
APIT定位算法 [11] 是对质心法的改进，首先对邻居锚节点组合进行PIT测试，通过计算满足PIT条件的锚节点三角形的重叠区域，来缩小待定位节点所处的位置范围，最后将重叠区域的质心作为节点的估计位置。APIT的计算复杂度很高，对于某个待定位节点而言，假设其邻居锚节点数为n，APIT算法需要穷尽所有的锚节点组合，复杂度为O(n3)。除此之外，APIT在计算三角形的重叠区域时，需要将整个待定位区域划分为栅格，每计算一个新三角形与当前重叠区域的交集时，需要对栅格进行逐一扫描，扫描复杂度为O(m∙n3)，m是区域划分的栅格数目。因而APIT难以在能量和计算资源严重受限的传感器节点上分布式实现。
MSP [12] 利用声音信号在空间中的传播规律，距离声源越远，信号的到达时间越迟。依据信号接收时间，将一跳范围内的节点进行距离远近的排序，进而确定节点间的相对位置。由于声音信号的发射与接收需要额外的硬件，且当区域范围大、待定位节点数多时，要在区域边界以大功率多次发射声源信号，使之从多个不同方向覆盖整个区域，因而MSP的硬件开销大、能耗高、实现复杂，在实际传感器网络中的应用受限。
虽然RSS易受环境及硬件差异的影响，在很多情况下并不是精确测距的首要选择，但除了邻接关系，RSS确实可以提供有用的距离信息。在室外开阔环境下进行多次硬件实验发现，RSS随距离呈现单调衰减的趋势，因此可以定性区分单跳范围内邻居节点的距离远近。而且RSS值可以在节点间收发报文的同时测量得到，不需要额外的硬件和通信开销，较MSP中的声源信号具有更大的优势和实用价值。
2.2. 系统布设开销
在传感器网络定位系统中，锚节点通常配备GPS接收机来获得自身的位置，其成本较普通节点(位置未知的节点)要高很多，因此，为降低硬件成本和布设开销，减少定位所需的锚节点数，而又达到较好的锚节点覆盖率，可通过增大锚节点和待定位节点的无线电射程比ANR (anchor node radio range ratio)来作用于更大的范围，实现对更多待定位节点的覆盖。
极端地，当单个锚节点的无线电信号可以覆盖整个待定位区域时，理论上，三个锚节点足够为区域中所有的待定位节点提供位置参考。然而，对于质心法、APIT等测距无关的定位算法而言，锚节点个数太少会导致待定位节点的估计位置聚团，定位误差增大。因此ANR作为系统布设的重要参数，直接与系统的布设成本相关，同时，对测距无关定位算法的性能具有重要影响。
3. SAL算法
测距无关定位算法APIT较质心法而言，具有较高的定位精度，但其计算开销也高得多。而且对于某个待定位节点而言，当其单跳邻居锚节点数少于三个，或者所有的邻居锚节点组合都不满足PIT测试时，APIT将失效，无法给出该节点的位置估计。
定位覆盖率体现了节点的有效利用比例，没有位置信息的感知数据是没有用处的，未得到定位的节点实际在做无用功，因此确保传感器网络100%的定位覆盖率，对于提高网络的感知能力和节点利用率具有重要意义。
与APIT必须穷尽所有锚节点组合不同，SAL利用接收信号强度RSS定性地判断单跳邻居锚节点的远近，选择满足PIT测试、并且距离最近的三个锚节点作为位置参考锚节点，将其质心作为待定位节点的估计位置；如果没有锚节点满足PIT测试，那么就将RSS值最大的三个锚节点的质心作为待定位节点的估计位置。
SAL算法的实现过程如下：1) 锚节点周期性发送定位信标报文；2) 待定位节点在接收邻居锚节点报文的同时测量RSS，根据邻居锚节点数执行不同的定位策略：a) 若邻居锚节点数 ≥ 3，则根据RSS大小将邻居锚节点排序，形成序列Listnbr，锚节点i排在j前，当且仅当RSSi > RSSj；之后从序列中选择满足PIT测试且RSS值最大的三个锚节点，将其质心作为待定位节点的估计位置；若PIT测试不满足，则将RSS值最大的三个锚节点的质心作为待定位节点的估计位置；b) 若邻居锚节点数 < 3，则利用多跳范围内的锚节点信息进行定位，确保定位覆盖率为100%，算法流程见图1。
SAL利用无线电接收信号强度来对单跳通信范围内的锚节点进行距离远近的区分，通过选择RSS值最大(距离最近)的锚节点可以有效缩小待定位节点位置所处的区域，对一个更小的区域求质心可以有效提高测距无关定位算法的精度。
在SAL算法中，利用距离最近的且符合PIT测试的锚节点进行位置估计，首先需要根据RSS值对邻居锚节点进行排序，复杂度为O(nlogn)，在排序后的邻居列表Listnbr中从前到后进行PIT测试，在最差情况下的复杂度为O(n3)，最优情况下的复杂度为O(1)。除此之外，SAL不需要计算锚节点三角形的重叠区域，扫描开销为0，相较于APIT的O(m∙n3)，计算复杂度大大降低。
下面通过仿真和现场实验来定量比较SAL与质心法、APIT的性能。
4. 性能比较
4.1. 仿真分析
4.1.1. 建立仿真模型
在仿真中，20个锚节点、180个待定位节点在120×120米的正方形区域内等概率随机布设，待定位节点的无线电射程(radio range)为10米，通过改变锚节点和待定位节点的无线电射程比值ANR来改变锚节点的无线电传播半径和待定位节点的邻居锚节点数。
仿真中无线电信号强度采用最常用的对数正态阴影衰落模型 [13] ，如下式所示。
d是发送方和接收方之间的距离，d0是一个参考距离，n是路径损耗系数，Xs是一个零均值的高斯分布，标准差为s，表征了阴影效应。在室外环境进行大规模测量，通过曲线拟合的方法，确定上述参数取值如表1 [14] ：
Figure 1. The flow show of algorithm SAL
图1. SAL算法流程图
Table 1. Parameters of wireless channel model
表1. 标准试验系统结果数据无线信道模型参数
4.1.2. 仿真结果及分析
1) SAL的定位效果
当锚节点在区域中随机布设时，会出现部分待定位节点无法被任何锚节点组覆盖的情形(例如，图2中位于区域边缘的节点)，对这些节点而言，PIT判断不成立，APIT算法将会失效。当ANR = 10时，在图2所示的场景上分别运行质心法和SAL，结果分别如图3、图4所示。从图3可知，质心法导致节点位置出现严重的抱团现象，节点的定位误差很大。这是由于质心法完全基于节点间的邻接信息，没有对单跳范围内的节点进行更细粒度的区分，导致一些待定位节点在定位中使用的参考锚节点几乎相同，进而出现了位置的聚团。SAL算法由于定性使用了RSS作为距离远近的标识，可以对待定位节点进行更准确的位置限定，因而可以有效消除位置估计的聚团现象，提高定位精度，如图4所示。
2) ANR对定位误差的影响
根据节点可定性理论，对于待定位节点而言，只需要三个锚节点的位置及相应的距离值就可以实现
Figure 3. The centration of convex algorithm
图3. 质心法的抱团现象
Figure 4. Localization results of SAL
图4. SAL算法的定位效果
定位。因而，ANR (anchor node radio range ratio)越大，完成网络节点定位所需的锚节点数就越少，相应的硬件开销也越小，极端地，当ANR足够大时，三个锚节点即可以实现整个网络的定位。然而ANR对测距无关定位算法的性能存在重要影响，为定量比较质心法、APIT、SAL的性能受ANR影响的程度，改变ANR值进行多次仿真，结果如图5所示。
由图中可知，随着ANR的增大，质心法、APIT的定位误差亦增大，质心法的误差增加最为剧烈。这是因为随着锚节点无线电射程的增大，单跳距离的粒度更粗，导致节点所处的位置范围更大，进行质心求解时误差也更大。SAL的定位误差最小，且随着ANR的增长最缓慢，当ANR > 6时，定位误差甚至出现了下降的趋势，这得益于接收信号强度可以对单跳范围进行更细粒度的划分，有效缩小了节点位置所处的区域，提高了节点的定位精度。
3) SAL的计算复杂度
APIT算法需要穷尽所有的锚节点组合，计算复杂度为O(n3)。而SAL算法在PIT判断阶段，并不是穷尽所有的锚节点组合，而是从距离最近的锚节点开始进行PIT判断，一旦满足，立即停止，只有在最差情况下才会穷尽所有的锚节点组合。
为比较APIT和SAL在实际定位中的计算复杂度，在100个随机生成的网络中进行仿真，平均结果见图6，横坐标AH表示180个待定位节点在定位过程中使用的平均锚节点数，纵坐标表示PIT判断的次数。从图6可知，在定位过程中，SAL的计算复杂度比APIT小得多，至多仅为后者的1/4。
4.2. 现场实验分析
4.2.1
. 实验设备和场景
实验采用USRP 2930平台进行无线信号的发送和接收，并在接收信号的同时测量信号接收强度RSS。如图7(a)所示。9个USRP节点在操场40 m × 40 m的区域内布设，为尽量降低操场地面对无线信号造成的多径效应，采用三脚架将USRP节点抬高，实验场景和节点拓扑图分别见图7(b)和图8。
4.2.2
. 实验结果
改变USRP平台的发射功率，从30 mW到100 mW变换，三种定位算法的性能比较见图9。从图中可知，随着发送功率的增大，定位误差呈现下降趋势。与质心法和APIT算法比较而言，SAL算法有效利用了USRP锚节点的RSS信息对待定位节点的位置进行更精确地估计，节点定位精度有了明显提高。
Figure 5. Relationship of localization error and ANR
图5. 定位误差与ANR的关系图
Figure 6. Computation complexity of APIT and SAL
图6. APIT和SAL的计算复杂度比较
(a) 
(b)
Figure 7. (a) USRP platform, (b) Experiment scenario
图7.(a) USRP平台，(b) 实验场景
5. 结束语
本文利用易于测量的RSS值作为锚节点距离远近的定性度量，提出了强度辅助的定位算法SAL，可以在节点上完全分布式独立执行，并确保网络100%的定位覆盖率。在不需要额外硬件、不增大通信开销的情况下，有效提高了节点的定位精度，在随机布设下，定位误差小于APIT，计算开销低于APIT的1/4，在大范围室外传感器网络定位应用中具有显著的优势。下一步我们将研究在室内及其他多径影响严重的环境下SAL的性能，并提出改进的措施，扩大SAL的适用范围。
基金项目
国家自然科学基金(61273047，61573376)。