基于蟻群“覓食”機制的深海自組織網絡路由算法F－ACO＊

田子希 胡洪寧 田林潔

（1.駐上海地區艦炮系統軍事代表室 上海 200135）（2.海軍工程大學 武漢 430033）

1 引言

基于節點地理位置信息的定向洪范算法能較好地解決在水聲網絡中尋找最優路徑的問題［1］。但是這種算法將加重網絡的負載，特別是當目標節點運動速度不大、網絡中節點密度很稀松時，容易造成算法失敗［13］。另外，在水下獲得高精度的節點地理位置信息較難，這對于地理路由算法而言無疑是雪上加霜。因此，尋找一種不借助節點地理位置信息、但又不降低性能的算法就顯得迫在眉睫了。

蟻群算法［2］最早是由 Marco Dorigo等學者在真實螞蟻覓食行為的啟發下提出的一種元啟發式算法。開始是為了解決TSP［3］（旅行商問題），在隨后短短的22年內，它的應用已經擴展到優化問題領域的方方面面，同時由最初的AS［2］算法衍生出一系列經典算法［4～5］，這些算法在組合優化問題方面取得了豐碩的成就［6］，國內有代表性的是張勇徳提出的多目標蟻群算法［7］以及金浩提出的“基于覓食－返巢機制”的蟻群算法 MO－FHACO［8］。其中，MO－FHACO算法的核心是將螞蟻的信息素分為食物信息素和蟻巢信息素。即，從蟻巢出發的螞蟻，釋放蟻巢信息素，循著食物信息素到達食物源；從食物源返回的螞蟻，釋放食物信息素，循著蟻巢信息素最終回到蟻巢［8］。雖然這種機制能較好的解決一些連續域多目標優化問題，但在算法的初期信息素仍然困乏，螞蟻比較盲目，收斂速度慢。這些問題導致蟻群算法很難在通信延時嚴重的稀疏深海自組織網絡加以應用。

本文受蟻群覓食返巢的這一整個生物過程啟發，提出一種新的“覓食”機制。并基于此機制提出一種新的深海自組織網絡蟻群優化算法F－ACO。該算法能較好地解決稀疏網絡普遍存在的“空洞”問題［9，11］；同時，隨著通信次數的增加，數據包將越來越集中于當前網絡最優路徑進行傳播，通信的時延與網絡能量的消耗也越來越小。

2 基于蟻群“覓食”機制的深海自組織網絡路由算法

2.1 “覓食”原理

遵循“食物的氣味”來尋找食物，是自然界大部分動物最重要的基本生存技能之一，螞蟻也不例外。本算法就是利用這一生物學特性，在蟻群算法中加入食物自身散發的信息素這一因素。即螞蟻行走時釋放螞蟻信息素，食物自身散發引導螞蟻前進方向的氣味信息素。

深海 水 聲 網 絡 由 兩 種 節 點 組 成［9，11］：super－node、normal－node。其中，normal－node構成深海通信網絡的主體，負責數據信息的傳遞；super－node負責信息的產生與接收，它既有“食物”性質，又有“蟻巢”性質。具體如下：

1）開始的時候，super－node均為“食物源”，設定好各自“氣味”傳遞的最大步數，在整個網絡中進行F－ACO算法的第一部分：氣味擴散算法。

2）當super－node有通信需求時，立即轉變為“蟻巢”，并依照網絡中各節點存放的目標super－node的“氣味”信息，出動“螞蟻”尋找兩個節點之間的通信路徑；

3）處于“食物源”的super－node，其“氣味”信息素以“洪范”的方式迅速在全網蔓延，“氣味”攜帶“食物源”的地理位置信息和標志信息；“氣味”η濃度大小由到達該normalnode的所用跳數多少決定：跳數越多，“濃度”η越小。

4）“目標蟻巢”以“食物氣味”作為信息素的初始條件，出動“螞蟻”到“食物源”；即開始“螞蟻”只走有“氣味”的路線；隨后，決定“螞蟻”路徑的由“氣味”和“信息素”共同決定；

2.2 信息素更新機制

信息素包括：“食物氣味”信息素和“螞蟻”信息素。

其中，“食物氣味”信息素是由“食物源”super－node發出的，發生在蟻群算法進行路徑尋找之前，用于對信息素的初始化。從“蟻巢”super－node出發的螞蟻初次尋找路徑時，其鄰節點的“食物氣味”越濃，則被選為螞蟻下一跳節點的概率越大。有了初始的食物信息素，螞蟻避免了開始尋找路徑時的盲目性。食物氣味信息素的更新公式為

其中，Γfood為“食物源”super－node的氣味信息素；L 表示氣味最大能傳遞的跳數，這也和自然界法則一致；k表示從“食物源”到達該點共花了k跳轉發；

在蟻群系統（ACS）［10］的更新機制基礎上，本算法螞蟻信息素的更新機制對局部更新策略進行了修改，具體更新機制如下：

1）路徑構建

