無線傳感器網絡中利用隨機網絡編碼的低能耗可靠機會

徐 驥,朱藝華,田賢忠,池凱凱

(浙江工業大學計算機科學與技術學院,浙江杭州 310023)

?

無線傳感器網絡中利用隨機網絡編碼的低能耗可靠機會

徐 驥,朱藝華,田賢忠,池凱凱

(浙江工業大學計算機科學與技術學院,浙江杭州 310023)

無線傳感器網絡中節點大多采用電池供電，讓節點以低能耗將采集的數據傳遞到信宿，對無線傳感器網絡有效運行極為重要.該文提出了能量有效的可靠機會路由EROR(Energy-efficient Reliable Opportunistic Routing)，它利用結合節點剩余能量和鏈路上收發雙方的總能耗的轉發代價，選擇轉發節點集合(簡稱“轉發集”)、主轉發節點和協助轉發節點，讓節點調節發射功率并利用隨機線性編碼把數據包分片編碼發送到轉發集，進而以多跳方式把數據可靠低能耗地傳遞到信宿.仿真結果表明：在網絡生存時間和能耗方面，EROR比已有路由策略CodePower更優.

無線傳感器網絡;機會路由;節能;功率控制;網絡編碼

1 引言

傳統的路由協議需要節點在發送數據之前建立一條或多條端到端的數據傳輸路徑，以將數據逐跳發送到目的節點.為了提高可靠性，路徑上節點通常采用重傳和確認機制傳遞數據.在通信鏈路質量比較差的情況下，節點需要重傳多次才能將數據包發送給下一跳節點.頻繁的重傳會導致節點過多消耗能量.而且，節點重傳需要競爭信道，從而導致帶寬利用率不高[1,2].

無線信道的廣播特性可以在某一程度上克服上述不足.當一個節點發送數據包時，其鄰居節點可以監聽到該數據包.機會路由[3]利用了無線信道的這一廣播特性，它需要在正確接收數據包的節點中選擇到目地節點的一個節點來轉發數據包，從而提高轉發數據包的可靠性以提高吞吐率.如圖1，設源節點S到目地節點D存在一條路徑S→1→2→3→4→D，其中，S到節點1，2，3的數據包傳輸成功率分別為0.9，0.7，0.5，且節點2和3到D的數據包傳輸成功率分別為0.6和0.85.按照傳統路由，節點S將數據包發送到節點1，且在節點1未能成功收到數據包的條件下，需要重傳.由于無線鏈路的廣播特性，在節點S向節點1發送數據包時，節點2和3分別以0.7和0.5的概率監聽數據包.也就是說，在節點1收到數據包的同時，節點2和(或)節點3可能均收到該數據包.傳統路由忽視了這一現象，只是簡單地逐跳轉發：把數據包從節點1轉發到節點2，再轉發到節點3，最終到達目的節點D.但機會路由并非這樣做，而是直接讓節點3把數據包發送給其下游節點甚至于目的節點D.由這個例子可見，機會路由可以減小數據包的傳遞次數.

在無線傳感器網絡中，節點通常由能量有限的電池供電，因此，機會路由需要考慮節點的能耗.若節點選擇較大的發生功率，那么數據包能夠被更遠更多的節點監聽到，但會增加網絡的能耗開銷；若減少發送的功率，鏈路質量越差，數據包可能要經過更多節點轉發才能到達Sink，可靠性降低.因此在無線傳感器網絡中，我們需要設計一個能量高效的可靠機會路由，此乃本文的研究動機.本文的貢獻如下：

(1)給出了結合節點剩余能量和收發雙方能耗的數據包轉發代價計算公式，設計了能夠讓節點在數據傳輸過程中動態地選擇轉發節點集合(下稱“轉發集”)、發送功率和轉發代價的算法.

(2)提出了基于編碼的低能耗機會路由策略EROR(Energy-efficient Reliable Opportunistic Routing).EROR利用隨機線性編碼，讓節點將編碼包發送到下游節點，以提高傳輸可靠性.在數據轉發過程中，EROR可以讓節點根據轉發代價在轉發集中動態選擇一個主轉發節點，使數據傳遞到Sink節點.此外，EROR允許主轉發節點選取若干協助轉發節點，并且每個協助轉發節點可以根據其所在轉發集的代價、鏈路質量和緩存的編碼包個數來確定自己需要發送的最大編碼包個數，以降低和平衡各轉發節點的消耗，從而延長網絡的生存時間.

2 相關工作

