Computing consistent global states in a distributed system is a fundamental problem. A large class of distributed system problems can be cast as construction of consistent global states and evaluation of relevant properties over these global states. Examples of such problems include the monitoring and debugging of distributed systems, the detection of stable properties such as deadlock, termination, and loss of tokens, protocol specification and verification, garbage collection, checkpointing and failure recovery, and many others. / Finally, we will present a suit of three new snapshot algorithms for mobile ad hoc network systems: cooperative, localized, and centralized. These new snapshot algorithms have different timing and tailoring components, Compared to existing snapshot algorithms, our snapshot algorithms can be proven to work in the presence of node mobility and dynamic topology changes, i.e., all of them can compute consistent global states in a mobile ad hoc network system. We will also evaluate the effectiveness and efficiency of these newly proposed snapshot algorithms by using extensive simulations. / Firstly, we will develop a system model for a mobile ad hoc network system. In addition to the internal, send and receive events that are considered in a traditional system model for static systems, two novel types of events called on and off are introduced to represent dynamic topology changes in our system model. Based on these on and off events, it is convenient to devise new distributed algorithms that can handle dynamic topology changes for the mobile ad hoc network environment. We will also propose a new relation called the extended-happened-before relation, which is generalized from the well-known happened-before relation defined by Lamport, to fully model the ordering of events in a mobile ad hoc network system. The event orders captured by the extended-happened-before relation playa critical role in solving the snapshot problem at hand. / However, consistent global states are not freely available in distributed systems without shared memory and synchronized clocks. In the literature, the fundamental problem of constructing consistent global states in a distributed system was defined as the snapshot problem. Although many solutions to the snapshot problem have been developed for various types of distributed systems, most of them cannot be applied directly to a mobile ad hoc network system, which has no fixed network infrastructure for operating support and may experience dynamic topology changes due to node mobility. In this thesis, we present a systematic study on the snapshot problem in mobile ad hoc network systems. / Secondly, we will derive a new consistency criterion for constructing a global state in a mobile ad hoc network system. Without a common time base and shared memory, the development of the new consistency criterion sticks to the fundamental principle that if the events for recording the local states are ensured to be concurrent, then the recorded local states are equivalent to those that are recorded simultaneously in real time and the resulting global state is guaranteed to be consistent. Importantly, we will also show a consistency theorem, which gives a necessary and sufficient condition for computing consistent global states in a mobile ad hoc network system. That is, a global state of a mobile ad hoc network system is consistent if and only if its corresponding cut is not only causally consistent but also topologically consistent. / Thirdly, we will propose a simple method called timing-and-tailoring to design and analyze snapshot algorithms in a well structured approach. In this generic method, a snapshot algorithm is decomposed into two basic components. The first component called timing is used to record the ordering of events by using logical time algorithms. The second component called tailoring is used to find a consistent global state based on known event ordering. To demonstrate the proposed timing-and-tailoring method, we will also present several examples of using this method to design and analyze snapshot algorithms. These examples provide helpful insights in designing new snapshot algorithms for mobile ad hoc network systems. / Wu, Dan. / Adviser: Man Hon Wong. / Source: Dissertation Abstracts International, Volume: 73-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 135-145). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Lam, Kim Yung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 87-92). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Rayleigh Fading Channels --- p.1 / Chapter 1.2 --- Wireless Ad Hoc Networks --- p.3 / Chapter 1.3 --- Ad Hoc Routing Protocols --- p.3 / Chapter 1.4 --- Information Capacity --- p.4 / Chapter 1.5 --- Cooperative Communications --- p.6 / Chapter 1.6 --- Outline of Thesis --- p.7 / Chapter 2 --- Background and Related Work --- p.8 / Chapter 2.1 --- Cooperative Communications --- p.8 / Chapter 2.1.1 --- Cooperative Diversity --- p.8 / Chapter 2.1.2 --- User Cooperation --- p.10 / Chapter 2.1.3 --- Coded Cooperation --- p.11 / Chapter 2.2 --- Cooperative Routing --- p.12 / Chapter 2.3 --- Information-Theoretic Study --- p.16 / Chapter 2.4 --- Optimization techniques --- p.17 / Chapter 3 --- Single-Source Single-Destination Cooperative Routing --- p.21 / Chapter 3.1 --- System Model --- p.22 / Chapter 3.1.1 --- Network Assumptions --- p.22 / Chapter 3.1.2 --- Routing Process --- p.22 / Chapter 3.1.3 --- Transmitting Signal --- p.23 / Chapter 3.1.4 --- Link Cost Formulation --- p.23 / Chapter 3.2 --- Minimum Energy Cooperative Route --- p.25 / Chapter 3.2.1 --- Cooperative Graph --- p.25 / Chapter 3.2.2 --- An Example of the Cooperative Graph --- p.27 / Chapter 3.2.3 --- Non-reducible property of the Cooperative Graph --- p.29 / Chapter 3.3 --- Optimized Scheduling --- p.32 / Chapter 3.3.1 --- KKT conditions --- p.32 / Chapter 3.3.2 --- Newton´ةs Method --- p.34 / Chapter 3.4 --- Complexity Analysis --- p.35 / Chapter 3.5 --- Simplified Scheduling Process --- p.37 / Chapter 3.5.1 --- Linear relationship in low rate regime --- p.37 / Chapter 3.5.2 --- The Simplified Scheduling Algorithm --- p.39 / Chapter 4 --- Heuristic Single-Source Cooperative Routing Schemes --- p.41 / Chapter 4.1 --- Maximum Hops Cut --- p.42 / Chapter 4.1.1 --- The Routing Protocol --- p.42 / Chapter 4.1.2 --- Simulations --- p.46 / Chapter 4.2 --- Maximum Relays Subgraph --- p.47 / Chapter 4.2.1 --- The Routing Protocol --- p.47 / Chapter 4.2.2 --- Simulations --- p.51 / Chapter 4.3 --- Adaptive Maximum Relays Subgraph --- p.55 / Chapter 4.3.1 --- The Routing Protocol --- p.55 / Chapter 4.3.2 --- Simulations --- p.57 / Chapter 4.4 --- Comparison of three protocols --- p.60 / Chapter 4.4.1 --- Implementation --- p.60 / Chapter 4.4.2 --- Cooperative Performance --- p.60 / Chapter 4.5 --- Enhancement of the algorithms --- p.61 / Chapter 4.5.1 --- Conclusion --- p.63 / Chapter 5 --- Multiplexing Cooperative Routes in Multi-source Networks --- p.64 / Chapter 5.1 --- Problem Formation --- p.65 / Chapter 5.1.1 --- The Network Model --- p.65 / Chapter 5.1.2 --- Objective Aim --- p.65 / Chapter 5.1.3 --- Link Cost Formulation --- p.66 / Chapter 5.1.4 --- Time Sharing and Interference --- p.66 / Chapter 5.1.5 --- Multiple Sources Consideration --- p.67 / Chapter 5.2 --- Multi-Source Route-Multiplexing Protocols --- p.68 / Chapter 5.2.1 --- Full Combination with Interference (FCI) --- p.68 / Chapter 5.2.2 --- Full Combination with Time Sharing (FCTS) --- p.68 / Chapter 5.2.3 --- Selection Between Interference and Time Sharing (SBITS) --- p.69 / Chapter 5.2.4 --- Interference and time sharing combinations --- p.71 / Chapter 5.2.5 --- The Simplified Version for SBITS --- p.72 / Chapter 5.3 --- Stage Cost Calculation --- p.73 / Chapter 5.3.1 --- Total stage cost formation in the sub timeslot --- p.73 / Chapter 5.3.2 --- Total stage cost formulation in different routing protocols --- p.74 / Chapter 5.3.3 --- Multiplexing for non-uniform timeslot routes --- p.75 / Chapter 5.4 --- Simulation --- p.76 / Chapter 5.4.1 --- Simulation model --- p.76 / Chapter 5.4.2 --- Simulation detail --- p.77 / Chapter 5.4.3 --- Simulation evaluation --- p.78 / Chapter 6 --- Conclusion and Future Work --- p.83 / Chapter 6.1 --- Conclusion --- p.83 / Chapter 6.2 --- Future Work --- p.84 / Chapter 6.2.1 --- Multiple-Source System Optimal Route --- p.84 / Chapter 6.2.2 --- Better Relay-Selection Policy --- p.85 / Chapter 6.2.3 --- Single Optimization for Minimum Energy Cooperative Route --- p.85 / Chapter 6.2.4 --- Dynamic Programming for Minimum Energy Cooperative Route --- p.85 / Chapter 6.2.5 --- Min-Max Problem --- p.85 / Chapter 6.2.6 --- Distributed Algorithm --- p.86 / Chapter 6.2.7 --- Game Theory --- p.86 / Bibliography --- p.87

