无线Ad hoc网络中一种基于网络编码的协同MAC协议

李 楠 戚进勇 蔡跃明 程乃平

①(解放军理工大学通信工程学院 南京 210007)

②(总装备部陆装科订部 北京 100009)

③(装备指挥技术学院 北京 101416)

1 引言

协同通信利用无线信道的广播特性产生空间分集，可以显著地提高系统性能和链路可靠性[1]。在多数具有自动重传请求(ARQ)机制的协同MAC协议中，当直传出现错误时，中继节点用来转发源节点的数据分组。但是，这种协同转发需要中继节点做出较大的牺牲。中继节点需要贡献部分带宽去帮助其它节点发送数据分组，却不能处理自己要发送的数据分组。尤其是在基于二进制指数退避的IEEE 802.11协议中，帮助其它节点发送数据将增大中继节点的退避窗口，降低中继节点接入信道的概率。所以，从中继节点的角度出发，帮助其它节点发送数据会降低自己的性能，是不利于自己的一种行为，这称之为协同传输中的中继低效率问题[2]。

如何解决上述的问题，我们进而想到如果中继节点既能转发源节点的数据，又能同时发送自己的数据，协同传输中的中继低效率问题不就迎刃而解了吗。但是要做到上述这点，节点必须具有将两个或者多个数据包融合，并且在接收端解析的能力，而网络编码恰好可以实现这一想法，给我们提供了一个解决协同传输中的中继低效率问题的有效途径。

网络编码理论是网络信息论领域的一项重要突破，其由Ahlswede等人[3]于2000年提出，并迅速成为研究热点，给信息论与通信技术、计算机网络和密码学等领域带来了深远影响。一直以来，网络通信皆采用存储转发机制以传输数据，数据流被当成不可融合的实体流加以存储转发，而网络编码技术指出数据流的本质是信息流，允许信息流在网络节点进行编码运算能有效提高网络的吞吐量。目前对网络编码的研究大多数集中在物理层(如误码率，分集度等)和信息论(如信道容量等)方面，结合MAC层的研究还非常少。文献[4]提出了一种利用中心控制机制来最优化网络编码的方法，从而达到了基于TDMA的MAC协议和网络编码的最佳结合。这种方法可以取得性能的巨大提升，但是它无法适用于分布式的Ad hoc网络。文献[5,6]提出了一种网络编码和MAC协议结合的方案，设计了一种机会的网络编码来提高系统吞吐量性能，但它的研究模型是双向中继信道模型，并不涉及协同传输中的中继低效率问题。

为了解决协同传输中的中继低效率问题，本文结合网络编码，跨层设计了一种新的协同MAC协议NCCMAC(Network Coding Cooperative MAC)。NCCMAC协议是一种分布式的协同MAC协议，适用于无线Ad hoc网络。它的主要思想是在需要协同传输时，让中继节点帮助源节点转发数据的同时也一起发送自己的数据，实现这一目的的途径就是采用网络编码。当中继节点也有数据要发送时，利用网络编码将源节点的数据和中继节点自己的数据融合在一起发送出去，中继节点在帮助了其它节点的同时也发送了自己的数据，解决了协同传输中的中继低效率问题，进一步提升了系统的性能。本文还在多跳网络中对衰落信道下的NCCMAC协议进行了性能分析，推导出了吞吐量性能表达式，并分析了网络节点数、多跳和信道质量对吞吐量性能的影响。

本文组织如下：第2节详细描述了NCCMAC协议；第3节对NCCMAC协议进行了建模和吞吐量性能分析；第4节是仿真结果和分析，NCCMAC协议分别跟802.11DCF协议和一般的协同MAC协议进行了性能比较，并分析了网络节点数、多跳和信道质量对吞吐量性能的影响；第5节对本文进行了小结。

2 协议描述

