无线网络中的移动预测综述

王莹，苏壮

（1.北京邮电大学信息与通信工程学院，北京 100876；2.北京邮电大学网络与交换技术国家重点实验室，北京 100876）

1 引言

随着移动互联网以及物联网、车联网的快速发展，终端设备正在急剧增加，无处不在的传感设备和智能设备产生了海量数据，包括天气状况、交通状况、地理位置、社交数据等[1]。与此同时，基于位置的服务也日益受到关注，收集用户的地理位置信息，可以更好地锁定用户并推出针对性服务。面对智慧城市带来的发展机遇，挖掘这些数据背后的规律能够解决众多问题。例如，在无线网络中，车辆、行人等个体的移动性引起小区的频繁切换和资源分配，由此导致的切换时延严重影响了用户对时延敏感型业务的体验。因此，为了更加充分合理地利用无线资源，学者们在移动管理方面进行了很多探索。众所周知，人类倾向于具有相似模式的循环行为[2-3]，这使从个体之前的历史位置信息中预测个体的移动成为可能。一旦移动被预测，就能获取用户在特定时间的位置，进而规划资源或者提供定制服务。

目前，移动预测在众多场景中被提出，包括旅游导航、交通控制、车联网和设备到设备（D2D,device-to-device）等。其中，在旅游导航中，通过预测人群的移动模式，对景点进行推荐，避免景区人群分布不均衡，能显著提高用户的游览体验。在交通控制中，预测车辆的移动规律，对车辆行驶路线进行规划，能够有效避免交通堵塞。在D2D 通信中，设备通过广播获取当前位置的邻近设备，并从中选取某个设备作为通信节点[4]，但由于节点的移动性，网络拓扑是非常不稳定的，双方脱离通信范围就会中断连接；如果预测到每个设备的移动方向，就能够选取更稳定的拓扑节点，提高通信连接的顽健性和传输速率。在无线网络移动管理中，对终端进行移动预测，并在切换到下一接入节点前预留通信资源，能够降低资源调度的时延，提高时延敏感型业务的体验质量。

此外，在无线传感网络（WSN,wireless sensor network）中，移动传感节点收集数据并发送到基站[5]，当基站通过定向天线与移动节点通信时，定向传输将信号强度集中在主瓣方向上，形成指向接收机方向的定向波束，能够提升通信容量并降低设备能耗，因此，预测移动传感节点的位置并和基站保持定向传输能够提供更高质量的数据服务。在车载网中，预测车辆的移动，并将车辆请求的内容预先缓存到即将接入的Wi-Fi 节点，在切换到该接入点后能够迅速获取数据，有效降低内容获取的时延[6]。总而言之，移动预测的应用场景十分广泛，因此对移动预测的研究是十分有价值的。

本文着重总结了移动预测的特征提取以及目前主流的移动预测方法，并结合无线网络场景分析了各类方法在不同场景的适用性。无线网络有多种结构和技术，包括LTE（long term evolution）、超密集组网（UDN,ultra dense network）、Wi-Fi、车载自组网（VANET,vehicle ad hoc network）等，这些网络在覆盖范围、规模、部署密度、稳定性等方面存在差异，因此在不同的场景中预测算法的适用性不同。最后分析了其他因素对移动预测的影响，并指出了未来的工作和挑战。

2 移动数据

移动预测所需的数据主要来自无线网络（GSM、Wi-Fi）中的日志、GPS 采样数据以及终端APP 签到信息。GSM 日志记录了用户在不同小区的接入记录、通话记录等，通过蜂窝定位技术能够映射为相应的位置信息，包括＜基站ID，终端ID，时间戳＞等信息。Wi-Fi 日志与之类似，记录了用户访问节点的接入历史、接收信号强度信息（RSSI,received signal strength information）等，通过室内定位技术能够映射为相应的位置信息，包括＜AP（access point），终端ID，RSSI，时间戳＞等信息。GPS 数据是目前移动预测最常用的数据，一方面，由于智能移动终端能够方便地获取GPS 信息，包括终端的经纬度和时间戳；另一方面，GPS 精确地记录了终端的移动轨迹，其轨迹可以由坐标点序列精确地描述，因此包含更加丰富的信息，能够更准确地提取移动模式。但是GPS 数据集通常较大，处理复杂度较高，并且纯粹的经纬度坐标缺乏位置含义，一般根据预测模型的需要，对数据进行特征工程处理，才能用于模式提取和移动预测。APP 签到数据是通过智能终端的APP 收集的，例如用户通过发布社交动态、团购、摄影等隐含位置信息的方式，获取操作APP 时产生的签到记录。

