Browsing by Subject "Mobile Ad Hoc Networks"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Communication Algorithms for Wireless Ad Hoc Networks(2012-10-19) Viqar, SairaIn this dissertation we present deterministic algorithms for reliable and efficient communication in ad hoc networks. In the first part of this dissertation we give a specification for a reliable neighbor discovery layer for mobile ad hoc networks. We present two different algorithms that implement this layer with varying progress guarantees. In the second part of this dissertation we give an algorithm which allows nodes in a mobile wireless ad hoc network to communicate reliably and at the same time maintain local neighborhood information. In the last part of this dissertation we look at the distributed trigger counting problem in the wireless ad hoc network setting. We present a deterministic algorithm for this problem which is communication efficient in terms of the the maximum number of messages received by any processor in the system.Item Design and analysis of distributed primitives for mobile ad hoc networks(Texas A&M University, 2006-10-30) Chen, YuThis dissertation focuses on the design and analysis of distributed primitives for mobile ad hoc networks, in which mobile hosts are free to move arbitrarily. Arbitrary mobility adds unpredictability to the topology changes experienced by the network, which poses a serious challenge for the design and analysis of reliable protocols. In this work, three different approaches are used to handle mobility. The first part of the dissertation employs the simple technique of ignoring the mobility and showing a lower bound for the static case, which also holds in the mobile case. In particular, a lower bound on the worstcase running time of a previously known token circulation algorithm is proved. In the second part of the dissertation, a self-stabilizing mutual exclusion algorithm is proposed for mobile ad hoc networks, which is based on dynamic virtual rings formed by circulating tokens. The difficulties resulting from mobility are dealt with in the analysis by showing which properties hold for several kinds of mobile behavior; in particular, it is shown that mutual exclusion always holds and different levels of progress hold depending on how the mobility affects the token circulation. The third part of the dissertation presents two broadcasting protocols which propagate a message from a source node to all of the nodes in the network. Instead of relying on the frequently changing topology, the protocols depend on a less frequently changing and more stable characteristic ?????? the distribution of mobile hosts. Constraints on distribution and mobility of mobile nodes are given which guarantee that all the nodes receive the broadcast data.Item Information Infrastructures in Distributed Environments: Algorithms for Mobile Networks and Resource Allocation(2013-10-28) Chung, Hyun-ChulA distributed system is a collection of computing entities that communicate with each other to solve some problem. Distributed systems impact almost every aspect of daily life (e.g., cellular networks and the Internet); however, it is hard to develop services on top of distributed systems due to the unreliable nature of computing entities and communication. As handheld devices with wireless communication capabilities become increasingly popular, the task of providing services becomes even more challenging since dynamics, such as mobility, may cause the network topology to change frequently. One way to ease this task is to develop collections of information infrastructures which can serve as building blocks to design more complicated services and can be analyzed independently. The first part of the dissertation considers the dining philosophers problem (a generalization of the mutual exclusion problem) in static networks. A solution to the dining philosophers problem can be utilized when there is a need to prevent multiple nodes from accessing some shared resource simultaneously. We present two algorithms that solve the dining philosophers problem. The first algorithm considers an asynchronous message-passing model while the second one considers an asynchronous shared-memory model. Both algorithms are crash fault-tolerant in the sense that a node crash only affects its local neighborhood in the network. We utilize failure detectors (system services that provide some information about crash failures in the system) to achieve such crash fault-tolerance. In addition to crash fault-tolerance, the first algorithm provides fairness in accessing shared resources and the second algorithm tolerates transient failures (unexpected corruptions to the system state). Considering the message-passing model, we also provide a reduction such that given a crash fault-tolerant solution to our dining philosophers problem, we implement the failure detector that we have utilized to solve our dining philosophers problem. This reduction serves as the first step towards identifying the minimum information regarding crash failures that is required to solve the dining philosophers problem at hand. In the second part of this dissertation, we present information infrastructures for mobile ad hoc networks. In particular, we present solutions to the following problems in mobile ad hoc environments: (1) maintaining neighbor knowledge, (2) neighbor detection, and (3) leader election. The solutions to (1) and (3) consider a system with perfectly synchronized clocks while the solution to (2) considers a system with bounded clock drift. Services such as neighbor detection and maintaining neighbor knowledge can serve as a building block for applications that require point-to-point communication. A solution to the leader election problem can be used whenever there is a need for a unique coordinator in the system to perform a special task.Item Intrusion detection in mobile ad hoc networks(Texas A&M University, 2005-08-29) Sun, BoMost existent protocols, applications and services for Mobile Ad Hoc NET-works (MANETs) assume a cooperative and friendly network environment and do not accommodate security. Therefore, Intrusion Detection Systems (IDSs), serving as the second line of defense for information systems, are indispensable for MANETs with high security requirements. Central to the research described in this dissertation is the proposed two-level nonoverlapping Zone-Based Intrusion Detection System (ZBIDS) which fit the unique requirement of MANETs. First, in the low-level of ZBIDS, I propose an intrusion detection agent model and present a Markov Chain based anomaly detection algorithm. Local and trusted communication activities such as routing table related features are periodically selected and formatted with minimum errors from raw data. A Markov Chain based normal profile is then constructed to capture the temporal dependency among network activities and accommodate the dynamic nature of raw data. A local detection model aggregating abnormal behaviors is constructed to reflect recent subject activities in order to achieve low false positive ratio and high detection ratio. A set of criteria to tune parameters is developed and the performance trade-off is discussed. Second, I present a nonoverlapping Zone-based framework to manage locally generated alerts from a wider area. An alert data model conformed to the Intrusion Detection Message Exchange Format (IDMEF) is presented to suit the needs of MANETs. Furthermore, an aggregation algorithm utilizing attribute similarity from alert messages is proposed to integrate security related information from a wider area. In this way, the gateway nodes of ZBIDS can reduce false positive ratio, improve detection ratio, and present more diagnostic information about the attack. Third, MANET IDSs need to consider mobility impact and adjust their behavior dynamically. I first demonstrate that nodes?? moving speed, a commonly used parameter in tuning IDS performance, is not an effective metric for the performance measurement of MANET IDSs. A new feature -link change rate -is then proposed as a unified metric for local MANET IDSs to adaptively select normal profiles . Different mobility models are utilized to evaluate the performance of the adaptive mechanisms.