基于谓词检测方法的上下文感知案例研究

摘要：当前，开发灵活的适应环境变化的上下文感知应用较为复杂在上下文感知应用开发过程中，很多未知情况无法事先被充分考虑到，实际的开发又需要处理很多意外情形，因此有效地表示和处理上下文尤为重要谓词检测作为实现上下文感知的重要方法之一，能够有效对上下文信息进行建模，但在实际应用中对于真实物理设备的支持如何在很大程度上仍然是未知的为了应对以上问题，通过构建一个简单的物理场景，将谓词检测方法应用于真实的机器小车上，支持其在一个既定轨道上完成运行任务在该场景下对原始的上下文环境进行建模，将环境特性逐步规约成特定的快照谓词和序列谓词，并在案例研究中，对规约化的谓词进行检测，将谓词检测应用于真实的机器小车实验上实验分析的结果表明，谓词检测的方法能有效检测小车的上下文特性并成功支撑小车完成既定的行走目标

关键词：上下文感知； 谓词检测； 快照谓词； 序列谓词

中图分类号：TP301 文献标志码：A

0引言

在普适计算中，相关的环境信息被归类为上下文，上下文感知应用正是基于这些相关的上下文信息为用户不断调整自身行为[1-2]无线通信领域技术的进步，各种新型移动和嵌入式设备的出现，不仅使得上下文感知应用的实现越来越重要，也对其发展提出了更大的挑战

谓词检测是实现上下文感知的重要方法之一[1]在实现谓词检测过程中，应用程序使用逻辑谓词的形式描述其对计算环境的感知情况，通过运行时对规约化的谓词进行检测以实现上下文感知已有的基于谓词检测的上下文感知应用研究中，有些侧重于处理含噪声的上下文，通过检测用来描述含噪上下文的逻辑谓词以使应用避免或消除上下文信息中的噪声[2]；有些侧重于处理从分布式资源中获取的异步上下文信息[1，3]

大多数已有工作都着重于理论方面的研究，而谓词检测对于真实场景下的上下文感知应用有着怎样的促进作用在很大程度上还是未知的具体来说，以下几个方面的问题亟待解决：1）在真实的场景中谓词是否易于使用和表示，对上下文进行建模以及对谓词的规约是否易于实现；2）谓词检测方法能否有效应用于实际的上下文感知应用中并满足应用需求；3）需要在真实的物理环境下考察谓词检测方法对于实际物理设备的控制效果如何

基于上述几点，本文使用一辆机器小车来考察基于谓词检测的上下文感知方法的实际作用小车不断地同外部物理环境进行交互，由于环境本身对小车而言是未知的，因而应用上下文感知十分必要本文的主要工作为：

1）在真实的物理环境下实际控制机器小车，将小车的上下文信息建模成谓词的形式，通过对谓词的检测实现上下文感知；

2）将小车运行过程中的环境特性规约成快照谓词，并进一步规约成时序逻辑状态下的序列谓词形式；

3）在机器小车上应用基于谓词检测的上下文感知方法，通过实验分析和比较实际控制小车的效果

1相关工作

在上下文感知计算方面，Dey等[4]明确地定义了上下文感知计算的概念，提出了构建上下文感知应用所需的基本要求大多关于上下文感知方面的工作主要关注于如何构建基于上下文感知的框架、中间件等，并有很多相应的架构被开发出来[5-6]，但缺乏实际的同真实的上下文环境进行有效交互的应用

有些方面的工作侧重于对上下文以及上下文特性建模过程中出现的错误和问题的检测Xu等[7]提出了上下文感知应用中的非一致性检测问题，通过将特性建模成元组的形式，利用元组中元素的比较实现特性检测Sama等[8]使用基于模型的方法来检测上下文感知的应用程序中的错误还有很多工作使用基于规则的方法以帮助检测有关特性Ranganrhan等[7]也是基于一阶谓词逻辑为上下文感知应用提供了基础架构，使用基于规则的方法对上下文进行演绎和推理Sama等[8]在基于模型的方法上也使用了自适应规则来检测相应的特性Schilit[9]通过基于IFTHEN的简单规则描述了在不同上下文上的应用行为，因而应用逻辑较难在不同情况下进行修改

