一种新型的无竞争的基于TDMA的MAC协议*

任昊翔，郭达伟*，邵凝宁，毛保磊

(1.西北工业大学自动化学院，西安710129;2.南京北方信息控制集团有限责任公司，南京210000)

在Ad Hoc网络[1]中，MAC协议由于其直接影响网络的性能而成为研究热点。Ad Hoc网络中的MAC协议，按照其自身的发送机制，大抵可以划分为以下两大类。

第一类是基于竞争的 MAC协议[2－5]。这类协议的主要思想是通过网络节点的相互竞争来直接决定信道的使用权，并且通过一定的策略使得拥有高优先级数据的节点能够更容易的竞争到信道，以使其具有更高的分组投递率。

第二类是无竞争的 MAC协议[6－8]。这类协议的主要思想是先将信道划分为超帧，又进一步将超帧划分为时隙。整个网络通过分配或者竞争的方法来决定时隙的使用权。一旦节点获得了时隙的使用权，那么这个节点在以后的超帧内也将继续使用这个时隙，直到节点没有数据发送。

无竞争的MAC协议为了满足各种QoS，主要是将竞争的思想融入到无竞争的协议中。引入竞争思想就可能产生冲突，从而造成数据时隙的浪费。

本文提出一种新型的无竞争的MAC协议。通过加入时隙竞争和时隙续约机制以避免数据时隙的浪费并提高数据时隙使用率和分组投递率。而且通过引入虚拟数据和竞争时隙交换的机制，在提高分组投递率的同时也降低了整个网络的传输延迟。

1 无竞争的MAC协议研究现状

无竞争的MAC协议，按照不同的QoS要求，大体可以分为两类。

第1类是指提高分组投递率的MAC协议。这类协议的思想是在TDMA体系中融入竞争的思想。主要是将超帧划分为如图1所示的结构。每个超帧都拥有竞争时隙和数据时隙[9]。如果节点有数据要发送，则首先会在超帧中随机挑选一个竞争时隙用于发送申请请求。如果申请请求正确发送，则这个节点可以在申请的数据时隙发送数据。否则，不能发送数据，且要实行退避。当然，通过对不同优先级的数据采用不同的竞争算法和退避算法，可以实现让拥有高优先级数据节点更容易竞争到竞争时隙，以满足提高其分组投递率的服务要求。

图1 无竞争的MAC协议超帧格式

第2类是指降低网络延迟的 MAC 协议[10－11]。文献[10]提出的协议有着类似于图1的超帧结构。只是将时隙竞争时期变为信标时期。在信标时期内，每个节点都有自己的信标时隙。节点想要发送数据时，首先会在自己的信标时隙中，广播这个信息。接收到这个信息的节点也会在属于自己的信标时隙中继续广播这个消息，并且在这个消息中加入自己的节点信息。通过不断的广播直到目的节点接收到这个消息。目的节点在接收到这个消息之后，会选择一条合适的路径进行单播回复，并且在回复中确定这两个节点之间数据流使用的时隙。最终在这一去一回的消息交换中，以一定的超帧的时间为代价建立起发送节点到目的节点的一条路径，之后节点才会发送数据，以获得较低的网络延迟。

而本篇论文，综合了以上两种思想的优点，提出了一种新型的属于自己的时隙竞争思想和路径建立思想，以同时满足以上两种QoS要求。

2 CA-TDMA协议

2.1 超帧格式

CA-TDMA协议的超帧格式如图2所示。在CA-TDMA协议中，超帧划分为时隙竞争时期和数据发送时期。时隙竞争时期由M个竞争时隙组成。每个节点有且仅有一个属于自己的竞争时隙。竞争时隙的作用是使节点发送数据时隙申请请求，以使节点获得数据时隙的使用权。数据发送时期由N个数据时隙组成。其中N小于M。数据时隙主要用于发送数据。

图2 CA-TDMA协议超帧格式

2.2 RTS、CTS、CTR 的消息结构

2.2.1 RTS 消息的结构

图3为 CA-TDMA协议中 RTS消息的结构。CA-TDMA协议中RTS消息按照不同的功能可以划分为3个部分:时隙申请信息、时隙续约信息和时隙使用状态信息。时隙申请信息用于节点申请新的数据时隙。时隙续约信息用于节点续约旧的数据时隙。时隙使用状态信息用于填写与节点有关的数据时隙使用状态的信息，以完成对续约信息的确认和取消。

图3 CA-TDMA协议中RTS的帧结构

2.2.2 CTS 消息的结构

图4为CA-TDMA协议中CTS的帧结构。CATDMA协议中的CTS消息按照不同的功能划分成两个部分:时隙分配确认信息和竞争时隙交换信息。时隙分配确认信息用于对接收到的RTS信息进行确认回复。竞争时隙交换信息用于进行竞争时隙交换。

图4 CA-TDMA协议中CTS的帧结构

2.2.3 CTR 消息的结构

图5为CA-TDMA协议中CTR的帧结构。CTR消息用于对节点已确认的发送请求进行清除。

