文瑞涵 冯 钢

(电子科技大学通信与抗干扰国家重点实验室 成都 610054)

1 引言

在多跳无线网络中的许多重要应用，如文件分发、实时信息发布，电子文档分发、股票报价、视频会议等都需要网络提供一点同时对多点的(组)通信服务。利用组播(multicast)方式来支持组播通信的应用，可以大大提高资源利用率。特别在资源受限的多跳无线网络中，链路带宽受限且传输错误率较高，在这种情况下，组播网络利用率高、能节省发送者自身的资源、可扩展性较强的优点尤为凸显。因此，多跳无线网络中组播一直是国际上无线网络研究领域中的一个热点研究课题[1-3]。大多数的组播应用属于数据组播应用，要求恢复组播报文差错、所有组播接收者收到的报文数量一致、顺序一致、并具有一定实时性等，也即是说这些数据组播应用都需要可靠组播(reliable multicast)服务。如有接受者检测到有传输错误或数据丢失，需要某种机制来恢复这些错误或丢失。

根据丢失恢复机制，现有的协议可以分为两类：基于自动重播请求(ARQ)和基于前向纠错法(Forward Error Correction, FEC)的协议。基于ARQ协议中，丢失分组由源节点根据 ACK(ACKnowledgement)或NACK反馈请求进行重传，直到所有接收者都正确收到分组，使用 ACK反馈机制所有接受者必须发送 ACK到源节点，这加重了源节点负担，还可能造成“应答闭塞”(Feedback implosion)，因此在组播网络多采用NACK反馈机制，如PGM协议[4]和NORM[5]。RFC3208[4]中提出的PGM(Pragmatic General Multicast)协议是适用于有线网络的采用 NACK反馈机制的可靠组播协议，组播组成员检测到丢包后单播NACK。网元(路由器等中间系统)将 NACK沿组播路由反向地向上游转发，直到到达发送节点，并在收到NACK的节点上组播 NACK 确认信息(NCF)，防止重复的NACK请求。基于FEC的可靠组播协议在每个分组中嵌入冗余数据，丢失的分组用 FEC 重建。在以往的研究中，我们已经对基于层叠网络的可靠组播[6]、可靠组播网中丢包恢复对拥塞控制的影响[7]、以及可靠组播网络本地恢复的多会话缓存分割[8]等相关问题进行了研究。最近，文献[9]提出一种无线网络中可靠组播协同丢失恢复算法 CoreRM，基于树型路由(如MAODV)、NACK确认丢失，通过整个网络中的所有节点间相互协同提供丢失恢复，使得丢包在最小的范围内得到恢复。

利用网络编码来实现可靠组播是近年来提出的新思路。随着Katti等人[10]提出COPE这种实用的XOR网络编码策略用于减少多跳单播无线网络的传输次数之后，近年来出现很多基于COPE的网络编码重传策略。ER重传策略[11]使用XOR网络编码的重传机制代替COPE的MAC层重传，但ER采用遍历的方法构建编码树，计算复杂度高，只能用于理论分析。文献[12]中提出使用最小簇分割策略的网络编码重传方法，并在节点处存储需要重传的包，同时也考虑了重传包的再次丢失。但是，现有方案基本上是在有限域GF(2)中进行 XOR编码[10-12]，这种XOR编码机制有两个限制条件：(1)只能允许将不同的接收方的丢包编码到一起，但若采用随机线性网络编码，属于同一个接收方的丢包也可以进行编码；(2)寻找最优编码策略包是 NP困难的问题[13]，而使用随机线性网络编码(Random Linear Network Coding, RLNC)却没有这些限制。Chi等人[14,15]在文献中提出一种基于随机线性网络编码静态重传策略，算法的计算复杂度为O(M3)，其中M为接收节点的数量。但Chi等人关注的是线性无关编码向量的选择过程，并未将 NACK机制与划分“代”的恢复机制有效结合起来。

