## 3 Checkpointing Scheme for Clustering Routing Protocols
### System Modeling
#### 3.3.2 Optimal checkpointing interval  
In the clustering routing protocols, a cluster head is in charge of the data collection activity, and this step is modeled as in Figure 4.  
This cluster is composed of N nodes (a cluster head and \(N\)-1 normal nodes), and each member node sends sensing data to its cluster head during time \(T\). If the failure rate of each node is \(\lambda\), then \(\mathrm{e}^{-\lambda\mathrm{T}}\) represents a lack of failure for each node during the total time of data collection of all member nodes (_i.e._, time \(T\)). In this condition, the probability of failure is \(\mathrm{P_{k}}=\left(\mathrm{e}^{-\lambda\mathrm{T}}\right)^{\mathrm{k-1}}(1- \mathrm{e}^{-\lambda\mathrm{T}})\), when the cluster head gathers data from the \(k^{th}\) node. Figure 4: The data collection step. Figure 3: The state diagram of our scheme. To compare the energy consumption of our checkpointing scheme with that of an existing non-checkpointing scheme, we define \(E_{pre}\) and \(E_{ckpt}\) as in Equation (5):  
\[\mathrm{E_{pre}}=\sum_{\mathrm{k=0}}^{\mathrm{N-1}}\{(1-\mathrm{P_{k}})\cdot \mathrm{MSG_{s}}\cdot\mathrm{E_{rf}}+\mathrm{P_{k}}\cdot(\mathrm{E_{elec}}+ \mathrm{MSG_{s}}\cdot\mathrm{E_{rf}})\:\}\]  
\[\mathrm{E_{elec}}=\{\:(\mathrm{N-1})^{2}+2(\mathrm{N-1})\}\cdot\mathrm{MSG_{s }}\cdot\mathrm{E_{rf}}\]  
\[\mathrm{E_{ckpt}}=\sum_{\mathrm{k=0}}^{\mathrm{N-1}}\{(1-\mathrm{P_{k}}) \cdot\mathrm{MSG_{s}}\cdot\mathrm{E_{rf}}+\mathrm{P_{k}}\cdot\mathrm{MSG_{s }}\cdot\mathrm{E_{rf}}\:\}\:+\:(\mathrm{n-1})\cdot\mathrm{MSG_{s}}\cdot \mathrm{E_{rf}}\cdot\left[\frac{\mathrm{k}}{\mathrm{1_{ckpt}}}\right] \tag{5}\]  
The energy consumption of the existing clustering routing protocols (\(E_{pre}\)) is divided by two parts. One is the summation of energy consumption of each member node while the cluster head operates properly. The other is the energy consumption of the recovery process. In clustering routing protocols without a checkpointing mechanism, when a cluster head fails, member nodes re-elect a new cluster head. This recovery process includes many types of messages such as a recovery process start message (\(N-I\)), broadcasting the remaining energy notification messages of normal nodes (\((N-I)^{2}\)), and a recovery process end message of the new cluster head (\(N-I\)), used for finding member nodes and constructing a routing table [17]. The energy consumption of the cluster head re-election process is represented by \(E_{elec}\). The energy consumption of a clustering routing protocol with checkpointing (\(E_{ckpt}\)) is similar to that of previously reported clustering routing protocols. However, the proposed checkpointing scheme excludes re-election cost (\(E_{elec}\)) because our scheme does not need to re-elect a new cluster head, although it does includes checkpointing costs during time \(k\). Algorithm 1 explains the checkpointing and recovery process of our scheme. As our scheme can omit cluster head election and state recovery, it reduces energy consumption and recovery latency. ```
if cluster head failure is detected!= true then if elapsed time >= \(I_{ckpt}\)then  checkpointing in backup nodes else  collecting data from normal nodes endif else  one of the backup nodes is assigned as a new cluster head  broadcast ID of a backup node to its normal nodes endif
```  
**Algorithm 1**the recovery process of our scheme. The optimal checkpointing interval is the time between two successive checkpoints while satisfying the \(E_{pre}\geq E_{ckpt}\) condition. This condition means that the checkpointing energy is to be less than the re-election energy.