多信道时分多址MAC协议在WMN中的优化应用*

张瑞琪， 降爱莲

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

多信道时分多址MAC协议在WMN中的优化应用*

张瑞琪， 降爱莲

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

随着无线Mesh网络(WMN)中跳数的增加，端到端的延时急剧增大，所以，在多跳WMN中很难做到服务质量(QoS)保证。针对以上问题，提出了一种新型多信道时分多址(TDMA)媒体访问控制(McTMAC)的协议，可以有效地降低在多跳网络中端到端的延时。通过测试评估结果显示：McTMAC协议优于现有的无线WMN协议，通过使用McTMAC协议端到端最大延时降低了60 %。

调度延迟; 多信道; 时隙分配; 时分多址; 信道分配; 无线Mesh网络

0 引 言

无线Mesh网络(WMN)作为一种新兴的通信网络，其网络拓扑中包含多个通信节点。随着它的发展应用，多跳通信链路的服务质量也开始受到关注。因为随着跳数的增加，端到端的延时快速升高。为了解决这种延时升高问题，基于媒体控制(MAC)协议的时分多址(TDMA)技术被采用并作为标准。基于TDMA的WMN采用时隙分配算法来降低端到端的延时，所以，最优化需要处理的问题就是降低最大延时，但现有优化方式都是局限于使用单信道系统。

尽管在WMN中有多种信道分配算法，但是大部分都只是增强系统容量，如“distance-1”算法就是增加了系统的容量[1]。尽管这种算法能够明显地提高系统的容量，但是它却没有考虑到端到端的延时问题。文献[2]中所提的算法是基于最大数据流的多频射多信道WMN中选取最优信道分配和集中链路分配。这些算法都能够以最少的时隙数完成全部数据的传送，但是最少的时隙数并不能保证降低多跳数据流端到端的延时[2]。文献[3]中提到了集中式和分散式的最大调度算法在多频射多信道WMN中的应用，文中考虑到了数据交换延时，但是它没有考虑到在多跳连接链路中的传输顺序，这是影响端到端延时的重要因素[3]。

本文提出在多信道链路中，使用一种基于TDMA的多信道网状网络，分别采用信道和时隙分配算法来实现降低端到端延时的目标。本文算法主要是基于长的数据流进行信道分配和时隙分配。

1 WMN中的延时问题

假设有多跳WMNG=(N,L)，其中,N为设备集合，L为连接设备的链路集合。存在于节点n和m的链路为l=(n,m)，其中,节点n和m包含在传输网络中。假设l∈L，节点n通过多通道系统C向m发送数据包。此外，假设一个时间被分为固定连续的帧T的TDMA型系统，每个帧又被细分为一个时隙集合k。假定有流集合F和流f，规定F为节点集合R(f)={v1,v2,…,vn}，其中,vi为链路中的第i个节点。第一个节点v1为源节点，vn为接收节点。在图1中，有一个数据流R(f1)={1,2,3,4}。节点1是源节点，节点4是目标节点，有3条通道，在每一帧中都有k=5的时隙。

图1 无冲突信道中两条数据流时隙分配Fig 1 Time-slot assignment of two data flows in conflict free channel

网络中某个节点使用信道和时隙的组合(c,s)发送一个数据包，这两个参数是确定联机或是脱机的,因此，WMN就会有信道和时隙的分配问题。本文所关注是QoS，所以,目标是有效地降低数据流的延时[4]。其中重点是要找出一种最优的方法来减小数据流的最大延时，因为这是一个NP完全问题。

2 长数据流优先信道分配和长数据流优先时隙分配

首先，向所有的链路分配信道,然后根据算法向信道分配时隙，算法的核心思想是给予长数据流更高的优先级。采取这种长数据流优先(longest flow first,LFF)的思想效果很明显，因为在WMN中，随着跳数的增加，端到端延时明显增大，网络吞吐量显著下降[5]。

2.1 LFF信道分配

