基于k-目標跟蹤的節(jié)點部署優(yōu)化算法

白秋產,張昊倫

(1.淮陰工學院 自動化學院,江蘇 淮安 223003;2. 黑龍江大學 機電工程學院, 黑龍江 哈爾濱 150080)

0 引 言

無線傳感網(wǎng)絡(WSNs)已廣泛應用于機器人系統(tǒng)、病人看護、目標跟蹤[1-2]．在目標跟蹤應用中,先將傳感節(jié)點部署于興趣區(qū)域[3-4],再通過這些傳感節(jié)點感測目標移動,進而實現(xiàn)對目標的跟蹤．WSNs中的目標跟蹤被認為是衡量跟蹤系統(tǒng)(TTS)[5-8]的跟蹤性能的重要指標．

若有k個定向節(jié)點同時跟蹤FoI的移動目標,則稱為k-目標跟蹤(kTT)．圖1示出了一個TTS系統(tǒng),傳感節(jié)點分布于長形區(qū)域,目標在FoI內移動．當靠近移動目標時,定向節(jié)點就將跟蹤信息傳輸至信宿．如果從定向節(jié)點至信宿有m條連通路徑,且m≥1,則稱為m-連通．

本文旨在通過優(yōu)化節(jié)點部署方案,提高WSNs內的kTT的跟蹤質量．考慮三角形、矩形和六邊形節(jié)點部署模型,并針對這些模型解決問題:如何以最少的節(jié)點實現(xiàn)目標跟蹤．文獻[9]利用超寬帶傳感節(jié)點和Bernoulli濾波器解決目標跟蹤問題[10]．通過Bernoulli濾除數(shù)據(jù)噪聲．類似地,文獻[11]針對1-覆蓋和m-連通的WSNs,研究了最優(yōu)節(jié)點部署策略．此外,文獻[12]也研究了節(jié)點部署問題．依據(jù)不同的通信半徑和感測半徑,研究如何以最少的節(jié)點數(shù)實現(xiàn)4-連通和興趣區(qū)域的全覆蓋．

圖1 TTS的示例

然而,現(xiàn)在的解決目標跟蹤問題方案僅考慮一個目標跟蹤．并且,這些節(jié)點部署方案只是基于特定的區(qū)域．為此,針對目標跟蹤問題進行分析．考慮三種規(guī)則形狀(等邊三角形、矩形和六邊形),分析在這些規(guī)則形狀下實現(xiàn)k-目標跟蹤所需的節(jié)點數(shù),并推導了最優(yōu)邊長．

1 系統(tǒng)模型及約束條件

定向節(jié)點確定性地部署在興趣區(qū)域Ψ內．考慮三種規(guī)則多邊形:等邊三角形、矩形和六邊形,如圖2所示．圖2中的點a和點b表示一段路線的始點和終點．

(a)等邊三角形 (b)矩形 (c)六邊形

令l表示多邊形的邊長,且l>0．并引用p表示多邊形,p=0、1、2分別表示等邊三角形、矩形、六邊形．同時,令(x,y)表示FoI內的節(jié)點位置,且(x,y)∈Ψ,x≥0,y≥0．

1.1 跟蹤模型

引用定向的跟蹤模型[13]．圖3示出了一個定向節(jié)點模型．令φ表示節(jié)點的跟蹤角度,且1≤φ≤360°．此外,每個節(jié)點只有有限的跟蹤半徑．令Rs表示節(jié)點的跟蹤半徑,且Rs>0．

圖3 定向節(jié)點模型

引用跟蹤區(qū)域的定向(OTR)變量,其表示FoI內定向節(jié)點的方向．令θx,y表示將位于s(x,y)處的節(jié)點的定向矢量,且0≤θx,y≤2π．

1.2 通信模型

引用全向的通信模型．節(jié)點si能夠與其通信范圍Rc內的任何節(jié)點通信．令A(si,Rc)表示節(jié)點si的通信區(qū)域．假定網(wǎng)絡內所有節(jié)點具有相同的通信半徑Rc．

定義1:如果節(jié)點si離節(jié)點sj的距離小于Rc,則節(jié)點sj就是節(jié)點si的一個鄰居節(jié)點．在m-連通的WSNs,任意節(jié)點sx的鄰居節(jié)點數(shù)大于m,且m≥1．

定義2:令點a和點b是路徑一段的始點和終點．這兩點的歐式距離就是該段的長度,如圖2所示．令l表示規(guī)則多邊形的邊長．若滿足式(1),則表明目標穿越了至少一個跟蹤區(qū)域,即

Lsegment≥lp+1.

(1)

1.3 目標跟蹤問題

