摘 要研究了AntNet的程序總體架構(gòu)設(shè)計(jì)、模塊接口定義、定時(shí)器設(shè)計(jì)，并基于OMNeT++仿真平臺(tái)搭建了AntNet的算法環(huán)境，程序運(yùn)行效果良好，可以滿足后續(xù)的研究使用。

【關(guān)鍵詞】網(wǎng)絡(luò)路由 智能算法 螞蟻算法

1 引言

螞蟻覓食時(shí)，會(huì)在沿途灑下一種隨時(shí)間揮發(fā)的信息素，來指導(dǎo)后面螞蟻的選路。當(dāng)?shù)缆烦霈F(xiàn)分叉點(diǎn)時(shí)，螞蟻總是傾向選擇信息素較濃的路徑。螞蟻找到食物源后按原路返回，沿途繼續(xù)灑下信息素，這樣找到食物的路徑上的信息素就得到了增強(qiáng)。路徑越短，螞蟻往返的就越快，相應(yīng)路徑上的信息素增強(qiáng)的頻率就越高，后面螞蟻選擇這條路的概率也就越大，選擇的這條路徑的螞蟻數(shù)量也隨之變多，信息素又得到進(jìn)一步的增強(qiáng)。這種正反饋機(jī)制，最終導(dǎo)致所有的螞蟻都選擇了最短的路徑。受此啟發(fā)，意大利學(xué)者M(jìn). Dorigo等提出了蟻群優(yōu)化算法（Ant Colony Optimization， ACO），成為了近期的研究熱點(diǎn)。AntNet是Muddassar Farooq博士設(shè)計(jì)出的螞蟻算法軟件，其直觀、高效，成為很多人學(xué)習(xí)、研究蟻群算法研究的基礎(chǔ)，本文基于OMNeT++平臺(tái)搭建了AntNet算法。

2 測試環(huán)境搭建

在Win2000平臺(tái)上，基于OMNeT++與Microsoft Visual C++ 6.0的集成編譯環(huán)境，搭建AntNet的算法仿真，步驟如下：

步驟一：程序安裝。

首先安裝MSVC6.0和它ServicePack5以上版本的程序補(bǔ)丁，下載一個(gè)版本的OMNeT++執(zhí)行安裝，我們選用的是v3.0pre1版本。

步驟二：文件拷貝。

安裝完畢后，將宏文件omnetpp.dsm拷貝到如下目錄：

C：＼Program Files＼Microsoft Visual Studio＼Common＼MSDev98＼Macros

步驟三：添加設(shè)置系統(tǒng)變量。

以實(shí)驗(yàn)環(huán)境至少包含以下幾項(xiàng)內(nèi)容：

（1）INCLUDE = %INCLUDE%；C：＼Program Files＼Microsoft Visual Studio＼VC98＼INCLUDE；C：＼OMNeT++＼include

（2）LIB = %LIB%；C：＼Program Files＼Microsoft Visual Studio＼VC98＼Lib；C：＼OMNeT++＼lib

（3）Path=%PATH%；C：＼OMNeT++＼bin；C：＼Program Files＼Tcl＼bin；C：＼Program Files＼Microsoft Visual Studio＼Common＼msdev98＼BIN；C：＼Program Files＼Microsoft Visual Studio＼VC98＼BIN

（4）TCL_LIBRARY = C：＼OMNeT++＼lib＼tcl8.4

步驟四：在MSVC開發(fā)環(huán)境下激活宏文件。

（1）打開菜單“Tools|Customize”→選擇tab中“Add-ins and Macro Files”一項(xiàng)→在列表框中選中“omnetpp”一項(xiàng)。

（2）將圖標(biāo)加入MSVC工具條：打開菜單“Tools|Customize”→選擇tab中“Commands”→在組合框中“the Category”選擇“Macros”→在列表框中能看到的“addNEDfileToProject”一項(xiàng)拖至工具條→選擇圖標(biāo)→最后關(guān)閉對(duì)話框。

