基于贝叶斯概率树的机会社会网络转发节点选择方法

黄少芬， 王 杨， 孟 丹， 赵传信， 赵晨曦， 许闪闪， 方 群

0 引 言

机会社会网络(Opportunistic Social Network，OSN)是一种以人为主体的机会网络，网络中的节点具有社会属性。其主要特点：一是源节点与目标节点之间进行通信时不存在完整的路径[3]，二是消息的转发主要依赖节点的“存储—携带—转发”方法，将消息送达到目标节点。

针对机会社会网络转发节点选择问题，目前，国内外的相关研究主要分为以下三类：1)传染病转发(Epidemic Forwarding)机制[4]：运用洪泛的思想去复制网络中节点的消息副本，其优点是具有较高的消息投递成功率，但是缓存资源开销大。2)基于上下文感知(Context-aware Forwarding)转发机制[7]：主要通过获取节点移动速度、缓存大小、移动方向，并结合网络拓扑结构等特点，消息传输过程中根据上下文感知判断并决定合适的转发节点。3)基于社区感知(Community-aware Forwarding)转发机制[8]：采用单副本半隐式马尔可夫模型转发方法，通过节点在不同周期下的接触方式相似性进行社区发现。

以上三种转发方法主要针对节点消息转发机制问题，忽略了转发节点的相遇概率大小以及节点之间的社会关系强度差异。本文主要工作是在充分考虑节点的社会属性,利用社区内节点的活跃度能够增加社区之间联系的基础上,提出了一种基于贝叶斯概率树节点选择方法以减少消息平均时延和路由开销比，提高消息投递成功率。

1 网络模型及问题描述

1.1 网络模型

定义1:本文定义网络拓扑结构包含节点和链路组成的连通图，即为G=(N,L)，N代表节点组成的集合，则L代表节点间存在边的集合,表示节点与节点的连接状态。节点之间存在连接表示节点在过去的时间内相遇过并转发消息，否则没有。

定义2:(社区活跃度)表示节点离开所在社区去访问网络中其他社区的次数，同时也表示社区的聚集情况[8]。社区活跃度越大，节点离开本地社区的概率就越大，与其他社区节点相遇次数增加。反之，概率越小，相遇机会变小。

1.2 问题描述

图1 机会社会网络应用场景示意图Fig.1 Opportunity social network scenario diagram

假设该网络模型由m个社区、n个节点所组成，在消息转发时每个节点只属于一个社区，不考虑节点自私行为。处于同一个社区，节点间交互次数较多，联系较频繁。因此，可以利用社会关系强度选择节点进行消息传输，从而降低消息平均时延。相反，若节点处于不同的社区，就要先通过寻找社区，其次在社区内查找社会关系强度高的节点进行消息转发。根据社交权值大小，根据节点的权值判断是否可作为消息转发节点，保证消息在社区内能够迅速转发。如图1所示。

由图1的机会社会网络应用场景示意图可看出，节点分布在同一个社区比较密集，联系较频繁，传输效率高。而不同社区之间进行连接就需要选择社交权值比较大的节点作为转发节点，保证了消息传输的高效性。

图2 社团结构示意图Fig.2 Community structure diagram

1.2.1 社团结构 在机会社会网络的应用场景中，节点由于地理位置、兴趣爱好等划分为不同社团。而社团结构又把节点划分成不同的社区，社区内的节点分布均匀，连接频繁，社区间的节点连接匮乏。在日常生活中和专业合作中，人们往往会因为共同兴趣、工作地点等形成社团结构，图2表示为机会社会网络一个具有3个社团结构和15个节点的网络拓扑结构示意图。

1.2.2 节点消息转发策略 应用场景假设为某省一所高校，同一院系的同学、老师等可以看作一个小社团，同一院系的成员联系紧密，具有很强的社会关系，能够将消息迅速在其中传输；而处于不同院系的成员，联系稀疏，社会关系强度较低。各院系之间的联系又需要社会关系度高的人员在其中进行连接，进而达到消息转发的目的。

