基于社会关系和信任关系的机会网络路由算法

窦 冲，王小明，林亚光，王冉茵，王新燕

(1.陕西师范大学 现代教学技术教育部重点实验室，陕西 西安 710119； 2.陕西师范大学 计算机科学学院，陕西 西安 710119)

0 引 言

近年来，随着移动通信技术的快速发展，便携式智能设备(如智能手机、PDA等)已经成为人们日常生活的必备品，用户可以利用移动带来的相遇机会形成以通信为目的的自组织网络，进而对数据进行共享。机会网络[1]是一种具有一般延迟容忍网络[2]特征的移动自组织网络[3]，基于“存储-携带-转发”的消息传输机制，节点接收到消息时，先将消息存储在本地缓存中，然后携带该消息移动直到遇到合适的中继节点进行转发。然而，节点设备资源包括的能量和缓存通常是有限的，转发消息将会导致资源的额外开销，大多节点都会表现出一定的自私性，即拒绝转发消息或者先答应帮助转发，然后将接收到的消息进行丢弃[4]，导致网络性能受到很大的影响。因此，解决自私节点行为的影响变得至关重要。

在机会网络中，如果用户间具有一定的社会关系，则他们的联系会更加频繁。研究表明，社会网络中节点的移动具有规律性，表现出节点间重复或者周期性的交互。因此可以利用节点的社会关系，因为节点间社会特征的相似程度在一定程度上可以反映为用户间联系的频繁程度[5]。

机会网络具有端到端连接易断、节点经常移动等特点，导致现有的信任模型很难直接运用到网络中。其存在的问题包括：大多信任机制无法适应信任关系的动态变化，不支持推荐信任关系的自动形成与更新；没有利用信任关系防止协同的自私行为；没有考虑到将社会关系和信任关系结合起来。

针对上述问题，提出一种基于社会关系和信任关系的路由算法SRTR，主要内容如下：

(1)从节点间的历史交互信息和可信邻居节点的推荐信息两个角度出发，综合考虑直接信任度和间接信任度，通过总体信任度的计算建立信任矩阵。根据信任矩阵筛选出当前周期内的可信节点，建立本地信任列表，确保具有较高信任水平的节点参与消息的安全转发过程。

(2)采用向量形式表示节点的社会属性特征，并根据交互信息进行更新。通过计算和目的节点的社会相似度，选择信任列表中社会相似度更大的节点作为中继节点。确保消息到达目的节点的最佳路径，提高消息投递率，降低平均延迟。

(3)对于已选择的中继节点，根据社会相似度大小按比例分配消息副本，确保消息副本的高效传输。

1 相关工作

相关研究人员提出了多种经典的路由协议。文献[6]提出了基于洪泛的Epidemic协议。当前节点复制一份消息传输给相遇节点，直到传输给目的节点，该协议具有较大的投递率，但是存在大量的副本冗余。PROPHET[7]协议根据相遇概率选择性地复制数据分组。

相关文献基于用户间的交互行为，将用户的活跃度或者中心性作为转发消息的重要参考指标。文献[8]提出了一种基于活跃度的路由协议Bubble Rap，该协议为每个节点设定活跃度等级，节点将消息转发至活跃度排名高的节点，直至遇到目的节点。文献[9]基于数据挖掘中PageRank算法的思想，将消息转发至重要性大的节点，直至遇到目的节点。文献[10]基于兴趣社区的思想选择中继节点进行数据包的转发。文献[11]提出dLife算法，根据节点间历史相遇信息来预测下一周期的相遇情况。

以上算法虽然考虑了节点间的交互行为或社会关系，但通常认为节点是相互信任的，忽略了网络中存在的自私行为。文献[12]提出基于Credit的激励机制，节点转发消息可以获得虚拟货币，付出虚拟货币购买其他节点提供的转发服务。文献[13]提出一种基于Reputation的激励机制—IRONMAN，根据节点间的历史交互信息来检测网络中节点的行为，节点通过主动合作来改善自己的信任度。

然而，现有的激励策略通常只检测相遇节点能否作为中继节点，忽视了使用信任机制检测节点间存在的合作自私行为。同时，也没有将信任关系和社会关系结合起来。

2 用户社会和信任关系的评估模型

2.1 网络模型

2.2 信任评估模型

根据节点间的历史交互信息以及可信邻居节点的推荐信息建立信任评估模型，能够及时准确地对节点的可信状态进行分析和判断。可以拒绝自私节点参与到消息转发的过程中，同时避免与网络中低信任度的节点建立合作关系，保证节点之间安全、可靠的通信。

通过周期性观察节点间的交互行为，对节点间的直接信任关系进行估计和判断。同时根据可信邻居节点的推荐信息对节点间的间接信任关系进行估计和判断，因此判断信任关系时综合考虑直接信任关系和间接信任关系。

定义1(直接信任度)：根据节点间历史交互信息所估计的直接信任水平。

用DTi,j(t+Δt)表示t+Δt时刻节点i对节点j的直接信任评估值，其计算公式如下：

(1)

(2)

定义2(信任相似度)：节点i和节点j对共同相遇节点(如共同相遇节点集合NS中节点)信任度的相似程度。

