In this paper, we study the adversarial robustness of deep neural networks (DNN) for classification against optimal classifiers. We look at the smallest magnitude of possible additive perturbations that can change a classifier's output. We provide a matrix-theoretic explanation of the adversarial fragility of DNNs for classification. In particular, our theoretical results show that the adversarial robustness of a neural network can degrade as the input dimension d increases. Analytically, we show that the adversarial robustness of neural networks can be only 1/√d of the best possible adversarial robustness of optimal classifiers. Our theories match remarkably well with empirical results. The matrix-theoretic explanation aligns with an earlier information-theoretic feature-compression-based explanation for the adversarial fragility of neural networks.

The rapid spread of SARS-CoV-2 has placed a significant burden on public health systems to provide swift and accurate diagnostic testing highlighting the critical need for innovative testing approaches for future pandemics. In this study, we present a novel sample pooling procedure based on compressed sensing theory to accurately identify virally infected patients at high prevalence rates utilizing an innovative viral RNA extraction process to minimize sample dilution. At prevalence rates ranging from 0-14.3%, the number of tests required to identify the infection status of all patients was reduced by 69.26% as compared to conventional testing in primary human SARS-CoV-2 nasopharyngeal swabs and a coronavirus model system. Our method provided quantification of individual sample viral load within a pool as well as a binary positive-negative result. Additionally, our modified pooling and RNA extraction process minimized sample dilution which remained constant as pool sizes increased. Compressed sensing can be adapted to a wide variety of diagnostic testing applications to increase throughput for routine laboratory testing as well as a means to increase testing capacity to combat future pandemics.

We present a simple hypothesis about a compression property of artificial intelligence (AI) classifiers and present theoretical arguments to show that this hypothesis successfully accounts for the observed fragility of AI classifiers to small adversarial perturbations. We also propose a new method for detecting when small input perturbations cause classifier errors, and show theoretical guarantees for the performance of this detection method. We present experimental results with a voice recognition system to demonstrate this method. The ideas in this paper are motivated by a simple analogy between AI classifiers and the standard Shannon model of a communication system1.

We describe an experimental study of an mid-range resonant wireless power transfer (WPT) system with multiple transmit coils. While there exists substantial literature on WPT systems using coupled resonance as well as those using multi-coil transmitters, previous work has been limited to simple transmitter configurations with a small number of coils uncoupled with each other because of the difficulty of accurately tuning and optimizing such systems. Our key novelty is to use real-time receiver feedback to adaptively tune the system. This simple and powerful idea opens up the possibility of large-scale WPT systems with potentially large numbers of resonant transmitter coils that can adaptively transfer power to one or more receivers using realtime feedback. We describe a experimental study that shows the feasibility of this concept and its advantages over WPT systems without real-time feedback.

We consider the problem of optimal precoder design for a multi-input single-output wideband wireless system to maximize two different figures of merit: the total communication capacity and the total received power, subject to individual power constraints on each transmit element. We show that the two optimal precoders satisfy a separation principle that reveals a simple structure for these precoders. We use this separation principle extensively to derive several interesting properties of these two optimal precoders. Some key analytical results are as follows. We show that the power-maximizing precoders must concentrate all their energy in a small number of active channels that cannot exceed the number of input terminals. The capacity-maximizing precoder turns out to be very different from the classical water filling solutions and also very different from the power-maximizing precoders except at asymptotically low SNRs where the power-maximizing precoders also maximize capacity. We also show that the capacity of the wideband system is lower bounded by the sum rate of a multiple-access channel with the same channel gains and power constraints. Finally, the separation principle also yields simple fixed-point algorithms that allow for the efficient numerical computation of the two optimal precoders.

