王 雷，王 珺，朱志偉，吳 涵

(1.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室,江蘇 南京 210003;2.南京郵電大學 江蘇省無線通信重點實驗室,江蘇 南京 210003)

無線傳感網中基于能量均衡的機會路由算法

王 雷1,2，王 珺1,2，朱志偉1,2，吳 涵1,2

(1.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室,江蘇 南京 210003;2.南京郵電大學 江蘇省無線通信重點實驗室,江蘇 南京 210003)

機會路由實現了數據在有損無線鏈路中的高吞吐量傳輸?，F有的機會路由協議—MORE，雖然是第一個將網絡編碼應用到機會路由中的，但是在選擇候選轉發(fā)節(jié)點集時，僅考慮節(jié)點間的鏈路質量，使得部分節(jié)點因為能量耗盡而過早死亡，影響了無線傳感網的整體性。針對這一突出問題，提出了一種改進的基于MORE協議的機會路由算法，以均衡節(jié)點的能量消耗。根據機會路由的傳輸機制，綜合考慮節(jié)點的期望傳輸次數(ETX)和剩余能量(RE)，提出了一種新的路由測度期望生存時間(ELT)和基于它的候選轉發(fā)節(jié)點集的選擇策略。最后，基于NS2仿真平臺進行仿真分析。仿真結果表明：在考慮節(jié)點剩余能量的基礎上，改進MORE協議既保證了數據傳輸的可靠性，同時均衡了節(jié)點的能量消耗，提高了節(jié)點生存時間，延長了網絡的生命周期。

機會路由；期望傳輸次數；剩余能量；期望生存時間

0 引 言

作為21世紀最有影響力的技術之一，無線傳感器網絡(WSNs)[1]正在深刻改變著人類的生活。而路由協議作為無線傳感器網絡技術發(fā)展的關鍵因素之一，一直是近年來的研究熱點。

用于無線網絡的傳統(tǒng)路由協議，在實際的數據傳輸開始之前，會預先選擇一個或多個理想的、確定的路徑作為最佳路徑路由。這種策略的最大缺點是，它只是簡單應用了最初設想用于有線網絡路由的解決方案和規(guī)則。事實上，傳統(tǒng)的無線路由協議不能很好地適應無線環(huán)境的變化。因此，傳統(tǒng)無線路由協議將引起鏈路層的過度重傳，網絡資源的重傳，甚至可能導致系統(tǒng)的崩潰。此外，無線媒介被認為是這些協議的限制，因為它的動態(tài)變化、擁擠等，是很難控制的。但是，在機會路由[2]中，共享無線介質被認為是機會而不是限制。

機會路由背后的關鍵思想是，利用無線媒介廣播特性克服無線傳輸不可靠的缺點。也就是說，不同于在每一次的傳輸過程中，預先選擇中繼節(jié)點，機會路由是廣播數據分組，以便它的鄰居節(jié)點能夠偵聽到該數據包，而后這些鄰居節(jié)點成為它的候選中繼節(jié)點集。之后，實際的數據包轉發(fā)節(jié)點將從這些成功接收到數據包的候選節(jié)點集中選擇。但是，在選擇候選節(jié)點集時，路由度量考慮不充分。

針對這一問題，在機會路由選取候選轉發(fā)節(jié)點上進行改進，定義新的路由度量，綜合考慮鏈路質量和節(jié)點剩余能量，提出一種改進的基于MORE協議的能量均衡的機會路由算法，并對此方案進行仿真驗證。

1 相關工作

