延遲容忍網(wǎng)絡(luò)中基于鄰居信息精確度的查詢算法*

吳大猛，錢江波，陳葉芳，董一鴻

（寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211）

1 引言

隨著移動(dòng)無線通信技術(shù)的發(fā)展，越來越多的應(yīng)用要求網(wǎng)絡(luò)中的節(jié)點(diǎn)部分或全部具有移動(dòng)性。例如，對(duì)野生動(dòng)物進(jìn)行監(jiān)控和追蹤以了解其生活習(xí)性的網(wǎng)絡(luò)[1]、偏遠(yuǎn)地區(qū)的網(wǎng)絡(luò)傳輸[2]及車載網(wǎng)絡(luò)[3]等，這些網(wǎng)絡(luò)的共同特點(diǎn)就是某一時(shí)刻網(wǎng)絡(luò)中的源節(jié)點(diǎn)和目的節(jié)點(diǎn)不一定存在端到端的通信路徑，數(shù)據(jù)的傳輸具有一定的延遲性。延遲容忍網(wǎng)絡(luò)（delay tolerant network，DTN）模型[4]正是為解決這一問題而產(chǎn)生的。該網(wǎng)絡(luò)泛指沒有端到端傳輸路徑的間斷性連接的網(wǎng)絡(luò)，其主要利用節(jié)點(diǎn)“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的通信模式實(shí)現(xiàn)數(shù)據(jù)傳輸。大量低成本、具備短距離無線通信能力的移動(dòng)設(shè)備（如智能手機(jī)、PDA及掌上電腦）在生活中的普及進(jìn)一步推動(dòng)了延遲容忍網(wǎng)絡(luò)的迅速發(fā)展。這些移動(dòng)設(shè)備一般都具有吉比特字節(jié)的存儲(chǔ)能力并且可以通過藍(lán)牙[5]、IEEE 802.11[6]短程通信技術(shù)實(shí)現(xiàn)相互連接。在一個(gè)特定區(qū)域（如某商業(yè)區(qū)）內(nèi)，移動(dòng)設(shè)備利用無線通信技術(shù)相互連接形成一個(gè)區(qū)域內(nèi)的延遲容忍網(wǎng)絡(luò)，人們利用自己的移動(dòng)設(shè)備搜索和共享信息資源（如MP3歌曲、電子書、廣告信息等）。這種場(chǎng)景在生活中到處可見，比如在學(xué)校、商務(wù)中心、大型購(gòu)物廣場(chǎng)及機(jī)場(chǎng)等，每個(gè)移動(dòng)設(shè)備自由移動(dòng)，可以加入或離開網(wǎng)絡(luò)。由于網(wǎng)絡(luò)中移動(dòng)設(shè)備的高度動(dòng)態(tài)性，維護(hù)網(wǎng)絡(luò)結(jié)構(gòu)的代價(jià)非常高，一個(gè)合理的解決方案就是采取無結(jié)構(gòu)的網(wǎng)絡(luò)方式構(gòu)建網(wǎng)絡(luò)中的節(jié)點(diǎn)[7,8]。在這種方式下，移動(dòng)設(shè)備僅動(dòng)態(tài)維持其通信可達(dá)范圍內(nèi)的鄰居移動(dòng)設(shè)備信息。由于移動(dòng)設(shè)備時(shí)刻移動(dòng)，設(shè)備間的鄰居關(guān)系變化很快，網(wǎng)絡(luò)中的信息要不斷地更新。

在實(shí)際應(yīng)用中，很多用戶期望能主動(dòng)搜索自己想要的信息，比如搜索特定用途的信息、查找打折廣告及下載音樂等。本文主要討論在延遲容忍網(wǎng)絡(luò)中為終端用戶提供主動(dòng)查詢的方法。在延遲容忍網(wǎng)絡(luò)中進(jìn)行主動(dòng)信息查詢主要面臨以下幾個(gè)挑戰(zhàn):第一，網(wǎng)絡(luò)沒有全局索引；第二，由于移動(dòng)設(shè)備計(jì)算能力、電池能量、通信帶寬的限制，查詢轉(zhuǎn)發(fā)算法必須是輕量型、高能效的；第三，由于網(wǎng)絡(luò)具有高動(dòng)態(tài)性，查詢算法必須適應(yīng)頻繁的數(shù)據(jù)更新及網(wǎng)絡(luò)波動(dòng)性。

為了解決上述問題，本文模擬社會(huì)網(wǎng)絡(luò)[9]中的人類行為解決信息查詢問題。用相關(guān)鄰居節(jié)點(diǎn)的鄰居信息（neighbor information）表示社會(huì)網(wǎng)絡(luò)中的相識(shí)；用信息精確度（information accuracy，IA）估計(jì)所有鄰居節(jié)點(diǎn)提供信息的精確度，從而幫助節(jié)點(diǎn)在其鄰居節(jié)點(diǎn)中選擇一個(gè)最優(yōu)的后繼節(jié)點(diǎn)將查詢信息傳送下去。鄰居節(jié)點(diǎn)間的信息交換猶如人們之間的聊天，并在鄰里范圍內(nèi)傳播，可以幫助節(jié)點(diǎn)從其鄰居節(jié)點(diǎn)處收集信息，同時(shí)節(jié)點(diǎn)也可以從自己的查詢經(jīng)驗(yàn)中學(xué)習(xí)。通過對(duì)社會(huì)網(wǎng)絡(luò)的模仿，本文提出一種基于鄰居信息精確度的方法，可以有效處理延遲容忍網(wǎng)絡(luò)的查詢請(qǐng)求。

本文主要貢獻(xiàn)如下:

