基于移动WSN目标追踪算法

刘志强，吴晓雄+，沈廼桐，张 旭

(1.内蒙古工业大学 信息工程学院，内蒙古 呼和浩特 010080；2.内蒙古建筑职业技术学院 建筑与规划学院，内蒙古 呼和浩特 010070)

0 引 言

在水下目标跟踪技术[1-5]应用场景中，经常会使用到移动的水下自主巡航器(autonomous underwater vehicles，AUV)进行监测与目标跟踪。该种巡航器通常是由负责监测环境和感知目标的监测感知部分、负责控制巡航器移动和姿态的动力部分，以及远程通讯和节点组网的通讯部分构成。在实际部署时，为了节省AUV能量，通常将巡航器进行组网通讯，仅由一台设备将数据进行上传。因此在特定海域中每个部署的AUV均为无线传感器网络中的一个传感器节点，利用多个AUV组成无线传感器网络，对目标进行跟踪是移动的水下自主巡航器的一个重点研究方向。

目前利用无线传感器对目标追踪的主要思想是利用传感器捕获到的目标移动信息，对目标移动路径加以预测，结合预测结果调度传感器节点，以达到最佳的追踪效果。文献[6]提出一种知识感知主动节点选择(knowledge-aware proactive nodes selection，KPNS)系统，根据目标轨迹的预测精度动态地调整主动节点的数量，提高了监测质量与跟踪性能。文献[7]通过模拟退火算法对区域传感器节点追踪方案进行优化，以平衡每个簇首节点的剩余能量、承受负载比例，从而延长节点在网时间。文献[8]提出基于簇状网络的追踪算法(dynamic cluster detection and tracking，DCDT)，以被监测的节点为研究对象，根据收集到的目标信息对所有节点进行分簇，构建动态追踪簇，进而形成对目标的分布式追踪。文献[9]提出了一种基于分区的目标跟踪框架，该框架采用改进的连续蚁群优化算法，在每个时刻自适应地调整跟踪系统的参数，使跟踪系统的能量消耗最小，并获得较高的跟踪精度。文献[10]提出了区域内传感节点基于密度的部署机制，传感器节点通过感知邻近节点，计算邻近节点与自身距离，推测周边节点部署密度，进而调整自身位置，保证局部传感节点数量，实现对目标的持续追踪。该方案没有充分考虑到传感器节点之间的位置关系(拓扑关系)，仍然存在节点部署的冗余及空洞。

综上，以上目标追踪方案没有充分考虑目标移动的随机性以及节点之间的拓扑关系，传感器节点部署不够合理，容易出现丢失目标和无效调度问题。本文将针对这些问题，在现有基于密度方案[11，12]的基础上，利用拓扑熵对节点间位置关系进行建模，实现传感器节点位置的自适应调度，使传感器节点在目标追踪路径上及时完成合理部署，实现对目标持续有效的追踪。

1 基于移动WSN网络的目标追踪模型

1.1 传感器节点运动模型

本文考察传感器节点追踪算法，在此认为传感器具有良好的运动执行能力，其系统可以依照收到的命令进行准确的移动。当移动目标深度一定时，可类似为二维平面运动模型，忽略由于水的阻力等外界因素对运动的影响。

综上所述，传感器的运动模型可以表示为如下形式

(x′，y′)=(cos(θ)·vt+x，sin(θ)·vt+y)

(1)

其中，(x′，y′) 为传感器节点运动后的位置，(x，y) 为传感器节点运动前的位置，θ为传感器节点运动方向角，v为传感器节点速度。

1.2 传感器节点间通信模型

在目标感知过程中，感知精度与目标和传感器节点的距离有关。传感器概率感知模型如图1所示。

图1 传感器概率感知模型

概率感知模型可表示为

