This paper studies the online scheduling of electric vehicle charging by a service provider subject to a demand charge in a distribution system. Demand charge imposes a penalty on the peak power consumption over each billing period, representing a substantial cost for the service provider with a large number of clients. Because the demand charge is calculated at the end of the billing period, it poses challenges in real-time scheduling when energy demand forecasts are inaccurate, resulting in either overly conservative power consumption or substantial demand charge. We propose a block model predictive control approach that decomposes the demand charge into a sequence of stage costs. Optimality conditions on demand patterns are also presented and analyzed. Numerical simulations demonstrate the efficacy of the proposed approach.Note to Practitioners—This paper addresses a significant practical problem of minimizing the demand charge on the real-time scheduling of deferrable demands. In particular, we consider a setting where a commercial electric vehicle (EV) charging service provider has to manage the online scheduling of a large number of arriving EVs at a charging facility subject to a maximum charging power constraint and a tariff with the demand charge. A major practical challenge is to balance the tradeoff between maximizing profit in scheduling as much EV charging as possible and the need to minimize penalty on the peak charging power. We propose a model predictive control strategy that decomposes the overall demand charge into a sequence of terminal costs. Also addressed is the practical constraint arising from the mismatched EV charging decision period and the power measurement period used to compute the demand charge. Using real data collected at the Adaptive Charging Network (ACN) testbed in simulations, the proposed approach yields 8-12% improvement in operational profit over existing benchmarks, while it has yet been tested in actual charging systems. In the future research, we will address the charging scheduling under demand charge over multiple charging stations.

An innovations sequence of a time series is a sequence of independent and identically distributed random variables with which the original time series has a causal representation. The innovation at a time is statistically independent of the history of the time series. As such, it represents the new information contained at present but not in the past. Because of its simple probability structure, the innovations sequence is the most efficient signature of the original. Unlike the principle or independent component representations, an innovations sequence preserves not only the complete statistical properties but also the temporal order of the original time series. An long-standing open problem is to find a computationally tractable way to extract an innovations sequence of non-Gaussian processes. This paper presents a deep learning approach, referred to as Innovations Autoencoder (IAE), that extracts innovations sequences using a causal convolutional neural network. An application of IAE to the one-class anomalous sequence detection problem with unknown anomaly and anomaly-free models is also presented.

The problem of detecting data anomaly under unknown probability distributions is considered. Whereas the probability distribution of the anomaly-free data is unknown, anomaly-free training samples are assumed to be available. For anomaly data, neither the underlying probability distribution is known nor anomaly data samples are available. A deep learning approach coupled with a statistical test based on coincidence is proposed where an inverse generative adversary network is trained to transform data to the classical uniform vs. nonuniform hypothesis testing problem. The proposed approach is particularly effective to detect persistent anomalies whose distributions have an overlapping domain with that of the anomaly-free distribution.

We study the online learning problem of a bidder who participates in repeated auctions. With the goal of maximizing his T-period payoff, the bidder determines the optimal allocation of his budget among his bids for $K$ goods at each period. As a bidding strategy, we propose a polynomial-time algorithm, inspired by the dynamic programming approach to the knapsack problem. The proposed algorithm, referred to as dynamic programming on discrete set (DPDS), achieves a regret order of $O(\sqrt{T\log{T}})$. By showing that the regret is lower bounded by $\Omega(\sqrt{T})$ for any strategy, we conclude that DPDS is order optimal up to a $\sqrt{\log{T}}$ term. We evaluate the performance of DPDS empirically in the context of virtual trading in wholesale electricity markets by using historical data from the New York market. Empirical results show that DPDS consistently outperforms benchmark heuristic methods that are derived from machine learning and online learning approaches.

The problem of online learning and optimization of unknown Markov jump linear models is considered. A new online learning algorithm, referred to as Markovian simultaneous perturbations stochastic approximation (MSPSA), is proposed. It is shown that ν/ MSPSA achieves the minimax regret order of Θ(√T). Using the Van Trees inequality (stochastic Cramér-Rao bound), it is shown ν/ that Θ(√T) is the lowest regret order achievable. Simulation results show scenarios that MSPSA offers significant gain over the greedy certainty equivalent approaches.

The problem of integrating renewables and storage into a distribution network is considered under two integration models: 1) a centralized model involving a retail utility that owns the integration as part of its portfolio of energy resources, and 2) a decentralized model in which each consumer individually owns and operates the integration and is capable of selling surplus electricity back to the retailer in a net-metering setting. The two integration models are analyzed using a Stackelberg game in which the utility is the leader in setting the retail price of electricity, and each consumer schedules its demand by maximizing individual consumer surplus. The solution of the Stackelberg game defines the Pareto front that characterizes fundamental tradeoffs between retail profit of the utility and consumer surplus. It is shown that, for both integration models, the centralized integration uniformly improves retail profit. As the level of integration increases, the proportion of benefits goes to the consumers increases. In contrast, the consumer-based decentralized integration improves consumer surplus at the expense of retail profit of the utility. For a profit regulated utility, the consumer-based integration may lead to smaller consumer surplus than that when no renewable or storage is integrated at either the consumer or the retailer end.

The quickest detection of short-term voltage instability in a smart grid is considered. The problem is formulated as a binary sequential composite hypothesis testing where the null hypothesis is a non-stationary process with an unknown exponentially decaying mean and the alternative is a nonstationary process with an unknown exponentially increasing mean. A sequential generalized likelihood ratio test (SGLRT) is proposed and analyzed. It is shown that the proposed SGLRT is asymptotically optimal.

Smart Grid is a complex cyber-physical system that modernizes the traditional electric power infrastructure by sensing, control, computation and communication. Validating the functionality, security and reliability of Smart Grid applications within such a system requires the modeling and emulation of both power networks and communication networks, as well as the interactions between them. In this paper, we present the design, implementation and evaluation of an integrated scalable cyber-physical experiment environment for Smart Grid, called ScorePlus. Compared with previous related works, ScorePlus fills the gap by: 1) Creating and integrating both software emulator and hardware testbed, such that they all follow the same architecture and interface, and the same Smart Grid application program can be tested on either of them without any modification; 2) Providing remote access to the hardware testbed such that users can configure physical devices of the hardware testbed through Internet; 3) Supporting scalable distributed experiments such that multiple software emulators and hardware testbeds running at different locations are able to connect and form a larger Smart Grid system.

In many practical parameter estimation problems, a model selection is made prior to estimation. In this paper, we consider the problem of estimating an unknown parameter of a selected population, where the population is chosen from a population set by using a predetermined selection rule. Since the selection step may have an important impact on subsequent estimation, ignoring it could lead to biased-estimation and an invalid Cramér-Rao bound (CRB). In this work, the mean-square-selected-error (MSSE) criterion is used as a performance measure. The concept of Ψ-unbiasedness is introduced for a given selection rule, Ψ, by using the Lehmann-unbiasedness definition. We derive a non-Bayesian Cramér-Rao-type bound on the MSSE of any Ψ-unbiased estimator. The proposed Ψ-CRB is a function of the conditional Fisher information and is a valid bound on the MSSE. Finally, we examine the Ψ-CRB for different selection rules for mean estimation in a linear Gaussian model.

The problem of joint off-nominal frequency and phasor estimation in an unbalanced three-phase power system using a phasor measurement unit (PMU) is considered. Voltage unbalance arises when magnitudes are different from each other or when phases are unequally spaced. A general model for the zero, positive, and negative sequences from a PMU measurement at off-nominal frequencies is presented. Then, the maximum likelihood (ML) estimator is developed under an unbalanced condition for joint symmetrical components phasors and frequency estimation. Finally, a low complexity technique is developed for the estimation of frequency deviation based a new autoregressive (AR) representation of the innovation process for the symmetrical component.

The sixteen articles in this special section explore advances in communication technologies that have the potential for improving energy efficiency and realizing the smart grid vision. The articles tackle important challenges with respect to smart grid communications and include a wide range of topics such as electric load models, electric vehicle charging, models for demand response, power management optimization and storage, pricing, and security.

A new mechanism aimed at misleading a power system control center about the source of a data attack is proposed. As a man-in-the-middle state attack, a data framing attack is proposed to exploit the bad data detection and identification mechanisms currently in use at most control centers. In particular, the proposed attack frames meters that are providing correct data as sources of bad data such that the control center will remove useful measurements that would otherwise be used by the state estimator. The optimal design of a data framing attack is formulated as a quadratically constrained quadratic program. It is shown that the proposed attack is capable of perturbing the power system state estimate by an arbitrary degree controlling only half of a critical set of measurements that are needed to make a system unobservable. Implications of this attack on power system operations are discussed, and the attack performance is evaluated using benchmark systems.

This paper investigates a network coding problem wherein an adversary controls a subset of nodes in the network of limited quantity but unknown location. This problem is shown to be more difficult than that of an adversary controlling a given number of edges in the network, in that linear codes are insufficient. To solve the node problem, the class of polytope codes is introduced. Polytope codes are constant composition codes operating over bounded polytopes in integer vector fields. The polytope structure creates additional complexity, but it induces properties on marginal distributions of code vectors so that validities of codewords can be checked by internal nodes of the network. It is shown that polytope codes achieve a cut-set bound for a class of planar networks. It is also shown that this cut-set bound is not always tight, and a tighter bound is given for an example network.

As a state-of-the-art programming model for big data analytics, MapReduce is well suited for parallel processing of large data sets in opportunistic environments. Existing research on MapReduce in opportunistic environment has focused on improving single job performance, the issue of fairness that is critical in the more dominant scenario of multiple concurrent jobs remains unexplored. We address this problem by proposing an opportunistic fair scheduling algorithm, which extends the broadly adopted Fair Scheduler to an environment where nodes are intermittently available with possibly different availability patterns. The proposed scheduler maintains statistics specific to the opportunistic environment, e.g., node availability rates and pairwise availability correlations, and utilizes this information in scheduling decisions to improve fairness. Using a Hadoop-based implementation, we compare our scheduler with the current Hadoop Fair Scheduler on representative benchmarks. Our experiments verify that our scheduler can significantly reduce the variability in job completion times.

We consider the problem of estimating two deterministic vectors in a linear Gaussian model where one of the unknown vectors is subject to a sparsity constraint. We derive the maximum likelihood estimator for this problem and develop the Projected Orthogonal Matching Pursuit (POMP) algorithm for its practical implementation. The corresponding constrained Cramér-Rao bound (CCRB) on the mean-square-error is developed under the sparsity constraint. We then show that estimation in linear dynamical systems with a sparse control can be formulated as a special case of this problem.

The papers in this special issue explore advances in communication technologies that have the potential for improving energy efficiency and realizing the smart grid vision.

Covert data attacks on the network topology of a smart grid is considered. In a so-called man-in-the-middle attack, an adversary alters data from certain meters and network switches to mislead the control center with an incorrect network topology while avoiding detections by the control center. A necessary and sufficient condition for the existence of an undetectable attack is obtained for strong adversaries who can observe all meter and network data. For weak adversaries with only local information, a heuristic method of undetectable attack is proposed. Countermeasures to prevent undetectable attacks are also considered. It is shown that undetectable attacks do not exist if a set of meters satisfying a certain branch covering property are protected. The proposed attacks are tested with IEEE 14-bus and IEEE 118-bus system, and their effect on real-time locational marginal pricing is examined.

In this letter, we consider the problem of joint off-nominal frequency and phasor estimation that incorporates Kirchhoff's Current Law (KCL) as a constraint. We develop the constrained maximum likelihood (CML) and constrained weighted least-squares (CWLS) estimators for this problem and derive the corresponding constrained Cramér-Rao bound. The KCL constraint is shown to behave as a noise cancellation factor for the phasors estimation. We show that the KCL CML is based on the classical periodogram subtracting the average current periodogram. The results indicate significant performance improvement compared to the unconstrained maximum likelihood (ML) and unconstrained weighted least-squares (WLS).

Multipacket reception (MPR) refers to physical layers where receivers can decode multiple simultaneously transmitted packets. In this paper we investigate the resulting performance of conjoining carrier sense multiple access (CSMA) communications with MPR. We report on its maximum achievable stable throughput with decentralized control and show there can be throughput gain over slotted ALOHA (S-ALOHA), the non-channel-sensing protocol of choice. However, this gain diminishes as the physical layer's MPR strength increases, thereby diminishing the need for channel sensing. Nonetheless, for systems evolving from a single-user (SU) to a multiple-user (MU) channel, CSMA can furnish significantly more efficient utilization of MPR capacity than S-ALOHA. This is meaningful in practice because the emerging generation of the widely deployed IEEE 802.11 wireless local area networks (WLAN) - 802.11ac - is adapting MPR and will operate in said region. In that regard, we also discuss the effective usage of a channel's resources for MPR and highlight the advantages multiuser-MIMO (MU-MIMO), an MPR technique, can offer to WLANs. Using early design specifications of 802.11ac, we show that the existing SU-oriented 802.11 MAC parameters can under-utilize the MPR capacity offered by a MU-oriented physical layer.