目前，已經有一些機會路由在選擇轉發節點時考慮了能耗問題，但這些研究還存在不足.在文獻[4]中作者提出的EEOR每個節點可在調發送能量和不可調發送能量模型下計算路由代價和選擇最優轉發節點集合，從而使得數據通過這些節點轉發到Sink時總能耗最小.EEOR中節點根據優先級轉發數據，若高優先級的轉發了數據，那么低優先級的節點需要丟棄監聽到的數據包，造成節點能量的浪費.AsOR[5]設計了分段路由的方法，通過選擇最優的段內節點個數使得平均能耗最小化，但AsOR是從全局角度優化能耗，是集中式的路由算.一些研究將網絡編碼用于路由，如基于網絡編碼的無重傳路由[6]和編碼增益感知的路由[7].MORE[8]將機會路由和流內隨機線性編碼相結合，解決了節點轉發調度困難的問題.CodeOR[9]用滑動窗口提高MORE數據傳輸的效率，但CodeOR沒有考慮能耗.CodePower[10]通過分布式算法選擇了最優的發送功率和對應的最優轉發節點，將結合流內隨機線性編碼的機會路由用于無線傳感器網絡，但CodePower不能保證數據可靠傳遞，節點只轉發確定數量的編碼包，不能保證數據可靠傳遞.本文提出的EROR通過選擇主轉發節點和協助轉發節點來解決了上述能量浪費和可靠性問題.文獻[11]提出基于部分網絡編碼的機會路由.文獻[12]提出分布式聯合候選節點選擇和速率分配的多流機會路由算法.文獻[13]結合端到端的可靠性與能耗，針對自組織網絡，提出兩個路由策略：RMECR(Reliable Minimum Energy Cost Routing)和RMER(Reliable Minimum Energy Routing).前者的鏈路權重考慮了鏈路兩端節點的收發能耗和剩余能量，后者的鏈路權重僅考慮鏈路兩端節點的收發能耗；兩者均利用Dijkstra算法找到能耗最小的路徑.文獻[13]的作者指出：上述兩種路由需要網絡中每個節點知道整個網絡的拓撲結構，可以采用諸如洪泛(flooding)等方法獲得網絡拓撲結構信息；兩者在采用Dijkstra方法求最小能耗時，均需要采用集中計算.事實上，文獻[13]提出的RMECR和RMER路由均不適用無線傳感器網絡，其理由如下所述:(1)當代無線傳感器網絡大多基于IEEE 802.15.4標準，節點的處理能力、無線電覆蓋范圍、可以通信的數據包長度、內存空間等均為捉襟見肘.IEEE 802.15.4標準針對低數據率、低功耗的無線個域網絡，其物理層可以攜帶的來自數據鏈路層數據幀的最大長度只有127字節[14].目前，CrossBow公司生產的TelosB傳感器節點，其射頻收發器兼容IEEE 802.15.4標準，通信距離僅為數十米，而且只有10kB內存；(2)在低功耗的無線傳感器網絡中，節點之間的鏈路時斷時續，這會導致采用集中方式計算出來的最優路徑在傳遞數據包時可能因某個鏈路中斷而失效，而且存在最優路徑未使用就失效的可能，這是因為最優路徑在計算出來之后，計算路徑的節點需要發送數據包通知各相關節點，而且包含該通知的數據包在發送過程中可能丟失.本文提出的EROR路由方案，可以克服上述缺陷.本文的EROR的主要異同之處在于：EROR采用分布式算法，節點在選路時只需獲取鄰居的狀態信息，無須知道整個網絡的拓撲結構，也不需要計算從信源到信宿的路徑.而且，EROR適用于資源極度受限的、鏈路時斷時續的、基于IEEE 802.15.4標準的無線傳感器網絡.

3 基于編碼的低能耗可靠機會路由

3.1 EROR的轉發策略

與MORE[8]類似，本文提出的EROR協議利用流內隨機線性網絡編碼來傳遞數據，關鍵在于：利用轉發代價確定轉發節點集合(簡稱“轉發集”).我們將在下一節給出轉發代價的定義.

轉發集Fs中的節點，每偵聽到一個來自節點s的編碼包，就檢查收到的編碼包與緩存的編碼包是否線性無關.若是，則放入緩存，否則，棄之.當一個節點緩存的編碼包的個數達到m時，該節點就向節點s回復一個ACK，使節點s停止生成和發送編碼包.

