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

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

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