## 3 Checkpointing Scheme for Clustering Routing Protocols
### System Modeling
#### 3.3.2 The minimum number of backup nodes  
In our scheme, there is a trade-off between reliability and energy consumption. As the number of backup nodes increases, reliability also increases. However, the energy consumption of the checkpointing process also increases, and, as a result, the life-time of the network decreases. Therefore, we need to find the minimum number of backup nodes that satisfies user reliability expectations (\(R_{user}\)). Here, we apply the Markov model to determine the minimum number of backup nodes when the expected reliability is specified by a user or an application designer.  
In [16], there is a special case of a birth-death process that reflects that of a continuous-time Markov model. Figure 3 shows the state diagram of our model, where the state indicates the number of failure nodes.  
\begin{table}
\begin{tabular}{l|l} \hline
**Notation** & **Description** \\ \hline \(N\) & The number of nodes in a cluster \\ \(n\) & The number of backup nodes +1 (a cluster head) \\ \(\dot{\lambda}\) & Failure rate of each node \\ \(\mu\) & Repair rate of backup nodes \\ \(\rho\) & \(\dot{\lambda}\)/\(\mu\) \\ \(\pi_{k}\) & Steady-state probability of state \(k\) \\ \(R_{user}\) & User Expected reliability \\ \(MSG_{s}\) & Message length \\ \(E_{elec}\) & Energy consumption by cluster head election \\ \(E_{init}\) & Initial residual energy of a node \\ \(E_{ef}\) & Communication cost between two nodes \\ \(I_{ckpt}\) & Checkpointing interval \\ \(T\) & Total time of collecting data from all member nodes \\ \(t\) & Elapsed time of collecting data form a member node ( \(t=T\)/ (N-1) ) \\ \(E_{pre}\) & Energy consumption of clustering protocols without checkpointing \\ \(E_{ckpt}\) & Energy consumption of clustering protocols with checkpointing \\ \(D_{schd}\) & Packet scheduling delay \\ \(D_{pre}\) & Recovery latency of previous scheme \\ \(D_{ckpt}\) & Recovery latency of our scheme \\ \hline \end{tabular}
\end{table}
Table 1: List of notations.  
If the failure rate of each node (including the cluster head) is \(\lambda\) and the repair rate is \(\mu\), the expressions for steady-state probabilities are obtained via Equations (1) and (2):  
\[\pi_{k}=\pi_{0}\ \prod_{\mathrm{i=0}}^{\mathrm{k-1}}\frac{\lambda(\mathrm{n-i})}{ \mu},\ 0\ \leq\mathrm{k}\ \leq\mathrm{n} \tag{1}\]  
\[\pi_{0}=\frac{1}{\sum_{\mathrm{k=0}}^{\mathrm{n}}\rho^{\mathrm{k}}\frac{ \mathrm{n!}}{(\mathrm{n-k})!}} \tag{2}\]  
Each node has its own repair facility such as a watchdog timer that monitors the state of the sensor node periodically. If a sensor node has problems and cannot operate properly, a watchdog timer restarts the system. When the watchdog timer interval is the repair rate (\(\mu\)), the availability of an individual component (\(A_{indiv}\)) is obtained via Equation (3), and the steady-state availability (\(A_{steady}\)) is computed via Equation (4):  
\[\mathrm{A_{indiv}}=\frac{1}{1+\frac{\lambda}{\mu}}=\frac{1}{1+\rho} \tag{3}\]  
\[\mathrm{A_{steady}}=1-\pi_{\mathrm{n}}=1-\frac{\rho^{\mathrm{n}}\mathrm{n!}}{ \sum_{\mathrm{k=0}}^{\mathrm{n}}\rho^{\mathrm{k}}\frac{\mathrm{n!}}{(\mathrm{ n-k})!}} \tag{4}\]  
When \(\mathrm{A_{steady}}\) equal to the expected reliability of the user (\(R_{user}\)), \(\mu\) is equal to the frequency of watchdog timer and the failure rate of each node, (\(\lambda\)), is given, we can define the minimum number of backup nodes (\(n\)-1) through Equation (4).