水下無人集群優化部署算法設計與分析

佟 盛，李大輝，戴學豐

(1.中國船舶信息中心，北京 100101；2.齊齊哈爾大學 計算機與控制工程學院，黑龍江 齊齊哈爾 161006)

0 引 言

移動集群中每個節點的感知范圍都十分有限，如果節點分布不合理，就會導致網絡中出現感知盲區，從而無法對目標實現覆蓋要求，而且由于水下節點的造價高昂，通過增加冗余節點的方法并不現實，因此研究水下節點部署問題十分重要。群體智能算法是一類新興優化算法，并大量用于最優化求解[1]。這類算法模仿了社會性動物的群聚行為。單個動物體能夠完成簡單的任務，如果多個動物體間相互交流、相互協作，便能完成更加復雜的任務，這一系列過程的實現并不只是通過動物個體數量的增加得到的，更重要的是個體間的信息交互。比較經典的群體智能算法有粒子群算法、蟻群算法以及人工魚群算法等[2-7]。這些算法均能夠有效提高覆蓋率，并使整個網絡節點的分布更加均勻。但算法本身也存在著不足之處，均存在“早熟”收斂、局部最優解[8]等問題。

無線傳感網絡（Wireless sensor network，WSN）是一種將無線通信、傳感器以及分布式信息處理融為一體的網絡技術，它以部署靈活成本低廉等特點得到廣泛的使用[9]。如何在保持網絡覆蓋率的條件下延長網絡的生命周期，成為傳感器網絡研究的一個關鍵問題，國內外學者對無線傳感網絡覆蓋進行了研究，文獻[10]提出一種基于遺傳粒子群優化算法（Particle swarm optimization，PSO）的無線傳感網絡覆蓋優化算法，該方法能有效地實現無線傳感網絡覆蓋優化，不足的是PSO算法易陷入局部極值點，從而限制了粒子的搜索范圍。文獻[11]提出將改進的蟻群算法運用到網絡節點覆蓋優化中，雖然增加了算法局部搜索能力，但在一定程度上沒有考慮實際環境因素，影響網絡覆蓋優化的實時性。文獻[12]提出一種運用分形理論自相似性原理進行區域劃分以構建最優覆蓋模型的方法，該方法有效地降低網絡部署成本和能耗，但存在一定的重復覆蓋比例。文獻[13]提出了在無線傳感網絡中引入遺傳算法進行節點優化，算法雖然具有較強的并行搜索能力，但在最優解附近收斂速度慢，難以滿足動態節點的實時性要求。

由于水下環境的復雜，以及水下節點的造價昂貴，陸上傳感網絡的大規模隨機部署方案在水下不可能實現。因此，國內外的研究重點都基于如何使用盡量少的節點實現網絡覆蓋的最優化。通過總結發現，早期國內外的很多研究基于數學模型，對于水下環境的考慮并不全面，而且大多基于靜態網絡的部署。而近期的研究中很多人開始使用諸如魚群算法等智能算法，更多地考慮水下環境的復雜性以及節點的移動，不僅提高了網絡的覆蓋度，還增強了網絡連通性，降低了能量消耗，從而保持網絡穩定運行，有效防止網絡空洞。

本文主要采用布爾感知模型重點研究區域覆蓋，利用粒子群優化算法與人工魚群優化算法進行混合編程，完成水下移動節點部署優化，從而實現對目標區域高覆蓋度的部署目標。重點完成水下無人集群節點部署優化方案和仿真實驗設計，主要利用粒子群優化算法與人工魚群優化算法混合完成水下無人集群對水下環境的覆蓋。利用粒子群算法初期收斂快的特點，進行初期尋優，再用人工魚群算法進行后期尋優，二者優勢互補，完成對集群節點部署優化。

1 網絡覆蓋模型

1.1 節點覆蓋率

現假設檢測區域A為二維平面坐標，在該區域上投放參數相同的傳感器節點，數目為N，每個節點的坐標均已知，且有效監測半徑均為r，則傳感器節點集表示為c={c1,c2,c3,· · ·,cN}，其中ci={xi,yi,r}，表示以節點坐標{xi,yi}為圓心，監測半徑為r的圓。假設監測區域A被數字離散化為m×n個像素，將像素點（x,y）被傳感器節點i所覆蓋的事件定義為ri，則該事件發生的概率P{ri}即為像素點（x,y）被傳感器節點i所覆蓋的概率Pcov（x,y,ci）。

式（1）表明，當像素點（x,y）到傳感器節點i的距離小于傳感器范圍r時，就認為該像素點（x,y）被傳感器節點i覆蓋。

圖1 海上場景示意圖Fig.1 Schematic diagram of the sea scene

節點集中只要有一個節點覆蓋了像素點（x,y），就認為該像素點（x,y）被節點集覆蓋。因此，像素點被節點集所覆蓋的概率即為ri的并集，假設所有的隨機事件ri是互相獨立的，則節點集C的覆蓋率可以利用下式計算：

