朱曉娟，何勇男

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

0 引 言

近年來，國(guó)內(nèi)外學(xué)者廣泛研究了無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)任務(wù)調(diào)度問題[1-4]。文獻(xiàn)[5]依據(jù)子任務(wù)預(yù)計(jì)完成時(shí)間及權(quán)重系數(shù)求出關(guān)鍵子任務(wù)，優(yōu)先選擇調(diào)度能力強(qiáng)、處理效率高的節(jié)點(diǎn)執(zhí)行。文獻(xiàn)[6]將粒子群算法的自適應(yīng)與動(dòng)態(tài)聯(lián)盟的靈活應(yīng)對(duì)能力進(jìn)行整合，通過加權(quán)方式得到適應(yīng)度值獲得全局最優(yōu)分配方案。文獻(xiàn)[7]提出一種自適應(yīng)調(diào)度器體系結(jié)構(gòu)，可動(dòng)態(tài)地延遲執(zhí)行低優(yōu)先級(jí)任務(wù)，以減少低電量時(shí)的能量消耗。文獻(xiàn)[8]提出了一種使用線性規(guī)劃的動(dòng)態(tài)聯(lián)合任務(wù)分配算法，獲得了更均衡的任務(wù)分配策略。文獻(xiàn)[9]先將任務(wù)分配到不同的集群以達(dá)到減少能源消耗的目的，再將任務(wù)由集群分配給合適的傳感器節(jié)點(diǎn)以平衡網(wǎng)絡(luò)的能量損耗。文獻(xiàn)[10]給出了一種帶遷移策略的記憶蟻群優(yōu)化算法MIACO(memory-based immigrants ACO)，根據(jù)動(dòng)態(tài)環(huán)境對(duì)任務(wù)進(jìn)行遷移。文獻(xiàn)[11]針對(duì)以上問題提出一種基于記憶的動(dòng)態(tài)任務(wù)調(diào)度算法，它首先利用基于異或的動(dòng)態(tài)環(huán)境生成器模擬了無(wú)線傳感器網(wǎng)絡(luò)中因節(jié)點(diǎn)失效產(chǎn)生的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)渥兓賹?duì)模擬的動(dòng)態(tài)環(huán)境進(jìn)行實(shí)時(shí)感知，使算法能夠自適應(yīng)動(dòng)態(tài)環(huán)境以降低能耗。但它在模擬環(huán)境的過程中，并沒有考慮傳感器節(jié)點(diǎn)的感測(cè)質(zhì)量[12]，例如覆蓋率[13]等問題，這與實(shí)際應(yīng)用中的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)有很大區(qū)別。

本文在文獻(xiàn)[11]關(guān)于感知?jiǎng)討B(tài)環(huán)境的基礎(chǔ)上，對(duì)傳感器節(jié)點(diǎn)的覆蓋率、可調(diào)度性等做了一定的約束，并且對(duì)于節(jié)點(diǎn)的加入和離開對(duì)網(wǎng)絡(luò)的影響進(jìn)行了更為細(xì)致的探討，可以有效節(jié)約網(wǎng)絡(luò)的節(jié)點(diǎn)能量。同時(shí)，出于對(duì)網(wǎng)絡(luò)負(fù)載均衡及能量最小化的考慮，將蟻群算法進(jìn)行改進(jìn)后應(yīng)用于動(dòng)態(tài)任務(wù)調(diào)度中，可以延長(zhǎng)網(wǎng)絡(luò)的生存周期。

1 動(dòng)態(tài)任務(wù)調(diào)度模型

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

