Browsing by Author "Tassiulas, Leandros"
Results Per Page
Sort Options
Item Adaptive Channel Allocation for OFDM-Based Smart Antenna Systems with Limited Transceiver Resources(2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNSmart antennas constitute perhaps the most promising means of increasing capacity in wireless systems by allowing intra-cell channel reuse by several users. The employment of smart antennas at the physical layer raises significant issues in medium access control (MAC) layer. In this paper, we study the impact of smart antennas on MAC layer channel allocation in the presence of limited transceiver resources, where a transceiver is a communication unit that is used to set up a distinct beam. The problem is addressed in the context of Orthogonal Frequency Division Multiplexing (OFDM), which is the predominantly proposed signaling scheme for wireless broadband access. Since a beam can only serve users in different subcarriers, the problems of subcarrier and transceiver assignment are coupled. We propose heuristic algorithms to allocate channels to users, adjust beamforming vectors and assign users and channels in beams, with the objective to increase system throughput and provide QoS to users in the form of minimum rate guarantees. Our criteria for resource assignment and beam formation are based on spatial separability properties of users, beam vector cross-correlations and induced interference to the system. This unified cross-layer approach is shown to yield significant throughput benefits.Item Adaptive Resource Allocation in SDMA-Based Wireless Broadband Networks with OFDM Signaling(2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNThe increasing popularity of wireless broadband access in local and wide area networks is the main expression of the need for flexible and ubiquitous wireless connectivity. In order to satisfy user resource requirements in the presence of volatility of the wireless medium, sophisticated multiple access and adaptation techniques are required, which alleviate channel impairments and increase system throughput. The use of multiple antennas at the base station allows intra-cell channel reuse by multiple spatially separable users through Space Division Multiple Access (SDMA) and hence enhances cell capacity. However, the employment of antennas in the physical layer raises significant issues in medium access control (MAC) layer. In this paper, we investigate the impact of antenna arrays on MAC layer channel allocation in the context of Orthogonal Frequency Division Multiplexing (OFDM), which is the predominantly proposed signaling scheme for wireless broadband access. We propose an algorithm to allocate channels to users based on their spatial separability properties, while appropriately adjusting beamforming weights and transmission rates for each user in a channel. The unified consideration of such adaptive techniques yields significant throughput benefits.Item Balanced-RED: An Algorithm to Achieve Fairness in the Internet(1999) Farooq M. Anjum; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNThe problem of fair bandwidth sharing among adaptive (TCP) and non-adaptive(i.e. CBR-UDP) flows at an Internet gateway is considered. An algorithm thatdrops packet preventively, in an attempt to actively penalize the non-adaptivetraffic that attempts to "steal" buffer space, and therefore bandwidth from theadaptive traffic flows, is presented. The algorithm maintains minimal flow stateinformation and is therefore scalable. The performance of the algorithm iscompared with other gateway algorithms, and it is shown that, in the presence of non-adaptive traffic, it achieves a more balanced bandwidth allocation among thedifferent flows. The behavior of a flow subjected to the given algorithm has also been analyzed in detail.Item Carrier Assignment Algorithms in Wireless Broadband Networks with Channel Adaptation(2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNWireless broadband access is an appealing solution to the projected trend towards reliable and easily deployable high-speed connections. In order to enhance system capacity and tolerate volatility of the wireless medium, sophisticated adaptation techniques are required. In this paper, we consider the problem of efficient resource allocation with adaptive modulation techniques in a multi-carrier wireless cellular system. We identify the inherent complexity of the problem and propose a heuristic algorithm for carrier frequency assignment to users, based on channel quality. The algorithm leads to an efficient allocation, in the sense that each user is assigned to a carrier and occupies the least number of channels (timeslots). Simulation results show that the algorithm leads to high link utilization and low blocking rate for a wide range of traffic loads and interference levels.Item Channel State-Adaptive Techniques for Throughput Enhancement in Wireless Broadband Networks(2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNWireless broadband access is becoming increasingly popular in the telecommunications market due to the projected demand for flexible and easily deployable high-speed connections. In order to adhere to the volatility of the wireless medium, the adoption of sophisticated adaptation techniques is required. In this paper, we investigate the problem of enhancing channel throughput by performing resource assignment and reuse with adaptation of physical layer parameters. We propose an algorithm to allocate channels to users with different rate requirements, while appropriately adjusting the modulation level and transmission power, based on instantaneous channel quality. Our algorithm constructs the cochannel set of users in a sequential manner, by utilizing a criterion which is based on the induced and received amounts of interference for a user and the contribution in throughput increase. Although illustrated in the context of TDMA/TDD, the proposed technique can be applied in systems which support different multiple access and signaling schemes with orthogonal channels (e.g. OFDMA, CDMA). Our results indicate a considerable increase in throughput per utilized channel under such adaptive techniques.Item Designing Broadcast Schedules for Information Dissemination through Broadcasting(1997) Su, Chi-Jiun; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNBroadcast data delivery is encountered in many applications where there is a need to disseminate information to a large user community in a wireless asymmetric communication environment. In this paper, we consider the problem of scheduling the data broadcast such that the access latency experienced by the users is low. In a push-based system, where the users cannot place requests directly to the server and the broadcast schedule should be determined based solely on the access probabilities, we formulate a deterministic dynamic optimization problem, the solution of which provides the optimal broadcast schedule. Properties of the optimal solution are obtained and then we propose a suboptimal dynamic policy which achieves mean access latency close to the lower bound. The policy has low complexity, it is adaptive to changing access statistics, and is easily generalizable to multiple broadcast channels. In a pull-based system where the users may place requests about information items directly to the server, the scheduling can be based on the number of pending requests for each item. Suboptimal policies with good performance are obtained in this case as well. Finally, it is demonstrated by a numerical study that as the request generation rate increases, the achievable performance of the pull- and push- based systems becomes almost identical.Item Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees(1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISRWe study fairness in arbitrary networks with multicast capabilities.Multicast traffic in internet and ATM provides a motivationfor studying these networks. A study of fairness in multicastnetworks poses several interesting problems e.g., the issueof {it intra-session} fairness in addition to thatof {it inter-session} fairness in unicastnetworks. We develop a mathematical frameworkto model the fair allocation of bandwidth in multicast networkswith minimum and maximum rate constraints. We presentdistributed algorithms for computation of maxmin fair ratesallocated to various source-destination pairs.Item Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks(2004) Salonidis, Theodoros; Tassiulas, Leandros; Tassiulas, Prof. Leandros; ISR; CSHCNWe present a novel framework for the provision of deterministic end-to-end bandwidth guarantees in wireless ad hoc networks. Guided by a set of local feasibility conditions, multi-hop sessions are dynamically offered allocations, further translated to link demands. Using a distributed TDMA protocol, nodes adapt to the demand changes on their adjacent links by local, conflict-free slot reassignments. As soon as the changes stabilize, the nodes must incrementally converge to a TDMA schedule that realizes the global link (and session) demand allocation.We first identify an inherent trade-off between the degree of topology control and fraction of feasible allocations that can be captured by the local conditions. We show that tree topologies can be maximally utilized in this respect and that a converging distributed link scheduling algorithm exists in this case.
Decoupling end-to-end bandwidth allocation from link scheduling allows support of various end-to-end QoS objectives. Focusing on Available Bit Rate (ABR) service, we design an asynchronous distributed algorithm for sharing bandwidth to the sessions in a maxmin fair (MMF) manner.
Finally, we present the implementation of this framework over Bluetooth, an existing wireless technology that enables the formation of ad hoc networks. This implementation is free of the usual restrictive assumptions of previous TDMA approaches: it does not require any a-priori knowledge on the number of nodes in the network nor even network-wide slot synchronization.
Item Distributed On-Line Schedule Adaptation for Balanced Slot Allocation in Bluetooth Scatternets and other Wireless Ad-Hoc Network Architectures(2002) Tassiulas, Leandros; Salonidis, Theodoros; ISR; CSHCNIn this paper we propose an algorithm for design and on the fly modification of the schedule of an ad-hoc wireless network in order to provide fair service guarantees under topological changes. The primary objective is to derive a distributed coordination method for schedule construction and modification in Bluetooth scatternets. The algorithm proposed here has wider applicability, to any wireless ad-hoc network that operates under a schedule where the transmissions at each slot are explicitly specified over a time period of length T.First we introduce a fluid model of the system where the conflict avoidance requirements of neighboring links are relaxed while the aspect of local channel sharing is captured. In that model we propose an algorithm where the nodes asynchronously re-adjust the rates allocated to their adjacent links based only on local information. We prove that from any initial condition the algorithm finds the max-min fair rate allocation in the fluid model. Hence if the iteration is performed constantly the rate allocation will track the optimal even in regimes of constant topology changes.
Then we consider the slotted system and propose a modification method that applies directly on the slotted schedule, emulating the effect of the rate re-adjusment iteration of the fluid model. Through extensive experiments in networks with fixed and time varying topologies we show that the latter algorithm achieves balanced rate allocation in the actual slotted system that are very close to the max-min fair rates. The experiments show also that the algorithm is very robust on topology variations, with very good tracking properties of the max-min fair rate allocation.
Item Dynamic Code Assignment and Spreading Gain Adaptation in Synchronous CDMA Wireless Networks(2002) Koutsopoulos, Iordanis; Kozat, Ulas C.; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNDS-CDMA has been recognized as the major candidate for providing high and variable data rates in third generation wireless networks, where multi-code structures and different spreading gains will be employed. In this paper, we address the problem of assignment of variable spreading gain deterministic codes to a set of users, with the objective to maximize down-link system throughput. We propose an algorithm to allocate codes to users with different minimum rate requirements, based on code cross-correlation properties and spreading gains. Our algorithm first constructs an admissible set of codes by using criteria which are based on induced interference to the system and code rates. These codes are then appropriately assigned to users, so that user rate requirements are satisfied. Comparative numerical results for different performance measures of these criteria are also provided.Item Efficient Media Access Protocols for Wireless LANs with Smart Antennas(2002) Ren, Tianmin; Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNThe use of smart antennas in extending coverage range and capacity of wireless networks dictates the employment of novel media access control protocols, with which the base station (BS) or access point (AP) provides access to users by learning their locations. We consider the class of protocols that employ beamforming and use contention-based or contention-free polling methods to locate users residing in or out of coverage range of the AP. Such protocols allow rapid media access and can be embedded in existing MAC protocols.Item Efficient Media Access Protocols for Wireless LANs with Smart Antennas(2003) Ren, Tianmin; Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNThe use of smart antennas in extending coverage range and capacity of wireless networks dictates the employment of novel media access control protocols, with which the base station (BS) or access point (AP) provides access to users by learning their locations. We consider the class of protocols that employ beamforming and use contention-based or contention-free polling methods to locate users residing in or out of coverage range of the AP. Such protocols allow rapid media access and can be embedded in existing MAC protocols.Item Efficient Resource Utilization through Carrier Grouping for Half-duplex communication in GSM-based MEO Mobile Satellite networks(2001) Koutsopoulos, Iordanis; Tassiulas, Leandros; ISR; CSHCNIn the near future, existing terrestrial radio networks are envisioned to integrate with satellite systems to provide global coverage. In order to enable communication for both non-hand-held and hand-held User Terminals (UTs), the radio link design must allow the UT to operate in full- and half-duplex mode respectively, where the latter is desirable when radiation power restrictions are imposed. In addition, sophisticated resource management and diversity provisioning will enhance system capacity and reliability. However, propagation delay caused by the satellite link may lead to inefficient resource allocation and problematic diversity provisioning.In this paper, we address and study the resource allocation problem pertaining to a Medium-Earth-Orbit (MEO) satellite system with half-duplex communication capabilities. Such a system is characterized by large propagation delays, large intra-beam delay variations and inherently poor resource utilization.
We propose a channel classification scheme, where the available carriers are partitioned into classes and each class is associated with a certain range of propagation delays to the satellite. The suggested infrastructure results in higher channel utilization, reduced call blocking rate and efficient diversity provisioning and can be implemented with low signaling load.
Item Fair Allocation of Discrete Bandwidth Layers in Multicast Networks(1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISRWe study fairness when receivers in a multicast network can not subscribeto fractional layers. This case arises whenthe source hierarchically encodes its signal and the hierarchical structureis predetermined. Unlike the case of the fractional layer allocation,which has been studied extensively in a previous work, bandwidth canbe allocated in discrete chunks only. Fairness issues becomevastly different. Computation of lexicographically optimal rateallocation becomes NP-hard in this case, while lexicographicallyoptimal rate allocation is polynomial complexity computablewhen fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case.We introducea new notion of fairness, maximal fairness.We propose a polynomialcomplexity algorithm for computation of maximally fair ratesallocated to various source-destination pairs. Even though, maximal fairnessis a weaker notion of fairness, itcoincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. So the algorithmfor computing maximally fair rate allocation computes maxmin fairrate allocation, when the latter exists.Item A Framework for Cross-layer Design of Energy-efficient Communication with QoS Provisioning in Multi-hop Wireless Networks(2004) Kozat, Ulas C.; Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNEfficient use of energy while providing an adequate level of connection to individual sessions is of paramount importance in multi-hop wireless networks. Energy efficiency and connection quality depend on mechanisms that span several communication layers due to the existing co-channel interference among competing flows that must reuse the limited radio spectrum. Although independent consideration of these layers simplifies the system design, it is often insufficient for wireless networks when the overall system performance is examined carefully. The multi-hop wireless extensions and the need for routing users' sessions from source to the destination only intensify this point of view. In this work, we present a framework for cross-layer design towards energy-efficient communication. Our approach is characterized by a synergy between the physical and the medium access control (MAC) layers with a view towards inclusion of higher layers as well. More specifically, we address the joint problem of power control and scheduling with the objective of minimizing the total transmit power subject to the end-to-end quality of service (QoS) guarantees for sessions in terms of their bandwidth and bit error rate guarantees. Bearing to the NP-hardness of this combinatorial optimization problem, we propose our heuristic solutions that follow greedy approaches.Item A Framework for Routing and Congestion Control for Multicast Information Flows(1998) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNWe propose a new multipurpose multicast routing and schedulingalgorithm (MMRS). The routing policy load balances amongstvarious possible routes between the source and the destinations,relying its decisions on the message queue lengths at thesource node. The scheduling amongst various sessionssharing links is devised such that the flow of a sessiondepends on the congestion of the next hop links. MMRSis throughput optimal and computationally simple.The algorithm can be implemented in a distributed,asynchronous manner. It has several parameters which can besuitably modified to control the end-to-end delay, packet lossin a topology specific manner. These parameters can be adjustedto offer limited priorities to some desired sessions. MMRS is expectedto play a significant role in end-to-end congestion controlin the multicast scenario.Item Functioning of TCP Algorithms over a Wireless Link(1999) Anjum, Farooq M.; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNIn this paper, we investigate the behavior of the various algorithms of TCP, the Internet datatransport protocol, over wireless links with correlated packet losses. For such ascenario, we show that the performance of NewReno is worse than theperformance of Tahoe in many situations and even OldTahoe in a few situations on account of the inefficientfast recovery method of NewReno.We also show that random loss leads tosignificant throughput deterioration when either the product of the squareof the bandwidth-delay ratio and the loss probability when in the good state exceeds 1 or the product of the bandwidth-delay ratio and the packet successprobability when in the bad state is less than two.
The performance of Sackis always seen to be the best and the most robust thereby arguing for theimplementation of TCP SACK over the wireless channel. We also show thatunder certain conditions the performance depends not only on thebandwidth-delay product but also on the nature of timeout, whether coarse orfine. We have also investigated the effects of reducing the fast retransmitthreshold.
Item The Impact of Space Division Multiplexing on Resource Allocation: A Unified Approach(2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNRecent advances in the area of wireless communications have revealed the emerging need for efficient wireless access in personal, local and wide area networks. Space division multiple access (SDMA) with smart antennas at the base station is recognized as a promising means of increasing system capacity and supporting rate-demanding services. However, the existence of SDMA at the physical layer raises significant issues at higher layers. In this paper, we attempt to capture the impact of SDMA on channel allocation at the media access control (MAC) layer. This impact obtains different forms in TDMA, CDMA and OFDMA access schemes, due to the different cochannel and inter-channel interference instances, as well as the different effect of corresponding channels (time slots, codes or subcarrier frequencies) on user channel characteristics. We follow a unified approach for these multiple access schemes and propose heuristic algorithms to allocate channels to users and adjust down-link beamforming vectors and transmission powers, with the objective to increase achievable system rate and provide QoS to users in the form of minimum rate guarantees. We consider the class of greedy algorithms, based on criteria such as minimum induced or received interference and minimum signal-to-interference ratio (SIR), as well as the class of SIR balancing algorithms. Our results indicate that this cross-layer approach yields significant performance benefits and that SIR balancing algorithms achieves the best performance.Item A Low-Overhead Rate Control Algorithm for Maximizing Aggregate Receiver Utility for Multirate Multicast Sessions(2000) Kar, Koushik; Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNIn multirate multicasting, different users (receivers) within the same multicastgroup could receive service at different rates, depending on user requirementsand network congestion level. Compared to unirate multicasting, this provides moreflexibility to the user, and allows more efficient usage of network resources.In this paper, we address the rate control problem for multirate multicast sessions,with the objective of maximizing the total receiver utility.This aggregate utility maximization problem not only takes into account the heterogeneityin user requirements, but also provides a unified framework for diverse fairness objectives.
We propose an algorithm for this problem and show, through analysis andsimulation, that it converges to the optimal rates.
In spite of the non-separability of the problem,the solution that we develop is completely decentralized, scalableand does not require the network to know the receiver utilities.Moreover, the algorithm requires very simple computations both forthe user and the network, and also has very low overhead of network congestionfeedback.
Item Network Layer Support for Service Discovery in Mobile Ad Hoc Networks(2003) Kozat, Ulas C.; Tassiulas, Leandros; ISRService discovery is an integral part of the ad hoc networking toachieve stand-alone and self-configurable communication networks. Inthis paper, we discuss possible service discovery architectures alongwith the required network support for their implementation, and wepropose a distributed service discovery architecture which relies on avirtual backbone for locating and registering available serviceswithin a dynamic network topology. Our proposal consists of twoindependent components: (i) formation of a virtual backbone and (ii)distribution of service registrations, requests, and replies. Thefirst component creates a mesh structure from a subset of a givennetwork graph that includes the nodes acting as service brokers and asubset of paths (which we refer as virtual links) connectingthem. Service broker nodes (SBNs) constitute a dominating set, i.e.all the nodes in the network are either in this set or only one-hopaway from at least one member of the set. The second componentestablishes sub-trees rooted at service requesting nodes andregistering servers for efficient dissemination of the servicediscovery probing messages. Extensive simulation results are providedfor comparison of performance measures ,i.e. latency, success rate,and control message overhead, when different architectures and networksupport mechanisms are utilized in service discovery.