基于负载分割理论的无线传感器网络任务调度算法

乔 蕊，李 靖

（周口师范学院计算机科学与技术学院，河南周口466001）

报告汇聚节点子任务Wi的最小测量时间为：

基于负载分割理论的无线传感器网络任务调度算法

乔 蕊，李 靖

（周口师范学院计算机科学与技术学院，河南周口466001）

利用分簇思想和负载分割理论，提出基于一种集群结构的无线传感器网络任务调度算法。将整个无线传感器网络划分为多个簇进行负载分割，采用簇间和簇内任务调度建立任务执行过程的时序图，通过最小化总任务时间，实现任务所需数据测量、融合和传输时间的合理分配，达到任务的最优调度。仿真实验结果表明，该算法能缩短任务执行时间，并减少节点在任务执行过程中的能量消耗。

无线传感器网络；任务调度；网络分簇；负载分割理论；节点能耗

1 概述

在最短时间内传感器之间的传感任务只有被及时分配和处理才能保证用户快速获取传感数据，且快速分配和执行任务有助于减少系统能量消耗。有向无环图和独立任务集通常作为传感器任务调度的建模工具，但这2种模型的调度问题是一个NP难问题［1-2］。为有效解决无线传感器网络（Wireless Sensor Netw ork，WSN）的任务调度问题，本文基于启发式方法，采用负载分割理论得到任务调度的最优解决方案。负载分割理论可以使给定的任务在最短时间内获得最佳分割和调度策略。在采用负载分割理论对传感器网络进行处理时，所采用的网络拓扑结构为单级树状结构或集群结构（均质多级树形结构）。虽然在无线传感器网络中［3-4］，单级树状结构简单、容易实现，但并不适合于采用负载分割理论的无线传感器网络［5-6］。因此，本文提出的基于负载分割理论的传感器网络采用集群结构进行分析，通过最小化总任务时间，使得集群算法可以对网络进行有效分簇，实现多个子任务划分，同时充分利用网络资源，达到任务的最优调度。

2 相关工作

文献［7］提出一种WSN中基于多目标优化的协同任务分配算法，建立基于动态联盟的、具有跟踪精度、系统能耗、负载均衡等多个目标参数的优化模型，并基于折中度的决策精选策略，从最优解集中选出最终的任务分配方案，该算法可以获得较好的任务调度结果。文献［8］提出一种无线传感器网络可分负载调度算法，该算法在群内调度阶段，采用群内节点共享同一信道，相继向群首发送数据的方式，而在群间调度阶段，采用群首节点和Sink节点之间独立的信道使得群首将群内节点报告的数据融合，可以减少总任务完成时间，提高资源利用率。文献［9］提出一种无线传感器网络中带复杂联盟的自适应任务分配算法，以节点能耗和网络能量分布平衡为优化目标，并且采用矩阵的二进制编码形式，通过设计一种离散粒子群优化算法以并行生成联盟，并执行基于负载和能量平衡的子任务分配算法，能够在较短时间内得到较好的任务调度解。文献［10］提出无线传感器网络分布式数据链路（Data Link，DL）推理任务的上下文感知任务调度算法，该算法结合无线传感器网络和分布式本体进行一致推理，基于本体的方法和DL推理来优化带宽利用率和功率消耗。文献［11］提出一种多功能无线传感器网络系统并发应用的节能任务分配算法，采用一种新的资源分配启发式的多功能无线传感器网络系统，以最大限度地提高系统寿命，通过有效的启发式与服务参数进行任务调度，最大化地利用网络资源，减少能量损耗。

3 面向任务调度的WSN系统场景分析

假设无线传感器网络在其生命周期构建多个集群，每个集群有一个建立阶段和稳态阶段，假设在稳态阶段有K个簇网络［16-18］，每个簇头表示为Ci，在每一个簇Gi内，有j个节点表示为，簇头和汇聚节点Si之间的通信链路表示为li（i≤K）。在簇内节点和簇头之间的通信链路表示为（

系统场景需要用到的符号表示如下：Wi表示通过汇聚节点分配到簇头Ci的负载总数；表示在簇Gi内分配给群集内节点的负载数，其中，Wi和分别满足：表示一个簇头Ci的处理（数据融合）速度成反比的常量。表示一个与簇内节点nij的感测速度成反比的常量。表示一个与簇头Ci和簇内节点之间的链路速度成反比的常量。TD表示当λi=1时在一个簇头融合所有负载所需的时间。λiTDbi表示在簇头Ci融合负载所需的时间。TE表示当λi=1时采用簇内节点感测整个负载时间，在簇内的节点上所有被分配的负载被感测出所用的时间为表示通信强度不变时，当时它需要发送的所有处理负荷。整个负载可以通过第i条链路传输，所用时间为ψ表示簇头C的效用信息。T表示一个给iiK定任务的完成时间。本文将大规模传感器网络中的任务调度问题进行优化，通过尽可能地减少TK提高任务完成速度。

4 簇内任务调度模型

图1给出了一组簇内任务处理时序图。从图1可以看出，每2个连续的节点之间没有时间差，因为可分配的工作量能够在簇中进行转移。所有节点在同一时间开始测量数据。一旦一个节点完成传输数据的任务，另外一个节点完成测量任务并开始报告其数据。最后所提出的时序图通过安排每个节点的测量时间和报告时间来最小化任务完成时间。

图1 簇内任务处理时序图

对于簇头Ci，基于图1所示的时序图，在簇Gi内任务分配给簇内节点可以表示如下：

其中：

簇头Ci使用获取j-1个剩余的传感器所测量到的数据量，表示为：

报告汇聚节点子任务Wi的最小测量时间为：

5 簇间任务调度模型

在簇头融合了簇内节点的数据后，簇头可以通过一个单独的信道发送融合数据给汇聚节点。为提高任务工作效率，减少节点闲置所带来的性能下降问题，如图2的任务调度时序图所示，可以得到：

图2 簇间任务调度时序图

将式（6）简化为：

将σi引入到式（7）中，可以得到：

得到簇头Ci从汇聚节点接收到的负载量Wi和簇内节点从汇聚节点接收到的负载量所得到的总任务执行时间如下：

无线传感器网络每个簇内的传感器网络参数，具体如下：测量速度λ，通信速度η，数据融合速度θ和信息效用Ψ，且都具有m个节点，汇聚节点能够均匀地给每个簇分配负载，因此假设负载量为1，则任一簇Gi分配的负载量为：

任一簇Gi完成总任务最小花费时间是：

6 任务调度能耗模型

在无线传感器网络中有3种类型的能源消耗，包括数据测量、数据融合及通信。由于每一个簇内的节点通过数据传输来协作执行任务，因此在簇内节点、簇头都存在能耗，而簇头不需要花费能量在数据测量上，但需要花费能量在数据融合上，而通信所产生的能耗是两者都具有的。在本文中测量、融合以及发送和接收一个单元的感知数据分别用ES，EF，ET，ER来表示。假设发送端节点i和接收端节点j的距离为d（i，j），则在执行任务负载为Wi的簇内节点i所消耗的能量表示为：

在执行任务负载为Wi的簇头节点i所消耗的能量表示为：

汇聚节点i所需要消耗的能量表示为：

7 实验仿真与结果分析

本文研究不同参数λ，η，θ，ψ对每个簇内的节点的最小任务完成时间的影响。仿真软件采用Matlab7.1，算法模拟仿真环境设置为：节点感知每单元数据的能耗为ES=200 nJ，发送每单元数据的能耗为ET=200 nJ，接收每单元数据的能量消耗为ER= 100 nJ，融合每单元数据的能量消耗为EF=30 nJ。接收端和发送端之间相距d（i，j）=100 m，每个簇内设定为50个节点。假设时间参数TD=TE=TF=1。

本文选择参数λ的变化范围为（0，1）之间，并分别取在这个范围内的4个λ值进行仿真，其他参数不变，都设置为1，从图3可以看出，簇的数量越小时，参数λ的值越大，任务完成时间越小，当参数λ保持不变，簇数量增大时，则完工时间会随之变小。可以看出，在参数λ在［0.2，0.4］的范围内，完工时间随着簇数量和参数λ的增大而减少。

