Cross Layer Based Virtual Node Layer for Reactive MANET Routing

Cross Layer Based Virtual Node Layer for Reactive MANET Routing

Prof.Rekha Patil, Shveta R. Shah

Department of Computer Science & Engineering

Poojya Doddappa Appa College of Engineering Gulbarga 585103, India

Abstract

The Virtual Node Layer (VNLayer) is a cluster based programming abstraction for a Mobile Ad-Hoc Network that provides sharable virtual nodes emulated by the network nodes. The VNLayer approach simplifies software development for MANET by providing the developers an abstraction of a network divided into fixed geographical regions, each containing a virtual server (virtual nodes) for network services. In this work, we propose an improvement over Cluster based routing with an aid of VNLayer and updating AODV with VNLayer. A cross layer based method is proposed whereby the network layer will fragment or decide the packet sending rate based on estimated bandwidth, information provided by MAC layer. This work deals with enhancing AODV routing protocol using virtual nodes. VNLayer defines fixed geographical regions. In each region, a number of mobile nodes collectively emulate a virtual node, which provides services and relays packets. As a clustering scheme, the VNLayer approach can theoretically improve the efficiency and reliability of MANET protocols. As a general programming abstraction, the VNLayer hides underlying complexities from protocol developers and can be shared by multiple applications. In this work, we use simulation to determine the impact on the performance of the protocol. Simulation results show that the proposed protocol performs better even at higher load. Results justify the theoretical performance improvement claims.

Keyword: AODV, Cross Layer, MANET, Routing, Virtual Nodes, VNLayer

1. Introduction

   A system with no fixed infrastructure in which mobile clients may wander in the plane and assist each other in forwarding messages is called an ad-hoc network. The central challenge of Mobile Ad-Hoc Networks (MANETs) is the absence of fixed infrastructure. In a MANET, participating nodes can enter or leave the network, fail and recover at will and may move rapidly even while participating, making the network topology highly dynamic and the links between mobile nodes very unstable. In addition, link bandwidth and transmission power are scarce. These inherent complexities make scalable implementation of services in a MANET exceedingly difficult.

   MANET is an autonomous network of wireless nodes without any centralized routing and transmission control. Therefore topology controlled protocols like cluster-based routing, backbone routing [10], zone- based routing protocol (ZRP) [8] have gained popularity. In most of these techniques the routing protocol is inherited from AODV and is based on unique IP address allocation to each node. Cluster- based networks represent another useful tool to aid fault-tolerant data aggregation and efficient routing. They do not provide, however, a fully-generalized programming abstraction.

   In this work, we develop a unique solution for MANET by introducing the Virtual Node Layer based reactive routing concept. The Virtual Node Layer (VNLayer) [1] approach is a clean, well-defined programming abstraction designed to alleviate the difficulties in MANET. The VNLayer approach divides a network into regions at fixed geographical locations. Within each region, a subset of physical nodes co- operates to emulate a virtual server (virtual node). Hence, the virtual node in a region can maintain persistent state and be fault tolerant even when

   individual physical nodes might fail or leave a region. Furthermore, the fixed virtual nodes also create a level of hierarchy in a flat MANET, allowing MANET protocols to operate efficiently and reliably.

   A cross layered approach is proposed here [18] [19]. The MAC layer will estimate the bandwidth prior to transmission and would notify the Network layer about the state of the channel.

   As a popular MANET routing protocol, AODVs [7] main strength is its reactive nature. Since route entries are created only when they are needed, there is no need for periodic routing updates. Compared with the connections among physical nodes that are moving, the connections and topology among the virtual nodes are much more stable.

   The VNLayer lies between the MANET link layer and applications built upon it (the application layer). The VNLayer hide complexities such as location checking, leader election and packet buffering from programmers. Because programmers only need to deal with the VNLayer rather than dealing with a set of highly unpredictable physical nodes and the unreliable wireless channel, they can deploy applications on both mobile devices and virtual servers with greater ease and efficiency.

