CPS 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度設(shè)計(jì)

0 引 言

信息物理融合系統(tǒng)（Cyber-Physical System，CPS）是一個(gè)集傳感器系統(tǒng)、嵌入式網(wǎng)絡(luò)系統(tǒng)和計(jì)算機(jī)系統(tǒng)等眾多子系統(tǒng)于一體的復(fù)雜系統(tǒng)，各子系統(tǒng)相互協(xié)作，共同完成 CPS 任務(wù)要求。CPS 通過傳感器系統(tǒng)獲取物理世界的信息。傳感器系統(tǒng)是由眾多傳感器節(jié)點(diǎn)構(gòu)成的具有一定自組織能力的無線傳感器網(wǎng)絡(luò)，各傳感器節(jié)點(diǎn)相互協(xié)作完成特定的感知任務(wù)。通常傳感器節(jié)點(diǎn)的電源模塊攜帶能量較少，因此合理分配和管理傳感器資源，實(shí)現(xiàn)對(duì)傳感器節(jié)點(diǎn)的有效調(diào)度已成為目前CPS 研究的熱點(diǎn)問題?；旌贤芴惴ㄊ且环N全新的群智能化算法，利用該算法可滿足簡單、收斂速度快、算法參數(shù)少、尋優(yōu)速度快等要求。本文將混合蛙跳調(diào)度算法融入 CPS 傳感器節(jié)點(diǎn)調(diào)度中，提出了一種基于混合蛙跳多目標(biāo)優(yōu)化調(diào)度算法。

1 任務(wù)調(diào)度模型

假設(shè)有 N 個(gè)獨(dú)立的任務(wù)競爭使用傳感器網(wǎng)絡(luò)中的 M 個(gè)節(jié)點(diǎn)，傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的實(shí)質(zhì)是將 N 個(gè)相互獨(dú)立的任務(wù)合理分配到 M 個(gè)異構(gòu)可用傳感器資源上執(zhí)行 [1]。 圖 1 所示為用 DAG 圖表示的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的任務(wù)調(diào)度模型。在 DAG 圖中需要為節(jié)點(diǎn)和邊添加屬性來表示任務(wù)信息 [2]。DAG=（T，E）， 其 中，T 表示執(zhí)行任務(wù)傳感器節(jié)點(diǎn)集合 ；E 表示傳感器節(jié)點(diǎn)通信邊集合，

接收 K bit 數(shù)據(jù)消耗的能量見式（2）：

式中：d0 為常量；d 為發(fā)送節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離；Eelec 為發(fā)送或接收每比特?cái)?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í)行時(shí)間 ；ETCij 表示任務(wù) i 在第 j 個(gè)資源上的理論執(zhí)行時(shí)間 ；傳感器Sj 的理論執(zhí)行時(shí)間為

負(fù)載均衡定義式 ：

傳感器節(jié)點(diǎn)能量總損耗定義式 ：E X E E im pi ci ( ) = + ( ) =∑1 ，式中 ：Ep 為傳感器任務(wù)處理時(shí)的能量損耗 ；Ec 為任務(wù)調(diào)度中的通信損耗。為實(shí)現(xiàn)調(diào)度具有最優(yōu)跨度、較優(yōu)的負(fù)載均衡和較低的能量損耗，利用加權(quán)模型得到傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的評(píng)價(jià)函數(shù) ：F（X）=min（a·Time（X）+b·Load（X）+c·E（X）），a， b，c 分別代表任務(wù)完成時(shí)間、負(fù)載衡和傳感器節(jié)點(diǎn)能量損耗的加權(quán)因子。

3 混合蛙跳算法

Eusuff 和 Lansey 為解決組合優(yōu)化問題提出了混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）。該算法首先隨機(jī)產(chǎn)生一個(gè)包含若干族群的青蛙種群，且每個(gè)族群中的青蛙根據(jù)自身文化及族群間文化的影響進(jìn)行跳躍，完成族群間的信息交流，通過不斷進(jìn)行族群進(jìn)化和族群混合，最終使得整個(gè)種群逼向食物源 [5]。算法的執(zhí)行過程分為族群劃分、族群內(nèi)部搜索和全局信息交換三部分 [6]。

族群劃分 ：設(shè)種群中青蛙數(shù)為 P，每只青蛙為一個(gè)候選解，族群數(shù)為 m，每個(gè)族群中有 n 只青蛙。隨機(jī)產(chǎn)生的初始種群得出每一個(gè)候選解的適應(yīng)度值，并進(jìn)行降序排列，其中第 km+i（k=0，1，2，…，n-1 ；i=1，2，…，m）只青蛙分到第 i 組。

族群內(nèi)部搜索 ：設(shè)整個(gè)種群內(nèi)適應(yīng)度最優(yōu)的候選解為Pg，而一個(gè)族群內(nèi)適應(yīng)度最優(yōu)和最差的候選解分別為 Pb 和 Pw。所有族群進(jìn)行內(nèi)部搜索，對(duì)每個(gè)族群中的 Pw 進(jìn)行更新。

式中 Dmax 表示青蛙個(gè)體的最大跳動(dòng)步長。更新后，若產(chǎn)生的newPw 的適應(yīng)度值優(yōu)于 Pw 的適應(yīng)度值，則 newPw=Pw；否則， 用 Pg 代替 Pb 進(jìn)行步長更新和個(gè)體位置更新。

4 結(jié) 語

信息物理融合系統(tǒng)中感知節(jié)點(diǎn)的能量通常由帶電量有限的電池供應(yīng)，將混合蛙跳算法引入傳感器節(jié)點(diǎn)資源調(diào)度中，可以合理分配傳感器節(jié)點(diǎn)資源，延長傳感器節(jié)點(diǎn)的使用壽命。