图5 CA-TDMA协议中CTR的帧结构

2.3 CA-TDMA的时隙竞争和时隙续约

2.3.1 时隙竞争

CA-TDMA协议中采用一种变相的竞争方法。首先每个节点都会依据算法1来决定如何生成RTS请求。如果节点发送有效的RTS信息后，收到有效的CTS信息，则生成相应的记录信息。如果在时隙竞争时期结束之后，节点记录信息依然存在，则该节点可以在相应的数据时隙发送数据。否则，节点会放弃该数据时隙，并且将数据的优先级提升后放回数据缓冲区。这里有效的RTS消息是指RTS消息中有对数据时隙的申请请求信息，有效的CTS是指CTS消息是对RTS消息的正确回复。

算法1 RTS发送的确定算法

例如，如图6所示的简单拓扑中。

图6 3节点的拓扑图

假设节点1有数据发送给节点2且优先级为2，节点3也有数据发送给节点2优先级暂且未知，而数据时隙的个数为1。那么当超帧开始时，由于数据时隙1为空闲，节点1会在自己的竞争时隙内和节点2交互“有效”的RTS和CTS信息(RTS1和CTS1)以完成数据时隙1的申请并做相应的记录信息。由于网络是无线网络，节点3也能收到CTS1信息，并会修改数据时隙1的状态。当节点3的竞争时隙到来后，则根据算法1，如果节点3的数据优先级不大于节点1，节点3会发送“无效”的RTS信息。否则，节点3会发送“有效”的RTS信息(RTS2)，以实现节点3和节点2之间的控制信息交互。而节点1收到CTS2信息后也会得知，有更高优先级的节点“占用”了与自己相同的数据时隙，则节点1删除记录信息并放弃数据时隙1。通过这种变相的竞争方法，以使得高优先级数据能够优先发送。

由于CA-TDMA协议中的RTS和CTS信息的传输范围只是发送RTS节点和发送CTS节点的一跳范围，所以有可能会产生数据时隙的冲突。例如在如图7所示的简单拓扑中。假设节点1给节点2发送数据，节点3给节点4发送数据并且节点3的数据优先级高于节点1。那么当节点1和节点3选择相同的数据时隙时就会产生数据冲突。

图7 CTR作用说明拓扑图

为了解决这种问题，CA-TDMA协议引入了CTR消息。当出现上述情况时，节点2会生成CTR消息并发送给节点1，以阻止其发送数据。从而避免可能产生的数据冲突。

2.3.2 时隙续约

为了满足大数据量的传输要求，CA-TDMA协议提出了时隙续约的机制。时隙续约也是时隙申请，是指对已经成功申请的数据时隙再次进行申请。

具体来说，例如在图6拓扑中，假设节点1有大量的数据要发送给节点2。那么节点1在第一个超帧会通过RTS的时隙申请信息对节点2进行数据时隙申请并做记录。而在接下来的超帧内，如果节点1还有数据要发送给节点2，那么节点1首先会填写RTS的续约信息，以告知节点2我依然会用原来的时隙继续发送数据，如果此时节点1的还有数据存在，那么节点1就会通过RTS中的时隙申请信息向节点2申请第二个数据时隙用来发送数据。之后，如果节点1的数据依然很多，那么节点1就可以继续续约2个数据时隙并且申请第三个数据时隙，直到达到网络达到负载上限。

当节点1的数据变少时，节点1就必须立刻通告周围邻居自己放弃使用数据时隙，并删除自己的续约信息，以使其他节点可以使用这些数据时隙。

2.4 CA-TDMA的虚拟数据和竞争时隙交换

为了降低数据的传输延迟，CA-TDMA协议加入虚拟数据和竞争时隙交换的思想。虚拟数据思想是指节点在申请数据时隙时要考虑到由RTS信息提供的虚拟数据信息这个因素。具体来说，例如在图8拓扑中，对于数据流1，当节点N(N=2、3)收到节点N－1的RTS申请请求之后，节点N就会根据RTS信息记录一个虚拟数据信息。而当节点N自己的竞争时隙到来的时候，如果节点N的虚拟数据信息的优先级大于数据缓冲区内所有数据的优先级，那么节点N会依据虚拟数据信息发送对于虚拟数据的申请请求。最终构成一个连续的申请，使得在一个超帧内，完成节点1向节点4数据发送。

图8 四节点拓扑图

但是对于图8中的数据流2，那么仅仅依靠虚拟数据就没有办法降低延迟的。因为节点N(N=2、3)在收到节点N+1的RTS申请请求之后，已无法再去申请数据时隙。所以CA-TDMA协议更提出了竞争时隙交换的思想以辅助解决这种情况，竞争时隙交换思想就是决定如何交换竞争时隙，主要由算法2确定。

算法2 竞争时隙交换的确定算法

对于图8所示的数据流2，根据算法2，就出现如图9所示的竞争时隙交换。最终节点1、2、3、4的竞争时隙的位序会改变为4、3、2、1。在加上虚拟数据的思想，就可以实现在一个超帧内对数据流2的数据进行正确的发送。

