FCM-DAFSA的無線傳感器網絡多目標跟蹤節點任務分配方法

王艷春，尚曉麗，李 會

(1.齊齊哈爾大學通信與電子工程學院，黑龍江 齊齊哈爾 161006;2.綏化大學計算機學院，黑龍江 綏化 152061)

1 引言

無線傳感器網絡WSN(Wireless Sensor Networks)多目標跟蹤節點任務分配是研究如何選擇和分配傳感器節點構成多個監測聯盟進行協同工作，以實現對多個目標的高性能跟蹤[1]。其核心問題是根據WSN多目標跟蹤的主要性能指標，建立相應的目標函數，通過優化目標函數，確定工作的傳感器節點及工作模式，從而達到任務分配的目的。

在近期的多目標跟蹤節點任務分配中，文獻[2]等采用目標誤差協方差矩陣的跡、均方根誤差、最大信息增量作為指標構建目標函數，目的是提高跟蹤精度。文獻[3]利用基本粒子群算法，將粒子群算法離散化后，直接應用于節點任務分配，效果一般。文獻[4]選擇距離目標最近的三個傳感器節點組合對目標定位跟蹤，該方法適用于單體目標跟蹤，對于節點隨機分布和通信能耗問題沒有多加考慮。文獻[5]提出集中式任務分配的信號處理方式，該方法探測聯盟相對固定，容易出現探測聯盟能量消耗過大導致網絡癱瘓的情況。文獻[6,7]綜合考慮目標跟蹤準確度和網絡能耗，根據節點空間相關性構造能耗函數進行節點優化。文獻[8]采用最小能量準則建立目標函數，以彈性神經網絡實現對多目標節點任務進行優化分配，由于系統能耗降低過大，導致任務分配時間較長。

本文利用離散人工魚群算法結合模糊C均值聚類，對WSN多目標跟蹤節點任務分配進行仿真實驗；該方法首先利用類間距閾值的模糊C均值聚類算法，估計監測區域可能出現的目標數量和目標位置；再根據目標函數改進了基本人工魚群算法，使得該方法更適合對目標函數進行快速優化；最后根據任務分配的目標函數，使用改進的離散人工魚群算法優化目標函數，得到任務分配方案。實驗結果表明，同最近鄰法、MEM(Multiple Elastic Modules)[9]、粒子群算法比較，該方法綜合性能比較優越。

2 WSN多目標跟蹤節點任務分配數學描述及目標函數

WSN多目標跟蹤節點任務分配是一個資源分配滿足不同約束的過程，不同時刻任務的分配可能不同，所以具有一定的動態性[10]。當對多個目標進行跟蹤時，要對多個目標一一建立其監測聯盟。存在的問題是，當被跟蹤的目標距離比較近的時候可能發生資源爭奪，在這種情況下，必須調整分配方案，分配關鍵性的節點資源以合適任務，從而達到優化的目的。因為任務分配具有動態性，任務分配算法必須在不同的時刻根據跟蹤的目標調整分配方案。當跟蹤目標出現時，任務節點把自己探測到的信息傳給匯聚節點，匯聚節點構建目標監測數據矩陣，再根據任務分配算法選擇目標監測聯盟，確定盟主，由盟主對監測到的數據進行預處理并且進行狀態預測，并把結果傳送到匯聚節點。當跟蹤目標離開當前聯盟的范圍時，由匯聚節點根據各目標下一時刻的預測狀態和任務分配算法，選擇合適節點組成新的監測聯盟繼續進行檢測。

2.1 數學描述

假設監測區域均勻隨機分布N個傳感器節點，M個被跟蹤目標，N≥3M，保證每個目標周圍至少有三個節點可以探測到目標。在T0時刻，用bmn(m=1,2,3,…,M;n=1,2,3,…,N)表示第n個WSN節點能否觀測到第m個目標，bmn=1表示第n個WSN節點能觀測到第m個目標，否則bmn=0。則WSN節點監測目標的情況可用如下監測數據矩陣來描述：

(1)

用Cm={sm1,sm2,sm3}(m=1,2,3,…,M)表示第m個目標的監測聯盟，smi(i=1,2,3)為聯盟內節點，M個目標需要建立M個聯盟集合：Ω={C1,C2,C3,…,CM}，用amn=1 (m=1,2,3,…,M;n=1,2,3,…,N)表示第n個WSN節點加入第m個監測聯盟來監測第m個目標，否則amn=0。M個目標的任務分配矩陣描述如下：

(2)

同時，A矩陣中的元素還應該滿足：

(3)

節點任務分配就是要確定任務分配矩陣A中每個元素amn的值。式(2)、式(3)構成了WSN多目標跟蹤節點任務分配問題數學模型。

