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

高建明　朱小華

(浙江越秀外國語學院　浙江 紹興 312000)

?

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

高建明朱小華

(浙江越秀外國語學院浙江 紹興 312000)

為了節(jié)約能量，往往設計無線傳感器網(wǎng)絡工作于低占空比模式，在此模式下傳感器節(jié)點只在小部分工作期間保持活躍狀態(tài)。如果應用場合有多個數(shù)據(jù)率要求高、時間緊的數(shù)據(jù)傳輸任務，低占空比工作模式可能會導致嚴重的傳輸擁塞和數(shù)據(jù)損失。為了減輕數(shù)據(jù)擁塞和損失，需要對任務進行詳細的調度，以從時間和空間兩方面平衡傳感器節(jié)點工作負荷。對基于負載均衡的多任務調度問題進行研究，并證明該問題在一般網(wǎng)絡拓撲結構下是NP完全問題，提出并分析兩種高效的負載均衡調度算法。仿真結果表明，該算法極大地提高了絕大多數(shù)網(wǎng)絡場景下的網(wǎng)絡性能。

無線傳感器網(wǎng)絡低占空比多任務負載均衡NP完全問題

0　引　言

無線傳感器網(wǎng)絡(WSN)[1]在環(huán)境監(jiān)測、結構監(jiān)測、棲息地研究等跨時較長的領域具有巨大的應用潛力。為了解決傳感器節(jié)點供能有限和要求系統(tǒng)壽命較長這一矛盾，許多研究建議無線傳感器網(wǎng)絡工作于低占空比模式[2,3]。低占空比無線傳感器網(wǎng)絡大大地延長了網(wǎng)絡的壽命，但同時只有極短的時間供傳感器接收數(shù)據(jù)。于是，低占空比工作模式無法避免地產(chǎn)生了兩個問題：(1) 如果剛好在其極短的可用時間內，多個節(jié)點向同一節(jié)點發(fā)送數(shù)據(jù)，則會導致嚴重的傳輸擁塞問題，進而導致分組丟失，降低網(wǎng)絡性能。(2) 由于傳輸擁塞，單跳傳輸時延變長，導致節(jié)點可能無法獲得足夠的帶寬及時將收到的數(shù)據(jù)分組轉發(fā)出去。在高速數(shù)據(jù)應用情況下，數(shù)據(jù)分組很可能由于緩沖器溢出而丟失。

如果網(wǎng)絡中存在多個數(shù)據(jù)轉發(fā)任務，則這兩個問題可能會更加嚴重。如果傳輸調度設計不當，則網(wǎng)絡轉發(fā)能力在時間和空間層面將會無法得到有效利用。為了對具有時間約束的多數(shù)據(jù)轉發(fā)任務進行協(xié)調，需進行細致的任務調度，根據(jù)負荷調度表，實現(xiàn)傳感器的負荷平衡。然而，當前在低占空比無線傳感器網(wǎng)絡多任務調度性能提升方面研究不多。如何在時間約束條件下就給定的數(shù)據(jù)傳輸請求，確定最優(yōu)調度方案，以實現(xiàn)負荷在傳感器節(jié)點中的均勻分布，這一問題仍然沒有解決。因此，在本文中，對低占空比無線傳感網(wǎng)絡多任務調度問題展開深入研究，并提出高效算法，以對任務進行調度，實現(xiàn)傳感器均衡使用。

1　相關工作

