Search

This paper discusses the problem of reconstructing the state of a linear time invariant system when some of its actuators and sensors are compromised by an adversarial agent. In the model considered in this paper, the adversarial agent attacks an input (output) by manipulating its value arbitrarily, i.e., we impose no constraints (statistical or otherwise) on how control commands (sensor measurements) are changed by the adversary other than a bound on the number of attacked actuators and sensors In the first part of this paper, we introduce the notion of sparse strong observability and we show that is a necessary and sufficient condition for correctly reconstructing the state despite the considered attacks. In the second half of this work, we propose an observer to harness the complexity of this intrinsically combinatorial problem, by leveraging satisfiability modulo theory solving. Numerical simulations illustrate the effectiveness and scalability of our observer.

We consider the problem of estimating the state of a noisy linear dynamical system when an unknown subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm, and derive (optimal) bounds on the achievable state estimation error given an upper bound on the number of attacked sensors. The proposed state estimator involves Kalman filters operating over subsets of sensors to search for a sensor subset which is reliable for state estimation. To further improve the subset search time, we propose Satisfiability Modulo Theory-based techniques to exploit the combinatorial nature of searching over sensor subsets. Finally, as a result of independent interest, we give a coding theoretic view of attack detection and state estimation against sensor attacks in a noiseless dynamical system.

Networks need to accommodate diverse applications with different Quality-of-Service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms converging to the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division. Index Terms--Networks, resource management, optimization methods, communication systems, channel coding.

We consider the problem of side-information scalable (SI-scalable) source coding, where the encoder constructs a two-layer description, such that the receiver with high quality side information will be able to use only the first layer to reconstruct the source in a lossy manner, while the receiver with low quality side information will have to receive both layers in order to decode. We provide inner and outer bounds to the rate-distortion (R-D) region for general discrete memoryless sources. The achievable region is tight when either one of the decoders requires a lossless reconstruction, and when the distortion measures are degraded and deterministic. Furthermore, the gap between the inner and the outer bounds can be bounded by certain constants when the squared error distortion measure is used. The notion of perfect scalability is introduced, for which necessary and sufficient conditions are given for sources satisfying a mild support condition. Using SI-scalable coding and successive refinement Wyner-Ziv coding as basic building blocks, we provide a complete characterization of the rate-distortion region for the important quadratic Gaussian source with multiple jointly Gaussian side informations, where the side information quality is not necessarily monotonic along the scalable coding order. A partial result is provided for the doubly symmetric binary source under the Hamming distortion measure when the worse side information is a constant, for which one of the outer bounds is strictly tighter than the other. Index Terms--Scalable source coding, side information, successive refinement.

Designs for transmit alphabet constrained space--time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multilevel space--time codes for flat-fading channels have been designed from sets of binary matrices with rank distance guarantees over the binary field by mapping them onto quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. In this paper, we demonstrate that diversity embedded space--time codes for fading intersymbol interference (ISI) channels can be designed with provable rank distance guarantees. As a corollary, we obtain an asymptotic characterization of the fixed transmit alphabet rate--diversity tradeoff for multiple antenna fading ISI channels. The key idea is to construct and analyze properties of binary matrices with a particular structure (Toeplitz structure) induced by ISI channels. Index Terms--Diversity embedding, fading channels, inter-symbol interference (ISI), rank--distance codes, space-time codes, unequal error protection.

We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean-squared error distortion measure. The channel state information is known only at the receiver but not at the transmitter. The source is assumed to be encoded in a successive refinement (SR) manner, and then transmitted over the channel using the broadcast strategy. In order to minimize the expected distortion at the receiver, optimal power allocation is essential. We propose an efficient algorithm to compute the optimal solution in linear time O (M), when the total number of possible discrete fading states is M. Moreover, we provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method. The proposed algorithm as well as the continuous solution is based on an alternative representation of the capacity region of the Gaussian broadcast channel. Index Terms--Broadcast strategy, joint source-channel coding, power allocation, successive refinement (SR).

