包 威，毛鶯池，王龍寶，陳小麗

(河海大學(xué) 計算機與信息學(xué)院，南京 211100)

(*通信作者電子郵箱maoyingchi@gmail.com)

基于動態(tài)分簇的移動目標追蹤方法

包 威，毛鶯池*，王龍寶，陳小麗

(河海大學(xué) 計算機與信息學(xué)院，南京 211100)

(*通信作者電子郵箱maoyingchi@gmail.com)

針對無線傳感器網(wǎng)絡(luò)(WSN)中目標追蹤的準確性低、網(wǎng)絡(luò)能耗過高和網(wǎng)絡(luò)生命周期短等問題，提出基于動態(tài)分簇的移動目標追蹤技術(shù)。首先，構(gòu)建了雙層環(huán)狀動態(tài)分簇的拓撲模型(TRDC)，并提出了動態(tài)分簇的更新算法；其次，在質(zhì)心定位算法基礎(chǔ)上，考慮到節(jié)點的能量，提出了基于功率級別的質(zhì)心定位(CLPL)算法；最后，為了進一步減小網(wǎng)絡(luò)的能耗，改進CLPL算法，提出了隨機性定位算法。在仿真實驗中，與靜態(tài)簇相比，網(wǎng)絡(luò)周期延長了22.73%；與非環(huán)狀簇相比，丟失率降低了40.79%；而追蹤準確性與基于接受信號強度值(RSSI)算法相差不大。所提的追蹤技術(shù)能夠有效保證追蹤準確度，同時降低網(wǎng)絡(luò)能耗，減小目標丟失率。

無線傳感器網(wǎng)絡(luò)；雙層環(huán)狀；目標追蹤；動態(tài)簇；質(zhì)心定位

0 引言

目標追蹤是無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)最具代表性和基礎(chǔ)性的應(yīng)用之一。大量的微型傳感器節(jié)點部署在監(jiān)測區(qū)域內(nèi)，通過無線通信方式形成一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)稱為無線傳感器網(wǎng)絡(luò)[1-2]。目標追蹤在各個領(lǐng)域都有所涉及：如在軍事上，對敵人坦克、裝甲車進行定位和跟蹤；在災(zāi)難預(yù)測方面，定位泥石流的發(fā)生地點以及擴散速度等信息；在動物遷徙監(jiān)測方面，需要追蹤遷徙的動物，獲得其位置和種群等信息。移動目標追蹤技術(shù)幾乎涉及到無線傳感器網(wǎng)絡(luò)的各個應(yīng)用領(lǐng)域，在環(huán)境監(jiān)測[3]、軍事監(jiān)控[4]和基建保護[5]等領(lǐng)域都被廣泛應(yīng)用，體現(xiàn)了巨大的科學(xué)意義和應(yīng)用前景。

目前，移動目標追蹤技術(shù)采用的拓撲結(jié)構(gòu)，在監(jiān)測較快的移動目標時，存在著定位不夠準確問題，容易出現(xiàn)丟失追蹤目標，導(dǎo)致重新定位目標，消耗較大的能量，直接影響追蹤目標的及時性，導(dǎo)致較長的網(wǎng)絡(luò)延遲?，F(xiàn)有的質(zhì)心定位算法，在網(wǎng)絡(luò)節(jié)點部署不均勻時，追蹤目標時會出現(xiàn)較大的誤差，追蹤不夠精確，而且網(wǎng)絡(luò)中能量不同的節(jié)點對定位目標有較大的影響。此外，連續(xù)不斷地定位追蹤目標，雖然可以提供較為準確的目標定位，但是付出了較大的能耗代價。總之，無線傳感器網(wǎng)絡(luò)的移動目標追蹤都要面對兩個挑戰(zhàn)：一是設(shè)計追蹤模型，保證目標定位和移動軌跡描述的準確性；二是盡量減少目標追蹤模型的能量消耗，延長整個網(wǎng)絡(luò)的生命周期。

針對這兩個問題，本文主要工作如下：

1)一般的動態(tài)分簇監(jiān)測較快的移動目標時，容易丟失目標，提出雙層環(huán)狀動態(tài)分簇的拓撲模型(Two-Ring Dynamic Clustering, TRDC)；為適應(yīng)目標的隨機性移動，提出了動態(tài)簇的更新算法。

2)在質(zhì)心定位算法的基礎(chǔ)上進行改進，將節(jié)點的能量考慮在內(nèi)，提出了基于功率級別的質(zhì)心定位(Centroid Localization based on Power-Level, CLPL)算法；為了減少網(wǎng)絡(luò)的能耗，進一步優(yōu)化CLPL算法，結(jié)合目標移動的相關(guān)性，提出了隨機性定位算法。

3)通過實驗，得出基于環(huán)狀動態(tài)分簇的移動目標追蹤技術(shù)，在追蹤準確度、能耗和丟失率等方面具有優(yōu)勢。

1 研究現(xiàn)狀

傳感器監(jiān)測用戶感興趣的事件，節(jié)點間相互協(xié)作，計算出移動事件的軌跡，回傳給基站?；靖鶕?jù)計算出來的軌跡，對移動事件進行追蹤。目前，無線傳感器網(wǎng)絡(luò)的移動目標追蹤技術(shù)一般可以歸納為：

1)基于二元傳感器網(wǎng)絡(luò)的目標追蹤技術(shù)。如CTBD(Cooperative Tracking with Binary-Detection)[6]、BPS(Binary Proximity Sensors)[7]。追蹤目標處于傳感器節(jié)點感知范圍內(nèi)或感知范圍外，二元傳感器節(jié)點的功能非常有限，只能根據(jù)目標是否在節(jié)點的感知范圍內(nèi)作出決策，而無法測量目標與節(jié)點的距離。

