机会网络中基于社会信任的数据转发算法

袁江涛，张振宇，杨文忠

（新疆大学 信息科学与工程学院，新疆 乌鲁木齐830046）

0 引 言

机会网络不需要源节点和目的节点之间存在完整链路，通过节点移动带来的相遇机会以 “存储－携带－转发”的方式实现节点间通信［1，2］，但在真实网络环境中，节点的内存、能量等资源有限，节点基于自身利益可能会拒绝转发消息而表现出自私行为［3］，严重影响网络服务的可靠性，甚至破坏网络正常运行。

针对机会网络中的自私节点，一些信任转发方法被提出，这些方法在经典的Epidemic［4］、Prophet［5］、Sprayand－Wait［6］等数据转发算法基础上，利用节点的相关信息评价节点信任，找出信任节点作为可靠转发节点。其中，信任的评价方式可以分为基于反馈信息、基于交互信息和基于跳数距离3类。目前，由人携带的移动设备构成的机会网络在社会中得到普遍的应用，如何确保数据转发在此种机会网络中不受自私节点干扰是一个重要问题。

1 相关工作

文献 ［7］在Prophet基础上，引入 “看门狗”机制统计反馈消息数量度量节点信任值，选取合适的节点转发数据，但这种方法在网络规模较大时，对网络资源的消耗过大；文献 ［8］在Spray－and－Wait基础上，每个节点通过历史交互次数评价相遇节点的信任等级，利用信任级别绕过自私节点，但是在自私节点数量较多时，其信任评价的准确度较差；文献 ［9］按照路径上每个节点到目的节点的跳数度量节点信任值，再将数据依次从低信任节点发往高信任节点，该方法虽然可以抵抗自私节点的攻击，但在自私节点较多时，部分自私节点依然可以侥幸获得数据。

当网络设备由人来携带时，节点设备会具备人的社会属性，比如：熟悉度、亲密度等。不同的社会属性可以构成节点的社会信任，反映节点的信任强度［10］。基于这种联系，可引入社会网络思想研究机会网络信任转发问题［11］。文献［12］提出一种基于社会信任的机会网络信任模型，该模型利用网络拓扑结构和跳数距离建立的节点关系和历史交互信息确认的节点友好度来评价节点信任，有效抵抗了女巫攻击。

为了能在具有社会属性的机会网络中避免将数据转发到自私节点，同时克服以往信任转发算法在自私节点较多时，存在转发延迟较高、信任评价不准确等问题。本文在Epidemic的基础上，提出一种基于社会信任的数据转发算法ST－Epidemic（social trust Epidemic），利用Epidemic高转发效率，依据节点接触次数、连接时间、接收次数、转发次数描述机会网络节点的社会属性，构建节点间的信任关系，选取信任节点作为转发节点，避开自私节点对数据转发的干扰。

2 基于社会信任的转发算法

2.1 社会信任的度量

在社会网络中，社会信任是指一定社会成员之间相互认同、信任并进行真诚交往的现象［13］。社会信任可由社会关系决定，而社会关系又是由社会成员的社会属性构成，所以根据不同的社会属性可以构建节点的社会信任，并反映节点间的信任强度［14］。基于这种联系，可引入社会信任的思想解决机会网络信任转发问题。

社会心理学认为信任关系是通过人与人之间的交流建立的［12］。通常相见频率越高，彼此间就越熟悉。在地理位置上距离越近，相互交流的时间越长，亲密度就越高。此外根据人的历史行为可判断其可靠性，如商人间的信任度会随着成功交易次数的增加而提高。

因此通过机会网络节点模仿人的移动方式，完成与其它节点必要的交互，根据节点间的相见频率、交流时间、历史行为构建节点的熟悉度、亲密度、服务度3个社会属性，共同构建节点的社会信任。

2.1.1 熟悉度

机会网络中每个节点的地位都是相互平等的，随着节点的移动，节点会接触若干不同的节点，并且与不同节点的接触频率各不相同。在转发数据的过程中，可以选取较熟悉的节点作为转发节点，节点熟悉度的定义如下

