郭文忠，蘇金樹，陳澄宇，陳國龍

(1. 國防科學技術(shù)大學 計算機學院，湖南 長沙 410073；2. 福州大學 數(shù)學與計算機科學學院，福建 福州 350108)

1 引言

無線傳感器網(wǎng)絡（WSN, wireless sensor network）作為一種新型的計算模式，它通過在目標區(qū)域中部署大量微型無線傳感器，以自主組網(wǎng)方式實現(xiàn)大范圍內(nèi)的信息自動采集與處理，具有低成本、高可靠、長周期和抗損毀等優(yōu)點，有著廣闊的應用空間[1]。

由于無線傳感器網(wǎng)絡中單個節(jié)點的能量以及計算和存儲能力有限，往往不能獨立完成面臨的計算任務，需要多個傳感器節(jié)點采用一定的算法通過交換信息協(xié)作完成指定任務。例如，在對象跟蹤應用中，為了估計目標的位置，需要進行信號檢測、因式分解以及快速傅里葉變換等復雜的數(shù)據(jù)處理，但是單個節(jié)點的計算能力和能量不足以完成這些計算密集型的任務，需要多個節(jié)點協(xié)同計算移動目標的位置或?qū)Χ鄠€目標進行分類。又如，在視頻傳感器應用中，多媒體信息處理通常也都是計算密集型的任務，單個節(jié)點的能量以及計算和存儲能力無法完成，同樣需要多個節(jié)點聯(lián)合處理完成任務[2]。

動態(tài)聯(lián)盟是為了完成特定任務而建立的盟主組織，聯(lián)盟內(nèi)的盟主實行資源共享和任務分擔，相互合作以期用最佳方式完成任務，使聯(lián)盟的整體資源得到充分利用，并能保證無線傳感器網(wǎng)絡任務調(diào)度中各個基本任務的服務質(zhì)量要求。為了適應無線傳感器網(wǎng)絡拓撲的動態(tài)變化、網(wǎng)絡和節(jié)點資源的局限性以及脆弱的網(wǎng)絡環(huán)境3個關鍵特點，本文基于動態(tài)聯(lián)盟思想，很好地將無線傳感器網(wǎng)絡中任務調(diào)度的聯(lián)盟并行生成機制和自適應調(diào)整機制結(jié)合，構(gòu)建了一個基于聯(lián)盟機制的高度靈活任務調(diào)度策略。

2 相關工作

目前，雖然傳統(tǒng)網(wǎng)絡環(huán)境下的任務調(diào)度取得了令人滿意的成果，但都是假設處理器之間不存在通信沖突，并且?guī)缀醪淮嬖谀茉聪拗茊栴}。然而，無線傳感器網(wǎng)絡通信資源受限，傳感器節(jié)點之間可能存在通信沖突，因此，現(xiàn)有的傳統(tǒng)方法難以有效解決無線傳感器網(wǎng)絡的任務調(diào)度問題。

無線傳感器網(wǎng)絡本身所具有的特性要求任務調(diào)度需要從實時性、經(jīng)濟性、節(jié)能性和動態(tài)協(xié)調(diào)性等方面改善和滿足無線傳感器網(wǎng)絡對系統(tǒng)性能的要求。文獻[2]同時考慮了應用的實時性和網(wǎng)絡的能源有效性，提出了一種基于遺傳算法 (GA, genetic algorithm)的嵌套優(yōu)化技術(shù)，并在多跳聚簇網(wǎng)絡中進行能源高效的任務分配，但該算法在執(zhí)行的過程中默認網(wǎng)絡中傳感器節(jié)點是同構(gòu)的；文獻[3]基于同構(gòu)單跳網(wǎng)絡環(huán)境，設計了一個用于求解任務分配問題的帶整數(shù)線性規(guī)劃的多項式時間三階段啟發(fā)式算法；文獻[4]引入了動態(tài)電壓調(diào)制策略(DVS,dynamic voltage scaling)，提出了一種局部跨層實時的任務映射和調(diào)度方案；文獻[5]在文獻[4]基礎上提出了一個基于獨立于應用的動態(tài)關鍵路徑的任務映射和調(diào)度(DCTMP，dynamic critical-path task mapping and scheduling)方案；文獻[6]將無線傳感器網(wǎng)絡任務分配問題抽象為二次0-1規(guī)劃問題，給出了分布式逐層優(yōu)化分配算法；文獻[7]針對任務在各執(zhí)行器的協(xié)作問題，提出一種動態(tài)調(diào)度策略，根據(jù)執(zhí)行器節(jié)點的剩余能量和工作狀態(tài)，利用混合模擬退火的粒子群優(yōu)化(PSO，particle swarm optimization)算法，在任務時效期內(nèi)統(tǒng)一安排各任務在執(zhí)行器上的執(zhí)行周期；文獻[8]針對傳統(tǒng)的多處理器有向無環(huán)圖(DAG，directed acyclic graph)調(diào)度算法的不足，考慮了能耗和負載平衡2個目標，提出了一種基于GA的任務調(diào)度算法；文獻[9]同時考慮群間和群內(nèi)任務分配的合理性，提出了基于可分負載理論的任務最優(yōu)調(diào)度雙層規(guī)劃模型，并利用罰函數(shù)原理將線性雙層規(guī)劃轉(zhuǎn)化為目標函數(shù)帶懲罰項的單層問題進行求解，很好地最小化任務的完成時間和減少節(jié)點能耗；文獻[10]以空中目標跟蹤為背景，針對無線傳感器網(wǎng)絡協(xié)同信息處理中的任務分配問題，提出一種基于最小能量準則的非全連接的環(huán)形結(jié)構(gòu)的彈性神經(jīng)網(wǎng)絡模型，解決了多目標跟蹤的任務分配問題及多動態(tài)聯(lián)盟對資源競爭沖突時能耗增加的問題；文獻[11]基于動態(tài)聯(lián)盟機制，引入聯(lián)盟覆蓋范圍和休眠聯(lián)盟的概念，提出一種帶有休眠聯(lián)盟的動態(tài)更新聯(lián)盟機制，節(jié)省了網(wǎng)絡資源能耗；文獻[12]為延長網(wǎng)絡的生命周期，通過平衡所有節(jié)點的能量消耗給出了一種能量感知的無線傳感器網(wǎng)絡任務分配算法。

