基于社会关系的簇建立与更新方法及基于簇的路由方法

摘要

本发明公开了一种基于信息熵的移动机会网络节点社会关系度量方法，选择影响节点之间社会关系的特征作为社会关系评价指标，利用信息熵来衡量不同评价指标对节点之间社会关系强度的影响，并以该影响作为权重，通过对各个评价指标值进行加权求和得到节点间社会关系强度。本发明还公开了一种簇建立与更新及路由方法，以及基于簇的路由方法，每个节点选择与自己有紧密社会关系的节点形成一个本地簇，充分利用簇成员间的紧密社会关系来进行信息的交换以及消息的转发。本发明能够准确度量节点间的社会关系，利用计算得到的节点间社会关系进行路由可以有效提高网络性能。

权利要求

1.一种基于社会关系的簇建立与更新方法，其特征在于，包括以下步骤：

1)每个节点vk各建立一个历史信息表Nk、本地簇Ck及删除链表Dk；其中历史信息表Nk用于记录节点vk在最近T时间内相遇的节点，以及其与各节点之间各个评价指标的值；本地簇Ck用于存储与节点vk的社会关系强度大于阈值ω的节点以及相应的社会关系强度值，删除链表Dk用于存储等待观察是否要从本地簇Ck中删除的节点；最初Nk和Dk均为一个空的表格，Ck为空集；

2)当节点vk和节点vj相遇，节点vk先更新其历史信息表，再计算与vj的社会关系强度Rj，计算两个节点的社会关系强度的方法为：选择影响节点之间社会关系的特征作为社会关系评价指标，利用信息熵来衡量不同评价指标对节点之间社会关系强度的影响，并以该影响作为权重，通过对各个评价指标值进行加权求和得到节点间社会关系强度；

设Rj(t)是节点vk在当前时刻计算得到的Rj值，节点vk根据Rj(t)和ω的不同情况，进行簇更新：情况1：当Rj(t)大于ω时，节点vk判断节点vj是否为Ck的成员，若不是，则将节点vj加入到Ck中；否则先将Ck中存储的与节点vk的社会关系强度Rj更新为设Rj(t)，再判断节点vj是否在删除链表Dk中，若是则将节点vj从Dk中剔除；

情况2：当Rj(t)等于或小于ω时，节点vk判断节点vj是否为Ck的成员，若不是，则不进行任何操作；否则判断节点vj是否在删除链表Dk中，若在则将节点vj从Ck和Dk中剔除，若不在则节点vk将节点vj加入删除链表Dk中；

3)本地簇Ck中存储的社会关系强度Rj每隔一段时间就进行一定的自衰减，若本地簇中存储的社会关系强度Rj在T时间段内没有更新且Rj自衰减到等于或小于ω，节点vk将节点vj加入到删除链表Dk中；

计算两个节点的社会关系强度的方法具体为：

定义移动机会网络中的节点集合为V＝{vj|j＝1，2，...，N}，节点社会关系的评价指标集合为A＝{ai|i＝1，2，...，M}，其中N为移动机会网络中的节点个数，M为节点社会关系的评价指标个数；对于每个节点，分别根据以下步骤计算其与其它节点的社会关系强度：步骤1：统计原始数据

根据自己与其它节点的相遇历史信息，得到与其它节点之间不同评价指标的值，用sij表示当前节点与节点vj之间评价指标ai的值，i＝1，2，...，M，j＝1，2，...，N；

步骤2：对每个指标对应的原始数据分别进行处理；

对评价指标ai，首先对sij，j＝1，2，...，N进行归一化处理，公式为：其中，mini{sij}＝min{sij|j＝1，2，...，N}，maxi{sij}＝max{sij|j＝1，2，...，N}，s′ij表示对sij进行归一化处理之后的取值；

然后，计算s′ij在评价指标ai对应的所有取值之和中的占比Pij：步骤3：分别计算每个评价指标的熵值：

对评价指标ai，其熵值Hi计算公式为：

其中，h为系数，Hi≥0，ln为自然对数，且设定如果Pij＝0，那么Pij*lnPij＝0；

步骤4：分别计算每个评价指标的权重：

对评价指标ai，其权重Qi计算公式为：

步骤5：计算节点间社会关系强度：

当前节点与节点vj的社会关系强度Rj计算公式为：

Rj的值越大，两者的社会关系越紧密。

2.根据权利要求1所述的方法，其特征在于，所述步骤3中，令 使得Hi∈[0，1]。

3.根据权利要求1所述的方法，其特征在于，所述ω＝0.4。

4.一种基于簇的路由方法，其特征在于，路由过程包括两个阶段，一个是信息交换，另一个是消息转发；

A.信息交换

当两个节点相遇，首先会向彼此发送自己的节点标识符及历史信息表中的相遇信息；

相遇信息到达后，节点根据彼此的相遇信息，统计和计算两个节点之间每个评价指标的值，更新历史信息表，并采用权利要求1所述的方法建立/更新本地簇；

B.消息转发

设源节点vk遇到节点vj；若节点vj是消息的目的节点，节点vk将消息转发给节点vj，同时从发送队列中删除此消息；否则，节点vk的消息转发过程有以下两种情况：

1)簇中消息转发

如果消息的目的节点在节点vk的本地簇中，且节点vj是vk的本地簇成员，则节点vk向节点vj转发一个消息副本；否则，节点vk不向vj转发消息；

2)簇间消息转发

如果消息的目的节点不在节点vk的本地簇中，节点vk会向节点vj发送一个请求包，判断目的节点是否在节点vj的本地簇中；当节点vj收到请求包后，根据请求包的信息检查本地簇，然后向节点vk回复一个响应包，通知节点vk其本地簇中是否存在目的节点；如果节点vk收到响应包且目的节点是节点vj的本地簇成员，节点vk转发一个消息副本给节点vj；否则，节点vk不向节点vj转发消息。

说明书

基于社会关系的簇建立与更新方法及基于簇的路由方法

技术领域

[0001] 本发明涉及一种基于信息熵的移动机会网络节点社会关系度量、簇建立与更新及路由方法。

背景技术

[0002] 移动机会网络是一种新型的移动自组织网络，以人为中心，利用各类传感器组成感知网络，实时感知人们生产生活。近年来移动机会网络得到了广泛应用，并在数据收集与数据共享上发挥了越来越重要的作用。移动机会网络采用“存储-携带-转发”的数据传输策略，节点首先存储准备发送的数据，然后携带数据移动直至遇到合适的中继节点后进行数据传输。在移动机会网络中，消息的传输过程是动态进行的，即网络中任何节点都可能作为中继节点，帮助消息转发。不同于传统自组织网络中相对稳定的网络拓扑环境，连接链路的时断时续无法保证端到端的连通路径的存在，这就使得传统路由算法中先建立路由后传输的工作模式无法在移动机会网络中有效运行。因此，传统自组织网络的路由算法不再适用于移动机会网络，路由算法成为移动机会网络的一个研究热点。

[0003] 移动机会网络中消息的传输依赖于节点之间的移动。移动机会网络中，节点社会关系对路由性能有重要影响。网络中的节点由人随身携带的可移动设备组成，因此其接触行为会表现出一定的社会性。利用节点社会关系进行路由算法设计可以有效帮助消息转发，同时在消息传输过程中避免冗余消息的产生，有利于网络性能的提高。已有一些研究工作[1]表明节点间的社会关系会影响节点的相遇事件及相遇持续时间等情况，这些研究工作使用节点的社会属性设计数据转发机制并且取得了良好的效果。

[0004] 目前大多数学者利用节点的接触次数、节点两次接触的间隔时间，接触持续时间等指标来度量节点间的社会关系。当两个节点接触频繁，则认为这两个节点有紧密的社会关系。

[0005] 一些学者通过历史数据去预测节点相遇的概率，并实现对路由算法的优化；一些学者通过节点相遇的频次去推测节点间社会关系的强弱，并以社会关系形成节点簇，构造基于簇的路由机制。文献[2]设计了一种基于朋友关系的转发算法。文中认为具有较高接触次数、较长接触时间的节点是朋友关系，并以此设计路由算法。文献[3]研究了用户社交图路由算法，认为朋友关系是一种高稳定性的社会关系，可帮助消息转发。

[0006] 在Bubble[4]中，节点的社会地位由全局中心度和局部中心度两个指标评价。在设计转发机制时，考虑节点在本社区的地位及所处社区在全局的地位。当数据没有被传输到目的节点所处社区前，按照节点的社会地位位序进行转发，即消息向拥有更高社会地位的节点转发。在目的节点所处社区中传输目的节点时，选择该社区中社社会地位高的节点转发，以此降低网络路由开销。文献[5]由中心度和相似度共同度量节点的SimBet值，SimBet值高的节点有更高的社会地位，消息转发时被优先考虑。

