A significant part of human activity today consists of searching for pieces of information online, an endeavor that may be time-consuming if the individual searching for the information is unfamiliar with the subject matter. However, online social networks exist where experts can aid individuals by answering questions posed by these users. This paper describes a theoretical framework to model the dynamic process by which requests for information arrive in a social network of experts, who then answer the requests after a random time interval. Results on the requests-handling capacity of the network are provided.

Reconfigurable radio frequency (RF) system has recently emerged as a promising solution to cope with multiple communication standards and high spectrum density. In this paper, we propose a novel optimization framework to efficiently program a reconfigurable RF system. In particular, two novel techniques, including (i) search space reduction by adaptive resolution and (ii) global polynomial optimization based on branch and bound, are developed. When combined with a relaxation iteration scheme, our proposed method offers superior performance when programming a large-scale reconfigurable RF system designed for the WLAN 802.11g standard.

Reconfigurable radio frequency (RF) system has emerged as a promising avenue to achieve high communication performance while adapting to versatile commercial wireless environment. In this paper, we propose a novel technique to optimally program a reconfigurable RF system in order to achieve maximum performance and/or minimum power. Our key idea is to adopt an equation-based optimization method that relies on general-purpose, non-convex polynomial performance models to determine the optimal configurations of all tunable circuit blocks. Most importantly, our proposed approach guarantees to find the globally optimal solution of the non-convex polynomial programming problem by solving a sequence of convex semi-definite programming (SDP) problems based on convexification. A reconfigurable RF front-end example designed for WLAN 802.11g demonstrates that the proposed method successfully finds the globally optimal configuration, while other traditional techniques often converge to local optima.

Passive macromodeling for RF circuit blocks is a critical task to facilitate efficient system-level simulation for large-scale RF systems (e.g., wireless transceivers). In this paper we propose a novel algorithm to find the optimal macromodel that minimizes the modeling error based on measurement data, while simultaneously guaranteeing passivity. The key idea is to attack the passive macromodeling problem by solving a sequence of convex semi-definite programming (SDP) problems. As such, the proposed method can iteratively find the optimal poles and zeros for macromodeling. Our experimental results with several commercial RF circuit examples demonstrate that the proposed macromodeling method reduces the modeling error by 1.31-2.74× over other conventional approaches.

In order to support a multi-standard platform, a reconfigurable RF front-end needs an optimal configuration that adapts to a dynamic communication condition. To find an optimal configuration efficiently, we previously proposed the Environment-Adaptable Fast (EAF) optimization in terms of the RF impairments of gain, nonlinearity and noise figure. However, this preliminary study did not include the important impairment of phase noise. In this paper, we extend the EAF optimization algorithm to phase noise impairment in a reconfigurable RF front-end. In this study, we will propose a novel statistical estimation tool for obtaining phase noise spectrum information with the Interpolated FIR (IFIR) model and the least mean squares (LMS) adaptive algorithm. We formulate the calculation of the Signal-to-Interference-and- Noise Ratio (SINR) which hastens the optimization process. Phase noise is included in the SINR calculation. We demonstrate the efficient performance of the EAF optimization method even with phase noise impairment. This study shows that while finding an optimal configuration, the EAF optimization significantly reduces simulation time compared to the other four conventional optimization methods.

Reconfigurable radio frequency (RF) system is an emerging component to mitigate the growing engineering cost for wireless chip design. In this paper, we propose a new methodology for efficient programming of reconfigurable RF receiver. The proposed method is facilitated by two novel techniques: two-phase relaxation search and Pareto-based search space reduction. Our numerical experiments demonstrate that the proposed methodology is more robust (i.e., close to global optimum) and/or efficient (i.e., with low computational cost) than other traditional algorithms based on either local relaxation or simulated annealing.

In this paper, we consider the problem of latent sentiment detection in Online Social Networks such as Twitter. Modeling the underlying social network as an Ising prior, we demonstrate the effect that the underlying social network structure has on the performance of a trivial sentiment detector. In doing so, we introduce a novel communications-oriented framework for characterizing the probability of error and the associated error exponent, based on information theoretic analysis. We study the variation of the calculated error exponent for several stylized network topologies such as the complete network, the star network and the closed-chain network, and show the importance of the network structure in determining detection performance.

There are many protocols for MAC-layer rate control and scheduling of wireless ad hoc networks. Yet, network nodes are often compromised, and thus cannot trust one another to be running a given protocol correctly. This paper proposes a secure protocol for fair rate allocation and rate-stable scheduling at the MAC layer for wireless ad hoc networks. We assume the physical hardware is secure, and design our protocol to be secure against software attacks, i.e., hacking. Software vulnerabilities are divided into three parts: (1) the inputs to the program; (2) the program itself; (3) the output of the program. Our proposed secure fair MAC protocol leverages trusted computing technology. A typical (insecure) fair MAC protocol is first described, and simulations show that our proposed secure fair MAC protocol achieves comparable performance even while under attack.

We consider a general class of low complexity distributed scheduling algorithms in wireless networks, prioritized maximal scheduling, which compute a maximal set of transmitting links in each time slot according to certain pre-specified static priorities. The proposed scheduling scheme has low complexity, and is easily amendable for distributed implementation, such as adjusting inter-frame space (IFS) parameters under the ubiquitous 802.11 protocols. We provide throughput guarantees on the proposed scheduling scheme, by proving tight lower bound on the stability region and scheduling efficiency associated with a fixed priority vector. We next propose an online low complexity priority assignment algorithm, which can stabilize any arrival rate that is in the union of the lower bound regions of all priorities. The throughput guarantees are proved by fluid limits, and therefore can be applied to very general stochastic arrival processes. Finally, the performance of the proposed prioritized maximal scheduling scheme is verified by simulation results.

