改進多目標蟻獅算法的WSNs節點部署策略

張 浩，覃 濤，徐凌樺，王 霄，2，楊 靖，2

(1.貴州大學 電氣工程學院，貴州 貴陽 550025；2.貴州省互聯網+協同智能制造重點實驗室，貴州 貴陽 550025)

無線傳感器網絡(Wireless Sensor Networks，WSNs)由許多能量有限的傳感器節點組成，通過節點之間的協作，可向用戶提供精確、全面的實時監測數據。目前，無線傳感器網絡已廣泛應用于軍事、交通、環境監測等領域[1-2]，其中節點部署是影響無線傳感器網絡性能的重要環節之一，是整個網絡可靠工作的必要條件。

節點的部署屬于NP-hard完全問題，實質是一個非線性、多約束、多目標的最優化問題[3]，復雜度高不易求解，常見的求解方法有專家經驗、運籌規劃和啟發式搜索算法等。其中啟發式搜索算法在解決NP-hard問題時，具備較快的求解速度和精確度。智能算法作為一種啟發式算法，在無線傳感器網絡節點部署問題上有廣泛的應用。文獻[4]提出了一種基于快速非友配排序遺傳算法(NSGA-Ⅱ)的節點覆蓋策略，有效增加了節點的覆蓋率并降低了網絡的能耗，但算法的復雜度過高。文獻[5]利用遺傳算法實現了節點的k連通和m覆蓋，減少了節點的使用數目。文獻[6]利用和聲搜索算法實現了節點的最小代價覆蓋，將區域的覆蓋率和節點數目融合為一個目標函數，有效提高了區域的覆蓋率。文獻[7]將節點之間的連通性作為約束條件，覆蓋率作為目標函數，添加到節點的覆蓋問題中，最后利用遺傳算法去解決節點的覆蓋問題，有效提升了覆蓋率與節點間的連通性。文獻[8]提出了一種基于改進灰狼算法的無線傳感網絡節點覆蓋策略，有效提升了區域的覆蓋率。文獻[9]提出了一種基于生物地理學優化算法的無線傳感網絡覆蓋連通策略，能有效獲得位置較好的節點部署位置。

盡管上述部署策略都各有優勢，但主要集中在單目標優化、權重相加或約束化處理上。另外，將多目標問題轉化為單目標問題求解時，一般只能求取一個最優解。而基于帕累托思想的多目標求解方法，不需要通過設置權重系數將問題轉化為單目標問題，且可以同時獲取多個優化解，因此被應用在多個實際問題中[10-12]。

目前，學者已提出的多種群體智能算法，如粒子群算法(PSO)[13]、灰狼優化算法(GWO)[14]、鯨魚優化算法(WOA)[15]、麻雀優化算法(CS)[16]、蝴蝶優化算法(BOA)[17]、蟻獅算法(ALO)[18]等。其中，蟻獅算法被學者MIRJALILI在2015年提出，具備調節參數少，尋優能力強的優點；在2017年又提出了多目標蟻獅算法[19]，利用種群中個體間的支配關系尋找最優解集，并證明該算法優于一些經典多目標算法。由于該算法的優越性，被迅速應用到多個領域。文獻[20]利用蟻獅算法優化(SVR)核參數，并將其應用在鋰電池的壽命預測中，有效提高鋰離子電池剩余使用壽命預測的準確性和魯棒性。文獻[21]運用蟻獅算法求解風電集群儲能容量配置優化問題，分析了儲能電池單位成本和壽命對優化結果影響，并驗證了所提算法與模型的有效性。文獻[22]將改進后的蟻獅算法用于無人機的三維航跡中，實現了航跡問題中的在線局部重規劃。

