Communication in Wireless Networks with Directional Antennas

被引：0

作者：

Caragiannis, Ioannis ^{[1
,2
]}

Kaklamanis, Christos ^{[1
,2
]}

Kranakis, Evangelos ^{[3
]}

Krizanc, Danny ^{[4
]}

Wiese, Andreas ^{[5
]}

机构：

[1] Univ Patras, RACTI, Rion 26500, Greece

[2] Univ Patras, Dept Comp Engn & Informat, Rion 26500, Greece

[3] Carleton Univ, Sch Comp Sci, Ottawa, ON, Canada

[4] Wesleyan Univ, Dept Math & Comp Sci, Middletown, CT 06459 USA

[5] Tech Univ Berlin, Math Inst, Berlin, Germany

来源：

SPAA'08: PROCEEDINGS OF THE TWENTIETH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES | 2008年

关键词：

Wireless networks; directional antennas; connectivity;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：344 / +

页数：3

共 18 条

[1] Energy-efficient wireless network design [J].

Caragiannis, Ioannis ;

Kaklamanis, Christos ;

Kanellopoulos, Panagiotis .

THEORY OF COMPUTING SYSTEMS, 2006, 39 (05) :593-617

[2]

Clementi A, 2001, LNCS, V2001, P121

[3]

Hu CY, 2003, 2003 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-5, P104

[4]

HU L, 2003, P 11 ANN NETW DISTR

[5]

HUANG Z, P 11 IEEE INT C COMP, P16

[6] HAMILTON PATHS IN GRID GRAPHS [J].

ITAI, A ;

PAPADIMITRIOU, CH ;

SZWARCFITER, JL .

SIAM JOURNAL ON COMPUTING, 1982, 11 (04) :676-686

[7] Power consumption in packet radio networks [J].

Kirousis, LM ;

Kranakis, E ;

Krizanc, D ;

Pelc, A .

THEORETICAL COMPUTER SCIENCE, 2000, 243 (1-2) :289-305

[8]

Kranakis E, 2005, LECT NOTES COMPUT SC, V3544, P357

[9]

Kranakis E, 2004, LECT NOTES COMPUT SC, V3149, P917

[10]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architecture: Arrays. Trees. Hypercubes

← 1 2 →