李杰

（三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，南京210012）

0 引言

AODV（Ad hoc On-Demand Distance Vector Rout?ing）協(xié)議通過(guò)洪泛的方法，使得設(shè)備能夠讓很多的路由達(dá)到目的地，而且不需要設(shè)備在沒(méi)有相互通訊時(shí)，協(xié)議可以自行維護(hù)這些路由。當(dāng)這些路由因故斷開(kāi)時(shí)，可以快速做出響應(yīng)，為完善拓?fù)浣Y(jié)果做出及時(shí)應(yīng)對(duì)。而且這個(gè)協(xié)議的頻寬使用量有限，對(duì)資源占有較小。但是因?yàn)檫@種及時(shí)響應(yīng)的措施也會(huì)出現(xiàn)附帶的問(wèn)題，雖然這種路由協(xié)議響應(yīng)快，但是為了找到可達(dá)路由，會(huì)使整個(gè)網(wǎng)絡(luò)的時(shí)延和路由開(kāi)銷(xiāo)在這個(gè)階段大大增加。在這些問(wèn)題上一直有大量研究人員進(jìn)行研究。

從古到今，人類(lèi)一直通過(guò)模仿自然界動(dòng)物的行為特征來(lái)，認(rèn)識(shí)自然科學(xué)并使用各種原理來(lái)發(fā)展人類(lèi)自身科技。在算法領(lǐng)域中有一種新的仿生優(yōu)化算法進(jìn)入人們的視野——蟻群算法[1]。1991年，Marco Dorigo等人提出一種仿生算法，比利時(shí)、意大利、德國(guó)這三個(gè)國(guó)家是蟻群算法的主要研究國(guó)家，國(guó)內(nèi)有上海、北京等幾個(gè)研究所和大學(xué)對(duì)蟻群算法展開(kāi)過(guò)研究。在改良AODV路由協(xié)議上可以鑒戒蟻群算法。蟻群算法采取正反饋機(jī)制的分布式啟發(fā)式算法，具有適用于移動(dòng)場(chǎng)景、自發(fā)建立、自動(dòng)布置等特性，也被成為增強(qiáng)式學(xué)習(xí)系統(tǒng)，與AODV路由協(xié)議相適應(yīng)[1]。

1 全面深入AODV

（1）AODV協(xié)議綜述

AODV協(xié)議的目標(biāo)是能夠在未知環(huán)境中也能建立的，并且自身能夠隨拓?fù)涞淖兓赃m應(yīng)的網(wǎng)絡(luò)。該協(xié)議以路徑長(zhǎng)度為取舍路由的標(biāo)準(zhǔn)，每個(gè)節(jié)點(diǎn)僅需對(duì)自己通往的最短路徑節(jié)點(diǎn)進(jìn)行維護(hù)，這個(gè)路徑上的節(jié)點(diǎn)不只是線(xiàn)性的而是一個(gè)范圍內(nèi)所有的節(jié)點(diǎn)。取最短路徑節(jié)點(diǎn)的方法，使得該協(xié)議對(duì)于網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)有著靈活的自適應(yīng)性。該協(xié)議的相關(guān)操作使得變化時(shí)的收斂性很好，拓?fù)浒l(fā)生改變時(shí)，發(fā)生變化的節(jié)點(diǎn)會(huì)給就近節(jié)點(diǎn)發(fā)送通知信息包。附近節(jié)點(diǎn)就會(huì)更新自身路由表，剔除無(wú)效路由[4]。

AODV協(xié)議使用seq號(hào)來(lái)維護(hù)和更新路由信息表。目的節(jié)點(diǎn)創(chuàng)建seq號(hào)，在它給附近節(jié)點(diǎn)發(fā)送路由信息包時(shí)，把這個(gè)seq號(hào)作為路由中一部分發(fā)送出去，發(fā)送給所有給目的節(jié)點(diǎn)發(fā)送請(qǐng)求的節(jié)點(diǎn)。這個(gè)seq號(hào)是嵌入在路由信息表中不需要另外操作。該協(xié)議對(duì)路由更新也使用這個(gè)seq號(hào)，更新路由信息表時(shí)，檢查收到的路由信息包，比較路由表中的當(dāng)前seq號(hào)是否是最大值。當(dāng)成為最大值之后進(jìn)行更新。

無(wú)論是在未知環(huán)境中的網(wǎng)絡(luò)構(gòu)建，還是因拓?fù)浒l(fā)生變化而需要更新路由信息表，其本質(zhì)都是需要改動(dòng)路由表中的路由表項(xiàng)。那么就需要去了解路由表項(xiàng)的具體內(nèi)容以及作用。AODV路由表項(xiàng)如表1所示。

