基于蟻群算法的移動自組網AODV路由協議動態優化研究

盧志恒

摘要：現有的AODV路由協議優化研究大多采用高延遲方式。本文對AODV路由協議進行動態優化，并采用蟻群算法對其進行優化。通過對路徑規劃中的避障規則及關鍵節點的敏感度進行修正，增加關鍵路徑上的信息素含量，設定信息素水平分區，進而對通信傳輸最優路徑的辨識與規劃進行優化。利用蟻群算法，將每個結點的信息素辨識結果與蟻群算法相結合，求得最佳傳播路徑。試驗表明，經過優化的路由通信數據傳輸平均時延維持在0.3—0.45秒之間，可以有效緩解移動自組網擁塞狀況，并且路徑節點的變化也逐漸平穩，總體工作效率與性能得到了顯著提升。

關鍵詞：蟻群算法；移動自組網；AODV路由協議；動態優化

移動無線自組網絡是一種自組織、快速配置而且無需固定設施的動態網絡。當移動自組網拓撲變化時，該算法可以迅速收斂，具有較低的計算量和較少的內存需求，并具有自修復和斷開能力。此外，AODV還采用了結點序號的方法來解決移動自組網中的循環和無限計數問題。然而，當有效路由出現連接失效時，存在著對源節點進行修補或局部修補選擇不當的問題，這將導致整個移動自組網性能的惡化。因此，本文擬研究一種基于移動自組網的AODV路由協議，采集數據，設置動態頻率門限，并通過實驗驗證了該算法的優越性，提高了協議中分組的動態交付率[1]。

一、蟻群算法

在不斷研究探討中，學者們根據蟻群“信息素”的變化規律，將其劃分為三種不同類型的蟻群算法。循環模型（cycle）：每只蟻群可釋放的信息素總量是恒定的。密度模型（denseness）：當蟻群通過一條通路后，不管這條通路有多長，它們都會釋放出同樣的信息素。數量模型（quantity）：每只蟻群在同一條路徑上釋放的信息素濃度均相同。在這三種模式的持續試驗和實際運用中，以其更具邏輯性和合理性而成為三種模式中的最佳模式。在接下來的研究中，很多學者通過引入各種算法和技術來對蟻群算法進行改進，主要有三種改進方法，分別是根據信息素的更新方式、基于路徑選擇邏輯的方法以及將其他算法與蟻群算法相結合，從而得到了各種改進算法。

（一）基于信息素局部更新方式的改進蟻群算法

在此基礎上，采用局部弱化信息素作用，使未被走過的路徑有一定幾率被選中，從而避免陷入局部最優；提高了全局的搜索能力，提高了全局信息素養更新速度；在確定局部最優路徑上，提高信息素的作用和集中程度，從而加強正反饋作用，提高收斂速度。

（二）基于路徑選擇邏輯的改進蟻群算法

采用一種基于遺傳算法的算法，對蟻群算法進行了改進，使得蟻群算法能夠在最短時間內得到全部的可行解；為了提高算法的收斂效率，同時保證路徑的合理性，采用了一種基于遺傳算法的蟻群算法。

（三）基于算法融合的改進蟻群算法

由于蟻群算法并行性好、分布性能好等特點，蟻群算法更容易與其他算法相結合，通過與各種精確算法和啟發式算法的結合，形成一種新的算法，該算法可以將啟發式算法的強大全局尋優能力與蟻群算法的正向反饋相結合，從而實現快速、準確求解。

從算法層次上來說，它不但在算法層次上進行了持續演化，而且在實踐中，它已經被廣泛應用于從生產生活中提煉出來的各種問題，例如：車輛路徑問題、圖像處理問題、移動自組網路由問題、聚類問題等。

二、AODV路由協議工作過程

（一）AODV路由協議的路由發現

