Hui, Tan Hing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 151-162). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Literature Review --- p.7 / Chapter 2.1 --- Background --- p.7 / Chapter 2.1.1 --- "Tools for Analyzing Vehicles' Speeds, Traffic Flows and Densities" --- p.7 / Chapter 2.1.2 --- Tools for Analyzing Bytes Received by the Vehicles from an AP --- p.9 / Chapter 2.1.3 --- Effort-Fairness vs Outcome-Fairness --- p.10 / Chapter 2.1.4 --- Quantifying Fairness on the Bytes Received by the Vehicles from an AP --- p.10 / Chapter 2.2 --- Delay-Tolerant Networks(DTNs) --- p.12 / Chapter 2.3 --- Drive-thru Internet Systems --- p.14 / Chapter 2.4 --- Resource Allocation/Scheduling in Drive-thru Internet and Related Systems --- p.20 / Chapter 2.4.1 --- Resource Allocation/Scheduling Algorithms for Multiple Vehicles --- p.20 / Chapter 2.4.2 --- Rate Adaptation Algorithms for Fast-varying Channels due to Vehicular Movement/Mobility --- p.29 / Chapter 3 --- Performance Evaluation of Round-robin Scheduler with IEEE 802.11 MAC --- p.33 / Chapter 3.1 --- System Model --- p.34 / Chapter 3.2 --- Description of the Real-life Vehicular Traffic Trace --- p.36 / Chapter 3.2.1 --- Analysis on Hourly Single-lane Traffic Flow of 1-80 Highway --- p.40 / Chapter 3.2.2 --- Analysis on Hourly Directional Traffic Flow of 1-80 Highway --- p.43 / Chapter 3.2.3 --- Analysis on Hourly Single-lane Vehicles' Speeds of 1-80 Highway --- p.45 / Chapter 3.2.4 --- Analysis on Daily Vehicles' Speeds of 1-80 Highway --- p.48 / Chapter 3.2.5 --- "Relationship among Average Traffic Densities, Flows and Vehicles' Speeds in Singlelane Scenarios" --- p.51 / Chapter 3.2.6 --- "Relationship among Average Traffic Densities, Flows and Vehicles' Speeds in Multilane Scenarios" --- p.52 / Chapter 3.3 --- Trace-driven Simulations of Drive-thru Internet Scenarios using Round-robin Scheduler with IEEE 802.11 MAC --- p.54 / Chapter 3.3.1 --- Simulation Setup --- p.54 / Chapter 3.3.2 --- Scenarios of using Fixed Data Rate --- p.57 / Chapter 3.3.3 --- Scenario of using Auto-rate Algorithm --- p.67 / Chapter 4 --- The Design and Implementation of VECADS --- p.73 / Chapter 4.1 --- Towards the Design of an Intelligent Scheduling for Drive-thru Internet --- p.74 / Chapter 4.1.1 --- System Throughput Maximization vs Fairness --- p.74 / Chapter 4.1.2 --- Antenna --- p.75 / Chapter 4.1.3 --- Speed --- p.76 / Chapter 4.1.4 --- Noisy Measurement of Predicting Channel Condition based on RSSI(or Similar Metrics) only --- p.77 / Chapter 4.1.5 --- Region for Serving “Weak´ح Vehicles --- p.78 / Chapter 4.2 --- System Model --- p.79 / Chapter 4.3 --- The Design of VECADS --- p.83 / Chapter 4.3.1 --- Using Vehicular Context to Help Scheduling --- p.83 / Chapter 4.3.2 --- Penalizing Slow Vehicles in the Coverage . --- p.88 / Chapter 4.3.3 --- "Round-Robin Scheduling for ""Weak"" Vehicles in the “Sweet Zone´ح" --- p.90 / Chapter 4.3.4 --- Rate Adaptation Algorithm in VEC ADS --- p.94 / Chapter 4.4 --- The Implementation of VECADS --- p.97 / Chapter 4.4.1 --- Overall System Architecture of VECADS --- p.97 / Chapter 4.4.2 --- Overall Scheduling Flow of VECADS --- p.100 / Chapter 4.4.3 --- Algorithms in VECADS --- p.102 / Chapter 5 --- Performance Evaluation of VECADS --- p.110 / Chapter 5.1 --- Simulation Setup --- p.110 / Chapter 5.2 --- Simulation Results and Discussion --- p.114 / Chapter 5.2.1 --- Evaluation of the Performance Impact of Different System Parameters --- p.114 / Chapter 5.2.2 --- Evaluation of Different Design Options --- p.119 / Chapter 6 --- Conclusions and Discussion --- p.142 / Chapter A --- Average Bytes Received by a Moving Vehicle from a Roadside AP --- p.146 / Chapter B --- Distribution of the Cumulative Bytes Received by Vehicles from a Roadside AP --- p.148 / Bibliography --- p.151