假设节点i和节点j为邻居节点，共同相遇节点集合为NS，具体的计算公式如下：

(3)

其中，NS=[N1,N2,…,Nn]表示节点i和节点j的共同相遇节点集合，采用信任评价向量的方式表示节点i对每一个相遇节点的信任评价情况，表示形式为：TiS=[TiN1,TiN2,…,TiNp,…,TiNn]，其中TiNp(Np∈NS,1≤p≤n)表示当前节点i对节点Np的直接信任度。利用定义2的计算公式，可以得出节点i和每一个邻居节点的相似性，从而得到m个最相似的邻居节点，进而得出定义3。

定义3(间接信任度)：网络中和当前节点具有较高信任相似度的节点所推荐的直接信任度。综合考虑具有较高信任相似度节点的直接信任度，能够可靠、准确地反映出推荐的信任水平。

间接信任度ITi,j的计算公式为：

(4)

其中，M={k1,k2,…,km}表示和节点i最相似的m个邻居节点集；DTk,j表示节点k对节点j的直接信任度。显然，0

定义4(信任度)：包含直接信任度和间接信任度的综合信任水平。

根据定义1、3的计算公式得出节点i对节点j的信任度Ti,j：

Ti,j=αDTi,j+(1-α)ITi,j

(5)

其中，0<α<1,0≤Ti,j≤1。根据实际的网络情况对α进行取值。

根据上述计算，则整个网络的信任关系可抽象成如下n×n的二维矩阵：

对于网络中任一节点i，其储存矩阵T中对应的第i个行向量：存储Ti=(Ti1,Ti2,…,Tin)，该行向量由节点i维护，同时进行周期性更新，并反馈到网络。每一个周期中，节点i需要建立本地信任列表Tlist(i)，用于存放可以信任的其他节点，同时根据交互信息对本地信任列表进行周期性更新。

2.3 社会关系评估模型

机会网络中，如果用户间具有一定的社会关系，则他们之间的联系会更加频繁。社会关系可以反映为用户间具有某些共同的社会特征。因此，共同的社会特征的多少在一定程度上可以反映用户间联系的频繁程度。

由图1可看出，随着共同社会特征个数的增加，相遇频率也随之增加。因此可以将节点的社会属性特征作为中继节点选择的重要依据。

图1 相遇频率和共同特征数的关系

下面给出量化的社会属性特征定义以及节点间联系程度的计算公式。

定义5(社会特征向量)：用于描述节点的社会属性特征，表示如下：

FNi={f1,f2,…,fm}

(6)

其中，FNi表示节点Ni的社会特征向量；fi表示第i种社会属性，网络中共有m种社会属性。

定义6(静态社会特征向量)：静态社会特征向量根据用户的自身信息得到，用于表示用户节点的初始社会特征向量，xi表示属性fi对应的权重大小。

随着网络中节点之间的交互，对节点的静态社会特征向量进行更新，公式如下：

(7)

其中，0≤xi≤1，1≤i≤m；Mi表示节点Ni和具有属性fi的节点的相遇次数；Mtotal表示节点Ni和所有节点的相遇总次数。

定义7(社会相似度)：用于衡量用户间社会属性特征的相似程度，计算公式如下：

(8)

其中，sim(i,j)表示用户节点i和j的社会相似度；Fi表示用户i的社会特征向量。

3 SRTR算法步骤

SRTR算法采用有限消息副本转发策略，依据节点间的交互信息和可信邻居节点的推荐信息建立信任矩阵，根据信任矩阵建立本地信任列表，用于存放可信任的邻居节点，然后根据目的节点对中继节点的社会相似度实现转发决策和分割消息副本数。当前节点Ni如果存在需要转发的消息集M，算法具体步骤如下：

(1)当前周期中，根据信任矩阵T，节点Ni存储信任矩阵T中的行向量Ti=(Ti1,Ti2,…,Tin)。根据系统环境设定信任度阈值Tth，由行向量分别获取节点Ni对其他节点的信任度，将满足信任度阈值条件的节点添加至节点的本地信任列表Tlist(i)，同样，删除本地信任列表中不符合阈值条件的节点。

(2)对于节点Ni携带的消息m∈M，获取消息m的目的节点ND。当节点Ni遇到节点Nj时，如果Nj=ND，则节点Ni将消息直接发送至目的节点。如果节点Nj∈Tlist(i)，则进入步骤3；否则，节点Ni继续携带消息直到遇到目的节点或者本地信任列表Tlist(i)中的节点。

(3)根据节点的社会特征向量分别计算当前节点Ni、相遇节点Nj和目的节点的社会相似度sim(Ni,ND)以及sim(Nj,ND)，如果sim(Nj,ND)>sim(Ni,ND)，则节点Ni需要分割消息m的副本数Ncj，将副本数为Ncj的消息m转发给Nj，更新节点Ni的消息副本数Nci←Nci-Ncj，消息副本数分割计算如下式：

(9)

(4)否则当sim(Nj,ND)≤sim(Ni,ND)，节点Ni继续携带消息直到遇到目的节点或者本地信任列表Tlist(i)中的节点。

