Minimizing Transmission Cost for Third-Party Information Exchange with Network Coding
In wireless networks, getting the global knowledge of channel state information (CSI, e.g., channel gain or link loss probability) is always beneficial for the nodes to optimize the network design. However, the node usually only has the local CSI between itself and other nodes, and lacks the CSI between any pair of other nodes. To enable all the nodes to get the global CSI, in this paper, we propose a network-coded third-party information exchange scheme, with an emphasis on minimizing the total transmission cost for exchanging the CSI among the nodes. We show that for a network of N nodes, if and only if any k nodes (1 _ k < N) send at least k2 packets, a feasible solution exists for third-party information exchange. Formulating the problem of feasible and optimal solutions as an integer linear programming (ILP) problem, we compute the optimal number of packets that must be transmitted by every node. Guided by the necessary and sufficient condition, we construct two practical transmission schemes: fair load (FL) scheme and proportional load (PL) scheme. A deterministic encoding strategy based on XORs coding over GF(2) is further designed to guarantee that with FL or PL scheme, each node finally can decode the complete packets. It is shown that in two specific networks, these two schemes are optimal, achieving the minimum transmission cost. In more general networks, simulation results show that PL is still close to optimal with a high probability. Finally, a distributed transmission protocol is developed, which allows FL and PL schemes to be operated in a distributed and hence scalable manner.
Network coding, a cross-layer technology that was initially developed for static (wireline) networks has received extensive research attention in wireless community, due to its significant benefits in improving wireless performance including throughput, reliability and etc.
Recent studies show that network coding can also help reduce the number of transmissions or the transmission delay/cost for general cooperative data exchange.
An earlier study of third-party information exchange demonstrated the existence of optimal solutions, where the optimality is measured in terms of minimizing the total number of transmissions.
The existing researches on cooperative data exchange mainly focus on minimizing the total number of packets required to exchange, the total transmission cost/delay or fixing the security issues.
DISADVANTAGES OF EXISTING SYSTEM:
The problem of third-party information exchange presents a special case of the general problem of cooperative data exchange.
However, finding the deterministic code design to achieve these limits for cooperative data exchange can be non-trivial as it needs very high field size, and the complication comes, in part, from the very general setup of cooperative data exchange.
In this paper, we further study network-coded third party information exchange with the objective of minimizing the total transmission cost. Different from previous works, we aim to propose an efficient and scalable transmission scheme which can tell the exact number of packets that should be sent by each node. Besides that, we also aim to design an efficient deterministic encoding strategy, which not only can achieve good performance, but also has a very low encoding/decoding complexity (e.g., with a very low coding field size). We call a deterministic coding and transmission scheme feasible if it allows all the nodes to eventually deduce all the global CSI, and we call a feasible solution optimal if it also minimizes a certain cost metric.
The goal of this paper is to develop constructive, feasible solutions (including how many packets for each node to transmit and how they are encoded and decoded) that are optimal with respect to the total transmission cost.
We construct two efficient and feasible transmission schemes, and prove that the proposed two schemes will achieve optimality (with respect to the total transmission cost) under two specific scenarios.
A deterministic encoding strategy is designed and can be used in combination with the proposed schemes to ensure the successful deduction of all desired packets at each node. Different from previous works on minimizing transmission cost, the proposed encoding strategy is based on XORs coding over only GF(2), which has very low complexity.
We also develop a practical distributed transmission protocol that enables the proposed two transmission schemes to be operated in a distributed and hence scalable manner.
ADVANTAGES OF PROPOSED SYSTEM:
Common control channel is available which allows reliable broadcast by any node to all the other nodes.
We formulate the problem of minimizing the total transmission cost as an integer linear programming (ILP) problem. We show that the optimal solution is one of “water-filling” nature, and a node with lower transmission cost should therefore send more packets than the node with higher transmission cost.
The deterministic encoding strategy helps in achieving good performance
The system is optimal with respect to the total transmission cost.
The system also ensures the successful deduction of all desired packets at each node.
System : Pentium IV 2.4 GHz.
Hard Disk : 40 GB.
Floppy Drive : 44 Mb.
Monitor : 15 VGA Colour.
Ram : 512 Mb.
Operating system : Windows XP/7/LINUX.
Implementation : NS2
NS2 Version : 2.28
Front End : OTCL (Object Oriented Tool Command Language)
Tool : Cygwin (To simulate in Windows OS)
Xiumin Wang, Chau Yuen, Tiffany Jing Li, Wentu Song, and Yinlong Xu, “Minimizing Transmission Cost for Third-Party Information Exchange with Network Coding”, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 6, JUNE 2015.