一種基于排序蟻群算法的無線Mesh 多徑路由協議*

彭 藝，李啟騫，朱 豪，張 申

（昆明理工大學 信息工程與自動化學院，云南 昆明 650000）

0 引言

無線Mesh 網的組成部分有骨干網和客戶端兩部分。大量的無線路由器組成骨干網，與外接Internet 網絡連接，客戶端部分則和骨干網相連，從而構成一個區域性的臨時自組織通信網格網。在無線Mesh 網絡的通信環境下，Mesh 網絡的拓撲結構比較穩定，但是傳統的單徑路由協議還存在很大的不足。例如，把無線Mesh 網絡放在高原山區環境下，單徑路由會存在很大的路由中斷可能。所以，本文擬研究一種多徑路由的協議方法，從源節點到目的節點間，通過蟻群算法計算出多條可供使用的路由路徑，最后選擇最優的兩條路由鏈路并行傳輸，使得傳輸過程中一條鏈路出現斷裂的情況下可以馬上使用備選路由，保證通信的穩定性和可靠性。

由于無線Mesh 網絡的前景漸漸得到了廣大學者的認可，目前關于無線Mesh 網的路由技術研究已有一定量的成果[1-5]。文獻[6]提出基于粒子群算法優化的無線Mesh 網絡多徑路由發現方法，并且定義擁塞預測度和節點轉發優良度函數作為粒子群算法模型的適應度函數，以保證計算所得路徑的有效性和高效性。文獻[7]提出把蟻群算法的TSP 問題求解能力運用到無線Mesh 網的路由尋優上，并證明了蟻群算法可以快速高效地找到最優最短的路由鏈路。文獻[8]描述了一種改進的基于蟻群算法的能量優化算法，在蟻群算法實現的基礎上加入距離帶和限制搜索角的概念，當某個節點在傳輸過程中過“熱”時，篩選出“熱”剩余能量不足和距離較遠的“熱”點，并且在路由尋優時在節點候選列表中去掉，從而避免“熱”點負載過重增加Mesh網絡的生存周期。文獻[9]從無線自組網ZigBee 網絡的負載均衡角度出發，研究分析AOMDV 算法在ZigBee 通信網應用的優點和缺點，提出改進型蟻群算法。該算法基于蟻群尋優，加入多徑搜索，多徑并行傳輸消息，解決了傳統蟻群算法尋優慢且不靈活的缺點，并且有效避免鏈路了中斷重新尋找路由的時間開銷，有較好的穩定性和可靠性。文獻[10]提出一種基于MAC 層剩余能量判據的蟻群算法，把設備的剩余能量考慮到路由節點的選擇上，路由判據不再是單一的路徑最短，從而豐富蟻群算法的魯棒性以及在不同場景的適應度。其次，在新算法的基礎上融入多徑搜索，以鏈路關聯度為判據，盡可能搜索出多條不相關的路由鏈路并行傳輸，提高網絡的QoS 滿意度。文獻[11]從通信的QoS 滿意度角度出發，針對普通的多播樹路由協議缺少帶寬請求考慮的問題，提出了一種MQMR 協議。該協議通過控制動態時隙，使得路徑的聚合帶寬可以滿足帶寬的調用要求，最后實現減少網絡阻塞和提高呼叫成功率方面的有效性。文獻[12]提出了一種EQSR 協議，綜合考慮無線自組網實際使用的各種參數，包括節點實時能量、節點的實時擁堵程度和傳輸環境的信噪比，并基于這些參數計算鄰居節點的轉發滿意度，從而達到網絡負載均衡，避免部分節點負載過大的效果，減少丟包率，提高傳輸成功率。

1 網絡模型與問題描述

1.1 無線Mesh 網傳輸模型

無線Mesh 網的網絡結構分為骨干網、終端網和混合網3 種。本文算法研究主要是針對骨干網的路由鏈路選擇，所以下面簡單介紹無線Mesh 的骨干網拓撲結構。