图3所示为某高校的院系间领导与学生进行消息转发的示意图，源节点S与目标节点所在的社区节点D通信时，在t1时刻，由图中可看出两个节点进行间接通信，此时需要在源节点所在的社区内找出比当前节点活跃度高的节点，即节点A。在t2时刻，转发节点A向目标节点所在的区域范围移动，此时与E节点相遇并完成消息的转发，到达t3时刻，将消息转发给目标节点D。该方法在消息平均时延得到进一步改善，使得消息传输率提高。

图3 消息转发示意图

2 社区划分及转发节点选择算法

2.1 社区划分策略

由于机会社会网络中的节点移动具有随机性，将网络划分为不同的社区，分别在社区内和社区间完成消息的转发过程。同一社区的节点联系密切，相遇次数较高；不同社区间的节点因为进行消息的转发时相遇次数较少，相遇概率也随之降低。

定义3：(相遇频率)指节点i和节点j的相遇总次数与节点j从初始状态到t时间段内与其他节点相遇的总次数比值，即

(1)

其中Mi,j(t)表示网络中节点i与节点j在t时间段内进行消息转发时相遇的总次数，Mj(t)表示节点i和节点j从起初到t时间段内与其他节点相遇的总次数。

定义4：(社交权值)若两个节点i和节点j相互联系,其中节点与节点之间熟悉强度的取值范围为[0，1],数值越大说明个体之间越熟悉，社交强度越高。

根据网络中节点具有的社会关系特征，按照该特征将节点划分为不同的社区。其中节点表示携带移动设备的个体，节点之间存在的边表示移动设备携带者之间的社会关系，边所在的权值表示移动设备携带者之间的社会关系强度。现将网络中的节点按照上述方法进行划分，结果如图4所示。

图4 社区划分的结果

2.1.1 贝叶斯概率树 在许多消息转发方法中使用单副本机制，当携带节点和节点相遇时直接进行消息的转发或接收。在这种情况下，未考虑到转发过程中更好的相遇机会。为了解决上述问题，本文提出一种基于贝叶斯概率树转发节点选择(Bayesian Probability Tree-Based Forwarding Node Selection,BFANS)方法。该方法结合源节点到相遇节点间的概率及节点间的贝叶斯概率去选择下一个转发节点。此外，携带节点作为树的根节点，携带节点所遇到的节点作为树的二级和三级节点。满足这些节点的贝叶斯概率值位于两个节点所在的边，并且树节点上的内容表示消息由每个节点到目标节点成功交付的概率。

本文主要针对某个网络中含有i,a,b,c,和d节点，如下图5(a)所示。节点i将产生的消息存储后并转发给目标节点j，在某一时刻t0遇见了节点a，如果仅仅依赖于传输消息给携带节点和节点相遇的概率做出决定，发送给节点a后不会考虑所遇到的下一个机会。是否将消息发送给下一个节点a根据BFANS算法决定，如下图5(b)所示。在此情况下，将根节点的发送概率与满足节点的贝叶斯概率的值乘积和节点相遇的概率值进行比较。如果节点i在遇到节点a之后再遇到节点b的概率乘以b节点将消息传递到目标节点j概率高于由节点i到a的传输概率，节点i存储消息后遇到节点a后并希望遇见节点b，重复上述步骤，直到与目标节点j相遇并转发。

图5 贝叶斯概率树的产生过程

2.1.2 相遇概率估计 利用经典的算法Prophet来计算每个节点发送到目标节点的概率，其中P(i,j)是节点i发送消息到节点j的发送概率，Pinit∈[0,1]为初始化常数[2]。

P(i,j)=P(i,j)old+(1-P(i,j)old)×Pinit

(2)

其中Pinit为节点i发送消息给节点j首次相遇概率。

如果节点i发送消息到节点j在某段时间内不存在相遇情况，则传输概率将会降低。如式(3)所示。

P(i,j)=P(i,j)old×λω

