Geometric spanners for wireless ad hoc networks

被引：135

作者：

Alzoubi, K ^{[1
]}

Li, XY ^{[1
]}

Wang, Y ^{[1
]}

Wan, PJ ^{[1
]}

Frieder, O ^{[1
]}

机构：

[1] IIT, Dept Comp Sci, Chicago, IL 60616 USA

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2003年 / 14卷 / 04期

关键词：

connected dominating set; clustering; Delaunay triangulation; spanner; unit disk graph; localized algorithm; wireless ad hoc networks;

D O I：

10.1109/TPDS.2003.1195412

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.

引用

页码：408 / 421

页数：14

共 39 条

[1]

Alzoubi K. M., 2002, THESIS ILLINOIS I TE

[2]

Alzoubi K. M., 2002, P IEEE HAW INT C SYS

[3]

Amis A. D., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P32, DOI 10.1109/INFCOM.2000.832171

[4]

Amis A. D., 2000, P 3 IEEE S APPL SPEC

[5]

[Anonymous], P IEEE HAW INT C SYS

[6]

[Anonymous], P 3 ACM INT S MOB AD

[7]

[Anonymous], 2000, P ACM IEEE INT C MOB

[8]

[Anonymous], 1999, TELECOMMUN SYST

[9]

Baker D. J., 1984, IEEE Journal on Selected Areas in Communications, VSAC-2, P226, DOI 10.1109/JSAC.1984.1146043