人們已經(jīng)就無線傳感器網(wǎng)絡調度算法展開了廣泛研究，試圖盡量減少通信時延，避免沖突，提高能源使用效率或公平性。Lu等人[4]研究了在每個傳感器有占空比要求或平均只在1/K時隙內保持活躍狀態(tài)的情況下，如何實現(xiàn)通信時延最小化[ 4]；文獻[5]提出了一種可以降低數(shù)據(jù)聚集應用時延的啟發(fā)式調度算法；Gandham等人提出了一種可以實現(xiàn)無沖突調度的分布式邊緣著色算法[6]；Chipara等人[7]針對高數(shù)據(jù)率傳感器網(wǎng)絡應用，提出了一種稱為動態(tài)無沖突查詢調度(DCQS)的新的調度算法[2[8]；Rao等人提出了一種實用性很強的分布式算法[9]，計算出基于時隙的調度表后，可以為多跳無線網(wǎng)絡提供端到端最大—最小公平性；Tan等人對時延約束條件下的分布式機會調度(DOS)算法展開研究，在兩種不同類型的平均時延約束下實現(xiàn)吞吐量最大化[10]。

文獻[2,11-14]對低占空比無線傳感器網(wǎng)絡的數(shù)據(jù)傳輸機制進行了研究。在文獻[2]中，Guo等人對帶有不可靠鏈路的低占空比無線傳感網(wǎng)絡機會泛洪技術進行了研究；文獻[11]提出了一種新的無線傳感器網(wǎng)絡異步MAC協(xié)議(PA-MAC)。PA-MAC通過采用接收方發(fā)起數(shù)據(jù)傳輸機制、異步占空比機制以及節(jié)點喚醒時間估計機制，降低了節(jié)點的工作占空比，提高了網(wǎng)絡的能量有效性。仿真結果表明，在保持網(wǎng)絡性能的前提下，PA-MAC能夠進一步降低節(jié)點工作的占空比，進而減少節(jié)點的能耗。文獻[12]提出了一種動態(tài)數(shù)據(jù)發(fā)送協(xié)議DDF(dynamic data forwarding)，它將異步占空比和實際的鏈路模型結合在一起。在DDF中，每個節(jié)點先選出一個候選節(jié)點集合，然后再把數(shù)據(jù)包發(fā)給集合中先醒來的節(jié)點，從而可以降低端到端的時延，保證包成功發(fā)送率和提高網(wǎng)絡壽命。Gu等人[13]提出一種部分節(jié)點提升占空比算法，同時就匯節(jié)點布置提出一種方案，可以為通信時延提供實時化保證。文獻[14]提出了一種動態(tài)數(shù)據(jù)轉發(fā)算法(DSF)，并在低占空比無線傳感網(wǎng)絡上進行了實驗。本文工作不同于以上工作，不是為了避免沖突而對各條鏈路分開調度，而是綜合考慮了多數(shù)據(jù)傳輸任務的負載均衡和時間調度問題。

2　網(wǎng)絡模型和問題描述

2.1網(wǎng)絡模型

本文中，傳感器網(wǎng)絡被看成是一個無向圖G(V,E)，其中V表示傳感器節(jié)點集合，E表示節(jié)點間無線鏈路集合。為了節(jié)約能量，節(jié)點工作于低占空比模式，節(jié)點V的工作周期V被劃分為多個等時長的時隙。在每個工作周期中，節(jié)點V只在一個時隙內開啟無線電設備，以接收數(shù)據(jù)，這一時隙為節(jié)點V的活躍時間，用Hv表示。在其余時隙內，節(jié)點V均處于休眠狀態(tài)，直到自己發(fā)送數(shù)據(jù)為止。假設傳感器節(jié)點已經(jīng)同步[1]，有相同的工作周期T，且每個節(jié)點提前知道相鄰節(jié)點的活躍時間。

為簡便起見，時隙長度設為1，并且看成是最短時隙。一項任務需要明確從源節(jié)點發(fā)出數(shù)據(jù)傳輸請求，通過給定路徑，將數(shù)據(jù)發(fā)至目的節(jié)點?？紤]網(wǎng)絡中有n個任務，每個任務TASKi(1≤i≤n)表示為，其中vsi和vdi分別表示源節(jié)點和目的節(jié)點，PATHi和NODEi分別表示從vsi至vdi數(shù)據(jù)傳輸路徑的邊和節(jié)點，Di是任務的時間約束。如果節(jié)點u生成數(shù)據(jù)或在時隙j接收數(shù)據(jù)，則任務數(shù)據(jù)可在時隙j從節(jié)點u單跳傳輸至節(jié)點v，其中i≤j≤i+P且P為單跳時間約束。

