一種基于能量有效性的反應式路由算法的研究

王 雪，董 博

(1.遼寧大學信息化中心，遼寧 沈陽 110031； 2.遼寧大學創新創業學院，遼寧 沈陽 110031)

一種基于能量有效性的反應式路由算法的研究

王 雪1，董 博2

(1.遼寧大學信息化中心，遼寧 沈陽 110031； 2.遼寧大學創新創業學院，遼寧 沈陽 110031)

針對提高無線傳感器網絡的穩定性及其生存時間的問題，結合TEEN和DEEC方法，通過設置相關參數，提出了一種新的路由算法即改進的能量有效性算法EEER，并進行了仿真實驗.結果表明，EEER算法可以延長網絡的生存周期并提高網絡的穩定性.

無線傳感器網絡；簇頭；能量有效性；路由算法

無線傳感器網絡(WSN)近年來成為一個熱門的研究課題，其主要原因在于這種網絡可以廣泛使用在工業、軍事、人體健康和環境監測等多個領域.數據傳感器可能以分散或者均勻的方式部署在基站周圍進行數據采集.這種網絡特點使得在設計傳感器網絡的時候需要考慮到多方面的因素，如電池容量、硬件資源、部署的隨機性和動態不可靠環境等.近年來，無線傳感器網絡中的路由協議提出了很多算法，眾多算法[1-3]對網絡協議進行了多方面的設計，其中能量的節約作為其中一個重要的因素，得到了很大的關注.[4]W.B.Heinzelman等人[5]提出了用于無線傳感器的算法LEACH，其主要思想是把節點進行分簇，從而形成傳感器節點的集群.這樣只在簇頭節點Cluster Head(CH)執行到基站Base Station(BS)的數據進行傳輸，節約了能量.LEACH協議在由數據結構相同的節點組成的網絡內能夠很好地運行，而在異構的網絡中，性能嚴重惡化.文獻[6]提出了一種反應式路由協議，該路由協議把時間作為主要考慮因素.頭結點CH的選擇過程與LEACH的方案相同.CH的廣播采用兩種閾值，進行廣播包的控制，這樣不僅降低了數據包傳輸的數量也增加了網絡的生存期.文獻[7]提出DEEC(Distributed Energy Efficient Clustering)協議.DEEC也是一種聚類協議，它用于兩級及多級異構網絡.頭結點CH的選舉過程基于剩余的節點能量和網絡的平均能量，具有較高初始化能量的結點成為頭節點的概率較大.然而，DEEC對于異構網絡的支持性不足，同時也不適合實時應用.

本文針對時間為關鍵因素的應用設計了一種協議，使其在同構和異構的網絡中都具有較好的性能.

1 相關工作

在無線傳感器網絡中，根據應用模式的不同，將無線自組織網絡分為主動型(proactive)協議和響應型(reactive)協議2種類型.主動型傳感器網絡協議通常持續監測周圍的物質現象，并以恒定速率發送監測數據；而響應型路由協議及相關算法，只有在被觀測變量及數據發生變化時才進行數據傳送.因此，響應型傳感器網絡更適合在敏感時間的應用中.

1.1 TEEN算法

TEEN[8](Threshold Sensitive Energy Efficient Sensor Network Protocol)是第一個被提出的反應式路由算法，TEEN算法和LEACH算法的實現過程相類似，TEEN是響應型的算法，而LEACH屬于主動型算法.在TEEN算法中定義了硬、軟2個閾值，用來確定是否進行數據發送.當數據量第一次超過設定的硬閾值時，網絡節點用新值作為硬閾值，并在下一個時間間隔內進行發送.如果節點收集的數據的變化幅度較大，并且大于軟閾值的范圍，則節點將會傳送最新采集的數據，并且將它作為新的閾值.該算法通過調節閾值的大小，可以在監測精度和系統能耗之間取得合理的平衡，從而降低了傳輸數據的數量.

1.2 DEEC算法

DEEC[7]是一種主動型協議，用于兩級或多級異構網絡.具有較高的初始能量和較多的剩余能量的節點更容易被選為CH節點.

在兩級異構網絡中，存在兩類節點.mN為高級節點，初始能量為E0(1+a)；(1-m)N為普通節點.E0是初始化能量，a和m為百分比類型的變量，用來控制節點是普通節點或者高級節點.網絡中消耗能量的總和表示為

ETotal=N(1-m)E0+NmE0(1+a)=NE0(1+am).

(1)

所有多層次異構網絡初始能量總和表示為

(2)

兩級異構網絡中普通節點成為頭結點CH的概率為

(3)

擴展到多級異構網絡中，CH的概率可以表示為

(4)

假設節點均勻分布在M×M區域內，則節點到CH節點間的距離為

(5)

頭節點CH到基站BS的距離為

(6)

2 EEER算法描述

2.1 網絡性能評估指標

本文定義了一系列相關性能參數用來對比算法的性能.

