Research Project Summary

Rate and power allocation under the pairwise distributed source coding constraint

This project is regarding to distributed compression over a (sensor) network. Consider N sensors observe N correlated sources and a terminal wants to recover these sources. The famous Slepian-Wolf theorem in information theory tells us the correlated sources can be compressed without any communication among the source nodes but still achieve the same efficiency as if source nodes communicate. In the current state of art research, Slepian-Wolf codes are well known for two sources, but for multiple sources, the ideal practical coding scheme is not well known. Thus, we could apply two-source Slepian-Wolf coding schemes and properly determine the encoding rate for each source and which two sources are jointly decoded together. We call the constraint that each time only two sources are jointly decoded as pairwise distributed source coding constraint.

We consider the problem of rate and power allocation for a sensor network under the pairwise distributed source coding constraint. We find ways to allocate rate and power for each sensor node such that some overall metrics for the network are optimized. Specifically, for noiseless source-terminal channels, we show that the minimum sum rate assignment can be found by finding a minimum weight arborescence in an appropriately defined directed graph. For orthogonal noisy source-terminal channels, the minimum sum power allocation can be found by finding a minimum weight matching forest in a mixed graph. Numerical results are presented for both cases showing that our solutions always outperform previously proposed solutions. The gains are considerable when source correlations are high.

Key words:

distributed source coding, Slepian-Wolf theorem, matching forest, directed spanning tree, resource allocation

Fig.1 Slepian-Wolf region for two sources. The red points are corner points and at those points, asymmetric SW codes are used. One source (say, X_1)is encoded at a rate of entropy by lossless compression and is used as side information to help decode X_2. As long as R_2 = H(X_2|X_1), X_2 can be recovered. For the noiseless channel case, asymmetric SW codes are used, while for the noisy channel case, some source pairs are working at the slope where R_1+R_2 = H(X_1,H_2).

Fig.2 An simple illustration of our rate allocation scheme for noiseless case. Note that X_1 is encoded and decoded by entropy coding. X_2, X_3, X_4 are encoded and decoded by asymmetric Slepian-Wolf codes (in fact, we can apply channel codes including Turbo and LDPC as SW codes after properly modification). X_1 is used as side information to help decode X_3. After X_3 is decoded by jointly decoder, it can be used as side information to help decode X_2, which will be used as side information to help decoding X_4. All four terminals can be recovered.

Publications:
Journal
Shizheng Li and Aditya Ramamoorthy, "Rate and power allocation under the pairwise distributed source coding constraint", accepted by IEEE Transaction on Communications.preprint available at ArXiv.
Conference
Shizheng Li and Aditya Ramamoorthy, “Rate and power allocation under the pairwise distributed source coding constraint”, in IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, Jul. 2008, pp.2312 – 2316.(.pdf)

Presentations:

ISIT08 presentation, 07/11/2008;
Communication and Signal Processing Group Seminar (contains more details),09/17/2008 ;
Qualifying examination, 11/21/2008;