左現剛，張志霞，賈　蒙

（1.河南科技學院信息工程學院，河南新鄉(xiāng)453003；2.新鄉(xiāng)學院機電工程學院，河南新鄉(xiāng)453003）

基于分布式聚類的有向傳感器網絡移動目標跟蹤算法研究*

左現剛1*，張志霞1，賈蒙2

（1.河南科技學院信息工程學院，河南新鄉(xiāng)453003；2.新鄉(xiāng)學院機電工程學院，河南新鄉(xiāng)453003）

針對有向傳感器網絡DSN（Directional Sensor Networks）中，傳感器節(jié)點部署數量對目標跟蹤精度、網絡壽命和能效問題的影響方面，提出了一個分布式聚類算法，該算法在優(yōu)化活躍傳感器和節(jié)點的直接通信過程中，由分布式集群來負責協(xié)調成員間的節(jié)點，通過傳輸給Sink的定位信息及從多個節(jié)點聚集的傳感數據來準確定位目標的位置。基于該理論的目標跟蹤機制，提高了目標跟蹤精度、增加了網絡壽命和網絡剩余能量。并進行了仿真驗證，結果表明該方法能實現更高的跟蹤性能。

有向傳感器網絡；目標跟蹤；分布式聚類；生命時間

EEACC:7230；6210doi:10.3969/j.issn.1004-1699.2016.07.024

無線傳感器是數據處理、物理傳感及通信的一體化微型器件，有著廣泛的應用?？煞譃槿蚝投ㄏ騼深悺Ｈ騻鞲衅骼萌蛱炀€可以探測周圍任何方向的環(huán)境，而定向傳感器的傳感和通信范圍有限，只能檢測到一個特定方向有限的視野范圍。在定向傳感器網絡（DSN）中，傳感器的通信區(qū)域是扇形的而不是圓形。定向傳感器能提高檢測的質量和縮小干擾和衰落，提高網絡的性能及壽命［1］。

運動目標跟蹤是DSN的一個重要應用，為了達到對運動目標跟蹤的良好效果，需要傳感節(jié)點之間的合作。無線傳感器網絡中移動目標跟蹤中的關鍵問題有：準確的路徑檢測、低成本的數據報告、無數據包丟失的最佳性能、最大化的網絡生命周期。這些問題已經在全向傳感器網絡中進行了很好的研究［2-3］。但是這些解決方案并不適用于DSN，所以在運動目標跟蹤應用中，對傳感器方向性的研究是個新的研究領域。目前已經有一些關于DSN的工程研究應用到移動目標跟蹤中［4-5］，但是這些研究還有進一步提高的必要。

文獻［4］使用協(xié)作DSN的方法，每個傳感器以分布式的方式實時的將運動目標的近似方向信息傳給sink節(jié)點。提出了一種基于扇區(qū)的傳感器網絡目標跟蹤，其中每個節(jié)點識別目標的存在或不存在，也根據從相鄰的傳感器節(jié)點探測的信息來計算目標的位置。這兩種方法增加了sink節(jié)點的計算開銷、冗余感測信息以及從所有節(jié)點接收到的錯誤信息。文獻［5］使用高精度的有向傳感器檢測目標的運動，其視覺范圍是一條直線。為了克服高凸優(yōu)化問題，引入了一種自適應基礎算法ABA（Adaptive Basis Algorithm），ABA估計目標的軌跡、方向及現場傳感線路。因此，傳感器網絡中sink節(jié)點和每個節(jié)點的連接是一個能量饑渴和超負荷的過程；此外，傳感節(jié)點之間的協(xié)調性差，到 sink節(jié)點信息的過度傳遞可能減少跟蹤的精度。