步驟五：使用時(shí)MSVC開發(fā)調(diào)試程序。

點(diǎn)擊→在出現(xiàn)的輸入框內(nèi)鍵入需要加入的ned類型文件名“*.ned”→相應(yīng)的宏文件就加入到工程了。這個(gè)工作實(shí)際上封裝了兩步內(nèi)容：編譯“*.ned”文件和加入編譯過的相應(yīng)“*_n.cpp”文件。然后，就可以在MSVC中根據(jù)需要編寫算法的核心程序。

步驟六：使用命令行方式開發(fā)程序。

在DOS狀態(tài)下進(jìn)入應(yīng)用程序的相應(yīng)目錄，分別運(yùn)行命令“opp_nmakemake -f”和“nmake -f Makefile.vc depend”即可。前一個(gè)命令用于生成“makefile.vc”文件，后一個(gè)命令用于重新編譯程序。

3 軟件架構(gòu)分析

3.1 軟件模塊分析

AntNet軟件共有11個(gè)模塊構(gòu)成，包含6個(gè)簡單模塊和3個(gè)復(fù)合模塊，如圖1所示。6個(gè)簡單模塊分別是AG（AntGenerator）、AS（AntSink）、AN（AntNest）、DG（DataGenerator）、DS（DataSink）、RT（Router）、ST（Statistics）和GN（GenericNetworkNode），3個(gè)復(fù)合模塊分別是Network、AntNeworkNode和SpecialTopology。

DG是網(wǎng)絡(luò)節(jié)點(diǎn)處數(shù)據(jù)的產(chǎn)生模塊，它負(fù)責(zé)產(chǎn)生各種要求的數(shù)據(jù)報(bào)文；AG模塊是網(wǎng)絡(luò)節(jié)點(diǎn)處螞蟻的產(chǎn)生模塊，它負(fù)責(zé)周期性產(chǎn)生前行螞蟻，并根據(jù)當(dāng)前的網(wǎng)絡(luò)模型選擇前行螞蟻的目的地；DS用于統(tǒng)計(jì)數(shù)據(jù)的各種相關(guān)指標(biāo)，包括報(bào)文吞吐率、報(bào)文延遲、報(bào)文跳數(shù)等等；AS用于統(tǒng)計(jì)螞蟻的相關(guān)信息，包括螞蟻跳數(shù)、螞蟻壽命、前行/后行螞蟻的吞吐率等等；RT用于數(shù)據(jù)和螞蟻的路由處理，包括本地?cái)?shù)據(jù)和螞蟻向其它網(wǎng)絡(luò)節(jié)點(diǎn)的轉(zhuǎn)發(fā)、外來數(shù)據(jù)和螞蟻向節(jié)點(diǎn)內(nèi)部各個(gè)模塊轉(zhuǎn)發(fā)、消息隊(duì)列的調(diào)遣等等，此外，借用OSPF的拓?fù)浣⑦^程也在該模塊內(nèi)完成；AN是AntNet算法的核心模塊，它負(fù)責(zé)路由表更新、巡行時(shí)間統(tǒng)計(jì)序表更新、螞蟻健康狀態(tài)檢測、回環(huán)路由信息的檢測/刪除等等，所有前行螞蟻的選路策略和后行螞蟻的返回策略也都在此模塊執(zhí)行。這六個(gè)簡單模塊再加上其它的一些屬性，共同構(gòu)成了AntNetworkNode復(fù)合模塊，它是采用AntNet路由算法網(wǎng)絡(luò)中的基本節(jié)點(diǎn)單位。ST模塊實(shí)際上是一個(gè)后臺(tái)進(jìn)程，提供了螞蟻/數(shù)據(jù)報(bào)文各種指標(biāo)統(tǒng)計(jì)的基礎(chǔ)函數(shù)供其它模塊調(diào)用，并將運(yùn)行結(jié)果記錄到文件或輸出到屏幕；GN模塊是個(gè)基礎(chǔ)模塊，標(biāo)識(shí)網(wǎng)絡(luò)節(jié)點(diǎn)的一些基礎(chǔ)屬性，如地址、鏈路帶寬等。這兩個(gè)簡單模塊再加上其它的一些屬性，共同構(gòu)建了SpecialTopology復(fù)合模塊，SpecialTopology主要用于詳細(xì)定義需要研究的各種拓?fù)浣Y(jié)構(gòu)。

