馮冬青,邢凱麗

(鄭州大學(xué)電氣工程學(xué)院,河南鄭州450001)

基于能量平衡的無線傳感器網(wǎng)絡(luò)分布式成簇機(jī)制

馮冬青,邢凱麗

(鄭州大學(xué)電氣工程學(xué)院,河南鄭州450001)

針對資源有限的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤問題，采用一種基于能量平衡的最優(yōu)分布式成簇機(jī)制，為此引入了基于節(jié)氛剩余能量標(biāo)準(zhǔn)差的能量平衡指標(biāo)，將其轉(zhuǎn)化為多目標(biāo)約束優(yōu)化問題，并采用二進(jìn)制粒子群優(yōu)化算法求取最優(yōu)解.Matlab仿真結(jié)果表明，與基于能耗和擴(kuò)展卡爾曼濾波的成簇機(jī)制相比，采用基于能量平衡的最優(yōu)成簇機(jī)制能在保證跟蹤精度和能量平衡的前提下，提高網(wǎng)絡(luò)壽命近2倍，從而有效地延長了網(wǎng)絡(luò)壽命.

無線傳感器網(wǎng)絡(luò);目標(biāo)跟蹤;能量平衡;成簇;網(wǎng)絡(luò)壽命

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)是一種新興的自組織網(wǎng)絡(luò),它在目標(biāo)跟蹤領(lǐng)域有著良好的應(yīng)用前景.實(shí)際應(yīng)用中,因傳感器節(jié)點(diǎn)的感知半徑、存儲、通信、數(shù)據(jù)處理能力、網(wǎng)絡(luò)帶寬及節(jié)點(diǎn)能量都十分有限,所以必須動態(tài)地管理調(diào)度網(wǎng)絡(luò)資源來進(jìn)行協(xié)同信號與信息處理［1］.

WSNs應(yīng)用于目標(biāo)跟蹤時(shí),通過分簇機(jī)制來優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),從而達(dá)到均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)壽命的目的.文獻(xiàn)［2-4］中分簇機(jī)制僅僅考慮了網(wǎng)絡(luò)總能耗而忽略了能量平衡,從而容易導(dǎo)致網(wǎng)絡(luò)出現(xiàn)斷連、信息丟失等現(xiàn)象.目前,有些文獻(xiàn)提出了基于能量平衡的分簇機(jī)制,如文獻(xiàn)［5］基于簇頭間能量平衡來延長網(wǎng)絡(luò)覆蓋時(shí)間;文獻(xiàn)［6］建立了一種能量平衡模型,并考慮了網(wǎng)絡(luò)總能耗和簇頭與簇盟員節(jié)點(diǎn)剩余能量差;文獻(xiàn)［7］通過最小化最大的任務(wù)節(jié)點(diǎn)間剩余能量的能耗差來平衡監(jiān)測區(qū)域內(nèi)局部能量.但是,文獻(xiàn)［5-7］只考慮了部分任務(wù)節(jié)點(diǎn)的能量平衡,未考慮到網(wǎng)絡(luò)壽命與每個節(jié)點(diǎn)的剩余能量有關(guān),因此,這些分簇機(jī)制仍可能會導(dǎo)致整個網(wǎng)絡(luò)能量分布不平衡,縮短網(wǎng)絡(luò)壽命.鑒于此,筆者采用工作區(qū)域內(nèi)節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差來衡量網(wǎng)絡(luò)能量平衡程度,進(jìn)而引人了一種新的能量平衡指標(biāo),不僅節(jié)省總能耗,而且兼顧考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量的分布程度.

另一方面,當(dāng)前用于解決非線性條件下目標(biāo)跟蹤問題的濾波方法中,無跡卡爾曼濾波(UKF)的應(yīng)用較為廣泛.為了提高UKF的跟蹤精度,需要調(diào)度多個任務(wù)傳感器節(jié)點(diǎn)去感知目標(biāo),這樣會增加網(wǎng)絡(luò)消耗,縮短網(wǎng)絡(luò)壽命.

綜上所述,為了尋找一種最優(yōu)成簇機(jī)制,需綜合考慮影響網(wǎng)絡(luò)壽命的能量平衡和跟蹤精度這兩個因素.筆者將其轉(zhuǎn)化為多目標(biāo)約束優(yōu)化問題,并采用了二進(jìn)制粒子群優(yōu)化算法尋求最優(yōu)解.

1 UKF算法

筆者采用式(1)目標(biāo)狀態(tài)模型:

