Network coding has been used in recent years to improve the quality of service of wireless networks, by reducing data transmission and energy consumption. Network coding allows intermediate nodes of the network to encode several packets into a single packet, and then broadcast, i.e., transmit simultaneously to all neighbours only once. Broadcasting is the term used to describe communication where the data packets are sent from one node to all other connected nodes; a single sender transmits data, and the data is sent to all connected receivers.
In wireless networks interference has a significant impact on energy consumption, network routing and performance. Wireless communication relies on shared communication media, that can be accessed by several devices, close to each other, at the same time. Interference is caused by simultaneous transmissions between these devices.
Routing strategies have a major impact on the total energy consumption of networks. In multi-hop WSNs each communication is routed through a single path, i.e., unsplittably from its source node to its target node. Unsplittable routing allows intermediate nodes to use less memory, speeds up packet handling processes, minimizes loss rates and enables better quality of service (QoS). Unsplittable routing can be modelled as the integer programming formulation of unsplittable multi-commodity flow (UMCF) problems. The state-of-art method to solve UMCF is the branch-and-price algorithm, and the branch-and-price algorithm employs the column generation approach to speed-up the resolution of the Linear Programming relaxation.
In this work, we study the integration of network coding into the routing process in wireless networks under interference, the problem is named as wireless unsplittable multi-commodity flow with network coding (wUMCFC).

Contributions:

We analyse and model the effects of network coding on the energy cost and the capacity usage under the network interference. The wUMCFC problem is formulated into an integer programming problem.
We propose three compact mixed-integer formulations:

- one mixed-Boolean quadratic programming (MBQP) formulation;

- two mixed-integer linear programming formulations: edge linearization formulation and edge balance formulation.

The edge linearization formulation is a direct linearization of the MBQP formulation via McCormick envelopes of bilinear terms, while we prove that the LP relaxation of edge balance formulation is stronger than that of the edge linearization formulation. To scale up with large networks, we derive a path-based reformulation of the edge balance formulation. In particular, we show that the pricing sub-problem can be solved efficiently by the polynomial-time algorithm. We propose an exact approach based on the branch-and-price algorithm. We implement the open source branch-and-price based solver wUMCFC. Our computational tests show the speedup of wUMCFC over CPLEX on simulated networks. The employment of network coding reduces 18.3% of routing energy cost onaverage.