无线传感器网络中能量高效的Top-k监测算法  

Energy Efficient Top-k Monitoring Algorithm in Wireless Sensor Networks

作　　者：毕冉[1] 李建中[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机研究与发展》2014年第11期2361-2373,共13页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2012CB316200);国家自然科学基金项目(61190115;61033015;60933001);国家自然科学基金国际(地区)合作与交流项目(60831160525);中央高校基本科研业务费专项基金项目(HIT.NSRIF.201180)

摘　　要：传感器节点由于电源能量耗尽的原因经常失效或废弃,因此研究无线传感网的高能效查询处理算法具有重要意义.Top-k监测返回k个最大(或最小)的感知值及相应的位置信息,可以帮助用户检测异常事件并定位发生异常事件的位置,对于用户具有重要的实际意义.已有的Top-k查询处理算法致力于返回精确或近似的查询结果,通信能量开销较高.以最小化网内通信开销的期望为优化目标,提出了基于过滤器的Top-k监测算法.首先,提出了过滤器的健壮性并给出了通信开销模型;其次,根据期望的均值内涵和感知数据的时空相关性,给出了过滤器失败概率的计算公式;最后,以最小化通信开销的期望为优化目标,证明了健壮的过滤器的最优阈值,并提出了基于过滤器的Top-k监测算法(filter based Top-k monitoring algorithm,FTM).理论分析和实验结果验证了该算法的正确性以及低能耗性.Due to the battery energy exhausted, sensor node becomes invalid and gets out of use, hence researching on energy efficiency query processing algorithms plays a significant role in the area of sensor networks. The results returned by the Top-k queries provide k largest （or smallest） sensed values and their locations, which are very useful for detecting abnormal events happened in the monitored region. Existing algorithms focus on returning either exact results or approximate results, which brings about higher communication consumption. To overcome the shortcomings of the existing Top-k queries and improve the energy efficiency, filter based Top-k monitoring algorithm is proposed in this paper, which aims at minimizing the expectation of communication overhead. Firstly, the robustness of filters guaranteeing the correctness and high energy efficiency is proposed, and then the communication overhead model is presented. Based on the essence of expectation and sensed data correlation, the probability of filter failure is derived. Finally, minimizing the expectation of communication overhead as an optimization objective, optimal filter threshold is proved and filter based Top-k monitoring algorithm （FTM） is proposed. Real dataset based experiments are carried out to evaluate the efficiency and effectiveness of the proposed algorithm. The theoretical analysis and performance evaluation demonstrate the accuracy and energy efficiency of the proposed algorithm.

关 键 词：无线传感器网络 最小化通信能量 Top-k监测算法 滤波器 阈值 

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