Efficient broadcasting in known topology radio networks with long-range interference

ABSTRACT

We study broadcasting (one-to-all communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance d_I. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on limited number of transmissions at each node.

In what follows we assume that n stands for the number of nodes, D_T is the diameter of the subnetwork induced by the transmission edges, and Δ refers to the maximum combined degree formed of transmission and interference edges) of the network. We contribute the following new results:

(1) We prove that even for networks with the interference distance d_I = 2 any broadcasting schedule requires at least D_T + Ω(Δ ∙ log n/log Δ) rounds.

(2) We also provide for networks modeled by bipartite graphs an algorithm that computes 1-shot (each node is allowed to transmit at most once) broadcasting schedules of length O(Δ ∙ log n).

Note that in this case the length of the broadcasting schedule is independent of the interference distance of the network.

(3) The main result of the paper is an algorithm that computes a 1-shot broadcasting schedule of length at most 4 ∙ D_T + O(Δ ∙ d_I ∙ log⁴ n) for networks with arbitrary topology.

Note that in view of the lower bound from (1) the broadcast schedule is almost optimal for d_I polylogarithmic in n. Note also that by applying our algorithm to radio networks with no interference edges the time of the broadcasting schedule from [10] is improved in graphs with Δ = o(√n/log⁴ n).

The 1-shot broadcasting algorithm proposed in [10] relies heavily on the concept of internal ranks that impose currently an Ω(√n)-time bottleneck in the broadcasting schedule.

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: Petra Berenbrink , Zengjian Hu , Colin Cooper, Energy efficient randomised communication in unknown AdHoc networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248419]
• 3: J.-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Perennes. Hardness and approximation of gathering in static radionetworks. Parallel Processing Letters 16, 2006, pp. 165--184.
• 4: I. Chlamtac and S. Kutten. On broadcasting in radio networks--problem analysis and protocol design. IEEE Transactions on Communications 33, 1985, pp. 1240--1246.
• 5: I. Chlamtac and S. Kutten. The wave expansion approach to broadcasting in multihop radio networks. IEEE Transactions on Communications 39, 1991, pp. 426--433.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: Michael Elkin , Guy Kortsarz, Improved schedule for radio broadcast, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Iris Gaber , Yishay Mansour, Centralized broadcast in multihop radio networks, Journal of Algorithms, v.46 n.1, p.1-20, January 2003 [doi>10.1016/S0196-6774(02)00292-4]
• 9: František Galčík, Centralized Communication in Radio Networks with Strong Interference, Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, June 17-20, 2008, Villars-sur-Ollon, Switzerland [doi>10.1007/978-3-540-69355-0_23]
• 10: L. Gąsieniec, E. Kantor, D. Kowalski, D. Peleg, and Ch. Su. Time efficient k-shot broadcasting in known topology radio networks. Distributed Computing 21 (2008), pp. 117--127.
• 11: Leszek Gasieniec , David Peleg , Qin Xin, Faster communication in known topology radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073840]
• 12: Olga Goussevskaia , Thomas Moscibroda , Roger Wattenhofer, Local broadcasting in the physical interference model, Proceedings of the fifth international workshop on Foundations of mobile computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400863.1400873]
• 13: P. Gupta and P.R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory 46(2), 2000, pp. 388--404.
• 14: D. Kowalski and A. Pelc. Centralized deterministic broadcasting in undirected multi-hop radio networks. In Proc. APPROX, LNCS 3122, 2004, pp. 171--182.
• 15: Dariusz R. Kowalski , Andrzej Pelc, Optimal deterministic broadcasting in known topology radio networks, Distributed Computing, v.19 n.3, p.185-195, January 2007 [doi>10.1007/s00446-006-0007-8]
• 16: T. Muetze, P. Stuedi, F. Kuhn, and G. Alonso. Understanding Radio Irregularity in Wireless Networks. In Proc. SECON'08, 2008, pp. 82--90.
• 17: Melih Onus , Andrea Richa , Kishore Kothapalli , Christian Scheideler, Efficient Broadcasting and Gathering in Wireless Ad-Hoc Networks, Proceedings of the 8th International Symposium on Parallel Architectures,Algorithms and Networks, p.346-351, December 07-09, 2005 [doi>10.1109/ISPAN.2005.43]
• 18: D. Peleg. Time-Efficient Broadcasting in Radio Networks: A Review. In Proc. ICDCIT 2007, LNCS 4882, 2007, pp. 1--18.
• 19: Andrzej Pelc, Broadcasting in radio networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 20: D. Welsh and M. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal 10 (1), 1967, pp. 85--86.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory

Keywords:
broadcasting, long-range interference, radio networks