基于多信道的能量高效传感器节点调度算法

张治学，曾 波，b，张各各，b，王 辉，b

（河南科技大学a.网络信息中心；b.信息工程学院，河南洛阳471023）

基于多信道的能量高效传感器节点调度算法

张治学a，曾 波a，b，张各各a，b，王 辉a，b

（河南科技大学a.网络信息中心；b.信息工程学院，河南洛阳471023）

在无线传感器网络中，传统时分多址（TDMA）调度算法未考虑节点在不同状态间切换时所耗费的能量，缩短了网络生存时间。为此，提出一种基于接收端的时分多址时隙分配算法。时隙分配过程始于数据汇聚节点，以节点的数据量为偏移，父节点以自身的时隙为基础为其子节点分配时隙，以保证每个节点的传输活动满足连续接收-发送模式，并将节点的状态切换次数最小化为2次，降低节点能量消耗。采用优化的多信道分配机制，通过将节点时隙分派给不同信道，解决节点间时隙分配冲突问题，并实现时隙重用与信道数优化。仿真结果表明，在数据汇聚传感器网络中，与多跳TDMA和集中式TDMA调度算法相比，该算法节省了约10%的传感器网络能量，降低了数据汇聚时间。

无线传感器网络；能量消耗；多信道；调度算法；时隙

1 概述

无线传感器网络（Wireless Sensor Network，WSN）因其成本低廉、部署灵活、覆盖范围广，在环境感知、入侵检测、战场监测等领域具有广泛应用前景［1］。当传感器节点部署完毕之后，节点通常采用自组织方式形成多跳数据汇聚树，并由一个数据汇聚节点，即Sink完成数据汇聚。传感器节点周期性采集传感数据并以单跳或多跳的方式将数据投递至Sink［2-3］。

对于大多数部署在无人监管的恶劣环境中的传感器网络而言，由于节点采用容量有限的电池提供能量，大部分节点无法进行电池更换或充电，降低节点能量消耗是延长网络寿命的有效手段。

从无线信道访问的角度看，采用随机信道访问机制，如载波侦听多路访问/冲突避免（Carrier Sense M ultip le Access with Collision Avoidance，CSMA/ CA）等将导致明显的数据包传输冲突，其主要原因是无线传感器网络中存在的多跳传输与隐藏节点问题。数据包传输冲突导致数据重传将消耗节点能量并降低网络性能。面向传感器网络的时分多址（Time Division Multiple Address，TDMA）调度算法［4］通过对节点访问信道的时隙进行预先安排，能够有效剔除节点之间的数据传输冲突与信道竞争。通过避免节点空闲侦听，节点能够有效节省能量以延长网络寿命。目前，针对传感器网络能量优化的TDMA调度算法主要有考虑降低空闲时隙内传感器节点的能量消耗的TDMA调度算法［5-7］。类似的，文献［8］提出了延长节点休眠间隔的方式来降低能量消耗的调度策略。而通过对相关数据进行融合以降低节点间通信负载，传感器网络的能量消耗能够得到明显下降［9-11］，调度算法因而能够实现在能量优化的同时优化网络性能，然而，此类算法并不适用于周期性收集感知数据的传感器网络应用。以分簇的无线传感器网络应用中的能量与延迟问题为研究出发点，文献［12］提出了跨层优化方案。MODESA［13］是面向数据汇聚应用的多信道时隙分配算法，其主要研究目标是优化数据汇聚时间而并没有考虑节点的能量消耗情况，该算法假设Sink节点具备多个射频天线。利用多信道技术，文献［14］实现了块数据的多跳传输以获得更高的网络吞吐量，算法同样没有优化节点能量消耗。

上述调度算法中主要通过降低传感器节点工作时间，或者降低网络通信负载，又或者降低节点的数据采集周期来优化网络能量消耗，而多信道技术目前主要用于优化传感器网络吞吐量或数据汇聚时间，这些算法并没有考虑到传感器节点在低通信负载、低功耗的网络环境中不同工作状态的能量消耗问题，影响网络生存时间。鉴于多信道技术与节点调度算法在优化网络性能方面的优势，本文提出一种基于多信道技术的网络能量效率优化算法。该算法通过接收端为节点分配时隙，并采用多信道技术保证分配给节点的时隙是无冲突的，从而实现能量与数据汇聚时间的优化。

2 问题定义

