Title
Connectivity guarantees for wireless networks with directional antennas
Abstract
We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible. We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an @a-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,q@?P are connected by an edge in G, if and only if q lies in p@?s wedge and p lies in q@?s wedge.) We prove that if @a=60^o, then it is always possible to adjust the wedges so that G is connected, and that @a=60^o is sometimes necessary to achieve this. Our proof is constructive and yields an O(nlogk) time algorithm for adjusting the wedges, where k is the size of the convex hull of P. Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if @a=90^o, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and @e0, there exist sets of points such that G cannot contain a Hamiltonian path if @a=90^o-@e.
Year
DOI
Venue
2011
10.1016/j.comgeo.2011.05.003
Comput. Geom.
Keywords
Field
DocType
n transceivers,points p,communication graph g,wireless network,directional antenna,hamiltonian path,connectivity,directional antennas,wireless networks,a-degree directional antenna,connected communication network,alternative proof,connectivity guarantee,polygonal paths,n point,combinatorial geometric problem,convex hull
Discrete mathematics,Wireless network,Combinatorics,Transceiver,Telecommunications network,Constructive,Hamiltonian path,Wedge (mechanical device),Convex hull,Directional antenna,Mathematics
Journal
Volume
Issue
ISSN
44
9
Computational Geometry: Theory and Applications
Citations 
PageRank 
References 
20
0.99
13
Authors
4
Name
Order
Citations
PageRank
Paz Carmi132143.14
Matthew J. Katz222519.92
Zvi Lotker3100079.68
Adi Rosén476859.38