1、1 緒論1.1 研究背景 隨著無線通訊技術，嵌入式技術的逐漸成熟，網絡系統不在單一化，而是形成一種由多個具有傳感和通信功能的傳感器連接設備構成的新型網絡無線傳感器網絡（wireless sensor network,wsn），并且該網絡形式已然起人們極大關注1。無線傳感器網絡結合傳感器技術，信息技術，分布式處理，嵌入式計算機和通信技術，使其能夠協助并對分布區域內的信息進行的感知、采集、檢測，獲取詳細和準確的信息，將信息傳輸到用戶，以滿足用戶的需求。無線傳感器網絡利用傳感器節點對周邊環境進行震動、雷達、熱、紅外等信號的監測，來獲取溫度、光強度、物體的大小、壓力、速度和方向等目標屬性，然后各個節點

2、之間協同合作，完成數據的感知采集和處理，發送給用戶。它具備以下優勢：網絡覆蓋區域廣，部署比較靈活；節點分布密集，靠近目標區域，可實現多方位和高精度的信息獲取；低成本，冗余網絡設計，保證網絡的高可靠性；分布式自組織網絡結構，支持并發訪問和任務的實現。無線傳感器網絡具有非常廣闊的應用前景，可廣泛應用于軍事，環境監測，目標跟蹤，醫療，智能家居等諸多方面。其研究和發展涉及國家安全，經濟發展等重大方面，因此近年來，無線傳感器網絡的應用引起了廣泛的國際關注和投資。1.2 國內外研究前景無線傳感器網絡作為一種新的計算機模型，以用于促進社會進步和科技開發，其研究已涉及到國家的經濟和社會安全，成為國際競爭，新的

3、制高點，因此引起世界各地的工業部門軍事部門的極大關注。英特爾，微軟等信息產業巨頭也設立或啟動相應的行動計劃。美國國防部和各軍事部門對無線傳感器網絡給予高度重視，把無線傳感器網絡作為一個重要研究領域，設立了一系列的軍事無線傳感器網絡研究項目。許多國家已經紛紛展開了該領域的研究。近年來，中國已開始重視無線傳感器網絡技術研究。國家自然科學基金資助了無線傳感器網絡研究項目，包括重點工程和表面工程。“中國在未來20年技術預見研究”報告中，在傳感器網絡方面的技術課題達到了7個。我國關于無線傳感器網絡的應用方面的研究起步略晚，但目前已經越來越受到重視，正逐漸成為熱點，并已開展有關于該領域的研究，其研究對社會

4、、經濟有著長遠的戰略性意義。1.3 論文主要的內容及結構本文首先對無線傳感器網絡路由協議aodv的原理進行了討論，并進一步闡述了其實現方法。然后，對它的傳輸時延，平均時延，分組投遞率，路由發現時間進行研究。并在此基礎上把aodv協議與dsdv協議從性能上進行了比較。全部章節如下：第一章簡單介紹了無線傳感器網絡的背景，及網內外研究現狀和簡單闡述了本論文的章節安排。第二章對無線傳感器網絡，包括其結構和特點進行了概述。第三章對無線傳感器網絡路由協議進行了分類和比較，并進一步的闡述了aodv協議。第四章介紹了aodv路由協議來源，進一步闡述了路由算法的原理和操作方法。第五章在ns-2平臺上對aodv協

5、議進行了仿真模擬，對其平均時延，分組投遞率和路由發現時間進行研究。并在此基礎上把aodv協議與dsdv協議從性能上進行了比較。2 無線傳感器網絡概述2.1 無線傳感器網絡的介紹無線傳感器網絡（wireless sensor network，wsn）是一種新的科學技術網絡，該研究始源于美國軍方。無線傳感器網絡是由大量具有特殊作用的無線傳感器節點，通過自組織的方式進行信息傳遞，互相協作完成特定功能的智能型網絡2。它結合了微機電系統（micro.electron mechanical system，mems），傳感器技術，嵌入式計算技術，現代網絡及無線通信技術，通過集成微傳感器對各類分布式信息處理技

6、術和軟件編程技術實時協作，對各種環境實時監控，將監測對象控制地區的采集到的數據聚集，通過自組織多跳網絡的方式傳送給用戶終端，從而實現物理世界，計算機世界和人類世界社會的三元連接。無線傳感器網絡的應用有著廣闊的發展前景，在工業，農業，交通，軍事，醫療，空間監測，環境監測，搶險救災，危險區域及其他重要領域有著實際的作用，因此近年在國內外引起了廣泛的關注，并投入大量的資金。2.2 無線傳感器網絡系統及其協議的體系結構通常情況下，無線傳感器網絡體系結構如2.1所示，無線傳感器網絡中的各個部分分布著眾多具有射頻功能的傳感器節點，并負責收集數據，并通過無線傳感器網絡技術將數據發送到接收器節點匯聚節點（網關

