分層Ad Hoc網(wǎng)絡(luò)的分群及群首選舉算法研究

楊健康，湯曉晨，陳穎穎

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

分層Ad Hoc網(wǎng)絡(luò)的分群及群首選舉算法研究

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

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

文章分析了戰(zhàn)術(shù)互聯(lián)網(wǎng)是典型的Ad Hoc網(wǎng)絡(luò)，其結(jié)構(gòu)導(dǎo)致層次及分群相對固定，可通過地址列表信息來完成群首的選舉，以維護(hù)特殊情況下的群穩(wěn)定性和網(wǎng)絡(luò)功能。

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

Ad Hoc（點對點）網(wǎng)絡(luò)具有網(wǎng)絡(luò)的自組織性、動態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、有限的無線傳輸帶寬及分布式網(wǎng)絡(luò)、單向無線信道等特點。Ad Hoc網(wǎng)絡(luò)中的所有節(jié)點作用相同，既可以作為主機(jī)發(fā)送接收信息，也可以作為路由器對數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)。Ad Hoc網(wǎng)絡(luò)可以應(yīng)用于無基礎(chǔ)設(shè)施的應(yīng)用環(huán)境，包括無線傳感器網(wǎng)絡(luò)、作戰(zhàn)與訓(xùn)練、搶險救災(zāi)、應(yīng)急事件處置、個人通信等。Ad Hoc網(wǎng)絡(luò)的主要研究包括信道接入、路由協(xié)議等，其中路由協(xié)議研究又是熱點。對于戰(zhàn)術(shù)互聯(lián)網(wǎng)等特殊環(huán)境下的Ad Hoc網(wǎng)絡(luò)，分群方法及群維護(hù)算法成為路由協(xié)議研究的重要內(nèi)容。

戰(zhàn)術(shù)互聯(lián)網(wǎng)作為Ad Hoc網(wǎng)絡(luò)，具有以下特點［1］：（1）無基礎(chǔ)性網(wǎng)絡(luò)；（2）節(jié)點資源的有限性；（3）無線通信介質(zhì)的不可靠性；（4）節(jié)點的移動性。

除此之外，戰(zhàn)術(shù)互聯(lián)網(wǎng)還具有如下特征：（1）信道速率低，一般為幾K到幾十K；（2）網(wǎng)絡(luò)覆蓋范圍大，一般大于40×40km；（3）節(jié)點的傳輸距離遠(yuǎn)，干線通信設(shè)備電臺可達(dá)10～20km；（4）節(jié)點密度較大，網(wǎng)絡(luò)覆蓋范圍的節(jié)點數(shù)量遠(yuǎn)大于一般應(yīng)用場景。

同時戰(zhàn)術(shù)互聯(lián)網(wǎng)環(huán)境中的大部分節(jié)點都是1跳或2跳可達(dá)的，節(jié)點的相對運動速率較低，網(wǎng)絡(luò)拓?fù)涞淖兓俾时鹊湫偷腁d Hoc網(wǎng)絡(luò)低［2］。因此，需要對現(xiàn)有的Ad Hoc路由協(xié)議針對戰(zhàn)術(shù)互聯(lián)網(wǎng)進(jìn)行改進(jìn)，以滿足其要求。由于作戰(zhàn)分隊本身是具有指揮層級的層次性結(jié)構(gòu)，即上級單位包含一定數(shù)量的下級單位，下級單位有唯一的上級單位，各個分隊及單位之間不會相互重疊?？山Y(jié)合該特點設(shè)計相應(yīng)的分群算法。

1　分群算法

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

根據(jù)Ad Hoc網(wǎng)絡(luò)的分群過程，分群算法與群維護(hù)算法是管理過程中對群的不同階段的管理。分群算法根據(jù)系統(tǒng)管理和運行要求，按照既定的規(guī)則將網(wǎng)絡(luò)劃分成互相連通且覆蓋各個節(jié)點的群組；分群過程結(jié)束時，網(wǎng)絡(luò)中各節(jié)點應(yīng)該已經(jīng)加入且唯一加入某個群。群維護(hù)算法是在網(wǎng)絡(luò)結(jié)構(gòu)或者節(jié)點狀態(tài)發(fā)生變化時更新群結(jié)構(gòu)，來保證網(wǎng)絡(luò)的正常運行，一般指分群過程結(jié)束之后即進(jìn)入群維護(hù)過程。

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

