东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2011, Vol. 32 ›› Issue (8): 1076-1079+1096.DOI: -

• 论著 • 上一篇    下一篇

基于过滤器的K-NN深度优先查询算法

谢英红;吴成东;张云洲;李孟歆;   

  1. 东北大学信息科学与工程学院;沈阳建筑大学信息与控制工程学院;
  • 收稿日期:2013-06-19 修回日期:2013-06-19 发布日期:2013-04-04
  • 通讯作者: -
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(60874103)

A depth-first K-NN query algorithm based on filters

Xie, Ying-Hong (1); Wu, Cheng-Dong (1); Zhang, Yun-Zhou (1); Li, Meng-Xin (2)   

  1. (1) School of Information Science and Engineering, Northeastern University, Shenyang 110819, China; (2) School of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China
  • Received:2013-06-19 Revised:2013-06-19 Published:2013-04-04
  • Contact: Xie, Y.-H.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

436

摘要： 为减少数据查询的能量消耗,有效延长无线传感器网络的生存时间,提出了一种基于过滤器的K-NN深度优先查询(FKDF)算法.通过为每个节点设置过滤器来确定K-NN查询区间;利用查询节点的邻接表信息,在进行深度优先遍历时生成查询消息;基站分发查询消息,并等待查询节点返回查询结果,从而减少查询的平均跳数.仿真结果表明:与FILA设置过滤器方法和GPSR路由算法相比,FKDF算法节约了查询所需的平均跳数,能够适应网络拓扑结构的动态变化,当K值经常变化时不增加查询开销.

关键词: 无线传感器网络, 过滤器, K-NN, 深度优先, 邻接表

Abstract: To reduce the energy consumption for data query and prolong the lifetime of wireless sensor networks, a depth-first K-NN query algorithm based on filters is proposed(FKDF). In the FKDF algorithm, the K-NN query range is determined by setting filters for each node. As depth first traversal is carried out, the query information is formed by using adjacent list information of the query nodes. Then, a sink node delivers query information and waits for the query nodes sending back query results, thereby decreasing the average hops per query process needed consequently. Simulation results show that FKDF algorithm reduces the average hops per query process needed, compared with the FILA algorithm setting filters and the GPSR routing algorithm, and it can not only adapt to the dynamic network topology structure, but also realize the minimal query cost when the value of K changes constantly.

中图分类号: