UWSNs移動節點部署優化策略 ①

張海洋， 趙歡歡

(1.滁州學院計算機與信息工程學院，安徽 滁州 239000;2.中國科學技術大學，安徽 合肥 230000)

0 引 言

隨著海洋資源開發以及海洋軍事的影響，UWSNs已變為近幾年國內外研究熱門課題。UWSNs通過節點組成網絡并實時監測并發送目標區域內的信息到水面基站，再通過衛星或近岸基站將實時信息發給觀察者[1]。在UWSNs研究中，監測區域部署是一個基本問題，即如何利用有限的節點部署在目標監測區域，達到網絡的最大覆蓋度[2]。

布置在水下的靜態節點其適應性較差，受復雜水聲環境、水生物及水流等影響較大，網絡的優化效果較低，不能對目標監測地區達到合理高效的部署效果，容易導致監測盲區或網絡失效，而移動節點則能較好的解決這一問題。

概率感知模型，考慮了信號衰減及噪聲干擾，比0-1感知模型更適合水下復雜環境。節點si對任意點pj的感知公式為[3]：

(1)

水下節點通常采用水聲信號進行相互通信，任意節點si與sj之間的歐氏距離定義為

(2)

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

1 UCGA算法求解UWSNs移動部署問題

GSO是一種較為新穎的群智能優化算法，具備計算速率快、設置參數較少、搜索自適應且易于實現的特征，能夠較好地求取全局極值及搜索多極值問題中的多個極值。根據文獻仿真驗證，螢火蟲算法也存在陷入局部最優問題的可能性，但是螢火蟲算法具有跳出局部最優的能力，具有更好的全局尋優能力[4]。針對三維UWSNs網絡部署的特點，將GSO算法結合混沌思想優化為與三維空間的UWSNs部署環境需求相符的新算法UCGA。

將目標監測區域節點部署方案視為一個求最優值問題，其目的是使網絡的覆蓋度達到最優值。目標適應度值函數則對應為所有節點的目標水域覆蓋面積與監測水域的總面積之比，則目標適應度值函數即覆蓋度為[5]：

(3)

UCGA算法具體步驟如下：

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

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

(4)

(5)

式中，tmax是算法的最高迭代數目，t則是當前到達的迭代數目。

步驟二：依據目標適應度值函數計算其發光亮度；

步驟三：所有螢火蟲移位，對每個個體，尋找其周圍發光強度高于它的個體并計算它們之間的距離，依據適應度值函數計算出群體的相對亮度及吸引度，然后確定其移動方位并更新位置；

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

步驟五：通過對比螢火蟲個體的適應值和種群位置適應值得出新最優位置和最優適應值，判斷最優結果是否大于原種群位置處適應值。若否，則在其感知范圍內繼續尋找最優解，若是，則將選出的新最優位置作為新的群體位置，即重置種群位置，否則種群個體繼續尋找周圍最優解，返回步驟二。

2 仿真與評估

假設在三維監控水域內隨機布撒了節點，且該網絡具備以下性質：所有節點均擁有一致的物理結構，即感知及通信半徑完全一致，并采用概率感知模型。

將UCGA算法與Horng等[7]提出的改進GSO算法在Matlab2009上進行對比仿真，將9個節點投放在水下檢測區域形成覆蓋圖形如圖1所示，其有效覆蓋度為35.72%,目標水域極限覆蓋度為12π×Rs3/104=82.75%；經改進GSO進行重新部署后的優化效果如圖2所示，其對目標檢測水域的有效覆蓋度為65.43%；通過UCGA進行優化得到節點分布圖如圖3所示，其有效覆蓋度為72.14%。通過對比可以看出經過優化后UCGA分布效果更加合理，當種群數目即節點數增加的時候，改進GSO的優化效果要低于UCGA算法。

圖1 隨機部署覆蓋圖

圖2 改進GSO覆蓋圖

圖3 UCGA算法優化圖

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

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

圖4 隨機部署不同深度截面圖

圖5 改進GSO算法優化后不同深度截面圖

圖6 UCGA算法優化后不同深度截面圖

圖7 覆蓋度對比圖

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

3 結 語

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