无向双环网络的是优设计研究

2013-08-15朱琦

科技传播 2013年23期

关键词：双环结点路由

朱琦

吉林工商学院信息工程学院，吉林长春 136200

无向双环网络的节点故障出现在保证网络节点间的路由是一个非常重要的问题。如果按照最短的路径访问方式而映射到直角坐标系会形成最优的路由构图CG(N; ±r，±s)，针对故障节点的封闭区和逃选区，仍然可以进行最优路由。

1 无向双环网络设计定理

我们来举个例子，如果a=84,若b=89,u=102；v=68 的话，x=0;y 是基数并且满足定理的条件，这时，x=0,y=3，b-a=5 ≠y,b-a=5 ≠y-2,所以，这样的形式是不可成立的。

1）双环网络G（N；r，s）有N个结点0，1，2，…，N－1，而且是从每个结点i发出两条有向边i→i＋r（m odN）和i→i＋s（modN其中1≤r≠s〈N。有一个这样的问题：对于给定的N，如何选取r和s使得G（N；r，s）有最小的直径呢，我们就根据r＝1的特殊情形想到一个方法，并且构造出最小直径是不会在r＝1的情况下达到的双环网络无限族，同时指出了错误；

2）早在1987 年就有人证明一般的双环网络G（N;r,s）是成立的，而此时，大家通过网络搜索发现到，N 是存在的，最小值竟然是450，事实上d1(450)=36，而且G（450；1,59）是优的。有很多方法都可以构造出含有奇异无线子族的紧优双环的网络无线族是优2 种情形发生的，第一种情况就是已经知道某个奇异紧优的双环网络G(No;ro,so)为了起始的元素紧优的双环网络无线族，使之其中的一个奇异无限子族在起始元素未知的情况下构造出一个含有奇异无限子族的紧优双环网络无限族；

3）无向双环网络的构造简单而且具有规则性、对称性和可扩性，所以在计算机互联网可以得到广泛的应用，是非常重要的，它可以用直径去度量，目前已经找到了大量的含有紧优的双环网络无限族，早在1993 年的时候，人们就提出关于给定的K ＞1 并且找出了无向紧优双环网络的无限族，对给定的正整数n,给出了一个全新的算法用来无向双环网络的最优步长s,使之无向双环网络G(n；±1,±s)的直径最短，无向双环网络G(2t2－B；±1,±s)及无向双环网络G(2t2－2；±1,±s)紧优的充分必要条件；

4）有一种仿真算法：（1 小边；s 为大边；N 为节点数)但是不足的是利用数据库去采取中间的结果，N 很大的时候计算时间就会长，不利于N 值紧优双环网络的分析。针对这个问题，应该提出一个非常有效的仿真法，根据存取的结果，再加上这样的算法很快会研究到G(N；±1,±s)紧优分布的特性计算出了4 ≤N ≤1 000 当中的任意节点数N 的紧优无向双环网络个数n；仿真此时的n-N 紧优分布率和n/(N-3)-N 紧优分布率；计算4 ≤N ≤1 000 中不存在紧优无向双环网络的N 值；

5）双环网的寻径是当前关注较多的课题。主要是关于同一个双环网在两个不同节点间的运算情况,其算法则需要完成的时间为O(△),其中△是该网络的直径。双环网络已经是一个很重要的互联网络结构了，最传统的优寻径方法并没有利用网络中同一节点和不同节点的最短路径之间的关系，所以给的算法不是最优的，定义了双环网络的一种最短路径—— [+ 1]边优先最短路径，在这样的形式下，最短的路径形式已成为唯一，况且同一个源节点和不同目的节点的最短的路径存在着递推的联系，并且给出了相应的递推公式。运用这个公式，平均不到两次的加法运算和一次比较就能找到源节点至所有其它节点的最短路径。再利用所得的结果，源节点只用储很少的信息就能经过简单的计算求得到其它节点的最短路径。和传统的方法比较起来，这种算法已经提高了系统的寻径效率设n=qh+r,这里1 ≤r ≤h-1,w=「(h-1)/(q+r)；

6）2hn.（双环网络),(hnD 是如下定义的有向图：其结点集是}1,1,0{-=nZnL, 边集是}10：)(mod),(mod1{-++=ninhiiniiE.设rhrqhwhrrqhn/)其中，源结点至目的结点最短路径的算法，这样的算法最多只要2 次的算术运算和一次比较，各结点没有必要先存储网络中其他信息，而是可以提出新的紧优双环网络无限族的构造方法，这种构造不含k(0 ≤k ≤m)紧优双环网络的无限族。从一个可以表现具体的实现L 形瓦出发，利用h 和y 互素条件，构造就能实现L 形瓦的无限族，给出的7 紧优、8 紧优双环网络的无限族，并且解决好几个关于紧优双环网络无限族的公开问题，双环网络G(N ;r,s)有N 个结点 0,1,2，… ,N - 1,并从从每个结点i 发出两条有向边i →i +r(modN)和i →i+s(modN) ,其中 1 ≤r ≠s N。有一个问题是对于给定的N，如何选取r 和s 使得G(N ;r,s)有最小直径，这就可以在特殊计算环境下使用数值定义的方法。可以对最小直径超出r=1 的的相关双环网络无限族进行扩大和利用；

7）先利用之前计算出来的L-形瓦的四个参数及同余方程s_1x+s_2y ≡1(mod n)的一个解，并且给出有向双环网络G(n；s_1，s_2)的时间复杂性作为常数的最优路由算法。也就是说，经过常数时间的计算就可以得到任意两点间的一条最短的路径。如果n 是一个定值整数，使用数据算法对k-紧优的双环网络G(n；1，s)进行运算，该种算法公式具有一定的时间复杂性O(k～(2.5)n～(0.25)log n)。利用已知变量L-形瓦的相关参数原理和同余方程s_1x+s_2y ≡1(mod n)得出一个最优解，从而可以得知双环网络G(n；±s_1，±s_2)的时间复杂性计算的最优时间计算方法。也可以通过基本常数运算对两个所求点的最短距离进行精确化运算。