會話間網(wǎng)絡編碼技術(shù)的無線網(wǎng)絡能耗最小化

胡 紅，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

會話間網(wǎng)絡編碼技術(shù)的無線網(wǎng)絡能耗最小化

胡 紅，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

文中主要研究會話間網(wǎng)絡編碼技術(shù)的無線網(wǎng)絡能耗最小化。生存期有限的無線網(wǎng)絡能耗受限于該網(wǎng)絡中節(jié)點可達的生存期。將到達相同信宿的多播流組成一個虛擬多播流，在同一個虛擬多播流內(nèi)的數(shù)據(jù)流間進行網(wǎng)絡編碼。用公式表明能量最小化問題，并將其轉(zhuǎn)化為一個線性規(guī)劃問題。通過拉格朗日對偶將原優(yōu)化問題轉(zhuǎn)化為對偶問題，該對偶問題可分解為兩個子問題：節(jié)點生存周期受限時的能耗最小化問題及流守恒和速率受限時的路由調(diào)度問題。可利用次梯度算法獲得對偶問題的最優(yōu)解。仿真結(jié)果表明，理論分析與實際計算非常吻合，基于會話間網(wǎng)絡編碼技術(shù)的無線網(wǎng)絡能耗小于基于會話內(nèi)網(wǎng)絡編碼技術(shù)的系統(tǒng)能耗，而基于會話內(nèi)網(wǎng)絡編碼技術(shù)的系統(tǒng)能耗小于基于傳統(tǒng)路由轉(zhuǎn)發(fā)技術(shù)的系統(tǒng)能耗。

會話內(nèi)網(wǎng)絡編碼；會話間網(wǎng)絡編碼；無線網(wǎng)絡；次梯度

0 引 言

與傳統(tǒng)的路由轉(zhuǎn)發(fā)數(shù)據(jù)方式不同，網(wǎng)絡編碼技術(shù)允許中間節(jié)點將接收到的數(shù)據(jù)包進行編碼處理再轉(zhuǎn)發(fā)出去，中間節(jié)點或者信宿節(jié)點通過網(wǎng)絡譯碼來獲得信源發(fā)出的原始數(shù)據(jù)包信息[1]。網(wǎng)絡編碼可以極大地提高網(wǎng)絡性能，如吞吐量[2-4]和功耗[5-8]等，因而受到了當前學者的廣泛關(guān)注。

網(wǎng)絡編碼可分為兩種：會話內(nèi)網(wǎng)絡編碼[9]和會話間網(wǎng)絡編碼[10]。會話內(nèi)網(wǎng)絡編碼只允許將來自同一會話流的數(shù)據(jù)包進行網(wǎng)絡編碼，而會話間網(wǎng)絡編碼則允許將來自不同會話流的數(shù)據(jù)包進行編碼。通常情況下研究的是針對單個多播流的會話內(nèi)網(wǎng)絡編碼[11]，可由線性網(wǎng)絡編碼使系統(tǒng)性能達到最優(yōu)[12]。文獻[13-14]考慮了基于兩個會話流間的網(wǎng)絡編碼的系統(tǒng)性能最優(yōu)化問題。然而，針對一般化的會話間網(wǎng)絡編碼技術(shù)的系統(tǒng)性能最優(yōu)化問題至今仍是一個開放的問題。

文中考慮將到達相同信宿的多播數(shù)據(jù)流組成一個虛擬多播流(“commodity”)，在同一個“commodity”內(nèi)的數(shù)據(jù)流間進行會話間網(wǎng)絡編碼，假定網(wǎng)絡中的每個節(jié)點生存周期均受限，基于會話間網(wǎng)絡編碼技術(shù)來優(yōu)化網(wǎng)絡編碼子圖[15]，從而使網(wǎng)絡能耗最小化[16]。該問題的對偶問題可分解為兩個子問題：節(jié)點生存周期受限時的能耗最小化問題、流守恒和速率受限時的路由調(diào)度問題。通過數(shù)學分析，可將第二個子問題簡化為最大權(quán)重的超圖匹配問題，該問題大體上能僅僅通過節(jié)點局部信息交換解出。

