Abstract: In this study a power aware on demand routing protocol using mobile agents called Agent Based Ad hoc on Demand Distance vector routing protocol (AB-AODV) was proposed. This protocol uses the on demand capability of Ad hoc on Demand Distance Vector (AODV) routing protocol and a distributed topology discovery mechanism using mobile agents. Our protocol model uses a mixture of mobile and static agents to gather relevant information. These agents could perform important tests, which could be used to generate the best power aware route through a network. This research looks at different models for the deployment of these agents, which balance the usage of static and mobile agents. These are appraised in the terms of performance, reconfigurability and easy of installation. However, the simulation studies carried out for table-driven and on-demand ad hoc routing protocols fall short of examining essential power-based performance metrics, such as average node and network lifetime, energy-based protocol fairness, average dissipated energy per protocol and standard deviation of the energy dissipated by each individual node. This research present a thorough energy-based performance study of power aware AODV routing protocols for wireless mobile ad hoc networks. Moreover, we propose some novel enhancements to routing in wireless ad hoc networks that enables the admission of flows without jeopardizing the limited energy of the wireless stations.
INTRODUCTION
An ad hoc network is a collection of wireless mobile hosts forming a temporary without the aid of any centralized administration or standard support services. Ad hoc wireless networks eradicate the costs of infrastructure deployment, setup and administration. Ad hoc wireless networks allow anywhere, anytime network connectivity with complete lack of control, ownership and regulatory influence. The limited energy capacity of the mobile devices making up the network draws our attention to the importance of power awareness in ad hoc network protocol design (Safwat et al., 2002). Most of the research performed in the field of wireless ad hoc networks has focused on the problem of routing. Bandwidth efficiency and end-to-end delays were the main concern of the developed protocols and the conducted simulation studies. Due to the limited energy capacity of the wireless devices and the importance of power awareness in ad hoc routing protocol design, a thorough energy-based performance study is essential.
The conventional routing protocols for mobile ad hoc network suffers form certain inherent shortcomings. The proactive routing scheme continuously updates the routing tables of mobile nodes consuming large amount of power for exchanging large chunks of route table data. On the other hand, the on-demand routing protocol launches a route discovery and delays the actual communication until the route is discovered. This may not be suitable for real time data and multimedia communication application.
A mobile agent can be used for efficient routing in a network and discovery topology, to provide high connectivity at the nodes. A mobile agent can be defined as a software program that can suspend its execution on a host computer, transfer itself to another agent-enabled host on the network and resume its execution on the new host. A mobile agent is a program which is capable of migrating form one node to another node in a network to perform the designated task. The ability to migrate code and processing function to a remote node offers the potential benefits of reduced network traffic and bandwidth requirement. The key features of mobile agents that distinguish them from traditional distributed programming are: mobility; network awareness; communication; intelligence; reactivity; autonomous; goal-oriented; temporally continuous; learning; flexible and character (Ho et al., 2000; Franklin and Graesser, 1996). Mobile agent technology has been proposed for a number of applications such as Internet-wide collaborative systems, network management, monitoring systems, information retrieval, intrusion detection systems and e-commerce. A new potential application of mobile agents is in mobile computing environments and, especially, in wireless networks. Mobile agents are ideal for such environments because of their ability to support asynchronous communication and flexible query processing. This is because user tasks can be delegated to mobile agents, when a mobile client is disconnected (Lauzac and Chrysanthis, 2002). In certain cases, mobile agents can reduce network traffic compared to the traditional client-server approaches and maintain load balancing, thus increase performance of network nodes especially in wireless ad-hoc networks (Braun, 2004). This study proposed a novel application of mobile agents and ad hoc networks in terms of power aware routing, topology discovery and automatic network reconfiguration.
EXISTING ROUTING AND ENERGY CONSERVATION SCHEMES
Routing protocols in wireless mobile ad hoc networks can be classified as table-driven and on-demand. In table-driven routing protocols, all the mobile stations are required to have complete knowledge of the network through their periodic and incremental/triggered updates. Unnecessary periodic updates may have a negative effect on energy conservation. Table-driven routing is also known as proactive routing. Examples of table driven routing protocols include Global State Routing (GSR) (Tsu-Wei and Gerla, 1998) and Destination-sequenced Distance Vector (DSDV) (Perkins and Bhagwat, 1994). Nodes running GSR exchange vectors of link states among their neighbors. In DSDV, loops are avoided using sequence numbers which provide a means to enable mobile nodes to distinguish old routes from new ones. On-demand routing requires that routes are built between nodes only as desired by source nodes. Hence, the terms on-demand and reactive can be used interchangeably. On-demand routing is composed of route discovery and route maintenance. In route discovery, a source uses flooding to acquire a route to its destination. This degrades system-wide energy conservation. The transit nodes, upon receiving a query, learn the path to the source and enter the route in their forwarding tables. The destination node responds using the path traversed by the query. Route maintenance is responsible for reacting to topological changes in the network and its implementation differs from one algorithm to the other. On-demand protocols include Ad hoc on Demand Distance Vector Routing (AODV) (Perkins and Royer, 1999) and Dynamic Source Routing (DSR) (David and Maltz, 1996). In on-demand protocols, route discovery and maintenance may become inefficient under heavy network load since intermediate nodes will have a higher probability of moving due to the delay in packet transmissions attributed to MAC contention. Hence, routes will also have a higher probability of breaking as a result of mobility. This wastes battery power and thus the lifetime of the wireless nodes decreases. It is worth mentioning that the flooding of route request and route reply packets in on-demand routing protocols may result in considerable energy drains under a realistic energy consumption model that takes idle time and promiscuous mode power into account. Every station that have ability to hears the route request broadcasts will consume an amount of energy proportional to the size of the broadcast packet. In addition, stations that hear a corrupted version of a broadcast packet will still consume some amount of energy. Besides, the simulation studies carried out for table-driven and on-demand routing protocols fall short of providing necessary power-based performance metrics, such as average node and network lifetime, average dissipated energy per protocol, standard deviation of the energy dissipated by each individual node, etc.
A number of routing proposals for ad hoc networks took energy conservation into consideration so as to extend the lifetime of the wireless nodes by wisely using their battery capacity. Singh et al. (1998) proposed a multi-tier power conservation approach, optimizing the MAC layer, network layer and transport layer protocols individually. The routing algorithm they proposed and implementation involves choosing the minimum residual energy path so as to minimize the total node cost per packet. The cost at each node is defined as the residual battery energy at each node. Their MAC layer power optimization algorithm was discussed by Singh and Raghavendra (1988). Minimum Total Power Routing (MTPR) was proposed by Scitt and Bambos (1996). If the total transmission power for route R is PR, then the route can be obtained from:
Where, S is the set containing all possible paths. On the downside, this approach will in most cases tend to select routes with more hops than others. This is realizable due to the fact that transmission power is inversely proportional to distance (Braun, 2004). Thus, more energy may be wasted network-wide since a larger number of nodes are now involved in routing as all nodes that are neighbors to the intermediate nodes will also be affected, unless they were in sleep mode. Minimum Battery Cost Routing (MBCR) (Singh et al., 1998) utilizes the sum of the inverse of the battery capacity for all intermediate nodes as the metric upon which the route is picked. However, since it is the summation that must be minimal, some hosts may be overused because a route containing nodes with little remaining battery capacity may still be selected. Min-max Battery Cost Routing (MMBCR) (Singh et al., 1998) treats nodes more fairly from the standpoint of their remaining battery capacity. Smaller remaining battery capacity nodes are avoided and ones with larger battery capacity are favored when choosing a route. The route is found using the equation:
However, more overall energy will be consumed throughout the network since minimum total transmission power routes are no longer favored. MTPR is used when all the nodes forming a path (note that one path is sufficient) have remaining battery capacity that is above a so-called battery protection threshold and MMBCR is used if no such path exists (Toh, 2001). The combined protocol is called conditional Max-min Battery Capacity Routing (CMMBCR). The approach was to minimize the total energy expenditure to reach the destinations. Consequently, some nodes are overused and their batteries are thus depleted. In our proposed model, we use mobile agent for selecting the power aware route for transmission. Here we modify the AODV protocol slightly to make it compatible with mobile agents.
PROPOSED PROTOCOL MODEL
AODV routing protocol: AODV routing protocol is also based upon distance vector and uses destination sequence numbers to determine the freshness of routes. It operates in the on-demand fashion. AODV requires hosts to maintain only active routes. An active route is a route used to forward at least one packet within the past active timeout period. When a host needs to reach a destination and does not have an active route, it broadcasts a route request (RREQ), which is flooded in the network. A route can be determined when RREQ is received either by the destination itself or by an intermediate host with an active route to that destination. A route reply (RREP) is unicast back to the originator of RREQ to establish the route. Each host that receives RREQ caches a route back to the originator of the request, so that RREP can be sent back. Every route expires after a predetermined period of time. Sending a packet via a route will reset the associated expiry time. It uses HELLO messages to determine the connectivity among the neighbours.
Features of this protocol include loop-freedom and that link breakages cause immediate notification to be sent to the affected set of nodes. AODV also supports multicast routing and avoids the Bellman-Ford counting-to-infinity problem. The use of destination sequence number ensures the freshness of the route. AODV also uses periodic Hello broadcast by the nodes in the network to inform each mobile node of other nodes in its neighbourhood. This broadcast message is used to maintain local connectivity. If a node along a route moves, its upstream neighbor notices the move and propagates a link failure notification/route error message (RERR) to each of its active upstream neighbor to inform the removal of that part of the route.
Mobile agents: Mobile agents have the ability to support asynchronous communication and flexible query processing. Therefore, the mobile user can assign a task to a mobile agent and when the agent feels that there is communication availability that will roam the network and fulfill the task delegated by its user. In this way, a mobile node requires less communication connectivity than it would need following traditional client/server approaches. Another equally important reason for mobile agents in wireless networks is that they can reduce network traffic. Mobile nodes running on battery power do not have enough power to run complex routing protocols necessary in ad hoc networks. An alternative is to use mobile agents to perform routing operations and thus reduce complexity and network traffic. Thereby, saving the important battery life of mobile computers. The research proposes to access different models of the usage of static and mobile agents to determine the best route through ad-hoc networks. The idea is based on the fact that in each mobile node there will be a static agent that will run on the background monitoring available resources such as connection availability, processing power, memory capacity, cost and so on. In addition to static agents, mobile agents will be independently roaming the ad hoc network gathering information from static agents. Then they will use the information gathered to perform necessary calculations in order to determine the best path for routing network traffic. Mobile agent system is shown in Fig. 1.
Agent-based AODV routing algorithm: In the New routing protocol proposed here we have combined the features of Agent Based routing and AODV routing protocol.
| Fig. 1: | Mobile agent system |
| Fig. 2: | Proposed model |
We tried to eliminate the drawbacks of both the algorithm. This hybrid algorithm enhances the node connectivity and decreases the end-to-end delay and route discovery latency.
Agent-Based AODV routing protocol (AB-AODV) utilizes agents working independently and providing routes to the nodes. Each node will run an agent server that provides the basic functionality for static and mobile agents, such as migration, communication and security. Possibly, the agent server will be written in Java language due to its object-orientation nature, object serialization and remote method invocation techniques and enhanced security. Static agents will be resident on mobile hosts and will be continuously running. These agents will be mainly responsible for the following operations: maintain a routing table; decide the path with minimum transmission power to route network traffic based on power information found on the routing table and monitoring system’s resources in terms of memory capacity, processing capabilities, network performance, cost and so on. On the other hand, mobile agents will be responsible for the following operations: collect information generated from static agents; update routing tables on mobile hosts and discovering new routes. They must also inform static agents; and other mobile agents for changes in the network. Static agents will maintain routing tables continuously, decide the power aware path dynamically and monitor system’s resources periodically. Mobile agents will collect information from static agents periodically, update routing tables periodically and communicate with static agents and other mobile agents when necessary. Figure 2 shows the model with four mobile hosts, four static agents and two mobile agents.
The nodes also have the scalability of launching on-demand route discovery to find routes to the destination when they do not have a fresh enough route entry. The use of mobile agents with AODV increases the nodes connectivity which in turn reduces the amount of route discoveries. Even if a node launches a route discovery message (RREQ) for a destination which does not have a fresh enough route, the probability of receiving the reply from the neighboring node is very high due to the increased connectivity of all nodes. This reduces route discovery latency. Lastly, an mobile agent update the routes continuously, a source node can switch from longer or stale route to a newer and shorter route provided by the agents which reduces the overall transmission power of the nodes in the network. This leads to decreases in the average end-to-end delay as compared to both AODV and agent based routing. Local connectivity is maintained by using route error message (RERR). The routing table used in this algorithm is common for both AODV protocol and mobile agents.
SIMULATION MODEL
The Agent Based AODV protocol proposed here is compared with conventional AODV routing protocol. Network Simulator NS-2 (2001) is used to simulate these protocols. NS-2 is a discrete event simulator. The physical layer for the simulation uses the 2-ray ground reflection as radio propagation model. The link layer is implemented using IEEE 802.11 Distributed Coordination Function (DCF)and Media Access Control (MAC). It uses RTS/CTS/DATA/ACK patter for unicast packets and DATA for broadcast packet. Carrier sense Multiple Access with Collision Avoidance (CSMA/CA) is used to transmit these packets. The transmission parameters used in the simulation is shown in Table 1.
The protocols simulated here maintain a send buffer of 64 data packets, containing data packets waiting for a route. Packets send by the routing layer are queued at the interface queue till MAC layer can transmit them, which has a maximum size of 50 data packets.
| Table 1: | Transmission parameters |
Routing table used by the two protocols are same. Every route entry in the routing table has a destination node address, next hop node, the power needed to reach the node, the sequence number of the destination and time to live period for that route.
Mobility model: The mobility model uses the random waypoint model. The simulation was done on 6 different pause times; 0, 30, 60, 120, 300 and 600 sec. Pause time is a dormant time during which nodes do not move after reaching a destination. After pausing for a pause time seconds it again selects a new destination and proceeds at a speed distributed uniformly between 0 and certain maximum speed.
Traffic model: Twenty Continuous Bit Rate (CBR) connections (traffic flows) were used for the simulations. CBR traffic sources were chosen, as the aim was to test the routing protocols. Source nodes and destination nodes were chosen at random with uniform probabilities. Connections were started at times uniformly distributed from 0 and 180 sec. The sending rate used was 4 packets per second with a packet size of 64 bytes. Each data point in the comparison results represents an average of multiple runs with identical traffic models but with different movement scenarios. Same movement and traffic scenario were used for all the two protocols.
RESULTS
Average end-to-end delay: This includes buffering delay during route discovery, queuing delay at interface queue, retransmission delays and propagation and transfer times. Comparing AB-AODV and AODV it can be observed that the end-to-end delay (Fig. 3) is considerably reduced in AB-AODV as compared to AODV. Agent programs help in maintaining high connectivity in AB-AODV, hence the packets need not wait in the send buffer till the routes are discovered.
| Fig. 3: | Average end-to-end delay provided by AODV and AB-AODV routing
protocols |
| Fig. 4: | Packet delivery fraction of AODV and AB-AODV routing protocols |
Even if the source node does not have a ready route to the destination, due to the increases connectivity at all the nodes the probability of its receiving replies quickly from nearby nodes is high resulting in reduced route discovery latency. Lastly, the dynamic nature in which routes are kept updated by the mobile agents leads to the source node switching from a longer (and stale) route to newer and shorter ones hence reducing end-to-end delay for active routes.
Packet delivery fraction: Packet delivery fraction is the ratio of number of data packets sent to the number of data packets received. From the Fig. 4 it is seen that packet delivery fraction is high for AB-AODV. This is because they make use of link failure detection and route error messages.
Normalized routing overhead: Normalized routing overhead is the number of routing packets transmitted per data packet received at the destination. The routing overhead in case of ant-based routing is independent of the traffic. Even if there is no communication the mobile agents would still be traversing the network and update the routing tables. However in case of AODV, the overhead is dependent on the traffic and if there is no communication then there will be no control messages generated in the network. In AB-AODV the overhead has two components.
| Fig. 5: | Comparison of normalized routing overhead in AB-AODV and AODV
routing protocols |
| Fig. 6: | Comparison of connectivity in AODV and AB-AODV routing protocols |
| Fig. 7: | Transmit power of AODV and AB-AODV routing protocols |
It has the agents traversing in the network and the route discovery and route reply messages being generated in case the nodes do not have routes provided to them by the agents for some destinations. From the comparison results (Fig. 5) it is seen that the normalized overhead is too high in case of agent-based routing scheme. The reason for this is that the actual data packets delivered are too less and hence the ratio of control overhead to data packets delivered becomes too high. In case of AODV (Fig. 6) the normalized overhead is the least. The normalized overhead is slightly greater in AB-AODV as compared to AODV because of the continuous movement of agents in the network.
Connectivity: Connectivity is the average number of nodes in the network for which a node has un-expired routes. In case of AB-AODV, the agents continuously traverse the network and update the routing table entries. Due to this, a node has fresh enough (or un-expired) routes to a large number of nodes in the network at any given point of time. Connectivity in AB-AODV is more than double the connectivity in AODV (Fig. 6). Higher connectivity leads to lesser route discoveries, which in turn reduces power consumption for route and reduced end-to-end delay.
Power optimization: Here only the transmit power is taken into consideration. Transmit power is the power spent on transmission alone i.e., not including power spent by nodes to listen, receive and process packets. Figure 7 that AODV protocol consumes excess transmit power as it uses more number of hops. We can see that our proposed AB-AODV has produced sufficient reduction in transmit power consumption
Performance of AB-AODV: It is evident from the simulation results that by combining mobile agents with the on-demand route discovery mechanism of AODV, the AB-AODV hybrid routing protocol would give reduced end-to-end delay and route discovery latency with high connectivity. Such low end-to-end delay cannot be achieved from AODV protocol because of their inherent shortcomings.
CONCLUSIONS
The shortcomings of on-demand routing protocols like AODV routing have been tried to overcome in this paper by combining mobile agents with AODV enhance its capabilities and alleviate its weaknesses. AB-AODV hybrid protocol is able to provide reduced end-to-end delay, high connectivity and less power consuming as compared to AODV. As a result of increased connectivity the number of route discoveries is reduced and also the route discovery latency. This makes AB-AODV hybrid routing protocol suitable for real-time data and multimedia communication. As a direct result of providing topology information to the nodes (using mobile agents), the foundations for designing a distributed network control and management get automatically laid. Higher connectivity and reduced end-to-end delay are achieved at the cost of extra processing of the agents messages and the slightly higher overhead occupying some network capacity. However this does not adversely affect the packet delivery fraction. Even though the nodes uses additional power for processing the agent messages, when we consider the total transmit power consumed by all node in the network it is comparatively better in AB-AODV than AODV. The future research would be to explore the use of back up or multiple routes provided to the nodes by agents in their frequent and continuous visits to the node.