由于数据汇聚树的多跳传输特性，树中非Sink与非叶子节点均可能需要接收并转发来自子节点的大小不等的数据量，加上子节点发送时间并不连续，从而导致节点需要多次状态切换才能够完成数据汇聚。注意，节点状态切换指的是将节点从休眠状态唤醒，或者将节点从活动状态切换至休眠状态的过程。在文献［15-16］中，证明了节点在进行状态切换时的能量是不可忽略的。以Mica2 Mote传感器节点为例，表1列出了该传感器节点在各状态下的能量消耗情况［17］。

表1 Mica2 Mote节点的能量消耗

图1显示了节点在不同传输速率与负载情况下节点状态切换在一次数据传输过程中所占的百分比P，P采用下式进行计算：

其中，Esw表示节点状态切换能量消耗；Et表示传输单个数据包的能量消耗。

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

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

考虑一棵由n个传感器节点，一个数据汇聚节点Sink构成的数据汇聚树T。传感器节点集合表示为：

所有传感器节点周期性进行数据采集并将数据发送至Sink。假定节点的有效通信距离为R。当节点Vi与Vj之间的距离dνi，νj≤R时，可认为两者之间的通信是可靠的。

对于任意数据汇聚树T，数据汇聚周期内的总能量开销可采用公式进行计算：

由于在基于树的数据汇聚过程中，节点Vi需要转发的数据包数由以Vi为根的子树包含的节点数目决定，即可用表示该子树的大小。由于该子树在一段时间能够维持不变，因此节点消耗在数据传输上的总能量（即i就成为节点的固定能量开销。根据公式可知，节点状态切换能量消耗决定于其状态切换次数，因此，优化节点能量消耗问题可以转换为最小化节点状态切换次数

3 本文算法设计

本文算法结合了多信道与TDMA调度技术，并实现了2个目标：（1）通过采用基于接收端的时隙指派机制，保证分配给节点的时隙能够满足连续“接收-发送”模式，从而使得节点从开始调度到结束数据汇聚过程能够持续保持活动状态，将节点状态切换次数降低为2次。因此，对网络中任意一个节点Vi而言，（2）通过将干扰节点的时隙安排在相互正交的无线信道上，实现节点间无干扰的数据并发传输，以降低数据汇聚时间或TDMA帧长度。

本文算法的详细步骤如下：

SteP1 初始化

自下而上计算每个节点的负载并建立子节点列表，每个表项均采用二元组（Ci，Wi）表示，其中，Ci表示子节点i的编号；Wi表示子节点i的负载大小。

SteP2 基于接收端的时隙分配策略

以Sink为时隙分配开始节点，逐层往下为数据汇聚树中的所有节点分配时隙。具体而言，对于网络中具有负载Wj的非叶子节点Vj。假设其子节点列表表示为：

SteP3 多信道分配机制

当所有节点均获得了时隙指派之后，以保证节点间的数据能无冲突并发传输为目标，基于下式所示的每条信道的时隙占用情况为节点分配正交信道。对任意时隙ti，应该满足条件：当且仅当信道chi的时隙列表中没有包含时隙ti时，时隙ti才会分配给信道chi。

除此之外，为了降低信道的使用数，仅当从已使用信道序列（ch1，ch2，…，chh）中无法保证Step2中为节点指派的时隙都被分配给已有信道时，算法才会加入一条新信道，并将无法分配的时隙添加到该信道的时隙列表。

SteP4 时隙分配调整

由于在Step2中，非叶子节点Vj为其子节点集CjL分配的发送时隙是以Vj的最后一个发送时隙tj为起点，这将导致其子节点的发送时隙位于节点Vj之后。因此，为了避免此情况，算法在完成所有节点的时隙分配之后，将根据时隙分配结果，求得网络中已分配时隙的最大序号tmax。将节点分配的时隙与tmax相减，所得结果即为节点执行数据接收或发送的最终时隙分配方案。因此，对于Step2中的节点Vj，其最终时隙分配为：

综上所述，为了保证传感节点被正确调度，每个节点需要维护由信道号，时隙列表构成的节点活动调度表。节点按照该活动调度表，在正确的时隙内，执行数据接收或发送，完成后节点切换至睡眠状态，以节省能量消耗。

4 仿真结果与分析

由于需要验证算法因降低传感器节点状态切换次数而节省了能量消耗，通过统计节点状态切换次数即可实现对算法性能的分析，因此本文采用Matlab作为实验平台进行模拟实验。本文算法命名为EM-TDMA，而用于比较的算法包括集中式TDMA调度算法（命名为Centralized［17］，包含了时隙重用（即reuse on）与非重用机制（即reuse off）），支持多跳数据传输的TDMA算法（命名为M ulti-TDMA）。在所有实验中，传感器节点部署范围均为100 m×100 m，节点有效传输范围为10 m。网络中节点数在200～1 000变化，并且节点部署位置由系统随机生成，其数据汇聚树采用最短路径路由算法生成。实验采用的传感器节点为Mica2 Mote节点，其参数如表1所示。

