Distributed Topology Organization and Transmission Scheduling in Wireless Ad Hoc Networks

An ad hoc network is a set of nodes that spontaneously form a multi-hop all-wireless infrastructure without centralized administration. We study two fundamental issues arising in this setting: topology organization and transmission scheduling. In topology organization we consider a system where nodes need to coordinate their transmissions on a non-broadcast frequency hopping channel to discover each other. We devise a symmetric technique where two nodes use a randomized schedule to synchronize and connect in minimum time. This forms the basis for a topology construction protocol where a set of initially unsynchronized nodes are quickly grouped in multiple interconnected communication channels such that the resulting topology is connected subject to channel membership constraints imposed by the physical layer. In the transmission scheduling problem we consider Time Division Multiple Access (TDMA) the network operates with a schedule where at each slot transmissions can be scheduled w…

Author: Salonidis, Theodoros

Source: University of Maryland

Download Link: Click Here To Download This Report

Reference URL: Visit Now

Reference URL: Visit Now

Contents
1 Introduction
1.1 Topology Organization in wireless ad hoc networks
1.1.1 Topology Control
1.1.2 Neighborhood Discovery
1.1.3 The challenge
1.2 Transmission scheduling in wireless ad hoc networks
1.2.1 Interference constraints and traffic models
1.2.2 Medium Access Control Protocols
1.2.3 TDMA challenges
1.3 Contributions of this dissertation
2 Distributed topology construction of BluetoothWireless Personal Area Networks
2.1 Link establishment in Bluetooth
2.1.1 The Asymmetric Protocol
2.2 A symmetric link establishment protocol
2.3 Scatternet formation
2.4 The Bluetooth Topology Construction Protocol (BTCP)
2.4.1 Phase I: Coordinator Election
2.4.2 Phase II: Role Determination
2.4.3 Phase III: Connection Establishment
2.4.4 Leader election termination
2.5 Experiments
2.5.1 Emulating Bluetooth
2.5.2 Determining ALT TIMEOUT
2.5.3 Protocol Performance
2.6 Related Work
2.7 Further issues
3 Asynchronous TDMA: Scheduling and Performance
3.1 Asynchronous TDMA communication model
3.2 Problem formulation and approach
3.3 Equivalent schedules
3.4 Computing optimal asynchronous schedules
3.4.1 Optimal algorithm
3.4.2 MIN PROGRESS
3.5 Performance Evaluation
3.5.1 Factors affecting the overhead
3.5.2 Experimental setting
3.5.3 Performance of MIN PROGRESS with respect to optimal
3.5.4 Performance of MIN PROGRESS for large problem sizes
3.6 Summary
4 A distributed asynchronous TDMA protocol
4.1 Related work
4.2 TDMA architecture
4.2.1 Signaling and local TDMA schedule structure
4.2.2 Exchanging control information
4.3 The distributed TDMA protocol
4.3.1 Overview
4.3.2 Detailed operation
4.3.3 Properties
4.3.4 Design considerations
4.4 Link-level Quality of Service (QoS)
4.4.1 Local feasibility conditions
4.4.2 Optimal link scheduling for tree networks
4.4.3 Some practical considerations
4.5 Summary
5 Link-level max-min fairness
5.1 Network Communication Model
5.1.1 Rate feasibility and max-min fairnesS
5.2 Distributed algorithm–Fluid model
5.2.1 Fairness deficit
5.2.2 Fluid distributed algorithm
5.3 Distributed algorithm–Slot model
5.3.1 Local conditions
5.3.2 Slotted FDC
5.3.3 Slot assignment algorithm
5.3.4 Slotted distributed algorithm
5.4 Performance evaluation
5.4.1 Experimental model and setting
5.4.2 Experiments on static networks
5.4.3 Experiments on dynamic networks
5.4.4 Traffic adaptation
5.5 Related work
5.6 Conclusions
6 End-to-end rate guarantees
6.1 Distributed dynamic link scheduling for tree-based ad hoc networks
6.1.1 Network architecture, assumptions and definitions
6.1.2 The distributed algorithm
6.2 End-to-end rate guarantees
6.2.1 Constant Bit Rate (CBR) Service
6.2.2 Available Bit Rate (ABR) service
6.3 Bluetooth Implementation
6.3.1 Design
6.3.2 Experiment
6.4 Conclusions
7 Summary and extensions
7.1 Contributions
7.2 Suggestions for future work
7.2.1 Topology organization
7.2.2 Transmission scheduling
7.2.3 Transmission scheduling and topology discovery
Bibliography