[0007] 文献[6]中，提出了社会关系机会路由算法SROR，使用节点的社会关系和概况作为路由过程中选择最优转发节点的关键指标，优化路由性能。文献[7]中的动态社会关系路由算法，通过节点的物理社会关系及其相遇概率来评估网络中的社会关系，然后动态更新和计算节点间的社会关系矩阵。根据社会关系矩阵，消息的源节点选择合适的成员节点作为中继节点，将消息传递到目的节点，最大限度避免网络中自私节点丢弃消息的可能性。文献[8]中，发现了一个用于移动机会网络中路由和转发的上下文感知框架。该框架是通用的，并且能够承载各种风格的上下文感知路由。学者提出了一种特定的协议HiBOp，利用框架通过上下文信息学习、用户行为表现以及他们之间的社会关系等信息来推动转发过程。

[0008] 文献[9]利用节点的地理位置信息和社会关系为辅助信息，提出一种基于社会关系的机会网络低延迟多副本路由算法。选择与目的节点有密切关系的节点和与目的节点地理位置接近的节点作为中继节点，帮助消息转发。文献[10]中通过分析网络中移动节点的实时数据，总结并提出影响这些移动节点之间社会关系的因素。然后从多个角度对这些因素的复杂性和动态性进行推断和评估，从这些因素中计算出每个传感器节点之间的社会关系值。最后，根据社会关系的价值，梳理邻居的网络拓扑信息，选择最佳的下一跳中继节点进行信息路由。

[0009] 在基于社会关系的路由机制中，关键问题是发现并准确度量节点间的社会关系，这个问题依赖于对节点历史相遇数据的分析。然而，已有研究工作在挖掘节点间社会关系问题上仍存在未周全考虑的地方。节点间社会关系与节点之间的很多特征有联系，如节点间的相遇次数、相遇持续时间(从建立通信连接到断开通信之间经过的时间，实际上就是通信时间)、节点之间转发消息的情况、共同的好友数量、共同的兴趣、节点之间的运行轨迹重合度等等，这些特征都可作为节点间社会关系的评价指标。已有的研究工作往往考虑了一个或几个指标。同时，不同特征对于节点间社会关系的影响可能不同，且在机会网络中，由于节点的移动和相遇具有不确定性，造成了节点之间联系(社会关系)的不确定性，各种不同特征对于节点间社会关系的影响也是不确定的，目前还没有一种方法能够准确评估各种不同特征对于节点间社会关系的影响。因此，现有方法在社会关系度量准确性上仍需大力提高。

[0010] 考虑到现有技术中存在的技术问题，有必要设计一种能够发现并准确度量节点间的社会关系的方法，以及基于该社会关系的路由方法。

发明内容

[0011] 本发明所解决的技术问题是，针对现有技术的不足，提供一种基于信息熵的移动机会网络节点社会关系度量与路由方法，能够准确度量节点间的社会关系，利用计算得到的节点间社会关系进行路由可以有效提高网络性能。

[0012] 本发明所提供的技术方案为：

[0013] 一种基于信息熵的移动机会网络节点社会关系度量方法，选择影响节点之间社会关系的特征(如节点间的相遇次数、相遇持续时间、节点之间转发消息的情况、共同的好友数量、共同的兴趣、节点之间的运行轨迹重合度等等)作为社会关系评价指标，利用信息熵来衡量不同评价指标对节点之间社会关系强度的影响，并以该影响作为权重，通过加权求和得到节点间社会关系强度。具体包括以下5个步骤：

[0014] 步骤1：统计原始数据

[0015] 设在移动机会网络中有N个节点，M个节点社会关系的评价指标。则根据历史信息，可以得到节点之间的不同评价指标的值。定义节点社会关系的评价指标集合为A＝{ai|i＝1,2,…,M}，评价机会网络中节点的集合为V＝{vj|j＝1,2,…,N}。每个节点根据自己与其它节点的相遇历史信息，得到与其它节点之间不同评价指标的值，如表1所示，表1中的值sij表示当前节点与节点vj之间评价指标ai的值。

[0016] 表1节点vx中与其他节点之间的评价指标值

[0017]

[0018] 步骤2：对原始数据进行处理

