一种基于改进遗传算法的无线传感器网络覆盖优化方法

本发明涉及通信技术领域，尤指一种基于改进遗传算法的无线传感器网络覆盖优化方法。

无线传感器网络(Wireless Sensor Network,WSN)由大量低成本、低功耗微型传感器节点组成，节点与节点之间通过无线通信手段进行数据信息的交换和传输，在目标领域进行信息感知、采集和处理工作，最后利用汇聚节点将数据传输到终端用户。无线传感器网络具有大规模性、自组织性和动态性等特点。在目标监控区域经常布置大量传感器节点，并且环境一般是比较荒凉的地方，不能预知传感器节点的位置，也无法预测节点之间的相互关系，当有新节点的加入或者旧节点出现问题时，传感器网络系统要能够应对面临的状况，需要自身的组织能力进行重新组合链接，通过集成电路控制系统和网络协议传递监测数据，提高信息数据的准确性和可信度，目前无线传感器网络已在较多领域有重要的作用。

由于传感器节点一般采用随机排列的方法，节点布局是随机安排的，不可能均匀分配到整个监测区域，因此部分监测不到的区域成为构建无线传感器网络的主要难题。在保证无线传感器网络服务性能的前提下，使用尽可能少的节点，确保最大的范围区域，提供准确的信息收集及目标跟踪服务的覆盖优化问题已成为无线传感器网络研究的热点问题。引入优化算法，结合移动节点，提高了覆盖率，但要求部分节点能动态移动，调整位置，对实际能量受限的无线传感器网络提出了更高的要求。

为解决覆盖率低和节点能量利用率低的问题，本发明采用改进的遗传算法，结合节点能量与覆盖率之间的网络效用，提出无线传感器网络覆盖优化方法，最终得到传感器节点覆盖方案的最优解，可有效减少网络系统的能量消耗，提高无线传感器网络生存周期和系统性能，主要包括以下步骤：

建立无线传感器网络覆盖最优化数学模型：

以较少的节点工作状态得到最大的节点集覆盖效率为目的，本发明以布尔感知模型为基础，糅合节点网络效用建立网络覆盖最优化模型。假设传感器网络是由M(m＝1,2,...,M)个传感器节点组成的连通守恒系统，布尔感知模型函数表达式为：

式中d(m,l)表示传感器m所在位置与点l的欧氏距离，B(m,l)表示传感器m对点l的感知度，ρ代表距离。当d(m,l)≤ρ时，表示传感器节点m对点l完全感知；当d(m,l)≥ρ时，表示传感器节点m对点l不能感知。该模型表示与传感器节点小于ρ范围内的任意节点都能被覆盖，反之则没有被覆盖。

如果传感器监测区域内任意一个位置都至少被节点集中任意一个节点所覆盖，也就是节点将目标区域全部覆盖。将监测区域的面积设为D，将该区域离散化为K(k＝1,2,...,K)行， N(n＝1,2,...,N)列的网格，且每小格的面积为ΔX·ΔY，传感器节点集M(m＝1,2,...,M)所覆盖的区域面积记为Dc，如下式：

由此得到节点集的覆盖率F为：

传感器网络监测目标区域里内每个节点拥有两种状态，W＝{ON,OFF}，其中{ON}表示节点的工作状态方案，{OFF}表示节点的非工作状态方案。定义节点的网络效用Um为

CGm＝ω1×URm

CAm＝(ω2×AC)+(ω3×RCm)

其中sm是节点m的方案选择；μ是效用概率；URm是没被节点m的隔壁节点覆盖的区域的概率；RCm是节点m的次区域的冗余覆盖区域的概率；AC是工作节点的能耗。ω1,ω2和ω3为系统覆盖率权重系数，满足ω1＞0,ω2＞0和ω3＞0，CGm为URm的加权值，CAm为RCm的加权值。

假设任意节点在任意方案中的效用都相同，节点选择工作的概率P为：

在保证基本覆盖率的前提下对节点成本函数中的节点数进行判定，离散型随机变量处于工作状态中的节点数为M的概率分布满足：

P(X＝Mi)＝Pi,i＝1,2,3,4,...n

P(X＝M1)＝P1

P(X＝M2)＝P2

......

P(X＝Mn)＝Pn

进行加权平均得到的数学期望：

此时数学期望表示处于工作状态的节点数的平均值。

由此构造传感器节点覆盖优化总目标为：

MaxλF+(1-λ)UmE(X)

s.t 0＜λ＜1

λ为加权因子，保证目标函数的公平性。

基于改进遗传法的网络覆盖最优化方法

遗传算法是按照进化生活过程计算最优值的方法，具有全局扫描功能。编码将解空间映射到染体编码空间，根据个体的属性编码成染体，不同的染体个体组成种，最终遗传迭代结束后的种即为可行解集，根据适应度选择出较好个体进入下一代，根据交叉和变异概率产生新的个体，决定个体的遗传与淘汰。通过这些遗传操作，个体逐渐向较好方向进化，多次迭代进化后完成对问题最优解的求解过程。因为遗传算法搜索的对象是编码集合而不是问题本身，搜索最优解的过程不受函数本身约束条件的限制。

