一种新的竞争与分配相结合的MAC协议

潘 鹏，郭达伟，刘 航，王 鹏

一种新的竞争与分配相结合的MAC协议

潘 鹏，郭达伟，刘 航，王 鹏

针对IEEE 802.11在高竞争下吞吐量低，以及TDMA协议在低负载下吞吐量低的问题，提出了一种新的TDMA MAC协议：Q-TDMA。结合TDMA协议可以保证节点在每个周期内有一个发送机会，而同步CSMA/CA机制可以解决隐藏终端和暴露终端的问题，Q-TDMA协议要求节点根据本身的队列长度来竞争复用时隙。仿真实验结果表明，Q-TDMA提高了网络吞吐量，降低了端到端的延迟。

Ad hoc网络；时分多址；媒介接入控制；Q-TDMA协议

1 引言

Ad hoc网络是一种不依赖于任何固定基础网络设施的自组织、分布式的多跳无线网络。它可以由无线移动终端在一定的范围内自由搭建。Ad hoc网络中节点直接通过无线共享媒介，进行交换数据包。媒体接入控制（MAC）主要作用是提供有效的调度机制来分配有限的无线共享信道资源。MAC层控制网络节点接入无线信道，是所有数据报文和控制信息在无线信道上发送和接收的直接支配者。因此，MAC层高效地使用无线信道的有限带宽是至关重要的。

根据信道接入的策略，Ad hoc网络的MAC协议可以分为竞争类和分配类。竞争类协议主要包括：Aloha、 CSMA、MACA、FAMA和802.11[1-5]。它们一般采用冲突避免机制和随机重传，在网络负载较轻时比较有效。但随着负载增加冲突增多，吞吐量可能降低至零，网络不稳定，不能保证有界的端到端延迟。其优点是移动透明性，即协议不会根据网络拓扑的变化来改变工作方式。分配类协议主要包括：传统的TDMA、E-TDMA[6]和ADAPT[7]等。传统TDMA具有移动透明性优点，但是它不能复用时隙，吞吐量低；E-TDMA适用于大负载网络，缺点是不具有移动透明性，不能适应于拓扑变化快的网络；ADAPT是一个竞争分配相结合的MAC协议，有效地增加了吞吐量，但同时引入了隐藏终端和暴露终端的问题。

为了解决这些协议中存在的上述缺点，本文提出了Q-TDMA协议。

2 Q-TDMA协议描述

Q-TDMA协议是一种TDMA与同步CSMA/CA机制相结合的协议。每个节点固定拥有一个属于自己的时隙，引入同步竞争机制对未使用的时隙进行管理，在自己时隙上节点有优先发送RTS的权力；当其他节点发现时隙的拥有者没有数据发送时，它则根据本节点队列的长度，对该时隙进行分优先级竞争复用时隙。

网络中存在N个节点，每个节点固定分配一个时隙，每个时隙包括监听、竞争和数据3个阶段；其中监听阶段又分为两个子微时隙。竞争阶段包括竞争1和竞争2两个阶段。每个竞争阶段分为n个微时隙，每个微时隙再分为两个子微时隙。竞争阶段和监听阶段的微时隙、子微时隙相等。具体帧和时隙结构如图1所示。

图1 帧和时隙结构

本文将从时隙的监听、竞争、数据阶段来介绍Q-TDMA协议。假设目前正处在时隙i，各个节点在这个时隙内的具体动作如下。

监听阶段：在时隙i中，节点i如果有数据要发送，则在第一个子微时隙发送RTS。收到RTS的目的节点在第二个子微时隙回复CTS，节点i收到CTS回复，则节点i在数据阶段发送数据。如果非目的节点收到RTS，则这些节点标记在时隙i内不接收数据。如果非发送节点收到CTS，则这些节点标记在时隙i内不发送数据。这样可以保证在发送端不存在其他的接收节点，在接收端不存在其他的发送节点。

