0 概述

近年来, 随着视频监控、图像、红外和超声波传感器的普及, 有向传感器网络的应用广度和深度日益扩大^[1-2], 而能量问题是制约有向传感器网络应用的一个重要因素, 受到越来越多研究者的重视^[3]。节点调度是一种利用节点状态切换来降低能量消耗和延长网络寿命的有效手段^[4-5], 相关研究较多。文献[6]对有向传感器网络节点多覆盖集问题进行研究, 提出了贪婪的方向优化算法和公平的方向优化算法, 但前者忽略了临界目标的覆盖, 而后者中的效用值计算较为复杂。文献[7]提出一种分布式贪心算法解决有向传感器覆盖调度问题, 但算法仅考虑覆盖面积的最大化, 未考虑节点的能耗问题。文献[8]提出2种启发式有向传感器网络节点调度算法来解决监测目标有优先级情况下的网络覆盖问题, 延长网络寿命, 但算法需要大量的消息交换, 复杂度较高。文献[9]提出一种基于遗传算法的节点调度策略来延长网络的生命周期。文献[10]将网络中的节点划分成多个互不相交的子集合, 每个子集合都能将数据传送到sink节点, 每次只有一个子集合处于工作状态, 其他子集合处于睡眠状态, 以此种方式延长网络的生命周期。

以上研究都是针对调度算法节点参数相同的情况, 未考虑到现实工程实践中异构节点才是最普遍的节点状态, 并且忽视了节点异构性对调度算法的影响。此外, 同构节点构成的网络维护成本高, 不利于节点的大规模部署。为此, 本文利用差分进化(Differential Evolution, DE)算法寻优能力较强的特点, 提出一种改进的DE算法用于异构有向传感器的节点调度。考虑到差分算法控制参数对其性能有重要影响^[11], 并且文献[12-14]参数自适应的差分算法存在实现复杂、盲目性大和缺少对进化过程引导等缺点, 本文通过在差分算法中加入学习自动机, 借助其与环境的反馈增强对进化过程的引导和算法参数的自适应特性, 从而延长网络生命周期。

1 系统模型

在二维平面A内随机分布M个需要监测的目标点T_i(i=1, 2, …, M), 目标点位置信息已知。在二维平面A内部署N个有向传感器节点s_i, 其感知半径为RS_i(i=1, 2, …, N), 通信半径为RC_i(i=1, 2, …, N), 感知方向D_i的数量为|D_i|(i=1, 2, …, N), 感知角度为A_i(i=1, 2, …, N), 携带能量为E_i(i=1, 2, …, N), 所在位置P_i(i=1, 2, …, N)已知或者可通过其他定位技术获得^[11]。这些有向传感器节点的参数, 即感知半径、通信半径, 感知方向的数量、感知角度和携带能量均不相同。假定有向传感器节点同一时刻只能在一个感知方向上处于工作状态, 即同一时刻某个节点只有一个感知方向处于工作状态, 其他的感知方向都处于睡眠状态。在节点能量消耗方面, 用wt表示每个集合工作时间, 在本文中假定节点消耗的能量与节点工作的时间成正比, 即E_si=p′×wt×e(s_i), 其中, p′为比例系数, 本文将其值设为1, e(s_i)为单位时间内节点处于工作状态消耗的能量。

定义1 (目标点T_i被有向传感器节点s_i覆盖)  目标点T_i与有向传感器节点s_i所在位置P_i的距离小于等于s_i的感知半径且s_i与目标点T_i之间的连线与s_i感知方向的夹角小于节点s_i的感知角度的一半。

定义2 (网络寿命)  网络中的节点能覆盖全部监测目标的时间^[10], 也称为网络的生命周期。

从定义1和定义2可以看出, 本文定义的网络寿命不仅与节点所携带的能量有关, 还与节点感知所产生的覆盖监测目标的服务质量密切相关。网络寿命是对满足覆盖监测目标这种服务质量的一种度量。

本文要解决的问题为:如何对有向传感器节点进行集合划分, 使得划分的集合数最多, 同时保证集合中的传感器节点能满足目标覆盖的要求, 进而达到网络的生命周期最大的目标。该问题的形式化描述如下:

$ \max \sum\limits_{k = 1}^K {{t_k}} $

(1)

$ {\rm{s}}.\;{\rm{t}}.\;\;\;\sum\limits_{k = 1}^K {\sum\limits_{j = 1}^{\left| {{D_i}} \right|} {{x_{i,j,k}}} } \cdot {t_k} \le {L_i},\forall {s_i} \in S $

(2)

