Dynamic power allocation and routing for time-varying wireless networks

We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support-where /spl lambda//sub ij/ represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002).     

Power allocation and routing in multibeam satellites with time-varying channels

We consider power and server allocation in a multibeam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues and the server rate for each queue, i, depends on the power, p/sub i/(t), allocated to that server and the channel state, c/sub i/(t), according to a concave rate-power curve /spl mu//sub i/(p/sub i/,c/sub i/). We establish the capacity region of all arrival rate vectors (/spl lambda//sub 1/,...,/spl lambda//sub N/) which admit a stabilizable system. We then develop a power-allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. Furthermore, the algorithm is shown to be robust to arbitrary variations in the input rates and a bound on average delay is established. As a special case, this analysis verifies stability and provides a performance bound for the choose-the-K-largest-connected-queues policy when channels can be in one of two states (ON or OFF ) and K servers are allocated at every timestep (K相似文献   

A deterministic approach to throughput scaling in wireless networks

We address the problem of how throughput in a wireless network scales as the number of users grows. Following the model of Gupta and Kumar, we consider n identical nodes placed in a fixed area. Pairs of transmitters and receivers wish to communicate but are subject to interference from other nodes. Throughput is measured in bit-meters per second. We provide a very elementary deterministic approach that gives achievability results in terms of three key properties of the node locations. As a special case, we obtain /spl Omega/(/spl radic/n) throughput for a general class of network configurations in a fixed area. Results for random node locations in a fixed area can also be derived as special cases of the general result by verifying the growth rate of three parameters. For example, as a simple corollary of our result we obtain a stronger (almost sure) version of the /spl radic/n//spl radic/(logn) throughput for random node locations in a fixed area obtained by Gupta and Kumar. Results for some other interesting non-independent and identically distributed (i.i.d.) node distributions are also provided.     

