宋玉亭

摘 要：針對(duì)CPS系統(tǒng)中能否高效調(diào)度傳感器節(jié)點(diǎn)資源，提出一種基于混合蛙跳算法的任務(wù)調(diào)度算法。混合蛙跳算法兼具模因演化算法和粒子群算法的特點(diǎn)，同時(shí)也存在容易陷入局部最值、收斂速度不佳的缺點(diǎn)。針對(duì)這些問題，結(jié)合CPS傳感器任務(wù)調(diào)度的特點(diǎn)，提出了相應(yīng)的優(yōu)化策略，利用混合蛙跳算法求得最優(yōu)解。

關(guān)鍵詞：CPS;傳感器節(jié)點(diǎn);任務(wù)調(diào)度;混合蛙跳算法;優(yōu)化策略;粒子群算法

中圖分類號(hào)：TP273 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2019）03-00-02

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)問題。混合蛙跳算法是一種全新的群智能化算法，利用該算法可滿足簡(jiǎ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ù)競(jìng)爭(zhēng)使用傳感器網(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)通信邊集合，。根據(jù)文獻(xiàn)[3]，傳感器節(jié)點(diǎn)傳輸能量損耗描述如下：

式中：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)系可用如下矩陣表示：

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]。

族群內(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)的使用壽命。

參 考 文 獻(xiàn)

[1]林偉偉，齊德昱.云計(jì)算資源調(diào)度研究綜述[J].計(jì)算機(jī)科學(xué)， 2012，39（10）：1-6.

[2]房婷.異構(gòu)分布式環(huán)境下任務(wù)調(diào)度問題的研究[D].大連：大連理工大學(xué)，2014.

[3]吉佳，溫巧燕，張華.無線傳感器網(wǎng)絡(luò)中基于分簇的數(shù)據(jù)聚合機(jī)制[J].傳感器與微系統(tǒng)，2015， 34（1）：17-20.

[4]高超，程良倫.一種改進(jìn)的能量均衡非均勻分簇路由算法[J].工業(yè)控制計(jì)算機(jī)，2015（9）：106-108.

[5]康杰紅，馬苗.基于蛙跳算法與Otsu法的圖像多閾值分割技術(shù)[J].云南大學(xué)學(xué)報(bào)（自然科學(xué)版），2012（6）：634-640.

[6]龐樂.改進(jìn)混合蛙跳算法及其在人群運(yùn)動(dòng)仿真中的應(yīng)用研究[D].濟(jì)南：山東師范大學(xué)，2015.

[7]張留朝，張彭，劉貞德.無線傳感器網(wǎng)絡(luò)立體定位算法與仿真[J].物聯(lián)網(wǎng)技術(shù)，2018，8（10）：21-24.

[8]曹晨紅.基于CPS節(jié)點(diǎn)操作系統(tǒng)的調(diào)度系統(tǒng)研究與設(shè)計(jì)[D].沈陽：東北大學(xué)，2013.

[9]楊白薇，于宏毅，李宏.基于協(xié)作的無線傳感器網(wǎng)絡(luò)休眠調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2008，25（3）：677-680.

[10]姚萌萌，邵秀麗，任智娟，等.基于SEP協(xié)議和無線傳感網(wǎng)節(jié)點(diǎn)剩余能量的多跳傳輸節(jié)能算法的實(shí)現(xiàn)[J].物聯(lián)網(wǎng)技術(shù)，2016，6（8）：40-43.