文獻［6］通過引入一個具有乘性噪聲的距離測量模型，提出了一種基于貝葉斯估計的分布式目標跟蹤算法。該算法利用有向傳感器所感知目標的有向感知區(qū)域信息，將目標估計約束在限制區(qū)域內。但其運算成本較高。文獻［7］通過引入重疊質心和有效質心的概念，提出了一種基于虛擬勢場的有向傳感器網絡覆蓋優(yōu)化算法PCAFD，該算法利用與鄰居節(jié)點間覆蓋重疊區(qū)域的面積和位置決定節(jié)點所受虛擬斥力的大小和方向，逐步消除網絡中的覆蓋重疊區(qū)和盲區(qū)，達到快速提高網絡覆蓋率的目的；但該算法僅僅解決了邊界情況中的節(jié)點往復運動的問題。文獻［8］提出了使用中心節(jié)點收集網絡中所有傳感器關于目標的二進制信息，再對這些信息使用粒子濾波器后來更新目標的軌跡。但是，單個節(jié)點要傳輸每一個傳感器的信息需要很大的能量供給。所以這種集中方法是不可靠的，而且，粒子濾波器需要的計算量很大。文獻［9-11］改進了基于每個傳感器和目標距離的權重來檢測目標的算法。作者提出了一種近似線性模型，該模型通過為目標當前的測量軌跡分配一個靈活窗口并使用一個直線段來表示目標在該窗口中的軌跡。此算法通過計算傳感器的加權平均來檢測目標，也作為目標路徑上的估計值，每個估計點都是從最近路徑確定和估計目標的速度，線性方程式有助于確定目標的位置。然而這種方法需要在網絡中保持時間同步，計算也非常復雜，跟蹤不是實時的。

本文使用有向傳感器網絡提出了一種基于分布式集群的算法，能提高跟蹤的精度和可靠性。該算法設計一個DSNs中聚類算法，該聚類算法使用簇頭來執(zhí)行目標跟蹤算法。①為了解決通信開銷，在網絡部署階段，本文引入分布式聚類方法。以分布方式選擇一個簇頭，選擇其中一個簇頭為網關節(jié)點用于和sink的通信。簇頭計算目標的位置并和sink進行連通。因此，降低了網絡流量和能量損耗。②為了增加網絡的壽命和節(jié)省能源，開發(fā)有源節(jié)點選擇算法，開始，為了使用最小數量的有源節(jié)點覆蓋整個群集區(qū)域，每個簇頭都運行該算法。當檢測到目標的存在后，簇頭喚醒相鄰休眠節(jié)點，最后，協(xié)議中規(guī)定計算位置及和sink的通信由簇頭完成。簇頭是通過從集群成員收集目標的檢測信息完成的。

1　網絡模型

假設有向傳感器網絡（DSN）是由N個固定的傳感器節(jié)點放置在一個有限的二維平面區(qū)域組成的。傳感器采用均勻分布和高密度隨機部署，從而保持覆蓋和連接。節(jié)點依靠數據通信網絡形成簇，從而使簇頭可以以多跳方式和sink節(jié)點進行數據通信［12-13］。

假定傳感器可靠地檢測目標的存在，即如果一個目標的位置在一個傳感器的感測范圍之內就會被記錄。傳感器和sink通信并發(fā)送決定目標位置的感測數據到簇頭。

在網絡部署階段，每個節(jié)點由一個三元組＜ID，（x，y），Einit＞定義，其中ID是節(jié)點的唯一標識碼，（x，y）是傳感器的坐標。Einit是其傳感器的剩余能量。通過鄰居發(fā)現協(xié)議［13］，每個節(jié)點都知道和它相鄰節(jié)點的上述三元組信息。

2　MTDC架構

基于分布式集群的運動目標跟蹤（MTDC）機制由如下組件組成：簇群的形成算法，網關節(jié)點的選擇機制，主動感知節(jié)點及其傳感方向的確定，基于簇頭的目標跟蹤算法。

2.1集群的形成

MTDC集群形成算法須實現以下3個目標：①為了保證網絡壽命的最大化，必須確保平衡網絡節(jié)點之間的能量消耗；②增加每個集群成員的數量，以使形成網絡的集群個數減少；③減少從簇頭向sink傳輸數據包的過程中跳躍的次數，因此，通過將剩余能量，相鄰節(jié)點的數量和到sink的距離這3個指標進行線性組合成一個集成指標。

集群的形成是在部署網絡節(jié)點之后開始的。由前面描述知道：每個節(jié)點都知道它的相鄰節(jié)點的標識碼，剩余能量和坐標（x，y）位置。每個節(jié)點可以計算在每一個扇區(qū)s∈Ψc中所擁有的相鄰節(jié)點的數量ni，s，以及到sink的距離d（i，sink）。首先，每個節(jié)點i∈N計算它在扇區(qū)s∈Ψc，（Wi，s）中簇的權重，及其所有的相鄰節(jié)點。

其中 w1，w2，w3是權重因子，w1＞w1＞w1，w1+w1+ w1=1，是傳感器i擁有的最大相鄰節(jié)點數，由下式確定。