7、或基站），匯聚節點通過公共網絡監控和管理中心（如internet網絡/衛星通信網絡等）傳達給用戶，用戶對收集到的數據處理和分析，作出判斷或決定。圖2.1 無線傳感器網絡體系結構與其他網絡相同，無線傳感器網絡分層的網絡通信協議的包括物理層，數據鏈路層，網絡層，傳輸層和應用層，其協議結構2.2所示。物理層負責數據的抽樣量化，信號的調制，發送和接收，即負責比特流的傳輸工作;數據鏈路層負責數據成幀，對幀實行監測，介質訪問控制，差錯控制，以減少傳輸節點間的沖突；網絡層的任務，例如，實現數據傳輸，傳感器和傳感器，傳感器和信息中心的通信;如果信息在內部傳遞，不需要傳輸層，但從實際應用的角度來看，無線傳感器網

8、絡和外部需要通訊傳輸數據，因此在無線傳感器網絡以數據基礎的網絡尋址到外部尋址，即完成數據格式的轉換功能；在應用層，根據不同的應用需求，可以實現無線傳感器網絡的特殊用途的應用。和蜂窩網絡、無線局域網等其它網絡相比，無限傳感器網絡有上述顯著的優點。根據其特點結合實際應用，無線傳感器網絡需要采取一種靈活的解決方案。在網絡層，針對不同的應用需求，采用節能分布式路由算法和協議和數據融合算法。從圖2.2可見，在無線傳感器網絡協議體系結構中定義了，如能源管理，拓撲管理的跨層管理技術和應用支持技術。應用支持技術分布式網絡服務端口分布式網絡管理接口應用層傳輸層網絡層數據鏈路層物理層能量管理拓撲管理qos管理網絡

9、管理網絡安全管理移動控制遠程管理分層的網絡通信協議無線傳感器網絡跨層管理技術圖2.2 無線傳感器網絡協議體系結構2.3 無線傳感器網絡的特點無線傳感器網絡是一個“智能“網絡，它具有一定的獨特性。也正是因為這些特點，無線傳感器網絡有其自身的優勢，也有許多問題需要解決，無論是對現在研究人員來說，還是對無線傳感器網絡在實際中的應用來說，都具有很大的挑戰。無線傳感器網絡具有以下主要特點。(1) 傳感器節點密度高，數目多，采用空間位置尋址4。在無線傳感器網絡中，為了保證網絡上數據傳輸的可用性和可行性，因此需要節點的密度相對比較高。正因為存在大量的傳感器節點，網絡一般不支持兩個節點之間進行點對點通信，并且

10、每個節點不存在唯一的標識符，故而采用空間位置尋址對數據進行傳輸。(2) 傳感器節點計算能力和存儲容量能源有限5。隨著微型化傳感器節點的產生，電池所能提供的能量越發的有限，并且由于節點分布的環境并不穩定，很難更換電池。所以如何限制節點能源的消耗就成為網絡設計當中的瓶頸，它直接決定著網絡使用的壽命。另一方面，傳感器節點的存儲容量小，低計算能力，數據存儲不能復雜。因此，無線傳感器網絡的研究人員構成了挑戰，他們必須設計簡單，高效的無線傳感器網絡路由協議。(3) 具有自組織能力隨著無線傳感器網絡能源需求增加，傳感器節點可以工作和睡眠之間隨時切換，由于各種原因導致的故障或失效，或增加新的傳感器網絡節點，這

11、些事件都會使得無線傳感器網絡的拓撲結構在使用中容易改變。此外，因為節點有移動性，必須更改網絡的拓撲結構。基于網絡的拓撲結構變異，無線傳感器網絡已經具有自我組織，自我配置功能。(4) 傳感器節點具有數據融合能力在無線傳感器網絡中，由于存在大量的傳感器節點，多個節點可能采集到相同類型的數據，因此，通常需要一些節點具有數據融合能力，可以將多個傳感器的數據融合，然后發送給信息處理中心。數據融合可以減少冗余數據，從而減少在傳輸過程中的能量消耗，延長網絡的壽命。3 無線傳感器網絡中的路由協議3.1 無線傳感器網絡路由協議的分類無線傳感器網絡路由協議的分類延續了ad hoc網絡的基本傳統的分類方法，根據不同

12、的角度可進行不同的分類。從路由發現策略的來看，可分為主動和被動兩種類型的路由;從網絡管理的邏輯結構可以分為，包括泛洪、spin、sar和定向擴散在內的平面路由協議，和包括leach、teen、pegagis和多層類聚算法在內的分層路由協議兩類3。（1） 主動路由也稱為表驅動路由（table driven），主動路由發現策略類似于傳統的路由協議，節點周期性的廣播路由信息包交換路由信息，主動尋找路線，而所有的網絡節點都必須保持對所有節點路線，即主動路由協議，網絡中的所有節點之間保持通常是源節點和目的節點的路由表，無論路線是否必要。主動式的路由協議通常包括“鄰居探測“和路由廣播兩個過程。（2） 被動

