## 4 RoCoMAR Algorithm
### Wireless Link Reinforcement  
In RoCoMAR, each node maintains two lists of geographical positions: one list for its neighboring nodes, and another for its one-hop and two-hop neighboring RNs. In order for nodes to obtain the two-hop neighboring RNs' information, each node in the network appends the one-hop RN information to its _Hello_ message, which also contains the position of itself and is periodically broadcasted. Suppose that the source node \(S\) needs to send data packets to the destination node \(D\). After node \(S\) finds a route using AODV (or using other ad hoc routing protocols), node \(S\) sends data packet to node \(D\) through this route. When a node receives a data packet from the predecessor on the path, it appends the current PDR value of the link with its predecessor to the header of the data packet (PDR value is used to estimate the link quality, and the calculation of PDR will be discussed in detail in Section 4.3). When node \(D\) receives a data packet, it extracts the PDR values of all links on the path and calculates the end-to-end PDR value of route, \(R_{ete}\),which is  
\[R_{ete}=\prod_{i=1}^{n}R_{i} \tag{1}\]  
where \(n\) and \(R_{i}\) represent the number of links on the path and the PDR value of \(i^{th}\) link. Note that \(R_{ete}\) is a simplified approximation of the end-to-end PDR assuming subsequent transmissions are independent. Then, node \(D\) compares the current value of \(R_{ete}\) with a required PDR value, \(R_{req}\), which is specified by the user application. If the current end-to-end PDR value of the route is less than \(R_{req}\), the node \(D\) determines the link that has the lowest PDR value (or the poorest link). Then, node \(D\) sends a reinforcement request _(REI-REQ)_ message to the data-receiving node of the poorest link, which is referred to as REI (reinforcement) node hereafter. Upon the reception of _REI-REQ_ message, the REI node sends an \(ACK\) message to confirm the reception. If node \(D\) does not receive the \(ACK\) after \(k\) time retransmissions of REI-REQ message, it selects another link to reinforce. If the node \(D\) receives the \(ACK\) message to the REI-REQ message, it waits for reinforcement reply _(REI-REP)_ message, which indicates whether or not the placement of new robotic relay has been successfully performed. Upon receiving _REI-REQ_, the REI node determines an optimal position where a new RN should be relocated. RoCoMAR uses a simple yet effective heuristics that places a RN in the midpoint of the poor link, which results in maximization of the link quality and minimization of the transmission power [10]. Robotic node can be placed in another position if it cannot be placed at the initially determined position due to obstacles or other geographic features. The algorithm for placing a robotic relay avoiding obstacle is out of the scope of this paper, and in this paper it is assumed that the RN can be relocated to the midpoint. After the REI node determines the position of new relay, it looks up the list of neighboring RNs and chooses a RN that is closest to the position where a new relay should be placed. When a RN is selected, the REI node sends a move request _(MREQ)_ message which contains the network address of its predecessor on the data path and the position to which the RN should move. If the REI node does not receive \(ACK\) to _MREQ_ after \(h\) time retransmissions, it selects another RN in the list unless the list is empty. If the REI node could not select any RN, it informs node \(D\) of this failure using _REI-REP_ message. When a RN receives _MREQ_, it starts moving immediately to the position that is indicated in _MREQ_. Upon arrival at the dictated position, the RN sends an _CHG-NEXT-HOP_ (change next hop) message to the predecessor node of the REI node on the path, so that the predecessor node updates its routing table and forwards the data packets to the RN from that time on. The RN also adds a route entry that contains the REI nodes as the next hop.