然后，每個節(jié)點i∈N檢測以下情況：

如果式（3）對所有的節(jié)點i∈N成立，那么它把自己作為簇頭，式（1）確保每個相鄰的環(huán)境中，根據剩余能量、鄰居節(jié)點數目及與sink距離的權重系數w1，w2和w3的線性加權的組合計算，決定具有最高w值的節(jié)點被選為簇頭。剩余能量被給予最高權重（w1），而距離因子給予最低權重（w3）。第一項有助于確保網絡節(jié)點之間能源消耗的平衡，而第二項減少網絡中形成簇的數目；最后，第三項減少為了給sink傳遞數據包所需要跳躍的數目，這樣，具有較高的剩余能量、較多的相鄰節(jié)點及和sink之間具有較短距離的節(jié)點，將被選為簇頭并具有較高的優(yōu)先級，即在多個具有和sink相同距離及相鄰節(jié)點的簇中，具有最高剩余能量的將被選為簇頭。

CH計算選擇朝向匯聚節(jié)點（sink）的工作通信扇區(qū)，每個簇頭發(fā)送簇成員的請求CH_REQUEST消息到所有鄰近節(jié)點，該消息包括簇頭標識碼、工作通信扇區(qū)標識碼及通信扇區(qū)的設置。

如果 j∈ncH，s收到了簇頭的 CH_REQUEST消息，則j將其通信方向面向簇頭。然后給簇頭發(fā)送包含節(jié)點ID、簇頭ID的簇頭確認信息（CH_CONFIRM）。之后，使用式（1）更新自身和鄰居的W參數。如果一個節(jié)點收到了從多個不同簇頭發(fā)來的請求信息（CH_REQUEST），則加入和其最近的簇。

集群的形成過程如算法1所示。示例如圖1所示，B有最大的W值，選為集群的頭，成員有C和D。同樣的，A節(jié)點創(chuàng)建了一個包括E和F的集群。

圖1　集群的形成

2.2網關的選擇

集群形成后，集群間數據通信需要選擇網關。網關幫助建立數據通信的網絡骨干。由簇頭選擇作為和其他集群通信之用。傳感器i如果能直接和附近的簇頭或者通過該簇頭中的成員直接通信，則作為簇頭的候選網關節(jié)點，假定接收天線是全方位的。簇頭A為所有的備選網關節(jié)點按照如下公式計算網關選擇權重（G）

其中w1，w2，w3是權重因子，w1＞w2＞w3，w1+w2+ w3=1。當節(jié)點滿足下列情況時，簇頭選擇傳感器節(jié)點i作為網關節(jié)點。

因此，因為節(jié)點i使用單跳鄰里信息具有最高的G值，簇頭選擇節(jié)點i作為網關，簇頭k廣播一個網關請求信息GW_REQUEST，該信息包括網關節(jié)點ID和網關工作通信扇區(qū)ID，該網關和其他所有集群成員節(jié)點都知道這個選擇。被選擇的網關給其他的簇頭發(fā)送一個網關確認信息GW_CONFIRM。

一個網關選擇過程的例子如圖2所示。A和B分布是集群1和2的簇頭。節(jié)點成員X和Y在兩個集群的公共區(qū)域，這兩個節(jié)點作為候選網關節(jié)點。和其他所有的候選節(jié)點相比，節(jié)點Y具有最高的G，因此，選擇Y作為和下跳集群通信的網關節(jié)點。

圖2　網關節(jié)點的選擇

2.3集群區(qū)域覆蓋

通信骨干網構造完成后，每個簇頭選擇一些活躍節(jié)點，開始這些活躍節(jié)點將保持清醒狀態(tài)。集群中的其他節(jié)點將處于睡眠模式以節(jié)省能源。

2.3.1邊界區(qū)域的覆蓋

由于存在一些區(qū)域被有向傳感器節(jié)點重疊覆蓋的概率較高，目標機制是通過減少重復覆蓋的范圍及簇邊界區(qū)域內的活躍傳感器節(jié)點的數量。因為簇頭知道其成員節(jié)點的位置，就可以判斷該組傳感器的節(jié)點BCH是用于邊界區(qū)域覆蓋的候選節(jié)點。每個節(jié)點i∈BCH須滿足以下條件：

