# CONE: A Connected Dominating Set-Based Flooding Protocol for Wireless Sensor Networks
## 3 Design and Implementation of CONE
### Flooding Protocol  
A node proceeds with the flooding process once an event timer for the CDS construction has expired. In flooding, an initiator is a node that initiates network flooding by initially broadcasting a message. During the flooding process, the initiator node periodically broadcasts a packet in order to trigger network flooding. For the flooding process, we use the Trickle algorithm [13]. Trickle uses polite gossip in order to distribute information through an entire network. Polite gossip means that if a node receives new or old information, then the node rebroadcasts the received information. Otherwise, the node does not broadcast the received information, because broadcasting the same information again is considered being aggressive. Figure 10 provides an example of how Trickle works. To determine whether information is old or new, packets in Trickle contain a sequence number \(seqno\_x\). In case of CONE, only dominators rebroadcast information. As stated in Section 2.2.3, each node in the network that is not in the CDS is adjacent to at least one node of the CDS. Therefore, it is sufficient that only nodes in the CDS rebroadcast information in order to ensure that all nodes in the network receive the newest information. Hence, CONE can reduce redundant broadcasts in Trickle by using a CDS without impairing Trickle's ability to keep information in a network up to date. Algorithm 7 shows how Trickle works in pseudo-code when it uses a CDS. ```
1:receive Trickle_message
2:if received sequence number is equal to my sequence number then
3: stop rebroadcasting
4:elseif received sequence number is lower than my sequence number then
5:if I am dominator then
6: broadcast information
7:endif
8:else
9: set my sequence number to received sequence number
10: store the received information
11:if I am dominator then
12: set timer for broadcasting information
13:endif
14:endif

Figure 9: Dominating set being turned into a connected dominating set. The dominators are colored in green and red. The red dominators have a lower token value than the green dominators. White and grey nodes are non-dominators. Furthermore, the grey nodes separate the two disconnected sets of dominators. (**a**) The red dominators periodically receive the token with the largest value from the grey nodes, but do not update their token value because the grey nodes are not dominators. After receiving the token with the largest value from the grey nodes n times, the red dominators elect one of the grey nodes to become a dominator. When one of the grey nodes becomes a dominator, the red dominators accept the token with the largest value from it. (**b**) All dominators have the highest token value and thus are colored in green. ### CDS Maintenance

We designed CONE such that a network can maintain a constructed CDS. CONE can cover the following cases: (1) new node joins the network after CDS construction is done, (2) a dominator leaves the network because of node failure, and (3) a non-dominator loses connection to all dominators. Nodes use maintenance_messages and is_connected_messages in order to handle those three cases. The state chart in Figure 11 shows how CONE maintains a constructed CDS. When a node initializes CONE, then it broadcasts a maintenance_messages to ask its neighbors whether a CDS has been constructed. If a node receives a is_connected_messages, then this means that a CDS has been constructed and, therefore, the node does not need to initialize the CDS construction. Instead, it enters the flooding process. Furthermore, because the initiator broadcasts flooding packets in a known interval, other nodes in the network expect to receive flooding packets after a certain time. If this is not the case, then nodes broadcast a maintenance_messages to ask their neighbors whether the CDS is still intact. Nodes which receive a maintenance_messages reply with a is_connected_messages if the CDS is still intact. Algorithm 8 provides the pseudo-code for CDS maintenance. Figure 11: Flooding protocol states.