UWSNs移動(dòng)節(jié)點(diǎn)部署優(yōu)化策略 ①

張海洋， 趙歡歡

(1.滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院，安徽 滁州 239000;2.中國(guó)科學(xué)技術(shù)大學(xué)，安徽 合肥 230000)

0 引 言

隨著海洋資源開(kāi)發(fā)以及海洋軍事的影響，UWSNs已變?yōu)榻鼛啄陣?guó)內(nèi)外研究熱門課題。UWSNs通過(guò)節(jié)點(diǎn)組成網(wǎng)絡(luò)并實(shí)時(shí)監(jiān)測(cè)并發(fā)送目標(biāo)區(qū)域內(nèi)的信息到水面基站，再通過(guò)衛(wèi)星或近岸基站將實(shí)時(shí)信息發(fā)給觀察者[1]。在UWSNs研究中，監(jiān)測(cè)區(qū)域部署是一個(gè)基本問(wèn)題，即如何利用有限的節(jié)點(diǎn)部署在目標(biāo)監(jiān)測(cè)區(qū)域，達(dá)到網(wǎng)絡(luò)的最大覆蓋度[2]。

布置在水下的靜態(tài)節(jié)點(diǎn)其適應(yīng)性較差，受復(fù)雜水聲環(huán)境、水生物及水流等影響較大，網(wǎng)絡(luò)的優(yōu)化效果較低，不能對(duì)目標(biāo)監(jiān)測(cè)地區(qū)達(dá)到合理高效的部署效果，容易導(dǎo)致監(jiān)測(cè)盲區(qū)或網(wǎng)絡(luò)失效，而移動(dòng)節(jié)點(diǎn)則能較好的解決這一問(wèn)題。

概率感知模型，考慮了信號(hào)衰減及噪聲干擾，比0-1感知模型更適合水下復(fù)雜環(huán)境。節(jié)點(diǎn)si對(duì)任意點(diǎn)pj的感知公式為[3]：

(1)

水下節(jié)點(diǎn)通常采用水聲信號(hào)進(jìn)行相互通信，任意節(jié)點(diǎn)si與sj之間的歐氏距離定義為

(2)

如果d(si,sj)小于節(jié)點(diǎn)通信半徑Rc，則si與sj可直接通信并互為鄰居節(jié)點(diǎn)。

1 UCGA算法求解UWSNs移動(dòng)部署問(wèn)題

GSO是一種較為新穎的群智能優(yōu)化算法，具備計(jì)算速率快、設(shè)置參數(shù)較少、搜索自適應(yīng)且易于實(shí)現(xiàn)的特征，能夠較好地求取全局極值及搜索多極值問(wèn)題中的多個(gè)極值。根據(jù)文獻(xiàn)仿真驗(yàn)證，螢火蟲(chóng)算法也存在陷入局部最優(yōu)問(wèn)題的可能性，但是螢火蟲(chóng)算法具有跳出局部最優(yōu)的能力，具有更好的全局尋優(yōu)能力[4]。針對(duì)三維UWSNs網(wǎng)絡(luò)部署的特點(diǎn)，將GSO算法結(jié)合混沌思想優(yōu)化為與三維空間的UWSNs部署環(huán)境需求相符的新算法UCGA。

將目標(biāo)監(jiān)測(cè)區(qū)域節(jié)點(diǎn)部署方案視為一個(gè)求最優(yōu)值問(wèn)題，其目的是使網(wǎng)絡(luò)的覆蓋度達(dá)到最優(yōu)值。目標(biāo)適應(yīng)度值函數(shù)則對(duì)應(yīng)為所有節(jié)點(diǎn)的目標(biāo)水域覆蓋面積與監(jiān)測(cè)水域的總面積之比，則目標(biāo)適應(yīng)度值函數(shù)即覆蓋度為[5]：

(3)

UCGA算法具體步驟如下：

步驟一：初始化各參數(shù)，根據(jù)混沌策略產(chǎn)生取值區(qū)間的初始化種群值，比較并從{Xi|i=1,…,N}中選出最優(yōu)秀的個(gè)體向量Xb，隨機(jī)的生成維數(shù)為N的變量Z1=[z1,1,z1,2,…,z1,N]，使用Z1作為混沌變量進(jìn)行迭代分析，其中z1,N表示混沌序列長(zhǎng)度，將Z1與Xb組合用以生成螢火蟲(chóng)種群初始向量Xc，相關(guān)公式如下[6]：

Xc=ρ×Z1+(1-ρ)Xb

(4)

(5)

式中，tmax是算法的最高迭代數(shù)目，t則是當(dāng)前到達(dá)的迭代數(shù)目。

步驟二：依據(jù)目標(biāo)適應(yīng)度值函數(shù)計(jì)算其發(fā)光亮度；

步驟三：所有螢火蟲(chóng)移位，對(duì)每個(gè)個(gè)體，尋找其周圍發(fā)光強(qiáng)度高于它的個(gè)體并計(jì)算它們之間的距離，依據(jù)適應(yīng)度值函數(shù)計(jì)算出群體的相對(duì)亮度及吸引度，然后確定其移動(dòng)方位并更新位置；