2. Related Work

   VNLayer based routing is also a cluster based routing scheme, in which the leader and non-leader nodes in each region emulate a virtual router. In the existing implementation of the VNLayer [1], local broadcast is extensively used to ensure all physical nodes emulating a virtual node in the same region can hear a message for the virtual node. Because link layer capabilities such as address resolution, RTS/CTS and data packet acknowledgement cant be used on broadcast messages, broadcast is more susceptible to transmission Failures than unicast messages.

   There has been working on the design and analysis of several varieties of VNLayers and their implementations [2]-[6]. These existing VNLayers can be divided into two main categories. Implementations in the first category make optimistic assumptions about the communication behaviour of the physical nodes in the network. Namely, they assume that broadcast messages will always be received by nodes within range. Under these conditions, in [4], Jiang Wu et al. define a VNLayer whose VNs are stationary

   asynchronous objects. In [5], a VNLayer in which the VNs are arbitrary timed asynchronous automata, positioned at known fixed locations. The failure model allows crash failures if and only if the regions immediately surrounding the VN are unpopulated by physical nodes. It also allows some bounded stretch in the clock rate. The second category of VNLayer implementations make more pessimistic assumptions about the communication behaviour of physical nodes, allowing for arbitrary, non-uniform message loss. It does assume, however, rough synchrony. We describe a VNLayer in which the VNs are arbitrary synchronous automata positioned at known fixed locations; fault- tolerant agreement protocols, such as those explored in [6], are used to maintain agreement on VN state in the face of message loss.

   The VNLayer approach is a clustering [9] scheme in which physical nodes are grouped to create a level of hierarchy in the originally flat MANET. There have been many works done on using clustering for MANET routing. The basic idea of clustering is to group mobile nodes into cluster and inter-cluster communications are handled by a set of cluster heads. A large number of clustering algorithms and cluster-based MANET protocols have been designed. Cluster based routing protocols such as COB and CEDAR improved the efficiency of MANET routing by creating hierarchies in a flat clustering is used in many MANET routing protocols. Cluster Overlay Broadcast (COB) [10] is similar to AODV [7], but with route request and response messages (RREQs and RREPs) relayed only by cluster heads. When a cluster head receives a route reply (RREP) message, cluster head marks itself as active for specific session. However, the route created by COB can only be used once. Another cluster based routing rotocol is CEDAR [11]. CEDAR uses a degree based core extraction algorithm to elect cluster heads (core nodes) and to form dominating sets among physical nodes in a MANET. In CEDAR, to reduce the negative impact of flooding, the route request messages are flooded by core nodes by unicast, rather than by local broadcast. CEDAR is a more complex and practical solution than COB. However, both COB and CEDAR uses dynamic clustering, which are subject to re-cluster when cluster membership changes. In addition, in each cluster, there is only one cluster head.

   1. Cross layer

      At present, seen from whether OSI seven layer model or TCP/IP protocols stack, Internet has a layered structure. The layering method is the base to design network protocols and it make designer divide a

      complex question into several different sub-questions of different layers. However, the barriers of operation in different layer affect the optimization in one certain layer. It decreases the efficiency of the software that is designed according to strict layered method. So, when a designed protocol, keeping the separation of layers, relaxing the strict demand of layered and allowing protocols in different layers sharing the status information of networks has been a promising method. It results in cross layer [18] [19].

      Cross Layer violates the OSI layered architecture but keep the impact of design violations as small as possible. There are various cross layer design methods available. A simple and effective design of the cross layer architecture has been chosen to improve the performance of lot of services in ad hoc networks. In our paper, we are using upward information flow. A higher-layer protocol that requires some information from the lower layer(s) at runtime results in the creation of a new interface from the lower layer(s) to the higher layer.

