基于智能演化的无线多媒体传感器网络覆盖增强方法

摘要

基于智能演化的无线多媒体传感器网络覆盖增强方法是一种用于无线多媒体传感器网络环境，基于多媒体传感器节点的有向感知模型，针对传感器节点主感知方向调整受相邻节点感知方向的相互制约，主感知方向的调整是一个NP-Hard问题，已有的增强方法直接求解时间复杂度较高，和传感器网络能量受限和计算能力不足相矛盾问题，将量子遗传算法应用于无线多媒体传感器网络的覆盖增强中，并针对网络覆盖增强过程的实际需要进行一些改进，主要包括：覆盖增强过程中的基于多媒体传感器节点的单次最小调整角度进行基因量子比特数选取；在角度调整过程中为了避免迭代次数过大问题，提出了基于传感器节点单次角度调整范围的动态量子旋转门策略。

说明书

技术领域

本发明是一种适用于无线多媒体传感器网络(Wireless Multi-media SensorNetworks，缩写为WMSNs)环境中，采用基于动态旋转门的量子遗传智能演化为传感器节点提供一种主感知方向调整的技术，从而实现无线多媒体传感器网络的覆盖增强。本技术属于计算机网络领域。

背景技术

伴随着无线通信技术、机电技术以及嵌入式系统的快速发展而出现的无线传感器网络在工农业、军事、环境监测等领域展现出广泛的应用前景。作为传感器网络高级形式的无线多媒体传感器网络，主要包括视频传感器和图像传感器，该类传感器具备数据、图像和视频等多媒体信息的感知、采集、处理和传输能力，相对于传统传感器网络更具优越性。然而无论在通信协议还是网络服务质量上，无线多媒体传感器网络都对传统无线传感器网络产生了巨大的冲击，传感器网络的覆盖就是一个典型问题。覆盖反映了网络对物理世界的感知范围并直接影响着整个网络的服务质量。总的来看，无线传感器网络覆盖包括三类：点覆盖，传感器节点实现对若干离散点目标的覆盖；区域覆盖，传感器节点实现整个目标区域的覆盖；路径覆盖，也即栅栏覆盖，目标穿越部署传感器节点的区域时，对穿越轨迹节点的覆盖跟踪情况。本发明主要是针对无线多媒体传感器网络的区域覆盖，针对初始场景中多媒体传感器节点位置及其主感知方向随机分布可能产生的监测盲区和监测重叠区，导致监测区域整体覆盖率不高的情况，引入智能计算方法调整初始节点的主感知方向，从而消除监测盲区和监测重叠区，最终实现监测场景的高效覆盖。

目前针对多媒体传感器网络的覆盖增强，主要基于虚拟力或虚拟势场的方法，其通过定义传感器节点的质心，将有向传感器网络覆盖增强问题转化为质心均匀分布问题，以质心点做圆周运动代替传感器节点传感方向的转动，质心在虚拟力作用下作扩散运动，以消除网络中感知重叠区和盲区，最终增强整个传感器网络的覆盖。事实上虚拟势场作为一种基于矢量力合成的人工受力分析方法，其最早通过源于障碍物的排斥力与源于目标点的吸引力的合力应用于机器人的运动规划之中。采用虚拟人工势场法易陷入局部极小点，此时由于机器人运动的速度及方向取决于力矢量和的大小及方向，当合力为零时，机器人就无法运动。对应于传感器网络的覆盖增强也存在类似问题，当传感器节点处于邻居传感器节点对该传感器节点的斥力合力为零的情况，而此时若该传感器节点和周围传感器节点存在大量共同的覆盖区域点时，该传感器节点并没有发挥其有效覆盖功能，对应为陷入局部最小情况。事实上，由于传感器节点主感知方向的调整受相邻节点感知方向的相互制约，因而主感知方向的调整是一个NP-Hard问题。已有的基于势场的增强方法直接进行求解时间复杂度高，和传感器网络能量受限和计算能力不足相矛盾。

发明内容

技术问题：本发明的目的是提供一种基于智能演化的无线多媒体传感器网络覆盖增强方法，采用一种基于动态旋转门的量子遗传算法求解无线多媒体传感器网络覆盖增强过程中节点主感知方向调整的NP-hard问题，通过使用本发明提出的方法可以有效消除多媒体传感器节点的感知重叠区域，从而实现监测场景的高效覆盖。

