移動自組網絡中的層次結構

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