基于自適應動態簇和預測機制的WSN目標跟蹤算法*

崔亞峰，史健芳

（太原理工大學信息工程學院，太原 030024）

基于自適應動態簇和預測機制的WSN目標跟蹤算法*

崔亞峰，史健芳*

（太原理工大學信息工程學院，太原 030024）

無線傳感器網絡由大量能量有限的傳感器節點組成，如何高效利用網絡中節點的能量是無線傳感器網絡用于目標跟蹤時研究的主要內容。合理構建動態簇可以有效降低網絡的能量消耗，延長網絡的生命周期，本文通過改進動態簇組建過程中簇頭的選舉和簇成員的征集過程，達到進一步節能的效果。其中，簇頭的選擇，綜合考慮節點的能量和節點離目標的距離兩個因素。簇成員的征集，同時考慮目標的移動速度和網絡中節點的分布情況。同時，引入有效的預測機制，通過避免盲目的喚醒網絡中的節點和降低跟蹤延遲，可以進一步增強網絡的跟蹤性能，使跟蹤過程更加有效和穩定。仿真結果表明本文算法在保證跟蹤精度的前提條件下，可以有效節省網絡中節點的能量。

無線傳感器網絡；目標跟蹤；動態簇；預測機制；節能

無線傳感器網絡（Wireless Sensor Network，WSN）是由部署在監測區域內大量的廉價傳感器節點通過無線通信方式形成的一個多跳自組織網絡［1］。與傳統網絡相比，無線傳感器網絡在目標跟蹤中的優勢明顯，它具有跟蹤可靠、及時、隱蔽、低成本、低功耗等特點［2］。但同時，由于無線傳感器網絡中的節點能量有限，所以如何降低網絡能量消耗，從而延長網絡的生命周期，是無線傳感器網絡用于目標跟蹤時重點研究的問題［3］。

動態簇是在監測目標的周圍形成的一個節點群，傳統的PDC算法［4］是采用固定半徑的動態簇結構來跟蹤目標。為了有效跟蹤目標，動態簇的半徑取值較大，這樣在整個跟蹤過程中，處于工作狀態的簇內節點數較多，能量消耗大。近年來，隨著對動態簇結構的研究，有些學者提出了動態簇半徑的自適應調整［5-6］，該算法簇半徑的調整只考慮到運動目標的移動速度，沒有考慮無線傳感器網絡中節點的分布密度，有可能使簇內節點太少，無法達到有效跟蹤［7］。同時，跟蹤目標時，沒有引入預測機制［8］或使用的預測機制不合理［9］，使網絡響應延遲，不利于目標的跟蹤。

本文對傳統的動態簇無線傳感器網絡目標跟蹤算法［10］進行改進，提出綜合考慮運動目標的運動速度和網絡中節點的分布情況構建動態簇，在跟蹤過程中簇結構的半徑根據目標的運動速度和網絡中節點的分布情況自適應調整，通過優化簇結構，從而提高網絡中能量的使用率。同時，引入預測算法，預測運動目標的移動軌跡，以便動態簇根據目標的預測軌跡，提前喚醒目標周圍監測半徑內的傳感器節點，準備監測目標。該算法模型簡單，計算量小，避免了盲目喚醒節點所造成的能量浪費，有效節省了節點的能量，同時降低了響應延遲，延長了網絡生命周期。

1 網絡的假設與初始狀態

1.1 本文中網絡的假設

為了簡化問題，不失一般性，本文對網絡做如下假設：

①目標區域節點之間為覆蓋連通的。

②所有節點都具有相同的能力，節點在網絡中的地位平等。

③節點具有定位能力，即每個節點能夠獲得自身的位置信息。

④節點有五種工作狀態：CH（Cluster_Header，簇頭狀態）、CM（Cluster_Member，簇成員狀態）、Idle（等待狀態）、Sleep（睡眠狀態）、Dead（死亡狀態），其中CH和CM狀態都屬于Work狀態。Work狀態是傳感器節點完全激活的狀態，具有感知信息、融合信息和傳輸信息的能力，因此，Work狀態的節點消耗能量最大；Idle狀態的節點只能感知信息，節點能耗很小；Sleep狀態的節點什么都不做，可以認為，處于該狀態的節點不消耗能量；處于Dead狀態的節點的能量已經耗盡，不能再繼續工作。

1.2 節點自身保存信息：

為了算法有效工作，節點保存如下信息：

①節點的ID。

②節點當前所處狀態。

③節點所處位置的坐標。

④節點的最大能量值。

⑤節點當前所剩的能量。

⑥鄰居節點ID表以及對應節點所剩余的能量。

1.3 網絡的初始狀態