表1 AODV路由表項(xiàng)

（2）AODV操作

在使用AODV協(xié)議通信時(shí)，節(jié)點(diǎn)會(huì)生成路由請(qǐng)求、路由應(yīng)答和路由錯(cuò)誤三種報(bào)文信息。為了恰當(dāng)?shù)貙?duì)三種信息進(jìn)行發(fā)送、接收，在路由表項(xiàng)中設(shè)定狀態(tài)信息。

①seq號(hào)管理

為了恰當(dāng)?shù)貙?duì)各種報(bào)文進(jìn)行發(fā)送和接收，在路由信息表中維護(hù)一個(gè)seq號(hào)。這個(gè)seq號(hào)就是上述的目標(biāo)seq號(hào)，即節(jié)點(diǎn)路由信息表中維護(hù)的最新的目的節(jié)點(diǎn)IP和其他信息。定義了這個(gè)seq號(hào)，當(dāng)一個(gè)節(jié)點(diǎn)收到一系列新的報(bào)文，首先判斷該報(bào)文是否跟請(qǐng)求消息、接收消息和錯(cuò)誤消息的seq號(hào)有關(guān)，反之就會(huì)拋棄該報(bào)文消息。然后再檢查這些消息中的seq號(hào)是否是最新的，如果是就更新路由表項(xiàng)中的seq號(hào)，否則也舍棄掉該報(bào)文。增加目標(biāo)節(jié)點(diǎn)自身的seq號(hào)也有特定的場(chǎng)景下的。一個(gè)節(jié)點(diǎn)在向其他節(jié)點(diǎn)發(fā)起請(qǐng)求之前需要對(duì)自身的seq號(hào)進(jìn)行加法操作，這相當(dāng)是對(duì)當(dāng)前版本號(hào)的操作，給當(dāng)前操作規(guī)定一個(gè)版本號(hào)，如果響應(yīng)者發(fā)回路由，那么就會(huì)核對(duì)版本號(hào)，版本號(hào)對(duì)不上就不會(huì)進(jìn)行更新操作。所以AODV協(xié)議中有要求，為每一個(gè)節(jié)點(diǎn)新建和更新目標(biāo)seq號(hào)。并且目標(biāo)節(jié)點(diǎn)在對(duì)其他節(jié)點(diǎn)發(fā)來(lái)的請(qǐng)求報(bào)文進(jìn)行答復(fù)時(shí)，目標(biāo)節(jié)點(diǎn)也必須先更新自身的seq號(hào)，而且更新的seq號(hào)要保證是最新的版本號(hào)[4]。

②路由表項(xiàng)和先驅(qū)列表

當(dāng)節(jié)點(diǎn)從鄰居接收到AODV控制消息并創(chuàng)建和更新特定目標(biāo)節(jié)點(diǎn)和目標(biāo)子網(wǎng)的路由表?xiàng)l目時(shí)，它將檢查該節(jié)點(diǎn)是否在表中，該條目對(duì)應(yīng)于此目的地。如果沒(méi)有關(guān)聯(lián)的條目，將創(chuàng)建一個(gè)新條目。可以從AODV控制消息中提取seq號(hào)，也可以在路由表?xiàng)l目中的“seq號(hào)有效”位置標(biāo)記為“無(wú)效”。

在維護(hù)和更新路由表時(shí)，可以使用控制消息。其中的有用路由超時(shí)字段，是用來(lái)更新路由表中有用時(shí)間字段的參考字段，更新規(guī)則是：路由轉(zhuǎn)發(fā)時(shí)，請(qǐng)求路由、響應(yīng)路由的節(jié)點(diǎn)的有用時(shí)間需要參考控制消息中的有用路由超時(shí)時(shí)間，新的值下限是當(dāng)前時(shí)間與有用路由超時(shí)時(shí)間之和。因?yàn)榘l(fā)起請(qǐng)求節(jié)點(diǎn)和回復(fù)請(qǐng)求節(jié)點(diǎn)是相互對(duì)應(yīng)的，那么請(qǐng)求節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)發(fā)送請(qǐng)求報(bào)文中的目的地址，就是目的節(jié)點(diǎn)也就是回復(fù)節(jié)點(diǎn)中的源地址是相同的，那么這樣對(duì)應(yīng)的兩條路由就是對(duì)應(yīng)存在的，請(qǐng)求節(jié)點(diǎn)中的這條路由如果刪除了，意味著該條路由已失效，那么目標(biāo)節(jié)點(diǎn)路由表中對(duì)應(yīng)路由也應(yīng)該刪除，所以這兩條路由的有效時(shí)間是相同的。對(duì)其中一條路由進(jìn)行更新時(shí)另外一條路由也需要更新。

對(duì)于每條有效路由，每個(gè)節(jié)點(diǎn)會(huì)維護(hù)一張先驅(qū)表，所謂先驅(qū)表就是存放那些發(fā)送請(qǐng)求報(bào)文到本節(jié)點(diǎn)的節(jié)點(diǎn)。這些先驅(qū)節(jié)點(diǎn)可能會(huì)使用本地路由轉(zhuǎn)發(fā)數(shù)據(jù)。先驅(qū)表的作用就是防止節(jié)點(diǎn)斷開(kāi)導(dǎo)致的重建路由的開(kāi)銷(xiāo)問(wèn)題。本節(jié)點(diǎn)檢測(cè)到下一跳節(jié)點(diǎn)與自身節(jié)點(diǎn)失效，本節(jié)點(diǎn)就會(huì)通知這些先驅(qū)節(jié)點(diǎn)，下一跳路由已失效[5]。

③處理和轉(zhuǎn)發(fā)路由請(qǐng)求

節(jié)點(diǎn)接收到周?chē)?jié)點(diǎn)發(fā)送的請(qǐng)求消息后，首先檢查在路徑發(fā)現(xiàn)周期內(nèi)是否已存在源IP和請(qǐng)求ID與該請(qǐng)求信息匹配的消息，存在該消息就會(huì)丟棄，否則就會(huì)檢查本地路由表中是否存在通往該節(jié)點(diǎn)的可達(dá)路徑，不存在則新建通往發(fā)送節(jié)點(diǎn)的路由表項(xiàng)，如果存在則只是將本地seq號(hào)進(jìn)行加一操作。

請(qǐng)求消息的處理不僅僅是對(duì)路由信息表中的seq號(hào)進(jìn)行更新或是簡(jiǎn)單轉(zhuǎn)發(fā)，還需要更新跳數(shù)、源seq號(hào)，創(chuàng)建反向路由，匹配源IP地址。而且在創(chuàng)建了反向路由后，仍然需要比較seq號(hào)之后再更新路由表項(xiàng)，更新seq號(hào)合法標(biāo)識(shí)，更新反向路由表中的跳數(shù)和路由生命周期。詳細(xì)而言，若是節(jié)點(diǎn)領(lǐng)受到四圍節(jié)點(diǎn)發(fā)送的請(qǐng)求消息，當(dāng)請(qǐng)求消息在該節(jié)點(diǎn)以前沒(méi)有存在過(guò)，就先將領(lǐng)受到的請(qǐng)求消息中的跳數(shù)加一，標(biāo)識(shí)請(qǐng)求消息抵達(dá)了該節(jié)點(diǎn)。更新完跳數(shù)之后，需要去創(chuàng)建一條反向路由。反向路由的目的節(jié)點(diǎn)就是接收的請(qǐng)求消息中源IP，這條路由中的seq號(hào)使用請(qǐng)求消息中的源seq號(hào)加一。那么使用這條反向路由發(fā)送的消息相當(dāng)于是對(duì)發(fā)送請(qǐng)求消息所在節(jié)點(diǎn)的回復(fù)消息[5]。創(chuàng)建和更新反向路由時(shí)，需要更新路由表項(xiàng)、更新seq號(hào)合法標(biāo)識(shí)等。

④路由錯(cuò)誤處理

當(dāng)路由發(fā)生錯(cuò)誤或者節(jié)點(diǎn)之間的連接發(fā)生中斷時(shí)，需要以下步驟進(jìn)行處理：

第一步，首先需要把本地路由進(jìn)行無(wú)效化處理，具體是將本地路由信息表中的有效超時(shí)字段進(jìn)行更新，還有每一個(gè)節(jié)點(diǎn)維護(hù)的先驅(qū)表也進(jìn)行更新，通過(guò)先驅(qū)表向周?chē)?jié)點(diǎn)通知下一跳路由已失效。第二步，通過(guò)路由表枚舉出沒(méi)有通過(guò)錯(cuò)誤路由的路徑。第三步，檢查出錯(cuò)誤路由影響哪些鄰居節(jié)點(diǎn)抵達(dá)目的節(jié)點(diǎn)。第四步，本節(jié)點(diǎn)向周?chē)泥従庸?jié)點(diǎn)發(fā)出錯(cuò)誤消息，提示通過(guò)這個(gè)節(jié)點(diǎn)抵達(dá)目標(biāo)節(jié)點(diǎn)的路徑已斷開(kāi)。

以下三種情況，節(jié)點(diǎn)會(huì)對(duì)錯(cuò)誤消息進(jìn)行初始化處理：

第一種，當(dāng)節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)發(fā)送請(qǐng)求，就是向目標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)，節(jié)點(diǎn)在生存周期內(nèi)檢查出原本存活的路由發(fā)生了連接斷開(kāi)問(wèn)題，并且修復(fù)路由沒(méi)有結(jié)果，那么就會(huì)將錯(cuò)誤信息初始化。第二種，當(dāng)節(jié)點(diǎn)接收到附近節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包時(shí)，檢查數(shù)據(jù)包中的路由信息表，發(fā)現(xiàn)目的IP不可達(dá)，即本節(jié)點(diǎn)的路由表沒(méi)有通往該目的IP的路徑。那么節(jié)點(diǎn)對(duì)錯(cuò)誤信息初始化。第三種，當(dāng)節(jié)點(diǎn)沒(méi)有接收到正常數(shù)據(jù)包，而是接收附近節(jié)點(diǎn)發(fā)送的錯(cuò)誤消息，并且發(fā)送錯(cuò)誤消息的在鄰居節(jié)點(diǎn)集中不止一個(gè)，那么節(jié)點(diǎn)會(huì)對(duì)錯(cuò)誤消息初始化。

（3）AODV相關(guān)應(yīng)用

在某些網(wǎng)絡(luò)配置中，無(wú)線(xiàn)自組網(wǎng)網(wǎng)絡(luò)能夠在不利用AODV的外部路由區(qū)域間提供連接。對(duì)于在外部路由區(qū)域中的任何相關(guān)網(wǎng)絡(luò)，如果與其他網(wǎng)絡(luò)連接的點(diǎn)能夠像子網(wǎng)路由器一樣工作，那么無(wú)線(xiàn)自組網(wǎng)網(wǎng)絡(luò)就能夠在外部路由區(qū)域間保持連接。實(shí)際上，外部路由網(wǎng)絡(luò)可以將AODV所定義的無(wú)線(xiàn)自組網(wǎng)網(wǎng)絡(luò)像傳送網(wǎng)絡(luò)（transit network）來(lái)使用。

為了使無(wú)線(xiàn)自組網(wǎng)網(wǎng)絡(luò)向傳送網(wǎng)絡(luò)來(lái)使用，外部網(wǎng)絡(luò)的連接點(diǎn)相當(dāng)于是起到了每個(gè)子網(wǎng)中的一個(gè)路由器的作用。這個(gè)路由器需要使外部網(wǎng)絡(luò)的子網(wǎng)提供訪(fǎng)問(wèn)權(quán)限。需要為外部子網(wǎng)創(chuàng)建并更新目的地址序列數(shù)[4]。

2 蟻群算法原理

（1）蟻群算法簡(jiǎn)介

只要觀(guān)察過(guò)螞蟻在覓食的行為，總能看到蟻群不斷的嘗試不同的路徑，雖然一開(kāi)始的路徑會(huì)天差地別，但是最后總是能夠找到一條最優(yōu)路徑，有時(shí)候不一是最短但一定是最優(yōu)的路徑。假設(shè)有一群螞蟻，它們?cè)趯ふ沂澄锏臅r(shí)候遇到一個(gè)障礙物，所以出現(xiàn)左右兩條路徑，但是因?yàn)橹皼](méi)有螞蟻?zhàn)哌^(guò)，也就沒(méi)有信息素來(lái)指引螞蟻，螞蟻?zhàn)咦笥衣窂绞堑雀怕实?。每?dāng)有螞蟻?zhàn)哌^(guò)就會(huì)留下會(huì)以一定速度散發(fā)的信息素。后面的螞蟻是以信息素強(qiáng)烈程度判斷走哪條路徑，因此，信息素大多分布在短的那條路徑上，螞蟻會(huì)趨向于走信息素多的路[10]。

（2）蟻群算法計(jì)算過(guò)程

首先需要對(duì)這個(gè)問(wèn)題進(jìn)行建模，假設(shè)出需要的參數(shù)變量。螞蟻經(jīng)過(guò)的路徑，也就是標(biāo)識(shí)每個(gè)螞蟻訪(fǎng)問(wèn)過(guò)的地點(diǎn)，這里設(shè)置一個(gè)boolean型的visited訪(fǎng)問(wèn)矩陣來(lái)表示螞蟻訪(fǎng)問(wèn)過(guò)的地點(diǎn)，如果只為false就表示沒(méi)有訪(fǎng)問(wèn)過(guò)，如果是true表示已訪(fǎng)問(wèn)。Int型的變量S_L表示最短的距離，B_T表示最優(yōu)的距離，這些距離計(jì)算起來(lái)都比較方便，每次只需將兩個(gè)地點(diǎn)的距離加入即可。螞蟻會(huì)釋放信息素那么信息素量化，就創(chuàng)建一個(gè)信息素矩陣M_P，橫縱坐標(biāo)表示地點(diǎn)。那么地點(diǎn)之間的信息素需要記錄，單個(gè)螞蟻?zhàn)咭淮吾尫诺男畔⑺匾矐?yīng)該被記錄下來(lái)，這里假設(shè)螞蟻之間沒(méi)有區(qū)別的，這個(gè)矩陣用來(lái)計(jì)算信息素和比較法方便。該矩陣命名為Ant_P，橫縱坐標(biāo)也是地點(diǎn)。螞蟻需要對(duì)路線(xiàn)進(jìn)行選擇，因?yàn)椴皇撬新肪€(xiàn)螞蟻都可以通過(guò)，所以需要另一個(gè)矩陣存儲(chǔ)螞蟻可以通過(guò)的地點(diǎn)，命名為Permit矩陣。在螞蟻運(yùn)動(dòng)過(guò)程還有一些參數(shù)需要進(jìn)行控制這里就設(shè)為a，b，c，d四個(gè)參數(shù)，螞蟻運(yùn)動(dòng)時(shí)間也需要記錄設(shè)為T(mén)。算法步驟如下[11]：

①初始化矩陣和參數(shù)。

設(shè)置算法開(kāi)始運(yùn)行的時(shí)間T為0，最優(yōu)路徑設(shè)為Integer.MAXVLAUE，B_T設(shè)為空值。設(shè)置螞蟻的信息素矩陣的所有初始值為0，visited矩陣初始化false，Permit矩陣可訪(fǎng)問(wèn)地點(diǎn)設(shè)置為1，不能訪(fǎng)問(wèn)的地點(diǎn)設(shè)置為0。設(shè)置螞蟻的初始位置，可以隨機(jī)也可固定一個(gè)起始位置。在visited矩陣中將起始節(jié)點(diǎn)設(shè)置為true，可以訪(fǎng)問(wèn)的Permit矩陣中設(shè)置該起始節(jié)點(diǎn)值為0。

②迭代選路過(guò)程。

以輪盤(pán)賭選擇方式選擇每只螞蟻的下一條路徑，選擇一條路徑，在visit中將該節(jié)點(diǎn)改為true，并且將Permit矩陣中對(duì)應(yīng)節(jié)點(diǎn)狀態(tài)設(shè)為0。遍歷全部節(jié)點(diǎn)后，將節(jié)點(diǎn)插入建立的res路徑結(jié)果集。然后按照狀態(tài)轉(zhuǎn)移概率計(jì)算螞蟻k在地點(diǎn)i和j之間選擇某個(gè)地點(diǎn)，作為其信息素矩陣M_P的信息素值。然后比較出最好路徑，經(jīng)由對(duì)比每個(gè)螞蟻的路徑時(shí)間，然后將較小值賦值給B_L。狀態(tài)轉(zhuǎn)移概率公式如下[11]：

狀態(tài)轉(zhuǎn)移概率公式中p表示，第k個(gè)螞蟻選擇地點(diǎn)i到j(luò)的當(dāng)中一個(gè)地點(diǎn)的概率，τi,j(t)表示節(jié)點(diǎn)i，j在t時(shí)刻的信息素，這個(gè)信息素的大小是從信息素矩陣M_P中按照第i行，第j列的取值大小，φi,j(t)表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離的倒數(shù)，距離是按照地點(diǎn)i和地點(diǎn)j的距離計(jì)算的，然后取該距離的倒數(shù)代入公式中。公式中的α，β參數(shù)為信息啟發(fā)式因子和期望啟發(fā)式因子，這兩個(gè)參數(shù)是信息素和路徑上的指數(shù)，所以狀態(tài)轉(zhuǎn)移概率受到信息素大小和路徑長(zhǎng)度的影響是可以通過(guò)調(diào)整這兩個(gè)參數(shù)大小來(lái)控制的。但是就算調(diào)整了這兩個(gè)參數(shù)，概率還是主要受信息素和路徑的影響。所以該公式的現(xiàn)實(shí)意義就是螞蟻會(huì)選擇離自己距離近的，信息素濃度大的路徑。

③更新信息素矩陣M_P

更新信息素是根據(jù)上一只螞蟻更新后的信息素，當(dāng)然第一只是直接進(jìn)行更新的。更新信息素是可以對(duì)距離進(jìn)行設(shè)置，即走完n個(gè)地點(diǎn)進(jìn)行更新，這里的n可以為1，2，…，n。按如下公式更新信息素矩陣M_P。

3 基于蟻群算法的AODV路由協(xié)議

（1）算法設(shè)計(jì)

Ad hoc網(wǎng)絡(luò)拓?fù)涑橄鬄閳DGraph，通信節(jié)點(diǎn)由頂點(diǎn)表示，鏈路由圖的邊表示，其中N為圖Graph中所有節(jié)點(diǎn)集合，并且維護(hù)一張LinkedTable表，意為鏈路的集合，假設(shè)任意2個(gè)節(jié)點(diǎn)i，j存在鏈路，則表明節(jié)點(diǎn)i，j之間存在連接。

本文研究的是將Ad hoc網(wǎng)絡(luò)中路由協(xié)議和蟻群算法結(jié)合起來(lái)，首先將螞蟻分為前驅(qū)螞蟻和后繼螞蟻，前驅(qū)螞蟻對(duì)應(yīng)AODV協(xié)議中的請(qǐng)求報(bào)文消息。后繼螞蟻對(duì)應(yīng)回應(yīng)消息報(bào)文。對(duì)上述兩種報(bào)文消息進(jìn)行修改，通過(guò)添加報(bào)文發(fā)送的時(shí)間和上一跳的阻塞程度，來(lái)更新前驅(qū)螞蟻報(bào)文和后繼螞蟻報(bào)文，然后通過(guò)報(bào)文計(jì)算路由時(shí)延和擁塞狀態(tài)。為了達(dá)到最佳路徑，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)保存信息素，建立一個(gè)概率路由表代替原來(lái)的AODV表，如圖1所示。

圖1 概率路由表表項(xiàng)和AODV路由表表項(xiàng)對(duì)應(yīng)關(guān)系

圖1 左邊是概率路由表表項(xiàng)，右邊AODV路由表表項(xiàng)。

概率路由表中的Dst Hops對(duì)應(yīng)AODV路由表中Hop Count表項(xiàng)，存放去往同一個(gè)目的節(jié)點(diǎn)的多條不同的跳數(shù)，用Route list替換AODV路由表中的Next Hop以保證蟻群算法的運(yùn)行。

計(jì)算這個(gè)狀態(tài)轉(zhuǎn)移概率使用改進(jìn)的算法公式：

該公式計(jì)算結(jié)果為路由選擇的概率，表示在t時(shí)刻在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包k從當(dāng)前節(jié)點(diǎn)i選擇鄰接節(jié)點(diǎn)j作為下一個(gè)節(jié)點(diǎn)的概率。μi,j(t)是鏈路質(zhì)量函數(shù)，表示當(dāng)前節(jié)點(diǎn)j的堵塞程度，當(dāng)且僅當(dāng)該值為0時(shí)，表示節(jié)點(diǎn)j阻塞，為1時(shí)j通暢。這里維護(hù)的概率路由表相當(dāng)于是信息素的濃度表。螞蟻根據(jù)信息素的濃度強(qiáng)烈程度選擇要走的路徑，而本文的則是數(shù)據(jù)包根據(jù)概率表大小也就是信息素濃烈程度，選擇最佳的路徑。與螞蟻在前進(jìn)過(guò)程中釋放信息素和修改跳數(shù)、阻塞程度相一致，網(wǎng)絡(luò)中的數(shù)據(jù)包在從一個(gè)節(jié)點(diǎn)抵達(dá)另一個(gè)節(jié)點(diǎn)也會(huì)對(duì)節(jié)點(diǎn)的概率路由、下一跳、阻塞程度進(jìn)行更新，也就是在運(yùn)動(dòng)過(guò)程中不斷維護(hù)每個(gè)節(jié)點(diǎn)的AODV路由表。由不斷地路由組建和路由維護(hù)最終形成路由。

（2）算法實(shí)現(xiàn)

①路徑探索