在麻省理工學院(MIT)的Biswas等[2]提出機會路由的概念之后，研究者們進行了深入研究。Eric Rozner等[3]提出的SOAR協議，采用自適應轉發(fā)路徑以避免重傳，并通過基于優(yōu)先級的定時器，局部損失恢復方案與自適應速率控制，獲得了較好的性能。文獻[4]提出的多速率地理選擇路由(MGOR)，是以地理位置為基礎，并結合無線網絡中多速率傳輸的特點提出的機會路由。該協議引入OEOT路由度量，通過該路由度量達到傳輸速率和候選轉發(fā)節(jié)點集的平均優(yōu)化的目的。而面對機會路由相關的開銷問題，許多研究人員利用網絡編碼來解決該問題。S.Chachulski等[5]抓住這一特點，將隨機線性網絡編碼引入到機會路由中，提出了MAC層獨立的機會路由(MORE)協議，以非常低的成本顯著降低了節(jié)點間的協作開銷，改進了機會路由的性能。但是在該協議下，只能被動利用各節(jié)點網絡編碼機會。針對這一問題，文獻[6]提出了編碼感知機會路由協議(CAOR)。CAOR將局部流間網絡編碼策略和機會路由相結合，創(chuàng)造出更多的編碼機會，從而提高了多流情況下無線網絡的吞吐量。文獻[7]提出的CoAOR協議，主要是為了解決CAOR中轉發(fā)節(jié)點需要其兩跳鄰居節(jié)點狀態(tài)信息這一突出問題。但是，在低功耗多跳無線網絡中，即無線傳感器網絡中，能量消耗是一個極為重要的因素。因此，最近的一些機會路由協議將能量消耗這個參數考慮進去。

在節(jié)能路由的研究中，Mao等[8]提出了能量有效機會路由協議(EEOR)。在該協議中，候選轉發(fā)節(jié)點的選擇及其優(yōu)先級都是以最小能量消耗為度量。此外，EEOR認為可以通過調節(jié)傳輸功率，使得發(fā)送者逐漸增加它的發(fā)射功率達到最大閾值，從而增加候選轉發(fā)節(jié)點的數目。文獻[9]提出的MDOR路由算法，利用動態(tài)能量計算的方式，優(yōu)化網絡的端到端傳輸時延以及網絡的生存時間。Zorzi等[10]設計的地理路由協議(GeRaF)，運用基于競爭的路由機制，允許節(jié)點自主休眠與蘇醒，從而提高了網絡整體的生存時間。文獻[11]提出的CL-EE算法，是結合物理層和介質介入控制層感知的機會路由協議。該協議利用跨層之間的信息交換，以較小的能量消耗獲得了較高的端到端吞吐量。文獻[12]提出的基于拓撲和鏈路質量感知的地理機會路由協議(TLG-OR)，將地理位置、鏈路質量以及節(jié)點的剩余能量考慮進來。在候選節(jié)點集的選擇上，以地理位置為主要參考因素，選擇具有最少轉發(fā)時延的節(jié)點作為最佳轉發(fā)節(jié)點。文獻[13]提出了具有異步睡眠的機會路由協議(ORAS)，在保證發(fā)送者有潛在的轉發(fā)節(jié)點并能高效接收數據包的同時，降低能耗。文獻[14]提出了一種適用于WSN的基于協同的機會路由協議，提出新的路由度量，轉發(fā)能效，以能量有效的方式提高了數據的轉發(fā)速率，但是也增加了信令開銷。

2 基于MORE的改進算法

2.1 無線傳感網節(jié)點能耗模型

文獻[15]中提出了first-order能耗模型，該模型的結構如圖1所示。

圖1 first-order能耗模型

根據該能量消耗模型，傳輸k位數據包的發(fā)送能耗etx(d,k)與接收能耗erx(k)如下：

etx(d,k)=(eelec+eamp*d2)*k

(1)

erx(k)=eelec*k

(2)

其中，無線收發(fā)器的運行開銷為eelec=50nJ/b；傳輸開銷eamp=100 pJ/(b*m2)。

Douglas等[16]提出了期望傳輸次數(ETX)路由度量。ETX值是一個預測值，用來衡量數據包在一對節(jié)點間傳輸數據直到成功時，可能需要的次數，自然包括重傳次數。但是對于一個完整的路由，不好直接預測ETX值，所以通過將各鏈路ETX值相加的形式，得到一條路由的ETX值。

