کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415705 681227 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Connectivity guarantees for wireless networks with directional antennas
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Connectivity guarantees for wireless networks with directional antennas
چکیده انگلیسی

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 PP 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∈Pp,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°α=60°, then it is always possible to adjust the wedges so that G   is connected, and that α⩾60°α⩾60° 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 PP.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°α=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ε>0, there exist sets of points such that G   cannot contain a Hamiltonian path if α=90°−εα=90°−ε.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 44, Issue 9, November 2011, Pages 477–485
نویسندگان
, , , ,