·基于社會(huì)網(wǎng)絡(luò)中的模仿機(jī)制，模仿人類通過相識(shí)的人獲取答案并從經(jīng)驗(yàn)和閑談中學(xué)習(xí)的自然行為，在延遲容忍網(wǎng)絡(luò)中提出一個(gè)新的信息查詢方法；

·本文提出的方法用于動(dòng)態(tài)網(wǎng)絡(luò)和數(shù)據(jù)需不斷更新的環(huán)境，通過消耗模型分析能量消耗和通信消耗，證明本文提出的方法在高度動(dòng)態(tài)的網(wǎng)絡(luò)中有很好的適應(yīng)性及穩(wěn)定性。

2 相關(guān)工作

延遲容忍網(wǎng)絡(luò)可用于間斷連通的網(wǎng)絡(luò)傳輸數(shù)據(jù)，其本質(zhì)是一種機(jī)會(huì)網(wǎng)絡(luò)[10]。由于網(wǎng)絡(luò)中同一時(shí)刻可能不存在從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的連通路徑，因此需要充分利用節(jié)點(diǎn)移動(dòng)的通信機(jī)會(huì)，采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的模式轉(zhuǎn)發(fā)消息。

近年來，研究人員針對(duì)DTN環(huán)境下的數(shù)據(jù)傳輸，提出了多種查詢轉(zhuǎn)發(fā)機(jī)制[11～22]。最簡(jiǎn)單的機(jī)制是直接傳輸（direct transmission）[11]，即源節(jié)點(diǎn)緩存數(shù)據(jù)直到遇到目的節(jié)點(diǎn)才轉(zhuǎn)發(fā)信息。這種方式網(wǎng)絡(luò)開銷很小，但傳輸時(shí)延大、成功率低。2-HOP算法[11]中源節(jié)點(diǎn)將消息副本傳輸給最先遇到的L個(gè)中繼節(jié)點(diǎn)，源節(jié)點(diǎn)和L個(gè)中繼節(jié)點(diǎn)只將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)，消息需要兩跳到達(dá)目的節(jié)點(diǎn)，相對(duì)直接傳輸提高了傳輸效率。Vahdat等人提出的傳染路由（epidemic routing）[12]本質(zhì)上是一種泛洪算法，由于其在網(wǎng)絡(luò)中大量復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)，網(wǎng)絡(luò)資源消耗較大，且隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增多，其性能由于廣播導(dǎo)致的擁塞會(huì)急劇下降。Spyropoulos等人提出了基于效用與單副本的搜索聚焦路由協(xié)議[13]，雖然可以降低資源消耗，但帶來較大的時(shí)延。Spyropoulos等還對(duì)該協(xié)議進(jìn)行改進(jìn)，提出了Spray and Wait算法[14]，在源節(jié)點(diǎn)指定消息允許的最大副本數(shù)為L(zhǎng)，并使用基于二叉樹的方法產(chǎn)生L份副本。該機(jī)制包括Spray和Wait兩個(gè)階段，相比只允許源節(jié)點(diǎn)分發(fā)消息副本的2-HOP算法，進(jìn)一步降低傳輸時(shí)延。Sun等人[15]針對(duì)機(jī)會(huì)網(wǎng)絡(luò)中多種類型數(shù)據(jù)具有不同傳輸質(zhì)量的需求，提出了一種自適應(yīng)的數(shù)據(jù)收集機(jī)制，有效控制了網(wǎng)絡(luò)開銷。朱金奇等人[16]設(shè)計(jì)了一種基于選擇復(fù)制的傳輸策略，但節(jié)點(diǎn)實(shí)時(shí)定位需要消耗較多的能量，影響網(wǎng)絡(luò)壽命且無法適用于移動(dòng)匯聚節(jié)點(diǎn)的數(shù)據(jù)收集場(chǎng)景。Hass等人[17]討論了采用 SWIM（system wideinformation management,正廣域系統(tǒng)管理）系統(tǒng)收集鯨魚的生物信息的場(chǎng)景，該機(jī)制實(shí)際上是傳染轉(zhuǎn)發(fā)式，如果節(jié)點(diǎn)的緩存足夠大，這種機(jī)制的數(shù)據(jù)傳輸成功率就高，但網(wǎng)絡(luò)開銷較大。Princeton大學(xué)的ZebraNet項(xiàng)目[1]是追蹤并研究斑馬活動(dòng)習(xí)性的網(wǎng)絡(luò)系統(tǒng)，但由于傳感器節(jié)點(diǎn)與基站相遇的機(jī)會(huì)很少，數(shù)據(jù)的傳輸可靠性較低。Wang等人[18]對(duì)該轉(zhuǎn)發(fā)機(jī)制進(jìn)行了改進(jìn)，提高了節(jié)點(diǎn)和基站相遇的概率。Wang等人還建議采用 FAD （fault tolerance based adaptive data delivery）策略[19,20]，但FAD策略忽略了消息的存活時(shí)間。Pasztor B等[21]提出的SCAR（sensor contex-aware routing）機(jī)制依靠節(jié)點(diǎn)上下文信息定義傳輸概率。Song等[22]提出的ProPHET協(xié)議則基于歷史記錄預(yù)測(cè)節(jié)點(diǎn)接觸概率。

與本文研究最相關(guān)的是Fiore等[23]提出的Eureka算法，其移動(dòng)節(jié)點(diǎn)估算其鄰近范圍內(nèi)的信息密度并把查詢結(jié)果向密度大的區(qū)域發(fā)送，但它需為每個(gè)節(jié)點(diǎn)建立信息密度索引，維護(hù)成本高，同時(shí)也面臨信息更新時(shí)的高通信開銷問題。本文提出的IA方法能在常見的移動(dòng)環(huán)境下更好地適應(yīng)具有頻繁數(shù)據(jù)更新的高度動(dòng)態(tài)網(wǎng)絡(luò)，實(shí)驗(yàn)表明本文所提方法的性能優(yōu)于其他算法。