ETX的計算，由兩個因素構成，分別為前向轉發(fā)成功率df與反向ACK確認成功率dr。那么，一次傳輸的期望概率，即成功接收與確認，為df*dr。因為每一次傳輸數據包的嘗試，可以被認為是伯努利實驗，所以期望傳輸次數為：

(3)

通過對鏈路探測包的計算，可以得到轉發(fā)率df和dr。根據設定的發(fā)送周期τ，每個節(jié)點會發(fā)送固定大小的探測包。如果所有節(jié)點都在同一時間發(fā)送探測包，可能會導致同步效應，所以每個節(jié)點探測包采用0.1τ的抖動發(fā)送。另外，因為探測包的發(fā)送是以廣播的形式，而且在802.11b的機制下，不存在確認和重傳機制。所以，每個節(jié)點只要記錄在過去的時間內接收到的探測包的數據，就能夠計算轉發(fā)率，見式(4)。

(4)

其中，count(t-w,t)為在過去的ω時間內實際接收到的探測包個數；ω/T為在ω時間內應該收到的探測包數量。

通過探測包，可以計算出節(jié)點間鏈路質量，得到ETX值，這樣也能夠得出節(jié)點成功接收一個數據包時期望的能量消耗：

Erx=ETXi*erx(k)

(5)

其中，ETXi為節(jié)點i與其前一跳的ETX值。

同理，節(jié)點i成功發(fā)送一個數據包的預期能量消耗為：

Etx=ETXj*etx(d,k)

(6)

其中，ETXj為節(jié)點i與其下一條的ETX值。

那么節(jié)點i成功接收并發(fā)送一個數據包的預期能量消耗為：

EECi=Erx+Etx

(7)

2.2 ELT路由測度

ETX值代表節(jié)點間的鏈路質量，數值越小，意味著數據在節(jié)點間重傳的可能性越小，節(jié)點間的預期能量消耗也越小(根據式(7))。但是，如果單純的以ETX作為路由度量，鏈路質量較好的節(jié)點將持續(xù)不斷地作為轉發(fā)節(jié)點，那么這些節(jié)點將因為能量耗盡而過早死亡。為了保證網絡的整體性，避免部分節(jié)點的過早死亡而退出網絡，期望既保證數據傳輸的可靠性，又能夠考慮節(jié)點的剩余能量(Eres)，防止某些節(jié)點能量過早耗盡。因此，綜合了ETX和節(jié)點的剩余能量，提出了期望生存時間(ExpectedLifeTime,ELT)作為路由度量，計算公式為：

(8)

由式(8)知，ETX值越小且Eres越大，節(jié)點期望生存時間越長，那么選擇該節(jié)點轉發(fā)數據包的概率越大。

2.3 候選轉發(fā)節(jié)點集的選取

和傳統(tǒng)路由協議相比，機會路由最主要的工作在于候選轉發(fā)節(jié)點集的選擇。對于候選轉發(fā)節(jié)點集，當中的節(jié)點個數越多，可以認為數據轉發(fā)的成功率越高?？墒沁@也帶來了另一方面的問題，節(jié)點過多，它們的協作開銷將非常困難。MORE協議是根據各個節(jié)點到目的節(jié)點的ETX來選擇候選轉發(fā)節(jié)點集。在該協議中，將節(jié)點的剩余能量考慮其中，并且假設候選轉發(fā)節(jié)點集的集合大小為6，其候選轉發(fā)節(jié)點集選擇確定的具體算法如圖2所示。

圖2 確定候選轉發(fā)節(jié)點集的流程算法

2.4 改進MORE協議的性能分析

對改進MORE協議，定性分析其三大優(yōu)點：

(1)較高的可靠性。

