文莎,蔡自興,劉麗玨,任孝平
(中南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙,410083)
近年來(lái),隨著嵌入式系統(tǒng)、微傳感技術(shù)以及無(wú)線通信技術(shù)的發(fā)展,無(wú)線傳感器網(wǎng)絡(luò)(WSN)在民用和軍事領(lǐng)域得到廣泛的應(yīng)用[1]。而目標(biāo)跟蹤作為無(wú)線傳感器網(wǎng)絡(luò)的熱點(diǎn)研究領(lǐng)域,一直備受關(guān)注[2]。在現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)協(xié)同跟蹤移動(dòng)目標(biāo)的任務(wù)分配研究成果中,Tseng等[3]只針對(duì)跟蹤1個(gè)目標(biāo)和傳感器呈特殊的等邊三角形分布的情形,沒(méi)有考慮存在多目標(biāo)和傳感器隨機(jī)分布的情形以及能量消耗的因素。Kaplan[4]雖然考慮能耗因素,但是也沒(méi)有考慮多目標(biāo)跟蹤任務(wù)和資源競(jìng)爭(zhēng)沖突問(wèn)題。Zhu等[5]考慮傳感器節(jié)點(diǎn)隨機(jī)分布情形,也考慮了多目標(biāo)跟蹤任務(wù),但只試圖使系統(tǒng)能耗最低,沒(méi)有考慮精度因素。由此可知,WSN目標(biāo)跟蹤技術(shù)仍不完善,有許多內(nèi)容亟待研究。本文采用動(dòng)態(tài)聯(lián)盟機(jī)制[6-7]進(jìn)行協(xié)同任務(wù)分配,除考慮系統(tǒng)能耗外,還考慮定位精度,提出兼顧能耗和精度的綜合性能指標(biāo)函數(shù)[8],對(duì)目標(biāo)跟蹤系統(tǒng)進(jìn)行建模。并運(yùn)用遺傳算法,以綜合性能指標(biāo)函數(shù)為目標(biāo)函數(shù)指導(dǎo)搜索,實(shí)現(xiàn)動(dòng)態(tài)聯(lián)盟中盟主盟員的選擇,最終實(shí)現(xiàn)各指標(biāo)平衡、綜合性能優(yōu)化的協(xié)同任務(wù)分配。
采用動(dòng)態(tài)聯(lián)盟機(jī)制[6-7]進(jìn)行任務(wù)分配,動(dòng)態(tài)聯(lián)盟機(jī)制執(zhí)行過(guò)程可用形式化語(yǔ)言描述如下:
(1)當(dāng)目標(biāo)T從感知區(qū)域以外進(jìn)入到感知區(qū)域內(nèi)部時(shí),原則上選出第一個(gè)感測(cè)到它的節(jié)點(diǎn)作為盟主H[9],H立即廣播消息“Coming Target”, 喚醒其通信范圍內(nèi)的鄰節(jié)點(diǎn)。
(2)設(shè)Ωs= {s1,s2,… ,sN}為被喚醒的N個(gè)節(jié)點(diǎn)構(gòu)成的集合,各節(jié)點(diǎn)根據(jù)任務(wù)信息和自身當(dāng)前狀態(tài)給出回復(fù)信息,盟主根據(jù)回復(fù)信息選取一定數(shù)量的節(jié)點(diǎn)作為盟員,構(gòu)成盟員集合此盟員集合Ωm與盟主H一起構(gòu)成1個(gè)動(dòng)態(tài)聯(lián)盟。
在第2步中,盟主如何選取一定數(shù)量的節(jié)點(diǎn),構(gòu)成盟員集合mΩ,即為本文的研究重點(diǎn)——?jiǎng)討B(tài)聯(lián)盟自組織算法[2]。假設(shè):1個(gè)動(dòng)態(tài)聯(lián)盟需要3個(gè)傳感器節(jié)點(diǎn)組成。考慮到傳感器節(jié)點(diǎn)的能力限制,1個(gè)節(jié)點(diǎn)只能加入1個(gè)動(dòng)態(tài)聯(lián)盟實(shí)現(xiàn)對(duì)1個(gè)目標(biāo)的跟蹤。當(dāng)監(jiān)視區(qū)域內(nèi)有多個(gè)目標(biāo)時(shí),需要多個(gè)動(dòng)態(tài)聯(lián)盟,這時(shí),不同的聯(lián)盟也許選中同樣的節(jié)點(diǎn)作為其成員,即會(huì)產(chǎn)生節(jié)點(diǎn)資源競(jìng)爭(zhēng)沖突的現(xiàn)象[10]。在這種情況下,必須優(yōu)化分配關(guān)鍵性的節(jié)點(diǎn)給合適的聯(lián)盟,如果關(guān)鍵資源無(wú)策略地隨機(jī)分配,其結(jié)果可能會(huì)導(dǎo)致網(wǎng)絡(luò)總性能降低。
以文獻(xiàn)[10]的模型為基礎(chǔ),根據(jù)節(jié)點(diǎn)能量消耗情況,結(jié)合具體定位法,給出本文的網(wǎng)絡(luò)能耗模型。
節(jié)點(diǎn)的能量消耗一般由感應(yīng)、數(shù)據(jù)處理、節(jié)點(diǎn)間的通信3方面構(gòu)成[10]。其中,占能量消耗主體的是節(jié)點(diǎn)間的通信,而通信能耗主要取決于通信距離。因此,控制通信距離能有效地節(jié)約網(wǎng)絡(luò)能量。
設(shè)有M個(gè)目標(biāo):T1,T2,…,Tm,…,TM,因此有M個(gè)盟主:H1,H2,…,Hm,…,HM。任取1個(gè)目標(biāo)Tm為例(1≤m≤M),它的盟主節(jié)點(diǎn)是Hm,被喚醒的節(jié)點(diǎn)盟主節(jié)點(diǎn)Hm與被喚醒節(jié)點(diǎn)(1≤n≤N)之間的距離;αmn為指示數(shù),當(dāng)αmn=1時(shí),盟主Hm選擇被喚醒節(jié)點(diǎn)作為聯(lián)盟成員;當(dāng)=0時(shí),盟主Hm不選擇被喚醒節(jié)點(diǎn)作聯(lián)盟成員。
為使網(wǎng)絡(luò)的總通信能耗最少,任務(wù)分配須有如下目標(biāo)函數(shù):

