物联网中时间驱动的ICN缓存机制研究

赵国锋，邢 媛，段 洁，田瑞林

(1. 重庆邮电大学 未来网络研究中心，重庆 400065; 2. 重庆市光通信与网络高校重点实验室，重庆 400065)

0 引 言

随着互联网技术与应用的飞速发展以及互联网用户的快速增长，传统的因特网体系架构逐渐暴露出可扩展性差、安全性低、移动性支持不足等诸多问题。为了解决这些问题，学术界提出了一类以内容为中心的新型网络体系架构，统称为信息中心网络(information centric networking, ICN)，典型的ICN研究项目有data-oriented network architecture (DONA)[1]，publish-subscribe internet routing paradigm (PSIRP)[2]，network of information (NetInf)[3]，content-centric networking (CCN)[4]和 named data networking (NDN)[5]。在这类ICN架构设计中，每个路由器都具有内置缓存的功能，旨在为消费者提供各种各样的缓存服务，同时缓解快速增长的网络流量对网络带宽造成的严峻压力。由于ICN采用基于名字的路由方式，因此，消费者可以通过内容名从缓存节点直接获取请求的信息。

ICN网络级内置缓存的特性能够减轻网络负载、降低内容传播时延和提高缓存资源利用率[6]，因此，众多研究者期望将ICN思想应用到物联网(internet of things, IoT)架构设计中，目的是实现因特网中数据的快速交互[7]。Pentikousis等[8]提出了ICN机制部署于物联网环境的因特网草案，草案中描述了几个ICN应用场景，讨论了将ICN机制应用于IoT架构存在的关键问题，提出了在IoT中运用命名数据的思想。使用命名数据无疑是将ICN思想应用于IoT部署的关键因素。命名数据可以使信息对网络层透明、可识别，并且能够有效地管理IoT内的协作。事实证明，因特网草案中的研究成果对ICN应用于IoT领域的科学研究作出了突出贡献。相应地，Heidemann等[9]也证实了命名数据在IoT中的诸多优势，同时描述了一种支持命名数据和网内处理的软件架构。

大量异质缓存节点参与物联网应用将会引起可扩展性及兼容性等问题。特别地，有限的硬件资源将使大量网络设备在存储、计算和通信能力等方面受到限制。Song等在文献[10]中解决了硬件资源限制问题，主要依据CCN基本模型和核心思想提出了以内容为中心的方案，将资源有限的弱网络设备中的超载任务(如存储、发布和获取)映射到资源充足的强网络设备中，最终实现了资源的共享和信息的交互。节点映射方案虽然解决了弱网络设备资源受限问题，但强弱网络设备间频繁的任务调度容易产生大量的信号交换开销。

ICN网络内置缓存及移动性支持等特性使其可以很好地支持物联网应用场景(如家庭网络，车联网等)。Ravindran等[11]详细说明了如何将ICN机制应用于家庭网络，同时强调了构建一个能够处理家庭网络中设备、服务和用户需求等多样性的同质平台的重要性。ICN基于名字的路由方式和网络内置缓存的特性使其在克服车联网(vehicular ad hoc networks, VANETs)[12]中诸如快速变化的拓扑、短暂和间接的车辆连接等方面具有明显优势。对于VANET-ICN中的缓存策略，Deng等[13]认为采用简单的处处缓存策略(leave copy everywhere, LCE)[14]会降低缓存利用率，进而浪费缓存资源。因此，提出了VANETs中运用NDN思想的分布式概率缓存(distributed probabilistic caching, DPC)策略。DPC策略中，节点依据用户需求、车辆重要性以及接收者和发送者间的相对运动共同做出缓存决策。分布式策略中每个节点独立地执行缓存策略，减少了节点间不必要的信号交换开销。

