# Energy-Efficient Wireless Hopping Sensor Relocation Based on Prediction of Terrain Conditions
## 3 The Proposed Relocation Protocol for Rugged Terrains
### Basic Operation of the Proposed Relocation Protocol  
In this section, we propose a novel relocation protocol that takes into account the environment surrounding the sensing hole occurred. Figure 4 shows the message flows between hopping sensors that the types are cluster header, relay node, and member sensor node. The detailed formats of the messages for the proposed relocation protocol and the message flows for each sensor node are described in detail as follows. Figure 3: An example of recovering a sensing hole with cross-clusters. **Step 1**: The cluster header of the cluster zone A periodically broadcasts a HELLO message inside its zone to identify member sensor nodes. If a member node receives HELLO for the first time, the source address of the received HELLO message is memorized as its cluster header. HELLO: = {message type, source address, destination address (broadcasting)}  
**Step 2**: The member that received the HELLO message responds to the cluster header with a HELLO-ACK message to notify its health. If different HELLO messages are received from several cluster headers in Step 1, the member node is aware of that it has become a relay node for each cluster header. Thus, it also indicates whether a relay node or not, when the HELLO-ACK message is replied. HELLO-ACK: = {message type, source address, destination address, relay node? (T/F)}  
**Step 3**: The cluster header determines whether or not, currently, its zone is a sensing hole using the number of addresses of HELLO messages received. In the case of a sensing hole, the cluster header sends a relay message to all its relay nodes. RELAY: = {message type, source address, destination address (multicasting)}  
**Step 4**: As soon as the relay nodes receive the RELAY message, they send a RELAY-ACK message back to the cluster header. The cluster header may sequentially receive several RELAY-ACK messages. Among them, the relay node of the RELAY-ACK message, which is first received at the cluster header, is selected and other RELAY-ACK messages are ignored. Also, if a relay node overhears a RELAY-ACK message from another relay node while preparing to send a RELAY-ACK message, it immediately stops sending its message. RELAY-ACK: = {message type, source address, destination address}  
**Step 5**: So far, the cluster header is able to detect that a sensing hole has occurred (Step 3), and it could choose a relay node to forward a message to the neighbor cluster header for requesting member hopping sensor nodes needed (Step 4). Here, the required number of members is the difference (\(T-C\)) between the threshold value (\(T\)) to determine the sensing hole and the current number of members  
Figure 4: Scenario and message flow diagram for describing the proposed protocol. (_C_). However, the environment around the detected sensing hole may be rough terrain in reality, the sensing hole would continue because it might be high probability that the number of relocated hopping sensors is smaller than the requested number (\(T-C\)). Therefore, the cluster header checks the numbers of previously requested members and successfully moved members and calculates the movement success rate (\(p\) = number of members successfully moved/number of members requested) of the surrounding environment for the current cluster zone. Here, the number of requesting member sensors (\(cnt\)) that can overcome the sensing hole can be calculated as follows. \[cnt:=\text{Ceiling}[(T-C)*(1+(1-p))] \tag{2}\]  
The cluster header sends a REQ message to the selected relay node. REQ: = {message type, source address, destination address, \(cnt\), sensing hole address, sensing hole GPS info.} **Step 6**: When the relay node receives the REQ message from the cluster header of the sensing hole occurred, it forwards the received REQ message to another cluster header. Here, the source and destination addresses of the currently received REQ message are modified to its own address and the address of the another cluster header to be delivered, respectively.