NCCMAC协议仍然以CSMA/CA的竞争方式接入信道，并且同样采用ARQ重传机制，传输的场景示意图如图1。如果在信道衰落或噪声的影响下，源节点S的目的节点D1没能正确接收源节点的数据分组a,D1将反馈NACK，告知它的中继节点R直传失败，需要启用协同传输。到这里，我们遇到了协同传输中的中继低效率问题，中继节点如果单纯的转发源节点的数据分组a将损伤自己的利益。我们的目的是在协同传输时，让中继节点R在帮助源节点S转发数据a的同时也可以给自己的目的节点D2发送数据分组b。NCCMAC协议采用网络编码的方法来解决这个问题，进一步提高系统的性能。

图1 传输场景示意图

NCCMAC协议的流程图如图2。若节点D1第1次接收数据包a错误，如果第2次收到一个采用网络编码融合的数据包，该数据包融合了数据a和数据b，这种情况下使用基本的网络编码是不能恢复出任何信息的，因为对基本的网络编码来说只有完整的数据才能正确解码。但是，文献[7]中提出的一种网络编码MIMO_NC可以解决这种问题。MIMO_NC是一种物理层网络编码，它将物理层的纠错码和基本的网络编码相结合，即使在一个数据包出错的情况下，MIMO_NC依然可以对融合的数据包进行解码，MIMO_NC为解决协同传输中的中继低效率问题提供了基本保障。

如果源节点S到目的节点D1的信道质量非常差，网络编码MIMO_NC的正确解码率将非常低，网络编码将不再适用。为了避免这种情况的发生，节点D1在发送NACK之前将检查错误数据帧的SINR，如果这个值低于给定的门限值，就说明不适合使用网络编码，节点D1将在反馈的NACK中用1个比特标记出此问题，可以用NACK_flag表示，不适合使用网络编码时flag为0，反之为1。在flag为0时，NCCMAC协议将退化成普通的协同MAC协议，通过一定中继选择算法选出的中继节点将只转发源节点数据a。这里采用机会的退避算法来选择中继节点，也就是让潜在的中继节点在规定的范围内随机的选择一个退避窗口进行退避(潜在的中继节点为听到NACK分组并且之前正确接收了数据a的节点)，率先退避到0的节点将成为中继节点帮助源节点重传数据分组。在flag为1时，NCCMAC协议可以采用网络编码来进一步提高系统的性能。如果中继节点本身也有数据分组b要发送，它将通过网络编码，将源节点的数据a和自己的数据b融合在一起发送出去。具体实施方法如下：

中继节点在退避到0后将广播RRTS(Relay RTS)分组，RRTS分组主要有两个作用：一是告知自己中继节点的身份，其它潜在的中继节点听到RRTS分组后将不再退避；二是中继节点与它的目的节点进行信息交互。中继节点的目的节点有可能是源节点S或S的目的节点D1，也有可能是其它节点，需要分情况讨论：

(1)如果中继节点的目的节点是源节点S的目的节点D1。D1收到RRTS分组后，将反馈RCTS分组，这里节点R和节点D1交互RRTS/RCTS分组的意义在于减小多中继节点冲突对系统性能的影响。多中继节点冲突是指多个潜在的中继节点同时发送了分组而导致冲突发生的情况。在这种情况下，如果R收到NACK分组后直接发送数据，就会严重影响系统的性能，而通过交互RRTS/RCTS分组可以将这种影响降至最小，即使发生了冲突也只是付出了很小的代价，对系统性能不会造成太大的影响。目的节点接收完融合的数据之后，将反馈两次ACK/NACK分组，第1次是对源节点数据分组a的反馈，第.2.次是对中继节点数据分组b的反馈。

(2)如果中继节点的目的节点是源节点S。节点R同样要和源节点S交互RRTS/RCTS分组来减小因多中继节点冲突对系统性能的影响。节点D1在接收完融合的数据后反馈ACK/NACK分组，随后源节点S也将反馈ACK/NACK分组。