Given two independent point processes and a certain rule for matching points between them, what is the fraction of matched points over infinitely long streams? In many application contexts, e.g., secure networking, a meaningful matching rule is that of a maximum causal delay, and the problem is related to embedding a flow of packets in cover traffic such that no timing analysis can detect it. We study the best undetectable embedding policy and the corresponding maximum flow rate-that we call the embedding capacity-under the assumption that the cover traffic can be modeled as an arbitrary renewal process. We find that computing the embedding capacity requires the inversion of a very structured linear system that, for a broad range of renewal models encountered in practice, admits a fully analytical expression in terms of the renewal function of the processes. This result enables us to explore the properties of the embedding capacity, obtaining closed-form solutions for selected distribution families and a suite of sufficient conditions on the capacity ordering. We test our solution on real network traces, which shows a remarkable match for tight delay constraints. A gap between the predicted and the actual embedding capacities appears for looser constraints, and further investigation reveals that it is caused by inaccuracy of the renewal traffic model rather than of the solution itself.

This paper studies a minimal-energy driving strategy for high-speed electric trains with a fixed travel time. A hybrid system model is proposed to describe the new characteristics of high-speed electric trains, including the extended speed range, energy efficiency, and regenerative braking. Based on this model, train driving is characterized by the gear sequence and the switching locations. An approximate gradient information is derived via the variational principle. To avoid a combinatorial explosion, the gear sequence is fixed by a priori knowledge. Then, a gradient-based exterior point method is proposed to calculate the optimal driving. In the case study, the minimal-energy driving with a fixed travel time for CRH-3 is investigated, and the result reveals some new understandings for high-speed electric train drive. Additionally, the tradeoff relationship between energy consumption and travel time is quantitatively studied, which is helpful in assigning an appropriate travel time for high-speed trains.

We consider the problem of opportunistically scheduling low-priority tasks onto underutilized computation resources in the cloud left by high-priority tasks. To avoid conflicts with high-priority tasks, the scheduler must suspend the low-priority tasks (causing waiting), or move them to other underutilized servers (causing migration), if the high-priority tasks resume. The goal of opportunistic scheduling is to schedule the low-priority tasks onto intermittently available server resources while minimizing the combined cost of waiting and migration. Moreover, we aim to support multiple parallel low-priority tasks with synchronization constraints. Under the assumption that servers' availability to low-priority tasks can be modeled as ON/OFF Markov chains, we have shown that the optimal solution requires solving a Markov Decision Process (MDP) that has exponential complexity, and efficient solutions are known only in the case of homogeneously behaving servers. In this paper, we propose an efficient heuristic scheduling policy by formulating the problem as restless Multi-Armed Bandits (MAB) under relaxed synchronization. We prove the index ability of the problem and provide closed-form formulas to compute the indices. Our evaluation using real data center traces shows that the performance result closely matches the prediction by the Markov chain model, and the proposed index policy achieves consistently good performance under various server dynamics compared with the existing policies.

The problem of minimizing queueing delay of opportunistic access of multiple continuous time Markov channels is considered. A new access policy based on myopic sensing and adaptive transmission (MS-AT) is proposed. Under the framework of risk sensitive constrained Markov decision process with effective bandwidth as a measure of queueing delay, it is shown that MS-AT achieves simultaneously throughput and delay optimality. It is shown further that both the effective bandwidth and the throughput of MS-AT are two-segment piece-wise linear functions of the collision constraint (maximum allowable conditional collision probability) with the effective bandwidth and throughput coinciding in the regime of tight collision constraints. Analytical and simulation comparisons are conducted with the myopic sensing and memoryless transmission (MS-MT) policy which is throughput optimal but delay suboptimal in the regime of tight collision constraints.

We consider the problem of scheduling low-priority tasks onto resources already assigned to high-priority tasks. Due to burstiness of the high-priority workloads, the resources can be temporarily underutilized and made available to the low-priority tasks. The increased level of utilization comes at a cost to the low-priority tasks due to intermittent resource availability. Focusing on two major costs, bandwidth cost associated with migrating tasks and latency cost associated with suspending tasks, we aim at developing online scheduling policies achieving the optimal bandwidth-latency tradeoff for parallel low-priority tasks with synchronization requirements. Under Markovian resource availability models, we formulate the problem as a Markov Decision Process (MDP) whose solution gives the optimal scheduling policy. Furthermore, we discover structures of the problem in the special case of homogeneous availability patterns that enable a simple threshold-based policy that is provably optimal. We validate the efficacy of the proposed policies by trace-driven simulations.

This paper presents a distributed Demand and Response algorithm for smart grid with the objective of optimizing social-welfare. Assuming the power demand range is known or predictable ahead of time, our proposed distributed algorithm will calculate demand and response of all participating energy demanders and suppliers, as well as energy flow routes, in a fully distributed fashion, such that the social-welfare is optimized. During the computation, each node (e.g., demander or supplier) only needs to exchange limited rounds of messages with its neighboring nodes. It provides a potential scheme for energy trade among participants in the smart grids. Our theoretical analysis proves that the algorithm converges even if there is some random noise induced in the process of our distributed Lagrange-Newton based solution. The simulation also shows that the result is close to that of centralized solution.

Anonymous wireless networking is studied when an adversary monitors the transmission timing of an unknown subset of the network nodes. For a desired quality of service (QoS), as measured by network throughput, the problem of maximizing anonymity is investigated from a game-theoretic perspective. Quantifying anonymity using conditional entropy of the routes given the adversary's observation, the problem of optimizing anonymity is posed as a two-player zero-sum game between the network designer and the adversary: The task of the adversary is to choose a subset of nodes to monitor so that anonymity of routes is minimum, whereas the task of the network designer is to maximize anonymity by choosing a subset of nodes to evade flow detection by generating independent transmission schedules. In this two-player game, it is shown that a unique saddle-point equilibrium exists for a general category of finite networks. At the saddle point, the strategy of the network designer is to ensure that any subset of nodes monitored by the adversary reveals an identical amount of information about the routes. For a specific class of parallel relay networks, the theory is applied to study the optimal performance tradeoffs and equilibrium strategies. In particular, when the nodes employ transmitter-directed signaling, the tradeoff between throughput and anonymity is characterized analytically as a function of the network parameters and the fraction of nodes monitored. The results are applied to study the relationships between anonymity, the fraction of monitored relays, and the fraction of hidden relays in large networks.

We consider a cognitive radio network where multiple secondary users (SUs) contend for spectrum usage, using random access, over available primary user (PU) channels. Our focus is on SUs' queueing delay performance, for which a systematic understanding is lacking. We take a fluid queue approximation approach to study the steady-state delay performance of SUs, for cases with a single PU channel and multiple PU channels. Using stochastic fluid models, we represent the queue dynamics as Poisson driven stochastic differential equations, and characterize the moments of the SUs' queue lengths accordingly. Since in practical systems, an SU would have no knowledge of other users' activities, its contention probability has to be set based on local information. With this observation, we develop adaptive algorithms to find the optimal contention probability that minimizes the mean queue lengths. Moreover, we study the impact of multiple channels and multiple interfaces on SUs' delay performance. As expected, the use of multiple channels and/or multiple interfaces leads to significant delay reduction. Finally, we consider packet generation control to meet the delay requirements for SUs, and develop randomized and queue-length-based control mechanisms accordingly.

The problem of distributed multiuser medium access of a hierarchical cognitive radio network with multiple primary and secondary users is considered. Each primary user has a licensed channel; it allows access by secondary cognitive users under certain collision constraints. The secondary cognitive users seek to capture transmission opportunities while avoiding collisions with primary and other secondary users. Under tight collision constraints, we establish the maximum throughput region achievable by distributed multiaccess of secondary users when the number of secondary users is less than the number of primary channels using a scheme referred to as the Distributed Orthogonal and Periodic Sensing with Memoryless Access (DOPS-MA). Packet-level simulations are used to validate the performance prediction.

Malicious data attacks to the real-time electricity market are studied. In particular, an adversary launches an attack by manipulating data from a set of meters with the goal of influencing revenues of a real-time market. The adversary must deal with the tradeoff between avoiding being detected by the control center and making maximum profit from the real time market. Optimal attacking strategy is obtained through an optimization of a quasi-concave objective function. It is shown that the probability of detection of optimal attack will always be less than 0.5. Attack performance is evaluated using simulations on the IEEE 14-bus system.

The secure networking problem of embedding information flows into cover traffic is addressed. When relayed packets must obey a causal delay constraint, this naturally remaps to a matching problem between point processes (here taken as arbitrary renewal processes). The best hiding policy is thus characterized in terms of the maximum fraction of matched points, which is accordingly referred to as embedding capacity. For a broad range of renewal models encountered in practice, we provide a simple analytical formula for the capacity, which depends only on the renewal function of the underlying processes, and further find conditions for capacity-ordering of different types of cover traffic. The results are also tested on real network traces, and a very good match is observed, especially for tight delay constraints.

The problem of cognitive access of multiple primary channels by multiple cognitive users is considered. The primary transmission on each channel is modeled by a continuous time Markov on-off process. Cognitive access of the primary channels is realized via channel sensing. Each cognitive user adopts a slotted transmission structure, senses one channel in each slot and makes the transmission decision based on the sensing outcome. The cognitive transmissions in each channel are subject to collision constraints that limit their interference to the primary users. The maximum throughput region of this multiuser cognitive network is characterized by establishing inner and outer bounds. Under tight collision constraints, the inner bound is obtained by a simple orthogonalized periodic sensing with memoryless access policy and its generalizations. The outer bound, on the other hand, is obtained by relating the sum throughput with the interference limits. It is shown that when collision constraints are tight, the outer and inner bounds match. This maximum throughput region result is further extended by a generalized periodic sensing scheme with a mechanism of timing sharing. Under general collision constraints, another outer bound is obtained via Whittle's relaxation and another inner bound obtained via Whittle's index sensing policy with memoryless access. Packet level simulations are used to validate the analytical performance prediction.

The problem of cognitive access of channels of primary users by a secondary user is considered. The transmissions of primary users are modeled as independent continuous-time Markovian on-off processes. A secondary cognitive user employs a slotted transmission format, and it senses one of the possible channels before transmission. The objective of the cognitive user is to maximize its throughput subject to collision constraints imposed by the primary users. The optimal access strategy is in general a solution of a constrained partially observable Markov decision process, which involves a constrained optimization in an infinite dimensional functional space. It is shown in this paper that, when the collision constraints are tight, the optimal access strategy can be implemented by a simple memoryless access policy with periodic channel sensing. Analytical expressions are given for the thresholds on collision probabilities for which memoryless access performs optimally. Extensions to multiple secondary users are also presented. Numerical and theoretical results are presented to validate and extend the analysis for different practical scenarios.

The problem of maximum-likelihood (ML) estimation of discrete tree-structured distributions is considered. Chow and Liu established that ML-estimation reduces to the construction of a maximum-weight spanning tree using the empirical mutual information quantities as the edge weights. Using the theory of large-deviations, we analyze the exponent associated with the error probability of the event that the ML-estimate of the Markov tree structure differs from the true tree structure, given a set of independently drawn samples. By exploiting the fact that the output of ML-estimation is a tree, we establish that the error exponent is equal to the exponential rate of decay of a single dominant crossover event. We prove that in this dominant crossover event, a non-neighbor node pair replaces a true edge of the distribution that is along the path of edges in the true tree graph connecting the nodes in the non-neighbor pair. Using ideas from Euclidean information theory, we then analyze the scenario of ML-estimation in the very noisy learning regime and show that the error exponent can be approximated as a ratio, which is interpreted as the signal-to-noise ratio (SNR) for learning tree distributions. We show via numerical experiments that in this regime, our SNR approximation is accurate.

The problem of cognitive access of channels of primary users by a secondary user is considered. The transmissions of primary users are modeled as independent continuous-time Markovian on-off processes. A secondary cognitive user employs slotted transmissions, and it senses one of the possible channels before transmission. The objective of the cognitive user is to maximize its throughput subject to collision constraints imposed by the primary users. The optimal access strategy is in general a solution of a constrained partially observable Markov decision process, which involves a constrained optimization in an infinite dimensional functional space. It is shown in this paper that, when the collision constraints are tight, the optimal access strategy can be implemented by a simple memoryless access policy with periodic channel sensing. Numerical results are presented to validate and extend the analysis for different practical scenarios.

The queueing performance of a (secondary) cognitive user is investigated for a hierarchical network where there are N independent and identical primary users. Each primary user employs a slotted transmission protocol, and its channel usage forms a two-state (busy, idle) discrete-time Markov chain. The cognitive user employs the optimal policy to select which channel to sense (and use if found idle) at each slot. In the framework of effective bandwidths, the stationary queue tail distribution of the cognitive user is estimated using a large deviation approach for which closed-form expressions are obtained when N = 2. Upper and lower bounds are obtained for the general N primary user network. For positively correlated primary transmissions, the bounds are shown to be asymptotically tight. Monte Carlo simulations using importance sampling techniques are used to validate the obtained large deviation estimates.

We consider a cognitive radio network where multiple secondary users (SUs) contend for spectrum usage, using random access, over available primary user (PU) channels. Our focus is on SUs' queueing delay performance, for which a systematic understanding is lacking. We take a fluid queue approximation approach to study the steady-state delay performance of SUs, for cases with a single PU channel and multiple PU channels. Using stochastic fluid models, we represent the queue dynamics as Poisson driven stochastic differential equations, and characterize the moments of the SUs' queue lengths accordingly. Since in practical systems, a secondary user would have no knowledge of other users' activities, its contention probability has to be set based on local information. With this observation, we develop adaptive algorithms to find the optimal contention probability that minimizes the mean queue lengths. Moreover, we study the impact of multiple channels and multiple interfaces, on SUs' delay performance. As expected, the use of multiple channels and/or multiple interfaces leads to significant delay reduction.

