混沌鯨魚優(yōu)化算法在WSNs覆蓋優(yōu)化中的應(yīng)用*

王 鑫, 張 菁

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201600)

0 引 言

隨著信息技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)受到越來越多的關(guān)注，并廣泛應(yīng)用于社會日常生活中[1～3]。WSNs節(jié)點的部署在WSNs的研究中占據(jù)重要地位，影響網(wǎng)絡(luò)能耗的高低，對網(wǎng)絡(luò)使用壽命有著直接影響。過高的部署密度會提高網(wǎng)絡(luò)覆蓋率，但伴隨著大量冗余節(jié)點，增加了能量損耗，因此,如何對網(wǎng)絡(luò)節(jié)點的部署優(yōu)化已成為WSNs研究中亟需解決的重要問題[4,5]。

現(xiàn)階段，智能優(yōu)化算法已被廣泛應(yīng)用于WSNs傳感器節(jié)點的覆蓋優(yōu)化問題中。文獻[6]提出一種螢火蟲算法的覆蓋優(yōu)化方法，有效給出節(jié)點網(wǎng)絡(luò)覆蓋優(yōu)化方案，但對移動距離的考量缺乏全面性。文獻[7]將節(jié)點有效覆蓋率作為優(yōu)化因子構(gòu)造目標(biāo)函數(shù)，提高了收斂速度和網(wǎng)絡(luò)節(jié)點覆蓋率，但對平衡全局探索和局部開發(fā)能力缺乏考慮。文獻[8]采用一種混合策略改進蟻獅算法對節(jié)點部署優(yōu)化，覆蓋率同其他算法相比更高，且優(yōu)化節(jié)點分布更加均勻，但收斂速度有待進一步提高。文獻[9]使用一種帶狀區(qū)域的WSNs覆蓋部署方法，根據(jù)同基站的距離優(yōu)化簇頭節(jié)點的數(shù)目，有效提高了節(jié)點覆蓋率，降低了能耗，但對節(jié)點覆蓋冗余還需進一步考慮。綜上所述，WSNs傳感器節(jié)點的覆蓋優(yōu)化主要集中在如何加快收斂速度、提高網(wǎng)絡(luò)覆蓋率、降低網(wǎng)絡(luò)能耗等問題中，最終延長網(wǎng)絡(luò)使用壽命。

本文針對WSNs節(jié)點冗余、生命周期短暫等問題，提出一種混合策略改進鯨魚優(yōu)化算法(whale optimization algorithm，WOA)的覆蓋優(yōu)化方法。首先提出一種改進Tent混沌映射對種群初始化問題改進，使搜索空間的解分布更加均勻，然后引入萊維飛行對鯨魚位置更新進行擾動操作，避免算法出現(xiàn)局部最優(yōu)。

1 WSNs節(jié)點覆蓋模型

設(shè)有面積為S=L×P的二維矩形WSNs監(jiān)測區(qū)域，隨機部署N個同構(gòu)傳感器，節(jié)點集合為Z={z1,z2,…,zi,…,zN}，每個節(jié)點的感知半徑Rs和通信半徑Rc均一致，Rs≤2Rc。集合中zi的位置坐標(biāo)為(xi,yi),i=1,2,…,N。傳感器節(jié)點的感知范圍可視為半徑為Rs的圓形區(qū)域，故可將監(jiān)測區(qū)域轉(zhuǎn)換成m×n個待覆蓋的目標(biāo)點，其集合為K=(xj,yj)，每個目標(biāo)點的中心點為覆蓋優(yōu)化的目標(biāo)位置。

設(shè)監(jiān)測區(qū)域中zi點位置坐標(biāo)為zi=(xi,yi)，目標(biāo)點Qj位置坐標(biāo)為Qj=(xj,yj)，有節(jié)點與目標(biāo)點間距離為

(1)

目標(biāo)點被傳感器節(jié)點感知的概率p(zi,Qj)為

(2)