傳統算法中，通常對初始狀態有兩種假設：一種是假設初始狀態下，網絡邊緣的傳感器節點處于等待狀態，網絡中剩余的節點處于睡眠狀態［11-13］。另一種是假設網絡中的節點周期性的進入睡眠狀態。第一種假設會使網絡中節點能量消耗不均勻，處于網絡邊緣的節點會很快死亡。第二種假設對網絡中的所有節點進行周期性的喚醒—睡眠操作，網絡的整體能耗較大，而且，可能會發生不能及時發現目標等意外情況。

本文針對上述兩種網絡初始狀態假設的缺陷進行改進，提出當WSN網絡中無目標時，網絡內的節點使用LEACH-PSOC算法［14］形成動態簇，簇內節點輪流擔任簇頭，平衡網絡中的節點能量。

2 基于自適應動態簇和預測機制的跟蹤算法

自適應動態簇的形成和預測機制的合理應用是無線傳感器目標跟蹤算法的核心內容，本文提出自適應動態簇算法及預測算法。

2.1 自適應動態簇組建算法：

動態簇的組建過程主要包括探測到目標的傳感器節點競選簇頭和簇頭對簇成員的選擇等。本文提出的算法中動態簇的形成過程如下：

①競選簇頭

當目標進入監測區域時，目標可能會被多個節點監測到，監測到目標的節點之間相互交換信息，選出距目標最近的節點，然后，該節點廣播消息并喚醒以R為半徑的圓內的節點，同時，網絡中其它處于工作狀態的節點轉為睡眠狀態，喚醒的節點對目標測距，距離大于設置閾值d和能量低于20%*ei_max的節點重新睡眠。

簇頭在當前處于喚醒狀態的節點中選取，簇頭的選舉同時考慮節點當前的剩余能量ei_current［3］和節點距目標的距離ri兩個因素，距目標越近、剩余能量越多的節點被選為簇頭，因此，本文提出通過式（1）來選擇簇頭。

式中，ei_current表示節點i當前剩余的能量，ri表示節點i離目標的距離。喚醒節點根據式（1）計算各自的剩余能量和距目標距離的比值Hi，然后相互交換各自的Hi值，選舉Hi最大的節點作為簇頭節點，其余節點轉為睡眠狀態。

②自適應動態簇組建

選出的簇頭節點以半徑R喚醒圓形區域內的節點，喚醒的節點成為簇成員并與簇頭協同工作，形成簇，對目標進行跟蹤。R的選取非常重要，如果R太小，則簇內節點數目太少，不能有效跟蹤；如果R太大，則簇內節點數目較多，造成不必要的能量浪費。

本文提出半徑R根據目標的運動狀態（如速度v）和傳感器的分布密度自適應確定。首先，簇的半徑至少應該大于目標移動速度。其次，要達到有效跟蹤，簇內傳感器節點應該達到一定數目。

為了節省能量和有效跟蹤，簇內節點數N應該滿足

其中，Nmin和Nmax為兩個設定的閾值，Nmin表示要達到有效跟蹤簇內至少應該包含的節點數目，Nmax表示簇內節點數目的上限。 Nmax應該設置合理，否則，不但浪費能量，而且增大計算量。本文實驗中Nmin和Nmax分別取8和18。

初始時R1是根據具體應用環境及經驗或實驗設置的一個定值，簇頭節點喚醒半徑R1內的節點，之后根據簇內節點數目N是否滿足式（2）而調整R1，若N＜Nmin，則增大半徑R1，若N＞Nmax，則減小半徑R1。直到N的取值滿足式（2）為止，此時自適應得到的半徑R1用于下一步決定最終簇半徑R。

目標的運動速度v也會影響半徑R的選取，速度v較大，則半徑R也較大；速度v較小，則半徑R也較小。

綜合考慮目標運動速度v和上述半徑R1，可以得到，簇頭喚醒的半徑R為：

其中α為常數，可以根據具體情況設置，本文實驗中α=2。由于速度v的量綱為m/s，半徑R1的量綱為m，此處目的是比較αv和R1的大小，用來確定半徑R，所以統一量綱為m。當目標剛進入監測區域時，無法獲得目標的移動速度，此時取R=R1。

由于目標的移動速度v是變化的，且上述R1是自適應的，因此R是根據目標運動狀態和網絡分布情況自適應調整的。

2.2 預測算法

預測算法可根據目標當前運動狀態預測目標下一時刻的狀態，從而提前喚醒監測區域的傳感器，及時跟蹤目標，有效降低傳感器網絡的能量消耗。預測機制的引入，節點對目標的跟蹤不再是被動的跟蹤，而是對運動目標主動的感知，本文使用最小二乘估計和二次多項式擬合對目標軌跡進行預測。

設擬合多項式為y=a0+a1x+a2x2，則本文中測出的各點到這條曲線的偏差平方和為：

等式兩端對ai求偏導，化簡整理得

