混合式移动社会网络及消息分发机制综述

孔 靓， 贾美娟， 邵国强

(大庆师范学院 计算机科学与信息技术学院， 黑龙江 大庆 163712)

引言

移动社会网络(Mobile Social Networks，MSNs)已经渗透到现代社会的各个领域，从滴滴打车，到微信交友，再到淘宝购物，无不昭示出其与人类生活的相互依赖和深度融合。混合式移动社会网络(Hybrid Mobile Social Networks，HMSNs)代表着MSNs在复杂环境下的发展趋势，具备移动网络与社会网络、集中式拓扑与分布式拓扑、直接链路与机会链路共存下的结构互补优势，无论是美国、日本等发达国家的战略立项，还是具体的消息分发机制研究中，都是当前该领域关注的重点[1]。因此，本文针对MSNs及HMSNs这2种社会网络的特性及关系拟做出全面分析比较，并对相应的消息分发方法的优缺点进行详细剖析，最后提出未来的研究方向。基于此，本文可给出研究内容论述如下。

1 传统MSNs

MSNs是传统社交网络在移动网络领域的应用和延伸[2]，自提出以来，形成了集中式、分布式和混合式3种典型模式。其中，集中式的消息分发依靠基础网络结构和中心服务器完成，网络拓扑结构简单，消息分发策略单一；分布式的消息分发借助移动节点之间的相互通信完成，无需中心服务器的支持，部署灵活方便。

在网络基础设施的支撑下，集中式MSNs可提供高质量的移动社交服务，无需移动用户和中心服务器在物理位置上保持关联，但是却无法避免这种客户服务器模式的性能瓶颈和单点失效问题。Gupta等人[3]早在2009年就着手这一领域的研究尝试，并提出了MoBiSoC中间件平台，致力于为User-centric和Place-centric这2类服务提供统一的解决方案。

2 混合式移动社会网络HMSNs

文献[1]明确指出MSNs的发展趋势是将集中式和分布式两者进行融合，使其兼具集中式和分布式的优点，在受限的网络资源环境下具有潜在的应用价值[2]，即HMSNs的概念雏形，其典型结构如图1所示。

HMSNs不但是集中式和分布式MSNs在体系结构上的结合，而且是端到端和机会转发2种消息分发机制的融合。与集中式MSNs相比，HMSNs的结构灵活且部署方便；与分布式MSNs相比，HMSNs既可以在移动节点间直接指派消息分发，又可以借助潜在的中心结构来保障消息分发能力，因而在复杂环境下具有重要的应用价值。然而，HMSNs还存在着高度动态的网络拓扑结构、难以控制的消息分发过程、有限能力的连接机会等问题，严重阻碍了HMSNs的实用化进程[4]。

图1 HMSNs概念结构

文献[1]对传统MSNs和HMSNs的特点进行了归纳，研究结果可详见表1。

表1 传统的MSNs和HMSNs的对比分析

3 消息分发方法

在MSNs环境下，如何实现高效的消息分发始终是本领域的热点和难点问题。传统方法大都基于位置信息，如GPSR、MV、Mobyspace、Locus等[5]，当前研究多是从社会属性、消息内容等方面探讨展开；在网络连通能力受限的环境下，常采用主动机制和混合拓扑来提升消息分发效率[6]。本文将从社会网络、消息内容、主动机制和混合拓扑4个方面来梳理MSNs消息分发方法。研究详情可分述如下。

3.1 基于社会网络分析的消息分发

3.1.1 研究分析综述

文献[5]根据节点的中心度、相似度等社会属性选择中继节点，在全局网络拓扑和节点历史活动数据的基础上，将具有相近社会属性的节点划分到同一社区，进而将消息分发问题转化为社区间和社区内的选路问题。Bubble Rap[7]通过分析节点社会特性和实际移动轨迹来构建社会关系图，然后根据节点的全局等级和本地等级选择下一跳节点。

传统的社区划分需要全局网络信息和节点历史行为数据，难以适用于分布式MSNs或者HMSNs的消息分发。在分布式的探测方法中，每个节点通过探测邻居节点来构建局部社交地图，根据节点间的相遇频度和关系密切程度构建局部社区结构。文献[8]通过联系频度和联系时长生成高质量社会图，支持社区结构的分布式探测，并识别社区间的桥节点和社区重叠关系。文献[9]采用时间联系图模型来分析网络动态特征，将社会性和联系图进行关联，在用户中心度和消息分发角色间建立了强关联关系，便于对消息分发的效率进行测量和分析。

