針對現(xiàn)有Epidemic路由協(xié)議及其特點(diǎn)進(jìn)行了研究。分析了請求定位技術(shù)并將其引入到Epdemic協(xié)議中。改進(jìn)后的新協(xié)議通過記錄歷史路由信息，對傳輸數(shù)據(jù)定位接收，限制了數(shù)據(jù)的洪泛范圍。仿真結(jié)果表明，新協(xié)議在數(shù)據(jù)到達(dá)率與資源消耗上有了較大改善。
關(guān) 鍵 詞 移動(dòng)自組織網(wǎng)絡(luò); 路由協(xié)議; 洪泛; 請求定位

現(xiàn)有Ad hoc網(wǎng)絡(luò)中的路由協(xié)議通常基于以下假設(shè)：從源端到目的端總是可以找到一條通路。但是，隨著低功率小范圍無線通信設(shè)備的大量應(yīng)用，以及無線通信技術(shù)部署的場景越來越廣闊，上述假設(shè)在實(shí)際應(yīng)用中經(jīng)常無法得到滿足。這種源端－目的端非連通的Ad hoc網(wǎng)絡(luò)稱作稀疏Ad hoc網(wǎng)絡(luò)。在稀疏Ad hoc網(wǎng)絡(luò)中，傳統(tǒng)Ad hoc路由協(xié)議已經(jīng)很難實(shí)現(xiàn)數(shù)據(jù)的正常傳輸[1]。
文獻(xiàn)[1]提出的Epidemic路由協(xié)議解決了稀疏Ad hoc網(wǎng)絡(luò)中的數(shù)據(jù)傳輸問題。Epidemic算法最初被用于解決大型異構(gòu)網(wǎng)絡(luò)中的數(shù)據(jù)庫復(fù)制問題。文獻(xiàn)[1]將Epidemic算法的設(shè)計(jì)思路引入到Ad hoc網(wǎng)絡(luò)的路由協(xié)議中，Epidemic路由協(xié)議設(shè)計(jì)所針對的下層Ad hoc網(wǎng)絡(luò)連通性極為“苛刻”：(1) 數(shù)據(jù)發(fā)送方不知道接收方的當(dāng)前位置和數(shù)據(jù)發(fā)送應(yīng)該如何選路；(2) 任意兩個(gè)無線移動(dòng)節(jié)點(diǎn)都是隨機(jī)地進(jìn)入對方的通信范圍。因此在大規(guī)模隨機(jī)移動(dòng)場景中，Epidemic路由協(xié)議能夠獲得較好的性能。
1 Epidemic路由協(xié)議簡介
事實(shí)上，只要Ad hoc網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠充分隨機(jī)移動(dòng)，Epidemic路由協(xié)議就能夠?qū)崿F(xiàn)數(shù)據(jù)到任意目的端的傳輸。Epidemic路由協(xié)議的工作原理如下所述：Ad hoc網(wǎng)絡(luò)中的每個(gè)移動(dòng)節(jié)點(diǎn)有一個(gè)緩存來存儲(chǔ)數(shù)據(jù)。為了提高效率，注入網(wǎng)絡(luò)中的每一個(gè)數(shù)據(jù)都有一個(gè)全局標(biāo)識(shí)符，節(jié)點(diǎn)以該標(biāo)識(shí)符為鍵值，為緩存中的所有數(shù)據(jù)建立了一張哈希索引表。同時(shí)，節(jié)點(diǎn)還維護(hù)一個(gè)一維比特?cái)?shù)組(Summary Vector，SV)，用來標(biāo)識(shí)哈希表中每一項(xiàng)的“有”或“無”。
當(dāng)移動(dòng)節(jié)點(diǎn)A進(jìn)入到B通信范圍后(連通)，數(shù)據(jù)通信過程由以下4個(gè)階段完成：
(1) 節(jié)點(diǎn)A向B發(fā)送自己的SVA(Summary Vector)；
(2) B收到SVA后，會(huì)和自己維護(hù)的SVB(Summary Vector)進(jìn)行比較，由此來判斷哪些數(shù)據(jù)被N存儲(chǔ)而自己沒有，這些數(shù)據(jù)的集合為MA，MA=(m1，m2，…，ms)比較完成以后，B會(huì)向A發(fā)送信息來請求獲取MA；
(3) A根據(jù)B的請求信息逐條發(fā)送數(shù)據(jù)；
(4) B接收到A發(fā)送的數(shù)據(jù)并更新SVB。
上述4個(gè)階段過程完成了A向B的數(shù)據(jù)傳輸，反過來B也會(huì)按照這四個(gè)階段來完成向A的數(shù)據(jù)傳輸。在Epidemic協(xié)議中規(guī)定：數(shù)據(jù)的接收方全權(quán)決定是否接受數(shù)據(jù)并保存到緩存，而數(shù)據(jù)的發(fā)送方無權(quán)拒絕對方的請求。比如，它可以拒絕接受長度過大或者發(fā)往某些源端的數(shù)據(jù)。圖1為Epidemic路由協(xié)議中的節(jié)點(diǎn)A到B的數(shù)據(jù)傳輸過程，圖中f1為SVA；f2為B的數(shù)據(jù)請求信息；f3為A根據(jù)請求發(fā)送的數(shù)據(jù)。
A
Epidemic路由協(xié)議之所以被稱作“Epidemic”，是因?yàn)閿?shù)據(jù)是以類似于病毒的“接觸－感染”方式在整個(gè)網(wǎng)絡(luò)中“傳染”的。從全網(wǎng)角度來說，Epidemic協(xié)議所采取的是一種洪泛機(jī)制。Epidemic路由協(xié)議中數(shù)據(jù)轉(zhuǎn)發(fā)所獲得的較高到達(dá)率和較低延時(shí)犧牲了無線網(wǎng)絡(luò)帶寬和移動(dòng)節(jié)點(diǎn)存儲(chǔ)空間，增加了移動(dòng)節(jié)點(diǎn)的運(yùn)行功耗。因此，需要對Epidemic路由協(xié)議進(jìn)行改進(jìn)以減少移動(dòng)節(jié)點(diǎn)存儲(chǔ)空間的占用率。