時間調度表S記載了傳感器節(jié)點的數(shù)據(jù)接收時間。具體地，安排表中的S(i,j)表示節(jié)點vj∈NODEi{vsi}接收任務TASKi數(shù)據(jù)的時間，S(i,di)表示任務TASKi的時延。如果對?vp→vq∈PATHi有S(i, p)≤S(i, q)≤S(i, p)+P且S(i, di)≤Di，則判定S可行。確定時間安排表S后，節(jié)點vi在時間j時的負載為vi在時間j時收到的所有數(shù)據(jù)，表示為w(i,j)。為簡便起見，任務TASKi的時間安排表也可表示為vsi→vki(tk1)→…→vdi(tdi)，其中括號中的tj表示節(jié)點vj從數(shù)據(jù)傳輸路徑上一節(jié)點處接收數(shù)據(jù)的時間。很顯然，tdi=S(i,di)。圖1展示了總線型拓撲結構低占空比傳感器網(wǎng)絡，網(wǎng)絡任務是將節(jié)點v0的數(shù)據(jù)傳輸給v3。在時間1時生成數(shù)據(jù)，然后在時間2、2、4，數(shù)據(jù)發(fā)至v1, v2, v3。請注意，如果v0在時間3接收了其他數(shù)據(jù)，則這些數(shù)據(jù)無法在時間T內發(fā)至v3,原因是對v0→v1→v2→v3路徑上的節(jié)點，在范圍內沒有合法的非降序時間序列。如圖1所示。

圖1　一個低占空比網(wǎng)絡示例(其中T=5,P=2,D=4)

2.2問題描述

負載均衡(LB)問題可描述為：設無線傳感器網(wǎng)絡的工作周期為T，單跳時間約束為P，活躍時間Hv?v∈V，有n個任務且1≤i≤n，現(xiàn)欲確定時間安排表S，以將每個時隙內的節(jié)點最大負載最小化。設x(i,j,k)為1—0整數(shù)變量，表示任務TASKi的數(shù)據(jù)是否在時間k被節(jié)點vj收到。

(1)

s.t.

(2)

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

(3)

(4)

(5)

條件式(2)是保證每個任務的數(shù)據(jù)只來源于任務相關節(jié)點。條件式(3)用來約束各節(jié)點在睡眠狀態(tài)時的接收數(shù)據(jù)能力。條件式(4)保證每個任務的數(shù)據(jù)在時間Di內能夠沿著路徑傳輸至目的地。條件式(5)用于約束每個任務的數(shù)據(jù)能夠在P時延內通過逐個節(jié)點得以轉發(fā)。w(j,k)表示節(jié)點vj在時間k的負載。

圖2為負載均衡問題一個示例。(a)為網(wǎng)絡拓撲結構及任務；(b)為T=5，P=D=8時的活躍和休眠節(jié)點；(c)最大負載W(S)=2時的最優(yōu)調度方案，在時間3出現(xiàn)于節(jié)點v3，在時間5出現(xiàn)于節(jié)點v6。部分節(jié)點只有一次機會接收數(shù)據(jù)，比如說v1和v4，而其他節(jié)點有兩個時隙可以接收數(shù)據(jù)，比如v3和v5。最大負載為2的最優(yōu)調度表見圖2(c)，該調度表可以表示為：

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

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

圖2　LB問題及最優(yōu)調度方案

不同的調度安排會導致不同的最大負載。例如，如果任務TASK2的時間安排變?yōu)関2→v3(3)→v5(3)，則最大負載升為3。

3　基于樹結構的多任務調度算法(SAT)

首先考慮如下負載均衡問題：所有任務的目的節(jié)點均為vs，路徑構成一個根為vs的有向樹(見圖3(a)所示)。即：如果兩條路徑在節(jié)點v處交匯，則該兩條路徑以v為起點的其余部分完全相同。這種情況經(jīng)常出現(xiàn)于傳感器節(jié)點通過路由樹采集數(shù)據(jù)等實際應用場景。本節(jié)中，出于簡便，假設P=D*。

圖3　計算任務樹下的W(S)

引理1對任一最優(yōu)時間調度S，vs在某個時刻的負載等于W(S)。

