基于网络编码的无线多跳网络寿命优化模型研究

李　明　王　睿　马　睿　汪新建　童　玲

(中国人民解放军成都军区总医院网络管理中心　四川 成都 610083)



基于网络编码的无线多跳网络寿命优化模型研究

李明王睿马睿汪新建童玲

(中国人民解放军成都军区总医院网络管理中心四川 成都 610083)

摘要针对无线多跳网络的寿命优化问题，通过将无网络编码、双向网络编码和侦听网络编码的寿命优化问题转化为线性约束规划问题，提出一种基于网络编码的无线多跳网络寿命优化模型。在该模型中，基于功率控制模型、数据流个数、业务需求分布和每个节点初始能量的随机拓扑模型，首先对这三种不同情形下的网络寿命优化问题进行建模。然后使用内点法对这些问题进行求解，最后评估网络寿命。通过对多种情况下网络编码对网络寿命的影响进行仿真，验证了模型的有效性。仿真结果表明，在弱功控情况下网络编码可以取得较好的网络寿命增益，且该增益随数据流个数的增加而增加，相对于侦听网络编码方法，双向网络编码方法在取得相近性能的同时，具有更低的计算开销。

关键词寿命优化无线多跳网络网络编码线性规划随机拓扑模型

ON LIFETIME OPTIMISATION MODEL FOR WIRELESS MULTI-HOP NETWORKS BASED ON NETWORK CODING

Li MingWang RuiMa RuiWang XinjianTong Ling

(Department of Network Management Center,Chengdu Military General Hospital,Chengdu 610083,Sichuan,China)

AbstractFor the problem of wireless multi-hop networks lifetime optimisation, we proposed a network coding-based wireless multi-hop networks lifetime optimisation model by converting the problem of lifetime optimisation for networkless coding, two-way network coding and interception network coding to linear-restriction programming problem. In this model, based on the power control model, the number of data flows, the traffic demand distributions and the stochastic topology model of initial energy of each node, we first modelled the network lifetime optimisation problems under these three different scenarios, then solved them via the interior-point method, and finally evaluated the networks lifetime. To verify the validity of the model, we simulated the impact of network coding on network lifetime under various network environments. Simulation results showed that with weak power control the network coding could achieve better networks lifetime gain, and which increased with the increase of the number of data flow, and that the two-way network coding method, relative to interception network coding, performed close to it but had lower computation overhead.

KeywordsLifetime optimisationWireless multi-hop networksNetwork codingLinear programmingStochastic topology model

0引言

在能量受限的无线多跳网络中，更换节点电池或给节点电池充电通常是不方便或是不可能的。因此，最小化所有节点尤其是瓶颈节点的能量消耗对延长网络寿命非常重要。由于整个网络的能量最小化可能导致某些瓶颈节点的过度使用和网络的断开，所以研究网络寿命比研究能源消耗更有意义。网络编码方法可有效改善网络的吞吐量性能[1,2]和功率的消耗[3-5]。Ahlswede首先提出了网络编码，并证明多播的速率域，即从源点到汇点的最小割/最大流，可以通过线性网络编码来获得[6]。将网络编码运用到无线多跳网络中，亦会给网络的优化带来新的机遇与挑战。网络编码的研究对象主要包括两类：最优的单播网络中的网络编码，即会话内网络编码；最优的广播网络编码，即会话间的网络编码。对会话内网络编码已经有了深入全面的了解，并可利用线性网络编码对其进行实现[7,8]。针对网络优化问题，相关文献提出了在无线和有线网络中基于会话内网络编码多播的容量区域，采用动态背压算法和全分布交叉层算法来实现多播在分配方式上吞吐量的优化[9,10]。基于网络编码的最低代价多播可以在多项式时间内或者采用双分布式子梯度法加以实现，其等同于基于线性边缘定价的最低成本[3,4]。针对使用会话间网络编码的网络优化问题，相关工作已开展。针对预定路由，提出了调度的联合优化和网络编码以及背压优化策略并对之加以分析[1,11]。针对联合路由和网络编码采用线性规划法进行理论分析。结果表明，编码和干扰感知路由相较于编码无关路由可以产生更高的性能增益[2]。相关文献针对成对对话间网络编码的网络应用优化问题进行了建模研究[12]。

