低占空比无线传感器网络同步MAC协议最优信标间隔分析

邢宇龙　陈永锐　易卫东　段成华

(中国科学院大学电子电气与通信工程学院　北京　100049)



低占空比无线传感器网络同步MAC协议最优信标间隔分析

邢宇龙陈永锐易卫东段成华

(中国科学院大学电子电气与通信工程学院北京100049)

(xingyulong11@mails.ucas.ac.cn)

能量效率是无线传感器网络协议设计的首要考虑因素.无线传感器网络中，介质访问控制层(medium access control, MAC)协议通过降低节点的占空比来降低网络能耗，延长网络的生命周期.相比其他MAC协议，尽管同步MAC需要周期性分发信标来保持严格的时间同步，但却在数据传输方面具有更高的能量效率.信标间隔的长短直接影响同步MAC能量效率的高低.一方面，较短的信标间隔导致较高的同步开销；另一方面，由于时钟漂移的影响，较长的信标间隔会引起较大的保护时间，从而导致空闲侦听能耗的增加.因此，同步开销和空闲侦听这2部分能耗之间存在一个最优折中.分析了低占空比无线传感器网络同步MAC的最优信标间隔问题，提出了一种采用最优信标间隔的TDMA MAC协议(Opt-TDMA).实验表明：Opt-TDMA的能量效率优于非最优信标间隔的TDMA协议和同步MAC协议SCP-MAC.

信标间隔；同步MAC协议；低占空比；能量效率；无线传感器网络

能耗是无线传感器网络介质访问控制层(medium access control, MAC)协议设计的首要考虑因素.在无线传感器网络中，能耗最高的部分来自于节点的射频通信[1-2].因此，降低节点射频工作占空比(duty cycle)成为MAC协议延长网络生存期的有效途径[3].

射频能耗除数据收发以及其他控制开销外，还包括空闲侦听、串听、碰撞等不必要的额外开销.其中，空闲侦听能耗所占比重最大.减少空闲侦听能耗最有效的办法就是降低节点的占空比.根据文献[4]的定义，节点占空比指的是节点处于活跃状态的持续时间和1个完整的活跃休眠周期的比值.节点在活跃状态打开射频进行数据收发等工作，在休眠状态关闭射频以节省能量.

文献[5-6]将低占空比MAC协议分为异步协议和同步协议2大类.

异步MAC协议(例如B-MAC[7]，X-MAC[8]，A-MAC[9]，PW-MAC[10])节点间的占空比相互独立，邻居节点之间不需要维护对方的调度信息.异步MAC采用低功耗侦听技术(low power listening, LPL)大幅降低了节点空闲侦听能量开销.在每一次发送数据包之前，发送节点首先发送1个持续时间长于接收节点休眠时间的长前导序列(long preamble)，接收节点周期性的探测信道，当检测到发送节点的前导信号时，保持射频打开，准备接收数据.这类协议不需要同步开销，具有较高的能量效率.然而，异步MAC还存在以下不足：1)长前导的存在导致网络数据传输的延时较高；2)长前导会唤醒非数据包目的地址的节点，造成串听.

同步MAC协议分为基于竞争和基于TDMA调度2大类.基于竞争的MAC协议包括S-MAC[11]，T-MAC[12]，DW-MAC[13]等.这类MAC协议引入轻量级的同步机制，实现簇内节点的相对同步，节点在相同时刻唤醒并交换数据.这种方法的最大优点是发送节点不再需要发送长前导序列，有效减少了LPL机制中周期性前导序列采样能耗以及接收节点空闲侦听能耗.由于引入时间同步机制，基于竞争的MAC协议需要额外的同步开销.此外，受信道竞争的影响，网络吞吐量在数据流量较大时会明显下降.

不同于前面介绍的MAC协议，基于TDMA调度的MAC协议[14-15]为每个节点分配1个或多个独立的时隙，节点只有在自己的时隙打开射频传输数据，极大减少了碰撞的概率，有效降低了节点空闲侦听的时间，提高了能量效率.但是，TDMA机制对网络的时间同步有严格要求.因此，时间同步是基于TDMA调度MAC协议实现的基础.

