双归属环形网络拓扑规划算法设计

1、电信科学2012年第8期研究与开发双归属环形网络拓扑规划算法设计卢研平，吕光宏(四川大学计算机学院 成都610()65)愛木文研克了-种岛效的双归属环形网络拓扑规划劇.捉川了圧满坏I满环耐整节点的启发式捜 索鼻法，半节点数任I 500个以内时.本再法都能很快求解.而现有舁法通常只能处理儿百个节点的中 彎规模网络。木文杵先给出了相关数学模型然后详述了初始Ki扑生成过程及采用的川发式优化体法。 忆后通过将CPIJ-X规划结果、人工规划结果和并法规划进行比卷验程蒔法性能,关键词 女归顶：环形拓扑；启发式却法；铁数现划? 1994-2015 China Academic Journal Electro

2、nic Publishing House. All rights reserved, 电信科学2012年第8期? 1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 电信科学2012年第8期1引言坏网在保护技术上仃天然的优势，足电信级网络的一 种匝耍拓朴 o SDH/SONET (synchronous digital hieraivhy/ synchronous optical networking)和 DM(wavelength-division multiplexing)都离

3、不开环网结构。随着对业务保护耍求的 不断提高，双归属环网使用越来越广泛。环网拓扑设计是 整个环网规划的基础，受到广泛关注。參考文献I中将自 愈环用于本地网络设计。随着通信技术的发展和业务需求 的改变，环形拓扑仗讣问题也变的多样化.参羽文献2 提岀了一种用贪婪算法求解单归属环网设计法。参考 文献3将同样的方法扩展为求解双归属环网。簽考 文献2和卩屮的方法仅能处理大约150个节点,而現代 网络中节.个数常常超过150个，因此对算法性能提出了 新的耍求。参考文献4中介绍了圧于模拟退火的单归属坏 形网络拓扑设计算法算法能处理300个节点参考文献5 中采用分支界定法求解环网拓扑，此蒂确算法只能求解 20

4、个节点以内小规模网络.：参考文献16中作者使用1 规划技术设计环拓扑，以环容量作为约束，没有考虑汇聚 环和4地环代价参考文献|7汝让的环网拓扑结构屮一个 节点可能屈于多个环:,参考文駅8屮仪考虑按入环议 计参考文献9用公式求解但没冇严格约束本地环到汇 聚环级联方式本文提出了一种快速求解双归屈环形网络 拓扑的方法，图1给出典型环形拓扑构崖的网络拓扑：水算*可在较短时间内求解1 500个节点左右的网 络本文的算法熏点解决IP RAN(radio access networks)的損入节成图1网络拓扑结构传输网规划问題用于种代H前的人工规划，本席法也适 用于一般的两层双归属环网拓扑设计，当限制汇集环

5、个数 为1个时拓扑结构和参考文献4屮相同，本郭法以插件的形式集成到网络規划仿真软件 OPNET中，已用于实际网络规划且取得良好效果:2问题模型2.1问题推述在IP RAN的传输网部分，通常采用环网结构，第一 层和第二层分别为接入层和汇聚层，接入层由48个路由 器构成环形结构：在双归屈结构屮，按入坏双挂到汇聚环， 汇聚环节点个数为25个，汇聚层由多个汇聚环构成，汇 聚环进一步级联到ITT路由器本第法朿点解决节点最 多、人工规划难度最大的接入环和汇聚环网络规划设计问 题该问題中已知接入节点和汇聚节点的经纬度坐标，以 接入环节点个数、汇聚环节点个数作为约東条件，在满足 双归属环形柘扑条件下，使总链路

6、距离代价赧小为尽昴 真实评估网络的距离代价,笔肴采用球面距离。在求解拓 扑时，必须满足以卞约束条件：汇聚坏节点个数不趙过N个；汇聚环仅由汇聚节点构成;接入坏节点个数不超过M个；所右接入H点都在接入环上；接入环双归屈到汇聚环。2.2数学模型以卜什上）表示无向图，其中V表示图中布点集合厨 代我边集合JFI示G中暂点数目,1刃=。二值变駅心1 表示节点i为汇聚场点,亿=0表示节点i为接入卩点。1表示节点i在环/?,上,70表示 节点i不在环儿上，二值变気= 1表乐边5在环/?,上， 心日）则边勺不在环/?上。冃标肉数可表示为以卜形式： D =丈.0x4）I 7刈等于0表示r.和巧至少有 一个足IE汇