We consider distributed nullforming using an array of wireless transmitters that coordinate their transmissions to achieve destructive interference at a designated receiver. We describe the first experimental demonstration of distributed nullforming to a target receiver from an array of three distributed transmitters using (mostly) off-the-shelf hardware and simple and standard signal processing techniques. We are motivated by the goal of using distributed arrays to achieve increased spectrum reuse through interference cancellation. Our results show interference suppression in excess of 25dB over uncoordinated transmission. We build on our recent experimental demonstration of beamforming from a distributed antenna array after estimating and compensate for the combined effects of unknown propagation channels, hardware mismatches and clock drifts between the array nodes. The transmitters do not share clocks or have any wired back channels. They coordinate achieve nullforming entirely using in-band wireless message exchanges. Thus these methods can be implemented on portable mobile devices rather than being limited to Base Stations.

We consider the problem of multicasting a common message signal from a distributed array of wireless transceivers by beamforming to a set of beam targets, while simultaneously protecting a set of null targets by nullforming to them. We describe a distributed algorithm in which each transmitter iteratively adapts its complex transmit weight using common aggregate feedback messages broadcast by the targets, and the local knowledge of only its own channel gains to the targets. This knowledge can be obtained using reciprocity without any explicit feedback. The algorithm minimizes the mean square error between the complex signal amplitudes at the targets and their desired values. We prove convergence of the algorithm, present geometric interpretations, characterize initializations that lead to minimum total transmit power, and prescribe designs for such initializations. We show that the convergence speed is nondecreasing in the number of transmitters N if a step size parameter is kept constant. For Rayleigh fading channels, as N goes to infinity: 1) convergence can be made arbitrarily fast and 2) beams and nulls can be achieved with vanishing total transmit power even with noise, both with probability one. These results add up to some remarkable scalability properties: the feedback overhead does not grow with the number of transmitters, and with high probability, the algorithm can be configured to converge arbitrarily fast and use vanishingly small total transmit power.

We present an empirical performance evaluation of algorithms that replace arithmetic operations with low-level bit operations for power-aware Big Data processing. Specifically, we compare two different data structures in terms of both execution time and power efficiency: (a) a baseline design using arrays, and (b) a design using bit-slice indexing (BSI) and distributed BSI arithmetic. We evaluate two types of queries popular in Big Data analytics: aggregations and top-k. These queries were implemented using each of the two data structure designs on Apache Spark running on a server cluster that was instrumented with specialized hardware for synchronized real-time power measurement for each server in the cluster. We performed a series of experiments running the above queries on several different datasets. These experiments show that the bit-slicing algorithm consistently outperforms the array algorithm in both power efficiency and execution time. An interesting observation is that the power efficiency improvement of the bit-slicing algorithm over the array method is comparable to or greater than the improvement in execution time for both queries evaluated.

Most prior research in distributed beamforming involves narrowband, frequency nonselective, channels, with the goal of sending a common message from cooperating nodes so that phases of the signals transmitted from the different nodes align at the receiver. The performance metric is the received SNR (directly related to the Shannon capacity for an AWGN channel). This "coherence metric" is maximized when each transmitter compensates its channel phase to the receiver, while transmitting at maximum allowable power. In this paper, we consider the problem of distributed transmit beam-forming over broadband, frequency selective channels, defining the coherence metric as the Shannon capacity, to be maximized subject to a power constraint at each transmitter. OFDM provides a natural decomposition of such channels into narrowband subchannels, hence the problem reduces to determining how each transmitter allocates its power across subchannels. A key technical result is that the optimal solution obeys a separation property that significantly simplifies computation. We show that it differs from classical water-filling due to the per-transmitter power constraints of the distributed beamforming setting. We compare it both structurally and numerically, to a centralized beamforming system with power constraint across transmitters. This is like waterfilling and upper bounds the performance of our setup.

We provide a two-step approach to recover a jointly k-sparse matrix X, (at most k rows of X are nonzero), with rank r <; <; k from its under sampled measurements. Unlike the classical recovery algorithms that use the same measurement matrix for every column of X, the proposed algorithm comprises two stages, in each of which the measurement is taken by a different measurement matrix. The first stage uses a standard algorithm, [4] to recover any r columns (e.g. the first r) of X. The second uses a new set of measurements and the subspace estimate provided by these columns to recover the rest. We derive conditions on the second measurement matrix to guarantee perfect subspace aware recovery for two cases: First a worst-case setting that applies to all matrices. The second a generic case that works for almost all matrices. We demonstrate both theoretically and through simulations that when r <; <; k our approach needs far fewer measurements. It compares favorably with recent results using dense linear combinations, that do not use column-wise measurements.

