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

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

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