證明假設任意時刻vs的負載均小于W(S)，則必有節(jié)點Vj和時刻k滿足w(j,k)=W(S)。既然vs是任務的唯一目的地，vj在k時接收到的數(shù)據(jù)最終將在p(p≤1)個時隙(t1,t2,…tp,ti

假設以上操作之后vj的負載是w′(j,k)，由于vs可能從vj以外節(jié)點接收數(shù)據(jù)，因此有w′(j,k)≤w(s,t1)。此外，w(s,t1)

最后，所有節(jié)點按拓撲次序執(zhí)行相關操作。對節(jié)點u，只有它的所有子節(jié)點負載均衡之后，它自己才能負載均衡。由于拓撲結構是樹結構，這一次序可以保證，u的負載無法通過操作被上層節(jié)點交替均衡。因此，這一過程完成后，除vs外的所有節(jié)點的最大負載均小于W(S)，這與先前假設矛盾，證畢。

在樹結構下，于時間k推遲其他節(jié)點向節(jié)點vj發(fā)送數(shù)據(jù)，以保證更新過后的負載w′(j, k)不大于w(s,t1)，此時vs的負載保持不變。

引理1表明，如果能夠找到一個可以實現(xiàn)vs最大負載最小化的可行性調度方案，那么這一調度方案總體來說也是最優(yōu)的。本文設計了一種多項式時間算法SAT(樹形布局調度算法)，該算法的主要過程是：首先，為vs計算一張任務表，記載每個任務在數(shù)據(jù)準備階段有多少時間可用于時間調度；然后計算vs負載再分配最優(yōu)方案，在負載最小化步驟中，實現(xiàn)vs最大負載最小化；最后，在調度生成步驟，獲得針對所有節(jié)點的可行性調度方案。

算法的主要思路是使用貪婪策略，在每列之和閾值為k的條件下，確定一個可行的調度方案。如果將任務表轉化為優(yōu)先級隊列Q，則算法在時間i(i=1 tom)時調度任務數(shù)量小于等于k。具體地，如果在最先時間i，Q中任務數(shù)量小于等于k個，則在i時調度所有任務，并從Q中提取出所有任務；否則，在i時只調度和提取前k個任務，且其余任務的最早時間變?yōu)閕+1。如果該步驟結束時一些任務仍沒有被調度，算法會返回“假”；否則返回“真”及一個節(jié)點vs可行性調度方案A，其中A(i,j)=1表示在vs的第j個活躍時間調度了第i個任務。具體步驟見算法1偽代碼。

算法1SAT算法

輸入：以優(yōu)先級隊列Q和閾值k(1≤k≤n)呈現(xiàn)的任務表。

輸出：是否存在可行的調度計劃A，使最大負載不大于k。

1：num=0；

/*還沒調度的任務數(shù)量*/

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的證明在此略去。根據(jù)引理2，W(S)是讓貪婪算法返回“真”的最小閾值k。因此，通過從范圍1至n對k進行對分搜索，可以確定W(S)。負載最小化步驟需要O(nlogn)的時間來建立優(yōu)先級隊列，并在對分搜索每一步調用算法1，于是這一步的時間復雜度為O(n2logn)。

在調度方案生成步驟中，根據(jù)計算出來的節(jié)點vs的調度方案，這一步對其余節(jié)點的任務進行調度?？紤]到對任務TASKi(1≤i≤n)，有?vp→vq∈PATHi，結點vq接收數(shù)據(jù)的最早時間是te(i, q)=min{t | t ≤ te(i, p)且vq在時間 t處于活躍狀態(tài)}。設在te(i,q)時間調度結點vq(vq≠vs)，以接收任務TASKi的數(shù)據(jù)，而vs在它第j個活躍時間(不小于時間te(i, s))接收TASKi的數(shù)據(jù)。通過這種方法，可以獲得最優(yōu)方案。

定理1設有n個任務，及有m個節(jié)點的導出樹，SAT算法可在O(mn2log2n)時間內計算出最優(yōu)調度方案。

證明根據(jù)引理1和2，SAT算法計算出的最優(yōu)方案S，對1≤t≤D*，有W(S)=w (vs, t)。在上文討論中，數(shù)據(jù)準備步驟和負載最小化步驟分別需要時間O(mn+nlogn)和O(n2log2n)。因為方案生成步驟需要為樹中每個節(jié)點調用一次算法1，因此它的時間復雜度為O(mn2log2n)，是SAT算法運行時間的主要組成部分。證畢。

4　一般情況下的調度算法

在一般的負載均衡問題中，任務路徑圖不一定是樹形結構。本節(jié)將證明，負載均衡問題是完全NP解題，然后給出一種近似算法及性能分析。

4.1負載均衡問題的難度

考慮一種額外約束條件下的特殊的負載均衡問題(LBS問題)：(1)T1= T2=…T|v|= T= 1；(2)P=0，表明必須同時對NODEi節(jié)點進行調度，以接收TASKi的數(shù)據(jù)；(3)D1=…=Dn=3，即每個任務調度的延時不得大于3。

