基于多尺寸網(wǎng)格的LEACH協(xié)議改進

劉國繁,丁 燕

(1.湖南工程學院電氣信息學院,湖南湘潭411104; 2.湘潭大學信息工程學院,湖南湘潭411105)

基于多尺寸網(wǎng)格的LEACH協(xié)議改進

劉國繁1,丁 燕2

(1.湖南工程學院電氣信息學院,湖南湘潭411104; 2.湘潭大學信息工程學院,湖南湘潭411105)

針對低功耗自適應集簇分層型(LEACH)協(xié)議中節(jié)點采集的數(shù)據(jù)存在大量冗余和能量消耗不均衡問題,提出一種能量高效路由協(xié)議MDG-LEACH。該協(xié)議基于虛擬網(wǎng)格和多尺寸網(wǎng)格選取活躍節(jié)點,采用綜合考慮節(jié)點剩余能量和空間分布情況的簇頭選擇機制,簇頭與基站之間根據(jù)動態(tài)規(guī)劃方法建立最短傳輸路由樹進行數(shù)據(jù)傳輸。仿真結果表明,與LEACH協(xié)議以及單劍鋒的LEACH改進協(xié)議(計算機技術與發(fā)展,2013年第2期)相比,MDGLEACH協(xié)議在均衡節(jié)點能量消耗和延長無線傳感器網(wǎng)絡壽命方面有了較大提高。

低功耗自適應集簇分層型協(xié)議;多尺寸網(wǎng)格;活躍節(jié)點;分簇;多跳;Matlab仿真

1 概述

無線傳感器網(wǎng)絡由大量能量有限的節(jié)點組成［1-2］,這些節(jié)點由感應模塊、處理模塊、存儲模塊、傳輸模塊以及電源模塊組成。它們一般部署在人們無法靠近的惡劣環(huán)境,一旦電源耗完,節(jié)點也就失效了,因此,如何降低無線傳感器網(wǎng)絡的能量消耗、延長網(wǎng)絡壽命成為研究的熱點［3-4］。

低功耗自適應集簇分層型(Low Energy Adaptive Clustering Hierarchy,LEACH)路由協(xié)議［5］是一種經(jīng)典的分層路由協(xié)議,該協(xié)議的主要思想是通過輪詢隨機選擇簇頭節(jié)點,將整個網(wǎng)絡的能量負載平均分配到每個傳感器節(jié)點中,目的是為了均衡整個系統(tǒng)的能量消耗,進而延長網(wǎng)絡的生命周期。在LEACH協(xié)議的基礎上,許多學者提出了大量的改進路由協(xié)議。文獻［6］提出一種節(jié)點分組機制,在簇內(nèi),基于組間檢測的數(shù)據(jù)存在冗余這一思想,讓簇內(nèi)各組之間交替工作,大大減少了系統(tǒng)的能量消耗,延長了網(wǎng)絡壽命。文獻［7］提出了一個改進LEACH協(xié)議ESSCSTA,該協(xié)議基于節(jié)點監(jiān)測數(shù)據(jù)的相似度成簇,讓離簇頭近的50%的節(jié)點和簇內(nèi)其他節(jié)點輪詢處于休眠狀態(tài),簇間采用最小生成樹的方法將采集的數(shù)據(jù)發(fā)送至基站。文獻［8］提出一種基于各節(jié)點的屬性不同,給予各節(jié)點不同簇首概率的算法,并在數(shù)據(jù)傳輸過程中,采用了多種傳輸選擇機制,均衡了能量消耗,從而延長了無線傳感器網(wǎng)絡的壽命。文獻［9］則從簇頭選擇、簇的形成以及數(shù)據(jù)傳輸?shù)确矫婵紤],提出了一種改進的LEACH協(xié)議,延長了網(wǎng)絡的生存時間。

針對LEACH協(xié)議中節(jié)點采集的數(shù)據(jù)存在大量冗余和節(jié)點能量消耗不均衡問題,基于虛擬網(wǎng)格思想,本文提出一種基于多尺寸網(wǎng)格的LEACH改進協(xié)議,以減少活躍節(jié)點的數(shù)量,均衡各節(jié)點的能量消耗,從而延長無線傳感器網(wǎng)絡的生命周期。

