基于分層虛擬簇的多信道組網算法

張 姣 曹 闊 王海軍 趙海濤 熊 俊

(國防科技大學電子科學學院 長沙 410073)

1 引言

隨著智能化技術的快速發展，人機智能協同工作將會變得越來越普遍，呈現出“人類指揮、機器自主、網絡支撐”的景象[1]。網絡支撐作為智能化協作的基礎，將各組成單元通過高效協同組網支撐形成集群協作力量，可以有效實現自主協同、態勢共享和群體智能等。無線自組網因其無中心、自組織且支持靈活部署等優勢，被廣泛應用到民用和軍事通信體系中，例如，美軍提出的陸基、空基和海基數據鏈均使用了無線自組網技術[2]。然而，在實際應用場景中，無線自組網的構建將面臨更加復雜且不確定的因素影響，節點臨時加入或遭到物理摧毀使得網絡拓撲發生改變、多節點間的頻譜資源競爭占用激烈、外界強電磁頻譜干擾造成節點間通信鏈路中斷等，這些現象都將極大地削弱自組網的效能。因此，構建一個高可靠的無線自組網以提升其對復雜動態環境的自適應能力成為關鍵。

無線自組網的構建過程通常包括鄰居發現、拓撲建立、信道分配等多個階段，最終形成的網絡結構主要包括平面式和分簇式兩類[3]。相比于平面式結構，分簇式結構構建多個更小的簇單元，且簇內與簇間均具有能夠實現控制與轉發的節點，網絡管理可控且可擴展性強，更適用于大型網絡，而分簇結構的設計與控制又受到網絡節點能耗、鏈路質量、移動性以及任務等特性的影響[4,5]。考慮到無線傳感器網絡節點能量受限且存在重復相似數據收集的問題，文獻[6]提出了一種聯合分簇和動態時分多址接入(Time Division Multiple Access, TDMA)協議調度的拓撲控制算法，用于數據聚合和平衡節點能量。文獻[7]采用K-means 聚類算法對無人機集群進行分簇，以實現對地面物聯網用戶的通信覆蓋，其優化目標為在保證最小中斷概率的情況下最大化通信覆蓋范圍，但是該文獻沒有解決簇間通信實現無人機自組網的問題。針對無人軍用車輛之間的軍事信息傳遞問題，文獻[8]采用基于權重的分簇算法將菱形目標區域劃分為多個簇網絡，并通過實時平均速度和度的加權值來選舉簇頭節點。然而，以上文獻考慮的無線自組網均是較為理想的單信道網絡，需要嚴格的時間同步或控制節點才能實現。

在實際的應用場景中，無線自組網除了受到自然環境帶來的傳輸損耗、陰影衰落和多徑效應等影響外，往往還面臨惡意的電磁頻譜干擾和火力打擊等情況[9]，造成全網時鐘同步信息無法獲取且節點感知到的可用信道狀態發生變化，各節點間的實際可用信道互不相同。這種可用信道差異為無線自組網的實現帶來了極大的挑戰，主要體現在鄰居發現和多信道自組網等方面。針對僅部分信道可觀測的鄰居發現問題，文獻[10]提出了一種基于信道跳變的盲交匯算法，該算法不依賴時間同步要求并且適用于信道非對稱模型，但是該算法只解決了點對點建鏈問題。進一步，為了實現多信道無線自組網，文獻[11]提出了一種基于生物啟發的分布式多信道自適應分簇組網算法，實現了分簇網絡的連通性與靈活性折中。文獻[12]考慮次用戶的剩余能量和相對頻譜感知對認知無線電傳感器網絡進行分簇，并根據主用戶的出現概率來選擇簇網絡的公共信道，以實現網絡吞吐量最大化、時延和能耗最小化。但是，文獻[11,12]均沒有解決簇間組網的問題。文獻[13]提出了一種基于鄰域信息的多信道自適應建網算法，所構建的無線自組織網絡在公共信道和簇規模方面都取得了較好的性能，但是該模型并沒有考慮網絡的干擾控制問題。綜上所述，雖然現有文獻對多信道條件下的無線自組網構建過程中的鄰居發現、拓撲建立和信道選擇等內容進行了研究，但是仍然沒有較為全面地解決自組網過程中關于拓撲域和資源域的聯合優化問題。

