2 MSAODV 路由算法的基本思想與算法原理
　　2.1 路由算法的基本思想
　　在研究了 AODV 路由協(xié)議之后，本文提出了一種全新的路由算法，這種路由算法適合在微型無線傳感器網(wǎng)絡(luò)上使用，又由于是基于AODV 路由協(xié)議之上，故稱之為MSAODV（Micro-Sensor Ad-hoc On-Demand Distance Vector Algorithm）路由協(xié)議。
　　無線傳感器網(wǎng)絡(luò)與傳統(tǒng)無線移動網(wǎng)絡(luò)有區(qū)別，無線傳感器網(wǎng)絡(luò)關(guān)心的是整個網(wǎng)絡(luò)的成存周期，而傳統(tǒng)無線移動網(wǎng)主要關(guān)心的是網(wǎng)絡(luò)拓撲變化情況下可靠傳輸質(zhì)量。微型無線傳感器網(wǎng)絡(luò)中的節(jié)點具有體積小，功耗小，通信距離短等特點，他們應(yīng)用的場合非常廣泛，像戰(zhàn)場敵方信息采集，森林火災(zāi)監(jiān)控等，這些場合往往是一些無人區(qū)，傳感器節(jié)點拋撒到這些地方再回收的可能性非常小，所以節(jié)點的功耗決定了他的使用時間。針對這些特點，MSAODV 路由算法采用了按需查詢方式，他簡單實用，易于擴充，協(xié)議開銷小，應(yīng)用了這種路由算法傳感器節(jié)點大部分時間都可以處在睡眠狀態(tài)，這樣就延長了節(jié)點的使用時間，適合無線傳感器網(wǎng)絡(luò)的使用環(huán)境。
　　2.2 MSAODV 路由算法原理
　　MSAODV 路由協(xié)議算法是在AODV 路由協(xié)議的基礎(chǔ)上改進演化而來的，他繼承了AODV 路由算法的許多特點，但是又與AODV 路由協(xié)議算法有所不同。無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)將有助于設(shè)計MSAODV 路由協(xié)議算法，圖1 顯示了無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)。
　　

　　MSAODV 路由算法同樣假設(shè)網(wǎng)絡(luò)中的所有鏈路都是雙向?qū)ΨQ的，即某個源節(jié)點通過一條路由可以到達無線網(wǎng)絡(luò)中的某個目的節(jié)點時，該目的節(jié)點同樣也可以通過這條路由的反向路由回到源節(jié)點。MSAODV 路由協(xié)議同樣是一種按需的距離向量路由協(xié)議，具有按需路由協(xié)議的特點，網(wǎng)絡(luò)中的每個節(jié)點在需要進行通信時才發(fā)送路由分組，而不會周期性地交互路由信息以得到所有其它主機的路由：同時具有距離向量路由協(xié)議的一些特點，即各節(jié)點路由表只維護本節(jié)點到其他節(jié)點的路由，而無須掌握全網(wǎng)拓撲結(jié)構(gòu)。
　　MSAODV 路由協(xié)議中只有兩種類型的消息控制幀：路由請求RREQ 和路由應(yīng)答RREP。
　　和AODV 路由協(xié)議一樣，當(dāng)源節(jié)點需要發(fā)送數(shù)據(jù)而又沒有到目的節(jié)點的有效路由時，啟動一個路由發(fā)現(xiàn)過程：向網(wǎng)絡(luò)廣播一個路由請求包RREQ,中間節(jié)點轉(zhuǎn)發(fā)該路由請求，收到請求的目的節(jié)點以單播的方式向源節(jié)點返回一個RREP 包，RREP 沿著剛建立的逆向路徑傳輸回源節(jié)點，源節(jié)點收到該RREP 包后則開始向?qū)?yīng)目的節(jié)點發(fā)送數(shù)據(jù)。在路由請求包的正向傳播過程中，網(wǎng)絡(luò)中能收到該路由請求的節(jié)點都建立起了到源節(jié)點的反向路由，當(dāng)目的節(jié)點收到路由請求而回送路由應(yīng)答時，逆向路徑上的節(jié)點又建立了前向路由。整個MSAODV 路由發(fā)現(xiàn)過程如圖2 所示，a 圖表示的是反向路由的建立過程，節(jié)點S 需要和節(jié)點D 通信，但是他沒有節(jié)點D 的路由，所以節(jié)點S 發(fā)起到節(jié)點D 的路由請求，節(jié)點S 廣播一個路由請求包，收到路由請求包的節(jié)點轉(zhuǎn)發(fā)節(jié)點S 的請求，終節(jié)點D 收到了節(jié)點S 的路由請求包，這個過程建立了節(jié)點S 到節(jié)點D 的反向路由；b 圖表示的是由節(jié)點S 到節(jié)點D 前向路由的建立過程，當(dāng)節(jié)點D 收到節(jié)點S 的路由請求包后，他要給節(jié)點S 回送一個路由應(yīng)答包，順著剛才建立的反向路由，應(yīng)答包終被節(jié)點S 成功接收，在此過程中節(jié)點S 又建立了到節(jié)點D 的前向路由。
　　MSAODV路由算法的原理及在無線傳感器網(wǎng)絡(luò)方面的應(yīng)用
　　3 MSAODV 路由中的路由表與協(xié)議幀的格式
　　3.1 MSAODV 路由協(xié)議路由表
　　網(wǎng)絡(luò)中的每一個節(jié)點都有這樣的一個路由表，該表保存了對應(yīng)節(jié)點的路由信息，由于各個節(jié)點在網(wǎng)絡(luò)中的位置不同，因而他們的路由表項也不相同，例如在圖2（b）中，a 節(jié)點的路由表有兩項，c 節(jié)點的路由表也有兩項，如表1 所示。
　　