監(jiān)測區(qū)域中，因目標(biāo)點可同時被多個傳感器節(jié)點感知，則WSNs對任意目標(biāo)點的感知概率為

(3)

該區(qū)域中，覆蓋率Rcov表示為節(jié)點集合Z覆蓋的目標(biāo)點數(shù)和該監(jiān)測區(qū)域總目標(biāo)點數(shù)的比值，定義為

(4)

將式(4)作為混沌鯨魚優(yōu)化算法(chaotics whale optimization algorithm，CWOA)求解WSNs覆蓋優(yōu)化問題的目標(biāo)函數(shù)，即利用CWOA求解覆蓋率Rcov最大值以提高WSNs的覆蓋質(zhì)量，降低節(jié)點冗余。

2 CWOA

2.1 基本W(wǎng)OA

WOA是基于座頭鯨覓食行為提出的優(yōu)化算法,依據(jù)座頭鯨覓食行為的特點，可分為三個階段：包圍獵物、氣泡網(wǎng)狩獵和搜索獵物。

2.1.1 包圍獵物

在包圍獵物階段，首先需要確定獵物位置再進行包圍，WOA假定當(dāng)前階段的最優(yōu)位置為目標(biāo)獵物的位置，鯨魚群其它鯨魚向當(dāng)前最優(yōu)位置移動，該描述用數(shù)學(xué)模型表達為

D=|C·X*(t)-X(t)|

(5)

X(t+1)=X*(t)-A·D

(6)

式中D為當(dāng)前最優(yōu)解和搜索目標(biāo)的距離向量，X*(t)為最優(yōu)解的位置，X*(t)為搜索目標(biāo)的位置；t為當(dāng)前迭代次數(shù)；A,C為系數(shù)向量，定義為

A=2ar-a

(7)

C=2r

(8)

式中a隨迭代次數(shù)從2線性遞減至0，r為[0,1]中的隨機數(shù)。

2.1.2 氣泡網(wǎng)狩獵

座頭鯨的捕食攻擊行為，按照WOA可分為螺旋式位置更新和收縮包圍兩種方式，用數(shù)學(xué)模型表達有

X(t+1)=D*eblcos(2πl(wèi))+X*(t)

(9)

D*=|X*(t)-X(t)|

(10)

式中D*為座頭鯨與目標(biāo)獵物之間的距離；l為[0,1]中的隨機數(shù)；b為定義對數(shù)螺旋形狀的常量參數(shù)。

為模擬座頭鯨在螺旋移動的同時縮小包圍，設(shè)p為[0,1]中的隨機數(shù)，則收縮包圍和螺旋位置更新的數(shù)學(xué)模型為

(11)

2.1.3 搜索獵物

在搜索獵物階段，鯨魚根據(jù)各自位置隨機搜索獵物，增強算法對監(jiān)測區(qū)域搜索的全面性，數(shù)學(xué)模型為

D=|C·Xrand-X(t)|

(12)

X(t+1)=Xrand(t)-A·D

(13)

式中Xrand(t)為種群中座頭鯨的隨機位置。

2.2 混沌映射初始化

混沌映射具有隨機性和遍歷性的特性，能更加全面地搜索監(jiān)測區(qū)域，利用該特性對鯨魚算法的種群初始化，可有效解決普通鯨魚優(yōu)化算法中的隨機初始化分布不均勻的問題，提高算法在搜索過程中的搜索效率。結(jié)合混沌理論和鯨魚優(yōu)化算法，在文獻[10]中可知帳篷映射(tent map)對WOA搜索性能的提升在所有混沌映射中的最優(yōu)。故本文選擇Tent混沌映射初始化鯨魚種群，定義為

(14)

式中xn∈[0,1]，系統(tǒng)參數(shù)μ=1.99時，Tent混沌映射均勻分布。

雖然Tent混沌映射對WOA搜索性能的提升最優(yōu)，但映射的迭代過程中存在小周期和不穩(wěn)定周期，均會迭代到不動點0。為解決上述問題，提出一種將隨機因子引入種群位置更新中，定義為

