Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 3/2015

01.04.2015

An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks

verfasst von: Namsu Ahn, Sungsoo Park

Erschienen in: Wireless Networks | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

In wireless sensor networks (WSNs), virtual backbone has been proposed as the routing infra-structure and connected dominating set has been widely adopted as virtual backbone. However, since the sensors in WSNs are prone to failures, recent studies suggest that it is also important to maintain a certain degree of redundancy in the backbone. To construct a robust backbone, so called k-connected m-dominating set has been proposed. In this research, we propose an integer programming formulation and an optimal algorithm for the minimum k-connected m-dominating set problem. To the best of our knowledge, this is the first integer programming formulation for the problem, and extensive computational results show that our optimal algorithm is capable of finding a solution within a reasonable amount of time.
Vorheriger Artikel Videocent: a quality-oriented incentive mechanism for video delivery in opportunistic networks
Nächster Artikel An energy management method of sensor nodes for environmental monitoring in Amazonian Basin

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
1.
Alzoubi, K. M., Wan, P. J., & Frieder, O. (2002). Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on mobile ad hoc networking and computing (pp. 157–164). ACM, Lausanne, Switzerland.
2.
Basu, P., & Redi, J. (2004). Movement control algorithms for realization of fault tolerant ad hoc robot networks. IEEE Networks, 18, 36–44.CrossRef
3.
Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization. Belmont: Athena Scientific.
4.
Blum, J., Ding, M., Thaeler, A., & Cheng, X. (2004). Connected dominating set in sensor networks and MANETs, handbook of combinatorial optimization. Massachusetts: Kluwer Acacemic Publishers.
5.
Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Berlin: Springer.MATH
6.
Bredin, J. L., Demaine, E. D., Hajiaghayi, M., & Rus, D. (2005). Deploying sensor networks with guaranteed capacity and fault tolerance. In Proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing (pp. 309–319). ACM SIGMOBILE, Urbana-Champaign, Illinois.
7.
Dai, F., & Wu, J. (2006). On constructing k-connected k-dominating set in wireless network. Journal of Parallel and Distributed Computing, 66, 947–958.CrossRefMATH
8.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W. H. Freeman and Company.MATH
9.
10.
Grotschel, M., Lovasz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197.CrossRefMathSciNet
11.
Kim, D., Wang, W., Li, X., Zhang, Z., & Wu, W. (2010). A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks. In INFOCOM, IEEE (pp. 1–9). San Diego, CA.
12.
Koskinen, H., & Karvo, J. (2005). On improving connectivity of static ad-hoc networks by adding nodes, 4th annual Mediterranean workshop on ad hoc network. IEEE Communications Society (pp. 169–178). Porquerolles, France.
13.
Kuhn, F., Moscibroda, T., & Wattenhofer, R. (2006). Fault-tolerant clustering in ad hoc and sensor networks. In 26th international conference on distributed computing systems. IEEE Computer Society, Lisboa, Portugal.
14.
Li, Y., Wu, Y., Ai, C., & Neyah, R. (2012). On the construction of k-connected m-dominating sets in wireless networks. Journal of Combinatorial Optimization, 23, 118–139.CrossRefMATHMathSciNet
15.
Ni, S. Y., Tseng, Y. C., Chen, Y. S., & Sheu, J. P. (2002). The broadcast storm problem in a mobile ad hoc network. Wireless Networks, 8, 153–167.CrossRefMATH
16.
Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial pptimization. Mineola, NY: Dover Publications.MATH
17.
Ryl, D. S., Stojmenović, I., & Wu, J. (2005). Energy-efficient backbone construction, broadcasting, and area coverage in sensor networks. In I. Stojmenović (Ed.), Handbook of sensor networks (pp. 343–380). Hoboken: Wiley.
18.
Shang, W., Yao, F., Wan, P., & Hu, X. (2007). Algorithms for minimum m-connected k-dominating set problem. Lecture Notes in Computer Science, 4616, 182–190.CrossRefMathSciNet
19.
Shang, W., Yao, F., Wan, P., & Hu, X. (2008). On minimum m-connected k-dominating set problem in unit disc graphs. Journal of Combinatorial Optimization, 16, 99–106.CrossRefMATHMathSciNet
20.
Sinha, P., Sivakumar, R., & Bharghavan, V. (2001). Enhancing ad hoc routing with dynamic virtual infrastructures. IN 20th annual joint conference of the IEEE computer and communications societies. Technical Committees on Computer Communications (TCCC) of the Societies (Vol. 3, pp. 1763–1772). Anchorage, Alaska.
21.
Stojmenović, I., & Wu, J. (2005). Mobile ad hoc networking. Hoboken: Wiley
22.
Tarjan, R. E. (1972). Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
23.
Thai, M. T., Zhang, N., Tiwari, R., & Xu, X. (2007). On approximation algorithms of k-connected m-dominating sets in disk graphs. Theory of Computation Sc, 385, 49–59.CrossRefMATHMathSciNet
24.
Thulasiraman, K., & Swamy, M. N. S. (1992). Graphs: Theory and algorithms. New York: Wiley.MATH
25.
Tiwari, R., & Thai, M. T. (2012). On enhancing fault tolerance of virtual backbone in a wireless sensor network with unidirectional links. Sensors: Theory, Algorithms, and Applications, 61, 3–18.
26.
Wang, F., Thai, M. T., & Du, D. Z. (2009). On the construction of 2-connected virtual backbone in wireless network. IEEE Transactions on Wireless Communications, 8, 1230–1237.CrossRef
27.
Wang, W., Kim, D., An, M. K., Gao, W., Li, X., Zhang, Z., & Wu, W. (2012). On construction of quality fault-tolerant virtual backbone in wireless networks. Networking, IEEE/ACM Transactions, 21(5), 1499–1510.
28.
West, D. B. (2001). Introduction to graph theory. Upper Saddle River: Prentice-Hall.
29.
Wu, Y., Wang, F., Thai, M. T., & Li, Y. (2007). Constructing k-connected m-dominating sets in wireless sensor networks. In Military communications conference. Orlando, FL.
30.
Wu, Y., & Li, Y. (2008) Construction algorithms for k-connected m-dominating sets in wireless sensor networks. In 9th ACM international symposium on mobile ad hoc networking and computing (pp. 83–90). ACM SIGMOBILE, May, Hong Kong.
31.
Yu, J., Wang, N., Wang, G., & Yu, D. (2013). Connected dominating sets in wireless ad hoc and sensor networks—A comprehensive survey. Computer Communications, 36, 121–134.CrossRef
32.
Zhang, J., Gao, X., & Wu, W. (2009). Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theoretical Computer Science, 410, 812–817.CrossRefMATHMathSciNet
33.
Zhou, J., Zhang, Z., Wu, W., & Xing, K. (2014). A greedy algorithm for the fault-tolerant connected dominating set in a general graph. Journal of Combinatorial Optimization, 28(1), 310–319.
Metadaten
Titel
An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks
verfasst von
Namsu Ahn
Sungsoo Park
Publikationsdatum
01.04.2015
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 3/2015
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-014-0819-6

Weitere Artikel der Ausgabe 3/2015

Wireless Networks 3/2015 Zur Ausgabe

OriginalPaper

Network-layer abstraction and simulation of vehicle communication stack

OriginalPaper

Integrated mobility and resource management for cross-network resource sharing in heterogeneous wireless networks using traffic offload policies

OriginalPaper

Multi-objective network planning optimization algorithm: human exposure, power consumption, cost, and capacity

OriginalPaper

SPEED-MAC: speedy and energy efficient data delivery MAC protocol for real-time sensor network applications

OriginalPaper

A multimedia transmission control algorithm based on cross-layer design in UMTS networks

OriginalPaper

Sleeping mobile AP: a novel energy efficient Wifi tethering scheme

Neuer Inhalt

    Bildnachweise