基于网络编码的TDMA移动自组网MAC协议设计

郑博文，刘丽哲

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

0 引言

移动自组织网络(Mobile Ad Hoc Network,MANET)作为一种不借助基础实施的移动通信网络，在地震救援、火灾救援、林区通信和安保通信等多个领域有广泛的应用。移动自组织网络的业务类型主要有单播、广播和多播。单播源节点和目的节点都分别只有一个，广播是一个源节点以洪泛的方式向网络中的所有节点发送消息，广播业务资源利用率高，但是造成网络拥塞。多播是源节点向部分多个目的节点发送消息。多播通信在移动自组网中具有广泛的应用[1]，如文件分发、视频会议、分组话音及事件通知等。MANET资源调度的好坏直接影响了服务质量，如何对MANET进行有效的资源调度，提高多播业务吞吐率和服务质量，是当前亟待解决的研究问题。

针对多播业务的资源调度问题，传统的做法是在多跳网络构建到达各节点的调度树。多播业务所能取得的理论最高速率由最大流最小割定理(Max-Flow Min-Cut Theorem)[2]决定。传统的存储转发方式无法取得最大流最小割定理下的网络容量上限。2000年AHLSWEDE R[3]等人提出了网络编码理论，对来自不同节点的数据包进行编码，并理论证明在多播场景下可以取得由最大流最小割定理决定的网络容量上限。由于机会路由[4-6]和网络编码可以通过创造性地利用无线介质的广播性质来显著提高无线网络的性能[7]，网络编码一直是学术界的研究热点之一。针对网络编码在移动自组网MAC协议设计方面的应用，文献[8]将基于网络编码的MAC机制相关研究工作归纳为3个方面：① 通过合理的MAC机制设计以寻求更多的潜在编码机会；② 网络编码和MAC机制进行联合设计，使编码增益和网络吞吐量达到最优化；③ 改进MAC机制解决网络编码中机会侦听、伪广播等引起的冲突问题。Mendoza-Almanza J等人[9]提出了一种基于机器学习技术的协作网络动态编码系统，将动态网络编码与机器学习技术相结合，使用决策树协调节点在网络编码中的角色。Sun B等人[10]提出了一种基于网络编码的无线传感器网络滑动窗口最大寿命算法，仿真表明该算法提高了无线传感器网络的吞吐量和网络寿命。GU J等人[11]提出基于缓冲区辅助的物理层网络编码(Physical Layer Network Coding,PLNC)技术，根据最大似然和最小均方误差设计标准设计基于最佳线性网络编码矩阵，以改善协作网络上的数据传输。Xing H等人[12]研究了基于网络编码的组播中的负载均衡优化问题，并提出了一种改进的人工蜂群算法(Modied Articial Bee Colony algorithm,MABC)。

KATTI S等人[13]首次提出了机会网络编码架构(Completely Opportunistic Network Coding,COPE)，并通过实验证明了COPE方案的有效性。COPE方案使用的MAC协议是IEEE802.11。IEEE802.11协议采用CSMA/CA机制来竞争无线信道的使用权，从而实现接入控制，但是CSMA/CA网络在节点数量较大时，可能造成网络中节点传输冲突频繁，等待时间长，信道利用率低等问题。因此，对于高并发且业务量较大的网络，更适合采用时分多址接入协议(Time Division Multiple Access，TDMA)。近来已有一些研究者[8-16]考虑在MAC层采用TDMA的方式来支持无线多跳网中基于网络编码的数据传输。但目前在无线多跳网络中，基于TDMA的网络编码传输机制研究还比较少，已有的研究还是将网络编码与TDMA机制进行简单的结合。很少有研究者针对基于TDMA的无线多跳网络，研究动态时变的无线链路以及受限的无线节点资源，对网络中网络编码数据传输性能的影响，并设计与之相适应的通信传输协议。为了得到高效的网络编码传输协议，本文将COPE机会网络编码机制与TDMA自组网相互结合，提出了一种基于网络编码的TDMA移动自组网MAC协议，并通过仿真验证了算法的有效性。

1 网络编码技术

网络编码的基本思想是对来自不同节点的多个数据包进行编码传输，从而提高了单次传输的信息量，减少发送次数，从而达到提高网络吞吐量的目的。网络编码的基本思想如图1所示，考虑网络中节点A、节点C和节点B组成链状网络，节点A和节点B均有业务发给对方，传统的存储转发方法需要4个时隙，如图1 (a)所示；采用网络编码的方法如图1(b)所示，节点A和节点B分别发送数据包至及节点C，节点C将需要中继转发的数据包a和数据包b进行异或运算得到a⨁b后进行发送，节点A收到后与本地数据包a异或后得到b，节点B同理，完成整个传输过程需要3个时隙。

图1 网络编码示例Fig.1 An example of Network coding

KATTI S[13]等人提出的COPE方案的基本操作为：每个节点对整个信道进行侦听并缓存侦听到的数据包；同时，一跳范围内的节点相互交换信息，以掌握其邻居节点的缓存数据信息；每个节点根据其一跳范围内各邻居节点的缓存数据信息来确定编码机会，执行编码操作，并以伪广播的方式来发送编码包。由于COPE方案采用逐比特异或操作，算法复杂度低，易于实现和大规模部署。

2 MAC协议设计

基于机会网络编码的思想，本文提出了基于网络编码的TDMA移动自组网MAC协议，基本思想是：将整个TDMA周期分为信令阶段和数据阶段，在信令阶段实现网络的内同步、邻居发现并向一跳邻居节点广播解码包池缓存的数据包，在数据阶段依据邻居节点的解码包池缓存的数据包情况，通过机会网络编码与解码，进行数据通信。

