能量異構無線傳感器網絡分簇路由改進算法*

李安超,陳桂芬

(長春理工大學電子信息工程學院,長春 130022)

能量異構無線傳感器網絡分簇路由改進算法*

李安超,陳桂芬*

(長春理工大學電子信息工程學院,長春 130022)

路由算法作為無線傳感器網絡的核心技術,對延長網絡生命周期,提高網絡效率起到了至關重要的作用。針對分布式能量有效成簇算法未考慮節點位置和對節點保護、利用不充分的問題,提出了一種改進的能量異構分簇路由算法。該算法引入邊緣度的概念,使距離基站近的節點優先擔任簇頭,減少了網絡能量消耗;設立了雙能量閾值,提高節點能量利用,延長節點生命周期;綜合考慮節點、簇頭、基站三者的位置分布,提出了更合理的入簇機制。仿真結果顯示,在小面積檢測(10 m×10 m到100 m×100 m)與大面積檢測(100 m×100 m到500 m×500 m)環境下改進算法與原算法相比,網絡生命周期分別提高了18.7%到36.2%,24.4%到66.5%。

異構無線傳感器網絡;路由算法;邊緣度;雙能量閾值;入簇機制

無線傳感器網絡WSNs(Wireless Sensor Networks)作為信息技術的三大支柱之一,憑借其獨特的學科交叉性,已經成為國際上備受關注的關鍵技術。無線傳感器網絡由部署在檢測區域內的大量微型、廉價、低功耗的傳感器節點組成,傳感器通過相互協作的方式感知和采集檢測環境的信息,并對數據進行預處理然后將處理后的信息傳送給用戶[1-2]。無線傳感器網絡的應用領域十分廣闊,目前已經可以廣泛應用于環境檢測、醫療護理、軍事、環境科學等其他一些商業應用領域[3]。無線傳感器網絡可以根據傳感器節點的異同,分為同構型無線傳感器網絡和異構型無線傳感器網絡,其中僅初始能量不同的節點所組成的能量異構型無線傳感器網絡符合現實情況,更具有研究價值。

路由算法是無線傳感器網絡的核心技術之一,直接決定了傳感器節點在傳輸數據時的效率。由于傳感器節點能量微小且隨機分布,遠距離傳輸數據會大量消耗能量,不合理的路由算法很容易引發局部節點快速死亡而產生的能量黑洞現象,因此研究合理有效的路由算法具有現實與科研的意義。

目前,國內外學者提出了多種路由算法,其中分簇型路由算法憑借良好的可擴展性和優異的網絡性能,已經成為無線傳感器網絡路由算法的研究重心。典型的分簇型路由算法有低能量自適應分群算法LEACH(Low Energy Adaptive Clustering Hierarchy)[4]、門限敏感的傳感器網絡節能算法TEEN(Threshold sensitive Energy Efficient sensor Network protocol)[5]、分布式能量有效成簇算法DEEC(Distribute Energy-Efficient Clustering Algorithm)[6]等。LEACH算法使每個節點輪番擔任簇頭,平均網絡負載,但節能性一般;TEEN算法提出雙門限值減少數據傳輸量,但實時性很差。

DEEC算法作為LEACH算法的改進,在其優點的基礎上,動態的調整每個節點當選簇頭的概率,提高了能量效率,因此受到國內外學者的關注。文獻[7]改進了DEEC算法中最佳簇頭個數與每輪平均能量公式,使整體網絡能量更加清晰明了,但沒有考慮節點位置因素;文獻[8]考慮了節點的位置分布,使靠近基站的節點更易當選簇頭,卻沒有對低能量節點進行保護,很容易造成基站附近的節點因反復當選簇頭而迅速死亡。

針對上述問題,本文首先分析了DEEC算法的優缺點并在其基礎上提出了一種改進能量異構分簇路由分布式能量有效成簇改進算法RDEEC(Reformative Distribute Energy-Efficient Clustering Algorithm),綜合考慮了節點位置、剩余能量、入簇機制等方面對網絡生命周期的影響,引入了邊緣度與雙能量閾值,優化了入簇機制,延長了網絡的生命周期。

1 相關研究

1.1 異構傳感器網絡

1.1.1 異構傳感器網絡分類

異構傳感器網絡可以根據節點感測能力、計算能力、通信能力和能量等不同而分為4種類型:計算能量異構型、節點能量異構型、鏈路異構型和網絡協議異構型[9]。本文研究節點能量異構型傳感器網絡,即節點配置不同的初始能量,這一特征也具有現實意義。

