An approximation algorithm for the wireless gathering problem. (English) Zbl 1210.90035
Summary: The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Akyildiz, I. F.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E., Wireless sensor networks: A survey, Computer Networks, 38, 4, 393-422 (2002) |
| [2] | Bar-Yehuda, R.; Israeli, A.; Itai, A., Multiple communication in multihop radio networks, SIAM Journal on Computing, 22, 4, 875-887 (1993) · Zbl 0774.68013 |
| [3] | Bermond, J.-C.; Galtier, J.; Klasing, R.; Morales, N.; Pérennes, S., Hardness and approximation of gathering in static radio networks, Parallel Processing Letters, 16, 2, 165-183 (2006) |
| [4] | J.-C. Bermond, R.C. Corrêa, M.-L. Yu, Gathering algorithms on paths under interference constraints, in: Proc. 6th Italian Conf. on Algorithms and Complexity, 2006, pp. 115-126; J.-C. Bermond, R.C. Corrêa, M.-L. Yu, Gathering algorithms on paths under interference constraints, in: Proc. 6th Italian Conf. on Algorithms and Complexity, 2006, pp. 115-126 · Zbl 1183.90085 |
| [5] | Bermond, J.-C.; Galtier, J.; Klasing, R.; Morales, N.; Pérennes, S., Gathering in specific radio networks, (Huitièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (2006), Trégastel: Trégastel France), 85-88 |
| [6] | Haenggi, M., Opportunities and challenges in wireless sensor networks, (Handbook of Sensor Networks: Compact Wireless and Wired Sensing Systems (2004), CRC Press: CRC Press Boca Raton) |
| [7] | V.S. Anil Kumar, M.V. Marathe, S. Parthasarathy, A. Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, in: J.I. Munro (Ed.), Proc. 15th Symp. on Discrete Algorithms, 2004, pp. 1021-1030; V.S. Anil Kumar, M.V. Marathe, S. Parthasarathy, A. Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, in: J.I. Munro (Ed.), Proc. 15th Symp. on Discrete Algorithms, 2004, pp. 1021-1030 · Zbl 1318.68063 |
| [8] | Pahlavan, K.; Levesque, A. H., Wireless Information Networks (1995), Wiley: Wiley New York |
| [9] | Perkins, C. E., Ad Hoc Networking (2001), Addison-Wesley: Addison-Wesley Boston |
| [10] | Tanenbaum, A. S., Computer Networks (2003), Prentice Hall |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
