【摘要】：连通支配集是用于为无线传感器网络和Ad Hoc网络构建骨干网的主要技术之一。CDS中的节点称为支配者，而其他节点称为被支配者。目前存在着多种用于评估骨干网协议质量的指标。通常情况下，在构建小型骨干网时，它是非常理想的，因而能够延长网络的生命周期，缓解网络拥塞。也就是说，连通支配集对于寻找最小连通支配集是非常有用的。但是，参考文献证实，在一般图中寻找MCDS等价于集合覆盖问题，该问题属于NP难问题。
连通支配集是用于为无线传感器网络和Ad Hoc网络构建骨干网的主要技术之一。CDS概念可简要介绍如下：支配集（Dominating Set，DS）是图中顶点的一个子集，图中的每个顶点要么在子集中，要么与子集中至少一个顶点相邻。CDS是一种连通DS。CDS中的节点称为支配者，而其他节点称为被支配者。目前存在着多种用于评估骨干网协议质量的指标。这些指标对骨干网特性（如骨干网规模、协议持续时间、消息开销和骨干网鲁棒性）进行评估（Basagni et al.，2006）。通常情况下，在构建小型骨干网时，它是非常理想的，因而能够延长网络的生命周期，缓解网络拥塞。也就是说，连通支配集对于寻找最小连通支配集（Minimum Con-nected Dominating Set，MCDS）是非常有用的。但是，参考文献（Garey and John-son，1978）证实，在一般图中寻找MCDS等价于集合覆盖问题，该问题属于NP难问题。即使是在UDG中，MCDS仍然属于NP难问题（Clark et al.，1990）。因此，文献中提出了近似算法和启发式算法来解决这个问题。通常情况下，近似算法可以用近似值/性能比来评估近似算法，它是算法性能与最优算法性能比的上限。后续引入的算法可以划分为集中式算法（如参考文献（Guha and Khuller，1998））和局部算法（如参考文献（Adjih et al.，2005））。参考文献（Alzoubi et al.，2002）引入了一些可以实现集中式算法的分布式算法。(www.xing528.com)
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