Network coding is studied when an unknown subset of nodes in the network is controlled by an adversary. To solve this problem, a new class of codes called Polytope Codes is introduced. Polytope Codes are linear codes operating over bounded polytopes in real vector fields. The polytope structure creates additional complexity, but it induces properties on marginal distributions of code vectors so that validities of codewords can be checked by internal nodes of the network. It is shown that a cut-set bound for a class planar networks can be achieved using Polytope Codes. It is also shown that this cut-set bound is not always tight, and a tighter bound is given for an example network.

Dynamic spectrum access (DSA) aims to improve spectrum efficiency via spectrum sensing and optimal spectrum access. An essential component in DSA is the joint design of sensing and access strategies. This paper focuses on dynamic spectrum access in the time domain. To maximize channel utilization while limiting interference to primary users, a framework of linear programming is presented based on the stationary distribution of the primary user channels. It is shown that the optimal tradeoff between sensing and transmitting is achieved with required limit on the interference to the primary users.

The problem of localizing in-band wormhole tunnels inMANETs is considered. In an in-band wormhole attack, colluding attackers use a covert tunnel to create the illusion that two remote network regions are directly connected. This apparent shortcut in the topology attracts traffic which the attackers can then control.

In this paper a communication system operating over a Gilbert-Elliot channel is studied. The goal of the transmitter is to maximize the number of successfully transmitted bits. This is achieved by choosing among three possible actions: (i) betting aggressively by using a weak code that allows transmission with a high data rate but provides no protection against a bad channel, ii) betting conservatively by using a strong code that perfectly protects the communication against a bad channel but does not allow a high data rate, iii) betting opportunistically by sensing the channel for a fixed duration and then deciding which code to use. The problem is formulated and solved using the theory of Markov decision processes (MDPs). It is shown that the optimal strategy has a simple threshold structure. Closed form expressions and simplified procedures for the computation of the threshold policies in terms of the system parameters are provided.

Abstract The rapid proliferation of wireless systems makes interference management more and more important. This paper presents a novel cognitive coexistence framework, which enables an infrastructure system to reduce interference toad hocor peer‐to‐peer communication links in close proximity. Motivated by the superior resources of the infrastructure system, we study how its centralized resource allocation can accommodate thead hoclinks based on sensing and predicting their interference patterns. Based on an ON/OFF continuous‐time Markov chain model, the optimal allocation of power and transmission time is formulated as a convex optimization problem and structured solutions are derived. The optimal scheduling is extended to the case where the infrastructure channel is random and rate constraints need only be met in the long‐term average. Finally, the multi‐terminal case is addressed and the problem of optimal sub‐channel allocation is discussed. Numerical performance analysis illustrates that utilizing the superior flexibility of the infrastructure links can effectively mitigate interference. Copyright © 2009 John Wiley & Sons, Ltd.

A novel formulation for optimal sensor selection and in-network fusion for distributed inference known as the prize- collecting data fusion (PCDF) is proposed in terms of optimal tradeoff between the costs of aggregating the selected set of sensor measurements and the resulting inference performance at the fusion center. For i.i.d. measurements, PCDF reduces to the prize-collecting Steiner tree (PCST) with the single-letter Kullback-Leibler divergence as the penalty at each node, as the number of nodes goes to infinity. PCDF is then analyzed under a correlation model specified by a Markov random field (MRF) with a given dependency graph. For a special class of dependency graphs, a constrained version of the PCDF reduces to the PCST on an augmented graph. In this case, an approximation algorithm is given with the approximation ratio depending only on the number of profitable cliques in the dependency graph. Based on these results, two heuristics are proposed for node selection under general correlation structure, and their performance is studied via simulations.

The problem of binary hypothesis testing is considered when the measurements are drawn from a Markov random field (MRF) under each hypothesis. Spatial dependence of the measurements is incorporated by explicitly modeling the influence of sensor node locations on the clique potential functions of each MRF hypothesis. The nodes are placed i.i.d. in expanding areas with increasing sample size. Asymptotic performance of hypothesis testing is analyzed through the Neyman-Pearson type-II error exponent. The error exponent is expressed as the limit of a functional over dependency edges of the MRF hypotheses for acyclic graphs. Using the law of large numbers for graph functionals, the error exponent is derived.

The quadratic Gaussian CEO problem is studied when the agents are under Byzantine attack. That is, an unknown subset of agents is controlled by an adversary that attempts to damage the quality of the estimate at the central estimation officer, or CEO. Inner and outer bounds are presented for the achievable rate region as a function of the fraction of adversarial agents. The inner bound is derived from a generalization of the Berger-Tung quantize-and-bin strategy, which has been shown to be tight in the non-Byzantine case. The outer bound has similarities to the singleton bound in that the traitorous agents must be prevented from allowing two sources to result in the same transmitted codewords if their values are too far apart for the distortion constraint to be satisfied with a single estimate. The inner and outer bounds on the rate regions are used to find bounds on the asymptotic proportionality constant in the limit of a large number of agents and high sum-rate. These bounds on the proportionality constant differ at most by a factor of 4.

The problem of maximum-likelihood learning of the structure of an unknown discrete distribution from samples is considered when the distribution is Markov on a tree. Large-deviation analysis of the error in estimation of the set of edges of the tree is performed. Necessary and sufficient conditions are provided to ensure that this error probability decays exponentially. These conditions are based on the mutual information between each pair of variables being distinct from that of other pairs. The rate of error decay, or error exponent, is derived using the large-deviation principle. The error exponent is approximated using Euclidean information theory and is given by a ratio, to be interpreted as the signal-to-noise ratio (SNR) for learning. Numerical experiments show the SNR approximation is accurate.

The energy scaling laws of multihop data fusion networks for distributed inference are considered. The fusion network consists of randomly located sensors distributed i.i.d. according to a general spatial distribution in an expanding region. Under Markov random field (MRF) hypotheses, among the class of data-fusion policies which enable optimal statistical inference at the fusion center using all the sensor measurements, the policy with the minimum average energy consumption is bounded below by the average energy of fusion along the minimum spanning tree, and above by a suboptimal policy, referred to as Data Fusion for Markov Random Fields (DFMRF). Scaling laws are derived for the energy consumption of the optimal and suboptimal fusion policies. It is shown that the average asymptotic energy of the DFMRF scheme is strictly finite for a class of MRF models with Euclidean stabilizing dependency graphs.

The problem of hypothesis testing against independence for a Gauss–Markov random field (GMRF) is analyzed. Assuming an acyclic dependency graph, an expression for the log-likelihood ratio of detection is derived. Assuming random placement of nodes over a large region according to the Poisson or uniform distribution and nearest-neighbor dependency graph, the error exponent of the Neyman–Pearson detector is derived using large-deviations theory. The error exponent is expressed as a dependency-graph functional and the limit is evaluated through a special law of large numbers forstabilizinggraph functionals. The exponent is analyzed for different values of the variance ratio and correlation. It is found that a more correlated GMRF has a higher exponent at low values of the variance ratio whereas the situation is reversed at high values of the variance ratio.

The proliferation of wireless systems requires that the coexistence between heterogeneous technologies be addressed. This paper presents a cognitive framework in which sensing- based resource management of an infrastructure system effectively suppresses interference to close-by ad-hoc or peer-to- peer links. By utilizing its superior communication resources the infrastructure system estimates interference conditions and judiciously allocates transmission power such as to minimize interference. Despite adapting its transmission behavior, a rate constraint ensures that the infrastructure system continues to meet a specified quality-of-service level. The problem of optimal coexistence is formulated as a convex program. Structured solutions similar to classical water filling are derived and a solution method with guaranteed convergence is developed. An average-rate formulation extends the results to water filling across frequency and time. Numerical results corroborate our analysis and demonstrate a promising interference reduction.

The problem of interest is to characterize to what extent nodes independently following certain transmission schedules can be hijacked to relay flows of information packets. Information flows can be embedded in given transmission schedules by properly adding delays and inserting dummy packets. Such hidden flows are usually indicators of network intrusion, and it is of interest to know their rates. The maximum rate of information flow that can be transmitted without causing the transmission activities to deviate from given transmission schedules is used to measure the covert capacity under these schedules. Based on the assumption that information flows have bounded delays, a theoretical framework is constructed to quantitively analyze the covert capacity under transmission schedules modeled by renewal processes. Explicit solution is obtained for Poisson processes. The results suggest a close correlation between the covert capacity and the traffic burstiness.

We propose a randomized transmission scheme for minimizing a time-averaged cost metric in a cognitive radio. We assume that a single cognitive radio (i.e., a transmitter and receiver) hops over N orthogonal channels, each occupied by a primary user whose ON-OFF activity is modeled by a two-state Markov chain. We assume that the cognitive radio senses the activity in each channel at the beginning of every symbol period, and that a usage cost is assigned to each channel that depends on the channel’s physical-layer characteristics and the sensing outcome. We fully characterize the transmission scheme that minimizes the time-averaged cost, subject to interference constraints imposed by the primaries. Finally, we evaluate the performance for two special cases of the cost: the bit error rate and (lower and upper bounds on) the channel capacity.

The problem of minimum cost in-network fusion of measurements, collected from distributed sensors via multihop routing is considered. A designated fusion center performs an optimal statistical-inference test on the correlated measurements, drawn from a Markov random field. Conditioned on the delivery of a sufficient statistic for inference to the fusion center, the structure of optimal routing and fusion is shown to be a Steiner tree on a transformed graph. This Steiner-tree reduction preserves the approximation ratio, which implies that any Sterner- tree approximation can be employed for minimum cost fusion with the same approximation ratio. The proposed fusion scheme involves routing packets of two types viz., raw measurements sent for local processing, and aggregates obtained on combining these processed values. The performance of heuristics for minimum cost fusion are evaluated through theory and simulations, showing a significant saving in routing costs, when compared to routing all the raw measurements to the fusion center.

Providing anonymity to routes in a wireless ad hoc network from passive eavesdroppers is considered. Using Shannon's equivocation as an information theoretic measure of anonymity, scheduling strategies are designed for wireless nodes using receiver directed signaling. The achievable rate region for multiaccess relays are characterized under constraints on average packet latency. The relationship between overall network throughput and the route anonymity is obtained by drawing a connection to the rate-distortion tradeoff in information theory. A decentralized implementation of the relaying strategy is proposed, and the corresponding performance analyzed.

The problem of distributed fusion for binary hypothesis testing in a multihop network is considered. The sensor measurements are spatially correlated according to a Markov random field (MRF) under both the hypotheses. A fusion scheme for detection involves selection and localized processing of a subset of sensor measurements, fusion of these processed values to form a sufficient statistic, and its delivery to the fusion center. The goal is to find a fusion scheme that achieves optimal linear tradeoff between the total routing costs and the resulting detection error exponent at the fusion center. The Neyman-Pearson error exponent, under a fixed type-I bound, is shown to be the limit of the normalized sum of the Kullback-Leibler distances (KLD) over the maximal cliques of the MRF under some convergence conditions. It is shown that optimal fusion reduces to a prize- collecting Steiner tree (PCST) with the approximation factor preserved when the cliques of the MRF are disjoint. The PCST is found over an expanded communication graph with virtual nodes added for each non-trivial maximal clique of the MRF and their KLD assigned as the node penalty.

The CEO Problem is considered when a subset of the agents are under Byzantine attack; that is, they have been taken over and reprogrammed by a malicious intruder. Inner and outer bounds are given for the error exponent with respect to the sum rate, as a function of the fraction of reprogrammed, or traitor, agents. The inner bound is proved by introducing a coding scheme that takes advantage of the fact that the set of honest (non-traitor) agents will report jointly typical information. The CEO looks for a group with the same size as the set of honest agents that appear to do so. Even if not all the agents in this group are honest, the fact that they all agree keeps the probability of error in check. The outer bound is given in two parts, based on two different possible attacks by the traitors. The first is a black hole attack, in which the traitors simply transmit no information at all. The second is one in which they fabricate false data such that the CEO cannot determine which of two possibilities is the truth.

The problem of security against timing based traffic analysis in multihop networks is considered in this work. In particular, the relationship between the level of anonymity provided and the quality of service, as measured by network latency, is analyzed theoretically. Using an information theoretic measure of anonymity of routes in eavesdropped networks is considered, and packet scheduling strategies are designed to guarantee any desired level of anonymity. In particular, for individual relays, scheduling strategies based on mixing are designed so that the incoming and outgoing transmission epochs do not reveal any information. The proposed strategies utilize a limited fraction of dummy transmissions, and a significant reduction in packet latency at individual relays is demonstrated analytically for Poisson distributed arrivals. To minimize overall network latency, a randomized selection strategy is considered to choose the set of relays that use the designed scheduling strategies. The random selection is optimized for the desired level of anonymity using a well known distortion rate optimization in information theory. The tradeoff between overall network latency and anonymity in the network is characterized for centralized and decentralized scheduling strategies.

In this paper we design a cognitive radio that can coexist with multiple parallel WLAN channels while abiding by an interference constraint. The interaction between both systems is characterized by measurement and coexistence is enhanced by predicting the WLAN's behavior based on a continuous-time Markov chain model. Cognitive medium access (CMA) is derived from this model by recasting the problem as one of constrained Markov decision processes. Solutions are obtained by linear programming. Furthermore, we show that optimal CMA admits structured solutions, simplifying practical implementations. Preliminary results for the partially observable case are presented. The performance of the proposed schemes is evaluated for a typical WLAN coexistence setup and shows a significant performance improvement.

