基于网络编码的无线局域网多播MAC协议及性能分析

杨  林^{1, 2}，郑  刚²

(1. 国防科技大学 电子科学与工程学院，湖南 长沙，410073；

2. 中国科学院 软件研究所 综合信息系统技术国家级重点实验室，北京，100190)

摘  要：针对现有IEEE 802.11协议无法提供可靠多播服务的缺陷，提出一种基于网络编码的无线局域网多播MAC协议MPNC。该协议对已有的ELBP协议进行了扩展，采用网络编码组传输模型发送多播数据。对于多播源节点，采用随机线性码对多播数据帧进行编码组合发送；对于多播接收节点，在接收的编码帧累积到一定数量后通过解码操作恢复出所需的原始数据。该方案有效减少了多播数据帧的发送次数，从而提高了无线带宽的利用效率。基于终端信道竞争的二维马尔可夫链模型，推导了差错信道下MPNC协议在网络饱和状态下的吞吐量理论表达式。最后，使用NS-2模拟器评估MPNC协议在不同信道误比特率和多播节点数目下的性能。仿真结果表明，MPNC比已有LBP和ELBP协议获得更优的吞吐量性能，并验证了理论分析的正确性。

关键词：MAC协议；多播；吞吐量；随机线性码

中图分类号：TN919；TP393          文献标识码：A         文章编号：1672-7207(2009)04-1008-07

A multicast MAC protocol for wireless LAN based on network coding and its performance analysis

YANG Lin^{1, 2}, ZHENG Gang²

(1. School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China;

2. National Key Laboratory of Integrated Information System Technology, Institute of Software,

Chinese Academy of Sciences, Beijing 100190, China)

Abstract: In order to conquer the deficiency of the multicast service provided by IEEE 802.11, a multicast MAC protocol called MPNC based on network coding was proposed for the wireless local area network (WLAN). By extending the previous proposed ELBP protocol, MPNC exploited network coding group to transmit multicast data frames. In multicast source node, the data frames were combined with random linear codes to transmit. In received nodes, the data frames were decoded after receiving enough combined frames. The scheme can effectively reduce the number of transmission and improve the throughput efficiency. Based on the 2-dim Markov chain model for the channel contention of terminals, analytic solutions were derived for the saturation throughput of MPNC under the error-prone channels. Finally, NS-2 simulator was used to evaluate the performance of MPNC under the condition of different bit error rates and the number of multicast users. The results show that MPNC can achieve better performance than LBP and ELBP protocols in terms of throughput. Further, the results validate the conclusion of the theory analysis.

Key words: MAC protocol; multicast; throughput; random linear codes

随着无线局域网的广泛部署和多播应用的兴起，设计高效可靠的多播MAC协议已成为当前的研究热点。目前，IEEE 802.11 DCF^[1](Distributed coordination function, 分布式协调功能) 已成为无线局域网MAC协议的事实标准，但该协议并未提供可靠的多播机制。由于采用普通的广播帧发送多播数据，缺少RTS-CTS信道预约和ACK确认机制的支持，现有的802.11DCF在多播应用中存在可靠性差、吞吐性能不佳等诸多缺陷^[2]。许多研究者对IEEE 802.11 DCF的多播性能进行了分析，并提出了多种改进方案^[3-8]。对多播组用户进行ACK轮询^[3]能有效解决多播通信的可靠性问题，然而，该协议需要周期性交换大量ACK帧，协议信令开销较大，因而，不适用于多播用户规模较大的网络环境。一些研究者提出使用“忙音”信道^[4-6]进行信道预约和差错控制可有效实现可靠的多播通信。虽然采用这些方案能取得较好的网络性能，但由于需要增加额外的信令信道，协议设计复杂。Kuri^[7]提出了一种简单可靠的多播MAC协议LBP，其核心思想是在源节点与多播群首用户之间进行RTS-CTS信道预约和ACK确认，而普通用户仅在数据接收失败的情况下反馈NAK消息产生碰撞，使源节点启动数据重传。该协议能提供可靠多播通信，实现简单，但要求所有用户必须同时正确接收才能开始下一帧的发送，因而，协议的带宽利用率较低。对此，Bao等^[8]提出了增强的ELBP协议，通过引入SEQ控制帧提前通知下一帧的序列号，使用户能预先判断出接收的重复帧，减少了不必要的重传。上述方案主要解决多播通信的可靠性问题，当处于多播用户较多和高损耗的无线网络环境下，方案的吞吐性能会因为数据帧的重传次数过多而急剧下降。在此，本文作者提出一种基于网络编码的MAC多播协议MPNC(Multicast protocol based on network coding)。它对现有的ELBP协议进行了扩展，采用网络编码组传输模型发送多播数据，当用户接收的编码帧累积到一定数量后可通过解码操作1次恢复全组数据。由于编码帧中包含了多个用户需求的信息，MPNC协议有效减少了数据帧的发送次数，可提供高效可靠的多播服务。结合经典的马尔可夫链性能分析模型，推导差错信道和饱和业务条件下MPNC的多播吞吐量理论表达式，并使用NS2模拟器比较LBP，ELBP和MPNC这3种协议的性能，验证MPNC的有效性。

1  网络编码基本原理

Ahlswede等^[9]提出了网络编码的概念，通过利用网络中间节点对信息进行编码处理，获得了有线网络的最大多播速率。网络编码的基本思想是鼓励网络中间节点对接收的数据进行合并处理，网络编码的基本原理如图1所示。图中，节点A和节点B通过中继R交换信息包X_a和X_b。若采用传统方法，则需要进行4次交换。而采用网络编码方法，中继R将X_a和X_b先进行异或编码，然后广播发送，则节点A能通过X_a⊕X_b⊕X_a解出X_b，同理，节点B也可获得X_a。在网络编码情况下，交换次数减少到3次，提高了网络的带宽利用效率。从示例中可以看出，网络编码的本质是通过增大节点的计算和存储资源以换取带宽利用率的提高。在网络编码技术被提出之后，研究者们开始考虑将它应用到无线网络中来提高无线广播^[10-11]和单播路由^[12-13]的性能。

图1  传统方法和网络编码方法的信息包交换

Fig.1  Information packet exchange for traditional approach and network coding

2  基于网络编码的多播协议(MPNC)

2.1  网络编码组传输模型

与传统逐帧发送的策略不同，MPNC使用网络编码组传输模型发送多播数据。其关键特征是将多个数据帧编为1组并利用随机线性码^[14]编码发送，使用户可以通过1次解码操作恢复出整组数据帧。随机网络编码是1种基于特定有限域的符号编码，每1个数据包可以看作由有限域F_q上的若干个符号构成的符号流，编码计算的加法和乘法操作均遵循有限域运算规则。网络编码组的编码帧产生过程如图2所示。设X₁, X₂, …, X_m为1组长度相等的多播数据帧，g_ij(1≤j≤m)为从有限域F_q中随机选取的编码系数，按照式(1)可得编码帧。

图2  网络编码组的编码帧生成示意图

Fig.2  Illustration of producing an encoding frame in network coding group

源节点将同一组多播数据帧X₁, X₂, …, X_m产生的编码帧标记为1个网络编码组，并依次发送。当用户接收了该网络编码组中的任意m个编码帧Y₁, Y₂, …, Y_m后，可通过式(2)给出的解码方法，解出原始数据帧X₁, X₂, …, X_m。由矩阵运算规则可知，这m组编码帧的编码系数g_ij(1≤i≤m)应该线性无关。上述过程称为网络编码组传输模型。

2.2  MPNC帧格式说明

为了支持网络编码组传输模型，MPNC协议对已有的ELBP协议进行了扩展^[8]，引入新的控制帧NCINFORM和EACK(Enhanced ACK)。图3所示为2种控制帧的帧格式说明。利用NCINFORM帧，用户

可以从GroupID域中获取编码帧的网络编码组标识，从Coefficient Vector域中提取解码计算所需的编码系数，并根据SEQ域判断接收的数据帧是否为重复帧。利用EACK控制帧，由源节点可以判断整个网络编码是否可以完成解码。EACK在现有802.11 ACK基础上扩展了1个新的解码标志域(1个字节)，并利用其中的1个Bit作为标志位。当标志位设置为“1”时，表示整个编码组已解码成功，可进入下一个编码组发送周期，当设置为“0”时，则表示单个编码帧接收成功。

(a) NCINFORM帧格式；(b) EACK帧格式

图3  NCINFORM和EACK的帧格式说明(单位：字节)

Fig.3  Format of NCINFORM and EACK frame

2.3  MPNC协议描述

与LBP协议类似，MPNC采用RTS-CTS握手和群首用户反馈机制。图4所示为协议的帧交互流程，其协议描述如下：

a. 源节点将网络层传递的多播数据包分割为长度相等的数据帧，存入发送队列。

b. 源节点首先进入数据发送阶段，从发送队列中提取m个数据帧X₁, X₂, …, X_m，并按照图4所示的帧交互流程逐个发送。在各数据帧发送之前，预先由源节点和群首节点进行RTS-CTS信道预约。在X_i的NCINFORM帧中，Coefficient Vector域被存入单位向量e_i (X_i可看作对X₁, X₂, …, X_m采用单位向量e_i编码的特殊编码帧)。当数据发送阶段出现数据帧传输失败的情况时，源节点不进行重传操作。

c. 当m个数据帧发送完毕后，源节点进入编码重传阶段，采用随机网络编码生成编码帧Y_i并发送。

d. 当群首用户接收到编码帧Y_i后，立即对数据帧进行校验。若接收错误，群首发送NAK帧给源节点；若接收正确，则进一步判断整个网络编码组是否可以解码；若可以解码，则EACK帧的解码标志位被设置为“1”，否则设置为“0”，并发送EACK帧给源节点。

e. 当普通用户接收到编码帧Y_i后，若接收正确，则用户不进行任何反馈；若发现数据出错或网络编码组解码失败，则用户立即发送NAK帧给源节点。

f. 当源节点接收到NAK帧或检测到多用户的NAK帧发生碰撞后，重传编码帧Y_i，直至所有多播用户均正确接收为止。

g. 当源节点接收到EACK帧后，若发现解码标志位设置为“0”，则节点继续发送新的编码帧Y_i+1；若发现解码标志位设置为“1”，则节点立即停止重传操作，并进入下一个网络编码组的发送周期。

图4  MPNC协议的帧交互流程

Fig.4  Frame exchange process of MPNC protocol

3  MPNC性能分析

3.1 模型与假设

a. 网络结构模型：由n-1个用户节点和1 个AP(接入节点)组成的单跳无线局域网，其中r(r≤n-1)个节点构成多播组，每个节点均能侦听到其他节点的发送，不存在隐藏终端或暴露终端。

b. 网络业务流量模型：用户节点向AP 发送恒定比特率数据，AP向r个用户发送恒定比特率多播数据，各节点的发送队列始终非空，网络处于饱和状态。

c. 数据传输模型：假设AP和多播用户间为无记忆的高斯白噪声信道，信道质量用误比特率(P_b)衡量。对于数据帧，同时考虑碰撞和信道差错引起的传输失败。对于长度较短的RTS和CTS等控制帧，仅考虑碰撞引起的发送失败。

3.2  多播用户信道竞争的马尔可夫链模型

根据IEEE802.11DCF协议的CSMA/CA机制，MPNC多播用户在信道竞争时采用离散时间避退算法，退避最小间隔为1个时隙。按照Bianch提出的分析框架^[15]，使用图5描述的二维Markov链模型描述多播用户的信道竞争过程。图5中，W₀为站点初始竞争窗口的大小，状态{s(t), b(t)}分别表示用户站点在时刻t的退避级数和退避时间计数器的取值。帧首次发送从退避级数0开始，计数器取值从[0, W₀-1]中等概率选取，若信道空闲1个时隙，则退避计时器以概率1递减；当计数器减为0后尝试发送数据帧，若出现帧传输失败，则每次失败后站点退避级数增加1，竞争窗口增大为W_j，计数器从[0, W_j-1]中等概率选取初始值并重新退避，当退避级数达到最大值k后，竞争窗口不再增加。由上述分析易知，s(t)的取值范围为  [0, k]，b(t)的取值范围为[0, W_j-1]，W_j=2^jW₀，j∈[0, k]。

图5  多播用户信道竞争的马尔可夫链模型

Fig.5  Markov chain model of channel contention for multicast users

设每个用户对任意1个时隙占用的概率为τ，根据文献[15]，可得出：则

通过求解式(3)和(4)，可以解出τ和p。

3.3  多播吞吐量分析

在MPNC协议中，网络编码组的平均传输延时包括数据发送和编码重传2部分时间。首先分析m个数据帧构成的网络编码组在这2个阶段分别耗费的平均传输时间T_d和T_r，然后，在此基础上求解MPNC的多播吞吐量S。假设：v 为MAC层的帧发送速率；P_i为剩余n-1个节点空闲的概率，P_i =(1-τ)^n-1；P_s为剩余n-1个节点中单个节点发送成功的概率P_s=(n-1)? τ(1-τ)^n-2(1-P_f )；P_e为剩余n-1个节点中单个节点发送出错的概率P_e=(n-1)τ(1-τ)^n-2P_f；P_c为剩余n-1个节点发送碰撞的概率P_c=1-(1-τ)^n-1-(n-1)τ(1-τ)^n-2；T_i为空闲时隙长度σ；T_s为数据帧平均成功传输时间，T_s=t_DIFS+t_RTS+t_CTS+(h_MAC+L)/v+t_ACK+3t_SIFS；T_c为数据帧平均碰撞时间，T_c=t_DIFS+t_RTS+t_CTS+t_SIFS；T_e为数据帧平均错误传输时间，T_e=t_DIFS+t_RTS+t_CTS+(h_MAC+L)/v+ t_ACK+3t_SIFS；T_avg为源节点退避计数器减1等待的虚拟时隙时长，T_avg=P_sT_i+P_eT_c+P_cT_e+P_cT_e；T_nc为编码帧平均传输时间，T_nc=t_DIFS+t_RTS+t_CTS+t_NCINFORM+(h_MAC+L)/v+ t_ACK+4t_SIFS。

定义1  编码组在数据发送阶段的平均传输时间为：

定义2  定义为编码重传阶段任意2个编码帧的发送间隔时间，为发送的编码帧数目，则编码组在编码重传阶段的平均传输时间为

。             (8)

考虑各多播用户的信道误帧率P_f均相等，当m充分大时，可近似认为各多播用户需重传的编码帧数目为mP_f ，根据文献[10]，可得重传阶段编码帧的发送次数为：

由于在编码重传阶段，编码帧除了RTS碰撞外，还必须考虑因信道错误引起的重传，则

定义3  将MPNC的多播吞吐量S定义为网络编码组的有效载荷长度和编码组平均传输时间的比值：

利用式(3)和(4)求解的τ 和p，并将式(5)~(10)代入式(11)中，可求得MPNC在差错信道和网络饱和状态下的多播吞吐量。

4  模拟与性能评估

使用NS-2模拟器评估MPNC协议，并与LBP和ELBP协议进行比较。仿真场景为30个终端和1个AP组成的无线局域网，MPNC协议采用有限域GF(2⁸)作为编码系数的产生范围，网络编码组的大小为20，NCINFORM帧长50字节，有效载荷L为1 000字节，其余物理层参数遵循802.11b标准^[1]。仿真中使用的主要参数如表1所示。测试主要包括不同的多播用户数目和信道误比特率条件下MPNC，LBP和ELBP协议的多播吞吐量对比以及MPNC吞吐量理论模型的  验证。

表1  仿真使用的主要系统参数

Table 1  System parameters for simulation

图6所示为不同多播节点数目和信道误比特率下的MPNC多播吞吐量。从图6可以看出，3种协议的吞吐性能随着多播节点数目的增加而减少，但MPNC协议的性能始终优于LBP和ELBP协议的性能。当信道误比特率逐渐增加时，MPNC协议的吞吐性能仍然具有较大的优势。这是因为当多播用户数目和信道误比特率增加时，各节点正确接收单个数据帧的时间延长，导致多播吞吐量下降。但MPNC利用网络编码技术将多个节点的数据帧进行组合发送，减少了帧发送次数，因而获得了较好的性能。图7给出了典型的信道误比特率条件下，MPNC的编码组传输延时和多播吞吐量随用户数目变化的性能曲线。从图7可以看出，在常规网络规模下(n=31)，随着多播用户数从5增加到30，MPNC的多播吞吐量略有下降，但降幅不超过20%，说明MPNC具有一定的可扩展性。此外，由图7还可见，理论分析结果与仿真数据结果比较符合，验证了所提吞吐量计算模型的正确性。

(a) P_b=10(-5)，不同多播节点数目下3种协议的吞吐量；

(b) r=20，不同信道误比特率条件下3种协议的吞吐量

1—LBP; 2—ELBP; 3—MPNC

图6  不同多播节点数目和误比特率下3种协议的吞吐量

Fig.6  Throughput of three protocols with different numbers of multicast nodes and P_b

(a) 不同多播节点数目和误比特率下MPNC的编码组传输延迟；(b) 不同多播节点数目和误比特率下MPNC的多播吞吐量

图7  不同多播节点数目和误比特率下MPNC性能

Fig.7  Performance of MPNC with different numbers of multicast nodes and P_b