13、路由又稱為按需路由（on demand）路由，和主動路由相反，被動路由認為在動態變化的網絡中，沒有必要維持到所有節點的路由信息，它只會在沒有去目的節點路由時“按需“的路由發現。被動式的路由協議報文傳輸請求根據網絡的傳輸請求，被動節點從源節點搜索到目的節點的路由。當沒有傳輸請求數據包時，路由器是在安靜的狀態，并不需要相互交換路由信息。拓撲結構和路由表內容按需建立，它可能只是拓撲結構的一部分。（3） 平面路由平面結構是指網絡中，每個節點在路由功能上的地位相同，通過本地業務和反饋信息生成路由，并沒有引入分級管理機制。（4） 分層路由分層路由是平面路由對應的路由協議。分層路由協議使用簇來分類傳感器節點

14、，即相鄰節點集群的概念，每個群集有一個簇首。由簇首完成簇內通信，簇首節點匯聚簇內節點的信息，以減少交通量，并最終通過簇首節點將收集到的數據傳遞給終端節點。因此，無線傳感器網絡具有可擴展性，同時盡量避免了傳感器節點的能量消耗，使網絡的生命周期延長。針對這些特點，許多大學開始對無線傳感器網絡通信協議進行研究，提出了多種路由協議，主要是平面路由（如：flooding協議、spin協議、sar協議和dd協議）和分層聚類協議（如：leach協議，pegagis協議，teen協議）6。如圖3.1所示。平面路由分層聚類floodingaodvsarddleachpegagisteen路由協議圖3.1 無線傳

15、感器網絡的路由協議3.2 表驅動路由與按需路由協議的比較卡耐基梅隆大學，josh broch等人以ns-2網絡仿真工具為基礎開發了無線移動網絡仿真模塊，并在相同的仿真環境分析dsdv，dsr和aodv協議進行性能比較，他們模擬節點具有低移動率，節點具有較高的移動率，節點移動慢三仿真環境10。他們的仿真結果是，在三種仿真環境下，被動路由協議(dsr和aodv)的性能都比表驅動路由（dsdv）好很多。在中等的流量負載下，dsr的性能要比aodv協議好，而在高負載的情況下aodv的性能高于dsr。產生這種結果的具體原因，主要是由于表驅動路由協議可以使路由表比較準確的反映出網絡的拓撲結構。一旦節點發送

16、數據包，可以立即獲取目的節點的路由，所以路由協議的時延較小，但該協議需要付出大量的路由控制包，造成更大路由開銷。因此，在網絡負載中等的情況下適于使用，在比較大的網絡規模和移動性大的情況下不應使用。相反，按需路由協議并不需要周期性的維護不需要的路由，而是當需要獲取路由的時候在發送數據請求數據包，因此所產生的路由控制信息比表驅動路由要少很多。但是由于數據在傳輸之前需要建立路由，所以存在一定的時延。故按需路由協議在節點移動不大的場合下比較適用。4 aodv協議4.1 aodv協議的來源dsdv協議dsdv是表驅動路由協議，由傳統的bellman . ford（dbf）路由協議改善而成。在dsdv中，

17、每個移動節點需要維護一個路由表。路由表條目包含目標節點、跳數、目的序列號，其中目的序列號主要是用于確定是否過時，避免路由回路分配。在dsdv使用序列號最高的路由，如果兩個路由具有相同的序列號，那么選擇最佳路線，就是最小跳數路由。4.2 aodv簡述aodv協議是移動自組織網絡manet（mobile ad hoc network）應用最廣泛的按需路由協議，采用最短路由選路，注重網絡吞吐量和網絡服務質量。無線傳感器網絡是manet網絡技術中一個主要應用領域，所以可以將aodv協議移植到wsn中。當網絡拓撲發生變化，aodv協議快速收斂。計算量比較小，占用較少的存儲資源，能夠自我修復短路，減少網絡

18、帶寬。當源節點需要發送數據到目的節點，且源節點的路由表中沒有到達目的節點的路由記錄時，源節點將啟動路由發現過程。aodv適用于資源受限的自組織無線網絡，它不需要定時廣播路由信息，節省有限的網絡帶寬，降低網絡的控制開銷。aodv中源節點和目的節點之間的通信分為三部分:（1）路由請求（2）路由應答（3）數據傳輸aodv算法中使用4種類型的控制分組:（1）route request (rreq)，路由請求分組（2）route reply (rrep)，路由回復分組（3）route error (rerr)，路由錯誤分組（4）hello 分組aodv使用洪范（flood）方式，從源節點廣播rreq請求

19、進行路由發現。當源節點s要建立到目的節點d的路由時，源節點向周圍相鄰節點廣播路由分組請求（rreq），rreq請求分組擴散到全網之后將建立所需路由。中間只有在第一次接收到該分組時提取rreq請求分組中的目的節點與自身ip地址進行比較。如自身是目的節點，立即向源節點回復應答分組（rrep)。如自身不是目的節點，則提取rreq請求分組中的源節點ip和廣播id判斷是否轉發過該分組。如已轉發過，則丟棄該rreq分組，若沒有轉發過，則將源節點的ip地址和廣播id寫入路由請求記錄表，并建立到源節點s的反向路由。同時，請求數據包rreq跳數字段（hop count）值加1，然后轉發rreq給鄰居節點。一旦r

