受限網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)歷史異步路由及中繼數(shù)量研究

1、受限網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)歷史異步路由及中繼數(shù)量研究*陳輝i 樊秀梅i 單志廣2(|北京理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京，100081)g國(guó)家信息小心信息化研究部，北京，100045)摘要：由于節(jié)點(diǎn)的移動(dòng)性、稀疏鏈路和節(jié)點(diǎn)的不可靠，受限網(wǎng)絡(luò)節(jié)點(diǎn)2間在大部分時(shí)間處于斷開(kāi)狀態(tài)，現(xiàn) 有的同步路由方法不能適用這種實(shí)際情況,所以必須從異步角度來(lái)考慮這類(lèi)網(wǎng)絡(luò)環(huán)境下的路由問(wèn)題。木文 完金從:異步的角度思考無(wú)線(xiàn)自組織網(wǎng)中的路山問(wèn)題，利用分組轉(zhuǎn)發(fā)的歷史信息智能做出路山?jīng)Q策，并研究 中繼節(jié)點(diǎn)數(shù)量對(duì)性能的影響，以減少由于復(fù)制大量分組而產(chǎn)生的網(wǎng)絡(luò)流量。本文詳細(xì)介紹了我們提出的方 法，并通過(guò)仿真實(shí)驗(yàn)

2、和一些相關(guān)算法進(jìn)行比較，分析算法性能。關(guān)鍵詞：路由 受限網(wǎng)絡(luò) 機(jī)會(huì)通信 容遲網(wǎng)絡(luò)中圖分類(lèi)號(hào)：tp393文獻(xiàn)標(biāo)識(shí)碼：a文章編號(hào)：forwarded history-based asynchronous routing for challengednetworks and research of the number of relayschen hui1 fan xiumei1shan zhiguang2('beijing laboratory of intelligent information technology, school of computer science, beijin

3、g institute of technology, beijing 100081 prc)institute of information research, state information center, beijing 100045)abstract. for the reason of the mobility > fallibility of nodes, and the sparsity of links, most of the time links in challenged networks are disconnected traditional synchron

4、ous routing methods are unsuitable for this circunistancc, thus wc should consider the routing problem of challenged networks in an asynchronous way. in this article, we propose a totally asynchronous routing algorithm, which uses the forwarded history of the messages to make routing decision. this

5、method could decrease network traffic caused by message flooding in addition, we study of the influence of the number of relays on the performance. this paper elaborates our method and analyses the performance of our method by comparing the simulation result with some other methodskeywords: routing

6、, challenged networks , contact , delay tolerant network本文受到國(guó)家鬥然科學(xué)基金(no. 90604012國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)(no.2007aa01z220) 和新世紀(jì)優(yōu)秀人才計(jì)劃(ncet-07-0074)資助。陳輝，研究牛，研究領(lǐng)域?yàn)闊o(wú)線(xiàn)網(wǎng)絡(luò)、容遲網(wǎng)絡(luò)的路由技術(shù)。hchen229單志廣，博士，研究員，研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、petri網(wǎng)理論與應(yīng)川等；shan7ig通訊作者：樊秀梅，博士，副教授。研究領(lǐng)域?yàn)橹銠C(jī)網(wǎng)絡(luò)無(wú)線(xiàn)網(wǎng)絡(luò)，網(wǎng)絡(luò)性能評(píng)價(jià)等。xmfanbiteducntel: 130219616981簡(jiǎn)介無(wú)線(xiàn)自組織網(wǎng)(m

7、anet, mobile ad-hoc network)是一種典型的分布式網(wǎng)絡(luò)模式, 這對(duì)節(jié)點(diǎn)間的相互通信提出了很多挑戰(zhàn)。針 對(duì)無(wú)線(xiàn)口組織網(wǎng)的路由問(wèn)題，大屋算法已被 提出"為了研究問(wèn)題的簡(jiǎn)單化,大多數(shù) 學(xué)者的研究都基于這樣的假設(shè)：只有在相直 連接的同一云圖中的節(jié)點(diǎn)問(wèn)的通信才是有 意義的，即通信都是同步的。然而在實(shí)際的 應(yīng)用中這種假設(shè)被越來(lái)越多的打破，在實(shí)際 屮可能需要在不同的連接云圖屮通信，或者 是某一地區(qū)由于某些原因，比如節(jié)點(diǎn)比較稀 疏,節(jié)點(diǎn)能量管理或是節(jié)點(diǎn)移動(dòng)比較頻繁， 使網(wǎng)絡(luò)屮很難維持穩(wěn)定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。此 外，在目前的一類(lèi)越來(lái)越重耍的所謂“受限 網(wǎng)絡(luò)(challenged n

8、etwork)中,由于 較人的網(wǎng)絡(luò)延時(shí)、頻繁的網(wǎng)絡(luò)斷開(kāi)和間歇連 接使得很難維持節(jié)點(diǎn)持續(xù)的連通性。在以上 情況下使用現(xiàn)冇的同步路由算法很明顯不 能滿(mǎn)足這些情況下的端到端通信。異步通信 很自然的適用于這些部分連接的網(wǎng)絡(luò)壞境。“受限網(wǎng)絡(luò)”的最基本要求就是在盡量 小的延遲下保證分組的成功送達(dá)，本文使用 基于分組傳發(fā)歷史來(lái)進(jìn)行路由決策，并選擇 較好的節(jié)點(diǎn)作為分組的攜帶者的方法來(lái)滿(mǎn) 足“受限網(wǎng)絡(luò)”的特殊性。我們通過(guò)在 dtnsim2異步事件仿真平臺(tái)上實(shí)現(xiàn)我們提出 的路巾算法，并和流行性算法(epidemic algorithm) "、simple contact 算法和 global knowl

