王 雪，董 博

(1.遼寧大學(xué)信息化中心，遼寧 沈陽(yáng) 110031； 2.遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院，遼寧 沈陽(yáng) 110031)

一種基于能量有效性的反應(yīng)式路由算法的研究

王 雪1，董 博2

(1.遼寧大學(xué)信息化中心，遼寧 沈陽(yáng) 110031； 2.遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院，遼寧 沈陽(yáng) 110031)

針對(duì)提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的穩(wěn)定性及其生存時(shí)間的問(wèn)題，結(jié)合TEEN和DEEC方法，通過(guò)設(shè)置相關(guān)參數(shù)，提出了一種新的路由算法即改進(jìn)的能量有效性算法EEER，并進(jìn)行了仿真實(shí)驗(yàn).結(jié)果表明，EEER算法可以延長(zhǎng)網(wǎng)絡(luò)的生存周期并提高網(wǎng)絡(luò)的穩(wěn)定性.

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；簇頭；能量有效性；路由算法

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

本文針對(duì)時(shí)間為關(guān)鍵因素的應(yīng)用設(shè)計(jì)了一種協(xié)議，使其在同構(gòu)和異構(gòu)的網(wǎng)絡(luò)中都具有較好的性能.

1 相關(guān)工作

在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，根據(jù)應(yīng)用模式的不同，將無(wú)線(xiàn)自組織網(wǎng)絡(luò)分為主動(dòng)型(proactive)協(xié)議和響應(yīng)型(reactive)協(xié)議2種類(lèi)型.主動(dòng)型傳感器網(wǎng)絡(luò)協(xié)議通常持續(xù)監(jiān)測(cè)周?chē)奈镔|(zhì)現(xiàn)象，并以恒定速率發(fā)送監(jiān)測(cè)數(shù)據(jù)；而響應(yīng)型路由協(xié)議及相關(guān)算法，只有在被觀測(cè)變量及數(shù)據(jù)發(fā)生變化時(shí)才進(jìn)行數(shù)據(jù)傳送.因此，響應(yīng)型傳感器網(wǎng)絡(luò)更適合在敏感時(shí)間的應(yīng)用中.

1.1 TEEN算法

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

1.2 DEEC算法

DEEC[7]是一種主動(dòng)型協(xié)議，用于兩級(jí)或多級(jí)異構(gòu)網(wǎng)絡(luò).具有較高的初始能量和較多的剩余能量的節(jié)點(diǎn)更容易被選為CH節(jié)點(diǎn).

在兩級(jí)異構(gòu)網(wǎng)絡(luò)中，存在兩類(lèi)節(jié)點(diǎn).mN為高級(jí)節(jié)點(diǎn)，初始能量為E0(1+a)；(1-m)N為普通節(jié)點(diǎn).E0是初始化能量，a和m為百分比類(lèi)型的變量，用來(lái)控制節(jié)點(diǎn)是普通節(jié)點(diǎn)或者高級(jí)節(jié)點(diǎn).網(wǎng)絡(luò)中消耗能量的總和表示為

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

(1)

所有多層次異構(gòu)網(wǎng)絡(luò)初始能量總和表示為

(2)

兩級(jí)異構(gòu)網(wǎng)絡(luò)中普通節(jié)點(diǎn)成為頭結(jié)點(diǎn)CH的概率為

(3)

擴(kuò)展到多級(jí)異構(gòu)網(wǎng)絡(luò)中，CH的概率可以表示為

(4)

假設(shè)節(jié)點(diǎn)均勻分布在M×M區(qū)域內(nèi)，則節(jié)點(diǎn)到CH節(jié)點(diǎn)間的距離為

(5)

頭節(jié)點(diǎn)CH到基站BS的距離為

(6)

2 EEER算法描述

2.1 網(wǎng)絡(luò)性能評(píng)估指標(biāo)

本文定義了一系列相關(guān)性能參數(shù)用來(lái)對(duì)比算法的性能.

