（通信与信息系统专业论文）数字移动通信网优化调整的算法研究.pdf

敌 穆动通信州优化调钍的玎法研究 摘要 本文针对目前数字移动通信网络规模不断扩大，用户数量飞速发展的 。 现实，为了在“兼顾网络安全与网络效益”的原则下合理优化网络资源， 提高现网运行效率，并使现有g s m 网能够在平稳运行和原有投资得到保证 。 的基础上平滑过渡至第三代移动通信网络，本文率先提出了以本地网为单 位进行网络组织调整的移动通信全网优化调整方案，并将蚂蚁寻垃算法引 入到数字移动通信网络优化调整中来。 r f 最短路由寻址方式( s f p r ) 和最小负荷寻址方式( l l r ) 是较为成熟且 l 应用较广的电信网路由寻址方式，目前传统的电信网络路由寻址算法如： o s p f 算法、s p f 算法、s p f - 1 f 算法、b f 算法等都是基于这两种方式的。 最短路由寻址的原理是对于任何情况下系统产生的呼叫，总是选择通路最 短的路由进行呼叫的接续最小负荷寻址的原理是对于任何情况下系统产 生的呼叫，总是选择链路负荷最低的路由进行呼叫的接续蚂蚁寻址算法 在实现呼叫接续时，将同时考虑路由的长度和链路的负荷，因此蚂蚁寻址 算法是最短路由寻址和最小负荷寻址的综合理论证明，分布式动态路由 寻址( d d r ) 方式可以最佳程度利用网络，所以在数字移动通信网络优化 调整中应尽可能地使网络结构实现或接近d d r 形式d d r 形式的网络能够 广泛适应网络的多样性发展，并满足多种服务质量( o o s ) 需求，诸如话 音、数据、视频信号等等而目前我国的移动通信网皆为等级结构，本文 通过调整路由走向、修改交换机参数等措施降低现有移动通信网络的等级 数 # 劫通信l 叫优化调整的辣法研究 性，从而实现动态无等级路由寻址。网络中交换机的缓存能力和处理器能 力是极为重要的因素，而对于链路而言，其时延传播性、带宽和信号复用 方式是影响网络运行的重要因素在以下的讨论中所涉及的移动通信本地 网，虽然由于不同市地的用户发展速度不同及历史原因，使得本地网在结 构和规模上有所差异，但各本地网的拓扑结构都具有相同的特征 本文作者将在参与移动通信网络扩容建设和第三代移动通信网络规划 探讨的同时，对全省各本地网进行链路选择网元配置、话务流向和信令 分担等的方面的调整和优化，并及时从现网中采集数据，观察网络运行情 况通过对多种算法下的网络传输速度、话务时延、系统中央处理器负荷 等网络运行指标数据进行比较和分析，来验证这种新型移动通信网络优化 调整方案的可行性和有效性通过统计数据可见，d a e m o n 算法最佳，但它 只是网络设备所提供的一种用于测试的理想算法，在实际中是无法实现 的除此之外，蚂蚁寻址算法对现有移动通信本地网的性能改良是最好的， 在某些情况下，它具有极其突出的优越性，在其他情况下它在统计波动内 也是最好的当前移动通信本地网所应用的传统算法在不同情况下会产生 较大的波动性，而蚂蚁寻址算法的性能相对稳定，更加适用于移动通信网 络 从数据统计中可见，在可变比特率的条件下o s p f 算法、s p f 算法和b f 算法的性能较之蚂蚁寻址算法和s p f 一1 f 算法要差，而s p f - 1 f 算法与其他 传统电信网络路由寻址算法一样会在不同的实验环境下产生较大的波动 性，因此蚂蚁寻址算法不论在网络性能方面还是在统计稳定性方面都优于 传统路由寻址算法 3 数+ 一千# 动通信州优化调骼的算法研究 本文将基于移动代理的分布式路由寻址算法一一蚂蚁算法引如到数字 移动通信网络路由寻址中来，通过对采用不同算法的网络传输速度和网络 平均时廷的统计以及对网络资源利用率的予析，可以看到蚂蚁寻址算法具 ， 有明显的优越性。在话务量增长迅速的实验氟境下，可变比特牢和惺趸比 特率时四种分市下网络性能数据说明，在劳字移动通信网络进行优化调整 。 中引入蚂蚁寻址算法可以有效保证网络的良每运行并提高网络资源利用 率，从而在增加网络效能的同时有效保护现啊投资。 对于考虑到网络招塞、话务流量控制等更力：复杂的情况，有待于连一 步的分析和研究。) f 关键词：本地网蚂蚁寻址算法优化调整分布式动态路 由寻址方式 a b s t r a c t w i t ht h ed e v e l o p m e n to f t h em o b i l ec o m m u n i c a t i o nn e t w o r kt 。c h n o l o g y a n dt h ee x p a n d i n gq u a n t i t yo f t h em o b i l es u b s c r i b e r s ，h o wt om e e t t h e “e t w o r k e f f i c l e n c va n di t ss e c u r i t yi s af a t a lp r o b l e mw h i c ht h em o b i l ec o r n f n u n l c a t l o n n e t w o r ko d e r a t o r sm u s tf a c e w i t h t h i st h e s i sb r i n g su pt h e l o c a l n e t w o r k 。 b a s e dm o b i l ec o m m u n i c a l i o nn e t w o r ko p t i m i z a t i o na n da d j u s t m e n t ，a n dt r i e d o u s et h e a n t n e t a l g o r i t h m t o o p t i m i z e a n d a d j u s t t h e d i g i t a l m o b i l 。 c o m m u n i c a t i o nn e t w o r k s t h es h o n e s t f e a s i b l e p a t h r o u t i n g ( s f p r ) a n d l e a s tl o a d e d r o u t i n g ( l l r ) a r et y p i c a l l yr o u t i n g s c h e m e s “c l a s s i c a l ”a l g o r i t h m s ( o s p f , s p f s p f i fa n db f ) a r ea l l i nt h eu p p e rf u n c t i o n s s f p ri s a ns c h e m ew h i c h a l w a v st r i e st of i n dt h es h o r t e s tp a t ha m o n g a l lf e a s i b l ep a t h sb e 咐e e i lt h es o u r c 。 锄dt h ed c s t i n a t i o n i nt h el l r s c h e m e ，t h eo u t g o i n gl i n kw i t h t h el a r g e s tf r 。 c a p a c i t yi sp r e f e r r e d i n a n t n e t ，b o t ht h el e n g t ha n d - f r e ec a p a c i t yo fp a m a r e t a k e ni n t oa c c o u n t ，s ot h ea n t n e ts c h e m e i st h ec o m b i n a t i o no fs f p r a n dl l r s c h e m e f o re m p l o y i n g n e t w o r k sr e s o u r c e s i nb e s t , w em u s td e v e l o p d i s t r i b u t e dd y n a m i cr o u t i n g ( d d r ) t o l e a dt ot h ei m p l e m e n t a t i o no fd y n a m i c n o n h i c r a r c h i c a lr o u t i n g t h e ni tc 姐s u p p o r taw i d ev a r i e t y o ft r a f f i c sw i t h d i 脑r c n tt r a f f i cc h a r a c t e r i s t i c sa n dq u a l i t y 、o fs e r v i c e ( ：q o s ) r e q u i r e m e n t s ，s u c h a sv o i c e d a t a ，v i d e o ，a n d s oo n b u tt h ed i g i t a l m o b i l ec o m m u n i c a t i o n 敦：一移动通俯h 优化渭锭的尊法研究 n 。1 w o r k sa r ea 1 1i nh i e r a r c h i c a ls t r u c t u r ei nc h i n an o w a d a y s i n t h i sp a p e r , t h e a u t h o rt r i e dt ol o w e rt h eh i e r a r c h i c a lo f t h en e t w o r kb yt h em u t i n ga d j u s t m e n t ， s w i t c hc e n t e rp a r a m e t e r sc h a n g i n ga n do t h e rm e a s u r e m e n t st o t u l t lt h en o n h i e r a r c h i c a lm o b i l ec o m m u n i c a t i o nn e t w o r ki n t or e a l i t y s w i t c h e sa r em a i n l y c h a r a c t e r i z e db yt h e i rb u f f e r i n ga n dp r o c e s s i n gc a p a c i t y , w h e r e a s l i n k s b y p r o p a g a t i o nd e l a y , b a n d w i d t h a n ds t r e a m sm u l t i p l e x i n gs c h e m e a l t h o u g h b e c a u s eo ft h ed i f f e r e n to ft h es u b s c r i b e r sn u m b e r a n dt h eh i s t o r i c a le f f e c t ，t h e m o b i l ec o m m u n i c a t i o nl o c a ln e t w o r k sw h i c hw e r ed i s c u s s e di nt h i st h e s i sa r ea l l h a v et h ec h a r a c t e ri nt h e i rt o p o l o g i c a ls t r u c t u r e w i t hh e l po ft h es i g m a l i n gl i n k ss e l e c t i o n ，n e t w o r ke l e m e n t ss e t ，t r a f f i c t r a n s m i s s i o na n dt h es i g n a l i n gs h a r i n g ，w ec a ns e et h a tt h ea n t n e ta l g o r i t h mi s m o r es u p e r i o rt h a no t h e rm o b i l ec o m m u n i c a t i o nr o u t i n ga l g o r i t h m s r e p o r t e d r e s u l t ss h o wc l e a r l yt h a tt h ea n t n e ti st h eb e s tp e r f o r m i n ga l g o r i t h ma m o n g t h e c o n s i d e r e do n e s ( e x c e p tf o rt h ei d e a la l g o r i t h md a e m o n ) i ns o m ec a s e si t s s u p e r i o r i t yi se v i d e n t ，i no t h e r si tp e r f o r m sl i k e t h eb e s to n e sw i t h i ns t a t i s t i c a l f l u c t u a t i o n s i nt h ec b rc a s e ，a n t n e ts h o w sv e r yl o wd e l a y sc o m p a r e d t ot h e o t h e r s ，w h i l ei n t h ev b rc a s e ，t h eo t h e rn e wa l g o r i t h m , s p fi f , p r e s e n t s 。 c o m p a r a b l e o rs l i g h t l yb e t t e rp e r f o r m a n c e o f c o u r s e ，t h ed a e m o na l g o r i t h mh a s a l w a y st h eb e s tp e r f o r m a n c e ，a se x p e c t e d ，a n dc o m p a r i n gi t sp e r f o r m a n c ew i t h 。 t h a to fa n t n e tw ec a ns c et h a ti nt h eh a l fo ft h ec a s e sa n t n e tp e r f o r m a n c ei s a l m o s tt h es a m ew i t h i ns t a t i s t i c a l u n c e r t a i n t i e s ，c o n f i r m i n g i nt h i s w a yt h e e x c e l l e n tb e h a v i o ro fo u ra l g o r i t h mi na c c o r d a n c ew i t ha na b s o l u t es c a l eo f 投+ # 移动迎信叫优化调档的玎法研究 v a l u e s o s p es p fa n db fa l g o r i t h m sp e r f o r m e dp o o r l yw i t hr e s p e c tt oa n t n e t a n ds p f 1 f ( 1 i m i t e dt ot h ev b r c a s e ) a n dt h e i rb e h a v i o rs h o w e ds i g n i f i c a n t f l u c t u a t i o n s ，b o t hi nt e r m so fa b s o l u t ep e r f o r m a n c ea n do f s t a b i l i t y a n t n e tu a s m o r es t a b l ei n p e r f o r m a n c ea n di nb e h a v i o r , t h a ti s ，a l w a y sm o v i n gr a p i d l y t o w a r dag o o ds t a b l ed e l a yv a l u ea f t e ra ni n i t i a lt r a n s i t o r y p h a s e i nt h i sp a p e r , w ei n t r o d u c e da n t n e t ，an e w a l g o r i t h mf o ra d a p t i v er o u t i n g i ti sam o b i l e a g e n t s - b a s e dd i s t r i b u t e da l g o r i t h m i t sb e h a v i o rw i t hr e s p e c tt o t h r o u g h p u t ，m e a l lp a c k e td e l a ya n dr e s o u r c e su s a g e ，h a sb e e nc o m p a r e dt ot h e b e h a v i o ro fo t h e rs h o r t e s tp a t h sr o u t i n ga l g o r i t h m s a sat e s t b e dw e c o n s i d e r e d h e a v yt r a f f i c c o n d i t i o n sf o rs o m er e p r e s e n t a t i v e t e m p o r a l a n ds p a t i a lt r a f f i c d i s t r i b u t i o n sf o rar e a ln e t w o r ki n s t a n c e a n t n e tw a s a l w a y s ，w i t h i nt h e s t a t i s t i c a l f l u c t u a t i o n s ，a m o n gt h eb e s tp e r f o r m i n ga l g o r i t h m s ，b e i n gi ns o m e c a s e st h eb e s t o n e d i f f e r e n t l yf r o m t h eo t h e r a l g o r i t h m s ，a n t n e ts h o w e da l w a y s ar o b u s t b e h a v i o r , b e i n ga b l e t or a p i d l yr e a c hag o o ds t a b l el e v e li np e r f o r m a n c e m o r e o v e r , t h ep r o p o s e da l g o r i t h mh a san e g l i g i b l ei m p a c to nn e t w o r kr e s o u r c e s a n das m a l ls e to f r o b a s t l yt u n a b l ep a r a m e t e r s t h ef e a t u r e so ft h ep r o p o s e d a l g o r i t h mm a k ei t a l l i n t e r e s t i n ga l t e r n a t i v et oc l a s s i c a ls h o r t e s tp a t hr o u t i n g a l g o r i t h m s f o ram o r ec o m p l e t ev a l i d a t i o no ft h ea p p r o a c h ，am o r e c o m p r e h e n s i v e a n a l y s i s ，t a k i n gi n t oa c c o u n tc o n g e s t i o na n df l o wc o n t r o lm e c h a n i s m s 。w i l lb c n e c e s s a r y ， k e y w o r d s ：l o c a l a r e an e t w o r k ， a n t n e t a l g o r i t h m ， n e t w o r ko p t i m i z a t i o n ，d i s t r i b u t e dd y n a m i cr o u t i n g 8 数：# 牡动通信| 卅优化请健的# 法研究 符号说明 ti j ：信息素表中第i 行、第j 列所对应的信息素值 dj i ：从节点j 至节点i 间最短路由的跳跃值 c x j ：节点x 和j 之问链路的带宽 c r x j ：节点x 和j 之间链路带宽的空闲部分 t 1 “节点x 和j 之间链路的带宽 p h e r o m o n e ( i ，r ，s ) ：信息素强度 c l ：网络链路极限容量 s f p r ：最短路由寻址方式 l l r ：最小负荷寻址方式 a n t n e t ：蚂蚁寻址算法 d d r ：分布式动态路由寻址 q o s ：网络服务质量 t m s c ：通信网络话务汇接中心 m s c ：移动通信交换中心 g m s c ：移动通信关口局 s p f ：最短路径优先算法 o s p f ：开放式最短路径优先算法 s p f i f ：第一相邻节点最短路径优先算法 b f ：b e li m a n - f o r d 算法 前言： 路由寻址是任何形式的电信网络的核心，路由寻址方式的科学- 5 否直 。 接影响网络的运营质量，它会同时受到网络结构、设计方案甚至运营思想 的影响和制约，因此路由寻址也是移动通信网络一项非常重要的功能在 。 移动通信中，移动交换子系统和传输链路是整个移动通信网络的骨干部 分，本文所讲的网络就是以g s m 交换机系统为核心、辅以共路信令链路的 移动通信骨干网络和本地网络。现有g s m 网络的特性为我们提供了将等级 网演进为无级网的很好机会本文提到的动态网络是指网络路由寻址采用 依状态实时更新方式的移动通信网络，这种路由寻址方式与目前等级网络 的固定寻址方式是不同的实践证明，在多种形式的电信网络中引入动态 路由寻址的概念皆可提高网络接通率，改善网络质量并有效节省投资 近几年来，为了优化电信网络、有效实现路由寻址，研究人员提出了 多种路由寻址算法并将其用于实践，很大程度上推动了路由寻址技术的发 展和电信网络的演进其中，最短路由寻址方式( s f p r ) 和最小负荷寻址 方式( l l r ) 是较为成熟且应用较广的电信网路由寻址算法，而本文所讨 论的蚂蚁寻址算法( a n t n e t ) 是两者的综合但是迄今为止，尚没有将蚂 蚁寻址算法用于移动通信网络的先例，本文通过对现有g s m 网络进行调整， o 使其近似满足适应分布式动态路由寻址的无等级网络的条件，并尝试在已 调网络中引入蚂蚁寻址算法，以验证将这种新式网络路由寻址算法用于移 动通信网络的可行性和有效性 数# 移动砸情州优化调帮的算法研究 理论证明，分布式动态路由寻址( d d r ) 方式可以最佳程度利用网络， 所以在数字移动通信网络优化调整中应尽可能地使网络结构实现或接近 d d r 形式d d r 形式的网络能够广泛适应网络的多样性发展，并满足多种 服务质量( q o s ) 需求，诸如话音、数据，视频信号等等而目前我国的 移动通信网皆为等级结构，本文通过调整路由走向、修改交换机参数、改 变鉴权范围等措施降低现有移动通信网络的等级性，从而实现动态无等级 网络路由寻址 嚣。，移动越信h 优化调群的尊浩研究 第一章数字移动通信网络现状及优化调整的 可行性分析 第一节网络现状介绍 数字移动通信网络由长途话务网、本地话务网和信令网组成，由于目 前国内的数字移动通信网络皆具有相似的结构，所以下面就以山东省的数 字移动通信网为例对网络现状加以介绍，并就优化调整前现网的优、缺点 加以说明 一网络现状 山东省的话路汇接网的结构如图i - 1 所示，长途汇接网是由t m s c l 局，t m s c 2 局组成；在济南设一对t m s c i 局，负责全省省际话务 的汇接；东部五地市和西部十二地市组成两含省内业务汇接区， 在济南、青岛各设一对t m s c 2 局，分别负责本业务区内的省内长 途话务汇接，济南、青岛的2 对t m s c 2 做网状互连各个本地网 内的端局、关口局均直联t m s c 2 和t m s c i 局 数芦移动通信叫优化调繁的符法研究 圈卜1 ，我省的话路汇接网结构 二现网话路网组眄原则 1 各本地网内的m s c 组成网状网，本地网内话路不经过汇接中心，直 接通过本地网内m s c 之问的直达中继疏通 同一汇接区内，不同本地网间m s c 的话务经过t m s c 2 转接 2 省际话路原则上通过各m s c g m s c 与t m s c l 之间的中继疏通，不经 过t m s c 2 转接 3 原则上在移动方设立独立或综合型g m s c ，疏通与其它网闻的话务， 不兼作g m s c 的端局与其它网不设直达中继 综上所述，我省目前的g s m 话路汇接网是形似三级网，实为二级网的 网络结构，省内话务经过t m s c 2 疏通，不经过t m s c l ，省际话务通过t m s c i 疏通，不经过t m s c 2 敖。f 移动迥信h 优化谔幢的尊法研究 话务网为分级结构济南一对t m s c i ( j n t m s c i i 、j n t m s c l 2 ) 与省外 其他1 2 对t m s c l 一起构成一级话务汇接网，t m s c i 之间以网状网相连济 南、青岛各设一对t m s c 2 ( j n t m s c 2 1 、j n t m s c 2 2 、q d t m s c 2 i q d t m s c 2 2 ) ， 构成省内二级话务汇接网，4 个t m s c 2 以网状网相连各m s c g m s c 与t m s c i 问皆有直达电路，且按负荷分担方式与t m s c l 相连西部1 2 市地( 济南、 淄博、济宁荷泽、临沂、德州、滨州、聊城，东营泰安、莱芜、枣庄) 与济南1 3 f s c 2 之间有直达链路且每个网元皆按负荷分担方式与济南t m s c 2 相连当主、被叫非同一本地网用户且皆属于西部1 2 市地时，话务转接 由济南t m s c 2 实现东部5 市地( 青岛、烟台、威海潍坊、日照) 与青 岛t m s c 2 之间有直达链路且每个网元皆按负荷分担方式与青岛t m s c 2 相 连当主、被叫非同一本地网用户且皆属于东部市地时，话务转接由青岛 t m s c 2 实现济南t m s c i 至t m s c 2 问有备用电路，济南t m s c l 至青岛t m s c 2 问的电路已撤消省际话务一般情况下走m s c 和t i s c l 间的直达电路，如 果直达中继发生故障，则通过济南t m s c 2 和t m s c i 间的中继转接省内话 务通过t m s c 2 汇接对于主、被叫同属同一本地网的情况，话务的接续在 本地网内实现 三现网的优点 从上面的论述可以看到目前的g s m 话务网有以下的优点： 1 结构简单、清晰，本地网的端局，关口局与t m s c i 、t m s c 2 均有直 达电路，组成一个形似三级网，实为二级网的网络结构； 2 这种结构使得省际话路转接的次数达到最少，加快了省际话务的 h l 教f 善动通信m 优化讽鞋的玎洼研究 接续，减少了省际话务的故障点； 3 网络安全性高，这体现在以下几点： ( i ) 省际省内话务分别走不同的路由，t m s c l 发生故障，不会影响省 内话务：t m s c 2 发生故障也不会影响省际的话务； ( 2 ) 省内划分为东西两个汇接业务区，济南的t m s c 2 发生故障不会影 响东部业务区的话务；青岛t m s c 2 发生故障也不会影响西部业务 区的话务； ( 3 ) 以单个m s c 为单位与省际、省内汇接局相连，单个端局发生故障 也不会影响本地网内其它端局的话务。 这样，一旦一个网元发生故障，也会将故障的危害限制在最小的范围 内 四现网的缺点 1 现阶段所有的交换局都以端局为单位直联t m s c i 和t m s c 2 ，这样对 于电路资源是十分浪费的 2 现阶段所有的端局都直联t m s c i 和t m s c 2 ，每当增加一个端局 时，都要建立与t m s c l 和t m s c 2 的长途电路，都要t m s c i 和t m s c 2 局 作相应的数据修改，加大了工程量，不利于网络的扩容和发展； 3 不同本地网的话务都是通过t m s c 2 转接，要通过两段长途电路， 造成了话路的迂回，这对电路资源造成了巨大的浪费而有些本地网 之间的话务量是比较大的，完全可以考虑在话务量较高的本地网之间 设立高效直达路由： 4 而以现在的网络结构，是无法设立本地网之间的直达话务路由的 1 5 数， # 动通信h 优化诵饪的尊法妍宄 例如青岛和烟台之间的话务量忙对达到5 2 爱尔兰，应当建立直达路由 但青岛的6 个m s c 和烟台的3 个m s c 之间的以m s c 为单位的话务量并不 高，话务量最高的y t g 2 和q d g 6 之间也只有9 8 爱尔兰因此，有必要 将本地网的省内话务汇接以后再连接到另一个棼地网； 5 省际省内汇接局直联端局，从骨干网的管理角度看，不利于分级 。 管理，无法隔离故障点 第二节网络优化调整的可行性分析 图i - 2 、目标网结构草图 本地网之问的高效直达路由，有必要经过一个本地长途汇接局进行汇 接如前所述，从话务量来看，虽然本地网之间的话务量较大，但是不同 本地网的单个交换机之间的话务量并不是很大，在不同本地网的单个交换 机之问设直达路由对电路的利用率是比较低的从本地网到省内长途汇接 数宁移动地信叫优化调整的符法研究 局和省际长途汇接局的连接考虑，也只有将本地的省际省内话务通过本地 长途汇接局汇接后再连接到t m s c i 、t m s c 2 才能充分利用长途电路当本 地网扩容时，无需再与省际、省内长途汇接局建立连接 若从网络结构方面考虑，可以做如下分析： ( 1 ) 目前数字移动通信网的所有交换局分为五种类型：端局、关 口局、本地长途汇接局、省内长途汇接局、省际长途汇接局端局连 接b s c 和基站，负责一个较小范围的话务交换；关口局疏通g s m 网与 其它网闻的话务；本地长途汇接局汇接所有本地的省内、省际话务， 与上一级长途汇接局相连，在话务量较高的本地网之问通过本地长途 汇接局设立高效直达路由；省内长途汇接局汇接所有的省内话务；省 际长途汇接局汇接所有的出省话务； ( 2 ) 以上五种类型的划分是逻辑上的，也就是说在物理上它们可 以是合一的当本地网的规模较小时，关口局、本地长途汇接局可以 由一个端局来充当 若从长途电路利用率的角度考虑，可以做如下分析： 各本地长途汇接局与本业务区的t m s c 2 局相连，到达一定的话务 量时与t m s c l 局直连；如果一个本地网的省际话务量非常小，则省际 话务通过t m s c 2 到t m s c i 进行转接 若从安全的角度考虑，可以做如下分析： ( 1 ) 设立本地长途汇接局以后，本地网中增加网元不需要建立到 t m s c i 、t m s c 2 的电路，也不需要从t m s c l 和t m s c 2 局做相应的数据修 改，减少了工程量，降低了人为故障； 1 7 致一社础面信h 优化调鼙的玎浊研究 ( 2 ) 虽然当本地长途汇接局在发生故障时会影响整个本地网的话 务，但可以通过不断提高自身的维护水平，将这种概率降到最低( 固 定电话网一直采用这种模式) 由于各个大话务量的本地网之间均有直达路由，只有溢出话务和较 4 、话务量的本地网之问才经过t m s c 2 转接，因此现有数字移动通信网的 t m s c 2 局可以不再增加除济南、青岛外，其余地市每个本地网只设一 个长途出口，建设了独立g m s c 的，以g m s c 兼作长途局，未建设g m s c 的，指定一个m s c 作为长途局，其余端局的长途业务均通过长途局转接 网络优化调整的具体步骤将在第四章第一节中作详细介绍 技一移动通信h 优化调储的尊法研究 第二章“蚂蚁寻址”算法的提出和传统电信 网络路由寻址算法的介绍 第一节“蚂蚁寻址”算法的基本概念 近几年来，研究人员基于蚂蚁的行为而得到灵感，提出多种有用的算 法并将其成功地加以实践运用，取得了极好的效果“蚂蚁寻址”算法 ( a n t n e t ) 是在蚂蚁能够在巢穴和食物之间找到距离最短通路的启发下提 出，其原理可以用于面向连接的电信网络路由优化 一蚂蚁寻址原理 蚂蚁在爬行过程中会沿途留下信息素( 体外激素) i 例，它们能够精 确地沿着同伴或自己留下的信息素活动，并能够识别信忠素的强度信息 素会不断地蒸发和散失，每只蚂蚁留下的信息素的有效时阈相同且互不相 关如图2 - i 所示，节点a 和节点e 分别代表蚂蚁的巢穴和食物，a 和e 之间有三条可选的路由：a - b - e 、a - c - e 和a - d - e ，现有若干蚂蚁同时高开 巢穴以相同的爬行速度去寻找在e 点的食物若不使用信息素，每只蚂蚁 选取三条可选路由的概率皆为1 3 ；若使用信息素，则蚂蚁选择路由的概 率将与信息素的强度成比例 堑! ! 型业型塑型里堂堕 多个蚂蚁同时离开巢穴a 以相同的速度去寻找在e 点的食物时，选择 最短路由a - c e 的蚂蚁将最先到达目的地e ，此时选择其他路由的蚂蚁仍 在路上如果后到目的地的蚂蚁要返回巢穴，它们将最有可能选择路由e c a ，这是因为，当由经最短路由a - c - e 而最先到达目的地e 的蚂蚁沿原 途返回巢穴时，它将再次在所经路由上留下信息素，从而使得这条最短路 由上的信息素强度增加，当由经其他路由而后到e 点的蚂蚁从e 点返回到 点时，它将比较从e 点至 点所有可选路由上的信息素强度，并选择拥 有最大强度信患素的路由返回巢穴因此，最短路由上的信息素强度会不 断增加，选择最短路由返回巢穴的蚂蚁也会越来越多，而其他可选路由上 的信息素则会因在其有效时间内得不到必要的更新和加强而不断减弱，直 至最终消失至此，蚂蚁群落完成了最佳路由的选择工作，这就是“蚂 蚁寻址”算：圭的原理 二， 蚂蚁寻址算法方案 根据蚂蚁通过比较信息素强度的方式选择最短路由的原理，定义一个 致一移动通信叫优化调整的嚣沽研究 新的寻址概率表一一信息素表- 一例，来代替传统的网络节点路由寻址 表对于一个拥有n 个节点的网络，如果节点x 的相邻节点数为k ，则节 点x 的信息素表的行数为( n 一1 ) 信息素表中的每一行对应节点x 的 可能目的地及其所有相邻且相连接的节点信息素表分别给出了经由不同 相邻节点到达目的地的概率，此概率直接影响蚂蚁在通往目的地的过程中 对下一节点的选择川对于图2 一l 中给出的模型，节点a 的信息素表如表 2 - 1 所示 a 的檑邻节点 耳的地节点 bcd 色o7 30 1 2o 1 5 co 1 00 救0 0 8 d0 0 70 1 5o7 8 eo3 6n 5 l0 1 3 表2 i 、节点a 的信息累表 由图2 - 2 所示，信息素表的更新( 关于信息素表更新的详细内容详见 本章第二节) 和新发起呼叫的路由选择是相互关联的先前的呼叫( 最先 到达目的地的蚂蚁) 对原信息素表进行更新，从而决定新发起的呼叫的路 由而新发起的呼叫将影响链路的负荷，从而影响蚂蚁的路由选择 链路负荷 圈2 - 2 、信息素表更新与呼叫路由选择关系图 墼：垡塾业坐坐型盥型堕 第二节网络系统初始化和信息素表更新 一，系统初始化和信息素表更新计算 当整个网络系统初始化时，信息素即被赋值对于节点x ，用ti j 表 示信息素表宁第i 行、第j 列所对应的信息、素值，眉dj i 表示从节点j 至 节点i 间最短路由的跳跃值 f 。= 1 ( 1 + dj ，) ( 1 ) ( i o n - i 】，i x ，i n x = x 的相邻节点) ) 为了使r 。，- l ，而对fi 。进行归一化如下 tj j tt ij tik( 2 ) k n x 在信息素表初始化完成后，呼叫发起节点( 蚂蚁巢穴) 即产生发往各 个相邻节点的呼叫呼叫发起时，各个呼叫随机其下一个节点之后，呼 叫将依概率选择下一个节点以延续其路由。此概率的计算方法如下： p 。j 一，f ，jn ，j t ik n x k( 3 ) keh 1 其中，t 1 ，j - c 。j c 。j 。c j 表示节点x 和j 之间链路的带宽，c x j 表 示节点x 和j 之间链路带宽的空闲部分 致，转动越信州优化吗整的尊 士研究 我们再以蚂蚁为例进行形象地描述，蚂蚁在所选路由上爬行的过程中 会记录所有经过的节点，当蚂蚁重新访问这些节点或在( n - 1 ) 个时间间 隔内无法达到目的地时，它就会死亡。另一只蚂蚁会出发赶往目的地，如 果它在规定的时间内到达了目的地，则此蚂蚁所经过节点的信息素表都会 被更新，更新的规则如下所述1 若节点x 的目的地是i ，而蚂蚁在下一个时间点上将访问节点j ，则信 息素更新为： t i j 皇( ti j + ti j ) ( 1 + rj j ) ( 4 ) tik tik ( 1 + ti j ) “j ，keh x ( 5 ) tj j 。an2 x j 1( 6 ) 其中，1 是蚂蚁从巢穴至食物之间所访问的所有节点数目，a 是一个 正常数，ti j 同时受路由长度和链路负荷的影响信息素表被更新后， 更多的蚂蚁会选择路径短且负荷低的路由抵达目的地 以上是我们再次利用蚂蚁为例描述信息素表的更新过程，对于一次呼 叫，我们用路由单元( r o u t i n gp a c k e t ) 来证明其寻址过程当路由单 元访问节点x 时，它将依概率选择下一个节点j ，此概率由公式( 3 ) 计 算而来如果节点x 和j 之间链路的带宽足够，则此路由单元将顺利访问 节点j ，否则呼叫被拒绝 敌。一移动通信叫优化弭赣的尊沾蚪究 二、 蚂蚁寻址算法与传统电信网路由寻址方式的关系 最短路由寻址和最小负荷寻址1 是较为成熟且应用较广的电信f 路由 寻址方式最短路由寻址的原理是对于任何情况下系统产生的呼叫，总是 选择通路最短的路由进行呼叫的接续最小负荷寻址的原理是对于任何情 况下系统产生的呼o q ，总是选择链路负荷最低的路由进行呼叫的接续由 公式( 6 ) 可见，蚂蚁寻址算法在实现呼叫接续时，将同时考虑路由的长 度釉链路的负荷，因此蚂蚁寻址算法是最短路由寻址方式和最小负荷寻址 方式的综合实际上，如果选择拥有最大信息素的相邻节点，r ，= a 1 ， 则蚂蚁寻址算法就是最短路由寻址如果ri j - ar 12 ，j ，则蚂蚁寻址算法 与最小负荷寻址极为相似 第三节传统电信网络路由寻址算法的介绍 o s p f ( o p e ns h o r t e s t p a t hf ir s t 开放式最短路径优先) 算法、 s p f ( s h o r t es tp a t hf i r s t 最短路径优先) 算法、b f ( b e l i m a n - f o r d ) 算法、 s p f - 1 f ( 第一相邻节点最短路径优先) 算法等都是传统的电信网络路由寻 址算法“7 1 ”“在本文的实验结果中将拿蚂蚁寻址算法的统计数据与这些 传统算法的数据相对比，这里只是对上述的传统算法作一个简要的介绍 o s p f 算法是一种简单的最短路由统计算法，在网络进行初始化时源节 点将发出位长为5 1 2 字节的数据包来估计最短路由并将存储至网络的路由 表中 墼：至竺垫望堕竺! ! 苎! 兰! 苎! 竺翌兰! ! 丝 s p f 算法是一种将网络运营成本考虑在内的最短路由寻址算法 s p f 一1 f 算法与s p f 算法类似，- 9 之不同的是在s p f 一1 f 算法中源节点 总是将与之临近的节点作为首选目标 b f 算法是电信网最早使用的一种路由寻址算法，采用最短路由寻址方 式 另外，为了验证蚂蚁寻址算法这种新型路由寻址算法的有效性，选取 一种处于理想状态的算法- 9 之比较是可行的d a e m o n 算法m 1 便是这种处 于理想状态的算法d a e m o n 算法是专门用于电信网络工程调测和性能评估 的一种“纯实验室”的算法，它可以通过自适应逻辑结构来保证待测试网 络的性能 蚂蚁寻址算法与上述传统网络路由寻址算法用于数字移动通信网络后 的统计数据将分别以数据表和附图的形式在第四章第二节给出 墼= ! = 壁垫塑垡竺垡竺! 坚塑塑墅i 旦塑 第三章现有移动网络d d r 方式引入蚂蚁寻 址算法的数学分析 前面已经提到过，使用分布式动态路由寻址方式