一种基于有限信道的能量高效节点调度机制*

曾 波,李姗姗,王 辉1,

(1.河南科技大学网络与通信技术研究所,河南 洛阳 471023;2.河南科技大学网络信息中心,河南 洛阳 471023)



一种基于有限信道的能量高效节点调度机制*

曾 波1,2*,李姗姗2,王 辉1,2

(1.河南科技大学网络与通信技术研究所,河南 洛阳 471023;2.河南科技大学网络信息中心,河南 洛阳 471023)

在低负载、低功耗无线传感器网络中,节点状态切换的能量消耗因为用于数据传输的能量较小而变得不可忽略。针对此问题,提出了结合多信道技术与时分多路访问(TDMA)技术的节点调度算法。该算法设计了基于接收端的连续时隙分配策略以减少节点状态切换次数,并且在可用无线信道有限的约束条件下,提出了信道分配与时隙调整机制,实现了时隙重用并最小化有限信道约束对优化节点状态切换次数的影响。仿真实验结果表明,当可用无线信道数为3～5时,算法能够有效地改善节点能量效率。当可用无线信道数大于3之后,算法能够获得优化的数据汇聚时间。

无线传感器网络;能量;TDMA;多信道;调度;仿真

近年来,无线传感器网络因其成本低廉、部署灵活、覆盖范围广等特性,广泛应用于环境保护、智能交通、文物保护等领域[1]。对大多数部署在无人监管的恶劣环境下的无线传感器网络,因其仅依靠电池供电[2]而使得传感器节点不得不采用周期性工作方式来实现数据采集与汇聚传输,以降低传感器节点能量消耗。采用超低功耗传感器节点射频技术[3-4]在进行数据发送之前需要唤醒节点,虽然降低了能量消耗,却增加了传输延迟。而采用功率控制的能量优化[5]需要额外的控制消息。

TDMA调度算法[6]通过对每个节点访问信道的时隙进行合理安排,能够有效避免节点对无线信道的访问竞争,让节点能够在指定的时隙无干扰的完成数据发送,并且在数据发送完成之后,节点立即切换至休眠状态,极大的节省了节点能量。

目前,针对传感器网络能量优化的TDMA调度算法主要包括降低空闲时隙内传感器节点活动[7-9]、延长节点工作间隔和降低工作循环时间[10-11]。在前述方法中,主要考虑降低数据汇聚过程中节点在空闲状态的能量消耗。基于邻居信息共享,Luo等人[12]提出了多信道协同方法以优化节点能量消耗与网络吞吐量。在基于多信道的节点调度技术中,更多的是通过信道间的时隙重用来优化网络吞吐量[13-14]或传输延迟[15-16]。上述方法中均没有考虑节点在各状态下的能量消耗差异。

由于数据汇聚过程中的Many-to-One数据传输特性,树中非Sink与非叶子节点均可能需要接收并转发来自子节点的数目不定的数据包,如果其子节点的数据包无法在连续时间内发送完成,将导致节点需要进行多次状态切换才能够完成数据汇聚。注意,节点状态切换指的是将节点从休眠状态唤醒,或者将节点从活动状态切换至休眠状态的过程。在文献[17-18]中,作者证明了在低负载、低功耗的无线传感器网络中,节点消耗在状态切换上的能量因数据传输过程消耗能量较小而不可忽略。本文以Mica2 Mote传感器节点为例进行说明。表1列出了该传感器节点在各状态下的能量消耗情况[19]。图1显示了在不同传输速率与数据包大小情况下节点状态切换能量与传输一个数据包的总能量消耗的比例P,P由式进行计算。

(1)

其中,Esw表示节点状态切换能量消耗,Csw表示节点状态切换功率,Tsw表示节点状态切换时间,Et表示传输一个包含若干位数据包的能量消耗。Ct表示数据发送功率,Tt表示数据包发送时间。

图1 Mica2 Mote节点状态切换能量消耗

表1 Mica2 Mote节点各状态下的能量消耗

从图1中可知,当节点负载与传输速率都较低时(如4 byte,10 kbyte/s),节点状态切换能量消耗占据了传输一个数据包总能耗的75%,即P=75%。随着传输速率的增大,在相同负载情况下P最终能够达到90%左右。因此,在低负载、低功耗的情况下,优化节点能量消耗可以转化为降低节点状态切换能量消耗问题加以解决。

针对最小化节点状态切换能量消耗问题,Ma等人[20]提出了集中式连续链路调度算法,该方法虽然优化了节点状态切换能量消耗,但是无法保证节点的所有数据能够在一个周期内完成汇聚。与该算法不同,本文提出了结合多信道与TDMA技术的集中式能量优化算法。利用多信道的正交特性,将不同节点的数据分派至不同信道,实现了数据并发传输,优化了数据汇聚时间并保障了数据汇聚可靠性。然而,由于无线通信系统中可用的信道数有限,在考虑信道数约束基础上,设计了基于接收端的连续时隙分配策略,优化了节点的状态切换次数及能量消耗。

