基于蜂窝网络拓扑的无线传感网定位算法

任秀丽，刘 莹

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引 言

无线传感器网络(wireless sensor network，WSN)的节点定位技术是其关键支撑技术之一[1-5]。目前，节点定位算法主要分为两类：基于测距[6-10]和基于非测距[11-16]。

在基于非测距的定位算法中，运用最广泛的是DV-HOP算法，但其定位精度低，对此很多学者都提出过改进方案。文献[17]提出基于DV-Hop 测距修正的对数搜索(improved DV-Hop ranging-based logarithmic search，DH-RLS)定位算法，其估计跳距误差后修正跳距值，过于依赖信标节点，计算量大且耗能多。文献[18]提出改进的DV-Hop定位算法(improved DV-Hop localization algorithm，IDVH-LA)，对一跳距离加权校准，依据跳距作用域计算距离。虽硬件开销小，但能耗较高且计算误差较大。文献[19]提出全局跳数优化与跳距误差修正的DV-Hop 改进算法(improved DV-Hop algorithm based on global hop count optimization and hop distance error correction，IDVH-HCHEC)，对跳数值协同优化并修正平均跳距以提升精度，但仍不能改善DV-Hop算法因为网络环路导致的较大误差。

针对上述算法的不足，本文提出了基于蜂窝网络拓扑的定位算法(location algorithm based on cellular network topology，LABCNT)。该算法仅需两个信标节点即可定位监测区域内所有节点的位置，解决了其它算法在信标节点极少、未知节点过多的情况下定位效率低，甚至无法定位的问题。首先筛选网络中全部节点，设计并构造一个蜂巢网络结构模型，通过模型确定结构上节点的位置，最后利用最小二乘法对域内其它节点进行定位。实验结果表明，该算法定位精度高，计算量小且对信标节点数依赖性极小。

1 网络模型

本文针对无线传感网中信标节点密度低、未知节点密度高的环境下进行定位研究。网络模型如下假设：①全部节点都具有相同的通信范围，选取合适的通信半径r作为全部节点的固定通信半径；②每一个节点都有其唯一ID，以便将其记录到结构链表当中；③节点间可以通过测距技术获取距离信息，网络测距技术采用接收信号强度指示(RSSI)；④本文所用的RSSI信号传播模型为对数常态分布模型，如式(1)所示

(1)

其中：RSSI(d)是未知节点的接收功率；RSSI(d0)是参考距离d0点对应的接收功率；d是未知节点到锚节点之间的距离；d0是参考距离；α为与环境有关的路径损耗指数，一般取默认值；为表示标准差为σ的正态随机变量。

2 LABCNT算法

LABCNT算法适用于信标节点数量极少，且存在大量未知节点的环境。在不改变原DV-Hop算法理论的基础上，引入RSSI技术，对算法执行过程进行了3个方面的改进：一是在定位开始阶段对跳距进行规范，减少在定位后期的误差积累；二是在定位过程中有向筛选出一些特征节点继而搭建构成一个相对有序的网络拓扑结构，避免原DV-Hop算法因为环路和曲路导致的较大误差；三是利用网络拓扑结构对域内所有节点进行最小二乘算法定位，减小原始算法中因迭代而产生的累积误差。

LABCNT算法主要思想分为两个阶段：一是蜂巢搭建阶段，二是马蜂回巢阶段。在蜂巢搭建阶段，对网络中全部节点进行筛选，筛选完毕后，使用所有满足特定要求的节点构造出一个结构模型，且在该模型中所有节点位置均为相对位置。模型搭建完成后，进入第二阶段，即马蜂回巢阶段。在马蜂回巢阶段要修正该模型中全部节点的相对位置，并通过蜂巢搭建阶段所构筑的网络结构将整个侦测区域划分为若干个大小相等的三角形区域，最终通过计算获取全部未知节点的准确位置。

2.1 蜂巢搭建

蜂巢搭建阶段分为4个步骤：选点、编号、划域和定点。首先对网络中全部节点进行筛选，对选中的节点构造蜂巢网络拓扑模型，并将其按照规定的方法进行编号。最后，对拓扑网络中全部节点进行分区域处理，并对各区域内节点位置进行相对定位。

2.1.1 选点

定义1 节点的度。节点i的度是它的邻居节点的个数，即与它相邻的节点个数。

