1. INTRODUCTION
Ad-Hoc wireless networks are multi-hop wireless networks consisting of mobile nodes that do not relay on the presence of any fixed network, where all nodes cooperatively maintain network connectivity. This type of network is useful in any situation where temporary network connectivity is needed, such as disaster relief, law enforcement, battlefield, etc. Energy consumption in Ad hoc network imposed some limitations in data transmission range. So every node
should serve as relays for data transmission. An Ad-hoc network provides robust communication even in hostile environment. An Ad-hoc network poses a challenge for developing efficient routing protocols. Efficient routing needs complete network topology information. But in Ad-hoc network, topology changes quite often, requiring large exchange of data among the network nodes.
Ad-hoc routing protocols can be roughly classified as table driven routing and source initiated on –demand routing. Table driven approach uses a routing table which is maintained via periodic updates from all the other nodes in the network irrespective of the fact that the network may not be active in terms of data traffic. The on-demand approach, on the other hand, sends out request for routes to the destination only if the source node has data packets, which are to be sent to the destination. Generally speaking, the table driven approach is more expensive in terms of energy consumption as compared to the on-demand approach because of large routing overhead incurred in the former. So in this paper we thus focus on on-demand routing.
In Ad-Hoc Networks the bandwidth is scarce and battery Energy is limited, it is important to find efficient routing algorithms to create, maintain and repair paths with a minimum overhead [3]. We have proposed a TMR algorithm for link break prediction in Ad-hoc networks to reduce the likelihood of data packets being dropped due to less Energy in the node. Our routing protocol also provides multiple alternate routes to deliver data packets when the primary routes become disconnected due to node mobility and less energy in the node. In our Throughput Maximization Routing the throughput is increased by 70% compared to current Ad-Hoc On demand routing protocol & DSR protocol.
The rest of the paper is organized as follows. Section 2 deals with System Energy Model, in section 3 Throughput Maximization routing, in section 4 Simulation Results and in section 5 Conclusion and future work.
- SYSTEM ENERGY MODEL
An Ad-hoc network can be modeled by a weighted graph G = (N, L), where N is the set of mobile nodes and L is the set of full duplex communication links. The weight associated with a link (u, v) Î L is the power level of its two endpoints u and v and its residual energy. u and v should be within the transmission range of each other. Suppose a source node u transmits a packet to a destination node v and it has a distance d (u,v) from u. Then, the minimum transmission energy required at u is E (u, v).
E (u, v) = k d a(u,v) -------(1)
Where k and a are constants, and a is either 2 or 4. Equ (1) represents an approximation model for power consumption at u. A residual network Gr = (N, Lr) of an Ad-hoc network G = (N, L) is defined as follows. The remaining energy of the battery at node u at time t is E t(u), simply E (u) instead of E t(u). The battery capacity at v initially is C (v) and its remaining energy capacity at time t is E t(v). If a mobile vj is within the transmission range of vi then vi uses the energy E(vi) to transmit a packet , then there is a directed edge in Gr from vi to vj and the weight assigned to the edge is kd a( vi , vj ),where d ( vi , vj ) is distance between vi and vj .(i.e Lr Í L).
Let P be the residual energy path consisting of links < v0,v1>,< v1,v2,>… ,<vl-1..vl>.Each link is provided with the weight ( k d αvi , vi+1 , Evi- k d αvi , vi+1 ). During the path selection ,the node is considered when the node energy is greater than or equal to Eth
SELECT(Gr,
Eth ) find the Throughput
maximization path in Gr from s to t, /* L be the
length of the path between s and t */ /* threshold
energy required in each node is Eth*/ if no such path exists then no routing path for the request exists. exit; else /* find
a routing path for it */ Source(s) ←
u for i ←1
to n-1 do for each link
<u,v> e Lr do if E(u) - k e α u , v ≥ Eth
then Source(s) ← v else send error ® Source(s) end for; end for;Algorithm
3.THROUGHPUT MAXIMIZATION ROUTING
3.1 Route Discovery
When a Source node needs to send a data to a destination but does not have any route information, it searches the route by flooding a ROUTE REQUEST (RREQ) packet [11] across the network. Nodes receiving the RREQ packet update the information for the source node and set up backward pointers to the source node in the route tables. The node, which receives the RREQ, stores the source node’s IP address, current source node sequence number, destination node sequence number [8] and BroadcastID.
The source node sequence number in the RREQ message is the node’s own sequence number. The source node sequence number is used to maintain freshness information about the reverse route to the source. This is to make sure that packet from the destination to the source follow a path, which was set up by the route request packet for this session, as shown in Fig 3.1. The destination sequence number specifies how fresh a route to the destination must be before it can be accepted by the source. A node receiving the RREQ may send a route reply (RREP) if it is either the destination or if it has a route to the destination with corresponding sequence number greater than or equal to that contained in the RREQ. If this is the case, it unicast a RREP back to the source. Otherwise, it rebroadcasts the RREQ.
Each RREQ packet has a unique identifier so that nodes can detect and drop duplicate packets. An intermediate node will respond to the RREQ only if its battery Energy is above a particular threshold Eth. Otherwise the node has to initiate a Energy Error(EERR) packet [11]in a very near future. On receiving a non-duplicate RREQ, the node with battery Energy above threshold records the previous hop and the source node information in its route table (i.e., backward learning). It then broadcasts the packet or sends back a ROUTE REPLY (RREP) packet to the source if it has a route to the destination. The destination node sends a RREP via the selected route when it receives the first RREQ or subsequent RREQs that traversed a better route (in AODV for instance, fresher or shorter route) than the previously replied route.
Nodes keep track of the RREQ’s source IP address and broadcast ID. When they receive a RREQ, if it is already processed, they discard the RREQ and do not forward it. As the RREP propagates back to the source, nodes set up forward pointers to the destination. Once the source node receives the RREP, it may begin to forward data packets to the destination. If the source later receives a RREP containing a greater sequence number or contains the same sequence number with a smaller hop count, it may update its routing information for that destination and begin using the better route. As long as the route remains active, it will continue to be maintained.
 |