技术方案：本发明的方法是一种改进性方法，将量子遗传算法应用于无线多媒体传感器网络的覆盖增强中，并针对网络覆盖增强过程中的实际需要进行一些改进，主要包括覆盖增强过程中基于多媒体传感器节点的单次最小调整角度进行基因量子比特数的选取；在角度调整过程中为避免迭代次数过大问题，提出了基于传感器节点单次角度调整范围的动态量子旋转门策略；此外为避免量子遗传算法陷入局部最优，引入相邻两代有效覆盖区域的平均覆盖度最小值之差进行判断，并采用量子非门操作策略跳出局部最优点。通过以上改进，可有效提高覆盖增强的搜索时间和搜索精度，实现多媒体传感器网络监测区域的高效覆盖。

基于量子遗传演化算法的无线多媒体传感器网络覆盖增强，包含在以下具体步骤中：

初始场景设置：

步骤1)配置监测场景及多媒体传感器节点：设置需要采用多媒体传感器网络监测的区域场景大小；初始化监测场景中无线多媒体传感器节点的数量、布撒位置、主感知方向、感知半径以及传感器节点单次调整的角度值范围；

步骤2)配置量子遗传算法：设定种群初始规模，即染色体数目；根据场景中初始节点的数目配置染色体的基因数；根据传感器节点单次调整的最小角度值配置基因的量子比特数；根据传感器节点的单次调整的角度范围设定量子旋转门中的角度函数；

多媒体传感器节点最佳主感知方向计算：

步骤3)在[0，1]中随机选择一个数，和量子遗传算法的量子比特的概率幅进行比较，分别取0或者1生成种群中各染色体的测量；

步骤4)对每一条染色体的测量，将染色体基因的多位二进制表示转化为十进制数值，得到对应传感器节点的主感知方向集合，计算在该主感知方向集合下有效监测区域的平均覆盖度；

步骤5)判断是否迭代结束，若未结束则：获取有效监测区域的平均覆盖度最小所对应的染色体测量，该染色体对应为演化目标，采用量子动态旋转门对种群中的其它染色体进行调整，获得下一代种群；

步骤6)计算前后两代有效监测区域的平均覆盖度的最小值的差δ，若δ小于阈值表明迭代演化陷入了局部最小，对量子进行非门操作，改变0、1趋势，并返回步骤3；

多媒体传感器节点主感知方向调整：

步骤7)取有效监测区域平均覆盖度最小的染色体，逐一对该染色体中的基因比特位进行二进制到十进制的转化，并根据单次最小调整角度得到对应传感器节点的优化主感知方向；

步骤8)根据优化主感知方向调整监测区域中传感器节点的主感知方向，计算最终场景覆盖率。

以上步骤中所涉及的一些关键操作定义如下：

量子比特：量子遗传算法中，基因采用量子比特来表示，此时表达的不是一个确定的信息而是包含所有信息的可能性；对于染色体中的任意一个基因，假设染色体中包含的基因数目为k，k和监测场景中的传感器节点数目一致；设传感器节点单次调整的最小角度值为θ_min，则任一传感器其主感知方向最多的可能状态m可表示为：

则对应染色体中基因的量子比特数也为m，最终染色体对应的量子比特可表示为：

α_ij、β_ij(1≤i≤k，1≤j≤m)为2个复常数，且有下式成立：

|α_ij|²+|β_ij|²＝1

覆盖：监测场景网络中的任意一点N被多媒体传感器节点P覆盖的充分必要条件为：

(1)点N到多媒体传感器节点的距离小于传感器节点P的感知半径；

(2)点N属于传感器节点P的角度覆盖范围；

有效监测区域的平均覆盖度：监测区域中被至少一个传感器节点覆盖的点的平均覆盖度S，也即被覆盖的监测区域点平均被多少个传感器节点覆盖，其定义为：

$S=\frac{\underset{i=1}{\overset{k}{\Sigma }}{N}_j}{\underset{f=\mathrm{1,2},...,K}{\cup }{N}_f}$

其中：表示区域中实际被覆盖到的点数目，N_j反映了传感器节点的覆盖能力，表示第j个传感器节点可以覆盖到的点的数目。

