# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 2 Ad Hoc Network Structure and Hybrid Checkpointing Model
### Hybrid Checkpointing Model  
As we know, the different kinds of resources on MH\({}_{\text{s}}\) are quite limited in mobile ad hoc networks. These resources include the storage space, processing capacity, battery energy, wireless bandwidth and so on. If we fully adopt the asynchronous checkpointing algorithm, it will need to transmit a lot of checkpoint coordination messages. Because the communication among MH\({}_{\text{s}}\) in different clusters usually needs multi-hop routing before reaching the destination, the number of checkpoint coordination messages is proportional to the number of hops and the retransmission will occupy precious wireless bandwidth. Though it will avoid a lot of checkpoint coordination messages if we completely use the asynchronous checkpointing algorithm, the cascade rollback caused by asynceshronous checkpointing would waste resources such as precious CPU allocation and power sources of MH\({}_{\text{s}}\) and the storage space for storing checkpoint information is large. Therefore, this paper plans to adopt the hybrid checkpointing model which combines the synchronization and asynchronization after considering the kinds of resource limitations in MH\({}_{\text{s}}\) synthetically. In this model, the hosts in the same cluster use the synchronous checkpointing (because these hosts could communicate with each other directly without the retransmissions involving cluster heads), while the hosts in different clusters adopt the asynchronous checkpointing. This will not only avoid the waste of all kinds of resources for hosts in same cluster because of cascade rollback, but also avoid too many transmissions of messages among hosts in different clusters. What is more, it reduces the communication delay of the network and checkpoint operation delay. **Definition 1**. : _A same cluster checkpoint (SC) is a checkpoint which is used for ensuring the consistency of processes in hosts of the same cluster._  
The SC is a synchronous checkpoint. Every time the process use a SC, it needs to remain synchronous with the related processes in the same cluster. During the synchronization procedure, if part of processes cannot finish their checkpoints because of their own reasons, then the coordinated checkpoints become useless checkpoints which need to be eliminated. Hence, in order to reduce the occupation of precious storage space in wireless terminals, the SC\({}_{\text{s}}\) can be further divided into two kinds: uncertain checkpoints and certain checkpoints. **Definition 2**. : _An uncertain checkpoint is a SC which is stored in the cache of a MH when the coordination is not finished._  
**Definition 3**. : _A certain checkpoint is a SC which is stored on the local disk of a MH when the coordination is finished._  
Figure 1: Multi-frequency hierarchy topological structure. Therefore, if and only if the coordination of checkpoints succeeds, the uncertain checkpoints could be turned to certain checkpoints. Otherwise, the uncertain checkpoints become useless checkpoints which could be eliminated. The elimination of uncertain checkpoints involves releasing the information stored in the cache. **Definition 4**. : _A different cluster checkpoint (DC) is a checkpoint which is used for assuring the consistency of processes in MHs of different clusters._  
The DC is an asynchronous checkpoint. When a process receives messages from MH\({}_{\text{s}}\) of different clusters, it finishes the checkpoint operation independently without informing other MH\({}_{\text{s}}\). The DC is triggered by the reception of messages from MH\({}_{\text{s}}\) of different clusters and its checkpoint information is directly stored in the local disk of the MH, so the DC is a certain checkpoint in nature. Suppose \(P_{i,j,k}\) expresses a process, \(i\) is the id of cluster which the mobile terminal stays, \(j\) is the id of mobile terminal and \(k\) expresses the id of process. Figure 2 is an example of hybrid checkpoint model.