3. Methodology

   The basic VNLayer implementation [1], a MANET is tiled with equal sized square regions. A region can have up to 8 neighbour regions around it. Each region is set to a size such that a message sent by any physical node can reach all the physical nodes in the senders region and its neighbour regions.

   Assuming the mobile nodes have GPS capabilities, each node knows the region it is in. Each VN represents a predetermined geographic area and has broadcast capabilities similar to those of the mobile physical nodes. Each physical node is periodically told its region and frequent updates of real time by the GPS. We assume each physical node is equipped with GPS. However, it is too expensive to do; the majority of physical nodes can infer their locations from the location of a small subset of GPS equipped physical nodes, using a localization algorithm [12]. Node belonging to an area becomes Virtual Node of that area. All physical nodes are assumed to have the same radio range, to know their geographical locations and the region setting. Because a physical node always knows the region it is in, region based clusters can be formed easily.

   Figure 1. MANET Routing using the Basic VNLayer Implementation. The red circles represent leader nodes, and the blue circles represent non-leader nodes.

   Our VN layer is emulated by physical mobile nodes in the network. Each physical node emulating a virtual node is called an emulator. The emulation can be implemented in many ways. A common approach is to have physical nodes in each region elect a leader. In each region, one emulator takes the leader role and the others take non-leader roles. When an emulator becomes a non-leader, it synchronizes with the leader of the region.

   When a physical node arrives in an empty region, it restarts and initializes the virtual node of the region. Since each nonempty region will have a leader, the virtual node in a nonempty region is said to be up. The virtual node is an empty region is said to have failed. In our simulations, every physical node is an emulator and hosts a process.

   Every physical node has a local clock that runs at the rate of real time and is synchronized. Many algorithms depend significantly on timing, and it is reasonable to assume that many mobile nodes have access to reasonably synchronized clocks.

   In a region, when the leader leaves or crashes, a non- leader is elected as the new leader. A virtual node can communicate only with virtual nodes in its neighbour regions. This guarantees the reliability of inter virtual node communications. It also guarantees that in each region, either all emulators receive a message or none do (the atomicity property). In addition, when a node moves into a region and there is already a leader in the region, the node becomes a non-leader and synchronizes with the leader. When a leader node leaves the region, the nodes left in the region still stay

   in the same region. The membership changes in a cluster will not cause other clusters to re-cluster.

   Each Area has a Leader Node. Leader Node is selected as the node with highest Energy and degree of neighbourhood. The cost for a node to send or receive a network-layer packet is modelled as linear. There is a fixed cost associated with channel acquisition and an incremental cost proportional to the size of the packet. Energy [14] can be calculated by

   Energy = m * size + b (1)

   where m= packet cost, size= packet size, b= incremental cost. Number of neighbours can be taken from the routing table. Virtual Nodes are set of nodes where if data is sent to one, it is received by all other. They are like multicasting group. Multicast is the delivery of a message or information to a group of destination nodes simultaneously in a single transmission from the source. A virtual node emulated router can stay functional even when the leader leaves a region.

   In order to shorten the forwarding paths created by AODV, we relaxed the communication rules in the basic implementation. Now, a virtual node is given the option, called Direct Receipt (DR), to accept messages received from virtual nodes from its neighbour regions leader. A virtual node is given the option, called Long Links (LL), to accept messages received from any other virtual node (or leader). A virtual node providing routing service is also called a vrouter.

   Figure 2. Route shortened created by AODV using DR and LL option

   A node participates in the routing if only it satisfies the bandwidth criteria. Bandwidth [16] is defined as the channel capacity through at which rate data packets are sent (maximum data transfer rate of a network). The Idle Time (Ti) is composed of several idle periods during an observation interval t; the node adds all the

   idle periods to compute the total idle time. The idle ratio (R) for each period of time t is calculated as:

   Ratio= idle time (Ti) / observed time (t) (2) The available bandwidth BWavail:

   BWavail= Ratio * total_BW (3)

   where BW is the raw channel bandwidth (11mbps). After the node finishes computing the available bandwidth during a period of time t at the MAC layer, it sends the information of the available bandwidth to the Network layer and starts computing available bandwidth during the next period of time t. Multiple paths are generated from source to destinations. Routing from source to destination follows the path through Virtual regions instead of nodes. Within a Virtual Region, a node can receive message directly from all its neighbours. The nodes must also accumulate the bandwidth information of the intermediate nodes as this is the most crucial parameter in wireless network. Destination selects the best path. The packet delivery ratio is high even at higher data rate or more number of nodes.

   The VNLayer works as a clustering scheme that creates a level of hierarchy in a MANET. There are many advantages of using clustering in wired networks. We are trying to use the VNLayer for finding the less congested nodes or path to send the data efficiently. VNLayer is an on demand or reactive protocol in which nodes find the path only when it has some data to send. This reduces te number of nodes that has to handle a distributed network service. Therefore, VNLayer based services can be more scalable than services that run over a flat MANET. In addition, the virtual nodes are defined at known and fixed locations. This makes the topology of the overlay network formed by the virtual nodes stable. It can also make the communication between remote virtual nodes easier.

   Algorithm

   Establish MANET Environment. Divide into square Regions.

   Select a virtual node leader for each region based on energy and degree of neighbourhood.

   Dynamically select source and destination.

   Generate RREQ, appending additional field of bandwidth.

   Intermediate nodes add its bandwidth and forwards. Destination transmits RREP.

   Select Route

   Initialize load=N; For Data=0: N Begin:

   Store in Network Layer Queue Estimate Bandwidth

   Re configure packet rate based on estimated bandwidth.

   Transmit //in the channel If (Bwthreshold <=BWavail)

   {

   Select route

   }

   End

