基于蚁群的Mesh网络路由算法模型的设计

张千里

（1.安徽理工大学 计算机科学与工程学院；2.淮南联合大学，安徽 淮南 232001）

基于蚁群的Mesh网络路由算法模型的设计

张千里

（1.安徽理工大学 计算机科学与工程学院；2.淮南联合大学，安徽 淮南 232001）

随着当今无线网络的快速发展，人们对无线网络的依赖性越来越强，本文主要对基于Mesh无线网络的核心Mesh路由进行研究，提出基于蚁群的Mesh路由算法，蚁群算法具有自组织能力，因此将蚁群算法应用到Mesh路由中有一定的优越性.该算法通过相邻节点交换高度及现存能量，在整个网络中建立梯度和平面路径上的信息浓度，在路由维护阶段，算法通过对路由传送中的数据的信息素浓度进行相应的增加，并模仿蚂蚁信息素的挥发过程.

无线Mesh网；路由算法；蚁群算法；信息素

1 无线Mesh网络的发展

随着当今无线网络的快速发展，人们对无线网络的依赖性越来越强.当前用户连接无线网主要通过三种方式：（1）通过2G的GPRS连接；（2）通过3G网络连接；（3）通过802.11无线局域网连接.这三种方式都具有信号稳定、性能可靠、维护方面，但2G和3G基站建立费用较高，用户联网费用高，通过802.11无线局域网连接方式覆盖范围小，信号难以进行大面积覆盖.基于Mesh的无线网络是在Ad Hoc网络发展起来的一种无线网络技术，其具有自组网功能、费用低、覆盖范围广和性能稳定等优点.

基于Mesh的无线网络（WMN）主要有两类节点组成：Mesh路由器和Mesh客户.其中Mesh路由器具有网关路由和Mesh组网路由两个功能.无线Mesh网络，如1图所示，众多无线路由器（WR）相互合作，成网状分布，从而将无线网络对城市任意位置覆盖，实现无线移动通信.

图1 无线Mesh网络

由于无线Mesh网络具有自动组网功能，能够提供无线网主干的灵活性，在无线网高速发展的今天特别受关注，无线Mesh网络的如今的应用非常广泛如：社区网络、小区监控系统、无线公交等.

2 蚁群算法概述

蚁群算法 （ant colony optimization,ACO），又称蚂蚁算法，它由Marco Dorigo于1992年在他的博士论文中提出，其核心思想是来自于大自然蚂蚁寻食过程，蚂蚁在寻食过程中，会在所经过的路径上留下一定浓度的信息素，当下次蚂蚁经过时，会判断信息素的浓度，以判断到达食物的最短路径.从蚂蚁寻食过程可以看出，蚂蚁表现出一种存在信息正反馈倾向，也就是某一路径经过的蚂蚁越多，信息素浓度也就越强，则后面选择该路径的概率越大，是一种用来在图中寻找优化路径的机率型算法.

蚁群算法最早被应用在旅行商问题（TSP）的求解中，在蚁群算法中，每个经过路径的蚂蚁都要根据当前路径状态选择下一跳的节点，而路径上的信息素依据全局更新规则进行更新.

说明：

（1）上式中△τ*表示精英蚂蚁引起的路径（i,j）上的信息素量的增加；

（2）σ是精英蚂蚁的个数；

（3）L*是所找出的最优解的路径长度.

3 无线Mesh网路由算法模型

针对无线Mesh网的特点，设计路由算法，首先要考虑网络中可能遇到的各种情况，所要数据有不同的需求，然后根据不同的情况和需求选择最优的路径来完成数据的传输.

为说明问题，首先建立一个简单的网络模型：给定n个节点和两两节点间的距离，要求确定一条经过各节点且每个节点只经过一次的最短路线.图论描述为G=（V,A），V节点集，A为边集，已知各顶点间的连接距离，要求确定一个最短的Hamilton回路.

模拟现实网络，作如下标记：