4 实 验

4.1 仿真环境设置

文中利用基于Java的机会网络仿真平台ONE[14](opportunistic network environment)进行实验仿真，使用Infocom 2006 trace[15]数据集，源节点和目的节点从85个节点中随机选择。选取数据库中的6个特征[5]，分别是国籍、语言、城市、公司、职业、教育背景等。具体参数设置如表1所示。

表1 仿真环境参数设置

4.2 性能指标

为了验证SRTR算法的性能，选取的指标如下：

(1)消息投递率：网络中成功交付到目的节点的消息数与源节点产生的消息总数的比值。

(2)平均延迟：消息从源节点产生到交付到目的节点所花费时间的平均值。

(3)路由开销：网络中消息副本总数和成功传输到目的节点的消息数的比值。

(4)丢包数目：网络中自私节点所丢弃的消息总数。

4.3 仿真结果分析

实验过程中通过调整自私节点的比率得到不同算法的四个性能指标，用于分析SRTR算法与Epidemic、dLife和IRONMAN算法的性能。

4.3.1 消息投递率

不同自私节点比率下四种算法的消息投递率如图2所示。

图2 消息投递率vs自私节点比率

随着自私节点比率的增加，4种路由算法的投递率都呈下降的趋势。由于没有自私节点检测机制，和SRTR、IRONMAN算法相比，Epidemic和dLife算法的投递率下降得比较迅速。和IRONMAN算法相比，SRTR算法仍然具有较高的消息投递率。IRONMAN算法没有考虑到节点间的信任评估和社会关系，而SRTR算法能够确保具有较高信任水平的节点参与到消息转发的过程中，并且根据社会关系选择中继节点。因此，SRTR算法的表现总体上优于IRONMAN算法。

4.3.2 平均延迟

不同自私节点比率下四种算法的平均延迟如图3所示。

图3 平均延迟vs自私节点比率

随着自私节点比率的增大，4种路由算法的平均转发延时均呈现出上升的趋势。主要是随着自私节点比率的增大，更多的消息长时间等待传输或者被重新传输。由于没有自私节点检测机制，不能避免自私节点转发消息，因此Epidemic路由的平均转发延时增长最快。虽然dLife算法不能检测到自私节点，但是该算法基于社会关系选择中继节点，一定程度上能够避免选择自私节点转发消息，相对而言具有较为稳定的时延。和Epidemic、dLife算法相比，SRTR、IRONMAN算法具有较低的时延，因为这两种算法具有相应的自私节点检测机制。根据之前所述，和IRONMAN算法相比，SRTR算法能够更为准确地检测到自私节点，并且根据社会相似度动态分配消息副本，当自私节点比例超过50%时，SRTR算法的表现优于IRONMAN算法。

4.3.3 路由开销

在不同自私节点比率下四种算法的路由开销如图4所示。

图4 路由开销vs自私节点比率

随着网络中更多的正常节点变为自私节点，Epidemic算法的传输开销呈现增长的趋势，且该算法的路由开销最大。当自私节点比率低于40%时，随着自私节点的增多导致更多的消息副本被丢弃，因此dLife算法的路由开销呈现增长的趋势，该算法根据社会关系选择中继节点，当自私节点比率超过40%时，被选择的中继节点逐渐减少，使得消息被丢弃的速率逐渐下降，传输开销呈现下降的趋势，因此dLife算法的表现优于Epidemic路由。SRTR算法和IRONMAN算法的路由开销呈现下降的趋势，因为这两种算法能够检测到自私节点，IRONMAN算法的路由开销更小，因为该算法借鉴于SAW算法的思想，采用有限消息副本转发的策略[15]。

4.3.4 丢包数目

在不同自私节点比率下四种算法的丢包数目如图5所示。

图5 丢包数目vs自私节点比率

可以看出，相比dLife和Epidemic算法，IRONMAN算法和SRTR算法具有较少的丢包数目，因为dLife算法和Epidemic算法没有自私节点检测机制。和IRONMAN算法相比，SRTR算法能够更为准确地检测到自私节点，相比而言，SRTR算法具有更少的丢包数目。相比Epidemic算法，dLife算法根据社会关系选择下一跳节点，因此该算法的表现优于Epidemic算法。

5 结束语

文中提出一种机会网络中基于社会关系和信任关系的路由算法SRTR，该算法综合考虑直接信任度和间接信任度，根据总体信任度建立节点间的信任矩阵。特别是在获取推荐信息时，通过建立信任相似关系对邻居节点进行信任评估，并以信任相似度作为约束条件来避免自私节点出现谎报推荐信息的可能。建立节点本地信任列表确保具有较高信任水平的节点参与到消息的安全转发过程中。并且结合社会关系，选择本地信任列表中和目的节点社会相似度更大的节点作为转发消息副本的中继节点，并根据社会相似度动态分配消息副本。在确保中继节点可靠的前提下，使得消息沿着社会相似度递增的方向传递，可以避免节点间自私行为的发生，确保消息到达目的节点的最佳路径，提高整个网络的消息投递率，降低网络中消息转发时延，使得消息副本得以高效、可靠的传输。