面向移动机会社会网络的社会感知和概率预测的路由方法

摘要

本发明公开了一种面向移动机会社会网络的社会感知和概率预测的路由方法，该方法在初始化阶段通过探索节点的活跃度、兴趣、移动性以及节点间的关系提出了两种相关的中心度，以简化网络模型；在路由阶段，基于所简化的网络模型，在综合考虑社会感知和概率预测的基础上进行消息的传输。此外，在消息传输过程中采用了一种消息副本控制策略，有效地控制了网络中消息的副本数，减少了网络资源的消耗。仿真实验结果表明，与其它三种经典的路由方法相比，本发明所公开的方法有效地提高了消息的投递率，降低了网络的开销率。

说明书

技术领域

本发明涉及移动机会社会网络领域，特别涉及一种面向移动机会社会网络的社会感知和概率预测的路由方法。

背景技术

在移动机会社会网络(Mobile Opportunistic Social Networks，以下简称MOSNs)中，移动用户(为简化起见，下文将交替使用移动用户、用户和节点)可以四处移动，不需要通信基础设施支持的条件下，可以利用手持的便携式移动设备进行消息传输。详细来说，用户所携带的便携式移动设备通常可以通过Wi-Fi或蓝牙进行无线通信，当两个设备处于彼此的通信范围内时，它们之间就能进行消息传输。正是由于MOSNs中消息的传输不需要通信基础设施支持这一特点，MOSNs被广泛地应用于许多场景中，比如：灾难救援通信、偏远地区通信或通信基础设施受损地区的通信。

与传统的自组织网络相比，MOSNs正经历着节点移动速度快，链路变化频繁和节点特征差异大等挑战。因此，路由成为MOSNs研究的主要问题之一。在MOSNs路由研究中，通常以多跳的方式，为消息选出一条从源节点到目的节点的路径。因此，当节点相遇时，如何为自身携带的消息选出合适的中继，成为MOSNs路由方法研究中的一个关键问题。

目前面向MOSNs的路由方法主要关注于利用节点的兴趣或移动特点来提高路由方法的性能(即，较高的投递率，较低的时延和网络开销)。其中，比较成功的策略是考虑概率或社会感知的路由方法。事实上，这些方法还存在一些不足。由于节点的社会特性具有长期稳定的特点，因此，该特点可以被用来降低路由决策的开销。所以，与社会感知的路由方法相比，一些基于概率预测的方法会产生大量的网络开销。此外，基于单副本的社会感知的路由方法通常不会有特别高的投递率，因为网络中的节点具有移动性而且在单副本方法中每个消息只存在一个副本，如果一个消息在网络中被丢弃，那么它将永远不可能被成功投递。因此，提出一种结合多副本并综合考虑概率和社会感知的方法来提高MOSNs的路由性能是一件很有必要的事情。

通常，一个MOSN可以被划分成一些区域，基于所划分的区域，人们可以访问一个或多个区域。我们的校园就是一个典型的MOSN，它可以被划分成宿舍、教学楼、学校食堂、操场和图书馆等区域。在划分好的区域中，学生和教职工可以在一个特定的区域中移动或者在区域间移动。

事实上，节点不是随机地在一个特定区域或在区域之间移动而是根据自身的兴趣特点选择所要访问的区域。具体来说，具有某一相同兴趣的节点通常会访问一些与该兴趣相关的位置。研究人员发现，在一个MOSN中，50％的节点会花费其70％的时间来访问很少的位置。显然，一些有关系或者兴趣相同的节点之间的相遇概率更高。同时，节点访问区域的行为具有长期稳定的特点。因此，我们可以探索节点的兴趣与划分好的区域之间的规律，然后将探索到的规律用在机会网络消息传输过程中。

此外，由于工作特点的不同，不同的人通常在不同的区域中扮演不同的角色。例如，图书管理员在工作时间通常会在学校图书馆里整理书籍，因此，他们在图书馆里的活跃度比其他人高，构成了图书馆的核心。研究人员也发现和证明了节点的活跃度对提高MOSNs路由性能的重要性。在本发明中，我们将每个被划分好的区域看成是一个小型的MOSN。在每个区域中，少数活跃的节点构成了该区域的核心，而该区域的边缘是由许多不活跃的节点所构成的，其中不活跃的节点指的是与该区域其它节点相遇频率较低的节点。因此，我们可以利用节点的活跃度来提高MOSNs路由算法的性能。