(3)

其中λ是一个初始化常数,ω是一个时间单元个数，ω受社区内的时间间隔影响。

通过公式(4)计算节点与节点之间的贝叶斯概率。

(4)

2.2 BFANS消息传输过程

由于本文按照节点的社交权值及相遇概率值划分社区，源节点与目标节点想要进行消息传输，就需要利用社区内社交权值高的节点来辅助消息的传输。而在社区间的消息传输，利用BFANS将源节点作为根节点，其次将相遇的节点作为二级根节点，选择转发节点时需要考虑相遇概率和贝叶斯概率，直到将消息转发给目标节点为止。

2.2.1 社区内消息传输 在社区内的消息传输主要是根据网络中节点的相遇概率值大小来判定，并且利用相遇的概率值构建贝叶斯概率树，在该树中选择比此刻携带节点相遇概率值大的节点作为转发节点。在转发过程中，对于转发的消息会生成相应的副本，按照“先进先出”的原则进行消息的存储管理，直到遇见目标节点为止。从节约能量的角度来说，选择概率值高的节点作为转发节点这种方式，提高了消息传输效率。社区内消息转发方法如算法1所示。

2.2.2 社区间消息传输策略 节点在同一个社区内紧密相连，相遇机会较多，消息传输效率也得到进一步提高；而社区间消息传输的方法首先是将源节点所携带的消息传输到目标节点所在的社区内，再根据社区内的节点权值去寻找合适的转发节点，社区之间的消息传输目的是根据贝叶斯概率树选择最佳转发路径。节点之间的移动按照各自的兴趣爱好漫游在各个社区之间，使得社区之间存在连通性。对于存在单个节点时，只能访问节点所在的社区，因此节点只提供节点所在社区到目标社区的连通路径。节点到达其他节点社区需要通过中间节点的协助，大量的节点在社区之间移动可能存在许多条连通路径，找出其中最佳的路径可以优化社区间的消息传输。

在本文中，选择节点相遇概率高的节点作为转发节点，由于节点在漫游社区之间概率具有传递性，因此选取一条社交权值最高的路径。假设源节点S和目标节点D进行消息的转发时，详细过程如算法2所示。

算法1:社区内消息传输算法Input:Message m,encountering node viOutput:Node vi encounters va(a=1,2,3…)When va is not the destination node vjthen Calculate Piaa=1,2,3…)according Eq.(4) When Pia==max(Pia(a=1,2,3…)) Send m to the encounter node vaIf vi is the destination node vj Send m to the destination vj算法2:社区间消息传输算法Input:Message m,encountering node vi,forwarding node vcOutput:If vi and vj both in a community use 社区内传输算法When vi and vj are not in a community Send m to the most active community(vi➝vj)If vj and vc are in a community use 社区内传输算法 end ifend if

2.3 算法分析

针对上述模型，通过贝叶斯概率及相遇概率算法描述，并对算法进行相关分析。算法中将处于同一个社区内不同节点属性进行划分，并选择源节点作为根节点，根据节点相遇的概率构建贝叶斯概率树，并将消息存储在节点缓存区，消息转发时需要从节点缓存区找到，并转发给相遇的节点。算法通过一次深度遍历即可选择出最佳路径。时间复杂度为O(n2)。

3 仿真实验和结果分析

3.1 模拟环境设置

本文提出的BFANS算法在ONE[6]仿真平台上进行实验，与典型的消息转发算法Epidemic，Prophet两种进行实验对比[2]。参数设置如表1所示：

3.2 仿真结果分析

将本文算法与传统的Epidemic、Prophet算法在消息投递成功率、平均时延以及路由开销比率进行比较。下面分别介绍三个指标的定义[2]。

1)消息投递成功率 消息投递成功率是指成功到达目标节点的消息总数占网络中源节点发送消息的总数比例，计算公式为：

Dratio=R/S

(5)

该公式中R代表成功到达目标节点发送的消息总个数，S代表源节点已经发送到目标节点的消息个数[6]。