本文选择参数λ，η，θ和ψ的变化范围都在（0.5，1.5）之间，并分别取在这个范围内的4个η，θ和ψ值进行仿真，在此实验中其他参数都保持不变，设置为1。从图4可以看出，参数η在范围［0.6，1.2］内变化时，任务完成时间随着簇数量和参数η的增大而减小。从图5可以看出，随着簇数量的变化任务完成时间逐渐减小，而当参数θ发生变化时，任务完成时间的变化幅度很小，因此参数θ在（0.5，1.5）之间变化时对任务完成时间的影响基本可以忽略。

图4 参数η对任务完成时间的影响

图5 参数θ对任务完成时间的影响

从图6可以看出，参数ψ的值越大会造成算法在执行任务时的完工时间越长，因此参数ψ在（0.5，1.5）之间取值越小越有利。

图6 参数ψ对任务完成时间的影响

在上述实验中，通过仿真实验可知，参数λ，η，θ和ψ的取值变化对任务完成时间的影响，因此在接下来的实验中尽量选取有利的参数，并在实验对比中进行体现。

本文选取的参数值如下：λ=0.4，η=1.2，θ= 0.8，ψ=0.6。对比算法为基于分布式DL推理的任务调度算法［10］与基于系统并发应用的节能任务调度算法［11］。图7为不同簇数量下算法的任务完成时间对比，其中本文提出的基于负载分割理论的任务调度算法在完成相同任务上需要的时间更少。由于本文算法采用将无线传感器网络分成多个簇，再通过簇间和簇内的节点任务调度来最小化完工时间，相比另外2个算法采用一个汇聚节点为传感器内所有节点进行任务分配的方法更加有效。

图7 算法任务完成时间比较

图8 为在执行完任务后传感器网络节点的平均能量消耗情况，在实验中逐渐增大簇的数量，可以看出，簇的数量越多，节点的平均能量消耗量越少，这是因为有更多的簇来分担任务量，从而使每个簇内的节点负担变得更小。基于系统并发应用的节能任务调度算法基于节能目的进行设计，因此在节能方面表现较好，但随着簇数量的逐渐增多，本文的节能效果更加明显，能量消耗量相比基于系统并发应用的节能任务调度算法要更少。

图8 节点平均能量消耗比较

8 结束语

为缩短无线传感器网络在执行数据采集任务时所消耗的时间，从而提高任务执行效率，并且通过减少任务执行时间来降低网络能耗，本文提出一种基于负载分割理论的集群传感器任务调度算法，通过将整个无线传感器网络划分为多个簇进行负载分割，利用汇聚节点将任务分配给簇头，再由簇头进行簇内任务调度，以最小化任务完成时间为目标来合理分配执行任务所需的数据测量、融合和传输时间。实验仿真及对比分析结果表明，本文算法可以有效缩短执行任务所需时间，并降低网络节点能量消耗。今后将对不可靠环境下的无线传感器网络节点定位、数据通信及能耗问题作进一步研究。

［1］ Shrivastava P，Pokle S B.Energy Efficient Scheduling Strategy for Data Collection in Wireless Sensor Networks［C］//Proceedings of 2014 International Conference on Electronic System s，Signal Processing and Computing Technologies.Washington D.C.，USA：IEEE Press，2014：170-173.

［2］ Mezei I，Lukic M，Malbasa V，et al.Auctions and iMesh Based Task Assignment in Wireless Sensor and Actuator Networks［J］.Computer Communications，2013，36（9）：979-987.

［3］ Jin Y，Vural S，Gluhak A，et al.dynamic Task Allocation in Multi-hop Multimedia Wireless Sensor Networks with Low Mobility［J］.Sensors，2013，13（10）：13998-14028.

［4］ Chen J，Guo W.A PSO-optim ized Nash Equilibrium based Task Scheduling Algorithm for Wireless Sensor Network［M］.Berlin，Germany：Springer，2013：62-73.

［5］ Shao Yuanhai，Chen Weijie，Zhang Jingjing，et al.An Efficient Weighted Lagrangian Twin Support Vector Machine for Imbalanced Data Classification［J］.Pattern Recognition，2014，47（9）：3158-3167.

［6］ Peng X，Xu D.Structural Regularized Projection Tw in Support Vector Machine for Data Classification［J］. IEEE Transactions on Neural Networks，2014，22（4）：416-432.

［7］ 杜庆伟，顾汉杰，陶 军.WSN中基于多目标优化的协同任务分配算法［J］.东南大学学报：自然科学版，2014，44（4）：11-15.