現(xiàn)有的大部分研究工作僅僅停留在無線傳感器網(wǎng)絡的靜態(tài)分配上，雖然有些工作考慮到動態(tài)性并提出了一些動態(tài)任務分配算法，但大多在任務分配的初始階段就設定了節(jié)點及網(wǎng)絡的狀態(tài)，并沒有真正結(jié)合無線傳感器網(wǎng)絡的動態(tài)性，來設計真正適用于無線傳感器網(wǎng)絡的任務分配算法。文獻[13]引入動態(tài)聯(lián)盟機制，給出了無線傳感器網(wǎng)絡任務分配的動態(tài)聯(lián)盟模型及其相應的求解算法，繼而采用多agent技術(shù)，將動態(tài)聯(lián)盟機制和自適應調(diào)整機制相結(jié)合，設計了一個基于多agent的無線傳感器網(wǎng)絡自適應任務調(diào)度策略[14]。但該模型只涉及到動態(tài)聯(lián)盟的串行聯(lián)盟機制，并沒有考慮并發(fā)的多任務分配和任務截止期的約束。本文基于動態(tài)聯(lián)盟機制，設計了一個無線傳感器網(wǎng)絡的自適應任務分配算法。算法根據(jù)任務截止期賦予任務優(yōu)先級，優(yōu)先考慮高優(yōu)先級任務，對截止期較為緊迫的任務，采用歷史信息生成歷史聯(lián)盟，并執(zhí)行快速子任務分配算法，而對截止期較為寬裕的任務，在滿足任務截止期約束條件下，以節(jié)點能耗和網(wǎng)絡能量分布平衡為優(yōu)化目標定義適應度函數(shù)，設計了一種離散粒子群優(yōu)化算法，以并行生成聯(lián)盟，并執(zhí)行基于負載和能量平衡的子任務分配算法。

3 問題描述

3.1 WSN任務分配問題

考慮一個無線傳感器網(wǎng)絡由n個異構(gòu)傳感器組成，有m個獨立任務要競爭使用傳感器，假定該無線傳感器網(wǎng)絡為一個軟實時系統(tǒng)，即在一定范圍內(nèi)允許調(diào)度失敗而不引起任何災難性后果，同時截止期未得到保證的任務不予調(diào)度執(zhí)行以避免不必要的能量損耗，則任務分配的目標就是要把這m個任務合理地分配到n個傳感器上執(zhí)行，在盡可能滿足任務截止期約束的前提下，優(yōu)化網(wǎng)絡的能耗，均衡網(wǎng)絡的負載，并延長網(wǎng)絡的生命周期。

根據(jù)實際需求，每個任務可以分解為多個不同的子任務，子任務是傳感器節(jié)點執(zhí)行的基本單位，最多可達到l個，匯聚節(jié)點（sink）實時感知任務并分解成不同需求的子任務，具體的任務需求可由一個m×l的矩陣REQ來表示，其中的元素reqij表示任務i的第j個子任務需求。此外，用一個n維向量E表示節(jié)點能量，ei表示第i個節(jié)點的能量，并采用一個n×l的矩陣B來表示不同節(jié)點對不同子任務的處理能力，元素bi,j表示第i個節(jié)點處理第j個子任務的能力，任務的截止期則用一個向量D來表示，元素di可表示為第i個任務的截止時間，另用一個矩陣A表示執(zhí)行具體子任務的傳感器節(jié)點，元素aij表示執(zhí)行第i個任務中第j個子任務的傳感器編號，那么可以采用式(1)表示任務i是否錯失截止期，若Gapi值為0，則表示按期完成，否則Gapi值為超過截止期的時間。

傳感器在處理任務i的計算能量消耗具體表示如下

其中，cosi,j是一個n×l矩陣中的元素，表示節(jié)點i執(zhí)行子任務j的單位計算能耗。

傳感器在處理任務i的過程中進行調(diào)度的必要通信開銷如下

其中，p表示當前任務需要的通信對數(shù)，j1與j2分別代表通信兩端的節(jié)點編號，Ecomm_j表示第j對通信時的能耗，采用文獻[15]中的一階無線模型。