在本文中，我們考慮如圖1所示的無(wú)線傳感器網(wǎng)絡(luò)。節(jié)點(diǎn)與各種類型的傳感器集成在一起，例如超聲波傳感器，光電傳感器，紅外傳感器等，每個(gè)傳感器負(fù)責(zé)其傳感區(qū)域內(nèi)相應(yīng)目標(biāo)的傳感任務(wù)。通過不同符號(hào)標(biāo)記的感測(cè)任務(wù)對(duì)目標(biāo)實(shí)行分類，即圖1中的▲，■，●，★。在任意時(shí)刻，傳感器節(jié)點(diǎn)都可以精確地感測(cè)每一個(gè)目標(biāo)。我們首先對(duì)節(jié)點(diǎn)的相關(guān)約束進(jìn)行探討。

圖1 網(wǎng)絡(luò)模型

1.1.1 覆蓋率約束

文獻(xiàn)[11]盡管可以快速感知環(huán)境變化，但卻忽視節(jié)點(diǎn)對(duì)于目標(biāo)的覆蓋質(zhì)量，任務(wù)無(wú)法調(diào)度至所有的節(jié)點(diǎn)上執(zhí)行。傳感器節(jié)點(diǎn)能夠同時(shí)感測(cè)不同目標(biāo)的多個(gè)任務(wù)。給定的感測(cè)任務(wù)通常涉及多個(gè)傳感器以實(shí)現(xiàn)一定的感測(cè)質(zhì)量，例如覆蓋率就是一種通常采用的感測(cè)度量。設(shè)計(jì)節(jié)能傳感器調(diào)度和管理策略是重要的，并保證所有任務(wù)的傳感質(zhì)量。

設(shè)S和T分別表示傳感器集合和任務(wù)集合。對(duì)于任務(wù)t∈T， 其感測(cè)目標(biāo)集由Gt表示，并且所需的覆蓋率由dt表示。在不失一般性的情況下，我們假設(shè)傳感器節(jié)點(diǎn)和感測(cè)目標(biāo)在網(wǎng)絡(luò)區(qū)域中隨機(jī)分布。只有在傳感器s的感知范圍之內(nèi)，任務(wù)t∈T的感測(cè)目標(biāo)g∈Gt才能夠被傳感器s監(jiān)測(cè)到。我們可以用vstg來表示這種情況

(1)

再定義一個(gè)二進(jìn)制變量αst來表示傳感器s是否調(diào)度任務(wù)t，如下所示

(2)

無(wú)線傳感器網(wǎng)絡(luò)中的傳感質(zhì)量需滿足兩點(diǎn)，一是目標(biāo)t在s的感測(cè)范圍內(nèi)，即vstg=1； 二是感測(cè)任務(wù)t被調(diào)度時(shí)，傳感器s∈S可以感知任務(wù)t∈T的目標(biāo)g∈Gt。 用βstg表示傳感器s是否能夠感知任務(wù)t的目標(biāo)g，有

βstg=αstvstg, ?s∈S,t∈T,g∈Gt

(3)

對(duì)于被覆蓋的感測(cè)對(duì)象，必須保留其最小感知率以確保感知精度。目標(biāo)的感知率fstg首先由βstg確定，其中，ft為最小采樣率

0≤fstg≤βstg·ft, ?s∈S,t∈T,g∈Gt

(4)

這表示只有當(dāng)傳感器s能夠感知任務(wù)t的目標(biāo)g時(shí)，才能為fstg分配大于0的值。

多個(gè)傳感器可能感測(cè)同一個(gè)目標(biāo)。例如，如圖1所示，黑色三角形中的任務(wù)1的目標(biāo)可以由傳感器A、B和C在它們的重疊覆蓋范圍內(nèi)被感測(cè)。有效感知率不是簡(jiǎn)單地疊加這些傳感器的感知率，因?yàn)閷?duì)相同目標(biāo)進(jìn)行感知會(huì)被認(rèn)定是重復(fù)行為應(yīng)被忽略。則感知任務(wù)t的目標(biāo)g的協(xié)同有效感知率為

(5)

(6)

為了確保每個(gè)感測(cè)任務(wù)的感測(cè)質(zhì)量，對(duì)于覆蓋率δt有以下限制，其中Gt為感測(cè)目標(biāo)的集合

