network coding

Cai et al.(2013) and  Cai and Han (2014) presented the polynomial time algorithms for two-pair and three-pair networks with common bottleneck links, respectively. Also, Chen and HaiBin(2012) proposed a non-polynomial time algorithms for $n$-pair networks with common bottleneck links, where $n$ is an arbitrary integer. This paper presents a new sufficient and necessary condition to determine the solvability of single rate $n$-pair networks with common bottleneck links, which concludes a polynomial time algorithm for $n$-pair networks with common bottleneck links, where $n$ is an arbitrary integer. Our algorithm runs in $O(|V||E|^{2})$ time, where $|V|$ and $|E|$ are the number of nodes and links, respectively.

The Wireless Sensor Networks (WSNs) include a number of fixed sensor nodes so that each sink moves to collect data between nodes. It is necessary to determine the optimum route and residence location of mobile sinks to reduce energy consumption and increase the value of collected data, which causes increasing the lifetime of WSNs. Using Network Coding (NC), this paper presents a Mixed Integer Linear Programming Model to determine the multi cast Sink Optimal Route (SOR) of Source Sensor Nodes (SSNs) to mobile sinks in WSNs which determines the time and location of sinks to collect maximum coded data and reduce the delay in sinks movement and energy consumption. Since solving this problem is not possible in polynomial time due to the multiple parameters and the limited resources of WSNs, therefore, several heuristic, greedy and fully distributed algorithms are proposed to determine the movement of sinks and their residence location based on maximizing the Value of Collected Coded Data (VCCD) and the type of data deadline. It is demonstrated, by simulation, that the optimal model and the use of NC and proposed algorithms, causes reducing the energy consumption and increasing the Value of Collected Coded Data and network lifetime than non-NC methods.

In recent years, Network Coding (NC) has been used to increase performance and efficiency in Wireless Sensor Networks (WSNs). In NC, Sensor Nodes (SNs) of network first store the received data asa packet, then process and combine them and eventually send them. Sincethe bandwidth of edges between SNs is limited, management and balancing bandwidth should be usedfor NS. In this paper, we present an optimization model for routing and balancing bandwidth consumption using NC and multicast flows in WSNs. This model minimizes the ratio of the total maximum bandwidth to the available bandwidth innetwork's edges and we use the dual method to solve this model. We also use the Karush–Kuhn–Tucker conditions (KKT) to calculate a lower bound and find the optimal solution and point in optimization model. For this purpose, we need to calculate the derivative of the Lagrangian function relative to its variables, in order to determine the condition as a multi-excited multi-equation device. But since the solution of equations KKT is centralized and for WSNs with a large number of SNs, itis very difficult and time consuming and almost impractical, we provide a distributed and repeatable algorithm for solving proposed model in which instead of deriving derivatives, combination Sub-gradient method and network flow separation methodare used, thus allow each SN locally and based on the information of its neighboring nodes performs optimal routing and balances bandwidth consumption in the network. The effectiveness of the proposed optimization model and the proposed distributed algorithm with multiple runs of simulation in terms of the number of Source SNs (SSNs) and Lagrange coefficient and step size have been investigated. The results show that the proposed model and algorithm, due to informed routing and NC, can improve the parameters of theaveragerequired time to find the route optimal, the total amount of virtual flowin network’s edges, the average latency end-to-endof the network, the consumed bandwidth, the average lifetime of the network and the consumed energy, or not very weak compared to other models. The proposed algorithm also has great scalability, because computations are donedistributed and decentralized,andthere is aninsignificantdependence between the SNs.