Distributed detection of information flows is considered in which traffic sensors at different locations of a network observe transmission epochs. The traffic sensors communicate their measurements to a fusion center via channels with rate constraints, and the fusion center performs hypothesis testing for information flow detection. Under a nonparametric flow model where relayed packets can be perturbed up to bounded delays and multiplexed with chaff noise, flow detectability is characterized through a notion called consistency-rate function that shows the level of detectable flows under capacity constraints on the fusion channels. Achievability results are presented by constructing detection systems consisting of quantization, data transmission, and detection subsystems. In particular, slot-by-slot quantization schemes at the local sensors and threshold detection schemes at the fusion center are proposed to provide consistent detection with quantifiable performance.

In this correspondence, the problem of distributed Bayesian estimation is considered in the context of a wireless sensor network. The Bayesian estimation performance is analyzed in terms of the expected Fisher information normalized by the transmission rate of the sensors. The sensors use a communication scheme known as the type-based random access (TBRA) scheme. Under a constraint on the expected transmission energy, an optimal spatio-temporal allocation scheme that maximizes the performance metric is characterized. It is shown that the performance metric is crucially dependent on the fading parameter known as the channel coherence index. For channels with low coherence indices, sensor transmissions tend to cancel each other, and there exists an optimal finite mean transmission rate that maximizes the performance metric. On the other hand, for channels with high coherence indices, there should be as many simultaneous transmissions as allowed by the network. The presence of a critical coherence index where the change from one behavior to another occurs is established.

The detection of information flows by timing analysis is considered. Given transmission timestamps of monitored nodes, the problem is to decide whether there is an information flow through these nodes by analyzing the transmission patterns. Due to constraints that packets from an information flow need to be delivered within certain delay or the relay nodes have bounded memory, transmission patterns of an information flow are statistically different from those of independent traffic. The main result of this paper is a tight characterization of the maximum amount of chaff noise such that Chernoff-consistent detection is achievable. The direct part of the result is an explicit construction of a detector that has vanishing false alarm and miss probabilities as the sample size increases whenever the noise level is below certain threshold. Conversely, when the noise level is above this threshold, there exist means to hide the information flow such that it is indistinguishable from independent traffic. Explicit characterization of the noise threshold is provided for Poisson transmission schedules. It is also shown that while information flows can be hidden among chaff noise for a small number of hops, the rate of information flow diminishes as the number of hops increases.

The distributed source coding problem is considered when the sensors, or encoders, are under Byzantine attack; that is, an unknown group of sensors have been reprogrammed by a malicious intruder to undermine the reconstruction at the fusion center. Three different forms of the problem are considered. The first is a variable-rate setup, in which the decoder adaptively chooses the rates at which the sensors transmit. An explicit characterization of the variable-rate achievable sum rates is given for any number of sensors and any groups of traitors. The converse is proved constructively by letting the traitors simulate a fake distribution and report the generated values as the true ones. This fake distribution is chosen so that the decoder cannot determine which sensors are traitors while maximizing the required rate to decode every value. Achievability is proved using a scheme in which the decoder receives small packets of information from a sensor until its message can be decoded, before moving on to the next sensor. The sensors use randomization to choose from a set of coding functions, which makes it probabilistically impossible for the traitors to cause the decoder to make an error. Two forms of the fixed-rate problem are considered, one with deterministic coding and one with randomized coding. The achievable rate regions are given for both these problems, and it is shown that lower rates can be achieved with randomized coding.

The problem of security against packet timing based traffic analysis in wireless networks is considered in this work. An analytical measure of ldquoanonymityrdquo of routes in eavesdropped networks is proposed using the information-theoretic equivocation. For a physical layer with orthogonal transmitter directed signaling, scheduling and relaying techniques are designed to maximize achievable network performance for any desired level of anonymity. The network performance is measured by the total rate of packets delivered from the sources to destinations under strict latency and medium access constraints. In particular, analytical results are presented for two scenarios: For a single relay that forwards packets from users, relaying strategies are provided that minimize the packet drops when the source nodes and the relay generate independent transmission schedules. A relay using such an independent scheduling strategy is undetectable by an eavesdropper and is referred to as a covert relay. Achievable rate regions are characterized under strict and average delay constraints on the traffic, when schedules are independent Poisson processes. For a multihop network with an arbitrary anonymity requirement, the problem of maximizing the sum-rate of flows (network throughput) is considered. A randomized selection strategy to choose covert relays as a function of the routes is designed for this purpose. Using the analytical results for a single covert relay, the strategy is optimized to obtain the maximum achievable throughput as a function of the desired level of anonymity. In particular, the throughput-anonymity relation for the proposed strategy is shown to be equivalent to an information-theoretic rate-distortion function.

An information theoretic queueing model is proposed in a wireless multiple access communication setup. The proposed symmetric N user model captures physical layer parameters such as the encoding rate, transmit power and Medium Access Control (MAC) layer metrics such as queue stability. Two alternative medium access strategies are considered: centralized scheduling and ALOHA. Next, a cross-layer approach is taken wherein the maximum stable throughput of the system is achieved by a joint optimization over the MAC parameters (viz., scheduling set size with scheduling and transmission probability with ALOHA) and the encoding rate. Performance comparisons with traditional layered designs are given. It is shown that in the low and high SNR regimes, layered designs are close to optimal whereas in the moderate SNR range, cross-layer designs outperform layered schemes. Exact characterizations of the ";low"; and ";high"; SNR regimes are given quantitatively. It is also shown that ALOHA with transmission probability one is optimal in the low SNR regime.

In this paper we propose cognitive medium access (CMA), a protocol aimed at improving coexistence with a set of independently evolving WLAN bands. A time-slotted physical layer for the cognitive radio is considered and CMA is derived based on experimental models. By recasting the problem as a constrained Markov decision process (CMDP), throughput is optimized while keeping interference below some given constraint. The optimal control policy is obtained via linear programming. In addition, we show that optimal CMA admits structured solutions which are computationally less expensive and allow further insight into the problem. Numerical results are presented for typical coexistence setups and show a significant performance improvement.

The problem of hypothesis testing against independence for a Gauss-Markov random field (GMRF) with nearest-neighbor dependency graph is analyzed. The sensors measuring samples from the signal field are placed IID according to the uniform distribution. The asymptotic performance of Neyman-Pearson detection is characterized through the large-deviation theory. An expression for the error exponent is derived using a special law of large numbers for graph functionals. The exponent is analyzed for different values of the variance ratio and correlation. It is found that a more correlated GMRF has a higher exponent (improved detection performance) at low values of the variance ratio, whereas the opposite is true at high values of the ratio.

We address the design of binary local sensor quantizers for decentralized detection over multiple access channels. Our goal is to minimize the error probability at the fusion center using a single snapshot of local observations. Considering both the synchronized and asynchronous transmissions among sensors, we establish the optimality of a likelihood ratio test for both cases. For the case of asynchronous transmissions, to compensate for the unknown fading channel parameters and transmission delays, we propose a structure consisting of a RAKE receiver and a square-law detector. Simulations results are presented to demonstrate effectiveness of the design procedure.

We introduce a likelihood based multiple access (LBMA) communication/estimation scheme for nonrandom parameter estimation in wireless sensor networks with additive multiple access channels. Constraining the system in terms of energy and allowing the available number of degrees of freedom to scale as nα, 0.5 <; α <; 1, we prove that LBMA is asymptotically efficient. Thus, the new scheme is appropriate for large networks. LBMA is, in addition, simple to implement and relies upon an intuitive approach.

We study the target class detection performance of a sensor network having a structured topology. The target is in the far-field of the network, located at a distance gamma and angle thetas, and produces a random signal field that is sampled by sensors. It is assumed that samples have a correlation structure and power level that depend on gamma, thetas and the target's class i, i isin {0,1}. We study the Neyman-Pearson miss probability error exponent for this scenario using large deviations theory. When (gamma, thetas) is known, we characterize the properties of the error exponent as a function of signal and design parameters. When (gamma, thetas) has at least one unknown component, we use the theory of adaptive tests to prove that there exists a test that achieves the same error exponent as if (gamma, thetas) were known in some scenarios, but that there exists no such test in others.

Distributed detection of information flows is considered. The detector detects the presence of information flows by collecting timing information from nodes of interest through channels of finite capacity. The information flows are assumed to be perturbed up to a bounded delay and interleaved with chaff. Joint compression and detection schemes are proposed to achieve reliable detection with inaccurate measurements. Detection performance is analytically evaluated by robustness against chaff as functions of the capacity constraints in the data collection. The proposed detectors are proved to be optimal for their corresponding quantizers. A comparison of their performance gives guidelines on quantizer design.

The distributed source coding problem is considered when the sensors, or encoders, are under Byzantine attack; that is, an unknown number of sensors have been reprogrammed by a malicious intruder to undermine the reconstruction at the fusion center. Three different forms of the problem are considered. The first is a variable-rate setup, in which the decoder adaptively chooses the rates at which the sensors transmit. An explicit characterization of the variable-rate minimum achievable sum rate is stated, given by the maximum entropy over the set of distributions indistinguishable from the true source distribution by the decoder. In addition, two forms of the fixed-rate problem are considered, one with deterministic coding and one with randomized coding. The achievable rate regions are given for both these problems, with a larger region achievable using randomized coding, though both are suboptimal compared to variable-rate coding.

The problem of dynamically accessing a set of parallel channels occupied by primary users is considered. The secondary user is allowed to sense and to transmit in a single channel. By exploiting idle periods between bursty transmissions of primary users, and by using a periodic sensing strategy, optimal dynamic access is achieved by maximizing the throughput of the secondary user while constraining collision probability with the primary user. The optimal dynamic spectrum access problem can then be formulated within the framework of constrained Markov decision processes (CMDPs). The optimal control policy is identified via a linear program, and its performance is analyzed numerically and through Monte Carlo simulations. Finally, we compare the optimal scheme to an ideal benchmark case when simultaneous sensing of all channels is assumed.

In this paper, the detection of a correlated Gaussian field using a large multi-hop sensor network is investigated. A cooperative routing strategy is proposed by introducing a new link metric that characterizes the detection error exponent. Derived from the Chernoff information and Schweppe's likelihood recursion, this link metric captures the contribution of a given link to the decay rate of error probability and has the form of the capacity of a Gaussian channel with the sender transmitting the innovation of its measurement. For one-dimensional Gauss-Markov fields, the link metric can be represented explicitly as a function of the link length. Cooperative routing is achieved using the Kalman data aggregation and shortest path routing. Numerical simulations show that cooperative routing can be significantly more energy efficient than noncooperative routing for the same detection performance

We propose decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. Recognizing hardware and energy constraints, we assume that a secondary user may not be able to perform full-spectrum sensing or may not be willing to monitor the spectrum when it has no data to transmit. We develop an analytical framework for opportunistic spectrum access based on the theory of partially observable Markov decision process (POMDP). This decision-theoretic approach integrates the design of spectrum access protocols at the MAC layer with spectrum sensing at the physical layer and traffic statistics determined by the application layer of the primary network. It also allows easy incorporation of spectrum sensing error and constraint on the probability of colliding with the primary users. Under this POMDP framework, we propose cognitive MAC protocols that optimize the performance of secondary users while limiting the interference perceived by primary users. A suboptimal strategy with reduced complexity yet comparable performance is developed. Without additional control message exchange between the secondary transmitter and receiver, the proposed decentralized protocols ensure synchronous hopping in the spectrum between the transmitter and the receiver in the presence of collisions and spectrum sensing errors

The problem of retrieving information by a mobile access point from a sensor network where sensors cooperatively transmit messages using a common codebook is considered. It is assumed that there is a probability that a sensor is misinformed with a wrong message, which complicates the information retrieval process. The access point uses the capacity achieving stay-kscheduler that schedules a sensor to transmit forkconsecutive code-letters before switching to a new sensor. The random coding exponent is derived as a function ofk, and it is shown that there is an optimalkthat gives the largest error exponent. The application of low-definition parity-check (LDPC) codes is considered next. It is shown in simulations that the optimalkof the stay-kscheduler for LDPC codes can be inferred from that for the random coding exponent.

We propose and analyze an energy-aware traffic-adaptive routing strategy for large-scale mobile ad hoc networks. Referred to as Energy-Aware GEolocation-aided Routing (EAGER), this protocol optimally blends proactive and reactive strategies for energy efficiency. Specifically, EAGER partitions the network into cells and performs intra-cell proactive routing and inter-cell reactive routing. The cell size and transmission range are optimized analytically. By adjoining cells around hot spots and hot routes in the network, EAGER is capable of handling time-varying and spatially heterogeneous traffic conditions.

In this paper we study the maximum asymptotic stable throughput of an opportunistic slotted ALOHA protocol. We provide a characterization of the maximum stable throughput as the number of users in the system goes to infinity. We then apply our findings to CDMA networks with the signal-to-interference-ratio (SIR) threshold model. It is shown that the slotted ALOHA protocol with the power/transmission control rule that equalizes the reception powers achieves 1 - O(logN/radicN) channel utilization, which is defined as the throughput divided by the optimal throughput N achieved by scheduling. This implies that the slotted ALOHA is asymptotically optimal in the sense that its channel utilization converges to 1 as the spreading gain goes to infinity