經典MORE協議以節(jié)點間的鏈路質量作為路由測度，并采用網絡編碼的方法，在進行轉發(fā)前，將數據包隨機混合，保證了較高的數據傳輸成功率。改進MORE協議，以經典MORE協議為基礎，繼承了其高可靠性的特點。另外，以ELT作為路由度量，考慮了節(jié)點剩余能量，保證了網絡的整體性，同時提高了數據傳輸的可靠性。

(2)均衡能耗，延長網絡生存時間。

所提出的ELT路由測度，綜合考慮了節(jié)點間的鏈路質量和節(jié)點的剩余能量，在保證數據傳輸質量的同時，也保證了網絡的整體性。以圖3為例，假設一個數據包的能耗E為1，ETX值和剩余能量如圖所示。經典MORE協議，將選擇節(jié)點B作為下一跳，那將導致節(jié)點B因能量耗盡而死亡。而根據式(8)計算得ELTA≈3.57，ELTB≈1.67，改進MORE協議將選擇節(jié)點A進行轉發(fā)。所以，以ELT為路由測度，考慮節(jié)點的剩余能量，減少剩余能量較少節(jié)點的數據轉發(fā)次數，以防止其因能量耗盡而過早死亡，均衡節(jié)點間傳輸數據的能量消耗，延長網絡的生存時間。

圖3 下一跳路由選擇示意圖

(3)提高網絡吞吐量。

經典MORE協議，以節(jié)點間的鏈路質量作為路由測度，在選擇轉發(fā)節(jié)點時，將一直選擇鏈路質量較好的節(jié)點轉發(fā)數據包，導致這些節(jié)點因為能量耗盡而過早死亡，影響了網絡整體性以及吞吐量。改進MORE協議，以鏈路質量和節(jié)點的剩余能量作為路由測度，均衡了節(jié)點能量消耗，延長了鏈路質量較好的節(jié)點的生存時間，保證了網絡的整體性，也提高了在整個網絡生存周期中的網絡吞吐量。

3 仿真結果分析

采用NS2(NetworkSimulatorVerson2)軟件完成仿真實驗，將改進的MORE協議與經典MORE協議進行比較。具體的仿真參數為：網絡拓撲大小為500m*500m；節(jié)點數目為50個，初始能量為10J；節(jié)點傳輸距離為100m；網絡編碼數據包大小為1 400B。

3.1 評價指標

在路由度量的設計上，綜合了鏈路質量和節(jié)點剩余能量。為了進行有效的對比，設計了以下指標：

(1)節(jié)點剩余能量方差：每經過一段時間，統(tǒng)計各節(jié)點的剩余能量，并計算所有節(jié)點剩余能量的平均值，計算所有節(jié)點與該平均值之差的平方和。

(2)網絡節(jié)點存活數：每經過一段時間，統(tǒng)計網絡中節(jié)點剩余能量還能支撐節(jié)點工作的節(jié)點個數。

(3)網絡吞吐量：在MORE協議中，傳輸吞吐量定義為數據塊的大小(一個數據塊所包含的個數)除以數據塊的傳輸時間(即從源節(jié)點開始發(fā)送當前數據塊到源節(jié)點收到來自目的節(jié)點的ACK確認信息為止)。從這里可以看出，傳輸吞吐量是由每秒發(fā)送多少個數據包為單位的，即Packets/s。設傳輸吞吐量為100 Packets/s，換算成常用單位bps，換算關系式如式(9)所示：

100 Packets/s=100*1 400*8/1 024= 1 093.75kbps

(9)

3.2 實驗結果

3.2.1 節(jié)點剩余能量方差

