梁哲文，張少杰，龍 飛

（北京慧清科技有限公司，北京 101500）

0 引言

隱蔽通信網(wǎng)絡(luò)是一種不依賴基礎(chǔ)設(shè)施的移動自組織網(wǎng)絡(luò)，具有通信帶寬小、通信距離遠且網(wǎng)絡(luò)拓?fù)渥兓忍攸c[1]。為了實現(xiàn)通信的隱蔽性，隱蔽通信網(wǎng)絡(luò)的路由協(xié)議需要及時發(fā)現(xiàn)并動態(tài)維護跳數(shù)較少、傳輸可靠的路由，在保證低延時、高可靠的前提下，盡可能降低數(shù)據(jù)報文的轉(zhuǎn)發(fā)次數(shù)。目前，隱蔽通信網(wǎng)絡(luò)多采用動態(tài)源路由（Dynamic Source Routing，DSR）協(xié)議。該協(xié)議為按需路由協(xié)議，在數(shù)據(jù)報文發(fā)送時由源節(jié)點按照最短路徑準(zhǔn)則計算完整路由，不需要中繼節(jié)點進行路由計算，從而降低了路由報文的發(fā)送開銷。但是，DSR 協(xié)議沒有考慮跳數(shù)、鏈路質(zhì)量以及中繼節(jié)點緩存等對路由的影響，造成路由中斷概率高、數(shù)據(jù)傳輸延時大等問題，無法滿足隱蔽通信網(wǎng)絡(luò)的需求[2-3]。

蟻群優(yōu)化（Ant Colony Optimization，ACO）算法利用蟻群的智能功能高效地在復(fù)雜的網(wǎng)絡(luò)拓?fù)渲姓业阶顑?yōu)路徑，為隱蔽通信網(wǎng)絡(luò)路由協(xié)議的設(shè)計提供了新的思路[4-5]。文獻[6]提出了移動自組網(wǎng)蟻群路由（Ant Routing for Mobile Ad hoc Network，ARMAN）。該協(xié)議的路由發(fā)現(xiàn)過程與AODV 協(xié)議類似，在計算路由時根據(jù)端到端延時、鏈路容量等QoS 相關(guān)指標(biāo)計算信息素以及選擇概率，可以實現(xiàn)網(wǎng)絡(luò)QoS 指標(biāo)的改善。但是，該協(xié)議為逐跳路由協(xié)議，每個中繼節(jié)點都需要計算路由并選擇下一跳，因此節(jié)點需要周期性地廣播HELLO 分組來進行路由維護，不適合隱蔽通信網(wǎng)絡(luò)降低傳輸次數(shù)的需求。文獻[7]同樣針對AODV 協(xié)議做出了改進，在計算信息素時考慮傳輸可靠性、節(jié)點的擁塞狀態(tài)和剩余能量，在改善端到端性能的同時通過能量均衡提高網(wǎng)絡(luò)壽命。文獻[8]提出的蟻群路由算法（Ant based Routing Algorithm，ARA）路由旨在優(yōu)化無線傳感器網(wǎng)絡(luò)中節(jié)點的能量消耗，在節(jié)點信息素低于某個閾值時進入休眠模式以節(jié)約能量，從而實現(xiàn)節(jié)點間能量消耗的均衡。改進的蟻群路由算法（Improved ARA，IARA）對ARA 中的冗余鄰居節(jié)點進行篩選，采用角度因子和距離因子限制搜索方向，避免產(chǎn)生無關(guān)路徑。但是，該算法的節(jié)點計算復(fù)雜度高，收斂速度慢[9]。文獻[8-9]主要關(guān)注網(wǎng)絡(luò)中節(jié)點的能量消耗，無法解決隱蔽通信網(wǎng)絡(luò)對路由開銷和傳輸可靠性等指標(biāo)的要求。

