基于改進蟻群算法的應急通信網絡路由協議

宋方振，徐彥彥，唐 鑫，潘少明

武漢大學 測繪遙感國家重點實驗室，武漢 430079

1 引言

自然災害和公共突發事件會造成傳統通信手段失效，如何啟動應急通信機制，快速高效地構建應急通信網絡，提升網絡的傳輸效能，成為亟待解決的問題[1]。應急通信具有發生的時間和地點不確定性、通信需求不可預測性、業務緊急性、網絡構建快速性、節點移動性等特點[1]，移動無線自組網（MANET）[2]具有網絡自組織和協同合作的特征，非常適合在事發現場組建應急通信網絡來協調各類人員開展救援行動和應對突發事件。應急MANET[3]具有更高的Qos傳輸要求，并且要求網絡能夠較好地適應通信擁塞及快速變化的網絡拓撲結構，如何設計合理的路由算法，實現路由選擇及資源的優化配置是應急MANET的核心。

傳統MANET路由協議使用靜態路由決策機制，無法對網絡擁塞進行感知并做出相應調整，不適用于應急通信[4]。近年來仿生學在MANET路由中的應用展現了突出的優勢[5]，其中蟻群算法以其能夠有效適應MANET網絡拓撲的動態變化，最終建立收斂的最優路徑等特點而得到廣泛應用[6]。文獻[7]提出了一種ARA路由協議，目的是使用蟻群元啟發方法降低網絡的路由開銷。文獻[8]提出的Ant-AODV 路由協議結合按需路由協議AODV和蟻群算法，有效降低了網絡的端到端時延和路由發現等待間隔。文獻[9]提出的Ant Hocnet是一種多徑路由算法，包括被動發現和主動維護路由組件，其中被動發現過程存在于相互通信的節點間，而主動維護過程存在于相鄰節點間用于更新和維持路由表項。文獻[10]中Hopnet 是基于蟻群算法的混合路由協議，同時搭載區域路由框架用于分區間的螞蟻包跳轉傳遞。文獻[11]提出PERA（Probabilistic Emergent Routing Algorithm）路由協議，在該協議中數據包使用確定的路由路徑，即蟻群探索得到的最佳質量保證路徑，而前向螞蟻包則使用廣播機制以發現到目的節點的多條備選路徑。文獻[12]提出MABR（Mobile Ant Based Routing）路由協議，采用主動式路由方案釋放前后向螞蟻周期性地更新網絡狀態信息，該算法同時利用節點地理分區信息進行信息素的產生。

上述路由協議的共同特點是均使用前向螞蟻采集網絡信息，當前向螞蟻到達目標節點后再釋放反向螞蟻對經過路徑節點進行信息素更新，在高度動態變化的MANET 網絡中，上述機制不再適用[13]。針對應急通信網絡較高的節點移動性和突發的網絡擁塞狀況，本文提出一種結合強化學習的改進蟻群路由協議MLSA（Modelbased Learning Strategy combine with ACO），依概率釋放局部探測螞蟻包，收集網絡狀態信息進行系統建模，從而動態評估鏈路狀態，進行最優路徑的選取。考慮整個路由過程中，每個節點對下一跳的選取決策，可以等效為局部的馬爾可夫過程[14-16]，通過調整決策過程與網絡環境間的相互作用，達到路由節點對網絡動態變化與擁塞程度的智能感知；同時保留蟻群算法并行、多徑可達的特點，使得在網絡拓撲或流量分布發生變化時，路由決策能夠動態調整到新的最優路徑并對網絡擁塞進行流量均衡。仿真實驗證明了本文提出方法的有效性。

2 傳統蟻群路由算法

傳統蟻群優化算法使用一組螞蟻協同作用，尋找問題的最優解，即整個探索路徑的最小消費[17]。蟻群搜索過程開始于一個特定的起始狀態，使用概率選擇模型決定下一個移動的鄰居狀態，最終收斂于一個或多個結束狀態，如公式（1）所示：