2)基于節(jié)點選擇協(xié)作的目標追蹤技術(shù)。通過選擇合適的節(jié)點協(xié)作執(zhí)行追蹤任務(wù)，減少網(wǎng)絡(luò)內(nèi)工作節(jié)點數(shù)目，降低數(shù)據(jù)傳輸量，從而節(jié)省能耗和通信帶寬。信息驅(qū)動的節(jié)點協(xié)作機制[8]根據(jù)節(jié)點通信、獲取目標位置信息以及處理監(jiān)測數(shù)據(jù)的能耗三方面信息，選擇下一時刻的跟蹤節(jié)點。由于節(jié)點可以選擇后繼追蹤節(jié)點，因此該機制能夠有效減少參與追蹤任務(wù)的節(jié)點數(shù)量。

3)可容錯的目標追蹤技術(shù)。由于傳感器節(jié)點可能失效、感知部件精度有限和環(huán)境干擾等因素，WSN存在各種不確定性。容錯機制可降低網(wǎng)絡(luò)不確定性對目標追蹤質(zhì)量的影響，基于不可靠節(jié)點序列的目標追蹤方法[9]，考慮到感知范圍和環(huán)境噪聲的不規(guī)則性等因素，將追蹤問題轉(zhuǎn)化為節(jié)點序列的最優(yōu)化匹配問題。此外，引入睡眠調(diào)度機制[10]，使活躍節(jié)點協(xié)同工作對目標進行定位，此方法充分考慮了信息丟失和感知誤差帶來的非確定性。

4)基于特定網(wǎng)絡(luò)拓撲結(jié)構(gòu)的目標追蹤技術(shù)。通過采用特定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，協(xié)助節(jié)點完成目標的監(jiān)測和追蹤任務(wù)。如基于分布式動態(tài)分簇的目標追蹤方法[11]，該方法假設(shè)能力較強的特殊傳感器節(jié)點擔(dān)當(dāng)簇頭節(jié)點，當(dāng)簇頭節(jié)點監(jiān)測到信號強度超過預(yù)定義閾值后，即轉(zhuǎn)入活躍狀態(tài)，并向鄰居節(jié)點廣播數(shù)據(jù)以召集簇內(nèi)節(jié)點，簇頭節(jié)點接收簇內(nèi)成員的感知信息，并估算追蹤目標位置。

5)基于預(yù)測模型的目標追蹤技術(shù)。根據(jù)目標此時的位置，預(yù)測目標下一時刻的位置，調(diào)度節(jié)點處于工作狀態(tài)或睡眠狀態(tài)，節(jié)省網(wǎng)絡(luò)能耗。由于目標的運動軌跡具有連續(xù)性，無法從單個時間間隔內(nèi)預(yù)測目標移動軌跡，無縫數(shù)據(jù)挖掘(Seamless Data Mining, SDM)算法[12]能夠發(fā)現(xiàn)移動目標的時間運動模式，并提出了基于時間運動模式的目標定位算法，有效減少預(yù)測誤差。

2 系統(tǒng)模型

目標在區(qū)域內(nèi)移動，能夠被傳感器節(jié)點監(jiān)測的區(qū)域稱為追蹤區(qū)域。為了簡化起見，本文對無線傳感器網(wǎng)絡(luò)模型作出了如下假設(shè)：

1)追蹤區(qū)域S為二維平面區(qū)域；節(jié)點一旦部署不再移動；只有一個sink節(jié)點，其存儲能力和計算能力不受限制；

2)節(jié)點均勻分布，每個節(jié)點有一個ID，從1到n標識；

3)節(jié)點通過GPS(Global Position System)或其他機制[13]獲得自己的坐標信息，每個感知節(jié)點都能獲得sink節(jié)點的坐標信息；

4)節(jié)點的感知功率級別是可調(diào)的，感知半徑隨功率級別動態(tài)變化[14]；

5)節(jié)點有四種狀態(tài)：休眠(sleep)、等待(wait)、工作(work)和κ級別工作(κ_work)。工作狀態(tài)的節(jié)點可正常感知和通信；休眠狀態(tài)的節(jié)點不工作；等待狀態(tài)的節(jié)點感知半徑較??；κ級別工作是感知功率級別增大κ(κ≥1，κ=1時為正常工作狀態(tài))倍后的狀態(tài)，具有較大的感知半徑。節(jié)點信息表如表1所示。

表1 節(jié)點信息表

在目標未進入節(jié)點感知范圍內(nèi)，節(jié)點采取節(jié)能的工作機制[15]。當(dāng)目標進入感知范圍內(nèi)后，為了提高監(jiān)測的準確率，應(yīng)使更多的節(jié)點加入監(jiān)測，但不能監(jiān)測到目標的節(jié)點仍采取節(jié)能機制，避免不必要的能耗。因此，在保證監(jiān)測準確率的同時，又能降低節(jié)點的能耗，本文采用動態(tài)分簇的拓撲結(jié)構(gòu)。

3 動態(tài)分簇

3.1 雙層環(huán)結(jié)構(gòu)動態(tài)簇

在構(gòu)建動態(tài)簇前，先對網(wǎng)絡(luò)進行初始化。分為兩階段：第一階段，將節(jié)點都設(shè)為等待狀態(tài)，sink節(jié)點以最大功率進行廣播，給定合適的閾值，若節(jié)點收到的信號強度大于閾值，則進入工作狀態(tài)并置q為1，向sink節(jié)點報告其ID和剩余能量，sink節(jié)點將這些信息登記到sink候選簇頭表中(表2)；反之，則進入休眠狀態(tài)。第二階段，工作狀態(tài)的節(jié)點調(diào)整通信功率至一跳范圍距離(表3)，進行消息廣播，收到消息的節(jié)點進入工作狀態(tài)，并將其ID和剩余能量回傳，同時調(diào)整通信功率至一跳范圍距離，進行消息廣播，鄰居節(jié)點互相登記信息到鄰居節(jié)點信息表。

表2 sink節(jié)點候選簇頭表