Ruan, Sichao. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 62-65). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Multihop Ad Hoc Wireless Networks --- p.1 / Chapter 1.1.1 --- Introduction to Multihop Ad Hoc Networks --- p.2 / Chapter 1.1.2 --- Scalability of Ad Hoc Wireless Networks --- p.3 / Chapter 1.2 --- Hidden Terminal Problem --- p.3 / Chapter 1.3 --- Exposed Terminal Problem --- p.5 / Chapter 1.4 --- Overview of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- MAC Protocols for Wireless Networks --- p.8 / Chapter 2.1.1 --- Aloha --- p.8 / Chapter 2.1.2 --- CSMA/CA --- p.9 / Chapter 2.1.3 --- IEEE 802.11 DCF Standard --- p.10 / Chapter 2.2 --- Related Work --- p.12 / Chapter 2.2.1 --- Schemes for Hidden Node Problem --- p.12 / Chapter 2.2.2 --- Schemes for Exposed Node Problem --- p.13 / Chapter 2.3 --- Tradeoff between Hidden and Exposed Nodes --- p.14 / Chapter 2.4 --- The Effect of Carrier Sensing Range --- p.17 / Chapter 3 --- Analysis on Carrier Sensing Range --- p.18 / Chapter 3.1 --- Analysis Model --- p.18 / Chapter 3.1.1 --- Terminal Configurations --- p.18 / Chapter 3.1.2 --- Timing/Packet Parameters --- p.19 / Chapter 3.1.3 --- Protocol Approximation --- p.20 / Chapter 3.1.4 --- Throughput Measurement --- p.21 / Chapter 3.2 --- Derivation of Throughput --- p.21 / Chapter 3.2.1 --- Channel Modeling --- p.22 / Chapter 3.2.2 --- Actual Transmission Rate --- p.24 / Chapter 3.2.3 --- Case One --- p.24 / Chapter 3.2.4 --- Case Two --- p.26 / Chapter 3.2.5 --- Mathematical Form of Throughput --- p.28 / Chapter 3.2.6 --- Analysis Results --- p.30 / Chapter 3.3 --- Implications --- p.31 / Chapter 3.3.1 --- Value of Sensing Range in CSMA/CA --- p.31 / Chapter 3.3.2 --- Need for New MAC Protocols --- p.32 / Chapter 4 --- MAC Protocols by Congestion Control --- p.34 / Chapter 4.1 --- Motivations and Principles --- p.34 / Chapter 4.1.1 --- Balancing Hidden and Exposed Nodes --- p.35 / Chapter 4.1.2 --- Controlling Carrier Sensing Range --- p.36 / Chapter 4.1.3 --- Non-homogenous Sensing Range --- p.36 / Chapter 4.2 --- Algorithm Descriptions --- p.38 / Chapter 4.2.1 --- Core Concept --- p.38 / Chapter 4.2.2 --- LDMI Control Scheme --- p.40 / Chapter 4.2.3 --- Tahoe Control Scheme --- p.41 / Chapter 5 --- Simulation Analysis --- p.44 / Chapter 5.1 --- Simulation Configurations --- p.44 / Chapter 5.1.1 --- Geometric Burst Traffic Model --- p.45 / Chapter 5.1.2 --- Network Topology --- p.46 / Chapter 5.1.3 --- Simulation Parameters --- p.47 / Chapter 5.2 --- Throughput Comparisons --- p.48 / Chapter 5.3 --- Fairness Comparisons --- p.50 / Chapter 5.3.1 --- Situation of Unfairness --- p.50 / Chapter 5.3.2 --- Fairness Measurement --- p.52 / Chapter 5.4 --- Convergence Comparisons --- p.54 / Chapter 5.5 --- Summary of Performance Comparison --- p.55 / Chapter 6 --- Conclusions --- p.56 / Chapter A --- Categories of CSMA/CA --- p.58 / Chapter A.1 --- 1-persistent CSMA/CA --- p.58 / Chapter A.2 --- non-persistent CSMA/CA --- p.58 / Chapter A.3 --- p-persistent CSMA/CA --- p.59 / Chapter B --- Backoff Schemes --- p.60 / Chapter B.1 --- Constant Window Backoff Scheme --- p.60 / Chapter B.2 --- Geometric Backoff Scheme --- p.60 / Chapter B.3 --- Binary Exponential Backoff Scheme --- p.61 / Bibliography --- p.62