7、聚节点，3于1农示C乜都足汇聚节点。式巾）约束每个节点在环上的度为20式（7）约柬接入环上接入节点个数大于或等于2,小 于或等于朋，式“）约柬汇聚环节点个数大于或等于2,小于或等 于儿式W）约束所有汇聚环上总节点个数等于汇聚节点个 数，且汇聚环上所有节点都为汇聚节点。式iiom束所有节点的度大于或等于1,即所有节点 都在环上。式（11）为 f 回路约柬,由 TSP（travelling salesman problem. 旅行商问題）了回路约束变化而来，参孑文献10介绍了 TSP的整数规划方程。3求解算法笔&采用启发式IZ法求解，郭法分为两步：初始拓扑构建和拓扑优化。3.1初始拓扑构建初始拓扑

8、将也接彩响到整个算法性能,所成初始拓扑 应该尽量更优,且必须满足约束条件本算法*i,n先构建 汇聚环，在汇聚环的耳础上构建接入环构建汇聚环时先 将汇聚节点分组，每组厲个节点，再将每组生成1个环） 本文比较了两种分组算法：J-从mean聚类的分组郭法 和凤远距図分组法。进行gan聚类,A=（F+.V-I）IN；F表示汇聚节点个 数,N表示汇聚环节点个数约束:A-n）ean聚类算法根据节 点距离将汇聚n点聚为K个类，求得个聚类屮心。以这k 个中心为依据进行汇聚节点分组。每次选取一个聚类中心, 找到离直垠近的“个节点作为一个分组,直到1个聚类中 心都使用完。此步中尽量将距离近的节点聚集到一个分组:

9、在实验屮发现通过这种方法分组成坏后汇聚容易出现重 叠部分，造成距离代价増加，足又使用了眾远距离分组法 进行实验对比:该方法中，将所有汇聚节点作为一个集合, 计算中心节点。在集合中选择离中心节点最远的节点u,作 为聚类中心,选择离节点叽最近的NJ个节点和节点 构成-个分组。重复上而的步骤，直到集合中的节点全部 分组完成c使用此方法分组成环能冇效避免环出现甫 栓部分。阳2为使用阿种方法分组成环后的拓扑对比. 后面给岀了便用两种方法对实际网例规划的给果对比。 J 口（口（a）tf干Kmean 更分Hl算法（b）jft远距勇分齟注图2购神方法所成拓扑对比上文所述的步骤将汇聚节点划分为了人个集合每个 集

10、合内节点生成环，等同于在每个集合内解决TSP。笔者 采用动态規划解决応P,使用这种将硼算法可使得每个环 代价嚴小，能保证局部最优下面给出动态规划的状态转 移方程：Ci V卜min（C/,h_X，HJ e I（Ci,I；表示从0号节点IB发,经过集合V.内所有节 点一汝，止步于节点i的就小距离.表示节点个数：肖n=l 时砂冋,当n等于坏内节点个数时即町求得最优环將每条琏路上的两个汇聚节点对作为-个接入集合。 便用/仏$）表示接入节点叫到接入集合s的距离。若集介 s中的汇聚节点对为JU ）= d赳,即接入节点到汇 聚节戎r. 口的距离和）遍历所有接入节点为每个节点找 到个接入集合i,使得/（1）皿

11、）忙,将节点加入 到集合i中。下一步在每个接入汇聚集合中求解接入环。 初始狀态下,每个集合内只有一个环中仅有集合里 的两个汇聚节点。步骤1：对于他，在集合中找到一个空闲节点叽合并 到几，使得R5的代价小于步骤2：更新几节点，将刃加入到几中，如果/?,中接 入节点个数等于M（接入节点个数限制）,新建环和,将 区域中的两个汇聚借点加入到几+1中，令r = r+ 13步骤3：重复第1、2步，直到集合中节点为空。对于每个集合重复上而的3步后，所冇接入节点都 将连接到接入环上：此时的接入坏并不一定局部最优，因 此，使用前文提到的动态規划算法对每个接入环解决 TSP：最终，求得完整的初始拓扑。3.2启发式

12、优化笔者的优化方法并非自冃地旬接交换环上节点，而是 尝试粘坏上节点移动到节点个数尚未达到限制的坏，即n 点移动的i：i标环仅为那些非满环,每次节点都是单向移 动，所以这样的搜索方式能极大地减少搜索空间，便得幣 个拓扌结构能在较短时间内收敛实验证明，使用前面的 方式生成初始拓扑后，再用这种方式进行启发式搜索求得 拓扑S构效果理姐，当节点規模在150个左右时，算法所 成拓扌、距离代价通常仅为人T规划的70%启发式搜索具 体方法如下。3.2.1 n节点移动搜索境法步骤1：将汇聚环每条边上节点对作为接入环的两个 节点，为每个节点对新建一个接入环，加入到环集合R中。步骤2：遍历所有环，若/?,接入节点个

