Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks.

Area of Science:

• Computer Science
• Network Engineering
• Distributed Systems

Background:

• Wireless sensor networks (WSNs) are crucial for environmental sensing in the Internet of Things (IoT).
• Battery limitations and software issues pose significant challenges for WSN nodes.
• Self-stabilization offers a fault-tolerance technique to restore network integrity after topological changes.

Purpose of the Study:

• To propose the first self-stabilizing algorithms for the capacitated vertex cover problem in WSNs.
• To enhance the fault tolerance and efficiency of WSNs using graph theoretical structures.
• To address limitations of existing WSN management techniques.

Main Methods:

• Developed two novel self-stabilizing algorithms for capacitated vertex cover.
• Algorithm 1: Stabilizes in O(n^2) steps under an unfair distributed scheduler.
• Algorithm 2: Stabilizes in O(n) steps with 2-hop knowledge under an unfair scheduler.

Main Results:

• Theoretical analysis provided proof of correctness and step complexities for both algorithms.
• Simulations using IRIS sensor node parameters demonstrated superior performance.
• Proposed algorithms exhibited faster convergence, reduced energy usage, and better vertex cover solutions compared to counterparts.

Conclusions:

• The proposed self-stabilizing capacitated vertex cover algorithms are effective for WSNs.
• These algorithms offer significant improvements in speed, energy efficiency, and solution quality.
• The findings are applicable to various WSN applications including routing, clustering, and link monitoring.