如果节点i没有数据要发送，则它不竞争信道。其中RTS、CTS帧格式如图2、图3所示。

图2 RTS帧

图3 CTS帧

竞争阶段：在时隙i的监听阶段，节点j如果没有监听到CTS，且有数据要发送，则可以根据本节点队列的长度，来判断选择在竞争1或竞争2阶段中来进行竞争信道。节点在所选择的竞争阶段随机选择一个微时隙来竞争信道，具体流程如下（给定队列长度的阈值为L）：

在时隙i内，如果节点j的队列长度为M，且大于给定的阈值L，则它在竞争1阶段中随机选择一个微时隙，来竞争信道。假设节点j选择在微时隙q(1≤q≤n)中进行竞争信道。如果节点j在前q-1个时隙内没有收到过其他节点发送的CTS，则节点j在微时隙q的第一个子微时隙中发送RTS，如果目的节点收到RTS，且在前q-1时隙内没有收到其他节点发送的RTS，则目的节点在第二个子微时隙回复CTS。如果节点j收到CTS回复，则说明节点j成功地占用了信道，它将会在数据阶段发送数据。收到RTS的非目的节点标记在时隙i中不接收数据。

如果节点j的队列长度M小于等于给定的阈值L，则它在竞争2阶段随机选择微时隙竞争信道，同上所述。

数据阶段：竞争到信道的节点，在此阶段发送数据。

3 协议性能分析

3.1 吞吐量

为了简化分析，本文假设网络拓扑是静态的，流量负载均匀分布。网络中存在N个节点，一个周期内包含N个时隙。

对于一个给定的节点i，需要分析讨论两种情况的吞吐量：一种是时隙分配给节点i，另一种是时隙未分配给节点i。用φ表示节点i有数据包传输的概率，π表示节点i的邻居平均个数（不包括有数据向节点i的两跳邻居传输的节点）。由于每个时隙分配给节点i的概率为1/N，所以节点i在自己的时隙上传输数据包的概率为：

另一种情况是节点i尝试在未分配给自己的时隙上发送数据。节点竞争未分配给自己的时隙的概率可以表示为：

其中，t是节点在一个时隙内传输的概率。节点i竞争成功的概率为：

通过联合两种情况的传输数据包概率，得到一个节点的近似吞吐量：

通过计算，得出，当t=1/(π(1-φ/N)π)时，Q-TDMA的节点的吞吐量上界为：

3.2 同步RTS/CTS消除隐藏终端和暴露终端

IEEE 802.11 DCF通过引入异步RTS/CTS握手机制来减少隐藏终端问题，但是它并没有完全消除隐藏终端问题，同时又带来了暴露终端问题。

在图4中，Si是发送节点，Ri是接收节点。在802.11方式下，可能会出现如下情况：当节点S2正在给节点R2发送RTS，同时节点R1在给节点S1回复CTS时，节点R1无法检测来自节点S2的RTS，节点S2无法检测来自节点R1的CTS，这样就会出现节点S1向节点R1发送数据时，节点S2向节点R2发送数据或CTS，数据在节点R1处发生碰撞。这就是隐藏终端问题。

图4 隐藏终端和暴露终端问题

这里引入同步RTS/CTS方式[8]进行握手交换，从而来解决隐藏终端问题。假设节点S1、S2选择同一等级的竞争阶段，竞争向节点R1、R2发送数据，其中节点S1、S2选择在T1、T2微时隙内竞争。

当T1＜T2时，在T1微时隙的第一个子微时隙内，节点S1发送RTS给节点R1，收到RTS的节点R1在第二个子微时隙内回复CTS，节点S1收到节点R1回复的CTS，在数据阶段，节点S1向节点R1发送数据。由于节点S2收到节点R1回复给节点S1的CTS，所以在这个时隙内节点S2标记不发送数据。

