无线传感器网络中多日冕分割定位算法的设计*

张 拓，钱升港，蒋 健，毛科技，徐瑞吉，邱杰凡，何文秀

(1.浙江工业大学计算机科学与技术学院，浙江 杭州 310023；2 浙江省信息安全标准化技术委员会，浙江 杭州 310000；3.浙江工业大学之江学院，浙江 绍兴 312030)

无线传感器网络(Wireless Sensor Network，WSN)的定位技术可以分为测距和非测距两种[1]。 基于测距的技术需要通过到达时间(Time of Arrival，TOA)[2]、到达角(Angle of Arrival，AOA)[3]、到达时间差(Time Difference of Arrival，TDOA)[4]或无线电信号强度(Received Signal Strength，RSS)[5]来分析节点位置。 而现实环境中的噪声不可避免地影响了距离测量的准确性，有时甚至导致测量结果不可靠。 同时，随着定位精度和规模的要求不断增加，网络的复杂度和成本也随之增加。 非测距定位技术在很大程度上减少了额外的噪音影响和设备成本。 本文简化了一般非测距技术需要的条件，只需要满足以下要求即可进行非测距定位:①无线传感器网络中需要存在位置的锚节点，②非锚节点可能不与锚节点直接通信而是借助其他非锚节点，③需要跳数信息用于位置估计(单跳节点之间不需要测距)。 其中要求①有助于提高定位精度；要求②缓解了对通信范围的需求；要求③使得昂贵的测量距离的设备可以省略，这样大大节省了定位成本。

支持向量机定位(Localization Support Vector Machine，LSVM)[6]是一种非测距的技术，它与多日冕分割技术(Multi-Corona Division，MCD)具有相同的要求(①-③)，LSVM 方法是基于向量机的分类结果去估计非锚节点的位置，但是实现SVM 需要一个具有较高计算能力的中心节点(如汇聚节点或基站)。 另外，DV-Hop[7-8]也是一种常用的非测距定位技术，利用跳数信息估计锚节点与非锚节点之间的距离，其定位精度由一跳表示的平均距离的精度决定。 文献[9]提出了同心圆锚节点定位算法(Concentric Anchor Beacon Localization Algorithm，CAB)，使用与本文日冕划分类似的圆划分，该方法依靠多级发射功率形成的可变通信范围，将非锚节点，即定位目标锁定在一定的圆周内。 这种方法不符合非测距定位要求②的要求，并且随着通信距离的增加，额外的噪声会加剧对定位的影响:不规则度(Degree of Irregularity，DOI)[10]，如图1 所示。 相反，MCD 中的上述影响并不是由跳数决定的圈选择引起的，而是由通信范围决定的。

图1 DOI＝0.05，r＝5 情况下CAB 定位情况

本文提出了一个方法:基于MCD 的定位技术。MCD 的协议比较简单，就像一个泛洪协议:所有非锚节点同时监视信道，并传输消息，再加上快速分割算法，这样很大程度上降低了计算成本。

1 多日冕分割技术

1.1 日冕的定义

假设在一个平面区域[0，X]×[0，Y]内部署了很多传感器节点，其中节点分为两类:(1)锚节点，即知道自己所处位置的节点；(2)非锚节点，即不知道自身位置的节点，也就是算法需要实现定位的目标节点。 所有节点可以互相通信，它们的通信半径为r(r＞0，r≪X，Y)。 凡是节点间距离d满足d＜r，即可认为节点间可以直接进行通信。 锚节点可以通过改变通信功率来改变自身的通信半径，从而形成如图2(a)所示的以锚节点为圆心的一个同心圆组。此时，传感器网络中的非锚节点根据自身所在的位置不同处在锚节点形成的不同通信半径的圆环中，当锚节点由近及远改变通信半径时，各个非锚节点收到消息的时间是不同的，距离锚节点比较近的非锚节点会最先收到消息，而比较远的非锚节点会较迟收到消息甚至收不到消息。 通过改变锚节点的通信半径和比较非锚节点收到消息时间的长短就可以确定非锚节点正处在同心圆的哪一个圆环中，然后通过多个锚节点的叠加，即可较为精确地得到非锚节点的位置信息。 然而，此方法忽略了较远距离通信产生的巨大能耗和锚节点本身改变通信半径所需的设备成本，所以上述方法有缺陷。 因此，本文提出了图2(b)所示的最短跳数形成的日冕，它既能根据跳数形成类似于CAB 方法形成的同心圆组，又可以降低能耗且不需要其他的能改变通信半径的设备。