其中x是在邊界圓弧或直線的上任何點。條件（6）意味著至少節(jié)點i∈BCH及扇區(qū)s∈Ψs可以覆蓋簇邊界的一些區(qū)域。問題歸結到從BCH選擇最小數量的節(jié)點覆蓋在群集邊界區(qū)域上面，這完全是一個NP問題［14］。因此，提出一種貪婪的解決方法。

簇頭使用式（7）在所有節(jié)點i∈BCH中尋找其覆蓋區(qū)域和鄰近節(jié)點（記為 ζB）沒有重疊區(qū)域的節(jié)點。

如果節(jié)點i沒有覆蓋其相鄰節(jié)點j，則overlap（i，j）返回0，否則返回1，如圖3所示，k節(jié)點是簇頭，節(jié)點j在點 p1j（x1j，y1j）和（x2j，y2j），節(jié)點i在 p1j（x1j，y1j）和（x2i，y2i）和簇的邊沿交叉。節(jié)點i和節(jié)點j互有覆蓋。因此，overlap（i，j）可以使用式（8）測試并且返回相應的結果。

圖3　邊界的重疊覆蓋

得到結果后，CH激活剩余所有沒有和其他節(jié)點相覆蓋的節(jié)點，并放入活躍節(jié)點鏈表中，然后，MTDC在第二步驟中，基于覆蓋面積和邊界區(qū)域覆蓋機制，MTDC使用一種貪婪方法激活節(jié)點。CH調整剩余的覆蓋邊界，采用覆蓋區(qū)域降序的排列。

3　仿真分析

通過在matlab中仿真分析實時分布式目標跟蹤（RDTT）［4］、自適應基礎算法［5］和基于分布式聚類算法（MTDC）在移動目標跟蹤方面的性能比較。包塊目標跟蹤的精度、剩余能量的標準差及網絡的壽命。仿真區(qū)域為100 m×100 m，傳感節(jié)點數量200個～1 000個，移動目標的數量1個～5個，傳輸范圍100 m，感知范圍50 m，基于運動目標的一般性，這里設定目標的運動軌跡為在半徑為2 m的圓上做圓周運動，速度大小為1 m/s～6 m/s，仿真時間1 000 s，以下從傳感器節(jié)點部署的數量在目標跟蹤的精度、剩余能量的標準差及網絡壽命方面進行分析。

以下是通過200 m/s～1 000個不同方向的傳感器來測量之前討論的性能指標，扇區(qū)數保持在5個。

圖4（a）顯示在目標跟蹤精度的比較，從一個目標的實際路徑的測量偏差方面有著顯著的改進。從圖中也可以看出，和RDTT、ABA比較，因為CH需要協(xié)調和匯總來自傳感器節(jié)點的目標跟蹤信息，并檢測可能的最佳路徑，目標的跟蹤精度隨傳感器部署數量的增加而增加，這是因為，當有很多節(jié)點的時候，目標將被更大數量的節(jié)點跟蹤，從而跟蹤的準確率會更高。所以，本文提出的算法在這方面表現出了更好的性能。

圖4（b）顯示節(jié)點剩余能量的標準偏差隨著署在網絡中的節(jié)點數量的增加而降低。因為RDTT和ABA在選擇簇頭、網關和主動感測節(jié)點時不考慮節(jié)點的剩余能量水平，因此增加了不平衡能量消耗，另外，在MTDC算法中為了確保能源消耗的平衡而不斷的選擇和更新剩余能量的閾值，因此和RDTT和ABA算法比較，本文提出的MTDC算法得到了更好的結果。

圖4（c）顯示由MTDC、RDTT和ABA算法提供的網絡生命周期的比較。如理論預期一樣，網絡壽命隨著所研究協(xié)議中部署的傳感器數量線性增加。和RDTT和ABA的算法相比，由于MTDC算法使用聚類方法激活最初的幾個節(jié)點，降低了網絡開銷和面積覆蓋率，取得較好的生命周期。

圖4　傳感器節(jié)點部署數量的影響

4　結論

本文提出了以分布式集群為基礎的運動目標跟蹤系統(tǒng)。在MTDC系統(tǒng)中，首先確定簇頭和網關，然后每個CH通過激活一些相鄰區(qū)域的傳感節(jié)點，解決區(qū)域的覆蓋問題。通過在MTDC系統(tǒng)中形成的簇頭收集來自成員節(jié)點的有效數據，來提高目標的跟蹤精度。另外通過減少向匯節(jié)點發(fā)送數據的數量，來降低網絡帶寬的浪費，增加網絡的壽命。

