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 2/2013

01.02.2013

Cooperative data collection in ad hoc networks

verfasst von: Liron Levin, Michael Segal, Hanan Shpungin

Erschienen in: Wireless Networks | Ausgabe 2/2013

Einloggen

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

search-config
loading …

Abstract

This paper studies the problem of data gathering in multi-hop wireless ad hoc networks. In this scenario, a set of wireless devices constantly sample their surroundings and initiate report messages addressed to the base station. The messages are forwarded in a multi-hop fashion, where the wireless devices act both as senders and relays. We consider data gathering without aggregation, i.e. the nodes are required to forward all the messages initiated by other nodes (in addition to their own) to the base station. This is in contrast to the well studied problem of data gathering with aggregation, which is significantly simpler. As some nodes experience a larger load of forward requests, these nodes will have their battery charges depleted much faster than the other nodes—which can rapidly break the connectivity of the network. We focus on maximizing the network lifetime through efficient balancing of the consumed transmission energy. We show that the problem is NP-hard for two network types and develop various approximation schemes. Our results are validated through extensive simulations.
Vorheriger Artikel Admission control for cellular networks with direct QoS monitoring
Nächster Artikel Directional routing and scheduling for green vehicular delay tolerant networks

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
Fußnoten
1
The homogeneous model is better known as the UDG model [2].
 