[0019] 对于各个社会关系评估指标来说，使用的单位可能不一样，例如相遇次数和平均相遇时间，如果直接将这些信息进行计算，得到的结果差异性可能会很大。所以，在进行计算之前需要对这些数据进行预处理，保证每个评价指标有相同的取值范围。具体的处理方法如公式1所示。

[0020]

[0021] 其中，mini{sij}表示表1中指标ai对应行元素的最小值，即min{sij|j＝1，2，...，N}，maxi{sij}表示表1中指标ai对应行元素的最大值，即max{sij|j＝1，2，...，N}，s′ij表示对sij进行归一化处理之后的取值，s′ij∈[0，1]。数据预处理后，可计算出当前节点与节点vj之间评价指标ai的值在评价指标ai对应的所有取值之和中的占比Pij：

[0022]

[0023] 步骤3：计算每个评价指标的熵值Hi：

[0024] 根据香农的信息论中熵的定义，可以根据Pij得到每个评价指标的熵值Hi：

[0025]

[0026] 其中，Hi≥0，ln为自然对数；设定如果Pij＝0，那么Pij*lnPij＝0。对于某一个指标ai来说，如果s′i1＝s′i2＝…＝s′iN，那么Hi＝hlnN最大。若令 那么Hi∈[0，1]。如果某个社会关系评价指标ai，各元素值差异性越大，那么Hi越小，则该指标所蕴含的信息量越大，对于节点间社会关系的度量就有越大的影响。

[0027] 步骤4：计算各评价指标的权重：

[0028] 得到了每个评价指标的熵值后，则可以计算对应的每个评价指标的权重。对评价指标ai，其权重Qi为式(4)。

[0029]

[0030] 因为Hi越小，1-Hi越大，Qi也越大，对社会关系值的影响越大。

[0031] 步骤5：计算节点间社会关系强度：

[0032] 对当前节点和节点vj，由公式1-4可得到各个评估指标值及其权重，则当前节点与节点vj的社会关系强度Rj如公式5所示。

[0033]

[0034] Rj表示当前节点与节点vj的社会关系强度，Rj的值越大，两者的社会关系越紧密。

[0035] 基于社会关系的路由方法

[0036] 通过基于信息熵对节点间社会关系的有效度量，本发明还提出了一种移动机会网络中基于社会关系的路由(为区分于其他基于社会关系的路由算法和和基于簇的路由算法，将本发明简称为ICR，即Information entropy based Clustering Routing)，包括簇的建立与更新和基于簇的路由；

[0037] (1)簇的建立与更新

[0038] 在ICR方法中，每个节点有一个历史信息表，记录着在最近T时间内相遇的节点以及相应的社会关系评价指标的历史信息。根据历史信息表，节点可以按上述基于信息熵的计算方法计算出与其它节点的社会关系强度。社会关系的度量完成后，每个节点选择与自己有紧密社会关系的节点进入本地簇中。本地簇会被动态地更新以控制其大小及保证簇中的节点始终是与本节点拥有紧密社会关系。在簇更新时，节点维护一个删除链表，其中存储着等待观察是否从本地簇中删除的节点。对于节点vk，Nk、Ck和Dk分别是它的历史信息表、本地簇及删除链表。

[0039] 最初，节点的相关表都是空的。当两个节点相遇，它们更新彼此的历史信息表。交换彼此历史信息表中存储的相遇信息后，节点更新两个节点之间的各个评价指标的初始值。然后，根据公式1-5计算彼此间的社会关系强度。

[0040] 当节点vk和节点vj相遇，设Rj(t)是节点vk在t时刻根据上述公式计算得到的与vj的社会关系强度，参数ω是成为本地簇成员的社会关系强度阈值。根据Rj(t)和ω的不同情况，簇的建立和更新如下所示：

[0041] 情况1：当Rj(t)大于ω且节点vj不是节点vk的本地簇成员时，节点vj将加入到节点vk的本地簇Ck中；否则，如果节点vj是Ck的成员，则将Ck中存储的与节点vk的社会关系强度Rj更新为设Rj(t)，并判断节点vj是否在删除链表Dk中，若在则节点vj将被从Dk中剔除，避免vj被从本地簇中删除；

[0042] 情况2：当Rj(t)等于或小于ω且节点vj不是节点vk的本地簇成员时，节点vk将不进行任何操作；否则，如果节点vj是Ck的成员并在删除链表Dk中，节点vj将被从Ck、Dk中剔除；然而，如果节点vj没有在删除链表Dk中，vj将被加入删除链表Dk，视未来情况再确定是否从本地簇中删除；

