基于朋友圈和节点感知的内容中心MSN 路由机制*

张卜聆，王兴伟+，李 婕，易 波，黄 敏

1.东北大学 计算机科学与工程学院，沈阳110169

2.东北大学 信息科学与工程学院，沈阳110819

1 引言

随着智能手机等移动设备的普及，移动社交网络（mobile social network，MSN）发展迅速，其相关技术成为近年来的研究热点。当移动节点在应用场景中以自组织形式进行数据传输服务时，移动社交网络是一种将网络与节点社会特性相结合的时延容忍网络[1]。由于节点的移动性使得端到端的路由呈现间歇性特点，导致数据传输时延、投递率等方面受到了限制，因此如何设计高效的内容分发和数据传输方式就成为现阶段研究的重点和难点。

近几年，大部分互联网内容以密集的信息形式存在，如视频、音频、文件流等，据思科（Cisco）发布的可视化网络指数预测报告可知，截至2017 年，全世界的互联网用户数量已达34 亿，全球移动数据流量将在2017 年至2022 年间增长7 倍[2]。互联网的研究方向逐渐趋于高效率、大规模、更具安全性的网络信息的接收与转发，TCP/IP 在网络的安全性、可靠性、移动性、可扩展性以及路由策略等方面渐渐显现出了不足之处。信息中心网络（information-centric networking，ICN）不同于现有的支持端到端通信的TCP/IP 互联网体系结构，它是通过使用内容标识符将内容和位置分离[3]，形成松散耦合的通信模式，着重于内容本身以及数据的自有属性，能很好地支持移动性，其天然的网内缓存机制，能够大大降低网络负载，实现高效的数据分发。但是，将信息中心网络架构引入移动社交网络中以解决端到端通信难问题的研究，还处于起步阶段，主要研究现状如下：

文献[4]提出了一种选择性缓存方法和概率转发方法，以降低缓存冗余和最小化获取内容的预期成本。同时，提供了一种可扩展的方法来维护路由器内缓存内容的路由信息。文献[5]设计和分析了两种转发方式：盲转发和提供者感知转发。通过减少兴趣包和数据包的数量，提供者感知转发可以在很大程度上优于盲转发方案，尤其是在效率方面。但在特定应用场景下，简单的盲转发是最佳解决方案。文献[6]基于节点兴趣的社会规律性和距离度量分别设计了兴趣包和数据包的路由方案，同时提出了基于节点友好度量的网络缓存方案降低传输时延。文献[7]考虑了用户的流动性和视频的流行程度提出了基于ICN 的移动视频在5G 网络中的缓存方法，利用移动性来减少频繁切换带来的检索延迟。文献[8]通过对车辆的社区相似度和隐私等级进行评价，设计了一种动态概率缓存方案。文献[9]考虑了节点的当前位置和节点的剩余能量，以改善数据传输的过程中网络性能。同时基于节点间的距离设计高速缓存策略，以减少未来请求内容的检索时间。如何高效使用ICN 网内缓存空间对于快速检索和准确定位内容至关重要，文献[10-11]利用软件定义网络（software defined network，SDN）的集中控制能力将内容信息进行集中管理。此外，文献[10]提出的ICN 缓存内容定位机制联合使用布隆过滤器和压缩感知可有效地表示缓存的内容。文献[11]提出了一种基于最大树的社区划分方案，根据划分的结果设计了社区内和社区间路由机制。文献[12]根据信息项需求和网络的缓存功能制定了一种缓存感知路由方案，用最小的传输成本计算路径。文献[13]表明社区家庭是传播信息的重要因素，通过使用社区家庭能更快地传播消息。

以上缓存路由算法虽然在不同方面具有一定性能上的优势，但是在移动节点划分时，没有考虑节点缓存内容的类型，而且在数据传输时缺乏对内容源、目的地的感知。基于以上问题，根据节点的实际运动情况，提出了基于朋友圈和节点感知的内容中心MSN 路由机制。本文的研究工作主要包括以下几点：明确了节点模型的功能表，使节点具有一定的感知能力；利用节点缓存内容相似性以及节点间关系强度构造朋友圈；根据朋友节点的关系，提出相适应的缓存机制以维护朋友圈；设计基于节点感知的路由算法；利用NS3（network simulator 3）[14]对提出的路由机制进行仿真实现，并与其他算法进行对比分析。

2 问题描述

2.1 网络模型

网络由节点和节点之间的边组成，网络模型G(V,E)表示无向连通图，其中V是具有存储、转发和处理能力的节点集合，表示网络中的移动设备；E是边集合，表示网络中的移动设备之间存在的链路。

2.2 节点模型

