基于群体用户行为的移动网络合作缓存方法研究

硕 士 学 位 论 文基于群体用户行为的移动网络合作缓存方法研究专业名称：信息与通信工程 基于群体用户行为的移动网络合作缓存方法研究摘要近年来，将内容缓存到网络边缘侧逐步成为移动网络中一种减少系统传输代价和提升用户体验的有效方式。随着移动网络的不断发展，我们可以利用网络架构优势更进一步地提升移动网络中内容服务的效率。与此同时，“共享经济”的概念逐渐在社会上引起广泛的关注，人们开始意识到，在资源调度和配置过程中，对于具有相似兴趣或行为的用户群体的描述能够有效地提升资源的利用效率，为移动网络中的资源共享问题提供了新的思路。针对现有的移动网络缓存策略中存在的缓存针对性不强、内容传输效率低等问题，本文提出了一种基于群体用户行为的移动网络合作缓存方法（Group User Behavior Aware Collaborative Caching Method，GUCC），其主要贡献点如下：1. 对用户的移动网络使用详细数据（Usage Detail Records，UDR）进行了分析，并研究了用户移动网络访问行为中所存在的内容及位置特征维度下的多样性、可预测性和群体性。2. 提出了一种基于群体用户行为的基站合作模型，利用用户的访问内容特征和访问位置特征分别构建用户相似网络，提出加权相似网络融合（Weighted Similarity Network Fusion，WSNF）算法融合内容相似网络和位置相似网络，根据得到的融合相似网络对用户聚类，并依据用户类获得基站间的合作关系。3. 提出了一种基于基站间合作关系的移动网络缓存策略，综合考虑了基站间数据传输所带来的传输代价和基站合作带来的整个系统的命中率的提升，以最大化命中率和最小化传输代价为优化目标进行求解，依据博弈论，本文对整个系统的多目标优化问题进行了分析，从而求得问题的最终解。4. 针对实际应用中存在的缓存更新问题，提出了一种合作关系驱动的缓存更新方法。具体提出了一种基于移动网络用户访问行为在基站上的分布差异的关键点发现方法，通过对基站中的关键点上的用户访问行为进行监控，决定基站间合作关系的变化时间，从而进行缓存更新。上述方法通过实验验证，相较于传统的方法有更好的命中率和传输代价的表现。关键词：合作缓存, 群体用户行为, 移动网络, 缓存更新 AbstractCaching content on the edge of the network has recently been considered as an efficient way to reduce the transmission cost and improve the users experience in emerging mobile networks. With the development of the mobile network, there are more advantages of the structure that can be taken to further increase the efficiency of the service. At the same time, a rise of Sharing Economy has recently brings to more and more attention of the society, people begin to realize that in the process of resource scheduling and configuration, the description of user groups with similar interests or behaviors can effectively improve the utilization efficiency of resources, and thus provide a new method for the resource sharing in the mobile network.To solve the problem that the caching is not accurate enough and to improve the low transmission efficiency in the existing mobile network caching strategy, we proposed a Group User Behavior Aware Collaborative Caching Method (GUCC) in this paper, and the main contribution is showed below:1. We make an analysis of the Usage Detail Records (UDR) and explore the heterogeneity, predictability and the group behavior of users during the access of location and content. 2. We design a collaborative relationship model based on group user behavior. We use content and location similarity network to depict the group behavior. Weighted Similarity Network Fusion (WSNF) algorithm is raised to solve the fusion problem of largescale similarity network. And the user groups are formed based on the fused network. The collaborative relationship among the base stations is established according to the user groups they serve.3. We propose a caching placement scheme that based on the collaborative relationship among base stations. In the scheme, both the cost of the transmission among base stations and the hit ratio of the requests are considered. A multi-objective optimization problem is solved to maximize the hit ratio and minimize the transmission cost at the same time. We analyze and solve the problem according to the Game Theory.4. To solve the cache updating problem during the real application, we propose a cache updating method driven by the base station cooperative relationship. In detail, we propose an articulate point discovering method based on the distribution of users access to the base stations. In this method, we decide the updating time according to the access behavior on the articulate point to finally update the cache.The numerical results show that the proposed method achieves performance gain in terms of both hit rate and transmission cost.Keywords：Collaborative caching, group user behavior, mobile network, cache update目录摘要IAbstractII1绪论11.1研究背景及意义11.2国内外研究现状41.2.1用户群体行为研究现状41.2.2移动网络缓存研究现状81.3本文的主要内容及结构安排122移动互联网用户行为特征分析142.1数据集介绍142.2用户多样性和可预测性特征分析142.3用户群体性特征分析162.4本章小结193基于群体用户行为特征的基站合作关系模型203.1群体用户行为特征模式213.2大规模加权相似网络融合算法223.3基于用户相似网络的基站合作关系模型273.4本章小结314基于基站合作关系模型的缓存方法324.1基站侧缓存模型324.2缓存策略性能评估344.2.1多种用户数性能评估344.2.2不同缓存空间性能评估374.2.3稳定性评估384.3本章小结385合作关系驱动的缓存更新方法395.1基于关键点的合作关系更新方法395.1.1关键点发现方法概述395.1.2基于用户行为分布的关键点发现方法425.2合作关系驱动的缓存更新实例分析465.3本章小结486总结与展望506.1全文总结506.2研究展望51参考文献53致谢61附录 攻读硕士期间发表的学术论文62III1 绪论1.1 研究背景及意义近年来，网络数据流量开始大量从传统网络向移动网络转移。根据Cisco项目组最近的报告显示，在2021年移动数据的流量将会达到49.0EB1。不断增长的数据流量将会导致传输链路的压力不断增大，超负荷的数据流量会导致传输效率降低而影响用户体验。如何缓解整个移动网络的负载压力已成为了一个重要的问题2。在这样的背景下，计算的一个新趋势是将资源和服务更多地向网络的边缘倾斜3，移动边缘计算（Mobile Edge Computing，MEC）就是在这样的背景下诞生的一种将计算从核心部分迁移至网络边缘的技术。边缘计算中除了强调对计算资源的需求之外，还强调了对计算数据源的需求3，即在移动网络中，基站上所缓存的内容要能够满足服务和应用的需求。从用户的角度来说，人们往往希望自己能够在尽可能短的时间内获得尽可能多的质量尽可能好的内容，归根结底就是对内容传输速率和内容传输质量的要求。其中内容传输质量受信道等因素的影响，而内容传输速率问题可以通过在基站侧建立内容缓存得到很好的改善，那么缓存的内容和策略就在很大程度上影响着该问题的改善程度。从运营商的角度来说，运营商往往希望能够在为用户提供优质服务的同时，尽可能地节省资源的消耗。合适的缓存策略可以有效地减少内容传输过程中的资源消耗，从而满足运营商的需求。理想的缓存策略能够用本地缓存满足用户所有的请求，然而，由于在基站侧所提供的内容缓存空间有限，用户的访问行为中所请求的内容未知，我们只能根据用户的历史访问记录来对用户可能的请求内容进行估计，从而将用户的访问特征作为先验知识来决定基站侧的内容缓存策略。在解决这一问题的研究中，大部分的工作只单独针对用户访问内容的分布或位置的分布进行缓存策略的制定。而对于基站来说，不同的基站服务的用户不同，如果对全部用户的访问行为进行整体考虑则会忽略用户之间的差异，从而导致基站侧缓存针对性下降；如果对每一个用户分别考虑，则由于用户间访问行为差异大，将会导致用户访问行为描述难度增大，基站侧的缓存策略制定复杂度增加。现有的工作大部分采用的是“同质性缓存策略”，即不同的基站上缓存相同的内容或以相同的概率分布决定缓存的策略4-9。但是，由于不同基站上的访问内容呈现出多样性，故不同基站上，不同内容的访问频率和次数是不同的10。在实际的移动网络访问过程中，由于用户间存在地理位置上的邻近关系和内容偏好上的部分相似关系，对于任意一个基站而言，其稳定服务对象（也就是访问该基站的次数或频率较为稳定持久而非临时访问的用户）有限。种种迹象表明在移动网络访问过程中，用户将形成不同的用户群体，这种用户群体在访问位置或访问内容上存在一定的相似性，为用户的访问行为描述和基站侧的缓存策略制定带来了方便。同时，网络架构正随着时代的步伐不断演进，基站间的合作为提升服务质量提供了一种新的可能。许多研究工作者开始采用基站合作的策略来提升基站侧缓存的效率。文献51112中，作者尝试使用基站的位置来决定基站间的合作关系，文献1314中，作者让缓存有相同内容的基站之间进行合作式的内容传输以提高用户的内容获取效率。然而，上述工作多强调的是以基站为单位的用户访问行为的统计特性，忽略了以用户为主体的访问行为本身所具有的一些独特特性，例如，当用户在办公地点附近时，他们最长访问的多是与工作相关的内容，而当他们在居住地附近时则会更多地访问娱乐休闲性质的内容。如图 11所示，如果以全体基站为对象考虑用户访问行为分布的统计特性，那么我们只能获得所有基站用户访问的总体分布情况，如图 11(a)所示，每个基站会获得统一的平均化的用户兴趣，这种方式导致所有基站上的缓存呈现出同质化，故用户兴趣差异性的部分将会被忽略。如果以单个基站为对象考虑用户访问行为分布的统计特性，则只能获取单一基站上的用户访问行为分布，如图 11(b)所示，每个基站对本基站上的用户访问分布进行统计，则每个基站只能满足极少数用户的需求，忽略其他用户的兴趣。如前所述，在用户访问内容呈现出一定规律的区域内（工作区域或居住地区域），往往涵盖了多个基站的用户访问行为分布，当我们以用户群体为主体考虑访问行为在基站上的分布时，可以得到基站间的“相关”程度，也就是不同基站服务同一群用户的概率,而这一特性可以帮助我们构建基站间的合作关系，如图 11(c)所示，合适的合作关系可以让基站上的缓存满足更多用户的需求。（a） 全局统计特性（b） 单一用户统计特性（c） 群体用户统计特性图 11不同方法获得的用户访问特性在基站侧的映射合作式的基站侧缓存能够有效地提升基站侧缓存的效率，针对如何设计基站间的合作关系的问题，有许多研究工作者提出了自己的设计方案。“共享经济”是目前炙手可热的一个概念，它的核心思想是通过对一些热点资源以各种方式进行重复利用实现用户体验的提升15。“共享经济”是基于用户之间行为的相似性来实现的，例如，如果大家都喜欢骑车，那么我们就可以提出“共享单车”的概念，将车放在用户常去的位置，用户可以在需要的时候取用。这种思想与缓存的目的十分相似，基站侧缓存也是将用户希望访问的内容存放在基站上，用户可以在需要的时候取用。唯一不同之处在于，“共享单车”中的单车种类单一，但是在基站侧缓存内容时，内容的种类却是多种多样的。我们可以将“共享”的概念引入到用户访问行为的分析和基站侧缓存策略的制定中，考虑群体用户而不是个体用户，利用群体用户的行为相似性来决定基站侧的内容缓存策略。例如，一群经常在某些基站上访问某些内容的用户就可以被看作是一个用户群体，依据相应的用户群体的访问行为，我们就可以决定这些基站上的内容缓存策略。群体用户的行为不是由单一特征描述的，而是由多种特征（访问位置、访问内容等）描述，故在群体用户行为描述的过程中，如何将这些特征融合在一起对行为进行完整全面的描述，也成为了一个重要的问题。本文针对现有的基站侧缓存策略针对性不足的问题，首先分析了记录用户移动网络访问行为的UDR数据，重点描述和分析了用户的内容和位置信息，发现了用户访问行为中存在的异质性和可预测性，以及用户在移动网络访问过程中存在明显的群体聚集现象。并且，相较于个体用户，群体用户的可预测性表现得更为稳定。同时，用户的不同特征之间也存在一定的关联性和互补性，对不同特征的综合使用能够在一定程度上提升用户行为的可预测性。基于这些分析结果，本文提出了一种基于群体用户行为的移动网络合作缓存方法。其中，提出了WSNF算法对用户的内容相似网络和位置相似网络进行融合，从而挖掘出用户的群体行为；然后将用户群体用于基站间合作关系的确定，最终基于基站间的合作关系确定基站侧的内容缓存策略。针对实际应用中存在的基站侧缓存更新问题进行了研究，提出了合作关系驱动的缓存更新方法。其中，提出了基于用户访问行为分布差异的关键点发现方法，通过跟踪网络中的关键点，实现对网络中用户访问行为分布变化的监控，并据此决定基站缓存的更新时间。1.2 国内外研究现状1.2.1 用户群体行为研究现状用户行为存在一定的群体性16-18，这种群体性受生活环境的影响，有相似生活环境的人容易表现出相似的行为。目前用户群体行为研究主要集中在群体行为应用、群体行为挖掘方法以及用户潜在需求预测等三个方面。1. 群体行为应用目前用户行为的群体性已经被应用于多个领域，例如商业规划、城市资源规划和移动通信网络优化。a) 商业规划应用中，主要利用群体的移动行为和访问行为进行商业推广策略的优化。例如，文献19中，作者对用户在地理空间上的移动轨迹进行了相关性分析，并依据结果对商铺的选址过程进行了优化。文献20通过在移动设备上运行的实时分布式算法，利用蓝牙数据对用户之间的聚集关系进行识别，从而获得对特定商品有购买意向的人群。b) 城市资源规划应用中，群体行为特征能为城市功能区域划分等工作提供依据。例如，文献21中，作者计算了日本地理空间相关的Jaccard系数，分析了人群在灾后的应急行为轨迹等，为自然灾害等应急管理提供了依据。文献22对城市人群出行的起止点（Original Destination，OD）进行了语义挖掘，并依据挖掘出的群体行为语义信息指导城市资源的部署等。文献23中，作者根据旅行者群体的移动进行路线分类，将火车线路和用户的基站切换模式相匹配，用于测量城市中特定路线上的人流量。c) 移动通信网络优化应用中，将群体行为特征中所体现出的资源占用情况用于对通信资源进行调度和配置。例如，文献24提出移动预测即服务的模型，基于用户的行为模式构建马尔可夫预测器，该方法可以预测用户接下来将要访问的基站等，运营商可以根据预测结果对资源进行统筹和调度。文献25根据群体用户行为构建流量模型动态地分配基站带宽资源。综上，目前群体行为发现的主要应用场景是各类资源的优化，包括道路资源、通信资源和商业资源等。其中，利用群体的移动网络访问行为，可以得到移动网络资源使用的整体分布情况，能够根据分析结果对移动网络资源进行高效的配置和调度。2. 群体行为挖掘方法目前大部分群体行为挖掘主要采用聚类、网络分割等方法。近年还出现了大量针对特定场景的改进型方法，包括基于局部行为特征的群体行为挖掘方法，基于累积行为数据的群体行为挖掘方法和基于随机块模型的群体行为发现方法。a) 基于局部行为特征的群体行为挖掘方法利用社会局部聚集的特征，即在局部形成同质性群体社区，同一社区内的人有相似行为模式，而不同社区内的人则在行为模式上表现出较大的差异。例如，文献26中，作者结合层次聚类算法，提出一种将局部相似性度量用于社区发现的方法，解决了部分相似性在计算过程中被忽略的问题。文献27中，作者对近线性聚类算法进行了优化和改进，利用局部特征，将节点的独立特征之间的关系用于整体的合作从而实现聚类。b) 基于累积行为数据的群体行为挖掘方法主要解决的是实际应用中数据不断累积的问题，在数据增长的过程中就需要对增量数据进行有针对性的聚类。例如，文献28中，作者对SNN算法进行了改进，在原始数据中计算与新增数据的距离，据此可得到原始数据中改变的部分，然后只需对改变的数据进行重新聚类计算，极大地降低了计算量。文献29中，作者提出一种针对增量数据的改进型K-means的聚类算法，对已有的累积数据进行聚类后的均值计算，对新到来的数据计算与现有的均值之间的距离，借用KNN的思想，为新增数据进行归类。c) 随机块模型的特点在于以生成式的方法对网络的结构进行捕捉，通过该模型可以得到网络结构特点，进而得到网络中的社区结构。相对于其他社区发现方法，随机块模型对于无先验信息的网络结构有更为出色的效果。文献3031中，作者以较大的网络中节点连边概率进行随机块模型的生成，最终实现重叠社区的识别。文献32中，作者针对现有方法时间复杂度较高的问题，在更细粒度的层面构建随机块模型，并利用快速学习算法实现了在保持学习精度的同时降低时间复杂度的目标。随机块模型需要进行随机抽样和假设检验的计算，因此该类方法复杂度比较高。3. 基于群体行为的用户潜在需求研究基于群体行为可以获取用户潜在需求，例如用户访问内容偏好、常访问的位置等。例如，文献33利用潜在语义空间提出了一种基于图论的打分模型，根据用户群体的相似性对用户潜在的兴趣进行排序，预测用户访问内容。文献34中，作者依据混合高斯分布提出了一种新的用户行为时间框架，基于用户活动中体现出的模式，对用户访问过程中出现的周期性进行了描述。文献23中，作者为用户访问行为构建了一种新的模型，同时考虑多个维度的信息，基于非参数贝叶斯方法对用户潜在需求进行预测。群体行为发现有利于发现用户需求和兴趣特征，有利于降低计算复杂度（例如，使用群体行为代替个体行为缩小了分析过程的状态空间），同时群体行为发现有助于合作共享的实现，由于行为的相似性，分析得到的群体内部可以存在一定程度的合作（例如有相同兴趣内容的人群，在向基站发起请求时可以将共同的兴趣内容缓存，在之后的请求中，该内容可以服务于其他请求相同内容的成员）。在对用户行为进行描述时，可用的特征非常丰富，包括时间、空间和行为内容等。多种维度的特征在量纲、衡量方法、数据来源和应用价值上都存在着差异，例如时间维度的特征以秒等单位计量，可用于分析群体行为时间序列上的变化，而空间维度的特征则以经纬度或坐标等标识，可用于分析群体行为空间上的分布。多特征融合方法将不同维度的特征融合在一起，能更准确全面地刻画用户行为，故将多特征融合的方法应用到群体行为发现过程中，能够提升群体行为发现的准确性。现有的数据融合方法根据数据融合过程中所强调的数据源的特征不同可以分为三类，分别是分步累加型数据融合、特征提取型数据融合和关系型数据融合。a) 分步累加型数据融合分步累加型数据融合强调的是不同数据之间在描述相同对象时的异质性，即不同的数据从完全独立的角度对相同的对象或事件进行描述，其数据融合方法则主要是将对象或事件的分析过程分成不同的阶段，在不同的阶段中加入不同的数据描述，逐步构建完整的描述结果。文献35中，作者将城市中的区域及道路数据和车辆的移动轨迹数据相融合。具体的，作者首先根据城市的区域和道路数据对城市的道路进行划分，然后将车辆的GPS数据投影到划分的结果上，即可得到车辆的移动轨迹分布，此方法所得到的数据融合结果可以帮助对城市的道路交通规划进行指导和改进。文献3637中，作者利用用户的移动轨迹和用户访问节点之间的关系进行数据融合，用于描述用户之间的潜在亲密关系。具体的，作者首先从用户的移动轨迹中提取出所需的访问节点，然后通过节点之间的关系构建用户访问行为的层次图，层次图中的相似度描述了用户之间的亲密关系程度，此方法所得到的数据融合结果可以帮助为用户提供内容推荐和好友推荐的服务。显然，由于分步累加型数据融合过程中将不同的数据放在了不同的融合阶段独立使用，故在数据源的表现形式上没有严格的一致性要求，即允许不同形式和格式的独立数据源参与到数据融合的过程当中来。然而，在实际的应用场景中，描述相同的对象或事件的数据源可能在一定程度上存在关联性，分步累加型数据融合方法则会忽略这种数据源之间的关联性。b) 特征提取型数据融合在许多应用场景中，直接获取的数据往往不能满足我们实际的数据分析或应用需求，此时，就需要对原始的数据进行特征提取，根据应用需求将所需的特征生成新的数据，然后进行融合。特征提取型数据融合强调的是数据的独立性，即从不同的数据中提取出的特征之间几乎没有冗余，而经过数据融合之后能够对对象或事件进行完整的描述。文献3839就是从不同的数据源中提取出所需的特征进行融合，最后根据融合得到的特征进行聚类得到最终所需的结果。文献40中，作者为了预测房地产的投资价值，分析了与房地产价值相关的四个数据源：社交数据、交通数据、车辆移动数据和导航数据。作者首先从四个数据源中提取出所需的特征，并综合利用这些特征进行学习和训练，得到最终的预测模型。事实上，在机器学习被广泛应用的今天，大量的工作中开始利用深度学习等框架进行数据源的特征学习和提取，然后进行融合得到特征数据41-44。c) 关系型数据融合与分步累加型数据融合方法相反，关系型数据融合方法强调的是不同数据源之间的关联性。具体的，对于不同的数据源，经过一些数据处理方法可以得到相同的数据特征表示方法，例如，对于各种类型的数据，都可以将其表示成为相似网络的形式。文献45中，作者为了判断城市中的噪音污染状况，选用了包括城市地理空间、用户的社交信息和位置信息等数据源，并通过构建张量的方式从这些数据源提取出统一的数据特征描述形式，从而对噪音污染分布情况进行了模拟和分析。文献46则融合了道路信息和用户移动过程中的访问热点信息，对城市的功能区进行划分。显然，关系型数据融合对数据之间的关系进行了较为完整的保留，所得到的数据特征在融合过程中可以相互加强和弥补，便于生成完整的特征描述。现有的数据融合方法中，对于不同数据源在融合过程中的重要性差异没有考虑。例如，在内容推荐场景中，相关的数据源可能包括用户的访问轨迹、访问兴趣、亲密关系等，但显然用户的访问兴趣在该场景中占有最重要的位置。为了解决这一问题，我们需要找到一种能够区别不同数据源在数据融合过程中的重要程度的方法，同时又能够对数据源的关联性进行保留，从而对对象进行较为完整和全面的描述。1.2.2 移动网络缓存研究现状边缘缓存是移动网络中一种重要的提升服务效率和性能的技术，在5G架构的关键技术MEC中，边缘缓存被用于移动网络计算数据源的缓存，缓存的主要架构为边缘节点可以缓存应用服务及其相关数据，即服务缓存（或服务放置）和内容缓存，并处理来自多个用户的卸载计算。其中，服务缓存包括空间流行驱动的服务缓存，指的是根据服务器的具体位置和周边用户的共同兴趣在不同的MEC服务器上缓存不同的服务组合和数量。内容缓存则主要针对数据密集型的计算进行，只保留经常使用的数据。面向服务的内容缓存与面向计算的内容缓存的共同点在于其目标都是为了提升用户的体验同时缓解网络的传输负载，其关键问题都在于如何在海量的数据和有限的存储空间之间找到平衡：每个边缘节点都希望能够腾出更多的存储空间来缓存其单元中最流行的内容，并且还需要利用部分存储来容纳不太流行的内容。一种实现方式就是通过多个边缘节点之间的协作缓存以提升内容缓存的覆盖，并可以通过将附近的用户作为群体以提升大规模缓存网络的性能3。不同的是面向服务的内容缓存相对于面向计算的内容缓存而言更强调用户的访问行为描述。在面向服务的内容缓存中，主要的服务对象是访问移动网络的用户，而服务的提供方则是基站。现有的基站侧缓存方法主要分为两种，一种是合作式缓存，另一种是非合作式缓存。在非合作式缓存方法中，每个基站有一定大小的缓存空间，独立为用户提供完整或部分服务，即在响应用户请求的过程中，基站只以本地的缓存为服务依据，尽量满足用户请求，而不考虑任何其他基站上的缓存或传输状况。在合作式缓存方法中，每个基站虽然有独立的缓存空间，但是基站之间可以合作，即用户所发起的请求在被响应时，与被请求基站有合作关系的基站可以以信息共享的形式决定最终的请求响应方式，只有当这些基站都无法响应该请求的时候，才会由核心网响应。典型的非合作式缓存包括CMP（Cache Most Popular），CD（Cache Distinct）等。CMP主要依赖于内容的受欢迎程度，而受欢迎程度一般由用户对内容的访问次数来衡量，最受欢迎的若干个内容将会被缓存到所有基站上。CD则与CMP相反，完全没有考虑内容的受欢迎程度，而是以提升缓存内容的多样性为目的，让每个基站随机缓存一定数量的内容。典型的非合作式缓存方法由于策略简单，被广泛地应用于许多现有的工作中，例如在文献5-9中作者都用到了CMP，在文献1147-51中作者也都用到了多种不同的非合作式缓存方法。在此基础上，还有许多人针对通用的文件存储方式提出了新的缓存算法，其中一类针对文件的存储单元进行改进，例如文献52中作者将文件编码后进行分块存储，文献535455的基本思路都是将文件分成多个子文件存储在多个不同的缓存中，但是对文件的切割方式和分配方式会略有不同。文献13中作者将文件以符号的形式分块并存在不同的缓存中，文献4中，作者也是对分割后的文件片进行缓存。另一类主流的缓存方式则是根据不同的需求提出优化目标，将缓存矩阵作为变量进行求解。如文献56中以缓存和传输能量最小为目标，文献57中以尽可能满足所有请求为目标，文献145859中以最小化延迟函数为目标，文献60中以最小化回程链路的传输率为目标，文献12以最小化负载为目标，文献10则是将最大化整个系统的收益（与系统的命中率等有关）和最小化代价为目标。另外文献461中均涉及了一种分层的网络架构下的缓存策略，即将整个网络中的节点分成若干层，每一层根据需求存储不同的内容。值得一提的是，文献62中作者提出了一种最优概率模型，以一定的概率将内容缓存在不同的基站上以增加内容在基站上分布的多样性，同时又考虑了用户对内容的偏好。在合作式的缓存中，基站以一定的策略缓存一定大小的内容后，将以合作的形式服务用户，即用户所请求的内容可能依据当前的共享信息被具有合作关系的基站中的任何一个或多个基站响应。目前的合作式缓存方式主要可以分为两种，一种方式主要基于用户访问过程中的位置特征，另一种方式主要基于用户访问过程中所反映出的内容特征。基于位置特征的合作的基本原则是用户的请求可能被一个邻域内的基站响应。文献4中介绍了一种六边形网格合作方式，在距离近的基站间建立合作关系。这种合作关系只考虑了基站本身的位置特征，却没有考虑基站的服务特性，合作关系不够紧密。另一种是将基站和用户之间的距离作为用户请求响应基站的选择标准。例如，文献51112中都将距离作为选择基站标准，其中文献5用Voronoi分布让用户连接到距离自己最近的基站，然后再根据请求的内容等其他因素确定最终的响应基站。基于内容特征的合作基本的原则是用户的请求可以被存有该内容的一个或多个基站响应。例如，文献1314将内容作为选择基站的标准，其中文献13根据分块存储的顺序依次获取内容分片直至获取到完整的内容，文献14将信道状况作为标准，从存有自己所需内容的所有基站中选择出最终建立连接的一个。另外文献8中，用户所发出的请求最终将会由有最大接收信号能量的节点响应，文献59中用户在发起请求的时候可以连接到多个“helper”，每个“helper”的传输时延不同，缓存的内容也不同，用户最终会选择存有所请求内容且传输延时最小的“helper”进行响应。基于内容特征的合作方式需要在用户发起请求的时候获取大量的网络信息并进行计算，代价较大。文献1063则使用全局合作方式，这种合作方式在所有的基站间建立合作关系，显然在实际操作中会带来很大的控制和调度开销。上述的基站侧缓存相关工作中，大都只考虑了全体用户访问行为的统计信息，而忽略了用户之间的群体性，即用户群体内存在较强的访问行为相似性，而不同用户群体间存在访问行为的差异性。基于全局统计信息的方法通常只能对头部内容进行缓存。图 12内容访问分布如图 12所示，用户对内容的访问分布呈现出长尾特性。对全体用户进行访问行为描述，最终会保留下用户整体访问兴趣头部的内容，也就是图中左侧绿色条状部分，这部分内容会被基站缓存以满足用户的请求。然而，在实际的访问过程中，用户的差异性体现在如图 12中所示的右侧红色条状部分，我们称之为“次头部内容”，这部分内容多为受到部分用户的喜爱而非全体用户的喜爱的内容，其访问次数也较大。显然，如果能够将这部分内容的偏好体现在基站侧缓存中，则可以有效地提升基站的缓存效率和用户的体验。但是，仅在对全体用户访问兴趣进行描述时加上全部的“次头部”内容，显然会大大地增加基站的缓存开销。如果在进行用户访问行为描述时，不是对全体而是对行为相似的用户群体进行描述，则可以找到每个“次头部”内容所对应的用户群体，并依据用户群体的访问行为差异进行有针对性的内容缓存。故基站所需增加的缓存代价就能有效地降低，对用户内容需求的响应率却能够有效提升。缓存更新在基站内容缓存的实际应用中，是不可或缺的一部分工作，在时间维度上，基站侧缓存策略应该根据用户访问行为的变化进行相应的调整。现有的基站侧缓存更新方法主要有三种，即基于内容权重的更新策略、基于在线学习的更新策略和基于Markov过程的更新策略。基于内容权重的更新策略主要思想是根据系统的需求为内容设计评分规则，然后根据这一评分规则给所有被请求过的内容打分，当基站缓存空间不足时，将会根据该基站上被请求过的内容的评分判断此时的更新策略。目前主要的评分指标包括最近访问（Recency）、访问频率（Frequency）、获取时延（Obtain Delay）和内容大小（Size）。在文献64中，作者将未缓存内容的请求等待时间、内容的受欢迎程度和内容的寿命作为评分指标；在文献65中，作者认为内容的评分和内容权重、请求频率、内容大小、获取时长有关；在文献66中，作者以内容被访问的次数和最近被访问的两次之间的时间间隔作为该内容在系统中的重要程度指标；在文献67中，作者以内容在当前节点的受欢迎程度和获取该内容所需的网络跳数除以当前节点空间大小为指标；在文献68中，作者以最近请求频率和该内容对解码的贡献为指标；在文献69中，作者以访问者和内容发布者之间的关系强弱和内容的LRU（Least Recently Used）值作为指标。基于在线学习的更新策略则主要是利用在线学习的策略进行缓存内容的更新和调整，其依据是以某个指标达到最优为目标，主要分成两种方式，一种是如文献70中，作者基于Q-learning计算命中率提升，即每次迭代时计算更新后回报值最大的策略，回报值是命中率的提升；另一种是对整个移动网络中的节点构建模型，然后通过对节点间的参数进行调整实现最终的更新策略制定，如文献71中，作者基于用户的访问行为构建回归模型，将模型的相关因子定为内容的观看时长和分享次数，在文献72中，作者为整个系统构建神经网络，网络的输入是内容访问频率，最近访问间隔和内容大小。基于Markov过程的更新策略则是将缓存更新描述成一个Markov过程，如文献73中作者就是将基站侧的缓存内容更新描述成一个Markov决策过程（Markov Decision Process，MDP），在文献74中，作者则提出了一种基于Markov图的缓存更新策略（Markov Graph Cache Replacement Policy，MGCRP），通过Markov模型预测客户端的下一个位置进行缓存更新；在文献75中，作者将Markov模型应用到分布式缓存更新策略中，在缓存更新过程中不需要在基站间传输多余的数据即可完成更新。现有的工作已经对基站上的内容更新方法和评价指标进行了较为完整和全面的研究，对于合作关系驱动的缓存更新却尚未见到有针对性的研究工作。而在本文的应用场景中，由于基站间的合作关系由用户的访问行为决定，随着用户访问行为发生变化，基站间的合作关系也需要进行相应的更新。由于基站间合作关系的更新势必带来全局缓存内容的更新，故我们需要做的就是找到一种方法发现更新的时间点（用户访问行为发生变化的时间点），从而在网络中的合作关系和缓存内容不能匹配用户的访问行为分布时通过更新实现用户访问体验的提升。1.3 本文的主要内容及结构安排本文基于用户移动网络访问数据，针对现有的移动网络中的基站侧缓存方法存在的问题进行了分析和改进。主要内容包括：首先对用户行为的异质性、可预测性和群体性进行分析，说明了群体用户相较于个体用户有更强的可预测性。同时说明用户访问行为的不同特征之间可以互相消除不确定性，综合使用用户的不同维度的特征可以有效地提升用户访问行为的可预测性。基于分析结果，本文提出了一种加权相似网络融合算法WSNF，以融合后的相似网络与原始相似网络的距离之和最小为优化目标求解相似网络融合结果，并依据得到的融合后相似网络对用户进行群体发现。然后，将得到的用户群体映射到基站侧以获得网络中的基站合作模型。接着，基于基站合作模型，以最大化用户请求在基站侧的命中率和最小化基站间内容传输的代价为优化目标，求解最终的缓存策略，并从命中率和传输代价的角度对所得到的基站侧缓存策略进行分析并与现有的算法对比。最后，针对实际应用过程中存在的缓存更新问题进行了分析，提出了合作关系驱动的缓存更新方法。其中，提出了一种基于用户访问行为分布差异的关键点发现方法，并通过跟踪网络中的关键点，发现用户访问行为发生变化的时间，从而进行基站缓存的更新。本文的组织结构和主要内容安排如下：第一章对基站侧缓存相关的背景进行了阐述，并介绍了用户群体行为和移动网络缓存的研究现状。第二章对移动网络中用户行为异质性、可预测性和群体性进行分析。首先对异质性和可预测性进行了分析，包括内容维度和位置维度的特征。接着对用户访问过程中的群体行为进行了分析，包括群体用户在内容维度和位置维度的可预测性和不同维度特征相结合后的可预测性。第三章提出一种基于群体用户行为的基站合作模型。首先提出WSNF算法将用户间不同维度的相似网络进行融合，并基于融合后的相似网络对用户进行社区划分，划分后的用户群体将用于基站间合作关系的映射。第四章提出了一种基于群体用户行为的移动网络合作缓存策略GUCC，根据基站间的合作关系，以系统的命中率和传输代价为优化目标，求解得到基站侧的缓存策略。用真实的用户移动网络访问数据进行缓存效果的验证，并对比现有的多种缓存策略进行分析。第五章结合实际应用需求，对缓存更新问题进行了分析并提出了合作关系驱动的缓存更新方法。具体提出了基于移动网络用户访问行为分布差异的关键点发现方法，通过对网络中的关键点进行监控，依据关键点上用户访问行为的变化决定缓存更新的时间。第六章对本文的主要工作进行了总结，对基于群体用户行为的基站合作缓存方法中存在的不足进行了探讨和分析，也对移动网络用户行为分析与应用方面未来的研究工作进行了展望。2 移动互联网用户行为特征分析2.1 数据集介绍本文以浙江省金华市的运营商数据作为分析和实验的数据源，包括金华市23天的用户移动网络访问记录。主要信息如表 21所示。表 21数据表格式用户ID开始时间结束时间基站URL689608140312014-11-21 12:02:192014-11-21 12:02:26689B_83A1690614523392014-11-21 06:23:032014-11-21 06:23:2067BD_3345689608140312014-11-21 13:40:522014-11-21 13:41:0967BD_5BB92.2 用户多样性和可预测性特征分析用户的个体特征包括用户访问特征的多样性和可预测性，用户访问内容或位置的多样性是由用户访问的内容或位置的种类数度量，而可预测性则是由用户访问的内容或位置的概率分布的信息熵来衡量。本文首先对用户访问行为的内容和位置的多样性进行统计，统计结果的累积分布函数（Cumulative Distribution Function，CDF）如图 21所示。从图中可以看出，用户访问的位置数和内容数呈现出一种长尾特性，这种特性在之前的许多工作中都有分析和说明76-80。用户访问的位置数和内容数有限，大多集中在5个左右，绝大部分用户访问的位置和内容数都少于10个。从图中我们还可以看出，访问位置数少于5个的用户比访问内容数少于5个的用户要多，显然，用户在访问位置上表现出比访问内容更强的局限性。一种解释是，位置的切换涉及到用户本身的位置移动，也就是用户需要从一个位置移动到另一个位置（并且是相隔较远的位置），而内容的切换只需要用户在访问的页面上进行选择即可，内容的切换相较于位置的切换要容易的多，故内容的多样性相较于位置的多样性要更丰富一些。图 21用户访问行为中内容和位置多样性接着，为了刻画用户在空间上的移动特性，本文计算用户在移动网络访问过程中的回转半径81，回转半径在本文中是用户移动网络访问过程中其轨迹所覆盖的范围大小，用户u的回转半径定义如公式（21）所示。 （21）其中，表示用户u移动网络访问范围的质心，为用户访问行为轨迹中第i个轨迹点，为用户轨迹点的个数，本文将的CDF曲线绘制如图 22所示。可以发现，移动网络用户在对基站的访问行为中活动的范围十分有限。特别的，有70%左右的用户其回转半径小于5km；回转半径小于10km 的用户更是占比85%。图 22用户回转半径的累积分布函数最后我们将研究用户访问行为中不同特征的可预测性，我们用香农熵和条件熵分别衡量单个特征的可预测性和不同特征之间的相关性。香农熵和条件熵的定义分别如式（22）和式（23）所示,