Bootstrapping Free-Space Optical Networks

Loading...
Thumbnail Image

Files

umi-umd-1645.pdf (621.7 KB)
No. of downloads: 1697

Publication or External Link

Date

2004-07-08

Citation

DRUM DOI

Abstract

We consider one challenging problem in establishing a Free Space Optical (FSO) network. In our model, it is assumed that each node is a base station and its number of transceivers is limited. Such a network can be abstracted by a graph where each node represents a base station and each edge represents a link connecting two base stations. The problem is that of forming a connected topology, which is known to be NP-complete because of the transceiver limitation. What makes this problem even more challenging is the need to have a "distributed" solution to form a connected topology, because a node can have knowledge only of its neighbors. We have developed a fully distributed approximation algorithm, which constructs a spanning tree with maximal node degree at most one larger than that in the optimal solution. Due to its distributed nature, this algorithm outperforms serial algorithms.

Notes

Rights