定義1(穩(wěn)定時(shí)長(zhǎng)) 該時(shí)長(zhǎng)表示網(wǎng)絡(luò)中節(jié)點(diǎn)初始化完成，從網(wǎng)絡(luò)開(kāi)始運(yùn)行時(shí)間t0直到某一個(gè)節(jié)點(diǎn)無(wú)法響應(yīng)的時(shí)間tNodedied.即

(7)

(8)

TNLT=TInstability+TStability.

(9)

定義4(存活網(wǎng)絡(luò)節(jié)點(diǎn)) 表示能夠正常運(yùn)行的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量.即

NAlive=NAll-NDied.

(10)

其中NDied表示節(jié)點(diǎn)剩余能量Ei=0的節(jié)點(diǎn).有

(11)

2.2EEER算法

基于上述內(nèi)容，本文提出EEER算法.算法用于改善在分組過(guò)程中的穩(wěn)定性，適用于響應(yīng)型同構(gòu)或者異構(gòu)傳感器網(wǎng)絡(luò)中運(yùn)行.

步驟1ni表示對(duì)于節(jié)點(diǎn)si成為頭結(jié)點(diǎn)的選舉過(guò)程中所經(jīng)過(guò)的輪數(shù).在網(wǎng)絡(luò)運(yùn)行過(guò)程中，所有結(jié)點(diǎn)不可能具有相同的剩余能量.基于r輪結(jié)點(diǎn)si不同，剩余能量Ei(r)選取不同的ni.

步驟2 令pi=1/ni為經(jīng)過(guò)ni輪成為CH結(jié)點(diǎn)的概率.當(dāng)節(jié)點(diǎn)在一個(gè)周期內(nèi)具有相同的能量時(shí)，pi=popt確保每輪的CH結(jié)點(diǎn)數(shù)量為poptN，這樣能使得節(jié)點(diǎn)死亡的時(shí)間大致相同.

步驟4 當(dāng)簇(子集)形成之后，CH結(jié)點(diǎn)發(fā)送2個(gè)閾值.分別為硬閾值δ及軟閾值Υ.各傳感器節(jié)點(diǎn)不斷監(jiān)控內(nèi)部變量X值.如果其數(shù)值達(dá)到了δ即X≥δ，該節(jié)點(diǎn)觸發(fā)數(shù)據(jù)發(fā)送過(guò)程，如圖1所示.

(a)子集形成X<δ

(b)X≥δ觸發(fā)發(fā)送過(guò)程

步驟5 當(dāng)前值Cv表示第一次發(fā)生傳輸過(guò)程發(fā)生時(shí)變量數(shù)值.Cv被存儲(chǔ)在稱(chēng)為感測(cè)節(jié)點(diǎn)中的一個(gè)內(nèi)部變量Y中.從而減少了傳輸?shù)臄?shù)據(jù)量.如果Cv-Y≥Υ，再一次進(jìn)行數(shù)據(jù)傳輸.

每個(gè)節(jié)點(diǎn)通過(guò)初始化能量和剩余能量選舉出頭結(jié)點(diǎn)CH，使得每個(gè)節(jié)點(diǎn)都?xì)w并到某一個(gè)簇中.在步驟3中，每輪選舉過(guò)程中不需要知道所有結(jié)點(diǎn)的能量形成子集并選出CH結(jié)點(diǎn).步驟4中，節(jié)點(diǎn)發(fā)現(xiàn)當(dāng)X≥δ時(shí)，頭節(jié)點(diǎn)CH匯集數(shù)據(jù)觸發(fā)發(fā)送過(guò)程，并將當(dāng)前X存儲(chǔ)到變量Y中.最后的步驟5中，通過(guò)采用變化的差值大于閾值Υ時(shí)才進(jìn)行傳輸?shù)臋C(jī)制，進(jìn)一步減少了傳輸?shù)臄?shù)據(jù)量.

2.3 算法分析

