Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links
Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links
复制标题
DOI：
10.1007/11610113_2
复制
发表时间：
2006-01
期刊：
影响因子：
--
通讯作者：
D. Du;M. Thai;Yingshu Li;Dan Liu;Shiwei Zhu
中科院分区：
文献类型：
--
作者：
D. Du;M. Thai;Yingshu Li;Dan Liu;Shiwei Zhu
由于无线传感器网络中没有固定的基础设施或集中管理，连通支配集(CDS)可以作为无线传感器网络的虚拟骨干网。在CDS的帮助下，路由更容易，并可以快速适应网络拓扑的变化。CDS问题已经在无向图中得到了广泛的研究，特别是在单位圆盘图中，其中每个传感器节点具有相同的传输范围。然而，在实践中，所有节点的传输范围不必相等。本文将网络建模为考虑单向连接的圆盘图，并引入了圆盘图中的强连通支配集问题。我们提出了两种求解SCDS问题的常值逼近算法，并通过理论分析比较了它们的性能。
A Connected Dominating Set (CDS) can serve as a virtual backbone for a wireless sensor network since there is no fixed infrastructure or centralized management in wireless sensor networks. With the help of CDS, routing is easier and can adapt quickly to network topology changes. The CDS problem has been studied extensively inundirectedgraphs, especially in unit disk graphs, in which each sensor node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessarily to be equal. In this paper, we model a network as a disk graph where unidirectional links are considered and introduce the Strongly Connected Dominating Set (SCDS) problem in disk graphs. We propose two constant approximation algorithms for the SCDS problem and compare their performances through the theoretical analysis.