• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science ›› 2025, Vol. 47 ›› Issue (7): 1181-1192.

• Computer Network and Znformation Security • Previous Articles     Next Articles

A virtual backbone construction algorithm in wireless sensor networks

HUANG Jinhe1,2,LIANG Jiarong1,2,LI Changzhen3   

  1. (1.School of Computer,Electronics and Information,Guangxi University,Nanning 530004;
    2.Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004;
    3.School of Public Policy and Management,Guangxi University,Nanning 530004,China)
  • Received:2024-03-13 Revised:2024-07-20 Online:2025-07-25 Published:2025-08-25

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