無人平臺移動網絡分簇研究

劉邈

【摘要】 無人平臺集群移動網絡較多呈現分布式、無中心以及網絡成員數較多、動態性較強等特點，為有效確保網絡運行性能，大規模的無人平臺集群移動網絡維護管理常利用分區域管理模式。此外，在實際應用中，無人平臺集群移動網絡常會遭遇由于電磁環境、干擾等因素導致的通信質量不穩定變化。因此，本文采用引入節點通信質量的網絡加權分簇算法，其通過計算各相關因素的權值并根據最終得到的總權值確定簇頭節點，進而完成網絡的分簇。

【關鍵詞】 網絡分簇 通信質量 網絡拓撲

Research of Cluster-constructing for Unmanned Platforms Mobi Network Liu Miao （Southwest China Institute of Electronic Technology， Chengdu 610036）

Abstract： There are characteristics in the Mobi Network for unmanned swarming platforms： no-centered， distributed， large amount of nodes， and more dynamic. The Mobi Network which has a large scale of nodes is managed via zoning， in order to ensure network performances. In addition， in actual use， the communication quality of the network is probably instable due to the complex electromagnetic environment or the jamming and so on. So cluster constructing algorithm based on communication quality and authoritys is discussed in this thesis. The algorithm calculates authoritys of elements， and identifies the cluster head according to the result of the authoritys sum. On this basis， cluster constructing of the network is done.

Key words： Network Clustering； Communication Quality； Network Topology；

一、引言

無人平臺集群移動網絡的應用越來越廣泛，包括：無控制中心的分布式軍事通信、無人移動平臺傳感器網絡，以及難以部署基礎設施的應急網絡通信等，網絡較多地呈現分布式、無中心以及網絡成員數較多、動態性較強等特點，高效的網絡維護管理非常重要。為有效確保網絡運行性能，大規模的無人平臺集群移動網絡維護管理常利用分區域管理模式。因此，就必須有相應措施對網絡成員進行分簇，并對分簇網絡結構進行維護[1]。

此外，在實際應用中，無人平臺集群移動網絡常會遭遇由于電磁環境、干擾等因素導致的通信質量不穩定變化。因此，本文采用引入節點通信質量的網絡加權分簇算法（Communication Quality Authority Clustering Algorithm，CQACA），將包括節點度、節點通信質量、節點移動性等在內的各相關因素賦以不同權值，根據最終所求得的總權值選取總權值最小的節點作為簇頭節點，完成網絡的分簇。

二、無人平臺集群移動網絡特點

無人平臺集群移動網絡根據節點成員的層次情況將形成以下典型拓撲結構：①平面結構：節點的身份角色并無特殊區分——網絡中沒有專門的控制管理節點；②分簇結構：在網絡成員數較多、規模較大情況下使用，節點在網絡中的身份角色分為：簇頭節點和普通節點；③Mesh結構：約束了網絡中節點的路由規模，一般情況下節點僅與其鄰節點通信，該拓撲與平面結構較類似。上述幾類典型拓撲結構如圖1所示。

無人平臺集群移動網絡作為一種典型的移動Ad hoc網絡（MANET），其體現出以下特點：①分布式、無中心；②突出的拓撲動態性；③無線信道將由多跳節點共享；④節點能量受限；⑤帶寬受限；⑥數據業務為主；⑦建立運行靈活。此外，由于無人平臺集群移動網絡在較多應用條件下，常會遭遇由于電磁環境、干擾等因素導致的通信質量不穩定變化，因此對于部分對網絡節點間的通信質量較為敏感的應用，保持網絡節點間通信質量穩定、可靠在網絡的分簇、維護管理中就較為重要。在網絡分簇維護管理過程中，需要針對性地考慮上述特點對網絡分簇維護管理機制的影響，而不宜直接采用通常的無線網絡分簇維護管理算法、策略。

三、網絡拓撲與分簇

無人平臺集群的移動Ad hoc網絡（MANET）在規模較大條件下，網絡拓撲的構建將不可避免地面臨開銷較大、收斂較慢、路由不夠穩定等問題。因此，網絡維護管理將采取層次化的分布式方法以便提高網絡運行效能：在不同的區域中選出各自的簇首節點，其將是本簇中唯一與其他簇外節點通信的節點，網絡通信基干就將由簇首節點動態構成，其將負責數據的中繼轉發等職責。對于簇首節點的選擇，其數目與簇內普通節點數應該保持協調，也即是說對于分簇算法，其所形成的簇所包含的節點既不宜太多、也不宜過少。研究發現，采用三層的層次結構將是一個較好的平衡策略[2]。

移動Ad hoc網絡的網絡拓撲從層次關系上看包括以下兩種大的類別：節點隨機扁平分布方式、分層分布方式。常用的典型Ad hoc網絡其拓撲以節點隨機扁平分布方式居多；較多應用于軍事應用戰場環境的無人平臺集群移動Ad hoc網絡會較多地形成分層分布式網絡拓撲，這是受到部隊作戰指揮層次化特點影響導致的。典型的分層分布式Ad hoc網絡拓撲如圖2所示。

