面向異構WSNs的基于能量感知的簇路由算法*

焦克瑩,郭 強

(1.駐馬店職業技術學院,河南 駐馬店 463000;2.黃淮學院國際教育學院,河南 駐馬店 463000)

面向異構WSNs的基于能量感知的簇路由算法*

焦克瑩1*,郭 強2

(1.駐馬店職業技術學院,河南 駐馬店 463000;2.黃淮學院國際教育學院,河南 駐馬店 463000)

有效地使用傳感節點的能量,進而延長網絡壽命成為設計無線傳感網路由協議的一項挑戰性的工作。為了延長網絡,現存的多數簇路由是面向同構網絡。為此,提出分布式能量感知的異構WSNs非均勻分簇路由DEAC(Distributed Energy Aware unequal Clustering)算法。DEAC算法是以EADUC(Energy Aware Distributed Unequal Clustering)為基礎,并進行優化。與EADUC不同,DEAC算法從簇頭競選機制、簇間多跳通信中的下一跳轉發節點的選擇策略以及自適應的節點通信半徑的設置三方面進行優化。在簇頭競選機制中,采用退避算法,利用節點的剩余能量以及鄰居節點的平均能量設置延時時間;在選擇下一跳轉發節點時,建立節點的關于能量的度量函數,選擇具有最大剩余能量的節點作為下一跳;而在設置節點通信半徑時,考慮了距離、剩余能量以及鄰居節點數信息。仿真結果表明,與EADUC協議相比,提出的DEAC算法能夠有效地延緩第1個節點失效的時間,減少了能耗,擴延網絡壽命。

異構無線傳感網;路由;能量感知;非均勻簇;網絡壽命

通著現代電子技術的發展,無線傳感網絡 WSNs(Wireless Sensor Networks)在多類應用中得到廣泛使用[1-2]。然而,WSNs受到多類資源的限制,包括能量、功耗、存儲容量以及傳輸距離。其中,能量的有限性是目前WSNs最主要的資源限制。而部署WSNs的根本目的就是收集監測區域數據。若節點的能量耗盡,則該節點就成為失效節點,一旦失效,節點便無法收集數據。這不僅縮短了網絡壽命,還產生覆蓋空洞,這直接影響了數據收集,也失去對區域監測的目的。

目前,研究人員針對WSNs的能量受限問題提出了不同處理算法[3-5]。其中,簇路由技術得到廣泛關注,它能夠有效地完成數據傳輸,并提高了網絡能量利用率。基于簇的網絡的模型如圖1所示。多個節點形成不同的簇,每個簇產生一個簇頭,簇頭收集簇內成員數據,經處理后傳輸基站。

圖1 網絡模型

基于分簇路由可提高網絡壽命[3]。文獻[6]提出了LEACH協議。文獻[7]提出了分布式能量有效簇DEEC(Distributed Energy-Efficient Clustering)協議。DEEC協議采用了兩級能量結構,每個節點依據自己的剩余能量選擇自己的簇頭。DEEC協議僅從自己的剩余能量選擇簇頭,存在不足。為此,文獻[8]提出了改進算法,提出DDEEC(Developed DEEC)協議。DDEEC協議自適應地選擇簇頭,進而實現節點能量消耗的平衡。文獻[9]也提出了DEEC的改進協議,記為HUCL協議。HUCL協議采用了三級能量結構,將節點分為三類。每類節點初始能量不同。但是,HUCL協議并沒有依據節點的能量水平改變簇頭的選擇概率。

此外,文獻[10]提出了能量感知的分布式非均勻簇EADUC(Energy Aware Distributed Unequal Clustering)路由。EADUC協議采用非均勻的簇算法,進而降低了能量消耗速率。但是該協議在選擇簇頭以及簇形成階段,只考慮了節點本身的剩余能量和離基站的距離信息,并沒有充分考慮節點所處區域的能量信息以及區域的節點數。

