盧志恒

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

關(guān)鍵詞：蟻群算法；移動(dòng)自組網(wǎng)；AODV路由協(xié)議；動(dòng)態(tài)優(yōu)化

移動(dòng)無線自組網(wǎng)絡(luò)是一種自組織、快速配置而且無需固定設(shè)施的動(dòng)態(tài)網(wǎng)絡(luò)。當(dāng)移動(dòng)自組網(wǎng)拓?fù)渥兓瘯r(shí)，該算法可以迅速收斂，具有較低的計(jì)算量和較少的內(nèi)存需求，并具有自修復(fù)和斷開能力。此外，AODV還采用了結(jié)點(diǎn)序號(hào)的方法來解決移動(dòng)自組網(wǎng)中的循環(huán)和無限計(jì)數(shù)問題。然而，當(dāng)有效路由出現(xiàn)連接失效時(shí)，存在著對源節(jié)點(diǎn)進(jìn)行修補(bǔ)或局部修補(bǔ)選擇不當(dāng)?shù)膯栴}，這將導(dǎo)致整個(gè)移動(dòng)自組網(wǎng)性能的惡化。因此，本文擬研究一種基于移動(dòng)自組網(wǎng)的AODV路由協(xié)議，采集數(shù)據(jù)，設(shè)置動(dòng)態(tài)頻率門限，并通過實(shí)驗(yàn)驗(yàn)證了該算法的優(yōu)越性，提高了協(xié)議中分組的動(dòng)態(tài)交付率[1]。

一、蟻群算法

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

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

在此基礎(chǔ)上，采用局部弱化信息素作用，使未被走過的路徑有一定幾率被選中，從而避免陷入局部最優(yōu)；提高了全局的搜索能力，提高了全局信息素養(yǎng)更新速度；在確定局部最優(yōu)路徑上，提高信息素的作用和集中程度，從而加強(qiáng)正反饋?zhàn)饔?，提高收斂速度?/p>

（二）基于路徑選擇邏輯的改進(jìn)蟻群算法

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

（三）基于算法融合的改進(jìn)蟻群算法

由于蟻群算法并行性好、分布性能好等特點(diǎn)，蟻群算法更容易與其他算法相結(jié)合，通過與各種精確算法和啟發(fā)式算法的結(jié)合，形成一種新的算法，該算法可以將啟發(fā)式算法的強(qiáng)大全局尋優(yōu)能力與蟻群算法的正向反饋相結(jié)合，從而實(shí)現(xiàn)快速、準(zhǔn)確求解。

從算法層次上來說，它不但在算法層次上進(jìn)行了持續(xù)演化，而且在實(shí)踐中，它已經(jīng)被廣泛應(yīng)用于從生產(chǎn)生活中提煉出來的各種問題，例如：車輛路徑問題、圖像處理問題、移動(dòng)自組網(wǎng)路由問題、聚類問題等。

二、AODV路由協(xié)議工作過程

（一）AODV路由協(xié)議的路由發(fā)現(xiàn)

在AODV協(xié)議中，如果有一方想要向目的方發(fā)送一條信息，那么只需在此基礎(chǔ)上創(chuàng)建一條路徑。為尋找到達(dá)目標(biāo)點(diǎn)的路徑，它廣播一個(gè)路由請求信息RREQ到鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)又將消息轉(zhuǎn)發(fā)給下一鄰近結(jié)點(diǎn)，直至到達(dá)目標(biāo)點(diǎn)或有一條有效路徑到達(dá)目標(biāo)點(diǎn)。同時(shí)，接收RREQ的中間節(jié)點(diǎn)按照RREQ協(xié)議中提供的信息，創(chuàng)建一條新路徑——即“反向路由”。在此基礎(chǔ)上，提出了一種基于RREQ協(xié)議的逆向路由機(jī)制[2]。在到達(dá)目標(biāo)節(jié)點(diǎn)或者有一條有效路徑的情況下，節(jié)點(diǎn)會(huì)向源節(jié)點(diǎn)發(fā)送一條路由應(yīng)答消息，并在給定的方向上向源節(jié)點(diǎn)發(fā)送消息。在傳送過程中，收到RREP的節(jié)點(diǎn)會(huì)生成一條新路徑，并將其加入“正向路由”路由表。前向路由協(xié)議的目的節(jié)點(diǎn)是RREP的來源節(jié)點(diǎn)，下一節(jié)點(diǎn)將RREP發(fā)送給它的鄰居節(jié)點(diǎn)。

（二）AODV路由保持過程

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

當(dāng)有效路徑出現(xiàn)故障時(shí)，AODV協(xié)議提供了局部修補(bǔ)和源端重構(gòu)兩種方法。當(dāng)斷開鏈的前一節(jié)點(diǎn)處于MAX_REPAIR_TTL跳數(shù)范圍內(nèi)時(shí)，它將啟動(dòng)局部恢復(fù)；局部修復(fù)是上一節(jié)點(diǎn)啟動(dòng)路由發(fā)現(xiàn)，并通過對目標(biāo)節(jié)點(diǎn)的序號(hào)添加1來對鏈路進(jìn)行修復(fù)；啟動(dòng)該修補(bǔ)程序的節(jié)點(diǎn)會(huì)等待一個(gè)RREP循環(huán)以獲取RREQ的訪問權(quán)限。當(dāng)斷鏈的前一節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離超過MAX_REPAIR_TTL時(shí)，首先對其進(jìn)行恢復(fù)，即在中斷鏈附近的前一節(jié)點(diǎn)發(fā)出一條RERR信息，源方在收到RERR消息后，發(fā)起一條路由查找，源方將其序列號(hào)加上1，然后向目標(biāo)節(jié)點(diǎn)發(fā)送RREQ。

（三）AODV路由協(xié)議路由修復(fù)過程的缺陷

在圖1中結(jié)點(diǎn)6和結(jié)點(diǎn)7之間的鏈路被切斷之后，目的結(jié)點(diǎn)D將從源節(jié)點(diǎn)S遷移到新的結(jié)點(diǎn)，這個(gè)時(shí)候，結(jié)點(diǎn)6開始本地修補(bǔ)，使整個(gè)防火網(wǎng)絡(luò)的性能下降。因此，使用源節(jié)點(diǎn)來進(jìn)行修補(bǔ)，最為合理[3]。

若在結(jié)點(diǎn)3與結(jié)點(diǎn)4之間斷開連接，則如在圖2中所示，目標(biāo)結(jié)點(diǎn)D移至離源節(jié)點(diǎn)近數(shù)個(gè)跳點(diǎn)的結(jié)點(diǎn)3的位置；在這種情況下，如果在源節(jié)點(diǎn)上啟動(dòng)重構(gòu)路由，則會(huì)使整個(gè)移動(dòng)自組網(wǎng)的性能降低。這種情況下，還是使用局部節(jié)點(diǎn)來進(jìn)行修復(fù)更加合理[4]。

三、移動(dòng)自組網(wǎng)AODV路由協(xié)議動(dòng)態(tài)優(yōu)化

本文提出了一種新的基于蟻群算法的AODV路由協(xié)議。在進(jìn)行數(shù)據(jù)通信時(shí)，由于所處環(huán)境的影響，其所處的環(huán)境是不確定的。在此基礎(chǔ)上，提出了一種新的基于蟻群算法的AODV路由協(xié)議。

以起始點(diǎn)為路由起點(diǎn)，決定了目標(biāo)節(jié)點(diǎn)的具體位置，然后向目標(biāo)節(jié)點(diǎn)出發(fā)，在過程中避免遇到任何的干擾和障礙，生成與當(dāng)前環(huán)境相適應(yīng)的動(dòng)態(tài)路線。新路徑的出現(xiàn)將增加數(shù)據(jù)通信的傳輸距離，從而增加了數(shù)據(jù)通信的傳送時(shí)間。為在保證通信效率的前提下，實(shí)現(xiàn)最優(yōu)路徑，需重新制定避障準(zhǔn)則，當(dāng)通信路由遇到這種障礙時(shí)，無需再重新規(guī)劃其他路徑，使通信路徑最短[5]。

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

在公式（1）中，q是蟻群對障礙的辨識(shí)參數(shù)，f是不同結(jié)點(diǎn)的辨識(shí)函數(shù)，u、v是不同結(jié)點(diǎn)的辨識(shí)結(jié)果，ε是辨識(shí)出的關(guān)鍵性資訊的個(gè)數(shù)，σ是參加辨識(shí)規(guī)劃的結(jié)點(diǎn)資訊總數(shù)。在此基礎(chǔ)上，提出了一種基于蟻群算法的蟻群算法。通過改進(jìn)蟻群算法，實(shí)現(xiàn)了對避障策略的調(diào)整，并改善了對關(guān)鍵路線和優(yōu)先障礙的選擇能力。