目前常用的算法采用在次要冲突链路中的争议等级。在信道c中，链路l的争议等级是链路中有干扰的链路的数目。例如:链路(1,2)在独立的信道1和2之间的争用等级有0和2。这些冲突链路是在干扰范围内的一对链路。如果它们有公共节点，即为主要冲突链路；否则，即为次要的。链路(1,2)和(2,3)为主要的冲突链路，而链路(1,2)和(3,4)为次要冲突链路。在LFF的信道分配中，本文根据“distance-1”算法，并且进一步将数据流的长度考虑在内，利用争用等级或次要冲突链路数目来分配信道的过程如下：

1)初始化次要争用等级为0。

2)根据流长度降序排列数据流。

3)在数据流序列中选取最长的且没有分配信道的流f。

4)对于未分配信道的流f的所有链路l：

a.分配信道c给争用等级最小的流；

b.如果等级相等，且原链路的争用等级是最小的，将信道分配给原始链路；否则，任意分配给一条争用等级最小的链路;

c.更新次要争用等级。

5)如果l是流f中的最后一条链路，跳至步骤(2)；否则，跳至步骤(3)。

如图1中例子所示，有2条数据流R(f1)={1,2,3,4}和R(f2)={5,6}。假定有2条可用信道，由于流f1最长，LFF信道分配算法首先为它分配信道。对于链路(1,2),由于争用等级的初始值为0，所以,它任意选取一条信道，假定分配信道1。然后，由于前一步的链路分配，算法同样分配信道给链路(2,3)。那么，在信道1和2中链路(3,4)的争用等级分别是1和0。需要注意的是,在计算次要冲突链路的数量时，链路(3,4)并没有相同的节点，因此,LFF信道分配算法将链路(3,4)分配在信道2，其中,链路(3,4)是最低的争用等级。流f1的链路分配完后，LLF信道分配算法为链路(5,6)上的流f2分配信道。因为在信道1和2上的争用等级分别是2和1，所以分配信道2。

2.2 LFF时隙分配

在WMN的时隙分配中，提出了基于树的拓扑结构，可以最大程度地减小端到端的延时[6]。然而，它却被局限在单一的信道和单一的网关中。本文提出的LFF时隙分配算法将在多网关、多信道的网络中应用。与信道分配算法相似，LFF时隙分配算法仍然采用的是长数据流。算法基本思想是分配长数据流的多个时隙，使得以前链路中的数据包可以被立即完成传输。例如：如果时隙1在优先链路中被用于数据流1，分配时隙2或相近时隙2可以流程化传输。和LFF信道分配一样，优先给长数据流分配时隙。每个链路都有一个没有在冲突链路中使用的时隙列表，列表中每一个时隙都可以被选取。时隙分配过程如下：

1)初始化可用时隙列表{1,2,3,…,T},其中,T为时隙个数。

2)根据流长度降序排列数据流。

3)在数据流序列中选取最长的且没有分配信道的流f。

4)对于未分配信道的流f的所有链路l：

a.将其后最接近先前链路中时隙的可用时隙t分配;

b.如果以上时隙不存在，则T加1，且重新应用该算法；

c.更新可用时隙列表。

5)如果l是流f的最后一条链路，跳到步骤(2)；否则，跳到步骤(3)。

如图1所示为LFF时隙分配的结果。其最长的流f1在链路(2,3)分配时隙2在先前链路(1,2)在时隙1传送到达后立即传输。由于次要冲突链路(5,6)和(1,2)被分配了不同的信道，它们可以同时在时隙1安排传输。本文提出的算法是半静态的，本文在给定的网络假设了一组给定的数据流。信道和时隙的分配可以按需要变为固定的间隔。此外，本算法与传统算法不同，它采用的是网络层中的数据流，而现在大部分信道分配算法都是工作在数据链路层。

3 性能评估

本文提出的算法的性能在Matlab 7.0中自己开发的模拟器进行测试评估。模拟802.11标准的网状网络如图2所示，其模拟器的参数如表1所示。

图2 5×5网状网络Fig 2 5×5 mesh network

参数数值速率2Mbps编解码器G729A数据包大小864bits时隙大小432μs分组间隔24路由协议负载均衡、最小跳数

3.1 LFF信道分配算法与“distance-1”算法对比

