周 歡 任 東 徐守志蔣廷耀 黃志勇

(三峽大學(xué)湖北省水電工程智能視覺(jué)監(jiān)測(cè)重點(diǎn)實(shí)驗(yàn)室 宜昌 443002)

(三峽大學(xué)計(jì)算機(jī)與信息學(xué)院 宜昌 443002)

延遲容忍網(wǎng)絡(luò)中能量有效的接觸探測(cè)研究

周 歡 任 東 徐守志*蔣廷耀 黃志勇

(三峽大學(xué)湖北省水電工程智能視覺(jué)監(jiān)測(cè)重點(diǎn)實(shí)驗(yàn)室 宜昌 443002)

(三峽大學(xué)計(jì)算機(jī)與信息學(xué)院 宜昌 443002)

在延遲容忍網(wǎng)絡(luò)中，為了發(fā)現(xiàn)在其通信范圍內(nèi)的鄰居節(jié)點(diǎn)，網(wǎng)絡(luò)中的節(jié)點(diǎn)必須不斷地探測(cè)周圍的環(huán)境。這個(gè)接觸探測(cè)過(guò)程極其耗費(fèi)能量。如果網(wǎng)絡(luò)中的節(jié)點(diǎn)探測(cè)太過(guò)頻繁，會(huì)耗費(fèi)很多能量，且使得網(wǎng)絡(luò)能量的使用效率降低。另一方面，稀疏的探測(cè)可能導(dǎo)致節(jié)點(diǎn)失去和其它節(jié)點(diǎn)的接觸，從而錯(cuò)失交換數(shù)據(jù)的機(jī)會(huì)。因此，在延遲容忍網(wǎng)絡(luò)中能量效率和接觸機(jī)會(huì)之間存在著一種折中的關(guān)系。為了研究這種折中關(guān)系，該文首先對(duì)基于隨機(jī)路點(diǎn)模型(Random Way-Point model, RWP)的接觸探測(cè)過(guò)程進(jìn)行建模，得到恒定探測(cè)間隔下接觸探測(cè)概率的表達(dá)式，并且證明在所有平均探測(cè)間隔相同的策略中，以恒定間隔探測(cè)的策略是最優(yōu)的。其次，基于提出的理論模型，分析不同情況下能量效率和接觸探測(cè)概率之間的折中。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該理論模型的正確性。

延遲容忍網(wǎng)絡(luò)；能量效率；接觸探測(cè)；隨機(jī)路點(diǎn)模型

1 引言

近年來(lái)，隨著裝備有Wi-Fi 接口或者藍(lán)牙接口的無(wú)線便攜設(shè)備(如：Ipad, PDAs，智能手機(jī)等)的普及和流行，基于延遲容忍網(wǎng)絡(luò)(Delay Tolerant Networks, DTNs)方面的應(yīng)用得到了蓬勃的發(fā)展[1]。延遲容忍網(wǎng)絡(luò)又稱為間歇性連通網(wǎng)(Intermittently Connected Networks, ICNs)，稀疏網(wǎng)絡(luò)(SparseNetworks)，或機(jī)會(huì)移動(dòng)網(wǎng)絡(luò)(Opportunistic Mobile Networks, OppNets)，是無(wú)線網(wǎng)絡(luò)中一個(gè)新興的研究熱點(diǎn)[2?5]。延遲容忍網(wǎng)絡(luò)目前還沒(méi)有統(tǒng)一的定義，泛指由于節(jié)點(diǎn)的稀疏分布、快速移動(dòng)和無(wú)線通信技術(shù)的限制等原因造成的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間不存在完整的端到端連接的一類特殊的移動(dòng)自組織網(wǎng)。

在延遲容忍網(wǎng)絡(luò)中，為了實(shí)現(xiàn)節(jié)點(diǎn)之間的數(shù)據(jù)傳輸，網(wǎng)絡(luò)中的節(jié)點(diǎn)必須不斷地探測(cè)周圍的環(huán)境，從而發(fā)現(xiàn)在其通信范圍內(nèi)的鄰居節(jié)點(diǎn)。顯而易見(jiàn)，這個(gè)接觸探測(cè)過(guò)程會(huì)消耗大量能量。一些研究者在諾基亞6600手機(jī)上做了一個(gè)實(shí)驗(yàn)檢測(cè)接觸探測(cè)過(guò)程中消耗的能量，結(jié)果表明手機(jī)做一次接觸探測(cè)所需要的能量和打一次電話所需要的能量幾乎相等[6]。再者，延遲容忍網(wǎng)絡(luò)是一個(gè)接觸很稀疏的網(wǎng)絡(luò)，節(jié)點(diǎn)的接觸時(shí)間間隔遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)的接觸時(shí)長(zhǎng)；這就意味著如果網(wǎng)絡(luò)中的節(jié)點(diǎn)探測(cè)周圍的環(huán)境太頻繁，會(huì)浪費(fèi)很多的能量。因此，研究如何提高接觸探測(cè)過(guò)程中能量的使用效率是一個(gè)很緊迫的問(wèn)題。

