基于任务相关性的无线传感器网络任务调度算法

严芳芳，石 悦，魏 伟

（1.太原大学 太原030024；2.北京邮电大学 北京100876；3.国网电力科学研究院信息通信技术服务中心 北京100761）

1 引言

无线传感器网络（wireless sensor network,WSN）是一种信息获取及处理技术，有着广泛的应用和发展前景，在军事、工业、商业等领域体现出许多优越性。任务调度问题是无线传感器网络中的一个重要问题，也是多代理（agent）系统中的热点问题之一。其原因是：第一，任务调度的结果会直接影响到网络的生存周期；第二，任务调度机制的好坏直接关系到系统中的各节点能否最大限度地发挥自身的能力，避免占用更多的资源；第三，任务调度的结果会影响到任务的完成时间，进而影响到整个网络的性能。

无线传感器网络有着自组织性、动态性等特点，同时又有着网络通信资源受限、节点之间存在通信冲突的问题，这就需要合理设计其任务调度算法，减小网络节点的能耗，从而延长节点的生命周期[1]。对任务进行聚簇调度，有利于减少完成任务所需的节点数目，减少完成任务的时间，提高节点的利用率。

在整个网络的任务组中，可能很多任务之间存在相互依赖的关系。如果将任务直接分配给普通节点，可能会造成有的任务等待时间过长，占用系统资源过多，也影响到其他任务的完成。需要sink节点合理地对它们之间的执行顺序做一个规划，确保任务按时高效完成。对任务间的相关性进行分析并进行聚簇、任务复制，目的在于降低节点间的通信能耗，同时减少完成整个任务组的时间。

本文采用有向无环图 （directed acyclic graph，DAG）对任务间的依赖关系进行描述，并针对无线传感器网络的特性对任务进行聚簇调度，提出了一种新的聚簇算法。

2 相关工作

[2]提出了一种应用于多处理器和分布式系统的时间相关性的研究方案，使用非抢占调度策略捕获了输出时间流的时间相关性。但其着重于对相关性的捕获分析，没有从任务的角度考虑调度问题。本文根据任务相关性，利用DAG对任务间的依赖关系做出描述，从而实现对任务的聚簇调度。参考文献[3]基于图论和贝叶斯方法提出了网格计算系统中的任务分解和资源分配的方案，得到了最优的服务性能（即最小执行时间）。但这种策略大大增加了节点的计算量，不适用于能量有限的无线传感器网络。本文通过对调度机制的改进，分析任务间的相关性，而后进行聚簇和复制，适当降低了任务完成所需的节点数和任务时间，从而降低节点能耗，以达到延长网络生命周期的目的。参考文献[4]基于逻辑优化和任务并行分配算法，提出了一种新的逻辑优化调度分配的处理算法。但这也是偏重于逻辑上的调度，未考虑到实际应用中的节点间通信等问题。本文考虑到无限传感器网络的通信冲突和能耗问题，在调度机制中引入根据任务相关性进行的聚簇和任务复制的方式，以减小节点间的通信量，提高了节点的利用率，令调度算法适用于实际的动态网络环境。

为此，本文提出了一种基于相关性的任务调度算法，以解决现有的无线传感器网络中的静态调度算法（静态关键路径（static critical path，SCP）算法）在调度具有相关性任务时的缺陷，尽量减少任务复制的次数以减小总的完成时间；同时，尽量减少完成任务的节点数目，也能有效降低节点间的通信能耗。

3 基于相关性的任务调度算法

3.1 任务描述

任务的相关性通常用一个有向无环图表示，如图1所示。DAG=（T，E，W）为一个三元组。其中，T是任务节点的集合，ti∈T，ti表示第i个任务；E是任务间通信开销的集合，eij∈E，eij表示ti和tj之间的通信的时间开销，如果两个任务被交付给同一节点，那么eij=0；W是任务的完成时间的集合，W（ti）指任务ti的预计完成时间。

图1 任务的有向无环图表示

在任务的DAG中，根据任务间的依赖关系，有任务的前驱节点集合和后继节点集合之分，令pred（ti）=｛j|eji∈E｝、post（ti）=｛j|eij∈E｝成立，则pred（ti）和post（ti）分别为ti的前驱节点和后继节点；若pred（ti）=覫，那么任务ti被称为入节点（in node）；若post（ti）=覫，那么任务ti被称为出节点（out node）。从入节点到出节点的最长路径（节点的计算成本和各个边的通信成本之和）为这个图的关键路径。

设任务ti的最早开始时间 （earliest start time，EST）为EST（ti），最晚开始时间（latest start time，LST）为LST（ti），最晚完成时间（latest finished time，LFT）为LFT（ti），在处理器pj上的实际开始时间（actual start time，AST）为ASTpj（ti），则任务ti的完成时间（finished time，FT）为：