假定有10个双向噪声信息通过一组节点(1,3,10,20,11,22,24,919,17)到网关节点25。最有效的数据通信就是当所有的时隙都没有用于噪声通信时，所有的节点都以2 Mbps的速度传输数据。如图3显示了两信道分配算法在1～5个信道中端到端延时性能表现。当3个信道时，端到端最大延时降低了60 %，并且随着信道数量增加，端到端延时性能变化较小，因为在网状网络中4个信道能够满足任意冲突中的信道分配。

图3 LFF信道分配算法性能测试Fig 3 Performance test of LFF channel allocation algorithm

3.2 LFF时隙分配

通过使用LFF时隙分配算法与其他算法对比，如PETAR09。仿真模拟在拥有信道1和信道2的线性网络拓扑中完成的。数据链从1到8的长度各不相同，图4表示了PETAR09延迟性能和LFF时隙分配在单双信道中的延迟性能的对比。

通过使用LFF时隙分配算法与其他算法对比，如PETAR09。仿真模拟在拥有信道1和信道2的线性网络拓扑中完成的。数据链的长度各不相同，图4表示了PETAR09延迟性能和LFF时隙分配算法在单双信道中的延迟性能的对比。理想化的结果是所有的时隙全部有效使用。由于PETAR09算法被设计用于单信道的网络中，所有它在单信道中的性能表现与LFF时隙分配算法的性能相同。当LFF时隙分配算法在双信道中使用时，与单信道性能相比，其最大延时降低了大约48 %。

图4 LFF时隙分配算法性能测试Fig 4 Performance test of LFF time slot assignment algorithm

4 结 论

本文分析了McTMAC协议在多跳WMN有效地处理了端到端延时。PETAR09算法的时隙分配与多信道时隙分配结合应用，增强了“distance-1”算法的信道分配性能。模拟结果显示：本文的时隙算法得到的结果与PETAR09在单信道时隙分配应用结果相似，并且在多信道环境中优于PETAR09算法。此外，模拟结果还表明：在某些情况下，使用LFF信道分配算法替代“distance-1”算法能够明显降低端到端最大延时。

[1] Aryafar E,Gurewitz O,Knightly E.Distance-1 constrained cha-nnel assignmentin single radio wireless mesh networks[C]∥IEEE INFOCOM,Orlando,USA:IEEE Communications Society,2008:762-770.

[2] Yu H,Mohapatra H,Liu X.Channel assignment and link scheduling in multi-radio multi-channel wireless mesh networks[J].Journal of Network and Computer Applications,2008,13(3):169-185.

[3] Yun M.Channel-assignment schedulingin wireless mesh networks considering switching overhead[C]∥IEEE ICC,Dresden,Germany:IEEE Communications Society,2009:1-6.

[4] 种红波.无线Mesh网QoS关键技术研究[D].长沙:中南大学,2010.

[5] 王 震,常颖华.基于预测时延的无线Mesh网络组播路由算法[J].传感器与微系统,2012,31(4):133-137.

[6] 漆华妹,陈志刚,吴显平.基于最小加代数理论求解无线Mesh网络端到端延迟上界的方法[J].高技术通讯,2010,33(20):233-238.

Optimization application of multi-channel TDMA MAC protocol in WMN*

ZHANG Rui-qi， JIANG Ai-lian

(College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024,China)

With the increasing number of hops,it is difficult to guarantee QoS over multihop wireless mesh networks(WMN) because end-to-end delay increases quickly.To solve the above issues,a novel multi-channel time-division multiple-access(TDMA) media access control(MAC),that is McTMAC protocol that can help to efficiently reduce end-to-end delay over multihop networks.Performance evaluation results demonstrate that McTMAC outperforms existing WMN protocols,the maximum-delay can be reduced by as much as 60 % by using McTMAC protocol.

scheduling delay; multi-channel; time-slot assignment; TDMA; channel assignment; WMN

2013—09—11

山西省留学回国人员科研资助项目(2011—10); 山西省基础研究资助项目(2013011019—7)

TP 393

A

1000—9787(2014)04—0158—03

张瑞琪(1988-)，男，山西太原人，硕士研究生，主要从事无线传感器网络的研究。