# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 6 Checkpointing and Recovery Algorithms
### Algorithm for Failure Recovery
Then the process executes rollback operation according to _ERS_ and sends the _ERS_ to related processes in old cluster to inform them to roll back. Reactive Rollback. The process waits for the _ERS_ sent by the process running in old cluster and executes rollback after received the _ERS_. Figure 8: The transition of states. #### 7.1.2 The Process Stays the Checkpoint State

_CKP_ Initiitor. If the process stays the receiving stage of DL, then it goes on waiting for the DL sent from processes in old cluster. If the process has sent the _LDS_, then it waits for the replies from processes in old cluster. After that, the process continues executing the checkpointing until the end. _CKP_ Participant. The process waits for the coordination request from the initiator of checkpointing and replies until the end of checkpointing procedure. ### Update of Checkpoint Dependence Relation

Because the the relations of the HOH in same cluster and different clusters all change after it leaves the old cluster and enters the new cluster, so it needs to update the dependence relations among checkpoints in old or new cluster and the checkpoints of processes in HOH when the all processes in HOH have finished their current work. The main update work is to renew the related data structures such as the _PL_, _DL_, _IntraCDG_ and _InterCDG_. Let \(C_{k}\) and \(C_{i}\) respectively the old cluster and new cluster related to HOH. \(PS\) is the set of processes running in HOH. #### 7.2.1 Update of Checkpoints Dependence Relation in Old Cluster

Firstly, it needs to delete the processes in \(PS\) from the \(PL_{k}\) and \(DL_{s}\) of all processes in old cluster. Then it should turn the same cluster dependence relation among checkpoints of processes in \(PL_{k}\) and \(PS\) to dependence relations among different clusters. That means to modify the related _IntraCDG_ and _InterCDG_. Let \(P_{t}\in PS\), \(P_{j}\in PL_{k}\). \(CKP_{a}\) and \(CKP_{b}\) are the checkpoints of \(P_{t}\) and \(P_{j}\) respectively. The algorithm for updating of checkpoints dependence relations in old cluster is described as the Algorithm 5. ```
DELETE_process(\(PL_{k}\), \(PS\)); //delete \(PS\) from \(PL_{k}\) NOTICE_DLChange(\(PS\)); //notice processes to change \(DL\) for(\(P_{x}\in PS\) | \(| P_{x}\in PL_{k}\))do REQUIRE_IntraCDG(\(P_{x}\)); //sendIntraCDG request BUILD_IntraCDG(\(IntraCDG\)[\(\alpha\)]); if(\(\exists\)Edge(\(CKP_{a}\), \(CKP_{b}\)) \(\land\)IntraCDG[\(\beta\)])then CHANGE_IntraCDG(\(IntraCDG\)); //modifyIntraCDG\({}_{j}\) CHANGE_InterCDG(\(R\_InterCDG\)); if(\(\exists\)Edge(\(CKP_{b}\), \(CKP_{a}\)) \(\land\)IntraCDG[\(\beta\)])then CHANGE_IntraCDG(\(IntraCDG\)); CHANGE_InterCDG(\(S\_InterCDG\)); BUILD_SubInterCDG(\(R\_InterCDG\), \(S\_InterCDG\), \(P_{t}\)); //build subgraph related to \(P_{t}\) SEND_SubInterCDG(\(CH_{i}\)); //send subgraph to \(CH_{i}\) CHANGE_InterCDG(\(R\_InterCDG\)); CHANGE_InterCDG(\(S\_InterCDG\));
```

**Algorithm 5****OldCluster_CKPUpdate()**

#### 7.2.2 Update of Checkpoints Dependence Relation in New Cluster

Firstly, it needs to add the processes in \(PS\) to \(PL_{i}\). When \(CH_{i}\) receives the subgraph \(SubInterCDG\) from \(CH_{k}\), it adds the edges ended by the checkpoints of processes in \(PS\) to \(R\_InterCDG_{i}\) and adds the rest to \(S\_InterCDG_{i}\). Then \(CH_{i}\) builds new relations of same cluster for the processes in \(PS\), namely updates the \(IntraCDG_{s}\) and \(DL_{s}\) of related checkpoints. Let \(P_{t}\in PS\), \(P_{s}\in C_{i}\). \(CKP_{c}\) and \(CKP_{d}\) are the checkpoints of \(P_{t}\) and \(P_{s}\), respectively. The algorithm for updating checkpoints dependence relations in a new cluster is described as the Algorithm 6. ## 8 Performance Test and Analysis

### Experiment Environment and Parameters

This experiment builds a simulation environment of a mobile ad hoc network based on Windows XP. The simulation network consists of five clusters. Each cluster includes 5 MHs. The routing protocol in the experiment is the Ad hoc On-Demand Distance Vector Routing (AODV).