发明内容

本发明的目的在于提供一种面向移动机会社会网络的社会感知和概率预测的路由方法，该方法能够克服现有技术中存在的问题，实现网络节点消息传输的高投递率和低开销率。

为达到上述目的，本发明提供如下技术方案：

一种面向移动机会社会网络的社会感知和概率预测的路由方法，所述方法通过探索节点的活跃度、兴趣、移动性以及节点间的关系提出了两种相关的中心度，以简化网络模型，在已简化的网络模型、社会感知和概率预测的基础上对消息进行传输，并在消息传输过程中采用了消息副本控制策略，控制网络中消息的副本数，减少网络资源的消耗；具体包括以下步骤：

S1：网络初始化；

S2：在源区域S中传输消息m给Top_k_S，D集合中的节点；

S3：将消息m传输给目的区域D；

S4：在目的区域D中将消息m转发给目的节点d；

进一步，所述步骤S1具体包括：

S11：属于区域l的节点交换彼此缓冲区中所存储的从区域l到其它每个区域l'的前k个inter-region betweenness中心度较高的节点的信息；

S12：一个节点请求到其邻居节点所存储的相遇信息后，该节点会对请求到的参数和自身所存储的k个inter-region betweenness中心度较高的节点的参数进行降序排序，然后再选出前k个参数较高的节点信息，对自己所存储的信息进行更新；

S13：属于区域l的节点不断地在完成自身存储信息的更新后，从区域l到其余每个区域l'的Top_k_l，l'节点集合的信息会被选择出来并存储在属于区域l的每个节点的缓冲区中；

所述inter-region betweenness中心度用于衡量节点在区域l和l'之间传递消息的重要性；

进一步，所述步骤S2具体包括：

S21：通过局部记录的Top_k_S，D节点集合中的信息，建立一个从源区域S到目的区域D的虚拟连接；

S22：源节点s将消息m的h个初始副本按概率为Top_k_S，D节点集合中的每个节点v分配副本数H_v，计算公式为：

S23：确定Top_k_S，D节点集合中那些被分配副本数不小于1的节点为从区域S传递消息到区域D的桥梁节点；

S24：源节点s将消息m转发给步骤S23中所述桥梁节点；

进一步，所述步骤S3具体包括：

S31：Top_k_S，D集合中的节点v根据所接收到的消息m的副本后，计算出其能被分配到的消息m的副本数H_v；

S32：节点v将分配到的消息m的H_v个副本发送给遇到的第一个属于区域D的节点；

进一步，所述步骤S4具体包括：

S41：属于目的区域D的节点i接收到消息m的副本后，若目的节点d是节点i的邻居，节点i直接将消息m的副本转发给节点d，完成消息m的投递；

S42：若目的节点d不在属于目的区域D的节点i的邻居中，节点i从每个邻居节点v中请求其与目的节点d相遇的指数分布参数λ_v，d，计算出相应的相遇概率P_v,d；

S43：若节点i所拥有的消息m的副本数等于1，则节点i找出遇到目的节点d的相遇概率最高的邻居节点；如果所选出的节点遇到目的节点d的相遇概率比节点i遇到目的节点d的相遇概率高，节点i将消息m的这一副本发送给所选出来的节点，然后删除自身存储的消息m的副本；否则，节点i仍自己携带消息m的副本，直到遇到消息m的目的节点或合适的中继节点再进行转发。

若节点i所携带的消息m的副本数大于等于2，则节点i计算出每个邻居节点v将能被分配到的消息m的副本数HD_v；如果所计算出来的一个邻居节点v遇到消息m的目的节点d的相遇概率P_v，d高于节点i自身到目的节点d的相遇概率P_i,d，即满足P_v,d≥P_i，d，节点i将发送所计算出的HD_v个副本给节点v，否则不发送；

节点i发送副本给满足所述条件P_v,d≥P_i，d的邻居节点v之后，若还有剩余副本，节点i在自身和所有的邻居中找出intra-region>