9、edge算法進(jìn)行比較,分析算 法性能。2無(wú)線(xiàn)自組織網(wǎng)絡(luò)中的異步通信我們?cè)谌粘Ｉ钪薪?jīng)常使用internet 和在可能距離很遠(yuǎn)的其他用戶(hù)進(jìn)行及時(shí)通 信或文件傳輸。在這些同步通信的情況下， 源節(jié)點(diǎn)和11標(biāo)節(jié)點(diǎn)建立一條端到端的路徑， 在這條路徑上發(fā)送消息分組。如果山于某些 原因，如網(wǎng)絡(luò)異常，某-個(gè)分組發(fā)送失敗， 源節(jié)點(diǎn)會(huì)垂新給口標(biāo)節(jié)點(diǎn)發(fā)送該分組。但是 像在10 屮提到的環(huán)境，不同部落間的節(jié)點(diǎn) 可能rti于沒(méi)有這樣的端到端的路徑，這樣采 用同步的方法就不能進(jìn)行通信，提出了異步 工作模式的需求。目前提出的關(guān)于無(wú)線(xiàn)口組織網(wǎng)中的異步 路由算法已有一些成果。一種最簡(jiǎn)單的 方法是源節(jié)點(diǎn)將分組洪泛給區(qū)域中的所有

10、節(jié)點(diǎn),直到id標(biāo)節(jié)點(diǎn)接收到該消息，這種算 法被稱(chēng)為流彳亍性算法(epidemic algorithm ')。雖然這種算法保證消息以最 小的延遲發(fā)送給目標(biāo)節(jié)點(diǎn)同時(shí)保證很高的 發(fā)送成功率，但這種算法產(chǎn)生過(guò)多的網(wǎng)絡(luò)流 量，為此也可以借鑒一些改進(jìn)思路° 17j o 由于無(wú)線(xiàn)網(wǎng)絡(luò)中的節(jié)點(diǎn)沒(méi)有持續(xù)的能量供 給，節(jié)點(diǎn)的存儲(chǔ)能量和計(jì)算能力都是冇限 的，特別是在用于特殊場(chǎng)合傳感網(wǎng)絡(luò)中，如 13中用于監(jiān)測(cè)斑馬活動(dòng)規(guī)律的斑馬網(wǎng)中， 帶有g(shù)ps定位系統(tǒng)的無(wú)線(xiàn)傳感節(jié)點(diǎn)被安裝在 斑馬少上，這些節(jié)點(diǎn)一旦安裝完畢就不能再 更換電池，所以我們希望電池能用盡量長(zhǎng)的 時(shí)間。這樣，因?yàn)榱餍行运惴óa(chǎn)生太多的網(wǎng) 絡(luò)流量

11、而使節(jié)點(diǎn)處于活動(dòng)的時(shí)間會(huì)大大增 加，同時(shí)節(jié)點(diǎn)要處理更多的分組，過(guò)人的計(jì) 算量同樣會(huì)消耗掉很多能量。另一方面，由 于網(wǎng)絡(luò)中節(jié)點(diǎn)存儲(chǔ)能量?jī)酉蓿绻?jié)點(diǎn)接收 到的分組超過(guò)了節(jié)點(diǎn)的緩存的范圍，節(jié)點(diǎn)就 會(huì)丟棄掉一些優(yōu)先級(jí)低或時(shí)間比較久的分 組，這最終影響到分組發(fā)送的成功率。所以, 實(shí)際的路由算法應(yīng)該是挑選部分較好節(jié)點(diǎn) 來(lái)轉(zhuǎn)發(fā)分組，以減少不必要的網(wǎng)絡(luò)流量?，F(xiàn) 有的大量路由算法都是圍繞著如何選取較 好的中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)分組，如何在復(fù)制較少分 纟r的情況下仍然能達(dá)到較好的傳輸效來(lái)。kevin fall等人提出了兒種依靠網(wǎng)絡(luò)知 識(shí)來(lái)轉(zhuǎn)發(fā)分組的算法。這些算法使用一種 類(lèi)似丁傳統(tǒng)網(wǎng)絡(luò)路由協(xié)議的鏈接量度，每個(gè) 節(jié)點(diǎn)都建立

12、一個(gè)全局網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，最終 在這個(gè)圖上運(yùn)行最小路徑算法來(lái)計(jì)算出一 條最小路徑，使用這條路徑上的節(jié)點(diǎn)轉(zhuǎn)發(fā)分 組。mirco musolesi等 人提出了 一種 context-aware routing 路由算法(山。這 種算法里節(jié)點(diǎn)從利用環(huán)境信息合成傳輸可 能性信息來(lái)進(jìn)行路由決策。在同步路由時(shí)節(jié) 點(diǎn)周期性的發(fā)送同步路由需要的潛在信息 和它給其它節(jié)點(diǎn)傳輸可能性的列表。節(jié)點(diǎn)收 到這些消息后更新自己的路由表。對(duì)于異步 路由，每一個(gè)節(jié)點(diǎn)都維持一個(gè)列表，這個(gè)列 表中保存(目標(biāo)節(jié)點(diǎn)，最好節(jié)點(diǎn)，傳輸可能 性)這樣的組。當(dāng)一個(gè)節(jié)點(diǎn)被選為消息攜帶 者并接收到消息后，節(jié)點(diǎn)把消息存入緩沖區(qū) 中。這個(gè)攜帶消息的節(jié)點(diǎn)

13、執(zhí)行同樣的操作， 直到消息送達(dá)目標(biāo)節(jié)點(diǎn)。此外,他們還提出 了使用卡爾曼濾波(kalman filter)c2l來(lái)預(yù) 測(cè)節(jié)點(diǎn)環(huán)境的變化和優(yōu)化帶寬的使用。joy ghosh等人研究在etn zurich校園 中無(wú)線(xiàn)用戶(hù)的移動(dòng)性軌跡來(lái)驗(yàn)證他們?cè)谇?91 中提出的社會(huì)性軌跡(,即移動(dòng)節(jié)點(diǎn)經(jīng)常 訪(fǎng)問(wèn)一些重要地方(稱(chēng)作“網(wǎng)絡(luò)中心”)，這 些地方形成節(jié)點(diǎn)的一個(gè)“網(wǎng)絡(luò)中心”列表并 且通過(guò)混合貝努利分布把這些“網(wǎng)絡(luò)中心” 列表形成簇。簇使用“網(wǎng)絡(luò)中心”列表和與 其相關(guān)聯(lián)的訪(fǎng)問(wèn)可能性，并利用這些簇作為 “移動(dòng)輪丿郭”，使用這些輪綁為移動(dòng)節(jié)點(diǎn)提 供有效的路rti決策。kevin fall等人提岀了容遲網(wǎng)絡(luò)(dela

14、y tolerant nelwork)體系結(jié)構(gòu) '來(lái)處理不同'受 限網(wǎng)絡(luò)”類(lèi)型問(wèn)的節(jié)點(diǎn)的通信問(wèn)題。同時(shí)， 基于文獻(xiàn)8的思想他們提出了幾種需要網(wǎng) 絡(luò)知識(shí)的路由算法，這些算法在節(jié)點(diǎn)間定義 一種量度，這樣節(jié)點(diǎn)和節(jié)點(diǎn)間的通信機(jī)會(huì)形 成一個(gè)加權(quán)圖，然厲利用最小路徑算法尋找 一條較好的路徑來(lái)轉(zhuǎn)發(fā)消息。evan p. c. jones等人對(duì)該算法進(jìn)行了改進(jìn)如。wang yong等人提出基于擦除碼 (erasure-coding)的消息轉(zhuǎn)發(fā)算法來(lái)提高 簡(jiǎn)單的消息復(fù)制算法)。在基于擦除碼的 算法屮，首先在源節(jié)點(diǎn)對(duì)消息進(jìn)行編碼產(chǎn)生 大量的編碼塊，然后這些編碼塊平均的在前 n個(gè)到了的中繼間分配，讓它