We consider information retrieval in a wireless sensor network deployed for the reconstruction of a spatially correlated signal field. Referred to as quality-of-service specific information retrieval (QUIRE), the proposed protocol optimizes the network performance under the metric of information rate per Joule while ensuring a given QoS. Based on the density of sensor deployment and the QoS specified by the maximum distortion for reconstructing the signal field, QUIRE partitions the sensor network into disjoint and equal-sized cells. The cell size is chosen to minimize the number of transmissions required for a given QoS by exploiting the spatial correlation of the signal field. Adopting the cross-layer design methodology that integrates opportunistic carrier sensing and optimal cell activation, QUIRE eliminates redundant transmissions and fully utilizes the channel reception capability in a fading environment

We consider the problem of distributed detection over a multi-access channel. Assuming a random number of sensors transmitting their observations using Type Based Multiple Access, we derive the detection performance using Large Deviations Principle as the mean number of sensors goes to infinity. We characterize the performance in terms of error exponents. We provide comparison with the case when the number of sensors is deterministic. We generalize this scheme to multiple collections, propose a Minimum Sum-Rate detector and characterize its error exponents.

Network intruders often hide their identities by sending attacks through a chain of compromised hosts that are used as "stepping stones". The difficulty in defending against such attacks lies in detecting stepping-stone connections at the compromised hosts. In this paper, to distinguish normal from attacking connections, we consider strategies that do not depend on the content of the traffic so that they are applicable to encrypted traffic. We propose a low complexity detection algorithm that has no miss detection and an exponentially-decaying false alarm probability. A sequential strategy is then developed to reduce the required number of testing packets.

In this paper, a novel medium access control (MAC) protocol, name hybrid ALOHA, is proposed to improve the system performance by allowing collision-free channel estimation and simultaneous multiuser data transmission. The idea behind it is to design an MAC protocol that is in favor of the physical (PHY) layer information transmission, and the improved PHY layer, in turn, can improve the MAC performance. Using the general multipacket reception (MPR) model as an interface between the MAC layer and the PHY layer, the hybrid ALOHA protocol is analyzed in terms of throughput, stability, as well as delay behavior. Significant performance improvement is observed in comparison with the traditional ALOHA either with the MPR model or with the collision model.

We consider the design of quantizers for the distributed estimation of a deterministic parameter, when the fusion center uses a Maximum-Likelihood estimator. We define a new metric of performance, which is to minimize the maximum ratio between the Fisher Information of the unquantized and quantized observations. Since the estimator is M-L, the criterion is equivalent to the minimizing the maximum asymptotic relative efficiency due to quantization. We propose an algorithm to obtain the quantizer that optimizes the metric and prove its convergence. Through simulations, we illustrate that the quantizer performance is close to the best possible Fisher Information as number of quantization bits increases. Furthermore, under certain conditions, the quantizer structure is found to belong to the class of score-function quantizers, hich maximize Fisher Information for a given value of the parameter.

We consider a many-to-one sensor network where a large number of sensors are deployed to monitor a physical environment. We explore sensor activity management to maximize the network lifetime while meeting the quality of service (QoS) requirement. Specifically, in each round the sink estimates the number of active sensors and the control information is fed back to the sensors for activity control. We start with a basic case where the total number of sensors N is known, and the estimator of the number of active sensors fit is accurate. We devise a sensor activity control scheme under which the number of active sensors would converge to the minimum that can meet the QoS requirement. Next, we generalize the study to the following two more complicated cases. (1) The case with known N and inaccurate nt. For this case, we propose a stochastic approximation algorithm to minimize the average number of active sensors while meeting the QoS requirement. (2) The case with unknown N and accurate nt. For this case, we cast the problem as the adaptive control of a Markov chain with unknown parameters and propose a composite optimization-oriented approach for the corresponding sensor activity control. We show that using this composite optimization-oriented approach the number of active sensors would converge to the minimum that can meet the QoS requirement

An information theoretic queueing model is proposed in a wireless multiple access communication setup. The proposed symmetric N user model captures physical layer parameters such as the encoding rate, transmit power and medium access control (MAC) layer metrics such as queue stability. Two alternative medium access strategies are considered: centralized scheduling and ALOHA. Next, a cross-layer approach is taken wherein the maximum stable throughput of the system is achieved by a joint optimization over the MAC parameters (viz., scheduling set size with scheduling and transmission probability with ALOHA) and the encoding rate. Performance comparisons with traditional layered designs are given. It is shown that in the low and high SNR regimes, layered designs are close to optimal whereas in the moderate SNR range, cross-layer designs outperform layered schemes. Exact characterizations of the "low" and "high" SNR regimes are given quantitatively. It is also shown that ALOHA with transmission probability one is optimal in the low SNR regime

We consider the transmission of space-time block codes (STBC) over doubly-selective channels, which are encountered in highly mobile environments or high-frequency (HF) communications. In particular, we propose two extensions of time-reversal STBC with superior performance under these fast-fading conditions, and compare these schemes for various decision-feedback equalizers. The tradeoffs between performance and complexity are illustrated, and simulation results for the severely doubly-selective HF-channel corroborate our analysis

In this paper, we consider a many-to-one sensor network where a large number of sensors are deployed to monitor a physical environment. We explore sensor activity management to maximize the network lifetime, while meeting the quality-of-service (QoS) requirement. Specifically, in each round the sink estimates the number of active sensors and the control information is fed back to the sensors for activity control. We start with a basic case where the total number of sensors N is known, and the estimator of the number of active sensors n/spl circ//sub t/ is accurate. We devise a sensor activity control scheme under which the number of active sensors would converge to the minimum that can meet the QoS requirement. Next, we generalize the study to the following two more complicated cases: (1) The case with known N and inaccurate n/spl circ//sub t/: For this case, we propose a stochastic approximation algorithm to minimize the average number of active sensors while meeting the QoS requirement. (2) The case with unknown N and accurate n/spl circ//sub t/: For this case, we cast the problem as the adaptive control of a Markov chain with unknown parameters and propose a composite optimization-oriented approach for the corresponding sensor activity control. We show that using this composite optimization-oriented approach the number of active sensors would converge to the minimum that can meet the QoS requirement.

This letter examines the influence of low-bit quantization on moment estimators with special emphasis on the 1-bit case. Moment estimators are especially useful if no prior knowledge on the distribution of the observations is available or if an ML approach is analytically intractable or computationally infeasible. In order to arrive at analytical results for this very general case, we focus on a dithered quantization scheme that allows us to specify and analyze its asymptotic behavior. We show that consistency can be retained under mild conditions, and furthermore, we quantify the asymptotic variance. Additionally, we illustrate how to find an estimator that achieves the best performance possible in this scenario. Finally, we bolster our analytical results with simulations for the illustrative case of an AR(1) process and provide a comparison with undithered schemes. A conclusion summarizes this letter's contribution and explores possible areas of application

Sensor network with mobile access (SENMA) is an architecture in which randomly deployed low-power sensors are orchestrated by a few powerful mobile access points. This paper considers SENMA from energy-efficiency and information-theoretic perspectives. By allowing sensors to propagate data directly to mobile access points over multiaccess channels and relieving sensors from energy-consuming network functions, SENMA has the potential of offering orders of magnitude of improvement in energy efficiency over the multihop ad hoc architecture, as demonstrated by our analysis on scalability. Optimization configurations of SENMA such as the altitude, the trajectory, and the coverage of access points are considered next, using the sum-rate as the performance metric. Optimal strategies for single and multiple access points are determined. For multiple access points, the possibility of and the gain due to cooperation (i.e., joint decoding of signals received at different access points) are investigated.

Sensor network with mobile access (SENMA) is an architecture in which randomly deployed low-power sensors are orchestrated by a few powerful mobile access points (APs). This paper considers SENMA from energy-efficiency and information-theoretic perspectives. By allowing sensors to propagate data directly to mobile APs over multiaccess channels, and relieving sensors from energy-consuming network functions, SENMA has the potential of offering orders of magnitude of improvement in energy efficiency over the multihop ad hoc architecture, as demonstrated by our analysis on scalability. Optimization configurations of SENMA such as the altitude, the trajectory, and the coverage of APs are considered next, using the sum-rate as the performance metric. Optimal strategies for single and multiple APs are determined. For multiple APs, the possibility of and the gain due to cooperation (i.e., joint decoding of signals received at different APs) are investigated

The performance of Neyman-Pearson detection of correlated random signals using noisy observations is considered. Using the large deviations principle, the performance is analyzed via the error exponent for the miss probability with a fixed false-alarm probability. Using the state-space structure of the signal and observation model, a closed-form expression for the error exponent is derived using the innovations approach, and the connection between the asymptotic behavior of the optimal detector and that of the Kalman filter is established. The properties of the error exponent are investigated for the scalar case. It is shown that the error exponent has distinct characteristics with respect to correlation strength: for signal-to-noise ratio (SNR) /spl ges/1, the error exponent is monotonically decreasing as the correlation becomes strong whereas for SNR<1 there is an optimal correlation that maximizes the error exponent for a given SNR.

We use the cutoff rate to study the optimal binary input distributions for the Rayleigh flat-fading channel with imperfect receiver channel state information (CSI). First, we evaluate the cutoff rate and analyze the optimal binary input as a function of the CSI quality and receiver SNR. Next, we study the limiting distributions - BPSK and on-off keying (OOK) - and derive an analytic design rule that allows adaptive switching between these two as the receiver CSI changes. We establish the virtues of a modulation scheme that employs only these limiting distributions, rather than the full spectrum of binary inputs. Finally, we use our results to design an adaptive modulation scheme for pilot symbol assisted modulation systems. We show that switching between just BPSK and equiprobable-OOK is nearly optimal for moderate to large SNR, and that switching between BPSK and generalized-OOK is nearly optimal for all SNR

The problem of detecting changes from data collected from a large-scale randomly deployed 2D sensor field is considered. Under a nonparametric change detection framework, we propose detection algorithms using two measures of change. The theoretical performance guarantee is derived from the Vapnik-Chervonenkis theory. By exploiting the structures of the search domain, we design a suboptimal recursive algorithm to detect the area of largest change which, for M sample points, runs in time O(M/sup 2/logM) (compared to an O(M/sup 4/) required for a straightforward exhaustive search). The lost of performance diminishes as M increases.

Following the SENMA concept, we consider a wireless network of very dumb and cheap sensors, polled by a travelling "rover". Sensors are randomly placed and isotropic: individually they have no ability to resolve the direction of arrival (DOA) of an acoustic wave. We assume that the communication load must be as limited as possible, so that these times cannot be communicated to the rover. Notwithstanding the lack of transmission of arrival times and the lack of DOA resolution ability of the individual sensors, DOA estimation is possible, and asymptotic efficiency becomes closely approximated after a reasonable number of rover snapshots. Key features are the directionality of the rover antenna, the area it surveys, and the average number of sensors inside that area, as accorded a Poisson distribution.

We study the problem of communicating sensor readings over a multiaccess channel. Previous works focused on the approach that each sensor is allocated an orthogonal channel to transmit its data as in TDMA (time-division multiple access). In this paper, we propose an. alternative method in which the sensors transmit simultaneously to deliver a noisy version of the type of sensor observations. We analyze the estimation/detection performance of this type-based multiple access (TBMA) approach in inferring a parameter /spl theta/. The data at different sensors are modeled as conditionally independent given /spl theta/. An asymptotic performance analysis is presented, and significant gains in estimation/detection performance and bandwidth usage are demonstrated.

We consider the problem of sensor node localization in a randomly deployed sensor network, using a mobile access point (AP). The mobile AP can be used to localize many sensors simultaneously in a broadcast mode, without a preestablished sensor network. We consider a multi-modal approach, combining radio and acoustics. The radio broadcasts timing, location information, and acoustic signal parameters. The acoustic emission may be used at the sensor to measure Doppler stretch, time delay, and angle of arrival. These measurements are individually sufficient to localize a sensor node, or they may be advantageously combined. We focus on the cases of Doppler and time delay. Sensor localization algorithms are developed, and performance analysis includes acoustic propagation effects caused by the turbulent atmosphere.

The problem of scheduling sensor transmissions for the detection of correlated random fields using spatially deployed sensors is considered. Using the large deviations principle, a closed-form expression for the error exponent of the miss probability is given as a function of the sensor spacing and signal-to-noise ratio (SNR). It is shown that the error exponent has a distinct characteristic: at high SNR, the error exponent monotonically increases with respect to sensor spacing, while at low SNR, there is an optimal spacing for scheduled sensors.

We propose a hybrid networking strategy for large-scale energy constrained ad hoc networks. Referred to as energy-aware geolocation aided routing (EAGER), this protocol optimally blends proactive and reactive routing strategies for energy efficiency. Specifically, EAGER partitions the network into cells and performs intracell proactive routing and inter-cell reactive routing. The cell size and transmission range are optimized analytically for energy efficiency. Furthermore, by gluing cells around the hot spots in the network, EAGER is capable of adapting to time-varying heterogenous traffic patterns.

The communication from a cooperative sensor network to a mobile access point is considered in this paper. Sensors are assumed to be informed with a global message, and some nodes are misinformed with random messages. Three system configurations are discussed based on whether a polling channel is implemented and whether an energy limit is imposed on individual sensors. The capacity of these system configurations are derived. It is shown that if a polling channel is implemented and there is no energy constraint on individual nodes, there is no rate loss with the presence of sensor errors. If there is no polling channel implemented and there is no energy constraint on individual nodes, the rate loss is proportional to the probability that a node is misinformed.