目前，已經(jīng)有很多研究者對(duì)接觸探測(cè)過(guò)程中的能量有效問(wèn)題進(jìn)行了研究[6?12]。文獻(xiàn)[6]給出了兩種新穎的自適應(yīng)工作機(jī)制來(lái)動(dòng)態(tài)地為接觸探測(cè)過(guò)程選擇合適的參數(shù)。網(wǎng)絡(luò)中的節(jié)點(diǎn)在兩個(gè)無(wú)線電之間進(jìn)行切換：一種是低功率無(wú)線電，它采用一種慢發(fā)現(xiàn)模式去發(fā)現(xiàn)接觸和傳輸數(shù)據(jù)；另一種是高功率無(wú)線電，它根據(jù)節(jié)點(diǎn)的移動(dòng)情況采用一種快的發(fā)現(xiàn)模式發(fā)現(xiàn)接觸和傳輸數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明文中提出的自適應(yīng)算法要比靜態(tài)的能量保持算法消耗的能量減少50%，但是相應(yīng)的網(wǎng)絡(luò)性能卻能提高8%。文獻(xiàn)[7, 8]研究了延遲容忍網(wǎng)絡(luò)中探測(cè)間隔對(duì)于錯(cuò)失一次接觸的概率的影響，并且研究了接觸錯(cuò)失概率和能量消耗之間的折中。再者，通過(guò)分析真實(shí)移動(dòng)數(shù)據(jù)集中節(jié)點(diǎn)間的接觸規(guī)律，文中提出一種自適應(yīng)的接觸探測(cè)機(jī)制?；谡鎸?shí)移動(dòng)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明文中提出的自適應(yīng)的接觸探測(cè)機(jī)制要比采用恒定的接觸探測(cè)間隔的策略消耗的能量少3倍。文獻(xiàn)[9]提出一種理論模型研究接觸探測(cè)對(duì)于鏈路時(shí)長(zhǎng)的影響，以及能量消耗和吞吐量之間的折中。除此之外，該文也提供一個(gè)用于在能量有限情況下計(jì)算最優(yōu)接觸探測(cè)頻率的框架，其中每個(gè)節(jié)點(diǎn)都根據(jù)節(jié)點(diǎn)相遇率去自適應(yīng)地調(diào)整接觸探測(cè)頻率。針對(duì)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)(Delay Tolerant Mobility Sensor Network, DTMSN)節(jié)點(diǎn)間連接探測(cè)開(kāi)銷大、錯(cuò)失率高的問(wèn)題，文獻(xiàn)[11]提出一種高效的DTMSN異步探測(cè)機(jī)制。文獻(xiàn)[12]提出一種簡(jiǎn)單的自適應(yīng)的接觸探測(cè)機(jī)制去節(jié)省探測(cè)過(guò)程中消耗的能量，和文獻(xiàn)[7,8]不同，該機(jī)制需要通過(guò)GPS設(shè)備獲取節(jié)點(diǎn)的移動(dòng)速度，并且只允許節(jié)點(diǎn)在靜止或者低速移動(dòng)過(guò)程中發(fā)送探測(cè)包。

和現(xiàn)有工作不同，本文的工作側(cè)重于對(duì)基于隨機(jī)路點(diǎn)模型的接觸探測(cè)過(guò)程進(jìn)行研究，并且提出一種理論模型去研究接觸探測(cè)過(guò)程中的能量有效問(wèn)題。本文工作的創(chuàng)新點(diǎn)和主要貢獻(xiàn)為：(1)基于隨機(jī)路點(diǎn)模型，提出一種研究延遲網(wǎng)絡(luò)中接觸探測(cè)過(guò)程的理論模型。給出隨機(jī)路點(diǎn)模型中接觸時(shí)長(zhǎng)分布的情況下，從理論上得到接觸探測(cè)概率的表達(dá)式，并且證明在所有平均探測(cè)間隔相同的策略中，以恒定間隔探測(cè)的策略是最優(yōu)的。(2)基于該理論模型，得到接觸探測(cè)概率和能量消耗之間的關(guān)系，并分析不同場(chǎng)景下的能量效率和接觸探測(cè)概率之間的折中。(3)通過(guò)仿真實(shí)驗(yàn)驗(yàn)證提出的理論模型的正確性。結(jié)果表明，不同場(chǎng)景下的仿真實(shí)驗(yàn)結(jié)果和理論結(jié)果都很接近，從而證明提出的理論模型的正確性。