2)平均时延 平均时延为节点发送的消息的总时间占成功到达目标节点总个数之比，计算公式为：

(6)

其中Tι表示第i个节点在时间t内发送的消息到达目标节点的消息传输时延，R为成功到达目标节点的总数。

3)路由开销比率 表示在进行实验情况下，节点未能成功到达目的地消息总数占成功到达目的地的消息总数比值，计算公式为：

(7)

表1 主要参数设置

3.2.1 缓存空间对传输策略的影响分析 在机会社会网络中，节点的移动速度、方向都具有随机性，而节点的缓存大小也是有限的。本小节主要针对节点缓存空间大小，对提出的BFANS方法及先前的两种算法在消息成功投递率方面作出对比。

从图6中可看出，三种算法在不同缓存空间下有着明显的增长趋势。当缓存空间达到20MB时，在消息成功投递率方面呈下降的趋势，原因在于增大节点缓存空间及消息缓存空间有限导致丢弃的数量增加。BFANS算法之所以会优于其他两种路由算法，是因为相比于传统的Prophet，该算法在社区内部选择转发节点时采用了贝叶斯概率思想计算相遇概率值，能够精确的选择最佳的转发节点。

图6 不同缓存空间下消息投递成功率的比较Fig.6 Comparison of delivery rates in different buffersizes

图7 不同缓存空间下消息平均时延的比较
Fig.7 Comparison of the average latency in different buffersize

从图7结果显示可知，在平均时延方面的结果与消息成功投递率相似。平均时延越长，表明路径的选择优化能力越弱。因此，转发节点的正确选择能够减少消息的平均时延。随着节点自身的缓存空间不断增加，Prophet算法的传输平均时延与BFANS传输平均时延相接近。

图8 不同缓存空间下路由开销比率的比较Fig.8 Comparison of overhead ratio in different buffersizes

由图8可以看出，本文提出的BFANS算法低于其他两种算法在路由开销方面。Epidemic算法在路由开销方面比其他两种算法开销率要高，这是因为其他两种算法在起初的时候控制消息副本的数量，而在消息副本数量方面Epidemic算法未得到限制，在消息转发的过程同时会产生冗余，因此导致开销率较高。

由以上结果可看出，当节点的缓存空间变化时，可用于作为转发节点的数量也随之增加，节点转发的概率也增加。本文提出的BFANS方法与传统的Prophet算法相结合，在此基础上加以修改，提高了消息的投递率，而由于社区间可用于转发的节点选择不恰当，导致了消息在转发过程中传输延迟高，并造成了网络负载。文中所提出的BFANS消息转发方法主要是对节点的社会属性进行社区的划分，并且根据节点的移动规律及节点的相遇概率，完成转发节点选择过程。

3.2.2 节点数量对传输策略影响分析 从以上结果看出，网络中的节点移动范围已知及节点缓存空间大小确定的情况下，节点之间相遇的总次数和网络中存在的节点总数有关。本部分主要针对网络中节点数量的变化进行实验，分别从消息在转发过程中的消息成功投递率、发送消息平均时延及网络中路由开销比率3个方面。

Epidemic、Prophet、BFANS三种算法在不同节点个数下的消息成功率如图9所示，从图中可明显看出，消息成功投递率会受到节点数量的影响，节点数量达到一定个数，呈现出下降趋势。因为节点数量比较多，在消息的传输过程中，可用于转发的次数也多，从而导致投递率下降。随着节点数量的增加，本文提出的方法在消息成功投递率方面优于另外两种方法。

图9 不同节点个数下消息投递成功率的比较Fig.9 Comparison of delivery ratio in different node numbers

图10 不同节点个数下消息平均时延的比较
Fig.10 Comparison of average latency in different node numbers

