Ad hoc networks

Recent advances in portable computing and wireless technologies are opening up exciting possibilities for the future of wireless mobile networking. A mobile ad hoc network (MANET) is an autonomous system of mobile hosts connected by wireless links. Mobile networks can be classified into infrastructure networks and mobile ad hoc networks according to their dependence on fixed infrastructures. In an infrastructure mobile network, mobile nodes have wired access points (or base stations) within their transmission range.
The access points compose the backbone for an infrastructure network. In contrast, mobile ad hoc networks are autonomously self-organized networks without infrastructure support. In a mobile ad hoc network, nodes move arbitrarily, therefore the network may experiences rapid and unpredictable topology changes. Additionally, because nodes in a mobile ad hoc network normally have limited transmission ranges, some nodes cannot communicate directly with each other. Hence, routing paths in mobile ad hoc networks potentially contain multiple hops, and every node in mobile ad hoc networks has the responsibility to act as a router.

Mobile ad hoc networks originated from the DARPA Packet Radio Network (PRNet) and SURAN project. Being independent on pre-established infrastructure, mobile ad hoc networks have advantages such as rapid and ease of deployment, improved flexibility and reduced costs.




 

Multicasting is the transmission of datagrams to a group of hosts identified by a single destination address and hence is intended for group-oriented computing. In MANETs, multicasting can support a variety of applications such as conferences, meetings, lecturers, traffic control, search and rescue, disaster recovery, and automated battlefield. In ad hoc networks, each host must act as a router since routes are mostly multihop.

Figure 1-1 shows an example of using MANET to hold conference meeting in a company. A group of mobile device users set up a meeting outside their normal office environment where the business network infrastructure is missing. The mobile devices automatically construct a mobile ad hoc network through wireless links and   communicate with one another. The figure shows topology of the network and the available wireless links at a certain time. Suppose Susan wants to send data to Jerry. According to the network topology, Jerry’s PDA is not in the immediate radio transmission range of Susan’s laptop. The routing software on Susan’s laptop finds a route Susan �� Tommy �� Jerry and sends the data packets to Tommy’s laptop. Then Tommy’s laptop forwards the packets to the destination, Jerry’s PDA. If the network topology changes and the wireless link between Susan and Tommy become broken, the routing software on Susan’s laptop will try to find another route.

Well established routing protocols do exist to offer efficient multicasting service in conventional wired networks. These protocols, having been designed for fixed networks, may fail to keep up with node movements and frequent topology changes in a MANET. As nodes become increasingly mobile, these protocols need to evolve to provide efficient service in the new environment. Therefore, adopting existing wired multicast protocols as such to a MANET, which completely lacks infrastructure, appears less promising. So new protocols need to be proposed and investigated so that they take issues like topological change. Ad hoc network may consist of unidirectional links as well as bidirectional links. Moreover, wireless channel bandwidth is limited. The scarce bandwidth decreases even further due to the effects of multiple access, signal interference, and channel fading. Securing Adhoc routing presents challenges because the constrains in Adhoc networks usually arise due to low computational and bandwidth capacity of the nodes, mobility of intermediate nodes in an established path and absence of routing infrastructure. All these limitations and constraints make multihop mobile ad hoc network research more challenging.

   1.2 Challenges in Routing and Multicasting

         Routes in ad hoc networks are multihop because of the limited propagation range of wireless nodes. Since nodes in the network move freely and randomly, routes often get disconnected. Routing protocols are thus responsible for maintaining and reconstructing the routes in a timely manner as well as establishing the robust routes. Furthermore, routing protocols are required to perform all the above tasks without generating excessive control message overhead. Control packets must be utilized efficiently to deliver data packets, and be generated only when necessary. Reducing the control overhead can make the routing protocol efficient in bandwidth and energy consumption.

Multipoint communications have emerged as one of the most researched areas in the field of networking. As the technology and popularity of Internet grow, applications, such as online gaming, video conferencing, that require multicast support are become more widespread. In a typical ad hoc environment, network hosts work in groups to carry out a given task. Therefore, multicast plays an important role in ad hoc networks. As we can see, providing efficient multicasting over MANET faces many challenges, including dynamic group establishment and constant update of delivery path due to node movement. Multicast protocols used in static networks like Distance Vector Multicast Routing Protocol (DVMRP), Multicast Open Shortest Path First (MOSPF), and Core Based Tree (CBT) do not perform well in wireless ad hoc networks because multicast tree structures are fragile and must be readjusted as connectivity changes. Hence, the tree structures used in static networks must be modified, or a different topology between members (i.e., mesh) need to be deployed for efficient multicasting in wireless mobile ad hoc networks [1]. Undoubtedly, multicast communication is an efficient means of supporting group oriented applications. This is especially true in MANETs where nodes are energy-and bandwidth limited. In these resources constrained environments, reliable point –to-point protocols can get prohibitively expensive. The Convergence of multiple requests to a single node typically causes intolerable congestion, violating the time constraints of a critical mission, and may drain the node’s battery, cutting short the network’s lifetime. Despite the fact that reliable multicasting is vital to the success of mission critical applications in MANETs.