3 基于鄰居信息精確度的查詢策略

對(duì)于延遲容忍網(wǎng)絡(luò)中基于鄰居信息精確度的查詢策略，其主要思想是模仿社會(huì)網(wǎng)絡(luò)中人的行為，從而提高查詢的效率，即模仿人從經(jīng)驗(yàn)中學(xué)習(xí)，節(jié)點(diǎn)（設(shè)備視為網(wǎng)絡(luò)中的節(jié)點(diǎn)）在查詢處理后調(diào)整信息精確度值；模仿人的閑談方式來交換、更新鄰居信息；模仿人從熟人那獲取答案的自然行為來確定查詢的轉(zhuǎn)發(fā)策略。如圖1所示，查詢路由可分解為多個(gè)步驟，在每一步中，攜帶查詢信息的節(jié)點(diǎn)根據(jù)其鄰居節(jié)點(diǎn)提供的信息及信息精確度將查詢信息轉(zhuǎn)發(fā)給其可達(dá)范圍內(nèi)的某一個(gè)鄰居節(jié)點(diǎn)。其中，L表示查詢的路徑長(zhǎng)度，K表示處于第K跳的位置。本文使用TTL（time-to-live）控制查詢信息的轉(zhuǎn)發(fā)跳數(shù)，如果查詢信息的轉(zhuǎn)發(fā)跳數(shù)大于或等于TTL且沒有發(fā)現(xiàn)所要查詢的結(jié)果時(shí)，則認(rèn)為此條信息查詢失?。环駝t，資源提供者（R-provider）按照查詢路徑將資源發(fā)送給查詢節(jié)點(diǎn)（Q-issuer）。

圖1 查詢路由示例

3.1 信息精確度

在介紹查詢策略之前，先介紹鄰居信息以及計(jì)算鄰居信息精確度的方法。鄰居信息是指對(duì)于某一查詢，鄰居節(jié)點(diǎn)所知道的關(guān)于此查詢相關(guān)結(jié)果所在節(jié)點(diǎn)的信息，這些信息主要通過鄰居節(jié)點(diǎn)之間的信息交換及查詢轉(zhuǎn)發(fā)的經(jīng)驗(yàn)獲取。如圖2所示，每個(gè)節(jié)點(diǎn)都保持兩張索引表，圖2（a）的索引表稱為自包含數(shù)據(jù)項(xiàng)（self-contained item，SCI），保存節(jié)點(diǎn)本身已有的信息，主要用來和鄰居節(jié)點(diǎn)進(jìn)行信息交換；圖2（b）的索引表稱為鄰居節(jié)點(diǎn)數(shù)據(jù)項(xiàng) （neighbors’item，NI），主要從鄰居節(jié)點(diǎn)處收集而來，記錄鄰居節(jié)點(diǎn)的相關(guān)信息，用來決定查詢轉(zhuǎn)發(fā)的方向。

圖2 索引表結(jié)構(gòu)

IA是查詢節(jié)點(diǎn)到最近資源提供節(jié)點(diǎn)距離的評(píng)判標(biāo)準(zhǔn)。設(shè)節(jié)點(diǎn)i保存的數(shù)據(jù)項(xiàng)j的信息精確度為Ii,j，由于是高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境，設(shè)置參數(shù)time表示數(shù)據(jù)信息的實(shí)效性。本文按如下步驟計(jì)算信息精確度值。

（1）對(duì)于節(jié)點(diǎn)本身提供的數(shù)據(jù)信息，將數(shù)據(jù)信息的精確度設(shè)置為I0，表示網(wǎng)絡(luò)內(nèi)最大的IA值；時(shí)間參數(shù)設(shè)置為T0，表示本節(jié)點(diǎn)可提供的信息，一直可利用直到數(shù)據(jù)被更新或刪除。

（2）轉(zhuǎn)發(fā)查詢結(jié)果信息j后，中介節(jié)點(diǎn)NI表中關(guān)于數(shù)據(jù)信息j的IA值和時(shí)間參數(shù)都需要更新。IA值更新的策略遵循這一原則:節(jié)點(diǎn)越靠近數(shù)據(jù)項(xiàng)信息j的提供者，則此節(jié)點(diǎn)NI表中關(guān)于數(shù)據(jù)項(xiàng)信息j的IA值就越大。在實(shí)際執(zhí)行過程中，為了提高網(wǎng)絡(luò)環(huán)境中數(shù)據(jù)的查詢成功率，將查詢結(jié)果在查詢發(fā)起節(jié)點(diǎn)緩存一段時(shí)間。在這期間，查詢發(fā)起節(jié)點(diǎn)也可以作為資源的提供者。如果查詢發(fā)起節(jié)點(diǎn)的存儲(chǔ)空間已滿，則將最老的緩存數(shù)據(jù)刪除，緩存時(shí)間要根據(jù)具體的應(yīng)用環(huán)境而定。之所以不將查詢結(jié)果在中間節(jié)點(diǎn)暫存，是基于平衡數(shù)據(jù)分發(fā)與設(shè)備存儲(chǔ)消耗的考慮。查詢發(fā)起節(jié)點(diǎn)內(nèi)的緩存數(shù)據(jù)對(duì)查詢發(fā)起節(jié)點(diǎn)周圍鄰居節(jié)點(diǎn)中關(guān)于此數(shù)據(jù)的IA值也會(huì)有影響，調(diào)整IA值時(shí)必須考慮這一影響。因此，本文調(diào)整相關(guān)數(shù)據(jù)信息的IA值是根據(jù)它和相關(guān)資源提供者及緩存點(diǎn)的位置而定的。如圖3所示，若節(jié)點(diǎn)離源節(jié)點(diǎn)或緩存節(jié)點(diǎn)近，則其IA值就高；反之，其IA值就低。