(15)

加入隨機因子，使Tent混沌映射在迭代到小周期和不穩(wěn)定周期時重新進入混沌狀態(tài)，有效地解決了迭代到不動點的問題，使映射更具遍歷性。

2.3 萊維飛行擾動

萊維分布為在動物覓食過程中，下一步行動由當(dāng)前位置和狀態(tài)進行預(yù)測，可通過數(shù)學(xué)模型表示。萊維飛行能增加種群多樣性和擴大搜索范圍，因此采用萊維飛行的智能優(yōu)化算法更容易跳出局部最優(yōu)點[11]。

在基本W(wǎng)OA中，隨迭代次數(shù)的增加座頭鯨會向適應(yīng)度較高的個體靠近，導(dǎo)致算法容易出現(xiàn)局部最優(yōu)現(xiàn)象。因此，引入萊維飛行對尋優(yōu)過程中位置更新進行擾動操作，避免算法出線早熟收斂現(xiàn)象。位置更新公式為

Xl(t)=X(t)+α⊕Levy(λ)

(16)

式中Xl(t)為擾動后的位置；⊕為點乘；Levy(λ)為隨機搜索路徑，表現(xiàn)為隨機冪次形式的概率密度函數(shù)，即

Levy-u=t-λ，1<λ≤3

(17)

對與萊維分布的隨機步長s，使用Mantegna算法進行模擬，公式為

s=μ/|v|1/β

(18)

(19)

為使萊維飛行擾動后的位置優(yōu)于原位置，對比擾動后和原有位置的適應(yīng)度，擇優(yōu)選擇是否更新位置，數(shù)學(xué)模型為

(20)

3 覆蓋優(yōu)化策略

基于CWOA的WSNs覆蓋優(yōu)化目標(biāo)為：使目標(biāo)監(jiān)測區(qū)域的節(jié)點覆蓋率Rcov最大化，即將所部署的傳感器節(jié)點位置優(yōu)化，求得節(jié)點的最優(yōu)位置。覆蓋優(yōu)化問題可視為以節(jié)點覆蓋率Rcov為目標(biāo)函數(shù)的高維尋優(yōu)問題，而節(jié)點的搜尋過程，則可視為座頭鯨覓食過程中的包圍獵物、氣泡網(wǎng)狩獵、搜索獵物的行為，所得最優(yōu)解即各傳感器節(jié)點部署的目標(biāo)位置。算法中每頭座頭鯨代表一種覆蓋分布，設(shè)節(jié)點數(shù)為N,則個體維度為2N，其中第2i和第2i-1分別代表節(jié)點的橫坐標(biāo)和縱坐標(biāo)。算法流程如圖1所示。

圖1 基于CWOA的WSNs覆蓋優(yōu)化

具體算法步驟如下：1)輸入WSNs監(jiān)測區(qū)域和CWOA的相關(guān)參數(shù)；2)將混沌理論結(jié)合鯨魚算法，在監(jiān)測領(lǐng)域中選擇Tent混沌映射初始化鯨魚種群的個體位置；3)以覆蓋率Rcov作為求解WSNs覆蓋優(yōu)化問題的目標(biāo)函數(shù)，利用式(4)計算種群適應(yīng)度，求得種群當(dāng)前全局最優(yōu)解的位置；4)判斷隨機數(shù)p是否高于0.5，若不是,則轉(zhuǎn)Step5;若是,則根據(jù)式(9)使鯨魚在螺旋移動的同時縮小包圍；5)根據(jù)式(6)更新種群個體向最優(yōu)個體移動的位置；6)引入萊維飛行，對種群更新后位置使用式(15)進行擾動，并同原位置適應(yīng)度比較，擇優(yōu)選擇；7)判斷算法中迭代次數(shù)i是否達到最大次數(shù)，若是,則輸出最優(yōu)解停止迭代，即輸出最優(yōu)覆蓋率和對應(yīng)節(jié)點的位置坐標(biāo)；若不是，則跳轉(zhuǎn)步驟(3)繼續(xù)迭代。