(3)如果中继节点的目的节点是其它节点D2。节点D2收到RRTS分组后，如果之前节点D2也正确地接收了源节点的数据分组a，它将能够对节点R通过网络编码融合后的数据进行解码，节点D2反馈RCTS分组告知节点R可以使用网络编码对数据进行融合，节点R将可以在转发源节点数据的同时发送自己的数据。如果节点D2之前没有收到数据分组a，它将不能对融合的数据进行解码，节点D2将反馈NCTS分组告知这一情况，在这种情况下，NCCMAC将退化成普通的协同MAC协议，中继节点R只转发源节点的数据a。这里节点R和节点D2交互RRTS/RCTS的目的在于确定中继节点是否可以使用网络编码对数据a和b进行融合。在接收完数据后，节点D1和D2分别反馈ACK/NACK。

为了尽可能地利用网络编码来解决协同传输中的中继低效率问题，我们让有数据发送的潜在中继节点的优先级高于没有数据发送的潜在中继节点，具体的方法是使有数据发送的潜在中继节点的中继退避窗口更短，使它成为中继节点的概率更高。

图2 NCCMAC协议流程图

3 建模与分析

本节将对在2维Markov退避模型的基础上，加入网络编码和协同机制，并在多跳的网络中对NCCMAC协议进行建模和分析。

3.1 网络模型

考虑一个由n个节点组成的全分布式的无线多跳网络。假设网络中节点的缓存器中总是有数据发送，也就是说网络处在饱和状态。其中每个节点仅配备单天线，工作在半双工模式。节点的数据分组长度相等，包括L个数据比特。分组在服从瑞利平坦衰落的信道中传输，接收节点采用最大比合并(Maximal Ratio Combiner,MRC)方式接收。信号调制方式为 BPSK，则接收机接收k分支调制信号的平均误比特率(Bit Error Rate,BER)可以通过下式计算得到[8]

3.2 吞吐量性能分析

在单跳网络中可以假设隐藏终端问题是不存在的，但是在多跳网络中，隐藏终端是不能不考虑的问题。源节点在发送分组时有两种情况会发生冲突：(1)至少有一个源节点的邻节点也发送了分组。(2)至少有一个目的节点的邻节点发送了分组。第(2)种情况就会发生隐藏终端问题。设nn为源节点的平均邻节点数(除去接收节点)，为在发送节点传输范围之外，但在目的节点传输范围内的平均节点数，实际上就是隐藏终端的个数。在考虑了隐藏终端问题后，源节点发送分组时冲突的概率Pc为

其中τ为节点发送分组的概率，τ可以表示为[9]

其中m是最大退避次数，W0是最小退避窗口，P为节点发送数据失败的概率，考虑目的节点接收数据失败后重传一次的情况，P可以表示为

其中Pde和Pce分别为直传和协同传输的误码率，Pr为潜在中继节点发生冲突的概率。

设Ps为在至少有一个节点发送分组的条件下无冲突传输的概率。

在一个时隙内传输有4种情况：(1)信道空闲；(2)多个节点发送分组而导致冲突；(3)目的节点成功接收数据分组；(4)因为信道噪声或衰落，导致目的节点未能正确接收数据分组。下面对4种情况分别进行讨论。

(1)信道空闲 设σ为一个时隙长，则空闲的平均时长E[Tb]可表示为

(2)多个节点发送分组而发生冲突 设tx代表传送相对应分组的时长，比如，tRTS就表示传送RTS分组所需时长。所以节点发生冲突所耗费的时长Tc为

因此，单位时隙内发生冲突的平均时长E[Tc]为

(3)目的节点接收数据分组成功 设直传传输所耗时长为Tsdir，协同传输所耗时长为Tscoop，中继发生冲突后再传输所耗时长为Tccoop，数据分组长为Lbits，则

在式(11)中，Wr为中继节点退避窗口大小，(Wr+ 1)/2为中继退避所需的平均时长。还需注意的一点是，在使用网络编码融合两个数据包时，在每个数据包需要标记解码时需要的系数因子，一般为8 bit，两个数据包附加16 bit。所以在协同传输时，传数据分组时需要附加16 bit。从中也可以看到，在使用网络编码融合两个数据所带来的附加开销非常少，对系统性能的影响将极其微小。

专业人士对信息化的定义是信息化是从物资层面升华到抽象层面，在生活需要和具体运用中产生的物资信息描述。信息化是指以计算机为主体的一系列智能工具的价值运用，这种运用可以加速社会的发展，提高人们生活的质量。智能工具与传统工具不一样，它们不是单一的工具，而是具有系统性的整体工具体系。它们可以形成一个有密切关系的体系。并且信息化工具可以提升人们的思维方法、交流方法等各方面，让人类社会得到巨大的进步。

所以，单位时隙内成功传输的平均时长E[Ts]可表示为

(4)因为信道噪声或衰落，导致目的节点未能正确接收数据分组 设这种情况下直传传输所耗时长为Tedir，协同传输所耗时长为Tecoop，中继发生冲突后再传输所耗时长为Teccoop。在这种情况下所耗的时长与成功传输所耗的时间是相同的，所以有

则单位时隙内因为误码导致传输失败的平均时长E[Te]为

最后再来分析单位时隙内源节点传输的有效负载E[Tp]。在网络编码的作用下，单位时隙内可以由以前的传一个数据分组变为传输两个数据分组，所以有

其中Rrate为数据传输速率。所以，总的吞吐量Stotal为

在多跳网络中，从源节点的角度出发，为了得到有效的吞吐量性能，需要用平均路径划分总的吞吐量，图3为多跳时的传输场景，其中Tr为节点传输的最大距离，A'为隐藏终端可能存在的区域，则

图3 多跳传输场景图

源节点到目的节点的平均路径长z为[10]

其中ρ为网络密度，即单位面积内的节点数。设适合一跳传输的平均距离为Rc，节点一跳传输的平均距离为d，则

所以有效吞吐量性能Seffect为

4 仿真结果与分析

本节将对NCCMAC协议吞吐量性能进行仿真分析，并和IEEE 802.11 DCF协议和一般的协同MAC协议性能进行比较。考虑独立同分布的准静态瑞利衰落信道，且具有加性高斯白噪声。系统采用BPSK调制方式，有效负载长度均为1024 bit，数据的传输速率为1 Mbit/s，节点随机分布在Y×Y(m×m)的正方形区域内，设节点的最大传输距离为300 m，其它参数的选取参照文献[11]，如表1。

表1 仿真参数设置

4.1 网络节点数对吞吐量性能的影响

节点随机分布在600 m×600 m的区域内，信道的平均信噪比为10 dB，图4是NCCMAC协议与一般协同MAC协议和802.11 DCF协议的吞吐量性能比较图。从图中可以看到，采用协同机制可以较好地改善系统性能，而采用网络编码的 NCCMAC协议可以更进一步的提高系统性能，相对一般的协同MAC协议和802.11 DCF协议，NCCMAC协议的吞吐量性能分别提高了 23.54%和 41.86%。我们还注意到，随着网络节点数的增多，802.11 DCF协议的吞吐量性能增大到一定程度后基本不变，而采用协同机制的 MAC协议随着网络节点数的增多吞吐量性能略有减小，这是因为在协同传输中存在潜在中继节点冲突的情况，随着节点数的增多，潜在的中继节点的冲突概率会增大，但是这种冲突带来的影响较小，所以从图4中看到采用协同机制的MAC协议吞吐量会随着节点数的增多而略有减小。

4.2 多跳对吞吐量性能的影响

图5显示的是NCCMAC协议的吞吐量性能与网络规模关系图。取网络节点数为50，信道的平均信噪比为 10 dB，节点随机分布在Y×Y(m × m)的正方形区域内。从图中可以看到，NCCMAC协议的吞吐量是随着网络规模的增大而减小的。这是因为随着网络规模的增大，网络的平均跳数也随之增多，节点传输一个数据包所需的步骤也增加了，传输步骤的增加将导致吞吐量下降，所以吞吐量是随着网络平均跳数的增多而减小的。在Y=4 00m时，网络的平均跳数约等于1，在Y=8 00m时，网络的平均跳数约等于 2，随着网络规模的变大，网络平均跳数的增多，Y=8 00m时的吞吐量和Y=4 00m时的吞吐量相比减少了56.98%。

4.3 信道质量对吞吐量性能的影响

