Asynchronous Local Construction of Bounded-Degree Network Topologies Using Only Neighborhood Information

作     者：Koyuncu, Erdem Jafarkhani, Hamid 

作者机构：Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA Univ Calif Irvine Ctr Pervas Commun & Comp Irvine CA 92697 USA 

出 版 物：《IEEE TRANSACTIONS ON COMMUNICATIONS》 (IEEE通讯汇刊)

年 卷 期：2019年第67卷第3期

页      面：2101-2113页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 

基　　金：DARPA GRAPHS program [N66001-14-1-4061] NSF [CCF-1814717, CCF-1815339] 

主　　题：Topology control local algorithms connectivity degree-bounded graphs 

摘      要：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.