低占空比、低碰撞的异步无线传感器网络MAC协议

李哲涛，朱更明，王志强，裴廷睿，潘高峰

（1. 湘潭大学 信息工程学院，湖南 湘潭 411105；2. 国防科学技术大学 计算机学院，湖南 长沙 410073；3. 湘潭大学 智能计算与信息处理教育部重点实验室，湖南 湘潭 411105；4. 湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201；5. 西南大学 电子信息工程学院，重庆 400715）

1 引言

无线传感器网络（WSN, wireless sensor network）由分布在一定区域内大量电池供电的传感器节点组成，采用无线通信的方式形成多跳自组织网络。由于其监控区域广、无人值守等优点，WSN被广泛应用到农业种植、医疗监控、智能家居、智能交通等生活的各个领域，尤其是灾后重建、突发事件监控等[1]。电池能量直接影响传感器和网络生存周期，因此，研究一种低耗能、轻负载协议成为WSN领域的热点。媒体访问控制（MAC, medium access control）协议是数据报文和控制消息在无线信道上进行收发的直接控制者，也间接影响上层路由协议和传输控制协议性能。因此，高效的MAC协议是保证WSN数据服务质量（QoS, quality of service）的基础[2]。

根据节点时间是否同步，可将现有MAC协议分为2类：同步和异步MAC协议。同步MAC协议（如 S-MAC[3]、TMAC[4]、SCP[5]和 DW-MAC[6]）通过节点同步的唤醒/休眠机制来减少能量消耗，但全网时间同步会带来不可忽略的能量消耗[7,8]。

异步 MAC协议又可分为由发送节点发起的MAC 接入协议（如 B-MAC[9]、X-MAC[10]、O-MAC[11]和Wise MAC[12])和由接收节点发起的MAC接入协议（如RI-MAC[13]）2种类型[14]。由发送节点发起的MAC接入协议是指由发送者发送前同步码报头（preamble）来通知目标节点准备接收数据；由接收节点发起的MAC接入协议是指发送节点醒来侦听，等待接收节点发送的信标（beacon）分组的到来再发送数据。异步MAC协议无需时间同步，并且异步周期的工作模式能减少网络中流量猝发所带来的碰撞。一般来说，在异步MAC协议中，发送节点的占空比要远比接收节点的占空比高。

B-MAC是一种基于CSMA的异步MAC协议。它通过使用低能耗侦听和持续的前同步码报文实现低能耗通信。另外，它通过动态调节休眠时间表来改变网络流量负载。然而，串音问题和冗长的前同步码带来了较大的能量损耗。

X-MAC通过使用多个较小的前同步码报文来解决B-MAC中的串音问题。通过在前同步码中嵌入目标节点地址引导邻居中非目标接收节点进入休眠，达到节能的目的。然而，持续的前同步码仍然占据着信道，降低了信道利用率。

Wise MAC通过固定的唤醒间隔减少前同步码的长度。同时，发送节点通过采样目标节点时间表预测其下一次唤醒时间，降低了占空比。该协议虽然减少了空闲监听开销，但固定的时间表易导致连续的碰撞。

RI-MAC是由接收节点发起建立连接的异步MAC协议，发送节点只需醒来侦听目标节点的信标帧而不用占据信道，提高了信道利用率。然而，发送节点平均仍需半个周期等待目标节点的信标帧，空闲侦听耗能较大。

另外，现有的MAC协议大多采用二进制指数退避算法[14]来解决分组丢失重传问题。这类算法总是给予最后一次发送成功的节点以最大的优先权，易导致不公平现象。当网络节点较多时，节点每次成功发送后都将竞争窗口重置为最小值，易引起碰撞。

为降低能耗、减少数据碰撞，本文提出了一种由发送节点发起建立连接的异步低占空比、低碰撞的PB-MAC（predict-base MAC）协议算法。在PB-MAC中，节点通过伪随机数生成伪随机唤醒时间表。发送节点可通过获取接收节点的随机种子、当前时间和最近一次唤醒时间信息精确地推导出接收节点的下一次唤醒时间。与其他具有预测功能的MAC协议(如Wise MAC[12])相比，在PB-MAC中，节点能快速预测目标节点的醒来时间，并能减少碰撞。PB-MAC只需在预测目标节点唤醒时间侦听信道，因此，在发送节点和接收节点都能保持极低的占空比。另外，PB-MAC报头仅需携带极小量的预测信息，具有通信开销小和报头短的特征。