設存在一個由12個節(jié)點圖和6個任務構成的約束組件。節(jié)點表示為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。使用約束組件是為了強制規(guī)定，在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。根據(jù)以上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，可以看出，一個節(jié)點在每個時隙期間最多從一個節(jié)點處接收數(shù)據(jù)，因此得出的方案S有W(S)=1。

定理2LBS問題是NP完全問題

證明假設包含n個任務的LBS問題及對應方案S，結論W(S)>1可用規(guī)模為n的多項式時間加以證明。因此，LBS∈NP。然后，構建多項式時間歸約，將可著色圖問題(G3C)歸約為LBS問題，因為G3C是NP完全問題[15]，因此LBS問題也是NP完全問題。

4.2一種啟發(fā)式算法

既然問題是NP完全問題，提出一種稱為SAG(普遍適用的調度算法)的啟發(fā)式算法。主要思路是：首先計算一個初始安排方案，此方案下每個任務中的節(jié)點都會盡快地把數(shù)據(jù)轉發(fā)給下一個單跳相鄰節(jié)點，然后延遲部分節(jié)點的任務時間，以降低當前最大負載。

如圖2所示，SAG算法的輸出是時間調度方案S，用每個任務TASKi和節(jié)點vj∈NODEi的I(i,j)表示，意思是節(jié)點vj在其第I(i,j)個活躍時間時接收到TASKi的數(shù)據(jù)。知道S(i,j)表示vj接收數(shù)據(jù)的時間，將I(i,j)轉化為S(i,j)可表示為S(i,j)=time(I(i,j))。

首先，SAG算法計算節(jié)點vj接收TASKi數(shù)據(jù)的活躍時間的最小值I(i,j)。其次，節(jié)點vj在其第t個活躍時間的負載，設置為第t個活躍時間被調度的任務數(shù)量。然后，SAG算法繼續(xù)尋找在k時間負載等于當前最大負載的節(jié)點vj，接著確定TASKi和延時δ，以便節(jié)點vj接收數(shù)據(jù)的時間可以被推遲至其第(I(i, j)+ δ)個活躍時間，進而降低w(i ,j)和W(S)的值。這里使用了兩種操作：(1)任務TASKi在路徑PATHi中節(jié)點vj和vj的后繼節(jié)點的所有時間都被推遲了δ；(2)任務TASKi在路徑PATHi中節(jié)點vj的先前節(jié)點的所有時間都被推遲了δ。

算法將檢查：(1)是否time(I(i, di)+δ)≤Di，即Vdi的推遲時間不大于Di；(2)是否time(I(i,j)+ δ)- time(I(i,p))≤P，其中vp→vj∈PATHi。如果都是的話，且操作(1)有效，即經(jīng)操作(1)改進過后的調度方案的最大負載得以降低，則SAG將執(zhí)行操作(1)。此外，如果執(zhí)行了操作(1)且操作(2)有效，則SAG算法執(zhí)行操作(2)。

如果沒有操作可以執(zhí)行以降低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啟發(fā)算法

輸入：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)節(jié)點vj接收數(shù)據(jù)的最早時間；

4：計算每個時間t的負載w(j,t)；

5： while end==false do

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

7：選擇一個節(jié)點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中的所有后繼節(jié)點vx有w(x, I( i, x)+ δ)

12: end=false;

13:for vp在路徑PATHi中的所有后繼節(jié)點vxdo

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

15：if vj在路徑PATHi中的所有先前節(jié)點vx有w(x,I(i,x)+ δ)

16:for vj在路徑PATHi中的所有先前節(jié)點vxdo

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

/*更新任務(i, x, δ)在節(jié)點vx處的調度方案*/

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

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

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

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

5　仿真實驗

為了評估本文算法的性能，利用TOSSIM[16]模擬器，在多種網(wǎng)絡配置下，進行了全面的實驗仿真。使用網(wǎng)絡吞吐量作為主要指標，該指標計算方法為：

(7)

