面向上下文质量控制的服务调度研究

摘要

在普适计算的构想中，遍布于环境中的计算设施为用户提供无处不在的服务，而用户并不察觉服务和计算的存在。上下文感知计算(Context Aware Computing)通过收集与用户和环境相关的上下文信息，选择适时的、无干扰的服务行为，被认为是实现上述构想的关键。
　　 任何上下文感知计算应用，都客观地存在对上下文信息质量的需求。但是有多方面的因素引起上下文质量动态变化，进而影响应用的服务质量。其中，上下文信息服务系统受成本、技术条件等限制，只能提供有限的资源用于上下文服务，因而不能始终满足应用对上下文质量的需求，称为影响上下文质量的资源因素。
　　 为消除和缓解资源因素的影响，需要合理地组织上下文服务对有限资源的使用，从而有效控制上下文的质量，本文称之为“面向上下文质量控制的服务调度”。相关的研究有两种思路，其一是在确保上下文具有一定质量的前提下，尽量减少服务资源的使用；代表性的研究是以减少数据更新为目标的各种filter协议，已有丰富的研究成果。其二是在限定服务资源用量的前提下，保证和优化上下文的质量，实现手段为上下文服务的调度算法。本文的研究基于第二种思路，根据资源因素影响上下文的不同表现形式，分别设计不同的服务调度方案。
　　 有限资源影响上下文质量的具体表现，是在消耗资源的上下文服务达到一定数量时，不能充分满足每项服务对上下文每个方面的质量需求——满足其中一部分，将导致另一部分不能满足——因此在上下文服务之间，以及上下文质量多方面需求之间产生各种形式的矛盾。在这些矛盾中，以下三类是常见和典型的。
　　 1)多个上下文服务竞争同一资源的矛盾。服务的资源需求超过可用资源总量时，将有一部分服务不能按时按量完成；被竞争的资源通常是计算时间。
　　 2)多种上下文质量属性对资源使用的矛盾需求。为保持上下文的新鲜度，需要服务执行时间足够短；为加强某些质量属性，又需要执行时间尽量长。
　　 3)隐私保护需求与上下文质量需求的矛盾。出于降低隐私泄露风险的目的，需要降低上下文质量，这不仅影响上下文可用性，在一些应用领域还会增加后续上下文处理的资源消耗。
　　 本文针对上述三类典型的矛盾，分别选取具体应用背景下的问题实例，明确其中需要满足的上下文质量指标，通过构造相应的服务调度方案，实现了对质量指标的控制(以及优化)。
　　 1)在多个服务竞争同一资源的矛盾方面
　　 选取一阶谓词表达的上下文信息的逻辑推理为应用背景，考察了大量上下文逻辑推理在有限资源上执行时，如何尽力保证上下文信息时效性(新鲜度)的问题。设计了一个软实时的一阶谓词逻辑推理器RTCR(Real-Time Context Reasoner)，用于推理具有时效性的上下文。RTCR将逻辑推理过程分解为每个(需要推理的)高级上下文对应一个独立推理任务的形式，使用EDF(Earliest Deadline First)规则进行调度。同时还对RTCR中的高级上下文求值算法提出“赋值重用”和“赋值参考”两个改进方法，减少重复的推理计算。在模拟实验中，RTCR在推理任务来过载的情况下能够保证全部推理按时完成。实验也证实改进算法有效缩短了推理的平均执行时间。
　　 2)在多种上下文质量属性对资源使用的矛盾需求方面
　　 选取增量型上下文服务作为应用场景，研究了该类服务如何在保证上下文新鲜度的前提下，优化服务增量为用户提供的使用价值的问题。针对运行多项增量型上下文服务的系统，提出将每项服务任务分为必须完成的基本段和提供增量的延伸段，通过分析基本段的可调度性和延伸段价值(量化的用户体验)产出随时间变化的趋势，分别设计了针对两段任务的多个调度算法，在保证基本段按时完成的同时，优化延伸段提供的总价值。通过模拟实验验证了各个调度算法的有效性，比较了它们的性能，总结了各自适用的条件。
　　 3)在隐私保护需求与上下文质量需求的矛盾方面
　　 选取基于位置的服务(Location Based Service，LBS)中用于隐私保护的K-匿名服务为研究对象，分析了此类服务如何控制位置匿名引起的额外资源消耗，同时优化隐私保护强度的问题。提出以匿名结果集势作为度量匿名LBS服务资源消耗的QoS指标，从理论上分析了它与匿名度K的估算函数关系，并据此构造了相应的匿名度K的调节算法，间接地控制LBS资源消耗。模拟试验的结果与上述理论函数关系吻合得很好，并且证明所提出的匿名度K调节算法能够将匿名结果集势约束在给定值附近，实现了相应的QoS指标。