Fig 3.1 Route Discovery
3.2. Link Break and Energy Status Prediction
Since most mobile hosts of an ad hoc network today operate using batteries, it is important to route the packet through the path with sufficient battery power. The Energy required by each mobile host can be classified into two categories:
1. Communication Related Energy
2. Non - Communication Related Energy
Communication Related Energy is further divided into two parts:
1. Processing Energy
2. Transceiver Energy
Each Mobile host spends some Energy during the packet transmission and packet reception. In ad hoc networks, wireless nodes have limited battery power. Each host moves in an arbitrary manner and routes are subject to frequent disconnection due to mobility and less Energy. After link Breakage the source node reconstructs the route. During the period of route reconstruction, packets may be dropped. The loss of packets may cause significant throughput degradation, significant packet loss and increased control packet transmission for both real-time and non real-time data. Our Throughput Maximization routing protocol for Ad-Hoc increases the throughput by reducing the packet loss and control packet transmission.
Node energy initially is C. Packet Transmission duration is PTx. Battery Transmission Energy coefficient is K. Energy required for packet transmission between u and v at time t is , Et = k d α u, v.
Energy required for receiving a Packet between u and v is Er.Threshold Energy is Eth. Packet receiving duration is PRx.
E (u) = C (u) - (PTx*K*Et) ------- (1)
Energy in the node u after packet transmission is calculated by (1).
E (u) = C (u)-(Er * PRx + idle Time energy)) ----- (2)
Energy in the Node after receiving a packet is calculated by (2).
Each Node predict the available Energy in the node by the (1) and predict the link breakage time if the Energy in the node is less than the Eth and sends a warning (EERR) to the source node of the packet that the link is soon-to-be-broken during the packet transmission time. The source node can perform a reactive route rebuild after receiving the Energy Error packet. The remaining Energy in each node after packet receiving is calculated by (2).
When a node predicts a link breakage the node will not bring down its route to the destination. Because the rest of the route is still valid. Its upstream nodes of this route have the route entry in their route tables. The upstream nodes are informed of the link status. The node after predicting the link breakage initiates the Energy Error (EERR) message and the source node finds a new route. Already available route could still be used for transmitting packets shown in Fig 3.1.
 |
