An ad hoc network is a collection of mobile wireless devices that cooperate with each other to route packets amongst themselves. The main difficulty in designing routing algorithms for such a network is the large number of topology changes that the network undergoes due to device movement. Selective flooding is a routing technique that is more resilient to topology changes than traditional algorithms but is more bandwidth efficient than pure flooding. An on-demand selective flooding algorithm has been designed and tested on the ns-2 simulator. In scenarios involving a large number of topology changes, selective flooding outperforms other ad hoc network routing techniques. Unfortunately, selective flooding is much more bandwidth hungry and is unable to scale to handle reasonable traffic loads. Interestingly, the analysis of selective flooding reveals major problems with traditional ad hoc networking techniques. Many current algorithms demonstrate shortcomings when dealing with bursty traffic, and current wireless hardware cannot handle ad hoc networking traffic in an efficient manner. These issues need to be addressed before ad hoc networking technology can become feasible for widespread use.

Over the past decade or so, there has been rapid growth in wireless and mobile applications technologies. More recently, an increasing emphasis has been on the potential of infrastructureless wireless mobile networks that are easy, fast and inexpensive to set up, with the view that such technologies will enable numerous new applications in a wide range of areas. Such networks are commonly referred to as mobile ad hoc networks (MANETs). Exchanging sensitive information over unprotected wireless links with unidentified and untrusted endpoints demand the deployment of security in MANETs. However, lack of infrastructure, mobility and resource constraints of devices, wireless communication links and other unique features of MANETs induce new challenges that make implementing security a very difficult task and require the design of specialized solutions. This thesis is concerned with the design and analysis of security solutions for MANETs. We identify the initial exchange of authentication and key credentials, referred to as pre-authentication, as well as authentication and key exchange as primary security goals. In particular, the problem of pre-authentication has been widely neglected in existing security solutions, even though it is a necessary prerequisite for other security goals. We are the first to classify and analyze different methods of achieving pairwise pre-authentication in MANETs. Out of this investigation, we identify identity-based cryptographic (IBC) schemes as well-suited to secure MANET applications that have no sufficient security solutions at this time. We use pairing-based IBC schemes to design an authentication and key exchange framework that meets the special requirements of MANETs. Our solutions are comprised of algorithms that allow for efficient and secure system set up, pre-authentication, mutual authentication, key establishment, key renewal, key revocation and key escrow prevention. In particular, we present the first fully self-organized key revocation scheme for MANETs that does not require any trusted third party in the network. Our revocation scheme can be used to amend existing IBC solutions, be seamlessly integrated in our security framework and even be adopted to conventional public key solutions for MANETs. Our scheme is based on propagated accusations and once the number of received accusations against a node reaches a defined threshold, the keys of the accused nodes are revoked. All communications are cryptographically protected, but unlike other proposed schemes, do not require computationally demanding digital signatures. Our scheme is the first that efficiently and securely enables nodes to revoke their own keys. Additionally, newly joining nodes can obtain previous accusations without performing computationally demanding operations such as verifying digital signatures. Several security and performance parameters make our scheme adjustable to the hostility of the MANET environment and the degree of resource constraints of network and devices. In our security analysis we show how security parameters can be selected to prevent attacks by colluding nodes and roaming adversaries. In our proposed security framework, we utilize special properties of pairing-based keys to design an efficient and secure method for pairwise pre-authentication and a set of ID-based authenticated key exchange protocols. In addition, we present a format for ID-based public keys that, unlike other proposed formats, allows key renewal before the start of a new expiry interval. Finally, we are the first to discuss the inherent key escrow property of IBC schemes in the context of MANETs. Our analysis shows that some special features of MANETs significantly limit the escrow capabilities of key generation centers (KGCs). We propose a novel concept of spy nodes that can be utilized by KGCs to increase their escrow capabilities and analyze the probabilities of successful escrow attacks with and without spy nodes. In summary, we present a complete authentication and key exchange framework that is tailored for MANET applications that have previously lacked such security solutions. Our solutions can be implemented using any pairing-based IBC scheme. The component design allows for the implementation of single schemes to amend existing solutions that do not provide certain functionalities. The introduction of several security and performance parameters make our solutions adjustable to different levels of resource constraints and security needs. In addition, we present extensions that make our solutions suitable for applications with sporadic infrastructure access as envisioned in the near future.