[0043] 节点的本地簇会被动态地更新，如果相关信息发生变化，上述过程会被执行。簇更新的过程如图1所示。

[0044] 如果当前的社会关系强度计算结果Rj(t)＞ω，则Rj(t)会被更新存储在本地簇中。设定T时间段内社会关系强度自衰减的次数n和每次的衰减值θ；在下一次更新前，本地簇中存储的社会关系强度每隔一段时间(T/n)会被减少一定值(自衰减θ)，这样有助于删除掉本地簇中过时的节点，以控制簇的大小，保证节点与其簇成员之间紧密的社会关系。如上所述，时间T是节点相遇信息收集持续时间，因此如果没有信息表示一个簇成员在这期间是活跃的，则节点将会观察是否将该簇成员从其本地簇中删除。如果本地簇中存储的社会关系强度Rj在T时间段内没有更新且Rj自衰减到等于或小于ω，则vj将被加入到节点vk的删除链表中，等待观察是否从本地簇中删除。

[0045] (2)基于簇的路由算法设计

[0046] 如上所述，节点选择与自己有紧密社会关系的节点形成一个本地簇，充分利用簇成员间的紧密社会关系可以帮助提高消息转发成功率，减少路由开销。在本文中，当两个节点相遇，只有目的节点在相遇节点的本地簇中时才会进行消息传输。路由过程包括两个阶段，一个是信息交换，另一个是消息转发。

[0047] A.信息交换

[0048] 当两个节点相遇，首先会向彼此发送一个“hello”报文，得到彼此的节点标识符及历史信息表中的相遇信息。相遇信息到达后，节点根据彼此的相遇信息，统计和计算两个节点之间每个评价指标的值，更新历史信息表，计算两个节点间的社会关系强度，然后建立和更新本地簇。

[0049] B.消息转发

[0050] 设源节点vk遇到节点vj；若节点vj是消息的目的节点，节点vk将消息转发给节点vj，同时从发送队列中删除此消息；否则，节点vk的消息转发过程有以下两种情况：

[0051] 1)簇中消息转发

[0052] 如果消息的目的节点在节点vk的本地簇中，且节点vj是vk的本地簇成员，则节点vk向节点vj转发一个消息副本；否则，节点vk不向vj转发消息。

[0053] 2)簇间消息转发

[0054] 如果消息的目的节点不在节点vk的本地簇中，节点vk会向节点vj发送一个请求包(“Request”包)，判断目的节点是否在节点vj的本地簇中；当节点vj收到请求包后，根据请求包的信息检查本地簇，然后向节点vk回复一个响应包(“Response”包)，通知节点vk其本地簇中是否存在目的节点；如果节点vk收到响应包且目的节点是节点vj的本地簇成员，节点vk转发一个消息副本给节点vj；否则，节点vk不向节点vj转发消息。

[0055] 消息可以在节点vk缓存中存储时间的长短取决于节点vk缓存的大小。在这段时间内，如果节点vk遇到符合上述规则的转发目标，则会安排发送消息。否则，消息将根据缓存管理算法从节点vk的缓存被删除。如果消息的目的节点不是本地簇成员，则存在消息无法转发的可能性。此时，较大的缓存将有助于消息转发。

[0056] 有益效果：

[0057] 在香农信息论中，信息是对事物运动状态或者存在方式的不确定性的描述，而某个信息的不确定性的大小定义为自信息，也就是该信息的信息量[11]，信息熵则是某个信息所有可能的平均不确定性。在机会网络中，由于节点的移动和相遇具有不确定性，造成了节点之间联系(社会关系)的不确定性。节点之间的社会关系越亲密，则不确定性越低，信息量越小。为此，发明考虑所有相关的节点社会关系评价指标，为了更为准确的得到不同评价指标的影响权重，利用信息熵来计算各个评价指标的权重，并据此计算节点间社会关系强度，然后根据节点社会关系强度来建立簇，设计基于簇的路由策略。与其他社会关系路由机制进行了实验比较，实验结果表明，与其他算法相比，本文提出的算法具有较高的消息传递成功率，并且在传输延迟和平均跳数方面也有很好的表现，验证了本发明所提基于信息熵的社会关系度量的有效性和准确性。

附图说明

[0058] 图1本发明实施例簇更新过程示意图；

[0059] 图2为实验参数对路由性能影响；其中图2(a)为ω对数据转发成功率的影响，图2(b)为ω对传输延迟的影响，图2(c)为ω对路由开销比率的影响，图2(d)为n对路由开销比率的影响。

