离散差分进化算法生成无线传感器最优化调度方案的方法

摘要

本发明提供的生成最优调度方案的方法通过引入离散差分进化算法，对变异、交叉、选择进行重新定义，使其能应用在离散问题中，经试验证明，离散化差分进化算法在解决离散问题中，与连续版本一样，都具有良好性能。同时，为进一步证明此方法在解决无线传感器网络中传感器调度问题的性能，将该方法与Lee等人提出的改进蚁群算法做出比较。在不同传感器与监测目标的比例的五幅图中，应用该方法，每幅图运行该方法三十次就可求得平均值，其运行的效率高。相对于改进版蚁群算法，本发明提供的方法可将整个网络的工作时间延长10%‑20%。

说明书

技术领域

本发明涉及无线传感网络领域，更具体地，涉及一种运用离散差分进化算法生成无线传感网络中无线传感器最优化调度方案的方法。

背景技术

无线传感网络综合了传感器技术、嵌入式操作系统技术、无线通信技术、信息安全技术、数据融合和数据管理技术等。将多个同构或异构的传感器和其他相关设备组织成一个网络，该网络就称无线传感网络。无线传感网络能够对目标区域内的目标物体的状态进行全方位监控，并具备对所收集到的信息进行实时的收集、处理、分析等功能。

基于上述性质，无线传感网络在实践中已经被用于多个领域，包括实时环境监控、智能家居、军事跟踪、工业生产等。无线传感网络的一般结构如图1所示。

使用无线传感网络进行目标跟踪时一般分为以下几个步骤：1)确定目标；2)划定目标区域；3)部署传感器；4)调控传感器。无线传感器在网络中的部署位置通常分为确定性部署和任意性投放。无线传感器结点的工作方式可分为全唤醒模式、随机唤醒模式、特定调度机制唤醒模式、任务循环唤醒模式等等。通常特定调度机制唤醒模式进行唤醒是比较理想的方式，根据当前网络的拓扑结构及全部传感器的能量状态，根据特定的调度算法选择合适的传感器节点进行唤醒，有利于充分使用传感器能量，延长网络的工作时间。

现有的生成无线传感器调度方案的方法分为两大类，一是将网络中的所有传感器分为多个不重叠的传感器子集，然后依次唤醒这些传感器子集，每个工作中的传感器子集一经调度则工作至这个传感器子集的能量耗尽，功能失效为止。另一类则是，将传感器工作时间和系统工作时间划分为同等大小的刻度，然后为每一个系统时间刻度选择合适的传感器进行唤醒，被唤醒的传感器子集只工作到该时间刻度结束为止。第一种方法中，时间划分粒度较大，导致传感器能量不能被有效的使用；而第二种方法中，当网络中无线传感器的数量增多时，算法计算复杂度增加，同时算法迭代次数也随之增加，但时间粒度划分的减少，可充分利用无线传感器的能量。本发明所提供的方法正是针对第二类传感器唤醒方法。由于一个时间刻度的调度方案会对下一个时间刻度的调度方案产生影响，因此采用一般的深度搜索解空间的方法需要较高的时间复杂度。该问题已经被证明是一种非确定多项式复杂度(NP)完全问题[1]。

现有的研究工作中已经开始尝试将进化算法应用在生成优化的传感器调度方案中。例如，蚁群算法(ACO)、遗传算法(GA)、粒子群算法(PSO)都已经被应用在解决该问题中。其中，Lin等人利用蚁群算法产生传感器和中继器同时存在时最大设备子集的配置方案[2]。Lee则利用遗传算法、粒子群算法和蚁群算法产生在时间粒度较小的情况下每个时间粒度的调度方案，同时制定了一种衡量一个时间粒度内解调度方案的评判标准[3]。

如上所述，将设备划分几个不重复的设备子集的方法并不能充分使用无线传感设备的整体电量，而利用传统的解决离散问题的进化算法不能给问题带来新的突破，同时利用电量单一衡量每一时间刻度解优劣的方法过于片面。

[1]M.Cardei,D.Z.Du.Improving wireless sensor network lifetime throughpower aware organization.Wireless Networks,2005,11(3):333-340.

[2]Y.Lin,J.Zhang,H.S.H.Chung.An ant colony optimization approach formaximizing the lifetime of heterogeneous wireless sensor networks.IEEETransactions on Systems,Man,and Cybernetics,Part C(Applications and Reviews),2012,42(3):408-420.

[3]J.W.Lee,J.J Lee.Ant-colony-based scheduling algorithm for energy-efficient coverage of WSN.Sensors Journal,IEEE,2012,12(10):3036-3046.