四、引入節點通信質量的網絡加權分簇算法

4.1總體思路

根據無人平臺集群的移動Ad hoc網絡（MANET）的應用需求特點，包括：確保網絡節點間的連通性，確保網絡成員間對通信質量敏感的信息可靠傳輸，不難看出對該類網絡設計網絡分簇算法應當考慮下述因素：網絡連通性、傳輸可靠性、分簇穩定性及負載均衡性等。因此，本文所提出的網絡分簇算法將基于虛擬骨干網節點、引入節點通信質量按照網絡加權分簇的策略實施，其思路如下：

首先，網絡節點通過監聽其可達范圍內的鄰居節點通信獲取其兩跳范圍內的節點情況；其次，按照應用需求確定的初始節點將發送構建網絡分簇請求，消息的發送對象是網絡拓撲維護算法確定的虛擬網絡骨干節點（即最小主控集節點），骨干節點在接收到構建分簇請求后將對其做出響應。然后，初始發送節點收到響應信息后，將根據其所獲取的骨干節點及其鄰節點情況，構建本分簇的拓撲結構。算法實施過程中，既應滿足網絡的全網連通性也應控制虛擬網絡骨干節點規模，既應有所側重滿足某方面重點需求又應使系統整體性能達到均衡，節點通信質量、節點覆蓋度、節點移動性、節點剩余能量、鄰節點距離等都將成為影響網絡分簇的因素。

4.2考慮節點通信質量的加權分簇

2002年Chatterjee提出的加權分簇算法 [3]中心思想為：綜合考慮節點移動情況、節點覆蓋度、節點能耗及鄰節點距離等各因素，按照不同應用需求為上述因素分配不同權值，來描述其按照該應用要求在網絡分簇中所起作用的重要程度。

無人平臺集群的移動Ad hoc網絡應用有較高的信息可靠傳輸需求，其對節點通信質量較為敏感，因此，本文提出一種引入節點通信質量的網絡加權分簇算法（Communication Quality Authority Clustering Algorithm，CQACA）。在本算法中，節點通信質量、節點覆蓋度、節點剩余能量、鄰節點距離、節點移動性等因素各類因素將被賦予不同權值，根據無人平臺集群的移動Ad hoc網絡應用需求特點，節點通信質量將賦以較高的權值。本算法還在節點移動性、與鄰節點距離兩項上進行了改進：①節點移動性：采用由節點y相對其鄰節點的平均移動速度替換原算法中的節點y自身的絕對平均移動速度；②與鄰節點距離：采用由節點y相對其鄰節點的平均距離替換原算法中的節點y與其鄰節點的距離和。最終，選取所求得總權值最小的節點作為簇頭節點。算法具體過程如下：

首先，對節點通信質量NodeComQuay進行定義，具體如下：

假設節點y到其n個鄰居節點的丟包率分別為e1，e2，…，en，在網絡運行過程中，丟包率ei=（1-C/（c2-c1））*100%。其中：ΔT時間段內，收端節點實際收到的數據包數為：C；ΔT時間段起始時刻t1收端收到的數據包序列號為：c1；終止時刻t2收端收到的數據包序列號為：c2。節點y的鄰節點ri成功接收到其發送的消息時節點y所需發送的次數為：隨機變量Xi；n個鄰節點都成功接收到其發送的消息時，節點y所需發送的次數為：隨機變量Y，那么：

網絡運行過程中，網絡節點到其鄰居節點的鏈路丟包率ei能夠通過周期交互的網絡維護類消息獲得。節點y按照上述定義將獲得節點通信質量NodeComQuay，并實時更新。NodeComQuay值越小，表示節點y在網絡中的通信質量越好。CQACA網絡加權分簇算法將利用該實時更新的節點通信質量NodeComQuay，簇頭節點則根據算法的計算結果確定。

以下將描述引入節點通信質量的網絡加權分簇算法（CQACA）：

1）計算節點y的覆蓋度：

①Δdegry：節點y與網絡中最優覆蓋度的差距，該值越小則y的覆蓋度越接近最優覆蓋度，即：節點y的覆蓋能力越好；

②Distany：節點y相對其鄰居節點的平均距離，該值越小則y距其鄰節點越近，從而可能獲得更好的通信質量或鏈路余量；

③Mobiy：節點y相對于其鄰節點的相對平均速度，該值越小則y相對其鄰節點的移動性越弱；

④Powy：節點y的剩余能量，Powy值越小則y剩余能量越多；

⑤NodeComQuay：節點通信質量，NodeComQuay值越小表示節點y的通信質量越好；

按照不同應用需求，上述公式中各部分因子的權值也將不同。在無人平臺集群的移動Ad hoc網絡的組網應用中，由于應用有較高的信息可靠傳輸需求且其對節點通信質量較為敏感，因此節點通信質量NodeComQuay將占有較大的權重。

根據網絡分簇算法簇頭選取總權值計算公式，不難看出：總權值Authorityy與各部分權值呈線性關系單調遞減關系。因此，最終將選取總權值Authorityy最小的節點，作為簇首節點。