In this paper, a novel iterative encoding scheme is proposed for memory systems suffering from stuck-at errors. The stuck-at errors can be efficiently managed by using side information about stuck-at memory cells during encoding, while encoding for unconstrained number of stuck-at errors is intractable due to its exponential complexity. The proposed coding scheme employs an iterative encoding algorithm using cross-entropy method, which has a polynomial time complexity. In addition, any linear block code (LBC) can be concatenated with the proposed code, to correct for both residual stuck-at errors and random (soft) errors. The proposed coding schemes are evaluated by numerical simulations using a memory channel undergoing both stuck-at and random errors. Simulation results show that the cross-entropy based coding scheme provides an improved block error rate (BLER) performance, or alternatively, a higher overall storage capacity.

In this paper, we propose a distributed throughput-optimal ad hoc wireless network scheduling algorithm, which is motivated by the celebrated simplex algorithm for solving linear programming (LP) problems. The scheduler stores a sparse set of basic schedules, and chooses the max-weight basic schedule for transmission in each time slot. At the same time, the scheduler tries to update the set of basic schedules by searching for a new basic schedule in a throughput increasing direction. We show that both of the above procedures can be achieved in a distributed manner. Specifically, we propose an average consensus based link contending algorithm to implement the distributed max weight scheduling. Further, we show that the basic schedule update can be implemented using CSMA mechanisms, which is similar to the one proposed by Jiang et al. Compared to the optimal distributed scheduler, where schedules change in a random walk fashion, our algorithm has a better delay performance by achieving faster schedule transitions in the steady state. The performance of the algorithm is finally confirmed by simulation results.

This paper proposes a dynamic primal-dual type scheduling algorithm in wireless networks, which achieves optimal throughput even with uncertain parameters. In wireless networks, such uncertain parameters are generated by complicated stochastic dynamics, such as random packet arrivals, channel fading, and node mobilities. The algorithm is a generalization of the well-known max-weight scheduling algorithm proposed by Tassiulas et al., where the only uncertain parameters are the packet arrival rates. Using the technique of fluid limits, sample path convergence result of the algorithm to an arbitrarily close to optimal solution is proved, under the assumption that the Strong Law of Large Numbers (SLLN) applies to the random processes which generate these uncertain parameters. The performance of the algorithm is further verified by simulation results. This method may potentially be applied to other cross-layer optimization problems, where dynamic algorithms for convex problems with uncertain parameters are needed.

This paper demonstrates fundamental limits of sensor networks for detection problems where the number of hypotheses is exponentially large. Such problems characterize many important applications including detection and classification of targets in a geographical area using a network of seismic sensors, and detecting complex substances with a chemical sensor array. We refer to such applications as large-scale detection problems. Using the insight that these problems share fundamental similarities with the problem of communicating over a noisy channel, we define the “sensing capacity” and lower bound it for a number of sensor network models. The sensing capacity expression differs significantly from the channel capacity due to the fact that for a fixed sensor configuration, codewords are dependent and nonidentically distributed. The sensing capacity provides a bound on the minimal number of sensors required to detect the state of an environment to within a desired accuracy. The results differ significantly from classical detection theory, and provide an intriguing connection between sensor networks and communications. In addition, we discuss the insight that sensing capacity provides for the problem of sensor selection.

In this paper we consider greedy scheduling algorithms in wireless networks, i.e., the schedules are computed by adding links greedily based on some priority vector. Two special cases are considered: 1) Longest Queue First (LQF) scheduling, where the priorities are computed using queue lengths, and 2) Static Priority (SP) scheduling, where the priorities are pre-assigned. We first propose a closed-form lower bound stability region for LQF scheduling, and discuss the tightness result in some scenarios. We then propose an lower bound stability region for SP scheduling with multiple priority vectors, as well as a heuristic priority assignment algorithm, which is related to the well-known Expectation Maximization (EM) algorithm. The performance gain of the proposed heuristic algorithm is finally confirmed by simulations.

Two-dimensional magnetic recording (TDMR) is a data storage paradigm that has recently been proposed to record more than one channel bit to one magnetic grain in order to achieve 10 Tbit/in² of user bit density on a magnetic recording medium with 20 Tgrains/in². In addition to conventional noise in magnetic recording, the TDMR channel also suffers from write errors due to the randomness in size and placement of the grains; however aggressive two-dimensional (2D) signal processing schemes may enable reliable data retrieval. In this study, the symmetric information rate (SIR) of a TDMR channel model based on random Voronoi grains, named the ideal readback TDMR channel model, is analyzed. Using numerical simulations, a lower bound of the SIR is evaluated for a half grain per channel bit ideal readback TDMR channel. Although approximately half of the channel bits may not be recorded in this channel, the resulting lower bound of the SIR is 0.46 ~ 0.51 information bits per grain. This result indicates the potential of TDMR to achieve 10 Tbit/in² of user bit density on a magnetic medium with 20 Tgrains/in².

We consider a general scheduling problem in wireless networks under uncertain arrival and channel state statistics. The objective is to minimize a linear cost function, which can be used to model wireless communication constraints, such as power consumption. We assume that the arrival processes and the network states are random, and with unknown distributions. In each time slot, the schedule can only be computed based on past history. We propose a conditional-gradient type scheduling algorithm and a priority queuing mechanism with auxiliary dummy queues. We show that these can achieve an objective function value which is arbitrarily close to the optimal, while guaranteeing network stability. The performance of the algorithm is further confirmed by simulation results.

