一種漸進(jìn)式的分簇路由協(xié)議

一種漸進(jìn)式的分簇路由協(xié)議

1驅(qū)動的路由協(xié)議移動adhoc網(wǎng)絡(luò)是一個多才多藝、自由組織的網(wǎng)絡(luò)。每個節(jié)點(diǎn)都是主機(jī)和路由器。如果這兩個節(jié)點(diǎn)正在通信，并且另一方未在信號范圍內(nèi)，則必須通過其他節(jié)點(diǎn)進(jìn)行通信。路由選擇的優(yōu)劣在很大程度上影響了網(wǎng)絡(luò)的性能。由于MANET網(wǎng)絡(luò)中的節(jié)點(diǎn)隨時可能移動,并且沒有基站之類的中央控制設(shè)備與之相連,這一方面給用戶帶來了很大的便利,另一方面也為設(shè)計(jì)合適的路由協(xié)議帶來了困難。由于MANET網(wǎng)絡(luò)的特點(diǎn),傳統(tǒng)的路由協(xié)議(如距離向量和鏈路狀態(tài))無法適用,目前已針對MANET網(wǎng)絡(luò)提出了許多路由協(xié)議,這些路由協(xié)議通?？煞殖蓛深?基于路由表驅(qū)動(tabledriven)的路由協(xié)議和按需驅(qū)動(on-demanddriven)的路由協(xié)議。路由表驅(qū)動的路由協(xié)議又稱為先驗(yàn)式(pro-active)路由協(xié)議,如DSDV、TBRPF、OLSR等。這類路由協(xié)議的特點(diǎn)是各節(jié)點(diǎn)需要定期交換路由信息,使節(jié)點(diǎn)維護(hù)的路由表能隨網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化及時更新。這類協(xié)議的路由獲得延遲很小,因?yàn)槁酚杀碇幸呀?jīng)包含了到各目標(biāo)節(jié)點(diǎn)的路由。但形成完整的路由表及路由信息的維護(hù)開銷很大,對規(guī)模較大或數(shù)據(jù)發(fā)送頻率較低的MANET網(wǎng)絡(luò)不太適用。按需驅(qū)動的路由協(xié)議又稱為反應(yīng)式(re-active)路由協(xié)議,如AODV、DSR、CBRP等,這類路由協(xié)議節(jié)點(diǎn)不需要維護(hù)及時準(zhǔn)確的路由信息,僅當(dāng)需要發(fā)送報(bào)文時,源節(jié)點(diǎn)才在網(wǎng)絡(luò)中發(fā)起路由查找過程,因此開銷較小,更適合于拓?fù)鋭討B(tài)變化、資源受限的MANET網(wǎng)絡(luò),已成為MANET路由協(xié)議的主流。付出的代價(jià)是增加了數(shù)據(jù)傳輸?shù)臅r延,因?yàn)橛幸欢温酚砂l(fā)現(xiàn)延遲。AODV的路由發(fā)現(xiàn)過程如下:源節(jié)點(diǎn)首先查看路由表中是否已有到目的節(jié)點(diǎn)的新鮮路由(序列號滿足要求),如有,則可直接使用該路由;如不存在,則通過向鄰居以洪泛方式廣播路由請求報(bào)文RREQ來查找路由。RREQ中除攜帶發(fā)起者節(jié)點(diǎn)的地址和RREQ的序號外,還有發(fā)起者節(jié)點(diǎn)記錄的目的節(jié)點(diǎn)序列號。收到RREQ的中間節(jié)點(diǎn),查看自己的路由表中是否記錄有到該目的節(jié)點(diǎn)的有效的路由,也即路由表中的目的節(jié)點(diǎn)的序列號不小于RREQ中攜帶的序列號;若沒有,中間節(jié)點(diǎn)更新路由表數(shù)據(jù)并向其鄰居轉(zhuǎn)發(fā)RREQ;若有或該中間節(jié)點(diǎn)就是目的節(jié)點(diǎn),將發(fā)送“路由回答”報(bào)文RREP給源節(jié)點(diǎn),RREP中包含新的目的序列號和路由,轉(zhuǎn)發(fā)RREP的節(jié)點(diǎn)更新路由表,設(shè)置路由的下流節(jié)點(diǎn)、目的序列號、有效時間信息,并根據(jù)先前記錄的上流節(jié)點(diǎn)地址將RREP報(bào)文轉(zhuǎn)發(fā)給上流節(jié)點(diǎn),直至源節(jié)點(diǎn)。源節(jié)點(diǎn)收到后,就獲得了到目的節(jié)點(diǎn)的路由。AODV的路由維護(hù)過程如下:AODV通過周期性地廣播“hello”報(bào)文來確認(rèn)鄰居的存在(如鏈路層支持反饋,也可利用鏈路層的反饋機(jī)制替代hello報(bào)文),如節(jié)點(diǎn)多次在規(guī)定的時間間隔內(nèi)不再收到其某一鄰居節(jié)點(diǎn)發(fā)來的“hello”報(bào)文,它就認(rèn)為該鄰居節(jié)點(diǎn)已移動,并將它到該鄰居節(jié)點(diǎn)的鏈路標(biāo)為斷開。如果節(jié)點(diǎn)在使用某個鏈路時發(fā)現(xiàn)該鏈路斷開,它將從路由表中刪除包含該斷開鏈路的路由,并發(fā)送“路由出錯”報(bào)文RERR通知那些受鏈路斷開影響的節(jié)點(diǎn),讓它們將對應(yīng)路由從各自的路由表中刪除,沿途轉(zhuǎn)發(fā)RERR的節(jié)點(diǎn)也刪除自己路由表中的對應(yīng)路由。由于AODV協(xié)議只在需要時才建立路由,不需要為不處于活動狀態(tài)的通信維護(hù)路由,因此減少了路由表維護(hù)的開銷;另外,它通過使用目的序列號有效地防止了循環(huán)的發(fā)生,解決了傳統(tǒng)的基于距離向量算法的無限計(jì)數(shù)問題。AODV還允許中間節(jié)點(diǎn)發(fā)送RREP,使源節(jié)點(diǎn)能快速獲得路由。AODV協(xié)議自1997年首次作為IETF的草案提出后,受到了廣泛的關(guān)注,并于2003年被接納為IETF的實(shí)驗(yàn)標(biāo)準(zhǔn)(RFC3561)。與其他協(xié)議相比,AODV具有較低的內(nèi)存和處理開銷,實(shí)現(xiàn)簡單,即使在節(jié)點(diǎn)移動性強(qiáng)的場合下也能很好地工作,總體上體現(xiàn)了較佳的性能。協(xié)議在各種不同的拓?fù)浜铜h(huán)境下經(jīng)歷了嚴(yán)格的測試,證明了協(xié)議是正確和強(qiáng)壯的。研究人員還不斷提出對AODV的改進(jìn)方案,如擴(kuò)展的環(huán)搜索(expandingringsearch)算法。因?yàn)锳ODV中的RREQ報(bào)文,是采用洪泛方式在全網(wǎng)廣播的,當(dāng)網(wǎng)絡(luò)規(guī)模較大,而源與目的節(jié)點(diǎn)又相距較近時,會造成網(wǎng)絡(luò)資源較大的浪費(fèi),而擴(kuò)展的環(huán)搜索算法能有效降低這種浪費(fèi)。該算法先在一個較小的范圍內(nèi)搜索路由,如未找到,再逐步擴(kuò)大搜索范圍。具體地,在RREQ中增加一個TTL字段,該字段決定了RREQ傳播的范圍,開始時可設(shè)定一個較小的值,中間節(jié)點(diǎn)每轉(zhuǎn)發(fā)一次就將該值減1,減為0后就不再轉(zhuǎn)發(fā)。如源節(jié)點(diǎn)在一段時間內(nèi)未收到RREP,它就使用一個稍大的TTL值重新廣播RREQ(該RREQ與原來的RREQ采用不同的標(biāo)識),開始一個新的路由發(fā)現(xiàn)過程。這個過程反復(fù)進(jìn)行直到源節(jié)點(diǎn)收到RREP或其RREQ的TTL值達(dá)到某個門限,這時又有兩種不同的處理方法:或是認(rèn)為目標(biāo)節(jié)點(diǎn)不可達(dá),放棄搜索;或讓RREQ報(bào)文在全網(wǎng)范圍內(nèi)廣播。AODV路由協(xié)議在通常情況下能工作得很好,但當(dāng)節(jié)點(diǎn)數(shù)較多時(如200節(jié)點(diǎn)以上),協(xié)議的性能就會急劇下降,這是因?yàn)锳ODV的路由發(fā)現(xiàn)本質(zhì)上還是使用洪泛方式的擴(kuò)散法,當(dāng)網(wǎng)絡(luò)規(guī)模較大,節(jié)點(diǎn)數(shù)較多時,RREQ等路由控制報(bào)文激增,導(dǎo)致網(wǎng)絡(luò)超負(fù)荷運(yùn)行和擁塞,大大降低了網(wǎng)絡(luò)的性能。因此,減少網(wǎng)絡(luò)中以RREQ為代表的路由控制報(bào)文的數(shù)量,是提高性能的關(guān)鍵。著眼于這個目標(biāo),我們提出了一種基于AODV的漸進(jìn)式分簇策略,稱為AODV-clustering。2道路策略aodv2.1漸進(jìn)和漸進(jìn)方式AODV-clustering路由協(xié)議的設(shè)計(jì)目標(biāo)是在保留AODV優(yōu)點(diǎn)(如正確性、強(qiáng)壯性、簡單,高效)的前提下提高其可擴(kuò)展性,以支持更大規(guī)模的網(wǎng)絡(luò)。設(shè)計(jì)時采用了以下幾個原則:(1)漸進(jìn)式協(xié)議一開始是按AODV方式工作,以后逐漸演變?yōu)橐环N分簇式路由為主,AODV為輔的工作機(jī)制。之所以采用漸進(jìn)的方式,主要是基于以下的考慮:首先,在MANET網(wǎng)絡(luò)中不存在中央控制節(jié)點(diǎn),很難以統(tǒng)一的方式來開始簇的形成,漸進(jìn)式演變的方式更切合實(shí)際,并消除了簇建立延遲;其次,采用漸進(jìn)方式也是為了便于與AODV兼容;最后,由于網(wǎng)絡(luò)拓?fù)涫请S時變化的,采用漸進(jìn)方式可以減少由此帶來的簇變動的開銷。(2)與AODV兼容由于AODV是一個被廣泛接受的路由協(xié)議,我們設(shè)計(jì)協(xié)議的一個重要原則就是與AODV兼容,即允許網(wǎng)絡(luò)中存在AODV節(jié)點(diǎn)并能正常工作。為此,我們保留了AODV所有的路由控制報(bào)文,并根據(jù)需要增加了一些新的路由控制報(bào)文。另外,讓沒有加入簇的節(jié)點(diǎn)以典型的AODV方式工作。(3)傳統(tǒng)路由發(fā)現(xiàn)和快速路由發(fā)現(xiàn)相結(jié)合在AODV-clustering協(xié)議中,對加入簇的節(jié)點(diǎn),配備了兩種路由發(fā)現(xiàn)機(jī)制:第一種是為簇成員設(shè)計(jì)的快速路由發(fā)現(xiàn)機(jī)制;第二種就是傳統(tǒng)的AODV洪泛式路由發(fā)現(xiàn)機(jī)制。對加入簇的節(jié)點(diǎn)先啟用第一種機(jī)制查找路由,如找不到,再啟用第二種機(jī)制查找。未加入簇的節(jié)點(diǎn)只能用第二種機(jī)制。(4)局部路由修復(fù)由于MANET網(wǎng)絡(luò)中節(jié)點(diǎn)是可以自由移動的,節(jié)點(diǎn)的移動有可能造成路由的斷開和數(shù)據(jù)包的丟失。雖然AODV中也有路由維護(hù)機(jī)制,但僅是發(fā)送RERR報(bào)文給前繼節(jié)點(diǎn),讓前繼節(jié)點(diǎn)刪除路由表中受影響的項(xiàng)。如果這時數(shù)據(jù)報(bào)文已經(jīng)在途中,該報(bào)文就會丟失。為提高數(shù)據(jù)發(fā)送的成功率,AODV-clustering協(xié)議中采用了局部路由修復(fù)技術(shù),讓鏈路斷開處的節(jié)點(diǎn),在發(fā)送RERR的同時,暫時緩存到達(dá)的數(shù)據(jù)報(bào)文,并以本節(jié)點(diǎn)作為發(fā)起者開始路由查找過程,若找到,就沿新路由將數(shù)據(jù)報(bào)文發(fā)送到目的地。2.2分簇協(xié)議的形成和工作機(jī)制從宏觀上看,AODV-clustering是一種被動式的、按需的路由策略。與現(xiàn)有的大多數(shù)主動式的分簇協(xié)議不同,該協(xié)議僅在節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送時開始路由查找,并觸發(fā)相關(guān)節(jié)點(diǎn)形成簇。簇的形成是一個漸進(jìn)的過程。協(xié)議的工作機(jī)制可分為兩部分:一是路由機(jī)制,主要包括路由發(fā)現(xiàn)和路由維護(hù);二是分簇機(jī)制,主要是簇的形成和維護(hù)。2.2.1打造協(xié)作網(wǎng)關(guān)協(xié)議的簇是在路由發(fā)現(xiàn)過程中逐步形成的。整個過程可分為兩個階段:第一階段是AODV方式的路由發(fā)現(xiàn)(見圖1(a));第二階段是以新發(fā)現(xiàn)的路由為中心來形成簇(見圖1(b))。具體過程為:開始時所有節(jié)點(diǎn)均未加入簇,節(jié)點(diǎn)的狀態(tài)為“未分配(un-assigned)”,其路由發(fā)現(xiàn)機(jī)制完全與AODV相同。源節(jié)點(diǎn)以洪泛的方式廣播RREQ,中間節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ,最后目的節(jié)點(diǎn)或具有到目的節(jié)點(diǎn)的新鮮路由的中間節(jié)點(diǎn)在收到RREQ后回送RREP給源節(jié)點(diǎn)。協(xié)議在RREP所經(jīng)過的路徑上,每隔一定距離設(shè)置一個簇首節(jié)點(diǎn)。實(shí)現(xiàn)的方案中具體為RREP沿途每隔兩個節(jié)點(diǎn),如果該節(jié)點(diǎn)的狀態(tài)為“未分配”,就將它設(shè)置為簇首。另外,如果RREP的接收節(jié)點(diǎn)發(fā)現(xiàn)沿途還沒有節(jié)點(diǎn)聲明為簇首(CH,clusterhead),它也會將自己設(shè)置為簇首。節(jié)點(diǎn)一旦成為簇首,它就會向鄰居發(fā)布簇首廣播(CHBM,CHbroadcastmessage),收到廣播的節(jié)點(diǎn),根據(jù)自己的角色,分別有不同的反應(yīng):(1)如果節(jié)點(diǎn)(設(shè)為A)的狀態(tài)為“未分配”,它就向發(fā)布簇首廣播的CH節(jié)點(diǎn)發(fā)送“簇加入請求報(bào)文”(JCRM,joinclusterrequestmessage),CH節(jié)點(diǎn)收到請求后,回送“簇加入應(yīng)答報(bào)文”(JCAM,joinclusterACKmessage)。節(jié)點(diǎn)A在收到應(yīng)答報(bào)文后,就成為簇的普通成員(CM,clustermember)。為降低協(xié)議實(shí)現(xiàn)的難度,AODV-clustering中簇為單層結(jié)構(gòu),簇成員到簇首的跳數(shù)均為1跳。(2)如果收到簇首廣播的節(jié)點(diǎn)(設(shè)為D)已經(jīng)是簇的普通成員了,它判斷簇首廣播的發(fā)送者(設(shè)為F)是否就是自己的簇首,如是,不動作;如不是,向F發(fā)送“簇加入請求報(bào)文”,在收到F的應(yīng)答報(bào)文后,D就變成網(wǎng)關(guān)(gateway)。這時,D將向它能直接到達(dá)的所有簇首節(jié)點(diǎn)發(fā)送網(wǎng)關(guān)消息(GM,gatewaymessage),讓簇首節(jié)點(diǎn)將D的地址放入自己的網(wǎng)關(guān)表(gatewaytable)。在網(wǎng)關(guān)節(jié)點(diǎn)中會保存兩張表,一張為可達(dá)簇首節(jié)點(diǎn)表(reachableCHnodetable),存放網(wǎng)關(guān)能直接到達(dá)的所有簇首節(jié)點(diǎn)的地址,另一張為協(xié)作網(wǎng)關(guān)表(jointgatewaytable),它記錄了與該網(wǎng)關(guān)直接相連的協(xié)作網(wǎng)關(guān)及通過這些協(xié)作網(wǎng)關(guān)能一跳到達(dá)的所有其他簇首節(jié)點(diǎn)。所謂協(xié)作網(wǎng)關(guān)(jointgateway),是網(wǎng)關(guān)節(jié)點(diǎn)直接的鄰居,通過它可一跳到達(dá)其他的簇首節(jié)點(diǎn)。為生成協(xié)作網(wǎng)關(guān)表,網(wǎng)關(guān)節(jié)點(diǎn)(設(shè)為G)需向鄰居廣播協(xié)作網(wǎng)關(guān)請求報(bào)文(JGRM,jointgatewayrequestmessage),收到該消息的鄰居節(jié)點(diǎn)(設(shè)為B),如發(fā)現(xiàn)自己的簇首與消息發(fā)送者的簇首不同,就回送協(xié)作網(wǎng)關(guān)應(yīng)答報(bào)文(JGPM,jointgatewayreplymessage),網(wǎng)關(guān)節(jié)點(diǎn)G會將B的地址加入其協(xié)作網(wǎng)關(guān)表,B成為G的協(xié)作網(wǎng)關(guān)(見圖2)。(3)如收到簇首廣播的是網(wǎng)關(guān)節(jié)點(diǎn),它將檢查簇首廣播的發(fā)送者(設(shè)為節(jié)點(diǎn)F)是否已在自己的可達(dá)簇首節(jié)點(diǎn)表中,如在,不動作;如不在,向F發(fā)送“簇加入請求報(bào)文”,在收到應(yīng)答后將F的地址加入其可達(dá)簇首節(jié)點(diǎn)表,并向F發(fā)送網(wǎng)關(guān)消息告知其本節(jié)點(diǎn)的網(wǎng)關(guān)身份。一旦節(jié)點(diǎn)加入簇,成為簇的成員,其采用的路由發(fā)現(xiàn)機(jī)制也會改變。具體如下:(1)如RREQ的發(fā)起者節(jié)點(diǎn)(下簡稱節(jié)點(diǎn))為簇的普通成員,它先檢查目的節(jié)點(diǎn)是否在一跳可達(dá)的鄰居中,如不在,則將發(fā)送的RREQ置上快速轉(zhuǎn)發(fā)標(biāo)記發(fā)往該節(jié)點(diǎn)的簇首。(2)如發(fā)起者或收到RREQ的節(jié)點(diǎn)為簇首,它將向與其直接相連的所有網(wǎng)關(guān)轉(zhuǎn)發(fā)RREQ。(3)如發(fā)起者或收到RREQ的節(jié)點(diǎn)為網(wǎng)關(guān),它將向與該其直接相連的所有簇首節(jié)點(diǎn)和協(xié)作網(wǎng)關(guān)轉(zhuǎn)發(fā)RREQ。(4)轉(zhuǎn)發(fā)RREQ的節(jié)點(diǎn)將根據(jù)RREQ是否設(shè)置了快速轉(zhuǎn)發(fā)標(biāo)記來決定采用快速路由查找或與AODV相同的普通路由查找?？焖俾酚刹檎沂前丛垂?jié)點(diǎn)-->簇首-->網(wǎng)關(guān)-->(協(xié)作網(wǎng)關(guān))-->簇首-->網(wǎng)關(guān)-->…-->目的節(jié)點(diǎn)的方式實(shí)施的(見圖3)。如在規(guī)定的時間內(nèi)未找到路由,再采用普通的路由查找方式來查找。(5)為避免路由環(huán)路,進(jìn)行快速轉(zhuǎn)發(fā)的RREQ,記錄其已經(jīng)訪問過的簇首節(jié)點(diǎn)集,如果收到RREQ的節(jié)點(diǎn)發(fā)現(xiàn)其簇首也包含在這個集合中,則丟棄該RREQ。經(jīng)過一段時間以后,網(wǎng)絡(luò)中已經(jīng)加入簇的節(jié)點(diǎn)數(shù)會越來越多,采用快速路由查找的比例也越來越高,網(wǎng)絡(luò)中包括RREQ在內(nèi)的路由負(fù)載的數(shù)量會有明顯降低。在AODV-clustering協(xié)議中,簇中各成員的角色在一定條件下可以相互轉(zhuǎn)換(見圖4),如:(1)簇首節(jié)點(diǎn):一旦某節(jié)點(diǎn)成為簇首,它只有在以下情況下改變角色:當(dāng)它發(fā)現(xiàn)自己的簇成員表的成員數(shù)為0時,它將自己的狀態(tài)改為“未分配”。(2)普通成員:簇的普通成員在收到新簇首節(jié)點(diǎn)發(fā)來的簇首廣播后,可加入新簇并成為網(wǎng)關(guān)。另外,簇的普通成員如發(fā)現(xiàn)自己的簇首節(jié)點(diǎn)包含在RERR的不可達(dá)節(jié)點(diǎn)集中,則該節(jié)點(diǎn)將自己的狀態(tài)改為“未分配”。(3)網(wǎng)關(guān)節(jié)點(diǎn):網(wǎng)關(guān)節(jié)點(diǎn)如收到RERR消息并發(fā)現(xiàn)不可達(dá)節(jié)點(diǎn)是自己的簇首節(jié)點(diǎn)或該節(jié)點(diǎn)在自己的可達(dá)簇首節(jié)點(diǎn)表中,就從可達(dá)簇首節(jié)點(diǎn)表中刪除對應(yīng)的項(xiàng),如表中只剩下一個節(jié)點(diǎn)時,網(wǎng)關(guān)就將自己的角色轉(zhuǎn)變?yōu)榇氐钠胀ǔ蓡T。2.2.2打造rreq下的使用平臺AODV-clustering的路由維護(hù)一方面保留了AODV中路由維護(hù)機(jī)制,即通過周期性地廣播“hello”報(bào)文來確認(rèn)鄰居的存在(如鏈路層支持反饋,也可使用鏈路層的反饋機(jī)制),并通過發(fā)送RERR報(bào)文來通知那些受鏈路斷開影響的節(jié)點(diǎn)更新路由表等;另一方面,增加了簇的維護(hù)機(jī)制,具體包括加入簇、退出簇和變更簇等。(1)加入簇狀態(tài)為“未分配”的節(jié)點(diǎn)在收到簇首廣播后向簇首發(fā)送“簇加入請求報(bào)文”,在收到簇首返回的應(yīng)答后即加入簇。為了降低開銷,沒有采用周期性的簇首廣播,而采用如下的方式允許新的節(jié)點(diǎn)加入簇:狀態(tài)為“未分配”的節(jié)點(diǎn)在向鄰居廣播RREQ時,在RREQ中設(shè)置一個特殊的標(biāo)記位P,表示RREQ中捎帶了簇加入請求。當(dāng)類型為簇首的節(jié)點(diǎn)收到跳數(shù)為1且?guī)в羞@個特殊標(biāo)記的RREQ時,就會向該節(jié)點(diǎn)以單播的形式發(fā)送簇首廣播,此節(jié)點(diǎn)隨后可通過發(fā)送“簇加入請求報(bào)文”來加入簇。通過這種方式,可以讓一些有數(shù)據(jù)發(fā)送要求的新近移動到簇首附近的未分配節(jié)點(diǎn)加入到簇中,而沒有數(shù)據(jù)發(fā)送要求的節(jié)點(diǎn),即使移動到簇首附近,也不加入到簇中,以減低簇首的開銷,這也符合協(xié)議按需工作的思想。(2)退出簇簇的普通成員節(jié)點(diǎn)如發(fā)現(xiàn)它的簇首不可達(dá),就將自己的狀態(tài)改為“未分配”,即退出簇。網(wǎng)關(guān)節(jié)點(diǎn)當(dāng)其可達(dá)簇首節(jié)點(diǎn)表中直接可達(dá)的簇首節(jié)點(diǎn)只有一個時,就轉(zhuǎn)變?yōu)榇氐钠胀ü?jié)點(diǎn)。另外,簇首節(jié)點(diǎn)如發(fā)現(xiàn)其成員變?yōu)?,其狀態(tài)轉(zhuǎn)為“未分配”。(3)變更簇在AODV-clustering中,簇的變更并不是立即執(zhí)行的。節(jié)點(diǎn)退出簇后,它的狀態(tài)變?yōu)椤拔捶峙洹?隨著網(wǎng)絡(luò)中數(shù)據(jù)的發(fā)送,若附近有節(jié)點(diǎn)成為簇首,它又可以加入新的簇,在此之前該節(jié)點(diǎn)以AODV方式工作。(4)相關(guān)表格的維護(hù)AODV-clustering協(xié)議中,除路由表外,還有一些其他的表格需要維護(hù)。簇首節(jié)點(diǎn)有存放簇成員地址的簇成員表(clustermemberstable),存放簇中網(wǎng)關(guān)地址的網(wǎng)關(guān)表(gatewaytable);簇的普通成員則只保存簇首地址;網(wǎng)關(guān)節(jié)點(diǎn)則保存可達(dá)簇首節(jié)點(diǎn)表(reachableCHnodetable)和協(xié)作網(wǎng)關(guān)表(jointgatewaytable)。這些表格形成后,如節(jié)點(diǎn)發(fā)現(xiàn)輸出鏈路上的某個鄰居不可達(dá),或收到的RERR消息的不可達(dá)節(jié)點(diǎn)列表中包含某個節(jié)點(diǎn),路由協(xié)議就會在這些表格中查找這個節(jié)點(diǎn),若找到就將它從表中刪除。如需要,還要向相關(guān)的其他節(jié)點(diǎn)轉(zhuǎn)發(fā)RERR消息。另外,假設(shè)當(dāng)前節(jié)點(diǎn)是網(wǎng)關(guān),而不可達(dá)節(jié)點(diǎn)正好是當(dāng)前節(jié)點(diǎn)的簇首,則節(jié)點(diǎn)除了從可達(dá)簇首節(jié)點(diǎn)表中刪除不可達(dá)節(jié)點(diǎn)外,還要從表中找一節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的新簇首。若該表中只剩下一個簇首節(jié)點(diǎn),則當(dāng)前節(jié)點(diǎn)的狀態(tài)應(yīng)改為簇的普通成員,另外還要發(fā)消息給該簇首節(jié)點(diǎn),讓它從網(wǎng)關(guān)表中刪除本節(jié)點(diǎn)對應(yīng)的項(xiàng),因?yàn)楸竟?jié)點(diǎn)已不再是網(wǎng)關(guān)了。3增加了b.協(xié)議的路由控制報(bào)文除與AODV兼容的RREQ、RREP、RERR、Hello、RREP-ACK外,還增加了簇首廣播報(bào)文、簇加入請求報(bào)文、簇加入確認(rèn)報(bào)文、網(wǎng)關(guān)消息報(bào)文、協(xié)作網(wǎng)關(guān)發(fā)現(xiàn)報(bào)文、協(xié)作網(wǎng)關(guān)應(yīng)答報(bào)文等。因篇幅關(guān)系這里省略了詳細(xì)的報(bào)文格式。4被動式分簇算法AODV-clustering協(xié)議試圖通過降低在網(wǎng)絡(luò)上傳播的路由控制報(bào)文的數(shù)量來提高性能。由于AODV協(xié)議本質(zhì)上使用洪泛法作為基本的機(jī)制來廣播控制信息,節(jié)點(diǎn)數(shù)多時網(wǎng)絡(luò)負(fù)擔(dān)很重。但事實(shí)上,一般只需要網(wǎng)絡(luò)中的一小部分節(jié)點(diǎn)轉(zhuǎn)發(fā)信息即可使信息遍布整個網(wǎng)絡(luò)。困難的是如何來選擇這部分承擔(dān)轉(zhuǎn)發(fā)功能的節(jié)點(diǎn)以減少網(wǎng)絡(luò)的開銷。目前主要有兩大類方式:一是以O(shè)LSR協(xié)議中采用的MPR(multipointrelays)為代表的路由聚集技術(shù),另一類就是分簇方案。MPR模式的前提是節(jié)點(diǎn)要獲得充分的網(wǎng)絡(luò)拓?fù)湫畔?然后從其直接相連的鄰居節(jié)點(diǎn)中選擇最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)集,使得該節(jié)點(diǎn)發(fā)送的報(bào)文通過節(jié)點(diǎn)集中的節(jié)點(diǎn)轉(zhuǎn)發(fā)能到達(dá)任意兩跳范圍內(nèi)的其他節(jié)點(diǎn)。但在MANET網(wǎng)絡(luò)中,要收集準(zhǔn)確的拓?fù)湫畔⒑芾щy并有巨大的開銷,一般只在表驅(qū)動路由協(xié)議中使用,其性能也與網(wǎng)絡(luò)拓?fù)涿芮邢嚓P(guān)。分簇式機(jī)制則是根據(jù)簇首的無線廣播范圍將網(wǎng)絡(luò)分成一系列的簇,網(wǎng)絡(luò)拓?fù)鋵Υ氐男阅懿粫袊?yán)重影響。典型的基于分簇的路由算法為CBRP。CBRP是一個主動式的分簇算法,其開始階段的任務(wù)是推舉簇首。通常采取的是最小ID法,即推舉具有最小節(jié)點(diǎn)標(biāo)識的節(jié)點(diǎn)為簇首。另一種策略是選舉具有最大連接數(shù)(度)的節(jié)點(diǎn)為簇首。CBRP同樣需要事先了解周圍的拓?fù)湫畔?如鄰居節(jié)點(diǎn)的情況,并且在一些場合下不能形成合適的簇。如以下兩種情況:一是所有節(jié)點(diǎn)沿一字型排列,其ID依次增大。這種情況下最小ID算法與最大度算法都無法得到可用的簇;二是網(wǎng)絡(luò)中局部節(jié)點(diǎn)的連接數(shù)均相同,這時最大度算法就無法推舉簇首,需要使用第二個推舉指標(biāo)。作為一種按需的、被動方式的路由方案,AODV-clustering與MPR等路由聚集技術(shù)和CBRP等主動式分簇技術(shù)相比,具有下列優(yōu)點(diǎn):(1)不需要事先了解網(wǎng)絡(luò)的拓?fù)湫畔?2)也不需要周期性地交換路由信息(3)消除了CBRP中簇建立所帶來的延時(4)在任何情況下均能工作。當(dāng)沒有合適的簇時就以AODV方式工作,不會產(chǎn)生如CBRP中的極端情況。在文獻(xiàn)中,也提出了一種被動的分簇式算法PC-LID。該算法的特點(diǎn)是節(jié)點(diǎn)在轉(zhuǎn)發(fā)報(bào)文時將自己的IP地址和當(dāng)前的簇狀態(tài)信息包含在報(bào)文的IP選項(xiàng)中,使得接收節(jié)點(diǎn)能了解到鄰居節(jié)點(diǎn)的信息和拓?fù)淝闆r,并據(jù)此來形成簇。該方案采用“先聲明者贏”的規(guī)則來選舉簇首,采用一種復(fù)雜的啟發(fā)式算法來找出最小數(shù)量的網(wǎng)關(guān)。該方案不需要定期的報(bào)文交換,減輕了網(wǎng)絡(luò)負(fù)擔(dān),并通過分簇機(jī)制有效地降低了洪泛的開銷。但該方法也存在以下的不足之處:(1)分簇前節(jié)點(diǎn)仍需了解周圍節(jié)點(diǎn)的信息和拓?fù)淝闆r;(2)鄰近節(jié)點(diǎn)的信息包含在IP報(bào)文選項(xiàng)中,使得報(bào)文長度增加,增大了無效載荷;(3)簇的狀態(tài)過多(7種),且狀態(tài)之間轉(zhuǎn)換頻繁,增加了系統(tǒng)開銷;(4)網(wǎng)關(guān)選擇算法復(fù)雜,周期長;(5)“先聲明者贏”的規(guī)則不一定能形成合理的分簇。相比之下,AODV-clustering既吸取了其被動式分簇機(jī)制的優(yōu)點(diǎn),又對其不足之處進(jìn)行了改進(jìn)。為了對這幾種方案在改進(jìn)洪泛機(jī)制方面的效果有一個定量的分析,我們通過仿真考察了各種方案在相同條件下的TNP(thetotalnumberofpacketssentforonebroadcast)值,即發(fā)送單位數(shù)據(jù)報(bào)文網(wǎng)絡(luò)上傳輸?shù)膱?bào)文總數(shù)(包括中間節(jié)點(diǎn)轉(zhuǎn)發(fā)的報(bào)文和相關(guān)的路由控制報(bào)文)。仿真條件如下:采用單一數(shù)據(jù)源,節(jié)點(diǎn)數(shù)為100,節(jié)點(diǎn)傳輸半徑為250m,仿真區(qū)域?yàn)?000m×1000m,節(jié)點(diǎn)以waypoint方式移動,移動速度在0m/s到16m/s之間,停頓時間為100s,數(shù)據(jù)速率為1packet/s,報(bào)文長度為20byte。得到的仿真結(jié)果如表1,其中的數(shù)據(jù)為多次實(shí)驗(yàn)的平均值,CBRP采用最小ID法來推舉簇首。從仿真結(jié)果也可看出,AODV-clustering和PC-LID在控制洪泛、提高報(bào)文轉(zhuǎn)發(fā)效率方面,要明顯好于MPR和CBRP,但考慮到PC-LID在報(bào)文的IP選項(xiàng)中捎帶鄰居信息,平均報(bào)文長度更長,所以AODV-clustering發(fā)送單位報(bào)文的網(wǎng)絡(luò)總開銷更小一些。5實(shí)驗(yàn)結(jié)果比較我們利用康內(nèi)爾大學(xué)(CornellUniversity)新推出的仿真工具JiST/SWANS,實(shí)現(xiàn)了AODV-Clustering協(xié)議的仿真程序并進(jìn)行了仿真。JiST(Javainsimulationtime)是一個高效的離散事件模擬平臺,采用Java編寫,具有仿真效率高、可擴(kuò)展性好和編程容易的特點(diǎn)。SWANS(scalablewirelessAdhocnetworksimulator)則是一個基于JiST的可擴(kuò)展的無線Adhoc網(wǎng)絡(luò)仿真器,采用層次模型,已實(shí)現(xiàn)了無線網(wǎng)絡(luò)物理層、MAC層、網(wǎng)絡(luò)層、傳輸層、應(yīng)用層的主要內(nèi)容和AODV、DSR、ZRP三種路由協(xié)議。相比傳統(tǒng)的仿真軟件如NS2和GloMoSim,JiST/SWANS可支持更多的網(wǎng)絡(luò)節(jié)點(diǎn),仿真速度也快一些。由于JiST/SWANS推出不久,功能上還不是很完善,我們對它進(jìn)行了改進(jìn)和完善(參見文獻(xiàn)),并編寫了AODV-clustering的仿真程序進(jìn)行了仿真實(shí)驗(yàn)。為了便于比較,在相同的仿真環(huán)境下分別運(yùn)行AODV和AODV-clustering的仿真程序并比較仿真結(jié)果,其中的AODV實(shí)施了擴(kuò)展的環(huán)搜索算法。仿真環(huán)境如下:MAC層協(xié)議采用802.11DCF,節(jié)點(diǎn)數(shù)的取值分別為4,9,16,25,49,100,200和400,為保持節(jié)點(diǎn)密度的相對恒定,節(jié)點(diǎn)的仿真區(qū)域隨節(jié)點(diǎn)數(shù)的增加從800m×800m的范圍逐漸擴(kuò)展到3000m×3000m的范圍,并且初始時以網(wǎng)格布局放置節(jié)點(diǎn),節(jié)點(diǎn)缺省的發(fā)射功率設(shè)置為15dBm。實(shí)驗(yàn)中一半節(jié)點(diǎn)靜止不動,另一半節(jié)點(diǎn)以waypoint方式隨機(jī)移動,waypoint方式中節(jié)點(diǎn)的移動速度在0m/s到20m/s之間,移動到目標(biāo)后停頓時間為30s。假設(shè)要發(fā)送的數(shù)據(jù)報(bào)文有20%為長報(bào)文(長度為1620byte),其余80%為短報(bào)文(長度為20byte)。每個節(jié)點(diǎn)被隨機(jī)地被選取作為源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳送。仿真持續(xù)時間為1500s。實(shí)驗(yàn)中每個樣本數(shù)據(jù)由5次仿真結(jié)果的平均值得到(節(jié)點(diǎn)數(shù)為400時仿真次數(shù)為3)。我們讓網(wǎng)絡(luò)中每個節(jié)點(diǎn)平均每2min發(fā)送一個報(bào)文,考察網(wǎng)絡(luò)規(guī)模對協(xié)議性能的影響。實(shí)驗(yàn)中主要對三種性能指標(biāo)進(jìn)行了評價(jià)。首先是數(shù)據(jù)報(bào)文發(fā)送成功率(packetdeliveryfraction),它是根據(jù)成功到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)報(bào)文數(shù)量與發(fā)送的數(shù)據(jù)報(bào)文總數(shù)之比得到的,可用來評價(jià)協(xié)議發(fā)現(xiàn)路由的能力。其次是路由負(fù)載(routingload),以發(fā)送單位數(shù)量的數(shù)據(jù)報(bào)文需要在網(wǎng)絡(luò)中傳送的路由控制報(bào)文的數(shù)量來衡量,其中中間節(jié)點(diǎn)對路由控制報(bào)文的每一次轉(zhuǎn)發(fā)都算作一次,該指標(biāo)可用來衡量協(xié)議的效率。還有一個指標(biāo)是平均路由發(fā)現(xiàn)延遲(averagerouteacquisitionlatency),是仿真期間所有路由延遲的平均值。路由延遲是指節(jié)點(diǎn)從發(fā)送RREQ查找路由開始一直到收到目的節(jié)點(diǎn)的RREP,路由找到這一段時間延遲。如果節(jié)點(diǎn)一開始就有了到目的節(jié)點(diǎn)的路由,延遲就按0來計(jì)算。從該指標(biāo)可看出路由協(xié)議找到路由的速度。根據(jù)實(shí)驗(yàn)結(jié)果,得到不同節(jié)點(diǎn)數(shù)情況下AODV與AODV-clustering數(shù)據(jù)報(bào)文發(fā)送成功率的比較圖(見圖5)。從仿