此外，實驗還記錄了任務延時，傳感器節(jié)點存儲溢出，及任意兩個節(jié)點間的傳輸損失。為便于比較，實驗也在轉發(fā)任務數(shù)據(jù)時使用了“盡力”策略(BST)[2,3]。仿真結果既表明了開發(fā)高數(shù)據(jù)率多任務高效調度算法的迫切必要性，也證明了本文算法可以顯著提升網(wǎng)絡性能。

5.1實驗配置

實驗中，在100 m×100 m方形區(qū)域上隨機布置30～100個傳感器節(jié)點，采用默認發(fā)射功率。時隙長度設為2秒，每個節(jié)點的工作周期T設為20個時隙，于是得出一個占空比為5%的網(wǎng)絡。開始時，每個節(jié)點在各自工作期間從[1,T]內選擇一個時隙作為其活躍時間。

仿真主要考慮第4節(jié)討論的任務導出樹情景。由CTP等路由協(xié)議構建路由樹，然后根據(jù)路由樹確定任務路徑。對于普通情況下的任務，通過探測消息在固定長度的圖上隨機游走來構建路徑?？紤]參數(shù)包括：(1)網(wǎng)絡規(guī)模N;(2)任務時間約束D*;(3)數(shù)據(jù)率R，用每個任務的分組數(shù)據(jù)來衡量;(4)節(jié)點的緩沖區(qū)大小B。

5.2網(wǎng)絡規(guī)模的影響

本實驗中，網(wǎng)絡節(jié)點數(shù)量設置為30、50、100，除匯點外的每個傳感器任務由100個分組組成。每個任務的時間約束設置為100，緩沖區(qū)大小設置為100個分組。隨著網(wǎng)絡規(guī)模增大的實驗結果顯示于圖4所示。在圖4中，可以看到，SAT算法下的網(wǎng)絡吞吐量遠高于BST算法。

SAT算法下的任務平均時延大于BST算法(見圖5)。但是兩種算法的時延都小于時間約束D*=100。結果表明，SAT算法以增大時延為代價提升網(wǎng)絡吞吐量。為進一步分析網(wǎng)絡吞吐量下降的原因，實驗統(tǒng)計了緩沖溢出和傳輸損失的時間。圖6表明，隨著網(wǎng)絡規(guī)模增大，緩沖溢出和傳輸損失也會增大。圖6的白色柱體代表傳輸損失，可以看出，當N=30和N=100時，BST算法下的溢出分組數(shù)量小于SAT，而BST算法的分組損失數(shù)量大于SAT，導致性能下降。當網(wǎng)絡規(guī)模變大時，兩種策略下的緩沖區(qū)平均使用率均會上升(見圖7)，且差異很小。

圖4　網(wǎng)絡規(guī)模VS網(wǎng)絡吞吐量　　圖5　網(wǎng)絡規(guī)模VS任務平均時延(D*=100)

圖6　網(wǎng)絡規(guī)模VS緩沖溢出和傳輸損失程度　　　　圖7　網(wǎng)絡規(guī)模VS緩存平均使用率(B=100)

5.3數(shù)據(jù)率的影響

改變每個任務的分組數(shù)量可以改變數(shù)據(jù)率。數(shù)據(jù)率上升時，擁塞和存儲負載上升，進而網(wǎng)絡吞吐量將會不可避免地下降。如圖8所示，SAT算法的網(wǎng)絡吞吐量幾乎是BST的兩倍。圖9表明，SAT算法下的任務平均延時總是高于BST。當數(shù)據(jù)率從10上升到200時，分組丟失和緩沖溢出均會上升。BST的分組丟失要遠高于SAT，而SAT的緩存溢出要略過于BST(見圖10)。這些結果表明，當N=30時，SAT可以較低的緩存占用率，有效緩解時隙期間的傳輸擁塞(見圖11)。

圖8　數(shù)據(jù)率VS網(wǎng)絡吞吐量　　　圖9　數(shù)據(jù)率VS任務平均時延(D*=100)

圖10　數(shù)據(jù)率VS緩沖溢出和傳輸損失程度　　　　圖11　數(shù)據(jù)率VS緩存平均使用率(B=100)

5.4用戶設置參數(shù)的影響

在實際應用中，用戶可能需要為不同的任務提供不同大小的緩沖區(qū)，設置不同的時間約束。為了研究這兩個用戶參數(shù)的影響，實驗考察了不同配置下的網(wǎng)絡吞吐量。圖12結果表明，SAT對時間延時約束更加敏感，而時間延時對BST算法下的網(wǎng)絡吞吐量影響甚微。當可用緩存大小上升時，SAT下的網(wǎng)絡吞吐量也會稍微上升，而BST會保持穩(wěn)定，甚至當B=200時下降(見圖13)。

圖12　時延約束VS網(wǎng)絡吞吐量(N=30)　　　　圖13　緩沖大小VS網(wǎng)絡吞吐量(N=30)

5.5SAG性能

最后，測試了本文SAG算法的性能?？梢钥闯?，網(wǎng)絡規(guī)模變化時，SAG算法下的網(wǎng)絡吞吐量上升了將近20%(見圖14)。此外，當數(shù)據(jù)率變化時，SAG性能始終優(yōu)于BST(見圖15)。與圖5結果相比，網(wǎng)絡吞吐量下降得更慢。原因是因為與任務特性有關，也就是說，普遍情況下的任務數(shù)據(jù)流，比樹形拓撲結構分布得更加均勻，因此傳輸擁塞和緩存溢出程度更低。

圖14　普遍情況下的網(wǎng)絡規(guī)模VS網(wǎng)絡吞吐量　　　　圖15　普遍情況下的數(shù)據(jù)率VS網(wǎng)絡吞吐量

5.6不同方案的性能比較

圖16　不同方案的平均延遲比較

為了更好地體現(xiàn)本文方案的優(yōu)越性，將本文的SAG方案與DSF方案和DDF方案在平均延遲方面進行了比較。實驗結果如圖16所示?？梢钥吹?，隨著網(wǎng)絡規(guī)模的增大，三種方案的平均延遲都在降低，其中本文方案和DSF方案的平均延遲要明顯低于DDF方案。仔細分析其原因可知，這主要是由于在DDF中，每個節(jié)點需要先選出一個候選節(jié)點集合，然后再把數(shù)據(jù)包發(fā)給集合中先醒來的節(jié)點。這會導致兩個問題：1)候選節(jié)點集合的計算將耗費較多的系統(tǒng)資源開銷，且容易受到節(jié)點分布的影響；2)當網(wǎng)絡中節(jié)點總數(shù)增多時，如何從眾多的集合元素中選擇最先醒來的節(jié)點將變得更加困難。這些都會增加DDF方案的數(shù)據(jù)傳輸延遲。

仔細觀察圖16還可以發(fā)現(xiàn)，本文方案(SAG)的延遲要稍稍低于DSF方案。這是因為SAG方案能在時間約束條件下就給定的數(shù)據(jù)傳輸請求，確定最優(yōu)調度方案，以實現(xiàn)負荷在傳感器節(jié)點中的均勻分布，因此當有多個數(shù)據(jù)率要求高、時間緊的數(shù)據(jù)傳輸任務時，SAG方案的性能表現(xiàn)更優(yōu)。

6　結　語

本文詳細研究了低占空比傳感器網(wǎng)絡多任務調度問題。同時描述了負載均衡(LB)問題，證明該問題是完全NP問題，并給出相應算法，實現(xiàn)效率最大化。基于TOSSIM模擬器進行了全面仿真，證明了本文協(xié)議設計的有效性。TSP協(xié)議在大多數(shù)情況下的性能要優(yōu)于“盡力”策略。本文算法主要應用場合，要求靜態(tài)路由及任務數(shù)據(jù)率可預測。對本文工作進行拓展，研究可用于動態(tài)路由和數(shù)據(jù)率及拓撲結構變化(比如節(jié)點/鏈路損壞)情況下的自適應策略。此外，還將針對問題的普遍形式展開深入研究。

[1] 顧晶晶,陳松燦,莊毅.基于無線傳感器網(wǎng)絡拓撲結構的物聯(lián)網(wǎng)定位模型[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:一種被動的異步低占空比無線傳感器網(wǎng)絡MAC協(xié)議[J].傳感技術學報,2011,24(3):423-428.

[12] 段秩,吳小兵,陳貴海.低占空比無線傳感器網(wǎng)絡中的動態(tài)數(shù)據(jù)傳輸協(xié)議[J].計算機研究與發(fā)展,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)。高建明，講師，主研領域：無線傳感器網(wǎng)絡，網(wǎng)絡安全技術。朱小華，實驗師。

TP391

A

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