智能优化算法应用：基于回溯搜索算法无线传感器网络(WSN)覆盖优化 - 附代码

摘要：本文主要介绍如何用回溯搜索算法进行无线传感器网(WSN)覆盖优化。

1.无线传感网络节点模型

本文主要基于0/1模型，进行寻优。在二维平面上传感器节点的感知范围是一个以节点为圆心，半径为$R_n$的圆形区域，该圆形区域通常被称为该节点的“感知圆盘”，$R_n$称为传感器节点的感知半径，感知半径与节点内置传感器件的物理特性有关，假设节点$n$的位置坐标为$(x_n,y_n)$在0-1感知模型中，对于平面上任意一点$p(x_p,y_p)$,则节点$n$监测到区域内点$p$的事件发生概率为：
$$P_r(n,p)=\{\begin{array}{l}1,d(n,p)\le R_n\\ 0,esle\end{array}\text{\hspace{1em}(1)}$$
其中$d(n,p)=\sqrt{(x_n-x_p{)}^2+(y_n-y_p{)}^2}$为点和之间的欧式距离。

2.覆盖数学模型及分析

现假定目标监测区域为二维平面，在区域$Area$上投放同型结构传感器节点的数目为N,每个节点的位置坐标值假设已被初始化赋值，且节点的感知半径r。传感器节点集则表示为：
N o d e { x 1 , . . . , x N } (2) Node\{x_1,...,x_N\} \tag{2} Node{x1​,...,xN​}(2)
其中 n o d e i = { x i , y i , r } node_i=\{x_i,y_i,r\} nodei​={xi​,yi​,r},表示以节点$(x_i,y_i)$为圆心,r为监测半径的圆，假定监测区域$Area$被数字化离散为$m\ast n$个像素点，像素点的坐标为$(x,y)$，目标像素点与传感器节点间的距离为：
$$d(nod{e}_i,p)=\sqrt{(x_i-x{)}^2+(y_i-y{)}^2}\text{\hspace{1em}(3)}$$
目标区域内像素点被传感器节点所覆盖的事件定义为$c_i$。则该事件发生的概率$P{c}_i$即为像素点$(x,y)$被传感器节点$nod{e}_i$所覆盖的概率:
$$P_{cov}(x,y,nod{e}_i)=\{\begin{array}{l}1,ifd(nod{e}_i,p)\le r\\ 0,esle\end{array}\text{\hspace{1em}(4)}$$
我们将所有的传感器节点在目标监测环境中的区域覆盖率$CoverRatio$定义为传感器节点集的覆盖面积与监测区域的面积之比，如公式所示：
$$CoverRatio=\frac{\sum P_{cov}}{m\ast n}\text{\hspace{1em}(5)}$$
那我们的最终目标就是找到一组节点使得覆盖率最大。

3.回溯搜索算法

回溯搜索算法原理请参考：https://blog.csdn.net/u011835903/article/details/108366901
该算法是寻找最小值。于是适应度函数定义为未覆盖率最小，即覆盖率最大。如下：
$$fun=argmin(1-CoverRatio)=argmin(1-\frac{\sum P_{cov}}{m\ast n})\text{\hspace{1em}(6)}$$

4.实验参数设定

无线传感器覆盖参数设定如下：

%% 设定WNS覆盖参数,
%% 默认输入参数都是整数，如果想定义小数，请自行乘以系数变为整数再做转换。
%% 比如范围1*1，R=0.03可以转换为100*100，R=3；
%区域范围为AreaX*AreaY
AreaX = 100;
AreaY = 100;
N = 20 ;%覆盖节点数
R = 15;%通信半径

回溯搜索算法参数如下：

%% 设定优化参数
pop=30; % 种群数量
Max_iteration=80; %设定最大迭代次数
lb = ones(1,2*N);
ub = [AreaX.*ones(1,N),AreaY.*ones(1,N)];
dim = 2*N;%维度为2N，N个坐标点

5.算法结果

从结果来看，覆盖率在优化过程中不断上升，表明回溯搜索算法对覆盖优化起到了优化的作用。

6.参考文献

[1] 史朝亚. 基于PSO算法无线传感器网络覆盖优化的研究[D]. 南京理工大学.

7.MATLAB代码