無人機自組網中基于蟻群優化的多態感知路由算法

孫明杰,周 林,于云龍,顧金玲

(1.空軍工程大學防空反導學院,陜西 西安 710051;2.中國人民解放軍93861部隊,陜西 咸陽713800;3.中國人民解放軍32272部隊,甘肅 蘭州 730060)

0 引 言

當前,無人機的應用越來越廣泛,已涵蓋到民用和軍用多個領域。而且無人機已成為現代戰爭中不可缺少的重要組成部分,其主要用于戰場偵察監視、情報搜集、通信中繼、快速打擊等任務。現代戰場具有對抗程度高、覆蓋范圍廣、信息量大等特點,單架無人機已無法滿足現代戰爭的需要,多無人機協同作戰成為當今研究熱點。多無人機協同完成任務時,通常組成飛行編隊。

多無人機編隊協作執行任務時,可通過無人機自組織網絡來交換彼此的任務規劃、飛行狀態和情報信息等數據,以提高無人機編隊對實時態勢的感知,實現大于多架無人機獨立執行任務的整體效能。無人機自組織網絡屬于航空自組網,而航空自組網又是無線自組織網絡(mobile AdHoc network,MANET)在航空領域的典型應用。該網絡能夠保證無人機在戰場環境下,快速地入網和退網,同時,為了提高網絡的魯棒性,各架無人機在通信體系中的地位是平等的。在無人機自組織網絡中,將每架無人機作為節點處理。

然而,無人機自組織網絡與移動自組織網絡相比,具有節點移動性更強、網絡拓撲結構變化更快、應用環境復雜、數據交互頻繁等特點。這些特點為無人機自組織網絡中路由算法的設計帶來了很大的挑戰。傳統的路由算法在這種環境下不能滿足多無人機協同執行任務的需求,而其他基于服務質量(quality of service,QoS)保證的路由算法又有各自特定的應用場合,因此需要設計出適用于無人機自組織網絡的路由算法,以滿足復雜通信環境下無人機協同執行任務的要求。

對于無人機自組網中的路由算法,本文認為,應滿足如下要求:① 數據傳輸延時小;② 丟包率低;③ 可靠性高;④ 無擁塞現象出現;⑤ 路由開銷小;⑥ 可針對編隊變化,隨時調整路由算法,以保證網絡性能不下降。傳統的路由算法無法同時滿足上述要求。本文總結出了設計該路由算法時需要注意的3個關鍵點:路徑長度、路徑擁塞度和路徑穩定性。需要將這3者綜合考慮來設計無人機自組網中的路由算法。同時,在無人機自組網中,認為每個節點能量充足,能量不是影響路由性能的因素。

近年來,航空自組織網絡的路由協議已呈現多樣化趨勢。按照路由信息的更新機制,可將這些路由協議劃分為3大類:① 表驅動(主動)路由協議,如DSDV[1]、FSR[2]、STAR[3]、OLSR[4]、WRP[5]、TBRPF[6]等。在主動路由協議中,每一個節點都要維護一個或多個路由表,表中包含了該節點到網絡中所有其他節點一致的、最新的路由信息。為了維護這樣的路由表,每個節點需要周期性地向整個網絡廣播路由更新信息,以便時刻維護并記憶全網的拓撲結構與節點路由信息。表驅動路由協議的優點主要是能夠很好地保證網絡傳輸低延時性和服務質量,但是,使用該協議需要較高的代價,數量龐大的路由控制包會大大地增加路由開銷,因此也會導致節點的擁塞度增加。② 按需(被動)路由協議,如AODV[7]、DSR[8]、TORA[9]、SSR[10]等。在被動路由協議中,當源節點有通信需求時,才根據事先設定的算法搜索路由,由于不需要周期性地廣播路由更新信息,所以其路由開銷小,節省了網絡資源,但是當源節點有通信需求時,若沒有到達目的節點的路由,則需要重新搜索創建,數據傳輸也會因此被迫延時。③ 混合路由協議,如ZRP[11]。該路由協議將上述兩種協議結合起來,但依然無法解決主動路由協議路由開銷大的問題。

