Search

We investigate the problem of finding minimum-distortion policies for streaming delay-sensitive but distortion-tolerant data. We consider cross-layer approaches which exploit the coupling between presentation and transport layers. We make the natural assumption that the distortion function is convex and decreasing. We focus on a single source-destination pair and analytically find the optimum transmission policy when the transmission is done over an error-free channel. This optimum policy turns out to be independent of the exact form of the convex and decreasing distortion function. Then, for a packet-erasure channel, we analytically find the optimum open-loop transmission policy, which is also independent of the form of the convex distortion function. We then find computationally efficient closed-loop heuristic policies and show, through numerical evaluation, that they outperform the open-loop policy and have near optimal performance. Index Terms--Delay-sensitive, distortion, scheduling, source-coding, streaming.

In wireless networks, throughput optimization is an essential performance objective that cannot be adequately characterized by a single criterion (such as the minimum transmitted or sum-delivered throughput) and should be specified over all source--destination pairs as a rate region. For a simple and yet fundamental model of tandem networks, a cross-layer optimization framework is formulated to derive the maximum throughput region for saturated multicast traffic. The contents of network flows are specified through network coding (or plain routing) in network layer and the throughput rates are jointly optimized in medium access control layer over fixed set of conflict-free transmission schedules (or optimized over transmission probabilities in random access). If the network model incorporates bursty sources and allows packet queues to empty, the objective is to specify the stability region as the set of maximum throughput rates that can be sustained with finite packet delay. Dynamic queue management strategies are used to expand the stability region toward the maximum throughput region. Network coding improves throughput rates over plain routing and achieves the largest gains for broadcast communication and intermediate network sizes. Throughput optimization imposes fundamental tradeoffs with transmission and processing energy costs such that the throughput-optimal operation is not necessarily energy efficient. Index Terms--Cross-layer design, energy efficiency, medium access control, network coding, network stability, routing, throughput optimization, wireless networks.

In this paper, a novel cognitive multiple-access strategy in the presence of a cooperating relay is proposed. Exploiting an important phenomenon in wireless networks, source burstiness, the cognitive relay utilizes the periods of silence of the terminals to enable cooperation. Therefore, no extra channel resources are allocated for cooperation and the system encounters no bandwidth losses. Two protocols are developed to implement the proposed multiple-access strategy. The maximum stable throughput region and the delay performance of the proposed protocols are characterized. The results reveal that the proposed protocols provide significant performance gains over conventional relaying strategies such as selection and incremental relaying, specially at high spectral efficiency regimes. The rationale is that the lossless bandwidth property of the proposed protocols results in a graceful degradation in the maximum stable throughput with increasing the required rate of communication. On the other hand, conventional relaying strategies suffer from catastrophic performance degradation because of their inherent bandwidth inefficiency that results from allocating specific channel resources for cooperation at the relay. The analysis reveals that the throughput region of the proposed strategy is a subset of its maximum stable throughput region, which is different from random access, where both regions are conjectured to be identical. Index Terms--Cooperative communications, delay analysis, diversity techniques, multiple access, queueing theory, relay channel, stability analysis, stability region.

This paper addresses network coding in wireless networks in conjunction with medium access control (MAC). It is known that coding over wired networks enables connections with rates that cannot be achieved by routing. However, the properties of wireless networks (e.g., omnidirectional transmissions, destructive interference, single transceiver per node, finite energy) modify the formulation of time-varying network coding in a way that reflects strong interactions with underlying MAC protocols and deviates from the classical approach used in wired network coding. To perform network coding over conflict-free transmission schedules, predetermined network realizations are separately activated by a time-division mechanism and the content of network flows is derived through network coding to optimize performance measures such as achievable throughput and energy costs. A systematic method is presented to construct linear wireless network codes and interactions with MAC schedules are discussed under wireless assumptions. Network coding is also extended to operate with arbitrary (random or scheduled access based) MAC protocols. Alternatively, conflict-free transmission schedules are jointly constructed with network codes by decomposing wireless networks into subtrees and employing graph coloring on simplified subtree graphs. Finally, network coding and plain routing are compared in terms of throughput, energy and delay performance under different MAC solutions. Index Terms--Cross-layer design, energy efficiency, graph theory, medium access control (MAC), multiuser information theory, network coding, wireless ad hoc networks.

