DTN中基于贝叶斯的节点相遇概率预测方法

马继红，杨文涛,白跃彬

(1.邯郸职业技术学院 机电工程系，河北 邯郸　056001；2.北京航空航天大学 计算机学院，北京　100191)



DTN中基于贝叶斯的节点相遇概率预测方法

马继红1，杨文涛2,白跃彬2

(1.邯郸职业技术学院 机电工程系，河北 邯郸056001；2.北京航空航天大学 计算机学院，北京100191)

DTN网络由于频繁的网络断开、高延迟和异构性等原因，导致网络可用性较低；为了提高DTN网络可用性，一方面要提高数据包送达目的节点的比例，另一方面也要注意控制网络中的副本数量；着重研究在便携设备交换网(PSN)和移动规律性较弱的车载网络(VAN)等网络中对节点相遇概率直接预测的方法；提出了一种利用贝叶斯概率的方法进行相遇概率预测，这种方法基于数据集的历史数据，不依赖于具体的数据集，具有较好的适应性和准确性。

DTN网络；贝叶斯网络；节点；相遇概率

0　引言

容迟容断网络DTN 是主要针对端到端连接和节点资源都有限时的一种网络解决方案，用以满足随意的异步消息的可靠传递。PROPHET路由协议借助历史数据对相遇概率进行估算，根据和目的节点的相遇概率进行转发，取得了较好的效果。两个节点的相遇概率预测是DTN预测的核心问题。对于星际网络(IPN)和规律性较强的车载网络(VAN)[1]等移动规律较为固定和已知的网络形态中，节点相遇的时间可以通过对节点的运动建模计算得到较为精确的时间，因此，在这种网络形态下不需要进行相遇概率的预测。而对于便携设备交换网(PSN)和移动规律性较弱的车载网络(VAN)等网络，由于无法对节点的移动规律进行建模，所以目前此类网络中的路由主要通过划分社区或直接计算等多种方式对节点间相遇概率进行预测，并利用预测结果作为路由选择的依据。本文将着重研究在后一种情况下对节点相遇概率直接预测的方法。

目前还不存在一种可以对相遇概率进行直接预测且预测准确率较高的算法，同时上述预测方法考虑因素较为单一，在不同数据集中表现具有较大区别，在具体不同的网络环境下通用性较差。本文提出了一种利用贝叶斯概率的方法进行相遇概率预测，这种方法基于数据集的历史数据，不依赖于具体的数据集，具有较好的适应性和准确性。

1　基于贝叶斯网络的DTN节点相遇知识学习方法

1.1节点相遇知识挖掘

节点相遇知识是指DTN中任意两节点间存在的两节点在过去一段时间内的相遇情况的特征，包括节点接触频率、平均接触时长、平均接触时间间隔等。这些参数中有些参数属于受节点影响的主要原因，有些则受其它因素影响。为了得到影响节点相遇的主要因素，通过构建贝叶斯网络对节点间相遇情况的特征进行学习。

表1　节点相遇知识特征参数

1.2构建贝叶斯网络模型

通过结构学习和参数学习过程，可以构建出一个基于网络性能参数变量的贝叶斯网络结构模型，如图1所示。从图中可以看出主要因素有接触频率、平均接触时长、被影响因素为节点流行度和节点相似度。贝叶斯网络模型表示出了各个网络参数之间的依赖关系，同时可以得出它们具体参数值之间的概率关系。

图1　贝叶斯网络结构图

2　基于贝叶斯概率的DTN节点相遇概率预测方法

对相对概率的预测，是指在两个节点处在没有接触的情况下，根据节点的历史数据信息及所处网络环境对两节点在未来一段时间内相遇的概率进行预测。将用到表2中的符号。

表2　符号定义表

预测两个节点是否会在未来的某段时间Tf内相遇，其实就是预测目前两节点在最近接触后Tl时间时，再等待Tf时间内两节点是否会有新的接触，即二者所处接触间隔的长度Ic是否短于Tf+Tl。