2 PB-MAC的算法设计

PB-MAC的目标是设计一种以发送节点发起建立连接的低占空比、低碰撞的异步MAC协议。

2.1 基本工作原理

PB-MAC协议基于RTS/CTS/Data/ACK的通信过程，节点随机唤醒侦听，如果在一个给定的信道侦听时间（TA，time active）内没有发生激活事件，则进入休眠状态。节点醒来后侦听信道时间需满足：

其中，RTT为端到端往返时延，sT为节点由休眠状态启动为工作状态所需要的时间。

图1 PB-MAC协议的基本机制

在PB-MAC中，节点首次在[0,T]（T为节点唤醒的平均时间周期）之间随机唤醒进入活动状态，之后仍采取随机唤醒机制。图1为PB-MAC协议的基本机制，图中向上的箭头表示发送消息，向下的箭头表示接收消息，上面部分的信息流表示节点一直处于侦听方式下的消息收发序列，下面部分的信息流表示采用PB-MAC协议时的消息收发序列。图1中节点首次在14 ms唤醒，随后依随机数89、129和76在103 ms、232 ms和308 ms分别唤醒。

2.2 伪随机唤醒时间表机制

为了预测目标节点的唤醒时间和避免邻居节点唤醒时间频繁接近，PB-MAC中每个节点采用伪随机唤醒时间表。节点通过与邻居节点共享随机种子来推导对方产生伪随机唤醒时间表的伪随机数。

为了使节点间随机种子不同并且可在相邻节点种子相近的情况下更改，节点产生伪随机数的随机种子Seed采用线性同余(LCG, linear congruential generator)[15]的方法产生，如式(2)所示。

其中，m(m＞0)是模数，a(0

其中，RandNum为每调用一次rand方法产生的随机数。节点将产生的随机数RandNum作为节点唤醒时间间隔，生成伪随机时间表。

因此，通过获取邻居节点的随机种子同样可以推导出其唤醒时间表的唤醒时间间隔。

2.3 预测目标节点唤醒时间算法

PB-MAC协议的报头（beacon分组）包含节点的随机种子Seed、最近一次唤醒时间lastT 和节点当前时间curT 。节点根据收到目标节点的 beacon分组可据式(2)和式(3)计算出其下一次唤醒时间NextTimeWakeup。

其中，locT 为本地节点时间，diffT 为本地节点与目标节点的时差。

图 2是发送节点 S通过目标接收节点 R的beacon分组来预测R下一次唤醒时间的伪代码。其算法的核心思想是：如果R的相关参数未知，则立即侦听信道；否则根据R的随机种子、当前时间和最近一次唤醒时间信息计算R的下一次唤醒时间。

图2 节点S预测节点R唤醒时间的伪代码

其中，Seed[R]为目标接收节点 R的随机种子，currentTime[R]为 R的当前时间，Tcur[R]为 R发送beacon分组的时间，Tlast[R]为R的最近一次唤醒时间，nextWakeupTime[R]是预测下一次R的唤醒时间(初始值为R的最近一次唤醒时间)。

图3 发送节点与接收节点数据传输

如图3所示，发送节点S首次向目标接收节点R建立连接需要一直醒来侦听R的beacon分组，S在收到R的beacon分组后向R发起建立连接传输数据。当S下一次需要向R发送数据时，根据式(3)和式(4)来精确推导目标节点唤醒时间，在此时间唤醒侦听R的beacon分组，并在收到R的beacon分组后向R发起建立连接。

综上所述，PB-MAC报头beacon分组仅需携带2 byte Seed、4 bytelastT 和4 bytecurT 共10 byte的预测信息，即可完成对邻居节点唤醒时间的预测，具有报头短和低开销的特征。

2.4 预测重建连接机制

针对2个隐藏终端节点可能同时向目标节点发起建立连接请求而导致建立连接失败的情况，PB-MAC采用随机延退和释放预测的方法规避冲突和提高重连接效率。

随机延退是指多个发送节点收到同一目标接收节点R的广播beacon分组后，在[0,cT]内各自随机延退一段时间dT，再向R发起建立连接，实现规避冲突，提高连接成功率，dT需满足

其中，Tdelay为端到端传输时延，即 R TT / 2。结合式(1)和式(5)可得：Td≤RTT/2，因此取Tc=RTT/2。

以图4为例，在发送节点S1和S2同时收到R的beacon分组后不是立即向R发起建立连接，而是在延退[0, /2RTT ]区间的随机时间后再向R发起建立连接。由于 S2延退时间小于 S1延退时间，所以S2成功与R建立连接。

针对建立连接失败的节点，PB-MAC采用释放预测机制来重建连接。具体预测规则分以下情况进行计算。

图4 预测重建连接机制

1) 若收到目标节点发送给其他节点的CTS帧，则目标节点传完数据后释放连接的预计时间nextT 为

