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

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

0 引言

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

1 拓?fù)浣Y(jié)構(gòu)分類

Ad Hoc 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有不同的分類，研究者們習(xí)慣于將其分為平面結(jié)構(gòu)和分級結(jié)構(gòu)[2]。如圖1 所示，平面結(jié)構(gòu)的網(wǎng)絡(luò)復(fù)雜度較低，其中的網(wǎng)絡(luò)節(jié)點具有相同的地位和功能，各節(jié)點之間相互協(xié)同合作完成通信，所以又稱為對等式平面結(jié)構(gòu)。

圖1 平面結(jié)構(gòu)的Ad Hoc 網(wǎng)絡(luò)

如今，因為不同的任務(wù)需求，網(wǎng)絡(luò)不斷的開發(fā)，規(guī)模也越來越大，網(wǎng)絡(luò)中的節(jié)點數(shù)量也隨著越來越多。每個節(jié)點都互相交互信息去維護(hù)網(wǎng)絡(luò)里所有的拓?fù)湫畔?，無疑會增加網(wǎng)絡(luò)開銷。但是在網(wǎng)絡(luò)復(fù)雜度更高的分級結(jié)構(gòu)中，根據(jù)分簇算法將網(wǎng)絡(luò)中的節(jié)點劃分進(jìn)不同的簇，每個簇由一個簇首、多個簇成員和網(wǎng)關(guān)節(jié)點組成，不同節(jié)點被賦予不同的功能。簇首形成高一級網(wǎng)絡(luò)，分別負(fù)責(zé)不同簇內(nèi)節(jié)點之間的通信，并提供路由信息和發(fā)現(xiàn)合適的路徑，方便簇間節(jié)點通信。分級結(jié)構(gòu)又可以被繼續(xù)劃分為單頻分級結(jié)構(gòu)網(wǎng)絡(luò)和多頻分級結(jié)構(gòu)網(wǎng)絡(luò)，如圖2 所示。在單頻分級結(jié)構(gòu)網(wǎng)絡(luò)中，所有節(jié)點都使用相同的頻率通信，通過網(wǎng)關(guān)節(jié)點能夠?qū)崿F(xiàn)簇首節(jié)點之間的通信。與單頻分級結(jié)構(gòu)網(wǎng)絡(luò)不同，在多頻分級結(jié)構(gòu)網(wǎng)絡(luò)中，節(jié)點級別決定了節(jié)點的通信頻率，級別不同的節(jié)點采用不同的通信頻率，高級節(jié)點的通信范圍大于低級節(jié)點，簇首節(jié)點可以使用兩種不同的頻率，一個用來維持與其他簇首節(jié)點之間的通信，另一個頻率用來與本簇內(nèi)的簇成員通信。

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

圖2 分級結(jié)構(gòu)網(wǎng)絡(luò)

當(dāng)下Ad Hoc 網(wǎng)絡(luò)正逐漸呈現(xiàn)出分級化的趨勢，許多網(wǎng)絡(luò)路由算法也基于分級結(jié)構(gòu)的網(wǎng)絡(luò)模式被提出和改進(jìn)。為了更清晰地理解這兩種分類各自的特點，將平面路由和分簇路由的特點進(jìn)行宏觀比較，見表1。

2 不同分簇方案

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

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

圖3 分簇方案

3 在無線傳感器網(wǎng)絡(luò)中的應(yīng)用

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

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

4 在自組織網(wǎng)絡(luò)中的應(yīng)用

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

由于節(jié)點的移動性，MANET 中的網(wǎng)絡(luò)拓?fù)渥兓诸l繁。當(dāng)一個節(jié)點的遷移信息被共享給網(wǎng)絡(luò)中的所有節(jié)點時，拓?fù)渚S護(hù)會產(chǎn)生額外的開銷。為了解決MANET 中的拓?fù)渚S護(hù)開銷問題，研究人員提出了不同的基于簇群的算法來減小路由表的大小。簇的形成是為了局部地調(diào)整簇內(nèi)的拓?fù)渥兓?。如果一個節(jié)點希望與簇群外部的節(jié)點通信，那么它只與自己的簇首通信。CH 與其他CHs 通信，將數(shù)據(jù)傳輸?shù)侥康牡?。為了有效地利用MANET 中的分簇機(jī)制，需要穩(wěn)定、均衡的簇群。一些度量指標(biāo)有助于優(yōu)化且形成質(zhì)量良好的簇群，如相對移動性（節(jié)點速度、方向等）、節(jié)點度、剩余能量、通信工作量和鄰居節(jié)點的性能。文獻(xiàn)[9]總結(jié)了近年來MANET 的分簇情況，還介紹了最近研究的目的、目標(biāo)和貢獻(xiàn)。同時，對研究結(jié)果、面臨的挑戰(zhàn)和未來的發(fā)展方向進(jìn)行了闡述。

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

