Files in this item
Files  Description  Format 

application/pdf Kowshik_Hemant.pdf (814kB)  (no description provided) 
Description
Title:  Information aggregation in sensor networks 
Author(s):  Kowshik, Hemant J. 
Director of Research:  Kumar, P.R. 
Doctoral Committee Chair(s):  Kumar, P.R. 
Doctoral Committee Member(s):  Srikant, Rayadurgam; Basar, Tamer; Coleman, Todd P. 
Department / Program:  Electrical & Computer Eng 
Discipline:  Electrical & Computer Engr 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Innetwork Computation
Sensor Networks Function Computation Communication Complexity Threshold Functions Zeroerror Block Computation Sequential Decisionmaking Checking Connectivity Distributed Computing 
Abstract:  In many sensor network applications, one is interested only in computing some relevant \textit{function} of the sensor measurements. In this thesis, we study optimal strategies for innetwork computation and communication in such wireless sensor networks. We begin by considering a directed graph $G = (\mathcal{V},\mathcal{E})$ on the sensor nodes, with a designated collector node, where the goal is to characterize the rate region in $\mathbf{R}^{\mathcal{E}}$, i.e., the set of vector rates for which there exist feasible encoders and decoders which achieve zeroerror computation for large enough block length. For directed tree graphs, we determine a necessary and sufficient condition for each edge that yields the optimal alphabet, from which we then calculate the minimum worst case and average case complexity. For general directed acyclic graphs, we provide an outer bound on the rate region by finding the disambiguation requirements for each cut, and describe examples where this outer bound is tight. Next, we consider undirected tree networks, where each node has an integer measurement, and all nodes want to compute a symmetric Boolean function. For a class of functions called sumthreshold functions, we derive an optimal strategy which minimizes the worstcase number of bits exchanged on each edge. In the case of general graphs, we present a cutset lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme. We then turn to a collocated network of nodes, where each node has a Boolean measurement and we wish to compute a symmetric Boolean function of these measurements with zero error. Our objective is to determine the minimum worstcase total number of bits to be communicated to perform the desired computation. We define three classes of functions, namely threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and an orderoptimal strategy with optimal preconstant for interval functions. Using these results, we can characterize the complexity of computing percentile type functions. The results also extend to the case of integer measurements and certain integervalued functions. We use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools. In the collocated network scenario, minimizing the average case complexity presents a variety of interesting problems. We show that the average case complexity of computing a Boolean threshold function of i.i.d. measurements, with threshold $\theta$, is $O(\theta)$, in comparison to the worst case complexity of $\Omega(\log n)$, where $n$ is the number of nodes. In the case of independent but not identically distributed measurements, we show that the optimal order of transmissions is determined by a surprisingly simple rule that depends in a trivial way on the values of the previously transmitted bits and the ordering, but not the exact values of the marginal probabilities. The approach presented can be generalized to the case of block computation, and to alternate models of communication. We also determine the optimal strategy when the number of bits to be communicated is fixed, and one wants to minimize the conditional entropy of the parity function. Finally, we consider the problem of determining the connectivity of a random graph by sequentially sampling edges. We present optimal strategies for determining connectivity in series graphs, parallel graphs, seriesparallel graphs and parallelseries graphs. In the case of general graphs, we consider the related problem of finding a certificate for connectivity, and conjecture the optimal strategy. 
Issue Date:  20110525 
URI:  http://hdl.handle.net/2142/24189 
Rights Information:  Copyright 2011 Hemant Jagadish Kowshik 
Date Available in IDEALS:  20110525 
Date Deposited:  201105 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering