基于时间调度表的无线传感器网络MAC协议

龙昭华，马永建，蒋贵全，陈丹丹

（重庆邮电大学 计算机系统结构研究所，重庆400065）

0 引 言

无线传感器网络是由部署在监测区域内的大量微型节点组成，并且通过无线通信形成一个自组织网络系统。传感器节点是通过电池供电的，所以在传感器网络中，能量是最重要的。而在整个无线传感器网络的生命周期中，能量浪费最多的是节点的空闲监听部分，浪费最少的是节点的睡眠期。针对传感器的节能需求，许多MAC协议提出了工作／休眠机制，比如S－MAC[2]，但是它使网络的时延增加，吞吐量下降。

为了减少网络的延迟时间，PA－MAC[3]（Pattern－MAC）在S－MAC和T－MAC[4]协议的基础上，进一步减少了空闲侦听的时间。PA－MAC减少了空闲侦听的时间，但是传输的一些模式帧，并没有实际意义。而且协议的执行非常复杂，增加了节点的控制开销。总之，这些协议[5]并不能使节点在多跳网络传输中保持监听状态，它们仍然存在很长的延迟时间。为了减少延迟时间，我们提出了AST－MAC协议，AST－MAC协议跟S－MAC类似，也是基于工作／休眠机制。

在这篇论文中，我们设计并实现了AST－MAC协议，我们增加了提高吞吐率的算法，这个算法让节点保存下一个数据分组转发的时间调度表。通过节点之间的数据分组的传输，从而形成了节点监听／睡眠的同步。利用这个算法，网络的吞吐量提高了很多。

1 AST－MAC协议设计和改进

1.1 AST－MAC的设计

AST－MAC协议算法依赖于精确的时钟信息，因此节点间的时钟同步相当重要。节点的全局时钟同步通过转发一个同步包来完成。我们提出了一个基于帧格式全局时钟

在全局同步阶段，所有节点处于监听状态。首先叶节点发送一个同步控制帧AST－RTS，通过多跳传输这个控制帧，每个节点收到这个控制帧，保存自己的调度表。ASTRTS帧采用了跨层的路由信息，Source＿id发送数据帧的节点号，Target＿id是发送数据帧的下一跳节点号，Send＿time是节点发送数据帧的时间，Next＿send＿time是节点发送下一个数据帧的时间，Info＿type是发送数据帧同步[6]的思想。首先，我们给出AST－MAC协议中各个包的帧格式，如图1所示，下面是一些帧的格式。

从图1可以看出同步控制帧AST－RTS和数据帧DATA的格式基本一致。因此两个节点从准备发送同步控制帧，并且传输同步控制帧，直至收到同步控制帧的时间间隔与节点传输数据帧近似一致。我们根据这个特点提出全局同步机制。AST－MAC的基本设计如图2所示。的类型。

首先，叶节点A记下自己发送控制帧AST－RTS的时间Tsend＿time和发送下一个数据帧的时间Tnext＿send＿time，然后保存自己 （叶节点）的调度表，见表1。

并且转发到下个节点B，节点B收到AST－RTS帧后记下接收时间Trecv＿time，则叶节点A传输给节点B的时间为如下

表1 叶节点的调度

于是可以确定B节点接收下一个数据帧的时间，根据控制帧AST－RTS和数据帧DATA的格式基本一致，节点A，B之间传输数据帧DATA所对应的时间也应该是TAB，而之前B节点接收到的控制帧的字段里有A节点发送下一个数据帧的时间Tnext＿time＿send＿A，可以确定B节点的接收时间如下

而实际在射频模块[7]中，从睡眠状态转化为监听状态需要时间Tsleep＿tx，见表2。

表2 射频模块的状态转换

所以说节点B接收A节点发出下一个数据帧时间 （实际上是节点B的被唤醒时间）如下

而从接收状态转换到发送状态需要时间Trx＿tx，所有调度表中next＿send＿time的值，如下

计算完毕之后，保存自己 （非叶节点）的调度表，见表3。

表3 非叶节点的调度

然后B根据跨层的路由信息将控制帧AST－RTS转发给下一跳节点C，节点C收到控制帧AST－RTS之后，更新AST－RTS帧的发送时间、发送帧的节点号和发送帧的下一跳节点号，并且更新调度表中的next＿recv＿time和next＿send＿time的字段，此时，如图2，节点A并没有在睡眠状态，而是在监听状态，也会同时接收到节点B转发的控制帧AST－RTS，得到A之前发送的隐式确认，并且将叶节点A调度表中的send＿time置0，表示A发送的控制帧已经成功转发，之后A进入睡眠状态，所以说AST－RTS帧有RTS和CTS的两个功能，并且在很短的监听时间内可以转发更多的跳数。在AST－RTS帧到达最后目的节点之前，节点A与节点B的握手机制也同样在其它节点之间一直重复着。AST－RTS帧到达最后目的节点E，由于后面没有节点了，E不需要转发AST－RTS控制帧了，所以它的上一跳节点得不到这个隐式确认，则节点E必须发送显式确认帧LST－ACK。