低占空比数据采集网络中，节点间时间同步是通过周期性的交换信标实现的.通过形成1个数据采集树，汇聚节点Sink周期性地向其子节点发送包含时间戳的信标，子节点在收到信标后完成与Sink节点的时间同步.子节点继续分发信标到叶子节点，从而完成子节点和叶子节点间的时间同步.如此循环，最终实现整个数据采集树的全网同步.

信标分发间隔的长短直接影响着网络的能量效率.一方面，信标间隔越短，信标收发频率越高，网络能耗越高；另一方面，信标间隔越长，由于时钟漂移的影响，节点的保护时间(guard time)和空闲侦听时间越长.时钟漂移对同步误差的影响具有时间累积性，较长的信标间隔会导致较大的同步误差，因此需要更长的保护时间.本文分析了同步MAC协议的最优信标间隔问题，提出了采用最优信标间隔的TDMA MAC协议(Opt-TDMA).实验表明，在能量效率方面，本文提出的Opt-TDMA优于非最优信标间隔TDMA协议和SCP-MAC.

1　相关工作

无线传感器网络MAC协议参数最优化的研究主要包括：针对S-MAC存在的不足，T-MAC[12]根据当前数据流量自适应的调整唤醒休眠的占空比，减少了节点处于唤醒状态的时间，从而降低节点的能量开销.T-MAC的缺点是没有专门针对2次唤醒间隔的长度进行最优化分析.X-MAC[8]提出1个近似的优化算法自适应地调整接收节点的占空比.针对不同的传输负载，综合考虑休眠时间和空闲侦听时间最小化网络能耗.在低占空比同步MAC中，文献[4]针对LPL和SCP-MAC，提出最优化的信道探测间隔机制.相比LPL协议，优化的SCP-MAC达到了混合MAC的能量下限，而且可以根据网络流量的变化自适应调整探测间隔.不足的是，这些方法只针对某一类特定的MAC协议进行优化，并不能在其他MAC中通用.

本文提出的Opt-TDMA区别于前人工作的最大特点是它并不是针对某个特定MAC协议定制的最优化方法，而是可以适用于其他同步MAC协议(例如Dozer[5], Koala[16]等)的通用方法.据我们文献调研，本文首次在低占空比无线传感器网络数据采集应用中，针对信标间隔的最优化问题进行分析.

2　系统模型

2.1能量模型

无线传感器网络的基本通信模型如图1所示.A是主节点，B是从节点，A和B可以直接通信.节点B(从节点)周期性地感知数据并将数据发送给节点A；节点A(主节点)周期性地发送信标到节点B.节点B在收到信标后完成与节点A的同步.节点A和B周期性地休眠唤醒，并且它们的休眠唤醒时刻相同，具有相同的占空比.为了能在相同的时刻唤醒，节点A和B必须事先完成时间同步.受时钟漂移影响，节点之间存在同步误差，当节点处于接收状态时，必须提前一小段时间打开射频监听信道，监测信道中是否有数据到来.如果检测到数据包或信标的帧首界定符(SFD)，射频一直保持打开直到接收全部完成；否则，射频立即关闭进入休眠状态.

Fig. 1　Basic communication model.图1　基本通信模型

本文我们只分析射频能耗，不考虑传感器感知能耗和CPU处理能耗等其他相对较低的能耗(与文献[4]类似).射频工作包括侦听、发送、接收、休眠4种状态下的功耗分别表示为Pl，Ps，Pr，Psleep，总能耗由式(1)所示：

E=El+Es+Er+Esleep=

(1)

其中，ts，tr，tsleep分别表示射频处于发送、接收和休眠状态的时间；tlisten表示射频在数据包到来之前空闲侦听信道的时间.

2.2拓扑和帧结构

无线传感器网络树形拓扑结构广泛应用于数据采集场景，本文在树形拓扑的基础上展开研究，如图2所示.在数据采集树结构中，数据流向为从叶子节点到子节点，最后到达Sink节点；信标分发方向为从Sink节点到子节点.节点通常扮演2种角色：父节点和子节点.父节点接收子节点发送的数据包，子节点接收来自于父节点的信标，完成同步.为了简化分析，本文数据和信标的传输采用基于TDMA的MAC协议.

