Distributed query processing in flash-based sensor networks

Abstract

Wireless sensor networks are used in a large array of applications to capture, collect, and analyze physical environmental data. Many existing sensor systems instruct sensor nodes to report their measurements to central repositories outside the network, which is expensive in energy cost. Recent technological advances in flash memory have given rise to the development of storage-centric sensor networks, where sensor nodes are equipped with high-capacity flash memory storage such that sensor data can be stored and managed inside the network to reduce expensive communication. This novel architecture calls for new data management techniques to fully exploit distributed in-network data storage. This paper describes some of our research on distributed query processing in such flash-based sensor networks. Of particular interests are the issues that arise in the design of storage management and indexing structures combining sensor system workload and read/write/erase characteristics of flash memory.

References

1. Madden S R, Franklin M J, Hellerstein J M, et al.. TAG: A tiny aggregation service for ad-hoc sensornetworks. In: Proceedings of USENIX OSDI, 2002, 131–146
2. Yao Y, Gehrke J . Query processing for sensornetworks. In: Proceedings of CIDR, 2003
3. Silberstein A, Braynard R, Filpus G, et al.. Data-driven processing in sensor networks. In: Proceedings of CIDR, 2007, 10–21
4. Diao Y, Ganesan D, Mathur G, et al.. Rethinking data management for storage-centricsensor networks. In: Proceedings of CIDR, 2007, 22–31
5. Intanagonwiwat C, Govindan R, Estrin D . Directed diffusion: A scalable and robust communicationparadigm for sensor networks. In: Proceedingsof ACM/IEEE MobiCom, Boston, MA, 2000, 56–67
6. Considine J, Li F, Kollios G, et al.. Approximate aggregation techniques for sensordatabases. In: Proceedings of IEEE ICDE, Boston, MA, 2004, 449–460
7. Greenwald M B, Khanna S . Power-conserving computationof order-statistics over sensor networks. In: Proceedings of ACM PODS, 2004, 275–285
8. Shrivastava N, Buragohain C, Agrawal D, et al.. Medians and beyond: New aggregation techniquesfor sensor networks. In: Proceedings ofACM SenSys, 2004, 239–249
9. Kotidis Y . Snapshotqueries: Towards data-centric sensor networks. In: Proceedings of IEEE ICDE, 2005, 131–142
10. Hartl G, Li B . Infer: A bayesian inferenceapproach towards energy efficient data collection in dense sensornetworks. In: Proceedings of IEEE ICDCS, 2005, 371–380
11. Silberstein A, Braynard R, Yang J . Constraint-Chaining: On energy-efficient continuous monitoringin sensor networks. In: Proc. ACM SIGMOD, Chicago, IL, 2006, 157–168
12. Silberstein A, Munagala K, Yang J . Energy-efficient monitoring of extreme values in sensornetworks. In: Proceedings of ACM SIGMOD, Chicago, IL, 2006, 169–180
13. Nath S, Gibbons P B, Seshan S, et al.. Synopsis diffusion for robust aggregation insensor networks. In: Proceedings of ACMSenSys, 2003, 250–262
14. Han Q, Mehrotra S, Venkatasubramanian N . Energy efficient data collection in distributedsensor environments. In: Proceedings ofIEEE ICDCS, Tokyo, 2004, 590–597
15. Sharaf M A, Beaver J, Labrinidis A, et al.. Balancing energy efficiency and quality of aggregatedata in sensor network. VLDB Journal, 2004, 13(4): 384–403. doi:10.1007/s00778‐004‐0138‐0
16. Deligiannakis A, Kotidis Y, Roussopoulos N . Processing approximate aggregate queries in wirelesssensor networks. Information Systems, 2006, 31(8): 770–792. doi:10.1016/j.is.2005.02.001
17. Wu M, Xu J, Tang X . Processing precision-constrained approximate queriesin wireless sensor networks. In: Proceedingsof MDM, Nara, 2006, 31
18. Madden S R, Franklin M J, Hellerstein J M, et al.. TinyDB: An acquisitional query processing Systemfor sensor networks. ACM Transactions onDatabase systems, 2005, 30(1): 122–173. doi:10.1145/1061318.1061322
19. Deshpande A, Guestrin C, Madden S, et al.. Model-driven data acquisition in sensor networks. In: Proceedings of VLDB, 2004, 588–599
20. Chu D, Deshpande A, Hellerstein J M, et al.. Approximate data collection in sensor networksusing probabilistic models. In: Proceedingsof IEEE ICDE, 2006, 48
21. Li M, Ganesan D, Shenoy P . PRESTO: Feedback-driven data management in sensor networks. In: Proceedings of NSDI, San Jose, 2006, 311–324
22. Wu S H, Chuang K T, Chen C M, et al.. DIKNN: An itinerary-based KNN query processingalgorithm for mobile sensor networks. In: Proceedings of ICDE, 2007, 456–465
23. Yang X, Lim H B, Ozsu T, et al.. In-network execution of monitoring queries insensor networks. In: Proceedings of SIGMOD, 2007, 521–532
24. Xiang S, Lim H B, Tan K L, et al.. Two-tier multiple query optimization for sensornetworks. In: Proceedings of ICDCS, 2007, 39
25. Xu Y, Lee W C, Xu J, et al.. Processing window queries in wireless sensornetworks. In: Proceedings of IEEE ICDE, Atlanta, 2006, 10
26. Wu M, Xu J, Tang X, et al.. Top-k monitoring in wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(7): 962–976. doi:10.1109/TKDE.2007.1038
27. Wang D, Xu J, Liu J C, et al.. Mobile Filtering for Error-Bounded Data Collectionin Sensor Networks. In: Proceedings ofthe 28th IEEE Int Conf on Distributed Computing Systems, 2008, 1483–1485
28. Tang X, Xu J . Adaptive Data CollectionStrategies for Lifetime-Constrained Wireless Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(6): 721–734. doi:10.1109/TPDS.2008.27
29. Tang X, Xu J . Optimizing lifetime for continuousdata aggregation with precision guarantees in wireless sensor networksIEEE/ACM Transactionson Networking, 2008, 99: 1–14
30. Ratnasamy S, Karp B, Shenker S, et al.. Data-centric storage in sensornets with GHT,a geographic hash table. Mobile Networksand Applications, 2003, 8(4): 427–442. doi:10.1023/A:1024591915518
31. Zhang W, Cao G, Porta T L . Data dissemination with ring-based index for wirelesssensor networks. IEEE Transactions on MobileComputing, 2007, 6(7): 832–847. doi:10.1109/TMC.2007.1019
32. Xu J, Tang X, Lee W C . A new storage scheme for approximate location queriesin object tracking sensor networks. IEEETransactions on Parallel and Distributed Systems, 2008, 19(2): 262–275
33. Li X, Kim Y J, Govindan R, et al.. Multi-dimensional range queries in sensor networks. In: Proceedings of ACM SenSys, 2003, 63–75
34. Bhattacharya A, Meka A, Singh A K . MIST: Distributed indexing and querying in sensor networksusing statistical models. In: Proceedingsof VLDB, 2007, 854–865
35. Wu C H, Chang L P, Kuo T W . An efficient R-tree implementation over flash-memorystorage systems. In: Proceedings of ACMGIS, 2003, 17–24
36. Wu C H, Chang L P, Kuo T W . An efficient B-tree layer implementation for flash-memorystorage systems. ACM Transactions on EmbeddedComputing Systems, 2007, 6(3): 19. doi: 10.1145/1275986.1275991
37. Nath S, Kansal A . FlashDB: Dynamic self-tuningdatabase for NAND flash. In: Proceedingsof IPSN, 2007, 410–419
38. Dai H, Neufeld M, Han R . ELF: An efficient log-structured flash file system formicro sensor nodes. In: Proceedings ofACM SenSys, 2004, 176–187
39. Zeinalipour-Yazti D, Lin S, Kalogeraki V, et al.. MicroHash: An efficient index structure forflash-based sensor devices. In: Proceedingsof USENIX FAST, 2005, 31–44
40. Lee S W, Moon B . Design of flash-Based DBMS:An in-page logging approach. In: Proceedingsof SIGMOD, 2007, 55–66
41. Xu J, Lee W C, Tang X, et al.. An error-resilient and tunable distributed indexingscheme for wireless data broadcast. IEEETransactions on Knowledge and Data Engineering, 2006, 18(3): 392–404. doi:10.1109/TKDE.2006.37