Connectivity with directional antennas in the symmetric communication model
Connectivity with directional antennas in the symmetric communication model
复制标题
DOI：
10.1016/j.comgeo.2016.03.002
复制
发表时间：
2016-05-01
影响因子：
0.6
通讯作者：
Stacho, L.
中科院分区：
文献类型：
--
作者：
Dobrev, S.;Eftekhari, M.;Stacho, L.
我们研究了无线网络中每个节点使用单个定向天线的连通性问题。我们考虑了带有定向天线的对称通信模型。在该模型中，当且仅当两个节点位于对方天线的传输扇区时，它们之间通过链路连接。给定平面上的节点，每个节点都有一个波束宽度为phi，半径为r的天线，我们研究天线定向的问题，以便创建一个连接的网络。我们证明了对于< pi/3和给定的半径，确定一个确保连通网络是np完全的方向的存在性问题。对于phi >= pi/2，在这种情况下，连通性总是可能的，我们研究了在最小化半径的同时实现连通性的问题。对于不同范围的phi，我们给出了近似算法，在使用最多为最优半径的常数倍的半径时实现连通性。与具有给定半径的全向天线的节点网络相比，我们的一些算法在所得网络的拉伸因子上也具有可证明的界限。(C) 2016 Elsevier B.V.版权所有
We study the problem of connectivity in wireless networks in which each node uses a single directional antenna. We consider the symmetric model of communication with directional antennas. In this model, two nodes are connected by a link if and only if they lie in the transmission sectors of each other's antenna. Given nodes located in the plane, each with an antenna of beamwidth phi and radius r, we study the problem of orienting the antennas in such a way as to create a connected network. We show that for phi < pi/3 and a given radius, the problem of determining the existence of an orientation that ensures a connected network is NP-complete. For phi >= pi/2, in which case connectivity is known to be always possible, we study the problem of achieving connectivity while minimizing the radius. For different ranges of phi, we give approximation algorithms that achieve connectivity while using a radius that is at most a constant times the optimal radius. Some of our algorithms also have provable bounds on the stretch factor of the resulting network compared to a network of nodes with omnidirectional antennas of a given radius. (C) 2016 Elsevier B.V. All rights reserved.