(7)

1.1.2 可調(diào)度性約束

接下來進(jìn)行可調(diào)度性約束的探討。若當(dāng)前任務(wù)均滿足可調(diào)度性判定條件，則認(rèn)為節(jié)點(diǎn)可調(diào)度。相反，若某個(gè)任務(wù)不能滿足可調(diào)度性判定條件，則認(rèn)為節(jié)點(diǎn)不可執(zhí)行該任務(wù)。由于傳感器節(jié)點(diǎn)可以具備多個(gè)感測(cè)目標(biāo)，感測(cè)目標(biāo)g∈Gt， ?t∈T在傳感器節(jié)點(diǎn)s∈S上需要一定的感知率fstg和持續(xù)時(shí)間ct。所有傳感器節(jié)點(diǎn)必須滿足以下限制，以確保多任務(wù)可調(diào)度性

(8)

1.2 傳感器節(jié)點(diǎn)動(dòng)態(tài)變化

在實(shí)際的無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)由容量有限的電池供電，且通常無(wú)法充電，這會(huì)影響整個(gè)傳感器網(wǎng)絡(luò)的壽命,使得一些任務(wù)無(wú)法正常執(zhí)行，因此，網(wǎng)絡(luò)會(huì)重新部署節(jié)點(diǎn)。即在動(dòng)態(tài)網(wǎng)絡(luò)中，現(xiàn)有節(jié)點(diǎn)將因能量耗盡或者故障而離開，而新節(jié)點(diǎn)將會(huì)加入進(jìn)網(wǎng)絡(luò)中。

首先考慮在網(wǎng)絡(luò)中部署新節(jié)點(diǎn)的情況。雖然讓新節(jié)點(diǎn)保持睡眠狀態(tài)并不會(huì)降低感測(cè)質(zhì)量，但是會(huì)失去許多減少原有活動(dòng)節(jié)點(diǎn)數(shù)量的機(jī)會(huì)。如圖2所示，兩個(gè)傳感器節(jié)點(diǎn)A和B分別感測(cè)兩個(gè)目標(biāo)，當(dāng)有新節(jié)點(diǎn) C加入時(shí)，匯聚節(jié)點(diǎn)(sink)根據(jù)節(jié)點(diǎn)C的位置、傳感質(zhì)量、覆蓋率等信息發(fā)現(xiàn)其感測(cè)范圍內(nèi)的潛在感測(cè)目標(biāo)，當(dāng)其感測(cè)范圍能夠覆蓋圖中兩個(gè)目標(biāo)時(shí)，我們可以停用節(jié)點(diǎn)A和B僅保持節(jié)點(diǎn)C處于活動(dòng)狀態(tài)。

圖2 C節(jié)點(diǎn)可覆蓋A、B兩節(jié)點(diǎn)內(nèi)的任務(wù)

然后考慮傳感器節(jié)點(diǎn)離開網(wǎng)絡(luò)的情況。如圖3所示，當(dāng)分配有感測(cè)任務(wù)的傳感器A節(jié)點(diǎn)離開網(wǎng)絡(luò)時(shí)，其鄰居節(jié)點(diǎn)應(yīng)能夠發(fā)現(xiàn)這種事件并將其報(bào)告給匯聚節(jié)點(diǎn)(sink)，而任務(wù)1和3的目標(biāo)在節(jié)點(diǎn)A離開之后變得未被覆蓋，因此，需要激活節(jié)點(diǎn)B和C節(jié)點(diǎn)以確保覆蓋要求。

圖3 A節(jié)點(diǎn)離開時(shí)，需激活B、C節(jié)點(diǎn)

根據(jù)本節(jié)對(duì)于網(wǎng)絡(luò)和節(jié)點(diǎn)的討論，我們可以確定每個(gè)任務(wù)可調(diào)度節(jié)點(diǎn)集合，在下文中用調(diào)度算法將任務(wù)調(diào)度至相關(guān)節(jié)點(diǎn)處執(zhí)行。

