机会网络中基于兴趣和相遇相关的消息自适应推荐方法

摘要

本公开涉及一种机会网络中基于兴趣和相遇相关的消息自适应推荐方法，所述方法根据机会网络中用户之间交互所表现出的规律性和社会性，将符合条件的消息推荐至感兴趣的用户节点，在推荐过程中，若相遇节点能作为转发该消息的中继节点，则将消息转发至中继节点，并同时对中继节点的历史相遇节点预分配消息副本，以待下次相遇时直接转发。在这种消息副本分配方式下，有效增强了消息传输的目的性，对消息副本合理分配，使消息副本能更加快速地扩散、有效地传递。所述方法中，节点根据自身和网络拓扑结构的变化，动态分配当前节点的消息副本，并根据历史相遇节点的变化动态调整预先分配的消息副本数目，从而使节点能够更加适应动态变化的网络环境。

说明书

技术领域

本公开涉及计算机网络和普适计算的交叉领域，具体地讲，涉及一种机会网络中基于兴趣和相遇相关的消息自适应推荐方法。

背景技术

机会网络中，在源节点和目的节点之间可能不存在一条完整的路径，利用节点移动获得的相遇机会而形成网络通信，通过节点移动和在节点间转发而实现消息传输。机会网络采用“存储-携带-转发”的路由模式，即节点携带着消息移动，直到有机会将消息转发至其他节点，利用其他节点的帮助将消息传输至目的节点。机会网络作为一种网络通信新技术，是移动自组织网络发展的新方向，在野生动物追踪、手持设备组网、灾难地区救援、星际网络、车载网络、偏远山区建设等移动网络的范畴中有着广泛的应用研究前景。

在机会网络中，数据的传输需要利用节点移动带来的通信机会，数据经过多个中继节点传输至目的节点。这种通过多跳形式转发数据的方式使得数据在传输过程中对中继节点的选取显得十分关键，选取不当将直接影响机会网络的数据转发性能。因此，有关机会转发机制的研究成为机会网络研究热点之一。

伴随着互联网的发展，各种新的互联网应用形式层出不穷，互联网的用户和信息规模也在急剧增加，用户间通过互联网共享各种信息(如网络文本、图像、音频、视频等)，这种新的应用形式更注重于用户的交互作用，用户既是信息的浏览者，也是信息的制造者，向用户提供了一个交友、分享资讯的平台，其在一定程度上起到了信息传播和流通的作用。传统的网络形式中，用户通过台式机等终端设备接入互联网，网站通过对用户偏好档案，订阅信息以及历史交互记录的分析为用户推荐信息。

目前，消息(即内容，包括电影，书籍，商品，音乐等)的个性化推荐的应用较广，在微博上可以表现为好友动态信息的推荐，在电影和视频网站可以表现为个性化影视信息的推荐，在阅读类网站可以表现为文章的推荐，在商务网站可以表现为用户感兴趣商品的推荐，可以说消息的个性化推荐对于扩大社交网络影响力十分重要。现有的推荐技术主要有基于内容的消息推荐、协同过滤消息推荐、基于语义的消息推荐、混合消息推荐等四类。

发明内容

本公开所提出的消息推荐方法不同于这种社会化网络形式，该方法基于用户携带的手机、蓝牙设备、支持Wi-Fi的手持电子设备等组成的机会网络中用户之间进行交互所表现出来的规律性以及社会性，可以有效提高机会网络中数据转发的性能，同时推荐给用户的消息具有较高的准确性。

本公开的技术方案为一种机会网络中基于兴趣和相遇相关的消息自适应推荐方法，所述方法包括下述步骤：

S1、将携带消息副本的节点视为源节点，检测所述源节点在当前周期内的是否有相遇节点；若有相遇节点，执行步骤S2；否则，执行步骤S8；

S2、在所述相遇节点中，判断是否有预留消息副本的相遇节点；若有预留消息副本的相遇节点，执行步骤S3；否则，执行步骤S4；

S3、从源节点向预留消息副本的相遇节点分配预留的消息副本，执行步骤S4；

S4、判断是否有感兴趣的相遇节点；若有感兴趣的相遇节点，执行步骤S5；否则，执行步骤S6；

S5、从源节点向感兴趣的相遇节点分配1个副本，执行步骤S6；

S6、判断所述源节点当前所携带的消息副本数目是否大于1；若大于1，则执行步骤S7；