圖3 IA值的調(diào)整

本文使用類似正態(tài)分布函數(shù)模擬IA值的調(diào)整。假設(shè)查詢數(shù)據(jù)項(xiàng) j，節(jié)點(diǎn)i是數(shù)據(jù)項(xiàng)j查詢轉(zhuǎn)發(fā)路徑上的節(jié)點(diǎn)，節(jié)點(diǎn)i處于第K跳位置上且路徑長(zhǎng)度為L(zhǎng)，如圖1所示，本文使用式（1）計(jì)算節(jié)點(diǎn)i中關(guān)于數(shù)據(jù)項(xiàng) j調(diào)整后的IA值。

式（1）是調(diào)整后的正態(tài)分布函數(shù)，期望值 μ=[（L+1）/2]，方差σ=1/L。如圖1所示的查詢轉(zhuǎn)發(fā)過程中，K=0和K=3處節(jié)點(diǎn)的IA值都是I0；而K=1和K=2處節(jié)點(diǎn)的IA值I

（3）節(jié)點(diǎn)i通過信息交換從其鄰居節(jié)點(diǎn)處收集數(shù)據(jù)信息并更新本地保存的NI表:

其中，Mi，j是由更新時(shí)間及IA值計(jì)算出來的，表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)內(nèi)關(guān)于數(shù)據(jù)項(xiàng)j的最大轉(zhuǎn)發(fā)權(quán)重。若IA值大，并且與上一次更新時(shí)間間隔短，則轉(zhuǎn)發(fā)權(quán)重就大（因?yàn)橛械腎A值可能會(huì)比較大，但是在很久之前更新的，這個(gè)較大的IA值不一定精確）。文中部分符號(hào)含義見表1。

3.2 查詢轉(zhuǎn)發(fā)算法

基于上述討論，信息精確度值一定程度上表示節(jié)點(diǎn)到源節(jié)點(diǎn)的距離。對(duì)于某項(xiàng)要查詢的數(shù)據(jù)項(xiàng)j，某個(gè)節(jié)點(diǎn)IA值越接近I0j，則說明此節(jié)點(diǎn)越靠近網(wǎng)絡(luò)中提供數(shù)據(jù)項(xiàng)j的資源節(jié)點(diǎn)，節(jié)點(diǎn)i將查詢轉(zhuǎn)發(fā)給Ii，j值大的鄰居節(jié)點(diǎn)。若考慮時(shí)間因素，則最近更新的IA值最精確。綜合以上考慮，本文的信息查詢算法設(shè)計(jì)如下。

表1 文中部分符號(hào)含義

（1）節(jié)點(diǎn)i接收到一個(gè)數(shù)據(jù)項(xiàng)j查詢請(qǐng)求，查看本地是否有數(shù)據(jù)項(xiàng)j，若有則將數(shù)據(jù)項(xiàng)j發(fā)送給查詢請(qǐng)求節(jié)點(diǎn)。

（2）如果節(jié)點(diǎn)i本身沒有數(shù)據(jù)項(xiàng)j，則根據(jù)NI表把查詢轉(zhuǎn)發(fā)給其Ni個(gè)鄰居節(jié)點(diǎn)中關(guān)于數(shù)據(jù)項(xiàng)j具有最大權(quán)重的鄰居節(jié)點(diǎn)，此點(diǎn)經(jīng)過式（2）、式（3）計(jì)算后保存在NI表中:

其中，Ni，k指節(jié)點(diǎn)i鄰居節(jié)點(diǎn)中的第k個(gè)節(jié)點(diǎn) ，I（Ni，k），j是節(jié)點(diǎn) i的鄰居節(jié)點(diǎn) Ni，k關(guān)于數(shù)據(jù)項(xiàng) j的 IA值，NIi是節(jié)點(diǎn)i的NI表，Node是最終選出的接收查詢信息的鄰居節(jié)點(diǎn)。

（3）如果節(jié)點(diǎn)i所有鄰居節(jié)點(diǎn)關(guān)于數(shù)據(jù)項(xiàng)j的精確度值Ii，j都是 0，即鄰居節(jié)點(diǎn)中沒有關(guān)于數(shù)據(jù)項(xiàng)j的信息，節(jié)點(diǎn) i把查詢轉(zhuǎn)發(fā)給其鄰居節(jié)點(diǎn)中總體信息精確值最高的節(jié)點(diǎn)Vi，Vi由式（5）計(jì)算得出:

其中，SCIk指Numi個(gè)鄰居節(jié)點(diǎn)中第k個(gè)鄰居節(jié)點(diǎn)的SCI表，|SCIk|表示SCIk表中的數(shù)據(jù)項(xiàng)數(shù)。節(jié)點(diǎn)i將查詢發(fā)送給總體信息精確度值最高的鄰居節(jié)點(diǎn)，就像人們經(jīng)常會(huì)向知識(shí)淵博的熟人詢問問題一樣?？傮w信息精確度最高的節(jié)點(diǎn)可使得查詢通過它找到查詢的結(jié)果，通過這樣的節(jié)點(diǎn)查詢成功率就會(huì)提高。Vi是由鄰居節(jié)點(diǎn)和交換更新信息計(jì)算得來的。

3.3 查詢結(jié)果返回情況的處理

在延遲容忍網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)是自由的。當(dāng)查詢信息查詢到結(jié)果時(shí)，需要考慮如何將結(jié)果順利返回到查詢節(jié)點(diǎn)處，介紹如下。