与文献[4-6]中侧重于如何构建中间件方面的研究相比，本文的工作重点关注实际的上下文感知应用实现，尤其是将基于谓词检测的上下文感知方法应用在实际的机器小车场景中，真实地比较和验证相关方法的效果文献[7-8]都关注了如何检测上下文感知应用中的错误和不一致问题，本文在小车的研究案例中也会遇到应对外部物理环境中的错误数据问题，但本文不侧重于专门解决这一类问题，只是将某些初步能检测到的错误同样作为上下文的一部分规约成谓词作为相应的特性约束为了增强应用的可复用性，与文献[9]中的IFTHEN规则不同，通过基本的谓词形式能够更有效地将不同场景下复杂的上下文表示出来，同时利用基于时序的序列谓词，可以更为准确地描述环境特性

2小车简介

将基于谓词检测的上下文感知方法应用于一辆机器小车（RobotCar）上并通过检测其环境特性支持小车运行小车主要由五个部件组成：ARM板、单片机主板、马达驱动器、4个超声波传感器和1个WiFi模块，如图1所示

图片

ARM板中嵌入了一个简化的Linux系统；单片机主控制板用于连接小车的不同部件并传输各种数据；超声波传感器分别位于小车的4个方向上，它们主要用于收集小车的外部环境信息这些不同的部件都集成在小车的开发板上，通过总线进行数据传输

小车自身的运行逻辑为：嵌入式Linux系统中的可执行程序通过与小车系统各个部分的交互，将指令传达给控制单元，驱动小车完成相应动作程序通过总线向控制单元发送读取数据的指令使小车获取超声波传感器收集的环境信息，然后总线将从传感器读到的数据传送给控制单元处理程序进行分析和处理由于总线是串行的，即一次读取命令只能从一个传感器读到数据，因此要获取小车周围全部4个方向的环境信息时，就必须依次读取每个方位上对应传感器的值一旦程序检测到环境特性改变，小车就需要相应地判断是否对自身行为进行调整控制单元会根据总线上发来的控制命令利用马达等来控制小车调整

3基于小车的上下文感知案例研究

3.1小车运行场景及分析

在本文的案例研究中，小车需要完成从A点到B点的L型路线行走任务理想情况下的路径为从A点向东直线到达L型拐角处，左转后（假设场景中B点在A点东北方向），再径直向北走向B点虽然从直觉角度考虑实现理想路线行走的任务并不困难，但是实际运行中仍有很多未知的意外情况需要处理，基于以下两点论证小车需借助感知周边的物理环境才能完成行走任务：

1）小车自身无法保证径直走直线首先，履带和马达自身存在一定缺陷；其次，传感器也存在一定程度误差，而且地面并不是完全平整由此，直接通过设定马达驱动的参数控制小车会使其易于偏离预想的直线轨道

2）小车需要实时感知周围环境状态，保证在转角处或遇到障碍物时能相应地转弯或进行对应行为调整

为此，应用上下文感知的方法让小车不断改变自身行为以适应周围环境状态的变化，从而完成既定任务因此需要解决如下问题：1）如何对小车上下文进行建模；2）如何对小车的环境特性进行规约；3）如何检测小车当前的特性

3.2小车的上下文信息建模

为了形式化地描述小车的环境特性，要对有关的上下文进行建模建模和规约用到的相关符号及解释附在表1中说明小车的上下文主要通过超声波传感器获取，然后控制部分依次读取收集的数据进行后续处理传感器分布于小车的4个方向以监测环境控制部分对每个方向的传感器执行一次数据读取操作，4个方向依次读取构成一个读取周期为了规范化表示传感器数据，将收集的数据定义成变量表示，见表1和图2中相关部分所示

收集4个方向的数据可大致描述小车在某个时间点上相关的上下文，即通过一个读取周期获得的传感器数据可构建当前环境下瞬时的小车快照状态进一步将数据建模并规约成对应一个快照状态的快照谓词（snapshot predicate）由于小车状态是随着时间序列不断变化的，因而可以基于时序状态进一步规约成描述一段时间内上下文的序列谓词（sequence predicate）通过对快照谓词和序列谓词的检测可以分别得到某个瞬时状态下的上下文特性和一段时间序列上的状态变化进而让小车自适应地进行调整图3表示小车从收集上下文数据到规约的整个建模过程

当谓词检测方法检测到相应环境特性不能满足时，小车要根据当前状态作出调整对应于小车所做的自适应调整行为，将小车基本动作规范为以下五种：AL（向左大幅度调整）、AR（向右大幅度调整）、AL′（向左微调）、AR′（向右微调）和TL/TR（左转或右转90°）其中TL/TR是在小车遇到墙壁拐角处对应的调整，AL和AR是在小车直线运行时偏移较大的调整，而AL′和AR′是在位置偏移较小状态下的微调