但蟻獅算法也存在收斂精度低、易陷入局部最優的缺陷，導致在求解實際問題時容易過早收斂，不利于尋找全局最優解[23-24]。因此，筆者提出了一種改進的多目標蟻獅算法(Improved Multi-Objective Ant-Lion Optimizer，IMOALO)，首先，引入混沌初始化策略增加種群的多樣性，并提出連續自適應收縮邊界以增強算法的尋優能力；然后，利用時變策略對螞蟻位置進行擾動，以增強算法跳出局部最優的能力；最后，基于帕累托最優解集的思想，將IMOALO算法應用在節點多目標部署問題中，并通過仿真驗證了所提算法在無線傳感網絡部署應用中的有效性。

1 系統模型與問題描述

1.1 節點感知模型與連通模型

假設在面積為M×L的部署區域內，隨機拋撒n個節點，其中節點集合S={s1，s2，…，si，…，sn}，si位置坐標為(xi，yi)，i=1，2，…，n，節點的感知半徑為Rs，通信半徑為Rc。為簡化計算，將該監測區域離散化為m×l個單位正方形區域，每個子區域的中心坐標就是節點的覆蓋目標，中心點的坐標集合為Cj=(xj，yj)，j∈{1，2，…，m×l}。若中心點Cj與任意節點的距離小于或等于感知半徑Rs，則說明Cj被覆蓋。節點si與中心點Cj的間距定義為

d(si，Cj)=((xi-xj)2+(yi-yj)2)1/2。

(1)

假設節點感知模型為布爾感知模型，中心點Cj=(xj，yj)被節點si感知的概率p(si，Cj)定義為

(2)

中心點Cj被所有節點聯合感知概率定義為

(3)

若節點之間的距離小于通信半徑，則兩節點間連通，故節點si與節點si*之間的連通性p(si，si*)(i≠i*)可定義為

(4)

1.2 問題描述

節點的連通性與網絡覆蓋率是節點部署問題中兩個重要的指標。如圖1(a)所示，在網絡中存在4個節點a、b、c、d，節點a的信息可通過節點c和d傳輸至基站，但當節點c出現故障時，節點a沒有可傳輸信息至基站的路徑而導致出現信息空洞；當節點b的位置移動至b1處，如圖1(b)所示，b1處于節點a的通信半徑內，網絡中信息傳輸的路徑增加，當節點c喪失信息傳輸的功能時，節點a的信息可以通過節點b1和節點d傳輸至基站。

(a) (b)

由圖1(a)與圖1(b)的對比可知，當節點b移動至b1時，網絡中節點的連通性增強，但節點之間重疊的覆蓋區域增加，整體的區域覆蓋率下降。由此可見，網絡中的覆蓋率與連通度存在矛盾關系；此外，如果減少節點的使用數量，會導致網絡覆蓋率下降；相反地，增加節點數目，網絡可達到更高的覆蓋率。當同時考慮多種目標需求時，則屬于多目標優化問題(Multi-objective Optimization Problem，MOP)，在多目標優化問題中，多個目標可能存在著矛盾，不存在惟一的最優解；相反地，存在著多個目標折中的最優解。

1.3 部署目標

無線傳感器網絡針對不同的需求，有不同的節點部署目標，當同時考慮多個目標時，傳感器節點的部署問題實際是一個多目標優化問題，文中部署目標如下。

(1) 節點數目。由于傳感器節點成本限制，應在監測區域內部署適當數目的節點，避免出現過多的冗余節點。

(2) 區域覆蓋率。區域覆蓋率RCov為感知節點集合S所對應的聯合感知概率之和與區域內中心點總數的比值，即

(5)

為避免節點在優化時過于集中，對覆蓋率的限制條件為RCovl≤RCov≤1，其中，RCovl為最低覆蓋率。

(3)節點連通性。節點連通性是指網絡中節點一跳范圍之內能夠與其通信的相鄰節點的數量，用于描述整個網絡的通信能力。同時，節點間的通信能力也是無線傳感網絡中信息可靠傳輸的基礎。整個網絡中節點的連接數目為

(6)

節點間連通的限制條件為?i∈[1，n]，?i*∈[1，n]，i≠i*，p(si，si*)=1，可保證每個節點至少能與一個其他節點連通。