1.1.2 多級能量異構傳感器網絡

在多級能量異構傳感器網絡中,節點的能量值是在一個區間隨機分布的,我們區分節點為普通節點和高能節點兩種,普通節點的初始能量為Eo,高能節點的初始能量為Eo(1+ai),ai表示高能節點超過普通節點能量的倍數,因此節點的初始能量可以描述為在[Eo,Eo(1+amax)]的區間內隨機分布[10]。其中amax為所有能量倍數ai的最大值。因此網絡的整體能量可以描述為式(1):

(1)

1.1.3 異構無線傳感器網絡能耗模型

異構無線傳感器網絡中的能耗模型如下[11]。

節點的能耗公式主要有3種,分別為發送數據能耗ETx(l,d),接收數據能耗ERx(l),數據融合能耗Ec。具體公式如式(2)～式(5):

(2)

ERx(l)=lEelec

(3)

Ec=(M+1)lEDA

(4)

(5)

式中:l為發送的數據大小;Eelec為發射電路的能耗;εfs和εmp為功率放大的能耗;d0為節點有效距離的閾值;EDA為單位數據融合的能耗,M為簇內成員的節點數。

1.2 DEEC算法

DEEC算法以LEACH算法為基礎并改進了其未考慮節點剩余能量的缺點,使高初始能量及高剩余能量節點當選簇頭的概率增加,從而均衡網絡負載,延長了網絡生命周期。算法原理與LEACH算法相似,網絡周期性的按輪(round)運行。每個輪循環分為簇的建立(set-up)階段和穩定工作(steady-state)階段,穩定工作階段也即為數據傳輸階段[12]。算法實現原理如下:

①簇的建立階段:

在能量異構無線網絡中,每個節點的初始能量不同[13]。節點當選簇頭的概率為式(6)所示:

(6)

(7)

式中:G為當前普通節點的集合。

②穩定工作階段:

簇頭節點確立后,該簇頭節點便會向鄰居節點通過廣播的方式發送“入簇”的消息,非簇頭節點收到此消息時,就根據收到消息信號的強弱,選擇最強信號的簇頭節點加入。

1.3DEEC算法的缺點

DEEC算法在LEACH算法的基礎上考慮到了節點的剩余能量,使高剩余能量節點更高概率當選簇頭,但DEEC算法的缺點如下:①低剩余能量節點仍有可能當選簇頭。②高剩余能量節點不能重復當選簇頭,利用率很低。③簇頭選舉時未考慮到節點的位置分布因素。④在入簇機制上選擇最近的簇頭點加入,考慮因素太片面。

2 RDEEC算法

針對DEEC算法的缺點,提出了一種改進的節能分簇路由算法RDEEC,該算法適用于多級能量異構傳感器網絡。具體實現過程如下:

①簇的建立階段:

首先,向檢測區域隨機部署N個節點,節點能量服從多級能量異構傳感器網絡設定,每個節點當選為簇頭的概率如式(8):

(8)

(9)

式中:Etotal為多級能量異構傳感器網絡整體能量,見式(1),r為當選循環輪數,rmax為設定的最大循環輪數。

記錄每個節點到基站的距離dis(i),引入邊緣度edge(i)的概念,邊緣度的計算公式如下(10):

(10)

式中:dismax為節點到基站的最遠距離。

引入邊緣度之后的當選簇頭概率pi為式(11):

pi=piedge(i)

(11)

簇頭的當選不僅要考慮節點的剩余能量,還要考慮節點的位置分布,使靠近基站的高能量節點更易當選為簇頭。

RDEEC算法的閾值同式(7),同時引入最低當選能量閾值Elow如式(12):

Elow=0.2Etotal(1-r/rmax)2/N

(12)

只有當節點的剩余能量大于Elow時才能參與簇頭選取過程,從而避免了低能量節點當選為簇頭的情況,保護了低能量節點。

在第一輪簇頭選取中,每個節點產生一個0～1的隨機數,若該隨機數小于式(7)設定的閾值,則該節點當選為簇頭。

從第二輪開始,上一輪中未當選簇頭且剩余能量大于Elow的普通節點參與簇頭選取,同時,上一輪中當選過簇頭且剩余能量大于重復當選能量閾值的節點也被允許參與簇頭選取。重復當選閾值如式(13):