2 網(wǎng)絡(luò)模型

這一節(jié)介紹延遲容忍網(wǎng)絡(luò)中和接觸探測(cè)過(guò)程相關(guān)的網(wǎng)絡(luò)模型。延遲容忍網(wǎng)絡(luò)中有多種移動(dòng)模型，包括隨機(jī)路點(diǎn)模型[13]、隨機(jī)漫步模型(Random walk model)[14]和真實(shí)的移動(dòng)軌跡(Realistic mobility trace)[15]。本文集中對(duì)基于隨機(jī)路點(diǎn)模型的接觸探測(cè)過(guò)程進(jìn)行研究。在隨機(jī)路點(diǎn)模型中，考慮一種2維的正方形場(chǎng)景，面積為S，長(zhǎng)和寬都為s。在移動(dòng)模型中，每個(gè)節(jié)點(diǎn)會(huì)以相同的概率從Vmin, Vmax中選擇一個(gè)移動(dòng)速度V，然后以速度V向一個(gè)選定的目標(biāo)位置移動(dòng)。一旦到達(dá)目標(biāo)位置，節(jié)點(diǎn)會(huì)暫停一段時(shí)間，然后再選擇另外一個(gè)速度向另一個(gè)目標(biāo)位置移動(dòng)。以這種方式一直重復(fù)以上的過(guò)程。為了方便建模，假設(shè)網(wǎng)絡(luò)中總共有N個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的移動(dòng)速度V，節(jié)點(diǎn)的暫停時(shí)間相同并且為0。

在延遲容忍網(wǎng)絡(luò)中，節(jié)點(diǎn)之間處于接觸狀態(tài)當(dāng)且僅當(dāng)它們?cè)诒舜说耐ㄐ欧秶鷥?nèi)。節(jié)點(diǎn)之間不間斷地接觸的時(shí)間長(zhǎng)度定義為接觸時(shí)長(zhǎng)，同時(shí)連續(xù)的接觸之間的間隔時(shí)間被定義為接觸時(shí)間間隔。假設(shè)接觸時(shí)長(zhǎng)Td是獨(dú)立同分布的隨機(jī)變量，其累計(jì)分布函數(shù)為FTd(t)。圖1給出了一個(gè)關(guān)于兩個(gè)節(jié)點(diǎn)之間的接觸時(shí)長(zhǎng)Td和接觸時(shí)間間隔Tc的例子。為了方便分析，同時(shí)假設(shè)每次探測(cè)需要的能量是相同的，這樣節(jié)點(diǎn)的能量消耗率就可以轉(zhuǎn)化為平均的接觸探測(cè)頻率。

為了實(shí)現(xiàn)上面的數(shù)據(jù)交換過(guò)程，網(wǎng)絡(luò)中的節(jié)點(diǎn)必須不斷地探測(cè)周圍的環(huán)境去發(fā)現(xiàn)在其附近的其它節(jié)點(diǎn)。假設(shè)網(wǎng)絡(luò)中總共有 N 個(gè)節(jié)點(diǎn)。這些節(jié)點(diǎn)由一些具有藍(lán)牙接口的便攜設(shè)備組成，且有相同的通信距離 r。因?yàn)楸銛y設(shè)備中藍(lán)牙的通信距離一般小于10 m，所以本文也假設(shè)通信距離r≤10m。延遲容忍網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)是接觸的當(dāng)且僅當(dāng)兩個(gè)節(jié)點(diǎn)在彼此的通信范圍內(nèi)。但是，如果兩個(gè)節(jié)點(diǎn)在接觸過(guò)程中都沒(méi)有探測(cè)的話，也會(huì)錯(cuò)失彼此之間的接觸。因此，下面會(huì)對(duì)延遲容忍網(wǎng)絡(luò)中的接觸探測(cè)過(guò)程進(jìn)行建模。

圖1 恒定探測(cè)間隔T下兩個(gè)節(jié)點(diǎn)之間的接觸探測(cè)過(guò)程示例