每个数据包都具有以下特征：在从节点i到节点j无能运动的过程中，数据包k在边（i,j）上留下一定量的信息.

数据包概率地选择下一个将要访问的节点，这个概率是两个节点间距离和两个节点间路径上存有的信息量的函数.

bi（t）：t时刻位于节点 i的包数

dij：两节点i和j之间的距离.

ηij：边（i,j）的能见度，反映由节点i转移到节点j的启发程度，这个量在系统的运行中是不变的.

τij：边（i,j）上的信息素轨迹强度.

△τij：包k在边（i,j）上留下的单位信息长度轨迹信息素量.

pkij：包k的转移概率，j是尚未访问的节点.

为了满足问题的约束条件，在完成一次循环后，不允许数据包选择已经访问过的路径，基于以上模型，用蚁群算法（ANT）来实现.

4 基于蚁群的无线Mesh网络路由算法设计

初始时刻，由于每条路径上的信息量是相同的，不妨设τij=C（C为为常），蚂蚁k（k=1,2,3…）在运动过程中的转移方向取决于路径上的信息量.依据随机比例规则，可以确定蚂蚁k从节点i到j的转移概率.在t时刻蚂蚁k在节点i选择节点j的转移概率为pkij（t），如图2所示.

图2 蚁群算法模型方程1

其中，allowedk={0,1,2,3…,n-1}表示蚂蚁k下一步可以选择的节点.依据方程 1 可知，概率 pkij（t）与 ταij*ηβij成正比.α为信息启发因子，β为期望启发式因子，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性，ηij为能见度因数.但与真实蚁群的区别在于人工蚁群系统具有记忆功能.为了满足约束条件（即蚂蚁必须经过所有n个不同的节点），为每只蚂蚁都设计了一个禁忌表（tabu list），禁忌表记录了在t时刻蚂蚁已经走过的节点，且在本次循环中该蚂蚁不走重复节点.在本次循环结束后，禁忌表被用来计算该蚂蚁所经过的路径长度.之后，清空禁忌表，该蚂蚁可再次进行自由地选择.

经过n个时刻，蚂蚁完成一次循环，各路径上信息量依据方程2进行调整，如图3所示.

图3 蚁群算法模型方程2

其中，△τkij（t,t+1）表示第k只蚂蚁在时刻（t,t+1）留在路径（i,j）上的信息素浓度，其值取决于蚂蚁表现的优劣程度.ρ（0<ρ<1）为信息素的挥发系数，能够避免路径上轨迹量的无限累加.

根据具体算法的不同，△τij，△τkij及 pkij的表达式形式允许不同，要依据具体情况而定.

5 总结

无线Mesh网络是一种新型的宽带无线网络结构，是非常有前途的一种无线接入技术，文本简单介绍了无线Mesh的基本原理及其发展，然后对蚁群算法进行了概述，鉴于蚁群算法具有自组织优点，提出基于蚁群的无线Mesh网络路由算法，并建立算法模型.

〔1〕刘美茹，程世杰.C++程序设计教程[M].哈尔滨:哈尔滨工业大学出版社,2005.

〔2〕方旭明，等.下一代无线因特网技术[M].北京:人民邮电出版社,2006.

〔3〕郑相全.无线自组网技术实用教程[M].北京:清华大学出版社，2004.

〔4〕张会霞.基于Wireless Mesh技术的宽带无线接入系统[J].现代电信科技,2003,（12）:29-30.

〔5〕宋文,方旭明.无线网格网络技术及其应用[C]//2004西南交通大学研究生学术论坛论文集，2004.1-8.

〔6〕Ian F.Akyildiz,Xudong Wang.A Survey on WirelessMesh Networks[J].IEEE Radio Communications.2005,43（9）:s23-s30.

〔7〕Fowlers T P.Mesh networks for broadband access[J].IEE Review,2001,47（1）:17-22.

TP302

A

1673-260X（2012）09-0028-02