位于節點（初始為super－node，中間為 normal－node）i的螞蟻c，根據偽隨機比例規則從其鄰節點中選擇節點j作為下一跳節點。這個規則［2］如下

其中，q是均勻分布在［0，1］中的一個隨機變量，實驗時取q0＝0.5為固定參數。

2）全局信息素更新

每次迭代后，只有一只螞蟻（至今最優螞蟻）被允許釋放螞蟻信息素：

其中，Cbs代表該螞蟻走過的路徑長度。實驗時ρ取0.5。

3）局部信息素更新

在路徑構建過程中，螞蟻每經過一條邊（i，j），都將更新該邊上的信息素，這一點與ACS算法一致，不同的是更新的規則不同，本算法按下式更新局部信息素：

其中，ε為蒸發系數，取0.1；Δτ0為螞蟻釋放的信息素，實驗時取0.2。這兩個值均為常數。初始的時候，默認網絡中任意邊的螞蟻信息素均為0.1。

2.3 減少水聲網絡通信負載的措施

傳統的ACO算法在路徑尋找時，需要花費大量的網絡通信負載和節點的信息發送能量，這對傳播時延大、網絡稀疏、節點能量有限的水下自組織網絡是大為不利的。因此，為了減少網絡通信負載，F－ACO算法進一步做以下處理：

1）氣味擴算算法部分在網絡節點播放自身信息、構建各自鄰節點表的時候進行。具體如下：

（1）和normal－node構建鄰節點表一樣，super－node節點也是每隔一段時間在一跳范圍內廣播帶有自身標識的信息幀。

（2）在網絡中只有super－node節點的信息幀被轉發。當normal－node接收到該信息幀時，首先判斷是否接收過該幀，接收過則直接丟棄，否則進一步判斷該幀是直接由super－node發送過來，還是由normal－node節點轉發過來的。如果是前者，則首先回應一個帶自身標識的ACK，通知super－node。然后將該幀中的步數減一，并在一跳范圍內廣播該幀；若是后者，則直接將該幀中的步數減一，然后在一跳范圍內廣播該幀一次。

2）將數據包的每一次傳遞作為螞蟻算法進行路徑尋找的一次迭代，同時對并行處理的螞蟻做以下處理：

（1）數據包分為包頭和包身。包身保存要發送的數據信息，包括源、目標節點；包頭用于處理螞蟻算法問題。保存的信息為：參加該數據包傳遞的各螞蟻相關信息以及對應螞蟻選擇的下一跳節點的標識集合。

（2）節點接收到數據包時，首先根據包頭的下一跳節點集合確定自己是否在選擇之列。如果不在，則直接丟棄該數據包；否則，進一步確定是哪幾只螞蟻選擇本節點的，然后保存這幾只螞蟻的相關信息，分別針對這幾只螞蟻進行下一跳節點選擇。包頭中其他沒有選擇本節點作為下一跳節點的螞蟻信息則直接被該節點刪除。

3 實驗驗證

實驗采用的是文獻［9，11～12］中所提及的網絡模型，整個水聲通信網絡由400個“normal”節點構成，這些“normal”節點均被隨機布置在10×10平方公里的正方形區域內，圖1給出了網絡中的節點初始分布情況。

圖1 網絡中節點的分布情況

初始化后，網絡中各節點構建相應的鄰節點表，同時FACO的第一部分算法也在此時進行。圖2給出了網絡中節點的鄰節點圖。為了加以區別，圖3給出了網絡中右上角的super－node（用“＋”表示）的進行氣味散布，而左下角super－node接收“氣味”的（用“藍色＋”表示）實際情況。顏色代表各節點的“氣味”濃度高低：濃度從高到底，顏色從紅轉變為藍。

圖2 節點的相鄰情況

圖3 “氣味”在網絡中的散布情況

由圖3可見，距離“食物源”super－node越“近”，“食物的氣味”越濃，中間的各節點顏色也越紅。

DREAM是一種典型的定向洪泛路由算法，具有一定的代表性，因此本文將以此協議作為參照，通過仿真對比來檢查F－ACO算法的性能。為了便于充分發揮DREAM算法的性能，除其他實驗條件與F－ACO算法一致外，實驗時還將網絡中所有節點的地理位置信息作為已知條件告知DREAM。

實驗場景為：一個super－node（左下“＋”）作為產生信息的源節點，在1小時內隨機發送100個數據包給另一個目標super－node（右上“＋”）的情況。DREAM算法運行時，網絡中所有節點均能獲得自身的地理位置信息；F－ACO算法運行時，則不能獲得節點的地理位置信息。

圖4、圖5分別給出了通信100次之后，兩種算法進行數據包傳遞的實際路徑。

由圖4不難發現，由于網絡的稀疏度較高，DREAM協議需要大量的節點參入到數據包的轉發和重傳過程中，但同時也保證了數據包沿著多條路徑成功到達目標節點，協議的健壯性較好，相應的網絡能量的消耗和資源的浪費也較大。同時，由于每次傳遞都是獨立事件，算法并不保存路由表，因此在下一次傳遞時，同樣甚至更多的網絡能量和資源將被消耗。

