移动WSNs 中基于跳数矢量的节点定位算法

2021-06-26张焕生崔炳德

火力与指挥控制 2021年5期

张焕生，崔炳德，冯涛

（河北水利电力学院计算机科学与信息工程学院，河北沧州 061001）

0 引言

随着电子通信技术的发展，无线传感网络（Wireless Sensor Networks，WSNs）［1-2］已在多个应用中广泛使用。WSNs 是由多个微型、低功耗的传感节点组成，这些传感节点具有数据感知、数据处理和通信能力。传感节点先感知环境数据，再通过多跳通信，将数据传输至基站。

在所有的应用中，收集的所有数据都需依赖于传感节点的准确位置。若数据离开位置信息，该数据可能就无价值。因此，定位成为基于WSNs 应用的关键［3］。

事实上，定位就是估计传感节点的位置。为了估计节点位置，通常先在网络内部署一些已知位置的节点，这些节点也称为锚节点。通过测量锚节点与未知节点间信号参数，估计未知节点位置［4］。

依定位过程中是否需要测距信息，定位算法可分为测距和非测距定位。相比于测距定位，非测距定位简单，易实施。但非测距定位精度劣于测距定位算法。

现存的多数定位算法是针对静态节点，并没有考虑节点的移动性。事实上，节点的移动对节点位置的估计提出了挑战［5-6］。未知节点的移动使节点位置不断变化，提高了对节点位置估计的难度，增加了定位算法的复杂性。此外，WSNs 内的部分节点可能会发布虚假数据，这些虚假数据降低了定位算法的精度。

作为非测距定位算法，DV-Hop 定位避免了额外的硬件开销，得到较广泛应用［7］。DV-Hop 测距算法先估计锚节点与未知节点的跳数，然后再估计网络内的局部平均跳距，最终将跳距与跳数相乘，便可估计锚节点与未知节点的距离。然而，通过跳数估计节点间的欧式距离存在误差，并且跳数的估计值也存在误差。这些误差降低了DV-Hop定位精度。

为此，提出基于跳数矢量的节点定位算法（Hop Vector-based Node Localization Algorithm，HVLA）。HVLA 算法先通过跳数信息构建跳数矢量信息，再利用质心定位算法估计节点位置。同时，通过测量节点间的响应时间，丢弃一些虚假数据，进而提高定位精度。仿真结果表明，提出的HVLA 算法有效地提高了定位精度，并控制了算法的复杂性。

1 系统模型

每个未知节点知晓m 个锚节点的位置信息，并且向基站注册，获取自己的证书。此外，令Tr表示锚节点的传输距离，其随应用场景要求［8］变化。由于网络场景是动态变化，对Tr进行限定，即在最小传输距离和最大传输距离间变化：式中，Random（0，1）表示随机产生0 至1 的函数。

2 HVLA 定位算法

2.1 基于Friis 传播模型的测距

依据Friis 传播模型，利用式（2）计算节点的接收功率Pr：

式中，Pr表示锚节点的天线所接收的功率，Pt表示发射天线的发射功率，Gr和Gt分别表示发射天线增益和接收天线增益［9］，为波长，d 表示收发两端间的距离，其可通过接收功率估计发送节点与接收节点间的距离。

当接收到来自未知节点u 的信号，锚节点a 就依式（3）估计离节点u 间的距离：

2.2 控制包的传输

为了收集跳数信息，采用两类控制包：矢量跳数请求包（Vector Hop ReQuest，VHRQ）和矢量跳数响应包（Vector Hop ReSponse，VHRS）。图1 描述了这两个控制包的传输过程。

图1 VHRQ 和VHRS 的传输过程

锚节点先向邻居节点广播VHRQ，其携带的信息如式（4）所示：

式中，SADD 表示锚节点的IP 地址，由于节点是移动，锚节点每隔Δt 广播VHRQ 包，ISEQ 表示VHRQ消息的序列号，通过该序列号，保证VHRQ 包的实时性［10］。ISEQ 值越大，表示所接收的VHRQ 消息越新鲜。

HC 表示该VHRQ 包所遍历的跳数。最初，HC=0。一旦收到VHRQ，传感节点就回复VHRS，并将HC 加1。cert 表示节点证书，其有利于判断发布虚假数据的恶意节点。

未知节点一旦收到VHRQ，就回复VHRS，其格式如式（5）所示：

式中，UADD 表示未知节点的IP 地址。