Fig 3.2 Route Maintenance by Energy Error Packet
During the Route maintenance, a Energy Error packet is send to the source by a node, if its battery Energy falls below a threshold Eth.The intermediate nodes on receiving the Energy Error packet will make use of the information in the Energy Error packet to update their route table .Each node maintains a Link Table. Each entry in the Link Table has the address of the target node (node that initiated the EERR) – source (that is the source of the data packet) node pair, packet reception time and link status flag RTF_PREDICTION. The purpose of having a Link Table is to prevent a node from sending multiple EERR messages for the same source node and replying a route with bad link for the Route Request. Also, there is a time-out for each entry of the Link Table.
On receiving a data packet, the node checks its battery power, if the node’s battery power is in critical state, first it will check if the target node - source node pair is in its Link Table. If it is not, it will add this pair to its Link Table and initiate an EERR messages and unicast it to its active neighbors.
3.2.1 Energy Error prediction
A node receiving the EERR message will not remove the route that has the same destination as in the message. It just sets the route flag to RTF_PREDICTION of this entry in its routing table. This route is still available and valid. The source node will receive the EERR message and initiate a RREQ and broadcast it. If a node receives a RREQ, it will not reply to it when the route flag of the entry is RTF_PREDICTION, if it happens to have a route to that destination, this route will soon break.
It will further broadcast it to the nearby nodes. When the entry with the same destination in the Link Table times out, this node will also set the hop count to infinite to invalidate this route. The node that initiated the prediction EERR message will handle the Route Request message differently. When it receives a Route Request message, it will be dropped to prevent from replying to the Route Request from its routing table, and from broadcasting further the Route Requests, otherwise the source node may get a route with a soon-to-be-broken link.
3.3 Route Maintenance
The mesh structure and alternate paths are established during the route reply phase. Taking advantage of the broadcast nature of wireless communications, a node promiscuously overhears packets that are transmitted by their neighboring nodes. From these packets, a node obtains alternate path information and becomes part of the mesh as follows. When a node that is not part of the route overhears a RREP packet not directed to itself transmit by a neighbor (on the primary route), it records that neighbor as the next hop to the destination in its alternate route table.
 |
Fig 3.3 Alternate route Construction
A node may receive numerous RREPs for the same route if the node is within the radio propagation range of more than one intermediate node of the primary route. In this situation, the node chooses the best route among them and inserts it to the alternate route table. When the RREP packet reaches the source [9], the primary route between the source and the destination is established and ready for use. Nodes that have an entry to the destination in their alternate route table are part of the mesh. The primary route and alternate routes together establish a mesh structure that looks similar to a fish bone shown in Fig 3.3
When a node detects a link break it performs a one-hop data broadcast to its immediate neighbors. The node specifies in the data header that the link is disconnected and thus the packet is a candidate for alternate routing. Upon receiving this packet, neighbor nodes that have an entry for the destination in their alternate route table, unicast the packet to their next hop node. Data packets therefore can be delivered through one or more alternate routes and are not dropped when route breaks occur. To prevent packets from tracing a loop, these mesh nodes forward the data packet only if the packet is not received from their next hop to the destination and is not a duplicate. When a node of the primary route receives the data packet from alternate routes, it operates normally and forwards the packet to its next hop when the packet is not a duplicate. The node that detected the link break also sends a ROUTE ERROR (RERR) packet to the source to initiate a route rediscovery. The reason for reconstructing a new route instead of continuously using the alternate paths is to build a fresh and optimal route that reflects the current network situation and topology.
- SIMULATION RESULTS
4.1 Comparison with AODV and DSR
The throughput of our algorithm is increased by 70% compared to current conventional AODV and DSR. Fig 4.1, Fig 4.2, Fig 4.3 clearly shows that the throughput and packet delivery ratio increases and end to end delay decreases in our Throughput Maximization routing compared to AODV and DSR, because of alternate route and low energy prediction time alert message. Uniform energy is considered in all nodes. The Simulation Parameters are given in the Table 4.1. We have simulated TMR routing protocol using the Network simulator GLOMOSIM
Table 4.1 Fixed Simulation Parameters
|
|
|
|
|
|
|
|
|
|
|
|
Fig 4.1 Throughput for various Mobility
 |
