Asynchronous Local Construction of Bounded-Degree Network Topologies Using Only Neighborhood Information
Asynchronous Local Construction of Bounded-Degree Network Topologies Using Only Neighborhood Information
复制标题
DOI：
10.1109/tcomm.2018.2883457
复制
发表时间：
2018-11
影响因子：
8.3
通讯作者：
Erdem Koyuncu;H. Jafarkhani
中科院分区：
文献类型：
--
作者：
Erdem Koyuncu;H. Jafarkhani
我们考虑由$n$个无线节点组成的ad-hoc网络，这些节点位于平面上。任何两个给定的节点被称为邻居，如果他们位于一定的距离（通信范围）从彼此。一个给定的节点可以直接连接到它的任何一个邻居，并根据一个独特的拓扑控制算法，可在每个节点选择它的连接。鉴于每个节点只知道它的一个和两个跳邻居的索引（唯一的标识号），我们确定了一个算法，保留连接，可以操作，而不需要任何节点之间的同步。此外，该算法的结果在一个稀疏的图与最多$5n$边和最大节点度为10。具有相同承诺的现有算法还需要每个节点处的邻居距离和/或方向信息。我们还评估了我们的算法的随机网络的性能。在这种情况下，我们的算法提供了一个渐进连接的网络与$n（1+o（1））$边的度小于或等于6的$1-o（1）$分数的节点。我们还介绍了另一种异步连接保持算法，可以提供一个上界，以及节点度的下界。
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.