WSN中一种节能的按需调度协作式MAC协议研究*

卫小伟

(陕西交通职业技术学院信息工程系　西安　710018)



WSN中一种节能的按需调度协作式MAC协议研究*

卫小伟

(陕西交通职业技术学院信息工程系西安710018)

摘要能量空洞问题影响了由电池供电的多跳无线传感器网络的寿命。为此,论文提出一种按需调度协作式MAC协议(ODSC-MAC),综合采用按需策略及可扩展(传输)范围的传感器协作机制,ODSC-MAC协议解决了多跳WSN网络进行协作式传输(CT)时存在的时空问题,延长了网络寿命。另外,采用正交管线占空比调度以缓解流量竞争,同时设计了一种基于预定策略的唤醒机制以使协作节点时间同步,并为CT传输范围扩展提供支持。与现有的MAC协议相比,基于REACT的NS-2仿真结果表明,该协议既明确考虑了CT传输的开销及流量密集时控制报文的实际故障,又使网络运行时间提升了近80%。

关键词无线传感器网络; 能量空洞; 协作传输; 按需调度; 网络寿命

An Energy-saving On-demand Scheduling Cooperative MAC Protocol in Wireless Sensor Networks

WEI Xiaowei

(Department of Information Engineering, Shanxi College of Communication Technology, Xi’an710018)

AbstractThe energy hole problem limits the lifetime of battery powered multi-hop wireless sensor networks(WSNs). To solve this problem, An On-demand Scheduling Cooperative MAC protocol(ODSC-MAC) is proposed. By combining an on-demand strategy and sensor cooperation intended to extend range, ODSC-MAC tackles the spatio-temporal challenges for performing cooperative transmission(CT) in multi-hop WSN, to prolong the lifetime of the network. In addition, orthogonal and pipelined duty-cycle scheduling are used for reducing the traffic contention, and a reservation-based wake-up scheme is devised to bring cooperating nodes into temporary synchrony to support CT range extension. Compared with existing MAC protocols, our NS-2 simulations with REACT show that while explicitly accounting for the overhead of CT and practical failures of control packets in dense traffic, ODSC-MAC still gives almost 80% increase in network lifetime.

Key Wordswireless sensor networks, energy hole, cooperative transmission, on-demand scheduling, lifetime of the network

Class NumberTP393

1引言

众所周知,能量空洞问题影响了由电池供电的多跳无线传感器网络的寿命[1~2]。Sink附近的节点由于负载较重,能量耗尽较早,容易出现能量空洞问题:Sink附近的节点既要传输自己的报文,又要为距离Sink较远的节点转发报文。文献[3]已经证明,残余能量激活式协作传输(REACT)转发策略可纠正能量不均衡现象,将网络寿命延长2倍甚至更多。然而,该策略没有考虑协作式传输(CT)导致的额外控制开销。同时也没有考虑如何将REACT与占空比结合起来,而占空比是节约能量、提升WSN网络寿命的常用方法。

文献[4]的研究表明,MAC协议的能量消耗主要集中于空闲侦听、开销和冲突及数据传输和接收。空闲侦听意味着即使没有入向报文,节点也需不断地对信道进行侦听,IEEE 802.11内的许多MAC协议均没有考虑这一情况,而WIFI基站也必须侦听可能的流量。很显然,对WSN来说,空闲侦听是灾难性的,因为这种模式下的节点消耗的能量与接收数据时的能耗相同。许多文献已经研究了占空比MAC协议[5~7],并允许节点在活跃状态和睡眠状态间进行切换。这些协议显著降低了空闲侦听的周期和开销。具体来说,文献[5]中的DW-MAC协议具有出色的传输比、延时和节能表现。然而,DW-MAC和其他协议均没有解决多跳WSN网络的能量空洞问题。