The problems of sensor configuration and activation for the detection of correlated random fields using large sensor arrays are considered. Using results that characterize the large-array performance of sensor networks in this application, the detection capabilities of different sensor configurations are analyzed and compared. The dependence of the optimal choice of configuration on parameters such as sensor signal-to-noise ratio (SNR), field correlation, etc., is examined, yielding insights into the most effective choices for sensor selection and activation in various operating regimes.

The performance of Neyman-Pearson detection of correlated stochastic signals using noisy observations is investigated via the error exponent for the miss probability with a fixed level. Using the state-space structure of the signal and observation model, a closed-form expression for the error exponent is derived, and the connection between the asymptotic behavior of the optimal detector and that of the Kalman filter is established. The properties of the error exponent are investigated for the scalar case. It is shown that the error exponent has distinct characteristics with respect to correlation strength: for signal-to-noise ratio (SNR) > 1 the error exponent decreases monotonically as the correlation becomes stronger, whereas for SNR < 1 there is an optimal correlation that maximizes the error exponent for a given SNR

In mobile asynchronous ad hoc networks, multiple users may transmit packets at the same time. If a collision occurs, then in current systems both packets are lost and need to be retransmitted, reducing the overall throughput. To mitigate this, we consider to extend the receiver with a small antenna array, so that it can suppress interfering signals. To characterize the signal of interest, we propose to modulate it at the symbol rate by a known amplitude variation. This allows the corresponding multichannel receiver to estimate the beamformer weights that will suppress the interfering sources. We introduce "known modulus algorithms" to achieve this. We also derive synchronization algorithms to estimate the offset of the desired packet in an observation window, among interfering data packets. The algorithms are illustrated via simulations.

An analytical approach to the characterization of energy consumption of large-scale wireless networks is presented. The radio model includes energy consumption of nodes at various operating states. We analyze the total energy consumption of the proactive and the reactive networking strategies, taking into account transmitting, listening, and sleeping energy. Scaling laws with respect to the increase of node density and geographical size are derived. Energy efficiency and overhead at the physical and the network layers are evaluated against message duty cycle, channel fading rate, and node mobility. The crossover point in message duty cycle below which reactive network has assured advantages is obtained. The analysis is then applied to large-scale sensor networks for applications involving data-centric and location-centric queries. The ad hoc sensor network architecture is compared with sensor networks with mobile access points.

A probabilistic sequential polling protocol (PSPP) is presented for the estimation of the sensor population in a large-scale sensor network with a mobile access point. It is shown that PSPP requires O(log/sub 2/N) sensor transmissions and a total of O((log/sub 2/N)/sup 2/) polls to achieve an arbitrarily predetermined level of accuracy.

Following the SENMA concept, we consider a wireless network of very dumb and cheap sensors, polled by a travelling "rover". Sensors are randomly placed and isotropic: Individually, they have no ability to resolve the direction of arrival (DOA) of an acoustic wave. However, they do observe the wavefront at different times. We assume that the communication load must be as limited as possible, so that these times cannot be communicated to the rover. Notwithstanding the lack of transmission of arrival times and the lack of DOA resolution ability of the individual sensors, DOA estimation is possible and simple, and asymptotic efficiency becomes closely approximated after a reasonable number of rover snapshots. Key features are the directionality of the rover antenna, the area it surveys, and the average number of sensors inside that area, as accorded a Poisson distribution.

We study the use of channel state information (CSI) for random access in fading channels. Traditionally, random access protocols have been designed by assuming simple models for the physical layer where all users are symmetric, and there is no notion of channel state. We introduce a reception model that takes into account the channel states of various users. Under the assumption that each user has access to its CSI, we propose a variant of Slotted ALOHA protocol for medium access control, where the transmission probability is allowed to be a function of the CSI. The function is called the transmission control. Assuming the finite user infinite buffer model we derive expressions for the maximum stable throughput of the system. We introduce the notion of asymptotic stable throughput (AST) that is the maximum stable throughput as the number of users goes to infinity. We consider two types of transmission control, namely, population-independent transmission control (PITC), where the transmission control is not a function of the size of the network and population-dependent transmission control (PDTC), where the transmission control is a function of the size of the network. We obtain expressions for the AST achievable with PITC. For PDTC, we introduce a particular transmission control that can potentially lead to significant gains in AST. For both PITC and PDTC, we show that the effect of transmission control is equivalent to changing the probability distribution of the channel state. The theory is then applied to code-division multiple-access (CDMA) networks with linear minimum mean-square error (LMMSE) receivers and matched filters (MF) to illustrate the effectiveness of using channel state. It is shown that through the use of channel state, with arbitrarily small power, it is possible to achieve an AST that is lower-bounded by the spreading gain of the network. This result has implications for the reachback problem in large sensor networks.

We study the stability and capacity problems in regular wireless networks. In the first part of the paper, we provide a general approach to characterizing the capacity region of arbitrary networks, find an outer bound to the capacity region in terms of the transport capacity, and discuss connections between the capacity formulation and the stability of node buffers. In the second part of the paper, we obtain closed-form expressions for the capacity of Manhattan (two-dimensional grid) and ring networks (circular array of nodes). We also find the optimal (i.e., capacity-achieving) medium access and routing policies. Our objective in analyzing regular networks is to provide insights and design guidelines for general networks. The knowledge of the exact capacity enables us to quantify the loss incurred by suboptimal protocols such as slotted ALOHA medium access and random-walk-based routing. Optimal connectivity and the effects of link fading on network capacity are also investigated.

The effect of multipacket reception (MPR) on stability and delay of slotted ALOHA based random-access systems is considered. A general asymmetric MPR model is introduced and the medium-access control (MAC) capacity region is specified. An explicit characterization of the ALOHA stability region for the two-user system is given. It is shown that the stability region undergoes a phase transition from a concave region to a convex polyhedral region as the MPR capability improves. It is also shown that after this phase transition, slotted ALOHA is optimal i.e., the ALOHA stability region coincides with the MAC capacity region. Further, it is observed that there is no need for transmission control when ALOHA is optimal i.e., ALOHA with transmission probability one is optimal. Next, these results are extended to a symmetric N>2 user ALOHA system. Finally, a complete characterization of average delay in capture channels for the two-user system is given. It is shown that in certain capture scenarios, ALOHA with transmission probability one is delay optimal for all stable arrival rates. Further, it is also shown that ALOHA with transmission probability one is optimal for stability and delay simultaneously in the two-user capture channel.

The communication capacity of Cooperative SEnsor Networks with Mobile Access (C-SENMA) is considered when some sensors may be misinformed with erroneous messages. It is assumed that a global message is first distributed to all the nodes, each node receiving the message correctly with probability 1-/spl beta/. The nodes cooperate in delivering the global message to the mobile access point. Three system configurations are discussed based on whether a polling channel and/or an energy constraint are present. The first type is C-SENMA with Polling with No Energy constraints (PNE), where the mobile access point has the ability to poll individual sensors. Without energy constraints, each sensor can transmit for an unlimited number of times. The second type is C-SENMA with No Polling with No Energy constraints (NPNE), where adaptive polling is not allowed and sensors have to transmit according to a predetermined schedule. The third type is C-SENMA with No Polling with an Energy constraint (NPE), where each node has a limit on the number of transmissions. The capacities of the three system configurations are analyzed. It is shown that, the capacity for C-SENMA PNE is the same as that when there are no misinformed sensors. For C-SENMA NPNE, with the absence of the polling channel, there is a loss on the achievable rate, proportional to /spl beta/, the probability that a sensor is misinformed. Results are extended to multiple simultaneous transmissions with the presence of channel fading. The optimal number of simultaneous transmissions is investigated under three different fading situations.

The problem of placing known symbols in a data stream for a slowly varying frequency-selective channel is considered from an information-theoretic perspective. Given the amount of redundancy associated with known symbols, placement schemes that minimize the outage probability are derived by assuming that the transmitted codewords consist of packets that are constrained to have the same known symbol placement. Under the assumption that each known symbol cluster is at least as large as /spl alpha/ /spl ges/ 2L + 1 (where L is the channel order), we show that the optimal placement is obtained by arranging the known symbols into as many clusters as possible and placing them such that the unknown symbol blocks are as equal as possible. It is shown that the optimal placement of known symbol clusters does not depend on the probability density of the channel. Numerical examples are used to illustrate the ideas and potential gains of using optimal known symbol placement.

Communication from a cooperative sensor network to a mobile access point is considered in this paper. Sensors are assumed to be informed with a global message and some nodes are misinformed with random messages. The multiple access channel is i.i.d. fading and the realization of the channel state is known to the access point only. An achievable rate is derived for the information retrieval process when multiple sensors are activated at a time. For a Gaussian multiple access channel under a total network power constraint, the optimal number of simultaneous transmissions is investigated under three fading scenarios: non-fading, unit-gain, and Rayleigh-fading. With Gaussian code books, the optimal number of simultaneous transmissions varies in the three fading environments.

We have proposed an estimator for the number of operating sensors in a wireless sensor network based on the Good-Turing non-parametric estimator of the missing mass (Budianu and Tong, Proc. Asilomar Conf. on Sig., Systems and Computers, 2003). We now investigate the performance of this estimator using the theory of large deviations. We determine the asymptotic behavior of the large deviations exponent as the ratio n/N between the number of collected samples n and the number of operating sensors N decreases to zero. The simulations reveal that the confidence intervals obtained using the large deviations formula are upper bounds for the actual performance of the estimator. Together with the asymptotic behavior of the exponent, this suggests the surprising fact that if the scaling law n=f(N) is used for the number of samples, then reliable estimation can be done if n grows at least as fast as /spl radic/N. Separately, it is shown that, if lim/sub N/spl rarr//spl infin//(n//spl radic/N)=0, the estimator cannot be used.

We investigate the impact of medium access control (MAC) design on the reconstruction performance of a 1D random signal field measured by a large scale sensor network. Assuming the sensor density goes to infinity, we show that MAC design affects the decay rate of reconstruction distortion, and thus the efficiency of reconstruction, as the number of received packets M increases. Using a deterministic MAC with uniform spatial sampling, i.e., scheduling sensor transmissions from uniformly spaced locations, results in a faster decay rate of distortion than that using an ALOHA-like random access MAC. In particular, the ratio of the excess reconstruction distortion under random access MACs to that under the MAC with uniform sampling grows as log M+O(log log M). We further show that in the high measurement SNR regime, the benefit from carefully scheduling transmission, instead of random access, is substantial. In the low SNR regime, however, using random access MACs results in little reconstruction performance loss.

We consider the problem of optimal allocation of resources between training and data for transmission over a Gauss-Markov fading channel. Inaccurate channel state information (CSI) is available at the receiver through periodic training. There is no feedback, so that CSI is not available at the transmitter. We study MMSE estimators that predict the current channel state based on: all past pilot observations; only the most recent pilot observation; and the most recent and next in the future pilot observations. We analyze the optimal training energy and periodicity for each of these estimators. We show that optimizing the energy and periodicity of training results in significant energy savings over a sensible, but unoptimized, approach, particularly for rapidly varying channels.

We consider distributed detection with a large number of identical sensors deployed over a region where the phenomenon of interest (POI) has unknown spatially varying strength. Each sensor makes a decision based on its own measurement of the signal at its location and the local decision of each sensor is sent to a fusion center through a multiple access channel. The fusion center decides whether the POI has occurred in the region, under a global size constraint in the Neyman-Pearson formulation. Assuming that the initial distribution of sensors is a homogeneous spatial Poisson process, we show that the Poisson process of 'alarmed' sensors satisfies the locally asymptotic normality (LAN) condition as the number of sensor goes to infinity. We derive a new asymptotically locally most powerful (ALMP) detector jointly over the fusion scheme and the sensor threshold. We also derive the conditions on the spatial signal shape to guarantee the existence of the ALMP detector. We show that the optimal test statistic is a weighted sum of local decisions, the optimal weight function being the shape of the spatial signal, but the exact value of the spatial signal is not required. The optimal threshold for a single sensor is also derived. For the case of independent, identically-distributed (i.i.d.) sensor observation, we show that the counting-based detector is also asymptotic locally optimal.

We consider protocol design for extracting information from sensors by a mobile access point. Energy efficiency, defined as the expected number of bits reliably received for each unit of energy consumed, is used as the performance measure. A distributed opportunistic information retrieval protocol which exploits channel state information (CSI) is proposed. Referred to as the CSI-based carrier sensing, this protocol encodes the channel state into the backoff strategy of carrier sensing. When the propagation delay is negligible, CSI-based carrier sensing achieves the highest energy efficiency of the opportunistic strategy. For significant propagation, we construct the backoff function which maps the channel state to backoff time to minimize the performance loss. The CSI-based carrier sensing with the constructed backoff strategy is shown to be robust to propagation delay.

We consider the distributed detection problem with a large number if identical sensors deployed over a region where the phenomenon of interest (POI) has different signal strength depending on the location. Each sensor makes a decision based on its own measurement of the spatially varying signal and the local decision of each sensor is sent to a fusion center through a multiple access channel. The fusion center decides whether the POI has occurred in the region, under a global size constraint in the Neyman-Pearson formulation. Assuming that the initial distribution of sensors is a homogeneous spatial Poisson process, we show that the Poisson process of 'alarmed' sensors satisfies the locally asymptotic normality (LAN) condition as the number of sensor goes to infinity and derive a new asymptotically locally most powerful detector for the spatially varying signal. We show that (1) an optimal test statistic is a weighted sum of local decisions, (2) the optimal weight function is the shape of the spatial signal, and (3) the exact value of the spatial signal is not required. For the case of independent, identical distributed (i.i.d.) sensor observation, we show that the counting-based detector is also asymptotic locally optimal.

