白秋產(chǎn),張昊倫

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

0 引 言

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

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

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

圖1 TTS的示例

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

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

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

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

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

1.1 跟蹤模型

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

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

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

1.2 通信模型

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

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

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

Lsegment≥lp+1.

(1)

1.3 目標(biāo)跟蹤問題

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

2 目標(biāo)跟蹤問題的解

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

2.1 節(jié)點(diǎn)坐標(biāo)

針對等邊三角形、矩形和六邊形模型,求解目標(biāo)跟蹤問題．最初,將FoI劃分為規(guī)則形狀,然后再計算節(jié)點(diǎn)坐標(biāo)．如圖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é)點(diǎn)的橫坐標(biāo)(x)和縱坐標(biāo)(y),即x=rl、y=rlp．類似地,在奇數(shù)行,即r=(1,3,5,…)時,橫坐標(biāo)x在rl的基礎(chǔ)上加l/2．因此,用式(2)表示節(jié)點(diǎn)坐標(biāo).

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

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

(2)

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

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

(3)

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

2.2OTR

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

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

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

(4)

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

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

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

(5)

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

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

(6)

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

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é)點(diǎn)s的位置．令離節(jié)點(diǎn)s最近的第m個鄰居節(jié)點(diǎn)位于υ．將節(jié)點(diǎn)s離此鄰居節(jié)點(diǎn)的距離表示為dp,m．

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

(9)

2.4 節(jié)點(diǎn)的部署

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

Np=(Lsegmentsinθp)

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

(10)

式中,p=0,1,2．

先計算三種形狀(等邊三角形、矩形、六邊形)下所需的節(jié)點(diǎn)數(shù)的最小值Nmin,并記錄Nmin值所對應(yīng)的形狀(即p值)．為了簡化描述,用p*表示能獲取最小Np值所對應(yīng)的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é)點(diǎn)s(x,y)的位置:

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

(12)

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

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

(13)

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

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

3 性能仿真

3.1 仿真參數(shù)

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

表1 仿真參數(shù)

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

3.2 跟蹤角的影響

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

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

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

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

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

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

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

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

3.3 跟蹤距離的影響

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

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

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

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

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

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

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

3.4 目標(biāo)跟蹤k值的影響

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

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

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

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

圖7 跟蹤距離范圍

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

4 總 結(jié)

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