Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Tassiulas, LeandrosSubject: search.filters.subject.Global Communication Systems

Search Results

Now showing 1 - 10 of 21
  • Thumbnail Image
    Item
    Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks
    (2004) Salonidis, Theodoros; Tassiulas, Leandros; Tassiulas, Prof. Leandros; ISR; CSHCN
    We 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.

  • Thumbnail Image
    Item
    Network Layer Support for Service Discovery in Mobile Ad Hoc Networks
    (2003) Kozat, Ulas C.; Tassiulas, Leandros; ISR
    Service 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.
  • Thumbnail Image
    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; CSHCN
    Efficient 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.
  • Thumbnail Image
    Item
    Efficient Media Access Protocols for Wireless LANs with Smart Antennas
    (2003) Ren, Tianmin; Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    The 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.
  • Thumbnail Image
    Item
    Throughput Capacity of Random Ad Hoc Networks with Infrastructure Support
    (2003) Kozat, Ulas C.; Tassiulas, Leandros; ISR
    In this paper, we consider the transport capacity of ad hoc networkswith a random flat topology under the present support of an infinitecapacity infrastructure network. Such a network architecture allowsad hoc nodes to reach each other by purely using ad hoc nodes asrelays. In addition, ad hoc nodes can also utilize the existinginfrastructure fully or partially by reaching any access point (orgateway) of the infrastructure network in a single or multi-hopfashion.

    Using the same tools as in cite{gupta-capacity2000}, weshowed that the per source node capacity of $Theta(W/log(N))$ can beachieved in a random network scenario with the assumptions that thenumber of ad hoc nodes per access points is bounded above and that $N$ad hoc nodes excluding the access points, each capable of transmittingat $W$ bits/sec using a fixed transmission range, constitute aconnected graph.

    This is a significant improvement over the capacityof random ad hoc networks with no infrastructure support which isfound as $Theta(W/sqrt{N log(N)})$ in cite{gupta-capacity2000}.Although better capacity figures are obtained by complex networkcoding or exploiting mobility in the network, infrastructure approachprovides a simpler mechanism that has more practical aspects.

    We alsoshow that even when less stringent requirements are imposed ontopology connectivity, a per source node capacity figure that isarbitrarily close to $Theta(1)$ can not be obtained. Neverthelessunder these weak conditions, we can further improve per nodethroughput significantly.

  • Thumbnail Image
    Item
    Dynamic Code Assignment and Spreading Gain Adaptation in Synchronous CDMA Wireless Networks
    (2002) Koutsopoulos, Iordanis; Kozat, Ulas C.; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    DS-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.
  • Thumbnail Image
    Item
    Adaptive Resource Allocation in SDMA-Based Wireless Broadband Networks with OFDM Signaling
    (2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    The 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.
  • Thumbnail Image
    Item
    Adaptive Channel Allocation for OFDM-Based Smart Antenna Systems with Limited Transceiver Resources
    (2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    Smart 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.
  • Thumbnail Image
    Item
    The Impact of Space Division Multiplexing on Resource Allocation: A Unified Approach
    (2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    Recent 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.
  • Thumbnail Image
    Item
    Carrier Assignment Algorithms in Wireless Broadband Networks with Channel Adaptation
    (2002) Koutsopoulos, Iordanis; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCN
    Wireless 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.