其中，hT为处理单位数据的时间，dIR为目标节点还需接收数据分组的个数，ctsT 为收到目标节点CTS帧的时间。

2) 若收到目标节点发送给其他节点的Data数据分组，则目标节点传完数据后释放连接的预计时间nextT 为

其中， I Sd为目标节点还需发送数据分组的个数，Tdata为收到目标节点Data数据分组的时间。

3) 其他情况，立即进入休眠。如图4所示发送节点S1在建立连接失败后，收到目标节点R发送给节点S2的CTS帧。S1根据收到R的CTS帧，依式(6)推导R接收完数据释放的连接时间，并在此时间向R发起建立连接。

2.5 预测数据重传机制

基于无线网络的不稳定性和网络去拥塞的时滞性，在出现分组丢失时，PB-MAC要求发送节点和接收节点尽快进入休眠模式，达到降低占空比的目的。

在分组丢失后，发送节点和接收节点的具体表现为：发送节点首先启动2.3节所述的预测目标唤醒算法计算接收节点下一次的唤醒时间，然后转入休眠状态；接收节点在没有收到后续有效数据或者数据已经传送完毕时进入休眠状态。

由于发送节点和接收节点均进入休眠状态，等待目标节点下一次醒来再重传该数据。如图3所示，当S发送第二个数据分组出现分组丢失后马上进入休眠，在R第3次醒来后再重传该数据。

3 仿真与分析

3.1 仿真参数与环境说明

实验采用OMNet++软件对比分析了PB-MAC、RI-MAC和X-MAC的性能，采用MATLAB辅助分析实验数据。为了保障3个协议的可比性，分别对每个协议进行如表1所示设置。

表1 协议参数设置

在PB-MAC中，为保障节点间随机种子尽可能不相近，随机种子产生式的参数a、c、m分别设置为20、7和999。

实验模拟运行500 s，节点每隔[500，1 500] ms产生一个数据分组，数据传输时延设定为5 ms。为了检测节点的消息负载量，假设节点的消息缓冲区是无限大。仿真中测量以下指标。

1) 平均占空比：节点处于侦听状态占整个实验时间的比率。

2) 数据传递率：基站接收到的数据总量占所有节点产生的数据总量的比率。

3) 端到端的数据延迟：从节点产生数据或收到数据开始到该数据成功被下一跳节点接收的平均时间。

4) 消息负载量：节点在整个实验时间中消息队列的最大数据量。

5) 发送耗能：发送消息消耗的能量，以发送单位数据消耗1个单位的能量来计量。

6) 碰撞次数：节点在激活状态同时收到2个及以上发送节点数据的次数。

3.2 随机网络评估

在900 m×900 m的方形区域内随机部署49个节点，在中心部署1个基站，节点通信半径为200 m。表2为PB-MAC、RI-MAC和X-MAC在消息传递率、占空比、端到端延迟、最大消息负载量、发送数据耗能和平均碰撞次数指标的对比。

表2 随机网络性能对比

表2表明，PB-MAC在保持高传递率和低延迟的情况下，占空比、平均发送数据耗能和碰撞次数3个性能分别比RI-MAC降低了68.60%、24.75%、68.05%，比 X-MAC降低了 64.39%、64.05%、70.54%。这是因为PB-MAC通过精确估计目标节点的唤醒时间，避免像RI-MAC和X-MAC那样每次醒来侦听信道，等待与目标节点建立连接。在随机网络中由于节点分布不均，容易导致数据分组丢失，而PB-MAC协议在数据分组丢失后采用2.5节所示的快速进入休眠状态的重传机制，故在延迟性能上比RI-MAC和X-MAC略高。

