一種基于聚類算法的ETX輔助無人機AODV路由協議

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

(1.中國電子科技集團公司第五十四研究所,河北石家莊 050081;2.通信網信息傳輸與分發技術重點實驗室,河北石家莊 050081)

無人機被廣泛應用于交通管理[1-2]、監控[3]、邊境巡邏[4]、災難救援[5-6]等領域。由于無人機的高移動性、拓撲變化的周期性、能量約束和通信范圍有限,其通信網絡內鏈路斷裂和數據包丟失現象較其他無線通信鏈路更加頻繁。在飛行自組網(flying ad hoc network,FANET)中,需要穩定的數據傳輸路徑來保證網絡內高效可靠的通信。因此,路由協議設計是FANET中的一個重要問題,開發低開銷、低延時的高效路由協議成為研究的熱點和難點[7]。

無線自組網按需平面距離向量(ad hoc on-demand distant vector,AODV)路由協議以其方便高效的性能被廣泛應用于無人機自組織網絡[8],網絡中的節點并不存儲網絡整體的拓撲結構,僅當需要發送信息時才會尋找路由路徑,但在發現、生成路由時會產生較高的延遲,跳數最短路由機制也存在一定的弊端。

針對上述問題,許多學者基于AODV路由協議提出了更加穩定高效的改進協議。SARKAR等[9]提出了一種基于增強蟻群優化算法的Enhanced-Ant-AODV路由協議,利用信息素判別最優路徑,提供了有效的QoS保障;LI等[10]提出了一種基于模糊邏輯輔助的FL-AODV路由協議,提高了路徑的可靠性;BAMHDI等[11]提出了一種基于節點密度的DP-AODV路由協議,通過動態調整傳輸數據包所需的功率,從而減少網絡的功率總需求;SHAFI等[12]提出了一種基于機器學習的ML-AODV路由協議,用來檢測泛洪黑洞攻擊,提高了網絡的安全性。

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

圖1 泛洪廣播Fig.1 Flooding broadcast

本文在AODV-ETX路由協議的基礎上,結合K-means聚類算法,提出了K-AODV-ETX路由協議,通過聚類特征選擇RREQ消息轉發的最佳集群,減少盲目泛洪廣播帶來的資源浪費,縮短路徑發現時間,有效降低協議的路由開銷與端到端時延。

為了驗證性能,將K-AODV-ETX路由協議與AODV路由協議、AODV-ETX路由協議、ND-AODV-ETX路由協議進行比較,其中AODV-ETX路由協議與ND-AODV-ETX路由協議是分別在AODV路由協議、ND-AODV路由協議的基礎上改進而來的。

1 算法設計

1.1 ETX機制原理

AODV-ETX路由協議、ND-AODV-ETX路由協議均采用ETX機制。ETX機制通過一種消息探針來監控鏈路上的數據包預期傳輸數。為了找出傳播值最小的傳播鏈路,AODV路由協議中傳統的跳數最短路徑選擇機制將被ETX機制取代。當源節點和目的節點之間的通信鏈路建立時,通過計算鏈路正向傳輸成功的概率和反向重傳成功的概率來得到節點鏈路中的ETX值。

ETX定義為

(1)

式(1)中:R為網絡2個節點之間的路由;η為路由R的一跳;φ(η)為轉發接收比;ρ(η)為反向接收比,即對應ACK報文被成功接收的概率。

接收比常由鏈路探測報文(link probe packet,LPP)估計:

(2)

式(2)中:

(3)

α為鏈路質量老化參數,α越大,接收比的平均時間越長,從而產生更穩定、可靠的估計。

鏈路的ETX值由在該鏈路上發送數據包所需的預期傳輸數表示,包括重傳。如果pf表示報文成功傳輸的概率,pr表示ACK報文成功接收的概率,那么報文成功發送并確認的概率為pf×pr,則鏈路l的ETX值可以表示為

ETXl=1/(pf×pr)。

(4)

網絡中節點以平均周期τ廣播鏈路探測消息報文LPP,概率Pf和Pr都可以通過LPP來測量,周期τ內最大抖動設置為10%來避免意外同步的產生。每個節點將在最近w秒內接收到的LPP數量記錄在自己的路由表中,并根據式(5)計算任意時刻t下的概率:

(5)

式(5)中:count(t-w,t)為在窗口w期間實際接收到的LPP數量;w/τ為在此窗口期間應該接收的LPP數量。如在鏈路X→Y上,X通過計算從Y成功接收到的LPP來測量pr,節點Y發送的每個LPP都包含最近w秒內從X接收到的LPP數量。節點X根據w秒內接收到的LPP數量來計算pr,路由r的度量為路由中每個鏈路l的ETX值的和:

(6)

1.2 K-means聚類算法