Cheung, Man Hon. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 89-94). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Rayleigh Fading Channels --- p.1 / Chapter 1.2 --- Ultra-Wideband (UWB) Communications --- p.2 / Chapter 1.2.1 --- Definition --- p.2 / Chapter 1.2.2 --- Characteristics --- p.3 / Chapter 1.2.3 --- UWB Signals --- p.4 / Chapter 1.2.4 --- Applications --- p.5 / Chapter 1.3 --- Cooperative Communications --- p.7 / Chapter 1.4 --- Outline of Thesis --- p.7 / Chapter 2 --- Background Study --- p.9 / Chapter 2.1 --- Interference-Aware Routing --- p.9 / Chapter 2.2 --- Routing in UWB Wireless Networks --- p.11 / Chapter 2.3 --- Cooperative Communications and Routing --- p.12 / Chapter 3 --- Cooperative Routing in Rayleigh Fading Channel --- p.15 / Chapter 3.1 --- System Model --- p.16 / Chapter 3.1.1 --- Transmitted Signal --- p.16 / Chapter 3.1.2 --- Received Signal and Maximal-Ratio Combining (MRC) --- p.16 / Chapter 3.1.3 --- Probability of Outage --- p.18 / Chapter 3.2 --- Cooperation Criteria and Power Distribution --- p.21 / Chapter 3.2.1 --- Optimal Power Distribution Ratio --- p.21 / Chapter 3.2.2 --- Near-Optimal Power Distribution Ratio β´ة --- p.21 / Chapter 3.2.3 --- Cooperation or Not? --- p.23 / Chapter 3.3 --- Performance Analysis and Evaluation --- p.26 / Chapter 3.3.1 --- 1D Poisson Random Network --- p.26 / Chapter 3.3.2 --- 2D Grid Network --- p.28 / Chapter 3.4 --- Cooperative Routing Algorithm --- p.32 / Chapter 3.4.1 --- Cooperative Routing Algorithm --- p.33 / Chapter 3.4.2 --- 2D Random Network --- p.35 / Chapter 4 --- UWB System Model and BER Expression --- p.37 / Chapter 4.1 --- Transmit Signal --- p.37 / Chapter 4.2 --- Channel Model --- p.39 / Chapter 4.3 --- Received Signal --- p.39 / Chapter 4.4 --- Rake Receiver with Maximal-Ratio Combining (MRC) --- p.41 / Chapter 4.5 --- BER in the presence of AWGN & MUI --- p.46 / Chapter 4.6 --- Rake Receivers --- p.47 / Chapter 4.7 --- Comparison of Simple Routing Algorithms in ID Network --- p.49 / Chapter 5 --- Interference-Aware Routing in UWB Wireless Networks --- p.57 / Chapter 5.1 --- Problem Formulation --- p.57 / Chapter 5.2 --- Optimal Interference-Aware Routing --- p.58 / Chapter 5.2.1 --- Link Cost --- p.58 / Chapter 5.2.2 --- Per-Hop BER Requirement and Scaling Effect --- p.59 / Chapter 5.2.3 --- Optimal Interference-Aware Routing --- p.61 / Chapter 5.3 --- Performance Evaluation --- p.64 / Chapter 6 --- Cooperative Routing in UWB Wireless Networks --- p.69 / Chapter 6.1 --- Two-Node Cooperative Communication --- p.69 / Chapter 6.1.1 --- Received Signal for Non-Cooperative Communication --- p.69 / Chapter 6.1.2 --- Received Signal for Two-Node Cooperative Communication --- p.70 / Chapter 6.1.3 --- Probability of Error --- p.71 / Chapter 6.2 --- Problem Formulation --- p.75 / Chapter 6.3 --- Cooperative Routing Algorithm --- p.77 / Chapter 6.4 --- Performance Evaluation --- p.80 / Chapter 7 --- Conclusion and Future Work --- p.85 / Chapter 7.1 --- Conclusion --- p.85 / Chapter 7.2 --- Future Work --- p.86 / Chapter 7.2.1 --- Distributed Algorithm --- p.87 / Chapter 7.2.2 --- Performance Analysis in Random Networks --- p.87 / Chapter 7.2.3 --- Cross-Layer Optimization --- p.87 / Chapter 7.2.4 --- Game Theory --- p.87 / Chapter 7.2.5 --- Other Variations in Cooperative Schemes --- p.88 / Bibliography --- p.89