2 動(dòng)態(tài)優(yōu)化目標(biāo)

在無(wú)線傳感器網(wǎng)絡(luò)中，動(dòng)態(tài)環(huán)境會(huì)對(duì)任務(wù)調(diào)度產(chǎn)生一定的影響。因此，本文的動(dòng)態(tài)優(yōu)化目標(biāo)不僅需要找到最優(yōu)解，還應(yīng)當(dāng)在環(huán)境發(fā)生改變時(shí)及時(shí)調(diào)整調(diào)度方案。假設(shè)一個(gè)無(wú)線傳感器網(wǎng)絡(luò),其應(yīng)用程序按功能分為m個(gè)任務(wù)：M={Mj∶j=1,2,…,m}。 網(wǎng)絡(luò)有n個(gè)傳感器節(jié)點(diǎn)：N={Ni∶i=1,2,…,n}。 任務(wù)調(diào)度的目的是把m個(gè)任務(wù)合理調(diào)度至n個(gè)傳感器節(jié)點(diǎn)，最優(yōu)解為環(huán)境發(fā)生動(dòng)態(tài)改變時(shí)，使所有任務(wù)完成的總能耗最低的分配方案。

2.1 任務(wù)完成能耗

無(wú)線傳感器網(wǎng)絡(luò)中，任務(wù)調(diào)度不僅需要滿足應(yīng)用對(duì)服務(wù)質(zhì)量的要求，還要盡可能減少任務(wù)的總能耗，該總能耗是指各傳感器節(jié)點(diǎn)完成任務(wù)的能耗之和。由于當(dāng)前考慮的傳感器網(wǎng)絡(luò)不同節(jié)點(diǎn)的計(jì)算能力和通信帶寬具有差異，使得任務(wù)調(diào)度到不同的傳感器節(jié)點(diǎn)上執(zhí)行需要的能耗也會(huì)不同。因此，需要根據(jù)每個(gè)傳感器節(jié)點(diǎn)的計(jì)算能力及每個(gè)任務(wù)的大小來進(jìn)行任務(wù)調(diào)度。本文采用的WSN能耗模型主要由通信和計(jì)算能耗兩部分組成。

2.1.1 通信能耗

無(wú)線傳感器網(wǎng)絡(luò)大部分能耗由數(shù)據(jù)的發(fā)出和接收構(gòu)成，本文中節(jié)點(diǎn)數(shù)據(jù)發(fā)送能耗和接收能耗分別用ET和ER表示。

數(shù)據(jù)發(fā)送能耗

ET(l,d)=l(Eε+Ea×d3)

(9)

數(shù)據(jù)接收能耗

ER(l)=lEε

(10)

其中，l為數(shù)據(jù)包大小，d為發(fā)送距離，Eε為發(fā)送或者接收每比特?cái)?shù)據(jù)的能耗，Ea為每比特?cái)?shù)據(jù)到每平方米的范圍內(nèi)發(fā)射放大器所消耗的能量。

2.1.2 計(jì)算能耗

Eproc=eproc×Tproc

(11)

其中，eproc為節(jié)點(diǎn)在單位時(shí)間內(nèi)的耗能，Tproc為任務(wù)所占用的計(jì)算時(shí)間。

2.1.3 總能耗

綜上，單個(gè)任務(wù)執(zhí)行的能耗應(yīng)為

Ecost=ET+ER+Eproc

(12)

則執(zhí)行所有任務(wù)的總耗能為

(13)

除了對(duì)總能耗的考慮，無(wú)線傳感器網(wǎng)絡(luò)的壽命也是任務(wù)調(diào)度中的關(guān)鍵評(píng)估部分。為了延長(zhǎng)網(wǎng)絡(luò)壽命，我們應(yīng)該平衡每個(gè)傳感器在活動(dòng)期間的能耗。我們可以基于熵理論[14]來測(cè)量傳感器節(jié)點(diǎn)剩余能量的均勻性。

