移动AdHoc网络拓扑控制研究_英文_

移动AdHoc网络拓扑控制研究_英文_ () Dec. 2003 2003 年 12 月自然科学版四川大学学报 ( ) Journal of Sichuan U niversity Nat ural Science Editio n 第 40 卷第 6 期Vol . 40 No . 6 () 文章编号 :049026756 20030621065206 Research on Topology Control in Mobile Ad Hoc Net works Y U A N D ao2h u a ( )College of Co mp uter Science , Sichuan U niversity , Chengdu 610064 ,China Abstract : Ad hoc wireless net wo r ks have received significant at tentio n in recent years. Co nsiderable research has been do ne o n ro uting in ad hoc net wo r ks , but t he research o n topolo gy co nt rol has received lit tle at tentio n . This paper surveys stat us of current research o n topology co nt rol in ad hoc net wo r ks and so me t ypical topology co nt rol met ho ds. It also p ropo ses a dist ributed topology co nt rol algo rit hm fo r mo bile ad hoc net wo r ks. The algo rit hm maintains t he co nnected topolo gy using minimum power t hro ugh finding t he clo sest no de pairs bet ween different partitio ns of t he net wo r k . It ( ) co mbines wit h so me ro uting p rotocol such as op timized link2state p rotocol , so t here is hardly additio nal co nt rol over head to t he topolo gy co nt rol mechanism. The perfo r mance of multihop mo bile wireless net wo r ks and t he net wo r k lifetime can be substantially increased wit h topology co nt rol . Key words : ad hoc mo bile wireless net wo r k ; topolo gy co nt rol ; net wo r k partitio n ; co nnectivit y maintenance ; power op timisatio n . CL C number :TP393 Document code :A 1 Introduct ion Wireless co mmunicatio ns amo ng mo bile users is beco ming mo re pop ular t han ever befo re . There are t wo distinct app roaches fo r enabling wireless mo bile co mp uters to co mmunicate wit h each ot her . The first is to utilize t he existing cellular net wo r k inf rast ruct ure o riginally developed fo r voice co mmunicatio ns using cellular p ho nes. The ot her app roach is to let users w ho wish to co mmunicate wit h each ot her fo r m an ad hoc net wo r k and collabo rate amo ngst t hemselves to deliver data packet s f ro m a so urce to it s destinatio n po ssibly via o ne o r mo re inter mediate no des. An ad2hoc net wo r k is a collectio n of wireless mo bile no des , w hich fo r m a tempo rary net wo r k wit ho ut 1 relaying o n t he existing net wo r k inf rast ruct ure o r cent ralized administ ratio n. Mo bile no des co mmunicate wit h each ot her using multihop wireless links. Each mo bile no de in t he net wo r k also act s as a ro uter , fo rwarding data packet s fo r ot her no des. Ad hoc wireless net wo r ks have received significant at tentio n in recent years due to t heir potential applicatio ns in co nferences , nat ural disasters , bat tlefields , emergency and relief scenario s. In ad hoc net wo r ks , since mo bile no des move rando mly , disco nnectio ns occur f requently , and t his causes f requent net wo r k topolo gy changes even net wo r k divisio n . Co nsequently , data accessibilit y in ad hoc net wo r ks is lower t han t hat in t he co nventio nal fixed net wo r ks. In figure 1 , due to t he radio link disco nnectio n , t he mo bile user1 cannot access t he dataitem D, and t he 1 mo bile user2 cannot access t he dataitem D . Therefo re maintaining st ro ng co nnectivit y is an impo rtant 2 requirement of ad hoc net wo r k . Additio nally , t he lifetime of a wireless mo bile net wo r k t hat is operating o n bat2 tery power is limited by t he capacit y of it s energy so urce . Minimizing power co nsump tio n in ad hoc net wo r k has been o ne of t he majo r design goals. ( Topology co nt rol in ad hoc net wo r ks is intended to create and maintain desired topology such as co nnected ) net wo r k by adjusting and op timizing t he use of t ransmissio n power of each no de . The imp roper topology can Received date :2002212219 co nsiderably reduce t he capacit y and perfo r mance , increase t he end2to2end packet delay , decrease t he ro bust ness to no de f ailures , and sho rten net wo r k lifetime . So we need to co nt rol t he topolo gy of ad hoc net wo r ks to maintain t he efficient co mmunicatio ns bet ween no des. Topolo gy co nt rol is usually do ne by changing t he t ransmit and receive powers of no des in an ad hoc net wo r k . In t his paper , we p ropo se a dist ributed topology co nt rol algo rit hm fo r mo bile ad hoc net wo r ks. It maintains t he co nnected topology using minimum power t hro ugh ( finding t he clo sest no de pairs bet ween different partitio ns. Co nsequently , an energy efficient link wit h ) minimized power co nsump tio nis set up bet ween t wo different partitio ns. Energy efficient ro utes directly impact () extendt he net wo r k lifetime . Fig. 1 Data inaccessibility due to net wor k divisio n 2 Related works Alt ho ugh t he p ro blem do main is f airly clear , t here has been o nly a limited amo unt of wo r k in t he general 2 area of topology co nt rol and net wo r k design , especially fo r mo bile ad hoc net wo r k . Hudescribes a dist ributed , Delaunay t riangulatio n2based algo rit hm fo r choo sing lo gical links and as a co nsequence carrying o ut topolo gy co nt rol . In choo sing t hese links he follow s a few heuristic guidelines such as not exceeding an upper bo und o n t he degree of each no de and choo sing links t hat create a regular and unifo r m grap h st ruct ure . He does not take 3 advantage of adap tive t ransmissio n power co nt rol . Ramanat han and Ro sales2Haindescribe t wo cent ralized op timum algo rit hms fo r creating co nnected and bi2co nnected static net wo r ks wit h t he o bjective of minimizing t he maximum t ransmissio n power fo r each no de . Additio nally , t hey describe t wo dist ributed heuristic algo rit hms fo r mo bile net wo r ks , t hat adjust no de t ransmit powers in respo nse to topolo gical changes and at temp t to maintain a co nnected topology using minimum power . Their reaso ning and algo rit hms are based o n simple heuristics and 4 co nsequently do not guarantee net wo r k co nnectivity in all cases. Ro doplu and Mengp ropo se an ingenio us dist ributed topolo gy co nt rol algo rit hm t hat guarantees co nnectivit y of t he entire net wo r k . Their algo rit hm relies o n a simple radio p ropagatio n mo del fo r t ransmit power roll2off as 1/ d , n ?2 . U sing t his t hey achieve t he n minimum power topology , w hich co ntains t he minimum2power pat hs f ro m each no de to a designated master2site 5 no de. Wat tenhofer and Li Li etcp ropo se a novel dist ributed co ne2based topolo gy co nt rol algo rit hm , t hat increases net wo r k lifetime by deter mining t he minimal operatio nal power requirement fo r each no de w hile guarant ying t he same maximum co nnected no de set as w hen all no des are t ransmit ting wit h maximum power . ( ) They p rove t hat t he algo rit hm is co rrect result s in a co nnected grap hand t he ro utes t hat can be fo und in t he απαπgrap h are power efficient w hile co ne wit h angle ?2/ 3 and ?/ 2 respectively. The current st udies in topolo gy co nt rol mainly limit to static ad hoc net wo r ks. Few papers address topolo gy co nt rol in mo bile ad hoc net wo r ks , and t here are not goo d solutio ns to t his p ro blem. Paper 3 p resent s t wo dist ributed heuristic algo rit hms fo r mo bile net wo r ks , L IN T and L IL T. L IN T uses locally available neighbo r ( ) info r matio n collected by a ro uting p rotocol , and at temp t s to keep t he degree number of neighbo rsof each no de YUAN Dao2hua : Research o n Topolo gy Co nt rol in Mo bile Ad Hoc Net wo r ks 第 6 期1067 bo unded , co nsequently desired t ransmit power . In o rder to keep desired degree , t he no de needs to increase o r decrease it s operatio nal power . 6 γ( ) Acco rding to t he well2know n generic mo del fo r p ropagatio n, t he p ropagatio n lo ss f unctio n r is as follow s γ( )r < rγ( ) r = r, if t hrt hr γ( ) γ( ) ( ) εr= r+ 10 ??logr/ if r, ? r r t hr 10 t hrt hr γ( ) w here r is t he distance , ris a t hreshold distance below w hich t he p ropagatio n lo ss is a co nstant r. L et t hr t hrdand pdenote , respectively , t he current degree and current t ransmit power , and d and p denote , c c d d respectively , t he desired degree and targeted t ransmit power of a no de . The following equatio n can be used to calculate t he new power perio dically , assuming a unifo r mly rando m dist ributio n of t he no des in t he plane . The εvalue of is usually bet ween 2 and 5 , depending o n t he enviro nment ( )ε p = p- 5 ??log d / d d c d c In L IN T , t he power op timizatio n is do ne in an indirect manner by limiting t he number of neighbo rs , and is at best a poo r app ro ximatio n to an op timal solutio n . A significant sho rtco ming of L IN T is it s incognizance of net wo r k co nnectivit y and t he co nsequent danger of a net wo r k partitio n . L IL T also uses t he f reely available neig2 hbo r info r matio n , but additio nally exploit s t he glo bal topolo gy info r matio n t hat is available wit h so me ro uting 3 p rotocols such as link2state p rotocols. There are t wo main part s to L IL T ———t he neighbo r reductio n p rotocol ( ) ( ) N R Pand t he neighbo r additio n p rotocol NA P. The N R P is essentially t he L IN T mechanism. The NA P is t riggered w henever an event driven o r perio dic link2state up date arrives. It s p urpo se is to override t he high t hreshold bo unds o n t he no de degree and increase t he power if t he topology change indicated by t he ro uting up date result s in undesirable co nnectivity. A no de receiving a ro uting up date first deter mines w hich of t hree states t he up dated topolo gy is in2 disco nnected , co nnected but not bico nnected , o r bico nnected. If it is bico nnected , no actio n is taken . If it is disco nnected , t he no de increases it s t ransmit power to t he maximum po ssible value . If it is co nnected , but not bico nnected , t he no de first finds it s distance f ro m t he clo sest articulatio n point . An articulatio n point is a no de w ho se removal will partitio n t he net wo r k . The no de t hen set s a timer fo r a value t t hat is rando mized aro und an expo nential f unctio n of t he distance f ro m t he articulatio n point . If af ter time t t he net wo r k is still not bico nnected , t he no de increases it s power to t he maximum po ssible . In L IL T , t he N R P reduces t he powers to an app rop riate level in time . 3 Algorithm Descript ion The t ransmit power adjust ment in L IL T described in sectio n 2 is not op timized in t hat it is po ssible t hat t he net wo r k over2react s by having multiple no des maximize t heir power fo r fixing t he co nnectivit y. What is not op timized is embo died o n following aspect s : ?Which no des sho uld increase t heir t ransmit powers to fix t he co nnectivity ? ( ) ?What levels sho uld t hese no des increase t heir powers to Not necessarily maximum? ?It may increase interference and collisio n . Additio nally , above algo rit hms do not guarantee net wo r k co nnectivit y in all cases. In L IL T , w hen a no de maximizes it s t ransmit power , t he ot her side no de may not increase it s power co rrespo ndingly. This result s in t hat fo r med link is unidirectio nal . In t his paper , we want to discuss topolo gy co nt rol fo r mo bile ad hoc net wo r ks. Our algo rit hm is an op timizatio n and imp rovement of algo rit hms p ropo sed in paper 3 , and guarantees net wo r k co nnectivity in all cases. It also exploit s t he glo bal topolo gy info r matio n t hat is available locally at every no de ,p rovided by link2state ( ) ro uting p rotocol such as OL SR. The OL SR is an op timizatio n over t he p ure no r mallink state p rotocol , tailo red 8 fo r mo bile ad hoc net wo r ks. Such glo bal co nnectivit y info r matio n is used to recognize and repair net wo r k partitio ns. So o ur algo rit hm is a dist ributed , glo bal topology info r matio n based , topology co nt rol algo rit hm. It s o bjective is fixing net wo r k co nnectivit y using minimum power w hen t he net wo r k partitio ns in mo bile ad hoc net wo r ks. Our algo rit hm is based o n t he following assump tio ns : ( ) () 1It is po sitio n2based , assuming each no de equipped wit h a glo bal po sitio ning unit GPS; () 2It exploit s perio dical ro uting up dates and maintains t he net wo r k co nnectivity , assuming t hat we select t he perio dical time interval t hat makes o nly o ne no de move during each perio d ; () 3Each no de in t he net wo r k maintains topolo gical info r matio n abo ut t he net wo r k , using t he adjacency list . This algo rit hm is applicable to t he ad hoc net wo r k t hat it s size is not very large , so t hat t he link2state up dates can be efficiently p ropagated wit hin t he related partitio ns , and t he net wo r k mo bility is not high . 3 . 1 General Idea of Our Algorithm Ad hoc net wo r k topology is highly dynamic due to f requent no de migratio n , and t his causes f requent net w2 o r k divisio n . Mo bile no des in t he different partitio ns can not co mmunicate and access data wit h each ot her . Therefo re , maintaining t he co nnectivit y is significant fo r mo bile ad hoc net wo r ks. We expect to recover t he net wo r k co nnectivit y using minimum power t hro ugh finding t he clo sest no de pairs bet ween different partitio ns. Assume t hat net wo r k topolo gy is divided into ( ) following t hree partitio ns co nnected co mpo nent sdue to no de’s movement , as in Figure 2 . Gmove is t he partitio n w here t he moving no de is , deter mined by t he po sitio n info r matio n in t he received link2state up date packet . Fo r fixing t he net wo r k co nnectivity , we need to co nnect to get her t hese co mpo nent s. Our algo rit hm centers o n Fig. 2 Net wor k partitio ns due to node’s movementco mpo nent G, because t ho se no des in Ghave t he move move f ull knowledge abo ut t he glo bal net wo r k topolo gy af ter t he net wo r k partitio ns. ?Each no de in Gcalculates and finds t he clo sest no de pairs bet ween Gand every ot her co mpo nent in move move ( ) o rder to co nnect t hem. In above diagram , t he clo sest no de pairs bet ween Gand Gare A , C, and t he move ot her1 ( ) clo sest no de pairs bet ween Gand Gare B , D . move ot her2 ) ( ?If t he no de belo ngs to so me selected no de pairs , it here , A and B increases it s t ransmit power , acco rding to t he distance of t he no de pairs , so t hat a link can be set up bet ween t he no de pairs. Mo reover , it sends a link2set up message to t he ot her no de of t he no de pairs. ?When t he ot her no de in ot her co mpo nent receives t he link2set up message , it increases it s t ransmit power co rrespo ndingly to set up a symmet ric link bet ween t he no de pairs. Co nsequently , t he t wo co mpo nent s t he no de pairs are in are co nnected. The link2set up message carries up dated glo bal topology info r matio n . 3 . 2 Deta il descript ion of our algorithm In ad hoc net wo r ks , t he no de movement and adjust ment of t ransmit power may cause link up / dow ns. In many ro uting p rotocols , t his causes ro uting up dates. Our algo rit hm uses perio dical link2state ro uting up date p rotocol in o rder to p ropagate changing net wo r k topolo gy info r matio n in time . In o ur app roach , t he link2state YUAN Dao2hua : Research o n Topolo gy Co nt rol in Mo bile Ad Hoc Net wo r ks 第 6 期1069 up date packet exchanged bet ween no des has following fo r mat : ()Sender Positio n Sequence number Adjacent link2state up dates or Neighbor informatio n Sender is t he so urce no de sending o ut t he link2state up date packet . Po sitio n denotes current locatio n of t he ( ) sender. Adjacent link2state up dates are a set of link2state up dates L SU s, w here each L SU co ntains t wo endpoint s of a link and a flag of up / dow n . () Each no de detect s adjacent link co nnectivit y changes i . e . link up / dow nsusing different measures , and perio dically co nst ruct s and dist ributes t he link2state up date packet to ot her no des if it s po sitio n o r adjacent link co nnectivit y changes. () When a no de receives t he ro uting up dates link2state up datesf ro m ot her no des , it up dates current net wo r k topolo gy and deter mine w het her o r not t he up dated topolo gy is co nnected. If it is co nnected , no actio n is taken . If t he up dated topology is not co nnected , t he no de at temp t s to participate in fixing t his disco nnected net wo r k topolo gy. First it identifies vario us co nnected co mpo nent s in t he topology. So me standard grap h2t raversal 7 met ho ds can be used to identify t he net wo r k co nnectivit y and co nnected co mpo nent s. Then t ho se no des , in ( ) t he co mpo nent w here t he moving no de is denoted by G, calculate and find t he clo sest no de pairs bet ween move t heir co mpo nent and ot her co mpo nent s , t hat links are needed bet ween t hese no de pairs in o rder to repair t he ( ) co nnectivit y. The clo sest no de pair x , ybet ween co mpo nent Gand ot her co mpo nent Gis defined as move ot heri ( ) M IN distance l , l | x ? y? G?G x y moveot he ri( )x , y w here l and l are t he locatio ns of no des x and y respectively. If so me no de it self in Gbelo ngs to t he x y move selected no de pairs , it increases it s t ransmit power to t he value at t hat it is able to just reach t he ot her no de , in 6 ot her co mpo nent , of t he no de pairs. Acco rding to t he well2know n radio p ropagatio n mo del , t he power α α required to suppo rt a link bet ween t wo no des separated by distance r is r , w here t ypically takes o n a value bet ween 2 and 4 depending o n t he enviro nment . Fo r set ting up a bidirectio nal o r symmet ric link , af ter a no de in co mpo nent Gincreases it s t ransmit move power , it send a link2set up message to ot her no de of t he no de pairs. The link2set up message carries t he current ( ) po sitio n of moving no de and overall link2state up dates reflecting t he currently entire net wo r k topolo gy, t hat have not been p ropagated to ot her co mpo nent s due to t he net wo r k partitio n . When ot her no de of t he no de pairs ( receives t he link2set up message , it increases it s t ransmit power co rrespo ndingly acco rding to t he distance of ) no de pairsfo r set ting up a link bet ween t he no de pairs and p ropagates t he received overall link2state up dates in it s co mpo nent . Co nsequently , t he net wo r k co nnectivit y is fixed and t he newly glo bal topology info r matio n is floo ded to all no des in t he net wo r k . Perio dically , o ur algo rit hm p ropagates up dates and maintains t he net wo r k co nnectivity. So t he glo bal net w2 o r k topolo gy info r matio n is know n to every no de befo re next up date perio d. Based o n t he know n net wo r k topolo gy and currently received link2state up dates , a no de can co nst ruct new topology and identif y t he co nnectivit y of t he net wo r k . Af ter t he net wo r k partitio ns , t ho se no des in a co nnected co mpo nent have t he same net wo r k topology , and all no des in co mpo nent Gknow t he currently co mplete net wo r k topology , includi ng move t he po sitio ns of all no des in t he net wo r k . Therefo re t hese no des can calculate exactly t he distances of all no de pairs bet ween co mpo nent Gand ot her co mpo nent s. Co nsquently , t hey can figure o ut t he clo sest no de pairs move bet ween different co mpo nent s fo r fixing t he net wo r k co nnectivity. ( ) In o ur algo rit hm , w hen t he degree number of neighbo rsof a no de is greater t han a t hreshold value , t he no de reduces it s operatio nal power . The desired no de degree sho uld not be too large . 4 Concl usion Ad hoc wireless net wo r ks have received significant at tentio n in recent years due to t heir t ypical applicatio ns in military maneuver , emergency and disaster recovery , and so o n . Co nsiderable research has been do ne o n ro uting in ad hoc net wo r ks , but t he research o n topolo gy co nt rol has received lit tle at tentio n . This paper p ropo ses a dist ributed topolo gy co nt rol algo rit hm fo r mo bile ad hoc net wo r ks. It maintains t he co nnected topolo gy using minimum power t hro ugh finding t he clo sest no de pairs bet ween different partitio ns of t he net w2 ( ) o rk . The algo rit hm co mbines wit h so me ro uting p rotocol such as link2state p rotocol, and exploit s t he glo bal topolo gy info r matio n t hat is available wit h t his ro uting p rotocol . So , t here is no additio nal over head to t he topolo gy co nt rol mechanism , excep t locally sent few link2set up messages. Simulatio n analysis demo nst rates t hat t he t hro ughp ut of multihop mo bile wireless net wo r ks and t he net wo r k lifetime can be substantially increased wit h t he topolo gy co nt rol algo rit hm. In f ut ure research , we shall st udy t he op timized topolo gy co nt rol under arbit rary net wo r k mo bilit y. Ref erences : Jo hnso n D B ,Maltz D A. Dynamic source routing in ad2hoc wireless net wor ks , Mobile Co mp uting M . Bosto n U SA : Kluwer 1 Academic Publishers , 1996 . ( ) Hu L . Topology co nt rol for multi hop packet radio net wor ks J . I EEE Trans. o n Co mmunicatio ns , 1993 , 41 10: 1474 - 2 1481 . Ramanat han R , Rosales H R. Topology co nt rol of multi hop wireless net wor ks using t ransmit power adjust ment R . I EEE 3 Co mp uter and Co mmunicatio ns Societies :in Proc. I EEE Infoco m March , 2000 . Rodoplu V , Meng T H. Minimum energy mobile wireless net wor ks J . I EEE J . Selected Areas in Co mmunicatio ns , 1999 , 4 () 17 8. Wat tenhofer R ,Li L . Dist ributed Topology Co nt rol for Power Efficient Operatio n in Multi hop Wireless Ad Hoc Net wor ksR . 5 I EEE Co mp uter and Co mmunicatio ns Societies :in Proc. I EEE Infoco m , 2001 . Rappaport T S. Wireless co mmunicatio ns : p rinciples and p ractice M . En glewood Cliff : Prentice Hall , 1996 . 6 Sedgewick R. Algorit hmsM . Pearso n Educatio n , En gland :Addiso n2Wesley , 1988 . 7 8 J acquet P , Muhlet haler P. Op timized Link State Routing Protocol OL . I E TF : Internet 2Draf t , draf t2ietf2manet2olsr204 . t xt , 2001 . 移动 Ad Hoc 网络拓扑控制研究 袁道华 () 四川大学计算机学院 ,成都 610064 摘要 :概述了 Ad Hoc 网络拓扑控制的研究现状和一些典型的拓扑控制 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ,并提出了一种适用于移动 Ad () Hoc 网络的分布式拓扑控制算法 ,它通过寻找网络的不同划分 partitio ns之间最近的结点对 ,以最小的能量 () 维护连接的拓扑. 该算法与某种路由协议 如优化的链路状态协议相结合 ,从而该拓扑控制机制几乎没有 ( ) 额外的控制开销. 通过对网络拓扑的控制 ,可显著增加多步 multihop移动无线网络的性能和网络寿命. 关键词 :Ad Hoc 移动无线网络 ;拓扑控制 ;网络分割 ;连通性维护 ;能量优化