Ke, Bingwen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 52-54). / Abstracts in Chinese and English. / Abstract --- p.3 / Acknowledgement --- p.5 / Content --- p.6 / Table of Figures --- p.8 / Chapter Chapter 1 --- Introduction --- p.9 / Chapter 1.1 --- Motivations and Contributions --- p.9 / Chapter 1.2 --- Organization of the Thesis --- p.11 / Chapter Chapter 2 --- Background --- p.12 / Chapter 2.1 --- Multiple-Input-Multiple-Output (MIMO) System --- p.12 / Chapter 2.1.1 --- Basic MIMO Structure --- p.12 / Chapter 2.1.2 --- Multiple User Detection (MUD) in MIMO Networks --- p.14 / Chapter 2.2 --- IEEE 802.11 --- p.16 / Chapter 2.2.1 --- CSMA/CA in 802.11 --- p.16 / Chapter 2.2.2 --- CSMA/CA(k) in 802.1 In --- p.18 / Chapter 2.2.3 --- Co-channel Transmission in MIMO WLAN --- p.19 / Chapter Chapter 3 --- Channel Correlation in MIMO Ad Hoc Networks --- p.20 / Chapter 3.1 --- Introduction of Channel Correlation --- p.20 / Chapter 3.2 --- Channel Correlation Threshold --- p.25 / Chapter Chapter 4 --- MAC with SINR Threshold --- p.28 / Chapter Chapter 5 --- Performance Evaluation of MWST in Fully-Connected Networks --- p.33 / Chapter Chapter 6 --- MAC with SINR Threshold (MWST) in Partially-Connected Networks --- p.38 / Chapter 6.1 --- Hidden Link Problem in Partially-Connected Networks --- p.38 / Chapter Chapter 7 --- Performance Evaluation in Partially-Connected Networks --- p.42 / Chapter 7.1 --- Fairness Issues in CSMA/CA(k) --- p.42 / Chapter 7.2 --- Fairness Performance of MWST --- p.45 / Conclusion --- p.50 / References --- p.52

