胡 煒 曾 斌

（海軍工程大學(xué)管理工程系 武漢 430033）

基于遺傳退火算法的水下傳感器部署優(yōu)化方法＊

胡 煒 曾 斌

（海軍工程大學(xué)管理工程系 武漢 430033）

水下傳感器部署是構(gòu)建水下傳感器網(wǎng)絡(luò)從而對重點海域可能的敵方水下入侵行為進行監(jiān)測預(yù)警的關(guān)鍵環(huán)節(jié)。利用a－h(huán)oc網(wǎng)絡(luò)中經(jīng)典網(wǎng)格拓撲結(jié)構(gòu)對傳感器節(jié)點部署進行規(guī)劃。分析水聲環(huán)境復(fù)雜性，采用Urick的聲納效能系列公式，將節(jié)點穿透網(wǎng)格單元的信號強度轉(zhuǎn)化為適應(yīng)度，運用遺傳退火算法對傳感器節(jié)點部署進行優(yōu)化，有效提高了部署區(qū)域的適應(yīng)度值，進而提升了整體網(wǎng)絡(luò)性能。通過Matlab仿真驗證了混合算法的可行性和優(yōu)越性。

部署；網(wǎng)格拓撲結(jié)構(gòu)；信號強度；適應(yīng)度；遺傳退火算法

Class NumberTP212

1 引言

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

本文在Golen的基礎(chǔ)上，充分考慮到水聲環(huán)境的復(fù)雜性，將水聲環(huán)境劃分為六個主要影響因素，在Urick的被動聲納探測效能公式基礎(chǔ)上，采用ad－h(huán)oc網(wǎng)絡(luò)中網(wǎng)格拓撲結(jié)構(gòu)作為傳感器網(wǎng)絡(luò)結(jié)構(gòu)，進而將部署區(qū)域分割為各網(wǎng)格單元，運用改進的遺傳退火混合算法對節(jié)點部署策略進行優(yōu)化，進而提升傳感器在部署區(qū)域的整體探測性能［4～6］。

2 遺傳退火混合算法優(yōu)勢特點

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

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

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

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

3 水下傳感器部署混合優(yōu)化算法實現(xiàn)

3.1 水聲環(huán)境特點

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

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

3.2 部署區(qū)域的節(jié)點拓撲結(jié)構(gòu)

網(wǎng)格拓撲（mesh）結(jié)構(gòu)的概念在無線傳感器網(wǎng)絡(luò)中，特別是a－h(huán)oc網(wǎng)絡(luò)中具有重要意義。網(wǎng)格的劃分為整個網(wǎng)絡(luò)提供了多種通信鏈接路徑以此來增強連通性能［7］。

圖1 網(wǎng)格結(jié)構(gòu)的節(jié)點連接示意圖

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

3.3 算法描述

第一步：初始種群構(gòu)建

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

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

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

第二步：區(qū)域評估和適應(yīng)度計算

節(jié)點隨機部署完畢后，各劃分區(qū)域內(nèi)傳感器節(jié)點之間的無向連接圖就生成了。根據(jù)網(wǎng)狀拓撲結(jié)構(gòu)最小分割集大小的定義、水聲環(huán)境的優(yōu)劣程度定義一個最小分割集閾值（MCSS）。假設(shè)MCSS閾值為3，傳感器部署區(qū)域MCSS值只有2，那么該區(qū)域的適應(yīng)度即為0，以此阻止它進入下一代遺傳種群中。

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

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

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

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

只要每個網(wǎng)格單元的信號穿透強度轉(zhuǎn)換為POD，那么傳感器部署全區(qū)域的適應(yīng)度就可以表示為

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

很顯然，當適應(yīng)度值增加，傳感器在部署區(qū)域的整體表現(xiàn)性能也隨之提升。

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

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

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

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

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

圖2 交叉操作示例圖

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

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

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

圖3 變異操作示例圖

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

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

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

4 仿真實現(xiàn)

4.1 仿真參數(shù)設(shè)置

表1 仿真參數(shù)設(shè)置表

4.2 Matlab仿真結(jié)果圖

圖4 MCSS取值2時的適應(yīng)度值變化圖

圖5 MCSS取值為4時的適應(yīng)度變化圖

5 結(jié)語

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

［1］趙小敏，毛科技，何文秀.感測范圍不規(guī)則情況下無線傳感器網(wǎng)絡(luò)節(jié)點部署算法［J］.軟件學(xué)報，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，F(xiàn)L，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］雷英強，張善文.遺傳算法工具箱及應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2014：37－55.

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

［10］M.Stoer，F(xiàn).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－h(huán)oc 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日

湖北省基金項目：稀疏動態(tài)水下傳感器網(wǎng)絡(luò)優(yōu)化部署（編號：2011CDD051）資助。

胡煒，男，碩士研究生，研究方向：水下傳感器網(wǎng)絡(luò)。曾斌，男，博士，教授，碩士生導(dǎo)師，研究方向：水下傳感器網(wǎng)絡(luò)、管理信息系統(tǒng)，裝備維修。