基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第7页
索过程如表3.1所示，求出的最短路径如图3.2（b）所示。
图3.2 一个通信网络的加权无向图以及求出的最短路径
表3.1 最短路径的搜索过程
步骤 最短路径的节点集合N B C D E F G
1 {B} (2,A) (6,A) (∞,-) (∞,-) (∞,-) (∞,-)
2 {B,C} (2,A) (4,B) (10,B) (∞,-) (∞,-) (∞,-)
3 {B,C,D} (2,A) (4,B) (9,C) (∞,-) (∞,-) (∞,-)
4 {B,C,D,F} (2,A) (4,B) (9,C) (13,D) (11,D) (∞,-)
5 {B,C,D,F,G} (2,A) (4,B) (9,C) (13,D) (11,D) (13,F)
每个路由器节点按照上述的SP算法计算出节点间的最短路径，形成路由表，在路由器加电启动时加载到路由器中。在路由器工作过程中，将根据数据分组中的目的地址查找路由表，找出最短的路径来转发数据分组。
（2）基于流量的路由选择
SP算法只是根据网络拓扑结构计算最短路径，而没有考虑通信流量或负载。FR算法则考虑网络拓扑结构和通信流量两方面因素进行路由选择。
在一些网络中，节点之间的通信流量是相对稳定和可预测的。如果在预先知道节点之间平均通信流量的条件下，采用适当的算法对通信流量进行数学分析，可以优化路由选择。FR算法的基本条件是：
1） 必须知道网络拓扑结构；
2） 必须知道节点之间平均通信流量；
3） 必须知道各条线路的容量；
4） 采用适当的路由选择算法。
FR算法的基本原理是：对于一个给定的线路，如果知道该线路的负荷量和
平均流量，则可以用队列理论计算出该线路的平均分组延迟。于是，路由选择问题就可归结为如何找出产生网络最小延迟的路由选择算法。
以图3.2为例，假设已经预先得到该网络的有关参数：网络拓扑结构、各
条线路的平均流量F（分组/s）和线路容量C（分组/s），并计算出个条线路的平均延迟时间T = 1 /（C-F）和权值，参见表3.2。
表3.2 网络有关参数
线路 F（分组/s） C（分组/s） T /ms 权值
AB 14 25 91 0.171
BC 12 25 77 0.146
CD 6 12.5 154 0.073
AC 11 25 71 0.134
BD 13 62.5 20 0.159
DE 8 12.5 222 0.098
DF 10 25 67 0.122
EG 8 25 59 0.098
FG 10 20 100 0.112
通过表3.2中的参数可以求出整个网络的平均延迟时间，即每条线路的平均延迟时间加权和。在本例中约为98ms。
编写不同的路由选择算法程序，确定算法求得的网络平均延迟时间最小，该算法便是最好的路由选择算法，所计算出的路径就是最佳路由。这些计算式预先脱机进行，可以不考虑计算开销和费时问题。
2. 动态路由选择算法
网络的拓扑节都和通信量是动态变化的，如路由器的加入或退出，网络发生
拥塞等。如果路由器能够及时获得这些网络动态变化情况，并以此作为路由选择的依据，则会有助于路由器优化路由选择。动态路由选择算法就是采用这一机制进行路由路由选择的，它也称为自适应路由选择算法。
现代计算机网络系统通常采用动态路由选择算法，在动态路由选择算法中，最常见的有距离矢量路由选择和链路状态路由选择等两种算法：
（1）距离矢量路由选择
距离矢量路由选择（distance vector routing, DVR）算法的基本原理是每个路由器都文护一个路由表，表中记录通向目的节点的最佳距离和线路。每个路由器都要与相邻的路由器交换路由信息来更新路由表，使路由表中的信息总是反映网络最新的动态变化情况。
DVR算法最初应用于ARPANET中，后被其他网络所采用，如DECnet、Novell的IPX协议、Apple的Appletalk协议以及Cisco路由器等。著名的路由选择信息协议（routing information protocol, RIP）也是基于该算法开发的。
在DVR算法中，每个路由器都文护一个路由表，表中的每个表项都对应网络中的一个路由器，每个表项包含两部分内容：① 通往目的节点的输出线路；② 到达目的节点的距离或所需时间估算值，估算值的度量标准可以是节点数、时间延迟估算值、该路由的队列长度等。路由器要选择一种度量标准来估算本节点与目的节点之间的距离。如果选择节点数，则一个距离长度为一个节点；如果选择队列长度，则路由器检查每个队列；如果选择时间延迟，则路由器可以通过向相邻路由器发送一个特殊的回应（echo）分组请求对方回送带有时间标记的分组来获取时间延迟值。
在一个网络系统中，每个路由器都按约定（或路由协议）采用某种度量标准来估算它到达目的节点的距离，并传送给相邻路由器；同时，它也会从相邻路由器中得到类似的估算值，并以此更新路由表。这样，路由器就可以从路由表上估算值中找出最佳值，该估算值对应的输出线路便是最佳路由，并选择该路由转发数据分组。
（2）链路状态路由选择
DVR算法存在两个主要缺陷：① 在选择路由时没有考虑线路带宽，而线路带宽随着网络技术的发展在不断地提高；② 算法在获取路由信息时需要耗费很多的时间。因此，DVR算法后来被链路状态路由选择（line state routing, LSR）算法所取代。现在，各种各样的LSR算法广泛应用于现代网络系统中，著名的开放最短路径优先（open shortest path first, OSPF）协议采用的就是LSR算法，而OSPF协议广泛应用于Internet中。
每个路由器上的LSR算法都要执行如下过程：
1）发现相邻路由器，获取其网络地址。当一个路由器加入网络后，首先向每个相邻的路由器发送一个特殊的Hello分组，目的是声明它的存在，并希望得到相邻路由器的响应。各个相邻路由器接受到Hello分组后，都回应一个包含本路由器地址的响应分组。每个路由器地址应是一个全局惟一的地址。
2）测量到各个相邻路由器的时间延迟或线路开销。一个路由器可通过发送Echo分组来测量到各个相邻路由器的延迟，各个相邻路由器接收到Echo分组后都回应一个包含时间标记的响应分组。从发送Echo分组开始到接收到响应分组所经历时间除以2，便是该线路的延迟时间估算值。它反映了线路带宽状况，线路带宽越大，延迟时间越小；反之，线路带宽越小，延迟时间越大。
3）将测量值通告给其他路由器。路由器在获得有关路由器和链路状态信息后，构造一个特殊的链路状态（LS）分组来发布链路状态信息，该分组包含发送者地址、序号、生存期以及各个相邻路由器地址和对应的延迟时间估算值等信息。该分组可以周期性地发送，也可以在网络发生重大事件时发送，并采用如下的传递机制：
① 路由器采用扩散法周期地响所有线路广播LS分组，每发送一个新的LS分组，分组的序号加1。
② 相邻路由器接收到LS分组后，通过核对发送者地址和序号来判断LS分组是否是重复的或过时的。如果是新的LS分组，则在路由表中记录新的链路状态信息，并向除出入线路之外的所有线路扩散，传播给其他的路由器；如果是重
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>
基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第7页下载如图片无法显示或论文不完整，请联系qq752018766