8）網絡成員節點加入簇中

Ch表示所選擇的簇頭節點集合，如果簇頭節點y覆蓋度小于最優覆蓋度（degry≤σ），那么y向所有鄰居節點發送簇頭通報消息；如果簇頭節點y覆蓋度大于最優覆蓋度（degry>σ），那么y的所有鄰節點均計算處理：A（i，y）adapt=a 2*Distany+a3*Mobiy+a5*NodeComQuay，其表示網絡成員節點i加入以節點y為簇頭的簇的合適程度，其中：A（i，y）adapt值越小節點i越適合加入以節點y為簇頭的簇。節點y在對其全部鄰節點的A（i，y）adapt做對比后選擇A（i，y）adapt最小的σ-1個鄰居節點，向其發送簇頭通報消息。

節點y的鄰節點在接收簇頭通報消息后將做以下處理：首先設置一個定時器；在定時器有效時間段內若成員節點僅收到單獨一條簇頭通報消息，則向其回傳簇頭通報應答消息，并加入該簇；如果在定時器有效時間段內成員節點收到多條簇頭通報消息，那么該成員節點將對每個向其發送消息的簇頭節點計算A（i，x）adapt，并向所得A（i，x）adapt最小的簇頭節點發送簇頭通報應答消息，并加入該簇；

9）還未加入到簇中的節點均重復上述1）～8）步驟，直到網絡中所有節點都加入到所生成的各簇當中后，算法結束。

4.3算法基本特性分析

以下將主要從實現算法所需的相關信息是否易于獲取、以及其獲取是否會額外增加網絡負擔等方面，對本文提出的引入節點通信質量的網絡加權分簇算法（CQACA）主要特性進行分析：

相對鄰節點的平均距離Distany：在進行網絡維護獲取最小主控集過程中節點y將獲得與其一跳鄰節點yi的距離，再結合degry，各節點可以直接計算得到Distany，不會增加新的開銷和復雜度；

相對鄰節點的平均移動速度My-opp：鄰節點在周期發送的鄰居拓撲信息中將攜帶上自身在ΔT時間段內的平均速度信息Vi；節點y易得自身在ΔT時間段內的平均速度信息Vy，再結合degry，各節點可以直接計算得到My-opp，不會增加新的開銷和復雜度；

節點y的通信質量NodeComQuay：在無人平臺集群的移動Ad hoc網絡進行拓撲維護過程中，其獲取網絡最小主控集時成員就會獲取并周期更新該信息，因此本算法不會增加開銷和復雜度；

簇頭選取總權值Authorityy計算：成員通過所獲取的上述信息進行計算即可得到Authorityy；在完成自身的計算處理后，網絡成員將在本周期發送的鄰居拓撲信息攜帶上一周期的該信息，從而實現周期交互獲??；

節點加入簇：需交互簇頭通報消息、簇頭通報應答消息，這是由網絡分簇而帶來的新增維護類信息交互。因此，在算法設計中考慮需盡量提高信息交互效率。

①節點將比較所獲取的鄰節點的Authorityy權值，結合自身覆蓋度degry與最優覆蓋度σ的對比情況，決定自身如何發送簇頭通報消息；鄰節點在收到簇頭通報消息后進行判斷處理，向滿足條件的簇頭發送簇頭通報應答消息；

②當degry≤σ時，節點y將向其全部鄰節點發送簇頭通報消息；當degry>σ時，表示節點y有較多鄰節點，其覆蓋度很大。因此：根據y的鄰節點上報的A（i，y）adapt信息，選擇A（i，y）adapt最小的σ-1個鄰節點發送簇頭通報消息，該方法將有效減小簇頭通報消息的發送量；

③節點y的鄰節點收到簇頭通報消息后，將對每個向其發送消息的簇頭節點計算A（i，x）adapt，并向A（i，x）adapt最小的簇頭節點發送簇頭通報應答消息，并加入該簇。

五、結論

通過對無人平臺集群移動Ad hoc網絡特點及網絡分簇、維護管理需求的分析，本文提出了一種引入節點通信質量的網絡加權分簇算法（CQACA），并對算法原理和實現進行了詳細描述。該分簇算法既能確保網絡成員間信息盡量可靠、實時傳輸，還能使網絡的整體性能得到一定的均衡，從而能夠較好地滿足無人平臺集群移動Ad hoc網絡的應用通信需求。

參 考 文 獻

[1] 丁玲. 無線移動Ad Hoc網絡拓撲管理技術. 《電子科技大學碩士論文》. 2007： 12-18.

[2] Nelson Minar， KwindleHultman Kramer， Pattie Maes. Cooperating Mobi Agents for Dynamic Network Routing chapter 12[C].In： Alex Hayzeldoned Software Agent for Future Communications Systems， 1999： 36-43.

[3] Jahani S， Bagherpour M. A clustering algorithm for Mobi ad hoc networks based on spatial auto-correlation. International Symposium on Computer Networks and Distributed Systems， Tehran， 2011：136-141.