S7、从源节点向能作为中继节点的相遇节点分配相应数目的消息副本；进入下一周期，返回步骤S1；

S8、获取所述源节点的历史相遇节点集合，为所述历史相遇节点预分配消息副本；进入下一周期，返回步骤S1。

与现有技术相比，本公开的方法具有下述特点：

将符合条件的消息推荐至感兴趣的用户，同时考虑相遇节点是否能够作为转发该消息的中继节点的情况，将消息转发至中继节点；在没有相遇节点时，对携带消息的节点的历史相遇节点进行预分配，以待下次相遇时传输消息副本。在这种消息副本分配方式下，有效增强了消息传输的目的性，对于消息副本合理的分配，使得消息副本能够更加快速地扩散、有效的传递。由于节点自身和网络拓扑结构的变化，动态分配当前节点的消息副本，同时根据历史相遇节点的变化动态的调整预先分配的消息副本的数目，使得节点能够更加适应动态变化的网络环境。

附图说明

图1一个实施例中关于携带消息副本的节点在一个运动周期内消息推荐的流程示意图；

图2一个实施例中关于当前节点的通信范围示例图；

图3一个实施例中关于历史相遇节点预先分配消息副本示例图。

具体实施方式

本公开深入研究和分析了机会网络中用户间交互过程中所表现出的社会性和规律性，提出了一种机会网络中基于兴趣和相遇相关的消息自适应推荐方法。

在一个实施例中，提供了一种机会网络中基于兴趣和相遇相关的消息自适应推荐方法，所述方法包括下述步骤：

S1、将携带消息副本的节点视为源节点，检测所述源节点在当前周期内的是否有相遇节点；若有相遇节点，执行步骤S2；否则，执行步骤S8；

S2、在所述相遇节点中，判断是否有预留消息副本的相遇节点；若有预留消息副本的相遇节点，执行步骤S3；否则，执行步骤S4；

S3、从源节点向预留消息副本的相遇节点分配预留的消息副本，执行步骤S4；

S4、判断是否有感兴趣的相遇节点；若有感兴趣的相遇节点，执行步骤S5；否则，执行步骤S6；

S5、从源节点向感兴趣的相遇节点分配1个副本，执行步骤S6；

S6、判断所述源节点当前所携带的消息副本数目是否大于1；若大于1，则执行步骤S7；

S7、从源节点向能作为中继节点的相遇节点分配相应数目的消息副本；进入下一周期，返回步骤S1；

S8、获取所述源节点的历史相遇节点集合，为所述历史相遇节点预分配消息副本；进入下一周期，返回步骤S1。

由上述步骤可知：

(1)一个携带消息的源节点在一个周期中将自身携带的消息副本进行自适应推荐的方法，当一个周期结束，这个携带消息的源节点以及其它获得消息副本的节点重复上述步骤，即在下一个周期中，机会网络中携带消息的节点除了源节点还有中继节点；

(2)一个携带消息的节点在遇到曾经对消息感兴趣的历史相遇节点、或者可以作为中继节点的历史相遇节点时，将预留的消息副本直接转发给它；当首次遇到一个节点时，其判断该节点对其携带的消息是否感兴趣，并进一步判断该节点是否适合作为中继节点；

(3)当所有节点自身只有一个消息副本时，它们携带消息移动，直至消息生命周期结束。

上述技术方案与现有技术相比，具有下述特点：

将符合条件的消息推荐至感兴趣的用户，同时考虑相遇节点是否能够作为转发该消息的中继节点的情况，将消息转发至中继节点；在没有相遇节点时，对携带消息的节点的历史相遇节点进行消息副本预分配，以待下次相遇时传输消息副本。在这种消息副本分配方式下，有效增强了消息传输的目的性，对于消息副本合理的分配，使得消息副本能够更加快速地扩散、有效的传递。由于节点自身和网络拓扑结构的变化，动态分配当前节点的消息副本，同时根据历史相遇节点的变化动态的调整预先分配的消息副本的数目，使得节点能够更加适应动态变化的网络环境。

前述或以下实施方案/特征/方面中任一项的方法，其中所述中继节点通过下述步骤判断：

S71、使用效用值度量节点的转发能力；根据下式(1)计算相遇节点的效用值；

S72、若所述相遇节点的效用值满足设定的阈值条件，则该相遇节点能够为中继节点；

式(1)中：

n表示节点；

i为节点的下标，使用下标来区别不同的节点；

m表示消息；

U(n_i,m)表示节点n_i对于消息m的效用值；