1 问题定义

考虑数据汇聚树T,由n个无线传感器节点V={v1,v2,…,vn},单个汇聚节点Sink构成。在正常情况下,传感器节点以固定周期采集与发送感知数据至Sink。

对于T而言,由于每个节点周期性进行数据汇聚,因此,可采用式(2)计算数据汇聚周期内的总能量开销:

(2)

(3)

结合式(2)与式(3),对于任意树T,可得E≥Emin。

在无线通信系统中,信道数受限于频谱、带宽等因素。考虑最大可用信道数约束Ch,本文算法在实现连续时隙分配时所使用的信道数需要满足如下条件:

Cu≤Ch

其中,Cu表示算法所使用的信道数。

2 算法设计

对任意数据汇聚树T,本文算法的详细执行步骤如下:

Step2:基于接收端的连续时隙分配策略:采用自上而下的方式为每个节点分配时隙。具体而言,Sink为时隙分配起始节点,首先为其子节点,即树T中第1层节点分配连续时隙。随后第1层节点为第2层节点分配连续时隙,……,逐层往下为树T中的节点分配连续时隙。

(4)

Step4:时隙分配调整:在Step2中,非叶子节点vi为其子节点集Li分配的发送时隙是以vi的最后一个发送时隙ti为起点,这将导致其所有子节点vj的发送时隙都位于节点vi之后。为了保证节点vi能够按照“接收-发送”的活动模式进行数据汇聚,在完成所有节点的时隙分配之后,算法将对所有节点的时隙进行调整,确保节点vi的所有子节点的发送时隙位于其发送时隙之前。时隙调整方法如下:①求得网络中已分配时隙的最大序号tmax。②将tmax减去节点的时隙,所得结果即为节点执行数据发送时的最终时隙分配。对于节点vj,其最终发送时隙为:(tmax-tj′,tmax-tj)。

综上所述,为了保证节点调度的正确执行,每个节点需要维护一张节点活动调度表S,S的项由<信道,时隙列表>构成。节点按照其活动调度表S,在所分配的时隙内,使用对应的信道,执行数据接收或发送,完成后节点将由活动状态切换至睡眠状态,以节省能量消耗。

3 性能评估

本文采用MATLAB仿真实验平台对算法性能进行评估。为了便于比较,文中提出算法命名为CE-TDMA,而用于比较的算法包括能量优化的集中式TDMA调度算法[20](命名为E-TDMA),支持多跳数据传输的TDMA算法(命名为M-TDMA)。在所有实验中,传感器节点数在200～1 000之间,且随机部署在100m×100m的区域。节点有效通信范围为10m。为实现E-TDMA的时隙重用,本文采用UnitDiskGraph传输模型,因而将节点干扰距离设置为20m,即两倍于有效通信距离。数据汇聚树采用最短路径路由算法生成。本文以传感器节点Mica2Mote的能量消耗为例来分析所提出算法的能量效率。节点各状态的能量消耗情况如表1所示。节点状态切换能量消耗=节点状态切换次数x节点单次状态切换的能量消耗。

图2展示了一个数据汇聚周期内,传感器节点的状态切换次数比较。从该图中可以看出,与E-TDMA算法和M-TDMA算法相比,CE-TDMA算法在信道数为3与5时降低了节点状态切换次数。这表明,在大多数规模较小的网络中,3～5条信道已经足够优化网络在节点状态切换上耗费的能量。除此之外,当信道数为5时,节点状态切换次数与节点数基本呈线性关系,表明在数据汇聚过程中,大部分节点均只需要从休眠切换至唤醒状态一次,并在数据汇聚结束后切换至休眠状态,然后节点将保持休眠直至下一数据汇聚周期到来。

图2 传感器节点状态切换次数

图3描述的是网络完成了100个数据汇聚周期后,网络中传感器节点状态切换能量消耗结果。该实验结果表明:在网络规模相同的情况下,CE-EDMA算法因减少了节点状态切换次数,消耗在节点状态切换上的能量较M-TDMA算法与E-TDMA算法低。当信道数为5时,CE-TDMA算法节省的能量明显降低。

图3 传感器网络的节点状态切换能量消耗

由于在采用Mica2 Mote节点的传感器网络中,其典型速率为19.2 kbit/s[19],因此在需要长时间低功耗、周期性运行的低负载无线传感器网络,如用于获取温湿度、CO2浓度等参数信息的微环境监控系统,CE-TDMA算法将能够有效地延长网络寿命。

