Transmission of Correlated Information Sources with Network Coding

This paper addresses the problem of the distributed delivery of correlated data sources with help of network coding. Network coding provides an alternative to routing algorithms and offers improved system performance, robustness and throughput, with no need of deploying sophisticated routing strategies. However, the performance is directly driven by the number of innovative data packets that reach the receiver. If the number of received innovative data packets is significantly small, the decoder cannot perfectly recover the transmitted information. However, we show that the correlation between the data sources can be used at decoder for effective approximate decoding. We analytically investigate the impact of the network coding algorithm, and in particular, of the size of finite fields on the decoding performance. Then, we determine an optimal field size that minimizes the expected decoding error, which represents a trade-off between quantization of the source data and probability of decoding error. The network coding with approximate decoding algorithm is implemented in illustrative multimedia streaming and sensor network applications. In both cases, the experimental results confirm the field size analysis and illustrate the effectiveness of approximate decoding of correlated data.

Network coding of correlated data with approximate decoding

Pascal Frossard, Hyung Gon Park, Nikolaos Thomos

We consider the problem of distributed delivery of correlated data from sensors in ad hoc network topologies. We propose to use network coding in order to exploit the path diversity in the network for efficient delivery of the sensor information. We further show that the correlation between the data sources can be exploited at receivers for efficient approximate decoding when the number of received data packets is not sufficient for perfect decoding. We analyze how the decoding performance is influenced by the choice of the network coding parameters and in particular by the size of finite fields. We determine the optimal field size that maximizes the expected decoding performance, which actually represents a trade-off between information loss incurred by quantizing the source data and the error probability in the reconstructed data. Moreover, we show that the decoding performance improves when the accuracy of the correlation estimation increases. We have illustrated our network coding based algorithms with approximate decoding in sensor networks and video coding applications. In both cases, the experimental results confirm the validity of our analysis and demonstrate the benefits of our solution for distributed delivery of correlated information in ad hoc networks.

2010

Lossy Network Correlated Data Gathering with High-Resolution Coding

Razvan Cristescu

Sensor networks measuring correlated data are considered, where the task is to gather data from the network nodes to a sink. A specific scenario is addressed, where data at nodes are lossy coded with high-resolution, and the information measured by the nodes has to be reconstructed at the sink within both certain total and individual distortion bounds. The first problem considered is to find the optimal transmission structure and the rate-distortion allocations at the various spatially located nodes, such as to minimize the total power consumption cost of the network, by assuming fixed nodes positions. The optimal transmission structure is the shortest path tree and the problems of rate and distortion allocation separate in the high-resolution case, namely, first the distortion allocation is found as a function of the transmission structure, and second, for a given distortion allocation, the rate allocation is computed. The second problem addressed is the case when the node positions can be chosen, by finding the optimal node placement for two different targets of interest, namely total power minimization and network lifetime maximization. Finally, a node placement solution that provides a tradeoff between the two metrics is proposed.

2006

Identity Aware Sensor Networks

Suhas Diggavi, Christina Fragouli, Mahdi Jafari Siavoshani, Lorenzo Keller

In a significant class of sensor-network applications, the identities of the reporting sensors are an essential part of the reported information. For instance, in environmental monitoring, the goal is to reconstruct physical quantities over space and time; these quantities are sampled by the sensors, and the source identity associated with each measurement is necessary for the spatial and temporal reconstruction. In many practical scenarios, source identities constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit. In these scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. In this paper, we re-examine this traditional data separation and propose a scheme for joint identity-message encoding; we use this scheme to design a new efficient collection protocol for identity-aware sensor networks. Compared to conventional data collection, our protocol reduces the amount of traffic in the network at least by a factor of two (up to an order of magnitude, in lossy environments), while its performance scales better with network complexity; we show these results both through theoretical analysis and extensive simulations.

2008