3.2 模塊間接口定義

AntNet軟件架構(gòu)中各個(gè)模塊采用C++類獨(dú)立構(gòu)成，Statistics類和Ant類采用指針方式為其它類共享調(diào)用，Statistics類提供統(tǒng)計(jì)函數(shù)庫，Ant類負(fù)責(zé)構(gòu)建螞蟻的基本屬性和行為能力。節(jié)點(diǎn)內(nèi)的其它模塊類之間采用消息驅(qū)動(dòng)，主要的消息流如圖2所示，主要的消息過程表述如下。

3.2.1 過程一：節(jié)點(diǎn)產(chǎn)生前行螞蟻，并路由出節(jié)點(diǎn)

⑴AG→AN：AG產(chǎn)生前行螞蟻，將螞蟻發(fā)射到AN模塊中，AN負(fù)責(zé)前行螞蟻的選路；

⑵AN→RT：AN將前行螞蟻發(fā)送給RT模塊，交給RT模塊路由出去；

⑶RT→RT：RT模塊將前行螞蟻路由到指定節(jié)點(diǎn)的對(duì)應(yīng)路由模塊RT。

3.2.2 過程二：前行螞蟻路由進(jìn)入節(jié)點(diǎn)，并路由出節(jié)點(diǎn)

⑷RT→RT：對(duì)應(yīng)節(jié)點(diǎn)的RT模塊將前行螞蟻路由進(jìn)入模塊RT；

⑸RT→AN：RT模塊將前行螞蟻發(fā)送給AN，AN負(fù)責(zé)前行螞蟻的選路；

⑵AN→RT：AN將前行螞蟻發(fā)送給RT模塊，交給RT模塊路由出去。

3.2.3 過程三：前行螞蟻路由進(jìn)入節(jié)點(diǎn)，發(fā)現(xiàn)到達(dá)目的地，轉(zhuǎn)變成后行螞蟻，并路由出節(jié)點(diǎn)

⑷RT→RT：對(duì)應(yīng)節(jié)點(diǎn)的RT模塊將前行螞蟻路由進(jìn)入模塊RT；

⑸RT→AN：RT模塊將前行螞蟻發(fā)送給AN，AN檢查前行螞蟻已經(jīng)到達(dá)目的地，將前行螞蟻轉(zhuǎn)變成后行螞蟻，更新路由表、巡行時(shí)間統(tǒng)計(jì)序表；

⑵AN→RT：AN將后行螞蟻發(fā)送給RT模塊，交給RT模塊路由出去。

3.2.4 過程四：后行螞蟻路由入節(jié)點(diǎn)，更新路由表、巡行時(shí)間統(tǒng)計(jì)序表后，路由出節(jié)點(diǎn)

⑺RT→RT：對(duì)應(yīng)節(jié)點(diǎn)的RT模塊將后行螞蟻路由進(jìn)入模塊RT；

⑸RT→AN：RT模塊將后行螞蟻發(fā)送給AN，更新路由表、巡行時(shí)間統(tǒng)計(jì)序表后，AN負(fù)責(zé)后行螞蟻的選路；

⑵AN→RT：AN將后行螞蟻發(fā)送給RT模塊，交給RT模塊路由出去。

3.2.5 過程五：后行螞蟻路由入節(jié)點(diǎn)，發(fā)現(xiàn)已經(jīng)返回源點(diǎn)

⑺RT→RT：對(duì)應(yīng)節(jié)點(diǎn)的RT模塊將后行螞蟻路由進(jìn)入模塊RT；

⑸RT→AN：RT模塊將后行螞蟻發(fā)送給AN，AN負(fù)責(zé)更新路由表、巡行時(shí)間統(tǒng)計(jì)序表后；

⑹AN→AS：AN模塊發(fā)現(xiàn)后行螞蟻已經(jīng)返回到源點(diǎn)，將消息發(fā)送給AS，AS負(fù)責(zé)統(tǒng)計(jì)螞蟻的相關(guān)信息。

3.2.6 過程六：數(shù)據(jù)產(chǎn)生，并路由出節(jié)點(diǎn)

⑻DG→RT：DG產(chǎn)生數(shù)據(jù)報(bào)文，將數(shù)據(jù)發(fā)送到RT模塊中，同時(shí)執(zhí)行⑼；

⑼DG→AG：DG將產(chǎn)生的數(shù)據(jù)報(bào)文發(fā)一份拷貝給AG，AG用于計(jì)算本地流量模型，為產(chǎn)生的前行螞蟻選擇目的地址

⑽RT→RT：RT模塊將數(shù)據(jù)路由到指定節(jié)點(diǎn)的對(duì)應(yīng)路由模塊RT。

3.2.7 過程七：數(shù)據(jù)路由入節(jié)點(diǎn)并路由出節(jié)點(diǎn)

⑾RT→RT：鄰居節(jié)點(diǎn)的RT模塊將數(shù)據(jù)路由到指定節(jié)點(diǎn)的對(duì)應(yīng)路由模塊RT中；

⑿RT→RT：RT模塊將數(shù)據(jù)路由到指定節(jié)點(diǎn)的對(duì)應(yīng)路由模塊RT。

3.2.8 過程八：數(shù)據(jù)路由入節(jié)點(diǎn)，發(fā)現(xiàn)已經(jīng)到達(dá)目的地

⑾RT→RT：鄰居節(jié)點(diǎn)的RT模塊將數(shù)據(jù)路由到指定節(jié)點(diǎn)的對(duì)應(yīng)路由模塊RT中；

⒀RT→DS：如果RT發(fā)現(xiàn)數(shù)據(jù)已經(jīng)到達(dá)目的地，則將數(shù)據(jù)發(fā)送給DS，由DS負(fù)責(zé)統(tǒng)計(jì)數(shù)據(jù)吞吐率等的相關(guān)信息。

3.2.9 過程九：拓?fù)浣⒑途S護(hù)

⒁AntNet算法實(shí)現(xiàn)中，網(wǎng)絡(luò)拓?fù)涞慕⒑驼z測過程借用了存活協(xié)議，它發(fā)生在本路由節(jié)點(diǎn)的RT模塊和鄰居路由節(jié)點(diǎn)的RT模塊間。

3.3 定時(shí)器設(shè)計(jì)

AntNet軟件在AN、AG、AS、DG、RT等模塊設(shè)計(jì)了不同粒度的定時(shí)器，分別滿足螞蟻派遣、信息素更新、數(shù)據(jù)路由表更新、形成反饋機(jī)制等。AG模塊有產(chǎn)生螞蟻定時(shí)器、發(fā)派新螞蟻定時(shí)器；AN模塊有休眠定時(shí)器、初始化路由表定時(shí)器；AS模塊有流量測量定時(shí)器、計(jì)時(shí)定時(shí)、間隔定時(shí)器；DG模塊有數(shù)據(jù)啟動(dòng)、休眠、消息、事件定時(shí)器；RT模塊有存活驗(yàn)證定時(shí)器、發(fā)送/接受定時(shí)器等等。

4 仿真運(yùn)行效果

基于Windows平臺(tái)，在OMNeT++仿真環(huán)境下，成功搭建了AntNet算法，以NTTnet為例的拓?fù)浣Y(jié)構(gòu)如圖3所示。在這個(gè)仿真環(huán)境中進(jìn)行算法改進(jìn)，可以進(jìn)一步比較研究算法的有效性。

作者簡介

王培博（1999-），男，天津市人。研究方向?yàn)橹悄芩惴ā④浖こ獭?/p>

作者單位

天津市武清區(qū)楊村一中 天津市 301700