能量有效的無線傳感器網絡動態任務調度算法

朱曉娟，何勇男

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

0 引 言

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

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

1 動態任務調度模型

1.1 網絡模型

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

圖1 網絡模型

1.1.1 覆蓋率約束

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

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

(1)

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

(2)

無線傳感器網絡中的傳感質量需滿足兩點，一是目標t在s的感測范圍內，即vstg=1； 二是感測任務t被調度時，傳感器s∈S可以感知任務t∈T的目標g∈Gt。 用βstg表示傳感器s是否能夠感知任務t的目標g，有

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

(3)

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

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

(4)

這表示只有當傳感器s能夠感知任務t的目標g時，才能為fstg分配大于0的值。

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

(5)

(6)

為了確保每個感測任務的感測質量，對于覆蓋率δt有以下限制，其中Gt為感測目標的集合

(7)

1.1.2 可調度性約束

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

(8)

1.2 傳感器節點動態變化

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

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

圖2 C節點可覆蓋A、B兩節點內的任務

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

圖3 A節點離開時，需激活B、C節點

根據本節對于網絡和節點的討論，我們可以確定每個任務可調度節點集合，在下文中用調度算法將任務調度至相關節點處執行。

2 動態優化目標

在無線傳感器網絡中，動態環境會對任務調度產生一定的影響。因此，本文的動態優化目標不僅需要找到最優解，還應當在環境發生改變時及時調整調度方案。假設一個無線傳感器網絡,其應用程序按功能分為m個任務：M={Mj∶j=1,2,…,m}。 網絡有n個傳感器節點：N={Ni∶i=1,2,…,n}。 任務調度的目的是把m個任務合理調度至n個傳感器節點，最優解為環境發生動態改變時，使所有任務完成的總能耗最低的分配方案。

2.1 任務完成能耗

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

2.1.1 通信能耗

無線傳感器網絡大部分能耗由數據的發出和接收構成，本文中節點數據發送能耗和接收能耗分別用ET和ER表示。

數據發送能耗

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

(9)

數據接收能耗

ER(l)=lEε

(10)

其中，l為數據包大小，d為發送距離，Eε為發送或者接收每比特數據的能耗，Ea為每比特數據到每平方米的范圍內發射放大器所消耗的能量。

2.1.2 計算能耗

Eproc=eproc×Tproc

(11)

其中，eproc為節點在單位時間內的耗能，Tproc為任務所占用的計算時間。

2.1.3 總能耗

綜上，單個任務執行的能耗應為

Ecost=ET+ER+Eproc

(12)

則執行所有任務的總耗能為

(13)

除了對總能耗的考慮，無線傳感器網絡的壽命也是任務調度中的關鍵評估部分。為了延長網絡壽命，我們應該平衡每個傳感器在活動期間的能耗。我們可以基于熵理論[14]來測量傳感器節點剩余能量的均勻性。

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

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

(14)

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

2.2 動態優化目標

本文算法的動態優化目標和約束設定為

(15)

3 傳感器動態任務調度算法

在確定動態環境下每個任務的可調度節點的集合之后，便可以將任務進行調度。原始蟻群算法常被用于搜索和優化路徑問題，在本文中，我們將任務調度過程中的一次任務分配當作原始蟻群算法的一條路徑，同時考慮到WSN中網絡動態環境及原始蟻群算法易陷入局部最優等特性，需要對算法做進一步的改進。

3.1 概率轉移函數

螞蟻為任務選擇執行節點時，要通過如下概率轉移函數進行選擇，其中，i為任務執行節點，Γ為當前任務M允許選擇的節點集合

(16)

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

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

(17)

再用信息熵表示下一時刻網絡中節點能量分布情況

(18)

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

(19)

要使下次循環網絡內能量均衡，需使H(t+1) 最大，各節點能量值近似于均勻分布。啟發因子的值越大，被選中的概率越大。

3.2 信息素擴散

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

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

(20)

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

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

(21)

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

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

(22)

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

4 算法流程

步驟1 初始化參數，包括算法的迭代次數nc，螞蟻的數量k，任務的數量m，信息素揮發率參數ρ，概率轉移函數中兩個權重參數α和β。

步驟2 sink節點根據當前環境所產生的約束，確定每一個新到達任務的可調度節點集合，記為ΓM。初始化最優任務調度方案。

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

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

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

步驟6 判斷迭代是否終止，若否增加迭代次數，檢測當前環境是否發生改變，若發生改變，則輸出最優任務調度方案，并返回步驟2；若環境沒有發生改變，則返回步驟3。若達到最大迭代次數，則算法結束。

5 仿真實驗及分析

5.1 實驗環境設置

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

5.2 實驗與分析

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

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

圖4 環境每隔100代變化一次的任務能耗

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

(23)

任務分配總執行時間可以被表示為

T=max(ett(i))

(24)

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

圖5 任務的執行時間

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

(25)

圖6 能量負載均衡狀況

6 結束語

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