2.2 目標函數

為了提高目標跟蹤系統的總體性能，節點任務分配要保證跟蹤精度，同時盡量降低網絡能耗。通信能耗主要由發送能耗ETx和數據接收能耗ERx兩部分組成，是距離d的函數。監測M個目標的通信能耗模型可表示為：

(4)

其中，dmn表示監測節點n與被監測目標m之間的歐氏距離，dn1n2表示聯盟內任意兩個節點n1、n2之間的歐氏距離。

為了提高跟蹤精度，要求節點與目標之間的距離之和盡量小，即：

(5)

綜合考慮，節點任務分配目標函數為：

E=α1E1+α2E2

(6)

其中，α1、α2為權重值，且有：α1,α2∈[0,1]；α1+α2=1。

任務分配就是根據給定的α1和α2值，求得式(6)的最小值，從而得到聯盟的組合。

3 WSN基于類間距閾值的FCM算法

WSN基于類間距閾值的模糊C均值FCM(Fuzzy C-Means)算法實現步驟：

(2)設監測數據集合X={x1,x2,x3,…,xN}，聚類中心集合V={v1,v2,v3,…,vC}，數據xi(i=1,2,…,N)對vk(k=1,2,…,C)的隸屬度uik，U={uik}(i=1,2,…,N;k=1,2,…,C)，設定模糊權重因子β，那么WSN監測數據zk(k=1,2,…,C)與聚類中心vk(k=1,2,…,C)的帶權距離平方和為：

(7)

得到數據集最佳劃分滿足式(8)：

(8)

通過迭代運算，調整聚類中心，計算對各類中心的隸屬度，估算出節點目標位置，此時目標函數達到較小值。

4 基于FCM-DAFSA的節點任務分配

人工魚群算法是一種新型的基于集群智能優化算法[11]。其思想是：在魚生活的水域中，魚往往能自行或尾隨其它魚找到食物多的地方。人工魚群算法就是根據這一特點，通過模擬魚群的行為動作，結合動物自制體模式，來對問題進行優化。基本人工魚群算法AFSA(Artificial Fish Swarm Algorithm)針對連續問題進行求解，而WSN多目標跟蹤節點任務分配問題是一個離散問題[12]。因此，必須對該算法及相關個體魚的行為重新進行定義。

4.1 離散人工魚群算法DAFSA(Discrete Artificial Fish Swarm Algorithm)原理

定義個體魚位狀態X，即X={x1,x2,…,xn}，其中xi∈{0,1}(i=1,2,…,n)為尋優變量；人工魚當前位置的食物濃度為Y=f(X)，Y表示目標函數值；個體魚之間的距離d2ij為Xi與Xj的海明距離；Visual表示感知范圍，Step表示個體魚的運動步長，取值均為整數；δ表示擁擠度因子。下面簡述魚群的行為[10]:

(1)覓食行為。設第i個人工魚當前狀態為Xi={xi1,xi2,…,xin}，在其視野范圍內隨機選擇一個狀態Xj，如果該狀態周圍的食物濃度大于當前狀態時，則向該方向前進一步，使得Xi與Xj的海明距離縮小；如果該狀態周圍的食物濃度小于當前狀態時，則重新在其視野范圍內隨機選擇狀態Xj，判斷當前狀態是否滿足前進條件。試探try_number次后，如果仍不滿足前進條件，則執行隨機行為。

(2)聚群行為。設人工魚當前狀態為Xi，在其可視范圍內的同伴的個數為Nf，中心位置為Xc；如果伙伴中心有較多食物且不太擁擠，即YcNf<δYi，則人工魚Xi向中心位置Xc的方向前進一步，使得Xi與Xc的海明距離縮小；否則執行覓食行為。

(3)追尾行為。設人工魚在其可視范圍內尋找狀態最優的鄰居，設為Xmax，如果它附近有較高的食物濃度且不太擁擠，則向Xmax的位置前進一步，使得Xi與Xmax的海明距離縮小；否則，執行覓食行為。

(4)隨機行為。人工魚在視野中隨機選擇一個狀態，然后向該方向移動。

(5)行為選擇。選擇其中的最優者來實際執行，缺省的行為方式為覓食行為。

(6)公告板。記錄最優人工魚個體狀態的地方，即為所求的最優值和個體魚的位置。

4.2 DAFSA的改進

根據個體魚自適應值與整個魚群的平均自適應值作比較，將人工魚群分為三組，并動態調整每組魚的視野范圍和步長。具體實現如下：