文獻(xiàn)[11]提出了一種新的基于全球定位系統(tǒng)（Global Positioning System，GPS）的自組網(wǎng)路由協(xié)議——基于區(qū)域的分層鏈路狀態(tài)（zone-based two-level link state，ZHLS）路由協(xié)議。在該協(xié)議中，網(wǎng)絡(luò)被劃分為多個區(qū)域而且每個區(qū)域之間互不重疊。每個節(jié)點只知道其區(qū)域內(nèi)的節(jié)點連接和整個網(wǎng)絡(luò)的區(qū)域連接。鏈路狀態(tài)路由在本地節(jié)點和全局區(qū)域兩個級別上執(zhí)行。與其他分層協(xié)議不同的是，這個協(xié)議中沒有簇首節(jié)點。區(qū)域級拓?fù)湫畔⒎植嫉剿泄?jié)點。這種點對點方式緩解了流量瓶頸，避免了單點故障，簡化了移動管理。由于只需要目的地的區(qū)域ID 和節(jié)點ID 進(jìn)行路由，因此從源到目的地的路由可以適應(yīng)不斷變化的拓?fù)浣Y(jié)構(gòu)。通過向每個區(qū)域發(fā)送一個位置請求，就可以找到目的地的區(qū)域ID。位置搜索方案比基于洪泛的方案產(chǎn)生更少的開銷。在該協(xié)議中創(chuàng)建和維護(hù)拓?fù)涞耐ㄐ砰_銷要小于平面LSR 協(xié)議。這種新的路由協(xié)議提供了一種靈活、高效和有效的方法來適應(yīng)無線網(wǎng)絡(luò)環(huán)境中不斷變化的拓?fù)浣Y(jié)構(gòu)。

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

節(jié)點的動態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和移動特性可能會對連通性和路由造成挑戰(zhàn)。針對大型的移動自組網(wǎng)，各種各樣的分簇方案是可以根據(jù)網(wǎng)絡(luò)拓?fù)渥兓瘉碇匦聝?yōu)化組織網(wǎng)絡(luò)的有效方法之一。在文獻(xiàn)[13]中，作者提出了一種基于區(qū)域群移動性的自組織分簇（Self-Organization Based Clustering）方案來提高整個網(wǎng)絡(luò)的可擴(kuò)展性和穩(wěn)定性。該算法利用鳥類群集的生物啟發(fā)行為研究，以形成和維持MANET 的分群。提出了一種動態(tài)的考慮簇大小的管理機(jī)制，以減少網(wǎng)絡(luò)擁塞，提高M(jìn)ANET 在群組移動性能方面的性能。為了合理利用資源，降低額外的能耗，提出了一種合理處理孤立節(jié)點的算法。根據(jù)節(jié)點接收信號的強(qiáng)弱將節(jié)點進(jìn)行分區(qū)，簇內(nèi)結(jié)構(gòu)被分為三種不同類型的區(qū)域：簇首、節(jié)點吸引區(qū)域和節(jié)點排斥區(qū)域。算法流程包括節(jié)點狀態(tài)識別、簇首選擇以及孤立節(jié)點處理。仿真結(jié)果表明，文獻(xiàn)中提出的改進(jìn)算法有效降低了網(wǎng)絡(luò)的能耗開銷，提高了網(wǎng)絡(luò)中節(jié)點的生存時間，使網(wǎng)絡(luò)結(jié)構(gòu)更加穩(wěn)定具有較強(qiáng)的魯棒性。

近年來，就小型無人機(jī)廣泛應(yīng)用的優(yōu)勢來說，基于通信網(wǎng)絡(luò)的合作可以有效地擴(kuò)大無人機(jī)的工作范圍。雖然無人機(jī)網(wǎng)絡(luò)與傳統(tǒng)的移動自組織網(wǎng)絡(luò)非常相似，但是相關(guān)文獻(xiàn)中并沒有考慮到無人機(jī)應(yīng)用場景的特殊性。針對無人機(jī)網(wǎng)絡(luò)的應(yīng)用特點，文獻(xiàn)[14]提出了一種適用動態(tài)網(wǎng)絡(luò)的分布式網(wǎng)關(guān)選擇算法。該算法通過將網(wǎng)絡(luò)劃分成多個子區(qū)域來減弱信息不對稱現(xiàn)象對無人機(jī)拓?fù)淇刂频挠绊?。在網(wǎng)絡(luò)運(yùn)行過程中，即使無人機(jī)移動速度較快，也可以通過自適應(yīng)調(diào)整網(wǎng)絡(luò)的分區(qū)來保持整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的穩(wěn)定。同時，可以完全控制網(wǎng)關(guān)的數(shù)量，每個子區(qū)域的大小可以根據(jù)目標(biāo)的分布進(jìn)行調(diào)整。特別是定義了無人機(jī)網(wǎng)絡(luò)的穩(wěn)定性，建立了網(wǎng)絡(luò)劃分模型，設(shè)計了分布式網(wǎng)關(guān)選擇算法。仿真結(jié)果表明，在該方案中，不管節(jié)點移動速度變慢或變快，拓?fù)浣Y(jié)構(gòu)都能相對保持穩(wěn)定，所以這個方案十分適用于無人機(jī)組成的移動自組網(wǎng)。

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

5 結(jié)語

如今，因為不同的任務(wù)需求，網(wǎng)絡(luò)規(guī)模在逐漸擴(kuò)大，網(wǎng)絡(luò)中的節(jié)點數(shù)量也會隨著不斷增加。節(jié)點需要維護(hù)網(wǎng)絡(luò)里所有的拓?fù)湫畔?，無疑會增加網(wǎng)絡(luò)開銷。但是在分級結(jié)構(gòu)中，根據(jù)分簇算法將網(wǎng)絡(luò)中的節(jié)點劃分成為相應(yīng)的簇，每個簇由一個簇首、多個簇成員和網(wǎng)關(guān)節(jié)點組成，不同節(jié)點被賦予不同的功能。當(dāng)下Ad Hoc 網(wǎng)絡(luò)正逐漸呈現(xiàn)出分級化的趨勢，基于分簇技術(shù)，越來越多的網(wǎng)絡(luò)路由算法被提出和優(yōu)化改進(jìn)。