高建明　朱小華

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

?

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

高建明朱小華

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

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

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

0　引　言

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

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

1　相關(guān)工作

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

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

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

2.1網(wǎng)絡(luò)模型

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

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

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

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

2.2問題描述

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

(1)

s.t.

(2)

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

(3)

(4)

(5)

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

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

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

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

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

不同的調(diào)度安排會(huì)導(dǎo)致不同的最大負(fù)載。例如，如果任務(wù)TASK2的時(shí)間安排變?yōu)関2→v3(3)→v5(3)，則最大負(fù)載升為3。

3　基于樹結(jié)構(gòu)的多任務(wù)調(diào)度算法(SAT)

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

圖3　計(jì)算任務(wù)樹下的W(S)

引理1對(duì)任一最優(yōu)時(shí)間調(diào)度S，vs在某個(gè)時(shí)刻的負(fù)載等于W(S)。

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

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

最后，所有節(jié)點(diǎn)按拓?fù)浯涡驁?zhí)行相關(guān)操作。對(duì)節(jié)點(diǎn)u，只有它的所有子節(jié)點(diǎn)負(fù)載均衡之后，它自己才能負(fù)載均衡。由于拓?fù)浣Y(jié)構(gòu)是樹結(jié)構(gòu)，這一次序可以保證，u的負(fù)載無法通過操作被上層節(jié)點(diǎn)交替均衡。因此，這一過程完成后，除vs外的所有節(jié)點(diǎn)的最大負(fù)載均小于W(S)，這與先前假設(shè)矛盾，證畢。

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

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

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

算法1SAT算法

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

輸出：是否存在可行的調(diào)度計(jì)劃A，使最大負(fù)載不大于k。

1：num=0；

/*還沒調(diào)度的任務(wù)數(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;

/*在時(shí)間i調(diào)度任務(wù)*/

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)；

/*沒有調(diào)度的任務(wù)*/

14：num++；

15：if num==0 then

16:返回真；

17：else

18:返回假；

算法1最多可以調(diào)度n個(gè)任務(wù)，每次調(diào)度需要O(n)次Q提取和更新操作，每次操作耗時(shí)為O(logn)。因此，貪婪算法的時(shí)間復(fù)雜度為O(n2logn)。另外，該上界是緊上界。最壞情況下，對(duì)1≤i≤n，有TASKi.e=1且TASKi.e=m(m≥n)，同時(shí)k|n=0。算法在第i時(shí)間調(diào)度k個(gè)任務(wù)，需要n-(i-1)k次提取和更新操作，因此運(yùn)行時(shí)間為：

(6)

引理2當(dāng)且只當(dāng)存在閾值為k的可行性調(diào)度方案時(shí)，貪婪算法才會(huì)返回“真”。

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

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

定理1設(shè)有n個(gè)任務(wù)，及有m個(gè)節(jié)點(diǎn)的導(dǎo)出樹，SAT算法可在O(mn2log2n)時(shí)間內(nèi)計(jì)算出最優(yōu)調(diào)度方案。

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

4　一般情況下的調(diào)度算法

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

4.1負(fù)載均衡問題的難度

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

設(shè)存在一個(gè)由12個(gè)節(jié)點(diǎn)圖和6個(gè)任務(wù)構(gòu)成的約束組件。節(jié)點(diǎn)表示為A至K，6個(gè)任務(wù)的路徑為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。任務(wù)的調(diào)度時(shí)間分別表示為tA, tB, tC, tD, tE, tF。使用約束組件是為了強(qiáng)制規(guī)定，在W(S)=1方案中，為TASKC和TASKF分配的時(shí)間相等，如引理3所示。

引理3當(dāng)且只當(dāng)tA= tD，tB=tE，且tC= tF時(shí)，才存在W(S)=1的6個(gè)任務(wù)調(diào)度方案S。

證明如果方案S有W(S)=1，則：(1)由于NODEA∩NODEB∩NODEC={G}，因此tA≠tB≠tC；(2)因?yàn)镹ODEB∩NODEF={J}，因此tB≠tF；(3)因?yàn)镹ODEA∩NODEF={L}，因此tA≠tF。根據(jù)以上3個(gè)結(jié)論及tA,…,tF∈{1,2,3}，于是有tC=tF。此外，NODEA∩NODEE={I}，因此tA≠tE，進(jìn)而tA=tD且tB≠tE。相反，如果tA=tD且tB=tE且tC=tF，設(shè)tA=tD=1，tB=tE=1，tC=tF=3，可以看出，一個(gè)節(jié)點(diǎn)在每個(gè)時(shí)隙期間最多從一個(gè)節(jié)點(diǎn)處接收數(shù)據(jù)，因此得出的方案S有W(S)=1。

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

證明假設(shè)包含n個(gè)任務(wù)的LBS問題及對(duì)應(yīng)方案S，結(jié)論W(S)>1可用規(guī)模為n的多項(xiàng)式時(shí)間加以證明。因此，LBS∈NP。然后，構(gòu)建多項(xiàng)式時(shí)間歸約，將可著色圖問題(G3C)歸約為LBS問題，因?yàn)镚3C是NP完全問題[15]，因此LBS問題也是NP完全問題。

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

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

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

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

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

如果沒有操作可以執(zhí)行以降低W(S)，則SAG算法終止。因?yàn)闄z測(cè)部分任務(wù)能否推遲δ時(shí)間需要耗時(shí)O(|V|2D*n)，且一次操作至少可以使一個(gè)I(i, j)上升δ≥1(對(duì)各任務(wù)TASKi和vj∈V, 1≤I(i,j)≤D*))，所以SAG算法終止需要時(shí)間O(|V|3D*2n2)。

算法2SAG啟發(fā)算法

輸入：n個(gè)任務(wù)TASKi(1≤n)，導(dǎo)出圖G(V, E)。

輸出：vj∈V，每個(gè)任務(wù)TASKi的I(i, j)。

1： for所有vj∈V do

2:for 所有TASKido

3:I(i, j)節(jié)點(diǎn)vj接收數(shù)據(jù)的最早時(shí)間；

4：計(jì)算每個(gè)時(shí)間t的負(fù)載w(j,t)；

5： while end==false do

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

7：選擇一個(gè)節(jié)點(diǎn)vj，使得對(duì)部分時(shí)間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 對(duì)vp在路徑PATHi中的所有后繼節(jié)點(diǎn)vx有w(x, I( i, x)+ δ)

12: end=false;

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

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

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

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

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

/*更新任務(wù)(i, x, δ)在節(jié)點(diǎn)vx處的調(diào)度方案*/

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

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

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

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

5　仿真實(shí)驗(yàn)

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

(7)

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

5.1實(shí)驗(yàn)配置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.5SAG性能

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

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

5.6不同方案的性能比較

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

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

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

6　結(jié)　語

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

[1] 顧晶晶,陳松燦,莊毅.基于無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的物聯(lián)網(wǎng)定位模型[J].計(jì)算機(jī)學(xué)報(bào),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:一種被動(dòng)的異步低占空比無線傳感器網(wǎng)絡(luò)MAC協(xié)議[J].傳感技術(shù)學(xué)報(bào),2011,24(3):423-428.

[12] 段秩,吳小兵,陳貴海.低占空比無線傳感器網(wǎng)絡(luò)中的動(dòng)態(tài)數(shù)據(jù)傳輸協(xié)議[J].計(jì)算機(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。全國教育信息技術(shù)研究課題(1262406 73)；浙江省教育廳項(xiàng)目(Y201122728)。高建明，講師，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)安全技術(shù)。朱小華，實(shí)驗(yàn)師。

TP391

A

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