同时,许多文献还提出支持CT传输的MAC协议[8~9]。多个单天线无线设备经过协调而形成一个虚拟的天线阵列时,即可进行CT传输,可有效提升接收器的信噪比。然而,这些研究既没有解决网络寿命问题,也没有缓解能量空洞问题。此外,这些研究均做出如下空间假设:数据源、合作节点和目的节点均位于同一冲突域中(即:互相位于对方的传输范围内),同时做出如下时间假设:在CT传输期间,所有节点保持活跃状态。一般地,多跳网络不满足空间假设,而且异步占空比网络也难以满足时间假设。

与大部分重点研究能量节约或能量均衡策略的MAC协议文献不同,本文提出一种按需调度协作式MAC协议,集成了MAC协议设计时的能量节约和能量均衡启发式策略,既提高了能耗的均衡性,又延长了网络寿命。具体来说,通过利用可对CT范围扩展进行无缝调度的MAC协议,解决了能量空洞问题,同时通过一种按需唤醒机制放松了时间假设。为了给上述方法提供支持,提出在MAC中集成管线和正交调度机制,以实现按需CT传输,并缓解流量竞争。

NS-2仿真结果表明,即使考虑了开销,基于REACT的MAC协议仍然将网络寿命延长了80%。

2网络模型和占空比设计

REACT协议需要假设一种基于树的路由协议。考虑时分CT传输(TDCT)包括一个多播阶段和多个单播阶段。在首个多播阶段,数据源与协调节点共享报文的一份拷贝。然后,协调节点在正交时隙期间把报文转发给目的地。为了扩展CT范围,当数据源把报文多播给协调节点时,源节点、协调节点和目的地的无线设备必须开启。目的地的无线设备开启之后,即可对数据源发来的信号进行采集和存储,然后与协调节点发来的报文拷贝进行融合。文献[10]提出的SCT-MAC协议通过使节点在其母节点和两跳母节点调度期间(即Sched1和Sched2)唤醒并在Sched2期间发起CT传输,以实现唤醒交汇。然而在该机制中,距离Sink较远的节点,其调度次数往往多于Sink附近的节点,因此空闲侦听时消耗更多的能量。另外,候选辅助节点局限于共享相同母节点的兄弟节点或母节点的兄弟节点。为此,本文提出一种方法通过按需方式使协作节点实现时间同步。具体来说,每个节点自身维护一个永久调度,以接收入向报文,只在需要支持CT传输时按需唤醒,本文将其称为时间调度。

一个占空比包括调度周期、数据周期和睡眠周期。超级帧定义为调度周期和数据周期的串接。本文将工作循环(cycle)的长度定义为Ns个超级帧。在超级帧期间,利用调度周期进行协作唤醒请求和传输预约。在数据周期期间,根据先前调度周期提供的调度信息进行非CT数据传输和CT数据传输。节点在整个睡眠周期及“未被使用的”数据周期部分时间内处于睡眠状态。网络初始化时使用与SCT-MAC相同的贪婪算法和广播策略,以建立永久超级帧调度,如算法1所示。与文献[5]中的DW-MAC相同,假设由一种专门的网络时间同步协议来传播占空比信息。在图1给出的调度算法示例中,50个节点随机形成拓扑结构且Ns=12。方块中的数字表示对应节点的永久调度。请注意,叶节点服从其母节点的调度。

算法1:超级帧调度

1:输入:

2:pt=节点t的直接母节点

3:It=节点t的干扰母节点集合

4:Sa={s∈[1,Ns]:s≠si∀i∈It,si表示结点i的调度}

5:输出:st

6:开始

9:ifs

12: end

13:end

14:返回st

15:end

在异构网络中进行CT传输的难度很大,因为数据源、协调节点和目的地必须就进行CT传输的唤醒周期达成一致。本文研究通过明确的请求步骤,使协调节点和单跳母节点会集于共同的唤醒交Sink,下一节对此做详细描述。

图1　随机拓扑结构的调度示例