P(c，p)={1|c-p|R

(2)

其中，c为传感器节点位置，p为目标位置，P为传感器节点发现目标的概率，α为衰减系数，r为概率感知半径最小值，R为概率感知半径最大值。为了有效调度传感器，还需要分析传感器之间的通信过程。

在理想空间中，无线信号受传播距离影响，符合Friis公式，即

PRPT=GRGT(λ4πd)η

(3)

距离发射点d处的信号衰减Ld的分布为

Ld=10lg(PRPT)

(4)

其中，PR与PT分别为接收端与发射端功率，GR与GT分别为接收端与PT发射端信号增益值，λ为波长，η为无线信号在该类介质中传播的衰减系数。假设本文传感器节点为同构节点，即GR=GT增益值相等，信号衰减Ld可以表示为

Ld=20lgGT-10ηlgλ4πd

(5)

令A′=20lgGT-10ηlgλ4π， 其中GT以及λ4π均为传感器节点的自身属性，可得

Ld=A′+10ηlgd

(6)

RSSI=PT+GT-Ld

(7)

A=PT+GT-A′

(8)

整理可得对信号衰减的一般形式为

RSSI=A-10ηlgd

(9)

基于此通信模型，传感器节点可以通过其自身接收到的信号强度判断该信号源与自身之间的近似距离。

1.3 传感器节点拓扑熵模型

为了有效描述节点间位置关系，本节将利用拓扑熵理论对节点间位置关系进行建模。

h*(f)=supAh*(f，A)

(10)

其中，h*(f) 为开覆盖熵，即拓扑熵。

定义2 设X为一个拓扑空间，如果∀x，y∈X且x≠y，点x和y分别有各自的开邻域U和V使得U∩V=∅， 则称X为一个Hausdorff空间，简称为T2拓扑空间。由Hausdorff空间定义可知，包含不少于两个欧式空间下点的离散空间是Hausdorff空间。又根据其空间性可知，当Hausdorff空间为闭集时，该空间为紧致空间。

根据上一节传感器通信模型的分析可知，基于信号衰减的传感器间距离感知为传感器节点间自映射，可令f(x)=x， 并根据Hausdorff空间性质以及紧致空间性质可知该映射为连续映射，而映射序列 {f，f2，f3，…，fn，…} 为X上由连续映射f经迭代而生产的离散拓扑板动力系统，即拓扑动力系统或紧致系统，记为 (X，f)。 不同传感器节点可以在Hausdorff空间下根据该拓扑动力系统感知周边节点元素所在位置，其拓扑熵的具体计算过程如下所示：

设定自映射为f(θ，r)=(θ，r)， 由此映射产生n次复合映射fn(θ，r)=f∘f∘…∘f∘fn(θ，r)=(θ，r)。

定义3 设(X，T) 是Hausdorff空间，B∈T， 如果∀A∈T，∃BA⊂B，s.t.A=∪B∈BAB， 则称B是Hausdorff空间的基。

因此根据上述Hausdorff空间基的定义可知，可令欧式空间X中的传感器节点组成的集合作为描述不同节点间位置概念性的Hausdorff空间的基。在此种基选择方法下，N(Af，n) 在每个子覆盖Af，n下的最少基个数为ni， 即该子覆盖下传感器节点数。

将感知半径等距划分组成的同心圆环内的点作为子覆盖。因此上述公式可以变形成

supAlimn→∞1nlogN(Af，n)=-∑Ni=1niN(1NlogN(Af，n))=-∑Ni=1niN(logN(Af，n)N)=-∑Ni=1PilogniN=-∑Ni=1PilogPi

即

E(P)=-∑ni=1Pilog2Pi

(11)

其中，Pi=NiN，Ni为落在距离划分内的传感器节点数量，N为样本内总节点数。

定理1 当传感器节点均匀分布时，各个传感器节点感知到拓扑熵到达最大。

证明：利用拉格朗日乘子法构造上述函数E(P)的构造函数

G(p1，p2，…，pn，λ)=-∑ni=1pilnpi+λ(∑ni=1pi-1)

(12)

由于∑ni=1pi-1=0， 分别对pi和λ求导，并令其为0，可以得到

∂G∂pi=-lnpi-1+λ=0，i=1，2，…，n

(13)

可得：p1=p2=…=pn=1n时，即周边传感器节点均匀分布时，感知到的拓扑熵达到最大值。

利用拓扑熵来衡量周边节点分布情况，进而优化节点部署，实现对目标的持续追踪。

2 面向目标持续追踪的传感器部署调整方案

本节根据上文所述传感器节点拓扑熵模型的相关理论，提出动态调整传感器节点部署方案，主要有3个阶段：

第一阶段：传感器节点对目标进行感知，监测其感知范围内是否存在目标节点，进而判断是否需要进行移动；

第二阶段：感知到目标的传感器节点与邻近节点进行通信，计算当前节点与周边节点之间的拓扑熵，用于评估周边节点分布是否均匀；

第三阶段：根据得到的拓扑熵向拓扑熵增加的方向移动，对目标进行持续追踪。

2.1 目标节点拓扑熵计算

在传感器节点部署到观测水域前，依据节点自身硬件特点对传感器节点的信号强度进行划分，划分间隔与信号强度的关系如图2所示。

图2 传感器节点感知信号强度

根据距离间隔对传感器节点通信强度进行分类，测量出相等距离下信号强度差，以便划分子覆盖，计算拓扑熵。结合目标运动情况，感知拓扑熵变化，并沿拓扑熵增大方向移动。具体过程如时序图3所示。

图3 拓扑熵计算时传感器节点工作时序图

算法1：拓扑熵算法

(1) Input:COM//传感器节点通信常数

(2) Input:RSSI[] //传感器节点感知到信号强度

(3) Input:n//感知到的信号数量

(4) Input:k//强度分级数

(5) Input:η//当前介质通信衰减系数

(6) Input:distancemax//最大感知半径

(7) Input:distancemin//当前强度划分下, 第一层感知半径

(8) Output:E//目标临近传感器节点的拓扑熵

(9) for i=1 to n do

(10)distance[i]=10COM-RSSI[i]10η

(11) end for

(12) for i=1 to n

(13) switch|distance[i]-distancemindistancemax-distancemink|

(14) case 0:distance0++;count0++;

(15) case 1:distance1++;count1++;

(16) …

(17) case k:distancek++;countk++;

(18) default: Error

(19) end switch

(20) end for

(21) for i=1 to k

(22)Pi=countin

(23)E=E+Pi·log2Pi

(24) end for

算法1是传感器节点拓扑熵计算过程，结合距离distancemax和distancemin将得到的多组邻近节点距离进行分类，最后根据式(8)计算拓扑熵值。

2.2 传感器节点运动调整策略

为了得到新的运动方向和速度需要对传感器节点间的距离矢量进行分析。根据传感器节点同周边节点信号交互方向及强度，通过几个观测周期的趋势累加，确定新的移动方向和速度。考虑到目标移动具有一定的不确定性(延迟和误差)，利用衰减函数对此前得到的移动速度及方向进行衰减计算，来降低之前数据对当前时刻的影响，保证传感器节点及时确定最佳移动方式。

本文利用常用的指数衰减函数的变形形式作为历史数据的衰减函数，如式(14)所示

d=∑NT=t(e-T∑Ni，j=1&i≠j(i-j))

(14)

当传感器节点被唤醒且感知范围内未感知到目标时，传感器节点会根据其唤醒信号来源判断其运动速度。

在图4中，由于目标P1进入传感器节点A1和A2的感知半径内，传感器节点B1被初次唤醒。唤醒后，节点B1将持续记录其接收到的通信范围内的所有唤醒信号，直到一定时间后不再产生新的唤醒信号。节点B1将记录A1和A2所发送的唤醒信号。此后被唤醒节点将跟据唤醒信号中的唤醒信息计算自身与唤醒信号发生节点之间的矢量，并计算矢量和，进而得到节点自身的移动方向。B1处实线即为传感器节点的移动方向。目标继续移动，形成一段时间的持续追踪后，到达P2位置，由于节点B2在前一时刻已经接收到唤醒信号，并作出了响应移动，即B2存在前一时刻信号来源矢量V1、V2，将V1、V2通过式(14)求得衰减后的前次信号源矢量和作为修正矢量。最终在计算传感器节点移动方向时，将传感器节点唤醒的信号来源位置矢量与衰减后得到的修正矢量相加得到当前周期传感器节点的运动方向。

综上，节点运动速度大小与拓扑熵变化以及唤醒信号源位置有关，将拓扑熵对通信距离进行量化分析可以得到节点的运动速度式(15)

v=|ΔSSmax+dlmax|·vmax，Smax=∑ni=11klog21k

(15)

其中，v为传感器节点的速度大小，ΔS为拓扑熵增量，lmax为最大通信半径，Smax为当前区域节点最大拓扑熵，d为信号源与接收端之间的距离，vmax为传感器节点最大速度，n为当前传感器节点感知范围内节点数量，k为信号强度确定的子覆盖数量。速度调整方案的时序图如图5所示。

图5 计算传感器节点移动速度时传感器节点工作时序图

算法2：传感器节点运动调整方案算法

(1)Input: 传感器当前位置 (x,y)

(2)Output: 传感器下一时刻位置 (x′,y′)

(3)If|(xA,yA)-(x,y)

(4)If|(xA,yA)-(xB,yB)|

(5)B.li=(xA-xB,yA-yB) //A节点感知到目标,将自身位置告知通信半径内的临近节点, 若节点在通信范围rt内存在接收到A类节点, 则记为B类节点。

(6)For(i=1;i<=n;i++)

(7)If|(xi,yi)-(xB,yB)|

(8)B.um=|(xi,yi)-(xB,yB)| //B节点向其通信范围内节点发出请求, 通过接收信号感知强度RSSI计算传感器分级n, 判断距离。

(9) Else:B.state=sleep//若未感知到目标或接收到A类节点信号则节点进入休眠等待进入下一个感知周期。

(10)B.l=B.lj-B.li//B节点向其发送信息的A类节点发送通信请求, 根据回波强度RSSI以及返回的坐标计算信息来源矢量, 并利用感知到目标先后逆序作差(i信息源先于j信息源感知到目标), 进行矢量减法得到节点移动向量。

(11)Switch|B.um-B.umminB.ummax-B.umminK|

(12) Case 0:B.N0++

(13) Case 1:B.N1++

…

(14) Case k:B.NK++

(15) Default: Error

(16) end switch

(17)B.Pi=B.NiN

(18)B.E=-∑Ni=1B.Pilog2B.Pi//B类节点根据自身感知的距离, 并依据拓扑熵式(11)进行拓扑熵计算。

(19)B.bef=∑M×tT=te-T∑Mi,j=1&i≠j(B.beforei-B.beforej)

//根据式(14)计算信号源衰减矢量。

(20)Smax=∑πr2ci=11Klog21K

(21)B.v=|ΔB.E·lmaxSmax+B.l|·Vmaxlmax//根据式(15)计算传感器节点在当前感知周期内移动速率。

(22)end for

(23)θ=θ(B.bef)+θ(B.l) //根据信号源矢量以及计算得到的衰减矢量计算传感器节点移动方向。

(24)(x′,y′)=(cos(θ)×B.v+x,sin(θ)×B.v+y) //根据传感器节点运动模型得到节点下一时刻的坐标 (x′,y′)。

3 仿真实验

3.1 仿真目的

为了分析节点损耗情况下基于拓扑熵节点移动(topo-logical entropy solution)方案的捕捉效果，本文通过其对比节点静止(Motionless)方案[13]、传感器节点随机运动(Stochastic Motion)方案[14]和传感器节点根据密度调整追踪(Density Solution)方案[12]，实验结果表明基于拓扑熵的移动捕捉方案较其它3种常见方案具有较高的捕捉效率。

3.2 仿真环境

本文在Intel(R)Core(TM)i5-8300H CPU@2.30 GHz计算机配置、Windows 10操作系统下，采用Matlab R2018a编程实现。仿真设定在100*100 m的矩形二维平面内，设定目标以1.5 m每秒的线速度在观测水域内随机运动，转弯半径为6 m，每秒发生转弯的概率小于20%，若运动至边缘则折向矩形中心运动。对目标前90 s的运动情况进行观测分析。初始随机分布一定数量的传感器节点，最大感知半径为4.5 m，绝对感知半径为1 m，感知概率参数α设定为-1.316，传感器节点最大可移动速度为1 m/s。在追踪捕捉过程中传感器节点与目标的体积忽略不计，设定传感器节点的通信半径为2倍的最大感知半径。

由正六边形部署所需节点数量公式[15]可得

(16)

实现正六边形全覆盖所需最少节点部署数量为195个，因此本文以200个节点作为全覆盖所需必要节点数量。

3.3 实验结果分析

3.3.1 节点数量对目标追踪效果的影响

仿真实验设定保持传感器节点最大感知半径4.5 m不变，部署数量从500个降低至100个。在上述仿真实验背景下，对比其它3种方案的捕捉效果。图6(a)至图6(e)中以目标进入监测水域的时间作为横轴，捕获率作为纵轴。根据结果可以发现：

图6 N个节点调整方案捕获率随时间变化

(1)拓扑熵方案明显优于其它3种方案的追踪效果，较其它3种方案捕获率有5%～10%的提升。随着传感器节点数量的减少，传感器节点捕获率降低的程度比其它3种方案少降低5%。表明在传感器节点数量减少的情况下，拓扑熵方案能够对目标进行更持久的追踪，验证了拓扑熵方案的有效性。对比4种调整方案可以看出，基于密度和基于拓扑熵的调整方案在总体上均优于静止和随机运动方案，究其原因是由于后两种方案部署时没有充分考虑节点间的拓扑关系，导致不能在目标移动方向上形成有效部署，降低了追踪率。

(2)如图6(a)至图6(e)所示，拓扑熵方案能够更加快速的使追踪捕获率趋于稳定。相比其它3种方案，拓扑熵方案对应的捕获率第一个记录点数值普遍高于其它3种方案。表明在传感器节点数量减少的情况下，拓扑熵方案相比其它3种方案能够更早的对目标进行追踪，提高了追踪的时效性。

3.3.2 感知半径对目标追踪效果的影响

为了模拟传感器节点通信感知半径衰减的情况，本节设定传感器节点数量300个不变，最大感知半径依次由5 m降低到4 m，分析4种目标追踪捕捉方案对目标追踪的效果。由图7(a)至图7(c)可知，通信感知半径从5 m下降到4 m，拓扑熵方案相比自身捕获率降低7%，而其它方案均相比自身降低10%～15%。说明在传感器节点在数量不变且通信感知半径衰减的情况下，拓扑熵方案依旧能保持较好的捕获率。

图7 感知半径为R米的传感器节点捕获率随时间变化

4 结束语

本文针对传感器节点长时间使用造成损耗时追踪效率降低的情况，提出了基于拓扑熵的传感器节点追踪方案，提高传感器节点对目标的追踪效率。该方案利用拓扑熵作为传感器节点拓扑结构的刻画，将拓扑熵变化量作为传感器节点移动时速度调整中的指导标准，调节节点移动方向及速度，使得节点在目标移动水域均匀部署，持续追踪目标。利用仿真验证了基于拓扑熵的追踪方案，在传感器节点数量减少的情况下，相比现有方案在追踪效率上有了明显提升，验证了拓扑熵方案可以在传感器节点损耗的情况下，有效优化移动传感网络在目标追踪过程中的节点部署，持续提升目标追踪效果。