一种面向区域监测的无线传感器网络节点布设的优化方法

摘要

本发明公开了一种面向区域监测的无线传感器网络节点布设的优化方法。包括：首先对包含障碍区和热区的无线传感器网络监测范围进行网格化，根据节点检测模型和对各不同类型区域的覆盖要求，建立待优化的目标函数，使用粒子群优化算法来求解最佳的节点布设位置集合，并结合布设问题的特点设计了最好－最坏变异和弹性势能变异两种变异算子，以加快粒子群优化算法的收敛速度，最后，利用匈牙利算法得到节点初始布设位置集合与优化布设位置集合的最佳一一映射关系，使节点移动到优化布设位置所消耗的总能量最少。通过本发明，可以高效地解决无线传感器网络节点布设优化所面临的高维优化问题，从目标检测功能的角度来提高监测区域的覆盖率。

说明书

技术领域

本发明涉及一种面向区域监测的无线传感器网络节点布设的优化方法，特别适用于无线传感器网络目标检测应用。

背景技术

随着传感器技术、无线通信技术、嵌入式计算技术、分布式信息处理技术的飞速发展和日益成熟，具有感知能力、计算能力和通信能力的微型传感器网络开始大范围出现。其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者，主要应用于军事场景、目标跟踪、环境检测以及空间探索等。对于无线传感器网络的诸多应用，由于传感器节点众多或者需要监测的区域的不可达性，往往采用飞机空投、大炮投射等方式进行节点随机的布设。考虑到每个传感器的目标检测范围有限，这类随机布设方式很难保证监测区域被有效覆盖，尤其是大量节点落在一个较小的区域内时，会使其他区域处于传感器检测覆盖范围之外，导致出现功能盲区。因此，如何改善传感器的布设性能，有效利用各传感器的检测能力一直是无线传感器网络基础支撑技术的热点研究问题。

研究人员尝试在采用空投等方式随机布设传感器节点后，通过一次性调整传感器的位置，达到改善覆盖性能的目的。传感器具有一次的跳跃能力来改变其初始位置，然后处于静止工作状态。典型的算法有Yi Zou提出的虚拟力算法(VFA)[Yi Zou，Krishnendu Chakrabarty，“Sensor deployment and targetlocalization based on virtual forces，”Proc.IEEE Infocom Conference，vol.2，pp.1293-1303，2003]，该算法假定传感器之间、传感器和障碍物之间、传感器和热区之间都具有引力或斥力的作用，而传感器在上述各种力的合力作用下不断虚拟的调整自身位置，直到各传感器受力达到平衡，再让传感器直接移动到最终选择的位置上。VFA算法的缺点是并不能保证整个布设调整过程是朝着优化的方向进行的，也不能保证具有收敛性，实际可操作性甚差。一些全局优化算法，如遗传算法、粒子群优化算法也用来求解该问题[Xiaoling Wu，Lei Shu，Jie Yang，et al，“Swarm based sensor deployment optimization in ad hocsensor networks，”ICESS 2005，LNCS 3820，PP.533-541，2005]，将对监测区域的覆盖建模为待优化的目标函数，希望找到一组最佳的节点位置集合使得监测区域到达最佳的覆盖，但是面临传感器节点数众多的高维优化问题，这些算法普遍存在搜索效率低、容易陷入局部极值等问题，甚至根本无法使用。

发明内容

为解决上述所存在的问题与缺陷，本发明提供了一种高效的面向区域监测的无线传感器网络节点布设的优化方法。

本发明提供的优化方法的构思是每个传感器具有一定的检测范围，传感器被空投等形式初始布设后，能跳动一次来调整初始布设位置，改善整个网络对区域的检测覆盖水平，以有效检测覆盖率和节点跳动能耗为指标来实现布设优化，具体包括以下步骤内容：

a、根据传感器节点检测模型和对各不同区域的覆盖要求，对面向区域监测的布设优化目标函数进行建模；

b、使用带有最好-最坏变异算子或/和弹性势能变异算子的粒子群优化算法对区域覆盖优化目标函数进行优化求解；

c、使用匈牙利算法得到节点初始位置集合与优化位置集合的最佳一一映射关系，使节点从初始位置移动到优化位置的总能耗最小。

所述的步骤a进一步包含如下步骤：

