基于移動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 結束語

本文針對傳感器節點長時間使用造成損耗時追蹤效率降低的情況，提出了基于拓撲熵的傳感器節點追蹤方案，提高傳感器節點對目標的追蹤效率。該方案利用拓撲熵作為傳感器節點拓撲結構的刻畫，將拓撲熵變化量作為傳感器節點移動時速度調整中的指導標準，調節節點移動方向及速度，使得節點在目標移動水域均勻部署，持續追蹤目標。利用仿真驗證了基于拓撲熵的追蹤方案，在傳感器節點數量減少的情況下，相比現有方案在追蹤效率上有了明顯提升，驗證了拓撲熵方案可以在傳感器節點損耗的情況下，有效優化移動傳感網絡在目標追蹤過程中的節點部署，持續提升目標追蹤效果。