1.4 多目標部署模型

根據1.3節的描述，可將部署問題用多目標優化函數表示如下：

(7)

其中，決策空間X∈[n，(x，y)]，n為部署區域中的節點數目，(x，y)為節點的位置坐標矢量。

約束條件為

(8)

其中，F(X)是目標函數；F1(X)為未被覆蓋率，該值越小，說明網絡的覆蓋率越高；F2(X)為節點連接數目的倒數，該值越小，說明網絡中存在的連接越多，數據傳輸越穩定。約束條件要求節點部署在監測區域內，網絡覆蓋率不低于最低覆蓋率且節點至少可以與其他任意一個節點連通。

2 改進多目標蟻獅算法

2.1 Pareto優化模型

為了求解上述節點部署的多目標問題，利用帕累托解集的思想，求出問題的一組可行解，為不同的目標需求提供相應的方案，以最小化目標為例，MOP問題可表述為

minF(X)={f1(X)，…，fi(X)，…，fm(X)} ，

(9)

其中，F(X)為目標組合向量，X={x1，x2，…，xq}為MOP問題的解，q為變量的個數；fi(X)為其中一個目標函數，1≤j≤m，m為目標函數的數量。Pareto的相關定義[3]如下。

定義1帕累托支配：假設x是決策空間R內的可行解，對任意兩個決策向量x1與x2，若滿足式(10)中的關系，則說明x1可支配x2，記錄為x1?x2。

(10)

定義2帕累托非支配解：x是決策空間內的可行解，且沒有解可以支配解x，則稱x為非支配解。

定義3帕累托最優解集：由全部非支配解組成的集合。

2.2 多目標蟻獅算法

多目標蟻獅算法中包含以下幾個角色：螞蟻、蟻獅、外部存檔和精英蟻獅，主要由以下幾個步驟組成。

(1) 隨機初始化種群：

xi，j=xmin，j+rand(0，1)(xmax，j-xmin，j) ，

(11)

其中，i=1，2，…，SN，j=1，2，…，D，xmax，j和xmin，j為搜索空間的上界和下界。每個解xi，j代表一個D維向量。

(2) 螞蟻隨機游走，定義為

Xi=[0，cumsum[2r(1)-1]，…，cumsum[2r(t)-1]，…，cumsum[2r(T)-1]] ，

(12)

其中，cumsum為數值累計函數，t、T分別為當前迭代次數與最大迭代次數，r(t)是0和1間的隨機數，v為[0，1]內的隨機數，定義為

(13)

為保證螞蟻游走的路徑維持在上下界內，對其游走路徑做歸一化處理，定義為

(14)

(3) 通過輪盤賭選擇的蟻獅和上下界共同決定螞蟻的游走邊界：

(15)

(16)

(4) 在螞蟻被蟻獅捕捉過程中，若存在可支配精英蟻獅的個體，則該個體替換掉精英蟻獅：

(17)

將每一代中適應度最高的蟻獅作為精英蟻獅，并通過輪盤賭隨機選擇一只蟻獅，共同決定螞蟻的游走路徑：

(18)

(5) 重構陷阱：多目標蟻獅算法中采用一個外部存檔來存儲帕累托支配解集，為了獲得多樣性更強的解，利用小生境技術對外部存檔中解的分布進行判斷，使用

(19)

來定義在歸檔中選擇解決方案的概率，當存檔已滿時，具有最密集鄰居的解決方案將從存檔中刪除，以適應新的解決方案。使用

(20)

來定義從存檔中刪除解決方案的可能性。其中，c是一個大于1的常數，Ni是第i個解的附近解個數。在固定的半徑范圍內，解周圍的鄰居解越多，被存檔的概率越低。當存檔已滿時，解周圍存在其他解越多，被刪除的可能性越大。

2.3 改進的多目標蟻獅算法

2.3.1 混沌初始化策略