图9 4节点竞争时隙交换

3 仿真与性能分析

3.1 仿真参数

使用仿真工具为NS2[12]，具体仿真参数如表1。

表1

3.2 仿真结果与性能分析

本文针对不同的发包频率，在以20 m/s的移动场景中，对CA-TDMA协议和DTDMA协议在性能上做了对比分析，在相同的环境中，实验结果如下:

结合图10和图11我们可以看出，CA-TDMA协议和DTDMA协议的分组投递率都没有高于85%。这是由于节点移动所导致的一定时间内路由信息与实际拓扑信息不对等而产生的丢包。并且通过仿真结果来看，这部分丢失的数据包大约占到所有数据的17%左右。

图10 整个网络的平均分组投递率

图11 高优先级数据的分组投递率

通过图10和图11我们还可以看出，随着发包频率的增加，CA-TDMA协议在平均分组投递率和高优先级数据的分组投递率上较DTDMA协议有着更为优异的表现，这是由于CA-TDMA协议是无竞争的，所以不会因为高网络负载而产生竞争时隙的冲突，也就不会造成的数据时隙的浪费，从而提高了分组的投递率。并且不产生冲突也就意味着数据能够正常的发送，会减少数据在缓冲区内的停留时间，会减低数据的传输延迟。

图12 高优先级数据的传输延迟

通过图12可以看出，在高优先级数据的传输延迟性能方面，CA-TDMA表现的比DTDMA更为优秀，这是因为CA-TDMA协议可以通过竞争时隙交换和虚拟数据的思想，尽量使得高优先级数据能够在一个超帧内传输到目的节点。

4 结语

本文提出了一种新型的无竞争的MAC协议CA-TDMA。仿真结果说明CA-TDMA相比DTDMA协议，在平均分组投递率、高优先级数据分组投递率、高优先级数据传输延迟性能方面均有明显的提高。当然，MAC协议的性能和具体的网络拓扑息息相关，如何使CA-TDMA协议能够适用于更多的网络拓扑，会是一个重要的后续需要研究的问题。

[1]王金龙，王呈贵，吴启辉，等.Ad Hoc移动无线网络[M].北京:国防工业出版社，2004:3－180.

[2]Rehman H，Wolf L.A Multihop IEEE 802.11 MAC Protocol for Wireless Ad Hoc Networks[C]//Distributed Computing Systems Workshops，2009.ICDCS Workshops’09.29th IEEE International Conference on，Braunschweig，Germany，2009:432－439.

[3]Youn-Chul Cho，Sun-Joong Yoon，Young-Bae Ko.Modifying the IEEE 802.11 MAC Protocol for Multi-Hop Reservation in MIMC Tactical Ad Hoc Networks[C]//Advanced Information Networking and Applications(WAINA)，2011 IEEE Workshops of International Conference on，Suwon，South Korea，2011:178－183.

[4]Xiao Yongkang，Yin Xunhe.Performance Modeling and Analysis of IEEE 802.11 MAC Protocol in Multihop Ad Hoc Networks[C]//Wireless CommunicationsNetworkingand MobileComputing(WiCOM)，2010 6th International Conference on，Beijing，China，2010:1－5.

[5]Jian Ni，Bo Tan，Srikant R.Q-CSMA:Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks[C]//Infocom，2010 Proceedings IEEE，Urbana，USA，2010:1－5.

[6]Bokri J，Ouni S，Kamoun F.A Novel Reservation Approach for TDMA-Based Ad Hoc Networks[C]//Communications and Networking(ComNet)，2010 Second International Conference on，Tunis，Tunisia，2010:1－7

[7]Li Jianping，Wakahara Y.Time Slot Assignment for Maximum Bandwidth in a Mobile Ad Hoc Network[C]//Wireless Pervasive Computing，2007.ISWPC 07.2nd InternationalSymposium on，2007.

[8]Djukic P，Valaee S.Link Scheduling for Minimum Delay in Spatial Re-Use TDMA[C]//Infocom 2007，26th IEEE International Conference on Computer Communication，Toronto，Canada，2007:28－36

[9]Kamruzzaman S M，Alam M S.Dynamic TDMA Slot Reservation Protocol for Cognitive Radio Ad Hoc Networks[C]//Computer and Information Technology(ICCIT)，2010 13th International Conference on，Yongin，South Korea.2010.142－147

[10]Jae-Ryong Cha，Kwang-Chun Go，Jae-Hyun Kim.TDMA-Based Multi-Hop Resource Reservation Protocol for Real-Time Applications in Tactical Mobile Ad Hoc Network[C]//MILCOM 2010，Suwon，South Korea，2010:1936－1941

[11]Braten L E，Voldhaug J E，Ovsthus K.Medium Access for a Military Narrowband Wireless Ad-Hoc Network;Requirements and Initial Approaches[C]//Milcom 2008.IEEE 2008:1－7

[12]于斌，孙斌，温暖，等.NS2与网络模拟[M].北京:人民邮电出版社，2007:46－133