引言
隨著通信技術、嵌入式計算技術和傳感器技術的飛速發展和日益成熟,具有感知能力、計算能力和通信能力的微型傳感器開始在世界范圍內出現。由這些微型傳感器構成的傳感器網絡引起了人們的極大關注。這種傳感器網絡綜合了傳感器技術、嵌入式計算技術、分布式信息處理技術和通信技術,能夠協作地實時監測、感知和采集網絡分布區域內的各種環境或監測對象的信息,并對這些信息進行處理,獲得詳盡而準確的信息,傳送到需要這些信息的用戶。本文在AODV路由協議的基礎上,提出了一種全新的路由協議—MSAODV協議,這種路由算法適合在微型無線傳感器網絡上使用。
2 MSAODV路由算法的基本思想與算法原理
2.1 路由算法的基本思想
在研究了AODV路由協議之后,本文提出了一種全新的路由算法,這種路由算法適合在微型無線傳感器網絡上使用,又由于是基于AODV路由協議之上,故稱之為MSAODV(Micro- Sensor Ad-hoc On- Demand Distance Vector Algorithm)路由協議。
無線傳感器網絡與傳統無線移動網絡有區別,無線傳感器網絡最關心的是整個網絡的成存周期,而傳統無線移動網主要關心的是網絡拓撲變化情況下可靠傳輸質量。微型無線傳感器網絡中的節點具有體積小,功耗小,通信距離短等特點,他們應用的場合非常廣泛,像戰場敵方信息采集,森林火災監控等,這些場合往往是一些無人區,傳感器節點拋撒到這些地方再回收的可能性非常小,所以節點的功耗決定了他的使用時間。針對這些特點,MSAODV路由算法采用了按需查詢方式,他簡單實用,易于擴充,協議開銷小,應用了這種路由算法傳感器節點大部分時間都可以處在睡眠狀態,這樣就延長了節點的使用時間,適合無線傳感器網絡的使用環境。
2.2 MSAODV路由算法原理
MSAODV路由協議算法是在AODV路由協議的基礎上改進演化而來的,他繼承了AODV路由算法的許多特點,但是又與AODV路由協議算法有所不同。無線傳感器網絡的體系結構將有助于設計MSAODV路由協議算法,圖1顯示了無線傳感器網絡的體系結構。
MSAODV路由算法同樣假設網絡中的所有鏈路都是雙向對稱的,即某個源節點通過一條路由可以到達無線網絡中的某個目的節點時,該目的節點同樣也可以通過這條路由的反向路由回到源節點。MSAODV路由協議同樣是一種按需的距離向量路由協議,具有按需路由協議的特點,網絡中的每個節點在需要進行通信時才發送路由分組,而不會周期性地交互路由信息以得到所有其它主機的路由:同時具有距離向量路由協議的一些特點,即各節點路由表只維護本節點到其他節點的路由,而無須掌握全網拓撲結構。
圖1 無線傳感器網絡體系結構
MSAODV路由協議中只有兩種類型的消息控制幀:路由請求RREQ和路由應答RREP。和AODV路由協議一樣,當源節點需要發送數據而又沒有到目的節點的有效路由時,啟動一個路由發現過程:向網絡廣播一個路由請求包RREQ,中間節點轉發該路由請求,收到請求的目的節點以單播的方式向源節點返回一個RREP包,RREP沿著剛建立的逆向路徑傳輸回源節點,源節點收到該RREP包后則開始向對應目的節點發送數據。在路由請求包的正向傳播過程中,網絡中能收到該路由請求的節點都建立起了到源節點的反向路由,當目的節點收到路由請求而回送路由應答時,逆向路徑上的節點又建立了前向路由。整個MSAODV路由發現過程如圖2所示,a圖表示的是反向路由的建立過程,節點S需要和節點D通信,但是他沒有節點D的路由,所以節點S發起到節點D的路由請求,節點S廣播一個路由請求包,收到路由請求包的節點轉發節點S的請求,最終節點D收到了節點S的路由請求包,這個過程建立了節點S到節點D的反向路由;b圖表示的是由節點S到節點D前向路由的建立過程,當節點D收到節點S的路由請求包后,他要給節點S回送一個路由應答包,順著剛才建立的反向路由,應答包最終被節點S成功接收,在此過程中節點S又建立了到節點D的前向路由。
圖2 MSAODV路由建立過程
3 MSAODV路由中的路由表與協議幀的格式
3.1 MSAODV路由協議路由表
網絡中的每一個節點都有這樣的一個路由表,該表保存了對應節點的路由信息,由于各個節點在網絡中的位置不同,因而他們的路由表項也不相同,例如在圖2(b)中,a節點的路由表有兩項,c節點的路由表也有兩項,如表1所示。
表1 相關路由表
由于MSAODV路由協議是AODV路由協議的改進演化,所以與AODV路由協議幀類似,MSAODV路由協議也包括RR衛Q協議幀和RREP協議幀,但不包含RERR協議幀。不包含RERR協議幀會導致MSAODV協議在路由維護和錯誤處理上功能欠缺,但可以通過其他方法來彌補這個缺陷。
1 RREQ協議幀格式
2 RREP協議幀格式
4 MSAODV路由協議的操作
由于MSAODV路由協議是對AODV協議的改進演化,所以MSAODV路由協議的操作與AODV路由協議的操作大同小異,為了清晰起見,對MSAODV協議的操作做一詳細的介紹還是有必要的。
4.1產生路由請求
無線網絡中某個節點需要和網絡中的另一個節點通信時,他首先會查找自己的路由表,以確定是否有通往該目的節點的有效路由,如果有的話,從對應的目的節點路由表項中取出下一跳節點地址,然后構造數據包并把該數據包發往下一節點,如果不存在通往目的節點的路由,那么該節點就要發起一次路由請求。
4.2處理和轉發路由請求
處理和轉發路由請求是針對源節點和目的節點之間的中間節點而言。這些中間節點可能不止一個,在他們收到源節點廣播的RREQ路由請求幀之后,必需處理和轉發該路由請求幀。
在某個中間節點接收到源節點廣播或者由其他節點轉發的RREQ請求幀后,他首先會判定該RREQ請求幀是否己經被成功接收過,判斷的依據就是源節點的IP地址和廣播ID號,如果發現由源節點和廣播ID唯一標志的RREQ請求幀是新的,也就是沒收到過,就會根據此RREQ請求幀更新自己路由表中對應的項。很顯然,該路由表項的目的節點IP字段就是是源節點IP地址,下一跳IP地址就是發送此RREQ請求幀的節點IP地址,有可能是源節點也有可能是另一個中間節點。接下來此中間節點判斷該RREQ請求幀的目的IP是不是就是自己,如果是就回送一個RREP回應幀,不是就轉發該RREQ請求幀。
4.3產生路由應答
RREQ經過中間節點的轉發到達目的節點或者是直接到達目的節點后,目的節點要進行相應的處理。
目的節點收到RREQ請求包,首先會判斷是否已經收到過此請求包,如果沒有收到過則更新自己相應的路由表項,目的節點把該路由表項的目的IP更新為源節點的IP地址,下一跳IP為發給他RR衛Q請求幀的節點IP,目的節點序列號填上源節點的序列號,該序列號在RREQ請求幀里,跳數直接從RREQ請求幀里拷貝。在確認請求的節點就是自己后,目的節點要給源節點發送一個RREP應答幀,接下來目的節點構造一個RREP應答幀并正確初始化該幀。類型字段為2,表示該幀是RREP應答幀。跳數字段為0,因為是目的節點發起的RREP應答幀。目的節點產生一個RREP應答包之前,必需更新自己的序列號,更新值為當前序列號與RREQ請求包中的目的序列號兩者中的最大值,目的序列號字段被初始化為這個最大值。源IP地址指的是發起RREQ請求幀的源節點的IP地址,而不是指目的節點的IP地址,同樣的,目的IP地址就是目的節點的IP地址,也就是發起RREP應答幀的節點IP地址。
在目的節點構造好RREP回應幀后,就要把該幀以單播的形式沿著反向路由傳送,他的下一跳節點IP地址是發給他RREQ請求幀的節點地址,可能是某個中間節點,也可能是源節點。一切準備就緒,目的節點按照退避算法發送該幀。
4.4接收和轉發路由應答
由于無線網絡的特點,盡管目的節點是以單播的形式向源節點回送RREP回應幀,但是網絡中的很多節點也能接收到該幀,當然,這些節點只是簡單的丟棄該幀,只有反向路由上的節點才會接收該RREP回應幀。反向路由上的節點會沿著反向路由順利的把RREP回應幀傳給源節點,同時他們也根據此RREP回應幀建立了前向路由。該節點下面要完成的工作就是把該RREP回應幀轉發出去。他要知道下一跳節點的IP地址,以RREP回應幀中的源節點IP地址為關鍵字查找路由表,得到下一跳節點的IP,這個表項是在建立反向路由時建立或更新的。該中間節點在完成上面的步驟后,以退避算法轉發該RREP回應幀。與RREQ請求幀的轉發不同,R.REP回應幀的轉發是單播的,他不會像R.REQ請求幀那樣可能被轉發多次,所以R.REP回應幀的字段里不存在廣播ID。
4.5新節點加入
無線傳感器網絡中的節點在開機或重啟之后,會向網絡廣播一個RESET消息,網絡中的其他節點收到此RESET消息后會轉發該幀,最后主節點收到該幀。新節點在RESET消息幀里攜帶自己的IP地址,這樣當主節點收到該幀后就可以知道是哪個節點重啟。
收到RESET消息幀的其他節點首先查找自己的路由表看是否有主節點的IP地址,如果有就以單播的形式發送該幀,反之則繼續廣播此RESET消息幀。每個節點都要保存上一次他收到的RESET消息幀中的源節點IP地址,下次再收到RESET消息幀首先要比較源IP地址是否和保存值相同,相同就不再轉發該幀,在經過一段時間后,將保存值清零,這樣就避免了重復轉發同一個RESET消息幀,又避免了不再轉發下次的RESET消息幀。
4.6其他操作
除了前文描述的產生路由請求、處理和轉發路由請求、產生路由應答、接收和轉發路由應答、新節點加入等主要操作外,MSAODV路由算法余下的操作可以參考第二章介紹的AODV路由算法。
5 本文作者創新點
AODV路由算法應用在無線傳感器網絡中有一定的局限性,不能很好得適合無線傳感器網絡的體系結構。以無線傳感器網絡與傳統移動無線網著重點不同為依據,本文提出了適合無線傳感器網絡的路由算法MSAODV,并詳細敘述分析了MSAODV路由算法。