[0060] 图3为各算法在四个数据集下的数据成功转发率对比图；其中图3(a)为各算法在Infocom5数据集下的数据成功转发率对比图，图3(b)为各算法在Infocom6数据集下的数据成功转发率对比图，图3(c)为各算法在Cambridge数据集下的数据成功转发率对比图，图3(d)为各算法在Intel数据集下的数据成功转发率对比图；

[0061] 图4为各算法在四个数据集下的传输延时对比图；其中图4(a)为各算法在Infocom5数据集下的传输延时对比图，图4(b)为各算法在Infocom6数据集下的传输延时对比图，图4(c)为各算法在Cambridge数据集下的传输延时对比图，图4(d)为各算法在Intel数据集下的传输延时对比图；

[0062] 图5为各算法在四个数据集下的路由开销比率对比图；其中图5(a)为各算法在Infocom5数据集下的路由开销比率对比图，图5(b)为各算法在Infocom6数据集下的路由开销比率对比图，图5(c)为各算法在Cambridge数据集下的路由开销比率对比图，图5(d)为各算法在Intel数据集下的路由开销比率对比图；

具体实施方式

[0063] 以下结合附图和具体实施方式对本发明进行进一步具体说明。

[0064] 本发明综合考虑机会网络中影响节点之间社会关系的不同评价指标，提出评价指标信息熵计算方法，并以评价指标信息熵为权重计算节点之间的社会关系强度，提出了一种基于社会关系的簇建立与更新方法，以及基于簇的路由方法。在该方法中，每个节点有一个历史信息表，记录着在最近一段时间内相遇的节点以及相应的各种社会关系评价指标的历史信息。根据历史信息表，节点可以根据信息熵计算出与其它节点的社会关系强度。然后，每个节点选择与自己有紧密社会关系的节点形成一个本地簇，充分利用簇成员间的紧密社会关系来进行信息的交换以及消息的转发。

[0065] 本实施例以实际的机会网络中的数据为例说明节点社会关系强度计算过程。

[0066] (1)统计原始数据

[0067] 在例子中，我们考虑9个节点和5个评价指标的情况(如表2所示)。一般来说，机会网络中节点会保存移动过程中所遇到节点的信息，包括相遇时间、相遇次数、转发消息次数等，并且会随着节点的移动和节点之间的相遇不断的更新。当需要计算两个节点的关系时，可以从节点的历史信息表中统计出这些信息。假设当前节点为v9，需要统计节点v9和其他节点之间的社会关系强度，则根据机会网络中节点v9的历史信息可以统计出表3的数据。

[0068] 表2社会关系评价指标

[0069]a1 相遇次数
a2 平均相遇持续时间
a3 转发消息次数
a4 共同好友个数
a5 共同兴趣个数

[0070] 表3 v9节点与其他节点之间的评价指标值

[0071]

[0072] (2)对原始数据进行处理

[0073] 根据公式1对表3的数据进行处理之后得到归一化数据如表4所示。

[0074] 表4归一化处理后的新表

[0075]

[0076] (3)计算每个标准的比重Pij

[0077] 根据公式2，可以计算出各元素值在对应的评价指标中的占比，结果如表5所示。

[0078] 表5各元素值在对应的评价指标中的占比

[0079]

[0080]

[0081] (4)计算每个评价指标的熵值Hk

[0082] 根据公式3和表5中的数据，可以计算出每个评价指标的熵值，具体的值如表6所示。这里的熵值代表每个评价指标所贡献的平均信息量的大小，根据香农信息论中的论述可知，此处的熵值越小，对应的评价指标所提供的信息量越大。

[0083] 表6每个评价指标的熵值

[0084]

[0085] (5)计算每个指标的权重由公式4可得各指标权重值如表7所示。

[0086] 表7每个评价指标的权重

[0087]  H 1-H Q
a1 0.453364 0.546636 0.238872
a2 0.454025 0.545975 0.238583
a3 0.427482 0.572518 0.250182
a4 0.759979 0.240021 0.104886
a5 0.616746 0.383254 0.167477
SUM 2.711596 2.288404 1

[0088] (6)计算社会关系强度

[0089] 有了表4中节点之间每个指标的社会关系值以及表7中每个指标对应的权重，按公式5可计算出节点v9和其他节点的社会关系强度，该值越大，对应节点与节点v9之间的社会关系就越紧密。具体的值如表8所示。

