一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法

摘要

本发明提出一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法，首先，以无线传感网络中的传感器节点的利用率和网络有效覆盖率作为优化目标，建立相应的数学模型；然后，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局；最后，通过萤火虫算法对传感器节点进行自适应动态部署。本发明在延长无线传感网络寿命的同时有效提高了网络覆盖效率。

权利要求

1.一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法，其特征在于，首先，以无线传感网络中的传感器节点的利用率和网络有效覆盖率作为优化目标，建立相应的数学模型；然后，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局；最后，通过萤火虫算法对传感器节点进行自适应动态部署；

所述数学模型包括传感器节点感知概率模型、传感器节点的区域覆盖率和覆盖优化问题中的适应度函数；

所述感知概率模型如下式所示；

其中，P(ci,g)为第i个传感器节点ci对目标g的感知概率， 为传感器节点ci与目标g之间的距离，r为传感器节点ci所能够覆盖范围的半径，re为传感器节点ci感知的不确定性误差量度，且re≤r，α的值通常取 λ和β分别是感知范围为r-re和r+re时的感知质量衰减系数，σ为各种干扰，是一个服从正态分布的随机数；

所述传感器节点的区域覆盖率R(C)如下式所示：

其中，n为布置在监测区域内的无线传感器节点个数，i≤n；C为无线传感器节点集合，且C＝{c1,c2,…,cn}，ci＝{xi,xj,r}，表示传感器节点ci以坐标{xi,xj}为圆心，覆盖范围半径为r的圆；假设监测区域被数字离散化成m×n个像素点，m，n代表像素点个数，每个像素点的面积大小为Δx×Δy，用传感器节点集合的覆盖率p(x,y,ci)来表示每个像素点是否被无线传感器网络节点覆盖；

所述覆盖优化问题中的适应度函数如下所示；

F(x)＝ω1×f1(x)+ω2×(1-f2(x))

其中，f1(x)表示无线传感器节点利用率，f2(x)表示无线传感网络覆盖率，即f2(x)＝R(C)，|c|为无线传感网络中部署的传感器节点总数，|ci|为处于工作状态的传感器节点数,ω1+ω2＝1,ω1,ω2分别为对应函数的权重，取值取决于对网络综合性能的要求。

2.如权利要求1所述无线传感网络覆盖优化方法，其特征在于，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局的方法为：

2.1计算两个传感器节点之间的虚拟力Fij，计算方法如下式所示，其中，aij为其中一个传感器节点si到另一个传感器节点sj的矢量角度；dij表示其中一个传感器节点si到另一个传感器节点sj的距离，dth为调整传感器节点间相互作用力属性的距离阈值；c是距离的临界值，c设为2倍的dth；ωa和ωr分别表示引力系数和斥力系数，作为调节虚拟力调节节点疏密的依据；

2.2计算出传感器节点受到的合力Fi，计算方法如下式所示，

其中，Fo为障碍物对传感器节点si的作用力，Fr为热点区域对传感器节点si的作用力；

2.3更新传感器节点的位置，位置更新方法如下所示：

其中，(xold,yold)为更新前的位置，(xnew,ynew)为更新后的位置，Fix和Fiy分别为虚拟力合力Fi的x轴分量和y轴分量，Maxstep为进行感知的传感器节点的最大可移动距离。

3.如权利要求2所述无线传感网络覆盖优化方法，其特征在于，通过萤火虫算法对传感器节点进行自适应动态部署的方法为：

3.1将每个传感器节点看成一个萤火虫，形成萤火虫群，赋予抛洒节点中每个传感器节点相同的荧光素浓度；

3.2更新传感器节点荧光素浓度；

3.3传感器节点根据移动概率向比自己荧光素浓度高的相邻节点方向移动；

3.4更新传感器节点移动后的位置；

3.5更新萤火虫相邻决策域半径。

说明书

一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法

技术领域

[0001] 本发明属于无线传感器网络技术领域，具体涉及一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法。

背景技术

