分簇技術(shù)的研究綜述

０引言近些年來，小型無人機(jī)在軍事作戰(zhàn)中顯示出極大的優(yōu)越性，“無人、分布、協(xié)同”是其三大顯著特征。在戰(zhàn)場(chǎng)上，無人機(jī)配合重型武器常能達(dá)到出其不意、攻其不備的效果。通過無人機(jī)蜂群的靈活性，精準(zhǔn)打擊，降低我方傷亡風(fēng)險(xiǎn)。但如何控制數(shù)量眾多的無人機(jī)一直是研究的重點(diǎn)。不僅是在軍事作戰(zhàn)中，使用分簇算法去管理大規(guī)模的網(wǎng)絡(luò)一直是有效可行的方法。在分簇結(jié)構(gòu)下網(wǎng)絡(luò)規(guī)模是不受限制的，具有更好的可擴(kuò)充性，并且路由開銷會(huì)相對(duì)小一些。網(wǎng)絡(luò)中節(jié)點(diǎn)被劃分為多個(gè)簇，每個(gè)簇里都有簇首和簇成員，簇首維護(hù)和管理自己簇內(nèi)的節(jié)點(diǎn)，負(fù)責(zé)簇內(nèi)節(jié)點(diǎn)的通信，并為簇群之間的通信提供路由信息和尋找合適的路徑。1拓?fù)浣Y(jié)構(gòu)分類AdHoc網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有不同的分類，研究者們習(xí)慣于將其分為平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)[2]。如圖1所示，平面結(jié)構(gòu)的網(wǎng)絡(luò)復(fù)雜度較低，其中的網(wǎng)絡(luò)節(jié)點(diǎn)具有相同的地位和功能，各節(jié)點(diǎn)之間相互協(xié)同合作完成通信，所以又稱為對(duì)等式平面結(jié)構(gòu)。圖1平面結(jié)構(gòu)的AdHoc網(wǎng)絡(luò)如今，因?yàn)椴煌娜蝿?wù)需求，網(wǎng)絡(luò)不斷的開發(fā)，規(guī)模也越來越大，網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量也隨著越來越多。每個(gè)節(jié)點(diǎn)都互相交互信息去維護(hù)網(wǎng)絡(luò)里所有的拓?fù)湫畔?，無疑會(huì)增加網(wǎng)絡(luò)開銷。但是在網(wǎng)絡(luò)復(fù)雜度更高的分級(jí)結(jié)構(gòu)中，根據(jù)分簇算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分進(jìn)不同的簇，每個(gè)簇由一個(gè)簇首、多個(gè)簇成員和網(wǎng)關(guān)節(jié)點(diǎn)組成，不同節(jié)點(diǎn)被賦予不同的功能。簇首形成高一級(jí)網(wǎng)絡(luò)，分別負(fù)責(zé)不同簇內(nèi)節(jié)點(diǎn)之間的通信，并提供路由信息和發(fā)現(xiàn)合適的路徑，方便簇間節(jié)點(diǎn)通信。分級(jí)結(jié)構(gòu)又可以被繼續(xù)劃分為單頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)和多頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)，如圖2所示。在單頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都使用相同的頻率通信，通過網(wǎng)關(guān)節(jié)點(diǎn)能夠?qū)崿F(xiàn)簇首節(jié)點(diǎn)之間的通信。與單頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)不同，在多頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)中，節(jié)點(diǎn)級(jí)別決定了節(jié)點(diǎn)的通信頻率，級(jí)別不同的節(jié)點(diǎn)采用不同的通信頻率，高級(jí)節(jié)點(diǎn)的通信范圍大于低級(jí)節(jié)點(diǎn)，簇首節(jié)點(diǎn)可以使用兩種不同的頻率，一個(gè)用來維持與其他簇首節(jié)點(diǎn)之間的通信，另一個(gè)頻率用來與本簇內(nèi)的簇成員通信。