雙層環(huán)結(jié)構(gòu)動態(tài)簇的構(gòu)建分為以下步驟：

1)等待就緒。目標出現(xiàn)在追蹤區(qū)域之前，節(jié)點以等待狀態(tài)監(jiān)測網(wǎng)絡(luò)中可能出現(xiàn)的移動目標。

2)構(gòu)建內(nèi)層環(huán)結(jié)構(gòu)。當(dāng)目標進入追蹤區(qū)域后，所有能監(jiān)測到目標出現(xiàn)的節(jié)點進入正常工作狀態(tài)，加入內(nèi)層環(huán)集合，同時根據(jù)鄰居節(jié)點信息表，通知鄰居節(jié)點，如果鄰居節(jié)點已經(jīng)處于內(nèi)層環(huán)集合，則不作回應(yīng)。

3)構(gòu)建外層環(huán)結(jié)構(gòu)。收到通知的非內(nèi)層環(huán)集合的鄰居節(jié)點，首先調(diào)整至正常工作狀態(tài)，然后再將功率增大至κ倍，感知范圍增大。此時，如果鄰居節(jié)點能夠監(jiān)測到移動目標，則加入外層環(huán)集合，進入κ級別工作狀態(tài)；反之，鄰居節(jié)點降低功率，進入等待狀態(tài)。

表3 i節(jié)點一跳范圍內(nèi)鄰居節(jié)點信息表

如圖1所示，1所在的是外環(huán)，2所在的是內(nèi)環(huán)。虛線表示內(nèi)外環(huán)之間的一跳關(guān)系。

圖1 雙層環(huán)結(jié)構(gòu)動態(tài)簇

3.2 簇內(nèi)工作機制

簇內(nèi)成員節(jié)點監(jiān)測移動目標，實時向簇頭節(jié)點匯報數(shù)據(jù)和剩余能量。簇頭節(jié)點的工作主要是：

1)估計移動目標當(dāng)前位置。簇頭節(jié)點收到數(shù)據(jù)后，執(zhí)行數(shù)據(jù)處理，估算目標的位置。

2)更新簇內(nèi)信息。簇頭節(jié)點收到簇內(nèi)成員的能量信息后，將數(shù)據(jù)登記到臨時簇成員信息表(由成員ID和剩余能量組成)，每隔一段時間后，廣播臨時簇成員信息表數(shù)據(jù)，簇內(nèi)成員收到數(shù)據(jù)后，查詢臨時簇成員信息表，在鄰居節(jié)點信息表中更新此鄰居節(jié)點信息。

3)向sink節(jié)點傳送數(shù)據(jù)。簇頭節(jié)點通過單跳或多跳的路由方式[16]將目標位置數(shù)據(jù)和能量信息發(fā)送到sink節(jié)點， sink節(jié)點收到信息后，查詢sink節(jié)點候選簇頭信息表，如果存在此簇頭節(jié)點信息，則更新sink節(jié)點候選簇頭信息表；否則只接收位置數(shù)據(jù)。

3.3 分簇動態(tài)更新

隨著目標的隨機移動或追蹤區(qū)域的改變，簇結(jié)構(gòu)也發(fā)生變化，因此動態(tài)簇需要定期更新，主要考慮以下三方面：新監(jiān)測到移動目標的節(jié)點加入、不能監(jiān)測到移動目標的節(jié)點退出和簇頭節(jié)點移交。

3.3.1 新節(jié)點加入動態(tài)簇

目標在不停地移動，追蹤區(qū)域內(nèi)處于等待狀態(tài)的節(jié)點會監(jiān)測到目標，將這些節(jié)點加入動態(tài)簇。

對于任意一個非簇內(nèi)節(jié)點i，即i?Cdyn，當(dāng)目標進入感知范圍內(nèi)，節(jié)點i發(fā)送加入動態(tài)簇的廣播請求REQin。等待Δt時間后，如果收到簇頭節(jié)點j的同意信息ANSin，則節(jié)點i加入簇Cj，簇頭節(jié)點j將節(jié)點i信息登記到臨時簇成員信息表；如果沒有收到任何信息，則進入構(gòu)建動態(tài)簇的步驟。節(jié)點i根據(jù)鄰居節(jié)點信息表，通知一跳范圍內(nèi)的鄰居節(jié)點k，節(jié)點k進入κ級別工作狀態(tài)，如果能監(jiān)測到移動目標，則申請加入簇Cj，否則進入等待狀態(tài)。

新節(jié)點加入動態(tài)簇算法如算法2所示。

算法1intJoin(i,j)算法。

輸入：節(jié)點i，當(dāng)前簇頭節(jié)點j的動態(tài)簇Cj。 輸出：節(jié)點i加入Cj。

1)

/*Si表示節(jié)點i是否監(jiān)測到目標：值0表示未監(jiān)測到，值1表示監(jiān)測到；i.id、i.energy分別為節(jié)點i的編號和剩余能量；Cdyn為動態(tài)簇；T_CM為臨時簇成員信息表*/

2)

IfSi=1

3)

NodeisendREQinto sink nodej

4)

Wait for Δttime

5)

If nodeireceive theANSinfrom sinkj

6)

Then

7)

Cj=Cj+i

//加入動態(tài)簇Cj

8)

Sinknodejrecordi.id,i.energyto T_CM

9)

Return 1

10)

Else

11)

Create a dynamic cluster

12)

Return 0

13)

End

14)

End

算法2 新節(jié)點加入動態(tài)簇算法。

輸入：移動的目標、新節(jié)點和動態(tài)簇。 輸出：新節(jié)點加入動態(tài)簇。

1)

//i.state為節(jié)點i的狀態(tài)

2)

Foreachnodei(i?Cdyn)

3)

Join(i,j)

//節(jié)點i加入動態(tài)簇成功或構(gòu)建動態(tài)簇

4)

Nodeiinform neighbors in T_NET

5)

For eachkofi’s neighbors

6)

k.state←κ_work

