ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, Vol.21, No.8, August 2010, pp.1920 1935 www.1mpi.com doi: 10.3724/SP.J.1001.2010.03710 Tel/Fax: +86-10-62562563

© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

无线传感器网络上的极值区域查询处理

熊蜀光1+, 李建中1, 陈 雷2, 王新兵3

1

2

3 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) (香港科技大学 计算机科学系,香港) (上海交通大学 电气工程学院,上海 200240)

Querying Peak Regions in Wireless Sensor Networks

XIONG Shu-Guang1+, LI Jian-Zhong1, CHEN Lei2, WANG Xin-Bing3

1

2

3(Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) (Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, China) (Department of Electronic Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

+ Corresponding author: E-mail: n2xiong@gmail.com, www.1mpi.com

Xiong SG, Li JZ, Chen L, Wang XB. Querying peak regions in wireless sensor networks. Journal of Software,

2010,21(8):1920 1935. www.1mpi.com

Abstract: This paper proposes a query in wireless sensor networks: Peak Region Query (PRQ). Given the shape

and size of the query region, i.e., a disk region with radius R, peak region query finds out a region with this shape in

the network field, in which the aggregation value of the data of the sensors can be maximized. This paper first gives

the definition of PRQ, and then proposes a centralized algorithm for the problem. Because the sensors have limited

energy, a distributed approach EXQ (an algorithm for extreme value query processing) is proposed, which not only

reduces the energy cost but also balances the workload of the sensors, so as to prolong the lifetime of the network.

The basic idea is to divide the network field into overlapped sub-regions, compute a local result for each sub-region

and aggregate these results to obtain the query answer. The paper compares the energy efficiency and load balance

between EXQ and the centralized approach analytically and experimentally.

Key words: wireless sensor network; query processing; energy efficiency; extreme value; distributed algorithm

摘 要: 提出了无线传感器网络上的一种查询——极值区域查询(peak region query,简称PRQ),即用户指定查询区

域的大小和形状,例如半径为R的圆形区域,然后需要查询传感器网络中的某个区域,使得区域内传感器节点数据的

某种聚集值最大.定义了极值区域查询的概念,并提出一种集中式算法以求解查询结果.由于传感器节点的能量有

限,为了降低查询处理过程中的能耗,提出了分布式算法EXQ(an algorithm for extreme value query processing).与集

中式算法相比,EXQ不但显著降低了能耗,而且使得每个传感器的能耗更加平均,从而延长了网络的使用寿命.EXQ

的基本思想是,将整个网络划分为若干相互重叠的子区域,对每个子区域通过本地数据聚集得到一个本地结果,然后

对这些结果再进行全局数据聚集从而得到查询结果.从理论和实验两方面分析和比较了集中式算法和EXQ的能耗

Supported by the National Natural Science Foundation of China under Grant No.60533110 (国家自然科学基金); the National Basic

Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973))

Received 2008-09-26; Revised 2009-01-14, 2009-05-05; Accepted 2009-07-23