# DDS: A Delay-Constrained Duty-Cycle Scheduling Algorithm in Wireless Sensor Networks
## 4 A Delay-Constrained Duty-Cycle Scheduling Algorithm
### Group-Based Forwarding Algorithm
#### 4.1.1 Group Determination Phase  
This phase includes two subphases. The first one assigns the group index to the nodes, and the second one aggregates the network information at the sink. First, the group index of the nodes is determined as follows. The group index of the sink is set to zero while sensor nodes initialize the infinite values for the group indices. Each node broadcasts a hello message (which contains the node's group index) periodically or when the group index of the node changes. When node A (except for the sink) receives a hello message from node B, the group index of node A is calculated as follows:  
\[GI_{A}= \begin{cases}GI_{B}+1,&\text{if }GI_{A}>GI_{B}+1,\\ GI_{A},&\text{otherwise},\end{cases}  \tag{1}\]  
where \(GI_{A}\) and \(GI_{B}\) are the group indices of node A and node B, respectively. After updating their group index, nodes immediately broadcast the changed information to neighboring nodes. At the end of this subphase, nodes update the group index and maintain the forwarder's information, which will be sent to the sink in the second subphase. Let \(j\) denote the group index of nodes, i.e., nodes in group \(j\) have a group index that equals \(j\). Let \(N_{j}\) and \(g\) denote the number of nodes in group \(j\) and the largest group index for nodes in the network, respectively. Thus, \(j=0,1,2,\ldots,g\). Note that only the sink node is in group 0. Let \(n_{j}^{i}\) denote the \(i\)th node in group \(j\), where \(i=1,2,\ldots,N_{j}\). We define the potential forwarding candidates (PFCs) of node \(n_{j}^{i}\) as nodes that are in group \((j-1)\) within the transmission range of node \(n_{j}^{i}\). Figure 1 shows a WSN that consists of a sink node and nine sensor nodes. By the first subphase, nodes know their group index, neighboring nodes, and potential forwarders. For example, node \(n_{2}^{1}\) in group 2 has four neighboring nodes (i.e., \(n_{3}^{1}\), \(n_{2}^{2}\), \(n_{1}^{2}\), and \(n_{1}^{1}\)) and two PFCs (i.e., \(n_{1}^{1}\) and \(n_{1}^{2}\)). In the second subphase, the sink collects the information necessary for estimating the duty cycle interval. Instead of using a flooding protocol that causes redundant packets, a period-based scheme is used. First, this subphase duration is divided into \(q\) equal periods, which should be greater than or equal to the maximum group index (i.e., \(q\geq g\)). We assume that the sink knows and broadcasts the \(q\) value throughout the network. In the first period, each node with a group index equal to \(q\) (i.e., \(j=q\)) forwards an information packet that contains the necessary information (i.e., the group index and the list of PFCs) to a next-hop node. The next-hop node is randomly selected from among the PFCs of the transmitter. Then, nodes in group \((q-1)\) that received information packets append their information to the received information packets. Thus, nodes in group \((q-1)\) have information packets that contain information from nodes in group \(q\) and \((q-1)\). With the same procedure, at the beginning of the second period, nodes in group \((q-1)\) forward their information packets to the next-hop nodes that are in group \((q-2)\). The second subphase finishes when the nodes in group 1 forward their information packets to the sink. For instance, assume that \(q\) is set to 3 in the network deployment scenario shown in Figure 1. At the beginning of the first period, nodes in group 3 forward their information packets to nodes in group 2. Then, each node in group 2 appends its information to the received information packets from nodes in group 3. These combined packets are relayed to nodes in group 1 at the beginning of the second period. Finally, the sink receives network information, including the number of groups in the network (i.e., \(g=3\)), the number of nodes in the groups, and the PFCs of the nodes. The information from group 2 is shown in Table 2.