2.1.2 亲密度

一般网络中可能存在不同节点与某一节点熟悉度相近情况，此时熟悉度不能全面衡量节点的社会信任，这主要有两个方面原因，一方面是实际场景中存在的自私节点在不停地移动，自私节点可能与正常节点具有较高的接触频率，自私节点会依此骗取正常节点的信任；另一方面，在数据转发过程中要保证数据有足够的时间发送到下一跳节点，只有节点之间连接时间越长，才能保证转发数据的完整性。

所以根据社会网络熟人圈思想［11］，在节点的接触频率基础上，同时考虑节点间的连接时间，可以更加准确地描述节点的社会信任。所以节点亲密度的定义如下

2.1.3 服务度

由于正常节点能帮助其它节点及时转发数据，自私节点只能接收数据不转发数据，网络中节点可通过交换各自记录的数据接收和转发次数衡量对方的服务度。所以通过服务度不仅可以反映节点的转发可靠性，而且能有效地区分出自私节点和正常节点。服务度的定义如下

式中：servi，j——节点j对节点i 的服务程度，且servi，j∈［0，1］，trani，j——节点j帮助节点i完成的数据转发次数，recei，j——节点j接收节点i的数据次数，此处节点j接收次数recei，j必然大于或等于节点转发次数trani，j。

2.1.4 信任计算

由于社会信任是通过综合考虑不同社会属性得出，所以社会信任的计算采取加权求和的方式，具体表示为

式中：Ti，j——节点j对节点i的社会信任，α、β、γ——熟悉度、亲密度、服务度在社会信任中的权重，α，β，γ ∈（0，1］且α＋β＋γ＝1。

考虑到节点的社会信任是从3个不同的社会属性角度进行描述，共同构成节点社会信任的基础，权值的具体分配如下

为了体现信任评价的主观性［11］，在确定3个权重系数的过程中，首先给定γ，因为在3个社会属性中，服务度不仅描述了节点的社会属性，而且能逐渐区分出自私节点和正常节点，服务度对社会信任的贡献最大。其次，节点间的接触频率和连接时间各不相同，在不同的情况下节点会偏重不同的社会属性度量与其它节点的信任强度。所以利用不同节点对熟悉度和亲密度的偏重程度，由节点的熟悉度和亲密度确定α和β，如式 （5）、式 （6）所示。

在节点i计算出节点j 的社会信任Ti，j后，规定θ为信任转发阈值，当Ti，j≥θ时，认为该节点为信任节点并向该节点发送数据；当Ti，j≤θ时，认为该节点为自私节点。拒绝向该节点发送数据。

2.2 基于社会信任的转发过程

ST－Epidemic是通过判断节点的社会信任值进行数据转发。若节点i首次向节点j 转发数据，则根据节点的初始信任值直接向节点j 转发数据，若非首次转发，则通过fami，j、intii，j、servi，j计算节点j 对源节点i 的社会信任Ti，j，如果Ti，j达到信任转发阈值，则向节点j转发数据，反之，则拒绝向节点j转发数据，具体如算法1所示。

算法1：ST－Epidemic数据转发算法

输入：fami，j、intii，j、servi，j、Ti，j←θ、trani，j←0

输出：信任节点集合TR［j］节点

上述算法过程中设置节点的初始信任值θ是为了更快地促使节点建立信任关系，为后续数据转发提供更好的信任基础。比如初次向某个节点转发数据，若该节点是正常节点，它会继续向其它节点转发数据，若该节点是自私节点，它不会向其它节点转发任何数据，通过这种试探性的方法可能会丢失小部分数据包，但可以帮助节点更快地分辨出正常节点和自私节点，所以设置初始信任值为θ是有必要的。

2.3 算法复杂度分析