2.3 VHRS 包的筛选

一旦收到所有VHRS 消息，锚节点j 就构建跳数矢量：

式中，E 为系统测时误差。

如果某个VHRS 包的VHTT 大于阈值VHTTth，则认为发送该VHRS 包的未知节点是不诚实，其发送了虚假数据。因此，锚节点拒绝接收该VHRS 包。

阈值VHTTth的定义如式（8）所示：

2.4 跳数矢量的产生流程

接收到VHRS 包后，就判断VHTT 是否大于VHTTth；若大于VHTTth，就丢弃；否则，就存储该节点的信息。直到接收到所有未知节点发送的VHRS包。整个流程如图2 所示。每个锚节点均依据图2产生自己的跳数矢量。

2.5 定位阶段

式中，α1j表示锚节点j 离第1 个未知节点的跳数，αnj表示锚节点j 离第n 个未知节点的跳数。网络内m 个锚节点就有m 个多项式。通过这些多项式构成m×n 维的跳数矢量矩阵（Hop Vector Matrix，HVM），如式（10）所示：

矩阵HVM 中第i 列HVM［；，i］包含第i 个未知节点离m 个锚节点的跳数。一旦构建了HVM，未知节点i 就选择第i 列（HVM［；，i］），然后从HVM［；，i］中选择5 个最小值。这5 个值表示未知节点i离m 个锚节点中最近的5 个锚节点的跳数。随后，依据五边形质心算法估计未知节点的位置。具体过程如下：

图3 五边形质心定位算法

3 性能分析

3.1 仿真环境

为了更好地分析HVLA 算法的性能，利用NS-2 仿真器建立仿真平台。引用Mica2 作为节点模型。在区域内部署200 个节点，其中，锚节点数为30个、未知节点数为150 个，发布虚假数据的节点（恶意节点）数为20 个，具体的仿真参数如表1 所示。

表1 仿真参数

此外，选择文献［13］提出的安全和强健的DVHop 定位算法（Secure and Robust DV-Hop Localization algorithm，SR-DH），文献［14］提出防御虫洞攻击的安全DV-Hop 定位算法（Securing DV-Hop Localization algorithm against wormhole attacks，S-DH-W）和文献［15］提出的面向虫洞攻击安全DV-Hop 定位算法（Secure DV-Hop localization scheme against wormhole，S-DH-W）作为参照，并分析它们的平均定位误差、定位所消耗时间（平均时延）以及剩余能量率。

式（13）给出了平均定位误差（Average Localization Error，ALE）的定义：

3.2 平均定位误差

首先，分析平均定位误差随未知节点的数变化情况，其中未知节点数从10～150 变化，如图4 所示。

图4 平均定位误差率

从图4 可知，在未知节点数较低时，HVLA 算法的平均定位误差性能与SR-DH-W、S-DH-W 的平均定位误差性能相媲美，并且当未知节点数增加后，HVLA 算法的平均定位误差性最低，且在未知节点数达到100 个后，其平均定位误差性几乎保持常数。在未知节点数从10～150 间变化期间，最小的平均定位误差为5.33%，最大的平均定位误差率达到13.77%。

SR-DH-W 和S-DH-W 算法分别在未知节点达到80 个和60 个后，平均定位误差快速上升。但是，SR-DH-W 算法在未知节点数较少时，其定位性能与HVLA 算法相近。然而，当未知节点数增加后，其定位误差快速增加。

SR-DH 算法的平均定位误差性能随未知节点数的增加而变化的趋势与SR-DH-W 和S-DH-W算法相反。在未知节点数较小时，定位误差较大，但是随着未知节点数的增加，其定位误差逐步减少，原因在于：SR-DH 算法采用反馈机制。未知节点数越多，其反馈的信息越丰富，越有利于降低定位误差。

3.3 平均时延

图5 显示了HVLA 定位算法的平均时延，即估计未知节点位置所消耗的时间。平均时延越低，定位算法复杂度越低，定位性能越好。

图5 平均时延

从图5 可知，相比于SR-DH、SR-DH-W 和S-DH-W 算法，HVLA 定位算法的平均时延约11.474 ms，SR-DH 算法的平均时延最高，达到85.846 ms。这也说明，SR-DH 算法是以复杂度为代价，换取高的定位精度。此外，SR-DH-W 和S-DH-W 算法的平均时延约26.71 ms 和37.52 ms。