所述相遇概率为：其中，t_m≥0。

附图说明

图1是本发明方法流程图；

图2是本发明区域间建立连接的演化模型图；

图3是本发明简化后的网络模型图；

图4是本发明在网络中有200个节点时节点缓冲区大小的变化对投递率影响的结果图；

图5是本发明在网络中有200个节点时消息大小的变化对投递率影响的结果图；

图6是本发明在网络中有400个节点时节点缓冲区大小的变化对投递率影响的结果图；

图7是本发明在网络中有400个节点时节点缓冲区大小的变化对开销率影响的结果图；

图8是本发明在网络中有400个节点时消息大小的变化对投递率影响的结果图；

图9是本发明在网络中有400个节点时消息大小的变化对开销率影响的结果图。

具体实施方式

以下结合附图和实施例对本发明作进一步的详细描述。

本发明的基本思想在于利用网络模型和假设以及基于社会感知和概率预测的方法，实现高投递率和低开销率的路由。

1、网络模型和假设

本发明将移动机会社会网络(简称MOSN)建模成一个有|V|个节点(V＝{v|v∈V})的有向图G＝(V,L,W)，其中，每一个节点v可以在|L|个区域内进行移动，W是网络中节点间或节点访问区域的权重值集合。

假设1.在本发明中，我们假定节点间的相遇频率和节点访问区域的频率均服从泊松分布，即任意两个节点间的相遇时间间隔或一个节点访问某一区域的时间间隔均服从指数分布。

每个节点v(v∈V)大多数情况下只访问少数的区域，而且节点v访问一个区域l(l∈L)的时间间隔服从参数为λ_v，l的指数分布，λ_v，l也是节点v访问区域l的权重。此外，单位时间内节点i与节点j的相遇频率参数为λ_i，j，λ_i，j也是节点i与节点j之间的连接权重。λ_i，j的值越大，表明节点i与节点j相遇次数越频繁。为了使我们的表述更清楚，我们将本发明中涉及的主要参数及其所表达的含义总结在表1中。

表1：

假设2.在本发明中，我们假设网络中没有孤立的区域，即任意一对区域之间都有一些共同的节点，我们称这些节点为“桥梁”节点。

2、区域构建

在描述本发明的方法之前，我们先建立区域，然后再定义两个与区域相关的中心度。

2.1区域

本发明实施例中的区域l是由经常访问该区域的一组节点集合C_l(访问频率超过了一个给定的阈值δ)所构成的。

C_l＝{v|λ_v,l≥δ,v∈V}(1)

如果节点v遇到了一个属于区域l的节点，这意味着节点v访问了区域l一次。记λ_v，l为节点v在单位时间内访问区域l的频数，计算公式如下：

其中，j是节点v所遇到的属于区域l的一个节点。

2.2区域中心度

中心度通常被用来测量节点在消息投递过程中的重要性。我们将整个网络建模成一些有重叠的区域。消息投递的过程可以被转化为在一个区域中投递或在两个区域间进行投递。因此，我们提出了intra-region weighted中心度来衡量节点在区域内部投递消息的重要性，用inter-region betweenness中心度来度量节点在区域间传递消息的重要性。

2.2.1 Intra-region weighted中心度

节点i的intra-region weighted中心度是所有与节点i相关的节点j的连接权重之和。此外，节点i和节点j均属于同一个区域l，即：

节点的intra-region weighted中心度值越大表明该节点在它所属的区域内越活跃，即，该节点会在它所属的区域内遇到更多的节点而且遇到这些节点的频率越大。

2.2.2 Inter-region betweenness中心度

对属于区域l的每个节点v来说，节点v访问其它区域l'的参数λ_v,l'越大，表明节点v的inter-region>

记Top_k_l，l'为从区域l到区域l'的前k个inter-region>l，l'节点集合来帮助消息完成从区域l到区域l'的转发。

3、社会感知和概率预测的路由方法

本发明提出的社会感知和概率预测的路由方法包括初始化阶段和路由阶段，如图1所示。在初始化阶段，每对区域l和l'形成了Top_k_l，l'节点集合，以简化网络模型。基于简化的网络模型，我们的路由阶段主要包括三个方面：①在源区域S中传播消息m给Top_k_S，D集合中的节点；②由Top_k_S，D集合中的节点将消息m转发到其目的区域D；③在目的区域D内将消息m转发给其目的节点d。