15、們負(fù)責(zé)轉(zhuǎn)發(fā)編 碼塊。當(dāng)有部分代碼塊到達(dá)終端節(jié)點(diǎn)即可使 用它們重新恢復(fù)消息。除了有效的路由以 外，這種方法也能應(yīng)對(duì)比較差的通道質(zhì)量或 網(wǎng)絡(luò)擁塞造成的分組丟失。這些方法從不同的角度考慮無(wú)線(xiàn)口組 網(wǎng)中界步路山問(wèn)題，但這些方法都在某些方 而存在一定的問(wèn)題。我們提出的方法可以和 這些方法進(jìn)行了一定的融合，最終形成一種 混合的路由方法，這種方法需要較少的網(wǎng)絡(luò) 知識(shí)、復(fù)制較少的消息、選擇合適的中繼點(diǎn) 及中繼點(diǎn)數(shù)量，并ii能考慮到網(wǎng)絡(luò)中人部分 影響路由的因素。3基于轉(zhuǎn)發(fā)歷史的路由我們提出一種基于轉(zhuǎn)發(fā)歷史的智能路山 算法 (routing algorithm based on transfer history,

16、簡(jiǎn)稱(chēng)為fi),該算法的 tj標(biāo)是讓節(jié)點(diǎn)能夠智能的做出路由決策，選 擇一些將同類(lèi)消息成功送達(dá)目標(biāo)節(jié)點(diǎn)成功 率比較高的節(jié)點(diǎn)作為中繼點(diǎn)來(lái)轉(zhuǎn)發(fā)分組。同 時(shí)fh算法使用盡量少的網(wǎng)絡(luò)知識(shí)，便于網(wǎng) 絡(luò)的部署和擴(kuò)展。算法川來(lái)做出路由決策 的信息是基于對(duì)以往消息轉(zhuǎn)發(fā)歷史的統(tǒng)計(jì) 來(lái)得到的，在算法運(yùn)行初期和流行性算法類(lèi) 似，在這一階段節(jié)點(diǎn)建立轉(zhuǎn)發(fā)信息表，一旦 轉(zhuǎn)發(fā)信息表建立成功就開(kāi)始選取部分節(jié)點(diǎn) 而不是所有節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)消息。3.1系統(tǒng)模型間歇性斷開(kāi)的網(wǎng)絡(luò)通常被建模成一系 列的移動(dòng)性節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以?huà)人魍ㄐ欧?圍內(nèi)的其它節(jié)點(diǎn)并建立連接，節(jié)點(diǎn)具有一疋 的消息緩存能力和有限的帶寬。當(dāng)兩個(gè)節(jié)點(diǎn) 進(jìn)入彼此的通信范圍后，建立連

17、接并相互發(fā) 送分纟r消息。在傳輸中，發(fā)送方給接收方發(fā) 送一個(gè)分組后并不將口身的分組拷貝刪除。 節(jié)點(diǎn)可以直接或通過(guò)其它中i、可節(jié)點(diǎn)將分組 發(fā)送給目標(biāo)節(jié)點(diǎn)。假設(shè)日標(biāo)節(jié)點(diǎn)有足夠的空 間存儲(chǔ)接收的消息，則只有傳輸中的分組受 有限存儲(chǔ)空間的限制。間歇性斷開(kāi)網(wǎng)絡(luò)中節(jié) 點(diǎn)之間的通信機(jī)會(huì)持續(xù)的時(shí)間遠(yuǎn)小于節(jié)點(diǎn) 間斷開(kāi)的時(shí)間。我們的研究實(shí)驗(yàn)基于圖1所示的模型， 模型是一個(gè)有向圖結(jié)構(gòu)，圖屮的節(jié)點(diǎn)表示網(wǎng) 絡(luò)節(jié)點(diǎn)，圖中的邊表示節(jié)點(diǎn)間所擁冇的通信 機(jī)會(huì)(通信機(jī)會(huì)是雙向的，并且按照一定的 規(guī)律到來(lái))。異步路由算法的目標(biāo)就是利用 這些通信機(jī)會(huì)，將盡量多的消息從源節(jié)點(diǎn)發(fā) 送到目標(biāo)節(jié)點(diǎn)。32研究中的一些假定philo juang

