## 4 RoCoMAR Algorithm
### Adaptive Link Maintenance  
RoCoMAR enables the network not only to keep high quality links but also to prevent links from being broken, which results in a significant improvement of routing protocol performance. In this subsection, we describe RoCoMAR's adaptive link maintenance algorithm, which allows RNs to adjust their positions according to the network topology change and to prevent link breakage by working with the link reinforcement algorithm. RNs perform the adaptive link maintenance when they work as relay nodes. After each RN becomes a relay node, it periodically updates the positions of its predecessor (referred to as PRE node hereafter) and its next-hop node (referred to as NEXT node hereafter) on the path from the source to the destination, using the information obtained from the received _Hello_ messages. Then, the RN relocates itself to the midpoint position of the segment between its PRE and NEXT nodes at every \(t_{alm}\) seconds. The system parameter \(t_{alm}\) is set considering the speed of the RN's PRE and NEXT nodes and the speed of RN itself such that the links of RN with the PRE and NEXT nodes would not be broken or the links' PDR values would not become less than a specific threshold value. It is possible that the PRE and NEXT nodes of a RN become close each other as they move, and hence the PRE and NEXT nodes could establish a high quality direct link. RoCoMAR's adaptive link maintenance allows a RN to detect this situation and resign as a relay. More specifically, the NEXT node calculates the PDR value of the potential link with the PRE node based on _Hello_ messages received from the PRE node. This PDR value is added to the NEXT node's _Hello_ messages so that the RN can also know the PDR value. When the PRE and NEXT nodes can have a direct link with a consistently high quality (_i.e._, placing a relay node is unnecessary or even wasteful), the RN sends a _CHG-NEXT-HOP_ message to its PRE node which leads to establishment of a direct link between the PRE and NEXT nodes. Note that the PRE and NEXT nodes may be either RNs or regular nodes. In other words, in RoCoMAR, multiple RNs can work as relay nodes in a row between two regular nodes. This feature of RoCoMAR is particulary useful when one or a group of nodes moves far away (e.g., for searching or following some events in the operation) and still needs a communication link with the rest nodes in the network. Also note that when those nodes are returning to the rest nodes, the RNs detect this and _adaptively_ resign as a relay. Figure 3 illustrates an example of the adaptive link maintenance process for the route from node \(S\) to node \(D\) as the network topology changes over time. As shown in Figure 3, at time \(t_{1}\), RN2 is a relay node between node \(A\) (PRE node) and node \(B\) (NEXT node). RN2 periodically updates its position to follow the midpoint position of node \(A\) and \(B\). In addition, as shown in Figure 3, at time \(t_{2}\) RN1 becomes a relay node of the link between node \(S\) and node \(A\) after it receives a _MREQ_ from node \(A\). After some time, RN1 detects that PDR value of the link between node \(S\) and \(A\) is greater than the required PDR value, and RN1 resigns as a relay and switches its state to _Stand-by_. At time \(t_{3}\), as node \(A\) and node \(B\) move apart, the quality of link between node \(A\) and RN2 becomes poor, and RN2 sends a _MREQ_ message to RN1 to request to become a relay. Then, RN1 becomes a new relay between node \(A\) and RN2 and moves to the midpoint of them and RN2 also moves accordingly to the midpoint of RN1 and node \(B\). The link reinforcement and adaptive link maintenance algorithms for a RN is presented in Algorithm 2. \(R(u,v)\) denotes the PDR value of link between \(u\) (data sender) and \(v\) (data receiver). Also, \(mid(u,v)\) is defined as the midpoint position of node \(u\) and \(v\). As shown in Algorithm 2, when the \(R(u,v)\)  
Figure 3: An example of an adaptive link maintenance process over time.