2.3 基于預測機制的跟蹤算法

動態簇形成以后，對目標進行預測跟蹤，本文提出的算法跟蹤過程如下：

①當前簇的簇成員節點將使用RSSI算法［15］測出的到目標的距離ri和自身的坐標（ ）xi,yi發送給簇頭節點，簇頭節點選取距目標最近的三個節點信息，使用三邊測量法［16］，計算出目標的位置坐標P（x,y）并存儲在簇頭節點中。

②若簇頭節點距目標距離小于d（本文中d取為0.5R），當前簇對目標進行跟蹤，目標前一時刻的位置坐標記為Old（x,y），目標當前時刻的位置坐標信息，記為Now（x,y），當簇頭節點儲存目標的三個位置坐標信息時，使用最小二乘預測算法和二次多項式擬合，計算出目標下一時刻的位置坐標Next（ ）x,y 。

③若簇頭節點距目標距離不小于d（本文中d取為0.5R），簇頭遷移。新的簇頭符合式（1），然后，新簇頭廣播一個信息給其他節點，宣稱自己成為簇頭，其他節點自動轉換為該簇頭的簇成員節點。舊簇頭在接收到新簇頭發來的簇頭當選信息后，將自己儲存的P（x,y）位置信息傳送給新簇頭，同時，舊簇頭轉換為簇成員節點。新的動態簇根據2.1節式（2）中的方法自適應調整簇成員，以便有效跟蹤和節能。新形成的動態簇重復步驟①、步驟②中的過程，繼續進行跟蹤。

④重復步驟②、步驟③，這樣，在新的簇頭節點中總會存儲三個坐標信息，即：Old1（ ）x,y，Old2（x,y）和Now（x,y）。根據這三個坐標信息，使用最小二乘預測算法和二次多項式擬合，計算出目標下一時刻的位置坐標Next（ ）x,y。⑤簇頭節點通過路由喚醒坐標Next（ ）x,y附近的節點進入等待狀態。

⑥隨著目標的移動，重復步驟④、步驟⑤，即可實現目標的跟蹤。

基于預測機制的跟蹤算法流程圖見圖1。

圖1 工作流程圖

3 仿真實驗

為了驗證本文提出的基于預測機制的跟蹤算法，本文利用MATLAB對算法的能量消耗和跟蹤精度進行仿真實驗。假設1 000個節點隨機分布在500 m×500 m的區域，目標在區域內做變速運動，在1 s～40 s內，目標運動速度為［vx, vy］=［3 m /s,3 m/s］，41 s～80 s內，目標的運動速度為［vx, vy］=［8 m/s，4 m/s］，目標初始位置為（0，0），取 Nmax=18，Nmax=18，每個傳感器的檢測半徑為30 m，通信半徑為50 m，傳感器采樣周期為1 s。

為了證明算法的有效性，本文對算法跟蹤誤差，每一時刻跟蹤節點的數目以及能量節約百分比進行了仿真實驗。依次為圖2～圖4。

圖2 跟蹤性能對比

圖2為跟蹤性能比較圖，可以看出，本文的算法在跟蹤誤差為0.2～2.6，基本維持在1.2左右，傳統誤差為0.1～2.3，基本在1.0上下。本文算法略大于無預測機制且簇半徑固定的傳統算法，這是因為傳統算法的簇內參加跟蹤的節點數目一般要大于本文提出的算法，因此在犧牲傳感器節點能量的條件下，會提高跟蹤的精度。但是，本文算法的跟蹤精度同樣也可以滿足要求，而且可以延長網絡的生命期。較無預測機制且簇半徑固定的傳統算法及文獻［5-9］中提出的算法有明顯改進。

簇內傳感器節點數仿真結果如圖3所示。

圖3可以看出，本文所采用的簇結構動態調整方法，可以使簇內節點數基本穩定在一定范圍內，簇內節點數較傳統算法少，這樣既可以有效跟蹤，同時有效節省網絡的能量，延長網絡的生命。而傳統算法由于簇半徑固定，所以為了達到有效跟蹤目標的目的，需要設置簇半徑較大，這樣會浪費節點的能量。

圖4 每一時刻能量節約百分比

圖4為本文算法比傳統算法每一時刻網絡中的能量節約百分比。可以看出，本文算法有效節省了網絡中節點的能量，可以達到延長網絡生命周期的目的。

4 結語

無線傳感器網絡由大量能量有限的傳感器節點組成，因此，如何高效利用網絡中的節點能量是傳感器網絡面臨的主要挑戰之一。本文通過改進動態簇的組建過程中簇頭的選舉和簇成員的征集過程，來達到進一步節能的效果。簇頭的選擇，綜合考慮節點的能量和節點離目標的距離兩個因素。簇成員的征集，同時考慮到目標的移動速度和網絡中節點的分布情況。此外，引入有效的預測機制，使跟蹤過程更加有效和穩定。仿真實驗表明，與傳統算法相比，本文算法在保證跟蹤精度的前提條件下，可以有效節省網絡中節點的能量。

