水下傳感器網絡覆蓋優化算法＊

郭 勇 姜衛東 劉胤祥

（海軍指揮學院信息系 南京 211800）

1 引言

水下傳感器網絡部署分為確定部署和隨機部署，隨機部署存在網絡節點分布不均，覆蓋率低等問題。而目前針對水下傳感器網絡隨機部署后的覆蓋優化問題研究并不多，由于水下傳感器網絡是無線傳感器網絡在水下的延伸［4］，可借鑒無線傳感器網絡對該問題展開研究。針對無線傳感器網絡覆蓋，林祝亮［5］提出了基于概率測量模型的粒子群優化策略，以網絡有效覆蓋率為優化目標，通過粒子群算法實現有效覆蓋；賈杰［6］針對傳感器節點密度高的特點，研究了工作節點集選取問題，提出了基于加權遺傳算法和基于約束遺傳算法的優化覆蓋機制，延長了網絡生存時間；王蕊［7］針對由少量移動節點和固定節點組成的無線傳感器網絡提出了一種基于魚群算法的優化部署方案，該方案以網絡覆蓋率為目標函數，將移動節點的位置遷移過程抽象為人工魚的追尾和覓食行為，并在人工魚的狀態更新過程中加入虛擬力影響因子來引導人工魚的游動方向，有效提高了網絡覆蓋率，優化了網絡性能。

2 模型描述

本文考慮在邊長為L的正方形區域部署N個傳感器節點組成一個二維水聲網絡，其中N1個固定節點，N2個移動節點。在實際的軍事或工程應用中固定節點可由固定水聲站或錨節點水聲器充當；移動節點可由水下AUV擔任。在監測區域外圍部署匯聚節點進行覆蓋優化計算并將結果發送給移動節點，移動節點按照指令移動到指定位置，從而優化網絡部署，提高網絡覆蓋率。

2.1 網絡模型

1）傳感器節點采用布爾感知模型［8］，每個節點抽象為一個點，具有相同的感知半徑Rs；

2）網絡初始化時，所有節點分布在（0，0）～（L，L）的正方形區域范圍內，每個傳感器節點位置已知，且能感知周圍節點位置；

3）監測區域之外的匯聚節點能量不受限制，可與傳感器節點進行直接或間接通信；

4）為降低能耗，在算法執行中，傳感器節點不移動，只在優化算法結束后才移動到最終位置。

2.2 人工魚群算法網絡覆蓋優化模型

設當前網絡中傳感器節點矢量為Z＝［，，…，，…，］T（i∈［1，N］）。其中Psi為第i個傳感器節點，其位置為（xi，yi）。

類風濕關節炎是一種自身免疫性、以炎癥細胞因子浸潤和慢性炎癥反應的疾病。RA臨床表現為關節慢性炎癥浸潤、關節疼痛、關節腫大和畸形。及早診斷類風濕關節炎和抑制炎癥反應對類風濕關節炎治療和預后至關重要［10-11］。本論文中，我們發現P2X7受體在類風濕關節炎患者滑膜組織中高表達，且對類風濕關節炎具有較好的診斷價值。此外，P2X7受體與炎癥細胞因子密切相關，抑制P2X7受體的表達可抑制關節滑膜細胞的炎癥細胞因子分泌和炎癥反應，表明P2X7受體不僅是類風濕關節炎的診斷標志物，也是治療類風濕關節炎的潛在靶點。

初始化生成M條人工魚Z1，Z2，…，Zj，…，ZM（j∈［1，M］），每條人工魚都有N個傳感器節點分布在監測區域內，其中Zj＝［，，…，，…，PsjN］T（i∈［1，N］，j∈［1，M］），既表示人工魚又表示人工魚狀態。為簡化處理，假設第j條人工魚Zj中第i個傳感器sji為Zj中到當前傳感器網絡中第i個傳感器si最近的傳感器節點。設T為當前傳感器節點對監測區域的覆蓋率，則Tj（j∈［1，M］）為第j條人工魚對監測區域覆蓋率。

定義兩條人工魚Za和Zb（a，b∈［1，M］，a≠b）的距離為

人工魚的一些其他參數不作詳細介紹，只將其簡述如下：Visual為人工魚的感知視野，λ為人工魚的步長，δ為人工魚的擁擠度因子。設置公告板，記錄最優目標函數值Tk和最優人工魚Zk。

3 水下傳感器網絡覆蓋優化

3.1 改進全局人工魚行為在覆蓋率優化中的描述

魚群算法是一種群智能優化算法［9～10］，江銘炎［11］在人工魚搜索過程中加入最優人工魚信息來加速人工魚尋優的收斂速度，即全局人工魚群算法。然而其向最優人工魚移動的比例是一定的，不能根據情況動態變化，尋優速度和精度受限，針對以上問題，本文在人工魚行為中引入權重系數，加速算法收斂。改進的追尾行為描述如下：

設人工魚i當前狀態為Zi，目標函數值為Ti。探索其當前鄰域內d（d＜Visual）目標函數值Tj最大的伙伴Zj，Zj鄰域內伙伴數為nf。若Tj／nf＞δTi，則人工魚i朝伙伴Zj和最優人工魚Zk方向移動一步：

Random（0，λ）是一個在（0，λ）之間隨機分布的2N維向量，c是權重系數，是向最優人工魚靠攏的比例，若人工魚i離最優人工魚較遠，則c較大，向最優人工魚移動較多，加速算法收斂；若人工魚i離最優工魚較近，則c較小，向最優人工魚移動較少，在目標人工魚附近尋優。若不滿足條件則執行聚群行為，聚群、覓食行為的權重系數引入方法和追尾行為類似，此處不再贅述，隨機行為與魚群算法一樣。