图2 区域分割方式

日冕的定义:在传感器网络的某一覆盖区域内，在一个锚节点周围会形成一个k层日冕覆盖的通信区域，其中每一层日冕都表示为Ni(i=1，2，3…k)。定义每一层日冕的半径为0＜R1＜R2＜R3＜…＜Rk(Ri=ri)。 例如，如果某一节点A与锚节点S的最短路径为c跳(即与锚节点之间有c-1 个中间节点)，那么就定义A节点位于S日冕的第c层，那么其所处区域即为[(c-1)r，cr]的环形区域内。

为了方便计算，我们假设该模型在环境中的噪声可以先忽略，即该系统所得到的非锚节点到锚节点的跳数总是正确的。 然而纵使目标节点的跳数正确，也有可能发生错误。 由于通信半径的限制和节点分布的随机性，前一层日冕的节点很难通过一跳就完全覆盖后一层日冕，例如图3 中的‘+’节点，‘+’实际上是处于第2 层日冕，但是由于上述的种种限制，导致第一层日冕中的节点(即‘⊙’节点，也可称为一跳节点)无法在一跳范围内联系到‘+’节点。 那么‘+’节点就需要至少三跳才可以从锚节点(即‘*’节点)到达该节点，这时‘+’节点就会被误认为处于日冕的第3 层或者第4 层甚至更高。 其中‘○’表示第2 层日冕中的节点(也可以称为两跳节点)。

图3 锚节点的日冕覆盖

1.2 日冕的融合

上文提出算法可能出现的错误可以归结为:某一节点A实际上在日冕的Ni层中，但是由于通信半径的限制和节点分布的随机性，A节点与锚节点S的最短跳数是(Ni+j)跳(其中j必定大于0)，那么系统判定A节点在第(Ni+j)层日冕中。

现在提出一种日冕融合的思想:由于算法的错误只会是偏大估计目标节点的日冕层数，那么就扩大该节点所处的的日冕范围。 也就是说原本算法估计目标节点A处于第(Ni+j)层(也就是位于距离锚节点[(Ni+j-1)r，(Ni+j)r]的一个圆环范围内)，此时扩大目标节点的日冕层范围，即外层日冕融合内层日冕，使该层日冕范围扩大。 例如向内融合k层，即该目标节点处于距离锚节点的[(Ni+j-1-k)r，(Ni+j)r]的一个较大圆环范围内。 此时的k可以被认为是一个参量，我将它定义为融合层数(Fuse Index，FI)，若FI＞j，那么就认为节点就处于第(Ni+j)层日冕中，并且不需要融合内层日冕。 融合日冕层的好处是显而易见的，但是这么做的弊端就是定位收敛速度会变慢，但是考虑到锚节点个数不少，通过多个锚节点的配合，最终的收敛速度是可以接受的，所以这种融合思想是可行的。

接下来讨论FI(N)的取值。 其中N代表估计层数。 FI 的值如果偏小，那么目标节点可能还是落不到正确的定位范围，而FI 的值如果偏大就会使定位不够精准，使得后续计算量增大甚至会影响最后的定位准确性和精度。 使:

式中:PN-j(X=N)表示估计层数为N的目标节点实际处于N-j层的概率，且A为常数0.9。 这样保证了目标节点能大概率落在合适的融合日冕层中。

1.3 算法和协议