定義1(穩定時長) 該時長表示網絡中節點初始化完成，從網絡開始運行時間t0直到某一個節點無法響應的時間tNodedied.即

(7)

(8)

TNLT=TInstability+TStability.

(9)

定義4(存活網絡節點) 表示能夠正常運行的網絡節點數量.即

NAlive=NAll-NDied.

(10)

其中NDied表示節點剩余能量Ei=0的節點.有

(11)

2.2EEER算法

基于上述內容，本文提出EEER算法.算法用于改善在分組過程中的穩定性，適用于響應型同構或者異構傳感器網絡中運行.

步驟1ni表示對于節點si成為頭結點的選舉過程中所經過的輪數.在網絡運行過程中，所有結點不可能具有相同的剩余能量.基于r輪結點si不同，剩余能量Ei(r)選取不同的ni.

步驟2 令pi=1/ni為經過ni輪成為CH結點的概率.當節點在一個周期內具有相同的能量時，pi=popt確保每輪的CH結點數量為poptN，這樣能使得節點死亡的時間大致相同.

步驟4 當簇(子集)形成之后，CH結點發送2個閾值.分別為硬閾值δ及軟閾值Υ.各傳感器節點不斷監控內部變量X值.如果其數值達到了δ即X≥δ，該節點觸發數據發送過程，如圖1所示.

(a)子集形成X<δ

(b)X≥δ觸發發送過程

步驟5 當前值Cv表示第一次發生傳輸過程發生時變量數值.Cv被存儲在稱為感測節點中的一個內部變量Y中.從而減少了傳輸的數據量.如果Cv-Y≥Υ，再一次進行數據傳輸.

每個節點通過初始化能量和剩余能量選舉出頭結點CH，使得每個節點都歸并到某一個簇中.在步驟3中，每輪選舉過程中不需要知道所有結點的能量形成子集并選出CH結點.步驟4中，節點發現當X≥δ時，頭節點CH匯集數據觸發發送過程，并將當前X存儲到變量Y中.最后的步驟5中，通過采用變化的差值大于閾值Υ時才進行傳輸的機制，進一步減少了傳輸的數據量.

2.3 算法分析

主動感知類路由的協議，通過感知節點的周圍環境并定期傳輸數據.由于周期性傳輸數據會不斷地消耗能量.因此，本文算法的主要目的是延長網絡生存周期，增加吞吐量和降低能量消耗.與主動式路由協議相比，EEER被動式路由協議是依賴型的應用[9-10].其定期感測周圍環境，但只有當到達閾值時才進行發送.

因此，在被動式路由協議中[11]，吞吐量的大小由其應用所決定.在反應式網絡中吞吐量與網絡的生命周期及網絡的穩定時長成反比.如果傳輸量較小，網絡的穩定時長和網絡的生存周期會延長.通過設置的參數δ和參數Υ可以調節網絡的生存周期.例如，如果當前值X頻繁超過δ，那么數據傳輸過程也會頻繁發生，網絡的穩定時長就會很短.

3 實驗與仿真

采用NS-3進行模擬.節點數量為100，隨機部署在100 m×100 m的正方形區域.假設基站位于區域中心.為了評估EEER的性能，選取TEEN協議和DEEC協議進行對比.實驗過程中所使用的參數如表1所示.

表1 仿真過程選用參數

3.1 實驗過程

實驗的實施過程分成兩個階段.第一階段設置EEER參數δ=100和參數Υ=3，進行實驗模擬，對比TEEN、DEEC與EEER的網絡生存周期和傳輸到BS的數據包傳輸數量；第二階段，改變實驗參數δ=60和參數Υ=10，再次對比本協議同其他2種協議的相關性能參數.

3.2 實驗結果

第一階段網絡的生存周期如圖2所示，從圖2中可以看出，TEEN協議第一個節點死亡之后，剩余節點經過很少的輪數之后相繼死亡.這是由于所有成為CH節點具有的相同的概率.DEEC協議相對延長了持久度時長和網絡生存的時間，主要原因是由于CH的選取過程以殘余能量作為基礎.含有較高的剩余能量節點具有成為CH更大的概率.

EEER的節點生存周期同其他2種協議相比，穩定時長分別延長了51.7%和46.6%.EEER采用硬閾值提高了網絡穩定性和網絡的生存周期，軟閾值進一步減少了數據的傳輸次數，從而降低了傳輸到基站(BS)的傳輸數據包的數量，降低了能源消耗，延長了網絡壽命(見圖3).

圖2 節點能量相同網絡生存周期對比

圖3 節點能量同構情況下發送到BS的數據包數

第二階段對部分節點采用高能節點的設置，同時調整了EEER的參數，設置δ=60和Υ=10，結果見圖4.在圖4中用EEER2表示.由于部分高能節點的加入，3種協議的網絡生存周期都有所增加.另外，我們采用更改參數方式，可以更加靈活地調整網絡的生存周期與吞吐量之間的關系，從而適應多種不同的應用環境.