20、req分組到達目的節點d，或有“足夠的新“路由到目的地節點d（“足夠新“意味著這條路由相應的序列號（sequence number）大于或等于rreq消息的序列號），該節點將按剛剛創建好的路線返回源節點s rrep分組，以單播的方式11。rrep應答分組會沿著中間節點建立好的反向路由單播到源節點。當源節點s接收到目的節點的rrep應答分組時，就可以通過建立好的正向路由向目的節點發送數據。圖4.1和圖4.2分別是aodv協議路由請求和路由應答過程的示意圖。圖4.1 源節點廣播路由請求過程圖4.2 目的節點單播路由應答過程圖4.3為源節點建立到目的節點路由的過程圖4.4為路由建立后，監聽的過程圖4

21、.3為源節點建立到目的節點路由的過程。路由建立后，中間節點會定時監聽從鄰居節點發來的hello分組，如在定期時間內未收到來自下游鄰居節點發送的hello分組時，則判斷路徑發生斷裂，并向上游節點單播路由錯誤分組rrer。當源節點接收到rrer分組后，將重新建立向目的節點的路由，發送一帶有大于原先目的節點序列號的rreq請求分組。另外，如與工作路由無關的節點移動或者斷裂，應不影響到目的節點的路由。圖4.4為路由建立后，監聽的過程。4.3 aodv分組格式4.3.1 rreq分組格式表4.1 rreq分組分組格式分組包含以下的域：type 1j 加入標識符，標識是否為多播。r 修復標識符，標識是否為

22、多播。g 非必要的rrep標識符，表明是否需要單播rrep分組和目的 節點ip地址給指定的節點。d 目的節點唯一性標識符，表明只有目的節點才對rreq做出回應。u 未知序列號標識符，表明目的節點序列號當前未知。reserved 設為0，接收時忽略。hop count 從源節點到當前節點所處理的rreq的節點的跳數。rreq id 和源ip地址一起保證和標志該路由建立過程發送的rreq分組的唯一性。destination ip address目的節點的ip地址。destination sequence number源節點收到的最新的目的節點序列號。originator ip address源節點

23、的ip地址originator sequence number源節點的序列號4.3.2 rrep 分組格式表4.2 rrep分組格式分組包含以下的域：type 2r 修復標識符，在多播情況下使用的字段a 確認標識符，表明是否需要確認收到rrep分組reserved 保留字段，設為0prefix sz 前綴長度，如果非零，說明指定的下一跳將被當作前綴相同的節點的目的節點。hop count 源節點到目的節點的跳數。destination ip address目的節點的ip地址destination sequence number目的節點序列號originator ip address源節點ip地

24、址lifetime 生存時間，收到rrep的節點認為保留該路徑所需要的時間，以毫秒為單位。a標識位是在發送rrep鏈路不可靠或者信息單向傳播時，進行設置，收到rrep的節點被期望返回一個rrep-ack分組，格式如表4.4所示。4.3.3 rerr 分組格式表 4.3 rerr 分組格式分組包含以下的域：type 3n 不刪除標識，當節點實現本地鏈路修復時設置該位，并且上游的節點不應刪除這條路徑。reserved 保留字段，設為0destcount 不可達的節點的個數，至少為1additional unreachable destination ip address因鏈路中斷而變得不可達的目的

25、節點的ip地址additional unreachable destination sequence number因鏈路中斷而變得不可達的目的節點的序列號4.3.4 rrep-ack分組格式表 4.4 rrep-ack分組格式type 4reserved 保留字段，設為04.4 aodv路由算法的原理aodv路由協議是一種按需距離矢量路由，和表驅動路由協議不同，按需路由協議只有需要一個源節點到目的節點的路由，或者當一個節點想要加入一個多播組才進行路由發現12。aodv路由在ad hoc移動網絡中單播，組播或廣播的移動網絡協議。當源節點需要一條通往目的節點，將發起一個網絡路由發現過程。當尋找到一

26、條路徑，或所有可能的路徑已被檢查后，路徑發現過程完成。一旦路徑建立，路由表將維持到不再需要該路徑、該條路由失效或超過生存期。aodv路由查找使用廣播機制。除了源路由，aodv協議還依靠中間節點動態創建路由表項。該協議借用dsdv中的目的序列號機制，每個節點維護一個單調遞增序列號計算器，用它來標記在緩存中路由的新舊。4.5 aodv路由算法基本操作4.5.1 維護序列號一個節點只有在以下3種情況中會改變路由表項中的目的節點序列號：(1) 它自己本身就是目的節點；(2) 它收到了一個更新的有關目的節點序列號的信息。(3) 到目的節點的鏈路終止或中斷。目的序列號會在接收到rreq,rrep或rerr

27、中新的信息時更新。aodv依靠網絡中的每個節點去保存和維護它的目的節點序列號，以保證沒有環路。一個目的節點會在兩種情況下增加它自己的序列號：(1) 當需要對同一個目的節點啟動新的路由發現(route discovery)時，它必須增加它自己的序列號。這會防止與之前建立的到源節點的反向路徑出現沖突。(2) 當目的節點即將發送的rreq消息響應一個rrep，必須更新自己的序列號，使當前的rreq分組的序列號和目的節點是序列號最大的一個13。為了保證關于目的節點的信息不會變得陳舊，節點比較當前的序列號和從分組中獲得的序列號。這種比較必須使用32位的有符號整數，這是為了實現序列號的輪轉。如果新獲得的序