當(dāng)查詢信息轉(zhuǎn)發(fā)路徑上的節(jié)點(diǎn)都在彼此的通信范圍內(nèi)時(shí)，可以直接將結(jié)果按照查詢路徑返回給查詢節(jié)點(diǎn)，如圖1所示。

當(dāng)查詢轉(zhuǎn)發(fā)路徑上的某一個(gè)節(jié)點(diǎn)移出下一跳鄰居節(jié)點(diǎn)的通信范圍時(shí)，如何將結(jié)果返回給查詢節(jié)點(diǎn)呢？本文采取的方法是:某一個(gè)節(jié)點(diǎn)在向鄰居節(jié)點(diǎn)傳送查詢信息時(shí)，在本節(jié)點(diǎn)通信范圍和所選擇的鄰居節(jié)點(diǎn)通信范圍的交集內(nèi)選擇一個(gè)節(jié)點(diǎn)備份數(shù)據(jù)信息。此備份的數(shù)據(jù)信息包含有關(guān)上一跳節(jié)點(diǎn)的相關(guān)位置信息，以此增加結(jié)果返回的成功率。如圖4所示，節(jié)點(diǎn)P1向鄰居節(jié)點(diǎn)P2轉(zhuǎn)發(fā)查詢信息時(shí)，會(huì)在P1和P2通信范圍的交集內(nèi)選擇一點(diǎn)P1’備份P1的數(shù)據(jù)信息。同理，節(jié)點(diǎn)P2、P3也會(huì)選擇數(shù)據(jù)備份點(diǎn)。當(dāng)節(jié)點(diǎn)P3接收節(jié)點(diǎn)P4返回的結(jié)果后，P3會(huì)檢查其上一跳節(jié)點(diǎn)P2是否還在其通信范圍內(nèi)，若在，則直接將結(jié)果傳送給P2；若已移出P3的通信范圍，則節(jié)點(diǎn)P3選擇P2的備份節(jié)點(diǎn)P2’作為轉(zhuǎn)發(fā)的中介節(jié)點(diǎn)向查詢發(fā)起節(jié)點(diǎn)發(fā)送結(jié)果。

圖4 查詢路由示例

3.4 網(wǎng)絡(luò)動(dòng)態(tài)及數(shù)據(jù)更新

在延遲容忍網(wǎng)絡(luò)中，移動(dòng)節(jié)點(diǎn)可以自由地加入或離開網(wǎng)絡(luò)，并且移動(dòng)節(jié)點(diǎn)可以任意地添加、刪除和修改數(shù)據(jù)，網(wǎng)絡(luò)具有很高的動(dòng)態(tài)性。在這種不穩(wěn)定的網(wǎng)絡(luò)環(huán)境下進(jìn)行通信和維護(hù)數(shù)據(jù)更新的開銷非常大。實(shí)驗(yàn)表明，本文提出的IA方法在處理這種不穩(wěn)定網(wǎng)絡(luò)的數(shù)據(jù)更新時(shí)效果較好。下面介紹如何利用IA方法處理網(wǎng)絡(luò)動(dòng)態(tài)及數(shù)據(jù)的更新。

（1）節(jié)點(diǎn)的加入或離開

如果一個(gè)新的節(jié)點(diǎn)加入網(wǎng)絡(luò)，它只需將其本身自帶的數(shù)據(jù)IA值發(fā)送給它可達(dá)范圍內(nèi)的鄰居節(jié)點(diǎn)。鄰居節(jié)點(diǎn)收到此信息后將其看作一個(gè)正常的NI表更新來處理；如果一個(gè)節(jié)點(diǎn)離開網(wǎng)絡(luò)，它可以通知其鄰居節(jié)點(diǎn)，也可以什么都不做直接離開。即使一個(gè)節(jié)點(diǎn)悄悄地離開，也可以通過查詢轉(zhuǎn)發(fā)及NI的更新將關(guān)于此點(diǎn)的相關(guān)信息很快刪除。

（2）數(shù)據(jù)的插入或刪除

對(duì)于節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)，如果某條數(shù)據(jù)被刪除，則把SCI表中此數(shù)據(jù)項(xiàng)的I和T都設(shè)置為0，并通知其鄰居節(jié)點(diǎn)；如果添加一條新的數(shù)據(jù)項(xiàng)，則在SCI表中添加一個(gè)新的項(xiàng)，把此數(shù)據(jù)設(shè)為I0、T0并通知其鄰居節(jié)點(diǎn)。接收到通知信息的鄰居節(jié)點(diǎn)僅執(zhí)行正常的NI表更新過程。

（3）數(shù)據(jù)的修改

如果一條數(shù)據(jù)被修改，在這種不穩(wěn)定的網(wǎng)絡(luò)環(huán)境下很難就地修改其他節(jié)點(diǎn)的相關(guān)數(shù)據(jù)信息。為此設(shè)置數(shù)據(jù)的版本信息，將修改后的數(shù)據(jù)作為新的數(shù)據(jù)添加到節(jié)點(diǎn)。查詢節(jié)點(diǎn)可以通過數(shù)據(jù)的版本號(hào)區(qū)分?jǐn)?shù)據(jù)的新舊。查詢節(jié)點(diǎn)選取它所查詢到的最新版本的數(shù)據(jù)作為最終結(jié)果。即使某條數(shù)據(jù)不是最新版本的數(shù)據(jù)，在沒有找到最新版本數(shù)據(jù)之前仍舊是可以利用的，如果一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)新的版本數(shù)據(jù)，將丟棄舊版本數(shù)據(jù)的相關(guān)索引和緩存副本，并用新的代替。

