基于AODV協議的無線傳感器網絡多路徑路由改進機制

貴彩虹

1 引言

由于AODV協議在存儲容量、算法復雜度、實用性以及拓撲變化適應性等方面表現出較優的性能，同時由于Adhoc網與無線傳感器網絡在網絡拓撲結構和數據傳輸中的相似性，近些年基于AODV協議的無線傳感器網絡的路由研究比較多。AODV協議在無線傳感器網絡的路由中使用單一路徑進行數據分組的傳輸，當需要數據傳輸時，節點首先得尋找一條到目的節點的路徑；若在數據傳輸中，一旦該路徑中某個節點或鏈路斷開，就需要重新進行路由發現，因此中間節點會因較大的傳輸延遲和一段時間內負載的相對集中，易出現能量較早耗盡而死亡，從而導致網絡拓撲不穩定，數據傳輸效率低的問題。在本文提出的改進方案中可使每個節點保存兩條最短路徑，當數據需要傳輸時，從這兩條最短路徑中選擇剩余能量多的下一跳節點作為中轉節點；如果遇到路徑斷鏈，可通過另一條路徑進行本地路由恢復；若這兩條最短路徑都失效，網絡才進行路由查找，同時對Hello機制進行改造，即通過定期發送Hello包不僅進行路由的監測，同時實現路由表中的路由能量值的更新。

2 AODV協議工作工程

2.1 路由的獲取

AODV協議采用廣播路由的機制按需發現路由，當源節點需要向目的節點發送數據時，它就廣播一條路由請求（RREQ）消息，中間節點通過分析收到的RREQ建立一條到達源節點的反向路由，同時轉發該RREQ消息。收到RREQ消息的目的節點向源節點發送路由應答（RREP）消息以建立正向路由。如果源節點在超時前沒有收到RREP消息，它采用擴展環機制重新廣播一條新的RREQ消息，直到超過最大重新廣播次數，仍沒有任何RREP，則應該將所有對應目的節點的數據分組從緩存中丟棄。

2.2 路由的保持

路由建立以后，如果在路由過期時間內沒有被使用，或者節點確定的有效路由的下一跳無法到達時，該路由無效，便將一條出錯（RERR）消息向所有將此節點作為下一跳節點的相鄰節點廣播并在本節點路由表中標記相應路由信息為無效。同時，AODV路由協議通過廣播HELLO消息來監視鏈路連通性，實現有效路由的保持。當節點監測到某一條路由無效時，它將該路由從路由表中刪除并廣播路由出錯分組RERR，收到RERR的中間節點將路由表中相應路由設置為無效，并采用相同的原則繼續廣播RERR，源節點收到RERR后重新啟動路由發現過程。

2.3 路由的維護

如果一條活動路由上發生鏈路中斷，則這個節點可能會選擇在本地修復。為了修復鏈路，節點增加目的節點的序列號，然后廣播關于目的節點的RREQ進行路由發現，在本地修復過程中數據分組需緩存。如果路由查找周期結束節點仍然沒有收到關于目的節點的RREP，則發送該節點的RERR。

3 AODV的改進方案

為了有效利用兩條最短路徑減少時延、降低開銷，本文在AODV路由表中加入了兩個字段，同時進行了三方面的改進：多路徑路由的建立、多路徑路由的保持和維護。

3.1 RREQ、RREP和HELLO消息與路由表的改進

路由表中新添加了zdf_cout、zdz_cout和energy三個字段。

RREQ、RREP和HELLO消息中分別添加了zdf_energy、zdz_energy和he_energy字段。這三個字段分別標識收到RREQ、RREP或者HELLO消息的節點的前一跳節點的剩余能量，其值由節點自動產生。

zdf_cout字段用于標識路由表中反向路徑的條數，其初值為0。

zdz_count字段用于標識路由表中正向路徑的條數，其初值為0。

energy字段用于標識節點兩條正向、反向最短路徑的剩余能量。其值是在向路由表進行正、反向路由添加時從相應RREQ、RREP或者HELLO消息的各自能量字段復制得到。