28、列號減去當前的序列號結果小于0，那么新獲得的序列號就會被忽略。另一種會改變路由表項中目的節點序列號的情況是當去往下一跳的鏈路中斷或終止時，節點會把相應的路由項置為無效，同時增加這些路由項的序列號。4.5.2 產生路由請求當目的節點未知、原路徑失效或終止，且節點（即源節點）在需要發現路由的時候會發送rreq分組。rreq中的目的節點序列號域先設為最后所知道的序列號，若序列號未知，則必須設置未知序列號標識。節點自己的序列號在復制到rreq中后自我增值。rreq id域設為最后使用的rreq id加一。跳數域設為0。廣播rreq消息前,源節點將緩存的rreq id和自己的ip地址的path_disc

29、overy_time長時間，這樣，當它從鄰居節點接收到相同的rreq分組，不要發送，處理重復14。當源節點期望能和目的節點進行雙向通信時，源節點會設置g標識位。這樣目的節點就能接收到反向路徑的通報。一個源節點每秒內不應發送超過設置的請求分組帶寬的rreq。如果在等待了net_traversal_time毫秒后節點還沒收到相關路由信息，節點會再次嘗試發送rreq,最多嘗試rreq_retries次。為了減少網絡的擁塞，同一個節點重復的請求會利用利用二元指數后退算法。即節點第一次發送rreq時，等待net_traversal_time毫秒，隨后的每次嘗試等待的時間都是前一次等待時間乘2。4.5.3

30、 路由請求消息的控制傳播為了防止的rreq分布擴展至整個網絡，源節點將使用擴展環式搜索技術。在這種技術，為源節點的rreq分組的ip中初始化一個ttl=ttl_start，并設置收到rrep時間為ring_traversal_time毫秒。用來計算ring_traversal_time的ttl_value設置為ip頭中ttl的值。當rreq超時，重發rreq時，ttl增加ttl_increment。如此繼續，直到ttl達到ttl_threshold，此后的重試中設ttl=net_diameter。每一次等待rreq的計時時間都為ring_traversal_time，當需要重試的分組跨越整個a

31、d hoc網時，可以把ttl_start和ttl_increment都設為net_diameter。當需要對同一個目的節點啟動新的路由發現時，rreq中的ttl將被初始化，成為原有失效的跳數加上ttl_increment。一個過期的路由表項在delete_period的時間內都不能被擦除。另外還能夠設置更長的擦除時間。任何一個正在等待rreq的路由表項在2*net_traversal_time的時間內都不能被擦除。4.5.4 處理和轉發路由請求當一個節點接收到rreq消息時，它首先創建或更新沒有有效的路由表項。然后查看在至少path_discovery_time是否收到相同的源ip地址和rre

32、q id消息的rreq分組，如果有的話，忽略目前收到的rreq分組。當收到的rreq不被忽略時，首先把rreq中的跳數增1，然后在路由表中搜尋到源節點的反向路徑，使用最長匹配原則，如果有需要，則創建新的反響路由表項，或者用rreq中的源節點序列號更新原有路由表項。當反向路徑被創建或更新時，將會執行下面的操作：如圖4.5圖所示。(1) 將rreq消息源節點序號的和相對應的反向路由中的目的節點序列號作比較，如果前者比后者大，前者將取代后者。(2) 路由項的有效序列號域被設為真。(3) 路由項的下一條設為向該節點傳送rreq的節點，這個從ip頭部中的源地址ip中獲得。不管何時收到一個rreq,反向路

33、由項的生存期都會被設為existinglifetime和minimallifetime中的較大者，其中minimallifetime=(當前時間+2*net_traversal_time.2*hopcount*node_traversal_time).如果一個節點不產生一個rrep，且收到的rreq的ip頭中的ttl大于1，則這個節點向它的每一個接口用255.255.255.255作為目的地址廣播rreq。這些rreq的ttl減1，而跳數則增1。最后，目的節點接收到rreq分組設置為自己的節點和目的節點序列號中最大的序列號值。然而，即使收到的rreq目標節點序列，它比目前的保存自己的目標序列號

34、大，也不能修改其保存的值。如果一個節點會產生rrep，則可忽略它收到的rreq。注意，如果一個中間節點對每一個rreq都作出回復，那么目的節點可能收不到任何路由發現的信息。在這種情況下，目標節點無法從rreq分組中獲取源節點的路由。這將導致目標節點也該發起路由發現過程。為了避免這種情況，當目的節點可能需要一條到源節點的路徑時，源節點會設置rreq中的g標志域。當一個節點收到設置了g域的rreq，當它回復rrep給源節點時，它也必須同時單播一個非必要rrep給目的節點。圖4.5 節點收到rreq處理過程4.5.5 產生路由應答一個節點在以下2種情況會產生rrep：(1) 它本身就是目的節點(2)

