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

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

0 引 言

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

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

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

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

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

1.1 節(jié)點(diǎn)覆蓋率

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

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

圖1 海上場(chǎng)景示意圖Fig.1 Schematic diagram of the sea scene

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

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

1.2 區(qū)域覆蓋率

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

2 優(yōu)化算法

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

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

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

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

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

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

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

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

2.3 粒子群-人工魚群算法

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

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

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

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

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

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

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

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

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

對(duì)于區(qū)域覆蓋部署問題，本文設(shè)定每條人工魚代表一個(gè)節(jié)點(diǎn)，區(qū)域覆蓋度為算法的適應(yīng)度函數(shù)，采用Matlab對(duì)特定場(chǎng)景進(jìn)行了仿真分析。仿真場(chǎng)景設(shè)定為：部署區(qū)域?yàn)殚L800 m、寬700 m的長方形范圍。并假設(shè)節(jié)點(diǎn)的通信范圍大于2倍的節(jié)點(diǎn)感知范圍，以保證網(wǎng)絡(luò)的連通性。當(dāng)節(jié)點(diǎn)感知半徑為90 m，通信距離200 m，步長20 m，最大試探次數(shù)try number 20次，擁擠度因子0.2，節(jié)點(diǎn)數(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 收斂速度對(duì)照?qǐng)DFig.6 Control diagram of convergence rate

4 結(jié) 語

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