## 5 Sleep Scheduling Algorithm  
Network lifetime is a critical aspect of wireless sensor networks (WSNs). Due to the limited power of sensor nodes, several techniques have been explored to prolong network longevity, one of which is sleep scheduling. This method involves sensor nodes working in duty cycles, with different nodes sleeping in each epoch while the rest remain awake. During sleep periods, nodes reduce their transmission and reception channels and processing power to conserve energy. However, sleep scheduling may impact packet routing and cause network disconnection depending on which nodes go to sleep. For example, in Figure 9, nodes \(e\) and \(f\) act as the only connection between nodes \(b\) and \(h\). If both nodes \(e\) and \(f\) go to sleep simultaneously, there will be no route between nodes \(b\) and \(h\). In order to avoid scenarios such as the one described above, [PERSON] et al. [33] proposed an efficient decentralized sleep scheduling algorithm to reduce the number of awake  
Figure 8: (**a**) Bridges depend on the sink movement. (**b**) A bridge is established when the sink determines that there exists a shortest path between its current position and a previous position exists. Figure 9: Sleep scheduling may disconnect the network if nodes \(e\) and \(f\) go to sleep in the same epoch. nodes while maintaining the network connected. Their algorithm addresses the connected k-neighborhood (CKN) problem, an NP-complete problem in graph theory: Given a constant \(k\) and an undirected graph \(G=(V,E)\), find a subset of nodes \(C\subset V\), such that \(C\) is a minimum connected k-neighborhood. In CKN, (i) each node \(v\in V\) has at least \(m=min(k,d_{v})\) neighbors from \(C\), where \(d_{v}\) is the degree of \(v\) in the \(G\), and (ii) the nodes in \(C\) are connected. \(C\) is a minimum CKN if no CKN has a smaller number of nodes. The near-optimal solution to the CKN problem is presented in Algorithm 1, with a detailed explanation provided in the work by [PERSON] et al. [33]. To determine whether a node will go to sleep, each node selects a random rank from a random number generator, which is then compared with its neighborhood. Nodes with larger ranks have a higher probability of going to sleep. However, to balance the network lifetime among nodes, [PERSON] et al. [34] proposed using the residual energy information of the nodes to determine whether a node will be awake or asleep. In our solution, we take advantage of the energy information shared for packet routing to obtain the rank for each node using Equation (8). Once the rank is determined, the sensor nodes use the same algorithm proposed by [PERSON] et al. [33] to estimate whether they will stay awake or go to sleep, skipping step 1 of the algorithm since the rank is already known. \[rank_{u}=1-energy_{u} \tag{8}\]  
where \(rank_{u}\) is the rank that node \(u\) will use to determine if it is going to remain awake or go to sleep, and \(energy_{u}\) is the residual energy of node \(u\). ```
1: Pick a random rank \(rank_{u}\). 2: Broadcast \(rank_{u}\) and receive the ranks of its currently awake neighbors \(N_{u}\). Let \(R_{u}\) be the set of these ranks. 3: Broadcast \(R_{u}\) and receive \(R_{v}\), from each \(v\in N_{u}\). 4: If \(|N_{u}|<k\) or \(|N_{v}|<k\) for any \(v\in N_{u}\), remain awake. Return. 5: Compute \(C_{u}=\{v|v\in N_{u}\) and \(rank_{v}<rank_{u}\}\)
6: Go to sleep if both of the following conditions hold. Remain awake otherwise. * Any two nodes in \(C_{u}\) are connected either directly or indirectly through nodes within \(u\)'s 2-hop neighborhood that have a \(rank\) lower than \(rank_{u}\). * Any node in \(N_{u}\) has at least k neighbors from \(C_{u}\). 7: Return. ```  
**Algorithm 1** Connected k-neighborhood (CKN) (* run the following at each node u *). It has been observed that sensor nodes near the sink consume more energy since they receive packets from the entire network for forwarding them to the sink. In contrast, nodes far from the sink consume less energy due to the lower packet traffic.