# Data Gathering Techniques in WSN: A Cross-Layer View
## 5 Routing for Data Gathering in WSN
### Network Coding (NC)
In RLNC, relays transmit random linear combinations of the packets they receive, with randomly chosen coefficients from a finite Galois field (GF). The receiver must obtain a sufficient number of linearly independent combinations (packets) to decode the original packets. If the GF size is sufficiently large, the probability that the randomly generated combinations will be linearly independent is high. However, the receiver needs to know the coefficient used in each combination; hence, it needs to be sent as overhead piggybacked on each traversed packet. The larger the GF size, the higher the overhead. RLNC scheme with distributed encoding was utilized by [PERSON] et al. [165] for a perimeter data-gathering objective, in which the data should reach the perimeter nodes that are located on the boundary of the covered area. The proposed scheme does not deploy routing algorithms or maintain routing information and relies on random walks. One disadvantage of RLNC is its decoding complexity in the order of \(O(n^{3})\), where \(n\) denotes the number of original packets. Sparse end-to-end erasure-correcting codes can reduce the decoding load on the receiver at the cost of introducing an additional, non-negligible delay. [PERSON] et al. [166] suggest a tunable sparse network coding (TSNC) scheme that tunes the level of sparsity as the transmission process evolves. This tuning process can reduce the delay overhead by using denser codes towards the end of the transmission while maintaining the complexity advantages of a sparse code. [PERSON] et al. [167] propose two network coding schemes for information gathering, which are based on tunable sparse codes, with and without explicit feedback from the sink. The suggested schemes are designed for meter readings in a smart grid. [PERSON] et al. [168] further exploit RLNC and TSNC for data gathering and derived analytical bounds for a multi-hop line network using a fluid model, which is valid for any field size and various sparsity levels, and has two different feedback mechanisms. SenseCode [169] adopts the NC paradigm, aspiring to balance energy efficiency and end-to-end packet error rate. SenseCode relies on nodes transmitting both uncoded and coded packets. Each node stores only a small portion of the packets it overhears, which can be attained by letting the node wake up sporadically within its duty cycle and stay awake for a short time interval each time it wakes up, storing overheard packets. Accordingly, each coded packet comprises only a small subset of the packets the node could have potentially overheard and coded. NetCoDer [170] concentrates on a star topology in which the star-head can be a sink or a relay that collects information from its neighbors. NetCoDer opportunistically selects, based on network conditions, a set of relays that, in addition to the data sent by the nodes, send additional coded packets with packets they overheard, which helps the star-head recover lost packets. To reduce the overhead, the relays use LNC coefficients based on the addresses of the sensor nodes. A similar idea that also does not rely on feedback was presented in SR-Code [171] in which nodes and relays send redundant coded messages to help the sink recover lost messages. SR-Code utilizes the XOR operator (GF(2)). Similar to NetCoDer, SR-Code reduces the overhead by using a bitmap to identify the coded packets rather than the address of the sending node. [PERSON] et al. [172] assume a data-gathering setup with single or multiple gateways (sinks) that can collaborate (exchange information via accessible shared distributed storage system). The paper distinguishes between traditional relays, which forward packets they receive as-is, and encoding relays, which perform network-coding on the packets they receive before forwarding them.