基于多尺寸網格的LEACH協議改進

劉國繁,丁 燕

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

基于多尺寸網格的LEACH協議改進

劉國繁1,丁 燕2

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

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

低功耗自適應集簇分層型協議;多尺寸網格;活躍節點;分簇;多跳;Matlab仿真

1 概述

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

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

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

2 LEACH協議

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

2.1 簇的建立階段

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

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

2.2 數據通信階段

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

LEACH協議存在以下不足:

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

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

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

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

3 MDG-LEACH協議

MDG-LEACH協議以LEACH協議為基礎,同樣采用以輪為周期的循環過程,在每一輪中,基于虛擬網格和多尺寸網格選取活躍節點,活躍節點采用分簇的方式將檢測的數據發送至基站。

假設網絡模型如下:

(1)所有預先部署在特定區域內的無線傳感器網絡節點具有有限的能量。

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

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

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

(5)L×L區域內的所有節點可以直接與基站通信,并且能夠根據需要調節發射功率的大小。

3.1 簇的建立和活躍節點的選取

圖1 虛擬網格的劃分

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

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

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

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

由于簇頭節點可能分布在監測區域的任何一個位置,監測區域將被分成多種尺寸的大網格,如圖2所示。

圖2 簇頭節點隨機分布時的網格和活躍節點分布情況

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

3.2 數據通信階段

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

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

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

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

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

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

4 仿真與分析

4.1 能耗模型

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

圖3 無線傳感器網絡能耗模型

在該模型下,每個節點發送l位數據消耗的能量為:

每個節點接收l位數據消耗的能量為:

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

4.2 實驗參數

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

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

4.3 性能分析

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

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

圖4 存活節點個數與輪數的關系

表1 3種協議死亡節點與輪數的關系

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

圖5 網絡剩余總能量與輪數的關系

5 結束語

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

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

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

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

［4］ 李芳芳,王 靖.一種基于LEACH協議的無線傳感器網絡路由算法［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］ 單劍鋒,莊琴清,陳 明.基于簇首概率優化的LEACH協議改進［J］.計算機技術與發展,2013, 23(2):138-140,144.

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

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

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

［12］ 郭前崗,周得祥,周西峰.LEACH路由協議最優簇頭數計算方法［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-),男,教授,主研方向:傳感器網絡,嵌入式系統應用;丁 燕,碩士研究生。

2013-10-12

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

中文引用格式:劉國繁,丁 燕.基于多尺寸網格的LEACH協議改進［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.