混沌具有隨機性、遍歷性的特點，混沌初始化可提高種群的多樣性，有利于算法跳出局部最優，增強全局尋優的能力。其中Fuch映射作為一種經典的混沌模型，已經被證明了優于一些經典混沌映射方法[25]，故文中選取Fuch映射去初始化種群。假設種群規模為{1，2，…，i，…，SN}，算法的空間維數為{1，2，…，j，…，D}，Fuch映射的表達式如下所示：

(21)

取Fuch混沌序列的初始值z(0)=0.47，種群的規模SN=30，空間維數D=80，將式(21)產生的混沌序列映射到求解空間后得到初始化種群，種群個體xi，j如下：

xi，j=xmin，j+|Xn+1|(xmax，j-xmin，j)，i=1，2，…，SN，j=1，2，…，D，

(22)

其中，Xn+1為混沌值，xmax，j和xmin，j為搜索空間的上界和下界。

2.3.2 基于正弦函數的邊界收縮因子I

在基本的ALO算法中，為了搜索陷阱里可能存在的解，邊界因子I隨迭代次數的增加而呈現階躍式增加，從而導致搜索的空間的收縮存在不連續性，易錯過最優解。假設搜索空間的上界ub=100，下界lb=-100，設迭代次數為100，算法中ub和lb的變化趨勢如圖2所示。

圖2 原始算法的上下界變化趨勢圖

從圖2可知，由于邊界因子I由階躍函數決定，陷阱的上下界呈現跳躍的狀態，蟻獅捕捉螞蟻過程中陷阱的收縮存在不連續性，導致算法易錯過最優解，從而陷入局部最優。考慮到原始算法中陷阱收縮的不均勻性，將邊界因子I替換為連續函數，即

I=αsin(0.5π(t/T))+β，

(23)

其中，t為當前迭代次數；T為最大迭代次數；α為系數；β為調節參數，經多次實驗后取值為0.1。

將改進后的邊界因子用于陷阱收縮中，假設搜索空間的上界ub=100，下界lb=-100，迭代次數為100，上下界的變化趨勢如圖3所示。

圖3 算法改進后的上下界變化趨勢圖

從圖3可知，由于改進后的邊界因子I是連續性增加的函數，所以上下界的變化呈現出逐步遞減的趨勢，陷阱的收縮更加平滑，有利于種群搜索的遍歷性，從而增強了算法的尋優能力。

2.3.3 時變策略

為進一步提升算法的探索能力，采用一種基于時變高斯變異的螞蟻位置擾動策略，利用高斯變異算子對螞蟻的位置進行擾動，即

aposition*=aposition[1+γG(0，1)] ，

(24)

(25)

其中，aposition*為更新后的螞蟻的位置，aposition為原始的螞蟻位置，G(0，1)為高斯變異算子，γ為時變參數，t為當前迭代次數，T為最大迭代次數。算法前期γ較大，變異尺度大，有利于算法跳出局部最優。在算法后期，由于算法基本已收斂至最優，故此時γ較小，只對螞蟻位置進行細微的擾動。

得到新的螞蟻位置以后，計算新位置所對應的適應度函數，再根據與原始螞蟻位置的帕累托支配的關系決定是否更新解的位置。改進后的算法偽代碼如下所示。

算法1IMOALO偽代碼。

參數設置：最大迭代次數為T，當前迭代次數為t，螞蟻數目為Numa，蟻獅數目為Numb，種群的維數為dim，初始外部存檔中解的個數為N，存檔中實際存在的解的個數為N1，變量上下界為ub和lb。

種群初始化：按式(21)和式(22)產生初始化種群，計算適應度值后存入Archive中，并按蟻獅間的支配關系選擇出精英蟻獅。

Whilet

For every ant

從Archive中隨機選擇一個蟻獅和精英蟻獅

按式(16)和式(23)更新c和d的值

螞蟻按式(12)和式(14)進行隨機游走

按式(18)更新螞蟻的位置aposition，并計算其適應度Fa

