周歡，童林萍，任東，徐守志，蔣廷耀

三峽大學計算機與信息學院，湖北宜昌443002

延遲容忍網(wǎng)絡(luò)中接觸探測過程建模研究

周歡，童林萍，任東，徐守志，蔣廷耀

三峽大學計算機與信息學院，湖北宜昌443002

延遲容忍網(wǎng)絡(luò)中的接觸探測過程極其耗費能量。為了研究能量消耗對延遲容忍網(wǎng)絡(luò)中接觸探測過程的影響，首先對基于真實的移動軌跡的接觸探測過程進行了建模，分別得到了恒定探測間隔下單點接觸探測概率和雙點接觸探測概率的表達式。基于得到的理論模型，分別從單點接觸探測過程和雙點接觸探測過程出發(fā)，分析了不同場景下能量消耗對接觸探測過程的影響。通過真實移動數(shù)據(jù)集驅(qū)動的仿真實驗驗證提出的理論模型的正確性。

延遲容忍網(wǎng)絡(luò)；能量消耗；接觸探測；真實移動數(shù)據(jù)集

1　引言

近年來，隨著裝備有Wi-Fi接口或者藍牙接口的無線便攜設(shè)備（如：ipad，PDAs，智能手機等）的普及和流行，基于延遲容忍網(wǎng)絡(luò)（Delay Tolerant Networks，簡稱為DTNs）方面的應(yīng)用得到了蓬勃的發(fā)展［1-2］。延遲容忍網(wǎng)絡(luò)又稱為間歇性連通網(wǎng)（Intermittently Connected Networks，ICNs），稀疏網(wǎng)絡(luò)（Sparse Networks），或機會移動網(wǎng)絡(luò)（Opportunistic Mobile Networks，OppNets），是無線網(wǎng)絡(luò)中一個新興的研究熱點［3-8］。

延遲容忍網(wǎng)絡(luò)泛指由于節(jié)點的稀疏分布、快速移動和無線通信技術(shù)的限制等原因造成的源節(jié)點和目的節(jié)點之間不存在完整的端到端連接的一類特殊的移動自組織網(wǎng)。在延遲容忍網(wǎng)絡(luò)中，為了實現(xiàn)節(jié)點之間的數(shù)據(jù)傳輸，網(wǎng)絡(luò)中的節(jié)點必須不斷地探測周圍的環(huán)境，從而發(fā)現(xiàn)在其通信范圍內(nèi)的鄰居節(jié)點。顯而易見，這個接觸探測過程會消耗大量能量［9］。再者，延遲容忍網(wǎng)絡(luò)是一個接觸很稀疏的網(wǎng)絡(luò)，這就意味著如果網(wǎng)絡(luò)中的節(jié)點探測周圍的環(huán)境太頻繁的話，會浪費很多的能量。因此，如何提高接觸探測過程中能量的使用效率是一個很緊迫的問題。

目前，已經(jīng)有很多學者對接觸探測過程中的能量消耗進行了研究［10-15］。文獻［10］提出了兩種新穎的自適應(yīng)工作機制來動態(tài)地為延遲容忍網(wǎng)絡(luò)中的接觸探測過程選擇合適的參數(shù)。一種是低功率無線電，它采用一種慢發(fā)現(xiàn)模式去發(fā)現(xiàn)接觸和傳輸數(shù)據(jù)；另一種是高功率無線電，它根據(jù)節(jié)點的移動情況采用一種快的發(fā)現(xiàn)模式發(fā)現(xiàn)接觸和傳輸數(shù)據(jù)。實驗結(jié)果表明文中提出的自適應(yīng)算法要比靜態(tài)的能量保持算法消耗的能量減少50%，但是相應(yīng)的網(wǎng)絡(luò)性能卻能提高8%。文獻［11-12］從理論上研究了延遲容忍網(wǎng)絡(luò)中探測間隔對于錯失一次接觸的概率的影響，并且研究了接觸錯失概率和能量消耗之間的折衷。再者，通過分析真實移動數(shù)據(jù)集中節(jié)點間的接觸規(guī)律，提出了一種自適應(yīng)的接觸探測機制，叫做“STAR”?；谡鎸嵰苿訑?shù)據(jù)集的實驗結(jié)果表明，“STAR”要比采用恒定的接觸探測間隔的策略消耗的能量少三倍。文獻［13-14］提出了一種理論模型去研究接觸探測對于鏈路時長的影響，并且研究了能量消耗和吞吐量之間的折衷。除此之外，該文也提供了一個用于在能量有限情況下計算最優(yōu)接觸探測頻率的框架，其中每個節(jié)點都根據(jù)節(jié)點相遇率去自適應(yīng)地調(diào)整接觸探測頻率。文獻［15］對基于隨機路點模型（Random Way-Point model）的接觸探測過程進行了建模，并且分析了不同情況下能量效率和有效接觸總數(shù)之間的折衷。

