基于蟻群“覓食”機(jī)制的深海自組織網(wǎng)絡(luò)路由算法F－ACO＊

田子希 胡洪寧 田林潔

（1.駐上海地區(qū)艦炮系統(tǒng)軍事代表室 上海 200135）（2.海軍工程大學(xué) 武漢 430033）

1 引言

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

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

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

2 基于蟻群“覓食”機(jī)制的深海自組織網(wǎng)絡(luò)路由算法

2.1 “覓食”原理

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

深海 水 聲 網(wǎng) 絡(luò) 由 兩 種 節(jié) 點(diǎn) 組 成［9，11］：super－node、normal－node。其中，normal－node構(gòu)成深海通信網(wǎng)絡(luò)的主體，負(fù)責(zé)數(shù)據(jù)信息的傳遞；super－node負(fù)責(zé)信息的產(chǎn)生與接收，它既有“食物”性質(zhì)，又有“蟻巢”性質(zhì)。具體如下：

1）開始的時候，super－node均為“食物源”，設(shè)定好各自“氣味”傳遞的最大步數(shù)，在整個網(wǎng)絡(luò)中進(jìn)行F－ACO算法的第一部分：氣味擴(kuò)散算法。

2）當(dāng)super－node有通信需求時，立即轉(zhuǎn)變?yōu)椤跋伋病?，并依照網(wǎng)絡(luò)中各節(jié)點(diǎn)存放的目標(biāo)super－node的“氣味”信息，出動“螞蟻”尋找兩個節(jié)點(diǎn)之間的通信路徑；

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

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

2.2 信息素更新機(jī)制

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

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

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

在蟻群系統(tǒng)（ACS）［10］的更新機(jī)制基礎(chǔ)上，本算法螞蟻信息素的更新機(jī)制對局部更新策略進(jìn)行了修改，具體更新機(jī)制如下：

1）路徑構(gòu)建

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

其中，q是均勻分布在［0，1］中的一個隨機(jī)變量，實(shí)驗(yàn)時取q0＝0.5為固定參數(shù)。

2）全局信息素更新

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

其中，Cbs代表該螞蟻?zhàn)哌^的路徑長度。實(shí)驗(yàn)時ρ取0.5。

3）局部信息素更新

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

其中，ε為蒸發(fā)系數(shù)，取0.1；Δτ0為螞蟻釋放的信息素，實(shí)驗(yàn)時取0.2。這兩個值均為常數(shù)。初始的時候，默認(rèn)網(wǎng)絡(luò)中任意邊的螞蟻信息素均為0.1。

2.3 減少水聲網(wǎng)絡(luò)通信負(fù)載的措施

傳統(tǒng)的ACO算法在路徑尋找時，需要花費(fèi)大量的網(wǎng)絡(luò)通信負(fù)載和節(jié)點(diǎn)的信息發(fā)送能量，這對傳播時延大、網(wǎng)絡(luò)稀疏、節(jié)點(diǎn)能量有限的水下自組織網(wǎng)絡(luò)是大為不利的。因此，為了減少網(wǎng)絡(luò)通信負(fù)載，F(xiàn)－ACO算法進(jìn)一步做以下處理：

1）氣味擴(kuò)算算法部分在網(wǎng)絡(luò)節(jié)點(diǎn)播放自身信息、構(gòu)建各自鄰節(jié)點(diǎn)表的時候進(jìn)行。具體如下：

（1）和normal－node構(gòu)建鄰節(jié)點(diǎn)表一樣，super－node節(jié)點(diǎn)也是每隔一段時間在一跳范圍內(nèi)廣播帶有自身標(biāo)識的信息幀。

（2）在網(wǎng)絡(luò)中只有super－node節(jié)點(diǎn)的信息幀被轉(zhuǎn)發(fā)。當(dāng)normal－node接收到該信息幀時，首先判斷是否接收過該幀，接收過則直接丟棄，否則進(jìn)一步判斷該幀是直接由super－node發(fā)送過來，還是由normal－node節(jié)點(diǎn)轉(zhuǎn)發(fā)過來的。如果是前者，則首先回應(yīng)一個帶自身標(biāo)識的ACK，通知super－node。然后將該幀中的步數(shù)減一，并在一跳范圍內(nèi)廣播該幀；若是后者，則直接將該幀中的步數(shù)減一，然后在一跳范圍內(nèi)廣播該幀一次。

