军事信息系统中基于内容流行度的情报分发模型研究

杨慧杰，刘 娜，李国栋，陈健军

(中国电子科学研究院,北京 100041)

0 引 言

战术信息系统的应用场景具有通信带宽受限、实时性要求高、系统用户数量众多、机动性强、散布范围广等特点，并且随着侦察感知手段的不断增强，情报规模也急剧膨胀。传统的集中存储+发布/订阅的情报分发方式暴漏出越来越多的不足。一是情报分发准确度低，由于情报订阅的粒度难以把握，用户漏定感兴趣情报的情况时有发生，影响了用户对战场态势的掌握和决策的合理性；二是情报服务时效性差，由于情报服务中心和终端用户往往在物理上和逻辑上都有较远的距离，情报的传递过程需要经过多次转发，影响了情报服务的实时性；三是情报服务对资源消耗量过大，由于现有的情报服务都是直接从服务器向终端用户传输情报，不但大量占用了宝贵的通信带宽资源，还给情报服务器带来了较大的负载，增加了资源消耗，间接影响情报服务的质量。

近年来，不少学者和工程师提出了基于用户兴趣模型的情报分发方式，通过朴素贝叶斯、人工神经网络、加权内容相似度等方法建立用户兴趣模型[1-3]，将实时情报与用户兴趣模型的匹配，向用户推送其感兴趣的情报，过滤其不感兴趣的情报，从而实现按需分发。但是此类解决方案依然无法解决情报服务时效性差、资源消耗量大的问题，并且，通过对单个用户订阅信息进行分析建立起的兴趣模型，由于数据量有限等原因，往往不够准确，难以反映该用户的实时需求，容易造成推送情报与用户兴趣的不匹配问题。

内容中心网络(Content-Centric Networks, CCN)的发展为情报服务系统模型设计以及情报分发算法的研究提供了新的思路[4, 5, 6]。内容中心网络是一种新的网络架构，以内容为通信的主体，每个中间节点，如网关、路由器等，都具有一定的存储能力用于缓存通信内容，可以有效提高请求响应的效率，减少对通信带宽的占用，降低内容服务器的负载[7]。但由于中间节点缓存大小有限，因此，应该缓存哪些内容以及如何对缓存进行替换是内容中心网络研究的核心问题之一[8-9]。经典的缓存替换策略有基于最近使用的方法、基于最常使用的方法以及最近使用和最常使用相结合的方法等[7, 10]。最近，大量的研究人员聚焦于内容流行度的研究，提出了基于内容流行度的缓存替换策略[11-14]，例如，将缓存替换看作是一个多臂老虎机问题(Multi-Armed Bandit，MAB)[15-16]，通过在线学习用户的请求信息来估计内容流行度，进而完成缓存替换操作[17-18]。

本文根据移动环境的特点以及情报服务的需求，参考内容中心网络架构，建立了包含“情报服务中心-情报服务站-情报用户”三个层级的移动情报服务系统模型以及情报缓存节点模型；提出了情报内容流行度估计函数，通过对用户情报需求信息的在线学习实时估计情报内容流行度，在此基础上，提出了基于内容流行度的情报分发算法，当缓存节点转发情报时，将最流行的情报进行缓存，为用户提供更加快速的服务响应，降低情报服务器负载，减少通信带宽占用。最后，通过仿真试验考察了新算法的缓冲命中率和收敛时间两个影响算法性能的关键性指标，并与传统算法进行了对比分析，证明了新算法的有效性。

1 相关技术

1.1 情报内容流行度模型

引入内容流行度概念之后，可以根据情报用户的订阅信息，实时分析各类情报的流行度。假定每条情报内容在缓存中占据大小相同的空间，那么将所有可用的情报定义为F={f1,f2,…,fn}，存储于情报内容服务器中，可以被用户订阅使用。将一个相对固定的情报用户群体记作U，在每个周期Δt内，由U产生的情报使用请求记作Du。在实际作战中，这些使用请求是彼此独立的。已有的研究表明，用户的请求通常服从Zipf-like分布，并且与请求的频率、情报的大小和请求变化率无关[19]。因此，对第i个最流行的情报进行使用请求的相对概率为

进一步，在周期Δt内，对情报i进行请求的预期数量可以表示为

其中参数α决定了请求的集中程度。当α=0时，用户请求在所有情报上呈均匀分布，也就是说，所有的情报具备相同的流行度。这个参数越大，请求的集中程度越高。当α=1时，用户请求的分布服从标准Zipf律，在这种情况下，大约80%的用户访问请求集中在最流行的20%的情报上。

现实中，情报的流行度往往是无法预先获知的，需要根据用户的情报订阅请求来实时估计。

1.2 MAB问题分析

多臂赌博机(MAB，Multi-Armed Bandit)在决策理论中是一个经典的问题。在一些特定的领域内已经应用并且被证明是有效的，例如互联网广告匹配等场景中。近年来，部分学者将内容中心网络中的缓存替换问题抽象为MAB问题，为解决缓存替换与优化提供了新的解决途径，然而，缓存替换问题与MAB问题并不完全一致，用MAB问题的求解方法来解决缓存替换问题会丢失一部分的用户请求信息，造成流行度估计的不准确。

MAB模拟一个带有多个拉杆臂的赌博机，用户每个回合可以拉下一个臂，并且会产生一个即时的回报，但是每个臂的回报分布和均值都是未知的，只能通过其之前给出的历史回报值来估计得到。显然，一个臂被拉下的次数越多，对其回报值期望的估计就越可信，同时，高回报率的臂被拉下的次数越多，用户得到的累积回报就会越高。因此，用户为了得到更高的累计回报会倾向于拉动那些回报期望值高的臂，但是为了提高回报期望值估计的准确性又必须去拉下那些拉动次数少的臂。也就是说，在拉动高回报率的臂和拉动次数少的臂之间存在一个悖论。如果已知了每个臂的预期回报，则最优的策略就是每次拉动回报估值最高的臂，这样得到的累积回报称为最佳回报。将实际回报值和最佳回报值之间的差记作r，它是衡量解决MAB问题的策略的有效性的指标。解决MAB问题的目标是寻找一个最小r值。已有的研究表明UCB策略可以实现 的regret，其接近最优值，n为回合数。如果一个回合中多个臂可以同时被拉下，该问题称为联合多臂赌博机问题(Combinatorial Multi-Armed Bandit，CMAB)。有学者给出了一种解决CMAB问题的框架和算法，CUCB，并且证明了该算法r值的上界为 。

目前，MAB问题以及相应的解决算法已经在互联网广告匹配、网络缓存管理等多个领域得到了广泛的应用[18, 20, 21]。

2 基于内容流行度的情报分发

2.1 移动情报服务系统模型

移动情报服务系统在战时要能够为战场上的所有情报用户提供服务，一般来说，移动情报用户多为单兵、车辆等移动节点，具有移动速度快、机动范围广、通信带宽窄、实时性要求高等特点，因此，本文设计了移动情报服务系统模型，分为情报服务中心、移动情报服务站、情报用户三个层级，如图1所示。情报服务中心存储全部的情报信息，通过卫星通信与战场中分布式的移动情报服务站进行通信，提供情报服务；移动情报服务站从情报服务中心获取情报信息并向周边一定范围内的用户提供情报服务，其可以看作一个情报镜像服务器，可以存储周边情报用户中最流行的部分情报。这样，当用户向情报服务站订阅情报时，如果本站已经存储了该类情报，则可以直接提供服务，可以有效提高情报服务效率，减少对无线带宽的消耗，降低情报中心服务器的负载。

图1 移动情报服务系统模型示意图

为了更好的描述情报服务模型以及情报分发算法，本文给出了情报内容服务器和情报缓存节点的定义。

定义1 情报内容服务器(Content Server)：存放于情报服务中心，用于存储全部情报信息，并可以向用户提供情报服务的大型服务器或者服务器集群

定义2 情报缓存节点(Cache Node)：存储部分情报信息，通过向情报服务器获取情报来向本地情报用户提供情报服务。

2.2 情报缓存节点模型

情报缓存节点能够存储整个情报中的一小部分并服务本地的用户请求。尽管存储节点的存储能力有限，但由于它存取速度快、距离用户近的优点，可以为用户提供高速率的服务。当收到用户请求时，如果被请求的情报信息在本地缓存中(称为缓存命中)，该请求被立即响应，被请求的情报信息立即被发送给用户。如果被请求的情报信息不在本地缓存中(称为缓存失效)，节点将连接到情报内容服务器，获取被请求情报并返回给用户。然后，缓存节点将根据一定的规则更新缓存，这种规则即为缓存替换策略。显然，当缓存失效时，从服务器获取被请求情报信息将会给服务器带来额外负载，同时占用网络带宽，并给用户造成较大的服务延时。

