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

0 引 言

信息物理融合系统（Cyber-Physical System，CPS）是一个集传感器系统、嵌入式网络系统和计算机系统等众多子系统于一体的复杂系统，各子系统相互协作，共同完成 CPS 任务要求。CPS 通过传感器系统获取物理世界的信息。传感器系统是由众多传感器节点构成的具有一定自组织能力的无线传感器网络，各传感器节点相互协作完成特定的感知任务。通常传感器节点的电源模块携带能量较少，因此合理分配和管理传感器资源，实现对传感器节点的有效调度已成为目前CPS 研究的热点问题。混合蛙跳算法是一种全新的群智能化算法，利用该算法可满足简单、收敛速度快、算法参数少、寻优速度快等要求。本文将混合蛙跳调度算法融入 CPS 传感器节点调度中，提出了一种基于混合蛙跳多目标优化调度算法。

1 任务调度模型

假设有 N 个独立的任务竞争使用传感器网络中的 M 个节点，传感器网络任务调度的实质是将 N 个相互独立的任务合理分配到 M 个异构可用传感器资源上执行 [1]。 图 1 所示为用 DAG 图表示的传感器网络节点的任务调度模型。在 DAG 图中需要为节点和边添加属性来表示任务信息 [2]。DAG=（T，E）， 其 中，T 表示执行任务传感器节点集合 ；E 表示传感器节点通信边集合，

接收 K bit 数据消耗的能量见式（2）：

式中：d0 为常量；d 为发送节点与目标节点的距离；Eelec 为发送或接收每比特数据消耗的能量；εfs 和 εmp 代表在自由空间和多路衰减信道模型上的放大器能量损耗系数 [4]。

2 适应度函数

在传感器网络任务调度中，任务与资源之间的映射关系可用如下矩阵表示 ：

矩阵中，rij 代表任务 i 被分配到资源 j 上，任务与资源间完成了映射，rij=0 表示任务 i 与资源 j 之间未形成映射 ； m×n 的矩阵 ETC 表示各任务在各传感器上预估执行时间 ；ETCij 表示任务 i 在第 j 个资源上的理论执行时间 ；传感器Sj 的理论执行时间为

负载均衡定义式 ：

传感器节点能量总损耗定义式 ：E X E E im pi ci ( ) = + ( ) =∑1 ，式中 ：Ep 为传感器任务处理时的能量损耗 ；Ec 为任务调度中的通信损耗。为实现调度具有最优跨度、较优的负载均衡和较低的能量损耗，利用加权模型得到传感器网络任务调度的评价函数 ：F（X）=min（a·Time（X）+b·Load（X）+c·E（X）），a， b，c 分别代表任务完成时间、负载衡和传感器节点能量损耗的加权因子。

3 混合蛙跳算法

Eusuff 和 Lansey 为解决组合优化问题提出了混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）。该算法首先随机产生一个包含若干族群的青蛙种群，且每个族群中的青蛙根据自身文化及族群间文化的影响进行跳跃，完成族群间的信息交流，通过不断进行族群进化和族群混合，最终使得整个种群逼向食物源 [5]。算法的执行过程分为族群划分、族群内部搜索和全局信息交换三部分 [6]。

族群划分 ：设种群中青蛙数为 P，每只青蛙为一个候选解，族群数为 m，每个族群中有 n 只青蛙。随机产生的初始种群得出每一个候选解的适应度值，并进行降序排列，其中第 km+i（k=0，1，2，…，n-1 ；i=1，2，…，m）只青蛙分到第 i 组。

族群内部搜索 ：设整个种群内适应度最优的候选解为Pg，而一个族群内适应度最优和最差的候选解分别为 Pb 和 Pw。所有族群进行内部搜索，对每个族群中的 Pw 进行更新。

式中 Dmax 表示青蛙个体的最大跳动步长。更新后，若产生的newPw 的适应度值优于 Pw 的适应度值，则 newPw=Pw；否则， 用 Pg 代替 Pb 进行步长更新和个体位置更新。

4 结 语

信息物理融合系统中感知节点的能量通常由带电量有限的电池供应，将混合蛙跳算法引入传感器节点资源调度中，可以合理分配传感器节点资源，延长传感器节点的使用寿命。