由圖4可以看出，0～20 s內，改進MORE協議和經典MORE協議的節(jié)點剩余能量方差相差無幾,但在20 s之后，節(jié)點的剩余能量方差出現了分歧。由于經典MORE協議不考慮節(jié)點的能量消耗，優(yōu)先選擇鏈路質量較好的節(jié)點進行轉發(fā)，導致部分節(jié)點的能耗較大，所有節(jié)點的剩余能量方差較大。而改進MORE協議，在路由度量上，考慮節(jié)點的剩余能量，在選擇候選節(jié)點時，分散了節(jié)點的能量消耗，從而均衡了網絡的能量消耗。

圖4 節(jié)點剩余能量方差

3.2.2 網絡節(jié)點存活數

圖5給出了經典MORE協議和改進MORE協議關于網絡節(jié)點存活數的對比情況。在0～20 s內，兩種協議的網絡節(jié)點死亡數目都為0。之后，經典MORE協議下的節(jié)點開始因為能量耗盡而不斷死亡；改進MORE協議下節(jié)點也出現死亡，但相比較而言，出現的時間晚一些。在30～100 s之間，經典MORE協議下節(jié)點的存活數目都小于改進MORE協議下的。特別是在100 s時，經典MORE協議下的節(jié)點已經全部死亡；而改進MORE協議下還有少量節(jié)點存活，還能完成少部分的數據傳輸工作。綜上所述，改進MORE協議能夠延長網絡生命周期。

圖5 網絡節(jié)點存活數

3.2.3 網絡吞吐量

由圖6可以看出，在30 s之前，兩種協議的吞吐量大致相當。而在30 s，根據圖5，經典MORE協議下部分節(jié)點已經因為能量耗盡而死亡，所以吞吐量有所降低。而改進MORE協議考慮了節(jié)點的剩余能量，在選擇轉發(fā)節(jié)點時，會舍棄部分能量較低的節(jié)點作為轉發(fā)節(jié)點，使得整個網絡中節(jié)點的能量消耗較為平均，節(jié)點不會出現像經典MORE協議中，節(jié)點間鏈路質量較好，卻過早因能量耗盡而退出網絡的情況。但是即便如此，畢竟節(jié)點的能量有限，還是會有節(jié)點因能量耗盡而退出網絡，那么網絡的整體性能也勢必會降低。

圖6 吞吐量

4 結束語

經典MORE協議，率先將網絡編碼引入到機會路由中，進一步提高了網絡吞吐量，但是在選擇候選轉發(fā)節(jié)點時，僅考慮節(jié)點間的鏈路質量，使得部分節(jié)點因為能量耗盡而過早地退出網絡。針對這一突出問題，提出了以ELT為路由度量選擇候選轉發(fā)節(jié)點集的標準，并設計了基于新路由度量的候選節(jié)點選擇策略，提出了改進MORE協議。通過分析以及仿真結果表明，改進MORE協議在選擇候選轉發(fā)節(jié)點時，同等條件下，會舍棄能量較低的節(jié)點，均衡能量消耗，保證節(jié)點的存活率，提高網絡的完整性，延長網絡的生存周期。在今后的研究中，將針對數據傳輸時延進行優(yōu)化，提高數據傳輸的效率。

[1] 崔 莉,鞠海玲,苗 勇,等.無線傳感器網絡研究進展[J].計算機研究與發(fā)展,2005,42(1):163-174.

[2] Biswas S,Morris R.Opportunistic routing in multihop wireless networks[J].ACM SIGCOMM Computer Communication Review,2004,34(1):69-74.

[3] Rozner E,Seshadri J,Mehta Y,et al.SOAR:simple opportunistic adaptive routing protocol for wireless mesh networks[J].IEEE Transactions on Mobile Computing,2009,8(12):1622-1635.

[4] Zeng K,Lou W,Zhai H.Capacity of opportunistic routing in multi-rate and multi-hop wireless networks[J].IEEE Transactions on Wireless Communications,2008,7(12):5118-5128.

[5] Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[C]//Proceedings of the ACM SIGCOMM 2007.New York:ACM Press,2007:169-180.

