无线传感器网络中Skyline节点连续查询算法  

Continuous Skyline Nodes Query Processing over Wireless Sensor Networks

作　　者：信俊昌[1] 王国仁[2] 

机构地区：[1]医学影像计算教育部重点实验室(东北大学),沈阳110819 [2]东北大学信息科学与工程学院,沈阳110819

出　　处：《计算机学报》2012年第11期2415-2430,共16页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(60933001);国家自然科学基金青年科学基金项目(661100022);国家杰出青年科学基金项目(61025007);中央高校基本科研业务费专项资金(N110404009)资助~~

摘　　要：作为多目标决策的重要手段之一,Skyline节点查询在传感器网络应用中发挥着非常重要的作用.文中深入地分析了Skyline节点查询的性质,提出了基于过滤的Skyline节点连续查询算法(FIlter based Skyline moniToringalgorithm,FIST).FIST算法共包括自底向上、自顶向下和混合3种过滤方式,均通过在传感器节点设置本地或全局过滤器来避免不必要的数据传输,进而节约传感器节点的能量.自底向上过滤方式通过缓存先前Skyline结果作为本地过滤器来避免数据重复传输,而自顶向下过滤则通过设置超立方体作为全局过滤器来避免数据反复更新.由于两者各有利弊,因而提出了混合过滤方式,通过为节点选择合适的过滤器来扬长避短.大量仿真实验的结果表明,FIST算法能有效地减少Skyline节点连续查询过程中传感器节点的通信代价,进而降低传感器网络的能量消耗.As an important operator for multiple criteria decision making, Skyline node query plays a very important role in many sensing applications. In this paper, the properties of Skyline node query are theoretically analyzed, and then a novel approach, called Filter based Skyline monitoring algorithm （FIST）, is proposed to evaluate the continuous Skyline node query in wireless sensor networks. Specifically, three filtering mechanisms, including bottom-up filtering, topclown filtering and hybrid filtering, are introduced. All of them install local or global filters within each sensor to reduce the amount of data transferred among sensor nodes and save the energy consumption as a consequence. The bottom-up filtering mechanism caches the previous Skyline results as the local filter to avoid the unnecessary data transmissions, while the top-down filtering mechanism assigns a hypercube to each sensor node as the global filter to suppress the unnecessa- ry data updates. Since both bottom-up filtering and top-down filtering have their own pros and cons, a hybrid filtering mechanism is proposed to choose the ＂right＂ filter for each sensor node to avoid their disadvantages and fully utilize their advantages. Our extensive simulation studies show that FIST approach can effectively reduce the communication cost among sensor nodes and save the energy consumption during the continuous Skyline node query evaluation in wireless sensor networks.

关 键 词：无线传感器网络 Skyline节点查询 能量有效性 过滤 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]