基于兴趣匹配的机会社会网络消息分发机制

张淯舒　王慧强　冯光升　吕宏武

(哈尔滨工程大学计算机科学与技术学院　哈尔滨　150001)(zhangyushu@hrbeu.edu.cn)



基于兴趣匹配的机会社会网络消息分发机制

张淯舒王慧强冯光升吕宏武

(哈尔滨工程大学计算机科学与技术学院哈尔滨150001)(zhangyushu@hrbeu.edu.cn)

摘要机会社会网络(opportunistic social networks)能够利用节点移动创造的相遇机会，在缺乏持续端到端连接的网络中，为用户提供稳定的消息分发途径，但在消息分发效率以及用户体验方面存在不足.为提高消息分发系统的性能、改善网络用户体验，提出一种基于节点兴趣匹配的机会社会网络分发机制.通过引入混合结构的机会社会网络分发系统解决网络拓扑信息获取不全与节点计算能力不足的问题；从节点行为规律与兴趣爱好2方面对网络进行分析，并提出一种用于复杂关系数据分析的联合聚类方法；针对用户需求，设计消息属性与节点兴趣匹配优先的消息分发策略.仿真结果表明，该机制能够在投递率、投递时延、缓存占用率等方面提升网络性能，且具有较高的分发效率、覆盖率与兴趣匹配度.

关键词机会网络；消息分发；联合聚类；兴趣匹配；拥塞控制

机会社会网络(opportunistic social networks)[1-2]是移动自组织网络的演化，是社交网络向线下实体化转变的一种形式，能够在缺乏持续、稳定端到端连接的环境中，通过节点移动带来的相遇机会实现信息传递，可以更好地应对无线环境中需要面对的间歇性连接、大延迟、高错误率等通信特征.作为移动互联网络的一种有效接入方式，采用“存储-携带-转发”形式路由协议的机会网络，能够极大地拓展移动互联网络的覆盖范围，使得在缺乏网络基础设施的环境中实现信息的分发与检索成为可能.社交网络分析方法的引入，提高了网络拓扑感知、社区划分与节点行为预测的准确性，有助于网络性能的增强与用户体验的提升，然而不断扩大的网络规模以及随之而来的节点与信息数量的急剧增加，使其分析系统与方法都面临着数据收集与处理的压力.

机会网络的特殊路由方式已被广泛应用于校园网络、手持交换网络和车载网络等移动网络环境中.随着机会网络应用的增加，作为路由研究拓展与延伸的消息分发机制也受到越来越多的关注.与传统网络中数据分发属于应用层功能不同，机会网络的消息分发与其路由机制密不可分，机会路由的多副本特性使得消息分发在其传递过程中得以实现.然而，在实际使用的过程中，为保证消息传输的成功率，网络中会存在大量重复的消息副本，使得消息分发过程极大地占用网络存储资源，成为造成网络拥塞的主要原因.在机会社会网络这种典型的资源受限网络中，节点行为由用户设置的策略决定，如果节点有限的存储资源被过多的无关消息占用，会导致用户在网络协助策略的设置上趋于自私，进而影响整个网络的性能.针对机会网络中节点自私行为的问题，虽然有多种惩罚机制被提出，但是惩罚机制不能解决产生自私行为的根本问题，即使能提高网络整体表现，也无法改善单一用户的服务体验.

Kayastha等人在文献[2]中对移动社会网络相关研究做了深入总结与分析，将其体系结构分为中心式、分布式与混合式3种.其中，中心式结构的网络中设备通过移动网络、WIFI等方式直接与核心网络连接，节点能够连接到丰富的信息与计算资源，但会受到无线接入范围的限制；分布式结构的网络中节点以自组织方式组网，虽然其拓扑结构具有极强的鲁棒性，不依赖基础通信设施，但缺乏丰富的内容；混合式结构的网络能够继承上述2种结构的优点，虽然节点不能时刻与核心网络连接，一般情况下与其他节点通过自组织方式建立连接，但能够通过移动获得与核心网络连接的机会，更符合实际生活中使用场景的特点.然而，现有机会社会网络的相关研究大多面向分布式体系结构，实际使用效果不可避免地受到节点信息获取不全与计算能力不足的影响，缺乏应对大规模网络及其产生的大数据分析需求等挑战的能力.可见，构建混合式结构的机会社会网络是在保持网络结构灵活性的基础上，应对网络规模增大的可行方法.

针对混合式机会社会网络的结构特性，本文提出一种基于兴趣匹配的机会网络分发机制.该机制具有的优点可以概括3个方面：

1) 与面向分布式结构的机会社会网络研究相比，混合式结构的网络节点能够利用与核心网络连接的机会，同步各自收集的网络拓扑信息，以此解决离散分布的节点信息获取不完整的问题；

2) 利用核心网络的计算能力，可以设计相对复杂的网络拓扑与节点关系分析算法，对节点行为、兴趣与消息属性进行联合聚类分析，使联系紧密且兴趣相近的节点聚集为簇，提高分析结果对网络描述的准确性；

3) 在消息分发过程中，优先选择与消息属性相符的节点作为中间节点，提高消息属性与节点兴趣的匹配度，降低无关消息对节点资源的占用，从而提升网络中消息分发系统的用户体验.

此外，设计了一种基于消息密度的拥塞控制机制，控制副本数量在合理区间，既不影响分发效率，又不给网络制造过高的压力.实验表明本文提出的消息分发机制不仅能够提高消息投递率、减少投递时延、降低缓存占用率，而且能够有效地提高消息分发的效率、提升消息分发服务的用户体验.

1相关工作

机会网络的概念最早由Pelusi等人[1]提出，其中许多概念都来源于Fall在文献[3]中提出的延迟容忍网络(delay tolerant network, DTN).随后，大量针对机会网络的路由算法被提出，这些算法大多从消息复制与拓扑预测2个方面增强机会网络的路由表现.Epidemic算法与Spray and Wait算法通过增加消息在副本中的数量的方式提高路由效率，而Seek and Focus，PRoPHET，MaxProp算法则通过预测选择投递成功率较高的节点.

此外，更多的较为复杂的基于拓扑预测方法被相继提出.Whitbeck等人[4]采用基于连接的最大直径方式；Dang等人[5]通过在线统计节点相遇概率的方式，为节点的簇划分以及信息交换和路由提供基础；另外，Hui等人[6]针对口袋交换网络(pocket switched network, PSN)，引入中心度和社区的概念，运用社会学的相关理论优化路由策略；Jahanbakhsh等人[7]将社会距离作为选取消息转发目标的度量，同时为降低动态社区划分方法的计算压力，引入静态的社会关系图.

Fig. 1　Hybrid opportunistic network architecture.图1　机会网络混合式结构

作为路由算法的扩展与延伸，机会网络消息分发获得了越来越多的关注.Lenders等人[8]采用了基于发布订阅模式的内容分发架构，在没有基础设施支持的情况下，首次实现移动无线节点间的消息共享.Yoneki等人[9]首次引入社交关系的信息，提出了基于社交感知的内容发布订阅系统.Ros等人[10]提出一种利用局部周期性的信标消息构造节点的连通支配集，并对支配集内节点进行广播的分发方法.

随着研究的深入，人们发现在机会网络环境中广泛存在的自私节点能够对网络性能造成极大的影响.因此，设计机会网络环境的激励机制成为新的挑战.Lu等人[11]提出了一种由消息源节点制定奖励策略的机制，能够实现了机会网络中隐私敏感数据的安全、高效分发.Sugiyama等人[12]提出一种基于悬赏规则的消息分发传递机制，节点在发送消息时声明参与消息传递节点的总奖励额度，中间节点利用自身剩余资源换取相应奖励.Ning等人[13]提出一种自私性驱动的消息分发激励策略，中间节点能够通过参与消息传递获取虚拟支票，并兑换相应的报酬.Valerio等人[14]利用认知方法设计了一种可扩展的机会网络消息分发机制，主要通过节点的历史活动分析与随机选择相结合的方式决定消息复制的方式.Vingelmann等人[15]讨论了网络编码在机会网络消息分发中的应用，并分析了不同编码方式在多种应用场景中的实际表现情况.Wang等人[16]设计了蜂窝网络与机会网络相结合的信息分发系统，利用机会离线通信方式极大地降低了蜂窝网络的数据流量.

有限的存储空间、计算能力与能量等私有资源被大量应用于处理与用户无关的信息，是产生自私节点的主要原因.现有的机会网络分发机制的研究大多以分发效率、覆盖率等宏观指标衡量分发算法的性能，没有考虑分发过程中用户体验的优劣，容易引起用户趋向于选择较为自私的网络协作策略.而对自私节点的处理上，也大都采用基于奖励惩罚的激励机制，虽然提高了网络的整体性能，但单个节点的用户体验并没有提升.另外，现有机会网络分发机制的研究多数是建立在分布式网络结构上，分发算法在实际使用中会受到拓扑信息获取不全、节点计算能力低下等因素的限制，难以准确地预测网络拓扑的变化趋势，会对消息分发效果造成严重影响.

2问题描述

机会社会网络的混合式结构模型如图1所示.机会社会网络由多种无线手持设备组成，通常情况下，各节点采用自组织方式组网，不依靠基础通信设施接入核心网络.通过自身移动，节点不仅能够与其他节点相遇并进行信息交换，还能够获得周期性地接入核心网络的机会.利用与核心网络的连接机会，节点将自身收集的网络拓扑信息与用户兴趣同步到核心网络进行分析，并从核心网络接受返回的分析结果.同时，核心网络也利用这种间歇性的连接向网络注入消息分发任务.

网络的全局拓扑信息是消息分发的基础，而机会社会网络节点的移动性使得网络不具备稳定的拓扑结构，通常情况下其拓扑结构利用其节点间的关联关系与社区划分等方式描述.本文中，节点分别存储自身收集的局部拓扑信息与核心网络返回的全局拓扑信息.其中，局部拓扑信息由节点间的历史相遇记录表示，作为对相应节点在未来一段时间内相遇概率的预测，在相遇时节点分别更新该信息；全局拓扑信息由节点行为与兴趣联合聚类结果表示，以各节点收集的局部拓扑信息为基础，当节点获得与核心网络连接的机会时，上传近期收集的局部拓扑与节点兴趣信息供其分析，并从核心网络同步最新全局拓扑信息.

在机会社会网络分发系统中共包含m个节点，用集合U表示，n种消息类型，用集合V表示.消息评分可以记作(ui,vj,rij)，表示用户ui对消息类型vj的评分为rij；相遇统计可以记作(ui,uj,pij)，表示用户ui与用户uj的相遇概率为pij.核心网络收集并合并各节点上传的消息评分列表与相遇统计列表，构造节点与消息类型的联合特征矩阵A与节点相似矩阵W.其中，A=[aij]m×n，aij对应消息评分(ui,vj,rij)；W=[wij]m×m，wij对应相遇统计(ui,uj,pij).核心网络根据A与W对节点与消息属性构成的二元关系U×V所对应的矩阵Z进行联合聚类分析，并获得聚类结果(ρ,γ)，其中(ρ,γ)表示一组映射关系：

ρ:{1,2,…,m}|→{1,2,…,k}，

γ:{1,2,…,n}|→{1,2,…,l}.

3基于联合聚类的节点兴趣与行为分析方法

利用核心网络对节点兴趣与行为进行分析，与传统的分布式分析方法相比，能够有效地避免由节点计算能力较弱与信息获取不全导致的结果不准确问题.网络优化问题一般可以从路径选择与消息属性2方面考虑，而机会网络可以将通过节点移动创造的相遇机会当作通信链路使用，因而可以通过分析节点行为规律与消息属性的联系提高网络消息分发的效率.本文利用联合聚类方法同时从节点兴趣与行为2个方面探索网络行为特征，所得到的聚类分析结果能够作为消息分发决策的基础.

一般情况下，联合聚类通常用于分析图2所示的普通二元关系U×V，通过对U与V的联合特征矩阵A的处理与分析，获得聚类结果(ρ,γ).然而，在机会网络中除了节点兴趣与消息类型的关系外，节点相互联系的紧密程度也对消息分发效果具有重要的影响.因此，机会网络中节点与消息的关系是如图3所示的复杂二元关系，由(U×V,U×U)表示，

