278 计算机学报 2017年 模式克服广域网时延问题,通过局域网提供低延 与 Cyber Foraging依赖服务搜索服务器进行 时、高带宽的实时交互式服务. Cloudlet模式可以代理发现的机制不同, Cloudlet将移动终端上运 进一步细分为移动微云模式[2;和固定微云模行的应用程序以VM的形式直接映像迁移至附近 式[31:,其架构如图6所示.固定微云模式以计指定服务器执行,简化了移动终端功能.服务器通过 算能力较强的台式计算机提供云计算服务,通常这互联网与云端数据中心相连,可以将复杂的计算任 种连接方式能够提供较大的带宽和计算资源.移动务和延时要求不高的任务迁移到云端执行,进一步 微云通过移动终端组建微云,旨在随时随地提供接提高计算迁移的处理能力.此框架的不足在于,将移 入服务 动终端运行环境整体克隆到服务器,对服务器的资 源管理能力以及硬件水平都出了更高的要求 虚拟执行环境( Virtualized execution Environ ment)[3不再依赖专用的服务器,而是利用VM技 术直接在云端为移动终端建立运行环境.云端为每 个应用创建新的虚拟机实例,将迁移的VM克隆至 虚拟机实例中执行.该方案通过在移动终端的操作 系统和硬件间设置中间件,以支持运行时负载迁移, 移动终端和云服务器中虚拟机实例的同步,并支持 移动云 传输状态的暂停和恢复机制.然而,中间件及同步机 图6 Cloudlet架构分 制给移动终端带来了计算与流量的额外开销 表1迁移方案对比分析 系统框架 操作平台 决策 目标 粒度 划分迁移支持管理模式 Miscol12J 移动云节点代理 方法级 程序级 集中式 MAUI 云服务器代理/移动终端 动态程序级 集中式 Think Airton 云服务器 移动端 延迟/能耗 线程级 动态 系统级 集中式 Comet[43] 云服务器 多线程态系统级集中式 性能/能耗应用程序程序级集中式 本地分布式 用程序 系统级集中式 Cloudlet[T] 本地服务器 应用程序 系统级 小布式 云服务器 性能/能 动态系统级 集中式 Virtualized Execution environment3云服务器 应用程序 系统级 集中式 Clonecloud同样采用VM技术直接在云端建技术,一直得到学术界的广泛关注.文献[50]围绕位 立运行环境,不需要操作系统和应用程序作任何额置服务的体系架构,对主流定位技术、位置索引及查 外的改动. Clonecloud还针对不同类型的应用设计询处理等技术进行了总结,帮助我们全面深入地认 了3种不同的迁移算法来进一步优化迁移效率.除识了位置服务基于GPS[1等传统定位技术的位置 了将语音识别、图像处理等计算密集型的任务迁移服务覆盖范围大,技术成熟,已经在军事、交通等诸 到云端,将安全性检测也迁移至云端服务器,进一步多领域得到了广泛应用.然而,由于其存在穿透力 减轻终端负担.然而,基于应用程序多样性的迁移策弱,定位能耗大[2等问题,已经无法完全满足精确 略增加了移动终端的开销,单线程的部署方式也增室内定位、用户动作识别等新的移动应用需求.例 加了系统运行时的抖动.为了克服无线网络不稳定如,购物中心的自动导购指引服务、智能家居中的病 等弊端, Tango通过部署多副本的方式,在服务器人监护等.移动云计算模式已经被用来构建新型的 与移动终端同时执行计算任务,将最快返回的执行位置服务解决这些问题,并成为其重要支撑技术.本 结果作为输出,进一步提高了系统的可靠性.表1对章重点对基于移动云的室内轨迹追踪与导航、精确 上述主要计算迁移方案进行了对比分析. 定位与动作识别以及海量位置信息管理等近两年学 术界研究的热点进行深入分析与总结 3基于移动云的位置服务 3.1室内轨迹追踪与导航 由于室内空间范围小,对导航的精度要求更高 位置服务作为移动云计算不可或缺的一项支撑另外,建筑物内部的空间结构、拓扑关系比室外复杂
模式克服广域网时延问题，通过局域网提供低延 时、高带宽的实时交互式服务．Ｃｌｏｕｄｌｅｔ模式可以 进一步细分为移动微云模式［１２，４５４６］和固定微云模 式［７８，１１，４７４８］，其架构如图６所示．固定微云模式以计 算能力较强的台式计算机提供云计算服务，通常这 种连接方式能够提供较大的带宽和计算资源．移动 微云通过移动终端组建微云，旨在随时随地提供接 入服务． 图６Ｃｌｏｕｄｌｅｔ架构分类 与ＣｙｂｅｒＦｏｒａｇｉｎｇ依赖服务搜索服务器进行 代理发现的机制不同，Ｃｌｏｕｄｌｅｔ［７］将移动终端上运 行的应用程序以ＶＭ的形式直接映像迁移至附近 指定服务器执行，简化了移动终端功能．服务器通过 互联网与云端数据中心相连，可以将复杂的计算任 务和延时要求不高的任务迁移到云端执行，进一步 提高计算迁移的处理能力．此框架的不足在于，将移 动终端运行环境整体克隆到服务器，对服务器的资 源管理能力以及硬件水平都出了更高的要求． 虚拟执行环境（ＶｉｒｔｕａｌｉｚｅｄＥｘｅｃｕｔｉｏｎＥｎｖｉｒｏｎ ｍｅｎｔ）［３４］不再依赖专用的服务器，而是利用ＶＭ技 术直接在云端为移动终端建立运行环境．云端为每 个应用创建新的虚拟机实例，将迁移的ＶＭ克隆至 虚拟机实例中执行．该方案通过在移动终端的操作 系统和硬件间设置中间件，以支持运行时负载迁移， 移动终端和云服务器中虚拟机实例的同步，并支持 传输状态的暂停和恢复机制．然而，中间件及同步机 制给移动终端带来了计算与流量的额外开销． 表１迁移方案对比分析 系统框架 操作平台 决策 目标 粒度 划分 迁移支持 管理模式 Ｍｉｓｃｏ［１２］ 移动云节点 代理 延迟 方法级 静态 程序级 集中式 ＭＡＵＩ［９］ 云服务器 代理／移动终端 能耗 方法级 动态 程序级 集中式 ＴｈｉｎｋＡｉｒ［１０］ 云服务器 移动端 延迟／能耗 线程级 动态 系统级 集中式 Ｃｏｍｅｔ［４３］ 云服务器 × 延迟 多线程 动态 系统级 集中式 ＣｏｇｎｉＳｅｒｖｅ［３９］ 云服务器 × 性能／能耗 应用程序 × 程序级 集中式 ＣｙｂｅｒＦｏｒａｇｉｎｇ［１１］ 本地分布式 代理 延迟 应用程序 × 系统级 集中式 Ｃｌｏｕｄｌｅｔ［７］ 本地服务器 × 延迟 应用程序 × 系统级 分布式 Ｃｌｏｎｅｃｌｏｕｄ［８］ 云服务器 × 性能／能耗 ＶＭ 动态 系统级 集中式 ＶｉｒｔｕａｌｉｚｅｄＥｘｅｃｕｔｉｏｎＥｎｖｉｒｏｎｍｅｎｔ［３４］ 云服务器 × × 应用程序 × 系统级 集中式 Ｃｌｏｎｅｃｌｏｕｄ［８］同样采用ＶＭ技术直接在云端建 立运行环境，不需要操作系统和应用程序作任何额 外的改动．Ｃｌｏｎｅｃｌｏｕｄ还针对不同类型的应用设计 了３种不同的迁移算法来进一步优化迁移效率．除 了将语音识别、图像处理等计算密集型的任务迁移 到云端，将安全性检测也迁移至云端服务器，进一步 减轻终端负担．然而，基于应用程序多样性的迁移策 略增加了移动终端的开销，单线程的部署方式也增 加了系统运行时的抖动．为了克服无线网络不稳定 等弊端，Ｔａｎｇｏ［４９］通过部署多副本的方式，在服务器 与移动终端同时执行计算任务，将最快返回的执行 结果作为输出，进一步提高了系统的可靠性．表１对 上述主要计算迁移方案进行了对比分析． ３基于移动云的位置服务 位置服务作为移动云计算不可或缺的一项支撑 技术，一直得到学术界的广泛关注．文献［５０］围绕位 置服务的体系架构，对主流定位技术、位置索引及查 询处理等技术进行了总结，帮助我们全面深入地认 识了位置服务．基于ＧＰＳ［５１］等传统定位技术的位置 服务覆盖范围大，技术成熟，已经在军事、交通等诸 多领域得到了广泛应用．然而，由于其存在穿透力 弱，定位能耗大［２６２７］等问题，已经无法完全满足精确 室内定位、用户动作识别等新的移动应用需求．例 如，购物中心的自动导购指引服务、智能家居中的病 人监护等．移动云计算模式已经被用来构建新型的 位置服务解决这些问题，并成为其重要支撑技术．本 章重点对基于移动云的室内轨迹追踪与导航、精确 定位与动作识别以及海量位置信息管理等近两年学 术界研究的热点进行深入分析与总结． ３１室内轨迹追踪与导航 由于室内空间范围小，对导航的精度要求更高． 另外，建筑物内部的空间结构、拓扑关系比室外复杂 ２７８ 计 算 机 学 报 ２０１７年
2期 崔勇等:移动云计算研究进展与趋势 得多,这对室内导航技术提出了更高的要求.当前针在100ms左右.为了提高TOA在有限的无线信道 对室内轨迹追踪与导航的研究主要通过群智的方式中的分辨率, Ontrack利用捷变频技术提高带 收集移动用户沿途拍摄的照片[83、手机信号强宽利用率AP在相邻信道获得3个数据包的情况 度5,并与加速、惯性等手机传感器数据融合,追踪下,就可以达到90cm的定位精度. SpotFiL利用超 用户行动轨迹,绘制建筑物内部平面图,进而实现实分辨率算法和估算技术计算多径分量的AOA,在普 时的定位导航.这些历史信息的收集、存储以及运算通AP上实现了40cm的定位精度. WiTrack2.o17 处理,需要耗费大量的存储与计算资源,这是普通移基于人体反射的无线电信号,在服务器端执行傅里 动终端无法胜任的.因此,大多数解决方案都是基于叶变换,实现了同时对5个人的定位,定位精度达到 公有云或者通过构建微云模式服务器设计实现的 针对构造室内地图需要进行现场勘测,耗费大3.2.2动作识别 量人力物力的问题,LiFS5通过收集用户移动过程 基于WiFi的人体动作识别是当前学术界研究的 中的手机信号强度,构造高维信号强度指纹空间,热点之一. IhEart通过专门的定向天线获取由唇形 将此映射为室内平面图 Jigsaw, mOon{321等系变化带来信道状态信息( Channel state information, 统则通过从移动用户处收集照片构建3D点云,以CS1变化,在云端服务器上运行机器学习算法,根 此为基础在云端服务器上构造建筑物内部地图.据人体发音时唇形的不同来辨别发出的单词,并基 mOon还允许用户拍照后上传到云端,与云端存储于上下文进行纠错.由于并没有有效地消除噪声,因 的地图进行匹配,以实现实时定位.Dong等人1利此该系统需要通过定向的天线来得到更高的精度 用基于密度的冲突检测技术对 mOon进行改进, ViDeo21基于目标物体动作对wFi信号反向散射 进一步提高了系统在障碍物位置的信息完善度,以的反射,实现对目标物体的定位及动作识别,在多人 及群智建立初始阶段的定位性能. Travi-Navi「,同时做动作的环境下,能达到7cm的识别精度 FOLLOWME等系统通过收集用户上传的照片、 E-eyes利用不同运动动作带来CS振幅不同来 手机wii信号强度指纹,实现用户行动轨迹记录,辨别包括洗澡、走路、洗碗等9种日常用户的行为 并采用加速、惯性等手机传感器数据进行校正.然但基本是以位置为导向的判断方法. CRAME除 后,基于这些轨迹信息绘制室内平面图,实现室内高了可以像E-eyes一样识别人们的日常行为动作外 精度的导航服务 还通过CSI- speed和隐式马尔可夫模型推测用户的 3.2室内精确定位与动作识别 移动速度和动作的幅度变化.在 CRAME研究的基 近年来兴起的智能家居、体感游戏等新型应用,础上,作者又提出了识别键盘敲击动作的wKey61 不仅对目标物体的定位精度提出了更高要求,还需识别准确率达到93.5%也有一些学者基于RFID、 要对用户的特定动作进行识别.当前针对室内精确VIC甚至声音实现人体动作识别、位置标记等. 定位与动作识别的研究通常以移动终端的无线信号Yang等人2提出 Tadar系统,通过RFID识别墙 强度( Received Signal Strength Indicator,RSSI)、体另一侧的人体动作变化. Luxaposel61、 PIXELL6 信号抵达时间( Time of arrival,TOA)和信号抵达等系统则尝试利用移动设备内置的照相机捕 角度( Angle of Arrival,AOA)4:等数据为输入,捉LED灯光的高频闪烁实现定位.基于VLC的 通过数学模型求解位置坐标,这些数据的存储、处理 HiSense系统,利用遮挡二维阴影信息重新构造 以及复杂的求解运算一般都需要在云端完成 人体的三维骨架图. EchoTag则是通过手机扬声 3.2.1精确室内定位 器主动发出声音信号,由麦克风感测回声的方式,实 Iim等人56将定位的WiFi访问点( Access现精度1cm的室内位置标记 Point,AP)增加到3个,将收集到的RSS和AOA3.3海量位置信息管理 信息发送到云端服务器,执行三角测量算法进行实 在移动云计算环境中,一方面,定位技术不断发 时跟踪定位,将定位精度提高到0.5m~0.75m区展,为移动应用提供越来越精准的位置信息;另一方 间内. Array track1基于AOA实现移动终端的室面,随着用户数量的增长和移动应用的丰富,用户位 内定位和实时跟踪,并通过MIMO技术和多路径置、轨迹等数据量爆发式增长,查询请求剧增、查询 抑制算法来减少室内多路径反射的影响,将定位空间变得更广,位置服务系统也越来越依赖云平台 精度进一步提高到几十厘米级,同时将时延控制进行用户位置轨迹等数据的存储、计算、索引和查询
得多，这对室内导航技术提出了更高的要求．当前针 对室内轨迹追踪与导航的研究主要通过群智的方式 收集移动用户沿途拍摄的照片［１８，５２］、手机信号强 度［５３］，并与加速、惯性等手机传感器数据融合，追踪 用户行动轨迹，绘制建筑物内部平面图，进而实现实 时的定位导航．这些历史信息的收集、存储以及运算 处理，需要耗费大量的存储与计算资源，这是普通移 动终端无法胜任的．因此，大多数解决方案都是基于 公有云或者通过构建微云模式服务器设计实现的． 针对构造室内地图需要进行现场勘测，耗费大 量人力物力的问题，ＬｉＦＳ［５３］通过收集用户移动过程 中的手机信号强度，构造高维信号强度指纹空间， 将此映射为室内平面图．Ｊｉｇｓａｗ［５４］，ｉＭｏｏｎ［５２］等系 统则通过从移动用户处收集照片构建３Ｄ点云，以 此为基础在云端服务器上构造建筑物内部地图． ｉＭｏｏｎ还允许用户拍照后上传到云端，与云端存储 的地图进行匹配，以实现实时定位．Ｄｏｎｇ等人［５５］利 用基于密度的冲突检测技术对ｉＭｏｏｎ进行改进， 进一步提高了系统在障碍物位置的信息完善度，以 及群智建立初始阶段的定位性能．ＴｒａｖｉＮａｖｉ［１８］， ＦＯＬＬＯＷＭＥ［１９］等系统通过收集用户上传的照片、 手机ＷｉＦｉ信号强度指纹，实现用户行动轨迹记录， 并采用加速、惯性等手机传感器数据进行校正．然 后，基于这些轨迹信息绘制室内平面图，实现室内高 精度的导航服务． ３２室内精确定位与动作识别 近年来兴起的智能家居、体感游戏等新型应用， 不仅对目标物体的定位精度提出了更高要求，还需 要对用户的特定动作进行识别．当前针对室内精确 定位与动作识别的研究通常以移动终端的无线信号 强度（ＲｅｃｅｉｖｅｄＳｉｇｎａｌＳｔｒｅｎｇｔｈＩｎｄｉｃａｔｏｒ，ＲＳＳＩ）［５６］、 信号抵达时间（ＴｉｍｅＯｆＡｒｒｉｖａｌ，ＴＯＡ）和信号抵达 角度（ＡｎｇｌｅＯｆＡｒｒｉｖａｌ，ＡＯＡ）［１４，５７］等数据为输入， 通过数学模型求解位置坐标．这些数据的存储、处理 以及复杂的求解运算一般都需要在云端完成． ３．２．１精确室内定位 Ｌｉｍ等人［５６］将定位的ＷｉＦｉ访问点（Ａｃｃｅｓｓ Ｐｏｉｎｔ，ＡＰ）增加到３个，将收集到的ＲＳＳ和ＡＯＡ 信息发送到云端服务器，执行三角测量算法进行实 时跟踪定位，将定位精度提高到０．５ｍ～０．７５ｍ区 间内．ＡｒｒａｙＴｒａｃｋ［１４］基于ＡＯＡ实现移动终端的室 内定位和实时跟踪，并通过ＭＩＭＯ技术和多路径 抑制算法来减少室内多路径反射的影响，将定位 精度进一步提高到几十厘米级，同时将时延控制 在１００ｍｓ左右．为了提高ＴＯＡ在有限的无线信道 中的分辨率，ＴｏｎｅＴｒａｃｋ［１６］利用捷变频技术提高带 宽利用率．ＡＰ在相邻信道获得３个数据包的情况 下，就可以达到９０ｃｍ的定位精度．ＳｐｏｔＦｉ［５８］利用超 分辨率算法和估算技术计算多径分量的ＡＯＡ，在普 通ＡＰ上实现了４０ｃｍ的定位精度．ＷｉＴｒａｃｋ２．０［１７］ 基于人体反射的无线电信号，在服务器端执行傅里 叶变换，实现了同时对５个人的定位，定位精度达到 １１．７ｃｍ． ３．２．２动作识别 基于ＷｉＦｉ的人体动作识别是当前学术界研究的 热点之一．ＷｉＨｅａｒ［２０］通过专门的定向天线获取由唇形 变化带来信道状态信息（ＣｈａｎｎｅｌＳｔａｔｅＩｎｆｏｒｍａｔｉｏｎ， ＣＳＩ）变化，在云端服务器上运行机器学习算法，根 据人体发音时唇形的不同来辨别发出的单词，并基 于上下文进行纠错．由于并没有有效地消除噪声，因 此该系统需要通过定向的天线来得到更高的精度． ＷｉＤｅｏ［２１］基于目标物体动作对ＷｉＦｉ信号反向散射 的反射，实现对目标物体的定位及动作识别，在多人 同时做动作的环境下，能达到７ｃｍ的识别精度． Ｅｅｙｅｓ［５９］利用不同运动动作带来ＣＳＩ振幅不同来 辨别包括洗澡、走路、洗碗等９种日常用户的行为， 但基本是以位置为导向的判断方法．ＣＲＡＭＥ［６０］除 了可以像Ｅｅｙｅｓ一样识别人们的日常行为动作外， 还通过ＣＳＩｓｐｅｅｄ和隐式马尔可夫模型推测用户的 移动速度和动作的幅度变化．在ＣＲＡＭＥ研究的基 础上，作者又提出了识别键盘敲击动作的ＷｉＫｅｙ［６１］， 识别准确率达到９３．５％．也有一些学者基于ＲＦＩＤ、 ＶＬＣ甚至声音实现人体动作识别、位置标记等． Ｙａｎｇ等人［６２］提出Ｔａｄａｒ系统，通过ＲＦＩＤ识别墙 体另一侧的人体动作变化．Ｌｕｘａｐｏｓｅ［６３］、ＰＩＸＥＬ［６４］ 等系统则尝试利用移动设备内置的照相机捕 捉ＬＥＤ灯光的高频闪烁实现定位．基于ＶＬＣ的 ＬｉＳｅｎｓｅ系统［６５］，利用遮挡二维阴影信息重新构造 人体的三维骨架图．ＥｃｈｏＴａｇ［６６］则是通过手机扬声 器主动发出声音信号，由麦克风感测回声的方式，实 现精度１ｃｍ的室内位置标记． ３３海量位置信息管理 在移动云计算环境中，一方面，定位技术不断发 展，为移动应用提供越来越精准的位置信息；另一方 面，随着用户数量的增长和移动应用的丰富，用户位 置、轨迹等数据量爆发式增长，查询请求剧增、查询 空间变得更广，位置服务系统也越来越依赖云平台 进行用户位置轨迹等数据的存储、计算、索引和查询 ２期 崔勇等：移动云计算研究进展与趋势 ２７９
280 计算机学报 2017年 等管理,从而减轻移动端的存储和计算负载 节能的研究也大多基于这两类网络开展 面对庞大的用户位置和运动轨迹等历史数据,4.1.1 Cellular网络传输节能 学者们基于云平台的分布式处理方法,提出高效的 移动终端通过 Cellular网络传输数据通常采用 索引査询方案,旨在向用户提供快速的查询响应.无线资源控制协议( Radio resource control,RRC) Ma等人[将 Map-Reduce架构用在大规模历史轨针对RRC协议全过程的移动终端能耗测量显示,移 迹数据处理方面,该方案把时间和空间轨迹数据存动终端网络接口在完成数据传输后,会从高能耗状 储在不同节点上.在处理查询时,在不同的节点分别态转移到中间能耗状态,即尾能耗状态,其功率约为 执行查询操作,再合并输出查询结果. Eldawy等高能耗状态的50%.尾能耗状态结束后才会进入 人将 Hadoop上的 Map-Reduce架构改进,设计低能耗状态,功率约为高能耗状态的1%.尾能耗 了用于分布式处理空间数据的 SpatialHadoop系状态的设计是为了减轻状态转换的延迟和开销,然 统 SHAHED将现有的 SpatialHadoop系统,用而数据传输过程中存在的过多尾能耗状态却大大降 于卫星数据处理.文中将卫星的数据按时间、空间存低了移动终端的能耗利用率 储在不同的节点上,在索引端建立多重Quad-tree 前针对尾能耗状态节能的研究主要集中在两 时空索引结构,査询时返回时空卫星数据的热点图.个方面:一是通过改变尾能耗时间阈值来减少跳至 另外,用户针对这些海量位置数据的信息査询尾能耗状态次数及时间;二是通过传输调度来减少 需求也越来越旺盛.而随着査询数据库变多、査询空尾能耗. Labiod等人通过实验数据来获得最优静 间变得更加广泛,移动终端的计算能力和电池能耗态快速休眠时间阈值,然而这没有在真正意义上消 无法满足大数据下的查询服务.针对位置频繁变化除尾能耗,且不准确的估算会造成额外的开销 的移动终端,有些研究致力于索引技术的改进,提出 ailTheft机制2通过虚拟收尾机制和双队列调度 了基于Rtre、Bt- treelet、 Quad-treel2等索引算法进行预取数据和延迟传输的传输调度,以消除 结构,综合利用历史轨迹、当前位置等信息査询索尾能耗.与调整时间阈值相比,此方法减少了错误估 引,旨在提高查询的性能Cong等人3提出的算算造成的跳转延时和开销,但此方法并不适用于小 法,综合考虑空间相似度和标注信息相关度,通过倒数据传输. Tailender协议[通过对应用实现延迟 排表和R-tree索引,返回k个最相关的空间对象.或预取策略,合并数据发送状态,减少传输过程中 Zhang等人提出m最近关键字查询,用于找到m尾时间,达到节能目的.Zhao等人提出了基于 个空间最近并满足m个用户给定的关键字空间对GBRT的预测算法来预测用户下载网页后的浏览时 象.还有一些研究则希望通过将信息查询与推荐相间,当浏览时间大于一定阈值时,设备状态将从尾能 结合,以进一步提高用户体验.Shi等人[挖掘社交耗状态跳至低能耗状态.Cui等人[2设计了自适应 网络中群体用户潜在行为和喜好的相似性,设计在线调度算法 PerES来最小化尾能耗和传输能耗, LGM群体行为挖掘和推荐模型. 使能耗任意接近最优调度解决方案 4.1.2WiFi网络传输节能 4移动终端节能技术 移动终端在WiFi网络中的能耗浪费主要源于 CSMA机制中空闲监听(ⅡL)状态下的能耗.移动终 移动终端电池容量增长速度缓慢,迅速丰富的端在I状态下的功耗和数据传输时的功耗相当,是 移动应用与移动终端有限的电量的矛盾愈发突出. Cellular网络IDLE状态功耗的40倍左右.目前 移动终端电量已成为良好用户体验的瓶颈,也得到对于WiFi的能耗优化主要是基于802.11节电模 了学术界的广泛关注.为了深人理解移动终端能耗式(PSM),即通过睡眠调度算法减少IL状态的时 管理的研究,本节从数据传输节能、定位服务节能等间来达到节能目的.根据 Zhang等人[的测量 方面对节能方案进行梳理 PSM通过捆绑下行数据包来减少网络层延迟,减少 4.Ⅰ数据传输节能 了不必要IL时间.然而,由于载波感测和竞争使用 随着移动云计算的推广应用,移动终端无线传的存在,PSM本身不能够减少IL时间.他们发现IL 输的薮据量快速増长.无线数据传输能耗占移动终下即使使用PSM策略仍然消耗了大量能耗,在繁 端能耗的比例也越来越大.wiFi和 Cellular网络是忙网络中IL消耗能量占到80%,在网络接近空闲 目前应用最广泛的无线传输技术,因此网络的传输状态下消耗能量也占到60%
等管理，从而减轻移动端的存储和计算负载． 面对庞大的用户位置和运动轨迹等历史数据， 学者们基于云平台的分布式处理方法，提出高效的 索引查询方案，旨在向用户提供快速的查询响应． Ｍａ等人［６７］将ＭａｐＲｅｄｕｃｅ架构用在大规模历史轨 迹数据处理方面，该方案把时间和空间轨迹数据存 储在不同节点上．在处理查询时，在不同的节点分别 执行查询操作，再合并输出查询结果．Ｅｌｄａｗｙ等 人［６８］将Ｈａｄｏｏｐ上的ＭａｐＲｅｄｕｃｅ架构改进，设计 了用于分布式处理空间数据的ＳｐａｔｉａｌＨａｄｏｏｐ系 统．ＳＨＡＨＥＤ［６９］将现有的ＳｐａｔｉａｌＨａｄｏｏｐ系统，用 于卫星数据处理．文中将卫星的数据按时间、空间存 储在不同的节点上，在索引端建立多重Ｑｕａｄｔｒｅｅ 时空索引结构，查询时返回时空卫星数据的热点图． 另外，用户针对这些海量位置数据的信息查询 需求也越来越旺盛．而随着查询数据库变多、查询空 间变得更加广泛，移动终端的计算能力和电池能耗 无法满足大数据下的查询服务．针对位置频繁变化 的移动终端，有些研究致力于索引技术的改进，提出 了基于Ｒｔｒｅｅ［７０］、Ｂ＋ｔｒｅｅ［７１］、Ｑｕａｄｔｒｅｅ［７２］等索引 结构，综合利用历史轨迹、当前位置等信息查询索 引，旨在提高查询的性能．Ｃｏｎｇ等人［７３］提出的算 法，综合考虑空间相似度和标注信息相关度，通过倒 排表和Ｒｔｒｅｅ索引，返回犽个最相关的空间对象． Ｚｈａｎｇ等人［７４］提出犿最近关键字查询，用于找到犿 个空间最近并满足犿个用户给定的关键字空间对 象．还有一些研究则希望通过将信息查询与推荐相 结合，以进一步提高用户体验．Ｓｈｉ等人［７５］挖掘社交 网络中群体用户潜在行为和喜好的相似性，设计 ＬＧＭ群体行为挖掘和推荐模型． ４移动终端节能技术 移动终端电池容量增长速度缓慢，迅速丰富的 移动应用与移动终端有限的电量的矛盾愈发突出． 移动终端电量已成为良好用户体验的瓶颈，也得到 了学术界的广泛关注．为了深入理解移动终端能耗 管理的研究，本节从数据传输节能、定位服务节能等 方面对节能方案进行梳理． ４１数据传输节能 随着移动云计算的推广应用，移动终端无线传 输的数据量快速增长．无线数据传输能耗占移动终 端能耗的比例也越来越大．ＷｉＦｉ和Ｃｅｌｌｕｌａｒ网络是 目前应用最广泛的无线传输技术，因此网络的传输 节能的研究也大多基于这两类网络开展． ４．１．１Ｃｅｌｌｕｌａｒ网络传输节能 移动终端通过Ｃｅｌｌｕｌａｒ网络传输数据通常采用 无线资源控制协议（ＲａｄｉｏＲｅｓｏｕｒｃｅＣｏｎｔｒｏｌ，ＲＲＣ）． 针对ＲＲＣ协议全过程的移动终端能耗测量显示，移 动终端网络接口在完成数据传输后，会从高能耗状 态转移到中间能耗状态，即尾能耗状态，其功率约为 高能耗状态的５０％［７６］．尾能耗状态结束后才会进入 低能耗状态，功率约为高能耗状态的１％［７６］．尾能耗 状态的设计是为了减轻状态转换的延迟和开销，然 而数据传输过程中存在的过多尾能耗状态却大大降 低了移动终端的能耗利用率． 目前针对尾能耗状态节能的研究主要集中在两 个方面：一是通过改变尾能耗时间阈值来减少跳至 尾能耗状态次数及时间；二是通过传输调度来减少 尾能耗．Ｌａｂｉｏｄ等人［７７］通过实验数据来获得最优静 态快速休眠时间阈值，然而这没有在真正意义上消 除尾能耗，且不准确的估算会造成额外的开销． ＴａｉｌＴｈｅｆｔ机制［２２］通过虚拟收尾机制和双队列调度 算法进行预取数据和延迟传输的传输调度，以消除 尾能耗．与调整时间阈值相比，此方法减少了错误估 算造成的跳转延时和开销，但此方法并不适用于小 数据传输．ＴａｉｌＥｎｄｅｒ协议［７６］通过对应用实现延迟 或预取策略，合并数据发送状态，减少传输过程中 尾时间，达到节能目的．Ｚｈａｏ等人［７８］提出了基于 ＧＢＲＴ的预测算法来预测用户下载网页后的浏览时 间，当浏览时间大于一定阈值时，设备状态将从尾能 耗状态跳至低能耗状态．Ｃｕｉ等人［２３］设计了自适应 在线调度算法ＰｅｒＥＳ来最小化尾能耗和传输能耗， 使能耗任意接近最优调度解决方案． ４．１．２ＷｉＦｉ网络传输节能 移动终端在ＷｉＦｉ网络中的能耗浪费主要源于 ＣＳＭＡ机制中空闲监听（ＩＬ）状态下的能耗．移动终 端在ＩＬ状态下的功耗和数据传输时的功耗相当，是 Ｃｅｌｌｕｌａｒ网络ＩＤＬＥ状态功耗的４０倍左右［７９］．目前 对于ＷｉＦｉ的能耗优化主要是基于８０２．１１节电模 式（ＰＳＭ），即通过睡眠调度算法减少ＩＬ状态的时 间来达到节能目的．根据Ｚｈａｎｇ等人［８０］的测量， ＰＳＭ通过捆绑下行数据包来减少网络层延迟，减少 了不必要ＩＬ时间．然而，由于载波感测和竞争使用 的存在，ＰＳＭ本身不能够减少ＩＬ时间．他们发现ＩＬ 下即使使用ＰＳＭ策略仍然消耗了大量能耗，在繁 忙网络中ＩＬ消耗能量占到８０％，在网络接近空闲 状态下消耗能量也占到６０％． ２８０ 计 算 机 学 报 ２０１７年