Chau, Wai Shing. / Thesis submitted in: October 2007. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 64-66). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Ad hoc network --- p.1 / Chapter 1.2 --- Outline of the thesis --- p.3 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Multiple Access Control (MAC) --- p.4 / Chapter 2.1.1 --- Time Division Multiple Access (TDMA) --- p.5 / Chapter 2.1.2 --- Spatial TDMA (STDMA) --- p.5 / Chapter 2.2 --- Interference Models --- p.6 / Chapter 2.2.1 --- Primary and Secondary Interferences --- p.6 / Chapter 2.2.2 --- Interference-based Model --- p.7 / Chapter 2.2.3 --- Graph-based Model --- p.7 / Chapter 2.3 --- Scheduling in Graph-based Model --- p.8 / Chapter 2.3.1 --- Conflict Graph --- p.9 / Chapter 3 --- Scheduling Algorithms in Ring Networks --- p.11 / Chapter 3.1 --- Problem Formulation --- p.12 / Chapter 3.2 --- Regular Sequences --- p.14 / Chapter 3.3 --- Scheduling in Ring Networks with Even-number of Edges --- p.22 / Chapter 3.4 --- Scheduling in Ring Networks with an Odd-number of Edges --- p.26 / Chapter 3.4.1 --- Scheduling by Reducing a Ring Network with an Odd-number of Edges into a Ring- Network with an Even-number of Edges --- p.28 / Chapter 3.4.2 --- Scheduling by Shifting the Regular Sequences --- p.32 / Chapter 3.5 --- Discussion --- p.42 / Chapter 3.6 --- Conclusion --- p.42 / Chapter 4 --- Distributed Scheduling Algorithm for Ad Hoc Network --- p.43 / Chapter 4.1 --- Problem Formulation --- p.44 / Chapter 4.2 --- Distributed Scheduling Heuristic Algorithm --- p.44 / Chapter 4.2.1 --- Weight functions --- p.44 / Chapter 4.2.2 --- Main Algorithm --- p.46 / Chapter 4.3 --- Centralized algorithm on a chain network --- p.49 / Chapter 4.4 --- Performance of the Algorithm on Chain Network --- p.50 / Chapter 4.4.1 --- Comparison 1 --- p.51 / Chapter 4.4.2 --- Comparsion 2 --- p.52 / Chapter 4.4.3 --- Comparsion 3 --- p.53 / Chapter 4.5 --- Performance of the Algorithm on Random Conflict graph --- p.55 / Chapter 4.6 --- Discussion --- p.57 / Chapter 4.7 --- Special Graphs --- p.58 / Chapter 4.8 --- Conclusion --- p.61 / Chapter 5 --- Conclusion --- p.62 / Bibliography --- p.64