（a）單頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)（b）多頻分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)圖2分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)對(duì)等式平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)都不是完美的，各有優(yōu)缺點(diǎn)：對(duì)等式平面結(jié)構(gòu)網(wǎng)絡(luò)的優(yōu)勢(shì)是其相對(duì)而言比較簡(jiǎn)單，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的地位都相同，沒有上下級(jí)之分。在通信時(shí)，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的通信路徑有很多，可以避免網(wǎng)絡(luò)瓶頸擁塞的問題，網(wǎng)絡(luò)的安全系數(shù)也相對(duì)較高。就網(wǎng)絡(luò)規(guī)模來看，對(duì)等式平面結(jié)構(gòu)網(wǎng)絡(luò)規(guī)模較小，且當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)無法解決路由維護(hù)開銷和帶寬消耗之間的矛盾。相對(duì)而言，分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)的復(fù)雜度更高，網(wǎng)絡(luò)規(guī)模不受限，具有良好的可擴(kuò)展性，在對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)分簇的情況下，可以相對(duì)降低網(wǎng)絡(luò)路由的開銷。當(dāng)下AdHoc網(wǎng)絡(luò)正逐漸呈現(xiàn)出分級(jí)化的趨勢(shì)，許多網(wǎng)絡(luò)路由算法也基于分級(jí)結(jié)構(gòu)的網(wǎng)絡(luò)模式被提出和改進(jìn)。為了更清晰地理解這兩種分類各自的特點(diǎn)，將平面路由和分簇路由的特點(diǎn)進(jìn)行宏觀比較，見表1。表1平面路由與分簇路由特點(diǎn)比較２不同分簇方案分簇是將移動(dòng)節(jié)點(diǎn)劃分為不同的虛擬群組的過程。如圖3所示，分簇方案需要考慮多個(gè)方面，如網(wǎng)絡(luò)的用途、所處的環(huán)境、規(guī)模等各個(gè)方面。分簇的過程可分為主動(dòng)、反應(yīng)式和兩者兼而有之的混合分簇。簇內(nèi)的節(jié)點(diǎn)也根據(jù)其功能進(jìn)行分類，如簇首、簇成員和網(wǎng)關(guān)節(jié)點(diǎn)。簇首的職責(zé)是管理簇成員，處理簇間的通信和向基站的數(shù)據(jù)傳輸。同時(shí)處在多個(gè)簇首傳輸范圍內(nèi)的節(jié)點(diǎn)，我們將其稱為網(wǎng)關(guān)節(jié)點(diǎn)。網(wǎng)關(guān)節(jié)點(diǎn)的用處是幫助相鄰簇之間轉(zhuǎn)發(fā)數(shù)據(jù)。除了網(wǎng)關(guān)和簇首之外的任何其他節(jié)點(diǎn)都是成員節(jié)點(diǎn)，也稱為普通節(jié)點(diǎn)。在簇首選擇過程中，確定了網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量、相對(duì)移動(dòng)性、可靠性、通信工作量等重要參數(shù)。圖3分簇方案３在無線傳感器網(wǎng)絡(luò)中的應(yīng)用在無線傳感器網(wǎng)絡(luò)（WirelessSensorNetworks，WSN）中，基于分簇的模型具有較好的節(jié)能效果。然而，在動(dòng)態(tài)環(huán)境中管理簇內(nèi)的節(jié)點(diǎn)是一個(gè)開放的挑戰(zhàn)。選擇簇首（ClusterHead，CH）無疑是分簇過程中的要點(diǎn)和難點(diǎn)，要考慮諸多因素是否會(huì)影響網(wǎng)絡(luò)性能。雖然已有一些研究提出了CH選擇方法，但大多數(shù)都不適合動(dòng)態(tài)分簇環(huán)境。針對(duì)這一問題，有的研究員提出了基于模糊邏輯、遺傳算法和神經(jīng)網(wǎng)絡(luò)的智能算法。然而，這些算法在單跳分簇模型框架中工作得更好，在多跳分簇環(huán)境中，網(wǎng)絡(luò)生存期是一個(gè)大問題。文獻(xiàn)提出了一種基于遺傳算法的單跳和多跳分簇模型的CH選擇方法。該方法旨在滿足動(dòng)態(tài)環(huán)境的要求，基于六個(gè)主要特征選舉CH，即剩余的能量、消耗能量、附近的鄰居的數(shù)量、能量感知距離、節(jié)點(diǎn)的魯棒性和節(jié)點(diǎn)遷移度。文章提出的算法經(jīng)實(shí)驗(yàn)結(jié)果表明，大大延長(zhǎng)了網(wǎng)絡(luò)壽命。文獻(xiàn)提出的是一個(gè)基于網(wǎng)格結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)分簇路由算法。根據(jù)面積大小和傳輸范圍，計(jì)算出合適的網(wǎng)格大小，構(gòu)造出虛擬網(wǎng)格結(jié)構(gòu)。在每個(gè)網(wǎng)格中，根據(jù)到網(wǎng)格中點(diǎn)的最近距離選擇一個(gè)簇首。為了在網(wǎng)格中轉(zhuǎn)發(fā)數(shù)據(jù)，遵循局部單通路策略。為了將數(shù)據(jù)從簇首轉(zhuǎn)發(fā)到接收點(diǎn)，實(shí)現(xiàn)了基于角的傾向的組合路由模型。在數(shù)據(jù)收集、目標(biāo)監(jiān)控以及應(yīng)用在無線傳感器網(wǎng)絡(luò)等方面，蜂群無人機(jī)得到了越來越廣泛的應(yīng)用。在無線傳感器領(lǐng)域，無人機(jī)被用來創(chuàng)建一個(gè)更靈活的數(shù)據(jù)收集平臺(tái)。這種集成通過優(yōu)化能量預(yù)算，使WSN的壽命最大化。在文獻(xiàn)中，作者利用無人機(jī)的這些優(yōu)點(diǎn)，提出了一種最優(yōu)簇首選擇策略來最大化WSNs的生存期。該方法利用無人機(jī)各傳感器節(jié)點(diǎn)的平均剩余能量、信道條件和歐氏距離來確定一組CHs。與現(xiàn)有的解決方案相比，該方法能夠最大限度地提高無線傳感器網(wǎng)絡(luò)的壽命。４在自組織網(wǎng)絡(luò)中的應(yīng)用分簇算法在車載自組網(wǎng)中一樣得到了應(yīng)用。文獻(xiàn)選擇最接近集群中心地理位置的車輛作為簇首，從簇首的一跳鄰居集中選擇向同一方向移動(dòng)的節(jié)點(diǎn)作為簇成員。由于節(jié)點(diǎn)的移動(dòng)性，MANET中的網(wǎng)絡(luò)拓?fù)渥兓诸l繁。當(dāng)一個(gè)節(jié)點(diǎn)的遷移信息被共享給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)時(shí)，拓?fù)渚S護(hù)會(huì)產(chǎn)生額外的開銷。為了解決MANET中的拓?fù)渚S護(hù)開銷問題，研究人員提出了不同的基于簇群的算法來減小路由表的大小。簇的形成是為了局部地調(diào)整簇內(nèi)的拓?fù)渥兓Ｈ绻粋€(gè)節(jié)點(diǎn)希望與簇群外部的節(jié)點(diǎn)通信，那么它只與自己的簇首通信。CH與其他CHs通信，將數(shù)據(jù)傳輸?shù)侥康牡?。為了有效地利用MANET中的分簇機(jī)制，需要穩(wěn)定、均衡的簇群。一些度量指標(biāo)有助于優(yōu)化且形成質(zhì)量良好的簇群，如相對(duì)移動(dòng)性（節(jié)點(diǎn)速度、方向等）、節(jié)點(diǎn)度、剩余能量、通信工作量和鄰居節(jié)點(diǎn)的性能。文獻(xiàn)總結(jié)了近年來MANET的分簇情況，還介紹了最近研究的目的、目標(biāo)和貢獻(xiàn)。同時(shí)，對(duì)研究結(jié)果、面臨的挑戰(zhàn)和未來的發(fā)展方向進(jìn)行了闡述。傳統(tǒng)的AdHoc路由協(xié)議在機(jī)載網(wǎng)絡(luò)中由于飛機(jī)的運(yùn)動(dòng)而面臨挑戰(zhàn)，經(jīng)常導(dǎo)致鏈路中斷，鏈路重新建立的過程不可避免地會(huì)引起拓?fù)浣Y(jié)構(gòu)的變化。針對(duì)這些問題，文獻(xiàn)中作者利用了能夠安裝在無人機(jī)上或懸停的飛機(jī)上的網(wǎng)狀路由器。由于這些網(wǎng)格點(diǎn)之間通常具有相對(duì)穩(wěn)定的連接，所以它們起到簇首的作用，形成分層的路由結(jié)構(gòu)。在分簇管理中引入一個(gè)簡(jiǎn)單的自組織規(guī)則來限制簇群控制開銷和路由發(fā)現(xiàn)洪泛。此外，路由協(xié)議中還可以部署容錯(cuò)機(jī)制（DynamicTurnManagement，DTM），提高對(duì)臨時(shí)鏈路或節(jié)點(diǎn)故障的彈性。文獻(xiàn)提出了一種新的基于全球定位系統(tǒng)（GlobalPositioningSystem，GPS）的自組網(wǎng)路由協(xié)議——基于區(qū)域的分層鏈路狀態(tài)（zone-basedtwo-levellinkstate，ZHLS）路由協(xié)議。在該協(xié)議中，網(wǎng)絡(luò)被劃分為多個(gè)區(qū)域而且每個(gè)區(qū)域之間互不重疊。每個(gè)節(jié)點(diǎn)只知道其區(qū)域內(nèi)的節(jié)點(diǎn)連接和整個(gè)網(wǎng)絡(luò)的區(qū)域連接。鏈路狀態(tài)路由在本地節(jié)點(diǎn)和全局區(qū)域兩個(gè)級(jí)別上執(zhí)行。與其他分層協(xié)議不同的是，這個(gè)協(xié)議中沒有簇首節(jié)點(diǎn)。區(qū)域級(jí)拓?fù)湫畔⒎植嫉剿泄?jié)點(diǎn)。這種點(diǎn)對(duì)點(diǎn)方式緩解了流量瓶頸，避免了單點(diǎn)故障，簡(jiǎn)化了移動(dòng)管理。由于只需要目的地的區(qū)域ID和節(jié)點(diǎn)ID進(jìn)行路由，因此從源到目的地的路由可以適應(yīng)不斷變化的拓?fù)浣Y(jié)構(gòu)。通過向每個(gè)區(qū)域發(fā)送一個(gè)位置請(qǐng)求，就可以找到目的地的區(qū)域ID。位置搜索方案比基于洪泛的方案產(chǎn)生更少的開銷。在該協(xié)議中創(chuàng)建和維護(hù)拓?fù)涞耐ㄐ砰_銷要小于平面LSR協(xié)議。這種新的路由協(xié)議提供了一種靈活、高效和有效的方法來適應(yīng)無線網(wǎng)絡(luò)環(huán)境中不斷變化的拓?fù)浣Y(jié)構(gòu)。最近的研究活動(dòng)已經(jīng)認(rèn)識(shí)到節(jié)點(diǎn)移動(dòng)性對(duì)于在移動(dòng)自組網(wǎng)中創(chuàng)建性能良好的、穩(wěn)定的、可伸縮和自適應(yīng)群的重要性。文獻(xiàn)提出了一種基于群遷移率的分布式分簇算法（Groupmobilitybasedclustering），并根據(jù)節(jié)點(diǎn)的瞬時(shí)速度和方向推導(dǎo)出一種修正的群遷移率度量。我們的動(dòng)態(tài)分布式分簇方法使用高斯馬爾可夫群遷移率模型進(jìn)行遷移率預(yù)測(cè)，使每個(gè)節(jié)點(diǎn)能夠預(yù)測(cè)其相對(duì)于鄰居的遷移率。簇首具有相對(duì)較低的遷移率、較大的能量?jī)?chǔ)備和較高的連通性。特別適用于反映移動(dòng)群體普遍存在的群組分離和融合行為的群體移動(dòng)模式。我們還考慮了節(jié)點(diǎn)的剩余能量以及相鄰節(jié)點(diǎn)的數(shù)目，提出的聚類方案旨在通過減少分簇迭代來形成穩(wěn)定的簇群。仿真結(jié)果表明，比較平均簇首變化數(shù)時(shí)，該框架的性能優(yōu)于兩種著名的聚類方法MOBIC和DGMA。節(jié)點(diǎn)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和移動(dòng)特性可能會(huì)對(duì)連通性和路由造成挑戰(zhàn)。針對(duì)大型的移動(dòng)自組網(wǎng)，各種各樣的分簇方案是可以根據(jù)網(wǎng)絡(luò)拓?fù)渥兓瘉碇匦聝?yōu)化組織網(wǎng)絡(luò)的有效方法之一。在文獻(xiàn)中，作者提出了一種基于區(qū)域群移動(dòng)性的自組織分簇（Self-OrganizationBasedClustering）方案來提高整個(gè)網(wǎng)絡(luò)的可擴(kuò)展性和穩(wěn)定性。該算法利用鳥類群集的生物啟發(fā)行為研究，以形成和維持MANET的分群。提出了一種動(dòng)態(tài)的考慮簇大小的管理機(jī)制，以減少網(wǎng)絡(luò)擁塞，提高M(jìn)ANET在群組移動(dòng)性能方面的性能。為了合理利用資源，降低額外的能耗，提出了一種合理處理孤立節(jié)點(diǎn)的算法。根據(jù)節(jié)點(diǎn)接收信號(hào)的強(qiáng)弱將節(jié)點(diǎn)進(jìn)行分區(qū)，簇內(nèi)結(jié)構(gòu)被分為三種不同類型的區(qū)域：簇首、節(jié)點(diǎn)吸引區(qū)域和節(jié)點(diǎn)排斥區(qū)域。算法流程包括節(jié)點(diǎn)狀態(tài)識(shí)別、簇首選擇以及孤立節(jié)點(diǎn)處理。仿真結(jié)果表明，文獻(xiàn)中提出的改進(jìn)算法有效降低了網(wǎng)絡(luò)的能耗開銷，提高了網(wǎng)絡(luò)中節(jié)點(diǎn)的生存時(shí)間，使網(wǎng)絡(luò)結(jié)構(gòu)更加穩(wěn)定具有較強(qiáng)的魯棒性。近年來，就小型無人機(jī)廣泛應(yīng)用的優(yōu)勢(shì)來說，基于通信網(wǎng)絡(luò)的合作可以有效地?cái)U(kuò)大無人機(jī)的工作范圍。雖然無人機(jī)網(wǎng)絡(luò)與傳統(tǒng)的移動(dòng)自組織網(wǎng)絡(luò)非常相似，但是相關(guān)文獻(xiàn)中并沒有考慮到無人機(jī)應(yīng)用場(chǎng)景的特殊性。針對(duì)無人機(jī)網(wǎng)絡(luò)的應(yīng)用特點(diǎn)，文獻(xiàn)[14]提出了一種適用動(dòng)態(tài)網(wǎng)絡(luò)的分布式網(wǎng)關(guān)選擇算法。該算法通過將網(wǎng)絡(luò)劃分成多個(gè)子區(qū)域來減弱信息不對(duì)稱現(xiàn)象對(duì)無人機(jī)拓?fù)淇刂频挠绊?。在網(wǎng)絡(luò)運(yùn)行過程中，即使無人機(jī)移動(dòng)速度較快，也可以通過自適應(yīng)調(diào)整網(wǎng)絡(luò)的分區(qū)來保持整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的穩(wěn)定。同時(shí)，可以完全控制網(wǎng)關(guān)的數(shù)量，每個(gè)子區(qū)域的大小可以根據(jù)目標(biāo)的分布進(jìn)行調(diào)整。特別是定義了無人機(jī)網(wǎng)絡(luò)的穩(wěn)定性，建立了網(wǎng)絡(luò)劃分模型，設(shè)計(jì)了分布式網(wǎng)關(guān)選擇算法。仿真結(jié)果表明，在該方案中，不管節(jié)點(diǎn)移動(dòng)速度變慢或變快，拓?fù)浣Y(jié)構(gòu)都能相對(duì)保持穩(wěn)定，所以這個(gè)方案十分適用于無人機(jī)組成的移動(dòng)自組網(wǎng)。隨著無人機(jī)的廣泛應(yīng)用，迫切需要構(gòu)建無人機(jī)組網(wǎng)網(wǎng)絡(luò)以提高整體作戰(zhàn)效率，其中應(yīng)采用移動(dòng)自組網(wǎng)架構(gòu)。在文獻(xiàn)中，作者提出一種新的路由協(xié)議來解決無人機(jī)編隊(duì)網(wǎng)絡(luò)中的路由問題，稱為基于簇群的位置輔助動(dòng)態(tài)源路由協(xié)議（Cluster-BasedLocation-AidedRoutingProtocol，CBLADSR）。CBLADSR以形成穩(wěn)定的無人機(jī)機(jī)群集群結(jié)構(gòu)為基礎(chǔ)，利用無人機(jī)的地理位置進(jìn)行航路發(fā)現(xiàn)和航路維護(hù)。分簇過程采用節(jié)點(diǎn)權(quán)重啟發(fā)式算法選擇簇首，形成簇。路由過程是由簇內(nèi)路由和簇間路由的組合而成，分別采用短程傳輸和遠(yuǎn)程傳輸。CBLADSR采用基于斜率的轉(zhuǎn)發(fā)策略，在鄰居節(jié)點(diǎn)中，選擇其中斜率最小的作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。仿真結(jié)果