Quevedo等[15]认为IoT环境中的用户更趋向于请求最新的信息，因此，提出了用户驱动的信息新鲜度机制，其中信息新鲜度指内容在缓存中逗留的时间。首先IoT用户在兴趣包中添加请求内容的新鲜度值，其次内容源依据不同用户的新鲜度要求为内容设置恰当的新鲜度值。缓存节点中的内容在新鲜度值到期前被移除，从而避免了网络中存储过时的信息。然而，用户请求过去某时刻产生的历史信息时，新鲜度机制中的节点通过简单地内容名匹配，误解为缓存中已存有请求的信息，进而不断地用最新的信息作为应答，而不是将兴趣包转发至内容源。最糟糕的情况为用户永远接收不到正确的信息。

为了满足物联网用户对信息准确度，尤其是时间维度的严格要求，本文采用以信息为中心的ICN思想，提出了IoT环境中时间驱动的普适性缓存方案。方案主要由时间匹配算法和缓存策略两部分组成，时间匹配算法用于向消费者返回时间容忍阈值内的内容，缓存策略用于对到达节点的数据包做出缓存决策。

1 缓存问题分析

IoT环境中各种各样的应用程序产生的信息量不计其数，且相同应用在不同时刻产生的信息可能截然不同。当物联网用户对信息准确度提出要求，尤其是时间维度要求较高时，已有的ICN缓存机制不再适用。图1说明了已有的ICN缓存机制的操作过程。例如，ConsumerA发送名字为“/Name1/Latest Temperature”的兴趣包，兴趣包发送路径上的路由器解析该名字，并查看缓存中是否存有ConsumerA请求的内容。依据已有的ICN缓存机制，若节点匹配到Name1则将内容返回用户。图1中路由器R6的内容存储(content store,CS)中恰巧存有名字为Name1的条目，则R6将数据包沿兴趣包发送路径原路返回至用户。然而，用户收到的信息可能为某时刻过时的温度信息，而非最近的温度信息。

图1 已有的ICN缓存机制Fig.1 Existing ICN cache mechanism

现有的ICN缓存机制中，节点收到携带有最新消息的数据包时，通过简单地内容名匹配，错误地认为缓存中已经存储的信息与新收到的信息相同，从而拒绝更新陈旧的信息。该节点收到后续请求时，仅通过匹配内容名，将缓存中已有的旧信息直接返回用户，不再向其余节点或内容源转发兴趣包。若用户请求的是历史信息，则返回的内容恰好符合要求。若用户请求的是最新信息，则用户最终得到了错误的内容。

新鲜度机制中的节点通常缓存最新的内容，因此能够解决用户请求最新信息的问题。然而当用户请求相对久远的历史信息时，新鲜度机制中的缓存节点通常用较新的信息作为响应，而不是向上游节点或内容源继续转发用户请求。

当IoT环境中用户对数据和信息的准确度提出要求，尤其是时间维度要求较高时，已有的ICN缓存机制和用户驱动的信息新鲜度机制均不再适用。本文提出时间驱动的普适性缓存方案，主要用于解决信息准确度的问题，尤其是时间维度的问题，简单的方案示意图如图2所示。方案在兴趣包、数据包和CS条目中添加时间戳字段(Timestamp)，时间戳在满足准确性要求的同时辅助节点缓存内容。兴趣包中Timestamp用于指定用户请求某特定时刻产生的内容，Threshold指用户能够容忍的时间阈值。数据包中Timestamp指其所携带内容的产生时间。节点CS中Timestamp指所存储内容的产生时间。从CS表中可以看出，内容名相同但内容产生时间不同，对应的具体内容则不同。图2中，ConsumerA发送名字为“/Name1/2015.07.02 00:48:50/5s”的兴趣包，网络节点通过匹配名字和时间戳后，路由器R6将CS中“/Name1/2015.07.02 00:48:52”对应的内容返回至用户，返回的信息显然符合用户要求。

图2 时间驱动的普适性缓存方案示意图Fig.2 Schematic diagram for time-driven universal caching approach

2 时间驱动的普适性缓存方案

时间驱动的普适性缓存方案中的时间指在兴趣包和数据包包头中添加具体时间戳信息；普适性指节点不仅缓存最近产生的内容，而且缓存历史性内容。添加时间字段能够为用户提供更准确的信息。普适性能够满足IoT应用需求，一些历史信息可以直接从缓存中而不是内容源处获得，减少了用户获取内容的时延。

