（通信与信息系统专业论文）基于基础设施的无线局域网路由协议设计.pdf

武汉理1 ：大学硕七学侥论文 摘要 当前移动计算领域的很多工作都集中在路由协议方面，却忽略了这样一个 事实，超过5 0 的无线网络拓扑结构的实现是基十蟮础结构的。i e e e 从2 0 0 2 到 2 0 0 5 年有l l 篇之多的论文是研究移动讨算的路由问题的，1 0 篇是研究移动 a d h o c 网络的就说明这种情况。 按照文献n 在现实的环境下，移动终端都只需要和访问点( a c c e s sd o i n t ， a p ) 通信，不需要和其它的终端通信，所以，为了不增加不必要的网络流量，没 有必要使用a d h o c 的路由协议。本文研究中提出j - 一种新的基于基础结构的路 由坍议( i n f r a s t r u c t u r e b a s e dr o u t i n gp r o t o c 0 1 i b r p ) 。i b r p 是一。种表驱动的 无线路由协议，与d s d v ，a o d v 和d s r 相比，该协议仅仅支持邻近无线节点 间或a p 与移动终端之间的直接通信。文中假定所有的非邻近目的节点不能直接 访问，无论什么时间要发送数据到非邻近节点必须通过a p 而不能通过m n 转 发因此，i b r p 不是一个多跳路由协议。 i b r p 是为基础结构的无线拓扑网络设计的一种协议，对于基础结构的无线 网络的路由是一种好的解决方案，它减少由于使用a d h o c 路由协议而产生的不 必要的网络流量来实现基础结构无线网络。与另一种表驱动的路由协议d s d v ( 为a d h o c 而设计) 相比，研究表明i b r p 路由协议比d s d v 好。结果表明在高 速的移动环境下，i b r p 与d s d v 相比，有低的时延，有更高的吞吐量，并且是 更少丌销。 关键词：无线局域网w l a n ( w i r e l e s sl o c a la r e an e t w o r k ) ，基于基础设施的路由 协议( i b r p ) ，表驱动路由协议，移动节点，有效漫游 武汉理1 ：犬学硕十学位论文 a b s t r a c t m o s to ft h er e s e a r c hw o r ku n d e r t a k e nr e c e n t l yo nt h ea r e ao fm o b i l ec o m p u t i n g ， p a r t i c u l a r l yo nr o u t i n gp r o t o c o l st o p i c ，h a v ei g n o r e dt h et r u t ht h a tas i g n i f i c a n tn u m b e r ， p o s s i b l ym o r et h a n5 0 o ft h er e a l w o r l di m p l e m e n t a t i o ns c e n a r i o so fw i r e l e s s n e t w o r k i n gt o p o l o g i e sa r ei n f r a s t r u c t u r eb a s e d t os u p p o r tt h i sh y p o t h e s i s ，f o ri n s t a n c e ， o u to f e l e v e nr e s e a r c hp a p e r sf o c u s i n gr o u t i n gp r o t o c o l sp u b l i s h e di ni e e et r a n s a c t i o n s o nm o b i l ec o m p u t i n gf r o mt h ey e a r2 0 0 2t o2 0 0 5t e nw e r ef u l lc o n c e n t r a t e di nm o b i l e a d h o cn e t w o r kf m a n e t ) ， b u ta c c o r d i n gt o 【s l ，i nm a n yr e a l w o r l ds c e n a r i o sm o b i l en o d e sc a r to n l yc o n m m n i c a t e w i t ha c c e s sp o i n t ( a p ) ，n o t 、v i 山o t h e rm o b i l en o d e s ，a n dt h u sn on e e do fd e p l o y i n g a d h o cr o u t i n gp r o t o c o l sa st h e yt e n dt oi n c r e a s eu n n e c e s s a r yn e t w o r kt r a f f i c i nt h i s r e s e a m hw o r kan e wi n f r a s t r u c t u r e b a s e dr o u t i n gp r o t o c o l ( i b r p ) h a sb e e np r o p o s e d 1 b r pi sat a b l e d r i v e nw i r e l e s sr o u t i n gp r o t o c o lt h a t ( i nc o n t r a s tt od s d v a o d va n d d s r ) o n l ys u p p o r t sd i r e c tc o m m u n i c a t i o nb e t w e e nn e i g h b o r i n gw i r e l e s sn o d e so r b e t w e e na c c e s sp o i n t ( a p ) a n dm o b i l en o d e s i b r pi sn o tf a v o rm u l t i h o pw i r e l e s s r o u t i n ga si t i sn o ts u p p o r t i n gf o r w a r d i n go fap a c k e tt h r o u 曲m n s ，a s s u m i n ga l l n o n n e i g h b o rd e s t i n a t i o n st ob eu n r e a c h a b l ea n dw h e n e v e rw a n t st os e n dp a c k e t s d e s t i n e dt on o n n e i g h b o rd e s t i n a t i o ni tc h a n n e l e dt h r o u g ha p i b r po b s e r v e dt oo p e r a t ee f f i c i e n t l yi ni n f r a s t r u c t u r ew i r e l e s st o p o l o g y i no t h e rw o r d s ， i b r ps e e m st ob ea p e r f e c ts o l u t i o nf o ri n f r a s t r u c t u r ew i r e l e s sn e t w o r kr o u t i n g m e c h a n i s mb ye l i m i n a t e su n n e c e s s a r yn e t w o r kt r a f f i co v e r h e a d sc a u s e db yu s i n ga dh o c r o u t i n gp r o t o c o l s i ni m p l e m e n t i n gi n f r a s t r u c t u r eb a s e dw i r e l e s sn e t w o r k s ，w i t h c o m p a r i s o nt oa n o t h e rt a b l e d r i v e nr o u t i n gp r o t o c o l ，n a m e l yd s d v ，d e s i g n e df o r a d h o cn e t w o r k t h es t u d yc l e a r l yi n d i c a t e st h a ti b r pr o u t i n gp r o t o c o li ss u p e r i o rt o d s d vi b r pp r o v e st oh a v el o w e rd e l a yt h a nd s d vi nh i g h e rm o b i l i t y i th a so b s e r v e d t op e r f o r l nb e t t e rw i t hh i g ht h r o u g h p u tt h a nd s d va sw e l la so b s e r v e dt oh a v et o w o v e r h e a dc o m p a r e dt ot h a to fd s d v k e y w o r d s ：w l a n ( w i r e l e s sl o c a la r e an e t w o r k ) ，i n f r a s t r u c t u r e b a s e dr o u t i n g p r o t o c o l ( i b p , p ) ，t a b l e d r i v e nr o u t i n gp r o t o c o l ，m o b i l en o d e s ，e f f i c i e n t r o a m i n g 独创性声明 v 8 6 0 3 3 4 本人声明，所星交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所徽的任何 贡献均已在论文中作了明确钧说明并表示了谢意。 慨 ， ccj卧稿i|， 签名：丝= 三丝日期：呈丝型! ! 世 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 导师签名 ( 注：此页内容装订在论文扉页) 期：竺掣够锄 武汉理i 大学硕士学位论文 c h a p t e r 1i n t r o d u c t i o n 1 1f u n d a m e n t a lc o n c e p to fr o u f i n gm e c h a n i s m r o u t i n gp r o t o c o lm e c h a n i s m ，l y i n ga b o v et h em a cp r o t o c o l ，h a sam a i nf u n c t i o no f f i n d i n gar o u t eo f ap a c k e tc o m i n gf r o mh i g h e rl e v e lt h a ti sr e a d yt ob et r a n s m i t t e d ，t h e n f o r w a r d si tt om a cl a y e rf o rt r a n s m i s s i o n t h er o u t e ri sd o i n gt h i sb yl o o k i n ga tt h e p a c k e t sd e s t i n a t i o na d d r e s sa n dt h e nd e t e r m i n e sw h i c ho ft h eo u t p u tp o r tw i l lb et h e b e s tc h o i c et ot h a ta d d r e s s o f c o u r s ear o u t e rm a k e st h i sd e c i s i o nb ye i t h e rc o n s u l t i n ga f o r w a r d i n gt a b l eo rb r o a d c a s t i n ga na d v e r t i s e m e n tt oo t h e rr o u t e r sc o n c e r n i n gt h e w h e r e a b o u t so fp a c k e t sd e s t i n a t i o n i ne i t h e rw a y ，r o u t e rh a sar e s p o n s i b i l i t yo f i n s u r i n gs m o o t ha n de f f i c i e n tr o u t e s e a r c h i n go p e r a t i o n ，w h i c hw i l lg u a r a n t e ef a s t ， a c c u r a t ea n dp r o p e rr o u t i n gr e s u l tw h e n e v e rn e e d e d p r o p e ri ns u c haw a yt h a tt h e s e l e c t e dr o u t i n gp a t hs h o u l db es h o r t e ra m o n ga l lp o s s i b l er o u t e s t h cf u n d a m e n t a lc h a l l e n g eo f r o u t i n gi st of i n dt h es h o r t e s tp a t hb e t w e e nt w on o d e st h a t w a n tt oc o m m u n i c a t e f o rs o m ef e ws e c t i o n so f c h a p t e r1 ，t h er e p o r tw i l lu s ef i g u r e l 一l ， w h i c hg i v e sap i c t u r eo fas i m p l en e t w o r ki n c l u d e sn o d e sa n de d g e s m o r e o v e r , t h e e d g e sh a v eg i v e nw e i g h t ，h e r er e f e r r e da sc o s t ，l o g i c a l l yt oi n d i c a t et h ed e s i r a b i l i t yo f s e n d i n gt r a f f i co v e rt h a tp a r t i c u l a rl i n k n o t et h a t ，t h ee d g e sr e p r e s e n tl i n k sb e t w e e n c o n n e c t e dn o d e sa n dc o u l db ew i r e do rw i r e l e s s f i g u r e1 - 1n e t w o r kr e p r e s e n t e da sg r a p h 武汉理工犬学硕十学何论文 i np r a c t i c a ln e t w o r kr o u t i n e ，r o u t i n gd o e sn o ts i m p l ym e a nt oc a l c u l a t et h es h o r t e s tp a t h s a n d l o a d i n gt h ei n f o r m a t i o ni n t om e m o r yo f e a c hn o d e r o u t i n gi sa c h i e v e db yr u n n i n g a s p e c i a l i z e dr o u t i n gp r o t o c o li ne a c hn o d et h a tp r o v i d e st on o d ead i s t r i b u t e da n d d y n a m i cw a yt os o l v et h ep r o b l e mo ff i n d i n gt h es h o r t e s tp a t he v e ni nt h ep r e s e n c eo f l i n ka n d o rn o d ef a i l u r e sa n dr a p i dc h a n g eo f e d g ec o s t 1 1 1c l a s s i f i c a t i o no fr o u t i n gp r o t o c o l s r o u t i n gp r o t o c o l sc a nb eb r o a d l yc l a s s i f i e da st a b l e d r i v e nr o u t i n gp r o t o c o l sa n ds o u r c e i n i t i a t e do n d e m a n dr o u t i n gp r o t o c o l s t h ef i r s ta p p r o a c hu s e sar o u t i n gt a b l ew h i c hi s m a i n t a i n e dv i ap e r i o d i cu p d a t e sf r o ma 1 1t h eo t h e rn o d e si nt h en e t w o r ki r r e s p e c t i v eo f t h ef a c tt h a tt h en e t w o r km a yn o tb ea c t i v ei nt e r m so fd a t at r a m c t h eo n d e m a n d a p p r o a c h ，o nt h eo t h e rh a n d ，s e n d so u tr e q u e s t sf o rr o u t e st ot h ed e s t i n a t i o no n l yi ft h e s o u r c en o d eh a sd a t a - p a c k e t sw h i c ha r et ob es e n tt ot h ed e s t i n a t i o n i nt h en e x tt w o s u b s e c t i o n st h et h e s i sw i l lt r yt oe x p l o r e rm o r ed e t a i l so ft h e s et w oc l a s s e so fr o u t i n g p r o t o c o l st om a i n t a i naf l o wt o w a r d st h e s i sf o c a lp o i n t 1 t a b l e - d r i v e nr o u t i n gp r o t o c o l s n l et a b l e d r i v e nr o u t i n gp r o t o c o l sd e t e r m i n et h ed i r e c t i o n ( v e c t o r ) a n dd i s t a n c eu s e dt o s e n dd a t ao v e ran e t w o r k t h e s et y p e so f p r o t o c o l ss h a r er o u t i n gt a b l e sw i t i ln e i g h b o r i n g r o u t e r st or e f l e c tt h et o p o l o g ya n ds t a t u so ft h en e t w o r k t l l i sm e t h o ds a v e ss y s t e m r e s o l t c so nt h er o u t e rb e c a u s ei to n l yb r o a d c a s t sap o r t i o no f t h er o u t i n gt a b l el e a v i n g a n o t h e rp o r t i o no fr o u t i n gi n f o r m a t i o nt oo t h e rr o u l e r sap a c k e tw i l lp a s st h r o u g h t h e m e c h a n i s mh e r ei sa n a l o g o u st oad r i v e ru s i n gah i g h w a yi n t e r s e c t i o ns i g n sp o i n tt o w a r d ad e s t i n a t i o na n ds h o wt h ed i s t a n c et ot h ed e s t i n a t i o n a st h ed r i v e rm o v e sm r t h e r ， a n o t h e rs i g ns h o w st h ed e s t i n a t i o n ，b u tn o wt h ed i s t a n c et ot h ed e s t i n a t i o ni ss h o r t e r i f t h ed i s t a n c ec o n t i n u e st og e ts h o r t e r t h ed r i v e rw b ec o n f i d e n to ft a k i n gt h er i g h t ”r o u t e o rp m ht ot h ed e s t i n a t i o n a c t u a l l y ，am a j o rr e s p o n s i b i l i t yo f ar o u t i n gp r o t o c o lo f t a b l e - d r i v e nc l a s si st h ep r o c e s s b y w h i c hr o u t i n g - t a b l e sa r eb u i l t e a c hr o u t e ri sr e s p o n s i b l et oc o n s t r u c ta o n e d i m e n s i o n a la r r a yf av e c t o r ) c o n t a i n i n gt h ed i s t a n c e ( i e c o s ti no t l l s c e n a r i o ) t oa l l o t h e rt o u t e r sa n dd i s t r i b u t e st h a tv e c t o rt oi t si m m e d i a t en e i g h b o r s t h ei n i t i a l a s s u m p t i o nf o rb u i l d i n gr o u t i n g - t a b l ei st h a te a c hr o u t e rk n o w s t h ec o s to ft h el i n kt o e a c ho fi t sd i r e c t l yc o n n e c t e dn e i g h b o r s e a c hr o u t e ra u t o m a t i c a l l ys e n d sa nu p d a t e 2 武汉理工大学硬学位论文 m e s s a g e ( p e r i o d i cu p d a t e ) e v e r ys oo f t e n ，e v e ni fn o t h i n gh a sc h a n g e d ，f o rt w o i m p o r t a n tp u r p o s e s ： t 0l e to t h e rr o u t e r sk n o w st h a tt h i sr o u t e ri ss t i l tr u n n i n g - t om a k es u r et h a tt h e yk e e pg e t t i n gi n f o r m a t i o nt h a tt h e ym a yn e e di ft h e i rc u r r e n t r o u t e sb e c o m et m v i a b l e a l s ot ok e e pat a b l eu p t o d a t e ，r o u t e r se x c h a n g er o u t i n gu p d a t e sk n o w na st r i g g e r e d u p d a t ew h e n e v e rar o u t e rr e c e i v e sa nu p d a t ef r o mo n eo fi t sn e i g h b o r st h a tc a u s e si tt o c h a n g e o no fi t sr o u t e si ni t s r o u t i n g t a b l e ，t h a tm e a n s 。w h e n e v e ra r o u t e r s r o u t i n g t a b l ec h a n g e ，i ts e n d sa i lu p d a t et oi t sn e i g h b o r s ，w h i c hm a yl e a dt oac h a n g e i nt h e i rt a b l e s ，c a u s i n gt h e mt os e n da nu p d a t et on e i g h b o r st o o f o rt h ep u r p o s eo fl e a n i n gt ol e a d e ro ft h i st h e s i sl e t st r yt oc o n s t r u c tar o u t i n g - t a b l e f r o m a ne x a l d p l e o f as i m p l er o u t e r c o n n e c t i o na s d e p i c t e d i n f i g u r e1 - 1a b o v e t a b l e1 - 1 b e l o wr e p r e s e n t se a c hr o u t e r si n i t i a lk n o w l e d g ea b o u tt h ed i s t a n c et oa l to t h e rr o b t e r s ； t a b l e1 - 1 ：i n i t i a ld i s t a n c ek n o w l e d g eb ye a c hm u t e r i n f o r m a t i o ns t o r e d d i s t a n c et oe a c hr o u t e r a tr o u t e r abcdef a03 l3 b3 o24 c1202 d4o l e 2loi f3 jo e a c hr o wi nt a b l e1 - 1l i s t sc o s tt om o v ef r o mo n er o u t e rt oa l lo t h e rt o u t e r s n o t et h a t f i l l e dt oa l lt h o s ef i e l d sar o u t e rd o e sn o th a v ei n i t i a lk n o w l e d g eo ft h e i r w h e r e a b o u t s t h r o u g hp e r i o d i ca n dt r i g g e r su p d a t e si to n l yt a k e saf e we x c h a n g e so fi n f o r m a t i o n b e t w e e nn e i g h b o r sb e f o r ee a c hr o u t e rh a sac o m p l e t er o u t i n g t a b l e f o re x a m p l e ，r o u t e r 3 武汉理工大学硕士学位论文 c 、v i l lt e l lr o u t e r a t h a ti tc a nr e a c hr o u t e r e a tac o s to f2 ：a k n o w i n gt h a ti tc a n r e a c hr o u t e r c a tac o s to f1 s oi ta d d st h e s ec o s t st og e t3a sac o s to fr e a c h i n g e t h r o u g h c l i k e w i s e ，r o u t e r f w i l lt e l lr o u t e r a t h a ti tc a nr e a c hr o u t e r e a tf lc o s t o f1 ；a k n o 谢n gt h a ti tc a r lr e a e hr o u t e r f a tac o s to f3w i l la d dt h e s ec o s t st og e t4a s ac o s to fr e a c h i n g e t h r o u g h f b u ts i n c e 血i si sw o r s et h a l lt h ep r e v i o u sc o s to f r e a c h i n g e t h r o u 曲c ，t h i sn e wi n f o r m a t i o nw i l lb ei g n o r e d 。w i t hs a n l et r e n d st o o t h e rr o u t i n g , a w i l lb ea b l et ou p d a t ei t sr o u t i n g t a b l ew i mc o s ta n dn e x th o p sf o ra l l r o u t e r si nt h en e t w o r ka ss h o w nb yt a b l e1 2b e l o w ： t a b l e1 - 2 ：f i n a lr o u t i n g t a b l ea tr o u t e r a d e s t i n a t i o nc o s t n e x t h o p b3b clc d 4c e3c f 3f t h ep r o b l e mw i t ht h i st y p eo f r o u t i n gp r o t o c o l si sar i s ko f p a c k e tt r a n s m i t t e db e i n gl o s t o rd e l a y e do n c ean e t w o r kp o r t i o ni ni t sp a t hb e c o m ei n a c t i v ei 1 1t e r m so f d a t at r a f f i c t o d e a lw i t hk i n do f p r o b | e mar o u t e rc o n t i n u a l l yt e s t st h et i 呔t oa n o t h e rr o u t e rb ys e n d i n g ac o n t r o lp a c k e ta n ds e e i n gi fi tr e c e i v e sa na c k n o w l e d g e m e n t a l s oar o u t e rd e t e r m i n e s m a tt h el i n ki sd o w ni fi td o e sn o tr e c e i v et h ee x p e c t e dp e r i o d i cu p d a t e sf o rt h ei a s tf e w u p d a t ec y c l e s n o r m a l l yar o u t e rt h a tn o t i c ef i r s ts e n dn e w l i s to f c o s t st ot h e i rn e i 【曲b o r s ， a n du s u a l l yt h es y s t e ms e t t l ed o w nf a i r l yq u i c k l yt oan e ws t a t e a n o t h e rp r o b l e mt h a ti sm o s td e s t a b i l i z i n gt ot a b l e d r i v e nr o u t i n gp r o t o c o li sk n o w na s “c o u n t 的i n f i n i t y ”p r o b l e m s u p p o s et h a tl i n k sb e t w e e na b ，c e ，a n d d eg od o w n 。i n t h en e x tr o u n do f u p d a t er o u t e rdw i l lf i n a l l yc o n c l u d et h a ti tc a r lr e a c he i n5h o p s ；a n d s oo ni f t h en e t w o r ki sl a r g e r o u t i n g t a b l es t a b i l i t yc o u l db ew o r s ei f t h en e t w o r ki sv e r y l a r g ea n ds o m el i n k sg od o w n n l i sp r o b l e mi s o n eo ft h em a i nw e a k n e s s e so f t a b l e d r i v e nr o u t i n gp r o t o c 0 1 t h ep r o b l e mi sp a r t i a l l ys o l v e db yd e c i d i n gt h em a x i m u m n u m b e ro f h o p st og e ta c r o s sac e r t a i nn e t w o r kb e f o r ec o u n t i n gt oi n f i n i t y f o ri n s t a n c e ， i nd e s i g n i n gr o u t i n gp r o t o c o la l g o r i t b a no n ec o u l dd e c i d et h a tt h em a x i m u mn u m b e ro f 4 武汉理工大学硕士学位论文 h o p sn o tt ob em o r et h a n 12 8 ，a n ds ow ec o u l dp i c k12 8a st h ev a l u et h a tr e p r e s e n t i n f i n i t y 2 o n - d e m a n dr o u t i n gp r o t o e o i s c o n t r a r yt ot a b l e d r i v e nr o u t i n gp r o t o c o l s ，o n d e m a n dr o u t i n gp r o t o c o l sa r eb e t t e rf o r l a r g en e t w o r k s t h e ya r e s m a r t e r ”t h a nt a b l e - d r i v e np r o t o c o l s 嬲t h e ym a i n t a i nn o to n l y c o m p l e xd a t a b a s eo ft h en e t w o r kt o p o l o g yb u ta l s os t a t u so fn e t w o r kl i n k ss h o w i n g w h e t h e rl i n k si nd a t a b a s ea r ea c t i v eo rn o t t h i si sa c c o m p l i s h e du s i n g ”l i n ks t a t e a d v e r t i s e m e n t s ”( l s a ) t h a tu s e dt o ”m a p ”o u tt h en e t w o r k t h er o u t e ru s e st h i sm a pt o d e t e r m i n et h es h o r t e s tp a t hf o rd a t ad e s t i n a t i o n s t h i sm e c h a n i s mi s a n a l o g o u st oa d r i v e ru s i n ga h i g h w a ya n dw h e n e v e rr e a c h e d a l li n t e r s e c t i o n 、撕t hn op r i o ri n f o r m a t i o n o f w h e r et og o ，t h ed r i v e rh a st ol o o kf o ri n f o r m a t i o no nw h e r et og oa n dt h es t a t u so f t h e r o a db e f o r ep r o c e e dw i t l lt h ej o u r n e y n o w ，l e ts e eh o wl s am e s s a g em a po u tt h en e t w o r k s p e c i f i c a l l y ，ar o u t e rr u n n i n g o n - d e m a n dr o u t i n gp r o t o c o lm a y g e n e r a t el i n k - s t a t ep a c k e t st h a ta d v e r t i s eo n eo rm o r e o ft h en e t w o r kt h a ta r cd i r e c t l yc o n n e c t e dt ot l l a tr o u t e r i na d d i t i o n ar o u t e rt h a ti s c o n n e c t e dt oa n o t h e rr o u t e rb ys o m el i n km u s ta d v e r t i s et h ec o s to fr e a c h i n gt h a tr o u t e r o v e rt h el i n k ，t h e s et w ot y p e so f a d v e r t i s e m e n t sa r en e c e s s a r yt oe n