移動adhoc網(wǎng)絡中基于分簇的資源分配方法

移動adhoc網(wǎng)絡中基于分簇的資源分配方法

移動adhoc網(wǎng)絡（manet）的內(nèi)部結(jié)構(gòu)可以分為平坦型和分類型。平面結(jié)構(gòu)比較健壯,但是控制開銷大,可擴展性不佳,主要適用于中小型網(wǎng)絡。分級結(jié)構(gòu)中,網(wǎng)絡劃分成簇,每個簇包含一個簇頭和多個簇成員,簇頭和網(wǎng)關構(gòu)成虛擬骨干網(wǎng)。分級結(jié)構(gòu)的優(yōu)點是網(wǎng)絡可擴充性好,容易實現(xiàn)網(wǎng)絡的管理和同步。另外,基于分簇結(jié)構(gòu),MANET可采用類似蜂窩網(wǎng)絡的資源分配方法。在簇內(nèi),簇頭可以控制節(jié)點的業(yè)務接入請求并合理分配帶寬。因此通過分簇算法將網(wǎng)絡劃分成簇可以提高Adhoc網(wǎng)絡的性能,具有重要意義。1最小統(tǒng)治集網(wǎng)絡mds。在現(xiàn)代社會分簇算法的目標是構(gòu)造一個能夠覆蓋整個網(wǎng)絡并較好支持資源管理和路由的互連的簇集合。為減少分簇開銷,分簇算法應簡單高效,當只有很少節(jié)點移動和拓撲變化較慢時,網(wǎng)絡應盡量保持原有結(jié)構(gòu),從而減少重新分簇引入的開銷并提高網(wǎng)絡效能。理想情況下希望以最少的簇頭覆蓋整個網(wǎng)絡,即簇頭的集合為最小統(tǒng)治集(MDS)。網(wǎng)絡的統(tǒng)治集是由所有簇頭組成的集合,并且滿足其他節(jié)點都是統(tǒng)治集中某節(jié)點的鄰居節(jié)點。進一步還可考慮限制簇頭成為鄰居節(jié)點,即簇頭的集合構(gòu)成網(wǎng)絡的統(tǒng)治無關集(DIS)。滿足MDS的簇頭優(yōu)化問題等價于最小集覆蓋問題(MSC),后者是NP完全問題,因此一般采用啟發(fā)式算法。2一些典型的adhoc網(wǎng)絡分組算法2.1白色節(jié)點的識別算法最高節(jié)點度分簇算法的目標是提高網(wǎng)絡的控制能力和減少簇的數(shù)目。算法工作過程描述如下:(1)初始時,網(wǎng)絡中每個節(jié)點標記為白色;(2)當一個白色節(jié)點發(fā)現(xiàn)它是鄰居白色節(jié)點中節(jié)點度最大的節(jié)點時,它成為簇頭,并標記自己為黑色(節(jié)點度相同時選擇ID較小的節(jié)點為簇頭);(3)簇頭的鄰居成為簇的普通節(jié)點,并標記為灰色;(4)重復(2)和(3),直到網(wǎng)絡中不存在白色節(jié)點。該算法的特點是簇數(shù)目較少,減少了分組投遞時延,但也減少了信道空間重用率。由于簇內(nèi)節(jié)點數(shù)不受限制,并且信道由節(jié)點共享,當簇內(nèi)節(jié)點數(shù)量過多時,每個節(jié)點的吞吐量急劇下降。此外,當節(jié)點移動性較強時,簇頭更新頻率較高,簇維護開銷較大。因此,該算法適合于移動性較弱并且節(jié)點密度較低的場合。2.2最小id算法最小ID啟發(fā)式算法只依據(jù)節(jié)點ID選擇簇頭,即在最高節(jié)點度算法的步驟(2)中,相鄰白色節(jié)點中ID最小的節(jié)點為簇頭。該算法計算簡單,實現(xiàn)方便。在移動環(huán)境下,最小ID算法的簇頭更新頻率較慢,維護簇開銷較小,并且網(wǎng)絡的吞吐量高于最高度啟發(fā)式算法。但是該算法傾向選擇ID較小的節(jié)點為簇頭,使這些節(jié)點消耗更多的能量,減少了網(wǎng)絡出現(xiàn)分割的時間,并且沒有考慮負載平衡等因素。2.3最低移動性分簇算法節(jié)點權(quán)重啟發(fā)式算法基于適合作為簇頭的程度來為每個節(jié)點分配權(quán)重。即在最高節(jié)點度算法的步驟(2)中,相鄰白色節(jié)點中權(quán)重最高的節(jié)點為簇頭(權(quán)重相同時,選擇ID較小的節(jié)點)。一種方法是根據(jù)節(jié)點的移動速率為節(jié)點分配權(quán)重,移動速度越快,分配的權(quán)重越低,可以看作是最低移動性分簇算法。在移動性較強時,該算法可以明顯減少簇頭更新頻率。它的缺點是節(jié)點權(quán)重的更新較頻繁,簇頭計算開銷較大,并且未考慮負載平衡和節(jié)點的能量損耗問題。2.4基于自適應按虛加權(quán)算法的聚合式區(qū)分區(qū)分算法以上算法選擇簇頭時只考慮某方面的因素,簇頭選擇不夠優(yōu)化。為此,可采用一種組合加權(quán)算法來選舉簇頭以改善分簇網(wǎng)絡的性能。每個節(jié)點分配一個權(quán)值(W)指示它適合充當簇頭的程度,W=am+bd+cp+de+x。其中,m表示節(jié)點的移動性;d表示節(jié)點度;p表示節(jié)點的傳輸功率;e表示節(jié)點剩余的能量;x表示其它可能的因素對組合權(quán)重的影響。參數(shù)a、b、c為權(quán)重因子,可動態(tài)調(diào)整。自適應按虛加權(quán)(AOW)算法選舉簇頭時綜合考慮4種因素:節(jié)點度、節(jié)點的傳輸功率、節(jié)點的移動性和節(jié)點的剩余能量。另外,簇的維護采用按需更新簇頭的策略:只有當節(jié)點移出統(tǒng)治集覆蓋范圍時才重新選舉簇頭。AOW算法與上述算法的區(qū)別主要在于簇頭的選舉,這里將選舉簇頭的過程描述如下:(1)節(jié)點n計算其度數(shù)dn與理想度數(shù)M之差,即Dn=|dn-M|。(2)節(jié)點n計算其到所有鄰居節(jié)點的距離總和Pn。(3)根據(jù)節(jié)點n的平均移動速度來表示其移動性Mn。(4)統(tǒng)計節(jié)點n作為簇頭的時間Tn來表示已經(jīng)消耗的電池能量。(5)計算每個節(jié)點n的組合權(quán)重In=c1Dn+c2Pn+c3Mn+c4Tn。其中,c1~c4為權(quán)重因子,某個參數(shù)越重要,權(quán)重因子越大,并滿足c1+c2+c3+c4=1。(6)選擇相鄰白色節(jié)點中In最小的白色節(jié)點為簇頭,如果In相同,選擇ID較小的節(jié)點為簇頭。2.5各節(jié)點算法設計假設一個網(wǎng)絡有12個節(jié)點,節(jié)點的理想度數(shù)Dideal=2,c1=0.7,c2=0.2,c3=c4=0.05,各個節(jié)點的Mn和Tn如表1所示。在相同網(wǎng)絡條件下,采用以上4種算法得到的分簇網(wǎng)絡結(jié)構(gòu)分別如圖1中的(a)~(d)所示。從圖中可以看出,4種算法得到的簇結(jié)構(gòu)中,簇頭數(shù)和充當簇頭的節(jié)點數(shù)各不相同:最高節(jié)點度算法的簇頭數(shù)較少(4個),最小ID算法的簇頭數(shù)最多(7個),而最低移動性和AOW算法的簇頭數(shù)介于兩者之間(6個)。3集群算法的性能比較3.1節(jié)點移動方向隨機排列對以上4種算法比較時采用以下指標:簇頭數(shù)C、單位時間內(nèi)節(jié)點重入簇的次數(shù)J(即簇間轉(zhuǎn)移的次數(shù))和統(tǒng)治集更新的次數(shù)U、節(jié)點充當簇頭的公平性指數(shù)(HFI)。HFI為E{|[ti-E(ti)]|},i∈V。ti表示節(jié)點i擔當簇頭的時間,E(ti)表示節(jié)點作簇頭的平均時間。HFI越小,節(jié)點充當簇頭的公平性越好,從而延長網(wǎng)絡分割的時間。在具體模擬實現(xiàn)時,未考慮背景噪聲、分組傳輸差錯和沖突的影響。因為模擬環(huán)境對各算法是公平的,簡化模擬不會影響分簇算法的比較結(jié)果。在一個100×100單位距離的區(qū)域內(nèi)隨機放置N個節(jié)點,節(jié)點移動方向在[0,2π]內(nèi)隨機分布,移動速度在[0,maxV]內(nèi)隨機選擇,單位是距離/時間。當節(jié)點到達區(qū)域邊界時,它向區(qū)域內(nèi)反射。節(jié)點的數(shù)量、傳輸范圍和移動速度均可根據(jù)要求動態(tài)調(diào)整。為了更好地比較,在此4種算法均采用按需更新簇頭的簇維護策略。3.2節(jié)點傳輸范圍首先比較簇頭數(shù)隨節(jié)點傳輸范圍的變化。固定節(jié)點數(shù)n=30,節(jié)點最大移動速度v=5,節(jié)點傳輸范圍r從5~70變化。模擬結(jié)果如圖2所示,其中LOWID表示最小ID算法,HIGHD表示最高節(jié)點度算法,WM表示基于速率的節(jié)點權(quán)重算法,AOW和AOW1均表示自適應按需加權(quán)算法。但前者中,M=10,c1=0.7,c2=0.2,c3-c4=0.05;后者中,M=4,c1=c2=0.1,c3=c4=0.4。從圖中看出,簇頭數(shù)隨節(jié)點傳輸范圍的增加而減少,當傳輸范圍大于30后,速度逐漸變慢,最終收斂到1。此外,HIGHD的簇頭數(shù)明顯偏低,與前面分析吻合。AOW的簇頭數(shù)略大于WM和LOWID,并且AOW稍大于AOW1,因為AOW限制了節(jié)點度,簇的分布更加合理,并且AOW中的權(quán)重c1略大。另外,模擬結(jié)果(如圖3所示)表明,當節(jié)點傳輸范圍較低時,簇數(shù)較多,簇內(nèi)節(jié)點數(shù)很少,節(jié)點離開原簇的概率很小。當傳輸范圍增大時,J逐漸增加并在傳輸范圍為25左右達到最大值,隨后J開始下降。并且可以看到,對于指標J,各算法的性能差別較小,可比性較差。節(jié)點在簇間轉(zhuǎn)移引入的開銷較小,而統(tǒng)治集更新會帶來較大開銷,因此更加關心指標U的大小。模擬結(jié)果表明(如圖4所示),當節(jié)點傳輸范圍較小時,統(tǒng)治集的覆蓋范圍(統(tǒng)治域)較小,節(jié)點容易移出統(tǒng)治域,當節(jié)點的傳輸范圍增加時,統(tǒng)治域隨之增加,節(jié)點移出統(tǒng)治域的概率減小。此外可以看到HIGHD算法的U明顯偏大,因為它選擇簇頭只考慮節(jié)點的度數(shù),簇頭的分布不合理,移動環(huán)境下,節(jié)點度數(shù)變化較頻繁,簇頭更新較多。AOW的簇頭較穩(wěn)定,分布較均勻,并能根據(jù)節(jié)點分布自適應調(diào)節(jié);LOWID的簇頭較穩(wěn)定,但是簇頭分布不均勻;WM能夠較好適應移動性,但對其它因素(節(jié)點的分布和電池能量)考慮較少;AOW1更加強調(diào)電池能量和節(jié)點移動性,性能略低于AOW,但是可以減少網(wǎng)絡分割的概率,并且簇頭移動性較低,增強了骨干網(wǎng)絡的穩(wěn)定性。模擬結(jié)果(圖略)還表明,節(jié)點的運動速度對簇頭數(shù)幾乎沒有影響,因為簇頭的多少是由節(jié)點的傳輸范圍決定的。但是,J和U均隨節(jié)點速度的增加而增大。下面比較各算法下HFI的區(qū)別。節(jié)點數(shù)為30,節(jié)點最大移動速度為5,傳輸范圍從5到150變化,模擬時間為1000。從模擬結(jié)果(如圖5所示)可以看出,LOWID和WM的HFI較大,AOW的HFI較小,而HIGHD介于其間,并且AOW1的HFI略小于AOW。此外,HFI基本上隨傳輸范圍的增加先增加后減小。模擬結(jié)果分析如下:LOWID中ID較小的節(jié)點傾向充當簇頭,導致各節(jié)點作為簇頭的時間偏差較大。WM僅考慮節(jié)點的移動性來計算權(quán)重,因此速度較低的節(jié)點將成為簇頭,導致HFI較大。HIGHD算法中節(jié)點度隨節(jié)點的運動不斷變化,各節(jié)點都可能為簇頭,HFI較小。AOW中,節(jié)點的權(quán)重隨時間不斷改變,各節(jié)點都可能作簇頭,HFI較小。當傳輸范圍很小時,大多節(jié)點都是簇頭,HFI很小。當傳輸范圍增大時,簇頭數(shù)減少,HFI增大。傳輸范圍繼續(xù)增加時,簇頭數(shù)迅速減少,各節(jié)點作簇頭的平均時間較小,HFI也較小。由于節(jié)點移出統(tǒng)治集時才更新簇頭,當傳輸范圍很大時,一個節(jié)點被選為簇頭,它將永遠是簇頭,而其他節(jié)點為簇頭的時間為0,所以各算法的HFI都等于64.4。這也意味著傳輸范圍過大時,各算法下節(jié)點充當簇頭的公平性都不好,因此需要控制節(jié)點的傳輸功率。4不同分簇算法的優(yōu)缺點分析分簇結(jié)構(gòu)有利于移動管理、資源分配和提高可擴展性。但是分簇算法會帶來計算、通