主動(dòng)感知類(lèi)路由的協(xié)議，通過(guò)感知節(jié)點(diǎn)的周?chē)h(huán)境并定期傳輸數(shù)據(jù).由于周期性傳輸數(shù)據(jù)會(huì)不斷地消耗能量.因此，本文算法的主要目的是延長(zhǎng)網(wǎng)絡(luò)生存周期，增加吞吐量和降低能量消耗.與主動(dòng)式路由協(xié)議相比，EEER被動(dòng)式路由協(xié)議是依賴(lài)型的應(yīng)用[9-10].其定期感測(cè)周?chē)h(huán)境，但只有當(dāng)?shù)竭_(dá)閾值時(shí)才進(jìn)行發(fā)送.

因此，在被動(dòng)式路由協(xié)議中[11]，吞吐量的大小由其應(yīng)用所決定.在反應(yīng)式網(wǎng)絡(luò)中吞吐量與網(wǎng)絡(luò)的生命周期及網(wǎng)絡(luò)的穩(wěn)定時(shí)長(zhǎng)成反比.如果傳輸量較小，網(wǎng)絡(luò)的穩(wěn)定時(shí)長(zhǎng)和網(wǎng)絡(luò)的生存周期會(huì)延長(zhǎng).通過(guò)設(shè)置的參數(shù)δ和參數(shù)Υ可以調(diào)節(jié)網(wǎng)絡(luò)的生存周期.例如，如果當(dāng)前值X頻繁超過(guò)δ，那么數(shù)據(jù)傳輸過(guò)程也會(huì)頻繁發(fā)生，網(wǎng)絡(luò)的穩(wěn)定時(shí)長(zhǎng)就會(huì)很短.

3 實(shí)驗(yàn)與仿真

采用NS-3進(jìn)行模擬.節(jié)點(diǎn)數(shù)量為100，隨機(jī)部署在100 m×100 m的正方形區(qū)域.假設(shè)基站位于區(qū)域中心.為了評(píng)估EEER的性能，選取TEEN協(xié)議和DEEC協(xié)議進(jìn)行對(duì)比.實(shí)驗(yàn)過(guò)程中所使用的參數(shù)如表1所示.

表1 仿真過(guò)程選用參數(shù)

3.1 實(shí)驗(yàn)過(guò)程

實(shí)驗(yàn)的實(shí)施過(guò)程分成兩個(gè)階段.第一階段設(shè)置EEER參數(shù)δ=100和參數(shù)Υ=3，進(jìn)行實(shí)驗(yàn)?zāi)M，對(duì)比TEEN、DEEC與EEER的網(wǎng)絡(luò)生存周期和傳輸?shù)紹S的數(shù)據(jù)包傳輸數(shù)量；第二階段，改變實(shí)驗(yàn)參數(shù)δ=60和參數(shù)Υ=10，再次對(duì)比本協(xié)議同其他2種協(xié)議的相關(guān)性能參數(shù).

3.2 實(shí)驗(yàn)結(jié)果

第一階段網(wǎng)絡(luò)的生存周期如圖2所示，從圖2中可以看出，TEEN協(xié)議第一個(gè)節(jié)點(diǎn)死亡之后，剩余節(jié)點(diǎn)經(jīng)過(guò)很少的輪數(shù)之后相繼死亡.這是由于所有成為CH節(jié)點(diǎn)具有的相同的概率.DEEC協(xié)議相對(duì)延長(zhǎng)了持久度時(shí)長(zhǎng)和網(wǎng)絡(luò)生存的時(shí)間，主要原因是由于CH的選取過(guò)程以殘余能量作為基礎(chǔ).含有較高的剩余能量節(jié)點(diǎn)具有成為CH更大的概率.