3.2 多路徑路由的建立

根據AODV，當啟動了路由查找，收到RREQ的節點進行消息分析，首先判斷此消息是不是自己產生，若是就丟棄，否則看之前有沒有收到過此分組，若是就丟棄，否則將收到的廣播分組存入Broadcase ID Cache中，接下來便通過本文改進的字段進行兩條最短路徑的選擇，即查看路由表中的zdf_cout字段，如果其值小于等于2，則把RREQ中的相關信息按照AODV協議添加為路由表的反向路由，并給zdf_cout加1；否則用RREQ中的序號和跳數與路由表中與其消息具有相同目的節點的反向路由條目的相應字段比較，若RREQ中的序號大于路由表中的兩條最短路徑中任意一條的序號，或者在序號相同的情況下，RREQ中的跳數小于路由表中兩條最短路徑跳數中任意一條的跳數值，就將RREQ的相關信息存入路由表代替序號最小或者序號相同的情況下跳數最大的反向路由。同理，在RREQ發送至目標節點，目標節點回復路由應答時，即查看節點路由表中zdz_cout字段，如果其值小于等于2，則把RREP中的相關信息添加為路由表的正向路由，zdz_cout加1；否則用RREP中的序號和跳數與路由表中與其消息具有相同目的節點的正向路由條目的相應字段比較，若RREP中的序號大于路由表中的兩條最短路徑中任意一條的序號，或者在序號相同的情況下，RREP中的跳數小于路由表中兩條最短路徑任意一條跳數的值，就將RREP的相關信息存入路由表代替序號最小，或者序號相同的情況下跳數最大的正向路由。剩下的路由發現過程與AODV的相同。

3.3 多路徑路由的保持和維護

路由建立以后，節點進行數據分組傳輸時，根據數據分組是傳給源節點還是目的節點，選擇路由表中兩條正向或者反向路由中energy值大的下一跳節點進行轉發。如果在活動路由上發生了鏈路中斷，節點選擇路由表中到達目的節點的另一條最短路徑中下一跳節點進行數據轉發，從而實現正向或者反向路由本地路由恢復，同時設置當前節點的此路由為無效。當遇到兩條最短路徑同時失效，才由當前節點發出RREQ，啟動路由發現過程，以便路徑及時恢復、數據分組及時傳輸。AODV協議定時發送HELLO消息，收到此消息的節點，不僅更新自己的鄰居表或者有效期限，同時通過Hello消息中的he_energy字段，更新路由表中相應energy值。除此以外的路由保持和維護過程與AODV的相同。

4 改進方案的仿真及性能分析

傳統的AODV協議，只有一條傳輸路徑，如果路由斷鏈，數據分組的轉發只能等到路由重新獲取成功才能進行，所以傳輸的延遲大，本文采用了多路徑機制，提出的兩條最短路徑選擇方案，除了選取了兩條跳數最小、最新的傳輸路徑外，還保證了當其中一條路徑斷鏈便可在本地啟用另一條路徑，使傳輸路徑得到及時修復的作用，從而減少了傳輸路徑上的延遲（如圖1）。

圖1 各節點能量變化值

同時，只有這兩條最短路徑都失效，節點才進行路由發現，從而也減少了原AODV協議中路由發現的次數，有效地降低開銷。在數據分組進行傳輸時，選用兩條路徑中剩余能量最大（能耗小）的下一條節點，避免了采用本方案可能存在的因節點相交而導致的某中間節點長期使用而過大的能量消耗，實現了中間節點能量均衡的目的（如圖2）。

圖2 端到端的延遲

5 結束語

本文引入的多路由機制，采用了兩條最短路徑保證數據分組的有效傳輸，減少了路由發現的次數，并且通過選用能量大的節點進行數據轉發，實現了對能耗大的節點的能量均衡，從而可提高網絡的傳輸效率。為了進一步提高基于AODV協議的無線傳感器網絡的傳輸效率，下一步工作將著眼于考慮數據分組傳輸所需的整條路徑上的能耗均衡情況。