Wireless sensor networks (WSNs) provide rapid, untethered access to information, eliminating the barriers of distance, time, and location for many applications in national security, civilian search and rescue operations, surveillance, border monitoring, and many more. Sensor nodes are resource constraint in terms of power, bandwidth, memory, and computing capabilities. Sensor nodes are typically battery powered and depending on the application, it may be impractical or even impossible to recharge them. Thus, it is important to develop mechanisms for WSN which are energy efficient, in order to reduce the energy consumption in the network. Energy efficient algorithms result in an increased network lifetime. Data gathering is an important operation in WSNs, dealing with collecting sensed data or event reporting in a timely and efficient way. There are various scenarios that have to be carefully addressed. In this dissertation we propose energy efficient algorithms for data gathering. We propose a novel event-based clustering mechanism, and propose several efficient data gathering algorithms for mobile sink WSNs and for spatio-temporal events. Border surveillance is an important application of WSNs. Typical border surveillance applications aim to detect intruders attempting to enter or exit the border of a certain region. Deploying a set of sensor nodes on a region of interest where sensors form barriers for intruders is often referred to as the barrier coverage problem. In this dissertation we propose some novel mechanisms for increasing the percentage of events detected successfully. More specifically, we propose an adaptive sensor rotation mechanism, which allow sensors to decide their orientation angle adaptively, based on the location of the incoming events. In addition, we propose an Unmanned Aerial Vehicle UAV aided mechanism, where an UAV is used to cover gaps dynamically, resulting in an increased quality of the surveillance. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2019. / FAU Electronic Theses and Dissertations Collection

Today's distributed systems exist on a scale that was unimaginable only a few decades ago. Distributed systems now can consist of thousands or even millions of computers spread across the entire world. These large systems are often organized into overlay networks - networks composed of virtual links, with each virtual link realized by one or more physical links. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, the correct network topology is always built. This area of research is young, and prior examples of self-stabilizing overlay networks have either been for simple topologies, or involved complex algorithms that were difficult to verify and extend. We address these limitations in this thesis. First, we present the Transitive Closure Framework, a generic framework to transform any locally-checkable overlay network into a self-stabilizing network. This simple framework has a running time which is at most a logarithmic number of rounds more than optimal, and in fact is optimal for a particular class of overlay networks. We also prove the only known non-trivial lower bound on the convergence time of any self-stabilizing overlay network. To allow fast and efficient repairs for local faults, we extend the Transitive Closure Framework to the Local Repair Framework. We demonstrate this framework by implementing an efficient algorithm for node joins in the Skip+ graph. Next, we present the Avatar network, which is a generic locally checkable overlay network capable of simulating many other overlay networks. We design a self-stabilizing algorithm for a binary search tree embedded onto the Avatar network, and prove this algorithm requires only a polylogarithmic number of rounds to converge and limits degree increases to within a polylogarithmic factor of optimal. This algorithm is the first to achieve such efficiency, and its modular design makes it easy to extend. Finally, we introduce a technique called network scaffolding, which builds other overlay network topologies using the Avatar network.

In this dissertation, we study self-adjusting algorithms for large-scale distributed systems. Self-adjusting algorithms enable distributed systems to adjust their properties dynamically as the input pattern changes. Self-adjustment is an attractive tool as it has the potential to significantly improve the performance of distributed systems, especially when the input patterns are skewed. We start with a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the CONGEST model (i.e. uses O(log n) bit messages), and requires O(log n) bits of memory for each node, where n is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model. As a follow-up work, we present a distributed self-adjusting algorithm (referred to as DyHypes) for topological adaption in hypercubic networks. One of the major differences between hypercubic networks and skip graphs is that hypercubic networks are more rigid in structure than that of skip graphs. This property of hypercubic networks makes self-adjustment significantly different compared to skip graphs. Upon a communication between an arbitrary pair of nodes, DyHypes transforms the network to place frequently communicating nodes closer to each other to maximize communication efficiency, and uses randomization in the transformation process to speed up the transformation and reduce message complexity. We show that, as compared to DSG, DyHypes reduces the transformation cost by a factor of O(log n), where n is the number of nodes involved in the transformation. Moreover, despite achieving faster transformation with lower message complexity, the combined cost (routing and transformation) of DyHypes is at most a log log n factor more than that of any algorithm that conforms to the computational model adopted for this work. Similar to DSG, DyHypes is fully decentralized, conforms to the CONGEST model, and requires O(log n) bits of memory for each node, where N is the total number of nodes. Finally, we present a novel distributed load balancing algorithm called Meezan to address the load imbalance among large-scale networked cache servers. Modern web services rely on a network of distributed cache servers to efficiently deliver content to users. Load imbalance among cache servers can substantially degrade content delivery performance. Due to the skewed and dynamic nature of real-world workloads, cache servers that serve viral content experience higher load as compared to other cache servers. Our algorithm Meezan replicates popular objects to mitigate skewness and adjusts hash space boundaries in response to load dynamics in a novel way. Our theoretical analysis shows that Meezan achieves near perfect load balancing for a wide range of operating parameters. Our trace driven simulations shows that Meezan reduces load imbalance by up to 52% as compared to prior solutions.

