＋设为首页 ＋添加到收藏夹
路由算法的数学模型是图论模型。如下图： 【相关文章:关于Fault Modeling usi】
第三章 路由算法的设计 【扩展阅读:ASP.NET 数据访问类】
【扩展信息:关于Fault Modeling usi】
图7 网络模型
路由过程的选择，即是在加权无向图（或有向图）中寻找源结点与目标结点的最佳路径，根据最佳路径选择下一站路由器。如图7中，0结点至4结点的最佳路径是0→2→3→4，那么由0结点发往4结点的数据包在0结点时的下一站路由器是2结点，其余类推。 目前已有众多成熟的路由算法，典型如dijkstra算法，可以方便的计算某一顶点到其余各顶点的最短路径，该过程的复杂度为o(n2)，则计算一个网络模型的路由表的时候，共需要调用n次算法，所以复杂度为o(n3)。另一个典型算法是floyed算法，可以计算图中每对顶点之间的最短路径，复杂度为o(n3)。路由算法的详细情况可见于参考资料[6]与[7]。 但随着计算机科学的发展，新兴的计算模型得到广泛的注意与利用，尤其是智能计算。本文的路由算法设计中，改造实现了floyed算法，使之由计算最短路径并同时计算路由表。另外，独立设计一种演化路由算法，并初步讨论了算法的收敛性。最后根据实验数据分析两种算法的性能。 §3.1 floyed路由算法设计 floyed算法从图的邻接矩阵开始，按照图结点0，1，2，…，n-1的顺序，分别以每个结点k（0<=k<=n-1）作为新考虑的中间点，在第k-1次运算得到的a (k-1) ( a (-1)为图的邻接矩阵ga)的基础上，求出每对结点i～j的目前最短路径长度a (k)[i][j]。计算公式为： a(k)[i][j]=min(a(k-1)[i][j],a(k-1)[i][k] + a(k-1)[k][j])， （ 0<= i<=n-1，0<= j <=n-1 ）。 当i结点是源结点，j结点是目标结点，而且i结点与k结点是相邻的时候，k结点就是目前最短路径中i结点的下一站路由器。 ... 下一页