和現(xiàn)有工作不同，本文的工作側(cè)重于從理論上對基于真實的移動軌跡的接觸探測過程進行研究，并且提出了一種理論模型去研究真實場景下能量消耗對接觸探測過程的影響。本文工作的創(chuàng)新點和主要貢獻如下：

（1）基于真實的移動軌跡，提出了一種研究延遲容忍網(wǎng)絡(luò)中接觸探測過程的理論模型。給出真實移動數(shù)據(jù)集中接觸時長分布的情況下，從理論上得到了單點接觸探測概率和雙點接觸探測概率的表達式。

（2）基于得到的理論模型，分別從單點接觸探測過程和雙點接觸探測過程出發(fā)，分析了不同場景下能量消耗對接觸探測過程的影響。

（3）通過真實移動數(shù)據(jù)集驅(qū)動的仿真實驗驗證提出的理論模型的正確性。結(jié)果表明，不同場景下的仿真實驗結(jié)果和理論結(jié)果都很接近，從而證明了提出的理論模型的正確性。

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

延遲容忍網(wǎng)絡(luò)中有多種移動模型，包括隨機路點模型（Random Way-Point Model）、隨機漫步模型（Random Walk Model）和真實的移動軌跡（Realistic Mobility Trace）。本文對基于真實的移動軌跡的接觸探測過程進行研究。

在延遲容忍網(wǎng)絡(luò)中，節(jié)點之間處于接觸狀態(tài)當且僅當它們在彼此的通信范圍內(nèi)。節(jié)點之間不間斷地接觸的時間長度定義為接觸時長，同時連續(xù)的接觸之間的間隔時間被定義為接觸時間間隔。假設(shè)接觸時長Td是獨立同分布的（Independent and Identically Distributed）的隨機變量，其累計分布函數(shù)（Cumulative Distribution Function）為FTd（t）。圖1給出了某一個節(jié)點和其他節(jié)點之間的接觸時長Td和接觸時間間隔Tc的例子。

圖1　恒定探測間隔T下某一個節(jié)點的接觸探測過程示例

為了實現(xiàn)上面的鄰居發(fā)現(xiàn)過程，網(wǎng)絡(luò)中的節(jié)點必須不斷地探測周圍的環(huán)境發(fā)現(xiàn)在其附近的其他節(jié)點。延遲容忍網(wǎng)絡(luò)中兩個節(jié)點是接觸的當且僅當兩個節(jié)點在彼此的通信范圍內(nèi)。但是，如果兩個節(jié)點在接觸過程中都沒有探測的話，也會錯失彼此的接觸。因此，這里將接觸探測過程中的接觸分為兩類：有效的接觸和錯失的接觸。有效的接觸發(fā)生時當且僅當在兩個節(jié)點的接觸探測過程中，至少有一個節(jié)點探測了其周圍的環(huán)境。這類接觸可以被彼此發(fā)現(xiàn)，且可以被用于延遲容忍網(wǎng)絡(luò)中的不同應(yīng)用。錯失的接觸發(fā)生時當且僅當在兩個節(jié)點的接觸探測過程中，兩個節(jié)點都沒有探測其周圍的環(huán)境。由于此類接觸不能被彼此發(fā)現(xiàn)，因此定義此類接觸為錯失的接觸。由于延遲容忍網(wǎng)絡(luò)中的接觸一般是很稀疏的，并且接觸探測過程對延遲容忍網(wǎng)絡(luò)中的各種應(yīng)用都有很大的影響，因此下面會對延遲容忍網(wǎng)絡(luò)中的接觸探測過程進行建模。

3　接觸探測過程建模

這一部分考慮從理論上對延遲容忍網(wǎng)絡(luò)中的接觸探測過程進行研究，并且分析不同場景下能量消耗對接觸探測過程的影響。

3.1單點接觸探測概率

