Dynamic server allocation to parallel queues with randomly varyingconnectivity

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. Allocation at each slot; 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. 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. 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     

Push forward link-level scheduling for network-wide performance

A virtual circuit network with arbitrary topology is considered. The traffic streams follow prespecified routes, different in general for each stream, to reach their destination. A fluid traffic model is adopted and a processor sharing service discipline is considered. A policy is proposed for setting adaptively the fractions of the transmission capacity, which is allocated to the different traffic streams in the processor sharing discipline at each link. The amount of traffic arrived at the originating node of each link is measured for each stream. The fraction of the link capacity allocated to each stream is set to be proportional to the measured traffic. The traffic is measured continuously and the fractions are updated regularly based on the most recent traffic measurements. It is shown that eventually, the transmission capacity allocated to each stream converges to a quantity proportional to the average rate of the stream. Hence, if the capacity condition is satisfied, sufficient fractions of the capacity are allocated at each link for each stream. End-to-end performance guarantees are provided, if the traffic is regulated. The policy is distributed since each link adjusts the service fractions based on observations of the traffic arriving at its originating node only. Furthermore, it is adaptive since no information on the traffic characteristics is needed for the application of the policy     

Joint Optimal Access Point Selection and Channel Assignment in Wireless Networks

In wireless cellular networks or in other networks with single-hop communication, the fundamental access control problem pertains to access point (AP) selection and channel allocation for each user. For users in the coverage area of one AP, this involves only channel allocation. However, users that belong in the intersection of coverage areas of more than one AP can select the appropriate AP to establish connection and implicitly affect the channel assignment procedure. We address the joint problem of AP selection and channel assignment with the objective to satisfy a given user load vector with the minimum number of channels. Our major finding is that the joint problem reduces to plain channel allocation in a cellular network that emerges from the original one after executing an iterative and provably convergent clique load balancing algorithm. For linear cellular networks, our approach leads to minimum number of required channels to serve a given load vector. For 2D cellular networks, the same approach leads to a heuristic algorithm with a suboptimal solution due to the fact that clique loads cannot be balanced. Numerical results demonstrate the performance benefits of our approach in terms of blocking probability in a dynamic scenario with time-varying number of connection requests. The presented approach constitutes the basis for addressing more composite resource allocation problems in different context.     

Efficient resource utilization through carrier grouping forhalf-duplex communication in GSM-based MEO mobile satellitenetworks

In the near future, existing terrestrial radio networks are envisioned to integrate with satellite systems in order to provide global coverage. In order to establish communication for both nonhand-held and hand-held user terminals, the radio link design must allow full- and half-duplex operation, respectively, where the latter is desirable when radiation power restrictions are imposed. In addition, due to user mobility and wireless channel volatility, sophisticated resource management is required, so as to enhance system capacity. However, a major inherent problem of the satellite link is propagation delay, which may lead to inefficient resource allocation and reduced spectral efficiency. We address the resource allocation problem that arises in the context of a medium-Earth-orbit (MEO) satellite system with half-duplex communication capabilities. MEO satellite systems are characterized by large propagation delays and large intrabeam delay variations, which are shown to result in resource consumption. We propose a channel classification scheme, in which the available carriers are partitioned into classes and each class is associated with a range of propagation delays to the satellite. The suggested infrastructure results in better channel utilization and reduced call blocking rate and can be implemented with low signaling load     

Transmit beamforming and power control for cellular wirelesssystems

Joint power control and beamforming schemes are proposed for cellular systems where adaptive arrays are used only at base stations. In the uplink, mobile power and receiver diversity combining vectors at the base stations are calculated jointly. The mobile transmitted power is minimized, while the signal-to-interference-and-noise ratio (SINR) at each link is maintained above a threshold. A transmit diversity scheme for the downlink is also proposed where the transmit weight vectors and downlink power allocations are jointly calculated such that the SINR at each mobile is above a target value. The proposed algorithm achieves a feasible solution for the downlink if there is one and minimizes the total transmitted power in the network. In a reciprocal network it can be implemented in a decentralized system, and it does not require global channel response measurements. In a nonreciprocal network, where the uplink and downlink channel responses are different, the proposed transmit beamforming algorithm needs to be implemented in a centralized system, and it requires a knowledge of the downlink channel responses. The performances of these algorithms are compared with previously proposed algorithms through numerical studies     

