基于蟻群算法的移動自組網(wǎng)AODV路由協(xié)議動態(tài)優(yōu)化研究

摘要：現(xiàn)有的AODV路由協(xié)議優(yōu)化研究大多采用高延遲方式。本文對AODV路由協(xié)議進行動態(tài)優(yōu)化，并采用蟻群算法對其進行優(yōu)化。通過對路徑規(guī)劃中的避障規(guī)則及關鍵節(jié)點的敏感度進行修正，增加關鍵路徑上的信息素含量，設定信息素水平分區(qū)，進而對通信傳輸最優(yōu)路徑的辨識與規(guī)劃進行優(yōu)化。利用蟻群算法，將每個結(jié)點的信息素辨識結(jié)果與蟻群算法相結(jié)合，求得最佳傳播路徑。試驗表明，經(jīng)過優(yōu)化的路由通信數(shù)據(jù)傳輸平均時延維持在0.3—0.45秒之間，可以有效緩解移動自組網(wǎng)擁塞狀況，并且路徑節(jié)點的變化也逐漸平穩(wěn)，總體工作效率與性能得到了顯著提升。關鍵詞：蟻群算法；移動自組網(wǎng)；AODV路由協(xié)議；動態(tài)優(yōu)化移動無線自組網(wǎng)絡是一種自組織、快速配置而且無需固定設施的動態(tài)網(wǎng)絡。當移動自組網(wǎng)拓撲變化時，該算法可以迅速收斂，具有較低的計算量和較少的內(nèi)存需求，并具有自修復和斷開能力。此外，AODV還采用了結(jié)點序號的方法來解決移動自組網(wǎng)中的循環(huán)和無限計數(shù)問題。然而，當有效路由出現(xiàn)連接失效時，存在著對源節(jié)點進行修補或局部修補選擇不當?shù)膯栴}，這將導致整個移動自組網(wǎng)性能的惡化。因此，本文擬研究一種基于移動自組網(wǎng)的AODV路由協(xié)議，采集數(shù)據(jù)，設置動態(tài)頻率門限，并通過實驗驗證了該算法的優(yōu)越性，提高了協(xié)議中分組的動態(tài)交付率[1]。一、蟻群算法在不斷研究探討中，學者們根據(jù)蟻群“信息素”的變化規(guī)律，將其劃分為三種不同類型的蟻群算法。循環(huán)模型（cycle）：每只蟻群可釋放的信息素總量是恒定的。密度模型（denseness）：當蟻群通過一條通路后，不管這條通路有多長，它們都會釋放出同樣的信息素。數(shù)量模型（quantity）：每只蟻群在同一條路徑上釋放的信息素濃度均相同。在這三種模式的持續(xù)試驗和實際運用中，以其更具邏輯性和合理性而成為三種模式中的最佳模式。在接下來的研究中，很多學者通過引入各種算法和技術來對蟻群算法進行改進，主要有三種改進方法，分別是根據(jù)信息素的更新方式、基于路徑選擇邏輯的方法以及將其他算法與蟻群算法相結(jié)合，從而得到了各種改進算法。（一）基于信息素局部更新方式的改進蟻群算法在此基礎上，采用局部弱化信息素作用，使未被走過的路徑有一定幾率被選中，從而避免陷入局部最優(yōu)；提高了全局的搜索能力，提高了全局信息素養(yǎng)更新速度；在確定局部最優(yōu)路徑上，提高信息素的作用和集中程度，從而加強正反饋作用，提高收斂速度。（二）基于路徑選擇邏輯的改進蟻群算法采用一種基于遺傳算法的算法，對蟻群算法進行了改進，使得蟻群算法能夠在最短時間內(nèi)得到全部的可行解；為了提高算法的收斂效率，同時保證路徑的合理性，采用了一種基于遺傳算法的蟻群算法。（三）基于算法融合的改進蟻群算法由于蟻群算法并行性好、分布性能好等特點，蟻群算法更容易與其他算法相結(jié)合，通過與各種精確算法和啟發(fā)式算法的結(jié)合，形成一種新的算法，該算法可以將啟發(fā)式算法的強大全局尋優(yōu)能力與蟻群算法的正向反饋相結(jié)合，從而實現(xiàn)快速、準確求解。從算法層次上來說，它不但在算法層次上進行了持續(xù)演化，而且在實踐中，它已經(jīng)被廣泛應用于從生產(chǎn)生活中提煉出來的各種問題，例如：車輛路徑問題、圖像處理問題、移動自組網(wǎng)路由問題、聚類問題等。二、AODV路由協(xié)議工作過程（一）AODV路由協(xié)議的路由發(fā)現(xiàn)在AODV協(xié)議中，如果有一方想要向目的方發(fā)送一條信息，那么只需在此基礎上創(chuàng)建一條路徑。為尋找到達目標點的路徑，它廣播一個路由請求信息RREQ到鄰居節(jié)點，鄰居節(jié)點又將消息轉(zhuǎn)發(fā)給下一鄰近結(jié)點，直至到達目標點或有一條有效路徑到達目標點。同時，接收RREQ的中間節(jié)點按照RREQ協(xié)議中提供的信息，創(chuàng)建一條新路徑——即“反向路由”。在此基礎上，提出了一種基于RREQ協(xié)議的逆向路由機制[2]。在到達目標節(jié)點或者有一條有效路徑的情況下，節(jié)點會向源節(jié)點發(fā)送一條路由應答消息，并在給定的方向上向源節(jié)點發(fā)送消息。在傳送過程中，收到RREP的節(jié)點會生成一條新路徑，并將其加入“正向路由”路由表。前向路由協(xié)議的目的節(jié)點是RREP的來源節(jié)點，下一節(jié)點將RREP發(fā)送給它的鄰居節(jié)點。（二）AODV路由保持過程在路由形成之后，為了維持路由，各節(jié)點定期通過廣播向鄰居發(fā)送Hello消息，并將消息限制在發(fā)送節(jié)點與鄰居節(jié)點之間。接收到Hello信息的節(jié)點將創(chuàng)建或者更新到發(fā)送節(jié)點的路由。在AODV中，無論何時，當一個節(jié)點接收到一個控制報文時，其含義都相當于一個顯式Hello消息。因此，無論何時，節(jié)點都能保持有效的連通性。當一個節(jié)點發(fā)現(xiàn)一個路徑不可用，就會在路由表中設定這個路徑表的條目為無效，然后過一段時間再刪除。當有效路徑出現(xiàn)故障時，AODV協(xié)議提供了局部修補和源端重構(gòu)兩種方法。當斷開鏈的前一節(jié)點處于MAX_REPAIR_TTL跳數(shù)范圍內(nèi)時，它將啟動局部恢復；局部修復是上一節(jié)點啟動路由發(fā)現(xiàn)，并通過對目標節(jié)點的序號添加1來對鏈路進行修復；啟動該修補程序的節(jié)點會等待一個RREP循環(huán)以獲取RREQ的訪問權(quán)限。當斷鏈的前一節(jié)點與目標節(jié)點之間的距離超過MAX_REPAIR_TTL時，首先對其進行恢復，即在中斷鏈附近的前一節(jié)點發(fā)出一條RERR信息，源方在收到RERR消息后，發(fā)起一條路由查找，源方將其序列號加上1，然后向目標節(jié)點發(fā)送RREQ。（三）AODV路由協(xié)議路由修復過程的缺陷在圖1中結(jié)點6和結(jié)點7之間的鏈路被切斷之后，目的結(jié)點D將從源節(jié)點S遷移到新的結(jié)點，這個時候，結(jié)點6開始本地修補，使整個防火網(wǎng)絡的性能下降。因此，使用源節(jié)點來進行修補，最為合理[3]。若在結(jié)點3與結(jié)點4之間斷開連接，則如在圖2中所示，目標結(jié)點D移至離源節(jié)點近數(shù)個跳點的結(jié)點3的位置；在這種情況下，如果在源節(jié)點上啟動重構(gòu)路由，則會使整個移動自組網(wǎng)的性能降低。這種情況下，還是使用局部節(jié)點來進行修復更加合理[4]。三、移動自組網(wǎng)AODV路由協(xié)議動態(tài)優(yōu)化本文提出了一種新的基于蟻群算法的AODV路由協(xié)議。在進行數(shù)據(jù)通信時，由于所處環(huán)境的影響，其所處的環(huán)境是不確定的。在此基礎上，提出了一種新的基于蟻群算法的AODV路由協(xié)議。以起始點為路由起點，決定了目標節(jié)點的具體位置，然后向目標節(jié)點出發(fā)，在過程中避免遇到任何的干擾和障礙，生成與當前環(huán)境相適應的動態(tài)路線。新路徑的出現(xiàn)將增加數(shù)據(jù)通信的傳輸距離，從而增加了數(shù)據(jù)通信的傳送時間。為在保證通信效率的前提下，實現(xiàn)最優(yōu)路徑，需重新制定避障準則，當通信路由遇到這種障礙時，無需再重新規(guī)劃其他路徑，使通信路徑最短[5]。將通信環(huán)境中存在的多條路徑結(jié)點和障礙物結(jié)點用蟻群算法表示，并將路徑結(jié)點的信息集成為：X=（x1，x2…xn），以集合的形式表達的障礙節(jié)點Y=（y1，y2…yn），給出了最優(yōu)的數(shù)據(jù)傳送路線和避障路線，a代表蟻群，D描述了蟻群所走過的路線，并能求出理想的最佳路線與實際的最佳路線，并對蟻群在各種障礙下的避讓狀況進行了分析：在公式（1）中，q是蟻群對障礙的辨識參數(shù)，f是不同結(jié)點的辨識函數(shù)，u、v是不同結(jié)點的辨識結(jié)果，ε是辨識出的關鍵性資訊的個數(shù)，σ是參加辨識規(guī)劃的結(jié)點資訊總數(shù)。在此基礎上，提出了一種基于蟻群算法的蟻群算法。通過改進蟻群算法，實現(xiàn)了對避障策略的調(diào)整，并改善了對關鍵路線和優(yōu)先障礙的選擇能力。根據(jù)蟻群對每個結(jié)點的信息素識別能力，將蟻群劃分為不同的等級，以增強蟻群對主要障礙物的吸引，從而增強蟻群對蟻群的吸引力。利用調(diào)高路由識別關鍵節(jié)點的靈敏度，縮小最優(yōu)路徑范圍，提高其識別最優(yōu)路徑的能力；基于該方法，將關鍵節(jié)點的信息素添加到原始信息素中，并與已知信息素濃度進行融合，獲得各節(jié)點間的濃度差[6]。（2）式中，Δk表示信息素濃度的差異，η表示信息素的分歧，a表示蟻群軌跡的錯誤范圍，h表示整個路徑的長度，Eij表示蟻群感受到的信息素總量。根據(jù)以上公式所算出的信息，對最優(yōu)路徑進行判定：公式（3）中，L表示得到的路線結(jié)果并且Lij是最初計劃的參考路線。通過分析，得出了在給定的條件下，得到的運動軌跡是最優(yōu)的，反之，如果不滿足，則不是最優(yōu)的。以此能夠得到更加科學合理的路由傳輸路徑，實現(xiàn)了移動路由協(xié)議動態(tài)的優(yōu)化。四、實驗研究利用Matlab作為試驗軟件，分析了火災撲救過程中的節(jié)點識別率、節(jié)點之間的平均傳輸時間、傳輸率和丟包率。以NS2為例，在550m×550m的防火網(wǎng)絡結(jié)構(gòu)中，選取20個節(jié)點，以10m/s的最大運動速度10m/s進行仿真。傳統(tǒng)路由通信中，當傳送資料相同時，移動自組網(wǎng)速率會影響從起始結(jié)點至該區(qū)域中各結(jié)點的傳送速率。在不同的傳輸路徑上，傳送節(jié)點之間的平均傳送時間是恒定的，而路由傳送的封包率與接收速率成反比，恒定的移動自組網(wǎng)速率下，增加了傳送速率，則會使該地區(qū)的移動自組網(wǎng)環(huán)境變得更加擁擠，對移動自組網(wǎng)資源的占用也會增加，此外，它還會給網(wǎng)絡中的節(jié)點帶來額外的負荷，從而降低了網(wǎng)絡的傳輸速度和效率[7]。蟻群算法是一種最優(yōu)路徑規(guī)劃方法，其平均延遲為0.3—0.45秒，而常規(guī)算法的延遲大于0.7秒。這是由于本論文所提出的方法可以在多個任務之間實現(xiàn)最優(yōu)的傳送線，減少移動自組網(wǎng)擁塞，減少節(jié)點負荷，加快分組的傳送速率。在相同的移動自組網(wǎng)環(huán)境中，監(jiān)控并分析了在不同傳輸速率情況下節(jié)點的報文接收率。隨著數(shù)據(jù)傳輸速率的提升和移動自組網(wǎng)擁塞的加劇，傳統(tǒng)通信模式下路由拓撲結(jié)構(gòu)的開銷增大，對移動自組網(wǎng)拓撲結(jié)構(gòu)的需求也隨之增大，從而加劇了通信系統(tǒng)的不穩(wěn)定性，極大地提升了通信的失敗率。本文提出一種新的基于蟻群算法的無線傳感器移動自組網(wǎng)傳輸路徑優(yōu)化