基于網(wǎng)絡(luò)編碼的無(wú)線傳感器網(wǎng)絡(luò)功率管理*

梁平元，黃光亞，陸 芷，徐 倩

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000)

基于網(wǎng)絡(luò)編碼的無(wú)線傳感器網(wǎng)絡(luò)功率管理*

梁平元，黃光亞，陸 芷，徐 倩

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000)

無(wú)線傳感器網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)采集及其運(yùn)算時(shí)均采用電池驅(qū)動(dòng)，能耗便成了無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)時(shí)最應(yīng)考慮的關(guān)鍵因素.采用網(wǎng)絡(luò)編碼時(shí)，中間節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包是其接收信息的線性組合，傳輸一定大小數(shù)據(jù)包時(shí)最小化數(shù)據(jù)傳輸次數(shù)，傳輸次數(shù)越少，功率消耗也越少.分析了網(wǎng)絡(luò)編碼時(shí)無(wú)線傳感器網(wǎng)絡(luò)傳輸過(guò)程及其節(jié)能的原理，比較了是否采用網(wǎng)絡(luò)編碼的2種無(wú)線傳感器網(wǎng)絡(luò)傳輸方式的能效.結(jié)果表明，采用網(wǎng)絡(luò)編碼技術(shù)，可以有效地減少傳輸總功率，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間.

無(wú)線傳感器網(wǎng)絡(luò);網(wǎng)絡(luò)編碼;功率最小化;能效

然而，由于節(jié)能問(wèn)題同樣是無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)的核心問(wèn)題，所以文中的研究是建立在能效與功率管理的基礎(chǔ)之上的.在不考慮可靠性提高的基礎(chǔ)上，盡可能地節(jié)省無(wú)線傳感器網(wǎng)絡(luò)的能量，減少傳輸功率，并最終達(dá)到延長(zhǎng)整個(gè)無(wú)線傳感器網(wǎng)絡(luò)生存時(shí)間的目的.無(wú)線傳感器網(wǎng)絡(luò)在采用網(wǎng)絡(luò)編碼傳輸時(shí)可以最大化吞吐量，從而導(dǎo)致能量的節(jié)省.同時(shí)比較是否采用網(wǎng)絡(luò)編碼的2種無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸模式的能效，說(shuō)明采用網(wǎng)絡(luò)編碼的優(yōu)勢(shì)所在.實(shí)驗(yàn)結(jié)果表明，網(wǎng)絡(luò)編碼技術(shù)可以有效地減少數(shù)據(jù)的傳輸功率，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間.

1 網(wǎng)絡(luò)編碼及其優(yōu)勢(shì)

圖1 簡(jiǎn)單數(shù)據(jù)交換

網(wǎng)絡(luò)編碼的基本思想可以用圖1表示，節(jié)點(diǎn)A，B和C可以共享無(wú)線傳輸媒介.考慮到節(jié)點(diǎn)A和C有信息要相互交換，信道受限，那么只有1個(gè)節(jié)點(diǎn)能在任何時(shí)候發(fā)送數(shù)據(jù).節(jié)點(diǎn)A發(fā)送數(shù)據(jù)包(p1)到中繼節(jié)點(diǎn)B，節(jié)點(diǎn)B再轉(zhuǎn)發(fā)數(shù)據(jù)包到節(jié)點(diǎn)C.同樣地，節(jié)點(diǎn)C發(fā)送數(shù)據(jù)到節(jié)點(diǎn)B，而節(jié)點(diǎn)B再轉(zhuǎn)發(fā)到節(jié)點(diǎn)A，如圖1a)所示.在沒(méi)采用網(wǎng)絡(luò)編碼(見(jiàn)圖1b))時(shí)，這樣的數(shù)據(jù)交換需要4個(gè)傳輸次數(shù).而當(dāng)采用網(wǎng)絡(luò)編碼時(shí)，可以減少傳輸?shù)拇螖?shù).節(jié)點(diǎn)A和C經(jīng)過(guò)2次連續(xù)地傳輸數(shù)據(jù)包到中間節(jié)點(diǎn)B，而不是直接發(fā)送數(shù)據(jù)包到目的.2個(gè)分別來(lái)自于A和C數(shù)據(jù)包在節(jié)點(diǎn)B進(jìn)行異或運(yùn)算結(jié)合成為1個(gè)數(shù)據(jù)包，而節(jié)點(diǎn)A和C分別都知道它們本身所具有的數(shù)據(jù)包p1和p2，因此，在獲得節(jié)點(diǎn)B廣播的異域編碼后的數(shù)據(jù)后，再次進(jìn)行異或運(yùn)算，就能得到各自所需要的對(duì)方的數(shù)據(jù)包.對(duì)于這種情況總共只需要3次傳輸次數(shù)，比原來(lái)的4次要少1次傳輸.在這種簡(jiǎn)單化的數(shù)據(jù)交換模型中，采用網(wǎng)絡(luò)編碼技術(shù)可以節(jié)省25%的能耗.