骨干網由少量的Mesh 網關和多個Mesh 路由器組成。每個路由器互聯互通構成Mesh 骨干網。節點之間既可以直連近距離通信，也可以通過多跳傳輸的方式協助完成遠距離通信。當兩個Mesh 節點距離超出相互的傳輸接收范圍時，就需要啟動路由尋找機制尋找多跳路由，實現遠距離通信。下面是無線Mesh 骨干網的拓撲示意圖，圖1 和圖2 表示一個多跳傳輸情況。

圖1 無線Mesh 骨干網原路由鏈路

圖2 無線Mesh 骨干網新路由鏈路

從無線Mesh 網絡模型可知，消息需要從源節點S傳輸到目的節點D，原鏈路是S →A →C →E →D。但是，因為出現一些特殊情況，A 和C 的鏈路斷開了。當節點A 知道和下一跳節點C 失聯后，會把傳輸失敗的消息原路返回給源節點S。源節點S 收到后，重新發起路由尋找請求，找到新的可通路由S →A →B →E →D，使得消息傳輸成功。可見，在無線Mesh 網絡下，消息傳輸的路徑靈活多變，魯棒性強。

1.2 蟻群算法

蟻群算法源于意大利學者M.Dorigo、V.Maniezzo和A.Colorni 等人提出的自然種群仿生算法，開始主要用于求解TSP 問題，根據蟻群覓食習慣，在走過的路上留下信息素，后來的螞蟻會根據路徑積累的信息素選擇路徑，使得覓食路徑漸漸收斂于一條最短最優的路徑。后來蟻群算法也被廣泛應用到路由鏈路的尋優問題上，文獻[7]證明了蟻群算法可以快速高效地找到最優最短的路由鏈路。

1.3 傳統的蟻群算法存在的不足

傳統的單徑路由中存在著鏈路斷裂的問題。在自然界的蟻群尋找食物過程，螞蟻會根據路徑的信息素濃度選擇路徑。信息素（Pheromone）與經過的螞蟻數目相關的，但考慮的前提是蟻群經過的路徑是一條普通的路，不像無線Mesh 網存在帶寬限制，也不存在因節點負載過大導致消息列表擁堵或消息丟包的情況。所以，要把蟻群算法應用到無線Mesh 網的路由尋優問題上不能單一只考慮路徑的長短，還要綜合考慮無線Mesh 網的實際負載和布網環境的情況。同時，如果使用傳統蟻群算法的單徑路由，丟失后網絡要重新尋找路由，將會增加傳輸時延和網絡開銷。

傳統的蟻群算法中，螞蟻根據每條路徑的信息素強弱選擇信息素較多的路徑，然后在所經過的路徑上留下等量信息素。這種傳統的蟻群尋優算法在實現的初始會存在尋優速度慢的缺點。

2 Fortified Ant 路由協議介紹

針對上面的兩個問題，本文提出一種可以修復斷裂鏈路的基于排序蟻群算法的無線Mesh 網絡多徑路由協議——Fortified Ant 協議。首先，該協議在傳統的蟻群算法中引入排序算法，排名靠前的螞蟻可以釋放更多的信息素，排名的權值計算加入路徑長度、信道的信噪比和節點當前負載大小3 個參數共同決定，從而優化蟻群尋優得出的最優路徑。其次，引入多徑路由機制，前期路由尋優時搜索多條優質鏈路，取其中兩條作主備鏈路并行傳輸，增強網絡消息傳輸的時效性和可靠性。Fortified Ant 路由協議的實現分為統計路由表、發起路由發現請求、信息素更新、路由選擇和路由維護5 個部分。

2.1 路由表

Fortified Ant 路由協議設置了一張路由表，用于分類及維護路由發現的信息。每張路由表存儲著5 個主要信息，分別是NextHop、HopCount、Pheromone、Selected-Probability 和SeqNo。NextHop 表示下一跳節點，HopCount表示跳數，Pheromone表示信息素值，Selected-Probability 表示根據信息素計算的本路徑被選擇的概率，SeqNo 表示路由條目序列號。

2.2 路由發現

路由發現采用按需方式向目的節點廣播前向螞蟻。當源節點與目的節點通信時，首先查找概率路由表，搜索路由表是否已有存儲的可以到達目的節點的路由鏈路。如果有，直接使用路由表存儲的路由；否則，源節點開始發起路由尋找請求。當源節點S 發起路由請求時，會向所有處于通信范圍的節點廣播前向螞蟻（Forward Ant）分組，鄰居節點收到消息建立反向路由進行反饋。

當目的節點D 收到來自不同鄰居節點發送過來的前向螞蟻后，依次向不同鄰居節點單播后向螞蟻（Backward Ant）分組。鄰居節點收到后向螞蟻分組后，再繼續往自己的鄰居節點廣播后向螞蟻分組，直到源節點接收到后向螞蟻分組并獲取路由鏈路的信息，路由發現過程完成。

2.3 信息素更新規則

首先，源節點通過路由發現后，完成了前向主路由的建立。建立完前向主路由的源節點S 開始更新每一條目的節點為D 的主路由的信息素。信息素的值主要由更新算子和揮發因子共同決定。信息素的更新公式如下。

信息素值的更新規則：

其中，i為當前節點；j為下一跳節點；τij(t+n)為信息素更新的值；ρ表示路徑上信息素的蒸發系數0＜ρ＜1；1-ρ表示信息素的持久性系數；Δτij表示本次迭代中當前節點i和下一跳節點j之間的信息素的增量。

傳統的信息素增量的更新規則為：

其中，Q為正常數；Lk表示第k只螞蟻在本次周游中所走過路徑的長度；Δτij表示本次迭代中當前節點i和下一跳節點j之間的信息素的增量；表示第k只螞蟻在本次迭代中留在邊ij上的信息素量。

改進的基于排序的信息素增量更新規則。提到的信息素增量更新規則是傳統蟻群算法的更新規則，下面提出一種改進的基于排序的信息素更新規則。基于排序的蟻群算法（Rank-Based Ant System）在 文 獻[5]最 早 是Bullnheimer、Hartl 和Strauss 等人提出的。在該算法中，每個螞蟻釋放的信息素按照它們不同的等級進行揮發，另外類似于精英蟻群算法，精英螞蟻在每次循環中釋放更多的信息素。在修改信息素路徑前，螞蟻按照它們的旅行長度進行排名（短的靠前），螞蟻釋放信息素的量要與螞蟻的排名相乘。在每次循環中，只有排名前w-1 位的螞蟻和精英螞蟻才允許在路徑上釋放信息素。已知的最優路徑給以最強的反饋，與系數w相乘；而排名第r位的螞蟻則乘以系數“w-r”（≥0）。

改進的基于排序的蟻群算法的信息素增量規則為：

其中，Lr表示排名為第r位的螞蟻的旅行路徑的長度；表示最優路徑的信息素量的值。

2.4 改進的蟻群算法路由選擇

蟻群算法中螞蟻每次選擇下一跳節點，都會計算與其相連的每一條鏈路的合適度，用概率表示。螞蟻最后會選擇概率最大的鏈路[13-15]，概率值計算公式如式（6）所示。式（7）是啟發函數，表示兩個節點間的鏈路費用，費用包括兩個節點間的距離、信噪比和節點負載。

其中，S/N為信噪比；G為負載；Lij表示節點i和節點j之間的距離；Jk(i)={1，2，3，…，n}表示螞蟻k下一步允許選擇的城市集合；μij(t)是一個啟發式因子，表示螞蟻從節點i轉移到節點j的期望程度。在該協議里，啟發式因子由節點i和節點j之間距離的倒數、信道的信噪比以及下一跳節點j的負載程度大小共同決定。

2.5 路由維護

路由維護中采用HELLO 消息監測活動路由中當前節點到達下一跳節點的鏈路狀態。Fortified Ant協議設計了一種路由維護的方法，分別從啟用備份路徑、本地路由恢復和源節點路由重建3 個方面實現這個方法[16-20]。

（1）啟用備份路徑：當中間節點i檢測到與下一跳節點n鏈路斷裂時，如果此時節點i緩存有到達目的節點d的備份路徑時，直接刪除到達目的節點d的失效路由，并且把節點i緩存的可到達目的節點d的備份路徑轉換為主路由。

（2）本地路由恢復：如果節點i距離目的節點d更近，則緩存來自源節點s的數據分組，嘗試進行本地修復。