[0002] 随着信息技术的高速发展，掌握即时有效的信息对人们有着至关重要的作用。因而收集信息与数据的手段和技术得到了广泛的开发与应用，很多新兴的信息收集技术与策略也随之诞生。无线传感器网络就是当前最为热门的数据收集技术之一。无线传感器网络具有诸多优点，例如能量消耗低、易于分布在任何环境中、造价成本低廉、可以自组织地形成无线网络等特点，使无线信息感知与采集变得空前的简单与方便。因此，无线传感器网络在现实生活中得到了广泛的应用，如在气温、压力、定位等方面对周围环境的检测有着很高的应用前景，无线传感器网络中的数据收集也成为当下研究的热门。

[0003] 构建无线传感器网络过程中，合理地部署无线传感器节点能够提高无线传感器监测网络的有效覆盖面积。而在大规模传感器节点部署中，通过随机抛撒等手段得到的传感器节点部署的覆盖效果具有不确定性。为了实现对无线传感器节点部署的优化，近年来，有技术将智能优化算法引入到无线传感器节点部署的优化之中，优化的目标是提高整体无线传感器网络对监测区域的有效覆盖，延长无线传感器网络的监测时间。通常以提高覆盖面积比例或覆盖的网格比例(网格比例指将监测区域离散成网格形式)为目标进行部署优化，尽可能减少盲区和重复覆盖面积。但这种技术存在传感器节点冗余，导致网络寿命短、覆盖效率不高的缺点。

发明内容

[0004] 本发明的目的在于提出一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法，在延长无线传感网络寿命的同时有效提高了网络覆盖效率。

[0005] 为了解决上述技术问题，本发明提供一种基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法，首先，以无线传感网络中的传感器节点的利用率和网络有效覆盖率作为优化目标，建立相应的数学模型；然后，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局；最后，通过萤火虫算法对传感器节点进行自适应动态部署。

[0006] 进一步，所述数学模型包括传感器节点感知概率模型、传感器节点的区域覆盖率和覆盖优化问题中的适应度函数；

[0007] 所述感知概率模型如下式所示；

[0008]

[0009] 其中，P(ci,g)为第i个传感器节点ci对目标g的感知概率， 为传感器节点ci与目标g之间的距离，r为传感器节点ci所能够覆盖范围的半径，re为传感器节点ci感知的不确定性误差量度，且re≤r，α的值通常取 λ和β分别是感知范围为r-re和r+re时的感知质量衰减系数，σ为各种干扰，是一个服从正态分布的随机数；

[0010] 所述传感器节点的区域覆盖率R(C)如下式所示：

[0011]

[0012] 其中，n为布置在监测区域内的无线传感器节点个数，i≤n；C为无线传感器节点集合，且C＝{c1,c2,…,cn}，ci＝{xi,xj,r}，表示传感器节点ci以坐标{xi,xj}为圆心，覆盖范围半径为r的圆；假设监测区域被数字离散化成m×n个像素点，m，n代表像素点个数，每个像素点的面积大小为Δx×Δy，用传感器节点集合的覆盖率p(x,y,ci)来表示每个像素点是否被无线传感器网络节点覆盖；

[0013] 所述覆盖优化问题中的适应度函数如下所示；

[0014] F(x)＝ω1×f1(x)+ω2×(1-f2(x))

[0015]

[0016]

[0017] 其中，f1(x)表示无线传感器节点利用率，f2(x)表示无线传感网络覆盖率，即f2(x)＝R(C)，|c|为无线传感网络中部署的传感器节点总数，|ci|为处于工作状态的传感器节点数,ω1+ω2＝1,ω1,ω2分别为对应函数的权重，取值取决于对网络综合性能的要求。

[0018] 进一步，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局的方法为：

[0019] 3.1计算两个传感器节点之间的虚拟力Fij，计算方法如下式所示，[0020]

[0021] 其中，aij为其中一个传感器节点si到另一个传感器节点sj的矢量角度；dij表示其中一个传感器节点si到另一个传感器节点sj的距离，dth为调整传感器节点间相互作用力属性的距离阈值；c是距离的临界值，c设为2倍的dth；ωa和ωr分别表示引力系数和斥力系数，作为调节虚拟力调节节点疏密的依据；

[0022] 3.2计算出传感器节点受到的合力Fi，计算方法如下式所示，

[0023]

[0024] 其中，Fo为障碍物对传感器节点si的作用力，Fr为热点区域对传感器节点si的作用力；

[0025] 3.3更新传感器节点的位置，位置更新方法如下所示：

[0026]

[0027] 其中，(xold,yold)为更新前的位置，(xnew,ynew)为更新后的位置，Fix和Fiy分别为虚拟力合力Fi的x轴分量和y轴分量，Maxstep为进行感知的传感器节点的最大可移动距离。

[0028] 进一步，通过萤火虫算法对传感器节点进行自适应动态部署的方法为：

[0029] 4.1将每个传感器节点看成一个萤火虫，形成萤火虫群，赋予抛洒节点中每个传感器节点相同的荧光素浓度；

[0030] 4.2更新传感器节点荧光素浓度；

[0031] 4.3传感器节点根据移动概率向比自己荧光素浓度高的相邻节点方向移动；

[0032] 4.4更新传感器节点移动后的位置；

[0033] 4.5更新萤火虫相邻决策域半径。

[0034] 本发明与现有技术相比，其显著优点在于，建立了改进的异构节点概率感知模型和目标优化函数，然后采用虚拟力算法在虚拟力的作用下引导节点移动进行初始部署，为了进一步提高网络的覆盖率和部署的效率，采用萤火虫算法实现对节点部署的寻优，提高了无线传感器网络节点的覆盖率，减少了传感器节点冗余，有效降低了网络成本，网络生存时间得到了延长。

附图说明

[0035] 图1是用虚拟力合力进行传感器节点的初始布局后的无线传感器网络模拟图；

[0036] 图2是在图1的基础上用萤火虫算法进行自适应地动态部署后的无线传感器网络模拟图；

[0037] 图3是本发明方法具体流程图。

具体实施方式

[0038] 容易理解，依据本发明的技术方案，在不变更本发明的实质精神的情况下，本领域的一般技术人员可以想象出本发基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法的多种实施方式。因此，以下具体实施方式和附图仅是对本发明的技术方案的示例性说明，而不应当视为本发明的全部或者视为对本发明技术方案的限制或限定。

[0039] 本发明所述基于虚拟力和萤火虫算法的无线传感网络覆盖优化方法方法，首先，以无线传感网络中的传感器节点的利用率和网络有效覆盖率作为优化目标，建立相应的数学模型；然后，根据传感器节点之间的虚拟力合力进行传感器节点的初始布局，使得传感器节点能较为均匀地覆盖在无线传感网络区域中；最后，通过萤火虫算法对传感器节点进行自适应动态部署。具体包括：

[0040] 步骤一、数学模型建立

[0041] 1.1确定传感器节点感知概率模型

[0042] 鉴于在实际的无线传感网络监测区域中经常会出现电磁扰动和背景噪声干扰等因素，同时考虑到传感器节点的剩余能量对传感器节点的感知能力也具有影响，因此，本发明在传统的感知概率模型的基础上，加入上述因素。设用 作为第i个传感器节点ci对目标g的感知概率，则感知概率模型如下式所示；

[0043]

[0044] 感知概率模型中， 为传感器节点ci与目标g之间的距离，r表示传感器节点ci所能够覆盖范围的半径，re为传感器节点ci感知的不确定性误差量度且re≤r,α的值通常取λ和β分别是感知范围为r-re和r+re时的感知质量衰减系数,σ为各种干扰，是一个服从正态分布的随机数。

[0045] 1.2计算传感器节点的区域覆盖率

[0046] 假设无线传感网络监测区域是一个二维平面，在监测区域内布置了n个无线传感器节点，i≤n，无线传感器节点集合为C＝{c1,c2,…,cn}，其中ci＝{xi,xj,r}，表示传感器节点ci以坐标{xi,xj}为圆心,覆盖范围半径为r的圆。假设监测区域被数字离散化成m×n个像素点，m和n代表像素点个数，每个像素点的面积大小为Δx×Δy，用传感器节点集合的覆盖率p(x,y,ci)来表示每个像素点是否被无线传感器网络节点覆盖，则整个无线传感网络监测区域的覆盖率R(C)为节点集的覆盖面积 与监控区域的总面积m×n之比，覆盖率R(C)的表达式如下式所示：

[0047]

[0048] 1.3确定覆盖优化问题中的适应度函数

[0049] 在无线传感器网络覆盖优化问题中，要满足两个条件：第一个条件是，要使无线传感器网络的覆盖率最大化；第二个条件是，要使传感器节点得到最大限度的利用，即使传感器节点的利用率最大化。适应度函数可以描述如下；

