论文总字数：26329字

摘 要

论文作者签名：

导师签名：

日期： 年 月 日

基于群体智能的流量路由算法

09015315 贾 卓

指导老师 王万元

摘 要

本文在研究一种通过自动化方式设计的强化学习算法，即群体智能的基础上，通过探究实验结果来论证群体智能相较于传统的基于强化学习的最短路由选择算法在实现网络流量路由方面的优势。许多分布式计算任务自然地被称为强化学习算法的递归神经网络。(例如群体智能)。这样做的困难在于，为了培养良好的整体表现，尽管没有集中的通信和控制，但是基于独立神经元的奖励是同步工作的，相关的神经元在相同的目的下工作。

在总结最短路径算法Dijkstra原理和相关技术的技术上，进一步深入探究Q-routing算法、PQ-routing算法、群体智能相关算法，分析不同算法在不同网络状态下实现的原理，并以数学框架为理论基础，详细介绍了Dijkstra算法和群体智能算法的理论实现，并设计了相应的伪代码来展示这两种算法的具体逻辑架构。

除此之外，还以网络协议为基础，分析了局部加权学习、Q-routing、PQ-routing和关于群体智能的人工鱼群等算法的具体原理以及探究了在不同网络状态下的探究性试验结果，进一步加深对互联网路由的理解和掌握。

关键词：群体智能，最短路径算法，局部加权学习，Q-routing，PQ-routing

Traffic Routing Algorithm Based on Collective Intelligence

09015315 Jia Zhuo

Advisor Wang Wanyuan

ABSTRACT

On the basis of studying a reinforcement learning algorithm designed by means of automation, namely swarm intelligence, this paper demonstrates the advantages of swarm intelligence in network traffic routing compared with the traditional shortest routing algorithm based on reinforcement learning through exploring experimental results. Many distributed computing tasks are naturally called recursive neural networks of reinforcement learning algorithms.(for example, swarm intelligence).The difficulty with this is that in order to foster good overall performance, although there is no centralized communication and control, rewards based on individual neurons work in sync, with related neurons working for the same purpose.

Summarizing the Dijkstra shortest path algorithm principle and related technical technology, further explore the Q - routing algorithm, the PQ - routing algorithms, and swarm intelligence algorithms, analysis the principle of different algorithms under different network condition, and based on the theory of mathematical framework, detailed introduces the Dijkstra algorithm and the theory of the swarm intelligence algorithm, and design the corresponding pseudo code to display the two specific logical architecture of the algorithm.

In addition, based on the network protocol, the specific principles of partial weighted learning, q-routing, pq-routing and artificial fish swarm algorithm about swarm intelligence are analyzed, and the exploratory test results under different network states are explored, so as to further deepen the understanding and mastery of Internet routing.

KEY WORDS: Collective intelligence, Shortest path algorithm, Local weighted learning,，Q-routing，PQ-routing

目 录

第一章 绪论 1

1.1 研究背景 1

1.2 研究现状 2

1.2.1 最短路由选择算法 2

1.2.2 动态变化网络中的分组路由 2

1.2.3 局部加权学习 2

1.2.4 群体智能—人工鱼群算法 3

1.3 研究目标和内容 4

1.4 论文组织结构 5

第二章 基础理论知识 6

2.1 最短路由选择算法 6

2.1.1 Dijkstra算法原理 6

2.1.2 Dijkstra算法技术分析 7

2.2 动态变化网络中的分组路由 7

2.2.1 Q-routing算法及与最短路径算法性能的比较 7

2.2.2 动态变化网络中的Q-routing 9

2.3 预测Q-routing 10

2.3.1预测Q-routing算法伪代码 11

2.3.2预测Q-routing在网络路由中的应用 12

2.3.3关于预测Q-routing的讨论 13

2.4 群体智能 13

2.4.1 群体智能理论知识 13

2.4.2 群体智能数学框架 14

2.4.3基于群体智能的流量路由 16

第三章 最短路径算法和群体智能在网络路由中的应用及结果分析 17

3.1最短路径算法在网络路由中的应用 17

3.1.1 最短路径算法伪代码 17

3.1.2 最短路径算法在网络路由中的实现 18

3.2 群体智能在网络路由中的应用 19

3.2.1群体智能的算法伪代码 19

3.2.2群体智能在网络路由中的实现 19

3.3 对于最短路径算法和群体智能算法的结果分析 23

3.4 对于群体智能系统的讨论 23

第四章 总结和展望 24

4.1 论文总结 24

4.2 工作展望 24

参考文献 25

致 谢 26

第一章 绪论

1.1 研究背景

因特网随着科技时代的迅速推进已经发展成为全球性的网络，因特网的内部又划分为多个子网构成了自治系统(简称AS)，在自治系统内和自治系统之间许多路由器，这项工作是找到通过路由器的数据包的最佳传输路径，有效地将数据传送到目的站点。通过路由器交换路由信息的这一工作，每个路由器必须遵循自己的协议，以维护自己的工作。分别是内部网关协议(IGP)和边界网关协议(BGP),这两个协议统一称为路由选择协议。路由选择协议的作用在于：1.交换路由信息；2.找到最短路径。内部网关协议包括基于距离的路由协议(RIP)和链路状态路由协议(OSPF)。在简单算法中，相对较小的自治系统使用RIP协议：路由仅与相邻路由交换信息，路由器交换的信息是当前路由器知道的所有信息，称为路由表。所有信息包括：从路由器到自治系统中所有网络的最短距离，以及为了到达目的网络应该经过的下一跳路由器。路由器每隔30s根据收到的路由信息更新路由表。OSPF协议更为适用于大型网络。路由器将信息发送到该自治系统中的所有路由器，发送的信息是与路由器相邻的所有路由器的链路状态(链路：从一个节点到另一个相邻节点的物理线路)。外部网关协议只是BGP协议。

RIP协议使用距离向量算法来查找最短路径，它使用跳数作为评价标准，跳数越少，距离越短，当跳数为16时，距离无法到达。每一个路由器的路由表是不同的，路由器并没有包含去目的网络的一个路径，而是仅给出下一条的地址。OSPF使用链路状态路由算法找到最短路径。此链路状态包括连接性、成本、距离、延迟和带宽等。与RIP想比，OSPF更全面地考虑这个问题，因为最短路径理论上应该是最短的时间，以及路由时间与上述因素并不仅仅是在RIP中提到的跳数。OSPF将所有信息发送到路由器，使用的是水浸法，其将信息发送到所有输出接口，以使所有路由器都具有这个消息的副本。水浸法转发信息，只有当链路状态信息发生改变时。相比于RIP，最后OSPF中每一个路由器将得到整个网络的拓扑结构，类似于一个加权无向图，这个图可以用最短路径算法(如Dijkstra算法提出的最短路径算法)来找到最短路径，但不同的是，差异在于最后填入路由表的还是下一跳的信息。相较于内部网关协议，不同之处在于边界网关协议BGP的目的不是为了找到目标网络的最短路径，而是找到一个合适的路径。原因在于互联网规模巨大，如果使用最短路径算法将会耗费大量的时间。

剩余内容已隐藏，请支付后下载全文，论文总字数：26329字