（3）源節點路由重建：如果節點i距離目的節點d比較遠，則丟棄數據分組，并刪除到下一跳節點n的失效主路由，然后向鄰居節點廣播包含目的節點和主路由的序列號的錯誤消息分組。

3 實驗與結果

為了檢測Fortified Ant 協議的性能，本文使用網絡仿真軟件NS2 對該算法協議進行仿真實驗，并與基本蟻群算法（Ant Colony Optimization，ACO）、動態源路由協議（Dynamic Source Routing，DSR）和無線自組網按需平面距離向量路由協議（Ad-hoc On-Demand Distance Vector，AODV）發現算法進行比較。

3.1 仿真內容

3.1.1 路由尋優時間

路由尋優時間定義為從源節點發起信息傳輸請求，到源、目的節點間的傳輸路由建立過程中所耗費的時間[21-22]。Fortified Ant 協議理論上具有更快的路由尋優速度，本次仿真擬把Fortified Ant 協議的路由尋優花費的時間導出，與ACO 算法和DSR 協議作對比，觀察新路由協議是否有更快的尋優速度。

3.1.2 平均鏈路時延

平均鏈路時延定義為整個Mesh 網所有傳輸鏈路的平均時延值。Fortified Ant 協議理論上具有全局優化效果，可以有效避免尋優鏈路集中在局部最優。本次仿真把Fortified Ant 協議尋優鏈路的鏈路時延導出，與傳統的ACO 算法和DSR 協議作對比，觀察新路由協議是否可以有效縮短Mesh 網絡中的鏈路時延。

3.1.3 傳輸成功率

無線Mesh 網在消息傳輸過程中，會因為網絡擁塞或者環境干擾出現丟包的情況。信息丟包則視為傳輸失敗，需要源節點重新發起路由。所以，傳輸成功率是一個測試新算法性能的重要指標。Fortified Ant 協議引入多徑傳輸，理論上可以減少傳輸的丟包率，增加傳輸成功率，所以本次仿真把Fortified Ant 協議的傳輸成功率導出，與ACO 算法和AODV 協議作對比，觀察新路由協議的優化效果。

3.2 仿真環境設置

仿真環境參數設置，如表1 所示。

表1 仿真環境參數表

3.3 結果分析

圖3 表示的是3 種協議的源節點、目的節點鏈路的建立時間和區域內節點個數的關系圖。可見，隨著節點數的增加，3 種協議的鏈路建立時間都變短了。這是因為節點越多，可供給鏈路的節點變多，節點負載小，建立鏈路的速度相對較快。其次，提出的Fortified Ant 協議的仿真結果明顯優于傳統的蟻群算法（ACO）和動態源路由協議（DSR）。可見，在蟻群算法的基礎上加入排序能有效加快Mesh 網絡的路由尋優速度。

圖4 表示的是3 種協議的平均鏈路延時和網絡內鏈路的數量的關系圖。仿真是在區域內節點數量固定的情況下隨機生成不同數量的源節點和目的節點，增加Mesh 網絡內的鏈路數量，然后對比3 種協議仿真的鏈路時延情況。結果顯示，Fortified Ant協議的仿真效果較好。

圖3 3 種協議的鏈路建立時間對比

圖4 3 種協議的平均鏈路時延對比

最后，對3 種協議在不同的鏈路數量下的傳輸成功功率進行仿真，仿真結果如圖5 所示。

圖5 3 種協議的傳輸成功率對比

可以看到，具有多徑傳輸的協議的傳輸成功率明顯比單徑傳輸高，Fortified Ant 協議在本次的仿真中效果優良。可見，Fortified Ant 協議能比較好地適用于Mesh 網絡環境。

4 結語

本文主要研究了無線Mesh 骨干網的路由選擇問題，提出了一種改進的Fortified Ant 協議。新傳輸協議在蟻群算法的基礎上引入排序的方法優化，可以加快算法初期的尋優速度，再引入多徑路由機制，實現主備路由并行傳輸，同時根據實際情況，使用三種路由維護方法進行數據傳輸的維護。實驗結果表明，Fortified Ant 協議的鏈路尋找的速度明顯快于傳統的蟻群算法（ACO），同時平均端到端時延和傳輸成功率的效果明顯優于AODV 和DSR 兩個協議。