水下無人集群優(yōu)化部署算法設(shè)計與分析

佟 盛，李大輝，戴學(xué)豐

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

0 引 言

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

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

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

本文主要采用布爾感知模型重點研究區(qū)域覆蓋，利用粒子群優(yōu)化算法與人工魚群優(yōu)化算法進(jìn)行混合編程，完成水下移動節(jié)點部署優(yōu)化，從而實現(xiàn)對目標(biāo)區(qū)域高覆蓋度的部署目標(biāo)。重點完成水下無人集群節(jié)點部署優(yōu)化方案和仿真實驗設(shè)計，主要利用粒子群優(yōu)化算法與人工魚群優(yōu)化算法混合完成水下無人集群對水下環(huán)境的覆蓋。利用粒子群算法初期收斂快的特點，進(jìn)行初期尋優(yōu)，再用人工魚群算法進(jìn)行后期尋優(yōu)，二者優(yōu)勢互補(bǔ)，完成對集群節(jié)點部署優(yōu)化。

1 網(wǎng)絡(luò)覆蓋模型

1.1 節(jié)點覆蓋率

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

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

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

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

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

1.2 區(qū)域覆蓋率

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

2 優(yōu)化算法

2.1 標(biāo)準(zhǔn)粒子群算法

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

圖2 標(biāo)準(zhǔn)粒子群算法流程圖Fig.2 Flow chart of standard particle swarm algorithm

整個種群的當(dāng)前最優(yōu)解被稱為全局極值（gbest）。每次迭代過程中，Pbest和gbest都會更新，如果迭代次數(shù)足夠多，Pbest和gbest最終會趨于穩(wěn)定，算法結(jié)束后gbest即整個算法求得的最優(yōu)解。

2.2 改進(jìn)粒子群算法

標(biāo)準(zhǔn)粒子群算法收斂較快，但后期尋最優(yōu)解效果較差，容易陷入局部最優(yōu)，真實部署時不僅浪費(fèi)時間，還浪費(fèi)節(jié)點能量，本項目將引入線性遞減慣性權(quán)重系數(shù)，如式（6）所示，采用線性遞減慣性權(quán)重可以加強(qiáng)前期全局搜索能力，控制后期的局部搜索能力，避免算法陷入局部極值。權(quán)重系數(shù)

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

每次迭代過程中，選出每個粒子中距離最近的兩個節(jié)點，對這兩個節(jié)點進(jìn)行位置進(jìn)行二次調(diào)節(jié)，使其相互遠(yuǎn)離。

2.3 粒子群-人工魚群算法

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

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

假設(shè)某條人工魚當(dāng)前狀態(tài)為x，魚會在當(dāng)前視野范圍內(nèi)選一個狀態(tài)x，如果狀態(tài)y優(yōu)于狀態(tài)x，則魚移動到y(tǒng)，否則不移動。人工魚會以此方式試探Tnum次，選出狀態(tài)最好的一個為x的下一個狀態(tài)。如果Tnum次試探后沒有比x更好的狀態(tài)，人工魚將執(zhí)行其他行為，如隨機(jī)游動。

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

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

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

4）隨機(jī)行為。魚會在水中自由游動，為了更好的尋找食物和同伴。以上的4種行為會在周圍環(huán)境發(fā)生變化時進(jìn)行轉(zhuǎn)變，以更好地覓食。

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

3 仿真與結(jié)果分析

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

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

圖4 優(yōu)化算法仿真圖Fig.4 Simulation diagram of optimization algorithm

圖5 優(yōu)化曲線Fig.5 Optimization curve

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

4 結(jié) 語

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