当T1=T2时，在T1微时隙内的第一个子微时隙内，节点S1、S2发送RTS，节点R1感知到RTS的碰撞，将不回复CTS；节点R2收到节点S2的RTS，在第二个子微时隙内回复CTS，节点S2收到节点R2回复的CTS，则在数据阶段节点S2向节点R2发送数据。

类似地，当T1＞T2时，节点S2在数据阶段向节点R2发送数据。

如果节点S1、S2在不同竞争阶段下，竞争向节点R1、R2发送数据，则更为简单，同上所述。

另一个问题是802.11方式存在暴露终端问题。如图4所示，如果节点S1向节点R1发送RTS，则节点S3收到节点S1的RTS并会保持沉默，同一时间内不会发送数据。但在实际情况下，节点S3向节点R3发送数据，并不影响节点S1向节点R1发送数据。Q-TDMA协议可以保证节点S3在收到RTS后，仍能发送RTS或数据给节点R3。这样就解决了暴露终端问题。

3.3 延迟分析

Ad hoc网络中传递一个分组，其每跳传递的延迟[8]包括如下：

载波侦听时延（Tcs）为发送节点进行载波侦听时花费的时间，载波侦听时延大小由竞争窗口大小决定。

退避时延（Tb）为节点侦听到另外一个或者发生碰撞而导致载波侦听时所产生的时延。

传输时延（Ttx）由信道带宽以及所采用的分组长度和编码方案决定。

传播时延（Tprop）由发送节点和接收节点之间的距离决定。在Ad hoc网络中，节点通信距离通常很短，因此通常忽略传播延迟。

处理时延（Tproc）为节点在将所收分组转发到下一个转发跳之前对该分组所作处理而花费的时间。

排队时延（Tqueue）依赖于流量载荷。在重载荷情形下，排队延迟变成一个支配因素。

上述时延是采用IEEE 802.11协议的多跳网络的固有时延。

TDMA协议时延主要包括排队延迟Tqueue，传输时延（时隙的大小Tslot），第n个转发跳的时隙等待时延（Twait，n），处理时延Tproc。

Q-TDMA协议时延主要包括排队延迟Tqueue，固定大小的监听竞争延迟Tfixed，传输时延（数据时隙的大小TDATAslot），第n个转发跳的时隙等待延迟（Twait，n），处理时延Tproc。

下面将从不同负载下分析在M跳网络中MAC协议的时延。首先假设3种协议的传输时延相等。在流量负载较小（一个帧周期内有一个数据包）时，没有排队延迟和退避延迟，另外假定传播延迟和处理延迟可以忽略不计。在这种情形下，Q-TDMA协议的延迟为：

从公式（6）、（7）、（8），可以得到TDMA协议与IEEE 802.11协议的端到端延迟比较取决于M跳的时隙等待时延和M跳的载波侦听时延；Q-TDMA协议的端到端延迟比TDMA多了M个固定大小的监听竞争时延。

在流量负载较大时，IEEE 802.11因为碰撞导致侦听时延Tcs，n（第n个转发的侦听时延）和退避时延Tb增大，使得端到端的延迟很大。Q-TDMA协议能够根据队列的长度来复用时隙，从而可以有效地减少队列延迟，并弥补了固定大小的监听竞争时延。

在低负载下，Q-TDMA协议端到端延迟高于TDMA协议。在高负载下，Q-TDMA协议端到端延迟低于TDMA协议和IEEE 802.11协议（见仿真实验图9）。

4 仿真及分析

将该协议与IEEE 802.11和传统的TDMA进行对比。

4.1 评价指标

网络吞吐量：网络中所有节点每秒成功接收位数。端到端延迟：数据包从源节点发送出去，到目的节点收到数据包所消耗的时间。

4.2 仿真参数的设定

仿真工具采用NS2[9]，仿真的参数如表1。

表1 仿真参数表

4.3 仿真结果分析