本文提出一种基于 G F(28)的 RLNC的可靠组播方案(NCRM)，将划分“代”的机制和NACK机制结合起来，只要节点收到的编码系数矩阵满秩，就可以解出编码包。在文献[16]中证明， 这种选取原则可以使得线性编码组合出现线性无相关的概率极大(约为0.99608)，完全具备有效性。本文的主要贡献是：提出一种新的高效多跳无线网络组播恢复机制，将划分“代”的数据包发送机制与NACK抑制机制结合起来，并对算法进行了数学建模分析，验证了模型的有效性。此外，我们还考虑了恢复节点也发生丢包的情况，恢复节点在第 1次收到NACK以后，用已知邻居数量计算出NACK退避时延，按照重传下限发送编码包，同时，恢复节点将不能帮助恢复的包序号携带在 m-NACK的比特向量中，立即向上游节点请求恢复，经过邻居恢复、多跳恢复和源端恢复，完成可靠组播过程。

本文在第 2节中给出 NCRM 的细节，在第 3节建立了节点恢复的齐次马尔科夫链数学模型，在第4节给出使用此模型进行数值计算和仿真结果。

2 基于网络编码的多跳无线网络可靠组播算法(NCRM)

2.1 算法概述

NCRM是依靠MAODV路由协议建立组播树，将划分“代”的机制和NACK抑制机制结合起来的算法。NCRM算法采用两种NACK：一种是组播组成员发送的头部携带原始丢包比特向量的NACK；另一种是组播树成员转发的m-NACK，由于存在恢复节点不能帮助请求节点恢复所有包的情况，恢复节点会筛选出 NACK的原始比特向量中能够恢复的数据包比特位，保留剩余不能恢复的比特位，生成新的丢包比特向量携带在m-NACK头部，发送给上游节点。节点只要位于请求节点的通信范围内，就可以成为恢复节点帮助完成数据包的恢复。在NCRM算法中所有节点都存储收到的数据包，恢复节点可以充分利用邻居节点缓存的数据包信息，帮助丢包节点用最少的跳数和 NACK完成数据包的恢复。

如图1所示，NCRM算法的重传恢复过程主要包括3个可能的丢失恢复阶段。(1)邻居恢复阶段。节点检测出来待恢复的“代”的比特向量不全为1，表明此“代”发生丢包，将此“代”的状态标识为Gen_Repairing，然后向邻居节点广播发送携带丢包比特向量的NACK。收到NACK的邻居节点帮助恢复这个接收节点恢复丢包。(2)多跳恢复阶段。收到NACK的邻居节点不能帮助恢复所有的丢包，则需要进入多跳恢复阶段。恢复节点将已经帮助恢复的那些包对应的比特位置为 0，若恢复节点的身份是组播树成员，则将剩余的向量复制到m-NACK的比特向量字段，立即发送给上游节点。中间节点不断重复此过程，直至到达某节点能够帮助恢复丢包比特向量中所有比特位为1的包。(3)源端恢复阶段。中间节点不能帮助恢复数据包，最终m-NACK会到达源端，表明从请求重传节点到源节点途经的所有节点都丢失m-NACK的丢包比特向量中比特位为1的数据包。发送节点需要重新组播这些丢包，完成源端恢复。

图1 NCRM算法的重传恢复过程

2.2 数据包存储和“代”状态转换策略

组播树成员或非组播树成员都对收到的不重复的数据包进行存储，假设所有节点都拥有无限大存储数据空间。每一个数据包具有全局唯一的包序号(pid)和“代”序号。发送节点在发送某一序号的数据包时，“代”序号等于 pid ModG,G为“代”的大小。每一个节点维护一张GenID列表，存储各个“代”对应的状态和接收比特向量。当组播组成员收到一个数据包，需要提取数据包中的“代”序号，并更新此序号对应的“代”的状态和接收比特向量。