由式(24)干擾螞蟻的位置得到新位置aposition*，并計算其適應度Fa*

WhileFa*可支配Fa

aposition=aposition*；

End while

End for

根據支配關系更新Archive并按照擁擠度進行排序

選擇排序在第1位的蟻獅為精英蟻獅

IfN1>N

則按式(20)和輪盤賭的方式刪除多余解

End

End while 。

2.4 算法時間復雜度分析

設置目標函數的維數為m，種群個數為n，迭代次數為T，初始化種群的時間復雜度為O(2mn)，更新外部存檔Archive的時間復雜度為O(n)。若外部存檔Archive超出設定值，則需要對外部存檔Archive進行刪減，其時間復雜度為O(n2)；輪盤賭方式選擇精英蟻獅的時間復雜度為O(n)，更新螞蟻位置的時間復雜度為O(mn2)，螞蟻位置擾動的時間復雜度為O(mn)，時變策略的時間復雜度為O(mn)，故IMOALO算法的時間復雜度為

O(m，n，T)=T(O(2mn)+O(n)+O(n2)+O(n)+O(mn2)+O(mn)+O(mn))=TO(mn2) 。

由文獻[19]可知，MOALO算法的時間復雜度也為TO(mn2)。綜上，筆者提出的策略沒有增加算法的時間復雜度。

3 算法性能測試

為了檢驗改進后算法的有效性，利用多變量的雙目標函數ZDT1、ZDT2、ZDT3、ZDT4、ZDT6對算法進行測試，并與多目標算法MOALO[19]、NSGA-Ⅱ[26]、MOPSO[27]、CMOALO[28]進行對比。本實驗仿真環境為：Win10操作系統，AMD Ryzen5 2500U with Radeon Vega Mobile Gfx @2.00 GHz主頻，8 GB內存，MATLAB 2016a。

3.1 評價指標

在帕累托解集中，解集應更貼近真實的前沿面，且還應具備一定的分布性，世代距離(Generational Distance，GD)可用于評價算法的收斂性，反向世代距離(Inverted Generational Distance，IGD)可用于評價算法的收斂性及解的分布性。GD值越小，表示求得的帕累托解集越接近真實的帕累托前沿面；IGD值越小，說明獲得的帕累托前沿面的收斂性越好。

3.2 實驗結果

實驗中蟻獅的數量為30，螞蟻的數量為30，最大迭代次數為100，外部存檔Archive的大小為100，圖4～8為算法在各個多目標算法在測試函數上的分布情況。從左到右分別為NSGA-Ⅱ、MOPSO、MOALO、CMOALO、IMOALO。圖中，True PF為真實的帕累托前沿，Obtained PF為求解獲得的帕累托前沿面。

圖4 4種不同算法在ZDT1下的前沿面

圖5 4種不同算法在ZDT2下的前沿面

圖6 4種不同算法在ZDT3下的前沿面

圖7 4種不同算法在ZDT4下的前沿面

圖8 4種不同算法在ZDT6下的前沿面

由圖4～8可知，IMOALO算法在求解ZDT6時只有一個解沒有落在帕累托前沿面上，其余均落在真實的帕累托前沿面上，對比于其他幾種經典的多目標算法，IMOALO算法的收斂性和分布性均優于其他多目標算法。這表明提出的策略有效地提升了多目標蟻獅算法的性能。

為更準確地評估IMOALO的性能，將上述算法在測試函數上運行30次，得到對應的GD和IGD值，實驗結果如表1和表2所示，其中加粗的為每一列的最小值，Mean為均值，Std為標準差。

表1 4種不同算法下的IGD指標值

表2 4種不同算法下的GD指標值

由表1和表2可知，IMOALO與其他幾種多目標算法相比，具有最小的IGD和GD值，算法收斂性和解的分布性均優于所對比的算法，且對應的標準差最小，表明改進后的算法穩定性更好，相比于其他兩種多目標蟻獅算法都有較大的提升。

4 實驗仿真及結果分析

