智能空间中的冲突问题研究
2016-08-05徐本胜
徐本胜 王 洁
(北京工业大学计算机学院 北京 100124)
智能空间中的冲突问题研究
徐本胜王洁
(北京工业大学计算机学院北京 100124)
摘要智能空间和回答集程序的整合解决了智能空间中固定优先关系下的资源冲突问题。然而，智能空间处在一个上下文敏感的、动态的环境中，信息更新以及环境变化都会导致资源分配的顺序重新发生变化，从而产生新的冲突问题。针对该问题，基于回答集程序提出一种动态优先的方法。首先，引入缺省规则并利用缺省决策理论动态决策智能空间中的优先关系；然后，使用回答集程序表达空间中的动态优先关系；最后，求解回答集程序得到冲突问题的解。实验结果表明，该方法可以动态决策空间中的优先关系，有效解决空间中的冲突问题，对空间中的资源实现合理分配。
关键词回答集程序智能空间动态优先缺省规则
0引言
智能空间是一个嵌入了多模态传感器、计算和信息设备的工作空间，可使用户便捷地访问空间中的信息并获取计算机的服务，帮助用户实现高效工作[1]。为了方便空间中的设备和服务之间进行信息和资源共享，智能空间最初使用语义网的方法[2]。
语义网采用RDF(资源描述框架)表达信息并且与网页的结构息息相关，然而语义网的推理能力和隐私性都不够好。因此，相关研究学者设计开发了Smart-M3平台以便更好地实现智能空间。
Smart-M3是智能空间中的一个的交互操作平台，空间中的所有信息和服务都可以在设备之间进行共享和存取。它包含两个部分，分别是SIB(Semantic Information Broke)和KP(Knowledge Processor)[3]。其中，SIB以RDF三元组的形式对空间中的信息进行存储；知识处理操作则由KP完成，通过删除、插入、查询、更新等操作来处理存储在SIB中的信息[4]。智能空间访问协议SSAP(Smart Space Access Protocol)则将SIB和KP进行了连接。
2010年Luukkala.V等人在智能空间中引入了回答集程序设计ASP[5]，并将ASP求解器Smodels和智能空间中的Smart-M3平台进行了整合[6]并在此基础上使用固定优先权的方法解决了空间中的资源分配和冲突问题。然而，现实生活中的优先权并不是完全固定的，它应该随着环境和信息变化而改变。
因此，建立一种随环境和信息更新而能够动态改变空间中优先关系的方法是很有必要的。为了解决这个问题，引入缺省规则[7]的方法并基于缺省决策理论[8]动态决策空间中的优先关系；然后，使用回答集程序表达空间中的这种动态优先关系，最后，求解回答集程序即可得到冲突问题的解。
1ASP与智能空间的整合
回答集程序设计ASP的理论基础是Gelfond和Lifschitz于1988年提出的一般逻辑程序的稳定模型语义。1999年ASP作为一种程序设计框架被提出，其语法上类似传统逻辑编程，语义上是一种非单调逻辑的描述性语义，具有丰富的知识表达和推理能力。ASP解决问题的基本思想是：通过一个非单调逻辑程序描述待求解的问题，根据描述设计一个带有回答集语义的回答集程序，计算回答集程序的回答集就是待求解问题的解决方案。
智能空间中的设备和服务信息是以RDF三元组的形式进行存储的，而ASP是一种基于规则的方法，因此为了整合ASP与智能空间就需要将RDF转化为规则的形式。转换的过程是将RDF的三元组
ASP与智能空间的整合主要是基于以下过程：通过ssls将回答集程序的推理工具Smodels与Smart-M3平台相连接。其中，ssls是一个能够访问Smart-M3操作(删除、插入、查询、更新等)的命令行工具并且可以把存储在SIB中的信息提取出来。利用RDF三元组与二元事实的转换性可以把存储在SIB中的每一条信息都转换成相对应的一条规则，从而得到一个回答集程序。利用Smodels求解回答集程序得到的结果则可以通过KP执行插入、更新、删除等操作，以实现SIB中信息的更新[10]。
ASP具有很强的知识表达和推理能力并支持资源分配和冲突消解，当有多个可能解的情况下可以利用偏好和最优化技术筛选最合适的解。2010年Luukkala.V等人通过Smart-M3与ASP的整合增强了智能空间中的推理能力，使用固定优先权的方法在一定程度上解决了空间中的资源分配和冲突问题。比如，在汽车这个智能空间中，设定交通信息的优先级高于音乐。当交通信息和音乐同时申请使用扬声器时，扬声器在任何环境下都会接受交通信息的申请，并优先分配给交通信息。
但是，智能空间是一个上下文敏感的，动态的环境[11,12]，信息更新和环境变化都会导致资源分配的顺序重新发生改变，引起新的冲突问题。比如，汽车中有一个正处于睡眠状态的婴儿，当收到一条最新的路况交通信息时，为了不打扰婴儿的睡眠，我们期望扬声器能够播放缓慢柔和的音乐而不是路况交通信息。采用Luukkala.V等人提出的固定优先级的方法无法解决这种问题。因此，我们提出另一种解决方法，即动态优先的方法。
2基于ASP解决智能空间中的冲突问题
由于ASP具有丰富的知识表达和推理能力，ASP与智能空间的整合促进了智能空间的相关研究工作。2010年张璟璟等人基于Jini技术并以智能空间中的漫游打印为应用背景，设计了一种有效的智能空间的资源管理解决方案。2012年Janhunen.T等人基于元程序的方法，允许智能空间中的设备发布它的行为规则，并利用元程序的具体化表达将规则信息存储到SIB中，从而实现了对规则信息的共享和存储，增强了智能空间中设备之间的交互能力。2012年赵丽丽等人基于加权逻辑程序来表达智能空间中确定性的信息以增强确定性信息的表达和推理，但是该方法不支持对空间中不确定信息的表达和推理。2014年刘志勇等人通过对智能空间中资源管理的研究构建了一个智能空间资源管理系统并对空间中的资源调度算法进行了研究。
本文为了处理智能空间中信息更新和环境变化后的资源冲突问题，基于ASP提出一种动态优先的方法，首先引入缺省规则并根据环境和信息变化动态决策优先关系，并用ASP表达这种动态优先关系，最后求解该回答集程序即得到冲突问题的解。
2.1智能空间中的动态优先关系表达
智能空间中存在很多的设备服务信息，每个设备实例称为一个capability，每个服务实例称为一个activity。在activity实例和capability实例之间有一个used关系，表示activity申请使用这个capability实例。当capability实例接受该请求，就会在两个实例之间建立一个committed的关系。此外，两个activity实例之间还有一个优先关系priority，比如priority(ActGood,ActBad)表示ActGood和ActBad之间的优先关系并且ActGood的优先级大于ActBad的优先级。对于to_commit来说，就是要选择一个capability-activity对集，并且满足以下三条原则。
(1) 空间中的所有资源在尚未达到它的最大使用量之前都可以被一个新的activity实例申请使用。
(2) 当多个activity实例申请使用同一个capability实例时具有更高优先权的activity实例应该给予优先分配。
(3) 如果没有更高优先权的activity实例申请使用设备，那么已分配的activity实例应保持对此设备的使用关系。
基于以上三条原则可以使用ASP的方法解决固定优先关系下的资源冲突问题，因此需要用规则的形式对以上三个原则进行描述。下面的三条约束规则(1)、(2)、(3)分别对应上面的三条原则。
←{to_commit(Cap,Act):used(Cap,Act)}M-1,
used(Cap,Act1),
not to_commit(Cap,Act1),
max_users(Cap,M)
(1)
←to_commit(Cap,ActBad),
used(Cap,ActBad),
not to_commit(Cap,ActGood),
used(Cap,ActGood),
priority(ActGood,ActBad)
(2)
←to_commit(Cap,ActBad),
not committed(Cap,ActBad),
used(Cap,ActBad),
committed(Cap,ActGood),
not to_commit(Cap,ActGood)
used(Cap,ActGood),
priority(ActGood,ActBad)
(3)
但是，智能空间是一个动态的上下文敏感的环境，空间中的优先关系不可能是完全固定的，当信息发生更新后，使用固定的优先方法会引起新的冲突问题，因此必须动态表示空间中的优先关系。为了表达空间中的动态优先关系引入缺省规则。缺省规则的一般形式为:
e→Aa
其中，e是一阶公式集合，表示已知的信息或知识，A是原子集合，表示所有可选择的决策行为，a是原子，并且a∈A。缺省规则e→Aa的直观含义是：在已知信息e的基础上，对于A中的所有决策，a是最优的决策结果。例如，对于缺省规则：“如果天气预报今天会下雨，那么今天出门要带伞”，可以如下表示：
date(today)∧weather(rain)→Acarry_umbrella
其中A={carry_umbrella,carry_nothing}。
为了对当前环境和信息下的不同activity实例之间的优先关系进行动态决策，引入了缺省决策理论。具体表示如下:
其中：
其中，ε(a,e)是a在已知信息e下的期望效用，w是选定的封闭世界，μ(a,w)表示行为a在w下的效用，P(w|e)是在已知信息e下w成立的条件概率。缺省决策理论的直观含义是，在已知信息e的基础上，A中期望效用最大的行为是最优的决策结果。
根据上述的缺省决策理论有如下原则：对于申请使用同一个设备的多个activity，在当前环境和信息下具有更大期望效用的activity应该被赋予更大的优先级。基于缺省规则可以进行如下表示：
activity(ActGood)∧activity(ActBad)∧
used(ActBad,Cap)∧used(ActBad,Cap)∧
capability(Cap)→Apriority(ActGood,ActBad)
其中：
A={priority(ActGood,ActBad),
priority(ActBad,ActGood)}
此外，我们定义谓词expect_utility(Act,X)表示Act的期望效用为X，因此，可以把上面的缺省规则改写为回答集程序的形式，记为规则(4)。
priority(ActGood,ActBad)←capability(Cap),
used(ActGood,Cap),used(ActBad,Cap),
activity(ActGood),activity(ActBad),
expect_utility(ActGood,X),
expect_utility(ActBad,Y),X>Y
(4)
利用规则(4)，我们就可以根据智能空间中的信息和环境的变化，依据缺省决策理论，通过计算当前环境下的activity实例的期望效用值来动态决策activity实例间的优先关系。
因此，基于(1)、(2)、(3)、(4)四条规则就可以动态决策空间中的优先关系以解决智能空间中的资源冲突问题。
2.2实例
例2：在汽车这个智能空间中存在键盘、扬声器等设备。扬声器可以用来播放路况交通信息和音乐。现在，汽车中有一个处于清醒状态的婴儿，扬声器正在播放一些缓慢柔和的音乐，当收到一条最新的路况交通信息时，用户希望能接收该条信息，因此期望扬声器能优先播放路况交通信息。一段时间后，婴儿慢慢进入睡眠状态，当又收到一条最新的路况交通信息时，为了不打扰到婴儿的睡眠，用户期望扬声器能够继续播放缓慢柔和的音乐而不是路况信息。在此种场景下，需要动态决策Message和Music的优先关系。因此，我们采用2.1节中的方法来解决上述问题。
首先对于该实例，智能空间中存储于SIB中的信息如下：
″rdf:type″(Loudspeaker,″dcs:capability″),
″rdf:type″(Message,″wp1:activity″),
″rdf:type″(Music,″wp1:activity″),
″wp1:used″(Loudspeaker,Message),
″wp1:used″(Loudspeaker,Music)
当婴儿处于清醒状态时，由当前环境下的效用和概率信息可以得到Message的期望效用大于Music的期望效用。因此由2.1节中的规则(4)可以推理得到priority(Message,Musuc)即Message的优先级高于Music。将SIB中的RDF三元组信息转化成规则的形式如下：
(5) activity(Music)←
(6) activity(Message)←
(7) capability(Loudspeaker)←
(8) used(Loudspeaker,Music)←
(9) used(Loudspeaker,Message)←
结合2.1节中的规则(1)-规则(3)可以得到一个回答集程序P，通过回答集推理机Smodels求解程序P，得到回答集A并且to_commit(Loudspeaker,Message)∈A即根据当前的信息和智能空间所处的环境得到的结果是将扬声器分配给Message。
一段时间后，婴儿慢慢进入睡眠状态。根据此时环境下的效用和概率信息可以得到Music期望效用大于Message的期望效用。由2.1节中的规则(4)可以推理得到priority(Music,Message)即当前环境下Music的优先级高于Message。更新程序P，求解P得到新的回答集B并且to_commit(Loudspeaker,Music)∈B即根据当前的信息和智能空间所处的环境得到的结果是扬声器分配给Music。
由上可以看出，通过2.1节中的方法可以根据环境和信息的变化动态决策空间中存在的activity实例间的优先关系，当婴儿清醒时Message的优先权高于Music，当婴儿熟睡时，Music的优先权高于Message。而Luukkala.V等人提出的固定优先方法是固定activity实例间的优先关系，比如固定Message的优先权始终高于Music，那么无论信息和环境发生任何更新和变化，扬声器都会优先播放路况交通信息Message。
固定优先方法只能处理固定优先关系下的资源冲突问题，并且资源一旦分配就不会改变。但是智能空间是一个动态的、上下文敏感的环境，空间中的优先关系和资源分配顺序不可能是固定不变的。当智能空间中的信息和环境发生变化时，固定优先方法已不能适应空间的动态变化。与之相比，我们提出的动态优先方法可以根据信息和环境变化动态决策空间中的优先关系，改变空间中的资源分配顺序，适应智能空间的动态变化，解决信息更新后的资源冲突问题，从而实现对资源的合理分配。
3结语
智能空间中的资源设备众多，固定空间中的优先关系可以在一定程度上解决资源分配时的冲突问题。但是，这无法解决因信息更新和环境变化而产生的冲突问题。本文基于缺省规则和缺省决策理论，提出了一种动态优先的方法，根据智能空间中信息和环境的变化动态决策空间中的优先关系，解决了空间中的这种冲突问题，实现了资源的合理分配。
参考文献
[1] Borkar S.Technology challenges and opportunities for ubiquitous computing[C].Solid State Circuits Conference,IEEE,2012:125-128.
[2] Selvarajah K,Zhao R,Speirs N.Building smart space applications with pervasive computing in embedded systems[J].Journal on Computing,2014,1(4):22-24.
[3] Honkola J,Laine H,Brown R.Smart-M3 information sharing platform[C].ISCC,2010:1041-1046.
[4] Kaustell A,Saleemi M,Rosqvist T,et al.Framework for smart space application development[C]//Proceedings of the International Workshop on Semantic Interoperability,2011.
[5] Luukkala V,Honkola J.Integration of an answer set engine to smart-m3[M].Smart Spaces and Next Generation Wired/Wireless Networking.Springer Berlin Heidelberg,2010:92-101.
[7] Wang J,Ju S E,Liu C N.Agent-oriented probabilistic logic programming[J].Journal of Computer Science and Technology,2006,21(3):412-417.
[8] Horvitz E J.Reasoning about beliefs and actions under computational resource constraints[J].arXiv preprint arXiv,2013,1(3):1304-1325.
[9] Schaub T.Answer set programming[C]//Proceedings of the 12thConference on Formal Methods in Computer-Aided Design.,2012:2-5.
[10] Janhunen T,Luukkala V.Meta programming with answer sets for smart spaces[M].Springer Berlin Heidelberg,2012.
[11] Honkola J,Laine H,Brown R,et al.Cross-domain interoperability:A case study[M].Smart spaces and next generation Wired/Wireless networking.Springer Berlin Heidelberg,2009:22-31.
[12] Aziz R A,Janhunen T,Luukkala V.Distributed deadlock handling for resource allocation in smart spaces[M].Smart Spaces and Next Generation Wired/Wireless Networking.Springer Berlin Heidelberg,2011:87-98.
收稿日期：2015-02-11。徐本胜，硕士生，主研领域：回答集程序设计，不确定推理。王洁，副教授。
中图分类号TP301
文献标识码A
DOI:10.3969/j.issn.1000-386x.2016.07.007
STUDY ON CONFLICT PROBLEM IN SMART SPACE
Xu BenshengWang Jie
(CollegeofComputerScience,BeijingUniversityofTechnology,Beijing100124,China)
AbstractThe integration of answer set programming (ASP) and smart space can solve resource conflict problems in smart space on the condition of fixed priority relation.However,smart space is in a context sensitive and dynamic environment,the updating of information and changing of environment would all cause the alternation in order of resource allocation,and further lead to new resource conflicts.To solve this problem,in this paper we put forward a dynamic priority method based on answer set programming.First,we introduce default rule and use default decision making theory to dynamically decide the priority relation in smart space.Secondly,we employ answer set programming to represent the dynamic priority relations in the space.Finally,we calculate the answer set programming to get the solution of conflict problem.Experimental result shows that this method is able to dynamically decide the priority relation in the space and effectively overcomes the conflict problems in space,and achieves reasonable allocation of resources in the space as well.
KeywordsASPSmart spaceDynamic priorityDefault rule
