基于机会连接的移动数据流量卸载策略研究.doc

硕 士 学 位 论 文 基于机会连接的移动数据流量卸载 策略研究 专业名称 ： 信息与通信工程 基于机会连接的移动数据流量卸载策略研究 摘要 随着移动互联网的快速发展和智能手机、平板电脑、个人电脑等移动终端设备的普及，移动数据流量急剧增长，从而给蜂窝网络带来了巨大的流量压力。建设更多基站或者升级蜂窝网络配置等传统的解决途径，难以有效应对数据流量的急剧增长。当前研究热点表明，移动数据流量卸载是解决蜂窝网络负载压力的有效措施之一。基于机会连接的流量卸载利用用户之间建立机会连接，是一种高效灵活的应对流量激增的解决方案。本文基于真实的中国移动用户上网记录数据，研究了基于机会连接的移动数据流量卸载策略，针对完全信息和不完全信息两种应用场景分别设计了流量卸载算法，主要研究内容如下： 1. 根据用户相遇关系进行网络建模，分析了网络拓扑结构、用户移动性和用户上网行为特征，然后采用随机森林算法对用户相遇的机会连接进行预测，并将该算法应用在真实数据集上，取得了较好的预测效果。 2. 提出了一种在完全信息应用场景中基于Stackelberg博弈的流量卸载算法，在机会连接预测的基础上，将运营商、内容提供用户和内容需求用户三方之间的交互行为建模为Stackelberg博弈过程，分析了构建的博弈模型中Nash均衡的存在性，然后利用迭代算法设计流量卸载策略，实验结果表明该算法可以有效减轻运营商的流量负载。 3. 提出了一种在不完全信息应用场景中基于强化学习的流量卸载算法，在分析用户流量需求的基础上，设计了系统效用函数，然后利用强化学习Gradient Bandit算法设计使总效用最大化的流量卸载策略，并通过实验验证了该算法的有效性。 本文利用用户之间建立机会连接，针对完全信息和不完全信息两种应用场景提出的流量卸载算法可以有效减轻蜂窝网络的流量负载压力，能够为两种应用场景中的流量卸载决策提供指导，高效应对数据流量的持续增长。本文的研究工作不仅具有应用价值，也为基于机会连接的移动数据流量卸载策略研究提供了一种新思路。 [关键词]：流量卸载，机会连接，博弈论，强化学习 Abstract With the rapid development of mobile Internet and the popularity of mobile terminal devices such as smart phones, tablet computers, personal computers and so on, the rapid growth of mobile data traffic has brought tremendous traffic pressure to cellular networks. Traditional solutions such as building more base stations or upgrading cellular network configurations have been unable to cope with the continuous growth of data traffic. The current research hotspot shows that mobile data offloading is one of the effective measures to solve the load pressure of cellular networks. Mobile data offloading based on opportunistic connection is an effective solution to cope with the surge of mobile data, taking advantage of opportunistic connection between users. Based on the real data provided by the mobile communication operator, this paper study the strategy of mobile data offloading based on opportunistic connection. We design the mobile data offloading algorithms respectively for two application scenarios of complete information and incomplete information. The main achievements are listed as follows: 1. We construct the network based on the encounter relations between users. The network topology features, user mobility characteristics and user internet behavior characteristics are analyzed. We exploit random forest algorithm to predict the opportunistic connection between users. The prediction model based on random forest is applied to the real data and has achieved great performances. 2. We propose a mobile data offloading algorithm based on Stackelberg game in a complete information scenario. Based on the results of the opportunistic connection prediction, we model the interaction characteristics among the operator, the content provider and demander as a Stackelberg game. We analyze the existence of Nash equilibrium in the Stackelberg game model constructed in this paper. An iterative algorithm is exploited to design mobile data offloading strategies. Experiment results show that the algorithm proposed in our paper can effectively reduce the traffic load in the cellular network. 3. We propose a mobile data offloading algorithm based on the reinforcement learning in an incomplete information scenario. Based on the analysis of users’ mobile data traffic demand, we design the system utility function. The Gradient Bandit algorithm in reinforcement learning is exploited to solve the optimal mobile data offloading strategies which maximize the system utility function. The experiments verified the effectiveness of the algorithm proposed in our paper. Taking advantage of the opportunistic connection between users, this paper propose mobile data offloading algorithms in the complete and incomplete scenarios respectively. The algorithms can effectively relieve the traffic load pressure of the operator, provide guidance for mobile data offloading decisions in two application scenarios, and well handle the continuous growth of data traffic. The research in this paper not only has practical significance, but also provides a new insight of mobile data offloading based on opportunistic connection. [Keywords]：Mobile Data Offloading, Opportunistic Connection, Game Theory, Reinforcement Learning I 目录 摘要I AbstractII 1绪论1 1.1研究背景及意义1 1.2国内外研究现状2 1.2.1基于互补网络的流量卸载研究现状2 1.2.2基于机会连接的流量卸载研究现状3 1.3本文的主要内容及结构安排4 2用户行为统计分析6 2.1数据集信息6 2.2用户移动行为统计分析8 2.3用户上网行为统计分析11 2.4本章小结12 3基于用户行为分析的机会连接预测模型14 3.1网络模型14 3.2网络结构和用户行为特征提取17 3.3机会连接预测模型25 3.3.1随机森林算法25 3.3.2仿真实验与分析26 3.4本章小结30 4完全信息场景中的流量卸载策略31 4.1流量卸载模型与算法31 4.1.1Stackelberg博弈模型32 4.1.2算法设计与实现35 4.2仿真实验与分析39 4.3本章小结43 5不完全信息场景中的流量卸载策略44 5.1流量卸载模型与算法44 5.1.1用户流量需求分析45 5.1.2基于强化学习的流量卸载算法46 5.2仿真实验与分析52 5.3本章小结55 6总结与展望56 6.1全文总结56 6.2研究展望57 参考文献58 附录A 攻读硕士学位期间发表的学术论文63 附录B 攻读硕士学位期间申请的发明专利64 致谢65 1 绪论 1.1 研究背景及意义 近年来，随着智能手机、平板电脑、笔记本电脑等移动智能设备的普及，移动业务流量呈现指数型增长。移动互联网的快速发展和移动智能设备的普及导致移动数据流量将在2020年激增8倍，并且诸如视频等对带宽敏感的应用将会占到全部数据请求的70%以上[1]。根据Cisco的移动网络前景报告[2]显示，全球移动数据流量将在2019年增长到292EB，并且智能流量占比高达97%。移动数据流量的急剧增长给蜂窝网络带来了十分巨大的压力来解决数据过载问题。为了应对持续增长的移动数据流量，减轻宏基站的流量负载，覆盖范围较小的小型基站被部署在更加靠近终端用户的地方，但是基站通过有限容量的回程链路连接到核心网，在流量高峰期时很难达到较好的用户服务质量。传统的解决途径是建设更多的基站或者升级蜂窝网络配置来缓解巨大的流量压力，然而这种方案需要投入高额的成本和较长的建设周期，在较短的时间内无法有效解决流量过载问题。在这样的背景下，移动数据流量卸载作为一种解决数据过载问题的有效方法，逐渐成为了业界学者的研究热点。 移动数据流量卸载通过互补网络来减轻流量负载，它的目标是在保障用户服务质量QoS的前提下，降低移动网络上对带宽需求较大的服务的成本，减小其对网络负载的影响。该技术可以有效解决移动数据量的激增所造成的资源竞争和用户体验指数下降的问题。当前的流量卸载技术主要有基于WiFi网络、微蜂窝和基于终端机会连接等方式，由于WiFi网络覆盖范围较小，卸载的流量有限[3]，而基于机会连接的流量卸载利用了用户的移动性，这种方式更加灵活，成本较低。由于存储内容数据的代价较小[4]，用户可以将自己下载过的内容存储在终端设备上，在流量高峰期时，当在邻近范围内的其他用户请求这些内容时，可以利用机会连接的方式，将内容数据直接发送给其他用户。用户机会连接是基于D2D的，机会连接是指利用用户之间相遇的接触机会，通过蓝牙等近距离通信方式进行数据传输。这种方式不需要经过回程链路，使在邻近范围内的邻居用户可以直接进行通信，共享已经下载过的内容，不需要从网络中再次下载这些内容，从而既可以提升用户体验，又能够减轻蜂窝网络的流量负载[5]。基于机会连接的移动数据流量卸载，利用用户之间的机会连接，进行流量卸载，可以减小回程链路的负载和传输代价，因此本文针对基于机会连接的流量卸载策略进行研究。 本文主要针对处于网络边缘侧的终端设备之间通过机会连接进行流量卸载展开研究。由于诸如多媒体视频、歌曲、新闻、游戏等内容可以容忍延迟，不需要即刻进行传输。用户先从内容服务提供商获取内容数据，并将其在手机中进行存储，当其他内容需求用户和这个用户相遇，处于能够互相通信的邻近范围内时，并且也请求这些内容时，该用户再通过蓝牙等近距离通信方式，将这部分内容数据分发给邻居范围内的其他用户。一方面，终端用户参与移动数据流量卸载可以减小数据服务的成本，同时获得更多的内容数据；另一方面，运营商也能够降低蜂窝网络的资源竞争和流量负载压力。因此，研究基于机会连接的移动数据流量卸载策略，对于提升蜂窝网络应对数据流量激增的能力，具有十分重要的意义。 现有的研究主要集中于固定场景下的移动数据流量卸载，较少考虑用户的移动性，不能预知用户对何时处于邻近范围内，能够建立机会通信进行流量卸载，并且这些研究需要依赖于具体已知的流量卸载需求[6-9]，无法在动态场景中根据流量负载的变化趋势，做出最优的流量卸载决策。针对用户移动的不确定性，本文首先提出了一种算法来预测哪一部分用户之间能够建立机会通信。然后在此基础上，针对完全信息和不完全信息两种应用场景，本文分别通过Stackelberg博弈建模和强化学习中Gradient Bandit算法，为运营商、内容提供方和内容需求方三方设计了系统效用函数，求解使总效用最大化的流量卸载策略，并将该算法应用在真实的手机用户上网数据集，实验结果表明，本文提出的方法可以有效减轻蜂窝网络的流量负载压力，能够用于指导两种应用场景中的流量卸载决策。本文的方法为基于机会连接的移动数据流量卸载策略研究提供了一种新思路。 1.2 国内外研究现状 移动数据流量卸载（Mobile data offloading）[10]是近年来兴起的一种新兴技术，利用互补网络分担原本在蜂窝网络上传输的数据流量，能够有效解决蜂窝网络流量负载问题，并且可以提升用户的使用体验，减小用户的数据流量费用，提供更大的接入带宽。由于大部分互补网络已经存在或部署代价较小，相较于建设更多宏蜂窝网络基站，升级网络配置的传统措施，移动数据流量卸载在经济成本、建设周期等投入代价方面有着巨大的优势。因此，移动数据流量卸载的研究成为一个热点问题，引起了业界学者的广泛关注。 1.2.1 基于互补网络的流量卸载研究现状 从互补网络技术来看，当前的移动数据流量卸载方式主要有基于WiFi网络、基于微蜂窝（Femtocell）和基于IP流移动性等方式。在基于WiFi的流量卸载方面，WiFi是基于IEEE 802.11系列标准的无线接入技术，主要用作室内环境的带宽接入，有着接入速率快但是覆盖范围有限的特点。目前大部分智能设备都配备有WiFi网络接口，很多家庭、办公场所和公共场所都有WiFi网络覆盖，并且WiFi的流量资费低于3G、4G的流量费用，因此利用已经部署好的WiFi网络，进行移动数据流量卸载，具有很大的优势。Lee[11]通过分析100位志愿者的移动设备在2周半时间内接入WiFi数据，对基于WiFi的3G移动数据流量卸载方案的性能进行了定量的研究，实验结果表明WiFi能够有效卸载约65%的移动数据，同时可以节省55%的电量消耗。Balasubramanian[12]针对3个城市中移动车辆接入3G和WiFi网络的数据进行研究，3G和WiFi网络的可用性分别为87%和11%，通过延迟传输和快速切换进行基于WiFi的流量卸载，首先预测WiFi的可用性，如果传输可以在容忍延迟时间内完成，就延迟数据传输，对于时延敏感的数据，就快速切换到3G网络，实验结果表明当容忍延迟时间为60s时，可以卸载约45%的数据量。Dimatteo[13]基于San Francisco500辆出租车30天的真实移动数据集，对城市范围内基于WiFi卸载的性能进行研究，根据数据传输服务质量的不同要求给出WiFi接入点数量，结果表明在增加有限WiFi接入点时，超过50%的3G流量可以被卸载，并且超过半数的请求传输时延减小。Ristanovic[14]通过运营商预测，当用户靠近WiFi接入点时下载内容，从而成功卸载一部分流量。Bulut[15]分析了大规模的用户移动数据，基于用户数据请求的频次，设计了一个在城市场景中具体部署WiFi接入点的算法，在实验中改变接入点个数，计算对应的流量卸载比例，该算法可以有效进行移动数据流量卸载。Siris[16]提出一种通过预测移动性，将延迟容忍和延迟敏感2种类型的数据卸载到WiFi的流量卸载算法，并且评估了流量卸载比例、传输时延和缓存大小对于算法性能的影响。 在基于Femtocell的流量卸载方面，Femtocell是小型、成本低、功耗小的基站，一般都部署在家庭和工作地[17]。相较于WiFi主要针对的是非授权频段，Femtocell主要针对的是授权频段，用户移动设备产生的数据流量不通过宏蜂窝网络基站传输，因此Femtocell能够有效减小蜂窝网络的负载压力，同时提升用户服务质量。Schroder[18]通过用户协助的方法来避免干扰问题。Ramaswamy[19]和Das[20]将蜂窝小区之间的干扰视为高斯随机变量，探究了Femtocell的反向链接能力。文献[21-23]研究了Femtocell的移动性管理和访问控制，利用访问控制来改进干扰。在基于IP流移动性的流量卸载方面，运营商可以无缝地选择一个独立的IP流切换到其它的无线连接上，并且维持其它用户正在进行的通信连接，这个技术作为一种可以实现3G无缝流量卸载的方法已经被纳入了3GPP[24]。 1.2.2 基于机会连接的流量卸载研究现状 在基于机会连接的流量卸载方面，机会连接是通过移动终端之间的接触机会而建立的通信连接，主要针对诸如多媒体视频、音乐、新闻和娱乐等有时延容忍性的数据，用户先从运营商获取这些数据，当这些用户和其它用户在可以通信的邻近范围内时，利用WiFi、蓝牙和红外等短距离通信技术进一步将这些数据转发给相邻的用户，由于经济成本较低，基于机会连接的移动数据流量卸载是一种有较大潜力应对流量激增问题的解决方案。 Baier[25]设计了一套机会机制的流量卸载方法，通过预测用户的移动性，计算用户流量卸载的潜力，将潜力较大的用户流量卸载到功率较低的基站，仿真实验结果表明该方法可以分担约40%蜂窝网络的流量。Izumikawa[26]将蜂窝网与机会网络结合起来，利用存储-携带-转发机制，对上行链路进行流量卸载。Han[27]阐述了基于机会连接的流量卸载的可行性，并且分别利用随机方法、贪心方法和启发式方法等进行流量卸载。在文献[28]中Han将蜂窝网络中的流量卸载到机会网络中，选择k个用户作为初始集合进行内容传输，这些用户通过诸如蓝牙和WiFi等近距离无线连接将内容进一步转发给其它用户，结果表明基于历史记录采用启发式算法选择初始用户集，可以从蜂窝网络卸载一大部分数据。Hui[29]通过识别用户社交网络，将特定的内容传输给某个社交群体，从而进一步提升传输效率。Li[30]和Andreev[31]提出利用DTN网络（Delay Tolerant Networks, 时延容忍网络）进行移动数据流量卸载，用户终端的一部分数据不需要实时的传输，先暂时存起来，等待和其它设备在无线通信的邻近区域内时，再将这部分数据分发给其它用户。Mehmeti[32]面向延迟容忍的流量卸载，提出了一个队列模型，根据数据大小、时延、卸载效率等参数，对延迟容忍流量卸载的收益进行定量分析，通过为各种类型数据设置延迟时间门限值，最优化流量卸载带来的收益。由于基于WiFi的方式具有接入速率快但覆盖范围有限的特点，基于Femtocell的方式主要用于室内环境，基于IP流移动性的方式需要修改终端软件或网络协议代价较大，而基于机会连接的流量卸载方式灵活成本较低，是一种高效灵活的应对流量激增的解决方案，因此本文主要研究了基于机会连接的移动数据流量卸载策略。 1.3 本文的主要内容及结构安排 本文基于手机用户上网记录数据，通过构建模型和实验分析对基于机会连接的卸载策略进行了研究，主要内容包括：首先对用户的移动行为和上网行为进行统计分析，其次提出了一种机会连接预测算法，预测用户何时能够建立机会连接，然后在此基础上进一步针对两种应用场景，分别通过构建Stackelberg博弈模型和强化学习中的Gradient Bandit算法，为运营商、内容提供方和内容需求方三方设计了系统效用函数，求解使总效用最大化的流量卸载策略。 本文的组织结构和主要内容安排如下： 第一章阐述了本文的研究背景与意义，并且介绍了移动数据流量卸载的相关研究现状。 第二章对用户行为进行统计分析。首先介绍了本文的数据集及其包含的字段和相关含义；其次对数据进行了预处理，对数据集中由振荡效应引起的异常记录进行了清洗；然后对用户移动行为和上网行为进行了统计分析。 第三章通过构建复杂网络模型，并对拓扑结构和个体行为特征进行了分析，然后利用随机森林模型对用户机会连接进行预测。 第四章提出了一种在完全信息场景中的流量卸载算法，将运营商、内容提供方和内容需求方三方之间的交互行为建模为Stackelberg博弈，首先为内容需求用户、运营商和内容提供用户三方分别设计了效用函数，其次证明了本文构建的Stackelberg博弈模型中Nash均衡的存在性，然后利用迭代算法求解最优定价和流量卸载策略，并通过实验验证了上述算法的有效性。 第五章提出了一种在不完全信息场景中的流量卸载算法，首先基于真实数据集进行用户历史机会连接分析，其次设计了系统效用函数，然后利用强化学习Gradient Bandit算法求解使总效用最大化的流量卸载策略，实验结果表明该算法能够有效减轻蜂窝网络的流量负载压力。 第六章对本文的主要工作进行了总结，指出本文工作中存在的有待改进之处，并对今后的研究工作进行了展望。 2 用户行为统计分析 2.1 数据集信息 本文的数据集从我国浙江省金华市的运营商处获取，包括了个体使用手机上网的所有记录。数据规模如表21所示。 表21本文数据集规模 记录数 42,023,038 用户数 1,614,291 基站数 8,845 数据集起止时间 2014/11/21~2014/12/13 当用户使用终端设备进行上网浏览内容时，由于运营商的计费需要，用户上网生成的有关数据业务信息会被存储下来，这些信息包含了经过模糊处理后的用户编号、所位于的基站编号、开始和结束时戳、消耗的上行及下行流量和当前访问的资源URL等信息。图21(a)展示了一部分MySQL中的用户数据流信息记录样本，图2-1(b)展示了基站信息表中部分记录，包含了基站编号、经纬度、所属行政区划和数据流发生的场景等详细信息。 （a） 数据流记录详情表 （b） 基站详情信息表 图21本文数据集示例 数据集中用户数据流信息表和基站信息表中各字节详情信息如下表所示。 表22用户数据流表格字节含义 字节 含义 模糊处理后的用户编号 基站所在区域的地区编号 扇区编号 数据流起始时间 数据流截止时间 上行流量（单位：B） 下行流量（单位：B） 访问的URL资源 从表22和表2-3可以看出，用户数据流记录表和基站信息表中都包含了2个相同的字段和，由于一组可以唯一标识一个基站，因此我们利用和对这两张信息表进行联合查询，通过用户当前接入的基站编号，在基站信息表中查询这个基站对应的经度和纬度，就可以得到用户上网所处位置。通过联合查询对数据集进行预处理后，每条数据流记录可以简化表示为一个八元组，将八元组表示为下式，其中各字段的含义符合表22和表2-3中的描述。接下来，本文对数据集进行了数据清洗，由于基站振荡效应[33]的影响，个体在多个基站间进行切换，导致存在一些异常记录，个体在较短的时间中以十分惊人的速度到达了相隔很远的位置。为了剔除此类异常数据，本文通过计算用户在相邻基站之间的移动速度，并以文献[34]中确定的速度阈值120 km/h为上限，剔除了所有移动速度超过120km/h的异常记录，保障了数据集的准确性。 表23基站信息表格字节含义 字节 含义 基站所处区域的地区编号 扇区编号 经度 纬度 所属行政区划 场景信息 2.2 用户移动行为统计分析 用户将自己下载浏览过的内容数据缓存在终端设备上，等到邻近范围内的用户请求这些内容时，利用WiFi或蓝牙等方式，直接将内容数据发送给用户。用户之间不需要经过回程链路，能够直接进行机会通信，需要满足以下3个条件：1）用户对在空间维度上有交集。由于WiFi和蓝牙都只能在短距离范围内进行通信，因此用户对处在邻近范围内，才可以进行通信。2）用户对在时间维度上有交集。两个用户需要满足通信时间有交集的条件，才能够进行机会通信。3）用户在兴趣维度上有交集。两个用户有内容上的共同兴趣，当一个用户已经下载过这个内容的数据，并在浏览后缓存在自己的终端设备上，当另一个有相同爱好的用户也请求相同的内容时，用户之间就可以直接进行传输。 本文对用户移动行为和上网行为进行了统计分析，在用户移动行为方面，分析了移动位置数量、回旋半径、移动距离；在用户上网行为方面，分析了上网时间间隔、数据流持续时间、同一基站下数据流时间交集、日均机会连接频次。通过分析机会通信的可行性，为进行基于机会连接的流量卸载奠定了坚实的基础。 （1）移动位置数量 由于人类行为的内在驱动性，用户在一天中会接入多个位置的基站，移动位置数量反应了用户在空间维度上的活动范围，用户访问的位置个数越多，说明用户空间活动范围越广，我们计算了在1天和23天内个体的移动位置个数，在双对数坐标中，图2-2（a）展示了概率密度函数（ ，），图2-2（b）展示了累积分布函数（ ，），从图中可以看出98%的用户在23天中的移动位置个数在15个之内，这说明用户在有限的区域范围内活动，每天只会接入有限个数的基站。 （a）PDF （b）CDF 图22移动位置数量分布 （2）回旋半径 为了进一步详细刻画用户的空间活动范围，本文计算了用户在一天内的移动回旋半径[35]，两个用户的空间移动轨迹和移动位置个数可能不一样，而他们可能有相同的回旋半径，这是因为回旋半径反映的是移动轨迹覆盖区域的大小，用户的回旋半径越大，说明这个用户在更广阔的空间范围内活动。回旋半径的计算公式如式（2-1）所示： （2-1） 其中，表示移动轨迹中第个位置，为用户移动范围内的质心位置，为用户访问的位置个数。用户在1天和23天内回旋半径的PDF和CDF曲线，如图2-3所示。 从图2-3（b）的CDF分布可以看出，90%的用户在一天内的移动回旋半径在5km以内，91%的用户在23天内的回旋半径小于15km，这说明用户大部分时间都在一定的活动半径内移动，在1天时间范围内，只有4%用户的回旋半径大于10km，在23天时间范围内，只有5%的用户的回旋半径在20km以上，这些数据表明只有一小部分用户会在较大的范围活动。 （a）PDF （b）CDF 图23回旋半径分布 （3）移动距离 本文对用户移动轨迹中两条相邻记录的空间距离进行了统计分析，假设用户的移动轨迹中相邻的两个位置记录分别为和，则用户在这2个基站之间的移动距离可以通过公式（2-2）计算得到： （2-2） 其中和为两个位置和的经纬度坐标，为地球半径。 图24移动距离分布 图2-4显示了移动距离的CDF和PDF曲线，从图中可以看出，85%的用户移动距离均在1km范围之内，这说明相邻记录的空间距离较小，用户在下载内容数据后，仍会在这个区域附近活动。通过观察移动距离的PDF分布，可以看出用户的移动距离近似服从幂律分布，本文的统计结果与文献[35][36][37]的结论一致，Gonzalez[35]基于10万用户的CDR (Call Detail Records)数据进行研究，发现个体局限在一定的范围内进行活动，并且论证了可以用带有指数尾部的幂律分布来对移动距离进行刻画。Brockmann[36]对人类移动行为进行分析，发现个体的移动步长服从幂指数为-1.59的幂律函数。Bin[37]利用出租车的GPS记录对移动行为进行研究，分析了瑞典四个城市中50辆出租车在6个月中的GPS数据集，发现用户的行车距离服从双段幂律分布。 2.3 用户上网行为统计分析 （1）上网时间间隔 上网时间间隔为用户两条相邻记录的时间间隔，上网时间间隔从另一个角度反映了用户使用移动互联网的频繁程度，图2-5（a）显示了上网时间间隔的PDF分布，图2-5（b）显示了上网时间间隔的CDF曲线，从图中可知，约89%的用户上网时间间隔大于10秒，当这个间隔时间设置为100秒时，用户的比例为37%。分析结果说明用户对移动互联网具有较强的依赖性，用户在一段较短时间内会多次访问互联网，两次相邻上网记录时间间隔较大。 （a）PDF （b）CDF 图25上网时间间隔分布 （2）数据流持续时间 数据流持续时间表示了数据集中每条数据流截止时间减去起始时间，数据流持续时间的CDF曲线如图2-6(a)所示，57%记录的会话持续时长大于10秒。同时，本文进一步统计了同一基站下数据流时间交集，两个用户的上网数据流时间上存在交集，并且都处在同一个基站下，即可认为这两个用户相遇，同时出现在同一个地方，可以进行机会通信。数据流持续时间交集的CDF曲线如图2-6(b)所示，37%的时间交集在10秒以上，并且数据流持续时间只包括用户终端设备连接互联网获取内容数据的时间，用户停留在这个基站下浏览内容一般会花费更长时间，分析结果说明用户有较为充足的时间，利用机会连接直接传输内容数据。 （a）数据流持续时间CDF （b）数据流持续时间交集CDF 图26数据流持续时间和时间交集分布 （3）日均机会连接频次 根据2.2节和2.3节中对移动距离和上网时间间隔的统计分析结果可知，约89%的用户上网时间间隔大于10秒，85%的相邻记录空间移动距离均在1km范围内，这说明相邻记录时间间隔较大，并且相邻记录的空间距离较小，用户在下载内容数据后，会在这个区域附近停留较长时间，使两个用户之间建立机会通信，直接进行数据传输具有较大的可行性。本文对日均机会连接次数进行了统计，并绘制其CDF曲线，如图2-7所示。从图中可知，40%的用户在一天中有机会连接的次数大于4次，说明用户在一天内有较多机会进行机会连接。上述统计分析均说明利用机会连接进行流量卸载具有较大的可行性。 图27日均机会连接分布 2.4 本章小结 本章首先介绍了本文使用的用户上网记录数据集，并且详细介绍了数据集中包含的各个字段及其含义。然后，对用户移动行为和上网行为进行了统计分析，发现37%的用户在同一基站下数据流时间交集大于10秒，说明用户有比较充分的时间进行机会通信。同时，用户相邻记录的时间间隔较大，并且相邻记录的空间距离较小，说明用户获取内容数据后仍会在这个区域附近活动。进一步地，对日均机会连接次数进行统计分析，发现40%的用户日均机会连接次数大于4次。本章的分析结果表明用户建立机会通信具有较大的可行性，为后文进行基于机会连接的流量卸载奠定了坚实的基础。 3 基于用户行为分析的机会连接预测模型 目前的流量卸载研究没有考虑用户的移动性，无法预知用户之间何时会相遇，能够处于邻近范围内建立机会连接，从而进行内容数据传输。本文针对用户移动的不确定性，提出了一个机会连接预测算法，预测哪一部分个体对之间能够有机会连接的可能，从而来进行流量卸载。预测算法流程如图413-1所示，通过构建复杂网络，分析网络和个体行为特征，利用随机森林对各时段用户之间相遇行为进行预测。利用将来各时段哪些用户会相遇，能够在通信范围内传输内容数据的信息，制定在用户移动的动态场景下的流量卸载策略。 图31机会连接预测方法流程图 3.1 网络模型 随着移动互联网覆盖范围越来越广，智能终端设备越来越普及，用户可以十分便捷地使用手机进行上网。由于需要对用户上网进行计费，运营商记录了每一条用户上网生成的相关会话信息，这些信息精确刻画了用户上网的时间、地点、流量和上网内容等方面的情况。这些记录中包含的个体时间和位置信息，可以描绘出个体的移动轨迹，在此基础上可以进一步挖掘人类移动行为模式。在大数据时代涌现出许多可以刻画个体位置信息的数据，使得大量业界学者投身到人类移动行为研究中，其中对个体移动行为的预测问题吸引了学者的广泛关注。Song[38]在《Science》上发表了一篇开创性的文章，通过分析随机熵、访问量相关熵、时序相关熵，论证了个体移动行为的可预测性高达93%，从而激励更多学者投入这方面的研究。现有的大多数研究主要是针对单个个体轨迹进行预测，这些研究分别利用马尔可夫链[39]、高斯混合模型[40]、轨迹序列模式挖掘[41-43]、线性回归[44]和决策树[45]等方法来预测个体移动轨迹。 在个体相遇预测方面的研究中，有科研