Mesh网络中基于粒子群优化的最优路径算法

赵宏伟

(苏州工业园区服务外包职业学院，江苏苏州 215123)

Mesh网络中基于粒子群优化的最优路径算法

赵宏伟

(苏州工业园区服务外包职业学院，江苏苏州 215123)

在以往的无线Mesh网络的最优路由设计中，往往仅考虑吞吐率和长度等单一因素。针对此问题，本文提出了一种基于量子粒子群优化的最优路径算法。首先，对网络中考虑的性能指标进行了详细描述，然后设计了路由协议，即路由发现、路由维护和路由修复。在此基础上，基于量子粒子群对路由进行优化，在路由优化过程中全面考虑网络总吞吐率、网络平均丢包率、网络端到端的延迟。在NS-2环境下进行仿真实验，在仿真实验中对网络总吞吐率、网络平均丢包率和网络端到端的延迟均进行了验证，结果证明，本文方法与其他方法相比具有较大的网络总吞吐率、较小的网络平均丢包率和网络端到端的延迟。

最优路径；路由协议；Mesh网络；通信

近年来，无线Mesh网络(wireless mesh network，WMN)即无线网状网，得到了广泛关注，其以静态无线中继Mesh节点，为移动的客户节点提供分布式网络。无线Mesh网络主要包括Mesh路由和Mesh用户。其中Mesh路由主要起到中继器的作用，通过无线方式连接上层网关同时为下层的MC提供网络服务。

为了实现Mesh网络的负载平衡和最大程度地提高整个网络的资源利用率，一些路由协议开始基于跨层的思想以提高网络的整体性能。如采用源节点到目标节点的最小跳数来设计路由协议(DSR，dynamic source routing)和AODV(Ad Hoc on Demand distance vector routing)。这些协议由于节点的移动性以及拓扑结构的动态变化，无法实现网络的最优。OLSR(Optimized link state routing)协议[2]基于DSR，是一种实现多点中继驱动的路由协议，能在多点中继的情况下通过选择性的泛洪机制，来减少某一分区控制分组的重复转发次数。闫茜[3]对无线Mesh网络中的多接口多信道进行了优化，提出了一种混合式信道分配相结合的多路径路由协议，实现了网络中多条路径的并行传输，以提高网络的吞吐率。邓晓衡[4]提出了一种新的路由判断依据EPBW，并在此基础上设计了路由协议EPBWR，同时在NS-2环境下在多种网络环境中进行了仿真。石文孝[5]在INX的基础上提出了无线Mesh网络干扰和区域负载的度量方法，并通过平均竞争度来描述干扰链路和离散程度来判断网络是否负载均衡。潘琢金[6]设计了一种支持多路径路由的先验式路由协议，通过先验式多树和比较累积传播的链路质量，来进行传输过程中的路由选择。何凌[7]提出了一种混合无线网状网协议的改进算法来解决AODV协议中的一些问题，如扩展性差、效率低，实验表明了改进的协议能快速计算出从源节点到目标节点的最优路径。

本文在上述工作的基础上，设计了一种基于量子粒子群的路由算法，该算法通过量子粒子群搜索出从任意节点到目标节点的最优路径，是一种Mesh网络中最优路由设计的有效方法。

1 网络性能评价

在设计路由协议时，最优路由的目标函数需要考虑的主要性能指标有网络总吞吐率、网络平均丢包率和端到端的平均时延。

1.1 网络总吞吐率

网络总吞吐率是网络中所有接收端在单位时间内正确接收的数据量，单位为kbit/s，表达式为：

(1)

其中，M是网络中所有运行的数据流组成的集合，Reci表示第i个接收端在数据流运行期间接收到的数据总量，Δt是网络中最后一个数据包传输完成减去第一个数据开始数据传输的开始时间，即整个网络中数据流进行运行的总时间。

网络吞吐率越高，网络能负载能力就越强，网络的性能就越好。

1.2 网络平均丢包率

网络的平均丢包率是网络中所有接收端接受到的正确的数据包与网络中所有输入端发出的所有的数据包的总量的比值，其计算方法为：

(2)

其中，N是网络中接收端接收到的所有正确的数据包的集合，|N|为网络中的所有接收端接收的正确的数据包数，Nsum表示网络中发送端发送的所有数据包的总和。

