触发式连通支配集构造：串行最大独立集算法新视角

"基于串行最大独立集的连通支配集构造及分析 (2011年)" 这篇2011年的论文聚焦于无线传感器网络中的最大独立集（MIS，Maximum Independent Set）构造问题，特别是如何构建连通支配集（CDS，Connected Dominating Set）。在无线传感器网络中，连通支配集是一种重要的网络覆盖和通信组织结构，它要求集合中的每个节点都能直接或间接通信到其他所有节点，并保持整个网络的连通性。 通常，最大独立集的构造方法分为并行和串行两类。并行构造算法虽然可以快速找到解，但可能会生成尺寸不确定的连通支配集，且难以确定边界节点，这增加了计算时延和通信开销。相反，串行构造算法虽然可能相对较慢，但能更好地控制连通支配集的大小和结构。 论文提出了一种新的基于权重和时序的触发式连通支配集构造算法。该算法考虑了节点的权重和时间顺序，以解决并行算法中的问题。具体来说，算法在选择节点加入连通支配集时，不仅考虑节点的权重，还考虑它们被选择的时间顺序，以确保边界节点数量的减少。通过这种方式，算法能够在不构建生成树的情况下降低计算延迟，同时减少了通信开销。 仿真结果证明了新算法的有效性：它无需生成树，这意味着减少了计算复杂度；而且，由于最大独立集节点的选择遵循时间顺序，这有助于减少边界节点，从而为连通支配集提供了一个明确的上界。这对于资源有限的无线传感器网络尤其重要，因为它能够优化网络的能源效率和整体性能。 论文的关键字包括无线传感器网络、最大独立集、连通支配集、通信复杂度和计算复杂度，这些都揭示了研究的核心领域和关注点。中图分类号TP393则表明这是一篇关于信息技术和通信的论文，文献标志码A则意味着这是一项原创性的科学研究。 这篇论文对无线传感器网络中的连通支配集构造提供了新的策略，旨在优化网络的连通性和效率，对于理解和改进这类网络的性能具有重要意义。