18、等人曾提出一種基于歷史 的路由算法(13),他們統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)和接收 消息的基站通信機(jī)會(huì)的歷史，利用這些歷史 信息計(jì)算一個(gè)量度值。當(dāng)一個(gè)節(jié)點(diǎn)要發(fā)消息 時(shí)，他將消息復(fù)制給那些和它有通信機(jī)會(huì)的 量度值較高的一些節(jié)點(diǎn)，這樣消息沿著-條 越來(lái)越接近基站的方向傳輸。這是一種坡度 路由的方法，等級(jí)越高的節(jié)點(diǎn)在基站附件活 動(dòng)越頻繁，同時(shí)和基站的通信的機(jī)會(huì)越多。 然而這種方法存在明顯的“慢啟動(dòng)”問(wèn)題麗, 特別是在大規(guī)模網(wǎng)絡(luò)環(huán)境屮。在規(guī)模比較大 的網(wǎng)絡(luò)中，同源節(jié)點(diǎn)有通信機(jī)會(huì)的中繼町能 都離目標(biāo)節(jié)點(diǎn)比較遠(yuǎn)，很町能沒(méi)有和目標(biāo)節(jié) 點(diǎn)通信的機(jī)會(huì)，所以他們不可能冇很高的成 功率讓我們選擇他們?yōu)橹欣^。這樣源節(jié)點(diǎn)或 其它中繼在

19、轉(zhuǎn)發(fā)給下一跳吋很難做出止確 的判斷。我們的算法根據(jù)轉(zhuǎn)發(fā)歷史記錄來(lái)做 出智能決策，可以很好的解決這個(gè)問(wèn)題。本文提出的路由算法基于如下假定： 網(wǎng)絡(luò)中的節(jié)點(diǎn)有一定的移動(dòng)規(guī)律；如果某 條消息沿著某一條路徑發(fā)送成功率比較高， 那么沿相反的方向發(fā)送消息也有幾乎同樣 的成功率；網(wǎng)絡(luò)屮的節(jié)點(diǎn)是時(shí)鐘同步的。 第一條假設(shè)在人部分實(shí)際受限網(wǎng)絡(luò)場(chǎng)景中 都是滿(mǎn)足的，比如節(jié)點(diǎn)運(yùn)行軌跡精確的星際 網(wǎng)同，依靠攜帯無(wú)線(xiàn)節(jié)點(diǎn)的公共汽車(chē)連接 的偏遠(yuǎn)村莊組成的網(wǎng)絡(luò)巴 斑馬網(wǎng)胸和校園 使用移動(dòng)設(shè)備的用戶(hù)所組成的網(wǎng)絡(luò)呦。在斑 馬網(wǎng)中攜帶無(wú)線(xiàn)傳感器的節(jié)點(diǎn)，在水源和生 t比較快的草地附近的機(jī)會(huì)更人，這樣每個(gè) 節(jié)點(diǎn)的運(yùn)行看似隨機(jī)，其實(shí)也存在很

20、強(qiáng)的規(guī) 律性。我們的第二個(gè)假設(shè)受兩個(gè)因素的影 響，反向路徑的可靠性可能因?yàn)楣?jié)點(diǎn)或鏈路 的不穩(wěn)定或不對(duì)稱(chēng)的消息傳輸率而影響。但 是鏈路和節(jié)點(diǎn)的不穩(wěn)定對(duì)所有的鏈路和節(jié) 點(diǎn)發(fā)生的概率都是相同的，另外我們假設(shè)反 向路徑有同樣高的轉(zhuǎn)發(fā)成功率是為了向參 與成功轉(zhuǎn)發(fā)消息的節(jié)點(diǎn)發(fā)送確認(rèn)消息，而我 們的確認(rèn)消息數(shù)據(jù)量非常小，即使反向的數(shù) 據(jù)傳輸率比較低，也不會(huì)造成很大的影響。提出的基于轉(zhuǎn)發(fā)歷史的路由算法分為 三部分：中繼選擇算法 (relay.select)；分組傳輸算法 (packet_transfer):路由信息更新 (rinfojjpdate)。中繼選擇算法在節(jié)點(diǎn)準(zhǔn) 備發(fā)送分組時(shí)或作為中繼接收到消息時(shí)被

21、執(zhí)行，為分組選擇較好的下一跳中繼。分纟ft 傳輸算法在兩個(gè)節(jié)點(diǎn)的通信機(jī)會(huì)到來(lái)時(shí)執(zhí) 行，進(jìn)行分組的傳輸。路由更新算法在節(jié)點(diǎn) 收到回饋信息后執(zhí)行，更新路由信息表。3.3中繼選擇算法因?yàn)樵陂g歇性連接網(wǎng)絡(luò)中節(jié)點(diǎn)大部分 時(shí)間處于斷開(kāi)狀態(tài)，不同的節(jié)點(diǎn)的通信機(jī)會(huì) 到來(lái)并不在同一時(shí)間，所以必須在發(fā)送消息 前做出路由決策，挑選較好的節(jié)點(diǎn)得到消息 的復(fù)制。d分組的目標(biāo)節(jié)點(diǎn)tm終點(diǎn)為d的條忖中最大的 平均時(shí)間ta中繼r通信機(jī)會(huì)到來(lái)的平均 時(shí)間sc中繼r成功發(fā)送數(shù)量de中繼r發(fā)送消息數(shù)量n挑選較好屮繼的個(gè)數(shù)m路由信息建立所發(fā)的消息 個(gè)數(shù)relay_select(d)1從路由表屮查詢(xún)出終端節(jié)點(diǎn)是d的條日。 2利用公式t

22、=l-ta/tm將各個(gè)條h中的平均 時(shí)間映射到0-1范圍內(nèi)。計(jì)算各個(gè)條目的轉(zhuǎn) 發(fā)成功率usc/dcc3合成路由量度m=kl*t+k2*r,平均時(shí)間 和轉(zhuǎn)發(fā)成功率分別被賦予不同的權(quán)值k1和k2o挑選m值較大的n個(gè)節(jié)點(diǎn)作為中繼， 對(duì)dc<m的屮繼同樣得到消息的復(fù)制來(lái)建 立路由信息。4將選擇的中繼記錄，等待這些節(jié)點(diǎn)的通信 機(jī)會(huì)的到來(lái)。3.4分組傳輸算法當(dāng)兩個(gè)節(jié)點(diǎn)的通信機(jī)會(huì)到來(lái)時(shí)，分組傳 輸算法被執(zhí)行。相遇的兩個(gè)節(jié)點(diǎn)執(zhí)行同樣的 方法將分組傳輸給對(duì)方。為了充分利用通信 機(jī)會(huì)我們按不同的順序來(lái)傳輸各種消息，確 認(rèn)消息首先得到傳輸，其次是目標(biāo)節(jié)點(diǎn)是通 信的另一方的消息，最厲發(fā)送其它的消息。 這樣保證確