給定FoI區(qū)域Ψ的參數(shù)(Rs、Rc、k、m、Lsegment),目標跟蹤問題就是:決定區(qū)域Ψ內定向節(jié)點的位置和跟蹤區(qū)域OTR,致使移動目標至少被k個定向節(jié)點跟蹤,且所需的定向節(jié)點數(shù)最少．

2 目標跟蹤問題的解

本節(jié)針對三個不同模型(等邊三角形、矩形和六邊形),求解目標跟蹤問題．求解過程可分為4個階段．第一步,估計定向節(jié)點坐標;第二步,估計跟蹤區(qū)域的OTR,隨后再針對給定模型,估計最優(yōu)的邊長度(OSL),最后,再依據(jù)OSL和規(guī)則模型計算所需的最少節(jié)點數(shù)．

2.1 節(jié)點坐標

針對等邊三角形、矩形和六邊形模型,求解目標跟蹤問題．最初,將FoI劃分為規(guī)則形狀,然后再計算節(jié)點坐標．如圖4所示．

(a)等邊三角形 (b)矩形 (c)六邊形

令l表示邊長,lp表示高度,且lp=lsinθp,其中p=0,1,2．將FoI區(qū)域劃分偶數(shù)和奇數(shù)行,并令r表示行數(shù)．

在偶數(shù)行里,即r=(0,2,4,…),用行數(shù)r表示節(jié)點的橫坐標(x)和縱坐標(y),即x=rl、y=rlp．類似地,在奇數(shù)行,即r=(1,3,5,…)時,橫坐標x在rl的基礎上加l/2．因此,用式(2)表示節(jié)點坐標.

(x,y)∈{(rl,rlp),r=(0,2,4,…),

(rl+l/2,rlp),r=(1,3,5,…).

(2)

在矩形模型中,如圖4(b)所示, 橫坐標和縱坐標相等．因此,可用式(3)計算矩形模型的節(jié)點坐標:

(x,y)∈(rl,rlp).

(3)

三角形與六邊形模型的差別僅在于:節(jié)點是否位于六邊形的中心,如圖4(c)所示．為了估計六邊形模型中節(jié)點坐標,就依據(jù)式(2)判斷是否節(jié)點位于六邊形內,如滿足:mod(y/lp,2)=mod(x,3)+1,則表明六邊形內沒有節(jié)點．

2.2OTR

使用以下定理推導每個模型中節(jié)點的OTR．

定理1:將興趣區(qū)域Ψ劃分等邊長l的矩形．令θx,y表示位于(x,y)處節(jié)點的方向,其中{x,y}≥0．如果滿足式(4),則興趣區(qū)域就能被k-目標跟蹤.

Rs≥2klandθx,y=mod(x+y,2)×π2.

(4)

定理2:將興趣區(qū)域Ψ劃分等邊三角形,且邊長為l．令θx,y表示位于(x,y)處節(jié)點的方向,如果滿足式(5),則興趣區(qū)域就能被k-目標跟蹤:

Rs≥3klandθx,y=mod((x+y+

mod(y,2)),3)×π3.

(5)

定理3:將興趣區(qū)域Ψ劃分六邊形,且邊長為l．令θx,y表示位于(x,y)處節(jié)點的方向,如果滿足式(6),則興趣區(qū)域就能被k-目標跟跟蹤:

Rs≥4klandθx,y=mod((x+y+mod(y,2)),3)×π3.

(6)

結合式(4)、(5)和(6),將OTR綜述地表述如下:將興趣區(qū)域Ψ劃分模型p,且邊長為l,則興趣區(qū)域就能被k-目標跟跟蹤的條件:

Rs≥(3p2-5p+62)kl,

(7)

且

θx,y≥

{mod((x+y+mod(y,2)),3)×θ0,ifp=0,

mod((x+y),2)×θ0,ifp=1,

mod((x+y+mod(y,2)),3)×θ0,ifp=2.

(8)

2.3OSL

令s(x,y)表示節(jié)點s的位置．令離節(jié)點s最近的第m個鄰居節(jié)點位于υ．將節(jié)點s離此鄰居節(jié)點的距離表示為dp,m．

min(Lsegmentp+1,2Rs(3p2-5p+6)k,Rcdp,m).

(9)

2.4 節(jié)點的部署

利用OSL在興趣區(qū)域Ψ部署節(jié)點．假定在寬為L、長為B的規(guī)則區(qū)域內,所需的節(jié)點數(shù)Np．

Np=(Lsegmentsinθp)

(Bsegment-Bpcosθp3segment-cosθp).

(10)

式中,p=0,1,2．

先計算三種形狀(等邊三角形、矩形、六邊形)下所需的節(jié)點數(shù)的最小值Nmin,并記錄Nmin值所對應的形狀(即p值)．為了簡化描述,用p*表示能獲取最小Np值所對應的p值．

Nmin={Np*|minp=0,1,2Np}.

(11)

將p*也稱為最優(yōu)模型．再將p*代入式(9),得到最優(yōu)的OSL值*segment．將p*賦給p(p←p*)、*segment賦給l(l←*segment)．然后,依據(jù)式(12)計算節(jié)點s(x,y)的位置:

(rl+lcos(θp2)cos(θp)mod(ylp,2),rlp).

(12)

如果(x,y)位于Ψ內,且將節(jié)點放置于s(x,y)處．若不屬于Ψ內,就將節(jié)點放置在Ψ邊界上交叉點上．對將x、y的進行更新:

x←x+l、y←y+lp,

(13)

如圖5顯示部署節(jié)點過程．

圖5 部署節(jié)點的過程

3 性能仿真

3.1 仿真參數(shù)

利用NS 2.34軟件建立仿真平臺．具體的仿真參數(shù)如表1所示．考慮兩個目標移動模型:1)隨機步行移動 (RKM)模型;2)隨機航點移動(RPM)模型．