為了從理論上對延遲容忍網(wǎng)絡(luò)中的接觸探測過程進行研究，首先考慮從理論上得到單點接觸探測概率的表達式。這里定義單點接觸探測概率Pd為兩個節(jié)點之間的接觸被其中某一個節(jié)點探測到的概率。為了方便下面的分析，假設(shè)對于節(jié)點A，一個和節(jié)點B之間的接觸能夠被探測到（也就是有效的接觸），當且僅當和節(jié)點B之間的接觸被節(jié)點A探測到，否則這次接觸就被錯失。如圖1所示，設(shè)定節(jié)點A以恒定的間隔T探測，那么對于節(jié)點A來說，接觸2和接觸3是有效的接觸，而接觸1則為錯失的接觸。為了計算單點接觸探測概率Pd，需要考慮多個參數(shù)，包括探測的間隔T和接觸時長Td等。值得注意的是，當Td≥T的時候，兩個節(jié)點之間的接觸都能被探測到。因此，有如下的定理：

定理1對于以恒定的間T探測的節(jié)點A來說，單點接觸探測概率Pd（T）可以表示為：

證明：假設(shè)節(jié)點A在時間點｛T，2T，…｝探測其周圍的環(huán)境；這里只考慮在時間范圍［0，T］內(nèi)去計算單點接觸探測概率。一次接觸能夠被節(jié)點A探測到，當且僅當（1）和節(jié)點A的接觸剛好發(fā)生在節(jié)點A在時間T要探測周圍的環(huán)境時；（2）和節(jié)點A的接觸發(fā)生在［0，T）的時間范圍內(nèi)，但是它們的接觸時長足夠長，從而可以保證節(jié)點A在時間T要探測周圍的環(huán)境時，它們?nèi)匀惶幱诮佑|的狀態(tài)。因此，單點接觸探測概率是上面兩個部分之和，也可以表示為式（1）。證畢。

根據(jù)式（1），如果節(jié)點之間的接觸時長Td服從一個給定的分布，就可以從理論上得到單點接觸探測概率Pd（T）的表達式。文獻［7］發(fā)現(xiàn)真實移動數(shù)據(jù)集中節(jié)點的累計接觸時長服從冪律分布（Pareto distribution或者power law distribution）。因此，本文也假設(shè)接觸時長Td服從冪律分布。

當接觸時長Td服從冪律分布時，可以得到其累計分布函數(shù)（）t為：

將式（2）代入式（1）中，可以得到單點接觸探測概率Pd（T）的表達式為：

3.2雙點探測概率

上面的部分給出了單點接觸探測概率的表達式，也就是一次節(jié)點A和節(jié)點B之間的接觸能夠被節(jié)點A探測到的概率。這個部分研究雙點接觸探測過程，也就是兩個節(jié)點A和B之間的接觸能夠被其中任意一個節(jié)點探測到的概率。在雙點接觸探測過程中，每個節(jié)點都以恒定的間隔T進行探測；同時設(shè)定節(jié)點A在時間點T，2T，…，nT探測，節(jié)點B在時間點y，y+T，…，y+（n-1）T探測。從圖中可以看出，接觸2和接觸3被節(jié)點A探測到，接觸1則被節(jié)點B探測到?？紤]節(jié)點A和B以恒定的間隔T獨立地和周期性地探測周圍的環(huán)境。然后，可以得出兩個節(jié)點的接觸可以被其中任意一個節(jié)點探測到的概率為：

因為兩個節(jié)點的探測是獨立的，所以y就均勻地分布在［0，T］的范圍內(nèi)。然后，就可以得到雙點接觸探測概率Pdd（T）的表達式為：

將式（2）代入式（5）中，可以得到雙點接觸探測概率Pdd（T）的表達式為：

得到單點接觸探測概率和雙點接觸探測概率的表達式后，這個部分用數(shù)值結(jié)果來分析能量消耗和單點接觸探測概率以及雙點接觸探測概率之間的關(guān)系。這里能量消耗定義為，代表網(wǎng)絡(luò)中節(jié)點的探測率。如果網(wǎng)絡(luò)中節(jié)點的探測率越大，那么節(jié)點會消耗越多的能量在接觸探測過程中。圖2給出了不同場景下能量消耗和單點接觸探測概率Pd（T）以及雙點接觸探測概率Pdd（T）的關(guān)系。從圖中可以看出，單點接觸探測概率Pd（T）和雙點接觸探測概率Pdd（T）均隨著能量消耗的增加而增加，這就意味著網(wǎng)絡(luò)中的節(jié)點必須消耗更多的能量去增加網(wǎng)絡(luò)的性能。當能量消耗大于時，單點接觸探測概率Pd（T）和雙點接觸探測概率Pdd（T）都為100%。從圖中也可以看出，在不同場景下的雙點探測概率Pdd（T）都比單點探測概率Pd（T）大。這個結(jié)果是合理的，因為在雙點接觸探測過程中，兩個節(jié)點之間的接觸只需要被其中任意一個節(jié)點探測到。相反，在單點接觸探測過程中，如果一個節(jié)點錯失了和另外一個節(jié)點的接觸，那么這個節(jié)點就錯失了這次接觸。從圖2（a）可以看出，單點接觸探測概率Pd（T）以及雙點接觸探測概率Pdd（T）均隨著u的增加而增加，這就意味著更大的u需要較少的能量消耗去達到一個特定的值。從圖2（b）可以看出，單點接觸探測概率Pd（T）以及雙點接觸探測概率Pdd（T）均隨著k的增加而減少，這就意味著更大的k需要更多的能量消耗去達到一個特定的值。

