Distributed Detection of Critical Nodes in Wireless Sensor Networks Using Connected Dominating Set

Dağdeviren O., Akram V. K., Tavli B., Yıldız H. U., Atılgan C.

15th IEEE Sensors Conference, Florida, United States Of America, 30 October - 02 November 2016 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Florida
  • Country: United States Of America
  • Keywords: Wireless Sensor Networks, Critical Node Detection, Connected Dominating Set, Reliability, Connectivity
  • TED University Affiliated: No


A critical node (cut vertex) in a wireless sensor network (WSN) is a node which its failure divides the network to disconnected parts. Identification of such nodes is the first step in countering against the threats on WSN reliability. In this paper, we propose the Connected Dominating Set based CUT vertex detection (CDSCUT) approach. We define 5 new rules for deciding about the statuses of nodes. The proposed algorithm has O(Delta(2)) local computation complexity and O(log(2)n) bit complexity per node where n is the node count and Delta is the maximum node degree. The simulation results show that our proposed approach achieves up to 30% improvement in percentage of status detection compared to the previous CDS based approach while consuming similar time and energy.