基于簇区间的无线传感器网络区间查询优化的研究与实现
|
摘要
传感器网络是一种以数据为中心的网络,把传感器节点视为数据源,把传感器网络视为数据库,把数据处理作为网络应用的目标。本文主要研究无线传感器网络中如何高效利用传感器节点的有限能量进行数据查询的问题,改进和设计了传感器网络中的区间查询算法。主要的工作包括:
(1)以查询优化为目的,研究了基于分簇的网络拓扑结构,设计了可用于查询优化的数据模型以及查询处理的体系结构。
(2)研究了传感器网络中的区间查询及其查询的处理过程。对现有的一些传感器查询优化算法进行分析,指出相关算法的不足之处,并提出改进意见。
(3)针对大规模传感器网络中的区间查询,提出相应的查询计划和优化模型。设计实现了一种基于簇区间过滤器的区间查询优化算法(SFOA)。该算法可大大减少参与查询的节点数,从而节省其能量。
(4)搭建了仿真环境并编写了大量的仿真程序,对改进的算法进行仿真实现。实验结果的分析比较表明,查询的次数越多,网络规模越大改进的算法优化的效果越好。
Wireless Sensor network is a data-centric network. It considers the sensor nodes as a source of data, regards the sensor network as a database and treats the data processing as an aim of the web application. This paper mainly studies how wireless sensor networks make efficient use of the nodes' limited energy to do data querying, and the main method is that improving and optimizing the query algorithm. The main work includes:
(1) For the purpose of the query optimization, we study the cluster-based network topology. We design a data model used for query optimizing and the architecture for query processing.
(2) We do research on the range query of sensor network and the querying process. We analyze some existing sensor algorithms, then, point out the deficiency of relative algorithms and present some improvements.
(3) For the range query in large-scale sensor networks, this paper presents the query plan and the optimizing model. And we design and implement a range query optimizing algorithm (SFOA) based on cluster-interval-filter. The algorithm can, reduce the number of nodes involved in the query greatly and save the energy of the nodes.
(4) We establish the simulation environment and write a large number of the simulation programs to simulate the improving algorithm. The experiment results show that that the larger the number of queries is and the larger network is, the better the effect of the improving algorithm is.
(1)以查询优化为目的,研究了基于分簇的网络拓扑结构,设计了可用于查询优化的数据模型以及查询处理的体系结构。
(2)研究了传感器网络中的区间查询及其查询的处理过程。对现有的一些传感器查询优化算法进行分析,指出相关算法的不足之处,并提出改进意见。
(3)针对大规模传感器网络中的区间查询,提出相应的查询计划和优化模型。设计实现了一种基于簇区间过滤器的区间查询优化算法(SFOA)。该算法可大大减少参与查询的节点数,从而节省其能量。
(4)搭建了仿真环境并编写了大量的仿真程序,对改进的算法进行仿真实现。实验结果的分析比较表明,查询的次数越多,网络规模越大改进的算法优化的效果越好。
Wireless Sensor network is a data-centric network. It considers the sensor nodes as a source of data, regards the sensor network as a database and treats the data processing as an aim of the web application. This paper mainly studies how wireless sensor networks make efficient use of the nodes' limited energy to do data querying, and the main method is that improving and optimizing the query algorithm. The main work includes:
(1) For the purpose of the query optimization, we study the cluster-based network topology. We design a data model used for query optimizing and the architecture for query processing.
(2) We do research on the range query of sensor network and the querying process. We analyze some existing sensor algorithms, then, point out the deficiency of relative algorithms and present some improvements.
(3) For the range query in large-scale sensor networks, this paper presents the query plan and the optimizing model. And we design and implement a range query optimizing algorithm (SFOA) based on cluster-interval-filter. The algorithm can, reduce the number of nodes involved in the query greatly and save the energy of the nodes.
(4) We establish the simulation environment and write a large number of the simulation programs to simulate the improving algorithm. The experiment results show that that the larger the number of queries is and the larger network is, the better the effect of the improving algorithm is.
引文
[1] Silberstein A S, Braynard R, Ellis C, et a1. A sampling-based approach to optimizing Top-k queries in sensor networks[C]. Proc of the 22nd International conference on Data Engineering. Atlanta: IEEE Computer Society, 2006, 68.
[2] Wu M J, Tang X Y. Monitoring Top-k query in wireless sensor networks[C]. Proc of the 22nd International conference on Data Engineering. Atlanta: IEEE Computer Society, 2006, 143.
[3]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展,软件学报,2003,14(10): 1717-1727.
[4] Chaiporn Jaikaeo. Querying and tasking in sensor networks [J]. Proc. SPIE 2000, 4037: 184-194.
[5] Zhao ZB, Yu G, Li BY, et al. An algorithm for optimizing multidimensional K-NN queries in wireless sensor networks. Journal of Software, 2007, 18(5):1186-1197.
[6] Y Yao and J Gehrke. Query Processing for Sensor Networks. Proc. of the 2003 Conf. on Innovative Data Systems Research, Ansilomar, California, USA, Jan. 2003.
[7] R Sion, M Atallah, and S Prabhakar. Resilient Rights Protection for Sensor Streams. Proceedings of the Thirtieth International conference on Very Large Databases Conference (VLDB), 2004, 732-743.
[8] Chu D, Deshpande A, Hellerstein JM, and et al. Approximate data collection in sensor networks using probabilistic models. Proc. of the 2006 International conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[9] Jeffrey Considine, Feifei Li, George Kollios, et al. Approximate Aggregation Techniques for Sensor Databases. Proceedings of the 20th International Conference on Data Engineering (ICDE), 2006, 449-461.
[10]S Madden and M J Franklin. Fjording the stream: An architecture for queries over streaming sensor data. Proc. of the 18th ICDE Conference, 2002, 555-566.
[11]A Cerpa, J Elson, D Estrin, et al., Habitat monitoring: Application driver for wireless communications technology. 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, San Jose, Costa Rica, 2001.
[12]A Mainwaring, J Polastre, R Szewczyk, et al., Wireless Sensor Networks for Habitat Monitoring. ACM International Workshop on Wireless Sensor Networks and Applications. (WSNA'02). 2002.
[13]郑相全,无线自组网技术实用教程.北京,清华大学出版社,2004: 1-386.
[14]M Bhardwaj, T Garnett, A Chandrakasan, et al. Upper Bounds on the Lifetime of Sensor Networks. Proceedings of IEEE ICC’01, 2001, 785– 790.
[15]Arisha KA,Youssef MA, Younis MF. Energy-aware TDMA-based MAC for sensor networks. Proc. Of the IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking(IMPACCT), 2002,69-74.
[16]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Hawaii International Conference on System Sciences. Maui:IEEE Computer Society, 2000. 3005-3014.
[17]A Manjeshwar and DP Grawal. TEEN:A routing protocol for enhanced efficiency in wireless sensor networks. 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, 2001, 2009-2015.
[18]Wenli Chen, Nitin Jain, Singh S. ANMP: ad hoc network management protocol. IEEE Journal on Selected Areas in Communications (USA), 1999,17(8): 1506～1531.
[19]Savarese C, Rabaey J. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. Park Y, ed. Proceedings of the USENIX Technical Annual Conference. Monterey: USENIX, 2001.317-328.
[20]Ratnasamy S, Karp B. GHT: A geographic hash table for data-centric storage. In: Reghavendrv CS, ed. Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. New York: ACM Press, 2002. 94-103.
[21]Hong W, Madden S. TinySchema: Creating attributes and commands in TinyOS.http://telegraph.cs.berkeley.edu/tinydb/.
[22]University of California at Berkeley. TinyOS. http://webs.cs.berkeley edu/tos.
[23]Doherty L. Algorithms for position and data recovery in wireless sensor networks [MS. Thesis]. Department of Electronic Engineering and Computer Science, University of California, Berkeley, 2000.
[24]University of California at Los Angeles. SenSorSim. http://nesl.ee.ucla. edu/projects/sensorsim.
[25]University of California at Los Angeles. WINS: Wireless integrated network sensors.http://www.janet.ucla.edu/WINS/biblio.htm.
[26]Mainwaring A, Polastre J, Szewczyk R, et al. Wireless sensor networks for habitat monitoring. Proc. of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002. 88?97.
[27]SMER sensor network advances bioscience discoveries. http://fs.sdsu.edu/kf/ news/view/index.php?id=0021
[28]Cui L, Ju HL, Miao Y, et al. Overview of wireless sensor networks. Journal of Computer Research and Development, 2005, 42(1):163?174.
[29]Crossbow Technology. MPR (mote processor radio board) and MIB (mote interface/programming board) Hardware User’s Manual. 2003, http:// www.xbow.com/Support/Support_pdf_files/MPR-MIB_Series_Users_Manual.pdf.
[30]Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. Carey MJ, Schneider DA, eds. Proc. of the’95 ACM SIGMOD International Conference on Management of Data, San Jose: ACM Press, 1995. 71?79.
[31]Song ZX, Roussopoulos N. K-Nearest neighbor search for moving query point. Jensen CS, Schneider M, Seeger B, Tsotras VJ, eds. Proc. of the 7th International Symp. on Spatial and Temporal Databases. Berlin: Springer-Verlag, 2001. 79?96.
[32]Arya S, Mount D, Netanyahu NS, et al. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM, 1998, 45(6):891?923.
[33]Cui B, Ooi BC, Su J, et al. Contorting high dimensional data for efficient main memory K-NN processing. Proc. of the 2003 ACM SIGMOD InternationalConference on Management of Data. San Diego: ACM Press, 2003, 479?490.
[34] Zhang R, Kalnis P, Ooi BC, Tan KL. Generalized multidimensional data mapping and query processing. ACM Trans. on Database Systems, 2005, 30(3):661?697.
[35]Shi QX, Nickerson BG.Decreasing radius k-nearest neighbor search using mapping-based indexing schemes. 2006. http://www.cs.unb.ca/tech-reports/ reportpage2006.shtml
[36]Babcock B, Olston C. Distributed top-k monitoring. Proc. of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego: ACM Press, 2003. 28?39.
[37]Deshpande A, Guestrin C, Madden S, et al. Model-Driven data acquisition in sensor networks. Proc. of the 2004 International Conference on Very Large Databases. Toronto: Morgan Kaufmann Publishers, 2004. 588?599.
[38]Chu D, Deshpande A, Hellerstein JM, et al. Approximate data collection in sensor networks using probabilistic models. Proc. of the 2006 International Conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[39]Silberstein A, Braynard R, Ellis C, et al. A sampling-based approach to optimizing queries in sensor network. Proc. of the 2006 International Conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[40]Silberstein A, Munagala K, Yang J. Energy-Efficient monitoring of extreme values in sensor networks. Proc. of the 2006 ACM SIGMOD International Conference on Management of Data. Chicago: ACM Press, 2006. 169?180.
[41]崔莉,鞠海玲,苗勇.无线传感器网络研究进展.计算机研究与发展,005,42(1): 163?174.
[42]OMNet++ object-oriented discrete event simulation system. URL reference: http://www.omnetpp.org, 2004.
[43]IEEE std. 802.15.4-2006, wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs), New York, NY:IEEE, 2006.
[44]***.OMNeT++ NEDXML API reference. http://www.omnetpp.org/doc/nedxml-api/ index.html, 2007.
[45]C Intanagonwiwat, R Govindan, D Estrin, et al. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, 2003,11(1):2–16.
[46]IF Akyildiz, W Su, Y Sankarasubramaniam, and et al. Wireless sensor networks: a survey. Computer Networks. 2002, 38(4):393-422.
[47] J Cai and DJ Goodman. General Packet Radio Service in GSM. IEEE Communications Magazine, 1997, 35(10):122-131.
[48] JJ Garcia-Luna-Aceves and S Murthy. A Path-Finding Algorithm for Loop-Free Routing. IEEE/ACM Transactions on Networking, 1997, 5(1):148-160.
[49]WR Heinzelman, J Kulik, and H Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. Proceedings of International Conference on Mobile Computing and Networking, 1999, 174-185.
[50]D Johnson, DA Maltz, and J Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. 2001, 139-172.
[51]CE Perkins, EM Belding-Royer, and SR Das. Ad hoc on-demand distance vector routing protocol. Second IEEE Workshop on Mobile Computing Systems and Applications, 2003, 90-100.
[52]P Stuckmann and O M?oller. Advanced scheduling and admission control techniques for cellular packet radio networks. Proceedings of European Personal Mobile Communications Conference EPMCC 2003, Glasgow, UK, 2003.
[53]“Castalia”simulation model. http://castalia.npc.nicta.com.au/.
[54]MAC simulator. http://www.consensus.tudelft.nl/ software.html.
[2] Wu M J, Tang X Y. Monitoring Top-k query in wireless sensor networks[C]. Proc of the 22nd International conference on Data Engineering. Atlanta: IEEE Computer Society, 2006, 143.
[3]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展,软件学报,2003,14(10): 1717-1727.
[4] Chaiporn Jaikaeo. Querying and tasking in sensor networks [J]. Proc. SPIE 2000, 4037: 184-194.
[5] Zhao ZB, Yu G, Li BY, et al. An algorithm for optimizing multidimensional K-NN queries in wireless sensor networks. Journal of Software, 2007, 18(5):1186-1197.
[6] Y Yao and J Gehrke. Query Processing for Sensor Networks. Proc. of the 2003 Conf. on Innovative Data Systems Research, Ansilomar, California, USA, Jan. 2003.
[7] R Sion, M Atallah, and S Prabhakar. Resilient Rights Protection for Sensor Streams. Proceedings of the Thirtieth International conference on Very Large Databases Conference (VLDB), 2004, 732-743.
[8] Chu D, Deshpande A, Hellerstein JM, and et al. Approximate data collection in sensor networks using probabilistic models. Proc. of the 2006 International conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[9] Jeffrey Considine, Feifei Li, George Kollios, et al. Approximate Aggregation Techniques for Sensor Databases. Proceedings of the 20th International Conference on Data Engineering (ICDE), 2006, 449-461.
[10]S Madden and M J Franklin. Fjording the stream: An architecture for queries over streaming sensor data. Proc. of the 18th ICDE Conference, 2002, 555-566.
[11]A Cerpa, J Elson, D Estrin, et al., Habitat monitoring: Application driver for wireless communications technology. 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, San Jose, Costa Rica, 2001.
[12]A Mainwaring, J Polastre, R Szewczyk, et al., Wireless Sensor Networks for Habitat Monitoring. ACM International Workshop on Wireless Sensor Networks and Applications. (WSNA'02). 2002.
[13]郑相全,无线自组网技术实用教程.北京,清华大学出版社,2004: 1-386.
[14]M Bhardwaj, T Garnett, A Chandrakasan, et al. Upper Bounds on the Lifetime of Sensor Networks. Proceedings of IEEE ICC’01, 2001, 785– 790.
[15]Arisha KA,Youssef MA, Younis MF. Energy-aware TDMA-based MAC for sensor networks. Proc. Of the IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking(IMPACCT), 2002,69-74.
[16]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Hawaii International Conference on System Sciences. Maui:IEEE Computer Society, 2000. 3005-3014.
[17]A Manjeshwar and DP Grawal. TEEN:A routing protocol for enhanced efficiency in wireless sensor networks. 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, 2001, 2009-2015.
[18]Wenli Chen, Nitin Jain, Singh S. ANMP: ad hoc network management protocol. IEEE Journal on Selected Areas in Communications (USA), 1999,17(8): 1506～1531.
[19]Savarese C, Rabaey J. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. Park Y, ed. Proceedings of the USENIX Technical Annual Conference. Monterey: USENIX, 2001.317-328.
[20]Ratnasamy S, Karp B. GHT: A geographic hash table for data-centric storage. In: Reghavendrv CS, ed. Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. New York: ACM Press, 2002. 94-103.
[21]Hong W, Madden S. TinySchema: Creating attributes and commands in TinyOS.http://telegraph.cs.berkeley.edu/tinydb/.
[22]University of California at Berkeley. TinyOS. http://webs.cs.berkeley edu/tos.
[23]Doherty L. Algorithms for position and data recovery in wireless sensor networks [MS. Thesis]. Department of Electronic Engineering and Computer Science, University of California, Berkeley, 2000.
[24]University of California at Los Angeles. SenSorSim. http://nesl.ee.ucla. edu/projects/sensorsim.
[25]University of California at Los Angeles. WINS: Wireless integrated network sensors.http://www.janet.ucla.edu/WINS/biblio.htm.
[26]Mainwaring A, Polastre J, Szewczyk R, et al. Wireless sensor networks for habitat monitoring. Proc. of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002. 88?97.
[27]SMER sensor network advances bioscience discoveries. http://fs.sdsu.edu/kf/ news/view/index.php?id=0021
[28]Cui L, Ju HL, Miao Y, et al. Overview of wireless sensor networks. Journal of Computer Research and Development, 2005, 42(1):163?174.
[29]Crossbow Technology. MPR (mote processor radio board) and MIB (mote interface/programming board) Hardware User’s Manual. 2003, http:// www.xbow.com/Support/Support_pdf_files/MPR-MIB_Series_Users_Manual.pdf.
[30]Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. Carey MJ, Schneider DA, eds. Proc. of the’95 ACM SIGMOD International Conference on Management of Data, San Jose: ACM Press, 1995. 71?79.
[31]Song ZX, Roussopoulos N. K-Nearest neighbor search for moving query point. Jensen CS, Schneider M, Seeger B, Tsotras VJ, eds. Proc. of the 7th International Symp. on Spatial and Temporal Databases. Berlin: Springer-Verlag, 2001. 79?96.
[32]Arya S, Mount D, Netanyahu NS, et al. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM, 1998, 45(6):891?923.
[33]Cui B, Ooi BC, Su J, et al. Contorting high dimensional data for efficient main memory K-NN processing. Proc. of the 2003 ACM SIGMOD InternationalConference on Management of Data. San Diego: ACM Press, 2003, 479?490.
[34] Zhang R, Kalnis P, Ooi BC, Tan KL. Generalized multidimensional data mapping and query processing. ACM Trans. on Database Systems, 2005, 30(3):661?697.
[35]Shi QX, Nickerson BG.Decreasing radius k-nearest neighbor search using mapping-based indexing schemes. 2006. http://www.cs.unb.ca/tech-reports/ reportpage2006.shtml
[36]Babcock B, Olston C. Distributed top-k monitoring. Proc. of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego: ACM Press, 2003. 28?39.
[37]Deshpande A, Guestrin C, Madden S, et al. Model-Driven data acquisition in sensor networks. Proc. of the 2004 International Conference on Very Large Databases. Toronto: Morgan Kaufmann Publishers, 2004. 588?599.
[38]Chu D, Deshpande A, Hellerstein JM, et al. Approximate data collection in sensor networks using probabilistic models. Proc. of the 2006 International Conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[39]Silberstein A, Braynard R, Ellis C, et al. A sampling-based approach to optimizing queries in sensor network. Proc. of the 2006 International Conference on Data Engineering. Atlanta: IEEE Computer Society, 2006.
[40]Silberstein A, Munagala K, Yang J. Energy-Efficient monitoring of extreme values in sensor networks. Proc. of the 2006 ACM SIGMOD International Conference on Management of Data. Chicago: ACM Press, 2006. 169?180.
[41]崔莉,鞠海玲,苗勇.无线传感器网络研究进展.计算机研究与发展,005,42(1): 163?174.
[42]OMNet++ object-oriented discrete event simulation system. URL reference: http://www.omnetpp.org, 2004.
[43]IEEE std. 802.15.4-2006, wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs), New York, NY:IEEE, 2006.
[44]***.OMNeT++ NEDXML API reference. http://www.omnetpp.org/doc/nedxml-api/ index.html, 2007.
[45]C Intanagonwiwat, R Govindan, D Estrin, et al. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, 2003,11(1):2–16.
[46]IF Akyildiz, W Su, Y Sankarasubramaniam, and et al. Wireless sensor networks: a survey. Computer Networks. 2002, 38(4):393-422.
[47] J Cai and DJ Goodman. General Packet Radio Service in GSM. IEEE Communications Magazine, 1997, 35(10):122-131.
[48] JJ Garcia-Luna-Aceves and S Murthy. A Path-Finding Algorithm for Loop-Free Routing. IEEE/ACM Transactions on Networking, 1997, 5(1):148-160.
[49]WR Heinzelman, J Kulik, and H Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. Proceedings of International Conference on Mobile Computing and Networking, 1999, 174-185.
[50]D Johnson, DA Maltz, and J Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. 2001, 139-172.
[51]CE Perkins, EM Belding-Royer, and SR Das. Ad hoc on-demand distance vector routing protocol. Second IEEE Workshop on Mobile Computing Systems and Applications, 2003, 90-100.
[52]P Stuckmann and O M?oller. Advanced scheduling and admission control techniques for cellular packet radio networks. Proceedings of European Personal Mobile Communications Conference EPMCC 2003, Glasgow, UK, 2003.
[53]“Castalia”simulation model. http://castalia.npc.nicta.com.au/.
[54]MAC simulator. http://www.consensus.tudelft.nl/ software.html.