2 MSAODV 路由算法的基本思想與算法原理

　　2.1 路由算法的基本思想

　　在研究了 AODV 路由協(xié)議之后,本文提出了一種全新的路由算法,這種路由算法適合在 微型無線傳感器網絡上使用,又由于是基于AODV 路由協(xié)議之上,故稱之為MSAODV(Micro- Sensor Ad-hoc On-Demand Distance Vector Algorithm)路由協(xié)議。

　　無線傳感器網絡與傳統(tǒng)無線移動網絡有區(qū)別,無線傳感器網絡最關心的是整個網絡的成 存周期,而傳統(tǒng)無線移動網主要關心的是網絡拓撲
網絡拓撲

　　通常將網絡中的主機、終端和其他通信控制與處理設備抽象為結點；將通信線路抽象為線路，而將結點和線路連接而成的幾何圖形稱為網絡的拓撲結構。網絡拓撲結構可以反映出網絡中各實體之間的結構關系。

變化情況下可靠傳輸質量。微型無線傳感 器網絡中的節(jié)點具有體積小,功耗小,通信距離短等特點,他們應用的場合非常廣泛,像戰(zhàn)場敵 方信息采集,森林火災監(jiān)控等,這些場合往往是一些無人區(qū),傳感器節(jié)點拋撒到這些地方再回 收的可能性非常小,所以節(jié)點的功耗決定了他的使用時間。針對這些特點,MSAODV 路由算 法采用了按需查詢方式,他簡單實用,易于擴充,協(xié)議開銷小,應用了這種路由算法傳感器節(jié)點 大部分時間都可以處在睡眠狀態(tài),這樣就延長了節(jié)點的使用時間,適合無線傳感器網絡的使用 環(huán)境。

　　2.2 MSAODV 路由算法原理

　　MSAODV 路由協(xié)議算法是在AODV 路由協(xié)議的基礎上改進演化而來的,他繼承了AODV 路由算法的許多特點,但是又與AODV 路由協(xié)議算法有所不同。無線傳感器網絡的體 系結構將有助于設計MSAODV 路由協(xié)議算法,圖1 顯示了無線傳感器網絡的體系結構。

　　MSAODV 路由算法同樣假設網絡中的所有鏈路都是雙向對稱的,即某個源節(jié)點通過一 條路由可以到達無線網絡中的某個目的節(jié)點時,該目的節(jié)點同樣也可以通過這條路由的反向 路由回到源節(jié)點。MSAODV 路由協(xié)議同樣是一種按需的距離向量路由協(xié)議,具有按需路由協(xié) 議的特點,網絡中的每個節(jié)點在需要進行通信時才發(fā)送路由分組,而不會周期性地交互路由信 息以得到所有其它主機的路由:同時具有距離向量路由協(xié)議的一些特點,即各節(jié)點路由表只維 護本節(jié)點到其他節(jié)點的路由,而無須掌握全網拓撲結構。

　　MSAODV 路由協(xié)議中只有兩種類型的消息控制幀:路由請求RREQ 和路由應答RREP。 和AODV 路由協(xié)議一樣,當源節(jié)點需要發(fā)送數據而又沒有到目的節(jié)點的有效路由時,啟動一 個路由發(fā)現過程:向網絡廣播一個路由請求包RREQ,中間節(jié)點轉發(fā)該路由請求,收到請求的目 的節(jié)點以單播的方式向源節(jié)點返回一個RREP 包,RREP 沿著剛建立的逆向路徑傳輸回源節(jié) 點,源節(jié)點收到該RREP 包后則開始向對應目的節(jié)點發(fā)送數據。在路由請求包的正向傳播過 程中,網絡中能收到該路由請求的節(jié)點都建立起了到源節(jié)點的反向路由,當目的節(jié)點收到路由 請求而回送路由應答時,逆向路徑上的節(jié)點又建立了前向路由。整個MSAODV 路由發(fā)現過 程如圖2 所示,a 圖表示的是反向路由的建立過程,節(jié)點S 需要和節(jié)點D 通信,但是他沒有節(jié)點 D 的路由,所以節(jié)點S 發(fā)起到節(jié)點D 的路由請求,節(jié)點S 廣播一個路由請求包,收到路由請求包 的節(jié)點轉發(fā)節(jié)點S 的請求,最終節(jié)點D 收到了節(jié)點S 的路由請求包,這個過程建立了節(jié)點S 到 節(jié)點D 的反向路由;b 圖表示的是由節(jié)點S 到節(jié)點D 前向路由的建立過程,當節(jié)點D 收到節(jié)點 S 的路由請求包后,他要給節(jié)點S 回送一個路由應答包,順著剛才建立的反向路由,應答包最終 被節(jié)點S 成功接收,在此過程中節(jié)點S 又建立了到節(jié)點D 的前向路由。

　　3 MSAODV 路由中的路由表與協(xié)議幀的格式

　　3.1 MSAODV 路由協(xié)議路由表

　　網絡中的每一個節(jié)點都有這樣的一個路由表,該表保存了對應節(jié)點的路由信息,由于各個 節(jié)點在網絡中的位置不同,因而他們的路由表項也不相同,例如在圖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é)議幀會導致MSAODV 協(xié)議在路由維護和錯誤處理上功能欠缺,但可以通過其 他方法來彌補這個缺陷。

　　1 RREQ 協(xié)議幀格式

　　RREQ 路由請求協(xié)議幀如表2 所示。