2 LEACH協(xié)議

LEACH［5］協(xié)議是一種基于聚類的路由協(xié)議,它最大限度地減少了系統(tǒng)能量的使用,在不同的時間,基站分發(fā)負載到不同的節(jié)點。LEACH是一個完全分布式的,不需要基站控制信息的以輪為周期的循環(huán)過程,在每輪中,LEACH分為2個階段:簇的建立階段和數(shù)據(jù)通信階段。

2.1 簇的建立階段

這個階段包括簇頭的選取和簇的形成。在LEACH協(xié)議中,所有節(jié)點都可以直接和基站通信。在每一輪中,每個節(jié)點都試圖成為簇頭,節(jié)點隨機產(chǎn)生一個0-1的隨機數(shù),如果該隨機數(shù)小于閾值T(n),則節(jié)點便可成為簇頭。T(n)的計算公式如下:

一個節(jié)點一旦成為簇頭,就發(fā)送一個成為簇頭的消息,其他節(jié)點根據(jù)接收到信號強度的強弱,加入最近的簇頭。

2.2 數(shù)據(jù)通信階段

當簇建立完成后,簇頭按照時分多址(TDMA)技術,為簇內(nèi)普通節(jié)點分配時隙,簇內(nèi)節(jié)點則在自己的時隙內(nèi),把采集到的數(shù)據(jù)發(fā)送到簇頭節(jié)點,簇頭節(jié)點把接收的數(shù)據(jù)進行融合、匯聚,然后直接發(fā)送至基站。

LEACH協(xié)議存在以下不足:

(1)簇頭在選舉過程中采用隨機輪詢的辦法,沒有考慮節(jié)點的剩余能量,由于簇頭節(jié)點耗能要比普通節(jié)點大,因此如果能量小的節(jié)點擔任簇頭節(jié)點,則可能導致此節(jié)點快速死亡［10］。

(2)簇頭在選舉時,沒有考慮節(jié)點的空間分布位置,假如簇頭節(jié)點位于簇的邊界處,則簇內(nèi)節(jié)點在發(fā)送數(shù)據(jù)到簇頭時消耗的能量不同,會造成簇內(nèi)節(jié)點的能耗分布不均。

(3)在LEACH協(xié)議中,由于簇內(nèi)某些節(jié)點之間的距離很小,它們監(jiān)測的數(shù)據(jù)存在很高的冗余度,而簇內(nèi)的所有節(jié)點都要始終保持活躍狀態(tài),將檢測的數(shù)據(jù)發(fā)送至相應的簇頭,導致部分簇內(nèi)節(jié)點不必要的數(shù)據(jù)傳輸和簇頭節(jié)點不必要的數(shù)據(jù)聚合。

(4)簇頭節(jié)點采用單跳的方式和基站通信,在大規(guī)模的無線傳感器網(wǎng)絡中,遠離基站的簇頭節(jié)點直接將數(shù)據(jù)發(fā)送至基站,不但消耗大量的能量,而且會造成簇頭節(jié)點的能量消耗不均［11］。

3 MDG-LEACH協(xié)議

MDG-LEACH協(xié)議以LEACH協(xié)議為基礎,同樣采用以輪為周期的循環(huán)過程,在每一輪中,基于虛擬網(wǎng)格和多尺寸網(wǎng)格選取活躍節(jié)點,活躍節(jié)點采用分簇的方式將檢測的數(shù)據(jù)發(fā)送至基站。

假設網(wǎng)絡模型如下:

(1)所有預先部署在特定區(qū)域內(nèi)的無線傳感器網(wǎng)絡節(jié)點具有有限的能量。

(2)基站沒有能量限制。

(3)所有無線傳感器網(wǎng)絡的節(jié)點可以通過GPS或者其他定位算法獲取自己所在的位置。

