## 3 Dynamic Sensor Scheduling Algorithms
### Centralized Adaptive Scheduling Algorithm (CASA)
\begin{table}
\begin{tabular}{l} \hline Assign \(N_{RG}=0\), \(\ell=1\); \\
**while** (\(U\
eq\phi\)) **do** \\ \(\{\) \\ \(H_{1}^{{}^{\prime}}=H_{1}\); \\ \(RG_{\ell}=\phi\); \\ \(\backslash*\) Selecting 2-hop round members \(*\backslash\) \\
**if** (\(H_{2}\
eq\phi\)) \\ \(\{\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\backslash*\) Selecting 1-hop round members \(*\backslash\) \\
**while** (\(H_{1}^{{}^{\prime}}\
eq\phi\)) **do** \\ \(\{\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\backslash*\) Selecting 1-hop round members \(*\backslash\) \\
**while** (\(H_{1}^{{}^{\prime}}\
eq\phi\)) **do** \\ \(\{\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\) \\ \(\}\) \\ \(\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \(\}\) \\ \end{tabular} \\ \hline \end{tabular}
\end{table} 
Table 1: The CASA Scheduling SchemeMaintenance of Network Connectivity  
After establishing the sensing schedule in each cluster, network connectivity may be maintained with two phases of operation (observation and confirmation phases). The period of the observation phase may last several sensing cycles (\(nT_{cycle}\), \(n>1\)), which allow the sensors to learn about the scheduling operation of their neighboring sensors in nearby clusters. During the observation phase, each sensing node and relay node executes a 1-hop broadcast at the beginning of its active period in the sensing schedule such that the sensing nodes can assign the gateway sensors for inter-cluster communication and data dissemination. The broadcast message includes the sensor node ID and the sensing cycle time \(T_{cycle}\) for the gateway nodes to initialize the next relay transmission. There are four possible scenarios when determining the gateway nodes: (1) When the sensing node receives only one broadcast message from an active node in the nearby cluster during its sensing period, these two nodes form a pair of distributed gateways. Hence, a sensing node or a relay node in the nearby cluster may be a gateway under this condition; (2) If the sensing node receives multiple broadcast messages from the same nearby cluster, the nearest active node in this specific cluster might be chosen as a gateway node based on distance information, which could be estimated by the received signal strength. Similar to Scenario 1, a sensing node or a relay node may be a gateway in this case; (3) When no broadcast message is received during the sensing period, the sensing node may choose the nearest node in an adjacent cluster as a gateway node; (4) If the clusters are too far apart (outside the range of communication \(R\)), no gateway sensors will be assigned. Built upon the learning process in the observation phase, the sensing node and the candidate of the gateway node acknowledge the role assignment in the confirmation phase. Thus, each pair of distributed gateways send 1-hop broadcast messages to confirm the gateway selection with each other. Accordingly, the result of gateway selection is that each round group member assigns a single member of each nearby clusters such that network connectivity during the sensor scheduling operation may be assured. Therefore, the CASA approach provides a virtual backbone for sensing coverage and network connectivity maintenance. The procedures of gateway selection is depicted in Figure 2. Figure 2 (a) and Figure 2 (b) describe the operation period of a pair of distributed gateways in Scenarios 1 and 3, respectively. Given the local common clock, the time stamp of the received message, and the duration of the sensing cycle \(T_{cycle}\), the sensing nodes A and B may work cooperatively as a pair of distributed gateways to adjust their active periods for data dissemination.