Energy Efficient Data Indexing and Query Processing for Static and Mobile Wireless Sensor Networks


Mohamed M.Ali Mohamed
Ashfaq Khokhar
Goce Trajcevski


This work addresses the problem of efficiently balancing the use of network resources when processing both spatially-constrained and (sensed) value based queries in Wireless Sensor Networks. To alleviate the drawbacks inherent to centralized approaches – e.g., overheads in energy consumption and latency due to the transmission of the individual raw data/measurements to a dedicated sink, we propose in-network processing methodologies which unify the management of physical and data-space based queries. Since sensed data typically represents values that evolve over time, the distributed data management approaches need to be efficient in terms of communication cost and storage requirements. Furthermore, if the query processing paradigm(s) allows approximate answers, it may yield additional benefits if data abstractions based on higher-order statistics are integrated in the data management. The related challenges are further compounded if the nodes are mobile, for the purpose of adapting the quality of sensing/coverage to spatial changes in the data field. We present novel communication and storage efficient physical and data-space abstractions to facilitate in-network indexing of sensed data and processing of queries in WSNs consisting of mobile and static nodes. We also present novel algorithms to handle changes in the abstractions due to mobility of the nodes. To trade-off (im)precision vs. energy consumption, the proposed abstraction schemes combine rank order statistics, regular sampling, and bitmap representation. The proposed abstractions are generic, in the sense that they can be utilized in any hierarchical indexing structure that is based on binary space partitioning (BSP), such as k-d trees, Quadtrees and Octrees. Based on implementation in SIDnet-SWANS simulator, our experimental results demonstrate the effectiveness of the proposed abstractions under different mobility models, mobility speeds, and query streams.


