## 3 Dynamic Sensor Scheduling Algorithms
### Cluster Formation for Scheduling Management  
When sensors of a network are first deployed, they may apply the Clustering Algorithm via Waiting Timer (CAWT) from [27] to partition the sensors into clusters. Each sensor sets a random waiting timer, broadcasts its presence via a '_Hello_' signal, and listens for its neighbor's '_Hello._' The sensors that hear many neighbors are good candidates for initiating new clusters; those with few neighbors should choose to wait. By adjusting randomized waiting timers, the sensors can coordinate themselves into sensible clusters, which can then be used as a basis for further communication and data processing.  
Sensors update their neighbor information (i.e. a counter specifying how many neighbors it has detected) and decrease the random waiting time based on each 'new' _Hello_ message received. This encourages those sensors with many neighbors to become clusterheads. The updating formula for the random waiting time of sensor \(i\) is:  
\[WT_{i}^{(k+1)}=\gamma\cdot WT_{i}^{(k)}, \tag{1}\]  
where \(WT_{i}^{(k)}\) is the waiting time of sensor \(i\) at time step \(k\) and \(0<\gamma<1\) is inversely proportional to the number of neighbors. Therefore, if the timer expires, then the sensor declares itself to be a clusterhead, a focal point of a new cluster. However, events may intervene that cause a sensor to shorten or cancel its timer. For example, whenever the sensor detects a new neighbor, it shortens the timer. On the other hand, if a neighbor declares itself to be a clusterhead, the sensor cancels its own timer and joins the neighbor's new cluster.  
After applying the CAWT, there are three different kinds of sensors: (1) the clusterheads (2) sensors with an assigned cluster ID (3) sensors without an assigned cluster ID, which will join any nearby cluster and become 2-hop sensors. In this phase, each sensor initiates two rounds of local flooding to its 1-hop neighboring sensors, one for broadcasting sensor ID and the other for broadcasting cluster ID, to select clusterheads and form 2-hop clusters. Figure 1 shows the network connectivity and cluster formation of a random network of 100 sensors with \(R/l=0.17\), where \(R/l\) is the ratio of transmitting range \(R\) to the  
Figure 1: The connectivity of the network (left); clusters are formed in a random network of 100 sensors with \(R/l=0.17\) (right).  
side length \(l\) of the square. Thus, the topology of the ad-hoc network is now represented by a hierarchical collection of clusters.  
Assume that a cluster of sensor nodes share a common view of a local clock time [28], so that all these nodes can coordinate in the sensor scheduling operation. Given the cluster-based network topology, each cluster member is assumed to sense only once during a sensing cycle \(T_{cycle}\) in a cluster. That is, \(T_{cycle}=\sum_{\ell=1}^{N_{RG}}T_{RG_{\ell}}\), where \(N_{RG}\) is the number of sensing rounds in a cluster and \(T_{RG_{\ell}}\) is the sensing duration of round \(\ell\). For sensor scheduling management, there are three kinds of sensors: (1) sensing nodes: executing the sensing task; (2) relay nodes: maintaining the cluster connectivity for intra-cluster communication; (3) gateway nodes: maintaining the network connectivity for inter-cluster communication. Note that the relay nodes may execute the sensing task in the later round and the gateway nodes may perform the sensing task and the relay transmission during the scheduling operation.