Figure 1. View of Mobile Adhoc Networks [1]
In 1990's, Mobile Adhoc networks have been widely researched for many years. Mobile Ad-hoc Networks are a collection of two or more devices equipped with wireless communications and networking capability. These devices can communicate with other nodes that are within their radio range or one that is outside their radio range. For the latter, the nodes should select an intermediate node to be the router to forward the packets from the source to the destination. In MANETs, every node can act as the gateway. In this dissertation, focus is laid on energy efficiency. There are many routing protocols in MANETs like DSDV, DSR and AODV etc. and each one has its own approach for dissemination of data packets in MANETs. But these routing protocols are less energy efficient. The aim of this dissertation is to design a routing protocol which would be better than the existing ones in terms of energy utilization and delivery ratio. In this dissertation, an energy efficient routing protocol has been proposed which uses Dijkstra's algorithm as a fundamental algorithm to route the nodes to their intended destination and a comparison is laid between the proposed protocol, AODV, DSDV and DSR, and the performance measures are evaluated.
Deployed in 1990's, Mobile Adhoc networks have been widely researched for many years [3]. Among all the contemporary wireless networks, Mobile Ad hoc Networks (MANETs) is one of the most important and unique applications [5, 10]. Mobile Ad-hoc Networks is a collection of two or more devices equipped with wireless communications and networking capability. These devices can communicate with other nodes that are within their radio range or one that is outside their radio range. For the latter, the nodes should deploy an intermediate node to be the router to route the packet from the source toward the destination. The Wire-less Adhoc Networks do not have gateway, every node can act as the gateway. Although since 1990s' lots of research has been done on this particular field, it has been questioned as to whether the architecture of Mobile Adhoc Networks is fundamental flawed architecture. The main reason for the argument is that Cellular Networks are almost never used in practice, almost every wireless network nodes communicate to base station and access points instead of co-operating to forward packets hop-by-hop.
Mobile Adhoc Network (MANET) is a collection of independent mobile nodes that can communicate with each other via radio waves. The mobile nodes that are in radio range of each other can directly communicate, whereas others need the aid of intermediate nodes to route their packets. These networks are fully distributed, and can work at any place without the help of any infrastructure. Figure 1 shows view of MANETs [1] .
Figure 1. View of Mobile Adhoc Networks [1]
Following are the characteristics of MANETs [2]
The emergence of MANETs has made a tremendous impact on IT industry over the past few years. MANETs provide cheap, flexible and reliable ways of computing to IT industry. MANETs are in initial stage, with many issues still to be addressed [8, 17].
The nodes in the Mobile Adhoc Networks are normally power curb because of their dependency on power. In wireless communication, especially in MANETs, remarkable amount of energy is consumed not only in transmission among the nodes, but also in overhearing of the packets sent from other nodes [4]. As green computing is emerging, it is required to formulate a routing protocol which is energy-efficient. One of the most important objectives of MANETs routing protocols is to maximize energy efficiency, since nodes in MANETs depend on limited energy resources. The possible energy consumption states are: transmit, receive, idle and dead.
The main objectives of MANETs routing protocols are to maximize throughput (network), energy efficiency, network lifetime and to minimize the delay. The network throughput is usually measured by packet delivery ratio, while the most significant contribution to energy consumption is measured by routing overhead which is the number or size of routing control packets.
“Routing is the process of information exchange from one host to the other host in a network.” [3]. Routing is the mechanism of forwarding packet towards its destination using most efficient path. The primary objectives of MANET routing the protocols are to maximize network throughput, to maximize energy efficiency, maximize network lifetime, and to minimize delay. The network throughput is usually measured by packet delivery ratio, while the most significant contribution to energy consumption is measured by routing overhead, which is the number or size of routing control packets. In order to achieve Quality of Service (QoS), several routing models have been proposed. Routing protocol for ad-hoc network can be categorized into two strategies.
In proactive routing scheme, every node continuously maintains complete routing information of the network. This is achieved by flooding network periodically with network status information to find out any possible change in network topology. Current routing protocols like Link State Routing (LSR) protocol (open shortest path first) and the Distance Vector Routing Protocol (Bellman-Ford algorithm) are not suitable to be used in mobile environment.
Destination Sequenced Distance Vector (DSDV) routing protocol and Optimized Link State Routing (OLSR) protocol were proposed to eliminate counting to infinity and looping problems of the distributed Bellman-Ford algorithm and widely used in mobile environment [12] .
This protocol is based on classical Bellman-Ford routing algorithm [7, 14] designed for MANETs. Each node maintains a list of all destinations and number of hops to each destination. Each entry is marked with a sequence number. It uses full dump or incremental update to reduce the network traffic generated by route updates. The broadcast of route updates is delayed by settling time. The only improvement made here is avoidance of routing loops in a mobile network of routers. With this improvement, routing information is always available, regardless of whether the source node requires the information or not. With the addition of sequence numbers, routes for the same destination are selected on the basis of following rules [1]:
The routing table of DSDV maintains the following list of fields as shown in Table 1:
Table 1. Fields of DSDV routing protocol
The sequence number is used to distinguish stale routes from new ones and thus it avoids the formation of loops. The stations periodically transmit their routing tables to their immediate neighbours. A station also transmits its routing table, if a significant change has occurred in its table from the last update sent [16]. So, the update is both time-driven and event driven.
Each row of the sent update is of the following form:
After receiving an update, neighbouring nodes utilize it to compute the routing table entries. This resolves the route failure of DSDV [9].
Figure 2 shows that link between e and h has broken. Figure 3 shows that a broadcast request has been made to the neighbors to update the routing tables. Figure 4 shows that new links have been established.
Figure 2. Link from e to h breaks [9]
Figure 3. A broadcast request to the neighbours [9]
Figure 4. Link Established [9]
Every node in this routing protocol maintains the information of only active paths to the destination nodes. A route search is needed for every new destination, therefore, the communication overhead is reduced at the expense of delay to search the route. Rapidly changing wireless network topology may break the active route and cause subsequent route search [6, 11]. Most effective routing protocols are AODV and DSR.
Ad hoc On-demand Distance Vector Routing (AODV) is an improvement of the DSDV algorithm discussed in section 2.1.1. AODV minimizes the number of broadcasts by creating routes on-demand as opposed to DSDV that maintains the list of all the routes [15, 16].
To find a path to the destination, the source broadcasts a route request packet [7, 13]. The neighbours in turn, broadcast the packet to their neighbours till it reaches an intermediate node that has recent route information about the destination or till it reaches the destination shown in Figure 5 [17]. A node discards a route request packet that has already been seen. The route request packet uses sequence numbers to ensure that the routes are loop free and to make sure that if the intermediate nodes reply to route requests, they reply with the latest information only [6, 14].
Figure 5. Propagation of route Requests (RREQ) Packets [18]
When a node forwards a route request packet to its neighbours, it also records in its tables, the node from which the first copy of the request came. This information is used to construct the reverse path for the route reply packet. AODV uses only symmetric links because the route reply packet follows the reverse path of route request packet. As shown in Figure 6, the route reply packet traverses back to the source [18], and the nodes along the path enter the forward route into their tables. If the source moves, then it can reinitiate route discovery to the destination. If one of the intermediate outing nodes move, then the moved nodes’ neighbour realizes the link failure and sends a link failure notification to its upstream neighbours and so on, till it reaches the source upon which the source can reinitiate route discovery, if needed.
Figure 6. Path taken by the Route Reply (RREP) Packets [18]
The Dynamic Source Routing Protocol is a source-routed on-demand routing protocol. A node maintains route caches containing the source routes that it is aware of. The node updates entries in the route cache as and when it learns about new routes.
The two major phases of the protocol are: route discovery and route maintenance [7, 14]. When the source node wants to send a packet to a destination, it looks up its route cache to determine if it already contains a route to the destination. If it finds that an unexpired route to the destination exists, then it uses this route to send the packet. But if the node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet. The route request packet contains the address of the source and the destination, and a unique identification number [15, 16]. Each intermediate node checks whether it knows of a route to the destination. If it does, it appends its address to the route record of the packet and forwards the packet to its neighbors. To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and its address is not present in the route record of the packet.
A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet. A route request packet reaching such a node already contains in its route record, the sequence of hops taken from the source to this node. Figure 7 [18] shows the building of route during route discovery and Figure 8 [18] shows the propagation of route reply with the route record.
Figure 7. Building Record Route during Route Discovery [18]
Figure 8. Propagation of Route Reply with the Route Record [18]
As green computing is emerging, it is required to formulate a routing protocol which is energy efficient. Here, a new routing algorithm has been articulated which has been observed to be an energy efficient technique. The research work has been classified into three cases based on the number of nodes. First case when n = 20, second case when n = 25, third case when n = 50.
Energy required for transmission of packets. It is denoted by Et. Here, the value of transmission energy is assumed as Et = 0.32.
Energy required for processing of packets. It is denoted by Ep. Here, the value of processing energy is assumed as Ep = 0.25.
During routing Et > Ep
Also transmission energy and processing energy of each node would be same, as the network is homogenous.
Total energy is denoted by T.E. Total energy for all the intermediate nodes is taken as T.E. = 10 Joules. For source node and destination node, it is taken to be T.E. = 50 Joules.
While transmission of data packets, energy utilized at each node = number of data packets each node can handle * (Transmission energy + processing energy) i.e.
The remaining energy of each node would be E.R. = Total energy – Energy utilized i.e.
Maximum number of packets which each node can handle without failure when number of nodes is 10 has been calculated as shown below:
comes out to be≈17. So if a node tries to handle equal to or greater than 17 packets, it would be considered as dead node in the network. Also, the total amount of data that can be simultaneously transmitted for one hop increases linearly with the total area of the ad hoc network.
The routing algorithm proposed in this thesis has been designed using Dijkstra's Algorithm for graphs. First of all, energy utilization of each mobile node of the Mobile Adhoc Network has been calculated as described above. Also, an incidence matrix edge[][] is created for the network connectivity. Now for two nodes i, j if an edge exist, then edge[i][j] = 1. The energy utilization for each nodes would become the weight of the edges, i.e. for two node i, j, w[i][j] = E.U. Let S1 be our source node and let S2 be our destination node. Now, using the above parameters, path from S1 to S2 with minimum energy utilization has been calculated.
After calculating the path, we would number the packets routed from source to destination which actually reached destination (say P). Total number of packets in to the network from source was (say Q). So delivery ratio would be as follows:
Delivery ratio (D) = Packets actually reaching destination/total number of packets.
Here, dynamic network topology for mobile nodes has been created. Connectivity of the network has been shown using the incidence matrix. After calculating the energy utilization (E.U.) for each node, the values are stored in array E.U[][]. Also, number of packets that each node can handle successfully was calculated and stored in an array Packets []. Now a text file “Data.txt” has been created and the following data was written into it using the commands available for file handling. Data written in text file are number of nodes (n), the end points for all the edge connections between various nodes based on incidence matrix, the energy utilization array E.U [] and number of packets stored in array Packets []. Table 2 shows the Number of Nodes and Corresponding Pause Time for EEUR.
Table 2. Number of Nodes and corresponding Pause Time for EEUR
Now the entire data from the text file Data.txt was read and using it we have calculated the shortest path for the dynamic network. Actually, Dijkstra's technique is the basis to calculate the shortest path from source to destination using energy utilization (E.U.) as an optimization parameter for each node. Number of edges gets stored in a variable named e. End points for all edges goes into variables u , v and correspondingly, energy utilized gets stored in a static 2_D array say energyutil [u][v], number of packets gets stored in packets [] array. User specifies the source (say S) which wants to send the data packets and would start the connection and destination (say D) which would receive the data packets. Now we pass source (S), destination (D) and energyutil[][] array to our shortest energy path function named shortest(int S, int D, float energyutil [][]). Table 3. shows the Number of Nodes and Corresponding Pause.
Table 3. Number of Nodes and corresponding Pause Time partition based Speed-Up of Dijkstra's scheme
Now here energyutil [][] will act as the initial weights of the graph and S as the source. The final values of energies get stored in an array energy [].
Initially energy [] = ∞ and energy[s] = 0. Integers i, k, mini are variables whose value changes while program gets executed.
Visited [] is an integer array. Its value is either 0 or 1 depending upon whether the element has been visited or not. For example: Visited [i] =0, if i-th element has not been visited.
Pathindex [] array stores the indices of the mobile nodes in increasing order of their energy utilization value after shortest path algorithm is called.
Pathfinal [] stores the shortest path from source to destination.
Edge [][] carries either value 1 or 0, 1 where there is an edge between the two vertices and 0 if there is no edge between them.
Experimental results show that this approach gives better results in term of energy efficiency as compared to other approaches. Hence, this approach has been used in our algorithm for extracting energy efficient solution.For reliable and energy efficient execution of routing in MANETs the technique proposed by us in this thesis is very effective.
For each i ← 0 to n do
energy [i] ← ∞.
visited [i] ← 0
End loop.
energy [] = 0.
For each k ← 0 to n do
mini ← -1
For each I ← 0 to n
If !(visited [i]) && ((mini == -1) || (d[i] < d[mini])))
do
mini = i.
End if
visited [mini] = 1
End for.
For each I ← 0 to n do
if energyutil [mini][i]
If energy [mini] + energyutil [mini][i] < energy [I]
energy [i] ← energy[mini] + energyutil [mini][i].
End if.
End if.
End for
End for.
The running time complexity for the algorithm varies from O (n*(lg(n)) in best case to O(n2) in average case. Here, the running time complexity is O (n2).
Time taken for the system to compute the shortest path is called pause time. In our case, it is O (n2) where n is the number of nodes and the pause time is directly proportional to square of n i.e. Pause time (Pt) ∝ n. Table 3 shown the pause time for n = 20, 25 and 50.
We can further optimize our code and reduce the pause time to k * n(log(n) by Partition-Based Speed-Up of Dijkstra's Algorithm where k is a small constant (say 0.4521).
Clearly, Partition Based Speed – Up of Dijkstra's Algorithm lead to a factor 34 improvement of time.
Now array energy carries the minimum energy values. Now based on the values energy[], the shortest path for transmitting data packets is calculated and stored in an array path[]. The array path [] will hold the shortest path. dest is an integer variable which carries the destination node value. In order to calculate the shortest path, first of all we sort array energy and store the result in a new array sortenergy. Next, we compare the value of energy with the values of sortenergy and check the index in the former array and store them in the array path []. Now we check elements of new path in consecution to check whether they are connected or not. If any of them is not connected, we will delete that element. This result will get stored in pathnew[] array and we will get our shortest path. Here, we have taken the node which is farthest form the root i.e. the node at position n as the destination node, dest = n. The pseudo code is as follows:
sortenergy []← insertion sort(energy []).
k ← 0.
Temp ← sortenergy [0].
For each i ← 0 to n - 1 do
If !(temp == sortenergy [i] && i>0) do
For each j ← 0 to n - 1 do
If sortenergy [i] == energy[j] do
pathindex [k]← j.
k ← k+1.
End if.
End for
End if
End for
i ← 0 and k ← 1
pathindex[i1] ← pathfinal [i]
a ← pathindex [i]
i ← i+1
b ← pathindex [i]
while pathindex [i]!=pathindex [n]
if edge [a][b]!=1 then
pathindex[i1] ← b
i1 ← i1+1
a ← b
i ← i+1
b ← pathindex [i]
else
i ← i + 1
b ← pathindex[i]
End if else
End while
if edge[pathfinal[i1-1]][pathindex[n-1]]==1 then
pathindex [i1] = path [n-1]
else do
while(edge[pathfinal[i1-1]][pathindex[n-1]]!=1)
i1=i1-1
End while.
End if else.
pathfinal[i1]=pathindex[n-1]
end.
We have used Network Simulator 2.35 (NS 2.35) for creating a network environment to analyse our proposed algorithm.
The Network Simulator 2.35 (NS 2.35) is a discrete event driven simulator developed at UC Berkeley. It is part of the VINT project. The goal of NS 2.35 is to support networking research and education. It is suitable for designing new protocols, comparing different protocols and traffic evaluations. NS 2.35 is developed as a collaborative environment. It is distributed freely and as open source [20]. A large amount of institutes and people in development and research use, maintain and develop NS 2.35. NS 2.35 can run under both UNIX and Windows operating systems. There are many components needed to be installed before running NS 2.35. The user can choose to install it partly or completely. For beginners, it is suggested to make a complete installation which automatically installs all necessary components at once and it requires 320 MB disk space. Installing it partly could save some disk space.
After running the command a scenario will be generated. Example: setdest -v 2 -n 10 -m 10 -M 100 -t 20 -P 1 -p 10 -x 200 -y 400 > scen-exp1
This is done with the help of cbrgen.tcl file executing with ns command
After running the command, a cbr traffic will be generated.
Example: ns cbrgen.tcl -type cbr -nn 9 -seed 1 -mc 10 - rate .25 > cbr-exp1
Paste the tcl file to the ~ns-allinone-2.31/ns-2.31/tcl/ex directory
If the simulation is successful, the desired trace file will be generated.
Animation is generated using a nam trace file. The nam trace file should contain topology information like nodes, links, queues, node connectivity etc. as well as packet trace information.
Graphs for DSR, DSDV, AODV and proposed algorithm (EEUR) have been plotted and compared on the basis of parameters such as:
Packets Sent for Route discovery during packets and Packets Received during Route Discovery
Table 4 shows comparison between the protocols laid on the basis of packets sent during route.
Table 4. Comparison on the basis of Packets Sent during Route Discovery
Here, the proposed protocol is more of a proactive protocol which does not send packets for route discovery and hence the time is saved. So, EEUR is outperforming the other three routing protocols. Figure 9. shows the Packets Sent during Route discovery.
Figure 9. Packets Sent during Route discovery
Following Table 4 shows comparison between the protocols laid on the basis of packets received during route discovery.
Here, the proposed protocol is more of a proactive protocol which does not receive packets for route
discovery and hence time is saved. So, EEUR is outperforming the other three routing protocol. Table 5 and Figure 10 shows the Packets received during Route Discovery.
Figure 10. Packets Received during Route Discovery
Table 5. Comparison on the basis of Packets Received during Route Discovery
Here, the data sent first increases smoothly as the number of nodes increases, but after certain point it increases sharply for EEUR. Table 6 and Figure 11 shows the Data sent.
Figure 11. Data Sent
Table 6. Comparison on the basis of Data Sent
Here, the data received first increases smoothly as the number of nodes increases, but after certain point, it increases sharply for EEUR. Table 7 and Figure 12 show the Data received.
Figure 12. Data received
Table 7. Comparison on the basis of Data Received
Here, the delivery ratio for EEUR first decreases with increase in number of nodes then increases with the increase in number of nodes. Table 8 and Figure 13 shows the Delivery ratio.
Figure 13. Delivery Ratio
Table 8. Comparison on the basis of Delivery Ratio
Here, energy consumed for the proposed algorithm EEUR is increasing fairly with increase in the number of nodes. Table 9 and Figure 14 show the Energy consumed.
Figure 14. Energy Consumed
Table 9. Comparison on the basis of Energy Consumed during Routing
In Figure 15, energy efficiency for the proposed routing algorithm remains constant till number of nodes =25, then energy efficiency increases with increase in the number of nodes. Table 10 shows the comparison based on energy efficiency during routing.
Figure 15. Energy Efficiency
Table 10. Comparison on the basis of Energy Efficiency during Routing
From the above results based on the analysis of the four routing protocols i.e. AODV, DSDV, DSR AND EEUR, it is clear that the value of delivery ratio which is data received/data sent is relatively better for the routing algorithm proposed by us (EEUR) in this thesis as compared to the other three. Since none of the routers failed, the value of router drop is zero for all cases. The value of packet sent for route discovery and packets received after route discovery is zero in the case of EEUR. As we haven't sent any packets for route discovery, data packets are sent directly to the intended destination travelling from node to node and it is left to the routing scheme proposed in this thesis (EEUR) to route the data packets in the most energy efficient way possible. Hence, this further decreases overhead and proves that it an energy efficient routing technique. So we conclude that the routing algorithm proposed by us is more often an energy saving and an efficient technique for routing the data packets in MANET.