//進入κ級別工作狀態(tài)

7)

If(Join(k,j)==0)

8)

k.state←wait

9)

End

10)

End

11)

End

3.3.2 失效節(jié)點退出動態(tài)簇

處于工作狀態(tài)的簇內(nèi)節(jié)點，當(dāng)目標移出其感知范圍，不能監(jiān)測到移動目標，這些節(jié)點退出動態(tài)簇。

對于任意一個簇內(nèi)節(jié)點i，即i∈Cdyn,當(dāng)目標移出其感知范圍，向簇頭j發(fā)送退出動態(tài)簇的請求REQout。簇頭節(jié)點j收到請求后，在臨時簇成員信息表中刪除相關(guān)信息，返回同意信息ANSout。節(jié)點i收到同意信息后，進入等待狀態(tài)，退出簇Cj；如果等待Δt時間后，沒有收到信息，則自動退出簇Cj。

失效節(jié)點退出動態(tài)簇算法如算法3所示。

算法3 失效節(jié)點退出動態(tài)簇算法。

輸入：移動的目標，動態(tài)簇Cj。 輸出：失效節(jié)點退出動態(tài)簇。

1)

ForeachnodeiinCj,i∈Cdyn:

2)

IfSi=0

3)

SendREQoutto sink nodej

4)

If sink nodejreceive theREQout

5)

Delete the items ofifrom T_CM

6)

Sink nodejsend backANSoutto nodei

7)

End

8)

IfnodeireceivetheANSout

9)

Then

10)

i.state←wait

11)

Cj=Cj-i

//節(jié)點i退出

12)

Else

13)

WaitforΔttime

14)

Cj=Cj-i

15)

End

16)

End

17)

End

3.3.3 簇頭節(jié)點移交

簇頭節(jié)點可能因為監(jiān)測不到目標而失效，使整個動態(tài)簇失效，導(dǎo)致追蹤結(jié)束，因此，簇頭節(jié)點的移交是非常重要。對于目前以i為簇頭的動態(tài)簇Ci中：

1)新加入簇的節(jié)點j，簇頭節(jié)點i查詢sink節(jié)點的候選簇頭信息表。如果節(jié)點j屬于sink候選簇頭集合，則選擇節(jié)點j為新的簇頭。節(jié)點i將所有信息移交給簇頭節(jié)點j，然后作為簇內(nèi)成員節(jié)點繼續(xù)工作。簇頭節(jié)點j向簇內(nèi)成員廣播簇頭信息。至此，動態(tài)簇成為以節(jié)點j為簇頭的簇Cj。

2)如果節(jié)點j不屬于sink候選簇頭集合，則節(jié)點i繼續(xù)作為簇頭。同時，簇頭節(jié)點i將節(jié)點j登記到簇內(nèi)候選簇頭信息表中。當(dāng)簇頭節(jié)點i不能監(jiān)測到目標時，立即查找簇內(nèi)候選簇頭信息表，選擇剩余能量Ek(0

簇頭節(jié)點移交算法如算法4所示。

算法4 簇頭節(jié)點移交算法。

輸入：移動的目標、動態(tài)簇Ci。 輸出：失效節(jié)點退出動態(tài)簇。

1)

/*CM為簇內(nèi)成員，CH為簇頭；T_S_CH為sink節(jié)點候選簇頭表；T_CM_CH為簇內(nèi)候選簇頭信息表*/

2)

//情況1：選取新節(jié)點為簇頭節(jié)點

3)

Instageone：

4)

ForeachnewCMjinCi(j∈Cdyn)：

5)

Ifj∈T_S_CH

6)

Then

7)

Nodejis elected to the CH

8)

Nodeisend T_CM，T_CM_CH to nodej

9)

Ci←Cj

//動態(tài)簇變?yōu)镃j

10)

CHjbroadcast the message inCj

11)

Else

12)

CH record nodejto the T_CM_CH

13)

End

14)

End

15)

//情況2：選取簇內(nèi)候選簇頭里的節(jié)點為簇頭

16)

In stage two：

17)

IfSi=0

18)

Choose nodekfor the CH from T_CM_CH whose energy is the most

19)

Nodeisend T_CM，T_CM_CH to nodek

20)

i.state←wait

21)

Ck←Ci

//動態(tài)簇變?yōu)镃k

22)

Ck=Ck-i

23)

CHkbroadcast the message inCk

24)

End

分簇動態(tài)更新如圖2所示，虛線圈是前一個時刻的簇情況，實線圈是當(dāng)前時刻的簇情況。隨著目標的移動，節(jié)點1，2，3和4失效，退出了動態(tài)簇。節(jié)點5加入了動態(tài)簇，并通知一跳范圍內(nèi)的三個鄰居節(jié)點，進入κ級別工作狀態(tài)。

圖2 動態(tài)簇更新示意圖

4 基于環(huán)狀分簇的目標追蹤技術(shù)

4.1 基于功率級別的質(zhì)心定位算法

質(zhì)心定位算法將質(zhì)心作為移動目標的位置，容易實現(xiàn)且成本低。但在本文的應(yīng)用場景中，各節(jié)點與目標之間距離差異較大，節(jié)點能量也會影響定位精確度，針對這些問題，在質(zhì)心定位算法上改進，提出了基于功率級別的質(zhì)心定位算法。

定義1 質(zhì)心O(x,y)。規(guī)則多邊形的幾何中心稱為質(zhì)心。假設(shè)一個規(guī)則多邊形的頂點坐標為(x1,y1)，(x2,y2)，…，(xn,yn)，則：

(1)

定義2 內(nèi)環(huán)集合SIR(Inner Ring Set, IRS)。對于任意的節(jié)點i，i∈Cdyn，若節(jié)點i主動監(jiān)測到移動目標，則i∈SIR，SIR?Cdyn。