式中:X(k)為k時(shí)刻系統(tǒng)的狀態(tài)向量;W(k)是均值為零、協(xié)方差矩陣為Qk的狀態(tài)高斯白噪聲.

假設(shè)WSNs是由一組同構(gòu)傳感器節(jié)點(diǎn)隨機(jī)分布組成的,各個節(jié)點(diǎn)的坐標(biāo)位置是已知的,而且其探測半徑r相同.在第k時(shí)間步有Nk個節(jié)點(diǎn)被喚醒探測目標(biāo),其中調(diào)度Lk個節(jié)點(diǎn),形成任務(wù)簇,其測量模型如下:

式中:Z(k)為測量向量;V(k)是均值為零、協(xié)方差矩陣為Rk的測量高斯白噪聲.

針對目標(biāo)狀態(tài)模型(1)和測量模型(2),筆者采用UKF實(shí)現(xiàn)對目標(biāo)狀態(tài)的預(yù)測估計(jì),具體公式見文獻(xiàn)［8］.系統(tǒng)在獲取k+1時(shí)刻的測量值后,通過UKF得到了k+1時(shí)刻的狀態(tài)的估計(jì)值和協(xié)方差從而目標(biāo)狀態(tài)估計(jì)的均方誤差可表示為

2 能量平衡的最優(yōu)成簇機(jī)制

目標(biāo)進(jìn)人監(jiān)測區(qū)域后,首先被傳感器節(jié)點(diǎn)內(nèi)置的被動紅外傳感器探測到,其喚醒所屬的傳感器節(jié)點(diǎn),被喚醒的Nk+1個節(jié)點(diǎn)構(gòu)成候選簇員集合Γ=之后,喚醒節(jié)點(diǎn)根據(jù)自身位置k+1和能量給出回復(fù)信息,上一簇頭CHk根據(jù)回復(fù)信息按照某種成簇機(jī)制調(diào)度部分喚醒節(jié)點(diǎn)形成下一簇C,包括簇頭CH和簇盟員的k+1k+1選擇;最后CHk將目標(biāo)狀態(tài)和方差發(fā)送給CHk+1.簇Ck+1形成后,各簇員節(jié)點(diǎn)執(zhí)行目標(biāo)感知任務(wù),簇盟員節(jié)點(diǎn)發(fā)送測量值到CHk+1,CHk+1根據(jù)UKF算法估計(jì)目標(biāo)位置.在目標(biāo)的移動過程中,將動態(tài)地生成新的簇來實(shí)時(shí)跟蹤.

2.1 采用改進(jìn)的BPSO進(jìn)行跟蹤傳感器的選擇

PSO算法中第i個粒子在第t代的狀態(tài)表示為

式中:D為待求解問題維數(shù);Xi(t)和Vi(t)為粒子群中第i個粒子在第t代的位置和速度.

第i粒子在D維搜索空間中飛行狀態(tài)的速度和位置更新為:

BPSO算法［9］將粒子的位置定義為一個二進(jìn)制的1/0串,來表示候選傳感器被選擇與未被選擇的信息.不同于式(6),由于BPSO中處理的是離散變量,所以不能通過算術(shù)的方式對位置和速度進(jìn)行相加,需要適當(dāng)?shù)匦薷?

2.2 適應(yīng)度函數(shù)的構(gòu)造

在目標(biāo)跟蹤成簇過程中,能量消耗集中在上一時(shí)刻簇頭和目標(biāo)探測范圍內(nèi)的節(jié)點(diǎn)上(即工作區(qū)域).因此,筆者在衡量網(wǎng)絡(luò)能量平衡程度時(shí),采用了工作區(qū)域內(nèi)節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差,并通過確保網(wǎng)絡(luò)能量平衡性來延長網(wǎng)絡(luò)壽命.

