分簇技術的研究綜述*

孫一凡，米志超，王 海，蘆方旭，趙 寧

（1.陸軍工程大學 電子與信息工程學院，江蘇 南京 210007；2.中國電子科技集團公司第二十八研究所，江蘇 南京 210007）

0 引言

近些年來，小型無人機在軍事作戰中顯示出極大的優越性，“無人、分布、協同”是其三大顯著特征[1]。在戰場上，無人機配合重型武器常能達到出其不意、攻其不備的效果。通過無人機蜂群的靈活性，精準打擊，降低我方傷亡風險。但如何控制數量眾多的無人機一直是研究的重點。不僅是在軍事作戰中，使用分簇算法去管理大規模的網絡一直是有效可行的方法。在分簇結構下網絡規模是不受限制的，具有更好的可擴充性，并且路由開銷會相對小一些。網絡中節點被劃分為多個簇，每個簇里都有簇首和簇成員，簇首維護和管理自己簇內的節點，負責簇內節點的通信，并為簇群之間的通信提供路由信息和尋找合適的路徑。

1 拓撲結構分類

Ad Hoc 網絡的拓撲結構有不同的分類，研究者們習慣于將其分為平面結構和分級結構[2]。如圖1 所示，平面結構的網絡復雜度較低，其中的網絡節點具有相同的地位和功能，各節點之間相互協同合作完成通信，所以又稱為對等式平面結構。

圖1 平面結構的Ad Hoc 網絡

如今，因為不同的任務需求，網絡不斷的開發，規模也越來越大，網絡中的節點數量也隨著越來越多。每個節點都互相交互信息去維護網絡里所有的拓撲信息，無疑會增加網絡開銷。但是在網絡復雜度更高的分級結構中，根據分簇算法將網絡中的節點劃分進不同的簇，每個簇由一個簇首、多個簇成員和網關節點組成，不同節點被賦予不同的功能。簇首形成高一級網絡，分別負責不同簇內節點之間的通信，并提供路由信息和發現合適的路徑，方便簇間節點通信。分級結構又可以被繼續劃分為單頻分級結構網絡和多頻分級結構網絡，如圖2 所示。在單頻分級結構網絡中，所有節點都使用相同的頻率通信，通過網關節點能夠實現簇首節點之間的通信。與單頻分級結構網絡不同，在多頻分級結構網絡中，節點級別決定了節點的通信頻率，級別不同的節點采用不同的通信頻率，高級節點的通信范圍大于低級節點，簇首節點可以使用兩種不同的頻率，一個用來維持與其他簇首節點之間的通信，另一個頻率用來與本簇內的簇成員通信。

對等式平面結構和分級結構都不是完美的，各有優缺點：對等式平面結構網絡的優勢是其相對而言比較簡單，網絡中所有節點的地位都相同，沒有上下級之分。在通信時，源節點與目的節點之間的通信路徑有很多，可以避免網絡瓶頸擁塞的問題，網絡的安全系數也相對較高。就網絡規模來看，對等式平面結構網絡規模較小，且當網絡規模擴大時無法解決路由維護開銷和帶寬消耗之間的矛盾。相對而言，分級結構網絡的復雜度更高，網絡規模不受限，具有良好的可擴展性，在對網絡節點分簇的情況下，可以相對降低網絡路由的開銷。

圖2 分級結構網絡

當下Ad Hoc 網絡正逐漸呈現出分級化的趨勢，許多網絡路由算法也基于分級結構的網絡模式被提出和改進。為了更清晰地理解這兩種分類各自的特點，將平面路由和分簇路由的特點進行宏觀比較，見表1。

2 不同分簇方案

分簇是將移動節點劃分為不同的虛擬群組的過程[3]。如圖3 所示，分簇方案需要考慮多個方面，如網絡的用途、所處的環境、規模等各個方面。分簇的過程可分為主動、反應式和兩者兼而有之的混合分簇。簇內的節點也根據其功能進行分類，如簇首、簇成員和網關節點。簇首的職責是管理簇成員，處理簇間的通信和向基站的數據傳輸。同時處在多個簇首傳輸范圍內的節點，我們將其稱為網關節點。網關節點的用處是幫助相鄰簇之間轉發數據。除了網關和簇首之外的任何其他節點都是成員節點，也稱為普通節點。在簇首選擇過程中，確定了網絡節點的剩余能量、相對移動性、可靠性、通信工作量等重要參數[4]。

表1 平面路由與分簇路由特點比較

圖3 分簇方案

3 在無線傳感器網絡中的應用