4 种数据对比及部分开源数据集总结如表1 所示。其中，通过GPS 采样的数据集GeoLife Dataset来自微软GeoLife 项目。该项目从2007 年4 月到2012 年8 月收集了182 个用户的轨迹数据。这些数据包含了一系列以时间为序的点，每一个点包含＜经度，纬度，海拔，时间戳＞等信息，共计17 621 条移动轨迹，总距离120 多万千米，总时间48 000 多小时。通过Wi-Fi 采样的数据集Dartmouth Campus Dataset[7]来自美国达特茅斯学院数千用户为期3 年的校园Wi-Fi 接入记录，该Wi-Fi 网络包含了近450个接入点，有大量的接入点切换记录。通过GSM采样的数据集Rice Context Dataset[8]来自Ahmad等获取的基站日志，该日志包含了10 个手机用户为期近2 个月的基站接入记录，每条记录包含基站每30 s 或60 s 采集一次的＜基站ID，信号强度，信道＞等信息。通过APP 签到采样的数据集Gowalla Dataset 来自Gowalla 的基于位置服务的社交网络签到数据，该数据集包含了近20 万用户近6 个月的600 多万条签到记录，每条记录包含＜用户ID，时间戳，经度，纬度，位置ID＞等丰富的信息。此外，研究者也可以根据条件自主获取符合研究要求的数据样本。

3 移动轨迹处理

移动预测首先要对移动轨迹进行处理。轨迹是由个体的移动形成的按时间连续的位置序列。轨迹的2 个要素分别是空间特征和时序特征。空间特征是在轨迹序列中元素所代表的位置含义，决定了移动预测的精度，同时能够反映个体的移动模式所具有的实际意义。通过对原始数据的处理得到有意义的轨迹序列，再结合适当的数据结构能够提高预测的性能。时序特征由采样方式决定，分为3 种：基于时间的采样方式、基于位置的采样方式和基于事件的采样方式。

3.1 空间特征

原始轨迹序列，如GPS 坐标序列，并不建议直接用来进行位置预测，因为预测的准确度较低，因此需要通过聚集、抽象来提取更高层次的空间特征。本文将空间特征划分为3 类：偏好区域的空间特征、偏好语义的空间特征和偏好路径的空间特征。

1)偏好区域的空间特征

偏好区域的空间特征表示区域性的空间位置，如“时刻T离开区域A，时刻T+1 到达区域B”，反映了简化的移动过程，其区域的粒度影响预测的精度。每个空间位置的定义往往与场景相关。常用的有路网模型和小区模型。

路网模型将平面划分为N×N个网格状区域，对每个网格进行编号，用户所处的网格就是该时刻用户的位置区域，如图1(a)所示。一种典型的路网模型——马里德网格模型，是在城镇通过横纵交错的道路将平面划分为网格状[9]，规定行人和车辆在道路上移动。在路网模型中，Wi-Fi 接入点或基站一般通过泊松分布分散在地图上。

小区模型的划分粒度一般和无线网络的具体类型有关，LTE 网络的基站覆盖较广，小区数目较少，位置状态也少，因此复杂度较低；而UDN 的微基站和Wi-Fi 的接入点十分密集，状态数多，复杂度高[10]，如图1(b)所示。

偏好区域的空间特征将地图划分为有限个区域，对于每一个用户，其位置状态即为对应的区域编号，用户在下一时隙将要到达的区域就是要预测的位置，这个区域可能是用户当前的区域，也可能是其他区域。 通过区域特征构造的轨迹序列为{r1,r2,…,ri,…,rn}，其中ri表示第i次采样用户所在的区域ID。

2)偏好语义的空间特征

偏好语义的空间特征表示有地理意义的空间位置，如“时刻T到达餐厅，时刻T+1 到达学校”，反映了个体的移动意图，是移动信息服务的起始点。每个地理位置的定义都与生活模式相关，典型的有兴趣点（POI,point of interest）模型和地标模型。

POI 模型[11]是个体在移动过程中有偏好的移动行为。在众多位置中，有一些是个体频繁访问的或长久驻留的，而有一些是偶尔访问的。其中频繁访问的位置定义为POI，是用户位置的状态，例如家、工作楼以及健身房等。POI 的提取通常通过GPS数据进行聚类得到，如图1(c)所示。以用户的兴趣点为空间特征能提高对个体移动模式的理解，不过也存在对偶尔访问，甚至从未访问的新颖位置的不可达问题，预测被局限在少数高频访问的位置。

地标模型将城市版图通过标志性地理位置表示，这些地标包括个体已经访问或者未曾访问的位置。相比POI 模型，地标模型在语义库中有更丰富的语料，但同时预测的维度也更高，如图1(d)所示。通过区域特征构造的轨迹序列为 {loc1,loc2,…,loci,…,locn}，其中loci表示第i次采样时用户所在的地标ID。

表1 4 种常用移动预测数据源对比

图1 空间特征示意

3)偏好路径的空间特征

偏好路径的空间特征表示移动行为中带有过程性的特征，表现为相对稳定的周期性重复的轨迹，如“时刻T到时刻T+1 经过学院路”，可通过GPS 传感器获取轨迹细节，反映了个体移动的典型轨迹。

在路网模型、POI 模型等空间特征中，移动预测将简化的位置作为预测的原子状态，将个体连续的移动路径抽象为在不同的位置间的转移，其抽象的粒度影响了预测空间的维度，粒度过大，虽然维度会降低，但是预测的精度也会降低而失去应用价值。相比而言，通过路径将轨迹朴素地表示[12]，能够近似描述个体的移动过程，达到路径细节的存储和复现。路径概率树[13]就是基于路径语义构造的数据结构，进行移动模式提取和预测。如图2 所示，移动轨迹被分割成多段路径。用户甲的轨迹序列为 {p1,p2,p4}，用户乙的轨迹序列为{p3,p4}。

图2 路径特征示意

3 种空间特征各有利弊。路网模型和小区模型数据处理简单，原始轨迹数据映射到该模型只需简单的距离测量，并且模型粒度容易调控，只需对网格数目调整即可，但是缺乏对个体移动规律的理解；POI 模型和地标模型便于理解个体的移动规律，但是预处理复杂，对驻留点的聚类复杂度高，并且忽视位置转移之间的具体移动过程；路径特征的预处理更加复杂，不仅要对驻留点、交叉点进行聚类和提取，还要进行冗余路径清洗和相似路径合并，抽象出典型的路径特征，但该特征包含丰富的移动细节，适用于各种需要移动预测的场景。

采用何种空间特征，需要由具体的应用需求决定，例如在蜂窝网小区切换中，只需要预测用户何时到达下一小区的覆盖范围，此时使用POI空间特征只会增加复杂度，而不会明显提高准确性和实用性。

3.2 时序特征

通过定位设备所收集的移动轨迹数据并非都是有价值的，过于密集或过于稀疏都会降低预测系统的性能，同时还要保证位置的特定时序以适应所应用的场景。因此要根据模型需要对数据进行采样构成特定时序的轨迹序列。采样方式有3 种[14]：基于时间的轨迹采样、基于位置的轨迹采样和基于事件的轨迹采样。

1)基于时间的轨迹采样

轨迹数据通过等时间间隔采样收集。例如GPS数据，目前移动终端大多都有GPS 传感器，能够等间隔5 s 获取＜经度，纬度，时间戳＞等定位信息，研究者也可以设置更大的时间间隔。

2)基于位置的轨迹采样

当地理位置发生改变时，将位置样本加入轨迹序列。例如Wi-Fi 接入点切换时和基站切换时的小区位置，以及经过数据清洗和路径提取后，路径发生转移时的路径位置。

3)基于事件的轨迹采样

当事件发生改变时，将位置加入轨迹序列，如使用智能终端发布社交动态、购买一张电影票或者餐票、登录购物商城等。通常由智能终端的APP 在使用过程中产生，常用的有社交网络的签到数据。基于事件采样依赖于智能终端的使用动作，且记录的用户行为并不完整。

以图1(a)网格中的移动轨迹为例，其采样的数据空间如图3 所示。

图3 基于时间和位置的轨迹采样

4 移动预测模型

移动预测主要解决2 个问题：个体在何时到达下一个位置以及个体的下一个位置是何处。前者要预测的是个体在一个地点的到达时间和驻留时间，是基于时间序列的移动预测；后者要预测的是个体的下一个驻留地点，是基于位置序列的移动预测。如果同时兼顾二者，由于个体的移动在时间维度和空间维度都有很大的随机性，目前还很难做到较高的预测准确度。

随着人工智能和大数据的发展，一些新的预测模型在移动预测上产生良好的效果。因此本文通过数学方法对移动预测模型进行分类，将预测方法分为3 类：基于概率统计模型的移动预测、基于判别模型的移动预测和基于频繁模式挖掘的移动预测。

4.1 基于概率统计模型的移动预测

基于概率统计的机器学习算法在处理大规模样本分类和线性系统学习中有高效和灵活的优点。常用的有马尔可夫模型（MM,Markov model）、隐马尔可夫模型（HMM,hidden Markov model）、贝叶斯模型等，通过计算联合概率预测可能的位置。

4.1.1 基于马尔可夫模型的移动预测

马尔可夫模型根据样本数据计算各个状态的转移概率，建立马尔可夫链，通过初始时刻位置状态和状态转移概率矩阵，计算未来时刻位置的概率并进行预测。马尔可夫链是具有马尔可夫性的随机变量序列，变量的所有取值范围被称为状态空间，在移动预测中位置集合就是状态空间。而k阶马尔可夫链意味着时刻t所处的状态分布与t之前的k个状态有关，是一种“有限记忆”系统。因此只要求系统中任意2 个状态之间的转移概率就能确定模型。假设轨迹序列为 {…,st-2,s t-1,st,st+1,st+2,…}，由一阶马尔可夫链定义可知，st+1的状态只与st有关，其满足条件概率

马尔可夫模型是应用最广泛的位置预测方法，但该模型也存在一些缺陷。对于高阶马尔可夫链存在复杂度太高和零频率问题，而低阶马尔可夫链的准确性不高，因此研究者在马尔可夫链的基础上提出了改进方法，他们分别从引入社交特征、弱预测器集成学习、变阶马尔可夫的角度对马尔可夫预测进行改进。其中，文献[15]以马尔可夫模型为基础对节点的移动性进行初步预测，然后利用与其社会关系较强的其他节点的位置对该节点的预测结果进行修正。文献[16]将马尔可夫模型与回归模型进行集成学习，通过投票机制提升性能。文献[17]通过变阶马尔可夫模型的逃逸机制来解决零频率问题，并采用树结构来减少高阶马尔可夫模型所需的内存。文献[18]基于个体的历史上车和下车记录，构造出行事件的位置序列，预测用户的出行需求并提供给用户个性化打车服务。文献[19]引入时间因素对移动的影响，对马尔可夫状态转移概率引入参数加以修正。文献[20]通过非齐次马尔可夫从驻留时间序列中预测移动用户何时离开当前位置以及下一步到达何处。研究者还针对轨迹片段缺失、数据稀疏等样本问题做出改进，引入新的特征或数据提高预测准确性。其中，文献[21]针对不完全轨迹，放宽模型假设的马尔可夫性质，对马尔可夫链的条件转移概率重新定义，使其适用于断续轨迹的预测。文献[22]解决在使用单个用户的轨迹数据建立状态转移矩阵时所产生的数据稀疏性问题，通过度量用户移动行为相似性的方法，将用户进行聚类，对同组用户建立共享状态转移矩阵。文献[23]采用马尔可夫模型进行位置预测，同时采用概率密度函数对离开时间和到达时间进行预测，对预测的结果进行结合，在一定程度上克服了马尔可夫模型无法兼顾时空特征的缺点。

4.1.2 基于隐马尔可夫模型的移动预测

HMM 是一种特殊的贝叶斯网络，它有5 个元素，如图4 所示，包括有限的隐藏状态S、有限的观察状态O、隐藏转移概率矩阵A、观察转移概率矩阵B和状态概率π。其中，S、O都是已知，HMM 可以表示为λ=[A,B,π]，通常利用Baum-Welch 算法学习参数λ。在一些场景中，无法直接获取某状态空间（隐藏状态）的值，但是能够通过另外的状态空间（观察状态）间接获取，此时马尔可夫模型不再适用。在移动预测中，将空间特征作为隐藏状态，相应的时刻为观察状态，就能够将时间特征和空间特征关联，预测未来某个时段的位置。

图4 隐马尔可夫模型

研究者从应用的角度提出HMM 移动预测，其中，文献[24]提出一种Wi-Fi 场景AP 选择方案，通过预测用户移动获取高质量的连接，同时降低扫描能耗，该场景为室内移动预测，无法直接观察到用户的历史位置，但通过历史的AP 连接记录作为观察序列能够间接预测用户的位置。文献[25]提出一种自适应流媒体（DASH,dynamic adaptive streaming over HTTP）的视频质量智能调控方案，用户所在的道路弧段为隐藏状态，包含噪声的GPS 采样点为观察状态，预测将要到达的路段，结合用户位置和速度进行带宽估计，进而自适应调整视频源的编码。文献[11,26]则分别根据位置熵（位置熵[9]是指根据用户访问各个地点的概率或频次计算的信息熵，反映用户移动的规律性程度）和社交距离对用户进行分组，并对各组用户分别训练隐马尔可夫模型，同组用户模型共享，相对地提高了整体预测性能。

2 种模型从统计的角度出发，能够充分利用先验知识，但也意味着需要丰富的数据关联信息。此外，用于移动预测的概率统计模型还有多种。文献[27]利用高斯混合模型进行预测，每个高斯分布代表一个特征的概率分布，对预测的结果由高斯分量加权的概率表示，在数据样本不足以及数据关联模糊的情况适用。文献[28-31]利用朴素贝叶斯模型进行移动预测，朴素贝叶斯模型要求各个特征之间相互独立，如果特征之间有很强的关联性，会导致朴素贝叶斯模型效果不佳，但它是最易实现的线性分类器。

4.2 基于判别模型的移动预测

基于概率统计的模型能够对线性系统进行高效的学习，但是对分类决策存在较高的错误率，从概率分布的角度考虑，属于生成模型（马尔可夫模型除外）。生成模型根据大量样本统计目标序列和观察序列的联合概率，产生概率密度模型进行预测，反映同类数据的相似度，不关心判别边界，能够充分地利用先验知识；判别模型根据有限样本生成判别函数进行预测，寻找不同类别之间的最优判别边界或分类面，反映的是异类数据之间的差异。生成模型的收敛速度更快，但是分类效果往往弱于判别模型，判别模型如支持向量机（SVM,support vector machine）、人工神经网络（ANN,artificial neural network）、深度神经网络能够逼近任意非线性函数，有更加强大的学习能力。

基于判别模型的机器学习算法如SVM、ANN通常用于分类问题。在移动预测中，通过原始轨迹处理和空间特征提取，构造出样本长度为n的轨迹序列 {l1,l2,…,ln}，通过滑动窗口取出长度为steps的元素，作为分类任务的特征向量，将滑动窗口外的下一个元素作为分类任务的标签，从而构造出分类数据集，滑动窗口越大，意味着受越多历史时隙的位置影响。数据集构造方法如图5 所示，本质上是将预测问题转化成了分类问题。

图5 训练所用的数据

4.2.1 基于SVM/ANN 的移动预测

SVM 适用于解决中小样本、非线性以及高维问题，对于数据噪声有很强的抗噪能力，能够降低异常值对模型的影响。其分类的基本思想是通过定义适当的核函数，将输入空间非线性变换到高维空间，并在此高维空间寻找支持向量来组成最优超平面。由于所预测的位置有多种可能，需要利用多值SVM 进行预测。ANN 在处理随机数据、非线性数据方面具有明显的优势，对数据规模大、信息不明确的系统尤为适用，并且模型结构简单，当数据充足时，ANN 能有效应用于移动预测，有较强的顽健性和容错能力，但缺点是神经网络需要大量的参数，训练时间较长。

利用上述2 种算法进行移动预测，很方便引入其他特征，例如天气特征、交通特征等，通过特征工程处理后，对图5 方式构造的特征向量进行扩充，构造新的特征向量，在无法获取不同特征内在关联情况下能够简单有效地将多种特征结合。文献[32-33]利用多值SVM 在异构网络中对终端进行移动预测，避免了马尔可夫模型的维数灾难，所输入特征向量采用图5 所构造的数据样本。其中，文献[32]为区别随机移动模式（移动的规则性和可测性较低的移动模式，只受近期位置影响较大）和规则移动模式，通过设定位置熵阈值将用户进行区分，并对二者采用不同维度的特征向量进行预测。文献[34-35]将ANN 应用于车载云计算，利用ANN 预测车辆路线，在路边单元切换过程前预留计算资源，使计算任务快速迁移。

上述传统机器学习方法在短期的移动预测中效果良好，但是对于长期的预测能力不足。例如用户在工作日每天的行程大多是规律的，但是每个周末会去俱乐部或游泳馆活动，以及每个月初会去医院检查身体，这种长期的行为模式是普遍存在的。但是对于这类移动模式，传统的机器学习方法往往会当作异常值处理，若单纯地增大网络规模来提高训练准确度，会产生过拟合现象。而基于深度学习的移动预测能够有效解决此问题。

4.2.2 基于深度学习的移动预测

基于深度学习的预测模型如循环神经网络（RNN,recurrent neural network）能够处理大规模的数据集，并从中挖掘出长期的时间依赖关系。RNN因其具有记忆性而被广泛应用于机器翻译、自然语言处理等领域，它能保留多个历史采样时刻的数据对当前采样产生的影响，因此方便用来提取具有循环移动行为的移动模式。实际应用中较少使用原版的RNN，因为训练过程会产生梯度爆炸或者梯度消失，导致记忆能力有限。实际中为了能够存储更长期的数据对后文的影响，采用RNN 的变体，如长短期记忆网络（LSTM,long short-term memory）、门控循环单元（GRU,gated recurrent unit）等，相比于RNN 存在梯度指数衰减而使网络后面的样本对前面的样本感知力下降的问题，LSTM 等能够过滤对后文有用的样本特征，从而训练更深层的网络。虽然版本不同，但训练和预测的过程是相同的。RNN 结构如图6 所示。

图6 多对一循环神经网络结构

图6 中，x表示输入层向量，其中xt表示第t（t=1,2,3,…）步的输入向量；步长代表循环周期，即最多能够通过隐藏层的连接获取多少步长的历史输入对目标的影响，例如ot+1能够获取x1,…,xt+1对其产生的影响，s t表示第t步的隐藏层输出，o t表示第t步的输出层输出；U表示输入层和隐藏层之间的权重矩阵；W表示连续2 个隐藏层间的权重矩阵；V表示隐藏层和输出层之间的权重矩阵。对于多对一（多个输入一个输出）网络结构，只保留最后一步的输出。

RNN 参数的传递式为

其中，f(⋅)为隐藏层激活函数，g(⋅)为输出层激活函数。在移动预测中，通过图5 方式构造数据集，要强调的是滑动窗口的长度和RNN 的循环周期保持一致。假设滑动窗口大小为 steps，将样本{l1,l2,…,lsteps}分 别输 入RNN 的每步的输入层，lsteps+1为输出标签，通过lsteps+1和ot计算损失函数并进行穿越时间的反向传播算法训练。预测时将目标前steps 步的数据样本传入模型，可直接得到预测值。

文献[36-37]针对位置划分维度过高导致LSTM 维数灾难，使用词向量代替One-Hot 编码提高学习效率。文献[38-39]通过引入车辆特征、方向特征、天气特征或文本特征提高RNN 预测准确性，例如车辆型号和行驶速度相关，而天气也影响车辆的驻留时间和行驶速度，通过卷积神经网络（CNN,convolutional neural network）将这些特征融合并嵌入LSTM 网络进行联合训练，有效地进行了车辆位置预测。文献[40]引入RNN 的Attention 机制，识别更长期的以及多种周期层次的移动模式，Attention 机制在模型输出时会选择性地专注考虑输入样本的某些信息，因此能够显著提高预测性能。