2.1 普适性缓存概述

时间驱动的普适性缓存方案主要包括时间匹配算法和缓存策略两部分。时间匹配算法的主要操作对象为兴趣包和节点CS条目中的时间戳。缓存机制的主要操作对象为缓存节点。图3对时间驱动的普适性缓存方案进行概述，主要包括兴趣包的发送和数据包的返回，具体操作过程如下所述。

图3 时间驱动的普适性缓存概述Fig.3 Overview of time-driven universal caching

用户请求内容时，发送携带有容忍阈值的时间戳兴趣包。路由器收到兴趣包后执行时间匹配算法，查看CS中缓存的内容能否满足用户对信息准确性的要求。若匹配成功，则将数据返回用户。若匹配失败，则将兴趣包转发至下一跳。若缓存节点均未存储用户请求的信息，则将兴趣包发送至内容源。图3中用户发送兴趣包，Router A和B均执行时间匹配算法，结果发现Router B中缓存的内容符合用户要求，则将CS中对应数据返回用户。

数据包沿兴趣包发送路径返回时，沿路节点若有剩余缓存空间，则直接存储该内容；若无，则依据内容流行度和时间请求概率做出缓存决策。对于具体的缓存决策，若节点CS中无与数据包同名的内容，则依据内容流行度做出缓存决策；若有，则依据时间请求概率做出缓存决策。图3中Router A收到数据包后执行缓存策略做出是否缓存内容的决定。

2.2 时间匹配算法

用户请求内容时，兴趣包中除了包含内容名外，同时还包含用于指定内容产生时刻的时间戳和时间容忍阈值。兴趣包到达缓存节点时节点执行算法1所示的时间匹配算法。将兴趣包与CS中内容名进行匹配；若匹配到内容名，则将兴趣包中时间戳和缓存中所有同名内容的产生时间分别做差并取绝对值，将时间差值在阈值范围内且绝对差最小的内容返回用户。若缓存节点未匹配到用户请求的内容，则将兴趣包转发至下一跳。若用户在缓存节点未获取到准确的内容，则将兴趣包转发至内容源。若内容源处仍未匹配到满足用户要求的内容，则丢弃兴趣包，向用户通告请求失败。

用户请求某时间段内产生的内容时，兴趣包中时间戳字段为请求内容的起止时间点。节点收到兴趣包后执行时间匹配算法，将符合用户要求的部分内容返回用户。由于节点缓存容量非常有限[16]，单个节点一般不能完全存储同内容名下某段时间内产生的所有内容，因此，需要继续向其余节点转发兴趣包直至用户请求时间段内的所有内容都被获取到。

Algorithm1: Time matching algorithm

Input: interest I % I is consists of “/name/timestamp/threshold/nonce”

Output: return the matched content

1: for all itemsiin CS do

2: MatchName (I.name,i.name)

3: if I.name==i.name then

4: Calculate absolute difference:Di←|I.timestamp-i.timestamp|

5: if theDi≤I.threshold then

6: Store itemiin Array[ ]

7: else

8: Forwarding I to the next hop

9: end if

10: else

11: Forwarding I to the next hop

12: end if

13: end for

14: return itemiwho owns the minimalDiin Array[ ]

2.3 缓存策略

返回的数据包到达缓存节点时，若节点有剩余缓存空间，则直接存储该内容；若节点缓存空间已满，则依据缓存节点CS中是否存在相同内容名的内容选择不同的缓存策略。具体地，若CS条目中未查询到同名内容，则调用基于内容流行度的缓存策略；若CS中查询到同名内容，则调用基于时间请求概率的缓存替换策略。

2.3.1 基于内容流行度的缓存策略

由于途经路由器的请求类型和数量不同，因此相同内容在不同路由器处的流行度一般也不同[17]。每个路由器对应一张本地内容流行度列表，主要用于存放不同名内容在该路由器处的流行度。此处内容流行度指内容名相同的内容被请求的概率，故流行度P计算公式为

(1)

(1)式中：N表示网络中总的内容名数目；n表示内容名；countn表示周期T内内容名n对应的内容被请求的次数。对内容名相同但时间戳不同的内容请求次数进行累加求和得到countn。

当数据包到达缓存节点且缓存空间已满时，若CS中未查询到与数据包内容名相同的内容，则依据流行度列表中内容流行度P做出缓存决策。若新到达数据包的同名内容流行度在节点流行度列表中最小，则不缓存该内容。若非最小，则采用LRU(least recently used)替换策略，即用新数据包替换列表中流行度值最小的内容。

2.3.2 基于时间请求概率的缓存替换策略

时间请求概率(time request probability)Ptr指随着时间间隔的变化，内容被用户请求的概率，其中时间间隔指内容生成时刻与当前时刻之间的时间差。物联网环境中用户普遍偏爱请求最近产生的信息，时间间隔越短，内容被用户请求的概率越大；时间间隔越长，内容被用户请求的概率越小。由此可见，用户请求内容的概率随着时间间隔的增加而减小。由于指数分布可以用于表示独立事件的时间间隔的概率分布，因此，可以合理假设时间请求概率服从参数λ为1的指数分布。时间请求概率Ptr计算公式为

Ptr=e-Δt,Δt≥0

(2)

(2)式中：Δt=|tc-tg|，tc表示当前时间(current time)，tg表示内容生成时间(generate time)，Δt表示二者的时间间隔。从(2)式中可以看出，随着时间间隔的增加，用户请求对应时刻内容的概率急剧下降，并呈指数式衰减。

当数据包到达缓存节点时，若CS中查询到与数据包内容名相同的内容，则依据时间请求概率做出缓存决策。时间请求概率可以预测同名但生成时间不同的内容被用户请求的概率。依据收到数据包中的时间戳以及CS中存储的同名内容的多个时间戳分别计算出每个时间戳下同名内容的时间请求概率。若新到达数据包的时间请求概率最小，则不缓存该数据包；若非最小，则替换相同内容名下时间请求概率最小的内容。

3 仿真与分析

3.1 参数设置

本文使用MATLAB对所提算法进行仿真验证。网络拓扑如图4所示，采用简单的3级分层结构，其中节点0表示内容源，节点1—13表示缓存路由器。假设用户请求到达速率服从泊松分布，网络中总的内容种类为10 000。CS中最初缓存的内容名及对应的时间戳由随机生成器产生，并存储于矩阵中，每行代表一个内容条目。兴趣包主要由用户指定的内容名、时间戳和容忍阈值构成，其中内容名和时间戳在仿真过程中依旧采用随机数生成器产生，时间容忍阈值的设置范围为1～5s。返回的数据包中除内容名外还携带该数据所产生时刻的时间戳信息。

图4 仿真拓扑图Fig.4 Network topology for simulation

仿真主要验证了不同参数设置下单节点的缓存命中率和用户收到信息的准确率。由于兴趣包随机产生，所以每次仿真运行得到的缓存命中率和信息准确率有一定的差异。为了减少误差，此处采用多次测量求平均值的方法。仿真共轮询了100次，最终缓存命中率和信息准确率取值为多次测量结果的平均值。

3.2 结果分析

缓存命中率是测量网络性能的基本准则之一，命中率的高低直接决定了缓存算法是否有效，仿真中节点缓存命中率指命中节点中内容名的概率。图5仿真了单个节点处兴趣包到达速率对缓存命中率的影响。其中，原生方案指没有运用时间驱动的普适性缓存方案，即兴趣包、数据包和CS条目中未添加时间戳字段。从图5中可以看出，在相同的用户请求速率情况下，时间驱动的普适性缓存方案的缓存命中率高于原生方案。原因在于，原生方案的节点CS中无时间戳选项，内容生存期到期前不会主动替换缓存中的旧内容，节点可能存储了过多的历史内容，而未存储最新产生的内容，因此不能满足用户对内容多样性的需求，从而缓存命中率较低。随着兴趣包到达速率的增加，2种方案的缓存命中率均呈现下降趋势。原因在于，节点的缓存容量有限，能够存储的具体内容种类也有限，因此，在总的请求次数不断增加的情况下，命中率呈下降趋势。

