王艷春，尚曉麗，李 會

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

1 引言

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)多目標(biāo)跟蹤節(jié)點任務(wù)分配是研究如何選擇和分配傳感器節(jié)點構(gòu)成多個監(jiān)測聯(lián)盟進(jìn)行協(xié)同工作，以實現(xiàn)對多個目標(biāo)的高性能跟蹤[1]。其核心問題是根據(jù)WSN多目標(biāo)跟蹤的主要性能指標(biāo)，建立相應(yīng)的目標(biāo)函數(shù)，通過優(yōu)化目標(biāo)函數(shù)，確定工作的傳感器節(jié)點及工作模式，從而達(dá)到任務(wù)分配的目的。

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

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

2 WSN多目標(biāo)跟蹤節(jié)點任務(wù)分配數(shù)學(xué)描述及目標(biāo)函數(shù)

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

2.1 數(shù)學(xué)描述

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

(1)

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

(2)

同時，A矩陣中的元素還應(yīng)該滿足：

(3)

節(jié)點任務(wù)分配就是要確定任務(wù)分配矩陣A中每個元素amn的值。式(2)、式(3)構(gòu)成了WSN多目標(biāo)跟蹤節(jié)點任務(wù)分配問題數(shù)學(xué)模型。

2.2 目標(biāo)函數(shù)

為了提高目標(biāo)跟蹤系統(tǒng)的總體性能，節(jié)點任務(wù)分配要保證跟蹤精度，同時盡量降低網(wǎng)絡(luò)能耗。通信能耗主要由發(fā)送能耗ETx和數(shù)據(jù)接收能耗ERx兩部分組成，是距離d的函數(shù)。監(jiān)測M個目標(biāo)的通信能耗模型可表示為：

(4)

其中，dmn表示監(jiān)測節(jié)點n與被監(jiān)測目標(biāo)m之間的歐氏距離，dn1n2表示聯(lián)盟內(nèi)任意兩個節(jié)點n1、n2之間的歐氏距離。

為了提高跟蹤精度，要求節(jié)點與目標(biāo)之間的距離之和盡量小，即：

(5)

綜合考慮，節(jié)點任務(wù)分配目標(biāo)函數(shù)為：

E=α1E1+α2E2

(6)

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

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

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

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

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

(7)

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

(8)

通過迭代運算，調(diào)整聚類中心，計算對各類中心的隸屬度，估算出節(jié)點目標(biāo)位置，此時目標(biāo)函數(shù)達(dá)到較小值。

4 基于FCM-DAFSA的節(jié)點任務(wù)分配

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

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

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

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

(2)聚群行為。設(shè)人工魚當(dāng)前狀態(tài)為Xi，在其可視范圍內(nèi)的同伴的個數(shù)為Nf，中心位置為Xc；如果伙伴中心有較多食物且不太擁擠，即YcNf<δYi，則人工魚Xi向中心位置Xc的方向前進(jìn)一步，使得Xi與Xc的海明距離縮?。环駝t執(zhí)行覓食行為。

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

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

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

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

4.2 DAFSA的改進(jìn)

根據(jù)個體魚自適應(yīng)值與整個魚群的平均自適應(yīng)值作比較，將人工魚群分為三組，并動態(tài)調(diào)整每組魚的視野范圍和步長。具體實現(xiàn)如下：

Visual=Visual-(Visual-

(9)

其中,Visual_end是預(yù)先設(shè)定的最小視野范圍值。

(3)將適應(yīng)值Yi次于Yavg的人工魚分為第三組，動態(tài)調(diào)整其視野為：

(10)

第一組人工魚是較優(yōu)秀的人工魚，因為已經(jīng)接近全局最優(yōu)解，所以賦予較小的視野范圍，能夠達(dá)到強化局部搜索能力的效果；第二組人工魚為一般人工魚，將其視野范圍固定為某一常數(shù)，可以實現(xiàn)在全局搜索和局部搜索之間的平衡；第三組人工魚為較差的人工魚，借鑒自適應(yīng)調(diào)整遺傳算法控制參數(shù)的方法進(jìn)行調(diào)整。k1、k2和Δ為控制參數(shù)，若Δ較大，則人工魚群分布較為分散，Visual較?。凰惴軌蚣訌娋植克阉髂芰κ谷后w趨于收斂；若Δ較小，則人工魚群分布較為集中，Visual較大，算法具有較強的全局搜索能力，從而有效地跳出局部極值。

4.3 基于FCM-DAFSA的節(jié)點任務(wù)分配算法過程

基于FCM-DAFSA的節(jié)點任務(wù)分配過程如下：

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

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

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

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

(7)產(chǎn)生新一代人工魚群，執(zhí)行(2)。

5 仿真實驗與結(jié)果分析

5.1 實驗環(huán)境

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

5.2 能耗分析

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

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

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法和最近鄰法任務(wù)分配所需時間比較曲線。在20 s內(nèi)任務(wù)分配平均時間分別為0.338 2 s、0.193 9 s、0.177 3 s和0.082 s。從數(shù)據(jù)上看，F(xiàn)CM-DAFSA方法的任務(wù)分配時間比MEM方法平均減少了19.7%，比粒子群算法平均減少4.21%。

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

最近鄰法由于直接選用最靠近目標(biāo)節(jié)點組成監(jiān)測聯(lián)盟，幾乎不消耗節(jié)點分配時間。FCM-DAFSA算法選擇與各聚類中心位置最近的三個節(jié)點位置作為監(jiān)測聯(lián)盟，而MEM法在監(jiān)測區(qū)域內(nèi)隨機產(chǎn)生節(jié)點作為監(jiān)測聯(lián)盟，所以FCM-DAFSA搜索區(qū)域較小，迭代次數(shù)也少，因此能縮短任務(wù)分配時間?；玖Ｗ尤核惴ㄈ蝿?wù)分配時間比MEM方法也減少較多，這也是因此粒子群算法采用了利用目標(biāo)函數(shù)優(yōu)化的方法，將不可能的分配方式過早地丟棄掉，因為也能夠減少任務(wù)的分配時間。但是，本文提出的算法在基本人工魚群算法上改進(jìn)較大，因而，算法執(zhí)行速度比粒子群算法要快，所以，任務(wù)分配時間也較少。由此實驗可知，利用FCM-DAFSA方法更能滿足跟蹤系統(tǒng)實時性要求。

5.4 目標(biāo)跟蹤誤差分析

表1是選擇某一目標(biāo)進(jìn)行真實位置與算法測試的位置之間的誤差分析。由表1數(shù)據(jù)可知，最大誤差值為2.5 m，平均值為1.65 m，可以滿足實際應(yīng)用的要求。

Table 1 Target tracking error表1 目標(biāo)的跟蹤誤差 m

6 結(jié)束語

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

[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.

附中文參考文獻(xiàn)：

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

[3] 劉美，徐小玲，黃道平.應(yīng)用粒子群優(yōu)化分配WSN多目標(biāo)跟

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

[5] 陳國龍，郭文忠，陳羽中.無線傳感器網(wǎng)絡(luò)任務(wù)分配動態(tài)聯(lián)盟模型與算法研究[J].通信學(xué)報,2009,30(11):48-55.

[6] 沈艷，郭兵，丁杰雄,等.無線傳感器網(wǎng)絡(luò)節(jié)能動態(tài)任務(wù)分配[J].四川大學(xué)學(xué)報,2008,40(4):143-147.

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

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

[11] 王闖.人工魚群算法的分析及改進(jìn)[D].大連：大連海事大學(xué)，2008.