In this correspondence, we consider the multiuser successive refinement (MSR) problem, where the users are connected to a central server via links with different noiseless capacities, and each user wishes to reconstruct in a successive-refinement fashion. An achievable region is given for the two-user two-layer case and it provides the complete rate-distortion region for the Gaussian source under the MSE distortion measure. The key observation is that this problem includes the multiple description (MD) problem (with two descriptions) as a subsystem, and the techniques useful in the MD problem can be extended to this case. It is shown that the coding scheme based on the universality of random binning is suboptimal, because multiple Gaussian side informations only at the decoders do incur performance loss, in contrast to the case of single side information at the decoder. It is further shown that unlike the single user case, when there are multiple users, the loss of performance by a multistage coding approach can be unbounded for the Gaussian source. The result suggests that in such a setting, the benefit of using successive refinement is not likely to justify the accompanying performance loss. The MSR problem is also related to the source coding problem where each decoder has its individual side information, while the encoder has the complete set of the side informations. The MSR problem further includes several variations of the MD problem, for which the specialization of the general result is investigated and the implication is discussed. Index Terms--Multiple description coding, rate distortion, source coding, successive refinement.

Rate and diversity impose a fundamental tradeoff in wireless communication. High-rate space-time codes come at a cost of lower reliability (diversity), and high reliability (diversity) implies a lower rate. However, wireless networks need to support applications with very different quality-of-service (QoS) requirements, and it is natural to ask what characteristics should be built into the physical layer link in order to accommodate them. In this paper, we design high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations while the embedded high-diversity code provides guarantees that at least part of the information is received reliably. We provide constructions of linear and nonlinear codes for a fixed transmit alphabet constraint. The nonlinear constructions are a natural generalization to wireless channels of multilevel codes developed for the additive white Gaussian noise (AWGN) channel that are matched to binary partitions of quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. The importance of set-partitioning to code design for the wireless channel is that it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain. We investigate the systems implications of embedded diversity codes by examining value to unequal error protection, rate opportunism, and packet delay optimization. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate signal-to-noise (SNR) regimes. Index Terms--Fading channels, multilevel codes, opportunistic communication, space-time codes, unequal error protection.

In this correspondence, we provide a complete characterization of the rate-distortion region for the multistage successive refinement of the Wyner-Ziv source coding problem with degraded side informations at the decoder. Necessary and sufficient conditions for a source to be successively refinable along a distortion vector are subsequently derived. A source--channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case. Furthermore, the notion of generalized successive refinability with multiple degraded side informations is introduced. This notion captures whether progressive encoding to satisfy multiple distortion constraints for different side informations is as good as encoding without progressive requirement. Necessary and sufficient conditions for generalized successive refinability are given. It is shown that the following two sources are generalized successively refinable: 1) the Gaussian source with degraded Gaussian side informations and 2) the doubly symmetric binary source when the worse side information is a constant. Thus for both cases, the failure of being successively refinable is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement. Index Terms--Degradedness, rate distortion, side information, source coding, successive refinement.