Fig 4.2 Average End-To-End Delay For Various Mobility
Fig 4.3 Packet Delivery Ratio by varying mobility
5. CONCLUSION
We have a proposed a routing algorithm that predict the link breakage due to less node battery Energy and mobility and provide alternate paths by a mesh structure. We have implemented the Throughput maximization routing in both physical layer and network layer. Compared to current Ad-Hoc on demand routing protocol our Throughput in our TMR is increased by 70%. Our Routing protocol can be incorporated into any ad hoc on-demand unicast routing protocol to improve reliable packet delivery in the face of node movements and route breaks. The link break prediction minimizes route break and improve throughput shown in Fig 4.1. The mesh configuration provides multiple alternate routes and is constructed without yielding any extra overhead. Compared to AODV & DSR the end-to-end delay is also less in Throughput Maximization routing (TMR) shown in Fig 4.2. Alternate routes are utilized only when data packets cannot be delivered through the primary route. So the packet delivery ratio is also more in our TMR protocol and shown in Fig 4.3.
We have compared our routing algorithm with AODV and DSR and performance is measured. Simulation results (Fig 4.1 , Fig 4.2 and Fig 4.3) indicated that our routing algorithm provides robustness to mobility and enhances protocol performance. We also learned that however, our algorithm does not perform well under heavy traffic networks. We are currently investigating ways to make our protocol robust to traffic load. Additionally, we plan to further evaluate our scheme by using more detailed and realistic channel models with fading and obstacles in the simulation. We believe the advantage of providing backup routes will be significant in those environments.
REFERENCES
[1] David A. Maltz, Josh Broch, Jorjeta Jetcheva and David B. Johnson, August 1999, “ The effect of On-Demand Behavior in Routing Protocols for Multihop Wireless Ad hoc Networks”, IEEE Journal on Selected Areas in Communications Special Issue on Mobile and Wireless Networks, pages 1439-1453.
[2] Elizabeth M. Royer and C.K. Toh, April 2001, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks”, IEEE Personal Communications Magazine, pages 46-55.
[3] He Dajing, Jiang shengming and Rao Jianqiang, April 2001, “ A Link Availability Prediction model for wireless Ad hoc Networks”, Proceedings of the International Workshop on Wireless Networks and Mobile Computing, D7-D11, Taipei, Taiwan.
[4] Garcia-Luna-Aceves J.J.and. Madruga E.L August 1999, “The Core-Assisted Mesh Protocol”, IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1380-1394.
[5] Lee S.J., W. Su, J. Hsu, M. Gerla, and R. Bagrodia, March 2000,”A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols”, Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Tel Aviv, Israel, March 2000, pp. 565-574.
[6] Mahesh K. Marina Samir R. Das,2002, “On-demand Multipath Distance Vector Routing in Ad Hoc Networks”, IEEE 2002.
[7]. Raju J and Garcia-Luna-Aceves J.J, October 1999,“A New Approach to On-demand Loop-Free Multipath Routing”, Proceedings of the Annual IEEE International Conference on Computer Communications and Networks (ICCCN), Boston, MA, October 1999, pp. 522-527.
[8] Perkins C.E and Royer E.M, February 1999, “Ad-Hoc On Demand Distance Vector Routing”, Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), New Orleans, LA, pp. 90-100.
[9] Perkins, Royer, Das, 2 March 2001,”Ad-hoc on demand distance vector routing“, draft-ietf-manet-aodv-12.txt, March 2001, http://www./ietf.org.
[10]Rapport, Wireless Communication: Principles and practice, Prentice Hall, pp 69-122, pp 139-196,1996
[11] Sung-Ju Lee and Mario Gerla, 2002 “AODV-BR: Backup Routing in Ad hoc Networks”, IEEE 2002, Journal on Selected Areas in Communications.
Technical College - Bourgas,
All rights reserved,
© March, 2000