r
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 590
ISSN 2229-5518
Efficient Energy Aware Location Based Routing
Tarandeep Singh Kang, Maninder Kaur, Dr K V P Singh
Abstract— W ireless Ad Hoc networks have several characteristics different from wired networks which make them completely different networks. Whereas network topology of wireless networks constantly changes, resources like bandwidth and energy are also limited. As power is very important factor for the proper working of Ad Hoc networks, need of the time is to research about efficient utilization of power. In the paper, we improve LAR (Loca- tion-Aided Routing), one of the most famous location based routing methods, which uses GPS technique to get information about the location of mobile node. Our new protocol considers both areas of routing and power. At first, propose a more efficient routing method which finds more stable paths
.Secondly, a power aware method is proposed to have a prior knowledge about the remaining battery backups of all the intermediate nodes so that the nodes with battery backups equal to greater than the minimum threshold power are the part of path between source and destination.
Index Terms— Ad hoc networks, Average power, Expected Zone, Global positioning system, Requested Zone, Threshold power
—————————— ——————————
An ad hoc network is a wireless network also known as Infra- structure less network that establish communications without a fixed network infrastructure or any central administration. It is a collection of nodes which are mobile and also have the capability of working as routers. These nodes can be connect- ed in arbitrary manner dynamically. These nodes when work as routers, discovers and maintains routes to the other nodes in the network.
This is the key feature of future wireless networks to adapt and exist without a fixed infrastructure. Ad Hoc networking is helpful in emergency rescue and search operations, meetings in which information has to be shared quickly and in inhospi- table terrains for acquisition of data.
The task to effectively route the data packets in terms of ener-
gy consumption and bandwidth is very important. For effi- cient routing, many routing protocols have been proposed. Earlier Reactive Routing protocols were developed which used to flood the routing packets in all the directions without considering the location of the destination node. This resulted in increased bandwidth consumption and large end to end delay, whereas in Table driven routing protocols, each node maintains a Routing table that stores a large amount of infor- mation. This required performing a large amount of computa- tions. Control packets overhead increases which in turn con- sumed the limited network bandwidth further resulting in premature loss of battery life. Location Aided Routing Proto- cols were then developed which reduced this bandwidth con- sumption. To find the direction of propagation of packets, these location based protocols uses the Global Positioning Sys- tem (GPS). Therefore bandwidth consumption can be de- creased by finding the direction of propagation. In this paper,
we propose a power aware routing method which helps to
find the stable paths in terms of power by utilizing the concept of global location information. The proposed protocol Efficient Energy Aware Location Based Routing (EEALBR) protocols use location information to minimize the Request Zone to reach the destination node with a path which is alive for the maximum time.
There are a number of location based routing protocols that provide path from source to the destination. Location based routing protocols use the following parameters.
Consider, source node S wants to send the data packet to the destination node D at time T [8]. Assume that the location of D is known to S at time Ti. Also it knows velocity (VD) of D with which D travels. Maximum distance traveled by D in any direction can be calculated as:
r
Figure 2.1 Expected Zone
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 591
ISSN 2229-5518
To find a path from the Source to the destination, the area where the request packets are sent or broadcast is known as a Request Zone. In the traditional routing algorithms, Request Zone is the complete network [8]. For e.g RREQ packets are broadcasted in all the directions to find the optimal path from source to the destination node in the protocols such as AODV and DSR. LAR tries to minimize the request zone by confining it to the smallest rectangular area which contains both sender and the receiver.
Requested Zone
ical location, and energy. From this communication, node which has the largest energy becomes grid header. And head- er node is changed when the rest of its energy equals to 1/2 of second node. Grid headers communicate each other by longer period than the one of general node. The data sent by each grid header includes information of all nodes in its grid. So grid header can get the information of entire nodes.
ILAR (Improved Location Aided Routing) is another location based technique which uses the concept of base line lying in between the source and destination node. Node which is clos- est to this line of sight will be chosen as the next intermediate node. As the transmitting node check the distance of every neighboring node from base line and find the closest neighbor
for further transmission.
S(Xs,Ys)
r
Expected Zone
Mobile Ad hoc Networks is an on demand routing protocol
which decreases the search area given by LAR [9]. In LAR the search area is the smallest rectangle containing both sender as well as receiver. LARDAR reduces this rectangle to triangular zone, which helps in reducing the routing overheads. But the
calculations done to find whether the node lie in the forward-
GPS is a system of satellites [2], ground control stations, and receivers that allows users to determine their position. By capturing and storing that position, GPS receivers “digitize” spatial data as they walk, drive, or otherwise traverse the land. Receivers differ in their ability to receive and process GPS signals and users can have a huge affect on accuracy depending on the methods used to collect and process data.
ing zone or not increases the overhead on the node. This re- sults in decrease in battery of the node.
4. LOCATION BASED POWER AWARE ROUTING LARDAR used the concept of Triangle zone and the angles α and β. The protocol LBPAR uses the concept of triangle zone [5]. But instead of using the angular values in route request packet as in LARDAR it using the concept of slopes of line (Figure 2.3) which can be calculated using the following for-
mula
Location Based Routing uses the following types of routing protocols.
Energy aware location based routing technique use location information by using GPS system and additionally takes a grid method. In this routing protocol each node has GPS in Ad-Hoc network divided by virtual grid [7]. This assumption
means that each node knows the location of itself and where
Requested Zone
m1
r
m2
Expected
they are included in the grid network. To maintaining infor- mation of neighborhoods, nodes in each grid communicate each other by beacon message which includes ID, geograph-
The Base objective of LBPAR is to find an optimal path in terms of bandwidth consumption along with the reduction in
power loss of a node. Here, the route discovery process starts
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 592
ISSN 2229-5518
when source node S initiates a request to send the data packet to destination node D. m1 and m2 are the slopes of the line. D(XT,YT) are the points where the tangents drawn from source to the expected zone touches the expected zone. From the mathematical equations it is clear that m1 and m2 will be the maximum and minimum slopes for any line drawn be- tween the source and any point in between these two tangents. These two slopes [1] can be calculated from the following quadratic equation:
Source node S broadcast a route request packet to find the path. Format of RREQ packet on receiving the RREQ packet node ‘N’ calculates the slope 
using its own location co- ordinates and source location coordinates. If its slope lies be- tween the max and min slope i.e. (m1 ≥ 
≥ m2) then node will again broadcast the packet otherwise node drops the packet. This routing protocol is use to routing packets between mobile nodes in an ad hoc network using the Global Position- ing System. Unlike routing protocols like LAR, ILAR, LAR- DAR this protocol considers various parameters like band- width requirement and battery life of all the intermediate nodes on a path to destination. Increase in the battery life tends to high probability of routing path. Based on evaluation of LBPAR is proved to be a better protocol as it helps in lower-
ing the bandwidth consumption of the network and also helps
to this, there is no idea about what time the path would be alive. This makes the paths found unstable. So there is no guarantee that the sent information packets would reach the destination node or not.
The proposed protocol is an efficient routing scheme which improves the efficiency of location-aided routing (LAR). Pro- posed approach is an extended version of Location Based power Aware Routing (LBPAR). Some parameters used for the calculation of expected zone and requested zone in this Routing protocol are minimum slope, maximum slope, TTL and minimum threshold power for communication. Route request packet (RREQ) can be sent to the neighbor node based on the minimum, maximum slope and if power of the node is greater than or equal to the threshold power.
THRESHOLD POWER
Threshold power is the power set initially which is taken as a reference to select the nodes with power greater than or equal to this reference value. This power is defined initially before the start of the Route Discovery process.
There are three phase in this protocol
in increasing the battery life by decreasing the number and | 1. | Discovery of Route |
complexity of calculations. | 2. | Reply of Route |
3. | Maintenance of Route |
In Location Based Power Aware Routing (LBPAR), if the source node wishes to communicate with the destination node, route discovery is initiated. The path is then set up ac- cordingly. In the route discovery process, the packet is sent to only that next node which lies in the minimum and the maxi- mum slopes. This way the path is formed between the source and destination and then information is sent. Nodes coming in the path are taken to form the path. But no focus is given to the remaining battery backups of the nodes. LBPAR helps in reducing the overheads at each node by decreasing the num- ber of calculations performed at each node, which in turn in- creased the battery life of node. But it can’t provide the guar- antee to delivery of packet on existing path because no con- cern is given to the remaining battery backups of nodes. Due
Source node S (Xs, Ys) wants to communicate with the desti- nation node D (Xd, Yd) in Figure 3.1. The intermediate nodes are 1, 2, 3, 4, 5, 6 and 7. For this communication to be possible first of all Source node S calculates the expected zone. It uses the destination coordinates to calculate the expected zone. After calculating the expected zone, it uses the expected zone to calculate the requested zone. It is shown in the Figure 3.1. After this, RREQ request is initiated by the source node S, this RREQ packet contains the information like TTL, minimum slope, maximum slope, minimum available power, broadcast id, source address, and destination address as shown in the Figure 3.5. The source node collects all this information and then sends the RREQ packet to its neighbors. After receiving
the RREQ packet from the source node, the neighbors first of
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 593
ISSN 2229-5518
all checks the destination address of the RREQ, The packet is consumed if the destination address is the address of any one of the neighbor node and then RREP packet is sent to the source node.
The value of TTL is checked if the destination address is not equal to the neighbor node address, if the value of TTL is less than or equal to zero the node discards the RREQ packet; else it calculates the slope of that node from the source node. If the slope lies between the maximum slope and the minimum slope, then it attaches its own address to the list of visited nodes and then RREQ packet is forwarded to its neighbor nodes. The RREQ packet is discarded by the node if the route can qualify neither minimum slope nor maximum slope.
Every node which receives the RREQ packet follows this pro- cess until the RREQ packet is successfully received by the des- tination node.
Figure 3.4 illustrates an example of Discovery of route process of EEALBR which finds the path between source node S and the destination node D. The path between Source node S and destination node D is S-1-2- 3-4-5-6-7-D.
Algorithm:
If(TTL>=0)
{
if(node id== dest id)
}
Consume packet;
Calculate avg power for current path from AP List;
Send RREP to source with avg communication power of current path;
{
Else if (node id !=dest id)
{ Calculate Mn;
If( )
{
If(node _power>=th_power)
{
Enter the address of node id to the visited node list;
Enter the node available power to AP List; Flood the RREQ;
}}}}
Expected
2 Zone
Else
{
Drop the packet;
}
3
Source
7 Destina-
6 tion
5
In the reply of route phase the packet header destination ad- dress is checked if the destination receives the RREQ packet. If
4 Requested
1 Zone
Figure 3.1 Discovery of Route process of EEALBR
This process is follows by every node which receive the RREQ packet until the RREQ receive the by destination node. Above figure is an example of Discovery of route process of EEALBR which find the path between source need S and destination node D. Source node S to destination node D path is S-1-2-3-4-
5-6-7-D.
the destination address is the address of node then it checks
the minimum and the maximum slopes. RREQ packet is con- sumed if slope lies between these two slopes and then finds the minimum available power from AB List in a packet header and then sent RREP packet to source node with minimum communication power via same path as the path used to re- ceive RREQ packet from the source to the destination. Other- wise RREQ packet is discarded. The reply of route path from the destination node to the source node D-7-6-5-4-3-2-1-s is illustrated by the figure 3.9.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 594
ISSN 2229-5518
3
Source
2 Expected
Zone
path has to be maintained. For example node 4 in Figure 3.10 moves outside to the reach of its neighbor, so the route from the source to the destination breaks. Maintenance of Route pro- cess is used in this case to maintain the route from the source to the destination. In this phase when a node does not receive a RREP packet it will break the path. So in this case, the node sends a route error packet (RERR) to the source node. A new path to the destination node is reconstructed by the Source node after the Source node receives this packet. As Figure 3.10 shows, node 4 moves outside the reach of its neighbors so the path breaks. Then new path is created by using node 3. So the source to destination path after maintenance is S-1-3-5-6-7-d.
6 7 2
5 Destina-
4 tion
Expected Zone
7
1 Requested Zone
Figure 3.2 Reply of Route Phase of EEALBR
For calculating the average power for a particular path, the following steps are involved:
1. First of all, power is extracted for each node from the
Available Power list (AP list) by the destination node.
2. Then the total number of nodes through which the RREQ
Source
3
5
1
Requested
Zone
6
Destination
4
packet travelled to reach the destination node is calculat- ed.
3. Then calculate total power by adding individual powers
of all the nodes.
4. Then, Average power is calculated by using, Avg-Power=Total Power/Total no of nodes
Algorithm for Calculating Average Power:
If (node-id==dest-id)
{
Consume the packet;
Length of path=length (path); For (i=1 to length of path)
{ Power=power+AP[path(i)];
}
There is high mobility of node in the Ad-hoc networks, so the links between various nodes are likely to break. Thus, the routing
Figure 3.3 Maintenance of Route Phase of EEALBR
Figure 4.1 Comparison of EEALBR with LBPAR
Figure 4.1 shows the comparison between EEALBR and
LBPAR protocol in terms of number of paths found between
the source and the Destination. When number of nodes in-
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 595
ISSN 2229-5518
crease then the number of paths found also increases in the EEALBR but in the LBPAR protocol number of paths found remains almost in constant. Also the number of paths found in the EEALBR protocol are more stable than the LBPAR proto- col because in the EEALBR, a threshold value of power is tak- en by virtue of which only those nodes are included in the path between the source and destination which have battery backup greater than or equal to the threshold value. After- wards average power of the whole path is taken. Due to this the source has the idea, approximately what time the path found would be alive. Depending upon the time that the in- formation packet will take to travel from source node to the destination node, the data is sent. If the calculated remaining battery backup of the route is greater than the time which in- formation packet would take to travel from source to destina- tion, the information is sent, and otherwise a new path is searched. But no such approach is used in LBPAR. Thus more routes are found in EEALBR; also stability of the routes found is more in EEALBR than in LBPAR.
Wireless Ad Hoc networks have several characteristics differ- ent from wired networks which make them completely differ- ent networks. Whereas network topology of wireless networks constantly changes, resources like bandwidth and energy are also limited. As power is very important factor for the proper working of Ad Hoc networks, need of the time is to research about efficient utilization of power. In the paper, we improve LAR (Location-Aided Routing), one of the most famous loca- tion based routing methods, which uses GPS technique to get information about the location of mobile node. Our new pro- tocol considers both areas of routing and power. At first, pro- pose a more efficient routing method which finds more stable paths .Secondly, a power aware method is proposed to have a prior knowledge about the remaining battery backups of all the intermediate nodes so that the nodes with battery backups equal to greater than the minimum threshold power are the part of path between source and destination.
The proposed protocol is an efficient routing scheme which improves the efficiency of location-aided routing (LAR). Pro- posed approach is an extended version of Location Based power Aware Routing (LBPAR). Some parameters used for the calculation of expected zone and requested zone in this Routing protocol are minimum slope, maximum slope, TTL and minimum threshold power for communication. Route request packet (RREQ) can be sent to the neighbor node based
on the minimum, maximum slope and if power of the node is greater than or equal to the threshold power.
On analyzing EEALBR, proposed protocol improves the Qual- ity of Service in terms of power and reduces the RREQ flood- ing. The proposed protocol uses power awareness factor to provide more stable and efficient path for communication from source to destination mobile node.
“Efficient Energy Aware Location Based Routing” protocol
helps in dealing with the two major quality factors power and RREQ flooding. But the calculations required in this protocol are more as after finding stable path, average of the path is also calculated which consumes more battery. Also, nodes with limited power are not used, therefore to find more stable paths, nodes with maximum battery backups are found, which increases delay. This protocol can further be improved by re- ducing the number of calculations performed, so that more battery power of the nodes is saved.
[1]. D. D. Perkins and H. D. Hughes, “A survey on quality- of-service support for mobile ad hoc networks,” Wireless Com- munications and Mobile Computing, 2002
[2]. G. Dommety and R. Jain. "Potential Networking Appli- cations of Global Positioning System (GPS)," Technical Report TR-24, Computer Science Department, The Ohio State Universi- ty, April 1999
[3]. Jangsu Lee, Seunghwan Y00, and Sungchun Kim,” Energy aware Routing in Location based Ad-hoc Networks”, Proceed- ings of the 4th International Symposium on Communications, Control and Signal Processing, ISCCSP 2010, Limassol, Cy- prus, 3-5 March 2010
[4]. Mohammad A. Mikki,” Energy Efficient Location Aided Routing Protocol for Wireless MANETs”, (IJCSIS) Internation- al Journal of Computer Science and Information Security Vol.
4, No. 1 & 2, 2009
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 596
ISSN 2229-5518
[5]. P.K.Suri Dr. M. K. Soni, Mrs. Parul Tomar” Location Based
Power Aware Routing”
[6]. Pramita M, Christian P and Shivajit M” Stability Aware Routing: Exploiting Transient Route Availability in MANETs Proceeding HPCC'07 Proceedings of the Third international con- ference on High Performance Computing and Communications Pages 508-520, Springer-Verlag Berlin, Heidelberg ©2007
[7]. Tzay-Farn Shih , Hsu-Chun Yen, “Location-aware routing protocol with dynamic adaptation of request zone for mobile ad hoc networks”, Springer Wireless Netw (2008) 14:321–333,DOI
10.1007/s11276-006-9955-y
[8]. Wenzhu Zhang, Jiandong Li and Xuan Wang, “Cost- Efficient QoS Routing Protocol for Mobile Ad Hoc Networks”, Proceedings of the 19th International Conference on Advanced Information Networking and Applications (AINA’05).
[9]. Y.B. Ko and N. H. Vaidya, "Location-Aided Routing in Mo- bile Ad Hoc-Scale for Ad Hoc Networks," Proceedings of the second ACM international symposium on Mobile ad hoc network- ing & computing, Long Beach, CA, USA, pp. 22-32, October
2001
IJSER © 2013 http://www.ijser.org