Literatur
1.
Bermond, J. C., Nisse, N., Reyes, P., & Rivano, H. (2009). Fast data gathering in radio grid networks. In AlgoTel’09, pp. 53–56.
2.
Buragohain, C., Agrawal, D., & Suri, S. (2005). Power aware routing for sensor databases. In INFOCOM 2005, pp. 1747–1757.
3.
Chehri, A., Fortier, P., & Tardif, P.-M. (2007). Security monitoring using wireless sensor networks. Communication Networks and Services Research, Annual Conference on, 0, 13–17.
4.
Chen, J., Kleinberg, R. D., Lovász, L., Rajaraman, R., Sundaram, R., & Vetta, A. (2007). (almost) tight bounds and existence theorems for single-commodity confluent flows. J ACM, 54, July 2007.
5.
Chen, T.-S., Tsai, H.-W., & Chu, C.-P. (2006). Gathering-load-balanced tree protocol for wireless sensor networks. pp. 8–13.
6.
Chintalapudi, K., Fu, T., Paek, J., Kothari, N., Rangwala, S., Caffrey, J. et al. (2006). Monitoring civil structures with a wireless sensor network. IEEE Internet Computing, 10(2), 26–34.CrossRef
7.
Ciullo, D., Celik, G. D., & Modiano, E. (2010). Minimizing transmission energy in sensor networks via trajectory control. In WiOpt’10: Modeling and optimization in mobile, ad hoc, and wireless networks, pp. 259–268.
8.
9.
Fortune, S. Hopcroft, J. E., & Wyllie, J. C. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10, 111–121.MathSciNetMATHCrossRef
10.
Gallager, R. G., Humblet, P. A., & Spira, P. M. (1983). A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems, 5, 66–77.MATHCrossRef
11.
Garey, M. R., & Johnson, D. S. (1990). Computers and intractability; A guide to the theory of NP-completeness. New York, NY: W. H. Freeman & Co.
12.
Gehrke, J., & Madden, S. (2004). Query processing in sensor networks. IEEE Pervasive Computing, 3(1), 46–55.
13.
Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., & Yannakakis, M. (2003). Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3), 473–496.MathSciNetMATHCrossRef
14.
Hekmat, R., & Van Mieghem, P. (2006). Connectivity in wireless ad-hoc networks with a log-normal radio model. Mobile Network Applications, 11, 351–360.CrossRef
15.
Hoebeke, J., Moerman, I., Dhoedt, B., & Demeester, P. (2004). An overview of mobile ad hoc networks: Applications and challenges. Journal of the Communications Network, 3, 60–66.
16.
Wei, H.-y., & Gitlin, R. D. (2004). Two-hop-relay architecture for next generation wwan/wlan integration. IEEE Wireless Communications (Special Issue on 4G Mobile Communications-Towards Open Wireless Architecture), 11, 24–30.
17.
Kalpakis, K., Dasgupta, K., & Namjoshi, P. (2003). Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Computer Networks, 42, 697–716.MATHCrossRef
18.
King, V., Rao, S., & Tarjan, R. (1992). A faster deterministic maximum flow algorithm, pp. 157–164.
19.
Kolchin, V. F., Sevastianov, B. A., & Chistiakov, V. P. (1978). Random allocations. Washington, New York: V. H. Winston; (distributed solely by Halsted Press).
20.
Kulik, J., Heinzelman, W., & Balakrishnan, H. (2002). Negotiation-based protocols for disseminating information in wireless sensor networks. Wireless Networks, 8, 169–185.MATHCrossRef
21.
Lenstra, J. K., Shmoys, D. B., & Tardos, É. (1990). Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46(3), 259–271.MathSciNetMATHCrossRef
22.
Lessmann, J., & Krishnamurthy, A. (2007). Parameterized hierarchical layer topology construction for wireless networks. In ICSNC ’07: Proceedings of the second international conference on systems and networks communications, p. 15. IEEE Computer Society.
23.
Levin, L., Segal, M., & Shpungin, H. (2010). Optimizing performance of ad-hoc networks under energy and scheduling constraints. In WiOpt’10: Modeling and optimization in mobile, ad hoc, and wireless networks, pp. 110–119.
24.
Liang, J., Wang, J., Cao, J., Chen, J., & Lu, M. (2010) An efficient algorithm for constructing maximum lifetime tree for data gathering without aggregation in wireless sensor networks. In Proceedings of the 29th conference on Information communications, INFOCOM’10 (pp. 506–510). New York: IEEE Press.
25.
Lin, C.-S., Huang, C.-N., & Fang, R.-J. (2008) A power-efficient data gathering scheme on grid sensor networks. In Proceedings of the 8th WSEAS international conference on multimedia systems and signal processing, pp. 142–147. World Scientific and Engineering Academy and Society (WSEAS).
26.
Liu, A.-F., Wu, X.-Y., Chen, Z.-G., & Gui, W.-H. (2010). An energy-balanced data gathering algorithm for linear wireless sensor networks. International Journal of Wireless Information Networks, 17, 42–53.CrossRef
27.
Liu, Y. (2007). Online data gathering for maximizing network lifetime in sensor networks. IEEE Transactions on Mobile Computing, 6(1), 2–11.CrossRef
28.
Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., & Anderson, J. (2002). Wireless sensor networks for habitat monitoring. In WSNA ’02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 88–97.
29.
Mhatre, V., & Rosenberg, C. (2004). Homogeneous vs. heterogeneous clustered sensor networks: A comparative study. In In Proceedings of 2004 IEEE international conference on communications (ICC 2004, pp. 3646–3651.
30.
Pahlavan, K., & Levesque, A. H. (1995). Wireless Information Networks.
31.
Segal, M. (2008). Fast algorithm for multicast and data gathering in wireless networks. Information Processing Letters, 107(1), 29–33.MathSciNetMATHCrossRef
32.
Segal, M., & Shpungin, H. (2009). On construction of minimum energy k-fault resistant topologies. Ad Hoc Networks, 7(2), 363–373.CrossRef
33.
Shpungin, H., & Segal, M. (2009). Near optimal multicriteria spanner constructions in wireless ad-hoc networks. IEEE/ACM Transaction on Networking.
34.
Stanford, J., & Tongngam, S. (1998). Approximation algorithm for maximum lifetime in wireless sensor networks with data aggregation. In FOCS 1998, pp. 300–309.
35.
Stoumpos, V., Deligiannakis, A., Kotidis, Y., & Delis, A. (2008). Processing event-monitoring queries in sensor networks. In Proceedings of the 2008 IEEE 24th international conference on data engineering, pp. 1436–1438. IEEE Computer Society.
36.
Sundaresan, K., & Rangarajan, S. (2008). On exploiting diversity and spatial reuse in relay-enabled wireless networks. pp. 13–22.
37.
Woo, A., Tong, T., & Culler, D. (2003). Taming the underlying challenges of reliable multihop routing in sensor networks. In SenSys ’03: Proceedings of the 1st international conference on Embedded networked sensor systems (pp. 14–27). New York, NY: ACM.
38.
Wu, Y., Fahmy, S., & Shroff, N. B. (2008). On the construction of a maximum-lifetime data gathering tree in sensor networks: Np-completeness and approximation algorithm. In INFOCOM (pp. 356–360).
39.
Zhang, H., Shen, H., & Tian, H. (2006). Reliable and real-time data gathering in multi-hop linear wireless sensor networks. In Cheng, X., Li, W., Znati, T. (Eds.), Wireless algorithms, systems, and applications, volume 4138 of lecture notes in computer science (pp. 151–162). Berlin: Springer.
40.
Zhang, L., & Soong, B.-H. (2005). Interference distribution in the Nakagami fading wireless CDMA ad hoc networks with multi-code multi-packet transmission (MCMPT). In 30th annual IEEE conference on local computer networks (LCN 2005), 15–17 November 2005, Sydney, Australia, Proceedings. IEEE Computer Society.
Metadaten
Titel
Cooperative data collection in ad hoc networks
verfasst von
Liron Levin
Michael Segal
Hanan Shpungin
Publikationsdatum
01.02.2013
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 2/2013
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-012-0456-x

Weitere Artikel der Ausgabe 2/2013

Wireless Networks 2/2013 Zur Ausgabe

OriginalPaper

The impact of network topology on delay bound in wireless Ad Hoc networks

OriginalPaper

Utility-based admission control for mobile WiMAX networks

OriginalPaper

Novel adaptive collaboration sensing for efficient acquisition of spectrum opportunities in cognitive radio networks

OriginalPaper

Admission control for cellular networks with direct QoS monitoring

OriginalPaper

Effective channel control random beamforming for single user MIMO systems

OriginalPaper

Design and analysis of an IEEE 802.21-based mobility management architecture: a context-aware approach

Neuer Inhalt

    Bildnachweise