Sparse measurement structures - in which each measurement only depends on a small number of the inputs-arise in models of many problems such as sensor networks, group testing and even lossless data compression. The most important question in these applications is `How many measurements are sufficient to reconstruct the input ?'. Regular structures, where each input is measured the same number of times, require fewer measurements than when arbitrary measurements are used. In this paper we conduct a general analysis of the performance of these regular measurement structures when used for lossy reconstruction of the input in the presence of measurement noise. The main contribution of our work is the generality of the result which is applicable to lossy detection with arbitrary, even non-linear measurements and with inputs and outputs in any discrete domain. The second contribution is the quantification of the effect of noise in the measurements on the reconstruction performance, which can be used to analyze the robustness of these sparse measurement structures. We show the generality and applicability of our results by analyzing the performance of pooling designs for rare allele detection.

This paper considers the joint routing and scheduling problem in wireless networks with lossy channels. In order to combat channel loss, packets are assumed to be transmitted by nodes using broadcast, instead of traditional point-to-point communication. We first analyze the network capacity region, and then propose a back-pressure routing with max-weight scheduling algorithm to achieve it. The proposed algorithm is a generalization of the algorithm proposed by Tassiulas to wireless broadcast networks. Further, we propose a random low complexity scheduling algorithm which, combined with backpressure routing, also achieves the same capacity region. Both stability results are proved by the method of fluid limits.

Quality of Service (QoS) guarantees in mobile wireless networks are typically provided through queuing analysis, which uses an idealized model for the physical layer, leading to optimistic guarantees. A queued-code combines ideas from queuing theory and information/coding theory, to allow rate adaptation, while enabling accurate modeling of the physical layer. Previous work showed the benefit of using a queued-code, in achieving lower error probabilities while satisfying a fixed delay bound. This paper analyzes the queued-code when some function of delay statistics must be optimized while guaranteeing a fixed error probability. A practical implementation of queued-codes based on low density parity check (LDPC) convolutional codes is also presented. Numerical and simulation results demonstrate the benefit of using the queued-code in obtaining a better QoS.

In this paper we consider prioritized maximal scheduling in multi-hop wireless networks, where the scheduler chooses a maximal independent set greedily according to a sequence specified by certain priorities. We show that if the probability distributions of the priorities are properly chosen, we can achieve the optimal (maximum) stability region using an i.i.d random priority assignment process, for any set of arrival processes that satisfy Law of Large Numbers. The pre- computation of the priorities is, in general, NP-hard, but there exists polynomial time approximation scheme (PTAS) to achieve any fraction of the optimal stability region. We next focus on the simple case of static priority and specify a greedy priority assignment algorithm, which can achieve the same fraction of the optimal stability region as the state of art result for longest queue first (LQF) schedulers. We also show that this algorithm can be easily adapted to satisfy delay constraints in the large deviations regime, and therefore, supports quality of service (QoS) for each link.

We consider the problem of providing explicit quality of service (QoS) guarantees to multiple users sharing a downlink time-slotted fading channel. We present a scheduler that can achieve a significant gain in terms of QoS, compared to a scheduler that uses a fixed time-slot assignment. QoS guarantees are provided for each user by using the queued-code framework which efficiently captures both, the queuing behavior at the link layer, and encoding/decoding at the physical layer. Numerical results show that our approach results in significantly better QoS compared to the fixed-slot assignment scheme, in a variety of communication scenarios.

This paper considers the scheduling problem in wireless networks. We focus on prioritized maximal scheduling, where a maximal scheduler chooses the links in an order specified by certain priority. We first analyze the capacity region of a maximal scheduler with fixed priority, where a lower bound is formulated and shown to be tight. Next we propose both centralized and distributed algorithms to search for the optimal priority for a given arrival rate. The algorithms are optimal in the sense that, if the arrival rate is in the lower bound region of any prioritized maximal scheduling, it is stable under the result of our algorithms. Finally, by combining the priority assignment and maximal scheduling, we prove that we can achieve a certain fraction of the optimal capacity region, which is bounded below by a constant for most networks.

In synchronous timing recovery approaches often employed in magnetic recording readback channels, the timing error detector (TED) output is assumed to be linearly related to the underlying phase offset. However, the noisy readback signal samples in high-density magnetic recording systems are nonlinearly related to the underlying timing disturbances. Thus, a nonlinear state space models may describe such systems more accurately and an improved timing recovery solution may be obtained via an extended Kalman filter (EKF) approach. In this paper, EKF based timing recovery is investigated for the acquisition stage. Numerical simulations indicate that the EKF based timing recovery scheme yields smaller root mean square (RMS) error in timing estimates, which enables it to handle larger timing errors more reliably. In addition, the proposed method converges faster than the conventional timing recovery schemes, which may allow us to reduce the length of the preamble pattern used for the acquisition.

Scheduling in an ad hoc wireless network suffers from the non-convexity of the cost function, caused by the interference between communication links. In previous optimization theoretic analysis, the weighted sum-rate maximization (WSRM) which inherits the non-convexity has been identified as a core problem of the hard scheduling problem. In this paper, we propose a polynomial-time approximation algorithm with guaranteed accuracy for WSRM under an Ultra- wide band (UWB) assumption. The algorithm is obtained by an appropriate adaptation of the 'shifting' strategy (a well- known approximation technique for some geometric problems) for the wireless broadcast environment. The worst case accuracy and complexity of the algorithm are analyzed by utilizing the quadratic link rate function derived in previous research, under the assumption of a large bandwidth, as is typical in UWB networks. The average case performance of the algorithm is investigated by simulations on random ad hoc networks.

We introduce a hypergraph based interference model for scheduling in wireless networks. As a generalization of the graph model, hypergraph considers the conflicts caused by sum interference. We show in an arbitrary network, the successful transmissions under any graph model can be improved by a hypergraph. In some networks, a hypergraph can double the uniform throughput compared to the disk graph. We then analyze the capacity region of maximal scheduling in the hypergraph, where a linear programming (LP) based lower bound is formulated and proven to be tight. We also show that the maximal scheduling in hypergraph can guarantee a certain fraction of the capacity region. Simulation results show that maximal scheduling in hypergraph can achieve about 40% more uniform throughput than in graph for random networks.

Seminal work by Chevillat and Costello showed that for specific convolutional codes transmitted over a binary symmetric channel and decoded by sequential decoding, a measure of decoding effort decreases exponentially with the column distance function of the code. This has led to a large body of research in the design of codes with good distance profiles which are also used for transmission over Gaussian channels. In this paper we analyze the computational complexity of a stack decoder working on a specific tree code with real (as opposed to binary) symbols, transmitted over a memoryless Gaussian channel. In contrast to prior work that used random coding arguments, we use the intuition provided by the original proof to prove that decoding effort exhibits similar behavior even for a memoryless Gaussian channel. Our result is applicable to convolutional codes with antipodal signaling, sequence detection over Gaussian ISI channels and some sensor networks.

The broadcast nature of the wireless medium makes the communication over this medium vulnerable to eavesdropping. This paper considers the problem of secret communication between two nodes, over a fading wireless medium, in the presence of a passive eavesdropper. The assumption used is that the transmitter and its helpers (amplifying relays) have more antennas than the eavesdropper. The transmitter ensures secrecy of communication by utilizing some of the available power to produce 'artificial noise', such that only the eavesdropper's channel is degraded. Two scenarios are considered, one where the transmitter has multiple transmit antennas, and the other where amplifying relays simulate the effect of multiple antennas. The channel state information (CSI) is assumed to be publicly known, and hence, the secrecy of communication is independent of the secrecy of CSI.

Abstract Providing quality of service (QoS) guarantees is important in the third generation (3G) and the fourth generation (4G) cellular networks. However, large‐scale fading and non‐stationary small‐scale fading can cause severe QoS violations. To address this issue, we design QoS provisioning schemes, which are robust against time‐varying large scale path loss, shadowing, non‐stationary small scale fading, and very low mobility. In our design, we utilize our recently developed effective capacity technique and the time‐diversity dependent power control proposed in this paper. The key elements of our QoS provisioning schemes are channel estimation, power control, dynamic channel allocation, and adaptive transmission. The advantages of our QoS provisioning schemes are (1) power efficiency, (2) simplicity in QoS provisioning, (3) robustness against large‐scale fading and non‐stationary small‐scale fading. Simulation results demonstrate that the proposed algorithms are effective in providing QoS guarantees under various channel conditions. Copyright © 2006 John Wiley & Sons, Ltd.

A 'queued-code' is a novel code which allows for instantaneous rate adaptation, to match the current channel state information (CSI), assumed known to the transmitter. Previously, information theoretic codes were analyzed in the regime of large delay bounds. Numerical results had demonstrated the performance gain of these codes over fixed rate codes, in a range of situations. This paper presents queued-codes which are designed using low density parity check (LDPC) block codes. Simulation results demonstrate performance gain of these codes over fixed rate LDPC block codes. The simulation results are consistent with the numerical results obtained for the information theoretic codes, which is a satisfying result. Further, this paper argues for the use of rate adaptation within a codeword, as opposed to rate adaptation across codewords, when CSI is available at the transmitter.

For decades, a disk-graph model has been used to design scheduling (coloring) in wireless networks, influencing many practical medium access control schemes. The pairwise - interference model used by a disk graph, however, has a fundamental limitation because it does not account for the sum- interference. Thus, a coloring algorithm that uses such a model cannot guarantee the originally intended rate on all links. In this paper, we specify a mapping to a flow-contention graph, which fully considers the aggregated effect of all interferers (sum- interference), and thus, guarantees the originally intended rate on all links. A coloring algorithm, specific to the generated graph, is presented along with a bound on the required number of colors (channels). Further, a mathematical analysis of the scheduling is presented along with simulation results, to show that the minimum number of channels required in a random network is Theta(logn/log log n), where n is the number of links, even after accounting for the sum-interference. This allows us to investigate the effect of the underlying physical layer, thus demonstrating the utility of the presented algorithm and analysis results.

Multi-slot resource scheduling in a general two dimensional wireless ad hoc network, is a hard problem with no known polynomial-time solution. Recent optimization theoretic analysis, structures this multi-slot scheduling problem into a polynomial number of particular single-slot sub-problems, thus isolating the hardness. We consider this hard sub-problem, under the useful topology restriction of a single route of many links. We introduced a novel interference model that allows for a dynamic programming (DP) algorithm to solve this sub-problem. The developed DP algorithm provides a solution with a provable accuracy in polynomial time. Incorporating this novel solution in a general resource scheduling framework, a multi-slot scheduling algorithm for single route networks is developed. The excellent accuracy of the algorithms is demonstrated through extensive simulations in various scenarios.

UWB and 802.11n have both been touted as technologies for next generation wireless networks. UWB exploiting a large bandwidth, and 802.11n utilizing MIMO, demonstrate high data rates in single links. However, in real world applications these two technologies will not operate as isolated single links, but in a network environment characterized by interference. Through the application of a formal optimization theoretic framework, we demonstrate that their relative network performance is very different from a physical layer comparison. The interference handling capabilities of UWB and 802.11n cause this significant network performance result. We explore practical effects that alter the perceived interference and so, relative network performance. Further, recommendations for the use of multiple antennas in 802.11n radios are presented.

Prior work motivated the use of sequential decoding for the problem of large-scale detection in sensor networks. In this paper we develop the metric for sequential decoding from first principles, different from the Fano metric which is conventionally used in sequential decoding. The difference in the metric arises due to the dependence between codewords, which is inherent in sensing problems. We analyze the behavior of this metric and show that it has the requisite properties for use in sequential decoding, i.e., the metric is, 1) expected to increase if decoding proceeds correctly, and 2) expected to decrease if more than a certain number of decoding errors are made. Through simulations, we show that the metric behaves according to theory and results in much higher accuracies than the Fano metric. We also show that due to an empirically-observed computational cutoff rate, we can perform accurate detection in large scale sensor networks, even when the optimal Viterbi decoding is not computationally feasible.

Existing protocols for secure key establishment all rely on an unspecified mechanism for initially deploying secrets to sensor nodes. However, no commercially viable and secure mechanism exists for initial setup. Without a guarantee of secure key deployment, the traffic over a sensor network cannot be presumed secure.

Throughput capacity is a critical parameter for the design and evaluation of ad-hoc wireless networks. Assuming a fixed per node transmission capability of T bits per second at a fixed range, it has been shown [1] that the information theoretic uniform throughput capacity per node r(n) is Theta (T/radicn log n), a decreasing function of node density n. However we consider an alternate communication model, with each node constrained to a maximum transmit power P0and capable of utilizing W Hz of bandwidth. Under the limiting case W rarr infin, such as in ultra wide band (UWB) networks, we show that the uniform throughput per node is O ((n log n)alpha-1/2(upper bound) and Omega(n(alpha-1)/2(log n(alpha+1)/2) (achievable lower bound). Thus we demonstrate that the throughput increases with node density n, in contrast to previously published results. The capacity problem is also considered from an optimization theoretic perspective. The novel information theoretic capacity bound is compared to the network optimization results, demonstrating its practical applicability to UWB networks. The dramatic effect of the UWB physical layer on the capacity justifies the promise of UWB as a physical layer technology for ad-hoc networks.

A general cross-layer optimization problem, to maximize network efficiency (min-max power) of ad-hoc networks, is formulated including power adaptation, scheduling and routing functionalities. The non-convexity of the link capacity, high dimensionality of multi-hop routing and inter-layer interactions among the protocol layers, renders the problem hard. Conversion to an equivalent form, results in two clearly separable sub-problems, demonstrating the functionalities of the protocol layers. This decomposition allows the application of a simple shortest path based algorithm to the high-dimensional routing sub-problem. Further, in the case of UWB networks, the non-convex scheduling & power adaptation sub-problem can be effectively approximated and solved by applying a novel quadratic lower bound to the link capacity function. Using these algorithmic solutions to these sub-problems, an interior point solver generating solutions to the joint UWB network problem is developed. The various simulation results demonstrate interesting characteristics of the optimal routing and scheduling solutions, and provide benchmarks for UWB network design. Comparison with prior information theoretic capacity results, validates the importance of this cross-layer optimization framework

Debate has been raging on the relative merits of Ultra Wide Band (UWB) and 802.11 as the technology of choice to achieve high speed wireless networking. The comparisons have focused on the single-link rate versus range issues. However, in real world applications, these radios will operate in a networking environment with significant interference effects. The interference handling capabilities of these two radios are drastically different due to their dramatically opposite power-bandwidth trade-offs. In this paper, a networking comparison, of UWB and 802.11, is performed through the application of a formal optimization theoretic framework. Simulations are conducted for network topologies typical of WPAN and WLAN scenarios. It is demonstrated that the link range over which UWB outperforms 802.11 is larger than is to be expected from a single-link comparison. Thus, a network-level comparison of different physical layers is shown to be essential in choosing the appropriate wireless technologies. A few possible future variations of 802.11 and UWB are also investigated in this flexible framework.

Computing the exact maximum likelihood or maximum a posteriori estimate of the environment is computationally expensive in many practical distributed sensing settings. We argue that this computational difficulty can be overcome by increasing the number of sensor measurements. Based on our work on the connection between error correcting codes and sensor networks, we propose a new algorithm which extends the idea of sequential decoding used to decode convolutional codes to estimation in a sensor network. In a simulated distributed sensing application, this algorithm provides accurate estimates at a modest computational cost given a sufficient number of sensor measurements. Above a certain number of sensor measurements this algorithm exhibits a sharp transition in the number of steps it requires in order to converge, leading to the potentially counter-intuitive observation that the computational burden of estimation can be reduced by taking additional sensor measurements.

A 'queued-code' is a novel channel code, whose input rate is instantaneously adapted to the channel state information, assumed to be known to the transmitter. Previously, a queued-code was demonstrated for i.i.d. block fading channels, demonstrating significant gains, in terms of error exponent, over a fixed rate code. This paper demonstrates the performance gain of the queued-code in the more realistic case of a finite-state Markov fading channel. Similar to the block-fading result, the analysis required combines the concept of random coding bounds from information theory, and the concept of effective capacity, arising from large deviation theory analysis of queues. However, a result on the limiting moment generating function of Markov chains is the additional tool required for the analysis

The ad hoc wireless MAC problem is based on a model of interference between links. Prior disk graph models consider pair-wise interference and have been analyzed to provide bounds on MAC performance, through the application of graph theoretic coloring results. The recently developed PHY graph model is based on the physical layer and so is a more realistic model than disk graph models. An initial MAC performance bound based on the PHY graph model has been shown. Here, the model is analyzed in a novel proof resulting in an improved bound on the MAC performance. The accuracy of the PHY graph model, in modelling the ad hoc wireless problem, is explored through detailed simulations. Salient features of the model are utilized to provide a performance improvement.

Reservation based medium access control (MAC) protocols such as the 802.11 distributed coordination function (DCF), are designed to maximize throughput efficiency, by utilizing small control packets. However, this ability to reserve bandwidth makes the protocol susceptible to sophisticated MAC layer denial of service (DoS) attacks. A novel attack on reservation based MAC protocols is described using the example of 802.11 networks. An analysis of the attack demonstrates the catastrophic effect on network throughput of a low power MAC layer jammer. This is in contrast to physical layer jamming, where the loss of throughput is proportional to jammer power. A counter-measure based on modifying the MAC protocol is developed, and shown to limit the intelligent jammer's effect. Protections against further attacks on the modified protocol are also discussed.

We bound the number of sensors required to achieve a desired level of sensing accuracy in a discrete sensor network application (e.g. distributed detection). We model the state of nature being sensed as a discrete vector, and the sensor network as an encoder. Our model assumes that each sensor observes only a subset of the state of nature, that sensor observations are localized and dependent, and that sensor network output across different states of nature is neither identical nor independently distributed. Using a random coding argument we prove a lower bound on the 'sensing capacity' of a sensor network, which characterizes the ability of a sensor network to distinguish among all states of nature. We compute this lower bound for sensors of varying range, noise models, and sensing functions. We compare this lower bound to the empirical performance of a belief propagation based sensor network decoder for a simple seismic sensor network scenario. The key contribution of this paper is to introduce the idea of a sharp cut-off function in the number of required sensors, to the sensor network community.

This paper computes the sensing capacity of a sensor network, with sensors of limited range, sensing a two-dimensional Markov random field, by modeling the sensing operation as an encoder. Sensor observations are dependent across sensors, and the sensor network output across different states of the environment is neither identically nor independently distributed. Using a random coding argument, based on the theory of types, we prove a lower bound on the sensing capacity of the network, which characterizes the ability of the sensor network to distinguish among environments with Markov structure, to within a desired accuracy

To efficiently support quality of service (QoS) in future wireless networks, it is important to model a wireless channel in terms of connection-level QoS metrics such as data rate, delay and delay-violation probability. To achieve this, in D. Wu and R. Negi (2003), we proposed and developed a link-layer channel model termed effective capacity (EC) for flat fading channels. In this paper, we apply the effective capacity technique to modeling frequency selective fading channels. Specifically, we utilize the duality between the distribution of a queue with superposition of N i.i.d. sources, and the distribution of a queue with a frequency-selective fading channel that consists of N i.i.d. sub-channels, to model a frequency selective fading channel. In the proposed model, a frequency selective fading channel is modeled by three EC functions; we also propose a simple and efficient algorithm to estimate these EC functions. Simulation results show that the actual QoS metric is closely approximated by the QoS metric predicted by the proposed EC channel model. The accuracy of the prediction using our model can translate into efficiency in admission control and resource reservation.

The max-min fair scheduling problem in wireless ad-hoc networks is a non-convex optimization problem. A general framework is presented for this optimization problem and analyzed to obtain a dual problem, which involves solving a series of optimization sub-problems. In the limit of infinite bandwidth (W /spl rarr/ /spl infin/), the scheduling solution reduces to simultaneous transmission (spread spectrum) on all links (R. Negi and A. Rajeswaran, March 2004). This motivates the analysis of the scheduling problem in the ultra wide band (UWB) regime (W /spl Gt/ 1, but finite), a model for certain practical radios. A quadratic (in 1/W) lower bound to the single link capacity function is developed, which simplifies the dual sub-problem to a quadratic optimization (R. Negi and A. Rajeswaran, December 2004). The solution to this sub-problem is then obtained under both total power and power spectral density constraints. This solution is utilized to iteratively construct the schedule (subband sizes) and power allocation, thus optimally solving the UWB max-min fair scheduling problem, to within any desired precision. Simulations on medium sized networks demonstrate the excellent performance of this scheme. A cellular architecture (not necessarily UWB) may also be considered in this framework. It is proved that frequency division multiple access is the optimal scheduling for a multi-band cellular architecture.

An important objective of next-generation wireless networks is to provide quality of service (QoS) guarantees. This requires a simple and efficient wireless channel model that can easily translate into connection-level QoS measures such as data rate, delay, and delay-violation probability. To achieve this, in D. Wu and R. Negi (July 2003), we developed a link-layer channel model termed effective capacity, for the setting of a single hop, constant-bit-rate arrivals, fluid traffic, and wireless channels with negligible propagation delay. In this paper, we apply the effective capacity technique to deriving QoS measures for more general situations, namely: 1) networks with multiple wireless links, 2) variable-bit-rate sources, 3) packetized traffic, and 4) wireless channels with non-negligible propagation delay.

Queuing theory allows the design of communication links that can provision for quality of service (QoS) in time-varying channels, such as mobile wireless channels, by considering an idealized queuing system that abstracts out the physical layer. Similarly, information theory allows the design and analysis of channel codes that can guarantee low decoding error probability by adapting to the time-varying channel. Whereas other researchers have attempted cross-layer design methods that combine these two approaches, these have been limited to specific choices of practical channel codes. There have been few attempts to combine these two theories to specify the ultimate limit of delay-constrained communications. The paper presents an approach that obtains a QoS exponent by combining the queuing and information theoretic models; in particular, by considering information-theoretically optimal channel codes. Calculations show that such a joint approach yields substantial improvement in QoS performance in a variety of communication scenarios.

The max-min fair scheduling problem in wireless ad hoc networks, in general, is a non-convex optimization problem. However in the limit of infinite bandwidth (W /spl rarr/ /spl infin/), the solution reduces to a simple simultaneous transmission (spread spectrum) of all links. Thus, having a very large bandwidth significantly simplifies the problem of scheduling. In This work, the scheduling problem is considered in the UWB regime (W /spl Gt/1 but finite), a model for certain practical radios. A quadratic (in 1/W) lower bound to the single link capacity function is developed. This approximation is applied to the general non-convex scheduling problem to obtain a dual problem, which involves a quadratic optimization sub-problem. A search algorithm is devised to find the optimal solution of the quadratic sub-problem. This solution is utilized to iteratively construct the schedule (sub-band sizes) and power allocation, thus optimally solving the UWB max-min fair scheduling problem, to within any desired precision. Simulations on medium sized networks demonstrate the excellent performance of this scheme. Thus, exploiting the UWB nature of the physical layer simplifies the wireless ad-hoc network scheduling problem.

Throughput capacity is a critical parameter for the design and evaluation of ad-hoc wireless networks. Consider n identical randomly located nodes, on a unit area, forming an ad-hoc wireless network. Assuming a fixed per node transmission capability of T hits per second at a fixed range, it has been shown that the uniform throughput capacity per node r(n) is /spl otimes/(T//spl radic/nlogn). We consider an alternate communication model, with each node constrained to a maximum transmit power P/sub 0/ and capable of utilizing W Hz of bandwidth. Under the limiting case W/spl rarr//spl infin/, such as in ultra wide band networks, the uniform throughput per node is /spl otimes/((nlogn)/sup /spl alpha/-1/2/ (upper bound) and /spl Omega/(n/sup (/spl alpha/-1)/2//(logn)/sup (/spl alpha/+1)/2/) (achievable lower bound). These bounds demonstrate that throughput increases with node density n, in contrast to previously published results. This is the result of the large bandwidth, and the assumed power and rate adaptation, which alleviate interference. Thus, the significance of physical layer properties on the capacity of ad-hoc wireless networks is demonstrated.

We define a notion of 'sensing capacity' that characterizes the ability of a sensor network to successfully distinguish among a discrete set of targets. Sensing capacity is defined as the maximum ratio of target positions to sensors for which inference of targets within a certain distortion is achievable. We demonstrate a lower bound on this capacity. Unlike previous work on 'sensor network capacity', our notion of sensing capacity is defined by the sensing task itself, as opposed to external resource constraints such as power, communications, and processing.

This paper presents an approach that uses relaying to increase CDMA cellular capacity (spectral efficiency). The key insight is that, since the power received by the mobile falls off rapidly, as a function to distance to the base station, relaying could potentially be used to eliminate the out-of-cell interference, thus increasing the cellular capacity. However, as the paper shows, achieving the increase in capacity requires a specific relaying architecture, which can successfully control the interference at the relay stations. This architecture is shown to achieve up to 20% increase in CDMA cellular capacity, when shadowing effects are absent.

We consider the problem of quality of service (QoS) provisioning for K users sharing a downlink time-slotted Rayleigh fading channel. We develop simple and efficient schemes for admission control, resource allocation, and scheduling, which can yield substantial capacity gain. The efficiency is achieved by virtue of multiuser diversity. A unique feature of our work is explicit provisioning of statistical QoS, which is characterized by a data rate, delay bound, and delay-bound violation probability triplet. The results show that compared with a fixed-slot assignment scheme, our approach can substantially increase the statistical delay-constrained capacity of a fading channel, when delay requirements are not very tight, while yet guaranteeing QoS at any delay requirement.

To facilitate the efficient support of quality of service (QoS) in next-generation wireless networks, it is essential to model a wireless channel in terms of connection-level QoS metrics such as data rate, delay, and delay-violation probability. However, the existing wireless channel models, i.e., physical-layer channel models, do not explicitly characterize a wireless channel in terms of these QoS metrics. In this paper, we propose and develop a link-layer channel model termed effective capacity (EC). In this approach, we first model a wireless link by two EC functions, namely, the probability of nonempty buffer, and the QoS exponent of a connection. Then, we propose a simple and efficient algorithm to estimate these EC functions. The physical-layer analogs of these two link-layer EC functions are the marginal distribution (e.g., Rayleigh-Ricean distribution) and the Doppler spectrum, respectively. The key advantages of the EC link-layer modeling and estimation are: 1) ease of translation into QoS guarantees, such as delay bounds; 2) simplicity of implementation; and 3) accuracy, and hence, efficiency in admission control and resource reservation. We illustrate the advantage of our approach with a set of simulation experiments, which show that the actual QoS metric is closely approximated by the QoS metric predicted by the EC link-layer model, under a wide range of conditions.

We present a new algorithm for blind symbol synchronization in orthogonal frequency division multiplexing (OFDM) systems. The new algorithm declares symbol synchronization when a certain autocorrelation matrix, constructed from the received signal, achieves minimum rank. Unlike previously proposed blind algorithms, the new rank method guarantees correct symbol synchronization, even in the presence of intersymbol interference. Also, it does not assume that the OFDM time samples are i.i.d. In particular, the rank method works even with OFDM systems that employ pulse shaping. The increased complexity of the algorithm would be acceptable for systems, such as fixed-receiver broadcast systems, that require guaranteed synchronization under all conditions.

Space-time codes have been introduced to improve mobile system performance in a multipath fading environment. We consider a multiple-input multiple-output (MIMO) system with m mobile antennas and n base station antennas, in which there are L multipaths at the base station at distinct angles of arrival. We show that when the channel has no intersymbol interference (ISI), then adaptive antennas in the form of beamforming, can be combined with space-time coding, to achieve a diversity gain of mL and a large signal-to-noise ratio (SNR) gain whenever n/spl ges/L. When the channel has ISI, beamforming can be used by the MIMO systems to achieve an SNR gain over a single-input multiple-output system, although both systems have the same diversity gain.

A block-fading channel model is considered, and a K-block delay constraint is imposed on data transmission. The key consideration is that the channel state information is fed back to the transmitter in a causal manner. A general cost function /spl mu/(x) is considered in solving the delay-constrained transmission problem, under the short-term and the long-term power constraints. A causal power adaptation strategy is needed to maximize the cost function, hence dynamic programming is found to give the optimum solution. The general cost function is then specialized to the cases of expected and outage capacities. In the case of expected capacity, it is observed that optimizing the transmitted power does not give much benefit at high signal-to-noise ratio (SNR), but provides a substantial gain at low SNR. At low SNR, it is proved that the capacity increases by a factor of approximately log K/m, due to power adaptation, when the channel fades according to the /spl chi//sub 2m//sup 2/ statistics. In the case of outage capacity, it is shown that the optimum power adaptation solution to the long-term constraint problem provides a substantial SNR gain at both low and high values of SNR. Random coding bounds are derived for the outage capacity algorithms.

To facilitate the efficient support of quality of service (QoS) in third generation (3G) and fourth generation (4G) wireless networks, it is essential to model a wireless channel in terms of connection-level QoS metrics such as bandwidth, delay and packet loss ratio. However, the existing wireless channel models do not explicitly characterize a wireless channel in terms of these QoS metrics. We propose and develop a wireless channel model termed effective capacity (EC). In this approach, we first model a wireless channel by two EC functions, namely the probability of a non-empty buffer and the QoS exponent of a connection. Then, we design a simple and efficient algorithm to estimate these EC functions. The key advantages of EC channel modeling and estimation are: (1) ease of translation into QoS guarantees, such as delay bounds; (2) simplicity of implementation; (3) accuracy, and hence efficiency, in admission control and resource reservation. We illustrate the advantage of our approach with simulations which show that the actual QoS metric is closely approximated by the QoS metric predicted by the EC channel model.

This paper studies the decorrelation property of the constituent codes in space-time turbo codes (STTCs), where different constituent codes are transmitted over different antennas. We show that the time correlation between constituent codes falls of with respect to STTC block length N as 1//spl radic/N for large N, and hence goes to zero as N/spl rarr//spl infin/. We then use this result to obtain analytical expressions for the frame error rate (FER) of STTCs in flat fading. The decorrelation property of STTCs helps explain the exceptional performance of STTCs on slowly varying flat fading channels.

This paper proposes to combine maximum-likelihood (ML) decoding and decision feedback equalization (DFE) for the Vertical Bell Laboratories Layered Space-Time (V-BLAST) system. In the new decoding algorithm, we perform ML decoding for the first p subchannels, and use the DFE procedure for the remaining subchannels. We mathematically show that the new decoding scheme increases the diversity order for the worst subchannel from 1 to p, and verify it by computer simulation. Also, we propose an ordering scheme which gives the best performance for the worst subchannel, and show that an SNR gain equal to the number of transmit antennas can be achieved by the suggested ordering.

We consider a block flat fading channel, where both the transmitter and receiver have perfect knowledge of the channel gain of the current block, but have no knowledge of future blocks. For a delay constraint of K blocks, and a target rate R/sub 0/, we derive the optimum power adaptation strategy that would minimize the probability of outage, which is equivalent to finding the outage capacity. Both, short term and long term power constraints are considered. Significant power gains are afforded by the strategy for all SNRs, even for small K.

In this paper we present a new space time block code as an antenna diversity scheme for transmit antenna diversity. The space-time-transmit-diversity (STTD) method is an open loop transmit diversity scheme, i.e. it does not require any knowledge of the channel at the transmitter. Simulations have shown that the STTD scheme significantly outperforms the case where no antenna diversity is used. In fact, it even outperforms the non-diversity (ND) case even when soft handoff is used. STTD exploits the extra path diversity afforded by the second antennas and therefore outperforms two other open loop transmit antenna diversity techniques, viz. the orthogonal transmit diversity (OTD) and the time switched time diversity (TSTD). These techniques use multiple transmit antennas to provide some interleaver time diversity against fading, particularly at low Doppler rates and when the mobile receiver does not have enough paths at the RAKE receiver. STTD has the added advantages of being a power amplifier (PA) balanced technique, is easily backward compatible with ND systems and does not need careful interleaver design.

We discuss the usage of space-time coding with multi-antenna transmission for a DS/CDMA system. We have considered an L-multipath, M-mobile antenna system in which the base station has a phased N-antenna array (i.e. fading at the base station antennas is completely correlated). We have shown that for the considered DS/CDMA system, for the channel with no ISI, adaptive antennas, with optimized transmit vector, can be combined with space-time coding (e.g. delay-diversity coding) to achieve a diversity gain of ML and a large coding gain whenever N/spl ges/L.