無線傳感網中一種負載均衡的多任務調度方案

高建明　朱小華

(浙江越秀外國語學院　浙江 紹興 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