圖4 節點能量異構網絡生存周期對比

圖5 節點能量異構情況下發送到BS的數據包數

本文提出的算法在一定程度上提高了網絡的生存周期，同時由于協議采用軟硬2種閾值，增加了協議的靈活程度.通過減少硬閾值δ，EEER的穩定時長和網絡壽命發生明顯變化.穩定期和網絡的生命周期降低.減少了2個閾值的EEER協議與DEEC的差異也在減小.同時硬閾值也影響了網絡的生存周期.如果傳輸數據包的數量增加，網絡的生命周期會隨之減小，同樣數據包的數量減少，網絡的生存周期會隨之增加(見圖5).

4 結束語

本文提出了基于能量有效性的反應式路由算法EEER，該算法與TEEN和DEEC相結合，同時設置了相關的參數對原有的算法加以改進.通過實驗可以看出，本文算法繼承了先前算法的優點，并且比原有算法TEEN和DEEC延長了網絡生存周期，具有更好的實用性.

[1] YAO YANJUN，QING CAO，ATHANASIOS V. VASILAKOS: An energy-efficient，delay-aware，and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J]. Networking IEEE/ACM Transactions on，2015，23(6):810-823.

[2] HEINZELMAN WENDI B.，ANANTHA P. CHANDRAKASAN，HARI BALAKRISHNAN. An application-specific protocol architecture for wireless microsensor networks[J]. Wireless Communications IEEE Transactions on，2002，1(4): 660-670.

[3] SINGH M P，GORE M M. A new energy-efficient clustering protocol for wireless sensor networks[C]// Intelligent Sensors，Sensor Networks and Information Processing Conference，2005. Proceedings of the 2005 International Conference on，Hatfield：IEEE，2006:25-30.

[4] CHELLATHURAI，A. SAMUEL，E. GEORGE DHARMA PRAKASH RA. A strategic review of routing protocols for mobile ad hoc networks[J]. International Journal of Engineering Trends & Technology，2014，10(8):390-395.

[5] HABIBI，JALAL，ALI GHRAYEB，AMIR G. AGHDAM. Energy-efficient cooperative routing in wireless sensor networks: a mixed-integer optimization framework and explicit solution[J]. IEEE Transactions on Communications，2013，61(8):3424-3437.

[6] MANJESHWAR A，DHARMA P. TEEN:A routing protocol for enhanced efficiency in wireless sensor networks[C]//Proceedings International Parallel & Distributed Processing Symposium，San Francisco：IEEE，2001:2009-2015.

[7] LIU JINGJING，YANJUN HU. A balanced and energy-efficient clustering algorithm for heterogeneous wireless sensor networks[C]// Wireless Communications and Signal Processing (WCSP)，2014 Sixth International Conference on，Hefei：IEEE，2014:1-6.

[8] TYAGI S S，CHAUHAN R K. Performance analysis of proactive and reactive routing protocols for ad hoc networks[J]. International Journal of Computer Applications，2010，1(14):27-30.

[9] ALMURIB H A F，KUMAR T N，LOMBARDI F. Scalable application-dependent diagnosisof interconnects of SRAM-based FPGAs[J]. IEEE Transactions on Computers，2014，63(63):1540-1550.

[10] 吳鵬悅，季薇. 基于能量有效性和時間有效性的聯合優化綠色通信算法[J]. 計算機應用，2014，34(7):1969-1973.

[11] 黃廷輝，伊凱，崔更申，等. 基于非均勻分簇的無線傳感器網絡分層路由協議[J]. 計算機應用，2016，36(1):66-71.

(責任編輯：石紹慶)

Aresearchbasedonenergyefficientreactivealgorithmforwirelesssensornetworking

WANG Xue1，DONG Bo2

(1 Information Technology Center，Liaoning University，Shenyang 110031，China; 2.School of Innovation and Entrepreneurship，Liaoning University，Shenyang 110031，China)

In order to improve the stability and lifetime of wireless sensor network，using the combination of TEEN and DEEC by setting the relevant parameters，this paper proposed a new routing algorithm named EEER algorithm which improved energy efficiency，and the simulation results show that the EEER algorithm can prolong the network lifetime and improve the stability of the network.

WSN；cluster head；energy efficient；routing algorithm

1000-1832(2017)03-0068-05

10.16163/j.cnki.22-1123/n.2017.03.015

2016-12-30

國家自然科學基金資助項目(61502090)；遼寧省教育廳科技項目(LYB201620);國家檔案局科技項目(2016-X-25)；遼寧省檔案局科技項目(L-2016-R-6，L-2017-R-7).

王雪(1981—)，女，實驗師，主要從事數據挖掘、無線傳感器網絡、信息化應用研究；董博(1981—)，男，副教授，主要從事人工智能、數據挖掘、電子商務研究.

TP 393 [學科代碼] 520·10

A