［8］ 代 亮，许宏科，陈 婷.无线传感器网络可分负载调度算法［J］.西安交通大学学报，2012，46（6）：23-28.

［9］ 郭文忠，苏金树，陈澄宇，等.无线传感器网络中带复杂联盟的自适应任务分配算法［J］.通信学报，2014，35（3）：1-10.

［10］ Verstichel S，Volckaert B，Dhoedt B，et al.Contextaware Scheduling of Distributed DL-reasoning Tasks in Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2011，3：1-24.

［11］ LiWei，Delicato F C，Pires P F.Energy-efficient Task Allocation with Quality of Service Provisioning for Concurrent Applications in Multi-functional Wireless Sensor Network System s［J］.Concurrency and Computation：Practice&Experience，2014，26（11）：1869-1888.

［12］ Guo W，Xiong N，Chao H C，et al.Design and Analysis of Self-adapted Task Scheduling Strategies in Wireless Sensor Networks［J］.Sensors，2011，11（7）：6533-6554.

［13］ Xiong Shuguang，Li Jianzhong，Li M o，et al.Multiple Task Scheduling for Low-duty-cycled Wireless Sensor Networks［C］//Proceedings of IEEE INFOCOM'11. Washington D.C.，USA：IEEE Press，2011：1323-1331.

［14］ Ergen S C，Varaiya P.TDMA Scheduling Algorithm s for Wireless Sensor Networks［J］.Wireless Networks，2010，16（4）：985-997.

［15］ Abdelhak S，Gurram C S，Tessier J，et al.ETSSI：Energy-based Task Scheduling Sim ulator for Wireless Sensor Networks［C］//Proceedings of IEEE International Symposium on Circuits and System s. Washington D.C.，USA：IEEE Press，2011：2821-2824.

［16］ Dai Liang，Chang Yilin，Shen Zhong.An Optimal Task Scheduling Algorithm in Wireless Sensor Networks［J］. International Journal of Computers Communications& Control，2011，6（1）：101-112.

［17］ Toscano E，Bello L.Multichannel Superframe Scheduling for IEEE 802.15.4 Industrial Wireless Sensor Networks［J］.IEEE Transactions on Industrial Informatics，2012，8（2）：337-350.

［18］ DaiLiang，Chang Y ilin，Shen Zhong.Non-cooperative Game Algorithm for Task Scheduling in Wireless Sensor Networks［J］.International Journal of Computers Communication&Control，2011，6（3）：592-602.

编辑 陆燕菲

Task Schedu ling Algorithm in Wireless Senser Network Based on Load Segm entation Theory

QIAO Rui，LI Jing
（School of Computer Science and Technology，Zhoukou Normal University，Zhoukou 466001，China）

In order to more effectively solve the task scheduling problem in Wireless Sensor Network（WSN），a cluster sensor task scheduling algorithm based on the idea of clustering and the theory of load segmentation is proposed.The whole WSN is divided into several clusters，and the timing diagram of task execution process is established by using the process of task scheduling between inter-cluster and intra-cluster.Reasonable distribution is performed between measurements of tasks performing，fusion，and transmission time by minimizing the total task time.It makes full use of network resources.Experimental results show that the algorithm shortens the task execution time of WSN，and further reduces the average energy consumption of nodes in the process of executing the task.

Wireless Sensor Network（WSN）；task scheduling；network clustering；load segmentation theory；energy consumption of node

乔 蕊，李 靖.基于负载分割理论的无线传感器网络任务调度算法［J］.计算机工程，2015，41（9）：140-144.

英文引用格式：Qiao Rui，Li Jing.Task Scheduling Algorithm in Wireless Senser Network Based on Load Segmentation Theory［J］.Computer Engineering，2015，41（9）：140-144.

1000-3428（2015）09-0140-05

A

TP393

10.3969/j.issn.1000-3428.2015.09.025

河南省软科学研究计划基金资助项目（132400411253）；河南省高等学校重点科研基金资助项目（15A520115）。

乔 蕊（1983-），女，讲师、硕士，主研方向：无线传感器网络，图像处理；李 靖，讲师、硕士。

2014-12-03

2015-01-24 E-m ail：18033023@qq.com