改進多目標(biāo)蟻獅算法的WSNs節(jié)點部署策略

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

(1.貴州大學(xué) 電氣工程學(xué)院，貴州 貴陽 550025；2.貴州省互聯(lián)網(wǎng)+協(xié)同智能制造重點實驗室，貴州 貴陽 550025)

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

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

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

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

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

1 系統(tǒng)模型與問題描述

1.1 節(jié)點感知模型與連通模型

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

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

(1)

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

(2)

中心點Cj被所有節(jié)點聯(lián)合感知概率定義為

(3)

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

(4)

1.2 問題描述

節(jié)點的連通性與網(wǎng)絡(luò)覆蓋率是節(jié)點部署問題中兩個重要的指標(biāo)。如圖1(a)所示，在網(wǎng)絡(luò)中存在4個節(jié)點a、b、c、d，節(jié)點a的信息可通過節(jié)點c和d傳輸至基站，但當(dāng)節(jié)點c出現(xiàn)故障時，節(jié)點a沒有可傳輸信息至基站的路徑而導(dǎo)致出現(xiàn)信息空洞；當(dāng)節(jié)點b的位置移動至b1處，如圖1(b)所示，b1處于節(jié)點a的通信半徑內(nèi)，網(wǎng)絡(luò)中信息傳輸?shù)穆窂皆黾?，?dāng)節(jié)點c喪失信息傳輸?shù)墓δ軙r，節(jié)點a的信息可以通過節(jié)點b1和節(jié)點d傳輸至基站。

(a) (b)

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

1.3 部署目標(biāo)

無線傳感器網(wǎng)絡(luò)針對不同的需求，有不同的節(jié)點部署目標(biāo)，當(dāng)同時考慮多個目標(biāo)時，傳感器節(jié)點的部署問題實際是一個多目標(biāo)優(yōu)化問題，文中部署目標(biāo)如下。

(1) 節(jié)點數(shù)目。由于傳感器節(jié)點成本限制，應(yīng)在監(jiān)測區(qū)域內(nèi)部署適當(dāng)數(shù)目的節(jié)點，避免出現(xiàn)過多的冗余節(jié)點。

(2) 區(qū)域覆蓋率。區(qū)域覆蓋率RCov為感知節(jié)點集合S所對應(yīng)的聯(lián)合感知概率之和與區(qū)域內(nèi)中心點總數(shù)的比值，即

(5)

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

(3)節(jié)點連通性。節(jié)點連通性是指網(wǎng)絡(luò)中節(jié)點一跳范圍之內(nèi)能夠與其通信的相鄰節(jié)點的數(shù)量，用于描述整個網(wǎng)絡(luò)的通信能力。同時，節(jié)點間的通信能力也是無線傳感網(wǎng)絡(luò)中信息可靠傳輸?shù)幕A(chǔ)。整個網(wǎng)絡(luò)中節(jié)點的連接數(shù)目為

(6)

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

1.4 多目標(biāo)部署模型

根據(jù)1.3節(jié)的描述，可將部署問題用多目標(biāo)優(yōu)化函數(shù)表示如下：

(7)

其中，決策空間X∈[n，(x，y)]，n為部署區(qū)域中的節(jié)點數(shù)目，(x，y)為節(jié)點的位置坐標(biāo)矢量。

約束條件為

(8)

其中，F(xiàn)(X)是目標(biāo)函數(shù)；F1(X)為未被覆蓋率，該值越小，說明網(wǎng)絡(luò)的覆蓋率越高；F2(X)為節(jié)點連接數(shù)目的倒數(shù)，該值越小，說明網(wǎng)絡(luò)中存在的連接越多，數(shù)據(jù)傳輸越穩(wěn)定。約束條件要求節(jié)點部署在監(jiān)測區(qū)域內(nèi)，網(wǎng)絡(luò)覆蓋率不低于最低覆蓋率且節(jié)點至少可以與其他任意一個節(jié)點連通。

2 改進多目標(biāo)蟻獅算法

2.1 Pareto優(yōu)化模型

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

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

(9)

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

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

(10)

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

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

2.2 多目標(biāo)蟻獅算法

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

(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為數(shù)值累計函數(shù)，t、T分別為當(dāng)前迭代次數(shù)與最大迭代次數(shù)，r(t)是0和1間的隨機數(shù)，v為[0，1]內(nèi)的隨機數(shù)，定義為

(13)

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

(14)

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

(15)

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

2.3 改進的多目標(biāo)蟻獅算法

2.3.1 混沌初始化策略

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

(21)

取Fuch混沌序列的初始值z(0)=0.47，種群的規(guī)模SN=30，空間維數(shù)D=80，將式(21)產(chǎn)生的混沌序列映射到求解空間后得到初始化種群，種群個體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 基于正弦函數(shù)的邊界收縮因子I

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

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

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

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

(23)

其中，t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)；α為系數(shù)；β為調(diào)節(jié)參數(shù)，經(jīng)多次實驗后取值為0.1。

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

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

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

2.3.3 時變策略

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

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

(24)

(25)

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

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

算法1IMOALO偽代碼。

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

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

Whilet

For every ant

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

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

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

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

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

WhileFa*可支配Fa

aposition=aposition*；

End while

End for

根據(jù)支配關(guān)系更新Archive并按照擁擠度進行排序

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

IfN1>N

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

End

End while 。

2.4 算法時間復(fù)雜度分析

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

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

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

3 算法性能測試

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

3.1 評價指標(biāo)

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

3.2 實驗結(jié)果

實驗中蟻獅的數(shù)量為30，螞蟻的數(shù)量為30，最大迭代次數(shù)為100，外部存檔Archive的大小為100，圖4～8為算法在各個多目標(biāo)算法在測試函數(shù)上的分布情況。從左到右分別為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時只有一個解沒有落在帕累托前沿面上，其余均落在真實的帕累托前沿面上，對比于其他幾種經(jīng)典的多目標(biāo)算法，IMOALO算法的收斂性和分布性均優(yōu)于其他多目標(biāo)算法。這表明提出的策略有效地提升了多目標(biāo)蟻獅算法的性能。

為更準(zhǔn)確地評估IMOALO的性能，將上述算法在測試函數(shù)上運行30次，得到對應(yīng)的GD和IGD值，實驗結(jié)果如表1和表2所示，其中加粗的為每一列的最小值，Mean為均值，Std為標(biāo)準(zhǔn)差。

表1 4種不同算法下的IGD指標(biāo)值

表2 4種不同算法下的GD指標(biāo)值

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

4 實驗仿真及結(jié)果分析

4.1 實驗參數(shù)設(shè)置

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

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

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

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

圖9 不同算法的Pareto解集

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

表3 帕累托最優(yōu)解集

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

(a) 節(jié)點覆蓋效果圖

(a) 節(jié)點覆蓋效果圖

4.3 不同節(jié)點數(shù)目下的Pareto前沿面

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

圖13 不同節(jié)點數(shù)目下的帕累托前沿面

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

5 結(jié)束語

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