為此,本文基于EADUC協議,并面向異構網絡,提出分布式能量感知的異構WSNs非均勻分簇路由DEAC(Distributed Energy Aware unequal Clustering)算法。DEAC算法對EADUC進行了三點優化。首先,在簇頭選擇階段,基于區域剩余能量設置延時退避機制;其次,采用自適應通信半徑策略,形成非均勻化的簇;最后一點的改進體現于簇間多跳通信中的下一跳節點選擇算法。通過從這三方面的改進,提高了網絡壽命,降低了節點消耗速度。仿真結果表明,改進后的DEAC有效地減少能量消耗,即延緩了第1個失效節點所發生的時間,也提高了活動節點數。

1 系統模型

考慮如圖1所示的系統模型,N個傳感節點隨機分布于M×M感測區域。一旦部署節點后,傳感節點和基站就不再移動,即靜態網絡。基站遠離感測區域,并且所有傳感節點知道基站的位置。

此外,考慮異構網絡,即網絡內所有傳感節點具有不同的特性。本文假定所有節點的初始能量不同,即節點的初始能量不完全相同,同時,所有節點的傳輸距離不相同,而同構網絡的傳輸距離相同。

每個傳感節點能夠依據傳輸距離調整自己的傳輸功率,這有利于提高節點的能量利用率,可延長網絡壽命,但是它們的位置未知,它們可以依據從基站接收的信號功率估計離基站的距離。同時,假定網絡內的鏈路是對稱的[11-12]。N個傳感節點形成不同的簇,簇頭能夠直接與基站通信。在簇內,簇內成員節點將感測數據傳輸至簇頭,并由簇頭收集、融合。

1.1 能量消耗模型

能量消耗模型如圖2所示。在相距為d兩節點間傳輸l比特的數據信息,消耗的能量如式(1)所示。當傳輸距離d小于門限值dco時,就采用自由空間傳輸模型,若傳輸距離d大于門限值dco時,就采用多徑傳輸模型。

(1)

式中:Eelec表示運行發射器或接收器固定的能量消耗,εfs、εmp分別表示發射器在自空間、雙徑傳播模型(two ray ground model)的單位功率放大器的能量消耗[13]。在NS2的仿真場景中,使用式(2)計算dco:

(2)

式中:λ為波長、κ為系統損耗。ht、hr分別表示發射天線和接收天線的增益系數。相應地,對于接收l比特的數據包,所消耗的能量ERx(l):

ERx(l)=lEelec

(3)

圖2 無線電能量消耗模型

2 DEAC

將時間劃分等間隔的輪。在每一輪內執行一次DEAC算法。DEAC協議主要兩個階段:簇建立階段和穩定階段。而簇建立階段又分為3個子階段,第1個子階段用于收集鄰居信息;第2個子階段選擇簇頭;最后一個子階段形成簇,如圖3所示。

圖3 DEAC協議的時間模型

2.1 簇建立階段

簇建立階段由鄰居信息收集、簇頭選擇和簇形成3個子階段組成。這3個子階段的時限分別為T1、T2、T3。

2.1.1 鄰居信息收集

每個節點廣播通告消息Know_Msg,其包含節點的ID、剩余能量。鄰居內所有節點將接收到該通告消息。然后,每個節點通過鄰居內節點的能量信息,計算鄰居區域的平均能量Eavg_res:

(4)

式中:Ni表示節點Si的鄰居數、Er(Sj)表示Si的鄰居節點Sj的剩余能量。

2.1.2 簇頭選擇

完成了鄰居信息收集后,即T1結束后便進入簇頭選擇階段。采用延時退避機制廣播簇頭競爭消息Com_Head_Msg。為了避免競爭,每個節點依據自己的剩余能量和鄰居區域的平均能量,設置不同的延時時間t:

(5)

式中:Er表示節點的剩余能量。而Vr表示在[0.9,1]區內的隨機值,用于降低不同節點具有相同的延時時間的概率,即減少節點同時發送Com_Head_Msg消息的概率[14]。在自己的延時退避期間內,若沒有收到其他節點所發送的Com_Head_Msg消息,即自己的延時時間最短,那么自己就成為簇頭。否則,就不轉發Com_Head_Msg消息。

2.1.3 簇形成

