基于啟發(fā)式環(huán)索算法的anycasing路由

基于啟發(fā)式環(huán)索算法的anycasing路由

1總結1.1任播路由技術移動社交網絡（移動adhoc網絡）是一種新型的無線網絡。這些動態(tài)節(jié)點由帶wlan條件的無線傳感器暫時形成一個罕見的自治系統(tǒng)。網絡上的每個節(jié)點都有兩個主機和路由器。與傳統(tǒng)的固定無線網絡（如基站或訪問點）相比，沒有必要在網絡上建立固定的通信裝置。因此，移動網絡具有很高的可靠性和靈活性，可以廣泛應用于海上勘探、緊急調查、臨時會議和其他辦公室。AdHoc網絡的路由協(xié)議可以分為表驅動路由和按需路由兩大類.在表驅動路由協(xié)議(先應路由協(xié)議)中,每個節(jié)點維護到所有已知目的節(jié)點的路由表.節(jié)點之間周期性連接且在網絡拓撲發(fā)生變化時交換路由信息,減少了獲得路由的延遲,使源節(jié)點能夠立即判斷目的節(jié)點的可達性,但是消費了較多的網絡資源,此外它浪費了一些資源來建立和重建那些根本沒有被使用的路由.在按需路由協(xié)議(反應路由協(xié)議)中,節(jié)點不需要花費資源來維護無用的路由,但路由發(fā)現過程費用比較昂貴而且不可預測,路由延遲與先應路由協(xié)議中恒定的查表時間相比,更加多變.目前研究的最為深入的表驅動路由協(xié)議為DSDV,OLSR,按需路由協(xié)議為DSR,AVOD和TORA.任播路由(AnycastingRouting)是一種全新的路由方式.這個詞的最初定義出現在1993年的rfc1546中.它的最初語義為,用一個anycast地址標識一組提供某種服務的主機,發(fā)送到該anycast地址的數據報將被投遞給這組主機中的某一臺,也就是任意一臺.這是一種無狀態(tài)的、盡力而為的網絡層投遞服務.從功能上說,任播路由可以描述如下:在給定的路由域當中,一個任播地址對應為多個接收節(jié)點,任播路由協(xié)議為轉發(fā)帶有任播地址的數據分組到某個接收節(jié)點而建立、維護必要的路由信息.概念上,任播路由為每個接收節(jié)點維護的路由信息定義為“服務域”,為適應接收節(jié)點設置的變化、網絡拓撲和環(huán)境的改變,任播路由需動態(tài)地調整服務域的內容.在移動無線網絡中,用戶和網絡拓撲結構都是完全動態(tài)的,帶寬資源和終端的能源十分有限.任播可以為動態(tài)的管理終端節(jié)點提供一種魯棒性的模式.下面是任播技術在AdHoc網絡中的具體應用:(1)分布式服務定位.在未來的AdHoc網絡中,需要在高度動態(tài)的環(huán)境內提供連續(xù)的分散控制,從而保證全網都得到魯棒性的可升級的服務.然而在沒有優(yōu)先級配置的前提下管理和定位分布式服務是個棘手的問題.在軍事上,要求網絡能夠在動態(tài)的環(huán)境內根據用戶的需求而平穩(wěn)切換和運行,任播路由技術可以通過支持分布式服務和用戶設計來達到此目的.(2)信息定位、檢索和收集.任播路由技術能從以下幾個方面實現此功能.首先,任播路由為信息的定位提供一種簡單的方法,可能分布在網絡層的更高層,通過某種服務或應用層來實現;其次,服務節(jié)點的定位有利于信息的檢索,這樣可以滿足數據序列號碼的檢索需求以及建立穩(wěn)定的連接.一個簡單的應用舉例為移動網絡中節(jié)點對分布式目錄和有關安全的服務要求.最后,任播路由為動態(tài)、分布式網絡數據的收集提供直接的功能支持.2基于主動廣播的anyctoring路由算法文獻中提出了一種基于虛擬節(jié)點的Anycasting擴展方法,方法的基本思想是用一個虛擬節(jié)點(vistualnode)通過虛擬鏈路(vistuallink)連接所有的Anycasting主機,任何一個發(fā)往虛擬節(jié)點的數據報被確保到達一個Anycasting主機(如圖1所示).文獻中給出了簡單擴展DSR、AODV和TORA路由協(xié)議的方法,但是完整的協(xié)議細節(jié)并沒有被闡述,而且文章中并沒有詳細討論如何減少在路由請求過程中帶來的過多的無用的網絡代價.在文獻中,作者通過模擬的方法證明了在AdHoc網絡中采用任播路由方法比采用傳統(tǒng)的單播路由方法具有更高的效率.文章同時指出了如何消除Anycasting路由在路由發(fā)現階段帶來的網絡代價過高的問題是一個需要深入研究的課題.為解決路由發(fā)現階段網絡代價過高的問題,文獻提出了中心節(jié)點路由算法(Node-CentricRouting),方法的基本思想是將Anycasting主機視為AdHoc網絡中的中心節(jié)點,由中心節(jié)點主動廣播自己的存在,網絡中的其他節(jié)點收到中心節(jié)點廣播后在路由表中建立到中心節(jié)點的路由.這樣,當節(jié)點訪問中心節(jié)點時不需要再發(fā)起路由發(fā)現過程,從而減少了網絡代價.但是,進一步的實驗表明,當網絡節(jié)點數較多,網絡拓撲變化較快的時候,中心節(jié)點為了維持網絡中其他節(jié)點到自己的路由,必須較頻繁地發(fā)出更新信息,這樣對AdHoc網絡仍然會產生較高的代價,而且如果網絡中的節(jié)點在一次更新周期內并沒有訪問中心節(jié)點,那么因此產生的網絡代價實際上是“無用”的.因此,基于主動廣播的Anycasting路由算法的廣播周期T和消息廣播范圍D等參數仍需要進一步地優(yōu)化.3啟發(fā)式環(huán)索算法環(huán)索技術(ringsearchingtechnique)是一種簡單實用的節(jié)點搜索技術,源節(jié)點從距離自己最近的區(qū)域開始搜索,逐步擴大自己的搜索范圍,若搜索成功,則立即停止搜索.在Anycasting的路由請求階段,可利用環(huán)索技術控制RREQ的生存跳數,從而控制RREQ的傳播范圍,達到減少網絡代價的目的.在AODV協(xié)議中,已經建議在路由請求階段采用環(huán)索技術,但是搜索的參數需手動配置,不適合AdHoc網絡分布式自組管理的特點.為使環(huán)索具有更大的靈活性和自適應性,從而提高環(huán)索算法的效率,進一步減少搜索時間和產生的網絡代價,本文提出的啟發(fā)式環(huán)索算法在以下兩個方面做了適合Anycasting路由的優(yōu)化.(1)采用主、被動路由相結合的混合方式.Anycasting主機定期廣播自己的存在,不必隨著網絡拓撲變化而發(fā)送更新消息.節(jié)點可從Anycasting主機廣播的消息中獲得搜索所需的先驗知識,動態(tài)地調整搜索的參數.(2)中間節(jié)點不是簡單地將RREQ中的生存跳數減1,而是根據以往積累的“經驗”以一定的概率和步長遞減,使搜索總是向著“最可能”的方向進行.3.1啟發(fā)式環(huán)搜索算法一個AdHoc網絡可被模型化為一個平面無向圖G=(V,E),其中E為圖中所有節(jié)點的集合,V為圖中邊的集合.圖G與實際網絡的對應為:網絡中的一個移動節(jié)點對應E中的一個節(jié)點,若網絡中的兩個節(jié)點可直接通信(即為鄰居),則兩節(jié)點在圖中的對應節(jié)點之間存在一條邊.假設AdHoc網絡中的每個節(jié)點具有相同的傳輸半徑,則G中的所有邊都為單位長度,任意兩節(jié)點間的距離由兩點間的跳數決定.為描述環(huán)搜索技術,先定義網絡直徑的概念.AdHoc網絡的網絡直徑為網絡中任意兩點間的最大跳數.即此外,定義與環(huán)搜索技術相關的參數如下:HOP_START為節(jié)點開始搜索時設置的跳數值;HOP_INCREMENT為搜索失敗時的跳數增量;NODE_TRAVERSAL_TIME為測量得到的節(jié)點間傳輸報文所用的時間;WAIT_RREP_TIME為等待RREP返回的最大超時時間;FAIL_THRESHOLD為搜索步長跳變的失敗閾值.其中滿足關系式WAIT_RREP_TIME=2×NODE_TRAVERSAL_TIME×HOP_START.啟發(fā)式環(huán)搜索算法的搜索過程描述如下:1.當一臺主機加入Anycasting組,它會定期廣播自己的存在,廣播消息中的生存跳數TTL=MaxD/2+1.2.中間節(jié)點收到這個廣播消息后,比較消息中的距離跳數值與路由表中已經存在的距離跳數值.若小,則更新路由表項,同時更新該路由信息的有效期.將廣播消息中的TTL=TTL-1;若TTL>0,則繼續(xù)廣播該消息.3.當一個節(jié)點請求Anycasting服務的時候,先檢查本地路由表中是否有有效的主機路由,若有,則不必發(fā)起路由請求過程;否則,按算法1動態(tài)調整搜索參數.算法1.啟發(fā)式環(huán)搜索的算法路由請求發(fā)起過程.1.IF(路由表中有到該地址過期的主機路由,跳數為H)THEN2.HOP_START=H/2+13.ELSEHOP_START=14.發(fā)出RREQ消息,進行路由請求5.IF(在WAIT_RREP_TIME時間內收到RREP消息)THEN6.更新路由表項H,FAIL_THRESHOLD=[MaxD/H],進行路由保持過程7.ELSE8.失敗計數器Counter=Counter+19.IF(Counter>=2×FAIL_THRESHOLD)THEN10.HOP_START=MaxD/2+111.ELSEIF(FAIL_THRESHOLD≤Counter<2×FAIL_THRESHOLD)THEN12.HOP_INCREMENT=Counter13. ELSEHOP_INCREMENT=114.HOP_START=HOP_START+HOP_INCREMENT15.GOTO4.分析算法1,可以得到搜索半徑R與失敗次數n的如下分段關系式:分段函數曲線如圖2所示.啟發(fā)式環(huán)索算法根據當前的網絡狀況和從上一次搜索中獲得的“先驗”知識,優(yōu)化當前搜索的關鍵參數Base_Start和FAIL_THRESHOLD.Base_Start與上一次成功時的跳數相關,而不必從1開始搜索.同時,FAIL_THRESHOLD與“記憶”中的目的節(jié)點的跳數成反比關系,即節(jié)點可能的存在距離越遠,搜索就越能快速的以較大的步長進行,從而提高環(huán)索算法的效率,進一步減少搜索時間和產生的網絡代價.3.2基于啟發(fā)式算法的rreq動態(tài)搜索算法中間節(jié)點在轉發(fā)Ayncasting路由請求過程中,如果能根據以往積累的“經驗”以一定的概率和步長減少消息中的生存跳數TTL,使搜索總是向著“最可能”的方向進行,會進一步提高搜索的效率.當Anycasting路由請求RREQ到達中間節(jié)點的時候,中間節(jié)點以如下規(guī)則減少RREQ中的生存跳數TTL.TTL=TTL-1-α(3)其中α>0稱為遞減因子.α按照如下算法2動態(tài)調整(其中變量M為節(jié)點根據已有“經驗”預測本地到目的地距離,稱為本地預測距離).算法2.啟發(fā)式環(huán)搜索算法的路由請求傳播過程.1.IF(路由表中有到該地址有效的主機路由)THEN2.先源地址發(fā)送RREP,α=TTL+13.ELSEIF(路由表中有到該地址無效的主機路由,跳數為H)THEN4.M=H/*預測距離M的值等于緩存的跳數H*/5. ELSEM=MaxD/*否則,M的值等于緩存的跳數H*/6.IF(M<TTL)THENα=07.ELSE8.RETURNα為驗證上述啟發(fā)式算法能使中間節(jié)點根據從前的搜索經驗動態(tài)地減少RREQ的生存跳數,我們在MaxD=50,TTL分別等于5,6,7的3種情況下,按上述算法計算1000次α的值后求其平均,得到α與M的關系曲線(如圖3所示).從圖3中可以看出,對于TTL選取任何值,α與M之間都遵循如下規(guī)律:若中間節(jié)點通過以前的轉發(fā)經驗知道自己距離目標節(jié)點較遠(M值較大),中間節(jié)點會有較大的可能以較大的α值減少RREQ的生存跳數;如果節(jié)點附近從來沒有過目標主機,那么節(jié)點的路由表中不會有到目標主機的過期路由表項,M取值為網絡直徑MaxD,從而使RREQ在本方向的無用傳播盡快結束,以降低網絡代價,使搜索總是向著“最可能”的方向進行.同時,α的取值又是概率相關的,這樣就避免了算法對某些特殊網絡情況的搜索失敗.4模擬與評估4.1模型擬合與性能評價我們用模擬軟件ns2設計了模擬實驗.實驗的AdHoc網絡場景包括50個移動節(jié)點,節(jié)點均勻分布在10000×10000m的正方形平面.每個節(jié)點采用IEEE802.11無線網絡接口,最大傳輸范圍為200m.節(jié)點的移動方式遵照RandomWayPoint移動模型.移動速率均勻分布在0～10m/s之間,停留時間均勻分布在0～500ms之間.AdHoc網絡中有一個Anycasting組,組中有5個Anycasting主機成員,網絡中有20個服務請求源節(jié)點.模擬實驗反復運行30次,每次運行1200s.模擬著重分析了三個協(xié)議:標準的DSR協(xié)議、簡單擴展支持Anycasing的DSR協(xié)議(SA-DSR)、采用啟發(fā)式環(huán)索算法的DSR協(xié)議(HA-DSR).采用如下三個指標評價協(xié)議的性能:(1)報文轉發(fā)率(packetdeliveryratio).數據報文成功地由源節(jié)點轉發(fā)到目的節(jié)點的比率.(2)消息平均跳數(meanmessagehopcount).數據報文由源節(jié)點成功地轉發(fā)到目的節(jié)點經過的跳數平均值.(3)路由代價(routingoverhead).網絡中RREQ和消息總數的比值.4.2基于anyctoring的網絡代價圖4、圖5、圖6分別給出了三種協(xié)議的三項指標的性能比較.從圖4中可以看出在一般情況下,三種協(xié)議的包轉發(fā)率都要高于80%.隨著節(jié)點停留時間的增加(即節(jié)點運動速度的降低),三種協(xié)議的包轉發(fā)率均增加.DSR的包轉發(fā)率要低于另外兩種改進的協(xié)議,SA-DSR和HA-DSR在包轉發(fā)率上只有細微的差別.從圖5中可以看出,DSR的消息平均跳數要遠遠大于SA-DSR和HA-DSR.這說明在AdHoc網絡中采用Anycasting路由會極大地提高網絡的整體效率,這個結論與文獻中提到的相符.此外,由于HA-DSR采用的是分布式局部搜索,有時不會比較網絡中的所有Anycasting主機,選擇的Anycasting主機可能不是最近的.