無人平臺移動網(wǎng)絡(luò)分簇研究

劉邈

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

【關(guān)鍵詞】 網(wǎng)絡(luò)分簇 通信質(zhì)量 網(wǎng)絡(luò)拓?fù)?/p>

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

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

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

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

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

三、網(wǎng)絡(luò)拓?fù)渑c分簇

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

移動Ad hoc網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)鋸膶哟侮P(guān)系上看包括以下兩種大的類別：節(jié)點隨機(jī)扁平分布方式、分層分布方式。常用的典型Ad hoc網(wǎng)絡(luò)其拓?fù)湟怨?jié)點隨機(jī)扁平分布方式居多；較多應(yīng)用于軍事應(yīng)用戰(zhàn)場環(huán)境的無人平臺集群移動Ad hoc網(wǎng)絡(luò)會較多地形成分層分布式網(wǎng)絡(luò)拓?fù)?，這是受到部隊作戰(zhàn)指揮層次化特點影響導(dǎo)致的。典型的分層分布式Ad hoc網(wǎng)絡(luò)拓?fù)淙鐖D2所示。

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

4.1總體思路

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

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

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

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

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

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

假設(shè)節(jié)點y到其n個鄰居節(jié)點的丟包率分別為e1，e2，…，en，在網(wǎng)絡(luò)運(yùn)行過程中，丟包率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ù)為：隨機(jī)變量Xi；n個鄰節(jié)點都成功接收到其發(fā)送的消息時，節(jié)點y所需發(fā)送的次數(shù)為：隨機(jī)變量Y，那么：

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

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

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

①Δdegry：節(jié)點y與網(wǎng)絡(luò)中最優(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ì)量越好；

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

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

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

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

4.3算法基本特性分析

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

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

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

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

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

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

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

②當(dāng)degry≤σ時，節(jié)點y將向其全部鄰節(jié)點發(fā)送簇頭通報消息；當(dāng)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ā)送簇頭通報應(yīng)答消息，并加入該簇。

五、結(jié)論

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

參 考 文 獻(xiàn)

[1] 丁玲. 無線移動Ad Hoc網(wǎng)絡(luò)拓?fù)涔芾砑夹g(shù). 《電子科技大學(xué)碩士論文》. 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.