其中，τij為信息素，即為路徑ci和cj間存在影響該路徑選擇概率大小的評價值；ηij為系統先驗信息，該先驗信息對應于強化學習中的探索過程，蟻群在搜索過程中將受到ηij的影響；α和β分別為剩余信息素值τij與期望函數ηij的權重因子；allowedk為所有下一跳鄰居節點構成的集合，表示第k只前向螞蟻fant從節點vi選擇節點vj作為下一跳的概率。

每只螞蟻在路徑尋優時會記錄所經過的路徑，以及路徑節點的相關信息，因此在到達目標節點時能夠利用這些路徑信息對求解過程進行評估，并且反向更新所經過路徑上的信息素值，如公式（2）所示：

其中，ρ∈( 0,1) 表示信息素τij隨時間的推移而衰減的程度，Δτij為螞蟻所選路徑的單次信息素累積量。

通過蟻群算法的正反饋作用，同時結合相鄰節點i、j間網絡Qos 鏈路狀態信息的加權和作為啟發值函數ηij，如公式（3）所示：

其中，N為所選Qos 評估指標總數，Qij(m)為相鄰網絡節點i、j間第m個Qos 鏈路狀態信息評估值，αm為第m個Qos 評估值的權重因子。網絡中帶寬較大、丟包率較小、時延低的多條路徑被篩選出來，作為后續數據傳輸中使用的首選傳輸路徑。

在路徑探索過程中，每只螞蟻獨立地對環境產生影響，體現在高質量路徑上信息素值τij的不斷積累，環境反過來對每只螞蟻的決策過程產生指導，后續蟻群將更加集中在信息素濃度較高的路徑上。這種正反饋的產生使得蟻群算法極易收斂在局部最優解上，并且難以進行控制。傳統蟻群算法作為典型模型無關的強化學習算法，盡管降低了計算復雜度，但其實驗敏感，即對應于不同的起始狀態趨向于不同收斂解的特性，使得探索搜索過程難以收斂到全局最優解。此外，由于應急網絡具有節點機動性及網絡狀態高度動態變化的特性，網絡拓撲更新間隔較短，往往前向螞蟻剛剛到達目的節點，路由包中記錄的路徑信息已經由于網絡拓撲的變化而失效，信息素的積累過程被擱置，中間節點不斷開啟路徑修復過程，致使路由信息不穩定和難以長期維護。因此，傳統蟻群算法難以適用于應急通信網絡。

3 結合強化學習的改進蟻群路由算法

針對上述問題，本文提出一種結合強化學習的改進蟻群路由算法（MLSA），通過系統探測和評估同步的連續建模，解決傳統蟻群算法易陷入局部最優及路由決策過程緩慢的問題。MLSA 使用強化學習模型進行系統建模，感知系統路由狀態變化并記錄動作產生的回報；利用上述模型對系統局部進行連續探測，并采用時間軸加窗的方式加速信息素的衰減；在數據傳輸過程依據Qos優先函數限制進行最優數據的傳輸，同時更新各節點網絡狀態。

3.1 網絡模型及問題定義

根據應急通信的具體需求，使用丟包率、時延、傳輸開銷的加權和作為系統評估的強化函數，根據不同的Qos 需求，動態調整三者的權重。整個尋優過程為在具體Qos 指標限定下，尋找使得核函數取得最大值的從源節點S到目的節點D的最優路徑，當有新的數據傳輸任務到來時，系統依參數啟動路徑搜索和數據傳輸過程。

假設應急響應系統網絡的部署環境是二維平面拓撲，其網絡拓撲可抽象成帶權有向圖G(V,E)，其中：V為移動節點集合，節點個數n=|V|；E為單跳通信鏈路集合，對任意單跳通信鏈路eij=e(vi,vj)∈E,vi,vj∈V,i≠j,i,j=1,2,…,n，當且僅當vi與vj在單跳通信范圍內可通信。G中每條鏈路eij包含時延、帶寬、丟包率、時延抖動等通信代價參數。根據應急響應通信系統的應用特點，如數據傳輸實時性與質量保障，考慮時延、帶寬與丟包率這3 個參數，其中：時延包括中繼節點上的排隊與處理時延和鏈路傳輸時延，丟包率包括節點緩沖區溢出丟包與信道間干擾丟包，帶寬即為鏈路允許的最大數據傳輸速率。對應于每一單跳通信鏈路eij∈E，其權值用一個三元組(b(vi,vj),d(vi,vj),l(vi,vj))表示，分別表示鏈路帶寬、鏈路時延與鏈路丟包率。

定義1（可行路徑）給定網絡G，如果從源節點source 到目的節點destination 通過多跳存在一條路徑p={v1,v2,…,vn} ，能夠將數據從source 節點傳輸到destination 節點，則稱p為一條可行路徑。

定義2（路徑Qos 參數）給定一條可行路徑p={v1,v2,…,vn}，設其路徑包括節點的個數為n，則路徑p的Qos 參數為路徑帶寬、路徑時延、路徑丟包率。根據參數凹性特征，其定義如下：

其中，B(p)、D(p)、L(p)分別表示路徑帶寬、路徑時延與路徑丟包率。

定義3（路徑優先函數）給定一條路徑p，其優先級函數綜合考慮定義2 中路徑的3 個Qos 參數，優先函數f(p)定義如下：

其中，Bmin與Dmax分別是應急響應系統數據傳輸所能容忍的最小帶寬與最大路徑時延，α、β、γ分別是3 種Qos 參數的權重因子，三者的范圍為[0,1],α+β+γ=1。通過公式（7）的處理，路徑優先函數的取值范圍為[0,1]。

本文所提出的算法MLSA 將利用路由發現過程得到的多條可行路徑，在相應路徑優先函數f(p)的條件限制下進行數據的逐跳傳遞，結合強化學習過程進行網絡擁塞的實時感知，完成系統流量的均衡及路徑的動態更新。

3.2 使用強化學習模型進行系統建模

強化學習模型通過感知系統現有狀態，評估計算采取下一行為對系統帶來的增益，從而選擇執行對系統狀態帶來較大增益的行為；節點執行狀態更改決策后，收到執行該行為獲取的系統增益值[18]。如圖1 所示，網絡中各個節點在路由發現過程t時刻采取不同的動作策略ai(t)，共同對整個網絡進行影響，節點完成從狀態si(t)到狀態si(t+1) 的轉換，獲得環境回饋的相應回報值ri(t+1) ，各節點重新評估自身價值函數Vi(s)并將其廣播到鄰居節點；此外，其他未被采用策略集上積累的信息素含量隨時間的流逝而蒸發。

圖1 強化學習決策過程

由于提前引入了數據包傳輸的最大TTL值，即數據傳輸過程中系統的狀態轉移次數總是限制在整體系統狀態集S內，單一節點的系統狀態評估值可應用無限視野價值評估模型：

進行計算，同時設置未來有限步內的系統狀態轉換所帶來的增益rt具有相同的權重γ。系統優化問題轉化為，調整從源節點S到目的節點D經過的所有數據傳輸節點的決策過程，以取得最大的價值函數V(s)值，下面介紹求解過程。

定義系統狀態集為S，當前狀態下可以執行的動作集為A，則系統增益R和狀態轉移分布函數T均可表示為S和A的某種運算結果，這里用R(s,a)表示從狀態s執行動作a帶來的系統增益，T(s,a,s′)表示s經過動作a后轉移到s′的概率。通過求解貝爾曼方程可以得到系統的最優解V*(s)：

其中，γ為狀態轉移增益權重，V*(s′ )對應于狀態集S中每個狀態s′的當前價值評估值。相應的，采取使得價值評估函數V*(s)取得最大值的動作a作為下一步的狀態轉移操作。

取T(s,a,s′ )為每條通信鏈路數據投遞成功與失敗的比例，為了計算T(s,a,s′ )，在每個節點記錄嘗試發送的單播包數NA、單播傳輸失敗包數NF、接收到的單播包數NR、接收到的廣播包數NB和混雜接收單播包數NP等統計量；考慮網絡的動態變化性，指定有效統計時間窗口，即選取從當前時間往前的一段時間內的統計量作為有效統計量。對于單個節點來說，自身發送數據包的統計值較成功接收數據包的統計值具有更高的可信度，因此在計算投遞率時，接收數據包統計量前添加置信參數σ；此外，將ρ作為節點未發送數據包時的投遞率估計值，最終投遞率計算公式表示為：

公式（10）對應系統下一狀態切換到投遞成功s′=S時的轉移概率T(s,a,S)。在路由過程中，對于一次成功的數據傳輸，其消耗的系統能量最小，將該過程獲得的強化函數值標記為rS，其系統消費歸一化為-1；同樣地，對于一次失敗的單跳數據傳輸，將該過程獲得的強化函數值記為rF=-7，其系統消費對應于底層802.11 MAC 協議的最大重傳次數7[19]。由于指定了rS和rF為確定值(-1和-7)，相應的

為T(s,a,s′ )的簡單組合函數。確定了評估模型T(s,a,s′ )、R(s,a)，最優值函數V(s)的計算可以通過求解貝爾曼方程：

考慮每個動作集a僅導致當前狀態s朝兩種可能的狀態轉變，假設下一跳節點為P，則系統的狀態轉變為：發生傳輸成功事件S，使得系統由當前狀態s=N轉化到s′=P；或發生傳輸失敗事件F，使得系統當前狀態s=N保持停留從而s′=N。因此系統Q值的計算如下式所示：

其中，pS是數據包成功傳輸到節點P的概率，相應的pF是傳輸失敗的概率。根據公式（14）：

轉化為求解

從而

一旦最優值函數由評估模型計算得到，最佳的決策過程便是采取使每個狀態能夠獲得最大Q值的動作，稱該優化決策過程為系統的開發策略。鑒于開發策略是由系統評估模型計算得到，而應急網絡具有較高動態性，評估模型會隨著時間變化；同時評估模型又依賴于系統的探測過程，因此為了執行較優的開發策略，需要對系統進行連續的探測。

3.3 系統模型的連續探測

為了利用已學習到的系統知識進行決策過程，并且同時能夠連續地對系統進行探測過程，以更新系統模型，本文提出使用如下策略：

（1）使用玻爾茲曼決策過程，對系統已知的動作集進行概率轉移，根據執行動作回饋信息更新網絡模型，有利于控制系統探測過程的頻次，使路由選擇朝著最優的方向前進，決策過程如下式所示：

其中，u(a)反應了決策a對系統帶來的實際效用，參數T反應了系統選擇次優決策過程的可能性，即參數T越大，系統選擇次優決策的可能性越大，該參數將極大影響系統建模所需的探測過程頻次。

（2）設計周期性的探測過程用來發現鄰居節點，在路由過程中選擇價值函數較高的節點作為下一跳。當一個節點嘗試發送單播或廣播數據包時，會在數據包頭添加關于源節點S和目的節點D的最優值估計，當鄰居節點接收到該數據包后，會利用這些估計值更新自身對S和D的最優值記錄。此外，考慮到系統網絡拓撲的動態變化性，同時需要對舊的記錄值進行蒸發操作，以不斷減小無用信息對路由決策的影響，具體更新過程如式（18）所示：

圖2 數據包格式

其中，Vadv(s)是該節點最后接收到的關于節點s的最優值通告，ΔT(s)是從最后一次接收到該通告值過去的時間，λ用來控制記錄值的消散速率。

（3）為了限制探索過程只在對系統感興趣的相關部分進行，且保證發送數據包較探測過程的優先級，使用貪婪算法規避對當前決策無用的部分進行探測。由于系統全局信息難以獲取，本文提出的方法只計算處于數據包投遞路線上相關節點的價值函數而不是針對整個網絡的所有節點進行計算。MLSA 將采用按需路由的方式，即當有數據請求到來時才進行路由發現過程，因此可以將相關的系統評估信息附加在數據包上用于鄰居節點信息素的更新，使得學習過程僅在數據傳輸鏈路附近進行，從而縮減了系統開銷；此外，將評估信息附加在數據包上進行傳遞，較發送獨立的路由包而言降低了網絡傳輸負載。

4 MLSA算法實現

根據協議設計策略，構造數據包格式如圖2。其中，括號中數字表示對應域所占字節數，單位：字節（Byte）。

其中，Qos 參數需求指示下一跳最低傳輸限制，對應于優先函數f(p)限制值；源節點價值函數估計值記錄了數據包原始傳輸節點價值函數VS(s)值，目的節點價值函數估計值記錄了目的節點價值函數VD(s)值；錯誤標記位指示數據包傳遞過程中下一跳是否發生傳輸失?。欢鴶祿蛄刑柨梢杂脕砼袛嗍欠袷盏街貜蛨笪?，并執行相應的丟棄操作。

MLSA路由算法流程概述如下：

（1）系統啟動階段，網絡各節點進行鄰居發現并收集各鏈路Qos 狀態信息。

（2）當數據傳輸任務到來時，檢測路由表項中是否存在到目標節點的路由條目，存在則根據公式（7）選擇相應的路徑進行數據傳輸；否則啟動路由發現過程。

（3）當節點收到路由包時，檢測是否是重復路由包，并丟棄重復路由包；若數據包目的節點為當前節點，發送后向螞蟻包通告源節點S數據傳遞成功，更新當前價值函數V(s)的值，并廣播到鄰居節點；若數據包記錄目的IP地址非本節點，則選擇鄰居節點中對應價值函數值最大的動作a，進行到下一跳的數據傳遞。

（4）路由建立階段，當節點收到路由發現廣播包時，按照公式（16）的玻爾茲曼探測模型，結合鄰居節點的價值函數，進行連續探測過程；同時更新系統狀態評估模型，建立到目標節點的最優路徑，該過程將統計鏈路丟包率、時延、帶寬等狀態信息。

（5）數據傳輸過程中，若當前節點找不到滿足路徑優先函數f(p)限制條件下，指定動作所a對應的下一跳節點，則以該節點為源節點S進行路由發現過程，轉至步驟（4）。

（6）在數據包傳遞過程中，前向螞蟻包到達的每一跳路由節點，將根據采取的動作a所帶來的回報值ri(t+ 1)更新自身價值函數V(s)，并將新的價值函數廣播到鄰居節點；從而該節點在相關路徑上積累了較高的信息素含量，以該節點作為下一跳的決策a，在鄰居節點的動作集中具有較高的選擇優先級。同時，鏈路性能較差或移動性較強的節點，僅在其通信局部范圍內擁有較高的價值函數而被選取為備選路徑；而在其他網絡節點的信息素更新策略中，僅按照公式（17）進行信息素累積量的衰減。

5 MLSA算法評估

使用NS2進行MLSA路由算法的網絡仿真，配置仿真場景對應于實際應急網絡環境，即網絡擁有少量服務器節點（這里配置為3），作為Mesh子網絡邊界的網關節點，同時設置大量網絡無線節點，具有1～60 m/s 不等的移動速度，運動方向設置為在二維平面內隨機做出選擇；各移動節點配置為在任意時刻，以隨機通信時長間隔的方式，進行到鄰近服務器節點的數據傳輸，傳輸數據為指定大小（512 Byte）的udp數據包。其他網絡參數配置為，仿真場景大小1 000 m×400 m，使用802.11作為MAC層協議，無線傳播模型為two-ray-ground。最后做出說明，對于移動節點到服務器（接入點）的選擇，將由路由算法根據到鄰居節點的強化學習評價值進行自主決策，優先連接到強化學習評價值最高的服務器節點。實驗拓撲如圖3所示。

