移动计算中自适应负载转移决策模型研究

摘要

以智能手机为代表的移动设备，受限于设备自身的尺寸、大容量电池制造工艺的滞后、无线通信网络的不稳定，已经越来越难以满足移动用户对智能手机执行功能更加复杂、能耗需求更高应用的需求。移动设备系统电能消耗与电池容量增长速度的不一致，系统能提供的计算能力与新应用的需求增长速度的不一致是移动设备发展中面临的挑战。移动负载转移思想，提出移动设备可以与服务器构成一个协作系统，通过负载转移的方式将部分应用功能(任务)转移至(协作)服务器端远程执行，提升应用执行的性能，如减少执行时间、减少设备能耗、提高执行结果质量等。
　　 与之对应的移动协作应用由多个任务组成，包括若干个可负载转移任务，即该任务既可以在移动设备本地执行，也可以在协作服务器端执行。移动负载转移的核心问题是如何使得移动协作应用，一方面可以尽可能地通过远程协作提升执行性能；另一方面又尽可能地减少由于资源可用性变化造成的执行延迟或者失败。例如，减小移动设备到协作服务器之间端到端的带宽波动对数据传输时间的影响，减小服务器负载变化对执行时间的影响等。移动负载转移决策引擎的任务就是根据协作系统的资源可用性和移动应用执行性能要求，动态决定移动协作应用中，每一个可负载转移任务的执行位置。现有的决策引擎多采用“静态决策策略”，采用静态决策策略的决策引擎仅仅在应用执行前启动，为应用的每一个任务选择执行位置后即停止。在应用执行过程中，决策引擎不对协作系统资源可用性变化进行跟踪，不对应用执行进度进行跟踪，不再调整任务执行位置，直至执行完成或者确认失败。静态决策策略缺乏应对资源变化的灵活，可能导致应用执行的延迟、失败，或增加移动设备额外的能量开销。
　　 本文的工作1围绕如何使得移动负载转移决策引擎更加灵活地，自适应地应对协作系统资源可用性的变化，提高决策的准确性，提高应用执行的性能而展开。本文提出“执行路径”的概念描述移动协作应用中各个任务在远程或本地执行的不同组合，采用图论的方法对移动协作应用的执行过程进行建模。采用“应用执行路径图”描述一个移动协作应用各种不同的执行组合以及与之对应的执行路径。决策引擎的任务是根据协作系统资源可用性情况，目标函数(减少执行时间、减少设备能耗等)，应用执行性能要求等为应用选择一条最优的执行路径。一方面可以尽可能地有效利用系统资源，提升应用执行性能，同时也尽量减小执行延迟和失败的风险。为了改进“静态决策策略”的不足，本文提出一组“自适应决策策略”，具体而言，本文
　　 1.提出“动态决策策略”。动态决策策略允许决策引擎在应用执行的全过程中，跟踪协作系统资源可用性情况变化和应用执行进度，并且可以根据协作系统资源可用性变化，调整协作应用的执行路径。
　　 2.提出“冗余路径执行”。与现有的“静态决策策略”中，移动协作应用只能采取一条路径执行不同。冗余路径执行允许协作应用同时采用多条执行路径同时执行，最早返回的结果将被使用。同时，决策引擎通过引入概率风险模型，评估因为对协作系统资源可用性估值偏差造成错误决策的概率和相应的风险，辅助应用执行路径、单路径执行或者冗余路径执行方案的选择。
　　 3.提出“联合决策策略”。联合决策策略允许协作服务器一起参与移动设备的负载转移决策过程。移动设备可以共享应用执行的性能要求，如执行完成的时间期限、最低执行结果质量要求等。当协作服务器接收到移动设备的任务数据和执行要求后，可以根据自身负载情况动态调整，如在负载条件允许下，提供更高质量的执行结果等。
　　 4.提出“渐进式数据传输”模式，以减少网络波动对于数据传输的影响。由于在服务器端，计算处理和网络传输通常不会造成资源重叠，渐进式数据传输不会影响应用执行时间。先前数据传递时候的网络带宽测试数据，也可以作为后续传送时，估算传送时间的依据。
　　 评估实验采用移动人脸识别应用(mobile face detection)和移动全景图应用(mobile panorama)作为目标应用。在运行安卓(Android)操作系统的Nexus S智能手机上，分别实现了基于动态决策策略和支持冗余路径执行方案的Wing负载转移决策系统，以及基于联合自适应决策策略和支持渐进式数据传输模式的Mind负载转移决策系统。
　　 评估实验采用控制变量的方法，评估自适应决策策略在应对协作服务器负载波动时的决策质量。实验结果显示，相比静态决策策略，采用单路径执行的动态决策策略可以减少30％(50％)左右的应用执行时间，30％(50％)左右的设备能耗。同时，Wing系统在执行动态决策时候的决策时间开销很小，与采用静态决策策略的时间开销相似。
　　 评估实验采用基于网络Trace数据的模拟实验方法，评估自适应决策策略在应对移动设备到服务器之间端到端网络连接质量波动时的决策质量。网络Trace数据集合包括约2400分钟的WiFi网络Trace数据，涵盖静态应用场景和移动(步行)应用场景，总计约1万多条数据记录(上行带宽、下行带宽、往返时延等)，提供了约1万多个决策评估点。实验评估还采用了4种常见的基本网络带宽估值模型。评估结果显示，与静态决策策略相比，采用单路径执行的动态决策策略平均可以降低40-50％的错误决策概率，同时减少30%左右的应用执行时间，40-50%左右的设备能耗。采用冗余路径执行(路径切换时保留原有执行路径的)的动态决策策略平均可以降低30％左右的应用执行时间，降低30%左右的设备能耗。与静态决策策略相比，采用渐进式数据传输模式的联合决策策略，可以降低10-20%的错误决策概率。