延迟容忍网络中接触探测过程建模研究

周欢，童林萍，任东，徐守志，蒋廷耀

三峡大学计算机与信息学院，湖北宜昌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