基于動態分簇的移動目標追蹤方法

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

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

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

基于動態分簇的移動目標追蹤方法

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

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

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

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

無線傳感器網絡；雙層環狀；目標追蹤；動態簇；質心定位

0 引言

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

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

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

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

2)在質心定位算法的基礎上進行改進，將節點的能量考慮在內，提出了基于功率級別的質心定位(Centroid Localization based on Power-Level, CLPL)算法；為了減少網絡的能耗，進一步優化CLPL算法，結合目標移動的相關性，提出了隨機性定位算法。

3)通過實驗，得出基于環狀動態分簇的移動目標追蹤技術，在追蹤準確度、能耗和丟失率等方面具有優勢。

1 研究現狀

傳感器監測用戶感興趣的事件，節點間相互協作，計算出移動事件的軌跡，回傳給基站。基站根據計算出來的軌跡，對移動事件進行追蹤。目前，無線傳感器網絡的移動目標追蹤技術一般可以歸納為：

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

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

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

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

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

2 系統模型

目標在區域內移動，能夠被傳感器節點監測的區域稱為追蹤區域。為了簡化起見，本文對無線傳感器網絡模型作出了如下假設：

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

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

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

4)節點的感知功率級別是可調的，感知半徑隨功率級別動態變化[14]；

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

表1 節點信息表

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

3 動態分簇

3.1 雙層環結構動態簇

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

表2 sink節點候選簇頭表

雙層環結構動態簇的構建分為以下步驟：

1)等待就緒。目標出現在追蹤區域之前，節點以等待狀態監測網絡中可能出現的移動目標。

2)構建內層環結構。當目標進入追蹤區域后，所有能監測到目標出現的節點進入正常工作狀態，加入內層環集合，同時根據鄰居節點信息表，通知鄰居節點，如果鄰居節點已經處于內層環集合，則不作回應。

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

表3 i節點一跳范圍內鄰居節點信息表

如圖1所示，1所在的是外環，2所在的是內環。虛線表示內外環之間的一跳關系。

圖1 雙層環結構動態簇

3.2 簇內工作機制

簇內成員節點監測移動目標，實時向簇頭節點匯報數據和剩余能量。簇頭節點的工作主要是：

1)估計移動目標當前位置。簇頭節點收到數據后，執行數據處理，估算目標的位置。

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

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

3.3 分簇動態更新

隨著目標的隨機移動或追蹤區域的改變，簇結構也發生變化，因此動態簇需要定期更新，主要考慮以下三方面：新監測到移動目標的節點加入、不能監測到移動目標的節點退出和簇頭節點移交。

3.3.1 新節點加入動態簇

目標在不停地移動，追蹤區域內處于等待狀態的節點會監測到目標，將這些節點加入動態簇。

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

新節點加入動態簇算法如算法2所示。

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

輸入：節點i，當前簇頭節點j的動態簇Cj。 輸出：節點i加入Cj。

1)

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

2)

IfSi=1

3)

NodeisendREQinto sink nodej

4)

Wait for Δttime

5)

If nodeireceive theANSinfrom sinkj

6)

Then

7)

Cj=Cj+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 新節點加入動態簇算法。

輸入：移動的目標、新節點和動態簇。 輸出：新節點加入動態簇。

1)

//i.state為節點i的狀態

2)

Foreachnodei(i?Cdyn)

3)

Join(i,j)

//節點i加入動態簇成功或構建動態簇

4)

Nodeiinform neighbors in T_NET

5)

For eachkofi’s neighbors

6)

k.state←κ_work

//進入κ級別工作狀態

7)

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

8)

k.state←wait

9)

End

10)

End

11)

End

3.3.2 失效節點退出動態簇

處于工作狀態的簇內節點，當目標移出其感知范圍，不能監測到移動目標，這些節點退出動態簇。

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

失效節點退出動態簇算法如算法3所示。

算法3 失效節點退出動態簇算法。

輸入：移動的目標，動態簇Cj。 輸出：失效節點退出動態簇。

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

//節點i退出

12)

Else

13)

WaitforΔttime

14)

Cj=Cj-i

15)

End

16)

End

17)

End

3.3.3 簇頭節點移交

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

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

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

簇頭節點移交算法如算法4所示。

算法4 簇頭節點移交算法。

輸入：移動的目標、動態簇Ci。 輸出：失效節點退出動態簇。

1)

/*CM為簇內成員，CH為簇頭；T_S_CH為sink節點候選簇頭表；T_CM_CH為簇內候選簇頭信息表*/

2)

//情況1：選取新節點為簇頭節點

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

//動態簇變為Cj

10)

CHjbroadcast the message inCj

11)

Else

12)

CH record nodejto the T_CM_CH

13)

End

14)

End

15)

//情況2：選取簇內候選簇頭里的節點為簇頭

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

//動態簇變為Ck

22)

