智能優化算法應用：基于廚師算法無線傳感器網絡(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?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?n}\text{\hspace{1em}(5)}$$
那我們的最終目標就是找到一組節點使得覆蓋率最大。

3.廚師算法

廚師算法原理請參考：https://blog.csdn.net/u011835903/article/details/130534839
該算法是尋找最小值。于是適應度函數定義為未覆蓋率最小，即覆蓋率最大。如下：
$$fun=argmin(1?CoverRatio)=argmin(1?\frac{\sum P_{cov}}{m?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代碼