图6是不同信道的平均信噪比下，NCCMAC协议相比一般协同MAC协议的吞吐量性能增益图，节点随机分布在600 m×600 m的区域内。从图中可以看出，在所给参数条件下，当SNR=10dB时，NCCMAC协议相比一般的协同MAC协议能获得高达23.54%的性能提升。但是在信道条件稍好或稍坏的情况下，NCCMAC协议的吞吐量性能增益都会有所下降。这是因为在信道条件稍差时，经过融合的数据也会更容易出现误码，所以吞吐量增益会有所降低。但是在信道质量更好时，直传的成功率很高，协同传输的几率变小，从而采用网络编码的机会也变小，所以相比一般的协同MAC协议，NCCMAC协议的吞吐量性能增益也会有所降低。

图7是不同信道的平均信噪比下，NCCMAC协议相比802.11 DCF协议的吞吐量性能增益图，节点随机分布在600 m×600 m的区域内。从图中可以看出，在所给参数条件下，当SNR=5dB时，采用协同机制可以极大地提高吞吐量性能，几乎是802.11 DCF协议吞吐量性能的5.2倍。在信道质量逐渐提高时，这种优势略有下降，在SNR=10dB时，这种增益变为1.419，在SNR=15dB时，这种增益仅为1.087。这是因为随着信道质量的提高，直传的成功率较高，协同传输的作用变小了，它对系统性能的提升也就降低了。所以可知，信道质量越差，协同通信对系统性能的改善就越明显。

图4 吞吐量性能与网络节点数关系图

图5 NCCMAC协议吞吐量性能与网络规模关系图

图6 改变信道的平均信噪比，NCCMAC协议相比一般协同MAC协议的吞吐量性能增益

图7 改变信道的平均信噪比，NCCMAC协议相比802.11 DCF协议的吞吐量性能增益

5 结论

本文针对无线Ad hoc网络，提出了一种新的协同MAC协议——NCCMAC协议。NCCMAC协议将网络编码和协同机制相结合，解决了协同传输中的中继低效率问题。本文还在多跳网络中对NCCMAC协议进行了吞吐量性能分析。仿真结果表明，和802.11 DCF协议相比，采用协同机制可以大大提高系统的吞吐量性能。和一般的协同MAC协议相比，加入网络编码可以进一步提升协同MAC协议的吞吐量性能，它对协同机制是一种很好的补充。

[1]Laneman J N,Tse D N C,and Wornell G W.Cooperative diversity in wireless networks：efficient protocols and outage behavior.IEEE Transactions on Information Theory,2004,50(12)：3062-3080.

[2]Munari A,Rossetto F,and Zorzi M.On the viability of a cooperative network coding protocol in clustered networks.Proc.IEEE MILCOM,San Diego,Nov.2008：1-8.

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

[4]Sagduyu Y E and Ephremides A.On joint MAC and network coding in wireless Ad hoc networks.IEEE Transactions on Information Theory,2007,53(10)：3697-3713.

[5]Argyriou A.Wireless network coding with improved opportunistic listening.IEEE Transactions on WirelessCommunications,2009,8(4)：2014-2023.

[6]Argyriou A.Cross-layer and cooperative opportunistic network coding in wireless Ad hoc networks.IEEE Transactions on Vehicular Technology,2010,59(2)：803-812.

[7]Fasolo E,Rossetto F,and Zorzi M.Network coding meets MIMO.Proc.NetCod 2008,Hong Kong,China,Jan.2008：1-6.

[8]Goldsmith A J.Wireless Communications.New York：Cambridge University Press,2005：258-265.

[9]Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function.IEEE Journal on Selected Areas in Communications,2000,18(3)：535-547.

[10]Xu S,Papavassiliou S and Narayanan S.Layer-2 multi-hop IEEE 802.11 architecture：design and performance analysis.IEE ProceedingsCommunications,2004,151(5)：460-466.

[11]Liu Pei,Tao Zhifeng,Narayanan S,et al..CoopMAC：a cooperative MAC for wireless LANs.IEEE Journal on Selected Areas in Communications,2007,25(2)：340-354.