然而，到目前为止，很少有研究基于网络编码的无线多跳网络的寿命最大化问题。对于没有网络编码情形下的寿命优化问题，可通过分布式子梯度迭代法[13]或启发式流量扩张路由法[14]来加以解决。针对网络编码情形下的寿命优化问题，相关文献考虑了在某些具体情况下，应用网络编码的寿命延长问题[15]并通过简便的拓扑法，对使用网络编码的多播寿命最大化问题进行了建模分析和评估[16]。另外，相关文献对使用单跳网络编码的寿命最大化问题进行了建模分析和解析[17]。但是，针对对话间网络编码对网络寿命的影响仍未得出确切的结论。

因此，本文主要研究使用会话间网络编码的无线多跳网络的寿命最大化问题，分析网络寿命随会话间网络编码的延长程度并研究影响改善率的因子。本文考虑两种编码方法，即双向网络编码和侦听网络编码，并分别评估它们的性能、复杂度和开销。

1基本原理与模型

1.1网络模型

通常将无线多跳网络建模为一个有向图G={V,E}，其中V是节点集合，E是链路集合。这里假设链路是对称的，即如果链路(i,j)∈E，则(j,i)∈E。使用rij指代链路(i,j)的速率。在本文中，分别用c、C、sc和dc代表从特定源节点和目的节点的数据流、数据流集合、源节点和目的节点。

目前传输功率控制是一种有效降低功率消耗和空间干扰的技术。此前对网络寿命的研究通常假设完全功率控制，而实际系统通常只能支持有限功率控制。故本文考虑两种极端情形：1) 未采用传输功率调整的协议模型；2) 采用完全功率控制的物理模型。

给定一种用于资源分享和调度的干扰模型，例如基本或者K跳干扰模型，网络G的可达速率域定义为Co(r)，它可用一个多维多面体来表示。

1.2网络编码

本文考虑单跳网络中使用的线性异或网络编码方式，该编码方式与c=a⊕b类似。这里，a和b为输入分组，c为异或之后的输出分组。基于两符号(分组)的网络编码占COPE的50%以上，占COPR的99%以上[12]。另外，对实际系统的研究也发现多于两个符号的网络编码运算会使优化过程极其复杂。因此，本文对网络编码的分析将在使用线性异或网络编码的单跳成对网络中进行。对于超过两个符号的网络编码，可以通过伺机方式，如在COPE和COPR中来实现。

下面的引理给出了单跳成对网络编码正常工作的要求。

引理1在单跳网络编码中，对于节点k，若想从节点i传输的编码分组Pc=Px⊕P解码出分组Px，则该节点需满足以下两个条件：1) 节点k从节点i接收到分组Pc；2) 节点k获得了未编码分组P。

考虑两种节点k获得未编码分组P的机会：① 通过链路(k,i)将P传输到节点i，如图1(a)中所示的节点k处的分组P2；② 节点k正确地从其他链路侦听到分组P，如图1(b)中所示的由节点k从链路(m,k)侦听到的分组P2。根据节点获得未编码分组的这两种方式，定义单跳成对网络中的两种网络编码：① 双向网络编码方式，该方式仅包含机会1)中的分组；② 侦听网络编码方式，该方式同时包含机会1)和机会2)中的分组。

图1　单跳网络编码

由于单跳网络编码同时涉及到前跳节点和后跳节点，为了描述的简便，本文定义了一种双跳链路。

定义1(双跳链路)对于节点i，从节点j到节点k经过节点i的链路称为节点i处的双跳链路，记为(j,i,k),j≠k。

需要注意的是，对于从源节点开始的传输，有j=i，而对于目的节点的接收，有i=k。

从上面的定义和描述可以看出，单跳网络编码依赖于邻居节点的相对位置。例如，在图1(b)中，双向链路(j,i,k)和(m,i,n)可以同时进行编码，这是因为节点k和n可以分别侦听到节点m和j的数据。而双跳网络(j,i,k)和(n,i,m)就不能同时编码。由此可以得到可同时进行网络编码的双向链路在几何上的结构定义。

定义2(网络编码结构)网络编码结构指的是在几何上能够同时编码的双向链路的有序集合。

使用上述定义和简记法，可以表述下述引理，以确定一种网络编码情况是双向网络编码还是侦听网络编码。