染色体测量：根据染色体基因对应的每一量子比特位，采用在[0，1]中随机选择一个数，和量子比特概率幅|α_ij|²进行比较，若大于|α_ij|²则对应位取1，否则取0，生成种群中各染色体的0、1测量序列。

动态旋转门：量子遗传算法中，为实现其它染色体向目标染色体演化需要对种群中的其它染色体的量子基因比特进行旋转，旋转角度采用动态调整策略，即初始调整时的旋转角度θ_f较大，随后逐步减小，设传感器节点的单次调整的最小角度值为θ_min，最大调整角度值为θ_max，则有：

${\theta }_f=\frac{({\theta }_{\max }-{\theta }_{\min })}{f},f=\mathrm{1,2}···n$

量子非门操作：将量子编码中的α、β互换，改变0、1趋势，防止量子遗传算法未成熟收敛，提供更好的全局搜索能力。

场景覆盖率：监测场景的覆盖率等于被至少一个传感器节点覆盖的场景离散点数与监测场景的总离散点数的比值。

有益效果

使用基于动态旋转门的量子遗传算法实现无线多媒体传感器网络的覆盖增强，对应实现方案有如下优点：

1.求解速度快

传感器节点主感知方向的调整受相邻节点感知方向的相互制约，因而主感知方向的调整是一个NP-Hard问题。已有的增强方法，如基于势场的方法直接求解时间复杂度较高，和传感器网络能量受限和计算能力不足相矛盾。量子遗传算法作为一类新颖的智能演化算法，具有收敛速度快、计算时间短等优点，很好地适应了传感器节点能量受限的特点。

2.较好的适应性

量子遗传算法用于传感器网络的覆盖增强中，其主要参数，如染色体的基因数、基因的量子比特位数均基于传感器网络节点的基本参数而设置，减少了人为设置参数的随意性和不准确性，从而表现出较好的适应性。

3.具有良好的系统性能

场景中基于随机分布的传感器节点，由于节点主感知方向和节点位置随机分布，因而网络中可能存在大量的监测盲区和监测冗余区，基于量子遗传算法的无线多媒体传感器网络覆盖增强通过智能演化计算节点的全局最优主感知方向，调整传感器节点的分布，从而有效减少节点覆盖盲区和节点覆盖冗余最终实现网络的高效覆盖。

附图说明

图1是多媒体传感器节点感知模型示意图。方向可调的多媒体传感器节点感知模型采用五元组来表示，其中，P＝(x，y)为多媒体传感器节点的位置坐标；R为节点的有效感知半径；为节点的主感知方向；2α为传感器节点的最大感知角度；β为传感器节点单次调整角度范围，本专利中取β∈[1°，10°]。

图2是量子遗传算法种群中染色体示意图，其中每一条染色体中的基因数目对应为传感器节点数k，基因的量子比特数m取决于传感器节点的单次调整的最小角度值为θ_min，且有：

图3是基于量子遗传算法的无线多媒体传感器网络覆盖增强方法的详细步骤框图。

具体实施方式

基于智能演化计算的无线多媒体传感器网络覆盖增强方法实现方案的核心设计思想为：将量子遗传算法应用于无线多媒体传感器网络的覆盖增强中，针对网络覆盖增强实际需要，基于多媒体传感器节点的单次最小调整角度计算基因量子比特数；为避免角度调整过程中的迭代次数过大问题，采用基于传感器节点单次角度调整范围的动态量子旋转门策略；更进一步，为避免量子遗传算法陷入局部最优，引入相邻两代有效覆盖区域的平均覆盖度最小值之差进行判断，并采用量子非门操作策略跳出局部最优点。

因此，方案首先通过设置初始场景，并基于量子遗传算法高效搜寻节点的最优主感知方向集合，调整初始节点的主感知方向，有效消除多媒体传感器节点的感知重叠区域，最终实现监测场景的高效覆盖。主要包括：

1.初始场景设置：

首先配置监测场景及多媒体传感器节点：设置需要采用多媒体传感器网络监测的区域场景大小；初始化监测场景中无线多媒体传感器节点的数量、布撒位置、主感知方向、感知半径以及传感器节点单次调整的角度值范围；在此基础上配置量子遗传算法，具体操作包括：