Shen, Yuxiu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 61-64). / Abstracts in Chinese and English. / 摘要........Error! Bookmark not defined / Abstract --- p.iii / Acknowledgement --- p.v / Content --- p.viii / List of Figures --- p.xi / List of Tables --- p.xii / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background Overview --- p.1 / Chapter 1.2 --- Motivation and Related Work --- p.2 / Chapter 1.3 --- Our Contribution --- p.3 / Chapter 1.4 --- Organization of the Thesis --- p.5 / Chapter Chapter 2 --- Preliminaries --- p.6 / Chapter 2.1 --- TDMA Technology --- p.6 / Chapter 2.1.1 --- Features of TDMA --- p.8 / Chapter 2.2 --- Previous Study on TDMA Link Scheduling --- p.8 / Chapter 2.3 --- Typical Network and Interference Models --- p.10 / Chapter Chapter 3 --- System Model --- p.14 / Chapter 3.1 --- Physical Layer Interference Model --- p.14 / Chapter 3.2 --- Objective of the Problem --- p.15 / Chapter 3.3 --- Rate Matrices for Transmission Sets --- p.17 / Chapter 3.4 --- Airtime Allocation --- p.19 / Chapter Chapter 4 --- Problem Formulation and Its Solution --- p.20 / Chapter 4.1 --- LP Formulation of Optimal TDMA Link Scheduling --- p.21 / Chapter 4.2 --- Solution to the Optimal Air Time Allocation Problem --- p.22 / Chapter 4.3 --- n-length Chain Network --- p.24 / Chapter 4.3.1 --- Adaptive Rate Transmission --- p.25 / Chapter 4.3.2 --- Fixed Rate Transmission --- p.27 / Chapter Chapter 5 --- Bad Transmission Set Removal Algorithm (BTSR) --- p.30 / Chapter 5.1 --- A 7-node Chain Example --- p.30 / Chapter 5.2 --- BTSR Algorithm --- p.32 / Chapter Chapter 6 --- Randomized Decentralized Scheduling Algorithm (RDSA) --- p.35 / Chapter 6.1 --- RDSA Algorithm --- p.35 / Chapter 6.2 --- Pseudo Code of RDSA --- p.37 / Chapter 6.3 --- The Flow Chart of RDSA --- p.39 / Chapter Chapter 7 --- Performance Evaluation --- p.41 / Chapter 7.1 --- Performance of Cross-layer TDMA Link Scheduling --- p.41 / Chapter 7.2 --- Complexity Analysis and Comparisons for BTSR+LP and LP --- p.46 / Chapter 7.2.1 --- Complexity of LP Problem --- p.47 / Chapter 7.2.2 --- Problem Size Reduced by BTSR --- p.48 / Chapter 7.2.3 --- Revised BTSR Algorithm --- p.49 / Chapter 7.2.4 --- The Complexity Issues --- p.51 / Chapter 7.3 --- Performance and Complexity Issues for RDSA --- p.52 / Chapter Chapter 8 --- Conclusion and Future Work --- p.57 / Chapter 8.1 --- Conclusions --- p.57 / Chapter 8.2 --- Future Work --- p.58 / Bibliography

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.

In this thesis, we propose a novel trust management scheme for improving routing reliability in wireless ad hoc networks. It is grounded on two classic autoregression models, namely Autoregressive (AR) model and Autoregressive with exogenous inputs (ARX) model. According to this scheme, a node periodically measures the packet forwarding ratio of its every neighbor as the trust observation about that neighbor. These measurements constitute a time series of data. The node has such a time series for each neighbor. By applying an autoregression model to these time series, it predicts the neighbors future packet forwarding ratios as their trust estimates, which in turn facilitate it to make intelligent routing decisions. With an AR model being applied, the node only uses its own observations for prediction; with an ARX model, it will also take into account recommendations from other neighbors. We evaluate the performance of the scheme when an AR, ARX or Bayesian model is used. Simulation results indicate that the ARX model is the best choice in terms of accuracy.

The need for an effective clustering algorithm for Vehicle Ad Hoc Networks (VANETs) is motivated by the recent research in cluster-based MAC and routing schemes. VANETs are highly dynamic and have harsh channel conditions, thus a suitable clustering algorithm must be robust to channel error and must consider node mobility during cluster formation. This work presents a novel, mobility-based clustering scheme for Vehicle Ad hoc Networks, which forms clusters using the Affinity Propagation algorithm in a distributed manner. This proposed algorithm considers node mobility during cluster formation and produces clusters with high stability. Cluster performance was measured in terms of average cluster head duration, average cluster member duration, average rate of cluster head change, and average number of clusters. The proposed algorithm is also robust to channel error and exhibits reasonable overhead. Simulation results confirm the superior performance, when compared to other mobility-based clustering techniques.