分層Ad Hoc網絡的分群及群首選舉算法研究

楊健康，湯曉晨，陳穎穎

（1.裝甲兵工程學院 信息工程系，北京　100072；2.63996部隊，北京　100094）

分層Ad Hoc網絡的分群及群首選舉算法研究

楊健康1，湯曉晨2，陳穎穎1

（1.裝甲兵工程學院 信息工程系，北京100072；2.63996部隊，北京100094）

文章分析了戰術互聯網是典型的Ad Hoc網絡，其結構導致層次及分群相對固定，可通過地址列表信息來完成群首的選舉，以維護特殊情況下的群穩定性和網絡功能。

Ad Hoc；群首選舉；分群算法

Ad Hoc（點對點）網絡具有網絡的自組織性、動態的網絡拓撲結構、有限的無線傳輸帶寬及分布式網絡、單向無線信道等特點。Ad Hoc網絡中的所有節點作用相同，既可以作為主機發送接收信息，也可以作為路由器對數據進行轉發。Ad Hoc網絡可以應用于無基礎設施的應用環境，包括無線傳感器網絡、作戰與訓練、搶險救災、應急事件處置、個人通信等。Ad Hoc網絡的主要研究包括信道接入、路由協議等，其中路由協議研究又是熱點。對于戰術互聯網等特殊環境下的Ad Hoc網絡，分群方法及群維護算法成為路由協議研究的重要內容。

戰術互聯網作為Ad Hoc網絡，具有以下特點［1］：（1）無基礎性網絡；（2）節點資源的有限性；（3）無線通信介質的不可靠性；（4）節點的移動性。

除此之外，戰術互聯網還具有如下特征：（1）信道速率低，一般為幾K到幾十K；（2）網絡覆蓋范圍大，一般大于40×40km；（3）節點的傳輸距離遠，干線通信設備電臺可達10～20km；（4）節點密度較大，網絡覆蓋范圍的節點數量遠大于一般應用場景。

同時戰術互聯網環境中的大部分節點都是1跳或2跳可達的，節點的相對運動速率較低，網絡拓撲的變化速率比典型的Ad Hoc網絡低［2］。因此，需要對現有的Ad Hoc路由協議針對戰術互聯網進行改進，以滿足其要求。由于作戰分隊本身是具有指揮層級的層次性結構，即上級單位包含一定數量的下級單位，下級單位有唯一的上級單位，各個分隊及單位之間不會相互重疊。可結合該特點設計相應的分群算法。

1　分群算法

根據Ad hoc網絡固有的特性，以及對網絡信息開銷和節點移動性的考慮，Ad Hoc網絡更適合采用分層式管理［3］，它是由管理者（Manager）、群首（Cluster Head）和代理（Agent）3級組成。最底層是代理，每個代理管理所在節點及周邊鏈路等；多個代理形成一個群并由群首管理；群首則由網絡管理者管理［4—5］。

根據Ad Hoc網絡的分群過程，分群算法與群維護算法是管理過程中對群的不同階段的管理。分群算法根據系統管理和運行要求，按照既定的規則將網絡劃分成互相連通且覆蓋各個節點的群組；分群過程結束時，網絡中各節點應該已經加入且唯一加入某個群。群維護算法是在網絡結構或者節點狀態發生變化時更新群結構，來保證網絡的正常運行，一般指分群過程結束之后即進入群維護過程。

群的大小是分群過程的重要信息，一般群的大小根據各節點的傳輸功率和節點自身的特性來決定。其目標是盡量減少計算和通信開銷來構造和維護網絡群集合，該集合能夠覆蓋整個網絡，其中構造群集合主要由分群過程完成，維護群集合主要由群維護過程完成，且該群集合具有較好的協議兼容性并支持網絡資源管理。

2　按編制的戰術互聯網分群方法

以營級分隊組網為例，基于編制的戰術互聯網無線通信網絡模型如圖1所示。

圖1　基于編制的營級戰術互聯網通信網絡模型

（1）營級。包括營長指揮車：營長指揮車；醫療車；運輸車；服務車等。營指揮車是網絡管理的頂層，是網絡管理的核心，負責監控網絡運行狀態，并在運行過程中對關鍵事件進行分析、處理和調度。營指揮車一般是相對固定的節點。營網是網絡的骨干，通信帶寬設置最大，同時該層不對數據包/幀進行任何處理，以提高包交換的速度。核心層的主要目的是實現連排節點與營指揮網絡以及各連排節點之間的高速連接。

（2）連排級。包括各連連長車和各排排長車，作為各群的群首，即節點車。連排指揮車作為一級，是營指揮級和作戰車輛的連接點［6］，同時對網絡的邊界進行定義，通常是靜態和動態路由選擇協議之間的分界點。對數據包/幀的處理應該在該層完成。數據包的處理、路由選擇、策略路由是該級的主要功能。

（3）作戰車輛。包括各連的作戰車輛，各連作戰車輛只能在自己的子網內和本連的車輛進行通信以協同作戰，接受直接上級即連排指揮車的領導，從連排指揮車接收戰場態勢及作戰命令。若某作戰車輛有特殊情況需要向營指匯報或是和他連的作戰車輛通信，則需要通過上級節點尋找路由，將消息轉發出去。因此，這些節點需要實現共享帶寬、交換帶寬等功能。

3　基于地址表的群首選舉方法

上述分級方式遵從了實際作戰編制，指揮體系明確，終端節點在自己的子網內通信。由于需要和另一子網交互的信息量不大，通過轉發尋找路由的方式能夠基本完成［7］。但是，考慮到實際作戰情況，即電磁干擾、以及戰損的情況下，一旦某一連的連排指揮車被干擾或是擊毀，這一個連的作戰車輛就會進入接受不到命令，不清楚戰場態勢的危險情況下，直接導致一個連戰斗力的丟失。因此，需要對這樣的分級網絡進行改進。改進的過程如下：

（1）連網各群的群首節點（連排車）定期廣播聲明消息，該消息的內容包含網絡標識和群首地址。聲明消息的作用是向網內其他節點（戰斗車）通報該群中已存在群首節點，且始終維護全網節點的地址使用情況表（Address In Used Table，AIUT），該表的版本號越大，則表中的信息越準確。

（2）若該群中某一節點（如Tank5）未收到聲明消息，則認為網絡中無群首，它在等待隨機時間后進行全網洪泛選舉消息，聲明它希望成為該群臨時新群首。

（3）收到選舉消息的節點將自己的AIUT版本號與收到的版本號比較，若自己的版本號大于收到的版本號，則標記自己是臨時新群首；若兩者等，則選擇具有最高地址的節點作為臨時新群首；若自己的版本號小于收到的版本號，則認為Tank5節點就是臨時新群首。

（4）如果在一段時間內臨時的新群首沒有收到其他節點的選舉消息，則自己成為該群的群首，并啟動預先存儲的上級網（即營指揮網）的路由表進行通信。

這樣，新群首選舉過程就是尋找具有最高AIUT版本的節點的過程。如圖1中網絡，設Plotoon2失效后，選舉Tank5作為新群首，如圖2所示。

圖2　通過版本選舉Tank5為新群首

4　仿真結果分析

按圖1結構采用集成網絡仿真（Virtual Reality Network，VRNET）環境建立仿真模型［8］，設Company1損毀的情況下，按照使用備選路由直接和營指揮車通信的狀況下Tank1的UDP交付率和延遲情況如圖3—4所示。

圖4　UDP Packet Delay

在群首節點更換后，網絡通過競爭選擇了新的群首。在圖5仿真實驗中可以看出，3個節點的誤比特率在節點更換時同時達到峰值，但隨著新的拓撲路由的建立，誤比特率呈下降的趨勢，在一定時間后，即恢復到正常的水平。

圖5　Bit Error Rate

另外，在仿真中發現，節點移動得越快，場景的移動性越大。隨著節點移動速率的提高，分組遞交率有所下降，因為提高節點移動速率會使路由失效得更快，從而導致部分分組因找不到路由而被丟棄。但分組抵達率下降的幅度并不是很大，成功率大于70%。

［1］鄭少仁，王海濤，趙志峰.Ad Hoc網絡技術［M］.北京：人民郵電出版社，2005.

［2］曹志剛.現代通信原理［M］.北京：清華大學出版社，2002.

［3］馬志欣，趙鼎新，謝顯中，等.車載通信網中基于DSR分層機制的移動代理路由策略研究［J］.重慶郵電大學學報（自然科學版），2011 （2）：207-213.

［4］沈中.無線Ad Hoc網絡拓撲管理研究［D］.西安：西安電子科技大學，2005.

［5］HEN W C，JAIN N，SINGH S.ANMP：Ad Hoc Network Management Protocol［J］.IEEE Journal on selected aeras in communications，1999（8）：1506-1531.

［6］George F.Elmasry.戰術無線通信與網絡—設計概念與挑戰［M］.曾浩洋，田永春，譯.北京：國防工業出版社，2014.

［7］張冬辰，周吉.軍事通信［M］.北京：國防工業出版社，2008.

［8］霍景河.網絡仿真VRNET基礎與開發［M］.北京：北京交通大學出版社，2016.

Research of clustering and group leader election algorithmon hierarchy Ad Hoc network

Yang Jiankang1， Tang Xiaochen2， Chen Yingying1
（1. Department of Information Engineering， Academy of Armored Forces Engineering， Beijing 100072， China；
2. Troop No. 63996 of PLA， Beijing 100094， China）

Tactical Networks is typical Ad Hoc Network. Its structure leads to relative fixation for hierarchy and clustering. In order to maintain the cluster stabilization and network function in particular cases， Group leader election can be reached by address list message. Key words: Ad Hoc； Group leader election；clustering algorithm

楊健康（1978— ），男，河北深州，碩士，講師；研究方向：戰術通信技術及應用。