ad_hoc網(wǎng)絡(luò)aodv路由協(xié)議算法設(shè)計

1、<p><b>　　西南科技大學(xué)</b></p><p><b>　　畢業(yè)設(shè)計（論文）</b></p><p>　　題目名稱：ad-hoc網(wǎng)絡(luò)AODV路由協(xié)議算法設(shè)計</p><p>　　年 級：2003級 □本科 □專科</p><p>　

2、　學(xué)生學(xué)號：20035233</p><p>　　學(xué)生姓名：虞靜 指導(dǎo)教師：江虹</p><p>　　學(xué)生單位：信息工程學(xué)院 技術(shù)職稱：副教授</p><p>　　學(xué)生專業(yè)：通信專業(yè) 教師單位：信息工程學(xué)院</p><p>　　西 南 科 技 大 學(xué)

3、 教 務(wù) 處 制</p><p>　　ad-hoc網(wǎng)絡(luò)AODV路由協(xié)議算法設(shè)計</p><p>　　摘要：Ad-hoc無線自組織網(wǎng)絡(luò)技術(shù)是近來出現(xiàn)的不同于傳統(tǒng)網(wǎng)絡(luò)的一種新技術(shù),受到國內(nèi)外的廣泛關(guān)注，其路由技術(shù)是無線自組網(wǎng)的一個重要研究領(lǐng)域。為適應(yīng)不同的應(yīng)用場合，已出現(xiàn)了諸如AODV等針對性較強的路由協(xié)議。</p><p>　　本文根據(jù)AODV路由協(xié)議的規(guī)范，

4、設(shè)計和實現(xiàn)了相應(yīng)的原理性算法，利用RREQ,RREP和RERR等協(xié)議幀進(jìn)行路由查找和維護(hù).并通過HELLO包維持鏈路的聯(lián)接。同時，為提高處理效率，該原理性算法使用Linux操作系統(tǒng)用戶態(tài)與內(nèi)核態(tài)實現(xiàn)相應(yīng)的路由表管理，并使用鉤子函數(shù)對網(wǎng)絡(luò)中不同主機產(chǎn)生的包進(jìn)行處理。在PC104操作平臺上進(jìn)行的大量實驗驗證了該原理性算法的可行性，證明其達(dá)到了相應(yīng)的設(shè)計目標(biāo)。論文最后簡述了AODV路由協(xié)議的研究方向，并對以后的研究作出了展望。</p&g

5、t;<p>　　關(guān)鍵字：AODV；無線自組網(wǎng)；路由；Linux</p><p>　　AODV Routing Protocol Algorithm Design of Ad-Hoc Wireless Network</p><p>　　Abstract：Ad-Hoc wireless network is a new network technology, which has

6、 received great consideration, being different from the traditional ones. Routing is a very important research field in wireless self-organizing network. In order to adapt various occasions, there appears many specific r

7、outing protocols such as AODV(Ad hoc On-Demand Distance Vector).</p><p>　　According to the AODV Route protocol specification, this thesis designs and realizes the corresponding implementation of principle al

8、gorithm. The design uses RREQ, RREP and RERR frames to discover and maintain routing, and keeps the link connectivity by using the HELLO packets. Meanwhile, in order to improve the efficiency, the principle algorithm man

9、ages routing table with kernel and user mode in Linux operating system, and deals with packets from different hosts by hook functions. Great many e</p><p>　　Key words：AODV, Wireless Self-Organizing Network,

10、 Route, Linux</p><p><b>　　目 錄</b></p><p>　　第1章 緒 論1</p><p>　　1.1 課題背景、目的及意義1</p><p>　　1.1.1 課題的背景1</p><p>　　1.1.2 課題的目的及意義1</p

11、><p>　　第2章 AODV路由協(xié)議算法原理2</p><p>　　2.1 AODV路由協(xié)議概述2</p><p>　　2.2 AODV 路由協(xié)議使用的專業(yè)術(shù)語4</p><p>　　2.3 幀的格式4</p><p>　　2.3.1 RREQ協(xié)議幀的格式4</p><p>　　

12、2.3.2 RREP協(xié)議幀的格式5</p><p>　　2.3.3 RERR協(xié)議幀的格式5</p><p>　　2.4 AODV的操作6</p><p>　　2.4.1 序列號的維護(hù)6</p><p>　　2.4.2 路由表項和先驅(qū)表6</p><p>　　2.4.3 產(chǎn)生路由請求7</p

13、><p>　　2.4.4 處理和轉(zhuǎn)發(fā)路由請求7</p><p>　　2.4.5 產(chǎn)生路由應(yīng)答8</p><p>　　2.4.6 接收和轉(zhuǎn)發(fā)路由應(yīng)答8</p><p>　　2.4.7 HELLO協(xié)議幀8</p><p>　　2.4.8 RERR協(xié)議幀，路由過期和路由刪除9</p><p

14、>　　2.4.9 接口信息9</p><p>　　第3章 Linux操作系統(tǒng)的網(wǎng)絡(luò)功能10</p><p>　　3.1 Linux操作系統(tǒng)的總體介紹10</p><p>　　3.2 Linux操作系統(tǒng)網(wǎng)絡(luò)功能的實現(xiàn)10</p><p>　　3.3 Linux操作系統(tǒng)路由轉(zhuǎn)發(fā)功能的實現(xiàn)11</p><

15、;p>　　第4章 AODV路由協(xié)議的實現(xiàn)13</p><p>　　4.1 AODV路由協(xié)議實現(xiàn)的框架結(jié)構(gòu)13</p><p>　　4.2 AODV協(xié)議實現(xiàn)的難點及其解決方法15</p><p>　　4.2.1 記錄每條路由的最后使用時間15</p><p>　　4.2.2 用戶空間和內(nèi)核空間的信息交互實現(xiàn)16<

16、/p><p>　　4.2.3 對內(nèi)核路由表的操作17</p><p>　　4.3 參數(shù)的設(shè)置17</p><p>　　4.4 路由協(xié)議中的主要流程18</p><p>　　4.4.1 主程序工作流程18</p><p>　　4.4.2 RREQ幀的接收處理流程20</p><p>

17、;　　4.4.3 HELLO幀的接收處理流程21</p><p>　　4.4.4 RREP幀的接收處理流程23</p><p>　　4.4.5 RERR幀的接收處理流程24</p><p>　　4.4.6 生成RREQ幀的函數(shù)流程27</p><p>　　4.4.7 生成RREP幀的函數(shù)流程28</p>&l

18、t;p>　　4.4.8 生成RERR幀的函數(shù)流程29</p><p>　　第5章 AODV路由協(xié)議的實驗研究31</p><p>　　5.1 測試環(huán)境31</p><p>　　5.2性能指標(biāo)測試31</p><p>　　5.2.1 路由查找時間及時延數(shù)據(jù)分析32</p><p>　　5.2.2

19、 ftp傳輸速率數(shù)據(jù)分析33</p><p>　　5.2.3 AODV背景流量數(shù)據(jù)分析35</p><p><b>　　總 結(jié)37</b></p><p><b>　　致 謝38</b></p><p><b>　　參考文獻(xiàn)39</b></p>

20、<p><b>　　附 錄41</b></p><p><b>　　第1章 緒 論</b></p><p>　　1.1 課題背景、目的及意義</p><p>　　1.1.1 課題的背景</p><p>　　自七十年代世界上第一個分組無線網(wǎng)絡(luò)ALOH在美國夏威夷大學(xué)研制成功之后，

