adhoc網(wǎng)絡(luò)的分簇算法

ad-key網(wǎng)絡(luò)是一個(gè)特殊的多段移動(dòng)網(wǎng)絡(luò)，具有廣闊的應(yīng)用場(chǎng)所，特別適用于戰(zhàn)術(shù)通信、救援、臨時(shí)會(huì)議等突然和臨時(shí)場(chǎng)所。Adhoc網(wǎng)絡(luò)的體系結(jié)構(gòu)可以是平面式的,也可以是分級(jí)式的。平面式結(jié)構(gòu)中,網(wǎng)絡(luò)中所有節(jié)點(diǎn)的功能和地位相等,網(wǎng)絡(luò)比較健壯,并且結(jié)點(diǎn)的覆蓋范圍比較小,相對(duì)比較安全。但在用戶較多,特別是在移動(dòng)的情況下,存在處理能力弱、控制開銷大、路由經(jīng)常出現(xiàn)中斷等缺點(diǎn),因此它主要適用于中小型網(wǎng)絡(luò)。分級(jí)結(jié)構(gòu)中,網(wǎng)絡(luò)被劃分成若干個(gè)簇,每個(gè)簇由一個(gè)簇頭和多個(gè)普通節(jié)點(diǎn)組成。簇頭之間的通信需要借助于網(wǎng)關(guān)或分布式網(wǎng)關(guān)完成,簇頭和網(wǎng)關(guān)形成了高一級(jí)的網(wǎng)絡(luò),稱為虛擬骨干網(wǎng)。分級(jí)結(jié)構(gòu)的最大優(yōu)點(diǎn)是網(wǎng)絡(luò)的可擴(kuò)充性好,網(wǎng)絡(luò)的規(guī)模不受限制,路由和控制開銷比平面結(jié)構(gòu)小,并且容易實(shí)現(xiàn)移動(dòng)性管理和網(wǎng)絡(luò)的局部同步。但是分級(jí)結(jié)構(gòu)也有缺點(diǎn),首先,維護(hù)分級(jí)結(jié)構(gòu)需要較復(fù)雜的簇頭選擇算法;其次,節(jié)點(diǎn)之間的路由不一定是最優(yōu)路由。比如在不同簇中但互為鄰居的結(jié)點(diǎn),在平面結(jié)構(gòu)中可以直接通信,但分簇后要通過簇頭進(jìn)行轉(zhuǎn)發(fā)。然而,可以通過設(shè)計(jì)合理的簇頭選擇算法來減少由于節(jié)點(diǎn)移動(dòng)需要維護(hù)簇結(jié)構(gòu)而引入的開銷,并且可以通過分布式網(wǎng)關(guān)來優(yōu)化路由,此外可以通過負(fù)載平衡策略或無簇頭分簇算法來防止簇頭成為瓶頸。Adhoc網(wǎng)絡(luò)面臨的另一個(gè)挑戰(zhàn)是如何高效地分配資源,從而可以按照定量或統(tǒng)計(jì)的方式來預(yù)約帶寬。在蜂窩網(wǎng)絡(luò)中,資源的分配比較容易實(shí)現(xiàn),各個(gè)移動(dòng)節(jié)點(diǎn)可以直接或借助基站獲得其它通信節(jié)點(diǎn)的帶寬要求,即通過基站來進(jìn)行資源分配。但是如果將網(wǎng)絡(luò)劃分成基于簇的分級(jí)結(jié)構(gòu),就能夠?qū)⒎涓C網(wǎng)絡(luò)中使用的方法擴(kuò)展到Adhoc網(wǎng)絡(luò)。在每個(gè)簇內(nèi),簇頭可以控制節(jié)點(diǎn)的業(yè)務(wù)請(qǐng)求接入并且合理地分配帶寬。此外,在分簇結(jié)構(gòu)中可以采用分級(jí)路由算法,簇內(nèi)采用先驗(yàn)式路由算法,節(jié)點(diǎn)維護(hù)到簇內(nèi)其它節(jié)點(diǎn)的完整的路由信息,簇間使用反應(yīng)式路由協(xié)議來減少通信和路由開銷。因此通過分簇算法將網(wǎng)絡(luò)劃分成簇可以在很大程度上提高Adhoc網(wǎng)絡(luò)的性能,具有重要的意義。1節(jié)點(diǎn)機(jī)團(tuán)內(nèi)分簇定義1系統(tǒng)拓?fù)銰=(V,E)是由節(jié)點(diǎn)和鏈路構(gòu)成的圖。V表示節(jié)點(diǎn)的集合,E表示邊的集合。節(jié)點(diǎn)x和y之間存在邊(x,y),意味著節(jié)點(diǎn)x和節(jié)點(diǎn)y是可以互相通信的1跳鄰居節(jié)點(diǎn)。定義21個(gè)簇Ci?V由一組節(jié)點(diǎn)構(gòu)成,并且對(duì)于任何2個(gè)節(jié)點(diǎn)x,y∈Ci,滿足d(x,y)≤h,h是可變的系統(tǒng)參數(shù),同時(shí)滿足V=∪iCiV=∪iCi。如果Ci∩Cj=?,i≠j,那么稱簇Ci和簇Cj為非交疊簇,反之兩者構(gòu)成交疊簇。定義3兩節(jié)點(diǎn)間的距離d(x,y)是指節(jié)點(diǎn)x和y之間的最小跳數(shù)。定義41個(gè)節(jié)點(diǎn)的1跳鄰居節(jié)點(diǎn)的數(shù)目稱為該節(jié)點(diǎn)的度數(shù)。定義5對(duì)于具有簇頭h的簇Ci而言,如果簇內(nèi)的任何節(jié)點(diǎn)x到簇頭h的距離最多為k跳,那么,稱該簇為k跳,即Max{d(x,h),x∈Ci}≤k,那么,稱簇Ci為k跳有頭簇。對(duì)于不選舉簇頭的簇Cj而言,如果簇內(nèi)任何2個(gè)節(jié)點(diǎn)x和y的距離不超過k跳,即Max{d(x,y),x,y∈Ci}≤k,那么,稱Cj為k跳無頭簇。定義6如果1個(gè)節(jié)點(diǎn)同時(shí)位于多個(gè)簇頭的通信范圍,則稱其為網(wǎng)關(guān)節(jié)點(diǎn)。分簇算法就是根據(jù)系統(tǒng)的要求將網(wǎng)絡(luò)劃分成多個(gè)簇,簇的大小可以由節(jié)點(diǎn)的無線傳輸功率控制。在分簇網(wǎng)絡(luò)結(jié)構(gòu)中,動(dòng)態(tài)運(yùn)動(dòng)的節(jié)點(diǎn)會(huì)經(jīng)常加入或離開某個(gè)簇,從而影響系統(tǒng)的穩(wěn)定性。更為嚴(yán)重的,劇烈的節(jié)點(diǎn)移動(dòng)有時(shí)會(huì)導(dǎo)致簇頭的更新和網(wǎng)絡(luò)的重新配置,而頻繁的簇頭更新會(huì)引入較大的計(jì)算和通信開銷,并且嚴(yán)重影響其它網(wǎng)絡(luò)協(xié)議的性能,如分組調(diào)度、路由和資源管理等。分簇算法的目標(biāo)就是構(gòu)造一個(gè)能夠覆蓋整個(gè)用戶節(jié)點(diǎn)的、可以較好支持資源管理和路由協(xié)議的相互連接的簇的集合。為了減少分簇算法帶來的通信和計(jì)算開銷,分簇算法應(yīng)該簡單高效,在只有很少的節(jié)點(diǎn)移動(dòng)和拓?fù)渥兓^慢時(shí),分簇機(jī)制應(yīng)該盡量保持原有結(jié)構(gòu),從而減少重新生成簇引入的開銷和提高網(wǎng)絡(luò)的總體效能。文獻(xiàn)中說明了簇頭的優(yōu)化選擇是NP完全問題,因此一般采用啟發(fā)式算法。但是好的分簇機(jī)制應(yīng)盡量保持網(wǎng)絡(luò)拓?fù)浞€(wěn)定,減少重新分簇的頻率,并且還應(yīng)考慮節(jié)點(diǎn)的能量級(jí)別、網(wǎng)絡(luò)的負(fù)載平衡和對(duì)信道接入?yún)f(xié)議的支持等因素。2分簇網(wǎng)絡(luò)的構(gòu)造和維護(hù)Adhoc網(wǎng)絡(luò)中分簇的概念最早是在分組無線網(wǎng)中提出的,當(dāng)時(shí)主要用于分級(jí)路由。隨著研究的不斷深入,迄今為止,已經(jīng)提出了大量的分簇算法來構(gòu)造和維護(hù)分簇網(wǎng)絡(luò)結(jié)構(gòu)?；诜执鼐W(wǎng)絡(luò),可以減少路由算法和洪泛廣播的開銷,能夠更加方便地管理移動(dòng)節(jié)點(diǎn)和控制信道接入,并可以提高網(wǎng)絡(luò)資源的使用效率。分簇算法的選擇依賴于應(yīng)用的需求、網(wǎng)絡(luò)的環(huán)境和節(jié)點(diǎn)的特征。不同的分簇算法具有不同的目標(biāo),包括最小化簇計(jì)算和維護(hù)開銷、最小化簇頭、最大化簇穩(wěn)定性和最大化節(jié)點(diǎn)生存時(shí)間等。以上的目標(biāo)存在矛盾,并且很多目標(biāo)及其組合都是NP完全問題,因此采用啟發(fā)式的分簇算法來尋求次優(yōu)解。2.1最小id啟發(fā)式算法鏈路分簇算法(LCA)是一種用于高頻特遣部隊(duì)(HFITF)通信網(wǎng)絡(luò)的分簇算法。LCA算法中,每個(gè)節(jié)點(diǎn)分配惟一的ID,鄰居節(jié)點(diǎn)中具有最高ID的節(jié)點(diǎn)成為簇頭,并且如果節(jié)點(diǎn)是它某個(gè)鄰居節(jié)點(diǎn)的ID最高的鄰居節(jié)點(diǎn),則它也成為簇頭。采用這種方法可以方便地構(gòu)造簇結(jié)構(gòu),但是它會(huì)產(chǎn)生過多的簇頭,特別是當(dāng)節(jié)點(diǎn)按ID線性遞增的順序排列時(shí)。最小ID啟發(fā)式算法對(duì)LCA算法進(jìn)行了改進(jìn)以減少簇頭的數(shù)量。該算法規(guī)定,相鄰節(jié)點(diǎn)中ID最小的節(jié)點(diǎn)作為簇頭,其1跳鄰居節(jié)點(diǎn)成為該簇頭所在簇的成員節(jié)點(diǎn),并不再參與簇頭選舉過程。此外,在某些特殊情況下,簇頭可以將其職責(zé)交付給其簇內(nèi)ID最小的成員節(jié)點(diǎn)。這種分簇算法計(jì)算簡單,實(shí)現(xiàn)方便,算法收斂較快。在移動(dòng)環(huán)境下,最小ID算法的簇頭更新頻率較慢,維護(hù)簇所需花費(fèi)的開銷較小。其缺點(diǎn)在于傾向選擇較小ID的節(jié)點(diǎn)作為簇頭,使這些節(jié)點(diǎn)消耗更多的電池能量,從而會(huì)減少整個(gè)網(wǎng)絡(luò)出現(xiàn)分割的時(shí)間,此外該算法沒有考慮負(fù)載平衡等因素。2.2凝膠電路節(jié)點(diǎn)的編碼最高節(jié)點(diǎn)度啟發(fā)式算法借鑒了Internet中選擇路由節(jié)點(diǎn)的方法,它的原則是盡量減少路由節(jié)點(diǎn)的數(shù)目,因此最高節(jié)點(diǎn)度啟發(fā)式算法的目標(biāo)是盡量減少簇的數(shù)目。每個(gè)節(jié)點(diǎn)通過交互控制消息獲悉鄰居節(jié)點(diǎn)的數(shù)目,然后將自己的度數(shù)向鄰居節(jié)點(diǎn)廣播。該節(jié)點(diǎn)和相鄰節(jié)點(diǎn)中最大度數(shù)的節(jié)點(diǎn)被選為簇頭,當(dāng)度數(shù)相同時(shí),則選擇ID最小的節(jié)點(diǎn)作為簇頭。簇頭的1跳鄰居節(jié)點(diǎn)則成為該簇的普通成員節(jié)點(diǎn),并不再參與簇的生成過程,重復(fù)以上過程直到所有節(jié)點(diǎn)都加入某個(gè)簇。該算法的優(yōu)點(diǎn)在于網(wǎng)絡(luò)中的簇的數(shù)目較少,源目的節(jié)點(diǎn)對(duì)之間的平均跳數(shù)較少,從而減少了分組投遞時(shí)延。但是由于簇的數(shù)目較少,信道的空間重用率較低。由于簇內(nèi)的節(jié)點(diǎn)數(shù)不受限制,并且簇中的資源通常由簇內(nèi)節(jié)點(diǎn)按照輪詢的方式共享,當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)量過多時(shí),每個(gè)節(jié)點(diǎn)的平均吞吐量將急劇下降。此外,當(dāng)節(jié)點(diǎn)移動(dòng)性較強(qiáng)時(shí),簇頭的更新頻率急劇上升,引入了大量的維護(hù)開銷。最高節(jié)點(diǎn)度算法比較適用于移動(dòng)性較弱并且節(jié)點(diǎn)密度較低的場(chǎng)合。2.3節(jié)點(diǎn)移動(dòng)方向量化為了適應(yīng)節(jié)點(diǎn)的移動(dòng)特性,提高簇結(jié)構(gòu)的穩(wěn)定性,可以根據(jù)節(jié)點(diǎn)的移動(dòng)性來為節(jié)點(diǎn)分配權(quán)重,并依據(jù)節(jié)點(diǎn)的權(quán)重來選舉簇頭。最低移動(dòng)性分簇算法中規(guī)定,節(jié)點(diǎn)的移動(dòng)性越高,其分配的權(quán)重越低,選擇鄰居節(jié)點(diǎn)中權(quán)重最高的節(jié)點(diǎn)作為簇頭。在基于節(jié)點(diǎn)移動(dòng)性的分簇算法中,需要一種機(jī)制來量化節(jié)點(diǎn)的移動(dòng)性。一種簡單的方法規(guī)定任何節(jié)點(diǎn)對(duì)的移動(dòng)性為它們相對(duì)速度絕對(duì)值的時(shí)間平均,但是這種方法需要通過GPS來獲得節(jié)點(diǎn)的位置。但是,并不是所有的環(huán)境都可以利用GPS,并且它不能真實(shí)地反映一個(gè)節(jié)點(diǎn)相對(duì)周圍鄰居節(jié)點(diǎn)的運(yùn)動(dòng)情況。為了能夠準(zhǔn)確刻畫節(jié)點(diǎn)的移動(dòng)性,文獻(xiàn)提出了一種聚集的本地移動(dòng)性指標(biāo),節(jié)點(diǎn)通過比較收到的來自某一鄰居節(jié)點(diǎn)的連續(xù)2次傳輸信號(hào)的強(qiáng)度來估計(jì)2個(gè)節(jié)點(diǎn)之間的相對(duì)移動(dòng)性。該移動(dòng)性指標(biāo)的計(jì)算不依賴與節(jié)點(diǎn)的位置信息,優(yōu)于單純的使用距離或速度的方法。在移動(dòng)性較強(qiáng)時(shí),最低移動(dòng)性分簇算法可以明顯減少簇頭的更新頻率,它的缺點(diǎn)在于節(jié)點(diǎn)權(quán)重的更新較頻繁,簇頭的計(jì)算開銷較大,并且也沒有考慮系統(tǒng)的負(fù)載平衡和節(jié)點(diǎn)的能量損耗。最低移動(dòng)性分簇算法和最小ID分簇算法適合于計(jì)算量小和復(fù)雜性高,并且不過多考慮負(fù)載平衡和節(jié)點(diǎn)能量耗費(fèi)的場(chǎng)合。2.4多通過織構(gòu)來提高簇頭負(fù)載穩(wěn)定性以上分簇算法大都傾向于選擇某些節(jié)點(diǎn)作為簇頭,使得這些節(jié)點(diǎn)的負(fù)擔(dān)較重,很容易耗盡能量。為此,需要在簇頭間實(shí)施負(fù)載平衡,使所有節(jié)點(diǎn)都可以較公平地充當(dāng)簇頭。而對(duì)于最高節(jié)點(diǎn)度算法,由于節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)經(jīng)常發(fā)生變化,簇頭的負(fù)載分布特性較好,但是簇結(jié)構(gòu)很不穩(wěn)定,需要設(shè)法提高簇結(jié)構(gòu)的穩(wěn)定性?；谝陨峡紤],通過對(duì)最小ID和最高節(jié)點(diǎn)度啟發(fā)式算法進(jìn)行改進(jìn)來實(shí)現(xiàn)負(fù)載平衡節(jié)點(diǎn)ID分簇算法和負(fù)載平衡節(jié)點(diǎn)度分簇算法。在負(fù)載平衡節(jié)點(diǎn)ID分簇算法中,限制簇頭的生存時(shí)間在一個(gè)預(yù)算值之內(nèi),如果節(jié)點(diǎn)充當(dāng)簇頭的時(shí)間超過預(yù)算值,該簇頭將其簇頭角色轉(zhuǎn)讓給其它節(jié)點(diǎn)。負(fù)載平衡節(jié)點(diǎn)度分簇算法中,節(jié)點(diǎn)只需保存2個(gè)本地變量:當(dāng)前的節(jié)點(diǎn)度和選舉度。選舉度表示該節(jié)點(diǎn)被選舉為簇頭時(shí)的節(jié)點(diǎn)度。算法運(yùn)行時(shí),節(jié)點(diǎn)將計(jì)算當(dāng)前節(jié)點(diǎn)度與選舉度之間的差值,如果差值的絕對(duì)值超過某一規(guī)定的門限值,則簇頭降級(jí)為普通節(jié)點(diǎn),從而提高了簇結(jié)構(gòu)的穩(wěn)定性。2.5引領(lǐng)網(wǎng)絡(luò)下多節(jié)點(diǎn)權(quán)值的分配以上算法中簇頭的選擇都只考慮了某個(gè)方面的因素,簇頭的選擇不夠優(yōu)化。首先,一個(gè)簇頭不能處理過多的節(jié)點(diǎn),即使這些節(jié)點(diǎn)都是其鄰居節(jié)點(diǎn)。例如,藍(lán)牙網(wǎng)絡(luò)中采用了主從模式,一個(gè)簇頭最多允許管理7個(gè)普通節(jié)點(diǎn)。其次,如果僅僅考慮最大化資源利用率,應(yīng)選擇最小的簇頭來覆蓋整個(gè)網(wǎng)絡(luò)范圍,但該系統(tǒng)中,當(dāng)簇頭移動(dòng)時(shí)需要選擇新的簇頭,并未考慮負(fù)載平衡,使得某些簇頭的負(fù)擔(dān)較重,成為網(wǎng)絡(luò)的瓶頸節(jié)點(diǎn)。因此簇頭的選舉對(duì)于網(wǎng)絡(luò)的性能至關(guān)重要,需要考慮多種因素,并基于網(wǎng)絡(luò)環(huán)境和業(yè)務(wù)需求進(jìn)行合理折衷。為此,可以采用一種組合的加權(quán)分簇算法。在這種算法中,每個(gè)節(jié)點(diǎn)分配一個(gè)權(quán)值指示該節(jié)點(diǎn)適合充當(dāng)簇頭的程度。各節(jié)點(diǎn)的權(quán)值可以使用一個(gè)考慮多種因素的通用公式表示:Weight=a*mobility+b*degree+c*power+d*energy-left。其中,參數(shù)a,b,c和d由應(yīng)用和網(wǎng)絡(luò)環(huán)境決定,Mobility表示節(jié)點(diǎn)的速度或相對(duì)鄰居節(jié)點(diǎn)的移動(dòng)性,degree表示節(jié)點(diǎn)度,power表示節(jié)點(diǎn)的傳輸功率、energy-left表示節(jié)點(diǎn)剩余的能量。此外,每個(gè)變量需要根據(jù)具體的應(yīng)用選用合適的單位,并且可以根據(jù)需要增加更多的變量。由于考慮了多種因素,通用組合加權(quán)分簇算法具有較強(qiáng)的適應(yīng)性和較廣泛的應(yīng)用場(chǎng)合。2.6打造有簇頭的分簇結(jié)構(gòu)在實(shí)現(xiàn)分簇算法時(shí),存在兩種觀點(diǎn):不選舉簇頭或者選舉簇頭。前者認(rèn)為簇頭需要承擔(dān)過重的任務(wù)而成為網(wǎng)絡(luò)的瓶頸節(jié)點(diǎn),當(dāng)簇頭出現(xiàn)故障時(shí),會(huì)嚴(yán)重影響網(wǎng)絡(luò)的性能。在無簇頭的簇結(jié)構(gòu)中,簇內(nèi)每個(gè)節(jié)點(diǎn)都需要維護(hù)簇內(nèi)和簇間的路由信息,當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí),業(yè)務(wù)量開銷急劇增加,并且由于沒有簇頭,不能充分利用簇結(jié)構(gòu)帶來的好處,如實(shí)施移動(dòng)管理和資源分配等。在有簇頭分簇結(jié)構(gòu)中,簇頭可以充當(dāng)簇內(nèi)的協(xié)調(diào)者,并可以和網(wǎng)關(guān)節(jié)點(diǎn)形成虛擬骨干網(wǎng)絡(luò),從而方便地實(shí)現(xiàn)分級(jí)路由、移動(dòng)管理和資源分配,特別當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí),可以減少維護(hù)簇結(jié)構(gòu)所需的控制開銷。但是由于簇頭不同于基站,它沒有特殊的硬件并且需要基于一定的算法動(dòng)態(tài)進(jìn)行選擇,因此分簇算法應(yīng)考慮簇頭的負(fù)載分布,盡可能防止簇頭成為瓶頸節(jié)點(diǎn)。前面討論的分簇算法基本上都是有簇頭的分簇算法,在網(wǎng)絡(luò)規(guī)模不大,節(jié)點(diǎn)密度較高并且節(jié)點(diǎn)的處理能力非常低的情況下,為了防止簇頭成為瓶頸節(jié)點(diǎn),可以考慮采用無簇頭分簇算法。文獻(xiàn)提出了一種分布式自適應(yīng)無簇頭算法。該分簇算法將網(wǎng)絡(luò)劃分為可以獨(dú)立進(jìn)行控制的多個(gè)分區(qū)。由于沒有簇頭,每個(gè)節(jié)點(diǎn)被同等對(duì)待,從而避免業(yè)務(wù)量瓶頸和易受攻擊的中心節(jié)點(diǎn)的產(chǎn)生,并且每個(gè)節(jié)點(diǎn)根據(jù)與簇內(nèi)其它節(jié)點(diǎn)的關(guān)系在簇間進(jìn)行轉(zhuǎn)移或生成新簇以維護(hù)簇結(jié)構(gòu)。2.7多跳簇分簇算法。u以上考慮的分簇算法產(chǎn)生的簇大都是1跳有頭簇或2跳無頭簇,這種分簇結(jié)構(gòu)相對(duì)簡單,但并不是最優(yōu)的簇結(jié)構(gòu)。簇的尺寸會(huì)影響基于簇的網(wǎng)絡(luò)協(xié)議的性能和控制開銷,例如簇內(nèi)節(jié)點(diǎn)數(shù)過多,將會(huì)導(dǎo)致簇頭負(fù)擔(dān)較重;簇內(nèi)節(jié)點(diǎn)數(shù)較少使得簇的數(shù)量較多,簇的維護(hù)開銷和分組投遞時(shí)延較大。因此需要通過某種方法來控制簇頭的密度和簇的數(shù)量,即根據(jù)節(jié)點(diǎn)的密度和數(shù)量來確定簇內(nèi)節(jié)點(diǎn)與簇頭的最大距離d。Max-Mind跳分簇算法是一種基于節(jié)點(diǎn)ID來選擇簇頭的多跳簇分簇算法,該算法可以有效減少簇頭數(shù)量,并在簇頭間提供較好的負(fù)載平衡能力。G.Chen等人也提出了一種基于連接度的k跳簇分簇算法。該算法將連接度作為第1指標(biāo)、而將節(jié)點(diǎn)ID作為第2指標(biāo)來選擇簇頭,目的是進(jìn)一步減少簇的數(shù)量。簇的尺寸一方面可以通過簇內(nèi)節(jié)點(diǎn)間的最大跳數(shù)加以約束,另外也可以通過限制簇內(nèi)節(jié)點(diǎn)數(shù)來實(shí)現(xiàn)。MMWN(MobileMultihopWirelessNetwork)體系結(jié)構(gòu)通過限制簇內(nèi)節(jié)點(diǎn)數(shù)來調(diào)節(jié)簇的尺寸。簇的分裂和合并由3個(gè)配置參數(shù)控制:分裂門限Nsplit,合并門限Nmerge和最佳尺寸Npref。如果一個(gè)簇的節(jié)點(diǎn)數(shù)超過Nsplit,那么將執(zhí)行分裂過程。當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)小于Nmerge時(shí),它可能與其相鄰簇合并,并盡量使新簇的尺寸接近Npref。多跳簇雖然可以減少簇的數(shù)量和分組的投遞時(shí)延,但是簇頭的負(fù)擔(dān)更重,簇結(jié)構(gòu)的維護(hù)可能更加復(fù)雜,特別在節(jié)點(diǎn)運(yùn)動(dòng)性較強(qiáng)的環(huán)境下。因此,需要根據(jù)節(jié)點(diǎn)的密度、數(shù)量、運(yùn)動(dòng)模式和業(yè)務(wù)的需求來確定簇的尺寸以優(yōu)化網(wǎng)絡(luò)的性能。2.8基于信道接入的被動(dòng)分簇算法上述算法可以看作主動(dòng)的分簇算法,因?yàn)樗鼈兓蛘呒僭O(shè)知道鄰居節(jié)點(diǎn)信息,或者通過周期地交換控制分組來獲得鄰居信息。在這些分簇算法中,節(jié)點(diǎn)即使沒有數(shù)據(jù)分組發(fā)送,也會(huì)引入大量控制開銷,特別當(dāng)節(jié)點(diǎn)的密度較高或者移動(dòng)性較強(qiáng)時(shí)。對(duì)于一些特殊的應(yīng)用場(chǎng)合,如軍事應(yīng)用和傳感器網(wǎng)絡(luò),周期性地控制分組會(huì)暴露節(jié)點(diǎn)位置、造成信息泄密及過多消耗傳感節(jié)點(diǎn)能量,從某種意義而言是不可取的。主動(dòng)分簇算法常假定在分簇形成過程和鄰居信息收集過程中,節(jié)點(diǎn)的拓?fù)洳话l(fā)生改變,并且可以獲得完整的鄰居節(jié)點(diǎn)信息。此外,這些分簇機(jī)制還會(huì)產(chǎn)生網(wǎng)絡(luò)分區(qū)。為了克服主動(dòng)分簇算法的缺陷,文獻(xiàn)提出了一種基于信道接入的被動(dòng)分簇算法(ABCA),簇的形成依賴于媒體接入控制協(xié)議(MAC)。所謂被動(dòng)分簇,是指分簇協(xié)議不使用專門的分簇控制消息,而是將分組的傳輸和分簇算法的實(shí)現(xiàn)緊密地結(jié)合在一起。ABCA不需要發(fā)送顯式的分簇消息,而是將與分簇相關(guān)的狀態(tài)信息附加到數(shù)據(jù)分組中,從而引入更少的控制開銷,并具有較穩(wěn)定的簇結(jié)構(gòu)。在簇形成過程中,每個(gè)節(jié)點(diǎn)都試圖接入信道來聲明自己是簇頭,一個(gè)節(jié)點(diǎn)如果在它的所有鄰居節(jié)點(diǎn)中最先成功地發(fā)送了簇頭聲明控制消息,那么它將成為簇頭,即按照“最先聲明優(yōu)先”的規(guī)則來選舉簇頭。收到簇頭聲明消息,自己還沒有成為簇頭的節(jié)點(diǎn)將成為該簇頭的成員節(jié)點(diǎn)。一旦一個(gè)節(jié)點(diǎn)成為簇頭并且它至少有一個(gè)成員節(jié)點(diǎn),它將一直充當(dāng)簇頭直到離開網(wǎng)絡(luò)或者出現(xiàn)故障。當(dāng)一個(gè)節(jié)點(diǎn)剛剛加入網(wǎng)絡(luò)或想改變簇時(shí),可以根據(jù)接收到的簇頭聲明消息來加入一個(gè)鄰居簇。被動(dòng)分簇的開銷較小,但它得到的分簇結(jié)構(gòu)是用戶數(shù)據(jù)傳輸?shù)母碑a(chǎn)品,如果節(jié)點(diǎn)不發(fā)送數(shù)據(jù)則不能形成簇結(jié)構(gòu)。并且產(chǎn)生的簇的隨機(jī)性較大,簇結(jié)構(gòu)不夠優(yōu)化并不易控制。因此,這種被動(dòng)分簇多用于提高廣播協(xié)議的效率和某些特殊的場(chǎng)合。綜上所述,不同的分簇算法有不同的使用場(chǎng)合。最小ID分簇算法實(shí)現(xiàn)簡單,但是考慮的因素較少,