We present an algorithm to store data robustly in a large, geographically distributed network by means of localized regions of data storage that move in response to changing conditions. For example, data might migrate away from failures or toward regions of high demand. The PersistentNode algorithm provides this service robustly, but with limited safety guarantees. We use the RAMBO framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. In addition, a half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

The genetic algorithm paradigm is a well-known heuristic for solving many problems in science and engineering in which candidate solutions, or “individuals”, are manipulated in ways analogous to biological evolution, to produce new solutions until one with the desired quality is found. As problem sizes increase, a natural question is how to exploit advances in distributed and parallel computing to speed up the execution of genetic algorithms. This thesis proposes a new distributed architecture for genetic algorithms, based on distributed storage of the individuals in a persistent pool. Processors extract individuals from the pool in order to perform the computations and then insert the resulting individuals back into the pool. Unlike previously proposed approaches, the new approach is tailored for distributed systems in which processors are loosely coupled, failure-prone and can run at different speeds. Proof-of-concept simulation results are presented for four benchmark functions and for a real-world Product Lifecycle Design problem. We have experimented with both the crash failure model and the Byzantine failure model. The results indicate that the approach can deliver improved performance due to the distribution and tolerates a large fraction of processor failures subject to both models.

Thesis (M. S.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2009. / Committee Chair: Jeff Shamma; Committee Member: Eric Feron; Committee Member: Magnus Egerstedt. Part of the SMARTech Electronic Thesis and Dissertation Collection.

It has been envisioned that in the near future, wireless ad hoc networks would populate various application fields, ranging from disaster relief, environmental monitoring, surveillance, to medical applications, the observation of chemical and biological processes and community mesh networks. The decentralized and self-organizing nature of wireless ad hoc networks makes distributed algorithms fit very well in these networks, which however pose great challenges to the algorithm designers as they try to achieve optimal efficiency in communications. In this thesis, I develop a set of distributed algorithms addressing these challenges and solving some fundamental communication problems in wireless ad hoc networks. Communications in wireless ad hoc networks happen on a shared medium, and consequently are subject to interference. The first part of the thesis focuses on disseminating information on multiple-access channels while avoiding collisions. For both single-channel and multi-channel networks, the complexity of information dissemination is investigated, and nearly optimal distributed algorithms are proposed. The second part of the thesis focuses on designing efficient distributed algorithms for some fundamental problems under the physical Signal-to-Interference-plus-Noise-Ratio (SINR) interference model. The SINR model defines global fading interference with which the success of a signal reception depends on all simultaneous transmissions. Compared with graph based models, the SINR model reflects the fading and cumulative nature of radio signals. Hence, the SINR model represents the physical reality more precisely. However, the global nature of the SINR model makes the analysis of distributed algorithms much more challenging. Two types of fundamental problems are addressed in this part. The first type is closely related to communication coordination, including the wireless link scheduling problem and the node coloring problem. The second type of problems are about basic communication primitives, including the local broadcasting problem and the multiple-message broadcast problem. I investigate the complexity of these fundamental problems under the SINR interference model, and present efficient or optimal distributed algorithms. In the third part of the thesis, I propose a general interference model that can include commonly adopted interference models as special cases, and study whether efficient distributed algorithms can still be designed and analyzed in such a general model. Specifically, the affectance model is proposed in this part, which depicts the relative interference (affectance) on communication links caused by transmitting nodes. Both graph based models and the SINR model can be transformed into the affectance model. Under this general model, distributed algorithms with worst-case guarantees for the local broadcasting problem are presented. I also show how to make use of the developed techniques to get nearly optimal algorithms under the graph based model and the SINR model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy