Prior research in routing for wireless ad hoc networks has shown that multipath routing can enhance data delivery reliability and provide load balancing. Nevertheless, only a few multipath routing algorithms have been proposed and their interaction with transport layer protocols has not been thoroughly addressed in the literature. In this work, we propose the multipath “Fresnel zone” routing (FZR) algorithm for wireless ad hoc networks. FZR constructs multiple parallel paths from source to destination based on the concept of “Fresnel zones” in a wireless network. The zone construction method assigns intermediate routers into different “Fresnel zones” according to their capacity and efficiency in forwarding traffic. The central idea in FZR is to disperse traffic to different zones according to network load and congestion conditions, thus achieving better throughput and avoiding congestion at intermediate routers. FZR differs from most existing multipath routing approaches in that both source and intermediate nodes use multiple forwarding paths. FZR also adopts a combination of proactive and on-demand (reactive) approaches to reduce control overhead and latency for packet delivery. Simulation experiments have shown that FZR outperforms unipath distance vector routing, multipath distance vector (MDV) routing, and split multipath routing (SMR) algorithms in quasistatic wireless ad hoc networks. In our simulations, FZR achieves up to 100 percent higher average throughput using the User Datagram Protocol (UDP) and 50 percent higher average throughput using the Transmission Control Protocol (TCP). FZR can also provide better load balancing among different paths, improve network resource utilization, and enable fairer resource allocation among different data transmission sessions. Future work is needed to evaluate FZR in mobile scenarios. / Master of Science

ITC/USA 2005 Conference Proceedings / The Forty-First Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2005 / Riviera Hotel & Convention Center, Las Vegas, Nevada / An ad hoc network is a group of wireless nodes which do not rely on any fixed infrastructure. Hosts cooperate by forwarding packets for each other to communicate with nodes that are out of the radio transmission range. We propose a new routing algorithm that is based on the concept of multipoint relay nodes (MPR). The main focus of the Trust Level Routing protocol is the reliability and survivability of the network by applying costs to each MPR candidate. The cost calculation is based on the delay incurred, energy available at the MPR node, energy spent during transmission and number of packets sent on each link. We highlight the vulnerabilities in current link state routing algorithms and propose the use of light weight encryption algorithms to achieve a dependable routing algorithm. Network simulator (ns-2) is used to compare the protocol performance to other existing link state routing protocols.

The growing number of wireless devices and wireless systems present many challenges on the design and operation of these networks. We focus on massively dense ad hoc networks and cellular systems. We use the continuum modeling approach, useful for the initial phase of deployment and to analyze broad-scale regional studies of the network. We study the routing problem in massively dense ad hoc networks, and similar to the work of Nash, and Wardrop, we define two principles of network optimization: user- and system-optimization. We show that the optimality conditions of an appropriately constructed optimization problem coincides with the user-optimization principle. For different cost functions, we solve the routing problem for directional and omnidirectional antennas. We also find a characterization of the minimum cost paths by extensive use of Green's theorem in directional antennas. In many cases, the solution is characterized by a partial differential equation. We propose its numerical analysis by finite elements method which gives bounds in the variation of the solution with respect to the data. When we allow mobility of the origin and destination nodes, we find the optimal quantity of active relay nodes. In Network MIMO systems and MIMO broadcast channels, we show that, even when the channel offers an infinite number of degrees of freedom, the capacity is limited by the ratio between the size of the antenna array at the base station and the mobile terminals position and the wavelength of the signal. We also find the optimal mobile association for the user- and system-optimization problem under different policies and distributions of the users.

Broadcast communications is critically important in vehicular networks. Many safety applications need safety warning messages to be broadcast to all vehicles present in an area. In this thesis, we propose a novel repetition-based broadcast protocol based on ``optical orthogonal codes.'' Optical orthogonal codes are used because of their ability to reduce the possibility of collision. We present a detailed mathematical analysis for obtaining the probability of success and the average delay. Furthermore, we propose to use coding to increase network throughput, and ``adaptive elimination'' of potentially colliding transmissions to further increase reliability. We show, by analysis and simulations, that the proposed protocol outperforms existing repetition-based ones and provides reliable broadcast communications and can reliably deliver safety messages under load conditions deemed to be common in vehicular environments. We also show that the proposed protocol is able to provide different levels of quality of service.

Broadcast communications is critically important in vehicular networks. Many safety applications need safety warning messages to be broadcast to all vehicles present in an area. In this thesis, we propose a novel repetition-based broadcast protocol based on ``optical orthogonal codes.'' Optical orthogonal codes are used because of their ability to reduce the possibility of collision. We present a detailed mathematical analysis for obtaining the probability of success and the average delay. Furthermore, we propose to use coding to increase network throughput, and ``adaptive elimination'' of potentially colliding transmissions to further increase reliability. We show, by analysis and simulations, that the proposed protocol outperforms existing repetition-based ones and provides reliable broadcast communications and can reliably deliver safety messages under load conditions deemed to be common in vehicular environments. We also show that the proposed protocol is able to provide different levels of quality of service.

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

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

Broadcasting is a fundamental primitive in local area networks (LANs).Operations of many data link protocols, for example, ARP (Address Resolution Protocol) and IGMP (Internet Group Management Protocol), must rely on this LAN primitive. To develop the broadcasting service in mobile ad hoc wireless LANs (WLANs) is a challenge. This is because a mobile ad hoc WLAN is a multi-hop wireless network in which messages may travel along several links from the source to the destination via a certain path. Additionally, there is no fixed network topology because of host moving. Furthermore, the broadcast nature of a radio channel makes a packet be transmitted by a node to be able to reach all neighbors. Therefore, the total number of transmissions (forward nodes) is generally used as the cost criterion for broadcasting. The problem of finding the minimum number of forward nodes in a static radio network is NP-complete. Almost all previous works, therefore, for broadcasting in the WLAN are focusing on finding approximation approaches in a, rather than, environment. In this paper, we propose a novel distributed protocol in WLANs to significantly reduce or eliminate the communication overhead in addition to maintaining positions of neighboring nodes. The important features of our proposed protocol are the adaptability to dynamic network topology change and the utilization of the existing routing protocol. The reduction in communication overhead for broadcasting operation is measured experimentally. From the simulation results, our protocol not only has the similar performance as the approximation approaches in the static network, but also outperforms existing ones in the adaptability to host moving.

With the growth of Internet, the underlying protocols are increasingly challenged by new technologies and applications. The original Internet protocols were, however, not designed for wireless communication, mobility, long disconnection times, and varying bandwidths. In this thesis, we study challenged networking, and how well old and new protocols operate under such constraints. Our study is experimental. We build network testbeds and measure the performance of alternative protocols and architectures. We develop novel methodologies for repeatable experiments that combine emulations, simulations and real world experiments. Based on our results we suggest modifications to existing protocols, and we also develop a new network architecture that matches the constraints of a challenged network, in our case, an opportunistic network. One of our most important contributions is an Ad hoc Protocol Evaluation (APE) testbed. It has been successfully used worldwide. The key to its success is that it significantly lowers the barrier to repeatable experiments involving wireless and mobile computing devices. Using APE, we present side-by-side performance comparisons of IETF MANET routing protocols. A somewhat surprising result is that some ad hoc routing protocols perform a factor 10 worse in the testbed than predicted by a common simulation tool (ns-2). We find that this discrepancy is mainly related to the protocols’ sensing abilities, e.g., how accurately they can infer their neighborhood in a real radio environment. We propose and implement improvements to these protocols based on the results. Our novel network architecture Haggle is another important contribution. It is based on content addressing and searching. Mobile devices in opportunistic networks exchange content whenever they detect each other. We suggest that the exchange should be based on interests and searches, rather than on destination names and addresses. We argue that content binding should be done late in challenged networks, something which our search approach supports well.

How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their messages or overwhelm them with his ownmalicious data. Being a tiny device, however, Collin can onlybroadcast up to B times. Given that Alice and Bob do not knowB, and cannot distinguish honest from malicious messages, howlong can Collin prevent them from communicating? We show the answerto be 2B + Theta(lg|V|) communication rounds, where V is theset of values that Alice and Bob may transmit. We prove this resultto be optimal by deriving an algorithm that matches our lowerbound---even in the stronger case where Alice and Bob do not start thegame at the same time.We then argue that this specific 3-player game captures the generalextent to which a malicious adversary can disrupt coordination in asingle-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower boundsfor several classical n-player problems: 2B + Theta(lg|V|) for reliable broadcast,2B + Omega(lg(n/k)) for leader election among k contenders,and 2B + Omega(k*lg(|V|/k)) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2B + Theta(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds in this paper represent the first such results for a wireless network in which the adversary has the ability to disrupt communication.