m個任務的總通信能耗EP和當前所有節(jié)點的平均能耗AVGEP分別為

能量分布平衡度是衡量傳感器網(wǎng)絡的能量分布的平衡程度，其值越小則能量分布平衡越好，從而傳感器網(wǎng)絡的負載平衡越好，可定義為

其中，ei為第i個節(jié)點的能量，eave是網(wǎng)絡所有節(jié)點的平均能量。

3.2 動態(tài)聯(lián)盟模型的構(gòu)造

動態(tài)聯(lián)盟作為多 agent系統(tǒng)中的最為重要協(xié)同合作方式之一，它主要通過發(fā)揮聯(lián)盟內(nèi)各成員的優(yōu)勢或者核心能力，以更高效地完成任務。多任務聯(lián)盟和交叉聯(lián)盟是目前復雜聯(lián)盟的2種主要形式[16]，鑒于動態(tài)聯(lián)盟需要 agent之間反復通信協(xié)商以及無線傳感器網(wǎng)絡節(jié)點能量受限，本文設計了一種交叉聯(lián)盟模型，該模型中一個任務映射一個聯(lián)盟，每個節(jié)點可以加入多個聯(lián)盟，同一個聯(lián)盟內(nèi)的節(jié)點需相互合作共同完成任務，聯(lián)盟由匯聚節(jié)點強制生成，無需成員節(jié)點多余的協(xié)商與交流且不采用聯(lián)盟最終確認的機制。將該模型運用于傳感器網(wǎng)絡節(jié)點動態(tài)組合的研究當中，則傳感器在處理任務i的計算能量消耗和通信開銷的式(2)和式(3)更新為

從而，無線傳感器網(wǎng)絡任務分配的動態(tài)聯(lián)盟可抽象為以下多目標優(yōu)化問題

4 算法實現(xiàn)

4.1 自適應任務分配算法的體系結(jié)構(gòu)

最早截止期優(yōu)先(EDF, earliest deadline first)算法作為最為重要的動態(tài)優(yōu)先級算法之一，已被證明是最佳的動態(tài)優(yōu)先級算法[17]。在系統(tǒng)運行時，匯聚節(jié)點利用EDF思想，對感知到的任務按照截止期非減排序，并按與截止期成反比方式設置優(yōu)先級，即截止期最早的任務擁有最高的優(yōu)先級，進而以優(yōu)先級為順序，分別對每一個任務生成相應的聯(lián)盟，并在聯(lián)盟環(huán)境下，執(zhí)行子任務分配算法，最后通過匯聚節(jié)點發(fā)布任務。當傳感器節(jié)點收到匯聚節(jié)點的指示后，則以子任務所對應任務的優(yōu)先級為先后順序執(zhí)行接收到的各子任務，并向匯聚節(jié)點匯報子任務執(zhí)行狀況。而當任務完成后，為避免不必要的能量消耗，匯聚節(jié)點解散聯(lián)盟，釋放網(wǎng)絡資源，讓其余任務順利得到分配。與此同時，匯聚節(jié)點通過維持一個歷史聯(lián)盟信息(HCI, historical coalition information)的閾值，采用先進先出的策略對接收到的HCI進行更新，具體的分配策略如圖1所示。

圖 1中的聯(lián)盟生成問題本身是一個 NP難的組合優(yōu)化問題，要生成一個較好的聯(lián)盟是一項復雜困難的工作。與其他進化算法相比，PSO算法具有簡單實現(xiàn)和更強的全局優(yōu)化能力的優(yōu)勢，并已經(jīng)成功解決許多領域中的優(yōu)化問題[14,18～20]。無線傳感器網(wǎng)絡中節(jié)點部署、節(jié)點定位、能量有效分簇、數(shù)據(jù)融合以及拓撲控制等問題都可抽象為相應的優(yōu)化問題，文獻[21]很好地綜述了PSO算法在上述領域的具體應用情況。為很好地解決本文 WSN任務分配中的并行聯(lián)盟生成問題，需要選用PSO算法并行生成復雜聯(lián)盟。鑒于PSO在求解聯(lián)盟生成問題中的算法開銷，顯然不適合在不同場合下無條件使用PSO算法并行生成聯(lián)盟，這也無法滿足實時性較強任務的時間約束。為此，本文定義了一個時間閾值T0來判斷任務截止期的緊迫程度，T0主要取決于PSO算法的時間開銷，T0的估值公式為

圖1 自適應任務分配算法的體系結(jié)構(gòu)

其中，mj為S2下的任務數(shù)，K為一常數(shù)，Iter_Num為PSO算法的迭代次數(shù)，Par_Num為PSO算法中的粒子數(shù)，Dmin為集合S2下任務的最早截止期，Dmax則為集合S1中任務的最遲截止期，Cur_Tim為當前時間。

任務可根據(jù)截止期的緊迫程度分別被劃入集合S1和集合S2，集合S1中任務的截止期緊迫，可根據(jù)HCI重新生成歷史聯(lián)盟，并把滿足截止期約束作為該集合下唯一的任務分配目標，執(zhí)行快速子任務分配算法；而集合S2下的任務截止期約束較弱，可采用基于PSO的并行生成聯(lián)盟算法，在滿足任務截止期約束條件下，以節(jié)點能耗、負載均衡、網(wǎng)絡能量分布平衡為S2集合下任務分配的優(yōu)化目標，執(zhí)行基于負載和能量平衡的子任務分配算法。若在當前任務隊列還未執(zhí)行完畢，而新的任務已經(jīng)到達，則可以回收當前已分配卻還未執(zhí)行的任務，將這些任務和新的任務隊列合并為一個任務隊列，然后根據(jù)上述方案進行任務分配。

4.2 基于PSO的并行生成聯(lián)盟算法

PSO算法最初被應用于連續(xù)空間的優(yōu)化，然而文中所涉及的并行聯(lián)盟生成問題本身是一個離散優(yōu)化問題，需要將基本PSO算法在二進制空間進行擴展，構(gòu)造一種離散形式的PSO算法模型。本文作者所在的課題組為解決實際工程應用問題，一直跟蹤PSO算法的研究進展，很好地將PSO算法用于無線傳感器網(wǎng)絡任務調(diào)度[14]、超大規(guī)模集成電路布圖規(guī)劃[19]以及電路劃分[20]等問題的應用中，積累了較好的離散PSO算法構(gòu)造經(jīng)驗。然而文獻[14]只涉及到動態(tài)聯(lián)盟的串行聯(lián)盟機制，并沒有考慮并發(fā)的多任務分配和任務截止期的約束，本文進一步考慮了任務調(diào)度的實時性問題，采用多agent的并行聯(lián)盟思想，將截止期的概念引入問題求解當中并作為評價聯(lián)盟性能的指標之一，對不同截止期任務執(zhí)行不同的子任務分配策略，將無線傳感器網(wǎng)絡中任務調(diào)度的聯(lián)盟并行生成機制和自適應調(diào)整機制結(jié)合。借助前期的算法構(gòu)造經(jīng)驗并對照 PSO算法的基本思想可以發(fā)現(xiàn)，可以利用矩陣形式的二進制編碼方式表示并行聯(lián)盟生成問題，以節(jié)點能耗、網(wǎng)絡能量分布平衡為優(yōu)化目標定義相應的適應度函數(shù)用于指導演化過程已得到優(yōu)化的結(jié)果，從而本文同樣選用全局優(yōu)化能力更強的 PSO算法進行聯(lián)盟生成問題的求解。

4.2.1 粒子的編碼

粒子的編碼分別采用一個m×n的矩陣X和V表示[22]，其中，粒子xij(0 ≤i＜m, 0 ≤j＜n)表示如下

則粒子速度與位置的更新公式如下

其中，X(i)和V(i)分別表示第i個粒子的位置和速度，pBest(i) 是第i個粒子的最優(yōu)值，gBest是全局最優(yōu)值，w是慣性權(quán)值，c1和c2為加速因子，r1和r2是在[0,1]范圍內(nèi)的2個隨機數(shù)，rand()是[0,1]范圍內(nèi)的隨機函數(shù)，sigmoid(V)=1/(1+exp(-V))。

w作為更新公式的一個重要參數(shù)，合適的w值能夠取得全局和局部搜索的平衡，為了提高PSO的全局搜索性能，這里采用經(jīng)典的線性遞減方式[23]

其中，Cur_Iter是當前迭代次數(shù)，Max_Iter是最大迭代次數(shù)，wmax和wmin分別是初始和最終慣性權(quán)值。

4.2.2 適應值函數(shù)

由3.2節(jié)可知，無線傳感器網(wǎng)絡任務分配動態(tài)聯(lián)盟模型是一個多目標優(yōu)化問題，這里采用線性加權(quán)和方式轉(zhuǎn)化為單目標優(yōu)化問題，以期在截止期、網(wǎng)絡能耗和網(wǎng)絡能量平衡度3個性能指標取得一個折中的任務分配方案。

其中，α、β和γ為加權(quán)因子。

4.2.3 算法描述

步驟1 隨機產(chǎn)生每個粒子的初始位置和初始歷史最佳位置pBest，產(chǎn)生全局最佳位置gBest。

步驟2 評價當前各個粒子的適應值，計算每個粒子的評估函數(shù)。

步驟3 如果粒子當前位置比歷史最佳位置pBest好，更新pBest。

步驟4 如果粒子當前位置比全局最佳位置gBest好，更新gBest。

步驟 5 根據(jù)式(13)和式(14)更新粒子的速度和位置。

步驟6 若滿足條件，則輸出群體的最優(yōu)值gBest并結(jié)束，否則轉(zhuǎn)步驟2。

4.3 子任務分配算法

圖2給出了B(i)與ER(i) 2個數(shù)據(jù)標準化函數(shù)曲線，其中，B(i)代表第i個節(jié)點的繁忙程度，是通過Sigmoid函數(shù)將第i個節(jié)點的未來持續(xù)繁忙時間Bzyi(0＜i＜n)映射到區(qū)間[0, 0.5]，具體計算式如下

其中，Bzymax與Bzymin分別指當前聯(lián)盟內(nèi)最繁忙節(jié)點的忙碌時間及最空閑節(jié)點的忙碌時間。

圖2 數(shù)據(jù)標準化函數(shù)曲線

同樣地，這里節(jié)點的剩余能量程度ER(i)也是通過Sigmoid函數(shù)將第i個節(jié)點的剩余能量值ei(0＜i＜n)映射到區(qū)間[0,0.5]，具體計算式如下

其中，emax、emin分別表示當前聯(lián)盟內(nèi)節(jié)點具有的最大剩余能量值與最小剩余能量值。

綜上，節(jié)點效能函數(shù)U(i)是節(jié)點i繁忙程度B(i)和剩余能量程度ER(i)的加權(quán)和，其值越小表示節(jié)點的綜合性能越好。

其中，wt1和wt2為權(quán)重系數(shù)。

針對無線傳感器網(wǎng)絡任務調(diào)度的實時性及節(jié)點計算及能量受限的特點，本文根據(jù)任務截止期的緊迫程度設計 2個不同的子任務分配算法。對S1集合下截止期緊迫的任務，這里采用快速子任務分配算法，僅把在截止期前完成任務作為子任務分配的唯一目標，算法的具體描述如下。

步驟1 在給定一聯(lián)盟內(nèi)，根據(jù)式(17)，匯聚節(jié)點選擇一個具有最小負載值B(i)作為當前待考慮的節(jié)點。

步驟 2 該節(jié)點挑選其最擅長并未被分配的子任務，被選中的子任務將被映射到該節(jié)點待執(zhí)行。

步驟 3 匯聚節(jié)點更新該節(jié)點所對應的B(i)、ER(i)和U(i)值。

步驟 4 若存在子任務尚未分配，轉(zhuǎn)步驟 1，否則結(jié)束。

針對S2集合下的任務，本文設計了一個基于負載和能量平衡的子任務分配算法，該算法同時考慮聯(lián)盟內(nèi)成員節(jié)點的剩余能量與當前負載信息，優(yōu)先挑選剩余能量較多的節(jié)點執(zhí)行子任務，使得聯(lián)盟內(nèi)具有較多能量的節(jié)點優(yōu)先承擔任務，算法的具體流程如下。

步驟1 根據(jù)式(19)，匯聚節(jié)點挑選一個具有最小U(i)效能值的聯(lián)盟成員節(jié)點。

步驟 2 針對被選中的節(jié)點，挑選其擅長的并未被分配的子任務，被選中的子任務將被映射到該節(jié)點待執(zhí)行。

步驟 3 匯聚節(jié)點更新該節(jié)點對應的U(i)、B(i)、ER(i)值。

步驟 4 若存在子任務尚未分配，轉(zhuǎn)步驟 1，否則結(jié)束。

5 仿真實驗與結(jié)果分析

貪心算法和隨機算法是2種經(jīng)典的任務分配算法[24,25]，為了說明本文提出算法（簡稱ERTAA）的有效性，在本文所設計的任務分配體系結(jié)構(gòu)下，融入貪心算法與隨機算法分別設計了基于最小完成時間的子任務貪心分配算法(MCTSAA, minimum complete time sub-task allocation algorithm)及隨機子任務分配算法(RSAA, random sub-task allocation algorithm)，并將其分別應用于各自算法的子任務分配環(huán)節(jié)，并通過大量的實驗來進行分析與對比。文中主要通過以下3個方面比較ERTAA、MCTSAA及RSAA算法的性能。

1) 截止期錯失率(deadline missing ratio)：錯失截止期的任務數(shù)目與感知到的任務總數(shù)的比例。

2) 平均能量消耗(average energy consumption)：無法滿足截止期約束的任務不予調(diào)度執(zhí)行，不消耗能量，故為衡量特定算法下能耗指標的優(yōu)劣，本文所指的平均任務能耗均為被成功執(zhí)行任務的平均能量消耗。

3) 剩余能量平衡度(remaining energy balance)：表示網(wǎng)絡中節(jié)點剩余能量的分布平衡度，該值越小表示網(wǎng)絡中的節(jié)點能量分布的越均衡，計算如式(6)所示。

5.1 實驗環(huán)境設置

假設節(jié)點數(shù)n設為100，任務數(shù)m為100，同時隨機在100 m×100 m的范圍內(nèi)生成各節(jié)點坐標，并根據(jù)節(jié)點坐標位置計算出任意節(jié)點之間距離d，任務最多可拆分為不同的子任務數(shù)目l被置為12。每個任務的通信節(jié)點對數(shù)p及需要兩子任務通信的子任務編號j1與j2分別由位于(0,l/2]及(0,l]區(qū)間的隨機整數(shù)。每個任務的子任務處理需要reqij均勻分布在區(qū)間(2, 6]范圍，同等條件下值越大表示需要處理的時間越久，體現(xiàn)了任務處理的難度；節(jié)點對不同子任務處理能力bi,j均勻分布在區(qū)間(15, 25]，值越大表示節(jié)點的處理對應子任務的能力越強；節(jié)點處理不同子任務的單位能耗cosi,j均勻分布在區(qū)間(3,7]，值越大表示節(jié)點單位計算耗能越多。任務截止期di均勻分布在區(qū)間(2, 5]，節(jié)點初始能量ei均勻分布在區(qū)間(45 000, 55 000] mJ。