当发送节点有数据需要发送时，RI-MAC采用被动等待方式，X-MAC采用不断向目标节点发送请求分组的主动建立连接方式，所以RI-MAC的发送耗能远小于X-MAC。PB-MAC中的预测机制使得发送节点与接收节点建立起连接的无效请求较少，发送数据耗能也较小。

表2显示在消息传递率相近的情况下，发送数据耗能与碰撞次数成正相关。由于RI-MAC碰撞窗口每次从0开始增加，而X-MAC的碰撞窗口固定为32，故RI-MAC的碰撞次数偏高。PB-MAC采用预测重建连接机制能提高连接的成功率和减少拥塞时的无效传输，故碰撞次数最少。

3.3 网格网络评估

在网格网络中，基站处于网络的中央位置，每个节点与其邻居节点的距离为100 m，节点通信半径为100 m。网格规模从4×4（16节点）逐步扩大到 9×9（81 节点）。

图5是PB-MAC、RI-MAC和X-MAC在网格网络环境中的各项性能对比图。图5(a)是PB-MAC、RI-MAC和X-MAC协议在网格网络环境中的占空比性能对比图。由于RI-MAC和X-MAC协议中发送节点平均需醒来等待半个RTT的空闲侦听时间，才能与目标接收节点建立起连接，而使用预测机制的PB-MAC等待的侦听时间接近0。因此，PB-MAC中发送节点具有占空比较低的显著优势。RI-MAC中发送节点避免了X-MAC中大量的preamble分组占用信道，信道利用率较高。因此，RI-MAC较X-MAC略占优势。

图5（b）是PB-MAC、RI-MAC和X-MAC协议在网格网络环境中的平均发送消息能耗对比图。由于 PB-MAC采用预测机制使得发送节点与目标节点成功建立连接的几率较高，仅需要少量的RTS请求分组，失效请求少。因此，平均发送消息耗能单位在 3个协议中最少。X-MAC中大量无效的preamble请求分组使耗能较RI-MAC高。

图5（c）是PB-MAC、RI-MAC和X-MAC协议在网格网络环境中的平均和最大碰撞次数对比图。3 种协议在奇网格（5×5、7×7、9×9）和偶网格（4×4、6×6、8×8）下的平均碰撞次数分别呈现递增状态。另外，由于基站一直处于侦听状态，偶网格中的碰撞次数要明显多于奇网格。

图5(d)是PB-MAC、RI-MAC和X-MAC协议在网格网络环境中的端到端延迟对比图。3种协议的端到端延迟随网格规模的变化基本保持一致。RI-MAC与X-MAC以付出高占空比的代价减少延迟，而PB-MAC以高效的预测重建连接机制，保障低延迟。

图5 网格网络性能参数对比

图 5（e）是 PB-MAC、RI-MAC和 X-MAC协议在网格网络环境中的分组传递率对比图。从图中可以看出，当网络边缘节点大于7时，所有协议分组传递率急剧下降，这与图 5（d）中网络边缘节点大于 7后延迟剧增相对应。实验发现，当规模超过 7×7（49节点）后，网络开始出现拥塞。

图5（f）是PB-MAC、RI-MAC和X-MAC协议在网格网络环境中的平均和最大消息负载量对比图。在网络边缘节点数小于7时，3种协议的平均消息负载量基本维持在 20左右。当网络边缘节点数大于7后，平均消息负载量急剧上升，也印证了网络出现拥塞。

总体来看，PB-MAC在占空比、发送消息耗能、碰撞次数3个性能上表现出明显优势。另外，在网络出现拥塞之前，随着节点规模的增大，PB-MAC在占空比、发送消息耗能、最大碰撞次数和平均碰撞次数指标上基本呈线性增长，稳定性好。在网络出现严重拥塞之后，在占空比、碰撞次数指标上，PB-MAC仍优于RI-MAC和X-MAC。

4 结束语

本文着重研究如何优化异步MAC协议来减少网络耗能和提高通信质量，提出了一种低占空比、低碰撞的异步无线传感器网络 MAC协议——PB-MAC协议。该协议以共享随机种子为基础，通过预测方式估计邻居节点的唤醒时间表，达到降低占空比的目的；通过预测重连接机制和预测数据重传机制，避免数据碰撞和实现高效重传。仿真结果表明：在随机网络和网格网络中，PB-MAC协议在保持低延迟和高传递率的情况下，其占空比、碰撞次数和能耗方面明显优于RI-MAC和X-MAC。

