延迟容忍网络中能量有效的接触探测研究

周 欢 任 东 徐守志蒋廷耀 黄志勇

(三峡大学湖北省水电工程智能视觉监测重点实验室 宜昌 443002)

(三峡大学计算机与信息学院 宜昌 443002)

延迟容忍网络中能量有效的接触探测研究

周 欢 任 东 徐守志*蒋廷耀 黄志勇

(三峡大学湖北省水电工程智能视觉监测重点实验室 宜昌 443002)

(三峡大学计算机与信息学院 宜昌 443002)

在延迟容忍网络中，为了发现在其通信范围内的邻居节点，网络中的节点必须不断地探测周围的环境。这个接触探测过程极其耗费能量。如果网络中的节点探测太过频繁，会耗费很多能量，且使得网络能量的使用效率降低。另一方面，稀疏的探测可能导致节点失去和其它节点的接触，从而错失交换数据的机会。因此，在延迟容忍网络中能量效率和接触机会之间存在着一种折中的关系。为了研究这种折中关系，该文首先对基于随机路点模型(Random Way-Point model, RWP)的接触探测过程进行建模，得到恒定探测间隔下接触探测概率的表达式，并且证明在所有平均探测间隔相同的策略中，以恒定间隔探测的策略是最优的。其次，基于提出的理论模型，分析不同情况下能量效率和接触探测概率之间的折中。最后，通过仿真实验验证该理论模型的正确性。

延迟容忍网络；能量效率；接触探测；随机路点模型

1 引言

近年来，随着装备有Wi-Fi 接口或者蓝牙接口的无线便携设备(如：Ipad, PDAs，智能手机等)的普及和流行，基于延迟容忍网络(Delay Tolerant Networks, DTNs)方面的应用得到了蓬勃的发展[1]。延迟容忍网络又称为间歇性连通网(Intermittently Connected Networks, ICNs)，稀疏网络(SparseNetworks)，或机会移动网络(Opportunistic Mobile Networks, OppNets)，是无线网络中一个新兴的研究热点[2−5]。延迟容忍网络目前还没有统一的定义，泛指由于节点的稀疏分布、快速移动和无线通信技术的限制等原因造成的源节点和目的节点之间不存在完整的端到端连接的一类特殊的移动自组织网。

在延迟容忍网络中，为了实现节点之间的数据传输，网络中的节点必须不断地探测周围的环境，从而发现在其通信范围内的邻居节点。显而易见，这个接触探测过程会消耗大量能量。一些研究者在诺基亚6600手机上做了一个实验检测接触探测过程中消耗的能量，结果表明手机做一次接触探测所需要的能量和打一次电话所需要的能量几乎相等[6]。再者，延迟容忍网络是一个接触很稀疏的网络，节点的接触时间间隔远远大于节点的接触时长；这就意味着如果网络中的节点探测周围的环境太频繁，会浪费很多的能量。因此，研究如何提高接触探测过程中能量的使用效率是一个很紧迫的问题。

目前，已经有很多研究者对接触探测过程中的能量有效问题进行了研究[6−12]。文献[6]给出了两种新颖的自适应工作机制来动态地为接触探测过程选择合适的参数。网络中的节点在两个无线电之间进行切换：一种是低功率无线电，它采用一种慢发现模式去发现接触和传输数据；另一种是高功率无线电，它根据节点的移动情况采用一种快的发现模式发现接触和传输数据。实验结果表明文中提出的自适应算法要比静态的能量保持算法消耗的能量减少50%，但是相应的网络性能却能提高8%。文献[7, 8]研究了延迟容忍网络中探测间隔对于错失一次接触的概率的影响，并且研究了接触错失概率和能量消耗之间的折中。再者，通过分析真实移动数据集中节点间的接触规律，文中提出一种自适应的接触探测机制。基于真实移动数据集的实验结果表明文中提出的自适应的接触探测机制要比采用恒定的接触探测间隔的策略消耗的能量少3倍。文献[9]提出一种理论模型研究接触探测对于链路时长的影响，以及能量消耗和吞吐量之间的折中。除此之外，该文也提供一个用于在能量有限情况下计算最优接触探测频率的框架，其中每个节点都根据节点相遇率去自适应地调整接触探测频率。针对延迟容忍移动传感器网络(Delay Tolerant Mobility Sensor Network, DTMSN)节点间连接探测开销大、错失率高的问题，文献[11]提出一种高效的DTMSN异步探测机制。文献[12]提出一种简单的自适应的接触探测机制去节省探测过程中消耗的能量，和文献[7,8]不同，该机制需要通过GPS设备获取节点的移动速度，并且只允许节点在静止或者低速移动过程中发送探测包。