节点首次收到k号“代”的数据包，查找GenID列表，发现k号“代”对应状态是“不存在”，则将状态更改成“待恢复”，同时将本次收到的包序号对应的比特向量位置1。节点持续接收属于k号“代”的数据包，则其状态停留在“待恢复”，直到首次接收到属于k+1号“代”的数据包，将k号“代”状态更新为“正在恢复”，此时存在两种可能：(1)k号“代”的数据包未发生丢失，则将k号“代”的状态转换为“恢复成功”，节点继续等待接收k+1号“代”的数据包，一直到接收k+2号“代”的数据包以后再进入k+1号“代”的恢复过程。(2)k号“代”发生丢失，若通过NCRM算法完全恢复了k号“代”的数据包后，则将k号“代”的状态更新为“恢复成功”，表示成功接收；否则k号“代”的状态仍为“正在恢复”。

图2 “代”状态转换图

需要指出的是，所有节点都维护GenID列表，但只有组播组成员才会因收到新“代”的包而触发NACK的发送。

2.3 NACK抑制策略

当组播网络中有多个组播成员丢失数据包，它们同时发送NACK请求，可能导致NACK风暴。NACK风暴会导致网络的瓶颈链路发生拥塞，甚至造成整个网络的瘫痪。因此，NCRM算法将NACK抑制与划分“代”的机制结合起来，以避免NACK风暴。MAODV协议本身没有NACK/ACK确认机制，NCRM算法需要使用MAODV路由协议邻居列表中邻居数量信息，因此将NACK作为MAODV路由协议包的一种在网络层进行处理。

NACK包头主要包括：数据包的“代”序号(nack_gen)，丢包比特向量(lost_bitvec)，原始发起NACK 的节点标识(initiator)和组播组的 IP地址(nack_maddr)。

网络中存在两种类型的NACK包：(1)组播组成员始发的NACK包。节点收到k+1号“代”的数据包以后，检查k号“代”的接收比特向量的比特位不全为1(表示k号“代”发生丢包)，而节点又是组播组成员，则向邻居节点广播initiator字段为本节点的地址的 NACK, nack_maddr为组播组的IP地址。(2)组播树成员转发的m-NACK包。恢复节点收到邻居组播组成员发送的NACK以后，考虑到可能存在恢复节点不能帮助邻居恢复所有包的情况(表明本节点也丢失其中的数据包，这种可能性随G的增加而增加)，则需要转发 m-NACK，将原来的NACK中已经成功恢复的向量比特位置0，再将剩余的丢包比特向量复制到 m-NACK的 lost_bitvec字段，进入多跳恢复过程。最坏的情况是NACK最终返回到组播组源节点，源节点重新在组播组广播丢失的数据包，完成源端恢复。

不同类型的节点在收到 NACK后会做出不同反应：(1)组播树成员：转发 m-NACK和尽可能地帮助恢复数据包。若首次收到某一序号“代”的NACK，则退避等待一段时间，等收到多个邻居发来的同一“代”的NACK以后，按照定理1的策略发送重传编码包。(2)非组播树成员：既不发送NACK，又不发送m-NACK，只是尽可能帮助发送重传编码包。它并没有邻居信息，收到NACK后不会退避等待，而是直接发送重传编码包。非组播树成员可能偷听到组播树成员转发的数据包，充分利用这些节点可以增大恢复重传包的可能性。

证明NCRM 方法选取的原则，是通过比较NACK比特向量中丢包比特位为1的个数Li，得到最大的丢包数Lj，恢复节点发送Lj个随机线性编码包。在M个邻居节点的编码向量矩阵中，Nj的未知变量个数最多，因此需要的用于增加编码向量矩阵秩的线性组合数目也是最多的。在文献[17]对随机线性网络编码的分析中，满足线性无关性的随机线性网络编码包，能使编码向量矩阵的秩增加 1，即丢包最多的接收节点Nj在接收到的编码包后，能够使得编码向量矩阵满秩，满足可解性条件。而在其他接收节点Ni(1≤i≤M,i≠j)，均能够获得大于未知变量个数的线性编码组合，同样满足使编码向量矩阵满秩的条件。因此，根据最大丢包数Lj发送随机线性网络编码包，可以达到重传目的。 证毕