3.1初始化阶段

初始化阶段中，同属于区域l的节点在彼此的通信范围内时，会交换彼此缓冲区中所存储的相遇信息。所交换的相遇信息是指，属于区域l的节点存储了从区域l到其它每个区域l'的前k个inter-region betweenness中心度较高的节点的信息。当一个节点请求到其邻居节点所存储的相遇信息后，该节点会对请求到的参数和自身所存储的k个inter-region betweenness中心度较高的节点的参数进行降序排序，然后再选出前k个参数较高的节点信息，对自己所存储的信息进行更新。最终，随着节点的移动和相遇信息的交换和更新，从区域l到其余每个区域l'的Top_kl,l'节点集合的信息将会被选择出来并存储在属于区域l的每个节点的缓冲区中。因此，属于区域l的每个节点将会存储(k*(|L|-1))条相遇信息。

基于上述讨论，所形成的Top_k_l，l'节点集合可以被当作一个虚拟节点，并且通过Top_k_l，l'集合中的节点为消息从区域l到区域l'的投递建立了一个虚拟连接。此外，该虚拟连接的权重为λ_l,l'，如图2所示。该虚拟连接的权重服从参数为λ_l,l'的指数分布。该权重的计算满足：

根据所形成的从区域l到其余每个区域l'的Top_k_l，l'节点集合，区域l中的每个节点能建立一个从它到其余(|L|-1)个区域的有向图。此外，如果其它(|L|-1)个区域中的节点做相同的工作，网络模型将会被简化，如图3所示。

此外，当属于区域S的一个节点s产生了一个目的节点为d的消息m，且该目的节点d在区域D时，Top_k_S，D集合中的节点收到消息m后，只能将其传递给属于区域D中的节点，不能再转发给区域S中的节点。

3.2路由阶段

路由阶段主要是在移动机会社会网络中做路由决策，具体包括三个阶段：①在源区域S中传播消息m：消息m的源节点s在其所在区域S中将消息m传递给Top_k_S，D集合中的节点；②将消息m传给其目的区域D：Top_k_S，D集合中的节点将消息m转发给它遇到的第一个属于目的区域D中的节点；③在消息m的目的区域D内将其投递给目的节点d：属于目的区域D中的节点将消息m转发给其目的节点d。

3.2.1在源区域S中传输消息m给Top_k_S，D集合中的节点

当源节点s产生了一个消息m时，它首先通过局部记录的Top_k_S，D节点集合中的信息，建立一个从源区域S到目的区域D的虚拟连接。此外，源节点s将消息m的h个初始副本分配给Top_k_S，D集合中的节点。按概率为属于Top_k_S，D集合中的每个节点v分配副本数，公式如下：

经过分配之后，节点v将会拥有H_v个消息m的副本。是节点v在消息m副本数分配中所占的权重。一个节点所占的权重越大，该节点将会被分配到的副本数越多。也就是说，Top_k_S，D中的有些节点将会被分配一个或多个副本，有的节点将分配不到副本。因此，Top_k_S，D节点集合中那些能被分配的副本数不小于1的节点是实现消息从区域S传递到区域D真正的“桥梁”节点。

消息m传输的第一件最重要的事情是迅速找到那些真正的“桥梁”节点。在本发明中，我们将这些真正的“桥梁”节点看作是一个虚拟的节点B，区域S中的任何节点v遇到虚拟节点B的时间间隔服从参数为λ_v,B的指数分布，即：

将消息m转发给虚拟节点B的具体过程如算法1所示：