21、分組網(wǎng)就受到了軍方的高度重視。國內(nèi)從八十年代起開始關(guān)注無線網(wǎng)的研究，經(jīng)過二十年來的努力，已經(jīng)取得了很多進(jìn)步和成果。而近幾年，由于軍用和民用需求的增加，大大促進(jìn)了無線自組網(wǎng)絡(luò)的研究。無線自組網(wǎng)現(xiàn)在廣泛用于自然災(zāi)害搶險，科學(xué)考察，以及戰(zhàn)場等通信場合。在任何時刻，任何地點，不需要現(xiàn)有信息基礎(chǔ)網(wǎng)絡(luò)設(shè)施的支持就能快速構(gòu)建起一個移動通信網(wǎng)絡(luò)。無線ad-hoc網(wǎng)絡(luò)的商業(yè)應(yīng)用發(fā)展越來越快，應(yīng)用范圍越來越廣。但是，目前無線自組網(wǎng)還缺乏很成熟的商業(yè)產(chǎn)品，它

22、還面臨著許多問題需要加以解決，比如對路由算法低功耗性能的要求、對QoS的支持、采用方位輔助路由方式等。由于受到手持設(shè)備電源供給的限制，路由算法的低能耗性能就顯得尤為重要。在對路由算法的解決方案中，有的對硬件的要求比較高，并不能發(fā)揮很好的市場優(yōu)勢，這給實際應(yīng)用帶來了不便，于此同時如何在移動中保持連接成為無線自組網(wǎng)的一個重要研究方向[1]。因此現(xiàn)階段有許多科研機構(gòu)對無線路由進(jìn)行研究，當(dāng)今已經(jīng)提出許多路由算法，各個路由算法有各自的優(yōu)缺點，適合

23、于不同場合。其中，AODV路由技術(shù)發(fā)展尤為迅速，</p><p>　　1.1.2 課題的目的及意義</p><p>　　無線自組網(wǎng)ad-hoc有靈活、機動組網(wǎng)、迅速適應(yīng)能力強的特點可應(yīng)用于野外工作環(huán)境，在有限的地域內(nèi)提供適應(yīng)機動條件的移動通信裝備以滿足特殊需求。如：國防戰(zhàn)備、災(zāi)難救助、偏遠(yuǎn)地區(qū)等無法得到有線網(wǎng)絡(luò)支持、或者某些只是臨時需要的通信環(huán)境。</p><p>

24、;　　考慮到Ad-Hoc網(wǎng)絡(luò)具有很多優(yōu)良特性，因此它的應(yīng)用領(lǐng)域需要進(jìn)一步去挖掘。比如：Ad-Hoc網(wǎng)絡(luò)可以用來擴(kuò)展現(xiàn)有蜂窩移動通信系統(tǒng)的覆蓋范圍，實現(xiàn)地鐵和隧道等場合的無線覆蓋，實現(xiàn)汽車和飛機等交通工具之間的通信，用于輔助教學(xué)和構(gòu)建未來的移動無線城域網(wǎng)和自組織廣域網(wǎng)等[3]。</p><p>　　第2章 AODV路由協(xié)議算法原理 </p><p>　　2.1 AODV路由協(xié)議概述<

25、/p><p>　　AODV路由協(xié)議是為ad-hoc網(wǎng)絡(luò)節(jié)點設(shè)計的，它提供對動態(tài)鏈路狀況的快速自適應(yīng)，處理開銷和存儲開銷低，網(wǎng)絡(luò)利用率低（路由開銷低）確定到達(dá)Ad-Hoc網(wǎng)絡(luò)內(nèi)的目的節(jié)點的單目標(biāo)傳輸路由。AODV路由協(xié)議明顯的特征是每個路由條目均使用一個目的節(jié)點序列號。使用目的節(jié)點序列號能夠確保路由是開環(huán)的。在選擇路由時，要求路由請求節(jié)點選擇序列號較大的那條路由。</p><p>　　AODV路

26、由協(xié)議定義了三種控制消息[4]：路由請求（Route Request, RREQ）、路由應(yīng)答（Route Reply, RREP）、路由錯誤（Route Err, RERR）。對于廣播消息并不是盲目發(fā)送，而是使用IP有限廣播地址（255.255.255.255），廣播幀通過使用IP頭部的TTL域來限定廣播幀的傳播范圍。</p><p>　　AODV協(xié)議是按需路由協(xié)議，即當(dāng)節(jié)點接收或者發(fā)送業(yè)務(wù)包時，才會進(jìn)行路由查找

27、和建立。在沒有接收到數(shù)據(jù)時主要用HELLO消息來保持相鄰節(jié)點的鏈接和系統(tǒng)維護(hù)，當(dāng)收到業(yè)務(wù)包數(shù)據(jù)時，在沒有路由的情況下，協(xié)議將會發(fā)起RREQ、RREP等控制消息來建立路由。</p><p>　　只要兩個通信連接的節(jié)點有相互到達(dá)的有效路由，則AODV路由協(xié)議不起作用。當(dāng)一個節(jié)點需要一條路由達(dá)到一個新目的節(jié)點時，該節(jié)點廣播一條RREQ控制消息來尋找一條到達(dá)目的節(jié)點的反向路由，通過給該RREQ控制消息，源節(jié)點回送一條單目

28、標(biāo)RREP控制消息來確定正向路由。如圖2-1中圖a所示，當(dāng)源節(jié)點A沒有到目的節(jié)點G的有效路由時，便啟動查找路由過程。源節(jié)點A廣播一個路由請求（RREQ），其中包含源節(jié)點地址、源節(jié)點序列號、目的節(jié)點地址、目的節(jié)點序列號和跳數(shù)等參數(shù)。中間節(jié)點收到B、C、D、E、F和J收到RREQ時，建立或更新到源節(jié)點A的反向路由，若中間節(jié)點回發(fā)路由應(yīng)答消息（RREP），并且RREQ幀沒有設(shè)置D標(biāo)志，則向上一跳節(jié)點回發(fā)應(yīng)答消息（RREP），其中包含源節(jié)點地址

29、、目的節(jié)點地址、目的節(jié)點序列號、跳數(shù)和生存時間參數(shù)，并經(jīng)若干中間節(jié)點到達(dá)源節(jié)點A.。否則繼續(xù)廣播RREQ消息，一直到目的節(jié)G收到RREQ后，向源節(jié)點A回發(fā)RREP。如圖2-1中圖b所示，經(jīng)過若干中間節(jié)點轉(zhuǎn)發(fā)后到源節(jié)點，確認(rèn)路由建立。其中RREQ沿多條路徑傳播，但RREP只沿最先到達(dá)的路徑（A、B和G）傳回源節(jié)點，即選擇時間度量最短的路</p><p>　　路由表項建立以后，路由中的每個節(jié)點都要執(zhí)行路由維護(hù)、路由表

30、管理。在維護(hù)路由表的過程中，當(dāng)路由不再被使用時，節(jié)點就會從路由表中刪除相應(yīng)項。同時，節(jié)點會通過HELLO消息來監(jiān)視一個活動路由下一跳節(jié)點的狀況，當(dāng)發(fā)現(xiàn)有鏈路斷開時，就用RERR控制消息來通知其他節(jié)點以及修復(fù)路由。每個節(jié)點都保留了一個“先驅(qū)列表（Precursor List）”來幫助完成錯誤報告。</p><p>　　圖a A到G的廣播查找過程(RREQ)</p><p>　　圖b RREP

31、建立確認(rèn)過程</p><p>　　圖2-1 正反向路由查找建立過程</p><p>　　在AODV路由協(xié)議中為了避免單向鏈路引起錯誤操作，協(xié)議引入了一個黑名單，把是單向鏈路的鄰居節(jié)點放入黑名單中。通過無法接收鏈路層應(yīng)答或者網(wǎng)絡(luò)應(yīng)答（例如RREP-ACK應(yīng)答）來檢測傳輸失敗，如果接收的RREQ分組是從黑名單節(jié)點中發(fā)送來的，就不予處理這些RREQ分組。</p><p>

32、　　2.2 AODV 路由協(xié)議使用的專業(yè)術(shù)語</p><p>　　Active route (有效路由)</p><p>　　通往目的節(jié)點的有效路由，只有有效路由可以用來轉(zhuǎn)發(fā)用戶數(shù)據(jù)分組。</p><p>　　Broadcast(廣播)</p><p>　　發(fā)送至IP地址為255.255.255.255的廣播報文。并且對它的轉(zhuǎn)發(fā)會有限制。但

