一種基于聚類算法的ETX輔助無(wú)人機(jī)AODV路由協(xié)議

郭少雄,宋志群,李 勇,劉玉濤

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所,河北石家莊 050081;2.通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室,河北石家莊 050081)

無(wú)人機(jī)被廣泛應(yīng)用于交通管理[1-2]、監(jiān)控[3]、邊境巡邏[4]、災(zāi)難救援[5-6]等領(lǐng)域。由于無(wú)人機(jī)的高移動(dòng)性、拓?fù)渥兓闹芷谛?、能量約束和通信范圍有限,其通信網(wǎng)絡(luò)內(nèi)鏈路斷裂和數(shù)據(jù)包丟失現(xiàn)象較其他無(wú)線通信鏈路更加頻繁。在飛行自組網(wǎng)(flying ad hoc network,FANET)中,需要穩(wěn)定的數(shù)據(jù)傳輸路徑來(lái)保證網(wǎng)絡(luò)內(nèi)高效可靠的通信。因此,路由協(xié)議設(shè)計(jì)是FANET中的一個(gè)重要問(wèn)題,開(kāi)發(fā)低開(kāi)銷、低延時(shí)的高效路由協(xié)議成為研究的熱點(diǎn)和難點(diǎn)[7]。

無(wú)線自組網(wǎng)按需平面距離向量(ad hoc on-demand distant vector,AODV)路由協(xié)議以其方便高效的性能被廣泛應(yīng)用于無(wú)人機(jī)自組織網(wǎng)絡(luò)[8],網(wǎng)絡(luò)中的節(jié)點(diǎn)并不存儲(chǔ)網(wǎng)絡(luò)整體的拓?fù)浣Y(jié)構(gòu),僅當(dāng)需要發(fā)送信息時(shí)才會(huì)尋找路由路徑,但在發(fā)現(xiàn)、生成路由時(shí)會(huì)產(chǎn)生較高的延遲,跳數(shù)最短路由機(jī)制也存在一定的弊端。

針對(duì)上述問(wèn)題,許多學(xué)者基于AODV路由協(xié)議提出了更加穩(wěn)定高效的改進(jìn)協(xié)議。SARKAR等[9]提出了一種基于增強(qiáng)蟻群優(yōu)化算法的Enhanced-Ant-AODV路由協(xié)議,利用信息素判別最優(yōu)路徑,提供了有效的QoS保障;LI等[10]提出了一種基于模糊邏輯輔助的FL-AODV路由協(xié)議,提高了路徑的可靠性;BAMHDI等[11]提出了一種基于節(jié)點(diǎn)密度的DP-AODV路由協(xié)議,通過(guò)動(dòng)態(tài)調(diào)整傳輸數(shù)據(jù)包所需的功率,從而減少網(wǎng)絡(luò)的功率總需求;SHAFI等[12]提出了一種基于機(jī)器學(xué)習(xí)的ML-AODV路由協(xié)議,用來(lái)檢測(cè)泛洪黑洞攻擊,提高了網(wǎng)絡(luò)的安全性。

期望傳輸次數(shù)(expected transmission count,ETX)度量是目前使用率較高的路由度量值之一。MALNAR等[13]最早基于網(wǎng)絡(luò)仿真平臺(tái)NS3實(shí)現(xiàn)了AODV路由協(xié)議的ETX機(jī)制改進(jìn),并在P-AODV路由協(xié)議的基礎(chǔ)上結(jié)合ETX機(jī)制提出了一種ND-AODV-ETX路由協(xié)議,在端到端延遲和丟包率方面提高了協(xié)議的性能,但也帶來(lái)了較大的路由開(kāi)銷;HUANG等[14]提出了一種AODV-NLS-AODV路由協(xié)議,但是也沒(méi)有考慮控制開(kāi)銷的問(wèn)題。事實(shí)上,ETX機(jī)制能夠很好地平衡以最小跳數(shù)選取路徑帶來(lái)的鏈路質(zhì)量問(wèn)題,提高網(wǎng)絡(luò)的吞吐量,但因增加了探測(cè)包,導(dǎo)致傳輸時(shí)延和路由開(kāi)銷也隨之增加,AODV路由協(xié)議的泛洪廣播更是加重了這一問(wèn)題。如圖1所示,當(dāng)源節(jié)點(diǎn)S尋找到達(dá)目的節(jié)點(diǎn)D的路徑時(shí),網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都廣播路由請(qǐng)求消息,這對(duì)于有限的無(wú)線資源是一種浪費(fèi)。

