嚴芳芳，石 悅，魏 偉

（1.太原大學 太原030024；2.北京郵電大學 北京100876；3.國網電力科學研究院信息通信技術服務中心 北京100761）

1 引言

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

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

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

本文采用有向無環(huán)圖 （directed acyclic graph，DAG）對任務間的依賴關系進行描述，并針對無線傳感器網絡的特性對任務進行聚簇調度，提出了一種新的聚簇算法。

2 相關工作

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

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

3 基于相關性的任務調度算法

3.1 任務描述

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

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

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

設任務ti的最早開始時間 （earliest start time，EST）為EST（ti），最晚開始時間（latest start time，LST）為LST（ti），最晚完成時間（latest finished time，LFT）為LFT（ti），在處理器pj上的實際開始時間（actual start time，AST）為ASTpj（ti），則任務ti的完成時間（finished time，FT）為：

若ti為tj的前驅節(jié)點，即ti∈pred（tj）。ti的數據到達tj的時間（arrive time，AT）為：

3.2 基于任務相關性的聚簇調度算法

3.2.1 基本思想

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

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

（2）置任務優(yōu)先級隊列為空，取靜態(tài)關鍵路徑上的第一個節(jié)點作為當前節(jié)點ti。

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

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

（5）任務優(yōu)先級隊列中的第一個任務作為當前任務，為該任務選擇最早可用的處理器。

（6）計算當前任務在當前處理器上的EST，分配到當前最早可用的處理器上。

（7）如果當前任務為任務優(yōu)先級隊列中的最后一個任務，則結束；否則，取下一個任務作為當前任務，執(zhí)行步驟（5）。

針對圖1中的DAG任務描述，通過SCP算法得到的調度結果如圖2所示。圖中小方格表示一個處理器空閑的時間單位。通過圖2可知，調度的EST=27。通過任務復制的方式將該任務的描述轉化為如圖3所示的樹型（稱為簇樹）來描述任務之間的關系，可以發(fā)現任務間的并行關系，為了引出基于任務相關性的調度算法，引入調度簇、簇樹、調度簇的完成時間和聚簇的概念。

圖2 SCP算法的調度結果（EST=27）

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

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

圖3 由圖1中的調度樹合并得到的CT樹

定義3（調度簇的完成時間）對于一個調度簇Ci，若tm1，tm2，…，tmk∈Ci，則 該 簇 的 完 成 時 間（clustered finishing time,CFT）為CFTi=W（tm1）+W（tm2）+…+W（tmk）。

定義4（聚簇）將兩個調度簇合并的操作過程。

3.2.2 聚簇調度算法

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

·將DAG的調度結果合并為CT樹，搜索所有調度簇，采用適當策略選擇調度簇進行聚簇，從而減少處理器的數目和處理器間的通信能耗。

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

聚簇算法流程如下。

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

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

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

第4步 設tm1、tm2、…、tmn是Ci和Cr的公共任務，計算FTi-tmp=FTi+FTr-（W（tm1）+W（tm2）+…+W（tmn））。

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

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

4 實驗與分析

為驗證本文提出的聚簇算法——ICS（improoed clustering scheduling）算法性能，令其對圖3所示的調度簇進行聚簇處理，并將得到的結果與圖2的調度結果進行比較。聚簇過程見表1。

圖4 ICS算法的調度結果

得到的調度結果如圖4所示。

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

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

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

表1 ICS算法的聚簇過程

表2 SCP和ICS算法的實驗結果比較

5 結束語

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

參考文獻

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 李海濤.無線傳感器網絡中任務動態(tài)調度.電子科技大學碩士學位論文，2009