23、認(rèn)消息盡快得到傳輸以及時(shí)的 更新路由信息表，另外優(yōu)先發(fā)送直接到達(dá)的 節(jié)點(diǎn)使中繼盡早釋放消息所占用的存儲(chǔ)空 間并避免消息被新的分組給覆蓋，提高分組 傳輸成功率。packet_transfer(x,y)1 x節(jié)點(diǎn)向y節(jié)點(diǎn)發(fā)送應(yīng)該由y轉(zhuǎn)發(fā)或發(fā)往 y的分組的關(guān)鍵字的列表l。等待y的回復(fù)。 2節(jié)點(diǎn)y把l屮沒(méi)有接收到的消息的關(guān)鍵 字的列表l2發(fā)送給x。3發(fā)送l2中的確認(rèn)消息給y。 4發(fā)送終點(diǎn)是y的分組給yo 5發(fā)送其它分組給y。6路山算法在通信機(jī)會(huì)結(jié)束或所有消息傳 輸完畢后結(jié)束。35路由信息更新發(fā)送分組的節(jié)點(diǎn)或得到分組復(fù)制的節(jié) 點(diǎn)在將分組加入存儲(chǔ)區(qū)時(shí)在消息頭中標(biāo)記 節(jié)點(diǎn)的標(biāo)識(shí)關(guān)鍵字和當(dāng)前時(shí)間。分組的終端

24、節(jié)點(diǎn)在接收到分組后從分組頭中取出參與 分組發(fā)送的節(jié)點(diǎn)列表ns和各個(gè)節(jié)點(diǎn)收到消 息的時(shí)間，計(jì)算出每跳所使用的時(shí)間ts。創(chuàng) 建確認(rèn)消息將ns和ts作為確認(rèn)消息的數(shù) 據(jù)，按和反路徑轉(zhuǎn)發(fā)給參與該分組轉(zhuǎn)發(fā)的節(jié) 點(diǎn)和分組的源節(jié)點(diǎn)。在消息發(fā)送過(guò)程中，我們?cè)谙㈩^里而 記錄消息發(fā)送所走的路徑，當(dāng)終端節(jié)點(diǎn)成功 接收到消息時(shí)利用該路徑的相反方向給路 徑上的節(jié)點(diǎn)發(fā)確認(rèn)消息。節(jié)點(diǎn)接收到確認(rèn)消 息肩更新路由信息表。比如一條消息沿著 a->b->e->g的路徑將一條消息成功發(fā)送，則 g按g->e->b->a路徑來(lái)發(fā)送確認(rèn)消息。假設(shè) 節(jié)點(diǎn)a收到了確認(rèn)消息，這不但表明它使用 節(jié)點(diǎn)b為中繼成

25、功給g發(fā)送了-條消息，同 時(shí)也表明它使用節(jié)點(diǎn)b為中繼成功給e發(fā)送 了一條消息和它成功給b發(fā)送了一條消息， 則在a的路由信息標(biāo)準(zhǔn)要更新以b為中繼， g、e、b為目標(biāo)節(jié)點(diǎn)的三個(gè)條目的信息。3.6仿真實(shí)驗(yàn)與性能比較我們?cè)赿tnsim2t22異步事件仿真平臺(tái)上 實(shí)現(xiàn)了流行性算法(epidemic protocol, ep)、直接通信機(jī)會(huì)(simple contact, sc)、 全局知識(shí)路由(earliest delivery, ed)、 及我們提岀的基于轉(zhuǎn)發(fā)歷史路由(routing algori thm based on transfer hi story, fh)等算法，并對(duì)仿真結(jié)果進(jìn)行比較。所冇

26、 算法仿真都基于表1所示的同樣參數(shù)。表1：仿真參數(shù)仿真區(qū)域(米)4500x3400節(jié)點(diǎn)數(shù)(個(gè))16消息大小(kb)400帶寬(kbps)800仿真時(shí)長(zhǎng)(天)l5建立路市信息發(fā)送消 息數(shù)(個(gè))8選擇較好中繼數(shù)(個(gè))4實(shí)驗(yàn)場(chǎng)景釆用jorg ott等人在9中使 用的一個(gè)經(jīng)過(guò)對(duì)移動(dòng)設(shè)備用戶(hù)的活動(dòng)規(guī)定 進(jìn)行統(tǒng)計(jì)而得出的一個(gè)實(shí)際的場(chǎng)景，在這個(gè) 場(chǎng)景里節(jié)點(diǎn)以不同的頻率出現(xiàn)在各個(gè)被稱(chēng) 為“網(wǎng)絡(luò)屮心”的地方，例如餐廳、教室， 同時(shí)出現(xiàn)在一個(gè)“網(wǎng)絡(luò)中心”的兩個(gè)節(jié)點(diǎn)具 有相互識(shí)別并進(jìn)行通信的能力。仿真使用的節(jié)點(diǎn)移動(dòng)模型是joy ghosh 等人通過(guò)對(duì)etn zurich校園中無(wú)線(xiàn)用戶(hù)的 移動(dòng)性軌跡進(jìn)行跟蹤而得到的節(jié)

27、點(diǎn)移動(dòng)性 模型"2)。在這個(gè)模型里，節(jié)點(diǎn)以不同的概 率在各個(gè)被成為“網(wǎng)絡(luò)中心”的地方出現(xiàn)， 當(dāng)兩個(gè)節(jié)點(diǎn)出現(xiàn)在同一個(gè)“網(wǎng)絡(luò)中心”時(shí)這 兩個(gè)節(jié)點(diǎn)處于連通狀態(tài)，開(kāi)始進(jìn)行通信。我 們選擇的移動(dòng)性模型屮的節(jié)點(diǎn)的移動(dòng)有一 定的規(guī)律性也存在一定的隨機(jī)性。這些節(jié)點(diǎn) 的移動(dòng)雖然看似隨機(jī)的，但是實(shí)際中某些節(jié) 點(diǎn)在某些“網(wǎng)絡(luò)屮心”出現(xiàn)的概率可能比其 它“網(wǎng)絡(luò)中心”出現(xiàn)的概率高,同樣在同一 個(gè)“網(wǎng)絡(luò)中心”中出現(xiàn)的概率相似的節(jié)點(diǎn)擁 有更多的通信機(jī)會(huì)。在相同環(huán)境下，我們對(duì)本文捉出的基于 轉(zhuǎn)發(fā)歷史的路由算法、直接發(fā)送算法、全局 知識(shí)算法和流行性算法在仿真實(shí)驗(yàn)中進(jìn)行 比較，分析比較了它們的一些性能參數(shù)指 標(biāo)。圖2是