在全局同步阶段，所有节点 （非最终目的节点）接收到隐式确认帧之后，都进入睡眠状态，如图2，在sleep状态，此时节点不能发送或者接收数据帧。在射频处于接收状态，节点接收它下一跳的确认帧，然后节点进入sleep状态，此时不会接收到其它的节点发出的任何数据帧。显然，这些节点大部分时间都在睡眠状态。

在数据传输阶段如图2，与全局同步阶段类似。节点根据自己的调度表唤醒自己，接收或者转发数据帧，当叶节点A调度表中next＿send＿time时间到了，节点A及时唤醒自己，将数据帧DATA转发给下一跳节点B，并且更新数据帧DATA的字段和节点A调度表next＿send＿time的值，此时经过TAB（数据帧从A传输给B的时间）后，由于先前节点B的调度表中已经有next＿recv ＿time字段，所以B节点被唤醒处于监听状态了，接收到数据帧之后，射频模块的状态从接收状态到发送状态，更新数据帧DATA的字段和调度表next＿recv＿time，next＿send＿time的值，将数据帧DATA转发给下一跳节点。同时A也会收到，相当于A节点之前发送的隐式确认，接收完之后，进入睡眠状态。最后一个节点需要发送一个显式的确认LAST＿ACK。很显然，节点只有在转发数据帧、接收确认帧和数据帧的时候处在工作状态，其余都处于睡眠状态。通过保存节点的时间调度表，AST－MAC减少了数据帧转发的延迟时间，并且，消除了列如CTS和ACK控制包的使用，从而减少了不必要的能量消耗。

1.2 调度冲突处理

在调度表保存期间，一些节点可能需要多个调度表，对于单个节点而言，调度时间可能会相同，导致传输数据帧发送冲突，也叫做调度冲突。图3中显示了调度冲突处理算法的处理流程。在图3中，一个路由是从节点A到节点E，另外一个路由是从F到G。首先，节点F传输全局同步控制帧到节点G。节点D保存节点F到节点G的调度表。然后节点A传输全局同步控制帧到节点E，此时节点D又保存节点A到节点E的调度表。在实际应用中，节点D的两个调度表中的next＿send＿time的值大体接近，也就是D发送下一个数据帧，会产生冲突。此时节点D发送错误调度确认帧ESK （ERROR－SCUDULE－ACK），通知这条路由上一跳节点C，C收到ESK帧后，在调度表中调整节点C发送时间Tadjust＿c，ESK帧包含时间戳t这个字段，Tadjust＿c是通过之前的调度表中的发送时间向下平移t，如下

节点D中的调度表 （路由从节点A到E）的next＿recv＿time，next＿send＿time字段的值也必须平移t个单位，如下

通过以上算法，避免了调度冲突。

1.3 数据错误传输处理

AST－MAC协议中，每个节点保存了自己的调度信息，并且根据自己的调度信息转发数据帧，所有节点工作／休眠的时间是同步的。因此，如果一个路由中的两个节点数据传输失败，接下来后面所有节点的数据传输都将会失败。

为了避免连锁反应的数据帧转发失败，我们采用了与类似于调度冲突的算法，利用时间平移，如图表中所示，通过时间平移的方法来恢复节点之间的正常传输，这个平移时间的大小为如下

式中:Tdata1——两个节点之间传输数据帧的时间，Tdata2——收到隐身确认的时间，Δt——节点处理数据帧的时间。Tshift包括了一个节点的发送、接收确认时间和处理数据帧的时间，可以通过这个时间来判断数据帧的传输是否发生了错误。

我们可以通过图4中看出，节点B向节点C传输数据，当节点C收到数据帧之后，节点C发现这个数据帧是有问题的。于是节点C放弃了转发这个数据帧，并调整自己的调度表，将自己的调度表中的所有时间向下平移Tshift，节点B在一定时间内没有得到隐式确认，则将自己的调度表中的send＿time向下平移Tshift。同样的，后面节点在监听时间内没有收到任何数据帧，则都将自己的调度表的时间向下平移Tshift时间，然后进入睡眠状态。

通过这种方法，节点之前保存的调度表并没有丢弃，而是被充分利用了。但是，太多的平移调度会消耗更多的能量，所以说，对于整个网络而言，平移调度的次数是受限制的。整个网络时间平移一次后，基本恢复正常了。

2 仿真测试与性能评估

2.1 实验的主要目标

我们实验的主要目标是通过与其它的一些MAC协议如S－MAC，802.15.4[8]，PAMC，对 AST－MAC协议的性能进行评估。我们通过3个性能指标能衡量MAC协议性能:端 到端的平均延迟[9]；吞吐率[9]，即单位时间接收数据帧的总字节数；网络的能量消耗[9]，即完成某项任务的消耗的总能量。

2.2 端到端的平均延迟

每个MAC协议的端到端平均延迟如图5所示。为了测量这个延迟时间，网络中的源节点和目标节点的时钟是同步的。首先，源节点将发送的起始时间加入发送帧，然后通过最终的目标节点计算端到端的平均延迟。与其它MAC协议相比，尽管AST－MAC也采用侦听和睡眠交替的策略，但它具有更少的延迟时间。