当每一个非锚节点到某一个锚节点的最短跳数被确定下来以后，那么这个非锚节点所处的以某一个锚节点为中心形成的日冕中的层数也就确定下来了。 如果计算许多个不同位置的锚节点所形成的日冕层对某一个目标节点的位置交集就可以得到一个相对精确的位置。 由一个锚节点所形成的日冕可把节点定位到一个圆环中，如图4(a)所示，而两个锚节点所形成的两个日冕可以把节点定位到一个曲边四边形中，如图4(b)所示。

图4 日冕分割定位

基于1.2 节的分析，由最短跳数形成的日冕可能是错误的，我们需要进行日冕融合。 详细的定位过程如下:

1.3.1 初始化阶段

①锚节点广播:所有锚节点在初始化时向周围发送一条包含锚节点位置、锚节点编号、通信跳数信息的消息。

②非锚节点在锚节点广播阶段持续监听，在接收到一条消息后与自身已接受的消息进行比较(即比较消息中锚节点的编号和跳数):若该锚节点消息在之前已经接受过并且记录的通信跳数少于当前消息，则丢弃；若该锚节点消息在之前已经接受过但是记录的通信跳数多于当前消息，则更新原来消息的跳数；若该锚节点消息之前未接受过，则存储当前消息。

1.3.2 粗略估计位置

初始化后，通过每个节点到锚节点的最短跳数可以直接得出最初的日冕层数为Ni，之后再通过算法计算得到融合日冕层，得到目标节点的最终定位范围[[Ni-1-FI(N)]r，Nir]。

1.4 求解精确范围

获得目标节点的精确定位范围仅仅只依靠一个锚节点是远远不够的，它是通过许多个不同位置的锚节点共同作用得到的交集区域来确定目标节点的精确位置。

式中:(x1，y1)，(x2，y2)…，(xn，yn)是n个锚节点的坐标位置。 上述不等式看似简单，但是考虑到无线传感器网络是一个较为庞大的系统，其中锚节点的个数可能较多且每一次日冕的划分无法确保是完全正确的，我们只保证了正确的概率至少大于0.9，这会使得计算量陡增且上述不等式组很有可能出现无解的情况，所以我们提出一种边界追踪的算法用来方便快速地确定交集区域。 我们先取距离目标节点最近的三个锚节点a，b，c(跳数越少越近)，并建立以下不等式组。

算法 边界追踪

由于锚节点与非锚节点之间的距离较近，所以日冕层的出错概率较小，所以认为上述不等式组(3)是可解的。 由此不等式组可以解得X∈[U1，U2]，Y∈[V1，V2]。 显然这是一个矩形区域，如图5所示。 其中的小黑点就表示目标节点可能存在的位置。 之后只需要判断这些可能存在的位置是否存在于其他锚节点的日冕层中即可，若不在则去掉此黑点，若在则保留，如此筛选过后目标节点的位置也就被精确定位了。

图5 最近三个锚节点的交集产生的离散区域

很显然，更加多的离散点会提高最终定位结果的精度，然而每多一次判断就需要多4 次加法和4次乘法运算，计算量会随着精度的提高而增加。 通过观察可得，我们的重点是得到一个日冕的交集区域，那么只需要关注到日冕的边界，也就是只要追踪到分割边界的离散点就可以得到最终的交集区域。假设矩形区域X∈[U1，U2]，Y∈[V1，V2]内以k为单位分割出离散点，那么总共离散点的个数就是[(U2-U1)/k×(V2-V1)/k)]个。 以图5 中锚节点2的第7 层日冕的下边界为例:确定日冕层界线的穿入点和穿出点:A和B。