蟻群優化算法是由意大利學者Dorigo在1992年提出的,該算法是一種啟發式算法,主要通過模擬自然界螞蟻覓食行為來實現[12]。隨著蟻群算法的發展,越來越多地被應用于移動自組織網絡的路由問題中。根據文獻[13],可以得到基于蟻群算法路由協議的分類,與航空自組網劃分相同,主要分為3大類。本文就其中具有代表性的且與本文相關的路由協議進行評述。

對于Ant-DSR算法[14],單一傳播的螞蟻用于建立和更新路由,余下的兩種螞蟻則用于探測鄰居節點。該方法屬于主動型路由算法,可以使數據傳輸延時變小,但是依然無法避免路由開銷的增加,以至于出現節點擁塞現象。

ADSR算法[15]在路由發現階段使用了前向螞蟻與后向螞蟻,屬于被動型路由算法。但ADSR算法沒有評價路徑的可靠性,在節點移動性較強的無人機自組網中,極易出現鏈路斷路現象,從而使得數據包成功傳輸率降低。

HOPNET算法[16]與HRAZHLS算法[17]均屬于混合型路由算法,且均包含4種類型的螞蟻。但是HOPNET算法只適用于小型網絡,對大型網絡的擴展性不好。HRAZHLS算法的路由開銷較大。

綜上所述,無論是主動路由協議、被動路由協議還是混合路由協議,無論是否與蟻群算法相結合,都無法滿足無人機自組織網絡對路由算法提出的要求。同時,上述路由算法都無法有效地避免移動自組網中常見的問題,如節點擁塞、鏈路斷路等,上述問題的發生會使得丟包率大大增加。

對于傳輸路徑穩定性的判斷,首先要對其中包含的鏈路的穩定性進行判斷。目前,針對鏈路穩定性的判斷方法主要有兩種,但都存在不足。第一,基于距離的鏈路穩定性判斷[18-19]。認為兩節點距離越近越穩定,可通過全球定位系統(global positioning system,GPS)定位或者接收Hello消息功率來判斷兩點距離。該種方法判斷形式單一,不能對節點建立長效監督機制。而且,采用GPS定位進行鏈路穩定性判斷,容易引入定位誤差和外界GPS信號干擾,使得判斷失敗。第二,基于節點移動性的鏈路穩定性判斷。一種是通過節點的位置信息[20]計算節點的運動方向、速度,進而計算鏈路的穩定度。但是容易引入GPS誤差。另一種是基于概率方法的鏈路穩定性估計,文獻[21]采用的概率穩定性估計方法較復雜,計算開銷大;文獻[22]以鄰居節點數量的變化來估計當前節點的穩定度,計算不準確,誤差大;文獻[23]雖然對鏈路穩定度的計算較為簡單,但是由其篩選出的穩定性高的鏈路可能處于節點通信范圍的邊緣,易造成該鏈路的中斷。

近年來,多篇文獻針對網絡擁塞問題提出了多種解決方案,但也存在一定不足。文獻[24]根據MAC層接口隊列長度對緩沖區總長度的比值來表征網絡負載,避免將重負載節點作為中間節點而導致網絡擁塞,但測量形式單一。文獻[25]從緩沖占有量、信道負載程度、掉包率3個方面來評估節點的擁塞度,但其將低能耗放在了第一位,造成了擁塞度測量結果并不準確。

上述文獻僅為單方面考慮路徑穩定性或者是路徑擁塞度,并沒有對二者進行聯合的判斷。文獻[26]對路徑穩定性和路徑擁塞度同時進行判斷,有效地避免了移動自組網中的常見問題,但是就其方法來看,改進的余地還很大。

因此,本文重新設計了無人機自組網中的路由算法,將DSR算法與蟻群算法相結合,并做出諸多改進,提出了一種高效的路由算法——APAR算法,使之滿足數據傳輸延時低、數據成功傳輸率高、路由開銷小的要求,并且能夠避免鏈路斷路、網絡擁塞等常見問題,同時能夠根據編隊的變化調整路由算法,最終,克服了傳統路由算法存在的諸多不足。

1 控制數據包定義