每个移动设备需要维护5 个表：内容存储库（content store，CS）、转发信息库（forwarding information base，FIB）、未决兴趣表（pending interest table，PIT）[2]、已决兴趣表（settled interest table，SIT）和朋友关系表（friendship table，FST）。其中，CS 作为存储部件，暂存内容对象及其名字的映射。FIB 记录了节点间的转发规则，是路由转发的主要依据。对于已经转发出去但对应的数据包未返回的兴趣包，PIT 记录兴趣包对应的接口信息。设计的SIT 记录PIT 中已经请求到的数据包所对应的兴趣包的名字前缀与请求该内容的节点ID，使节点具有一定的感知能力。节点的社交性通过在ICN 中增添FST 体现，该表记录本地节点ID、与邻居节点的关系以及邻居节点的缓存内容类型，是兴趣包路由至最大概率目的地的重要依据。

3 算法设计

3.1 社交度量

在MSN 中，因为节点具有移动性，使得网络拓扑一直在变化，因此节点之间难以存在稳定的路径。为了促进信息交换，选用交换频次、联系时长和缓存相似性衡量节点之间的社会关系。同时，考虑到节点的移动特性，结合了链路延迟、延迟抖动、阻塞率等因素在消息路由过程中选择合理的中继节点，实现高效路由。

3.1.1 交换频次

其中，Ci,j表示节点i和j互换内容的频率，Exi,j表示节点i向j提供内容的次数，Exi表示节点i向所有节点交换内容的次数。

3.1.2 联系时长

其中，CTi,j表示节点i和j之间的联系时长，表示节点i与中间节点k1的联系时长，∑cti表示节点i与其他节点的联系时长。

3.1.3 缓存相似度

其中，节点i和节点j的内容条目的交集即为相似性的内容。CCsimi,j表示节点i和j缓存内容的相似程度，CEi表示节点i的内容条目。

3.1.4 数据交换概率

利用交换频次、联系时长以及缓存相似性社交度量来衡量节点之间的联系强度。

其中，wi,j表示节点i和j之间的联系强度。

对于i和j之间的链路可靠程度，还额外考虑链路延迟de、延迟抖动dejit、阻塞率blo等情况。因此，节点i、j之间的链路可靠程度计算公式如下：

其中，α1+α2+α3+α4=1，Rei,j体现了节点i、j之间进行数据交换的可靠程度，由此可得节点i向节点j发送兴趣包的概率P(i,j)：

3.1.5 节点度中心性

其中，Cd(v)表示节点v的度中心性，用于选举簇头节点。度中心性越大，越适合选为转发节点进行信息的传递。如果节点i和j之间存在连接，那么link(vi,vj)=1。为了简化，接下来用Aij等价替换link(vi,vj)。

3.1.6 节点相似度

存在多个度中心性高的节点时，通过评价节点的相似度进一步甄选簇头节点。dij为节点i和j的相似度。若两节点相连，Aij=1，否则为0。dij的值越小，则两节点的相似度越高。

3.1.7 节点与朋友圈关联度

当节点与朋友圈内节点具有相似的兴趣爱好时，说明节点与该朋友圈之间具有关联度，用Ri,com表示。其中，m为朋友圈节点总数，r=(vi,vk)为两节点之间的关联度。当缓存相似度达到一定阈值时，r=1；否则为0。

3.1.8 朋友圈特征热度值

3.2 朋友圈构造算法

在MSN 中，具有相似的缓存内容通常联系程度密切，易形成一个朋友圈。根据这个特点，本文基于缓存内容相似度和节点中心性构造朋友圈。先选举度中心性高且相似度大的节点作为簇头节点，然后围绕簇头节点自底向上聚类朋友圈节点，直至网络所有节点划分完毕，形成不同的朋友圈。整个划分过程伪代码如下：

3.3 缓存机制

3.3.1 朋友圈的缓存特征

在MSN 中，朋友圈的结构受节点社会关系的影响。考虑到节点依据缓存内容构造朋友圈，对CS 的缓存置换策略引入了内容热度和多样性可以维护朋友圈的稳定性。依据二八原则，热度内容即节点感兴趣的内容在节点的CS 中占据主导地位，而缓存非热度内容以保证朋友圈缓存内容的多样性。

其中，n为节点内热度内容类型的数量，可实验测定。

3.3.2 节点缓存策略

设计中的节点有一定的概率对热度内容进行缓存，这里采用式（4）联系强度来衡量路径上节点是否缓存该内容，这样做的好处在于联系越紧密的节点，其兴趣越相似，则满足朋友节点请求该内容的命中率越大。而对于非热度内容，仅缓存至请求节点，以减少在路径上不必要内容缓存而造成资源浪费。同时，由于朋友节点越来越具有相似性，邻居节点间的缓存相似度需要控制在阈值之下：

3.3.3 节点置换策略