3 NCRM算法的性能建模与分析

本节对NCRM算法进行建模与性能分析。考虑一个发送节点和多个接收节点的组播模型。需要用到的术语见表1。设随机生成的网络拓扑为G(V,E)，其中V是网络中所有节点构成的集合，E是由网络中能够相互通信的节点构成的边集。

表1 术语

由于NCRM算法包括3个恢复阶段：邻居恢复，多跳恢复，源端恢复，不同阶段经历的时延也不相同。只要节点在某个阶段恢复失败，就会进入下一个阶段的恢复过程。节点接收新的数据包后，更新长度为G的接收比特向量，其中0代表丢包，1代表成功接收。节点发送的NACK中携带的丢包比特向量长度也为G，其中1代表丢包，0代表未丢包。

定理2每个比特位{bi,i=1,2,3,…,G}都是取值空间为A={0,1}的随机变量，则由Gbit构成的接收比特向量序列{XG,G=1,2,3,…} 是齐次马尔科夫链。

证明接收比特向量序列是由G个比特构成的序列，而每个比特bi是取值空间为A={0,1}的随机变量，其中1代表成功接收，概率为p, 0代表丢包，概率为1-p。用xi表示bi1bi2bi3…biG-1biG比特向量序列，xi的取值空间Ω有2G种可数状态。发生丢包是相互独立同分布的，因此每一个比特的取值是相互独立同分布的，且他们构成的比特向量序列也是独立同分布的。

n时刻的接收比特向量转变成n+1时刻的接收比特向量只与n时刻的接收比特向量的取值有关，因此有对任意正整数G与取值∀x1,x2,…,xn,xn+1∈Ω，有

由此得证接收比特向量序列{XG,G=1,2,3,…}是齐次马尔科夫链。

同理可证，丢包比特向量序列{XG,G=1,2,3,…}也是齐次马尔科夫链。 证毕

下面计算NCRM算法经历 3个恢复阶段的概率，设组播组成员Ri发生丢包，向邻居节点请求重传，则丢包向量比特的状态空间Ω有 2G种可数状态。由于丢包比特向量和接收比特向量都是齐次马尔科夫链，任意时刻m的状态都可以用n时刻的绝对概率与状态转移矩阵Pk相乘得到，其中k=m-n。

取G=2，则状态空间为Ω={00,01,10,11}，邻居帮助恢复的一跳转移矩阵P为

得到的P是一个下三角矩阵。显然，可以找到一个概率分布π={1,0,0,0}，使得π=πP,π={1,0,0,0}为齐次马尔科夫链的平稳分布，说明Ti节点最终会停留在{00}状态，即成功恢复的平稳状态。

在n时刻，节点Ti的绝对概率为π(n)=(p2,p(1-p),p(1-p),(1-p)2)。经过邻居j跳恢复以后的概率分布为π(n+j)=π(n)Pj。

经过j跳邻居恢复成功的概率为

NCRM算法的包投递率为

平均恢复跳数为

平均恢复时延为

在第4节中，我们将使用本节提出的模型进行数值计算和计算机仿真，分析影响系统性能的因素，并验证模型的有效性。

4 NCRM算法的数值结果与仿真

本节利用仿真实验验证我们的分析模型并估计NCRM性能。仿真平台是 2.30版本 NS2。仿真场景随机分布16个节点在670 m×670 m的范围内，任意选取一个作为发送节点，通过固定码率流量生成器产生整个网络仿真的数据，数据包长为 210 Byte，发送速率为 12 kbps。仿真中使用MAODV组播路由协议作为路由层协议，802.11作为 MAC层协议。本文采用性能指标主要有包投递率、网络的吞吐量和平均丢失恢复时延。包投递率是指节点成功接收的包数占发送节点发送包数的百分比。平均吞吐量是指每个节点每秒接收的比特量。平均丢失恢复时延是指数据包发生丢失到数据包成功恢复的时延。

