基于任務(wù)相關(guān)性的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)任務(wù)調(diào)度算法

嚴(yán)芳芳，石 悅，魏 偉

（1.太原大學(xué) 太原030024；2.北京郵電大學(xué) 北京100876；3.國(guó)網(wǎng)電力科學(xué)研究院信息通信技術(shù)服務(wù)中心 北京100761）

1 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（wireless sensor network,WSN）是一種信息獲取及處理技術(shù)，有著廣泛的應(yīng)用和發(fā)展前景，在軍事、工業(yè)、商業(yè)等領(lǐng)域體現(xiàn)出許多優(yōu)越性。任務(wù)調(diào)度問(wèn)題是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的一個(gè)重要問(wèn)題，也是多代理（agent）系統(tǒng)中的熱點(diǎn)問(wèn)題之一。其原因是：第一，任務(wù)調(diào)度的結(jié)果會(huì)直接影響到網(wǎng)絡(luò)的生存周期；第二，任務(wù)調(diào)度機(jī)制的好壞直接關(guān)系到系統(tǒng)中的各節(jié)點(diǎn)能否最大限度地發(fā)揮自身的能力，避免占用更多的資源；第三，任務(wù)調(diào)度的結(jié)果會(huì)影響到任務(wù)的完成時(shí)間，進(jìn)而影響到整個(gè)網(wǎng)絡(luò)的性能。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)有著自組織性、動(dòng)態(tài)性等特點(diǎn)，同時(shí)又有著網(wǎng)絡(luò)通信資源受限、節(jié)點(diǎn)之間存在通信沖突的問(wèn)題，這就需要合理設(shè)計(jì)其任務(wù)調(diào)度算法，減小網(wǎng)絡(luò)節(jié)點(diǎn)的能耗，從而延長(zhǎng)節(jié)點(diǎn)的生命周期[1]。對(duì)任務(wù)進(jìn)行聚簇調(diào)度，有利于減少完成任務(wù)所需的節(jié)點(diǎn)數(shù)目，減少完成任務(wù)的時(shí)間，提高節(jié)點(diǎn)的利用率。

在整個(gè)網(wǎng)絡(luò)的任務(wù)組中，可能很多任務(wù)之間存在相互依賴(lài)的關(guān)系。如果將任務(wù)直接分配給普通節(jié)點(diǎn)，可能會(huì)造成有的任務(wù)等待時(shí)間過(guò)長(zhǎng)，占用系統(tǒng)資源過(guò)多，也影響到其他任務(wù)的完成。需要sink節(jié)點(diǎn)合理地對(duì)它們之間的執(zhí)行順序做一個(gè)規(guī)劃，確保任務(wù)按時(shí)高效完成。對(duì)任務(wù)間的相關(guān)性進(jìn)行分析并進(jìn)行聚簇、任務(wù)復(fù)制，目的在于降低節(jié)點(diǎn)間的通信能耗，同時(shí)減少完成整個(gè)任務(wù)組的時(shí)間。

本文采用有向無(wú)環(huán)圖 （directed acyclic graph，DAG）對(duì)任務(wù)間的依賴(lài)關(guān)系進(jìn)行描述，并針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的特性對(duì)任務(wù)進(jìn)行聚簇調(diào)度，提出了一種新的聚簇算法。

2 相關(guān)工作

[2]提出了一種應(yīng)用于多處理器和分布式系統(tǒng)的時(shí)間相關(guān)性的研究方案，使用非搶占調(diào)度策略捕獲了輸出時(shí)間流的時(shí)間相關(guān)性。但其著重于對(duì)相關(guān)性的捕獲分析，沒(méi)有從任務(wù)的角度考慮調(diào)度問(wèn)題。本文根據(jù)任務(wù)相關(guān)性，利用DAG對(duì)任務(wù)間的依賴(lài)關(guān)系做出描述，從而實(shí)現(xiàn)對(duì)任務(wù)的聚簇調(diào)度。參考文獻(xiàn)[3]基于圖論和貝葉斯方法提出了網(wǎng)格計(jì)算系統(tǒng)中的任務(wù)分解和資源分配的方案，得到了最優(yōu)的服務(wù)性能（即最小執(zhí)行時(shí)間）。但這種策略大大增加了節(jié)點(diǎn)的計(jì)算量，不適用于能量有限的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。本文通過(guò)對(duì)調(diào)度機(jī)制的改進(jìn)，分析任務(wù)間的相關(guān)性，而后進(jìn)行聚簇和復(fù)制，適當(dāng)降低了任務(wù)完成所需的節(jié)點(diǎn)數(shù)和任務(wù)時(shí)間，從而降低節(jié)點(diǎn)能耗，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。參考文獻(xiàn)[4]基于邏輯優(yōu)化和任務(wù)并行分配算法，提出了一種新的邏輯優(yōu)化調(diào)度分配的處理算法。但這也是偏重于邏輯上的調(diào)度，未考慮到實(shí)際應(yīng)用中的節(jié)點(diǎn)間通信等問(wèn)題。本文考慮到無(wú)限傳感器網(wǎng)絡(luò)的通信沖突和能耗問(wèn)題，在調(diào)度機(jī)制中引入根據(jù)任務(wù)相關(guān)性進(jìn)行的聚簇和任務(wù)復(fù)制的方式，以減小節(jié)點(diǎn)間的通信量，提高了節(jié)點(diǎn)的利用率，令調(diào)度算法適用于實(shí)際的動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境。