3按需调度协作式MAC协议

(ODSC-MAC)

3.1概述

在ODSC-MAC协议中,每个节点维护一个永久调度,并在线决定时间调度。为了支持CT传输,可按需激活时间调度,然后关闭。假设每个节点知道其单跳相邻节点及两跳母节点的永久调度。因为每个节点可能是接收节点,所以它在其自身永久调度期间始终唤醒,以接收CT或非CT传输数据。当节点决定向其母节点直接传输一个非CT数据报文时,则该节点在其母节点的永久调度期间唤醒,并按照第4小节的步骤传输数据。另一方面,当源节点决定进行CT传输时,如图2所示,则它将会按照第2小节的准则过滤候选协同节点。本文使用与REACT相同的CT传输决策准则。在该准则下,需要比较源节点的残余能量Ei及其母节点的能量Ep。如果Ep>Ei,则进行非CT传输。否则,做出CT决策以保护母节点。然后,协同节点将会在线决定时间调度,在此期间这些节点将会唤醒,第3小节给出一种算法以落实这些步骤。本文定义了三种类型的积极调度以支持ODSC-MAC协调中的调度机制,相应节点的职责如下所示:

1) 永久调度(类型1):由每个节点设置,以侦听入向报文。

2) 临时调度(类型2):由初始化CT传输的源节点设置,以便对协同节点做出唤醒请求。

3) 临时调度(类型3):由协同节点设置为唤醒交Sink,以进行CT传输。

图2　源节点的CT决策和唤醒调度

3.2协同节点的选择

SCT-MAC协议在设计调度机制时要求协同节点必须为源节点的兄弟节点或母节点的兄弟节点。与该协议相反,ODSC-MAC没有类似约束。相反,每个节点可从其单跳相邻节点中选择协同节点。本文选择如下协同节点: 1) 残余能量最大, 2) 能量大于源节点。通过周期性地插入共同的信息共享广播时隙,即可获得能量信息。广播期间传输的报文也可用于重新调整调度,并更新其相邻节点信息,以适应可能发生的拓扑结构变化。

图3　唤醒机制

3.3按需唤醒

CT传输时,我们提供在线唤醒机制,通过在线管理临时调度以使相同节点实现临时同步。具体来说,本文要求在两跳母节点的永久调度期间进行CT传输,该调度也是可能发生的两跳非CT传输的调度。因此,本文的目标是使所有协同节点会聚于该CT交Sink。

因为节点的永久调度可能完全不同,本文提出一种明确的唤醒请求步骤,以设置协同节点的唤醒交Sink。如图3所示,源节点i设置类型2调度,以便在每个协同节点及单跳母节点的调度sj期间临时唤醒。请注意,每个sj是调度周期和数据周期的串接。源节点将向协同节点发送一个唤醒请求报文,以表明CT交Sink的预期时间β,并等待唤醒回复。视生成报文的时间隙α和协同节点的调度不同,为协同节点提供一种方法以便协同节点自行决定何时唤醒进行CT传输,如算法2所示。这一协调过程请见第4小节将要描述的MAC协议非CT传输步骤,即:使用调度周期交换唤醒请求/回复。

算法2:在线唤醒调度算法

输入:协同节点集合(包括母节点)Γ

报文到达时的时隙,α

两跳母节点的调度,β

输出:唤醒交Sink的调度

1:源节点:(进行唤醒请求)

2:maxTime←0;

3:for 每个j∈Γdo

4:ifsj≡βthen 设置WakedStatus[j];

5:else

6:d1←(sj-α)modNs;

7:d2←(β-sj)modNs;

9:scheduleTxRequest[j];

10:end

11:end

12:每个协同节点:(当接收到唤醒请求时)

13:d←(β-sj)modNs;

14:TimeToWake←startofSlot+d*superFrameLen;

15:ifTimeToWake

16:else

17:scheduleWakeup();