[0050] F(x)＝ω1×f1(x)+ω2×(1-f2(x))

[0051]

[0052]

[0053] 其中，f1(x)表示无线传感器节点利用率，f2(x)表示无线传感网络覆盖率，即f2(x)＝R(C)，|c|为无线传感网络中部署的传感器节点总数，|ci|为处于工作状态的传感器节点数,ω1+ω2＝1,ω1,ω2分别为对应函数的权重，取值取决于对网络综合性能的要求。

[0054] 步骤二、引入虚拟力算法，对传感器节点进行初始布置

[0055] 2.1计算两个传感器节点之间的虚拟力。在无线传感网络中，可以通过判断传感器节点 与 之间的距离、阈值以及通信半径之间的关系来确定传感器节点之间是引力还是斥力，两个传感器节点 和 之间的虚拟力Fij可以根据下式计算：

[0056]

[0057] 其中，aij为传感器节点si到sj的矢量角度，dij表示节点si和sj的距离、dth为调整移动节点间相互作用力属性的距离阈值，c是距离的临界值，设为2倍的dth，ωa和ωr分别表示引力系数和斥力系数，作为调节虚拟力调节节点疏密的依据。

[0058] 2.2计算出传感器节点受到的合力。对于某一传感器节点来说，除受到其它传感器节点对其的作用的虚拟力外，还受到障碍物和热点区域对该传感器节点的作用力，因此，节点 受到的虚拟力合力Fi如下式所示

[0059]

[0060] 其中，Fo为障碍物对传感器节点 的作用力，Fr为热点区域对传感器节点 的作用力。

[0061] 2.3更新传感器节点的位置。传感器节点 会在虚拟力合力Fi的作用下，从原位置(xold,yold)更新为新的位置(xnew,ynew)，位置更新过程为：

[0062]

[0063] 其中，虚拟力合力Fi的x轴分量和y轴分量分别为Fix和Fiy，Maxstep为进行感知的传感器节点的最大可移动距离。

[0064] 这样，应用虚拟力算法的传感器节点初始部署构建完成了。接下来用萤火虫算法进行自适应地动态部署，萤火虫算法过程中分为四个阶段：荧光素更新、萤火虫运动、萤火虫位置更新、萤火虫相邻半径更新。

[0065] 步骤三，通过萤火虫算法对传感器节点进行自适应动态部署

[0066] 3.1根据虚拟力的传感器节点初始部署，并将每个传感器节点看成一个萤火虫，从而形成萤火虫群；

[0067] 3.2在算法初始赋予抛洒节点中每个传感器节点相同的荧光素浓度；

[0068] 3.3更新传感器节点荧光素浓度，更新方式如下：

[0069] li(t+1)＝(1-ρ)li(t)+γF(xi(t+1))

[0070]

[0071] 其中，li(t)表示在第t次迭代时，传感器节点i的荧光素浓度，增加荧光素浓度衰减系数ρ(0＜ρ＜1)，F(xi(t+1))为节点传感器节点i在t次迭代时的目标函数值。目标函数为基于传感器节点i的坐标的函数，

[0072] 为传感器节点i和j之间的距离，j为处在传感器节点i的感知半径内也就是传感器节点i的相邻节点， 为传感器节点i在t次迭代时的相邻决策域的半径。

[0073] 3.4判断传感器节点i比自己荧光素浓度高的相邻节点，并向该相邻节点的方向移动，移动的概率由下式可得：

[0074]

[0075] 其中， k为在第t次迭代时，处在传感器节点i感知半径内且荧光素浓度低于传感器节点i的相邻节点，dik(t)为第t次迭代时，传感器节点i和k之间的距离。

[0076] 3.5更新传感器节点i，移动后的位置。

[0077]

[0078] 其中，xi(t)为传感器节点i在空间里的位置，s为位置更新的迭代步长，||xj(t)-xi(t)||为标准欧几里得距离。

[0079] 3.6传感器节点位置更新后，进行萤火虫相邻决策域半径的更新，更新方法如下：

[0080]

[0081] 其中，β是一个比例常数，rc为传感器节点的感知半径，nt是控制邻域范围内邻居萤火虫个数的参数，|Ni(t)|表示动态决策域内的萤火虫数。