To minimize energy consumption and response time, a replacement node should be a redundant sensor geographically closest to the failed node. Thus, replacement discovery is a distance-sensitive service discovery problem, where redundant sensors as service provider offer replacement service to failed sensors. After replacement discovery, discovered replacement will be migrated to the position of failed sensor. Replacement migration can be accomplished in a direct way or in a shifted manner (Section 10.3).
Many service discovery algorithms (Gao et al., 2006; Mian et al., 2006) have been proposed for wireless ad hoc networks. They can certainly be used to fulfill the replacement discovery problem. Some techniques such as location service (Chapter 8) and data centric storage (Li et al., 2008c) can also be adopted. By location service, redundant sensors update the network with their location and are searched when needed. By data centric storage, the location data of redundant sensors are stored somewhere in the network and retrieved by others. But, considering the resource constraints of sensors, a good solution should have low message overhead and constant per node storage load.
There exist a few sensor relocation algorithms in the literature. In the following sections, we group these algorithms according to their employed replacement discovery methods and review them in detail.
Wang et al. (2004b) proposed a proxy-based sensor ...