2　按編制的戰(zhàn)術(shù)互聯(lián)網(wǎng)分群方法

以營級分隊組網(wǎng)為例，基于編制的戰(zhàn)術(shù)互聯(lián)網(wǎng)無線通信網(wǎng)絡(luò)模型如圖1所示。

圖1　基于編制的營級戰(zhàn)術(shù)互聯(lián)網(wǎng)通信網(wǎng)絡(luò)模型

（1）營級。包括營長指揮車：營長指揮車；醫(yī)療車；運輸車；服務(wù)車等。營指揮車是網(wǎng)絡(luò)管理的頂層，是網(wǎng)絡(luò)管理的核心，負(fù)責(zé)監(jiān)控網(wǎng)絡(luò)運行狀態(tài)，并在運行過程中對關(guān)鍵事件進(jìn)行分析、處理和調(diào)度。營指揮車一般是相對固定的節(jié)點。營網(wǎng)是網(wǎng)絡(luò)的骨干，通信帶寬設(shè)置最大，同時該層不對數(shù)據(jù)包/幀進(jìn)行任何處理，以提高包交換的速度。核心層的主要目的是實現(xiàn)連排節(jié)點與營指揮網(wǎng)絡(luò)以及各連排節(jié)點之間的高速連接。

（2）連排級。包括各連連長車和各排排長車，作為各群的群首，即節(jié)點車。連排指揮車作為一級，是營指揮級和作戰(zhàn)車輛的連接點［6］，同時對網(wǎng)絡(luò)的邊界進(jìn)行定義，通常是靜態(tài)和動態(tài)路由選擇協(xié)議之間的分界點。對數(shù)據(jù)包/幀的處理應(yīng)該在該層完成。數(shù)據(jù)包的處理、路由選擇、策略路由是該級的主要功能。

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

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

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

（1）連網(wǎng)各群的群首節(jié)點（連排車）定期廣播聲明消息，該消息的內(nèi)容包含網(wǎng)絡(luò)標(biāo)識和群首地址。聲明消息的作用是向網(wǎng)內(nèi)其他節(jié)點（戰(zhàn)斗車）通報該群中已存在群首節(jié)點，且始終維護(hù)全網(wǎng)節(jié)點的地址使用情況表（Address In Used Table，AIUT），該表的版本號越大，則表中的信息越準(zhǔn)確。

（2）若該群中某一節(jié)點（如Tank5）未收到聲明消息，則認(rèn)為網(wǎng)絡(luò)中無群首，它在等待隨機(jī)時間后進(jìn)行全網(wǎng)洪泛選舉消息，聲明它希望成為該群臨時新群首。

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

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

這樣，新群首選舉過程就是尋找具有最高AIUT版本的節(jié)點的過程。如圖1中網(wǎng)絡(luò)，設(shè)Plotoon2失效后，選舉Tank5作為新群首，如圖2所示。

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

4　仿真結(jié)果分析

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

圖4　UDP Packet Delay

在群首節(jié)點更換后，網(wǎng)絡(luò)通過競爭選擇了新的群首。在圖5仿真實驗中可以看出，3個節(jié)點的誤比特率在節(jié)點更換時同時達(dá)到峰值，但隨著新的拓?fù)渎酚傻慕?，誤比特率呈下降的趨勢，在一定時間后，即恢復(fù)到正常的水平。

圖5　Bit Error Rate

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

［1］鄭少仁，王海濤，趙志峰.Ad Hoc網(wǎng)絡(luò)技術(shù)［M］.北京：人民郵電出版社，2005.

［2］曹志剛.現(xiàn)代通信原理［M］.北京：清華大學(xué)出版社，2002.

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

［4］沈中.無線Ad Hoc網(wǎng)絡(luò)拓?fù)涔芾硌芯浚跠］.西安：西安電子科技大學(xué)，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.戰(zhàn)術(shù)無線通信與網(wǎng)絡(luò)—設(shè)計概念與挑戰(zhàn)［M］.曾浩洋，田永春，譯.北京：國防工業(yè)出版社，2014.

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

［8］霍景河.網(wǎng)絡(luò)仿真VRNET基礎(chǔ)與開發(fā)［M］.北京：北京交通大學(xué)出版社，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— ），男，河北深州，碩士，講師；研究方向：戰(zhàn)術(shù)通信技術(shù)及應(yīng)用。