Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of

[23]G.Pottie and W.Kaiser.Wireless sensor networks.

Communications of the ACM,43,2002.

[24]S.Shakkottai,R.Srikant,and N.Shroff.Unreliable

sensor grids:Coverage,connectivity and diameter.In Proceedings of INFOCOM(to appear),2003.

[25]S.Slijepcevic and M.Potkonjak.Power efficient

organization of wireless sensor networks.In Proc.of

IEEE Intl.Conf.on Communications(ICC),2001.

[26]J.Wu and H.Li.A dominating-set-based routing

scheme in ad hoc wireless networks.

Telecommunication Systems Journal,3,2001.