在移動AdHoc網絡中,主要包含兩類路由控制包,路由請求控制包(routing request control packet,RREQ)和路由應答控制包(routing reply control packet,RREP)。RREQ包括目的節點地址、目的節點序列號、廣播序列號、源節點地址、源節點序列號、上一跳地址和跳數等信息。RREP包括源節點地址、目的節點地址、目的節點序列號、跳數和生存時間等信息。本文將蟻群算法與動態源路由算法相結合,并做了諸多改進,因此需要對RREQ和RREP的數據結構進行修改,使之滿足本文所提新路由算法。修改后的兩類路由控制包分別稱為RREQ.Ant和RREP.Ant,在本文中,這兩類控制包也被稱為前向螞蟻、后向螞蟻。其修改后的數據結構如圖1所示。

圖1 控制數據包格式Fig.1 Format of control data packet

源節點和目的節點的地址為MAC地址而不是IP地址,主要為了防止節點與網絡斷開鏈接而分配不到IP地址。HC代表了RREQ.Ant從源節點到目的節點所經過中間節點的個數,在RREQ.Ant中,HC的初始值為0。在RREP.Ant中,HC為一恒定值。RC與RS分別代表了從源節點到目的節點路徑的擁塞度和穩定度,a值僅在RREP.Ant中有效,主要用于確定后向螞蟻的轉發路徑。Type代表路由控制包的類型,當Type=1時,路由控制包為RREQ.Ant;當Type=0時,路由控制包為RREP.Ant。最后一部分用于存儲在路由發現過程中,RREQ.Ant從源節點到目的節點所經過的中間節點的地址。

2 路徑穩定性感知

在無人機自組織網中,由于無人機的移動速度較快且每架無人機的任務分配不同,所以其網絡拓撲變化較快,鏈路中斷的現象十分普遍。因此,為了避免鏈路中斷造成的網絡性能下降,本文提出了一種鏈路穩定性的評價方法,該方法主要通過接收Hello消息的信號強度并對其建立長效的監督機制,不但能夠綜合的評判某一鏈路的穩定性,還能預測并提前刪除可能中斷的鏈路,克服了之前方法的不足,從而提高了網絡性能。同時,為了避免GPS定位誤差或者外界干擾GPS信號對本文方法的影響,本文不使用節點的位置信息。

在無人機編隊對戰場環境的偵察過程中,由于任務不同的需要,編隊往往由不同種類的無人機構成,所以各個平臺的速度、天線增益、最大發射功率不同。因此,本文對Hello消息的數據包進行改進,最終包括:源節點地址、節點擁塞度、天線增益、傳輸功率、移動速度。

根據自由空間衰減模型[27],當前節點接收到距離d處的鄰居節點i的Hello消息的信號強度Pri為

(1)

式中：λ為無線電波的波長；Gr是接收天線的增益；Gt是發射天線的增益；Pt為鄰居節點Hello消息發射功率。

本文假設天線的覆蓋范圍為一個半徑為R的圓形區域。由文獻[28]可知,在半徑為R的圓形區域內,兩個移動節點之間的平均距離為0.905 4R。因此,本文將接收到鄰居節點Hello消息的信號強度的臨界值定義為

(2)

當前節點可以根據本節點已知信息和鄰居節點Hello消息中包含的信息計算出接收信號強度的臨界值,并與實測的信號強度進行比較,對鏈路的穩定性進行初次的評判。過程如下:

(3)

LSi值的大小代表了當前時刻第i條鏈路的穩定度,LSi越大代表該鏈路穩定性越好,但不超過1。當LSi為0時,該鏈路被認定為不穩定的鏈路,并從存儲區刪除。為了保持LSi值的實時性,需要不斷對其進行更新,更新的時間間隔(Hello消息的廣播周期)t為

(4)

式中：V1代表當前節點的最大移動速度；V2代表鄰居節點的最大移動速度。由于鄰居節點的類型不同,所以對應的t也是不同的。采用此時間間隔來更新LSi值,能夠保證在時間t內,存儲區中的鄰居節點都未移出其通信范圍,有效地利用了節點的存儲空間,為路由發現階段提供了可靠地選擇。有效地解決了固定Hello消息周期存在的缺陷。