式（4）表明，若所有的節點都沒有覆蓋到像素點，則該像素點為未覆蓋點，否則，便認為該像素點被節點集覆蓋。

1.2 區域覆蓋率

監測區域A內有m×n個像素，每個像素的面積大小可表示為△x×△y（假定每個像素的面積為1），每個像素是否被覆蓋用節點集覆蓋率Pcov（x,y,ci）來衡量，則將節點集C的區域覆蓋率Rarea定義為節點集C的覆蓋率面積Aarea與監測區域A的總面積As之比，即

2 優化算法

2.1 標準粒子群算法

粒子是粒子群算法的基本單位，每個粒子都代表解空間的一個候選解，所有粒子構成了種群，每一個粒子都有自己的飛行狀態，包括飛行速度和方向，適應度函數即算法的優化目標，決定了整個算法的搜索方向。在整個迭代過程中，每個粒子都會存在一個當前迭代值對應的最優解，被稱為個體極值（Pbest），具體迭代過程如圖2所示。

圖2 標準粒子群算法流程圖Fig.2 Flow chart of standard particle swarm algorithm

整個種群的當前最優解被稱為全局極值（gbest）。每次迭代過程中，Pbest和gbest都會更新，如果迭代次數足夠多，Pbest和gbest最終會趨于穩定，算法結束后gbest即整個算法求得的最優解。

2.2 改進粒子群算法

標準粒子群算法收斂較快，但后期尋最優解效果較差，容易陷入局部最優，真實部署時不僅浪費時間，還浪費節點能量，本項目將引入線性遞減慣性權重系數，如式（6）所示，采用線性遞減慣性權重可以加強前期全局搜索能力，控制后期的局部搜索能力，避免算法陷入局部極值。權重系數

每次迭代過程中，粒子的速度為：

每次迭代過程中，選出每個粒子中距離最近的兩個節點，對這兩個節點進行位置進行二次調節，使其相互遠離。

2.3 粒子群-人工魚群算法

人工魚有覓食行為、聚群行為、追尾行為和隨機行為4種，每條魚移動之前都會進行試探，試探結束后再決定采取哪種行動，流程如圖3所示。

1）覓食行為。魚群會根據水中的食物濃度決定游動方向，這是魚維持生存的本能行為，魚總會向著食物濃度高的方向游動。

假設某條人工魚當前狀態為x，魚會在當前視野范圍內選一個狀態x，如果狀態y優于狀態x，則魚移動到y，否則不移動。人工魚會以此方式試探Tnum次，選出狀態最好的一個為x的下一個狀態。如果Tnum次試探后沒有比x更好的狀態，人工魚將執行其他行為，如隨機游動。

圖3 人工魚群算法流程圖Fig.3 Flow chart of artificial fish swarm algorithm

2）聚群行為。聚群行為是為了在受到攻擊時尋求庇護，以保護自己，當某處食物濃度大時，也會導致群體覓食。

3）追尾行為。當魚群中某條或幾條魚發現了食物時，會將信息傳遞給周圍的魚，使周圍的魚向食物游來，信息會不斷傳遞下去。

4）隨機行為。魚會在水中自由游動，為了更好的尋找食物和同伴。以上的4種行為會在周圍環境發生變化時進行轉變，以更好地覓食。

5）粒子群算法初期收斂速度快，但是雖然引入了慣性權重，提升了穩定性，但是在水流的影響下，后期尋優效果并不理想，容易陷入局部最優解。相比改進粒子群算法，人工魚群算法前期收斂速度慢，后期尋優效果好，二者可以完美的將優勢互補。

3 仿真與結果分析

對于區域覆蓋部署問題，本文設定每條人工魚代表一個節點，區域覆蓋度為算法的適應度函數，采用Matlab對特定場景進行了仿真分析。仿真場景設定為：部署區域為長800 m、寬700 m的長方形范圍。并假設節點的通信范圍大于2倍的節點感知范圍，以保證網絡的連通性。當節點感知半徑為90 m，通信距離200 m，步長20 m，最大試探次數try number 20次，擁擠度因子0.2，節點數目20，迭代500次，初始位置為隨機位置。假定部署區域存在沿X軸方向的水流，流速 1 m/s，使用人工魚群算法，得到結果如圖4～圖6所示。

由圖可知，基于粒子群與人工魚群混合部署優化算法的覆蓋率提高了25%，且覆蓋度曲線初期收斂快，后期尋優效果有明顯提升，達到預期效果。

圖4 優化算法仿真圖Fig.4 Simulation diagram of optimization algorithm

圖5 優化曲線Fig.5 Optimization curve

圖6 收斂速度對照圖Fig.6 Control diagram of convergence rate

4 結 語

本文主要解決水下無人集群部署的問題，采用改進粒子群算法和人工魚群算法的混合算法進行水下無人集群的部署。這個方法克服了粒子群算法的后期尋優效果差以及人工魚群算法前期收斂效果慢的缺點，將水下無人集群的部署達到了一個令人滿意的效果。