根據(jù)蟻群對每個(gè)結(jié)點(diǎn)的信息素識(shí)別能力，將蟻群劃分為不同的等級(jí)，以增強(qiáng)蟻群對主要障礙物的吸引，從而增強(qiáng)蟻群對蟻群的吸引力。利用調(diào)高路由識(shí)別關(guān)鍵節(jié)點(diǎn)的靈敏度，縮小最優(yōu)路徑范圍，提高其識(shí)別最優(yōu)路徑的能力；基于該方法，將關(guān)鍵節(jié)點(diǎn)的信息素添加到原始信息素中，并與已知信息素濃度進(jìn)行融合，獲得各節(jié)點(diǎn)間的濃度差[6]。

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

公式（3）中，L表示得到的路線結(jié)果并且Lij是最初計(jì)劃的參考路線。通過分析，得出了在給定的條件下，得到的運(yùn)動(dòng)軌跡是最優(yōu)的，反之，如果不滿足，則不是最優(yōu)的。

以此能夠得到更加科學(xué)合理的路由傳輸路徑，實(shí)現(xiàn)了移動(dòng)路由協(xié)議動(dòng)態(tài)的優(yōu)化。

四、實(shí)驗(yàn)研究

利用Matlab作為試驗(yàn)軟件，分析了火災(zāi)撲救過程中的節(jié)點(diǎn)識(shí)別率、節(jié)點(diǎn)之間的平均傳輸時(shí)間、傳輸率和丟包率。以NS2為例，在550m×550m的防火網(wǎng)絡(luò)結(jié)構(gòu)中，選取20個(gè)節(jié)點(diǎn)，以10m/s的最大運(yùn)動(dòng)速度10m/s進(jìn)行仿真。

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

蟻群算法是一種最優(yōu)路徑規(guī)劃方法，其平均延遲為0.3—0.45秒，而常規(guī)算法的延遲大于0.7秒。這是由于本論文所提出的方法可以在多個(gè)任務(wù)之間實(shí)現(xiàn)最優(yōu)的傳送線，減少移動(dòng)自組網(wǎng)擁塞，減少節(jié)點(diǎn)負(fù)荷，加快分組的傳送速率。

在相同的移動(dòng)自組網(wǎng)環(huán)境中，監(jiān)控并分析了在不同傳輸速率情況下節(jié)點(diǎn)的報(bào)文接收率。隨著數(shù)據(jù)傳輸速率的提升和移動(dòng)自組網(wǎng)擁塞的加劇，傳統(tǒng)通信模式下路由拓?fù)浣Y(jié)構(gòu)的開銷增大，對移動(dòng)自組網(wǎng)拓?fù)浣Y(jié)構(gòu)的需求也隨之增大，從而加劇了通信系統(tǒng)的不穩(wěn)定性，極大地提升了通信的失敗率。本文提出一種新的基于蟻群算法的無線傳感器移動(dòng)自組網(wǎng)傳輸路徑優(yōu)化方案，減少移動(dòng)自組網(wǎng)阻塞率，保證移動(dòng)自組網(wǎng)拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性，保證移動(dòng)自組網(wǎng)節(jié)點(diǎn)的動(dòng)態(tài)變化，提高移動(dòng)自組網(wǎng)的接收成功率，達(dá)到最理想的移動(dòng)自組網(wǎng)傳輸效果。

結(jié)語

采用蟻群算法對AODV路由進(jìn)行了優(yōu)化，使其能夠有效地完成通信傳輸任務(wù)，使傳輸通道更平滑、更穩(wěn)定、數(shù)據(jù)傳輸時(shí)間更短，并獲得了較快的速度。另外，與傳統(tǒng)方式相比，移動(dòng)自組網(wǎng)擁塞程度得到緩解，通信環(huán)境更平穩(wěn)，節(jié)點(diǎn)變化率更低，從而顯著提高了信息數(shù)據(jù)的收發(fā)成功率。

參考文獻(xiàn)

[1]劉之濱，趙欣然.基于蟻群算法的移動(dòng)自組網(wǎng)AODV路由協(xié)議動(dòng)態(tài)優(yōu)化[J].電子設(shè)計(jì)工程，2022，30（02）：5.

[2]李原洲.基于動(dòng)態(tài)模糊蟻群算法的AODV路由協(xié)議改進(jìn)策略[D].杭州電子科技大學(xué)，2023.

[3]戴建輝.移動(dòng)自組網(wǎng)中基于鏈路連接度的蟻群算法路由協(xié)議[D].華中科技大學(xué)，2023.

[4]史釵.基于螞蟻算法的移動(dòng)自組網(wǎng)組播路由研究[D].燕山大學(xué)，2006.

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

[6]孫立山，張曉軍.一種基于螞蟻算法的移動(dòng)自組網(wǎng)節(jié)能路由算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2006，38（01）：3.

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