EEER的節(jié)點(diǎn)生存周期同其他2種協(xié)議相比，穩(wěn)定時(shí)長(zhǎng)分別延長(zhǎng)了51.7%和46.6%.EEER采用硬閾值提高了網(wǎng)絡(luò)穩(wěn)定性和網(wǎng)絡(luò)的生存周期，軟閾值進(jìn)一步減少了數(shù)據(jù)的傳輸次數(shù)，從而降低了傳輸?shù)交?BS)的傳輸數(shù)據(jù)包的數(shù)量，降低了能源消耗，延長(zhǎng)了網(wǎng)絡(luò)壽命(見(jiàn)圖3).

圖2 節(jié)點(diǎn)能量相同網(wǎng)絡(luò)生存周期對(duì)比

圖3 節(jié)點(diǎn)能量同構(gòu)情況下發(fā)送到BS的數(shù)據(jù)包數(shù)

第二階段對(duì)部分節(jié)點(diǎn)采用高能節(jié)點(diǎn)的設(shè)置，同時(shí)調(diào)整了EEER的參數(shù)，設(shè)置δ=60和Υ=10，結(jié)果見(jiàn)圖4.在圖4中用EEER2表示.由于部分高能節(jié)點(diǎn)的加入，3種協(xié)議的網(wǎng)絡(luò)生存周期都有所增加.另外，我們采用更改參數(shù)方式，可以更加靈活地調(diào)整網(wǎng)絡(luò)的生存周期與吞吐量之間的關(guān)系，從而適應(yīng)多種不同的應(yīng)用環(huán)境.

圖4 節(jié)點(diǎn)能量異構(gòu)網(wǎng)絡(luò)生存周期對(duì)比

圖5 節(jié)點(diǎn)能量異構(gòu)情況下發(fā)送到BS的數(shù)據(jù)包數(shù)

本文提出的算法在一定程度上提高了網(wǎng)絡(luò)的生存周期，同時(shí)由于協(xié)議采用軟硬2種閾值，增加了協(xié)議的靈活程度.通過(guò)減少硬閾值δ，EEER的穩(wěn)定時(shí)長(zhǎng)和網(wǎng)絡(luò)壽命發(fā)生明顯變化.穩(wěn)定期和網(wǎng)絡(luò)的生命周期降低.減少了2個(gè)閾值的EEER協(xié)議與DEEC的差異也在減小.同時(shí)硬閾值也影響了網(wǎng)絡(luò)的生存周期.如果傳輸數(shù)據(jù)包的數(shù)量增加，網(wǎng)絡(luò)的生命周期會(huì)隨之減小，同樣數(shù)據(jù)包的數(shù)量減少，網(wǎng)絡(luò)的生存周期會(huì)隨之增加(見(jiàn)圖5).

4 結(jié)束語(yǔ)

本文提出了基于能量有效性的反應(yīng)式路由算法EEER，該算法與TEEN和DEEC相結(jié)合，同時(shí)設(shè)置了相關(guān)的參數(shù)對(duì)原有的算法加以改進(jìn).通過(guò)實(shí)驗(yàn)可以看出，本文算法繼承了先前算法的優(yōu)點(diǎn)，并且比原有算法TEEN和DEEC延長(zhǎng)了網(wǎng)絡(luò)生存周期，具有更好的實(shí)用性.

[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] 吳鵬悅，季薇. 基于能量有效性和時(shí)間有效性的聯(lián)合優(yōu)化綠色通信算法[J]. 計(jì)算機(jī)應(yīng)用，2014，34(7):1969-1973.

[11] 黃廷輝，伊凱，崔更申，等. 基于非均勻分簇的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分層路由協(xié)議[J]. 計(jì)算機(jī)應(yīng)用，2016，36(1):66-71.

(責(zé)任編輯：石紹慶)

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

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

王雪(1981—)，女，實(shí)驗(yàn)師，主要從事數(shù)據(jù)挖掘、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、信息化應(yīng)用研究；董博(1981—)，男，副教授，主要從事人工智能、數(shù)據(jù)挖掘、電子商務(wù)研究.

TP 393 [學(xué)科代碼] 520·10

A