收稿日期:2007209206
基金项目：山西省软科学基金资助项目(2007041023204)
作者简介：刘三满(1968—
)，女，副教授,E 2mail :liusanman @第28卷 第3期
2008年3月北京理工大学学报
Transactions of Beijing Institute of Technology
Vol.28 No.3Mar.2008
刘三满
(山西警官高等专科学校计算机科学与技术系，山西，太原 030021)
摘 要：提出一种新的互联网络拓扑结构———基于交叉立方体环连接的Petersen 图互联网络RC P (n ).研究互联网络RC P (n )的通信特性.通过RC P (n )的单播路由算法、广播路由算法、可分组性算法，证明RC P (n )不仅具有环、彼特森图和交叉立方体本身所具有的性质，同时又具有自身独特的拓扑性质.研究结果表明,R C P (n )是一种具有良好拓扑结构和通信特性的互联网络.在通信效率上的花费只有由超立方体构成的互联网络的1/2，而通信效率却是由超立方体构成的互联网络的一倍. 关键词:RC P (n )互联网络；拓扑结构；可分组性；最优分组
中图分类号:T P 301 文献标识码:A 文章编号:100120645(2008)0320215203
Optimization Design of Topological Structure on
Interconnection N et w orks —RCP(n )
L IU San 2man
(Department of Computer Science &Technology ,Shanxi Police Academy ,Taiyuan ,Shanxi 030021,China )
Abstract :Propo ses a kind of new internet topology —t he Petersen network which inter 2connect s
on t he overlapping cube link chart ,or internet RCP (n ).St udies t he internet RCP (n )correspondence characteristics ,broadcast s t he route and broadcasted route ,and it s respective grouping.Through RCP (n )broadcast route algorit hm ,RCP (n )grouping algorit hm ,it is proved t hat RCP (n )not only has t he nat ure which t he link ,Pitt woods chart and overlapping cube it self has ,it also has it s own unique topological property.It is indicated t hat ,RCP (n )is a kind has of network t hat has it s good topology and correspondence characteristics of t he internet but it has t he correspondence efficiency twice t hat of t he ult ra cube constit ution internet ,but act ually requiring only half t he expendit ure of time by t he ult ra cube.K ey w ords :RCP (n )Internet ;topology ;grouping ;superior grouping
1 互联网络RCP (n )的构造及其拓扑
性质
随着互联网络中处理器数量的日益增加，如何设计出大规模、高性能的互联网络是当前研究热点之一.基于交叉立方体环连接的Petersen 图互联网络R C P (n )是一种新型互联网络.
交叉立方体作为超立方体的一个变种，其拓扑结构的改变使其更具有一些比超立方体更优越的性
质[1].如其直径大约是超立方体的1/2，更精确地表示为(n +1)/2，这使由交叉立方体构成的互联网络在通信效率上的花费只有由超立方体构成的互联网络的1/2即可.
性质1 R C P (n )网络具有115625×2n 个节点. 性质2 R C P (n )网络中任意节点的连接度均为n .
证明 由R C P (n )网络的构造易知,R C P (n )中
任意节点的连接度=节点在n-5维交叉立方体中的连接度+节点在环中的连接度+节点在彼特森图中的连接度=(n-5)+2+3=n.
性质3 R C P(n)网络是正则对称网络.
证明 由环、交叉立方体和彼特森图的正则性和对称性以及R C P(n)互联网络的构造易知, R C P(n)互联网络是n正则网络.
性质4 R C P(n)网络的连通度为n.
证明 由R C P(n)网络的构造和性质易知, R C P(n)网络的连通度为n.
性质5 RC P(n)网络的直径约为(n+3)/
2.
证明 由于交叉立方体的直径约为超立方体的1/2，因此R C P(n)网络的直径≈(n-5维超立方体的直径)/2+环的直径+彼特森图的直径=(n
-5)/
2+2+2=(n+3)/
2.
R C P(n)不仅具有环、彼特森图和交叉立方体本身所具有的性质，同时又具有自身独特的拓扑性质，因此R C P(n)是一种具有良好拓扑性质的互联网络.
2 互联网络(n)的通信特性本文中主要研究R C P(n)的单播和广播的路由算法及可分组性等通信特性.
211 RCP(n)的单播路由算法
单播通信(即点到点通信)是互联网络最基本的操作，其他操作都是建立在此操作的基础上的.假设源节点A(r1,s1,t1)向目标节点B(r2,s2,t2)发送数据，按照最短路径方法，可给出该算法如下[2]. 21111 算法1———R C P(n)的单播路由算法
①若A,B在同一个交叉立方体中，假设A,B 的距离为l，则如果l=1，则A直接向B发送数据；否则A先将数据发送到与B的距离为l-1的邻节点，再由该邻节点将数据发送到与B的距离为l-2的邻节点，直到将数据发送给B.
②若A,B不在同一个交叉立方体中，但在同一个组中，则A首先按①将数据发送到自己所在的交叉立方体中的t2号节点，再由t2号节点沿彼特森图按如下方法将数据转发给B.如果它们相连，则t2号节点直接向B发送数据；否则t2号节点先将数据发送到它与B的公共邻节点，再由该节点将数据发送给B.
③若A,B不在同一个组中，则A先将数据沿环发送到B所在的r2组内s1号交叉立方体中的t1号节点，再由该t1号节点按算法1的①或②将数据转发给B.
21112 算法1的性能分析
按最短路径路由算法，数据在环中传播最坏的情形下需要2轮通信操作，在交叉立方体中传播最坏情形下约需要(n-5)/2轮通信操作，在同一个彼特森图中传播最坏情形下需要2轮通信操作.因此，在最坏情形下RCP(n)互联网络中从任一源节点A向其他任一目标节点B进行单播时，采用算法1总共约需要2+(n-5)/2+2=(n+3)/2轮通信操作.
由于Q n的直径为n,H P(n)和R H P(n)的直径均为n-1，而R C P(n)的直径仅为(n+3)/
2，因此当n≥3时，有如下结论.
性质6 在网络规模相同的情况下,R C P(n)的单播路由算法的路由性能要优于Q n,H P(n)和R H P(n)网络的单播路由算法的路由性能.
212 RCP(n)的广播路由算法
广播通信也是互联网络的基本操作，其语义是将某一个源节点的数据广播到其他所有节点中.设A为R C P(n)中一个源节点,R C P(n)的广播路由算法如下[3].
21211 算法2———R C P(n)的广播路由算法
①在A所在的彼特森图中进行广播.
②收到信息的节点将信息扩散给自己所在的环上的所有其他节点.
③收到信息的所有节点将信息扩散给自己所在的交叉立方体之内的所有其他节点.
21212 算法2的性能分析
执行算法2的步①需要2轮通信操作，执行算法2的步②需要2轮通信操作，执行算法2的步③需要约(n-5)/2轮操作，因此整个广播需要2+ (n-5)/2+2=(n+3)/
2轮通信操作.
性质7 在网络规模相同的情况下,R C P(n)的广播路由算法的路由性能要优于Q n,H P(n)和R H P(n)网络的广播路由算法的路由性能.
213 RCP(n)的可分组性
并行程序要在一组节点内进行频繁的通信，组内的通信性能对程序的效率影响非常大.为此，已给一个
互联网络N和其上的一组节点G，引入最优分组和可分组性的概念[4-5].
定义1 (最优分组)对已给正整数λ，互联网络N存在多个包含λ个节点的节点组，称距离最短
612北京理工大学学报第28卷
的组为含有λ个节点的最优分组，记为G λ(N ).
定义2 (可分组性)对于已给的两个互联网络
N 1和N 2，若对于任意一个正整数λ，有G
λ(N 1)的距离≤G λ(N 2)的距离，那么，称N 1的可分组性优于互联网络N 2的可分组性.
如果互联网络N 1的可分组性优于互联网络N 2的可分组性，则利用G λ(N 1)作为一组计算节点
的通信开销就小于G
λ(N 2)作为一组计算节点的通信开销，因此互联网络的可分组性具有重要的意义.由R C P (n )互联网络的构造与文献易知,R C P (n ),R H P (n ),R P (n )以及二维Torus 网络的最优分组距离(记为d )分别为
d (G λ(RCP (n )))=
1
(λ=2)2
(2<λ≤10)2+(λ+3)div20(10<λ≤50)5+
lb ((λ+3
)div100)
(λ>50)
,
(1)
d (G λ(R H
P (n )))=
1(λ=2)2
(2<λ≤10)2+(λ-1)div10(10<λ≤50)5
+
lb ((λ-1)div50)
(λ>50)
,
(2)d (G λ(RP (n )))=
1
(λ=2)2+(λ-1)div10
(λ≥3)
,
(3)
d (G λ(Torus ))=2×(λ-1).
(4)
由式(1)～(4)易证下列性质成立.
性质8 R C P (n )的可分组性优于R H P (n )的可分组性.
证明 由式(1)和式(2)可知，当2<λ≤10时,d (G λ(R
C P (n )))=d (G λ(R H P (n
)))=2;
当10<λ≤
50时,d (G λ(RCP (n )))=2+(λ+3)div20<d (G λ(R HP
(n )))=5+lb ((λ-1)div50
)；当λ>50时,d (
G λ(RCP (n )))=5+lb ((λ+3)div100)<d (G λ(R H P (n )))=5+lb ((λ-1)div50)
;
综上所述，有d (G λ(R C P (n )))≤d (G λ×(R H P (n )))，即R C P (n )的可分组性优于R H P (n )的可分组性.
性质9 R C P (n )的可分组性优于R P (n )的可
分组性.
证明 由式(1)和式(3)可知，当λ=2时,d (G
λ(R C P (n )))=d (G λ(R P (n )
))=1；当2<λ≤10时,d (G
λ(R C P (n )))=
2<d (G λ×(R P
(n )))=2+(
λ-1)di v10；当10<λ
≤50时,d (G λ(R C P (n )))=2+
(λ+20
)di v20<d (G λ(R P (n )))=(
λ-1)di v10；当λ>50时
,
d (G λ(R C P (n )))=5+lb ((
λ+3)di v100)<d (G
λ(R P (n )))=(λ-1)di v10；综上所述，有d (G λ×(R C P (n )))≤d (G λ×(R C P (n )))，即R C P (n )的可分组性优于R H P (n )
的可分组性.
性质10 R C P (n )的可分组性优于二维Torus 的可分组性.
证明 由式(1)和式(4)可知，当λ≤50时，易证d (G λ(R C P (n )))≤d (G λ(Torus ))；因此只需要证明λ>50时结论成立即可.
由于λ>50，故不妨设λ=50k ,k >1.构造函数f (k )=214k -7-k -0103，求导后f ′(k )>0]f (k )单调递增.
再由f (1
)>0有214
k -7
-k -
0103>0]
14k -7>lb (k +01
03)]5+
lb (k +0
103
)<14k -2]5+
lb ((50k +3)di v100)
<
5+lb ((100k +3)di v100)<5+
lb k
<
14
k
-
2<2(
50k -1)]5+lb ((
λ+3)di v100)<2(λ-1).
综上所述，有d (G λ(R C P (n ))≤d (G λ(Torus ))
成立.证毕.
3 结束语
由以上论述可知,R C P (n )是一种具有良好通信特性的互联网络拓扑结构.其拓扑结构的改变使其更具有一些比超立方体更优越的性质，在通信效率上的花费只有由超立方体构成的互联网络的1/2，而通信效率却是由超立方体构成的互联网络的一倍.
参考文献:
[1]刘方爱，刘志勇，乔香珍.一种适用的互联网络拓扑结构
RP (k )及路由算法[J ].中国科学:E 辑,2002,32(3):3802385.
(下转第240面)
7
12第3期刘三满：互联网络RCP (n )的拓扑结构优化设计
212 扰动实验
输入信号为幅值8μm 的阶跃，扰动为幅值014μm ，频率2k Hz 的正弦信号，则3种控制器的响应曲线如图3所示，各线型定义与图2相同.在首次达到终值后,IASMC 控制器的平均波动值为0.0329μm ,SMC 控制器平均波动值为0.0442μm ,IPID 控制器平均波动值为0.1885μm ,IASMC 和SMC 对扰动抑制能力较强 .
图3 正弦扰动时各控制器阶跃响应曲线Fig.3 Step responses of different controllers
under sinusoidal disturbance
213 参数不确定性实验
当开环增益分别为K =1100和K =0.75时，输
入信号为幅值8μm 的阶跃,t =2ms 后,IASMC 控制器|e |max 从2117×10-4μm 变化到3181×10-3μm ,SMC 控制器的|e |max 从3112×10-3μm 变化到4154×10-2μm ,IPID 控制器|e |
max
从7107×10-3
μm 变化到0.12μm.3种控制器的响应时间均有所
增加，但是IASMC 控制器性能仍优于其他两种，对于参数的变化具有良好的鲁棒性.
3 结 论
在建立Preisach 逆模型补偿压电陶瓷执行器的迟滞特性的基础上，针对未被完全补偿的迟滞非线性和系统的不确定性设计自适应滑模变结构控制器，与常规滑模控制器以及结合逆模型补偿的PID 控制器
进行比较，在不同的输入信号下，该控制器的跟踪精度和鲁棒性均有改善.今后的工作将是将在实验平台上实现该控制算法，并验证其性能.
参考文献:
[1]Song G ,Zhao J Q ,Zhou X Q ,et al.Tracking control
of a piezoceramic actuator with hysteresis compensation using inverse preisach model [J ].IEEE Transactions on Mechatronics ,2005,10(2):1982209.
[2]G e P ,Jouaneh M.Tracking control of a piezoceramic
actuator [J ].IEEE Transactions on Control Systems Technology ,1996,4(3):2092216.
[3]Sabanovic A ,Abidi K ,Elitas M.A study on high accu 2
racy discrete 2time sliding mode control[C]∥Proceedings of 12th International Power Electronics and Motion Con 2trol Conference.Portoroz ,Slovenia :IEEE Press ,2006:3552360.
[4]Mayergoyz I D.Mathematical models of hysteresis[M ].
New Y ork :Springer 2Verlag ,1991:1228.
[5]Brokat M ,Sprekels J.Hysteresis and phase transitions
[M ].New Y ork :Spinger 2Verlag ,1996.
[6]J ean 2J acques E S ,Li W.Applied nonlinear control[M ].
Beijing :China Machine Press ,2006:81284.
(责任编辑：康晓伟)
(上接第217面)
L i u Fang ’ai ,L i u Zhi yong ,Qiao X iangz hen.A use of the internet netw ork topolog y R P (k )and the routing al gorithm [J ].
Science in China :series E ,2002,
32(3):3802385.(in Chinese )
[2]刘方爱，刘志勇，乔香珍.光R P (k )网络上的H y percube
通信模式的波长指派算法[J ].软件学报,2003,14(3):
5752581.
L i u Fang ’ai ,L i u Zhi yong ,Qi ao X iangz hen.R P (k )netw ork of hy percube comm unication w avelength as 2si gnment al gorithm [J ].J ournal of S of tw are ,2003,
14(3):5752581.(in Chinese )
[3]王雷，林亚平.基于超立方体环连接的Petersen 图互联
网络研究[J ].计算机学报,2005,28(3):4092413.
W ang L ei ,L in Yaping.B ased on the hy percube ring connecting the Petersen g rap h I nternet research [J ].Chinese J ournal of Com p uter ,2005,28(3):4092413.(in Chinese )
[4]N aserasr R ,S k rekovski R.T he petersen g rap h is not
32ed ge 2colorable :a new p roof [J ].Discrete M athmat 2ics ,2003,268(123):3252326.
[5]L a Forge L E ,Fadali M S.W hat desi gners of bus and
netw ork architectures shoul d know about hy percubes [J ].I E E E T rans on Com puters ,2003,52(4):5252544.
(责任编辑：刘雨)
042北京理工大学学报第28卷