Optimal throughput-delay scaling in wireless networks - part I: the fluid model

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is /spl Theta/(1//spl radic/(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=/spl Theta/(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of /spl Theta/(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be /spl Theta/(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of /spl Oscr/(1//spl radic/(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=/spl Theta/(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be /spl Theta/(nlogn), which is the delay for throughput of /spl Theta/(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.     

A new design for wide-sense nonblocking multicast switching networks

In this paper, we propose a new design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N/spl times/N multicast network, its hardware cost, in terms of the number of crosspoints, is about 2(3+2/spl radic/2)N/sup 3/2/=11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(N/sup 3/2/(logN/loglogN)) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sublinear time complexity, and does not require multicast capability for the switch modules in the input stage.     

Capacity of ad hoc wireless networks with infrastructure support

We determine the asymptotic scaling for the per user throughput in a large hybrid ad hoc network, i.e., a network with both ad hoc nodes, which communicate with each other via shared wireless links of capacity W bits/s, and infrastructure nodes which in addition are interconnected with each other via high capacity links. Specifically, we consider a network model where ad hoc nodes are randomly spatially distributed and choose to communicate with a random destination. We identify three scaling regimes, depending on the growth of the number of infrastructure nodes, m relative to the number of ad hoc nodes n, and show the asymptotic scaling for the per user throughput as n becomes large. We show that when m /spl lsim/ /spl radic/n/logn the per user throughput is of order W//spl radic/n log n and could be realized by allowing only ad hoc communications, i.e., not deploying the infrastructure nodes at all. Whenever /spl radic/n/log n /spl lsim/ m /spl lsim/ n/log n, the order for the per user throughput is Wm/n and, thus, the total additional bandwidth provided by m infrastructure nodes is effectively shared among ad hoc nodes. Finally, whenever m /spl gsim/ n/log n, the order of the per user throughput is only W/log n, suggesting that further investments in infrastructure nodes will not lead to improvement in throughput. The results are shown through an upper bound which is independent of the routing strategy, and by constructing scenarios showing that the upper bound is asymptotically tight.     

Cluster overlay broadcast (COB): MANET routing with complexity polynomial in source-destination distance

Routing algorithms with time and message complexities that are provably low and independent of the total number of nodes in the network are essential for the design and operation of very large scale wireless mobile ad hoc networks (MANETs). In this paper, we develop and analyze Cluster Overlay Broadcast (COB), a low-complexity routing algorithm for MANETs. COB runs on top of a one-hop cluster cover of the network, which can be created and maintained using, for instance, the Least Cluster Change (LCC) algorithm. We formally prove that the LCC algorithm maintains a cluster cover with a constant density of cluster leaders with minimal update cost. COB discovers routes by flooding (broadcasting) route requests through the network of cluster leaders with a doubling radius technique. Building on the constant density property of the network of cluster leaders, we formally prove that, if there exists a route from a source to a destination node with a minimum hop count of A, then COB discovers a route with at most O(/spl Delta/) hops from the source to the destination node in at most O(/spl Delta/) time and by sending at Most O(/spl Delta//sup 2/) messages. We prove this result for arbitrary node distributions and mobility patterns and also show that COB adapts asymptotically optimally to the mobility of the nodes. In our simulation experiments, we examine the network layer performance of COB, compare it with Dynamic Source Routing, and investigate the impact of the MAC layer on COB routing.     

New asymptotic bounds for self-dual codes and lattices

We give an independent proof of the Krasikov-Litsyn bound d/n/spl lsim/(1-5/sup -1/4/)/2 on doubly-even self-dual binary codes. The technique used (a refinement of the Mallows-Odlyzko-Sloane approach) extends easily to other families of self-dual codes, modular lattices, and quantum codes; in particular, we show that the Krasikov-Litsyn bound applies to singly-even binary codes, and obtain an analogous bound for unimodular lattices. We also show that in each case, our bound differs from the true optimum by an amount growing faster than O(/spl radic/n).     

Fast Fourier transform for discontinuous functions

In computational electromagnetics and other areas of computational science and engineering, Fourier transforms of discontinuous functions are often required. We present a fast algorithm for the evaluation of the Fourier transform of piecewise smooth functions with uniformly or nonuniformly sampled data by using a double interpolation procedure combined with the fast Fourier transform (FFT) algorithm. We call this the discontinuous FFT algorithm. For N sample points, the complexity of the algorithm is O(/spl nu/Np+/spl nu/Nlog(N)) where p is the interpolation order and /spl nu/ is the oversampling factor. The method also provides a new nonuniform FFT algorithm for continuous functions. Numerical experiments demonstrate the high efficiency and accuracy of this discontinuous FFT algorithm.     

Communication over a wireless network with random connections

A network of nodes in which pairs communicate over a shared wireless medium is analyzed. We consider the maximum total aggregate traffic flow possible as given by the number of users multiplied by their data rate. The model in this paper differs substantially from the many existing approaches in that the channel connections in this network are entirely random: rather than being governed by geometry and a decay-versus-distance law, the strengths of the connections between nodes are drawn independently from a common distribution. Such a model is appropriate for environments where the first-order effect that governs the signal strength at a receiving node is a random event (such as the existence of an obstacle), rather than the distance from the transmitter. It is shown that the aggregate traffic flow as a function of the number of nodes n is a strong function of the channel distribution. In particular, for certain distributions the aggregate traffic flow is at least n/(logn)/sup d/ for some d>0, which is significantly larger than the O(/spl radic/n) results obtained for many geometric models. The results provide guidelines for the connectivity that is needed for large aggregate traffic. The relation between the proposed model and existing distance-based models is shown in some cases.     

Grammar-based lossless universal refinement source coding

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).     

Scheduling satellite-switched time-division multiple access with general switching modes

Based on network circulation formulation, the existence of feasible beam-to-beam switching modes for a satellite-switched time-division multiple access system is completely and transparently proved, where simultaneous transmissions on several carriers in each spot-beam are configured. Showing the linear independence of all but one augmented switching modes, a new bound of mn+2 is obtained on the number of switching modes, where m and n are the number of up-link and down-link beams, respectively. The time complexity for finding the whole sequence of switching modes and for finding the initial switching mode are improved to O(m/sup 2/n/sup 2/) and O(min(/spl radic/K,(m+n)/sup 2/3/)mn), respectively. Practical implementation considerations are discussed.     

Efficient adaptive algorithms and minimax bounds for zero-delay lossy source coding

Zero-delay lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, which is defined as the difference between the normalized cumulative mean squared distortion of the scheme and the normalized cumulative distortion of the best scalar quantizer of the same rate that is matched to the entire sequence to be encoded. By improving and generalizing a scheme of Linder and Lugosi, Weissman and Merhav showed the existence of a randomized scheme that, for any bounded individual sequence of length n, achieves a distortion redundancy O(n/sup -1/3/logn). However, both schemes have prohibitive complexity (both space and time), which makes practical implementation infeasible. In this paper, we present an algorithm that computes Weissman and Merhav's scheme efficiently. In particular, we introduce an algorithm with encoding complexity O(n/sup 4/3/) and distortion redundancy O(n/sup -1/3/logn). The complexity can be made linear in the sequence length n at the price of increasing the distortion redundancy to O(n/sup -1/4//spl radic/logn). We also consider the problem of minimax distortion redundancy in zero-delay lossy coding of random sources. By introducing a simplistic scheme and proving a lower bound, we show that for the class of bounded memoryless sources, the minimax expected distortion redundancy is upper and lower bounded by constant multiples of n/sup -1/2/.     

Capacity and lattice strategies for canceling known interference

We consider the generalized dirty-paper channel Y=X+S+N,E{X/sup 2/}/spl les/P/sub X/, where N is not necessarily Gaussian, and the interference S is known causally or noncausally to the transmitter. We derive worst case capacity formulas and strategies for "strong" or arbitrarily varying interference. In the causal side information (SI) case, we develop a capacity formula based on minimum noise entropy strategies. We then show that strategies associated with entropy-constrained quantizers provide lower and upper bounds on the capacity. At high signal-to-noise ratio (SNR) conditions, i.e., if N is weak relative to the power constraint P/sub X/, these bounds coincide, the optimum strategies take the form of scalar lattice quantizers, and the capacity loss due to not having S at the receiver is shown to be exactly the "shaping gain" 1/2log(2/spl pi/e/12)/spl ap/ 0.254 bit. We extend the schemes to obtain achievable rates at any SNR and to noncausal SI, by incorporating minimum mean-squared error (MMSE) scaling, and by using k-dimensional lattices. For Gaussian N, the capacity loss of this scheme is upper-bounded by 1/2log2/spl pi/eG(/spl Lambda/), where G(/spl Lambda/) is the normalized second moment of the lattice. With a proper choice of lattice, the loss goes to zero as the dimension k goes to infinity, in agreement with the results of Costa. These results provide an information-theoretic framework for the study of common communication problems such as precoding for intersymbol interference (ISI) channels and broadcast channels.     

The inequalities of quantum information theory

Let /spl rho/ denote the density matrix of a quantum state having n parts 1, ..., n. For I/spl sube/N={1, ..., n}, let /spl rho//sub I/=Tr/sub N/spl bsol/I/(/spl rho/) denote the density matrix of the state comprising those parts i such that i/spl isin/I, and let S(/spl rho//sub I/) denote the von Neumann (1927) entropy of the state /spl rho//sub I/. The collection of /spl nu/=2/sup n/ numbers {S(/spl rho//sub I/)}/sub I/spl sube/N/ may be regarded as a point, called the allocation of entropy for /spl rho/, in the vector space R/sup /spl nu//. Let A/sub n/ denote the set of points in R/sup /spl nu// that are allocations of entropy for n-part quantum states. We show that A~/sub n/~ (the topological closure of A/sub n/) is a closed convex cone in R/sup /spl nu//. This implies that the approximate achievability of a point as an allocation of entropy is determined by the linear inequalities that it satisfies. Lieb and Ruskai (1973) have established a number of inequalities for multipartite quantum states (strong subadditivity and weak monotonicity). We give a finite set of instances of these inequalities that is complete (in the sense that any valid linear inequality for allocations of entropy can be deduced from them by taking positive linear combinations) and independent (in the sense that none of them can be deduced from the others by taking positive linear combinations). Let B/sub n/ denote the polyhedral cone in R/sup /spl nu// determined by these inequalities. We show that A~/sub n/~=B/sub n/ for n/spl les/3. The status of this equality is open for n/spl ges/4. We also consider a symmetric version of this situation, in which S(/spl rho//sub I/) depends on I only through the number i=/spl ne/I of indexes in I and can thus be denoted S(/spl rho//sub i/). In this case, we give for each n a finite complete and independent set of inequalities governing the symmetric allocations of entropy {S(/spl rho//sub i/)}/sub 0/spl les/i/spl les/n/ in R/sup n+1/.     

On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks

We develop on-line routing and wavelength assignment (RWA) algorithms for WDM bidirectional ring and torus networks with N nodes. The algorithms dynamically support all k-allowable traffic matrices, where k denotes an arbitrary integer vector [k/sub 1/, k/sub 2/,... k/sub N/], and node i, 1 /spl les/ i /spl les/ N, can transmit at most k/sub i/ wavelengths and receive at most k/sub i/ wavelengths. Both algorithms support the changing traffic in a rearrangeably nonblocking fashion. Our first algorithm, for a bidirectional ring, uses [(/spl Sigma//sub i=1//sup N/ k/sub i/)/3] wavelengths in each fiber and requires at most three lightpath rearrangements per new session request regardless of the number of nodes N and the amount of traffic k. When all the k/sub i/'s are equal to k, the algorithm uses [kN/3] wavelengths, which is known to be the minimum for any off-line rearrangeably nonblocking algorithm. Our second algorithm, for a torus topology, is an extension of a known off-line algorithm for the special case with all the k/sub i/'s equal to k. For an R /spl times/ C torus network with R /spl ges/ C nodes, our on-line algorithm uses [kR/2] wavelengths in each fiber, which is the same as in the off-line algorithm, and is at most two times a lower bound obtained by assuming full wavelength conversion at all nodes. In addition, the on-line algorithm requires at most C - 1 lightpath rearrangements per new session request regardless of the amount of traffic k. Finally, each RWA update requires solving a bipartite matching problem whose time complexity is only O (R), which is much smaller than the time complexity O(kCR/sup 2/) of the bipartite matching problem for an off-line algorithm.     

Efficient source decoding over memoryless noisy channels using higher order Markov models

Exploiting the residual redundancy in a source coder output stream during the decoding process has been proven to be a bandwidth-efficient way to combat noisy channel degradations. This redundancy can be employed to either assist the channel decoder for improved performance or design better source decoders. In this work, a family of solutions for the asymptotically optimum minimum mean-squared error (MMSE) reconstruction of a source over memoryless noisy channels is presented when the redundancy in the source encoder output stream is exploited in the form of a /spl gamma/-order Markov model (/spl gamma//spl ges/1) and a delay of /spl delta/,/spl delta/>0, is allowed in the decoding process. It is demonstrated that the proposed solutions provide a wealth of tradeoffs between computational complexity and the memory requirements. A simplified MMSE decoder which is optimized to minimize the computational complexity is also presented. Considering the same problem setup, several other maximum a posteriori probability (MAP) symbol and sequence decoders are presented as well. Numerical results are presented which demonstrate the efficiency of the proposed algorithms.     

Asymptotic behavior of the pairwise error probability with applications to transmit beamforming and rake receivers

We derive the precise asymptote of the pairwise error probability for high signal-to-noise ratio (SNR) and apply it to obtain new results concerning transmit beamforming and selective Rake receivers. For downlink beamforming (with N transmit antennas and independently identically distributed (i.i.d.) Rayleigh fading) based on quantized feedback from the mobile, we show that at least /spl lceil/log/sub 2/(N)/spl rceil/ bits of feedback (per coherence time) is required to obtain full diversity, and among all beamforming schemes using /spl lceil/log/sub 2/(N)/spl rceil/ bits of feedback, selection diversity is optimal. We give the exact expression for the SNR loss of selection diversity with respect to ideal beamforming based on perfect knowledge of fading coefficients. Further, we study selective Rake receivers for independent arbitrary fading distribution and arbitrary power delay profile (PDP). In particular, we show that the SNR loss of the SRake receiver with respect to the all-Rake receiver does not depend on the PDP, and we also propose a transformation to adapt the expressions known for the symbol error probability for the case of i.i.d. Rayleigh fading to the general case.     

Digital fingerprinting codes: problem statements, constructions, identification of traitors

We consider a general fingerprinting problem of digital data under which coalitions of users can alter or erase some bits in their copies in order to create an illegal copy. Each user is assigned a fingerprint which is a word in a fingerprinting code of size M (the total number of users) and length n. We present binary fingerprinting codes secure against size-t coalitions which enable the distributor (decoder) to recover at least one of the users from the coalition with probability of error exp(-/spl Omega/(n)) for M=exp(/spl Omega/(n)). This is an improvement over the best known schemes that provide the error probability no better than exp(-/spl Omega/(n/sup 1/2/)) and for this probability support at most exp(O(n/sup 1/2/)) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n)=polylog(M), improving over the best previously known complexity of /spl Omega/(M). For the case t=2, we construct codes of exponential size with even stronger performance, namely, for which the distributor can either recover both users from the coalition with probability 1-exp(/spl Omega/(n)), or identify one traitor with probability 1.