CPS傳感器網絡節點調度設計

宋玉亭

摘 要：針對CPS系統中能否高效調度傳感器節點資源，提出一種基于混合蛙跳算法的任務調度算法。混合蛙跳算法兼具模因演化算法和粒子群算法的特點，同時也存在容易陷入局部最值、收斂速度不佳的缺點。針對這些問題，結合CPS傳感器任務調度的特點，提出了相應的優化策略，利用混合蛙跳算法求得最優解。

關鍵詞：CPS;傳感器節點;任務調度;混合蛙跳算法;優化策略;粒子群算法

中圖分類號：TP273 文獻標識碼：A 文章編號：2095-1302（2019）03-00-02

0 引 言

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

1 任務調度模型

假設有N個獨立的任務競爭使用傳感器網絡中的M個節點，傳感器網絡任務調度的實質是將N個相互獨立的任務合理分配到M個異構可用傳感器資源上執行[1]。

圖1所示為用DAG圖表示的傳感器網絡節點的任務調度模型。在DAG圖中需要為節點和邊添加屬性來表示任務信息[2]。DAG=（T，E），其中，T表示執行任務傳感器節點集合;E表示傳感器節點通信邊集合，。根據文獻[3]，傳感器節點傳輸能量損耗描述如下：

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

2 適應度函數

在傳感器網絡任務調度中，任務與資源之間的映射關系可用如下矩陣表示：

3 混合蛙跳算法

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

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

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

4 結 語

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

參 考 文 獻

[1]林偉偉，齊德昱.云計算資源調度研究綜述[J].計算機科學， 2012，39（10）：1-6.

[2]房婷.異構分布式環境下任務調度問題的研究[D].大連：大連理工大學，2014.

[3]吉佳，溫巧燕，張華.無線傳感器網絡中基于分簇的數據聚合機制[J].傳感器與微系統，2015， 34（1）：17-20.

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

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

[6]龐樂.改進混合蛙跳算法及其在人群運動仿真中的應用研究[D].濟南：山東師范大學，2015.

[7]張留朝，張彭，劉貞德.無線傳感器網絡立體定位算法與仿真[J].物聯網技術，2018，8（10）：21-24.

[8]曹晨紅.基于CPS節點操作系統的調度系統研究與設計[D].沈陽：東北大學，2013.

[9]楊白薇，于宏毅，李宏.基于協作的無線傳感器網絡休眠調度算法[J].計算機應用研究，2008，25（3）：677-680.

[10]姚萌萌，邵秀麗，任智娟，等.基于SEP協議和無線傳感網節點剩余能量的多跳傳輸節能算法的實現[J].物聯網技術，2016，6（8）：40-43.