步驟四：由于基本螢火蟲(chóng)算法易陷于早熟并收斂，故選擇適應(yīng)度值較低的個(gè)體，利用公式生成相對(duì)應(yīng)的新個(gè)體并替換，提升了種群收斂速率，且由于新個(gè)體是由logistic映射生成，擁有者隨機(jī)性，故替換原個(gè)體的新螢火蟲(chóng)增加了種群的分布均勻性。

步驟五：通過(guò)對(duì)比螢火蟲(chóng)個(gè)體的適應(yīng)值和種群位置適應(yīng)值得出新最優(yōu)位置和最優(yōu)適應(yīng)值，判斷最優(yōu)結(jié)果是否大于原種群位置處適應(yīng)值。若否，則在其感知范圍內(nèi)繼續(xù)尋找最優(yōu)解，若是，則將選出的新最優(yōu)位置作為新的群體位置，即重置種群位置，否則種群個(gè)體繼續(xù)尋找周圍最優(yōu)解，返回步驟二。

2 仿真與評(píng)估

假設(shè)在三維監(jiān)控水域內(nèi)隨機(jī)布撒了節(jié)點(diǎn)，且該網(wǎng)絡(luò)具備以下性質(zhì)：所有節(jié)點(diǎn)均擁有一致的物理結(jié)構(gòu)，即感知及通信半徑完全一致，并采用概率感知模型。

將UCGA算法與Horng等[7]提出的改進(jìn)GSO算法在Matlab2009上進(jìn)行對(duì)比仿真，將9個(gè)節(jié)點(diǎn)投放在水下檢測(cè)區(qū)域形成覆蓋圖形如圖1所示，其有效覆蓋度為35.72%,目標(biāo)水域極限覆蓋度為12π×Rs3/104=82.75%；經(jīng)改進(jìn)GSO進(jìn)行重新部署后的優(yōu)化效果如圖2所示，其對(duì)目標(biāo)檢測(cè)水域的有效覆蓋度為65.43%；通過(guò)UCGA進(jìn)行優(yōu)化得到節(jié)點(diǎn)分布圖如圖3所示，其有效覆蓋度為72.14%。通過(guò)對(duì)比可以看出經(jīng)過(guò)優(yōu)化后UCGA分布效果更加合理，當(dāng)種群數(shù)目即節(jié)點(diǎn)數(shù)增加的時(shí)候，改進(jìn)GSO的優(yōu)化效果要低于UCGA算法。

圖1 隨機(jī)部署覆蓋圖

圖2 改進(jìn)GSO覆蓋圖

圖3 UCGA算法優(yōu)化圖

表1為隨機(jī)部署、改進(jìn)GSO、UCGA不同深度水平覆蓋度比較，仿真出的不同深度水平截面圖如圖4、5、6所示，從圖表中可以看出，相比改進(jìn)GSO算法，UCGA算法在z=25m、z=50m、z=75m三種深度的覆蓋效果均有較好的提升。

表1 不同深度水平覆蓋度比較

圖4 隨機(jī)部署不同深度截面圖

圖5 改進(jìn)GSO算法優(yōu)化后不同深度截面圖

圖6 UCGA算法優(yōu)化后不同深度截面圖

圖7 覆蓋度對(duì)比圖

仿真出的有效覆蓋度隨著迭代次數(shù)增加而變化如圖7所示，其中紅色曲線為基于UCGA迭代優(yōu)化曲線，藍(lán)色曲線為改進(jìn)GSO優(yōu)化迭代覆蓋度曲線，從圖里可以看出，UCGA在前期相較于GSO表現(xiàn)出更快的收斂速率，其主要原因在于采取Logistic映射所生成的序列初始化節(jié)點(diǎn)，得到質(zhì)量較優(yōu)的初始種群解；而GSO則是完全根據(jù)隨機(jī)移動(dòng)尋優(yōu)，因此其前期優(yōu)化速度較慢。UCGA在迭代后期由于混沌擾動(dòng)性對(duì)較優(yōu)解進(jìn)行局部搜索以跳出局部極值點(diǎn)，使其在小范圍內(nèi)具備更好的局部尋優(yōu)能力并收斂于較高覆蓋度，UCGA在后期體現(xiàn)出了更好的收斂速率并獲得較優(yōu)的部署覆蓋效果。

3 結(jié) 語(yǔ)

UWSNs移動(dòng)節(jié)點(diǎn)部署是近幾年重點(diǎn)研究課題之一，對(duì)節(jié)點(diǎn)部署優(yōu)化可以顯著提高其覆蓋性能，因而提出基于混沌理論的UCGA對(duì)水下移動(dòng)節(jié)點(diǎn)進(jìn)行部署優(yōu)化。在節(jié)點(diǎn)隨機(jī)部署階段UCGA采用Logistic映射所生成的序列初始化傳感器節(jié)點(diǎn)，并在重部署階段利用混沌擾動(dòng)性對(duì)適應(yīng)度值較低的局部搜索以跳出極值點(diǎn)。UCGA彌補(bǔ)了GSO的尋優(yōu)精度相對(duì)較低的問(wèn)題，仿真實(shí)驗(yàn)驗(yàn)證了，UCGA具有較理想的優(yōu)化效果和較快的收斂速率，因此在未來(lái)實(shí)際應(yīng)用中具有一定可行性和有效性。