2）將數(shù)據(jù)包的每一次傳遞作為螞蟻算法進(jìn)行路徑尋找的一次迭代，同時對并行處理的螞蟻?zhàn)鲆韵绿幚恚?/p>

（1）數(shù)據(jù)包分為包頭和包身。包身保存要發(fā)送的數(shù)據(jù)信息，包括源、目標(biāo)節(jié)點(diǎn)；包頭用于處理螞蟻算法問題。保存的信息為：參加該數(shù)據(jù)包傳遞的各螞蟻相關(guān)信息以及對應(yīng)螞蟻選擇的下一跳節(jié)點(diǎn)的標(biāo)識集合。

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

3 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)采用的是文獻(xiàn)［9，11～12］中所提及的網(wǎng)絡(luò)模型，整個水聲通信網(wǎng)絡(luò)由400個“normal”節(jié)點(diǎn)構(gòu)成，這些“normal”節(jié)點(diǎn)均被隨機(jī)布置在10×10平方公里的正方形區(qū)域內(nèi)，圖1給出了網(wǎng)絡(luò)中的節(jié)點(diǎn)初始分布情況。

圖1 網(wǎng)絡(luò)中節(jié)點(diǎn)的分布情況

初始化后，網(wǎng)絡(luò)中各節(jié)點(diǎn)構(gòu)建相應(yīng)的鄰節(jié)點(diǎn)表，同時FACO的第一部分算法也在此時進(jìn)行。圖2給出了網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰節(jié)點(diǎn)圖。為了加以區(qū)別，圖3給出了網(wǎng)絡(luò)中右上角的super－node（用“＋”表示）的進(jìn)行氣味散布，而左下角super－node接收“氣味”的（用“藍(lán)色＋”表示）實(shí)際情況。顏色代表各節(jié)點(diǎn)的“氣味”濃度高低：濃度從高到底，顏色從紅轉(zhuǎn)變?yōu)樗{(lán)。

圖2 節(jié)點(diǎn)的相鄰情況

圖3 “氣味”在網(wǎng)絡(luò)中的散布情況

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

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

實(shí)驗(yàn)場景為：一個super－node（左下“＋”）作為產(chǎn)生信息的源節(jié)點(diǎn)，在1小時內(nèi)隨機(jī)發(fā)送100個數(shù)據(jù)包給另一個目標(biāo)super－node（右上“＋”）的情況。DREAM算法運(yùn)行時，網(wǎng)絡(luò)中所有節(jié)點(diǎn)均能獲得自身的地理位置信息；F－ACO算法運(yùn)行時，則不能獲得節(jié)點(diǎn)的地理位置信息。

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

由圖4不難發(fā)現(xiàn)，由于網(wǎng)絡(luò)的稀疏度較高，DREAM協(xié)議需要大量的節(jié)點(diǎn)參入到數(shù)據(jù)包的轉(zhuǎn)發(fā)和重傳過程中，但同時也保證了數(shù)據(jù)包沿著多條路徑成功到達(dá)目標(biāo)節(jié)點(diǎn)，協(xié)議的健壯性較好，相應(yīng)的網(wǎng)絡(luò)能量的消耗和資源的浪費(fèi)也較大。同時，由于每次傳遞都是獨(dú)立事件，算法并不保存路由表，因此在下一次傳遞時，同樣甚至更多的網(wǎng)絡(luò)能量和資源將被消耗。

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

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

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

圖6 時延對比圖

圖7 每次傳遞消耗的網(wǎng)絡(luò)能量對比

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

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

4 結(jié)語

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

［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］張勇德，黃莎白.多目標(biāo)優(yōu)化問題的蟻群算法研究［J］.控制與決策，2005，20（2）：170－173，178.

［8］金浩，劉維寧.基于覓食－返巢機(jī)制連續(xù)域蟻群算法［J］.計算機(jī)工程與應(yīng)用，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，F(xiàn)letcher C.Evolution of Seaweb Underwater Acoustic Networking［C］／／OCEANs 2000MTS／IEEE Conference and Exhibition，Providence，Rhode Island：IEEE，2000：2007－2017.