和现有工作不同，本文的工作侧重于对基于随机路点模型的接触探测过程进行研究，并且提出一种理论模型去研究接触探测过程中的能量有效问题。本文工作的创新点和主要贡献为：(1)基于随机路点模型，提出一种研究延迟网络中接触探测过程的理论模型。给出随机路点模型中接触时长分布的情况下，从理论上得到接触探测概率的表达式，并且证明在所有平均探测间隔相同的策略中，以恒定间隔探测的策略是最优的。(2)基于该理论模型，得到接触探测概率和能量消耗之间的关系，并分析不同场景下的能量效率和接触探测概率之间的折中。(3)通过仿真实验验证提出的理论模型的正确性。结果表明，不同场景下的仿真实验结果和理论结果都很接近，从而证明提出的理论模型的正确性。

2 网络模型

这一节介绍延迟容忍网络中和接触探测过程相关的网络模型。延迟容忍网络中有多种移动模型，包括随机路点模型[13]、随机漫步模型(Random walk model)[14]和真实的移动轨迹(Realistic mobility trace)[15]。本文集中对基于随机路点模型的接触探测过程进行研究。在随机路点模型中，考虑一种2维的正方形场景，面积为S，长和宽都为s。在移动模型中，每个节点会以相同的概率从Vmin, Vmax中选择一个移动速度V，然后以速度V向一个选定的目标位置移动。一旦到达目标位置，节点会暂停一段时间，然后再选择另外一个速度向另一个目标位置移动。以这种方式一直重复以上的过程。为了方便建模，假设网络中总共有N个节点，节点的移动速度V，节点的暂停时间相同并且为0。

在延迟容忍网络中，节点之间处于接触状态当且仅当它们在彼此的通信范围内。节点之间不间断地接触的时间长度定义为接触时长，同时连续的接触之间的间隔时间被定义为接触时间间隔。假设接触时长Td是独立同分布的随机变量，其累计分布函数为FTd(t)。图1给出了一个关于两个节点之间的接触时长Td和接触时间间隔Tc的例子。为了方便分析，同时假设每次探测需要的能量是相同的，这样节点的能量消耗率就可以转化为平均的接触探测频率。

为了实现上面的数据交换过程，网络中的节点必须不断地探测周围的环境去发现在其附近的其它节点。假设网络中总共有 N 个节点。这些节点由一些具有蓝牙接口的便携设备组成，且有相同的通信距离 r。因为便携设备中蓝牙的通信距离一般小于10 m，所以本文也假设通信距离r≤10m。延迟容忍网络中两个节点是接触的当且仅当两个节点在彼此的通信范围内。但是，如果两个节点在接触过程中都没有探测的话，也会错失彼此之间的接触。因此，下面会对延迟容忍网络中的接触探测过程进行建模。

图1 恒定探测间隔T下两个节点之间的接触探测过程示例

3 接触检测过程建模

这一节首先从理论上得到当节点的探测间隔为恒定值时的接触探测概率的表达式，然后从理论上证明在所有平均接触探测间隔相同并且节点的接触过程未知的策略中，采用恒定探测间隔的策略是最优的。

3.1 接触探测概率

这里定义接触探测概率 Pd为两个节点之间的接触被其中某一个节点探测到的概率。为了方便下面的分析，假设对于节点A，一个和节点B之间的接触能够被探测到(也就是有效的接触)，当且仅当和节点B之间的接触被节点A探测到，否则这次接触就被错失。如图1所示，设定节点A以恒定的间隔T探测，那么对于节点A来说，接触2和接触3是有效的接触，而接触1则为错失的接触。首先考虑网络中的节点以恒定的间隔T探测(如图1所示)，下面的部分会分析平均探测间隔相同的接触探测策略。为了计算接触探测概率 Pd，需要考虑多个参数，包括探测的间隔T和接触时长 Td等。值得注意的是，当Td≥T的时候，两个节点之间的接触都能被探测到。因此，有如下的定理：

定理1 对于以恒定的间隔T探测的节点A来说，接触探测概率可以表示为

