摘 要研究了AntNet的程序总体架构设计、模块接口定义、定时器设计，并基于OMNeT++仿真平台搭建了AntNet的算法环境，程序运行效果良好，可以满足后续的研究使用。

【关键词】网络路由 智能算法 蚂蚁算法

1 引言

蚂蚁觅食时，会在沿途洒下一种随时间挥发的信息素，来指导后面蚂蚁的选路。当道路出现分叉点时，蚂蚁总是倾向选择信息素较浓的路径。蚂蚁找到食物源后按原路返回，沿途继续洒下信息素，这样找到食物的路径上的信息素就得到了增强。路径越短，蚂蚁往返的就越快，相应路径上的信息素增强的频率就越高，后面蚂蚁选择这条路的概率也就越大，选择的这条路径的蚂蚁数量也随之变多，信息素又得到进一步的增强。这种正反馈机制，最终导致所有的蚂蚁都选择了最短的路径。受此启发，意大利学者M. Dorigo等提出了蚁群优化算法（Ant Colony Optimization， ACO），成为了近期的研究热点。AntNet是Muddassar Farooq博士设计出的蚂蚁算法软件，其直观、高效，成为很多人学习、研究蚁群算法研究的基础，本文基于OMNeT++平台搭建了AntNet算法。

2 测试环境搭建

在Win2000平台上，基于OMNeT++与Microsoft Visual C++ 6.0的集成编译环境，搭建AntNet的算法仿真，步骤如下：

步骤一：程序安装。

首先安装MSVC6.0和它ServicePack5以上版本的程序补丁，下载一个版本的OMNeT++执行安装，我们选用的是v3.0pre1版本。

步骤二：文件拷贝。

安装完毕后，将宏文件omnetpp.dsm拷贝到如下目录：

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

步骤三：添加设置系统变量。

以实验环境至少包含以下几项内容：

（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开发环境下激活宏文件。

（1）打开菜单“Tools|Customize”→选择tab中“Add-ins and Macro Files”一项→在列表框中选中“omnetpp”一项。

（2）将图标加入MSVC工具条：打开菜单“Tools|Customize”→选择tab中“Commands”→在组合框中“the Category”选择“Macros”→在列表框中能看到的“addNEDfileToProject”一项拖至工具条→选择图标→最后关闭对话框。

步骤五：使用时MSVC开发调试程序。

点击→在出现的输入框内键入需要加入的ned类型文件名“*.ned”→相应的宏文件就加入到工程了。这个工作实际上封装了两步内容：编译“*.ned”文件和加入编译过的相应“*_n.cpp”文件。然后，就可以在MSVC中根据需要编写算法的核心程序。

步骤六：使用命令行方式开发程序。

在DOS状态下进入应用程序的相应目录，分别运行命令“opp_nmakemake -f”和“nmake -f Makefile.vc depend”即可。前一個命令用于生成“makefile.vc”文件，后一个命令用于重新编译程序。

3 软件架构分析

3.1 软件模块分析

AntNet软件共有11个模块构成，包含6个简单模块和3个复合模块，如图1所示。6个简单模块分别是AG（AntGenerator）、AS（AntSink）、AN（AntNest）、DG（DataGenerator）、DS（DataSink）、RT（Router）、ST（Statistics）和GN（GenericNetworkNode），3个复合模块分别是Network、AntNeworkNode和SpecialTopology。

DG是网络节点处数据的产生模块，它负责产生各种要求的数据报文；AG模块是网络节点处蚂蚁的产生模块，它负责周期性产生前行蚂蚁，并根据当前的网络模型选择前行蚂蚁的目的地；DS用于统计数据的各种相关指标，包括报文吞吐率、报文延迟、报文跳数等等；AS用于统计蚂蚁的相关信息，包括蚂蚁跳数、蚂蚁寿命、前行/后行蚂蚁的吞吐率等等；RT用于数据和蚂蚁的路由处理，包括本地数据和蚂蚁向其它网络节点的转发、外来数据和蚂蚁向节点内部各个模块转发、消息队列的调遣等等，此外，借用OSPF的拓扑建立过程也在该模块内完成；AN是AntNet算法的核心模块，它负责路由表更新、巡行时间统计序表更新、蚂蚁健康状态检测、回环路由信息的检测/删除等等，所有前行蚂蚁的选路策略和后行蚂蚁的返回策略也都在此模块执行。这六个简单模块再加上其它的一些属性，共同构成了AntNetworkNode复合模块，它是采用AntNet路由算法网络中的基本节点单位。ST模块实际上是一个后台进程，提供了蚂蚁/数据报文各种指标统计的基础函数供其它模块调用，并将运行结果记录到文件或输出到屏幕；GN模块是个基础模块，标识网络节点的一些基础属性，如地址、链路带宽等。这两个简单模块再加上其它的一些属性，共同构建了SpecialTopology复合模块，SpecialTopology主要用于详细定义需要研究的各种拓扑结构。