为调整因子；

U(n_i,m)_old表示上一周期中节点n_i对于消息m的效用值；

U(n_i,m)_upd表示从上一周期结束到当前时刻节点n_i对于消息m累积的效用值；

其中：

U(n_i,m_j)_upd通过式(2)计算：

式(2)中：

e为自然常数；

U(n_i,m)_upd′表示节点n_i对消息在当前周期内的累积效用值，通过下式(3)计算：

式(3)中：

k为节点的下标；

η表示两个节点的相遇概率，其下标为两个节点；

S(n_i)表示节点i在当前周期内遇到的邻居节点集合；

|S(n_i)|表示集合S(n_i)的大小；

Sim(n_k,m)表示节点n_k和消息m对应的兴趣相似度。

前述或以下实施方案/特征/方面中任一项的方法，其中所述相遇概率通过下式计算：

式中：

n表示节点；

i为节点的下标，k为节点的下标，使用下标来区别不同的节点；

η表示两个节点的相遇概率，其下标为相遇的两个节点；

C表示两个节点的相遇次数，其下标为相遇的两个节点；

N(i)表示节点i相遇到的其他节点的集合；

t_e(h)表示第h次相遇的结束时间，t_s(h)表示第h次相遇的开始时间。

上述步骤通过对用户历史交互信息的分析，从相遇节点和消息的兴趣匹配度以及用户节点和历史相遇节点的相遇概率等方面出发，给出了一种度量节点转发能力的方法。根据效用值的大小自适应分配消息副本，可以保证消息副本快速、有效传输至感兴趣的用户，对当前消息的效用值越大，说明之前经常相遇对该消息感兴趣的节点，并且节点间的相遇较为频繁，将效用值大的节点作为转发消息的下一跳节点，有效地增强了消息传输的目的性，对于消息副本合理的分配，使得消息副本能够更加快速地扩散、有效的传递。避免了传统方法固定分配消息副本的盲目性；同时能够降低无关消息对用户缓存资源的占用，从而提升网络中消息分发过程中的用户体验。

在计算效用值时，综合考虑当前周期和以往周期累积的效用值，进行加权处理。采用此种方法度量节点转发消息的能力大小，从而进行消息副本分配。有效的提高了选择中继节点的可靠性。

在计算节点间相遇概率时，优选地，携带消息副本的节点在本地建立并维护相应的相遇历史信息表，记录当前周期中节点和其他节点和相遇信息，随着网络拓扑结构的变化，该表中的内容也不断的进行更新，携带消息副本的节点所建立的相遇历史信息表的结构如表1所示：

表1：

前述或以下实施方案/特征/方面中任一项的方法，其中S81、所述源节点使用下式更新当前的效用值：

U(n_i,m)＝U(n_i,m)_old×γ

式中：

m表示消息；

n表示节点，i为节点的下标，使用下标来区别不同的节点；

γ∈(0,1)为衰老常量；

U(n_i,m)表示当前周期节点n_i对于消息m的效用值；

U(n_i,m)_old表示上一周期中节点n_i对于消息m的效用值。

上述步骤是一个更新节点效用值的衰老机制，从该公式中可以看出，假如在较长时间里节点没有遇到相应的兴趣节点或者转发消息副本至其他节点，表明其成功传输消息的可能性很小，从而其效用值逐渐衰减。

前述或以下实施方案/特征/方面中任一项的方法，其中所述步骤S7所述从源节点向能作为中继节点的相遇节点分配相应数目的消息副本包括下述步骤：

S701、根据下式计算每个中继节点的效用值权重：

式中：

N是中继节点下标集合；

l是节点下标，l∈N；

w_l表示节点n_l的权重，节点n_l是一个中继节点；

n_S表示携带消息副本的节点；

m表示消息；

U(n_l,m)表示节点n_l对于消息m的效用值；

U(n_j,m)表示节点n_j对于消息m的效用值；

U(n_S,m)表示节点n_S对于消息m的效用值；

S702、根据下式计算每个中继节点应该被分配的消息副本数：

式中：

L表示消息副本数目，其下标表示节点；

表示携带消息副本的节点n_S当前所携带的消息副本数目；

表示节点n_j当前携带的消息副本数目。

上述步骤中，当前携带消息副本的节点相遇其他节点时，通过比较各节点对当前消息的效用值，并根据自身占总体的权重获取分配新的消息副本数量，能够降低无关消息对用户缓存资源的占用，从而提升网络中消息分发过程中的用户体验。