本文在不同场景设置下仿真，并对吞吐量、端到端延迟进行分析。

4.3.1 吞吐量仿真及分析

26个节点随机分布在500 m×500 m场景下，仿真时间为80 s。本文根据不同数目的发送节点（不同负载和竞争下），来分析比较在不同的生成数据包时间间隔下，3种协议吞吐量的变化。

图5所示，当生成数据包时间间隔在[0.13，0.11]之间时，3种协议随着生成数据包间隔的减少，吞吐量呈线性增加。生成数据包时间间隔在[0.11，0.01]之间时，TDMA的吞吐量不变，且非常低，这是因为传统的TDMA只能在自己时隙内发送数据，不能复用时隙，信道利用率低。由于网络中发送节点很少，竞争强度很低，802.11充分利用信道，所以802.11吞吐量要高于TDMA。由于Q-TDMA存在固定监听和竞争时间，并比802.11的握手交换消耗的时间要长，所以Q-TDMA的吞吐量低于802.11的吞吐量。与TDMA相比，Q-TDMA复用了时隙，因此Q-TDMA吞吐量高于TDMA。

图5 发送节点为5个时的吞吐量

图6所示，当生成数据包时间间隔在[0.15，0.11]之间时，Q-TDMA、802.11和TDMA的吞吐量随着生成数据包时间间隔的减少而增加，并且3种协议的吞吐量大致相等。这是由于在这个时间间隔范围内，产生数据包的能力低于节点发送数据包的能力。生成数据包间隔在[0.11，0.01]之间时，Q-TDMA的每个节点可以保证在一个周期有一个固定的时隙来发送数据，同时也可以复用时隙发送数据，因此它的吞吐量要高于802.11和TDMA。

图6 发送节点为20个时的吞吐量

图7表示网络中存在25个发送节点时，在这种高竞争、高负载的网络中，3种协议吞吐量的变化。由于802.11发送碰撞的概率非常大，它消耗大量的时间在数据重传上，Q-TDMA和TDMA中每个节点在一个周期内有一次固定的发送机会，所以在整个的发送间隔[0.14，0.05]中，Q-TDMA和TDMA的吞吐量都高于802.11。又由于Q-TDMA还可以根据节点的负载情况竞争复用时隙，所以Q-TDMA的吞吐量比TDMA要高。

图7 发送节点为25个时的吞吐量

4.3.2 延迟仿真及分析

18个节点分布在1 000 m×500 m的场景下，如图8所示。

图8 网络拓扑图

从0 s开始，网络中启动第一条数据流（0～5）。随后，每50 s增加一条的数据流（7～6，8～7，12～6，13～7，14～8，4～10，15～9，16～10），本文统计不同数目数据流下，节点0到节点5数据包的平均端到端延迟，仿真时间为450 s。

图9表示随着数据流数目的增加，网络中平均端到端延迟的变化。在整个过程中，802.11随着数据流个数的增加，竞争节点会相继增加，平均的端到端延迟逐渐增加。当数据流数目增加到7条时，TDMA协议延迟突然增大，这是因为数据包在节点4上出现了队列排队延迟，导致数据包的端到端延迟增加；与TDMA相比，由于Q-TDMA可以复用时隙，数据包在节点4上没有产生额外的队列排队延迟，所以Q-TDMA的延迟保持不变。

图9 平均端到端延迟

5 结论

本文提出了一种竞争与固定分配相结合的Q-TDMA协议。它将TDMA与同步CSMA/CA机制相结合，并根据本节点的负载情况来选择竞争信道。从NS2仿真实验可以看出，与IEEE 802.11和传统的TDMA相比，Q-TDMA协议有效地提高了网络的吞吐量，降低了端到端的延迟。在今后的研究中，还需要对Q-TDMA做进一步的理论分析和验证，设计更加复杂的仿真和实验模型。