3.2 模块间接口定义

AntNet软件架构中各个模块采用C++类独立构成，Statistics類和Ant类采用指针方式为其它类共享调用，Statistics类提供统计函数库，Ant类负责构建蚂蚁的基本属性和行为能力。节点内的其它模块类之间采用消息驱动，主要的消息流如图2所示，主要的消息过程表述如下。

3.2.1 过程一：节点产生前行蚂蚁，并路由出节点

⑴AG→AN：AG产生前行蚂蚁，将蚂蚁发射到AN模块中，AN负责前行蚂蚁的选路；

⑵AN→RT：AN将前行蚂蚁发送给RT模块，交给RT模块路由出去；

⑶RT→RT：RT模块将前行蚂蚁路由到指定节点的对应路由模块RT。

3.2.2 过程二：前行蚂蚁路由进入节点，并路由出节点

⑷RT→RT：对应节点的RT模块将前行蚂蚁路由进入模块RT；

⑸RT→AN：RT模块将前行蚂蚁发送给AN，AN负责前行蚂蚁的选路；

⑵AN→RT：AN将前行蚂蚁发送给RT模块，交给RT模块路由出去。

3.2.3 过程三：前行蚂蚁路由进入节点，发现到达目的地，转变成后行蚂蚁，并路由出节点

⑷RT→RT：对应节点的RT模块将前行蚂蚁路由进入模块RT；

⑸RT→AN：RT模块将前行蚂蚁发送给AN，AN检查前行蚂蚁已经到达目的地，将前行蚂蚁转变成后行蚂蚁，更新路由表、巡行时间统计序表；

⑵AN→RT：AN将后行蚂蚁发送给RT模块，交给RT模块路由出去。

3.2.4 过程四：后行蚂蚁路由入节点，更新路由表、巡行时间统计序表后，路由出节点

⑺RT→RT：对应节点的RT模块将后行蚂蚁路由进入模块RT；

⑸RT→AN：RT模块将后行蚂蚁发送给AN，更新路由表、巡行时间统计序表后，AN负责后行蚂蚁的选路；

⑵AN→RT：AN将后行蚂蚁发送给RT模块，交给RT模块路由出去。

3.2.5 过程五：后行蚂蚁路由入节点，发现已经返回源点

⑺RT→RT：对应节点的RT模块将后行蚂蚁路由进入模块RT；

⑸RT→AN：RT模块将后行蚂蚁发送给AN，AN负责更新路由表、巡行时间统计序表后；

⑹AN→AS：AN模块发现后行蚂蚁已经返回到源点，将消息发送给AS，AS负责统计蚂蚁的相关信息。

3.2.6 过程六：数据产生，并路由出节点

⑻DG→RT：DG产生数据报文，将数据发送到RT模块中，同时执行⑼；

⑼DG→AG：DG将产生的数据报文发一份拷贝给AG，AG用于计算本地流量模型，为产生的前行蚂蚁选择目的地址

⑽RT→RT：RT模块将数据路由到指定节点的对应路由模块RT。

3.2.7 过程七：数据路由入节点并路由出节点

⑾RT→RT：邻居节点的RT模块将数据路由到指定节点的对应路由模块RT中；

⑿RT→RT：RT模块将数据路由到指定节点的对应路由模块RT。

3.2.8 过程八：数据路由入节点，发现已经到达目的地

⑾RT→RT：邻居节点的RT模块将数据路由到指定节点的对应路由模块RT中；

⒀RT→DS：如果RT发现数据已经到达目的地，则将数据发送给DS，由DS负责统计数据吞吐率等的相关信息。

3.2.9 过程九：拓扑建立和维护

⒁AntNet算法实现中，网络拓扑的建立和正常检测过程借用了存活协议，它发生在本路由节点的RT模块和邻居路由节点的RT模块间。

3.3 定时器设计

AntNet软件在AN、AG、AS、DG、RT等模块设计了不同粒度的定时器，分别满足蚂蚁派遣、信息素更新、数据路由表更新、形成反馈机制等。AG模块有产生蚂蚁定时器、发派新蚂蚁定时器；AN模块有休眠定时器、初始化路由表定时器；AS模块有流量测量定时器、计时定时、间隔定时器；DG模块有数据启动、休眠、消息、事件定时器；RT模块有存活验证定时器、发送/接受定时器等等。

4 仿真运行效果

基于Windows平台，在OMNeT++仿真环境下，成功搭建了AntNet算法，以NTTnet为例的拓扑结构如图3所示。在这个仿真环境中进行算法改进，可以进一步比较研究算法的有效性。

作者简介

王培博（1999-），男，天津市人。研究方向为智能算法、软件工程。

作者单位

天津市武清区杨村一中 天津市 301700