Skip to main content
Erschienen in: Wireless Networks 6/2010

01.08.2010

Distributed fault-tolerant topology control in wireless multi-hop networks

verfasst von: Indranil Saha, Lokesh Kumar Sambasivan, Subhas Kumar Ghosh, Ranjeet Kumar Patro

Erschienen in: Wireless Networks | Ausgabe 6/2010

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In wireless multi-hop and ad-hoc networks, minimizing power consumption and at the same time maintaining desired properties of the network topology is of prime importance. In this work, we present a distributed algorithm for assigning minimum possible power to all the nodes in a static wireless network such that the resultant network topology is k-connected. In this algorithm, a node collects the location and maximum power information from all nodes in its vicinity, and then adjusts the power of these nodes in such a way that it can reach all of them through k optimal vertex-disjoint paths. The algorithm ensures k-connectivity in the final topology provided the topology induced when all nodes transmit with their maximum power is k-connected. We extend our topology control algorithm from static networks to networks having mobile nodes. We present proof of correctness for our algorithm for both static and mobile scenarios, and through extensive simulation we present its behavior.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Literatur
1.
Zurück zum Zitat Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. Communications Magazine, IEEE, 40(8), 102–114.CrossRef Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. Communications Magazine, IEEE, 40(8), 102–114.CrossRef
2.
Zurück zum Zitat Li, L., & Halpern, J. Y. (2004). A minimum-energy path-preserving topology control algorithm. IEEE Transaction on Wireless Communication, 3(3), 910–921.CrossRef Li, L., & Halpern, J. Y. (2004). A minimum-energy path-preserving topology control algorithm. IEEE Transaction on Wireless Communication, 3(3), 910–921.CrossRef
3.
Zurück zum Zitat Li, L., Halpern, J., Bahl, V., Wang, Y., & Wattenhofer, R. (2001). Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks. In Proc. ACM Symposium on Principle of Distributed Computing (PODC), pp. 264–273. Li, L., Halpern, J., Bahl, V., Wang, Y., & Wattenhofer, R. (2001). Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks. In Proc. ACM Symposium on Principle of Distributed Computing (PODC), pp. 264–273.
4.
Zurück zum Zitat Li, N., Hou, J. C., & Sha, L. (2005). Design and analysis of an MST-based topology control algorithm. IEEE Transactions on Wireless Communication, 4(3), 1195–1206. Li, N., Hou, J. C., & Sha, L. (2005). Design and analysis of an MST-based topology control algorithm. IEEE Transactions on Wireless Communication, 4(3), 1195–1206.
5.
Zurück zum Zitat Liu, J., & Li, B. (2003). Distributed topology control in wireless sensor networks with asymmetric links. In Proc. IEEE GLOBECOM, pp. 1257–1262. Liu, J., & Li, B. (2003). Distributed topology control in wireless sensor networks with asymmetric links. In Proc. IEEE GLOBECOM, pp. 1257–1262.
6.
Zurück zum Zitat Li, N., & Hou, J. C. (2004). Topology control in heterogeneous wireless networks: Problems and solutions. In Proc. IEEE INFOCOM, pp. 243–254. Li, N., & Hou, J. C. (2004). Topology control in heterogeneous wireless networks: Problems and solutions. In Proc. IEEE INFOCOM, pp. 243–254.
7.
Zurück zum Zitat Pearlman, M., Hass, Z., & Manvell, B. (2000). Using multi-hop acknowledgements to discover and reliably communicate over unidirectional links in ad hoc networks. In Proc. Wireless Communications and Networking Conference (WCNC), pp. 532–537. Pearlman, M., Hass, Z., & Manvell, B. (2000). Using multi-hop acknowledgements to discover and reliably communicate over unidirectional links in ad hoc networks. In Proc. Wireless Communications and Networking Conference (WCNC), pp. 532–537.
8.
Zurück zum Zitat Bao, L., & Garcia-Luna-Aceves, J. (2001). Channel access scheduling in ad hoc networks with unidirectional links. In Proc. Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 9–18. Bao, L., & Garcia-Luna-Aceves, J. (2001). Channel access scheduling in ad hoc networks with unidirectional links. In Proc. Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 9–18.
9.
Zurück zum Zitat Kim, D., Toh, C., & Choi, Y. (2001). On supporting link asymmetry in mobile ad hoc networks. In Proc. IEEE GLOBECOM, pp. 2798–2803. Kim, D., Toh, C., & Choi, Y. (2001). On supporting link asymmetry in mobile ad hoc networks. In Proc. IEEE GLOBECOM, pp. 2798–2803.
10.
Zurück zum Zitat Prakash, R. (2001). A routing algorithm for wireless ad hoc networks with unidirectional links. ACM/Kluwer Wireless Network, 7(6), 617–625.MATHCrossRef Prakash, R. (2001). A routing algorithm for wireless ad hoc networks with unidirectional links. ACM/Kluwer Wireless Network, 7(6), 617–625.MATHCrossRef
11.
Zurück zum Zitat Ramasubramanian, V., Chandra, R., & Mosse, D. (2002). Providing a bidirectional abstraction for unidirectional ad hoc networks. In Proc. IEEE INFOCOM, pp. 1258–1267. Ramasubramanian, V., Chandra, R., & Mosse, D. (2002). Providing a bidirectional abstraction for unidirectional ad hoc networks. In Proc. IEEE INFOCOM, pp. 1258–1267.
12.
Zurück zum Zitat Marina, M., & Das, S. (2002). Routing performance in the presence of unidirectional links in multi-hop wireless networks. In Proc. ACM Mobihoc, pp. 12–23. Marina, M., & Das, S. (2002). Routing performance in the presence of unidirectional links in multi-hop wireless networks. In Proc. ACM Mobihoc, pp. 12–23.
13.
Zurück zum Zitat Hajiaghayi, M. T., Immorlica, N., & Mirrokni, V. S. (2007). Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. IEEE/ACM Transactions on Networking, 15(6), 1345–1358. Hajiaghayi, M. T., Immorlica, N., & Mirrokni, V. S. (2007). Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. IEEE/ACM Transactions on Networking, 15(6), 1345–1358.
14.
Zurück zum Zitat Wieselthier, J. E., Nguyen, G. D., & Ephremides, A. (2000). On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proc. IEEE INFOCOM, pp. 585–594. Wieselthier, J. E., Nguyen, G. D., & Ephremides, A. (2000). On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proc. IEEE INFOCOM, pp. 585–594.
15.
Zurück zum Zitat Srinivas, A., & Modiano, E. (2003). Minimum energy disjoint path routing in wireless ad-hoc networks. In Proc. ACM MobiCom, pp. 122–133. Srinivas, A., & Modiano, E. (2003). Minimum energy disjoint path routing in wireless ad-hoc networks. In Proc. ACM MobiCom, pp. 122–133.
16.
Zurück zum Zitat Bahramgiri, M., Hajiaghayi, M. T., & Mirrokni, V. S. (2006). Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. Wireless Networks, 8, 179–188.CrossRef Bahramgiri, M., Hajiaghayi, M. T., & Mirrokni, V. S. (2006). Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. Wireless Networks, 8, 179–188.CrossRef
17.
Zurück zum Zitat Clementi, A., Penna, P., & Silvestri, R. (1999). Hardness results for the power range assignment problem in packet radio networks. In Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 197–208. Clementi, A., Penna, P., & Silvestri, R. (1999). Hardness results for the power range assignment problem in packet radio networks. In Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 197–208.
18.
Zurück zum Zitat Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys, 37(2), 164–194.CrossRef Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys, 37(2), 164–194.CrossRef
19.
Zurück zum Zitat Shen, C. C., Srisathapornphat, C., Liu, R., Huang, Z., Jaikaeo, C., & Lloyd, E. L. (2004). CLTC: A cluster-based topology control framework for ad hoc networks. IEEE Transactions on Mobile Computing, 3(1), 18–32.CrossRef Shen, C. C., Srisathapornphat, C., Liu, R., Huang, Z., Jaikaeo, C., & Lloyd, E. L. (2004). CLTC: A cluster-based topology control framework for ad hoc networks. IEEE Transactions on Mobile Computing, 3(1), 18–32.CrossRef
20.
Zurück zum Zitat Chen, Y., & Son, S. H. (2005). A fault tolerant topology control in wireless sensor networks. In Proc. 3rd ACS/IEEE International Conference on Computer Systems and Applications, pp. 57–64. Chen, Y., & Son, S. H. (2005). A fault tolerant topology control in wireless sensor networks. In Proc. 3rd ACS/IEEE International Conference on Computer Systems and Applications, pp. 57–64.
21.
Zurück zum Zitat Li, N., & Hou, J. C. (2004). FLSS: A fault-tolerant topology control algorithm for wireless networks. In Proc. ACM MobiCom, pp. 275–286. Li, N., & Hou, J. C. (2004). FLSS: A fault-tolerant topology control algorithm for wireless networks. In Proc. ACM MobiCom, pp. 275–286.
22.
Zurück zum Zitat Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms (2nd ed.). Cambridge, MA, USA: MIT Press.MATH Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms (2nd ed.). Cambridge, MA, USA: MIT Press.MATH
Metadaten
Titel
Distributed fault-tolerant topology control in wireless multi-hop networks
verfasst von
Indranil Saha
Lokesh Kumar Sambasivan
Subhas Kumar Ghosh
Ranjeet Kumar Patro
Publikationsdatum
01.08.2010
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 6/2010
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-008-0133-2

Weitere Artikel der Ausgabe 6/2010

Wireless Networks 6/2010 Zur Ausgabe

Neuer Inhalt