1.2.1          Dynamic Topologies

Wireless nodes in an ad-hoc network are free to move about at will. As such, the topology of the network, which is typically multi-hop, is highly dynamic, changing randomly at unpredictable intervals in unpredictable ways. Because of wireless radio propagation effects, such as interference, links may be either bidirectional or unidirectional.

1.2.2 Bandwidth-constrained, variable capacity links

The bandwidth capacity of wireless networks will remain significantly below that of their wired counterparts. The realizable throughput of wireless links above the data link layer, due to effects such as noise, fading, interference, and the inability to use collision detection for media access control is often significantly less than the radio’s maximum throughput at the physical layer. The effects of this, and given that users of ad-hoc networks will demand similar high-bandwidth services to those on wired networks, means that congestion on wireless networks will be much more common than in wired networks.

1.2.3 Energy-constrained operation

Wireless networks will typically operate on laptop computers, hand-held computers and other battery-powered devices. As such, ad-hoc routing protocols must be designed with the conservation of the device’s energy in mind. There is a conflict between the requirements that nodes in an ad-hoc network must be willing to offer their services for forwarding packets for other nodes, versus the desirability from an energy conservation perspective that nodes sleep when they are not actively being used.

1.2.4   Limited physical security

There is an increased possibility of eaves-dropping, spoofing, and denial-of-service attacks on wireless networks, due in part to their relative lack of physical security in relation to their wired counterparts. Security enhanced versions of ad-hoc routing protocols could be used to ensure the operation of the routing protocol remains unaffected by attempts to forge or alter routing protocol control messages. Care must be taken when transferring sensitive data across an ad-hoc network. This could be achieved by conventional encryption. However, Public Key Infrastructure (PKI), or more basic key exchange techniques are difficult in an ad hoc network due to the lack of authorities of trust and appropriate network infrastructure.

1.2.5 Zero Configurations

Another desirable property of ad-hoc networks is that they should require little or no administrative overhead for their operation. It is desirable that when a group of Wireless nodes come together, they can negotiate all the relevant networking parameters automatically without manual intervention. In IP-enabled ad-hoc networks, the most important parameter is a node’s Internet Protocol (IP) address. This issue of assigning unique IP addresses to nodes in an ad-hoc network is another area of substantial research. Traditional wired networks typically use a centralized solution to the problem in the form of the Dynamic Host Configuration Protocol (DHCP). Given the lack of a central administrative body in an ad-hoc network, a distributed approach is required. It is likely the solution will involve nodes selecting their IP address at random, and using some means, such as examining Address Resolution Protocol (ARP) traffic from other nodes, to prevent or resolve issues where collisions have occurred.

1.3   Contributions

The accomplishments, which are elaborated throughout this dissertation, can be broadly listed as follows:

• A performed simulation of up to 50 seeds where each seed contains 100 nodes and evaluated ad hoc routing protocol scalability. Several schemes were introduced to improve the protocol performance in large networks. This work is the first to conduct a simulation study of such size using Qualnet 4.0 and NS 2.27.
• Proposed the On-Demand Multicast Routing Protocol (ODMRP). ODMRP builds the mesh structure on demand to provide multiple paths among multicast members. The mesh makes the protocol robust to mobility. ODMRP can function as multicast and unicast.  The protocol was implemented in simulation platform using GloMoSim and Qualnet 4.0.
• Applied various techniques to enhance the performance of ODMRP. Theses enhancements include mobility predictions, reliable packet delivery, and elimination of the route acquisition latency.
• Studied the various QoS requirements with multicast routing in ad hoc networks and proposed a new cross-layer framework which provides QoS guarantee to multicast routing in MANETs. These QoS parameters include call-admission, bandwidth reservation and delay constraint.
• Developed and implemented an Adhoc QoS multicasting (AQM) algorithm and proposed a cross layer framework to support QoS multicasting. This work is the first to provide multicast quality of service in mobile ad hoc networks.
• Proposed ReAct transport layer protocol on top of the multicast zone routing protocol to provide reliable services. Achieved good scalability and high throughput by employing local recovery mechanism. The protocol was implemented in simulation platform using Qualnet 4.0.
• The problem of constructing energy-efficient key distribution schemes for securing multicast communication in wireless ad hoc networks was studied. The network topology, the power proximity and the path loss characteristics of the medium were incorporated in the key distribution tree design to conserve energy. The algorithm has been developed for homogeneous environment.