為了評價和分析本文ERTAA算法的性能，采用主頻為2.00 GHz的PC機在VC環(huán)境下對ERTAA、MCTSAA和RSAA 3個算法進行一系列的仿真實驗，通過多次實驗，本文算法的參數(shù)按如下設置可以在較短的時間取得優(yōu)質(zhì)解：粒子最大速度Vmax為2.5，最大迭代次數(shù)Max_Iter為50，粒子個數(shù)為30，wmax與wmin為0.9與0.5，c1和c2都為2，α、β和γ分別為0.6、0.3和0.1，wt1和wt2為0.7和0.3。

5.2 實驗結(jié)果分析

5.2.1 不同任務截止期對性能的影響

下面先通過一組實驗來觀察任務截止期對無線傳感器網(wǎng)絡任務分配性能的影響，通過對相同的任務賦予不同的截止期加以測試，設置任務截止期分別在區(qū)間(0, 0.5]、[0, 1]、[0, 1.5]、[0, 2]、[0, 2.5]、[0, 3]服從均勻分布，同時采用任務截止期(0, 0.5]的區(qū)間環(huán)境設置固定的T0值，使得T0值不因?qū)嶒灲刂蛊诘淖兓兓?/p>

如圖3所示，在任務截止期錯失率方面，與算法RSAA相比較，ERATA與MCTSAA能夠較好地滿足任務的截止期約束。當任務截止期位于較為緊迫的(0,0.5]區(qū)間時，由于此時的截止期約束過分苛刻導致了3個算法效果都較差，而隨著任務截止期限值不斷增大，ERATA和MCTSAA的截止期錯失率下降的速度分別都超過了RSAA算法，這是因為ERATA與MCTSAA都考慮了傳感器節(jié)點的負荷，實時動態(tài)地根據(jù)節(jié)點繁忙程度而進行任務分配。而當針對截止期約束寬松的任務時，由于ERATA額外考慮網(wǎng)絡節(jié)點的能量分布因素，從而效果略微不如MCTSAA，但2個算法的結(jié)果非常接近。而對于RSAA，它總是隨機地在網(wǎng)絡中挑選節(jié)點執(zhí)行任務，這意味著該算法幾乎沒有考慮在滿足任務截止期約束下如何改善網(wǎng)絡的性能，因此RSAA在該指標下性能最差。

圖3 不同截止期下的截止期錯失率

圖4和圖5分別為不同截止期約束下剩余能量平衡度及平均能量消耗的結(jié)果比較。由圖可知，隨著任務截止期值增大，3個算法的剩余能量平衡度及平均能耗都有下降，但 ERATA效果最好，MCTSAA最差，這主要是因為 ERATA不僅考慮了任務截止期約束，而且綜合考慮了節(jié)點負載和剩余能量因素，而MCTSAA算法則一味地追求最快速完成任務，不對其他性能指標做任何優(yōu)化。

圖4 不同截止期下剩余能量平衡度

圖5 不同截止期下平均能量消耗

由于截止期緊迫會導致采用RSAA的截止期錯失率較高，任務分配的成功率較低，多數(shù)任務無法得到調(diào)度，從而網(wǎng)絡整體能耗較少。為了進一步進行實驗對比，不失一般性，這里針對任務截止期均勻分布在(0, 2.5]區(qū)間的任務對網(wǎng)絡的生命周期和網(wǎng)絡失效后的平均剩余能量進行測試，同時對所有節(jié)點的初始剩余能量重置為1 500 mJ，其他參數(shù)未變，結(jié)果如表1所示。其中，網(wǎng)絡的生命周期用回合數(shù)來表示，該值表示某種算法能夠運行直至網(wǎng)絡失效的次數(shù)。

表1 網(wǎng)絡的生命周期與平均剩余能量

從表1可以看出，由于ERATA綜合考慮了節(jié)點當前負載及節(jié)點剩余能量的平衡，采用 ERATA算法網(wǎng)絡的生命周期明顯高于采用 MCTSAA與RSAA算法。另外，由于ERATA對截止期較為寬裕的任務多數(shù)采用了基于負載和能量平衡的子任務分配算法，很好地均衡網(wǎng)絡能量并延長網(wǎng)絡的生命周期，從而當網(wǎng)絡失效時，ERATA節(jié)點的平均剩余能量會顯著低于另外2個算法。

5.2.2 不同節(jié)點數(shù)對性能的影響

本節(jié)通過一組實驗來觀察網(wǎng)絡中不同節(jié)點數(shù)目對任務分配的影響，不失一般性，對截止期隨機分布在(2, 5]區(qū)間的任務，分別對具有40、60、80、100、120、140個節(jié)點的網(wǎng)絡進行了測試，各個節(jié)點的剩余能量均勻分布在[45 000, 55 000]mJ范圍，具體結(jié)果如圖6和圖7所示。