通過以上論述，除了NI的更新，對(duì)于網(wǎng)絡(luò)動(dòng)態(tài)性和數(shù)據(jù)更新問題不需要額外的開銷，本文提出的方法可以很好地應(yīng)用于高動(dòng)態(tài)性的網(wǎng)絡(luò)。

4 通信開銷及能量消耗

4.1 通信開銷

本文以發(fā)送的信息量來表示通信開銷C，發(fā)送的信息包括查詢請(qǐng)求信息、查詢結(jié)果返回信息及更新信息。為了表述清晰，將一條信息的大小統(tǒng)一記為m，接下來分析查詢轉(zhuǎn)發(fā)及更新IA值的通信開銷。

如前所述，如果查詢節(jié)點(diǎn)成功查詢到結(jié)果時(shí)的路由跳數(shù)為L(zhǎng)，否則為TTL。在查詢路徑中，每個(gè)節(jié)點(diǎn)根據(jù)本地索引選擇一個(gè)鄰居節(jié)點(diǎn)，然后將查詢請(qǐng)求轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，一次只發(fā)送一條信息。查詢結(jié)果的返回信息也按照此方式進(jìn)行。通信開銷C為:

在通信開銷中，主要是IA值的更新開銷，因?yàn)楹芏噙^程本質(zhì)上是IA值的更新，比如節(jié)點(diǎn)的加入或離開過程、數(shù)據(jù)的添加和刪除及更新過程。對(duì)于節(jié)點(diǎn)i，假設(shè)它有Ni個(gè)鄰居節(jié)點(diǎn)，在更新過程中，節(jié)點(diǎn)i只需向每個(gè)鄰居節(jié)點(diǎn)發(fā)送一條信息mi，鄰居節(jié)點(diǎn)接收到信息后，只需自動(dòng)更新它們的NI表。節(jié)點(diǎn)i關(guān)于某條數(shù)據(jù)IA值更新的通信開銷為:

4.2 能量消耗

在轉(zhuǎn)發(fā)或更新IA值時(shí)要考慮移動(dòng)設(shè)備電池的能量消耗問題。節(jié)點(diǎn)能量消耗與通信量成正比。假設(shè)節(jié)點(diǎn)i一次轉(zhuǎn)發(fā)（或更新）的能量消耗是ei，移動(dòng)設(shè)備可以配置成多個(gè)能量水平狀態(tài)傳輸數(shù)據(jù)分組，不同能量水平的可達(dá)范圍也是不同的，為了簡(jiǎn)化計(jì)算，假設(shè)網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量水平是相同的，記為p，則每個(gè)節(jié)點(diǎn)有相同的可達(dá)通信范圍。節(jié)點(diǎn)i發(fā)送一個(gè)消息數(shù)據(jù)的能量開銷為:

其中，σi是參數(shù)，反映節(jié)點(diǎn)電池電量及計(jì)算單元數(shù)據(jù)開銷情況。

在查詢轉(zhuǎn)發(fā)過程中，分以下兩種情況解釋能量的消耗:

·如果節(jié)點(diǎn)i不在查詢路徑上，則節(jié)點(diǎn)i不參與查詢信息的轉(zhuǎn)發(fā)，其能量開銷ei=0；

·如果節(jié)點(diǎn)i位于查詢路徑上，節(jié)點(diǎn)i在能量水平為p的情況下轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)單元的查詢請(qǐng)求或者返回查詢結(jié)果，其能量開銷均為p×σi。

另外，節(jié)點(diǎn)i接收一個(gè)數(shù)據(jù)單元的能量消耗為固定值ri。對(duì)于網(wǎng)絡(luò)中的任意中間節(jié)點(diǎn)Eitm，它在查詢轉(zhuǎn)發(fā)和返回結(jié)果過程中都要接收和轉(zhuǎn)發(fā)信息兩次，能量開銷為:

對(duì)于查詢發(fā)起節(jié)點(diǎn)Eisr或資源提供節(jié)點(diǎn)Ersp，它們僅接收和轉(zhuǎn)發(fā)信息一次，其能量開銷為:

對(duì)于向其Ni個(gè)鄰居節(jié)點(diǎn)更新某項(xiàng)數(shù)據(jù)IA值的節(jié)點(diǎn)，其能量開銷Eupd為:

5 實(shí)驗(yàn)與分析

本文模擬實(shí)現(xiàn)了IA、Eureka[23]、Epidemic算法，主要從以下3個(gè)方面進(jìn)行性能分析:

·對(duì)網(wǎng)絡(luò)通信量、查詢響應(yīng)時(shí)間、查詢成功率及能量消耗進(jìn)行功能比較；

·研究不同的實(shí)驗(yàn)參數(shù)對(duì)3種算法產(chǎn)生的影響；

·分析比較IA與其他兩種算法的優(yōu)缺點(diǎn)。

本文將Epidemic算法作為基本方法進(jìn)行參考比較，同時(shí)也和Eureka算法相比較。Eureka算法中每個(gè)移動(dòng)節(jié)點(diǎn)都維持其范圍內(nèi)資源信息的密度大小，根據(jù)密度大小轉(zhuǎn)發(fā)查詢信息。

5.1 模擬環(huán)境

實(shí)驗(yàn)是基于ONE Simulator仿真[24]平臺(tái)設(shè)計(jì)實(shí)現(xiàn)的。在模擬實(shí)驗(yàn)中，定義整個(gè)模擬區(qū)域?yàn)?00 m×500 m的方形區(qū)域，區(qū)域內(nèi)移動(dòng)節(jié)點(diǎn)按照隨機(jī)漫步（random waypoint）移動(dòng)模型進(jìn)行移動(dòng)，節(jié)點(diǎn)移動(dòng)速度在[0.5，1.5]km/h內(nèi)隨機(jī)選取，移動(dòng)節(jié)點(diǎn)的通信半徑為10 m，節(jié)點(diǎn)緩存為50 MB。消息大小統(tǒng)一為1 KB。具體模擬參數(shù)設(shè)置見表2。

