王 鑫, 張 菁

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

0 引 言

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

2 CWOA

2.1 基本W(wǎng)OA

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

2.1.1 包圍獵物

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

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線(xiàn)性遞減至0，r為[0,1]中的隨機(jī)數(shù)。

2.1.2 氣泡網(wǎng)狩獵

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

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

(9)

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

(10)

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

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

(11)

2.1.3 搜索獵物

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

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

(12)

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

(13)

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

2.2 混沌映射初始化

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

(14)

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

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

(15)

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

2.3 萊維飛行擾動(dòng)

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

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

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

(16)

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

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

(17)

對(duì)與萊維分布的隨機(jī)步長(zhǎng)s，使用Mantegna算法進(jìn)行模擬，公式為

s=μ/|v|1/β

(18)

(19)

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

(20)

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

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

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

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

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 實(shí)驗(yàn)結(jié)果

1)與FA對(duì)比

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

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

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

2)與ALO算法對(duì)比

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

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

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

3)與WOA對(duì)比

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

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

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

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

5 結(jié) 論

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