We are concerned with the problem of maximizing the worst-case lifetime of a data-gathering wireless sensor network consisting of a set of sensor nodes directly communicating with a base-station.We propose to solve this problem by modeling sensor node and base-station communication as the interactive communication between multiple correlated informants (sensor nodes) and a recipient (base-station). We provide practical and scalable interactive communication protocols for data gathering in sensor networks and demonstrate their efficiency compared to traditional approaches. In this paper, we first develop a formalism to address the problem of worst-case interactive communication between a set of multiple correlated informants and a recipient. We realize that there can be different objectives to achieve in such a communication scenario and compute the optimal number of messages and bits exchanged to realize these objectives. Then, we propose to adapt these results in the context of single-hop data-gathering sensor networks. Finally, based on this proposed formalism, we propose a clustering based communication protocol for large sensor networks and demonstrate its superiority over a traditional clustering protocol.
The multiple correlated informants - single recipient'' communication problem we are considering in this paper, is basically well-known distributed source coding (DSC) problem. This problem was first considered by Slepian and Wolf @cite_11 for lossless compression of discrete random variables and by Wyner and Ziv @cite_24 for lossy distributed compression. However, these work only provided theoretical bounds on the compression, but no method of constructing practical codes which achieve predicted theoretical bounds.
@cite_24 @cite_11
2138256990 2156567124 2080257599 2051707898
We address the problem of compressing correlated distributed sources, i.e., correlated sources which are not co-located or which cannot cooperate to directly exploit their correlation. We consider the related problem of compressing a source which is correlated with another source that is available only at the decoder. This problem has been studied in the information theory literature under the name of the Slepian-Wolf (1973) source coding problem for the lossless coding case, and as "rate-distortion with side information" for the lossy coding case. We provide a constructive practical framework based on algebraic trellis codes dubbed as DIstributed Source Coding Using Syndromes (DISCUS), that can be applicable in a variety of settings. Simulation results are presented for source coding of independent and identically distributed (i.i.d.) Gaussian sources with side information available at the decoder in the form of a noisy version of the source to be coded. Our results reveal the promise of this approach: using trellis-based quantization and coset construction, the performance of the proposed approach is 2-5 dB from the Wyner-Ziv (1976) bound. This paper deals with the problem of multicasting a set of discrete memoryless correlated sources (DMCS) over a cooperative relay network. Necessary conditions with cut-set interpretation are presented. A Joint source-Wyner-Ziv encoding sliding window decoding scheme is proposed, in which decoding at each receiver is done with respect to an ordered partition of other nodes. For each ordered partition a set of feasibility constraints is derived. Then, utilizing the submodular property of the entropy function and a novel geometrical approach, the results of different ordered partitions are consolidated, which lead to sufficient conditions for our problem. The proposed scheme achieves operational separation between source coding and channel coding. It is shown that sufficient conditions are indeed necessary conditions in two special cooperative networks, namely, Aref network and finite-field deterministic network. Also, in Gaussian cooperative networks, it is shown that reliable transmission of all DMCS whose Slepian-Wolf region intersects the cut-set bound region within a constant number of bits, is feasible. In particular, all results of the paper are specialized to obtain an achievable rate region for cooperative relay networks which includes relay networks and two-way relay networks. This paper proposes a practical coding scheme for the Slepian-Wolf problem of separate encoding of correlated sources. Finite-state machine (FSM) encoders, concatenated in parallel, are used at the transmit side and an iterative turbo decoder is applied at the receiver. Simulation results of system performance are presented for binary sources with different amounts of correlation. Obtained results show that the proposed technique outperforms by far both an equivalent uncoded system and a system coded with traditional (non-concatenated) FSM coding. This monograph presents a unified treatment of single- and multi-user problems in Shannon's information theory where we depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities.In Part I, after reviewing the fundamentals of information theory, we discuss Strassen's seminal result for binary hypothesis testing where the type-I error probability is non-vanishing and the rate of decay of the type-II error probability with growing number of independent observations is characterized. In Part II, we use this basic hypothesis testing result to develop second- and sometimes, even third-order asymptotic expansions for point-to-point communication. Finally in Part III, we consider network information theory problems for which the second order asymptotics are known. These problems include some classes of channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels. Finally, we discuss avenues for further research.