【作者】 林欣；

【导师】 李善平；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2008， 博士

【摘要】 普适计算的目标是使得人们可以随时随地访问信息,并实现计算的不可见性。智能空间是普适计算在局部物理空间中的体现。而上下文感知计算在智能空间中起着举足轻重的作用,它体现了智能空间中智能性的特征。随着普适计算技术的深入挖掘与推广,智能空间的研究与应用也将从原来的单智能空间阶段逐步扩展到跨智能空间阶段,这种转变符合普适计算中“普”的要求,即无论用户处在哪个智能空间中,都可以充分享受到计算带来的服务。在跨智能空间研究阶段,上下文感知的研究仍然十分关键。然而,对于跨智能空间的场景,上下文共享又面临着多项理论与技术上的困难,如,上下文语义匹配问题、隐私性问题和时效性问题等。本文正是基于以上背景,开展对跨智能空间场景下上下文共享的隐私性问题和时效性问题的研究工作,具体研究内容和创新点表现在以下几个方面:(1)为了更好的开展跨智能空间上下文共享的研究,首先对普适计算中智能空间、跨智能空间和上下文感知的研究现状进行梳理,在此基础上提出了一个跨智能空间上下文共享的中间架构模型,并对其中遇到的隐私性问题和时效性问题做概括性探讨。(2)跨智能空间上下文隐私性研究。选取最典型也是应用最广的一种上下文——位置信息,作为研究对象,着重研究在用户所在空间和上下文消费者不可信任的场景下,保护用户位置信息的方法。本文发现基于位置的服务(LBS)中对查询隐私保护的两大类k匿名算法(clique cloaking和non-clique cloaking)只是针对单快照查询做匿名保护,无法保护连续查询的匿名性。因此提出一种连续查询模型,该模型融合了连续查询时间间隔模型和连续性模型,并基于该连续查询模型对两类LBS中的k匿名算法分别提出了一种连续查询攻击算法。本文发现在k匿名中普遍使用的以匿名集的势作为匿名集(即k)的度量方式并不适用于连续查询,提出了一种基于熵理论的匿名性度量方式AD,实验结果证明在连续查询中,AD比k能更好的反应查询的匿名性。(3)跨智能空间上下文传播的时效性研究,提出了一种面向推理的上下文缓存置换算法CORA,利用缓存技术来降低跨智能空间中由于上下文的数量大、距离远,所造成的上下文传播的开销。CORA采用状态空间对低级上下文到高级上下文的推理进行建模,对各种上下文推理方法具有普遍适用性。在此模型基础上,CORA计算出低级上下文的访问概率和预计失效时间,获得数据的缓存价值,作为上下文缓存置换的依据,以提高缓存的命中率。实验证实,针对普适计算环境上下文数据更新率高的特点,CORA相对传统的缓存置换算法能达到较高的命中率。(4)跨智能空间上下文推理的时效性研究,针对上下文推理结果在一段时间内仍然保持“新鲜”的特点,提出推理结果重复利用效率及其计算公式。在此基础上提出一种新鲜度敏感的上下文推理实时调度算法FRSA,以推理结果重复利用效率作为判断依据结合任务的deadline进行调度,其目标是在推理器负载较重时达到较高吞吐量。本文还提出一种实时调度的启发式规则,使FRSA避免基于值函数调度复杂度过高的缺陷。实验表明,在推理器负载重时,FRSA的系统吞吐量比经典调度算法(SJF、EDF、LSF和FCFS)高出10%-30%。更多还原

【Abstract】 Pervasive Computing enables access to information anywhere,anytime,and makes the computing disappear.A smart space is a local Pervasive Computing environment,in which context-aware computing plays an important role in bringing intelligent interaction to users.With the development and spread of Pervasive Computing technology,research and application of smart space has extended from individual-smart-space stage to inter-smart-space stage.This extension demonstrates "pervasiveness" of Pervasive Computing,i.e.people can enjoy computing services in any smart spaces. Context-aware computing is still important in the inter-smart -space stage.However, in this stage,context sharing faces several theoretic and technical difficulties,such as semantic translation of context between smart spaces,inter-smart-space privacy protection and timely provision of massive contexts.In this dissertation,the author’s researches focus on privacy protection and timely context processing in inter-smart-space context sharing scenarios.The specific issues and contributions include:(1) Firstly,it studies the state of the arts on "smart space","inter-smart space" and "context-aware computing",and proposed a context-sharing infrastructure in the inter-smart-space scenarios.Privacy and timeliness problems are briefly discussed with respect to this infrastructure.(2) Research on privacy protection in the inter-smart-space scenarios.Using location context,a typical and most widely used context,as the research object,it focuses on the users’ location privacy protection in untrusted smart spaces.The two classical k-anonymity algorithm in Location-Based Service(LBS),i.e.,Clique Cloaking and Non-Clique Cloaking,provide good privacy protection only for snapshot queries but not for continuous ones.A continuous query-issuing model is proposed,which incorporates a query issuing interval model and a consecutive queries relationship model.Under this model,an attacking algorithm is devised against the k-anonymity algorithm.It is arguedthat the cardinality of anonymity-set is not a good anonymity measurement under such attacking and an entropy-based anonymity measurement AD is proposed.Experiments demonstrate that the attacking algorithms have high success rate in identifying query senders when the consecutive queries have strong relationship,and that AD is better anonymity measurement than the cardinality of anonymity-set.(3) Research on the timeliness of context dissemination in the inter-smart-space scenarios.Caching is an effective way to reduce context access overhead and improve application availability when disconnections occur.The reasoning-oriented COntext cache Replacement Algorithm(CORA) is proposed in this dissertation,which adopts context state space as a general model for diverse context reasoning methods.And based on this model,it computes the estimated access probability and invalidation time of low-level contexts to get their caching values for replacement.Simulations demonstrate that CORA gets higher hit rate than conventional replacement algorithm for high data update rate(versus access rate) in pervasive computing scenarios.(4) Research on the timeliness of context reasoning in the inter-smart-space scenarios.Considering the fact that reasoning results remain fresh within a period of time,it introduces the concept of reasoning result reuse efficiency and its computation method.Then a Freshness-aware Real-time Scheduling Algorithm(FRSA) is proposed to promote the system throughput when the reasoner is overloaded,which schedules reasoning jobs according to their result reuse efficiencies and deadlines.A heuristic algorithm of real-time scheduling is also proposed to reduce the computing complexity of value function-based real-time scheduling.The simulation demonstrates that when the reasoner is heavily overloaded,the throughput of FRSA is 10%to 30%better than those of classic scheduling algorithms,i.e.,SJF,EDF,LSF and FCFS.更多还原