We consider the problem of multicasting a common message signal to a set of designated receivers from a distributed antenna array, while simultaneously forming nulls to another set of null targets. We propose an algorithm under which each transmitter in the distributed array iteratively makes an incremental adjustment to its complex gain (which controls the amplitude and phase of its transmitted RF signal). The cumulative effect of these incremental adjustments is that the individual transmitted RF signals from the transmitters add up at the intended receivers to a desired SNR level, while simultaneously canceling each other perfectly at the null targets. A crucial feature of this algorithm is that it can be implemented in a purely distributed fashion at each transmitter using only an estimate of its own channel gain to each receiver, and an aggregate feedback signal from each of the receivers that is broadcast to all the transmitters. This is an important advantage of our approach and assures its scalability; in contrast any non-iterative approach to the beam/nullforming problem requires knowledge of all channel gains - from all transmitters to all receivers - to be available at every transmitter.

We consider the robust localization of radioactive sources by using their gamma-ray count at the smallest number of sensors needed to theoretically localize. We formulate a class of non-convex cost functions and consider their gradient descent optimization. We show that in N-dimensions, if there are exactly N + 1 sensors and the source lies in their open convex hull, then this convex hull is devoid of false stationary points. Thus we augment gradient descent with random projections into the convex hull, when an estimate leaves it. We argue that convergence in probability to the correct source location, will occur. Simulations demonstrate the efficacy of this algorithm.

We describe a fully-wireless prototype of distributed transmit beamforming on a software-defined radio platform. Distributed beamforming is a cooperative transmission technique that can achieve orders of magnitude increases in range or energy efficiency of wireless communication systems. However, this technique requires precise synchronization of the radio frequency signal from each transmitter. The significance of our prototype is in demonstrating that this requirement can be satisfied using digital signal processing methods on commodity hardware with low-quality oscillators. Our synchronization approach scales to large numbers of transmitters: each transmitter runs independent algorithms based on periodically transmitted feedback packets from the receiver. A key simplification is the decoupling of the algorithms for frequency locking and beamsteering at each transmitter, even though both processes use the same feedback packets. Frequency locking employs an Extended Kalman filter to track the local oscillator offset between a transmitter and the receiver, using frequency offset measurements based on the feedback packet it waveform, while the phase adjustments for beamsteering are determined using a one-bit feedback algorithm based on the feedback packet it payload. Our prototype demonstrates that distributed transmit beamforming can be incorporated into wireless networks without requiring hardware innovations, and provides open-source building blocks for future research and development.

We present an implementation of distributed transmit beamforming using software-defined radios. The transmit nodes synchronize in carrier frequency using a pilot signal sent by a master node, and employ feedback from the receiver to adjust their carrier phases so as to add up coherently at the receiver. Our implementation advances the state of the art for all-wireless distributed beamforming in two important ways. The first is the implementation of extended Kalman filters for frequency synchronization at the slave nodes, which is shown to be effective despite the high local oscillator (LO) offsets typical of software-defined radios, and the low duty cycle of the pilot transmitted by the master node. The second advance is the implementation of the well-known one bit feedback scheme for phase adjustment using digital feedback from the receiver. We present experimental results that show the efficacy of our implementation for frequency synchronization and beamforming.

In this paper, we propose an algorithm for timing synchronization that attains fundamental bounds derived by Weiss and Weinstein. These bounds state that, in addition to improving with time-bandwidth product and signal-to-noise ratio (SNR), timing accuracy also improves as the carrier frequency gets larger, if the SNR is above a threshold. Our algorithm essentially follows the logic of the Weiss-Weinstein bound, and has the following stages: coarse estimation using time domain samples, fine-grained estimation using a Newton algorithm in the frequency domain, and final refinement to within a small fraction of a carrier cycle. While the results here are of fundamental interest, we are motivated to push the limits of synchronization to enable the tight coordination required for emulating virtual antenna arrays using a collection of cooperating nodes.