為此，本文提出了一種基于相關(guān)性的任務(wù)調(diào)度算法，以解決現(xiàn)有的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的靜態(tài)調(diào)度算法（靜態(tài)關(guān)鍵路徑（static critical path，SCP）算法）在調(diào)度具有相關(guān)性任務(wù)時(shí)的缺陷，盡量減少任務(wù)復(fù)制的次數(shù)以減小總的完成時(shí)間；同時(shí)，盡量減少完成任務(wù)的節(jié)點(diǎn)數(shù)目，也能有效降低節(jié)點(diǎn)間的通信能耗。

3 基于相關(guān)性的任務(wù)調(diào)度算法

3.1 任務(wù)描述

任務(wù)的相關(guān)性通常用一個(gè)有向無(wú)環(huán)圖表示，如圖1所示。DAG=（T，E，W）為一個(gè)三元組。其中，T是任務(wù)節(jié)點(diǎn)的集合，ti∈T，ti表示第i個(gè)任務(wù)；E是任務(wù)間通信開(kāi)銷(xiāo)的集合，eij∈E，eij表示ti和tj之間的通信的時(shí)間開(kāi)銷(xiāo)，如果兩個(gè)任務(wù)被交付給同一節(jié)點(diǎn)，那么eij=0；W是任務(wù)的完成時(shí)間的集合，W（ti）指任務(wù)ti的預(yù)計(jì)完成時(shí)間。

圖1 任務(wù)的有向無(wú)環(huán)圖表示

在任務(wù)的DAG中，根據(jù)任務(wù)間的依賴(lài)關(guān)系，有任務(wù)的前驅(qū)節(jié)點(diǎn)集合和后繼節(jié)點(diǎn)集合之分，令pred（ti）=｛j|eji∈E｝、post（ti）=｛j|eij∈E｝成立，則pred（ti）和post（ti）分別為ti的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)；若pred（ti）=覫，那么任務(wù)ti被稱(chēng)為入節(jié)點(diǎn)（in node）；若post（ti）=覫，那么任務(wù)ti被稱(chēng)為出節(jié)點(diǎn)（out node）。從入節(jié)點(diǎn)到出節(jié)點(diǎn)的最長(zhǎng)路徑（節(jié)點(diǎn)的計(jì)算成本和各個(gè)邊的通信成本之和）為這個(gè)圖的關(guān)鍵路徑。

設(shè)任務(wù)ti的最早開(kāi)始時(shí)間 （earliest start time，EST）為EST（ti），最晚開(kāi)始時(shí)間（latest start time，LST）為L(zhǎng)ST（ti），最晚完成時(shí)間（latest finished time，LFT）為L(zhǎng)FT（ti），在處理器pj上的實(shí)際開(kāi)始時(shí)間（actual start time，AST）為ASTpj（ti），則任務(wù)ti的完成時(shí)間（finished time，F(xiàn)T）為：

若ti為tj的前驅(qū)節(jié)點(diǎn)，即ti∈pred（tj）。ti的數(shù)據(jù)到達(dá)tj的時(shí)間（arrive time，AT）為：

3.2 基于任務(wù)相關(guān)性的聚簇調(diào)度算法

3.2.1 基本思想

針對(duì)DAG的調(diào)度問(wèn)題，SCP算法的主要思想是任一節(jié)點(diǎn)的執(zhí)行只有在全部?jī)?yōu)先它的節(jié)點(diǎn)完成后才能開(kāi)始。EST可以直接或間接地用于決定各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)，從而實(shí)現(xiàn)DAG的調(diào)度。因此，針對(duì)DAG調(diào)度，關(guān)鍵的問(wèn)題是如何精確地預(yù)估一些時(shí)間變量，如EST等。首先對(duì)SCP算法進(jìn)行研究，該算法步驟描述如下。

