負載均衡的高效傳感器網絡非均勻路由算法

劉雅娜，黃戰華

(1.石家莊學院 理學院，河北 石家莊 050035；2.河北師范大學 職業技術學院，河北 石家莊 050024)

0 引 言

為了延長整個WSN的生命期[1-3]，許多研究人員開發了有效的網絡協議，使全網的傳感器能耗均衡，從而延長全網的生命期[4]。WSN的路由協議主要分為平面型路由協議與分層型路由協議兩種[5]，平面型協議需要維持較大的路由表，占據較大的存儲空間，因此并不適用于大規模的WSN中；而分層路由協議則通過相對較低的成本達到最大化網絡生命期的目標[6]。

LEACH算法[7]是一個經典分簇路由協議，該協議采用分簇結構、本地數據聯合處理以及動態分配簇頭來實現網絡的能耗均衡，但LEACH并未考慮節點的剩余能量、簇頭分布等重要因素，因此性能一般。此外許多文獻對LEACH算法進行了優化，逐漸地提高了LEACH協議的性能[8-10]。文獻[11]提出一種基于粒子群的WSN分簇路由協議(PCR)，該協議充分地考慮了全網節點的剩余能量，有效地平衡了節點的能耗，其實驗結果表明，該算法優于許多主流的WSN路由協議。文獻[12]則進一步考慮了由控制消息傳輸所引起的能耗，以及基站附近的中繼簇頭容易過早死亡的問題，提出了一種去中心化的分簇路由協議(簡稱為DCR)。

MOIA算法(多目標免疫算法)是繼遺傳算法后的又一個重要的演化算法，MOIA具有幾個特性[13,14]：①具有全局的搜索能力；②解集在收斂性、多樣性、分布均勻性方面均具有較好的性能；③對于多目標約束的優化問題具有較好的健壯性；④可針對不同的目標問題，將種群大小調節至合理的大小，降低了目標評價函數的調用次數；⑤計算成本較低。

多跳的路由協議中，基站遠端的簇頭將基站附近的簇頭作為中繼節點，因此基站附近的簇頭能耗高于遠端的簇頭，該情況稱為WSN的“熱點”問題。為了解決“熱點”問題，本文設計了一種非均勻的分簇方案，基于區域與基站的距離以及節點的剩余能量值將整個區域劃分為不同大小的簇，然后采用多目標免疫算法，在保證節點間連接性與最小化所有節點通信成本的條件下，搜索最優的分簇方案并建立最優的路由樹。為了節約計算開銷與時間開銷，僅當當前簇頭的剩余能量值低于指定閾值的情況下，才設置新簇頭。基于多組仿真實驗的結果表明，本算法有效地提高了網絡生命期，解決了“熱點”問題，并平衡了網絡中節點的能耗，此外，本協議計算復雜度較低。

1 本文符號

假設WSN由一個BS(基站)與N個傳感節點組成，分布于M1×M2的目標區域，首先作以下假設：①BS資源豐富，其消息可發送至網絡中所有節點；②所有傳感節點與BS是固定的；③所有傳感器有一個ID；④傳感節點具有能量控制機制，可根據傳輸距離調節發送的能量大小；⑤簇內的感知信息關聯性高且可以融合，而簇間數據相差較大。

1.1 能耗模型

圖1所示是WSN的無線通信模型，將k比特消息傳輸距離d的無線成本計算為

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=kEelec+EAmpkdp

(1)

接收該消息的無線成本為

ERx(k)=ERx-elec(k)=kEelec

(2)

ESen(k)=kEsensing

(3)

因為簇內采集的信息十分相似，所以簇頭(CH)可將不同節點的數據聚集為一個固定長度的數據包，聚集m個k比特的數據所引起的能耗計算為

Eagg(k)=mkEDA

(4)

假設網絡分為L個簇，每個簇包含mi=(i=1,2,…,L)個成員節點，每個傳感節點的數據包長度為k比特，簇內成員節點需采集數據并將數據傳遞至CH。所以簇內成員節點l通信的能耗為

Emen-i(l,k,d)=Esen(k)+ETx(k,d)=
(kEsensing)+(kEelec+EAmpk(d(l,i)p))

(5)

式中：d(l,i)是l與簇頭i之間的距離。CH的能耗則包括簇內、簇間通信兩部分，式(6)是CH的總能耗

ECH(i,k,d)=kEsensing+kEelecmi+kEDA(mi+1)+
kEelecrelay(i)+(relay(i)+1)(kEelec+EAmpk(d(i,NH))p)

(6)

式中：d(i,NH)是CH節點i與下一跳之間的距離，relay(i)是轉發其它CH中繼數據包的數量。