我們稱轉發集中第一個收足m個編碼包的節點為“主轉發節點”.設節點u是Fs的主轉發節點.由于節點u的m個編碼包系數形成一個滿秩矩陣，它可以通過解碼得到節點s發送的原始數據.此時，Fs中其余節點收到的編碼包個數不足m，雖然這些節點不能通過解碼獲得原始數據，但其收到的編碼包或許對下游節點的解碼有用.因此，下述方案可以在Fs中篩選一些節點(稱為“協助轉發節點”)讓其轉發所收到的編碼包給下游節點.

(1)若f∈Fu，則f偵聽Fs中的節點廣播的編碼包；

(3)若f?Fu∪Fs，則不偵聽也不轉發數據.

主轉發節點u和協助轉發節點將各自緩存的編碼包進行隨機編碼不斷產生新的編碼包，再把編碼包廣播給Fu內的下游節點，直到收到Fu內主轉發節點的ACK為止.在圖2中，v是Fu的主轉發節點.節點v采用廣播的形式發送ACK，使得Fs中節點收到確認后就停止發送編碼包.

上述過程逐步推進，直到Sink收到m個線性無關的編碼包，進而解出源數據.之后，Sink發送ACK給其上游轉發節點，使其停止發送編碼包.

3.2 EROR的數據轉發代價

由上節可知，EROR協議是根據轉發代價選擇轉發節點的.因此，在設計轉發代價時，需要考慮以下因素：

(1)轉發代價應能夠根據節點的能量狀態和鏈路質量狀態來影響數據的轉發路徑.

(2)由于節點的發射功率影響著節點的鄰居集合，高發射功率使節點的鄰居多，但耗能大，因此，轉發代價需要反映節點的發射功率.

(3)為了使網絡有更長的工作時間，轉發代價應該分擔給剩余能量小的節點更小的數據轉發任務.

(1)

我們取

(2)

接下來，我們確定式(2)右邊兩個代價的表達式.本文采用文獻[13]的能耗模型.用A表示節點計算和處理調制數據的平均功率，用B表示接收方接收數據的平均功率.于是，在功率ε下發送l比特數據消耗的能量Etx(l,ε)和接收l比特數據消耗的能量Erx(l)可以表示為[13]：

(3)

(4)

其中0<β<1是放大器的效率，R是物理層的速率(單位：bps).

我們考慮瑞利衰落無線信道，節點u以功率ε發送信號給節點v的誤碼概率為[13]

(5)

(6)

式中，g1是與傳輸和接收天線有關的常數，εN是噪聲和干擾的功率，η為路徑衰減指數，du,v為節點u和v之間的距離.因而，

(7)

(8)

其中，REu和REv分別為節點u和v的剩余能量.

表1 集合F的主轉發節點及對應概率

(9)

上式中，右邊分式是在集合F中至少有一個節點接收到節點u所廣播的數據包這一條件下，節點fi成為主轉發節點的概率.

3.3 確定轉發集、發射功率和轉發代價的算法及其復雜度

3.4 轉發數據量的確定

考慮到協助轉發節點需要協助主轉發節點發送編碼包給下游轉發集，為了節省能量，我們需要限制協助轉發節點發送的編碼包的最大個數.假設節點f為主轉發節點u的一個協助轉發節點.我們引入符號

(10)

(11)

其中Γf是節點f緩存的編碼包的個數.每個協助轉發節點一旦發送的數據包個數達到Af或者收到確認包時，就停止發送.

3.5 主轉發節點的選擇

轉發集合中的節點在偵聽數據時，可能在同一時刻有多個節點緩存的編碼包個數同達到m.這時，如果這些節點同時發送確認包，可能會導致確認包的碰撞，也可能產生多個主轉發節點.為了避免這種情況發生，在節點f收齊m個編碼包時，我們讓節點延緩Tf符號周期(Symbol Period)發送確認包，而且，在延緩的Tf符號周期內，若該節點監聽到其它節點已經發送了確認包，則它取消發送確認包(即放棄成為主轉發節點).考慮到IEEE 802.15.4標準要求發送確認包的延遲時間在[12,32]這個區間內，我們定義：

(12)

4 仿真分析

由于節點可以調整發射功率，因此若節點增大發送功率，那么可能有更多節點能夠收到數據包，這樣節點的鄰居會隨功率增大而增多.在仿真中，我們使用與文獻[13]類似的方法確定式(6)中的g1/εN：我們取g1/εN的值滿足節點u以最大功率發送長度為800比特的數據包給相距50米遠的節點v收到的概率為0.5.利用文獻[13]的方法，可得：g1/εN=2058314.我們參考Telos節點的參數[16]：接收功率為38mW，發送功率為35mW，節點活躍時總功率為41mW.因此，我們取式(4)中B=38mW，發送功率E中最大值為35mW，式(3)中A=5mW.其它仿真參數如表2所示.我們采用C++程序設計語言設計仿真程序.