2.3 吞吐量

通过图6中，我们可以看出AST－MAC协议具有最好的吞吐量。802.15.4协议的吞吐率中略低于AST－MAC协议，因为802.15.4协议随着传输时间间隔减少，碰撞的几率增加，导致数据帧的重传，所以吞吐量略有降低。而SMAC和PA－MAC协议吞吐量降低了很多。

2.4 能量消耗

射频状态时间比如图7所示，其中源节点产生数据帧的间隔时间为2s，测量时间是500s，其中，由图7可以看出，802.15.4协议的大部分时间用在空闲监听上，其它的MAC协议通过侦听和睡眠交替的策略减少了空闲监听时间。在源节点产生数据帧的间隔时间为2s的时候如图6，AST－MAC协议与PAMAC有相同的吞吐率。但是ASTMAC有更少的空闲的监听时间。

一个数据帧被转发所消耗的能量如图8，以上测试的所有协议中，AST－MAC协议消耗最少的能量。

3 结束语

基于非竞争类的MAC[10]大都采用周期性侦听／睡眠机制来减少空闲监听能耗，但是过多的睡眠带来了通信延迟和很低的吞吐量。针对这些问题，本文提出了一种新型的能够实现快速转发的传感器网络AST－MAC协议。这个协议[11]也是基于周期性的侦听／睡眠，它可以减少不必要的能耗，而且大大减少了通信延迟，提高了吞吐量。ASTMAC协议通过转发数据包的时候，保存节点监听／睡眠的时间调度表。在实际应用中，针对存在调度冲突数、数据包错误传输的问题，AST－MAC协议提出了时间戳平移的算法。我们的仿真实验表明AST－MAC协议有延迟低，高吞吐率，能耗低的特点。

[1]ZHANG Jiawei，CHEN Yan，LI Mingbao.Energy－efficient framing MAC protocol for wireless sensor networks[J].Information and Control，2013，35 （22）:95－99 （in Chinese）.[张佳薇，陈岩，李明宝.用于无线传感器网络的高能效分帧MAC协议[J].信息与控制，2013，35 （22）:95－99.]

[2]Liu Ana，Li Lin，Yu Hongyi，et al.An energy—eficient MAC protocol based on routing information for wireless sensor networks[C]／／Hong Kong，China:Proceedings of IEEE Wireless Communications and Networking Conference，2008.

[3]Zhang Ye，Chen He，Jiang Lingge.Modeling the S－MAC protocol in single－hop wireless sensor networks[C]／／IEEE Technology Management Council，IEEE Communications Society.Proceedings of the Symposium on Communication Quality，Reliability，and Performance Modeling of ICC，2008:5－6.

[4]DING Fan，ZHOU Yongming.Adaptive cross－layer optimization strategy for the throughput of wireless sensor network[J].Microcontroller and Embedded Systems，2013，25 （5）:5－8（in Chinese）.[丁凡，周永明.无线传感器网络吞吐量的自适应跨层优化策略[J].单片机与嵌入式系统应用，2013，25 （5）:5－8.]

[5]WANG Mingchao.LR－MAC mechanism for the low－speed wireless sensor networks[J].Zhengzhou Institute of Light Industry（Natural Science Edition），2012，32 （6）:101－104 （in Chinese）.[王明超.一种适用于低速无线传感器网络的LRMAC机制研究[J].郑州轻工业学院学报 （自然科学版），2012，32 （6）:101－104.]

[6]Xiao Y，Pan Y.Differentiation，QoS guarantee，and optimization for real－time traffic over one－hop Ad hoc networks[C]／／IEEE Transaction on Parallel Distributed Systems，2009:100－101

[7]Omprakash G，Rodrigo F.Collection tree protocol[C]／／Proc of the 7th ACM Conf on Embedded Networked Sensor Systems，2009.

[8]Ye W，Heidemann J，Estrin D.An energy－elficient MAC protocol for wireless sensor network[C]／／Proceedings of the 12th IEEE International Conference on Computer Networks，2011:1567－1576.

[9]Randran V，Obraczka K，Gareia－Luna－Aceves J J.energy—eficient，collision—free medium access control for wireless sensor networksp[C]／／Los Angeles，CA:Proc1st int’l Conf on Embedded Networked Sensor Systems，2003:181－192.

[10]JIANG Ziifeng，LU Jiande.Dynamic adaptive CSMA／CA algorithm design and simulation for the IEEE 802.15.4[J].Computer Technology and Development，2010，33 （2）:69－73 （in Chinese）.[蒋子峰，陆建德.IEEE 802.15.4动态自适应CSMA／CA算法设计与仿真[J].计算机技术与发展，2010，33 （2）:69－73.]

[11]Wei Ye，John Heidemann，Deborah Estrin.Medium access control with coordinated adaptive sleeping for wireless sensor networks[C]／／IEEE／ACM Trans Netw，2009:493－506.