約束條件如下。
(1)1個(gè)傳感器節(jié)點(diǎn)只能加入1個(gè)聯(lián)盟,或者休眠。可解決跟蹤多目標(biāo)時(shí)節(jié)點(diǎn)資源競(jìng)爭(zhēng)沖突問(wèn)題。

(2)1個(gè)盟主需要選擇2個(gè)節(jié)點(diǎn)作為聯(lián)盟成員。保證了每個(gè)聯(lián)盟由3個(gè)節(jié)點(diǎn)組成。

(3)所有αmn之和應(yīng)滿足如下條件,以保證每個(gè)目標(biāo)都得到分配。

本文采用三點(diǎn)定位法[11]對(duì)目標(biāo)進(jìn)行定位。三點(diǎn)定位法計(jì)算簡(jiǎn)單、需要已知坐標(biāo)的節(jié)點(diǎn)數(shù)目少,適應(yīng)于傳感器節(jié)點(diǎn)計(jì)算和存儲(chǔ)能力有限的特點(diǎn)。其基本原理為:已知節(jié)點(diǎn)A,B,C的位置以及它們與目標(biāo)的距離,以3個(gè)節(jié)點(diǎn)為圓心,以它們到目標(biāo)的距離為半徑畫(huà)圓,若測(cè)量精確,3個(gè)圓應(yīng)該交于1個(gè)點(diǎn),則點(diǎn)就是目標(biāo)的估計(jì)位置。但是,由于測(cè)量存在誤差,3個(gè)圓產(chǎn)生重疊區(qū)域,如圖1所示。這時(shí),任意2圓的交點(diǎn)可定義1條直線,其中任兩條直線的交點(diǎn)就作為目標(biāo)的估計(jì)位置。圖1中點(diǎn)P為最后確定的目標(biāo)估計(jì)位置。
三點(diǎn)定位法是一種基于測(cè)距技術(shù)的定位[12],而它的定位精度除與節(jié)點(diǎn)到目標(biāo)的距離有關(guān)外,還與3個(gè)節(jié)點(diǎn)相對(duì)目標(biāo)的位置有關(guān),即在一定的距離范圍內(nèi),3個(gè)節(jié)點(diǎn)把目標(biāo)包圍在它們組成的三角形之內(nèi)時(shí),定位精度更高[13]。可通過(guò)仿真試驗(yàn)來(lái)證明此結(jié)論。
取目標(biāo)估計(jì)位置與實(shí)際位置的距離為定位誤差:


圖1 三點(diǎn)定位法原理示意圖Fig.1 Principle of three-point location
不妨給出如圖2所示的試驗(yàn)場(chǎng)景,取目標(biāo)T的坐標(biāo)(x0,y0)為(0,0),盟主H的坐標(biāo)(x1,y1)為(4,7),2 個(gè)盟員的初始位置是和盟主無(wú)限接近的(三點(diǎn)距離幾乎為0),2個(gè)盟員各沿著2條直線向下移動(dòng),3個(gè)節(jié)點(diǎn)間距離(簡(jiǎn)稱節(jié)點(diǎn)間距)越來(lái)越大,并慢慢將目標(biāo)圍在其中,直至終點(diǎn)a′,b′。
以節(jié)點(diǎn)間距為橫坐標(biāo),定位誤差為縱坐標(biāo),可得結(jié)果如圖3所示。由圖3可見(jiàn):隨著節(jié)點(diǎn)間距由0漸漸增大,3個(gè)節(jié)點(diǎn)漸漸將目標(biāo)包圍,誤差不斷減小。當(dāng)2節(jié)點(diǎn)移動(dòng)到a*和b*時(shí)(對(duì)應(yīng)節(jié)點(diǎn)間距為5.145 6),定位誤差最小。2節(jié)點(diǎn)再繼續(xù)向下移動(dòng),3個(gè)節(jié)點(diǎn)距目標(biāo)的距離已較遠(yuǎn)了,此時(shí),由于測(cè)量數(shù)據(jù)隨距離增加受到的干擾增大,準(zhǔn)確度降低,定位誤差又開(kāi)始增大。可見(jiàn):在一定的距離范圍內(nèi),限定3節(jié)點(diǎn)將目標(biāo)圍住,確實(shí)能減小定位誤差,提高定位精度。

圖2 試驗(yàn)場(chǎng)景Fig.2 Experimental scene

圖3 定位誤差與節(jié)點(diǎn)位置的關(guān)系Fig.3 Relationship between location error and position of nodes
本節(jié)的節(jié)點(diǎn)選擇即選取3個(gè)節(jié)點(diǎn)將目標(biāo)包圍在其中(目標(biāo)在 3點(diǎn)確定的三角形內(nèi))。如圖 4所示,若ΔPAB,ΔPAC和ΔPBC的面積之和與ΔABC的面積相等,則可判定點(diǎn)P在ΔABC內(nèi)(包括在3條邊上的情況)。

圖4 面積和法示意圖Fig.4 Schematic diagram of Area-sum Method
設(shè)(xA,yA),(xB,yB)和(xC,yC)分別為 3 頂點(diǎn)A,B和C的坐標(biāo),ΔABC的面積可用下式計(jì)算:

因此,面積和法可表示為:

則當(dāng)δ=0時(shí),點(diǎn)P在ΔABC內(nèi);當(dāng)δ>0時(shí),點(diǎn)P不在ΔABC內(nèi),且δ越大,點(diǎn)P離ΔABC越遠(yuǎn)。若δ無(wú)限接近于0,即δ=0,則盟員選擇的精度指標(biāo)為:

綜合以上對(duì)能耗和精度的分析,可總結(jié)出盟員選擇的一般規(guī)則。
節(jié)點(diǎn)相對(duì)于目標(biāo)的位置如圖5所示,H為已選定的盟主,(ΔabH各邊長(zhǎng) 4次方之和)是所有選擇中最小的,然而a,b和H在目標(biāo)的同一側(cè),沒(méi)有包圍目標(biāo),此時(shí)定位精度較低。對(duì)于節(jié)點(diǎn)c和d,雖稍大于,但H,c和d不在目標(biāo)的同一側(cè),而是將目標(biāo)圍在3個(gè)節(jié)點(diǎn)組成的三角形之內(nèi),盡管此時(shí)c和d點(diǎn)距盟主的距離更遠(yuǎn),但定位精度卻更高。綜合考慮能耗與精度的情況下,應(yīng)選擇節(jié)點(diǎn)c和d,而不選擇節(jié)點(diǎn)a和b。即在圖5中,
(1)若與相當(dāng),或略大于,則選擇c和d作盟員;
(2)若遠(yuǎn)大于,則選擇a和b作盟員。因?yàn)楫?dāng)很大時(shí),不但通信能耗大,且測(cè)距誤差大了,導(dǎo)致定位誤差也增大,故不能選擇c和d,仍然選擇a和b較好。

圖5 節(jié)點(diǎn)相對(duì)于目標(biāo)的位置Fig.5 Node Location to target
將能耗指標(biāo)與精度指標(biāo)進(jìn)行加權(quán),從而得到綜合性能指標(biāo)函數(shù)。設(shè):


綜合性能指標(biāo)目標(biāo)函數(shù)為:

其中:α1和α2分別為J1和J2的權(quán)重,調(diào)節(jié)權(quán)重可達(dá)到最佳的跟蹤效果。在實(shí)際應(yīng)用中,也可根據(jù)能耗或精度的偏重,通過(guò)調(diào)節(jié)權(quán)重,達(dá)到應(yīng)用要求。
盟主盟員的選擇是一個(gè)尋找最優(yōu)解的過(guò)程。采用遺傳算法來(lái)實(shí)現(xiàn)此尋優(yōu)過(guò)程,并在 MATLAB中對(duì)多目標(biāo)跟蹤和盟主盟員選擇過(guò)程進(jìn)行仿真。
取100個(gè)采樣時(shí)刻,2個(gè)隨機(jī)運(yùn)動(dòng)的目標(biāo),運(yùn)動(dòng)場(chǎng)地長(zhǎng)×寬為100 m×100 m的矩形場(chǎng)地,共隨機(jī)分布256個(gè)節(jié)點(diǎn)。
遺傳算法中,設(shè)初始種群個(gè)體(即染色體)數(shù)為100個(gè),迭代次數(shù)為100代。每個(gè)節(jié)點(diǎn)采用8個(gè)2進(jìn)制位編碼,那么每條染色體(個(gè)體)有32個(gè)2進(jìn)制位。設(shè)交叉概率為0.9,變異概率為0.01。
圖6~9所示分別為僅考慮能耗、僅考慮精度及綜合考慮能耗和精度3種情況下的跟蹤軌跡圖、定位誤差圖、各代聯(lián)盟能量消耗圖、遺傳操作中每代最優(yōu)適應(yīng)值變化圖。在計(jì)算各代聯(lián)盟消耗的能量時(shí),各節(jié)點(diǎn)消耗的能量計(jì)算公式參見(jiàn)文獻(xiàn)[10]。
綜合考慮能耗和精度時(shí),由試驗(yàn)可得:α1取0.6,α2取0.4,β取10,跟蹤效果最佳,且在能耗與定位精度上取得較好的平衡。
比較圖6可知:不使用面積和法約束時(shí),目標(biāo)估測(cè)軌跡不光滑,某些估測(cè)點(diǎn)偏離實(shí)際點(diǎn)較遠(yuǎn),可認(rèn)為是錯(cuò)誤點(diǎn),跟蹤效果較差;運(yùn)用面積和法后,跟蹤效果有很大提高,而加權(quán)(圖 6(c2))又比硬性約束 (圖 6(b2))的跟蹤效果更好。比較圖 6(b1)和(c1)可見(jiàn):圖 6(b1)中的盟員比較發(fā)散,尤其是在運(yùn)動(dòng)軌跡的尾部,主要原因就在于硬性約束3個(gè)節(jié)點(diǎn)將目標(biāo)圍住使得選擇過(guò)程中可能舍棄較近的不能圍住目標(biāo)的點(diǎn),而選擇遠(yuǎn)很多的能圍住目標(biāo)的點(diǎn)。在這種情況下,目標(biāo)的定位精度不但沒(méi)有加大,反而減小,這也可從圖7(b)和7(c)看出。