How to Cite
Mohamed M.Ali Mohamed, Ashfaq Khokhar, & Goce Trajcevski. (2015). Energy Efficient Data Indexing and Query Processing for Static and Mobile Wireless Sensor Networks. International Journal of Next-Generation Computing, 6(2), 96–128.


  1. Akkaya, K., and Younis, M. 2005. A survey on routing protocols for wireless sensor networks. In Ad hoc networks, 2005. 3(3), 325-349
  2. Ali Mohamed, M., Khokhar, A., Trajcevski, G., Ansari, R., and Ouksel, A. 2012. Approximate hybrid query processing in wireless sensor networks In Proceedings of the 20th International Conference on Advances in Geographic Information Systems. ACM 2012 542-545
  3. Caicedo-Nuez, C.H., and Zefran, M. 2008. A coverage algorithm for a class of non-convex regions. In Decision and Control, 2008. 4244-4249
  4. Chakrabarti, A., Sabharwal, A., and Aazhang, B. 2003. Using predictable observer mobility for power ecient design of sensor networks. In Information Processing in Sensor Networks. Springer Berlin Heidelberg 129-145.
  5. Chen, J., Johansson, K. H., Olariu, S., Paschalidis, I. C. and Stojmenovic, I. 2011. Guest editorial special issue on wireless sensor and actuator networks. In IEEE Transactions 2011. 56(10), 2244-2246.
  6. Chui, C. K. 1992. An introduction to wavelets. In Academic press.
  7. Ciancio, A., Pattem, S., Ortega, A., and Krishnamachari, B. 2006. Energy-ecient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm. In Proceedings of the 5th international conference on Information processing in sensor networks. 309-316.
  8. Dantu, K., Rahimi, M., Shah, H., Babel, S., Dhariwal, A., and Sukhatme, G. S. 2005. Robomote: enabling mobility in sensor networks. In Proceedings of the 4th international symposium on Information processing in sensor networks. IEEE Press 55.
  9. Dietrich, I., and Dressler, F. 2009. On the lifetime of wireless sensor networks. In ACM Transactions on Sensor Networks (TOSN), 5(1) 5.
  10. Ekici, E., Gu, Y., and Bozdag, D. 2006. Mobility-based communication in wireless sensor networks. In IEEE Communications Magazine, 44(7), 56.
  11. Gandham, S. R., Dawande, M., Prakash, R. and Venkatesan, S 2003. Energy ecient schemes for wireless sensor networks with multiple mobile base stations. In Global telecommunications conference, 2003. GLOBECOM'03. IEEE (Vol. 1, pp. 377-381).
  12. Gandhi, S., Hershberger, J., and Suri, S. 2007. Approximate isocontours and spatial summaries for sensor networks. In Information Processing in Sensor Networks, 2007. IPSN 2007. 6th International Symposium on (pp. 400-409).
  13. Ganesan, D., Greenstein, B., Estrin, D., Heidemann, J., and Govindan, R. 2005. Multiresolution storage and search in sensor networks. In ACM Transactions on Storage (TOS), 1(3), 277-315.
  14. Ghica, O. C., Trajcevski, G., Scheuermann, P., Bischof, Z., and Valtchanov, N. 2008. Sidnet-swans: A simulator and integrated development platform for sensor networks applications. In Proceedings of the 6th ACM conference on Embedded network sensor systems (pp. 385-386).
  15. Greenstein, B., Ratnasamy, S., Shenker, S., Govindan, R., and Estrin, D. 2003. DIFS: A distributed index for features in sensor networks. In Ad Hoc Networks, 1(2), 333-349.
  16. Hanoun, S., Creighton, D., and Nahavandi, S. 2008. Decentralized mobility models for data collection in wireless sensor networks. In Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on (pp. 1030-1035).
  17. Hosking, J. R. 1984. Modeling persistence in hydrological time series using fractional di erencing. In Water resources research, 20(12), 1898-1908.
  18. Keshner, M. S. 1982. 1/f noise. In Proceedings of the IEEE, 70(3), 212-218.
  19. Liu, C and Cao, G. 2010. Distributed monitoring and aggregation in wireless sensor networks. In INFOCOM, 2010 Proceedings IEEE (pp. 1-9).
  20. Lou, J., and Hubaux, J. P. 2005. Joint mobility and routing for lifetime elongation in wireless sensor networks. In INFOCOM 2005. 24th annual joint conference of the IEEE computer and communications societies. Proceedings IEEE (Vol. 3, pp. 1735-1746).
  21. Meliou, A., Guestrin, C., and Hellerstein, J. M. 2009. Approximating sensor network queries using in-network summaries. In Information Processing in Sensor Networks, 2009. IPSN 2009. International Conference on (pp. 229-240).
  22. Mohamed, M.M.A, and Khokhar, A.A 2011. Dynamic indexing system for spatio-temporal queries in wireless sensor networks. In Mobile Data Management (MDM), 2011 12th IEEE International Conference on (Vol. 2, pp. 35-37).
  23. Mohamed, M.M.A, Khokhar, A.A, and Trajcevski, G. 2013. Energy ecient in-network data indexing for mobile wireless sensor networks. In Advances in Spatial and Temporal Databases (pp. 165-182). Springer Berlin Heidelberg.
  24. Mulligan, R., and Ammari, H. M. 2010. Coverage in wireless sensor networks: a survey. In Network Protocols and Algorithms, 2(2), 27-53.
  25. Ouksel, A., Xiao, L., and Hauswirth, M. 2007. Dynamically Self-Organizing Sensors as Virtual In-Network Aggregators and Query Processors in Mobile Ad-Hoc Sensor Databases. In 2007 IEEE 23rd International Conference on Data Engineering (ICDE 2007).
  26. Pileggi, S. F., Fernandez-Llatas, C., and Meneu, T. 2011. Evaluating mobility impact on wireless sensor network. In Computer Modelling and Simulation (UKSim), 2011 UkSim 13th International Conference on (pp. 461-466).
  27. Pon, R., Batalin, M. A., Gordon, J., Kansal, A., Liu, D., Rahimi, M., and Estrin, D. 2005. Networked infomechanical systems: a mobile embedded networked sensor platform. In Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on (pp. 376-381).
  28. Samet, H. 1990. The design and analysis of spatial data structures. In (Vol. 85, p. 87). Reading, MA: Addison- Wesley.
  29. Shi, H. and Schaeffer, J. 1992. Parallel sorting by regular sampling. In Journal of Parallel and Distributed Computing, 14(4), 361-372.
  30. Somasundara, A. A., Ramamoorthy, A., and Srivastava, M. B. 2004. Mobile element scheduling for ecient data collection in wireless sensor networks with dynamic deadlines. In Real-Time Systems Symposium, 2004. Proceedings. 25th IEEE International (pp. 296-305).
  31. Sushant, R. C. S. S. R.. Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks.
  32. Wang, Z. M., Basagni, S., Melachrinoudis, E., and Petrioli, C. 2005. Exploiting sink mobility for maxi- mizing sensor networks lifetime. In System Sciences, 2005. HICSS'05. Proceedings of the 38th Annual Hawaii International Conference on (pp. 287a-287a).
  33. Willinger, W., Taqqu, M. S., Sherman, R., and Wilson, D. V 1997. Self-similarity through high-variability: statistical analysis of Ethernet LAN trac at the source level. In Networking, IEEE/ACM Transactions on, 5(1), 71-86.
  34. Xing, G., Li, M., Wang, T., Jia, W., and Huang, J. 2012. Ecient rendezvous algorithms for mobility-enabled wireless sensor networks. In Mobile Computing, IEEE Transactions on, 11(1), 47-60.
  35. Zhao, F., and Guibas, L. J. 2004. Wireless sensor networks: an information processing approach. In Morgan Kaufmann. [Online]