选点，即选取构筑蜂窝网络的特征节点。选点前，汇聚节点(Sink节点)判断网络中各信标节点的度，选取节点度最大的信标节点作为起始节点，确保起始节点找到满足要求的节点。特征节点的选取方法如下：以起始节点(信标节点)为中心，在半径为r的圆形通信范围内，选择最接近圆内接正六边形的6个节点，即任意两个相邻节点间距离尽可能接近固定通信半径r。随后再分别以这6个被选中的节点为中心，用同种方式再次对这些节点进行特征节点的选取，以此方法进行类推拓扑，构筑蜂巢拓扑结构。若在构造拓扑结构的过程中，出现特殊情况，即找不到足够多满足条件的节点，则把缺少节点的六边形顶点设为虚拟节点，不影响其它节点拓扑。

图1为监测区域内节点构筑蜂巢网络结构的示意图，其中图1(a)为监测区域内节点的分布。在监测区域内选择某一信标节点按选点步骤进行拓扑，得到一个由正六边形拼接的内外多层的蜂巢网络结构，如图1(b)所示。

图1 构筑蜂巢网络结构

2.1.2 编号

定义2 孤点。在各层正六边形网络结构中，各边两个端点位置的节点称为孤点，起始信标节点也作为孤点，如图2(a)所示。

定义3 交点。在各层正六边形网络结构中，除孤点外的节点称为交点。

定义4 子节点。由节点拓扑出的外层节点为其子节点。

定义5 顺序位孤点。只被孤点拓扑出的子层孤点为其顺序位孤点。

将经过选点过程得到的蜂窝网络结构图抽象出一个蜂窝层次结构图，如图2(b)所示。各层节点的个数为其层号的6倍。LABCNT采用层序坐标表示法对拓扑网络结构中的全部节点位置进行描述，即通过节点在蜂巢网络结构中所属的层号与层内序号表示该节点的位置。

图2 蜂巢层次结构

层序坐标表示法如下：

(1)层号编号规则：从起始信标节点开始，由内向外依次编号为0，1，2，3，4…n；

(2)层内序号编号规则：以第一层任意孤点为起点，逆时针依次编号为0，1，2，3，4，5。其后的每一层均以第一层0号孤点在该层的顺序位孤点为该层的编号起点，逆时针方向对节点进行编号。层内序号示意图，如图3所示。

图3 层内序号

根据层序坐标表示法，网络中任意节点表示为：Li(n,x)。 其中，i是节点的ID号，n是该节点i在拓扑结构中的层号；x是节点i在此层的序号。

节点编号示意图，如图4所示。以第一层到第三层的拓扑结构为例，Li(1,0) 单独发现的节点为Li(2,0)；Li(2,0) 单独发现的节点为Li(3,0)； 即每层0号节点单独发现下层0号节点。Li(1,1) 单独发现的节点为Li(2,2)；Li(2,2) 单独发现的节点为Li(3,3)；Li(1,2) 单独发现Li(2,4)；Li(2,4) 单独发现Li(3,6)； 即每层孤点单独发现的节点下层顺序位孤点。Li(1,0) 与Li(1,1) 共同发现的节点为Li(2,1)；Li(2,0) 和Li(2,1) 共同发现的节点为Li(3,1)， 即0号位和1号位同时发现的节点为下一层1号节点。Li(2,1) 与Li(2,2) 同时发现Li(3,2)， 即除第一层外，各层1号位和2号位同时发现的节点为下一层2号节点。此外，Li(1,0) 共发现3个节点，分别为Li(2,11)，Li(2,0)，Li(2,1)；Li(2,0) 共发现3个节点，分别为Li(3,17)，Li(3,0)，Li(3,1)； 即孤点发现其子层的顺序位孤点与子层两个交点。Li(2,11) 共发现两个节点，分别为Li(3,16) 与Li(3,17)；Li(2,1) 共发现两个节点，分别为Li(3,1) 与Li(3,2)； 即交点发现其两个子层交点。

图4 节点编号

2.1.3 划域

将节点编号后的网络进行划域，如图5所示。网络划分为6个区域，分别标记为A1、A2、A3、A4、A5、A6。对网络中的节点，确定其所属区域。将起始信标节点作为极点；从起始信标节点出发，向外依次连接各层0号位孤点后形成的射线作为初始假定极轴，以逆时针为正方向，则第一层各孤点及其顺序位孤点形成的射线方向分别为：0，π/3，2π/3，π，4π/3，5π/3。网络划分的6个区域分别为：A1[0,π/3)，A2[π/3,2π/3)，A3[2π/3,π)，A4[π,4π/3)，A5[4π/3,5π/3)，A6[5π/3,2π)。

图5 网络区域划分

2.1.4 定点

在该阶段，利用节点的编号以及所属区域，计算出它在地图上的相对坐标，相对坐标采用极坐标表示法，即Pi(ρ,θ)。 其中，i表示节点ID号，ρ为极径，即节点距起始信标节点的距离；θ为相对角度，即极径与其初始假定极轴之间的夹角(极角)。

图6所示为节点定点后的示意图，图中节点可分为两类：处于各区域边界射线上的点与处于各区域内的点。孤点处于各区域边界射线上；交点处于各划分区域内。

图6 节点定点

对于不同类别的节点，位置的计算各有不同。任意节点的类别通过层内序号x是否是层n的整数倍判断，若层内序号x是层n的整数倍，则节点i为孤点；否则节点i为交点。

不同类型的节点到起始信标节点的距离(极径)ρ，极径与其初始假定极轴之间的夹角θ(相对角度)的计算方法如下：

(1)孤点

ρ=n×r

(2)

(3)

其中，n为节点所在层数；r为蜂巢节点的固定通讯半径。

(2)交点

对于交点位置的计算，首先判断该节点所属的区域，然后推算其所属区域内起始孤点序号，最后在区域内根据勾股定理，计算它与起始信标节点的空间距离ρ以及极径与初始假定极轴的夹角θ(相对角度)

(4)

(5)

(6)

其中，n为节点所在层数；r为蜂巢节点的固定通讯半径；x为节点的层内序号；m表示该点所属区域的起始孤点序号。

2.2 马蜂回巢

蜂窝拓扑结构搭建完成后，运用假定的极坐标系计算出各个未知节点的相对位置。但由于是相对坐标，在实际定位中节点的具体位置并不能确定，因此，通过蜂巢网络结构中第二个信标节点，即马蜂节点来确定网络中所有节点的绝对坐标。

马蜂回巢阶段分为坐标校准与全局定位两个部分，坐标校准是根据蜂巢网络结构中的马蜂节点进行坐标更正；全局定位是将已经确定位置的节点升级为协作节点，辅助其它未确定位置的节点定位。

2.2.1 坐标校准

坐标校准是确定真实的极轴，并调整拓扑结构上各节点的角度的过程，即将整个拓扑网络所在的极坐标系进行调整。将原零度线方向(初始假定极轴)替换为两信标节点的连线方向，即将两信标节点的连线方向作为新极轴。此时，各个节点的距离并未发生变化，但是各个节点的角度要做出相应的调整。坐标校准后的马蜂节点与起始信标节点将拓扑网络中全部节点定格在地图上，如图7所示。初始假定极轴方向为0°方向，A点为马蜂节点。现将A点所在角度设为0°方向，则原坐标中B点位置调整到B′点，即B点相对角度θ，调整为现坐标轴B′点的相对角度φ。节点坐标校准的计算方法如下所示：

图7 校准节点

设马蜂节点的相对角度为θt，节点修正后的角度为φ，则节点的修正坐标为Pi(ρ,φ)

(7)

2.2.2 全局定位

通过执行上述蜂巢搭建以及坐标校准步骤后，对各层上六边形节点已完成定位。对于其它未在拓扑结构上的节点采用区域化处理，即将需要被侦测区域的各正六边形分割为若干个等边三角形，如图6所示。将蜂窝拓扑网络结构中已经确定位置的节点升级为协作节点，根据最小二乘法对各区域内的未知节进行定位。至此，监测区域内所有节点的位置均可以确定。

2.3 LABCNT算法的实现步骤

LABCNT算法分为两个阶段：一是蜂巢搭建阶段，二是马蜂回巢阶段。算法的具体实现过程如下：

步骤1 初始化网络。Sink节点广播初始化消息，监测区域内的传感器节点确定自身位置信息及自身的度，未知节点将自身位置信息设为NULL。各节点向Sink节点发送位置信息以及自身的度。

步骤2 选点拓扑。Sink节点接收到各节点的消息后，选取度最大的信标节点作为起始信标节点，起始信标节点根据2.1.1节选点要求进行网络拓扑选点。

步骤3 编号划域。拓扑结构建立后，对拓扑结构中的节点采用层序坐标法编号并划分节点所属区域。

