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

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

2、　學(xué)生學(xué)號(hào)：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è)計(jì)</p><p>　　摘要：Ad-hoc無線自組織網(wǎng)絡(luò)技術(shù)是近來出現(xiàn)的不同于傳統(tǒng)網(wǎng)絡(luò)的一種新技術(shù),受到國(guó)內(nèi)外的廣泛關(guān)注，其路由技術(shù)是無線自組網(wǎng)的一個(gè)重要研究領(lǐng)域。為適應(yīng)不同的應(yīng)用場(chǎng)合，已出現(xiàn)了諸如AODV等針對(duì)性較強(qiáng)的路由協(xié)議。</p><p>　　本文根據(jù)AODV路由協(xié)議的規(guī)范，

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

13、><p>　　2.4.4 處理和轉(zhuǎn)發(fā)路由請(qǐng)求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ò)功能的實(shí)現(xiàn)10</p><p>　　3.3 Linux操作系統(tǒng)路由轉(zhuǎn)發(fā)功能的實(shí)現(xiàn)11</p><

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

16、/p><p>　　4.2.3 對(duì)內(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é)議的實(shí)驗(yàn)研究31</p><p>　　5.1 測(cè)試環(huán)境31</p><p>　　5.2性能指標(biāo)測(cè)試31</p><p>　　5.2.1 路由查找時(shí)間及時(shí)延數(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>　　自七十年代世界上第一個(gè)分組無線網(wǎng)絡(luò)ALOH在美國(guó)夏威夷大學(xué)研制成功之后，

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

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

23、于不同場(chǎng)合。其中，AODV路由技術(shù)發(fā)展尤為迅速，</p><p>　　1.1.2 課題的目的及意義</p><p>　　無線自組網(wǎng)ad-hoc有靈活、機(jī)動(dòng)組網(wǎng)、迅速適應(yīng)能力強(qiáng)的特點(diǎn)可應(yīng)用于野外工作環(huán)境，在有限的地域內(nèi)提供適應(yīng)機(jī)動(dòng)條件的移動(dòng)通信裝備以滿足特殊需求。如：國(guó)防戰(zhàn)備、災(zāi)難救助、偏遠(yuǎn)地區(qū)等無法得到有線網(wǎng)絡(luò)支持、或者某些只是臨時(shí)需要的通信環(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)有蜂窩移動(dòng)通信系統(tǒng)的覆蓋范圍，實(shí)現(xiàn)地鐵和隧道等場(chǎng)合的無線覆蓋，實(shí)現(xiàn)汽車和飛機(jī)等交通工具之間的通信，用于輔助教學(xué)和構(gòu)建未來的移動(dòng)無線城域網(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é)點(diǎn)設(shè)計(jì)的，它提供對(duì)動(dòng)態(tài)鏈路狀況的快速自適應(yīng)，處理開銷和存儲(chǔ)開銷低，網(wǎng)絡(luò)利用率低（路由開銷低）確定到達(dá)Ad-Hoc網(wǎng)絡(luò)內(nèi)的目的節(jié)點(diǎn)的單目標(biāo)傳輸路由。AODV路由協(xié)議明顯的特征是每個(gè)路由條目均使用一個(gè)目的節(jié)點(diǎn)序列號(hào)。使用目的節(jié)點(diǎn)序列號(hào)能夠確保路由是開環(huán)的。在選擇路由時(shí)，要求路由請(qǐng)求節(jié)點(diǎn)選擇序列號(hào)較大的那條路由。</p><p>　　AODV路

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

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

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

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

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

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

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

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

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

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

36、每幀源節(jié)點(diǎn)維護(hù)的一個(gè)數(shù)字，它幫助其他節(jié)點(diǎn)判斷信息的新舊程度。</p><p><b>　　2.3 幀的格式</b></p><p>　　2.3.1 RREQ協(xié)議幀的格式</p><p>　　AODV路由協(xié)議的路由請(qǐng)求RREQ消息的格式如圖2-2所示，對(duì)其組成域說明如下：</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所示，對(duì)其組成域說明如下：</p><p>　　表2-2 RREP幀組成域說明</p><p>　　圖2-3 RREP幀結(jié)構(gòu)</p

38、><p>　　RERR協(xié)議幀的格式</p><p>　　AODV路由協(xié)議的路由錯(cuò)誤RERR消息的格式如圖2-4所示，對(duì)其組成域說明如下：</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ào)的維護(hù)</p><p>　　路由條目中的目的節(jié)點(diǎn)序列號(hào)越大就越能反映網(wǎng)絡(luò)當(dāng)前拓?fù)淝闆r。路由協(xié)議通過節(jié)點(diǎn)交互路由信息來建立和維護(hù)路由，目的節(jié)點(diǎn)序列號(hào)決定是否接收一個(gè)路由消息。在路由消息中目的節(jié)點(diǎn)序列號(hào)比自己所知序列號(hào)大，則根據(jù)該消息更新路由表；反之，不予處理。</p><p>　　在以下幾種情況下，節(jié)點(diǎn)增加自己的序列號(hào)：</p><p>　?。?

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

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

