移動自組網(wǎng)絡(luò)中的層次結(jié)構(gòu)

移動自組網(wǎng)絡(luò)中的層次結(jié)構(gòu)

1建立新型網(wǎng)絡(luò)模型移動集群網(wǎng)絡(luò)（移動應(yīng)用商店網(wǎng)絡(luò)，簡稱manet）是一種不依賴固定基礎(chǔ)設(shè)施的新型無線網(wǎng)絡(luò)。與需要中心控制設(shè)備(如基站或訪問服務(wù)點)的蜂窩移動通信網(wǎng)絡(luò)和無線局域網(wǎng)相比,移動自組網(wǎng)絡(luò)具有自組性、多跳性、無基礎(chǔ)設(shè)施要求及易鋪設(shè)等特點,可廣泛用于軍事戰(zhàn)場信息系統(tǒng)建設(shè)、民用緊急救助以及其他需要臨時建立網(wǎng)絡(luò)的場合,如野外活動、體育競賽、會議展覽等。移動自組網(wǎng)絡(luò)最初的結(jié)構(gòu)是平面式的,即所有節(jié)點都是對等的,都肩負著終端與路由器兩項功能,只有性能上的差異,沒有功能上的不同。這種平面式結(jié)構(gòu)的最大優(yōu)點之一是,源節(jié)點與目的節(jié)點之間存在多條路徑,因而可以通過多條傳送業(yè)務(wù)流,減少擁塞,并消除可能的瓶頸問題。但是,由于移動自組網(wǎng)具有動態(tài)的拓撲(節(jié)點可能會引入或退出網(wǎng)絡(luò))、有限的帶寬及采用電池供電等諸多特性,這種平面式結(jié)構(gòu)在節(jié)點數(shù)目增多時的路由開銷很大,因此可擴展性較差。解決這個問題的最主要方法就是采用適當(dāng)?shù)姆执厮惴?gòu)造分層的拓撲。相互鄰近的一組節(jié)點構(gòu)成一個簇,簇內(nèi)的成員可分簇首、簇成員、網(wǎng)關(guān)三種。簇成員之間的通信通過簇首進行,簇之間的通信則經(jīng)過網(wǎng)關(guān)轉(zhuǎn)發(fā)。在移動自組網(wǎng)絡(luò)中,基于簇的層次結(jié)構(gòu)能夠優(yōu)化網(wǎng)絡(luò)帶寬的應(yīng)用,提高共享信道的利用率,減少路由維護的代價以及提高應(yīng)用的可擴展性,在路由、安全、網(wǎng)絡(luò)管理及服務(wù)發(fā)現(xiàn)等方面具有重要的應(yīng)用。2集群算法的測量標(biāo)準(zhǔn)和工具2.1多節(jié)點獲得結(jié)構(gòu)穩(wěn)定性的標(biāo)準(zhǔn)化標(biāo)準(zhǔn)目前,衡量一個分簇算法的優(yōu)劣主要有以下幾個標(biāo)準(zhǔn):簇結(jié)構(gòu)的穩(wěn)定性、簇首節(jié)點的數(shù)量、負載均衡度(LoadBalancingFactor)及節(jié)電能力等。(1)簇結(jié)構(gòu)穩(wěn)定性控制由于移動自組網(wǎng)節(jié)點的動態(tài)特性,簇結(jié)構(gòu)經(jīng)常會因節(jié)點的加入/離開、不同簇首相遇時的競爭而發(fā)生變化。一個相對穩(wěn)定的簇結(jié)構(gòu)能夠有效地降低由于簇的重構(gòu)而帶來的通信與電能開銷,因而維持簇結(jié)構(gòu)的穩(wěn)定具有重要的意義。簇結(jié)構(gòu)的穩(wěn)定性用節(jié)點狀態(tài)(一般說來,節(jié)點狀態(tài)有簇首、簇成員與未決(Undecided)三種)變化頻率以及簇首節(jié)點變化頻率度量,分別定義為單位時間內(nèi)節(jié)點狀態(tài)變化次數(shù)、簇首節(jié)點變化次數(shù)。變化次數(shù)越小,則簇的穩(wěn)定性就越高。(2)高鏈路的利用率在鏈路容量許可的情況下,簇首節(jié)點數(shù)目少的算法能有效地提高鏈路的利用率。但是,由于節(jié)點資源限制,簇首不可能服務(wù)所有鄰居節(jié)點,即簇成員的數(shù)量應(yīng)有一定的限制,如藍牙協(xié)議,其主從結(jié)構(gòu)限制了每個主節(jié)點只能同時服務(wù)七個成員節(jié)點。(3)節(jié)點系統(tǒng)的動態(tài)均衡簇首的負載大小取決于其所支持的節(jié)點的多少。維護簇結(jié)構(gòu)與簇間路由均需要消耗簇首一定的資源,因此不希望出現(xiàn)有的簇首過載、有的簇首卻很輕閑的狀況。但是,由于節(jié)點經(jīng)常性地加入/離開,很難使系統(tǒng)一直維持在良好的負載均衡狀態(tài)。為了量化簇首負載的均衡程度,文獻提出了負載均衡度的概念:LBF=nc∑i(xi?u)2LBF=nc∑i(xi-u)2其中,xi為簇首節(jié)點i的成員節(jié)點數(shù),u為簇首的平均鄰居節(jié)點數(shù)量,u=(N-nc)/nc,N為網(wǎng)絡(luò)中的節(jié)點數(shù),nc為簇首節(jié)點的數(shù)量。該值越大,則表示負載均衡度越好。2.2glomosim、opnet與q智能化目前,用于分簇算法模擬的主要有以下這幾種模擬器:ns-2、GlomoSim、OPNET和Qualnet。其中,ns-2與GlomoSim屬免費軟件,代碼公開,對于有線以及無線網(wǎng)絡(luò)上的TCP、路由、組播協(xié)議等能夠提供有力的支持,因而在科學(xué)研究中得到廣泛的應(yīng)用。OPNET和Qualnet屬商用軟件,更適于開發(fā)實際的工程項目,但需付費使用。Qualnet中的一些模型甚至要求提供相關(guān)的(美)軍方許可才可以使用。3添加適當(dāng)控制信息現(xiàn)有分簇算法在分簇過程中大多顯式地使用控制信息,即各節(jié)點通過周期性地交換控制信息來選擇簇首,但也有些算法隱含地使用控制信息,即在正常的數(shù)據(jù)包中嵌入適當(dāng)?shù)目刂菩畔ⅰ０凑湛刂菩畔⒌氖褂梅绞?可將分簇算法分為主動分簇算法和被動分簇算法兩類。3.1主動分簇算法所有主動分簇算法的共同特征是需要通過周期性地交換控制信息來選擇簇首。按照選擇簇首的標(biāo)準(zhǔn),主動分簇算法又可分為最小ID或最大連接度相關(guān)算法、最小ID或最大連接度無關(guān)算法以及其它算法等三類。需要說明的是,這里的分類只是為了敘述方便,并無統(tǒng)一的標(biāo)準(zhǔn)。3.1.1基于最大連接度的最小id算法最小ID算法與最大連接度算法是最早提出的分簇算法。在最小ID算法中,每個節(jié)點擁有一個全網(wǎng)范圍內(nèi)唯一的標(biāo)識(ID),并周期性地向其鄰居節(jié)點(在其接收范圍內(nèi)的節(jié)點)廣播其ID值。這樣,每個節(jié)點就可以將自己的ID值與其直接鄰居節(jié)點進行比較,如果發(fā)現(xiàn)自己為ID值最小的節(jié)點,則自動成為簇首節(jié)點。如果一個節(jié)點處于兩個或多個簇首的發(fā)送范圍之內(nèi),則稱為網(wǎng)關(guān)節(jié)點。網(wǎng)關(guān)節(jié)點通常用于簇間的路由。最大連接度算法選擇簇首的標(biāo)準(zhǔn)是連接度,也就是一個節(jié)點的直接鄰居個數(shù)。與最小ID算法一樣,每個節(jié)點周期性地向其直接鄰居節(jié)點廣播自己的連接度。這樣,每個節(jié)點就可以將自己的連接度與直接鄰居節(jié)點相互比較,如果發(fā)現(xiàn)自己的連接度最大,則自動成為簇首節(jié)點,其鄰居節(jié)點成為簇成員節(jié)點。最小ID算法的主要優(yōu)點是簡單,主要缺點是ID較小的節(jié)點成為簇首的可能性要遠高于其他節(jié)點。因此,算法在能源有限的移動自組網(wǎng)絡(luò)中缺乏公平性。最大連接度算法的簇首數(shù)目較少,但算法對簇內(nèi)節(jié)點數(shù)目沒有限制,因而無法適用于某些對節(jié)點能力有限制的網(wǎng)絡(luò)(如藍牙協(xié)議,其主從結(jié)構(gòu)限制了每個主節(jié)點最多只能同時服務(wù)七個成員節(jié)點)。對于其它沒有節(jié)點限制的協(xié)議也有問題,當(dāng)節(jié)點數(shù)目增多時,節(jié)點的吞吐量會降低。此外,對于環(huán)狀拓撲,每個節(jié)點的度數(shù)均為2,還需要增加額外的規(guī)則保證算法的正確性。盡管這兩種算法存在很多不足,它們?nèi)匀皇呛罄m(xù)各種分簇算法進行性能比較的對象。由于最小ID算法與最大連接度算法存在諸多不足,于是很快又出現(xiàn)了不少基于這兩種算法的改進算法。LinandGerla提出了一種改進的最小ID算法,其簇生成過程與最小ID法完全相同,但在簇結(jié)構(gòu)發(fā)生變化時,不再按照最小ID選擇新簇首,而是將連接度最大的節(jié)點及其鄰居仍留在原始簇中?；跈?quán)值的算法(DCA算法、WCA算法)也可看成是最小ID法的擴展。這種算法假設(shè)每個節(jié)點具有唯一的權(quán)值,選擇鄰居節(jié)點中權(quán)值最大的節(jié)點作為簇首節(jié)點。權(quán)值與節(jié)點連接度、標(biāo)識等因素緊密相關(guān)(WCA算法還考慮了節(jié)點的移動速度、能耗以及簇成員限制等因素),雖然簇結(jié)構(gòu)的穩(wěn)定性有所提高,但每種因素在權(quán)值中所占的比重不確定,并且權(quán)值的計算和存儲需要一定的代價。3.1.2基于穩(wěn)定鏈路的分簇算法由于度量分簇算法的首要標(biāo)準(zhǔn)是簇結(jié)構(gòu)的穩(wěn)定性,而最小ID或最大連接度與簇結(jié)構(gòu)的穩(wěn)定性并無直接關(guān)系,因此一些分簇算法跳出了最小ID與最大連接度的圈囿,采用了完全不同的簇首選擇標(biāo)準(zhǔn)。其中,最有代表性、同時也頗具發(fā)展前景的主要有:基于位置預(yù)測的算法、基于節(jié)點移動性的算法和基于鏈路穩(wěn)定性的算法等。文獻提出了一個基于移動位置預(yù)測的分簇算法-(pik,tik,dik)算法。該算法將一個MANET網(wǎng)絡(luò)覆蓋的地理區(qū)域劃分為多個靜態(tài)的虛簇,并假定區(qū)域中每個移動節(jié)點知道虛簇中心(VCC)的位置信息。虛簇可以包含一個實簇,也可以不包括。(pik,tik,dik)簇算法按照以下原則選擇簇首:與同一個虛簇內(nèi)的其它節(jié)點相比,節(jié)點移出當(dāng)前所在虛簇的概率最小;節(jié)點與當(dāng)前虛簇中心的距離最短。前一個條件是為了排除移動性強的節(jié)點作為簇首的可能,后一個條件是為了保證簇首改變時,簇覆蓋的區(qū)域不會有大的變化。這里,pik表示第k個虛簇中的節(jié)點i,在距虛簇中心的距離為dik、停留時間為tik時的概率。如果k號虛簇中的節(jié)點i在tik≥tc(tc為與系統(tǒng)相關(guān)的一個常量)時滿足pik=pmax,則該節(jié)點成為該虛簇的簇首節(jié)點。由于移動是引起簇首與簇成員關(guān)系變化的主要原因,因此Prithwish提出的MOBIC算法就將移動性(Mobility)作為分簇與簇首選舉的一個重要因素。Prithwish依據(jù)以下假定提出了本地移動性度量標(biāo)準(zhǔn):接收節(jié)點檢測到的信號強度。通過接收到的鄰居節(jié)點后續(xù)發(fā)送的包(如周期性的“Hello”報文),可獲取當(dāng)前節(jié)點與鄰居節(jié)點間的相間移動性。初始時所有節(jié)點處于“未決”狀態(tài),每個節(jié)點周期性地在其Hello報文中廣播其移動性度量值M,鄰居節(jié)點接收到該值后將其存儲在本地的鄰居表中,并將自己的度量值與其進行比較。如果發(fā)現(xiàn)自己具有最小的度量值,則將狀態(tài)設(shè)為簇首,否則為簇成員。如果一個節(jié)點是兩個簇首的鄰居,則該節(jié)點成為網(wǎng)關(guān)節(jié)點。文獻提出了一種基于穩(wěn)定鏈路的分簇算法。該算法用CSm,n-avg(SS)表示從節(jié)點m到n的平均信號強度,并使用自由空間傳播模型(Freespacepropagationmodel)來預(yù)測接收到的信號強度(按以下Friis自由空間方程計算):Pr(d)=(PtGtG2r)/[(4π)2d2L]Ρr(d)=(ΡtGtGr2)/[(4π)2d2L]式中,Pr(d)是接收方功率;Gr是接收方天線增益;Pt是發(fā)送功率;Gt是發(fā)送方天線增益;L是系統(tǒng)損耗率;d是發(fā)送方到接收方的距離。該算法使用模糊理論將信號強度正規(guī)化為弱、中、強三個等級,盡可能地選取具有穩(wěn)定鏈路的節(jié)點作為簇首。3.1.3基于模糊規(guī)則的分簇算法還有一些算法與上述兩類算法有顯著的區(qū)別。一是基于模糊規(guī)則的算法。該算法選擇簇首的標(biāo)準(zhǔn)已經(jīng)不是一個,而是多個,并且是開放的,可以任意增加所需要的標(biāo)準(zhǔn)。WCA算法也考慮了多個簇首選擇標(biāo)準(zhǔn),但將所有標(biāo)準(zhǔn)綜合成一個權(quán)值,盡管基于模糊規(guī)則的算法顯得更合理,但由于考慮的因素很多,無論是通信開銷還是本地計算開銷都高于一般的分簇算法。另一種比較特別的算法是k-跳分簇算法,其簇成員到簇首的距離最多為k-hop(這種簇也稱k-cluster),而不是上述算法所采用的1-跳,這樣就必須解決簇內(nèi)通信的路由問題,而不能象其它分簇算法那樣直接利用adhoc網(wǎng)絡(luò)的廣播特性。此外,還有一些針對特定網(wǎng)絡(luò)環(huán)境的分簇算法,如針對存在單向鏈路的算法、針對節(jié)能要求的算法等。3.2ence:移動性信息更新的關(guān)鍵階段到目前為止,大多數(shù)分簇算法都是通過模擬進行研究的,并且需要完全的鄰居信息。由于移動自組網(wǎng)絡(luò)無固定中心的特征,鄰接信息只能通過交換beacon或hello信息收集。在這個“鄰居學(xué)習(xí)”(Neighbor-Learning)過程中,一般都假定節(jié)點不移動。在周期性的鄰居學(xué)習(xí)與分簇的初始階段,“節(jié)點不移動”對于正確的收斂(Convergence)是很重要的。這種假定必須存在于鄰接關(guān)系收集的整個階段、分簇的初始階段、重分簇階段。如果發(fā)生了移動,我們可能必須在鄰居學(xué)習(xí)階段處理陳舊的鄰居信息。并且,移動性導(dǎo)致鄰接關(guān)系改變,繼而可能觸發(fā)整個網(wǎng)絡(luò)的重新分簇。針對主動分簇算法存在的問題,文獻提出了被動分簇的概念,不需要周期性的通信開銷,也不需要節(jié)點不移動的假定。具體說來,被動分簇算法在簇的生成與維護過程中均不使用專用的控制信息,而是利用從正常數(shù)據(jù)包(如MAC幀)中獲取的鄰接信息,或者在數(shù)據(jù)包中嵌入適當(dāng)?shù)姆执貭顟B(tài)信息。從數(shù)據(jù)包中獲取的信息大多與基于權(quán)值的分簇算法相關(guān)。為了取得穩(wěn)定的簇結(jié)構(gòu),被動分簇沒有使用加權(quán)方式,而是使用了“先聲明先贏”規(guī)則(FirstDeclarationWins):第一個發(fā)出數(shù)據(jù)包的節(jié)點成為簇首,并“統(tǒng)治”簇(簇首的鄰接區(qū)域)中的其它節(jié)點。被動分簇算法的優(yōu)點是不需要顯式地使用控制信息,節(jié)省帶寬資源,其分簇過程可以在沒有收集到完整的鄰居信息的情況下進行。當(dāng)連接改變時,被動分簇不需要一個重構(gòu)過程以滿足某些分簇規(guī)則(如最小ID等)的要求。綜上所述,被動分簇是一項極具發(fā)展前景的adhoc網(wǎng)絡(luò)分層技術(shù)。4研究熱點分析在移動自組網(wǎng)絡(luò)中,基于簇的層次結(jié)構(gòu)具有廣泛的應(yīng)用,是解決移動自組網(wǎng)絡(luò)擴展性的最重要手段。以上我們介紹了當(dāng)前典型的分簇算法的特征及其主要優(yōu)缺點。從以上論述中我們可以看到:由于主動分簇算法使用顯式的控制信息并能充分利用移動自組網(wǎng)的廣播特性,因此受到廣泛的研究。盡管被動分簇算法的研究相對較晚,但在某些具體的應(yīng)用領(lǐng)域,卻具有主動分簇算法難以替代的作用。由于移動自組網(wǎng)本身尚處在研究階段,故有關(guān)分簇算法的研究也處在不斷發(fā)展之中。未來分簇算法的研究熱點應(yīng)當(dāng)集中在以下幾個方面:(1)增加簇結(jié)構(gòu)的穩(wěn)定性。穩(wěn)定的簇結(jié)構(gòu)能夠有效地增加節(jié)點收發(fā)報文的成功率,減少簇重構(gòu)的幾率,也有利于降低節(jié)點通信代價。(2)降低通信代價。由于移動自組網(wǎng)絡(luò)的節(jié)點隨機移動、帶寬有限等特點,通信開銷就成了一個不容忽視的重要因素。降低通信開銷的一個重要手段是增加簇結(jié)構(gòu)的穩(wěn)定性,但被動分簇也許是一個更有效的手段。(3)充分結(jié)合組移動的特點?，F(xiàn)有分簇算法大都是基于“節(jié)點運動是隨機的,互不相關(guān)的”的假設(shè)設(shè)計的。但是,在真實場景中,卻有大量的組移動現(xiàn)象,如戰(zhàn)場上一組士兵受領(lǐng)任務(wù)(如排雷、捉俘)搜索指定區(qū)域,一群學(xué)生參觀博物館,多個不