基于网络编码的机会网络路由综述

白琳　何欣　何明书

摘 要： 网络编码允许通信节点对接收到的消息进行编码处理，能够在一定程度上提高网络吞吐量，增强通信安全性。机会网络基于移动节点，面向动态拓扑结构组织、实现通信的特点，使其成为现代网络通信的发展趋势。但是机会网络投递率与消息副本数间的矛盾，严重制约着机会网络通信技术的推进。将网络编码技术应用到机会网络路由设计中，可以降低机会网络通信的消息副本数，提高投递率。详细描述了随机线性编码等几种网络编码在机会网络路由设计中的典型应用，并提出了网络编码在机会网络中的发展展望。

关键词： 网络编码； 机会网络； 随机线性编码； 投递率

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2016）11-25-04

The survey of opportunistic network routing based on network coding

Bai Lin1， He Xin1，2， He Mingshu1

（1. School of Computer and Information Engineering， Henan University， Henan， Kaifeng 475001， China； 2. School of Software， Henan University）

Abstract： Network coding allows the communication nodes to encode the received messages， which can improve the network throughput and enhance the communication security. The opportunistic network is based on the mobile node， and organization and implementation of communication based on dynamic topology， which make it the development trend of the modern network communication. However， the contradiction between the delivery rate and the number of message copies seriously restricts the advance of the opportunistic network communication technology. The application of network coding technology in the routing design of opportunistic network can reduce the number of message copies and improve the delivery rate. This paper describes the typical application of network coding， such as random linear coding and so on， in the routing design of opportunistic network， and puts forward the development prospect of network coding in the opportunistic network.

Key words： network coding； opportunistic network； random linear coding； delivery rate

0 引言

网络编码概念起源于R.Ahlswede等人于 2000年发表在IEEE trans-IT上的一篇题为“网络信息流”的文章。网络编码[1]是指对于在网络中传播的消息，数据传输节点对其不再仅仅执行存储转发，而是可以对接收到的消息进行编码与译码的处理，使得单次传输的信息量增大，可以提高整个网络的性能，进而提高数据传输效率。

根据节点对消息执行不同的操作处理，网络编码可分为两种：①网络节点对消息的处理，有线性网络编码和非线性网络编码；②网络节点对消息编码系数的处理，有随机性网络编码和确定性网络编码。网络编码采用“存储-编译码-转发”的方式进行数据的传输，在机会网络[2]中，通信节点的存储、携带、转发消息为网络编码的实现提供了极大的便利条件，因此在共享输出链路的网络环境下，结合适当的网络编码方案对机会网络吞吐量的提升、网络性能的优化、传输效率的提高等，都提供了良好的基础。本文介绍几种结合网络编码的路由算法在机会网络中的应用。

1 主动异或创建编码机制

机会网络路由传输算法中的Epidemic路由机制在节点相遇的过程中操作如图1所示，网络中节点A、B、C相遇后互相交互维护概要向量，然后再发送Request请求，最后进行数据传输。基于Epidemic路由传输的基本思想是复制转发，通过这种传输策略会使网络中存在大量消息副本，虽然可以提高消息到达目标节点的概率，但是这种操作会增大网络负担消耗网络资源。在基于网络编码的Epidemic[3]机制中，为了节省数据传输过程中节点间的Request请求在节点B处主动设置异或创建编码操作。网络中的三个节点处于同一个连通域内时如下图2所示，当节点B收到一个节点的SV后并不立马发送节点所需数据，而是在设定的一个周期T内对相继到达的A、C节点进行统一处理。首先发送统一处理后得到的数据分组集合MA、MC，对A、C都需要的数据进行多播处理，将A和C中剩余分组逐一提取并进行异或编码，然后将编码分组多播给A和C，如果数据分组集合MA和MC中还有一个集合存在剩余分组则将这些分组单播给该集合对应的节点。通过引入主动异或网络编码和多播可有效减少路由开销和传输时延，通过取消Request控制分组的发送进一步提高了传统的Epidemic路由投递率。

2 随机线性网络编码机制

结合引言的介绍，再针对当前随机线性网络编码技术的应用，本节主要介绍以下几种编码机制：RLC（Random linear coding）-Epidemic 机制、HubCode 机制、DSNC 机制。

2.1 RLC（Random linear coding）-Epidemic机制