3.1.2 研究小结

基于社会属性的消息分发需要考虑用户间的社会关系来选择中继节点，这种机制通常需要预先探测社区结构；根据历史数据形成的社区结构，难以兼顾社区演化性质且不利于扩展，分布式的社区探测又会产生严重的网络资源消耗。更为突出的问题是，当新增移动节点或社会属性时，极有可能对已建立的社区结构产生较大影响，导致现有方法难以取得理想的效果，甚至失效。

3.2 基于消息内容和节点兴趣的消息分发

3.2.1 研究分析综述

基于消息内容和节点兴趣的消息分发方式主要依托发布/订阅实现消息内容与节点兴趣的匹配。文献[10]提出了基于节点兴趣的消息分发框架SocialCast，根据移动节点间的同嗜性(Homophily)定义了消息分发的效用函数，进而依据效用大小来选择中继节点。在文献[11]所构建的发布/订阅覆盖网系统中，代理节点不但负责消息转发，而且还需对节点间的发布/订阅关系进行维护，在高度动态的环境下，网络资源消耗较大。文献[12]提出以内容为中心的消息分发模型，从目标函数选择和频谱特征分簇的角度来描述消息分发问题，采用随机网络编码来充分利用网络的冗余能力，以提高消息分发效率。文献[13]考虑节点资源限制和消息欢迎度，提出以内容为中心的消息分发方法，目的是最大化消息交付率。为了分析消息欢迎度对分发效率的影响，文献[14]建立了一个通用的分析框架模型，从而为这一类消息分发方法建立了理论依据。

3.2.2 研究小结

在消息分发中采用发布/订阅模式使得消息源节点和目的节点具有解耦特性，从而在动态的网络拓扑下具有较好的适应性；然而代理节点的失效将会造成节点间发布/订阅关系的丢失，导致消息分发过程中断。以内容为中心的消息分发机制需要在移动用户和消息内容间建立关联，且依赖于消息内容的快速、准确发现，导致消息分发效率难以提高[15]。

3.3 基于主动机制的消息分发

3.3.1 研究分析综述

基于主动机制的消息分发是为了弥补MSNs中节点相遇概率较低、机会连接能力不足而采用的手段。在MSNs中，移动用户的移动目的是为了完成某种社会任务，并不是为了将所携带的消息转发出去。这种机会式消息分发的性能优劣性很大程度上取决于用户的移动规律，也就是移动模型是否能够准确预测移动用户的活动规律。为了解决这个问题，在某些特定场景下已经提出了相应的主动式消息分发方法，然而由于缺乏社会属性的考虑，导致消息分发效率并不理想[16]。

文献[17]考虑了MSNs中真实用户的移动情况，提出了一个基于消息摆渡策略的超级节点路由方案，从社会属性的观点来研究主动式消息分发。该方案将普通用户的移动性建模为半马尔科夫模型，而将超级用户路由建模为凸优化和旅行商组合优化问题。在此基础上，文献[18]提出了基于地理特征和社会属性相结合的超级节点路由策略，目标是优化MSNs中的数据广播。该方案根据统计发现移动用户在地理社区中的驻留时间具有幂律分布，因此将用户移动模型建模为一个半马尔科夫模型，计算出地理社区中用户逗留时间的稳态概率分布，进而衡量每个地理社区的移动用户密度。基于此，即研发设计了具有最小化时延或者最大化消息分发效率的静态摆渡路由算法。

3.3.2 研究小结

主动式消息分发方法大都通过部署摆渡节点或者超级节点的形式设计实现[19]，虽然对普通节点的移动规则未做限制，但需要为普通节点的移动性进行建模，或者在全局上发现移动用户的分布规律。

3.4 基于混合拓扑的消息分发

3.4.1 研究分析综述

基于混合拓扑的消息分发大多是从多网共存、异构链路共存的角度开展研究，目的是利用混合拓扑实现流量分担，降低中心网络负载。

针对基础蜂窝网络与Ad Hoc的共存，文献[4]提出了一种视频分发方案，将网关节点的选择问题、网关到终端的路由问题以及视频适配问题进行了形式化描述，然后采用贪婪算法获得近似优化解。文献[20]提出了一个混合式消息分发方法MobiTribe，支持智能手机自主形成MSNs以达成流量分担的目的需求。这种方法能够通过低代价连接提供持续可用消息，而不会对通信费用和电池能量产生过多的损耗。在MobiTribe的基础上，文献[11]提出通过“Always-On”网络基础设施将消息内容复制到智能终端，然后通过机会式通信在终端之间进行消息分发，以弥补单一机会式消息分发所带来的高时延问题。文献[21]首先研究了蜂窝网络和DTN的集成方法，然后使用“存储-携带-转发”的模式进行消息分发，最大化消息交付率和最小化蜂窝网络接入的花费。另外，文献[22-23]将机会网络和D2D(Device to Device)通信相结合，提出了一个基于SNSs(Social Network Services)的流量卸载框架TOSS，用户通过机会式连接在局部区域内分享消息。