1)量子遗传算法中单条染色体的构成：染色体由基因构成，面向无线多媒体传感器网络覆盖增强的量子遗传算法中，染色体的基因数由初始场景中的传感器节点数确定；

2)单个基因中的量子比特数：算法中量子比特代表了当前传感器节点的主感知方向，因此量子比特数由传感器节点的最小单次调整角度θ_min确定，设量子比特数为m，则有：

最终染色体对应的量子比特可表示为：

α_ij、β_ij(1≤i≤k，1≤j≤m)为2个复常数，且有下式成立：

|α_ij|²+|β_ij|²＝1

3)量子遗传算法中动态旋转门的确定：算法中根据传感器节点的单次调整的角度范围设定量子旋转门中的角度函数，为实现其它染色体向目标染色体演化需要对种群中的其它染色体的量子基因比特进行旋转，初始调整时的旋转角度θ_f较大，随后逐步减小。设传感器节点的单次调整的最小角度值为θ_min，最大调整角度值为θ_max，则有：

${\theta }_f=\frac{({\theta }_{\max }-{\theta }_{\min })}{f},f=\mathrm{1,2}···n$

2.多媒体传感器节点最佳主感知方向计算：

1)对于每一代种群中的测量，将染色体的基因的多位二进制表示转化为十进制数值，得到对应传感器节点的主感知方向集合，计算各染色体的适应度。其中，适应度被定义为有效监测区域的平均覆盖度，即：监测区域中被至少一个传感器节点覆盖的点的平均覆盖度S，也即被覆盖的监测区域点平均被多少个传感器节点覆盖，其定义为：

$S=\frac{\underset{i=1}{\overset{k}{\Sigma }}{N}_j}{\underset{f=\mathrm{1,2},...,K}{\cup }{N}_f}$

其中：表示区域中实际被覆盖到的点数目，N_j反映了传感器节点的覆盖能力，表示第j个传感器节点可以覆盖的点的数目。

2)判断是否迭代结束，若未结束则：取有效监测区域的平均覆盖度最小所对应的染色体测量，该染色体对应为演化目标，采用量子动态旋转门对种群中的其它染色体进行调整，获得下一代种群；

3)计算前后两代有效监测区域的平均覆盖度的最小值的差δ，若δ小于阈值表明迭代演化陷入了局部最小，对量子进行非门操作，改变0、1趋势，重新进行迭代演化；

具体步骤包括：

初始场景设置：

步骤1)配置监测场景及多媒体传感器节点：设置需要采用多媒体传感器网络监测的区域场景大小；初始化监测场景中无线多媒体传感器节点的数量、布撒位置、主感知方向、感知半径以及传感器节点单次调整的角度值范围；

步骤2)配置量子遗传算法：设定种群初始规模，即染色体数目；根据场景中初始节点的数目配置染色体的基因数；根据传感器节点的单次调整的最小角度值配置基因的量子比特数；根据传感器节点的单次调整的角度范围设定量子旋转

门中的角度函数；

多媒体传感器节点最佳主感知方向计算：

步骤3)在[0，1]中随机选择一个数，和量子遗传算法的量子比特的概率幅进行比较分别取0或者1，生成种群中各染色体的测量；

步骤4)对每一条染色体的测量，将染色体的基因的多位二进制表示转化为十进制数值，得到对应传感器节点的主感知方向集合，计算在该主感知方向集合下有效监测区域的平均覆盖度；

步骤5)判断是否迭代结束，若未结束则：取有效监测区域的平均覆盖度最小所对应的染色体测量，该染色体对应为演化目标，采用量子动态旋转门对种群中的其它染色体进行调整，获得下一代种群；

步骤6)计算前后两代有效监测区域的平均覆盖度最小值的差δ，若δ小于阈值表明迭代演化陷入了局部最小，对量子进行非门操作，改变0、1趋势，并返回步骤3；

多媒体传感器节点主感知方向调整：

步骤7)取有效监测区域平均覆盖度最小的染色体，逐一对该染色体中的基因比特位进行二进制到十进制的转化，并根据单次最小调整角度得到对应传感器节点的优化主感知方向；

步骤8)根据优化主感知方向调整监测区域中传感器节点的主感知方向，并计算最终场景覆盖率。