# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
### Network Coding Approaches  
To truly enhance the performance of multi-hop wireless communications with packet loss and a large number of hops, the intermediate network nodes have to adopt a strategy other than forwarding. Random linear network coding (RLNC) [14] is a realization of network coding [15, 16] that allows the intermediate network nodes to transmit new packets generated by the received packets. Previous works showed that RLNC can achieve the capacity of networks with packet loss for a wide range of scenarios [14, 17, 18, 19, 20, 21]. Instead of forwarding, recoding (i.e., re-encoding) is performed at the intermediate network nodes, which generates recoded packets by linearly combining the received packets randomly. Various directions on applying RLNC were investigated in the literature, such as machine learning approaches [22], secure communications [23, 24], speedup via codebook design [25], hardware implementations [26, 27], vehicular networks [28, 29], mobile networks [30, 31], interactions with existing network protocols [32, 33], energy harvesting [34], and Internet of Things [35]. A direct implementation of the above RLNC scheme has a few technical problems and constraints. First, each intermediate network node has to buffer all the received packets, which may consume a huge amount of memory. Second, a coefficient vector being attached to each packet for recording the recoding operations is essential for decoding; however, the length of the vector can be very long when the number of input packets is large, which induces significant consumption of network resources. Third, the destination node has to solve a big, dense system of linear equations, which consumes significant computational resource for Gaussian elimination [36]. To resolve these several problems, a generation-based RLNC was proposed in [37]. In this approach, the input packets are first partitioned into multiple disjointed subsets called the generations. RLNC is then applied to each generation independently. This approach can be viewed as applying RLNC to multiple pieces of data (generations) independently. A generation can be discarded after its transmission. The main idea is that each generation is smaller than the original whole piece of data. Therefore, generation-based RLNC has smaller storage and computational requirements. Also, due to a smaller number of input packets in a generation, the length of coefficient vector is also shorter. However, the advantage of RLNC diminishes when the generation size is smaller--that is, we need a sufficiently large generation size to enjoy the gain of RLNC but the size cannot be too large; otherwise, we cannot mitigate the issues of RLNC mentioned above. Therefore, further optimizations on the design of generation-based RLNC were discussed and proposed in numerous stud ies, such as parallel decoding [38], speedup via codebook-based approach [39], smaller decoding delay and complexity [40; 41; 42; 43; 44; 45], input packet size selection [46; 47; 48; 49; 50], and coefficient overhead reduction [51; 52; 53]. In generation-based RLNC, data in a generation cannot be decoded using packets from another generation. The information carried by a generation has to be completely received in order to recover the data. This feature suggests that the optimal theoretical rate cannot be achieved. Towards the optimal rate, overlapped subsets of input packets were considered [54; 55; 56; 57]. More sophisticated approaches restrict the application of RLNC to small subsets of coded packets generated from the input packets [58; 59; 60; 61; 62; 63]. The coded packets can be generated by LDPC [60; 61], generalized fountain codes [62; 63], etc. This application of coding theory in network coding leads to another variant of RLNC called batched network coding (BNC). The small subsets of coded packets are called batches. In early literature, a batch is also known as a class [54], a chunk [55], or a segment [64].