As a result of the recent advances in the computation and communications industries, wireless communications-enabled computing devices are ubiquitous nowadays. Even though these devices are introduced to satisfy the user’s mobile computing needs, they are still unable to provide for the full mobile computing functionality as they confine the user mobility to be within certain regions in order to benefit from services provided by fixed network access points. Mobile ad hoc networks (MANETs) are introduced as the technology that potentially will make the nowadays illusion of mobile computing a tangible reality. MANETs are created by the mobile computing devices on an ad hoc basis, without any support or administration provided by a fixed or pre-installed communications infrastructure. Along with their appealing autonomy and fast deployment properties, MANETs exhibit some other properties that make their realization a very challenging task. Topology dynamism and bandwidth limitations of the communication channel adversely affect the performance of routing protocols designed for MANETs, especially with the increase in the number of mobile hosts and/or mobility rates. The Connected Dominating Set (CDS), a.k.a. virtual backbone or Spine, is proposed to facilitate routing, broadcasting, and establishing a dynamic infrastructure for distributed location databases. Minimizing the CDS produces a simpler abstracted topology of the MANET and allows for using shorter routes between any pair of hosts. Since it is NP-complete to find the minimum connected dominating set, MCDS, researchers resorted to approximation algorithms and heuristics to tackle this problem. The literature is rich of many CDS approximation algorithms that compete in terms of CDS size, running time, and signaling overhead. It has been reported that localized CDS creation algorithms are the fastest and the lightest in terms of signaling overhead among all other techniques. Examples of these localized CDS algorithms are Wu and Li algorithm and its Stojmenovic variant, the MPR algorithm, and Alzoubi algorithm. The designers of each of these algorithms claim that their algorithm exhibits the highest degree of localization and hence incurs the lowest cost in the CDS creation phase. However, these claims are not supported by any physical or at least simulation-based evidence. Moreover, the cost of maintaining the CDS (in terms of the change in CDS size, running time, and signaling overhead), in the presence of unpredictable and frequent topology changes, is an important factor that has to be taken into account -a cost that is overlooked most of the time. A simulation-based comparative study between the performance of these algorithms will be conducted using the ns2 network simulator. This study will focus on the total costs incurred by these algorithms in terms of CDS size, running time, and signaling overhead generated during the CDS creation and maintenance phases. Moreover, the effects of mobility rates, network size, and mobility models on the performance of each algorithm will be investigated. Conclusions regarding the pros and cons of each algorithm will be drawn, and directions for future research work will be recommended.