The effect of medium access control (MAC) for information retrieval on signal field reconstruction in large-scale sensor networks with finite density is analyzed. Two MAC schemes are compared: the deterministic scheduling and random access. For fixed sensor density, we show that there is a critical threshold of e/sup -/spl lambda/(1+o(1))/, where /spl lambda/ is the throughput of the random access protocol, on the sensor outage probability P/sub out/ beyond which the reconstruction performance of deterministic central scheduling is inferior to that of distributed random access.

This paper presents a temporally correlated single user Rayleigh flat-fading channels with imperfect receiver CSI. A cutoff rate analysis is used to determine the partial CSI of the receiver

We consider random access and coding schemes for sensor networks with mobile access (SENMA). Using an orthogonal code-division multiple access (CDMA) as the physical layer, an opportunistic ALOHA (O-ALOHA) protocol that utilizes channel state information is proposed. Under the packet capture model and using the asymptotic throughput as the performance metric, we show that O-ALOHA approaches the throughput equal to the spreading gain with an arbitrarily small power at each sensor. This result implies that O-ALOHA is close to the optimal centralized scheduling scheme for the orthogonal CDMA networks. When side information such as location is available, the transmission control is modified to incorporate either the distribution or the actual realization of the side information. Convergence of the throughput with respect to the size of the network is analyzed. For networks allowing sensor collaborations, we combine coding with random access by proposing two coded random access schemes: spreading code dependent and independent transmissions. In the low rate regime, the spreading code independent transmission has a larger random coding exponent (therefore, faster decay of error probability) than that of the spreading code dependent transmission. On the other hand, the spreading code dependent transmission gives higher achievable rate.

A dynamic medium access control (MAC) protocol is proposed for a finite-user slotted channel with multipacket reception (MPR). This protocol divides the time axis into transmission periods (TPs) where the ith TP is dedicated to the transmission of the packets generated in the (i-1)th TP. At the beginning of each TP, the state (active or idle) of each user is estimated based on the length of the previous TP and the incoming traffic load. By exploiting the information on the state of users and the channel MPR capability, the number of users who can simultaneously access the channel in the current TP is chosen so that the expected length of this TP is minimized. As a result, the MPR capability is more efficiently utilized by the proposed protocol as compared to, for example, the slotted ALOHA with optimal retransmission probability. Furthermore, the proposed protocol requires little online computation. Its simplicity is comparable to that of slotted ALOHA. It can be applied to random access networks with spread spectrum and/or antenna array.

Long-code wideband CDMA receivers are for computational reasons usually based on simple matched-filter techniques, and hence suffer from multiaccess interference. To mitigate this problem, we propose computationally efficient decorrelating RAKE and MMSE receivers for the uplink of long-code CDMA systems. The decorrelating matched filter eliminates multiaccess interference by code matrix inversion. Channel parameters and data symbols are then estimated jointly via rank-one decompositions. The feasibility of the proposed schemes hinges upon their efficient implementation in terms of time-varying state space realizations, with a complexity comparable to that of the conventional RAKE receiver.

We consider the problem of stability of slotted ALOHA for a system consisting of N users communicating with a common receiver, which employs spatial diversity to receive multiple transmissions simultaneously. We introduce a general packet reception model to incorporate multiple packet receptions since the collision channel model is no longer valid in such a scenario. We characterize the stability region of slotted ALOHA for the two user case explicitly. We also provide a sufficient condition for stability of slotted ALOHA for the N > 2 case, Finally, we apply our results to a simple system in which two users communicate with a base station equipped with a linear antenna array. Using stability region as a performance measure, we compare four different receivers/beamformers viz. matched filter, zero forcing, pseudo-MMSE and true MMSE employed by the base station to receive information from the users.

A new semiblind channel estimation technique is proposed for space-time coded wideband CDMA systems using aperiodic and possibly multirate spreading codes. Using a decorrelating matched filter, the received signal is projected onto subspaces from which channel parameters and data symbols can be estimated jointly. Exploiting the subspace structure of the WCDMA signaling and the orthogonality of the space-time code, the proposed algorithm provides the least squares channel estimate in closed form. A new identifiability condition is established. The mean square error of the estimated channel is compared with the Cramer-Rao bound, and a bit error rate (BER) expression for the proposed algorithm is compared with differential schemes.

An adaptive medium-access control (MAC) protocol for heterogeneous networks with finite populations is proposed. Referred to as the multiqueue service room (MQSR) protocol, this scheme is capable of handling users with different quality-of-service (QoS) constraints. By exploiting the multipacket reception (MPR) capability, the MQSR protocol adaptively grants access to the MPR channel to a number of users such that the expected number of successfully received packets is maximized in each slot. The optimal access protocol avoids unnecessary empty slots for light traffic and excessive collisions for heavy traffic. It has superior throughput and delay performance as compared to, for example, the slotted ALOHA with optimal retransmission probability. This protocol can be applied to random-access networks with multimedia traffic.

The time domain synchronous orthogonal frequency division multiplex (TDS-OFDM) modulation scheme has recently been proposed in a new digital television (DTV) system. The European DTV standard DVB-T, on the other hand, uses the cyclic prefix (CP) OFDM modulation. In this paper, TDS-OFDM and CP-OFDM for nonergodic broadcast inter-symbol-interference channels are compared from an information theoretical perspective. The outage probability expressions are derived for both schemes and evaluated numerically under various system configurations and channel distributions.

The problem of training symbol placement in data packets for channel tracking is considered, where the channel is time-varying Rayleigh flat fading. We use the minimum mean-square error (MMSE) estimator for channel tracking. A minmax approach is considered. We optimize the placement by minimizing the maximum MSE over a packet. It is shown that training symbols should be scattered throughout the packet with equal space to achieve the optimal performance.

The third generation (3G) wireless systems such as Wideband CDMA(WCDMA) employ coherent detection where pilot symbols for channel estimation are transmitted simultaneously with data using orthogonal channelization codes. The orthogonality of codes, unfortunately, is lost easily due to multipath delays. Furthermore, the use of long scrambling code introduces time variation in channel model. In this paper, based on the projection of time-varying subspaces, we present a semi-blind channel estimation technique for long code CDMA systems that use code division multiplexed pilot symbols.

We consider an asynchronous ad-hoc network with multiple users transmitting packets at the same time. The signal of interest is modulated by a known amplitude variation. This allows the corresponding multichannel receiver to estimate the beam former weights that will suppress the interfering sources. We introduce “known modulus algorithms” (KMAs) to achieve this, and illustrate the, throughput improvements that can be expected.

The problem of placing training symbols optimally for orthogonal frequency-division multiplexing (OFDM) and single-carrier systems is considered. The channel is assumed to be quasi-static with a finite impulse response of length (L + 1) samples. Under the assumptions that neither the transmitter nor the receiver knows the channel, and that the receiver forms a minimum mean square error (MMSE) channel estimate based on training symbols only, training is optimized by maximizing a tight lower bound on the ergodic training-based independent and identically distributed (i.i.d.) capacity. For OFDM systems, it is shown that the lower bound is maximized by placing the known symbols periodically in frequency. For single-carrier systems, under the assumption that the training symbols are placed in clusters of length /spl alpha/ /spl ges/ (2L + 1), it is shown that the lower bound is maximized by a family of placement schemes called QPP-/spl alpha/, where QPP stands for quasi-periodic placement. These placement schemes are formed by grouping the known symbols into as many clusters as possible and then placing these clusters periodically in the packet. For both OFDM and single-carrier systems, the optimum energy tradeoff between training and data is also obtained.

A performance comparison is presented between two types of code-division multiple-access wireless local area networks: centrally controlled and ad hoc networks. Based on a finite-population model, the network throughput, the average packet delay, and the network first exit time are derived for both systems. Two aspects of the performance comparison are addressed: (1) the comparison between the centrally controlled and the ad hoc architecture; and (2) the impact of spreading gain and error control coding on both systems. The efficiency of bandwidth utilization is investigated by normalizing the network performance with respect to the consumed bandwidth. Evaluations of these performance comparisons are also provided.

The problem of placing known symbols optimally for OFDM is considered. The channel is assumed to be quasi-static with a finite impulse response. Under the assumption that neither the transmitter and receiver know the channel, we optimize the training by maximizing a lower bound of the mutual information. It is shown that the lower bound is maximized by placing the known symbols periodically. Optimum energy trade-off between the training and the data is also obtained and illustrated through simulation.

The problem of design and placing pilot symbols for the estimation of frequency selective random channels is considered. For both SISO and MIMO channels, the Cramer-Rao bound (CRB) on the mean square error of channel estimators is derived and minimized with respect to the pilot symbols and their placement. It is shown that placing pilot symbols, possibly in multiple clusters, in the middle of the data packet leads to minimum CRB.

Space-time coding is an efficient technique to exploit transmitting and receiving diversities for wireless channels. One of the key components in the design of receivers for space-time codes is channel estimation. For the block codes based on orthogonal design proposed by Alamouti and Tarokh (see IEEE Trans. on Information Theory, vol45, no.5, p.1456-67, 1999), a new class of pilot assisted channel estimation schemes are presented where pilot symbols are superimposed on the data symbols. Placement strategies are examined for their efficiency in channel estimation and data transmission.

The estimation of signal parameters via rotational invariance technique (ESPRIT) algorithm has proved to be a robust solution to exploit single invariance structure in array elements. However, ESPRIT is not flexible to incorporate multiple invariances. A closed form solution to the problem of estimating eigenvalues in multiple invariant structures is presented in this paper. It is shown that the algorithm is comparable in complexity to ESPRIT but performs better than ESPRIT, especially when only a limited number of signal samples are available. In addition, the algorithm is shown to be feasible even for single array elements sharing multiple invariance.

A performance comparison is presented between two types of CDMA random access systems: cellular and ad hoc. Based on a finite population model, the network throughput is derived for both systems. Two aspects of the performance comparison are addressed: (1) the throughput comparison; and (2) the impact of spreading gain and error control coding on the throughput in both systems. Evaluations of these performance comparisons are also provided.

The detection of a data sequence with embedded known symbols is considered. For a class of symbol-by-symbol decision feedback receivers, known symbol distributions optimal with respect to the criterion of average mean square error (A-MSE) are presented. Optimal design of the decision feedback receiver is also obtained. Simulation results show that, compared to the performance with conventional symbol placement strategy, considerable gain can be obtained by the joint optimization of symbol placement and equalizer.

Traffic burstiness results in the predictability of user activity at the individual source level, and the exploitation of such predictability in the receiver design for wireless packet switching random access/CDMA networks is investigated. It is shown that the conventional approach of assuming all users are active results in substantial performance loss when a linear multiuser detector, and in particular, a decorrelating detector is implemented. A two-stage receiver is proposed where the first stage tracks active users and prior to the second stage symbol detection. Two different user trackers are presented and it is demonstrated that, with the help of traffic predictability, accurate estimate of active set of users is possible, even with a simple matched filter bank implementation at the first stage.

The problem of channel estimation for a frequency hopping system is considered. Under a discrete multipath fading model, the path gains and delays are estimated separately. By exploiting fixed (but unknown) patterns in the data packet, the delay estimation problem is formulated in an ESPRIT-like format by identifying multiple rotational invariance structures in the received data. Since ESPRIT is limited to exploitation of single invariance, the previously proposed SPECC algorithm is employed for the multipath delay estimation. Performance results based on simulations are presented.

We study the equalization problem in time division multiple access wireless asynchronous transfer mode (ATM) systems. Aiming at minimizing the overhead associated with equalization, we propose a protocol-aided channel equalization (PACE) approach for wireless ATM. Specifically, the medium access control (MAC) and data link control (DLC) protocols are exploited to provide known ATM cell headers to the receiver at the base station. A blind channel estimation-decision feedback equalizer (BCE-DFE) algorithm is developed for uplink data transmissions. There are two advantages of the BCE-DFE algorithm: the elimination of training symbols for uplink data bursts and the removal of channel estimation error propagation suffered by conventional block equalization schemes. Simulation results show the BCE-DFE has a robust performance for wireless ATM uplink data transmissions over fast time-varying channels.

The vector-constant modulus (VCM) criterion is an extension of the constant modulus (CM) criterion introduced recently for equalization of channels involving Gaussian sources. In this letter, we analyze the behavior of VCM for arbitrary source distributions and combined channel-receiver impulse responses of finite dimension. We begin by pointing out the difference between the VCM and CM cost functions and showing that the VCM criterion can be expressed as a composite criterion combining the CM cost function and a penalty term involving cross-correlations of the equalizer output. We continue by providing conditions for noise-free channels, under which VCM admits stable minima corresponding to zero-forcing (ZF) channel receivers. We find that for sub-Gaussian sources, the VCM and CM criteria share the same global minima. For Gaussian and super-Gaussian sources, however, it appears that only ZF receivers corresponding to input/output transmission delays at the extremes of the range of possible delays are truly stable equilibria of VCM.

An adaptive reinitialization algorithm for the constant modulus algorithm is proposed that relies on the similarities between the constant modulus and the Wiener equalizer and expands the capabilities of a previous algorithm. The proposed algorithm determines adaptively if the CMA will benefit through reinitialization, and if so, it will calculate new equalizer coefficients leading to the global minimum.

