延遲容忍網絡中接觸探測過程建模研究

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

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

延遲容忍網絡中接觸探測過程建模研究

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

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

延遲容忍網絡中的接觸探測過程極其耗費能量。為了研究能量消耗對延遲容忍網絡中接觸探測過程的影響，首先對基于真實的移動軌跡的接觸探測過程進行了建模，分別得到了恒定探測間隔下單點接觸探測概率和雙點接觸探測概率的表達式?；诘玫降睦碚撃Ｐ?，分別從單點接觸探測過程和雙點接觸探測過程出發，分析了不同場景下能量消耗對接觸探測過程的影響。通過真實移動數據集驅動的仿真實驗驗證提出的理論模型的正確性。

延遲容忍網絡；能量消耗；接觸探測；真實移動數據集

1　引言

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

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

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

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

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

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

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

2　網絡模型

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

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

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

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

3　接觸探測過程建模

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

3.1單點接觸探測概率

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

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

證明：假設節點A在時間點｛T，2T，…｝探測其周圍的環境；這里只考慮在時間范圍［0，T］內去計算單點接觸探測概率。一次接觸能夠被節點A探測到，當且僅當（1）和節點A的接觸剛好發生在節點A在時間T要探測周圍的環境時；（2）和節點A的接觸發生在［0，T）的時間范圍內，但是它們的接觸時長足夠長，從而可以保證節點A在時間T要探測周圍的環境時，它們仍然處于接觸的狀態。因此，單點接觸探測概率是上面兩個部分之和，也可以表示為式（1）。證畢。

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

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

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

3.2雙點探測概率

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

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

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

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

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

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

4　基于實際數據集的模型驗證

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

圖3　Nus Bluetooth數據集中的累計接觸時長分布

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

圖4　仿真結果和理論結果的比較

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

5　結論

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

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

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

［3］Zhou H，Chen J，Fan 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］宋蔓蔓，張振宇，楊文忠，等.一種機會網絡節點重復博弈模型［J］.計算機工程與應用，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，Feng 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，Feng 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）；湖北省水電工程智能視覺監測重點實驗室開放基金（No.2014KLA07）。

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

2015-03-26

2015-06-12

1002-8331（2015）22-0104-05

CNKI網絡優先出版：2015-07-14，http://www.cnki.net/kcms/detail/11.2127.TP.20150714.1617.006.html