## 4 RoCoMAR Algorithm
### Wireless Link Reinforcement
When the REI node receives the data packet from RN, it sends a REI-REP message to node \(D\) indicating that a new relay node is successfully added. Each RN has two states: _Stand-by_ and _Relaying_. A RN is initially in _Stand-by_ state, and switches to _Relaying_ state after it sends a _CHG-NEXT-HOP_ message to the predecessor node. If a RN receives multiple _MREQs_, it accepts the first request and discards others. However, in order to allow a RN to relay data for multiple flows that share the same link, a RN accepts a relay request for the same link for which it is already working as a relay. When the data transmission on path finishes or it receives a _RES-REQ_ (Resign Request) from the REI node, the RN switches to _Stand-by_ state. Figure 2 illustrates an example of the reinforcement process. As shown in the example of Figure 2, each node on the path (e.g., \(A\), \(B\) and \(C\)) appends the PDR value of its link to the data packet header (1). When node \(D\) receives the data packet which consists of the PDR values of links, it calculates \(R_{ete}\). Assume that \(R_{ete}\) is less than \(R_{req}\), and the link between \(B\) and \(C\) is the link with the lowest quality on the path. Then node \(D\) sends a _REI-REQ_ to node \(C\) to request for a new relay node (2). When node \(C\) receives _REI-REQ_ (2), it becomes a REI node and selects \(RN1\) as a new relay and sends \(MREQ\) to RN1 (3). Upon receiving \(MREQ\), the RN1 moves to the midpoint position of the link between node \(B\) and node \(C\) (4). When the RN1 arrives at position of the midpoint of link between node \(B\) and node \(C\), it sends the _CHG-NEXT-HOP_ message to node \(B\) (5) and adds itself to the route from node \(S\) to node \(D\). Node \(B\) updates its routing table and starts forwarding the data packets to RN1 (6). When node C receives the first data packet from RN1 (6), it sends a _REI-REP_ that indicates that a new relay node is successfully added (7). The repeated link reinforcement process algorithm for a destination node is presented in Algorithm 1. Let \(R_{c}\) and \(R_{b}\) denote the current end-to-end PDR value and the end-to-end PDR value before a RN is added to the route, respectively. \(G\) denotes the set of nodes in the network. The _link reinforcement_ process is repeatedly performed until the required end-to-end PDR, \(R_{req}\), is achieved or no more gain on PDR can be obtained. As presented in Algorithm 1, the destination node \(D\) uses \(R_{c}\), \(R_{b}\), and \(R_{req}\) value to determine whether or not it initiates a new link reinforcement process. In order to initiate a new reinforcement process, \(R_{c}\) should be less than \(R_{req}\), and the PDR gain by the latest reinforcement should not be negligible, _i.e._, \(R_{c}\geq R_{b}(1+\xi)\) as shown in line 5 in Algorithm 1, where \(\xi\) represents a system parameter for the PDR gain ratio. The value of \(\xi\) affects the network performance. A too small value of \(\xi\) can result in a lot of unnecessary reinforcement processes without a significant performance gain. On the other hand, a large value of \(\xi\) may prevent the network from  
Figure 2: An example of link reinforcement process. placing a new relay node even when some degree of performance gain is expected. If \(R_{c}\) is less than \(R_{b}\) (_i.e._, placing a new relay actually lowers the end-to-end PDR), then the newly added RN is removed from the route. Note that node \(D\) iteratively checks whether or not it can initiate a new reinforcement process every time interval \(t_{rei}\).