RLC-Epidemic机制[4-5]是一种基于随机线性网络编码的数据转发机制[6]。该算法能够提高机会网络数据传输的可靠性，其原理为：网络中的传输节点用其副本消息按照相应规则进行编码处理，产生一组新的编码数据包，接着再次按照同样的数据转发方式转发出去。具体操作为：当节点a和节点b在某一时刻相遇，节点a向节点b传输数据，在其相互发送自身携带的概要向量中，b收到a发来的编码系数矩阵，与自身缓存中的编码系数矩阵进行比较，判定是否线性相关。若相关，则终止此次通信。若不相关，则接收节点a发送的编码后数据，并将接收到的编码后数据与自身存储的数据副本重新按照已定的编码规则进行编码，形成新的编码矩阵并存储。采用这种机制进行编码传输，网络中会存在大量的编码节点一定程度上会耗费网络资源。

2.2 HubCode机制

S. Ahmed针对现有的路由算法在全网泛洪传输编码包中所带来的网络开销大等问题，在2011年提出了Hubcode算法[7]。该算法是在网络中选取有限个数节点作为编码节点，其核心思想为：利用网络中编码节点作为网络数据的传输桥梁，使数据的转发具有针对性，减少节点的平均转发次数，降低了网络开销。算法主要传输步骤为：①源节点发送数据到hub节点（即hub节点就是编码节点，下文用hub表示）；②hub节点将发往同一目的节点的数据编码，并在所有的hub节点中泛洪编码后数据，直到遇到目的节点，完成编码后数据的投递；③目的节点在收到足够多的编码数据后恢复原始数据。

Hubcode编码机制的主要操作流程如图3所示，编码节点A编码系数矩阵中包含有已编码包F1和接收到新的原始数据X3，到达同一目标节点的编码节点A遇到网络中的编码节点B，B中的编码系数矩阵CV={idX1：α3α1，idX2：α3α2，idX3：α4}两编码节点相遇后交互编码系数矩阵，线性无关时传输给对方编码包完成相遇操作继续执行下一步操作直到遇到目的节点。

现有的Hubcode编码还有另外一种编码传输方式这个编码传输方式不同之处在于：①hub可以进行解码或存储得到的编码后数据，即hub可以获得本地数据；②其比较的不再是编码后系数矩阵，而是本地数据列表；③hub遇到目的节点时，可以转发编码后数据，也可以转发已解码的一条或多条本地数据。

针对Hubcode编码机制中编码节点相遇时广播编码系数矩阵进行交互造成资源浪费以及目标节点解码时可能存在较大延迟，现有文章[8]提出HLDA编码机制，该机制在编码节点处设置一个存放源数据包的集合I和由目的节点反馈过来的解码集合D，编码节点相遇后首先根据集合I来判断是否进行交互省去了广播编码系数矩阵的资源消耗。解码时，编码节点收到后集合D，对比自身的编码系数矩阵优先发送给目标节点缺少的数据包，方便目标节点及时进行解码处理。由此可减少数据传输延迟。

2.3 DSNC机制

现有基于网络编码的机会网络，数据转发机制难以不断编码类似流水线形式接收的数据，并且数据量大会导致节点携带更复杂的编码系数矩阵，增大网络传输开销。经仿真实验结果表明目的节点解码的时间复杂度为O（n3）。因此，D.Zeng等[9]提出了动态分段式网络编码数据转发机制（Dynamic Segmented Network Coding，DSNC）。该机制采用双缓冲数据传输方式，DSNC机制的主要思想是对待传输消息进行分段编码传输，源节点发送完一段编码数据后，待收到目的节点反馈回来的确认消息包（确认消息即ACK（Acknowledgement），下文用ACK表示）后进行下一段数据的编码传输。以下给出该算法步骤。①准备阶段：源节点不断产生分段的数据并编码转发，直到接收到目的节点反馈的前一段的ACK。当源节点接收到前一段的ACK，或者当前段的大小达到预先设定值M，源节点将停止发送当前段的数据，进行下一步操作。②传输阶段：当编码节点相遇后，率先交换其数据包头信息，并且按照段的序号进行排列。若当前编码节点中存在不完全一致的数据消息，则先转发较小号段的数据，以保证目的节点能够快速接收到该号段编码包并且能够快速进行解码操作。若编码节点的缓存中只存在单个段的数据，则先转发TTL（Time to live）较大的数据。③ACK反馈确认阶段：如果目的节点成功解码并获得了某个段的数据，则将ACK反馈到源节点。当且仅当目的节点接收到的数据包个数等于段的大小时，即可以成功解码出原始数据。采用该机制可以有效解决大数据传输问题，降低传输时延，提高消息投递率。