①以空投等形式将N个传感器节点随机布撒在监测区域内，得到传感器的初始位置集合$P_{\mathrm{init}}=\{P_{\mathrm{init}}^1,P_{\mathrm{init}}^2,L,P_{\mathrm{init}}^i,L,P_{\mathrm{init}}^N\},$其中$P_{\mathrm{init}}^i=[x_{\mathrm{init}}^i,y_{\mathrm{init}}^i]$为第i个传感器的初始布设位置。假设每个传感器的检测面积为A_s，监测区域的总面积为A，在传感器节点的个数N可以由下式确定：

$N=\frac{A}{A_s}(1+ϵ)---\left(1\right)$

其中ε为考虑到各传感器检测区域的交叠而设置的冗余节点百分比，一般取值在[0，1]之间。

②监测区域可以由用户指定的普通区域、热区和障碍区组成，其中热区是重要监测区域，需要优先进行覆盖；障碍区是不需要覆盖的区域；普通区域是需要尽量多的被覆盖的区域。将包含障碍区和热区的监测区域使用网格化方法离散化，得到网格的端点作为检测覆盖率的考核点集合S_grid＝{S_normal，S_hot，S_obstacle}，其中S_normal为落在普通检测区域的网格端点集合，|S_normal|为S_normal所包含的点的个数；S_hot为落在热区的网格端点集合，|S_hot|为S_hot所包含的点的个数；S_obstacle为落在障碍区的网格端点集合，|S_obstacle|为S_obstacle所包含的点的个数。

③假设每个传感器的检测范围是以自身为圆心半径为r的圆盘，如果某个网格点距离任何一个传感器的距离小于r，则表示该网格点被有效覆盖。令S_normal中被有效覆盖的子集为为所包含的点的个数；S_hot中被有效覆盖的子集为为所包含的点的个数；S_obstacle中被有效覆盖的子集为为所包含的点的个数。为优先覆盖热区，回避对障碍区的覆盖，以有效利用传感器的检测范围，建立的布设优化的目标函数为：

$f\left(P\right)=\alpha (1-\frac{\left|S_{\mathrm{normal}}^{\prime }\right|}{\left|S_{\mathrm{normal}}\right|})+\beta (1-\frac{\left|S_{\mathrm{hot}}^{\prime }\right|}{\left|S_{\mathrm{hot}}\right|})+\gamma \frac{\left|S_{\mathrm{obstacle}}^{\prime }\right|}{\left|S_{\mathrm{obstacle}}\right|}---\left(2\right)$

其中0≤α，β，γ≤1分别为对普通监测区域、热区未覆盖率的加权系数和对障碍区覆盖率的加权系数，可以通过各区域的重要程度和占总的监测区域大小的比例来确定，一般取β≥γ>α。P＝{P¹，P²，L，Pⁱ，L，P^N}为节点布设位置集合，则布设优化问题就是寻找一组最优的P_opt，使得

$f\left(P_{\mathrm{opt}}\right)=\underset{P^i\in D}{\min }\left\{f\left(P\right)\right\}---\left(3\right)$

其中D表示整个二维传感器监测区域。

所述的步骤b中的最好-最坏变异算子，更进一步包含以下步骤：

1)将各个传感器节点设想为以检测距离为半径的弹性圆盘，当两个圆盘发生挤压时，将产生弹性势能。每个圆盘受到的弹性势能是所有其他圆盘对其作用之和。

2)弹性势能越大表明其对区域覆盖的贡献越小，当前最好粒子选择自身具有最大弹性势能的节点进行变异，将其随机调整到监测区域的另一位置。

使用最好-最坏变异算子或弹性势能变异算子的粒子群算法对上述布设优化的目标函数进行优化。假设当前通过粒子群算法得到的最好粒子为

$X_{\mathrm{best}}=\{x_{\mathrm{best}}^1,y_{\mathrm{best}}^1,L,x_{\mathrm{best}}^i,y_{\mathrm{best}}^i,L,x_{\mathrm{best}}^N,y_{\mathrm{best}}^N\}---\left(4\right)$

次好粒子为

$X_{\mathrm{sub}-\mathrm{best}}=\{x_{\mathrm{sub}-\mathrm{best}}^1,y_{\mathrm{sub}-\mathrm{best}}^1,L,x_{\mathrm{sub}-\mathrm{best}}^i,y_{\mathrm{sub}-\mathrm{best}}^i,L,x_{\mathrm{sub}-\mathrm{best}}^N,y_{\mathrm{sub}-\mathrm{best}}^N\}---\left(5\right)$