Fig. 2　Common binary relation.图2　普通二元关系

Fig. 3　Complex binary relation.图3　复杂二元关系

分别对应U与V的联合特征矩阵A以及U的相似矩阵W.为解决该问题，提出一种面向复杂二元关系数据的联合聚类方法.下面先分别从特征矩阵A与相似矩阵W角度分析聚类质量的评价方法，提出兴趣匹配与节点距离的度量方法，再给出联合聚类的简要流程.

3.1兴趣匹配度量方法

在信息学中，对于二元关系U×V来说，联合聚类理论上就是要寻找特定的(ρ*,γ*)，近似满足：

(1)

其中，I(U;V)代表U与V的交互信息，能够利用U与V的特征矩阵A通过某种形式表示.选取平方欧氏距离作为度量标准，即dφ(a1,a2)=(a1-a2)2，其中φ(a)=a2.显然dφ满足：

dφ(a1,a2)=φ(a1)-φ(a2)-a1-a2,φ(a2),

(2)

(3)

(4)

(5)

(6)

将式(3)代入可得：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

3.2节点距离度量方法

相似矩阵W由各节点提供的相遇概率统计记录(ui,uj,pij)组成，其中pij根据节点相遇情况以给定的时间间隔T为周期更新.如果在时间T内，节点i与节点j相遇，则pij更新为

(15)

其中，β∈(0,1)是相遇概率的衰减指数.

由pij的统计过程可知，wij值越大，节点i与节点j相遇概率越大、距离越小.因此，可以将节点i与节点j的距离d(ui,uj)定义为

(16)

对于相似关系U×U，聚类ρ的目标是最小化相同聚类样本之间的聚类、最大化不同聚类样本之间的距离，可以表示为

(17)

其中，当节点i与节点j属于相同聚类时，ωij=1；否则，ωij=0.由此可得，聚类ρ的目标可表示为

(18)

3.3联合聚类分析算法

联合聚类结果(ρ,γ)可通过交替更新ρ与γ获得，简要流程如图4所示，详细算法在第5节给出.其中，ρ与γ的更新原则是使得更新后的聚类结果具有较高的聚类质量.

Fig. 4　Process of co-clustering.图4　联合聚类流程

4消息分发与缓存控制策略

4.1目标区域划分

(19)

4.2消息转发规则

当携带消息M的节点ui与节点uj相遇时，按照节点ui与节点uj是否属于DM可分为4种情况：

1)ui∈DM，uj∈DM.属于相同聚类的节点具有相似的兴趣，区域DM中节点具有较大的几率对消息M感兴趣，因此在区域DM中消息转发按照Epidemic算法方式进行.

4.3拥塞控制机制

机会网络通常采用具有洪泛性质的消息分发策略，通过增加消息在网络中副本数量的方法，提高消息分发效率.然而，网络中消息副本数量过多会使节点缓存压力增大，引起网络拥塞现象；而消息副本数量过少又会影响网络通信效率.针对上述问题提出一种基于消息密度的拥塞控制机制，使网络中消息副本数量控制在合理范围内.

该机制针对节点临近区域中消息副本的密度，只考虑节点最近相遇的L个节点携带该消息的情况，能够避免由于特定消息过量复制导致的网络区域性拥塞现象.然而，由于不考虑当前节点缓存的剩余情况，该方法只能够间接缓解由节点缓存溢出造成的网络拥塞现象.

在消息分发过程中，节点u为其缓存中的消息Mj(j=1,2,…,N)分别设置长度为L的队列Qj，Qj由二元组(ui,flagi)构成，表示与节点u相遇的最近L个节点的ID及其是否携带消息Mj，如果ui不携带消息Mj记为flagi=0，否则记为flagi=1.当节点u与u′相遇时，先将(u′,01)加入Qj队尾.如果Qj中存在包含u′的项，则删除该项；如果Qj中没有包含u′的项且队列长度超过L，则删除Qj中队首项；否则不对Qj进行操作.定义消息Mj的浓度CMj为：

