無人機自組網(wǎng)中基于蟻群優(yōu)化的多態(tài)感知路由算法

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

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

0 引 言

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

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

然而,無人機自組織網(wǎng)絡(luò)與移動自組織網(wǎng)絡(luò)相比,具有節(jié)點移動性更強、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化更快、應(yīng)用環(huán)境復(fù)雜、數(shù)據(jù)交互頻繁等特點。這些特點為無人機自組織網(wǎng)絡(luò)中路由算法的設(shè)計帶來了很大的挑戰(zhàn)。傳統(tǒng)的路由算法在這種環(huán)境下不能滿足多無人機協(xié)同執(zhí)行任務(wù)的需求,而其他基于服務(wù)質(zhì)量(quality of service,QoS)保證的路由算法又有各自特定的應(yīng)用場合,因此需要設(shè)計出適用于無人機自組織網(wǎng)絡(luò)的路由算法,以滿足復(fù)雜通信環(huán)境下無人機協(xié)同執(zhí)行任務(wù)的要求。

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

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

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

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

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

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

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

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

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

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

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

1 控制數(shù)據(jù)包定義

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

圖1 控制數(shù)據(jù)包格式Fig.1 Format of control data packet

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

2 路徑穩(wěn)定性感知

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

根據(jù)文獻(xiàn)[29],可以得到比安內(nèi)梅-切比雪夫不等式：

(5)

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

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

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

(6)

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

(7)

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

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

在路由發(fā)現(xiàn)階段,通常需要選出最穩(wěn)定的路由來傳輸數(shù)據(jù),因此需要對當(dāng)前一跳鏈路的穩(wěn)定度進(jìn)行綜合量化。本文提出了一種當(dāng)前一跳鏈路穩(wěn)定性的綜合量化方法,如下：

(8)

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

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

(9)

3 路徑擁塞度感知

多架無人機以編隊形式對熱點地區(qū)偵察的過程中,需要共享和回傳大量的目標(biāo)數(shù)據(jù)。如果采用傳統(tǒng)的路由算法來構(gòu)建傳輸數(shù)據(jù)的路由,那么極易造成網(wǎng)絡(luò)擁塞現(xiàn)象。在無人機自組網(wǎng)中,如果出現(xiàn)網(wǎng)絡(luò)擁塞,會使網(wǎng)絡(luò)的數(shù)據(jù)傳輸性能下降,例如掉包率增加、平均端到端延時增大等。

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

3.1 緩沖占有量

節(jié)點Ni的MAC層接口隊列長度與緩沖區(qū)總長度的比值代表了當(dāng)前節(jié)點緩沖占有量BOi,表示如下:

(10)

式中：Qi為節(jié)點Ni的MAC層接口隊列長度;Qmax為當(dāng)前節(jié)點緩沖區(qū)的總長度,本文假設(shè)所有節(jié)點緩沖區(qū)的總長度相同。

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

(11)

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

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

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

(12)

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

3.2 信道負(fù)載程度

根據(jù)文獻(xiàn)[26],通過一段時間內(nèi)周期地對信道進(jìn)行采樣,便可以得到信道負(fù)載CLi，可表示為

(13)

式中：Nbusy表示該段時間內(nèi)信道處于繁忙狀態(tài)的次數(shù);Nidle表示該段時間內(nèi)信道處于空閑狀態(tài)的次數(shù)。

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

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

隨著信道負(fù)載CLi的增加,網(wǎng)絡(luò)中的擁塞現(xiàn)象會越來越嚴(yán)重。本文對CLi值進(jìn)行了多次連續(xù)測量,得到了時間t內(nèi)信道的平均負(fù)載:

(14)

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

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

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

(15)

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

(16)

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

(17)

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

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

(18)

4 基于蟻群優(yōu)化的多態(tài)感知路由算法

4.1 路由發(fā)現(xiàn)過程

由于執(zhí)行的任務(wù)不同,無人機存在多種形式的編隊,本文主要關(guān)注其編隊中無人機的密度對無人機自組網(wǎng)網(wǎng)絡(luò)路由的影響。因此,本文根據(jù)其網(wǎng)絡(luò)中節(jié)點密度提出了兩種不同的路由發(fā)現(xiàn)算法。

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

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

(1)稀疏編隊

當(dāng)某一無人機獲取到目標(biāo)信息,并需要將該信息共享至其他無人機時,當(dāng)前節(jié)點首先對本節(jié)點緩沖區(qū)內(nèi)已經(jīng)存在的路由進(jìn)行比對,如果存在能夠完成此次信息傳輸?shù)穆酚?那么根據(jù)路由選擇過程,選取最優(yōu)的路徑來傳輸該目標(biāo)信息;如果當(dāng)前節(jié)點找不到向目的節(jié)點傳輸目標(biāo)信息的路由,那么將從當(dāng)前節(jié)點啟動路由發(fā)現(xiàn)過程,向其鄰居節(jié)點中所有穩(wěn)定的節(jié)點發(fā)出前向螞蟻。與文獻(xiàn)[32]提出的洪泛方法相比,本文提出的方法能夠有效地避免洪泛廣播消息的無方向性、盲目性,提高了所發(fā)現(xiàn)路由的可靠性。

對于中間節(jié)點,如果接收到上一節(jié)點轉(zhuǎn)發(fā)來的前向螞蟻,首先對其數(shù)據(jù)包內(nèi)的跳數(shù)HC值進(jìn)行判斷,由于存儲空間的限制,HC的最大值為127,如果發(fā)現(xiàn)HC為最大值,那么該中間節(jié)點將銷毀該數(shù)據(jù)包,不再轉(zhuǎn)發(fā),以免引起路由長度測量的誤差。

