移动对象分布式连续范围查询处理

### 移动对象分布式连续范围查询处理 #### 1. 引言 在移动对象索引问题上，TPR - Tree及其变体被用于对具有轨迹的移动对象进行索引，但这些方法对连续查询的支持效率很低。有研究评估了移动对象索引的效率，得出使用网格方法进行查询索引性能最佳的结论。此外，还有一些不依赖特定索引处理连续查询的方法，如使用有效性区域、安全区域、安全周期和无操作区域等，这些方法的共同特点是返回答案的有效时间或区域，结果失效时客户端会重新提交查询。 本文工作的独特之处在于解决系统的可扩展性和健壮性问题。通过自适应组织服务器在整个服务空间协同工作，并提出一种能在移动设备上以内存数据结构实现的网格索引。该系统对对象移动无限制，能高效支持大量移动对象的连续范围查询。 #### 2. 系统设计与组件 ##### 2.1 系统基础设施与假设 系统考虑具有充足电力的移动主机，如配备全球定位系统（GPS）以获取连续位置信息的车辆。假设移动主机有一定内存和计算能力来存储查询并处理范围查询操作，文中用“移动对象”指代参与查询处理的移动主机。 基站端设计有两个假设： - 服务器和移动对象通过基于蜂窝的无线网络通信，可采用GeoCast等协议在特定区域内发送消息。 - 带有空间数据库的服务器通过有线互联网基础设施连接，每个服务器能接收任何用户的查询请求并转发给合适的服务器。 在设计中，移动对象用点表示，范围查询用矩形区域表示，挑战在于计算在特定时间哪些对象位于哪些查询区域内。 ##### 2.2 服务器设计 - **服务区域**：利用内容可寻址网络（CAN）的设计，将整个服务区域动态划分为一组子空间，每个子空间由一个服务器控制，称为服务区域。每个服务区域有一个服务区域标识符（SID），由其位置计算得出。服务区域划分采用二进制划分方法，将大的服务区域等分为两个小的子服务区域，对应的SID地址可用二叉树结构表示。每个服务器维护一个包含元组⟨SID, address⟩的路由表，存储相邻服务器的路由信息。使用与CAN相同的路由机制，系统能以O(nlogn)的复杂度为n个服务器分配任何服务区域。 当新查询q提交时，系统通过CAN设计中的M - CAN多播算法将其转发到查询区域覆盖的所有服务器。服务器收到查询后，将其插入查询存储库，更新网格索引，并向关联的移动对象广播消息GridIndexUpdate(GIndex)。当查询q要删除时，服务器从存储库中删除相应条目并更新网格索引。 当新服务器加入系统时，需进行以下步骤分配服务区域： 1. 新服务器找到已在系统中的引导服务器。 2. 引导服务器广播新服务器即将加入的消息，其他服务器回复当前系统负载和服务区域信息。 3. 负载最高的服务器将其服务区域一分为二。 4. 引导服务器通知分区服务器转发与新服务器服务区域重叠的查询。 5. 分区服务器向关联的移动对象广播更新的服务区域信息。 6. 若移动对象当前位置由新服务器控制，则向新服务器注册。 7. 新服务器收到转发的查询后，创建并维护相应的网格索引。 8. 分区服务器的邻居服务器更新路由表。 当服务器离开系统时，要确保其服务区域由剩余服务器接管，离开的服务器将移动对象和查询存储库移交给能与其服务区域合并的邻居服务器。 - **网格索引**：移动对象内存有限，需要一种能帮助其仅在接近查询时从服务器检索查询的紧凑索引结构。本文提出的网格索引满足这些要求。 以往基于网格的连续查询索引旨在通过记录查询分布实现随机数据访问，但在移动环境中对象沿轨迹连续移动，大部分服务区域的查询可被剪枝，无需随机访问。本文的网格索引保留查询分布的差异，可高效用于连续查询处理。 网格索引基于一组单元格，通过统一网格顺序将服务区域划分为网格单元，根据对象坐标可轻松计算其所在单元格。 服务器在其服务区域维护网格索引，每个单元格的网格索引结构由两个列表（right和lower）组成，分别记录与右侧和下方相邻单元格的查询分布变化。例如，在一个服务区域划分为16个网格单元的示例中，不同单元格的网格索引记录了查询的增减情况。 移动对象与服务器关联后，服务器将其服务区域的网格索引转发给移动对象。移动对象可利用本地内存中的网格索引