基于遺傳退火算法的水下傳感器部署優化方法＊

胡 煒 曾 斌

（海軍工程大學管理工程系 武漢 430033）

基于遺傳退火算法的水下傳感器部署優化方法＊

胡 煒 曾 斌

（海軍工程大學管理工程系 武漢 430033）

水下傳感器部署是構建水下傳感器網絡從而對重點海域可能的敵方水下入侵行為進行監測預警的關鍵環節。利用a－hoc網絡中經典網格拓撲結構對傳感器節點部署進行規劃。分析水聲環境復雜性，采用Urick的聲納效能系列公式，將節點穿透網格單元的信號強度轉化為適應度，運用遺傳退火算法對傳感器節點部署進行優化，有效提高了部署區域的適應度值，進而提升了整體網絡性能。通過Matlab仿真驗證了混合算法的可行性和優越性。

部署；網格拓撲結構；信號強度；適應度；遺傳退火算法

Class NumberTP212

1 引言

近年來，隨著海洋建設的快速發展，海上威脅日益嚴峻。特別是在面臨來自水下威脅時，主要手段還是依靠艦船自攜的聲納或反潛直升機，難以形成全天候、大范圍的警戒體系。為了彌補水下監測能力的不足，需要建立水下傳感器監測網絡來提升在重點海域、重點目標區域對敵方入侵的監測水平。這樣的海域往往是海上一塊重點探測區域或者一個具有軍事用途（高價值目標）的港口近海區域，然而在這樣的區域設計水下傳感器網絡帶來的困難有：水聲環境復雜和聲波衰減迅速。傳感器的探測及通信性能受影響因素多且變化大，不易計算。此外，對于設計者來說，傳感器的數量以及部署這些傳感器所帶來的高額成本也是必須考慮的重要因素。目前，在節點部署方面，趙小敏等［1］在AIO（area of interest）不規則前提下，提出了基于Delaunay三角化與網格的傳感器隨機部署法；Linfeng Liu等［2］提出了一種建立在水下信號不規則基礎上的傳感器網絡拓撲結構控制模型；Erick F.Golen［3］則在給定概率條件下將監測區域分割成不同子區域，在考慮單向博弈行為的基礎上采用遺傳算法求解節點部署的最優解。

本文在Golen的基礎上，充分考慮到水聲環境的復雜性，將水聲環境劃分為六個主要影響因素，在Urick的被動聲納探測效能公式基礎上，采用ad－hoc網絡中網格拓撲結構作為傳感器網絡結構，進而將部署區域分割為各網格單元，運用改進的遺傳退火混合算法對節點部署策略進行優化，進而提升傳感器在部署區域的整體探測性能［4～6］。

2 遺傳退火混合算法優勢特點

首先，遺傳算法作為一種優化方法，存在以下主要幾點局限性：

1）單一的遺傳算法編碼無法全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解采用閾值，但這樣算法計算的時間必然增加；2）遺傳算法容易出現過早收斂；3）像其他算法一樣，遺傳算法也容易陷入局部極值。

相比之下，模擬退火算法作為一種隨機搜索算法具有以下幾個優勢：1）與局部搜索法相比，模擬退火法能以一定概率接受惡化解從而擴大搜索空間，使迭代過程易跳出局部最優陷阱，增大搜索到全局最優解的機；2）理論上模擬退火法搜索到全局最優解的概率為1，合理選取冷卻溫度梯度和進度范圍，模擬退火法能在有效的時間內獲得較高質量的全局最優解。

綜合上述所列的兩種算法的特點，針對單一遺傳算法存在的先天性缺點，利用模擬退火算法的優點，針對性的對遺傳算法進行改進。在遺傳算法的交叉和變異過程中引入模擬退火的Metropolis接受準則，這樣不僅能夠縮短算法的運行時間，也可以有效避免單一遺傳算法容易陷入局部極值和過早收斂的問題。

3 水下傳感器部署混合優化算法實現

3.1 水聲環境特點

針對某一個重點海域（如附有高價值軍事用途的港口或海上某一片重點監測區域），水下地理環境的復雜性、介質對信號的吸收、水聲環境噪聲等都對傳感器探測和通信性能造成重要干擾（如探測和通信有效范圍降低、傳感器節點間數據傳輸延遲增加以及數據傳輸速率受限等）。此外，水下間歇性產生的氣泡和海底地震產生的沖擊波也會對傳感器性能，尤其是網絡整體的通信鏈接效能造成間歇干擾。

為了充分描述針對監測敵方入侵而建立的水下傳感器網絡的水聲環境特點以及所帶來的影響，這里將它們劃分為六個主要影響因子：1）探測范圍；2）通信范圍；3）成本；4）鏈路冗余；5）范圍依賴因子；6）敵方入侵的可能性。