引理2Si是双向网络编码结构,当且仅当p(Si)=n(Si)，而Si是侦听网络编码结构,当且仅当p(Si)≠n(Si)。

1.3网络寿命

网络寿命指的是网络运行良好，尤其是满足网络所有需求的持续时间。以前的研究对不同应用场景下的网络寿命提出了多种定义，例如所有节点的最小寿命、寿命向量等。为了简化分析，本文采用了第一种定义，并将其扩展，以使其适合文中分析网络编码的情况。

(1)

其中，第一项为节点i处的传输数据流c的功率消耗，第二项是从所有邻节点j∈V接收的数据流c的功率消耗，第三项是侦听的接收功率消耗。需要注意的是，对于一个网络编码结构Sj，节点i处的侦听条件为i∈n(Sj)，而i∉p(Sj)。

节点i处的寿命就可表示为：

(2)

其中，网络寿命由节点i的能量Ei和节点i处理所有分组所消耗的功率决定。由此得到整个网络的寿命：

(3)

2基于网络编码的无线多跳网络寿命优化模型

对无网络编码情形、双向网络编码情形和侦听网络编码情形下的网络寿命优化问题进行模型化描述。其中，无网络编码情形下的优化问题是另外两种情形的基准。本文提出了一种新的公式化描述方法，该方法从节点和本地数据流的角度对优化问题进行描述，并具有低复杂度。

2.1无网络编码情形

无网络编码情形下，优化问题的约束与流量守恒法则、总能量限制、每条链路的可达速率域以及整个网络有关。这种情形下，寿命优化问题可表述为：

maxT

(4)

(5)

(6)

(rij)∈Co(r)

(7)

(8)

其中，xc为数据流c的流量需求。

式(5)中的约束是能量约束，它说明了节点i在寿命T内的能量消耗不大于其初始能量Ei。式(6)和式(7)给出了速率约束，两式解释了链路(i,j)的总速率小于调度速率rij以及可达速率域Co(r)内的所有速率。

当链路速率足够大以使所有链路都能同时满足速率需求时，网络寿命就不会受干扰模型和调度算法的影响。由于对于流量需求相对较小的能量受限的无线网路通常满足这个条件，因此如式(6)和式(7)所示的速率约束可以忽略不计。优化问题可简化为：

maxT

(9)

(10)

2.2双向网络编码情形

maxT

(11)

(12)

(13)

其中，网络编码场景Fi集合仅包含双向网络编码和未编码传输。为了分析和研究的方便，这里假设它们之间并无差别。式(11)中的约束为流量守恒法则。式(12)中的约束是双向网络编码的编码和解码要求，它表明在满足(j,i,k)=Si(1)的网络编码结构Si上，数据流c的总传输速率小于该数据流从j到i的总输入速率。能量约束由式(13)给出。

2.3侦听网络编码情形

除了双向网络编码中的约束，侦听网络编码还需对前跳节点提出要求。为了正确解码使用侦听的分组，未编码数据的侦听速率应当大于总编码速率。故该情形下的寿命最优化问题可表述为：

maxT

(14)

(15)

(16)

(17)

式(14)给出了流量守恒法则。与式(12)相同，式 (15)中的约束与编码要求有关，即在满足(j,i,k)=Si(1)，∀k的网络编码结构Si上，数据流c的总传输速率小于来自j节点的总输入速率。式(16)描述了使用侦听的网络编码的解码要求。所有编码结构{Si}，包括(j,i,k)和(j′,i,k′),k≠j′的和速率应该小于从h到i，经过j′并由j侦听的未编码分组的速率。式(17)给出了能量约束。

2.4动态路由算法优化

在有网络编码场景下，为了优化网络的寿命，使用动态路由算法对网络的拓扑进行优化，进而可以使节点传输数据所需的路由更短，从而优化了网络的寿命。

在动态路由算法中，节点i的周期消耗可表示为：

(18)

其中，Ni为节点i的邻居节点集合，xij为节点i向节点j发送的信息数量，rij,tij分别为收发信息的能量损失系数，从而得到节点i的寿命：

(19)

其中bi为节点i的剩余能量。

从而网络寿命可定义为：

(20)

其中，(0,i)∈E表示链路(0,i)为网络中从原点到节点i的一条链路。

应用线性规划最大最小网络中的节点寿命：

∀i∈N∀j∈Ni

(21)

动态路由算法描述如下：