SVM 和ANN 只能进行短期预测，RNN 因为记忆性能够进行长期预测，但是复杂度较高，需要大量的训练样本，当样本数目少于某个阈值时，性能就会剧烈下降，产生欠拟合现象。

4.3 基于频繁模式挖掘的移动预测

数据挖掘常用的方法有分类、聚类、频繁模式挖掘（即关联分析）等。频繁模式挖掘建立在大数据的基础上，从海量的、有噪声的、不完整的、随机的数据中提取频繁出现在数据中的频繁项集。频繁项集能够发现大型事物或者数据之间的关联或相关性。频繁模式挖掘常用FP-Growth算法和Apriori 算法。利用Apriori 算法进行移动预测分为3 步，首先对用户原始移动轨迹进行特征处理，构造轨迹序列；然后对所提取的轨迹序列计算所有候选频繁项支持度，超过支持度阈值的候选频繁项构成频繁项集；最后通过置信度计算与当前序列最相关的频繁项，从而进行预测。其中，频繁项集就是所提取的移动模式，对当前轨迹序列和频繁项进行匹配，匹配到置信度最高的频繁项。

文献[41-42]分别利用FP-Growth 和Apriori 对移动进行预测，其中前者结合最长公共子序列算法进行改进，所谓最长公共子序列算法是通过发现和当前序列相似的历史最长公共子序列进行模式匹配；后者将人群移动模式应用于无线网络规划，改进基站的部署方案。文献[43-46]等对轨迹序列进行相似度度量，根据相似序列进行移动预测。文献[47-48]针对轨迹信息缺失、数据稀疏、冗余等问题做出特征处理及改进。文献[49]在马尔可夫模型中嵌入Apriori 关联分析来提高预测性能。

FP-Growth 算法将提供频繁项集的数据库压缩到一棵频繁模式树（FP-tree,frequent pattern tree），但仍保留项集之间的关联信息。频繁模式树是一棵特殊的前缀树，它解决了Apriori 算法会产生大量的候选集的问题。Apriori 算法需多次扫描数据，每次利用候选频繁项集产生频繁项集；FP-growth则利用树形结构，不需要产生候选频繁项集而直接得到频繁项集，减少了扫描数据的次数，效率更高，但Apriori 的算法扩展性较好，可以用于并行计算领域。

在实际预测中，很多研究者构造了其他树结构完成序列匹配。文献[46,50]通过概率后缀树采用单一序列的模式匹配进行预测。文献[13]构造了基于路径特征的概率基树进行决策，能够应用于多序列的模式匹配，如图7 所示，移动终端在路径a1有概率选择接连走路径a2a3，有概率选择走路径a4，依次类推，其转移概率是通过历史统计所得的位置转移频率。文献[51]综合考虑了用户的地理触发意图、时间触发意图和语义触发意图，与传统的频繁模式只能代表3 种意图中的一种不同，通过判断轨迹语义和时间属性来修正候选频繁项的支持度，生成更接近真实模式的频繁项集，有效地提升了预测性能。

图7 基于路径的概率树

以上总结了几种被广泛使用的移动预测算法，在应用中具体采用何种算法，需要根据数据集规模、移动的规律性、数据的连续性、异常值数量、时间复杂度、特征维度等综合考虑，每种算法都有各自的利弊，需要研究者合理利用算法的优势，甚至集成不同算法提升预测准确性。

5 其他因素对移动预测的影响

除了时空维度本身的规律，还有很多因素影响用户的移动，如天气特征、交通特征、身体特征等，因此移动预测是一个结合多维环境因素的复杂过程。例如天气因素，用户每天晚上都会去健身房，但是因为雾霾而暂停；又如交通因素，因为节日导致的交通拥堵迫使用户放弃外出活动。此外，还有社交因素、健康因素等，这些随机事件会扰乱用户的惯性行为，但又是时常发生的。本文对其中的社交因素进行重点阐述。