針對多信道場景中的自組網問題，本文聯合考慮了無線自組網中的分層分簇拓撲建立與信道分配，實現了網絡的可靠性提升與干擾控制。主要創新工作如下：首先，構建多信道無線自組網模型，定義了節點間的可用信道差異性與通信機制；其次，提出一種基于分層虛擬簇的多信道組網算法(Hierarchical Virtual Clustering based Multi-Channel Network Construction, HVC_MCNC)，解決了虛擬簇聚類、骨干網構建與信道分配等聯合優化問題。最后，仿真結果表明本文所提算法可以構建模塊度更高的分簇網絡拓撲，且在平均簇規模和受干擾鏈路數等指標方面相比于基準算法性能更優。

2 系統模型

考慮在無線自組網遭受外界強電磁頻譜干擾的實際應用場景中，全網無可用的公共控制信道和中央控制單元，各節點無法感知到全局的可用頻譜、拓撲、時間同步等信息，整個網絡陷入到彼此失聯的癱瘓狀態，各節點如何通過感知到的自身及鄰域信息實現節點間互聯互通并組建優化的網絡結構成為困難。如圖1所示，在給定范圍區域內，存在N個網絡節點，用U={1,2,...,N}表示。全網可用頻譜帶寬為B，將頻譜劃分為M個非重疊信道，總信道集用 CH={1,2,...,M}表示。在受到電磁頻譜干擾的情況下，節點i僅能感知到全網的部分可用信道 CHi,C Hi ?CH。

3 基于分層虛擬簇的多信道組網算法

為了解決無線自組網在遭受強電磁頻譜干擾條下多信道組網困難的問題，本文從拓撲域與資源域聯合優化的角度提出了基于分層虛擬簇的多信道組網算法。首先，各節點感知環境中自身可用的信道、地理位置等信息，通過盲交匯機制發現周圍的鄰居節點并與其共享感知信息[11]。基于各節點間自身和鄰域信息的共享，具備公共可用信道的節點將被聚類為一個虛擬簇。虛擬簇內成員節點之間的相互連接構成底層接入網絡，各成員節點通過簇內公共可用信道基于TDMA協議進行通信。各虛擬簇根據節點感知到的可用信道比率和鄰居節點比率的加權函數推舉重要度最大的節點作為簇頭節點。其次，虛擬簇間通過簇頭節點建立連接構成頂層骨干網絡。當簇頭節點間受通信距離限制無法建立直達鏈路時，將借助簇成員節點作為網關節點進行連接。在骨干網鏈路中，為避免出現信息風暴與碰撞，各骨干網節點之間僅考慮1條1跳或多跳的連通鏈路，骨干網節點通過多信道載波偵聽多點接入/沖突避免(Carrier Sense Multiple Access/ Collision Avoidance, CSMA/CA)機制進行信息交互與路由轉發。最后，在分層虛擬簇結構的無線自組網中，通過聯合簇內和簇間鏈路的信道分配實現通信干擾控制。具體地，本文重點對多信道組網過程中的虛擬簇聚類、骨干網構建與信道分配3個階段進行介紹。

3.1 基于公共信道鄰居比的虛擬簇聚類

在頻譜感知受限的無線自組網中，各節點可以依次在感知到的可用信道上進行周期性跳變，并通過盲交匯機制來實現鄰居發現與點對點鏈路構建。但是，這種建網方式只能夠構建平面結構的無線自組網，不利于大規模的信息交互。為了優化網絡結構，本節采用公共信道鄰居比建立節點間的相似度指標，并基于該指標定義了網絡的模塊度函數，用于優化形成分簇的無線自組網。