42、到來自相鄰節(jié)點(diǎn)發(fā)送的AODV控制分組，或?yàn)樘囟康墓?jié)點(diǎn)建立、更新路由時(shí)，路由表中若如無該目的節(jié)點(diǎn)表項(xiàng)，則新建該表項(xiàng)。并在下列情況更新：</p><p>　　協(xié)議幀中的新序列號(hào)高與本機(jī)路由表中的目的節(jié)點(diǎn)序列號(hào)；</p><p>　?。?） 協(xié)議幀中序列號(hào)與路由表中序列號(hào)相等，但跳數(shù)+1小于路由表中跳數(shù)；</p><p>　　（3） 本機(jī)路由表項(xiàng)中的目的序列號(hào)未知。&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58、的時(shí)候，節(jié)點(diǎn)在所有使用AODV協(xié)議的接口上廣播RREQ幀。只有一種情況除外：在這個(gè)接口上的所有鄰居節(jié)點(diǎn)已經(jīng)收到了這個(gè)RREQ則不在這個(gè)接口上廣播[6]。</p><p>　　第3章 Linux操作系統(tǒng)的網(wǎng)絡(luò)功能 </p><p>　　本設(shè)計(jì)中，AODV路由協(xié)議是在Linux操作系統(tǒng)上實(shí)現(xiàn)的。在實(shí)現(xiàn)方案中，充分利用了操作系統(tǒng)自身的特點(diǎn)。因此，在介紹設(shè)計(jì)方案前先對(duì)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ā)展成為一個(gè)多用戶開源操作系統(tǒng)。由于其源代碼開放性、廉價(jià)性、安全性以及優(yōu)越的性能，現(xiàn)在得到了越來越廣泛的應(yīng)用，尤其是在服務(wù)器操作系統(tǒng)領(lǐng)域。</p><p>　　從操作系統(tǒng)的功能角度來看，Linux的核

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

61、和BSD Socket層之間的應(yīng)用程序接都以4.4BSD為模板。INET Socket 層實(shí)現(xiàn)比IP協(xié)議層次高，實(shí)現(xiàn)對(duì)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ù)流程走向的觀點(diǎn)來分析，應(yīng)用曾中的操作對(duì)象是socket文件描述符，通過文件系統(tǒng)定義的通用接口，使用系統(tǒng)調(diào)用從用戶空間切換到內(nèi)核空間。