圖1 泛洪廣播Fig.1 Flooding broadcast

本文在AODV-ETX路由協(xié)議的基礎(chǔ)上,結(jié)合K-means聚類算法,提出了K-AODV-ETX路由協(xié)議,通過(guò)聚類特征選擇RREQ消息轉(zhuǎn)發(fā)的最佳集群,減少盲目泛洪廣播帶來(lái)的資源浪費(fèi),縮短路徑發(fā)現(xiàn)時(shí)間,有效降低協(xié)議的路由開(kāi)銷與端到端時(shí)延。

為了驗(yàn)證性能,將K-AODV-ETX路由協(xié)議與AODV路由協(xié)議、AODV-ETX路由協(xié)議、ND-AODV-ETX路由協(xié)議進(jìn)行比較,其中AODV-ETX路由協(xié)議與ND-AODV-ETX路由協(xié)議是分別在AODV路由協(xié)議、ND-AODV路由協(xié)議的基礎(chǔ)上改進(jìn)而來(lái)的。

1 算法設(shè)計(jì)

1.1 ETX機(jī)制原理

AODV-ETX路由協(xié)議、ND-AODV-ETX路由協(xié)議均采用ETX機(jī)制。ETX機(jī)制通過(guò)一種消息探針來(lái)監(jiān)控鏈路上的數(shù)據(jù)包預(yù)期傳輸數(shù)。為了找出傳播值最小的傳播鏈路,AODV路由協(xié)議中傳統(tǒng)的跳數(shù)最短路徑選擇機(jī)制將被ETX機(jī)制取代。當(dāng)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的通信鏈路建立時(shí),通過(guò)計(jì)算鏈路正向傳輸成功的概率和反向重傳成功的概率來(lái)得到節(jié)點(diǎn)鏈路中的ETX值。

ETX定義為

(1)

式(1)中:R為網(wǎng)絡(luò)2個(gè)節(jié)點(diǎn)之間的路由;η為路由R的一跳;φ(η)為轉(zhuǎn)發(fā)接收比;ρ(η)為反向接收比,即對(duì)應(yīng)ACK報(bào)文被成功接收的概率。

接收比常由鏈路探測(cè)報(bào)文(link probe packet,LPP)估計(jì):

(2)

式(2)中:

(3)

α為鏈路質(zhì)量老化參數(shù),α越大,接收比的平均時(shí)間越長(zhǎng),從而產(chǎn)生更穩(wěn)定、可靠的估計(jì)。

鏈路的ETX值由在該鏈路上發(fā)送數(shù)據(jù)包所需的預(yù)期傳輸數(shù)表示,包括重傳。如果pf表示報(bào)文成功傳輸?shù)母怕?pr表示ACK報(bào)文成功接收的概率,那么報(bào)文成功發(fā)送并確認(rèn)的概率為pf×pr,則鏈路l的ETX值可以表示為

ETXl=1/(pf×pr)。

(4)

網(wǎng)絡(luò)中節(jié)點(diǎn)以平均周期τ廣播鏈路探測(cè)消息報(bào)文LPP,概率Pf和Pr都可以通過(guò)LPP來(lái)測(cè)量,周期τ內(nèi)最大抖動(dòng)設(shè)置為10%來(lái)避免意外同步的產(chǎn)生。每個(gè)節(jié)點(diǎn)將在最近w秒內(nèi)接收到的LPP數(shù)量記錄在自己的路由表中,并根據(jù)式(5)計(jì)算任意時(shí)刻t下的概率:

(5)

式(5)中:count(t-w,t)為在窗口w期間實(shí)際接收到的LPP數(shù)量;w/τ為在此窗口期間應(yīng)該接收的LPP數(shù)量。如在鏈路X→Y上,X通過(guò)計(jì)算從Y成功接收到的LPP來(lái)測(cè)量pr,節(jié)點(diǎn)Y發(fā)送的每個(gè)LPP都包含最近w秒內(nèi)從X接收到的LPP數(shù)量。節(jié)點(diǎn)X根據(jù)w秒內(nèi)接收到的LPP數(shù)量來(lái)計(jì)算pr,路由r的度量為路由中每個(gè)鏈路l的ETX值的和:

(6)

1.2 K-means聚類算法

相比于AODV路由協(xié)議的跳數(shù)最小路徑選擇機(jī)制,ETX機(jī)制提供了一種有效提高自組織網(wǎng)絡(luò)吞吐量的方法,但由于探測(cè)包LPP的存在,增加了網(wǎng)絡(luò)的控制報(bào)文,從而增大了路由開(kāi)銷和時(shí)延,基于這一問(wèn)題,本文考慮采用聚類算法思想控制開(kāi)銷,減小時(shí)延。

聚類算法是一種有效的特征分類方法[15],并已被應(yīng)用到路由協(xié)議中,許多基于聚類算法的路由協(xié)議被提出[16-17],現(xiàn)階段大部分的聚類算法都應(yīng)用于分簇協(xié)議的設(shè)計(jì)與應(yīng)用,而本文旨在基于聚類算法的分類思想將FANET中的節(jié)點(diǎn)進(jìn)行特征分類。

執(zhí)行聚類算法后,分布在一定范圍內(nèi)的節(jié)點(diǎn)根據(jù)特征被分類,如圖2、圖3所示,其中圖3中不同顏色代表不同的類,當(dāng)路由發(fā)現(xiàn)過(guò)程觸發(fā)時(shí),改變RREQ消息泛洪廣播機(jī)制,沿著特定無(wú)人機(jī)節(jié)點(diǎn)集群傳播。

圖2 節(jié)點(diǎn)分布情況Fig.2 Node distribution

圖3 K-means聚類后節(jié)點(diǎn)分布情況Fig.3 Node distribution after K-means algorithm

算法選擇初始聚類數(shù)量K,目標(biāo)是將1≤j≤N的點(diǎn)集合Kj重新組織成K個(gè)聚類。為此,采用K-means聚類算法隨機(jī)選取點(diǎn)xi作為質(zhì)心,其中1≤i≤K,每個(gè)質(zhì)心屬于一個(gè)聚類C。然后,算法將數(shù)據(jù)集中的每個(gè)點(diǎn)分配到最近的質(zhì)心,該過(guò)程基于距離目標(biāo)函數(shù),該函數(shù)計(jì)算所有聚類中所有距離的平方和,利用式(7)進(jìn)行計(jì)算:

(7)

式(7)中:d(xj,ui)=|xj-ui|2,其為該點(diǎn)到聚類質(zhì)心的距離;xj為該點(diǎn)的位置;ui為i=1,2,…,K時(shí)質(zhì)心的位置,K是簇的個(gè)數(shù)。

如圖2所示,在分配完每個(gè)聚類中的點(diǎn)后,K-means算法使用式(8)更新每個(gè)質(zhì)心的位置:

(8)

在本文中,K-means聚類中使用的聚類特征有3個(gè),網(wǎng)絡(luò)中源節(jié)點(diǎn)基于鄰居的聚類特征來(lái)選擇最優(yōu)聚類進(jìn)行消息轉(zhuǎn)發(fā)。

1)到目的節(jié)點(diǎn)的跳數(shù) 到目的節(jié)點(diǎn)的跳數(shù)越小,路由越短,路由發(fā)現(xiàn)的時(shí)間越短。