Visual=Visual-(Visual-

(9)

其中,Visual_end是預先設定的最小視野范圍值。

(3)將適應值Yi次于Yavg的人工魚分為第三組，動態調整其視野為：

(10)

第一組人工魚是較優秀的人工魚，因為已經接近全局最優解，所以賦予較小的視野范圍，能夠達到強化局部搜索能力的效果；第二組人工魚為一般人工魚，將其視野范圍固定為某一常數，可以實現在全局搜索和局部搜索之間的平衡；第三組人工魚為較差的人工魚，借鑒自適應調整遺傳算法控制參數的方法進行調整。k1、k2和Δ為控制參數，若Δ較大，則人工魚群分布較為分散，Visual較小；算法能夠加強局部搜索能力使群體趨于收斂；若Δ較小，則人工魚群分布較為集中，Visual較大，算法具有較強的全局搜索能力，從而有效地跳出局部極值。

4.3 基于FCM-DAFSA的節點任務分配算法過程

基于FCM-DAFSA的節點任務分配過程如下：

(1)人工魚群初始化：人工魚群初始化的數據以WSN目標估計位置為依據，選取與目標估計位置最近三個節點構成初始監測聯盟，避免搜索空間過大。定義個體魚位置X代表一種任務分配方案，即X={X1,X2,…,Xj,…,XM}，1≤j≤M；Xj={xj1,xj2,…,xji,…,xjn}，1≤i≤N。其中xji=1表示第i個節點分配跟蹤目標j。初始化Step、Visual、擁擠度因子δ。最大迭代次數Gmax，試探try_number次。

(2)計算目標函數值，找出最小值及其對應的人工魚個體，并賦給公告板，判斷是否滿足結束條件，如果滿足結束條件，則輸出公告板；否則執行(3)；

(4)根據分組情況，利用式(9)、式(10)確定視野范圍及步長。

(5)根據情況選擇追尾行為、聚群行為、覓食行為、隨機行為。

(7)產生新一代人工魚群，執行(2)。

5 仿真實驗與結果分析

5.1 實驗環境

軟件環境：MATLAB 7.8；操作系統：Windows XP；硬件環境：Intel Core2，CPU主頻1.60 GHz，1 GB內存；設在[0,100] m×[0,100] m監測區域內隨機均勻布置60個傳感器節點，節點可以獲得自身位置信息，通訊半徑為20 m，監測半徑為20 m。

5.2 能耗分析

在實驗過程中，以三個目標連續運動20 s的節點任務分配所需能耗進行比較,并假設節點之間傳送數據通信量相同，以通信距離作為能耗近似衡量指標。圖1是最近鄰法、MEM、粒子群算法和FCM-DAFSA在三個目標上的平均能耗比較曲線圖。由圖1的仿真結果可見，最近鄰法的能耗最高，MEM方法次之，粒子群算法再次之，而本文提出的FCM-DAFSA算法能耗最低。四種方法在20 s的平均通信距離分別為139.87 m、154.60 m、160.01 m和162.18 m，本文提出的算法通信距離最大。與其他三種方法比較，FCM-DAFSA算法的能耗平均降低8.61%、5.52%和1.08%。

FCM-DAFSA算法能耗降低的原因在于它把能耗最小化作為節點任務分配目標函數，在改進DAFSA算法中以目標函數作為適應值函數，對基本人工魚群算法做了較大的改進，使得在尋找目標函數最優值時，能夠更快地找到目標函數的最優值，同時將不必要的解濾除掉，從而實現快速節點任務的最優分配。而文獻[3]是直接采用了基本粒子群算法，所以要比文本的算法稍差一些。本文的方法能夠在原理上確保WSN多目標跟蹤節點任務分配低能耗的要求。

Figure 1 Energy consumption curve compared with the nearest neighbor method,MEM method, and particle swarm algorithm圖1 與最近鄰分配方法、MEM方法、粒子群算法的能耗比較曲線

5.3 分配時間分析

圖2是MEM法、粒子群法、FCM-DAFSA法和最近鄰法任務分配所需時間比較曲線。在20 s內任務分配平均時間分別為0.338 2 s、0.193 9 s、0.177 3 s和0.082 s。從數據上看，FCM-DAFSA方法的任務分配時間比MEM方法平均減少了19.7%，比粒子群算法平均減少4.21%。

Figure 2 Allocation time curve compared with the nearest neighbor method,MEM method,and particle swarm algorithm圖2 與最近鄰分配方法、MEM方法、粒子群算法的分配時間比較曲線

最近鄰法由于直接選用最靠近目標節點組成監測聯盟，幾乎不消耗節點分配時間。FCM-DAFSA算法選擇與各聚類中心位置最近的三個節點位置作為監測聯盟，而MEM法在監測區域內隨機產生節點作為監測聯盟，所以FCM-DAFSA搜索區域較小，迭代次數也少，因此能縮短任務分配時間。基本粒子群算法任務分配時間比MEM方法也減少較多，這也是因此粒子群算法采用了利用目標函數優化的方法，將不可能的分配方式過早地丟棄掉，因為也能夠減少任務的分配時間。但是，本文提出的算法在基本人工魚群算法上改進較大，因而，算法執行速度比粒子群算法要快，所以，任務分配時間也較少。由此實驗可知，利用FCM-DAFSA方法更能滿足跟蹤系統實時性要求。

5.4 目標跟蹤誤差分析

表1是選擇某一目標進行真實位置與算法測試的位置之間的誤差分析。由表1數據可知，最大誤差值為2.5 m，平均值為1.65 m，可以滿足實際應用的要求。

Table 1 Target tracking error表1 目標的跟蹤誤差 m

6 結束語

首先，分析了WSN多目標跟蹤節點任務分配的國內外學者的工作，根據該研究領域的趨勢，提出了自己的研究方法；其次，利用FCM方法對WSN的節點進行聚類，估計出監測區域可能出現的目標數量和目標位置；再次，對人工魚群算法進行離散化，將離散人工魚群算法進行了改進，使得該方法能夠使用在無線傳感器節點任務分配上；最后，將本文方法與最近鄰方法、粒子群算法和MEM方法進行比較，從仿真實驗結果可以看出，本文方法能夠提高WSN的綜合性能，也適合實際的應用。

[1] Zhao Feng,Shin J, Reich J. Information-driven dynamic sensor collaboration[J]. Signal Processing Magazine, 2002, 19(2):61-72.

[2] Liu Xian-xing, Zhou Lin, Du Xiao-yu. A method of sensor management based on target priority and information gain[J]. Acta Electronica Sinica, 2005,33(9):1683-1687.(in Chinese)

[3] Liu Mei, Xu Xiao-ling, Huang Dao-ping. Using PSO to realize nodes task allocation of muti-target tracking in WSN[J].Chinese Journal of Sensors and Actuators,2010,23(9):1334-1339.(in Chinese)

[4] Tseng Yu-Chee, Kuo Sheng-po, Lee Hung-wei, et al. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies[J] . Computer Journal, 2004, 47(4):448-460.

[5] Chen Guo-long, Guo Wen-zhong, Chen Yu-zhong. Research on dynamic alliance of task allocation and its algorithm in wireless sensor network[J]. Journal on Communications, 2009,30(11):48-55. (in Chinese)

[6] Shen Yan, Guo Bing, Ding jie-xiong, et al. Energy-efficient dynamic task allocation in wireless sensor networks [J]. Journal of Sichuan University, 2008,40(4):143-147. (in Chinese)

[7] Kang Hui,Li Xiao-lin.Power-aware sensor selection in wireless sensor networks[C]∥Proc of VTC’09,2009:1-5.

[8] Liu Mei,Li Hai-hao,Shen Yi. Research on task allocation technique for aerial target tracking based on wireless sensor network[J]. Journal of Astronautics,2007, 28(4):960- 971. (in Chinese)

[9] Zhao Li-ping. Application of MEM models in locking and tracking multiple random passive targets [J]. Journal of East China University of Science and Technology,2001,27(5):527-532.(in Chinese)

[10] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]∥Proc of the Hawaii International Conference System Sciences, 2000:1.