在计算时，若出现小数，则进行取整处理，可以向上取整、向下取整或者四舍五入。

前述或以下实施方案/特征/方面中任一项的方法，其中所述步骤S8中所述预分配包括下述步骤：

S801、计算所述源节点与每个历史相遇节点的相遇概率，从而获得所述中继节点与历史相遇节点的平均相遇概率；

S802、从所述历史相遇节点集合中获取第二历史相遇节点集合，所述第二历史相遇节点集合中的节点与所述源节点的相遇概率不小于所述平均相遇概率；

S803、从所述第二历史相遇节点集合中获取对当前消息感兴趣的第三历史相遇节点集合；

S804、若所述源节点当前携带的消息副本数目不小于所述第三历史相遇节点集合的大小，则为所述第三历史相遇节点集合中的每个节点预留一个消息副本；

S805、若所述源节点当前携带的消息副本数目不小于1，执行步骤S806；

S806、从所述第二历史相遇节点集合中获取第四历史相遇节点集合，所述第四历史相遇节点集合中的节点为能够作为中继节点的节点；

S807、根据所述第四历史相遇节点集合中节点的优先级为所述第四历史相遇节点集合中节点预留相应数目的消息副本。

在机会网络中，节点的移动具有一定的规律性，之前一段时间频繁相遇的节点在以后的时间更有可能再次相遇。上述步骤对满足条件的兴趣节点均预先保留一份消息副本，以待下一次相遇时直接转发消息，使得节点能够根据历史相遇节点的变化动态的调整预先分配的消息副本的数目，从而能够更加适应动态变化的网络环境。

前述或以下实施方案/特征/方面中任一项的方法，其中所述步骤S807包括下述步骤：

S8071、若所述源节点所携带的消息副本数目小于所述第四历史相遇节点集合中节点的数目，则根据相遇概率大优先级高的原则对所述候选中继节点进行排序，然后为所述第四历史相遇节点集合中节点预分配消息副本；

S8072、若所述源节点所携带的消息副本数目不小于所述第四历史相遇节点集合中节点的数目，则根据节点的活跃度为所述第四历史相遇节点集合中节点预分配消息副本。

上述步骤提供了一种基于优先级分配消息副本的方式：当前中继节点的消息副本数目L′与候选中继节点数目不同的分配方式，在消息副本数目L′小于候选中继节点数目时，根据相遇概率对候选中继节点进行优先级排名，对优先级前L′个节点分配消息副本。否则，采用节点活跃度加权的方法分配消息副本至候选中继节点。其中活跃度表示节点的活动能力，活动能力越强，能够接触的节点越多，因此能够将消息成功转发到兴趣节点的机会越大。优选的，所述根据节点的活跃度为所述候选中继节点预分配消息副本包括下述步骤：

S8072.1、采用下述公式计算候选中继节点的参考活跃度：

式中：

n表示节点；

p为节点的下标且n_p是一个候选中继节点，j为节点的下标，使用下标来区别不同的节点；

S(n_p)为节点n_p在当前周期内的相遇节点集合；

C(n_p,n_j)为节点n_p、n_j在当前周期内的相遇次数；

为节点n_p的参考活跃度；

S8072.2、对所述参考活跃度进行归一化：

式中：

为节点n_p的活跃度；

为节点n_p的参考活跃度；

e为自然对数；

S8072.3、利用归一化后的参考活跃度，根据下述公式计算分配副本数目：

式中：

n_p是为所述第四历史相遇节点集合中的节点；

表示携带消息的节点n_i当前所携带的消息副本数目；

表示携带消息的节点n_i已为感兴趣节点分配的消息副本总数；

R(n_i)是节点n_i的历史相遇节点集合中能够作为中继节点的集合。

在计算消息副本数目时，若出现小数，则进行取整处理，可以向上取整、向下取整或者四舍五入。

前述或以下实施方案/特征/方面中任一项的方法，其中所述步骤S4中判断包括下述步骤：

S401、获取携带消息副本的节点所携带的消息，并获得该消息的消息兴趣属性向量，将所述消息兴趣属性向量记作B＝[b₁,b₂,…,b_I]，其中：I表示兴趣总数，q∈[1,I]，b_q表示该消息对第q个兴趣爱好的相关程度，b_q∈[0,1]且

S402、获取一个未判断过的相遇节点；

