Top

Wireless Networks

Published in:

01-02-2013

Cooperative data collection in ad hoc networks

Authors: Liron Levin, Michael Segal, Hanan Shpungin

Published in: Wireless Networks | Issue 2/2013

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

search-config

AI-assisted search

Off

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.

previous article Admission control for cellular networks with direct QoS monitoring

next article Directional routing and scheduling for green vehicular delay tolerant networks

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!

inform now

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!

inform now

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!

inform now

The homogeneous model is better known as the UDG model [2].

Bermond, J. C., Nisse, N., Reyes, P., & Rivano, H. (2009). Fast data gathering in radio grid networks. In AlgoTel’09, pp. 53–56.

Buragohain, C., Agrawal, D., & Suri, S. (2005). Power aware routing for sensor databases. In INFOCOM 2005, pp. 1747–1757.

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.

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.

Chen, T.-S., Tsai, H.-W., & Chu, C.-P. (2006). Gathering-load-balanced tree protocol for wireless sensor networks. pp. 8–13.

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

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.

Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399–404.MathSciNetMATHCrossRef

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.

Title: Cooperative data collection in ad hoc networks
Authors: Liron Levin
Michael Segal
Hanan Shpungin
Publication date: 01-02-2013
Publisher: Springer US
Published in: Wireless Networks / Issue 2/2013
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI: https://doi.org/10.1007/s11276-012-0456-x

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2013

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

Directional routing and scheduling for green vehicular delay tolerant networks

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

Utility-based admission control for mobile WiMAX networks

Admission control for cellular networks with direct QoS monitoring

Distributed Hash table-based routing and data management in wireless sensor networks: a survey