表2 其它仿真參數

考慮到RMECR和RMER[13]不適合于無線傳感器網絡(見第2節)，而CodePower與EROR均屬于機會路由，采用類似的機制，我們對EROR和CodePower的性能進行對比.由于EROR保證每跳可靠傳輸，源節點發送的數據包都到達sink節點，因此，以下僅對兩者的網絡生存時間和能耗進行對比.網絡生存時間定義為從發送第一個數據包開始到出現第一個剩余能量為0的節點為止這段時間，并且采用源節點發送數據包個數進行度量.平均能耗定義為網絡生存時間內平均每個到達Sink的數據包消耗的能量.仿真區域大小為1000×1000m2，Sink節點位于區域左下角，在區域中隨機產生節點.Sink的代價為0，其余節點初始代價取為無窮大.我們假設Sink節點能耗不受限制并且有足夠的計算能力，因而忽略Sink的接收能耗.圖3和圖4是不同網絡規模下1000次仿真運行的平均結果.由圖3可見：本文提出的EROR的生存時間大于CodePower.這是因為EROR在選擇轉發節點時，考慮了節點的剩余能量.剩余能量少的節點代價比較大，EROR避免將這些節點作為轉發節點，而是選擇其它能量比較充足的節點轉發數據包.然而，CodePower在計算代價時未能考慮節點的剩余能量，導致能耗不均.從圖3(a)可以看出：兩者的生存時間都隨著網絡規模的增大呈先增大后減小的趨勢.這是因為網絡中節點密度增大，每個節點的鄰居節點個數隨著增加，使得一個節點有更多機會從鄰居中選擇代價更小的節點作為轉發節點，從而使得生存時間增大.但當節點個數進一步增大時，主轉發節點的轉發集也隨著增大，即參與轉發數據包的節點個數增大，相互轉發的數據包增多，從而引起生存時間減小.從圖3(b)可以看出，網絡生存時間都隨分片增多而減小，這是因為分片數越多，節點轉發的數據包個數就越多，耗能越大.

由圖4可見：EROR的平均能耗低于CodePower，且兩者的能耗均隨著節點數和分片數的增大而增大.但隨著節點數的增大，EROR的能耗比CodePower增大緩慢(見圖4(a)).這是因為EROR的主轉發節點使得編碼包逐跳可靠傳輸，而且，它通過選擇適當的協助轉發節點來協同主轉發節點轉發部分編碼包.然而，CodePower采用端到端確認以保證可靠傳輸.因此，隨著網絡規模的擴大，CodePower的數據包可能因中途夭折而重傳，這時夭折的數據包可能走過了很多跳，從而導致平均能耗的上升.從圖4(b)可以看出，平均能耗都隨分片增多而增加，這與直觀是吻合的.

5 總結

本文提出了一種基于隨機線性編碼并且發送功率可調的低能耗機會路由EROR.這種路由策略利用隨機線性網絡編碼，并利用結合節點剩余能量和鏈路上收發雙方總能耗的轉發代價，選擇主轉發節點、協助轉發節點和轉發集，使數據可靠地從信源傳遞到信宿，降低和均衡了節點的能耗，在保證可靠性的同時，延長了網絡生存時間.

[1]Poonguzharselvi B,Vetriselvi V.Survey on routing algorithms in opportunistic networks[A].Proceedings of the 2013 International Conference on Computer Communication and Informatics(ICCCI)[C].Coimbatore:IEEE,2013.1-5.

[2]Zhang Z,Krishnan R.An overview of opportunistic routing in mobile ad hoc networks[A].Proceedings of the 2013-2013 IEEE Military Communications Conference[C].San Diego:IEEE,2013.119-124.

[3]Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM SIGCOMM Computer Communication Review,2005,35(4):133-144.

[4]Mao Xufei,Tang Shaojie,Xu Xiahua,Li Xiangyang,Ma Huadong.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1934-1942.

[5]Wei Chen,Zhi Chen,Fan Pingyi,et al.AsOR:an energy efficient multi-hop opportunistic routing protocol for wireless sensor networks over Rayleigh fading channels[J].IEEE Transactions on Wireless Communications,2009,8(5):2452-2463.

[6]盧文偉，朱藝華，陳貴海.無線傳感器網絡中基于線性網絡編碼的節能路由算法[J].電子學報，2010,38(10):2309-2314.