上述過程僅對某一時刻鏈路的穩定性進行了評價,并沒有建立長效機制,對鏈路的穩定度進行綜合的評價。因此,本文根據不同時刻Hello消息信號強度的變化,對鄰居節點的移動性進行估計,將當前節點存儲區內移動性強的鄰居節點刪除。

根據文獻[29],可以得到比安內梅-切比雪夫不等式：

(5)

式中：X為離散變量;E(X)為X的數學期望;var(X)為X的方差；ε為任意正數。

當var(X)=0時,有P{|X-E(X)|<ε}=1,說明了變量X與其期望值相等,同時也說明了變量X的方差越小,變量X越接近其期望,變量X的變化量越小。

根據變量X的多次測量值,可以得到其方差var(X)為

(6)

將LSi不同時刻的值作為變量X的多次測量值,并代入式(6)中,得

(7)

通過式(7),可以得到某一鄰居節點的移動性,var(LSi)越小,代表該鄰居節點運動越不明顯,第i條鏈路也就越穩定。此方法僅對當前節點存儲區內的鄰居節點移動性進行判斷。

綜上所述,具體的鏈路穩定性判斷過程為:每個節點都對進入本節點0.905 4R范圍內鄰居節點進行編號,并將其寫入存儲區,而且根據式(3),計算出每條鏈路當前時刻的穩定度LSi。當某一鏈路的LSi值為0時,存儲區將刪除該鏈路。當某一鏈路連續得到兩個不為0的LSi時,便對其節點移動性進行判斷,只要LSi不為0,就一直對該鏈路的節點移動性進行判斷。當某一鏈路的var(LSi)累計3次超過預先設定的臨界值varthreshold時,說明了此鄰居節點移動性強,同時也說明了該鏈路不穩定,因此將該鏈路從當前節點的存儲區中刪除。同時,為了節省存儲空間,本文定義節點存儲區內只存儲最近5個時刻的LSi值。

在路由發現階段,通常需要選出最穩定的路由來傳輸數據,因此需要對當前一跳鏈路的穩定度進行綜合量化。本文提出了一種當前一跳鏈路穩定性的綜合量化方法,如下：

(8)

式中：CLSi(tm)為第i條鏈路tm時刻的綜合穩定度;LSi(tm)為tm時刻的LSi值;varm(LSi)為tm時刻的var(LSi)值。當該時刻,某一鄰居節點第一次進入當前節點的存儲區時,var(LSi)值為空,在此方法中,令該時刻的varm(LSi)=1。并且,CLSi(tm)值越大,代表該鏈路的綜合穩定性越高。

在本文中,每一個路由控制包都包含一個RS值,其大小由RREQ在路由發現過程計算得到。源節點發出一只前向螞蟻,并令RS的初始值為1。當該前向螞蟻在網絡中移動時,每經過一個中間節點,就將該中間節點與上一跳節點之間的鏈路穩定度CLSi與當前RS值相乘,得到一個新的RS值。當該前向螞蟻到達目的節點時,便可以得到源節點到目的節點之間路徑的穩定度RS:

(9)

3 路徑擁塞度感知

多架無人機以編隊形式對熱點地區偵察的過程中,需要共享和回傳大量的目標數據。如果采用傳統的路由算法來構建傳輸數據的路由,那么極易造成網絡擁塞現象。在無人機自組網中,如果出現網絡擁塞,會使網絡的數據傳輸性能下降,例如掉包率增加、平均端到端延時增大等。

本文提出了一種路徑擁塞度測量方法,主要根據緩沖占有量、信道負載程度來測量節點的擁塞度,并采用了非線性化處理手段,結合路由發現過程使得路徑擁塞度測量結果更符合實際。

3.1 緩沖占有量

節點Ni的MAC層接口隊列長度與緩沖區總長度的比值代表了當前節點緩沖占有量BOi,表示如下:

(10)

式中：Qi為節點Ni的MAC層接口隊列長度;Qmax為當前節點緩沖區的總長度,本文假設所有節點緩沖區的總長度相同。