18:end

19:sendWakeupReply();

注意,该算法存在两种延时: 1) 链路延时(从数据源到下一跳节点,要么是单跳母节点,要么是两跳母节点)。 2) 协同节点进行协调时可能导致的“额外”延时。请注意,如果被选协调节点的协调过程准时发生于两跳母节点之用(称为提前协调),则协调节点的协调过程不会有任何额外延时,这主要是由于永久型调度的管线特征。实际上,协调节点的选择过程可以采用第3种准则(即sj<β),以保证提前协调。

3.4CT和非CT传输的无缝调度及传输

本小节对母节点调度期间的非CT传输和图3中CT传输交汇期间CT传输的无缝调度和传输进行详细描述。与SCT-MAC相同,使用调度周期来在下一数据周期内预留数据传输。节点在数据周期未被使用的时间内处于睡眠状态。接收器将跟踪自身数据周期内已经预留的非CT和CT传输次数。

1) 非CT情况:在调度期间,源节点S向目的节点D发送一个调度帧(SF),目的节点D将返回一个调度帧,且返回的调度帧中包含数据周期内已经预留的非CT(Nnon-CT)和CT(NCT)数量。节点S和D根据下式计算从后续数据周期开始的相应唤醒时间点TWakeup:

TWakeup=Tnon-CT×Nnon-CT+TCT×NCT

(1)

其中Tnon-CT=TPkt+TAck+SIFS且TCT=2TPkt+2TAck+3SIFS。很容易看出,对一个接收器来说,在后续数据周期内不会发生调度冲突,因此避免了不同发射机间的数据冲突。在数据周期内的调度时间TWakeup唤醒后,节点S和D进行DATA-ACK(数据确认)过程,然后再次进入睡眠状态。

2) CT传输情况:与SCT-MAC相同,使用一个协调节点来使(传输)范围翻倍。以图4(b)中的拓扑结构为例,在CT交汇时间内,节点S向两跳之外的目的节点D发送一个SF。招募的协调节点C在下一时隙期间于SIFS之后向节点D发送SF。基于最大比例组合准则(MRC)对SF解码后[11],节点D向源节点S发送一个包含Nnon-CT和NCT的SF。因为目的节点传输时没有使用CT传输,所以该SF必须由源节点的单跳母节点转发(将被保护的节点P)。接收到转发来的SF后,源节点S和协调节点C将会根据式(1)调度一个唤醒时间。然后,在数据周期内的唤醒时间,源节点S在首个时隙期间发送数据报文,由节点C在第2个时隙期间于SIFS之后对该报文进行解码和转发。在根据MRC准则解码CT报文时,两跳目的节点D通过两跳方式向节点S传输ACK。同时,由节点P代表节点D转发ACK。为了避免监听节点S和C的数据报文,节点P应该在节点D传输ACK前调度一个唤醒时间Tp,即Tp=TWakeup+2TPkt+2SIFS。因此,本文无法完全避免使用将被保护的节点P,只使用该节点进行控制报文的转发,其他情况下允许其进入睡眠状态。

CT和非CT重传包括SF握手重试和数据传输。前一种情况发生于调度周期内,可以进行多次尝试直至到达周期的边界。然而,如果SF握手成功但是被调度的数据传输在数据周期内失败,则节点必须等待下一工作循环。

3.5单跳节点处理及向Sink快速转发

因为与Sink相距单跳距离的节点的调度具有正交性(因为它们互相位于对方的干扰范围内),所以它们可在分裂时间(split time)内见到Sink,因此可向源节点直接发送回复SF,而不是使Sink通过两跳方式向源节点传输数据。有三种类型的流量可能会通过单跳节点,如图4所示:图(a)和(b)中以自己作为MAC层目的地的非CT传输和CT传输,图(c)中从其叶节点直接传向Sink的CT传输。在前两种情况下,节点多预留一个Tnon-CT,用于立刻把接收到的数据发往Sink。在第3种情况下,它代表Sink回复SF。