从上述转发算法流程看，整个算法的计算复杂度取决于相遇节点的数量、待转发的数据包数量以及信任转发阈值θ。场景中节点数量为n，待转发的最大数据包数量为m，信任转发阈值θ∈（0，1）。如果θ设定较高，则会提高相遇节点的信任要求，使得数据转发次数下降、转发延迟过高，降低算法效率。如果θ设定较低，则会提高数据的转发次数，但也会提高自私节点对数据转发的影响。因此，算法最坏的情况为某一节点与其它n－1个节点相遇且所有相遇节点的信任都满足θ，此时算法的计算复杂度为O（nm）。最好的情况为相遇节点的信任都不满足θ，此时算法的计算复杂度为O（n）。考虑到现实网络中的情况，该算法的计算复杂度介于O（n）和O（nm）之间。

3 实验仿真

本文利用仿真工具ONE 1.4.1［15］设计的场景对提出的转发算法进行评估。节点移动方式为ShortestPathMap－BasedMovement（SPMBM），具体仿真环境参数设置见表1。

表1 实验仿真环境

为了考察ST－Epidemic数据转发算法的优劣，本文从传输成功率和平均延迟时间两个指标进行衡量。实验分为两组，分别对比在不同自私节点比例时，ST－Epidemic、Epi－demic、Prophet、Spray－and－Waits4种转发方式的传输成功率和平均延迟时间，同时给出实验仿真结果，并分析其原因。

3.1 传输成功率

图1和图2分别展示了在30%和70%的自私节点比例情况下4种转发方式的传输成功率。

图1 传输成功率

图2 传输成功率

实验初期，ST－Epidemic 的传输成功率与Epidemic、Prophet、Spray－and－Wait转发方式相近，但随着节点交互次数增多，ST－Epidemic的传输成功率逐渐高于Epidemic、Prophet、Spray－and－Wait这3 种转发方式。由于实验初期节点间的信任关系还处在建立过程中，可能存在正常节点被暂时误判为自私节点的情况，所以ST－Epidemic的传输成功率增长趋势较缓。而在实验后期，一方面是由于正常节点之间逐渐建立起良好的信任关系，数据在信任节点之间被安全地转发；另一方面由于自私节点拒绝帮助其它节点转发数据，自私节点的服务度较低，致使自私节点的社会信任值也较低，正常节点通过信任判断逐渐避开向自私节点转发数据，从而使ST－Epidemic的传输成功率快速增长。

图3展示了ST－Epidemic、Epidemic、Prophet、Sprayand－Wait这4种转发方式的在不同自私节点比例的情况下的传输成功率。随着自私节点比例增大，ST－Epidemic、Epidemic、Prophet、Spray－and－Wait这4 种转发方式的传输成功率都在下降，而ST－Epidemic的下降趋势较缓。虽然在自私节点比例小于30% 时，Epidemic、Prophet、Spray－and－Wait这3种转发方式的传输成功率高于ST－Epi－demic转发方式，但是在自私节点比例大于30%时，STEpidemic转发方式的传输成功率却高于其它3种转发方式。主要原因是自私节点对Epidemic、Prophet、Spray－and－Wait的转发过程造成了严重的影响，大量的转发数据被自私节点截获并删除，导致数据的传输成功率快速下降。而ST－Epidemic在不同自私节点比例的情况下，通过已建立的信任关系确保了数据在信任节点之间有效地转发，减缓了传输成功率的下降趋势。

图3 传输成功率

3.2 平均延迟时间

图4和图5展示了在30%和70%的自私节点比例情况下4种转发方式的平均延迟时间。

图4 平均延迟时间

图5 平均延迟时间

实验初期ST－Epidemic的平均延迟时间基本介于Epidemic和Spray－and－Wait之间，而在实验后期ST－Epidemic的平均延迟时间短于其它3种转发方式，这是由于在实验初期存在正常节点被误判为自私节点的情况，造成ST－Epidemic的平均延迟时间与其它转发方式相近，实验后期由于节点之间的信任关系已经开始建立，正常节点逐渐避开向自私节点转发数据，数据被自私节点干扰的情况减少，所以平均延迟时间得到较大地缩短。