S403、获得该相遇节点的节点兴趣属性向量，将所述节点兴趣属性向量记作A＝[a₁,a₂,…,a_I]，其中：a_q表示该相遇节点对第q个兴趣爱好的感兴趣程度，a_q∈[0,1]且

S404、计算所述相遇节点和消息的感兴趣程度，将所述感兴趣程度记作Sim，则有：

S405、若所述感兴趣程度满足设定阈值条件，则判断所述相遇节点对所述消息感兴趣；

S406、返回步骤S402，直至判断完所有的相遇节点。

上述步骤中基于用户交互过程中所表现出来的兴趣因素对于节点和消息进行定义，适用于广告分发，兴趣消息扩散等场景，对于消息的向量化表示可以通过文本聚类获得。同时利用向量的形式根据自身喜好来度量用户对不同兴趣爱好的喜爱程度，即可以将用户的兴趣模型表示为一个多维兴趣属性向量，向量的每一维都由一个关键词及该关键词的权重组成。步骤S404中计算所述相遇节点和消息的感兴趣程度的公式也是求历史相遇节点和消息的兴趣相似度，该计算公式可以使用其它相似度公式代替。通过使用兴趣相似度计算，转发消息至感兴趣的用户，提高了机会网络中消息和节点兴趣匹配的准确度。

采用向量化的形式建立用户和消息的兴趣属性模型，通过对用户节点和传输消息的关系、用户间社会属性的关联程度的分析提出相应的消息自适应推荐方法。所提出的推荐方法具有较高的准确性，使用该方法能够有效提高机会网络中数据转发的性能。

前述或以下实施方案/特征/方面中任一项的方法，其中所述步骤S5具体包括下述步骤：

S501、若携带消息副本的节点所携带的副本数目大于1，则携带消息副本的节点向相遇节点发送1个副本；

S502、若携带消息副本的节点所携带的副本数目等于1，则携带消息副本的节点S向相遇节点复制1个副本。

当自身携带的消息副本数为1时，此时遇到兴趣节点时，只进行复制消息副本的操作，当前节点自身依然保留一个消息副本，直到其消息生命周期结束。

下面结合附图对本公开的方法进行进一步阐述。

图1给出了本公开方法在携带消息副本的节点在一个运动周期内消息推荐的流程示意图。

当前时刻节点S携带消息副本m需要转发，相应的消息属性向量为B_m，相应的消息副本数为21。图2为节点S的通信范围示例图，图中节点S通信范围内有相遇节点B、D、E、G等节点，相应的兴趣属性向量为A_B、A_D、A_E、A_G。节点S需要推荐消息m至通信范围内的兴趣节点，根据公式(10)进行相似度计算，节点和消息m的兴趣相似度依次为0.32、0.58、0.2、0.16，由于系统当前设定的相似度阈值θ为0.4，只有节点D符合兴趣匹配的条件，因此直接转发消息至节点D。

根据历史相遇记录信息计算，节点B、D、E、G相对于消息m的效用值依次为0.45、0.10、0.3、0，系统当前设定的条件中效用阈值ε

取值为0.3。当前周期中节点S对应消息m的效用值为0.75，节点B和E可以作为转发消息m的中继节点，根据效用值计算相应的权重大小，从而计算分配的消息副本数，所得L_B(m)＝6，L_E(m)＝4，相应的L_S(m)＝20-6-4＝10。最终节点B得到6个消息副本，节点E得到4个消息副本，当前节点S剩余10个消息副本。

图3为本发明中对历史相遇节点预先分配消息副本的示例图。由以上过程得知：节点B得到了6个消息副本。在一个新运动周期内，节点B当前通信范围内没有对消息m感兴趣的节点和可以充当中继的节点。此时需要对历史相遇节点进行消息副本预先分配的操作，遍历节点B的相遇历史信息表，有节点F、E、L和H，根据公式(10)进行相似度计算，获得节点和消息m的兴趣相似度依次为0.43、0.1、0.5、0.4，相应的通过计算相遇概率依次为0.36、0.1、0.4、0.2，系统当前设定的相似度阈值为0.4，很显然节点F和L符合兴趣匹配的条件，通过计算节点F、L和当前节点B的相遇概率大于平均相遇概率，则节点B需要为节点F和L各预留一个消息副本，以待下一次相遇时直接传输消息，此时节点B剩余的消息副本数为4个。

以上对本公开进行了详细介绍，本文中应用了具体个例对本公开的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本公开的方法及其核心思想；同时，对于本领域技术人员，依据本公开的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本公开的限制。