摘要: 本文研究移动计算环境下分布式Skyline查询处理问题，考虑如下场景：一个游客来到一海滨城市，他希望预订一个宾馆，于是他通过随身携带的移动设备（智能手机、便携式电脑、个人数字助理等）查询宾馆信息，宾馆信息集合被水平分片后存储在多个通过高速有线网络连接数据库服务器上，移动设备能够通过无线网络与其所在区域的基站(BS)进行通信并透明地访问存储在数据库服务器上的数据。该游客希望查找一个价格低、服务质量好且距离海滨近的宾馆，于是通过移动设备发出如下查询 Select *, From Hotels, Skyline of Price min, Quality of Service max, Distance to beach min 来获得感兴趣的宾馆信息。
上述应用场景中需要移动数据库系统提供分布式Skyline查询处理能力，不同于传统的集中式或分布式Skyline查询，移动计算环境固有的特性：移动性、资源受限性、频繁的断接性等，使得移动计算环境下分布式Skyline查询处理变得更加复杂。
上述问题的一个直观而自然的解决方案包括如下：（1）移动设备所在区域的BS接收到分布式Skyline查询请求后立即将该请求转发到所有数据库服务器(FDSi)；（2）每个FDSi在接收到查询请求后使用一个集中skyline查询算法计算本地局部skyline；（3）每个FDSi负责将本的局部skyline发送到移动设备；（4）移动设备在所有本地局部skyline的联合上再执行一次集中skyline查询算法，得到最终的分布式Skyline。
考虑到移动计算环境下移动设备CPU处理能力、存储空间受限加之无线网络低的网络带宽，可以对上述解决方案做一个简单的改进，即挑选接收skyline查询请求的BS作为协调者，FDSi将本的局部skyline发送到协调者，由协调者来负责最终Skyline计算，并负责将结果发送给移动设备。
上述简单改进后的解决方案仍然存在许多缺陷：首先简单地选择接收skyline查询请求的BS作为协调者导致了额外的带宽消耗，例如，移动设备发出skyline查询请求立即从原来的Cell（假定由BSj负责）移动到一个新的Cell（假定由BSi负责），简单地选定BSj作为协调者会导致最终结果将首先由BSj传送到BSi后再由BSi发送给相应的移动设备，显然这导致了额外的网络带宽消耗；其次，每个FDSi简单地将本的局部skyline发送到协调者也导致了昂贵的网络通信代价，因为本的局部skyline中有许多不属于最终结果集的数据，若在发送前采用一定的过滤策略来消除一些不属于最终结果集的数据将能有效地减低网络通信量；最后，我们发现在连接到相同BS控制器(BSC)上的两个FDSi间的数据传输的网络延迟要小于两接在不同BSC上FDSi间的数据传输延迟，基于这一观察，我们可以设计了有效的处理策略来最小化网络延迟。
本文提出的分布式skyline查询处理方案包括如下五个阶段：(1) 查询shipping阶段；（2） 本地处理阶段；（3）缩减阶段；（4）汇聚阶段；（5）最终处理阶段。对每个阶段我们都进行了精心的设计，以确保最小化网络带宽消耗、网络延迟与查询相应时间。
在将来的工作中，我们将引入位置信息，研究了移动计算环境下位置相关Skyline查询问题，基于我们现有的处理框架，对我们的处理方案进行扩展来解决位置相关Skyline查询问题。