圖1 WSN的無線通信模型

1.2 連接模型

為了保證傳感節點間的連接，本協議的簇頭應當覆蓋網絡的所有節點。簇頭CHi(xi,yi)覆蓋傳感節點snl(xl,yl)的表達式可描述為

(7)

網絡共有L個簇頭，所以節點snl被覆蓋的概率為

(8)

最終，將簇頭覆蓋的傳感器數量與網絡中總的活動節點數量(Nlive)的比例作定義為覆蓋率(RCov)，如下計算

(9)

1.3 問題模型

協議將網絡分簇為非均勻的L個簇，目標是滿足節點間連接的情況下，最小化網絡的通信成本，并平衡節點間的負載。本文WSN分簇路由協議主要有以下目標：

目標1：最小化協議每輪簇內所有節點的能耗

(10)

式中：ECH_CP(i,kCP,d)與Emem,CP-i(l,kCP,d)分別是簇頭i成員節點l數據包所引起的能耗。

目標2：在網絡中每個節點在與CH連接的前提下，最小化未覆蓋傳感節點的比例

min(RUncov=1-RCov)

(11)

目標3：搜索能耗最低的最優簇頭數量CHs(L)，目標函數為

min(NCH=L/N)

(12)

最終，將3個目標總結為以下的總目標函數

F=w1Edisp+w2RUncov+w3NCH

(13)

式中：w1、w2與w3是權重因子，范圍均為[0,1]，且w1+w2+w3=1。本文的第二個目標是使用非均勻分簇機制調節CH的簇內與簇間能耗來平衡節點的負載。

2 基于免疫的非均勻分簇路由協議

多跳路由具有“熱點”問題，分簇網絡中能耗不平衡的原因主要有兩個：CH與成員節點的能耗不同；BS附近的CH中繼遠端CH數據包需要更多的能耗。本協議解決熱點問題并平衡所有傳感節點的能耗，具體方法為：①采用MOIA算法選擇剩余能量較多的節點作為簇頭，選擇最優的簇頭數量，為每個CH建立一個路由樹，確保網絡的連接并最小化數據與控制報文的開銷；②周期地改變網絡的CH；③根據各簇與BS的距離將網絡分為非均勻的大小，并調節CH的簇內與簇間能耗；④從每個CH到BS的路由集中根據剩余能量與路由跳數選擇最優的下一跳；⑤考慮簇建立階段的距離與剩余能量。

如圖2所示，本協議中每輪包含兩個階段：第一階段為簇建立階段(T1)，BS建立一個最優分簇方案與每個簇頭的路由樹；第二階段為數據傳輸階段(T2(T2>>T1))。為了減少簇建立階段控制報文極大的計算開銷與時間，僅當上一輪中CH的剩余能量低于閾值(Eth)觸發簇建立階段。密集型網絡中搜索最優CH集合計算時間較長，所以本協議將傳感區域劃分為若干個虛擬網格，并選擇各虛擬網絡中剩余能量較高的節點建立候選傳感器集(S)；然后，BS使用MOIA算法從集合S中選擇最優的CH，同時，選擇與每個CH最近的節點作為副CH，如果CH發生故障，則將副CH代替CH。圖3所示是本協議的流程。

圖2 本協議的時序

圖3 本協議的總體流程

2.1 信息收集階段

僅在第一輪的開始進行信息收集，BS收集所有節點的信息并將傳感區域劃分為若干個虛擬網格。首先，BS廣播一個消息Reqst_Msg(ID,xBS,yBS)(其中包含其位置與ID)；收到該消息的節點回復一個消息Self_Info_Msg(ID,location,E0)(包含ID、位置與初始化能量(E0))，BS將所有節點的狀態設為普通節點并將全網信息保存，分簇完成后，節點設為CH或成員節點。然后，BS將目標區域劃分為ngrids個虛擬網格，如圖4所示，ngrids值的計算方法如下所示

ngrids=ngrids_x×ngrids_y

(14)

式中：ngrids_x與ngrids_y分別是水平軸與垂直軸的虛擬網格數量，分別如下計算

(15)

圖4 虛擬網格劃分

2.2 分簇建立階段

在簇建立階段，BS建立最優的分簇方案并為每個簇頭建立一個路由樹。首先，基于每個節點與BS的距離及其剩余能量計算節點的Rc，計算方法如下

Rc(l)=

(16)

