1160 计 算 机 学报 2011年 格被赋予一个标识符.移动对象所在的单元格的标 矩形框（左下角坐标(100,150），右上角坐标(120， 识符值被B+-tree进行索引.当处理范围查询时，需 180)内的移动对象感兴趣.因此，这个事件不会发 要通过移动对象的速度和相对时间对范围进行扩 送到订阅者， 展.Jensen等人[a)提出了支持更精确的范围查询的 基于内容的模型比较简单，但是无法记录发布 扩展算法.Yiu等人a]提出了B-tree,将一个二维 者或者订阅者的状态.例如，假设某用户（订阅者）不 的移动对象映射到四维的对偶空间进行索引.Chen 愿一天之内接连看两场电影，则最好不要在一天内 等人[3]针对移动对象经常在时空范围内发生变化 多次向他发送电影放映通知.由于基于内容的模型 的特点，提出了一种可自适应调节的STB-tree索 并不记录历史事件，无法满足这个需求，因此可以应 结构」 用基于主题空间的模型. 此外，STRIPESCs)是一个对位置和速度进行索 4.2基于主题空间的模型 引的对偶索引，它将在二维空间移动的移动对象映 基于主题空间的模型的核心概念是主题空间. 射到四维的对偶空间，并对四维空间进行PR Quad 一个主题空间实际上是一个多维空间，空间中的每 tree)索引.这样的结构提高了更新效率，但是却对 个维度分别被定义为一个元组d={name,type}, 查询效率有所影响.针对不同的当前/将来位置索引 其中ame是维度的唯一标识符，type表示数据类 技术，Chen等人[a]提出了一个测试基准，并对主要 型.例如，关于位置的主题空间可以被描述为 的当前/将来位置索引方法的特性进行了详细的比较. {(x,double),(y,double)}.此外，兴趣区域(interest region)表示订阅者感兴趣的一个子域，在某个主题 4 LBS中间件模型 空间中；对象区域(object region)表示一个对象的状 态或者属性.订阅者的订阅请求指定一组兴趣区域 中间件技术广泛地用于移动计算环境之中. 和一个过滤函数，以查看对象区域是否符合订阅标 LBS系统将LBS中间件作为服务处理引擎与终端用 准；发布者的发布准则指定了一组对象区域和一个 户之间的软件载体，隐藏了具体技术细节，便于向客 过滤函数，以查看兴趣区域是否与本次发布匹配.可 户端提供服务.主要的LBS中间件模型有三种，包括 基于内容的模型(content-based model)、基于主题 以通过订阅请求和发布准则来判定是否匹配0 在基于主题空间的模型中，信息在发布之后仍 空间的模型(subject space--based model)和元组空 旧会保留在系统之中，而不是直接被移除，因此该模 间模型(tuple space model),前两个模型又可被归 为发布/订阅模型(publish,/subscribe model).发布/ 型支持有状态的发布/订阅.此外，也有助于实现对 订阅模型是移动计算中应用最为广泛的中间件模型 称的发布/订阅系统.换句话说，仅当发布准则与订 之一.该模型中有两个角色：发布者和订阅者（也称 阅请求匹配时才会向订阅者发送信息.这个特性能 消费者)，二者之间通过事件交换信息，发布者产生 有效降低信息发布量，避免了冗余信息的传播， 事件，订阅者向发布者发送订阅请求.当特定事件发 4.3元组空间模型 生时，即可将该事件通知订阅者.发布者与订阅者之 元组空间模型最早被用于并行编程领域，以协 间的联系并不紧密，是松耦合的：换言之，当订阅者 调并发执行的任务，一个元组是一个包含多项值的 暂时无法工作时，发布者仍可发布事件4]」 矢量，元组空间是一个包含许多元组的集合.多个任 4.1基于内容的模型 务共享一个元组空间，可以通过改变元组空间中的 在本模型中，一个事件被描述为一组（属性，值） 各个元组值（或插入新元组）来实现任务间通信.因 对子，而订阅请求则被描述为一个事件相关的谓词. 此，一般情况下任务间通信是松耦合、匿名化的.如 对于任一事件，检查所有订阅请求的谓词：当谓词为 果想实现同步化通信的目的，则在任务向元组空间发 真时，则将该事件发布给订阅者 送信息之后，必须等待目标任务产生响应元组们 例如，假设某个LBS系统中某个移动对象产生 一般来说，元组空间模型需要支持3个原子 的事件为{(id,"救护车")，(location,(100,200))}, 操作。 表明某一辆救护车的当前坐标是(100,200).订阅者 rite(t):向元组空间插入一个元组t; 的请求是：(location,(x>100)and(x<120)and extract(p):从元组空间中取出符合谓词p的 (y>150)and(y<180)),表示订阅者对于空间上 元组：格被赋予一个标识符．移动对象所在的单元格的标 识符值被Ｂ＋ｔｒｅｅ进行索引．当处理范围查询时，需 要通过移动对象的速度和相对时间对范围进行扩 展．Ｊｅｎｓｅｎ等人［３４］提出了支持更精确的范围查询的 扩展算法．Ｙｉｕ等人［３５］提出了Ｂｄｕａｌｔｒｅｅ，将一个二维 的移动对象映射到四维的对偶空间进行索引．Ｃｈｅｎ 等人［３６］针对移动对象经常在时空范围内发生变化 的特点，提出了一种可自适应调节的ＳＴ２Ｂｔｒｅｅ索 引结构．此外，ＳＴＲＩＰＥＳ［３７］是一个对位置和速度进行索 引的对偶索引，它将在二维空间移动的移动对象映 射到四维的对偶空间，并对四维空间进行ＰＲＱｕａｄ ｔｒｅｅ［１７］索引．这样的结构提高了更新效率，但是却对 查询效率有所影响．针对不同的当前／将来位置索引 技术，Ｃｈｅｎ等人［３８］提出了一个测试基准，并对主要 的当前／将来位置索引方法的特性进行了详细的比较． ４犔犅犛中间件模型 中间件技术广泛地用于移动计算环境之中． ＬＢＳ系统将ＬＢＳ中间件作为服务处理引擎与终端用 户之间的软件载体，隐藏了具体技术细节，便于向客 户端提供服务．主要的ＬＢＳ中间件模型有三种，包括 基于内容的模型（ｃｏｎｔｅｎｔｂａｓｅｄｍｏｄｅｌ）、基于主题 空间的模型（ｓｕｂｊｅｃｔｓｐａｃｅｂａｓｅｄｍｏｄｅｌ）和元组空 间模型（ｔｕｐｌｅｓｐａｃｅｍｏｄｅｌ）．前两个模型又可被归 为发布／订阅模型（ｐｕｂｌｉｓｈ／ｓｕｂｓｃｒｉｂｅｍｏｄｅｌ）．发布／ 订阅模型是移动计算中应用最为广泛的中间件模型 之一．该模型中有两个角色：发布者和订阅者（也称 消费者），二者之间通过事件交换信息．发布者产生 事件，订阅者向发布者发送订阅请求．当特定事件发 生时，即可将该事件通知订阅者．发布者与订阅者之 间的联系并不紧密，是松耦合的；换言之，当订阅者 暂时无法工作时，发布者仍可发布事件［４，３９］． ４１基于内容的模型 在本模型中，一个事件被描述为一组（属性，值） 对子，而订阅请求则被描述为一个事件相关的谓词． 对于任一事件，检查所有订阅请求的谓词；当谓词为 真时，则将该事件发布给订阅者［４］． 例如，假设某个ＬＢＳ系统中某个移动对象产生 的事件为｛（犻犱，＂救护车＂），（犾狅犮犪狋犻狅狀，（１００，２００））｝， 表明某一辆救护车的当前坐标是（１００，２００）．订阅者 的请求是：（犾狅犮犪狋犻狅狀，（狓＞１００）ａｎｄ（狓＜１２０）ａｎｄ （狔＞１５０）ａｎｄ（狔＜１８０）），表示订阅者对于空间上 矩形框（左下角坐标（１００，１５０），右上角坐标（１２０， １８０））内的移动对象感兴趣．因此，这个事件不会发 送到订阅者． 基于内容的模型比较简单，但是无法记录发布 者或者订阅者的状态．例如，假设某用户（订阅者）不 愿一天之内接连看两场电影，则最好不要在一天内 多次向他发送电影放映通知．由于基于内容的模型 并不记录历史事件，无法满足这个需求，因此可以应 用基于主题空间的模型． ４２基于主题空间的模型 基于主题空间的模型的核心概念是主题空间． 一个主题空间实际上是一个多维空间，空间中的每 个维度分别被定义为一个元组犱＝｛狀犪犿犲，狋狔狆犲｝， 其中狀犪犿犲是维度的唯一标识符，狋狔狆犲表示数据类 型．例如，关于位置的主题空间可以被描述为 ｛（狓，犱狅狌犫犾犲），（狔，犱狅狌犫犾犲）｝．此外，兴趣区域（ｉｎｔｅｒｅｓｔ ｒｅｇｉｏｎ）表示订阅者感兴趣的一个子域，在某个主题 空间中；对象区域（ｏｂｊｅｃｔｒｅｇｉｏｎ）表示一个对象的状 态或者属性．订阅者的订阅请求指定一组兴趣区域 和一个过滤函数，以查看对象区域是否符合订阅标 准；发布者的发布准则指定了一组对象区域和一个 过滤函数，以查看兴趣区域是否与本次发布匹配．可 以通过订阅请求和发布准则来判定是否匹配［４０］． 在基于主题空间的模型中，信息在发布之后仍 旧会保留在系统之中，而不是直接被移除，因此该模 型支持有状态的发布／订阅．此外，也有助于实现对 称的发布／订阅系统．换句话说，仅当发布准则与订 阅请求匹配时才会向订阅者发送信息．这个特性能 有效降低信息发布量，避免了冗余信息的传播． ４３元组空间模型 元组空间模型最早被用于并行编程领域，以协 调并发执行的任务．一个元组是一个包含多项值的 矢量，元组空间是一个包含许多元组的集合．多个任 务共享一个元组空间，可以通过改变元组空间中的 各个元组值（或插入新元组）来实现任务间通信．因 此，一般情况下任务间通信是松耦合、匿名化的．如 果想实现同步化通信的目的，则在任务向元组空间发 送信息之后，必须等待目标任务产生响应元组［４１］． 一般来说，元组空间模型需要支持３个原子 操作． 狑狉犻狋犲（狋）：向元组空间插入一个元组狋； 犲狓狋狉犪犮狋（狆）：从元组空间中取出符合谓词狆的 元组； １１６０ 计 算 机 学 报 ２０１１年