（1）對(duì)于坌ti，計(jì)算其EST（ti），并確定一條靜態(tài)關(guān)鍵路徑。

（2）置任務(wù)優(yōu)先級(jí)隊(duì)列為空，取靜態(tài)關(guān)鍵路徑上的第一個(gè)節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)ti。

（3）入度通常指有向圖中節(jié)點(diǎn)作為圖中邊的終點(diǎn)的次數(shù)之和。如果ti的入度為0，則將該節(jié)點(diǎn)作為任務(wù)優(yōu)先級(jí)隊(duì)中最后一個(gè)節(jié)點(diǎn)插入隊(duì)列，并把該節(jié)點(diǎn)的子節(jié)點(diǎn)的入度減1，轉(zhuǎn)步驟（4）；如果ti的入度不為0，則先對(duì)其所有的尚未進(jìn)入任務(wù)優(yōu)先級(jí)隊(duì)列的父節(jié)點(diǎn)tj按ESTj+tj+eij的大小由大到小排序。以第一個(gè)父節(jié)點(diǎn)及其尚未進(jìn)入任務(wù)優(yōu)先級(jí)隊(duì)列的祖先節(jié)點(diǎn)為子圖，構(gòu)成一個(gè)有向無(wú)環(huán)圖，遞歸地創(chuàng)建該子圖的任務(wù)優(yōu)先級(jí)隊(duì)列，并將該子圖的任務(wù)優(yōu)先級(jí)隊(duì)列添加到要?jiǎng)?chuàng)建的任務(wù)優(yōu)先級(jí)隊(duì)列的隊(duì)尾。用類(lèi)似的方法處理其余父節(jié)點(diǎn)構(gòu)成的子圖。最后再將節(jié)點(diǎn)ni加到任務(wù)優(yōu)先級(jí)隊(duì)列的隊(duì)尾，并把該節(jié)點(diǎn)的子節(jié)點(diǎn)的入度減1。

（4）如果當(dāng)前節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)，則任務(wù)優(yōu)先級(jí)隊(duì)列創(chuàng)建完成，否則取靜態(tài)關(guān)鍵路徑上的下一個(gè)節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，執(zhí)行步驟（3）。

（5）任務(wù)優(yōu)先級(jí)隊(duì)列中的第一個(gè)任務(wù)作為當(dāng)前任務(wù)，為該任務(wù)選擇最早可用的處理器。

（6）計(jì)算當(dāng)前任務(wù)在當(dāng)前處理器上的EST，分配到當(dāng)前最早可用的處理器上。

（7）如果當(dāng)前任務(wù)為任務(wù)優(yōu)先級(jí)隊(duì)列中的最后一個(gè)任務(wù)，則結(jié)束；否則，取下一個(gè)任務(wù)作為當(dāng)前任務(wù)，執(zhí)行步驟（5）。

針對(duì)圖1中的DAG任務(wù)描述，通過(guò)SCP算法得到的調(diào)度結(jié)果如圖2所示。圖中小方格表示一個(gè)處理器空閑的時(shí)間單位。通過(guò)圖2可知，調(diào)度的EST=27。通過(guò)任務(wù)復(fù)制的方式將該任務(wù)的描述轉(zhuǎn)化為如圖3所示的樹(shù)型（稱(chēng)為簇樹(shù)）來(lái)描述任務(wù)之間的關(guān)系，可以發(fā)現(xiàn)任務(wù)間的并行關(guān)系，為了引出基于任務(wù)相關(guān)性的調(diào)度算法，引入調(diào)度簇、簇樹(shù)、調(diào)度簇的完成時(shí)間和聚簇的概念。

圖2 SCP算法的調(diào)度結(jié)果（EST=27）

定義1（調(diào)度簇（scheduled cluster））調(diào)度完成后映射到同一處理器上的有序任務(wù)簇，記為Ci（i=1，2，…，m）。其中，包含開(kāi)始任務(wù)和結(jié)束任務(wù)、執(zhí)行時(shí)間等于調(diào)度長(zhǎng)度（SL）的調(diào)度簇為關(guān)鍵調(diào)度簇，記為Ckey。Ckey之外的所有其他調(diào)度簇為非關(guān)鍵調(diào)度簇，記為Ci。