數(shù)據(jù)傳輸后傳感器剩余能量的均勻性可表示如下

Hi=-∑p(Ei)logp(Ei)

(14)

其中，p(Ei) 是傳感器節(jié)點(diǎn)i的剩余能量在所有節(jié)點(diǎn)剩余能量的比值，Hi是網(wǎng)絡(luò)中殘余能量熵的值。信息熵是從物理學(xué)范疇中引入的度量不確定方法的概念，是系統(tǒng)不確定性的有效度量。若不確定性越大，在式(14)中各節(jié)點(diǎn)占所有節(jié)點(diǎn)的剩余能量的比值p(Ei) 趨于相等，即Hi越高，網(wǎng)絡(luò)負(fù)載越均衡，網(wǎng)絡(luò)壽命越長(zhǎng)。

2.2 動(dòng)態(tài)優(yōu)化目標(biāo)

本文算法的動(dòng)態(tài)優(yōu)化目標(biāo)和約束設(shè)定為

(15)

3 傳感器動(dòng)態(tài)任務(wù)調(diào)度算法

在確定動(dòng)態(tài)環(huán)境下每個(gè)任務(wù)的可調(diào)度節(jié)點(diǎn)的集合之后，便可以將任務(wù)進(jìn)行調(diào)度。原始蟻群算法常被用于搜索和優(yōu)化路徑問題，在本文中，我們將任務(wù)調(diào)度過程中的一次任務(wù)分配當(dāng)作原始蟻群算法的一條路徑，同時(shí)考慮到WSN中網(wǎng)絡(luò)動(dòng)態(tài)環(huán)境及原始蟻群算法易陷入局部最優(yōu)等特性，需要對(duì)算法做進(jìn)一步的改進(jìn)。

3.1 概率轉(zhuǎn)移函數(shù)

螞蟻為任務(wù)選擇執(zhí)行節(jié)點(diǎn)時(shí)，要通過如下概率轉(zhuǎn)移函數(shù)進(jìn)行選擇，其中，i為任務(wù)執(zhí)行節(jié)點(diǎn)，Γ為當(dāng)前任務(wù)M允許選擇的節(jié)點(diǎn)集合

(16)

原始蟻群算法的啟發(fā)函數(shù)是由距離的倒數(shù)來表示，但在任務(wù)調(diào)度中發(fā)揮作用較小，因此引用最大信息熵原理[14]對(duì)啟發(fā)因子進(jìn)行改進(jìn)：

n為節(jié)點(diǎn)數(shù)，Ei(t+1) 為節(jié)點(diǎn)i的剩余能量，有

(17)

再用信息熵表示下一時(shí)刻網(wǎng)絡(luò)中節(jié)點(diǎn)能量分布情況

(18)

ηi(t)=H(t+1)

(19)

要使下次循環(huán)網(wǎng)絡(luò)內(nèi)能量均衡，需使H(t+1) 最大，各節(jié)點(diǎn)能量值近似于均勻分布。啟發(fā)因子的值越大，被選中的概率越大。

3.2 信息素?cái)U(kuò)散

原始蟻群算法由于正反饋?zhàn)饔?，易使某些?jié)點(diǎn)信息素越積越多，導(dǎo)致節(jié)點(diǎn)負(fù)載過重，為避免這種情況，每只螞蟻完成一次任務(wù)分配后，都要對(duì)信息素進(jìn)行擴(kuò)散，公式如下

τi(t+1)=(1-ρ)·τi(t)+Δτi(t)

(20)

其中，ρ是信息揮發(fā)因子，表示信息素的揮發(fā)程度， 1-ρ表示信息殘留程度，ρ∈(0,1)。

(1)當(dāng)一只螞蟻完成任務(wù)分配后，會(huì)得出一種分配方案，需要進(jìn)行局部信息素的更新

(21)