4 仿真實驗與分析

4.1 實驗環(huán)境

為驗證所提CWOA在WSNs傳感器節(jié)點覆蓋優(yōu)化的性能，將CWOA同基本鯨魚優(yōu)化算法WOA、蟻獅優(yōu)化(ant lion optimization,ALO)算法和螢火蟲算法(firely algorithm,FA)對覆蓋優(yōu)化的性能比較。其中，分別在實驗中對各算法選擇相同的試驗參數(shù)。

4.2 實驗結(jié)果

1)與FA對比

取相同實驗參數(shù)設(shè)置，設(shè)監(jiān)測區(qū)域為50 m×50 m的二維平面，傳感器節(jié)點個數(shù)N=30，其感知半徑Rs=5 m，通信半徑Rc=10 m，迭代次數(shù)取1 000次。對比CWOA和FA的覆蓋優(yōu)化程度，覆蓋率—迭代次數(shù)的變化趨勢如圖2所示，覆蓋優(yōu)化后節(jié)點部署如圖3所示，F(xiàn)A、CWOA覆蓋率分別為86.1 %和91.3 %。

圖2 覆蓋優(yōu)化迭代曲線

圖3 優(yōu)化后節(jié)點部署

2)與ALO算法對比

取相同實驗參數(shù)設(shè)置，設(shè)監(jiān)測區(qū)域為200 m×200 m的二維平面，傳感器節(jié)點個數(shù)N=50，其感知半徑Rs=20 m，通信半徑Rc=40 m，迭代次數(shù)取1 000次。對比CWOA和ALO算法的覆蓋優(yōu)化程度，覆蓋率—迭代次數(shù)的變化趨勢如圖4所示，覆蓋優(yōu)化后節(jié)點部署如圖5所示，ALO算法、CWOA覆蓋率分別為96.7 %和97.4 %。

圖4 覆蓋優(yōu)化迭代曲線

圖5 優(yōu)化后節(jié)點部署

3)與WOA對比

取相同實驗參數(shù)設(shè)置，設(shè)監(jiān)測區(qū)域為100 m×100 m的二維平面，傳感器節(jié)點個數(shù)N=40，其感知半徑Rs=10 m，通信半徑Rc=20 m，迭代次數(shù)取1 000次。對比CWOA和FA的覆蓋優(yōu)化程度，覆蓋率—迭代次數(shù)的變化趨勢如圖6所示，覆蓋優(yōu)化后節(jié)點部署如圖7所示，WOA、CWOA覆蓋率分別為92.7 %和95.9 %。

圖6 覆蓋優(yōu)化迭代曲線

圖7 優(yōu)化后節(jié)點部署

對比不同算法的覆蓋優(yōu)化性能，可見本文所提優(yōu)化方法在收斂速度和節(jié)點覆蓋率上更優(yōu)，充分證明了所提算法對網(wǎng)絡(luò)覆蓋的優(yōu)化效果。

5 結(jié) 論

本文針對WSNs中傳感器節(jié)點分布不均勻引起的節(jié)點覆蓋冗余、覆蓋率低等問題，提出一種CWOA的傳感器覆蓋優(yōu)化方法。該方法在基本鯨魚算法的基礎(chǔ)上，結(jié)合混沌理論，選擇Tent混沌映射初始化鯨魚種群，增加種群多樣性，有效解決種群隨機初始化分布不均勻的問題；引入萊維飛行對尋優(yōu)過程中位置更新進行擾動操作，避免了算法出線早熟收斂現(xiàn)象。仿真結(jié)果表明：同三種常用的覆蓋優(yōu)化算法對比分析，在分別取相同參數(shù)情況下，所提改進鯨魚算法的覆蓋優(yōu)化性能更優(yōu)，有效提升收斂速度和精度，增加網(wǎng)絡(luò)覆蓋率、降低節(jié)點覆蓋冗余度。