28、在帶寬和節(jié)點(diǎn)數(shù)確定為16個(gè)的 情況下，通過(guò)設(shè)定不同的緩沖區(qū)值來(lái)仿真而 得到的數(shù)據(jù)傳輸率的曲線(xiàn)圖。從圖屮看到基 于轉(zhuǎn)發(fā)歷史的路由方法在性能上比流行性 算法和全局知識(shí)算法稍差，而又比百接傳遞 方法好。因?yàn)橹苯觽鬟f方法受消息的源節(jié)點(diǎn) 和1=1標(biāo)節(jié)點(diǎn)互接的通信機(jī)會(huì)的次數(shù)的限制， 而流行性算法是以大暈消息為代價(jià)的，此外 全局知識(shí)算法不僅需要節(jié)點(diǎn)交換人量的消 息，而且要進(jìn)行大量的最小路徑的計(jì)算。這 兩種方法對(duì)節(jié)點(diǎn)的能量都有很人的消耗。最 后，流行性算法和全局知識(shí)算法受緩存區(qū)的 大小影響較大，我們可以看到隨著緩沖區(qū)大 小的增加這兩種算法的數(shù)據(jù)傳輸率增加很 快，而基于轉(zhuǎn)發(fā)歷史的路由方法和直接傳遞 的方法則變化

29、的相對(duì)較慢。這表明基于轉(zhuǎn)發(fā) 歷史的路由方法受緩存區(qū)大小的影響比較 小，因?yàn)榛谵D(zhuǎn)發(fā)歷史的路由方法在網(wǎng)絡(luò)中 產(chǎn)牛的流量比較少。圖2：緩存區(qū)大小vs分組傳輸率圖3是在設(shè)置不同的緩沖區(qū)人小的情況 下，網(wǎng)絡(luò)中所發(fā)送的消息的數(shù)量。我們可以 看到無(wú)論緩存的大小是多少，流行性算法所 發(fā)送的數(shù)據(jù)量大于基于轉(zhuǎn)發(fā)歷史的路由方 法。另外實(shí)驗(yàn)結(jié)果表明全局知識(shí)算法所傳輸 的數(shù)據(jù)量遠(yuǎn)遠(yuǎn)大于其它算法。而直接傳遞方 法產(chǎn)牛的消息量很小，而口隨緩沖區(qū)大小的 增加基本保持不變。流行性算法的曲線(xiàn)增加 基木是隨著數(shù)據(jù)發(fā)送成功的量的增加而增 加，因?yàn)楦嗟南l(fā)送到終點(diǎn)就需要復(fù)制 更多的消息?；谵D(zhuǎn)發(fā)歷史的算法消息量的 變化稍微比較和

30、緩，因?yàn)槲覀冊(cè)诿恳淮巫雎?由決策時(shí)只選擇四個(gè)最好的節(jié)點(diǎn)，相比于流 行性算法把消息復(fù)制給所有的節(jié)點(diǎn)基本上 少了三分z的消息量。而且，流行性算法 發(fā)送消息量是隨著節(jié)點(diǎn)數(shù)增加指數(shù)級(jí)增長(zhǎng) 的(n+l) m，基于轉(zhuǎn)發(fā)歷史的算法是乘數(shù) 級(jí)增長(zhǎng)的(n+l)*m*k (n是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),m 是發(fā)送的總消息數(shù)，k是fh算法選擇的較 好中繼數(shù))。圖3：緩存區(qū)大小vs傳輸總量圖4是在不同緩存區(qū)大小下，消息平均 延時(shí)的變化圖。從圖中可以看到fh算法消 息的平均延時(shí)比ep算法高，而且隨著緩沖 區(qū)的增加而增加的比較快。這說(shuō)明雖然我們 統(tǒng)計(jì)成功率都是最早發(fā)送消息成功的路徑， 但在節(jié)點(diǎn)規(guī)律性不是很強(qiáng)的場(chǎng)景下，并不能 保證我們選

31、擇的路徑是延時(shí)接近最小的路 徑。另外我們發(fā)現(xiàn)全局知識(shí)算法的平均時(shí)延 在緩存區(qū)小于1500()時(shí)比其它算法大，這是 因?yàn)閑d算法需要節(jié)點(diǎn)問(wèn)交換大量的路由信 息來(lái)建立量度，在緩存區(qū)小的情況下發(fā)送較 少的消息不能有效的建立網(wǎng)絡(luò)信息。隨著網(wǎng) 絡(luò)中發(fā)送消息數(shù)的增加，ed算法能做出更 準(zhǔn)確的路由決策。級(jí)存區(qū)大小vs祁挺時(shí)sc亠edep71的成功率。從該實(shí)驗(yàn)結(jié)果的分析可見(jiàn)，中繼 個(gè)數(shù)選擇受資源情況和消息暈的影響，選擇 合理的較好中繼數(shù)能捉高消息發(fā)送成功率。1.2緩存區(qū)大小聯(lián)好中擁數(shù)vs消息發(fā)送成功率圖4：緩沖區(qū)人小vs平均延時(shí)4中繼數(shù)量選擇研究本文提出的路rh算法有一個(gè)重要的參 數(shù)一選擇的較好中繼數(shù)。該參數(shù)