1 系統(tǒng)模型與干擾模型

定義單播流是數(shù)據(jù)從一個信源傳輸?shù)揭粋€信宿，而多播流是數(shù)據(jù)從一個信源傳輸?shù)剿械男潘?，將到達相同信宿的多播流組成一個“commodity”。文中用c和C分別表示一個特定“commodity”和所有“commodity”的集合。Sc和Dc分別表示“commodity”c的信源節(jié)點集合和信宿節(jié)點集合；sc和dc分別表示“commodity”c的一個信源節(jié)點和一個信宿節(jié)點。

在特定的資源共享模型中，網(wǎng)絡的可達速率域由調(diào)度策略決定。Π和π分別表示所有調(diào)度方案的集合和一種調(diào)度方案，則時間共享的網(wǎng)絡的可達速率域為：

(1)

2 最優(yōu)化問題

(2)

由式(2)可知，能耗Ei由生存期Ti和數(shù)據(jù)的發(fā)送、接收速率決定。優(yōu)化網(wǎng)絡能耗即是將節(jié)點中能耗最大值進行最小化，即：

(3)

2.1 線性規(guī)劃問題

由上述定義，會話間網(wǎng)絡編碼的能量最小化問題可表示為：

minE

(4)

d∈Dc

(5)

(6)

(7)

(riJ)∈Co(r)

(8)

(9)

(10)

2.2 拉格朗日對偶

引入λicsd,μi分別作為式(5)和式(9)的拉格朗日乘子，將可以得到拉格朗日對偶問題L(E,g,f;λ,μ)：

L(E,g,f;λ,μ)=E+

(11)

maxφ(λ,μ)

(12)

s.tμ≥0

(13)

假設總是存在網(wǎng)絡編碼的流分布對于所有流的需求，它們能滿足能量守恒定律并嚴格遵守原始問題的速率約束條件，還能通過選擇足夠大的E來滿足能量約束條件；因此Slater[17]約束條件總是滿足的，強對偶性適用于這個原始問題和對偶問題，可以通過式(12)、(13)所描述的對偶問題來解出原始問題。

2.3 次梯度算法

考慮E的范圍為[0,e]，其中e是E值一個比較松的上限。由上述過程得到的對偶函數(shù)是可微的，規(guī)范化目標函數(shù)的拉格朗日為：

(14)

對于給定的λicsd,μi，規(guī)范化問題的對偶函數(shù)為：

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

其中，αk>0,表示步長。

次梯度算法中，步長是事先給定的。根據(jù)文獻[17]，次梯度方法能保證收斂到最優(yōu)，當αk滿足下述條件：

(23)

根據(jù)上述分析，可以得到次梯度算法解決會話間網(wǎng)絡編碼能量最小化問題的步驟如下：

(4)次梯度的計算：由式(19)、(20)計算次梯度，如果所有的次梯度都為0，則最優(yōu)問題得到解決，迭代停止。

3 仿真結(jié)果分析

本節(jié)利用Matlab仿真軟件在無線網(wǎng)格網(wǎng)絡環(huán)境下，對前面提出的基于次梯度的會話間網(wǎng)絡編碼能耗最小化算法進行了仿真，并與傳統(tǒng)的路由算法和會話內(nèi)網(wǎng)絡編碼算法進行性能比較，分析這三種算法性能上的差異及造成這種差異的原因。

3.1 無線網(wǎng)格網(wǎng)絡下的仿真

文中研究一個4×4的無線網(wǎng)格網(wǎng)絡，如圖1所示。

在該網(wǎng)絡中，每個節(jié)點到與它相鄰的節(jié)點的距離相等，且只有它的鄰居節(jié)點才能獲得這個節(jié)點所發(fā)送的信息。