图6展示了ST－Epidemic、Epidemic、Prophet、Sprayand－Wait这4种转发方式的在不同自私节点比例的情况下的平均延迟时间。随着自私节点比例的不断增加，ST－Epidemic、Epidemic、Prophet、Spray－and－Wait这4 种转发方式的平均延迟时间都在增加，但ST－Epidemic的上升趋势较缓。在自私节点比例小于30%时，ST－Epidemic的平均延迟时间略长于Epidemic和Spray－and－Wait转发方式。而在自私节点比例大于30%时，ST－Epidemic的平均延迟时间短于其它3种转发方式的平均延迟时间。这是因为ST－Epidemic建立的信任关系有效阻止了自私节点的干扰，减缓了平均延迟时间的上升，而Epidemic、Prophet、Spray－and－Wait在数据转发过程中被自私节点严重影响，降低了数据发送到目的节点的概率，从而使平均延迟时间迅速增加。

图6 平均延迟时间

4 结束语

本文从社会学的角度出发，针对由人携带移动设备的机会网络，提出一种基于社会信任的转发策略。利用节点的接触次数、连接时间、接收次数、转发次数衡量了节点的社会信任，一方面完善了机会网络节点的信任评价过程，另一方面有效解决了自私节点对数据转发的影响。仿真结果表明，与经典转发方式对比，所提出的转发方式在自私节点较多情况下能保证数据的高效传递。

［1］Boldrini C，Conti M，Passarella A.Exploiting users’social relations to forward data in opportunistic networks：The HiBOp solution ［J］.Pervasive and Mobile Computing，2008，4 （5）：633－657.

［2］Liu L，Jing Y.A survey on social－based routing and forwar－ding protocols in opportunistic networks［C］／／IEEE 12th International Conference on Computer and Information Technology，2012：635－639.

［3］Zhang S，Qiu H，Liu Y，et al.Evolutionary reputation model for node selfishness resistance in opportunistic networks ［J］.Concurrency and Computation：Practice and Experience，2012，24 （11）：1261－1269.

［4］Ramanathan R，Hansen R，Basu P，et al.Prioritized epidemic routing for opportunistic networks ［C］／／Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking.ACM，2007：62－66.

［5］Huang T K，Lee C K，Chen L J.Prophet＋：An adaptive prophet－based routing protocol for opportunistic network［C］／／24th IEEE International Conference on Advanced Information Networking and Applications，2010：112－119.

［6］Huang W，Zhang S，Zhou W.Spray and wait routing based on position prediction in opportunistic networks ［C］／／3rd International Conference on Computer Research and Development.IEEE，2011：232－236.

［7］Li N，Das S K.A trust－based framework for data forwarding in opportunistic networks ［J］.Ad Hoc Networks，2013，11（4）：1497－1509.

［8］Al－Hinai A，Zhang H，Chen Y，et al.TB－SnW：Trust－based spray－and－wait routing for delay－tolerant networks ［J］.The Journal of Supercomputing，2014，69 （2）：1－17.

［9］Gupta S，Dhurandher S K，Woungang I，et al.Trust－based Security Protocol against blackhole attacks in opportunistic networks［C］／／IEEE 9th International Conference on Wireless and Mobile Computing， Networking and Communications，2013：724－729.

［10］Conti M，Kumar M.Opportunities in opportunistic computing ［J］.Computer，2010，43 （1）：42－50.

［11］Conti M，Giordano S，May M，et al.From opportunistic networks to opportunistic computing ［J］.Communications Magazine，IEEE，2010，48 （9）：126－139.

［12］Trifunovic S，Legendre F，Anastasiades C.Social trust in opportunistic networks ［C］／／INFOCOM IEEE Conference on Computer Communications Workshops，2010：1－6.

［13］Grabner－Kruter S，Bitter S.Trust in online social networks：A multifaceted perspective［J］.Forum for Social Economics，2013，44 （1）：1－21.

［14］Becker C，Schlinga S，Fischer S.Trustful data forwarding in social opportunistic networks ［C］／／Ubiquitous Intelligence and Computing，IEEE 10th International Conference on and 10th International Conference on Autonomic and Trusted Computing，2013：430－437.

［15］Keranen A.Opportunistic network environment simulator［EB／OL］.［2008－05－29］.http：／／www.netlab.tkk.fi／tutkimus／dtn／theone.