圖2 通信網(wǎng)絡(luò)中的多點(diǎn)傳送

關(guān)于節(jié)省能耗的網(wǎng)絡(luò)編碼模型是Ahlswede等在文獻(xiàn)［14］中舉出的蝴蝶狀網(wǎng)絡(luò)結(jié)構(gòu).文獻(xiàn)［14］考慮了一種線性網(wǎng)絡(luò)的多點(diǎn)傳送問(wèn)題，這種蝴蝶形網(wǎng)絡(luò)如圖2，它描述了從1個(gè)源節(jié)點(diǎn)多點(diǎn)傳送到2個(gè)匯聚節(jié)點(diǎn)(或2個(gè)目的地).假定在一個(gè)非循環(huán)網(wǎng)絡(luò)中，從源節(jié)點(diǎn)S多點(diǎn)傳送數(shù)據(jù)比特b1和b2分別到2個(gè)目的節(jié)點(diǎn)Y和Z，如圖2所示，每個(gè)通道可以攜帶b1或b2.圖2a)描繪了用不同的方式來(lái)多點(diǎn)從源節(jié)點(diǎn)S到Y(jié)和Z傳送2個(gè)比特，在這種方式中，由于使用網(wǎng)絡(luò)編碼，所有的9個(gè)通道剛好都傳輸1次.若相同的數(shù)據(jù)通信不經(jīng)網(wǎng)絡(luò)編碼而是進(jìn)接進(jìn)行比特復(fù)制來(lái)獲得，如圖2b)所示，則網(wǎng)絡(luò)至少有1個(gè)通道必須被使用2次，以至總的傳輸次數(shù)至少要達(dá)到10次.因此，網(wǎng)絡(luò)編碼提供了縮小延時(shí)和能耗的潛力，同時(shí)也可以最大化傳輸比特速率.

2 網(wǎng)絡(luò)編碼在環(huán)形與格子網(wǎng)絡(luò)中的應(yīng)用

2.1環(huán)行網(wǎng)絡(luò)

考慮有n個(gè)節(jié)點(diǎn)的環(huán)形網(wǎng)絡(luò)，節(jié)點(diǎn)被等距離部署在一個(gè)圓上，如圖3所示.假設(shè)每個(gè)節(jié)點(diǎn)能成功地廣播信息到它的2個(gè)鄰節(jié)點(diǎn).假定每個(gè)節(jié)點(diǎn)都是源節(jié)點(diǎn)，它們都想把信息廣播到所有的其他n－1個(gè)節(jié)點(diǎn).如文獻(xiàn)［15］中所分析的那樣，如果沒(méi)有網(wǎng)絡(luò)編碼，它就需要(n－2)次傳輸，而當(dāng)使用網(wǎng)絡(luò)編碼時(shí)，它只需要(n－1)/2次，如圖4所示.

圖3 環(huán)形網(wǎng)絡(luò)節(jié)點(diǎn)部署

圖4 不同節(jié)點(diǎn)在環(huán)形網(wǎng)絡(luò)中的傳輸次數(shù)

2.2格子網(wǎng)絡(luò)

考慮1個(gè)有n個(gè)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)，令n=m2.假定每個(gè)節(jié)點(diǎn)都是源節(jié)點(diǎn)，它們都想把信息廣播到所有的其他(n－1)個(gè)節(jié)點(diǎn).節(jié)點(diǎn)被部署在矩形柵格的交叉點(diǎn)上，且每個(gè)節(jié)點(diǎn)均能成功地廣播信息到它的4個(gè)最近的相鄰節(jié)點(diǎn)，如圖5所示.在文獻(xiàn)［16］中，當(dāng)沒(méi)有采用網(wǎng)絡(luò)時(shí)它需要n2/3次傳輸，而采用網(wǎng)絡(luò)編碼后，傳輸次數(shù)會(huì)減到n2/4，如圖6所示.

圖5 格子網(wǎng)絡(luò)節(jié)點(diǎn)部署

圖6 格子網(wǎng)絡(luò)的平均傳輸次數(shù)

3 仿真實(shí)驗(yàn)及其分析