上述过程中，我们使用Num来表示节点i所拥有的消息m的副本数。如果此时消息m的目的节点d是节点i的邻居，节点i直接将消息m转发给目的节点d，完成消息m的投递。否则，对于节点i的每个邻居j，如果节点j属于B，节点j没有收到过消息m并且Num>0，则节点i转发消息m的一个副本给节点j，并使得所拥有的消息副本数更新为Num-1；经过上述循环处理后，如果节点i所拥有的消息m的剩余副本数大于等于1，节点i请求每个不属于B的邻居节点j的参数λ_j,B，并且根据公式(6)计算出自身的参数λ_i，B。此外，如果此时消息m的剩余副本数等于1，节点i在所有请求到的参数中找出参数值(λ_v，B)最高的邻居节点v。如果λ_v,B>λ_i，B，节点i将消息m转发给所选出的邻居v，然后将自身携带的副本删除。相反，如果λ_v,B≤λ_i,B，节点i仍然自己携带该副本。如果消息m剩余的副本数hi不小于2，节点i根据下面的公式(7)计算出每个邻居j所能被分配到的副本数。

HB_j是邻居j能被分配到的消息m的副本数。同样地，节点i能继续携带个消息m的副本。对于每个不属于B的邻居j，如果所计算出来的参数满足λ_j,B≥ε，则该邻居j实质上会被分配HB_j个消息m的副本，否则将不给邻居j分配副本，其中ε是所设定的阈值。

如果经过上述的分配之后，仍剩有关于消息m的未分配的副本，节点i根据公式(3)计算出自己在区域S中的intra-region weighted中心度，并请求它的每个邻居在区域S中的intra-region weighted中心度。节点i再从获得的intra-region weighted中心度值中找出中心度值最大的节点v，并将剩余的副本分配给它。最后，节点i按照副本数分配情况，将对应数目的副本发送给所选择的节点。

3.2.2将消息m传输给目的区域D

基于上一阶段的完成，消息m已经成功地被转发给了从区域S到区域D的“桥梁”节点。本阶段主要陈述当这些真正的“桥梁”节点获取到消息m的副本时，如何将消息m传输到目的区域D，具体过程如算法2所示：

当属于Top_k_S，D集合中的一个节点v接收到消息m的一个副本时，

它首先根据公式(5)计算出能被分配到的消息m的副本数H_v。节点v再将所能分配到的Hv个副本发送给之后遇到的第一个属于区域D的节点。

为了实现控制消息m副本数的目标，我们定义一旦属于Top_k_S,D集合中的某个节点收到了消息m的副本，该节点将不会再接收任何关于消息m的副本，而且只能将消息m传递给属于目的区域D的节点，不能在源区域S中再传播。

3.2.3在目的区域D中将消息m转发给目的节点d

基于第二阶段的完成，本阶段的主要目标是在目的区域D中将消息m发送给它的目的节点d。更详细地说，当属于目的区域D的节点i收到消息m的副本时，节点i将尽自己最大的努力将消息m发给目的节点d，具体过程如算法3所示：