最后，InterRegedg 记录了所有边缘位置的点。检查矩形区域的四个边缘需要[2(U2-U1)/k+2×(V2-V1)/k]×4 个加法和乘法，而矩形中的离散点位，只需检查该点是否在日冕层边缘，因此只需要4×num个加法和乘法。 由于m远低于所有离散点的个数，边缘追踪的总成本远小于直接计算所有点。 当k翻倍时，它只会影响m(m的取值将在1.5 小节讨论)。在最坏的情况下，剩下的所有锚节点(n-3 个)的所有日冕都不会分割矩形区域，因此需要(n-3)×[2(U2-U1)/k+2×(V2-V1)/k]×4 加法和乘法。 然而，这种情况很少发生。 其他区域的边缘包括弧线，随着日冕数量的增加，所有边缘都是弧线而不是直线。 然而，边缘追踪只是关心边缘点，与边缘是弧线还是直线无关，所以它在其余区域仍然可用。

1.5 确定m 的值

通过先前的分析可知穿越交集区域的上下日冕边界是一段圆弧因此考虑m的取值实际上等价于求解这样一问题:当x(或者y)随着k变化时，y(或者x)的变化率。 且x，y满足:

应用极坐标变换[θ=arctan(x/y)]:

y的变化率与k的取值有关。 为了将x的变化离散点取到，m必须大于dx。k一般取小于1 的值，而θ一半的概率小于1，且tanθ很小概率取到无穷，所以m的值一般取1 比较合适。

2 仿真实验

我们首先构建了一个模拟场景:1 000 个传感器节点随机统一地部署在100 m×100 m 平面中，并将MCD 的定位精度与LSVM 和DV-Hop 两种算法在五个可变锚节点密度下进行比较:1%、1.5%、3%、5%、10%。 第1.4 节分析了计算成本，它与锚节点的数量n有关，另一方面，通信成本主要是来自节点之间的传输消息，因此也与n相关。 在本节中，我们更关注定位的准确性。 我们通过文献[6]的研究证明，将通信范围r=10 m。 另外，当k=1 m 时，定位误差最小，计算成本适中。 另外，我们还测试了传感器分布出现空洞情况下MCD 方法的准确性。

2.1 不同算法仿真结果比较

LSVM 方法是通过一些样例数据在内核空间中寻找一个超平面，使得这个超平面能够根据样本的某些特征矢量进行较为准确的分类，从而构建出一个类似于MCD 方法形成的不同类别的节点群以便完成定位。 但是，LSVM 分类模型的构建与训练数据息息相关，一旦训练数据改变，LSVM 模型就需要重新训练构建。 这种方法灵活度不高且适应性不强，不太适用于分布广泛的WSN 节点。

DV-Hop 方法则是使用整个网络中通信节点间1 跳的平均距离用于估算锚节点和非锚节点之间的距离，进而一步步计算目标节点的位置。 DV-Hop方法的准确性取决于1 跳平均距离与实际节点位置间距离的相近性。 为了达到较高的定位准确性，DV-Hop 方法需要比MCD 更多的锚节点。

图6 充分表明了MCD 方法比其他两种方法更有优势。 尤其在低锚节点密度下，MCD 方法更加准确。 例如，当锚节点密度为1%时，MCD 的平均定位误差接近3.9 m，而LSVM 和DV-Hop 的定位误差都超过8.5 m。 在所有参与实验的锚节点密度中，MCD 的性能表现比后两者都好。 MCD 的性能比LSVM 和DV-Hop 提高了51%和56%。 而在实际使用中，低锚节点才是经常出现的状况，这会使得LSVM 方法缺少训练样本，而DV-Hop 方法则更有可能错估1 跳的平均距离导致节点定位误差偏大。

图6 不同锚节点密度下的MCD、LSVM 和DV-Hop(r＝10 m)方法定位误差的统计

由于MCD 通过跳数确定日冕层数，通信传播产生的累积误差会使性能下降，所以我们分别将网络扩展到200 m×200 m，有4 000 个传感器节点和300 m×300 m，有9000 个传感器节点进行大规模网络实验。 表1 显示了MCD 方法的大规模网络定位性能，网络规模的扩大不仅没有使性能下降反而提高了定位的准确性。 分析可得，尽管非锚节点与锚节点之间的实际路径物理长度更长，导致累积误差更多，但MCD 的融合机制相应地考虑了这个误差，并增强了一层日冕的覆盖范围，交叉区域的面积可能会增大，但更多的锚节点不仅抵消了这种可选范围的增大，甚至还能减小可选区域的面积使得位置计算更加精准。