定義3 外環(huán)集合SOR(Outer Ring Set, ORS)。對于任意的節(jié)點i，i∈Cdyn，若節(jié)點i被動進入工作狀態(tài)，即節(jié)點j通知節(jié)點i進入工作狀態(tài)，j∈SIR，則i∈SOR，SOR?Cdyn。

外環(huán)節(jié)點的功率是內(nèi)環(huán)節(jié)點的功率的κ倍，由于功率的不同，內(nèi)外環(huán)節(jié)點的感知范圍和初始發(fā)射能量也不同。對質(zhì)心定位算法進行改進，結(jié)合功率因素，提出基于功率級別的質(zhì)心定位算法。公式如下：

(2)

其中：k是內(nèi)環(huán)節(jié)點的數(shù)目，q是外環(huán)節(jié)點的數(shù)目，β是內(nèi)外環(huán)節(jié)點的權(quán)值，由于內(nèi)環(huán)節(jié)點離移動目標更近，內(nèi)環(huán)節(jié)點得出的位置坐標占有較大的權(quán)重，所以β取值范圍：1/2≤β<1。式(2)還可以進一步簡化，令α=β/(1-β)，可以得到：

基于功率級別的質(zhì)心定位(CLPL)算法如算法5所示。

算法5 基于功率級別的質(zhì)心定位算法。

輸入：內(nèi)環(huán)集合SIR，外環(huán)集合SOR，動態(tài)簇Cdyn。 輸出：目標位置。

1)

//CH為簇頭；μIR存放內(nèi)環(huán)集合結(jié)果； μOR存放外環(huán)集合結(jié)果；

2)

ForeachnodeiinSIR

3)

CHcalculateasbelow

4)

μIRx=μIRx+xi

5)

μIRy=μIRy+yi

6)

k++

7)

End

8)

ForeachnodejinSOR

9)

CHcalculateasbelow

10)

μORx=μORx+xj

11)

μORy=μORy+yj

12)

q++

13)

End

14)

CHgetthetarget’sposition:

//結(jié)合兩層集合，得出目標位置

4.2 隨機性定位算法

Trace=(TS(1),TS(2),…,TS(n))

(4)

其中，TS(i)∈TSet，序列Trace是有序的，代表移動路徑，起點是TS(1)，終點是TS(n)。

在基于功率級別定位算法中，簇頭節(jié)點持續(xù)性定位，不間斷計算位置信息，并傳送給sink節(jié)點，能耗較大。本文提出了改進的算法——隨機性定位算法，簇頭節(jié)點能夠隨機性定位移動目標。

無線傳感器網(wǎng)絡(luò)中存在著時空相關(guān)性[17]，可以根據(jù)目標移動的相關(guān)性，隨機性定位。隨機不是無規(guī)律狀態(tài)，而是隨目標情況而定。例如某一時刻，目標移動緩慢，則位置信息可以默認為上一時刻的信息，簇頭不進行定位；而在目標移動較快時，簇頭開始不間斷定位。目標的移動相關(guān)性可以通過動態(tài)簇的改變獲取，動態(tài)簇的改變體現(xiàn)在簇內(nèi)成員節(jié)點加入或退出。在此，給出一個動態(tài)簇改變的狹義定義。

定義5ε-threshold簇改變。在一個時間序列T{t1,t2,…,tn}中，在Δt時間段內(nèi)，在簇頭沒有移交的情況下，有τ1個節(jié)點退出動態(tài)簇，有τ2個節(jié)點加入動態(tài)簇，如果τ1+τ2>ε，則認為動態(tài)簇改變。

根據(jù)定義5，提出隨機性定位算法如下：

1)在簇頭節(jié)點中定義一個計數(shù)值count，置初值為0。

2)在簇頭節(jié)點沒有移交情況下，有簇內(nèi)成員節(jié)點退出，count++；同樣，新節(jié)點加入動態(tài)簇，count++。

3)如果count>ε，則認為動態(tài)簇改變，簇頭節(jié)點進行定位計算，并將相關(guān)信息發(fā)送給sink節(jié)點。同時，置count為0。

4)如果簇頭節(jié)點進行了移交，則動態(tài)簇改變，新的簇頭節(jié)點進行定位計算，并將相關(guān)信息發(fā)送給sink節(jié)點，同時，置count為0。

隨機性定位算法如算法6所示。

算法6 隨機性定位算法。

輸入：移動的目標，動態(tài)簇Cdyn；給定的閾值ε；CH簇頭節(jié)點。 輸出：目標位置。

1)

//計數(shù)器count

2)

While(there is node join into theCdynor exit theCdyn)

3)

count++

4)

Ifcount>ε

5)

CHexecuteCLPL

6)

CHsendresulttosinknode

7)

count=0

8)

End

9)

If CH is changed

10)

New CH execute CLPL

11)

New CH send result to sink node

12)

count=0

13)

End

14)

End

4.3 算法分析

4.3.1 能耗分析

根據(jù)能耗模型[18]，本文假設(shè)追蹤區(qū)域中節(jié)點的平均分布密度為ρ，則節(jié)點感知區(qū)域內(nèi)的節(jié)點個數(shù)為ρπr2。內(nèi)環(huán)節(jié)點在監(jiān)測目標過程中，單位時間消耗的能量為δ；外環(huán)節(jié)點單位時間消耗的能量為κδ。

由于一個分簇內(nèi)，節(jié)點之間的距離基本上在一跳之內(nèi)，所以簇內(nèi)成員節(jié)點與簇頭通信的能耗基本上忽略不計。在單位時間內(nèi)，簇頭節(jié)點與sink節(jié)點通信消耗的能量為ES。

因此，每次分簇定位目標位置所需要的總能耗為：

E=δρπr2+κδρπr2+ES

(5)

4.3.2 能耗均衡性分析

從動態(tài)分簇和數(shù)據(jù)傳輸兩個階段分別分析能耗均衡性。