A wireless network in which packets are broadcast to a group of receivers through use of a random access protocol is considered in this work. The relation to previous work on networks of interacting queues is discussed and subsequently, the stability and throughput regions of the system are analyzed and presented. A simple network of two source nodes and two destination nodes is considered first. The broadcast service process is analyzed assuming a channel that allows for packet capture and multipacket reception. It is proved that the stability and throughput regions coincide in this small network. The same problem for a network with N sources and M destinations is considered next. The channel model is simplified in that packet capture and multipacket reception is no longer permitted. Bounds on the stability region are developed using the concept of stability rank and the throughput region of the system is compared to the bounds. Our results show that as the number of destination nodes increases, the stability and throughput regions diminish. Additionally, a previous conjecture that the stability and throughput regions coincide for a network of arbitrarily many sources is supported for a broadcast scenario by the results presented in this work. Index Terms--ALOHA, multipacket reception, random access, queueing, stability, throughput, wireless broadcast.

The problem of determining a minimal length schedule to satisfy given link demands in a wireless network is considered. Links are allowed to be simultaneously active if no node can simultaneously transmit and receive, no node can transmit to or receive from more than one node at a time, and a given signal-to-interference and noise ratio (SINR) is exceeded at each receiver when transmitters use optimally chosen transmit powers. We show that a) the general problem is at least as hard as the MAX-SIR-MATCHING problem, which is easier to describe and b) when the demands have a superincreasing property the problem is tractable. Index Terms--Power control, scheduling, signal-to-interference and noise ratio (SINR) constraints, wireless.

The problem of determining what links can be simultaneously activated in a wireless network such that a signal-to-interference-and-noise (SINR) constraint is satisfied at all receivers is considered. The term "feasible matching" is introduced to describe a set of (transmitter, receiver) pairs for which there exists some set of transmit powers which can simultaneously meet the SINR requirements at the receivers. Given disjoint equally sized sets of transmitters and receivers, it is shown that when the SINR requirement at the receivers is greater than 1, no more than one feasible matching between the transmitters and the receivers exists. Sufficient conditions are provided under which certain broad classes of matchings in a network are guaranteed to be feasible; for example all matchings involving k or fewer links. The application of these results to ad hoc wireless networks and to scheduling is discussed. Index Terms--Feasibility, interference, matchings, power control, wireless networks.

This paper studies finite-terminal random multiple access over the standard multipacket reception (MPR) channel. We characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of ALOHA protocol. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is coordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. Inner and outer bounds to the capacity region are derived. We show that both the inner and the outer bounds converge asymptotically to the throughput region. In the second part of the paper, we study the stability region of finite-terminal ALOHA multiple access. For a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. We also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. Particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions. Index Terms--ALOHA, capacity, multipacket reception (MPR), positive correlation, stability.

This paper extends our earlier results. We assume that the receiver has the capability of capturing multiple packets so long as the signal-to-interference-plus-noise ratio (SINR) of each packet is above a designed threshold T throughout its transmission period. We prove that, compared with a multiple-power-level system, the single-power-level system in which all nodes transmit at the maximum allowable power level achieves optimal throughput, under a condition that T exceeds the value 3.33. Given a minimum throughput requirement, under the same condition on T, the single-power-level system also achieves the maximum average packet capture probability as well as the optimum energy usage efficiency. If the multiple-power-level systems are constrained such that higher power levels always have shorter packet lengths, then the above results hold for T greater than 2. Index Terms--ALOHA, energy efficiency, power capture, random multiple access.

The optimal signature sequences that maximize the sum capacity of a direct sequence code-division multiple-access (CDMA) system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints. Index Terms--Asynchronous code-division multiple access (CDMA), CDMA, optimal signature sequences, sum capacity.

