Abstract: The virtual backbone of a wireless sensor network consists of nodes responsible for computation and routing tasks,and its energy efficiency is a critical factor in determining the overall network lifespan.The problem of constructing a long-lived fault-tolerant virtual backbone in wireless sensor networks can be abstracted as the weighted connected domatic partition problem in weighted undirected graphs,which is an NP-Hard problem.This paper proposes a lifespan-aware fault-tolerant virtual backbone construction algorithm,which comprises two sub-algorithms.Sub-algorithm 1 adopts a greedy strategy to select nodes with higher energy levels to construct multiple disjoint connected dominating sets,maximizing the battery utilization efficiency of virtual backbone nodes based on a sleep-wake mechanism.Sub-algorithm 2 employs a pseudo-disjoint connected dominating set technique to select nodes with longer lifespans to update the virtual backbone obtained from sub-algorithm 1,thereby constructing a new long-lived fault-tolerant virtual backbone.Simulation results demonstrate that the proposed algorithm outperforms the compared algorithms in terms of virtual backbone lifespan and the number of connected dominating sets.

Key words: wireless sensor network, virtual backbone, weighted connected domatic partition, node energy