表1 大规模网络下MCD 方法的性能表现

2.2 空洞问题

实际环境中部署传感器节点不可能会随机分布，总会有地方无法部署节点，导致传感器网络会在某一块空缺，我们称之为传感器网络空洞，简称空洞。 由于空洞的存在，原本传感器节点之间物理路径可能很短，但是中间缺少了部分节点，就会导致通信范围无法到达而绕了远路，致使跳数增加，路径变长。 为了模拟现实中可能存在的问题，我们在四种不同形状、尺寸、位置和数量的空洞场景下测试MCD 方法(括号中的数字表示形状中心的位置坐标):①一个边长为25 m，(50 m，50 m)的正方形孔；②两个半径为12.5 m，(25 m，25 m)和(75 m，75 m)的圆形孔；③三个半径为10 m，(30 m，30 m)、(30 m，70 m)和(70 m，50 m)的圆形孔；④四个15 m 边长的正方形孔分布在四角。

图7 显示，在四种空洞场景锚节点密度为5%的情况下，与LSVM 和DV-Hop 相比，MCD 在所有空洞场景的表现都最好。 随着空洞个数的增加，从锚节点到非锚节点的路径延长直接影响了节点间1 跳平均距离的估计，所以DV-Hop 的定位精度很显然受到了影响。 虽然LSVM 不依赖单跳平均距离，但在低锚节点密度下，其定位精度依然不高。 对于MCD来说，空洞对于初始日冕层的获得是有影响的，但由于采用日冕层融合思想，这使得以不多的锚节点就可以缩小这个交叉区域，直到达到较高的定位准确性。

图7 空洞场景下MCD、LSVM 和DV-Hop 方法的比较

2.3 噪声环境下MCD 与CAB 方法的比较

CAB 与MCD 有着相似的思路，它不是严格意义上的非测距定位技术，因为它是通过不同功率的信号发射来勾画出同心环从而让非锚节点感知自身与锚节点之间的距离。 与之相比，MCD 也是划分出相似的日冕层，只是MCD 是通过跳数划分并不改变节点的信号传输功率。 文献[7]考虑了噪声对定位方法的影响，这是具有实际意义的。 所以我们使用DOI 来模拟噪音的影响，并在此情况下继续测试MCD 方法，同时与CAB 方法进行比较。 图1 所示的DOI=0.05，在可变锚节点密度下，传感器节点总数为500。 在CAB 方法中，锚节点有三级发射功率。使用默认的r=10 m，我们应用MCD 方法来定位非锚节点。 表2 显示，在所有实验的锚节点密度中，MCD 方法的定位性能都优于CAB 方法。 这是因为MCD 只使用跳数确定划分的日冕层数，但是CAB的同心圆划分就需要通过发射功率改变形成，这样三个环路的通信信号受到噪声影响的程度也就不同。 不过，CAB 的非锚节点只需要接收信息，而MCD 中的所有节点都需要发送信息，所以MCD 方法中节点的通信成本要高于CAB 方法。

表2 MCD 与CAB 方法在噪声环境下的比较

3 总结

我们提出了MCD——一种基于日冕分割的无线传感器定位技术。 仿真结果表明，MCD 的表现优于LSVM，DV-Hop，后者同样使用跳计数器进行定位，并共享相同的需求模型。 在噪声情况下，MCD也被证明比CAB 更好，CAB 使用类似的通信圆环分割技术。 另一方面，从边缘追踪到计算交集区域，这个两个计算过程可能不会同时发生。 因此，在未来的工作中，我们考虑给协议一个异步特征，这样位置信息就不需要同步传输，而可以与日常数据一起被异步传输至控制中心。