圖2　不同場景下能量消耗和單點接觸探測概率Pd（T）以及雙點接觸探測概率Pdd（T）的關(guān)系

下面給出這一部分的總結(jié)：從理論上得到了單點接觸探測概率和雙點接觸探測概率的表達式，并且用數(shù)值結(jié)果分析了能量消耗和接觸發(fā)現(xiàn)概率之間的關(guān)系。從圖示結(jié)果可以看出，單點接觸探測概率和雙點接觸探測概率均隨著能量消耗的增加而增加，并且當能量消耗大于時，單點接觸探測概率和雙點接觸探測概率都為100%。再者，單點接觸探測概率和雙點接觸探測概率均隨著u的增加而增加，隨著k的減小而增加。從這里可以得出接觸時長對單點接觸探測概率和雙點接觸探測概率有著很大的影響。

4　基于實際數(shù)據(jù)集的模型驗證

本章利用從真實環(huán)境中采集到的真實移動數(shù)據(jù)集Nus Bluetooth去驗證提出的理論模型的正確性。Nus Bluetooth是由9個持有iMotes設(shè)備的志愿者收集的當一個設(shè)備發(fā)現(xiàn)其他的設(shè)備時，它會記錄接觸時間以及設(shè)備的ID［11］。利用這些記錄的信息，就可以得到任意兩個設(shè)備之間的接觸時長。如果一個設(shè)備在第m次連續(xù)的掃描被發(fā)現(xiàn)，那么這次的接觸時長就是第m次掃描和第一次掃描之間的時間差。如果一個設(shè)備只被掃描到一次，和文獻［7］中的方法類似，這里就把這次的接觸近似為60秒。下一步研究在真實移動數(shù)據(jù)集Nus Bluetooth中的累積接觸時長。圖3以對數(shù)刻度的形式畫出了Nus Bluetooth數(shù)據(jù)集中1-FTd（x）的曲線。從圖中可以看出，累計接觸時長服從冪律分布。通過曲線擬合，可以估計出FTd（x）=1-（x/u）-k中u=30 s和k=0.886 3。

圖3　Nus Bluetooth數(shù)據(jù)集中的累計接觸時長分布

下面利用上面介紹的真實移動數(shù)據(jù)集驗證提出的理論模型的正確性。圖4給出了單點接觸探測概率和雙點接觸探測概率的仿真結(jié)果和理論結(jié)果的比較。從圖中可以看出，隨著能量消耗的增加，單點接觸探測概率和雙點接觸探測概率的仿真結(jié)果和理論結(jié)果都非常接近。

圖4　仿真結(jié)果和理論結(jié)果的比較

綜上所述，通過真實移動數(shù)據(jù)集驅(qū)動的仿真實驗可以看出，單點接觸探測概率和雙點接觸探測概率的仿真結(jié)果都非常接近于其理論結(jié)果，從而證明了本文提出的理論模型的正確性。

5　結(jié)論

本文研究了基于真實的移動軌跡的接觸探測過程，并且提出了一種理論模型去研究不同場景下能量消耗對接觸探測過程的影響。給定真實移動數(shù)據(jù)集中接觸時長分布的情況下，本文首先從理論上得到了單點接觸探測概率和雙點探測概率的表達式。其次，基于得到的理論模型，分別從單點接觸探測過程和雙點接觸探測過程出發(fā)，分析了不同場景下能量消耗對接觸探測過程的影響。最后，通過真實移動數(shù)據(jù)集驅(qū)動的仿真實驗驗證提出的理論模型的正確性。實驗結(jié)果表明，不同場景下的仿真實驗結(jié)果和理論結(jié)果都很接近，從而證明了提出的理論模型的正確性。

［1］肖明軍，黃劉生.容遲網(wǎng)絡(luò)路由算法［J］.計算機研究與發(fā)展，2009，46（7）：1065-1073.