1.5   Related Work

 1.5.1   Classification of Ad-hoc Routing Protocols

Ad-hoc routing protocols can broadly be classified into proactive, reactive and hybrid protocols. The approaches involve a trade-off between the amount of overhead required to maintain routes between node pairs (possibly pairs that will never communicate), and the latency involved in discovering new routes as needed.

1.5.1.1   Proactive Protocols

Proactive protocols, also known as table-driven protocols, involve attempting to maintain routes between nodes in the network at all times, including when the routes are not currently being used. Updates to the individual links within the networks are propagated to all nodes or a relevant subset of nodes, in the network such that all nodes in the network eventually share a consistent view of the state of the network. The advantage of this approach is that there is little or no latency involved when a node wishes to begin communicating with an arbitrary node that it has not yet been in communication with. The disadvantage is that the control message overhead of maintaining all routes within the network can rapidly overwhelm the capacity of the network in very large networks, or situations of high mobility. Examples of pro-active protocols include the Destination Sequenced Distance Vector (DSDV), and Optimized Link State Routing (OLSR).

1.5.1.2   Reactive Protocols

Reactive protocols, also known as on-demand protocols, involve searching for routes to other nodes only as they are needed. A route discovery process is invoked when a node wishes to communicate with another node for which it has no route table entry. When a route is discovered, it is maintained only for as long as it is needed by a route maintenance process. Inactive routes are purged at regular intervals. Reactive protocols have the advantage of being more scalable than table-driven protocols. They require less control traffic to maintain routes that are not in use than in table-driven methods. The disadvantage of these methods is that an additional latency is incurred in order to discover a route to a node for which there is no entry in the route table. Dynamic Source Routing (DSR) and the Ad-hoc On-demand Distance Vector Routing (AODV)  protocol are examples of on-demand protocols.

1.5.1.3   Hybrid Protocols

There exists another class of ad-hoc routing protocols, such as the Zone Routing Protocol (ZRP), which employs a combination of proactive and reactive methods. The Zone Routing Protocols maintains groups of nodes in which routing between members within a zone is via proactive methods, and routing between different groups of nodes is via reactive methods.

1.5.1.4   Multicast Routing Protocols

One Straightforward way to provide multicast in a MANET is through flooding. With this approach, data packets are sent throughout the MANET, and every node that receives this packet broadcasts it to all its immediate neighbor nodes exactly once. It is suggested that in a highly mobile ad hoc network, flooding of the whole network may be a feasible alternative for reliable multicast. However, this approach has considerable overhead since a number of duplicated packets are sent and packet collisions do occur in a multiple access based MANET . Furthermore, multicast routing protocols are classified into four categories based on how routes are created to the members of the group:

      Tree-based approaches

      Mesh-based approaches

      Stateless multicast

      Hybrid approaches

Tree-based multicast is a very well established concept in wired networks. Protocols such as Ad hoc Multicast Routing Protocol Utilizing Increasing ID Numbers (AMRIS), Multicast Ad hoc On-Demand Distance Vector (MAODV), Lightweight Adaptive Multicast (LAM), and Location Guided Tree Construction Algorithm for Small Group Multicast are belonging to this category.

In contrast to a tree-based approach, mesh-based multicast protocols may have multiple paths between any source and receiver pair. Protocols such as On-Demand Multicast Routing Protocol (ODMRP), Dynamic Source Routing (DSR), and Temporarily Ordered Routing Algorithm (TORA) are belonging to this category.

Tree and Mesh based approaches have an overhead of creating and maintaining the delivery tree/mesh with time. In a MANET environment, frequent movement of mobile nodes considerably increases the overhead in maintaining the delivery tree/mesh. To minimize the effect of such a problem, stateless multicast is proposed wherein a source explicitly mentions the list of destinations in the packet header. Stateless multicast focuses on small group multicast. Protocol Differential Destination Multicast (DDM) is belongs to this approach .

The tree-based approaches provide high data forwarding efficiency at the expense of low robustness, whereas mesh based approaches provide better robustness at the expense of higher forwarding overhead and increased network load. The hybrid approach combines the advantage of both approaches. Protocols such as Ad hoc Multicast Routing Protocol (AMRoute), Multicast Core Extraction Distributed Ad hoc Routing (MCEDAR) are belonging to this category.