针对车载自组织网络中直接连接和间歇性连接共存的情况，文献[24]提出了一个适用于高速路场景的混合式消息分发协议HyDi(Hybrid Data Dissemination Protocol)。在间歇性连接时，采用“存储-携带-转发”的方式进行消息分发；而当存在稳定的直接连接时，采用广播抑制策略以避免链路层的竞争。为了在具有社区结构的网络中实现高效的消息分发，文献[16]提出了一个混合消息分发方案，在社区Ad Hoc子网内可做到直接消息分发处理，而在其它部分采用机会式通信；该方案还在社区内选择一个头节点直接参与消息分发策略的选择，以提升消息分发效率。

3.4.2 研究小结

虽然混合拓扑下的消息分发研究刚刚兴起，但已经在数据流量分担、选路能力提升等方面呈现出明显优势[25]。然而，现有研究还缺乏混合动态拓扑的统一建模和描述机制，不能充分利用混合拓扑的互补特性来提升消息分发能力，也不利于系统的扩展和应用。

4 研究现状总结及未来展望

MSNs的发展趋势揭示出了人类社会关系与无线移动通信的深度融合，利用其承载消息分发任务已成为一种必然需求。然而在特定环境下，如遇突发灾难，传统MSNs将无法满足消息分发效率的要求。HMSNs不但具备移动网络与社会网络、集中式拓扑与分布式拓扑、直接链路与机会链路等共存下的结构互补优势，而且还存在可利用的网络状态弱反馈能力，这种特性使HMSNs在突发灾难环境下具有承载消息分发的潜在优势，已经引起了国内外学者的高度关注[26]。然而，由于资源受限、连接受限、移动受限等因素，导致现有的消息分发方法存在如下具体问题亟需得到解决：

(1) 消息冗余、矛盾现象严重。消息内容来源于移动节点对突发灾难事件的感知，然而受环境因素、资源状态和拓扑结构的影响，缺少建立节点间关联感知的有效机制，既无法保障低冗余的消息生成，也极有可能产生相互矛盾的消息内容，直接影响到消息分发的效率，甚至导致网络状态恶化。

(2) 消息分发选路的效率较低。HMSNs涵盖移动网络与社会网络、集中式与分布式结构以及直接连接与机会连接3个层次的混合特性，在突发灾难环境下，现有方法难以快速地发现网络中存在的可用路径，导致选路效率难以满足实际要求。

(3) 消息分发控制机制的自适应性较差。现有方法主要依据确定性的全局状态来优化节点行为，而在突发灾难环境下难以获得网络状态的确定性反馈，导致移动节点无法选择优化的消息分发策略，网络资源浪费现象严重，网络效用较低。

MSNs在国内的研究已经日趋深入，在机会路由、节点激励、消息传输、安全信任等方面取得了丰硕成果[9，10，12，14，15，25]，极大地推动了MSNs的研究进展，树立了中国在该领域的国际学术声誉。同时，从研究现状可以看出，HMSNs在突发灾难环境下具有潜在的应用价值，美国、日本等国家已将这一领域研究提升到国家战略层面。据此，未来对该方面的研究应将紧密围绕突发灾难环境下资源受限、连接受限、移动受限等典型特征，利用HMSNs的结构互补和网络状态弱反馈优势，从消息生成、快速选路和分发控制3个环节突破影响消息分发效率的关键问题，满足极端环境下的设计应用目标。

5 结束语

本文对移动社会网络MSNs及混合式移动社会网络HMSNs进行对比分析，阐述2种社会网络的研究现状，及对应的消息分发机制存在的问题：目前的研究方法效果不理想，甚至失效；以内容为中心的消息分发机制可能导致较低的消息分发效率；主动式消息分发方法缺乏混合动态拓扑的统一建模和描述机制，不能充分利用混合拓扑的互补特性来提升消息分发能力，也不利于系统的扩展和应用。根据当前研究存在的问题，文章最后提出未来的研究方向。