33、有時將某些AODV協(xié)議幀廣播發(fā)送到全網(wǎng)。</p><p>　　Destination(目的節(jié)點地址)</p><p>　　用戶數(shù)據(jù)分組將被發(fā)送到的IP地址，其通過執(zhí)行AODV協(xié)議算法獲得。</p><p>　　Forwarding node(轉(zhuǎn)發(fā)節(jié)點)</p><p>　　轉(zhuǎn)發(fā)用戶數(shù)據(jù)分組的中間節(jié)點。沿著路由查找過程已經(jīng)建立好的路徑，轉(zhuǎn)發(fā)到距

34、離目的節(jié)點較近的下一跳節(jié)點。</p><p>　　Forwarding route (轉(zhuǎn)發(fā)路由)</p><p>　　為了從源節(jié)點發(fā)送用戶數(shù)據(jù)分組到目的節(jié)點而建立起來的一條路由。</p><p>　　Invalid route (無效路由)</p><p>　　已經(jīng)過期的路由，通過在路由表中的無效狀態(tài)來標(biāo)識。</p><p

35、>　　Source node(源節(jié)點)</p><p>　　發(fā)起AODV協(xié)議幀的節(jié)點。</p><p>　　Reverse route(反向路由)</p><p>　　為了將RREP協(xié)議幀從目的節(jié)點轉(zhuǎn)發(fā)至源節(jié)點，建立起的一條路由。</p><p>　　Sequence number(序列號)</p><p>　　

36、每幀源節(jié)點維護(hù)的一個數(shù)字，它幫助其他節(jié)點判斷信息的新舊程度。</p><p><b>　　2.3 幀的格式</b></p><p>　　2.3.1 RREQ協(xié)議幀的格式</p><p>　　AODV路由協(xié)議的路由請求RREQ消息的格式如圖2-2所示，對其組成域說明如下：</p><p>　　表2-1 RREQ幀組成域

37、說明</p><p>　　圖 2-2 RREQ幀結(jié)構(gòu)</p><p>　　2.3.2 RREP協(xié)議幀的格式</p><p>　　AODV路由協(xié)議的路由應(yīng)答RREP消息的格式如圖2-3所示，對其組成域說明如下：</p><p>　　表2-2 RREP幀組成域說明</p><p>　　圖2-3 RREP幀結(jié)構(gòu)</p

38、><p>　　RERR協(xié)議幀的格式</p><p>　　AODV路由協(xié)議的路由錯誤RERR消息的格式如圖2-4所示，對其組成域說明如下：</p><p>　　表2-3 RERR幀組成域說明</p><p>　　圖2-4 RERR幀結(jié)構(gòu)</p><p>　　2.4 AODV的操作</p><p>　

39、　2.4.1 序列號的維護(hù)</p><p>　　路由條目中的目的節(jié)點序列號越大就越能反映網(wǎng)絡(luò)當(dāng)前拓?fù)淝闆r。路由協(xié)議通過節(jié)點交互路由信息來建立和維護(hù)路由，目的節(jié)點序列號決定是否接收一個路由消息。在路由消息中目的節(jié)點序列號比自己所知序列號大，則根據(jù)該消息更新路由表；反之，不予處理。</p><p>　　在以下幾種情況下，節(jié)點增加自己的序列號：</p><p>　?。?

40、） 節(jié)點發(fā)起路由查找前，須增加序列號，該節(jié)點以前的反向路徑?jīng)_突；</p><p>　　（2） 目的節(jié)點響應(yīng)RREQ發(fā)起RREP前，目的節(jié)點須更新序列號，使序列號等于當(dāng)前序列號和RREQ中目的節(jié)點序列號較大值；</p><p>　?。?） 節(jié)點發(fā)現(xiàn)鄰節(jié)點的鏈路中斷或過期時，把相應(yīng)失效的路由條目中目的節(jié)點序列號加1。</p><p>　　節(jié)點在下列情況下可以改變路由表項

41、中目的節(jié)點的序列號：</p><p>　　節(jié)點本身是目的節(jié)點，并向其他站點提供了一條新的到自己的路由；</p><p>　　節(jié)點收到AODV協(xié)議幀，協(xié)議幀中有關(guān)于目的節(jié)點序列號較新信息；</p><p>　　通往目的節(jié)點的路徑過期或中斷。</p><p>　　2.4.2 路由表項和先驅(qū)表</p><p>　　當(dāng)節(jié)點收

42、到來自相鄰節(jié)點發(fā)送的AODV控制分組，或為特定目的節(jié)點建立、更新路由時，路由表中若如無該目的節(jié)點表項，則新建該表項。并在下列情況更新：</p><p>　　協(xié)議幀中的新序列號高與本機路由表中的目的節(jié)點序列號；</p><p>　　（2） 協(xié)議幀中序列號與路由表中序列號相等，但跳數(shù)+1小于路由表中跳數(shù)；</p><p>　?。?） 本機路由表項中的目的序列號未知。&l

43、t;/p><p>　　路由表項中生存字段由控制報文確定或初始化為ACTIVE-ROUTE-TIMEOUT。 </p><p>　　用路由進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時，它到源、目的節(jié)點和通往目的節(jié)點路徑的下一跳的有效路由生存期更新為大等于當(dāng)前加上ACTIVE-ROUTE-TIMEOUT。</p><p>　　節(jié)點維護(hù)有效路由表項的同時，還維護(hù)用來轉(zhuǎn)發(fā)報文的先驅(qū)列表。節(jié)點檢測到下一跳鏈

44、路丟失時，通知先驅(qū)列表。先驅(qū)列表是使用這條路由的所有鄰居節(jié)點。</p><p>　　2.4.3 產(chǎn)生路由請求</p><p>　　當(dāng)節(jié)點需到達(dá)某個目的節(jié)點而無可用路由時，則該節(jié)點發(fā)布一個RREQ。這種情況可能是：當(dāng)前節(jié)點對目的節(jié)點未知，或者它們之間路由過期或無效。</p><p>　　在RREQ協(xié)議幀中的目的序列號從路由表中復(fù)制并設(shè)成最后知道的目的節(jié)點序列號。如果

45、源節(jié)點無目的節(jié)點序列號則在RREQ中設(shè)置未知序列號標(biāo)記。RREQ協(xié)議幀中源節(jié)點序列號是節(jié)點自身序列號，填入RREQ之前要將其增加1。</p><p>　　在廣播RREQ以前，源節(jié)點在PATH-DISCOVERY-TIME時間內(nèi)緩存RREQ ID和RREQ源節(jié)點的IP地址。如果節(jié)點收到同樣的RREQ，不對此進(jìn)行處理</p><p>　　節(jié)點每秒種不因該產(chǎn)生多于RREQ-RATELIMIT次的

46、RREQ協(xié)議幀。廣播出一個RREQ以后，節(jié)點等待RREP。如果在NET-TRAVERSAL-TIME時間內(nèi)仍獲得路由，則節(jié)點廣播一個RREQ重新進(jìn)行路由查找過程，直到在最大TTL值時到達(dá)了RREQ-RETRIES次重傳。</p><p>　　2.4.4 處理和轉(zhuǎn)發(fā)路由請求</p><p>　　當(dāng)節(jié)點收到RREQ，首先建立或更新路由。并檢查是否在相應(yīng)時間內(nèi)，收到相同RREQ報文。如果收到，

47、則節(jié)點丟棄新收到的RREQ。相反則進(jìn)行以下處理：</p><p>　　首先，RREQ中跳數(shù)加1。然后，節(jié)點使用RREQ中的源節(jié)點序列號作為路由表項中的目的節(jié)點序列號，在路由表中建立或者更新到RREQ源節(jié)點的反向路由。在反向路由建立或更新的時候，反向路由表項需要進(jìn)行下列操作：</p><p>　?。?） 從RREQ中拷貝源節(jié)點序列號至路由表項中對應(yīng)的目的節(jié)點序列號；</p>&

