0 引 言

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

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

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

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

式中：d0 為常量；d 為發(fā)送節(jié)點與目標節(jié)點的距離；Eelec 為發(fā)送或接收每比特數(shù)據(jù)消耗的能量；εfs 和 εmp 代表在自由空間和多路衰減信道模型上的放大器能量損耗系數(shù) [4]。

2 適應度函數(shù)

在傳感器網(wǎng)絡任務調(diào)度中，任務與資源之間的映射關系可用如下矩陣表示 ：

矩陣中，rij 代表任務 i 被分配到資源 j 上，任務與資源間完成了映射，rij=0 表示任務 i 與資源 j 之間未形成映射 ； m×n 的矩陣 ETC 表示各任務在各傳感器上預估執(zhí)行時間 ；ETCij 表示任務 i 在第 j 個資源上的理論執(zhí)行時間 ；傳感器Sj 的理論執(zhí)行時間為

負載均衡定義式 ：

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

3 混合蛙跳算法

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

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

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

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

4 結 語

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