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

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

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