表2 模擬參數(shù)

5.2 網(wǎng)絡(luò)通信量比較

網(wǎng)絡(luò)通信量是指在模擬實(shí)驗(yàn)中網(wǎng)絡(luò)內(nèi)傳輸?shù)南⒖偭?，包括查詢信息、結(jié)果返回信息、信息更新等，通信量按照第4.1節(jié)所述方法計(jì)算。如圖5所示，本文提出的IA方法明顯優(yōu)于另外兩種方法。IA和Eureka算法都是采用索引保存有用的信息，但Eureka算法的通信量明顯高于IA，這主要是由其低效的索引更新引起的。在Eureka算法中，當(dāng)有數(shù)據(jù)更新發(fā)生時(shí)，節(jié)點(diǎn)就將更新后的索引值發(fā)送給其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)接收到更新信息后同樣將更新后的信息發(fā)送給它們的鄰居節(jié)點(diǎn)，這樣每一次更新都可能會(huì)涉及網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。而IA方法索引更新是在查詢過程中，某一節(jié)點(diǎn)以一個(gè)固定的時(shí)間間隔向其鄰居節(jié)點(diǎn)發(fā)送更新信息，不會(huì)像Eureka算法那樣出現(xiàn)遞歸現(xiàn)象。

5.3 查詢響應(yīng)時(shí)間性能比較

查詢響應(yīng)時(shí)間是指從查詢信息發(fā)出到查詢結(jié)果返回到查詢節(jié)點(diǎn)所用的時(shí)間，是判斷查詢優(yōu)劣的重要標(biāo)準(zhǔn)之一。在模擬實(shí)驗(yàn)中，本文只計(jì)算查詢成功的查詢響應(yīng)時(shí)間。為每條查詢信息設(shè)置一個(gè)時(shí)間閾值，如果一條查詢信息在時(shí)間閾值內(nèi)沒有任何返回則認(rèn)為此條查詢失敗。如圖6所示，Epidemic算法的查詢響應(yīng)時(shí)間最短，這主要是它泛洪查詢信息的結(jié)果。本文提出的IA方法的響應(yīng)時(shí)間比Eureka算法快，這意味著IA方法的查詢路徑要比Eureka算法短，這主要是因?yàn)镮A方法中各個(gè)節(jié)點(diǎn)相互配合并根據(jù)數(shù)據(jù)信息精確度選擇出一條最優(yōu)的查詢路徑。

圖5 網(wǎng)絡(luò)通信量性能比較

圖6 查詢響應(yīng)時(shí)間性能比較

5.4 查詢成功率性能比較

查詢成功率是指查詢信息的成功數(shù)占查詢信息的比重，計(jì)算式如下:

圖7顯示了不同方法的查詢成功率，即同樣的信息量不同網(wǎng)絡(luò)規(guī)模（節(jié)點(diǎn)數(shù)量多少）情況下的成功率，與網(wǎng)絡(luò)規(guī)模相關(guān)。很明顯，Epidemic算法的成功率最高，這是其泛洪查詢信息的結(jié)果。比較IA和Eureka算法可發(fā)現(xiàn)，IA方法的成功率低于Eureka算法，當(dāng)節(jié)點(diǎn)增多、網(wǎng)絡(luò)規(guī)模變大時(shí)，IA方法優(yōu)于Eureka算法。盡管IA方法只選擇一條路徑轉(zhuǎn)發(fā)查詢信息，但其可以有效地獲取數(shù)據(jù)資源相關(guān)信息并按照信息精確度選擇最可靠的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢信息。在高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境下，節(jié)點(diǎn)不斷地移動(dòng)、數(shù)據(jù)不斷地更新，高查詢成功率表明本文提出的IA方法的穩(wěn)定性高于Eureka算法。

對(duì)于本文中提出的IA算法，不同更新頻率對(duì)查詢成功率的影響也要考慮。本文為驗(yàn)證更新頻率對(duì)查詢成功率的影響，在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為150個(gè)、獨(dú)立數(shù)據(jù)量為150 MB的環(huán)境下進(jìn)行實(shí)驗(yàn)。在更新間隔時(shí)間分別為[3,6,9,12,15,18,21]時(shí)，對(duì)查詢成功率進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖8所示?？梢钥闯?，更新時(shí)間越長(zhǎng)，查詢成功率越低。當(dāng)更新間隔時(shí)間為[18,21,24]時(shí)，成功率出現(xiàn)平緩趨勢(shì)，即更新間隔時(shí)間大到一定時(shí)間時(shí)，成功率趨于穩(wěn)定。

圖7 查詢成功率性能比較

圖8 更新時(shí)間對(duì)查詢成功率的影響

5.5 能量消耗性能的比較

只要移動(dòng)節(jié)點(diǎn)參與查詢過程，就會(huì)產(chǎn)生能量消耗。按照第4.2節(jié)的方法計(jì)算節(jié)點(diǎn)的能量消耗。如圖9所示的平均電池能量消耗對(duì)比，IA方法的能量消耗比另外兩種方法要低。能量消耗和網(wǎng)絡(luò)通信量有密切的關(guān)系，信息傳輸量越大，能量消耗就越大。Eureka算法比Epidemic算法能量消耗大，主要是由其索引更新及查詢策略引起的。對(duì)于每一個(gè)查詢，Eureka算法都會(huì)將此查詢泛洪給所有的鄰居節(jié)點(diǎn)，只有少數(shù)幾個(gè)鄰居節(jié)點(diǎn)會(huì)根據(jù)自身索引轉(zhuǎn)發(fā)此查詢，大多數(shù)鄰居節(jié)點(diǎn)不進(jìn)行任何操作，能量就浪費(fèi)在這些過程中；另外，Eureka算法的索引更新涉及網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)，這也需要消耗大量的能量。