35、 它有一個有效的路由到達目的節點，而路由表項的目標序號大于等于rreq消息序列數目，且d標志未設置。當產生rrep時，節點復制rreq中的目的節點ip地址和源節點序列號到rrep中的相應域中，其余的操作，視上述兩種情況有細微的不同，下面將作仔細的說明。因為rrep是反向發送到源節點，因此在每一跳的過程中，跳數都會被增1。因此，當rrep到達源節點，源節點跳數表示到目的節點的距離。4.5.5.1 目的節點產生的rrep當節點本身是目的節點時，如果它自身的序列號增1后與rreq中的序列號相等，則將自身序列號增1，否則，在產生rrep之前不改變自身的序列號。然后目的節點把自己的序列號復制到rrep中

36、，并把跳數設為0，把my_route_timeout復制到rrep的生存期域中。每個節點都可以重新設置它們的my_route_timeout值。4.5.5.2 中間節點產生的rrep當節點是中間節點時，它復制它所知道目的節點序列號到rrep中，并把它收到的rreq中指示的上一跳節點添加到指向目的節點的路由項的前驅表中，而把去往目的節點的下一跳節點添加到指向源節點的反向路由項的前驅表中。最后，中間節點把目的節點的跳數復制到rreq分組當中，而生存范圍設置成路由項的到期時間減去當前時間。4.5.5.3 產生非必要rrep如果節點收到的rreq設置了g標志位，它必須單播一個被必要rrep給目的節點。

37、非必要rrep包含了以下表中，如圖4.5所示：跳數到源節點的跳數目的節點ip地址發送rreq的源節點的ip地址目的節點序列號rreq中的源節點序列號源節點ip地址rreq中目的節點ip地址生存期到達rreq的源節點的的路徑的生存期圖4.5 rrep內容注解rrep非必要，然后被發送到目的節點的下一跳，如果目標節點發送一個rreq分組到源節點，而rrep分組對rreq分組相同。而發往源節點的rrep不管rreq有無設置g標志位都一樣。4.5.6 接收和轉發路由應答當一個節點收到rrep,它首先在路由表中搜尋到上一跳的路由項，如有需要，會創建一條新的表項，但不包含有效的序列號。然后節點把rrep中

38、的跳數增1，并稱這個值為“新跳數”。如果去往目的節點的路徑尚不存在則創建一條新的，否則把rrep中的目的節點序列號和已有的相比較。經過比較后，只有在以下幾種情況中會更新已有的路由項：(1) 原路由項中的序列號被標志為無效；(2) rrep中的序列號大于原有的序列號；(3) 兩個序列號相等，不過這條路徑被標志為不活動的；(4) 序列號相等，但是新的跳數比原有的要小。如果去往的目的節點的路由項被創建或更新，會執行以下的操作：如圖4.6所示。(1) 路徑被標志為活躍的(2) 目的節點序列號被標志為有效的(3) 下一跳設為傳來rrep的那個節點(4) 跳數設為“新跳數”(5) 過期時間設為現在的時間加

39、上rrep中的生存時間(6) 目的節點序列號設置成為rrep中的序列號如果當前節點不是rrep中的源節點，它會查詢路由表以決定rrep的下一跳。如果節點發送的rrep的鏈路有錯誤或是單向的，節點會設置其中的a標志位，以使rrep的接收方會回復一個rrep-ack。任何轉發rrep的節點，都會把發送rrep的下一跳加入到去往目的節點的路由項前驅表中，在同一時間，修改源節點路徑的生存期為現有的生存與（當前時間+ active_route_timeout）的較大值。圖4.6 節點收到rrep的處理過程4.5.7 單向鏈路上的操作當鏈路為單向的時候，rrep的傳送有可能會失敗，如果源節點收不到rrep

40、，在計時結束后，會重新嘗試發起路由發現的過程。然而，這種情形可能一直重復而得不到任何改善，即使重復嘗試仍然不能得到任何路徑。在aodv中有對應糾正的操作，即節點只對第一個具有相同rreq id的rreq做出回應，其他后續的rreq都將被忽略。然而這又將產生新的問題，即第一個rreq可能經過的路徑中包含單向鏈路，但后續的rreq可能經過雙向鏈路到達，而它們將會被忽略。為了避免這種情況，當一個節點檢測到一個rrep傳輸失敗，它建立一個黑名單將剛剛傳送的rrep的下一跳記錄到其中。每個節點將忽略節點中黑名單所羅列的rreq分組。黑名單中的節點在經過blacklist_timeout后會從名單中移除。

41、rrep- ack數據包不包含有關的信息的rrep。這個信息只是為了告訴發送方鏈路當前是雙向的。4.5.8 hello消息一個節點由當地廣播hello報文節點提供連接信息。每隔hello_interval毫秒，該節點將檢查其是否在此期間發送了一個廣播數據包，如果不是，它會廣播ttl= 1的rrep，并稱為hello分組，它的格式如下設置，如下圖4.7所示：destination ip address節點本身的ip地址destination sequence number節點最新序列號hop count0lifetimeallowed_hello_loss*hello_interval圖4.7