This thesis contributes toward the design of a quality-of-service (QoS) aware network layer for wireless ad hoc networks. With the lack of an infrastructure in ad hoc networks, the role of the network layer is not only to perform multihop routing between a source node and a destination node, but also to establish an end-to-end connection between communicating peers that satisfies the service level requirements of multimedia applications running on those peers. Wireless ad hoc networks represent autonomous distributed systems that are infrastructure-less, fully distributed, and multi-hop in nature. Over the last few years, wireless ad hoc networks have attracted significant attention from researchers. This has been fueled by recent technological advances in the development of multifunction and low-cost wireless communication gadgets. Wireless ad hoc networks have diverse applications spanning several domains, including military, commercial, medical, and home networks. Projections indicate that these self-organizing wireless ad hoc networks will eventually become the dominant form of the architecture of telecommunications networks in the near future. Recently, due to increasing popularity of multimedia applications, QoS support in wireless ad hoc networks has become an important yet challenging objective. The challenge lies in the need to support the heterogeneous QoS requirements (e.g., data rate, packet loss probability, and delay constraints) for multimedia applications and, at the same time, to achieve efficient radio resource utilization, taking into account user mobility and dynamics of multimedia traffic. In terms of research contributions, we first present a position-based QoS routing framework for wireless ad-hoc networks. The scheme provides QoS guarantee in terms of packet loss ratio and average end-to-end delay (or throughput) to ad hoc networks loaded with constant rate traffic. Via cross-layer design, we apply call admission control and temporary bandwidth reservation on discovered routes, taking into consideration the physical layer multi-rate capability and the medium access control (MAC) interactions such as simultaneous transmission and self interference from route members. Next, we address the network-layer resource allocation where a single-hop ad hoc network is loaded with random traffic. As a starting point, we study the behavior of the service process of the widely deployed IEEE 802.11 DCF MAC when the network is under different traffic load conditions. Our study investigates the near-memoryless behavior of the service time for IEEE 802.11 saturated single-hop ad hoc networks. We show that the number of packets successfully transmitted by any node over a time interval follows a general distribution, which is close to a Poisson distribution with an upper bounded distribution distance. We also show that the service time distribution can be approximated by the geometric distribution and illustrate that a simplified queuing system can be used efficiently as a resource allocation tool for single hop IEEE 802.11 ad hoc networks near saturation. After that, we shift our focus to providing probabilistic packet delay guarantee to multimedia users in non-saturated IEEE 802.11 single hop ad hoc networks. We propose a novel stochastic link-layer channel model to characterize the variations of the IEEE 802.11 channel service process. We use the model to calculate the effective capacity of the IEEE 802.11 channel. The channel effective capacity concept is the dual of the effective bandwidth theory. Our approach offers a tool for distributed statistical resource allocation in single hop ad hoc networks, which combines both efficient resource utilization and QoS provisioning to a certain probabilistic limit. Finally, we propose a statistical QoS routing scheme for multihop IEEE 802.11 ad hoc networks. Unlike most of QoS routing schemes in literature, the proposed scheme provides stochastic end-to-end delay guarantee, instead of average delay guarantee, to delay-sensitive bursty traffic sources. Via a cross-layer design approach, the scheme selects the routes based on a geographical on-demand ad hoc routing protocol and checks the availability of network resources by using traffic source and link-layer channel models, incorporating the IEEE 802.11 characteristics and interaction. Our scheme extends the well developed effective bandwidth theory and its dual effective capacity concept to multihop IEEE 802.11 ad hoc networks in order to achieve an efficient utilization of the shared radio channel while satisfying the end-to-end delay bound.

Middleware has become a key enabler for the development of distributed applications. Unfortunately, conventional middleware technologies do not yet offer sufficient functionality to make them suitable for mobile environments. This dissertation proposes a novel middleware approach termed opportunistic overlays and its dynamically reconfigurable support framework for building efficient mobile applications. Specifically, we address the inefficiency of content delivery introduced by node mobility and by dynamically changing system loads, in the context of publish/subscribe systems. In response to changes in physical network topology, in nodes' physical locations, and in network node behaviors, the opportunistic overlay approach dynamically adapts event dissemination structures (i.e., broker overlays) with the goal of optimizing end-to-end delays in event delivery. Adaptation techniques include the dynamic construction of broker overlay networks, runtime changes of mobile clients' assignments to brokers, and dynamic broker load balancing. Essentially, opportunistic overlays implement a middleware-level analogue of the networking routing protocols used in wireless communications (i.e., Mobile IP, AODV, DSR and DSDV). By thus coordinating network- with middleware-level routing, opportunistic overlays can attain substantial performance improvements over non-adaptive event systems. Such improvements are due to their use of shorter network paths and better balancing of loads across event brokers. Opportunistic overlays and the adaptive methods they use are realized by a set of distributed protocols implemented in a Java-based publish/subscribe infrastructure. Comprehensive performance evaluations are performed via simulation, emulation, and with two representative applications on actual networks. Experimental results demonstrate that the opportunistic overlay approach is practically applicable and that the performance advantages attained from the use of opportunistic overlays can be substantial, in both infrastructure-based mobile environments and mobile ad hoc networks.