In the presence of channel fluctuation, rate adaptation is one way to maintain the quality of the link at a desired level. This is especially important in ad hoc wireless networks, where temporary channel fluctuations might create frequent needs for rerouting that would result in severe overhead and adversely affect the performance. We study an unusual method of passive rate adaptation in which some bits are dropped at the receiver end of a link. The symbol-error probability decreases as some bits are dropped. In terms of the distortion for a realtime analog signal, the tradeoff is between more reliable detection of fewer bits and less reliable detection of more bits. Our scheme achieves smaller distortion for a certain region of signal-to-noise ratio (SNR) values when compared with the original scheme without rate adaptation. Two examples, uniformly spaced, uncoded pulse amplitude modulation and quadrature amplitude modulation, are studied and compared for both a Gaussian channel and a Rayleigh fading channel. We conclude that our scheme is more suitable to use in a fading channel than in a Gaussian channel. We also verify that our scheme has a larger applicable region of SNR values when a nonuniform constellation is used, since the important bits are given additional protection. Index Terms--Distortion, fading channels, pulse amplitude modulation (PAM), quadrature amplitude modulation (QAM), quantization.

In an energy-efficient wireless communication system, transmit powers are minimized subject to predetermined signal-to-interference ratio (SIR) requirements. In this paper, a general framework for distributed stochastic power control (PC) algorithms is proposed, where the transmit powers are updated based on stochastic approximations. The proposed algorithms are distributed in the sense that no global information is needed in the power updates. Interference to each user is estimated locally via noisy observations. Two types of stochastic PC algorithms are studied: standard stochastic PC algorithms where the interference estimator is unbiased, and quasi-standard stochastic PC algorithms where the interference estimator is biased. The conditions under which the stochastic PC algorithms converge to the unique optimal solution are identified. Corresponding to two classes of iteration step-size sequences, two types of convergence, the probability one convergence and convergence in probability, are shown for both algorithms based on recent results in the stochastic approximation literature. Based on the theoretical results, some well-known stochastic PC algorithms, such as stochastic PC with matched filter receivers, and joint stochastic PC with blind minimum mean-squared error (MMSE) interference suppression, are revisited; several new stochastic PC algorithms, such as stochastic PC with minimum-power base-station assignment, and stochastic PC with limited diversity, are proposed. It is shown that these algorithms fall into either the standard or the quasi-standard stochastic PC framework. Simulation results are given to illustrate the performance of the proposed algorithms in practical systems. Index Terms--Distributed algorithms, stochastic approximation, stochastic power control.

In this paper, we consider a synchronous code-division multiple-access (CDMA) system with a multiuser receiver. All users are assumed to have symmetric signature sequences, but the presence of a subset of the users is unknown to the receiver. We first calculate the signal-to-interference ratio (SIR) in this environment for the matched-filter receiver, the decorrelating receiver, and the linear minimum mean-square error (MMSE) detector. We then identify the user capacity for a single-class system, and the effective bandwidth for a multiple-class system. The result is compared to the case of random sequences and of optimum sequences. For symmetric sequences, the effective bandwidth cannot be expressed by a scalar as in [9], because two constraints have to be satisfied simultaneously to satisfy the SIR requirement. We introduce a two-dimensional (2-D) vector notion of effective bandwidth with and without unknown users. For both the decorrelator and the MMSE detector, the user capacity is 1 when all users are known to the receivers and is reduced to (1 - N/L) when N users are unknown (with L the processing gain). The performance of these three linear detectors, with and without unknown users, is compared. Index Terms--Code-division multiple access (CDMA), effective bandwidth, multiuser detection, power control, user capacity.

In this paper, we address the issue of performance of linear multiuser detectors for a multicasting application in an ad hoc wireless network. Using a code-division multiple-access (CDMA) framework, we demonstrate how capacity results for multiuser detectors can be adapted to do session admission control for the multicasting problem. We then develop a multicast routing algorithm for ad hoc wireless networks. Using the session admission control mechanism and the multicast routing algorithm, we evaluate the performance of three different linear multiuser detectors for the multicasting application. Index Terms--Admission control, capacity of linear detectors, code-division multiple access (CDMA), multicasting, multiuser detection, power control, routing.

Nonlinear optimization under nonlinear constraints is usually difficult. However, standard ad-hoc search techniques may work successfully in some cases. Here, we consider an augmented Lagrangian formulation, and we develop a "projection heuristic" that "guides" the iterative search toward the optimum. We demonstrate the effectiveness of this approach by applying it to the problem of maximizing a circuit-switched communication network's throughput under quality-of-service (QoS) constraints by means of choosing the input offered load. This problem is useful for "sizing" the network capacity. Performance results using several versions of the algorithm demonstrate its robustness, in terms of its accuracy and convergence properties. Index Terms--Admission control, communication network, optimization, performance evaluation, quality-of-service (QoS).