相似度用于表示兩個節點之間的緊密程度，常用的表征方式包括余弦相似度、Jaccard相似度、Sorensen相似度等[14]，這些表征方式均是基于節點間的共同鄰居特性來衡量。在Jaccard相似度的啟發下，本節充分考慮了兩節點間的共同鄰居節點的拓撲特性與信道特性，構建了基于公共信道鄰居比的相似度指標，用于衡量網絡節點間的相似性。如果節點i與節點j具有公共信道h且均在雙方通信范圍之內，則兩者互為鄰居節點且可以直接建立鏈路關系，將兩節點間的基于公共信道鄰居比的相似度定義為

根據文獻[15]，模塊度函數作為復雜網絡社區發現質量評價的標準，可以用于定量描述分簇網絡的模塊性水平，模塊性水平越高的網絡其簇內連接更緊密，抗摧毀能力越強。基于公共信道鄰居比定義的相似度指標，對無線自組網的模塊度函數進行改進。假設Ci和Cj分別表示節點i和節點j所屬的簇網絡，則整個網絡的模塊度函數可以定義為

其中，Si,in表示節點i與簇網絡C內所有節點之間的相似度之和。

Fast Unfolding算法作為典型的基于模塊度優化的社區發現算法，具有計算效率高、可快速處理節點規模較大的復雜網絡的特點[16]。但是，該算法采用傳統模塊度函數作為社區發現的標準，并且不考慮節點間存在的信道差異和鄰居節點的影響，因此并不能直接適用于解決本文的網絡分簇問題。根據無線自組網中節點間的基于公共信道鄰居比的相似度指標定義的模塊度函數，本文提出了一種基于公共信道鄰居比的簇網絡聚類算法，具體流程如算法1所示。

算法1 基于公共信道鄰居比的簇網絡聚類算法

為了進一步構建頂層骨干網絡，將每個簇網絡內各節點感知到的可用信道比率與鄰居節點比率進行加權求和建立節點的重要度，并推舉重要度最大的節點作為簇頭節點。將節點的重要度定義為

其中，α表示節點可用信道比率與鄰居節點比率的加權因子，α ∈[0,1]。

3.2 基于R-跳連通控制集的骨干網構建

考慮采用簇頭節點與網絡中的網關節點構建虛擬骨干網鏈路，為不同簇網絡間的成員節點提供數據轉發服務。目前，最常用的虛擬骨干網構建方法主要是圖論中的連通控制集(Connected Dominating Set, CDS)[17]，骨干網節點作為連通控制集中的控制集為非骨干網節點提供連通鏈路。

將虛擬骨干網的構建過程建模為R-跳連通控制集問題。定義連通網絡為無向圖G=(V,E)，其中V,E分別表示網絡中的節點和連邊集合，找到一個具有最少節點數的子集D?V，并使其滿足：(1)D中任意兩節點間至少有1條路徑相連；(2)對于節點u ∈VD，最多通過R跳與D中的至少1個節點建立連接。顯然，R跳數越小，構建骨干網的節點數越多，骨干網覆蓋的范圍越大，可有效降低不同簇網絡內各節點間的路由轉發代價，但是會增加骨干網絡鏈路的通信代價。因此，R跳數的選擇需要進行折中設置。

現有的連通控制集的構造方法主要包括生成樹、圖著色、極大獨立集等。由于本文所構建的分簇網絡的簇頭節點間不一定存在直接連接關系，這些方法并不能直接適用。針對該問題，本文通過先控制再連通的方式對生成樹方法進行了改進，并提出了基于R-跳連通控制集的最小生成樹虛擬骨干網構建方法，如算法2所示。該方法的主要思想為：首先，選取所有簇頭節點構建一個樹節點集合，該集合中的任意兩個節點受發射功率的影響不一定能直接建立連接鏈路；然后，再選取一部分的成員節點作為網關節點加入到樹節點集合中，使得集合中的所有節點剛好可以構建一個R-跳連通控制集，連通控制集中的所有節點將作為虛擬骨干網節點負責不同簇網絡內成員節點間的信息轉發。

3.3 基于受限圖著色的信道分配

在構建的分層虛擬簇結構的無線自組網中，簇內節點采用公共信道CCHn(n ≤N)進行信息交互。簇間節點通過骨干網鏈路連接，各骨干網節點間的通信信道集合為連接邊兩端節點感知到的公共信道CHi,j。為了避免簇內通信與簇間通信之間造成相互干擾，將簇網絡抽象為虛擬節點，并基于骨干網對各虛擬簇節點與骨干邊同時進行信道分配，從而實現對整個分層分簇網絡的信道分配。

算法2 基于R-跳連通控制集的最小生成樹骨干網構建算法

將分層虛擬簇網絡采用無向圖G′= (V′,E′)來表征，其中節點A,B,C表示抽象的虛擬簇網絡，d為連接簇A和簇C的網關節點，各邊均為骨干網連邊。為了同時保證簇內與簇間的通信需求，對節點A,B,C以及各邊進行信道分配。由于節點d為網關節點，不對節點d單獨進行信道分配。假設虛擬簇節點與各邊的干擾域為其通信域的2倍，則可以采用圖G′對應的沖突圖來表征虛擬簇節點與各邊之間存在的潛在通信干擾，如圖2所示。

圖2 分層虛擬簇網絡連通圖與沖突圖

根據所構建的沖突圖，當虛擬簇網絡與骨干網絡同時發起通信需求時，各虛擬簇網絡將可能受到來自2倍通信距離范圍內的鄰居簇網絡或者骨干網邊的同頻干擾。因此，可將分層虛擬簇網絡的信道分配問題建模為圖G′對應的沖突圖的節點著色問題。與傳統的圖著色中各節點的著色種類對等不同，圖2(b)構建的沖突圖中各節點可選用的信道數不完全相同。沖突圖中各節點可用信道集合定義如下：

(1)若沖突圖中的節點為圖G′中的節點n，則節點的可用信道為 CCHn，即第n個虛擬簇網絡的公共信道集；

(2)若沖突圖中的節點為圖G′中的邊e，則節點的可用信道為 CHe，即圖G′中邊e的兩端節點的公共信道集。

在定義(2)中，由于簇間通信主要通過簇頭節點與網關節點進行路由轉發，當邊e的頂點中包括虛擬簇節點和網關節點時，其可用信道為簇網絡中的簇頭節點與網關節點間的公共信道。例如，對于邊EAd，則 CHEAd=CHa ∩CHd，其中節點a為虛擬簇網絡A的簇頭節點。

為了避免簇內與簇間通信產生干擾以確保全網的連通質量，本文以最小化分層虛擬簇網絡的通信干擾為優化目標，構建關于沖突圖節點的信道分配模型為

其中，N′表 示沖突圖中的頂點數量，N′=|V′cluster(G′)|+|E′(G′)|。In,k表示沖突圖中任意兩節點之間的通信干擾情況,f(n)與f(k)分別表示分配給沖突圖中節點n和節點k的信道。當節點n與k相鄰且f(n)=f(k) 時，In,k=1 ，否則In,k=0。

根據上述分析可知，沖突圖中各節點的可用信道受限且各不相同，傳統的圖著色算法并不適用。因此，本文提出了一種基于受限圖著色的分層虛擬簇網絡信道分配算法，如算法3所示。

4 仿真性能分析

本節將通過仿真實驗對所提的算法性能進行分析，考慮在一個1 000 m×1 000 m的矩形區域內隨機分布若干個網絡節點，全網可用子信道帶寬為10 kHz。初始時刻，各節點由于遭受強電磁干擾彼此之間相互失聯，且各節點僅能感知到全網頻段中的部分可用信道。各節點的最大傳輸距離為200 m，干擾距離為400 m。此外，為了避免設置固定的R跳數造成不同網絡形態下骨干網鏈路可能不存在的情況，將R跳數值設置為當前網絡形態下節點間的平均最短鏈路長度值用于構建基于最小生成樹的骨干網。其他信道相關參數參考文獻[13]設置。