(20)

当收集到足够信息估算Mj密度后，即Mj对应的队列Qj长度达到L后，节点按周期T检查缓存中消息浓度：

若CMj∈[0,18)，则表示网络中消息Mj浓度较低，Mj处于分发初期或末期，将Mj标记为休眠状态，等待下一周期.如果CMj连续2个周期都低于18，则将Mj删除，否则重新激活Mj.

若CMj∈[18,12]，则表示网络中消息Mj浓度正常，Mj正处于分发状态，因此应保存Mj.

若CMj∈(12,1]，则表示网络中消息Mj浓度过高，Mj的分发基本完成，因此应将Mj删除以避免拥塞现象产生.

5机会社会网络消息分发系统

针对混合式结构机会社会网络的特点，设计如图5所示的机会社会网络分发系统，将网络拓扑信息的收集与分析过程分离.

Fig. 5　Message dissemination system.图5　消息分发系统

其中，核心网络对网络拓扑信息进行整合与分析，节点在移动过程中收集网络拓扑信息，并实现消息分发与拥塞控制的功能.

核心网络中，处理U与V间复杂二元关系Z=(U×V,U×U)的改进联合聚类分析的实现方法描述如算法1所示:

算法1. 改进联合聚类算法.

输入: 矩阵A和矩阵W;

输出: (ρ*,γ*).

① 初始化(ρ,γ);

③ 计算AU,AV;

④ repeat

⑥ 更新行聚类;

⑦ fori=1 tomdo

wij)2];

⑨ end for

Aρ(i)-Aj+Ah)2;

算法1的运行时间与矩阵A和W中非零元素的个数Wglod以及行列2个维度的聚类变换操作时间分别线性相关，根据文献[18]的相关分析，其算法复杂度可以表示为O(Wglod+mkl+nkl).一般情况下，Wglod远大于m与n，而m与n远大于k与l，因此，相对于复杂度为O(m2n+n3)2的SVD联合聚类算法与复杂度为O(Wglodk)的NNMF联合聚类算法，算法1具有明显的效率提升.

节点收集、同步网络拓扑信息，以及实现消息分发与拥塞控制等功能的实现方法描述如算法2所示:

算法2. 消息分发算法.

输入: 节点u;

输出:M,CM.

① 等待与X连接的机会;

② ifX是核心网

③ 上传(ui,vj,rij)和(ui,uj,pij);

④ 下载(ρ,γ);

⑤ else ifX是移动节点u′

⑥ 为每个M更新(ui,uj,pij)和Q;

⑦ Part A:

⑧ for 缓存中的M

⑩ 发送M到u′;

在节点缓存空间有限且队列Q长度恒定的条件下，算法2可在常数时间内运行完成，因此其时间复杂度为O(1)，不会对节点造成额外的计算压力.

6实验与分析

6.1仿真平台与数据集

本文利用MATLAB平台对MIT Human Dynamics Lab提供的Social Evolution数据集[19]进行基于事件驱动的仿真.Social Evolution数据集通过移动电话收集信息，记录了同一公寓中80名学生长达8个月的活动规律与交互信息.参与者由30名大一学生、20名大二学生、10名大三学生、10名大四学生与10名研究生组成，均匀分布在公寓的1～4层.该数据集还记录了参与者对11种类型多达1 500首音乐的评价与分享情况，参与者对音乐的评分为1～3分.参与者间的接触间隔基本符合指数分布，同时存在明显的社会特征.

在仿真过程中，网络按照设定的速率产生消息分发请求，随机选择消息的源节点与其包含的音乐类型，并在对该类型音乐评分在2以上的节点中随机选择目的节点.数据包大小在[10 KB,100 KB]区间均匀分布，消息的TTL设定为1周，节点的缓存大小为20 MB.将数据集的前30%记录作为仿真的预热，使得各算法对网络的分析达到稳定状态，实验结果从对数据集的后70%记录的仿真中获得.

6.2对比算法介绍

Epidemic算法是一种采用洪泛策略的机会网络路由算法.在理想情况下，该方法能够获得较为理想的投递率与投递时延，但会对网络造成较大的压力.然而，实际应用的过程中由于网络节点缓存通常较小，效果往往不理想.

Spray and Wait算法是一种限定副本数量的路由算法，通过限定网络中消息副本总数，降低消息分发对网络的压力.该算法适应性强，能够在多种网络环境中提供较为理想的路由性能.

Clustering算法是一种基于聚类分析的机会网络路由算法，该算法根据节点的历史相遇信息为节点划分所属簇，并为关系紧密的簇选定网关节点.该算法能够利用聚类分析结果优化消息转发的路径选择过程.

6.3仿真结果及分析

下面将本文算法与对比算法在投递率、投递时延、缓存占用率、分发效率、分发覆盖率以及节点匹配度6个方面进行比较.

1) 投递率

Fig. 6　Comparison of delivery ratio.图6　投递率的比较

投递率是指网络中成功送达目的节点的消息数在消息总数中所占的比例.从图6可以看出，Epidemic算法与Spray and Wait算法投递率较低，Clustering算法与本文算法相对获得了较高的投递率.Epidemic算法采用复制策略，通过增加消息分发中间节点数量的方式提高消息的投递率，这使得网络中存在大量重复的消息副本.在实验中，由于节点的缓存空间有限，不能满足Epidemic算法的需求，当网络中同时存在多个消息分发任务时，极易引起节点缓存的溢出，进而导致还未成功送达的消息被丢弃，造成网络在投递率上表现较差.Spray and Wait算法也采用复制策略，但由于具有副本数量的控制机制，相对Epidemic算法获得了较高的投递率.与上述算法相比，Clustering算法与本文算法采用转发策略，限制副本的数量并对节点间的关联关系进行分析，在中间节点的选择上具有一定的针对性，因此更容易将消息送达目的节点.其中，本文算法由于采用了线上分析的机制，能获得较完整、准确的网络拓扑信息，因此获得了最高的投递率.

2) 投递时延

投递时延是指消息从产生到最终被送达目的节点所经历的时间.从图7可以看出，投递时延的结果与投递率相似.投递时延能够体现消息传递过程中路径选择的优化能力，选择正确的中间节点不仅能够获得较高的投递率，同时也能获得较低的投递时延.

Fig. 7　Comparison of delivery delay.图7　投递时延的比较

3) 缓存占用率

Fig. 8　Comparison of cache usage.图8　缓存占用率的比较

缓存占用率是指网络中消息副本占所有节点缓存的比例.从图8可以看出，由于Epidemic算法不限制副本数量，网络的平均缓存占用率达到了90%以上，造成大量节点的缓存溢出，严重影响了网络性能；Spray and Wait算法虽然限制了副本的数量，但也是通过复制的方法完成消息的分发，也有较高缓存占用率；Clustering算法与本方算法通过收集的网络信息对网络拓扑进行分析，因此可以在保持高投递率的前提下减少网络中消息副本的数量，降低缓存占用率.本方算法设计了相应的拥塞控制机制，在仿真中获得了最低的缓存占用率.

4) 分发效率

分发效率是指成功分发的消息数与网络中消息转发总次数的比值.分发效率能够体现出消息分发算法的优化程度，具有较高分发效率的消息分发算法能够在网络拥塞状态相同的情况下将更多的消息成功地送达相应的节点.从图9可以看出，本文算法拥有最高的分发效率，接近0.4，即表示利用本文算法平均经过2～3次传递就能将消息送达目的节点；Clustering算法也拥有较高的分发效率，但受到分析方法与网络信息获取方式的影响，略低于本文算法；Epidemic算法与Spray and Wait算法分发效率较差，其中Spray and Wait算法大约需要5次传递将消息送达目的节点，而Epidemic算法需要将近7次传递才能完成.由此可以看出，本文提出的算法在投递率相同的情况下转发次数少于其他算法，因而产生的副本数量、占用的节点缓存较少，能够有效节省网络资源，提高网络的利用率.

Fig. 9　Comparison of dissemination efficiency.图9　分发效率的比较

5) 分发覆盖率