情报缓存节点的目标是优化本地存储的情报内容，增强自身服务用户的能力，降低从情报内容服务器取数据的次数。优秀的缓存替换策略能增加缓存命中率。由于缓存节点事先并不知道情报内容的流行度分布，因此它必须实时观测情报用户的请求并找出当前最流行的情报进行存储。

将缓存记作C，其大小为m，当从情报内容服务器获取到情报信息f时，缓存节点根据策略π决定是否对其存储。将当前缓存C中的情报集合记作α，其为服务器上存储的所有情报内容的一个子集。为了提高缓存命中率，α需要根据用户的请求趋势实时动态调整。

情报缓存节点的架构与信息交互关系如图2所示。情报内容服务器模型模拟可向用户提供服务的情报集合。用户模型模拟一个相对固定的用户群体产生的情报请求，该请求服从Zipf-like分布。情报缓存节点包括内容缓存、情报请求处理器、情报请求数据库、缓存替换决策器和缓存替换控制器五个模块。内容缓存器是节点的高速存储模块，情报请求处理器用于接收用户模型的情报请求，并将被请求的情报返回给用户，情报请求数据库用于存放用户请求的历史信息，缓存替换决策器是缓存节点模型的核心，通过特定的缓存替换策略决定如何更新缓存，缓存控制器负责操作本地的内容缓存器，进行情报的获取、删除、添加等，同时可以连接到情报内容服务器获取需要的情报信息。需要注意的是，缓存替换操作在运行过程中根据实际情况按需进行，而非主动进行，这样可以避免额外的带宽消耗和负载增加。

图2 情报缓存节点架构与信息交互关系

用户模型根据输入的参数Du和α，按照相等的时间间隔产生一系列情报请求，并将这些请求发送到缓存节点。每条请求包括时间戳，被请求情报信息ID等。

当缓存节点收到情报请求时，请求处理器被激活。首先，它在本地寻找被请求的情报，如果成功则将该情报直接返回给用户。否则，它把该请求传递给缓存控制器，缓存控制器将连接到情报内容服务器获取情报。在从服务器取得情报信息之后，请求处理器将其返回给用户。然后，请求的相关信息被存储到请求数据库作为下一步缓存替换决策的依据。

2.3 情报分发算法

如果将用户对情报信息的请求作为回报，可以发现，可以将情报缓存的替换问题抽象为一个MAB或者CMAB的问题，但稍有区别。首先，在MAB问题中，如果想知道某个臂的即时回报，则必须拉动该臂，但是在缓存问题中，用户请求哪些情报与这些情报是否存放在缓存中并不相关；其次，把UCB或者CUCB直接应用到缓存问题中，会造成一些有用的信息遗失，分析如下：在CUCB算法中，每类情报信息的指标值按照如下计算

∀f∈C

其中Rf表示情报f总的用户请求次数，Tf表示情报f总的缓存次数，n表示缓存周期的总数。显然，它仅仅考虑了那些对缓存中的情报信息的请求，导致缓存失效的那些用户请求被忽略了；最后，该指标值由两项组成，第一项是平均请求次数，第二项为一个调节因子，意味着当两个情报信息的平均请求次数相等时，缓存次数较少的情报将会被优先缓存。该调节因子的目的是提高缓存次数较少的那些情报的缓存次数从而提高其平均请求次数的可靠性，然而，用户的请求并不依赖于你是否将情报内容进行了缓存。

尽管MAB问题和缓存替换问题之间存在一些差异，但是MAB问题的算法依然被用来解决缓存问题，并且表现出了较好的性能。受CUCB算法的启发，本文基于完整的用户请求信息，为每类情报信息提出了一种新的流行度估计函数，如下

∀f∈F

PEF的第一项表示请求次数的均值，第二项是调节因子。该调节因子意味着，当两个情报的请求次数均值相等时，认为缓存次数多的情报是更流行的，并优先缓存它。

由于缓存节点不会主动从情报内容服务器取数据进行缓存更新(初始化阶段除外，该阶段时间较短)，因此不会给服务器造成额外的负担。此外，也减少了缓存节点和服务器之间带宽资源的消耗。

Algorithm1 ST-PEF

1. Create vectorTf,RfandPEF(f), whose initial values are set as 0.

2.loop：

3.if∃f∈F,Tf=0then/* Initialization phase */

4. Cache these items as many as possible

5.Tf=Tf+1 for all cached items

6.n=n+1

7.else/* Initialization finished */

9. SortPEF(f)

13. n=n+1

14.endif

15. Observe the requests for a period Δt:

16. for each request for itemfdo

17.Rf=Rf+1

19. Get itemffrom cache and send it back to user

20.else

21. Get itemffrom server and send it back to user

23. Remove an itemf′ from cache,f′∈Cexpried

24. Store itemfinto cache

25.endif

26.endif

27.endfor

28.gotoloop

3 实验分析

3.1 实验设计

为了验证新提出的ST-PEF缓存替换策略的有效性，我们使用C++语言实现了第三章中模型和算法，并且实现了几种经典的缓存替换策略进行性能对比分析：

(1)Random，每个周期内，情报缓存节点随机选择一组情报进行主动缓存；

(2)Myopic，一种基于“最近最少使用”(Least Recently Used，LRU)的主动式缓存替换算法。起始时刻，缓存节点随机缓存一组情报信息，每个周期，缓存节点保留上一周期使用过的情报信息，并将上一周期未使用的情报信息用随机选取的情报替换；

(3)ε-greedy(ε= 0.07)，一种解决MAB问题的相对简便但性能良好的算法；

(4)CUCB，解决CMAB问题的经典算法；

(5)Oracle，预先知道情报内容实际流行度，并缓存最流行的m个情报内容的一种算法，实现了缓存命中率的上限值。

试验中采用的主要参数取值如表1所示。

表1 仿真试验参数取值

我们考虑用整体缓存命中率和收敛速度两个指标来评价情报缓存节点的性能。

(1)整体缓存命中率：缓存命中数量与所有用户请求数量的比值，这是最基本和最重要的指标，其他的多数性能，如情报服务时延等，都直接或者间接依赖于它；

(2)收敛速度，从起始时刻到取得稳定的实时缓存命中率的时长(实时缓存命中率是指一个周期中缓存命中次数和情报使用请求总数的比值)。

3.2 实验结果与分析

在第一组实验中，为了评估缓存替换策略的收敛性，我们记录了每个周期的实时缓存命中率。如图3所示，ST-PEF能够比CUCB和ε-greedy更快的到达稳定状态。这是因为ST-PEF流行度估计函数中的调节因子会加快收敛速度，而CUCB却倾向于测试那些缓存次数少的情报内容，导致收敛速度较慢。ε-greedy策略的实时缓存命中率波动较大，是因为它会以一个较小的概率随机存储情报内容，降低了缓存命中率。

图3 实时缓冲命中率随时间的变化关系

第二组实验，如图4所示，显示了情报内容流行度对缓存命中率的影响。当Zipf分布参数从0(均匀分布)变化到1(标准Zipf律)时，除Random之外的所有策略的缓存命中率均上升。这是因为Random不考虑情报内容流行度，而其他策略均或多或少地基于对流行度的估计进行缓存替换。由于ST-PEF中对流行度的估计更为准确，因此缓存命中率表现更好。

图 4 缓冲命中率与Zipf分布参数α的关系

第三组实验分析了缓存大小对命中率的影响。在仿真中，缓存大小从10变化到110(相对于缓存占所有情报总大小的比率从0.5%增加到了5.5%)，其他参数的取值按照表1。图5显示了所有缓存策略的总体命中率。显然，缓存越大，更多的流行情报能够被存储，缓存命中率也更高。正如预期，Random的缓存命中率与缓存大小占所有情报总大小的比率一致。

图5 缓存命中率与缓存大小m的关系

最后，第五组实验分析了不同用户请求数量对缓存命中率的影响。如图6所示，随着每个周期内情报用户请求数量的增加，整体缓存命中率也逐步提高。这是因为请求数量越多，使得对情报内容流行度的估计就更准确并且更快。

图 6 缓存命中率与Du的关系

4 结 语

针对移动情报系统中情报分发问题，本文设计了包含情报服务中心、移动情报缓存节点以及情报用户三个层级的情报服务系统模型，对情报缓存节点模型的结构、流程进行了设计，提出了情报内容流行度的估计函数，并在此基础上，提出了基于内容流行度的情报分发算法ST-PEF。在仿真试验中，我们设计了两个指标：整体缓存命中率和收敛速度，对新提出的ST-PEF算法和经典算法进行了对比分析，结果表明，ST-PEF算法与经典的Random、Myopic、CUCB、ε-greedy等算法相比，具有更快的收敛速度和更高的整体缓存命中率，在移动情报服务系统中可以为用户提供更高质量和更低成本的情报服务。