有向双环网络gn

有向双环网络gn

1双环网络的设计假设n和h是正整数，其中n5，2hn-1。N个节点的双环网络G(N;1,h)是如下定义的有向图:其节点集为ZN={0,1,…,N-1},边集为E={i→i+1(modN),i→i+h(modN)|i∈ZN}。双环网络由于其点对称性、连通性、易扩展性且具有一定的容错能力,已广泛地应用于局域网和计算机分布式系统的设计中。最优双环网络设计[1~3]、双环网络的寻径策略研究[4~6]及其网络的直径估计及计算一直是受到关注的研究课题。信息路由是通信网络的基本功能。若每个信息总是沿着从信源到信宿的最短路经传送,则称为最优信息路由。对于双环网络G(N;1,h),文献给出了时任意两点间最短路径的一个非常简便的算法。文献提出了“非正常节点”概念,提出的寻径策略是预先存储0~h所有“非正常节点”编号及节点0到这些节点的最短路径,以便提高寻径效率。文献也对0~h的“非正常节点”进行了研究,并给出了在满足某些条件的情况下,G(N;1,h)在区间(0,h)内不存在“非平常节点”,并给出了类似于文献的寻径策略。本文对在什么情况下,G(N;1,h)在区间(0,h)内不存在“非平常节点”,什么情况下存在“非平常节点”进行了研究。给出了双环网络G(N;1,h)在区间(0,h)内不存在“非平常节点”的充分必要条件,并得到了它的两个应用:(1)给出一类有向双环网络的单播路由算法,这个算法是简单且最优的;(2)给出了这类有向双环网络的直径公式。另外,指出了文献中两个推论的纰漏。2双环网络所含y[+h]边的最短路径网络中两个节点i与j间的距离d(i,j)定义为从i到j的最短路径的长度。网络的直径指的是网络中所有点对之间距离的最大者。用D(N;1,h)表示双环网络G(N;1,h)的直径。因为双环网络是点对称性的,所以D(N;1,h)=max{d(i,j)|0≤i,j<N}=max{d(0,j)|0≤j<N}。给定G(N;1,h),从点i到i+1的边称为[+1]边,从点i到i+h的边称为[+h]边。考虑一条从i到j的路径,它包含[+1]边、[+h]边的个数分别为x、y(x、y均为非负整数),则有j≡(i+x+yh)(modN),等式成立与边出现的顺序无关,我们可把此路径记为x[+1]+y[+h]。下面的三个定义来自文献。定义1若存在整数x,使得x[+1]是0到v(0<v<N)的路径,则称x[+1]是0到v的单一[+1]边路径。设x′[+1]是0到v的单一[+1]边路径,若不存在比x′更小的x,使x[+1]也是0到v的单一[+1]边路径,则称x′[+1]是0到v的单一[+1]边最短路径。若存在整数y,使得y[+h]是0到v(0<v<N)的路径,则称y[+h]是0到v的单一[+h]边路径。设y′[+h]是0到v的单一[+h]边路径,若不存在比y′更小的y,使y[+h]也是0到v的单一[+h]边路径,则称y′[+h]是0到v的单一[+h]边最短路径。考虑0到v(0<v<N)的最短路径,为了尽快到达v点,可优先走[+h]边,当走[+h]边不再有利时,走[+1]边,这种策略称为[+h]边优先的最短路径寻径策略。定义2设从节点0到节点v共有t条最短路径:xｖ（ｉ）[+1]+yｖ（ｉ）[+h](i=1,2,…,t),若yｖ（ｊ）=max{yｖ（ｉ）,i=1,2,…,t},且所有[+h]边依次在前,所有[+1]边依次在后,则称xｖ（ｊ）[+1]+yｖ（ｊ）[+h]为从节点0到节点v的[+h]边优先最短路径。定义3称以下节点为节点0所对应的“非平常节点”:0到它们的[+h]边优先最短路径正好就是它们的单一[+h]边最短路径。比如,双环网络G(26;1,11)中节点0所对应的“非平常节点”为:7,11,18,22。在区间(0,11)内节点0所对应的“非平常节点”为7。0到7的最短路径是3[+11],路径长度为3。下面将给出关于节点0所对应的“非平常节点”的若干性质。为了方便起见,把G(N;1,h)中在区间(0,h)内节点0所对应的“非平常节点”简称为在区间(0,h)内的“非平常节点”。比如,网络G(26;1,11)中,在区间(0,11)内的“非平常节点”为7。以下总设N、p、h为正整数,且N≥5,p≥1,h≥2,q为非负整数,0≤q≤h-1。引理1给定双环网络G(N;1,h),其中N=ph+q,0≤q≤h-1,则G(N;1,h)在区间(0,h)内至少存在一个“非平常节点”的充分必要条件是存在两个正整数x、xｈ,使得x≤xｈ<h,且xh≡xｈ(modN)。证明若G(N;1,h)在区间(0,h)内存在一个“非平常节点”xｈ,按照定义3可设0[+1]+x[+h]是0到xｈ的最短路径。因为xｈ[+1]+0[+h]是0到xｈ的一条路径,所以有x≤xｈ<h,且xh≡xｈ(modN)。另一方面,若存在两个正整数x、xｈ使得式(1)成立:不妨设xｈ是使得式(1)成立的最小正整数,对于使得式(1)成立的最小正整数xｈ,x是使得式(1)成立的最小正整数。现证0[+1]+x[+h]是0到xｈ的一条最短路径。用反证法,若i[+1]+j[+h]是0到xｈ的一条最短路径且i+j<x≤xｈ。(1)当i=0时,则有jh≡xｈ(modN)且j<x≤xｈ<h。这与假设对于给定的xｈ,x也是使得x≤xｈ<h,且xh≡xｈ(modN)成立的最小正整数矛盾!(2)当i>0时,则有xｈ≡i+jh(modN),即jh≡xｈ-i(modN)且j<xｈ-i<h。这与假设xｈ是使得x≤xｈ<h,且xh≡xｈ(modN)成立的最小正整数矛盾!从上可知,0[+1]+x[+h]是0到xh的一条最短路径,它也是单一[+h]边最短路径,即xh是G(N;1,h)在区间(0,h)内的一个“非平常节点”。□3双环网络的假设这一节将对在什么情况下,G(N;1,h)在区间(0,h)内不存在“非平常节点”,什么情况下存在“非平常节点”进行研究。定理1给定双环网络G(N;1,h),设N=ph+q,1≤q≤h-1,若p+q≥h,则G(N;1,h)在区间(0,h)内不存在“非平常节点”。证明令t=p+q-h≥0,则有N+p-t=(p+1)h。用反证法,若在区间(0,h)内有一个“非平常节点”,则存在两个正整数x、xｈ,使得x≤xｈ<h,且:设x=l(p+1)+r,其中0≤r≤p,由式(2)可得[l(p+1)+r]h≡xh(modN),即:因为p-t=p-(p+q-h)=h-q≥1,所以0≤l(p-t)≤l(p+1)+r=x<h。(1)当r=0,由式(3)可得xｈ=l(p-t),因此x=l(p+1)+r>xｈ,这与x≤xｈ的假设矛盾!(2)当1≤r<p,由式(3)可得xｈ=l(p-t)+rh≥h,这与xｈ<h的假设矛盾!(3)当r=p,由式(3)可得l(p-t)+ph+q≡xｈ+q(modN),即l(p-t)≡xｈ+q(modN)。因此l(p-t)=xｈ+q,从而xｈ<l(p-t)<x,这与x≤xｈ<h的假设矛盾!□定理2给定双环网络G(N;1,h),若N=ph,则G(N;1,h)在区间(0,h)内不存在“非平常节点”。证明用反证法,若在区间(0,h)内有一个“非平常节点”,则存在两个正整数x、xｈ,使得x≤xｈ<h,且:设x=lp+r,其中0≤r≤p-1,由式(4)可得(lp+r)h≡xh(modN),即:因此,rh=xh。因为xh>0,所以r≥1,xh=rh≥h,这与xh<h的假设矛盾!□推论1给定双环网络G(N;1,h),设N=ph+q,0≤q≤h-1,当时,G(N;1,h)在区间(0,h)内不存在“非平常节点”。证明当q=0时,由定理2可知,G(N;1,h)在区间(0,h)内不存在“非平常节点”。当q>0时,因为p=(N-q)/h>(N-h)/h=N/h-1≥h-1,所以有1≤q≤h-1且p+q≥h。由定理1可知,G(N;1,h)在区间(0,h)内不存在“非平常节点”。□推论2对于给定的正整数N≥5,令h=s+1。若N≠s2,则G(N;1,h)在区间(0,h)内不存在“非平常节点”。证明设N=ph+q,0≤q≤h-1。因为N≠s２,所以可把N分为下列四种情形进行讨论:(1)当N=s２+r,1≤r<s时,可得N=(s-1)(s+1)+r+1=(s-1)h+r+1,即p=s-1,q=r+1。此时p+q=s+r≥s+1=h。(2)当N=s２+s时,可得N=s(s+1),即p=s,q=0。(3)当N=s２+s+r,1≤r<s时,可得N=s(s+1)+r,即p=s,q=r。此时p+q=s+r≥s+1=h。(4)当N=s2+2s时,可得N=s(s+1)+s,即p=s,q=s。此时p+q=2s=h+s-1≥h。对于上面的第(1)、(3)、(4)三种情形,均有p+q≥h,由定理1可知在这三种情形下,G(N;1,h)在区间(0,h)内不存在“非平常节点”。对于上面的第(2)种情形,因为q=0,由定理2可知在这种情形下,G(N;1,h)在区间(0,h)内也不存在“非平常节点”。□引理2给定双环网络G(N;1,h),设N=ph+q,1≤q≤h-1,若p+q≤h-1,则G(N;1,h)在区间(0,h)内至少存在一个“非平常节点”。证明因为p+q≤h-1且1≤q≤h-1,所以有p+1≤h-q<h。因此,存在两个正整数p+1、h-q,使得p+1≤h-q<h且:从式(6)及引理1可知,区间(0,h)内至少存在一个“非平常节点”。□由定理1、定理2及引理2,可得如下的定理3。定理3给定双环网络G(N;1,h),设N=ph+q,0≤q≤h-1,则G(N;1,h)在区间(0,h)内不存在“非平常节点”的充分必要条件是q=0或1≤q≤h-1且p+q≥h。4双环网络的最短路径法这一节将利用上一节得到的结论,给出它们的两个应用:(1)当G(N;1,h)在区间(0,h)内不存在“非平常节点”时,其直径公式特别简单。(2)当G(N;1,h)在区间(0,h)内不存在“非平常节点”时,我们将给出一个简单且最优的单播路由算法,此算法适用的范围大于文献给出的范围(仅有一种情况除外)。引理3给定双环网络G(N;1,h),设N=ph+q,0≤q≤h-1,则G(N;1,h)的直径D(N;1,h)≤p+h-2。证明当0≤j≤(p-1)h+h-1时,设j=xh+y,其中0≤y≤h-1,则有x≤p-1,y≤h-1。注意到y[+1]+x[+h]是0到j的一条路径,因此有d(0,j)≤x+y≤p+h-2。当ph≤j≤N-1=ph+q-1时,设j=ph+y,其中0≤y≤q-1,注意到y[+1]+p[+h]是0到j的一条路径,因此有d(0,j)≤p+y≤p+q-1≤p+h-2。由上可知,D(N;1,h)=max{d(0,j)|0≤j<N}≤p+h-2。□定理4给定双环网络G(N;1,h),设N=ph+q,0≤q≤h-1,若G(N;1,h)在区间(0,h)内不存在“非平常节点”(即q=0或1≤q≤h-1且p+q≥h),则G(N;1,h)的直径为D(N;1,h)=p+h-2。证明先证(h-1)[+1]+(p-1)[+h]是0到(p-1)h+h-1=ph-1的一条最短路径。用反证法,若它不是最短路径,假设x[+1]+y[+h](其中0≤x<h-1,y>p-1)是0到ph-1的一条最短路径且x+y<p+h-2。可知0[+1]+(y-p+1)[+h]是0到h-1-x的一条路径。因为y-p+1<h-1-x且(y-p+1)h≡h-1-x(modN),由引理1可知,G(N;1,h)在区间(0,h)内至少存在一个“非平常节点”,这与G(N;1,h)在区间(0,h)内不存在“非平常节点”矛盾!从上可知,(h-1)[+1]+(p-1)[+h]是0到ph-1的一条最短路径,从而有d(0,ph-1)=p+h-2。这样可得,D(N;1,h)=max{d(0,j)|0≤j<N}≥d(0,ph-1)=p+h-2。由引理3,D(N;1,h)≤p+h-2,即可得D(N;1,h)=p+h-2。□从推论1和推论2可知,此定理拓广了文献中定理5的范围(仅有一种情况G(s２;1,s+1)除外)。比如,双环网络G(42;1,9)的步长9大于它不在文献中定理5所确定的范围。然而,因为42=4×9+6,4+6>9,据定理4可知,双环网络G(42;1,9)的直径等于4+9-2=11。文献中的两个推论有误,现举例说明之。文献中的推论2有误。取h=100,p=100,q=99,N=10099。所给的双环网络符合推论2的条件,按照推论2的公式,双环网络G(10099;1,100)的直径为max{p-1+h-1,p+q}=max{198,199}=199。然而根据定理4,双环网络G(10099;1,100)的直径应为p+h-2=100+100-2=198。文献中的推论3有误。为了讨论方便起见,现把其摘录如下:“推论3在G(N;1,h)中,当d>p+h-2时,则在0→h内至少存在一个‘非平常节点’(其中d指的是网络G(N;1,h)的直径)。”从引理2可知,不管在什么情况下,双环网络G(N;1,h)的直径是小于或等于p+h-2,不可能出现G(N;1,h)直径大于p+h-2的情况,因此推论3所给的条件是没有意义的。定理5给定双环网络G(N;1,h),设N=ph+q,0≤q≤h-1,当G(N;1,h)在区间(0,h)内不存在“非平常节点”时(即q=0或1≤q≤h-1且p+q≥h),G(N;1,h)存在简单且最优的单播路由算法:从0到v(其中1≤v≤N-1,v=mh+n,0≤m≤p,0≤n<h)的最短路径为n[+1]+m[+h]。证明用反证法,若n[+1]+m[+h]不是最短路径,假设x[+1]+y[+h](其中0≤x<h,y≥0)是0到v的一条最短路径,x+y<m+n。现在分三种情形证之。情形1y>m。由mh+n≡yh+x(modN)及x+y<m+n,可得n-x≡(y-m)h(modN)且0<y-m<n-x<h,由引理1可知,G(N;1,h)在区间(0,h)内至少存在一个“非平常节点”,这与G(N;1,h)在区间(0,h)内不存在“非平常节点”矛盾!情形2y=m。由mh+n≡yh+x(modN)及x+y<m+n,可得n-x≡0(modN)且0<n-x<h,可得n-x=kN,k≥1,即n-x>h,这与0<n-x<h矛盾!情形3y<m。若x≤n,则由mh+n≡yh+x(modN),可得(m-y)h+n-x≡0(modN)。即0<(m-y)h+n-x=kN,k≥1,这与0<