(4)一旦布置完成,所有的無線傳感器網(wǎng)絡節(jié)點以及基站不再移動。

(5)L×L區(qū)域內(nèi)的所有節(jié)點可以直接與基站通信,并且能夠根據(jù)需要調(diào)節(jié)發(fā)射功率的大小。

3.1 簇的建立和活躍節(jié)點的選取

圖1 虛擬網(wǎng)格的劃分

在每個虛擬網(wǎng)格內(nèi)選取一個剩余能量最多的節(jié)點作為活躍節(jié)點的候選節(jié)點,以平衡整個網(wǎng)絡的能量消耗,防止能量小的節(jié)點很快耗完自身能量。

每個候選節(jié)點隨機產(chǎn)生一個0～1的隨機數(shù),如果該隨機數(shù)小于閾值T1(n),則該候選節(jié)點便可成為候選簇頭節(jié)點。候選簇頭節(jié)點的選取考慮節(jié)點的剩余能量和節(jié)點所在網(wǎng)格內(nèi)非死亡節(jié)點的個數(shù),候選節(jié)點的剩余能量越多,候選節(jié)點所在網(wǎng)格內(nèi)非死亡節(jié)點的個數(shù)越多,則候選節(jié)點成為候選簇頭節(jié)點的可能性越大。T1(n)的計算公式如下:

其中,p代表候選節(jié)點成為候選簇頭節(jié)點的概率;r代表當前運行的輪數(shù);Eres代表候選節(jié)點的剩余能量;Eo代表候選節(jié)點的初始能量;G代表在前1/p輪中還未成為簇頭節(jié)點的候選節(jié)點的集合;num代表候選節(jié)點所在網(wǎng)格內(nèi)非死亡節(jié)點的個數(shù)。

為了防止簇頭節(jié)點的空間分布過于集中,設置一個簇頭節(jié)點之間的最小距離dmin,只有候選簇頭節(jié)點與其他簇頭節(jié)點的距離不小于dmin才能成為簇頭節(jié)點,沒有成為簇頭節(jié)點的候選簇頭節(jié)點重新標記為候選節(jié)點。成為簇頭的節(jié)點發(fā)送一個成為簇頭的消息給所有的候選節(jié)點,候選節(jié)點收到來自簇頭的消息,根據(jù)接收信號的強弱加入收到信號最強的簇頭。

由于簇頭節(jié)點可能分布在監(jiān)測區(qū)域的任何一個位置,監(jiān)測區(qū)域?qū)⒈环殖啥喾N尺寸的大網(wǎng)格,如圖2所示。

圖2 簇頭節(jié)點隨機分布時的網(wǎng)格和活躍節(jié)點分布情況

候選節(jié)點根據(jù)節(jié)點關聯(lián)算法決定是否保持活躍狀態(tài),成為活躍節(jié)點。假設任意簇頭節(jié)點為A(x1,y1),任意候選節(jié)點為B(x,y),其中,x1,y1,x,y分別為節(jié)點A,B的橫縱坐標。節(jié)點關聯(lián)算法如下:

3.2 數(shù)據(jù)通信階段

簇內(nèi)數(shù)據(jù)的傳輸采用類似于LEACH的數(shù)據(jù)傳輸方式,簇頭節(jié)點給簇內(nèi)的活躍節(jié)點分配TDMA時隙,并通知簇內(nèi)所有的活躍節(jié)點,這樣,簇內(nèi)活躍節(jié)點在屬于自己的時隙內(nèi)將檢測到的數(shù)據(jù)直接發(fā)送至相應簇頭。

簇頭節(jié)點之間數(shù)據(jù)的傳輸采用動態(tài)規(guī)劃的方法從根節(jié)點逐漸向葉子節(jié)點建立最短傳輸路由樹。假設簇頭節(jié)點的個數(shù)為n,每個簇頭節(jié)點將檢測的數(shù)據(jù)傳輸至其下一跳節(jié)點,即其父節(jié)點,直到傳輸至根簇頭節(jié)點,建立一條最短傳輸路徑。簇頭節(jié)點之間數(shù)據(jù)的傳輸采用自由空間模型,即簇頭節(jié)點到根簇頭節(jié)點的最短傳輸距離表示簇頭節(jié)點到根簇頭節(jié)點的多跳距離的平方和最小。具體實現(xiàn)方案如下:

(1)根簇頭節(jié)點的選取考慮簇頭節(jié)點的剩余能量和到基站的距離,在滿足能量大于簇頭節(jié)點平均能量的簇頭節(jié)點內(nèi)選取到基站距離最近的簇頭節(jié)點為根簇頭節(jié)點,令其為s0,令其最短傳輸距離為0,即f(s0)=0。

(2)依此選取離根簇頭節(jié)點s0距離最近的簇頭節(jié)點sk,k=1,2,…,n-1,根據(jù)式(3)求出其到根簇頭節(jié)點s0的最短傳輸距離f(sk),并保存其下一跳節(jié)點,即簇頭節(jié)點sk的父節(jié)點,建立最短傳輸路由樹。

其中,f(sk)代表簇頭節(jié)點sk到根簇頭節(jié)點s0的最短傳輸距離;d2(sk,uk(sk))代表簇頭節(jié)點sk與屬于集合uk(sk)中簇頭節(jié)點的距離的平方;uk(sk)代表到根簇頭節(jié)點s0的距離小于簇頭節(jié)點sk到根簇頭節(jié)點s0的距離的簇頭節(jié)點集合;集合uk(sk)中滿足使f(sk)最小的簇頭節(jié)點為sk的下一跳節(jié)點,即簇頭節(jié)點sk的父節(jié)點。

(3)當簇頭節(jié)點有數(shù)據(jù)要傳輸時,根據(jù)簇間建立的最短傳輸路由樹采用多跳的方式將檢測的數(shù)據(jù)傳輸至根簇頭節(jié)點s0,根簇頭節(jié)點s0將接收的數(shù)據(jù)進行融合、匯聚,然后直接發(fā)送至基站。

4 仿真與分析

4.1 能耗模型

能量消耗模型使用一階無線通信模式,如圖3所示［12］。

圖3 無線傳感器網(wǎng)絡能耗模型

在該模型下,每個節(jié)點發(fā)送l位數(shù)據(jù)消耗的能量為:

每個節(jié)點接收l位數(shù)據(jù)消耗的能量為:

其中,Eelec為發(fā)送(或接收)數(shù)據(jù)的單位能耗;εfs為自由空間模型的功率放大系數(shù);εmp為多路衰減模型的功率放大系數(shù)。

4.2 實驗參數(shù)

在無線傳感器條件下采用 LEACH協(xié)議、文獻［8］LEACH改進協(xié)議以及本文協(xié)議進行大量的仿真實驗,實驗在PC機上Matlab7.1中完成。具體仿真參數(shù)如下:

100個節(jié)點隨機分布在100×100的矩形區(qū)域內(nèi),基站位于(50,50),節(jié)點的初始能量Eo=0.5 J,節(jié)點成為簇頭的概率P=0.05,數(shù)據(jù)包的長度為4 000 bit,Eelec=50 nJ/bit,εfs=10 pJ/bit/m2,εmp=0.001 3 pJ/ bit/m4,節(jié)點處理數(shù)據(jù)的耗能EDA=5 nJ/bit/signal,簇頭之間的最小距離dmin=30,虛擬網(wǎng)格的邊長R=10。

4.3 性能分析

在相同實驗環(huán)境下,對LEACH協(xié)議、文獻［8］的LEACH改進協(xié)議以及MDG-LEACH協(xié)議進行仿真。