從圖6中可以看出，初始由于可用節(jié)點數(shù)目較少，任務數(shù)量過多，無法確保任務在截止期前完成，但隨著節(jié)點數(shù)目增加，3種算法截止期錯失率都呈現(xiàn)迅速下降的趨勢，ERATA和MCTSAA下降尤其明顯，且曲線基本重合，這主要是它們都考慮了節(jié)點的繁忙程度以及節(jié)點處理能力，從而 ERATA和MCTSAA在截止期錯失率方面明顯優(yōu)于RSAA，能夠較好地滿足任務截止期要求。從圖7可知，隨著節(jié)點數(shù)目不斷增加，任務的平均能量消耗也都呈下降趨勢，這主要是因為可供選擇節(jié)點變多，可提供更具節(jié)能的選擇，同上節(jié)實驗，可知ERATA具有較少的能量消耗，而MCTSAA為盡早完成任務，以能耗為代價，未考慮節(jié)能優(yōu)化，導致消耗最多的能量。

圖6 不同節(jié)點數(shù)下的截止期錯失率

圖7 不同節(jié)點數(shù)下任務的平均能量消耗

表2列出3種算法不同節(jié)點數(shù)情況下剩余能量平衡度的對比結(jié)果，由表2可知，隨著節(jié)點數(shù)的增加，3種算法剩余能量平衡度都隨之增大，在同等情況下，ERATA的效果略優(yōu)于MCTSAA與RSAA，這主要是因為面對不緊迫的任務，ERATA采用了基于負載和能量平衡的子任務分配算法，該算法將節(jié)點剩余能量納入考慮范圍，有利于具有較多能量的節(jié)點優(yōu)先選擇子任務執(zhí)行，進而均衡網(wǎng)絡節(jié)點能量分布，從而在網(wǎng)絡具有相同總能量情況下，ERATA更能延長網(wǎng)絡生命周期。

表2 不同節(jié)點數(shù)下的剩余能量平衡度

5.2.3 不同任務數(shù)對性能的影響

為測試不同任務數(shù)目對任務分配性能的影響，本節(jié)針對能量均勻分布在[45 000, 55 000] mJ區(qū)間的100個傳感器節(jié)點，對具有50、100、150、200、250、300個不同的任務進行模擬仿真，不失一般性，設置任務截止期均勻分布在[2, 5]的區(qū)間范圍。

圖8 不同任務數(shù)下的截止期錯失率

圖9 不同任務數(shù)下任務的平均能量消耗

表3列出3種算法在不同任務數(shù)情況下剩余能量平衡度的對比結(jié)果，與表2類似，隨著任務數(shù)的增加，3種算法剩余能量平衡度都隨之增大，同等情況下 ERATA算法的效果略優(yōu)于 MCTSAA與RSAA 2個算法。

表3 不同任務數(shù)下的剩余能量平衡度

6 結(jié)束語

無線傳感器網(wǎng)絡本身所具有的特性要求從實時性、經(jīng)濟性、節(jié)能性和動態(tài)協(xié)調(diào)性等方面，改善和滿足無線傳感器網(wǎng)絡對任務調(diào)度系統(tǒng)的性能要求。圍繞這一中心問題，本文基于動態(tài)聯(lián)盟機制設計了一個無線傳感器網(wǎng)絡自適應任務分配算法，對截止期較為緊迫的任務采用歷史信息生成歷史聯(lián)盟，并執(zhí)行快速子任務分配算法，而對截止期較為寬裕的任務，構(gòu)建了一個離散粒子群優(yōu)化算法以并行生成聯(lián)盟，并執(zhí)行基于負載和能量平衡的子任務分配算法。仿真實驗結(jié)果表明所構(gòu)造的自適應算法能夠較好地滿足任務截止期約束，節(jié)約節(jié)點能耗，均衡網(wǎng)絡負載，并在局部求解與全局探索之間能夠取得了較好的平衡，在較短的時間內(nèi)取得滿意的解。下一步研究工作重點將進一步考慮容錯機制，構(gòu)建一個具有容錯機制的無線傳感器網(wǎng)絡任務自適應分配算法。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y,et al.Wireless sensor networks: a survey[J]. Computer Networks, 2002,38(4): 393-422.

[2] 朱敬華, 高宏. 無線傳感器網(wǎng)絡中能源高效的任務分配算法[J]. 軟件學報, 2007, 18(5):1198-1207.ZHU J H, GAO H. An energy efficient algorithm for task allocation in wireless sensor networks[J]. Journal of Sofware, 2007, 18(5):1198-1207.

[3] YU Y, VIKTOR K P. Energy-balanced task allocation for collaborative processing in wireless sensor networks[J]. Mobile Networks and Applications, 2005, 10(12): 115-131.

[4] TIAN Y, BOANGOAT J, EKICI E,et al. Real-time task mapping and scheduling for collaborative in-network processing in DVS-enabled wireless sensor networks[A]. Proc of the 20th International Parallel and Distributed Processing Symposium[C]. Island, Greece, 2006.

[5] TIAN Y, GU Y Y, EKICI E,et al. Dynamic critical-path task mapping and scheduling for collaborative in network processing in multi-hop wireless sensor networks[A]. Proc of the 2006 International Conference on Parallel Processing Workshops[C]. Columbus, Ohio,USA, 2006. 215-222.2006. 215-222.

[6] 李志剛, 周興社, 李士寧等. 傳感器網(wǎng)絡能源有效任務分配算法[J].計算機研究與發(fā)展, 2009, 46(12): 1994-2002.LI Z G, ZHOU X S, LI S N,et al. An energy efficient task assignment algorithm of wireless sensor network[J]. Journal of Computer Research and Development, 2009, 46(12): 1994- 2002.