圖9 能量消耗對(duì)比

6 結(jié)束語

本文主要解決了延遲容忍網(wǎng)絡(luò)中基于鄰居信息精確度的查詢問題。提出的IA方案充分利用了移動(dòng)設(shè)備的特性分享有用的資源信息?；卩従有畔⒕_度的IA算法通過模仿社會(huì)網(wǎng)絡(luò)中人的行為來幫助移動(dòng)設(shè)備轉(zhuǎn)發(fā)查詢信息，采用信息精確度機(jī)制使得算法在查詢資源時(shí)是輕量高效的。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能更好地適應(yīng)高度動(dòng)態(tài)型的延遲容忍網(wǎng)絡(luò)，與其他算法相比，本文提出的IA算法查詢成功率更高，傳輸能耗低且性能好。

1 Juang P,Oki H,Wang Y.Energy-efficient computing for wildlife tracking:design trade offs and early experiences with ZebraNet.ACM Operating System Review,2002,37（10）:96～107

2 Pent land A,Fletcher R,Hasson A.DakNet:rethinking connectivity in developing nations.Computer,2004,37（1）:78～83

3 Hull B,Bychkovsky V,Zhang Y.CarTel:a distributed mobile sensor computing system. Proceedings of the 4th Int’l Conference on Embedded Networked Sensor Systems,Boulder,2006:125～138

4 Fall K.A delay-tolerant network architecture for challenged internets.Proceedings of the ACM Conference on Computer Communications （SIGCOMM 2003）,New York,USA,2003:27～34

5 The blue tooth specification. http://www.bluetooth.com/dev/specifications.asp

6 The IEEE 802.11 standards.http://grouper.ieee.org/groups/802/11,2013

7 Conti M,Gregori E,Turi G.A cross-layer optimization of gnutella for mobile Ad Hoc networks.Proceedings of MobiHoc 2005,Urbana-Champaign,IL,USA,2005:343～354

8 Diao Y,Rizvi S,Franklin M.Towards an internet-scale xml dissemination service.Proceedings of VLDB 2004,Toronto,Canada,2004:612～623

9 Daly E M,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs.Proceedings of the 8th ACM Int’l Symp on Mobile Ad Hoc Networking and Computing（MOBIHOC 2007）,Montreal,2007:32～40

10 Pelusi L,Passarella A,Conti M.Opportunistic networking:data forwarding in disconnected mobile Ad Hoc networks.Communications Magazine,2006,44（11）:134～141

11 Grossglauser M.Mobility increases the capacity of Ad Hoc wireless networks.IEEE/ACM Transactions on Networking,2002,10（4）:477～486

12 Vahdat A,Becher D.Epidemic Routing for Partially Connected Ad Hoc Networks.Technical Report,Durham,Duke University,2000

13 Spyropoulos T,Psounis K,Raghavendra C S.Efficient routing in intermittently connected mobile networks:the single-copy case.IEEE/ACM Transactions on Network,2008,16（1）:63～76

14 Spyropoulos T,Psounis K,Raghavendra C S.Efficient routing in intermittently connected mobile networks:the multiple-copy case.IEEE/ACM Transactions on Network,2008,16（1）:77～90

15 Sun L M,Xiong Y P,Ma J.Adaptive data gathering mechanism in opportunistic mobile sensor networks. Journal on Communications,2008,29（11）:187～193

16 Zhu J Q,Liu M,Gong H G.Selective replication-based data delivery for delay tolerant mobile sensor networks.Journal of Software,2009,20（8）:2227～2240

17 Small T,Haas Z J.The shared wireless infostation model-a new Ad Hoc networking paradigm （or where there is a whale,there is a way）.Proceedings of the 4th ACM Int’l Symp on Mobile Ad HocNet working and Computing （MOBIHOC 2003）,Annapolis,2003:233～244

18 Wang Y,Wu H Y.DFT-MSN:the delay fault tolerant mobile sensor network for pervasive information gathering.Proceedings of the IEEE 25th Int’l Conference on Computer Communications（INFOCOM 2006）,Barcelona,2006:1～12

19 Wang Y,Wu H Y,Dang H.Analytic study of delay/faulttolerant mobile sensor networks （DFT-MSN’s）.Proceedings of the 10th IEEE Int’l Symp on World of Wireless,Mobile and Multimedia Networks（WoWMom 2009）,San Francisco,USA,2009:1～9

20 Wu H Y,Wang Y,Dang H,et al.Analytic,simulation and empirical evaluation of delay/fault-tolerant mobile sensor networks.IEEE Transactions on Wireless Communications,2007,6（9）:3287～3296

21 Pasztor B,Musolesi M,Mascolo C.Opportunistic mobile sensor data collection with SCAR.Proceedings of the 4th IEEE Int’l Conference on Mobile Ad Hoc and Sensor Systems（MASS 2007）,Pisa,Italy,2007:1～12

22 Song L B,Kotz D F.Evaluating opportunistic routing protocols with large realistic contact traces.Proceedings of the 2nd ACM Workshop on Challenged Networks （CHANTS 2007）,Montreal,2007:35～42

23 Fiore M,Casett C,Chiasserini C F.Efficient retrieval of user contentsin MANETs.Proceedings of 26th Annual IEEE Conference on Computer Communications,IEEE INFOCOM 2007,Anchorage,Alaska,USA,2007:10～18

24 Opportunistic network environment simulator.http://www.netlab.tkk.fi/tutkimus/dtn/theone/