[0090] 表8各节点与v9的社会关系强度值

[0091]   v1 v2 v3 v4 v5 v6 v7 v8a1 2/3 1/3 2/5 4/5 1 0 0 2/15
a2 1/2 2/3 1/3 1/6 2/5 0 0 1
a3 11/14 6/7 1/2 9/14 1 0 0 1/7
a4 1/16 3/16 0 1/8 0 7/16 1/16 1
a5 1/7 2/7 1/7 1/7 1/14 0 2/7 1
Rt 0.505592 0.520638 0.324093 0.428729 0.59645 0.045888 0.054406 0.578536[0092] 由表8可以看到，节点v5与v9的社会关系强度值最大，说明这两个节点的关系最紧密。从原始数据来看，与其他节点相比，v5与v9有最大的相遇次数和最多的消息转发次数。

[0093] 仿真实验

[0094] 本部分使用机会网络仿真模拟器(ONE)对提出的ICR算法进行了仿真实验，并与其它三个移动机会网络路由算法PRoPHETv2、DRAFT和BUBBLE在相同仿真环境下进行了对比实验。在实验中，真实数据集Infocom5、Infocom6、Cambridge和Intel用来作节点移动驱动，这些数据集可从CRAWADA[12]下载，数据集最后一次更新时间是2016年8月，详细信息如表9所示。本实验中，节点缓存大小为5M，消息大小为1K，四个数据的节点的数量和TTL时间如表10所示。

[0095] 表9四个实验数据集信息

[0096]

[0097] 表10 ONE中四个数据集的仿真参数

[0098]

[0099]

[0100] 一般地，使用以下三个指标作为算法性能的度量依据。

[0101] 数据成功转发率(PDR)：在一定时间内成功转发到目的节点的消息数与源节点需传输的消息总数之比。该指标刻画了路由算法正确将消息传输到目的节点的能力，是最重要的度量值。

[0102] 传输延迟(TD)：消息从源节点传输到目的节点所花费的时间。

[0103] 路由开销：如式6所示，通常用开销率来评价，即网络中全部中继的消息数减去成功转发消息数，然后再与成功转发到目的节点的消息数之比。

[0104]

[0105] 实验参数分析

[0106] 在ICR路由算法中共有ω、μ和n三个参数。参数ω是簇成员的社会关系强度阈值，对于每个节点，其本地簇的大小会随着ω的减小而增大。参数μ与度量两个节点的社会关系强度的相遇次数有关。在给定条件下，μ的值越大，两个节点的社会关系强度计算值越小。本地簇构建时，ω和μ有着相似的影响。另一个方面，当ω的值固定时，可以改变μ的值以使节点加入本地簇。显然地，节点间社会关系强度阈值的改变和加入本地簇阈值的改变对于本地簇的构建有着相同影响，因此本部分只分析参数ω对实验结果的影响。参数n是在T时间段内社会关系强度自衰减的次数，用来对社会关系强度进行自衰减，剔除过时节点。给定的仿真时间为三天，ICR算法在Infocom5数据集下各参数变化的实验结果如图2所示。

[0107] 如图2所示，ω的值越小数据转发成功率越高，传输时延越小，路由开销越高。从理论上分析，本地簇的增大意味着簇成员变多，大大增加了消息转发到目的节点的几率，从而数据转发成功率得到了提高，降低了传输时延。但是由于簇中节点变大造成网络中有更多的数据副本，加大了路由开销。考虑到数据转发成功率，传输延时和路由开销这三个指标之间的平衡，本发明建议参数ω设置为0.4，以下对比均设置ω＝0.4。

[0108] 从实验结果来看，参数n对数据转发成功率和传输延迟几乎没有影响。本发明认为，n与过时节点从本地簇中剔除的速度有关，但是和帮助成功转发消息的关键中继节点没有关系。正如本文考虑到的，对于路由开销，n的值越小导致越多无用的节点停留在本地簇中，更多的消息副本在网络中被转发，因此，路由开销增大，如图2(d)所示。

[0109] 对比试验

[0110] 本部分将四种算法在相同环境下进行仿真并对比性能。

[0111] 在ICR机制中，参数设置为ω＝0.4，n＝500,μ为每个数据集中所有节点平均相遇次数的1.2倍。在DRAFT算法中，参数设置为τ＝7，δ＝0.9，t＝3600s。

