Estimation of hidden Markov processes and neighbor discovery in wireless networks.

摘要

Inference methods, such as estimation and hypothesis testing, have been developed along with and utilized by information theory and communication theory. This thesis studies two separate inference problems.The first problem focuses on a simple, yet important hidden Markov process which is generated by observing a discrete-time binary homogeneous Markov chain through an arbitrary memoryless (noisy) channel. It is found that the computation of entropy rate boils down to obtaining the stationary distribution of a filtering process, namely the log-likelihood ratio of estimating an element of the Markov process conditioned on all past observations. A fixed-point functional equation is then derived for the stationary distribution of the log-likelihood ratio and solved numerically by discretizing it with uniform quantization. The accuracy of the numerically computed entropy rate is shown to be of the same order as the quantization interval.The second part of the thesis concerns the problem of neighbor discovery in wireless networks. The problem is basically for each node in a wireless network to identify the network interface addresses of all nodes within its radio range. This thesis proposes a novel scheme, referred to as compressed neighbor discovery, where the detection algorithms are based on techniques developed in the literature of group testing and compressed sensing. The key feature of compressed neighbor discovery is to assign pseudo-random on-off signatures to nodes, and let nodes simultaneously transmit their signatures during the neighbor discovery phase. It is shown that if the expected number of neighbors is a small constant, then reliable discovery can be achieved by using signatures of length in the order of the square of the logarithm of the node population. The proposed compressed neighbor discovery schemes allow all nodes to discover their respective neighbors simultaneously with high accuracy using only non-coherent (energy) detection. In addition, comparisons with a class of widely implemented neighbor discovery schemes similar to what has been used in the ad hoc mode of IEEE 802.11 standard demonstrate that compressed neighbor discovery is much more efficient. Issues related to implementation of compressed neighbor discovery schemes are also addressed in this thesis.