WSNs中基于锚节点优先级节点定位算法

黄 珍, 潘 颖 , 苑 毅

(兰州文理学院 a. 数字媒体学院; b. 传媒工程学院, 兰州 730000)

0 引 言

由大量微型能量受限的具有数据感知能力的传感节点组成的无线传感网络 (WSNs: Wireless Sensor Networks)[1-2]已在医疗、 环境监测和军事等领域得到广泛应用。WSNs中节点先感知环境, 再获取环境数据, 然后将数据传输至汇聚节点, 进而实现对环境的监测。节点的位置信息对数据所产生的价值有重要影响。若没有准确的位置信息, 数据就没有应用价值。因此, 定位成为WSNs的一项关键技术[3-4]。

由于节点常处于恶劣环境中, 且节点本身属微型设备, 因此其能量以及数据处理能力有限。这些特性对节点定位提出了挑战。研究人员针对定位问题, 提出许多不同的定位算法。这些算法可分为测距定位、 非测距定位以及混合定位算法。

虽然测距定位算法的定位精度较高, 但其定位复杂度高, 并不适宜低功耗的WSNs网络。因此, 非测距定位算法在WSNs中广泛应用, 该非测距定位算法主要分为两类：启发式和分析式定位算法[5-6]。DV-Hop(Distance Vector-Hop)就是典型的启发式算法, 其通过未知节点与锚节点间的跳数估计它们间的距离。而分析式算法是利用理论分析推导锚节点与未知节点间的距离[6-7]。

基于节点连通定位算法就属典型的非测距定位算法。该算法利用锚节点间的连通信息估计未知节点的位置[7]。基于跳数和质心定位算法常用于该定位算法中, 如DV-Hop[8]、 PMDV-Hop(Path Match DV-Hop)[9]。这些算法假定两节点间距离与它们间跳数成正比。

在实际环境中, 特别是异构环境, 这些算法的定位精度并不高。障碍物以及跳数估计误差导致测距误差较大。王改云等[10]采用质心定位算法, 通过未知节点周围的锚节点构建三角形或六边形, 并将这些形状的质心位置作为未知节点的估计位置。刘雨等[11]提出加权的质心定位算法, 其将跳数作为权重, 并且离未知节点越近的节点的权重越大。但这些算法并没有考虑到锚节点的差异性。由于不同的锚节点分布在不同的网络区域, 它们可能对测距精度的影响也不尽相同。

为此, 笔者提出基于锚节点优先级的质心定位算法(PACL： Priority-Anchor node-based Centroid Localization)。利用不规则程度构建信号传输模型, 使信号传输模型更符合实际应用场景； 考虑到锚节点的差异性, 该算法利用锚节点的平均跳距值设置锚节点的优先级; 并通过仿真分析了PACL算法的性能。

1 网络模型

考虑到障碍物以及干扰等因素。假定节点的通信区域为不规则区域, 如图1所示。现存的多数定位算法仍假定节点通信区域形状为圆形, 这与实际环境不符。

图1 网络模型 图2 节点通信区域

假设所有节点具有不同的传输功率。节点间通信受障碍物影响, 如树, 建筑物等。为此, 引用文献[12-13]的基于不规则程度(DOI： Degree of Irregularity)的无线信号传输模型。依据

RRSSi=P0-(1+λDOI)η

(1)

计算节点i所获取的信号功率。其中P0为发射功率；η为路径衰减因子；λDOI为不规则程度。图2给出λDOI=0和λDOI=0.02两种情况下的节点通信区域。

2 PACL定位算法

现存多数定位算法通常假设网络中节点间的跳距是均匀分布的。但在实际环境中, 跳距受多种因素影响, 如不规则形状、 障碍物等[14-15]。为减少这些因素的影响, 笔者提出PACL算法。

2.1 最小跳数

每个锚节点向其邻居节点广播通告包ACK_Packet, 其包含锚节点的位置以及该数据包被转发的跳数NHop。最初,NHop=0。该数据包ACK_Packet被转发一次, 跳数NHop就加1, 即NHop←NHop+1。

一旦收到ACK_Packet, 节点先判断是否之前收到过该数据包。若首次收到, 就从中提取锚节点信息, 并存储该锚节点的位置以及跳数信息。若不是首次收到, 就将最新收到的ACK_Packet中的跳数信息与存储的跳数信息进行比较, 并保存最小跳数值。然后, 节点将跳数NHop加1, 并更新ACK_Packet中值, 再向其邻居节点转发。重复上述步骤, 直到网络内所有节点获取其周围锚节点的信息。图3给出传输ACK_Packet的流程。

图3 处理锚节点的通告包的流程

2.2 锚节点间的平均跳距

由于锚节点位置信息是已知的, 先计算锚节点间的平均跳距。锚节点αi利用

(2)

2.3 锚节点的优先级

计算了平均跳距AAHDi信息后, 锚节点αi就向未知节点广播AAHDi信息。未知节点获取了其邻近的锚节点的AAHDi信息后, 就计算锚节点的优先级。具体过程如下。

第1步 先对AAHDi信息进行归一化处理

(3)

第2步 计算所有锚节点的平均跳距的均值

(4)

第3步 依据

(5)

计算每个锚节点的优先级。其中Rranki为锚节点αi的优先级； Round(·)为取整函数。

2.4 基于权重因子的质心定位算法

笔者考虑的是二维空间。因此, 未知节点至少获取离3个锚节点的距离信息, 才能利用质心算法估计自身的位置。未知节点从其邻近的锚节点中选择优先级前三的3个锚节点, 并利用离这3个锚节点的距离信息估计自身的位置。

假设未知节点si依据优先级选择了3个锚节点：α1、α2、α3。令r1、r2、r3分别为离未知节点si的距离。这3个锚节点以自身位置为圆心以离未知节点的距离为半径形成3个圆。令O1、O2、O3为这3个圆的交点, 如图4所示。

图4 质心定位算法

然后, 计算这3个交点的坐标。令(Xo1,Yo1)、(Xo2,Yo2)、(Xo3,Yo3)分别为3个交点坐标。再计算3个交点所形成的三角形的质心坐标, 如下所示

(6)

最终, 将(X1,Y1)作为未知节点si的位置估计值。

3 性能仿真

3.1 仿真环境

利用Matlab 2018a软件建立仿真平台, 700个节点随机分布于300 m×300 m区域, 其中锚节点数比例p%从10%～40%变化；λDoI从0～0.16变化； 节点的传输功率从-5～-15 dBm变化, 具体仿真参数如表1所示。

表1 仿真参数

为更好地分析PACL定位算法的性能, 选用同类算法DV-Hop[8]、 QWCRC(Quadrilateral Weighted Centroidthm Based on Ranging Correction)算法[11]进行比较, 并分析它们的平均定位误差

(7)

3.2 平均定位误差性能

首先, 分析未知节点数对平均定位误差性能的影响, 如图5所示, 其中节点数从200～800变化, 步长为100, 锚节点数占比p%=20%；λDoI=0.06。

从图5可知, 节点数的增加有利于降低平均定位误差。其原因在于节点数越多, 相应地锚节点数也随之增加。锚节点数越多, 未知节点获取的测距信息越多, 定位精度越高。此外, 相比于DV-Hop和QWCRC算法, PACL算法的降低了平均定位误差。

图5 节点数对平均定位误差性能的影响 图6 参数λDoI对平均定位误差的影响

下面分析参数λDoI对平均定位误差的影响。其中节点数为300, 锚节点数占比p%=20%, 结果如图6所示。由于DV-Hop和QWCRC算法是假设节点的通信半径为圆形, 即λDoI=0, 并没有考虑节点通信区域的不规则性。因此, 它们的平均定位误差不随λDoI变化。

相比于DV-Hop和QWCRC算法, PACL算法控制了平均定位误差, 即使在λDoI=0.15时, PACL算法的平均定位误差也小于DV-Hop和QWCRC算法的平均定位误差。

3.3 平均定位误差的CDF曲线

最后, 分析平均定位误差的累积分布函数(CDF： Cumulative Distribution Function)曲线。CDF值越接近1, 定位准度越高, 可定位的节点数越多, 如图7所示。其中节点数为300, 锚节点数占比p%=20%,λDoI=0.06。

图7 平均定位误差的CDF曲线

从图7可知, PACL算法中有接近99%的节点可以达到相同的定位精度。但QWCRC和DV-Hop算法只能分别达到61%和43%。其原因在于PACL算法考虑了节点通信区域的不规则性, 而QWCRC和DV-Hop算法未考虑, 它们在估计节点位置时, 只是简单地假设节点的通信区域为圆形区域, 没有考虑到信号衰减问题。

4 结 语

针对无线传感网络中传统定位算法未能充分考虑节点通信区域的不规则性问题, 笔者提出基于锚节点优先级的质心定位算法。PACL算法依据锚节点的平均跳距, 优先选择参与质心定位算法的锚节点。锚节点的优先级越高, 其平均跳距越短。利用这些锚节点的距离信息所估计的未知节点位置越高。仿真结果表明, 笔者提出的PACL算法降低了平均定位误差, 同时也具有抵御不规则通信区域的能力。