王 鑫, 張 菁
(上海工程技術(shù)大學 電子電氣工程學院,上海 201600)
隨著信息技術(shù)的發(fā)展,無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)受到越來越多的關(guān)注,并廣泛應用于社會日常生活中[1~3]。WSNs節(jié)點的部署在WSNs的研究中占據(jù)重要地位,影響網(wǎng)絡能耗的高低,對網(wǎng)絡使用壽命有著直接影響。過高的部署密度會提高網(wǎng)絡覆蓋率,但伴隨著大量冗余節(jié)點,增加了能量損耗,因此,如何對網(wǎng)絡節(jié)點的部署優(yōu)化已成為WSNs研究中亟需解決的重要問題[4,5]。
現(xiàn)階段,智能優(yōu)化算法已被廣泛應用于WSNs傳感器節(jié)點的覆蓋優(yōu)化問題中。文獻[6]提出一種螢火蟲算法的覆蓋優(yōu)化方法,有效給出節(jié)點網(wǎng)絡覆蓋優(yōu)化方案,但對移動距離的考量缺乏全面性。文獻[7]將節(jié)點有效覆蓋率作為優(yōu)化因子構(gòu)造目標函數(shù),提高了收斂速度和網(wǎng)絡節(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)絡覆蓋率、降低網(wǎng)絡能耗等問題中,最終延長網(wǎng)絡使用壽命。
本文針對WSNs節(jié)點冗余、生命周期短暫等問題,提出一種混合策略改進鯨魚優(yōu)化算法(whale optimization algorithm,WOA)的覆蓋優(yōu)化方法。首先提出一種改進Tent混沌映射對種群初始化問題改進,使搜索空間的解分布更加均勻,然后引入萊維飛行對鯨魚位置更新進行擾動操作,避免算法出現(xiàn)局部最優(yōu)。
設(shè)有面積為S=L×P的二維矩形WSNs監(jiān)測區(qū)域,隨機部署N個同構(gòu)傳感器,節(jié)點集合為Z={z1,z2,…,zi,…,zN},每個節(jié)點的感知半徑Rs和通信半徑Rc均一致,Rs≤2Rc。集合中zi的位置坐標為(xi,yi),i=1,2,…,N。傳感器節(jié)點的感知范圍可視為半徑為Rs的圓形區(qū)域,故可將監(jiān)測區(qū)域轉(zhuǎn)換成m×n個待覆蓋的目標點,其集合為K=(xj,yj),每個目標點的中心點為覆蓋優(yōu)化的目標位置。
設(shè)監(jiān)測區(qū)域中zi點位置坐標為zi=(xi,yi),目標點Qj位置坐標為Qj=(xj,yj),有節(jié)點與目標點間距離為
(1)
目標點被傳感器節(jié)點感知的概率p(zi,Qj)為
(2)
監(jiān)測區(qū)域中,因目標點可同時被多個傳感器節(jié)點感知,則WSNs對任意目標點的感知概率為
(3)
該區(qū)域中,覆蓋率Rcov表示為節(jié)點集合Z覆蓋的目標點數(shù)和該監(jiān)測區(qū)域總目標點數(shù)的比值,定義為
(4)
將式(4)作為混沌鯨魚優(yōu)化算法(chaotics whale optimization algorithm,CWOA)求解WSNs覆蓋優(yōu)化問題的目標函數(shù),即利用CWOA求解覆蓋率Rcov最大值以提高WSNs的覆蓋質(zhì)量,降低節(jié)點冗余。
WOA是基于座頭鯨覓食行為提出的優(yōu)化算法,依據(jù)座頭鯨覓食行為的特點,可分為三個階段:包圍獵物、氣泡網(wǎng)狩獵和搜索獵物。
2.1.1 包圍獵物
在包圍獵物階段,首先需要確定獵物位置再進行包圍,WOA假定當前階段的最優(yōu)位置為目標獵物的位置,鯨魚群其它鯨魚向當前最優(yōu)位置移動,該描述用數(shù)學模型表達為
D=|C·X*(t)-X(t)|
(5)
X(t+1)=X*(t)-A·D
(6)
式中D為當前最優(yōu)解和搜索目標的距離向量,X*(t)為最優(yōu)解的位置,X*(t)為搜索目標的位置;t為當前迭代次數(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ù)學模型表達有
X(t+1)=D*eblcos(2πl(wèi))+X*(t)
(9)
D*=|X*(t)-X(t)|
(10)
式中D*為座頭鯨與目標獵物之間的距離;l為[0,1]中的隨機數(shù);b為定義對數(shù)螺旋形狀的常量參數(shù)。
為模擬座頭鯨在螺旋移動的同時縮小包圍,設(shè)p為[0,1]中的隨機數(shù),則收縮包圍和螺旋位置更新的數(shù)學模型為
(11)
2.1.3 搜索獵物
在搜索獵物階段,鯨魚根據(jù)各自位置隨機搜索獵物,增強算法對監(jiān)測區(qū)域搜索的全面性,數(shù)學模型為
D=|C·Xrand-X(t)|
(12)
X(t+1)=Xrand(t)-A·D
(13)
式中Xrand(t)為種群中座頭鯨的隨機位置。
混沌映射具有隨機性和遍歷性的特性,能更加全面地搜索監(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),有效地解決了迭代到不動點的問題,使映射更具遍歷性。
萊維分布為在動物覓食過程中,下一步行動由當前位置和狀態(tài)進行預測,可通過數(shù)學模型表示。萊維飛行能增加種群多樣性和擴大搜索范圍,因此采用萊維飛行的智能優(yōu)化算法更容易跳出局部最優(yōu)點[11]。
在基本W(wǎng)OA中,隨迭代次數(shù)的增加座頭鯨會向適應度較高的個體靠近,導致算法容易出現(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ōu)選擇是否更新位置,數(shù)學模型為
(20)
基于CWOA的WSNs覆蓋優(yōu)化目標為:使目標監(jiān)測區(qū)域的節(jié)點覆蓋率Rcov最大化,即將所部署的傳感器節(jié)點位置優(yōu)化,求得節(jié)點的最優(yōu)位置。覆蓋優(yōu)化問題可視為以節(jié)點覆蓋率Rcov為目標函數(shù)的高維尋優(yōu)問題,而節(jié)點的搜尋過程,則可視為座頭鯨覓食過程中的包圍獵物、氣泡網(wǎng)狩獵、搜索獵物的行為,所得最優(yōu)解即各傳感器節(jié)點部署的目標位置。算法中每頭座頭鯨代表一種覆蓋分布,設(shè)節(jié)點數(shù)為N,則個體維度為2N,其中第2i和第2i-1分別代表節(jié)點的橫坐標和縱坐標。算法流程如圖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)化問題的目標函數(shù),利用式(4)計算種群適應度,求得種群當前全局最優(yōu)解的位置;4)判斷隨機數(shù)p是否高于0.5,若不是,則轉(zhuǎn)Step5;若是,則根據(jù)式(9)使鯨魚在螺旋移動的同時縮小包圍;5)根據(jù)式(6)更新種群個體向最優(yōu)個體移動的位置;6)引入萊維飛行,對種群更新后位置使用式(15)進行擾動,并同原位置適應度比較,擇優(yōu)選擇;7)判斷算法中迭代次數(shù)i是否達到最大次數(shù),若是,則輸出最優(yōu)解停止迭代,即輸出最優(yōu)覆蓋率和對應節(jié)點的位置坐標;若不是,則跳轉(zhuǎn)步驟(3)繼續(xù)迭代。
為驗證所提CWOA在WSNs傳感器節(jié)點覆蓋優(yōu)化的性能,將CWOA同基本鯨魚優(yōu)化算法WOA、蟻獅優(yōu)化(ant lion optimization,ALO)算法和螢火蟲算法(firely algorithm,FA)對覆蓋優(yōu)化的性能比較。其中,分別在實驗中對各算法選擇相同的試驗參數(shù)。
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)絡覆蓋的優(yōu)化效果。
本文針對WSNs中傳感器節(jié)點分布不均勻引起的節(jié)點覆蓋冗余、覆蓋率低等問題,提出一種CWOA的傳感器覆蓋優(yōu)化方法。該方法在基本鯨魚算法的基礎(chǔ)上,結(jié)合混沌理論,選擇Tent混沌映射初始化鯨魚種群,增加種群多樣性,有效解決種群隨機初始化分布不均勻的問題;引入萊維飛行對尋優(yōu)過程中位置更新進行擾動操作,避免了算法出線早熟收斂現(xiàn)象。仿真結(jié)果表明:同三種常用的覆蓋優(yōu)化算法對比分析,在分別取相同參數(shù)情況下,所提改進鯨魚算法的覆蓋優(yōu)化性能更優(yōu),有效提升收斂速度和精度,增加網(wǎng)絡覆蓋率、降低節(jié)點覆蓋冗余度。