【正文】 即使是對于一個(gè)并不大的程序，代碼的組織都是非常重要的，因?yàn)檫@關(guān)系到日后的維護(hù) 以及擴(kuò)展。 通過本章的 NS 模擬，對 AODV 路由協(xié)議的性能及運(yùn)行原理有了直觀的了解。 圖 用 nam演示掉包 本章小節(jié) NS 是一個(gè)龐大的系統(tǒng)，無線網(wǎng)絡(luò)模塊內(nèi)容只是他其中很小的一部分，本章首先概要得介紹了 NS 系統(tǒng)，然后在 NS 環(huán)境下構(gòu)建了一個(gè)無線網(wǎng)絡(luò)，并在該網(wǎng)絡(luò)上運(yùn)行 AODV 路由協(xié)議。 圖 用 nam演示 RREQ 廣播 數(shù)據(jù)傳輸演示 無線網(wǎng)絡(luò)中存在大量的節(jié)點(diǎn)，節(jié)點(diǎn)間需要相互通信，可以用 nam 來演示這一過程，圖 是其中某個(gè)時(shí)刻的一個(gè)截圖，圖中的小黑點(diǎn)表示傳輸?shù)臄?shù)據(jù)，當(dāng)前正在從 1 號節(jié)點(diǎn)傳往 38 號節(jié)點(diǎn)?？梢杂?NS2 下的 nam 工具來演示 RREQ 廣播情形，圖 是在某一時(shí)刻截取到的運(yùn)行場景圖。 路由負(fù)載模擬 圖 34 路由負(fù)載模擬 由圖 可以很明顯的看出，隨著 pause time 的增大，路由負(fù)載呈遞減趨勢，這說明移動(dòng)性小的傳感網(wǎng)絡(luò)的路由負(fù)載要比移動(dòng)性大的好。 模擬結(jié)果 圖 網(wǎng)絡(luò)數(shù)據(jù)包時(shí)間延遲 圖中橫坐標(biāo) 是不同的連接，比如 12， 45 等，縱坐標(biāo)表示的延遲量， pause time是暫停的時(shí)間，值越大，表示整個(gè)場景的移動(dòng)性越小，由圖可以看出， pause time越大網(wǎng)絡(luò)的延遲就越小，這說明傳感網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)對整個(gè)網(wǎng)絡(luò)的延遲影響很大。 printf %ISs:%d}n,stopTime,stopTime。} if (recvdNum=0){ printf }nWarning:no packets were received,simulation may be too shortln。 } if (recvdNum!=0) {avgee delay=delay/recvdNum。 } delay+=(recvTime[i)sendTime[i))。 } } END{ delay=avgse delay=recvd Num=0。 } sendTime[pkt id]=time。amp。 level=$4。 plotid=$6。 t 加 e=$2。 st 叩 Time=0。 圖 AODV 協(xié)議吞吐量 網(wǎng)絡(luò)數(shù)據(jù)包時(shí)間延遲 計(jì)算延遲的 awk 腳本 BEGIN{ recvdSize=0。$1 echo $dd。$ echo set key left top box。$1 echo set ylabel \Transmission Speed(KB/s)\。 v src=$i v dst=$j f $ dd=$dd,\ $1 一 $i$\title\$i$j\with linespoints done echo set term png medium 。 網(wǎng)絡(luò)吞吐量模擬 shell 腳本 一次計(jì)算多個(gè)連接的吞吐量并且畫圖顯示的 shell 腳本如下 : !/bin/csh grep AGT $$ srcl=1 dstl=2 src2=4 dst2=5 src3=4 dst3=6 src4=6 dst4=7 src5=7 dst5=8 src6=7 dst6=9 src7=8 dst7=9 i=$src 1 j=$dstl dd=plot \$1 一 $i$\title\$i$j\with linespoints gawk v outfile=$1 一 $i$39。 ，重新進(jìn)行上述模擬過程。 NS2 解釋執(zhí)行剛才編寫的 Otcl 腳本。仿真完成后，可以對 trace 文件進(jìn)行分析研究。 Trace 對象能夠把模擬過程中發(fā)生的特定類型的時(shí)間記錄 在 trace 文件中。 ，從而確定網(wǎng)絡(luò)上的業(yè)務(wù)量分布。首先配置模擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，此時(shí)可以確定鏈路的一 些基本特性，如帶寬、延遲和丟失策略等。這就需要利用到分裂對象模型，添加新的 C++類和 Otcl 類，然后再編寫 Otcl 腳本。 在使用 NS2 進(jìn)行模擬前，首先要分析模擬涉及哪個(gè)層次 [3].NS2 模擬 分兩個(gè)層次 :一個(gè)是基于 Otcl 編程的層次，利用 NS2 己有的網(wǎng)絡(luò)元素實(shí)現(xiàn)模擬，無需對 NS2 本身進(jìn)行任何修改，只要編寫 Otcl 腳本 。*.tr39。 NS2 利用 NAM (Network Animator)和 Xgraph 軟件，可以將仿真結(jié)果文件*.nam39。支持 Drop Tail、 RED、 CBQ、 WRR、 DRR 和 SFQ 等隊(duì)列管理和包調(diào)度機(jī)制 。支持算法路由、分級路 由、廣播路由、多播路由、靜態(tài)路由、動(dòng)態(tài)路由協(xié)議 。所以為了兼顧網(wǎng)絡(luò)模擬效率和系統(tǒng)建模的靈活性，編程者可以使用面向?qū)ο?、解釋?zhí)行的腳本程序設(shè)計(jì)語言 Otcl 進(jìn)行模擬配置，并通過編寫 C++構(gòu)件擴(kuò)充系統(tǒng)的模擬能力。 C++程序模塊的運(yùn)行速度非常快， 是強(qiáng)制類型的程序設(shè)計(jì)語言，容易實(shí)現(xiàn)精確的、復(fù)雜的算法，但是修改和實(shí)現(xiàn)、修正 bug 所花費(fèi)的時(shí)間較長 。 NS2 采用面向?qū)ο?、離散事件驅(qū)動(dòng)的模擬方法，易于對實(shí)際網(wǎng)絡(luò)建模，模擬效率高，系統(tǒng)易于擴(kuò)展。 OPNET 主要面向?qū)I(yè)人士，價(jià)錢比較昂貴 。網(wǎng)絡(luò)模擬有著周期小、成本低等特點(diǎn)，而且可以使研究者更容易利用他人的研究成果，可以使研究者 更專注于自己所研究的部分而不必為系統(tǒng)的其他部分耗費(fèi)過多的精力。 第三章 AODV路由算法模擬 NS2 概述 網(wǎng)絡(luò)模擬是進(jìn)行網(wǎng)絡(luò)技術(shù)研究的一種基本手段，在新技術(shù)的研究過程中，由于各種原因，實(shí)際網(wǎng)絡(luò)系統(tǒng)的實(shí)現(xiàn)往往是代價(jià)較高或是不現(xiàn)實(shí)的。在 超時(shí)發(fā)生之前，如果有報(bào)文需要到達(dá)其它目的地節(jié)點(diǎn)，則其它路由將被修復(fù)。其它使用同樣鏈路的路由必須被標(biāo)記為無效，但是進(jìn)行本地修復(fù)的節(jié)點(diǎn)可以將每一條新丟失的路由標(biāo)記為本地可修復(fù)。 當(dāng)有效路由的鏈路中斷，通常有多個(gè)目的地節(jié)點(diǎn)變得不可達(dá)。在對鏈路中斷進(jìn)行本地修復(fù)之后，向發(fā)起者節(jié)點(diǎn)發(fā)送 RERR 可以允許發(fā)起者節(jié)點(diǎn)基于當(dāng)前的節(jié)點(diǎn)位置，找到一條更好更新 的到目的地節(jié)點(diǎn)的路由。 對路由中的鏈路中斷進(jìn)行本地修復(fù)有時(shí)候會(huì)導(dǎo)致到目的節(jié)點(diǎn)的路徑長度增加。 收到帶有“ N”標(biāo)記 RERR 消息的節(jié)點(diǎn)，一定不能刪除 RERR 中到目的地節(jié)點(diǎn)的路由，如果 RERR 從沿著那條路由的下一跳收到，并且 到目的地節(jié)點(diǎn)的路由有一個(gè)或者多個(gè)先驅(qū)節(jié)點(diǎn)，它所需要做的只是轉(zhuǎn)發(fā)這條消息。如果新確定的到目的地節(jié)點(diǎn)的路由的跳數(shù)大于原來知道路由的跳數(shù)，則節(jié)點(diǎn)發(fā)出關(guān)于該目的地節(jié)點(diǎn)的 RERR，并設(shè)置“ N”比特標(biāo)記。如果路由發(fā)現(xiàn)周期結(jié)束仍然沒有收到關(guān)于目的地節(jié)點(diǎn)的 RREP(或者其它建立或更新路由的控 制消息 )，則發(fā)送關(guān)于該目的地節(jié)點(diǎn)的 RERR 。發(fā)起修復(fù)的節(jié)點(diǎn)等待路由發(fā)現(xiàn)周期來獲得對 RREQ 進(jìn)行響應(yīng)的 RREP。為了修復(fù)鏈路，節(jié)點(diǎn)增加關(guān)于目的節(jié)點(diǎn)的序列號，然后廣播關(guān)于目的節(jié)點(diǎn)的 RREQ ， RREQ 的 TTL值初始時(shí)設(shè)為下面的值 : max(MIN REPAIR TTL, X hops)+LOCAL _ADD_TTL hops 是到當(dāng)前無法投遞報(bào)文的發(fā)送者的跳數(shù)。如果一條無效路由收到數(shù)據(jù)報(bào)文，它的生存期字段更新為當(dāng)前時(shí)間加上 DELETE _PERIOD 。在這個(gè)時(shí)間以前，表項(xiàng)不應(yīng)該被刪除。 路由表項(xiàng)標(biāo)記為無效。 在發(fā)送 RERR 之前，需要對路由表做一定的更新，這一更新可能影響到不可達(dá)目的地節(jié)點(diǎn)的目的序列號。如果只有唯一 個(gè)鄰居需要接收 RERR，則 RERR 應(yīng)該單播至該節(jié)點(diǎn)，否則將帶有不可達(dá)目的地節(jié)點(diǎn)和對應(yīng)目 的 地序 列 號的 RERR 消 息 發(fā) 送到 本地 廣 播地 址 ( 目的 地 IP 地址= , TTL=1) 。在 RERR 中應(yīng)該包含這些節(jié)點(diǎn) :他們是剛才建立好的不可達(dá)目的節(jié)點(diǎn)列表中具有非空的先驅(qū)列表的那部分。對于情況 ((3)，不可達(dá)目的地節(jié)點(diǎn)列表中應(yīng)該包含 RERR 的一些目的地節(jié)點(diǎn)，這些目的地節(jié)點(diǎn)在本地路由表中存在 著對應(yīng)的路由表項(xiàng)，路由表項(xiàng)的下一跳是所收到的 RERR 消息的發(fā)送者。 對情況 (1)，節(jié)點(diǎn)首先產(chǎn)生一張不可達(dá)目的地節(jié)點(diǎn)的列表，包含不可達(dá)鄰居和在本地路由表中使用不可達(dá)鄰居作為下一跳的其它任何目的地。 (2)如果節(jié)點(diǎn)收到去往某個(gè)目的地節(jié)點(diǎn)的數(shù)據(jù)報(bào)文，而節(jié)點(diǎn)沒有到該目的地節(jié)點(diǎn)的有效路由并且沒有在進(jìn)行修復(fù) 。節(jié)點(diǎn)每一秒鐘不應(yīng)該產(chǎn)生超過 RERR_RATELIMIT 個(gè) RERR 消息。 如果到下一跳的鏈路無法通過上述任何方法檢測，轉(zhuǎn)發(fā)節(jié)點(diǎn)應(yīng)該認(rèn)為鏈路丟失，并且按照 中的方法采取糾正行動(dòng)。 RREQ 單播至下一跳，請求到下一跳的路由 。如果在 NEXT HOP WAIT 微秒內(nèi)沒有檢測到傳輸或者下一跳是目的地節(jié)點(diǎn) (因此不應(yīng)該轉(zhuǎn)發(fā)報(bào)文 )，則使用下面的方法之一確定連接性。例如，沒有收到鏈路層的 ACK，或者發(fā)送 RTS 以后沒有收到 CTS，即使經(jīng)過最大數(shù)目的重傳嘗試以后，仍然失敗，則說明失去了到這一有效下一跳的鏈路。 維護(hù)本地連接性 每一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)都應(yīng)該了解到它到有效下一跳的持續(xù)連接性，同時(shí)也應(yīng)該留意在過去 (ALLOWED_HELLO_OSS X HELLO_INTERVAL)時(shí)間內(nèi)發(fā)送 Hello 消息的鄰居。 在 AODV 中，任何時(shí)候節(jié)點(diǎn)收到任何控制報(bào)文 ，也具有和收到顯性的 Hello消息一樣的意義。到鄰居的路由如果存在，必須包含 Hello 消息中的最新目的地序列號。 任何時(shí)候節(jié)點(diǎn)收到來自鄰居的 Hello 消息，節(jié)點(diǎn)應(yīng)該確信它具有到這個(gè)鄰居的有效路由，如果必要，建立一條這樣的路由。 跳數(shù) :0。每 HELLO INTERVAL 微秒內(nèi)，節(jié)點(diǎn)檢查在最近的 HELLO INTERVAL 是否發(fā)出了一個(gè)廣播報(bào)文 (比如 RREQ)，如果沒有發(fā)送，它會(huì)廣播一個(gè) TTL 值為 1 的RREP 稱為 Hello 消息， Hello 消息的字段設(shè)置如下 : 目的地 IP 地址 :節(jié)點(diǎn)的 IP 地址 。 Hello 消息 在 AODV 路 由協(xié)議中，節(jié)點(diǎn)可以通過廣播本地 Hell。然而，不能確保鏈路一直是雙向的。收到 RREP ACK 的時(shí)間很可能就在剛剛發(fā)出帶“ A”標(biāo)志的 RREP 的時(shí)間之后。這個(gè)時(shí)間可以設(shè)置為允許路由請求重試次數(shù)所需時(shí)間的上限。節(jié)點(diǎn)忽略所有從“黑名單”集 合處發(fā)來的 RREQ。隨后的 RREQ 可能通過一條雙向路徑 (假設(shè)這樣的路徑存在 )到達(dá)，但是這一RREQ 將被忽略。在 AODV 中，任何節(jié)點(diǎn)只處理具有同樣 RREQID 的第一個(gè) RREQ 消息，忽略任何后續(xù)的 RREQ報(bào)文。即使發(fā)起節(jié)點(diǎn)和目的節(jié)點(diǎn)存在雙向路由，這種情況仍可能發(fā)生。如果沒有其它 RREP 到達(dá) RREQ 消息的發(fā)起節(jié)點(diǎn)，發(fā)起者節(jié)點(diǎn)在超時(shí)以后重新嘗試路由發(fā)現(xiàn)。最后，通往目的地節(jié)點(diǎn)的下一跳的路由的先驅(qū)表更新為通往源路徑路由上的下一跳。任何節(jié)點(diǎn)傳送RREP 的時(shí)候，把 RREP 被轉(zhuǎn)發(fā)到的下一跳節(jié)點(diǎn)加入 對應(yīng)目的地節(jié)點(diǎn)的先驅(qū)列表中，對該先驅(qū)列表進(jìn)行更新。當(dāng)前節(jié)點(diǎn)現(xiàn)在可以使用這條路由對去往目的節(jié)點(diǎn)的數(shù)據(jù)報(bào)文進(jìn)行轉(zhuǎn)發(fā)了。跳數(shù)設(shè)為新跳數(shù)，過期時(shí)間為當(dāng)前時(shí)間加上 RREP 消息中的生存期。 序列號相同，新跳數(shù)小于路由表項(xiàng)中的跳數(shù)。 RREP 中的目的地序列號大于節(jié)點(diǎn)中的目的地序列號的拷貝，并且已知值為有效 。我們把這一增加后的值稱為“新跳數(shù)”。 免費(fèi) RREP 就這樣被發(fā)送到去往目的地節(jié)點(diǎn)路徑上的下一跳，就像目的地節(jié)點(diǎn)已 經(jīng)發(fā)出了到發(fā)起者節(jié)點(diǎn)的一個(gè) RREQ，而這一 RREP 正是對假想的 RREQ 進(jìn)行應(yīng)答一樣。 目的地序列號 :RREQ 中的發(fā)起者序列號 。 發(fā)給 Rl 妞 Q 發(fā)起者的 RREP 和前面提到的一樣，而發(fā)給目的節(jié)點(diǎn)的免費(fèi)RREP， 在 RREP 消息字段中包 含下面的值 : 跳數(shù) :節(jié)點(diǎn)路由表中到發(fā)起者節(jié)點(diǎn)的路由表項(xiàng)給出的跳數(shù) 。目的地節(jié)點(diǎn)很可能需要到發(fā)起者節(jié)點(diǎn)的路由，為了使目的節(jié)點(diǎn)能夠知道到發(fā)起者節(jié)點(diǎn)的路由，發(fā)起者節(jié)點(diǎn)應(yīng)該在 RREQ 消息中設(shè)置“ G”標(biāo)記。如果中間節(jié)點(diǎn)對每一個(gè)發(fā)出的 RREQ 進(jìn)行應(yīng)答，目的節(jié)點(diǎn)就不能收到任何 RREQ 的拷貝，也就不可能知道到發(fā)起者節(jié)點(diǎn)的路由。 RREP 的生存期字段由路由表項(xiàng)的過期時(shí)間減去當(dāng)前時(shí)間計(jì)算得出。中間節(jié)點(diǎn)同時(shí)更新到 RREQ 發(fā)起者節(jié)點(diǎn)的路由表項(xiàng)，這一操作通過將通往目的地的下一跳放入反向路由表項(xiàng) (即 RREQ 消息中發(fā)起者 IP 地址字段的表項(xiàng) )的先驅(qū)表中實(shí)現(xiàn)。 如果產(chǎn)生 RREP 的節(jié)點(diǎn)不是目的地節(jié)點(diǎn)，而是發(fā)起節(jié)點(diǎn)到目的地節(jié)點(diǎn)路徑上的一個(gè)中間節(jié)點(diǎn)，它將拷貝己知的目的地序列號至 RREP 消息中的目的地序列號字段。目的節(jié)點(diǎn)將它的序列號 (可能是新增加的 )放入 RREP 的目的地序列號字段當(dāng)中，并把跳數(shù)字段值設(shè)置為 O。 如果產(chǎn)生 RREP 的節(jié)點(diǎn)是目的節(jié)點(diǎn)本身，假如 RREQ 報(bào)文中的序列號等于目的地節(jié)點(diǎn)本身的序列號加 1，則節(jié)點(diǎn)必須把自己的序列號再加 1(RREQ 報(bào)文中的序列號大于目的地節(jié)點(diǎn)維護(hù)的自身序列號的情況