相比于AODV路由協議的跳數最小路徑選擇機制,ETX機制提供了一種有效提高自組織網絡吞吐量的方法,但由于探測包LPP的存在,增加了網絡的控制報文,從而增大了路由開銷和時延,基于這一問題,本文考慮采用聚類算法思想控制開銷,減小時延。

聚類算法是一種有效的特征分類方法[15],并已被應用到路由協議中,許多基于聚類算法的路由協議被提出[16-17],現階段大部分的聚類算法都應用于分簇協議的設計與應用,而本文旨在基于聚類算法的分類思想將FANET中的節點進行特征分類。

執行聚類算法后,分布在一定范圍內的節點根據特征被分類,如圖2、圖3所示,其中圖3中不同顏色代表不同的類,當路由發現過程觸發時,改變RREQ消息泛洪廣播機制,沿著特定無人機節點集群傳播。

圖2 節點分布情況Fig.2 Node distribution

圖3 K-means聚類后節點分布情況Fig.3 Node distribution after K-means algorithm

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

(7)

式(7)中:d(xj,ui)=|xj-ui|2,其為該點到聚類質心的距離;xj為該點的位置;ui為i=1,2,…,K時質心的位置,K是簇的個數。

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

(8)

在本文中,K-means聚類中使用的聚類特征有3個,網絡中源節點基于鄰居的聚類特征來選擇最優聚類進行消息轉發。

1)到目的節點的跳數 到目的節點的跳數越小,路由越短,路由發現的時間越短。

2)錯誤傳輸次數 節點錯誤傳輸的次數越少,節點的傳輸越可靠,則經過此節點的鏈路質量高,有助于提高吞吐量和數據投遞率。

3)節點可用緩沖空間 節點的可用緩沖空間越大,表示節點處的網絡擁塞情況越輕,數據包經過此處不容易發生擁塞,有助于提高網絡的吞吐量。

2 協議工作流程

K-AODV-ETX路由協議的工作流程主要分為2步:第1步,在網絡中執行K-means聚類算法對節點進行分類處理,選擇合理的集群進行源節點與目的節點之間的消息報文轉發;第2步,執行路由發現過程,與AODV-ETX路由協議相同。

2.1 轉發集群選擇

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

輸入:質心數量K;節點集合N;隨機分配給質心的列表Ck

輸出:具有質心的集群

Begin

1.Repeat

2.ForN個數據點,do

3.使用式(7)計算數據點和每個聚類的質心之間的距離

4.將數據點指定給最近的質心

5.Endfor

6.ForCk中的每個集群do

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

8.Endfor

9.Until所有數據點都屬于一個集群或達到最大迭代次數

End

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

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

為了收集網絡內節點信息從而確定轉發集群,利用網絡仿真軟件NS3,向AODV協議類中添加新字段,具體如下:

在“RREPHeader”和“RoutingTableEntry”類中增加m_txErrorCount(錯誤傳輸計數),m_freeSpace(緩沖空間),m_positionX(節點橫坐標),m_positionY(節點縱坐標)字段,同時在執行文件中新增協議文件aodvKmeans-routing-protocol.h和路由表文件aodvKmeans-rtable.h來進行K-AODV-ETX路由協議的實現。

2.2 路徑選擇

K-AODV-ETX路由協議的路由發現與維護過程與AODV協議基本相同,不同的是采用ETX機制進行路由選擇與判別,為此,對協議的RREQ與RREP消息報文進行修改,如圖5和圖6所示。

類型JRGDU保留跳數RREQ ID目的節點序列號路由請求RREQ源節點的IP地址壽命ETX

類型RA保留前綴長度多跳轉發計數器目的節點IP地址目的節點序列號路由請求RREQ源節點的IP地址壽命ETX

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

首先,每個路由表項都使用ETX字段展開。在AODV路由協議中,路由表項是按目的地分類的。如果到某個目的地有多條路由,則按跳數對路由進行分類,跳數最小的路由為最佳路由。在AODV-ETX路由協議中,根據路由的ETX值對路由進行分類,ETX值最小的路由為最佳路由。如果存在多個具有相同ETX值的路由,則再以跳數最小的路由為最佳。

當源節點S進行路由發現過程廣播RREQ消息時,ETX的初始值設置為0,此后ETX字段的處理方式與跳數類似。即RREQ轉發到目的節點時,每個節點的ETX字段按照式(6)進行更新。發送RREP報文的原理與之相同。ETX值是累積的,通過比較不同路徑的ETX值之和選擇路徑。

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

圖7 最小跳數機制下的消息傳播Fig.7 Message propagation with minimum hop count mechanism

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

如圖7所示,AODV路由協議采用跳數最小機制選擇路徑,RREQ消息每轉發1次,其路由表項中的跳數項則加1,節點A廣播RREQ消息報文,節點C和節點B均收到,隨后節點C和節點B廣播,節點B收到來自節點C的RREQ消息,與自身路由表更新過的跳數進行比較,對節點C的RREQ消息進行舍棄,直至目的節點D收到RREQ消息,并發送RREP消息建立正向傳輸路徑,S—A—C—B—D跳數較大,采用S—A—B—D進行數據傳輸。