[6] Yan Y,Zhang B,Mouftah H T,et al.Practical coding-aware mechanism for opportunistic routing in wireless mesh networks[C]//IEEE international conference on communications.[s.l.]:IEEE,2008:2871-2876.

[7] Hu Q,Zheng J.CoAOR:an efficient network coding aware opportunistic routing mechanism for wireless mesh networks[C]//IEEE GLOBECOM workshops.[s.l.]:IEEE,2013:4578-4583.

[8] Mao Xufei,Xu Xiaohua,Tang Shaojie,et al.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1934-1942．

[9] Sharma M,Singh Y.Middle position dynamic energy opportunistic routing for wireless sensor networks[C]//International conference on advances in computing,communications and informatics.[s.l.]:IEEE,2015.

[10] Zorzi M,Rao R R.Geographic random forwarding (GeRaF) for ad hoc and sensor networks:energy and latency performance[J].IEEE Transactions on Mobile Computing,2003,2(4):349-365.

[11] Jing Z,Chen D,Nguyen H V,et al.Cross-layer aided energy-efficient opportunistic routing in ad hoc networks[J].IEEE Transactions on Communications,2014,62(2):522-535.

[12] Zhao Z,Rosario D,Braun T,et al.Topology and link quality-aware geographical opportunistic routing in wireless ad-hoc networks[C]//International wireless communications and mobile computing conference.[s.l.]:[s.n.],2013:1522-1527.

[13] Liu S,Sha M,Huang L.ORAS:opportunistic routing with asynchronous sleep in wireless sensor networks[C]//2010 2nd international conference on future computer and communication.Hefei,China:ACM,2012:234-248.

[14] 胡海峰,楊 震.無線傳感器網絡中基于協同的機會路由[J].通信學報,2009,30(8):116-123.

[15] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks[C]//Proceedings of the 33rd IEEE Hawaii international conference on system sciences.Maui:IEEE Computer Society,2000:233-243.

[16] Couto D S J D,Aguayo D,Bicket J,et al.A high-throughput path metric for multi-hop wireless routing[J].Wireless Networks,2003,11(4):419-434.

Opportunistic Routing Algorithm Based on Energy Balance in Wireless Sensor Network

WANG Lei1,2，WANG Jun1,2，ZHU Zhi-wei1,2，WU Han1,2

(1.Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education,NJUPT,Nanjing 210003,China;2.Jiangsu Key Lab of Wireless Communication of NJUPT,Nanjing 210003,China)

Opportunistic routing achieves high throughput in the face of lossy wireless links.The current opportunistic routing protocol,MORE,is the first opportunistic routing work to adopt network coding,but in the selection of candidate forward node set,it only considers the quality of the link between nodes,which leads to premature dead for some nodes because of energy depletion,affecting the integrity of wireless sensor networks.Aiming at this outstanding issue,an improved routing protocol based on MORE is proposed,which balances energy consumption of wireless sensor nodes.According to transmission mechanism of opportunistic routing,considering the expected transmission count (ETX) and residual energy (RE),a new routing metric expected life time (ELT) and a selection strategy of candidate forward node set based on it is proposed.Finally,simulations are performed by NS2.The results show that in the basis of taking the residual energy into account,the improved MORE protocol not only ensures the reliability of data transmission,but also balances the energy consumption of nodes,improving survival of nodes and prolonging the network life cycle.

opportunistic routing;expected transmission count;residual energy;expected lifetime

2016-06-17

2016-09-21

時間：2017-03-07

國家自然科學基金資助項目(61401234)；江蘇高校優(yōu)勢學科工程資助項目；江蘇省政府留學獎學金

王 雷(1990-)，男，碩士研究生，研究方向為基于網絡編碼的數據收集技術；王 珺，博士，副教授，研究方向為下一代通信網絡技術。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.080.html

TP301.6

A

1673-629X(2017)04-0034-05

10.3969/j.issn.1673-629X.2017.04.008