[1]Abramson N.TheALOHA system-anotheralternative for computer communications[C]//Proceedings of the Fall Joint Computer Conference，1970：281-285.

[2]Tobagi F，Kleinrock L.Packet switching in radio channels I. Carrier sense multiple access models and their throughput delay characteristics[J].IEEE Transactions on Communications COM，1975，23（12）：1400-1416.

[3]Fullmerc L，Garcia-Luna-Acevje S.Floor Acquisition Multiple Access（FAMA）for packet-radio networks[C]//Proceedings of ACM SIGCOMM，1995.

[4]Karn P.MACA-a new channel access protocol for packet radio[C]//ARRUCRRL Amateur Radio Ninth Computer Networking Conference，1990：134-140.

[5]IEEE Draft Standard P802.11 Wireless LAN Wireless Medium Access Control and Physical Layer WG[S].IEEE Standards Department，1996-01.

[6]Zhu C，Corson M S.An evolutionary-TDMA scheduling protocol（ETDMA） formobile Adhocnetworks，Technical Research Report CSHCN TR 2001-17[R].2001.

[7]Chlamtac I.ADAPT：a dynamically self-adjusting media access controlprotocolforAd hoc networks[C]//Proceedings of the IEEE Globecom，1999.

[8]Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks[C]//Proc IEEE INFOCOM，New York，NY，June 2002：1567-1576.

[9]NS2[EB/OL].[2011-07].http：//www.isi.edu/nsnam/ns.

[10]Ni J，Tan B R，Srikant R.Q-CSMA：queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[C]//Proceedings of the 29th International Conference on Information Communication，March 14-19，2010：271-275.

[11]Durvy M，Thiran P.Packing approach to compare slotted and nonslotted medium access control[C]//Proceedings of IEEE INFOCOM，April 2006.

[12]Wu X，Srikant R，Perkins J R.Queue-length stability of maximalgreedy schedules in wireless networks[J].IEEE Transactions on Mobile Computing，2007：595-605.

PAN Peng,GUO Dawei,LIU Hang,WANG Peng

西北工业大学 自动化学院，西安 710129

School of Automation,Northwestern Polytechnical University,Xi'an 710129,China

Queue-length based Time Division Multiple Access（Q-TDMA）is a new Media Access Control（MAC）protocol.Its purpose is to resolve poor throughput for IEEE 802.11 with high competition and TDMA with low loads.TDMA protocol can guarantee that each node has a chance to send in a cycle,while synchronous Carrier Sense Multiple Access with Collision Avoidance（CSMA/CA）mechanism can solve the hidden terminal and exposed terminal problem.Combining with the advantages of TDMA and synchronous CSMA/CA mechanism,Q-TDMA demands that node needs to contend to access channel based on its'own queue length.According to the simulation results,Q-TDMA improves the network throughput and reduces end to end delay.

Ad hoc network;Time Division Multiple Access（TDMA）;Media Access Control（MAC）;Queue-length based TDMA（Q-TDMA）

A

TP393

10.3778/j.issn.1002-8331.1109-0068

PAN Peng,GUO Dawei,LIU Hang,et al.New combination of contention and allocation MAC protocol.Computer Engineering and Applications,2013,49（7）：76-80.

西北工业大学研究生创业种子基金资助项目（No.Z2011052）。

潘鹏（1985—），男，硕士研究生，研究方向为无线网络MAC协议以及路由协议；郭达伟（1968—），男，副教授，硕士生导师，主要从事信息安全、网络化控制、无线传感器网络等方向的研究工作；刘航（1973—），男，副教授，硕士生导师，主要从事密码硬件与嵌入式系统、嵌入式网络系统、嵌入式系统软硬件协同开发的研究与应用；王鹏（1985—），男，硕士研究生，主要研究领域为无线自组网网络路由协议。E-mail：5829panpeng@163.com

2011-09-05

2011-10-30

1002-8331（2013）07-0076-05

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.063.html