Search

In mobile ad hoc networks transmission-scheduling channel-access protocols are of interest because they can ensure collision free transmissions and provide fair access to the channel. The time taken to gain access to the channel is deterministic and hence these types of protocols can also guarantee a certain quality of service. However, these protocols suffer from two major drawbacks. The first issue is poor utilization of the channel due to fixed slot assignments. Once the slot assignments are decided they are held constant for a period of time. As a result the node to which a slot is assigned may not always have a packet to transmit in its assigned slot. This results in wasted slots and leads to poor utilization of the channel. The second issue is that there is no support for networks with rate adaptive radios. In this work a combined solution to both of these shortcomings is presented. In order to make transmission-scheduling channel-access protocols support networks with rate adaptive radios, a process called slot-packing is developed. The design of slot-packing ensures that it works with any transmission-scheduling channel-access protocol. Using slot-packing, we design and investigate a new protocol called adaptive recovering mini-slot transmission scheduling (RMTS-a) that tackles both the shortcomings and improves the performance of the network significantly. A key feature of our RMTS-a protocol is that if a radio assigned to a transmission opportunity is unable to utilize all of the time slot, other radios in the local neighborhood are given the opportunity to transmit in the remaining time. Additionally, because multiple radios within communication range of a transmitter are likely to be able to decode the payload, packets to multiple neighbors can be packed within a single transmission.

Ad hoc networks provide a flexible, infrastructure-free means to communicate between soldiers in war zones, aid workers in disaster areas, or consumers in device-to-device (D2D) applications. Ad hoc networks, however, are stilled plagued by interference. Communication with millimeter-wave (mmWave) devices offers hope to ad hoc networks through higher bandwidth, reduced interference due to directional antennas, and a lighter interference field due to blockage. This report uses a stochastic geometry approach to characterize the one-way and two-way coverage probability of a mmWave ad hoc network with directional antennas and random blockages. The coverage probability in the presence of noise and both line-of-sight and non-line-of-sight interference is analyzed and used to derive the transmission capacity. Several reasonable simplifications are used to derive the transmission capacity. Performance of mmWave is then analyzed in terms of area spectral efficiency and rate coverage. The results show that mmWave networks support larger densities, higher area spectral efficiencies, and better rate coverage compared to microwave ad hoc networks.

Vehicular networking is a new emerging wireless technology that supports the communication amongst vehicles and enables vehicles to connect with the Internet. This networking technology provides vehicles with endless possibility of applications, including safety, convenience, and entertainment applications. Examples for these applications are safety messaging, real-time traffic, route updates, and general purpose Internet access. The goal of vehicular networks is to provide an efficient, safe, and convenient environment for the vehicles. In vehicular networking technology, vehicles connect either through other vehicles in an ad-hoc multi-hop fashion or through road side units (infrastructure) which connects them to the Internet. Each approach has its own advantages and disadvantages. However, one of the main objectives of vehicular networking is to achieve a minimal delay for message delivery, and encourage a continuous connectivity for vehicles.This dissertation introduces a novel hybridcommunication paradigm for achievingseamless connectivity in Vehicular Ad-hoc NETworks (VANET), wherein the connectivity is often affected by changes in thedynamic topology, vehicles' speed, as well as trafficdensity. Our proposed technique ---named QoS-orientedHybrid Vehicular Communications Protocol (QoSHVCP)--- exploits bothexisting network infrastructure through a Vehicle-to-Infrastructure(V2I) protocol, as well as a traditional Vehicle-to-Vehicle (V2V), that satisfies Quality-of-Service requirements. Weanalyze time delay as a performance metric, and determine delaypropagation rates when vehicles are transmitting high prioritymessages via QoSHVCP.Focusing on V2V communication, we propose a novel reliable and low-collision packet-forwarding scheme, based on a probabilistic rebroadcasting. Our proposed scheme, called Collision-Aware REliable FORwarding (CAREFOR), works in a distributed fashion where each vehicle receiving a packet, rebroadcasts it based on a predefined probability. The success of rebroadcast is determined based on allowing the message to travel the furthest possible distance with the least amount of packet rebroadcast collision. Moreover, we present a QoS-Aware node Selection Algorithm (QASA) for VANET routing protocols. Our algorithm is focused on selecting the vehicle to communicate with, and is achieved by exploiting the bridging approach for message forwarding i.e., vehicles on the east (west) select from west (east). The QoS metrics that are being optimized are the throughput in the network, as well as end-to-end delay for packets. Finally, we exploit the use of autonomous vehicles in order to optimize the end-to-end packet delivery delay. Our protocol introduces a dynamic metric that depends on the vehicular density on the highway in order to control the inter-vehicle distance.Our results show a great promise for their future use in vehicular technology.

Managing interference is the main technical challenge in wireless networks. Multiple input multiple output (MIMO) methods are key components to overcome the interference bottleneck and deliver higher data rates. The most efficient MIMO techniques require channel state information (CSI). In practice, this information is inaccurate due to errors in CSI acquisition, as well as mobility and delay. CSI inaccuracy reduces the performance gains provided by MIMO. When compounded with uncoordinated intercell interference, the degradation in MIMO performance is accentuated. This dissertation investigates the impact of CSI inaccuracy on the performance of increasingly complex interference limited networks, starting with a single interferer scenario, continuing to a heterogeneous network with a femtocell overlay, and finishing with a clustered multicell coordination model for randomly deployed transmitting nodes. First, this dissertation analyzes limited feedback beamforming and precoded spatial multiplexing over temporally correlated channels. Assuming uncoordinated interference from one dominant interferer, using Markov chain convergence theory, the gain in the average successful throughput at the mobile user is shown to decrease exponentially with the feedback delay. The decay rate is amplified when the user is interference limited. Interference cancellation methods at the receiver are shown to mitigate the effect of interference. This work motivates the need for practical MIMO designs to overcome the adverse effects of interference. Second, limited feedback beamforming is analyzed on the downlink of a more realistic heterogeneous cellular network. Future generation cellular networks are expected to be heterogeneous, consisting of a mixture of macro base stations and low power nodes, to support the increasing user traffic capacity and reliability demand. Interference in heterogeneous environments cannot be coordinated using traditional interference mitigation techniques due to the on demand and random deployment of low power nodes such as femtocells. Using tools from stochastic geometry, the outage and average achievable rate of limited feedback MIMO is computed with same-tier and cross-tier interference, and feedback delay. A hybrid fixed and random network deployment model is used to analyze the performance in a fixed cell of interest. The maximum density of transmitting femtocells is derived as a function of the feedback rate and delay. The detrimental effect of same-tier interference is quantified, as the mobile user moves from the cell-center to the cell-edge. The third part of this dissertation considers limited coordination between randomly deployed transmitters. Building on the established degrading effect of uncoordinated interference on practical MIMO methods, and the analytical tractability of random deployment models, interference coordination is analyzed. Using multiple antennas at the transmitter for interference nulling in ad hoc networks is first shown to achieve MIMO gains using single antenna receivers. Clustered coordination is then investigated for cellular systems with randomly deployed base stations. As full coordination in the network is not feasible, a random clustering model is proposed where base stations located in the same cluster coordinate. The average achievable rate can be optimized as a function of the number of antennas to maximize the coordination gains. For multicell limited feedback, adaptive partitioning of feedback bits as a function of the signal and interference strength is proposed to minimize the loss in rate due to finite rate feedback.

Protocol designs targeted at a specific network scenario or performance metric appear promising on paper, but the complexity and cost of implementing and tuning a routing protocol from scratch presents a major bottleneck in the protocol design process. A unique framework called 'Orchestra` is proposed in the literature to support the testing and development of novel routing designs. The idea of the Orchestra framework is to create generic and reusable routing functional components which can be combined to create unique protocol designs customized for a specific performance metric or network setting. The first contribution of this thesis is the development of a generic, modular, scalable and extensible architecture of the Orchestra framework. Once the architecture and implementation of the framework is completed, the second contribution of this thesis is the development of functional components and strategies to design and implement routing protocols for delay tolerant networks (DTNs). DTNs are a special type of ad hoc network characterized by intermittent connectivity, long propagation delays and high loss rate. Thus, traditional ad hoc routing approaches cannot be used in DTNs, and special features must be developed for the Orchestra framework to support the design of DTN routing protocols. The component-based architecture of Orchestra can capture a variety of modules that can be used to assemble a routing protocol. However, manually assembling these components may result in suboptimal designs, because it is difficult to determine what the best combination is for a particular set of performance objectives and network characteristics. The third contribution of the thesis addresses this problem. A genetic algorithm based approach to automate the process of routing protocol design is developed and its performance is evaluated in the context of the Orchestra framework.