圖3 實驗拓撲環境

該場景下網絡節點數設置為30～50，當移動節點數小于15 時，由于平均范圍內節點數目過少而無法建立持續有效的傳輸鏈路，導致網絡數據傳輸不能正常進行；節點數大于60時，由于節點數量增加帶來的局部網絡擁塞較為嚴重，無法繼續通過增加網絡負載有效控制網絡整體擁塞程度。最終對照實驗取網絡節點數目為45。

此外，全局蟻群算法尋優參數設置如下，對應公式（1）中剩余信息素值τij權重因子α取0.5，期望函數ηij權重因子β取1，該部分參數的獲取為在α 取值范圍為0.1～0.9，β取值范圍為1～5，經過大量對照實驗得到的能使蟻群算法快速收斂的最優參數解；局部強化學習模型中評價參數設置如下，對應公式（11）中一次成功傳遞的強化函數反饋值rS取-1，一次失敗傳遞的強化函數懲罰值rF取-7，該部分參數的設置充分考慮底層802.11 MAC協議的最大重傳次數為7，并將一次數據包傳遞產生的代價歸一化為1。實驗證明，取以上組合參數有利于蟻群快速尋優和強化收斂過程的完成。

為了測試MLSA對網絡擁塞的適應能力，逐漸加大網絡通信負載的數據傳輸率，與按需路由的代表協議DSR[20]及AODV[21]進行同一場景下的數據傳輸性能對比，實驗結果如圖4～6 所示。其中圖4 顯示了隨著擁塞程度的增加，DSR和AODV的投遞率迅速降低，而MLSA協議由于使用了對系統的動態探測過程，不斷更改最優路徑決策，使網絡流量盡可能多地分配到更多次優的鏈路上（全局次優，當前最優），從而在很大程度上緩和了網絡的擁塞程度，數據包投遞率下降緩慢。

圖4 網絡擁塞對投遞率的影響

圖5 網絡擁塞對傳輸時延的影響

圖6 網絡擁塞對吞吐量的影響

圖5 顯示了在網絡擁塞的情況下，AODV 和MLSA均表現出較低的平均數據傳輸端到端時延，總體上看，MLSA平均時延變化較為穩定，呈現與擁塞程度增長的正比例關系，且相對于其他兩個路由協議在同一量級的網絡擁塞下具有更小的平均傳輸延時。

圖6 顯示了在擁塞情況下三個路由協議網絡吞吐量的表現，AODV 和DSR 曲線的網絡吞吐量先是隨著網絡負載通信流量的增加而快速增長，最后網絡吞吐量趨于一個上限閾值，實際上，在路由表記錄的最優路徑上，大量數據包未能被成功緩存而丟棄，體現在圖4 中數據投遞率的下降；而MLSA由于使用對系統的動態探索估計，當發現最優路徑上存在擁塞情況時，能及時調整尋優策略，改選路徑發現階段記錄的次優路由條目進行流量均衡，然而，由于無線自組織網絡中每個節點的鄰居數目有限，當網絡擁塞持續增加時，數據傳輸節點無法再將多余的流量平均到更多的路徑上，從而導致網絡吞吐量的下降和丟包率的上升。

6 結論

本文針對應急通信中網絡拓撲的快速動態變化及突發的網絡擁塞現象，詳細分析了傳統蟻群路由算法在該應用場景下不再適用的原因，提出了一種適用于應急通信網絡的路由算法MLSA，利用蟻群算法框架結合強化學習過程進行系統建模，將網絡鏈路性能統計分析過程限制在較高優先級的區域，通過探測局部鄰居節點的狀態信息，對不同路由決策過程進行打分，并根據網絡反饋做出策略調整，從而改善網絡整體性能，有利于緩解網絡擁塞，增加了數據傳輸的實時性、穩定性。實驗證明，在較高節點移動性環境下，針對應急通信中產生的網絡擁塞現象，MLSA較經典按需路由協議AODV和DSR，具有明顯的性能優勢。