无线传感器网络覆盖优化方法步骤如下：

步骤一：首先设置网络初始参数，如网络监测区域范围，节点数和节点初始能量等参数。并初始化遗传算法的种规模，使用二进制进行编码，节点处于工作状态ON表示为1,节点处于非工作状态OFF表示为0；

步骤二：用目标评价函数favg(X)对种个体进行评价，并显示其评价结果,其中适应度选择概率为P(X)，avg(avg＝1,2,...)表示种大小,favg(X)表示将某个体带入目标评价函数中的函数值，表示种所有个体带入目标函数后函数值之和；

步骤三：根据评价函数值结果，通过多次赌，用全部个体的选择概率来计算累计概率，然后生成随机数，通过比较得到选出优秀个体到下一代；

步骤四：利用改进公式对当前个体的交叉概率PC和变异概率Pm进行改进；选择两节点交叉方式跟单节点变异方式作用于体，选择优良解进入下一代种，以防止局部收敛；

步骤五：将当前种的结果解码带入网络节点网络效用式favg(X)中，得到此时情况下的网络效用；

步骤六：根据价值函数来判断是否已是最佳解决方案，将被评选为最有价值的个体选定为最佳解决方案，并在解码后获得最优解的判定。如果不是最优结果，则移动至步骤三，否则继续重复上述步骤；

步骤七：循环网络节点选择方案。随着网络工作时间的延长使得网络效用在某一时刻收敛于某一固定值，综合无线传感器网络覆盖率F和节点成本函数Um得到最优的无线传感器网络覆盖方案。

与现有技术相比，本发明具有以下优点：

1.为了达到对目标区域覆盖率最大的同时减少节点成本的投入，本发明将覆盖优化目标函数与节点网络效用结合，引进数学期望表达节点数，从而建立无线传感器网络覆盖最优化数学模型，保证使用尽可能少的节点确保最大的范围区域，提供准确的信息收集及目标跟踪服务的保证覆盖率的优化。

2.本发明所采用的改进遗传算法，搜索的对象是编码集合而不是问题本身，搜索最优解的过程不受函数本身约束条件的限制，易执行，可有效解决优化问题。在优化解迭代时，利用改进公式对当前个体的交叉概率和变异概率进行改进，防止因为搜索范围小导致陷入局部最优解，保证收敛速度和搜索效果的均衡，确保了系统具备很强的鲁棒性。

图1：本发明验证基于不同优化方法下的无线传感器网络覆盖优化方法对应的网络效用收敛示意图；

图2：本发明验证基于不同优化方法下的无线传感器网络覆盖优化方法对应的网络冗余覆盖率示意图；

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。本实施基于改进遗传算法的无线传感器网络覆盖优化方法，通过以下技术方案实现：

建立无线传感器网络覆盖最优化数学模型：

以较少的节点工作状态得到最大的节点集覆盖效率为目的，本发明以布尔感知模型为基础，糅合节点网络效用建立网络覆盖最优化模型。假设传感器网络是由M(m＝1,2,...,M)个传感器节点组成的连通守恒系统，布尔感知模型函数表达式为：

式中d(m,l)表示传感器m所在位置与点l的欧氏距离，B(m,l)表示传感器m对点l的感知度，ρ代表距离。当d(m,l)≤ρ时，表示传感器节点m对点l完全感知；当d(m,l)≥ρ时，表示传感器节点m对点l不能感知。该模型表示与传感器节点小于ρ范围内的任意节点都能被覆盖，反之则没有被覆盖。

如果传感器监测区域内任意一个位置都至少被节点集中任意一个节点所覆盖，也就是节点将目标区域全部覆盖。将监测区域的面积设为D，将该区域离散化为K(k＝1,2,...,K)行， N(n＝1,2,...,N)列的网格，且每小格的面积为ΔX·ΔY，传感器节点集M(m＝1,2,...,M)所覆盖的区域面积记为Dc，如下式：

由此得到节点集的覆盖率F为：

传感器网络监测目标区域里内每个节点拥有两种状态，W＝{ON,OFF}，其中{ON}表示节点的工作状态方案，{OFF}表示节点的非工作状态方案。定义节点的网络效用Um为

CGm＝ω1×URm

CAm＝(ω2×AC)+(ω3×RCm)

其中sm是节点m的方案选择；μ是效用概率；URm是没被节点m的隔壁节点覆盖的区域的概率；RCm是节点m的次区域的冗余覆盖区域的概率；AC是工作节点的能耗。ω1,ω2和ω3为系统覆盖率权重系数，满足ω1＞0,ω2＞0和ω3＞0，CGm为URm的加权值，CAm为RCm的加权值。

假设任意节点在任意方案中的效用都相同，节点选择工作的概率P为：

在保证基本覆盖率的前提下对节点成本函数中的节点数进行判定，离散型随机变量处于工作状态中的节点数为M的概率分布满足：