節點Ni周期性地對BOi值進行測量,便可以得到一定時間內緩沖平均占有量Ave_BOi(t)。本文假設,在t時間內共進行了N次測量,則

(11)

式中：BOi(j)為節點Ni對BOi值進行的第j次的測量結果。

通常情況下,MAC層接口隊列長度占緩沖區總長度65%以上就認定該節點緩沖占有量大[30]。因此,為使其符合實際需要，本文對Ave_BOi(t)進行非線性化處理：

NBOi=1-(1-Ave_BOi(t))5

(12)

式中：NBOi為節點Ni的非線性化緩沖平均占有量。

3.2 信道負載程度

根據文獻[26],通過一段時間內周期地對信道進行采樣,便可以得到信道負載CLi，可表示為

(13)

式中：Nbusy表示該段時間內信道處于繁忙狀態的次數;Nidle表示該段時間內信道處于空閑狀態的次數。

信道采樣過程如圖2所示。

圖2 信道采樣過程Fig.2 Sampling process of channel

隨著信道負載CLi的增加,網絡中的擁塞現象會越來越嚴重。本文對CLi值進行了多次連續測量,得到了時間t內信道的平均負載:

(14)

式中：CLi(j)為第j次CLi值的測量結果;N為時間t內的測量次數。通常情況下,時間t取30 s,每次的測量時間為5～10 s。

類似于緩沖占有量,信道負載程度依然要進行非線性化處理。本文認為,Ave_CLi(t)大于等于0.7就代表該信道負載程度高,因此對其進行如下非線性化處理：

NCLi=1-(1-Ave_CLi(t))4

(15)

為了綜合評價某一節點的擁塞度,定義如下等式:

(16)

CNCi(t)=νMi(t-1)+(1-ν)Mi(t)

(17)

式中：Mi(t)為當前時間窗節點的擁塞度；ν和(1-ν)為賦予前一時間窗和當前時間窗節點擁塞度的權重因子；CNCi(t)為該節點擁塞度的綜合值。

每一個路由控制包都含有一個RC值,由路由發現過程計算得到。源節點發出一只前向螞蟻,該螞蟻負責建立從源節點到目的節點的路由,當前向螞蟻到達目的節點時,其所經過的所有節點的節點擁塞度CNCi(t)的最大值將成為該路徑的擁塞度RC,表示為

(18)

4 基于蟻群優化的多態感知路由算法

4.1 路由發現過程

由于執行的任務不同,無人機存在多種形式的編隊,本文主要關注其編隊中無人機的密度對無人機自組網網絡路由的影響。因此,本文根據其網絡中節點密度提出了兩種不同的路由發現算法。

根據文獻[31],本文認為平均網絡分區(average network partitioning,ANP)小于等于3%時,無人機編隊為密集編隊;否則為稀疏編隊。路由發現過程對這兩種情況處理的不同點主要體現在RREQ.Ant的轉發方法上,在其他方面方法均相同。

4.1.1 路由請求控制包傳遞過程

(1)稀疏編隊

當某一無人機獲取到目標信息,并需要將該信息共享至其他無人機時,當前節點首先對本節點緩沖區內已經存在的路由進行比對,如果存在能夠完成此次信息傳輸的路由,那么根據路由選擇過程,選取最優的路徑來傳輸該目標信息;如果當前節點找不到向目的節點傳輸目標信息的路由,那么將從當前節點啟動路由發現過程,向其鄰居節點中所有穩定的節點發出前向螞蟻。與文獻[32]提出的洪泛方法相比,本文提出的方法能夠有效地避免洪泛廣播消息的無方向性、盲目性,提高了所發現路由的可靠性。

對于中間節點,如果接收到上一節點轉發來的前向螞蟻,首先對其數據包內的跳數HC值進行判斷,由于存儲空間的限制,HC的最大值為127,如果發現HC為最大值,那么該中間節點將銷毀該數據包,不再轉發,以免引起路由長度測量的誤差。

其次,針對無人機自組網中可能出現的路由環路問題,本文提出了一種預防機制,能夠避免路由環路對網絡性能產生的不利影響。當中間節點在RREQ.Ant的中間節點存儲區(INA)中發現本節點的地址時,就認為該路由發現過程已進入環路狀態,本文首先對RREQ.Ant進行修改,將進入環路的節點刪除,隨后從當前中間節點的鄰居節點中篩選出不會進入環路的穩定節點作為下一跳節點,并向這些節點轉發RREQ.Ant。

