馮冬青,邢凱麗

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

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

馮冬青,邢凱麗

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

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

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

0 引言

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

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

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

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

1 UKF算法

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

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

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

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

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

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

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

2.1 采用改進的BPSO進行跟蹤傳感器的選擇

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

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

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

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

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

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

首先選擇離目標最近的節(jié)點作為初始簇頭CH0.從Γk+1中調(diào)度部分節(jié)點形成一個候選簇=={,∈Γ,CH"為C′的簇頭,為k+1k+1k+1中簇成員節(jié)點集合.工作區(qū)域內(nèi)節(jié)點的能量消耗源于簇頭CHk發(fā)送目標狀態(tài)估計值和方差到下一時刻簇頭CHk+1,簇成員節(jié)點感知目標并發(fā)送測量值到簇頭,簇頭感知目標并接收CHk發(fā)送的目標狀態(tài)估計值和方差,同時接收發(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(·)為兩點間距離函數(shù).則簇C′k+1內(nèi)總能耗為

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

從而,第k+1時間步工作區(qū)域節(jié)點的剩余能量的標準差為

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

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

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

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

2.3 算法步驟

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

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

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

(4)對第i個粒子,進行如下操作:?使用公式(5)對其速度進行更新;如果速度Vi越過邊界［-Vmax,Vmax］,則將Vi設(shè)為邊界;?使用公式(7)對粒子位置進行更新;?對第i個粒子的新位置進行評估.如果(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時間步的最優(yōu)簇Ck+1.如果Ck+1=φ,則執(zhí)行(1).

3 實驗及分析

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

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

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

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

國家自然科學基金資助項目(60973094)

馮冬青(1958-),男,廣東佛山人,鄭州大學教授,博士,主要研究領(lǐng)域為智能控制理論與應(yīng)用,E-mail: dqfeng@zzu.edu.cn.