若ti为tj的前驱节点，即ti∈pred（tj）。ti的数据到达tj的时间（arrive time，AT）为：

3.2 基于任务相关性的聚簇调度算法

3.2.1 基本思想

针对DAG的调度问题，SCP算法的主要思想是任一节点的执行只有在全部优先它的节点完成后才能开始。EST可以直接或间接地用于决定各个节点的优先级，从而实现DAG的调度。因此，针对DAG调度，关键的问题是如何精确地预估一些时间变量，如EST等。首先对SCP算法进行研究，该算法步骤描述如下。

（1）对于坌ti，计算其EST（ti），并确定一条静态关键路径。

（2）置任务优先级队列为空，取静态关键路径上的第一个节点作为当前节点ti。

（3）入度通常指有向图中节点作为图中边的终点的次数之和。如果ti的入度为0，则将该节点作为任务优先级队中最后一个节点插入队列，并把该节点的子节点的入度减1，转步骤（4）；如果ti的入度不为0，则先对其所有的尚未进入任务优先级队列的父节点tj按ESTj+tj+eij的大小由大到小排序。以第一个父节点及其尚未进入任务优先级队列的祖先节点为子图，构成一个有向无环图，递归地创建该子图的任务优先级队列，并将该子图的任务优先级队列添加到要创建的任务优先级队列的队尾。用类似的方法处理其余父节点构成的子图。最后再将节点ni加到任务优先级队列的队尾，并把该节点的子节点的入度减1。

（4）如果当前节点为最后一个节点，则任务优先级队列创建完成，否则取静态关键路径上的下一个节点作为当前节点，执行步骤（3）。

（5）任务优先级队列中的第一个任务作为当前任务，为该任务选择最早可用的处理器。

（6）计算当前任务在当前处理器上的EST，分配到当前最早可用的处理器上。

（7）如果当前任务为任务优先级队列中的最后一个任务，则结束；否则，取下一个任务作为当前任务，执行步骤（5）。

针对图1中的DAG任务描述，通过SCP算法得到的调度结果如图2所示。图中小方格表示一个处理器空闲的时间单位。通过图2可知，调度的EST=27。通过任务复制的方式将该任务的描述转化为如图3所示的树型（称为簇树）来描述任务之间的关系，可以发现任务间的并行关系，为了引出基于任务相关性的调度算法，引入调度簇、簇树、调度簇的完成时间和聚簇的概念。

图2 SCP算法的调度结果（EST=27）

定义1（调度簇（scheduled cluster））调度完成后映射到同一处理器上的有序任务簇，记为Ci（i=1，2，…，m）。其中，包含开始任务和结束任务、执行时间等于调度长度（SL）的调度簇为关键调度簇，记为Ckey。Ckey之外的所有其他调度簇为非关键调度簇，记为Ci。

定义2（簇树（clustered tree））对于DAG经调度后得到的一组簇Ci（i=1，2，…，m），以Ckey为基础，将各Ci上的复制任务合并而生成的树称为簇树，简称为CT树。例如对于图2中的各调度簇，以Ckey为基础，通过合并复制任务t1，可 得 图3中 的CT树，图3中 的 调 度 簇Ckey={t1，t3，t6，t10，t9，t11}，C1={t1，t2，t7}，C2={t1，t4，t8}，C3={t1，t5}，可CT树上可由根节点到每个叶子节点的通路表示。节点间的通信开销在CT树上用虚线箭头标出，分别为e2,6、e5,8、e7,10、e8,9。

图3 由图1中的调度树合并得到的CT树

定义3（调度簇的完成时间）对于一个调度簇Ci，若tm1，tm2，…，tmk∈Ci，则 该 簇 的 完 成 时 间（clustered finishing time,CFT）为CFTi=W（tm1）+W（tm2）+…+W（tmk）。

定义4（聚簇）将两个调度簇合并的操作过程。

3.2.2 聚簇调度算法

ICS的主要思想基于以下原则。

·将DAG的调度结果合并为CT树，搜索所有调度簇，采用适当策略选择调度簇进行聚簇，从而减少处理器的数目和处理器间的通信能耗。

·使所有任务的完成时间达到最小，这包括任务的执行时间和通信时间，即Ckey的任务执行时间加上通信时间。

聚簇算法流程如下。

第1步 根据基于任务复制的调度算法对DAG的调度结果，获取CT树的信息（CT树不需要实际生成）。此时CT树上各调度簇与剩余通信为已知，所有节点的EST、LST、LFT值为已知。

第2步 将Ci按照CFTi从大到小的顺序排序，即排序之后，CFTkey≥CFT1≥CFT2≥CFT3≥…≥CFTk。

第3步 对于第i个簇，设剩余时间（remaining time，RT）为RTi=CFTkey-CFTi，在Ci+1到Ck中使用二分查找法，找到一个r，使CFTr≤RTi且r是满足条件的簇中的最大数。

第4步 设tm1、tm2、…、tmn是Ci和Cr的公共任务，计算FTi-tmp=FTi+FTr-（W（tm1）+W（tm2）+…+W（tmn））。

第5步 对Ci-tmp，计算其中每个任务的完成时间FT。对每个任务ti-j，若FT（ti-j）≤LST（post（ti-j）），则这次聚簇成功，否则聚簇失败。若i=k，则循环结束。若聚簇成功，则将新的簇Ci-tmp代替原簇Ci，并将Cr去掉，返回第3步。若聚簇失败，若r=k，则i++，返回第3步；若r＜k，则r++，返回第4步。

第6步 将聚簇后形成的新的调度簇分配给不同的任务节点处理。

4 实验与分析

为验证本文提出的聚簇算法——ICS（improoed clustering scheduling）算法性能，令其对图3所示的调度簇进行聚簇处理，并将得到的结果与图2的调度结果进行比较。聚簇过程见表1。

图4 ICS算法的调度结果

得到的调度结果如图4所示。

从图4可以看出，使用ICS聚簇算法对图3所示的调度簇进行聚簇以后，原来的C1、C2、C3合并成为了一个簇，整个任务被分为两个簇Ckey和C1，分配给两个节点执行。这一结果与图2的调度结果相比，在任务完成总时间不变的情况下，调度簇的数量减少了一半，节点间通信的次数由4次变为3次；同时由于调度簇的合并，重复任务t1执行的次数减少，从而使整个网络的能耗得到的降低。

进一步考虑普遍情况，随机生成几个任务组，分别运用SCP算法和ICS算法进行聚簇，得到的结果见表2（其中，节点平均利用率为实际处理时间与预留处理时间的比值）。

从表2可以看出，使用ICS算法进行聚簇，所需的节点数目、预留的处理时间和实际的处理时间都大大减少，节点的平均利用率得到了提高，这在网络中的任务组比较多的时候能体现出较大优势，其能够增加整个网络的节点利用率，减少总的任务完成时间以及减少节点的排队任务数。

表1 ICS算法的聚簇过程

表2 SCP和ICS算法的实验结果比较

5 结束语

本文针对现有的无线传感器网络中的静态调度算法（SCP算法）在调度具有相关性任务时的缺陷，提出了一种新的聚簇算法（ISC算法），该算法能够使无线传感器网络在任务调度过程中的节点间通信能耗和节点处理能耗大大降低，同时减少了总的任务完成时间，提高了节点的平均利用率，使任务在能耗减少的情况下更有效率地执行。但是，任务的过度集中不利于节点的负载均衡，有可能会出现某些节点生存时间较短的情况。在对任务调度的同时考虑对节点的调度，是今后有待进一步研究的课题。

参考文献

1 Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy efficient communication protocol for wireless micro-sensor networks.Proceedings of the 33rd Hawaii International Conference on System Sciences,Maui,Hawaii,USA,2000

2 Rox J,Ernst R.Exploiting inter-event stream correlations between output event streams of non-preemptively scheduled tasks.Proceedings of Design,Automation&Test in Europe Conference &Exhibition(DATE),Grenoble,France,2010:226～231

3 Yuan-Shun Dai,Levitin G.Optimal resource allocation for maximizing performance and reliability in tree-structured grid services.IEEE Transactions on Reliability,2007,56(3):444～453 4 Li C,Qiu J L,Gu X,et al.A task allocation algorithm for logic optimization parallel scheduling.Proceedings of 2012 Eighth International Conference on Natural Computation(ICNC),Chongqing,China,2012:1146～1150

5 AbdelSalam H S,Olariu S.Toward efficient task management in wireless sensor networks.IEEE Transactions on Computers,2011,60(11):1638～1651

6 Abdelhak S.Gurram C S,Tessier J,et al.ETSSI:energy-based task scheduling simulator for wireless sensor networks.Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS),Rio De Janeiro,Brazil,2011:2821～2824

7 Shekar V,Izadi B.Energy aware scheduling for DAG structured applications on heterogeneous and DVS enabled processors.Proceedings of 2010 International Green Computing Conference,Chicago,IL,USA,2010:495～502

8 Miranda S L C,Baker C J,Woodbridge K,et al.Comparison of scheduling algorithms for multifunction radar.IET Radar Sonar& Navigation,2007,1(6):414～424

9 李海涛.无线传感器网络中任务动态调度.电子科技大学硕士学位论文，2009