3.3快照谓词的规约与检测

3.3.1快照谓词的规约

从传感器读取的数据为原始的上下文信息要对原始的上下文进行处理以使小车能够“理解”其外部环境传感器设备将感知到的上下文数据信息（如检测到的距离）传送给控制部分，然后对数据进行建模，形式化成相应变量进行存储对应的变量（如xR）可以规约成简单的原子命题（atomic proposition）：如xR

为了更详细地描述快照谓词的规约，将讨论如何去表示并实际地构建谓词上面原子命题通过“与”和“或”的方式组合起来，将小车的上下文环境特性规约成形式化的快照谓词一个快照谓词通过多个原子命题的组合描述了某个状态下的上下文首先，定义如下的原子命题来表示小车运行状态的环境特性：

这些形如aLi的原子命题包含了读取的所有上下文信息，反映了小车周围环境的基本情况如原子命题aL界定了右侧传感器的数据xR小于阈值thresh类似地，小车的其他上下文特性也都被规约成对应的原子命题由此根据上面的原子命题可以将小车某个状态下的快照谓词定义成：

当所有的快照谓词被构建好后，原始物理环境的上下文就建模成功了其中每个快照谓词定义了小车在一个瞬时状态下所满足的约束，如SPAL就把一个瞬时状态下小车所需满足的环境特性形式化地表示出来，通过各原子命题的规约构成对某个特性的约束，再通过对原子命题的复合从而规约得到当前小车的上下文所要满足的环境特性将小车的整个运行过程看成是由瞬时状态所组成的序列集合，这样在将每个状态都规约成一个快照谓词后，小车运行过程的上下文信息就全部规约成了形式化的谓词

3.3.2快照谓词的检测

上一部分已将小车的上下文规约成了快照谓词通过对谓词进行检测确定相应的谓词是否满足约束后即可判断当前的上下文状态若某个谓词满足条件，小车就可以作出对应的调整以适应当前环境状态变化一个快照谓词是由几个原子命题构成，由此检测一个快照谓词就是基于谓词的语义根据原子命题的布尔值来计算谓词的真假根据快照谓词的组成结构可以为每个谓词建立一棵二叉树，其中树的叶节点为原子命题，内部节点为逻辑连接词图4所示即为快照谓词SPAL对应的二叉树形式此时谓词的检测对应于该二叉树的遍历当每一轮从传感器读取数据后，当前上下文状态即被确定下来，状态对应的所有原子命题的布尔值也被确定此时二叉树最低一层所有叶节点的布尔值已经得到，因而为得到快照谓词的真假，自下而上遍历整棵二叉树计算出根节点的布尔值即可

通过对每个快照谓词的检测，可以得到小车在当前状态下的特性，进而小车就能够根据当前状态下对周围上下文环境的检测判断是否需要针对性地对小车进行行为调整3.2节中大致说明了小车调整的5个基本动作，在感知小车的上下文后，例如检测出小车自身形态有所倾斜或小车距离周围障碍物太近，就可以针对特性检测结果让小车进行向右或向左的行为调整，保证其运行能处于一个较稳定的状态中

3.4序列谓词的规约与检测

3.4.1序列谓词的规约

对于小车的运行状态，可以有两种基本的状态分解模式：一种抽象方式同3.3节一致，将上下文状态看成是瞬时状态的序列，从而通过快照谓词的集合来描述小车整个运行过程中的上下文信息；另一种方式考虑到小车是随时间不断运行的，如果在规约的过程中引入时序的信息，将不同瞬时状态之间的变化而不仅仅是单个独立的静止状态作为规约的基础，可以更准确地描述整个小车运行过程中的上下文利用时序上不同状态之间的联系，尤其是相邻状态之间变化的潜在信息有助于更有效地表示小车的上下文环境特性由此可以将小车运行的上下文状态看成是由序列状态所构成，每个序列状态对应着一段时间的上下文状态变化，进而将所描述的序列状态规约成序列谓词

序列状态描述的是时序状态的变化，把整个过程看作是状态变化的集合，原先瞬时状态对应的快照谓词就无法直接用来表达时序的小车上下文这里将反映两个相邻瞬时状态变化的信息作为构成一个序列状态的基础这样，当一个表示状态变化的谓词被抽象成某个单一变量如a表示时，一个序列谓词就可以被描述为诸如aabbc的表达式形式为形式化地表示序列谓词，利用正则表达式来描述一个序列谓词Φ，语法定义如下：

其中：表示空集，ε表示空的字符，而a表示定义的任一反映相邻状态变化基础的谓词通过正则表达式的构建，将一个序列谓词形式化地表示成一串由反映状态变化的单一谓词组成的序列为了构造满足特性规约的表达式，从相邻状态变化的基本谓词开始，定义如下的表达式作为关联相邻状态的基础：

其中：xR表示当前状态小车读取的右侧传感器数据；xR′表示前一个状态记录的小车右侧距离；δ1、δ2描述前后相邻状态之间的距离变化（如图5中δ所示），基于此定义如下谓词：

比如Φ（AL）呈现出aaa的形式表示小车这一时段右侧与墙壁的距离连续处于减小的变化中，即小车的状态在不断偏向墙壁，需要向偏离墙壁的一侧调整小车状态，即向左调整

3.4.2序列谓词的检测

已将小车的上下文环境特性规约成了对应时序状态变化的序列谓词为了检测某个序列谓词是否满足，即需检查相应的正则表达式是否成立为此，引入确定性有限状态自动机（Deterministic Finite Automaton， DFA）来检测该正则表达式是否可以被接受

为了有效检测特性，需将正则表达式转换成对应的DFA我们知道，总会存在一个能接受某个正则表达式的DFA[10]一般而言正则表达式到DFA的转换需两个步骤：1）将正则表达式转换为非确定性有限状态自动机（Nondeterministic Finite Automaton， NFA）；2）将NFA转换为DFA这样通过DFA来检测规约的谓词对应的表达式能否被接受以判断相应的环境特性是否满足

在实际针对某些序列谓词的检测时，由于一些表示瞬时状态的信息仍然对当时环境状态变化有作用，需要在序列谓词的检测中加入快照谓词的检测如对于Φ（AL），检测到序列谓词aaa出现后，表明小车在处于偏向墙壁的过程中，此时向左调整的幅度是进行微调AL还是较大幅度的调整仍需要加入一个快照谓词才可以判断，根据Φ（AL）∧SP来对小车的行为进行调整

4基于小车的案例研究实验

4.1实验描述

在小车上设计了几种运行机制并实现了案例分析中的场景小车在一段L型路段上完成从A点到B点的行走任务，整个路线约几十米

为了同基于谓词检测的方法进行比较，设定了一种相对符合直觉假设的理想化运行机制理想化机制同样需要完成既定路线的运行，并保证不能碰撞到墙壁等障碍物理想化机制的规则是：设定一个相对合理的阈值区间，当检测到小车传感器读取的距离数据超出阈值区间范围，就需要对小车的动作进行相应调整在整个实验过程中，通过理想化机制、基于快照谓词检测的上下文感知以及基于序列谓词的上下文感知方法三种机制在小车上的实际应用来分析和比较基于谓词检测的上下文感知方法的作用

4.2实验配置

在实验过程中，通过记录小车的运行时间和小车运行的路线来反映实验的结果在三种实验机制下，需要确保小车的初始状态是一致的以尽可能排除其他因素对实验结果的影响为便于比较，小车的每个状态都会记录相应的处理时间以及传感器返回的距离数据处理时间反映小车在整个场景的运行过程中为适应环境变化而做的行为调整所花费的时间长短，记录的距离信息能够描述小车在各个时间点上的坐标

在实际的小车实验上，根据第3章案例研究所规约的谓词，将小车在具体的实验场景中有关的上下文信息建模成上述的谓词形式，如3.3.1节中的快照谓词SPAL和3.4.1节中的序列谓词ΦAL，通过对谓词的检测以确认当前小车是否满足谓词所约束的环境特性，从而针对性地进行如AL（小车向左调整）这样的动作调整

4.3实验结果和讨论

4.3.1实验结果

实验是为了研究不同的机制尤其是基于谓词检测的上下文感知方法对于小车运行的影响为便于更加准确地比较不同实验下的效果，对实验过程中记录的小车同墙壁的距离以及运行过程中在每个状态下的处理时间进行了分析通过对数据的初步处理，依据记录的小车距离数据，绘制了三个实验中小车运行的大致路径如图7所示

