Design of scalable and low complexity decoders for wireless sensor networks
Ruchira Yasaratna · Mspace (University of Manitoba) · 2008
Recent technological advances in sensors, embedded processors, and wireless devices, ofben all integrated on a single chip, are leading to the use of wireless sensor networks (WSN) for interacting with the physical world in wide range of applications such as security and surveillance, monitoring of natural habitats and eco-systems, medical monitoring etc.This thesis investigates the practical design of a joint decoder for a large scale wireless sensor network having a limited transmission bandwidth.Joint decoders are an effective means of decoding correlated signals gathered by a sensor network.However, the optimal joint decoder designed for a large sensor net- work suffers from it's high computational complexity.We consider m'in'imurn n'Lel,n squl,re error (MMSÐ) decoding in a dense sensor network where distributed quanti- zation is used to improve the performance.As a solution to the problem of exponen- tial complexity of the optimal decoder, v/e present a framework based on Bageszan networlts for designing a scalable, but near-optimal decoder.In our approach, a complexity-constrained factor graph is obtained by an algorithm which constructs an equivalent Bayesian network based on a training set of sensor observations, us- ing the matimum likeli,hood (ML) criterion.Our simulation results show that, the scalable decoders constructed using the proposed approach perform close to optimal with both Gaussian and non-Gaussian sensor data.Moreover, the complexity of the decoder grows only linearly with the size of the network.lu 2.8 Factor graph corresponds to the expansion (2.22).The design param- eters are chosen as G: 2 and H :7. 2.9 Performance of several decoders for a Gaussian source) as a function of CSNR.The network consists of 9 sensor nodes and each node uses quantizers of rate 1-bit/sample.31 3.1 Bayesian network representation of (u) Eq. (3.3) and (b) nq.(S.+).36 3.2 Bayesian network representation of (u) Eq. (3.5) and (b) Eq. (3.6).37 3.3 (a) Bayesian network representation of global pdf, p(X1, Xz, Xs, X¿) : p(Xz)p(XtlXz)p(XnlX¡ X2)p(X3lXn) (¡) The Bayesian network shown as a factor graph. 38 3.4 (a) BN Â corresponds to factorization P(12)P(I|I2)P(h111).(b) BN À' corresponds to lactorization P(I)P(I2lIr)P(hlIù .4I vlI LIST OF FIGURES 3.5 Factor graph belongs to non-optimal BN with maximum number of parents, S :2.Corresponding factorizatíon is as (3.14) and the like- lihood of the structure is -1.5052 x 105.3.6 Factor graph corresponds to optimal BN found using Algorithm 1. Maximum number of parents, S : 2. The resulting factorization is (3.13) and the likelihood of the structure is -1.3682 x 105.3.7 Factor tree corresponds to the optimal BN found using the mutual information as the measurement of closeness.Maximum number of parents, ,9 : 1.The resulting factorization is (3.17) and the overall closeness of the structure is 2.9349 bits.3.8 Performance of the decoders as a function of CSNR.The network has 9 sensors and each of them uses 1 bit/sample Lloyd-Max quantization.3.9 Performance of the decoders as a function of CSNR.The network has 9 sensors and each of them uses 2 bits/sample Lloyd-Max quantization.3.10 PIot of RSNR against number of clock cycles during the execution of the sum-product algorithm, for CSNR:5 dB.4.I Clustering of 15 sensors) Z,no, : 4 and Z^¿n : 2. Clusters, 1", : {Iz,In,Is, In}, 1." : {1¡, /to}, 1".: {It, Ir, /a}, f* : {Itr, lts}, 1", : {Irn}, f"u : Ut}, f", : {/rs}, f".: {/6}.4.2 Final result after step 1 and step 2. Z,no* ters, 11 : Uz, I+, Ig, I¡¡-j, lz : {/s, /ro}, {Iu,Irr,I¡3} and f5 : {/1, -I1a].4.3 (a) Factor graph corresponds to the clusters (b) Separate decoding based on the clusters.4.4 (a) Factor graph corresponds to distribution p(l) : P(Ir,Ia,Ir)- P(Iu,I6,Is)P(IL,Is,Ia) (b) Factor graph after linking clusters, P(I) : p (I 2, I a, I 7) p (I 5, IslI 4, I 7) P(Iu I /u, I s) P (I L, Isl I z, I 4) P (I 8l I L, h) .4.5 System model with binning 4.6 Simulation results -Source is distributed as multivariate Gaussian.Scalar quantization with a subsequent binning function at the encoder reduces channel rate to 1-bit/sample.4.7 Performance of several decoders as a function of CSNR.The network has l/ : 9 sensing nodes and each node uses rate 1-bit/sample quan- tization, without subsequent binning.4.8 Performance of various decoders when binning-based distributed quan- tizers are used in sensors, Each sensor uses a quantizer rate of Q bits/sample and a transmission rate of 1 bit/sample.The curves( a) and (b) are the same as those in Fig. 4.7.For the system with Q : 2, the performance of the optimal decoder is shown in curve (e).