3種協(xié)議的節(jié)點存活數(shù)量與輪數(shù)的關系如圖4所示。表1顯示了3種協(xié)議分別在第一個節(jié)點死亡(First Node Dead,FND)、半數(shù)節(jié)點死亡(Half Node Dead,HND)、最后一個節(jié)點死亡(First Node Dead, LND)時所對應的輪數(shù)。由表1可知,MDG-LEACH協(xié)議第一個節(jié)點的死亡時間比LEACH協(xié)議和文獻［8］LEACH改進協(xié)議提高了600%和450%;半數(shù)節(jié)點的死亡時間比LEACH協(xié)議和文獻［8］LEACH改進協(xié)議分別提高了760%和580%;最后一個節(jié)點的死亡時間比LEACH協(xié)議和文獻［8］LEACH改進協(xié)議提高了650%和510%。MDG-LEACH協(xié)議使能量較大的節(jié)點處于活躍狀態(tài),從而避免了能量較低的節(jié)點由于能量損耗過大而提前死亡,有效地延長了第一個節(jié)點的死亡時間,均衡了各節(jié)點的能量消耗。一般網(wǎng)絡的生命周期可以定義為第一個節(jié)點、半數(shù)節(jié)點以及最后一個節(jié)點死亡時所對應的時間,不管定義多少個節(jié)點死亡時間為網(wǎng)絡的生命周期,MDG-LEACH在延長網(wǎng)絡壽命方面都明顯優(yōu)于LEACH協(xié)議和文獻［8］的LEACH改進協(xié)議。

圖4 存活節(jié)點個數(shù)與輪數(shù)的關系

表1 3種協(xié)議死亡節(jié)點與輪數(shù)的關系

3種協(xié)議的網(wǎng)絡剩余總能量與輪數(shù)的關系如圖5所示。由圖5可知,每輪中MDG-LEACH協(xié)議網(wǎng)絡剩余總能量大于LEACH協(xié)議和文獻［8］LEACH改進協(xié)議。在1 500輪左右時,LEACH協(xié)議和文獻［8］LEACH改進協(xié)議的網(wǎng)絡總能量基本耗完,而MDGLEACH協(xié)議的網(wǎng)絡剩余總能量約為40 J,總體能量消耗較LEACH協(xié)議以及文獻［8］LEACH改進協(xié)議減少了80%。這是由于MDG-LEACH協(xié)議中每一輪活躍節(jié)點個數(shù)減少了,大大降低了每一輪消耗的總能量;簇頭的選取考慮節(jié)點的能量和位置因素,使得簇頭節(jié)點的分布更合理,網(wǎng)絡能耗更均衡;簇頭到基站的數(shù)據(jù)傳輸采用動態(tài)規(guī)劃的方法建立最短傳輸路由樹,大大減少了簇頭在數(shù)據(jù)傳輸時的能量消耗。

圖5 網(wǎng)絡剩余總能量與輪數(shù)的關系

5 結束語

針對LEACH協(xié)議中活躍節(jié)點存在很高冗余度和能量消耗不均衡的問題,基于網(wǎng)格和分層思想,提出了一種基于多尺寸網(wǎng)格的分簇路由協(xié)議MDGLEACH。該協(xié)議根據(jù)節(jié)點檢測半徑、結合節(jié)點位置以及能量信息,將監(jiān)測區(qū)域劃分為多尺寸網(wǎng)格,在保證網(wǎng)絡完全覆蓋的情況下,減少了活躍節(jié)點的個數(shù),降低了節(jié)點采集數(shù)據(jù)的冗余度;綜合考慮節(jié)點剩余能量和空間分布情況選取簇頭,均衡了各節(jié)點的能量消耗;簇頭與基站之間采用動態(tài)規(guī)劃的方法建立最短傳輸路由樹進行數(shù)據(jù)的傳輸,減少了簇頭節(jié)點的通信能量消耗。實驗結果表明,MDG-LEACH有效地均衡了節(jié)點能量消耗、延長了無線傳感器網(wǎng)絡的生命周期。

［1］ 沈 波,張世永,鐘亦平.無線傳感器網(wǎng)絡分簇路由協(xié)議［J］.軟件學報,2006,17(7):1588-1600.

［2］ 賀智勇,龍陳鋒,尹 乾.傳感器網(wǎng)絡中基于節(jié)點密度的分布式成簇算法［J］.計算機應用與軟件,2008, 25(12):19-20,82.