其中，实线（实验1）表示设定的理想化规则，虚线（实验2）和星型线（实验3）分别表示基于快照谓词和序列谓词的检测方法通过比较曲线的形状，可以很明确地看出小车在不同实验中的运行情况三条曲线都在X轴方向的值逐渐增大接近于0的时候转向左方，这与小车实际运行中在接近转角处左转是一致的三次实验中小车都完成了基本的任务（从起点A运行至终点B）并且没有触碰到墙壁等障碍物观察曲线的形状可以发现实线线条代表的路径更为曲折，折线情况比较明显，表明整体的运行情况不是很好，小车需要不断调整运行状态相对而言，虚线和星型线所表示的路径更加平滑，意味着在谓词检测的机制下，小车的运行状态更为稳定；尤其是星型线，在转弯前后的两段路线都最为接近直线的路径，可见基于序列谓词的检测机制能够较好地感知上下文信息

表2记录了实验的统计数据对小车运行过程中记录的距离数据和时间进行了基本处理，距离平均值是实验中获取的小车与墙壁之间距离的均值，方差是度量运行状态同距离平均值之间的偏离程度根据表2中的数据，实验1中数据的偏离最大，实验3的偏离程度最低，这与图7中小车运行的路线所反映的情况基本一致从运行总时间和单个状态小车所用的处理时间来看，不同机制对应的实验结果差别较小但相对而言，基于谓词检测的上下文感知方法所用的整体时间更短

4.3.2实验分析和讨论

从实验结果来看，小车的实际运行情况表明基于谓词检测的上下文机制更好地保证了小车完成既定目标显然，设定的理想化规则基于直觉假设的相对理想的环境，并没有能够充分利用小车的上下文信息，因此在实际应用到小车的运行过程中时没有很好地支持小车针对环境做出行为调整而谓词检测的机制有效地规约了环境上下文信息，根据环境的具体特性建立合适的规则，尤其是基于序列谓词的上下文感知方法，通过对时序状态下环境变化的检测，能更充分地“理解”上下文信息

5结语

本文研究了基于谓词检测的上下文感知的相关方法，通过总结和分析有关应用的问题和不足，给出一个相关的案例分析，在一个小车的实际场景应用谓词检测的方法，让小车能够通过感知周围上下文信息来自适应地调整自身行为根据具体的实验运行和比较，小车在基于谓词检测的机制下能较好地依据上下文状态变化进行有效调整，并验证了在真实的场景下，对于上下文建模、谓词规约和使用的易用性及有效性

当然，由于小车本身的场景并不复杂，还没有能够验证在复杂的上下文环境下谓词检测对于小车适应环境的作用如何同时，当场景发生变化时，实际规约化的谓词（尤其是快照谓词）有可能需要重新构建，相应的可复用性不强，虽然相比传统的基于IFTHEN的规则，谓词的规约化和相关规则更容易重建和更改，但仍需在将来的工作中对复杂环境下谓词检测的方法作进一步研究

参考文献：

[1]HUANG Y， YANG Y L， CAO J L， et al. Runtime detection of the concurrency property in asynchronous pervasive computing environments [J]. IEEE Transactions on Parallel and Distributed Systems， 2012，23（4）： 744–750.

[2]XU C， CHEUNG S， CHAN W， et al. Partial constraint checking for context consistency in pervasive computing [J]. ACM Transactions on Software Engineering and Methodology， 2010， 19（3）： 1-61.

[3]HUANG Y， MA X X， CAO J N， et al. Concurrent event detection for asynchronous consistency checking of pervasive context [C]// PerCom 2009： Proceedings of the 2009 IEEE International Conference on Pervasive Computing and Communications. Piscataway： IEEE， 2009： 1-9.

[4]DEY A K， ABOWD G D， SALBER D， et al. A conceptual framework and a toolkit for supporting the rapid prototyping of contextaware applications [J]. HumanComputer Interaction Journal， 2001， 16（2）： 97-166.

[5]HENRICKSEN K， INDULSKA J. A software engineering framework for contextaware pervasive computing [C]// PerCom 2004： Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications. Piscataway： IEEE， 2004： 77-86.

[6]RANGANRHAN A， CAMPBELL H R. An infrastructure for contextawareness based on first order logic [J]. Personal Ubiquitous Computing， 2003， 7（6）： 353-364.

[7]XU C， CHEUNG S. Inconsistency detection and resolution for contextaware middleware support [C]// ESEC/FSE13： Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York： ACM， 2005： 336-345.

[8]SAMA M， ROSENBLUM D， WANG Z， et al. Modelbased fault detection in contextaware adaptive applications [C]// Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York： ACM， 2008： 261-271.

[9]SCHILIT W N. A system architecture for contextaware mobile computing [D]. New York： Columbia University， 1995.

[10]HOPCRPT J， MOTWANI R， ULLMAN J. Introduction to automata theory， languages and computation [M]. 2nd ed. New York： Addison Wesley， 2000.