Caching Mechanism Based on Popularity and Relationship in Content-Centric Vehicule Social Network
Wei Chen,, Yi Bo,*School of Computer Science and Engineering, Northeastern University, Shenyang, Liaoning 110169, China通讯作者: 易波(E-mail:yibobooscar@gmail.com)
收稿日期:2020-03-28网络出版日期:2020-06-20
基金资助: |
Received:2020-03-28Online:2020-06-20
作者简介 About authors
魏晨,东北大学计算机科学与工程学院,研究生,主要研究领域为移动机器人网络、群体智能、移动社交网络。
本文主要承担工作为缓存决策策略设计及缓存替换策略设计。
Wei Chen is an M.S. student at the College of Computer Science and Engineering of Northeastern University. Her research interests include mobile robot network, Swarm intelligence and mobile social network.
In this paper she is mainly responsible for the design of cache decision strategy and cache replacement strategy.
E-mail:
易波,东北大学计算机科学与工程学院,讲师,主要研究领域为下一代网络与服务计算、编排,网络功能虚拟化等。
本文主要承担工作为系统整体架构设计以及文献调研。
Yi Bo is currently a lecturer at the College of Computer Science and Engineering, Northeastern University, Shenyang, China. His research interests include next generation network and service computing, orchestration, network function virtualization and etc.
In this paper he is mainly responsible for the overall framework design of system and literature research.
E-mail:
摘要
【目的】针对目前车载社交网络(Vehicular Social Network,VSN)中存在的缓存冗余大、效率低等问题,提出适用于动态VSN的缓存决策策略和缓存替换策略。【文献范围】文章重点调研国内外对于信息中心网络(Information-Centric Networking,ICN)的架构、ICN缓存、VSN的缓存机制,以及对于两者相结合的研究。【方法】本文首先以缓存内容流行度和节点间朋友关系度为指标判断是否缓存内容。然后将内容存储库进行划分,以增加缓存的多样性。最后基于节点的重要程度制定缓存替换策略。【结果】本文设计的缓存策略明显提高了兴趣包的响应效率,避免了由于频繁切换带来的损失,同时在保证包投递率的前提下,大大减少了网络开销。【局限】由于现实的局限性,使得无法在真实环境下进行实验,导致实验结果过于理想化。【结论】将ICN技术应用于VSN中,利用其内容和位置分离能更好支持终端移动性的特点,以及网内缓存机制的优势,可以降低网络延迟,实现快速的内容交付。
关键词:
Abstract
[Objective] Aiming at the problems in the Vehicle Social Network (VSN), such as large cache redundancy and low efficiency, two strategies related to cache decision and cache replacement adapting to the dynamic VSN are proposed. The fast response to user-requested content is realized through the in-network caching, which satisfies the real-time needs of passengers for data, and provides valuable reference for subsequent research on the cache mechanism in the Content-Centric Vehicule Social Network. [Scope of the literature] This paper focuses on the architecture design of Information-Centric Networking (ICN), the caching mechanism of ICN and VSN, and the researches of combining both. [Methods] Firstly, this paper uses the real-time monitoring of the popularity of cached content and the evaluation of the friendship among nodes as the basis for judging whether to cache the content. Then, the content storage is divided to increase the diversity of the cache. Finally, a cache replacement strategy is formulated based on the importance of the nodes. [Results] The cache strategy designed in this paper significantly improves the response efficiency of interest packets and avoids the loss caused by frequent switching. At the same time, under the premise of ensuring the packet delivery rate, the network overhead is greatly reduced. [Limitations] Due to the limitation of reality implementation, it is impossible to carry out the experiment in real environment, leading to overly ideal experimental results. [Conclusions] Applying ICN technology to VSN can effectively use the characteristcs of content and position separation, which can better support terminal mobility. Also the advantages obtained from in-network caching mechanism reduce network latency and achieve rapid content delivery.
Keywords:
PDF (6727KB)元数据多维度评价相关文章导出EndNote|Ris|Bibtex收藏本文
本文引用格式
魏晨, 易波. 内容中心VSN中基于流行度和朋友关系的缓存机制. 数据与计算发展前沿[J], 2020, 2(3): 66-74 doi:10.11871/jfdc.issn.2096-742X.2020.03.006
Wei Chen, Yi Bo.
引言
车载社交网络(Vehicular Social Network,VSN)是由车辆自组织网络(VANET)和社交网络的相关概念和功能组合而成的移动通信系统[1,2],它是一种允许车辆、行人及基站互联的网络架构,其中涉及到了移动网络、卫星网络以及传统通信网络等多种网络结构。作为移动社交网络(Mobile Social Network,MSN)的一个典型应用场景,VSN为驾驶人和乘客提供舒适的体验,已经引起了广泛关注。但是,众多车辆网络服务的暴增,使得传统的互联网架构已无法满足日益增长的网络需求。以网内缓存为主要特征的ICN可以使用户从附近节点而不是远程服务器检索数据,它的缓存技术有助于降低获取内容所需的网络时延、减小由于链路或者节点失效对内容获取带来的负面影响[3]等。这种通信模式的全新变革带来许多优势,比如高效的内容分发、天然地支持移动性[4],故成为可能代替IP的新型范式。命名数据网络(Named Data Networking, NDN)是一个比较成熟的ICN体系结构[5],它依据内容请求和网内缓存有效解决了传统通信方式中因无法就近获取所需内容而导致网络资源浪费的问题。由于ICN的种种优势,越来越多的研究者将ICN技术应用到VSN中。但VSN的移动性令拓扑频繁变化,导致节点之间的连续性无法保证,端到端的路径传输无法维持,所以需要充分挖掘用户之间的关系以及人类的移动特性,判断是否缓存内容,使用户可以及时获取需要的信息。虽然目前对于ICN缓存策略的研究已经有了阶段性的创新,但是如何将ICN更好的应用于VSN中以适应动态环境并增强其缓存效率,仍值得分析和研究。
本文将利用ICN中的NDN网络架构和VSN相结合,侧重于研究符合车辆快速移动场景下的缓存决策,提出一种基于内容流行度和朋友关系的缓存决策策略和考虑到节点重要性的缓存替换策略,以解决动态环境下的缓存放置问题,将ICN网内缓存发挥出最大的优势,从而达到快速获取内容的目的,满足车载用户的需求。
1 相关工作
缓存机制主要解决了缓存什么(What)、在哪缓存(Where)以及怎么缓存(How)的问题。根据内容缓存的位置,缓存机制可分为路径相关缓存(on-path caching)[6]和路径无关缓存(off-path caching)[7]。ICN默认将数据包在每个反向路由器上都进行缓存,称为 CEE(Cache Everything Everywhere)缓存决策机制。事实上,这在某种程度上会造成资源浪费,并且过高的缓存替换率会导致缓存内容稳定性下降,影响缓存命中率。针对这一缓存机制的不足,文献[8]提出了一种基于边缘缓存的ICN智能内容分发解决方案,根据内容的流行度、用户的移动性和社会关系决定是否缓存,从而有效提高内容传输效率。缓存替换策略旨在选择合适的替换算法更新缓存内容。在ICN中,根据车辆间的缓存策略对内容存储(Content Store,CS)中的内容进行替换。先进先出(First In First Out,FIFO)、最近最少使用机制(Least Recently Used,LRU)、最少频繁使用(Least Frequently Used,LFU)是针对ICN缓存提出的基本缓存策略。文献[9]提出了一种基于值的缓存替换方案,使用实用函数从延迟、流行度等参数确定从缓存中所要删除的项,在命中率、网络内延迟等方面都有一定的优势。文献[10]结合缓存的新鲜度要求提出了一种最小新鲜优先(LFF)缓存替换策略。基于传感器未来事件的时间序列预测,剔除无效缓存内容,提高了服务器命中率、减少了响应延迟。
移动自组织网络中引入ICN新型范式是一个新的跨领域的研究[11],文献[12]阐述了尽管 ICN 在移动无线环境中具有潜在的优势,但仍有几个重大的研究挑战有待解决,包括本地缓存内容的发现、能源效率、实际部署问题。在 NICNC 机制[13]中,路由器根据其对社区的节点重要性进行缓存决策,使缓存的内容在时空分布上更加合理。文献[14]提出一种博弈论方法来共同确定 ICN 中的缓存和定价方案,使用概率模型研究中继节点和内容提供者之间的非合作游戏的纳什策略,其中 ICN 缓存成本随内容受欢迎程度而变化。文献[15]针对以信息为中心的无线传感器网络(ICN-WSN)提出了一种协同缓存策略。该策略由节点介数的缓存大小、数据替换频率的缓存决策和内容值的缓存替换算法三部分组成。在文献[16]中,作者通过从VANET的角度研究ICN的命名、缓存等不同方面,简要讨论了ICN在车辆环境中的适用性,还指出了主要的挑战以及未来研究方向。在文献[17]中,作者通过联合考虑NDN中的内容流行度、底层网络拓扑、转发策略和路径缓存服务提出缓存放置策略,该策略在任意拓扑结构下,都有较好的响应速度。Su等人[18]提出了一个以内容为中心的车载网络(CCVN)的新框架,内容服务器中的内容根据车辆密度和内容流行度确定的优先级进行存储。但是这项工作并没有考虑移动性问题。目前国内外****在ICN缓存和置换策略等方面已经取得了一定的成果,但是对于如何更好的将ICN应用于VSN中以适应环境动态变化,有效提高缓存效率方面还面临诸多挑战。
针对上述问题,本文在已有ICN缓存策略的基础上,提出了一个适合于动态VSN的缓存决策策略和缓存替换策略。根据内容流行度和朋友关系这两个指标,每个节点判断是否缓存内容。然后为了增加缓存的多样性,满足不同用户的请求,根据流行度对内容存储库进行分区。最后提出一种缓存替换策略,当节点缓存区已满时,合理进行置换。本文所提出的机制在一定程度上可以弥补当ICN应用于VSN时在动态环境下缓存方面的不足,减少网络开销,避免频繁的缓存替换操作,以适应车载用户的动态请求。
2 节点模型
首先,本文利用内容流行度和朋友关系作为判断是否缓存内容的重要依据,所以在每个具有NDN功能的移动节点的原始结构中添加两种数据结构,分别是用于实时监控全网节点中本地内容流行度变化的内容流行度监控表(Content Popularity Monitor Table,CPMT)和用于记录节点之间关系信息的关系表(Relational Table,RT),在此对这两种数据结构进行详细介绍。2.1 CPMT结构
本文以 CPMT 实时监测全网各节点本地内容流行度的变化作为预测内容的流行度依据。通过 CPMT 对采样时间段内节点中不同类别兴趣包的到达次数进行统计,判断指定内容是否流行。其中CPMT 模块的数据结构如表1所示,包括获得某段时间内指定内容的请求次数以及预测指定内容的请求次数。Table 1
表1
表1内容流行度监控表
Table 1
$t_{1}^{{}}$ | $t_{2}^{{}}$ | $t_{3}^{{}}$ | |
---|---|---|---|
Type1 | Creq1(Type1) | Creq2(Type1) | Creq3(Type1) |
Type2 | Creq1(Type2) | Creq2(Type2) | Creq3(Type2) |
… | … | … | … |
新窗口打开|下载CSV
2.2 RT结构
RT是在NDN结构基础上结合节点移动性需求添加的节点结构,主要用于记录节点之间的关系。RT结构如表2所示,每个条目包括节点ID、内容类型和节点中心度。在本设计中规定,当节点之间的关系度达到一定阈值时定义为朋友节点,只有朋友节点之间可以相互交换缓存内容,以避免不必要置换导致的额外网络开销。Table 2
表2
表2关系表
Table 2
节点ID | 内容类型 | 节点中心度 |
---|---|---|
Com_A/1 | Type1,Type4… | Centrality1 |
Com_A/2 | Null | Centrality2 |
… | … | … |
新窗口打开|下载CSV
3 基于内容流行度和朋友关系的缓存决策算法
3.1 本地内容流行度监测
由于节点的独特性,每个内容类型可能在不同节点具有不同的流行度,因此我们基于每个节点的本地请求频率设计内容类型流行度预测方法。并采用次数对周期进行更新,即当有新的兴趣包到达时,设置的计数器次数累加,当次数达到规定的阈值N时,计数器清零,进入下一周期,依次循环统计。所以,对于节点$i$,内容类型$Typek$在周期$n$内的流行度$P_{Typek,n}^{i}$的计算方法用公式(1)表示。由上式可知,对于每个内容类型的流行度由该内容类型在周期$n$内的请求次数决定。
节点$i$上的内容类型$Typek$在周期$n$内的请求次数$Creq_{n}^{i}(Tpyek)$的初始值设置为上一时刻的请求次数$Creq_{n\text{-}1}^{i}(Tpyek)$,之后根据上两段时间内,该内容类型请求变化值进行调整,调整值用公式(2)表示。
其中,$\alpha +\beta =1$,越靠近当前内容请求次数,加权值越重,即$\beta \ge \alpha $,符合最近的变化应当分配更高权重这一特征。综上所述,节点$i$上的内容类型$Typek$在周期$n$内的请求次数估计方法用公式(3)表示。
3.2 缓存区划分
通常,对内容的请求数量遵循 Zipf 定律,所以对于普通车辆节点考虑根据内容流行度将 CS 划分成流行区 CS_P 和非流行区 CS_N。其中,CS_P 占缓存区 80%;CS_N 占缓存区 20%。分区的好处在于:减少查找 CS 带来的时延,增加缓存的多样性。3.3 朋友关系度
因为每个节点的兴趣偏好有所不同,具有相似性的节点汇集成一个社区,相比于社区外的节点联系更频繁。在本设计中,利用节点之间的平均联系时长和联系频率刻画节点之间的关系,关系度越高的节点请求内容的相似度越高,成为一个社区的可能性就越大,并将度中心性大的节点设为簇头,以维护社区内和社区间的联系。节点之间的平均联系时长用公式(4)表示。
其中,$T$表示当前时间,$fij(t)$表示节点$i$和节点$j$在时间$t$内是否联系,如果节点$i$和节点$j$保持联系,那么${{f}_{ij}}(t)=1$,否则为0。平均联系时长越长,它们从时间上描述的关系越可靠。
节点间联系频率用公式(5)表示。
其中,$N\text{con}(i,j)$表示节点$i$和节点$j$之间的联系次数,$N\text{con}(i)$表示节点$i$和网络中所有节点的联系次数。
综上所述,朋友关系度用公式(6)表示。
$Fr\text{i}(i,j)$衡量了节点$i$和节点$j$之间的关系度,为判断是否缓存内容提供了主要依据。其中,$\alpha $和$\beta $分别是平均联系时长和联系频率的权重因子,且$\alpha \text{+}\beta \text{=}1$。因为在数据包的传输中必须衡量的一个因素是数据包内容的尺寸,在兴趣包的设计中需要将朋友节点作为其中的一个信息进行传递,导致平均联系时长占比更重,故在本设计中设置$\alpha \text{=}0.6$,$\beta \text{=0}\text{.4}$。
3.4 基于内容流行度和朋友关系的缓存决策策略
基于本地内容流行监控度表以及簇头节点的集中收集,及时反馈上层节点,提出了适合快速移动场景下的缓存机制。缓存策略根据内容的流行程度和目的节点是否为朋友节点这两个因素进行缓存,具体缓存策略分成四种情况:(1)对于返回的数据包流行度高且是朋友节点请求的,无论此内容在本节点的 CS 中是否存在节点,都将缓存在 CS_P 中且标记为重点缓存对象。
(2)对于流行度高,但返回数据包是非朋友节点请求的,此内容之前在 CS 表的流行区,仍缓存在 CS_P 中且标记为重点缓存对象,若内容之前在 CS_N 或者在 CS 中查找不到此内容,则缓存在 CS_P 中,但不标记为重点缓存对象。
(3)对于流行度不高的内容,但是朋友节点请求的数据包,若此内容之前在 CS_P,则缓存在 CS_N 中且标记为重点缓存对象,若内容在 CS 中查找不到此内容,则缓存到CS_N 中。
(4)对于流行度不高的内容且不是朋友节点请求的数据包,则放弃缓存。
考虑到部分数据包在本社区没有请求到内容,最后通过簇头节点将该兴趣包转发出去。当数据包返回到请求者时,应该考虑是否需要将数据包备份至社区内的簇头节点。即兴趣包在社区内进行路由经过簇头节点时,簇头节点会对其返回的数据包的流行程度进行预测。若返回的内容数据流行程度高于一定阈值,则将该兴趣包标记为需要备份至簇头节点,待数据包返回至请求节点时,需要转发数据包至簇头节点进行备份,以便满足社区内其他节点的需求,这样可以降低用户获得所需信息的平均时延,提高包交付率。
3.5 缓存替换策略
上述中,如果节点的缓存空间已满时,需要根据缓存替换策略合理地缓存更符合需求的内容。大量的研究表明,缓存替换策略的选择对网络整体性能的影响并不大,通常默认采用 LRU 作为替换策略。所以在本设计中,也将采用 LRU策略置换出 CS_P 或者 CS_N 中的内容,并对标记为重点缓存对象的内容给予一次“逃生”机会,即若缓存替换内容为重点缓存对象时,会清空该标记获得一次保留机会,继而寻找其他最近最久未使用的内容进行置换,直至新的缓存空间容量满足现有需求。在该过程中考虑到缓存对象内容的重要性,可以有效避免频繁的置换操作,增加缓存内容的稳定性。4 仿真实现与性能评价
4.1 仿真平台
本文提出的CVR机制基于机会网络环境(Opportunistic Network Environment,ONE)仿真软件实现,ONE是一款针对机会网络的仿真实现设计的软件[19],基于离散事件模拟引擎,在每次模拟时间间隔内更新各个模块内容,各模块之间相互配合完成整个模拟功能。ONE仿真平台的主要模块功能和类介绍如下。(1)核心模块(Core)
Core 模块包含了模拟器的主要功能,包含的主要类如表3所示。首先读取配置文件,对仿真环境进行初始化操作,然后完成各个模块的配置工作,最后初始化模拟时间,在时间间隔内更新各个模块。
Table 3
表3
表3Core 模块主要类
Table 3
类名称 | 功能描述 |
---|---|
Node | 节点 |
SimScenario | 获取和存储模拟运行的仿真场景 |
Connection | 两个节点之间的连接 |
Coord | 保存节点二维坐标并执行简单的算术和转换 |
NetworkInterface | 负责主机之间连接的网络接口 |
Message | 节点传输的消息 |
World | 设置场景,负责更新它们的位置和连接 |
新窗口打开|下载CSV
(2)移动模块(Movement)
移动模型规定着网络内节点的移动规则。既可以使用 ONE 中默认的六种移动模型,同时也可以根据需求自定义模型。在本设计中采用最短路径地图移动模型(SPMB,ShortestPathMapBasedMovement)模型,同时加入了兴趣点(如商城,学校),构成兴趣点移动模型(PoI Movement Model,PIMM),使车辆具有人性化的移动,而不仅仅是随机选择一个目的地作为下次的移动方向。移动模块包含的主要类如表4所示。
Table 4
表4
表4Movement 模块主要类
Table 4
类名称 | 功能描述 |
---|---|
Movement Model | 所有移动模型的父类 |
Random Walk | 随机移动模型 |
Map Based Movement | 基于 Map 的随机移动模型 |
Shortest Path Map Based Movement | 基于 Map 的最短路径移动模型 |
Working Day Movement | 基于用户行为的移动模型 |
新窗口打开|下载CSV
4.2 仿真设置
本文仿真场景设置如表5所示,共设置115个节点,其中100个节点基于PIMM移动模型运动, 15个节点基于固定轨迹运动。Table 5
表5
表5仿真配置
Table 5
属性 | 值 |
---|---|
数据传输速率 | 250kBps |
车辆传输范围 | 200m |
车辆缓冲区大小 | 100MB |
产生兴趣包的时间间隔 | 25~30s |
兴趣包大小 | 0.5~1M |
数据包大小 | 1.5~3M |
车辆速度 | 5~30m/s |
移动节点数量 | 115 |
移动节点接口数量 | 2 |
新窗口打开|下载CSV
4.3 评价指标
本文使用包交付率、平均时延和网络开销比率等三个性能指标将设计的缓存机制和传统NDN缓存策略CEE+LRU,以及传统NDN缓存策略CEE+FIFO对比。各对比指标的定义如下。(1)包交付率
包交付率指的是所有交付的包的数量与所有发起包的数量的比值,交付率越高,表示兴趣包的响应效率越高,计算方法用公式(7)表示。
其中,$delivered$表示所有交付包的数量,$created$表示所有发起包的数量。
(2)平均时延
平均时延指的是所有包从创建到成功交付所需要的平均时长,计算方法用公式(8)表示。
其中,$delayofMessagei$表示包$i$交付成功经历的时长。
(3)网络开销比率
网络开销比率衡量包为了达到目的节点需要转发的次数,侧面反映了节点缓存内容的有效性。计算方法用公式(9)表示。
其中,$relayed$表示所有生成包被转发的总次数。
4.4 性能评估
图1-3显示了不同缓存机制下的各项指标呈现情况。图1
新窗口打开|下载原图ZIP|生成PPT图1不同缓存机制下的包交付率
Fig.1Delivery ratio under different caching mechanisms
图2
新窗口打开|下载原图ZIP|生成PPT图2不同缓存机制下的平均时延
Fig.2Average delay under different caching mechanisms
图3
新窗口打开|下载原图ZIP|生成PPT图3不同缓存机制下的网络开销比率
Fig.3Network overhead ratio under different caching mechanisms
从图1可以看出,本文所提机制CVR的包交付率随着运行时间的增加逐渐提升,最终比运行初期提高了6%~7%,基本维持在95%。相比CEE+FIFO和CEE+LRU机制分别提高了2.5%和1.3%。首先,这是因为CVR机制会根据缓存内容的重要程度有选择性的在路由器中进行缓存,不像CEE机制在每个路由器上都进行缓存。其次,在运行初期,由于节点对兴趣包的请求具有一定的随机性和偶然性,所以对内容流行度的预测并不准确,导致包交付率较低。随着运行时间的增加,CPMT 表构建逐渐完善且预测较仿真初始阶段更为准确,而且朋友关系较为稳定,同时考虑这两方面因素使得缓存中的内容更接近节点需求,故包交付率越来越高。
从图2可知,运行初期,由于节点对缓存内容流行度并不敏感,导致时延变大。但是随着时间的增加,CVR机制的平均时延相比CEE+FIFO和CEE+LRU机制分别下降17.1%和9.7%,这是因为遵循 Zipf 定律,大部分空间用于缓存流行度高的内容,以便响应社区内其他节点的快速请求。同时,20%的缓存空间保留给朋友节点对于流行度略低的内容请求,增加了缓存的多样性,这使节点更易获取到所需要的信息,从而有效降低了延迟。从网络开销比率来看,CVR机制在缓存替换策略中考虑到了节点缓存内容的重要性,从而避免了频繁的置换操作,最终使得开销减少,相比CEE+FIFO和CEE+LRU机制分别下降10.3%和7.6%。
5 展望与下一步工作
本文通过对现有缓存技术进行分析,针对以往研究中对于VSN中快速移动场景下的缓存机制例如缓存冗余等不足,提出了基于内容流行度和朋友关系度的内容中心VSN缓存决策算法。其次,根据节点的重要程度制定缓存替换策略,有效避免了频繁的置换操作。为验证本文方法的可行性和有效性,对算法进行了仿真实现,并与基准机制进行对比分析。从实验结果可以看出,本文设计的缓存机制明显的提高了兴趣包的响应效率,并在保证包投递率的前提下,大大的减少了网络开销。下一步工作将会考虑缓存机制中及时类型的数据缓存,以及关于这类数据的过滤和缓存问题。利益冲突声明
所有作者声明不存在利益冲突关系。参考文献 原文顺序
文献年度倒序
文中引用次数倒序
被引期刊影响因子
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[C]// ,
[本文引用: 1]
[C]// ,
[本文引用: 1]
[C]// ,
[本文引用: 1]
[C]// ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[C]// ,
[本文引用: 1]
[Z]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[J]. ,
[本文引用: 1]
[C]// ,
[本文引用: 1]