2 Epidemic協(xié)議中引入定位技術(shù)
請求定位(Query Localization，QLI)技術(shù)最初被用于改進(jìn)DSR和AODV這兩種Ad hoc網(wǎng)絡(luò)中的按需路由協(xié)議。它的提出基于以下概念：一定時(shí)間內(nèi)移動(dòng)節(jié)點(diǎn)的移動(dòng)范圍是有限的，因此可以預(yù)計(jì)目的節(jié)點(diǎn)會(huì)以較高概率出現(xiàn)在先前出現(xiàn)位置的附近區(qū)域。通過保存近期的路由記錄，可以在路由建立過程中將路由請求信息的洪泛區(qū)域限制在最近一次選路的附近區(qū)域[2]。
Epidemic協(xié)議由于完全采用“存儲(chǔ)－轉(zhuǎn)發(fā)”機(jī)制，并沒有傳統(tǒng)路由協(xié)議中的路由請求與路由建立過程。將請求定位技術(shù)引入該協(xié)議的基本思想如下：用一維數(shù)組Pold記錄移動(dòng)節(jié)點(diǎn)最近連通過的k個(gè)節(jié)點(diǎn)集合；移動(dòng)節(jié)點(diǎn)連通時(shí)，還會(huì)彼此交換自己的記錄，每個(gè)移動(dòng)節(jié)點(diǎn)保存最近m個(gè)節(jié)點(diǎn)與其交換的記錄。通過上述過程，移動(dòng)場景中的每個(gè)移動(dòng)節(jié)點(diǎn)建立一個(gè)m×(k+1)大小的二位數(shù)組H來保存這些歷史信息。節(jié)點(diǎn)N′在節(jié)點(diǎn)N的H中出現(xiàn)的次數(shù)就反映了N′與N的接近程度，出現(xiàn)次數(shù)越大，即節(jié)點(diǎn)N(或最近曾經(jīng)與N連通過的節(jié)點(diǎn))與N′連通的次數(shù)越大，則N′在N附近的概率越大。因此節(jié)點(diǎn)N的二位數(shù)組HN在某種程度上反映了節(jié)點(diǎn)N附近節(jié)點(diǎn)的空間分布狀況，隨著移動(dòng)場景中節(jié)點(diǎn)的移動(dòng)與相互位置關(guān)系的改變，H也會(huì)動(dòng)態(tài)實(shí)時(shí)地反映出來。
在節(jié)點(diǎn)A向B傳輸數(shù)據(jù)的第4階段，當(dāng)節(jié)點(diǎn)B收到它所請求的數(shù)據(jù)后，會(huì)遍歷自己的二維數(shù)組HB以判斷數(shù)據(jù)的目的地址是否在數(shù)組中出現(xiàn)：如果有，說明數(shù)據(jù)的目的節(jié)點(diǎn)在B附近的概率較高，即目的節(jié)點(diǎn)在A附近的概率較高，A會(huì)以較高概率在以后的較短時(shí)間內(nèi)與目的節(jié)點(diǎn)相連通，則B會(huì)丟棄數(shù)據(jù)；如果遍歷后二維數(shù)組HB中沒有目的地址，則B才會(huì)接收該數(shù)據(jù)。這樣節(jié)點(diǎn)B就實(shí)現(xiàn)了對數(shù)據(jù)的定向接收。