陳東海,李長庚

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

?

基于簇頭功能分化的無線傳感器網(wǎng)絡成簇算法

陳東海,李長庚*

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

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

無線傳感器網(wǎng)絡;功能分化;管理節(jié)點;融合節(jié)點;轉(zhuǎn)發(fā)節(jié)點

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

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

1 系統(tǒng)模型與問題描述

1.1 網(wǎng)絡模型

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

1.2 無線通信能量模型

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

(1)

而接收方接收lbit的數(shù)據(jù)所需能量為

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

(2)

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

1.3 平均剩余能量估計

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

(3)

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

(4)

其中,N為節(jié)點數(shù)目,r為實驗輪數(shù)。

2 簇頭功能分化算法

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

2.1 初始化

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

2.2 選舉管理節(jié)點

2.3 選舉融合節(jié)點

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

(5)

2.4 選舉轉(zhuǎn)發(fā)節(jié)點

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

(6)

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

需要強調(diào)的是,在符合條件的情況下,同一個簇內(nèi)的管理節(jié)點、融合節(jié)點和轉(zhuǎn)發(fā)節(jié)點可以只由一個節(jié)點或兩個節(jié)點擔任。

圖1 本文算法簇結構

3 仿真實驗及數(shù)據(jù)分析

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

3.1 仿真實驗及結果分析

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

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

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

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

表1 網(wǎng)絡生存周期

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

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

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

3.2 仿真參數(shù)分析

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

圖4 第1個節(jié)點死亡時間隨參數(shù)w0變化圖

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

圖5 第1個節(jié)點死亡時間隨參數(shù)w1變化圖

圖6 第1個節(jié)點死亡時間隨參數(shù)w2變化圖

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

4 結論

本文提出的簇頭功能分化算法,其核心思想包含兩個方面:一是提出分化簇頭功能的方案,使原來由一個節(jié)點承擔的功能任務分擔到2～3個節(jié)點,降低了功能節(jié)點的能量要求,緩解了功能節(jié)點過早死亡的現(xiàn)象,增強了網(wǎng)絡的能耗均衡性能;二是提出了功能節(jié)點的推薦機制,降低了選舉的復雜度,消除了融合節(jié)點選舉的隨機性,優(yōu)化了功能節(jié)點在簇內(nèi)的位置,降低了簇成員節(jié)的通信成本。仿真結果表明,采用本文算法提出的分化簇頭功能方案和功能節(jié)點的推薦機制,能將無線傳感器網(wǎng)絡生存周期提高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]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機學報,2007,30(1):27-36.

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

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

[8]劉東江,賈卓生.基于分簇的無線傳感器網(wǎng)絡路由協(xié)議的研究[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]尚鳳軍.無線傳感器網(wǎng)絡通信協(xié)議[M].北京:電子工業(yè)出版社,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-),男,中南大學在讀碩士研究生,研究方向為無線傳感器網(wǎng)絡路由算法,195840715@qq.com;

李長庚(1970-),男,中南大學教授,博士研究生,從事無線傳感器網(wǎng)絡研究,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