1) 初始化：获取网络的拓扑信息，k=1；

2) 执行式(21)的线性规划过程，获取节点的路由信息；

3) 当网络中有节点因能量耗尽而失效时，更新网络拓扑，如果存在基站的一跳节点，则转2)，k=k+1；

3仿真实验与分析

可采用性能评估的集中式解法[2]、对偶子梯度方法[3,13]和启发式流量扩张路由法[14,19]来研究性能的评估，这里采用第一种方法。针对不同的能量分布的配置、业务需求、数据流个数和功率控制模型开展网络寿命和计算开销方面的评估工作。

3.1参数设置

为了深入分析网络编码对寿命的影响，使用简单功率消耗模型。假设所有节点的物理特性和电气特性都是相同的且信道衰落为参数α=4的指数平坦衰落，则将一个比特从节点i传输到节点j的能量消耗仅依赖于节点之间的距离和收发器的功率消耗。发送和接收的功率消耗可写为：

(22)

(23)

3.2网络寿命和性能仿真

该部分将评估一个基于多约束编码的无线多跳网络寿命性能。在80 m×80 m的正方形区域内随机放置20个节点，且节点的平均度数为2.8。假设每个节点的初始能量服从均值为P的指数分布。每个节点产生16个数据流，且源节点从20个节点中随机选择。假定所有的数据流都具有合适的路径，即每个数据流的源节点和汇聚节点都是相连的。

为了评估协议模型和物理模型下网络寿命和计算开销的性能。所有仿真都运行50次且性能指标的均值和方差都归一到无网络编码情形下的对应值。

1) 平均寿命:设P=5并假设所有流量的需求为1 kbps，双向网络编码和侦听网络编码对不同数据流个数的归一化结果如 图 2所示。由图可知：(1) 网络寿命随数据流个数的增加而增加，这是因为更多的数据流个数会产生更多的编码机会。由于传输功率最高的链路决定着传输功率消耗，使用完全功率控制的物理模型所能节省的能量有限，故传输功率协议模型下的寿命增益远高于物理模型下的寿命增益；(2) 双向网络编码和侦听网络编码下的寿命之间的差距并不显著，甚至可以忽略。

图2　在物理和功率协议模型下，使用双向和侦听网络编码的归一化寿命随不同数据流个数的变化情况

2) 计算开销:使用迭代次数来评估优化问题的计算开销，仿真结果如图3所示。由图可知：(1) 两种功率控制模型下，迭代次数随着数据流个数的增加而增加；(2) 物理模型下的迭代次数比协议模型下的迭代次数高；(3) 使用侦听网络编码的迭代次数要高于使用双向网络编码的迭代次数。

图3　迭代次数随数据流个数的变化情况

3) 初始能量的影响:双向网络编码和侦听网络编码归一化寿命的编码机制涉及两种不同的初始能量配置，即P=1和P=5。不同初始能量配置下的两类模型的网络寿命如图4所示。图中，物理功率控制模型和协议功率控制模型分别用Phy，Pro表示，双向网络编码方式和侦听网络编码方式分别用2W和OH表示。可以发现寿命均随着数据流个数的增加而增加，但寿命和初始能量之间并不存在简单的对应关系。

图4　不同初始能量，网络编码机制和功率控制模型下的网络寿命

4) 业务非对称性的影响: 假设所有数据流的业务需求都是相等的，而实际网络中这种对称网络不存在，故需研究业务非对称性对随机拓扑网络寿命的影响。设定P=5，假设每个数据流的业务需求服从均值为F的指数分布。不同功率控制模型、网络编码机制和均值情况下的寿命仿真结果如图5所示。由图可知：双向和侦听网络编码机制的性能相近，与流量需求的平均值无关。

图5　不同业务需求，网络编码机制和功率控制模型下的寿命

通过以上仿真结果，可以发现：(1) 在弱功控情况下，网络编码可以取得较好的寿命增益，且该增益随数据流个数增加而增加；(2) 寿命增益和网络编码的计算开销都均随数据流个数的增加而增加；(3) 业务需求分布和节点初始能量对寿命性能的影响可忽略不计；(4) 侦听网络编码对寿命的优化表现与双向网络编码相近，但其计算开销更高；(5) 在有网络编码场景下，使用动态路由算法，可进一步提高网络的寿命。因此，在实际系统中，使用会话间的网络编码并配合动态路由算法，可以使网络寿命得到优化；在计算开销上，使用双向网络编码更具适应性。另外，上述网络寿命最优化建模和仿真试验结果为分析无线多跳网络参数对网络寿命性能的影响提供了方法和思路。

