能量有效的無線傳感器網(wǎng)絡(luò)動態(tài)任務(wù)調(diào)度算法

朱曉娟，何勇男

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

0 引 言

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

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

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

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

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

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

1.1.1 覆蓋率約束

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

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

(1)

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

(2)

無線傳感器網(wǎng)絡(luò)中的傳感質(zhì)量需滿足兩點，一是目標(biāo)t在s的感測范圍內(nèi)，即vstg=1； 二是感測任務(wù)t被調(diào)度時，傳感器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)

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

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

(4)

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

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

(5)

(6)

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

(7)

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

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

(8)

1.2 傳感器節(jié)點動態(tài)變化

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

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

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

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

圖3 A節(jié)點離開時，需激活B、C節(jié)點

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

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

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

2.1 任務(wù)完成能耗

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

2.1.1 通信能耗

無線傳感器網(wǎng)絡(luò)大部分能耗由數(shù)據(jù)的發(fā)出和接收構(gòu)成，本文中節(jié)點數(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ā)送或者接收每比特數(shù)據(jù)的能耗，Ea為每比特數(shù)據(jù)到每平方米的范圍內(nèi)發(fā)射放大器所消耗的能量。

2.1.2 計算能耗

Eproc=eproc×Tproc

(11)

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

2.1.3 總能耗

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

Ecost=ET+ER+Eproc

(12)

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

(13)

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

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

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

(14)

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

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

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

(15)

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

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

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

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

(16)

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

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

(17)

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

(18)

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

(19)

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

3.2 信息素擴散

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

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

(20)

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

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

(21)

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

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

(22)

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

4 算法流程

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

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

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

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

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

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

5 仿真實驗及分析

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

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

5.2 實驗與分析

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

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

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

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

(23)

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

T=max(ett(i))

(24)

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

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

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

(25)

圖6 能量負載均衡狀況

6 結(jié)束語

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