Fig. 2　Data-gathering tree.图2　数据采集树

Fig. 3　The frame structure.图3　帧结构

基于TDMA的MAC协议将整个时间轴分为连续的固定帧长的帧.如图3所示，每一帧分为2n个时隙，其中前n个时隙为信标下行时段(beacon slot)，后n个时隙为数据上行时段(data slot).信标下行时段的最后1个时隙较为特殊，它被定义为网络所有节点的接入时隙(access slot)，用于新节点加入等其他网络维护.

图3为帧结构的示意图.除汇聚节点外，每个节点可能存在5种活跃时隙：信标的发送与接收时隙、数据的发送与接收时隙以及接入时隙.汇聚节点没有信标接收时隙和数据发送时隙，只有其余3种时隙.每个节点在入网时分配1个唯一的时隙号(ID)：SlotNum，这个ID号决定了此节点的信标和数据发送时隙，其中信标的发送时隙为SlotNum，数据的发送时隙为SlotNum+n.而该节点的信标接收时隙和数据接收时隙分别由它的父节点和子节点所对应ID号决定.

当节点处于信标时段时，需要在其父节点的发送时隙接收信标，并在自身的发送时隙广播信标；当节点处于数据包时段时，需要在自身的数据包时隙发送数据(如果数据缓存队列中有数据包的话)，并在自身所有子节点的数据包时隙监听信道，且每一个发送时隙最多发送1个数据包；在接入时隙，所有节点都需要对可能的接入申请包进行监听.除此之外，其他的时隙均为非通信时段，节点在这些时段内进入休眠状态.

3　最优信标间隔

本节的主要内容是在数据采集树拓扑下计算每个节点的平均能耗，并分析Opt-TDMA的最优信标间隔.

在树形拓扑中，父节点发送信标给子节点，子节点发送数据到父节点.考虑1个父节点n个子节点的情形，父节点的能耗是射频在各个工作状态能耗之和，如式(2)所示(休眠功耗Psleep远远低于节点处于其他状态的功率，忽略不计).

(2)

父节点能耗包括发送能耗、接收能耗以及空闲侦听能耗.

1) 发送能耗.发送能耗包括信标的发送能耗和数据的发送能耗.节点广播信标的时间为LsynctBrsync，发送数据包的时间为(n+1)LdatatBrdata.其中，Lsync和Ldata分别代表信标长度和数据包长度;rsync和rdata分别代表信标分发速率和数据包产生速率;tB为射频发送接收1 B需要的时间.父节点向上一级节点发送的数据包括2部分内容：自己本身感知的数据和转发n个子节点的数据.因此，父节点发送数据包的时间表达式系数为(n+1).

节点处于发送状态的总时间为

(3)

2) 接收能耗.类似于发送能耗的分析，接收能耗包括信标的接收能耗和数据的接收能耗.父节点本身也是上一级节点的子节点，因此也要接收来自自己父节点的信标.节点接收信标的时间为LsynctBrsync，接收来自于子节点的数据的时间为nLdatatBrdata.

节点处于接收状态的总时间为

(4)

3) 空闲侦听能耗.受时钟漂移的影响，节点在接收信号之前必须提前打开接收机监听信道，以防止信号提前到达.空闲侦听的总时间可用式(5)表示：

(5)

其中，tguard代表保护时间，用来补偿时钟漂移导致的节点间存在的同步误差.

文献[4]研究表明：保护时间tguard的长短由同步周期Tsync和时钟漂移率θ共同决定.其中，θ由2个时钟间的频率偏差所决定，并受环境因素(如温度、电压等)影响.

2个节点间的最大时钟差为

(6)

其中，系数2表示2个节点的时钟漂移方向相反，为时钟差最大的情况.

由于发送节点并不知道自己和接收节点时钟偏差的方向，在时间轴前后2个方向都需要保护时间.因此，总的保护时间是最大时钟偏差的2倍，如式(7)所示：

(7)

将式(3)(4)(5)(7)代入式(2)，得到节点总的能量消耗为

E=rsync[tguardPlisten+LsynctB(Ps+Pr)]+

rdata[ntguardPlisten+LdatatB((n+1)Ps+nPr)]=