[1] 马祖长, 孙怡宁, 梅涛. 无线传感器网络综述[J]. 通信学报, 2004,25(4)：114-123.MA Z C, SUN Y N, MEI T. Survey on wireless sensors network[J].Journal on Communications, 2004, 25(4)：114-123.

[2] 李瑞芳, 李仁发, 罗娟. 无线多媒体传感器网络 MAC协议研究综述[J].通信学报, 2008, 29(8)：111-123.LI R F, LI R F, LUO J. Survey of MAC protocol in wireless multimedia sensor networks[J]. Journal on Communications, 2008, 29(8)：111-123.

[3] WEI Y, HEIDEMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks[A]. Proceedings of the IEEE INFOCOM'02[C]. New York, NY, USA, 2002.1567-1576.

[4] DAM T V, LANGENDOEN K. An adaptive energy-efficient MAC protocol for wireless sensor networks[A]. Proceedings of the First International Conference on Embedded Networked Sensor Systems(SenSys'03)[C]. Los Angeles, CA, USA, 2003.171-180.

[5] WEI Y, SILVA F, HEIDEMANN J. Ultra-low duty cycle MAC with scheduled channel polling[A]. Proceedings of the 4th ACM SenSys Conference(SenSys'06)[C]. Boulder, CO, USA, 2006.321-334.

[6] SUN Y, DU S, GUREWITZ O. DW-MAC： a low latency, energy efficient demand-wakeup mac protocol for wireless sensor networks[A].Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc'08)[C]. Hong Kong, China,2008.53-62.

[7] 胡玉鹏, 林亚平, 周四望. 面向异步通信机制的无线传感器网络及其MAC协议研究[J].计算机学报, 2011, 34(8)：1163-1477.HU Y P, LIN Y P, ZHOU S W. Asynchronous communication mechanism oriented wireless sensor networks and MAC protocols[J]. Journal on Computers, 2011, 34(8)：1163-1477.

[8] 李哲涛，李仁发，魏叶华. 无线传感器网络中时间同步与测距协同算法[J]. 计算机研究与发展, 2010,47(4)：638-644.LI Z T, LI R F, WEI Y H. Coordinated algorithm for time synchronization and distance measurement in wireless sensor networks[J]. Journal of Computer Research and Development, 2010,47(4)：638-644.

[9] POLASTRE J, HILL J, CULLER D. Versatile low power media access for wireless sensor networks[A]. Proceedings of the Second ACM SenSys Conference (SenSys’04)[C]. Baltimore, MD, USA, 2004. 95-107.

[10] BUETTNER M, YEE G V, ANDERSON E. X-MAC： a short preamble MAC protocol for duty-cycled wireless sensor networks[A]. Proceedings of the 4th ACM SenSys Conference (SenSys'06)[C]. Boulder, CO,USA, 2006.307-320.

[11] CAO H, PARKER K W, ARORA A. O-MAC： a receiver centric power management protocol[A]. Proceedings of the 14th IEEE International Conference on Network Protocols(ICNP'06)[C]. Santa Barbara, CA,USA, 2006.311-320.

[12] WEI Y, SILVA F, HEIDEMANN J. Ultra-low duty cycle MAC with scheduled channel polling[A]. Proceedings of the 4th ACM SenSys Conference(SenSys'06)[C]. Boulder, CO, USA, 2006.321-334.

[13] SUN Y, GUREWITZ O, JOHNSON D B. RI-MAC： a receiver initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[A]. Proceedings of the 6th ACM SenSys Conference (SenSys'08)[C]. Raleigh, NC, USA, 2008.1-14.

[14] Wireless LAN medium access control (MAC) and physical layer (PHY)specifications[EB/OL]. www.ieee.org, 1997.

[15] KNUTH D E. 计算机程序设计艺术, 第2卷： 半数值算法[M]. 北京： 人民邮电出版社, 2010.KNUTH D E. The Art of Computer Programming, Volume 2： Seminumerical Algorithms[M]. Beijing： Posts & Telecom Press, 2010.