［3］ 唐甲東,蔡 明.基于LEACH協(xié)議的能耗均衡路由算法［J］.計算機工程,2013,39(7):133-136,141.

［4］ 李芳芳,王 靖.一種基于LEACH協(xié)議的無線傳感器網(wǎng)絡路由算法［J］.傳感技術學報,2012,25(10): 1445-1451.

［5］ Heinzelman W R,Chandrakasan A,Bala K H.Energy Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Hawaii,USA:IEEE Press,2000.

［6］ Haneef M,Zhou Wenxun,Deng Zhongliang.MGLEACH:MultiGroupBasedLEACH anEnergy Efficient Routing Algorthm for Wireless Sensor Network［C］//Proceedings of the 14th International Conference on Advanced Communication Technology.Pyeongchang,Korea:［s.n.］,2012:179-183.

［7］ Chauhan R,Gupta V.Energy Efficient Sleep Scheduled Clustering&Spanning Tree Based Data Aggregation in Wireless Sensor Network［C］//Proceedings of the 1st InternationalConference on Recent Advances in Information Technology.Dhanbad,India:［s.n.］,2012: 536-541.

［8］ 單劍鋒,莊琴清,陳 明.基于簇首概率優(yōu)化的LEACH協(xié)議改進［J］.計算機技術與發(fā)展,2013, 23(2):138-140,144.

［9］ 李嬋嬋.無線傳感器網(wǎng)絡分簇路由協(xié)議研究［D］.南京:南京郵電大學,2013.

［10］ 李年瓊,黃宏光,李 鵬.基于剩余能量和位置的LEACH改進算法［J］.計算機工程,2012,38(24):70-73,77.

［11］ 何延杰,李臘元,邢明彥.WSN中一種能量均衡的分簇路由協(xié)議的設計［J］.傳感技術學報,2009,22(10): 1510-1514.

［12］ 郭前崗,周得祥,周西峰.LEACH路由協(xié)議最優(yōu)簇頭數(shù)計算方法［J］.微型機與應用,2013,32(3):61-63,66.

編輯 任吉慧

Improvement of LEACH Protocol Based on Grids with Multiple Dimensions

LIU Guofan1,DING Yan2
(1.School of Electrical Information,Hunan Institute of Engineering,Xiangtan 411104,China;
2.College of Information Engineering,Xiangtan University,Xiangtan 411105,China)

A new energy efficient routing protocol of MDG-LEACH is proposed in the paper,which is based on the question of numerous redundancies with data collecting in nodes and imbalance of energy consumption in Low Energy Adaptive Clustering Hierarchy(LEACH) protocol.It selects active nodes based on virtual grids and multiple dimensions grids.Further,it adopts cluster head choice mechanism in overall consideration of residual energy and spatial distribution of nodes and establishes the shortest transmission route tree between cluster heads and base station by the dynamic programming method for date transmission.Simulation results show that MDG-LEACH protocol improves LEACH protocol and the improved LEACH protocol(Computer Technology and Development,2013,No.2)in balancing energy consumption of nodes and prolonging the life time of wireless sensor network effectively.

Low Energy Adaptive Clustering Hierarchy(LEACH)protocol;grids with multiple dimensions;active node;clustering;multihop;Matlab simulation

1000-3428(2014)11-0087-05

A

TP393.03

10.3969/j.issn.1000-3428.2014.11.017

湖南省科技計劃基金資助項目(2012SK3173)。

劉國繁(1959-),男,教授,主研方向:傳感器網(wǎng)絡,嵌入式系統(tǒng)應用;丁 燕,碩士研究生。

2013-10-12

2014-01-06E-mail:liugf59@163.com

中文引用格式:劉國繁,丁 燕.基于多尺寸網(wǎng)格的LEACH協(xié)議改進［J］.計算機工程,2014,40(11):87-91.

英文引用格式:Liu Guofan,Ding Yan.Improvement of LEACH Protocol Based on Grids with Multiple Dimensions［J］.Computer Engineering,2014,40(11):87-91.