Wireless Sensor Networks Fault-Tolerance Based on Graph Domination with Parallel Scatter Search.

Area of Science:

• Computer Science
• Network Engineering
• Wireless Communication

Background:

• Wireless sensor/ad hoc networks suffer from broadcast storms due to frequent control message flooding.
• Virtual Backbones (VB) offer an efficient solution for broadcasting, inspired by wired network backbones.
• Constructing VBs often involves solving the Connected Dominating Set (CDS) problem, with minimizing CDS size being a key challenge.

Purpose of the Study:

• To propose a new parallel scatter search algorithm (pSSEF) for constructing wireless network virtual backbones by finding minimum connected dominating sets.
• To address virtual backbone node failures using pre-computed VBs or a fault-tolerant repair algorithm (FT-pSSEF).
• To enhance network longevity by proposing a virtual backbone scheduling algorithm (SC-pSSEF) that manages power consumption through periodic VB switching.

Main Methods:

• Development of a parallel scatter search algorithm with elite and featured cores (pSSEF) for minimum connected dominating set identification.
• Implementation of a fault-tolerant approach (FT-pSSEF) to repair broken virtual backbones upon node failure.
• Introduction of a virtual backbone scheduling algorithm (SC-pSSEF) for load balancing and power consumption management.

Main Results:

• The pSSEF algorithm effectively constructs virtual backbones by finding minimal connected dominating sets.
• The FT-pSSEF algorithm successfully repairs or replaces virtual backbones compromised by node failures.
• The SC-pSSEF algorithm enables periodic switching between multiple virtual backbones, significantly prolonging network operational lifetime.

Conclusions:

• The proposed pSSEF algorithm provides an efficient method for virtual backbone construction in wireless networks.
• The fault-tolerance and scheduling mechanisms enhance the robustness and longevity of wireless sensor/ad hoc networks.
• Optimizing virtual backbone construction and management is crucial for overcoming broadcast storms and extending network lifespan.