(8)

式(8)表明，假定信标和数据包的长度固定，总能耗只和子节点个数n、数据速率rdata、时钟漂移率θ和同步周期Tsync相关.关于同步周期Tsync：增大同步周期将减少收发信标的能耗，但同时保护时间也随之增大，导致空闲侦听能耗增加.因此，最优的同步间隔必须兼顾这2方面的能量开销，使总能耗最小.

通过求解式(8)关于Tsync的1阶导数可以得到使得总能耗最小的同步间隔值.

(9)

式(8)代入式(9)求解Tsync，如式(10)所示：

(10)

4　性能测试

为评估本文提出的Opt-TDMA的性能，我们对其进行了测试，并与非最优化的TDMA协议(没有采用最优的信标间隔机制)和文献[4]提出的SCP-MAC进行比较分析.SCP-MAC是一个基于竞争的同步MAC，采用周期性信道探测机制，节点平均占空比小于1%.通过测量射频在各个状态(发送、接收、空闲侦听)的工作时间可以得到节点的总能耗.实验参数如表1所示：

Table 1　Symbols Used in Radio Energy Analysis

4.1最优信标间隔

图4为不同子节点数目下最优信标间隔随数据速率的变化曲线.从图4可以看出，最优信标间隔与数据包发送间隔呈正相关，与网络规模(节点数)呈负相关.信标的收发能耗和保护时间导致的空闲侦听能耗之间存在1个最优折中.当数据包发送间隔增大时，接收端对数据包空闲侦听的频率降低,此时，高频率的同步会造成能量的浪费.我们可以通过增加很小的空闲侦听能耗来有效减小同步能耗，从而使总能耗最小.图4中还可以看出，最优信标间隔随着网络规模的减小而增大.这是因为子节点数目越少，产生的数据包越少，即数据包的间隔越大.根据上面的分析，慢的数据速率将导致最优信标间隔增大.因此，最优信标间隔会随着网络规模的减小而增大.

4.2能耗对比

Fig. 5　Power consumption for Opt-TDMA and TDMA with different clock drift.图5　不同时钟漂移率下Opt-TDMA和非最优化的TDMA的平均能耗

图5和图6分别为不同时钟漂移率下Opt-TDMA与TDMA和SCP-MAC平均能耗随数据包发送间隔的变化曲线.从图5和图6可以看出，平均能耗随数据速率的增加而增加；快的数据速率对应大的网络流量，数据传输能耗随之增加.我们还可以发现，平均能耗与时钟漂移率呈正相关.这是因为大的时钟漂移率会引起较大的同步误差，需要更长的保护时间，空闲侦听能耗随之增加.图5和图6表明，Opt-TDMA的平均能耗低于非最优化的TDMA和SCP-MAC.原因如下：1)与非最优化的TDMA相比(图5)，Opt-TDMA采用了最优的信标间隔，使得收发信标能耗和空闲侦听能耗的总和达到最小.非最优的信标间隔，无法兼顾收发信标能耗和空闲侦听能耗，不能使总能耗达到最小.2)与SCP-MAC相比(图6)，Opt-TDMA严格按照TDMA的方式进行时隙分配，消除了竞争开销，因而平均能耗低于SCP-MAC.尽管SCP-MAC也采用了最优的信道探测周期，但其信道访问是基于竞争模式的，不能完全避免碰撞，因此，耗能相对较多.

Fig. 6　Power consumption for Opt-TDMA and SCP-MAC with different clock drift.图6　不同时钟漂移率下Opt-TDMA和SCP-MAC的平均能耗

Fig. 7　Power consumption for Opt-TDMA and TDMA with different network size.图7　不同网络规模下Opt-TDMA和TDMA的平均能耗

图7和图8分别为不同网络规模下Opt-TDMA与非最优化的TDMA和SCP-MAC平均能耗随数据包发送间隔的变化曲线.图7表明，在不同数据速率下，Opt-TDMA节点平均能耗均低于非最优化的TDMA，特别是当网络流量较大时(高数据速率)，下降值更为明显.从图8可以看出，Opt-TDMA与SCP-MAC的平均能耗差值和网络规模呈正相关.例如，图8中n=3的2条曲线的差值明显大于n=1的2条曲线的差值.这是因为当网络中节点较多时，导致网络数据流量增大，SCP-MAC采用基于竞争的访问方式，因此在SCP-MAC中发生碰撞的概率增大，能耗增加.Opt-TDMA是冲突避免的，因此，Opt-TDMA的平均功耗低于SCP-MAC，特别是当网络规模较大时.

