貴彩虹

1 引言

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

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

2.1 路由的獲取

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

2.2 路由的保持

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

2.3 路由的維護(hù)

如果一條活動(dòng)路由上發(fā)生鏈路中斷，則這個(gè)節(jié)點(diǎn)可能會(huì)選擇在本地修復(fù)。為了修復(fù)鏈路，節(jié)點(diǎn)增加目的節(jié)點(diǎn)的序列號(hào)，然后廣播關(guān)于目的節(jié)點(diǎn)的RREQ進(jìn)行路由發(fā)現(xiàn)，在本地修復(fù)過(guò)程中數(shù)據(jù)分組需緩存。如果路由查找周期結(jié)束節(jié)點(diǎn)仍然沒(méi)有收到關(guān)于目的節(jié)點(diǎn)的RREP，則發(fā)送該節(jié)點(diǎn)的RERR。

3 AODV的改進(jìn)方案

為了有效利用兩條最短路徑減少時(shí)延、降低開(kāi)銷(xiāo)，本文在AODV路由表中加入了兩個(gè)字段，同時(shí)進(jìn)行了三方面的改進(jìn)：多路徑路由的建立、多路徑路由的保持和維護(hù)。

3.1 RREQ、RREP和HELLO消息與路由表的改進(jìn)

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

RREQ、RREP和HELLO消息中分別添加了zdf_energy、zdz_energy和he_energy字段。這三個(gè)字段分別標(biāo)識(shí)收到RREQ、RREP或者HELLO消息的節(jié)點(diǎn)的前一跳節(jié)點(diǎn)的剩余能量，其值由節(jié)點(diǎn)自動(dòng)產(chǎn)生。

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

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

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

3.2 多路徑路由的建立

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

3.3 多路徑路由的保持和維護(hù)

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

4 改進(jìn)方案的仿真及性能分析

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

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

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

圖2 端到端的延遲

5 結(jié)束語(yǔ)

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