由模拟测试可以看出，本文提出的MPNC协议相对已有的LBP和ELBP协议可以有效提高多播的吞吐量性能，尤其在多播用户数目较多，信道误码率较大的环境下优势愈显著。MPNC要求用户终端具有较强的计算能力进行网络编码组的解码计算，否则会影响数据传输的实时性。受到NS2模拟器的局限，仿真没有考虑网络编码组的解码延时。通过在Intel CPU 2 GHz，内存512 M的环境下编写VC程序，采用Gaussian消元法对m=20，L=1 000字节的网络编码组进行解码计算，得到平均解码延迟为0.35 s，代价是可以接受的。若采用Gauss-Jordan消元法使数据接收与解码计算同步进行，则解码延时可以被忽略。考虑到MPNC必须在编码帧积累到一定数量后才能解出原始数据，因此，该协议更适用于对数据完整性要求较高的文件分发、移动计算等多播应用。

5  结  论

a. 针对无线局域网的多播应用提出一种可靠多播MAC协议MPNC。该协议的核心思想是采用网络编码组传输模型将多个数据帧编码发送，使用户通过解码计算恢复出原始数据。仿真结果表明，在同等的网络环境和信道条件下，该协议的吞吐性能优于已有的LBP和ELBP协议，提高了无线网络的带宽利用  效率。

b. 基于终端信道竞争的马尔可夫链模型，推导了随机差错信道下MPNC协议在饱和状态下的多播吞吐量计算模型，并使用NS-2仿真进行了验证。仿真结果与理论计算较好地吻合，证明了所提模型的正  确性。

c. 结合无线局域网的多速率特性，进一步优化MPNC协议性能将是下一步的研究方向。

参考文献：

[1] IEEE. Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications[R]. IEEE Std 802.11-1999, 1999.

[2] Choi S, Choi N, Seok Y, et al. Leader-based Rate Adaptive multicasting for wireless LANs[C]//Proceedings of IEEE International Conference on Global Telecommunications Conference. San Jose: IEEE Press, 2007: 3656-3660.

[3] Sum M T, Huang L, Arora A, et al. Reliable MAC layer multicast in IEEE 802.11 wireless networks[C]//Proceedings of International Conference on Parallel Processing. Washington DC: IEEE Computer Society, 2002: 527-536.

[4] Gupta S K S, Shankar V, Lalwani S. Reliable multicast MAC Protocol for wireless LANs[C]//Proceedings of IEEE International Conference on Communications. San Jose: IEEE Press, 2003: 93-97.

[5] Chiu C Y, Wu E H, Chen G H. A reliable and efficient MAC layer broadcast (multicast) protocol for mobile ad hoc networks[C]//Proceedings of IEEE Global Telecommunications Conference. San Jose: IEEE Press, 2004: 2802-2807.

[6] Si W, Li C. RMAC: A reliable multicast MAC protocol for wireless ad hoc networks[C]//Proceedings of International Conference on Parallel Processing. San Jose: IEEE Press, 2004: 494-501.

[7] Kuri J, Kasera S K. Reliable multicast in multi-access wireless LANs[J]. ACM/Kluwer Wireless Networks Journal, 2001, 7(4): 359-369.

[8] Bao C W, Liao W J. Performance Analysis of reliable MAC layer multicast for IEEE 802.11 wireless LANs[C]//Proceedings of IEEE International Conference on Communications (ICC). San Jose: IEEE Press, 2005: 1378-1382.

[9] Ahlswede R, Cai N, Li S Y, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216

[10] Nguyen D, Tran T, Nguyen T, et al. Wireless broadcast using network coding[J]. IEEE Transactions of Vehicular Technology, 2009, 58(2): 914-925.

[11] 肖 潇, 杨路明, 王伟平. 高损耗无线网络中基于网络编码的广播重传策略[J]. 中南大学学报: 自然科学版, 2008, 39(6): 1291-1295.
XIAO Xiao, YANG Lu-ming, WANG Wei-ping. High loss wireless broadcasting retransmission scheme based on network coding[J]. Journal of Central South University: Science and Technology, 2008, 39(6): 1291-1295.

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

[13] Chachulski S, Jennings M, Katti S, et al. Trading structure for randomness in wireless opportunistic routing[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 169-180.

[14] Ho T, Karger D R, Medard M, et al. The benefits of coding over routing in a randomized setting[C]//Proceedings of of the International Symposium on Information Theory. San Jose: IEEE Press, 2003, 442-447.

[15] Bianch G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 1265-1275.

收稿日期：2009-03-05；修回日期：2009-06-02

基金项目：中国科学院创新基金资助项目(CXJJ-09-S03)；中国科学院支撑技术项目(K6GF735977, K6GF735979)

通信作者：杨  林(1981-)，男，湖南长沙人，博士研究生，从事网络编码与无线网络研究；电话：13581949840; E-mail: yanglin_nudt@yahoo.com.cn