4. Simulation

   To study the performance of our proposed algorithm simulation was conducted using OMNeT++ [21] which supports complete physical, data link and MAC layer models for simulating wireless ad hoc networks. OMNeT++ is a freely distributed, object-oriented, modular, discrete-event simulator written in C++. It is designed for general-purpose discrete-event simulation, and provides model libraries for communication protocols and network systems. We simulated network of mobile nodes placed randomly in an area of 450×450 square meters, which is divided into 3×3 cells, each cell having a virtual leader, with mobile nodes ranging from 20 to 65.

   A source and a destination is selected randomly. Free space propagation model is assumed as the channel model. Each node is assumed to have a constant transmission range of 100meters. Mobility pattern of the mobile nodes is generated using Random waypoint model [20]. A mobile selects another node in the network and constantly moves towards it at a given velocity. Once it reaches there, it waits for some pause time and selects another node and again starts moving. By observing the performance of the network under mobility we can test the stability of the design in real time scenario. Speed of a mobile node is assigned a value between 0 to 5 meters/sec.

   Initially all the mobiles would be given some initial energy (10000). As the packets re to be transmitted through the nodes, they would loose some energy. A threshold (7000) would be selected. It is assumed from previous research [15] (as the size of each packet is constant), that the radio interference, when powered on, consumes 1.2W while actually receiving a packet and 1.6W while transmitting a packet. As the communication in MANET is normally a cross layered

   approach, upward information flow model is very efficient in designing and modeling the network.

   The performance parameters studied for simulation study are throughput, latency, packet delivery fraction and control overhead by varying the nodes and simulation time. Performance evaluation of proposed protocol is compared with cluster-based network.

   Packet Delivery Ratio

   4.1. Result

   Nodes vs Packet Delivery Ratio

   120

   100

   80

   60

   40

   20

   0

   packet delivery

   ratio(present)

   packet delivery ratio(proposed)

   25 30 35 40 45 50 55 60 65

   Nodes

   Figure 3. Achieved Packet Delivery Ratio by varying Number of Nodes

   Latency

   Figure 3 shows packet delivery ratio achieved by proposed protocol. Improved packet delivery ratio is achieved due to the fact that proposed protocol is to choose stable paths. Increasing number of nodes does not affect the packet delivery ratio as is normally the case with other routing protocols.

   Nodes vs Latency

   2.5

   2

   1.5

   1

   0.5

   latency(present)

   latency(proposed)

   0

   40 45 50 55 60 65

   Nodes

   Figure 4. Latency vs. Number of Nodes

   The proposed system out performs the present system in terms of latency. This behaviour is more noticeable when the number of nodes increases. The nodes v/s the latency shows that the latency never shows an upward trend. Occasionally it would go high

   Throughput

   due to long waiting in the queue in the absence of the bandwidth but it improves as soon as the required bandwidth is available.

   Simulation Time vs Throughput

   12

   10

   8

   6

   4

   2

   0

   throughput(present)

   throughput(proposed)

   100 200 300 400 500 600

   Simulation Time

   Figure 5. Throughput vs. Simulation Time

   Control Overhead

   The throughput performance elaborates that the throughput is maintained at a very high level even when the simulation time offered is about 100%. The cross layered approach enables to transmit at a rate to obtain high throughput.

   Simulation Time vs Control

   Overhead

   40

   30

   20 control

   overhead(present)

   10

   control

   0 overhead(proposed)

   100 200 300 400 500 600

   Simulation Time

   Figure 6. Control Overhead vs. Simulation Time

   The control overhead is always almost constant. This is due to the stable topology. As the virtual node monitors the maintenance of the network, control overhead is optimum.

5. Conclusion and Future Work

   We presented a new technique for simulation study on doing reactive MANET routing over the VNLayer. The VNLayer is tuned to improve the performance, leads to fewer message collisions and message losses by shortened forwarding paths. VNLayer is designed to provide stable routes. The VNLayer approach can simplify software development for MANET. The cross layer design approach improves the performance of the VNLayer network significantly. Algorithms running on VNLayer can worry less about fault-tolerance and more

   about solving the task at hand. The replacement of local broadcast with multicast on data transmission reduces message losses by improving packet delivery fraction. With most of the complexity handled by the VNLayer, the program for the application are both simple and can be shared by multiple applications. Since the VNLayer is application independent, they can be used to improve the performance of any application in the network.

   A discrete-event C++ based simulator OMNET++ can efficiently simulate a VNLayer based network. From the simulation results we can conclude that the throughput and PDR are significantly improved in the proposed work. Control Overhead is reduced many a fold which justifies the use of VNLayer. There is however slight increase in the latency which is attributed by more packet delivery and layer updation. The proposed system works well for both smaller and larger sized networks with many sessions. This proved that the VNLayer approach can improve the efficiency and reliability of MANET protocols.

   The leader election needs to reduce the message overhead and election delay. Knowing it has entered a different region, a leader can send a message back to its original region to ask the non-leaders to start leader election immediately. More optimization schemes can be adopted to improve the performance of the system under mobility.

6. References

