Skip to main content
Top
Published in: Wireless Networks 3/2011

01-04-2011

Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks

Authors: Stefano Basagni, Alessio Carosi, Chiara Petrioli, Cynthia A. Phillips

Published in: Wireless Networks | Issue 3/2011

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We define scalable models and distributed heuristics for the concurrent and coordinated movement of multiple sinks in a wireless sensor network, a case that presents significant challenges compared to the widely investigated case of a single mobile sink. Our objective is that of maximizing the network lifetime defined as the time from the start of network operations till the failure of the first node. We contribute to this problem providing three new results. We first define a linear program (LP) whose solution provides a provable upper bound on the maximum lifetime possible for any given number of sinks. We then develop a centralized heuristic that runs in polynomial time given the solution to the LP. We also define a deployable distributed heuristic for coordinating the motion of multiple sinks through the network. We demonstrate the performance of the proposed heuristics via ns2-based simulations. The observed results show that our distributed heuristic achieves network lifetimes that are remarkably close to the optimum ones, resulting also in significant improvements over the cases of deploying the sinks statically, of random sink mobility and of heuristics previously proposed for restricted sink movements.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
Definitions of network lifetime vary, and depend on applications. In this paper we adopt the widely used definition introduced in [2] and used in many works (see [3, 4] and references therein) where lifetime is defined as the time until the failure (here for energy depletion) of the first node. This definition may seem too pessimistic, and many advocate definitions based on the failure of a certain percentage of the nodes. However, robust, energy-efficient protocols for WSNs tend to balance energy consumption among the nodes. So when the first node dies, many other nodes are also about to die.
 
2
One might expect that an optimal schedule will use all stationary sinks at all times. However, there may be times when it is best not to use one even if it is available. This is because the extra sink will affect packet routes, possibly affecting energy balance negatively.
 
3
If the protocol involves a training phase, i.e., a phase through which the sensors and the sinks learn about parameters needed to start protocol operations, e p is the energy after the training.
 
4
Holding major configurations for a longer time allows routes to stabilize and run for enough time to justify the cost of changing the configuration.
 
5
Note that these weights are a metric. Weighting only by the number of transient states does not satisfy the triangle inequality.
 
Literature
1.
go back to reference Yick, J., Mukherjee, B., & Ghosal, D. (2008). Wireless sensor network survey. Computer Networks, 52(12), 2292–2330.CrossRef Yick, J., Mukherjee, B., & Ghosal, D. (2008). Wireless sensor network survey. Computer Networks, 52(12), 2292–2330.CrossRef
2.
go back to reference Chang, J.-H., & Tassiulas, L. (2000). Energy conserving routing in wireless ad hoc networks. In Proceedings of IEEE infocom 2000, Tel Aviv, Israel, Vol. 1, pp. 22–31, March 26–30. Chang, J.-H., & Tassiulas, L. (2000). Energy conserving routing in wireless ad hoc networks. In Proceedings of IEEE infocom 2000, Tel Aviv, Israel, Vol. 1, pp. 22–31, March 26–30.
3.
go back to reference Cheng, Z., Perillo, M., & Heinzelman, W. B. (2008). General network lifetime and cost models for evaluating sensor network deployment strategies. IEEE Transactions on Mobile Computing, 7(4), 484–497.CrossRef Cheng, Z., Perillo, M., & Heinzelman, W. B. (2008). General network lifetime and cost models for evaluating sensor network deployment strategies. IEEE Transactions on Mobile Computing, 7(4), 484–497.CrossRef
4.
go back to reference Mak, N. H., & Seah, W. K. G. (2009). How long is the lifetime of a wireless sensor network? In Proceedings of the IEEE 23rd international conference on advanced information networking and applications, AINA 2009, Bradford, UK, pp. 763–770, May 26–29. Mak, N. H., & Seah, W. K. G. (2009). How long is the lifetime of a wireless sensor network? In Proceedings of the IEEE 23rd international conference on advanced information networking and applications, AINA 2009, Bradford, UK, pp. 763–770, May 26–29.
5.
go back to reference Basagni, S., Carosi, A., Melachrinoudis, E., Petrioli, C., Wang, Z. M. (2008). Controlled sink mobility for prolonging wireless sensor networks lifetime. ACM/Springer Wireless Networks, 14(6), 831–858.CrossRef Basagni, S., Carosi, A., Melachrinoudis, E., Petrioli, C., Wang, Z. M. (2008). Controlled sink mobility for prolonging wireless sensor networks lifetime. ACM/Springer Wireless Networks, 14(6), 831–858.CrossRef
6.
go back to reference Azad, A. P., & Chockalingam, A. (2006). Mobile base station placement and energy aware routing in wireless sensor networks. In Proceeding of the IEEE wireless communications and networking conference, WCNC 2006, Las Vegas, NV, Vol. 1, pp. 264–269, April 3–6. Azad, A. P., & Chockalingam, A. (2006). Mobile base station placement and energy aware routing in wireless sensor networks. In Proceeding of the IEEE wireless communications and networking conference, WCNC 2006, Las Vegas, NV, Vol. 1, pp. 264–269, April 3–6.
7.
go back to reference Gandham, S. R., Dawande, M., Prakash, R., & Venkatesan, S. (2003). Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In Proceedings of IEEE globecom 2003, San Francisco, CA, Vol. 1, pp. 377–381, December 1–5. Gandham, S. R., Dawande, M., Prakash, R., & Venkatesan, S. (2003). Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In Proceedings of IEEE globecom 2003, San Francisco, CA, Vol. 1, pp. 377–381, December 1–5.
8.
go back to reference Ren, B., Ma, J., & Chen, C. (2006). The hybrid mobile wireless sensor networks for data gathering. In Proceedings of the ACM international conference on wireless communications and mobile computing, IWCMC 2006, Vancouver, BC, pp. 1085–1090, July 3–6. Ren, B., Ma, J., & Chen, C. (2006). The hybrid mobile wireless sensor networks for data gathering. In Proceedings of the ACM international conference on wireless communications and mobile computing, IWCMC 2006, Vancouver, BC, pp. 1085–1090, July 3–6.
9.
go back to reference Chen, C., Ma, J., & Yu, K. (2006). Designing energy-efficient sensor networks with mobile sinks. In Proceedings of the 1st workshop on world-sensor-web: Mobile device centric sensory networks and applications, WSW 2006, Boulder, CO, October 31. Chen, C., Ma, J., & Yu, K. (2006). Designing energy-efficient sensor networks with mobile sinks. In Proceedings of the 1st workshop on world-sensor-web: Mobile device centric sensory networks and applications, WSW 2006, Boulder, CO, October 31.
10.
go back to reference Chatzigiannakis, I., Kinalis, A., Nikoletseas, S., & Rolim, J. (2007). Fast and energy efficient sensor data collection by multiple mobile sinks. In Proceedings of the 5th ACM international workshop on mobility management and wireless access, MobiWac 2007, Chania, Crete Island, pp. 25–32, October 22. ACM. Chatzigiannakis, I., Kinalis, A., Nikoletseas, S., & Rolim, J. (2007). Fast and energy efficient sensor data collection by multiple mobile sinks. In Proceedings of the 5th ACM international workshop on mobility management and wireless access, MobiWac 2007, Chania, Crete Island, pp. 25–32, October 22. ACM.
11.
go back to reference Hillier, F. S., & Lieberman, G. J. (2005). Introduction to operations research (8th ed.). Boston, MA: McGraw Hill. Hillier, F. S., & Lieberman, G. J. (2005). Introduction to operations research (8th ed.). Boston, MA: McGraw Hill.
12.
go back to reference Chandru, V., & Rao, M. R. (1998). Linear programming. In M. Atallah (Eds.), Algorithms and theory of computation handbook. Boca Raton, FL: CRC Press. Chandru, V., & Rao, M. R. (1998). Linear programming. In M. Atallah (Eds.), Algorithms and theory of computation handbook. Boca Raton, FL: CRC Press.
13.
go back to reference Lovász, L., Grötschel, M., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197.CrossRefMATHMathSciNet Lovász, L., Grötschel, M., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197.CrossRefMATHMathSciNet
14.
go back to reference Motwani, R., O’Callaghan, L., & Zhu, A. (2007). Asymptotic polynomial-time approximation schemes. In G. Gonzalez (Eds.), Handbook of approximation algorithms and metaheuristics. Boca Raton, FL: CRC Press. Motwani, R., O’Callaghan, L., & Zhu, A. (2007). Asymptotic polynomial-time approximation schemes. In G. Gonzalez (Eds.), Handbook of approximation algorithms and metaheuristics. Boca Raton, FL: CRC Press.
15.
go back to reference Schrijver, A. (1998). Theory of linear and integer programming. New York: Wiley.MATH Schrijver, A. (1998). Theory of linear and integer programming. New York: Wiley.MATH
16.
go back to reference Revelle, C., & Swain, R. (1970). Central facilities location. Geographical Analysis, 2, 30–42.CrossRef Revelle, C., & Swain, R. (1970). Central facilities location. Geographical Analysis, 2, 30–42.CrossRef
17.
go back to reference Berry, J., Hart, W., Phillips, C., Uber, J., & Watson, J.-P. (2006). Sensor placement in municipal water networks with temporal integer programming models. Journal of Water Resources Planning and Management, 132, 218–224.CrossRef Berry, J., Hart, W., Phillips, C., Uber, J., & Watson, J.-P. (2006). Sensor placement in municipal water networks with temporal integer programming models. Journal of Water Resources Planning and Management, 132, 218–224.CrossRef
19.
go back to reference Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Carnegie-Mellon University, Graduate School of Industrial Administration. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Carnegie-Mellon University, Graduate School of Industrial Administration.
21.
go back to reference Deitel, H. M., Deitel, P. J., Nieto, T. R., & McPhie, D. C. (2000). Perl how to program. Englewood Cliffs, NJ: Prentice Hall. Deitel, H. M., Deitel, P. J., Nieto, T. R., & McPhie, D. C. (2000). Perl how to program. Englewood Cliffs, NJ: Prentice Hall.
22.
go back to reference Gabow, H. N. (1973). Implementation of algorithms for maximum matching on non-bipartite graphs. PhD thesis, Stanford University, Department of Computer Science, Palo Alto, CA. Gabow, H. N. (1973). Implementation of algorithms for maximum matching on non-bipartite graphs. PhD thesis, Stanford University, Department of Computer Science, Palo Alto, CA.
24.
go back to reference IEEE Standard for Information Technology. (2003). Part 15.4: Wireless medium access control (MAC) and physical layer (PHY). Specifications for low-rate wireless personal area networks (LR-WPANs). IEEE Standard for Information Technology. (2003). Part 15.4: Wireless medium access control (MAC) and physical layer (PHY). Specifications for low-rate wireless personal area networks (LR-WPANs).
26.
go back to reference Gu, L., & Stankovic, J. A. (2005). Radio-triggered wake-up for wireless sensor networks. Real-Time Systems, 29(2–3), 157–182.CrossRef Gu, L., & Stankovic, J. A. (2005). Radio-triggered wake-up for wireless sensor networks. Real-Time Systems, 29(2–3), 157–182.CrossRef
27.
go back to reference Kolinko, P., & Larson, L. E. (2007). Passive RF receiver design for wireless sensor networks. In Proceeding of the IEEE/MTT-S international microwave symposium, IMS 2007, Honolulu, HI, pp. 567–570, June 3–8. Kolinko, P., & Larson, L. E. (2007). Passive RF receiver design for wireless sensor networks. In Proceeding of the IEEE/MTT-S international microwave symposium, IMS 2007, Honolulu, HI, pp. 567–570, June 3–8.
28.
go back to reference Lu, G., De, D., Xu, M., Song, W.-Z., & Shirazi, B. (2009). A wake-on sensor network. In Proceedings of the 7th ACM conference on embedded networked sensor systems, SenSys 2009, pp. 341–342, November 4–6. Lu, G., De, D., Xu, M., Song, W.-Z., & Shirazi, B. (2009). A wake-on sensor network. In Proceedings of the 7th ACM conference on embedded networked sensor systems, SenSys 2009, pp. 341–342, November 4–6.
29.
go back to reference Luo, J., & Hubaux, J.-P. (2005). Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of IEEE infocom 2005, Miami, FL, Vol. 3, pp. 1735–1746, March 13–17. Luo, J., & Hubaux, J.-P. (2005). Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of IEEE infocom 2005, Miami, FL, Vol. 3, pp. 1735–1746, March 13–17.
Metadata
Title
Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks
Authors
Stefano Basagni
Alessio Carosi
Chiara Petrioli
Cynthia A. Phillips
Publication date
01-04-2011
Publisher
Springer US
Published in
Wireless Networks / Issue 3/2011
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-010-0313-8

Other articles of this Issue 3/2011

Wireless Networks 3/2011 Go to the issue