每次行動完畢后，人工魚將自己的目標函數值與公告板比較，若好于公告板，則更新公告板中的最優目標函數值Tk和最優人工魚Zk。

3.2 步長變化公式

人工魚群算法雖然有很多優點，但也存在后期收斂慢，尋優精度不高等缺陷，這是由于人工魚的步長是固定值，隨著目標函數值的升高，固定步長使得人工魚在最優值附近震蕩，無法到達最優值。

為了克服以上缺點，引入可變步長［12］。隨著目標函數值的升高，動態地縮小步長，提高搜索精度，步長調整公式為

T是當前最優目標函數值，Tset是設定的目標函數值，λmin是最小步長。隨著當前最優目標函數值的升高，步長慢慢變小，人工魚尋優精度提高。

3.3 改進全局人工魚群算法對網絡覆蓋優化步驟

根據上述改進算法，對水下傳感器網絡的覆蓋率優化步驟如下：

1）初始化M條人工魚，每條人工魚都有N個傳感器節點的位置坐標；

2）設置覆蓋率目標值Tset、運算輪數n、人工魚步長、最小步長等參數，并將第一條人工魚設為最優人工魚Zk；

3）按照條件執行改進全局人工魚群算法的追尾、聚群、覓食和隨機等行為，并按照式（4）更改步長；

4）檢查執行后的覆蓋率是否提高，若提高則更新最優目標函數值和最優人工魚；

5）若達到覆蓋率目標值或者超出設置輪數，則執行步驟6），否則執行步驟3）；

6）輸出最優覆蓋率和最優人工魚。

4 實驗仿真

為驗證改進全局人工魚群算法對水下傳感器網絡的覆蓋優化性能，將其與遺傳算法和魚群算法進行了對比實驗，實驗參數如表1所示。

表1 改進全局人工魚群和魚群算法的實驗參數

圖1 三種算法覆蓋率對比圖

由于傳感器初始分布具有一定的隨機性，所以分別對三種算法進行了50次仿真，圖1為覆蓋率平均值與輪數的關系。圖2～圖5為初始時和三種算法優化后的一次傳感器分布，其中實心圓代表固定傳感器及其感知范圍，空心圓代表移動傳感器及其感知范圍。

圖2 初始隨機網絡分布

圖3 遺傳優化網絡分布

圖4 魚群優化網絡分布

圖5 改進全局魚群優化網絡分布

從圖1可以看出，初始時，15個固定節點和35個移動節點組成的網絡覆蓋率為55%左右，隨著輪數的增加，遺傳算法、魚群算法和改進的全局人工魚群算法50輪優化后的網絡平均覆蓋率依次為71.92%、78.47%和85.75%，改進全局人工魚群算法優化后的覆蓋率要高于其他兩種算法，且收斂較快。由圖2～圖5可知，隨機部署后傳感器分布不均勻，有很大區域未被傳感器覆蓋，遺傳算法和魚群算法優化后都有部分覆蓋盲區，而全局人工魚群算法優化后傳感器覆蓋盲區較小。可見，改進全局人工魚群算法在水下傳感器網絡覆蓋優化方面具有覆蓋率高和節點分布均勻等優點。

5 結語

本文將全局人工魚群算法應用到水下傳感器網絡覆蓋優化問題中，在魚群算法的四種行為中加入了按一定比例向最優人工魚移動的過程，并根據覆蓋率動態改變人工魚步長。實驗結果表明，改進的全局人工魚群算法較遺傳算法和魚群算法在水下傳感器網絡覆蓋優化中網絡覆蓋率高、優化速度快，能有效提升網絡性能。

［1］Dario Pompili.Efficient Communication Protocols For Underwater Acoustic Sensor Networks［D］.Atlanta：Georgia Institute of Technology，2007.

［2］李淑秋，李啟虎，張春華.水下聲學傳感器網絡的發展和應用［J］.聲納技術及應用專題，2006，35（11）：945－952.

［3］郭忠文，羅漢江，洪鋒.水下無線傳感器網絡的研究進展［J］.計算機研究與發展，2010，47（3）：377－389.

［4］王長生.水下傳感器網絡節點布置方法研究［D］.合肥：合肥工業大學，2011.

［5］林祝亮，馮遠靜.基于粒子群算法的無線傳感器網絡覆蓋優化策略［J］.計算機仿真，2009，26（4）：190－193.

［6］賈杰，陳劍，常桂然.無線傳感器網絡中基于遺傳算法的優化覆蓋機制［J］.控制與決策，2007，22（11）：1289－1292.

［7］王蕊，劉國枝.基于魚群優化算法的無線傳感器網絡部署［J］.振動與沖擊，2009，28（2）：8－11.

［8］周利民，楊科華，周攀.基于魚群算法的無線傳感器網絡覆蓋優化策略［J］.計算機應用研究，2010，27（6）：2276－2279.

［9］李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法［J］.系統工程理論與實踐，2002，22（11）：32－38.

［10］李曉磊，錢積新.基于分解協調的人工魚群優化算法［J］.電路與系統學報，2003，8（1）：1－6.

［11］江銘炎，袁東風.人工魚群算法及其應用［M］.北京：科學出版社，2012：110－111.

［12］王聯國，洪毅，施秋紅.全局版人工魚算法［J］.系統仿真學報，2009，21（23）：7483－7486.