Comparative study of various TCP versions over a wireless link with correlated losses

We investigate the behavior of the various transmission control protocol (TCP) algorithms over wireless links with correlated packet losses. For such a scenario, we show that the performance of NewReno is worse than the performance of Tahoe in many situations and even OldTahoe in a few situations because of the inefficient fast recovery method of NewReno. We also show that random loss leads to significant throughput deterioration when either the product of the square of the bandwidth-delay ratio and the loss probability when in the good state exceeds one, or the product of the bandwidth-delay ratio and the packet success probability when in the bad state is less than two. The performance of Sack is always seen to be the best and the most robust, thereby arguing for the implementation of TCP-Sack over the wireless channel. We also show that, under certain conditions, the performance depends not only on the bandwidth-delay product but also on the nature of timeout, coarse or fine. We have also investigated the effects of reducing the fast retransmit threshold.     

Throughput Scalability of Wireless Hybrid Networks over a Random Geometric Graph

In this paper, we consider the transport capacity of ad hoc networks with a random flat topology under the present support of an infinite capacity infrastructure network. Such a network architecture allows ad hoc nodes to communicate with each other by purely using the remaining ad hoc nodes as their relays. In addition, ad hoc nodes can also utilize the existing infrastructure fully or partially by reaching any access point (or gateway) of the infrastructure network in a single or multi-hop fashion. Using the same tools as in [9], we show that the per source node capacity of Θ(W/log(N)) can be achieved in a random network scenario with the following assumptions: (i) The number of ad hoc nodes per access point is bounded above, (ii) each wireless node, including the access points, is able to transmit at W bits/sec using a fixed transmission range, and (iii) N ad hoc nodes, excluding the access points, constitute a connected topology graph. This is a significant improvement over the capacity of random ad hoc networks with no infrastructure support which is found as in [9]. We also show that even when less stringent requirements are imposed on topology connectivity, a per source node capacity figure that is arbitrarily close to Θ(1) cannot be obtained. Nevertheless, under these weak conditions, we can further improve per node throughput significantly. We also provide a limited extension on our results when the number of ad hoc nodes per access point is not bounded.Ulaş C. Kozat was born in 1975, in Adana, Turkey. He received his B.Sc. degree in Electrical and Electronics Engineering from Bilkent University, Ankara, Turkey and his M.Sc. in Electrical Engineering from The George Washington University, Washington D.C. in 1997 and 1999 respectively. He has received his Ph.D. degree in May 2004 from the Department of Electrical and Computer Engineering at University of Maryland, College Park. He has conducted research under the Institute for Systems Research (ISR) and Center for Hybrid and Satellite Networks (CSHCN) at the same university. He worked at HRL Laboratories and Telcordia Technologies Applied Research as a research intern. His current research interests primarily focus on wireless and hybrid networks that span multiple communication layers and networking technologies. Mathematical modelling, resource discovery and allocation, vertical integration of wireless systems and communication layers, performance analysis, architecture and protocol development are the main emphasis of his work. E-mail: kozat@isr.umd.eduLeandros Tassiulas (S′89, M′91) was born in 1965, in Katerini, Greece. He obtained the Diploma in Electrical Engineering from the Aristotelian University of Thessaloniki, Thessaloniki, Greece in 1987, and the M.S. and Ph.D. degrees in Electrical Engineering from the University of Maryland, College Park in 1989 and 1991 respectively.He is Professor in the Dept. of Computer and Telecommunications Engineering, University of Thessaly, Greece and Research Professor in the Dept. of Electrical and Computer Eng and the Institute for Systems Research, University of Maryland College Park since 2001. He has held positions as Assistant Professor at Polytechnic University New York (1991–95), Assistant and Associate Professor University of Maryland College Park (1995–2001) and Professor University of Ioannina Greece (1999–2001).His research interests are in the field of computer and communication networks with emphasis on fundamental mathematical models, architectures and protocols of wireless systems, sensor networks, high-speed internet and satellite communications.Dr. Tassiulas received a National Science Foundation (NSF) Research Initiation Award in 1992, an NSF CAREER Award in 1995 an Office of Naval Research, Young Investigator Award in 1997 and a Bodosaki Foundation award in 1999 and the INFOCOM′94 best paper award. E-mail: leandros@isr.umd.edu     

