Distributed low-cost backbone formation for wireless ad hoc networks
Distributed low-cost backbone formation for wireless ad hoc networks
复制标题
DOI：
10.1145/1062689.1062692
复制
发表时间：
2005-05
影响因子：
9.5
通讯作者：
Yang Wang;Weizhao Wang;Xiangyang Li
中科院分区：
文献类型：
--
作者：
Yang Wang;Weizhao Wang;Xiangyang Li
主干已经广泛地用于各个方面（例如，路由、路由维护、广播、调度）。以前的方法大多是为了最小化骨架尺寸而设计的。然而，在许多应用中，当每个无线节点具有在骨干中的成本时，期望以小成本构建骨干。在本文中，我们首先表明，以前的方法专门设计，以尽量减少骨干的大小可能会产生一个大的成本骨干。然后，我们提出了一个有效的分布式方法来构建一个低成本的加权稀疏骨干。我们证明了，当节点的成本是光滑的或网络的最大节点度是有界的时，构造的骨干网的总成本是在一个小的常数因子的最优同构网络。我们还表明，与一个小的修改构造的骨干是有效的单播：总成本（或跳）的最小成本（或跳）的路径连接任何两个节点使用骨干不超过3（或4）倍的最小成本（或跳）的路径在原始通信图。作为副产品，我们给出了一个有效的覆盖的组播结构，其总成本不超过10倍的最小时，网络建模的UDG。我们的理论结果证实了我们的模拟研究。
Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless networks. Previous methods are mostly designed to minimize the backbone size. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with a large cost. We then propose an efficient distributed method to construct a weighted sparse backbone with low cost. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded. We also show that with a small modification the constructed backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than 3 (or 4) times of the least cost (or hop) path in the original communication graph. As a side product, we give an efficient overlay based multicast structure whose total cost is no more than 10 times of the minimum when the network is modeled by UDG. Our theoretical results are corroborated by our simulation studies.