2)錯(cuò)誤傳輸次數(shù) 節(jié)點(diǎn)錯(cuò)誤傳輸?shù)拇螖?shù)越少,節(jié)點(diǎn)的傳輸越可靠,則經(jīng)過(guò)此節(jié)點(diǎn)的鏈路質(zhì)量高,有助于提高吞吐量和數(shù)據(jù)投遞率。

3)節(jié)點(diǎn)可用緩沖空間 節(jié)點(diǎn)的可用緩沖空間越大,表示節(jié)點(diǎn)處的網(wǎng)絡(luò)擁塞情況越輕,數(shù)據(jù)包經(jīng)過(guò)此處不容易發(fā)生擁塞,有助于提高網(wǎng)絡(luò)的吞吐量。

2 協(xié)議工作流程

K-AODV-ETX路由協(xié)議的工作流程主要分為2步:第1步,在網(wǎng)絡(luò)中執(zhí)行K-means聚類算法對(duì)節(jié)點(diǎn)進(jìn)行分類處理,選擇合理的集群進(jìn)行源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的消息報(bào)文轉(zhuǎn)發(fā);第2步,執(zhí)行路由發(fā)現(xiàn)過(guò)程,與AODV-ETX路由協(xié)議相同。

2.1 轉(zhuǎn)發(fā)集群選擇

K-means聚類算法的偽碼如下。

輸入:質(zhì)心數(shù)量K;節(jié)點(diǎn)集合N;隨機(jī)分配給質(zhì)心的列表Ck

輸出:具有質(zhì)心的集群

Begin

1.Repeat

2.ForN個(gè)數(shù)據(jù)點(diǎn),do

3.使用式(7)計(jì)算數(shù)據(jù)點(diǎn)和每個(gè)聚類的質(zhì)心之間的距離

4.將數(shù)據(jù)點(diǎn)指定給最近的質(zhì)心

5.Endfor

6.ForCk中的每個(gè)集群do

7.使用式(8)計(jì)算新的質(zhì)心位置

8.Endfor

9.Until所有數(shù)據(jù)點(diǎn)都屬于一個(gè)集群或達(dá)到最大迭代次數(shù)

End

K-means聚類算法流程如圖4所示。

圖4 K-means聚類算法流程Fig.4 Process of K-means clustering algorithm

為了收集網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)信息從而確定轉(zhuǎn)發(fā)集群,利用網(wǎng)絡(luò)仿真軟件NS3,向AODV協(xié)議類中添加新字段,具體如下:

在“RREPHeader”和“RoutingTableEntry”類中增加m_txErrorCount(錯(cuò)誤傳輸計(jì)數(shù)),m_freeSpace(緩沖空間),m_positionX(節(jié)點(diǎn)橫坐標(biāo)),m_positionY(節(jié)點(diǎn)縱坐標(biāo))字段,同時(shí)在執(zhí)行文件中新增協(xié)議文件aodvKmeans-routing-protocol.h和路由表文件aodvKmeans-rtable.h來(lái)進(jìn)行K-AODV-ETX路由協(xié)議的實(shí)現(xiàn)。

2.2 路徑選擇

K-AODV-ETX路由協(xié)議的路由發(fā)現(xiàn)與維護(hù)過(guò)程與AODV協(xié)議基本相同,不同的是采用ETX機(jī)制進(jìn)行路由選擇與判別,為此,對(duì)協(xié)議的RREQ與RREP消息報(bào)文進(jìn)行修改,如圖5和圖6所示。

類型JRGDU保留跳數(shù)RREQ ID目的節(jié)點(diǎn)序列號(hào)路由請(qǐng)求RREQ源節(jié)點(diǎn)的IP地址壽命ETX

類型RA保留前綴長(zhǎng)度多跳轉(zhuǎn)發(fā)計(jì)數(shù)器目的節(jié)點(diǎn)IP地址目的節(jié)點(diǎn)序列號(hào)路由請(qǐng)求RREQ源節(jié)點(diǎn)的IP地址壽命ETX