1. Jiang Wu, Nancy Griffeth, Calvin Newport, Nancy Lynch, Engineering the Virtual Node Layer for Reactive MANET Routing IEEE International Symposium on Network Computing and Applications, 2011

2. Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina Nolte, and Michael Spindel. The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks. ACM AIGBED Review, 4(3), July 2007.

3. Mike Spindel, Simulation and Evaluation of the Reactive Virtual Node Layer, 2007, Masters Thesis at ASAIL, MIT.

4. Jiang Wu, Nancy Griffeth, Nancy Lynch, Calvin Newport, Ralph Droms, Simulatig Fixed Virtual Nodes for Adapting Wireline Protocols to MANET, the 8th IEEE International Symposium on Network Computing & Applications, Cambridge, MA, July, 2009.

5. S. Dolev, S. Gilbert, L. Lahiani, N. Lynch, and T. Nolte. Timed Virtual Stationary Automata for Mobile Networks. In Allerton Conference 2005: 43rd Annual Allerton Conference on Communication, Control, and

   Computing, page 323, Champaign-Urban, IL, September 2005. Invited paper.

6. S. Dolev, S.Gilbert, N. A. Lynch, E. Schiller, A. A. shvartsman and J. L. Welch. Virtual mobile nodes for mobile ad hoc networks. In R. Guerraoui, editor, 18th International Symposium on Distributed Computing (DISC 2004), Trippenhuis, Amsterdam, the Netherlands, October, 2004, volume 3274 of Lecture Notes in Computer Science. Springer, December 2004. Also Technical Report MIT-LCS-TR-937, MIT CSAIL,Cambridge, MA 02139, 2004.

7. C. E. Perkins, E. M. Royer, S. Das, Ad Hoc On- Demand Distance Vector (AODV) Routing, RFC3561, Network Working Group, IETF.

8. Hongbo Zhou, A survey on routing protocols in MANETs, Department of Computer Sciences, Michigan State University, Technical report MSUCSE- 03-8, 2003.

9. J. Y. Yu and P. chong, A survey of clustering schemes for mobile ad hoc networks, in IEEE Communications Surveys & Tutorials, vol. 7, no. 1, First Qtr. 2005.

10. Vinay Rishiwal, A. Kush, S. Verma, Backbone Nodes based Stable Routing for Mobile Ad Hoc Networks, Ubiquitous Computing and Communication Journal vol. 2 no. 3 pp.1-5.

11. L. Ritchie, H. S. Yang, A. Richa and M. Reisslein,Cluster overlay broadcast (COB): Manet routing with complexity polynomial in source destination distance, Mobile Computing, IEEE Transactions on publication, vol 5, no. 6, June 2006.

12. R. Sivakumar, P. Sinha, and V. Bharghavan, Cedar: a core-extraction distributed ad hoc routing algorithm, IEEE Journal on Selected Areas in Communications, 1999, Vol. 17, pages 1454-1465.

13. Sujatha P. Terdal, V. D. Mytri, Damodaram,. A and Bharthi Salimath, Multipath Load Balancing: An Entropy based Clustering Solution for Mobile Ad Hoc Networks International Journal on Recent Trends in Engineering & Technology, Vol. 05, No. 01, Mar 2011.

14. H. Chen, M. H. T. Martins, P. Huang, H. Cheung So and K. Sezaki, Co operation Node Localization for Mobile Sensor Networks, IEEE, 302-308, 2008.

15. L. M. Feeney, An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks, ACM J. of Mobile Networks and Applications, vol. 6 issue 3, June 2001, pages 239-249.

16. Nishant Gupta, Samir R. Das, Energy-Aware On- Demand Routing for Mobile Ad Hoc Networks, proceeding of the 4th international workshop on distributed computing, mobile and wireless computing, LNCS 2571, pp. 164-173, IWDC2002.

17. M. Pushpavallil Dr. A. M. Natarajan, Quality of Service in Mobile Ad Hoc Networks using Two Bandwidth Estimation Method in Optimized Link State Routing protocol IJCSNS International Journal of Computer Science and Network Security, VOL. 12 No. 1, January 2012.

18. Vineet Srivastava, Mehul Motani,Cross-Layer Design: A survey and the Road Ahead in IEEE Communications Magazine, December 2005.

19. Zhi Ren and Jing Su Wei Guo,A Cross-Layer AODV Routing Protocol, Proceedings of the IEEE International Conference on Mechatronics & Automation Niagara Falls, Canada. July 2005.

20. FanBai, Ahmed Helmy,A survey of mobility models in wireless Ad Hoc Networks, University of Southern California, U. S. A.

21. Andras Varga, OMNeT++, www.omnetpp.org