基于簇頭功能分化的無線傳感器網絡成簇算法

陳東海,李長庚

(中南大學物理與電子學院,長沙 410083)

?

基于簇頭功能分化的無線傳感器網絡成簇算法

陳東海,李長庚*

(中南大學物理與電子學院,長沙 410083)

以LEACH為基礎演化而來的各類算法在簇頭選舉時始終包含有“隨機選擇”的成分,導致無線傳感器網絡在拓撲結構的優化和能量消耗的均衡上受到限制。從分化簇頭功能和優化功能節點選舉機制的角度出發,提出一種分化簇頭功能的分布式算法,引入功能節點推薦機制,弱化簇頭選舉中的隨機成分,分化簇頭功能,將以往簇頭管理節點、融合數據、轉發信息的三大功能分別由管理節點、融合節點、轉發節點3個功能節點來承擔。仿真數據表明,提出的分簇算法能有效優化簇內拓撲結構、提高節點能量消耗均衡性,能夠延長網絡生存周期15%～20%。

無線傳感器網絡;功能分化;管理節點;融合節點;轉發節點

無線傳感器網絡改變了人類與自然界的交互方式,其節點一般部署在無人值守地域,且能量和計算能力有限,因而在設計算法和執行任務時必須突出考慮其能量因素,以此獲得較長的網絡生存周期。分簇算法的基本思想是把隨機分布的傳感器節點按簇進行劃分,每個簇內按照一定選舉規則選出簇頭,簇頭負責召集和管理成員節點、融合成員節點發來的數據并進行轉發[1],循環組簇,輪流選擇簇頭,將整個網絡的能量負載盡可能的平均分配到每個傳感器節點。分簇算法能減小節點數據傳輸距離和傳輸數據量,進而大幅度降低節點能量消耗。此外,分簇算法作為節點組網的一種方式,在較大規模的無線傳感器網絡中,能很好的提高網絡生存周期,增強網絡的穩定性和魯棒性。

LEACH[2]算法是經典的分層路由算法,其節點等概率地隨機擔任簇頭,這使得低能量的節點也有相同的概率成為簇頭節點,HEED[3]算法和TEEN[4]算法在選舉簇頭時考慮了能量因素,使能量較少的節點被選為簇頭的概率減小,EEUC[5]算法、EOUCP[6]算法、CHTD算法、LDBPL[7]算法引入了競選半徑非均勻、競選時間延遲、分層次成鏈等概念,文獻[8]還提出了代理簇頭的思想,這些算法均在簇頭選舉過程中作了改進,其結果更趨合理,但仍舊存在一定的隨機性,且多個約束條件作用于簇頭的選舉過程,增加了算法復雜度,增加了節點成簇組網的能量消耗。本文提出一種分化簇頭功能的算法,引入功能節點推薦機制,降低選舉的隨機性和復雜度,提高選舉功能節點的合理度,將原來一個簇頭的功能分擔到3個功能節點上,即管理節點、融合節點和轉發節點,分化簇頭功能,均衡網絡能耗。

1 系統模型與問題描述

1.1 網絡模型

無線傳感器網絡是一個面向應用的系統,不同的應用環境需要不同的網絡模型。文中假定N個傳感器節點隨機均勻分布在一個面積為M×M的方形區域A內,并且有如下性質:①所有節點部署后不移動,能量不補充;②基站部署在區域A內或邊界外一個固定位置,并且是唯一的;③無線信道滿足對稱性,即正向傳輸和反向傳輸等量的數據消耗的能量相同;④節點同構,具有相同的處理和通信能力,在網絡中地位平等;⑤節點無線發射功率可控,可根據距離調整發射功率;⑥節點可以獲取無線接收信號的強度(RSSI);⑦每輪中節點的能量消耗不一致。

1.2 無線通信能量模型

網絡中節點通信采用Heinzelman等人在文獻[9-10]中提出的無線通信模型。當發送節點與接收節點的距離小于閾值d0時,采用自由空間模型,否則采用多路衰減模型。發送方發送長度為lbit的數據到距離為d0的位置所消耗的能量為

(1)

而接收方接收lbit的數據所需能量為

ERx(l,d)=Eelec(l)=lEelec

(2)

其中,Eelec為發射電路的能量消耗,εfs和εmp為兩種模型發射放大器系數。

1.3 平均剩余能量估計

為提高能量消耗均衡性,便于節點了解自身剩余能量在全網絡中所處的水平,通常需要對節點的平均能量進行計算,但平均能量的計算需要統計全網的剩余能量信息,這對分布式路由算法是非常困難的[11],這里引入估計方法,對平均能量進行相應估計。首先粗略估計全網每一輪消耗的能量Eround

(3)

式中,Etotal為全網初始總能量,r0為估計輪數,即網絡理論生存周期,在實驗過程中可采用遞歸的方法取得,這里不作論述。估計全網剩余能量的平均值為

(4)

其中,N為節點數目,r為實驗輪數。

2 簇頭功能分化算法

本文所提算法沿用按輪組網的思想,每輪包含成簇設置和穩定運行兩個階段。在成簇設置階段,首先按所需成簇比例選出管理節點,然后由管理節點推薦融合節點,再由融合節點推薦轉發節點,進而完成組簇。

2.1 初始化

算法開始時,基站首先以某一特定的功率向全網發送廣播消息,各節點根據接收基站發來消息的信號強度確定自身與基站的近似距離di-BS,并通過定限功率與周圍節交換信息,確定半徑R內的節點度Ddegree。

2.2 選舉管理節點

2.3 選舉融合節點

融合節點負責接收簇成員節點發送的信息并進行融合,是真正意義上的“簇頭”,對節點能量和位置有一定要求。本文提出一種“推薦”機制,由管理節點在其鄰節點中選取,選取標準為節點能量和節點度。首先由管理節點以特定功率向鄰節點發送廣播消息,要求鄰節點計算出自身成為融合節點的權值,同時也計算出自身成為融合節點的權值,各節點計算出權值后發送給管理節點,管理節點對各權值進行比較,并向權值最大者發送消息,通知其被選為融合節點。權值計算公式為

(5)

2.4 選舉轉發節點

轉發節點由融合節點推薦,需要滿足3個要素:是融合節點的鄰節點、離基站較近、剩余能量較多。融合節點首先以特定功率向鄰節點發送廣播消息,要求鄰節點計算出自身成為轉發節點的權值,各節點計算出權值后發送給融合節點,融合節點對各權值進行比較,并向權值最小者發送消息,通知其被選為轉發節點。其權值公式為:

(6)

至此,簇拓撲結構已生成,它緩解了以往算法中簇頭節點功能過多、能量消耗過快、簇頭位置不科學的現象,減小了網絡重組的頻率、降低了簇頭選舉的要求和復雜度、優化了簇頭位置,節省了簇內成員節點的通信能量,所形成簇結構如圖1所示。

需要強調的是,在符合條件的情況下,同一個簇內的管理節點、融合節點和轉發節點可以只由一個節點或兩個節點擔任。

圖1 本文算法簇結構

3 仿真實驗及數據分析

由于本文主要是對簇的結構和成簇過程進行研究和創新,在實驗仿真過程中涉及的其他相關方面如簇半徑的大小、簇的數目的優化和簇間轉發策略等方面分別采用文獻[5,12-13]中的辦法。

3.1 仿真實驗及結果分析

仿真中,設置仿真場景參數為:在邊長M=100 m區域內隨機分布N=100個無線傳感器節點,節點初始能量E=0.5 J,基站位于(150,50)m,能量不受限制,初始成簇概率p=0.05,節點每次發送或接收數據長度為l=4 000 bit。對LEACH、EEUC和本文算法進行仿真,得到死亡節點個數隨仿真輪數的變化圖,如圖2所示。

圖2 M=100 m時生存周期比較

由圖可以看出,LEACH算法在750輪左右開始出現死亡節點,到1 350輪左右全部節點死亡,第1個節點死亡的時間和全部節點死亡的時間均較早,這是因為LEACH采用的隨機選舉簇頭的方式,對簇頭的能量和位置未做限制,簇頭功能多、能耗大,簇頭位置隨機,簇規模不均勻,且采用單跳通信,導致簇內成員節點通信距離難以控制,加大節點能耗;EEUC算法在1 200輪左右時開始出現死亡節點,在1 600輪左右全部節點死亡,相比LEACH算法有較大提高,能量均衡性較好,因為EEUC在簇頭選舉時考慮了能量因素,減少了低能量節點當選簇頭的可能性,且其通過對節點競選半徑的設置控制了簇規模的大小,提高了能耗均衡性;而本文算法在1 400輪左右出現第1個死亡節點,到1 800輪左右全部死亡,相比于EEUC,新算法在成簇時采用的推薦機制,不僅考慮了簇頭的能量因素,剔除了低能量節點當選簇頭的可能性,而且分化了簇頭的功能,進一步增強了能耗均衡性。

第1個節點死亡的時間FD(First Dead)和全部節點死亡時間AD(All Dead)是衡量路由算法的重要指標。為進一步驗證算法的性能,在上述仿真條件下重復實驗50次,記錄其第1個節點死亡的時間(輪數)和全部節點死亡時間(輪數),并進行比較。從表1數據可知,EEUC在FD和AD上比LEACH分別提高了54%、18%,這得益于EEUC在簇頭競選中引入了非均勻方案和對能量因素的考慮,而本文算法在FD和AD上比EEUC分別提高了19%、15%。

表1 網絡生存周期

為確定算法應用在不同規模條件下的變化,修改仿真場景條件為:邊長M=200 m,節點數N=400個,基站位于(300,100)m,其他條件不變,即單純改變監控區域大小而不改變節點密度,得到數據如圖3所示。

圖3 M=200 m時生存周期比較

從圖3可以看出,在保持節點密度不變而擴大監控區域時,3種算法的生存周期均有所下降,其中LEACH生存周期下降最快,EEUC次之,本文算法下降較慢,且較EEUC延長了20%～25%,這是由于在保持相同節點密度而擴大監控區域的條件下,增加的能量消耗主要是來源于簇頭與簇頭或簇頭與基站之間的通信,簇頭能量消耗加快導致簇重組頻率增加,從而縮短網絡生存周期,LEACH中簇頭與基站之間的通信距離大大增加,能量消耗隨距離二次方增長,EEUC和本文算法中簇間簇間轉發次數增加但距離未增加,能量消耗呈線性增長,又由于本文算法的簇頭功能分化機制比其他算法在功能節點能量的消耗上相對緩和,從而也降低了簇重組的頻率,減緩了能量的消耗。實驗證明,簇頭功能分化算法對大規模部署的無線傳感器網絡具有更強的適應性。

3.2 仿真參數分析

算法中的權值因子w0、w1、w2十分重要,對算法性能影響比較大,理論上,在特定的場景中,每個權值因子均存在一個最優值。如在上述M=100 m仿真場景條件下,限定w1=0.6、w2=0.55時,w0從0按步長0.05增加到1時,其第1個節點死亡時間(輪數)變化如圖4所示。當w0從0增大到0.2的過程中,第1個節點死亡時間逐漸推遲,即生存周期延長,這是由于管理節點需要一定的能量要求,過低能量的節點擔任管理節點后會加速死亡;當w0大于0.2以后,越來越多的節點達不到擔任管理節點的能量要求,使得管理節點數目逐漸減少,直接導致成簇數目減少,從而影響網絡的生存周期,所以0.2為w0的在該條件下的最優值。

圖4 第1個節點死亡時間隨參數w0變化圖

當限定w0=0.2、w2=0.55時,w1從0按步長0.05增加到1時,其第1個節點死亡的時間(輪數)變化如圖5所示。當w1從0增大到0.6的過程中,網絡生存周期逐漸延長,原因在于高能量節點被推薦為融合節點的權重在逐漸增加,更容易選取得最優的融合節點;而當w1大于0.8后,網絡生存周期加速減短,這是因為式(5)中,對融合節點的能量閾值提高,推薦權重卻沒有相應地提高,所在w1的值在0.6到0.8之間比較合適,圖為w1=0.6左右時,第1個死亡節點出現的時間最晚,即網絡生存時間最長。

圖5 第1個節點死亡時間隨參數w1變化圖

圖6 第1個節點死亡時間隨參數w2變化圖