[4]Liu Y,Chen W N,Zhan Z H,et al.A Set-Based Discrete DifferentialEvolution Algorithm,2013IEEE International Conference on Systems,Man,andCybernetics.IEEE,2013:1347-1352.

发明内容

本发明为解决以上现有技术的难题，提供了一种基于离散差分进化算法生成无线传感器最优化调度方案的方法，该方法用于解决无线传感网络中无线传感器的调度问题。

为实现以上发明目的，采用的技术方案是：

离散差分进化算法生成无线传感器最优调度方案的方法，用于为无线传感网络中将工作时间和电量平均划分为k份的无线传感器生成最优调度方案，该传感器在一份时间内消耗一份电量，其特征在于：对于每个时间刻度，该方法基于离散差分进化算法生成最优调度方案的过程包括以下步骤：

S1.初始化解空间，随机生成N_P个解：

其中表示为第i个初始化的解，分别表示无线传感网络中N_se个传感器的状态，其状态用0或1表示；其中0表示传感器处于睡眠状态，1表示传感器处于唤醒状态；

S2.初始化解空间后，进入步骤S3～S6的迭代过程；

S3.变异：将当前解空间中的每一个解当做一个目标集合，然后对每一个目标集合执行一次变异操作，产生一个变异集合v_j＝x_r1+F·(x_r2-x_r3)，j＝1,2,…,N_se；其中k表示迭代次数；

其中r1、r2和r3为在1-NP之间随机产生的数，r1、r2和r3之间互不相等，且均不等于i；F表示用于控制放缩大小的控制参数；

S4.交叉：对于每一个变异集合产生一个实验集合其构造方式如下：

其中CR为交叉参数，用来控制变异集合对目标集合的影响，j_rand为[1,j_rand]的随机整数，用于保证实验集合的扰动性；

S5.选择：比较实验集合和目标集合的适应值函数的大小：若实验集合的适应值函数小于目标集合的适应值函数，则选择实验集合作为目标集合参与下一次迭代，否则继续选择目标集合参与下一次迭代；

S6.重复步骤S3～S5直至迭代次数达到设定值，此时将目标集合X中适应值函数最小的集合作为最优解进行输出，输出的最优解即为当前时间刻度无线传感网络中传感器的最优调度方案。

优选地，所述适应值函数具体表示如下：

其中n表示第n个时间刻度，表示第n个时间刻度结束后监测目标p的被覆盖率，N_p表示监测目标的数量；e_j表示传感器j在当前剩余的电量；

其中d_pj表示传感器j和监测目标p之间的欧式距离，r_s和r_u分别表示传感器j的小传感边界和大传感边界，a和m为与传感器j种类有关的两个参数。

优选地，在进行步骤S1前，先判断唤醒当前还有能量剩余的传感器时能否满足所有监测目标的覆盖要求，若是，则执行步骤S1。

优选地，利用下式来确定传感器能否满足所有监测目标的覆盖要求：

p_pj表示为传感器j对监测目标p的感知概率，x_j表示是否调度传感器j，x_j可用1或0表示，1表示调度传感器j，0表示不调度，ε表示感知阈值。

与现有技术相比，本发明的有益效果是：

本发明提供的生成最优调度方案的方法通过引入离散差分进化算法，并对变异、交叉、选择进行重新定义，使其能应用在离散问题中，经试验证明，离散化差分进化算法在解决离散问题中，与连续版本一样，都具有良好性能。同时，为进一步证明此方法在解决无线传感器网络中传感器调度问题的性能，将该方法与Lee等人提出的改进蚁群算法做出比较。在不同传感器与监测目标的比例的五幅图中，应用该方法，每幅图运行该方法三十次就可求得平均值，其运行的效率高。相对于改进版蚁群算法，本发明提供的方法可将整个网络的工作时间延长10％-20％。

附图说明

图1为无线传感网络的结构示意图。

图2为离散差分进化算法的流程图。

图3为生成最优化调度方案的流程图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

以下结合附图和实施例对本发明做进一步的阐述。

实施例1

构造出一个完整的无线传感网络分为以下几个步骤：1)确定要监测目标；2)划定出目标区域；3)确定要部署的设备的种类、数量和位置。本发明所针对的无线传感网络，其将系统的工作时间和传感器的工作时间划分为相等的单位时间刻度。传感器每工作一个时间时刻，便消耗相等比例的电量。对于系统来说，若每个时间刻度内能够选出满足条件的传感器子集，则整个网络的工作时间可以延长一个刻度。