其次,針對無人機自組網(wǎng)中可能出現(xiàn)的路由環(huán)路問題,本文提出了一種預(yù)防機制,能夠避免路由環(huán)路對網(wǎng)絡(luò)性能產(chǎn)生的不利影響。當(dāng)中間節(jié)點在RREQ.Ant的中間節(jié)點存儲區(qū)(INA)中發(fā)現(xiàn)本節(jié)點的地址時,就認(rèn)為該路由發(fā)現(xiàn)過程已進(jìn)入環(huán)路狀態(tài),本文首先對RREQ.Ant進(jìn)行修改,將進(jìn)入環(huán)路的節(jié)點刪除,隨后從當(dāng)前中間節(jié)點的鄰居節(jié)點中篩選出不會進(jìn)入環(huán)路的穩(wěn)定節(jié)點作為下一跳節(jié)點,并向這些節(jié)點轉(zhuǎn)發(fā)RREQ.Ant。

最后,如果未發(fā)生路由環(huán)路問題,當(dāng)前節(jié)點會查找本節(jié)點緩沖區(qū)內(nèi)是否存在能夠到達(dá)目的節(jié)點的路由,若存在,則需要對前向螞蟻中的相關(guān)信息進(jìn)行更新(例如跳數(shù)、穩(wěn)定度、擁塞度等),并啟動路由應(yīng)答過程,該方法能夠降低端到端延時和路由開銷;如果不存在可用路由,當(dāng)前節(jié)點會更新前向螞蟻,并且轉(zhuǎn)發(fā)至其穩(wěn)定的鄰居節(jié)點。

對于目的節(jié)點,如果接收到RREQ.Ant,需要對其進(jìn)行更新并啟動路由應(yīng)答過程。

(2)密集編隊

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

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

(19)

式中：m為兩節(jié)點穩(wěn)定鄰居節(jié)點中公共部分的數(shù)量;n為屬于節(jié)點F但不屬于節(jié)點D的穩(wěn)定鄰居節(jié)點的數(shù)量;q為屬于節(jié)點D但不屬于節(jié)點F的穩(wěn)定鄰居節(jié)點的數(shù)量。

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

4.1.2 路由應(yīng)答控制包傳遞過程

當(dāng)目的節(jié)點接收到RREQ.Ant時,需要將其數(shù)據(jù)包類型轉(zhuǎn)換為RREP.Ant,并沿原路徑返回至源節(jié)點。對于中間節(jié)點,如果接收到RREP.Ant,那么該節(jié)點只需要按路徑轉(zhuǎn)發(fā)即可;如果中間節(jié)點接收到RREQ.Ant并找到了到達(dá)目的節(jié)點的路由,則需要將數(shù)據(jù)包變?yōu)镽REP.Ant,同樣將其按原路徑返回源節(jié)點。當(dāng)源節(jié)點接收到RREP.Ant時,需要啟動路由選擇過程,選出最優(yōu)路徑來傳輸目標(biāo)數(shù)據(jù)。

4.1.3 路由選擇

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

(20)

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

4.1.4 目標(biāo)信息傳遞過程

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

4.2 路由維護(hù)過程

在無人機自組織網(wǎng)絡(luò)中,節(jié)點的可移動性、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化都使得路由維護(hù)顯得十分重要。路由斷路和路由死循環(huán)是路由維護(hù)中必須解決的兩個關(guān)鍵問題。

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

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

(21)

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

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

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

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

5 仿真分析結(jié)果

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

表1 仿真參數(shù)Table 1 Simulation parameter

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

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

圖3和圖4給出了無人機自組織網(wǎng)絡(luò)在無人機稀疏編隊和密集編隊的情況下,分別采用DSR、Ant-DSR、HOPNET、APAR算法在數(shù)據(jù)包成功傳輸率性能上的比較?？梢郧宄乜吹?無論是稀疏編隊還是密集編隊,本文提出的APAR算法與之前的3種算法相比,數(shù)據(jù)包成功傳輸率有較大幅度的提升。具體來說,在稀疏編隊下,APAR算法比HOPNET、Ant-DSR、DSR算法將數(shù)據(jù)包成功傳輸率分別提高了30%、60%、130%以上;在密集編隊下,本文算法比上述3種算法分別提高了40%、90%、200%以上。由于在無人機密集編隊中,節(jié)點與節(jié)點之間鏈接的可能性更大,所以APAR算法在密集編隊中有更高的數(shù)據(jù)包成功傳輸率。

圖5和圖6給出了無人機自組織網(wǎng)絡(luò)在無人機稀疏編隊和密集編隊的情況下,采用上述4種算法在平均端到端延時性能上的比較?？梢钥闯?APAR算法無論在何種情況下,與其他3種算法相比,都具有較低的端到端延時。該性能的取得主要得益于本算法的路由發(fā)現(xiàn)過程和路由維護(hù)過程。

圖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給出了無人機自組織網(wǎng)絡(luò)在無人機稀疏編隊和密集編隊的情況下,采用上述4種算法在路由開銷性能上的比較?？梢钥闯?APAR算法在無人機稀疏網(wǎng)絡(luò)和密集網(wǎng)絡(luò)中,都具有相對較低的路由開銷,在一定程度上降低了該網(wǎng)絡(luò)中節(jié)點能量的消耗。同時,由于DSR算法在路由發(fā)現(xiàn)過程中采用了洪泛機制,所以其路由開銷相對較大。

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

6 結(jié) 論

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