針對上述問題，本文在傳統(tǒng)移動自組織網(wǎng)絡(luò)動態(tài)源路由協(xié)議基礎(chǔ)上，設(shè)計了一種基于蟻群算法的DSR 路由協(xié)議（Ant Colony based DSR，ACDSR）。本文第一次將蟻群算法融入DSR 協(xié)議，擴展了路由報文和ACK 報文并將其建模為螞蟻，將其攜帶的鏈路質(zhì)量和節(jié)點隊列緩存映射為信息素，根據(jù)路由跳數(shù)計算啟發(fā)函數(shù)計算各路由的選擇概率，動態(tài)使用選擇概率最高的路由發(fā)送數(shù)據(jù)報文。本文使用Opnet 實現(xiàn)了AC-DSR 路由協(xié)議，通過與傳統(tǒng)的DSR 路由和基于ACO 的ARMAN 路由協(xié)議的性能對比，驗證了AC-DSR 在路由協(xié)議開銷、端到端延時等方面的性能上有顯著提升。

1 基于蟻群算法的DSR 路由協(xié)議

與傳統(tǒng)DSR 協(xié)議類似[10]，AC-DSR 協(xié)議包含3個功能模塊。一是路由發(fā)現(xiàn)模塊。源節(jié)點通過路由報文的交互獲得多條通往目的節(jié)點的路由，并掌握多條路由的中繼節(jié)點隊列緩存、鏈路質(zhì)量等信息建立路由表。二是路由選擇模塊。源節(jié)點考慮路由表中各路由的跳數(shù)、中繼節(jié)點隊列緩存以及鏈路質(zhì)量等因素，實時計算各路由的信息素，并根據(jù)信息素推導(dǎo)選擇各路由發(fā)送數(shù)據(jù)報文的概率，最終使用選擇概率最高的路由發(fā)送數(shù)據(jù)報文，同時根據(jù)接收到的數(shù)據(jù)報文ACK 動態(tài)更新路由的信息素。三是路由維護模塊。發(fā)現(xiàn)路由失效的節(jié)點向源節(jié)點發(fā)送路由報文，其他中繼節(jié)點根據(jù)該路由報文更新路由表，并重新計算各路由的信息素以及對應(yīng)的路由選擇概率。

為了便于介紹，將以圖1 的典型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為例，對設(shè)計的AC-DSR 協(xié)議流程進行說明[11]。圖1 中的頂點表示通信節(jié)點，不妨假設(shè)S 為源節(jié)點，D 為目的節(jié)點，連接頂點的邊表示節(jié)點之間的無線鏈路，頂點上方數(shù)字表示該節(jié)點隊列緩存中待發(fā)送數(shù)據(jù)報文的數(shù)量，無線鏈路上的數(shù)字表示該無線鏈路的質(zhì)量。

圖1 隱蔽通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

1.1 路由發(fā)現(xiàn)

源節(jié)點S 在發(fā)送數(shù)據(jù)報文前，首先在其路由緩存表中查找是否存在到目的節(jié)點D 的可用路由。不存在可用路由時，節(jié)點S 將需要發(fā)送的數(shù)據(jù)報文加入隊列緩存，然后開始路由發(fā)現(xiàn)過程來動態(tài)查找通往目的節(jié)點的路由。AC-DSR 路由發(fā)現(xiàn)過程如圖2所示，主要包括以下幾個階段。

圖2 AC-DSR 路由發(fā)現(xiàn)過程

1.1.1 節(jié)點S 廣播發(fā)送RREQ 報文

當(dāng)前在節(jié)點S 無線傳輸范圍內(nèi)的所有節(jié)點（包括節(jié)點A 和B）都能夠接收到節(jié)點S 廣播發(fā)送RREQ 報文。節(jié)點S 發(fā)送的RREQ 報文內(nèi)容如表1所示。

路由域表示該條路由所經(jīng)過的各中繼節(jié)點的地址。鏈路質(zhì)量和緩存數(shù)量域分別表示該路由所經(jīng)各鏈路的質(zhì)量和各中繼節(jié)點的隊列緩存數(shù)。生存時間域表示該RREQ 報文剩余的可傳輸跳數(shù)。該數(shù)值與協(xié)議支持的跳數(shù)有關(guān)。

1.1.2 節(jié)點A 和B 收到節(jié)點S 發(fā)送的RREQ 報文

以節(jié)點B 為例進行說明。節(jié)點B 收到RREQ報文后，先讀取報文中的目的地址信息，發(fā)現(xiàn)自身并不是目的節(jié)點，然后讀取報文中的路由記錄，發(fā)現(xiàn)在路由記錄表中沒有記錄自身的地址。節(jié)點B 讀取RREQ ID 并搜索其維護的＜源地址,RREQ ID,路由記錄＞表，發(fā)現(xiàn)不存在＜S,1,Null＞項。因此，節(jié)點B 將＜S,1,NULL＞保存在＜源地址,RREQ ID,路由記錄＞表中，將自身地址添加到該RREQ 報文的路由記錄域中對應(yīng)的位置，計算節(jié)點S 到本節(jié)點的鏈路質(zhì)量“2”并添加到鏈路質(zhì)量域中對應(yīng)的位置，查看本節(jié)點當(dāng)前隊列緩存中待發(fā)的數(shù)據(jù)報文個數(shù)“3”并寫入緩存數(shù)量域中對應(yīng)的位置，將RREQ報文的生存時間值減1 并廣播轉(zhuǎn)發(fā)該分組。因此，節(jié)點B 轉(zhuǎn)發(fā)的RREQ 報文內(nèi)容如表2 所示，節(jié)點A轉(zhuǎn)發(fā)的RREQ 報文內(nèi)容如表3 所示。

表1 節(jié)點S 發(fā)送的RREQ 報文內(nèi)容

表2 節(jié)點B 轉(zhuǎn)發(fā)的RREQ 報文內(nèi)容

表3 節(jié)點A轉(zhuǎn)發(fā)的RREQ 報文內(nèi)容

1.1.3 節(jié)點C 收到節(jié)點A 轉(zhuǎn)發(fā)的RREQ 報文，節(jié)點C、D、F 收到節(jié)點B 轉(zhuǎn)發(fā)的RREQ 報文

節(jié)點C、F 收到RREQ 報文后的處理與1.1.2 章節(jié)中所述的處理過程類似，這里不再說明。節(jié)點D收到節(jié)點B 轉(zhuǎn)發(fā)的RREQ 報文后，讀取分組中的目的地址信息，發(fā)現(xiàn)自身地址與RREQ 報文中目的地址域相匹配，然后計算節(jié)點B 到本節(jié)點的鏈路質(zhì)量，創(chuàng)建RREP 報文回復(fù)至源節(jié)點S，并刪除收到的RREQ 分組。節(jié)點D 回復(fù)的RREP 分組內(nèi)容如表4 所示。

由于無法保證網(wǎng)絡(luò)中所有節(jié)點間的無線鏈路都是雙向鏈路，因此節(jié)點D 也將以洪泛轉(zhuǎn)發(fā)的方式回復(fù)RREP 分組至源節(jié)點S。中繼節(jié)點對收到RREP分組后的處理與RREQ 分組的處理過程相類似。

1.1.4 節(jié)點S 收到節(jié)點D 回復(fù)的RREP 報文

源節(jié)點S 收到RREP 報文后，讀取分組中的路由記錄，根據(jù)分組中的路由信息更新路由表。源節(jié)點S 維護的路由表如表5 所示。

AC-DSR 路由發(fā)現(xiàn)過程如圖2 所示。通過上述流程，源節(jié)點S 可以獲得多條通往目的節(jié)點D 的路由，并且能獲得各條路由當(dāng)前時刻的跳數(shù)、鏈路質(zhì)量、中繼節(jié)點緩存隊列中待發(fā)送報文數(shù)量等信息。下面介紹源節(jié)點根據(jù)上述路由表和路由選擇策略計算最優(yōu)路由的過程。

表4 節(jié)點D 回復(fù)的RREQ 報文內(nèi)容

表5 源節(jié)點S 維護的路由表

1.2 路由選擇

源節(jié)點收到目的節(jié)點回復(fù)的RREP 報文或者數(shù)據(jù)報文的ACK 后，將根據(jù)蟻群算法更新每一條路由的信息素和選擇概率，然后按照最大選擇概率準(zhǔn)則選擇發(fā)送數(shù)據(jù)報文的路由。路由選擇過程包括選擇概率計算和信息素更新兩個子過程。

1.2.1 選擇概率計算

與傳統(tǒng)路由協(xié)議僅考慮跳數(shù)、期望延時等影響因素不同，本文設(shè)計的基于蟻群算法的路由選擇策略綜合考慮了跳數(shù)、鏈路質(zhì)量和節(jié)點負(fù)載等因素，并參考了歷史路由選擇結(jié)果，可以獲得更優(yōu)性能。

路由跳數(shù)、鏈路質(zhì)量和節(jié)點負(fù)載等信息可以由RREP 報文和數(shù)據(jù)報文的ACK 攜帶至源節(jié)點處并動態(tài)更新，上述信息決定了每條鏈路上的信息素。在本文設(shè)計的基于蟻群算法的路由選擇策略中，路由r上某段鏈路(i,j)上的信息素用τij(t)表示，是鏈路(i,j)的鏈路質(zhì)量Lij(t)與中繼節(jié)點i緩存隊列中等待發(fā)送報文數(shù)量Ci(t)的比值，即：

路由r上的信息素，即路由r上所有鏈路的信息素之和，可以表示為：

路由r上的啟發(fā)函數(shù)值ηr(t)可以表示為：

式中，dr表示源節(jié)點到目的節(jié)點經(jīng)過路由r的跳數(shù)。顯然，該啟發(fā)函數(shù)表示螞蟻經(jīng)過路由r從源節(jié)點到目的節(jié)點的期望程度。值反映了尋優(yōu)過程中確定性因素的作用強度。值越大，表示源節(jié)點選擇最少跳數(shù)路由的可能性越大。

源節(jié)點在選擇路由時，同時受到路由上的信息素和啟發(fā)函數(shù)的影響。用R表示所有路由的集合，源節(jié)點路由r(r∈R)的選擇概率表示為：

式中：α為信息素因子，表示路徑上的信息素對路由尋優(yōu)影響的程度；β為啟發(fā)因子，表示啟發(fā)函數(shù)對路由尋優(yōu)影響的程度。作為路由信息素的冪數(shù)，α值越大，表示路由尋優(yōu)時路由報文交互和ACK 報文攜帶的信息素的影響越大，即路由尋優(yōu)主要受之前報文交互時獲得的鏈路質(zhì)量、緩存數(shù)據(jù)報文數(shù)的經(jīng)驗因素影響。作為啟發(fā)函數(shù)的冪數(shù)，β值越大，表示路由尋優(yōu)時路由跳數(shù)的影響越大，即路由尋優(yōu)主要受路由跳數(shù)這個確定性因素的影響。根據(jù)圖1 的各路由狀態(tài)信息計算得到的各路由的選擇概率如表5 所示，其中α和β均為0.3。

在AC-DSR 協(xié)議中，源節(jié)點采用最大選擇概率準(zhǔn)則選擇發(fā)送數(shù)據(jù)報文的路由，因此最優(yōu)路由可以表示為：

在后續(xù)的數(shù)據(jù)報文發(fā)送中，源節(jié)點S 會使用選擇概率最高的S-B-D 路由。根據(jù)圖1 中的拓?fù)浣Y(jié)構(gòu)可以看出，該路徑所經(jīng)過的鏈路質(zhì)量較好，同時各中繼節(jié)點隊列緩存數(shù)據(jù)量少，使用該鏈路傳輸可以獲得更優(yōu)的性能。

1.2.2 信息素更新

源節(jié)點收到目的節(jié)點回復(fù)的RREP 報文后，先根據(jù)其攜帶的鏈路質(zhì)量、中繼節(jié)點緩存數(shù)據(jù)報文個數(shù)等信息，計算各路由的初始信息素值和啟發(fā)函數(shù)值，進而計算各路由的選擇概率，而源節(jié)點將使用選擇概率最大的路由發(fā)送數(shù)據(jù)報文。源節(jié)點發(fā)送數(shù)據(jù)報文，當(dāng)收到目的節(jié)點回復(fù)的數(shù)據(jù)報文ACK 消息后，獲取ACK 消息攜帶的鏈路質(zhì)量、中間節(jié)點緩存?zhèn)€數(shù)等信息，對發(fā)送該數(shù)據(jù)報文路由的信息素值進行更新，并重新計算其路由選擇概率，以便源節(jié)點再次選擇發(fā)送數(shù)據(jù)報文的路由。

數(shù)據(jù)報文的ACK 內(nèi)容如表6 所示。

表6 數(shù)據(jù)報文的ACK 內(nèi)容

根據(jù)接收到的ACK中的鏈路質(zhì)量和緩存數(shù)量，源節(jié)點計算所選擇的路由各鏈路的信息素τij(t)，然后計算整個路由的信息素增量Δτr(t)為：

最終該路由的信息素可以更新為：

式中，ρ為信息素?fù)]發(fā)因子，ρ∈[0,1]，1-ρ表示信息素殘留因子。

1.3 路由維護

路由發(fā)現(xiàn)過程完成后，數(shù)據(jù)報文會沿著其攜帶的源路由所指定的路徑，依次被中間節(jié)點轉(zhuǎn)發(fā)至目的節(jié)點。但是，由于網(wǎng)絡(luò)拓?fù)浜玩溌焚|(zhì)量不斷動態(tài)變化等因素，可能會使源路由中某些相鄰節(jié)點不在彼此的通信范圍內(nèi)，導(dǎo)致當(dāng)前正在使用的源路由因為中間一些鏈路的中斷而不能成功轉(zhuǎn)發(fā)數(shù)據(jù)報文到目的節(jié)點，因此需要路由維護過程來修復(fù)路由。

在AC-DSR 協(xié)議中，中繼節(jié)點收到數(shù)據(jù)報文后，根據(jù)數(shù)據(jù)報文中包含的路由信息向下一跳發(fā)送數(shù)據(jù)報文。如果節(jié)點在設(shè)定的重發(fā)次數(shù)內(nèi)收到下一跳節(jié)點回復(fù)的確認(rèn)消息，則可以確定兩節(jié)點間的鏈路狀態(tài)正常；否則，認(rèn)為鏈路中斷，開始路由維護過程。

如圖3 所示，當(dāng)節(jié)點B、D 之間的鏈路中斷后，路由維護過程如下。節(jié)點B 確認(rèn)鏈路中斷后，開始路由維護過程，需要創(chuàng)建并向源節(jié)點S 發(fā)送路由錯誤報文RERR。根據(jù)RERR 報文指定的路徑，沿途轉(zhuǎn)發(fā)該報文的節(jié)點。如果它的路由列表中存有包含中斷鏈路的路由信息，必須被全部刪除。然后，節(jié)點檢查其自身的路由緩存，若存在另一條有效路由到達數(shù)據(jù)報文的目的節(jié)點，則利用這條路由來替代原有的路由將數(shù)據(jù)報文轉(zhuǎn)發(fā)至目的節(jié)點。

源節(jié)點S 收到RERR 報文后，會根據(jù)報文中攜帶的中斷鏈路信息刪除其路由緩存中相應(yīng)的失效路由。若源節(jié)點與目的節(jié)點之間仍存在通信業(yè)務(wù)，且源節(jié)點更新后的路由列表中有其他到目的節(jié)點的路由，則直接使用這條路由發(fā)送數(shù)據(jù)報文，否則將重新發(fā)起路由發(fā)現(xiàn)過程。