Lu Wenwei,Zhu Yihua,Chen Guihai.Energy-efficient routing algorithms based on linear network coding in wireless sensor networks[J].Acta Electronica Sinaca,2010,38(10):2309-2314.(in Chinese)

[7]田賢忠，朱藝華，繆得志.無線網絡編碼增益感知的低時延路由協議[J].電子學報，2013，41(4):652-658.

Tian Xianzhong,Zhu Yihua,Miao Dezhi.Wireless network coding gain aware routing protocol with low delay[J].Acta Electronica Sinaca,2013,41(4):652-658.(in Chinese)

[8]Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[J].ACM SIGCOMM Computer Communication Review,2007,37(4):169-180.

[9]Lin Y,Li B,Liang B.CodOR:opportunistic routing in wireless mesh networks with segmented network coding[A].Proceedings of the 2008 IEEE International Conference on Network Protocols(ICNP 2008)[C].Orlando:IEEE,2008.13-22.

[10]Tong J,Qian D,Du Z,et al.Energy-efficient coded routing with selective transmission power for wireless sensor networks[A].Proceedings of the 2010 IEEE 72nd Vehicular Technology Conference Fall(VTC 2010-Fall)[C].Ottawa:IEEE,2010.1-5.

[11]王曉東，霍廣城，孫海燕，孟祥旭，孫言強.移動自組網中基于部分網絡編碼的機會主義路由[J].電子學報，2010,38(8):1736-1740.

Wang Xiaodong,Huo Guangcheng,Sun Haiyan,Meng Xiangxu,Sun Yangqiang.An opportunistic routing for MANET based on partial network coding[J].Acta Electronica Sinaca,2010,38(8):1736-1740.(in Chinese)

[12]何施茗，張大方，謝鯤，張繼，喬宏.多并發流無線網狀網中的機會路由算法[J].電子學報，2014,42(5):1004-1008.

He Shiming,Zhang Dafang,Xie Kun,Zhang Ji,Qiao Hong.Opportunistic routing for multi-flow in wireless mesh networks[J].Acta Electronica Sinaca,2014,42(5):1004-1008.(in Chinese)

[13]Vazifehdan J,Prasad R V,Niemegeers I.Energy-efficient reliable routing considering residual energy in wireless ad hoc networks[J].IEEE Transactions on Mobile Computing,2013,13(2):434-447.

[14]IEEE Computer Society.IEEE 802.15.4 Standard for Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specifications for Low-Rate Wireless Personal Area Networks(WPANs)[S].2011.

[15]Ho T,M′edard M,Koetter R,Karger D,Effros M,Shi J,Leong B.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[16]Polastre J,Szewczyk R,Culler D.Telos:enabling ultra-low power wireless research[A].Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks[C].IEEE,2005.364-369.

徐 驥 男，1990年生于浙江紹興.碩士研究生,研究方向為無線傳感器網絡.

朱藝華(通信作者) 男，1961年生于浙江玉環，博士，教授，研究方向為無線網絡、物聯網、網絡編碼等.

E-mailyhzhu@zjut.edu.cn

Energy-Efficient Reliable Opportunistic Routing Applying Random Network Coding for Wireless Sensor Network

XU Ji,ZHU Yi-hua,TIAN Xian-zhong,CHI Kai-kai

(SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou，Zhejiang310023,China)

The nodes in Wireless Sensor Networks(WSNs)are usually powered by battery.It is extremely important to let the nodes deliver data to the destination in an energy-efficient manner such that the WSNs have longer runtime.In this paper,the Energy-efficient Reliable Opportunistic Routing(EROR)is presented.The EROR uses the forwarding cost,which takes into account node’s residual energy and the total energy consumption expended by the nodes over a wireless link;chooses the forwarding set consisting of forwarding nodes(FNs),the main FN,and the assistant FNs;and allows a node to change its transmission power to transmit the encoded packets,which are generated by randomly linear network coding,to the forwarding set such that the data are delivered to the destination in a multi-hop,reliable,and energy-efficient way.Simulation results indicate that the EROR outperforms the existing CodePower routing in terms of network lifetime and energy consumption.

wireless sensor network;opportunistic routing;energy conservation;transmit power control;network coding

2015-02-08;

2015-04-08；責任編輯：諸葉梅

國家自然科學基金重點項目(No.61432015);國家自然科學基金(No.61472367，No.61379124)

TP393

A

0372-2112 (2016)08-1799-07

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.08.004