置换策略分为两种情况：当节点的缓存区已满时，需要采用适当的策略置换缓存内容；当两个节点缓存相似度超过阈值时，需要置换热度缓存内容以降低相似度。采用基于内容热度和多样性相结合的缓存置换策略，可有效提高CS 命中率。

热度Heat为CS 缓存条目在历史时间段的热度值与当前时间段热度值的加权和，即：

其中，μ+λ=1，当需要调节缓存相似的节点时，考虑节点的热度内容向与其缓存内容相似性最低的邻居节点转移。当节点对的缓存相似性均低于阈值时，调节结束。

3.4 路由机制

基于朋友圈和节点感知的内容中心MSN 路由机制主要解决的是兴趣包在多跳情况下的路由问题。先在朋友圈内进行内容的检索，如若CS、SIT、PIT、FIB 表中未检索到相关内容，则表明朋友圈内没有所请求的内容。此时，将兴趣包发给簇头节点，以转向全局控制器进行外部路由。兴趣包在朋友圈内路由过程伪代码如下所示：

依据全局控制器对全局缓存内容信息的掌握情况，请求节点可以获取对目的节点ID 的感知。当请求节点接收到控制信息后，将目的节点的ID 加入兴趣包路由路径中，从而使兴趣包具有感知能力，找到目的节点的缓存内容。兴趣包在朋友圈间路由过程伪代码如下所示：

考虑到网络的动态变化，需要对传统的ICN 数据包的名字前缀加以改进，即数据包返回时，兴趣包记录的路径信息会被依次添加到内容名的前面，使数据包具有感知能力。当沿原路径的方向返回时，若某条链路处于断开状态，计算两节点的其余通路，并选取与请求者FST 关系度高的作为路由线路，依此路由直至请求者。

4 仿真与结果分析

4.1 仿真环境及场景设置

设计的路由机制通过NS3 仿真平台进行仿真实现，使用Infocom 2006 数据集（Infocom06 dataset，http://www.crawdad.org/cambridge/haggle/20090529/），仿真场景设置如表1 所示，表中TTL 表示生存时间（time to live）。

Table 1 Configuration of simulation表1 仿真配置

4.2 性能对比

将提出的基于朋友圈和节点感知的内容中心MSN 路由机制（friend circle and node awareness based content centric MSN routing mechanism，FACMR）与基于ICN 的缓存感知路由机制（cache-aware routing in ICN，CAR）[12]、基于社区对目的零认知的MSN 多拷贝路由机制（home-based multi-copy routing with zeroknowledge about destination in mobile social network，HBMRZ）[13]从缓存置换率、误包数、平均路由时延和投递开销方面进行性能评价。

4.2.1 缓存置换率

如图1 所示，设置缓存区大小分别为50 MB 和500 MB，FACMR 在缓存空间足够大的时候能够保证缓存信息的资源兼具多样性和稳定性，取得较低的缓存置换率。HBMRZ 的缓存置换率相对偏高是因为该算法在第一阶段扩散内容的副本。而CAR 算法通过全局资源的管理使资源合理分布。

Fig.1 Cache replacement rate图1 缓存置换率

4.2.2 误包数

如图2 所示，HBMRZ 算法误包数最高，是因为在MSN 中，HBMRZ 包传递具有很大的时延。而FACMR 算法中，包的传递均是在具有逻辑连接的朋友节点上进行，不仅有更大的几率获得内容，同时在TTL 生存周期内保证有较大几率完成包的传递。而CAR 算法，由于需要全局资源的协调控制，始终保持消耗资源最少，但相应的路由时延增加会导致较高的误包数。

Fig.2 Number of packet loss图2 误包数

4.2.3 路由开销

如图3 所示，三者之间在路由开销指标略有差异，但不是很明显，FACMR 算法在路由开销上与对比算法基本相同，能够保证性能的稳定性。

Fig.3 Routing overhead图3 路由开销

4.2.4 平均路由时延

如图4 所示，HBMRZ 算法时延较大是因为节点连接的随机性，包的传递也具有随机性。而FACMR算法和CAR 算法是基于ICN 设计，使得节点的相互联系更加紧密，因此平均路由时延均低于HBMRZ 算法。但由于CAR 算法用时间换取网络开销，因此平均路由时延高于FACMR 算法。

Fig.4 Average routing delay图4 平均路由时延

5 结束语

本文针对ICN 与MSN 相结合的网络环境，提出了基于朋友圈和节点感知的内容中心MSN 路由机制。在该机制中，利用节点中心性以及缓存内容的类型进行朋友圈构造。同时提出了相适应的节点缓存、置换策略，进行朋友圈维护。设计了节点感知型路由算法，能够依据圈内的朋友关系实现高效路由。如何更深层次挖掘节点的社会关系，利用圈内关系来提高数据分发性能是下一步的研究方向和重点。