［2］張振京，金志剛，舒炎泰.基于節(jié)點運動預(yù)測的社會性DTN高效路由［J］.計算機學報，2013，36（3）：626-635.

［3］Zhou H，Chen J，F(xiàn)an J，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］Zhou H，Chen J，Zhao H，et al.On exploiting contact patternsfordataforwardinginduty-cycleopportunistic mobile networks［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4629-4642.

［5］宋蔓蔓，張振宇，楊文忠，等.一種機會網(wǎng)絡(luò)節(jié)點重復(fù)博弈模型［J］.計算機工程與應(yīng)用，2014，50（16）：86-89.

［6］Zhang Z.Routing in intermittently connected mobile ad hoc networks and delay tolerant networks：overview and challenges［J］.IEEE Communications Surveys and Tutorials，2006，8（1）：24-37.

［7］Li F，Wu J.MOPS：Providing content-based service in disruption tolerant networks［C］//Proc of ICDCS，Montreal，IEEE，2009：526-533.

［8］Cao Y，Sun Z.Routing in delay/disruption tolerant networks： A taxonomy，survey and challenges［J］.IEEE Communications Surveys and Tutorials，2013，15（2）：654-677.

［9］Stemm M，Katz R H.Measuring and reducing energy consumption of network interfaces in hand-held devices［J］. IEICE Transactions on Communications，1997，80（8）：1125-1131.

［10］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.

［11］Wang W，Srinivasan V，Motani M.Adaptive Contact Probing Mechanisms for Delay Tolerant Applications［C］//Proc of MobiCom，Montreal，ACM，2007：230-241.

［12］Wang W，Srinivasan V，Motani M.Opportunistic energyefficient contact probing in delay-tolerant applications［J］. IEEE/ACM Transactions on Networking，2009，17（5）：1592-1605.

［13］Qin S，F(xiàn)eng G，Zhang Y.How contact probing affects the transmission capacity and energy consumption in DTNs［C］// Proc of IEEE ICC，Kyoto，IEEE，2011.

［14］Qin S，F(xiàn)eng G，Zhang Y.How the contact-probing mechanism affects the transmission capacity of delay-tolerant networks［J］.IEEE Transactions on Vehicular Technology，2011，60（4）：1825-1834.

［15］Zhou H，Zheng H，Wu J，et al.Energy-efficient contact probinginopportunisticmobilenetworks［C］//Procof ICCCN，Nassau，IEEE，2013：1-7.

［16］Vikram S，Anirudh N，Mehul M.CRAWDAD data set nus/bluetooth（v.2007-09-03）［EB/OL］.［2007-09-03］.http：// crawdad.cs.dartmouth.edu/nus/blue tooth.

Research on modeling of contact probing process in delay tolerant networks.

ZHOU Huan，TONG Linping，REN Dong，XU Shouzhi，JIANG Tingyao

College of Computer and Information Technology，China Three Gorges University，Yichang，Hubei 443002，China

Contact probing process is an extremely energy-consuming process in Delay Tolerant Networks（DTNs）.In order to investigate the impact of energy consuming on the contact probing process in DTNs，the contact probing process based on the real mobility trace is modeled，and the single contact probing probability and the double contact probing probability are obtained when the contact probing interval is constant，respectively.Then，based on the proposed model，it is analyzed that the impact of energy consuming on the contact probing process under different situations.Finally，extensive real trace-driven simulations are conducted to validate the correctness of the proposed model.

delay tolerant networks；energy consuming；contact probing；real mobility trace

A

TP393.04

10.3778/j.issn.1002-8331.1503-0335

國家自然科學基金（No.61174177，No.41172298）；湖北省自然科學基金資助項目（No.2014CFB145）；湖北省水電工程智能視覺監(jiān)測重點實驗室開放基金（No.2014KLA07）。

周歡（1986—），男，博士，講師，研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)，延遲容忍網(wǎng)絡(luò)等；童林萍（1991—），女，在讀研究生，研究領(lǐng)域為延遲容忍網(wǎng)絡(luò)；任東（1976—），男，博士，副教授，研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)；徐守志（1969—），通訊作者，男，博士，教授，研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)；蔣廷耀（1969—），男，博士，教授，研究領(lǐng)域為移動自組織網(wǎng)絡(luò)。E-mail：xsz@ctgu.edu.cn

2015-03-26

2015-06-12

1002-8331（2015）22-0104-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-07-14，http://www.cnki.net/kcms/detail/11.2127.TP.20150714.1617.006.html