從圖5、圖6可知,相比于原RREQ和RREP包格式,改進(jìn)的RREQ和RREP均增加了ETX項(xiàng),用以路徑判別。

首先,每個(gè)路由表項(xiàng)都使用ETX字段展開(kāi)。在AODV路由協(xié)議中,路由表項(xiàng)是按目的地分類的。如果到某個(gè)目的地有多條路由,則按跳數(shù)對(duì)路由進(jìn)行分類,跳數(shù)最小的路由為最佳路由。在AODV-ETX路由協(xié)議中,根據(jù)路由的ETX值對(duì)路由進(jìn)行分類,ETX值最小的路由為最佳路由。如果存在多個(gè)具有相同ETX值的路由,則再以跳數(shù)最小的路由為最佳。

當(dāng)源節(jié)點(diǎn)S進(jìn)行路由發(fā)現(xiàn)過(guò)程廣播RREQ消息時(shí),ETX的初始值設(shè)置為0,此后ETX字段的處理方式與跳數(shù)類似。即RREQ轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)時(shí),每個(gè)節(jié)點(diǎn)的ETX字段按照式(6)進(jìn)行更新。發(fā)送RREP報(bào)文的原理與之相同。ETX值是累積的,通過(guò)比較不同路徑的ETX值之和選擇路徑。

原AODV路由協(xié)議中的最小跳數(shù)機(jī)制下的RREQ和RREP消息傳播方式和本文提出的K-AODV-ETX路由協(xié)議ETX機(jī)制下的RREQ和RREP消息傳播方式分別如圖7、圖8所示:

圖7 最小跳數(shù)機(jī)制下的消息傳播Fig.7 Message propagation with minimum hop count mechanism

圖8 ETX機(jī)制下的消息傳播Fig.8 Message propagation under the ETX mechanism

如圖7所示,AODV路由協(xié)議采用跳數(shù)最小機(jī)制選擇路徑,RREQ消息每轉(zhuǎn)發(fā)1次,其路由表項(xiàng)中的跳數(shù)項(xiàng)則加1,節(jié)點(diǎn)A廣播RREQ消息報(bào)文,節(jié)點(diǎn)C和節(jié)點(diǎn)B均收到,隨后節(jié)點(diǎn)C和節(jié)點(diǎn)B廣播,節(jié)點(diǎn)B收到來(lái)自節(jié)點(diǎn)C的RREQ消息,與自身路由表更新過(guò)的跳數(shù)進(jìn)行比較,對(duì)節(jié)點(diǎn)C的RREQ消息進(jìn)行舍棄,直至目的節(jié)點(diǎn)D收到RREQ消息,并發(fā)送RREP消息建立正向傳輸路徑,S—A—C—B—D跳數(shù)較大,采用S—A—B—D進(jìn)行數(shù)據(jù)傳輸。

在ETX機(jī)制下,鏈路的ETX值之和越小,鏈路的質(zhì)量越好,因此K-AODV-ETX路由協(xié)議選擇ETX值之和最小的鏈路進(jìn)行數(shù)據(jù)傳輸,如在圖8中,當(dāng)鏈路A—C—B的ETX值之和小于A—B鏈路的ETX值時(shí),雖然A—B鏈路的跳數(shù)較小,但節(jié)點(diǎn)B仍會(huì)舍棄來(lái)自節(jié)點(diǎn)A的RREQ消息,采用鏈路S—A—C—B—D進(jìn)行數(shù)據(jù)傳輸。

3 仿真設(shè)置與分析

3.1 仿真環(huán)境和仿真參數(shù)介紹

本文采用網(wǎng)絡(luò)仿真軟件NS3進(jìn)行仿真,仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

為了衡量K-AODV-ETX路由協(xié)議的網(wǎng)絡(luò)性能,選取了以下3個(gè)仿真指標(biāo)。