图5 请求速率对缓存命中率的影响Fig.5 Impact of request rate on cache hit ratio

以CS表存储的内容条目数代表节点缓存大小，条目数越多表示节点缓存容量越大。图6仿真了单个节点的缓存容量对缓存命中率的影响，其中，兴趣包到达速率为2 000 包/s。随着节点缓存容量的增加，节点能够缓存的内容种类也增加，因此，不同方案的节点缓存命中率均呈现上升趋势。当缓存容量较小时，节点能够缓存的内容数量也较少，用户驱动的信息新鲜度机制偏向于缓存最新的内容，而本文提出的时间驱动的普适性缓存方案不仅缓存最新内容，而且缓存历史内容，因此，时间驱动的普适性缓存方案的命中率高于用户驱动的信息新鲜度机制。当缓存容量足够大时，用户驱动的信息新鲜度机制的缓存命中率高于普适性缓存方案。原因在于，用户驱动的信息新鲜度机制中节点有足够的容量缓存历史内容，并且同名内容仅被缓存一次，而时间驱动的普适性缓存方案中节点通常缓存不同时间段产生的同名内容，节点中内容名的总数目小于CS条目数。虽然足够大的缓存容量使得信息新鲜度机制的缓存命中率高于普适性缓存方案，但其准确率低于普适性缓存方案。

图6 缓存容量对缓存命中率的影响Fig.6 Impact of cache capacity on cache hit ratio

信息准确率指用户收到信息的准确程度，具体计算方式为用户接收到的正确信息数除以总的请求次数。图7仿真了2种不同缓存方案的信息准确率。在相同的参数设置下，时间驱动的普适性缓存方案的信息准确率高于用户驱动的信息新鲜度机制。原因在于，用户驱动的信息新鲜度机制中节点仅存储了网络中最近产生的内容。当用户请求某个历史时刻的信息时，节点仅通过匹配内容名从而向用户返回信息，而未考虑用户请求的是哪个时间点的内容，因此，向用户返回的内容不是其所请求时刻的内容，从而降低了用户收到信息的准确率。

图7 请求速率对信息准确率的影响Fig.7 Impact of request rate on information accuracy

图8仿真了缓存容量对信息准确率的影响，其中兴趣包到达速率依然设置为2 000 包/s。从图8中可以看出，用户获取信息的准确率随缓存容量的增加而提高。原因在于，节点缓存容量越大，能够缓存的内容条目数越多。随着缓存容量的增加，时间驱动的普适性缓存方案可以获得相对稳定且高的准确率，用户驱动的信息新鲜度机制的信息准确率呈现线性增长趋势。从图8中可以看出，相对于新鲜度机制，普适性缓存方案获得了更好的稳定性。

图8 缓存容量对信息准确率的影响Fig.8 Impact of cache capacity on information accuracy

图5中普适性缓存方案的缓存命中率相对于原生方案平均提高了14%。图7中普适性缓存方案的信息准确率相对于用户驱动的信息新鲜度机制平均提高了9.7%。图8中缓存容量变化时，普适性缓存方案的信息准确率相对于用户驱动的信息新鲜度机制平均提高了31.47%。因此，本文所提方案能够有效地提升网络性能。

4 总结与展望

本文在物联网架构设计中采用ICN思想，提出了时间驱动的普适性缓存方案。方案主要包括兴趣包匹配和数据包缓存2部分。节点通过精确匹配时间戳，返回与用户请求契合度最高的内容。数据包返回时，节点依据内容流行度和时间请求概率对其做出缓存决策，同名但时间戳不同的内容可以在同一节点共存。仿真结果显示，时间驱动的普适性缓存方案能够有效地提高缓存命中率和信息获取的准确率，满足了物联网用户对信息准确度，尤其是时间维度的严格要求。本文未来研究工作将通过仿真平台ndnSIM进一步验证所提算法的有效性；对于缓存策略，将考虑内容相似度对缓存决策的影响。

[1] KOPONEN T,CHAWLA M,CHUNB-G,et al.A data-oriented (and beyond) network architecture[C]∥ACM SIGCOMM ’07.Kyoto,Japan:ACM Press,2007:181-192.

