楊健康，湯曉晨，陳穎穎

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

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

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

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

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

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

Ad Hoc（點(diǎn)對(duì)點(diǎn)）網(wǎng)絡(luò)具有網(wǎng)絡(luò)的自組織性、動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、有限的無線傳輸帶寬及分布式網(wǎng)絡(luò)、單向無線信道等特點(diǎn)。Ad Hoc網(wǎng)絡(luò)中的所有節(jié)點(diǎn)作用相同，既可以作為主機(jī)發(fā)送接收信息，也可以作為路由器對(duì)數(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)練、搶險(xiǎn)救災(zāi)、應(yīng)急事件處置、個(gè)人通信等。Ad Hoc網(wǎng)絡(luò)的主要研究包括信道接入、路由協(xié)議等，其中路由協(xié)議研究又是熱點(diǎn)。對(duì)于戰(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ò)，具有以下特點(diǎn)［1］：（1）無基礎(chǔ)性網(wǎng)絡(luò)；（2）節(jié)點(diǎn)資源的有限性；（3）無線通信介質(zhì)的不可靠性；（4）節(jié)點(diǎn)的移動(dòng)性。

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

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

1　分群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這樣，新群首選舉過程就是尋找具有最高AIUT版本的節(jié)點(diǎn)的過程。如圖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損毀的情況下，按照使用備選路由直接和營(yíng)指揮車通信的狀況下Tank1的UDP交付率和延遲情況如圖3—4所示。

圖4　UDP Packet Delay

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

圖5　Bit Error Rate

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

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

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

［3］馬志欣，趙鼎新，謝顯中，等.車載通信網(wǎng)中基于DSR分層機(jī)制的移動(dòng)代理路由策略研究［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(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è)計(jì)概念與挑戰(zhàn)［M］.曾浩洋，田永春，譯.北京：國(guó)防工業(yè)出版社，2014.

［7］張冬辰，周吉.軍事通信［M］.北京：國(guó)防工業(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)用。