在動態(tài)分簇階段，為了能夠?qū)σ苿幽繕诉M行實時監(jiān)測，本文提出了分簇動態(tài)更新算法。隨著目標移動，分簇結(jié)構(gòu)動態(tài)更新，必然會使整個網(wǎng)絡(luò)達到良好的能耗均衡性。在網(wǎng)絡(luò)初始化過程中，為了保護低能量節(jié)點，sink節(jié)點備選了通信良好的候選簇頭，避免產(chǎn)生多余的跳距，消耗過多能量。

在數(shù)據(jù)傳輸階段，處于內(nèi)環(huán)節(jié)點監(jiān)測負擔(dān)比較重，能耗較高。為了均衡分簇的能量結(jié)構(gòu)，外環(huán)節(jié)點工作功率調(diào)為κ級別。在基于功率級別的定位算法中，外環(huán)節(jié)點分擔(dān)內(nèi)環(huán)監(jiān)測的任務(wù)，均衡整個分簇的能量結(jié)構(gòu)，同時擴大了對移動目標的追蹤范圍，避免因目標移動較快而丟失的情況。

4.3.3 網(wǎng)絡(luò)延遲和監(jiān)測概率分析

目標監(jiān)測延遲定義為在網(wǎng)絡(luò)中一個移動目標o從發(fā)生到被監(jiān)測到的時間長度的期望值。目標監(jiān)測概率定義為在網(wǎng)絡(luò)中一個移動目標o至少被一個工作節(jié)點監(jiān)測到的概率。

在LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議[16]中，假設(shè)在網(wǎng)絡(luò)生命周期里，事件發(fā)生概率相等且持續(xù)時間大于(m-1)×T(T表示LEACH協(xié)議運行一輪的時間長度，m表示節(jié)點狀態(tài)進行一個調(diào)度循環(huán)所經(jīng)需的輪數(shù))。若一個事件e發(fā)生在監(jiān)測區(qū)域中某點p，點p可以被s個傳感器節(jié)點所覆蓋。在此網(wǎng)絡(luò)場景下，一個事件的監(jiān)測延遲受到三個因素影響：時間長度T、輪數(shù)m和覆蓋節(jié)點數(shù)s。如果T增大或m增加，事件平均監(jiān)測延遲也增加；相反，點數(shù)s增加，事件平均監(jiān)測延遲就減少。

本文提出的基于環(huán)狀分簇移動目標追蹤模型，與上述模型類似。唯一區(qū)別的是，如果移動目標的瞬時速度v較快，分簇定位到目標的概率較低，目標定位的時間較長。

5 實驗與分析

5.1 實驗環(huán)境

為了觀察基于環(huán)狀動態(tài)分簇的目標追蹤技術(shù)的執(zhí)行效率，本文通過Matlab仿真平臺進行仿真實驗。

目標在剛進入追蹤區(qū)域時，定位誤差會比較大，這是不可避免的情況，在實驗仿真中，不考慮目標進入或退出追蹤區(qū)域的情況。假設(shè)移動目標是一個圓點，不考慮其大小?；緟?shù)設(shè)置如表4所示。

表4 仿真參數(shù)設(shè)置

在100m×100m的二維追蹤區(qū)域內(nèi)，隨機均勻部署了100個傳感器節(jié)點，在追蹤區(qū)域內(nèi)，模擬目標隨機移動的一種路徑，軌跡方程為：

Trace(x,y,t)=

(6)

其中，參數(shù)t從0.01增至2，間隔為0.01。

5.2 實驗結(jié)果與分析

本文從環(huán)狀分簇結(jié)構(gòu)和追蹤算法兩方面進行實驗仿真，環(huán)狀結(jié)構(gòu)方面包括：動態(tài)簇與靜態(tài)簇比較、功率κ值分析及速度對追蹤的影響；追蹤算法方面包括：權(quán)值α比較與定位算法誤差。

5.2.1 動態(tài)簇與靜態(tài)簇比較

圖3展示了本文的動態(tài)簇模型和一種靜態(tài)簇模型——網(wǎng)格模型[19]在生存時間上對比結(jié)果。實驗假定，當(dāng)網(wǎng)絡(luò)中能夠工作的節(jié)點數(shù)小于總節(jié)點數(shù)一半時，整個網(wǎng)絡(luò)的生命周期完結(jié)。靜態(tài)簇是一種在網(wǎng)絡(luò)運作前選好簇頭的模型，每一個簇的地位是平等的。

由圖3可知，動態(tài)簇模型在生存周期的長度上顯然要好于靜態(tài)簇，動態(tài)簇比靜態(tài)簇能夠節(jié)省更多的能量消耗。從圖3可以看出，在相同的追蹤區(qū)域內(nèi)，部署的節(jié)點越多，網(wǎng)絡(luò)的生存時間越長；在相同節(jié)點數(shù)情況下，動態(tài)簇的生存時間是明顯長于靜態(tài)簇。與靜態(tài)簇相比，動態(tài)簇的平均網(wǎng)絡(luò)周期延長了22.73%。

5.2.2 功率κ值分析

如圖4所示，節(jié)點的功率級別不一樣，感知半徑也不同，那么感知覆蓋的區(qū)域也不一樣，定位的精確度也會受到影響。在κ值小于1.7時，移動目標的定位平均誤差隨著功率級別κ值增大而降低；在κ值大于1.7時，平均誤差隨著功率級別κ值呈增大趨勢。在κ值為1.1的時候，誤差值有個上升，這是由于外環(huán)節(jié)點的加入，此時，外環(huán)節(jié)點的數(shù)目相對于內(nèi)環(huán)節(jié)點來說比較少，定位結(jié)果以內(nèi)環(huán)節(jié)點為主導(dǎo)。隨著功率級別κ值增大，越來越多的外環(huán)節(jié)點加入分簇，定位結(jié)果更具有均衡性；在κ值增至1.7之后，外環(huán)節(jié)點的數(shù)目較多，從而起到主導(dǎo)作用，目標定位誤差增大。

