CPS 傳感器網(wǎng)絡(luò)節(jié)點調(diào)度設(shè)計
掃描二維碼
隨時隨地手機(jī)看文章
0 引 言
信息物理融合系統(tǒng)(Cyber-Physical System,CPS)是一個集傳感器系統(tǒng)、嵌入式網(wǎng)絡(luò)系統(tǒng)和計算機(jī)系統(tǒng)等眾多子系統(tǒng)于一體的復(fù)雜系統(tǒng),各子系統(tǒng)相互協(xié)作,共同完成 CPS 任務(wù)要求。CPS 通過傳感器系統(tǒng)獲取物理世界的信息。傳感器系統(tǒng)是由眾多傳感器節(jié)點構(gòu)成的具有一定自組織能力的無線傳感器網(wǎng)絡(luò),各傳感器節(jié)點相互協(xié)作完成特定的感知任務(wù)。通常傳感器節(jié)點的電源模塊攜帶能量較少,因此合理分配和管理傳感器資源,實現(xiàn)對傳感器節(jié)點的有效調(diào)度已成為目前CPS 研究的熱點問題?;旌贤芴惴ㄊ且环N全新的群智能化算法,利用該算法可滿足簡單、收斂速度快、算法參數(shù)少、尋優(yōu)速度快等要求。本文將混合蛙跳調(diào)度算法融入 CPS 傳感器節(jié)點調(diào)度中,提出了一種基于混合蛙跳多目標(biāo)優(yōu)化調(diào)度算法。
1 任務(wù)調(diào)度模型
假設(shè)有 N 個獨立的任務(wù)競爭使用傳感器網(wǎng)絡(luò)中的 M 個節(jié)點,傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的實質(zhì)是將 N 個相互獨立的任務(wù)合理分配到 M 個異構(gòu)可用傳感器資源上執(zhí)行 [1]。 圖 1 所示為用 DAG 圖表示的傳感器網(wǎng)絡(luò)節(jié)點的任務(wù)調(diào)度模型。在 DAG 圖中需要為節(jié)點和邊添加屬性來表示任務(wù)信息 [2]。DAG=(T,E), 其 中,T 表示執(zhí)行任務(wù)傳感器節(jié)點集合 ;E 表示傳感器節(jié)點通信邊集合,
接收 K bit 數(shù)據(jù)消耗的能量見式(2):
式中:d0 為常量;d 為發(fā)送節(jié)點與目標(biāo)節(jié)點的距離;Eelec 為發(fā)送或接收每比特數(shù)據(jù)消耗的能量;εfs 和 εmp 代表在自由空間和多路衰減信道模型上的放大器能量損耗系數(shù) [4]。
2 適應(yīng)度函數(shù)
在傳感器網(wǎng)絡(luò)任務(wù)調(diào)度中,任務(wù)與資源之間的映射關(guān)系可用如下矩陣表示 :
矩陣中,rij 代表任務(wù) i 被分配到資源 j 上,任務(wù)與資源間完成了映射,rij=0 表示任務(wù) i 與資源 j 之間未形成映射 ; m×n 的矩陣 ETC 表示各任務(wù)在各傳感器上預(yù)估執(zhí)行時間 ;ETCij 表示任務(wù) i 在第 j 個資源上的理論執(zhí)行時間 ;傳感器Sj 的理論執(zhí)行時間為
負(fù)載均衡定義式 :
傳感器節(jié)點能量總損耗定義式 :E X E E im pi ci ( ) = + ( ) =∑1 ,式中 :Ep 為傳感器任務(wù)處理時的能量損耗 ;Ec 為任務(wù)調(diào)度中的通信損耗。為實現(xiàn)調(diào)度具有最優(yōu)跨度、較優(yōu)的負(fù)載均衡和較低的能量損耗,利用加權(quán)模型得到傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的評價函數(shù) :F(X)=min(a·Time(X)+b·Load(X)+c·E(X)),a, b,c 分別代表任務(wù)完成時間、負(fù)載衡和傳感器節(jié)點能量損耗的加權(quán)因子。
3 混合蛙跳算法
Eusuff 和 Lansey 為解決組合優(yōu)化問題提出了混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)。該算法首先隨機(jī)產(chǎn)生一個包含若干族群的青蛙種群,且每個族群中的青蛙根據(jù)自身文化及族群間文化的影響進(jìn)行跳躍,完成族群間的信息交流,通過不斷進(jìn)行族群進(jìn)化和族群混合,最終使得整個種群逼向食物源 [5]。算法的執(zhí)行過程分為族群劃分、族群內(nèi)部搜索和全局信息交換三部分 [6]。
族群劃分 :設(shè)種群中青蛙數(shù)為 P,每只青蛙為一個候選解,族群數(shù)為 m,每個族群中有 n 只青蛙。隨機(jī)產(chǎn)生的初始種群得出每一個候選解的適應(yīng)度值,并進(jìn)行降序排列,其中第 km+i(k=0,1,2,…,n-1 ;i=1,2,…,m)只青蛙分到第 i 組。
族群內(nèi)部搜索 :設(shè)整個種群內(nèi)適應(yīng)度最優(yōu)的候選解為Pg,而一個族群內(nèi)適應(yīng)度最優(yōu)和最差的候選解分別為 Pb 和 Pw。所有族群進(jìn)行內(nèi)部搜索,對每個族群中的 Pw 進(jìn)行更新。
式中 Dmax 表示青蛙個體的最大跳動步長。更新后,若產(chǎn)生的newPw 的適應(yīng)度值優(yōu)于 Pw 的適應(yīng)度值,則 newPw=Pw;否則, 用 Pg 代替 Pb 進(jìn)行步長更新和個體位置更新。
4 結(jié) 語
信息物理融合系統(tǒng)中感知節(jié)點的能量通常由帶電量有限的電池供應(yīng),將混合蛙跳算法引入傳感器節(jié)點資源調(diào)度中,可以合理分配傳感器節(jié)點資源,延長傳感器節(jié)點的使用壽命。