# CONE: A Connected Dominating Set-Based Flooding Protocol for Wireless Sensor Networks
## 1 Introduction
(**c**) Node 8, 9, and 3 broadcast the packet simultaneously to node 2 and others in response. Figure 2: Using a CDS for network flooding. Nodes which are in the CDS are colored in green. The dashed lines indicate that two nodes are in transmission range of each other. Arrows show a transmission from one node to another one. (**a**) Node 8 broadcasts a packet to node 2. (**b**) Since node 2 is in the CDS, it rebroadcasts the packet to node 3, 8, and 9. (**c**) Since node 3 is in the CDS, it rebroadcasts the packet to node 2, 9, and 13. However, because node 8 and 9 are not in the CDS, they do not rebroadcast the packet. However, finding a MCDS is a Non-deterministic Polynomial-time (NP)-hard problem [8]. There has been a lot of work done on finding approximation algorithms to solve this NP-hard problem [11]. In this article, we propose the Connected Dominating Set-based flooding protocol (called \"CONE\"), to improve the energy efficiency of network flooding. CONE exploits an approximation algorithm to construct a CDS and subsequently uses this CDS to boost the flooding procedure. As a side effect, CONE significantly reduces the problem of broadcast storms. For the evaluation of CONE, we perform simulations for analyzing the behavior of CONE. Furthermore, we employ a real-world testbed FlockLab [12] for the evaluation. The evaluation concentrates on (1) packet loss because of IEEE 802.15.4 medium access control (MAC) contention, (2) radio duty cycle (RDC), and (3) energy consumption. These metrics very well indicate the energy efficiency and reliability of flooding protocols in WSNs. Besides, we compare CONE to the baseline protocol Trickle [13] in order to address benefits brought by using a CDS. Note, we choose Trickle as the baseline because it is one of the most classic algorithms for propagating and maintaining code updates in WSNs and several IEEE 802.15.4 standards are based on Trickle, e.g., RPL [6]. In this work, we make the following contributions:  
* We propose CONE, a connected dominating set-based flooding protocol for WSNs. CONE reduces the number of broadcasts by disallowing the nodes that are not in the CDS to rebroadcast packets during a flooding process. * We implement CONE in Contiki OS [14] and carry out extensive experiments by simulation and in a real-world testbed, respectively. * We evaluate the performance of CONE and compare it to the state-of-the-art in terms of end-to-end reliability and duty cycle in the simulator Cooja [15] and energy consumption in the testbed FlockLab [12]. In Section 2, we review several existing approaches for controlling a network's topology. Also, we clarify the reasons why we choose a CDS-based approach in CONE. In Section 3, we describe the design of CONE. For this purpose, we detail the CDS construction and maintenance and then describe the portability of the CDS construction algorithm of CONE to other flooding protocols. In Section 4, we compare the performance of CONE and the baseline protocol [13] based on experiments in Cooja [15] and in FlockLab [12]. In Section 5, we summarize our work and provide a glimpse into future work.