其中，Q1為局部信息素強(qiáng)度，E(A)為第i只螞蟻在第nc次迭代中的分配方案所產(chǎn)生的任務(wù)調(diào)度能耗。

(2)當(dāng)前代所有螞蟻完成任務(wù)分配后，需要對(duì)所有的分配方案進(jìn)行比較，得出最優(yōu)值，更新信息素。其中，僅對(duì)最優(yōu)分配方案進(jìn)行全局信息素的更新，而其它分配方案的信息素就會(huì)逐漸的衰減，對(duì)算法的搜索具有一定的方向性，有利于縮小搜索范圍

(22)

其中，Q為全局信息素強(qiáng)度， min(E(A)) 為第nc次迭代中最優(yōu)分配方案所得出的能量消耗。

4 算法流程

步驟1 初始化參數(shù)，包括算法的迭代次數(shù)nc，螞蟻的數(shù)量k，任務(wù)的數(shù)量m，信息素?fù)]發(fā)率參數(shù)ρ，概率轉(zhuǎn)移函數(shù)中兩個(gè)權(quán)重參數(shù)α和β。

步驟2 sink節(jié)點(diǎn)根據(jù)當(dāng)前環(huán)境所產(chǎn)生的約束，確定每一個(gè)新到達(dá)任務(wù)的可調(diào)度節(jié)點(diǎn)集合，記為ΓM。初始化最優(yōu)任務(wù)調(diào)度方案。

步驟3 啟動(dòng)改進(jìn)后的蟻群算法，每只螞蟻按照概率轉(zhuǎn)移函數(shù)(16)為任務(wù)分配合適的節(jié)點(diǎn)，得出解的值即為分配方案。

步驟4 當(dāng)一只螞蟻完成任務(wù)分配之后，要按照式(21)進(jìn)行信息素局部更新。

步驟5 判斷當(dāng)前代螞蟻是否循環(huán)完畢，若否則重復(fù)步驟3和步驟4。若全部螞蟻循環(huán)完畢，則通過式(22)對(duì)信息素進(jìn)行全局更新。

步驟6 判斷迭代是否終止，若否增加迭代次數(shù)，檢測(cè)當(dāng)前環(huán)境是否發(fā)生改變，若發(fā)生改變，則輸出最優(yōu)任務(wù)調(diào)度方案，并返回步驟2；若環(huán)境沒有發(fā)生改變，則返回步驟3。若達(dá)到最大迭代次數(shù)，則算法結(jié)束。

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

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

本文中仿真程序是用Matlab 2017軟件編譯運(yùn)行，在100 m2*100 m2的監(jiān)測(cè)區(qū)域隨機(jī)部署不同數(shù)量的異構(gòu)傳感器節(jié)點(diǎn)，數(shù)目為50個(gè)，節(jié)點(diǎn)初始能量相同，記為2 J。式(9)、式(10)的參數(shù)設(shè)置為：Eε=50 Nj/b，Ea=0.1 nJ/b/m2。 在改進(jìn)的蟻群調(diào)度算法中，迭代次數(shù)設(shè)為300次，環(huán)境每隔50次變化一次，節(jié)點(diǎn)變化(加入和離開)的概率為[0，0.05]。ρ為0.4，α為1.5，β為2。

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

本節(jié)采用文獻(xiàn)[10]提到的帶有遷移策略的蟻群算法(MIACO)以及原始蟻群優(yōu)化算法(ACO)與本文提出的算法進(jìn)行對(duì)比。

由圖4可以看出，本文提出的算法可以對(duì)環(huán)境的變化進(jìn)行感知，能以較快的速度得到最優(yōu)解，其收斂速度、最優(yōu)分配方案得出的任務(wù)能耗均優(yōu)于其它兩種算法。

圖4 環(huán)境每隔100代變化一次的任務(wù)能耗