图10显示了在节点个数不同的情况下对消息传输平均时延的影响，由图可以看出Epidemic、Prophet及BFANS三种算法的消息传输时延与消息成功投递率结果接近。随着节点个数增加，网络资源缓存空间有限，节点的选择方法没有针对性，导致传输的平均时延也不断增加。而本文所提出的算法相比于其他两种算法平均时延会降低，因为节点选择的同时会考虑下一节点相遇的概率，并确定是否转发消息给该节点。

图11不同节点个数下路由开销比率的比较Fig.11 Comparison of overhead ratio in different node numbers

图11所示的是不同节点个数下路由的开销比率，从图中可以看出Epidemic算法的开销随着节点增加会上升，原因在于网络中节点转发消息时采用洪泛法的思想。本文提出的方法在开销率方面低于其他两种算法，由于在消息的传输过程中，利用所提出的方法对社区进行划分，并计算节点之间的相遇概率，根据历史相遇概率值大小与贝叶斯概率值进行比较，来确定转发节点，直到将消息转发给目标节点结束转发。

由上图可知，在节点消息转发时采用Prophet算法，尽管增加网络中的节点数量可获取所有节点历史的相遇情况。但是，该算法在社区间传输时没有考虑社区之间的连接情况，因此，消息被转发次数较多，说明该节点到达目标节点距离越长。随着网络中节点的数量增加，节点之间相遇机会变多，利用BFANS能够更好的利用机会社会网络的消息传输特性，节点通过将消息存储，并利用相遇机会转发给其他节点，进而以同样方式寻找目标节点，使得消息可靠并迅速传输。

4 结束语

针对现有的机会社会网络转发节点选择存在的不足及低效的消息传输方法，根据贝叶斯概率提出了一种转发节点选择方法，该方法在Prophet算法基础上进行修改，根据节点特有的社会属性，对网络中存在的节点进行社区划分。在消息的传输过程中分别从社区内和社区间进行分析，合理的选择转发节点，利用节点的相遇概率及贝叶斯概率构建树，选择符合条件的节点进行转发，否则等待下一次相遇机会。实验结果表明，文中所提出的算法，相比于其他两种方法能够提高消息投递成功率，降低消息平均延时以及路由开销比率。

参考文献:

[1] ZHU K，LI W，FU X，et al.Data routing strategies in opportunistic mobile social networks:Taxonomy and open challenges [J].Computer Networks，2015，93(P1):183-198.

[2] DERAKHSHANFARD N，SABAEI M，RAHMANI A M.CPTR:conditional probability tree based routing in opportunistic networks [J].Wireless Networks，2015，23(1):1-8.

[3] RANGO F D，SOCIEVOLE A，Exploiting online and offline activity-based,metrics for opportunistic forwarding [J].Wireless Networks，2015,21(4):1163-1179.

[4] REN ZHI,PENG SHUANG,CHEN Hong,et al.Epidemic routing based on adaptive compression of vectors:efficient low-delay routing for opportunistic networks based on adaptive compression of vextors [J].International Journal of Communication Systems,2015,28(3):560-573.

[5] LINDGREN A，DORIA A，SCHELÉN O.Probabilistic routing in intermittently connected networks [J].Acm Sigmobile Mobile Computing & Communications Review，2004，7(3):19-20.

[6] MA X，BAI X.A community-based routing algorithm for opportunistic networks [C]//Fifth International Conference on Ubiquitous and Future Networks.IEEE，2013:701-706.

[7] LEE J，KIM S K，YOON J H，et al.Snapshot:a forwarding strategy based on analyzing network topology in opportunistic networks [J].Wireless Networks，2015，21(6):2055-2068.

[8] RAVAEI B，SABAEI M，Pedram H，et al.Community-aware single-copy content forwarding in Mobile Social Network [J].Wireless Networks，2017(7):1-17.

[9] VENDRAMIN A C K，MUNARETTO A，DELGADO M R，et al.A social-aware routing protocol for opportunistic networks [J].Expert Systems with Applications，2016(54):351-363.

[10] 熊永平,孙利民,牛建伟,等.机会网络[J].软件学报，2009(1)：124-137.