3 接觸檢測(cè)過(guò)程建模

這一節(jié)首先從理論上得到當(dāng)節(jié)點(diǎn)的探測(cè)間隔為恒定值時(shí)的接觸探測(cè)概率的表達(dá)式，然后從理論上證明在所有平均接觸探測(cè)間隔相同并且節(jié)點(diǎn)的接觸過(guò)程未知的策略中，采用恒定探測(cè)間隔的策略是最優(yōu)的。

3.1 接觸探測(cè)概率

這里定義接觸探測(cè)概率 Pd為兩個(gè)節(jié)點(diǎn)之間的接觸被其中某一個(gè)節(jié)點(diǎn)探測(cè)到的概率。為了方便下面的分析，假設(shè)對(duì)于節(jié)點(diǎn)A，一個(gè)和節(jié)點(diǎn)B之間的接觸能夠被探測(cè)到(也就是有效的接觸)，當(dāng)且僅當(dāng)和節(jié)點(diǎn)B之間的接觸被節(jié)點(diǎn)A探測(cè)到，否則這次接觸就被錯(cuò)失。如圖1所示，設(shè)定節(jié)點(diǎn)A以恒定的間隔T探測(cè)，那么對(duì)于節(jié)點(diǎn)A來(lái)說(shuō)，接觸2和接觸3是有效的接觸，而接觸1則為錯(cuò)失的接觸。首先考慮網(wǎng)絡(luò)中的節(jié)點(diǎn)以恒定的間隔T探測(cè)(如圖1所示)，下面的部分會(huì)分析平均探測(cè)間隔相同的接觸探測(cè)策略。為了計(jì)算接觸探測(cè)概率 Pd，需要考慮多個(gè)參數(shù)，包括探測(cè)的間隔T和接觸時(shí)長(zhǎng) Td等。值得注意的是，當(dāng)Td≥T的時(shí)候，兩個(gè)節(jié)點(diǎn)之間的接觸都能被探測(cè)到。因此，有如下的定理：

定理1 對(duì)于以恒定的間隔T探測(cè)的節(jié)點(diǎn)A來(lái)說(shuō)，接觸探測(cè)概率可以表示為

證明 假設(shè)節(jié)點(diǎn)A在時(shí)間點(diǎn){T, 2T,…}探測(cè)其周圍的環(huán)境。為了方便建模，這里先考慮在時(shí)間范圍[0,T]內(nèi)去計(jì)算接觸探測(cè)概率。用隨機(jī)變量t代表在時(shí)間范圍[0,T]內(nèi)和節(jié)點(diǎn)A的某一次接觸發(fā)生的時(shí)間。文獻(xiàn)[5]聲明“延遲容忍網(wǎng)絡(luò)是一種很稀疏的網(wǎng)絡(luò)，因而節(jié)點(diǎn)間的接觸時(shí)間間隔要遠(yuǎn)大于探測(cè)間隔T”?；谶@個(gè)聲明，可以得出t是均勻地分布在[0,T]的范圍內(nèi)，那么這一次接觸能夠被節(jié)點(diǎn)A檢測(cè)到，如果(1)與節(jié)點(diǎn)A的接觸時(shí)間t剛好發(fā)生在節(jié)點(diǎn)A在時(shí)間T要探測(cè)周圍的環(huán)境時(shí)；(2)與節(jié)點(diǎn)A的接觸時(shí)間t發(fā)生在[0,T)的時(shí)間范圍內(nèi)，但是它們的接觸時(shí)長(zhǎng)足夠長(zhǎng)，可以保證節(jié)點(diǎn)A在時(shí)間T要探測(cè)周圍的環(huán)境時(shí)，它們?nèi)匀惶幱诮佑|的狀態(tài)。因此，接觸探測(cè)概率是上面兩個(gè)部分之和，也可以表示為式(1)。因?yàn)樵跁r(shí)間范圍(T,2T],(2T,3T],…內(nèi)的接觸探測(cè)過(guò)程和[0,T]范圍內(nèi)的接觸探測(cè)過(guò)程類似，所以接觸探測(cè)概率可以表示為式(1)。 證畢

如果節(jié)點(diǎn)之間的接觸時(shí)長(zhǎng)Td服從一個(gè)給定的分布，就可以從理論上得到能量消耗和Pd(T)之間關(guān)系。文獻(xiàn)[16, 17]顯示隨機(jī)路點(diǎn)模型中的Td是獨(dú)立同分布的變量，其累計(jì)分布函數(shù)FTd(t)可以表示為

其中r是節(jié)點(diǎn)的通信范圍，V是節(jié)點(diǎn)的移動(dòng)速度。根據(jù)式(2)可以看出，F(xiàn)Td(t)不能積分。為了方便下面的建模，考慮將式(2)進(jìn)行簡(jiǎn)化。如果t≤r/V，可以得到

如果t＞r/V，根據(jù)式(3)，可以得到

因此，式(2)的近似值可以表示為

圖2給出了在不同場(chǎng)景下FTd(t)的近似值(App)和精確值(Pre)的比較。從圖中可以看出，隨著接觸時(shí)長(zhǎng)Td的增加，F(xiàn)Td(t)的近似值和精確值很接近，特別是當(dāng)r = 6 m, V = 6 m/s時(shí)。因此，在下面的建模中，本文直接用FTd(t)的近似表達(dá)式來(lái)代替FTd(t)的精確表達(dá)式去計(jì)算接觸探測(cè)概率。

將式(5)代入式(1)中，可以得到接觸探測(cè)概率Pd(T)的表達(dá)式為

3.2 最優(yōu)接觸探測(cè)策略

上面僅僅給出了當(dāng)節(jié)點(diǎn)的探測(cè)間隔為恒定值時(shí)的接觸探測(cè)概率。事實(shí)上，在隨機(jī)路點(diǎn)模型中，在所有平均接觸探測(cè)間隔相同并且節(jié)點(diǎn)的接觸過(guò)程未知的策略中，采用恒定探測(cè)間隔的策略是最優(yōu)的。

定理 2 考慮一個(gè)總共有 N 個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的環(huán)境，并且節(jié)點(diǎn)的接觸時(shí)長(zhǎng)是獨(dú)立同分布的。再者，網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)有相同的接觸時(shí)間間隔分布，且平均接觸時(shí)間間隔為1/λ。那么，在所有平均接觸探測(cè)間隔相同并且節(jié)點(diǎn)的接觸過(guò)程未知的策略中，采用恒定探測(cè)間隔的策略是最優(yōu)的。

證明 不失一般性，考慮網(wǎng)絡(luò)中的節(jié)點(diǎn)要在一段很長(zhǎng)的時(shí)間 L 內(nèi)探測(cè)周圍的環(huán)境，并且采用不同策略的節(jié)點(diǎn)在這段時(shí)間內(nèi)總共探測(cè) n 次。根據(jù)前面的介紹，對(duì)于采用恒定的探測(cè)間隔T=L/n的策略，在時(shí)間L 內(nèi)的接觸探測(cè)概率為Pd(T)=1F(t)dt。假設(shè)某一個(gè)特定的策略在時(shí)間點(diǎn)Tdt1,t2,…,tn探測(cè)總共 n 次，并且t1＜t2＜…＜tn, tn?t1≤L。設(shè)定t0=0，然后就可以得到 n 個(gè)接觸探測(cè)間隔：I1=t1?t0,I2=t2?t1,…,In=tn?tn?1。因?yàn)楣?jié)點(diǎn)是隨機(jī)地選擇時(shí)間點(diǎn)tk探測(cè)，并且網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)有相同的接觸時(shí)間間隔分布，其平均接觸時(shí)間間隔為1/λ，因此，在第 k 個(gè)時(shí)間間隔Ik=tk?tk?1內(nèi)被某個(gè)節(jié)點(diǎn)探測(cè)到的有效接觸的期望數(shù)可以表示為：λ(N?1)(Ik?FTd(t)dt )，這里 N 是網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)。然后，在時(shí)間 L 內(nèi)的期望接觸探測(cè)概率可以表示為

當(dāng)Ik≥T時(shí)，可以得到

當(dāng)Ik＜T時(shí)，可以得到

將式(8)和式(9)代入式(7)中，可以得到

隨機(jī)路點(diǎn)模型中接觸時(shí)長(zhǎng)的分布是獨(dú)立同分布的，并且節(jié)點(diǎn)對(duì)有相同的接觸時(shí)間間隔分布，其分布可以近似為具有相同的接觸率的指數(shù)分布[18?19]。因此，可以得出在隨機(jī)路點(diǎn)模型中，在所有平均接觸探測(cè)間隔相同并且節(jié)點(diǎn)接觸過(guò)程無(wú)法預(yù)知的策略中，采用恒定探測(cè)間隔的策略是最優(yōu)的。 證畢