13、数加“小于或 等于船则环集合S=5U/?43步骤3：依次选择集合/?中的环代：步骤4 ：计算从磴移除“个连续接入节点V后减小的 代价人5步骤5：在集合S中找到乩,使紂K合并V后增加的 代价血最小,且化接入节点个数加小于或等于W 3步骤6 ：如果AQ，移动节点集合V到K.步骤7：如果有多种从/?,移除节点的方法，遍历毎种 方法,重复执行步骤46,此算法中，第1步是为了增加非满环数量，便得整个 拓扑中有足够的调整空何,因为节点移动方向都为非满 环，所以这一步很靈要。经过“节点移动搜索算法一次迭代后，将得到一个新 的拓扑，且优F前-拓扑。在新拓扑上再次进行迭代，可能 进一步得到更优的拓扑。3.2.2

14、完整启发式搜索流程步驟1：依次取n=I,-, /：步鼻2：使用节点移动搜索算法迭代。步.：若得到更优拓扑且“节点移动迭代次数小F 迭代次数限制IF.转入步骤2。步骤4：从“1到遍历完一次为一次完整迭代, 次完整迭代后，若整个拓扑暫变动且完整迭代次数小于 迭代次数限制转入步骤1。图3为部分环启发式优化节点调整示意。在*文算法中，取=10.=8通过对犬量实际网例 的测试，在E点移动过程中，迭代次数通常不超过8次, 拓扑即可收敛到一个稳定状态 而在整个拓扑优化中，完 整迭代次数大多在26次，拓扑即町收敛因此笔者取 =10上=8作为迭代停止的临界条件。在迭代过程中，笔者插入了空接入环用以堆加迭代空 间

15、，迭代停止后，痔要移除空按入环，即那些只冇两个汇聚 节点没有接入节点的环。4算法性能分析笔者从观划所得结果和算法效率两方而对灯法进行测 试本剪法运行十OPNET中将算法与整数规划具CPI.EX 規划结果进行了比对。便用AMPL建模语言描述数学模型。所 有程序运行于4GB内存266 GHz的4核CPU上。笔者使用了 3组数据对粥法进行测试评估，组为 15个节点内小规模数据与CPLEX进行比对;一组为实际 网例数厳用以验证算法结杲；最后一组隨机生成大规模数 据用以炯试算法效率。表1为本文算法和CPLEX测试比较,这组数据中,汇 聚节点个数限制为3个，接入节点个数限制为5个，最厉 3行数据汇聚节点个

16、数均为6个，其余场景屮汇聚节点个 数都为3个。表1 CPLEX求解结果与本文算法结果对比节点个数CPLEX代价(km)算法代价(km)代价比CPLEX时间(s)629.67429.674100%21730.87030.870100%37834.58734.587100%0938.32140.87393.8%1401()41.87345.23992.5%210114.83948.839100%3211250.29760.93882.5%6981355.98759.93293.4%1 8701459.89259.892KM)%4 87615609276.38978.8%13 761表I中代价比为C

17、PLEX代价/克法代价，通过这一列 可以看出，当“ W15时,算法规划代价与C PLEX求解结果 很相近，当“.7,8.11.14的这儿个场景卜,算法所求拓扑CPLEX相同：从测试结果屮可以&出，随着“的堆大, CPLEX规划所需时间急剧增长，当“ 15时,求解需要几个 小时。本文漳法在求解这儿个场呆所花时间均小于3 S3表2为实际网例的性能测试数据,这组测试数据中, 汇聚环节点个数限制均为4个，接入环上的接入节点个数 限制为8个，表2中w代表“节点调整最大迭代次数丿代 表总迭代次数.这M个值是笔者对第法中丁值和C值进 行取值的依据:，状态(b)竹点挂入也哎化)2 节 /cBittri该算法在

18、求解中等规模网络时，效率很高。当节点在 300个左右时.卽法求解时间均未超过10恥用4为这屿实 际网例规划代价对比。? 1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 电信科学2012年第8期表2实际网络性能测试场景代l:审点个数（个）M/时 M(im)NVX-ATN9042675VSATN113441 013NIV-ATN18()543 3(M)laS-AIN180534 U18M1N-ATN215954 896NIjC-12270734 691NVX-12275824 81