最后,如果未發生路由環路問題,當前節點會查找本節點緩沖區內是否存在能夠到達目的節點的路由,若存在,則需要對前向螞蟻中的相關信息進行更新(例如跳數、穩定度、擁塞度等),并啟動路由應答過程,該方法能夠降低端到端延時和路由開銷;如果不存在可用路由,當前節點會更新前向螞蟻,并且轉發至其穩定的鄰居節點。

對于目的節點,如果接收到RREQ.Ant,需要對其進行更新并啟動路由應答過程。

(2)密集編隊

對于密集編隊,若其路由算法與稀疏編隊相同,由于節點密度的增加,RREQ.Ant的轉發數量也大大增加,極易造成廣播風暴,致使網絡性能急劇下降,因此本文對密集編隊路由算法的改動有兩處。其一是對Hello消息的改動,在密集編隊中,Hello消息在原有基礎上附加了當前節點的穩定鄰居節點列表;其二是對前向螞蟻轉發方法的改動,本文受文獻[31]的啟發,提出了一種概率轉發方法,能夠減少RREQ.Ant的轉發數量,降低廣播風暴發生的可能性,同時也保證了所發現路徑的冗余性,在戰場環境中具有抗擊毀性。

該概率轉發方法僅適用于中間節點,對于源節點,依然采用稀疏編隊的前向螞蟻轉發方法,以保證發現路徑的冗余。當某一中間節點D接收到上一節點F發來的前向螞蟻時,首先對F節點Hello消息中的節點列表與本節點的作比較,計算出前向螞蟻的轉發概率p,節點D以概率p將更新過的前向螞蟻轉發至穩定的鄰居節點。轉發概率計算如下:

(19)

式中：m為兩節點穩定鄰居節點中公共部分的數量;n為屬于節點F但不屬于節點D的穩定鄰居節點的數量;q為屬于節點D但不屬于節點F的穩定鄰居節點的數量。

雖然對Hello消息的改動增加了數據包對無線媒介的占用時間,但是概率轉發機制能夠大大地降低所轉發前向螞蟻的數量,降低了路由開銷,而且能夠保證所發現路徑的可靠性,因此利大于弊。

4.1.2 路由應答控制包傳遞過程

當目的節點接收到RREQ.Ant時,需要將其數據包類型轉換為RREP.Ant,并沿原路徑返回至源節點。對于中間節點,如果接收到RREP.Ant,那么該節點只需要按路徑轉發即可;如果中間節點接收到RREQ.Ant并找到了到達目的節點的路由,則需要將數據包變為RREP.Ant,同樣將其按原路徑返回源節點。當源節點接收到RREP.Ant時,需要啟動路由選擇過程,選出最優路徑來傳輸目標數據。

4.1.3 路由選擇

源節點每接收到一個后向螞蟻,都會從中提取出HC值、RC值和RS值,用來計算該路徑的信息素,計算方法如下:

(20)

源節點會對每一條路徑的信息素進行計算,并選擇信息素最高的路徑來傳輸目標信息。用于傳輸信息的路徑通常有跳數小、穩定性高、擁塞度低等特點。源節點針對一個目的節點通常會保留多條可用路徑,以防最優路徑遭到破壞。同時,為了降低平均端到端延時,本文定義了如下機制:當源節點接收到第一個RREP.Ant時,便開始沿著該后向螞蟻提供的路徑傳輸目標信息;如果接收到第二個RREP.Ant,源節點會選擇信息素最高的路徑來傳輸信息,以此類推,直到最后一個RREP.Ant。由于本文引入了信息素揮發機制,所以每接收到一個后向螞蟻,需要對所有已知路徑的信息素進行重新選擇,不能沿用之前的信息素值。

4.1.4 目標信息傳遞過程