42、hello分組的格式一個節點通過監聽來自鄰居的分組來決定連通性。如果在過去delete_period時間之內，節點已經收到了鄰居的數據包，然后allowed_hello_loss* hello_interval毫秒從未收到任何來自這個鄰居的數據包，它就會認為到該鄰居的鏈路當前已經中斷，接著就執行5.4.11中描述的操作。當一個節點收到鄰居的一個hello分組時，它會認為它有一條到達鄰居活躍路徑。如果這條路徑已經存在，它會延長相應節點的生存期，如有必要，可至少設為allowed_hello_loss*hello_interval，并復制hello分組中最新的目的節點序列號到相應路由項中。4.5.

43、9 維護本地連接性節點應該持續監測活躍下一跳和在（allowed_hello_loss*hello_interval）時間內接收到過hello分組的鄰居連通性。一個節點使用以下的鏈路或網絡層機制來維護上述相關節點的連通性的準確信息。(1) 任何合適的鏈路層通知，例如每次給活躍下一跳發送數據包時ieee 802.11提供的一些通知，可以用來判定鏈路連通性。還有例如鏈路層ack的缺失，或發送rts后收不到cts，甚至于達到重傳次數的最大值時，都提示了鏈路層的中斷。(2) 如果沒有可用的上述通知信息，使用被動通知的方法。即當預期下一跳會轉發分組時，監聽嘗試傳送的信道，如果再next_hop_wait

44、毫秒內監聽不到傳送或下一跳就是目的節點時，使用下面的其中一種方法來判定連通性：收到任何來自下一跳的分組；單播一個rreq給下一跳，詢問到下一跳的路徑單播一個icmp響應請求給下一跳如果使用上面的任何方法都不能監測到到達下一跳節點的鏈路，那么這條鏈路則被認定為是丟失的。4.5.10 rerr消息，路由過期和路由刪除對路由錯誤和鏈路中斷的處理一般包含下面幾步：(1) 把現有的相關路徑置為失效；(2) 列出受影響的的目的節點；(3) 判定有哪些鄰居受影響；(4) 傳送rerr給這些受影響的的鄰居。rerr可以使用廣播或單播方式發送，也可以分別多次單播給前驅表中的節點。一個節點每秒不能產生超過rerr

45、_ratelimit個rerr。一個節點在以下3種情況中會準備發送rerr：如圖4.7所示。在發送數據時探測到一個往下一跳的鏈路中斷，或者路徑修復失敗；如果收到一個發往無相關活躍路徑的節點的數據包；如果節點收到來自鄰居的rerr。對于情況和情況，節點首先會列出那些使用該下一跳的無法到達的目的節點列表。如果一個與子網相關的路由項變得不可達，那么將會對該子網的ip地址附加0前綴。對于情況，無法到達節點列表應由rerr中的目的節點組成。列表中的不可達目的節點可能也被其它鄰居節點使用，因此節點會給相關節點發送新的rerr，這個rerr要包括不可達目的節點列表里的前驅表不為空的節點。在發送rerr前，對

