# CONE: A Connected Dominating Set-Based Flooding Protocol for Wireless Sensor Networks
## 3 Design and Implementation of CONE
### Neighbor Discovery and Degree Exchange
#### 3.2.2 Connecting the Dominating Set  
If a node initializes the flooding process by broadcasting a packet, then not all nodes in the network are able to receive the packet. The resulting DS from the previous step is not necessarily connected. For instance, the green nodes in Figure 7(b) are not connected to each other via other nodes. To connect the DS, we have to choose additional nodes to become dominators.  
The work from [20] uses a ST construction algorithm in order to connect the DS. However, this algorithm requires that each node knows all other nodes in the network. To keep the message overhead as low as possible, we came up with another idea for this work which requires less information. Our idea is that each node periodically broadcasts a token_message, in which way a token_value is updated. Every node in the network has a token_value which is the largest known ID of a dominator in the network. A node's token_message contains the sender's token_value. If all nodes in the network have the same token_value, then the DS_is_connected is true. Accordingly, if a received token_message differentiates from the receiver's token_message, then it indicates that the flag DS_is_connected is false.  
Algorithm 6 provides the pseudo-code of how nodes use their token_message in order to connect the DS. Each node periodically broadcasts a token_message. A token_message contains the sender's token and a flag which is set if the sender is a dominator. Nodes update their token if they receive a greater token from a dominator. However, a node does not accept a token_message that was sent by a non-dominator. Figure 9 shows how nodes can use their token_message in order to connect their DS. Let the red nodes have a lower token_value than the green nodes. The red nodes will not accept the largest token_value, because there is no dominator that broadcasts the token_message to them. However, the grey nodes are in transmission range of the dominator with the largest token_value. Hence, the red nodes receive the higher token_value from the grey nodes. Furthermore, selecting one of the grey nodes results in the connection of the DS. To select a grey node, each red node increases its local counter by one if it receives a higher token_message from the grey nodes. If the counter reaches a predefined threshold, the node resets it to zero and selects one of the grey nodes. Also, the red nodes record the grey node's ID which has the lowest ID in their neighborhood to increase the possibility that both red nodes select only one grey node.  
```
1:receive token_message
2:if dominator's ID equals the received token then
3: set ID of my dominator to 0
4: stop timer for election_message
5:elseif (my dominator is the sender of the received token_message and sender is a dominator) then
6: set ID of my dominator to 0
7: stop timer for election_message
8:endif
9:if value of my token is lower than the one of received token then
10:if sender is a dominator then
11: set value of my token to value of received token
12:else
13:if (ID of my dominator equals 0) or (ID of sender is equal to my dominator) then
14: set sender as my new dominator
15:endif
16: increase counter by 1
17:if counter equals threshold then
18: set token counter to 0
19: set counter to 0
20: set timer for election_message
21:elseif value of my token is greater than the one of received token then
22: set token counter to 0
23:endif
24:endif
25:endif
26: periodically broadcast token_message
27:while DS_is_connected is false do
28: set timer for broadcasting token_message
29: wait until (token counter is lower than threshold or I am a dominator)
30: wait until timer for broadcasting token_message has expired
31:if (DS_is_connected is false) and (token is not equal to 0) then
32: broadcast token_message
33: increase token counter by 1
34:endif
35:endwhile
36: set ID of my dominator to 0
37: stop timer for election_message
```  
**Algorithm 6** Token exchange.