流媒体无线Mesh网中基于机会路由的网络编码
夏卓群1, 2，李庆华1
(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；
2. 长沙理工大学 计算机与通信工程学院，湖南 长沙，410114)
摘 要：
无线Mesh网络的链路吞吐量模型，利用确定性网络演算工具，得到无线Mesh网络节点数据积压的上界以及端到端数据流延迟和抖动的上界；设计满足流媒体服务质量的确定性网络编码(DNC)，提出ETC作为确定机会路由中编码节点的指标，在节点数据积压未达到上界时，编码节点采用网络编码，提高网络的性能；提出ETP作为机会路由中选择候选节点的指标，主要考虑端到端的延迟和延迟抖动确定接收数据的候选集，然后，在侯选集中选择ETC最大的节点进行编码。仿真结果表明：吞吐量在增加的同时，端到端的延时和抖动值下降。
关键词：
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2012)01-0202-06
Network coding based on opportunistic routing in streaming media wireless mesh networks
XIA Zhuo-qun1, 2, LI Qing-hua1
(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;
2. School of Computer and Telecommunication Engineering, Changsha University of Science and Technology,
Changsha 410114, China)
Abstract: Using a deterministic network calculus tool, the wireless mesh network nodes’ backlog upper bound, the end-to-end upper delay bound and the end-to-end upper delay jitter bound were derived, based on the existing link throughput model of opportunistic routing; and then a deterministic network coding (DNC) which meets the QoS of streaming media was designed. An expect transmission coding (ETC) considering the node’s backlog upper bound was proposed to a guide line which determines the coding nodes. In order to improve the performance, the encode nodes using network coding before the node’s backlog upper bound was exceeded. The represented expect transmission performance (ETP) considering the jitter and the end-to-end upper delay jitter bound was a guide line which determines the received candidate nodes. The data packets were encoded among the candidate nodes by the max ETC. Comprehensive simulations and results show that the throughput is improved, and the delay time and jitter of end to end are degraded.
Key words: wireless mesh networks; deterministic network coding; quality of service; opportunistic routing
随着无线流媒体服务如视频会议、IPTV、在线游戏等在Mesh网中不断增加，迫切需要无线Mesh网络提供高质量的流媒体服务，而目前无线Mesh网中的实时流媒体支持技术还有待发展[1]。因此，研究新技术满足流媒体无线Mesh的服务质量(Quality of service, QoS)很有必要。机会路由(Opportunistic routing, OR)是一种使无线Mesh数据传输的吞吐量得到显著提高的新技术[2]。但是，机会路由的实现需要复杂的调度来实现节点之间的协商。而利用网络编码[3](Network coding)技术，机会路由可以不需要复杂的调度协议，用一种简单和可行的方法实现。越来越多的文献将结合网络编码的机会路由技术应用到无线Mesh网络 中[4-10]。如Chachulski等[4]采用结合了网络编码的机会路由MORE协议，该路由协议能够比文献[2]中单独使用机会路由的EXOR协议获得更高的吞吐量。但是，MORE协议中一个编码的数据报文在传输时，其他数据报文不能发送。Koutsonikolar等[7]提出了XCOR协议，主要是研究将机会路由和网络编码结合应用到Mesh网络中，大幅度提高网络的吞吐量。文献[9]主要研究融合了网络编码的机会路由应用到WMNs中的反馈问题。Lin等[10]对MORE协议进行了改进，提出CodeOR协议同时传播多个编码段提高了网络性能，该协议还解决了复杂调度和当规模增大网络性能下降的问题。但是，CodeOR缺乏针对流媒体Mesh网络中的QoS系统的研究。综上所述，目前的文献缺乏针对流媒体的服务质量来设计基于机会路由的网络编码。针对以上问题，本文作者设计满足流媒体Mesh网络的服务质量且适应机会路由的网络编码。采用确定性网络演算工具得到Mesh节点积压数据的上界，链路中数据流的延迟上界以及抖动上界，然后，据此设计基于机会路由的确定性网络编码(Deterministic network coding, DNC)。
1 相关知识
1.1 网络编码与机会路由
Ahlswede等[3]于2000年提出了网络编码概念。网络编码是一种融合编码和路由的信息交换技术，在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码信息融合，增加单次传输的信息量，提高网络整体性能。网络编码在提高网络吞吐量、改善负载均衡、增强网络鲁棒性等方面均显示出其优越性。
机会路由能够在无线链路信号不好时为Mesh网络带来高吞吐量，在数据传输时其无须寻找一条完整的传输路径，每通过一跳传输，数据包就越“接近”目标节点, 每一跳的传输通过无线传输的广播性来提高传输的成功率[2]。机会路由有效地提高了传输稳定性，非常适合于多跳、高丢包率的无线Mesh网络。
1.2 网络演算
由Cruz等开创和发展起来的确定性网络演算(Deterministic network calculus)是一种对性能边界进行定量分析的新工具[11]，利用它可以分析网络队列缓冲区大小、延迟以及延迟抖动等分组交换网络的基本属性[11-13]。
命题1[11] (积压数据上界)假定一个数据流被到达曲线α限制，通过一个提供服务曲线β的系统时，任意时刻的积压数据R(t) -R*(t)满足：
(1)
命题2[11] (延迟上界)给定一个流，进入系统时被到达曲线α(t)约束，通过系统时系统提供服务曲线β(t)，在一个任意时间，延迟d(t)满足下式：
(2)
其中：
也称作曲线
和
之间的水平偏差。
命题3[11] (串联节点服务曲线)系统1和系统2串联后提供的总服务曲线β为系统1提供的服务曲线β1和系统2提供的服务曲线β2的最小加卷积，即
(3)
定理1[13] (节点到达曲线)为保证更准确的QoS性能上界，对于服从参数为(σ, ρ)的漏桶管制的无线网络节点，其到达曲线可以表示为：
(4)
其中：
为流经无线网络中第i个节点的数据分组的字节数；ρ为数据流的最大上限速率。
定理1可根据文献[11]中关于数据流到达公式
(5)
证明。其中：
为数据分组的到达时间偏差容限且满足0≤≤TE；TE为数据分组期望到达的时间间隔。
1.3 网络传输模型
图1所示为网格Mesh拓扑结构，其中节点之间的干扰模型为一跳干扰，即2个节点之间若不相邻，则它们互不干扰。图1中的黑白节点之间轮流发送避免干扰。在使用机会路由传输数据包的Mesh网络中，网格拓扑下链路的吞吐量模型为[10]：
T≤
(6)
其中：K为网络编码块的大小；N为网络中节点数量；链路从源节点到目的节点的跳数h与
相关；p为链路传输成功的概率。K和p与节点数量N无关。
图1 网格拓扑
Fig.1 A grid topology
机会路由中使用ETX[14]中来确定候选节点，本文提出ETC和ETP来确定候选节点的编码节点。
2 确定性网络编码的研究与设计
这里首先利用链路吞吐量模型在确定性网络演算中的应用，得到无线Mesh网络的QoS性能，然后根据得到的服务质量性能设计确定性网络编码。
2.1 机会路由下无线Mesh网的性能确定
利用确定性网络演算工具得到Mesh网络中服务质量的性能上界，主要包括节点的积压数据上界、端到端数据流的延迟和抖动上界。
2.1.1 Mesh网络节点的积压数据上界
在网络演算中节点队列积压数据上界由该节点的到达曲线和服务曲线的最大垂直距离决定，由命题1和文献[13]定理3，可以得到节点的积压数据上界表达式为：
≤
(7)
其中：Ri具体到无线Mesh中就是数据流流经节点i到下一跳节点j的链路吞吐量，即Ri=thij。对于1个特定无线Mesh节点，参数ρ和Ri为定值，根据式 (5)可以得到；当
时，根据式(7)，最小。根据积压数据上界的表达式(7)和定理1，可以得到：
≤
(8)
在给定一条链路(i, j)中传输成功概率为pij，将式(6)代入式 (8)，可以得到无线Mesh任意节点i的积压数据上界模型：
≤
(9)
定理2 当网络节点积压数据未达到上界的时候，在网络中的节点采用线性网络编码可以达到流量上限。
证明：在网络中节点i积压的数据没有超过上界时候，数据没有丢失，若节点i采用网络编码来减少积压的数据，根据文献[15]中的定理3.3，网络能满足最小割最大流定理，此时网络中的流量达到了上限。
2.1.2 Mesh网端到端数据流延迟上界
假设
和
分别表示数据分组在节点i上的发射延迟以及传输延迟。根据命题2，可以得到以下 公式
≤
(10)
对于特定的节点i，当到达曲线的漏桶容量时可以保证更准确的延迟上界。
定理3 [13] (节点服务曲线)。为了保证更准确的QoS性能上界，对于为数据流提供参数为(R,T)的速率-延迟服务曲线的无线Mesh节点，其服务曲线为
(11)
根据命题2和命题3，式(11)变换可以得到以下公式：
≤
(12)
其中：
；thij为链路(i, j)的实际吞吐量。将式(6)代入式(12)得：
(13)
式(13)给出了无线Mesh中环境下数据流流经n个节点的延迟上界。
2.1.3 Mesh网端到端数据流延迟抖动上界
数据分组在传输过程中所产生的延迟抖动是由节点的积压数据所产生。因此，节点的延迟抖动上界可以表示为：
(14)
对于特定的节点i，当到达曲线的漏桶容量
时可以保证更准确的延迟抖动上界。无线Mesh网中数据流端到端的延迟由固定的分组发送延迟和节点数据积压所引起的延迟抖动(
)以及传输延迟组成，因此，得到下式：
≥
(15)
其中：
表示数据包在链路上的总延迟传输延迟，即=
；将式(13)代入式(15)得：
(16)
式(16)给出了无线Mesh网数据流流经n个节点的延迟抖动上界。
2.2 确定性网络编码的设计
根据Mesh网络中的服务质量性能来实现确定性的网络编码，主要包括2个方面：一是编码节点确定时要考虑节点的数据积压长度；二是机会路由中的候选节点集是编码节点的超集，而选择候选节点集要考虑服务质量的性能确定其优先级。采用机会路由技术的Mesh网络中节点的性能，确定网络中进行编码的节点，且设计节点编码的流程。
定义1 ETC(Expect transmission coding)用来标识编码节点的编码性能，利用节点的数据积压长度作为权值计算基准。
在确定编码节点的时候，本文重点考虑节点数据积压的长度，取节点积压数据的上界作为节点的数据积压长度大小，由定义1得到
，根据式(9)：
(17)
其中：pij为取节点i传输成功最小的概率；λ为与节点缓存区大小相关的系数。根据式(17)计算节点的队列积压长度，ETC越大，选取该节点进行编码的优先级越高。
编码节点进行编码的过程是首先节点监听所有的传输，当监听到一个数据报文时候，节点检查自己是否在数据报文的转发序列。若在，则节点检查数据报文是否包含了新的信息，若包含了新信息，则是一个新数据报文。然后，使用文献[16]中的高斯消去法来判断一个新数据报文是否线性独立于这个节点先前接到的这个批次的数据组信息。节点丢弃没有新信息的数据报文，存储它接收到的当前批次的新数据报文。最后在选择编码节点的时候根据ETC来确定编码的优先级，根据定理2，若节点的积压的数据还没有达到上界，则选取ETC最大值的节点进行编码操作，能使网络节点流量达到最大值。
3 基于机会路由的确定性网络编码
根据机会路由中源节点发送数据，选择转发候选集、到达目的节点的实现过程，将基于机会路由的确定性网络编码的设计实现主要有以下3部分。
3.1 源节点
源节点将发送的文件分成k组，即把文件划分为(A1, A2, …, Ak)，然后，Ai采用随机线性码[17]进行编码，假设每组Ai有n个数据报文，按照式(18)进行线性编码生成同等大小的编码报文
。
；j=1, 2, …, k (18)
式中：aij为由节点产生的随机编码的系数；Bj为从同一组数据组中的未编码数据报文。
是Ai组的编码向量。源节点附加一个机会路由的数据头到每一个数据报文。这个数据头包含了用于的编码向量，数据批次ID，源节点和目的节点的IP地址，以及能够参与转发数据报文的节点序列。源节点从当前的批次中保持发送编码的数据报文直到这个一组数据报文的所有批次都被目的节点确认，源节点继续发送下一批编码数据包。
3.2 转发候选集中编码实现
在机会路由中，候选节点的选取非常重要，是实现数据有效从源节点传输到目的节点的关键因素，而且编码节点集是转发候选集的子集。在流媒体网络中要着重考虑考虑服务质量，根据前面确定的网络中节点的性能，这里提出ETP，该指标包括了延迟、抖动性能，体现出在候选节点进行确定性网络编码。
定义2 ETP(Expect transmission performance) ETP(i)为节点vi通过此转发候选集F(I)发送数据包到目的节点vj (即流fj的数据包)的数学期望性能。
在2.1节得到了网络链路中形成链路的延迟和延迟抖动的上界，ETP(i)取这些链路中延迟和延迟抖动上界最小的链路节点，ETP(i)越小选中的可能性最大，满足下面的约束条件：
(19)
(20)
(21)
式(19)说明目的节点的ETP为0，式(20)指出根据ETP指标产生的转发候选集是一个偏序，ETP越小，对应的转发优先级越高；式(21)描述在计算ETP时节点i的延迟和抖动的权值分配，是延迟的系数，则链路延迟有严格的要求，则调高，增加延迟的比例；反之，
是抖动的系数，若链路的抖动比较大，则优先考虑抖动对节点的选择比例，调高。在候选节点中，根据求得的ETC进一步可以确定是否采用网络编码。从而使侯选节点的编码操作是在评估每条链路的服务质量后进行的，具有确定性，更适合于流媒体的传输。
若节点在转发的候选集中，则根据求得的ETC得到优先级最高的编码节点，编码节点对监听到的同一批次的数据编码报文进行随机线性混合。对编码的数据报文混合也是对单一的数据报文的线性混合。尤其是假设转发节点已经监听到编码数据报文为
，Aj是一个单一的数据报文。转发节点
对接收到的已编码的数据报文通过系数bi进一步编码，得到新的编码数据报文。由式(18)可以得到：
(22)
根据式(17)和(21)，可以得到在网络的中间节点还需要维护相关数据：网络编码块的大小为K，K由编码的数据包数量求得；传输的概率p在特定的无线环境中得到；路径跳数h可以通过相应的节点数目计算得到。此外，还有网络中数据流流经节点i到下一跳节点j的链路吞吐量Ri，通过给每个节点设置1个速率计算定时器，每隔一定时间计算得到。
3.3 目的节点
当目的节点接收到n(或大于n)份编码数据时，就可以采用矩阵转换的方式恢复出原始的n个报文。当收到k个编码数据(c i1, …, cij, …, cin)Ai时(其中，cij是由编码系数biaij形成)，构成一个可解满秩矩阵时，目的节点通过式(23)恢复出原始的k组个报文。如果目的节点接收的编码数据小于k时，可通过消息反馈机制通知上游节点对缓存的同组编码数据进行重编码操作并转发，直至目的节点能恢复出k个原始报文为止。
(23)
4 实验仿真
本文主要是考虑了无线Mesh网的服务质量来设计基于机会路由的网络编码,所以主要对比基于机会路由的确定性网络编码(DNC-OR)和文献[10]提出的基于机会路由的网络编码协议(CodeOR)的性能。仿真工具为NS2，网络拓扑采用如图1所示的网格拓扑，其中的相应参数设置是Mac协议为802.11b，队列是Drop Tail，其长度设置为2 000；采用全向天线传输；发送的文件为视频文件；数据包传输大小为1 024 byte；链路丢失率为0.02，与节点缓存区大小相关的系数
为0.5，
，
。
对网络中的吞吐量和延时性能进行了比较，结果如图2和3所示。从图2和图3可以看出：DNC-OR比CodeOR的网络性能要好；DNC-OR的吞吐量明显稳定增加，虽然编码对延时有影响，但是，增加延迟很小，并且由于在确定转发候选集的时候，考虑了延时等因素，所以，DNC-OR的延时不会对视频传输的性能产生大影响。其中，CodeOR的传输平均延时为27.386 ms，而采用DNC-OR的传输延时为25.052 ms。
图2 吞吐量的比较
Fig.2 Comparison of throughput
图3 延时的比较
Fig.3 Comparison of delay time
由于抖动性是流媒体传输的一个重要衡量指标，实验对传输的视频抖动指标进行了对比。采用CodeOR传输的数据包抖动(CodeOR-Jitter)的平均抖动时间为33 ms，抖动最大值为92 ms。采用基于机会路由的确定性网络编码进行传输，目的节点解码后的数据包抖动(DNC-OR-Jitter)的平均抖动值为23 ms，最大抖动值为81 ms，可见DNC-OR-Jitter性能比CodeOR-Jitter更好。
5 结论
(1) 利用确定性网络演算分析工具，得到无线Mesh的节点缓冲区队列积压数据上界和端到端延迟、抖动上界，提出ETC作为确定机会路由中编码节点的指标。在节点数据积压未达到上界时，采用网络编码提高网络的性能；提出根据端到端的延迟和延迟抖动得到的ETP指标确定机会路由中接收数据的候选集。
(2) 对提出的基于机会路由的确定性网络编码进行仿真，结果表明吞吐量在增加的同时，端到端的延时和抖动性下降。
参考文献：
[1] Akyildiz I F, Wang X D, Wang W L. Wireless mesh networks: a survey[J]. Computer Networks, 2005, 47: 445-487.
[2] Biswas S, Morris R. ExOR: Opportunistic multi-hop routing for wireless networks[C]//ACM SIGCOMM 2005. Philadelphia, PA, USA, 2005: 133-144.
[3] Ahlswede R, Cai N, Li S R. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.
[4] Chachulski S, Jennings M, Katti S, et al. Trading structure for randomness in wireless opportunistic routing[C]//ACM SIGCOMM 2007. Kyoto, Japan, 2007: 169-180.
[5] Radunovic B, Gkantsidis C, Key P, et al. An optimization framework for opportunistic multipath routing in wireless mesh networks[C]//Proceedings of IEEE International Conference on Computer Communications. Phoenix, AZ, 2008: 2252-2260.
[6] Katti S, Katabi D, Balakrishnan H, et al. Symbol-level network coding for wireless mesh networks[C]//ACM SIGCOMM 2008. Seattle, Washington, USA, 2008: 401-412.
[7] Koutsonikolar D, Charlie Y, Wang C C. XCOR: Synergistic interflow network coding and opportunistic routing[C]// Proceedings of the ACM International Conference on Mobile Computing and Networking. San Francisco, CA, 2008: 2980-2989.
[8] Koutsonikolar D, Charlie Y, Wang C C. Paci?er: High- throughput, reliable multicast without “Crying Babies” in wireless mesh networks[C]//Proceedings of IEEE International Conference on Computer Communications. Rio de Janeiro, Brazil, 2009: 2473-2481.
[9] Koutsonikolar D, Wang C C, Charlie Y. Designing coded feedback for efficient network coding based opportunistic routing[C]//Proceedings of the ACM International Conference on Mobile Computing and Networking. Beijing, 2009: 1368-1381.
[10] Lin Y F, Li B C, Liang B. CodeOR: Opportunistic routing in wireless mesh networks with segmented network coding[C]// Proceedings of the IEEE International Conference on Network Protocols. Orlando, Florida, USA, 2008: 13-22.
[11] Leboundec J Y, Thiran P. Network calculus[M]. London, Britain: Springer Verlag, 2004: 1-263.
[12] 张信明, 陈国良, 顾军. 基于网络演算计算保证服务端到端延迟上界[J]. 软件学报, 2001, 12(6): 889-893.
ZHANG Xing-ming, CHEN Guo-liang, GU Jun. On the computation of end-to-end delay bound in guaranteed service by network calculus[J]. Journal of Software, 2001, 12(6): 889-893.
[13] 李庆华, 陈志刚, 张连明, 等. 基于网络演算的无线自组网QoS性能确定上界研究[J]. 通信学报, 2008, 29(9): 32-39.
LI Qing-hua, CHEN Zhi-gang, ZHANG Lian-ming, et al. Deterministic upper bounds on QoS performance about wireless ad hoc network based on network calculus[J]. Journal of Communications, 2008, 29(9): 32-39.
[14] de Couto D S J, Aguayo D, Bicket J, et al. A high-throughput path metric for multi-hop wireless routing[C]//Proceedings of the ACM International Conference on Mobile Computing and Networking. SanDiego, California, USA, 2003: 134-146.
[15] Li S Y R, Yeung R W, Cai N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.
[16] Kortter R, M?Edard M. An algebraic approach to network coding[J]. IEEE Transactions on Networking, 2003, 11(5): 782-795.
[17] Ho T, M?Edard M, Koetter R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413-443.
(编辑 杨幼平)
收稿日期：2011-02-15；修回日期：2011-04-27
基金项目：国家自然科学基金资助项目(60873082，61073186，61073104，60903058)；中国博士后科学基金资助项目(20090451108)；湖南省科学技术厅科技计划(2011FJ3237)
通信作者：夏卓群(1977-)，男，湖南益阳人，博士研究生，副教授，从事网络计算与分布式研究；电话：13975803985；E-mail: xiazhuoqun@tom.com
摘要：采用机会路由下无线Mesh网络的链路吞吐量模型，利用确定性网络演算工具，得到无线Mesh网络节点数据积压的上界以及端到端数据流延迟和抖动的上界；设计满足流媒体服务质量的确定性网络编码(DNC)，提出ETC作为确定机会路由中编码节点的指标，在节点数据积压未达到上界时，编码节点采用网络编码，提高网络的性能；提出ETP作为机会路由中选择候选节点的指标，主要考虑端到端的延迟和延迟抖动确定接收数据的候选集，然后，在侯选集中选择ETC最大的节点进行编码。仿真结果表明：吞吐量在增加的同时，端到端的延时和抖动值下降。