首先選擇離目標(biāo)最近的節(jié)點(diǎn)作為初始簇頭CH0.從Γk+1中調(diào)度部分節(jié)點(diǎn)形成一個候選簇=={,∈Γ,CH"為C′的簇頭,為k+1k+1k+1中簇成員節(jié)點(diǎn)集合.工作區(qū)域內(nèi)節(jié)點(diǎn)的能量消耗源于簇頭CHk發(fā)送目標(biāo)狀態(tài)估計(jì)值和方差到下一時(shí)刻簇頭CHk+1,簇成員節(jié)點(diǎn)感知目標(biāo)并發(fā)送測量值到簇頭,簇頭感知目標(biāo)并接收CHk發(fā)送的目標(biāo)狀態(tài)估計(jì)值和方差,同時(shí)接收發(fā)送的測量值.根據(jù)傳感器能耗模型［10］,CHk、、CH"k+1的能耗分別為

式中:ut、ud及ur均為常數(shù),其中ut和ud由發(fā)送端配置［10］,ur由接收端配置［10］;us為傳感器感知單位數(shù)據(jù)消耗的能量;b1為CHk發(fā)送數(shù)據(jù)位數(shù), b2i、b2分別為、CH"k+1所獲測量值位數(shù); d(·)為兩點(diǎn)間距離函數(shù).則簇C′k+1內(nèi)總能耗為

下面通過內(nèi)搜索方法,確定該候選簇C′k+1中最優(yōu)的簇頭CH′k+1和盟員節(jié)點(diǎn)CM′k+1,

從而,第k+1時(shí)間步工作區(qū)域節(jié)點(diǎn)的剩余能量的標(biāo)準(zhǔn)差為

其中,std(·)是標(biāo)準(zhǔn)差函數(shù).引人一個新的能量平衡指標(biāo)

其中,ε1∈［0,1］為權(quán)重參數(shù),用來折中總能耗與能量平衡.此外根據(jù)式(3),候選簇C′k+1對應(yīng)的跟蹤精度為f′k+1,2=tr(.

在WSNs目標(biāo)跟蹤過程中,由于成簇的基本準(zhǔn)則是保證良好的能量平衡和較高的跟蹤精度,因此,基于BPSO算法的最優(yōu)成簇機(jī)制的適應(yīng)度函數(shù)是對f′k+1,1和f′k+1,2的加權(quán)和,如式(20)所示:轉(zhuǎn)(4).

式中:ε2∈［0,1］,為權(quán)重參數(shù);γ是能量匹配因子,使能量平衡指標(biāo)與跟蹤精度有相同的數(shù)量級.

2.3 算法步驟

通過前面的分析,能量平衡的最優(yōu)成簇問題最終轉(zhuǎn)化成從喚醒節(jié)點(diǎn)中尋求一個滿足min的候選簇.基于BPSO算法的最優(yōu)成簇機(jī)制具體實(shí)現(xiàn)如下.

(1)當(dāng)Γk+1=φ時(shí),Ck+1=CHk,否則執(zhí)行步驟(2).

(2)初始化.對種群的M個粒子進(jìn)行隨機(jī)初始化.第i個粒子的位置Xi(t)隨機(jī)初始化為二進(jìn)制1,0串;速度Vi(t)初始化為［-Vmax,Vmax］之間的隨機(jī)向量.設(shè)置參數(shù)c1=c2=2.0,當(dāng)前代數(shù)t=0.

(4)對第i個粒子,進(jìn)行如下操作:?使用公式(5)對其速度進(jìn)行更新;如果速度Vi越過邊界［-Vmax,Vmax］,則將Vi設(shè)為邊界;?使用公式(7)對粒子位置進(jìn)行更新;?對第i個粒子的新位置進(jìn)行評估.如果(Xi(t+1))＜(Pi),則Pi=Xi(t+1);那么(Pi)＜(Pg),則Pg=Pi.

(5)t=t+1.如果t＞Max Gen,則轉(zhuǎn)(6),否則

(6)輸出Pg.最后尋出第k+1時(shí)間步的最優(yōu)簇Ck+1.如果Ck+1=φ,則執(zhí)行(1).

3 實(shí)驗(yàn)及分析

在Matlab環(huán)境下,筆者對以下3種成簇機(jī)制進(jìn)行了對比實(shí)驗(yàn):①基于能量平衡的最優(yōu)成簇機(jī)制(CSEB),即筆者所提出的成簇機(jī)制;②基于能耗的成簇機(jī)制(CSBQN),此機(jī)制僅考慮了能耗,式(19)中ε1=1;③基于擴(kuò)展卡爾曼濾波(EKF)的成簇機(jī)制(CSEKF),與CSEB相比,采用了EKF濾波算法.

3.1 仿真參數(shù)設(shè)置

在100 m×100 m的矩形監(jiān)測區(qū)域內(nèi),隨機(jī)散布50個傳感器節(jié)點(diǎn),每個節(jié)點(diǎn)的探測半徑r= 20 m,除了節(jié)點(diǎn)6#、11#、12#和29#的初始能量設(shè)為0.2 J外,其余節(jié)點(diǎn)的均設(shè)為0.5 J,以構(gòu)成一個能量不平衡的網(wǎng)絡(luò),終止代數(shù)為20,其他參數(shù)設(shè)置見表1.其中ε1選取為0.5,在式(19)中,總能耗與能量平衡對f′k+1,1的影響均衡.若ε1選取得過大,會導(dǎo)致簇內(nèi)某節(jié)點(diǎn)能耗過多使得網(wǎng)絡(luò)出現(xiàn)斷連、能量空洞、信息丟失;ε1選取得過小,忽略成簇機(jī)制總能耗,則會造成能源浪費(fèi).

整個實(shí)驗(yàn)仿真時(shí)間是50個時(shí)間步,目標(biāo)在0～10,24～27,40～50時(shí)間步內(nèi)做線性運(yùn)動,其他時(shí)間步內(nèi)做圓弧運(yùn)動.

表1 仿真參數(shù)設(shè)置Tab.1 Setting of simulation parameters

3.2 仿真結(jié)果分析

圖1表示CSEB下的目標(biāo)跟蹤,與實(shí)際目標(biāo)之間用虛線相連的小三角表示該傳感器節(jié)點(diǎn)被選為了簇頭.圖2給出了3種機(jī)制下相應(yīng)的跟蹤誤差.在線性運(yùn)動階段,3種機(jī)制都能較好地跟蹤目標(biāo);在圓弧階段,CSEB、CSBQN仍能較好地跟蹤目標(biāo),然而CSEKF已不能較好地跟蹤目標(biāo),跟蹤軌跡偏離了實(shí)際軌跡.因此,UKF相比EKF來說,在復(fù)雜的非線性運(yùn)動中有更好的跟蹤精度.

圖1 CSEB機(jī)制下的跟蹤效果Fig.1 Tracking trajectory under CSEB

圖2 不同成簇機(jī)制下的跟蹤誤差比較Fig.2 Tracking errors comparison under different clustering mechanisms

圖3給出了不同成簇機(jī)制下各時(shí)間步在工作區(qū)域內(nèi)節(jié)點(diǎn)的剩余能量標(biāo)準(zhǔn)差.CSEB和CSEKF為了保證能量平衡,在調(diào)度節(jié)點(diǎn)時(shí)可能會選擇距離目標(biāo)較遠(yuǎn)的節(jié)點(diǎn),而未選擇距離目標(biāo)較近但剩余能量較少或是調(diào)度次數(shù)較多的節(jié)點(diǎn);CSBQN為了減少能耗會調(diào)度較少且距離目標(biāo)較近的節(jié)點(diǎn),一些節(jié)點(diǎn)如6#、12#、29#會被多次調(diào)度,所以CSBQN的標(biāo)準(zhǔn)差比CSEB和CSEKF都大.上述結(jié)果表明,與CSEKF和CSBQN相比,CSEB能較好地完成非線性運(yùn)動目標(biāo)跟蹤,同時(shí)還保證了網(wǎng)絡(luò)能量的平衡性.

圖4給出了完成目標(biāo)跟蹤后3種機(jī)制下的節(jié)點(diǎn)剩余能量.表2給出了不同機(jī)制下整個網(wǎng)絡(luò)的總能耗、總剩余能量和網(wǎng)絡(luò)壽命.在CSBQN中,節(jié)點(diǎn)6#在完成跟蹤任務(wù)之前其剩余能量已經(jīng)不足以去實(shí)現(xiàn)跟蹤,它的網(wǎng)絡(luò)壽命只有17時(shí)間步(見表2);然而,CSEB和CSEKF均考慮了能量平衡,很少調(diào)度節(jié)點(diǎn)6#和12#來避免節(jié)點(diǎn)死亡,其網(wǎng)絡(luò)壽命大于50時(shí)間步.此結(jié)果表明,CSEB能夠在保證能量平衡的前提下延長網(wǎng)絡(luò)壽命.

圖3 不同成簇機(jī)制下工作區(qū)域內(nèi)節(jié)點(diǎn)的剩余能量標(biāo)準(zhǔn)差Fig.3 Standard deviations of the residual energy in the working area at each time step under different clustering mechanisms

圖4 不同機(jī)制下節(jié)點(diǎn)剩余能量的比較圖Fig.4 Node residual energy comparison under different clustering mechanism s

表2 不同機(jī)制下整個網(wǎng)絡(luò)的總能耗、總剩余能量和網(wǎng)絡(luò)壽命Tab.2 Total energy consumptions，total residual energy and network lifetime of the network under different mechanisms

4 結(jié)論

在無線傳感器網(wǎng)絡(luò)資源有限的前提下實(shí)現(xiàn)對目標(biāo)的實(shí)時(shí)跟蹤是一項(xiàng)極具挑戰(zhàn)性的任務(wù).筆者采用了一種能量平衡的最優(yōu)分布式成簇機(jī)制,與基于能耗和擴(kuò)展卡爾曼濾波的成簇機(jī)制相比,此機(jī)制能在保證跟蹤精度和能量平衡的前提下,提高網(wǎng)絡(luò)壽命近2倍,從而有效地延長了網(wǎng)絡(luò)壽命.該機(jī)制容忍了能量不平衡網(wǎng)絡(luò),并通過確保網(wǎng)絡(luò)能量平衡性來有效地延長網(wǎng)絡(luò)壽命,同時(shí)又保證了跟蹤精度,有效地避免了網(wǎng)絡(luò)能量不平衡.

［1］ THARMARASA R,KIRUBARAJAN T,SINHA A,et al.Decentralized sensor selection for large-scalemu ltisensor-multitarget tracking［J］.IEEE Transactions on Aerospace and Electronic Systems,2011,47(2): 1307-1324.

［2］ LIU Xue-feng,CAO Jian-nong,LAIS,et al.Energy efficient clustering for WSN based structural health monitoring［C］//Proceedings of IEEE Con ference on Computer Communication.Shanghai:IEEE Press, 2011:2768-2776.

［3］ MAHMUD S,WU Hui,XUE Jing-ling.Efficient energy balancing aware multiple base station deployment forWSNs［C］//Proceedings of 8th European Conference on W ireless Sensor Networks.Berlin:Springer, 2011:179-194.

［4］ AMINI N,VAHDATPOUR A,XU Wen-yao,et al. Cluster size optimization in sensor networks with decentralized cluster based protoco-ls［J］.Computer Communications,2012,35(2):207-220.

［5］ SHU T,KRUNZ M.Coverage-time optimization for clustered wireless sensor networks:a power-balancing approach［J］.IEEE/ACM Transactions on Networking,2010,18(1):202-215.

［6］ LIU Yong-gui,XU Bu-gong,FENG Lin-fang.Energybalanced multiple sensor collaborative scheduling for maneuvering target tracking in wireless sensor networks［J］.Journal Control Theory Application,2011,9 (1):58-65.

［7］ ZHANG Jian,WU Cheng-dong,ZHANG Yun-zhou, et al.Energy-efficient adaptive dynamic sensor scheduling for targetmonitoring in wireless sensor networks［J］.ETRI Journal,2011,33(6):857-863.

［8］ JULIER S J,UHLMAN J K.Unscented filtering and nonlinear estimation［J］.IEEE Trans Automat Contr, 2004,92(3):401-422.

［9］ SHIRIN K,KARIM F,AMJAD O.Modified discrete binary PSO based approach to sensor placement in WSN networks［C］//Proc of the International Conference on Computational Intelligence and Communication Systems.Bhopal:IEEE Press,2010:200-204.

［10］LIN Jian-yong,XIAO Wen-dong,LEW IS F L,et al. Energy efficient distributed adaptive multi-sensor scheduling for target tracking in wireless sensor networks［J］.IEEE Transactions on Instrumentation and Measurement,2009,58(6):1886-1896.

A Distributed Clustering Mechanism Based on Energy Balance in Wireless Sensor Networks

FENG Dong-qing,XING Kai-li
(School of Electrical Engineering,Zhengzhou University,Zhengzhou 450001,China)

Focusing on the target tracking problem in resource-constrained wireless sensor networks,a novel energy-balanced optimal distributed clustering mechanism is adopted by introducing an energy-balanced index based on the standard deviation of residual energy of nodes.Then,it is transformed into a multi-objective constrained optimization problem,and a binary particle swarm optimization algorithm is employed to solve this problem.Simulation results in Matlab environment show that the energy-balanced optimal distributed clustering mechanism guarantees energy balance and tracking accuracy comparing with the clustering mechanisms respectively based on the energy consumption and the extended Kalman filter,and that it improves the network lifetime of nearly 2-fold,effectively prolonging the network lifetime.

wireless sensor network;target tracking;energy balance;clustering;network lifetime

TP393

A

10.3969/j.issn.1671-6833.2015.03.002

1671-6833(2015)03-0006-05

2015-01-20;

2015-02-04

國家自然科學(xué)基金資助項(xiàng)目(60973094)

馮冬青(1958-),男,廣東佛山人,鄭州大學(xué)教授,博士,主要研究領(lǐng)域?yàn)橹悄芸刂评碚撆c應(yīng)用,E-mail: dqfeng@zzu.edu.cn.