圖6 盟主盟員選擇及目標(biāo)軌跡圖Fig.6 Selection of cluster head and member and tracks of targets
比較圖7中的3個(gè)子圖,不使用面積和法約束時(shí),定位誤差較大;使用面積和法后,定位誤差明顯減小,而加權(quán)(圖7(c))又比硬性約束(圖7(b))的誤差更小。這一規(guī)律與圖6所示的軌跡圖規(guī)律相符。

圖7 目標(biāo)0定位誤差Fig.7 Location error for target 0
圖8所示是任選某一時(shí)刻(本文選定第100時(shí)刻)各代聯(lián)盟能量消耗圖,即進(jìn)化的每一代中,具有最大適應(yīng)值的染色體對(duì)應(yīng)的4個(gè)節(jié)點(diǎn)作盟員,與各自的盟主組成聯(lián)盟,傳感器網(wǎng)絡(luò)消耗的總能量。從圖8可見(jiàn):經(jīng)過(guò)遺傳操作選出來(lái)的盟員,所對(duì)應(yīng)的聯(lián)盟消耗的能量越來(lái)越小,而且減小量非常顯著,大大減小了網(wǎng)絡(luò)能耗,證明綜合性能指標(biāo)函數(shù)的合理性,及用遺傳算法進(jìn)行盟員選擇的有效性。

表1 不同聯(lián)盟的盟員(目標(biāo)0)Table 1 Members of different clusters (target 0)

圖8 第100時(shí)刻各代聯(lián)盟消耗能量圖Fig.8 Energy consumption of every generation of cluster at 100th time