证明 假设节点A在时间点{T, 2T,…}探测其周围的环境。为了方便建模，这里先考虑在时间范围[0,T]内去计算接触探测概率。用随机变量t代表在时间范围[0,T]内和节点A的某一次接触发生的时间。文献[5]声明“延迟容忍网络是一种很稀疏的网络，因而节点间的接触时间间隔要远大于探测间隔T”。基于这个声明，可以得出t是均匀地分布在[0,T]的范围内，那么这一次接触能够被节点A检测到，如果(1)与节点A的接触时间t刚好发生在节点A在时间T要探测周围的环境时；(2)与节点A的接触时间t发生在[0,T)的时间范围内，但是它们的接触时长足够长，可以保证节点A在时间T要探测周围的环境时，它们仍然处于接触的状态。因此，接触探测概率是上面两个部分之和，也可以表示为式(1)。因为在时间范围(T,2T],(2T,3T],…内的接触探测过程和[0,T]范围内的接触探测过程类似，所以接触探测概率可以表示为式(1)。 证毕

如果节点之间的接触时长Td服从一个给定的分布，就可以从理论上得到能量消耗和Pd(T)之间关系。文献[16, 17]显示随机路点模型中的Td是独立同分布的变量，其累计分布函数FTd(t)可以表示为

其中r是节点的通信范围，V是节点的移动速度。根据式(2)可以看出，FTd(t)不能积分。为了方便下面的建模，考虑将式(2)进行简化。如果t≤r/V，可以得到

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

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

图2给出了在不同场景下FTd(t)的近似值(App)和精确值(Pre)的比较。从图中可以看出，随着接触时长Td的增加，FTd(t)的近似值和精确值很接近，特别是当r = 6 m, V = 6 m/s时。因此，在下面的建模中，本文直接用FTd(t)的近似表达式来代替FTd(t)的精确表达式去计算接触探测概率。

将式(5)代入式(1)中，可以得到接触探测概率Pd(T)的表达式为

3.2 最优接触探测策略

上面仅仅给出了当节点的探测间隔为恒定值时的接触探测概率。事实上，在随机路点模型中，在所有平均接触探测间隔相同并且节点的接触过程未知的策略中，采用恒定探测间隔的策略是最优的。

定理 2 考虑一个总共有 N 个节点在网络中的环境，并且节点的接触时长是独立同分布的。再者，网络中的节点对有相同的接触时间间隔分布，且平均接触时间间隔为1/λ。那么，在所有平均接触探测间隔相同并且节点的接触过程未知的策略中，采用恒定探测间隔的策略是最优的。

证明 不失一般性，考虑网络中的节点要在一段很长的时间 L 内探测周围的环境，并且采用不同策略的节点在这段时间内总共探测 n 次。根据前面的介绍，对于采用恒定的探测间隔T=L/n的策略，在时间L 内的接触探测概率为Pd(T)=1F(t)dt。假设某一个特定的策略在时间点Tdt1,t2,…,tn探测总共 n 次，并且t1＜t2＜…＜tn, tn−t1≤L。设定t0=0，然后就可以得到 n 个接触探测间隔：I1=t1−t0,I2=t2−t1,…,In=tn−tn−1。因为节点是随机地选择时间点tk探测，并且网络中的节点对有相同的接触时间间隔分布，其平均接触时间间隔为1/λ，因此，在第 k 个时间间隔Ik=tk−tk−1内被某个节点探测到的有效接触的期望数可以表示为：λ(N−1)(Ik−FTd(t)dt )，这里 N 是网络中节点的总数。然后，在时间 L 内的期望接触探测概率可以表示为

当Ik≥T时，可以得到

当Ik＜T时，可以得到

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

随机路点模型中接触时长的分布是独立同分布的，并且节点对有相同的接触时间间隔分布，其分布可以近似为具有相同的接触率的指数分布[18−19]。因此，可以得出在随机路点模型中，在所有平均接触探测间隔相同并且节点接触过程无法预知的策略中，采用恒定探测间隔的策略是最优的。 证毕

3.3 能量效率和接触探测概率之间的折中

基于前面得到的接触探测概率的表达式，这一节介绍能量效率和接触探测概率之间的折中。本文只考虑在接触探测过程中消耗的能量，并未考虑数据传输过程中消耗的能量。因此，这里定义能量消耗为E=1/T，也就是网络中节点的探测率。如果网络中节点的探测率越大，那么节点在接触探测过程中消耗的能量就越多。因此，式(6)可以变化为

根据式(11)，当能量消耗 E 趋近于无穷大时，可以得到接触探测概率Pd(E)=1，也就是Pd(E)的最大值。当能量消耗E=0时，可以得到接触探测概率Pd(E)=0，也就是Pd(E)的最小值。

图3给出了不同场景下能量效率和接触探测概率之间的折中。图3(a)给出了当网络中节点的移动速度 V 变化时，能量效率和接触探测概率之间的折中，而图3(b)则给出了当网络中节点的通信范围r 变化时，能量效率和接触探测概率之间的折中。从图中可以看出，接触探测概率随着能量消耗的增加而增加。这个结果是合理的，因为更多的能量消耗意味着更加频繁的接触探测，从而导致接触探测概率的增加。但是，当能量消耗增加到一定值的时候，接触探测概率的增加率会大大地减小。例如，当r=6 m,V=2 m/s时，接触探测概率在能量消耗为 0.8时就将近达到最大值；当r=6 m,V=6 m/s，接触探测概率在能量消耗为2.5时将近达到最大值。因此，这些点就是接触探测过程中能量效率和接触探测概率之间的“好的折中点”。

图2 不同场景下FTd(t)的近似值和精确值的比较

图3 不同场景下能量效率和接触探测概率之间的折中

4 模型验证

本文利用 MATLAB 作为仿真工具来验证提出的理论模型的正确性。实验采用一个有10个节点分布在面积为1000×1000 m2的场景。场景中的节点根据随机路点模型移动，并且有相同的通信范围r。根据上面的假设，考虑网络中所有的节点都有相同的移动速度V，并且移动过程中的暂停时间为0。

图4给出了不同场景下FTd(t)的仿真结果(Sim)和FTd(t)的近似值(App)以及精确值(Pre)的比较。从图中可以看出，随着探测间隔T的增加，相比FTd(t)的精确值，不同场景下FTd(t)的仿真结果更加接近于FTd(t)的近似值，特别是当r=6 m, V=6 m/s 以及V=3 m/s。基于以上的结果，可以看出相比FTd(t)的精确值，本文给出的近似值更加接近FTd(t)的实际值。因此，本文可以用式(5)代替式(2)，来直接计算接触探测概率。

图5给出了不同场景下接触探测概率Pd(T)的仿真结果(Sim)和理论结果(Theo)的比较。图5(a)显示了当节点的移动速度变化时，Pd(T)的仿真结果和理论结果的比较，图5(b)显示了当节点的通信范围变化时，Pd(T)的仿真结果和理论结果的比较。从图中可以看出，随着探测间隔T的增加，不仅当节点的移动速度变化时，而且当节点的通信范围变化时，接触探测概率Pd(T)的仿真结果和理论结果都非常接近。

综上所述，通过不同场景下的仿真实验可以看出，相比FTd(t)的精确值，FTd(t)的仿真结果更加接近于FTd(t)的近似值；接触探测概率Pd(T)的仿真结果也非常接近于其理论结果，从而证明了本文提出的理论模型的正确性。

5 结束语

图4 FTd(t)的理论结果和相应的仿真结果的比较

图5 不同场景下Pd(T)的理论结果和相应的仿真结果的比较

本文研究了延迟容忍网络中基于随机路点模型的接触探测过程的能量有效问题。在给定随机路点模型中接触时长分布的情况下，从理论上分别得到了接触探测概率的表达式，并且也证明了在所有平均探测间隔相同并且不能提前知道节点的接触过程的策略中，采用恒定探测间隔的策略是最优的。其次，基于提出的理论模型，分析了不同情况下能量效率和接触探测概率之间的折中。最后，通过仿真实验验证所提出的模型的正确性。实验结果表明在不同场景下接触探测概率的仿真结果和理论结果都非常接近，从而证明了提出模型的正确性。

[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] 吴亚辉, 邓苏, 黄宏斌. 延迟容忍网络状态感知的路由策略研究[J]. 电子与信息学报, 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] 张振京, 金志刚, 舒炎泰. 基于节点运动预测的社会性DTN高效路由[J]. 计算机学报, 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] 李文霁, 郑康锋, 张冬梅, 等. 一种高效的延迟容忍移动传感器网络异步探测机制[J]. 电子与信息学报, 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年生，博士，讲师，研究方向为延迟容忍网络、移动社交网络和物联网技术.

任 东： 男，1976年生，博士，副教授，研究方向为模式识别、图像处理和物联网技术.

徐守志： 男，1969年生，博士，教授，研究方向为无线传感器网络和车辆自组网.

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改回

国家自然科学基金(61174177, 41172298)，国家863计划项目(2013AA10230207)，湖北省自然科学基金(2014CFB145)，湖北省水电工程智能视觉监测重点实验室开放基金(2014KLA07)和三峡大学人才科研启动基金(KJ2014B056, KJ2014B060)资助课题

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