[0112] (1)数据成功转发率

[0113] 在仿真实验中，分别将ICR、PRoPHETv2、DRAFT和BUBBLE算法在四个数据集下运行，运行时间即为数据集的持续时间，如表9所示，实验结果如图3所示。

[0114] 图3表示了随着时间变化四个算法的数据转发成功率实验结果。当仿真时间小于一天时，ICR算法的结果接近于其他三个算法。这是因为网络中簇的形成需要经过一定时间，在短时间范围内，簇中节点较少，无法进行高效的消息转发。随着仿真时间增加，ICR算法的数据成功转发率超过了其它三个路由算法。ICR算法对比于三个算法的实验结果如表11所示。

[0115] 表11相比于其它三个算法ICR在数据转发成功率上的提高(％)

[0116]

[0117] (2)传输延迟

[0118] 如图4所示四个路由算法的传输延迟。相比于其它三个路由算法，ICR算法在传输延迟上有一定程度下降，如表12所示。因为ICR算法是一种基于簇转发的算法，簇成员间有着紧密的社会关系，可以有效帮助消息转发，减少传输延迟。

[0119] 表12相比于其它三个算法ICR在传输延时上的降低(％)

[0120]

[0121] (3)路由开销

[0122] 路由消息的对比情况如图5所示。相对于其它三个路由算法，ICR算法在路由开销上有一定程度下降，如表13所示。由于ICR算法中簇成员间有紧密的社会关系，节点仅向和目的节点位于同一簇的中继节点转发消息副本，有效减少不必要的转发次数。因此，在不影响数据成功转发率的前提下减少了网络中消息数量，降低了路由开销。

[0123] 表13相比于其它三个算法ICR在路由开销上的降低(％)

[0124]

[0125] 实验结果表明，与其他算法相比，本文提出的算法具有较高的消息传递成功率，并且在传输延迟和平均跳数方面也有很好的表现。

[0126] 参考文献

[0127] [1]Haas ZJ,Small T.A new networking model for biological applications of ad hoc sensor networks.IEEE/ACM Trans.OnNetworking,2006,14(1):27 40.[doi:10.1109/TNET.2005.863461]

[0128] [2]Boldrini,C.；Conti,M.；Passarella,A.Impact of Social Mobility on Routing Protocols for Opportunistic Networks.In Proceedings of the IEEE International Symposium on a World of Wireless,Mobile and Multimedia Networks,Espoo,Finland,18–21June 2007；pp.1–6.

[0129] [3]Bulut E,Szymanski B.Exploiting friendship relations for efficient routing in mobile social networks.IEEE Trans.on Parallel andDistributed Systems,2012,23(12):2254 2265.[doi:10.1109/TPDS.2012.83]

[0130] [4]Balasubramanian A,Levine B,Venkataramani A.DTN routing as a resource allocation problem[J].ACM SIGCOMM Computer Communication Review,2007,37(4):37384.

[0131] [5]Hui P,Crowcroft J,Yoneki E.Bubble rap:social-based forwarding in delay tolerant networks[J].IEEE Transactions on Mobile Computing,2011 10(11):1576-1589.

[0132] [6]Daly  E,Haahr  M.Social network  analysis for routing in disconnecteddelay-tolerant MANETs.In:Proc.of the ACM MobiHoc2007.2007.32 40.[doi:10.1145/1288107.1288113]

[0133] [7]Jia X,Wong G K W.A novel socially-aware opportunistic routing algorithm in mobile social networks[C]//International Conference on Computing,NETWORKING and Communications.IEEE,2013:514-518.

[0134] [8]Guo L.RESEARCH ON OPPORTUNISTIC ROUTING BASED ON DYNAMIC SOCIAL RELATION[J].Computer Applications&Software,2013,30(11):180-183.

[0135] [9]Boldrini C,Conti M,Passarella A.Exploiting users’social relations to forward data in opportunistic networks:The HiBOp solution☆[J].Pervasive&Mobile Computing,2008,4(5):63657.

[0136] [10]Yao Y,Liu Y,Ren Z,et al.A low delay routing algorithm for opportunistic networks based on social relations[J].China Sciencepaper,2017.[0137] [11]Shannon C E.A mathematical theory of communication[J].Bell Labs Technical Journal,1948,27(4):379-423.

[0138] [12]CRAWDAD.Available online:http://www.crawdad.org/uoi/haggle/20160828/(accessed on 11 May 2017).