圖3 動態(tài)簇與靜態(tài)簇生存時間

圖4 功率級別κ與追蹤誤差關(guān)系

κ值對追蹤準確性有較大的影響，當(dāng)取值不合理時，誤差甚至超過1.2 m。在κ值為1時，內(nèi)外環(huán)節(jié)點具有相同的能量，此時的定位誤差為1.2 m，產(chǎn)生較大的誤差，對比κ值為1.7時，誤差不到0.6 m，在可接受范圍內(nèi)，可見κ值對定位誤差有較大影響；當(dāng)κ值超過2時，誤差超過1 m，對定位精度產(chǎn)生很大的影響。

因此，不是功率級別κ越大，移動目標的定位越準確；但功率級別越大，分簇的結(jié)構(gòu)越大，移動目標的丟失率越小。

5.2.3 速度對追蹤的影響

如圖5所示，對于環(huán)狀分簇和非環(huán)狀分簇模型，當(dāng)目標的移動速度越大，移動目標追蹤的丟失率越大，準確度越低。在目標的移動速度相等時，環(huán)狀分簇模型比非環(huán)狀分簇模型丟失率低，追蹤的準確度高。當(dāng)目標的移動速度低于4m/s的時候，采用環(huán)狀分簇模型對移動目標追蹤，丟失率可以忽略不計；高于4m/s時，丟失率急劇增加。與非環(huán)狀簇相比，在速度小于4m/s時丟失率降低了61.09%，速度大于4m/s時丟失率降低了34.02%，總體平均降低了40.79%。

由此可知，基于環(huán)狀分簇的目標追蹤算法，目標的丟失率較低，可以減少因目標丟失而重構(gòu)分簇帶來的能耗。

圖5 目標移動速度與丟失率關(guān)系

5.2.4 定位算法的誤差

圖6顯示，CLPL算法和基于接受信號強度值(ReceivedSignalStrengthIndicator,RSSI)定位算法[20]誤差比較。目標在追蹤區(qū)域移動時間為40s，分簇每秒對移動目標定位一次。CLPL算法得出的定位誤差，是外環(huán)節(jié)點為1倍功率級別的情況。最小誤差是0.2m，最大誤差是3.1m，平均誤差是1.29m?；赗SSI定位算法，最小誤差是0.8m，最大誤差是1.6m，平均誤差是1.16m。

由此可知，基于RSSI的定位算法，路徑精確度稍微高點，誤差值比較穩(wěn)定。但是，基于RSSI的定位算法，需要獲取詳細精確的距離與角度信息，對硬件的要求比較高。CLPL算法，對硬件要求可以忽略不計，相較于基于RSSI定位算法1.16m的誤差，1.29m的誤差也是比較樂觀的。

圖6 CLPL與RSSI目標定位誤差

5.2.5 權(quán)值α與平均誤差分析

圖7顯示了在外環(huán)節(jié)點感知半徑設(shè)為9.9 m的情況下，權(quán)值α對應(yīng)移動目標定位的平均誤差值。如圖7所示，α值在2～2.5，移動目標定位的平均誤差值較小。由式(3)可知，α值較大，得到的定位結(jié)果偏向于內(nèi)環(huán)節(jié)點；α較小，得到的定位結(jié)果偏向于外環(huán)節(jié)點。當(dāng)α值為1時，內(nèi)外環(huán)節(jié)點具有相同的權(quán)重，此時誤差較大，接近1.4 m，可見不合適的α值，對定位精確度影響較大。

由此可知，α值直接影響移動目標的定位準確度，合適的α值很重要。

5.2.6 隨機性定位算法對平均誤差的影響

圖8展示了隨機性定位算法對目標追蹤平均誤差的影響。當(dāng)ε值為0的時候，隨機性定位算法未介入追蹤算法，此時平均誤差即為CLPL算法得出的定位誤差，為1.29 m；當(dāng)ε值大于0的時候，隨機性定位算法開始介入追蹤算法，隨著ε值增大，平均誤差也在增大，以ε值為2為分界點，在之前平均誤差增大趨勢較緩，之后誤差增大趨勢較陡。

由此可知，設(shè)定合適的ε閾值，對于追蹤的影響還是比較明顯的，需尋求能耗代價與追蹤精確度的折中點。

圖7 權(quán)值α對應(yīng)的平均誤差

圖8 ε值與平均誤差關(guān)系

6 結(jié)語

本文提出雙層環(huán)狀動態(tài)分簇的拓撲模型，并給出了動態(tài)分簇的更新算法，以解決目標移動隨機性很大和分簇的監(jiān)測任務(wù)較重等問題。在質(zhì)心定位算法的基礎(chǔ)上，提出了基于功率級別的質(zhì)心定位算法?？紤]到網(wǎng)絡(luò)的能耗問題，對基于功率級別的質(zhì)心定位算法進行改進，提出了隨機性定位算法。最后通過仿真實驗驗證了基于環(huán)狀動態(tài)分簇的移動目標追蹤技術(shù)，在追蹤準確度、能耗和丟失率等方面的優(yōu)勢。

References)

[1] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:135-155.(SUN L M, LI J Z, CHEN Y, et al.Wireless Sensor Network [M].Beijing: Tsinghua University Press, 2005:135-155.)

[2] BRANCH J W, GIANNELLA C, SZYMANSKI B, et al.In-network outlier detection in wireless sensor networks [J].Knowledge and Information Systems, 2013, 34(1): 23-54.