在無線傳感器網絡（Wireless Sensor Networks，WSN）中，基于分簇的模型具有較好的節能效果。然而，在動態環境中管理簇內的節點是一個開放的挑戰。選擇簇首（Cluster Head，CH）無疑是分簇過程中的要點和難點，要考慮諸多因素是否會影響網絡性能。雖然已有一些研究提出了CH 選擇方法，但大多數都不適合動態分簇環境。針對這一問題，有的研究員提出了基于模糊邏輯、遺傳算法和神經網絡的智能算法。然而，這些算法在單跳分簇模型框架中工作得更好，在多跳分簇環境中，網絡生存期是一個大問題。文獻[5]提出了一種基于遺傳算法的單跳和多跳分簇模型的CH 選擇方法。該方法旨在滿足動態環境的要求，基于六個主要特征選舉CH，即剩余的能量、消耗能量、附近的鄰居的數量、能量感知距離、節點的魯棒性和節點遷移度。文章提出的算法經實驗結果表明，大大延長了網絡壽命。

文獻[6]提出的是一個基于網格結構的無線傳感器網絡分簇路由算法。根據面積大小和傳輸范圍，計算出合適的網格大小，構造出虛擬網格結構。在每個網格中，根據到網格中點的最近距離選擇一個簇首。為了在網格中轉發數據，遵循局部單通路策略。為了將數據從簇首轉發到接收點，實現了基于角的傾向的組合路由模型。在數據收集、目標監控以及應用在無線傳感器網絡等方面，蜂群無人機得到了越來越廣泛的應用。在無線傳感器領域，無人機被用來創建一個更靈活的數據收集平臺。這種集成通過優化能量預算，使WSN 的壽命最大化。在文獻[7]中，作者利用無人機的這些優點，提出了一種最優簇首選擇策略來最大化WSNs 的生存期。該方法利用無人機各傳感器節點的平均剩余能量、信道條件和歐氏距離來確定一組CHs。與現有的解決方案相比，該方法能夠最大限度地提高無線傳感器網絡的壽命。

4 在自組織網絡中的應用

分簇算法在車載自組網中一樣得到了應用。文獻[8]選擇最接近集群中心地理位置的車輛作為簇首，從簇首的一跳鄰居集中選擇向同一方向移動的節點作為簇成員。

由于節點的移動性，MANET 中的網絡拓撲變化十分頻繁。當一個節點的遷移信息被共享給網絡中的所有節點時，拓撲維護會產生額外的開銷。為了解決MANET 中的拓撲維護開銷問題，研究人員提出了不同的基于簇群的算法來減小路由表的大小。簇的形成是為了局部地調整簇內的拓撲變化。如果一個節點希望與簇群外部的節點通信，那么它只與自己的簇首通信。CH 與其他CHs 通信，將數據傳輸到目的地。為了有效地利用MANET 中的分簇機制，需要穩定、均衡的簇群。一些度量指標有助于優化且形成質量良好的簇群，如相對移動性（節點速度、方向等）、節點度、剩余能量、通信工作量和鄰居節點的性能。文獻[9]總結了近年來MANET 的分簇情況，還介紹了最近研究的目的、目標和貢獻。同時，對研究結果、面臨的挑戰和未來的發展方向進行了闡述。

傳統的Ad Hoc 路由協議在機載網絡中由于飛機的運動而面臨挑戰，經常導致鏈路中斷，鏈路重新建立的過程不可避免地會引起拓撲結構的變化。針對這些問題，文獻[10]中作者利用了能夠安裝在無人機上或懸停的飛機上的網狀路由器。由于這些網格點之間通常具有相對穩定的連接，所以它們起到簇首的作用，形成分層的路由結構。在分簇管理中引入一個簡單的自組織規則來限制簇群控制開銷和路由發現洪泛。此外，路由協議中還可以部署容錯機制（Dynamic Turn Management，DTM），提高對臨時鏈路或節點故障的彈性。

文獻[11]提出了一種新的基于全球定位系統（Global Positioning System，GPS）的自組網路由協議——基于區域的分層鏈路狀態（zone-based two-level link state，ZHLS）路由協議。在該協議中，網絡被劃分為多個區域而且每個區域之間互不重疊。每個節點只知道其區域內的節點連接和整個網絡的區域連接。鏈路狀態路由在本地節點和全局區域兩個級別上執行。與其他分層協議不同的是，這個協議中沒有簇首節點。區域級拓撲信息分布到所有節點。這種點對點方式緩解了流量瓶頸，避免了單點故障，簡化了移動管理。由于只需要目的地的區域ID 和節點ID 進行路由，因此從源到目的地的路由可以適應不斷變化的拓撲結構。通過向每個區域發送一個位置請求，就可以找到目的地的區域ID。位置搜索方案比基于洪泛的方案產生更少的開銷。在該協議中創建和維護拓撲的通信開銷要小于平面LSR 協議。這種新的路由協議提供了一種靈活、高效和有效的方法來適應無線網絡環境中不斷變化的拓撲結構。

最近的研究活動已經認識到節點移動性對于在移動自組網中創建性能良好的、穩定的、可伸縮和自適應群的重要性。文獻[12]提出了一種基于群遷移率的分布式分簇算法（Group mobility based clustering），并根據節點的瞬時速度和方向推導出一種修正的群遷移率度量。我們的動態分布式分簇方法使用高斯馬爾可夫群遷移率模型進行遷移率預測，使每個節點能夠預測其相對于鄰居的遷移率。簇首具有相對較低的遷移率、較大的能量儲備和較高的連通性。特別適用于反映移動群體普遍存在的群組分離和融合行為的群體移動模式。我們還考慮了節點的剩余能量以及相鄰節點的數目，提出的聚類方案旨在通過減少分簇迭代來形成穩定的簇群。仿真結果表明，比較平均簇首變化數時，該框架的性能優于兩種著名的聚類方法MOBIC和DGMA。

節點的動態網絡拓撲結構和移動特性可能會對連通性和路由造成挑戰。針對大型的移動自組網，各種各樣的分簇方案是可以根據網絡拓撲變化來重新優化組織網絡的有效方法之一。在文獻[13]中，作者提出了一種基于區域群移動性的自組織分簇（Self-Organization Based Clustering）方案來提高整個網絡的可擴展性和穩定性。該算法利用鳥類群集的生物啟發行為研究，以形成和維持MANET 的分群。提出了一種動態的考慮簇大小的管理機制，以減少網絡擁塞，提高MANET 在群組移動性能方面的性能。為了合理利用資源，降低額外的能耗，提出了一種合理處理孤立節點的算法。根據節點接收信號的強弱將節點進行分區，簇內結構被分為三種不同類型的區域：簇首、節點吸引區域和節點排斥區域。算法流程包括節點狀態識別、簇首選擇以及孤立節點處理。仿真結果表明，文獻中提出的改進算法有效降低了網絡的能耗開銷，提高了網絡中節點的生存時間，使網絡結構更加穩定具有較強的魯棒性。

近年來，就小型無人機廣泛應用的優勢來說，基于通信網絡的合作可以有效地擴大無人機的工作范圍。雖然無人機網絡與傳統的移動自組織網絡非常相似，但是相關文獻中并沒有考慮到無人機應用場景的特殊性。針對無人機網絡的應用特點，文獻[14]提出了一種適用動態網絡的分布式網關選擇算法。該算法通過將網絡劃分成多個子區域來減弱信息不對稱現象對無人機拓撲控制的影響。在網絡運行過程中，即使無人機移動速度較快，也可以通過自適應調整網絡的分區來保持整個網絡拓撲結構的穩定。同時，可以完全控制網關的數量，每個子區域的大小可以根據目標的分布進行調整。特別是定義了無人機網絡的穩定性，建立了網絡劃分模型，設計了分布式網關選擇算法。仿真結果表明，在該方案中，不管節點移動速度變慢或變快，拓撲結構都能相對保持穩定，所以這個方案十分適用于無人機組成的移動自組網。

隨著無人機的廣泛應用，迫切需要構建無人機組網網絡以提高整體作戰效率，其中應采用移動自組網架構。在文獻[15]中，作者提出一種新的路由協議來解決無人機編隊網絡中的路由問題，稱為基于簇群的位置輔助動態源路由協議（Cluster-Based Location-Aided Routing Protocol，CBLADSR）。CBLADSR 以形成穩定的無人機機群集群結構為基礎，利用無人機的地理位置進行航路發現和航路維護。分簇過程采用節點權重啟發式算法選擇簇首，形成簇。路由過程是由簇內路由和簇間路由的組合而成，分別采用短程傳輸和遠程傳輸。CBLADSR 采用基于斜率的轉發策略，在鄰居節點中，選擇其中斜率最小的作為下一跳轉發節點。仿真結果表明，CBLADSR 在成功交付率、平均端到端時延、可擴展性和動態性能等方面明顯優于DSR 和GRP，更適合應用于無人機編隊網絡。

5 結語

如今，因為不同的任務需求，網絡規模在逐漸擴大，網絡中的節點數量也會隨著不斷增加。節點需要維護網絡里所有的拓撲信息，無疑會增加網絡開銷。但是在分級結構中，根據分簇算法將網絡中的節點劃分成為相應的簇，每個簇由一個簇首、多個簇成員和網關節點組成，不同節點被賦予不同的功能。當下Ad Hoc 網絡正逐漸呈現出分級化的趨勢，基于分簇技術，越來越多的網絡路由算法被提出和優化改進。