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

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