［1］ 任勇默，范興剛，車志聰，等.一種有向傳感器網絡柵欄覆蓋增強算法［J］.傳感技術學報，2015，28（7）：1051-1057.

［2］ Bapat S，Kulathumani V，Arora A.Reliable Estimation of Influence Fields for Classification and Tracking in Unreliable Sensor Networks［C］//Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems，Orlando，FL，USA，26-28 October 2005：60-69.

［3］ 陳常超，孫力娟，韓崇，等.有向傳感網分塊區(qū)域p-覆蓋節(jié)點調度算法研究［J］.傳感技術學報，2015，28（1）：107-114.

［4］ Wang Z，Bulut E，Szymanski B K.Distributed Target Tracking with Directional Binary Sensor Networks［C］//Proceedings of the 28th IEEE Conferenceon Global Telecommunications，Honolulu，HI，USA，30 November-4 December 2009：1-6.

［5］ Plarre K，Kumar P.Tracking Objects with Networked Scattered Directional Sensors［J］.EURASIP J Adv Signal Process，2008：74.

［6］ 胡小青，胥布工，劉永桂，等.分布式的有向傳感器網絡目標跟蹤算法［J］.華南理工大學學報（自然科學版），2013（9）：8-14.

［7］ 戴寧，毛劍琳，付麗霞，等.基于虛擬勢場的有向傳感器網絡覆蓋優(yōu)化算法［J］.計算機應用研究，2014（3）：905-907.

［8］ Teng J，Snoussi H，Richard C.Binary Variational Filtering for Target Tracking in Sensor Networks［C］//Proceedings of the IEE/SP 14th Work shopon Statistical Signal Processing（SSP'07），Madison，WI，USA，26-29 August 2007：685-689.

［9］ Liu L，Zhang X，Ma H D.Exposure-Path Prevention in Directional Sensor Networks Using Sector Model Based Percolation［C］//Proc of the IEEE ICC 2009.New York：IEEE Press，2009：2707-2711.

［10］Wang Y，Cao G H.Minimizing Service Delay in Directional Sensor Networks［C］//Proc of the IEEE INFOCOM 2011.New York：IEEE Press，2011：1790-1798.

［11］譚勵，楊朝玉，楊明華，等.改進的非均勻有向傳感器網絡節(jié)點部署方法［J］.傳感技術學報，2015，28（12）：1835-1840.

［12］Dutta P，Culler D.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications［C］//Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems（SenSys'08），Raleigh，CA，USA，5-7 November 2008；ACM：New York，NY，USA，2008：71-84.

［13］Jo Y，Jung I.Analysis of Vehicle Detection with WSN-Based Ultrasonic Sensors［J］.Sensors，2014，14：14050-14069.

［14］Ai J，Abouzeid A A.Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks［J］.J Comb Optim，2006（11）：21-41.

左現剛（1976-）男，河南開封，碩士，研究方向為無線傳感器網絡，zuoxg2002@ 163.com；

張志霞（1982-），女，河南平頂山，碩士，研究方向為智能信號處理、圖像處理；

賈蒙（1981-），男，河南新鄉(xiāng)，博士，副教授，研究方向為非線性信號處理。

Moving Target Tracking Algorithm Based on Distributed Clustering in Directional Sensor Networks*

ZUO Xiangang1*，ZHANG Zhixia1，JIA Meng2
（1.Department of Information Engineering，Henan Institute of Science and Technology，Xinxiang He'nan 453003，China；2.Department of Electrical Engineering，Xinxiang College，Xinxiang He'nan 453003，China）

According to the effect of the amount of sensor node for the target tracking accuracy and residual energy and network lifetime in the directional sensor networks，a distributed clustering algorithm is proposed.During the process of optimizing and activating the direct communication between sensors and nodes，the algorithm uses the distributed cluster to coordinate the nodes among the members.And accurate positioning of the target can be realized according to the location information transmitted to the sink and the sensing data from the multiple nodes. Based on the target tracking mechanism of this theory，the network lifetime and residual energy is increased，and the target tracking accuracy in the network is improved.The simulation results show that the method proposed in this paper can achieve higher performance compared with other new methods.

directional sensor networks；target tracking；distributed clustering；life time

TP393

A

1004-1699（2016）07-1096-06

項目來源：國家自然科學基金項目（61501391）

2015-11-17修改日期：2016-03-18