62、對(duì)socket文件描述符的操作傳遞給對(duì)應(yīng)的BSD Socket操作，從而進(jìn)入到BSD Socket層的操作。在BSD Socket層中，操作的對(duì)象是socket結(jié)構(gòu)，每一個(gè)這樣的結(jié)構(gòu)對(duì)應(yīng)的是一個(gè)網(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、主要原則。在這一層中的操作對(duì)象是sock類型的數(shù)據(jù)，而數(shù)據(jù)存放在sk-buff結(jié)構(gòu)中。從INER Socket層到IP層，主要是路由過程，發(fā)送時(shí)根據(jù)發(fā)送的目標(biāo)地址確定需要使用的網(wǎng)絡(luò)設(shè)備接口和下一跳的主機(jī)地址；接收數(shù)據(jù)的時(shí)候需要在IP層判斷該數(shù)據(jù)分組是要發(fā)送給上一層協(xié)議還是需要做一個(gè)IP轉(zhuǎn)發(fā)，將數(shù)據(jù)傳遞給下一臺(tái)機(jī)器。從IP層到硬件層，也就是到網(wǎng)絡(luò)接口設(shè)備驅(qū)動(dòng)程序，即是有關(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ā)功能的實(shí)現(xiàn)</p><p>　　在Linux的路由功能子系統(tǒng)中，主要保存了三種與路由相關(guān)的數(shù)據(jù)。第一種是在物理上和本機(jī)相連接的主機(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é)點(diǎn)。第二種表是保存路由規(guī)則，用fib-table數(shù)據(jù)結(jié)構(gòu)的鏈表表示。第三中表被稱作路由緩存表，用rtable數(shù)據(jù)結(jié)構(gòu)的鏈表表示[8]。</p><p>　　Linux系統(tǒng)中路由采取的策略是，先到路由緩存表中查找表項(xiàng)，如果能夠查找到，就直接將對(duì)應(yīng)的一項(xiàng)取出來作為路由的規(guī)則；如果找不到，那么就根據(jù)fib-table鏈表中的內(nèi)容，利用特定規(guī)則換算出來，并

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

81、則調(diào)用該模塊注冊(cè)時(shí)使用的回調(diào)函數(shù)。這五個(gè)掛鉤的結(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)中的五個(gè)掛鉤點(diǎn)</p><p>　　4.2.2 用戶空間和內(nèi)核空間的信息交互實(shí)現(xiàn)</p><p>　　為了實(shí)現(xiàn)用戶空間和內(nèi)核空間的信息交互，本設(shè)計(jì)利用了Linux 2.4內(nèi)核的防火墻Netfilter提供一個(gè)分組

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

86、發(fā)還是發(fā)給本機(jī)的；若該數(shù)據(jù)包是發(fā)被本機(jī)的，則該數(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ù)報(bào)經(jīng)過最后一個(gè)鉤子函數(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ù)包；然后查找用戶空間層路由表項(xiàng)，查詢是否有到目的節(jié)點(diǎn)路由，如果存在該路由，則通過netlink socket通知內(nèi)核接受該數(shù)據(jù)包，使包順利通過鉤子[4]進(jìn)而進(jìn)行內(nèi)核對(duì)數(shù)據(jù)包的后續(xù)處理工作，如路由等；反之一旦路由表中不存在該路徑，立即將該數(shù)據(jù)包進(jìn)行排隊(duì)，同時(shí)應(yīng)該通過發(fā)送AODV控制包進(jìn)行路由查找，如：發(fā)送RREQ等待目的節(jié)點(diǎn)發(fā)回RREP給源節(jié)點(diǎn)在用戶空間建立路由，隨后利用ioctl()在內(nèi)核空間建立內(nèi)核路由表，最后同樣將數(shù)據(jù)包通過n

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

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

90、用戶空間之間的交互，不能直接交換信息。因此程序利用了Linux的控制函數(shù)ioctl來操作Linux內(nèi)核路由表。同樣也利用ioctl來獲取網(wǎng)絡(luò)接口的信息。它能獲取網(wǎng)絡(luò)接口的地址、是否支持廣播、是否支持多播等功能。在獲取網(wǎng)絡(luò)接口信息的時(shí)候，ioctl函數(shù)使用了一個(gè)叫做ifconf的數(shù)據(jù)結(jié)構(gòu)，而ifconf又使用了一個(gè)ifreq的數(shù)據(jù)結(jié)構(gòu)。每個(gè)網(wǎng)絡(luò)接口用一個(gè)ifreq表示，在這個(gè)結(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>　　程序開始時(shí),首先讀取程序可執(zhí)行文件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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