CPS传感器网络节点调度设计

2019-03-28宋玉亭

物联网技术 2019年3期

宋玉亭

摘要：针对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.