式中：l=1,2,…,Nlive，dmaxBS與dminBS分別是節點與BS間最長與最近的距離，d(l,BS)是節點l與BS的距離，Eres是節點的剩余能量，Emax是節點的最大剩余能量，α與β是[0,1]區間的常量，且α+β≤1。分析式(16)可看出，α、β與Rmax影響簇(Rc)的大小，Rmax是決定CH數量的關鍵參數，α與β則決定了節點-BS距離與剩余能量的權重。

BS使用MOIA算法搜索集合S中最優的CH與VCH，之后，每個CH中建立一個路由樹，簇內路由的目標是最小化數據與控制報文的通信成本，因為控制報文能耗較大，所以本協議在CH選擇程序中考慮控制消息的能耗。每輪CH與成員節點控制報文的能耗如下計算

ECH_CP(i,kCP,d)=2kCPEelec+kCPEelecmi+

(kCPEelec+EfskCP(Rc(i))p)

(17)

Emem_CP-i(l,kCP,d)=3kCPEelec+kCPEelec+EfskCP(d(l,i))p

(18)

2.2.1 簇頭的選擇

本協議采用MOIA搜索最優的CH與VCH，算法1所示是MOIA的主要步驟。

算法1: MOIA的主要步驟

輸入：集合S中傳感器的ID，位置與Eres

輸出：主副簇頭的ID

(1)設置免疫算法的參數；

(2)初始化種群；

(3)計算種群的目標函數值；

(4)WHILE(未達到結束條件) {

(5)gen=gen+1；

(6)pop_sel=RWS_selection(pop)；//輪盤賭選擇種群

(7)pop_rep=replication(pop_sel)；//復制操作

(8)pop_clon=clone(pop_sel)；//克隆操作

(9)pop_hyper=hypermutation(pop_clon)；//高頻變異

(10)pop_total=[pop_rep,pop_hyper]；//合并種群

(11)pop_off=mutation(pop_total)；//變異操作

(12)evaluate(pop_off)；//計算種群目標函數值

(13)pop=const_pop(pop,pop_off)；//建立下一代種群

(14)}

2.2.1.1 抗體種群的生成

將CH數量與其位置作為優化的目標參數，首先BS從每個虛擬網絡選擇剩余能量高于全網節點平均能量(Eavg)的傳感器集合(S={s1,s2,…,sngen}(sngen≤N))，其中nvg(0≤nvg≤ngen/ngrids)，表示為下式

S={G1,G2,…,Gg,…,Gngrids}

(19)

式中：Gg是虛擬網格g的傳感器集合，表示為

Gg={s1,s2,…,snvg}={snl|?l∈[1Nlive]∧snl
∈Grid(g)∧Eres(l)≥Eavg}, (g=1,2,…,ngrids)

(20)

之后，BS使用二進制流將集合S內的節點編碼，形成ps個抗體的種群，pop=(X1;X2;…;Xm;…;Xps)。每個CH抗體Xm為ngen個比特，每個比特(xb)對應S中一個傳感器，1表示CH，0為普通節點。

2.2.1.2 種群評價函數

傳感器的大部分能耗由通信引起[15]，因此每個抗體使用目標函數式(13)進行評價。

2.2.1.3 抗體選擇

2.2.1.4 復制操作

2.2.1.5 高頻變異的克隆擴增

2.2.1.6 變異操作

2.2.1.7 種群更新

(21)

2.2.1.8 結束條件

MOIA算法的結束條件定義為連續迭代之間種群F值變化不明顯或者達到最大的迭代次數，表示為下式

pop*=

(22)

2.2.2 建立路由樹