3.3 能量效率和接觸探測(cè)概率之間的折中

基于前面得到的接觸探測(cè)概率的表達(dá)式，這一節(jié)介紹能量效率和接觸探測(cè)概率之間的折中。本文只考慮在接觸探測(cè)過(guò)程中消耗的能量，并未考慮數(shù)據(jù)傳輸過(guò)程中消耗的能量。因此，這里定義能量消耗為E=1/T，也就是網(wǎng)絡(luò)中節(jié)點(diǎn)的探測(cè)率。如果網(wǎng)絡(luò)中節(jié)點(diǎn)的探測(cè)率越大，那么節(jié)點(diǎn)在接觸探測(cè)過(guò)程中消耗的能量就越多。因此，式(6)可以變化為

根據(jù)式(11)，當(dāng)能量消耗 E 趨近于無(wú)窮大時(shí)，可以得到接觸探測(cè)概率Pd(E)=1，也就是Pd(E)的最大值。當(dāng)能量消耗E=0時(shí)，可以得到接觸探測(cè)概率Pd(E)=0，也就是Pd(E)的最小值。

圖3給出了不同場(chǎng)景下能量效率和接觸探測(cè)概率之間的折中。圖3(a)給出了當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)速度 V 變化時(shí)，能量效率和接觸探測(cè)概率之間的折中，而圖3(b)則給出了當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的通信范圍r 變化時(shí)，能量效率和接觸探測(cè)概率之間的折中。從圖中可以看出，接觸探測(cè)概率隨著能量消耗的增加而增加。這個(gè)結(jié)果是合理的，因?yàn)楦嗟哪芰肯囊馕吨宇l繁的接觸探測(cè)，從而導(dǎo)致接觸探測(cè)概率的增加。但是，當(dāng)能量消耗增加到一定值的時(shí)候，接觸探測(cè)概率的增加率會(huì)大大地減小。例如，當(dāng)r=6 m,V=2 m/s時(shí)，接觸探測(cè)概率在能量消耗為 0.8時(shí)就將近達(dá)到最大值；當(dāng)r=6 m,V=6 m/s，接觸探測(cè)概率在能量消耗為2.5時(shí)將近達(dá)到最大值。因此，這些點(diǎn)就是接觸探測(cè)過(guò)程中能量效率和接觸探測(cè)概率之間的“好的折中點(diǎn)”。

圖2 不同場(chǎng)景下FTd(t)的近似值和精確值的比較

圖3 不同場(chǎng)景下能量效率和接觸探測(cè)概率之間的折中

4 模型驗(yàn)證

本文利用 MATLAB 作為仿真工具來(lái)驗(yàn)證提出的理論模型的正確性。實(shí)驗(yàn)采用一個(gè)有10個(gè)節(jié)點(diǎn)分布在面積為1000×1000 m2的場(chǎng)景。場(chǎng)景中的節(jié)點(diǎn)根據(jù)隨機(jī)路點(diǎn)模型移動(dòng)，并且有相同的通信范圍r。根據(jù)上面的假設(shè)，考慮網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都有相同的移動(dòng)速度V，并且移動(dòng)過(guò)程中的暫停時(shí)間為0。

圖4給出了不同場(chǎng)景下FTd(t)的仿真結(jié)果(Sim)和FTd(t)的近似值(App)以及精確值(Pre)的比較。從圖中可以看出，隨著探測(cè)間隔T的增加，相比FTd(t)的精確值，不同場(chǎng)景下FTd(t)的仿真結(jié)果更加接近于FTd(t)的近似值，特別是當(dāng)r=6 m, V=6 m/s 以及V=3 m/s?；谝陨系慕Y(jié)果，可以看出相比FTd(t)的精確值，本文給出的近似值更加接近FTd(t)的實(shí)際值。因此，本文可以用式(5)代替式(2)，來(lái)直接計(jì)算接觸探測(cè)概率。

圖5給出了不同場(chǎng)景下接觸探測(cè)概率Pd(T)的仿真結(jié)果(Sim)和理論結(jié)果(Theo)的比較。圖5(a)顯示了當(dāng)節(jié)點(diǎn)的移動(dòng)速度變化時(shí)，Pd(T)的仿真結(jié)果和理論結(jié)果的比較，圖5(b)顯示了當(dāng)節(jié)點(diǎn)的通信范圍變化時(shí)，Pd(T)的仿真結(jié)果和理論結(jié)果的比較。從圖中可以看出，隨著探測(cè)間隔T的增加，不僅當(dāng)節(jié)點(diǎn)的移動(dòng)速度變化時(shí)，而且當(dāng)節(jié)點(diǎn)的通信范圍變化時(shí)，接觸探測(cè)概率Pd(T)的仿真結(jié)果和理論結(jié)果都非常接近。