$ \sum\limits_{j = 1}^{\left| {{D_i}} \right|} {{x_{i,j,k}}} \le 1,\forall {s_i} \in S,k = 1,2, \cdots ,K $

(3)

$ \sum\limits_{{D_{i,j}} \in C\_{T_m}} {{x_{i,j,k}}} \ge 1,\forall {T_m} \in T,k = 1,2, \cdots ,K $

(4)

在上述公式中: ${x_{i, j, k}} = \left\{ {\begin{array}{*{20}{c}} {1, {D_{i, j}} \in {C_k}}\\ {0, \; 其他\; \; \; \; \; \; \; \; } \end{array}} \right.$; t_k表示每个集合的工作时间, t_k≥0;K表示划分的覆盖集合最大数量; D_{i, j}表示节点s_i的第j感知方向; C_k表示第k个满足条件的覆盖集合; L_i表示节点s_i的寿命; C_T_m表示能覆盖监测目标T_m的感知方向的集合, m=1, 2, …, M。式(2)可保证节点工作的时间不会超过其寿命; 式(3)可保证在满足条件的集合中最多只有一个感知方向处于工作状态; 式(4)可保证每个监测目标都能被覆盖集合中的至少一个感知方向所监测到。

2 基于学习自动机的差分进化算法

本节介绍原始差分进化算法、学习自动机的基本知识, 利用学习自动机的性质, 提出一种基于学习自动机的参数自适应差分进化算法。

2.1 差分算法

差分进化算法是为求解切比雪夫多项式拟合问题而提出的一种优化算法^[11-16]。该算法原理简单, 受控参数少, 易于理解和实现, 是一种有效的启发式进化算法。差分算法的一次迭代包括初始化种群、变异、交叉和选择4个基本操作, 算法描述具体如下:

输入    变异参数F, 交叉概率CR和种群规模NP

初始化    进化代数计数器t=0, 并在参数空间随机初始化种群${P^t} = \left\{ {X_1^t, X_2^t, \cdots, X_{NP}^t} \right\}$, 其中, $X_i^t = \left\{ {x_{i1}^t, x_{i2}^t, \cdots, x_{iD}^t} \right\}, i = 1, 2, \cdots NP$

计算初始种群中每一个目标矢量${\rm{X}}_{\rm{i}}^{\rm{t}}\left({{\rm{i}} = 1, 2, \cdots {\rm{NP}}} \right)$的适应度值。

While 预先设定的终止条件不满足 Do

For i=1:NP

//变异操作

为目标矢量X_i^t生成变异矢量:

$ {\rm{V}}_{\rm{i}}^{\rm{t}} = \left( {{\rm{v}}_{{\rm{i1}}}^{\rm{t}},{\rm{v}}_{{\rm{i2}}}^{\rm{t}}, \cdots ,{\rm{v}}_{{\rm{iD}}}^{\rm{t}}} \right) $

$ {\rm{V}}_{\rm{i}}^{{\rm{t}} + 1} = {\rm{X}}_{{\rm{r1}}}^{\rm{t}} + {\rm{F}} \times \left( {{\rm{X}}_{{\rm{r2}}}^{\rm{t}} - {\rm{X}}_{{\rm{r3}}}^{\rm{t}}} \right) $

//交叉操作

变异矢量与目标矢量交叉操作, 生成试验矢量:

$ {\rm{U}}_{\rm{i}}^{\rm{t}} = \left( {{\rm{u}}_{{\rm{i1}}}^{\rm{t}},{\rm{u}}_{{\rm{i2}}}^{\rm{t}}, \cdots ,{\rm{u}}_{{\rm{iD}}}^{\rm{t}}} \right) $

$ u_{{\rm{ij}}}^{\rm{t}} = \left\{ \begin{array}{l} {\rm{v}}_{{\rm{ij}}}^{\rm{t}},{\rm{ran}}{{\rm{d}}_{{\rm{ij}}}} \le {\rm{CR}}\;或\;{\rm{j}} = {{\rm{j}}_{{\rm{rand}}}}\\ {\rm{x}}_{{\rm{ij}}}^{\rm{t}},其他 \end{array} \right. $

//rand_ij是0~1之间的随机数, j_rand是1~D之间的随机//整数

//选择操作

计算试验矢量U_i^t的适应度值并与目标个体X_i^t进行比较:

$ {\rm{X}}_{\rm{i}}^{{\rm{t + 1}}} = \left\{ \begin{array}{l} {\rm{U}}_{\rm{i}}^{\rm{t}},{\rm{f}}\left( {{\rm{U}}_{\rm{i}}^{\rm{t}}} \right) \le {\rm{f}}\left( {{\rm{X}}_{\rm{i}}^{\rm{t}}} \right)\\ {\rm{X}}_{\rm{i}}^{\rm{t}},其他 \end{array} \right. $

End for

t=t+1

End while

2.2 学习自动机

学习自动机是一种能够根据外界环境自适应选择优化行为的智能单元, 其学习能力主要是通过与环境的不断交互来改进自己的行为, 从而在当前的环境条件下, 获得环境奖励最大的动作^[17-18]。一般来说, 学习自动机可用一组四元参数{α, β, p, G}描述。α代表候选动作的集合{α₁, α₂, …, α_r}; r为动作的个数; β表示环境的反馈集合。在学习自动机中, 环境可分为离散环境和连续环境。在连续环境也称为S型环境中, 取值为区间[0, 1]的小数; 在离散环境也称为P型环境中, 取值为0或1。参数p是与候选动作集一一对应概率的集合$\left\{ {{p_1}\left(n \right), {p_2}\left(n \right), \cdots {p_r}\left(n \right)} \right\}$, 表示集合α中每个动作被选中的概率, p_i(n)表示在时刻n对应于动作α_i所选取的概率。一般集合P中的元素需要满足0≤p_i(n)≤1, 各个元素的和为$\sum\limits_{i = 1}^r {{p_i}\left(n \right)} = 1$。G代表学习自动机的更新规则, 映射关系为${p_i}(n + 1) = G\left[{\alpha (n), \beta (n), {p_i}(n)} \right]$。学习自动机在学习过程中基于以下规则更新其动作概率^[17]。

对于有利的响应, 依据式(5)更新动作概率:

$ \begin{array}{l} \left\{ \begin{array}{l} {p_i}\left( {n + 1} \right) = {p_i}\left( n \right) + a \times \left[ {1 - {p_i}\left( n \right)} \right]\\ {p_j}\left( {n + 1} \right) = {p_j}\left( n \right) - a \times {p_j}\left( n \right) \end{array} \right.\\ \forall j \ne i \end{array} $

(5)

对于不利的响应, 依据式(6)更新动作概率:

$ \begin{array}{l} \left\{ \begin{array}{l} {p_i}\left( {n + 1} \right) = {p_i}\left( n \right) - b \times {p_i}\left( n \right)\\ {p_j}\left( {n + 1} \right) = {p_j}\left( n \right) + b \times \left[ {\frac{1}{{r - 1}} - {p_j}\left( n \right)} \right] \end{array} \right.\\ \forall j \ne i \end{array} $

(6)

学习自动机可以分为固定结构和可变结构。可变结构的学习自动机是指行为的数量可以发生变化的学习自动机。学习自动机具有控制规则简单易用不需要耗费计算资源, 适合传感器这种内存和计算资源受限的硬件节点。同时, 学习自动机具有收敛性的好的特点, 能迅速通过与环境的交互和反馈学习中找到优化的解, 具有优化能力强的特点。本文针对待解决问题的特点, 采用可变结构的自动机进行问题求解。

2.3 改进的差分进化算法

差分进化算法中的缩放因子F、交叉概率CR这2个控制参数对算法的优化能力和收敛速度有重要影响。原始差分进化算法中这2个参数的取值是根据经验选取的一组固定的参数, 但经验参数反映的是统计学上的性能效果, 由于这些参数在寻优过程中不发生改变, 无法较好地满足算法性能对控制参数的特殊要求。针对原始差分算法控制参数无法根据优化过程进行自适应调整从而影响算法寻优性能的问题, 本文借助学习自动机与外界环境交互而产生的学习能力对差分算法中的控制参数进行自适应学习, 提出一种基于学习自动机的参数自适应的差分进化算法LADE。

与原始差分算法相比, 本文算法步骤和原始差分算法类似, 只是在每一次迭代之后增加了利用学习自动机进行参数选择的步骤。具体为:针对每个控制参数par_i(i=1, 2;par₁=F; par₂=CR), 先在其可行的取值范围均分为N_i(i=1, 2)个离散的值; 再为每个控制参数par_i配备一个学习自动机LA_i(i=1, 2), LA_i有N_i个行动可选择。每个行动对应着N_i可选的控制参数值, 选取每个行动的概率采用类似遗传算法中轮转法计算得到。利用学习自动机与环境的交互与反馈, 经过一段时间的迭代, 优化的控制参数对应的选取概率较大。利用自动机选取参数的算法伪代码如下:

输入    控制参数par_i

输出    经过学习自动机优化的控制参数par_i

将控制参数par_i候选的取值范围均分成N_i个离散的取值点{par₁, par₂, …, par_N}

为控制参数par_i配备一个候选动作个数为N_i的学习自动机LA_i, 该自动机每个候选动作的概率为1/N_i

While 结束条件不满足时

利用轮转法得到某个候选动作的概率a_active

根据该候选动作的概率a_active得到对应的控制参数值par_active

将该控制参数的值par_active代入差分进化算法中

If 种群中适应度改善的个体总数超出阈值

按照式(5)奖励a_active, 相应地惩罚其他的候选动作概率

Else

按照式(6)惩罚a_active, 相应地奖励其他的候选动作概率

End if

End while

除了利用学习自动机自学习特性使得控制参数具有自适应特性之外, 从提高算法优化能力这个角度考虑, 在算法运行初期, 算法应具有较优的全局搜索能力, 在算法运行末期, 算法应具有较好的收敛速度。基于此, 本文引入一种自适应的变异策略, 对应公式如下:

$ V_i^{t + 1} = \left\{ \begin{array}{l} X_{r1}^t + F \times \left( {X_{r2}^t - X_{r3}^t} \right),1 - t/T > rand\\ {X_{{\rm{best}}}} + F \times \left( {X_{r{\rm{1}}}^t - X_{r{\rm{2}}}^t} \right),其他 \end{array} \right. $

(7)

其中, rand为(0, 1)之间的随机数, t为当前的迭代次数, T为最大的迭代次数。从式(7)可以看出, 在进化初期, DE/rand/1/bin变异策略有较大的概率被选中, 保持了种群的多样性, 从而对整个空间进行探索, 有利于全局优化。随着迭代次数的增加, 该策略被选中的概率增大, 算法的局部寻优能力得以增强, 加快了收敛速率。这种自适应的变异策略增强了算法的鲁棒性和收敛性。

为验证本文算法的有效性, 选择4个标准测试函数进行测试, 函数具体信息如表 1所示。

应用遗传算法(Genetic Algorithm, GA)、模拟退火(Simulated Annealing, SA)算法、原始差分进化CDE算法、本文LADE算法对4个测试函数进行求解。前三种算法均采用相同的参数设置, 即种群规模NP=30, CR=0.6^[18], F服从N(0, 1)正态分布^[19], 在LADE算法中, CR和F的取值范围均为[0, 1]^[19], 以0.05为间距, 将取值区间均分成20个离散的值。测试函数的维数均为30, 最大迭代次数为200, 每个算法重复运行100次进行测试, 表 2列出了测试结果。

从表 2中可以看出, 对于给定的测试函数F₃, DE和LADE算法分别获得了全局优化解0;对于其他测试函数, LADE算法优于其他算法。实验结果表明, 本文LADE算法性能优于其他比较算法, 证明了该算法的有效性。

3 基于LADE的异构有向节点调度

对于异构有向传感器节点调度问题, 本文将其转化为目标优化问题, 采用LADE算法进行求解。LADE算法的主要创新点在于:一方面, 其充分利用了差分算法优化能力强, 控制参数少、原理简单易于实现的特点; 另一方面, 其利用学习自动机与外界环境的“交互”而产生的学习能力, 进一步对原始差分算法的控制参数按照算法进化过程中目标函数的优化结果进行自适应调整, 从而增强了差分算法的优化能力。

3.1 问题编码

种群中的每个个体代表要求解问题的一个候选解, 根据要解决的异构有向节点调度问题的特点, 染色体编码示意图如图 1所示。

在图 1中, 染色体中每个位置g_{i, k}表示含义为第k个时间片里节点S_i的状态, 具体含义为:

$ {g_{i,k}} = \left\{ \begin{array}{l} 0,节点\;{s_i}\;处于休眠状态\\ j,若节点\;{s_i}\;的第\;j\;个感知方向处于工作状态 \end{array} \right. $

(8)

其中, j=1, 2, …, |D_i|。

当进行种群初始化时, 依据式(8)对染色体中每个位置进行初始化。满足条件的覆盖集合需要满足以下条件:

条件1    所有的监测目标必须被覆盖集合中的感知方向所覆盖。

条件2    覆盖集合中不存在不能覆盖监测目标的感知方向。

满足上述2个条件的覆盖集合的个数K由初始部署时能覆盖最稀疏监测目标(能被集合中感知方向监测到, 但被最少感知方向监测到)的感知方向个数d所决定^[20], 其上限为$\frac{d}{{wt}}$, 即$K \le \frac{d}{{wt}}$, 其中wt为每个覆盖集合工作时间。此时网络的生存时间可表示为K′×t, 其中K′为同时满足条件1和条件2的感知方向的集合, 0≤K′≤K。

3.2 适应度函数

本文要研究的问题为在满足覆盖条件的基础上使得网络工作时间最长。由于网络工作时间的长短和节点能量密切相关, 结合上文分析, 本文优化的目标有2个:K′和节点剩余能量E_i, 其数学表达式如式(9)和式(10)所示。

$ {f_1} = \frac{{K'/\left( {d/t} \right)}}{t},{f_2} = \tanh \left( {\alpha \times \sum\limits_{i = 1}^N {{E_i}} } \right) $

(9)

$ f = {\lambda _1} \times {f_1} + {\lambda _2} \times {f_2} $

(10)

其中:f₁为覆盖子目标函数, 其值域为[0, 1];f₂为剩余能量子函数, tanh为双曲正切函数, f₂值域为[0, 1];f为总体目标函数, λ₁和λ₂为子目标函数对应的权值, 它们的值取决于对该网络指标的综合要求, f为[0, 1]之间的一个值, 该值越大表示算法性能越好。

4 仿真实验 4.1 仿真环境设置

为验证算法的性能, 本文利用Matlab进行仿真实验。在仿真中, 节点部署在40 m×40 m方形区域内, 部署节点的个数为45, wt=1 s, 节点的其他参数设置如表 3所示, 感知方向的个数即为2π除以感知角度, 也就是3种类型的传感器节点的感知方向的个数分别为6、4和3。算法其他的参数设置为:G=200, NP=30, CR=0.6^[19], F服从N(0, 1)正态分布^[19], λ₁=λ₂=0.5。

4.2 仿真结果与分析 4.2.1 不同节点数量下的网络寿命比较

为研究不同节点部署总数对传感器网络寿命的影响, 在监测区域分别部署不同数目的传感器节点, 运行本文提出的算法LADE、原始差分进化算法DE和文献[21]提出的GTOH算法, 比较结果如图 2所示, 其中每个结果都是50次结果的平均值。

从图 2中可以看出:

1) 随着部署节点数目的增加, 运行某个特定算法(如GTOH(M=5))的传感器网络的寿命都在增加。原因在于, 节点数目越多, 形成的符合条件的覆盖集合也就越多, 进而网络的寿命得以延长。

2) 对于某个具体的算法, 比如LADE算法, 在部署节点总数不变的情况下, 若需要的监测的目标数增加, 即由M=5变成M=8, 网络的寿命会减少。原因在于, 在节点总数不变的前提下, 监测目标增加会使得可以形成的满足条件的集合数量减少, 从而使得网络的寿命随之减少。

3) 在需要监测的目标不变的情况下, 基于学习自动机的差分算法LADE明显优于原始差分算法DE和GTOH算法, 证明了LADE算法的有效性。

4.2.2 不同异构节点构成比例下的网络寿命比较

为考察不同异构节点构成比例情况下网络寿命的变化情况, 假定参与覆盖的监测目标为M=6, 假设参与调度的节点总数分别为30、45、60, 各种类型节点构成比例如表 4所示。

不同节点构成比例情况下的网络寿命比较如图 3所示, 从中可以看出:

1) 随着节点部署总数的增加, 各种情形下的网络寿命都在增加。

2) 在不同节点类型构成比例情况下, 本文基于学习自动机的差分算法LADE均显著优于比较算法DE, 如在节点总数为60的情况下, 在情形C下运行LADE算法的网络寿命为36 s, 而运行DE算法的网络寿命为20 s, 本文改进算法较DE算法网络寿命提高62.5%, 证明了算法的有效性。

3) 在3种不同情形下, 情形C的网络寿命优于其他2种情形。

4.2.3 平均适应度随迭代次数的变化趋势

为进一步验证算法的性能, 监测目标数M=5, 部署节点数为45, 在其他参数不变的情况下, 比较LADE和DE算法的平均适应度, 每个算法运行50次, 结果取50次结果的平均值, 最终结果如图 4所示。从图 4中可以看出:随着迭代次数的增加, 2种算法的平均适应度都在增加, 并且逐渐趋于收敛; 基于学习自动机的差分进化算法LADE的种群的平均适应度明显优于原始差分的平均适应度, 证明了本文改进策略的有效性。

5 结束语

本文提出一种基于学习自动机的差分进化算法, 用于解决异构有向传感器网络中的节点调度问题。仿真结果表明, 相比原始差分进化算法, 该算法能够增强参数自适应性和优化能力, 同时有效延长异构网络的生存时间。下一步拟将连通性要求加入调度算法, 构造符合覆盖要求和连通要求并且容错性更强的异构有向传感器网络。