上文采用免疫算法獲得了最優的簇頭集，然后為每個簇頭建立一個路由樹，最小化簇內的能耗。本協議的目標是為每個CH選擇最優的下一跳節點(NHbest)，每個CHi的NHbest應當保證連接性并節約能耗，總結為以下條件：①NH應當在其通信范圍內(d(i,NHbest)≤Rr(i))；②NH應當在CHi到BS的方向上(d(NHbest,BS)

(23)

2.2.3 副簇頭的選擇

BS選擇與各CH最近的節點作為副簇頭(VCH)，簇頭發生則采用VCH代替簇頭，具體方法為BS發送CH_STAT_MSG(NH_ID,VCH_ID,RC)消息將節點狀態從“普通節點”切換為“簇頭”，VCH成為簇頭之后，在其RC內廣播消息Adv_Msg(CH_ID)。

2.2.4 分簇的建立

收到CH廣播的消息后，普通節點發送消息Join_REQ_MEG(MN_ID)，消息包含ID及其最近的CH。如果一個節點l被多個(Lcov個)簇頭覆蓋，則選擇最近且剩余能量較高的CH，計算方法如下

(24)

式中：d(l,i)是節點l與CHi的距離，dmaxCH是節點l與其簇頭的最大距離。如果某個節點不在CH的覆蓋范圍內，將該節點作為新簇的簇頭或加入最近的CH內。

2.2.5 數據傳輸階段

傳感器收到BS的消息Reqest_DATA_MSG()則喚醒成員節點采集數據，然后各節點將采集的數據及其剩余能量發送至CH。各簇使用不同的CDMA編碼通信，從而降低不同簇節點間的干擾，CH收到成員節點采集的數據后，將數據重組為一個單數據包；然后，CH將總報文與成員節點的剩余能量基于路由樹發送至BS。

3 仿真與結果分析

3.1 性能評價指標與實驗環境

選擇以下的指標評估本協議的性能[18]：①FDN：第一個死亡節點的輪數；②穩定期：網絡啟動到FDN的時間段；③LDN：所有節點死亡的輪數；④BEED：計算為(LDN-FDN)/LDN。

實驗環境為CPU 2.7 GHz，4 GB內存，仿真平臺為Matlab 2013b。為了消除實驗誤差，每組仿真獨立地運行5次，將均值作為最終的統計結果。能量模型的參數設為：Eelec=50nJ/bit，Efs=10pJ/bit/m2，EDA=5nJ/bit/signal。參考文獻[17]將MOIA的參數設為ps=30，pc=0.05，ph=10pm，Nclon=5，Maxgen=150。權重因子設為w1=0.4,w2=0.5,w3=0.1,a1=0.55,a2=0.25,a3=0.2,γ=0.6。

3.2 仿真結果

將本協議與LEACH、PCR、DCR進行比較，共設置100個異構傳感節點，將各節點的初始化能量隨機地初始化(范圍為[1,3])，節點均勻地分布于200×200平方米的采集區域內。BS位于(100,250)米坐標處，報文大小統一為500個字節，Dth-BS值設為2Rmax，Esensing設為0.2 μJ/bit。

3.2.1α，β與Rmax的效果

為了研究α，β與Rmax這3個參數的效果，考慮兩種α，β情況：(1)α=β=0，(2)α=β=0.3，然后對不同的Rmax值測試分簇的數量。圖5所示是兩種情況下CH數量與Rmax之間的關系，可看出第二種情況優于第一種，原因在于固定Rmax，簇的覆蓋范圍隨α，β的增加而降低，此外，CH數量隨著Rmax的增加而降低，由此說明生成的CH數量由Rmax，α，β三者決定。如果α，β固定，Rmax的增加導致Rc增加、CH下降。

圖5 兩種情況下CH數量與Rmax之間的關系

3.2.2 CH的分布

設置簇的數量為5，Rmax=100米，α=β=0.3。圖6所示是隨機地選擇的30輪分布情況，可看出本協議每輪中獲得的CH數量均接近5，而LEACH中CH數量變化較大，主要原因是LEACH通過隨機數決定CH，同時其它3個協議將CH控制于覆蓋范圍Rc內。因為在MOIA算法的目標函數中考慮了能耗、未覆蓋節點的比例以及CH數量，所以本協議的CH分布穩定性優于其它3種協議，每輪選擇的CH數量較為穩定。

圖6 隨機地選擇的30輪分布情況

3.2.3 穩定期與生命期

為了測試本協議對異構網絡的性能，設置Rmax=100米，α=β=0.3。圖7所示是4個協議的穩定期與生命期結果，可看出本協議的穩定期比LEACH、PCR、DCR分別增加了815、507、396輪，提高了總生命期。究其原因，本協議基于與BS的距離及其剩余能量決定每個節點的覆蓋范圍，此外，從高能量節點中選擇了總能耗最低的CH組合。

圖7 4個協議的穩定期與生命期結果

4 結束語

本文針對無線傳感器網絡分層路由協議的“熱點”問題，提出基于免疫算法的非均勻分簇路由協議，該協議總體分為信息收集階段、簇建立階段與數據傳遞3個階段。本文利用多目標免疫算法的諸多優點，對簇頭的選擇進行優化，將平衡全網的節點能耗，延長網絡的生命期作為優化目標，獲得了良好的效果。為了降低密集型網絡中搜索最優CH集合的計算時間，本協議將傳感區域劃分為若干個虛擬網格，并選擇各虛擬網絡中剩余能量較高的節點建立候選傳感器集，提高了協議的計算效率。多組仿真實驗結果表明，本算法有效地提高了異構WSN網絡與大規模WSN網絡的網絡生命期，并獲得了理想的計算效率。

參考文獻：

[1]QI Lin,HAN Yubing,ZHANG Xiaoshuan,et al.Real time monitoring system for aquatic cold-chain logistics based on WSN[J].Transactions of the Chinese Society of Agricultural Machinery,2012,43(8):134-140(in Chinese).[齊林,韓玉冰,張小栓,等.基于WSN的水產品冷鏈物流實時監測系統[J].農業機械學報,2012,43(8):134-140.]

[2]LIU Hongqing.Deployment of wireless sensor network nodes by particle swarm optimization algorithm based on cloud model[J].Journal of Huazhong Normal University:Nat Sci,2013,47(2):185-188(in Chinese).[劉紅慶.基于云模型粒子群算法的WSN節點部署優化[J].華中師范大學學報:自然科學版,2013,47(2):185-188.]

[3]CHEN Liangyin,WANG Jinlei,ZHANG Jingyu,et al.Scheduling scheme algorithm in low-duty-cycle WSN[J].Journal of Software,2014,25(3):631-641(in Chinese).[陳良銀,王金磊,張靖宇,等.低占空比WSN中一種節點休眠調度算法[J].軟件學報,2014,25(3):631-641.]

[4]Malathi L,Chandrasekaran M K,Gnanamurthy R K.A novel routing protocol with lifetime maximizing clustering algorithm for WSN[C]//India Conference,2012:925-930.

[5]Mahapatra R P,Yadav R K.Descendant of LEACH based routing protocols in wireless sensor networks[C]//Procedia Computer Science,2015:1005-1014.

[6]Islam M M,Matin M A,Mondol T K.Extended stable election protocol (SEP) for three-level hierarchical clustered heterogeneous WSN[C]//Wireless Sensor Systems.IET,2012:43.

[7]Xu J,Jin N,Lou X,et al.Improvement of LEACH protocol for WSN[C]//International Conference on Fuzzy Systems and Knowledge Discovery,2012:2174-2177.

[8]DING Juan,LIU Sanyang,ZHANG Ping.A data gathering and fusion algorithm based on energy optimization for WSN[J].Application of Electronic Technique,2013,39(5):97-99(in Chinese).[丁娟,劉三陽,張平.基于能量優化的WSN數據收集和融合算法[J].電子技術應用,2013,39(5):97-99.]

[9]QIN Haisheng,HE Chuanbo,WU Wenjun,et al.Research on clustering protocol of WSN based on cell membrane optimization algorithm[J].Computer Engineering,2014(11):92-96(in Chinese).[覃海生,何傳波,吳文俊,等.基于細胞膜優化算法的WSN分簇協議研究[J].計算機工程,2014,40(11):92-96.]

[10]HU Fengsong,XIAO Qiu.Multi-hop routing algorithm of energy-balancing based on LEACH[].Journal of Chinese Computer Systems,2014,35(1):70-73(in Chinese).[胡峰松,肖球.一種基于LEACH的能耗均衡多跳路由算法[J].小型微型計算機系統,2014,35(1):70-73.]

[11]Xia L,Wang G,Liu Z,et al.An energy-efficient routing protocol based on particle swarm clustering algorithm and inter-cluster routing algorithm for WSN[C]//Control and Decision Conference.IEEE,2013:4029-4033.

[12]Sabet M,Naji H R.A decentralized energy efficient hierarchical cluster-based routing algorithm for wireless sensor networks[J].AEU-International Journal of Electronics and Communications,2015,69(5):790-799.

[13]YUAN Jiaxin,ZHAO Zhen,FEI Wenli,et al.Pareto optimum control of inverter based on multi-objective immune algorithm[J].Transactions of China Electrotechnical Society,2014,29(12):33-41(in Chinese).[袁佳歆,趙震,費雯麗,等.基于免疫算法的逆變器多目標Pareto最優控制策略[J].電工技術學報,2014,29(12):33-41.]

[14]Lin Q,Zhu Q,Huang P,et al.A novel hybrid multi-objective immune algorithm with adaptive differential evolution[J].Computers & Operations Research,2015,62(C):95-111.

[15]Yao Y,Jiang N.Distributed wireless sensor network localization based on weighted search[J].Computer Networks,2015,86:57-75.

[16]Kumar R.Blending roulette wheel selection & rank selection in genetic algorithms[J].International Journal of Machine Learning and Computing,2012,2(4):365.

[17]Liang Z,Song R,Lin Q,et al.A double-module immune algorithm for multi-objective optimization problems[J].Applied Soft Computing,2015,35(C):161-174.

[18]Hari U,Ramachandran B,Johnson C.An unequally clustered multihop routing protocol for wireless sensor networks[C]//International Conference on Advances in Computing,Communications and Informatics.IEEE,2013:1007-1011.