劉邈

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

【關鍵詞】 網(wǎng)絡分簇 通信質(zhì)量 網(wǎng)絡拓撲

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；

一、引言

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

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

二、無人平臺集群移動網(wǎng)絡特點

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

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

三、網(wǎng)絡拓撲與分簇

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

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

四、引入節(jié)點通信質(zhì)量的網(wǎng)絡加權分簇算法

4.1總體思路

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

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

4.2考慮節(jié)點通信質(zhì)量的加權分簇

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

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

首先，對節(jié)點通信質(zhì)量NodeComQuay進行定義，具體如下：

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

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

以下將描述引入節(jié)點通信質(zhì)量的網(wǎng)絡加權分簇算法（CQACA）：

1）計算節(jié)點y的覆蓋度：

①Δdegry：節(jié)點y與網(wǎng)絡中最優(yōu)覆蓋度的差距，該值越小則y的覆蓋度越接近最優(yōu)覆蓋度，即：節(jié)點y的覆蓋能力越好；

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

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

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

⑤NodeComQuay：節(jié)點通信質(zhì)量，NodeComQuay值越小表示節(jié)點y的通信質(zhì)量越好；

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

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

8）網(wǎng)絡成員節(jié)點加入簇中

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

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

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

4.3算法基本特性分析

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

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

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

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

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

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

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

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

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

五、結論

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

參 考 文 獻

[1] 丁玲. 無線移動Ad Hoc網(wǎng)絡拓撲管理技術. 《電子科技大學碩士論文》. 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.