定義2（簇樹(shù)（clustered tree））對(duì)于DAG經(jīng)調(diào)度后得到的一組簇Ci（i=1，2，…，m），以Ckey為基礎(chǔ)，將各Ci上的復(fù)制任務(wù)合并而生成的樹(shù)稱(chēng)為簇樹(shù)，簡(jiǎn)稱(chēng)為CT樹(shù)。例如對(duì)于圖2中的各調(diào)度簇，以Ckey為基礎(chǔ)，通過(guò)合并復(fù)制任務(wù)t1，可 得 圖3中 的CT樹(shù)，圖3中 的 調(diào) 度 簇Ckey={t1，t3，t6，t10，t9，t11}，C1={t1，t2，t7}，C2={t1，t4，t8}，C3={t1，t5}，可CT樹(shù)上可由根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的通路表示。節(jié)點(diǎn)間的通信開(kāi)銷(xiāo)在CT樹(shù)上用虛線(xiàn)箭頭標(biāo)出，分別為e2,6、e5,8、e7,10、e8,9。

圖3 由圖1中的調(diào)度樹(shù)合并得到的CT樹(shù)

定義3（調(diào)度簇的完成時(shí)間）對(duì)于一個(gè)調(diào)度簇Ci，若tm1，tm2，…，tmk∈Ci，則 該 簇 的 完 成 時(shí) 間（clustered finishing time,CFT）為CFTi=W（tm1）+W（tm2）+…+W（tmk）。

定義4（聚簇）將兩個(gè)調(diào)度簇合并的操作過(guò)程。

3.2.2 聚簇調(diào)度算法

ICS的主要思想基于以下原則。

·將DAG的調(diào)度結(jié)果合并為CT樹(shù)，搜索所有調(diào)度簇，采用適當(dāng)策略選擇調(diào)度簇進(jìn)行聚簇，從而減少處理器的數(shù)目和處理器間的通信能耗。

·使所有任務(wù)的完成時(shí)間達(dá)到最小，這包括任務(wù)的執(zhí)行時(shí)間和通信時(shí)間，即Ckey的任務(wù)執(zhí)行時(shí)間加上通信時(shí)間。

聚簇算法流程如下。

第1步 根據(jù)基于任務(wù)復(fù)制的調(diào)度算法對(duì)DAG的調(diào)度結(jié)果，獲取CT樹(shù)的信息（CT樹(shù)不需要實(shí)際生成）。此時(shí)CT樹(shù)上各調(diào)度簇與剩余通信為已知，所有節(jié)點(diǎn)的EST、LST、LFT值為已知。

第2步 將Ci按照CFTi從大到小的順序排序，即排序之后，CFTkey≥CFT1≥CFT2≥CFT3≥…≥CFTk。

第3步 對(duì)于第i個(gè)簇，設(shè)剩余時(shí)間（remaining time，RT）為RTi=CFTkey-CFTi，在Ci+1到Ck中使用二分查找法，找到一個(gè)r，使CFTr≤RTi且r是滿(mǎn)足條件的簇中的最大數(shù)。

第4步 設(shè)tm1、tm2、…、tmn是Ci和Cr的公共任務(wù)，計(jì)算FTi-tmp=FTi+FTr-（W（tm1）+W（tm2）+…+W（tmn））。

第5步 對(duì)Ci-tmp，計(jì)算其中每個(gè)任務(wù)的完成時(shí)間FT。對(duì)每個(gè)任務(wù)ti-j，若FT（ti-j）≤LST（post（ti-j）），則這次聚簇成功，否則聚簇失敗。若i=k，則循環(huán)結(jié)束。若聚簇成功，則將新的簇Ci-tmp代替原簇Ci，并將Cr去掉，返回第3步。若聚簇失敗，若r=k，則i++，返回第3步；若r＜k，則r++，返回第4步。

第6步 將聚簇后形成的新的調(diào)度簇分配給不同的任務(wù)節(jié)點(diǎn)處理。

4 實(shí)驗(yàn)與分析

為驗(yàn)證本文提出的聚簇算法——ICS（improoed clustering scheduling）算法性能，令其對(duì)圖3所示的調(diào)度簇進(jìn)行聚簇處理，并將得到的結(jié)果與圖2的調(diào)度結(jié)果進(jìn)行比較。聚簇過(guò)程見(jiàn)表1。

圖4 ICS算法的調(diào)度結(jié)果

得到的調(diào)度結(jié)果如圖4所示。