同樣的,當限定w0=0.2、w1=0.6時,則得到隨參數w2變化的生存周期圖,得到該條件下w2的最優值為0.55,見圖6。值得注意是,當仿真條件改變時,生存周期隨參數的變化也會有相應的改變。

4 結論

本文提出的簇頭功能分化算法,其核心思想包含兩個方面:一是提出分化簇頭功能的方案,使原來由一個節點承擔的功能任務分擔到2～3個節點,降低了功能節點的能量要求,緩解了功能節點過早死亡的現象,增強了網絡的能耗均衡性能;二是提出了功能節點的推薦機制,降低了選舉的復雜度,消除了融合節點選舉的隨機性,優化了功能節點在簇內的位置,降低了簇成員節的通信成本。仿真結果表明,采用本文算法提出的分化簇頭功能方案和功能節點的推薦機制,能將無線傳感器網絡生存周期提高15%～20%。

[1]AkyildizIF,SuW,SankarasubramaniamY,etal.ASurveyonSensorNetworks[J].IEEECommunicationsMagazine,2002,40(8):102-114.

[2]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks[C]//Proceedings of the Hawaii Internationnal Conference on System Sciences,LosAlamitos,C A,USA:IEEE Computer Society,2000:3005-3014.

[3]Ossama Y,Sonia F.HEED:A Hybird,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[4]Manjeshwar A,Agrawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proceedings of the 15th International Parallel and Distributed Processing Symposium(IPDPS),San Francisco,2001:2009-2015.

[5]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(1):27-36.

[6]劉鐵流,巫永群.基于能量優化的無線傳感器網絡分簇路由算法研究[J].傳感技術學報,2011,24(5):764-770.

[7]嚴英,郭麗,許建真.一種基于LEACH與PEGASIS協議的分層成鏈優化路由算法[J].傳感技術學報,2011,24(9):1311-1316.

[8]劉東江,賈卓生.基于分簇的無線傳感器網絡路由協議的研究[J].計算機學報,2012,39(10):23-38.

[9]Soro S,Heinzelman W B.Prolonging the Lifetime of Wireless Sensors Networks Via Unequal Clustering[J].In:Proc of the 19th IEEE Intertional on Parallel and Distributed Processing Symposium.San Francisco:IEEE Computer Society Press,2005:236-240.

[10]Heinzelman W B,Chandrakasan A,Balakrishman H.An Application-Specific Protocol Architecture for Wireless Microsensor NetWorks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[11]尚鳳軍.無線傳感器網絡通信協議[M].北京:電子工業出版社,2011:53-54.

[12]Tripathi R K,Singh Y N,Verma N K.Clustering Algorithm for Non-Uniformly Distributed Nodes in Wireless Sensor Network[J].E Electronics Letters,2013,49(4):299-300.

[13]Zhang D G,Li G,Zheng K,et al.An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network[J].IEEE Transactions on Mobile Computing,2014,10(1):766-773.

An Function Decomposition Algorithms for Cluster Head for WSNs

CHENDonghai,LIChanggeng*

(School of Physics and Electronics,Central South University,Changsha 410083,China)

Current algorithms based on LEACH or its derivatives always contain the factor of “random”in the aspect of selecting cluster heads,this is not conducive to balance the energy consumption of the wireless sensor networks.In order to improve the election mechanism of the cluster head and optimize its position and function,a new clustering method(Function Decomposition Algorithms for Cluster Head)for wireless sensor networks is proposed.Our approach provides a mechanism to recommend functional nodes,weaken the random component of cluster head selection,and split the cluster head into 3 functional nodes:management node,data fusion node,sending node.Simulation data show that the new algorithm can effectively optimize the topology of wireless sensor networks,improve the balance performance of energy consumption,and prolong sensor networks lifetime by 15%～20%.

wireless sensor networks,function decomposition,management node,data fusion node,sending node

陳東海(1987-),男,中南大學在讀碩士研究生,研究方向為無線傳感器網絡路由算法,195840715@qq.com;

李長庚(1970-),男,中南大學教授,博士研究生,從事無線傳感器網絡研究,lcgeng@mail.csu.edu.cn。

2014-09-11 修改日期:2014-11-19

C:6150P

10.3969/j.issn.1004-1699.2015.02.017

TP393

A

1004-1699(2015)02-0244-05