[11] Wang Chuang.The analysis and improvement of artificial fish-swarm algorithm [D].Dalian:Dalian Maritime University, 2008. (in Chinese)

[12] Eren T, Whiteley W, Belhumeur P N. Further results on sensor network localization using rigidity[C]∥Proc of European Workshop on Wireless Sensor Networks ( EWSN ), 2005:405-409.

附中文參考文獻：

[2] 劉先省，周林，杜曉玉.基于目標權重和信息增量的傳感器管理方法[J].電子學報,2005,33(9):1683-1687.

[3] 劉美，徐小玲，黃道平.應用粒子群優化分配WSN多目標跟

蹤節點任務[J].傳感技術學報,2010,23(9):1334-1339.

[5] 陳國龍，郭文忠，陳羽中.無線傳感器網絡任務分配動態聯盟模型與算法研究[J].通信學報,2009,30(11):48-55.

[6] 沈艷，郭兵，丁杰雄,等.無線傳感器網絡節能動態任務分配[J].四川大學學報,2008,40(4):143-147.

[8] 劉梅，李海昊，沈毅.無線傳感器網絡空中目標跟蹤任務分配技術的研究[J].宇航學報, 2007, 28(4):960-971.

[9] 趙莉萍. MEM模型在多傳感器多目標無源定位與跟蹤中的應用[J].華東理工大學學報,2001,27(5):527-532.

[11] 王闖.人工魚群算法的分析及改進[D].大連：大連海事大學，2008.