Source節(jié)點(diǎn)即源節(jié)點(diǎn)要和Destination即目標(biāo)節(jié)點(diǎn)進(jìn)行通信時(shí)，源節(jié)點(diǎn)在本地路由信息表中檢查通往目標(biāo)節(jié)點(diǎn)的路由信息，這個(gè)過(guò)程和上述反向路由建立過(guò)程相似，都需要現(xiàn)在本地查找，然后再作其它處理。在本地路由中找到通往目標(biāo)節(jié)點(diǎn)的路由，并且在路由生命周期中沒(méi)有消亡。那么就嘗試發(fā)送請(qǐng)求消息給目標(biāo)節(jié)點(diǎn)。如果能夠抵達(dá)目標(biāo)節(jié)點(diǎn)就更新該條路由，如果不能夠抵達(dá)那么就從路由表中刪除這條無(wú)效路由。

②路由組建

算法實(shí)現(xiàn)需要組建路由，發(fā)現(xiàn)路由采用廣泛使用的廣播方式，雖然可能會(huì)導(dǎo)致一些不必要的浪費(fèi)，或許可能還會(huì)發(fā)生阻塞，但是這種方式最簡(jiǎn)單能將所有可能情況覆蓋，所以還是選擇了廣播方式。

節(jié)點(diǎn)需要去搜尋目標(biāo)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)向周?chē)?jié)點(diǎn)發(fā)送的請(qǐng)求消息后，首先檢查在路徑發(fā)現(xiàn)周期內(nèi)是否已存在源IP和請(qǐng)求ID與該請(qǐng)求信息匹配的消息，存在該消息就會(huì)丟棄，否則就會(huì)檢查本地路由表中是否存在通往該節(jié)點(diǎn)的可達(dá)路徑，如果存在則向源節(jié)點(diǎn)回復(fù)消息建立路由，更新路徑上節(jié)點(diǎn)的概率路由表。

如果沒(méi)有檢查到存在任何的路由信息，就比較請(qǐng)求消息報(bào)文中的seq號(hào)和目的節(jié)點(diǎn)的seq號(hào)，請(qǐng)求消息中的源seq號(hào)和目的節(jié)點(diǎn)的seq號(hào)需要保持一致。因?yàn)榉聪蚵酚删褪菍?duì)發(fā)送節(jié)點(diǎn)的回復(fù)。但是也有可能不相等，如果發(fā)送請(qǐng)求消息的seq號(hào)大于目標(biāo)節(jié)點(diǎn)的seq號(hào)，則更新為發(fā)送請(qǐng)求消息的seq號(hào)，并且繼續(xù)向下一跳節(jié)點(diǎn)廣播，否則就丟棄該請(qǐng)求消息，因?yàn)樵撜?qǐng)求消息已經(jīng)過(guò)期了。每次建立路由時(shí)，還需檢查周?chē)鷪?bào)文中是否存在更小的跳數(shù)，如果存在就已該跳數(shù)建立一條反向路由用來(lái)跟本節(jié)點(diǎn)通信。當(dāng)節(jié)點(diǎn)收到數(shù)據(jù)包時(shí)，更新概率路由表，計(jì)算鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，選擇概率大的路徑轉(zhuǎn)發(fā)，借此來(lái)避免廣播帶來(lái)的網(wǎng)絡(luò)中發(fā)生嚴(yán)重阻塞情況。

③路由維護(hù)

建立路由后需要維護(hù)路由表的表項(xiàng)。開(kāi)始時(shí)廣播數(shù)據(jù)包，廣播到的節(jié)點(diǎn)動(dòng)態(tài)更新概率路由表，路由的維護(hù)以發(fā)送Hello信息包的形式檢測(cè)連接是否正常。假設(shè)存在節(jié)點(diǎn)i和節(jié)點(diǎn)j，需要維護(hù)這兩個(gè)節(jié)點(diǎn)之間的通信。節(jié)點(diǎn)i收到鄰居節(jié)點(diǎn)j的Hello消息后，節(jié)點(diǎn)i會(huì)根據(jù)返回的Hello消息更新路由表中的路徑、時(shí)延和到下一跳j的路徑。當(dāng)節(jié)點(diǎn)i在一定時(shí)間內(nèi)，沒(méi)有收到來(lái)自鄰居節(jié)點(diǎn)發(fā)送的Hello消息時(shí)，就認(rèn)為該鏈路中斷了。當(dāng)鏈路中斷時(shí)，不能立即重啟網(wǎng)絡(luò)，保證網(wǎng)絡(luò)不會(huì)因?yàn)轭l繁重啟而消耗大量資源。需要對(duì)中斷鏈路進(jìn)行替換。首先將該鏈路在概率表中對(duì)應(yīng)的表項(xiàng)刪除，然后查找概率路由表是否有其他的目的節(jié)點(diǎn)路徑。當(dāng)沒(méi)有其他鏈路可選時(shí)，才需要從源節(jié)點(diǎn)開(kāi)始重新構(gòu)建整個(gè)網(wǎng)絡(luò)。在通信過(guò)程中，數(shù)據(jù)傳輸過(guò)程可能出現(xiàn)路由黑洞問(wèn)題。但對(duì)于該協(xié)議，循環(huán)問(wèn)題在路徑探索時(shí)就已解決，在發(fā)送請(qǐng)求消息階段，螞蟻?zhàn)哌^(guò)的每一個(gè)節(jié)點(diǎn)會(huì)將自己的ID加入到螞蟻的信息中，螞蟻只會(huì)探索沒(méi)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。所以算法本身有效避免了死循環(huán)問(wèn)題[12]。