In wireless networks, devices (nodes) are connected by wireless links. An important issue is to set up high quality (high bandwidth) and efficient routing paths when one node wants to send packets to other nodes. Resource allocation is the foundation to guarantee high quality connections. In addition, it is critical to handle void areas in order to set up detour-free paths. Moreover, fast message broadcasting is essential in mobile wireless networks. Thus, my research includes dynamic channel allocation in wireless mesh networks, geographic routing in Ad Hoc networks, and message broadcasting in vehicular networks. The quality of connections in a wireless mesh network can be improved by equip- ping mesh nodes with multi-radios capable of tuning to non-overlapping channels. The essential problem is how to allocate channels to these multi-radio nodes. We develop a new bipartite-graph based channel allocation algorithm, which can improve bandwidth utilization and lower the possibility of starvation. Geographic routing in Ad Hoc networks is scalable and normally loop-free. However, traditional routing protocols often result in long detour paths when holes exist. We propose a routing protocol-Intermediate Target based Geographic Routing (ITGR) to solve this problem. The novelty is that a single forwarding path can be used to reduce the lengths of many future routing paths. We also develop a protocol called Hole Detection and Adaptive Geographic Routing, which identifies the holes efficiently by comparing the length of a routing path with the Euclidean distance between a pair of nodes. We then set up the shortest path based on it. Vehicles play an important role in our daily life. During inter-vehicle communication, it is essential that emergency information can be broadcast to surrounding vehicles quickly. We devise an approach that can find the best re-broadcasting node and propagate the message as fast as possible.

This thesis is concerned with the development and analysis of a new hybrid location-based routing protocol for ad hoc wireless networks. A feature that permeates throughout this work is the use of all available location information within the network in order to minimize the routing overhead. Such minimization leads to an enhanced scalability performance for the network. More directly, we can say the main contribution of this thesis is that it introduces a new Hybrid Location-based Ad-hoc Routing protocol (HLAR) designed specifically with optimal scalability performance in mind. The HLAR protocol combines features of reactive routing with geographic routing in such a manner so as to efficiently use all location information available, and to gracefully exit to reactive routing as the location information degrades. An important aspect of HLAR is that it can be spatially dependent - meaning different physical areas of the network may utilize different routing procedures simultaneously. A key feature of HLAR is the consideration given to realistic location errors within the protocol design. Through detailed analysis and detailed Monte Carlo simulations we investigate the scalability of the HLAR protocol within different environments and different target applications. A particular focus is the use of HLAR within the Vehicular ad hoc Network (VANET) environment. We demonstrate how HLAR is the ideal routing protocol for emerging VANET systems in that it produces effectively optimal scalability over a wide range of the anticipated environment variables. We demonstrate that similar scalability performance is expected for slower moving pedestrian ad hoc networks. We also introduce a simplified version of HLAR, which we refer to as Geographic Routing with Congestion Avoidance (GRCA), which is specifically designed for VoIP applications. The GRCA protocol couples a congestion avoidance algorithm specifically designed for VoIP, to a greedy geographic forwarding algorithm in order to deliver two key attributes that hitherto are not simultaneously present in any other single ad hoc routing protocol. Specifically, GRCA maximizes VoIP capacity whilst remaining scalable, and obtains an up-to factor of two improvement in VoIP capacity relative to other well known ad hoc routing protocols.

In this thesis, ad hoc networks with frequency-agile radios utilizing omni-directional and directional antennas form the basis of study. This work focuses on the selection of channel-access and routing protocols for these networks. Findings demonstrate that protocol selection must occur jointly in order to increase the efficient utilization of available spectrum while achieving maximum network performance. In this thesis, we investigate several channel-access methods that provide different ways of selecting one of the heterogeneous non-overlapping channels for transmission. We also investigate a modification of least-resistance routing that accounts for the variations in transmission channels. Through simulation, we find that better network performance can be achieved when the channel-access and routing protocols are considered jointly. Additionally, we examine the difference in protocol selection when using a network consisting of terminals equipped with omni-directional antennas and when using a network in which some of the terminals employ directional antennas. Finally, we explore a channel busyness metric as a means of assisting with an adaptive, distributed protocol, while the development of such a distributed protocol is left for future work.

We investigate strategies to improve the performance of transmission schedules for mobile ad hoc networks (MANETs) employing adaptive direct-sequence spread-spectrum (DSSS) modulation. Previously, scheduling protocols for MANETs have been designed under the assumption of an idealized, narrowband wireless channel. These protocols perform poorly when the channel model incorporates distance-based path loss and co-channel interference. Wideband communication systems, such as DSSS systems, are more robust in the presence of co-channel interference; however, DSSS also provides multiple-access capability that cannot be properly leveraged with a protocol designed for narrowband systems. We present a new transmission scheduling protocol that incorporates link characteristics, spreading factor adaptation, and packet capture capability into scheduling and routing decisions. This provides greater spatial reuse of the channel and better adaptability in mobile environments. Simulation results demonstrate the merits of this approach in terms of end-to-end packet throughput, delay, and completion rate for unicast traffic. We also discuss two variations of the protocol: one provides a method for enhancing the network topology through exchange of local information, and the other leverages multi-packet reception (MPR) capability to enhance the network topology. We show that each approach is useful in networks with sparse connectivity. We conclude by studying the capacity of the networks used in previous sections, providing insight on methods for realizing further performance gains.

In a distributed wireless system, multiple network nodes behave cooperatively towards a common goal. Though such assumptions on cooperation are desirable (e.g., controlling the transmit power level, reducing interference for each other, revealing private information, adhering to network policies) for analyzing and modeling, certain nodes belonging to a real-world system have often shown to deviate. These nodes, known as misbehaving nodes, bring more challenges to the design of the wireless network because the unreliable channel makes the actions of the nodes hidden from each other. In this dissertation, we analyze two types of misbehavior, namely, selfish noncooperation and malicious attacking. We apply game theoretic techniques to model the interactions among the nodes in the network. First, we consider a homogeneous unreliable channel and analyze the necessary and sufficient conditions to enforce cooperative packet forwarding among a node pair. We formulate an anti-collusion game and derive the conditions that achieve full cooperation when the non-cooperative nodes collude. In addition, we consider multi-hop communication with a heterogeneous channel model. We refine our game model as a hidden action game with imperfect private monitoring. A state machine based strategy is proposed to reach Nash Equilibrium. The strategy attains cooperative packet forwarding with heterogeneous channel and requires only partial and imperfect information. Furthermore, it also enforces cooperation in multi-hop packet forwarding. To tackle the malicious attacks, we use Bayesian game analysis to show the existence of equilibrium in the detection game and argue that it might not be profitable to isolate the malicious nodes upon detection. We propose the concept of "coexistence with malicious nodes" by proving the co-existence equilibrium and derive the conditions that achieve the equilibrium. This research is further accomplished by extensive simulation studies. Simulation results illustrate the properties of the games and the derived equilibria. The results validate our design philosophy and clearly indicate that the proposed game theoretic solutions can be effectively used to enforce cooperation and mitigate attacks.

This thesis aims at contributing to the field of cooperative AHNs. The focus of this research is on the relay based MAC layer: design of cooperative MAC protocols, performance modelling, and protocol enhancements. The first contribution of this thesis is dedicated to the modelling of energy consumption which aids MAC protocol developers in the design phase to devise efficient protocols and energy saving solutions. This model can predict energy consumption in an ideal and non-ideal environment. It is shown that using a relay results in not only better throughput but also higher energy efficiency. In the next contribution, we propose an Enhanced relay-enabled Distributed Coordination Function (ErDCF), which uses high data rate nodes to work as relays for the low data rate nodes. ErDCF in saturation achieves higher throughput, lower delay and lower energy consumption as compared to conventional 802.11 Distributed Coordination Function (DCF) in ideal conditions. The performance of ErDCF under non-ideal condition is evaluated and it proves that the gain of ErDCF can still be maintained under reasonable link quality and distance. Finally a multiple relay MAC protocol is proposed and its performance is evaluated. The results confirm the throughput advantage of multiple relays, but they also show that beyond two relays the throughput gain becomes increasingly marginal due to the cost of higher overhead.