1)數(shù)據(jù)包投遞率(packet delivery ratio,PDR) PDR為目的節(jié)點(diǎn)接收到的數(shù)據(jù)包個(gè)數(shù)與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包個(gè)數(shù)之比,反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?投遞率越高,協(xié)議的可靠性越大。

(9)

2)端到端的平均時(shí)延 它包括路由查找時(shí)延、數(shù)據(jù)包在接口隊(duì)列中的等待時(shí)延、傳輸時(shí)延及MAC層的重傳時(shí)延,其反映了路由有效性,尤其對(duì)語(yǔ)音消息來(lái)說(shuō),時(shí)延太大會(huì)嚴(yán)重影響通信質(zhì)量。

(10)

3)路由開(kāi)銷 路由開(kāi)銷指網(wǎng)絡(luò)中用于路由尋找和路由維護(hù)的控制數(shù)據(jù)包個(gè)數(shù)與目的節(jié)點(diǎn)接收到的數(shù)據(jù)包個(gè)數(shù)的比值。

(11)

4)吞吐量 吞吐量指單位時(shí)間內(nèi)通過(guò)鏈路成功傳輸?shù)钠骄鶖?shù)據(jù)量,吞吐量越大,網(wǎng)絡(luò)性能越好。

3.2 仿真結(jié)果分析

為評(píng)估K-AODV-ETX路由協(xié)議的性能,設(shè)置節(jié)點(diǎn)速度為20 m/s,在節(jié)點(diǎn)數(shù)為10,20,30,40,50個(gè)時(shí)對(duì)協(xié)議分別進(jìn)行仿真分析,并與AODV路由協(xié)議、AODV-ETX路由協(xié)議、K-AODV-ETX路由協(xié)議和ND-AODV-ETX路由協(xié)議進(jìn)行對(duì)比。

圖9顯示了節(jié)點(diǎn)速度為20 m/s時(shí),4種路由協(xié)議的PDR隨節(jié)點(diǎn)數(shù)的變化情況。從圖中可以看出,采用ETX機(jī)制可以明顯提高協(xié)議的數(shù)據(jù)包投遞率,AODV-ETX路由協(xié)議相比于AODV路由協(xié)議,其PDR最大可提升7%左右,而ND-AODV-ETX路由協(xié)議相比于AODV-ETX路由協(xié)議在PDR上沒(méi)有明顯的優(yōu)勢(shì)。本文提出的K-AODV-ETX路由協(xié)議的PDR略小于AODV-ETX路由協(xié)議,這是由于K-means機(jī)制路由發(fā)現(xiàn)過(guò)程中的選擇性轉(zhuǎn)發(fā),結(jié)合路徑選擇時(shí)候的ETX機(jī)制,容易引起節(jié)點(diǎn)處數(shù)據(jù)包的溢出丟失。

圖9 4種路由協(xié)議PDR隨節(jié)點(diǎn)數(shù)的變化Fig.9 Variation of PDR with number of nodes for four routing protocols

圖10展示了4種路由協(xié)議的時(shí)延隨節(jié)點(diǎn)數(shù)的變化情況。從圖中可以看出,ND-AODV-ETX路由協(xié)議和AODV-ETX路由協(xié)議的時(shí)延均明顯高于AODV路由協(xié)議與K-AODV-ETX路由協(xié)議。這是由ETX機(jī)制的重傳導(dǎo)致的,K-AODV-ETX路由協(xié)議采用K-means聚類算法,有目的地轉(zhuǎn)發(fā)RREQ數(shù)據(jù)包,實(shí)現(xiàn)了路徑的快速發(fā)現(xiàn),很好地平衡了ETX機(jī)制帶來(lái)的高延遲問(wèn)題,其時(shí)延性能和AODV路由協(xié)議相當(dāng)。

圖10 4種路由協(xié)議的時(shí)延隨節(jié)點(diǎn)數(shù)的變化Fig.10 Variation of delay with number of nodes for four routing protocols

