Abstract: To address the problem of uneven cluster head load caused by traditional clustering methods in wireless sensor networks (WSNs), this paper proposes a clustering algorithm for WSNs constrained by Vertex-Sum Reducible Edge Coloring (VSRECUC). From a graph-theoretic perspective, the node-to-cluster association and cluster head load are modeled by abstracting the network clustering structure as a multi-star graph. The theory of vertex-sum reducible edge coloring is introduced, where the node association cost is mapped to edge coloring values, and the chromatic sum of each cluster head is used to characterize its communication load, thereby theoretically constraining the load balance among different cluster heads. In the cluster head election stage, residual energy and local node density are jointly considered to construct a candidate cluster head selection function, which is combined with a competition radius mechanism to effectively alleviate the “hotspot problem” caused by cluster head overload near the sink node. In the clustering stage, a node reassignment strategy constrained by vertex-sum reducible edge coloring is proposed. The CRITIC method is employed to determine the weights of competition radius and residual energy, dynamically calculate the cluster head load threshold, and guide nodes to be reasonably reassigned among different cluster heads, ensuring that the load of each cluster head matches its resource capability. Simulation results demonstrate that, in terms of network lifetime, the proposed VSRECUC algorithm extends the lifetime by 369.1%, 59.9%, 116.1%, 57.2%, and 55.7% compared with MH-LEACH, ESPC, EEUC, FSCVG, and BEBMCR, respectively. Moreover, it exhibits significant advantages in performance metrics such as cluster head number control and energy consumption balance. The results indicate that introducing vertex-sum reducible edge coloring theory into WSN clustering design provides a novel modeling perspective and an effective approach for achieving load balancing and network lifetime optimization.

摘要： 针对无线传感器网络(WSN)中传统成簇方式导致的簇头负载不均问题，本文提出了一种点和可约边染色约束的无线传感网成簇算法，该算法从图论视角对节点入簇与簇头负载问题进行建模，将无线传感网络的分簇结构抽象为星图联图模型，并引入点和可约边染色理论，将节点入簇代价映射为边染色的色数，以簇头节点的色和刻画其通信负载，从理论上约束不同簇头之间的负载均衡关系。在簇头选举阶段，综合考虑节点剩余能量与局部节点密度，构建候选簇头选取函数，并结合竞争半径机制确定最终簇头，有效缓解基站附近簇头过载的“热区问题”。在节点成簇阶段，提出基于点和可约边染色约束的节点重分配策略，引入CRITIC方法确定竞争半径与剩余能量的权重，动态计算簇头负载阈值，引导节点在不同簇头间进行合理调整，使各簇头负载与其资源能力保持匹配。仿真实验结果表明，VSRECUC算法在网络寿命方面较MH-LEACH、ESPC、EEUC、FSCVG和BEBMCR算法分别延长了369.1%、59.9%、116.1%、57.2%和55.7%，在簇头数量和能耗均衡性等性能指标上也具有显著优势。研究结果表明，将点和可约边染色理论引入无线传感器网络分簇设计中，能够为实现负载均衡与网络寿命优化提供一种新的建模思路和有效方法。