48、lt;p>　　（2） 路由表中的下一跳設(shè)置為向它發(fā)出RREQ的節(jié)點；</p><p>　?。?） 跳數(shù)值等于接收到的RREQ協(xié)議幀的跳數(shù)字段中的值加1。</p><p>　　一個節(jié)點只有在下列兩種情況下才產(chǎn)生RREP：</p><p>　?。?） 節(jié)點本身是目的節(jié)點；</p><p>　?。?） 節(jié)點具有到目的節(jié)點的有效路由同時目的節(jié)點

49、序列號有效，并大于或者等于RREQ目的節(jié)點序列號，且RREQ中的“D”標(biāo)記沒有被設(shè)置。</p><p>　　如果上述任何一種情況滿足，則節(jié)點不再重新廣播RREQ。</p><p>　　2.4.5 產(chǎn)生路由應(yīng)答</p><p>　　如果節(jié)點收到到目的節(jié)點的路由請求，當(dāng)節(jié)點具有有效路由來滿足路由請求，或它本身就是目的節(jié)點，那么這個節(jié)點產(chǎn)生一個RREP的對應(yīng)節(jié)點字段。&

50、lt;/p><p>　　一旦建立了RREP，就把RREP單播至通往RREQ源節(jié)點的下一跳。隨著RREP逐步被轉(zhuǎn)發(fā)回發(fā)起RREQ協(xié)議幀的源節(jié)點，跳數(shù)也每中轉(zhuǎn)一次就增加1。這樣，當(dāng)RREP到達(dá)發(fā)起RREQ的節(jié)點，跳數(shù)就代表從目的節(jié)點到源節(jié)點的距離。</p><p>　　2.4.6 接收和轉(zhuǎn)發(fā)路由應(yīng)答</p><p>　　當(dāng)節(jié)點收到RREP協(xié)議幀，它首先建立或更新無有效序列

51、號的到上一跳的路由表項，然后RREP中的跳數(shù)值加1。隨后，RREP目的節(jié)點序列號和路由表中目的節(jié)點序列號進(jìn)行比較。此時現(xiàn)存的表項在下列情況下進(jìn)行更新：</p><p>　?。?） 現(xiàn)存路由表項中的序列號無效；</p><p>　?。?） 現(xiàn)存路由表項中的序列號有效，但RREP的目的節(jié)點序列號大于路由表項中的目的節(jié)點序列號；</p><p>　?。?） 序列號相同，但

52、是路由不再有效；</p><p>　?。?） 序列號相同，但RREP中標(biāo)明的“新跳數(shù)”小于路由表項中的跳數(shù)。</p><p>　　如果需要對到目的節(jié)點的表項進(jìn)行建立或者更新，路由表項的下一跳就設(shè)置為剛才發(fā)出RREP的節(jié)點。過期時間為當(dāng)前時間加上RREP協(xié)議幀的生存期。目的節(jié)點序列號為RREP協(xié)議幀中的目的節(jié)點序列號。</p><p>　　任何節(jié)點傳送RREP的時候，

53、把RREP被轉(zhuǎn)發(fā)到的下一跳節(jié)點加入到通往RREQ目的節(jié)點的路由表項的先驅(qū)列表中，對該先驅(qū)列表進(jìn)行更新。同時，往本節(jié)點發(fā)送RREP的上一跳節(jié)點也將加入到通往RREQ源節(jié)點的路由表項的先驅(qū)列表中。每個節(jié)點上用來轉(zhuǎn)發(fā)RREP的路由的生存期變?yōu)閧現(xiàn)有生存期，當(dāng)前時間+ACTIVE-ROUTE-TIMEOUT}兩者之間的最大值。</p><p>　　2.4.7 HELLO協(xié)議幀</p><p>　

54、　節(jié)點可通過廣播本地HELLO協(xié)議幀來提供連接信息。每HELLO-INTERVAL微妙內(nèi)，節(jié)點檢查最近的HELLO-INTERVAL是否發(fā)送了一個廣播報文（比如RREQ或者其它可以完成HELLO協(xié)議幀功能的幀），如果沒有發(fā)送，它會廣播一個TTL值為1的RREP，稱為HELLO協(xié)議幀。如果在連續(xù)發(fā)送3次HELLO協(xié)議，即3*HELLO-INTERVAL微妙內(nèi)節(jié)點仍沒有收到HELLO包，則認(rèn)為該節(jié)點與相應(yīng)鄰居節(jié)點的鏈路已經(jīng)斷開。并在鄰居節(jié)點

55、列表中刪除該鄰居。</p><p>　　2.4.8 RERR協(xié)議幀，路由過期和路由刪除</p><p>　　RERR協(xié)議幀可以廣播，可以是單播，或者交互式的單播至所有不可達(dá)節(jié)點。節(jié)點每一秒鐘不應(yīng)該產(chǎn)生超過RERR-RATELIMIT個RERR協(xié)議幀。</p><p>　　在RERR中不可達(dá)目的節(jié)點列表中的一些節(jié)點可能會被鄰居使用，所以需要發(fā)送一個新的RERR幀。新

56、的RERR幀中的不可達(dá)目的節(jié)點列表是有滿足下面條件的節(jié)點組成：節(jié)點在已經(jīng)建立的不可達(dá)目的節(jié)點鏈表中，并且這個節(jié)點在本機路由表中具有非空的先驅(qū)列表。</p><p>　　應(yīng)收到RERR的鄰居節(jié)點是：存在于新建立的RERR節(jié)點的先驅(qū)列表中。如果只有一個鄰居需要接收RERR，則RERR應(yīng)該單播至目的節(jié)點，否則將RERR協(xié)議幀發(fā)送到本地廣播地址（目的節(jié)點IP地址=255.255.255.255，TTL=1）。RERR報文

57、中的DestCount自動指出報文中包含的不可達(dá)目的節(jié)點的數(shù)目。</p><p>　　2.4.9 接口信息</p><p>　　AODV須知道分組從哪個網(wǎng)絡(luò)接口中來，當(dāng)從一個新鄰居節(jié)點收到分組時，須在路由表中記錄下這個鄰居節(jié)點及其它對應(yīng)的網(wǎng)絡(luò)接口。同樣發(fā)現(xiàn)到某個新的目的節(jié)點的路由時，須在對應(yīng)的路由表項中記錄下對應(yīng)的網(wǎng)絡(luò)接口。</p><p>　　當(dāng)存在多個網(wǎng)絡(luò)接口

58、的時候，節(jié)點在所有使用AODV協(xié)議的接口上廣播RREQ幀。只有一種情況除外：在這個接口上的所有鄰居節(jié)點已經(jīng)收到了這個RREQ則不在這個接口上廣播[6]。</p><p>　　第3章 Linux操作系統(tǒng)的網(wǎng)絡(luò)功能 </p><p>　　本設(shè)計中，AODV路由協(xié)議是在Linux操作系統(tǒng)上實現(xiàn)的。在實現(xiàn)方案中，充分利用了操作系統(tǒng)自身的特點。因此，在介紹設(shè)計方案前先對Linux操作系統(tǒng)，進(jìn)行總體

59、說明。</p><p>　　3.1 Linux操作系統(tǒng)的總體介紹</p><p>　　Linux操作系統(tǒng)是從Minix 操作系統(tǒng)發(fā)展起來的一種類Unix操作系統(tǒng)。后來發(fā)展成為一個多用戶開源操作系統(tǒng)。由于其源代碼開放性、廉價性、安全性以及優(yōu)越的性能，現(xiàn)在得到了越來越廣泛的應(yīng)用，尤其是在服務(wù)器操作系統(tǒng)領(lǐng)域。</p><p>　　從操作系統(tǒng)的功能角度來看，Linux的核

60、心由五大部分組成：進(jìn)程管理、存儲管理、文件管理、設(shè)備管理和網(wǎng)絡(luò)管理。</p><p>　　3.2 Linux操作系統(tǒng)網(wǎng)絡(luò)功能的實現(xiàn)</p><p>　　本設(shè)計在實現(xiàn)的時候，主要是利用Linux的網(wǎng)絡(luò)系統(tǒng)。從整體角度考慮Linux網(wǎng)絡(luò)系統(tǒng)基本可以分為硬件層/數(shù)據(jù)鏈路層、IP層、INER Socket層、BSD Socket層和應(yīng)用層五個部分。其中在Linux內(nèi)核中包括了前四個部分，在應(yīng)用層

61、和BSD Socket層之間的應(yīng)用程序接都以4.4BSD為模板。INET Socket 層實現(xiàn)比IP協(xié)議層次高，實現(xiàn)對IP分組排序、控制網(wǎng)絡(luò)系統(tǒng)效率等功能。圖3-1說明了Linux基于TCP/IP協(xié)議的網(wǎng)絡(luò)系統(tǒng)體系結(jié)構(gòu)[7]。</p><p>　　從應(yīng)用層到網(wǎng)絡(luò)設(shè)備接都硬件之間的數(shù)據(jù)流程走向的觀點來分析，應(yīng)用曾中的操作對象是socket文件描述符，通過文件系統(tǒng)定義的通用接口，使用系統(tǒng)調(diào)用從用戶空間切換到內(nèi)核空間。

62、對socket文件描述符的操作傳遞給對應(yīng)的BSD Socket操作，從而進(jìn)入到BSD Socket層的操作。在BSD Socket層中，操作的對象是socket結(jié)構(gòu)，每一個這樣的結(jié)構(gòu)對應(yīng)的是一個網(wǎng)絡(luò)連接，通過網(wǎng)絡(luò)地址族的不同來區(qū)分不同的操作方法，判斷是否應(yīng)該進(jìn)入到INET Socket層，這一層的數(shù)據(jù)存放在msghdr結(jié)構(gòu)的變量中，在INET Socket層，根據(jù)建立連接的類型，分成面向無連接和連接兩種類型，這是區(qū)分TCP和UDP協(xié)議的

63、主要原則。在這一層中的操作對象是sock類型的數(shù)據(jù)，而數(shù)據(jù)存放在sk-buff結(jié)構(gòu)中。從INER Socket層到IP層，主要是路由過程，發(fā)送時根據(jù)發(fā)送的目標(biāo)地址確定需要使用的網(wǎng)絡(luò)設(shè)備接口和下一跳的主機地址；接收數(shù)據(jù)的時候需要在IP層判斷該數(shù)據(jù)分組是要發(fā)送給上一層協(xié)議還是需要做一個IP轉(zhuǎn)發(fā)，將數(shù)據(jù)傳遞給下一臺機器。從IP層到硬件層，也就是到網(wǎng)絡(luò)接口設(shè)備驅(qū)動程序，即是有關(guān)硬件的控制方法，其驅(qū)</p><p>　　圖

64、3-1 Linux基于TCP/IP協(xié)議的網(wǎng)絡(luò)系統(tǒng)體系結(jié)構(gòu)</p><p>　　3.3 Linux操作系統(tǒng)路由轉(zhuǎn)發(fā)功能的實現(xiàn)</p><p>　　在Linux的路由功能子系統(tǒng)中，主要保存了三種與路由相關(guān)的數(shù)據(jù)。第一種是在物理上和本機相連接的主機地址信息表，第二種是保存了在網(wǎng)絡(luò)訪問中判斷網(wǎng)絡(luò)地址應(yīng)該走什么路由的數(shù)據(jù)表，第三種是保存最新使用過的路由信息的緩存信息數(shù)據(jù)表。第一種被稱為相鄰表，由n

65、eigh-table數(shù)據(jù)結(jié)構(gòu)的鏈表表示，以neighbor結(jié)構(gòu)為節(jié)點。第二種表是保存路由規(guī)則，用fib-table數(shù)據(jù)結(jié)構(gòu)的鏈表表示。第三中表被稱作路由緩存表，用rtable數(shù)據(jù)結(jié)構(gòu)的鏈表表示[8]。</p><p>　　Linux系統(tǒng)中路由采取的策略是，先到路由緩存表中查找表項，如果能夠查找到，就直接將對應(yīng)的一項取出來作為路由的規(guī)則；如果找不到，那么就根據(jù)fib-table鏈表中的內(nèi)容，利用特定規(guī)則換算出來，并

66、且在路由緩存中將這一項添加進(jìn)去。</p><p>　　Linux操作系統(tǒng)中，路由功能一般分為兩個部分。一部分駐留在操作系統(tǒng)內(nèi)核中，這部分的認(rèn)識是基于表驅(qū)動的進(jìn)程，根據(jù)路由表的信息，設(shè)定正確的地址，將數(shù)據(jù)分組發(fā)往對應(yīng)的網(wǎng)絡(luò)接口，這部分稱為“分組轉(zhuǎn)發(fā)功能模塊”。另一部分是實現(xiàn)路由協(xié)議的邏輯計算，根據(jù)與其它主機交換信息，計算出到其它節(jié)點的正確路由，實現(xiàn)真正的尋找路由和維護(hù)路由的功能，這部分稱為“分組尋找路由功能模塊”。

67、</p><p>　　分組轉(zhuǎn)發(fā)功能模塊在內(nèi)核中基于一個內(nèi)核路由表來工作，每次發(fā)送一個數(shù)據(jù)分組，都要向內(nèi)核路由表查詢，取得對應(yīng)的下一跳鄰居節(jié)點的地址和對應(yīng)的網(wǎng)絡(luò)接口。內(nèi)核路由表一般由分組尋路由功能模塊來操作維護(hù)。在查找內(nèi)核路由表的時候，根據(jù)路由表項的最佳匹配原則進(jìn)行轉(zhuǎn)發(fā)。如果找不到匹配的路由表項，則按照缺省路由發(fā)送，一般是將網(wǎng)關(guān)作為缺省路由的下一跳節(jié)點。如果缺省路由不存在，則當(dāng)數(shù)據(jù)分組在找不到匹配的路由表項的時候，

68、操作系統(tǒng)將簡單都把這個數(shù)據(jù)分組拋棄[9]。</p><p>　　分組尋路功能模塊負(fù)責(zé)尋路，它和其他節(jié)點交換信息，采用一定的路由協(xié)議算法來計算了維護(hù)內(nèi)核路由表。Linux操作系統(tǒng)中自帶的分組尋路功能模塊在內(nèi)核空間實現(xiàn)。</p><p>　　第4章 AODV路由協(xié)議的實現(xiàn)</p><p>　　4.1 AODV路由協(xié)議實現(xiàn)的框架結(jié)構(gòu)</p><p&

69、gt;　　與傳統(tǒng)的有線路由協(xié)議相比較，實現(xiàn)AODV協(xié)議會有很多地方不同。</p><p>　　本設(shè)計對AODV路由協(xié)議實現(xiàn)的方案中，將盡可能的利用Linux操作系統(tǒng)現(xiàn)有的路由機制。實現(xiàn)方案不改變Linux操作系統(tǒng)的分組轉(zhuǎn)發(fā)功能模塊，而是利用它的分組轉(zhuǎn)發(fā)功能模塊的實現(xiàn)機制，用自己的分組尋路功能模塊來代替Linux操作系統(tǒng)現(xiàn)有的分組尋路功能模塊[10]。</p><p>　　方案實現(xiàn)的基本思路

70、是：用一個接收模塊虛擬一個節(jié)點，將缺省的路由表項指向這個節(jié)點，從而由這個接收模塊發(fā)起路由查找請求?？紤]到程序的移植性和擴(kuò)展的方便性，方案采用在用戶空間實現(xiàn)分組尋路功能模塊。</p><p>　　本AODV路由協(xié)議的原理性算法設(shè)計擬在Linux2.4操作系統(tǒng)平臺上實現(xiàn)，Linux2.4分為三個主要部分：第一部分是接口部分，第二部分是AODV路由算法部分，第三部分是內(nèi)核模塊部分。其中，前兩個部分是在用戶空間實現(xiàn)的，第

71、三部分是內(nèi)核實現(xiàn)的。其中用戶空間和內(nèi)核空間各有一個路由表，在用戶空間路由表建立的同時通過相應(yīng)的系統(tǒng)調(diào)用在內(nèi)核空間建立路由表。</p><p>　　這三個部分的功能分別是[11]：</p><p><b>　　第一部分：接口部分</b></p><p>　　接口部分的主要功能是利用Linux系統(tǒng)提供的應(yīng)用程序接口，為實現(xiàn)AODV路由協(xié)議提供所需要

72、的各種信息和服務(wù)。例如：在現(xiàn)實方案里當(dāng)用戶分組到達(dá)時，首先查詢內(nèi)核路由表，如果數(shù)據(jù)分組的目的節(jié)點在內(nèi)核的路由表中已經(jīng)存在，并且路由表項有效，則由Linux內(nèi)核中的發(fā)送機制接發(fā)送，不發(fā)起AODV路由查找過程。如果數(shù)據(jù)分組的目的節(jié)點地址在內(nèi)核路由表中不存在，通過接口部分從內(nèi)核空間進(jìn)入用戶空間進(jìn)行路由查找建立，路由建立后，如果AODV成功查找出路徑，則要利用ioctl系統(tǒng)調(diào)用將這條路由表的時間，記錄在時間鏈表中，接著netlink-socke

73、t通知內(nèi)核接收該數(shù)據(jù)包以備進(jìn)行下步處理。如果沒有找到路徑，則將緩存的數(shù)據(jù)分組釋放，通知用戶程序出錯。</p><p>　　第二部分：AODV路由算法部分</p><p>　　從第一部分提取出用戶分組數(shù)據(jù)的目的地址，就可有足夠的信息來進(jìn)行AODV路由查找。這部分涉及到RREQ的廣播，RREP,RERR幀的處理等等。這部分功能就是實現(xiàn)AODV路由協(xié)議，基本不涉及和Linux的交互性問題。AOD

74、V各種數(shù)據(jù)幀（控制包）的接受和發(fā)送可以利用普通的UDP套接口實現(xiàn)，根據(jù)AODV協(xié)議，套接口使用的是UDP協(xié)議并在654端口進(jìn)行收發(fā)。每當(dāng)收發(fā)一個幀，都需要對對應(yīng)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新。在各種數(shù)據(jù)結(jié)構(gòu)中，最重要的是一個時間列隊。各種AODV時間的管理用了一個時間列隊，每個時間發(fā)生的時候，都需要更新這個列隊。這個列隊記錄了這個事件的超時時間。插入時間類隊的時候，根據(jù)要求發(fā)生時間在前的事件插在列隊的前面。</p><p>

75、<b>　　第三部分：內(nèi)核部分</b></p><p>　　在Linux 內(nèi)核設(shè)計中，為了擴(kuò)展內(nèi)核功能，方便的加載各種驅(qū)動程序，設(shè)計了內(nèi)核可加載模塊功能。用戶可以通過這個功能想內(nèi)核中加入新的功能模塊[12]。</p><p>　　這個部分是相對獨立的一部分，在內(nèi)核空間利用加載模塊技術(shù)實現(xiàn)。這里主要介紹內(nèi)核部分的時間提取和超時處理。</p><p&g

76、t;　　無線自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)因為是動態(tài)變化的，所以它的路由協(xié)議都有一個時間要求，每一條路徑都有一個有效時間，如果超過這個時間路徑?jīng)]有更新就需要將這條路由標(biāo)記為不可用。AODV路由協(xié)議也一樣。它要求記錄每條路徑的最后使用時間，如果空閑時間超過一點時間，就需要將這條路由標(biāo)記為不可用。</p><p>　　在AODV路由協(xié)議中有多種超時管理，如：路由超時管理、路由刪除超時管理以及RREQ包超時管理等。在本設(shè)計中，擬由軟

77、件實現(xiàn)所有超時管理，具體分為兩個隊列：等待隊列和超時隊列，例如：每個RREQ包都設(shè)有相應(yīng)等待時間，并且這些包都處于等待隊列中，然后依次將包的等待時間與當(dāng)前時間對比。如果小于當(dāng)前時間（即：等待超時），則把包從等待隊列中取出放入超時隊列，并執(zhí)行相應(yīng)的超時處理函數(shù)；反之則繼續(xù)在該隊列中等待。</p><p>　　綜上所述AODV協(xié)議實現(xiàn)的操作流程可以表示如圖4-1：</p><p>　　圖4-1

78、 AODV路由協(xié)議實現(xiàn)的操作流程 </p><p>　　4.2 AODV協(xié)議實現(xiàn)的難點及其解決方法</p><p>　　相比傳統(tǒng)的有線路由協(xié)議或者主動路由協(xié)議，實現(xiàn)按需路由協(xié)議會遇到更多的問題。實現(xiàn)AODV主要困難有以下幾點[13]：</p><p>　　（1） 如何記錄每條路由的最后使用時間；</p><p>　?。?） 如何在用戶空間和

79、內(nèi)核空間之間傳送數(shù)據(jù)；</p><p>　?。?） 對內(nèi)核路由表的操作。</p><p>　　4.2.1 記錄每條路由的最后使用時間</p><p>　　無線自組網(wǎng)的按需路由協(xié)議通常自己保存有一個路由表，這個路由表的每一項都有一個定時器與之相關(guān)聯(lián)。當(dāng)定時器到期以后，以為著路由表項過期了，則應(yīng)該將這個路由表項刪除或者標(biāo)記為過期不可用。AODV路由協(xié)議需要記錄每條路徑

80、的最后使用時間，而問題是，系統(tǒng)自身并沒有提供每條路徑的最后使用時間給用戶。</p><p>　　為了提取每條路由的最后使用時間，本設(shè)計使用了Linux操作系統(tǒng)的掛鉤函數(shù)，Netfilter提供了一個分組過濾子系統(tǒng)，在該系統(tǒng)中，Ipv4定義了五個掛鉤點[14]。內(nèi)核模塊可在這些掛鉤點上注冊自己的函數(shù)，這樣當(dāng)某個數(shù)據(jù)分組被傳遞給Netfilter框架時，內(nèi)核能檢測是否有任何模塊對該協(xié)議和掛鉤函數(shù)進(jìn)行了注冊。若注冊了，

81、則調(diào)用該模塊注冊時使用的回調(diào)函數(shù)。這五個掛鉤的結(jié)構(gòu)如圖 4-1 所示：</p><p>　　--->[1]--->[ROUTE]--->[3]--->[5]---></p><p>　　| ^</p><p>　　Local |</p>&l

82、t;p>　　| [ROUTE]</p><p>　　v |</p><p>　　[2] [4]</p><p>　　| ^</p><p>　　|

83、 |</p><p>　　v |</p><p>　　圖4-1 Linux系統(tǒng)中的五個掛鉤點</p><p>　　4.2.2 用戶空間和內(nèi)核空間的信息交互實現(xiàn)</p><p>　　為了實現(xiàn)用戶空間和內(nèi)核空間的信息交互，本設(shè)計利用了Linux 2.4內(nèi)核的防火墻Netfilter提供一個分組

84、過濾子系統(tǒng)并為Ipv4定義了五個鉤子。它們分別是：</p><p>　?。?） NF-IP-PRE-ROUTING[1]</p><p>　　（2） NF-IP-LOCAL-IN[2]</p><p>　?。?） NF-IP-FORWARD[3]</p><p>　　（4） NF-IP-LOCAL-OUT[4]</p><