P(节点在Tf内相遇)=P(Ic

Tf和Tl都是已知量，故整个问题转化为对间隔长度Ic的估计。由于目前已经等待了Tl的时间，故Ic>Tl。所以：

P(节点在Tf内相遇)=P(IcTl)

由条件概率公式可得：

P(IcTl)=P(IcTl)/P(Ic>Tl)

综合以上公式可得：

P(节点在Tf内相遇)=f(Tl

上式中的f(a)为发生a事件的频率。在这个场景中，频率可通过统计历史数据获得。综上，可利用历史数据对相遇概率进行预测。

3　实验结果

3.1方法有效性验证

对于实验可能会出现的结果可以分为4种情况，如表3所示。

表3　实验结果类型

对于预测准确性的度量可以参考信息检索中的查全率(Recall Ratio)和检准率(Accuracy)。二者的定义如下所示：

Recall Ratio =A1/(A1+A2)

Accuracy = A1/(A1+A3)

公式中所用符号均如表3所示。对于路由过程存在多个消息副本的DTN路由协议来说，查全率较为重要；对于单个消息副本的DTN路由协议来说，检准率更为重要。在实际应用中可以根据需求灵活选择参数，获得较好的路由效果。

实验均采用Haggle-6数据集，为防止异常数据的影响只对接触时间超过一个数据采集周期(120 s)的接触进行分析。预测的目标都是在未来1小时内是否会有新的接触发生。由于未限定求相遇概率的原因，因此实验并未根据实际需求取阈值，而是将所有阈值(每隔0.1%进行取样)下的查全率和检准率进行对比，以图的形式展示。其中查全率用虚线表示，检准率用实线表示。

图2为PROPHET路由算法中提供的相遇概率预测方法所得到的查全率和检准率的对比。其中横坐标为根据算法的预测概率区分是否会相遇的阈值，纵坐标为在该阈值下的查全率(虚线)和检准率(实线)。其中，这里PROPHET预测路由算法中的参数采用ONE仿真软件中的默认设置。从结果可知，随着阈值的提高，所预测的检准率会逐渐提升，但查全率始终维持在0.5左右的水平。

图3 为本文算法所预测的相遇概率预测。从图中可以看出在默认取0.5做分割阈值时，无论是查全率还是检准率都明显高于PROPHET算法。而且查全率和检准率有较为明显的负相关，可以通过选择不同阈值满足不同路由协议的需求。

图2　PROPHET概率预测方法阈值选取对查全和检准率的影响

图3　贝叶斯概率预测方法阈值选取对查全率和检准率的影响

3.2方法普适性验证

上面的方法验证了贝叶斯方法的有效性，为了验证说明方法的普适性，在另外4种不同类型的数据集中将贝叶斯方法同另外两种方法分别进行对比验证。4种数据集主要参数如表4所示。

表4　数据集及相关参数

Haggle数据集[2]是剑桥大学通过将自制的蓝牙设备(iMotes)部署到人身上进行数据采集得到的。

NUS数据集[3]是新加坡国立大学通过手机采集的的数据。

Reality数据集[4]是麻省理工学院利用一百部诺基亚6600手机收集的数据。

Sassy数据集[5]是圣安德鲁斯大学利用自制的IEEE802.15设备(T-mote)进行的数据采集，

对于每组实验主要有3个参数：数据集、预测方法及预测时间。根据上表的参数可以看出，我们一共进行了84组实验。每组实验进行100000次抽样，保证平均每个阈值样本所代表的参数为100个。

为了综合考虑查全率和检准率，在这里定义综合准确率为查全率和检准率的几何平均值，这个值在二者差距较大的情况下较客观的反应了预测质量。取每次实验各阈值对应的综合准确率中的最大值作为这次实验预测质量的代表。各组实验结果如图4～图7所示。其中黑色实线代表贝叶斯方法在不同预测时长的综合准确率，虚线和灰色十字分别代表PROPHET路由中的预测方法和基于指数分布的预测方法在不同预测时长的综合准确率。

图4　Haggle3数据集3种方法对比

图5　NUS数据集3种方法对比

图6　Sassy数据集3种方法对比

图7　Reality数据集3种方法对比

从图中可以看出，基于贝叶斯概率的节点相遇概率计算方法在各不同种类的数据集中的预测中的各种预测时长准确性均优于其他两种预测方法。

表5　3种算法准确率对比　%

表5为3种方法在4个数据集中的平均准确率，可以看出贝叶斯方法在各个数据集中预测准确性最高。表6表明新的贝叶斯方法对PROPHET方法和指数分布这两种相遇概率预测方法的准确度分别提升了39.62%和75.73%。

表6　贝叶斯方法准确率提升百分比　%

3.3实验结果分析

通过统计数据集中接触间隔，可以对基于贝叶斯的相遇概率预测方法预测概率提升的原因进行解释。

PROPHET路由协议中的相遇概率预测方法在节点没有接触时，预测的两节点的相遇概率会随时间逐渐缩小；基于指数分布的相遇概率预测方法假设接触间隔服从指数分布，所预测的相遇概率也是随时间逐渐缩小。

Haggle数据集里接触间隔和频率的关系如图 8所示。其中横轴为接触间隔，单位为小时；纵轴为接触间隔的频数。从图中可以看出，在开始时，随着接触间隔的增长，接触间隔的频率即节点再次接触的概率逐渐减小，这一点上之前的两种路由算法是较为符合实际情况的。但是随着时间的增长，当接触间隔超过十个小时后，接触间隔的频率随间隔增长会逐渐增加，并在18～24个小时左右达到峰值。结合数据集采集的场景，在第一天会议结束后到第二天会议开始，之间的时间间隔大约就是18～24个小时。在这个阶段，PROPHET路由协议中的相遇概率预测方法和基于指数分布的相遇概率预测方法均无法给出相应的预测。

图8　Haggle数据集接触间隔长度和频率的关系图

图9　Reality数据集接触间隔长度和频率的关系图

基于贝叶斯的相遇概率预测方法通过对历史数据的统计，可以有效拟合实际中的接触间隔变化规律。如当距离上次接触距离为五小时时，可以从图中的历史数据观察到未来五小时内会有新的接触发生的频率占接触间隔五小时以上的频率较小，因此发生接触的可能性也较小；当距离上次接触发生时间距离15小时时，虽然未发生接触时间间隔更长，但根据历史数据可知这时未来五小时内可能发生新接触的概率反而会增大，因此所得到的相遇概率的预测值也会相应变大。

不同于Haggle数据集仅收集几天的数据，Reality数据集连续收集了节点九个月的移动和接触数据，更便于观察节点接触的长期规律性。Reality数据集接触间隔长度和频率的关系如图9所示，其中横轴单位为天。从图中可以看出，虽然节点接触时间总体来看具有长期规律性，即接触概率随接触间隔的增长而降低，但图中仍然可以看出间隔时间的分布并非平滑的曲线，而是存在众多明显的峰值，而且峰值的排列具有一定的规律性：大约每七天左右就会出现一个峰值。结合数据集采集的场景来看，在校园活动中存在较强的以星期为周期的规律性：课程、例会、周末社交活动，很多人会间隔七天左右再次见面。Reality数据集的分析结果体现了这种规律性。

结合之前的分析可知，PROPHET路由协议中的概率预测方法和基于指数分布的预测方法均无法预测这种间隔七天的规律性，而贝叶斯方法可以通过历史数据的统计获得这种规律性，得到更为准确的预测值。同时，贝叶斯方法对这种规律性的预测完全基于历史数据而不需基于任何先验知识，是的基于贝叶斯的相遇概率预测方法具有普适性。

4　结论

PROPHET路由方法主要关注相遇概率相对大小，并不关注相遇概率的绝对值，因此即使在预测准确率偏低的情况下路由方法仍然有较好的表现。基于指数分布的预测方法目前多限于数据研究，并未作为路由的主要依据。两种预测方法的准确率都偏低，无法作为分簇的条件。贝叶斯概率预测方法预测相遇概率的准确性较高，已经可以作为DTN节点分簇的依据。

[1] Hull B,Bychkovsky V,Zhang Y,et al. CarTel: a distributed mobile sensor computing system[A]. Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys’06)[C].2006.

[2] Pan H,Chaintreau A, Scott J,et al. Pocket switched networks and human mobility in conference environments [A]. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking (WDTN’05)[C].2005.

[3] Natarajan A,Motani M,Srinivasan V. Understanding urban interactions from bluetooth phone contact traces [A].PAM 2007,8th Passive and Active Measurement Conference[C].2007.

[4] Nathan E,Pentland A. Reality mining: sensing complex social systems[J]. Journal of Personal and Ubiquitous Computing,2006.

[5] Bigwood G,Rehunathan D,Bateman M,et al. Exploiting self-reported social networks for routing in ubiquitous computing environments [A].Proceedings of IEEE International Conference on Wireless and Mobile Computing,Networking and Communication (WiMob '08)[C].2008.

A Prediction Method of Node Encounter Probability Using Bayesian in DTN

Ma Jihong1,Yang Wentao2,Bai Yuebin2

(1.Department of Mechanical and Electrical Engineering,Handan Polytechnic College,Handan056001,China 2.School of Computer Science and Engineering,Beihang University,Beijing100191,China)

Due to the frequent network disconnection,high latency and heterogeneity,DTN network has resulted in low network availability. In order to improve the availability of DTN network,it should increase the proportion of the data packets to the destination node. On the other hand,it also should control the number of copies in the network. The method of direct prediction of node encounter probability in the network,such as PSN,and weak regularity VAN,is studied. It presents a prediction method of Bayesian probability of encounter probability. This method is based on the historical data of data sets,which is not dependent on specific data sets,with better flexibility and accuracy.

DTN; Bayesian network; node; encounter probability

1671-4598(2016)04-0185-04DOI：10.16526/j.cnki.11-4762/tp.2016.04.054

TP393

A

2015-10-17；

2015-10-30。

国家自然科学基金项目(61073076)；河北省科技计划支撑项目(13200326D)。

马继红(1977-)，女，河北定州人，在读硕士，副教授，主要从事计算机控制方向的研究。

白跃彬(1962-)，男，河北石家庄人，教授，博士生导师，主要从事计算机网络及分布式系统方向的研究。