会话间网络编码技术的无线网络能耗最小化

胡 红，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

会话间网络编码技术的无线网络能耗最小化

胡 红，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

文中主要研究会话间网络编码技术的无线网络能耗最小化。生存期有限的无线网络能耗受限于该网络中节点可达的生存期。将到达相同信宿的多播流组成一个虚拟多播流，在同一个虚拟多播流内的数据流间进行网络编码。用公式表明能量最小化问题，并将其转化为一个线性规划问题。通过拉格朗日对偶将原优化问题转化为对偶问题，该对偶问题可分解为两个子问题：节点生存周期受限时的能耗最小化问题及流守恒和速率受限时的路由调度问题。可利用次梯度算法获得对偶问题的最优解。仿真结果表明，理论分析与实际计算非常吻合，基于会话间网络编码技术的无线网络能耗小于基于会话内网络编码技术的系统能耗，而基于会话内网络编码技术的系统能耗小于基于传统路由转发技术的系统能耗。

会话内网络编码；会话间网络编码；无线网络；次梯度

0 引 言

与传统的路由转发数据方式不同，网络编码技术允许中间节点将接收到的数据包进行编码处理再转发出去，中间节点或者信宿节点通过网络译码来获得信源发出的原始数据包信息[1]。网络编码可以极大地提高网络性能，如吞吐量[2-4]和功耗[5-8]等，因而受到了当前学者的广泛关注。

网络编码可分为两种：会话内网络编码[9]和会话间网络编码[10]。会话内网络编码只允许将来自同一会话流的数据包进行网络编码，而会话间网络编码则允许将来自不同会话流的数据包进行编码。通常情况下研究的是针对单个多播流的会话内网络编码[11]，可由线性网络编码使系统性能达到最优[12]。文献[13-14]考虑了基于两个会话流间的网络编码的系统性能最优化问题。然而，针对一般化的会话间网络编码技术的系统性能最优化问题至今仍是一个开放的问题。

文中考虑将到达相同信宿的多播数据流组成一个虚拟多播流(“commodity”)，在同一个“commodity”内的数据流间进行会话间网络编码，假定网络中的每个节点生存周期均受限，基于会话间网络编码技术来优化网络编码子图[15]，从而使网络能耗最小化[16]。该问题的对偶问题可分解为两个子问题：节点生存周期受限时的能耗最小化问题、流守恒和速率受限时的路由调度问题。通过数学分析，可将第二个子问题简化为最大权重的超图匹配问题，该问题大体上能仅仅通过节点局部信息交换解出。

1 系统模型与干扰模型

定义单播流是数据从一个信源传输到一个信宿，而多播流是数据从一个信源传输到所有的信宿，将到达相同信宿的多播流组成一个“commodity”。文中用c和C分别表示一个特定“commodity”和所有“commodity”的集合。Sc和Dc分别表示“commodity”c的信源节点集合和信宿节点集合；sc和dc分别表示“commodity”c的一个信源节点和一个信宿节点。

在特定的资源共享模型中，网络的可达速率域由调度策略决定。Π和π分别表示所有调度方案的集合和一种调度方案，则时间共享的网络的可达速率域为：

(1)

2 最优化问题

(2)

由式(2)可知，能耗Ei由生存期Ti和数据的发送、接收速率决定。优化网络能耗即是将节点中能耗最大值进行最小化，即：

(3)

2.1 线性规划问题

由上述定义，会话间网络编码的能量最小化问题可表示为：

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)

假设总是存在网络编码的流分布对于所有流的需求，它们能满足能量守恒定律并严格遵守原始问题的速率约束条件，还能通过选择足够大的E来满足能量约束条件；因此Slater[17]约束条件总是满足的，强对偶性适用于这个原始问题和对偶问题，可以通过式(12)、(13)所描述的对偶问题来解出原始问题。

2.3 次梯度算法

考虑E的范围为[0,e]，其中e是E值一个比较松的上限。由上述过程得到的对偶函数是可微的，规范化目标函数的拉格朗日为：