图4　单跳节点的流量

4仿真实验

下面给出了NS-2.29的仿真实验对ODSC-MAC协议的详细评估结果。假设有100个随机拓扑结构,50个节点随机部署于1000m*1000m面积上。Sink位于中心。与SCT-MAC和DW-MAC不同,使用随机相关事件(RCE)流量模型分析ODSC-MAC,以模拟空间相关事件触发的突发流量。每200s随机选择事件位置。以事件位置为中心、半径为R的圆内的每个节点生成一个报文发给Sink。半径R逐渐增加,以便向网络输入更多流量。表1给出了主要仿真参数。节点的初始能量为50J,Sink没有能量约束。路由层使用最小距离指标,路由层的能耗忽略。同时,还忽略ODSC-MAC协议在构建永久型调度时网络初始化阶段的能耗。将ODSC-MAC协议与合作式协议SCT-MAC[10]和非合作式占空比协议DW-MAC[5]进行比较。

表1　仿真参数

4.1网络寿命评估

本节评估了不同协议的网络寿命。网络寿命定义为首个节点死亡时成功发送到Sink的报文数量。图5给出了事件感知范围R上升时,平均寿命的增长情况,此时置信区间为95%(它们非常小)。研究发现,ODSC-MAC的寿命远优于SCT-MAC和DW-MAC。例如,当R=400m时,ODSC-MAC的平均寿命比SCT-MAC高77.8%。这是因为虽然进行CT传输,但是ODSC-MAC花费在空闲侦听上的时间很少。当流量增加时,交错的占空比降低了多个节点竞争媒介的冲突现象。

图5　网络寿命与事件感知范围的关系

图6以很小的标度给出了3种协议的平均输送比,置信区间为95%。除了输送比最高外,ODSC-MAC对所有事件感知范围的置信区间也最小。

图6　输送比与事件感知范围的关系

4.2残余能量情况

图7　当首个节点的能量耗尽时网络的残余能量情况

本节给出在事件感知范围为100m和300m条件下,首个节点死亡时网络中所有节点的残余能量情况。图7表明,SCT-MAC协议使Sink周围有大量能量未被利用。这是因为SCT-MAC协议的调度要求节点在母节点和两跳母节点调度时唤醒,以便支持CT传输,因此距离Sink较远的节点需要维护多达3个唤醒调度,消耗的能量大于空闲侦听时的能耗。从图7中还可以看出,DW-MAC的残余能量比较均衡,因为所有节点调度经过同步,所以许多能量消耗于空闲侦听时的调度周期及信道竞争。另一方面,ODSC-MAC的能量之所以比SCT-MAC均衡,是因为节点需要在线维护一个永久调度并管理多个临时调度,因此针对可能发生的CT流量而花费的空闲侦听时间有所降低。

4.3饱和寿命

为了量化CT传输对ODSC-MAC协议的影响,将感知范围从100m增加到1200m,然后比较ODSC-MAC协议支持CT传输和不支持CT传输时的寿命(置信区间为95%)。“不支持CT传输”是指,按照第2节内容进行占空比分配,但是每个报文必须进行非CT传输。当感知范围为1200m时,几乎每个节点均将进行周期性传输,因此有50个数据流发往Sink,大大增加了网络负载。从图8中可以发现,感知范围到达600m之前出现上升趋势后,寿命开始缓慢降低,直至到达稳定水平。Bianchi等人研究[12]发现,在WIFI网络中当流量增加时吞吐量有类似趋势。类似地,本文将该稳定水平定义为网络饱和寿命。图8表明,即使在两种情况下细致设计了占空比调度且考虑了CT传输的通信开销,与非CT传输相比,CT传输仍然会增加饱和寿命。

图8　饱和寿命:CT模式和非CT模式

4.4CT传输控制握手导致的实际缺陷

