Skip to main content

Advertisement

SpringerLink
Log in

Stochastic Models and Adaptive Algorithms for Energy Balance in Sensor Networks

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We consider the important problem of energy balanced data propagation in wireless sensor networks and we extend and generalize previous works by allowing adaptive energy assignment. We consider the data gathering problem where data are generated by the sensors and must be routed toward a unique sink. Sensors route data by either sending the data directly to the sink or in a multi-hop fashion by delivering the data to a neighbouring sensor. Direct and neighbouring transmissions require different levels of energy consumption. Basically, the protocols balance the energy consumption among the sensors by computing the adequate ratios of direct and neighbouring transmissions. An abstract model of energy dissipation as a random walk is proposed, along with rigorous performance analysis techniques. Two efficient distributed algorithms are presented and analyzed, by both rigorous means and simulation. The first one is easy to implement and fast to execute. The protocol assumes that sensors know a-priori the rate of data they generate. The sink collects and processes all these information in order to compute the relevant value of the protocol parameter. This value is transmitted to the sensors which individually compute their optimal ratios of direct and neighbouring transmissions. The second protocol avoids the necessary a-priori knowledge of the data rate generated by sensors by inferring the relevant information from the observation of the data paths. Furthermore, this algorithm is based on stochastic estimation methods and is adaptive to environmental changes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chatzigiannakis, I., Dimitriou, T., Nikoletseas, S., Spirakis, P.: A probabilistic algorithm for efficient and robust data propagation in smart dust networks. In: The Proceedings of the 5th European Wireless Conference on Mobile and Wireless Systems beyond 3G (EW 2004), pp. 344–350 (2004). Also, in the Ad-Hoc Networks Journal, Elsevier, 4(5):621–635 (2006)

  2. Chatzigiannakis, I., Nikoletseas, S., Spirakis, P.: Smart dust protocols for local detection and propagation. In: The Proceedings of the 2nd ACM Workshop on Principles of Mobile Computing (POMC), ACM Press, pp. 9–16, 2002. Also, in the Mobile Networks and Applications (MONET) Journal, 10(1):133–149 (2005)

  3. Efthymiou, C., Nikoletseas, S., Rolim, J.: Energy balanced data propagation in wireless sensor networks. In: Proc. 4th International Workshop on Algorithms for Wireless, Mobile, Ad-Hoc and Sensor Networks (WMAN ’04), IPDPS 2004, IEEE Computer Society Press (2004). Also, in the Wireless Networks (WINET) Journal, 12(6):691–707 (2006)

  4. Giridar, A., Kumar, P.R.: Maximizing the functional lifetime of sensor networks. In: Proceedings of the Fourth International Conference on Information Processing in Sensor Networks, IPSN’05, UCLA Los-Angeles, USA (2005)

  5. Guo, W., Liu, Z., Wu, G.: An energy-balanced transmission scheme for sensor networks. In: The First ACM International Conference on Embedded Networked Sensor Systems (ACM SenSys 2003), Poster Session, Los Angeles, CA, November (2003)

  6. Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H.: An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun. 1(4) (2002)

  7. Jarry, A., Leone, P., Powell, O., Rolim, J.: An optimal data propagation algorithm for maximizing the lifespan of sensor networks. IEEE International Conference on Distributed Computing in Sensor Systems, San Francisco, CA, USA, June 18–20 (2006). Lecture Notes in Computer Science (2006)

  8. Leone, P., Rolim, J.: Towards a dynamical model for wireless sensor network. First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Turku, Finland. Lecture Notes in Computer Sciences 3121, Springer, July (2004)

  9. Liu, Z., Xiu, D., Guo, W.: An energy-balanced model for data transmission in sensor networks. The IEEE 62nd Semiannual Vehicular Technology Conference, Dallas, Texas, September 25–28 (2005)

  10. Luo, J., Hubaux, J.-P.: Joint mobility and routing for lifetime elongation in wireless sensor networks. In: Proc. of the 24th IEEE INFOCOM (2005)

  11. Luo, J.: Mobility in wireless networks: friend or Foe – network design and control in the age of mobile computing. PhD thesis, School of Computer and Communications Science, EPFL, Switzerland (2006)

  12. Luo, J., Hubaux, J.-P.: Mobility to improve the lifetime of wireless sensor networks: a theoretical framework. In: Proc. of the Workshops of the Second International Conference on Distributed Computing in Sensor Systems (DCOSS) (2006)

  13. Muheymin, S.K., Tari, Z., Khalil, I.: Energy balanced topology for the sensor networks. In: Proceedings of the Post Graduate Research Students Conference – 2005 (PRSC 2005). RMIT University, 25 November (2005)

  14. Olariu, S., Stojmenovic, I.: Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting. IEEE INFOCOM, Barcelona, Spain, April 24–25 (2006)

  15. Powell, O., Leone, P., Rolim, J.: Energy optimal data propagation in sensor networks. J. Parallel Distributed Comput. 67(3), 302–317 (2007)

    Article  MATH  Google Scholar 

  16. Singh, M., Prasanna, V.: Energy-optimal and energy-balanced sorting in a single-hop wireless sensor network. In: Proc. First IEEE International Conference on Pervasive Computing and Communications – PERCOM (2003)

  17. Vass, D., Vincze, Z., Vida, R., Vidács, A.: Energy efficiency in wireless sensor networks using mobile base station. EUNICE 2005: Networks and Applications Towards a Ubiquitously Connected World

  18. Zhang, H., Shen, H., Tan, Y.: Optimal energy balanced data gathering in wireless sensor networks. In: Proc. IEEE IPDPS, pp. 1–10 (2007)

Download references

Author information

Authors and Affiliations

  1. University of Geneva, C.U.I., Battelle, Bat. A, route de Drize 7, 1227, Carouge, Switzerland

    Pierre Leone & José Rolim

  2. Computer Technology Institute, N. Kazantzaki Str 1, Patras University Campus, 26500, Rion, Patras, Greece

    Sotiris Nikoletseas

Authors
  1. Pierre Leone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sotiris Nikoletseas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José Rolim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pierre Leone.

Additional information

This work has been partially supported by the ICT Programme of the European Union under contract number FP7-215270 (FRONTS).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Leone, P., Nikoletseas, S. & Rolim, J. Stochastic Models and Adaptive Algorithms for Energy Balance in Sensor Networks. Theory Comput Syst 47, 433–453 (2010). https://doi.org/10.1007/s00224-009-9193-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-009-9193-7

Keywords

Search

Navigation