社交网络是用户社交关系的部分体现，相似的用户或者具有紧密社交关系的用户往往具有相似的行为模式，例如，用户甲和乙是关系密切的同事，那么在午饭时间有很大的概率同时从办公室到食堂就餐。因此基于位置的社交网络被用来对个体的移动性进行预测是有效的。文献[28,52]将社交关系作为影响移动的特征，对其他模型预测结果进行修正。文献[53-54]则考虑到移动预测基于历史数据，无法预测未曾访问的区域，引入社交关系协同滤波扩大预测候选集，解决部分新颖位置不可达问题。文献[55-56]应用图像识别和文本识别，从用户社交网络的文字图片中提取文本特征，增加特征维度来提高预测准确性。

6 无线网络场景中移动预测总结

无线网络是移动预测重要的应用场景。在蜂窝网、Wi-Fi 或超密集组网中，由于用户的移动性，基站或接入节点的资源（通信资源、计算资源）分配会随着时间变化。文献[7-8,24,57-59]将移动预测应用在不同的网络场景中预测即将接入的节点，在切换前预留通信资源，实现无缝切换服务，具体使用的预测模型因场景而异。文献[14,38,60]预测应用在车载自组织网络中，车载自组织网络相比于移动自组网具有车辆移动速度快、移动路径受限等特点，当车辆换道可能存在危险时，并线警告将提醒有意换道的驾驶员。并线警告使用V2V 通信和周边车辆的路径预测，利用链路的通信范围来预测驾驶员换道可能产生的碰撞。路径预测用于确定在3～5 s 的时间内，驾驶员要到达的车道区域是否被占用。如果该车道已被占用，则并线警告将会提醒驾驶员潜在的危险。文献[61]将预测应用在内容中心网络的主动缓存，预知用户移动性，在最佳预取节点缓存请求的内容，提高缓存的命中率。文献[62]将移动预测应用在移动边缘计算（MEC,mobile edge computing）的任务迁移，将应用发布的任务预先迁移到下一MEC 服务节点，避免任务迁移导致的长时间宕机而影响用户体验。以及上文提到的将预测应用在无线传感网络定向通信和自适应流媒体，实现智能调控视频质量。此外，还有更多应用值得研究者挖掘。

由于不同场景使用的轨迹序列的数据规模，特征维度以及预测目标的精度需求有所差异，采用的预测方法有所偏向。例如对于特征维度较高的数据，使用SVM 能够更好地进行分类及预测；如果所预测的位置状态较少，高阶马尔可夫模型综合性能良好且易实现；如果预测用户长期的移动模式，循环神经网络性能更好。

在无线网络中，采用何种算法并非绝对，影响算法性能的主要是所构造的轨迹序列，而轨迹序列是从原始数据通过特征工程得到的。因此，只要针对原始数据进行细致的特征处理，再选择合适的算法，就能得到针对该场景相对较好的预测性能。表2总结了研究较多的移动预测在无线网络中的应用。

表2 移动预测在无线网络中的应用

7 结束语

移动预测是智慧旅游、个性化服务、城市规划等场景重点关注的问题，目前学者致力于提高移动预测的准确性，为此提出了各种有效的模型，但也存在一些难以解决的问题。一是预测粒度、预测复杂度和预测准确性的权衡，为了提高预测的准确性，往往做出过于理想化的假设，但是其结果大多失去应用价值，而深度学习模型和频繁模式挖掘往往复杂度过高，在一些实时的应用场景如城市交通调度会有较大时延，难以应用。二是位置熵较高的非规则用户难以预测，位置熵越高概率分布越均匀，意味着用户移动更加随机，规律性不强，这类用户不遵循固定的行为模式。有学者尝试根据位置熵对用户进行分类，建立不同分组的预测模型，但是对位置熵高的群体，预测结果仍然不太理想。三是轨迹数据的发布会产生隐私泄露的风险，若被攻击者利用，会对用户的安全产生威胁，因此对轨迹数据的隐私保护尤为重要，目前隐私保护技术尚未完善。四是移动预测要解决的主要问题，即实现时间依赖与空间依赖结合的移动预测，目前的移动预测大多为2 种，根据位置序列预测用户的下一个位置，或根据时间序列预测用户驻留时间或到达时间，因为时间与位置之间的关联不稳定，预测的准确性不高，有学者通过将时间简单分段与位置建立关联，但所提出的解决方案缺乏准确性和顽健性。以上正是移动预测必须要解决的一些问题和难点。