綜上所述，通過(guò)不同場(chǎng)景下的仿真實(shí)驗(yàn)可以看出，相比FTd(t)的精確值，F(xiàn)Td(t)的仿真結(jié)果更加接近于FTd(t)的近似值；接觸探測(cè)概率Pd(T)的仿真結(jié)果也非常接近于其理論結(jié)果，從而證明了本文提出的理論模型的正確性。

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

圖4 FTd(t)的理論結(jié)果和相應(yīng)的仿真結(jié)果的比較

圖5 不同場(chǎng)景下Pd(T)的理論結(jié)果和相應(yīng)的仿真結(jié)果的比較

本文研究了延遲容忍網(wǎng)絡(luò)中基于隨機(jī)路點(diǎn)模型的接觸探測(cè)過(guò)程的能量有效問(wèn)題。在給定隨機(jī)路點(diǎn)模型中接觸時(shí)長(zhǎng)分布的情況下，從理論上分別得到了接觸探測(cè)概率的表達(dá)式，并且也證明了在所有平均探測(cè)間隔相同并且不能提前知道節(jié)點(diǎn)的接觸過(guò)程的策略中，采用恒定探測(cè)間隔的策略是最優(yōu)的。其次，基于提出的理論模型，分析了不同情況下能量效率和接觸探測(cè)概率之間的折中。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所提出的模型的正確性。實(shí)驗(yàn)結(jié)果表明在不同場(chǎng)景下接觸探測(cè)概率的仿真結(jié)果和理論結(jié)果都非常接近，從而證明了提出模型的正確性。

[1] Wei Kai-min, Liang Xiao, and Xu Ke. A survey of social-aware routing protocols in delay tolerant networks: applications, taxonomy and design-related issues[J]. IEEE Communications Surveys and Tutorials, 2014, 16(1): 556-578.

[2] 吳亞輝, 鄧蘇, 黃宏斌. 延遲容忍網(wǎng)絡(luò)狀態(tài)感知的路由策略研究[J]. 電子與信息學(xué)報(bào), 2011, 33(3): 575-579.

Wu Ya-hui, Deng Su, and Huang Hong-bin. Research of situation-aware routing method in delay tolerant network [J]. Journal of Electronics & Information Technology, 2011, 33(3): 575-579.

[3] Zhou Huan, Chen Ji-ming, Fan Jia-lu, et al.. Consub: incentive-based content subscribing in selfish opportunistic mobile networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(9): 669-679.