圖5為算法迭代到300次時(shí)得出的分配方案中任務(wù)總執(zhí)行時(shí)間。在傳感器節(jié)點(diǎn)的數(shù)量不變情況下，隨著任務(wù)數(shù)量的增加，分配給每個(gè)傳感器節(jié)點(diǎn)的任務(wù)量也增加，因此任務(wù)分配的總執(zhí)行時(shí)間也會(huì)增加。但需要注意的是，任務(wù)分配的總執(zhí)行時(shí)間并不是全部任務(wù)分配時(shí)間的總和，如式(24)所示，應(yīng)當(dāng)與任務(wù)分配執(zhí)行時(shí)間最長(zhǎng)的傳感器節(jié)點(diǎn)相同。用Tij表示任務(wù)Mj在節(jié)點(diǎn)Ni上的執(zhí)行時(shí)間，則分配給第i個(gè)傳感器節(jié)點(diǎn)的所有任務(wù)的執(zhí)行時(shí)間可以表示為

(23)

任務(wù)分配總執(zhí)行時(shí)間可以被表示為

T=max(ett(i))

(24)

從圖5中的情況可以看出，帶有遷移策略的蟻群算法執(zhí)行任務(wù)所耗費(fèi)的時(shí)間最多，這是因?yàn)槿蝿?wù)遷移消耗了大量時(shí)間，原始蟻群優(yōu)化算法傾向于將任務(wù)調(diào)度至最優(yōu)點(diǎn)執(zhí)行，從而導(dǎo)致大量任務(wù)擁擠于某些特定節(jié)點(diǎn)，負(fù)載不均衡，排隊(duì)將耗費(fèi)大量時(shí)間。而本文提出的任務(wù)調(diào)度算法緩解了蟻群算法易陷入局部最優(yōu)的問題，并根據(jù)網(wǎng)絡(luò)的整體負(fù)載情況，將任務(wù)調(diào)度至剩余能量充沛的節(jié)點(diǎn)執(zhí)行。

圖5 任務(wù)的執(zhí)行時(shí)間

圖6是網(wǎng)絡(luò)中節(jié)點(diǎn)為100的情況下，完成300次迭代后，各節(jié)點(diǎn)能耗與網(wǎng)絡(luò)中平均能耗的差值同網(wǎng)絡(luò)中平均能耗的比值。如式(25)所示，ei為第i號(hào)節(jié)點(diǎn)的能耗，eave為網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能耗。比值越接近0，代表網(wǎng)絡(luò)中的能量均衡狀況越好。本文提出的任務(wù)調(diào)度算法由于在啟發(fā)函數(shù)中加入了剩余能量的信息熵值，各節(jié)點(diǎn)的能耗基本相同，不會(huì)對(duì)網(wǎng)絡(luò)中某些節(jié)點(diǎn)造成較大負(fù)載影響。這種考慮網(wǎng)絡(luò)負(fù)載因素的算法可以延長(zhǎng)節(jié)點(diǎn)死亡時(shí)間，進(jìn)而提升網(wǎng)絡(luò)的整體壽命

(25)

圖6 能量負(fù)載均衡狀況

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

本文針對(duì)現(xiàn)有的任務(wù)調(diào)度算法的局限性，提出了能量最小化的動(dòng)態(tài)任務(wù)調(diào)度算法。通過對(duì)動(dòng)態(tài)環(huán)境變化進(jìn)行感知，包括了節(jié)點(diǎn)的加入和退出，同時(shí)從覆蓋率、可調(diào)度性對(duì)可調(diào)度節(jié)點(diǎn)進(jìn)行了約束。再根據(jù)改進(jìn)蟻群算法將任務(wù)調(diào)度至剩余能量較為充沛的節(jié)點(diǎn)執(zhí)行。通過仿真實(shí)驗(yàn)可以得出，本文提出的算法可有效縮短任務(wù)的執(zhí)行時(shí)間和減少能耗，對(duì)網(wǎng)絡(luò)負(fù)載起到了很好的平衡作用，延長(zhǎng)網(wǎng)絡(luò)壽命。