32、決定在節(jié)點(diǎn) 轉(zhuǎn)發(fā)消息時(shí)，將消息拷貝給幾個(gè)下一跳節(jié) 點(diǎn)。該參數(shù)的設(shè)置百接影響到本文提出的路 由算法的性能，所以需要進(jìn)行合理選擇。本 節(jié)從該參數(shù)對(duì)發(fā)送成功率、平均延遲和路rh 的效率的影響進(jìn)行分析。4.1中繼個(gè)數(shù)對(duì)消息發(fā)送成功率的影響因?yàn)樘魬?zhàn)網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的不穩(wěn)定 性，在每一跳需要將消息拷貝給多個(gè)卜一跳 節(jié)點(diǎn)來(lái)提高消息的可達(dá)性。另一方面，如果 每一跳選擇的屮繼過(guò)多，會(huì)造成更多的網(wǎng)絡(luò) 流量，特別是在網(wǎng)絡(luò)需要傳輸?shù)臄?shù)據(jù)量大或 緩存資源緊張的情況下。rh于不同的消息競(jìng) 爭(zhēng)緩存空間，會(huì)造成一些較iii的消息被刪 除，最終影響消息的可達(dá)性。如圖5所示是 在網(wǎng)絡(luò)中30個(gè)節(jié)點(diǎn)，消息量相同的情況下, 分別把消息

33、緩存區(qū)設(shè)為1m和3om,改變較 好中繼數(shù)而得到的結(jié)果。從圖5可以看到， 消息緩存區(qū)為3om的時(shí)候隨看較好中繼數(shù) 的增加消息發(fā)送的成功率也增加。選擇10 個(gè)中繼比選擇兩個(gè)消息發(fā)送成功率增加了 大約23個(gè)1?分點(diǎn)，但是選擇14個(gè)比選擇10 個(gè)只增加了不到1個(gè)百分點(diǎn)，說(shuō)明選擇超過(guò) 一定數(shù)量的屮繼對(duì)算法性能影響不人，選擇 太多的中繼效率比較低。在圖5中當(dāng)緩存區(qū) 設(shè)為1m時(shí)由于消息數(shù)量沒(méi)有改變，網(wǎng)絡(luò)中 的資源比較緊張，當(dāng)選擇14個(gè)中繼時(shí)消息 發(fā)送成功率稍微下降，這說(shuō)明在資源緊張的 情況卜較好屮繼的選擇數(shù)會(huì)影響消息發(fā)送61014較好中繼數(shù)圖5：選擇的較好中繼數(shù)對(duì)消息發(fā)送成功率的影響4.2中繼個(gè)數(shù)對(duì)平均延遲

34、的影響選擇更人的較好中繼數(shù)使更多的節(jié)點(diǎn) 攜帶消息不僅能在一定條件下提高消息發(fā) 送的成功率，也能降低消息的平均延遲。如 圖6所示當(dāng)選擇更多的較好中繼時(shí)，緩存區(qū) 為1m和30m時(shí)平均延遲都有大幅下降,特 別是在緩存區(qū)為1m時(shí)減少的比較多，這是 因?yàn)檫x擇較少的屮繼時(shí)消息需要傳遞更多 跳。較好中繼數(shù)設(shè)為6時(shí)比設(shè)為2時(shí)平均延 遲減少了大約7000,當(dāng)較好中繼數(shù)繼續(xù)增加 時(shí)平均延遲減少的越來(lái)越慢。當(dāng)緩存區(qū)為 30"時(shí)，選擇較好的中繼數(shù)也使平均延遲減 小，但是沒(méi)有在緩存資源緊張情況下減少的 多。從以上結(jié)果分析可得出結(jié)論增大較好中 繼的個(gè)數(shù)能較小消息的平均延遲，特別是在 緩存資源緊張的情況下更加明顯

35、。0000000000000 o o o o o o 2000806040加較好中瞬vs平購(gòu)延遲61014較好中螯數(shù)圖6：選擇的較好中繼數(shù)對(duì)消息發(fā)送成功率的影響4.3中繼個(gè)數(shù)選擇與效率我們定義平均消息拷貝數(shù)為仿真過(guò)程 "）傳輸?shù)南⒖倲?shù)除以成功傳送的消息的 個(gè)數(shù)。該值近似于傳輸成功的消息平均產(chǎn)牛 的拷貝數(shù)，能在一怎程度上反映消息傳輸?shù)?效率。該值越小表明產(chǎn)牛較少的消息拷貝成 功傳輸消息，所以效率越高。圖7可見(jiàn)隨著 選擇較好中繼數(shù)的增加，消息傳輸?shù)男氏?降。特別是在緩存區(qū)資源緊張的情況下，下 降的比較多。這從另一個(gè)角度說(shuō)明，選擇過(guò) 多的較好中繼對(duì)性能的影響較小，效率比較圖7：選擇的較

36、好屮繼數(shù)對(duì)消息發(fā)送成功率的影響5結(jié)論和展望本文中我們提出了一種基于轉(zhuǎn)發(fā)歷史 的界步路由算法來(lái)處理無(wú)線(xiàn)口組織網(wǎng)中的 異步路由問(wèn)題，并著重研究了中繼點(diǎn)數(shù)罐對(duì) 網(wǎng)絡(luò)性能的影響。無(wú)線(xiàn)自組織網(wǎng)屮的路由問(wèn) 題受很多因素的影響，這里只考慮了幾個(gè)最 重要的參數(shù)因素。fh算法幾乎不需耍任何 的網(wǎng)絡(luò)知識(shí)，便于網(wǎng)絡(luò)的布置；同時(shí)減少了 消息的拷貝數(shù)量，減少了網(wǎng)絡(luò)的負(fù)擔(dān)。另一 方面，fh算法也存在需要發(fā)送確認(rèn)消息的 問(wèn)題，雖然發(fā)現(xiàn)的數(shù)據(jù)量不大，但是過(guò)多的 消息仍然會(huì)增加節(jié)點(diǎn)的活動(dòng)時(shí)間，即消耗更 多的能量。下一步我們將考慮使用不用發(fā)送確認(rèn) 消息仍能進(jìn)行轉(zhuǎn)發(fā)成功率的統(tǒng)計(jì)，比如統(tǒng)計(jì) 接收消息的成功率。另外我們還要考慮其他 因