Multiple-power-level ALOHA has been proposed to take advantage of the capture phenomenon in order to improve the throughput of a multiple random access system. In this paper, we study the effect of the use of multiple transmission power levels and of the corresponding packet lengths on the system throughput and energy efficiency. We prove that the single-power-level system in which all transmit at the maximum allowable power level achieves both optimal throughput and energy usage efficiency under a condition on the decodability threshold value. Index Terms--ALOHA, capture, energy efficiency, random access.

We revisit the stability problem of systems consisting of N buffered terminals accessing a common receiver over the collision channel by means of the standard ALOHA protocol. We find that in the slotted ALOHA system queues have "instability rank" based on their individual average arrival rates and transmission probabilities. If a queue is stable, then the queue with lower instability rank is stable as well. The instability rank is used to intelligently set up the dominant systems. And the stability inner and outer bounds can be found by bounding the idle probability of some queues in the dominant system. Through analyzing those dominant systems one by one, we are able to obtain inner and outer bounds for stability. These bounds are tighter than the known ones although they still fail to identify the exact stability region for cases of N > 2. The methodology used is new and holds promise for successfully addressing other similar stability problems. Index Terms - Interacting queues, multiple access, slotted ALOHA, stability analysis.

Information theory has not yet had a direct impact on networking, although there are similarities in concepts and methodologies that have consistently attracted the attention of researchers from both fields. In this paper, we review several topics that are related to communication networks and that have an information-theoretic flavor, including multiaccess protocols, timing channels, effective bandwidth of bursty data sources, deterministic constraints on datastreams, queuing theory, and switching networks. Index Terms - Communication networks, effective bandwidth, multiaccess, switching.

In this correspondence, we identify a class of optimum multiuser detection problems which can be solved with polynomial complexity in the number of users. The identification is based on transforming a quadratic 0-1 programming problem into an equivalent problem in graph theory. For a synchronous direct sequence code-division multiple access (CDMA) system, the result translates to designing a set of pseudorandom codes with the property that the cross correlation between every pair of codes in the set over one symbol period is nonpositive. We give two sets of codes with good correlation properties that fall within this class. Finally, we derive a bound on the cardinality of a signal set in an n-dimensional space, having the property that the cross correlation between every pair of signals in the set is nonpositive. Index Terms - CDMA, Gold sequence, min cut, m-sequence, multiuser detection, polynomial complexity.

We develop an approach to the analysis of average queueing delay in a tree network of discrete-time queues with constant service time. The analysis of such systems is pertinent to packet-switched data networks with fixed-length packets. Our solution is based on considering an equivalent network, in which at each node packets in transit are given priority over exogenous arrivals. The solution to the equivalent model is easily computed, and, hence, the solution to the original model can be obtained. Index Terms - Queueing networks, tandem queue, queueing delay, equivalent model, priority disciplines.

We address the problem of 'link activation' or 'scheduling' in multihop packet radio networks.The objective is to determine a conflict-free schedule of minimum length that satisfies the specified end-to-end communication requirements. It is well known that this problem, in almost all of its forms, is a combinatorial-optimization problem of high complexity. We approach this problem by the use of a Hopfield neural network model in which the method of Lagrange multipliers is used to vary dynamically the values of the coefficients used in the connection weights.

In this paper we address the major issues associated with channel access in integrated wireless networks, and we propose and analyze the 'Wireless Integrated Multiple Access' (WIMA) protocol. This scheme is based on a mixture of boundary ideas for integration and of previously introduced protocols for wireless access, and is well suited to either satellite or to terrestrial networks. A two-dimensional first-order Markov chain model for this scheme is presented, and techniques that exploit the structural properties of this chain to simplify the evaluation of the equilibrium state, without sacrificing accuracy, are described. Analytical models for the evaluation of data-packet delay for both fixed- and movable-boundary versions of this protocol and for voice-call blocking probability are presented. Performance results illustrate the dependence of performance on system parameters, and demonstrate the improved performance that can be achieved through the use of the movable-boundary version.