圖11展示了4種路由協(xié)議的路由開(kāi)銷隨節(jié)點(diǎn)數(shù)的變化情況。由于ETX機(jī)制本身在路由控制包中占用了字節(jié),隨著節(jié)點(diǎn)數(shù)的增加,為維持穩(wěn)定鏈路需要更多的控制包,導(dǎo)致路由開(kāi)銷較大且不斷增加。本文提出的K-AODV-ETX路由協(xié)議,在路由發(fā)現(xiàn)廣播環(huán)節(jié)選取了最優(yōu)集群進(jìn)行轉(zhuǎn)發(fā),有效控制了無(wú)效的路由廣播,開(kāi)銷小于AODV-ETX路由協(xié)議和ND-AODV-ETX路由協(xié)議。從圖11中還可以看出,在節(jié)點(diǎn)數(shù)大于40個(gè)后,在相應(yīng)速度下網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)間信息交換較為充分,趨于一種穩(wěn)定狀態(tài),使得路由開(kāi)銷出現(xiàn)下降的趨勢(shì)。

圖11 4種路由協(xié)議的路由開(kāi)銷隨節(jié)點(diǎn)數(shù)的變化Fig.11 Variation of routing overhead with number of nodes for four protocols

圖12展示了4種路由協(xié)議的吞吐量隨節(jié)點(diǎn)數(shù)的變化情況。從圖中可以看出,采用ETX機(jī)制有效提高了AODV路由協(xié)議的吞吐量;在K-AODV-ETX路由協(xié)議中,在聚類特征中的節(jié)點(diǎn)緩沖項(xiàng),能夠有效減少網(wǎng)絡(luò)擁塞,增大了協(xié)議的吞吐量,比AODV路由協(xié)議最大可提高11.3%。

圖12 4種路由協(xié)議的吞吐量隨節(jié)點(diǎn)數(shù)的變化Fig.12 Variation of routing throughput with number of nodes for four protocols

4 結(jié) 語(yǔ)

本文提出了一種基于K-means聚類算法的ETX輔助無(wú)人機(jī)K-AODV-ETX路由協(xié)議。通過(guò)研究得到如下結(jié)論。

1)利用K均值聚類算法,協(xié)議根據(jù)相應(yīng)的聚類特征選擇最優(yōu)集群轉(zhuǎn)發(fā)RREQ消息報(bào)文,有效降低了節(jié)點(diǎn)泛洪廣播帶來(lái)的額外開(kāi)銷,同時(shí)RREQ消息的選擇性轉(zhuǎn)發(fā)可以加快鄰居發(fā)現(xiàn)的速度,降低了路徑發(fā)現(xiàn)時(shí)延。

2)數(shù)據(jù)傳輸采用ETX值較小的路徑,保證了鏈路的傳輸質(zhì)量。

3)NS3仿真結(jié)果表明,與AODV路由協(xié)議、AODV-ETX路由協(xié)議和ND-AODV-ETX路由協(xié)議進(jìn)行比較,K-AODV-ETX路由協(xié)議雖然在端到端投遞率方面有所下降,但是仍保持了高于AODV路由協(xié)議的投遞率水平,在保證一定吞吐量的同時(shí),在時(shí)延和路由開(kāi)銷性能方面也具有明顯優(yōu)勢(shì),是一種有效降低開(kāi)銷與路徑發(fā)現(xiàn)時(shí)延的路由協(xié)議。

對(duì)于提出的K-AODV-ETX路由協(xié)議,本文主要對(duì)不同網(wǎng)絡(luò)密度下的協(xié)議性能進(jìn)行了研究,未對(duì)不同速度下的協(xié)議性能進(jìn)行討論,而實(shí)際中無(wú)人機(jī)集群在執(zhí)行不同任務(wù)時(shí)可能采取不同的飛行速度,同時(shí)由于電池能量限制,亟需提高高速移動(dòng)下的協(xié)議性能并保障協(xié)議的能量效率,因此,今后將對(duì)不同速度下的協(xié)議性能做進(jìn)一步的研究。