Fig. 8　Power consumption for Opt-TDMA and SCP-MAC with different network size.图8　不同网络规模下Opt-TDMA和SCP-MAC的平均能耗

5　结论及下一步工作

本文分析了低占空比无线传感器网络同步MAC协议信标间隔与网络能量消耗之间的关系，针对这类MAC协议分析了最优信标发送间隔，并提出了一种采用最优信标间隔的TDMA协议——Opt-TDMA.根据数据包速率和子节点数目采用最优的信标间隔，Opt-TDMA减少了网络的总能耗.实验表明，通过采用最优的信标间隔和冲突避免的传输，Opt-TDMA与非最优化的TDMA和SCP-MAC相比，平均能耗更低.在网络规模较大和时钟漂移更严重时，Opt-TDMA比非最优化的TDMA和SCP-MAC节省更多的能量.这意味着Opt-TDMA更适用于环境条件较差的应用以及大规模网络.下一步工作包括将这种分析方法应用到其他同步MAC(如Dozer[5]和Koala[16]等)并测试其性能.

[1]Han Y, Li H, Qiu J. The analysis and summary about energy saving technologies of wireless sensor network[C]Proc of the 2011 Int Conf on Electronic and Mechanical Engineering and Information Technology. Piscataway, NJ: IEEE, 2011: 883-885[2]Cui Li, Ju Hailing, Miao Yong, et al. Overview of wireless sensor networks[J]. Journal of Computer Research and Development, 2005, 42(1): 163-174 (in Chinese)(崔莉, 鞠海玲, 苗勇, 等. 无线传感器网络研究进展[J]. 计算机研究与发展, 2005, 42(1): 163-174)[3]Chen Liangyin, Wang Jinlei, Zhang Jingyu, et al. Scheduling scheme algorithm in Low-Duty-Cycle WSN[J]. Journal of Software, 2014, 25(3): 631-641 (in Chinese)(陈良银, 王金磊, 张靖宇, 等. 低占空比WSN中一种节点休眠调度算法[J]. 软件学报, 2014, 25(3): 631-641)[4]Ye W, Silva F, Heidemann J. Ultra-low duty cycle MAC with scheduled channel polling[C]Proc of the 4th Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2006: 321-334[5]Burri N, Von Rickenbach P, Wattenhofer R. Dozer: Ultra-low power data gathering in sensor networks[C]Proc of the 6th Int Conf on Information Processing in Sensor Networks. Piscataway, NJ: IEEE, 2007: 450-459[6]Huang P, Xiao L, Soltani S, et al. The evolution of MAC protocols in wireless sensor networks: A survey[J]. IEEE Communications Surveys and Tutorials, 2013, 15(1): 101-120[7]Polastre J, Hill J, Culler D. Versatile low power media access for wireless sensor networks[C]Proc of the 2nd Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2004: 95-107[8]Buettner M, Yee G V, Anderson E, et al. X-MAC: A short preamble MAC protocol for duty-cycled wireless sensor networks[C]Proc of the 4th Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2006: 307-320[9]Dutta P, Dawson-Haggerty S, Chen Y, et al. Design and evaluation of a versatile and efficient receiver-initiated link layer for low-power wireless[C]Proc of the 8th Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2010: 1-14[10]Tang L, Sun Y, Gurewitz O, et al. PW-MAC: An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[C]Proc of the 30th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 458-465[11]Ye W, Heidemann J, Estrin D. Medium access control with coordinated adaptive sleeping for wireless sensor networks[J]. IEEEACM Trans on Networking, 2004, 12(3): 493-506[12]Van Dam T, Langendoen K. An adaptive energy-efficient MAC protocol for wireless sensor networks[C]Proc of the 1st Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2003: 171-180[13]Sun Y, Du S, Gurewitz O, et al. DW-MAC: A low latency, energy efficient demand-wakeup MAC protocol for wireless sensor networks[C]Proc of the 9th Int Conf on Mobile Ad Hoc Networking and Computing. New York: ACM, 2008: 53-62[14]Liu Anfeng, Xu Juan, Chen Zhigang. A TDMA scheduling algorithm to balance energy consumption in WSNs[J]. Journal of Computer Research and Development, 2010, 47(2): 245-254(in Chinese)(刘安丰, 徐娟, 陈志刚. 无线传感器网络能量均衡消耗的TDMA调度算法[J]. 计算机研究与发展, 2010, 47(2): 245-254)[15]Song W Z, Huang R, Shirazi B, et al. TreeMAC: Localized TDMA MAC protocol for real-time high-data-rate sensor networks[J]. Pervasive and Mobile Computing, 2009, 5(6): 750-765[16]Musaloiu E R, Liang C J M, Terzis A. Koala: Ultra-low power data retrieval in wireless sensor networks[C]Proc of the 7th Int Conf on Information Processing in Sensor Networks. Piscataway, NJ: IEEE, 2008: 421-432

