无线传感器网络中动态空间聚集查询研究
|
摘要
无线传感器网络(Wireless Sensor Networks,简称WSN)集传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术等技术于一体,协作地进行实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息,这些信息通过无线的方式被发送,并以多跳的网络方式传送到需要这些信息的用户。传感器网络可以使人们在任何时间、地点和任何环境条件下获取大量详实而可靠的信息。因此,这种网络系统可以被广泛地应用于国防军事、国家安全、环境监测、交通管理、医疗卫生、制造业、反恐抗灾等领域。
本文主要探讨如何处理WSN中动态空间窗口聚集查询问题,这种动态性体现在用户节点和传感器节点在网络中具有移动性。现有的静态路由协议和聚集算法不能直接应用,因为维持动态网络的固定框架(树结构,簇头等)可能会导致过多的能耗、消息重载、包丢失和传输延迟。因此本文提出一种新的位置可知和基于拉式的动态窗口聚集查询处理策略。
首先,查询消息从user节点动态路由到窗口区域阶段,采用改进的无状态的隐式地理转发(IGF)协议,在面向目标窗口60度角区域内通过竞争机制推出候选节点来转发查询信息直至目标区域。
其次,为减少消息的冲撞和延迟,在目标窗口内节点散播查询信息和聚集数据阶段,提出了一种高效的基于传感器广播直径的聚集查询(DWAQ)算法:散播查询和聚集数据在目标窗口内沿两个方向并发执行。
最后,考虑到用户节点位置变化,本文使用基于代理和基于预测的方法把聚集结果从查询窗口区域返回给节点user。基于代理方案中,在用户节点所在初始区域中确定一个代理节点,当用户节点迁出该区域前,代理节点监测用户节点所在的位置并在聚集结果到来时把该结果路由给用户节点;基于预测方案中,根据用户节点的运动参数信息来预测用户节点的位置,从而将处理结果重新转发给该节点。
仿真结果表明,随着目标窗口变大,本文提出的DWAQ聚集算法在查询准确性和延迟上有一定的优越性;在返回数据阶段,随着节点动态性加强,本文提出的TP算法较之AS算法具有耗能少、查询延迟小的优点。
Wireless sensor network, which is made by the convergence of sensor technology, embedded compute technology, distributed information processing and communication technology, is a novel technology about real-time monitoring, acquiring and processing information, such information is sent through wireless and multi-hop network transmission to these users in need. Sensor networks will enable people at any time and any place access to large number of detail and reliable information. Therefore, such a network system can be widely used in the military for national defense, national security, environmental monitoring, traffic management, health care, manufacturing, anti-terrorism disaster areas and so on.
In this paper, we investigate how to process spatial aggregation query over dynamic geosensor networks where both the sink node and sensor nodes may move around. The existing static routing protocols and aggregation algorithms are not available directly to this case, because dynamic framework for the maintenance of a fixed network (tree structure, a cluster or leader) may lead to excessive energy consumption, message overloads, packet losses and transmission latency. So we present a novel location aware and pull-based routing aggregation strategies for window query processing in dynamic geosensor networks.
First, routing a query toward the area specified by its query window. We improve the stateless of implicit geographic forwarding (IGF) protocol within the 60-degree sector as following candidates during forwarding the query message to target area, all candidate nodes compete for forward mission.
Secondly, to reducing message collisions and reaction latency after the messages are sent to target area, we present a novel diameter-based window aggregation query (DWAQ) algorithm for query propagation and data aggregation at the same time in the query window.
Finally, considering the location changing of sink node, we present two schemes to forward the result to the sink node: Agent Seek-based (AS) scheme and Tracking Prediction-based (TP) scheme. AS scheme determines the region where the sender originally located, before it moves out, it searches an agent node located in the same original region to monitor and forward result to the sender. TP scheme determines the predicted region where the sink node may be in according to moving parameters, and then forwards the result to the destination, the routing protocol is the same as forwarding query messages.
The simulation results show that, the larger the target window is, the better the performance both the query accuracy and latency of our DWAQ aggregation algorithm presented in this paper is; in the return stage, with the enhanced dynamics, the proposed TP algorithm than AS algorithm has less energy, lower latency and more superior performance.
本文主要探讨如何处理WSN中动态空间窗口聚集查询问题,这种动态性体现在用户节点和传感器节点在网络中具有移动性。现有的静态路由协议和聚集算法不能直接应用,因为维持动态网络的固定框架(树结构,簇头等)可能会导致过多的能耗、消息重载、包丢失和传输延迟。因此本文提出一种新的位置可知和基于拉式的动态窗口聚集查询处理策略。
首先,查询消息从user节点动态路由到窗口区域阶段,采用改进的无状态的隐式地理转发(IGF)协议,在面向目标窗口60度角区域内通过竞争机制推出候选节点来转发查询信息直至目标区域。
其次,为减少消息的冲撞和延迟,在目标窗口内节点散播查询信息和聚集数据阶段,提出了一种高效的基于传感器广播直径的聚集查询(DWAQ)算法:散播查询和聚集数据在目标窗口内沿两个方向并发执行。
最后,考虑到用户节点位置变化,本文使用基于代理和基于预测的方法把聚集结果从查询窗口区域返回给节点user。基于代理方案中,在用户节点所在初始区域中确定一个代理节点,当用户节点迁出该区域前,代理节点监测用户节点所在的位置并在聚集结果到来时把该结果路由给用户节点;基于预测方案中,根据用户节点的运动参数信息来预测用户节点的位置,从而将处理结果重新转发给该节点。
仿真结果表明,随着目标窗口变大,本文提出的DWAQ聚集算法在查询准确性和延迟上有一定的优越性;在返回数据阶段,随着节点动态性加强,本文提出的TP算法较之AS算法具有耗能少、查询延迟小的优点。
Wireless sensor network, which is made by the convergence of sensor technology, embedded compute technology, distributed information processing and communication technology, is a novel technology about real-time monitoring, acquiring and processing information, such information is sent through wireless and multi-hop network transmission to these users in need. Sensor networks will enable people at any time and any place access to large number of detail and reliable information. Therefore, such a network system can be widely used in the military for national defense, national security, environmental monitoring, traffic management, health care, manufacturing, anti-terrorism disaster areas and so on.
In this paper, we investigate how to process spatial aggregation query over dynamic geosensor networks where both the sink node and sensor nodes may move around. The existing static routing protocols and aggregation algorithms are not available directly to this case, because dynamic framework for the maintenance of a fixed network (tree structure, a cluster or leader) may lead to excessive energy consumption, message overloads, packet losses and transmission latency. So we present a novel location aware and pull-based routing aggregation strategies for window query processing in dynamic geosensor networks.
First, routing a query toward the area specified by its query window. We improve the stateless of implicit geographic forwarding (IGF) protocol within the 60-degree sector as following candidates during forwarding the query message to target area, all candidate nodes compete for forward mission.
Secondly, to reducing message collisions and reaction latency after the messages are sent to target area, we present a novel diameter-based window aggregation query (DWAQ) algorithm for query propagation and data aggregation at the same time in the query window.
Finally, considering the location changing of sink node, we present two schemes to forward the result to the sink node: Agent Seek-based (AS) scheme and Tracking Prediction-based (TP) scheme. AS scheme determines the region where the sender originally located, before it moves out, it searches an agent node located in the same original region to monitor and forward result to the sender. TP scheme determines the predicted region where the sink node may be in according to moving parameters, and then forwards the result to the destination, the routing protocol is the same as forwarding query messages.
The simulation results show that, the larger the target window is, the better the performance both the query accuracy and latency of our DWAQ aggregation algorithm presented in this paper is; in the return stage, with the enhanced dynamics, the proposed TP algorithm than AS algorithm has less energy, lower latency and more superior performance.
引文
[1]李建中,李金宝.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,14(10):1717-1727.
[2]任丰源,黄海宁.无线传感器网络.软件学报,2003,14(7):1281-1292.
[3]Rahul C.Shah and Jan M.Rabaey,"Energy Aware Routing for Low Energy Ad Hoc Sensor Networks",IEEE 2002,Volume:1,2002.
[4]C.-K.Toh,"Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoe Networks",IEEE Communications Magazine,Volume:39Issue:6,Jun 2001,Page(s):138-147.
[5]Suresh Singh,Mike Woo and C.S.Raghavendra,"Power-Aware Routing in Mobile Ad Hoe Networks,"in Proc.ACM MobiCom'98,Oct.1998.
[6]Kui Wu and Janelle Harms,"Load-Sensitive Routing for Mobile Ad Hoc Networks,"Computer Communications and Networks,2001.Proceedings.Tenth International Conference on,2001.
[7]Xiaoyan Hong,Gerla M,Hanbiao Wang,ClarL,"Loadbalanced,energy-aware communications for Mars sensor networks,"Aerospace Conference Proceedings,2002.IEEE,Volume:3,2002,Page(s):3-1109-3-1115 vol.3.
[8]Saltenis S,Jensen C S,et al.Indexing the Positions of Continuously Moving Objects.In:Proc.of the SIGMOD,2000.
[9]Tao Y,Papadias D,SunJ.The TPR-Tree:An Optimized Spatio-Temporal Access Method for Predictive Queries.In:VLDB,2003.790-801.
[10]Prabhakar S,Xia Y,KalashnikovD V,etal.Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous Queries on Moving Objects.IEEE Transactions on Computers,2002.
[11]Tao Yufei,Papadias D,Zhai Jian,et al.Venn Sampling:A No2 vel Prediction Technique for Moving Objects.In:Proc.ICDE,2005.
[12]Tao Yufei,Sun Jimeng,Papadias D.Selectivity Estimation for Predictive Spatio-Temporal Queries.In:Proc.ICDE,2003.
[13]Sun Jimeng,Papadias D,Tao yet al.Querying about the Past,the Present,and the Future in Spatio2Temporal Databases.In:VLDB,2004
[14]吴秋云,廖巍,景宁,李军.移动对象数据库预测范围聚集查询技术研究.计算机科学,2007,34(1):83-84.
[15]Sylvia R,Brad K,Scott S,Deborah E,Ramesh G,Li Y,Fang Y.Data-Centric storage in sensor nets with GHT,a geographic hash table.Mobile Networks and Applications,2003,8(4):427-442.
[16]Scott S,Sylvia R,Brad K,Ramesh G,Deborah E.Data-Centric storage in sensomets.ACM SIGCOMM Computer Communication Review,2003,33(1):137-142.
[17]Wensheng Z,Guohong C,Tom LP.Data dissemination with ring-based index for wireless sensor networks.In:Kevin A,Ken C,eds.IEEE Inter Conf.on Network Protocols(ICNP 2003).Washington:IEEE Computer Society,2003.305-314.
[18]Abhishek G,Jens G,John C.Resilient data-centric storage in wireless ad-hoc sensor networks.In:Arkady Z,ed.Proc.of the 4~(th)Inter Conf.on Mobile Data Management(MDM 2003).London:Springer-Verlag,2003.45-62.
[19]Deepak G,Deborah E,John H.Dimensions:Why do we need a new data handling architecture for sensor networks.ACM SIGCOMM Computer Communication Review,2003,33(1):143-148.
[20]Benjamin G,Deborah E,Ramesh G,Sylvia R,Scott S.DIFS:A distributed index for features in sensor networks.In:Erdal C,YaiebZ,Eylem E,eds.Proc.of the 1st IEEE Int'l Workshop on Sensor Network Protocols and Applications Anchorage.Washington:IEEE Computer Society,2003.163-173.
[21]廖巍,景宁,钟志农,陈宏盛.面向移动对象的高效预测范围聚集查询方.计算机研究与发展,2007,44(6):1015-1021.
[22]B.M.Blum,T.He,S.Son,and J.A.Stankovic,IGF:A robust state-free communication protocol for sensor networks.Technical Report CS-2003-11,University of Virginia,(2003).
[23]Tian He,Brian M.Blum,Qing Cao,John A.Robust and timely communication over highly dynamic sensor networks.Real-Time Systems Journal,Special Issue on Real-Time Wireless Sensor Networks,(2007).
[24]Ex.and W.-C.Lee.Window query processing in highly dynamic geo-sensor networks:Issues and solutions.GeoSensor.31-52,(2004).
[25]Hedetniemi S,Liestman A.A survey of gossiping and broadcasting in communication networks.Networks,1988,18(4):319-349.
[26]LindseyS,Raghavendra S.PEGASIS:Power-Efficient gathering in sensor information http://www.cs.wayne.edu/～loren/csc8220/menu.htm.
[27]许力,郑宝玉,吴子文.移动自组网中节能策略的分析与比较.计算机应用研究,2004,21(5):1-4.
[28]Niculescu D,Nath B.Trajectory based forwarding and its applications.In:Proc.of the 9th Annual Int'l Conf.on Mobile Computing and Networking.San Diego: ACM Press, 2003.260-272.
[29] Deborah Estrin et al.Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks.UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023.May 2001.
[30] Hein Zelman W, ChandrakaA, Balakrishnan Energy efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui: IEEE Computer Society, 2000.3005-3014.
[31] Brad Karp and H.T.Kung.Gpsr: Greedy perimeter stateless routing for wireless networks. In Proc.ACM Mobicom, Boston, MA, 2000.
[32] B.M.Blum, T.He, S.Son, and J.A.Stankovic, IGF: A robust state-free communication protocol for sensor networks. Technical Report CS-2003-11, University of Virginia, (2003).
[33] Y.Xu, W.-C.Lee, J.Xu, and .Mitchell.PSGR: Priority based stateless geo-routing in wireless sensor networks. In Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems, ashington, DC, Nov.2005.
[34] Kooi RP.The optimization of queries in relational databases [Ph.D.Thesis].Cleveland: Case Western Reserve University, 1980.
[35] Piatetsky-Shapiro G, Connell C.Accurate estimation of the number of tuples satisfying a condition.SIGMOD Record, 1984, 14(2):256-276.
[36] Gibbons PB,Matias Y,Poosala V.Fast incremental maintenance of approximate histograms.In:Jarke M,Carey MJ,Dittrich KR,Lochovsky FH, Loucopoulos P,Jeusfeld MA,eds.VLDB'97,Proc.of the 23rd Int'l Conf. on Very Large Data Bases. Athens: Morgan Kaufmann, 1997.466-475.
[37] Poosala V,Ioannidis Y,Haas P,She E.Improved histograms for select estimation of range redicates.SIGMOD,1996,25(2):294-305.
[38] Ioannidis Y, Poosala V.Balancing histogram optimality and practicality for query result size estimation. SIGMOD Record, 1995, 24(2):233-244.
[39] Jag dish HV, Koudas N, Muthukrishnan S, Poosala V, Sevcik K, Suel T.Optimal histogram swith quality ShmueliO, Widom, eds.VLDB'98, Proc.of the 24th Int'l Conf.on Very Large Data Bases. New York: Morgan Kaufmann, 1998.275-286.
[40] Guha S, Koudas N, Shim K.Data-Streams and histograms. In: Yannakakis M.Proc.of the 33rd Annual ACM Symp.On Theory of computing.Heraklion: ACM Press, 2001.471-475.
[41] GilbertA,Guha S,Indyk P,Kotidis Y,Muthukrishnan S,Strauss M.Fast,small-space algorithms for approximate histogram maintenance. In: Reif JH, ed.Proc.of the 34th Annual ACM Symp.On Theory of Computing. Montreal: ACM Press, 2002.389-398.
[42] Vitter JS.Random sampling with a reservoir.ACM Trans.on Mathematical Software, 1985, 11(1):37-57.
[43] Gibbons PB, Matias Y.New sampling-based summary statistics for improving approximate query answers.In: Haas LM, Tiwary A, eds.SIGMOD 1998, Proc.of the ACM SIGMOD Int'l Conf.on Management of Data. Seattle: ACM Press, 1998.331-342.
[44] Jawerth B, Sweldens W.An overview of wavelet based multire solutionanalyses.SIAMReview, 1994, 36(3):377-412.
[45] Matias Y, Vitter JS, Wang M. Wavelet-Based histograms for selectivity estimation.In: Haas LM, Tiwary A, eds.SIGMOD 1998, Proc.of the ACM SIGMOD Inter Conf.on Management of Data.Seattle: ACM Press, 1998.448-459.
[46] Matias Y,Vitter JS,Wang M.Dynamic maintenance of wavelet-based histograms.In:Abbadi AE,Brodie ML,Chakravarthy S,Dayal U,Kamel N,SchIageter G, Whang KY,eds.VLDB 2000,Proc.of the 26th Inter Conf.on Very Large Data Bases.Cairo:Morgan Kaufmann,2000.101-110.
[47] Fan L, Cao P, and Almeida J, Broder AZ.Summary cache: A scalable wide-area Web cache sharing protocol.IEEE/ACM Trans.On Networking, 2000,8(3):281-293.
[48] Mullin JK.Optimal semijoins for distributed database systems.IEEE Trans.on Software Engineering, 1990,16(5):558-560.
[49] Alon N, Matias Y, Szegedy M.The space complexity of approximating the frequency moments.In: Miller G, ed.Proc.of the 28th Annual ACM Symp.On the Theory of Computing.Philadelphia: ACM Press, 1996.20-29.
[50] Indyk P.Stable distributions, pseudorandom generators, embeddings and data stream computation.In: Blum A, ed.The 41st Annual Symp.On Foundations of Computer Science, FOCS 2000.Redondo Beach: IEEE Computer Society, 2000.189-197.
[51] Flageolet P, Martin GN.Probabilistic counting algorithms for data base applications. Journal of Computer and Systems Sciences, 1992, 31(2): 182-209.
[52] Ganguly S,Garofalakis M,Rastogi R.Processing set expressions over continuous update streams.In:Halevy AY,Ives ZG, Doan AH,eds.Proc.of the 2003 ACM SIGMOD Int'l Conf.on Management of Data.San Diego:ACM Press,2003.265-276.
[53]Y.Xu,J.Xu,and G.Mitchell.Processing Window Queries in Wireless Sensor Networks,IEEE International Conference on Data Engineering(ICDE'06),Atlanta,GA,April 2006.
[54]李建中,郭龙江,张冬冬等.数据流上的预测聚集查询处理算法.软件学报,2005,16(7):1252-1261.
[2]任丰源,黄海宁.无线传感器网络.软件学报,2003,14(7):1281-1292.
[3]Rahul C.Shah and Jan M.Rabaey,"Energy Aware Routing for Low Energy Ad Hoc Sensor Networks",IEEE 2002,Volume:1,2002.
[4]C.-K.Toh,"Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoe Networks",IEEE Communications Magazine,Volume:39Issue:6,Jun 2001,Page(s):138-147.
[5]Suresh Singh,Mike Woo and C.S.Raghavendra,"Power-Aware Routing in Mobile Ad Hoe Networks,"in Proc.ACM MobiCom'98,Oct.1998.
[6]Kui Wu and Janelle Harms,"Load-Sensitive Routing for Mobile Ad Hoc Networks,"Computer Communications and Networks,2001.Proceedings.Tenth International Conference on,2001.
[7]Xiaoyan Hong,Gerla M,Hanbiao Wang,ClarL,"Loadbalanced,energy-aware communications for Mars sensor networks,"Aerospace Conference Proceedings,2002.IEEE,Volume:3,2002,Page(s):3-1109-3-1115 vol.3.
[8]Saltenis S,Jensen C S,et al.Indexing the Positions of Continuously Moving Objects.In:Proc.of the SIGMOD,2000.
[9]Tao Y,Papadias D,SunJ.The TPR-Tree:An Optimized Spatio-Temporal Access Method for Predictive Queries.In:VLDB,2003.790-801.
[10]Prabhakar S,Xia Y,KalashnikovD V,etal.Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous Queries on Moving Objects.IEEE Transactions on Computers,2002.
[11]Tao Yufei,Papadias D,Zhai Jian,et al.Venn Sampling:A No2 vel Prediction Technique for Moving Objects.In:Proc.ICDE,2005.
[12]Tao Yufei,Sun Jimeng,Papadias D.Selectivity Estimation for Predictive Spatio-Temporal Queries.In:Proc.ICDE,2003.
[13]Sun Jimeng,Papadias D,Tao yet al.Querying about the Past,the Present,and the Future in Spatio2Temporal Databases.In:VLDB,2004
[14]吴秋云,廖巍,景宁,李军.移动对象数据库预测范围聚集查询技术研究.计算机科学,2007,34(1):83-84.
[15]Sylvia R,Brad K,Scott S,Deborah E,Ramesh G,Li Y,Fang Y.Data-Centric storage in sensor nets with GHT,a geographic hash table.Mobile Networks and Applications,2003,8(4):427-442.
[16]Scott S,Sylvia R,Brad K,Ramesh G,Deborah E.Data-Centric storage in sensomets.ACM SIGCOMM Computer Communication Review,2003,33(1):137-142.
[17]Wensheng Z,Guohong C,Tom LP.Data dissemination with ring-based index for wireless sensor networks.In:Kevin A,Ken C,eds.IEEE Inter Conf.on Network Protocols(ICNP 2003).Washington:IEEE Computer Society,2003.305-314.
[18]Abhishek G,Jens G,John C.Resilient data-centric storage in wireless ad-hoc sensor networks.In:Arkady Z,ed.Proc.of the 4~(th)Inter Conf.on Mobile Data Management(MDM 2003).London:Springer-Verlag,2003.45-62.
[19]Deepak G,Deborah E,John H.Dimensions:Why do we need a new data handling architecture for sensor networks.ACM SIGCOMM Computer Communication Review,2003,33(1):143-148.
[20]Benjamin G,Deborah E,Ramesh G,Sylvia R,Scott S.DIFS:A distributed index for features in sensor networks.In:Erdal C,YaiebZ,Eylem E,eds.Proc.of the 1st IEEE Int'l Workshop on Sensor Network Protocols and Applications Anchorage.Washington:IEEE Computer Society,2003.163-173.
[21]廖巍,景宁,钟志农,陈宏盛.面向移动对象的高效预测范围聚集查询方.计算机研究与发展,2007,44(6):1015-1021.
[22]B.M.Blum,T.He,S.Son,and J.A.Stankovic,IGF:A robust state-free communication protocol for sensor networks.Technical Report CS-2003-11,University of Virginia,(2003).
[23]Tian He,Brian M.Blum,Qing Cao,John A.Robust and timely communication over highly dynamic sensor networks.Real-Time Systems Journal,Special Issue on Real-Time Wireless Sensor Networks,(2007).
[24]Ex.and W.-C.Lee.Window query processing in highly dynamic geo-sensor networks:Issues and solutions.GeoSensor.31-52,(2004).
[25]Hedetniemi S,Liestman A.A survey of gossiping and broadcasting in communication networks.Networks,1988,18(4):319-349.
[26]LindseyS,Raghavendra S.PEGASIS:Power-Efficient gathering in sensor information http://www.cs.wayne.edu/～loren/csc8220/menu.htm.
[27]许力,郑宝玉,吴子文.移动自组网中节能策略的分析与比较.计算机应用研究,2004,21(5):1-4.
[28]Niculescu D,Nath B.Trajectory based forwarding and its applications.In:Proc.of the 9th Annual Int'l Conf.on Mobile Computing and Networking.San Diego: ACM Press, 2003.260-272.
[29] Deborah Estrin et al.Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks.UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023.May 2001.
[30] Hein Zelman W, ChandrakaA, Balakrishnan Energy efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui: IEEE Computer Society, 2000.3005-3014.
[31] Brad Karp and H.T.Kung.Gpsr: Greedy perimeter stateless routing for wireless networks. In Proc.ACM Mobicom, Boston, MA, 2000.
[32] B.M.Blum, T.He, S.Son, and J.A.Stankovic, IGF: A robust state-free communication protocol for sensor networks. Technical Report CS-2003-11, University of Virginia, (2003).
[33] Y.Xu, W.-C.Lee, J.Xu, and .Mitchell.PSGR: Priority based stateless geo-routing in wireless sensor networks. In Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems, ashington, DC, Nov.2005.
[34] Kooi RP.The optimization of queries in relational databases [Ph.D.Thesis].Cleveland: Case Western Reserve University, 1980.
[35] Piatetsky-Shapiro G, Connell C.Accurate estimation of the number of tuples satisfying a condition.SIGMOD Record, 1984, 14(2):256-276.
[36] Gibbons PB,Matias Y,Poosala V.Fast incremental maintenance of approximate histograms.In:Jarke M,Carey MJ,Dittrich KR,Lochovsky FH, Loucopoulos P,Jeusfeld MA,eds.VLDB'97,Proc.of the 23rd Int'l Conf. on Very Large Data Bases. Athens: Morgan Kaufmann, 1997.466-475.
[37] Poosala V,Ioannidis Y,Haas P,She E.Improved histograms for select estimation of range redicates.SIGMOD,1996,25(2):294-305.
[38] Ioannidis Y, Poosala V.Balancing histogram optimality and practicality for query result size estimation. SIGMOD Record, 1995, 24(2):233-244.
[39] Jag dish HV, Koudas N, Muthukrishnan S, Poosala V, Sevcik K, Suel T.Optimal histogram swith quality ShmueliO, Widom, eds.VLDB'98, Proc.of the 24th Int'l Conf.on Very Large Data Bases. New York: Morgan Kaufmann, 1998.275-286.
[40] Guha S, Koudas N, Shim K.Data-Streams and histograms. In: Yannakakis M.Proc.of the 33rd Annual ACM Symp.On Theory of computing.Heraklion: ACM Press, 2001.471-475.
[41] GilbertA,Guha S,Indyk P,Kotidis Y,Muthukrishnan S,Strauss M.Fast,small-space algorithms for approximate histogram maintenance. In: Reif JH, ed.Proc.of the 34th Annual ACM Symp.On Theory of Computing. Montreal: ACM Press, 2002.389-398.
[42] Vitter JS.Random sampling with a reservoir.ACM Trans.on Mathematical Software, 1985, 11(1):37-57.
[43] Gibbons PB, Matias Y.New sampling-based summary statistics for improving approximate query answers.In: Haas LM, Tiwary A, eds.SIGMOD 1998, Proc.of the ACM SIGMOD Int'l Conf.on Management of Data. Seattle: ACM Press, 1998.331-342.
[44] Jawerth B, Sweldens W.An overview of wavelet based multire solutionanalyses.SIAMReview, 1994, 36(3):377-412.
[45] Matias Y, Vitter JS, Wang M. Wavelet-Based histograms for selectivity estimation.In: Haas LM, Tiwary A, eds.SIGMOD 1998, Proc.of the ACM SIGMOD Inter Conf.on Management of Data.Seattle: ACM Press, 1998.448-459.
[46] Matias Y,Vitter JS,Wang M.Dynamic maintenance of wavelet-based histograms.In:Abbadi AE,Brodie ML,Chakravarthy S,Dayal U,Kamel N,SchIageter G, Whang KY,eds.VLDB 2000,Proc.of the 26th Inter Conf.on Very Large Data Bases.Cairo:Morgan Kaufmann,2000.101-110.
[47] Fan L, Cao P, and Almeida J, Broder AZ.Summary cache: A scalable wide-area Web cache sharing protocol.IEEE/ACM Trans.On Networking, 2000,8(3):281-293.
[48] Mullin JK.Optimal semijoins for distributed database systems.IEEE Trans.on Software Engineering, 1990,16(5):558-560.
[49] Alon N, Matias Y, Szegedy M.The space complexity of approximating the frequency moments.In: Miller G, ed.Proc.of the 28th Annual ACM Symp.On the Theory of Computing.Philadelphia: ACM Press, 1996.20-29.
[50] Indyk P.Stable distributions, pseudorandom generators, embeddings and data stream computation.In: Blum A, ed.The 41st Annual Symp.On Foundations of Computer Science, FOCS 2000.Redondo Beach: IEEE Computer Society, 2000.189-197.
[51] Flageolet P, Martin GN.Probabilistic counting algorithms for data base applications. Journal of Computer and Systems Sciences, 1992, 31(2): 182-209.
[52] Ganguly S,Garofalakis M,Rastogi R.Processing set expressions over continuous update streams.In:Halevy AY,Ives ZG, Doan AH,eds.Proc.of the 2003 ACM SIGMOD Int'l Conf.on Management of Data.San Diego:ACM Press,2003.265-276.
[53]Y.Xu,J.Xu,and G.Mitchell.Processing Window Queries in Wireless Sensor Networks,IEEE International Conference on Data Engineering(ICDE'06),Atlanta,GA,April 2006.
[54]李建中,郭龙江,张冬冬等.数据流上的预测聚集查询处理算法.软件学报,2005,16(7):1252-1261.