无线传感器网络任务调度双层规划方法

代亮，沈中，常义林，张颖，闫中江

(西安电子科技大学 综合业务网理论与关键技术国家重点实验室，陕西 西安710071)

0 引言

由于无线传感器网络中节点带有有限的能量，任务调度的关键问题是如何恰当地分配总任务到相应的节点上，以使得从SINK 节点下发任务到收到融合后的结果这段时间最短。

用于无线传感器网络任务调度应用建模的工具通常是有向无环图(DAG)和独立任务集。在一般情况下，基于这2 类模型的调度问题都是NP 完全的。与此形成鲜明对比的是可分负载理论(Divisible load theory)［1］。在一定条件下，可分负载理论可以得到最优解的解析解。

文献［2］首次将可分负载理论应用于无线传感器网络上来进行任务调度分析。其应用环境是，对于一个具体的数据采样空间来说，互不重叠地给每一个传感器节点分配一个采集子空间来采集数据。例如，采样空间覆盖一个很大的频率范围，可按照一定比例划分采集子空间，分配给不同的传感器来采集数据，以节省总任务完成时间及能耗。但是该文只是应用到了单层树型结构。而在无线传感器网络中，与单层树型结构相比分群结构(即多层树形结构)具有很大优势［3］。文献［4］在文献［2］的基础上，增加了对数据采集和网络通信中存在的延时的分析，但其网络拓扑还是单层树型结构。文献［5］将可分负载理论应用于无线传感器网状网(Wireless sensor mesh networks)中来分析任务调度，其任务下发到结果上报也是基于单层树型结构的。文献［6］将可分负载理论用于只有单个群的无线传感器网络中，分析了可行的指令下发时间和最短的总体完工时间。但由于分群结构的无线传感器网络都具有多个群，具有单个群的无线传感器网络没有太大的实用性，在这种网络结构下分析具有片面性。

本文基于可分负载理论，建立了双层规划［7］模型对分群结构无线传感器网络的任务调度进行优化，同时考虑了群间和群内任务分配的合理性，目标是得到在网络中SINK 节点给群首节点，群首节点给群内节点分配任务比例的最优解，以使SINK 节点从分配任务到完全得到任务执行结果的时间最短。

由于在无线传感器网络分群结构下，群首节点负责SINK 节点和群内节点的数据交互。为了减少冗余数据的传输耗能，降低延迟，延长网络的生存期，在群首节点需要进行数据融合［8］。本文基于文献［9］采用了信息效用常量方法。信息效用常量基于信息正确性估计技术，通过信息正确性估计，群首节点可以知道近似的数据融合比例。

1 问题描述

本文所讨论的无线传感器网络拓扑结构如图1所示，网络中一共有k 个群，分别表示为Clusteri，i=1，…，k，每个群内群首节点分别表示为Ci，i=1，…，k，群内分别有ni，i =1，…，k 个节点，群首和SINK节点的通信链路分别表示为li，i =1，…，k.群内的普通节点分别表示为nij(i =1，…，k;j =1，…，ni);群内节点和群首的通信链路分别用lij(i =1，…，k;j=1，…，ni)来表示。

yij是节点nij相对于标准处理器的数据采集速度;zij是第lij条链路相对于标准链路的传输速度;wi是群首Ci相对于标准处理器的计算(数据融合)速度;zi是第li条链路相对于标准链路的传输速度;φi是群首Ci的信息效用常量。

所谓的标准处理器和链路是作为参照的任何一个处理器和链路，可以是网络中的任何一个处理器和链路，甚至为了方便可以是假想的处理器和链路。

SINK 节点首先将负载划分为k 个部分，将这些子负载发送给k 个群首。第i 个群首Ci再将其负责的负载划分为ni个部分并将其发送给群内的ni个节点。定义αi是SINK 节点分配给群首Ci的负载百分比;αij是群首节点Ci分配给群内普通节点nij的负载百分比。由定义可知:

图1 网络拓扑图Fig.1 Network topology

定义Tms是整个采集业务在标准处理器上完成的时间，Tcm是在标准链路上传输这个应用的全部输入数据的时间，Tcp是整个应用在标准处理器上数据融合的时间［2］。因此αijyijTms是节点nij采集相应负载的时间，αijzijTcm是节点nij通过第lij条链路向群首Ci发送相应采集数据的时间，αiwiTcp是群首Ci融合群内节点报告的数据的时间，φiαiziTcm是群首Ci将融合后的数据报告SINK 节点所需的时间。

ti是第i 个群的群内处理时间(数据采集，报告群首)，Ti是网络中第i，i=1，…，k，个群完成相应的负载并报告SINK 节点所需的时间，Tf是整个系统响应的时间。调度的目标是整个负载的处理时间Tf最小，即各个群完成相应任务，数据融合后并报告SINK 节点所需时间Ti的最大值，即Tf=max{T1，T2，…，Tk}.

由于和其他执行过程的耗时相比较，SINK 节点和群首节点下发任务给相应节点的耗时是微不足道的。故在本文中，忽略SINK 节点，群首节点下发任务的耗时。

2 调度模型

本文考虑的任务调度模型基于可分负载理论，如图2所示:群内节点同时开始采集数据，假设群内节点共享同一信道，为了去除通信的干扰和空闲导致的性能下降，群内节点采集完相应的数据后相继向群首报告采集结果。群首节点收集群内节点采集的数据并作数据融合后，假设各群首间也共享同一信道，故也只能相继向SINK 节点报告数据。

图2 本文调度策略的时序图Fig.2 Timing diagram of this scheduling strategy

将SINK 节点给群首节点，群首节点给群内节点任务分配的优化视作一个领导者(Leader)-跟从者(Follower)问题。

上层规划可以描述为SINK 节点在满足可分负载条件下确定给群首节点分配任务的比例，使得总任务完成时间最小;下层规划描述了群首节点确定给群内节点分配任务的比例，使得该群所获子任务的完成时间最小。

由图2可知，对于上层规划来说，其数学模型为:

当上层模型达到最优时，即确定了各群首获得SINK 下发的子任务比例αi，则下层规划便根据上层规划确定的各群首的任务比例αi，寻求最优的群内分配方案，以确定群内节点应该获得的任务比例αi，j.约束条件式(3)表明了，由于各群首与SINK 间共享信道，各个群首相继将群内处理的结果融合后发送至SINK.约束条件(4)表明了总任务执行完毕。

对于下层规划来说其数学模型为

我们把上述双层规划归结成一个值型双层规划。上层规划确定了各个群应该获得的最合理的任务比例αi，下层规划确定各个群内节点所获得的最合理的任务比例αi，j，以求得最小的总任务完成时间。其中:αi和Tf分别为上层问题的决策变量和目标函数;αi，j和ti分别为下层问题的决策变量和目标函数。约束(5)表明了由于群内各节点共享信道，群内节点相继将采集的结果发送至群首。约束条件(6)说明每个群内的所有节点共同执行完该群的子任务。

双层规划模型的数学求解方法主要有K 次极点搜索法，分支定界法和罚函数法3 种［7］。本文利用罚函数原理，将线性双层规划转化为目标函数带惩罚项的单层问题，来进行本文的双线性规划模型的求解。

3 能量消耗模型

在本节，提出了分群结构的无线传感器网络能量消耗模型。在本文中，有4 种不同的能量消耗方式，分别是:数据采集，数据报告，数据接收和数据融合。在网络中，普通群内节点执行数据采集和数据报告;群首节点执行数据报告，数据接收和数据融合;SINK 节点执行数据接收。

在本文中，采用基于LEACH 协议［10］的一阶无线电模型来构造能量消耗公式。LEACH 协议的一阶无线电模型基于以下假设:1)网络中所有节点完全相同;2)无线电信号在各个方向上能量消耗相同;3)SINK 节点是固定的，并且离整个网络较远。

定义网路内节点采集，融合，报告，接收一单位数据所消耗的能量为分别为:es，ep，etx，erx;报告和发送节点间的距离均为d.

根据一阶无线电模型，可得第i 个群中第j 个节点的能量消耗为:

群首Ci的能量消耗为

SINK 节点的能量消耗为

4 仿真分析

在以上章节，我们得到了给定任务完成时间的封闭表达式和各个节点的能量消耗公式。在本章，我们对采集速度，通信速度，数据融合速度和信息效用常量这4 个系统参数在同构网络环境下，对任务完成时间和群内节点能量消耗的影响进行了仿真分析。

在仿真中，能量消耗参数如下所示:在一单位距离上，报告一单位数据所消耗的能量为etx=200 nJ;采集一单位数据所消耗的能量为es=100 nJ;报告、接收节点间的距离均为d =100 m，每个群里有30个节点。在仿真中令Tms=Tcm=Tcp=1.

因为在无线传感器网络中，SINK 节点一般没有能量限制，而且在现有的无线传感器网络分群协议中，当群稳定后，群首节点相对来说也是能量有保障的，所以在本文中，只考察群内节点的能耗情况。不失一般性，本文以第一个群中的节点来考察群内各个节点的能耗情况。

因为群数目增加，整个网络中节点的数目就会增加。网络中协作完成任务的机会也就会更多，但用于报告的开销又会增大。分别考察参数y，z，w，φ随着群的数目的增加，对系统总任务完成时间的影响，和随着负载分配的次序对群内节点能耗的影响。总体上来说，随着群数目的增加，总任务完成时间递减;随着群内各节点所承载的负载递减，各节点的能量消耗递减。

1)y，z，w 固定，令w=y=z =1.0，φ 分别取0.2，0.4，0.6，0.8，1.0.如图3(a)所示，随着群数目的增大，系统完成时间逐渐减小。信息效用常量越大，其系统完成时间减小的趋势越缓。如图4(a)所示，φ 的选取对于群内各节点的能耗情况几乎没有影响。随着群内负载的分配次序，各节点能耗递减。

2)φ，z，y 固定，令y=z=1.0，φ=0.5，w 分别取0.8，1.0，1.2，1.4，1.6.如图3(b)所示，随着网络中群数目的增加，系统总任务完成时间会减少。如图4(b)所示，随着群内负载分配的次序，群内节点的能耗递减。

3)φ，z，w 固定，令w =z =1.0，φ =0.5，y 分别取0.8，1.0，1.2，1.4，1.6.如图3(c)所示，由于数据采集只占据了总任务完成时间的很小一部分，所以传感器节点的数据采集速度的增大，对系统完成时间几乎没有影响。如图4(c)所示，群内节点采集数据的速度越大，群首可将负载更加均衡地分配给各个节点，所以各个节点的能耗越小。

4)φ，w，y 固定，令y =w =1.0，φ =0.5，z 分别取0.8，1.0，1.2，1.4，1.6.如图3(d)所示，随着群数目的增大，系统的完成时间会减少。节点间的通信速度越大，其系统完成时间减小的趋势越缓。如图4(d)所示，节点间的通信速度越大，群内节点的能耗越小。

图3 各参数对本文任务调度模型完成任务耗时的影响Fig.3 Impact of these four parameters on finish time

5 结论

由于无线传感器网络中的节点带有有限的能量，所以网络应该尽可能快的完成系统任务。可分负载理论在无线传感器网络上的应用为其任务调度提供了一个有效的解决方案。本文建立双层规划模型对分群结构的无线传感器网络的任务调度进行优化，同时考虑了群间和群内任务分配的合理性，得到了在网络中SINK 节点给群首节点、群首节点给群内节点分配任务比例的最优解，以使SINK 节点从分配任务到完全得到任务执行结果的时间最短。

随着无线传感器网络技术和泛在网络的逐步发展，可分负载理论对这种复杂网络的建模与扩展也需要进一步研究及验证。此外，目前对可分负载理论在无线传感器网络任务调度的验证仍停留在仿真试验阶段，缺乏大型的，实际的应用来证明它的真正潜力，因此可分负载理论在实际无线传感器网络的应用将是下一步研究的重要方向。

图4 各参数对本文任务调度模型群内各节点能耗的影响Fig.4 Impact of these four parameters on energy consumption of each in-cluster nodes

References)

［1］Bharadwaj V，Ghose D，Robertazzi T G.Divisible load theory:a new paradigm for load scheduling in distributed systems ［J］.Cluster Computing，2003，6(1):7 -18.

［2］Moges M，Robertazzi T G.Wireless sensor networks:scheduling for measurement and data reporting［J］.IEEE Transactions on Aerospace and Electronic Systems，2006，42(1):327 -340.

［3］刘丽萍，王智，孙优贤.无线传感器网络连接问题研究［J］.兵工学报，2007，28(9):1096 -1102.LIU Li-ping，WAN Zhi，SUN You-xian.Connectivity in wireless sensor networks［J］.Acta Armamentarii，2007，28(9):1096 -1102.(in Chinese)

［4］LIU Hao-ying，YUAN Xiao-jing，MOGES M.An efficient task scheduling method for improved network delay in distributed sensor networks［C］∥Proceedings of the International Conference on Testbeds and Research Infra-structure for the Development of Networks and Communities.Los Alamitos:IEEE Computer Society，2007:1 -8.

［5］LIU Hao-ying，SHEN Jian，YUAN Xiao-jing，Moges M.Performance analysis of data aggregation in wireless sensor mesh networks［C］∥Proceedings of the International Conference on Engineering，Science，Construction and Operations in Challenging Environments.Los Alamitos:IEEE Computer Society，2008:1 -8.

［6］Kijeung Choi，Robertazzi T G.Divisible load scheduling in wireless sensor networks with information utility performance［C］∥Proceedings of the International Performance Computing and Communications Conference.Piscataway:IEEE，2008:9 -17.

［7］王先甲，冯尚友.二层系统最优化理论［M］.北京:科学出版社，1995:12 -120.WANG Xian-jia，FENG Shang-you.Optimality theory of bi-level systems［M］.Beijing:Science Press，1995:12 -120.

［8］邓克波，刘中.基于无线传感器网络动态簇的目标跟踪［J］.兵工学报，2008，29(10):1197 -1202.DENG Ke-bo，LIU Zhong.Target tracking with dynamic clusters in wireless sensor network［J］.Acta Aramamentarii，2008，29(10):1197 -1202.(in Chinese)

［9］Lin Jianyong，Xiao Wendong，Lewis F L，et al.Energy-efficient distributed adaptive multisensor scheduling for target tracking in wireless sensor networks［J］.IEEE Transactions on Instrumentation and Measurement，2009，58(6):1886 -1896.

［10］Heinzelman W，Chandrakasan A.An application-specifid protocol architecture for wireless microsensor networks［J］.IEEE Transaction on Wireless Communications，2002，1(4):660 -670.