分发覆盖率是指消息的目标群体中收到消息的节点数占群体总数的比例.在实验中，将对消息所包含音乐类型的评分在2以上的个体作为其目标群体.从图10可以看出，Clustering算法与本方算法具有较高的分发覆盖率.与本文算法不同，Clustering算法只对节点间的相互联系进行分析，消息在联系紧密的节点中相互传递的机会较多，而这种节点往往具有相似的兴趣，使得其分发覆盖率相对另外2种算法高很多.而本文算法从节点与消息2个维度进行分析，因此在目标群体的判断上更为精确，在分发覆盖率上较Clustering算法表现出了一定的优势.

Fig. 10　Comparison of coverage rate.图10　覆盖率的比较

6) 节点匹配度

节点匹配度是指节点缓存中与节点兴趣相匹配的消息所占空间与总的缓存占用空间的比值.该指标能够反映用户对消息分发算法的满意程度，是决定用户是否积极参加网络协助的重要因素.从图11可以看出，本文算法获得了最高的节点匹配度.Epidemic，Spray and Wait，Clustering算法都没有考虑节点匹配度的概念，使得在消息传递的过程中，各节点大量处理与自身不感兴趣的消息，极大地消耗了节点有限的计算、存储资源，容易使节点转变为自私节点.而在本文算法中，节点缓存中大部分消息都是节点感兴趣的，因此能够提高节点参与网络协助的积极性.

Fig. 11　Comparison of matching rate.图11　匹配率的比较

7结论

机会社会网络是一种资源受限的特殊网络环境，如何有效利用有限的网络通信、存储与计算资源对提高网络性能有重要意义.针对现有机会社会网络分发方法存在的问题，本文提出一种基于兴趣匹配的机会社会网络分发机制.通过构建混合结构的消息分发系统，利用核心网络较强的计算能力同时从节点行为规律与兴趣爱好2个方面分析网络拓扑变化规律与节点间关联关系，不仅避免了单个节点所面临的信息获取不完整与计算能力不足的问题，还提高了网络拓扑预测的准确性.同时，节点兴趣匹配优先的分发策略也从根本上保证了用户参与网络协助的积极性.仿真实验表明，与现有方法相比，本文提出的消息分发机制能够有效地改善网络性能，提高消息分发系统的性能.

本文下一步的工作主要有：优化节点相遇概率统计的方法，以及探索节点移动规律对消息分发效率的影响.

参考文献

[1]Pelusi L, Passarella A, Conti M. Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, 2006, 44(11): 134-141

[2]Kayastha N, Niyato D, Wang P, et al. Applications, architectures, and protocol design issues for mobile social networks: A survey[J]. Proceedings of the IEEE, 2011, 99(12): 2130-2158

[3]Fall K. A delay-tolerant network architecture for challenged Internets[C] //Proc of the 2003 Conf on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2003: 27-34

[4]Whitbeck J, Conan V. HYMAD: Hybrid DTN-MANET routing for dense and highly dynamic wireless networks[J]. Computer Communications, 2010, 33(13): 1483-1492

[5]Dang Ha, Wu Hongyi. Clustering and cluster-based routing protocol for delay-tolerant mobile networks[J]. IEEE Trans on Wireless Communications, 2010, 9(6): 1874-1881

[6]Hui Pan, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2011, 10(11): 1576-1589

[7]Jahanbakhsh K, Shoja G C, King V. Social-greedy: A socially-based greedy routing algorithm for delay tolerant networks[C] //Proc of the 2nd Int Workshop on Mobile Opportunistic Networking. New York: ACM, 2010: 159-162

[8]Lenders V, Karlsson G, May M. Wireless ad hoc podcasting[C] //Proc of IEEE SECON 2007. Piscataway, NJ: IEEE, 2007: 273-283

[9]Yoneki E, Hui Pan, Chan Shuyan, et al. A socio-aware overlay for publish/subscribe communication in delay tolerant networks[C] //Proc of the 10th ACM Symp on Modeling, Analysis, and Simulation of Wireless and Mobile Systems. New York: ACM, 2007: 225-234

[10]Ros F J, Ruiz P M, Stojmenovic I. Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks[J]. IEEE Trans on Mobile Computing, 2012, 11(1): 33-46

