Connectivity guarantees for wireless networks with directional antennas |
| |
Authors: | Paz Carmi,Matthew J. Katz,Zvi Lotker,Adi Rosé n |
| |
Affiliation: | aDepartment of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel;bDepartment of Communication Systems Engineering, Ben-Gurion University, Beer-Sheva 84105, Israel;cCNRS and University of Paris 11, Laboratoire de Recherche en Informatique (LRI), Bât. 490 Université Paris-Sud, 91405 Orsay, France |
| |
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 α-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 α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an 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 α=90°, 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 ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε. |
| |
Keywords: | Wireless networks Directional antennas Connectivity Polygonal paths |
本文献已被 ScienceDirect 等数据库收录! |
|