46、不可達目的節點的路由項作以下處理：(1) 如果路由項存在且有效，則對于上面的情況、，把目的節點序列號增1，對于情況，直接把rerr中的序列號復制到路由項中。(2) 把相關路由項設為無效的；(3) 相關路由項生存期更新為當前時間加上delete_period。圖4.7 rrer發送過程4.5.11 本地修復當鏈路中斷，以及對目標節點的距離不超過請求設置的最大跳，在上游節點中斷，可以選擇本地修復這條鏈路。為了解決這個鏈路，節點增加目的節點的序列號，并廣播一個到達目的節點的rreq分組，這個rreq的ttl被初始化為max(min_repair_ttl,0.5*#hops)+local_add_tt

47、l,#hops的意思是當前節點到達不可達數據包源節點的跳數。在本地修復期間，所有發往相關目的節點的數據包應該被緩存。如果在路徑發現周期結束后節點仍沒收到rrep或者其他相關控制信息，它就會發送rerr。如果它收到了rrep，它首先比較新路徑的跳數和原無效路徑的跳數，如果新路徑的跳數更大，節點將會發送設置了n標志位的rerr。當一個節點收到設置了n標志位的rerr，它必須不能刪除到相關目的節點的路由項，唯一能做的就是轉發rerr。當源節點收到rerr時，可能會選擇重啟路由發現。當鏈接被破壞，往往有多個目的節點的影響，但上游節點的鏈路數據包中斷只為本地修復目的節點，其它的相關路徑則被置為無效，但是

48、同時可能會被置為是可修復的，但是當該路徑計時結束后，本地修復標志位必須重設。在計時結束前，這些路徑在需要時將被修復，而如果沒有數據包使用到這條路徑，那么該路徑將不會被修復。又或者因為本地擁塞，節點也許會開始這些路徑本地修復的過程，而不需要等到新的數據包到達。這樣后來的使用到這些路徑的數據包就能夠立即被發送，而不需要受本地修復的延遲影響。但是這樣做可能會導致修復那些不再使用的路徑，因此節點可以選擇提前修復或者等到收到數據包才開始修復路徑。5 aodv的仿真模擬5.1 ns-2簡介ns是網絡模擬器的縮寫，是一種用于網絡仿真的優秀的仿真軟件，主要應用于ip網絡的仿真。該軟件最初開發是針對unix系統

49、，后應用于windows和unix/linux等系統，具有較好的開放性與擴展性。ns-2是ns的第二個版本，采用面向對象的結構。采用otcl和c+兩種面向對象的程序設計語言。c+用于實現程序模塊，otcl語言用于編寫腳本。結構圖如圖5.1所示：network componentsns.2tclclotcltclevent schedulerc/c+otcl：object.oriented tcltclcl：c+ and otcl linkage tcl圖5.1 ns2結構圖ns-2采用事件調度器與網絡組件庫，對c+對象進行配置。運用nsobject為網絡上組件的父類，而它本身的父類則是tclo

50、bject類，該類的對象具有處理數據包的功能9。所有的基本組件劃分為兩類，其一為分類器，其二為連接器。如圖5.2所示：圖5.2 ns2網絡組件分類圖 ns-2使用事件調度器來處理分組的時延并充當定時器，依據事件發生的時間的先后順序對其進行排序，并且根據其排列的順序進行下一步的工作。ns-2工作流程如下：首先采用otcl語言編寫腳本，其次運用ns仿真中的trace文件對數據進行保存，然后輸出仿真的結果，即可運用可視化的圖標對數據進行相關內容的分析。ns-2支持的網絡協議主要有：tcp、ip、udp、rtp/rtcp、srm、802.3、802.11、靜態單播協議、動態單播協議和多播路由協議。此外

51、還支持red、cbq、sfq等隊列和包的調度。同時也支持avod、dsdv、tora等ad hoc網絡路由協議以及directed diffusion（dd）、leach、gaf、aodv等無線傳感器網絡路由協議15。5.2 基于ns-2的aodv路由算法的仿真首先對問題進行分析，判斷是否需要修改源代碼。如需要修改則修改相應的otcl 源代碼，并進行重新編譯。若編譯通過則繼續編寫tcl仿真腳本，若不通過則繼續調試。這一步是修改代碼的額外工作量。如果不需要修改源代碼，直接的tcl/otcl仿真代碼的編寫，生成tcl腳本文件，并執行與ns2仿真腳本后會產生相應的跟蹤文件7。通過該文件，用戶可以對其

52、進行分析得到結果圖表。如果是預期的結果，那么仿真順利結束，否則，分析問題所在，并重新對該問題進行定義、源碼的修改、tcl腳本的修改。如圖5.3所示：圖5.3 ns.2 進行網絡仿真的基本流程5.3 aodv的仿真5.3.1 aodv仿真場景的設計仿真場景的設計包含兩種 ：一種為節點運動場景，另一種為網絡流量場景。所謂節點運動場景就是在仿真過程中的運行區域，節點移動的時間、移動節點的數目、各節點的運動事件。所謂網絡流量場景就是在無限傳感器網絡當中哪些節點需要進行什么樣的連接，采用什么樣的方式進行數據包的發送。本論文中是利用setdest隨機的生成無線傳感器網絡仿真需要的移動場景。首先，進入set

53、dest目錄。其次，在指令中輸入建立aodv所需要的參數，對參數進行設置。再者，在tcl中載入設置好的場景，對指定的參數值編寫腳本，運行aodv.tcl文件就可在可視窗口下看到節點建立的結果。(1) 生成網絡拓撲節點運動場景，定義了模擬仿真的過程中所需要的節點分布區域、節點數目、運行時間等信息。本論文利用tcl腳本程序在場景文件中設置了21個節點。proc getcmdargu argc argv /使用getcmdargu設置參數 global val for set i 0 $i $argc incr i set arg lindex $argv $i if string range $a

54、rg 0 0 != - continu/ /判斷數組中是否有- set name string range $arg 1 end set val($name) lindex $argv expr $i+1 getcmdargu $argc $argv /定義argc類型的數組在設置數組的信息時，會設置成為0_0 ? 0_1 ? 0_2 ?。(2) 生成數據流ns2提供了流量生成器腳本工具cbrgen.tcl，可以生成cbr流和tcp流。使用cbrgen.tcl可以自定義流量模型、節點數目、隨機種子、最大連接數和傳輸速率，ns2會按要求隨機生成流量場景文件。cbrgen.tcl的參數設置如下所示

55、:ns cbrgen.tcl -type cbr/poisson -nn nodes -seed seed -mc connection -rate rate本次試驗中設置數據流的流量類型為cbr，節點數目為21，所以執行:ns cbrgen.tcl -type cbr -nn 21 -seed 2 -mc 25 -rate 4則生成相應的數據流場景，命名為cbr.scn。 (3) 定義網絡參數網絡參數上的設置主要包括一下內容，節點分布區域、節點的初始能量、信號發射功率、信號接收功率、信道模型、mac層協議等進行設置。路由協議處于網絡層，需要把其余各層的參數固定下來，才能進行比較分析。下列tcl代碼對網絡參數進行了設置：set val(chan