A mobile ad hoc network (MANET) consists of a group of autonomous mobile nodes with no infrastructure support. In this research, we develop a distributed intrusion detection and response system for MANET, and we believe it presents a second line of defense that cannot be replaced by prevention schemes. We based our detection framework on the study of attack taxonomy. We then propose a set of detection methods suitable of detecting different attack categories. Our approaches are based on protocol specification analysis with categorical and statistical measures. Node-based approaches may be too restrictive in scenarios where attack patterns cannot be observed by any isolated node. Therefore, we have developed cooperative detection approaches for a more effective detection model. One approach is to form IDS clusters by grouping nearby nodes, and information can be exchanged within clusters. The cluster-based scheme is more efficient in terms of power consumption and resource utilization, it is also proved resilient against common security compromises without changing the decentralized assumption. We further address two response techniques, traceback and filtering. Existing traceback systems are not suitable for MANET because they rely on incompatible assumptions such as trustworthy routers and static route topology. Our solution, instead, adapts to dynamic topology with no infrastructure requirement. Our solution is also resilient in the face of arbitrary number of collaborative adversaries. We also develop smart filtering schemes to maximize the dropping rate of attack packets while minimizing the dropping rate of normal packets with real-time guarantee. To validate our research, we present case study using both ns-2 simulation and MobiEmu emulation platform with three ad hoc routing protocols: AODV, DSR and OLSR. We implemented various representative attacks based on the attack taxonomy. Our experiments show very promising results using node-based and cluster-based approaches.

In this work, we consider the channel assignment problem in single radio multi-channel mobile ad-hoc networks. Specifically, we investigate the granularity of channel assignment decisions that gives the best trade-off in terms of performance and complexity. We present a new granularity for channel assignment that we refer to as component level channel assignment. The strategy is relatively simple, and is characterized by several impressive practical advantages. We also show that the theoretical performance of the component based channel assignment strategy does not lag significantly behind the optimal possible performance, and perhaps more importantly we show that when coupled with its several practical advantages, it significantly outperforms other strategies under most network conditions.

Ad hoc network is a new tendency of data transmission in the future. Because of the convenience and necessity of mobile phone and/or portable computer coupled with wireless data services, TCP/IP has become an important topic for the study in wireless networks. However, there were a few difficulties in data transmission that must be overcome due to ad hoc environments and the characteristics of the IEEE 802.11 protocols. In these protocols, MAC layer is our primary research topic. Based on the RTS/CTS signal of dynamic retransmission [4], this study presented an improvement to solve the problems: (1) media resources was easily robbed due to the RTS/CTS signal competition, (2) data frame would be dropped by the IEEE 802.11 protocol due to too many times collisions. In addition, this study modifies the CWND in TCP layer in accordance with congestion conditions. Sender can transmit data packets to the network, in which resources can be completely utilized without any waste or loss. We also use the related parameters from the IP and TCP header to calculate flow numbers. The calculated parameters are recorded in IP and TCP header, and then instantly forwarded to the receiver via routers. The receiver can forward these parameters back to the sender by using back transmission method. The simulation result shows that the proposed methods can effectively improve TCP performance, such as packet loss rate, and fastly increase the CWND, the buffer utilization, and so forth. Thus, the network can perform more effectively while using the MAC-layer RTS/CTS signal.

In this thesis, we proposed a delay limited routing scheme in wireless ad hoc networks. When nodes transmit packets in wireless ad hoc networks, most people think the one-hop way is better than the multi-hop way in reducing the delay time. Since most cases in wireless ad hoc networks are not single sources, we should consider at least two sources transmitting packets at the same time and then use the multi-hop way in order to reduce the energy consumption. We want to maximize the throughput with limited delay. Our contribution is to transform the optimal scheduling problem in wireless ad hoc networks to the classic maximum flow problem. The maximum flow approach does maximize the throughput and can get the optimal solution.

In this thesis, we consider how to reduce the communication cost of the key exchange procedures as many as possible, while the secure group communication can still be achieved. Due to the energy consumption is usually proportional to the distance, we use the shortest paths algorithm to find the shortest communication paths between any pair of the secure group members. We first propose a straightforward heuristic named Minimum-Energy First-Selected ( MEFS ). MEFS tries to select the pair of group members which has less communication cost than all other pairs have at every time. Though MEFS performs better than random selecting, it still has some weakness in solving the energy-aware key management problem. So we use the concept of the minimum cost flow problem, and by appropriate transformation, then we get the optimal solution of the energy-aware key management problem under some constraints. At last, the simulation results proves that the minimum cost flow approach actually works better than MEFS does.