(14)

对于给定的λicsd,μi，规范化问题的对偶函数为：

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

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

次梯度算法中，步长是事先给定的。根据文献[17]，次梯度方法能保证收敛到最优，当αk满足下述条件：

(23)

根据上述分析，可以得到次梯度算法解决会话间网络编码能量最小化问题的步骤如下：

(4)次梯度的计算：由式(19)、(20)计算次梯度，如果所有的次梯度都为0，则最优问题得到解决，迭代停止。

3 仿真结果分析

本节利用Matlab仿真软件在无线网格网络环境下，对前面提出的基于次梯度的会话间网络编码能耗最小化算法进行了仿真，并与传统的路由算法和会话内网络编码算法进行性能比较，分析这三种算法性能上的差异及造成这种差异的原因。

3.1 无线网格网络下的仿真

文中研究一个4×4的无线网格网络，如图1所示。

在该网络中，每个节点到与它相邻的节点的距离相等，且只有它的邻居节点才能获得这个节点所发送的信息。

为了方便实现，先从中选择信源节点，再从剩余网络节点中随机选取目的节点。

图1 无线网格网络

3.2 仿真结果与性能分析

图2给出了一个在4×4无线网格网络中的两个信源，三个目的节点的多播中应用基于次梯度的会话间能耗最小化算法的收敛性能，同时也给出了传统的路由算法和会话内网络编码算法能耗最小化的收敛性能。

图2 4×4的无线网格网络中的性能仿真

由图2可知，基于会话间网络编码算法的系统能耗比基于传统路由和会话内网络编码算法的系统能耗都要小。即使是在最初迭代时，基于会话间网络编码算法的系统能耗也比其他两种算法低。这是由于会话间网络编码可以利用无线网络的广播优势，将来自不同信源的数据包一起编码后再发送，在一次传输中发送更多的编码信息至邻居节点，大大减少了网络中能耗。

在图3中，将三种算法分别在3×3，5×5，7×7，9×9和11×11的节点规模的无线网格网络中应用，得到节点能耗性能图。

图3 不同规模的无线网格网络中的性能仿真

如图3所示，与传统路由算法相比，网络编码可以明显降低能量消耗，且不同规模的网络能耗性能的提升有所差距。会话内网络编码算法比路由算法性能提升20%～40%，而会话间网络编码算法则在会话内网络编码算法的基础上进一步提升，能耗降低约10%～30%。此外，由图可见，随着节点个数的增加，基于次梯度的会话间网络编码算法相对于其他两种算法性能的提升越明显。

4 结束语

文中主要介绍生存期受限时基于会话间网络编码的无线网络能耗的最小化问题。原优化问题并不满足严格凸函数特性，利用增广拉格朗日函数来获得优化问题的分布式求解算法。仿真结果表明，与会话内网络编码和传统路由的情况相比，基于会话间网络编码的系统能耗可显著降低。

[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] 黄 政，王 新.网络编码中的优化问题的研究[J].软件学报，2009，20(5)：1349-1361.

[4] 杨 林，郑 刚，胡晓惠.网络编码的研究进展[J].计算机研究与发展，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] 康巧燕，孟相如，王建峰.网络编码对组播通信的性能改善[J].计算机工程与应用，2007，43(3)：150-152.

[9] 王庆斌，梅中辉.无线网络中基于网络编码的最小能量多播[J].计算机技术与发展，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] 卢文伟，朱艺华，陈贵海.无线传感器网络中基于线性网络编码的节能路由算法[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] 杨叶舒，梅中辉.无线网络中网络编码子图优化问题的研究[J].计算机技术与发展，2014，24(3)：86-89.

[16] 陶少国，黄佳庆，杨宗凯,等.一种改进的最小网络编码代价的算法[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-)，女，硕士研究生，研究方向为网络编码技术、资源优化等；梅中辉，副教授，研究生导师，研究方向为网络编码技术、协助通信技术等。

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