A scheduling policy with maximal stability region for ring networks with spatial reuse

A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring withspatial reuse. It can achieve significantly higher throughput than standard token rings but it also raises the issue of fairness since some nodes may be prevented from accessing the ring for long time intervals. Policies that operate in cycles and guarantee that a certain number (quota) of packets will be transmitted by every node in every cycle have been considered before to deal with the fairness issue. In this paper we address the problem of designing a policy that results in a stable system whenever the end-to-end arrival rates are within the stability region of the ring with spatial reuse (the stability region of the ring is defined as the set of end-to-end arrival rates for which there is a policy that makes the ring stable). We provide such a policy, which does not require knowledge of end-to-end arrival rates. The policy is an adaptive version of the quota policies and can be implemented with the same distributed mechanism. We use the Lyapunov test function technique together with methods from the theory of regenerative processes to derive our main results.This research was primarily done while the author was visiting INRIA in Rocquencourt, France. The author wishes to thank INRIA (projects ALGO, MEVAL and REFLECS) for a generous support. Additional support was provided by NSF Grants NCR-9206315 and CCR-9201078 and INT-8912631, and by Grant AFOSR-90-0107, and in part by NATO Grant 0057/89.The research of this author was supported in part by NSF under Grants NCR-9211417 and NCR-9406415, and by the New York State Center for Advanced Technology in Telecommunications, Polytechnic University.     

High performance,low complexity cooperative caching for wireless sensor networks

During the last decade, Wireless Sensor Networks have emerged and matured at such point that they currently support several applications such as environment control, intelligent buildings, target tracking in battlefields. The vast majority of these applications require an optimization to the communication among the sensors so as to serve data in short latency and with minimal energy consumption. Cooperative data caching has been proposed as an effective and efficient technique to achieve these goals concurrently. The essence of these protocols is the selection of the sensor nodes which will take special roles in running the caching and request forwarding decisions. This article introduces two new metrics to aid in the selection of such nodes. Based on these metrics, we propose two new cooperative caching protocols, PCICC and scaPCICC, which are compared against the state-of-the-art competing protocol, namely NICoCa. The proposed solutions are evaluated extensively in an advanced simulation environment and the results confirm that the proposed caching mechanisms prevail over its competitor. The evaluation attests also that the best policy is always scaPCICC, achieving the shortest latency and the least number of transmitted messages.     

Wireless networks with retransmission diversity access mechanisms: stable throughput and delay properties

Building on the concept of retransmission diversity, a class of collision resolution protocols, NDMA (network-assisted diversity multiple access) and BNDMA (blind NDMA), has been introduced recently for wireless packet multiple access. These protocols provide the means for improved performance compared with random access and splitting-based collision resolution protocols at a moderate receiver complexity cost. However, stability of these protocols has not been established, and the available steady-state analysis is restricted to symmetric (common-rate) systems. The stability region of (B)NDMA is formally analyzed. The tools used in the analysis range from a preliminary dominant system approach to the Foster-Lyapunov recurrence criterion and the (/spl sigma/, /spl rho/) deterministic fluid arrivals approach. It is rigorously established that the maximum stable throughput is close to 1. This is followed by a simpler and more general steady-state analysis, bypassing the earlier generating function approach, using instead only balance equations. This approach allows dealing with asymmetry (multirate systems), yielding expressions for throughput and delay per queue. Finally, we generalize BNDMA and the associated analysis to multicode systems.