4.1 實驗參數設置

為了驗證IMOALO算法解決部署問題的有效性以及相對于其他多目標優化算法的優越性，將節點部署在面積為100 m×100 m的監測區域內，節點個數為40個，節點的感知半徑Rs為10 m，節點的通信半徑Rc為16 m。使用MOPSO、MOALO、CMOALO以及無連續性收縮性邊界的MOALO、IMOALO算法分別對1.4節中的模型進行求解，設置帕累托最優解集個數為30。

4.2 覆蓋率與連通性的Pareto前沿面

為直接反映目標函數間的博弈性和求解算法的有效性，選擇連通性和覆蓋率兩個目標函數進行試驗，其中目標函數1為區域的未被覆蓋率，目標函數2為節點之間的連接數目的倒數，結果如圖9所示。

由圖9可知，基于IMOALO算法下的解分布較為均勻，且獲得的解的數量遠多于其他幾種算法，解的分布更廣，且帕累托前沿面更靠近坐標軸，解的性能更優。將無連續性收縮邊界的MOALO算法與IMOALO算法的解對比可知，在添加收縮邊界以后，解的數量明顯增加，有效提升了算法的探索能力。總的來說，IMOALO相對于其他幾種算法有著更好的優化性能，能夠有效解決節點部署中的多目標優化問題，也進一步驗證了IMOALO算法的有效性。

圖9 不同算法的Pareto解集

表3是IMOALO算法優化得到的帕累托解集對應的目標函數值，共對應了30種不同的策略，對區域的覆蓋可達約96.52%，基本將整個區域覆蓋，最小約為44.50%；節點連接的數目最多達到250個，最少為52個，其中每一個節點都至少能與一個其他節點連通。

表3 帕累托最優解集

圖10～12是從帕累托解中選擇出來的3種典型的節點部署方案：方案1側重于整個區域的覆蓋；方案2側重于節點間的連通度，網絡中冗余度較大，適用于具有重點區域部署需求的監測環境；方案3則是在覆蓋率與連通度之間做一個折中。由此可見，基于IMOALO算法的節點部署策略能夠有效處理多目標需求下的節點部署模型，并獲取多個節點的部署方案，提供更廣的決策空間。

(a) 節點覆蓋效果圖

(a) 節點覆蓋效果圖

4.3 不同節點數目下的Pareto前沿面

為分析節點數目對區域覆蓋率與連通性的影響，以及不同節點數目下的解集分布，以便在節點數目發生變化時能進行快速決策，在相同的區域內分別部署20、25、30、35、40、45個節點。實驗結果如圖13所示。

圖13 不同節點數目下的帕累托前沿面

由圖13可知，當節點數目不同時，所提算法均能獲得數量較多的解，且解的分布較廣，隨著節點數目的遞增，帕累托前沿面呈現遞增的趨勢。但不同節點數目下的連通度和覆蓋率可能存在相等的情況，不同節點數目下的解有重疊的解。從圖中還可以看出，節點數目為40個與節點數目為45時節點的連通性度與覆蓋率相差較小，在決策時可挑選節點數目小的一組解，減少節點的使用數量，降低部署的成本。

5 結束語

筆者提出了一種基于IMOALO算法的無線傳感器網絡節點部署策略。首先，分析了節點部署中各個目標間存在的沖突，構建了節點多目標部署函數；然后，針對原始MOALO算法尋優能力不強易陷入局部最優的缺點，通過混沌初始化和連續性邊界收縮因子策略來提高算法搜索的遍歷性，添加時變機制對螞蟻位置進行擾動，以增強算法尋優能力。并與其他多目標算法在測試函數上進行測試對比，驗證了IMOALO算法的有效性；最后，將IMOALO算法應用在節點多目標部署問題中，結合帕累托前沿面的思想平衡不同目標之間的矛盾。仿真結果表明，所提算法能有效解決節點多目標部署問題，可為決策者提供多個方案，具有較好的應用價值。