首先分析δ,DNACK和G对包投递率和平均恢复时延的影响。图3(a)和3(b)分别为式(5)计算出的理论与实际仿真平均恢复时延的比较结果和式(6)计算出的理论与实际仿真平均恢复跳数的比较结果。可以看出理论和仿真时延结果符合很好。图4(a)和 4(b)分别为不同DNACK的平均恢复时延和包投递率，DNACK使每个节点退避等待NACK的时间增加，总时延也增加，但是适当延长DNACK得到的好处是：恢复节点能在等待时间内收到更多的NACK，每次能帮助更多邻居恢复数据包，有效减少重传包的发送个数，避免网络拥塞。图5(a)和5(b)分别为取不同G的平均恢复时延和包投递率。NCRM算法将数据包划分成大小为G的“代”逐一进行恢复，因此G的选取直接影响 NCRM 算法的平均恢复时延。与DNACK的选取类似，G越大，节点每次帮助恢复的数据包越多，可以减少NACK和重传数据包的数量，从而增加包投递率。

图3 理论和仿真平均恢复时延、平均恢复跳数

图4 不同 DNACK 的平均恢复时延和包投递率

图5 不同G的平均恢复时延和包投递率

从以上分析可以看出DNACK和G都对包投递率和平均恢复时延有影响，DNACK和G的选取其实是对包投递率和平均恢复时延的折中。

图 6，图 7和图 8所示为发生丢包时 PGM、CoreRM和NCRM算法的性能对比。原有的PGM算法是NACK反馈机制的有线网络可靠组播协议，我们修改了 PGM 的有线部分，使它可以用于无线网络。可以看出，随丢包率的增加，3种算法的投递率和平均吞吐量都降低，NCRM算法的包投递率和吞吐量都是最高的。图8中NCRM算法的平均恢复时延远远小于CoreRM和PGM算法。主要有3个原因：(1)NCRM算法采用随机线性网络编码，在GF(28)域选取编码系数，比在GF(2)域编码更能利用潜在的编码机会。(2)NCRM 算法采用的 NACK机制不同，CoreRM和PGM算法的NACK是单个包的确认机制，而NCRM算法是对一个“代”的包的确认机制。划分“代”的机制降低了网络中NACK的数量，进一步减少网络拥塞。(3)NCRM算法没有CoreRM的单播恢复的过程，因为广播NACK可以充分利用不在组播树上的节点所拥有的有效包信息，而单播对网络链路的依赖性很大，如果单播恢复发生再次丢失，会导致恢复过程经历更大的时延。另外，不在组播树上的节点只参与重传编码包的过程，并不再次广播NACK包，以防止NACK风暴。

因此，NCRM算法能充分利用邻居节点存储的信息，在发生丢包的情况下仍然具有很高的包投递率(大于 92%)和网络吞吐量，同时保持很低的重传恢复时延。

图6 发生丢包情况下的包投递率

图7 发生丢包情况下的吞吐量

图8 发生丢包情况下的平均恢复时延

5 结束语

本文提出了一个适用无线组播网络的可靠组播丢失恢复算法 NCRM。NCRM 是基于随机线性网络编码和NACK机制，将数据包划分为“代”进行丢失重传的算法。 NCRM算法将NACK抑制策略和划分“代”的方式结合起来，有效避免了NACK风暴。算法的设计主要目的是充分利用邻居信息，用最少的跳数和最短的时延完成丢包恢复。本文还建立了NCRM算法的数学模型，分析了模型中影响性能的主要因素。通过仿真无线多跳组播网络环境，对比另外两种组播传输协议算法的性能，发现NCRM 算法的性能在相同仿真环境中可靠性要高于使用 XOR编码的恢复算法。我们计划考虑多个发送节点和不同数据发送速率的情况，设计出适合不同应用场景的算法。