Distributed beamforming requires phase and frequency synchronization. As oscillators drift, through Brownian motion induced phase noise, their instantaneous phases must be tracked and compensated. Several papers and IEEE 1588 have proposed Kalman Filter (KF) based tracking algorithms using the unwrapped phase measurements. This paper quantifies the effect of Brownian Motion induced drift at two levels. First we derive Cramer-Rao Lower Bounds (CRLB) manifest in one shot estimation of frequency and phase from unwrapped phase observations, and reveal fundamental and illuminating differences with the existing frequency and phase estimation CRLBs in the literature derived in the absence of Brownian motion. Second, we consider a KF that tracks the instantaneous phase in intervals where there is no beamforming, and is switched off during beamforming. Bounds are derived relating the error growth as a function of the underlying duty cycle.

We explore a class of techniques for distributed transmit beamforming where the beamforming target sends cumulative feedback that is broadcast to all of the beamforming nodes. The simplest technique in this class is a 1-bit RSS feedback algorithm that has been studied in detail in the literature. Under this 1-bit algorithm, transmitters make random phase perturbations and the receiver periodically sends 1 bit of feedback indicating whether the received signal strength has increased or not compared to what was observed in the past. While this simple algorithm has very attractive properties such as dynamic tracking of time-varying phases, robustness to noise and other disturbances and is also simple to implement, we show in this paper that it also has serious limitations such as slow convergence and poor tracking performance in the presence of frequency offsets between the transmitters. We then show that enhanced feedback algorithms where the receiver sends as feedback several bits of feedback indicating the amplitude and phase of the received signal over time, are able to achieve beamforming in the presence of frequency offsets and large feedback channel latencies, while retaining the scalability and robustness of the 1-bit algorithm.

In this paper, we describe our ongoing work on designing an underwater sensor network for monitoring the ecosystem of the Mississippi river using freshwater mussels as biological sensors.

We describe the key ideas behind our implementation of distributed beamforming on a GNU-radio based software-defined radio platform. Distributed beamforming is a cooperative transmission scheme whereby a number of nodes in a wireless network organize themselves into a virtual antenna array and focus their transmission in the direction of the intended receiver, potentially achieving orders of magnitude improvements in energy efficiency. This technique has been extensively studied over the past decade and its practical feasibility has been demonstrated in multiple experimental prototypes. Our contributions in the work reported in this paper are three-fold: (a) the first ever all-wireless implementation of distributed beamforming without any secondary wired channels for clock distribution or channel feedback, (b) a novel digital baseband approach to synchronization of high frequency RF signals that requires no hardware modifications, and (c) an implementation of distributed beamforming on a standard, open platform that allows easy reuse and extension. We describe the design of our system in detail, present some initial results and discuss future directions for this work.

We present a fully wireless implementation of distributed transmit beamforming using software-defined radios. Distributed beamforming is a cooperative transmission scheme whereby a number of nodes in a wireless network organize themselves into a virtual antenna array and focus their transmission in the direction of the intended receiver, potentially achieving order of magnitude improvements in energy efficiency. The main technical challenge in realizing these gains is in precisely synchronizing the radio frequency signals of the cooperating nodes. This idea has been studied extensively over the past decade, and several techniques and architectures for its practical implementation have been developed. In this work, we demonstrate our recent implementation of distributed beamforming on a standard, open-source, software-defined radio platform, where the low quality oscillators make synchronization particularly challenging. Our demonstration will consist of three cooperating transmitters sending signals that add up constructively at the receiver. Low-rate feedback packets broadcast from the receiver are employed for frequency and phase synchronization at each transmitter in completely distributed fashion.