假設(shè)在無(wú)線傳感網(wǎng)絡(luò)部署區(qū)(200 m×200 m)無(wú)線傳播的平均功率模型為

表1 具體參數(shù)設(shè)置

其中:Ntx與Nrx分別為每秒鐘發(fā)送和接收的平均次數(shù);Ptx和Prx分別為發(fā)送和接收的功率消耗;Pout是無(wú)線發(fā)送傳輸功率;Tst為無(wú)線收發(fā)器起始時(shí)間，也就是實(shí)際上的數(shù)據(jù)發(fā)送與接收時(shí)間;Tst=L/R，L是包的比特長(zhǎng)度，R為比特率.參數(shù)大小設(shè)置如表1所示.

對(duì)于環(huán)形網(wǎng)絡(luò)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的總能量消耗如圖7所示，而格子網(wǎng)絡(luò)中所有節(jié)點(diǎn)的總能量消耗如圖8所示.從圖7，8可以看出，當(dāng)采用網(wǎng)絡(luò)編碼時(shí)，網(wǎng)絡(luò)使用功率的大小要比沒(méi)有網(wǎng)絡(luò)編碼時(shí)小.

圖7 環(huán)形網(wǎng)絡(luò)的平均消耗功率

圖8 格子網(wǎng)絡(luò)中節(jié)點(diǎn)的總能耗

無(wú)線傳感器網(wǎng)絡(luò)最重要的性能是網(wǎng)絡(luò)生存時(shí)間，即網(wǎng)絡(luò)中存活節(jié)點(diǎn)的百分比.網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有初始能量E0，對(duì)于1個(gè)給定的數(shù)據(jù)率Rb來(lái)說(shuō)，每傳輸1個(gè)數(shù)據(jù)包的能量為L(zhǎng)/Rb.因此，傳輸1個(gè)數(shù)據(jù)包總的能量消耗為

由于節(jié)點(diǎn)以平均速率發(fā)送數(shù)據(jù)包，其每秒鐘所花費(fèi)的平均功率為Pt，因此最后電池消耗后總的時(shí)間為

其中:τ是節(jié)點(diǎn)的生存時(shí)間;Rb為數(shù)據(jù)速率;L為數(shù)據(jù)包的長(zhǎng)度，實(shí)驗(yàn)中設(shè)為1 000 bits;λt為數(shù)據(jù)包到達(dá)率，設(shè)定為每秒到達(dá)0.5 wh數(shù)據(jù)包;Pt為發(fā)送功率，當(dāng)增加節(jié)點(diǎn)的發(fā)送功率，節(jié)點(diǎn)將消耗更多的能量，同時(shí)節(jié)點(diǎn)的生存時(shí)間也將減少.然而，若節(jié)點(diǎn)參與網(wǎng)絡(luò)編碼，則節(jié)點(diǎn)在編碼后的剩余功率將比沒(méi)有參與網(wǎng)絡(luò)編碼的節(jié)點(diǎn)要多.無(wú)論哪時(shí)采用網(wǎng)絡(luò)編碼，無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗都要減少，所以它能改進(jìn)相同節(jié)點(diǎn)時(shí)的網(wǎng)絡(luò)生存時(shí)間，如圖9所示.

圖9 網(wǎng)絡(luò)生存時(shí)間比較圖

4 結(jié)語(yǔ)

分析了采用網(wǎng)絡(luò)編碼的無(wú)線傳感器網(wǎng)絡(luò)中的最小能量消耗的情況，比較了環(huán)形和格子網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)是否采用網(wǎng)絡(luò)編碼的能量消耗情況.實(shí)驗(yàn)證明:采用網(wǎng)絡(luò)編碼在能耗方面的節(jié)省，其主要原因是采用網(wǎng)絡(luò)編碼時(shí)可以減少節(jié)點(diǎn)之間的數(shù)據(jù)傳輸次數(shù).網(wǎng)絡(luò)編碼應(yīng)用在無(wú)線傳感器網(wǎng)絡(luò)時(shí)，具有節(jié)省能量的潛力，這使無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間得以延長(zhǎng).

［1］ CHEKURI C，F(xiàn)RAGOULI C，SOLJANIN E.On Average Throughput and Alphabet Size in Network Coding［J］.IEEE Transactions on Information Theory，2006，52(6):2 410-2 424.

［2］ SENGUPTA S，RAYANCHU S，BANERJEE S.Network Coding-Aware Routing in Wireless Networks［J］.IEEE/ACM Transactions on networking，2010，18(4):1 158-1 170.

［3］ KIM Y，D E VECIANA.Is Rate Adaptation Beneficial for Inter-Session Network Coding?［J］.IEEE Journal on Selected Areas in Communications，2009，27(5):635-646.

［4］ LI Zong-peng，LI Bao-chun，LAP CHI LAU.A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks［J］.IEEE Transactions on Information Theory，2009，55(3):1 016-1 026.

［5］ PRICE J，JAVIDI T.Network Coding Games with Unicast Flows［J］.IEEE Journal on Selected Areas in Communications，2008，26(7):1 302-1 316.

［6］ CHEN Ying-da，KISHORE S.On the Tradeoffs of Implementing Randomized Network Coding in Multicast Networks［J］.IEEE Transactions on Communications，2010，58(7):2 107-2 115.

［7］ NOGUCHI T，MATSUDA T，YAMAMOTO M.Performance Evaluation of New Multicast Architecture with Network Coding［J］.IEICE Trans.Commun，2003，E86-B(6):1 788-1 795.

［8］ ZHANG Xin-yu，LI Bao-chun.Optimized Multipath Network Coding in Lossy Wireless Networks［J］.IEEE Journal on Selected Areas in Communications 2009，27(5):622-634.

［9］ DING Zhi-guo，KIN K LEUNG，DENNIS L，et al.On the Study of Network Coding with Diversity［J］.IEEE Transactions on Wireless Communications，2009，8(3):1 247-1 259.

［10］ AHLSWEDE R，CAI N，S.-Y.R.LI，et al.Network Information flow［J］.IEEE Transactions on Information Theory，2000，46 (4):1 204-1 216.

［11］ DULMAN S，NIEBERG T，WU J，et al.Trade-off Between Traffic Overhead and Reliability Multipath Routing for Wireless Sensor Networks［C］//Proc.of Wireless Communications and Networking.USA:New Orleans LA，2003:1 918-1 922.

［12］ OSAMEH M，AL-KOFAHI，KAMAL A E.Network Coding-Based Protection of Many-to-One Wireless Flows［J］.IEEE Journal on Selected Areas in Communication，2009，27(5):797-813.

［13］ HAN T S.Multicasting Multiple Correlated Sources to Multiple Sinks Over a Noisy Channel Network［J］.IEEE Transactions on Information Theory，2011，57(1):4-13.

［14］ AHLSWEDE R，CAI N，LI S R，et al.YEUNG.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46(4):1 204-1 216.

［15］ WIDMER J，F(xiàn)RAGOULI C，LE BOUDEC J Y.Low-Complexity Energy Efficient Broadcasting in Wireless Ad-Hoc Networks Using Network Coding［C］//First Workshop on Network Coding，2005:1-6.

(責(zé)任編輯 陳炳權(quán))

Power Management of Wireless Sensor Network Based on Network Coding

LIANG Ping-yuan，HUANg Guang-ya，LU Zhi，XU Qian
(College of Information Science and Engineering，Jishou University，Jishou 416000，Hunan China)

Wireless sensor networks are often driven by batteries when they are used in gathering data or ubiquitous computing.Therefore，energy consumption is the key issue in designing wireless sensor network system.When network coding is applied，intermediate nodes may send out data packets that are linear by minimizing the number of transmissions required to communicate a given amount of information across the wireless sensor networks.The less the number of transmissions is，the less the energy consumption will be.The transmission process and the principle of saving energy in wireless sensor networks based on network coding are analyzed，and the energy efficienly of the proposed solution using network coding is compared with non-network coding solution.The results show that the transmission power can be reduced efficiently by network coding，and it will benefit the lifetime of wireless sensor networks.

wireless sensor networks;network coding;power minimization;energy efficienly

TN929.5

A

10.3969/j.issn.1007-2985.2013.01.014

1007-2985(2013)01-0056-05*

2012-08-26