[1]Shakkottai S, Liu Xin, and Srikant R. The multicast capacity of large multihop wireless networks[J].IEEE/ACM Transactions on Networking, 2010, 18(6): 1691-1700.

[2]Traskov D, Heindlmaier M, Médard M,et al.. Scheduling for network-coded multicast[J].IEEE/ACM Transactions on Networking, 2012, 20(2): 1-9.

[3]Niati R, Banihashemi A H, Kunz T,et al.. Throughput and energy optimization in wireless networks: joint MAC scheduling and network coding[J].IEEE Transactions on Vehicular Technology, 2012, 61(3): 1372-1382.

[4]RFC3208: PGM reliable transport protocol [OL]. http://www.hjp.at/doc/rfc/rfc3208.html, 2001.

[5]Internet Engineering Task Force(IETF)RFC. RFC5740-NACK-Oriented Reliable Multicast(NORM)Transport Protocol[S]. 2009.

[6]石曦, 冯钢, 张翼德. 无线 Ad-hoc网络中基于层叠网络的可靠组播协议[J]. 通信学报, 2010, 31(8A): 26-31.

Shi Xi, Feng Gang, and Zhang Yi-de. Overlay reliable multicast protocol in wireless Ad-hoc network[J].Journal on Communications, 2010, 31(8A): 26-31.

[7]Xie Feng and Feng Gang. The impact of loss recovery on congestion control for reliable multicast[J].IEEE/ACM Trnsactions on Networking, 2006, 14(6): 1323-1335.

[8]Yeung K L and Feng Gang. Cache partitioning for multiple sessions in local loss recovery of reliable multicast[J].IEE Proceedings-Communications, 2005, 152(6): 866-876.

[9]黄梦洁, 冯钢, 张翼德. Ad hoc网络基于协同的可靠组播丢失恢复算法设计[J]. 电子与信息学报, 2010, 32(9): 2065-2071.

Huang Meng-jie, Feng Gang, and Zhang Yi-de. CoreRM:cooperative loss recovery for reliable multicast in Ad hoc networks[J].Journal of Electronics&Information Technology,2010, 32(9): 2065-2071.

[10]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.

[11]Rozner E, Lyer A, Mehta Y,et al.. ER: efficient transmission scheme for wireless LANs [C]. Proceedings of CoNext'07, New York, 2007: 78-90.

[12]Zhan C, Xu Y, Wang J,et al.. Reliable multicast in wireless networks using network coding[C]. IEEE 6th International Conference on MASS, Macau, 2009: 506-515.

[13]Rouayheb S Y, Chaudhry A R, Alex S,et al.. On the minimum number of transmissions in single-hop wireless coding networks[C]. IEEE Information Theory Workshop,Tahoe City, CA, 2007: 120-125.

[14]Chi Kaikai, Jiang Xiao-hong, Ye Bao-liu,et al.. Efficient network coding-based end-to-end reliable multicast in multi-hop wireless networks[C]. Proceedings of the 15th Asia-Pacific Conference on Communications, Shanghai,2009: 32-35.

[15]Chi Kai-kai, Jiang Xiao-hong, Horiguchi S,et al.. Network coding-based reliable multicast in wireless networks[J].Computer Network, 2010, 54(11): 1823-1836.

[16]Dulman S, Nieberg T, Wu J,et al.. Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks[C]. Wireless Communications and Networking Conference(WCNC), New Orleans, Louisiana USA, 2003, 3: 1918-1922.

[17]Ho T, Médard M, Shi J,et al.. On randomized network coding[C]. 41st Annual Allerton Conference on Communication Control and Computing, Monticello, 2003, 1:11-22.