整个TDMA周期分为N个子周期，每个子周期分为信令阶段和数据阶段，其帧结构如图2所示。其中信令阶段包含N个时隙，数据阶段共有M个数据时隙，每个数据时隙又包含1个数据子时隙和1个ACK子时隙。

图2 TDMA帧结构Fig.2 Time slots of TDMA

信令阶段为每个节点固定分配时隙，每个节点在信令阶段向一跳范围内的节点广播HELLO包，其中HELLO包中包含本机节点信息、同步信息、数据时隙请求与应答信息和解码包池缓存的数据包。信令阶段实现全网的时间同步、数据时隙分配并向全网广播解码包池缓存的数据包，信令阶段处理流程如图3所示。

图3 信令阶段处理流程图Fig.3 Flow chart of signaling phase

数据阶段实现数据传输和ACK确认，数据阶段处理流程如图4所示。数据阶段，在本节点的发送时隙，从当前缓存队列中取出数据包，如果是编码包则直接发送，否则进行编码机会判断，然后发送。编码层机会的判断规则为：一是当上层的数据包到达时，如果能编码则编码后立即发送；二是当发送队列里的数据包等待时间为0时，会再一次判断是否有编码机会的存在，如果有则编码后发送，如果没有也不再等待，直接发送数据包。

图4 数据阶段处理流程图Fig.4 Flow chart of data phase

与传统的COPE网络编码机制[13]一样，考虑节点在进行数据传输时，判断是否进行网络编码以及将哪些数据包进行编码遵循以下一些原则：

① 待编码的数据包应是中转发送的包，而不是由该节点初始发送的数据包；

② 待编码的数据包的下一跳节点应各不相同；

③ 待编码的数据包应为原始数据包。

编码机会的判断是通过要发送数据包下一跳节点的解码包池中缓存数据包信息判断的。遍历本节点的发送队列的数据包pk(i)，如果发送数据包pk下一跳节点的解码包池中有数据包pk(i)的信息，并且pk(i)下一跳节点的解码包池中也有pk的信息，表示pk和pk(i)两个包有编码机会，两个数据包可以编码在一起后发送。本文采用异或编码，由于本文采用TDMA的MAC机制，数据包的大小相同，因此直接将两个数据包的信息进行异或操作，pkencode=pk⨁pk(i)。

3 仿真验证

本文采用OPNET进行仿真，仿真环境为20 km×20 km的区域内，分布的16个节点，保证无孤立节点。仿真网络初始场景如图5所示。仿真参数设置如表1所示。

图5 仿真网络场景Fig.5 Simulation scenario

表1 仿真参数
Tab.1 Simulation parameters

参数数值工作频率600 MHz信道带宽4.0 MHzN16M256ACK时隙长度200 μs数据时隙长度2.0 ms控制时隙长度200 μs移动模型Random Waypoint

节点采用通用7层结构，如图6所示，各模块实现不同的协议。

节点的业务由application模块产生，业务包括数据访问、电子邮件、网页浏览和文件传输等业务类型。

图6 OPNET仿真流程图Fig.6 Flow chart of the OPNET simulation

为了仿真业务负载对网络编码增益的影响，本文仿真了低业务负载、中等业务负载和高业务负载3种等级，分别观察3种业务量下的吞吐量的提升。吞吐量的计算同上，为方便比较性能的提升，将吞吐量归一化输出。编码层数据包的等待时间为固定值0.7 s，解码池的缓存时间也为固定值6 s。低业务量、中等业务量和高业务量时得到的仿真结果如图7～图9所示。未使用编码时，采用MAC层的端到端时延来表示编码层的端到端时延。

图7 低业务量负载时归一化吞吐量和时延对比Fig.7 Comparison of normalized throughput and delay under low traffic load

图8 中等业务量负载时归一化吞吐量和时延对比Fig.8 Comparison of normalized throughput and delay under medium traffic load

图9 高业务量负载时归一化吞吐量和时延对比Fig.9 Comparison of normalized throughput and delay under high traffic load

通过对比图7～图9中的归一化吞吐量可以发现，编码技术的引进确实能提高系统的吞吐量。当业务负载为轻时，所提升的性能大约为10%，而随着业务量的增加，网络拓扑的吞吐量也随之提高，可稳定到20%。当业务量进一步增加时会稳定为21%。而我们编码的理论上界为33.3%，这是由于在网络中，存在大量的路由协议数据包，该类数据包为广播数据包，而广播的数据包是不存在编码机会的。对比图7～图9中的时延可以发现，在引入网络编码技术后，节点之间端到端的时延有所增加。当业务量越少，端到端的时延也就越小，随着业务的增加，编码的机会也越来越多，此时端到端的时延也随之增加。

4 结束语

网络编码作为提升无线网络吞吐量的重要手段之一，一直是学术界的研究热点，本文首先介绍了网络编码技术的研究现状；然后基于COPE机会网络编码的思想，提出了一种基于网络编码的TDMA移动自组网MAC协议，在信令阶段广播本地解码包池缓存的数据包，在数据阶段采用机会网络编码进行数据传输，并分别给出了TDMA时隙结构、MAC层处理流程和编码层的具体实现细节；最后通过OPNET在低业务负载、中等业务负载和高业务负载的情况下进行了仿真，仿真结果表明本文提出的基于网络编码的TDMA移动自组网MAC协议能够提升网络吞吐量。