一旦產生了簇頭,便進入簇形成階段。簇頭廣播自己成為簇頭的宣告消息Acc_Msg。鄰居節點(非簇頭節點)收到后,選擇離自己最近的簇頭作為自己的簇頭,即加入該簇,成為該簇成員,同時向該簇頭發送加入消息Join_Msg,進而形成簇。

(6)

式中:α、β、γ均為權重系數,且在[0,1]區間內。Rmax表示最大的通信半徑。dmax、dmin分別表示節點離基站的最大、最短距離。Einit為節點的初始能量。Ni表示節點Si的鄰居節點數,相應地Nmax表示最大的鄰居節點數。

2.2 穩定階段

當構建了簇后,便進入穩定階段,開始進行數據傳輸。在簇內,成員節點將自己所感測的數據直接傳輸至簇頭,由于在同一個簇,只需一跳就能完成數據傳輸,因此也稱為簇內通信。簇頭收集簇內成員數據后,便進行數據融合,最后傳輸到基站。

依據離基站的距離的不同,簇頭要么以直接或間接轉發方式向基站傳輸數據。如果離基站的距離大于門限值dth,就得借助其他簇頭節點進行轉發,形成簇間的多跳通信。否則,就采用直接傳輸。對于簇間多跳通信,需要通過多跳節點轉發才能完成數據的傳輸。因此,下一跳節點的選擇成為簇間通信的關鍵。

最初的EADUC協議是通過距離信息決策下一跳轉發節點。假定簇頭CHi需要向基站發送數據,并需要從其鄰居節點中選擇一個節點作為下一跳轉發節點。那么它就計算鄰居節點的成本值Cj(假定鄰居節點為Sj),如式(7)所示:

Cj=d2(CHi,Sj)+d2(Sj,BS)

(7)

式中:d(CHi,Sj)、d(Sj,BS)分別表示CHi離Sj、Sj離基站的距離。成本越低,節點成來下一跳節點的概率就越大。最終,簇頭CHi選擇成本最低的節點作為下一跳。

與EADUCE協議不同,提出的DEAC協議采用不同的策略選擇下一跳節點。提出的DEAC協議在選擇下一跳節點時不僅考慮了距離信息,而且還考慮了剩余能量以及鄰居節點數,并將這些信息量化為能量,最后選擇剩余能量最多的節點作為下一跳轉發節點。因此,DEAC協議引入了變量En_resj(假定鄰居節點為Sj):

(8)

式中:Mj表示簇頭CHj內的成員節點數。Eagg表示簇頭融合數據所消耗的單位能量。依據式(8)可知,En_resj越大,意味著節點的剩余能量越多。簇頭CHi就選擇剩余能量最多的節點作為下一跳節點。

2.3 與EADUC協議的不同之處

作為基于EADUC的改進協議,DEAC算法與EADUC有以下3點不同。①在簇頭選擇過程中,充分考慮了剩余能量,并采用延時退避機制,如式(5)所示,進而擴延網絡壽命;②采用自適應的通信半徑機制[15],如式(6)所示,這有利于更好地平衡網絡能量;③選擇下一跳的標準不同。DEAC協議更充分地考慮了節點的剩余能量,并選擇剩余能量最多的節點作為下一跳節點,進一步平衡了網絡內能量消耗。

3 性能仿真

3.1 仿真參數及性能指標

本節評估DEAC算法的性能,利用MATLAB建立仿真平臺,并與原始的EADUC、HUCL協議進行比較。100個節點隨機分布于200 m×200 m區域,基站位于區域外,其位置坐標表示為(250,100),數據包大小為512 byte,其他的仿真參數如表1所示。

表1 仿真參數

同時,考慮3個不同的仿真場景[16]:(1)場景1:100個節點均勻分布于200 m×200 m,如圖4(a)所示;(2)場景2:節點并不是均勻分布,而是多數節點分布區域的右邊,靠近于基站,如圖4(b)所示;(3)場景3:多數節點分布于區域的左邊,遠離基站,如圖4(c)所示。

圖4 仿真場景

3.2 網絡壽命