The issues of routing and scheduling the activation of links in packet radio networks are highly interdependent. In this paper, we consider a form of the problem of routing for the minimization of congestion as a step toward the study of the joint routing-scheduling problem. We formulate this as a combinatorial-optimization problem, and we use Hopfield neural networks (NN) for its solution. The determination of the coefficients in the connection weights is the most critical issue in the design and simulation of Hopfield NN models. In our studies, we use the method of Lagrange multipliers, which permits these coefficients to vary dynamically along with the evolution of the system state. Extensive software simulation results demonstrate the capability of our approach to determine good sets of routes in large heavily congested networks.

Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. The server is allocated to one of the connected queues at each slot; the allocation decision is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology (radio networks with mobile users, or networks with variable links such as meteor-burst communication channels). In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues (i.e., queues with equal arrival, service, and connectivity statistics) is provided. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical.

The stability of a queueing network with interdependent servers is considered. The dependency of servers is described by the definition of their subsets that can be activated simultaneously. Multihop packet radio networks (PRN's) provide a motivation for the consideration of this system. We study the problem of scheduling the server activation under the constraints imposed by the dependency among them. The performance criterion of a scheduling policy phi is its throughput that is characterized by its stability region C(sub phi), that is, the set of vectors of arrival rates for which the system is stable. A policy phi(sub 0) is obtained which is optimal in the sense that its stability region C(sub phi(sub 0)) is a superset of the stability region of every other scheduling policy. The stability region C(sub phi(sub 0)) is characterized. Finally, we study the behavior of the network for arrival rates that lie outside the stability region. Implications of the results in certain types of concurrent database and parallel processing systems are discussed.

A simple model of distributed computation that requires information exchange over a noisy channel is considered. A communication protocol is utilized that requires alternate bit exchanges between two processors. Interest in determining the communication complexity of this exchange is also shown. First, the case of a single public channel is considered and the number of bits that need to be exchanged between the processors to permit [Delta]-accuracy in their goal is computed. For this computation, an error-detection-and-retransmission mechanism of error control, as well as an error-correction-and-retransmission mixture that are consistent with the logical protocol that governs this exchange are considered. Second, the case of the availability of an additional secret channel is considered and interest in determining the minimum number of bits that need to be exchanged over a secret channel in order to maintain [Epsilon]-uncertainty about the computation for an eavesdropper on the public channel is shown. Various subcases under this case are considered and an upper bound on the number of secret bits when no error-control scheme is used is obtained. Index Terms--Distributed computation, communication complexity, secrecy, error control, protocol security.

The problem of scheduling time-critical messages over a tree network is considered. Messages arrive at any of the nodes and have to reach the root node before their deadlines expire, else they are considered lost. The network is assumed to be operating in discrete time and the messages need one time unit for transmission from one node to the next along its path. The arrival and deadline processes are arbitrary. The policy which transmits messages with smallest extinction (arrival + deadline) time at every link is shown to minimize the number of lost messages over all time intervals and for every sample path. Index Terms - Optimal scheduling, real time communications, tree networks.

Suppose that the description of a stochastic process needs to be sent to a destination through a communication network. Also assume there is a risk that the description may be lost. A technique to reduce the risk of losing such descriptions is by sending two (or more) descriptions and hoping that in this way at least one of the descriptions will get through. This problem is referred to as multiple description coding (MDC) and was first introduced at the September 1979 IEEE Information Theory Workshop by Gersho, Witsenhausen, Wolf, Wyner, Ziv, and Ozarow. So far, the main focus of research on this subject has been on the achievable rate-distortion functions and the related structural design issues for such encoders and decoders. Little effort has focused on the performance of such coding schemes in simple communication networks and relation of the overall distortion with respect to some network parameter such as congestion. In this paper, a double description coding (DDC) system in a simple network represented by a set of parallel queues is studied. Comparison is made with a single description coding system and it is shown that DDC significantly improves the overall average end-to-end distortion at high network loading. Index Terms--Delay-sensitive sources, multiple description coding (MDC), network congestion, queueing systems, rate-distortion performance, signal-to-noise ratio (SNR).

In this paper, we provide a graph-based characterization of the set of indecomposable sequences that are useful in the computation of an upper bound to error probability of maximum-likelihood (ML) detection in code-division multiple-access (CDMA) multiuser systems. We apply this characterization to a K-user symmetric system and to a two-user two-rate system. It leads to a precise calculation of the bound which is then compared to the performance of a decorrelator. Index Terms--Code-division multiple access (CDMA), error probability, error sequences, multiuser detection.