# Data Gathering Techniques in WSN: A Cross-Layer View
## 5 Routing for Data Gathering in WSN
### Network Coding (NC)  
Network coding leverages the routing protocols and the ability to construct multi-path routing between sources and their destination (the sink) to enable intermediate nodes to perform coding on the incoming packets before forwarding them. In the following section, we discuss network-coding-related works. Linear network coding was first introduced by [PERSON] and [PERSON] [153] and evolved in the seminal paper by [PERSON] et al. [154] as a means to improve the network's throughput, efficiency, and scalability, which can also be leveraged to improve the network resilience to attacks and eavesdropping. Linear network coding allows the network's intermediate nodes (e.g., relays) to accumulate arriving messages and forward a newly encoded message, which is a linear combination of the accumulated packets, multiplying them by coefficients chosen from a finite field. The manner in which nodes encode and decode messages depends on the selected coding scheme. Network coding (NC) over wireless communication can reduce the number of transmissions by leveraging the fact that a single transmission is overheard by multiple nodes in the transmitter's vicinity, and can therefore be utilized by each of these nodes, which will forward a coded packet with unique coefficients comprising its own message and the messages it overheard (e.g., [155]). In WSNs, NC can be utilized for various traffic patterns, including data dissemination (one-to-many communication) and data gathering. Works on energy-efficient NC-based dissemination can be followed in the survey [156], with multi-hop routing being emphasized. In data dissemination in which the base station/sink distributes information to the sensor nodes, NC is beneficial mainly for distributing _control_ messages (broadcast or multicast traffic) or, in case of unicast traffic, for recovering lost packets (retransmissions). The latter utilization relies on the fact that different nodes heard or did not hear different packets. Accordingly, nodes store packets they overheard, even if not destined to themselves. The transmitter (e.g., access-point) accumulates several packets that need to be retransmitted, each for a different receiver. It transmits a coded packet that is a composite of these accumulated packets. Each receiver can decode a missing packet by utilizing its stored overheard packets (e.g., [157; 158; 159; 160; 161; 162], where the last two mainly focus on data dissemination of control management messages. It is noteworthy that [PERSON] et al. [157] also present a successful real HW radio deployment of their scheme. XOR-CoW [163] exploits the same concept to design an IoT protocol in which relays transmit coded packets that mix downlink and uplink traffic. Similar to other previously mentioned studies, the coding scheme by [PERSON] et al. [163] is over finite Galois field of size 2 (GF(2)) (i.e., XORing the coded packets). Network coding is widely explored for data-gathering schemes. Typically, an NC-based protocol involves both the coding scheme and the multi-path routing. It relies on the relay nodes to overhear packets and perform the coding, and on the sink (or multiple sinks) to collect sufficient coded packets (combinations) to encode the sent information. The limited ability of the sensors constrains NC over WSN (e.g., limited storage to store overheard packets, limited computation power to perform sophisticated operations, limited awake time for packet overhearing, etc.). The utilized coding scheme influences the performance of the NC algorithm in several aspects such as the throughput, algorithm complexity, encoding complexity, decoding complexity, packet overhead (bits), required feedback, and so on. Note that many of these metrics are directly translated to air time and energy consumption, which must be considered in WSN. The random linear network coding (RLNC) encoding scheme (e.g., [164]) is widely used because, despite its simplicity, it can attain throughput that is close to the optimal one using a decentralized algorithm.