為了更好地評估網絡壽命,本次實驗分別從第1個節點失效所發生的輪數和10%節點失效所發生的輪數表征網絡壽命。實驗數據表2、表3所示。

從表2可知,提出的DEAC協議拖延了第1個失效節點所發生的輪數。通過5次實驗數據可知,不論是在場景1、場景2、場景3,DEAC協議的第1個失效節點所發生的輪數大于EADUC和HUCL協議,例如,在場景1時,DEAC協議的第1個失效節點所發生的平均值輪數為650,而EADUC和HUCL協議分別在280、320。這些數據說明DEAC協議能夠有效地擴延網絡壽命。此外,通過表2數據不難發現,3個場景的數據略有差別,在同等條件下,場景3的數據低于場景1、場景2。這說明,場景3的環境加速了節點失效,使得節點失效提前。這主要是因為在場景3中,多數節點遠離基站,增加了節點的能量消耗。

表3統計了3個協議在3個場景下,當10%節點失效時,所發生的輪數。換而言之,90%的節點還處于活動狀態時所維持的輪數。從表3可知,提出的DEAC協議的這項性能優于EADUC和HUCL協議。例如,在場景2,DEAC協議直到執行900輪時,才有10%的節點失效。即在900輪時,仍有90%的節點還處于活動狀態。而EADUCE和HUCL協議分別只能執行到350、750輪。

表2 第1個節點失效所發生的輪數

表3 10%節點失效所發生的輪數

圖5 活動節點數隨輪數的變化情況

3.3 活動節點數

本次實驗分析DEAC算法在3個不同場景的活動節點數,并與EADUC和HUCL協議進行比較,數值結果如圖5所示。

從圖5可知,提出的DEAC算法的活動節點數優于EADUC協議。特別是當執行輪數超過500次后,DEAC協議的優勢特別明顯。例如,在場景1中,當輪數達到500次時,EADUC協議的活動節點數低于60,而DEAC的活動節點數達到100,提高了近一倍。此外,與HUCL協議相比,DEAC算法在活動節點數方面也存在優勢,特別在場景1。即在傳感節點均勻分布的環境下,DEAC算法能夠有力地增加活動節點數。

4 總結

基于無線傳感網絡的節點能量受限的事實,分析了現有簇路由協議,并提出了基于EADUC的改進簇路由DEAC。DEAC算法采用非均勻的簇機制,進而平衡網內能量消耗。DEAC從簇頭選擇、節點通信半徑以及簇間多跳通信的下一跳轉發節點的選擇機制三方面對EADUC協議進行了改進。在簇頭選擇過程了,利用節點所處的區域能量信息設置不同的延時,進而產生簇頭;其次,依據節點能量自適應地設置節點的通信半徑,降低能量消耗。最后,在選擇下一跳轉發節點時,更充分地考慮節點的能量水平,選擇最佳的節點參與簇間多跳通信。

在本文中的3個不同場景的實驗數據可知,提出的DEAC算法有效地延緩第1個失效節點發生的時間,提高了活動節點數目。此外,通過3個不同場景的實驗數據可知,提出的DEAC算法可適用大中型的WSNs應用場景,如森林防火監測。

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 邵奇可,馮淑娜,毛科技. 面向WSN的自適應模糊功率控制算法研究[J]. 傳感技術學報,2015,4(28):563-572.

[3] 歸奕紅. 無線傳感器網絡HEDSA數據聚合研究[J]. 計算機工程,2011,37(7):160-164.

[4] Kaundal V,Mondal A K,Sharma P,et al. Tracing of Shading Effect on Underachieving SPV Cell of an SPV Grid Using Wireless Sensor Network[J]. Eng Sci Technol Int J,2015(18):475-484.

[5] Gu X,Yu J,Yu D,et al. ECDC:An Energy and Coverage-Aware Distributed Clustering Protocol for Wireless Sensor Networks[J]. Comp Electr Eng,2014(40):384-398.

[6] Yan J F,Liu Y L. Improved LEACH Routing Protocol for Large Scale Wireless Sensor Networks Routing[C]//International Conference on Electronics,Communications and Control. Ningbo,China,September 2011:35-42.