3 展望

本文概述了目前现有的几种基于网络编码的机会网络路由算法。实验结果表明，采用随机线性网络编码方法能有效降低网络中数据副本的数量并且能够提高网络投递率降低传输延迟，进一步提升机会网络在实际应用中的优势。结合网络编码的机会网络路由还存在很多亟待解决的问题：

⑴ 编码节点自身的资源消耗问题；

⑵ 如何将网络编码带来的网络开销和改善网络性能之间找到一个较好结合点；

⑶ 如何进一步降低网络编码的复杂度；

⑷ 目标节点接收到的编码包能否保证立马解码；

⑸ ACK消息如何及时传输给源节点等这些问题仍需进一步研究。

总之，随着网络编码技术与机会网络的结合，机会网络路由技术将会迈入新的发展阶段。

参考文献（References）：

[1] Ahlswede R， Cai N， Li S Y R， et al. Network information

flow[J].IEEETransactions on Information Theory，2000.46

（4）：1204-1216

[2] 熊永平，孙利民，牛建伟等.机会网络[J].软件学报，2009.20

（1）：124-137

[3] 任智，刘智虎，姚玉坤等.基于网络编码的机会网络高效路由

算法[J].通信学报，2013.9：16-23

[4] LIN Y， LI B， LIANG B. Efficient network coded data

transmissions in disruptiontolerant networks[A]//The 27thIEEE Conference on ComputerCommunications[C].（INFOCOM 2008）. Phoenix， AZ， USA： [s.n.]，2008：1508-1516

[5] FRAGOULI C， WIDMER J， LE B J Y. Efficient

broadcasting using networkcoding[J].IEEE/ACM Transactions on Networking，2008.16（2）： 450-463

[6] Qin Shuang， Feng Gang. Performance modeling of

network coding based epidemicrouting in DTNs[A].//Wireless Communications and Networking Conference[C].

Shanghai， China： IEEE Press，2013：2057-2062

[7] Ahmed S， Kanhere S S. HUBCODE： hub-based

forwarding using network codingin delay tolerant networks[J]. Wireless Communications and Mobile Computing，2013.

[8] 陈曦.基于网络编码的延迟容忍网络路由算法研究[D].重庆

邮电大学硕士学位论文，2015.

[9] Zeng Deze， Guo Song， Jin Hai， et al. Dynamic segmented

network coding for reliabledata dissemination in delay tolerant neworks[A].//IEEE International Conference onCommunications[C]. Ottawa， Canada： IEEE Press，2012：63-67

[10] 陶少国，黄佳庆，杨宗凯等.网络编码研究综述[J].小型微型

计算机系统，2008.29（4）：583-592

[11] 唐东明.网络编码关键问题研究[D].电子科技大学博士学位

论文，2013.

[12] 杨军.网络编码的若干关键问题研究[D].华中科技大学博士

学位论文，2013.

[13] Li S Y R， Yeung R W， Cai N. Linear Network Coding[J].

IEEE Transactions on Information Theory，2003.49（2）：371-381

[14] C.-C. Wang and N. B. Shroff， “Pairwise Intersession

Network Coding on Directed Networks，” IEEE Trans[J]. Inf. Theory，2010.56（8）： 3879-3900

[15] 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

[16] WEN H， REN F Y， LIU J， et al. A storage-friendly routing

scheme in intermittently connected mobile network[J].IEEE Transactions on Vehicular Technology，2011.60（3）：1138-1149

[17] Zeng D， Guo S， Jin H， et al. Dynamic segmented network

coding for reliable data dissemination in delay tolerant networks[A].// IEEE International Conference on Communications[C]. IEEE，2012：63-67

[18] Zhang X， Neglia G， Kurose J， et al. On the Benefits of

Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[A]// International Symposium on Modeling and Optimization in Mobile， Ad Hoc and Wireless Networks[C]，2006：1-7

[19] Yao J， Ma C， Wu P， et al. An Opportunistic Network

Coding Routing for Opportunistic Networks[J]. International Journal of Parallel Programming， 2015：1-15