Two subspaces of a vector space are here called "nonintersecting" if they meet only in the zero vector. Motivated by the design of noncoherent multiple-antenna communications systems, we consider the following question. How many pairwise nonintersecting [M.sub.t]-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A [subset] F? The most important case is when F is the field of complex numbers C; then Mt is the number of antennas. If A = F = GF (q) it is shown that the number of nonintersecting subspaces is at most ([q.sup.m] - 1) / ([q.sup.[M.sub.t] - 1), and that this bound can be attained if and only if m is divisible by Mr. Furthermore, these subspaces remain nonintersecting when "lifted" to the complex field. It follows that the finite field case is essentially completely solved. In the case when F = C only the case [M.sub.t] = 2 is considered. It is shown that if A is a PSK-configuration, consisting of the [2.sup.r] complex roots of unity, the number of nonintersecting planes is at least [2.sup.r] (m - 2) and at most [2.sup.r] (m - 1) - 1 (the lower bound may in fact be the best that can he achieved). Index Terms--Multiple-antenna communications, noncoherent systems, nonintersecting subspaces, space-time codes.

We study the capacity of ad hoc wireless networks with mobile nodes. The mobility model examined is one where the nodes are restricted to move along one-dimensional paths. We examine the scaling laws for the peruser throughput achievable over long time-scales, making this suitable for applications with loose delay constraints. We show that under this regime of restricted mobility, we attain a constant throughput (i.e., [THETA] (1)) per user, which is significantly higher than the throughput of fixed networks, which decays as O(1/[square root of n]) with the number of nodes n, as shown by Gupta and Kumar. Index Terms--Ad hoc wireless networks, capacity scaling laws, mobility, multiuser diversity.

In this paper, we study the multiple-access channel where users employ space-time block codes (STBC). The problem is formulated in the context of an intersymbol interference (ISI) multiple-access channel which occurs for transmission over frequency-selective channels. The algebraic structure of the STBC is utilized to design joint interference suppression, equalization, and decoding schemes. Each of the K users transmits using [M.sub.t] = 2 transmit antennas and a time-reversed STBC suitable for frequency-selective channels. We first show that a diversity order of 2[M.sub.r](v + 1) is achievable at full transmission rate for each user. when we have [M.sub.r], receive antennas, channel memory of v, and an optimal multiuser maximum-likelihood (ML) decoder is used. Due to the decoding complexity of the ML detector we study the algebraic structure of linear multiuser detectors which utilize the properties of the STBC. We do this both in the transform (D-domain) formulation and when we impose finite block-length constraints (matrix formulation). The receiver is designed to utilize the algebraic structure of the codes in order to preserve the block quaternionic structure of the equivalent channel for each user. We also explore some algebraic properties of D-domain quaternionic matrices and of quaternionic circulant block matrices that arise in this study. Index Terms--Fading channels, intersymbol interference (ISI), multiple-access channels, multiuser detection, space-time coding.

Multicarrier transmission over time-varying channels is investigated. A model for such a transmission arrangement is developed, with the focus on multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM).

We show that the optimum length-[upsilon] guard sequence for block transmission over a linear Gaussian-noise dispersive channel with memory [upsilon] is a linear Combination of the N information symbols of the block. A closed-form expression for the optimum guard sequence is derived subject to a total average energy .constraint on the information and guard symbols. The achievable channel block throughput with the optimum guard sequence is compared with that achievable with two common guard sequence types, namely zero stuffing and cyclic prefix. Index Terms--Intersymbol interference, throughput, transmitters.

This paper addresses the problem of soft equalization for space--time-coded transmissions over frequency-selective fading channels. The structure of the space--time code is embedded in the channel impulse response for efficient joint equalization and decoding. The proposed equalization/decoding approach uses a prefilter to concentrate the effective channel power in a small number of taps followed by a reduced-complexity maximum a posteriori probability (MAP) equalizer/decoder to produce soft decisions. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements such as using different prefilters for the forward and backward recursions, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the EDGE typical urban channel. Index Terms--BCJR algorithm, equalization, FIR prefilters, space--time coding.

Stochastic analysis of Rosenblatt's single layer perceptron algorithm for fast learning shows convergence features. Convergence points of the algorithm depend on variance of input signal, and the step size mu, with the algorithm being stable for all mu > 0. The convergence is also studied to find out the effects of noisy perceptron input vectors.

In this paper, we describe a high-resolution direction-of-arrival (DOA) estimation algorithm for the enhancement of a lens-based array system. In such a system, the antenna array is followed by an electromagnetic lens and a bank of power detectors (crystal video receivers). This system can handle sources over a large bandwidth and is capable of detecting pulsed sources that exist for short periods of time. The proposed algorithm operates directly on the power estimates provided by a bank of crystal video receivers (CVRs), yielding accurate DOA estimates for multiple narrowband sources. This approach is most effective when the sources are uncorrelated, and it potentially is capable of operating in environments where the signals are highly correlated. We present computer simulations to demonstrate the improved performance achieved by the algorithm for different source scenarios.