　　3.2 MSAODV 路由協(xié)議幀格式
　　由于 MSAODV 路由協(xié)議是AODV 路由協(xié)議的改進演化，所以與AODV 路由協(xié)議幀類似，MSAODV 路由協(xié)議也包括RR 衛(wèi)Q 協(xié)議幀和RREP 協(xié)議幀，但不包含RERR 協(xié)議幀。不包含RERR 協(xié)議幀會導(dǎo)致MSAODV 協(xié)議在路由維護和錯誤處理上功能欠缺，但可以通過其他方法來彌補這個缺陷。
　　RREQ 協(xié)議幀格式
　　RREQ 路由請求協(xié)議幀如表2 所示。
　

　　RREP 協(xié)議幀格式
　　RREP 路由應(yīng)答協(xié)議幀如表3 所示。

　　　4 MSAODV 路由協(xié)議的操作
　　由于MSAODV 路由協(xié)議是對AODV 協(xié)議的改進演化，所以MSAODV 路由協(xié)議的操作與AODV 路由協(xié)議的操作大同小異，為了清晰起見，對MSAODV 協(xié)議的操作做一詳細的介紹還是有必要的。
　　4.1 產(chǎn)生路由請求
　　無線網(wǎng)絡(luò)中某個節(jié)點需要和網(wǎng)絡(luò)中的另一個節(jié)點通信時，他首先會查找自己的路由表，以確定是否有通往該目的節(jié)點的有效路由，如果有的話，從對應(yīng)的目的節(jié)點路由表項中取出下一跳節(jié)點地址，然后構(gòu)造數(shù)據(jù)包并把該數(shù)據(jù)包發(fā)往下一節(jié)點，如果不存在通往目的節(jié)點的路由，那么該節(jié)點就要發(fā)起路由請求。
　　4.2 處理和轉(zhuǎn)發(fā)路由請求
　　處理和轉(zhuǎn)發(fā)路由請求是針對源節(jié)點和目的節(jié)點之間的中間節(jié)點而言。這些中間節(jié)點可能不止一個，在他們收到源節(jié)點廣播的RREQ 路由請求幀之后，必需處理和轉(zhuǎn)發(fā)該路由請求幀。
　　該RREQ 請求幀是否己經(jīng)被成功接收過，判斷的依據(jù)就是源節(jié)點的IP 地址和廣播ID 號，如果發(fā)現(xiàn)由源節(jié)點和廣播ID 標(biāo)志的RREQ 請求幀是新的，也就是沒收到過，就會根據(jù)此RREQ 請求幀更新自己路由表中對應(yīng)的項。很顯然，該路由表項的目的節(jié)點IP 字段就是是源節(jié)點IP 地址，下一跳IP 地址就是發(fā)送此RREQ 請求幀的節(jié)點IP 地址，有可能是源節(jié)點也有可能是另一個中間節(jié)點。接下來此中間節(jié)點判斷該RREQ 請求幀的目的IP 是不是就是自己，如果是就回送一個RREP 回應(yīng)幀，不是就轉(zhuǎn)發(fā)該RREQ 請求幀。
　　4.3 產(chǎn)生路由應(yīng)答
　　RREQ 經(jīng)過中間節(jié)點的轉(zhuǎn)發(fā)到達目的節(jié)點或者是直接到達目的節(jié)點后，目的節(jié)點要進行相應(yīng)的處理。
　　目的節(jié)點收到 RREQ 請求包，首先會判斷是否已經(jīng)收到過此請求包，如果沒有收到過則更新自己相應(yīng)的路由表項，目的節(jié)點把該路由表項的目的IP 更新為源節(jié)點的IP 地址，下一跳IP為發(fā)給他RR 衛(wèi)Q 請求幀的節(jié)點IP,目的節(jié)點序列號填上源節(jié)點的序列號，該序列號在RREQ請求幀里，跳數(shù)直接從RREQ 請求幀里拷貝。在確認請求的節(jié)點就是自己后，目的節(jié)點要給源節(jié)點發(fā)送一個RREP 應(yīng)答幀，接下來目的節(jié)點構(gòu)造一個RREP 應(yīng)答幀并正確初始化該幀。類型字段為2,表示該幀是RREP 應(yīng)答幀。跳數(shù)字段為0,因為是目的節(jié)點發(fā)起的RREP 應(yīng)答幀。
　　目的節(jié)點產(chǎn)生一個RREP 應(yīng)答包之前，必需更新自己的序列號，更新值為當(dāng)前序列號與RREQ請求包中的目的序列號兩者中的值，目的序列號字段被初始化為這個值。源IP 地址指的是發(fā)起RREQ 請求幀的源節(jié)點的IP 地址，而不是指目的節(jié)點的IP 地址，同樣的，目的IP地址就是目的節(jié)點的IP 地址，也就是發(fā)起RREP 應(yīng)答幀的節(jié)點IP 地址。
　　在目的節(jié)點構(gòu)造好 RREP 回應(yīng)幀后，就要把該幀以單播的形式沿著反向路由傳送，他的下一跳節(jié)點IP 地址是發(fā)給他RREQ 請求幀的節(jié)點地址，可能是某個中間節(jié)點，也可能是源節(jié)點。
　　一切準(zhǔn)備就緒，目的節(jié)點按照退避算法發(fā)送該幀。
　　4.4 接收和轉(zhuǎn)發(fā)路由應(yīng)答
　　由于無線網(wǎng)絡(luò)的特點，盡管目的節(jié)點是以單播的形式向源節(jié)點回送RREP 回應(yīng)幀，但是網(wǎng)絡(luò)中的很多節(jié)點也能接收到該幀，當(dāng)然，這些節(jié)點只是簡單的丟棄該幀，只有反向路由上的節(jié)點才會接收該RREP 回應(yīng)幀。反向路由上的節(jié)點會沿著反向路由順利的把RREP 回應(yīng)幀傳給源節(jié)點，同時他們也根據(jù)此RREP 回應(yīng)幀建立了前向路由。該節(jié)點下面要完成的工作就是把該RREP 回應(yīng)幀轉(zhuǎn)發(fā)出去。他要知道下一跳節(jié)點的IP 地址，以RREP 回應(yīng)幀中的源節(jié)點IP地址為關(guān)鍵字查找路由表，得到下一跳節(jié)點的IP,這個表項是在建立反向路由時建立或更新的。該中間節(jié)點在完成上面的步驟后，以退避算法轉(zhuǎn)發(fā)該RREP 回應(yīng)幀。與RREQ 請求幀的轉(zhuǎn)發(fā)不同，R.REP 回應(yīng)幀的轉(zhuǎn)發(fā)是單播的，他不會像R.REQ 請求幀那樣可能被轉(zhuǎn)發(fā)多次，所以R.REP 回應(yīng)幀的字段里不存在廣播ID。
　　4.5 新節(jié)點加入
　　無線傳感器網(wǎng)絡(luò)中的節(jié)點在開機或重啟之后，會向網(wǎng)絡(luò)廣播一個RESET 消息，網(wǎng)絡(luò)中的其他節(jié)點收到此RESET 消息后會轉(zhuǎn)發(fā)該幀，主節(jié)點收到該幀。新節(jié)點在RESET 消息幀里攜帶自己的IP 地址，這樣當(dāng)主節(jié)點收到該幀后就可以知道是哪個節(jié)點重啟。
　　收到 RESET 消息幀的其他節(jié)點首先查找自己的路由表看是否有主節(jié)點的IP 地址，如果有就以單播的形式發(fā)送該幀，反之則繼續(xù)廣播此RESET 消息幀。每個節(jié)點都要保存上他收到的RESET 消息幀中的源節(jié)點IP 地址，下次再收到RESET 消息幀首先要比較源IP 地址是否和保存值相同，相同就不再轉(zhuǎn)發(fā)該幀，在經(jīng)過一段時間后，將保存值清零，這樣就避免了重復(fù)轉(zhuǎn)發(fā)同一個RESET 消息幀，又避免了不再轉(zhuǎn)發(fā)下次的RESET 消息幀。
　　4.6 其他操作
　　除了前文描述的產(chǎn)生路由請求、處理和轉(zhuǎn)發(fā)路由請求、產(chǎn)生路由應(yīng)答、接收和轉(zhuǎn)發(fā)路由應(yīng)答、新節(jié)點加入等主要操作外，MSAODV 路由算法余下的操作可以參考第二章介紹的AODV 路由算法。