We investigate spatial interference statistics for multigigabit outdoor mesh networks operating in the unlicensed 60-GHz “millimeter (mm) wave” band. The links in such networks are highly directional: Because of the small carrier wavelength (an order of magnitude smaller than those for existing cellular and wireless local area networks), narrow beams are essential for overcoming higher path loss and can be implemented using compact electronically steerable antenna arrays. Directionality drastically reduces interference, but it also leads to “deafness,” making implicit coordination using carrier sense infeasible. In this paper, we make a quantitative case for rethinking medium access control (MAC) design in such settings. Unlike existing MAC protocols for omnidirectional networks, where the focus is on interference management, we contend that MAC design for 60-GHz mesh networks can essentially ignore interference and must focus instead on the challenge of scheduling half-duplex transmissions with deaf neighbors. Our main contribution is an analytical framework for estimating the collision probability in such networks as a function of the antenna patterns and the density of simultaneously transmitting nodes. The numerical results from our interference analysis show that highly directional links can indeed be modeled as pseudowired, in that the collision probability is small even with a significant density of transmitters. Furthermore, simulation of a rudimentary directional slotted Aloha protocol shows that packet losses due to failed coordination are an order of magnitude higher than those due to collisions, confirming our analytical results and highlighting the need for more sophisticated coordination mechanisms.

Multi-gigabit outdoor mesh networks operating in the unlicensed 60 GHz "millimeter (mm) wave" band, offer the possibility of a quickly deployable broadband extension of the Internet. We consider mesh nodes with electronically steerable antenna arrays, with both the transmitter and receiver synthesizing narrow beams that compensate for the higher path loss at mm-wave frequencies, achieving ranges on the order of 100 meters using the relatively low transmit powers attainable with low-cost silicon implementations. Such highly directional networking differs from WiFi networks at lower carrier frequencies in two ways that have a crucial impact on protocol design: (1) directionality drastically reduces spatial interference, so that pseudowired link abstractions form an excellent basis for protocol design; (2) directionality induces deafness, which makes medium access control (MAC) based on carrier sensing infeasible. Interference analysis in our prior work shows that, in such a setting, coordination between transmitters and receivers, rather than interference management, becomes the key MAC performance bottleneck. However, the question of whether such coordination can be achieved in a distributed fashion while achieving high medium utilization, was left open. In this paper, we answer this question in the affirmative, presenting a distributed MAC protocol that employs memory to achieve approximate time division multiplexed (TDM) schedules without explicit coordination or resource allocation. The efficacy of the protocol is demonstrated via packet level simulations, while a Markov chain fixed-point analysis provides insight into the effect of parameter choices.

We consider the problem of secure wireless communication in the presence of an eavesdropper when the transmitter has multiple antennas, using a variation of the recently proposed artificial noise technique. Under this technique, the transmitter sends a pseudo-noise jamming signal to selectively degrade the link to the eavesdropper without affecting the desired receiver. The previous work in the literature focuses on ideal Gaussian signaling for both the desired signal and the noise signal. The main contribution of this paper is to show that the Gaussian signaling model has important limitations and propose an alternative “induced fading” jamming technique that takes some of these limitations into account. Specifically we show that under the Gaussian noise scheme, the eavesdropper is able to recover the desired signal with very low bit error rates when the transmitter is constrained to use constant envelope signaling. Furthermore, we show that an eavesdropper with multiple antennas is able to use simple, blind constant-envelope algorithms to completely remove the Gaussian artificial noise signal and thus defeat the secrecy scheme. We propose an alternative scheme that induces artificial fading in the channel to the eavesdropper, and show that it outperforms the Gaussian noise scheme in the sense of causing higher bit error rates at the eavesdropper and is also more resistant to constant modulus-type algorithms.

The concept of distributed transmit beamforming is implicit in many key results of network information theory. However, its implementation in a wireless network involves the fundamental challenge of ensuring phase coherence of the radio frequency signals from the different transmitters in the presence of unknown phase offsets between the transmitters and unknown channel gains from the transmitters to the receiver. In this paper, it is shown that such phase alignment can be achieved using distributed adaptation by the transmitters with minimal feedback from the receiver. Specifically, each transmitter independently makes a small random adjustment to its phase at each iteration, while the receiver broadcasts a single bit of feedback, indicating whether the signal-to-noise ratio (SNR) improved or worsened after the current iteration. The transmitters keep the ¿good¿ phase adjustments and discard the ¿bad¿ ones, thus implementing a distributed ascent algorithm. It is shown that, for a broad class of distributions for the random phase adjustments, this procedure leads to asymptotic phase coherence with probability one. A simple analytical model, borrowing ideas from statistical mechanics, is used to characterize the progress of the algorithm, and to provide guidance on parameter choices. This analytical model is based on a conjecture on the distribution of the received phases when the number of transmitters becomes large. Finally, the proposed system is shown to be scalable: the random phase perturbations can be chosen such that the convergence time is linear in the number of collaborating nodes.