相較于DREAM算法，雖然F－ACO算法不能使用節點的地理位置信息，但是在氣味信息素與螞蟻信息素的雙重作用下，隨著通信次數的增加，算法將越來越收斂于當前最優的路徑進行數據包的傳遞，同時在2.3節介紹的減少網絡通信負載的措施下，F－ACO進行數據包傳遞時所消耗的能量和時間會越來越小，最終分別固定于某一值。圖6、圖7分別給出了兩種算法的時延對比圖和每次傳遞網絡能量消耗情況的對比圖。

圖4 通信100次后，采用DREAM算法的實際傳播情況

圖5 通信100次后，采用F－ACO算法的實際傳播情況

圖6 時延對比圖

圖7 每次傳遞消耗的網絡能量對比

F－ACO算法在前20次的數據包傳送過程中，氣味信息素的影響使得螞蟻偏重于選擇“氣味濃度”較高的節點。此時，螞蟻選擇路徑完全依賴氣味信息素，因此會有較多的節點參入路徑的選擇過程；在21次～100次數據包傳送期，路徑上信息素濃度的高低與信息素揮發系數成正比，而“氣味濃度”在全部通信過程中并沒有變化，使得螞蟻有更大的可能探索新的路徑。圖6、圖7中F－ACO的時延和能量損耗的抖動現象正是這種“探索”能力的有利證明。

DREAM算法不保存路由表，每次都利用節點的地理位置信息定向洪范數據包。在通信的初始階段，下一次傳送的數據包會受到上一次傳送的數據包的干擾而增加數據包的傳輸試驗，這也就解釋了在前五次數據包分別傳送時，傳播時延會略有上升的現象；在第五次數據包傳送之后，由于網絡中的負載已經達到一個穩定值，網絡的時延和每次傳播的能量損耗會穩定于一個固定值。而在整個實驗過程中，參入傳播的節點會基本不變，因此每次能量的損耗也將是一個固定值。

4 結語

針對深海水聲網絡無法獲知節點地理位置信息的情況，本文提出了一種替代高效地理路由協議的算法：FACO。該算法不需要知道節點的地理位置信息，路徑尋找過程和數據包傳遞同時進行，在“氣味”信息素與“螞蟻”信息素的雙重作用下，隨著通信次數的增加，數據包的傳遞路徑將越來越收斂于當前網絡最優路徑。實驗證明F－ACO算法在減小時延、節約網絡能源等性能方面都有出色的表現，在無法獲知節點地理位置信息的深海水聲網絡中具有良好的應用前景。

［1］I F Akyildiz，D Pompili，T Melodia.Underwater Acoustic Sensor Networks：Research Challenges［J］.Ad Hoc Networks，2005，3（3）：257－279.

［2］Marco Dorigo，Thomas Stutzle.Ant Colony Optimization［M］.America，Cambridge：The MIT Press，2004.

［3］COLORNI A，DORIGO M，MANIEZZO V，et al.Distributed optimization by ant colonies［C］／／Proc of the first European Conference on Artificial Life.Paris：Elsevier，1991：134－142.

［4］GAMBARDELLAL M，DORIGO M.Ant－Q：a reinforcement learning approach to traveling salesman problem［C］／／Proc of the 12th international Conference on Machine Learning，1995：252－260.

［5］Thomas S，HOLGER H H.MAX－MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889－914.

［6］Gambardella L M，Taillare E D，DORIGO M，et al.Ant colonies for the quadratic assignment problem［J］.Journal of the Operational Research Society，1999，50（2）：167－176.

［7］張勇德，黃莎白.多目標優化問題的蟻群算法研究［J］.控制與決策，2005，20（2）：170－173，178.

［8］金浩，劉維寧.基于覓食－返巢機制連續域蟻群算法［J］.計算機工程與應用，2012，48（1）：24－26.

［9］HU Hongning，LIU Zhong，YANG Bin.BFDREAM：A new routing protocol for deep sea acoustic network［C］／／2010IEEE 10th INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING PROCEEDINGS（ICSP2010）.Beijing：Springer Verlag，2010：2377－2381.

［10］Dorigo M，Gambardella L M.Ant Colony System：A cooperative learning approach to the traveling salesman problem［C］／／IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.

［11］HU Hongning，LIU Zhong，LI Lu.A real－time directed routing protocol based on projection of convex holes on underwater acoustic networks［C］／／The 3rd Internatioal Conference on Networks Security，Wireless Communications and Trusted Computing（NSWCTC2011）.Wuhan，2011：44－48.

［12］Rice J，Creber B，Fletcher C.Evolution of Seaweb Underwater Acoustic Networking［C］／／OCEANs 2000MTS／IEEE Conference and Exhibition，Providence，Rhode Island：IEEE，2000：2007－2017.