19、3M1N-12306648 297/見笃$a XX图4实际财络测试结果从规划结果对比中可以看出，本文算法规划较人工規 划结果优20%30%在构造初始拓扑时，便用最远距离分 组法求得汇聚坏不会岀现分，因此所求播扑优于垦 于K-mean聚类分组法。算法最终采用最远距离分组法。为了测试算法效率笔者随机生成了一组大规模网络 数据进行测试,测试结果如表3所示。表3算法效率测试审点个数汇聚节点个救初始州扑时河总时何（个）（个）(s)300280.978&21650()481.64227.2667CX)46&91470.1749006812.876136.4391 1008()31.32929().9851

20、 2(M)884&317428.1971 3009260.937773.157I 100100109.7321 118.7821 500108190.8372 904.672从表3中可以弄出，算法求解时间与节点个数并非线 性关系当节点规模较大时，算法用时成指数级増氏。当规 模达到1 500个节点时，本算法仅需要大约50 min。規模 在1 1D0个节点内时,求解仅需要几分钟。5结束语本文展现了 种快速求解双归属环形网络拓扑的方 法,描述和对比了两种不同方式构造初始拓扑后求解的结 果，将席法结果分别同CPI.EX整数规划结果及人工规划 结杲进行对比验证了算法的准确性)尊法的启发式搜索 仅在満环与

21、非满环Z何进!f,能很快求解大规模两络拓扑 结构，足以満足目前对算法效率的要求，本算法在IP HAN 的拓扌、设计中已取得很好效果。F步工作中，笔者将改进该算法，使其能根据用户 设置it行双归属规划或单双归混合规划:其可在用户自行 设置必经和必不经链路后进行規划，参考文献1 Kang 1) Lee K P&rk S.和 al Deign o( local networks iiMiig USHKs. TrlromnHini ation Systrnis. 2000. 14(1-4): 197-2172 SHI J, Eoncka J. Hicrardiiral sclMwulii rii 1E

22、EE/ACM Transactions on Mrtworking. 1994. 21(4):690 6973 SHI J. Fonsrku J AiiuIvm uikI design of Minivaidr trlc(-oinmiini*atioiis networks. 1EE PrcMvrdings-Coinmiinications. 1997. 144(5): 322-3304 Kl irugar K.K., Kujan K, iVtiigii of 2-lcvel hieran*hi*ulring nctMoricM. PftM-ccilingM of 3rd Intcmalion

23、iil CongrrM on Ultra Modem *1 rIcraninHini atiotis and Control Systems and U orkslx)|s (ICUMT). BixiapcM. 20115 Ihcmaikcn T Stidcn T IlicranJiical ring nc4work trnvriircaii Journal of 0|crational KrNran h. 2(X)3. 151(2):280-2958 Halil L Mcr, Saratli k Algorilluii* for the design of network lo|ologir

24、s with halanrovrllrm Prurc*Mlin& of the 5th Internationa) (xxitrrriUT on Network Optimization. Mamburg Grmuiny. 2011:24-3673?1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 研究与开发10 Pop P Nf integer progranuning fonnulations of the作者简介卢研半卩4川大学计铮机学院硕I：研究牛主要generalize

25、d travelling halonuin problem. American Journal of 研究力何为网络性优化、网络规划 宏 Ml 1： 04 川人学计 Applied Science2007. 4( 11 ):932-937煤机学院教授主耍研究方向为计机网络Algorithm for Dual-Homing Ring Network DesignLu Yanping Lv (uanglu)ng(Schoo! of Co叫)uter. Sichuan University. Chengdu 610065 China)Abstract Ulis paper develops an e

26、fficient algoritlini Io design hierarchical dual-honiing ring network A heuristic algonlhm that adjusts nodes lielween full-rings and non-full rings is presented. Tlie solution can lie obtains! for up Io 1 500 nxles in a small ainount of time liile lhe existing algohlhins usually can only lunulle a

27、lew hundred ixnles First this pajM-r pres*ntes the mathnnalical inodrL and then details the initial topology generation algorithm and the heuristic algorilh in. Finally* the jx?rfonnance of lhe algorithm is verified through compare the to|xjlogy with results obtained from the CPLEX anil inanual 6-12)? 1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 研究与开发? 1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 研究与开发简讯? 1994-2015 China Academic Journal Electronic Publishing House. All rights reserved, 研究与开发交通银行基于Teradata数据仓库