P(X＝Mi)＝Pi,i＝1,2,3,4,...n

P(X＝M1)＝P1

P(X＝M2)＝P2

......

P(X＝Mn)＝Pn

进行加权平均得到的数学期望：

此时数学期望表示处于工作状态的节点数的平均值。

由此构造传感器节点覆盖优化总目标为：

MaxλF+(1-λ)UmE(X)

s.t 0＜λ＜1

λ为加权因子，保证目标函数的公平性。

基于改进遗传法的网络覆盖最优化方法

遗传算法是按照进化生活过程计算最优值的方法，具有全局扫描功能。编码将解空间映射到染体编码空间，根据个体的属性编码成染体，不同的染体个体组成种，最终遗传迭代结束后的种即为可行解集，根据适应度选择出较好个体进入下一代，根据交叉和变异概率产生新的个体，决定个体的遗传与淘汰。通过这些遗传操作，个体逐渐向较好方向进化，多次迭代进化后完成对问题最优解的求解过程。因为遗传算法搜索的对象是编码集合而不是问题本身，搜索最优解的过程不受函数本身约束条件的限制。

无线传感器网络覆盖优化方法步骤如下：

步骤一：首先设置网络初始参数，如网络监测区域范围，节点数和节点初始能量等参数。并初始化遗传算法的种规模，使用二进制进行编码，节点处于工作状态ON表示为1,节点处于非工作状态OFF表示为0；

步骤二：目标评价函数favg(X)如下式：

favg(X)＝λF+(1-λ)UmE(X)

利用目标评价函数对种中的每个个体进行评价，并显示其评价结果。其适应度选择概率 P(X)表示为:

avg(avg＝1,2,...)表示一个种,favg(X)表示将某个体带入目标评价函数中的函数值，表示种所有个体带入目标函数后函数值之和；

步骤三：根据评价函数值结果，通过多次赌，用全部个体的选择概率来计算累计概率，然后生成随机数，通过比较得到选出优秀个体到下一代；

步骤四：利用公式计算对当前个体的交叉概率PC进行改进：

利用公式计算对当前个体的变异概率Pm进行改进；

式中PCmax、Pmmax分别为交叉概率和变异概率的最大值；f(x)为目标函数；favg(X)表示将某个体带入目标评价函数中的函数值，选择两节点交叉方式跟单节点变异方式作用于体，选择优良解进入下一代种，防止局部收敛；

步骤五：将当前种的结果解码带入网络节点网络效用式favg(X)中，得到此时情况下的网络效用；

步骤六：根据价值函数来判断是否已是最佳解决方案，将被评选为最有价值的个体选定为最佳解决方案，并在解码后获得最优解的判定。如果不是最优结果，则移动至步骤三，否则继续重复上述步骤；

步骤七：循环网络节点选择方案。随着网络工作时间的延长使得网络效用在某一时刻收敛于某一固定值，综合无线传感器网络覆盖率F和节点成本函数Um得到最优的无线传感器网络覆盖方案。

数值仿真

为了验证本发明方法的有效性,对本发明所提基于改进遗传算法的无线传感器网络覆盖优化方法进行仿真实验。考虑无线传感器网络用户随机均匀分布在300m*300m的监测区域内，节点初始能量为0.5，节点数为200，迭代次数设为I＝200。

将基于遗传算法(Genetic Algorithm,GA)、改进遗传算法1(Improved GeneticAlgorithm 1, IGA1)、改进遗传算法2(Improved Genetic Algorithm 2,IGA2)和本发明所提改进遗传算法 (Improved Genetic Algorithm 3,IGA3)的网络覆盖优化方法性能进行对比，其中IGA 1对应的是调整交叉概率PC，如下式：

IGA2对应的是变异概率Pm改进，如下式所示：

式中PCmax、Pmmax分别为交叉概率和变异概率的最大值；f(x)为目标函数；favg(X)表示将某个体带入目标评价函数中的函数值。本发明方法IGA 3对调整交叉概率PC和变异概率Pm按照上面两个式子进行同时改进。

图1给出了不同迭代下不同方法所对应的网络效用收敛的结果，从图中可以看出，经典GA算法对应的网络覆盖效用最小；IGA1次之；而本发明基于IGA3的网络覆盖优化方法对应的网络效用收敛最快，能量消耗最慢，这是由于本发明所提方法有效降低了节点通信能耗的能量。图2给出了不同迭代下不同方法所对应的网络冗余覆盖率，GA所对应的覆盖优化方法节点能耗最大，网络冗余覆盖率最差，而本发明所提方法IGA3对应的网络冗余覆盖率最小，这是因为选择两节点交叉方式跟单节点变异方式作用于体，增强了体的多样性，防止因为搜索范围小导致陷入局部最优解，选择优良解进入下一代种，保证收敛速度和搜索效果的均衡，有效降低了网络能耗，从而使得所提网络覆盖最优化方法具有更优的性能。