无线传感网中一种负载均衡的多任务调度方案

高建明　朱小华

(浙江越秀外国语学院　浙江 绍兴 312000)



无线传感网中一种负载均衡的多任务调度方案

高建明朱小华

(浙江越秀外国语学院浙江 绍兴 312000)

为了节约能量，往往设计无线传感器网络工作于低占空比模式，在此模式下传感器节点只在小部分工作期间保持活跃状态。如果应用场合有多个数据率要求高、时间紧的数据传输任务，低占空比工作模式可能会导致严重的传输拥塞和数据损失。为了减轻数据拥塞和损失，需要对任务进行详细的调度，以从时间和空间两方面平衡传感器节点工作负荷。对基于负载均衡的多任务调度问题进行研究，并证明该问题在一般网络拓扑结构下是NP完全问题，提出并分析两种高效的负载均衡调度算法。仿真结果表明，该算法极大地提高了绝大多数网络场景下的网络性能。

无线传感器网络低占空比多任务负载均衡NP完全问题

0　引　言

无线传感器网络(WSN)[1]在环境监测、结构监测、栖息地研究等跨时较长的领域具有巨大的应用潜力。为了解决传感器节点供能有限和要求系统寿命较长这一矛盾，许多研究建议无线传感器网络工作于低占空比模式[2,3]。低占空比无线传感器网络大大地延长了网络的寿命，但同时只有极短的时间供传感器接收数据。于是，低占空比工作模式无法避免地产生了两个问题：(1) 如果刚好在其极短的可用时间内，多个节点向同一节点发送数据，则会导致严重的传输拥塞问题，进而导致分组丢失，降低网络性能。(2) 由于传输拥塞，单跳传输时延变长，导致节点可能无法获得足够的带宽及时将收到的数据分组转发出去。在高速数据应用情况下，数据分组很可能由于缓冲器溢出而丢失。

如果网络中存在多个数据转发任务，则这两个问题可能会更加严重。如果传输调度设计不当，则网络转发能力在时间和空间层面将会无法得到有效利用。为了对具有时间约束的多数据转发任务进行协调，需进行细致的任务调度，根据负荷调度表，实现传感器的负荷平衡。然而，当前在低占空比无线传感器网络多任务调度性能提升方面研究不多。如何在时间约束条件下就给定的数据传输请求，确定最优调度方案，以实现负荷在传感器节点中的均匀分布，这一问题仍然没有解决。因此，在本文中，对低占空比无线传感网络多任务调度问题展开深入研究，并提出高效算法，以对任务进行调度，实现传感器均衡使用。

1　相关工作

