The Selective Intermediate Nodes Scheme for Ad Hoc On-Demand Routing Protocols 1The Selective Intermediate Nodes Scheme for Ad Hoc On-Demand RoutingProtocols 1 Yunjung Yi, Mario Gerla and Taek Jin Kwon*Computer Science DepartmentUniversity of California at Los Angeles, CA 90095*Telcordia Technologies, Applied ResearchRed Bank, NJ 07701 1This work is supported by ONR “MINUTEMAN” project under contract N000014-01-C-0016Abstract The on-demand routing schemes in mobile ad hoc networks are appealing because of the lower routing overhead, compared with traditional proactive schemes. The on-demand routing protocols introduce routing overhead only in the presence of data packets that need routes. However, the control overhead of on-demand routing schemes increases with node geographic density and traffic pattern density. In fact, this is undesirable feature for the scalable routing protocols whose control overhead should be under control to keep up with increasing offered load. As a solution for such a drawback of current reactive routing schemes, we propose Selective Intermediate Node s mechanism. In this protocol, each node adaptively propagates routing information based on the local load level and cluster status. The local load level (local load status), based on channel utilization and queue size, reflects the load of the node in question and of all of its neighbors; the cluster status denotes the role of a node in a cluster (i.e., a cluster head, gateway or ordinary node). We demonstrate the effectiveness of our enhancement by applying it to Ad hoc On-demand Distance Vector Routing (AODV) and Dynamic Source Routing (DSR). Simulation results show that proposed idea significantly reduces the control overhead and improves the overall performance and scalability of the routing protocols. I.I NTRODUCTION Multi-hop ad hoc networks (MANETs) have been in the spotlight because they are self-creating, self-organizing, and self-administering without using any kind of infrastructure. MANET offers unique benefits and versatility for wide applications in military (e.g., battlefields, sensor networks etc.), commercial (e.g., distributed mobile computing, disaster discovery systems etc.), and educational environments (e.g., conferences, conventions etc.), where preexisting fixed infrastructure cannot be easily acquired. With the absence of fixed infrastructure in a MANET, nodes can communicate with one another in a peer-to-peer fashion. Two nodes communicate directly if they are in the transmission range of each other. Otherwise, nodes can communicate via a multi-hop route with the cooperation of other nodes. Evidently, each MANET node must therefore be able to function as a router, forwarding data packets on behalf of other nodes. As the topology changes due to node mobility or dynamic link bandwidth, the routes must be instantaneously updated using control messages. However, the limited bandwidth of ad hoc networks imposes aconstraint on the amount and frequency of control overhead for this maintenance. For this reason, ensuring effective “mobile” routing is one of the great challenges in the design of MANETs. Ad hoc routing protocols, with parsimonious communication and processing overhead, must survive the high degree of node mobility and unpredictable topology changes.Current studies of ad hoc routing protocols can be classified into two approaches proactive and reactive routing . Proactive routing protocols (e.g., OSPF 5, OLSR 19), which are commonly used in the wired networks, maintain routes by exchanging the route table periodically. In ad hoc networks, the route table must be updated frequently enough to handle the dynamic topology changes. This constraint may involve a large amount of routing overhead caused by intensive exchanges of the route tables regardless of the actual needs for routes. Indeed, huge routing overhead has serious impact on the overall performance in the limited bandwidth networks. On the other hand, the principal aim of reactive routing approaches (e.g., AODV 9, DSR 10) is to reduce the routing overhead with dynamic maintenance of routes. Reactive routing schemes can reduce control overhead at the expense of setup latency due to the route search. In most on-demand routing protocols, a node initiates a route query flood only in the presence of the data packet that needs a new path. Each node that has received the route search packet is in charge of forwarding the packet to reach the destination no matter how much load this node currently has. Upon the reception of a route query packet, the destination sends the route reply packet to the source via the reverse path of the shortest route through which a route request packet passes. Reactive routing protocols work more successfully and effectively when the frequency of route maintenance packets and the demand of route queries are not high, compared with proactive routing schemes.Both routing s