为了验证多信道技术在优化数据汇聚时间上的性能,本文通过实验比较了3种算法在相同网络规模情况下的TDMA调度帧长度,其表示的是在一个数据汇聚周期内,将所有传感器节点采集的感知数据投递至数据汇聚节点需要的TDMA时隙的数量,即数据汇聚时间。从图4显示的实验结果可以看出,由于采用了时隙重用策略,CE-TDMA和E-TDMA算法能够让多个节点在同一时隙内进行无冲突数据传输,从而明显降低了数据汇聚时间。值得注意的是CE-TDMA算法在分别使用3条信道与5条信道时,算法在TDMA调度帧长度上没有明显变化。由于缺乏时隙重用,传感器节点的数据传输活动无法并发执行,M-TDMA无法有效优化数据汇聚时间。

图4 TDMA调度帧长度

为了明确信道数对网络性能的影响,本文将信道数从2增加到10,并比较了网络规模从200变化至600个节点时,CE-TDMA算法的性能变化情况。

图5显示了在不同的网络规模中,信道数与节点状态切换次数的关系。实验结果表明,当信道数为2时,网络中的节点为完成数据汇聚进行的状态切换(即从休眠切换至活动状态的过程)次数约为1.5。而随着可用信道数增加至5条～6条,CE-TDMA算法能够保证网络中大部分节点均只需要切换一次状态即可实现数据汇聚传输,即能够保证大多数节点在数据汇聚过程中的模式为“接收-发送”,随后节点切换至休眠状态直到下一周期到来。

图5 可用信道数与节点状态切换次数的关系

图6显示了在可用信道数持续增加的情况下,各种网络规模的节点状态切换能量消耗变化情况。由于节点状态切换能量与节点状态切换次数密切相关,因此,图6表现出与图5类似的趋势。

图6 可用信道数与节点状态切换能量消耗的关系

图7 可用信道数与TDMA调度帧长度的关系

图7显示的是算法在可用信道数增加的情况下所得出的TDMA调度帧长度变化情况。实验结果表明,在大多数网络中,当可用信道数从2条增加至3条时,信道数的增加明显降低了TDMA调度帧长度。其原因在于,多信道技术的加入主要是为了优化节点能量消耗,时隙重用仅会发生在节点使用不同信道时,当时隙分配在同一信道时,时隙必然是不重用的,这些限制了节点间的时隙重用。由于信道数为2时,没有足够多的信道实现时隙重用,引起节点无法最小化其状态切换次数(由图5可证),也同样导致TDMA帧长度无法得以优化。随着可用信道的加入,当信道数为3时,时隙能够充分在信道间重用,因而,其TDMA帧长度有了明显减小。然而,在网络规模较小的情况下,由于在同一区域内,数据汇聚树的最大跳数、节点分布情况的差异比较大规模网络中明显,可用信道数的变化将导致TDMA调度帧长度明显变化。

4 结论

针对低负载、低功耗无线传感器网络在节点状态切换上能量消耗较大的问题,在考虑了可用信道数有限的情况下,提出了结合多信道与TDMA技术的节点调度算法。算法结合了基于接收端的连续时隙分配策略、多信道分配与时隙调整机制实现了对节点唤醒能量消耗与数据汇聚时间的优化,并通过仿真实验证明了算法的性能。

本文所提出的节点调度算法充分利用了无线信道间的无冲突数据并发传输能力与TDMA在消除节点空闲侦听与信道访问竞争的先天优势,与常用的仅以节点能量消耗优化为目标的调度方法相比较,算法能够同时实现数据汇聚时间与节点能量消耗优化。

本文的工作可以为无线传感器网络能量效率优化方法设计提供参考。未来我们将在无线传感器网络测试平台上实现并评估算法的性能,而且采用分布式的方法实现本文算法也需要进一步研究。

[1] 任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[2]吕涛,施伟斌,范坤坤,等.WSN节点电池供电性能测试研究[J].传感技术学报,2013,26(10):1457-1462.

[3]Magno M,Marinkovic S,Brunelli D,et al.Smart Power Unit with Ultra Low Power Radio Trigger Capabilities for Wireless Sensor Networks[C]//Proceedings of the Conference on Design,Automation and Test in Europe.EDA Consortium,2012:75-80.

[4]Zhang Y,Dolmans G.Wake-Up Radio Assisted Energy-Aware Multi-Hop Relaying for Low Power Communications[C]//IEEE Wireless Communications and Networking Conference(WCNC),2012:2498-2503.

[5]陈立建,周雪,雷艳静,等.一种基于功率控制的WSN自适应能量高效传输模式研究[J].传感技术学报,2014,27(6):835-841.

