عنوان

Asynchronous local construction of bounded-degree network topologies using only neighborhood information

Number

LA5dk0c799

Title Proper

Asynchronous local construction of bounded-degree network topologies using only neighborhood information

General Material Designation

[Article]

First Statement of Responsibility

Koyuncu, EJafarkhani, H

Text of Note

© 1972-2012 IEEE. We consider the ad-hoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors, and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one and two-hop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization among nodes. Moreover, the algorithm results in a sparse graph with at most 5n edges and a maximum node degree of 10. Existing algorithms with the same promises further require neighbor distance and/or direction information at each node. We also evaluate the performance of our algorithm for random networks. In this case, our algorithm provides an asymptotically connected network with n(1+o(1)) edges with a degree less than or equal to 6 for 1-o(1) fraction of the nodes. We also introduce another asynchronous connectivity-preserving algorithm that can provide an upper bound as well as a lower bound on node degrees.

Date of Publication

2019

Title

UC Irvine

Electronic name

[Article]

278488

a

Y