從圖4可以看出，使用ICS聚簇算法對(duì)圖3所示的調(diào)度簇進(jìn)行聚簇以后，原來(lái)的C1、C2、C3合并成為了一個(gè)簇，整個(gè)任務(wù)被分為兩個(gè)簇Ckey和C1，分配給兩個(gè)節(jié)點(diǎn)執(zhí)行。這一結(jié)果與圖2的調(diào)度結(jié)果相比，在任務(wù)完成總時(shí)間不變的情況下，調(diào)度簇的數(shù)量減少了一半，節(jié)點(diǎn)間通信的次數(shù)由4次變?yōu)?次；同時(shí)由于調(diào)度簇的合并，重復(fù)任務(wù)t1執(zhí)行的次數(shù)減少，從而使整個(gè)網(wǎng)絡(luò)的能耗得到的降低。

進(jìn)一步考慮普遍情況，隨機(jī)生成幾個(gè)任務(wù)組，分別運(yùn)用SCP算法和ICS算法進(jìn)行聚簇，得到的結(jié)果見(jiàn)表2（其中，節(jié)點(diǎn)平均利用率為實(shí)際處理時(shí)間與預(yù)留處理時(shí)間的比值）。

從表2可以看出，使用ICS算法進(jìn)行聚簇，所需的節(jié)點(diǎn)數(shù)目、預(yù)留的處理時(shí)間和實(shí)際的處理時(shí)間都大大減少，節(jié)點(diǎn)的平均利用率得到了提高，這在網(wǎng)絡(luò)中的任務(wù)組比較多的時(shí)候能體現(xiàn)出較大優(yōu)勢(shì)，其能夠增加整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)利用率，減少總的任務(wù)完成時(shí)間以及減少節(jié)點(diǎn)的排隊(duì)任務(wù)數(shù)。

表1 ICS算法的聚簇過(guò)程

表2 SCP和ICS算法的實(shí)驗(yàn)結(jié)果比較

5 結(jié)束語(yǔ)

本文針對(duì)現(xiàn)有的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的靜態(tài)調(diào)度算法（SCP算法）在調(diào)度具有相關(guān)性任務(wù)時(shí)的缺陷，提出了一種新的聚簇算法（ISC算法），該算法能夠使無(wú)線(xiàn)傳感器網(wǎng)絡(luò)在任務(wù)調(diào)度過(guò)程中的節(jié)點(diǎn)間通信能耗和節(jié)點(diǎn)處理能耗大大降低，同時(shí)減少了總的任務(wù)完成時(shí)間，提高了節(jié)點(diǎn)的平均利用率，使任務(wù)在能耗減少的情況下更有效率地執(zhí)行。但是，任務(wù)的過(guò)度集中不利于節(jié)點(diǎn)的負(fù)載均衡，有可能會(huì)出現(xiàn)某些節(jié)點(diǎn)生存時(shí)間較短的情況。在對(duì)任務(wù)調(diào)度的同時(shí)考慮對(duì)節(jié)點(diǎn)的調(diào)度，是今后有待進(jìn)一步研究的課題。

參考文獻(xiàn)

1 Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy efficient communication protocol for wireless micro-sensor networks.Proceedings of the 33rd Hawaii International Conference on System Sciences,Maui,Hawaii,USA,2000

2 Rox J,Ernst R.Exploiting inter-event stream correlations between output event streams of non-preemptively scheduled tasks.Proceedings of Design,Automation&Test in Europe Conference &Exhibition(DATE),Grenoble,France,2010:226～231

3 Yuan-Shun Dai,Levitin G.Optimal resource allocation for maximizing performance and reliability in tree-structured grid services.IEEE Transactions on Reliability,2007,56(3):444～453 4 Li C,Qiu J L,Gu X,et al.A task allocation algorithm for logic optimization parallel scheduling.Proceedings of 2012 Eighth International Conference on Natural Computation(ICNC),Chongqing,China,2012:1146～1150

5 AbdelSalam H S,Olariu S.Toward efficient task management in wireless sensor networks.IEEE Transactions on Computers,2011,60(11):1638～1651

6 Abdelhak S.Gurram C S,Tessier J,et al.ETSSI:energy-based task scheduling simulator for wireless sensor networks.Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS),Rio De Janeiro,Brazil,2011:2821～2824

7 Shekar V,Izadi B.Energy aware scheduling for DAG structured applications on heterogeneous and DVS enabled processors.Proceedings of 2010 International Green Computing Conference,Chicago,IL,USA,2010:495～502

8 Miranda S L C,Baker C J,Woodbridge K,et al.Comparison of scheduling algorithms for multifunction radar.IET Radar Sonar& Navigation,2007,1(6):414～424

9 李海濤.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中任務(wù)動(dòng)態(tài)調(diào)度.電子科技大學(xué)碩士學(xué)位論文，2009