85、p>　　（5） NF-IP-POST-ROUTING[5]</p><p>　　內(nèi)核模塊可以在這五個掛鉤點的任何一個點注冊掛鉤函數(shù)，對數(shù)據(jù)分組進(jìn)行檢查過濾，并且記錄下路徑最后使用時間[15]。如圖4-1所示。</p><p>　　數(shù)據(jù)報從左邊進(jìn)入系統(tǒng)，進(jìn)行IP校驗以后，數(shù)據(jù)報經(jīng)過第一個鉤子函數(shù)NF-IP-PRE-ROUTING[1]進(jìn)行處理；然后就進(jìn)入路由代碼，其決定該數(shù)據(jù)包是需要轉(zhuǎn)

86、發(fā)還是發(fā)給本機的；若該數(shù)據(jù)包是發(fā)被本機的，則該數(shù)據(jù)經(jīng)過鉤子函數(shù)NF-IP-LOCAL-IN[2]處理以后然后傳遞給上層協(xié)議；若該數(shù)據(jù)包應(yīng)該被轉(zhuǎn)發(fā)則它被NF-IP-FORWARD[3]處理；經(jīng)過轉(zhuǎn)發(fā)的數(shù)據(jù)報經(jīng)過最后一個鉤子函數(shù)NF-IP-POST-ROUTING[5]處理以后，再傳輸?shù)骄W(wǎng)絡(luò)上。</p><p>　　本地產(chǎn)生的數(shù)據(jù)如果是業(yè)務(wù)包經(jīng)過鉤子函數(shù)NF-IP-LOCAL-OUT [4]處理后，進(jìn)入用戶空間并接收

87、該數(shù)據(jù)包；然后查找用戶空間層路由表項，查詢是否有到目的節(jié)點路由，如果存在該路由，則通過netlink socket通知內(nèi)核接受該數(shù)據(jù)包，使包順利通過鉤子[4]進(jìn)而進(jìn)行內(nèi)核對數(shù)據(jù)包的后續(xù)處理工作，如路由等；反之一旦路由表中不存在該路徑，立即將該數(shù)據(jù)包進(jìn)行排隊，同時應(yīng)該通過發(fā)送AODV控制包進(jìn)行路由查找，如：發(fā)送RREQ等待目的節(jié)點發(fā)回RREP給源節(jié)點在用戶空間建立路由，隨后利用ioctl()在內(nèi)核空間建立內(nèi)核路由表，最后同樣將數(shù)據(jù)包通過n

88、etlink-socket通知內(nèi)核接受該數(shù)據(jù)包以備進(jìn)行下步處理。</p><p>　　4.2.3 對內(nèi)核路由表的操作</p><p>　　在實現(xiàn)方案中，將不修改Linux自身的分組路由轉(zhuǎn)發(fā)功能。因此需要做的是：根據(jù)分組尋路模塊計算的路由結(jié)果，修改Linux內(nèi)核中的路由表。在實現(xiàn)方案中，有兩個路由表，一個是內(nèi)核的Linux自帶的稱為內(nèi)核路由表；另外一個是自己在用戶層自己建立的，稱為AODV

89、路由表[16]。</p><p>　　內(nèi)核路由表是Linux自身的分組路由轉(zhuǎn)發(fā)模塊工作的基礎(chǔ)。AODV路由表結(jié)構(gòu)是根據(jù)AODV協(xié)議構(gòu)造的記錄了每條路由的目的序列號、到目的節(jié)點的跳數(shù)等信息，分組路由尋路模塊需要利用這些信息，來進(jìn)行正確的路由查找。程序?qū)τ脩魧拥穆酚杀矶x了各種操作函數(shù)，因為分組路由尋路模塊和AODV路由表都是在用戶空間時間的，它們之間可以很方便的進(jìn)行信息交互。對內(nèi)核路由表則不一樣，它們之間涉及內(nèi)核和

90、用戶空間之間的交互，不能直接交換信息。因此程序利用了Linux的控制函數(shù)ioctl來操作Linux內(nèi)核路由表。同樣也利用ioctl來獲取網(wǎng)絡(luò)接口的信息。它能獲取網(wǎng)絡(luò)接口的地址、是否支持廣播、是否支持多播等功能。在獲取網(wǎng)絡(luò)接口信息的時候，ioctl函數(shù)使用了一個叫做ifconf的數(shù)據(jù)結(jié)構(gòu)，而ifconf又使用了一個ifreq的數(shù)據(jù)結(jié)構(gòu)。每個網(wǎng)絡(luò)接口用一個ifreq表示，在這個結(jié)構(gòu)里面包含了網(wǎng)絡(luò)接口的名字、地址等信息[17]。</p&

91、gt;<p>　　4.3 參數(shù)的設(shè)置</p><p>　　在程序中使用的協(xié)議參數(shù)值見下表[18]：</p><p>　　表4-1 主要協(xié)議參數(shù)值</p><p>　　4.4 路由協(xié)議中的主要流程</p><p>　　4.4.1 主程序工作流程</p><p>　　程序開始時,首先讀取程序可執(zhí)行文件

92、名。并對相應(yīng)鏈表、堆棧、套接字等部分初始化。將相應(yīng)的包設(shè)置為可讀文件參數(shù)組，并開始發(fā)送HELLO包維護(hù)鏈路連接。然后，判斷可讀文件標(biāo)示符，通過文件標(biāo)示符判斷文件類型，如果該文件是業(yè)務(wù)包，則被packet-input程序調(diào)用。將該業(yè)務(wù)包根據(jù)路由表信息發(fā)送到其目的地址，此時如果內(nèi)核路由表中無相應(yīng)路由或路由無效，則應(yīng)將包排隊并發(fā)起控制消息查找路由，。一旦查找路由失敗，則丟棄該業(yè)務(wù)包。如果該文件是控制包，則被net –socket調(diào)用并進(jìn)行路由

93、查找、修復(fù)、發(fā)送錯誤信息等[19]。其原理性算法流程如圖4-2。</p><p>　　圖4-2 主程序工作流程圖</p><p>　　4.4.2 RREQ幀的接收處理流程</p><p>　　在整個RREQ幀的接收處理流程中，當(dāng)接收到RREQ時，首先判斷在PATH-DISCOVERY-TIME時間內(nèi)是否已經(jīng)發(fā)送了一個RREQ，如果發(fā)送了就則將包丟棄。(每發(fā)送一個R

94、REQ后都會將其ID緩存到rreq-id-queue中，RREQ ID和源節(jié)點的IP地址聯(lián)合起來標(biāo)志一個獨一無二的RREQ報文)。反之，則將RREQ的ID和跳數(shù)加1并緩存到rreq-id-queue中。接下來，通過RREQ更新正反向路由.到源節(jié)點的反向路由表項的生存期設(shè)置為{現(xiàn)有生存期，MinimalLifeTime}兩者之中的最大值。（MinimalLifeTime = （當(dāng)前時間+2*NET-TRAVERSAL-TIME＋2*跳數(shù)*

95、NODE-TRAVERSAL-TIME））。</p><p>　　接著，在路由表中查找目的節(jié)點是否時是本機地址或本機有到目的節(jié)點的路由，如果是則產(chǎn)生RREP并發(fā)送到發(fā)起RREQ的節(jié)點.如果目的節(jié)點不是本機地址則轉(zhuǎn)發(fā)該RREQ。如果收到RREQ協(xié)議幀的IP報文頭部的TTL值小于1，則增加TTL的值直到達(dá)到最大TTL值時并嘗試了RREQ-RETRIES次，卻沒有收到RREP，則丟棄所有發(fā)往對應(yīng)目的節(jié)點的用戶數(shù)據(jù)分組。

96、為防止網(wǎng)絡(luò)用塞，每次重傳RREQ的時候，等待RREP的超時時間將在上一次的時間基礎(chǔ)上乘2。其具體流程圖如4-3。</p><p>　　圖4-3 RREQ幀的接收處理流程圖</p><p>　　4.4.3 HELLO幀的接收處理流程</p><p>　　在整個HELLO幀的接收處理流程中，當(dāng)接收到HELLO時，首先查找鄰居列表，看是否存在這個鄰居，如果沒有則添加這個