A mobile wireless ad hoc network (MANET) consists of a group of mobile nodes communicating wirelessly with no fixed infrastructure. Each node acts as source or receiver, and all play a role in path discovery and packet routing. MANETs are growing in popularity due to multiple usage models, ease of deployment and recent advances in hardware with which to implement them. MANETs are a natural environment for multicasting, or group communication, where one source transmits data packets through the network to multiple receivers. Proposed applications for MANET group communication ranges from personal network apps, impromptu small scale business meetings and gatherings, to conference, academic or sports complex presentations for large crowds reflect the wide range of conditions such a protocol must handle. Other applications such as covert military operations, search and rescue, disaster recovery and emergency response operations reflect the "mission critical" nature of many ad hoc applications. Reliable data delivery is important for all categories, but vital for this last one. It is a feature that a MANET group communication protocol must provide. Routing protocols for MANETs are challenged with establishing and maintaining data routes through the network in the face of mobility, bandwidth constraints and power limitations. Multicast communication presents additional challenges to protocols. In this dissertation we study reliability in multicast MANET routing protocols. Several on-demand multicast protocols are discussed and their performance compared. Then a new reliability protocol, R-ODMRP is presented that runs on top of ODMRP, a well documented "best effort" protocol with high reliability. This protocol is evaluated against ODMRP in a standard network simulator, ns-2. Next, reliable multicast MANET protocols are discussed and compared. We then present a second new protocol, Reyes, also a reliable on-demand multicast communication protocol. Reyes is implemented in the ns-2 simulator and compared against the current standards for reliability, flooding and ODMRP. R-ODMRP is used as a comparison point as well. Performance results are comprehensively described for latency, bandwidth and reliable data delivery. The simulations show Reyes to greatly outperform the other protocols in terms of reliability, while also outperforming R-ODMRP in terms of latency and bandwidth overhead.

Publish/subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this thesis, we present, evaluate benefits of, and compare with past work, an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.

In this thesis we investigate the performance of direct sequence spread spectrum(DS-SS) overlay ad hoc networks by performing computer simulations and numericalevaluations based upon mathematical analysis. Two such DS-SS systems, with different bandwidths, are studied. We investigate performance statistics for a terrestrial network model in a limited two-dimensional area, in which user (node) locations are random, and statistics are gathered over numerous realizations of these random node locations. For all users in both systems we collect statistics on performance in terms of signal-to-noiseplus-interference ratio (SNIR) and bit error probabilities, to illustrate aggregate behavior attainable in such systems. We first illustrate our technique for a specified reference system with a given set of parameters, then we vary several of these parameters to assess the effects on performance. Parameters we vary include transmit power, data rates,processing gain, path loss exponent and shadowing standard deviation. We demonstrate that overlay of different-bandwidth DS-SS systems in an ad hoc network can be practical by specifying appropriate system design parameters.

A wireless sensor network consists of a large number of low-power nodes equipped with wireless radio. For two nodes not in mutual transmission range, message exchanges need to be relayed through a series of intermediate nodes, which is a process known as multi-hop routing. The design of efficient routing protocols for dynamic network topologies is a crucial for scalable sensor networks. Geographic routing is a recently developed technique that uses locally available position information of nodes to make packet forwarding decisions. This dissertation develops a framework for energy efficient geographic routing. This framework includes a path pruning strategy by exploiting the channel listening capability, an anchor-based routing protocol using anchors to act as relay nodes between source and destination, a geographic multicast algorithm clustering destinations that can share the same next hop, and a lifetime-aware routing algorithm to prolong the lifetime of wireless sensor networks by considering four important factors: PRR (Packet Reception Rate), forwarding history, progress and remaining energy. This dissertation discusses the system design, theoretic analysis, simulation and testbed implementation involved in the aforementioned framework. It is shown that the proposed design significantly improves the routing efficiency in sensor networks over existing geographic routing protocols. The routing methods developed in this dissertation are also applicable to other location-based wireless networks.

Ad-hoc networks are on the forefront of technological advances as more embedded devices allow for wireless communications without necessarily requiring a network infrastructure to connect to. One of the larger problems associated with such ad-hoc networks is the lack of being able to access a PKI to create individual secure sessions for these groups being created. For this project, an implementation generating the public and private keys for an RSA public-key protocol has been created on top of the M2MI middleware developed at RIT. In this implementation, as originally described by Dan Boneh, all parties help contribute to the generation of the RSA public modulus, N, without explicitly knowing the factorization of it. It has been shown that this implementation requires, on average, 32689 rounds of the protocol to create a 1024-bit RSA modulus for the group, and has an approximate growth of log2(N) 25 rounds per bit.

Secure group communication in an ad hoc network is a largely unexplored research area. Currently available key exchange protocols were not designed to be implemented in an ad hoc network where nodes sporadically enter and leave the group. This project explores establishing secure group communication in an ad hoc network through public key infrastructure. Public key infrastructure (PKI) provides a framework for establishing and authenticating secure communication between users. A trusted certificate authority (CA) generates an identifying token, or certificate, for an authorized user. The certificate contains the user's public key and other identifying information and is digitally signed by the CA to prevent forging. This public key may then be used to initiate secure communication with the user. This project uses the tuple space distributed computing paradigm for all ad hoc group communication. A tuple space is a store of tuples, or lists of objects, from which consumers may read tuples matching filter criteria and to which producers may post new tuples. An easily made physical analogy to this concept is that of an announcement board, where people may read flyers and post new ones. Professor Alan Kaminsky's TupleBoard API is an implementation of tuple space designed for developing ad hoc distributed applications in Java. This project extends this library by adding a public key framework enabling dynamic group key exchange, public key encryption and digital signatures. To showcase the newly added security features an ad hoc music distribution application was developed in which all communication is encrypted and authenticated and users may only share or download songs authorized by certificates in their possession. Finally, a performance analysis was done to evaluate the impact of the new security features.

Wireless ad hoc networks are gaining popularity as quick and inexpensive methods of connecting computers. In particular, Wireless Mesh Networks (WMNs) are becoming a viable method of offering Internet access to entire neighborhoods. One reason WMNs are attractive is because of their use of inexpensive 802.11 wireless hardware. However, using 802.11 standard compliant hardware has a major limitation: the 802.11 standard does not support the use of multiple channels in the same network. Because of this limitation, wireless 802.11 networks are not able to achieve the traffic throughput possible when utilizing all the available channels. To increase the throughput in WMNs, this paper proposes a novel protocol allowing the use of multiple channels with a single wireless 802.11 interface. This protocol, Distributed Channel-switching Accessory Protocol, or DCAP, requires no modifications to the 802.11 MAC layer. DCAP defines the methods wireless nodes use to send and receive traffic across multiple channels with a single wireless interface. The key concept of our approach is Home Channels. A node's Home Channel is the only wireless channel on which the node receives data. By requiring the sender to change to the receiver's Home Channel to transmit a packet, all nodes know on which channel to transmit each packet. Once on the receiver's Home Channel, the transmission of the packet follows the 802.11 standard. In this work, DCAP is implemented in the ns-2 event simulator to evaluate its performance. DCAP is implemented as a separate protocol immediately above the 802.11 MAC layer in ns-2. The implementation of DCAP makes no modifications to the 802.11 MAC protocol. A series of performance evaluation tests are performed to compare DCAP's performance against a single channel 802.11 network. These tests compare the throughput of the two networks in a variety of different network traffic conditions and network topologies. The simulation results show the network with the DCAP protocol achieves significantly higher throughputs than the single channel 802.11 network (up to four times in a network with three channels).

