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

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

3 問題描述

3.1 WSN任務(wù)分配問題

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

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

傳感器在處理任務(wù)i的計(jì)算能量消耗具體表示如下

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

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

其中，p表示當(dāng)前任務(wù)需要的通信對(duì)數(shù)，j1與j2分別代表通信兩端的節(jié)點(diǎn)編號(hào)，Ecomm_j表示第j對(duì)通信時(shí)的能耗，采用文獻(xiàn)[15]中的一階無線模型。

m個(gè)任務(wù)的總通信能耗EP和當(dāng)前所有節(jié)點(diǎn)的平均能耗AVGEP分別為

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

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

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

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

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

4 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

4.2.1 粒子的編碼

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

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

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

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

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

4.2.2 適應(yīng)值函數(shù)

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

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

4.2.3 算法描述

步驟1 隨機(jī)產(chǎn)生每個(gè)粒子的初始位置和初始?xì)v史最佳位置pBest，產(chǎn)生全局最佳位置gBest。

步驟2 評(píng)價(jià)當(dāng)前各個(gè)粒子的適應(yīng)值，計(jì)算每個(gè)粒子的評(píng)估函數(shù)。

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

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

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

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

4.3 子任務(wù)分配算法

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

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

圖2 數(shù)據(jù)標(biāo)準(zhǔn)化函數(shù)曲線

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

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

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

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

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

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

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

步驟 3 匯聚節(jié)點(diǎn)更新該節(jié)點(diǎn)所對(duì)應(yīng)的B(i)、ER(i)和U(i)值。

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

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

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

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

步驟 3 匯聚節(jié)點(diǎn)更新該節(jié)點(diǎn)對(duì)應(yīng)的U(i)、B(i)、ER(i)值。

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

5 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

5.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

為了評(píng)價(jià)和分析本文ERTAA算法的性能，采用主頻為2.00 GHz的PC機(jī)在VC環(huán)境下對(duì)ERTAA、MCTSAA和RSAA 3個(gè)算法進(jìn)行一系列的仿真實(shí)驗(yàn)，通過多次實(shí)驗(yàn)，本文算法的參數(shù)按如下設(shè)置可以在較短的時(shí)間取得優(yōu)質(zhì)解：粒子最大速度Vmax為2.5，最大迭代次數(shù)Max_Iter為50，粒子個(gè)數(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 實(shí)驗(yàn)結(jié)果分析

5.2.1 不同任務(wù)截止期對(duì)性能的影響

下面先通過一組實(shí)驗(yàn)來觀察任務(wù)截止期對(duì)無線傳感器網(wǎng)絡(luò)任務(wù)分配性能的影響，通過對(duì)相同的任務(wù)賦予不同的截止期加以測(cè)試，設(shè)置任務(wù)截止期分別在區(qū)間(0, 0.5]、[0, 1]、[0, 1.5]、[0, 2]、[0, 2.5]、[0, 3]服從均勻分布，同時(shí)采用任務(wù)截止期(0, 0.5]的區(qū)間環(huán)境設(shè)置固定的T0值，使得T0值不因?qū)嶒?yàn)截止期的變化而變化。

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

圖3 不同截止期下的截止期錯(cuò)失率

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

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

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

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

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

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

5.2.2 不同節(jié)點(diǎn)數(shù)對(duì)性能的影響

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

無線傳感器網(wǎng)絡(luò)本身所具有的特性要求從實(shí)時(shí)性、經(jīng)濟(jì)性、節(jié)能性和動(dòng)態(tài)協(xié)調(diào)性等方面，改善和滿足無線傳感器網(wǎng)絡(luò)對(duì)任務(wù)調(diào)度系統(tǒng)的性能要求。圍繞這一中心問題，本文基于動(dòng)態(tài)聯(lián)盟機(jī)制設(shè)計(jì)了一個(gè)無線傳感器網(wǎng)絡(luò)自適應(yīng)任務(wù)分配算法，對(duì)截止期較為緊迫的任務(wù)采用歷史信息生成歷史聯(lián)盟，并執(zhí)行快速子任務(wù)分配算法，而對(duì)截止期較為寬裕的任務(wù)，構(gòu)建了一個(gè)離散粒子群優(yōu)化算法以并行生成聯(lián)盟，并執(zhí)行基于負(fù)載和能量平衡的子任務(wù)分配算法。仿真實(shí)驗(yàn)結(jié)果表明所構(gòu)造的自適應(yīng)算法能夠較好地滿足任務(wù)截止期約束，節(jié)約節(jié)點(diǎn)能耗，均衡網(wǎng)絡(luò)負(fù)載，并在局部求解與全局探索之間能夠取得了較好的平衡，在較短的時(shí)間內(nèi)取得滿意的解。下一步研究工作重點(diǎn)將進(jìn)一步考慮容錯(cuò)機(jī)制，構(gòu)建一個(gè)具有容錯(cuò)機(jī)制的無線傳感器網(wǎng)絡(luò)任務(wù)自適應(yī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)絡(luò)中能源高效的任務(wù)分配算法[J]. 軟件學(xué)報(bào), 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)絡(luò)能源有效任務(wù)分配算法[J].計(jì)算機(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)絡(luò)任務(wù)動(dòng)態(tài)調(diào)度策略[J]. 電子學(xué)報(bào), 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)絡(luò)任務(wù)調(diào)度雙層規(guī)劃方法[J].兵工學(xué)報(bào), 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)絡(luò)空中目標(biāo)跟蹤任務(wù)分配技術(shù)的研究[J]. 宇航學(xué)報(bào), 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)絡(luò)協(xié)同任務(wù)分配的動(dòng)態(tài)聯(lián)盟更新機(jī)制[J]. 傳感技術(shù)學(xué)報(bào), 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)絡(luò)任務(wù)分配動(dòng)態(tài)聯(lián)盟模型與算法研究[J]. 通信學(xué)報(bào), 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] 張國富, 蔣建國, 夏娜等. 基于離散粒子群算法求解復(fù)雜聯(lián)盟生成問題[J]. 電子學(xué)報(bào), 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]. 軟件學(xué)報(bào), 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.