37、素，如節(jié)點(diǎn)的負(fù)載量，使fh算法在節(jié)點(diǎn) 運(yùn)行規(guī)律性不是很強(qiáng)的網(wǎng)絡(luò)中盡量保證選 擇的路徑冇較小的延遲。此外，我們還要考 慮在更人規(guī)模網(wǎng)絡(luò)環(huán)境下路由表過(guò)于龐人 的問(wèn)題，需要考慮把網(wǎng)絡(luò)劃分成不同的區(qū) 域，在區(qū)域內(nèi)和區(qū)域外分層路由。參考文獻(xiàn)11 charles e. perkins , pravin bhagwat, "highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers'； proceedings of the conference on communicati

38、ons architectures, protocols and applications, august 31 -september 02, 1994, london, united kingdom, pp.234-244.21 t. clausen and p. jacquet. ''optimized link state routing protocol (olsr)". rfc 2326, october 2003.3 c. e. perkins, e. m. belding-royer, and s. r. das. "ad hoc on-dcm

39、and distance vector (aodv) routing". experimental rfc 3561, july 2003. 乙 j. haas, m. r. pearlman. the performance of query control schemes for the zone routing protocol. ieee/acm transactions on networking, aug. 2001,9(4). pp. 427-438.5 p. yao, e. krohne, and t. camp, ”performance comparison of

40、 geocast routing protocols for a manet", proc, of the 13th ieee ic3n, 2004. pp. 213220.6j v. cerf, s. burleigh, k. fall etc. udelay-tolerant networking architecture, drafl-irlf-dtnrg-arch-08.txt, december 2006.7 a. vahdat and d. becker, "epidemic routing for partially connected ad hoc netw

41、orks," department of computer science, duke university, tech. rep cs-2000-06, 2000.8 jain, s., fall, k and patra, r. “rowing in a delay tolerant network. proc, of acm sigcomm'04 , september 2004. pp.27-34.9 joy ghosh, hung q. ngo, and chunming qiao, "mobility profile based routing with

42、in intermittently connected mobile ad hoc networks (icman)n, in proceeding of the 2006 international conference on communications and mobile computing (iwcmc 2006), july 3-6, 2006 vancouver, canada, pp. 551556.10 i. t. union. "connecting remote communities, documents of the world summit on info

43、rmationsociety, /osg/spu/wsis-themes 11 mirco musolcsi, stephen hailes and cecilia mascolo, n adaptive routing for intermittently connected mobile ad hoc networks”，proceedings of ieee 6th international symposium on a world of wireless, mobile and multimedia networks (wowmom'05),

44、 taormina, italy. june 2005. ppi83-189.112 jorg ott, dirk kutscher, christoph dwertmann: integrating dtn and manet routing. proceedings of the sigcomm chants workshop, september 2006.13 juang p.energy-eificient computing for wildlife tracking:design tradeoffs and early rxperiences with zebranetc.san

45、 jose.ca:proceedings of the loih inti conference on architectural support for programming languages and operating systems, 2002. pp.96-107.114 y. wang et al., "erasure-coding based routing for opportunistic networks,” acm sigcomm dtn wksp.2005.wwwsigcomm()rg/sigcomm2()()5/p“pcwanjaipdf15 v. cer

46、f, s. burleigh, a. hooke, l. torgerson, r.durst, k scott.k fall, , and h. weiss, udelay tolerantnetworkarchitecture.draft-irtf-dtnrg-arch-02.txt, 2004.16 thrasyvoulos spyropoulos, konstantinospsounis, and cauligi s raghavcndra: "efficient routing in intermittently connected mobile networks: the

47、 single-copy case”. proceedings of the ieee secon2004.hmp:/wwwsopinridfi7planete/spynjp()ulos/papers/t() nsinglccody.r)df17 cedric westphal, "properties of opportunistic and collaborative ad hoc networks , in proc of globecom 2007, washington dc , november 2007.18 ghosh, j., philip, s. j., and

48、qiao, c. “poster abstract: sociological orbit aware location approximation and routing (solar) in manetm. presented as a poster in acm mobihoc 05, champaign, il, may 2005.19 ghosh, j., philip, s. j., and qiao, c. "sociological orbit aware location approximation and routing in manetm. proc, of i

49、eee broadnets'05,boston, ma, october 2005. pp.641-651.20 evan p. c. jones, lily li and paul a. s. ward, "practical routing in delay-tolerant networks” , acm sigcomm dtn wksp. 2005, august 22 - 26, 2005.http:wwwsigcommorg/sigcomm2005/paperjonlip df211 y. wang et al., "erasure-coding bas

50、ed routing for opportunistic networks acm sigcomm dtn wksp. 2005, august 22-26, 2005./sigcomm2005/paper-wanjai .pdf22 dtnsim2 dtn simulator. university of waterloo. online, available:hllp:shoshinuwaleiiooca/dlnsim2/樊秀梅，女，h?士，現(xiàn)北京理工大學(xué) 副教授，教育部2007年新世紀(jì)優(yōu)秀 人才入選者。主耍研究領(lǐng)域?yàn)橛?jì)算機(jī) 網(wǎng)絡(luò)qos控制、無(wú)線(xiàn)a

51、d hoc網(wǎng)絡(luò)路曲技術(shù)、容遲網(wǎng)絡(luò)、網(wǎng)絡(luò)性能評(píng)價(jià)； xmfanbit edu. cn。fan xiumei was born in shanxi province of china in 1967. she is currently a associate professor in school of computer science and technology, beijing institute of technology her current major research interests focus on wireless network, routing protocol and

52、 ngi qos . xmfanbit edu cn陳輝，男，碩士，研究領(lǐng)域?yàn)闊o(wú)線(xiàn) 寬帶網(wǎng)絡(luò)、dtn網(wǎng)絡(luò)及其路由技術(shù)。 hchc?n229gin3i l comchen hui was born in 1983 at henan province, china. he is currently a graduate student in school of computer science and technology, beijing institute of technology. his research activities are in asynchronous unicast routing algorithm and topology planning of wireless mesh networks in urban areas. hchen229gm3il com單志廣，男，博士，研究員，國(guó)家信 息中心信息化研究部首席工程師，兼 規(guī)劃研究室主任。曾獲2005年“教育 部提名國(guó)家自然科學(xué)一等獎(jiǎng)”。主耍研究領(lǐng)域?yàn)椋?/p>