Erep=1.5Etotal(1-r/rmax)/N

(13)

這樣,可以使高能量節點反復充當簇頭,提高高能量節點的利用率。

②穩定工作階段:

簇頭選定后,普通節點執行入簇選擇,傳統入簇是選擇距離最近的簇頭加入,但由于異構傳感器網絡發送數據如式(2),在d0范圍內功率放大能耗采用自由空間模型,傳輸距離大于等于d0時,采用多路徑衰減模型。假設節點分布如圖1所示,計算普通節點選擇不同簇頭加入并發送lbit數據至基站所消耗的能量,其中εfs,εmp參數如式(14)、式(15):

εfs=10 pJ(bit·m2)

(14)

εmp=0.001 3 pJ(bit·m4)

(15)

圖1 節點分布示意圖

當節點選擇簇頭A加入后,傳輸lbit所需要消耗的能量為:

Econ1=lEelec+l×10×152+lEelec+l×0.001 3×804=2lEelec+55 498l

當節點選擇簇頭B加入后,傳輸lbit所需要消耗的能量為:

Econ2=lEelec+l×10×252+lEelec+l×0.001 3×704=2lEelec+31 213l

通過對比兩者消耗的能量,可以看出,當節點選擇距離自己最近的簇頭加入后,消耗的能量增加,說明傳統的入簇機制沒有充分考慮所有因素。

因此RDEEC算法改進后的入簇機制為式(16)

(16)

式中:dtoCH為節點到簇頭節點的距離,dtoBS為簇頭節點到基站的距離。a為設定的權重,屬于[0,1]區間內,可以根據不同的應用環境進行設定,最后選擇使D最小的簇頭節點加入。RDEEC算法流程如圖2所示。

圖2 RDEEC算法流程圖

3 仿真結果分析

在仿真環節,根據節點傳輸數據方式的不同設立了兩組實驗環境,分別是以自由空間方式傳輸為主的小面積檢測環境(10 m×10 m到100 m×100 m)和以多路徑衰減傳輸方式為主的大面積(100 m×100 m到500 m×500 m)檢測環境,并利用MATLAB仿真軟件比較在不同應用環境下,DEEC算法與RDEEC算法性能,仿真實驗參數如表1所示,基站設定為檢測區域中心。

表1 仿真參數

3.1 小面積檢測環境下仿真結果分析

從圖3可以看出在小面積檢測環境下,RDEEC算法比DEEC算法網絡生命周期更長,增長比例為18.7%～36.2%,其中檢測區域面積為100 m×100 m環境下,RDEEC算法比DEEC算法增加了36.2%的生命周期,提升最為明顯。

圖3 小面積檢測環境下生命周期對比

從整體趨勢來看,在檢測區域面積為10 m×10 m 到90 m×90 m的區間內,兩種算法網絡生命周期曲線都平緩下降,因為此時節點間傳輸距離小于有效傳輸距離d0,節點間以自由空間方式傳輸數據,耗能較少,隨著檢測面積的不斷增大,整體網絡剩余能量下降速度穩定;在檢測區域面積為100 m×100 m時,兩種算法的網絡生命周期曲線迅速下降,因為此時節點間傳輸距離出現大于d0的情況,有部分節點以多路徑損耗方式傳輸數據,大量消耗網絡能量,從而使整體網絡生命周期迅速減少。

為了更加直觀體現出在小面積檢測環境下RDEEC算法與DEEC算法的差異,本文在檢測區域面積為100 m×100 m環境下進行仿真,主要考慮以下參數:網絡生命周期,網絡能量消耗和網絡傳輸數據。

圖4為100 m×100 m環境下網絡生命周期對比。仿真結果顯示,DEEC算法網絡生命周期為1 254輪,RDEEC算法網絡生命周期為1 708輪,比DEEC算法提高了36.2%。這是由于RDEEC算法設立了雙能量閾值,保護了低能量節點,提高了高能量節點的利用率,增加了網絡生命周期;同時更長的網絡生命周期也就意味著更多的傳輸數據,如圖5所示,RDEEC算法網絡整體傳輸數據為110 947 bit,而DEEC算法僅傳輸了48 718 bit的數據,效果提升明顯。

圖5 100 m×100 m環境下網絡數據傳輸對比

圖6為100 m×100 m環境下網絡能量消耗對比。DEEC算法與RDEEC算法兩者總能量相同,但DEEC算法卻比RDEEC算法在更短時間內將網絡能量消耗殆盡,反映出RDEEC算法比DEEC算法更加節約能量。