圖9 第30和60時(shí)刻每代最優(yōu)適應(yīng)值變化圖Fig.9 Change of every generation of best adaptive value at 30th and 60th time
同樣,比較圖8中的3個(gè)子圖可知:圖8(a)中由于不使用面積和法的限制,只考慮使節(jié)點(diǎn)間距4次方最小時(shí),所消耗的能量非常少(不超過(guò)2.5×105J)。而將面積和法作為1個(gè)硬性約束條件時(shí),能耗大大增加(幾乎達(dá)到15×105J),是前者的6倍多。加權(quán)形式(圖8(c)是較好的折中形式,雖然能耗與不使用面積和法時(shí)的相比有所增加,但比硬性約束時(shí)減少很多。這一規(guī)律也與圖6和圖7所示的規(guī)律一致。可見(jiàn):將“3個(gè)節(jié)點(diǎn)將目標(biāo)圍住”作為1個(gè)子目標(biāo)函數(shù),與能耗指標(biāo)進(jìn)行加權(quán),構(gòu)造出綜合性能指標(biāo)函數(shù),指導(dǎo)盟員的選擇,能達(dá)到既減小能耗又提高精度的目的,從而證明了本文綜合性能指標(biāo)函數(shù)設(shè)定的合理性。

表2 不同聯(lián)盟的盟員(目標(biāo)1)Table 2 Members of different clusters (target 1)
圖9所示是任選2個(gè)時(shí)刻(第30和60時(shí)刻),在3種情況下遺傳操作中每代最優(yōu)適應(yīng)值的變化圖。從圖9可見(jiàn):隨著進(jìn)化代數(shù)的增加,每代的最優(yōu)適應(yīng)值都呈上升趨勢(shì),直至找到最優(yōu)的4個(gè)節(jié)點(diǎn),此時(shí)最優(yōu)適應(yīng)值達(dá)到最大,并不再上升。這一規(guī)律與圖7中各代聯(lián)盟消耗能量逐漸減少的規(guī)律相符,進(jìn)一步證明了運(yùn)用遺傳算法選擇盟員的有效性,也證明了仿真中所選得盟員的正確性和最優(yōu)性。
(1)采用動(dòng)態(tài)聯(lián)盟機(jī)制進(jìn)行協(xié)同任務(wù)分配,論述了自組織動(dòng)態(tài)聯(lián)盟。分析能量消耗情況,建立能耗模型;介紹了3點(diǎn)定位法原理,分析了定位精度,建立精度模型。在此基礎(chǔ)上,將能耗模型與精度模型結(jié)合,構(gòu)造出綜合性能指標(biāo)函數(shù),指導(dǎo)盟員的選擇。最后,運(yùn)用遺傳算法實(shí)現(xiàn)了盟員選擇。
(2)在進(jìn)一步研究工作中,可采用不同的定位法,研究如何建立更合理的精度模型,且進(jìn)一步優(yōu)化能耗模型,以獲得更好的網(wǎng)絡(luò)綜合性能。
[1]CUI Li, JU Hai-ling, MIAO Yong, et al. Research development of wireless sensor networks[J]. Journal of Computer Research and Development, 2005, 42: 11-13.
[2]王永才. 傳感器網(wǎng)絡(luò)目標(biāo)跟蹤系統(tǒng)協(xié)同設(shè)計(jì)理論研究與應(yīng)用[D]. 北京: 清華大學(xué)自動(dòng)化系, 2006: 1-5, 24-31.WANG Yong-cai. Cooperative design of wireless sensor network target tracking system: A theoretical study and applications[D].Beijing: Tsinghua University. Department of Automation, 2006:1-5, 24-31.
[3]Tseng Y C, Kuo S P, Lee H W, et al. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies[J]. The Computer Journal, 2004, 47(4): 448-460.
[4]Kaplan L M. Transmission range control during autonomous node selection for wireless sensor networks[C]//2004 IEEE Aerospace Conference Proceedings, 2004: 2072-2087.
[5]ZHU Jing-hua, GAO Hong. An energy efficient algorithm for task allocation in wireless sensor networks[J]. Journal of Software, 2007, 18(5): 1198-1207.
[6]陳劍霞, 臧傳治, 梁韡, 等. 無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)協(xié)同任務(wù)分配機(jī)制[J]. 信息與控制, 2006, 35(2): 189-199.CHEN Jian-xia, ZANG Chuan-zhi, LIANG Wei, et al. A dynamic task allocation scheme for wireless sensor networks[J].Information and Control, 2006, 35(2): 189-199.
[7]陳劍霞. 基于動(dòng)態(tài)聯(lián)盟機(jī)制的無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配問(wèn)題研究[D]. 沈陽(yáng): 中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所, 2009: 88-98.CHEN Jian-xia. Research on task allocation in wireless sensor networks based on dynamic coalition mechanism[D]. Shenyang:Shenyang Institute of Automation Chinese Academy of Sciences,2009: 88-98.
[8]王睿, 梁彥, 潘泉, 等. 無(wú)線傳感器網(wǎng)絡(luò)信息感知中的自組織算法[J]. 自動(dòng)化學(xué)報(bào), 2006(5): 829-833.WANG Rui, LIANG Yan, PAN Quan, et al. A self-organization algorithm in wireless sensor net-works[J]. Acta Automatica Sinica, 2006(5): 829-833.
[9]Baek J, An S K, Fisher P. Dynamic cluster header selection and conditional re-clustering for wireless sensor networks[J].Consumer Electronics, IEEE Transactions on, 2010, 56(4):2249-2257.
[10]LI Hai-hao, LIU Mei, SHEN Yi, et al. Research on task allocation technique for multi-target tracking in wireless sensor network[C]//Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation, 2007: 360-365.
[11]孫利明. 無(wú)線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005:393-394.SUN Li-ming. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005: 393-394.
[12]He T, Huang C D, Blum B M, et al. Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proc of the 9th Annual Int’l Conf on Mobile Computing and Networking. San Diego: ACM Press, 2003: 81-95.
[13]文莎. 無(wú)線傳感器網(wǎng)絡(luò)多目標(biāo)智能跟蹤算法研究[D]. 廣州:廣東工業(yè)大學(xué)自動(dòng)化學(xué)院, 2010: 20-31.WEN Sha. Multi-target intelligent tracking algorithm in wireless sensor network[D]. Guangzhou: Guangdong University of Technology. School of Automation, 2010: 20-31.