步骤4 计算相对位置。根据节点的类别对拓扑网络中的节点计算其相对位置。

步骤5 计算绝对位置。通过2.2节马蜂回巢，运用拓扑网络中第二个信标节点，将拓扑网络中的节点完全定格在地图上。利用坐标校准修正相对坐标，得出绝对坐标。

步骤6 全局定位。将蜂窝拓扑网络中已经确定位置的节点升级为协作节点，区域化处理后，确定各区域内其它未知节点坐标。

3 性能评估与分析

为了评估本文提出的LABCNT算法的性能，使用NS-2仿真环境，对本文的LABCNT算法同DH-RLS算法、IDVH-LA算法、IDVH-HCHEC算法进行比较。将节点随机部署在100m×100m的监测区域内，假设所有节点都具有相同的通信半径，节点通过自组织形成一个无线传感器网络。仿真参数见表1。

表1 仿真参数

本文从三方面来验证各算法的性能。节点定位误差error如式(8)所示

(8)

其中，n为节点总数；m为信标节点的个数； (x′i,y′i) 为未知节点定位后的估计坐标； (xi,yi) 为未知节点的实际坐标位置。

从图8可知，随着信标节点数量的逐渐增加，节点的定位误差逐渐降低；LABCNT算法的定位精度明显高于其它3种算法。LABCNT算法使用两个信标节点定位，对信标节点的数量依赖性较小，在信标节点数量较少时定位精度较高，且在定位开始阶段规范跳距，减少在定位后期的误差积累。DH-RLS算法过于依赖信标节点数量，信标节点数量少时，误差过大。IDVH-LA和IDVH-HCHEC算法注重对信标节点平均跳距的修正，依赖信标节点的分布的均匀程度，信标节点比例过小时，网络区域信标节点可能分布不够均匀，误差较大。

图8 信标节点数量与定位误差之间的关系

如图9可知，监测区域内4种算法的定位精度随着节点总数的增加而提升，最终定位精度均趋于稳定，LABCNT算法的定位精度明显高于其它3种算法。LABCNT算法筛选出的特征节点构建而成的蜂窝拓扑结构，限制了拓扑结构上两个传感器节点之间的距离，减少了由于实际跳距不均等而引起的累计定位误差，也避免DV-Hop算法因为环路和曲路导致的较大误差。DH-RLS算法采用搜索定位算法进行后期处理，节点总数增加而收敛程度较弱，定位误差较高。IDVH-LA算法对信标节点的平均跳距进行修正，但节点增多导致跳数增加，产生了大量的累计误差。IDVH-HCHEC算法虽然改进了跳距和跳数，但由节点增多导至产生的环路结构不可避免，因此误差率较高。

图9 网络节点总数与定位误差之间的关系

如图10可知，4种算法的定位精度随通信半径的增大而提升。此次实验参数设置为节点总数130个，信标节点密度取8%。节点半径增大，各节点的邻居节点数增多，提升了网络的连通性，因此各算法定位精度提升。LABCNT算法对信标节点的依赖性较小，首先确定了蜂窝拓扑网络中的未知节点位置，然后利用RSSI技术与拓扑结构对域内全部节点进行区域化的最小二乘法定位，避免了DV-Hop算法中因迭代而产生的冗余误差。DH-RLS算法依赖信标节点，随着半径增大，质心定位算法的定位误差增大；IDVH-LA算法虽然优化了平均跳距及其作用域，但忽略了计算所产生的累计误差，节点通信半径增加，累积误差随之增加；IDVH-HCHEC算法大量使用未知节点的信息，节点间半径增大，更多未知位置的节点参与定位，使得算法误差率有所上升。

图10 节点通信半径与定位误差之间的关系

4 结束语

本文针对传统定位算法存在的过于依赖信标节点个数且定位精度低的缺陷，提出了基于蜂窝网络拓扑的无线传感网定位算法(LABCNT)。该算法通过对网络中节点的有向筛选，利用选中的节点构造蜂巢网络拓扑结构，得到节点的相对位置；利用拓扑结构中的第二个信标节点确定网络中节点的绝对位置，并将节点升级为协作节点；利用协作节点采用最小二乘法对各域内所有节点进行定位。仿真结果表明，本文提出的LABCNT算法与DH-RLS算法、IDVH-LA算法、IDVH-HCHEC算法相比，使用较少的信标节点即可达到较高的定位精度，定位过程中的能量消耗较小，延长了整个网络的生存周期。