[7] 易軍, 石為人, 唐云建等. 無線傳感器/執(zhí)行器網(wǎng)絡任務動態(tài)調(diào)度策略[J]. 電子學報, 2010, 38(6): 1239-1244.YI J, SHI W R, TANG Y J,et al. A dynamic task scheduling for wireless sensor and actuator networks[J]. Acta Electronica Sinica,2010, 38(6): 1239-1244.

[8] ZENG Z W , LIU A F, LI D,et al. A highly efficient DAG task scheduling algorithm for wireless sensor networks[A]. Proc of the 9th International Conference for Young Computer Scientists[C]. 2008.570-575.

[9] 代亮, 沈中, 常義林等. 無線傳感器網(wǎng)絡任務調(diào)度雙層規(guī)劃方法[J].兵工學報, 2010, 31(12): 1697-1701.DAI L, SHEN Z, CHANG Y L,et al. Bilevel programming method for task scheduling in wireless sensor networks[J]. Acta Armamentarii,2010, 31(12): 1697-1701.

[10] 劉梅, 李海昊, 沈毅. 無線傳感器網(wǎng)絡空中目標跟蹤任務分配技術(shù)的研究[J]. 宇航學報, 2007, 28(4): 960-965.LIU M, LI H H, SHEN Y. Research on task allocation technique for aerial target tracking based on wireless sensor network[J]. Journal of Astronautics, 2007, 28(4): 960-965.

[11] 陳劍霞, 于海斌. 一種面向無線傳感器網(wǎng)絡協(xié)同任務分配的動態(tài)聯(lián)盟更新機制[J]. 傳感技術(shù)學報, 2009, 22(4): 499-504.CHEN J X, YU H B. An updating scheme of the working dynamic coalition for collaborative task allocation in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2009, 22(4):499-504.

[12] ABDELHAK S, GURRAM C S, GHOSH S,et al. Energy balancing task allocation on wireless sensor networks for extending the lifetime[A]. Proc of the 2010 IEEE International 53rd Midwest Symposium on Circuits and Systems[C]. Seattle, Washington, 2010.

[13] 陳國龍, .郭文忠, 陳羽中. 無線傳感器網(wǎng)絡任務分配動態(tài)聯(lián)盟模型與算法研究[J]. 通信學報, 2009,30(11): 48-55.CHEN G L, GUO W Z, CHEN Y Z. Research on dynamic alliance of task allocation and its algorithm in wireless sensor network[J]. Journal on Communications, 2009,30(11): 48-55.

[14] GUO W Z, XIONG N X, CHAO H C,et al. Design and analysis of self-adapted task scheduling strategies in wireless sensor networks[J].Sensors, 2011, 11(7): 6533-6554.

[15] HEINZELMAN W B, CHANDRAKASN A P, BALAKRISHNAN H.An application specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4): 660-670.

[16] 張國富, 蔣建國, 夏娜等. 基于離散粒子群算法求解復雜聯(lián)盟生成問題[J]. 電子學報, 2007, 35(2):323-327.ZHANG G F, JIANG J G, XIA N,et al. Solutions of complicated coalition generation based on discrete particle swarm optimization[J].Acta Electronica Sinica, 2007, 35(2): 323-327.

[17] CHETTO H, CHETTO M. Some results of the earliest deadline scheduling algorithm[J]. IEEE Transaction on Software Engineering,1989, 15(10): 1261-1269.

[18] ZHU Z X, ZHOU J R, ZHEN J,et al. DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm[J]. IEEE Transaction on Evolutionary Computation, 2011,15(5): 643-658

[19] CHEN G L, GUO W Z, CHEN Y Z. A PSO-based intelligent decision algorithm for VLSI floor planning[J]. Soft Computing, 2010, 14(12):1329-1337.

[20] 郭文忠, 陳國龍等. 求解 VLSI電路劃分問題的混合粒子群優(yōu)化算法[J]. 軟件學報, 2011, 22(5): 833-842.GUO W Z, CHEN G L,et al. Hybrid particle swarm optimization algorithm for VLSI circuit partitioning[J]. Journal of Software, 2011,22(5): 833-842.

[21] KULKARNI R V, VENAYAGAMOORTHY G K. Particle swarm optimization in wireless sensor networks: a brief survey[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 2011, 41(2): 262-267.

[22] GUO W Z, GAO H L, CHEN G L,et al. Particle swarm optimization for the degree constrained MST problem in WSN topology control[A].Proc of the 2009 International Conference on Machine Learning and Cybernetics[C]. 2009. 1793-1798.

[23] SHI Y, EBERHART R C. A modified particle swarm optimizer[A].Proc of the 1998 IEEE International Conference on Evolutionary Computation[C]. Anchorage, Alaska, 1998. 69-73.

[24] LESSER V, ORTIZ C L, TAMBE M. Distributed Sensor Networks: a Multiagent Perspective[M]. Kluwer Academic Publishers, 2003.

[25] ARMSTRONG R, HENSGEN D, KIDD T. The relative performance of various mapping algorithms is independent of sizable variances in run time predictions[A]. Proc of the 7th IEEE Heterogeneous Computing Workshop[C]. Orlando, USA, 1998. 79-87.