表1 仿真參數(shù)

在RKM模型中,目標隨機選擇移動方向和移動速度,從當前位置移動至另一個位置．速度范圍限定在[?min,?max],方向限定在[0,2π]．令?avg表示目標的平均移動速度．在固定時間間隔Ct或者移動固定距離Cd后完成目標移動．而RPM模型中,目標每移動一段時間就暫停一段時間Pt．然后,再隨機選擇目的節(jié)點,以平均速度?avg進行移動．

3.2 跟蹤角的影響

首先分析跟蹤角對跟蹤誤差的影響．跟蹤誤差是指目標準確的位置與所跟蹤的位置間差值．表2～7示出了在等邊三角形、矩形和六邊形模型中的跟蹤誤差．

表2 RKM條件下跟蹤誤差(等邊三角形)

表3 RPM條件下跟蹤誤差(等邊三角形)

表4 RKM條件下跟蹤誤差(矩形)

表5 RPM條件下跟蹤誤差(矩形)

表6 RKM條件下跟蹤誤差(六邊形)

表7 RPM條件下跟蹤誤差(六邊形)

從表2～7可知,目標的角度和速度的增加,增加了跟蹤誤差．原因在于:速度的增加,降低了目標的穩(wěn)定性．此外,相比于矩形和六邊形,等邊三角形具有最小的平均跟蹤誤差．

3.3 跟蹤距離的影響

表8～13示出了跟蹤距離對跟蹤誤差的影響．從表中的數(shù)據(jù)可知,當跟蹤距離從5 m增加至10 m時,平均跟蹤誤差提高了近50%．原因在于:跟蹤距離越大,用于跟蹤的信號強度就越弱．這不利于跟蹤精度．

表8 RKM條件下跟蹤誤差(等邊三角形)

表9 RPM條件下跟蹤誤差(等邊三角形)

表10 RKM條件下跟蹤誤差(矩形)

表11 RPM條件下跟蹤誤差(矩形)

表12 RKM條件下跟蹤誤差(六邊形)

表13 RPM條件下跟蹤誤差(六邊形)

3.4 目標跟蹤k值的影響

本小節(jié)分析k值對目標跟蹤性能的影響．首先考慮k值對所需的節(jié)點數(shù)Np的影響．仿真參數(shù):m=1、Rc=45 m、Rs=35 m、‖Ψ‖=200 m×200 m,l=8 m．仿真數(shù)據(jù)如圖6所示．

圖6 所需的節(jié)點數(shù)

由圖6可知,符合預期,k值的增加,增加了所需的節(jié)點數(shù)．此外,除了k=1外,矩形模型所需的節(jié)點數(shù)最少．原因在于:k值越高,跟蹤重疊區(qū)域越多,這就增加所需的節(jié)點數(shù)．

然后,考慮k值對節(jié)點的跟蹤距離范圍的影響．仿真參數(shù):m=1、Rs=45 m、‖Ψ‖=200 m×200 m,l=8 m,Np=200．仿真數(shù)據(jù)如圖7所示．

圖7 跟蹤距離范圍

由圖7可知,節(jié)點的跟蹤距離范圍隨k值增加而上升．原因在于:在固定的節(jié)點數(shù)和跟蹤角度前提下,k值越大,跟蹤的區(qū)域就越大．

4 總 結

針對WSNs中k-目標跟蹤問題,進行分析,并利用定向節(jié)點解決k-目標跟蹤問題．基于規(guī)則形狀,推導了最優(yōu)邊長和所需的節(jié)點數(shù),并優(yōu)化部署節(jié)點,進而解決目標跟蹤問題．最終,通過數(shù)值證實分析的正確性．本文的分析給設計基于WSNs的目標跟蹤的節(jié)點部署提供參考．