Communication in wireless networks with directional antennas

ABSTRACT

We study the problem of maintaining connectivity in a wireless network where the network nodes are equipped with directional antennas. Nodes correspond to points on the plane and each uses a directional antenna modeled by a sector with a given angle and radius. The connectivity problem is to decide whether or not it is possible to orient the antennas so that the directed graph induced by the node transmissions is strongly connected. We present algorithms for simple polynomial-time-solvable cases of the problem, show that the problem is NP-complete in the $2$-dimensional case when the sector angle is small, and present algorithms that approximate the minimum radius to achieve connectivity for sectors with a given angle. We also discuss several extensions to related problems. To the best of our knowledge, the problem has not been studied before in the literature.

REFERENCES

• 1: Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos, Energy-Efficient Wireless Network Design, Theory of Computing Systems, v.39 n.5, p.593-617, September 2006 [doi>10.1007/s00224-005-1204-8]
• 2: Andrea E. F. Clementi , Pierluigi Crescenzi , Paolo Penna , Gianluca Rossi , Paola Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.121-131, February 15-17, 2001
• 3: L. Hu and D. Evans. Using directional antennas to prevent wormhole attacks, In Proceedings of the 11th Annual Network and Distributed System Security Symposium (NDSS'03), 2003
• 4: C. Hu, Y. Hong, and J. Hou. On mitigating the broadcast storm problem with directional antennas. In Proceedings of IEEE International Conference on Communications (ICC'03), Vol. 1, pp. 104--110, 2003.
• 5: Z. Huang, C.-C. Shen, C. Srisathapornphat, and C. Jaikaeo. Topology control for ad hoc networks with directional antennas. In Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (ICCCN'02), pp. 16--21, 2002.
• 6: A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton Paths in Grid Graphs. SIAM Journal on Computing, Vol. 11(4), pp. 676--686, 1982.
• 7: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 8: E. Kranakis, D. Krizanc, and J. Urrutia. Coverage and connectivity in networks with directional sensors. In Proceedings of the 10th International Euro-Par Conference (Euro-par'04), LNCS 3149, Springer, pp. 917--924, 2004.
• 9: E. Kranakis, D. Krizanc, and E. Williams. Directional versus omnidirectional antennas for energy consumption and k-connectivity of networks of sensors. In Proceedings of the 8th International Conference onPrinciples of Distributed Systems (OPODIS'04), LNCS 3544, Springer, pp. 357--368, 2004.
• 10: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 11: Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.19-34, February 2005 [doi>10.1145/1046430.1046433]
• 12: Friedhelm Meyer auf der Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Congestion, Dilation, and Energy in Radio Networks, Theory of Computing Systems, v.37 n.3, p.343-370, May 2004 [doi>10.1007/s00224-004-1124-z]
• 13: A. Nasipuri, K. Li and U. Sappidi. Power consumption and throughput in Mobile Ad Hoc Networks using Directional Antennas. IEEE International Conference on Computer Communication and Networks, Miami, FL, Oct 2002.
• 14: T. Ohira and K. Gyoda. Electronically Steerable Passive Array Radiator Antennas for Low-cost Adaptive Beam Forming. IEEE International Conference on Phased Array Systems, Dana Point, CA, May 2000.
• 15: Ram Ramanathan, On the performance of ad hoc networks with beamforming antennas, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501430]
• 16: Siuli Roy , Dola Saha , S. Bandyopadhyay , Tetsuro Ueda , Shinsuke Tanaka, A network-aware MAC and routing protocol for effective load balancing in ad hoc wireless networks with directional antenna, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778427]
• 17: M. Sekanina. On the ordering of the set of vertices of a connected graph. Publications of the Faculty of Sciences, University of Brno, Vol. 412, pp. 137--142, 1960.
• 18: T. S. Yum and K. W. Hung. Design algorithms for multihop packet radio networks with multiple directionalantennas. IEEE Trans. on Communications, vol. 40, pp. 1716--1724, 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
connectivity, directional antennas, wireless networks