Storing, collecting and querying data across miniaturized battery powered Wireless Sensor Networks (WSN) is a key research focus today. Distributed Data-Centric Storage (DCS), an alternate to External Storage (ES) and Local Storage (LS), is thought to be a promising and efficient storage and search mechanism. There has been a growing interest in understanding and optimizing WSN DCS schemes in recent years, where the range query mechanism, similarity search, load balancing, multi-dimensional data search, as well as limited and constrained resources have driven this line of research. In this paper, an extensive state-of-the-art study is provided including the prime WSN DCS schemes, challenges that inspired these schemes, as well as drawbacks and shortcomings of existing solutions. In contrast to previous surveys that briefly discuss the contribution of a few WSN DCS mechanisms, we provide a thematic taxonomy in which schemes are classified according to the problems dealt with including range query, similarity search, data aggregation, sensor network field non-uniformity, multi-replication, load balancing and routing algorithm.
References
[1]
Ratnasamy, S.; Karp, B.; Yin, L.; Yu, F.; Estrin, D.; Govindan, R.; Shenker, S. GHT: A Geographic Hash Table for Data-centric Storage. In Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, USA, 28 September 2002; pp. 78–87.
[2]
Campobello, G.; Leonardi, A.; Palazzo, S. A Novel Reliable and Energy-Saving Forwarding Technique for Wireless Sensor Networks. In Proceedings of the Tenth ACM international Symposium on Mobile Ad Hoc Networking and Computing, New Orleans, LA, USA, 18-21 May 2009; pp. 269–278.
Saroiu, S.; Gummadi, P.K.; Gribble, S.D. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of the Multimedia Computing and Networking (MMCN), San Jose, CA, USA, January 2002; pp. 152–157.
[5]
Yao, Y.; Tang, X.; Lim, E.-P. In-Network Processing of Nearest Neighbor Queries for Wireless Sensor Networks. In Proceedings of the 11th International Conference on Database Systems for Advanced Applications, Singapore, 12–15 April 2006; pp. 35–49.
[6]
Szewczyk, R.; Polastre, J.; Mainwaring, A.; Culler, D. Lessons from a Sensor Network Expedition. In Proceedings of European Workshop Wireless Sensor Network, Berlin, Germany, 19-21 January 2004; pp. 307–322.
[7]
Intanagonwiwat, C.; Govindan, R.; Estrin, D. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, Boston, MA, USA, 6-11 August 2000; pp. 56–67.
[8]
Zhang, W.; Cao, G.; Porta, T.L. Data dissemination with ring-based index for wireless sensor networks. IEEE Trans. Mob. Comput. 2007, 6, 832–847, doi:10.1109/TMC.2007.1019.
[9]
Madden, S.R.; Franklin, M.J.; Hellerstein, J.M.; Hong, W. TinyDB: An acquisitional query processing system for sensor networks. ACM Trans. Database Syst. 2005, 30, 122–173, doi:10.1145/1061318.1061322.
[10]
Ye, F.; Luo, H.; Cheng, J.; Lu, S.; Zhang, L. A Two-tier Data Dissemination Model for Large-scale Wireless Sensor Networks. In Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, Atlanta, GA, USA, 23-26 September 2002; pp. 148–159.
[11]
Ye, F.; Zhong, G.; Lu, S.; Zhang, L. Gradient broadcast: A robust data delivery protocol for large scale sensor networks. Wirel. Netw. 2005, 11, 285–298, doi:10.1007/s11276-005-6612-9.
[12]
Langendoen, K. Medium access control in wireless sensor networks. Medium Access Control Wirel. Netw. 2008, 2, 535–560.
[13]
Li, X.; Kim, Y.J.; Govindan, R.; Hong, W. Multi-dimensional Range Queries in Sensor Networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA, 5-7 November 2003; pp. 63–75.
[14]
Ganesan, D.; Estrin, D.; Heidemann, J. DIMENSIONS: Why do we need a new data handling architecture for sensor networks? ACM SIGCOMM Comput. Commun. Rev. 2003, 33, 143–148, doi:10.1145/774763.774786.
[15]
Ganesan, D.; Cerpa, A.; Ye, W.; Yu, Y.; Zhao, J.; Estrin, D. Networking issues in wireless sensor networks. J. Parallel Distrib. Comput. 2004, 64, 799–814, doi:10.1016/j.jpdc.2004.03.016.
[16]
Rumín, á.C.; Pascual, M.U.; Ortega, R.R.; López, D.L. Data centric storage technologies: Analysis and enhancement. Sensors 2010, 10, 3023–3056, doi:10.3390/s100403023.
[17]
Chatzigiannakis, I.; Kinalis, A.; Nikoletseas, S. An Adaptive Power Conservation Scheme for Heterogeneous Wireless Sensor Networks with Node Redeployment. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, Las Vegas, NV, USA, 17-20 July 2005; pp. 96–105.
Shen, H.; Zhao, L.; Li, Z. A distributed spatial-temporal similarity data storage scheme in wireless sensor networks. IEEE Trans. Mob. Comput. 2011, 10, 982–996, doi:10.1109/TMC.2010.214.
[20]
Rowstron, A.I.T.; Druschel, P. Pastry: Scalable, Decentralized Object Location,and Routing for Large-Scale Peer-to-Peer Systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms, Heidelberg, Germany, 12-16 November 2001; pp. 329–350.
[21]
Karp, B.; Kung, H.T. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, Boston, MA, USA, 6-11 August 2000; pp. 243–254.
[22]
Chung, Y.-C.; Su, I.F.; Lee, C. An efficient mechanism for processing similarity search queries in sensor networks. Inf. Sci. 2011, 181, 284–307, doi:10.1016/j.ins.2010.08.031.
[23]
Liao, W.-H.; Shih, K.-P.; Wu, W.-C. A grid-based dynamic load balancing approach for data-centric storage in wireless sensor networks. Comput. Electr. Eng. 2010, 36, 19–30, doi:10.1016/j.compeleceng.2009.04.003.
[24]
Albano, M.; Chessa, S.; Nidito, F.; Pelagatti, S. Dealing with nonuniformity in data centric storage for wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 2011, 22, 1398–1406, doi:10.1109/TPDS.2011.18.
[25]
Albano, M.; Chessa, S.; Nidito, F.; Pelagatti, S. Q-NiGHT: Adding QoS to Data Centric Storage in Non-Uniform Sensor Networks. In Proceedings of the 2007 International Conference on Mobile Data Management, Mannheim, Germany, 7-11 May 2007; pp. 166–173.
[26]
Von Neumann, J. Various techniques used in connection with random digits. Appl. Math Ser. 1951, 12, 36–38.
[27]
Joung, Y.-J.; Huang, S.-H. Tug-of-War: An Adaptive and Cost-Optimal Data Storage and Query Mechanism in Wireless Sensor Networks. Lect. Note. Comput. Sci. 5067, 237–251.
[28]
Sarkar, R.; Zhu, X.; Gao, J. Double Rulings for Information Brokerage in Sensor Networks. In Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, Los Angeles, CA, USA, 24-29 September 2006; pp. 286–297.
[29]
Albano, M.; Chessa, S. Distributed Erasure Coding in Data Centric Storage for Wireless Sensor Networks. In Proceedings of the IEEE Symposium on Computers and Communications, (ISCC 2009), Sousse, Tunisia, 5-8 July 2009; pp. 22–27.
[30]
Greenstein, B.; Estrin, D.; Govindan, R.; Ratnasamy, S.; Shenker, S. DIFS: A Distributed Index for Features in Sensor Networks. In Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications, Anchorage, AK, USA, 11 May 2003; pp. 163–173.
[31]
Finkel, R.A.; Bentley, J.L. Quad trees a data structure for retrieval on composite keys. Acta Informa. 1974, 4, 1–9, doi:10.1007/BF00288933.
[32]
Ee, C.T.; Ratnasamy, S.; Shenker, S. Practical Data-centric Storage. In Proceedings of the 3rd Conference on Networked Systems Design & Implementation, San Jose, CA, USA, April 2006; 3, pp. 24–24.
[33]
Yao, Z.; Yan, C.; Ratnasamy, S. Load Balanced and Efficient Hierarchical Data-Centric Storage in Sensor Networks. In Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, San Francisco, CA, USA, June 2008; pp. 560–568.
[34]
Zhao, Y.; Li, B.; Zhang, Q.; Chen, Y.; Zhu, W. Efficient Hop ID based Routing for Sparse Ad Hoc Networks. In Proceedings of the 13th IEEE International Conference on Network Protocols, Boston, MA, USA, 6-9 November 2005; pp. 179–190.
[35]
Liao, W.H.; Chen, C.C. Data storage and range query mechanism for multi-dimensional attributes in wireless sensor networks. Communications 2010, 4, 1799–1808.
[36]
Ghose, A.; Grossklags, J.; Chuang, J. Resilient Data-Centric Storage in Wireless Ad-Hoc Sensor Networks. In Proceedings of the 4th International Conference on Mobile Data Management, Melbourne, Australia, 21-24 January 2003; pp. 45–62.
[37]
Shen, H.; Li, T.; Schweiger, T. An Efficient Similarity Searching Scheme Based on Locality Sensitive Hashing. In Proceedings of the 3rd International Conference on Digital Telecommunications (ICDT); Bucharest, Romania: 29 June-5 July 2008.
[38]
Cuevas, A.; Uruena, M.; Cuevas, R.; Romeral, R. Modelling data-aggregation in multi-replication data centric storage systems for wireless sensor and actor networks. Communications 2011, 5, 1669–1681.
[39]
Amato, G.; Baronti, P.; Chessa, S. MaD-WiSe: Programming and Accessing Data in a Wireless Sensor Networks. In Proceedings of the International Conference on Computer as a Tool, (EUROCON 2005), Beograd, Yugoslavia, 21-24 November 2005; 2, pp. 1846–1849.
[40]
Madden, S.; Franklin, M.J.; Hellerstein, J.M.; Hong, W. TAG: A tiny AGgregation service for ad-hoc sensor networks. SIGOPS Oper. Syst. Rev. 2002, 36, 131–146, doi:10.1145/844128.844142.
[41]
Cuevas, A.; Uruena, M.; de Veciana, G. Dynamic Random Replication for Data Centric Storage. In Proceedings of the 13th ACM international Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, Bodrum, Turkey, 17-21 October 2010; pp. 393–402.
[42]
Aly, M.; Pruhs, K.; Chrysanthis, P.K. KDDCS: A Load-Balanced In-Network Data-Centric Storage Scheme for Sensor Networks. In Proceedings of the 15th ACM International Conference on Information and Knowledge Management, Arlington, VA, USA, 6-11 November 2006; pp. 317–326.
[43]
Thang Nam, L.; Wei, Y.; Xiaole, B.; Dong, X. A Dynamic Geographic Hash Table for Data-centric Storage in Sensor Networks. In Proceedings of the Wireless Communications and Networking Conference, (WCNC 2006), Las Vegas, NV, USA, 3-6 April 2006; 4, pp. 2168–2174.
[44]
Newsome, J.; Song, D. GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks without Geographic Information. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA, 5-7 November 2003; pp. 76–88.