最坏粒子为

$X_{\mathrm{worst}}=\{x_{\mathrm{worst}}^1,y_{\mathrm{worst}}^1,L,x_{\mathrm{worst}}^i,y_{\mathrm{worst}}^i,L,x_{\mathrm{worst}}^N,y_{\mathrm{worst}}^N\}---\left(6\right)$

则算法在每个迭代步数时的变异操作具体步骤为：

a、最好-最坏变异

图2是最好-最坏变异的示意图，最好粒子首先相对于次好粒子进行变异，得到变异后粒子

$X_{\mathrm{mul}}=\{x_{\mathrm{mu}1}^1,y_{\mathrm{mu}1}^1,L,x_{\mathrm{mu}1}^i,y_{\mathrm{mu}1}^i,L,x_{\mathrm{mu}1}^N,y_{\mathrm{mu}1}^N\}---\left(7\right)$

其中

$x_{\mathrm{mu}1}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{sub}-\mathrm{best}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{sub}-\mathrm{best}}^i)}^2}\cos {\theta }_i---\left(8\right)$

$y_{\mathrm{mu}1}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{sub}-\mathrm{best}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{sub}-\mathrm{best}}^i)}^2}\sin {\theta }_i---\left(9\right)$

η为[0，1]区间的随机数，θ_i为[0，2π)区间内随机选择的角度值。

最好粒子再相对于最坏粒子进行变异，得到变异后粒子

$X_{\mathrm{mu}2}=\{x_{\mathrm{mu}2}^1,y_{\mathrm{mu}2}^1,L,x_{\mathrm{mu}2}^i,y_{\mathrm{mu}2}^i,L,x_{\mathrm{mu}2}^N,y_{\mathrm{mu}2}^N\}---\left(10\right)$

其中

$x_{\mathrm{mu}2}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{worst}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{worst}}^i)}^2}\cos {\theta }_i---\left(11\right)$

$y_{\mathrm{mu}2}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{worst}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{worst}}^i)}^2}\sin {\theta }_i---\left(12\right)$

η为[0，1]区间的随机数，θ_i为[0，2π)区间内随机选择的角度值。

如果X_mu1或X_mu2的目标函数值比X_best小，则用其代替当前的X_best作为最好的粒子。

b、弹性势能变异

将各个传感器节点想象成为以自身为圆心半径为r的圆盘，当两个圆盘发生挤压时，将产生弹性势能，如图3所示。第i个圆盘和第j个圆盘之间的嵌入深度为：

　　　　　　　　　　　　　　　　　　　　　　　　　(13)

根据弹性力学，两光滑弹性物体之间的挤压弹性势能正比于它们之间互相嵌入深度的平方。则可以用来表征第i个圆盘与第j个之间的挤压弹性势能，

$U_{\mathrm{ij}}=d_{\mathrm{ij}}^2,$i，j＝1，2，L，N，i≠j　　　　　　(14)

则第i个圆盘具有的总的挤压弹性势能为

$U_i=\underset{j=1,j\ne i}{\overset{N}{\Sigma }}{d}_{\mathrm{ij}}^2,i=\mathrm{1,2},L,N---\left(15\right)$

最好粒子X_best从N个圆盘中选择具有最大的总的挤压弹性势能的圆盘i^*进行变异，将其圆心位置由原来的随机改变为监测区域内的另一位置其他圆盘位置保持不变，由此得到变异后的粒子X_mu。如果X_mu的目标函数值比X_best小，则用其代替当前的X_best作为最好的粒子。

最后，建立由带变异算子的粒子群优化算法得到的优化节点布设位置集合P_opt与初始位置集合P_init的最佳映射关系。

节点消耗的能量与其跳动的距离成正比，则求P_init与P_opt的最佳映射关系即是求：

$a^{*}=\underset{a\in {\Pi }_N}{\min }\left\{E_{\mathrm{con}}\right\}=\underset{a\in {\Pi }_N}{\min }\left\{\underset{i=1}{\overset{N}{\Sigma }}{d}_{i,a\left(i\right)}\right\}---\left(16\right)$

其中П_N为数组N＝{1，2，L，N}的所有排列组合的集合；a为П_N中的任意一种排列组合，a(i)为排列组合的第i个元素；d_i，a(i)为第i个传感器从初始布设位置分配到第a(i)个优化布设位置时需要跳动的距离。以上问题被建模为二分图的最佳匹配问题，使用匈牙利算法能较快速的得到最佳映射。