图2展示了一个数据汇聚周期内，传感器节点的状态切换次数比较。可以看出，与Centralized算法与M ulti-TDMA算法相比，利用EM-TDMA算法所产生的节点状态切换次数明显下降。除此之外，节点状态切换次数与节点数成线性关系，即在每个数据汇聚周期内，每个节点均只需要唤醒一次就可完成所有的数据汇聚工作。

图2 传感器网络状态切换次数

图3 描述了在单个数据汇聚周期内，传感器网络在状态切换能量消耗情况。实验结果表明，在网络规模相同的情况下，采用EM-EDMA算法的传感器节点状态切换能量消耗较M ulti-TDMA算法与Centralized算法减少约10%。而降低了能量消耗的主要原因是采用EM-TDMA算法的节点每个周期内仅需要切换其工作状态2次，即从休眠状态切换至工作状态。当数据汇聚过程结束后，节点从工作状态切换至休眠状态。

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

由于在采用Mica2 Mote节点的传感器网络中，其典型速率为19.2 Kb/s［18］，结合表1可知，对于一个需要长时间低功耗周期性运行的无线传感器网络，EM-TDMA算法在延长网络寿命方面将获得明显的性能改善。

为了验证多信道技术在优化数据汇聚时间上的性能，本文通过实验比较了3种算法在相同网络规模情况下的TDMA调度长度（单位是时隙，表示电路交换汇总信息传送的最小单位）。图4显示了得出的TDMA调度长度。可以看出，通过在传感器节点间的时隙重用策略，EM-TDMA和时隙重用的Centralized（reuse on）2种算法能够让多个节点在同一时隙内进行无冲突数据传输，从而降低数据汇聚时间。而在M ulti-TDMA与非时隙重用的Centralized算法中，由于时隙无法被多个节点同时使用，数据传输活动无法在节点间并发执行，从而无法缩短数据汇聚时间。

图4 TDM A调度长度

图5 显示了完成节点状态切换能量优化对信道数的需求情况，以及相应数据汇聚树的路由跳数。实验结果表明，在网络规模较小（节点数为200～700之间）的情况下，满足能量优化所需要的信道数不超过6。随着网络规模增加至1 000个传感器节点，需要的信道数渐增至9。这表明在大多数网络中，现有无线信道的频谱划分（16个信道）能够满足算法的需求。

图5 信道数与网络规模的对应关系

5 结束语

本文提出结合多信道与TDMA技术的无线传感器节点调度算法。该算法利用了无线信道间的无冲突数据并发传输能力与TDMA在消除节点空闲侦听、信道访问竞争的优势，与仅能优化节点能量效率的调度算法相比，该算法同时实现了对节点唤醒能量消耗与数据汇聚时间的优化，并通过仿真实验结果证明了算法的有效性。今后将进一步设计兼顾能量与网络效率的无线传感器网络调度算法，在无线传感器网络测试平台上实现并详细评估算法的性能。

［1］ 任丰原，黄海宁，林 闯.无线传感器网络［J］.软件学报，2003，14（7）：1282-1291.

［2］ IncelöD，Ghosh A，Krishnamachari B，et al.Fast Data Collection in Tree-based Wireless Sensor Networks［J］. IEEE Transactions on Mobile Computing，2012，11（1）：86-99.

［3］ Gnawali O，Fonseca R，Jamieson K，et al.CTP：An Efficient，Robust，and Reliable Collection Tree Protocol for Wireless Sensor Networks［J］.ACM Transactions on Sensor Networks，2013，10（1）：1-16.

［4］ 张晓玲，梁 炜，于海斌，等.无线传感器网络传输调度方法综述［J］.通信学报，2012，33（5）：143-157.

［5］ Zhao Wenbo，Tang Xueyan.Scheduling Sensor Data Collection with dynamic Traffic Patterns［J］.IEEE Transactions on Parallel and Distributed System s，2013，24（4）：789-802.

［6］ Niu Jianjun，Deng Zhidong.Distributed Self-learning Scheduling Approach for Wireless Sensor Network［J］. Ad Hoc Networks，2013，11（4）：1276-1286.

［7］ Prashanth L A，Chatterjee A，Bhatnagar S.Two Timescale Convergent Q-learning for Sleep-scheduling in Wireless Sensor Networks［J］.Wireless Networks，2014，20（8）：2589-2604.

［8］ Pantazis N A，Vergados D J，Vergados D，et al.Energy Efficiency in Wireless Sensor Networks Using Sleep Mode TDMA Scheduling［J］.Ad Hoc Networks，2009，7（2）：322-343.