圖3 AC-DSR 路由維護過程

2 性能仿真與分析

本文提出的AC-DSR 協(xié)議的仿真實驗在Opnet環(huán)境下進行，在2 km×2 km 的區(qū)域內(nèi)隨機分布5個通信節(jié)點搭建移動自組織網(wǎng)絡(luò)，并與經(jīng)典的DSR協(xié)議和基于蟻群優(yōu)化的AODV 路由協(xié)議ARMAN 就端到端延時和路由開銷性能進行對比分析。仿真場景如圖4 所示，表7 為仿真實驗參數(shù)設(shè)置情況。

圖4 仿真使用的網(wǎng)絡(luò)場景

表7 仿真實驗環(huán)境與參數(shù)設(shè)置

圖5 顯示的是數(shù)據(jù)報文端到端延時性能隨時間變化的曲線?？梢钥闯?，與傳統(tǒng)DSR 協(xié)議相比，基于蟻群優(yōu)化的ARMAN 和本文提出的AC-DSR 協(xié)議都可以獲得更低的端到端延時性能。究其原因，以圖4 時刻的網(wǎng)絡(luò)拓?fù)錇槔M行說明。當(dāng)使用傳統(tǒng)的DSR 協(xié)議時，源節(jié)點總是使用路徑最短的路由，因此源節(jié)點0 向節(jié)點4 發(fā)送數(shù)據(jù)報文時總會選擇路由“0-2-3-4”，造成節(jié)點2 處負(fù)載較重。發(fā)送隊列緩存較長，源節(jié)點0 發(fā)出的數(shù)據(jù)報文在節(jié)點2 的緩存隊列中等待較長時間才可以發(fā)往下一跳節(jié)點3，最終導(dǎo)致較長的端到端延時。但是，基于蟻群優(yōu)化的ARMAN 和AC-DSR 協(xié)議可以根據(jù)隊列緩存和鏈路質(zhì)量實時計算各路徑的信息素并更新選擇概率，當(dāng)節(jié)點2 隊列緩存較長時，選擇隊列緩存更優(yōu)的節(jié)點1 作為中繼節(jié)點，從而降低了端到端延時。

圖5 端到端延時性能隨時間變化曲線

圖6 顯示的是路由協(xié)議的額外開銷隨時間變化的曲線?？梢钥闯觯珼SR 和AC-DSR 協(xié)議路由報文的開銷遠低于ARMAN 協(xié)議。這主要是由于ARMAN 屬于逐跳路由協(xié)議，每一個節(jié)點都要周期性發(fā)送路由報文以維護與鄰節(jié)點的路由，而DSR 和AC-DSR 都屬于源路由協(xié)議，由源節(jié)點維護路由信息且僅在有數(shù)據(jù)報文發(fā)送時才發(fā)送路由報文以獲得到目的節(jié)點的路由信息，減少了發(fā)送的路由報文的數(shù)量，因此擁有更少的路由額外開銷。

圖6 路由協(xié)議額外開銷隨時間變化曲線

3 結(jié)語

隱蔽通信網(wǎng)絡(luò)需要在保證低延時、高可靠的前提下盡量減少報文的發(fā)送次數(shù)，這對路由協(xié)議提出了新的挑戰(zhàn)。本文設(shè)計的AC-DSR 將蟻群優(yōu)化思想融入DSR 協(xié)議設(shè)計，可根據(jù)路由跳數(shù)、鏈路質(zhì)量、緩存等狀態(tài)實時更新路由的選擇概率，能夠達到減少數(shù)據(jù)報文端到端延時和降低路由協(xié)議額外開銷的目標(biāo)，為隱蔽通信網(wǎng)絡(luò)路由協(xié)議設(shè)計提供了新的思路。