本发明的优点及有益效果是：

提供了一种有效的途径，来优化利用飞机空投等方式随机布设的无线传感器网络节点的初始布局，满足热区、障碍区及普通区域的不同覆盖要求。利用网格化方法建立待优化的目标函数，并使用带有最好-最坏变异算子和弹性势能变异算子的粒子群优化算法获得了较快的收敛速率和优化性能。匈牙利算法高效地得到初始节点布设集合和优化节点布设集合之间的最优映射关系，使节点跳动的总能耗最小。

附图说明

图1本发明所述面向区域监测的无线传感器网络节点布设优化方法流程图；

图2本发明中粒子群优化算法的最好-最坏变异算子示意图；

图3本发明中粒子群优化算法的弹性势能变异算子中弹性势能示意图；

图4本发明实施例得到传感器节点布设优化前、后的监测区域覆盖效果图，

(a)传感器节点布设优化前的监测区域初始覆盖效果图；

(b)传感器节点布设优化后的监测区域覆盖效果图；

图5本发明实施例得到的节点初始布设位置集合与优化位置集合映射图；

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式进行详细描述。

假设监测区域为50m×50m的矩形区域，监测区域内包含一个10m×10m的热区和一个10m×10m的障碍区。每个传感器的检测范围是以自身为圆心，半径为r＝5m的圆盘。本实施例应用于面向区域监测应用的无线传感器网络节点布设阶段，如图1所示，其具体包含如下步骤：

1)确定待布设的传感器个数N。本实施例中取ε＝0.25，由

$N=\frac{A}{A_s}(1+ϵ)$

得到N≈40。将40个传感器以空投等方式随机布撒到监测区域内，得到传感器的初始位置集合P_init。

2)使用网格化方法将包含障碍区和热区的监测区域离散化。得到网格的端点作为检测覆盖率的考核点集合S_grid＝{S_normal，S_hot，S_obstacle}，其中S_normal为落在普通检测区域的网格端点集合，|S_normal|为S_normal所包含的点的个数；S_hot为落在热区的网格端点集合，|S_hot|为S_hot所包含的点的个数；S_obstacle为落在障碍区的网格端点集合，|S_obstacle|为S_obstacle所包含的点的个数。

3)建立待优化的目标函数。令S_normal中被有效覆盖的子集为为所包含的点的个数；S_hot中被有效覆盖的子集为为所包含的点的个数；S_obstacle中被有效覆盖的子集为为所包含的点的个数。建立的布设优化的目标函数为：

$f\left(P\right)=\alpha (1-\frac{\left|S_{\mathrm{normal}}^{\prime }\right|}{\left|S_{\mathrm{normal}}\right|})+\beta (1-\frac{\left|S_{\mathrm{hot}}^{\prime }\right|}{\left|S_{\mathrm{hot}}\right|})+\gamma \frac{\left|S_{\mathrm{obstacle}}^{\prime }\right|}{\left|S_{\mathrm{obstacle}}\right|}$

其中0≤α，β，γ≤1分别为对普通监测区域、热区未覆盖率的加权系数和对障碍区覆盖率的加权系数，可以通过各区域的重要程度和占总的监测区域大小的比例来确定，一般取β≥γ>α。本实施例中取α＝0.3，β＝γ＝0.7。

4)使用带有最好-最坏变异算子或/和弹性势能变异算子的粒子群优化算法求解优化的节点布设位置集合P_opt。在粒子群算法的每一个迭代步内，进行如下变异操作：

a、最好-最坏变异

最好粒子首先相对于次好粒子进行变异，得到变异后粒子

$X_{\mathrm{mul}}=\{x_{\mathrm{mu}1}^1,y_{\mathrm{mu}1}^1,L,x_{\mathrm{mu}1}^i,y_{\mathrm{mu}1}^i,L,x_{\mathrm{mu}1}^N,y_{\mathrm{mu}1}^N\}$

其中

$x_{\mathrm{mu}1}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{sub}-\mathrm{best}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{sub}-\mathrm{best}}^i)}^2}\cos {\theta }_i$

$y_{\mathrm{mu}1}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{sub}-\mathrm{best}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{sub}-\mathrm{best}}^i)}^2}\sin {\theta }_i$