Digital transmission of uncompressed high-definition video is challenging because of its high data rate and its extreme sensitivity to bit errors. In this paper we propose a simple error correction scheme to reduce the bit error effects in the video at the receiver end of a wireless channel. Our scheme uses the large amount of spatial redundancy already present in uncompressed HD video data to provide an extra layer of protection in addition to that provided by channel coding. Thus, our method requires no change to the video signal being transmitted and is compatible with any existing solution for HD video transmission. Using simulations over a range of byte error rates, we show that our scheme effectively reduces the number of visible artifacts because of uncorrected channel errors, and provides approximately 7 dB improvement in peak signal to noise ratio.

We investigate an architecture for multi-Gigabit outdoor mesh networks operating in the unlicensed 60 GHz "millimeter (mm) wave" band. In this band, the use of narrow beams is essential for attaining the required link ranges in order to overcome the higher path loss at mm wave carrier frequencies. However, highly directional links make standard MAC methods for interference management, such as carrier sense multiple access, which rely on neighboring nodes hearing each other, become inapplicable. In this paper, we study the extent to which we can reduce, or even dispense with, interference management, by exploiting the reduction in interference due to the narrow beamwidths and the oxygen absorption characteristic of the 60 GHz band. We provide a probabilistic analysis of the interference incurred due to uncoordinated transmissions, and show that, for the parameters considered, the links in the network can be thought of as pseudo-wired. That is, interference can essentially be ignored in MAC design, and the challenge is to schedule half-duplex transmissions in the face of the "deafness" resulting from highly directional links. We provide preliminary simulation results to validate our approach.

This paper presents a practical method for using multi-antenna radios to cancel interference in cognitive radio systems. Under this method, secondary radio transmitters use beamforming techniques to find antenna weights that place nulls at the primary receivers, and secondary radio receivers use adaptive techniques to decode in the presence of interference from primary users. As an example, we show how this scheme can be leveraged to effectively reuse the uplink band of a cellular network. However, estimating the channel responses, without causing interference and without requiring significant modifications to legacy systems, is a challenging problem. We provide an iterative method for accurate channel estimation in frequency division duplexed networks, where the uplink is independent of the downlink.

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits while providing minimal descriptions of the estimated target trajectory. Using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution in localizing a target's trajectory is of the order of 1/ρ R , where R is the sensing radius and ρ is the sensor density per unit area. We provide a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a “lowpass” approximation of the trajectory is attainable, and explore the implications of this observation for estimating the target's velocity. We also consider nonideal sensing, employing particle filters to average over noisy sensor observations, and geometric geometric postprocessing of the particle filter output to provide an economical piecewise linear description of the trajectory. In addition to simulation results validating our approaches for both idealized and nonideal sensing, we report on lab-scale experiments using motes with acoustic sensors.

We investigate the fundamental performance limits of target localization, where a network of sensors observe and cooperatively estimate the 2D location of a target. Taking a general view of a sensor as any device whose observations depend statistically on target position, we consider the binary hypothesis testing problem of choosing between the correct target location and an incorrect location at a distance r from it, given the outputs of all sensors in the network. By considering a random placement of sensors in an infinitely large sensing area, we obtain upper and lower bounds on the error probability of this hypothesis testing problem. The error bounds depend only on the type of sensor and are independent of the detailed geometry of the sensor network deployment. This provides a compact comparison of the localization performance of sensors whose characteristics might differ widely (e.g., received signal strength, proximity and time of arrival sensors). Also the bounds decrease exponentially with the density of sensors, and the rate of decrease is shown to have a simple geometric interpretation.