[7] Qing L,Zhu Q,Wang M. Design of a Distributed Energy-Efficient Clustering Algorithm for Heterogeneous Wireless Sensor Network[J]. ELSEVIER,Comput Commun,2016,29:2230-2237.

[8] Elbhiri B,Saadane R,El-Fkihi S,et al. Developed Distributed Energy-Efficient Clustering(DDEEC)for Heterogeneous Wireless Sensor Networks[C]//5th International Symposium on I/V Communications and Mobile Network. 2010:32-42.

[9] Saini A P,Sharma K. Distributed and Grid Computing(PDGC-2010). E-DEEC-Enhanced Distributed Energy Efficient Clustering Scheme for Heterogeneous WSN[C]//2010 1st International Conference on Parallel,2011,3-9.

[10] Wu J,Qi Y,Wang G,et al. An Energy Aware Distributed Unequal Clustering Protocol for Wireless Sensor Networks[J]. Int J Distrib Sens Netw,2011:23-32.

[11] Li C,Ye M,Chen G,et al. An Energy Ecient Unequal Clustering Mechanism for Wireless Sensor Networks[C]//Proceedings of IEEE International Conference on Mobile Ad-Hoc and Sensor Systems(MASS),2015:596-604.

[12] Min X,Wei-Ren S,Changjiang J,et al. Energy Ecient Clustering Algorithm for Maximizing Lifetime of Wireless Sensor Networks[J]. Int J Electron Commun,2010:(64):289-298.

[13] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[14] Li J,Mohapatra P. An Analytical Model on the Energy Hole Problem in Many-to-One Sensor Networks[J]. Proc of IEEE Vehicular Technology Conf,Fall. 2015,3(5):2721-2725.

[15] Vrinda G,Rajoo P. An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks[J]. Engineering Science and Technology,2016,4(6):23-31.

[16] Coutinho R W L,Boukerche A,Vieira L F M,et al. GEDAR:Geographic and Opportunistic Routing Protocol with Depth Adjustment for Mobile Underwater Sensor Networks[C]//Proc IEEE Int Conf Commun,2014:251-256.

焦克瑩(1973-),女,漢族,河南南陽人,博士,副教授,研究方向為計算機網絡應用不確定信息處理、數據分析,jiaokeying89@yeah.net。

DistributedEnergyAwareUnequalClusteringAlgorithmforHeterogeneousWSNs*

JIAOKeying1*,GUOQiang2

(1.Zhumadian Vocational and Technical College,Zhumadian He’nan 463000,China; 2.Huanghuai University International Education College,Zhumadian He’nan 463000,China)

Using the energy of sensor nodes efficiently to prolong the network lifetime is a chief challenge for designing routing protocols. To prolong WSNs(Wireless Sensor Networks)lifetime,most of the existing clustering schemes are geared towards homogeneous WSNs. Therefore,Distributed Energy Aware Unequal Clustering(DEAC)algorithm for heterogeneous WSNs is proposed in this paper. Based on Energy Aware Distributed Unequal Clustering(EADUC),DEAC is different from EADUC. DEAC algorithm has improved in terms of cluster head campaign mechanism,next-hop forwarding node selection strategy in multi-hop inter-cluster communication,and the adaptive setting communication radius. In cluster head campaign mechanism,the delay is computed based on residual energy and energy level of neighbor nodes by back off algorithm. In selecting the next-hop forwarding node,the metric with energy is estimated,and the node with high-residual energy is selected. To set the communication radius,the distance,residual energy and number of neighbor nodes are taken into account. Simulation results show that DEAC can postpone the time of the first failed node,and reduce the energy consumption,prolong the network lifetime.

heterogeneous wireless sensor network;clustering routing;energy aware;unequal clustering;network lifetime

項目來源:國家自然科學基金項目(71073033);河南省科技攻關計劃項目(122102210430)

2017-03-28修改日期:2017-05-23

TP393

:A

:1004-1699(2017)09-1427-06

10.3969/j.issn.1004-1699.2017.09.022