Xing Yulong, born in 1988. Received his BEn degree in communication engineering from Northwestern Polytechnical University in 2011. PhD from the University of Chinese Academy of Sciences. His current research interests include signal processing and low power data transfer in wireless sensor networks (WSNs).

Chen Yongrui, born in 1978. Received his MSc degree from Tsinghua University in 2007 and his PhD degree from the University of Chinese Academy of Sciences in 2011. His main research interests include cross-layer protocol design and reliable data transfer in wireless communication.

Yi Weidong, born in 1959. Received his BSc degree from Peking University, Beijing, China, in 1982, MSc degree from Brown University, Providence, RI, in 1991, and his PhD degree from the University of California, Berkeley. Senior member of China Computer Federation. His current research interests include design and modeling of microsensors and microelectromechanical systems for node platforms in the Internet of things, energy harvesting, and consumption efficiency in WSNs.

Duan Chenghua, born in 1962. Received his MSc degree from the Institute of Electronics, Chinese Academy of Sciences. Professor in the University of Chinese Academy of Sciences. His main research interests include mobile computing and network security.

The Optimal Beacon Interval for Synchronous MAC in Low Duty-Cycle Wireless Sensor Networks

Xing Yulong, Chen Yongrui, Yi Weidong, and Duan Chenghua

(SchoolofElectronic,ElectricalandCommunicationEngineering,UniversityofChineseAcademyofSciences,Beijing100049)

Energy efficiency is a fundamental theme in the design of wireless sensor networks protocols, especially for medium access control (MAC) protocols. An energy-efficient MAC protocol can significantly elongate the lifetime of wireless sensor networks by reducing the duty-cycle of sensor nodes to an ultra-low level. Synchronous MAC can be even more efficient in data transfer at the cost of requiring tight time synchronization through periodical beacon dissemination. The length of the beacon interval may greatly affect the energy efficiency of a synchronous MAC. A shorter beacon interval leads to higher synchronization cost due to frequent beacon sending and receiving, while a longer beacon interval will lead to a larger guard time and longer idle listening due to clock drift. Therefore, there is a tradeoff between these two parts of energy consumption. In this paper, we investigate the optimal beacon interval for synchronous MAC in low duty-cycle sensor networks, and then present a strategy that adaptively utilizes the optimal beacon interval in a TDMA-based MAC protocol (called Opt-TDMA). By configuring the beacon interval to its optimal value according to the data packets rate and network size, Opt-TDMA can reduce the overall power consumption of both sendingreceiving beacons and data packets. Experimental results demonstrate that Opt-TDMA is more energy-efficient than pure TDMA protocol and SCP-MAC by using optimal beacon interval and contention-free transmission.

beacon interval; synchronous MAC protocol; low duty-cycle; energy efficiency; wireless sensor networks (WSNs)

2015-06-09；

2015-08-27

国家科技支撑计划基金项目(2012BAJ24B01)

陈永锐(chen_yong_rui@163.com)

TP393

This work was supported by the National Key Technology Research and Development Program of China (2012BAJ24B01).