[4] 張振京, 金志剛, 舒炎泰. 基于節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的社會(huì)性DTN高效路由[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(3): 626-635.

Zhang Zhen-jing, Jin Zhi-gang, and Shu Yan-tai. Efficient routing in social DTN based on nodes,movement prediction [J]. Journal of Computers, 2013, 36(3): 626-635.

[5] Zhou Huan, Chen Ji-ming, Zhao Hong-yang, et al.. On exploiting contact patterns for data forwarding in duty-cycle opportunistic mobile networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(9): 4629-4642.

[6] Drula C, Amza C, Rousseau F, et al.. Adaptive energy conserving algorithms for neighbor discovery in opportunistic bluetooth networks[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(1): 96-107.

[7] Wang, Wei, Srinivasan V, and Motani M. Adaptive contact probing mechanisms for delay tolerant applications[C]. Proceedings of the ACM MobiCom, Montreal, Canada, 2007: 230-241.

[8] Wang Wei, Srinivasan V, and Motani M. Opportunistic energy-efficient contact probing in delay-tolerant applications [J]. IEEE/ACM Transactions on Networking, 2009, 17(5): 1592-1605.

[9] Qin Shuang, Feng Gang, and Zhang Yi-de. How the contact-probing mechanism affects the transmission capacity of delay-tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(4): 1825-1834.

[10] Zhou Huan, Zheng Huan-yang, Wu Jie, et al.. Energyefficient contact probing in opportunistic mobile networks[C]. Proceedings of the IEEE ICCCN, Nassau, Bahamas, 2013: 1-7.

[11] 李文霽, 鄭康鋒, 張冬梅, 等. 一種高效的延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)異步探測(cè)機(jī)制[J]. 電子與信息學(xué)報(bào), 2012, 34(12): 2891-2897.

Li Wen-ji, Zheng Kang-feng, Zhang Dong-mei, et al.. An efficient asynchronous probing scheme for delay-tolerant mobility sensor network[J]. Journal of Electronics & Information Technology, 2012, 34(12): 2891-2897.

[12] Hess A, Hyyti? E, and Ott J. Efficient neighbor discovery in mobile opportunistic networking using mobility awareness[C]. Proceedings of COMSNETS, Bangalore, India, 2014: 1-8.

[13] Broch J, Maltz D, Johnson D, et al.. A performance comparison of multi-hop wireless ad hoc network routing protocols[C]. Proceedings of the ACM Mobicom, Dallas, USA, 1998: 85-97.

[14] McDonald B and Znati T. A path availability model for wireless Ad-hoc networks[C]. Proceedings of the IEEE WCNC, New Orleans, USA, 1999: 35-40.

[15] Eagle N, Pentland A, and Lazer D. Inferring social network structure using mobile phone data[J]. Proceedings of National Academy of Sciences, 2009, 106(36): 15274-15278.

[16] Tsao Cheng-lin, Liao Wan-jiun, and Kuo Jia-chun. Link duration of the random way point model in mobile Ad hoc networks[C]. Proceedings of the IEEE WCNC, Las Vegas, USA, 2006: 367-371.

[17] Wu Yueh-ting, Liao Wan-jiun, Tsao Cheng-lin, et al.. Impact of node mobility on link duration in multihop mobile networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(5): 2435-2442.

[18] Abdulla M and Simon R. The impact of intercontact time within opportunistic networks: protocol implications and mobility models[R]. TechRepublic White Paper, 2009.

[19] Spyropoulos T, Psounis K, and Raghavendra C. Performance analysis of mobility-assisted routing[C]. Proceedings of the ACM Mobihoc, Los Angeles, USA, 2006: 49-60.

周 歡： 男，1986年生，博士，講師，研究方向?yàn)檠舆t容忍網(wǎng)絡(luò)、移動(dòng)社交網(wǎng)絡(luò)和物聯(lián)網(wǎng)技術(shù).

任 東： 男，1976年生，博士，副教授，研究方向?yàn)槟Ｊ阶R(shí)別、圖像處理和物聯(lián)網(wǎng)技術(shù).

徐守志： 男，1969年生，博士，教授，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)和車輛自組網(wǎng).

Research on Energy-efficient Contact Probing in Delay Tolerant Networks

Zhou Huan Ren Dong Xu Shou-zhi Jiang Ting-yao Huang Zhi-yong
(Hubei Key Laboratory of Intelligent Vision Based Monitoring for Hydroelectric Engineering, Yichang 443002, China)
(College of Computer and Information Technology, China Three Gorges University, Yichang 443002, China)

In the Delay Tolerant Networks (DTNs), in order to discover the neighbors, the nodes in the network have to probe the surrounding environment continually. This can be an extremely energy-consuming process. If the nodes probe very frequently, they consume a lot of energy, and may be energy inefficient. On the other hand, infrequent contact probing might cause loss of many contacts, and thus missing the opportunities to exchange data. Therefore, there exists a trade-off between the energy efficiency and contact opportunities in the DTNs. In order to investigate this trade-off, this study first proposes a model to quantify the contact detecting probability when the contact probing interval is constant based on the Random Way-Point (RWP) model. Moreover, this study also demonstrates that the strategy which probes at a constant interval performs the best performance, among all contact probing strategies with the same average contact probing interval. Then, based on the proposed model, this study analyzes the trade-off between the energy efficiency and contact detecting probability under different situations. Finally, extensive simulations are conducted to validate the correctness of the proposed model.

Delay Tolerant Networks (DTNs); Energy efficiency; Contact probing; Random Way-Point (RWP) model

TP393.04

： A

：1009-5896(2015)06-1285-06

10.11999/JEIT140995

2014-07-25收到，2014-12-11改回

國(guó)家自然科學(xué)基金(61174177, 41172298)，國(guó)家863計(jì)劃項(xiàng)目(2013AA10230207)，湖北省自然科學(xué)基金(2014CFB145)，湖北省水電工程智能視覺(jué)監(jiān)測(cè)重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(2014KLA07)和三峽大學(xué)人才科研啟動(dòng)基金(KJ2014B056, KJ2014B060)資助課題

*通信作者：徐守志 xsz@ctgu.edu.cn