基于OMNeT++平台的AntNet的仿真

2017-03-22 22:59王培博
电子技术与软件工程 2017年3期
关键词:智能算法

摘 要研究了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

猜你喜欢
智能算法
神经网络智能算法在发电机主绝缘状态评估领域的应用
基于超像素的图像智能算法在矿物颗粒分割中的应用
从鸡群算法看群体智能算法的发展趋势
赛博经济中的智能硬件商业模式分析
蚁群算法在路径优化问题的应用研究