[11]Lu Rongxing, Lin Xiaodong, Shi Zhiguo, et al. IPAD: An incentive and privacy-aware data dissemination scheme in opportunistic networks[C] //Proc of IEEE INFOCOM 2013. Piscataway, NJ: IEEE, 2013: 445-449

[12]Sugiyama K, Kubo T, Tagami A, et al. Incentive mechanism for DTN-based message delivery services[C] //Proc of Global Communications Conf. Piscataway, NJ: IEEE, 2013: 3108-3113

[13]Ning Ting, Yang Zhipeng, Wu Hongyi, et al. Self-interest-driven incentives for ad dissemination in autonomous mobile social networks[C] //Proc of IEEE INFOCOM 2013. Piscataway, NJ: IEEE, 2013: 2310-2318

[14]Valerio L, Passarella A, Conti M, et al. Scalable data dissemination in opportunistic networks through cognitive methods[J]. Pervasive and Mobile Computing, 2015, 16: 115-135

[15]Vingelmann P, Heide J, Pedersen M V, et al. All-to-all data dissemination with network coding in dynamic MANETs[J]. Computer Networks, 2014, 74: 34-47

[16]Wang Xiaofei, Chen Min, Han Zhu, et al. Toss: Traffic offloading by social network service-based opportunistic sharing in mobile social networks[C] //Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 2346-2354

[17]Banerjee A, Merugu S, Dhillon I S, et al. Clustering with Bregman divergences[J]. The Journal of Machine Learning Research, 2005, 6: 1705-1749

[18]Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to Bregman co-clustering and

matrix approximation[C] //Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2004: 509-514

[19]Madan A, Cebrian M, Moturu S, et al. Sensing the “health state” of a community[J]. IEEE Pervasive Computing, 2012, 11(4): 36-45

Zhang Yushu, born in 1986. PhD candidate. His research interests include mobile networks and network security.

Wang Huiqiang, born in 1960. Professor and PhD supervisor. Senior member of China Computer Federation. His current research interests include cognitive networks, autonomic computing and next generation network.

Feng Guangsheng, born in 1980. PhD and lecturer. Member of China Computer Federation. His current research interests include QoS assurance of cognitive networks.

Lü Hongwu, born in 1983. PhD and lecturer. His current research interests include optimization and configuration of wireless networks resource.

Message Dissemination Based on Interest Matching for Opportunistic Social Networks

Zhang Yushu, Wang Huiqiang, Feng Guangsheng, and Lü Hongwu

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001)

AbstractOpportunistic social networks can provide message dissemination service through encounters created by nodes’ movement in intermittently connected or completely disconnected wireless networks, but there are still some shortcomings in message dissemination efficiency and user experience. In order to promote the performance of dissemination system and improve the user experience, an opportunistic social network message dissemination mechanism based on node interest matching is proposed. A kind of opportunistic social networks with hybrid architecture is introduced to avoid problems such as incomplete information of network topology and low computing ability of nodes. Considering the fact that node behaviors and interests can both affect the performance of dissemination, the analytical method designed takes both of them as reference factors, and an improved co-clustering algorithm for data with complex relationship is proposed. In addition, the interest matching rate for nodes is used to show what percentage of buffer is occupied by the useful messages to user, and a novel message dissemination strategy is proposed to raise the rate. Simulation results show that the proposed scheme can both improve the capability of opportunistic social networks in terms of delivery rate, latency and buffer usage, and promote the performance of message dissemination systems in terms of efficiency, coverage rate and interest matching rate.

Key wordsopportunistic network; message dissemination; co-clustering; interest matching; congestion control

收稿日期：2014-12-23；修回日期：2015-04-16

基金项目：国家自然科学基金项目(61370212,61402127,61502118);高等学校博士学科点专项科研基金项目(20122304130002);中央高校基本科研业务费专项资金项目(HEUCFZ1213,HEUCF100601)

中图法分类号TP393

This work was supported by the National Natural Science Foundation of China (61370212,61402127,61502118), Research Fund for the Doctoral Program of Higher Education of China (20122304130002), and the Fundamental Research Funds for the Central Universities (HEUCFZ1213,HEUCF100601).