圖6 100 m×100 m環境下網絡能量消耗對比

3.2 大面積檢測環境下仿真分析

在該類環境中,檢測區域面積大大增加,使節點間數據傳輸以多路徑衰減方式為主,兩種算法的網絡生命周期都大大縮減,如圖7所示。

圖7 大面積檢測環境下生命周期對比

仿真結果顯示,RDEEC算法比DEEC算法增加了24.4%～66.5%的生命周期,提升效果比小面積檢測環境更為明顯,因為RDEEC算法通過引入邊緣度來考慮節點位置因素,在大面積檢測環境下性能更加優異。

我們可以以圖7中曲線斜率作為下降速度的指標,以數值的方式直觀體現出兩種算法的性能。兩種算法下降速度如表2所示。

表2 網絡生命周期下降速度

從表2可以看出檢測區域面積從250 m×250 m到500 m×500 m的區間內,RDEEC算法生命周期下降速度大于DEEC算法,且在檢測區域面積為500 m×500 m時,兩種算法生命周期差距不大,說明RDEEC算法不再適合更大面積的檢測環境。

為了更加直觀體現出在大面積檢測環境下RDEEC算法與DEEC算法的差異,在檢測區域面積為300 m×300 m的環境下再次進行仿真,仿真結果如下:

圖8為300 m×300 m環境下網絡生命周期對比,仿真結果顯示DEEC算法的網絡生命周期為885輪,而RDEEC算法的生命周期為1 474輪,比DEEC算法提高了66.5%,提升效果明顯。因為隨著檢測區域面積的擴大,RDEEC算法一方面引入邊緣度使高能量且靠近基站的節點當選為簇頭,另一方面雙能量閾值又保護了因反復充當簇頭的低能量節點,從而提高了網絡生命周期。

圖8 300 m×300 m環境下網絡生命周期對比

圖9 300 m×300 m環境下數據傳輸對比

圖9為300 m×300 m環境下網絡數據傳輸對比,RDEEC算法網絡傳輸數據為35 324 bit,DEEC算法僅傳輸7 007 bit數據,可以看出RDEEC算法比起DEEC算法而言,傳輸數據量更大,更適合于大面積檢測環境,同樣如圖10所示可以直觀的看出,RDEEC算法比起DEEC算法更加節能。

圖10 300 m×300 m條件下網絡能量消耗對比

3.3 入簇機制改進仿真

針對不同的應用環境,新的入簇機制中的權重a也不同。圖11為100 m×100 m環境下不同權重a的RDEEC算法生命周期?？梢钥闯?網絡生命周期隨著權重a的增大而增加,在a=0.9的情況下網絡生命周期達到最大,因為該環境下,節點間距離小于do,節點間傳輸多采用自由空間損耗方式傳輸數據,入簇機制中的前一項所占權重更高,因此權重a大約在0.9時入簇機制達到最優,網絡生命周期最長。與此產生鮮明對比的是300 m×300 m的環境。

圖11 100 m×100 m環境下不同權重a的網絡生命周期

圖12 300 m×300 m環境下不同權重a的網絡生命周期

如圖12所示,在該環境下,權重a=0.4時網絡生命周期達到最大,因為隨著檢測區域的擴大,簇頭與基站間傳輸多采用多路徑衰減方式傳輸數據,在入簇機制中后一項成為關鍵因素,增加其權重會增加網絡的生命周期。

4 結束語

本文在DEEC算法的基礎上提出了一種改進的能量異構分簇算法RDEEC:通過設定雙能量閾值,保護了低能量節點,提高了高能量節點的利用率,延長了網絡生命周期;引入邊緣度,使簇頭選取過程中充分考慮了節點的位置因素;改進了入簇機制,使入簇機制更加合理。通過對小面積檢測環境和大面積檢測環境的仿真結果分析,RDEEC算法在網絡生命周期、網絡數據傳輸、網絡能量損耗方面比DEEC算法更加優秀,且在大面積檢測環境下比DEEC算法改善明顯,為100 m×100 m到500 m×500 m范圍內檢測區域提供了一種更加節能有效的路由算法;但該改進算法不適用于500 m×500 m以上的檢測環境,后續研究將利用多跳機制解決遠距離傳輸問題,與RDEEC算法實現優勢互補。