无线传感网络的一般构造如图1所示，划定的目标区域内，有既定的所有的需要被监控的监测目标，还有部署的众多传感器，和一个控制中心，用来收集传感器反馈的信息和关闭唤醒传感器。为方便调度传感器，控制中心首先确定传感器和监测目标的位置信息。然后基于传感器和监测目标的位置信息，建立传感器对监测目标监控概率(在传感器被唤醒的情况下)。

在本方法中采用概率感知模型对传感器和监测目标之间的关系进行建模，概率模型基于现实生活中信号衰减的特点，传感器对监测目标的感知概率随着距离的增大而减小。形式化表达如下：

其中d_pj表示传感器j和监测目标p之间的欧式距离，r_s和r_u分别表示传感器j的小传感边界和大传感边界，a和m为与传感器j种类有关的两个参数。依次可以建立所有监测目标与所有传感器之间的目标感知矩阵，SP＝[p_pj]，其中存放着传感器j(在唤醒的情况下)对监测目标p的监测概率。

在本方法中将系统工作时间和传感器的可持续工作时间划分为相等单位的时间刻度T。本实施例中，将传感器的电量分为十个刻度，每工作一个时间刻度，花费十分之一的电。系统每运行一次离散化差分进化算法，找出一个传感器子集，唤醒该传感器子集可使系统的工作时间整体延长T。

如图2、3所示，本发明提供的方法包括以下步骤：

S1.传感器电量初始化

e_j＝10e₀(j＝1,2,…,N_se)

e₀的电量可使传感器工作T₀时间(一个时间刻度)。

S2.初始化解空间，随机为生成N_P个解：

其中表示为第i个初始化的解，分别表示无线传感网络中N_se个传感器的状态，其状态用0或1表示；其中0表示传感器处于睡眠状态，1表示传感器处于唤醒状态；

S3.初始化解空间后，进入步骤S4～S7的迭代过程；

S4.变异：将当前解空间中的每一个解当做一个目标集合，然后对每一个目标集合执行一次变异操作，产生一个变异集合v_j＝x_r1+F·(x_r2-x_r3)，j＝1,2,…,N_se；其中k表示迭代次数；

其中r1、r2和r3为在1-NP之间随机产生的数，r1、r2和r3之间互不相等，且均不等于i；F表示用于控制放缩大小的控制参数；

S5.交叉：对于每一个变异集合产生一个实验集合其构造方式如下：

其中CR为交叉参数，用来控制变异集合对目标集合的影响，j_rand为[1,j_rand]的随机整数，用于保证实验集合的扰动性；

S6.选择：比较实验集合和目标集合的适应值函数的大小：若实验集合的适应值函数小于目标集合的适应值函数，则选择实验集合作为目标集合参与下一次迭代，否则继续选择目标集合参与下一次迭代；

S7.重复步骤S4～S6直至迭代次数达到设定值，此时将目标集合X中适应值函数最小的集合作为最优解进行输出，输出的最优解即为当前时间刻度无线传感网络中传感器的最优调度方案。

其中，上述方案中的(1)式的减法操作、加法操作、乘法操作具体定义如下：

一、减法操作

两个集合之间的减法操作按如下定义，差集中的元素为那些存在被减集合但不存在于减集合中的元素组成：

两个目标集合(Individual set)相减之后得到一个差分集合(Differentialset)

二、乘法操作

当用一个实数因子乘以一个集合之后，则就各个集合中的元素按照实数因子的定义的范围进行保留或者清空：

其中d为原集合中的每个元素

三、加法操作

目标集与放缩之后的差分集合进行加法操作，合集中的元素即为两个集合中元素的并集，在本算法背景下就是基于差分集合对于目标集的一个扩充操作。

A+B＝{e|e∈A or e∈B}

同时，本方法中引入一个新颖的构造适应值函数的方法，即观察判断两个传感器子集对当前系统中监测目标被覆盖的可靠度的影响。对于每个监测目标，其周围被覆盖的可靠度可以用其周围传感器感知该监测目标的感知概率和该传感器的电量来衡量。

当某个传感器被唤醒，工作一个时间刻度之后，该传感器的电量将会失去部分，因此监测目标被覆盖的可靠程度将会变化。因此，适应值函数通过衡量该传感器子集对所有监测目标被覆盖的可靠程度的影响(监测目标被覆盖可靠程度减小的平均值)来判定。

作为一个无线传感器网络，各个监测目标都有被监测概率上的要求。该要求随着无线传感器在不同应用场景的不同而不同。因此，在计算适应值函数的值之前首先要判定该传感器子集是否能够满足所有监测目标的被覆盖的要求。本方法中，采用的是丢弃-惩罚(dead-punishment)，即若当前传感器子集不能满足所有监测目标的覆盖要求，则对应的适应值函数值被设定为负无穷大。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。