4结语

本文主要研究基于网络编码的无线多跳网络的寿命最大化问题。针对无网络编码、双向网络编码和侦听网络编码三种情形，对无线多跳网络寿命的最优化问题进行了建模，并将寿命最大化问题转化为线性规划问题。然后通过研究数据流个数、功率控制模型、节点初始能量以及业务非对称性，针对三种情形下的网络寿命和计算开销进行了对比分析。仿真结果表明，使用网络寿命性能增益和计算开销均随数据流个数的增加而增加，业务需求分布和节点初始能量对寿命性能的影响忽略不计，双向网络编码可使用更低的计算开销达到与侦听网络编码类似的性能。

参考文献

[1] Katti S,Rahul H,Hu W,et al.XORs in the air:Practical wireless network coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[2] Sengupta S,Rayanchu S,Banerjee S.An analysis of wireless network coding for unicast sessions:The case for coding-aware routing[C]//26thIEEE International Conference on Compute Communications.Anchorage,AK:INFOCOM,2007:1028-1036.

[3] Lun D S,Ratnakar N,Medard M,et al.Minimum-cost multicast over coded packet networks[J].IEEE Transactions on Information Theory,2008,52(6):2608-2623.

[4] Wu Y,Chou P A,Kung S Y.Minimum-energy multicast in mobile ad hoc networks using network coding[J].IEEE Transactions on Commuhications,2005,53(11):1906-1918.

[5] Cui T,Chen L,Ho T.Energy efficient opportunistic network coding for wireless networks[C]//27thIEEE International Conference on Compute Communications.Phoenix,AZ:INFOCOM,2008:361-365.

[6] 王春雨,张曦煌.Ad Hoc网络中的基于网络编码的无线路由协议研究[J].计算机工程与设计,2013,34(5):1563-1567.

[7] Li S Y R,Yeung R W,Cai N.Linear network coding[J].IEEE Trans.on Information Theory,2003,49(2):371-381.

[8] Ho T,Medard M,Koetter R.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[9] Ho T,Viswanathan H.Dynamic algorithms for multicast with intra-session network coding[J].IEEE Transactions on Information Theory,2009,55(4):797-815.

[10] 葛青,白光伟,沈航,等.无线网络链路质量感知的机会网络编码机制[J].计算机科学,2013,35(11):29-34.

[11] Chaporkar P,Proutiere A.Adaptive network coding and scheduling for maximizing throughput in wireless networks[C]//MobiCom’07 proceedings of the 13thannual ACM international coference on Mobile computing and networking.New York,2007:135-146.

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

[13] Madan R,Lall S.Distributed algorithms for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Wireless Communications,2009,5(8):2185-2193.

[14] 李繁,金明录.基于网络编码的车载移动网络数据传输优化[J].计算机科学,2013,35(3):170-174,214.

[15] Nagajothy M,Radha D.Network lifetime enhancement in wireless sensor network using network coding[C]//International Conference on Control,Automation,Communication and Energy Conservation,Perundurai,Tamilnadu,2009:1-4.

[16] Hosseinmardi H,Lahouti F.Multicast lifetime maximization using network coding:A cross-layer approach[C]//Proceeding of 24th Biennial Symposium on Communications,Kingston,ON,2008:1-4.

[17] Hong Y,Xu J,Jiang C.Lifetime maximization in wireless sensor networks with network coding[C]//Proceeding IEEE WiCom,Shanghai,2007:2527-2530.

[18] 韩莉,钱焕延.基于网络编码的无线多跳网络多路径机会路由算法[J].计算机科学,2014,36(5):122-125.

[19] Ding L,Wu P,Wang H,et al.Flow augmenting routing with network coding for lifetime maximization in wireless networks[C]//CHINACOM,Beijing China,2010:1-5.

中图分类号TP311.12

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.029

收稿日期：2014-06-09。李明，工程师，主研领域：中心机房及虚拟化技术，数据库与数据安全，网络通信技术。王睿，助理工程师。马睿，工程师。汪新建，工程师。童玲，助理工程师。