[1] 錢志鴻,王義君. 面向物聯網的無線傳感器網絡綜述[J]. 電子與信息學報,2013(1):215-227.

[2] 龍勝春,盧定乾,池凱凱. 基于同構傳感器網絡的能量空洞避免策略[J]. 傳感技術學報,2016,29(1):103-108.

[3] 司海飛,楊忠,王珺. 無線傳感器網絡研究現狀與應用[J]. 機電工程,2011(1):16-20,37.

[4] 彭蕾,呂敬祥,劉秋平. 大規模無線傳感網絡的混合LEACH協議研究[J]. 傳感技術學報,2016,29(11):1737-1741.

[5] Chauhan T,Nayyer M. Review on Energy Efficient Protocol Based on LEACH,PEGASIS and TEEN. 2016 International Conference on Emerging Trends in Communication Technologies(ETCT),Dehradun,India,2016:1-5.

[6] Tiwari T,Roy N R. Modified DEEC:A Varying Power Level Based Clustering Technique for WSNs. 2015 International Conference on Computer and Computational Sciences(ICCCS),Noida,2015:170-176.

[7] Divya C,Krishnan N,Krishnapriya P. Modified Distributed Energy-Efficient Cluster for Heterogeneous Wireless Sensor Networks. 2013 IEEE International Conference ON Emerging Trends in Computing,Communication and Nanotechnology(ICECCN),Tirunelveli,2013:611-615.

[8] Shaji M. Distributed Energy Efficient Heterogeneous Clustering in Wireless Sensor Network. 2015 Fifth International Conference on Advances in Computing and Communications(ICACC),Kochi,2015:30-134.

[9] 潘巨龍,聞育. 無線傳感器網絡的異構性研究[J]. 航空計算技術,2007(2):124-126,130.

[10] 蔡海濱,琚小明,曹奇英. 多級能量異構無線傳感器網絡的能量預測和可靠聚簇路由協議[J]. 計算機學報,2009(12):2393-2402.

[11] 魏春娟,楊俊杰,張志美. 一種分布式能量有效的無線傳感器網絡分簇路由算法[J]. 傳感技術學報,2013,26(7):1014-1018.

[12] 葉繼華,王文,江愛文. 一種基于LEACH的異構WSN能量均衡成簇協議[J]. 傳感技術學報,2015,28(12):1853-1860.

[13] 梁英. 基于能量異構網絡環境下的WSN優化成簇算法[J]. 沈陽理工大學學報,2009(2):57-61.

李安超(1993-),男,山東人,碩士研究生,2016年于長春理工大學獲得學士學位,主要研究方向為無線通信,WSNs技術,lac1105@163.com;

陳桂芬(1964-),女,吉林人,博士,教授,1991于吉林工業大學獲得碩士學位,2009年于長春理工大學獲得博士學位,2004年～2005年作為訪問學者在華沙理工大學學習,主要從事光通信技術、信息理論及編碼技術、信息檢測及信號處理方面的研究,chenguif@163.com。

AnImprovedClusteringRoutingAlgorithmforEnergyHeterogeneousWirelessSensorNetworks*

LIAnchao,CHENGuifen*

(School of Electronic and Information Engineering,Changchun University of Science and Technology,Changchun 130022,China)

As core technology of wireless sensor net,routing algorithm plays a crucial role in prolonging net life circle and improving net efficiency. The article puts forward an improved energy isomerism cluster routing algorithm aiming at troubles of distributed energy effective cluster algorithm in lack of consideration of node position,node protection and insufficient utilization. The algorithm introduces concept of margin degree,so as to enable node near to base station act as cluster head in priority,reduce net energy consumption;establishes double-energy threshold value,improves node energy utilization,prolongs node life circle;and the article puts forward more reasonable in-cluster mechanism under the comprehensive consideration of position distribution of node,cluster head and base station. The simulation results showed that compared with former algorithm,the net life circle of improved algorithm increased 18.7% to 36.2%,24.4% to 66.5% under the condition of small area detection(10 m×10 m to 100 m×100 m)and large area detection(100 m×100 m to 500 m×500 m).

heterogeneous wireless sensor networksrouting protocol;edge degree;dual energy threshold;join cluster mechanism

TN92

A

1004-1699(2017)11-1712-07

項目來源:吉林省發改委項目(2016C089)

2017-05-04修改日期2017-06-28

10.3969/j.issn.1004-1699.2017.11.017