η为[0，1]区间的随机数，θ_i为[0，2π)区间内随机选择的角度值。

最好粒子再相对于最坏粒子进行变异，得到变异后粒子

$X_{\mathrm{mu}2}=\{x_{\mathrm{mu}2}^1,y_{\mathrm{mu}2}^1,L,x_{\mathrm{mu}2}^i,y_{\mathrm{mu}2}^i,L,x_{\mathrm{mu}2}^N,y_{\mathrm{mu}2}^N\}$

其中

$x_{\mathrm{mu}2}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{worst}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{worst}}^i)}^2}\cos {\theta }_i$

$y_{\mathrm{mu}2}^i=\eta \sqrt{{(x_{\mathrm{best}}^i-x_{\mathrm{worst}}^i)}^2+{(y_{\mathrm{best}}^i-y_{\mathrm{worst}}^i)}^2}\sin {\theta }_i$

η为[0，1]区间的随机数，θ_i为[0，2π)区间内随机选择的角度值。

如果X_mu1或X_mu2的目标函数值比X_best小，则用其代替当前的X_best作为最好的粒子。

b、弹性势能变异

计算第i个圆盘和第j个圆盘之间的嵌入深度为：

用来表征第i个圆盘与第j个之间的挤压弹性势能，

$U_{\mathrm{ij}}=d_{\mathrm{ij}}^2,i,j=\mathrm{1,2},L,N,i\ne j$

计算第i个圆盘具有的总的挤压弹性势能为

$U_i=\underset{j=1,j\ne i}{\overset{N}{\Sigma }}{d}_{\mathrm{ij}}^2,i=\mathrm{1,2},L,N$

最好粒子X_best从N个圆盘中选择具有最大的总的挤压弹性势能的圆盘i^*进行变异，将其圆心位置由原来的随机改变为监测区域内的另一位置其他圆盘位置保持不变，由此得到变异后的粒子X_mu。如果X_mu的目标函数值比X_best小，则用其代替当前的X_best作为最好的粒子。

5)将P_init到P_opt的最佳映射关系建模为二分图最佳匹配问题，

$a^{*}=\underset{a\in {\Pi }_N}{\min }\left\{E_{\mathrm{con}}\right\}=\underset{a\in {\Pi }_N}{\min }\left\{\underset{i=1}{\overset{N}{\Sigma }}{d}_{i,a\left(i\right)}\right\}$

其中П_N为数组N＝{1，2，L，N}的所有排列组合的集合；a为П_N中的任意一种排列组合，a(i)为排列组合的第i个元素；d_i，a(i)为第i个传感器从初始布设位置分配到第a(i)个优化布设位置时需要跳动的距离。使用匈牙利算法对上述问题求解。

对本发明上述实施例，我们利用Matlab进行性能仿真，得到的结果如图4和图5所示。

图4中实线圆圈表示单个传感器的检测范围，圆心表示传感器的位置。图4(a)显示了初始的随机布设的传感器节点对监测区域的覆盖情况，大量需要覆盖的热区和一般区域没有被覆盖，而障碍区却被多个节点覆盖，造成了检测资源的浪费，此时的目标函数值为f(P)＝0.8477；图4(b)显示了经过本发明提出的优化算法对布设位置进行优化后，在第167次迭代时传感器节点对监测区域的覆盖情况，传感器节点几乎完全覆盖了热区，在一般区域内的分布也较均匀，同时避免了对障碍区的覆盖，此时的目标函数值为f(P)＝0.023654。从图4可以看出，本发明基于网格点所建立的包含热区和障碍区的监测区域节点布设目标函数很好的表征了区域的覆盖要求，带有最好-最坏变异算子和弹性势能变异算子的粒子群优化算法能在较少的迭代步数内获得很好的布设位置优化结果。

从图5可以看出，将节点初始布设位置集合与优化布设位置集合的映射关系建模为求二分图最佳匹配问题，利用匈牙利算法可以快速得到最优的映射关系，使节点从初始布设位置移动到优化布设位置所消耗的能量E_con达到最小值，具有较强的实用性。

以上描述仅为本发明的一个典型实施例，本发明的应用范围包括各种类型的传感器节点应用于任意形状的监测区域的场合。本发明的保护范围并非局限于上述具体实施例，凡本领域技术人员根据本发明所做出的显而易见的改动均在本发明的保护范围内。