3.2 部署區域的節點拓撲結構

網格拓撲（mesh）結構的概念在無線傳感器網絡中，特別是a－hoc網絡中具有重要意義。網格的劃分為整個網絡提供了多種通信鏈接路徑以此來增強連通性能［7］。

圖1 網格結構的節點連接示意圖

一個網格拓撲結構的連接冗余度可以由最小分割集的大小來決定，即為了分割該網絡所必須移除的節點之間的連接數量。例如在某次間歇性環境影響下，節點f和d以及f和c之間的連接間斷，那么該網格拓撲結構就被分割成了兩個部分。若此時i節點獲得了探測數據，那么數據是無法傳輸到a節點（假設臨近某個數據中轉站）的。Stoer將圖論的方法應用到如何定量一塊網格區域的最小分割集大小［9］。那么，不難從邏輯上推理出：某一網格區域的最小分割集大小越高，該區域所在傳感器節點的探測范圍在某種程度上就越大［6］。

3.3 算法描述

第一步：初始種群構建

在二維直角坐標系中，傳感器部署區域表示為一系列N個二維傳感器位置坐標集：

G是染色體，每一個傳感器節點的二維坐標就是一個基因。起初，部署區域可以根據經驗數據庫里的水聲環境累積數據，采用一種學習算法（如自組織適應圖）劃分為具有相似水聲環境的多個子區域，各子區域是可以獨立優化且在算法開始前區域里已經包含了固定數量的傳感器。假設rc為傳感器節點的有效通信半徑。起始傳感器節點被隨機部署在一個位置上，下一個傳感器的部署的位置需要滿足以下條件：

drand和θ為兩傳感器節點之間的隨機距離和水平基準角度。

第二步：區域評估和適應度計算

節點隨機部署完畢后，各劃分區域內傳感器節點之間的無向連接圖就生成了。根據網狀拓撲結構最小分割集大小的定義、水聲環境的優劣程度定義一個最小分割集閾值（MCSS）。假設MCSS閾值為3，傳感器部署區域MCSS值只有2，那么該區域的適應度即為0，以此阻止它進入下一代遺傳種群中。

若分割子區域滿足閾值限定條件后，將整個部署區域分割成邊長為1個標準單位的方形網格單元組。根據文獻［2～5］和Urick的被動聲納傳感器效能公式有：

當信號穿透強度為0時，表明敵方在該網格單元里被瞬時或固定探測發現的概率為0.5。很顯然，當信號穿透強度越高，固定探測發現（probability of detection，POD）的概率就越高［6］。

式（4）表示對某個位置（i，j）上的網格單元來說，信號穿透強度大小應該取區域當中N個傳感器信號穿透強度里的最大值。

式（5）～（7）在文獻［5］中用來將網格單元的信號穿透強度轉換為POD。其中，式（5），式（6）表示的是一個六維多項式曲線擬合方法，A＝［1，0.0705，0.04223，0.00927，0.000152，0.000277，0.00000431］公式（7）中，SD為正太分布的標準偏差，一般值取6dB。

只要每個網格單元的信號穿透強度轉換為POD，那么傳感器部署全區域的適應度就可以表示為

α是全區域的長度，β為寬度。α、β值的大小決定了在二維坐標系中X軸和Y軸方向上有多少網格單元。

很顯然，當適應度值增加，傳感器在部署區域的整體表現性能也隨之提升。

第三步：設計選擇算子，移除相對較低的適配值的個體

計算個體的適應度，選擇使用比例算子，即假設種群數量為W，個體i的適應度為Fni，則個體i被選中的概率為

隨機產生（0，1］之間的隨機數，如果個體Pi大于或等于該隨機數，則被選中，小于則被淘汰［10］。

第四步：交叉操作并應用模擬退火的Metropolis接受準則（選擇H（xi）＝（1－Fn（xi））作為目標函數）生成新種群。

將新種群的染色體進行交叉操作，在給定交叉概率條件下交叉基因（即傳感器位置坐標）隨機選擇，用于交叉操作的基因數量限制在［1，2／N（取下限）］之間。

圖2 交叉操作示例圖

分別計算交叉前父代個體a和個體b的適應度值分別為Fn（a）和Fn（b），交叉后子代個體a′和個體b′的適應度值為Fn（a′）和Fn（b′），根據上述模擬退火的Metropolis接受準則可得：

隨機產生一個隨機數random（r）∈（0，1］，判斷滿足條件生成新種群，執行下一步，否則重新返回。

第五步：對第四步得到的新種群執行變異操作，同樣也將Metropolis接受準則應用到變異操作中，得到新種群。

圖3 變異操作示例圖

隨機產生一個隨機數random（r）∈（0，1］，判斷滿足條件生成新種群，執行下一步，否則重新返回。

第六步：將上述生成的新種群賦給初始種群，并判斷迭代次數是否達到最大遺傳代數，滿足則轉入第七步，否則轉入第四步。

第七步：更新溫度和初始種群。若達到終止準則（終止溫度），則停止計算，輸出最優解。否則，轉入第四步。

4 仿真實現

4.1 仿真參數設置

表1 仿真參數設置表

4.2 Matlab仿真結果圖

圖4 MCSS取值2時的適應度值變化圖

圖5 MCSS取值為4時的適應度變化圖

5 結語

本文對水下傳感器網絡節點區域優化部署進行研究，在分析六種水下聲學環境影響因子的基礎上，通過引入a－hoc網絡中經典的網格拓撲結構完成了傳感器節點的區域初步部署規劃，進而利用Urick關于被動聲納水下效能系列公式，將節點穿透網格單元的信號強度轉化為適應度值，設計并運用遺傳算法和模擬退火相結合的混合算法來對節點部署進行優化。Matlab仿真結果顯示了，在不同最小分割集大小的約束下，經過混合算法的優化，對比傳統遺傳算法，有效提高了區域的適應度值且收斂性更好，進而提升了傳感器部署區域的整體表現，證明了混合算法的可行性和優越性。

［1］趙小敏，毛科技，何文秀.感測范圍不規則情況下無線傳感器網絡節點部署算法［J］.軟件學報，2012，29（15）：59－68.

［2］Linfeng Liu，Ningshen Zhang，Ye Liu.Reasearch on Arichitecture for Reconfigurable Underwater Sensor Networks［C］／／Proc of IEEE Conf on Networking Sensing and Control.Arizona：IEEE，2005：831－834.

［3］E.F.Golen，N.Shenoy，B.I.Incze.UnderwaterSensor Field Design Using Game Theory［C］／／Military Communications Conference，Orlando，FL，2007（19）：188－199.

［4］Ptan，J.Kurose，B.N.Levine.A Survey of Practical Issues in Underwater Networks［J］.WUWNet，2006（6）：17－24.

［5］R.J.Urick.Principle of Underwater Sound，3rd Edition，Peninsula Publishing，Los Altos，CA，1983：108－117.

［6］Erick F.Golen.Intelligent Deployment Strategies For Passive Underwater Sensor Networks［D］.United States：Golisnano College of Compiting and Information Sciences，Rochester Institute of Technology，2009（4）：323－330.

［7］I.F.Akyildiz，D.Pompili，T.Melodia.Underwater Acoustic Sensor Networkd Research Challenges［J］.Ad Hoc Networkd，2005（5）：189－201.

［8］雷英強，張善文.遺傳算法工具箱及應用［M］.西安：西安電子科技大學出版社，2014：37－55.

［9］楊漢橋，林曉輝.遺傳算法和模擬退火法尋優能力綜述［J］.機械制造與研究，2009，27（4）：73－75.

［10］M.Stoer，F.Wanger.A Simple Min－Cut Algorithm［J］.Journal of the ACM，1997，44（4）：585－591.

An Optimization Method of Underwater Sensors Deployment Based on Genetic and Anneal Algorithm

HU Wei ZENG Bin
（Department of Management and Engineering，Naval University of Engineering，Wuhan 430033）

The deployment of underwater sensors is the key link for establishing an underwater sensor network，which will be used for detecting and early warning the invasion from enemies underwater.The topological structure of the mesh from the classic a－hoc network is used for deploying sensors.The complexity of the underwater acoustic environment is analyzed and a series of formulas of sonar performance from Urick's are used.By this way，the signal excess of grid cells can be transmitted to the value of fitness.Then，genetic and anneal algorithm is used to optimize the deployment of sensors，which can effectively improve the fitness value of deployment area and further improve the overall underwater network performance.The feasibility and superiority of genetic and anneal algorithm are verified through the simulation by Matlab.

deployment，topological structure of the mesh，signal intensity，fitness，genetic and anneal algorithm

TP212DOI：10.3969／j.issn.1672－9730.2015.11.007

2015年5月1日，

2015年6月28日

湖北省基金項目：稀疏動態水下傳感器網絡優化部署（編號：2011CDD051）資助。

胡煒，男，碩士研究生，研究方向：水下傳感器網絡。曾斌，男，博士，教授，碩士生導師，研究方向：水下傳感器網絡、管理信息系統，裝備維修。