［9］ Luo Tie，Motani M，Srinivasan V.Energy-efficient Strategies for Cooperative Multichannel MAC Protocols［J］. IEEE Transactions on Mobile Computing，2012，11（4）：553-566.

［10］ Liu Binghong，Jhang J Y.Efficient Distributed Data Scheduling Algorithm for Data Aggregation in Wireless Sensor Networks［J］.Computer Networks，2014，65：73-83.

［11］ Ma Junchao，Lou Wei，Li Xiangyang.Contiguous Link Scheduling for Data Aggregation in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed System s，2014，25（7）：1691-1701.

［12］ Li Qishi，Fapojuwo A.Energy Efficient and Delay Optimized TDMA Scheduling for Clustered Wireless Sensor Networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference.Washington D.C.，USA：IEEE Press，2009：1-6.

［13］ Soua R，Minet P，Livolant E.MODESA：An Optimized Multichannel Slot Assignment for Raw Data Convergecast in Wireless Sensor Networks［C］//Proceedings of IEEE the 31st International Performance Computing and Communications Conference.Washington D.C.，USA：IEEE Press，2012：91-100.

［14］ Gabale V，Chebrolu K，Raman B，et al.PIP：A Multichannel，TDMA-based MAC for Efficient and Scalable Bulk Transfer in Sensor Networks［J］.ACM Transactions on Sensor Networks，2012，8（4）：1-34.

［15］ Van L H，Havinga P.A Lightweight Medium Access Protocol（LMAC）for Wireless Sensor Networks：Reducing Preamble Transmissions and Transceiver State Sw itches［C］//Proceedings of the 1st International Workshop on Networked Sensing Systems.Washington D.C.，USA：IEEE Press，2004：205-208.

［16］ Xing Guoliang，Lu Chenyang，Zhang Ying，et al. M inimum Power Configuration for Wireless Communication in Sensor Networks［J］.ACM Transactions on Sensor Networks，2007，3（2）：1-30.

［17］ Ma Junchao，Lou Wei，Wu Yanwei，et al.Energy Efficient TDMA Sleep Scheduling in Wireless Sensor Networks［C］// Proceedings of INFOCOM'09.Washington D.C.，USA：IEEE Press，2009：630-638.

［18］ Lee W L，Datta A，Cardell-Oliver R，et al.A Flexibleschedule-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.

编辑 刘冰

Energy Efficient Sensor Node Schedu ling Algorithm Based on Multiple Channels

ZHANG Zhixuea，ZENG Boa，b，ZHANG Gegea，b，WANG Huia，b
（a.Network Information Center；b.Information Engineering College，Henan University of Science and Technology，Luoyang 471023，China）

In Wireless Sensor Network（WSN），traditional Time Division Multiple Address（TDMA）scheduling algorithm does not consider the energy of nodes sw itching between different states，and reduces the network survival time. In order to solve this problem，a receiver-based TDMA time slot assignment strategy is proposed.The process of slot allocation begins with the sink node，and the slots shifted according to the amount of data are assigned to children based on the slots owned by their parent.The objective is to assure that the nodes transmission meet the consecutive receive transmit mode and to minimize the number of node's state sw itching to 2.And the energy consumption of node is reduced.An optimized multi-channel assignment mechanism is used to resolve the collision of slot assignment by allocating time slot to different channel，and implement time slots reuse and optimize the number of channels.Simulation result shows that the algorithm conserves over 10%energy consumption and reduces data gathering time compared with multi-TDMA and centralized TDMA scheduling algorithm in WSN for data collection.

Wireless Sensor Network（WSN）；energy consumption；multiple channels；scheduling algorithm；time slot

10.3969/j.issn.1000-3428.2015.09.024

张治学，曾 波，张各各，等.基于多信道的能量高效传感器节点调度算法［J］.计算机工程，2015，41（9）：135-139.

英文引用格式：Zhang Zhixue，Zeng Bo，Zhang Gege，et al.Energy Efficient Sensor Node Scheduling Algorithm Based on Multiple Channels［J］.Computer Engineering，2015，41（9）：135-139.

1000-3428（2015）09-0135-05

A

TP393

河南省重点科技攻关计划基金资助项目（132102210246）；河南省科技攻关计划基金资助项目（13B510001）；河南省自然科学基金资助项目（14A510015）。

张治学（1963-），男，实验师，主研方向：无线网络通信；曾 波、张各各，讲师、博士；王 辉，教授。

2015-04-23

2015-06-26 E-m ail：zhangzx@haust.edu.cn