# CONE: A Connected Dominating Set-Based Flooding Protocol for Wireless Sensor Networks
## 1 Introduction  
Over the past decade, Wireless Sensor Networks (WSNs) have begun to play a significant role as an enabling technology in a large number of applications, e.g., healthcare, industry, and agriculture, to name a few. A WSN typically contains a large number of sensor nodes. Generally, a sensor node consists of a processing unit, a radio for wireless communication and one or more sensors. Sensor nodes are usually used to monitor environmental conditions, especially in places where wiring is impractical. Presently, WSNs act as an important infrastructure in the popular Internet of Things (IoT). The idea behind IoT is to fully integrate tiny devices such as sensor nodes with IP-based networks, in order to realize new areas of WSN applications [1]. The integration of WSNs in IoT enables users' immediate access to (environmental) data collected by the sensor nodes. This effectively increases the efficiency and the productivity of many processes [2]. However, in many applications, sensor nodes are powered by a limited power source, and sometimes it is unfeasible to replace or recharge sensor nodes. Hence, the network lifetime becomes a critical concern in the design of WSNs [3]. Increasing the energy efficiency of WSNs is an important topic in the research community [4]. As a fundamental service in WSNs, network flooding offers the advantages that information can be distributed fast and reliably throughout an entire network [5]. It is exploited in data dissemination, remote code update, wireless bulk data transfer, periodical update (e.g., in the IPv6 Routing Protocolfor Low-Power and Lossy Networks (RPL) [6]), and so forth. In network flooding, a node called \"initiator\" typically triggers the flooding process by broadcasting a packet to its neighboring nodes. If a node receives this packet, then it rebroadcasts this packet. Nodes repeat this process until a predefined event occurs, e.g., a timer expires. This process literally \"floods\" the information to all the nodes in the whole network. Besides, network flooding is simple to implement, and it normally does not require any routing mechanism that maintains routes from sources to certain destinations in a network. Therefore, it is often used to discover neighbors and to construct routing tables during network initialization, e.g., in [7,8]. However, network flooding suffers from the broadcast storm problem [9], leading to low energy efficiency of the network. A broadcast storm occurs when a network is overwhelmed by continuous broadcast traffic. For instance, when different nodes are broadcasting data over a network link and the other nodes are rebroadcasting the data back to the network link in response, then this eventually leads to a network communication breakdown [9]. Correspondingly, the broadcast storm causes collisions, traffic overhead, waste of bandwidth, and so forth. Therefore, it results in extremely energy-inefficient network flooding. As Figure 1 shows, node 2 and its neighboring nodes suffer from infinite broadcasting traffic. Energy efficiency of network flooding can be enhanced by using a minimal connected dominating set (MCDS). A Connected Dominating Set (CDS) is a connected subgraph of an initial graph that represents a network. Each node that is not in the CDS is adjacent to at least one node of the CDS. A MCDS is a CDS with the minimal number of nodes. MCDS-based approaches reduce communication overhead, radio duty cycles, and overall energy consumption of WSNs [10]. In Figure 2, node 2 and 3 form a CDS of the network. Instead of letting all nodes rebroadcast information, only node 2 and 3 rebroadcast this information. Nevertheless, every node which is not in the CDS also eventually receives the information. Figure 1: The broadcast storm problem in network flooding. The dashed lines indicate that two nodes are within transmission range of each other. The arrows show a transmission from one node to another one. (**a**) Node 8 broadcasts a packet to node 2. (**b**) Node 2 broadcasts this packet to node 3, 8, and 9.