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

作     者：Koyuncu, Erdem Jafarkhani, Hamid 

作者机构：Department of Electrical and Computer Engineering University of Illinois Chicago United States Center for Pervasive Communications and Computing University of California Irvine United States 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2018年

核心收录：

主　　题：Ad hoc networks 

摘      要：We consider 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. Copyright © 2018, The Authors. All rights reserved.