在傳輸目標信息之前,需要將已選擇路徑的中間節點地址寫入到目標信息中,使得目標信息能夠沿著該路徑到達目的節點。當目的節點接收到目標信息時,會立即發送ACK消息至源節點,表明此次信息傳輸成功。如果源節點在一定時間內未接收到ACK消息,那么會選用備用路徑來傳輸目標信息,若沒有路徑可以使用,則需要重新啟動路由發現過程。

4.2 路由維護過程

在無人機自組織網絡中,節點的可移動性、網絡拓撲結構的動態變化都使得路由維護顯得十分重要。路由斷路和路由死循環是路由維護中必須解決的兩個關鍵問題。

根據蟻群算法可知,當螞蟻尋找食物時,會經過不同的路徑到達食物源。在返回蟻穴的過程中,螞蟻會留下信息素,信息素值的大小代表了該路徑的可用程度。當某一路徑不斷地存在螞蟻返回時,會增加該路徑的信息素值;當食物消耗殆盡,不再有螞蟻返回時,該路徑的信息素由于揮發會逐漸減弱,直至消失。

受螞蟻覓食以及文獻[33]的啟發,本文對信息素的揮發機制[34-35]進行了改進,使之滿足本文算法的需要。當前時刻某一路徑的信息素值表示如下:

(21)

式中：Ph[k]t為t時刻某一路徑的信息素值;α為衰減系數,用于改變信息素的衰減幅度,可以根據實際應用隨時調整該系數;vmax為所有節點移動的最大速度;n為源節點接收到ACK消息的數量。

當某一路徑接收到后向螞蟻時,路由維護過程隨之啟動。在該過程,后向螞蟻具有和ACK消息一樣的作用,因此在t=0時,n=1。當該路徑正常的傳輸數據時,其信息素值會不斷“增加”,當然,這種“增加”是相對于無數據傳輸時信息素值變化的,總體來看,正常傳輸數據的路徑,其信息素水平也會下降,但下降速度較慢;當該路徑未被使用或者已經出現斷路時,其信息素水平會迅速下降,當低于某一門限值β時,該路徑失效被移出源節點存儲區。同時,節點的最大移動速度也是影響信息素水平的重要因素,節點的移動速度越大,造成鏈路中斷的可能性就增加,因此信息素的衰減程度與節點的移動速度成正相關。

在路由維護部分,α和β的大小可根據實際情況隨時調整,以便于滿足不同的要求。通常來說,被選定用于傳輸數據路徑的α值要比未被使用路徑的α值高,這是因為,選出的用于傳輸數據的路徑信息素水平是最高的,如果該路徑因某一節點遭擊毀而出現斷路,那么其信息素水平會迅速下降,且下降速度與其他未使用路徑的信息素下降速度相同(如果所有路徑的α值相同),當該路徑的信息素值小于β時,才認為路徑失效,但此時所有的備用路徑早已被認定是失效的了,重新啟動路由發現過程,增加了路由開銷。因此,本文將路徑信息素的衰減程度區分開來,對于正在使用的路徑,其信息素衰減程度大,一旦路徑遭到破壞,可使其信息素迅速下降并失效;備用路徑由于其信息素衰減程度小,可在主路徑失效時迅速切換至備用路徑,而不用啟動路由發現過程,降低了路由開銷。

對于路由循環問題,在路由發現階段就已經解決了。前向螞蟻所經過的中間節點都會將自己的地址加入到螞蟻信息當中,螞蟻對此都有記錄并且只經過從未到達的節點。因此,算法自身就很有效地避免了循環問題。

5 仿真分析結果

在仿真環境下,本文將APAR算法與部分主流算法進行了性能比較,這些算法包括:DSR算法[8]、Ant-DSR算法[14]、HOPNET算法[16]。其中,運用的仿真軟件為NS-2(Network Simulator v2.34)。由于本文針對無人機的稀疏編隊與密集編隊提出了兩種不同的路由策略,所以需要分成兩種情況來測試其性能,這兩種情況除了節點數量不同,其他仿真參數均相同。假設無人機為低空低速小型無人機,其通信距離較近,但由于執行任務的多樣性,所以該無人機自組網中的節點移動性較強,具體仿真參數如表1所示。仿真參數的選擇主要參考了文獻[4,8,16]。為了真實地模擬戰場環境,體現出本文提出的無人機自組網路由算法——APAR算法在戰時的優異性能。仿真過程中選擇隨機地關閉一些節點,以此來表示無人機自組網在戰時遭到一定程度破壞,某些無人機被擊毀。同時,為了減少隨機誤差,所有實驗結果為30次實驗的平均值。仿真結果如圖3～圖8所示。