④蟻群算法流程圖

（3）仿真結(jié)果

圖2 改進(jìn)后的蟻群算法流程圖

①不同暫停時(shí)間下的端對(duì)端傳輸延時(shí)性能

圖3 平均端對(duì)端傳輸時(shí)延與暫停時(shí)間曲線(xiàn)圖

由圖3可知，在不同的暫停時(shí)間下，改進(jìn)后的AODV路由協(xié)議的傳輸時(shí)延比原來(lái)的AODV協(xié)議小，這是由于改進(jìn)后的蟻群算法可以提供比較穩(wěn)定的連接，可以通過(guò)最優(yōu)路徑尋找下一個(gè)結(jié)點(diǎn)。因此，通過(guò)蟻群算法改進(jìn)后的AODV協(xié)議可以改善因網(wǎng)絡(luò)丟包嚴(yán)重導(dǎo)致的時(shí)延，具有更好的性能。

②不同結(jié)點(diǎn)移動(dòng)速度下的端對(duì)端傳輸延時(shí)性能

圖4 平均端對(duì)端傳輸時(shí)延與節(jié)點(diǎn)移動(dòng)速度曲線(xiàn)圖

由圖4可知，在相同的節(jié)點(diǎn)移動(dòng)速度下，改進(jìn)后的AODV協(xié)議的傳輸延時(shí)比原來(lái)的AODV協(xié)議小，說(shuō)明改進(jìn)后的AODV協(xié)議比原來(lái)的AODV協(xié)議性能更好，更能適應(yīng)拓?fù)洳粩嘧兓木W(wǎng)絡(luò)。

4 結(jié)語(yǔ)

MANET的路由協(xié)議可分為主動(dòng)式（表驅(qū)動(dòng)）和被動(dòng)式（按需），具體取決于它們對(duì)拓?fù)渥兓姆磻?yīng)方式[6]。因?yàn)閷?shí)際應(yīng)用中，即使移動(dòng)終端上沒(méi)有這種主動(dòng)協(xié)議也可能會(huì)花費(fèi)網(wǎng)絡(luò)資源來(lái)構(gòu)建路由，浪費(fèi)了有限的無(wú)線(xiàn)帶寬，所以許多研究人員提出使用反應(yīng)式協(xié)議，也就是使用按需方法構(gòu)建路由協(xié)議。具體而言，基于這種按需方法提出的一種反應(yīng)性協(xié)議是臨時(shí)按需距離矢量路由（AODV）。

無(wú)線(xiàn)移動(dòng)節(jié)點(diǎn)可以動(dòng)態(tài)地進(jìn)入網(wǎng)絡(luò)以及離開(kāi)網(wǎng)絡(luò)，常規(guī)網(wǎng)絡(luò)中的路由器通常不會(huì)四處走動(dòng)，并且很少離開(kāi)或加入網(wǎng)絡(luò)，這種情況導(dǎo)致總體上無(wú)法收斂到穩(wěn)定的路由。因此，在部署MANET時(shí)要考慮許多問(wèn)題。由于節(jié)點(diǎn)的移動(dòng)性，自組織網(wǎng)絡(luò)中的拓?fù)淇赡軙?huì)不斷變化。MANET的路由協(xié)議必須處理這些問(wèn)題才能有效。

因此，本文嘗試應(yīng)用已證明其在有線(xiàn)網(wǎng)絡(luò)路由協(xié)議中有效的蟻群優(yōu)化技術(shù)來(lái)優(yōu)化現(xiàn)有的AODV路由協(xié)議。在仿真實(shí)驗(yàn)中，將蟻群算法應(yīng)用于AODV路由協(xié)議嘗試克服已解決的問(wèn)題，并提高其運(yùn)行性能。