A Tree Search Approach to Detection and Estimation with Application to Communications and Tracking
Date
2011-08-18
Authors
Roufarshbaf, Hossein
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We propose complexity efficient tree search approaches to detection and estimation problems, and we consider both communication and target tracking applications in this regard. We formulate the problems of interest using a dynamic state space model, where we seek to estimate the system state from sensor observations. The proposed tree search approach initializes a search tree from a given initially estimated system state. With each new observation, the algorithm expands the search tree to find the best possible system state. The paths through the search tree correspond to sequences of system states. They are evaluated by their associated path metrics, which are proportional to the posterior probability of the system state. The stack algorithm and the M-algorithm, two tree search approaches that were originally used for decoding convolutionally-encoded sequences, are applied to reduce the complexity of the tree search. In wireless communication applications, we have considered blind channel equalization of time-varying channels and modulation classi cation of an unknown received signal. For both applications, tree search approaches are implemented to find the transmitted information sequence that maximizes the posterior probability distribution function of the system state. For blind channel equalization of time-varying channels, an exponentially decaying window, matched to the variation rate of the channel, is implemented in the path metric calculation to successfully equalize an unknown time-varying channel. For modulation classification of challenging high-density QAM (Quadrature Amplitude Modulation) schemes, the statistical properties of the mean square error are derived analytically and compared with those of the estimated sequence to identify the modulation scheme of the received signal. The proposed tree-search approaches provide superior performance in comparison with other competitive approaches. In target tracking applications, the proposed stack-based tree search approach sequentially tracks multiple targets in high clutter density with low observable targets and can be applied to both linear and nonlinear target models. The proposed technique is able to retain previously strong track candidates and may refer to them to refine the estimated track if the current track estimate is not satisfactory. A likelihood ratio track management technique has been embedded in the search tree to identify false tracks, and the sensitivity of the proposed tracker to different system parameters has been evaluated analytically. The results of empirical performance evaluation conducted for the detection and estimation problems described above reveal that the proposed tree search technique performs well in challenging detection and estimation environments with severely non-linear dynamic state space models.
Description
Keywords
Target Tracking, Tree Search, Modulation Classification, Stack Algorithm