網(wǎng)絡(luò)編碼突破了傳統(tǒng)數(shù)據(jù)傳輸?shù)墓潭Ｊ?，與傳統(tǒng)的路由傳輸模式相比，可以提高網(wǎng)絡(luò)的信息傳輸速率，增加網(wǎng)絡(luò)的信息流量［1-4］.網(wǎng)絡(luò)編碼充分利用網(wǎng)絡(luò)上的信道，使數(shù)據(jù)傳輸普適化［5］.當(dāng)部分節(jié)點(diǎn)處于休眠狀態(tài)暫時(shí)停止發(fā)送消息時(shí)，只要有足夠的節(jié)點(diǎn)在工作，網(wǎng)絡(luò)通信仍可正常進(jìn)行.而當(dāng)一部分節(jié)點(diǎn)在數(shù)據(jù)傳輸過(guò)程因能量耗盡而死亡，或是因外界環(huán)境變化而中斷傳輸后，只要其中有路徑到達(dá)目的節(jié)點(diǎn)，數(shù)據(jù)通信也能順利完成，因此，采用網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)魯棒性和可調(diào)節(jié)性也可以得以加強(qiáng)［6］.另外，網(wǎng)絡(luò)編碼還對(duì)整個(gè)網(wǎng)絡(luò)起到負(fù)載均衡的作用，作為流量工程的一種技術(shù)加以應(yīng)用，從而提高整個(gè)網(wǎng)絡(luò)的生存時(shí)間［7］.當(dāng)網(wǎng)絡(luò)編碼應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)時(shí)，不僅可以提高信息傳輸速率，節(jié)約傳輸所需能量，而且能耗與可靠性可實(shí)現(xiàn)均衡.對(duì)于傳統(tǒng)的單路傳輸，網(wǎng)絡(luò)所需能量仍要小于采用網(wǎng)絡(luò)編碼傳輸所需能量，然而只要中間一跳傳輸失敗，則整個(gè)傳輸過(guò)程將失敗，只能依靠MAC層失敗重發(fā)的策略來(lái)提高網(wǎng)絡(luò)的可靠性，這時(shí)其可靠性是比較差的.而采用網(wǎng)絡(luò)編碼之后，多條路徑同時(shí)進(jìn)行傳輸，且中間由于網(wǎng)絡(luò)編碼線性(或非線性)運(yùn)算，其中一部分的傳輸失敗不會(huì)影響數(shù)據(jù)的可靠接收［8-9］，這時(shí)所需的能耗比單路徑傳輸要有所增加.那么，怎樣設(shè)計(jì)簡(jiǎn)單的基于網(wǎng)絡(luò)編碼的多路徑傳輸路由機(jī)制，使能量消耗與可靠性之間實(shí)現(xiàn)均衡，或盡可能地提高無(wú)線傳感器網(wǎng)絡(luò)的使用能效，使功率消耗最小化是目前考慮的重要問(wèn)題.

Ahlswede等［10］研究了基于網(wǎng)絡(luò)編碼的一對(duì)多網(wǎng)絡(luò)連接，在非物理信息流上建立了經(jīng)獨(dú)立信道網(wǎng)絡(luò)的最大流最小割定理.文獻(xiàn)［11］提出了一種保證一定傳輸可靠性的多路徑路由算法，其基本思想是:將原數(shù)據(jù)分割成若干大小相同的數(shù)據(jù)片，每個(gè)數(shù)據(jù)片只在一條路徑中傳遞，根據(jù)路徑的數(shù)目以及每條路徑的出錯(cuò)概率設(shè)計(jì)最佳的分片方式，從而提高可靠性.文獻(xiàn)［12］建立了基于網(wǎng)絡(luò)編碼的多對(duì)一的網(wǎng)絡(luò)連接，允許多個(gè)相關(guān)的傳感器源節(jié)點(diǎn)路徑發(fā)送數(shù)據(jù)包，而不是單獨(dú)地發(fā)送，這樣，可以在提高網(wǎng)絡(luò)可靠性的同時(shí)，又可以利用其多路信息之間的相關(guān)性而實(shí)現(xiàn)資源開(kāi)銷最小化的目的.據(jù)最新進(jìn)展，T.S.Han于文獻(xiàn)［13］中，將基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)連接擴(kuò)充到多對(duì)多的連接，即對(duì)多個(gè)相關(guān)源節(jié)點(diǎn)與多個(gè)匯聚點(diǎn)之間的網(wǎng)絡(luò)連接進(jìn)行研究，建立并證明了其可靠傳輸?shù)某浞直匾獥l件.因此，采用網(wǎng)絡(luò)編碼結(jié)構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)在可靠性上有得天獨(dú)厚的優(yōu)勢(shì).

國(guó)家自然科學(xué)基金資助項(xiàng)目(61173018);湖南省教育廳優(yōu)秀青年資助項(xiàng)目(11B102);湖南省自然科學(xué)基金資助項(xiàng)目(11JJ6061);湖南省大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性實(shí)驗(yàn)計(jì)劃資助項(xiàng)目(JSU-CX-2012-50)

梁平元(1972-)，男，湖南漣源人，吉首大學(xué)信息科學(xué)與工程學(xué)院教授，博士生，主要從事無(wú)線通信與光通信技術(shù)研究.