4.1 網絡拓撲構建

為了便于直觀展示與分析，在目標區域內隨機部署50個網絡節點，全網信道數為6個。圖3展示了各節點通過感知到的自身與鄰域信息實現基于分層虛擬簇的無線自組網拓撲構建與信道分配過程。初始狀態，各節點僅能感知到部分可用信道，彼此失聯，如圖3(a)所示；圖3(b)展示了各節點通過感知到的自身和鄰居節點信息實現分簇網絡構建的過程，其中三角形節點為簇頭節點，圓形節點為成員節點，不同顏色的簇網絡連邊表示當前通信選用的可用公共信道；圖3(c)中的藍色虛線為基于R-跳連通控制集構建的虛擬骨干網鏈路，藍色矩形框內的成員節點作為網關節點為不同簇網絡中不可達的簇頭節點提供連通鏈路；圖3(d)為進行信道分配后形成的最終組網形態。從圖3可以看出，整個網絡形成了11個分簇網絡，各個簇網絡內的節點均具有共同的公共信道。不同簇網絡之間通過簇頭節點和網關節點建立連接，各骨干鏈路采用的信道為連邊兩端節點的公共可用信道。本文所提算法形成的網絡形態是典型的分層分簇網絡結構，可以有效實現分層網絡管理與可靠通信。

算法3 基于受限圖著色的分層虛擬簇網絡信道分配算法

圖3 分層虛擬簇網絡拓撲構建與信道分配

4.2 網絡模塊度分析

為了有效衡量本文所提算法得到的分簇網絡的模塊性水平，將所提算法與以下3種基準算法進行對比分析：(1)Fast Unfolding分簇網絡構建算法：當兩節點具有公共信道且均在對方可達通信范圍內時，則兩者的相似度為1，采用傳統的層次聚類算法進行簇網絡構建[16]；(2)基于Jaccard相似度的分簇網絡構建算法(Jaccard Similarity based Clustering Network Construction, JS_CNC)：設置兩節點間的相似度為Jaccard相似度，采用基于Jaccard相似度的層次聚類算法進行分簇網絡構建；(3)多信道自適應建網算法(Multi-channel Adaptive Network Establishment, MANE)：如文獻[13]所示，各節點將基于鄰域信息進行信道質量評價與鄰居簇頭評價，從而構建分簇網絡。

圖4展示了不同算法形成的分簇網絡的模塊度隨節點數量變化的性能曲線。隨著網絡節點數的增加，可以明顯觀察到不同建網算法得到的網絡模塊度均呈下降的趨勢，這是由整個網絡中各節點感知到的可用信道存在差異和通信距離受限所約束。不同節點的隨機分布造成節點間的可用信道差異性增大，整個網絡將形成更多的分簇網絡，簇內成員之間的緊密度變低，使得整個網絡的模塊性水平降低。此外，本文所提的HVC_MCNC算法和JS_CNC算法形成的分簇網絡的模塊度較為接近且遠大于其余兩種算法。

圖4 網絡節點數對模塊度的影響

圖5展示了不同總信道數下分簇網絡的模塊度變化曲線，網絡節點數為100個。隨著信道數的增加，可以觀察到MANE算法得到的網絡模塊度呈一定的下降趨勢，但是其他算法獲得的網絡模塊度變化趨勢并不明顯，而是呈一定的上下波動趨勢。在MANE算法中，各成員節點僅與簇頭節點建立連接形成星狀分簇網絡，當信道數增加時，各節點感知到的自身與鄰居節點間的信道差異性越明顯，具有公共信道的鄰居節點數越少，造成MANE算法所形成的簇網絡規模越小。簇網絡內部的緊密度降低，而簇間連接更加緊密，使得整個網絡的模塊度減小。而本文所提算法則充分考慮了不同節點間的拓撲關系和公共信道特性，形成簇規模更大的網狀簇網絡，整個網絡的模塊度受簇網絡內部的拓撲結構影響更大。不同節點感知到的信道差異性使得簇網絡內部結構的變化存在差異，因此，所獲得的網絡模塊度在不同的信道數下呈現差異性的變化趨勢。

圖5 網絡總信道數對模塊度的影響

4.3 網絡拓撲與信道分配性能分析

本節進一步對所提算法構建的網絡拓撲與信道分配性能與文獻[13]所提的MANE算法進行對比分析，所采用的性能評價指標包括：平均簇規模、平均最短鏈路長度以及通信干擾鏈路數。其中，平均簇規模是分層虛擬簇架構的無線自組網各簇內的平均節點數量；平均最短鏈路長度為網絡中任意兩點間的平均最短鏈路數；網絡中的通信干擾鏈路數則為分層虛擬簇網絡對應的沖突圖中受干擾的節點對數和。

圖6給出了平均簇規模隨節點數和信道數變化的情況。從中可以看到，隨著網絡節點數的增加，本文所提算法和MANE算法形成的分簇網絡的平均簇規模逐漸增大，且本文所提算法得到的平均簇規模明顯大于MANE算法。這是因為本文所提算法得到的分簇網絡模塊度更高，簇內成員節點間的緊密性更強，簇數量更少，因此平均簇規模越大，更利于提升網絡的抗摧毀能力。當信道數增加時，用戶之間的信道差異性變大，在相同節點情況下分簇網絡的數量會出現一定比例的增加，造成平均簇規模減小。

圖6 平均簇規模變化曲線

圖7展示了平均最短鏈路長度的變化情況。當總信道數一定時，平均最短鏈路長度隨網絡節點數量的增加呈逐漸增長且趨于平緩的趨勢。當節點數增加時，節點之間的信道差異性更明顯，形成的分簇網絡數量逐漸增加，造成不同簇網絡節點之間的路由轉發距離更遠，平均鏈路長度增加。但是，當分簇網絡數量足夠多時也會使得形成的骨干網鏈路覆蓋范圍越大，不同簇網絡節點間的路由轉發路徑變短，因此平均最短鏈路長度隨網絡節點數的增加逐漸趨于平緩。在相同的節點數和信道數的情況下，本文所提算法得到的平均最短鏈路長度略大于MANE算法，這是由本文所提算法得到的簇數量遠遠小于MANE算法所決定的。此外，隨著信道數的增加，簇數量呈現一定的增長趨勢，平均最短鏈路長度逐漸減少。

圖7 平均最短鏈路長度變化曲線

圖8展示了不同算法得到的分簇網絡中通信干擾鏈路數的變化情況。可以觀察到，隨著節點數的增多，不同算法得到的受干擾鏈路數呈明顯增長趨勢。在相同的信道條件下，節點數的增加會使得簇網絡數量和骨干網鏈路增加。當簇內和簇間成員分別采用TDMA和CSMA/CA協議進行通信時不得不對有限的信道資源進行復用，造成同頻干擾。由圖6可知，本文所提算法得到的簇網絡規模遠遠大于MANE算法。因此，其得到的簇網絡數量和骨干網鏈路更少，單位時隙內本文所提算法得到的受干擾鏈路數明顯更少。隨著信道數的不斷增加，雖然會帶來簇網絡數量的增加，但是也為不同的簇網絡和骨干網鏈路提供了更多的通信資源，因此受干擾鏈路數逐漸減小。

5 結束語

本文提出一種基于分層虛擬簇的多信道組網算法，以實現強電磁干擾下無線自組網的拓撲構建與信道分配。該算法利用網絡中各節點感知到的自身與鄰域信息構建了包括分簇網絡和虛擬骨干網的分層網絡拓撲，并基于該分層網絡提出了一種受限圖著色的信道分配方法。仿真結果表明，本文所提算法可以構建模塊性水平更高的分簇網絡拓撲，且在平均簇規模和降低通信干擾方面具有明顯優勢。下一步，本文將在組網協議設計、移動性管理與動態多信道條件下的自適應組網機制等方面展開深入研究，以提升分層分簇網絡的組網性能與自適應能力。