人们已经就无线传感器网络调度算法展开了广泛研究，试图尽量减少通信时延，避免冲突，提高能源使用效率或公平性。Lu等人[4]研究了在每个传感器有占空比要求或平均只在1/K时隙内保持活跃状态的情况下，如何实现通信时延最小化[ 4]；文献[5]提出了一种可以降低数据聚集应用时延的启发式调度算法；Gandham等人提出了一种可以实现无冲突调度的分布式边缘着色算法[6]；Chipara等人[7]针对高数据率传感器网络应用，提出了一种称为动态无冲突查询调度(DCQS)的新的调度算法[2[8]；Rao等人提出了一种实用性很强的分布式算法[9]，计算出基于时隙的调度表后，可以为多跳无线网络提供端到端最大—最小公平性；Tan等人对时延约束条件下的分布式机会调度(DOS)算法展开研究，在两种不同类型的平均时延约束下实现吞吐量最大化[10]。

文献[2,11-14]对低占空比无线传感器网络的数据传输机制进行了研究。在文献[2]中，Guo等人对带有不可靠链路的低占空比无线传感网络机会泛洪技术进行了研究；文献[11]提出了一种新的无线传感器网络异步MAC协议(PA-MAC)。PA-MAC通过采用接收方发起数据传输机制、异步占空比机制以及节点唤醒时间估计机制，降低了节点的工作占空比，提高了网络的能量有效性。仿真结果表明，在保持网络性能的前提下，PA-MAC能够进一步降低节点工作的占空比，进而减少节点的能耗。文献[12]提出了一种动态数据发送协议DDF(dynamic data forwarding)，它将异步占空比和实际的链路模型结合在一起。在DDF中，每个节点先选出一个候选节点集合，然后再把数据包发给集合中先醒来的节点，从而可以降低端到端的时延，保证包成功发送率和提高网络寿命。Gu等人[13]提出一种部分节点提升占空比算法，同时就汇节点布置提出一种方案，可以为通信时延提供实时化保证。文献[14]提出了一种动态数据转发算法(DSF)，并在低占空比无线传感网络上进行了实验。本文工作不同于以上工作，不是为了避免冲突而对各条链路分开调度，而是综合考虑了多数据传输任务的负载均衡和时间调度问题。

2　网络模型和问题描述

2.1网络模型

本文中，传感器网络被看成是一个无向图G(V,E)，其中V表示传感器节点集合，E表示节点间无线链路集合。为了节约能量，节点工作于低占空比模式，节点V的工作周期V被划分为多个等时长的时隙。在每个工作周期中，节点V只在一个时隙内开启无线电设备，以接收数据，这一时隙为节点V的活跃时间，用Hv表示。在其余时隙内，节点V均处于休眠状态，直到自己发送数据为止。假设传感器节点已经同步[1]，有相同的工作周期T，且每个节点提前知道相邻节点的活跃时间。

为简便起见，时隙长度设为1，并且看成是最短时隙。一项任务需要明确从源节点发出数据传输请求，通过给定路径，将数据发至目的节点。考虑网络中有n个任务，每个任务TASKi(1≤i≤n)表示为，其中vsi和vdi分别表示源节点和目的节点，PATHi和NODEi分别表示从vsi至vdi数据传输路径的边和节点，Di是任务的时间约束。如果节点u生成数据或在时隙j接收数据，则任务数据可在时隙j从节点u单跳传输至节点v，其中i≤j≤i+P且P为单跳时间约束。

时间调度表S记载了传感器节点的数据接收时间。具体地，安排表中的S(i,j)表示节点vj∈NODEi{vsi}接收任务TASKi数据的时间，S(i,di)表示任务TASKi的时延。如果对∀vp→vq∈PATHi有S(i, p)≤S(i, q)≤S(i, p)+P且S(i, di)≤Di，则判定S可行。确定时间安排表S后，节点vi在时间j时的负载为vi在时间j时收到的所有数据，表示为w(i,j)。为简便起见，任务TASKi的时间安排表也可表示为vsi→vki(tk1)→…→vdi(tdi)，其中括号中的tj表示节点vj从数据传输路径上一节点处接收数据的时间。很显然，tdi=S(i,di)。图1展示了总线型拓扑结构低占空比传感器网络，网络任务是将节点v0的数据传输给v3。在时间1时生成数据，然后在时间2、2、4，数据发至v1, v2, v3。请注意，如果v0在时间3接收了其他数据，则这些数据无法在时间T内发至v3,原因是对v0→v1→v2→v3路径上的节点，在范围内没有合法的非降序时间序列。如图1所示。

图1　一个低占空比网络示例(其中T=5,P=2,D=4)

2.2问题描述

负载均衡(LB)问题可描述为：设无线传感器网络的工作周期为T，单跳时间约束为P，活跃时间Hv∀v∈V，有n个任务且1≤i≤n，现欲确定时间安排表S，以将每个时隙内的节点最大负载最小化。设x(i,j,k)为1—0整数变量，表示任务TASKi的数据是否在时间k被节点vj收到。

(1)

s.t.

(2)

x(i,j)=o,∀k≤D*,(k-1)|T+q≠Hvj

(3)

(4)

(5)

条件式(2)是保证每个任务的数据只来源于任务相关节点。条件式(3)用来约束各节点在睡眠状态时的接收数据能力。条件式(4)保证每个任务的数据在时间Di内能够沿着路径传输至目的地。条件式(5)用于约束每个任务的数据能够在P时延内通过逐个节点得以转发。w(j,k)表示节点vj在时间k的负载。

图2为负载均衡问题一个示例。(a)为网络拓扑结构及任务；(b)为T=5，P=D=8时的活跃和休眠节点；(c)最大负载W(S)=2时的最优调度方案，在时间3出现于节点v3，在时间5出现于节点v6。部分节点只有一次机会接收数据，比如说v1和v4，而其他节点有两个时隙可以接收数据，比如v3和v5。最大负载为2的最优调度表见图2(c)，该调度表可以表示为：

v1→v3(3)→v5(3)，v2→v3(8)→v5(8)

V0→v3(3)→v6(5)，v4(8)→v6(5)

图2　LB问题及最优调度方案

不同的调度安排会导致不同的最大负载。例如，如果任务TASK2的时间安排变为v2→v3(3)→v5(3)，则最大负载升为3。

3　基于树结构的多任务调度算法(SAT)

首先考虑如下负载均衡问题：所有任务的目的节点均为vs，路径构成一个根为vs的有向树(见图3(a)所示)。即：如果两条路径在节点v处交汇，则该两条路径以v为起点的其余部分完全相同。这种情况经常出现于传感器节点通过路由树采集数据等实际应用场景。本节中，出于简便，假设P=D*。

图3　计算任务树下的W(S)

引理1对任一最优时间调度S，vs在某个时刻的负载等于W(S)。

证明假设任意时刻vs的负载均小于W(S)，则必有节点Vj和时刻k满足w(j,k)=W(S)。既然vs是任务的唯一目的地，vj在k时接收到的数据最终将在p(p≤1)个时隙(t1,t2,…tp,ti

假设以上操作之后vj的负载是w′(j,k)，由于vs可能从vj以外节点接收数据，因此有w′(j,k)≤w(s,t1)。此外，w(s,t1)

最后，所有节点按拓扑次序执行相关操作。对节点u，只有它的所有子节点负载均衡之后，它自己才能负载均衡。由于拓扑结构是树结构，这一次序可以保证，u的负载无法通过操作被上层节点交替均衡。因此，这一过程完成后，除vs外的所有节点的最大负载均小于W(S)，这与先前假设矛盾，证毕。

在树结构下，于时间k推迟其他节点向节点vj发送数据，以保证更新过后的负载w′(j, k)不大于w(s,t1)，此时vs的负载保持不变。

引理1表明，如果能够找到一个可以实现vs最大负载最小化的可行性调度方案，那么这一调度方案总体来说也是最优的。本文设计了一种多项式时间算法SAT(树形布局调度算法)，该算法的主要过程是：首先，为vs计算一张任务表，记载每个任务在数据准备阶段有多少时间可用于时间调度；然后计算vs负载再分配最优方案，在负载最小化步骤中，实现vs最大负载最小化；最后，在调度生成步骤，获得针对所有节点的可行性调度方案。

算法的主要思路是使用贪婪策略，在每列之和阈值为k的条件下，确定一个可行的调度方案。如果将任务表转化为优先级队列Q，则算法在时间i(i=1 tom)时调度任务数量小于等于k。具体地，如果在最先时间i，Q中任务数量小于等于k个，则在i时调度所有任务，并从Q中提取出所有任务；否则，在i时只调度和提取前k个任务，且其余任务的最早时间变为i+1。如果该步骤结束时一些任务仍没有被调度，算法会返回“假”；否则返回“真”及一个节点vs可行性调度方案A，其中A(i,j)=1表示在vs的第j个活跃时间调度了第i个任务。具体步骤见算法1伪代码。

算法1SAT算法

输入：以优先级队列Q和阈值k(1≤k≤n)呈现的任务表。

输出：是否存在可行的调度计划A，使最大负载不大于k。

1：num=0；

/*还没调度的任务数量*/

2：while Q非空do

3：count=0;

4：i=top(Q).e;

5:while Q非空且top(Q).e==i do

6:if count

7:A(top(Q).r,i)=1;

/*在时间i调度任务*/

8：从Q中提取top(Q)；

9：count++；

10：else if i< top(Q). l then

11: top(Q).e= i+1;

/*更新Q*/

12：else

13:从Q中提取top(Q)；

/*没有调度的任务*/

14：num++；

15：if num==0 then

16:返回真；

17：else

18:返回假；

算法1最多可以调度n个任务，每次调度需要O(n)次Q提取和更新操作，每次操作耗时为O(logn)。因此，贪婪算法的时间复杂度为O(n2logn)。另外，该上界是紧上界。最坏情况下，对1≤i≤n，有TASKi.e=1且TASKi.e=m(m≥n)，同时k|n=0。算法在第i时间调度k个任务，需要n-(i-1)k次提取和更新操作，因此运行时间为：

(6)

引理2当且只当存在阈值为k的可行性调度方案时，贪婪算法才会返回“真”。

限于篇幅，引理2的证明在此略去。根据引理2，W(S)是让贪婪算法返回“真”的最小阈值k。因此，通过从范围1至n对k进行对分搜索，可以确定W(S)。负载最小化步骤需要O(nlogn)的时间来建立优先级队列，并在对分搜索每一步调用算法1，于是这一步的时间复杂度为O(n2logn)。

在调度方案生成步骤中，根据计算出来的节点vs的调度方案，这一步对其余节点的任务进行调度。考虑到对任务TASKi(1≤i≤n)，有∀vp→vq∈PATHi，结点vq接收数据的最早时间是te(i, q)=min{t | t ≤ te(i, p)且vq在时间 t处于活跃状态}。设在te(i,q)时间调度结点vq(vq≠vs)，以接收任务TASKi的数据，而vs在它第j个活跃时间(不小于时间te(i, s))接收TASKi的数据。通过这种方法，可以获得最优方案。

定理1设有n个任务，及有m个节点的导出树，SAT算法可在O(mn2log2n)时间内计算出最优调度方案。

证明根据引理1和2，SAT算法计算出的最优方案S，对1≤t≤D*，有W(S)=w (vs, t)。在上文讨论中，数据准备步骤和负载最小化步骤分别需要时间O(mn+nlogn)和O(n2log2n)。因为方案生成步骤需要为树中每个节点调用一次算法1，因此它的时间复杂度为O(mn2log2n)，是SAT算法运行时间的主要组成部分。证毕。

4　一般情况下的调度算法

在一般的负载均衡问题中，任务路径图不一定是树形结构。本节将证明，负载均衡问题是完全NP解题，然后给出一种近似算法及性能分析。

4.1负载均衡问题的难度

考虑一种额外约束条件下的特殊的负载均衡问题(LBS问题)：(1)T1= T2=…T|v|= T= 1；(2)P=0，表明必须同时对NODEi节点进行调度，以接收TASKi的数据；(3)D1=…=Dn=3，即每个任务调度的延时不得大于3。

设存在一个由12个节点图和6个任务构成的约束组件。节点表示为A至K，6个任务的路径为PATHA=A→G→I→L， PATHB=B→G→J，PATHC=C→G→kL， PATHD=D→H→K PATHE=E→H→I，PATHF=F→H→J→L。任务的调度时间分别表示为tA, tB, tC, tD, tE, tF。使用约束组件是为了强制规定，在W(S)=1方案中，为TASKC和TASKF分配的时间相等，如引理3所示。

引理3当且只当tA= tD，tB=tE，且tC= tF时，才存在W(S)=1的6个任务调度方案S。

证明如果方案S有W(S)=1，则：(1)由于NODEA∩NODEB∩NODEC={G}，因此tA≠tB≠tC；(2)因为NODEB∩NODEF={J}，因此tB≠tF；(3)因为NODEA∩NODEF={L}，因此tA≠tF。根据以上3个结论及tA,…,tF∈{1,2,3}，于是有tC=tF。此外，NODEA∩NODEE={I}，因此tA≠tE，进而tA=tD且tB≠tE。相反，如果tA=tD且tB=tE且tC=tF，设tA=tD=1，tB=tE=1，tC=tF=3，可以看出，一个节点在每个时隙期间最多从一个节点处接收数据，因此得出的方案S有W(S)=1。

定理2LBS问题是NP完全问题

证明假设包含n个任务的LBS问题及对应方案S，结论W(S)>1可用规模为n的多项式时间加以证明。因此，LBS∈NP。然后，构建多项式时间归约，将可着色图问题(G3C)归约为LBS问题，因为G3C是NP完全问题[15]，因此LBS问题也是NP完全问题。

4.2一种启发式算法

既然问题是NP完全问题，提出一种称为SAG(普遍适用的调度算法)的启发式算法。主要思路是：首先计算一个初始安排方案，此方案下每个任务中的节点都会尽快地把数据转发给下一个单跳相邻节点，然后延迟部分节点的任务时间，以降低当前最大负载。

如图2所示，SAG算法的输出是时间调度方案S，用每个任务TASKi和节点vj∈NODEi的I(i,j)表示，意思是节点vj在其第I(i,j)个活跃时间时接收到TASKi的数据。知道S(i,j)表示vj接收数据的时间，将I(i,j)转化为S(i,j)可表示为S(i,j)=time(I(i,j))。

首先，SAG算法计算节点vj接收TASKi数据的活跃时间的最小值I(i,j)。其次，节点vj在其第t个活跃时间的负载，设置为第t个活跃时间被调度的任务数量。然后，SAG算法继续寻找在k时间负载等于当前最大负载的节点vj，接着确定TASKi和延时δ，以便节点vj接收数据的时间可以被推迟至其第(I(i, j)+ δ)个活跃时间，进而降低w(i ,j)和W(S)的值。这里使用了两种操作：(1)任务TASKi在路径PATHi中节点vj和vj的后继节点的所有时间都被推迟了δ；(2)任务TASKi在路径PATHi中节点vj的先前节点的所有时间都被推迟了δ。

算法将检查：(1)是否time(I(i, di)+δ)≤Di，即Vdi的推迟时间不大于Di；(2)是否time(I(i,j)+ δ)- time(I(i,p))≤P，其中vp→vj∈PATHi。如果都是的话，且操作(1)有效，即经操作(1)改进过后的调度方案的最大负载得以降低，则SAG将执行操作(1)。此外，如果执行了操作(1)且操作(2)有效，则SAG算法执行操作(2)。

如果没有操作可以执行以降低W(S)，则SAG算法终止。因为检测部分任务能否推迟δ时间需要耗时O(|V|2D*n)，且一次操作至少可以使一个I(i, j)上升δ≥1(对各任务TASKi和vj∈V, 1≤I(i,j)≤D*))，所以SAG算法终止需要时间O(|V|3D*2n2)。

算法2SAG启发算法

输入：n个任务TASKi(1≤n)，导出图G(V, E)。

输出：vj∈V，每个任务TASKi的I(i, j)。

1： for所有vj∈V do

2:for 所有TASKido

3:I(i, j)节点vj接收数据的最早时间；

4：计算每个时间t的负载w(j,t)；

5： while end==false do

6:计算W(S)=max{w(j, k)} ∀vj∈V和 ∀k≤D*；

7：选择一个节点vj，使得对部分时间t有w(j, t)=W(S)；

8：使k=arg min{w(j, k)=W( S)}，end=true；

9：if ∃TASKi且δ≥0，有time(I(i,di+δ)≤Di，then

10:if time(I (i, j)+δ)-time(I(i,p))≤P，其中vp(vj∈PATHithen

11: if 对vp在路径PATHi中的所有后继节点vx有w(x, I( i, x)+ δ)

12: end=false;

13:for vp在路径PATHi中的所有后继节点vxdo

14:更新(i, x, δ)；

15：if vj在路径PATHi中的所有先前节点vx有w(x,I(i,x)+ δ)

16:for vj在路径PATHi中的所有先前节点vxdo

17:更新(i, x, δ)；

/*更新任务(i, x, δ)在节点vx处的调度方案*/

步骤:更新(i, x, δ):

1：w(x, I(i, x)+ δ)++；

2：w(x, I(i,x)+ δ)--；

3：I(i, x)+=δ；

5　仿真实验

为了评估本文算法的性能，利用TOSSIM[16]模拟器，在多种网络配置下，进行了全面的实验仿真。使用网络吞吐量作为主要指标，该指标计算方法为：

(7)

此外，实验还记录了任务延时，传感器节点存储溢出，及任意两个节点间的传输损失。为便于比较，实验也在转发任务数据时使用了“尽力”策略(BST)[2,3]。仿真结果既表明了开发高数据率多任务高效调度算法的迫切必要性，也证明了本文算法可以显著提升网络性能。

5.1实验配置

实验中，在100 m×100 m方形区域上随机布置30～100个传感器节点，采用默认发射功率。时隙长度设为2秒，每个节点的工作周期T设为20个时隙，于是得出一个占空比为5%的网络。开始时，每个节点在各自工作期间从[1,T]内选择一个时隙作为其活跃时间。

仿真主要考虑第4节讨论的任务导出树情景。由CTP等路由协议构建路由树，然后根据路由树确定任务路径。对于普通情况下的任务，通过探测消息在固定长度的图上随机游走来构建路径。考虑参数包括：(1)网络规模N;(2)任务时间约束D*;(3)数据率R，用每个任务的分组数据来衡量;(4)节点的缓冲区大小B。

5.2网络规模的影响

本实验中，网络节点数量设置为30、50、100，除汇点外的每个传感器任务由100个分组组成。每个任务的时间约束设置为100，缓冲区大小设置为100个分组。随着网络规模增大的实验结果显示于图4所示。在图4中，可以看到，SAT算法下的网络吞吐量远高于BST算法。

SAT算法下的任务平均时延大于BST算法(见图5)。但是两种算法的时延都小于时间约束D*=100。结果表明，SAT算法以增大时延为代价提升网络吞吐量。为进一步分析网络吞吐量下降的原因，实验统计了缓冲溢出和传输损失的时间。图6表明，随着网络规模增大，缓冲溢出和传输损失也会增大。图6的白色柱体代表传输损失，可以看出，当N=30和N=100时，BST算法下的溢出分组数量小于SAT，而BST算法的分组损失数量大于SAT，导致性能下降。当网络规模变大时，两种策略下的缓冲区平均使用率均会上升(见图7)，且差异很小。

图4　网络规模VS网络吞吐量　　图5　网络规模VS任务平均时延(D*=100)

图6　网络规模VS缓冲溢出和传输损失程度　　　　图7　网络规模VS缓存平均使用率(B=100)

5.3数据率的影响

改变每个任务的分组数量可以改变数据率。数据率上升时，拥塞和存储负载上升，进而网络吞吐量将会不可避免地下降。如图8所示，SAT算法的网络吞吐量几乎是BST的两倍。图9表明，SAT算法下的任务平均延时总是高于BST。当数据率从10上升到200时，分组丢失和缓冲溢出均会上升。BST的分组丢失要远高于SAT，而SAT的缓存溢出要略过于BST(见图10)。这些结果表明，当N=30时，SAT可以较低的缓存占用率，有效缓解时隙期间的传输拥塞(见图11)。

图8　数据率VS网络吞吐量　　　图9　数据率VS任务平均时延(D*=100)

图10　数据率VS缓冲溢出和传输损失程度　　　　图11　数据率VS缓存平均使用率(B=100)

5.4用户设置参数的影响

在实际应用中，用户可能需要为不同的任务提供不同大小的缓冲区，设置不同的时间约束。为了研究这两个用户参数的影响，实验考察了不同配置下的网络吞吐量。图12结果表明，SAT对时间延时约束更加敏感，而时间延时对BST算法下的网络吞吐量影响甚微。当可用缓存大小上升时，SAT下的网络吞吐量也会稍微上升，而BST会保持稳定，甚至当B=200时下降(见图13)。

图12　时延约束VS网络吞吐量(N=30)　　　　图13　缓冲大小VS网络吞吐量(N=30)

5.5SAG性能

最后，测试了本文SAG算法的性能。可以看出，网络规模变化时，SAG算法下的网络吞吐量上升了将近20%(见图14)。此外，当数据率变化时，SAG性能始终优于BST(见图15)。与图5结果相比，网络吞吐量下降得更慢。原因是因为与任务特性有关，也就是说，普遍情况下的任务数据流，比树形拓扑结构分布得更加均匀，因此传输拥塞和缓存溢出程度更低。

图14　普遍情况下的网络规模VS网络吞吐量　　　　图15　普遍情况下的数据率VS网络吞吐量

5.6不同方案的性能比较

图16　不同方案的平均延迟比较

为了更好地体现本文方案的优越性，将本文的SAG方案与DSF方案和DDF方案在平均延迟方面进行了比较。实验结果如图16所示。可以看到，随着网络规模的增大，三种方案的平均延迟都在降低，其中本文方案和DSF方案的平均延迟要明显低于DDF方案。仔细分析其原因可知，这主要是由于在DDF中，每个节点需要先选出一个候选节点集合，然后再把数据包发给集合中先醒来的节点。这会导致两个问题：1)候选节点集合的计算将耗费较多的系统资源开销，且容易受到节点分布的影响；2)当网络中节点总数增多时，如何从众多的集合元素中选择最先醒来的节点将变得更加困难。这些都会增加DDF方案的数据传输延迟。

仔细观察图16还可以发现，本文方案(SAG)的延迟要稍稍低于DSF方案。这是因为SAG方案能在时间约束条件下就给定的数据传输请求，确定最优调度方案，以实现负荷在传感器节点中的均匀分布，因此当有多个数据率要求高、时间紧的数据传输任务时，SAG方案的性能表现更优。

6　结　语

本文详细研究了低占空比传感器网络多任务调度问题。同时描述了负载均衡(LB)问题，证明该问题是完全NP问题，并给出相应算法，实现效率最大化。基于TOSSIM模拟器进行了全面仿真，证明了本文协议设计的有效性。TSP协议在大多数情况下的性能要优于“尽力”策略。本文算法主要应用场合，要求静态路由及任务数据率可预测。对本文工作进行拓展，研究可用于动态路由和数据率及拓扑结构变化(比如节点/链路损坏)情况下的自适应策略。此外，还将针对问题的普遍形式展开深入研究。

[1] 顾晶晶,陈松灿,庄毅.基于无线传感器网络拓扑结构的物联网定位模型[J].计算机学报,2010,33(9):1548-1555.

[2] Guo S,Gu Y,Jiang B,et al.Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links[C]//Milan: Proceedings of the 15th annual international conference on Mobile computing and networking.ACM,2009:133-144.

[3] Jurdak R,Baldi P,Lopes C V.Adaptive low power listening for wireless sensor networks[J].Mobile Computing,IEEE Transactions on,2007,6(8):988-1004.

[4] Lu G,Sadagopan N,Krishnamachari B,et al.Delay efficient sleep scheduling in wireless sensor networks[C]//Monaco:INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE.IEEE,2005,4:2470-2481.

[5] Pan Y,Lu X.Energy-efficient lifetime maximization and sleeping scheduling supporting data fusion and QoS in Multi-Sensornet[J].Signal Processing,2007,87(12):2949-2964.

[6] Gandham S,Dawande M,Prakash R.Link scheduling in sensor networks:Distributed edge coloring revisited[C]//New York: INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE.IEEE,2005,4:2492-2501.

[7] Chipara O,Lu C,Stankovic J.Dynamic conflict-free query scheduling for wireless sensor networks[C]//Luxemburg:Network Protocols,2006.ICNP’06.Proceedings of the 2006 14th IEEE International Conference on.IEEE,2006:321-331.

[8] Yu B,Li J,Li Y.Distributed data aggregation scheduling in wireless sensor networks[C]//New York:INFOCOM 2009,IEEE.IEEE,2009:2159-2167.

[9] Rao A,Stoica I.Adaptive distributed time-slot based scheduling for fairness in multi-hop wireless networks[C]//Holland Hague:Distributed Computing Systems,2008.ICDCS’08.The 28th International Conference on.IEEE,2008:874-882.

[10] Tan S S,Zheng D,Zhang J,et al.Distributed opportu-nistic scheduling for ad-hoc communications under delay constraints[M].Brussels:IEEE,2010.

[11] 唐震洲,施晓秋,金可仲.PA-MAC:一种被动的异步低占空比无线传感器网络MAC协议[J].传感技术学报,2011,24(3):423-428.

[12] 段秩,吴小兵,陈贵海.低占空比无线传感器网络中的动态数据传输协议[J].计算机研究与发展,2011,48(S2):145-151.

[13] Gu Y,He T,Lin M,et al.Spatiotemporal delay control for low-duty-cycle sensor networks[C]//Monaco:Real-Time Systems Symposium,2009,RTSS 2009.30th IEEE.IEEE,2009:127-137.

[14] Gu Y,He T.Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks[J].Mobile Computing,IEEE Transactions on,2011,10(12):1741-1754.

[15] Garey M R,Johnson D S.Computers and intractability[M].New York:freeman,1979.

[16] Levis P,Lee N,Welsh M,et al.TOSSIM:Accurate and scalable simulation of entire TinyOS applications[C]//Bern:Proceedings of the 1st international conference on Embedded networked sensor systems.ACM,2003:126-137.

A LOAD BALANCING-BASED MULTI-TASK SCHEDULING SCHEME IN WIRELESS SENSOR NETWORKS

Gao JianmingZhu Xiaohua

(ZhejiangYuexiuUniversityofForeignLanguages,Shaoxing312000,Zhejiang,China)

For energy conservation, a wireless sensor network is usually designed to work in a low-duty-cycle mode, in which a sensor node keeps active for a small percentage of time during its working period. In applications where there are multiple data delivery tasks with high data rates and time constraints, low-duty-cycle working mode may cause severe transmission congestion and data loss. In order to alleviate congestion and reduce data loss, the tasks need to be carefully scheduled to balance the workloads among sensor nodes in both spatial and temporal dimensions. We studied the load balancing-based multi-task scheduling problem, and proved it to be the NP-complete in general network topology structure. We also proposed and analysed two efficient scheduling algorithms to achieve load balance. Simulation results showed that the proposed algorithms greatly improved the network performance in most scenarios.

Wireless sensor networksLow-duty-cycleMulti-taskLoad balancingNP-complete problem

2014-12-17。全国教育信息技术研究课题(1262406 73)；浙江省教育厅项目(Y201122728)。高建明，讲师，主研领域：无线传感器网络，网络安全技术。朱小华，实验师。

TP391

A

10.3969/j.issn.1000-386x.2016.08.035