為了方便實現(xiàn)，先從中選擇信源節(jié)點，再從剩余網(wǎng)絡節(jié)點中隨機選取目的節(jié)點。

圖1 無線網(wǎng)格網(wǎng)絡

3.2 仿真結(jié)果與性能分析

圖2給出了一個在4×4無線網(wǎng)格網(wǎng)絡中的兩個信源，三個目的節(jié)點的多播中應用基于次梯度的會話間能耗最小化算法的收斂性能，同時也給出了傳統(tǒng)的路由算法和會話內(nèi)網(wǎng)絡編碼算法能耗最小化的收斂性能。

圖2 4×4的無線網(wǎng)格網(wǎng)絡中的性能仿真

由圖2可知，基于會話間網(wǎng)絡編碼算法的系統(tǒng)能耗比基于傳統(tǒng)路由和會話內(nèi)網(wǎng)絡編碼算法的系統(tǒng)能耗都要小。即使是在最初迭代時，基于會話間網(wǎng)絡編碼算法的系統(tǒng)能耗也比其他兩種算法低。這是由于會話間網(wǎng)絡編碼可以利用無線網(wǎng)絡的廣播優(yōu)勢，將來自不同信源的數(shù)據(jù)包一起編碼后再發(fā)送，在一次傳輸中發(fā)送更多的編碼信息至鄰居節(jié)點，大大減少了網(wǎng)絡中能耗。

在圖3中，將三種算法分別在3×3，5×5，7×7，9×9和11×11的節(jié)點規(guī)模的無線網(wǎng)格網(wǎng)絡中應用，得到節(jié)點能耗性能圖。

圖3 不同規(guī)模的無線網(wǎng)格網(wǎng)絡中的性能仿真

如圖3所示，與傳統(tǒng)路由算法相比，網(wǎng)絡編碼可以明顯降低能量消耗，且不同規(guī)模的網(wǎng)絡能耗性能的提升有所差距。會話內(nèi)網(wǎng)絡編碼算法比路由算法性能提升20%～40%，而會話間網(wǎng)絡編碼算法則在會話內(nèi)網(wǎng)絡編碼算法的基礎上進一步提升，能耗降低約10%～30%。此外，由圖可見，隨著節(jié)點個數(shù)的增加，基于次梯度的會話間網(wǎng)絡編碼算法相對于其他兩種算法性能的提升越明顯。

4 結(jié)束語

文中主要介紹生存期受限時基于會話間網(wǎng)絡編碼的無線網(wǎng)絡能耗的最小化問題。原優(yōu)化問題并不滿足嚴格凸函數(shù)特性，利用增廣拉格朗日函數(shù)來獲得優(yōu)化問題的分布式求解算法。仿真結(jié)果表明，與會話內(nèi)網(wǎng)絡編碼和傳統(tǒng)路由的情況相比，基于會話間網(wǎng)絡編碼的系統(tǒng)能耗可顯著降低。

[1]AhlswedeR,CaiN,LiSYR,etal.Networkinformationflow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216.

[2]SenguptaS,RayanchuS,BanerjeeS.Ananalysisofwirelessnetworkcodingforunicastsessions:thecaseforcoding-awarerouting[C]//Procof26thIEEEinternationalconferenceoncomputercommunications.Anchorage,AK:IEEE,2007:1028-1036.

[3] 黃 政，王 新.網(wǎng)絡編碼中的優(yōu)化問題的研究[J].軟件學報，2009，20(5)：1349-1361.

[4] 楊 林，鄭 剛，胡曉惠.網(wǎng)絡編碼的研究進展[J].計算機研究與發(fā)展，2008，45(3):400-407.

[5]LunDS,RatnakarN,MedardM,etal.Minimum-costmulticastovercodedpacketnetworks[J].IEEETransonInformationTheory,2006,52(6):2608-2623.