在AODV協議中，如果有一方想要向目的方發送一條信息，那么只需在此基礎上創建一條路徑。為尋找到達目標點的路徑，它廣播一個路由請求信息RREQ到鄰居節點，鄰居節點又將消息轉發給下一鄰近結點，直至到達目標點或有一條有效路徑到達目標點。同時，接收RREQ的中間節點按照RREQ協議中提供的信息，創建一條新路徑——即“反向路由”。在此基礎上，提出了一種基于RREQ協議的逆向路由機制[2]。在到達目標節點或者有一條有效路徑的情況下，節點會向源節點發送一條路由應答消息，并在給定的方向上向源節點發送消息。在傳送過程中，收到RREP的節點會生成一條新路徑，并將其加入“正向路由”路由表。前向路由協議的目的節點是RREP的來源節點，下一節點將RREP發送給它的鄰居節點。

（二）AODV路由保持過程

在路由形成之后，為了維持路由，各節點定期通過廣播向鄰居發送Hello消息，并將消息限制在發送節點與鄰居節點之間。接收到Hello信息的節點將創建或者更新到發送節點的路由。在AODV中，無論何時，當一個節點接收到一個控制報文時，其含義都相當于一個顯式Hello消息。因此，無論何時，節點都能保持有效的連通性。當一個節點發現一個路徑不可用，就會在路由表中設定這個路徑表的條目為無效，然后過一段時間再刪除。

當有效路徑出現故障時，AODV協議提供了局部修補和源端重構兩種方法。當斷開鏈的前一節點處于MAX_REPAIR_TTL跳數范圍內時，它將啟動局部恢復；局部修復是上一節點啟動路由發現，并通過對目標節點的序號添加1來對鏈路進行修復；啟動該修補程序的節點會等待一個RREP循環以獲取RREQ的訪問權限。當斷鏈的前一節點與目標節點之間的距離超過MAX_REPAIR_TTL時，首先對其進行恢復，即在中斷鏈附近的前一節點發出一條RERR信息，源方在收到RERR消息后，發起一條路由查找，源方將其序列號加上1，然后向目標節點發送RREQ。

（三）AODV路由協議路由修復過程的缺陷

在圖1中結點6和結點7之間的鏈路被切斷之后，目的結點D將從源節點S遷移到新的結點，這個時候，結點6開始本地修補，使整個防火網絡的性能下降。因此，使用源節點來進行修補，最為合理[3]。

若在結點3與結點4之間斷開連接，則如在圖2中所示，目標結點D移至離源節點近數個跳點的結點3的位置；在這種情況下，如果在源節點上啟動重構路由，則會使整個移動自組網的性能降低。這種情況下，還是使用局部節點來進行修復更加合理[4]。

三、移動自組網AODV路由協議動態優化

本文提出了一種新的基于蟻群算法的AODV路由協議。在進行數據通信時，由于所處環境的影響，其所處的環境是不確定的。在此基礎上，提出了一種新的基于蟻群算法的AODV路由協議。

以起始點為路由起點，決定了目標節點的具體位置，然后向目標節點出發，在過程中避免遇到任何的干擾和障礙，生成與當前環境相適應的動態路線。新路徑的出現將增加數據通信的傳輸距離，從而增加了數據通信的傳送時間。為在保證通信效率的前提下，實現最優路徑，需重新制定避障準則，當通信路由遇到這種障礙時，無需再重新規劃其他路徑，使通信路徑最短[5]。

將通信環境中存在的多條路徑結點和障礙物結點用蟻群算法表示，并將路徑結點的信息集成為：X=（x1，x2…xn），以集合的形式表達的障礙節點Y=（y1，y2…yn），給出了最優的數據傳送路線和避障路線，a代表蟻群，D描述了蟻群所走過的路線，并能求出理想的最佳路線與實際的最佳路線，并對蟻群在各種障礙下的避讓狀況進行了分析：

在公式（1）中，q是蟻群對障礙的辨識參數，f是不同結點的辨識函數，u、v是不同結點的辨識結果，ε是辨識出的關鍵性資訊的個數，σ是參加辨識規劃的結點資訊總數。在此基礎上，提出了一種基于蟻群算法的蟻群算法。通過改進蟻群算法，實現了對避障策略的調整，并改善了對關鍵路線和優先障礙的選擇能力。

根據蟻群對每個結點的信息素識別能力，將蟻群劃分為不同的等級，以增強蟻群對主要障礙物的吸引，從而增強蟻群對蟻群的吸引力。利用調高路由識別關鍵節點的靈敏度，縮小最優路徑范圍，提高其識別最優路徑的能力；基于該方法，將關鍵節點的信息素添加到原始信息素中，并與已知信息素濃度進行融合，獲得各節點間的濃度差[6]。

（2）式中，Δk表示信息素濃度的差異，η表示信息素的分歧，a表示蟻群軌跡的錯誤范圍，h表示整個路徑的長度，Eij表示蟻群感受到的信息素總量。根據以上公式所算出的信息，對最優路徑進行判定：

公式（3）中，L表示得到的路線結果并且Lij是最初計劃的參考路線。通過分析，得出了在給定的條件下，得到的運動軌跡是最優的，反之，如果不滿足，則不是最優的。

以此能夠得到更加科學合理的路由傳輸路徑，實現了移動路由協議動態的優化。

四、實驗研究

利用Matlab作為試驗軟件，分析了火災撲救過程中的節點識別率、節點之間的平均傳輸時間、傳輸率和丟包率。以NS2為例，在550m×550m的防火網絡結構中，選取20個節點，以10m/s的最大運動速度10m/s進行仿真。

傳統路由通信中，當傳送資料相同時，移動自組網速率會影響從起始結點至該區域中各結點的傳送速率。在不同的傳輸路徑上，傳送節點之間的平均傳送時間是恒定的，而路由傳送的封包率與接收速率成反比，恒定的移動自組網速率下，增加了傳送速率，則會使該地區的移動自組網環境變得更加擁擠，對移動自組網資源的占用也會增加，此外，它還會給網絡中的節點帶來額外的負荷，從而降低了網絡的傳輸速度和效率[7]。

蟻群算法是一種最優路徑規劃方法，其平均延遲為0.3—0.45秒，而常規算法的延遲大于0.7秒。這是由于本論文所提出的方法可以在多個任務之間實現最優的傳送線，減少移動自組網擁塞，減少節點負荷，加快分組的傳送速率。

在相同的移動自組網環境中，監控并分析了在不同傳輸速率情況下節點的報文接收率。隨著數據傳輸速率的提升和移動自組網擁塞的加劇，傳統通信模式下路由拓撲結構的開銷增大，對移動自組網拓撲結構的需求也隨之增大，從而加劇了通信系統的不穩定性，極大地提升了通信的失敗率。本文提出一種新的基于蟻群算法的無線傳感器移動自組網傳輸路徑優化方案，減少移動自組網阻塞率，保證移動自組網拓撲結構的穩定性，保證移動自組網節點的動態變化，提高移動自組網的接收成功率，達到最理想的移動自組網傳輸效果。

結語

采用蟻群算法對AODV路由進行了優化，使其能夠有效地完成通信傳輸任務，使傳輸通道更平滑、更穩定、數據傳輸時間更短，并獲得了較快的速度。另外，與傳統方式相比，移動自組網擁塞程度得到緩解，通信環境更平穩，節點變化率更低，從而顯著提高了信息數據的收發成功率。

參考文獻

[1]劉之濱，趙欣然.基于蟻群算法的移動自組網AODV路由協議動態優化[J].電子設計工程，2022，30（02）：5.

[2]李原洲.基于動態模糊蟻群算法的AODV路由協議改進策略[D].杭州電子科技大學，2023.

[3]戴建輝.移動自組網中基于鏈路連接度的蟻群算法路由協議[D].華中科技大學，2023.

[4]史釵.基于螞蟻算法的移動自組網組播路由研究[D].燕山大學，2006.

[5]周德榮.基于蟻群算法改進的AODV路由協議研究[J].西南師范大學學報（自然科學版），2014（11）：75-80.

[6]孫立山，張曉軍.一種基于螞蟻算法的移動自組網節能路由算法[J].哈爾濱工業大學學報，2006，38（01）：3.

[7]孔含秋.基于蟻群算法的AdHoc分簇路由協議的研究與優化[D].南昌大學，2014.