基于k-目標跟蹤的節點部署優化算法

白秋產,張昊倫

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

0 引 言

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

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

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

圖1 TTS的示例

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

1 系統模型及約束條件

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

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

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

1.1 跟蹤模型

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

圖3 定向節點模型

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

1.2 通信模型

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

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

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

Lsegment≥lp+1.

(1)

1.3 目標跟蹤問題

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

2 目標跟蹤問題的解

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

2.1 節點坐標

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

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

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

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

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

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

(2)

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

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

(3)

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

2.2OTR

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

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

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

(4)

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

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

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

(5)

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

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

(6)

結合式(4)、(5)和(6),將OTR綜述地表述如下:將興趣區域Ψ劃分模型p,且邊長為l,則興趣區域就能被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)表示節點s的位置．令離節點s最近的第m個鄰居節點位于υ．將節點s離此鄰居節點的距離表示為dp,m．

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

(9)

2.4 節點的部署

利用OSL在興趣區域Ψ部署節點．假定在寬為L、長為B的規則區域內,所需的節點數Np．

Np=(Lsegmentsinθp)

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

(10)

式中,p=0,1,2．

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

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

(11)

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

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

(12)

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

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

(13)

如圖5顯示部署節點過程．

圖5 部署節點的過程

3 性能仿真

3.1 仿真參數

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

表1 仿真參數

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

3.2 跟蹤角的影響

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

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

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

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

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

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

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

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

3.3 跟蹤距離的影響

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

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

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

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

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

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

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

3.4 目標跟蹤k值的影響

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

圖6 所需的節點數

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

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

圖7 跟蹤距離范圍

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

4 總 結

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