[6]WuY,ChouPA,KungSY.Minimum-energymulticastinmobileadhocnetworksusingnetworkcoding[J].IEEETransonCommunications,2005,53(11):1906-1918.

[7]CuiT,ChenL,HoT.Energyefficientopportunisticnetworkcodingforwirelessnetworks[C]//Procof27thIEEEinternationalconferenceoncomputercommunications.Phoenix,AZ:IEEE,2008:361-365.

[8] 康巧燕，孟相如，王建峰.網(wǎng)絡編碼對組播通信的性能改善[J].計算機工程與應用，2007，43(3)：150-152.

[9] 王慶斌，梅中輝.無線網(wǎng)絡中基于網(wǎng)絡編碼的最小能量多播[J].計算機技術(shù)與發(fā)展，2013，23(1)：150-153.

[10]KattiS,RahulH,HuW,etal.XORsintheair:practicalwirelessnetworkcoding[J].IEEE/ACMTransonNetworking,2008,16(3):497-510.

[11]HoT,ViswanathanH.Dynamicalgorithmsformulticastwith

intra-session network coding[J].IEEE Trans on Information Theory,2009,55(2):797-815.

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

[13] Traskov D,Ratnakar N,Lun D S,et al.Network coding for multiple unicasts:an approach based on linear optimization[C]//Proc of 2006 IEEE international symposium on information theory.Seattle,USA:IEEE,2006:1758-1762.

[14] Khreishah A,Wang C C,Shroff N B.Cross-layer optimization for wireless multihop networks with pairwise intersession network coding[J].IEEE Journal on Selected Areas in Communications,2009,27(5):606-621.

[15] 楊葉舒，梅中輝.無線網(wǎng)絡中網(wǎng)絡編碼子圖優(yōu)化問題的研究[J].計算機技術(shù)與發(fā)展，2014，24(3)：86-89.

[16] 陶少國，黃佳慶，楊宗凱,等.一種改進的最小網(wǎng)絡編碼代價的算法[J].華中科技大學學報:自然科學版，2008，36(5):1-4.

[17] Boyd S,Vandenberge L.Convex optimization[M].Cambridge:Cambridge University Press,2004.

[18] Xiao L,Johansson M,Boyd S.Simultaneous routing and resource allocation via dual decomposition[J].IEEE Trans on Communications,2004,52(7):1136-1144.

[19] Bertsekas D P,Tsitsiklis J N.Parallel and distributed computation:numerical methods[M].USA:Athena Scientific,1997.

Energy Minimization with Inter-session Network Coding in Lifetime Constrained Wireless Networks

HU Hong，MEI Zhong-hui

(College of Telecommunication & Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The energy minimization for wireless networks with inter-session network coding was researched in this paper.The energy consumption of a lifetime constrained network is often limited by the available lifetime of network nodes.Multicast flows with the same destination nodes constitute a commodity and network coding can be employed among different flows in the same commodity.The problem of energy minimization is first formulated,and then transformed into a linear programming problem.In light of Lagrangian dual,the primary optimization problem can be converted into a dual problem,which can be solved by utilizing sub-gradient method.The dual problem is decomposed into two sub-problems.One is energy minimization with lifetime constrained at each node,and the other is routing and scheduling under the flow conservation and physical rates constraints.Simulation results illustrate that the energy consumption of wireless networks with inter-session network coding is lower than that of intra-session network coding,and the energy consumption of wireless networks with intra-session is no more than that of traditional routing.

intra-session network coding;inter-session network coding;wireless network;sub-gradient

2015-05-31

2015-09-04

時間：2016-01-26

國家科技重大專項(2010zx03003-003)作者簡介：胡 紅(1990-)，女，碩士研究生，研究方向為網(wǎng)絡編碼技術(shù)、資源優(yōu)化等；梅中輝，副教授，研究生導師，研究方向為網(wǎng)絡編碼技術(shù)、協(xié)助通信技術(shù)等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1522.080.html

TP31

A

1673-629X(2016)02-0185-04

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