Ck=Ck-i

23)

CHkbroadcast the message inCk

24)

End

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

圖2 動態簇更新示意圖

4 基于環狀分簇的目標追蹤技術

4.1 基于功率級別的質心定位算法

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

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

(1)

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

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

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

(2)

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

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

算法5 基于功率級別的質心定位算法。

輸入：內環集合SIR，外環集合SOR，動態簇Cdyn。 輸出：目標位置。

1)

//CH為簇頭；μIR存放內環集合結果； μOR存放外環集合結果；

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:

//結合兩層集合，得出目標位置

4.2 隨機性定位算法

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

(4)

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

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

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

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

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

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

2)在簇頭節點沒有移交情況下，有簇內成員節點退出，count++；同樣，新節點加入動態簇，count++。

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

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

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

算法6 隨機性定位算法。

輸入：移動的目標，動態簇Cdyn；給定的閾值ε；CH簇頭節點。 輸出：目標位置。

1)

//計數器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 能耗分析

根據能耗模型[18]，本文假設追蹤區域中節點的平均分布密度為ρ，則節點感知區域內的節點個數為ρπr2。內環節點在監測目標過程中，單位時間消耗的能量為δ；外環節點單位時間消耗的能量為κδ。

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

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

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

(5)

4.3.2 能耗均衡性分析

從動態分簇和數據傳輸兩個階段分別分析能耗均衡性。

在動態分簇階段，為了能夠對移動目標進行實時監測，本文提出了分簇動態更新算法。隨著目標移動，分簇結構動態更新，必然會使整個網絡達到良好的能耗均衡性。在網絡初始化過程中，為了保護低能量節點，sink節點備選了通信良好的候選簇頭，避免產生多余的跳距，消耗過多能量。

在數據傳輸階段，處于內環節點監測負擔比較重，能耗較高。為了均衡分簇的能量結構，外環節點工作功率調為κ級別。在基于功率級別的定位算法中，外環節點分擔內環監測的任務，均衡整個分簇的能量結構，同時擴大了對移動目標的追蹤范圍，避免因目標移動較快而丟失的情況。

4.3.3 網絡延遲和監測概率分析

目標監測延遲定義為在網絡中一個移動目標o從發生到被監測到的時間長度的期望值。目標監測概率定義為在網絡中一個移動目標o至少被一個工作節點監測到的概率。

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

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

5 實驗與分析

5.1 實驗環境

為了觀察基于環狀動態分簇的目標追蹤技術的執行效率，本文通過Matlab仿真平臺進行仿真實驗。

目標在剛進入追蹤區域時，定位誤差會比較大，這是不可避免的情況，在實驗仿真中，不考慮目標進入或退出追蹤區域的情況。假設移動目標是一個圓點，不考慮其大小。基本參數設置如表4所示。

表4 仿真參數設置

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

Trace(x,y,t)=

(6)

其中，參數t從0.01增至2，間隔為0.01。

5.2 實驗結果與分析

本文從環狀分簇結構和追蹤算法兩方面進行實驗仿真，環狀結構方面包括：動態簇與靜態簇比較、功率κ值分析及速度對追蹤的影響；追蹤算法方面包括：權值α比較與定位算法誤差。

5.2.1 動態簇與靜態簇比較

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

由圖3可知，動態簇模型在生存周期的長度上顯然要好于靜態簇，動態簇比靜態簇能夠節省更多的能量消耗。從圖3可以看出，在相同的追蹤區域內，部署的節點越多，網絡的生存時間越長；在相同節點數情況下，動態簇的生存時間是明顯長于靜態簇。與靜態簇相比，動態簇的平均網絡周期延長了22.73%。

5.2.2 功率κ值分析

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

圖3 動態簇與靜態簇生存時間

圖4 功率級別κ與追蹤誤差關系

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

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

5.2.3 速度對追蹤的影響

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

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

圖5 目標移動速度與丟失率關系

5.2.4 定位算法的誤差

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

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

圖6 CLPL與RSSI目標定位誤差

5.2.5 權值α與平均誤差分析

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

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

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

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

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

圖7 權值α對應的平均誤差

圖8 ε值與平均誤差關系

6 結語

本文提出雙層環狀動態分簇的拓撲模型，并給出了動態分簇的更新算法，以解決目標移動隨機性很大和分簇的監測任務較重等問題。在質心定位算法的基礎上，提出了基于功率級別的質心定位算法。考慮到網絡的能耗問題，對基于功率級別的質心定位算法進行改進，提出了隨機性定位算法。最后通過仿真實驗驗證了基于環狀動態分簇的移動目標追蹤技術，在追蹤準確度、能耗和丟失率等方面的優勢。

References)

[1] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,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的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報(交通科學與工程版),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。

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

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

1001-9081(2017)01-0065-08

10.11772/j.issn.1001-9081.2017.01.0065

TP393.02

A