# Energy and Distance-Aware Hopping Sensor
## 2 The Proposed Protocol to Relocate Hopping Sensors
### Basic Operation of Each Node-Specific Protocol for Sensing Hole Recovery  
In Figure 7, all headers periodically broadcast a HELLO message to maintain the information of their member sensor nodes. A timer helloMsgTimer of a predetermined time is executed for periodic  
Figure 5: A message sequence diagram for the example in Figure 4.  
Figure 6: An example of recovering sensing holes through relay relocation strategy.  
broadcasting. The member node adds the node that transmitted the HELLO as its own header and judges that it is a relay node when it has two or more own headers. In order to inform its header that the member node is a relay node, the member node sets the relayNode option to \"true\" in HELLO-ACK. The header that receives the HELLO-ACK adds the node that transmitted the HELLO-ACK as its own member and sets it as its own relay node if it is a relay node. If the number of members of the zone is less than a certain number, it can be determined that the cluster is a sensing hole.  
In Figure 8, if the header determines that its cluster is a sensing hole, it broadcasts a RELAY message to all relay nodes. The relay node receiving this message responds with a RELAY-ACK. The header sends an REQ message to the relay node that transmitted the first received RELAY-ACK. Successively, the relay node receiving the REQ delivers the REQ to its own header which is not in the sensing hole. However, it may happen that the cluster header of the sensing hole broadcasts the RELAY message but that a hopping sensor cannot be supplied for the sensing hole recovery.  
First, a relay node transmits a REQ message to a neighbor cluster header, but neighboring zones may also be sensing holes. In this case, the cluster header of the first sensing hole repeatedly broadcasts the RELAY message after a predetermined time (helloMsgTimer) and fails to receive the NEW message of the hopping sensor newly entered. Thus, the cluster header of the first sensing hole could suspend broadcasting of the RELAY message for a certain period of time, hoping that the neighboring zone is recovered from the sensing hole.  
Second, if all the relay nodes are dead, they will not receive the RELAY-ACK. In this case, the RELAY message is transmitted again after a predetermined time (helloMsgTimer). After a certain number of iterations, as in the first case, the broadcasting of the RELAY message could be stopped for a certain period of time. After the hopping sensors move from the neighboring zones, a sensor among these sensors is likely to become a new relay node, and a new protocol can be started from the new relay node.  
Figure 8: An attempt at recovering a sensing hole.  
Figure 7: The managing members and relay nodes in cluster headers.  
When a header receives a REQ message from a relay node, it immediately checks the number of movable members in its own cluster and compares with the number of requested members set in the REQ message, as shown in Figure 9.  
First, when the cluster has sufficient movable members more than the requested members, the ADV message is broadcasted to all its member nodes, and the member nodes receiving the ADV transmit the message ADV-ACK, including its location and energy information, to the header. The header receiving the ADV-ACK selects the movable members appropriately (with the weight was mentioned above in Section 2.2) and sends MOVE messages to the candidate members.  
Second, when the number of movable members is insufficient, the movable member can be moved to the sensing hole as much as possible. Due to this moving, its zone may become a sensing hole. In order to avoid this situation, it is possible to repeat the process of Figure 8 by transmitting the RELAY and REQ' to another relay node.  
Overall, the message flow of the hopping sensor relocation protocol described above is briefly summarized in Figure 10.  
Figure 10: The message flow of the proposed hopping sensor relocation protocol.  
Figure 9: The relocation strategy of a cluster header receiving the REQ message forwarded from Figure 8.