[3] MO L, HE Y, LIU Y, et al.Canopy closure estimates with GreenOrbs: sustainable sensing in the forest [C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems.New York: ACM, 2009: 99-112.

[4] HE T, KRISHNAMURTHY S, LUO L, et al.VigilNet: an integrated sensor network system for energy efficient surveillance [J].ACM Transactions on Sensor Networks, 2006, 2(1):1-38.

[5] HACKMANN G, GUO W, YAN G, et al.Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 63-72.

[6] MECHITOV K, SUNDRESH S, KWON Y, et al.Cooperative tracking with binary-detection sensor networks [C]// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.New York: ACM, 2003: 332-333.

[7] KIM W, MECHITOV K, CHOI J Y, et al.On target tracking with binary proximity sensors [C]// IPSN 2005: Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks.Piscataway, NJ: IEEE, 2005: 301-308.

[8] ZHAO F, SHIN J, REICH J.Information-driven dynamic sensor collaboration for tracking applications [J].IEEE Signal Processing Magazine, 2002, 19(2): 61-72.

[9] ZHONG Z, ZHU T, WANG D, et al.Tracking with unreliable node sequences [C]// INFOCOM 2009: Proceedings of the 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2009: 1215-1223.

[10] WANG Z J, BULUT E, SZYMANSKI B K.Distributed energy-efficient target tracking with binary sensor networks [J].ACM Transactions on Sensor Networks, 2010, 6(4): Article No.32.

[11] KHALIL E A, ATTEA B A.Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks [J].Swarm and Evolutionary Computation, 2011, 1(4): 195-203.

[12] LIN K W, HSIEH M H, TSENG V S.A novel prediction-based strategy for object tracking in sensor networks by mining seamless temporal movement patterns [J].Expert Systems with Applications, 2010, 37(4):2799-2807.

[13] SUN K, NING P, WANG C.Secure and resilient time synchronization in wireless sensor networks [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security.New York: ACM, 2006: 264-277.

[14] JEONG J, HWANG T, HE T, et al.MCTA: target tracking algorithm based on minimal contour in wireless sensor networks [C]// INFOCOM 2007: Proceedings of the 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2007: 2371-2375.

[15] VICAIRE P, HE T, CAO Q, et al.Achieving long-term surveillance in VigilNet [J].ACM Transactions on Sensor Networks, 2009, 5(1): Article No.39.

[16] TYAGI S, KUMAR N.A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks [J].Journal of Network and Computer Applications, 2013, 36(2): 623-645.

[17] BROOKS R R, RAMANATHAN P, SAYEED A M.Distributed target classification and tracking in sensor networks [J].Proceedings of IEEE, 2003, 91(8):1163-1171.

[18] YANG H, SIKDAR B.A protocol for tracking mobile targets using sensor networks [C]// Proceedings of the 2003 IEEE International Workshop on Sensor Network Protocols and Applications.Piscataway, NJ: IEEE, 2003: 71-81.

[19] BULUSU N, ESTRIN D, GIROD L, et al.Scalable coordination for wireless sensor networks: self-configuring localization systems [C]// ISCTA 2001: Proceedings of the 6th International Symposium on Communication Theory and Applications.Ambleside, UK: [s.n.], 2001: 1-6.

[20] 陳維克,李文鋒,首珩,等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2006,30(2):265-268.(CHEN W K, LI W F, SHOU H, et al.Weighted centroid localization algorithm based on RSSI for wireless sensor networks [J].Wuhan Science University of Technology (Transportation Science and Engineering), 2006, 30(2): 265-268.)

This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Science and Technology Support Program (2013BAB06B04), the Technology Project of China Huaneng Group Company Headquarters (HNKJ13-H17-04), the Science and Technology Project of Yunnan Province (2014GA007), the Special Fund for Basic Scientific Research of Central Universities (2015B22214).

BAO Wei, born in 1990, M.S.candidate.His research interests include wireless sensor network, distributed computing, parallel processing.

MAO Yingchi, born in 1976, Ph.D., associate professor.Her research interests include distributed computing and parallel processing, distributed data management.

WANG Longbao, born in 1977, lecturer.His research interests include intelligent data processing, project management.

CHEN Xiaoli, born in 1993, M.S.candidate.Her research interests include wireless sensor network, distributed computing.

Moving target tracking scheme based on dynamic clustering

BAO Wei, MAO Yingchi*, WANG Longbao, CHEN Xiaoli

(CollegeofComputerandInformation,HohaiUniversity,NanjingJiangsu211100,China)

Focused on the issues of low accuracy, high energy consumption of target tracking network and short life cycle of network in Wireless Sensor Network (WSN), the moving target tracking technology based on dynamic clustering was proposed.Firstly, a Two-Ring Dynamic Clustering (TRDC) structure and the corresponding TRDC updating methods were proposed; secondly, based on centroid localization, considering energy of node, the Centroid Localization based on Power-Level (CLPL) algorithm was proposed; finally, in order to further reduce the energy consumption of the network, the CLPL algorithm was improved, and the random localization algorithm was proposed.The simulation results indicate that compared with static cluster, the life cycle of network increased by 22.73%; compared with acyclic cluster, the loss rate decreased by 40.79%; there was a little difference from Received Signal Strength Indicator (RSSI) algorithm in accuracy.The proposed technology can effectively ensure tracking accuracy and reduce energy consumption and loss rate.

Wireless Sensor Network (WSN); two-ring clustering; target tracking; dynamic cluster; centroid localization

2016-07-20;

2016-08-05。

國家自然科學(xué)基金資助項目(U1301252)；國家科技支撐計劃項目(2013BAB06B04)；中國華能集團公司總部科技項目(HNKJ13-H17-04)；云南省科技計劃項目(2014GA007)；中央高校基本科研業(yè)務(wù)費專項資金資助項目(2015B22214)。

包威(1990—)，男，江蘇淮安人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、分布式計算、并行處理； 毛鶯池(1976—)，女，上海人，副教授，博士，CCF會員，主要研究方向：分布計算與并行處理、分布式數(shù)據(jù)管理； 王龍寶(1977—)，男，江蘇鹽城人，講師，主要研究方向：智能數(shù)據(jù)處理、項目管理； 陳小麗(1993—)，女，河南洛陽人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、分布式計算。

1001-9081(2017)01-0065-08

10.11772/j.issn.1001-9081.2017.01.0065

TP393.02

A