表1 仿真參數Table 1 Simulation parameter

圖3 稀疏編隊下數據包成功傳輸率比較圖Fig.3 Comparison diagram of data packet delivery ratio in sparse formation

圖4 密集編隊下數據包成功傳輸率比較圖Fig.4 Comparison diagram of data packet delivery ratio in concentrated formation

圖3和圖4給出了無人機自組織網絡在無人機稀疏編隊和密集編隊的情況下,分別采用DSR、Ant-DSR、HOPNET、APAR算法在數據包成功傳輸率性能上的比較。可以清楚地看到,無論是稀疏編隊還是密集編隊,本文提出的APAR算法與之前的3種算法相比,數據包成功傳輸率有較大幅度的提升。具體來說,在稀疏編隊下,APAR算法比HOPNET、Ant-DSR、DSR算法將數據包成功傳輸率分別提高了30%、60%、130%以上;在密集編隊下,本文算法比上述3種算法分別提高了40%、90%、200%以上。由于在無人機密集編隊中,節點與節點之間鏈接的可能性更大,所以APAR算法在密集編隊中有更高的數據包成功傳輸率。

圖5和圖6給出了無人機自組織網絡在無人機稀疏編隊和密集編隊的情況下,采用上述4種算法在平均端到端延時性能上的比較。可以看出,APAR算法無論在何種情況下,與其他3種算法相比,都具有較低的端到端延時。該性能的取得主要得益于本算法的路由發現過程和路由維護過程。

圖5 稀疏編隊下平均端到端延時比較圖Fig.5 Comparison diagram of average end to end delay in sparse formation

圖6 密集編隊下平均端到端延時比較圖Fig.6 Comparison diagram of average end to end delay in concentrated formation

圖7 稀疏編隊下路由開銷比較圖Fig.7 Comparison diagram of routing overhead in sparse formation

圖8 密集編隊下路由開銷比較圖Fig.8 Comparison diagram of routing overhead in concentrated formation

圖7和圖8給出了無人機自組織網絡在無人機稀疏編隊和密集編隊的情況下,采用上述4種算法在路由開銷性能上的比較。可以看出,APAR算法在無人機稀疏網絡和密集網絡中,都具有相對較低的路由開銷,在一定程度上降低了該網絡中節點能量的消耗。同時,由于DSR算法在路由發現過程中采用了洪泛機制,所以其路由開銷相對較大。

綜上所述,APAR算法在平均端到端延時、數據包成功傳輸率和路由開銷方面都有較為優異的性能,能夠為戰場環境下多無人機編隊執行任務提供有效的通信保障。

6 結 論

本文針對無人機自組織網絡中,采用傳統的路由算法容易使該網絡在數據包傳輸率、端到端延時和路由開銷等方面性能降低,以至于不能滿足多無人機編隊執行任務信息共享需要的情況,提出了一種基于蟻群優化的多態感知路由算法——APAR算法,該算法主要受蟻群相關行為的啟發,并與動態源路由算法相結合,通過感知路徑長度、路徑穩定性和路徑擁塞度來建立選路標準,有效地避免了擁塞和鏈路斷路現象的發生。同時,該算法能夠根據無人機編隊的變化適時地調整路由策略,以保證相關性能不下降。針對其他主流算法路由開銷較大的問題,本文改進了信息素的揮發機制,對于不同的路徑采用不同的衰減系數,降低了路由開銷。APAR算法與DSR、Ant-DSR和HOPNET算法在仿真部分進行了性能比較,結果表明,在戰場環境下,無論多無人機是稀疏編隊還是密集編隊,APAR算法都能保證較低的平均端到端延時、較高的數據包成功傳輸率和較低的路由開銷,能夠滿足多無人機編隊組網執行任務的需要。