[6]张晓玲,梁炜,于海斌,等.无线传感器网络传输调度方法综述[J].通信学报,2012,33(5):143-157.

[7]Zhang L,Ye Q,Cheng J,et al.Fault-Tolerant Scheduling for Data Collection in Wireless Sensor Networks[C]//IEEE Global Communications Conference(GLOBECOM),2012:5345-5349.

[8]Zhao W,Tang X.Scheduling Sensor Data Collection with Dynamic Traffic Patterns[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(4):789-802.

[9]Niu J,Deng Z.Distributed Self-Learning Scheduling Approach for Wireless Sensor Network[J].Ad Hoc Networks,2013,11(4):1276-1286.

[10]Luo T,Motani M,Srinivasan V.Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols[J].IEEE Transactions on Mobile Computing,2012,11(4):553-566.

[11]Hsu T H,Kim T H,Chen C C,et al.A Dynamic Traffic-Aware Duty Cycle Adjustment MAC Protocol for Energy Conserving in Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks,2012.

[12]Luo T,Motani M,Srinivasan V.Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols[J].Mobile Computing,IEEE Transactions on,2012,11(4):553-566.

[13]Soua R,Livolant E,Minet P.An Adaptive Strategy for An Optimized Collision-Free Slot Assignment in Multichannel Wireless Sensor Networks[J].Journal of Sensor and Actuator Networks,2013,2(3):449-485.

[14]Soua R,Minet P,Livolant E.MODESA:An Optimized Multichannel Slot Assignment for Raw Data Convergecast in Wireless Sensor Networks[C]//2012 IEEE 31st International Performance Computing and Communications Conference(IPCCC),2012:91-100.

[15]Guo P,Jiang T,Zhang Q,et al.Sleep Scheduling for Critical Event Monitoring in Wireless Sensor Networks[J].Parallel and Distributed Systems,IEEE Transactions on,2012,23(2):345-352.

[16]Nasser N,Karim L,Taleb T.Dynamic Multilevel Priority Packet Scheduling Scheme for Wireless Sensor Network[J].IEEE Transactions on Wireless Communications,2013,12(4):1448-1459.

[17]van L H,Havinga P.A Lightweight Medium Access Protocol(Lmac)for Wireless Sensor Networks:Reducing Preamble Transmissions and Transceiver State Switches[C]//1st International Workshop on Networked Sensing Systems,2004:205-208.

[18]Xing G,Lu C,Zhang Y,et al.Minimum Power Configuration in Wireless Sensor Networks[C]//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computting,2005:390-401.

[19]Lee W L,Datta A,Cardell-Oliver R.Flexi TP:A Flexible-Schedule-Based TDMA Protocol for Fault-Tolerant and Energy-Efficient Wireless Sensor Networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(6):851-864.

[20]Ma J,Lou W,Wu Y,et al.Energy Efficient TDMA Sleep Scheduling in Wireless Sensor Networks[C]//IEEE INFOCOM 2009,2009:630-638.

A Finite Channel Based Energy-Efficient Node-Scheduling Mechanism*

ZENGBo1,2*,LiShanshan2,WANGHui1,2

(1.The Institute of Network and Communication Technology,Henan University of Science and Technology,Luoyang He’nan 471023,China;2.Network and Information Center,Henan University of Science and Technology,Luoyang He’nan 471023,China)

In a low-load,low-power wireless sensor network,energy consumption of the node state switching should notbe neglected because energy for data transmission is less.Focusing on this problem,a node scheduling algorithm combine with multi-channel technology and time division multiple access(TDMA)technology is proposed.The algorithm designs a consecutive slots allocation strategy based on receiver to reduce the node status switching times,proposes a channel allocation and slot adjustment mechanism under the constraints that the available wireless channels are limited,and implements slots reusing and minimizes the limited channels constraints effects on optimizing times of node status switching.The simulation experiments results show the algorithm can effectively improve the node energy efficiency when the number of available wireless channel is between 3 and 5,while the algorithm can achieve the optimized data collection time when the number of available wireless channel is greater than 3.

wireless sensor networks;energy;TDMA;multichannel;schedule;simulation

曾 波(1981-),男,河南科技大学讲师,目前的主要研究领域是无线传感器网络和异构网络性能优化,bozeng@haust.edu.cn;

李姗姗(1987-),女,河南科技大学助教,主要研究方向为无线网络技术,lss@haust.edu.cn。

项目来源:河南省科技攻关项目(13B510001)

2014-10-11 修改日期:2014-11-21

C:7230

10.3969/j.issn.1004-1699.2015.02.019

TP393

A

1004-1699(2015)02-0254-06