97、鄰居。然后查找是否有到這個鄰居的路由表項，如果沒有就建立一條這樣的路由表項（分別在用戶空間和內(nèi)核空間路由表中建立）。這條新建立的路由如果不被其他活動路由使用，則新建到鄰居節(jié)點的路由的先驅(qū)列表將為空。當(dāng)路由表項的先驅(qū)列表為空時，這條路由過期無效的時候，將不出發(fā)RERR幀。如果到這個鄰居節(jié)點的路由已經(jīng)存在，那么應(yīng)該增加這條路由的生存期，生存時間至少增加為ALLOWED-HELLO-LOSS*HELLO-INTERVAL。到鄰居的路由如果存在

98、，必須包含HELLO協(xié)議幀中的最新目的節(jié)點序列號（在現(xiàn)在的序列號和HELLO協(xié)議幀中的序列號之間取最大值）[20]。其具體流程圖如4-4。</p><p>　　圖4-4 HELLO幀的接收處理流程圖</p><p>　　4.4.4 RREP幀的接收處理流程</p><p>　　在整個RREP幀的接收處理流程中，當(dāng)接收到RREP時，首先將跳數(shù)加1，判斷是否是本機發(fā)出

99、的，如果不是接著判斷是否是RREQ的發(fā)起節(jié)點，事件不為真則查找反向路由將RREP轉(zhuǎn)發(fā)到RREQ的發(fā)起節(jié)點，反之，則完成路由查找，</p><p>　　如果需要對到目的節(jié)點的表項進(jìn)行建立或者更新，路由表項的下一跳就設(shè)置為剛才發(fā)出RREP的節(jié)點。過期時間為當(dāng)前時間加上RREP協(xié)議幀的生存期。目的節(jié)點序列號為RREP協(xié)議幀中的目的節(jié)點序列號。</p><p>　　任何節(jié)點傳送RREP的時候，把R

100、REP被轉(zhuǎn)發(fā)到的下一跳節(jié)點加入到通往RREQ目的節(jié)點的路由表項的先驅(qū)列表中，對該先驅(qū)列表進(jìn)行更新。同時，往本節(jié)點發(fā)送RREP的上一跳節(jié)點也將加入到通往RREQ源節(jié)點的路由表項的先驅(qū)列表中。每個節(jié)點上用來轉(zhuǎn)發(fā)RREP的路由的生存期（即rrep.dest-ip路由的生存時間）變?yōu)閧現(xiàn)有生存期，當(dāng)前時間+ACTIVE-ROUTE-TIMEOUT}兩者之間的最大值。其具體流程圖如4-5。</p><p>　　圖4-5 R

101、REP幀的接收處理流程圖</p><p>　　4.4.5 RERR幀的接收處理流程</p><p>　　在整個RERR幀的接收處理流程中，當(dāng)接收到RERR時，首先，查找其不可達(dá)目的地址的反向路由表項是否找到，如果找到，則更新路由表項并刪除內(nèi)核中對應(yīng)的路由表項，按照如下步驟進(jìn)行更新：</p><p>　?。?） 路由表項的目的節(jié)點序列號如果存在并且有效，目的序列好加

102、1，對于如果鄰居收到一個關(guān)于一條或多條有效路由的RERR協(xié)議幀，目的序列號從收到的RERR協(xié)議幀中拷貝到路由表項；</p><p>　　（2） 將路由表項標(biāo)記為無效；</p><p>　　（3） 路由表項的生www.lunwenxf.com 論文學(xué)府存期字段更新為當(dāng)前時間加上DELETE-PERIOD。在這個時間以前，表項不應(yīng)該被刪除。</p><p>　　當(dāng)先驅(qū)列

103、表不為空時將不可達(dá)目的節(jié)點加入到不可達(dá)節(jié)點列表中。接著，判斷不可達(dá)目的節(jié)點是否游歷完。最后發(fā)送RERR。其具體流程圖如4-6。</p><p>　　圖4-6 RREQ幀的接收處理流程圖</p><p>　　4.4.6 生成RREQ幀的函數(shù)流程</p><p>　　在整個RREQ幀的接收處理流程中，當(dāng)接收到RREQ時，首先在事件時間隊列中查找是否存在到同一目的的RR

104、EQ，如果存在則不與處理，反之則在內(nèi)存中分配RREQ內(nèi)存空間并設(shè)置相應(yīng)的域。在發(fā)送前將設(shè)置好的RREQ的ID和源地址IP緩存起來（即在rreq-id-queue列隊中記錄這個RREQ幀）并將此事件插入到事件時間列隊中（即開始記時）。最后廣播RREQ。其具體流程圖如4-7。</p><p>　　圖4-7 生成RREQ幀的函數(shù)流程圖</p><p>　　4.4.7 生成RREP幀的函數(shù)流程&

105、lt;/p><p>　　在整個RREQ幀的接收處理流程中，當(dāng)接收到RREQ時，首先判斷該節(jié)點是否是RREQ的目的節(jié)點，如果是其目的節(jié)點，假如RREQ報文中的序列號等于目的節(jié)點本身的序列號加1，則節(jié)點必須把自己的www.lunwenxf.com 論文學(xué)府序列號再加1（RREQ報文中的序列號大于目的節(jié)點維護(hù)的自身序列號的情況：某節(jié)點因為檢測到同往目的節(jié)點的鏈路中斷，將目的節(jié)點序列號加1，然后重發(fā)路由請求）。否則，目的節(jié)點

106、在產(chǎn)生RREP協(xié)議幀之前不改變它的序列號。目的節(jié)點將它自己的序列號放入RREP的目的節(jié)點序列號字段當(dāng)中，并把跳數(shù)字段值設(shè)置為0。</p><p>　　目的節(jié)點拷貝MY-ROUTE-TIMEOUT的值到RREP的生存期字段，每個字節(jié)可以在適度限制的情況下重新配置MY-ROUTE-TIMEOUT的值。</p><p>　　如果是中間節(jié)點產(chǎn)生路由應(yīng)答并且G為1，它將拷貝已知的目的節(jié)點序列號至RR

107、EP協(xié)議幀中的目的節(jié)點序列號字段。中間節(jié)點通過把上一跳節(jié)點放入轉(zhuǎn)發(fā)路由表項的先驅(qū)列表中來更新轉(zhuǎn)發(fā)路由表項。上一跳節(jié)點指的是向它發(fā)送RREQ的節(jié)點（即反向路由表）。 中間節(jié)點將它目的節(jié)點的跳數(shù)放入RREP中的跳數(shù)字段。RREP的生存期字段由路由表項的過期時刻減去當(dāng)前時刻得出。其具體流程圖如4-8。</p><p>　　圖4-8 生成RREP幀的函數(shù)流程圖</p><p>　　4.4.8 生

108、成RERR幀的函數(shù)流程</p><p>　　在三種情況下發(fā)起RERR協(xié)議幀過程：</p><p>　?。?） 如果點檢測到一條正在傳輸數(shù)據(jù)的活動路由的下一跳鏈路斷開；</p><p>　?。?） 如果節(jié)點收到去往某個目的節(jié)點的用戶數(shù)據(jù)分組，而節(jié)點沒有到該目的節(jié)點的有效路由并且沒有在進(jìn)行修復(fù)；</p><p>　?。?）如果鄰居收到一個關(guān)于一條

109、或多條有效路由的RERR協(xié)議幀。</p><p>　　對情況（1），節(jié)點首先產(chǎn)生一張不可達(dá)目的節(jié)點的列表，包含不可達(dá)鄰居和在本地路由表中使用不可達(dá)鄰居作為下一跳的其他任何目的節(jié)點。對于情況（2）只有一個不可達(dá)目的節(jié)點，就是無法發(fā)送的用戶數(shù)據(jù)分組的目的節(jié)點。對于情況（3）不可達(dá)目的節(jié)點列表中的節(jié)點應(yīng)該滿足下面條件：包含RERR中，而且這些不可達(dá)目的節(jié)點在本地路由表中存在著對應(yīng)的路由表項，路由表項的下一跳是所收到的R