在ETX機制下,鏈路的ETX值之和越小,鏈路的質量越好,因此K-AODV-ETX路由協議選擇ETX值之和最小的鏈路進行數據傳輸,如在圖8中,當鏈路A—C—B的ETX值之和小于A—B鏈路的ETX值時,雖然A—B鏈路的跳數較小,但節點B仍會舍棄來自節點A的RREQ消息,采用鏈路S—A—C—B—D進行數據傳輸。

3 仿真設置與分析

3.1 仿真環境和仿真參數介紹

本文采用網絡仿真軟件NS3進行仿真,仿真參數設置如表1所示。

表1 仿真參數設置

為了衡量K-AODV-ETX路由協議的網絡性能,選取了以下3個仿真指標。

1)數據包投遞率(packet delivery ratio,PDR) PDR為目的節點接收到的數據包個數與源節點發送的數據包個數之比,反映了網絡傳輸的可靠性,投遞率越高,協議的可靠性越大。

(9)

2)端到端的平均時延 它包括路由查找時延、數據包在接口隊列中的等待時延、傳輸時延及MAC層的重傳時延,其反映了路由有效性,尤其對語音消息來說,時延太大會嚴重影響通信質量。

(10)

3)路由開銷 路由開銷指網絡中用于路由尋找和路由維護的控制數據包個數與目的節點接收到的數據包個數的比值。

(11)

4)吞吐量 吞吐量指單位時間內通過鏈路成功傳輸的平均數據量,吞吐量越大,網絡性能越好。

3.2 仿真結果分析

為評估K-AODV-ETX路由協議的性能,設置節點速度為20 m/s,在節點數為10,20,30,40,50個時對協議分別進行仿真分析,并與AODV路由協議、AODV-ETX路由協議、K-AODV-ETX路由協議和ND-AODV-ETX路由協議進行對比。

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

圖9 4種路由協議PDR隨節點數的變化Fig.9 Variation of PDR with number of nodes for four routing protocols

圖10展示了4種路由協議的時延隨節點數的變化情況。從圖中可以看出,ND-AODV-ETX路由協議和AODV-ETX路由協議的時延均明顯高于AODV路由協議與K-AODV-ETX路由協議。這是由ETX機制的重傳導致的,K-AODV-ETX路由協議采用K-means聚類算法,有目的地轉發RREQ數據包,實現了路徑的快速發現,很好地平衡了ETX機制帶來的高延遲問題,其時延性能和AODV路由協議相當。

圖10 4種路由協議的時延隨節點數的變化Fig.10 Variation of delay with number of nodes for four routing protocols

圖11展示了4種路由協議的路由開銷隨節點數的變化情況。由于ETX機制本身在路由控制包中占用了字節,隨著節點數的增加,為維持穩定鏈路需要更多的控制包,導致路由開銷較大且不斷增加。本文提出的K-AODV-ETX路由協議,在路由發現廣播環節選取了最優集群進行轉發,有效控制了無效的路由廣播,開銷小于AODV-ETX路由協議和ND-AODV-ETX路由協議。從圖11中還可以看出,在節點數大于40個后,在相應速度下網絡內的節點間信息交換較為充分,趨于一種穩定狀態,使得路由開銷出現下降的趨勢。

圖11 4種路由協議的路由開銷隨節點數的變化Fig.11 Variation of routing overhead with number of nodes for four protocols

圖12展示了4種路由協議的吞吐量隨節點數的變化情況。從圖中可以看出,采用ETX機制有效提高了AODV路由協議的吞吐量;在K-AODV-ETX路由協議中,在聚類特征中的節點緩沖項,能夠有效減少網絡擁塞,增大了協議的吞吐量,比AODV路由協議最大可提高11.3%。

圖12 4種路由協議的吞吐量隨節點數的變化Fig.12 Variation of routing throughput with number of nodes for four protocols

4 結 語

本文提出了一種基于K-means聚類算法的ETX輔助無人機K-AODV-ETX路由協議。通過研究得到如下結論。

1)利用K均值聚類算法,協議根據相應的聚類特征選擇最優集群轉發RREQ消息報文,有效降低了節點泛洪廣播帶來的額外開銷,同時RREQ消息的選擇性轉發可以加快鄰居發現的速度,降低了路徑發現時延。

2)數據傳輸采用ETX值較小的路徑,保證了鏈路的傳輸質量。

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

對于提出的K-AODV-ETX路由協議,本文主要對不同網絡密度下的協議性能進行了研究,未對不同速度下的協議性能進行討論,而實際中無人機集群在執行不同任務時可能采取不同的飛行速度,同時由于電池能量限制,亟需提高高速移動下的協議性能并保障協議的能量效率,因此,今后將對不同速度下的協議性能做進一步的研究。