有向双环网络的单播路由算法研究
有向双环网络的单播路由算法研究
1、引言
设N和h是正整数,其中 N ≥5,2≤h ≤N-1。N个节点的双环网络 G(N;1,h)是如下定义的有向图:其
节点集为 ZN={0,1,…,N -1},边集为 E={i→i+1(mod N),i→i+h(mod N)|i ZN}∈。双环网络由于其
点对称性、连通性、易扩展性且具有一定的容错能力,已广泛地应用于局域网和计算机分布式系
统的设计中。最优双环网络设计、双环网络的寻径策略研究及其网络的直径估计及计算一直是
受到关注的研究课题。
信息路由是通信网络的基本功能。若每个信息总是沿着从信源到信宿的最短路经传送,则称为最
优信息路由。对于双环网络 G(N;1,h),文献[6]给出了 2≤h≤ N +1�� 时任意两点间最短路径的一
个非常简便的算法。文献[4] “ ”提出了 非正常节点 概念,提出的寻径策略是预先存储 0~h “所有 非
”正常节点 编号及节点 0到这些节点的最短路径,以便提高寻径效率。文献[5]也对 0~h “的 非正常
”节点 进行了研究,并给出了在满足某些条件的情况下,G(N;1,h) 在区间 (0,h) “内不存在 非平常节
”点,并给出了类似于文献[4]的寻径策略。
本文对在什么情况下,G(N;1,h) 在区间 (0,h) “ ”内不存在 非平常节点 , “什么情况下存在 非平常节
”点 进行了研究。给出了双环网络 G(N;1,h) 在区间 (0,h) “ ”内不存在 非平常节点 的充分必要条件,
并得到了它的两个应用:(1)给出一类有向双环网络的单播路由算法,这个算法是简单且最优的;(2)
给出了这类有向双环网络的直径公式。另外,指出了文献[5]中两个推论的纰漏。
2、定义及引理
网络中两个节点 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)(mod N),等式
成立与边出现的顺序无关,我们可把此路径记为 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(i)v[+1]+y(i)v[+h](i = 1,2,…,t),若y(j)v=max{y(i)v,i=1,2,…,t},且所有[+h]边依次在前,所有[+1]
边依次在后,则称 x(j)v[+1]+y(j)v[+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、xh,使得 x ≤xh<h,且xh ≡xh(mod N)。证明若
G(N;1,h) 在区间 (0,h) “ ”内存在一个 非平常节点 xh,按照定义 3可设 0[+1]+x[+h]是0到xh 的最短
路径。因为 xh[+1]+0[+h]是0到xh 的一条路径,所以有 x≤xh<h,且xh ≡xh(mod N)。
另一方面,若存在两个正整数 x、xh 使得式(1)成立:x≤xh<h,且xh ≡xh(mod N) (1)不妨设 xh 是使得
式(1)成立的最小正整数,对于使得式(1)成立的最小正整数 xh,x 是使得式(1)成立的最小正整数。
现证 0[+1]+x[+h]是0到xh 的一条最短路径。用反证法,若i[+1]+j[+h]是0到xh 的一条最短路径
且i+j<x≤xh。
(1)当i=0 时,则有 jh≡xh(mod N)且j<x≤xh<h。这与假设对于给定的 xh,x 也是使得 x≤xh<h,且
xh≡xh(mod N)成立的最小正整数矛盾!
(2)当i>0 时,则有 xh≡i+jh(mod N),即jh ≡xh-i(mod N)且j<xh-i<h。这与假设 xh 是使得 x ≤xh<h,且
xh≡xh(mod N)成立的最小正整数矛盾!
从上可知,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、xh,使得 x≤xh<h,且:xh ≡xh(mod N) (2)设x=l(p+1)+r,
其中 0≤r≤p,由式(2) 可得 [l(p+1)+r]h≡xh(mod N),即:l(p-t)+rh ≡xh(mod N) (3)因为 p-t=p-(p+q-h)=h-
q≥1,所以 0≤l(p-t)≤l(p+1)+r=x<h。
(1)当r=0,由式(3)可得 xh=l(p-t),因此 x=l(p+1)+r>xh,这与 x≤xh 的假设矛盾!
(2)当1≤r<p,由式(3)可得 xh=l(p-t)+rh≥h,这与 xh<h 的假设矛盾!
(3)当r=p,由式(3)可得 l(p-t)+ph+q≡xh+q(mod N),即l(p-t)≡xh+q(mod N)。
因此 l(p-t)=xh+q,从而 xh<l(p-t)<x,这与 x≤xh<h 的假设矛盾!
定理 2给定双环网络 G(N;1,h),若N =ph,则G(N;1,h) 在区间 (0,h) “ ”内不存在 非平常节点 。证明用
反证法, 若在区间 (0,h) “ ”内有一个 非平常节点 ,则存在两个正整数 x、xh,使得 x≤xh<h,且:xh
≡xh(mod N) (4)设x=lp+r,其中 0≤r≤p-1,由式(4) 可得 (lp+r)h≡xh(mod N),即:rh ≡xh(mod N) (5)因
此,rh =xh。因为 xh>0,所以 r≥1,xh=rh ≥h,这与 xh<h 的假设矛盾!
推论 1给定双环网络 G(N;1,h),设N =ph+q,0≤q≤h-1,当h≤ N�� 时,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,令s= N,h=s+1�� 。若 N ≠s2,则G(N;1,h) 在区间 (0,h)内不存
“ ”在 非平常节点 。证明设 N =ph+q,0≤q≤h-1。因为 N ≠s2,所以可把 N分为下列四种情形进行讨
论:
(1)当N =s2+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 =s2+s 时,可得 N =s(s+1),即p=s,q=0。
摘要：
展开>>
收起<<
有向双环网络的单播路由算法研究1、引言设N和h是正整数,其中N≥5,2≤h≤N-1。N个节点的双环网络G(N;1,h)是如下定义的有向图:其节点集为ZN={0,1,…,N-1},边集为E={i→i+1(modN),i→i+h(modN)|iZN}∈。双环网络由于其点对称性、连通性、易扩展性且具有一定的容错能力,已广泛地应用于局域网和计算机分布式系统的设计中。最优双环网络设计、双环网络的寻径策略研究及其网络的直径估计及计算一直是受到关注的研究课题。信息路由是通信网络的基本功能。若每个信息总是沿着从信源到信宿的最短路经传送,则称为最优信息路由。对于双环网络G(N;1,h),文献[6]给出了2≤h≤...
相关推荐
-
福特锐界汽车营销策略
2022-10-15 114 -
车联网面临的安全风险与应对措施
2023-02-25 144 -
保险营销的现存问题与策略创新
2023-02-25 72 -
保险经纪人作为保险营销主要力量的探析
2023-02-25 77 -
我国家政服务质量的问题及提升对策
2023-05-24 133 -
微波通信的优点及其在移动通信网络中的具体应用
2023-05-24 295 -
网络信息安全中密码学的运用及其安全性分析
2023-05-24 118 -
探讨卫星通信组网在人防中的应用
2023-05-24 103 -
探讨傣族服饰文化融入幼儿园美术教育的有效路径
2023-05-24 73 -
我国中小企业电子商务管理现状分析
2024-03-02 33
作者：闻远设计
分类：其它行业资料
价格：免费
属性：4 页
大小：15.49KB
格式：DOCX
时间：2024-03-09