Energy efficient communication is a fundamental problem in wireless ad-hoc and sensor networks. In this paper, we explore the feasibility of a distributed beamforming approach to this problem, with a cluster of distributed transmitters emulating a centralized antenna array so as to transmit a common message signal coherently to a distant base station. The potential SNR gains from beamforming are well-known. However, realizing these gains requires synchronization of the individual carrier signals in phase and frequency. In this paper we show that a large fraction of the beamforming gains can be realised even with imperfect synchronization corresponding to phase errors with moderately large variance. We present a master-slave architecture where a designated master transmitter coordinates the synchronization of other (slave) transmitters for beamforming. We observe that the transmitters can achieve distributed beamforming with minimal coordination with the base station using channel reciprocity. Thus, inexpensive local coordination with a master transmitter makes the expensive communication with a distant base station receiver more efficient. However, the duplexing constraints of the wireless channel place a fundamental limitation on the achievable accuracy of synchronization. We present a stochastic analysis that demonstrates the robustness of beamforming gains with imperfect synchronization, and demonstrate a tradeoff between synchronization overhead and beamforming gains. We also present simulation results for the phase errors that validate the analysis

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits. In particular, using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution Δ in localizing a target's trajectory is of the order of 1overρ R, where R is the sensing radius and ρ is the sensor density per unit area. Using an Occam's razor approach, we then design a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a "lowpass" approximation of the trajectory is attainable, and explore the implications of this obervation for estimating the target's velocity.We show through simulation the effectiveness of the geometric algorithm in tracking both the trajectory and the velocity of the target for idealized models. For non-ideal sensors exhibiting sensing errors, the geometric algorithm can yield poor performance. We show that non-idealities can be handled well using a particle filter based approach, and that geometric post-processing of the output of the Particle Filter algorithm yields an economical path description as in the idealized setting. Finally, we report on our lab-scale experiments using motes with acoustic sensors to validate our theoretical and simulation results.

Recent work has shown that cross-layer optimization of the physical layer and medium access control for a wireless collision channel, based on a receiver with adaptive multiuser detection capability, is capable of providing significantly better performance than classical Aloha. The basic features of such a system are multipacket reception (MPR) capability, and the ability (with high probability) to estimate the number of contending users even when the packets are not successfully received. We provide an analytical model that includes these features, and use it to derive methods for backlog estimation and stabilization. Two classes of users are considered: high priority users with quality of service (QoS) requirements, who must succeed within a deadline with a specified probability; and low priority users whose throughput we wish to maximize, while maintaining the QoS for high priority users, and keeping the overall system stable. We obtain contention policies that ensure QoS and stability, based on backlog estimates obtained by extending Rivest's pseudo-Bayesian technique for classical Aloha. The channel throughput and the achievable QoS is characterized as a function of the arrival rates for high and low priority users. Finally, we apply these methods to simulations of a system employing differential minimum mean squared error (DMMSE) adaptive multiuser detection, and find that the analytical model provides accurate guidelines for design and performance predictions.

Recent work has shown that large gains in communication capacity are achievable by distributed beamforming in sensor networks. The principal challenge in realizing these gains in practice, is in synchronizing the carrier signal of individual sensors in such a way that they combine coherently at the intended receiver. In this paper, we provide a scalable mechanism for achieving phase synchronization in completely distributed fashion, based only on feedback regarding the power of the net received signal. Insight into the workings of the protocol is obtained from a simple theoretical model that provides accurate performance estimates

Energy efficient transfer of data from sensors is a fundamental problem in sensor networks. In this paper, we propose a distributed beamforming approach to this problem, with a cluster of sensors emulating a centralized antenna array. While it is well-known that beamforming can provide large performance gains, such gains presuppose not only accurate knowledge of the channel, but also time and phase synchronization at the transmitter. We propose explicit methods for achieving such synchronization in a distributed fashion, and analyze the effects of various sources of coordination error on the attained performance. We find that, as long as the error in range measurements or placement of the sensor nodes is within a fraction of a carrier wavelength, the proposed distributed beamforming strategies achieve most of the gains available from a centralized beamformer.