Medium-access control (MAC) and multiple-hop routing protocols are presented that exploit the presence of directional antennas at nodes in a wireless ad hoc network. The protocols are designed for heterogeneous networks in which an arbitrary subset use directional antennas. It is shown that the new protocols improvement the network`s performance substantially in a wide range of scenarios. A new MAC protocol is presented that employs the RTS/CTS mechanism. It accounts for the constraints imposed by a directional antenna system, and it is designed to exploit the capabilities of a directional antenna. It is shown that the receiver blocking problem is especially detrimental to the performance if the network includes nodes with directional antennas, and a simple solution is presented. A further improvement to the MAC protocol is presented which results in more efficient spatial reuse of traffic channels in the heterogeneous network. The protocol includes a mechanism by which a negotiating node pair dynamically determines if a traffic channel that is in use in the local area can be used concurrently to support additional traffic. It is shown that the new protocol yields significantly better performance than two existing approaches to the reuse of traffic channels. It is also shown that the improvements are achieved over a wide range of network conditions, including different network densities and different spread-spectrum processing gains. A new distributed routing protocol is also presented for use in heterogeneous wireless ad hoc networks. Two components of the routing protocol are jointly designed: a congestion-based link metric that identifies multiple routes with low levels of congestion, and a forwarding protocol that dynamically splits traffic among the multiple routes based on the relative capabilities of the routes. It is shown that the new routing protocol is able to exploit the decoupling of paths in the network resulting from the presence of nodes with directional antennas. Furthermore, it is shown that the protocol adapts effectively to the presence of advantaged nodes in the network. This approach to joint routing and forwarding is shown to result in a much better and more robust network performance than minimum-hop routing.

The proliferation of multimedia applications requiring strict QoS requirements have tested the performance of the widely used IEEE 802.11 MAC layer protocol for its ability to provide proper service differentiation and QoS. The IEEE 802.11e MAC layer protocol was put forward as an improvement to the IEEE 802.11 MAC layer protocol, focusing on service differentiation and QoS. The nature of IEEE 802.11e is such that in the presence of intensified high priority network traffic, the low priority traffic starves. In this thesis work possible causes for starvation of low priority traffic and the use of dynamic MAC layer parameters in removing starvation of low priority traffic and at the same time providing proper service differentiation and QoS for higher priority traffic in par with IEEE 802.11e EDCF are presented. Two novel schemes are presented which use dynamic MAC parameters. The proposed schemes change the inter frame spacing and contention window parameters based on the calculated collision probability and the fraction of transmission opportunities taken by each traffic class. The proposed schemes are evaluated under static (single hop and multi-hop) and mobile network (multi-hop) conditions. The issues that arise in a multi-hop network and the impact of mobility on the proposed schemes are discussed.

A majority of group communication applications in cellular-based heterogeneous wireless setups entail secure data exchange. The problem can be effectively tackled if the underlying cellular infrastructure is used to provide an authentication backbone to the security associations. We propose a novel distributed ID based key exchange mechanism using shared polynomials in which the shares are generated by the communicating groups. Our idea employs a mechanism where the Base Stations (BSs) carry out an initial key generation by a polynomial in a distributed manner and then pass on the key material to the Mobile Stations (MSs). The multi-interface MSs can now securely communicate over interfaces other than cellular. The scheme incorporates symmetric polynomials, which are chosen by the BS acting as polynomial distributors. Simulations done to measure performance have shown encouraging results.

Video communications play a vital role in present and future wireless ad hoc networks. One of the key requirements for a successful deployment of multimedia applications in multihop wireless networks is the ability to provide an acceptable video quality, even under a highly dynamic and perhaps unfriendly (or hostile) environment (e.g., in the presence of frequent node/link failure, interference, shadowing, fading, and so forth). Existing ad hoc routing protocols work well for data communications, but are not optimized for video, which is sensitive to latency and packet loss. Moreover, traditional end system based error control mechanisms alone cannot guarantee a sustainable video quality. Conventional QoS approaches typically optimize one or more network layer metrics, but they are usually agnostic to any kind of application layer performance. Consequently, new methodologies must be explored to improve the performance of video applications in multihop wireless networks. This dissertation directly addresses this important problem area by leveraging recent advances in video coding techniques along with novel cross-layer formulations and powerful optimization techniques. We follow an application centric cross-layer approach to address multimedia service provisioning over ad hoc networks. Our research efforts show that video communications over multihop wireless networks can substantially benefit from a cross-layer design principle by factoring in application layer video quality into routing algorithmic designs at the network layer. There are three components in this investigation, namely, (1) concurrent routing, (2) path selection and rate allocation, and (3) multipath routing for multiple description video. Each component addresses one or more unique challenges that hinder video communications in multihop wireless networks. Although we expect that a cross-layer approach will be more effective than a network centric (single-layer) approach in addressing application performance, it also brings in complex problems that cannot be effectively solved using traditional methods, and thus, calls for the design of customized algorithms. In concurrent routing, we focus on issues that arise while supporting multiple concurrent video communication sessions in an ad hoc network. These sessions compete for limited network resources (such as bandwidth) while interacting with each other. Such inter-session interactions couple the performance of an individual flow with that of other flows. Applying a video centric cross-layer design principle, we model the end-to-end video distortion as a function of network layer behavior, and formulate a network-wide optimal routing problem that minimizes the total video distortion. Results based on computational experiments performed using randomly generated network topologies establish the relative efficacy and robustness of the proposed genetic algorithm based solution approach. Specifically, we demonstrate that our approach outperforms other trajectory based metaheuristic approaches as well as with conventional network centric routing algorithms such as shortest path and disjoint shortest path routing. The joint path selection and rate allocation problem considers not only selecting the best set of paths for video communication, but also, computing the optimal video encoding rate and partitioning it among the chosen set of paths. The end-to-end video distortion is modeled as a function of network layer resources by capturing the tight coupling that exists between the optimal encoding rate for each video session, the selection of paths for video transmission, and the allocation of traffic among these selected paths. This problem is formulated as a nonlinear nonconvex programming problem, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT). This construct is embedded within a specialized branch-and-bound algorithm to achieve global optimality. Computational experience is reported for various problem instances, and the results validate the robustness of the proposed algorithmic procedure. The results exhibit the advantage of the solution approach over the popularly used max-min rate allocation scheme. The emergence of Multiple Description (MD) coding technique offers great potential for multipath routing of video in multihop wireless networks. In studying multipath routing for MD coding, we show that MD coded video, when used in combination with multipath routing in wireless networks, has tremendous advantages over traditional layered video coding techniques. We discuss how to implement an MD video codec and formulate a cross-layer optimization problem that can find a set of optimal paths, (one for each description) such that the overall video quality at the receiver is maximized. We further devise a specialized RLT-based branch-and-bound solution procedure for the ensuing 0-1 mixed integer nonconvex optimization problem. Convergence behavior of the proposed solution procedure is observed for various network topologies and the results further demonstrate the performance advantage of the proposed cross-layer approach over non-cross-layer approaches. The scope of this research is highly interdisciplinary. It intersects video communication, networking, optimization, and algorithm design. We expect that the theoretical and algorithmic results of this investigation will serve as important building blocks in developing a comprehensive methodology for addressing complex cross-layer problems in the area of wireless ad hoc networks.

Communication in ad hoc networks traditionally relies on network addresses known a priori. This work addresses the need for application-aware adaptive communication that creates network routes based on applications’ dynamic resource requests. We motivate this need by examining the state of the art in mobile ad hoc network communication, the requirements of applications, and the impact of existing protocols on flexibility and efficiency. We introduce an intuitive generalization to source routing which facilitates discovery of a resource in an ad hoc network and the creation and maintenance of a route from the requesting host to the discovered destination. We thus eliminate the requirement that existing routing protocols be coupled with a name or resource resolution protocol, instead favoring an entirely reactive approach to accommodate significant degrees of mobility and uncertainty. We present an initial implementation, a performance evaluation, and a comparison to existing alternatives.

The tuple board is a new distributed computing paradigm based on the tuple space concept invented by Gelernter in 1985. Designed for ad hoc mobile wireless networks, tuple board is a serverless architecture that differs from the original client-server paradigm proposed in tuple space. In this project, Tuple Board, a tuple board implementation has been developed based on the M2MP protocol. Comparing to the previous implementation in Bondada's work, the following improvements have been made: (1) M2MP, instead of M2MI, is used as the underlying network protocol for data communication, (2) notification is available in the tuple board implementation for tuple status changes, (3) a JavaSpaces Entry-like approach is used rather than using Java Class/Object arrays to represent tuple objects. To further study the strength and the limitations of Tuple Board, a collaborative photo sharing application has been developed. The application allows users in ad hoc mobile networks to share selected photos and view photos posted by other users based on dynamically defined rules. Photos available in the application can be shared or withdrawn by the owner.

HF-DSR is an ad hoc routing protocol designed to operate efficiently over high frequency (HF) radio networks. Ad hoc routing protocols allow networks to provide dynamic routing between endpoints. In contrast, static routing schemes require networks to be configured with potential routes in advance. As such, ad hoc routing mechanisms can compensate for unanticipated factors such as radio frequency (RF) interference or node mobility. HF-DSR is largely based on Dynamic Source Routing (DSR), a level 3 ad hoc networking protocol that emits network control information on demand. HF-DSR incorporates portions of DSR which minimize the quantity of control information transmitted. In this manner, as much network bandwidth as possible is conserved for user-initiated data transfers. During this project, an implementation of HF-DSR was developed to operate over the NATO standard STANAG 5066 data transfer protocol. A four node network was assembled using Microsoft Windows PCs, HF modems, HF radios, synchronous RS-232 interfaces, and Harris RF-6750W Wireless Gateways. Two different network topologies were constructed using the four nodes. Finally, HF-DSR route discovery and file transfer were exercised on both network topologies.

In this dissertation, we focus on the issue of power control and spatial reusability in Mobile Ad Hoc Networks (MANETs). We introduce a novel Spatial Reuse MAC (SRM) protocol based on IEEE 802.11 which accomplishes spatial reuse by employing a combination of power control and a distributed transmission sneaking mechanism. Our MAC scheme provides an improved power efficiency and enhanced throughput as compared to existing schemes. We also focus on the spatial reusability by using directional antennas. Existing MAC protocols which have been designed under the omnidirectional antenna assumptions are inadequate to fully exploit the benefits of directional antennas. Hence, the design of an efficient MAC protocol for directional antennas is an important issue and needs further investigation. We introduce a new MAC protocol for Directional Antennas (MDA) which exploits the benefits offered by such an environment. Through simulation work we show that MDA outperforms all exiting directional MAC protocols. We have also addressed directional routing issues in MANETs and propose an on-demand Directional Routing Protocol (DRP) which assumes a cross layer interaction between the routing and the MAC layers. The main features of DRP include an efficient route discovery mechanism, establishment and maintenance of directional routing and directional neighbor tables and a novel directional route recovery mechanism. A detailed study of issues related to routing in directional antenna systems is done and the behavior of different IEEE 802.11 system parameters in a multihop directional environment is also provided undertaken.

This thesis investigates distributed medium access control (MAC) protocols custom tailored to both impulse-based ultra wideband (I-UWB) radios and to large ad hoc and sensor networks. I-UWB is an attractive radio technology for large ad hoc and sensor networks due to its robustness to multipath fading effects, sub-centimeter ranging ability, and low-cost, low-power hardware. Current medium access control (MAC) protocols for I-UWB target small wireless personal area networks (WPANs) and cellular networks, but they are not suitable for large, multihop ad hoc and sensor networks. Therefore, this paper proposes a new type of MAC protocol that enables ad hoc and sensor networks to realize the benefits of I-UWB radios. First, we propose a method to overcome the challenges of quickly, reliably, and efficiently sensing medium activity in an ultra wideband network. This provides a base MAC protocol similar to carrier sense multiple access (CSMA) in narrowband systems. Next, we propose to exploit the unique signaling of I-UWB to improve performance over the base MAC protocol without the associated overhead of similar improvements in narrowband systems. I-UWB enables a distributed multichannel MAC protocol, which improves throughput. I-UWB also facilitates a busy signal MAC protocol, which reduces wasted energy from corrupt packets. Finally, because the I-UWB Physical Layer and MAC Layer affect the network and application layers, we propose a cross-layer adaptive system that optimizes performance. Physical Layer simulations show that both the base protocol and the improvements are practical for an I-UWB radio. Networks level simulations characterize the performance of the proposed MAC protocols and compare them to existing MAC protocols.

Performance of a mobile ad hoc network (MANET) depends directly on the quality of routes selected by the routing protocol at the network layer and the packet transmission efficiency of the MAC layer protocol. The network layer routing protocol used in a MANET does not truly reflect the exact network topology as there is always a delay between topology changes in the network due to user’s mobility and its corresponding routing table changes at the network layer by the routing protocol. Therefore, high user mobility in MANETs causes frequent link breaks when a pair of mobile user nodes, which have moved out of the transmission range of each other but are still shown as neighbors by the routing table, try to communicate with each other. This causes several unnecessary retransmissions between them at the MAC layer before the link is declared dead. Such retransmissions result in inefficient network resource utilization as power and bandwidth are wasted in transmission attempts by the sender node to send packet to the out-of-range receiver node. This research work proposes enhancements for the MAC layer protocol with associated changes at the network layer routing protocol that reduce link break probability, collision probability faced by a transmission, and solve the channel under-utilization problem because of the exposed terminal problem. The proposed schemes, i.e., location prediction check, transmission awareness and service differentiation, use current ongoing transmission information contained in the MAC layer protocol’s handshake packets with piggybacked transmitting node’s mobility-location information. A higher overall performance is achieved with the proposed implementation of the routing protocol over the MAC layer protocol in terms of throughput, power utilization and better quality of service (QoS).

The QoS Multi Meshed Tree Routing is a routing protocol designed to provide Quality of Service (QoS) in Tethered Mobile Ad hoc Networks (tMANET) in terms of bandwidth. This project is a part of the research project titled "Framework for Seamless Roaming, Handoff, and QOS Mapping in Next Generation Networks conducted at the Laboratory for Wireless Networking and Security, headed by faculty member Dr. Nirmala Shenoy. OPNET (Optimum Performance Network), a well-known network simulation tool, is used to implement the design and conduct performance studies of QoS MMT. QoS MANET protocol implements features such as route discovery, link failure identification, bandwidth calculation, resource reservation, and resource release. Various simulations were run to collect statistics of the following performance parameters: Node-Joining Time, End-End delays, Throughput, Route failure notification, and Route availability which were analyzed.

A wireless sensor network is a network of nodes equipped with sensors and capable of relaying their data to the monitoring station using multi-hop communication. Essentially, they operate using the ad hoc paradigm due to the unpredictable and dynamic topology. The lifetime of the nodes is limited to that of its battery. Thus in this work we try to conserve the battery by putting the nodes to sleep when they are not involved in any communication process. Sensor nodes produce readings every fixed time interval and we try to leverage the predictability of the packet inter-arrival time to obtain the sleep periods. We model the inter-arrival times that a node observes in the form of a probability distribution function. A node may be forwarding packets from multiple sources and it associate this knowledge to every stream it is carrying. After a node captures a packet, using its knowledge it can predict the approximate arrival time of the next packet. It can try to sleep during this period. It thus conserves power. In our study we show that simply forwarding the packet when they are received causes the predictability needed for this approach to be lost. We then propose an alternative approach, which is to maintain some local periodicity. This can be accomplished by delaying the packets. The multi-hop nature of the network causes these delays to accumulate and thus we have to consider the tolerances of the data packets to these delays. We then discuss the relation between the sleep durations possible and the delay tolerances of the packets. Finally, we explore the inter-dependence between packet loss, sleep duration, delay and the ultimate effect on the power savings.

Ad hoc networking research has received considerable attention in recent years as it represents the next phase of networking evolution. Efficient and reliable routing of data from the source to destination with minimal power consumption remains the crux of the research problem. Fading mechanisms inherent in wireless communications can impact the packet routing mechanisms in these types of networks. In this thesis, we develop a mathematical framework for evaluating several network diversity schemes that take advantage of the random nature of fading to provide/ enhance the network performance. The efficacy of these different network diversity mechanisms are examined in slow-fading, frequency non-selective Rice and Nakagami-m multipath fading channels. Performance metrics such as the end-to-end outage probability and the end-to-end average symbol error rate are studied in the analysis of these types of networks with the proposed network diversity schemes. Numerical results reveal that the proposed schemes can offer significant power efficiency improvement in a variety of operating scenarios of practical interest.

This thesis studies the idea of adding on-demand service discovery to on-demand routing protocols for mobile ad hoc wireless networks. When on-demand service discovery is used, the service discovery process is initiated only when a node requires access to a service. The address of the service provider is returned to the initiator of the service discovery process. However, the initiator still has to discover a route to the service provider. By integrating service and route discovery, both the identity of the node providing the service and the route to the service are discovered together. This approach differs from related work on service discovery in ad hoc networks which perform service discovery at the application layer and do not discover a route to the service. A combined process for service provider identification and discovery of a route to this provider saves additional message transmissions and reduces the delay incurred if the two processes were done separately at the application and network layers respectively. The idea of adding on-demand service discovery to on-demand routing protocols for mobile ad hoc networks was earlier proposed in an Internet-Draft and simulated using Ad Hoc On-Demand Distance Vector Protocol (AODV) as the routing protocol. In this thesis, we propose modifications and extensions to the Internet-Draft. We discuss solutions to the problem of notifying the nodes in the network when a service provider terminates its service. We also present a modified simulation of the integration of service discovery with AODV (we discovered a number of bugs in the original simulation). We then present a simulation of the integration of service discovery with the Dynamic Source Routing Protocol (DSR). Lastly, we compare the performance of service discovery with AODV and DSR. We find that integrating service discovery with AODV gives better results in terms of service route acquisition latency. In terms of path length and the ratio of the path length to the shortest path, DSR gives better results for a smaller network size, while AODV gives better results for a larger network size. Further, the number of service discovery failures is higher when DSR is used, especially in larger networks. However, due to the aggressive caching in DSR, a node which requires a service is more likely to have a route to the service provider and hence may not need to initiate a service discovery. Since the DSR implementation in ns-2 that we consider does not actively purge stale routes from its cache, such a cached route is likely to be valid only in conditions of low mobility. Overall, we conclude that integration of service discovery with AODV gives better results than integration with DSR.

Routing protocols in wireless ad hoc network are highly insecure and prone to various attacks owing to its inherent characteristics of open medium, dynamically changing topologies and distributed cooperation between the member nodes. Having a secure routing protocol in wireless ad hoc networks appears to be a problem that is not trivial to solve. We propose a scheme to enhance the fault-tolerance of cluster head’s functionality in CBRP. CBRP with a single cluster head is single point of failure and unsuitable especially for functionalities like key distribution. By distributing the cluster head service to a group of cluster heads called Council nodes and utilizing the (k, n) secret sharing scheme, we can increase the fault tolerance of network manifolds against security attacks. Simulation results obtained demonstrates that our proposed algorithm enables simultaneous formation the Council based clusters, thereby making the scheme time efficient and comparable to CBRP. Results also show that since large size clusters are formed in Council based clusters, it is feasible to apply (k, n) secret sharing concepts. The scheme is more suitable for low mobility networks due to the less signaling overhead involved in during cluster reformations.

Group communication is the most important mode of communication in ad hoc networks, because of the collaborative nature of mobile ad hoc applications. In this light, an efficient and light weight multicast routing protocol is necessary. Presently the multicast routing is either done entirely at the network layer, or at the application layer as stateless overlay mulitcasting. Owing to the dynamic nature of ad hoc networks, the first method incurs a large signaling overhead due to frequent modification of routing tables and exchanging of session state information. The latter approach uses the underlying unicast routing to build multicast data distribution trees without maintaining session state information thereby trading efficiency for minimal messaging overhead. For small groups with constant bound on the number of multicast group members, the overlay schemes, apart from having a trivial signaling overhead, are also known to be far more efficient than the network layer schemes. But the existing overlay schemes do not completely exploit the 'knowledge' possessed by the network layer; they just use the unicast routing at the network layer. We believe that, even for larger groups, the overlay schemes can function with reasonable efficiency along with trivial signaling overhead if they intelligently use the network layer information. In this thesis, we propose a network assisted multicast routing scheme, NAMO NAMAHA, which primarily operates as an overlay while getting assistance from the network layer unicast routing protocol, CEDAR. The overlay algorithms dynamically build an approximate Steiner data distribution tree, adopting the (CHINS)_T (Cheapest Insertion Heuristic with Table) algorithm for the distributed implementation of the well known Takahashi-Matsuyama heuristic. The Steiner trees are incrementally built over a subgraph of core nodes, which form the approximate Minimum Dominating Set (MDS) over the network nodes. The core nodes get computed by a network layer heuristic using local data at that layer, and they provide useful information for the NAMO NAMAHA tree computation algorithms at the overlay layer. The main idea in this thesis is that if the construction of overlays is aided by some minimal but useful information from the network layer that is almost invariant, local and that which would incur constant memory overhead, efficient overlays can be constructed. This thesis presents the algorithms for the protocol NAMO NAMAHA, offers proof of correctness for the protocol and shows that the time and memory complexity of the algorithms in the protocol are either constant, or linear with the number of graph edges or nodes. We compare our work with the MCEDAR protocol in terms of the cost of the multicast data distribution trees, the number of messages exchanged in building them and the time and memory complexity of the algorithms involved. We choose MCEDAR since other multicast protocols for ad hoc networks are either network based which does not scale for large nubmer of nodes, or function as overlays designed only for small groups. When compared to MCEDAR, NAMO NAMAHA has a simpler join protocol implemented by our unique Unicast Trap algorithm that does not make use of acknowledgements. Unlike MCEDAR, the sender discovery messages are not propagated all over the network; they are restricted to regions where it is absolutely necessary. In NAMO NAMAHA, at any given time, a path exists between any multicast subscriber and the sender (which is approximately the best path possible) with very high probability. Such a guarantee cannot be given in MCEDAR. Furthermore because of the incremental Steiner tree construction, the resulting multicast data distribution tree has nearly the least total cost. Cost is not minimized in MCEDAR. These advantages are obtained in NAMO NAMAHA just by using extra messages during tree construction, whose number is well below the actual number of nodes in the multicast group. The time and memory complexity of the NAMO NAMAHA algorithms are in the same order as that in MCEDAR.

The goal of this research is to estimate the capacity of wireless mesh networks (WMNs). WMNs have unique topology and traffic patterns when compared to conventional wireless Internet access networks. In WMNs, user nodes act as a host and a router simultaneously and form a meshed topology. Traffic is forwarded towards a gateway connected to the Internet by cooperating user nodes in a multihop fashion. Since the considered WMNs use IEEE 802.11 for medium access control and physical layer implementation, theoretical maximum throughput and fairness issues in IEEE 802.11 networks are investigated as a preliminary framework for the capacity estimation of WMN. Due to a centralized traffic pattern and meshed topology, forwarded traffic becomes heavier as it gets closer to the gateway. The characteristics of the traffic behavior in WMNs are thoroughly examined and an analytical solution for capacity estimation is presented. The analytical solution is derived for various topologies and validated using simulations.

Ad hoc networks provide a new approach for wireless communication. These networks have no pre-deployed infrastructure available for achieving end-to-end routing of packets in the network. Nodes communicate with each other without the intervention of centralized access points or base stations, so each node acts both as a router and as a host. Securing routing in ad hoc networks creates difficulties not present in traditional network: neither centrally administrated secure routers nor strict policy exists in an ad hoc network; the nodes in the networks can be highly mobile, thus rapidly changing the network topology and the presence or absence of links. So the routing in ad hoc networks is especially hard to accomplish securely, robustly and efficiently. Security primitives such as authentication, non-repudiation, data integrity and confidentiality, which would otherwise be provided by a central server, must be enabled by one or more network nodes. In this thesis, we focus on two issues of security, routing security and key management. We have discussed various threats to routing protocols in ad hoc networks and proposed methods to enhance the security of these protocols. We have put forth a new authentication scheme for on-demand routing protocols, specifically Dynamic Source Routing (DSR), by using public key cryptography in order to prevent the attacks against routing. The use of public key infrastructure in ad hoc networks raises the issue of key management. Certification of public keys of the nodes belonging to an ad hoc network is a non-trivial problem. Existing techniques for certifying keys are not well suited for ad hoc networks due to their sensitivity to single point of failure. We have defined a new key management paradigm, which can effectively deal with the challenges inherent in ad hoc networks and combat the attacks on the key management system itself. The proposed solution is then integrated into an existing hierarchical routing protocol.

An ad hoc network is a collection of wireless mobile hosts dynamically forming a network without the use of any existing stationary network infrastructure. If two nodes in an ad hoc network are not in each other's communication range, data packets must be routed by intermediate nodes. Routing in an ad hoc networks is a significant challenge because of the difficulty in maintaining a successful communication path between a source-destination pair in spite of changing topology. This is complicated by the fact that most wireless networks have low bandwidth, thus routing and data forwarding must be done prudently so as not to overwhelm a low capacity network. A significant amount of work has been done in designing efficient routing protocols for mobile ad hoc networks and many routing protocols have been developed. The focus of the community, however, has been on best effort traffic where packets must be routed as quickly as possible with minimum possible delay. However, it turns out that routing performance in terms of bandwidth usage and throughput may improve if packets are allowed to wait in buffers at the source or at intermediate nodes and are delivered to destinations with a minimum number of hop-wise transmissions at opportune moments. This obviously reduces bandwidth usage as a small number of transmissions are needed to deliver a packet. It also indirectly improves throughput as packet losses become less likely as packets are buffered when routes are unavailable and also packets are exposed less to wireless channel errors. However, the buffering increases end-to-end packet delay; so such an approach is applicable only to delay-tolerant applications. Also, care must be taken to prevent starvation where packets wait indefinitely in the buffers. In this thesis, we design and develop two location-based routing protocols "Geographic Forwarding with Buffering" and "Topology Based Forwarding with Buffering" based on the above idea that encourages buffering to gain better bandwidth usage and lower packet loss. The protocols use intelligent location tracking. Tracking is provided by a dead reckoning-based location service developed earlier. Packets are buffered when the destination is far and forwarded when it comes near. Packets are also buffered when congestion develops or when no route is available. The protocols are implemented in the network simulator Glomosim and their performance is evaluated against two standard routing protocols: one location based - GPSR and the other non-location based - AODV. The evaluations show that our protocols offer much better packet delivery ratios, often close to 100 % as well as a significant reduction in average hop-wise transmissions per packet, while the end-to-end delay degrades only slightly.

A mobile ad hoc network (MANET) is a collection of mobile platforms or nodes that come together to form a network capable of communicating with each other, without the help of a central controller. To avail the maximum potential of a MANET, it is of great importance to devise a routing scheme, which will optimize upon the performance of a MANET, given the high rate of random mobility of the nodes. In a MANET individual nodes perform the routing functions like route discovery, route maintenance and delivery of packets from one node to the other. Existing routing protocols flood the network with broadcasts of route discovery messages, while attempting to establish a route. This characteristic is instrumental in deteriorating the performance of a MANET, as resource overhead triggered by broadcasts is directly proportional to the size of the network. Bounded-dynamic source routing (B-DSR), is proposed to curb this multitude of superfluous broadcasts, thus enabling to reserve valuable resources like bandwidth and battery power. B-DSR establishes a bounded region in the network, only within which, transmissions of route discovery messages are processed and validated for establishing a route. All route discovery messages reaching outside of this bounded region are dropped, thus preventing the network from being flooded. In addition B-DSR also guarantees loop-free routing and is robust for a rapid recovery when routes in the network change.

A mobile ad hoc network is a collection of autonomous nodes connected to each other in a peer-to-peer fashion on a wireless medium. Such networks are used in emerging applications which require co-operative mobile data exchange in areas where there is little or no infrastructure available or where providing such infrastructure is not cost effective. Efficient dynamic routing is a major research challenge in such a network. Multipath routing provides a strong potential for efficient routing by maintaining multiple routes. This provides some form of fault-tolerance, as alternate paths can be used when one breaks. Also, data packets can be forwarded via multiple paths concurrently thus exploiting a larger network capacity. However, CSMA (carrier-sense multiple access) being a dominant form of channel access protocol in mobile ad hoc network, multipath forwarding is often unable to exploit its full potential. This is because multiple paths may form in each others’ radio neighborhood limiting spatial diversity. Data transmission in one path causes sufficient interference in another such that only one path can be used at a time. This phenomenon has been known as “route coupling.” We investigate the use of multichannel CSMA-based medium access protocols to reduce the impact of such route coupling. We use two such multichannel protocols to demonstrate that a significant throughput improvement is possible at high offered loads relative to the single channel CSMA for multipath data forwarding scenarios. One of the protocols chooses the channel based on interference power measurement at the sender. The other chooses a unique channel for each path. Our study shows that the multichannel protocols are able to limit the impact of interference between neighboring transmissions effectively.

A mobile ad hoc network is a collection of wireless nodes, all of which may be mobile, that dynamically create a wireless network amongst them without using any infrastructure. Ad hoc wireless networks come into being solely by peer-to-peer interactions among their constituent mobile nodes, and it is only such interactions that are used to provide the necessary control and administrative functions supporting such networks. Mobile hosts are no longer just end systems; each node must be able to function as a router as well to relay packets generated by other nodes. As the nodes move in and out of range with respect to other nodes, including those that are operating as routers, the resulting topology changes must somehow be communicated to all other nodes as appropriate. In accommodating the communication needs of the user applications, the limited bandwidth of wireless channels and their generally hostile transmission characteristics impose additional constraints on how much administrative and control information may be exchanged, and how often. Ensuring effective routing is one of the greatest challenges for ad hoc networking. As a practice, ad hoc routing protocols make routing decisions based on individual node mobility even for applications such as disaster recovery, battlefield combat, conference room interactions, and collaborative computing etc. that are shown to follow a pattern. In this thesis we propose an algorithm that performs routing based on underlying mobility patterns. A mobility pattern aware routing algorithm is shown to have several distinct advantages such as: a more precise view of the entire network topology as the nodes move; a more precise view of the location of the individual nodes; ability to predict with reasonably accuracy the future locations of nodes; ability to switch over to an alternate route before a link is disrupted due to node movements.

An ad hoc network is a collection of wireless hosts that spontaneously forms a network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network "hops" may be needed for one node to exchange data with another node across the network. Thus, individual nodes must also act as routers. The routing problem gets complex if the nodes are mobile. Dynamic routing in the face of topological changes is an important problem in such mobile ad hoc networks. Such networks find tremendous applications in any type of mobile collaborative applications, where the network must be set up on the fly. Examples include emergency response, law enforcement,explorations, conferencing and military. Not all ad hoc networks are mobile. A network of embedded sensors collaborating to perform a high level sensing task is one such example. Since sensor nodes are powered by battery and sensor networks must be operational in an unattended fashion for a long time,solving problems with low communication overhead is critical. This means communication must be primarily local. The overall goal of this thesis is to perform experimental study on real ad hoc network testbeds. Two types of network testbeds have been used – (i) a mobile ad hoc network using NovaRoam wireless IP routers,and (ii) a sensor network using the Berkeley MICA mote platform. Our focus is experimental protocol design and evaluation on these testbeds. In the NovaRoam-based mobile ad hoc network testbed, we have implemented a version of the well-known AODV (Ad hoc On Demand Distance Vector) routing protocol. It has been implemented as a part of the usual TCP/IP protocol stack. This thesis presents the design decisions for this implementation, as well as performance evaluation of dynamic multihop routing using UDP and TCP on this testbed. As demonstrated in current literature, the performance degrades with larger number of hops in the network and with high offered load. To exercise the sensor network testbed, we have focused on a collaborative monitoring problem. We have developed a simple algorithm that detects and tracks a moving target, and alerts sensor nodes along the projected path of the target. The algorithm involves only simple computation and localizes communication only to the nodes in the vicinity of the target and its projected course. The algorithm has been evaluated on the Berkeley MICA mote testbed using a light source as the moving target. The performance results are presented emphasizing the accuracy of the technique, along with a discussion about our experience in using such a platform for target tracking experiments.

Mobile ad hoc networks (MANET) consist of a collection of wireless mobile nodes, often with unpredictable mobility patterns, dynamically forming a network without using any existing network infrastructure or central control. Due to these mobility patterns, nodes in the network can be separated into partitions and reconnected a number of times. Whenever a larger partition divides into two smaller ones, there is a critical link that fails and thus divides the partition into two separate partitions. In graph theory, the two nodes forming this critical link are referred to as separation nodes while the graphs are referred to as mono-connected graphs and have been thoroughly studied in literature under network survivability concepts. In this work, we propose an approach that utilizes these concepts to detect the critical links whose failure will give rise to partitions in the network. Once the critical link has been detected, we propose three ways to delay or avoid its failure: change the trajectory of one or both nodes forming the link to reinforce it; bring in another node to reinforce the link; and the combination (hybrid) of these two. It is assumed that the nodes know their locations and periodically update their neighbors with their current location. We implement these techniques in the network simulator ns-2 and show that the approach can signicantly improve the network performance and reduce the degree of partitioning.

A mobile ad hoc network is a collection of wireless mobile nodes dynamically forming a network without the use of any existing network infrastructure or centralized administration. As the nodes are mobile, the network topology is dynamic leading to frequent unpredictable connectivity changes. It is critical to route packets to destinations effectively without generating excessive overhead. This presents a challenging issue for protocol design since the protocol must adapt to frequently changing network topologies in a way that is transparent to the end user. A class of routing protocols called on-demand protocols has received a lot of interest because of their low routing overhead. In this thesis, we study techniques that can reduce this routing overhead even further. The on-demand protocols depend on query floods to discover routes whenever a new route is needed. Network-wide floods incur substantial overhead. Techniques have been proposed to contain the flood in a limited region where a route to the destination is highly likely to be found. Techniques have also been proposed to reduce redundant broadcasts. We propose various mechanisms to improve on these existing techniques. We propose adaptive mechanisms that utilize prior routing histories, mobility pattern and network load to choose the area in which the query flood should be contained. In addition, we propose a technique that utilizes the neighborhood information to reduce or eliminate redundant broadcasts. We evaluate their performances in isolation and in tandem. In the next part of the thesis, we turn our attention to use of location information for routing. In has been shown in prior work that availability of location information can substantially reduce routing overheads. However, equipping all mobile nodes with GPS or other positioning system is not a cost effective proposition. We develop and evaluate a localization technique that can localize mobile nodes even when only a fraction of nodes in the network has direct access to location information. The rest of the nodes localize themselves by hearing radio beacons emitted from the nodes that have access to direct location information. We evaluate the localization accuracy using our technique via simulations. We show that the accuracy is better than the radio range even when only about 10% of the network nodes have direct access to location information. To be useful for routing, each node in the network must learn the location of every other node. However, disseminating this information sufficiently frequently can incur large overhead. To counter this, we develop a mobility prediction and location tracking model based on the dead-reckoning navigation technique. Here, both current location and movement model of mobile nodes are disseminated via flooding. Every other node is now able to track the movement with some accuracy until the movement model changes bstantially. We use this technique along with a geographic routing protocol to solve the unicast routing problem in ad hoc networks. Simulation studies show that it performs better than well-known on-demand routing protocols.

An Ad Hoc network is a collection of wireless, mobile nodes that dynamically form a network without the use of centralized, fixed network infrastructure. Inherent characteristics of an Ad Hoc network such as dynamic topology and limited physical security poses severe security challenges to the network. Hence, these networks demand much stronger security mechanisms than the traditional, wired and static networks. Well established contemporary routing protocols seem to adapt to the dynamic conditions as well. However, they provide either no security mechanisms at all, or have only partial solutions for protecting the dynamic routing framework.It is hard to achieve security and robustness in the routing protocols at the same time in such networks. Several issues have to be understood and addressed before devising a security mechanism. Moreover, challenges involved in addressing attacks differ from one protocol to the other. This thesis targets at securing reactive routing protocol AODV. The routing protocol is vulnerable to two kinds of attack: External and Internal attack. We have discussed some existing external attacks and possible malicious behavior from compromised nodes. To mitigate the attacks, we propose a dual level security model. On the first level, we have External Attack Detection Model(EADM), that secures the network with authentication and confidentiality that rely on mutual trust between nodes. And on the second level, Intrusion Detection Model (IDM) identifies the misbehaving nodes using the knowledge base and Response Model (RM) isolates these nodes from the network.

An Ad hoc network is a completely wireless network with a dynamic nature of topology, which rapidly changes with time. Due to the node movement there are sudden losses of packets and delays. Transport protocols like TCP have been designed for reliable fixed networks. TCP misapprehend these packet losses as congestion in the network and call upon congestion control, which leads to avoidable retransmissions and loss in overall performance. In this work we propose a receiver information based approach, so that source can distinguish between route failure and network congestion. Simulation results show that the use of this feedback approach provides a significant improvement in performance. TCP does not differentiate between congestion and packet loss due to transmission errors or route failures, because it is designed for use over fixed low-error networks like the internet. In internet route failures and disruptions are very sporadic since network is fixed, therefore, packet losses, which is detected by TCP as a timeout, can be interpreted as a symptom of congestion in the network. A lot of research has been done on reliable transport protocols for cellular wireless networks. All the mechanisms proposed heavily depend on the presence of wired base station network, and hence cannot be directly applied to ad-hoc networks. In this work we study TCP performance over ad hoc networks and propose receiver information based feed back scheme, to control the TCP window at the sender side. TCP performance is tested in ad hoc network routed with DSR routing protocol, with two versions of TCP, TCP-new Reno, and TCP-feecon (proposed). With this study, we see number of unique characteristic of ad hoc networks for TCP, such as increasing ratio of out-of-order packet delivery, multiple competing connections contending for the bandwidth-constrained wireless channel and induce network congestion, mobility-induced disconnection, and reconnection. We propose an adaptive feed back technique which uses receiver information to command and control the sender side TCP window. Our implementation complexity is on the receiver side and is stable.

An ad hoc network is a collection of wireless mobile nodes dynamically forming a network without the use of any existing stationary network infrastructure. The network can be multi-hop and mobile; there is no central controller and packet transmissions are typically unsynchronized. The efficiency of the medium access control (MAC) protocol to coordinate the access to the shared radio medium is critical. Carrier sense multiple access (CSMA) protocols are typically used. However, their efficiency is limited when the load and the level of contention is high. This thesis proposes use of multichannel CSMA protocols to reduce contention on the wireless medium. Though the aggregate capacity with a multichannel scheme is the same as a single channel, contention per channel is now lower and thus channel access is more efficient. We show that only a handful of channels provide optimum performance as with too many channels per-channel bandwidth is too low that affects performance adversely. Since the number of channels are much lower than the number of nodes, effective channel selection schemes are needed. We propose a receiver-based channel selection (RBCS) scheme that selects channel based on interference levels on different channels at the receiver. We implement this technique as an extension of IEEE standard 802.11 MAC protocol (which is a single channel protocol) on a network simulator. We show that it provides superior delay performance at high loads compared to single channel, as well as other, previously studied, channel selection schemes, such as selcting a random free channel or selecting channel based on sender-side signal power. As a final contribution, we study the effect of multichannel CSMA protocols for multipath routing on ad hoc networks. With use of single channel CSMA, ''route coupling'' can exist for multipath routes. This means that routes can form in radio neighborhood, and their transmissions can interfere with each other, preventing multiple routes to be used concurrently. Thus, the load balancing advantages of multiple paths are lost. We show that the use of multichannel CSMA protocols as above can remarkably improve the effectiveness of the multipath routing by providing more diversity.

An ad hoc network is a collection of wireless mobile nodes dynamically forming a network without the use of any existing network infrastructure orcentralized administration. Dynamic routing protocols have been developed that allow such nodes to communicate using multi-hop routes, but existing protocols typically provide only best-effort service. In particular, they do not directly provide any way to control the resource usage in the network. This thesis focuses on the management of two such resources, viz., battery power and the bandwidth available to the nodes. Both are premium resources in a wireless network with mobile nodes. We develop our techniques as extensions of “on-demand” routing protocols because of their superior performance as reported in current literature. These are routing protocols that compute routes on an “as needed” basis. All protocols and techniques developed in this thesis are evaluated using extensive simulations using a multi-layer network simulator. To manage battery power, we develop a technique to make on-demand routing protocols energy-aware. The goal is to increase the operational lifetime of the network where mobile nodes are operating on battery power alone, and batteries cannot be recharged or replaced. The idea here is to balance the residual energy levels of the batteries in the mobile nodes by dynamically shifting routing loads from nodes with low battery levels to those with higher battery levels. The technique also switches off network interfaces strategically to conserve energy. Simulations show significant improvement of the energy budget of the network as a whole resulting in increased operational lifetime. The most improvement is noticed for high loads and modest mobilities. To understand the question of bandwidth usage better, we develop empirical techniques to determine network capacity and utilization when the network is running commonly used routing and medium access protocols. While the technique is general, we specifically apply it to determine the network capacity and utilization for on-demand routing protocols and “virtual carrier sensing”- based medium access protocols. Simulation analysis with this technique reveals several interesting results. Specifically, it shows that a significant portion of the network capacity remain unutilized regardless of traffic and mobility conditions. Also, the network capacity increases with mobility, but the routing protocol is unable to take any advantage of this additional capacity. While these results have an important bearing on their own, they also help us forming realistic expectations from any bandwidth management techniques that could be developed for ad hoc networks. As a final contribution, we develop a quality-of-service (QoS) extension of on-demand routing protocols that attempts to provide bandwidth guarantees to sessions that request it. The guarantee is achieved via bandwidth reservation along the route of the session and taking admission control decisions at the source. Sessions are not admitted if the requested bandwidth guarantees cannot be provided. Simulation results demonstrate that QoS guarantees are indeed provided for most sessions that are admitted; while without this QoS extension the routing protocol admits all sessions, but fails to provide QoS guarantees to most of them. A set of validation experiments provide a background sanity check; that the QoS extension protocol actually admits sessions that could be admitted.

We are in a time of fundamental change in the world's telecommunications infrastructure, with the nature and quantity of information transmission undergoing major transformation. With expanding interest in mobile access to this communications infrastructure has come rapid growth in the number of users of wireless communication networks. The backbone of this growth has been single-hop networks, such as cellular systems, in which service areas are under the central control of a base station. More recently, researchers began investigating ad hoc wireless networks, which operate without a central controller, with each node acting as a network router. In this dissertation, we formulate models for both kinds of wireless networks, and develop optimal policies (protocols) under a variety of system assumptions. First, we formulate a problem in single-hop resource (multi-channel) allocation for wireless networks, under general arrival and connectivity processes at each mobile node. We provide conditions sufficient to guarantee the optimality of an index policy for this problem. We then refine the aforementioned sufficient conditions under additional assumptions on the arrival and connectivity processes. Next, we define a problem which both extends and restricts the previous model. The extension is to include a switching cost when server (channel) allocation changes; this cost models the penalty paid when a communications resource is moved between customers. The restriction is to include only one server in the model. We provide conditions sufficient to guarantee the optimality of an index policy for this problem. Finally, we present a time-invariant stochastic model for routing in ad hoc wireless networks, and we discuss the design decisions leading to this model. We first view the routing problem as a problem of centralized control, and prove optimality of an index policy. Then, we demonstrate that this index policy can be implemented in a distributed manner. We add quality of service considerations by allowing time-varying system parameters, and provide conditions under which we can specify an optimal policy for the time-varying system. We define three distributed algorithms, and prove each computes an optimal routing policy for the time-invariant problem. With these distributed algorithms, the original goal of finding an optimal decentralized protocol is attained.