A New Local Algorithm for Backbone Formation in Ad Hoc Networks

被引：3

作者：

Kassaei, Hossein ^{[1
]}

Mehrandish, Mona ^{[1
]}

Narayanan, Lata ^{[1
]}

Opatrny, Jaroslav ^{[1
]}

机构：

[1] Concordia Univ, Dept Comp Sci, Montreal, PQ H3G 1M8, Canada

来源：

PE-WASUN09: PROCEEDINGS OF THE SIXTH ACM INTERNATIONAL SYMPOSIUM ON PERFORMANCE EVALUATION OF WIRELESS AD-HOC, SENSOR, AND UBIQUITOUS NETWORKS | 2009年

关键词：

Performance evaluation; Connected dominating sets; Approximation algorithms; Ad hoc networks; UDG; CONNECTED DOMINATING SET;

D O I：

10.1145/1641876.1641886

中图分类号：

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

学科分类号：

0812 ;

摘要：

Several researchers have considered using a routing backbone to perform routing in a wireless ad hoc network. Such a backbone can be created by finding a connected dominating set (CDS) in the underlying graph We present a new distributed local algorithm to find a CDS in a unit disk graph (UDG), which is a commonly used model for ad hoc wireless networks. We assume that the nodes have information about their locations. The CDS produced by our algorithm is provably at most a constant times the size of the optimal CDS. We evaluate the performance of our algorithm in comparison with previously proposed algorithms in [6],[7],[15] and [17] via extensive simulations on randomly generated UDGs. Our results show that the CDS produced by our algorithm is 25% better than the next-best algorithm (which is however not local), and 28% better than the next-best local algorithm. Our algorithm is also computationally efficient and highly scalable.

引用

页码：49 / 57

页数：9

共 17 条

[1]

[Anonymous], 1990, COMPUT INTRACTABILIT

[2]

Basagni S., 2004, 2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems (IEEE Cat. No.04EX975), P70, DOI 10.1109/MAHSS.2004.1392076

[3] Distributed clustering for ad hoc networks [J].

Basagni, S .

FOURTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS, AND NETWORKS (I-SPAN'99), PROCEEDINGS, 1999, :310-315

[4] Local construction of planar spanners in unit disk graphs with irregular transmission ranges [J].

Chávez, E ;

Dobrev, S ;

Kranakis, E ;

Opatrny, J ;

Stacho, L ;

Urrutia, J .

LATIN 2006: THEORETICAL INFORMATICS, 2006, 3887 :286-297

[5]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[6]

CORMEN H, INTRO ALGORITHMS, P595

[7] Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes [J].

Czyzowicz, J. ;

Dobrev, S. ;

Fevens, T. ;

Gonzalez-Aguilar, H. ;

Kranakis, E. ;

Opatrny, J. ;

Urrutia, J. .

LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 :158-+

[8] An extended localized algorithm for connected dominating set formation in ad hoc wireless networks [J].

Dai, F ;

Wu, J .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2004, 15 (10) :908-920

[9] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[10] An efficient distributed algorithm for constructing small dominating sets [J].

Jia, LJ ;

Rajaraman, R ;

Suel, T .

DISTRIBUTED COMPUTING, 2002, 15 (04) :193-205

← 1 2 →