网络丢包率反应了网络的可靠性，网络的丢包率越低，网络越可靠，网络的性能越好。

1.3 网络端到端延迟

网络的端到端数据延迟是指数据包从开始发送到被网络的接收端正确接收所需要的总时间。平均的端到端延迟是网络中所有发送端发送的数据包的端到端时间延迟的平均值，表达式为：

(3)

其中，τj表示数据包j对应的端到端的时间延迟。

网络端到端延迟反应了数据在网络中传输的快慢。网络端到端的延迟越小，网络性能越好。

2 路由协议

2.1 路由发现

为了减少路由发现的开销，采用按需方式进行路由发现。当源节点S要向目标节点D发送数据时，就在全网中广播路由请求包，启动路由发现过程。路由请求包为RREQ(routing request packet)，每个RREQ包含单一的序列号ID和邻居节点列表，邻居列表记录是属于当前路径的节点。

当邻居节点在收到由源节点或由转发节点发送过来的RREQ后，首先查看是否曾经收到过该数据包，如果收到就丢弃该数据包；如果没有收到过该数据包，就写入RREQ消息中，并建立从该节点到源节点S的反向路由。同时判断是否自己存在着到RREQ中目标节点的路由，如果存在，则直接回复路由回应信息包给源节点；如果不存在则转发该RREQ；源节点S在收到来自多个中间节点或目标节点返回的路由回复信息包应答数据包RREP(routing reply packet)时，选择具有最小长度的路径存入路由表中，如果多个路由回复信息包中均具有最轻负载值，将新序列号存入到路由表中。

2.2 路由维护

路由发现用于建立源节点到目标节点之间的有效路由，通过该过程建立有效路由并进行数据传输。然而，由于无线网络的动态性，当前路由的吞吐量可能下降甚至路由可能失效。网络中可能由于动态性的变化，存在着更好的路径。

当目标节点发现其与源节点之间的路径吞吐率下降时，向源节点发送路由请求触发消息TREQ(triggering request message)。源节点在收到该信息后，就启动路由发现过程，并在全网中广播路由更新包UREQ(update routing request packet)。如果发现有更短路由和吞吐率更大的路径，则采用此路由作为首要路由。当网络进行动态性变化时，若数据传输有两条以上的可选相似路径，则选择一条较空闲的路由进行数据传输，由此不断重复。

2.3 路由修复

当建立的路由由于网络动态拓扑的变化而失效时，原因可能是由于目的节点到源节点返回的路由信息丢失或者数据传输过程中的链路断开。当RREQ从源节点出发，经过若干中间节点，最后到达目标节点后，目标节点会根据反向路由发送RREQ数据包。在数据传输的过程中，如果路径发生中断，传输失败的中间节点向源节点发送错误信息RERR(routing error packet)，而源节点在收到错误信息RERR后，会重启路由发现过程以找到新的路径。

3 基于量子粒子群的最优路径

3.1 量子粒子群概述

量子粒子群算法(Quantum-behaved Particle Swarm optimization，QPSO)是在粒子群算法的基础上发展而来的一种全局优化算法。

量子粒子群算法能在整个解空间中进行搜索，同时量子空间具有与普通粒子不一样的集聚态性，因此较粒子群算法具有更好的全局寻优能力。粒子位置向量采用ψ(x)表示，在时刻t或第t次迭代时，粒子的位置可以计算为：

(4)

其中，pl(t)、pg(t)和pr(t)分别表示粒子个体最优位置、粒子的全局最优位置和个体最优pl(t)。α为服从[0,1]上均匀分布的随机数，则有：

(5)

其中，pa(t)为第t次迭代所有粒子的位置均值，β为取值固定的惯性权重。粒子在时刻t+1或第t+1次迭代时的位置可以表示为：

(6)

3.2 基于改进量子粒子群的模型参数优化算法

在路由发现、路由维护和路由修复过程中寻找路由的过程往往仅考虑路径长度或吞吐率等因素，为了实现一个更优的最优路径，在最优路径的求解过程中充分考虑性能参数，即最优考虑最大化网络总吞吐率、最小化网络平均丢包率，最小化网络端到端的延迟。

算法1 基于量子粒子群的最优路由算法

初始化：粒子种群规模M，当前迭代次数i，迭代次数最大值；

①以路由发现生成的路由作为初始解，随机生成规模为M的粒子群P={p1,p2,…,pM}，每个粒子pi长度为路由的长度；

②根据公式(1)(2)(3)计算每个粒子的网络总吞吐率、网络平均丢包率、网络端到端的延迟；

③计算粒子的适应度：

(7)

④对所有粒子判断其适应度是否小于个体最优位置的适应度J(pl(t))：

如果小于，则采用p(t)作为新的个体最优位置pl(t)；

判断其是否小于J(pg(t))：

如果小于，则采用粒子的当前位置作为全局最优值pg(t)；

⑤根据公式(4)计算个体平均最优位置；

⑥根据公式(6)对粒子个体位置更新；

⑦更新迭代次数：t=t+1；判断当前迭代次数t达到最大值：

如果达到，输出最优路由；

否则转入②进行继续迭代。

4 仿真实验

在NS-2仿真工具下对文中设计的基于粒子群算法的最优路由进行仿真。在500×500 d区域中进行部署，每个节点有3个网络接口，节点的传输范围为300 m，干扰范围为500 m，传送数据包的大小为512 B。将文中方法与文献[7]方法在网络总吞吐率、网络平均丢包率、网络端到端的延迟等3个方面进行对比，如图1、图2和图3所示。

图1 网络总吞吐率比较

图2 网络平均丢包率对比

图3 平均端到端延迟对比

可以看出，本文方法在网络总吞吐率、网络平均丢包率、网络端到端的延迟方面均优于文献[7]方法。

5 结语

为了对Mesh网络的路由进行优化，本文提出了一种量子粒子群的最优路径算法。首先，设计了路由发现、路由维护和路由修复过程；然后基于量子粒子群对路由进行优化，在路由优化过程中全面考虑网络总吞吐率、网络平均丢包率、网络端到端的延迟。在NS-2环境下进行仿真实验，仿真实验证明了文中方法与其他方法相比具有较大的网络总吞吐率、较小的网络平均丢包率和网络端到端的延迟。

[1]王嵚琦,何新贵,徐明.无线Mesh网络路由协议的研究进展[J].计算机工程与设计,2009(10):2341-2349.

[2]A Laouiti,P Muhlethaler,A Najid,et al.Simulation results of the OLSR routing protocol for wireless network[C].Italy,Sardegna,1stMediterranean Ad-Hoc Networks Workshop,2002.

[3]闫茜,杨金程.结合混合式信道分配的Mesh多路径路由协议[J].计算机应用,2010(30):2505-2508.

[4]邓晓衡,刘强,李旭,等.链路质量与负载敏感的无线Mesh网络路由协议[J].计算机学报,2013(36):2009-2118.

[5]石文孝,许银龙,王继红,等.无线Mesh网络干扰与区域负载感知路由度量[J].北京邮电大学学报,2014(37):41-44.

[6]潘琢金,吴昊,罗振,等.无线Mesh网络先验式多树路由协议的研究与NS-3仿真[J].微电子学与计算机,2016(33):45-49.

[7]何凌,黄俊.基于混合无线网状网协议的改进算法研究[J].计算机应用研究,2011(28):1846-1849.

DesignforOptimalRouteofMeshNetworkBasedonParticleSwarmAlgorithm

ZHAO Hong-wei

(Suzhou Industrial Park, Service Outsourcing, Career Academy, Suzhou Jiangsu 215123, China)

The design for the optimal route design only considers the output and length. Aiming at this problem, an optimal route algorithm based on particle swarm algorithm is proposed. Firstly, the performance indexes are considered in detail, then the route protocol including route finding, route maintaining and route repairing are designed. The quantum particle swarm algorithm is used to optimize the route, on the basis of the total output, average packet loss rate and the delay between two ports. The simulation in NS-2 has verified the total output, average packet loss rate and the delay between two ports comprehensively. The result shows that the method in this paper has the high total output and low average packet loss rate and the delay between two ports.

optimal route; route protocol; Mesh network; communication

TP393

A

2095-7602(2017)12-0038-05

2017-05-03

赵宏伟(1980- )，男，工程师，硕士研究生，从事计算机应用、软件工程研究。