[2] AIN M, TROSSEN D,NIKANDER P,et al.D2.3-architecture definition,component descriptions,and requirements[EB/OL].(2009-02-17)[2017-08-25].http:∥www.psirp.org/files/Deliverables/FP7-INFSO-ICT-216173-PSIRP-D2.3_Architecture Definition.pdf.

[3] DANNEWITZ C, KUTSCHER D, OHLMAN B, et al. Network of information (NetInf)-An information-centric networking architecture[J].Computer Communications,2013,36(7):721-735.

[4] JACOBSON V, SMETTERS D K, THORNTONJ D, et al. Networking named content[C]∥ACM CoNEXT ’09. Rome, Italy: ACM Press, 2009: 1-12.

[5] ZHANG L, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73.

[6] ARALDO A, MANGILI M, MARTIGNON F, et al. Cost-aware caching: optimizing cache provisioning and object placement in ICN[C]∥2014 IEEE Global Communications Conference (GLOBECOM). Austin, TX, USA: IEEE Press, 2014: 1108-1113.

[7] 赵阔, 邢永恒. 区块链技术驱动下的物联网安全研究综述[J]. 信息网络安全, 2017(5): 1-6.

ZHAO K, XING Y H. Security survey of internet of things driven by block chain technology[J]. Netinfo Security, 2017(5): 1-6.

[8] PENTIKOUSIS K, DAVIES E, OHLMAN B, et al. ICN baseline scenarios and evaluation methodology [EB/OL]. (2013-07-15) [2017-08-25].https:∥tools.ietf.org/pdf/draft-pentikousis-icn-scenarios-04.pdf.

[9] HEIDEMANN J, SILVA F, INTANAGONWIWAT C, et al. Building efficient wireless sensor networks with low-level naming[C]∥The eighteenth ACM symposium on Operating systems principles. Banff, Alberta, Canada: ACM Press, 2001: 146-159.

[10] SONG Y, MA H, LIU L. Content-centric internetworking for resource-constrained devices in the internet of things[C]∥2013 IEEE International Conference on Communication Communications (ICC). Budapest, Hungary: IEEE Press, 2013: 1742-1747.

[11] RAVINDRAN R, BISWAS T, ZHANG X, et al. Information-centric networking based homenet[C]∥2013 IFIP/IEEE International Symposium on Integrated Network Management. Ghent: IEEE Press, 2013: 1102-1108.

[12] 袁超, 张浩, Gulliver T A. 车联网中协作车—车通信系统在N-Rayleigh信道下ASEP性能分析[J]. 信息网络安全, 2016(3): 40-46.

YUAN C, ZHANG H, GULLIVER T A. ASEP performance analysis of vehicle-to-vehicle communication system overN-Rayleigh fading channels in IoV[J]. Netinfo Security, 2016 (3): 40-46.

[13] DENG G, WANG L, Li F, et al. Distributed probabilistic caching strategy in VANETs through named data networking[C]∥2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). San Francisco, CA, USA: IEEE Press, 2016: 314-319.

[14] BERNARDINI C,SILVERSTON T,FESTOR O.A comparison of caching strategies for content centric networking[C]∥2015 IEEE Global Communications Conference(GLOBECOM).San Diego,CA,USA:IEEE Press,2015:1-6.

[15] QUEVEDO J, CORUJO D, AGUIAR R. Consumer driven information freshness approach for content centric networking[C]∥2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Toronto, Canada: IEEE Press, 2014: 482-487.

[16] CHOI N, GUAN K, KILPER D C, et al. In-network caching effect on optimal energy consumption in content-centric networking[C]∥2012 ICC. Ottawa, Canada: ACM Press, 2012: 2889-2894.

[17] WEI T M, CHANG L, YU B Y, et al. MPCS: a mobility/popularity-based caching strategy for information-centric networks[C]∥2014 IEEE Global Communications Conference (GLOBECOM). Austin, TX, USA: IEEE Press, 2014: 4629-4634.

(编辑：张 诚)