图9　CT取消频率

图9给出了事件感知范围为200m和600m时,每个源节点的CT取消频率。请注意,Sink周围的单跳节点无需初始化CT传输。当网络中的流量负载较高时,CT取消的频率显著上升。这一现象有两个原因: 1) 若网络负载较大,则CT交汇期间进行CT数据传输调度时SF握手的冲突加剧。冲突既来自于非CT握手竞争也来自于CT握手竞争。 2) 当我们为了到达CT交汇处而部署明确的唤醒请求/回复步骤时,由于存在竞争,导致该唤醒步骤发生故障的频率加剧。因此,必须放弃CT传输企图,然后采用非CT传输。

5结语

本文提出一种按需占空比MAC协议(ODSC-MAC)以支持REACT协议;该协议利用网络层的CT传输范围扩展来解决多跳WSN网络的能量空洞问题。通过综合利用在线调度和CT传输范围扩展机制,解决了多跳WSN网络进行CT传输时的时空挑战,显著延长了网络寿命。即使考虑控制报文的能量,支持REACT的ODSC-MAC协议仍然可将网络寿命提升80%左右。

参 考 文 献

[1] 杨宛楠,陈志刚,赵明.基于不等簇半径分簇的无线传感器网络能量空洞避免[J].中南大学学报(自然科学版),2014,45(4):1137-1142.

YANG Wanwan, CHEN Zhigang, ZHAO Ming. Energy Nole Avoid by Clustering with Unequal Cluster-radius in Wireless Senor Networks [J]. Journal of Central South University: Science and Technology, 2014,45(4):1137-1142.

[2] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.

QIAN Zhihong, WANG Yijun. Internet of Things-oriented Wireless Senor Networks Review[J].Journal of Electronics & Information Technology, 2013,35(1):215-227.

[3] Jung J W, Ingram M A. Residual-energy-activated cooperative transmission (REACT) to avoid the energy hole[C]//Communications Workshops(ICC), 2010 IEEE International Conference on. IEEE,2010:1-5.

[4] Ye W, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor networks[C]//INFOCOM 2012. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE.,2012:1567-1576.

[5] Sun Y, Du S, Gurewitz O, et al. DW-MAC: a low latency, energy efficient demand-wakeup MAC protocol for wireless sensor networks[C]//Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing. ACM,2008:53-62.

[6] Buettner M, Yee G V, Anderson E, et al. X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[C]//Proceedings of the 4th international conference on Embedded networked sensor systems. ACM,2006:307-320.

[7] Tong F, Tang W, Xie R, et al. P-mac: a cross-layer duty cycle mac protocol towards pipelining for wireless sensor networks[C]//2011 IEEE International Conference on Communications. IEEE,2011:1-5.

[8] Moh S, Yu C. A cooperative diversity-based robust MAC protocol in wireless ad hoc networks[J]. Parallel and Distributed Systems, IEEE Transactions on,2011,22(3):353-363.

[9] Zhou Y, Liu J, Zheng L, et al. Link-utility-based cooperative MAC protocol for wireless multi-hop networks[J]. Wireless Communications, IEEE Transactions on,2011,10(3):995-1005.

[10] Lin J, Ingram M A. SCT-MAC: A scheduling duty cycle MAC protocol for cooperative wireless sensor network[C]//2012 IEEE International Conference on Communications. IEEE,2012:345-349.

[11] Molisch A F, Tufvesson F. Propagation Channel Models for Next-Generation Wireless Communications Systems[J]. IEICE Transactions on Communications,2014,97(10):2022-2034.

[12] Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications,2013,18(3):535-547.

中图分类号TP393

DOI:10.3969/j.issn.1672-9722.2016.02.028

作者简介:卫小伟,男,博士,副教授,研究方向:无线传感网、移动计算。

*收稿日期:2015年8月4日,修回日期:2015年9月12日