In this paper we present a method for the deterministic blind identification of single-input multiple-output systems with unknown model order. The technique, that is applicable to both the FIR and IIR cases, requires only an upper bound of the model order. It is based on the special kernel structure of block Toeplitz matrices. When the model order is overestimated, this special structure entails the true solution to be embedded in the overestimated solution in a unique shift-chain form. This special shift-chain structure is then utilized to extract the true solution.

A decision feedback blind symbol estimation algorithm based on the least squares smoothing approach is proposed for single-input multiple-output finite impulse response systems. With the finite alphabet property, the input signal is estimated based on the past detected symbols and the least squares smoothing error of the observation. Implemented both time and order recursively, the proposed algorithm is adaptive to channel variation and has low complexity both in computation and in VLSI implementation. Based on a deterministic model, this algorithm has the finite sample convergence property, i.e., the input signal can be perfectly detected with a small set of data samples in the absence of noise.

In an OFDM system for wireless communications, a guard interval longer than the channel delay is used to avoid interchannel interference (ICI) and intersymbol interference (ISI), so the multiplexed subchannels can be decoupled by the discrete Fourier transform (DFT). However, this ICI- and ISI-free OFDM system reduces the efficiency of bandwidth usage and prevents the use of sufficient statistics in channel equalization. We consider an OFDM system that achieves one hundred percent efficiency of bandwidth usage and uses sufficient statistic. A one-tap decision feedback equalizer (DFE) is proposed. It is demonstrated that though occupying a narrower bandwidth, the one-tap DFE based, ICI and ISI OFDM system achieves a lower symbol error rate and higher mutual information between the input of the decision device and transmitted symbols.

The constant modulus (CM) cost function is analyzed for array signal processing. The analysis includes arbitrary source types. It is shown that CM receivers have the signal space property except in two special cases. Local minima of CM cost function are completely characterized for the noiseless case. In the presence of measurement noise, the existence of CM local minima in the neighborhood of Wiener receivers is established, and their mean squared error (MSE) performance, output power, estimation bias and residual interference are evaluated. Numerical examples are presented to demonstrate the effects of signal statistics on the locations of CM local minima. Für die Arraysignalverarbeitung wird die Kostenfunktion des konstanten Betrages (CM) untersucht. Die Analyse schließt beliebige Quellentypen ein. Es wird gezeigt, daß CM-Empfänger mit Ausnahme von zwei Spezialfällen die Signalraumeigenschaft besitzen. Lokale Minima der CM-Kostenfunktion werden im rauschfreien Fall vollständig charakterisiert. Liegt Meßrauschen vor, dann wird die Existenz der lokalen Minima in der Nähe von Wiener-Empfängern gezeigt, und ihr mittlerer quadratischer Fehler (MSE), die Ausgangsleistung, der Schätzoffset und die Reststörung werden berechnet. Numerische Beispiele werden präsentiert, um die Effekte der Signalstatistik auf die Lage der lokalen Minima bei CM zu zeigen. On analyse la fonction coût Module Constant (CM) pour le traitement d’antenne. L’analyse prend en compte des sources de type arbitraire. On montre que les récepteurs CM jouissent de la propriété dite de l’espace signal sauf dans deux cas particuliers. Les minima locaux de cette fonction coût CM sont complètement caractérisés en l’absence de bruit. En présence de bruit de mesure, l’existence de minima locaux au voisinage des récepteurs de Wiener est établie, et leurs performances en termes d’Erreur Quadratique Moyenne (MSE), de puissance de sortie, de biais, et d’interférence résiduelle sont évaluées. Des exemples numériques sont présentés pour illustrer les effets des statistiques des signaux sur les positions des minima locaux CM.

We investigated the feasibility of applying blind equalization to wireless ATM networks. Making use of the information exploited from the wireless ATM cell structure and medium access control (MAC), blind channel estimation together with a non-linear data directed estimator achieve good equalization performance without transmitting extra preamble. Simulation results are presented for ATM constant bit rate (CBR) and available bit rate (ABR) traffic.

A linear least squares smoothing approach is proposed for the blind channel estimation. It is shown that the single-input multiple-output moving average process has the property that the error sequence of the least squares smoother, under certain conditions, uniquely determines the channel impulse response. The relationship among the dimension of the observation space, channel order and smoothing delay is presented. A new algorithm for channel estimation based on the least squares smoothing is developed. The proposed approach has the finite-sample convergence property in the absence of the channel noise. It also has a structure suitable for recursive implementations.

A review of blind channel estimation algorithms is presented. From the (second-order) moment-based methods to the maximum likelihood approaches, under both statistical and deterministic signal models. We outline basic ideas behind several new developments, the assumptions and identifiability conditions required by these approaches, and the algorithm characteristics and their performance. This review serves as an introductory reference for this currently active research area.

The Godard (1980) or the constant modulus algorithm (CMA) is an effective technique for blind receiver design in communications. However, due to the complexity of the constant modulus (CM) cost function, the performance of the CM receivers has primarily been evaluated using simulations. Theoretical analysis is typically based on either the noiseless case or approximations of the cost function. The following question, while resolvable numerically for a specific example, remains unanswered in a generic manner. In the presence of channel noise, where are the CM local minima and what are their mean-squared errors (MSE)? In this paper, a geometrical approach is presented that relates the CM to Wiener (or minimum MSE) receivers. Given the MSE and the intersymbol/user interference of a Wiener receiver, a sufficient condition is given for the existence of a CM local minimum in the neighborhood of the Wiener receiver. The MSE bounds on CM receiver performance are derived and shown to be tight in simulations. The analysis shows that, while in some cases the CM receiver performs almost as well as the (nonblind) Wiener receiver, it is also possible that, due to its blind nature, the CM receiver may perform considerably worse than a (nonblind) Wiener receiver.

The noise predictive structure of DFE is attractive for the equalization of the coded modulation signals. In this paper, a blind predictive constant modulus (CM) decision feedback equalizer (PCM-DFE) is presented and analysed. The PCM-DFE employs the CM linear equalizer as its forward filter and a feedback filter that optimizes the CM cost of the decision variable. It is shown that for any fixed forward filter with reasonable small residue intersymbol interference, the CM cost function for the feedback filter is approximately convex and its global minimum can be approximated in closed form. We demonstrate that the convergence rate of the feedback filter is similar to the least mean square (LMS) algorithm used in the nonblind design. We show that the PCM-DFE performs better than the nonblind linear MMSE equalizer in simulations.

The constant modulus algorithm (CMA) is an effective technique for blind receiver design in practice. Treating CMA as a linear estimation problem, effects of noise and channel conditions are investigated. For the class of channels with arbitrary finite impulse responses, an analytical description of locations of constant modulus receivers and an upper bound of their mean squared errors (MSE) are derived. We show that, with proper initializations, CMA can achieve almost the same performance as the (nonblind) minimum mean square error (MMSE) receiver. Our analysis reveals a strong relationship between the (blind) constant modulus and the (nonblind) MMSE receivers. It also highlights the significance of initialization/reinitialization schemes. The approach developed in this paper also applies to CMA blind beamforming in array signal processing.

The proper initialization of the constant modulus algorithm (CMA) is a critical problem that has not been solved. This paper presents a new reinitialization scheme for CMA. The proposed scheme searches in the channel space for the constant modulus equalizer with minimum mean-square error by exploiting the structure of the minimum mean square error (MMSE) equalizer and connections between the constant modulus and the MMSE equalizers.

The identification of multichannel moving average (MA) parameter matrices {H(k)} using fourth-order output cumulants is considered. By analysing the eigenstructures of the cumulant matrices, it is shown that the MA parameter matrices can be identified uniquely up to a post multiplication of monomial matrices if H(0) does not have columns that are pairwise colinear and H=[H/sup t/(0),...,H/sup t/(L)]/sup t/ has full column rank. The constructive proof of this condition leads to a closed-form identification algorithm.

Equalization based on blind channel estimation using the second-order statistics has a rapid convergence rate and is potentially attractive in digital wireless communications. The asymptotic behavior of this type of approach is investigated. In particular, the achievable lower bounds of the asymptotic mean-square error (MSE) are derived to serve as benchmarks for a class of blind equalization algorithms using second-order statistics. It is shown that the convergence rate of these equalizers suffers when channels are ill-conditioned. Applying this analysis to systems using antenna arrays, the performance gain of multiple receivers over single receiver is evaluated analytically.

A number of papers have studied blind channel identification/equalization algorithms relying purely on second-order statistics of the fractionally sampled received signal. A class of cyclic allpass channels is shown to be the only class of IIR channels whose cascade with a core channel results in no change in the second-order-statistics indicators used by several of these algorithms. FIR approximations to the poles of these allpass channels result in robustness concerns for the second-order-statistics algorithms, even when FIR identifiability conditions are well satisfied. This sensitivity suggests that excluding only those channels with common subchannel roots is insufficient when applying these second-order-statistics algorithms.

A scheme of joint blind signal detection and carrier recovery is developed for intersymbol interference channels. Using a blind sequence estimation scheme, the proposed approach does not require explicit channel identification. It shows robustness against timing error and carrier phase uncertainty. The efficacy of the proposed approach is demonstrated in a simulation involving frequency selective fast fading channel with substantial Doppler shifts.

Estimating the data sequence from the received signal without knowing the transmission channel is referred to as blind sequence estimation. A new blind sequence estimation scheme is proposed by exploiting the second order statistical properties of the source and the algebraic structure of the data sequence. An optimal source (deterministic) correlation estimator and the Viterbi algorithm are used to achieve blind sequence estimation. The proposed approach also has a special structure particularly attractive for time varying channels.

In this communication, necessary and sufficient conditions are presented for the unique blind identification of possibly nonminimum phase channels driven by cyclostationary processes. Using a frequency domain formulation, it is first shown that a channel can be identified by the second-order statistics of the observation if and only if the channel transfer function does not have special uniformly spaced zeros. This condition leads to several necessary and sufficient conditions on the observation spectra and the channel impulse response. Based on the frequency-domain formulation, a new identification algorithm is proposed.>

Conventional blind channel identification algorithms are based on channel outputs and the knowledge of the probabilistic model of a channel input. In some practical applications, however, the input statistical model may not be known, or there may not be sufficient data to obtain accurate enough estimates of certain statistics. We consider the system input to be an unknown deterministic signal and study the problem of blind identification of a channel which can be decomposed into multichannel FIR systems driven by a input signal. A new deterministic blind identification algorithm based solely on the system outputs are proposed. Necessary and sufficient identifiability conditions concerning the channel and the deterministic input signal are also presented.>

Tong et al. (see IEEE Trans. on Information Theory, March 1994) has proposed a parametric approach for blind equalization based solely on the second-order statistics. It first demonstrates the possibility of achieving satisfactory blind equalization by using a few hundred data samples in some typical wireless communication scenarios. Nevertheless, the algorithm is still far from optimal and is quite computationally intensive. In this paper, we use a different approach and derive a new algorithm which is less complicated as the original one. Simulation studies also show that some improvement of the new approach over its alternative in some scenarios.>

A new blind channel identification and equalization method is proposed that exploits the cyclostationarity of oversampled communication signals to achieve identification and equalization of possibly nonminimum phase (multipath) channels without using training signals. Unlike most adaptive blind equalization methods for which the convergence properties are often problematic, the channel estimation algorithm proposed here is asymptotically ex-set. Moreover, since it is based on second-order statistics, the new approach may achieve equalization with fewer symbols than most techniques based only on higher-order statistics. Simulations have demonstrated promising performance of the proposed algorithm for the blind equalization of a three-ray multipath channel.>

The problem of speech separation from an array of microphones is considered. The problem is modeled as a wideband process with unknown model parameters, namely, sensor gains and time delays. The technique of blind identification is extended to the wideband case. It is shown that the wideband blind identification approach is capable of handling multipath situations. Simulations are presented which show that the wideband signals can indeed be separated by the proposed approach.>

A closed-form solution to the parameter identification of multichannel moving average processes is presented. An eigenstructure-based approach is proposed to solve the identification equations involving output cumulants of any order by further exploiting the eigenstructure of the output cumulant matrices. The identification equations are derived without using the Kroneker products, hence greatly reducing the computational complexity. This approach is also computationally simpler than that of L. Tong et al. (1991), and iterations are avoided. In addition, the proposed approach allows one to combine the statistics of different order to achieve better performance. Computer simulation has shown that a much smaller sample size, on the order of 5000, is needed to achieve even better performance than our previous approach.>

An identifiability result for the blind identification of memoryless channels with independent sources is presented. The necessary and sufficient conditions which were obtained by investigating the eigenstructure inherited in the observation cumulants are given. An eigenstructure-based algorithm is proposed to achieve the identification of the parameter matrix whenever such identification is possible. It is shown that the source signals can be extracted up to scale factors and a permutation if and only if all the source signals, but one, are non-Gaussian.>

An iterative algorithm for the identification of multichannel moving average (MA) processes driven by mutually independent and identically distributed (i.i.d.) input signals is proposed. It is shown that the algorithm has a finite-step global convergence property. This algorithm is computationally efficient and numerically stable. Two multichannel MA models, including one nonminimum-phase MA model, are estimated by this algorithm with satisfactory performances. It is shown that this algorithm guarantees a solution of third-order cumulant-based identification equations.>

An eigenstructure-based method called extended fourth-order blind identification (EFOBI) is presented for the problem of blind decomposition of multiple source signals in spatially correlated noise. Estimates of the source signals and the unknown model parameters are computed by the algorithm. The method is applied to a speech enhancement problem and to the direction-of-arrival problem in array signal processing under sensor gain uncertainties and shows improved performance over traditional methods such as MUSIC.>