每个属于目的区域D的节点i记录了与其它属于该区域的节点j相遇的指数分布参数λ_i，j。因此，节点i也记录了它与消息m的目的节点d相遇的指数分布参数λ_i，d。基于所记录的信息，节点i在消息m的剩余TTL(Time>m内将会遇到目的节点d的相遇概率为：

其中，t_m≥0。

在本阶段中，如果目的节点d在节点i的邻居中，节点i直接将消息m的副本转发给节点d，完成消息m的投递。否则，节点i首先从每个邻居节点v中请求其与目的节点d相遇的指数分布参数λ_v,d，再根据公式(8)分别计算出相应的相遇概率P_v,d。如果消息m的目的节点d不在节点i的通信范围内，且节点i所拥有的消息m的副本数等于1，节点i找出遇到目的节点d的相遇概率最高的邻居节点。如果所选出的节点遇到目的节点d的相遇概率比节点i遇到目的节点d的相遇概率高，节点i将消息m的这一副本发送给所选出来的节点，然后删除自身存储的消息m的副本。如果节点i所携带的消息m的副本数hd_i大于等于2，节点i计算出每个邻居v将能被分配到的消息m的副本数，计算公式如(9)所示：

其中，HD_v是节点v能被分配到的消息m的副本数。同样地，节点i能继续携带的消息m的副本的数量是而且，如果所计算出来的一个邻居节点v遇到消息m的目的节点d的相遇概率P_v,d高于节点i自身到目的节点d的相遇概率P_i,d，即满足P_v,d≥P_i，d，节点i将发送所计算出的HD_v个副本给节点v；否则不发送。

其次，如果有剩余副本，节点i根据公式(3)计算它在区域D中的intra-region weighted中心度，并请求其每个邻居在区域D中的intra-region weighted中心度。之后，节点i在自身和所有的邻居中找出intra-region weighted中心度值最高的节点j，再将剩余的副本分配给该节点。节点j所能获得到的消息m的副本个数是所有不满足条件P_v,d≥P_i，d的邻居节点v被计算出来的能分配到的副本数HD_v之和。最终，节点i按照分配情况，将消息m的副本按照所计算的数量发送给相应的节点。

4、实验验证

4.1实验设置

为了验证本发明所提方法的有效性，在网络仿真工具ONE中，将该方法与Epidemic、Spray-and-wait和Prophet这三种经典的路由方法进行比较。主要从投递率和开销率两方面来评估每个算法的性能，投递率和开销率的定义如下：

投递率：消息投递率公式为其中N_d是成功投递给目的节点的消息的数量，N_g是所产生的消息的总数量。

开销率：开销率用来评价带宽使用的有效性，公式为其中N_r是网络中消息副本的总数，N_d是成功投递给目的节点的消息的数量。

本发明所提方法与其它三种经典的路由方法在ONE仿真工具中的共同基本参数设置如表2所示。

表2：

4.2实验结果与分析

4.2.1实验一

针对网络中消息大小的变化情况，对本方法与其它三种路由方法进行了比较。网络中消息的大小分别设为：100KB、150KB、200KB、250KB、300KB、400KB、450KB、500KB、550KB、600KB、650KB、700KB、750KB、800KB、850KB、900KB、950KB和1000KB。网络由两个区域所构成。图5是每个区域中有100个节点，即网络中一共有200个节点时，消息大小的变化对投递率影响的实验结果图。图8是每个区域中有200个节点，即网络中一共有400个节点时，消息大小的变化对投递率影响的实验结果图。从实验结果中，我们可以清楚地看到：随着消息增大，每个算法的投递率都呈现出不同程度的下降趋势。导致这一现象的原因主要有两个。原因一，随着消息增大，每个节点的缓冲区中能存储的消息数量将会减少，只能协助较少的消息进行转发。原因二，由于节点的移动性，消息越大，该消息能被成功传输的概率会降低。两个相遇的节点很可能在交换信息的过程中，离开彼此的通信范围，中断消息的传输。从实验结果图中也可以清楚地看到，与其它方法相比，本方法能维持一个较高的投递率而且投递率下降的趋势更为缓慢。图9是每个区域中有200个节点，即网络中一共有400个节点时，不同方法的开销率变化趋势。从图中我们可以观察到，与其它方法相比，本方法和spray-and-wait方法能保持一个较低的开销率。这一现象的主要原因是，这两种方法都能有效地控制网络中消息的副本数。

4.2.2实验二

针对网络中节点的缓冲区大小的变化情况，对本方法和其它三种路由方法进行了比较。网络中节点的缓冲区大小分别设为：1MB、2MB、3MB、4MB、5MB、10MB、20MB、30MB、40MB、50MB、60MB、70MB、80MB、90MB、100MB。图4是每个区域中有100个节点，即网络中一共有200个节点时，节点缓冲区大小的变化对消息投递率影响的实验结果图。图6是每个区域中有200个节点，即网络中一共有400个节点时，节点缓冲区大小的变化对消息投递率影响的实验结果图。实验结果表明，随着节点缓冲区的增大，每个算法的投递率都呈现出不同程度的上升趋势。本方法和spray-and-wait方法的投递率都先上升然后保持平滑。造成这一现象的主要原因是随着节点缓冲区的增大，一个节点能存储更多的消息，因此能帮助更多节点转发消息。图7是每个区域有200个节点，即网络中一共有400个节点时，随着节点缓冲区大小的改变，不同方法的开销率变化情况。显然，与其它方法相比，本方法能保持一个较低的开销率。

以上两组实验表明：从消息大小和节点缓冲区大小的变化情况来看，本方法总能在保持较高投递率的同时，维持较低的开销率。

应当理解，以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施方式仅限于此，对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单的推演或替换，都应当视为属于本发明由所提交的权利要求书确定专利保护范围。