［1］ 孫利民，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版社，2005：391-402.

［2］ 李鳳保，李凌.無線傳感器網絡技術綜述［J］.儀器儀表學報，2005（z2）：559-561.

［3］ 彭勇，王國軍，邢蕭飛.無線傳感器網絡中一種自適應目標跟蹤協議［J］.傳感技術學報，2009，22（3）：427-432.

［4］ 李芳芳，韓冰，單嬌嬌.WSN中基于預測機制動態簇的目標跟蹤算法［J］.計算機與數字工程，2012：40（11）：55-59.

［5］ Enam R N.Energy Efficient Differential Data Aggregation in a Dynamic Cluster Based WSN［C］//2013 International Conference on Collaboration Technologies and Systems（CTS），IEEE，2013：580-583.

［6］ Hu B，He N H.WSN Collaborative Target Tracking Based on Dynamic Clustering［J］.Advanced Materials Research，2013，712：1868-1871.

［7］ Rabia Noor Enam.Energy Efficient Differential Data Aggregation in a Dynamic Cluster Based WSN［C］//International Conference on Collaboration Technologies and Systems（CTS），2013：580-583.

［8］ Dan Liu，Nihong Wang，Yi An.Dynamic Cluster Based Object Tracking Algorithm in WSN.Intelligent Systems（GCIS），2010 Second WRI Global Congress on（Volume：1），2010（1）：397-399.

［9］ Jing Teng，Hichem Snoussi，Cedric Richard.Prediction-Based Cluster Management for Target Tracking in Wireless Sensor Net-Works［J］.Wireless Communications and Mobile Computing，2012（12）：797-812.

［10］Huiyong Yuan，Yongyi Liu，Jianping Yu.A New Energy-Efficientunequal Clustering Algorithm for Wireless Sensor Networks［C］// IEEE Conference on Computer Science and Automation Engineering（CSAE），2011（1）：431-434.

［11］鄧克波，劉中.基于無線傳感器網絡動態簇的目標跟蹤［J］.兵工學報，2008，29（10）：1197-1202.

［12］劉軍，劉暉，葉寧，等.無線傳感器網絡自適應動態簇目標跟蹤策略［J］.東北大學學報：自然科學版，2011：32（8）：1080-1083.

［13］劉立陽，張金成，吳中林.基于分布式動態簇結構的WSN自適應目標跟蹤算法［J］.傳感技術學報，2012，25（1）：110-113.

［14］陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013，26（1）：116-121.

［15］楊文鉑，邢鵬康，劉彥華.一種基于自適應RSSI測距模型的無線傳感器網絡定位方法［J］.傳感技術學報，2015，28（1）：137-141.

［16］王小平，羅軍，沈昌祥.三邊測量法的結果穩定性研究［J］.計算機工程與科學，2012，34（6）：12-17.

崔亞峰（1990-），男，碩士研究生，主要研究方向為無線傳感器網絡目標跟蹤，lsky.cyf@163.com；

史健芳（1966-），教授，博士，碩導，主要致力于智能儀器及檢測技術、智能信息處理等方向研究。

Target Tracking Based on Adaptive Dynamic Clusters and Prediction Mechanism in WSN*

CUI Yafeng，SHI Jianfang*
（Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China）

Wireless sensor network is composed of a lot of energy limited sensor nodes，therefore，how to use the energy of nodes in network efficiently is one of the major challenges for target tracking in sensor network.It proves the reasonable construction of dynamic cluster structure can not only reduce the network energy consumption effectively but also reinforce the lifecycle of the network.By improving methods of the choose of cluster heads and the selection of the cluster members in the process of dynamic cluster construction，this paper is aimed to achieve the further effect of energy saving.The choose of cluster heads is based on the energy of the nodes and the distance from node to target.The selection of the cluster members takes the target's movement speed and the distribution of network nodes into consideration.And the introduction of effective prediction mechanism which can avoid waking up nodes in the network blindly and reduce the time delay of tracking process can further enhance the tracking performance of the network.In addition，the effective prediction mechanism makes the tracking process more effective and stable.The simulations show that the algorithm in this paper can save the energy of the nodes in the network effectively under the tracking precision condition.

wireless sensor network；target tracking；dynamic cluster；prediction mechanism；energy conservation EEACC：6150P；7950

TP393

A

1004-1699（2015）07-1046-05

10.3969/j.issn.1004-1699.2015.07.18

項目來源：國家自然科學基金（50905169）；武器裝備探索研究項目（7131017）；山西省自然科學基金項目（2014011019-1）

2014-11-19 修改日期：2015-03-17