基于AODV協(xié)議的無線傳感器網(wǎng)絡(luò)多路徑路由改進機制

貴彩虹

1 引言

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

2 AODV協(xié)議工作工程

2.1 路由的獲取

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

2.2 路由的保持

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

2.3 路由的維護

如果一條活動路由上發(fā)生鏈路中斷，則這個節(jié)點可能會選擇在本地修復(fù)。為了修復(fù)鏈路，節(jié)點增加目的節(jié)點的序列號，然后廣播關(guān)于目的節(jié)點的RREQ進行路由發(fā)現(xiàn)，在本地修復(fù)過程中數(shù)據(jù)分組需緩存。如果路由查找周期結(jié)束節(jié)點仍然沒有收到關(guān)于目的節(jié)點的RREP，則發(fā)送該節(jié)點的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消息的節(jié)點的前一跳節(jié)點的剩余能量，其值由節(jié)點自動產(chǎn)生。

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

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

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

3.2 多路徑路由的建立

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

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

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

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

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

圖1 各節(jié)點能量變化值

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

圖2 端到端的延遲

5 結(jié)束語

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