Mobile ad hoc Networks

ABSTRACT:

                                 With the recent technological advances in wireless communication and the increasing popularity of portable computing devices, wireless and mobile ad hoc networks are expected to play an increasingly


important role in future civilian and military setting where wireless access to wired backbone is either ineffective or impossible. A mobile ad hoc network (MANET) is a dynamic wireless network that can be formed without any pre-existing infrastructure in which each node can act as a router. The purpose of this report is to understand and discuss the mobile ad hoc networks and its routing protocols table driven protocol and on-demand protocol where the 1st one is a proactive protocol depending on routing tables which are maintained at each node. The other one is a reactive protocol, which find a route to a destination on demand, whenever communication is needed.





Introduction:

                                  A Network is defined as the group of people or systems or organizations who tend to share their information collectively for their business purpose. Similarly a computer network is a set of computers or devices that are connected with each other to carry on data and share information [1].
The networks are classified by method of connection in two main disciplines Wired networks and Wireless networks. In wireless networks there is no need of physical connectivity between nodes, but in wired networks we connect nodes by physical links (cable, fiber optics etc).

 Ad hoc networks are categorized in wireless networks. These are self organizing, self healing and distributed networks. There is no stationary infrastructure or base station for communication. Each node itself acts as a router for forwarding and receiving packets to/ from other nodes. Routing in ad-networks has been a challenging task ever since the wire-less networks came into existence. The major reason for this is the constant change in network topology because of high degree of node mobility. A number of protocols have been developed for accomplish this task. Some of them are DSDV and AODV routing protocols which are explained in the forthcoming pages.

In this we will discuss various types of wireless networks, a brief description of MANET (mobile ad hoc networks). Some advantages, characteristics and applications.




Wireless Networks:

                                             Wireless networks use some sort of radio frequencies in air to transmit and receive data instead of using some physical cables. The most admiring fact in these networks is that it eliminates the need for laying out expensive cables and maintenance costs.

Why Wireless Networks?

1.  Mobile users are provided with access to real-time information even when they are away from their home or office.
2. Network can be extended to places which can not be wired.
3. Wireless networks offer more flexibility and adapt easily to changes in the configuration of the network.
4. Setting up a wireless system is easy and fast and it eliminates the need for pulling out the cables through walls and ceilings.

Why not Wireless Networks?

1. Interference due to weather, other radio frequency devices or obstructions like walls.
2. The total Throughput is affected when multiple connections exist.

Types of Wireless Networks:

       There are many types of wireless networks and can be categorized in various ways:

1. By Network Formation and Architecture
2. By Communication Coverage Area.
3. By Access Technology.
4. By Network Applications.

[19]
                            But we will consider here By Network Formation and Architecture.


By Network Formation and Architecture:
                                                                                              On the basis of network formation and architecture wireless networks can be divided into two broad categorize.

I. Infrastructure-based network.
II. Infrastructure less (ad hoc) network.


I. Infrastructure-based network:
                                                                            A network with preconstructed infrastructure that is made of fixed and wired network nodes and gateways. Typically, network services are delivered via these preconfigured infrastructures. For example, cellular networks are infrastructure-based networks built from PSTN backbone switches, MSCs, base stations, and mobile hosts. Each node has its specific responsibility in the network, and connection establishment follows a strict signaling sequence among the nodes [2].
                                                 WLANs typically also fall into this category.

II. Infrastructure less (ad hoc) network:
                                                                                              A network is formed dynamically through the cooperation of an arbitrary set of independent nodes. There is no prearrangement regarding the specific role each node should assume. Instead, each node makes its decision independently, based on the network situation, without using a preexisting network infrastructure.

For example, two PCs equipped with wireless adapter cards can set up an independent network when ever they are within range of one another. In mobile ad hoc networks, nodes are expected to behave as routers and take part in discovery and maintenance of routes to other nodes.

                                     Here we are concern with ad hoc networks.


Ad Hoc Networks:
                                        In Latin ad hoc means ‘for this purpose only’. An ad hoc network is a small area network, especially one with wireless or temporary plug in connections.

Basically, an ad hoc network is a temporary network connection created for a specific purpose (such as transferring data from one computer to another). If the network is set up for a longer period of time, it is just a plain old local area network (LAN) [3].

Mobile Ad Hoc Networks:
                                                                   Mobile ad hoc network (MANET) also called short lived network can be defined as:
                                                 It is a type of ad hoc network that can change locations and configure itself on the fly. Because MANETS are mobile, they use wireless connections to connect to various networks. This can be a standard Wi-Fi connection, or another medium, such as a cellular or satellite transmission. [4]

It can also be defined as:
                                      A MANET consists of a collection of mobile nodes communicating in a multi-hop way without any fixed infrastructure such as access points or base stations.

                                                        Mobile ad hoc networks

Characteristics and Advantages:
                                                                                     MANETs inherit common characteristics found in wireless networks in general, and add characteristics specific to ad hoc networking:

Wireless: Nodes communicate wirelessly and share the same media (radio, infrared, etc).
Wireless, or single-hop networks, until recently were based on a fixed structure, basically network nodes communicating to fixed infrastructure. Mobile ad-hoc networking offers multi-hop communication, in effect network nodes communicating via other nodes.

Ad-hoc-based: A mobile ad hoc network is a temporary network formed dynamically in an arbitrary manner by a collection of nodes as need arises.

Autonomous and infrastructure less: MANET does not depend on any established Infrastructure or centralized administration. Each node operates in distributed peer-to-peer mode, acts as an independent router, and generates independent data.

Multihop routing: No dedicated routers are necessary; every node acts as a router and forwards each other’s packets to enable information sharing between mobile hosts.

Mobility: Each node is free to move about while communicating with other nodes.
The topology of such an ad hoc network is dynamic in nature due to constant movement of the participating nodes, causing the intercommunication patterns among nodes to change continuously.



Low cost of deployment: As the name suggests, ad hoc networks can be deployed on the fly, thus requiring no expensive infrastructure such as copper wires, data cables, etc. [5]

Applications of Mobile ad hoc Network:

                               There are many interesting applications of mobile ad hoc networks.

Tactical Networks:

•  Military communications and operations control in battlefield environments.

Sensor Networks:

• Collection of embedded sensor devices used to collect real-time data to automate everyday functions.
• Weather monitoring.
• Earth activities.
• Manufacturing Equipment automation.

Emergency Services:

• Search-and rescue operations as well as disaster recovery and medical needs.
• Patient records retrieval at point of contact.
• Loss of infrastructure due to catastrophic disaster.

Commercial Environments:

•  Electronic commerce.
• Make and receive payments from anywhere.
• Access customer records from the field.
• Vehicular access of road conditions, weather, or local news.

Home and Enterprise Networking:

•  Anywhere access for PDA.
•  Personal area networks.

Educational Applications:

•  Virtual classrooms or conference rooms for use during conferences, meetings or lectures.

Entertainment:

•  Multiuser games, robotic pets, and outdoor Internet access.

Location-aware Services:

•  Follow-on services.
• Call forwarding anywhere.
• Transmission of actual workspace to current location.
• Advertise location specific services.
• Location specific travel guides.
• Service availability information.

Salient characteristics in MANETs:
                                                                                           Besides the characteristics discussed above MANNETs have some salient characteristics, which should be kept in mind while using mobile ad hoc networks. These can be classified into

1. MANET Bandwidth Constraints.
2. MANET Energy Constraints.
3. Dynamic topologies.
4. Limited security.

*WEP – wireless encryption protocol.
** Because there is no requirement of physical connection.


Routing :
                        Routing is the act of moving information from a source to a destination in an inter network. During this process, at least one intermediate node within the internetwork is encountered.

It involves two activities: 1st, determining optimal routing paths.
2nd, transferring the information groups (called packets) through an inter network [6].

Routing protocols in Mobile ad hoc Networks:
                                                                                                          MANET has significant different characteristics than other wired or wireless networks. Existing networking protocols can not work in this new environment without considerable modification. In three different ways these protocols can be categorized.

1. Table-driven protocols (Proactive protocols).
2. On-demand routing protocols (Reactive protocols).
3. Hybrid routing protocols (mixed protocol).



                                                   Classification of MANET routing protocols


1. Table driven protocols (Proactive protocols) : 

 These protocols maintain consistent overview of the network. Each node uses routing tables to store the location information of other nodes in the network. This information is used to transfer data among various nodes of the network.

These protocols require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network in order to maintain a consistent network view [7].

Table-driven protocols might not be considered an effective routing solution for mobile ad-hoc network. Nodes in mobile ad-hoc networks operate with low battery power and with limited bandwidth. Presence of high mobility, large routing tables and low scalability result in consumption of bandwidth and battery life of the nodes. Moreover continuous updates could create unnecessary network overhead [8].

Table driven protocols can be further divided (as shown in fig):

1.1 Destination sequenced distance vector (DSDV) routing protocol.
1.2 Wireless Routing Protocol (WRP) routing protocol.
1.3 Cluster head Gateway Switch Routing (CGSR) routing protocol

                           We shall discuss later (DSDV) routing protocol.

2. On-demand routing protocols (Reactive protocol)
                                                                                                                          In contrast to table driven routing protocols, On demand protocols create routes only when desired by source nodes .With on-demand protocols, if a source node requires a route to the destination for which it does not have route information, it initiates a route discovery process which goes from one node to the other until it reaches to the destination or an intermediate node has a route to the destination [21].

It is the responsibility of the route request receiver node to reply back to the source node about the possible route to the destination. The source node uses this route for data transmission to the destination node. This process is completed once a route is found or all possible route permutations are examined. Once a route is discovered and established, it is maintained by route maintenance procedure until either destination becomes inaccessible along every path from source or route is no longer desired [22].

On demand protocol can be further divided (as shown in figure):

2.1 Ad-hoc On-demand Distance Vector routing (AODV)
2.2 Dynamic Source Routing (DSR)
2.3 Temporary Ordered Routing Algorithm (TORA).

We shall discuss later Ad-hoc On-demand Distance Vector routing (AODV).

3. Hybrid Routing Protocols (Proactive + Reactive):

Hybrid routing protocols inherit the characteristics of both on-demand and table-driven routing protocols. Such protocols are designed to minimize the control overhead of both proactive and reactive routing protocols. Consequentially, the delay and overhead of route discovery is avoided since locally (for example, within a zone) the routes are available at all the times. It avoids periodic updates for nodes which are at a far distance by using a reactive approach thereby reducing the control overhead in large networks. ZRP is hybrid protocol, we shall discuss this later.

1.1 Destination Sequenced Distance Vector (DSDV) Routing Protocol
                          In DSDV every node in the network maintains a routing table in which all of the possible destinations within the network and the number of hops to each destination are recorded. It is a proactive routing protocol based upon the distributed Bellman Ford algorithm [9].
Each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, thereby avoiding the formation of routing loops. Routing table updates are periodically transmitted throughout the network in order to maintain table consistency [10].
The tables can be updated in two ways – either incrementally or through a full dump. An incremental update is done when the node doesn’t observe any major changes in the network topology. A full dump is done when network topology changes significantly or when an incremental update requires more than one NPDU (Network Packet Data Unit) [11].
New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination, as well as a new sequence number unique to the broadcast [12].
The route labeled with the most recent sequence number is always used. In the event that two updates have the same sequence number, the route with the smaller metric is used in order to optimize (shorten) the path. Mobiles also keep track of the settling time of routes, or the weighted average time that routes to a destination will fluctuate before the route with the best metric is received [13].
By delaying the broadcast of a routing update by the length of the settling time, mobiles can reduce network traffic and optimize routes by eliminating those broadcasts that would occur if a better route was discovered in the very near future.

Advantages of DSDV

• DSDV protocol guarantees loop free paths.
• Count to infinity problem is reduced in DSDV.
• We can avoid extra traffic with incremental updates instead of full dump updates.
• Path Selection: DSDV maintains only the best path instead of maintaining multiple paths to every destination. With this, the amount of space in routing table is reduced [14].

Limitations of DSDV

• Wastage of bandwidth due to unnecessary advertising of routing information even if there is no change in the network topology [15].
• DSDV doesn’t support Multi path Routing.
• It is difficult to determine a time delay for the advertisement of routes [16].
• It is difficult to maintain the routing table’s advertisement for larger network. Each and every host in the network should maintain a routing table for advertising. But for larger network this would lead to overhead, which consumes more bandwidth.

2.1 Ad hoc on-demand Distance Vector (AODV) Routing Protocol

                     It is an improved version of DSDV algorithm previously described; it inherits the good features of DSDV. It minimizes the number of required broadcasts by creating routes on a demand basis, while DSDV algorithm maintains a complete list of routes. The authors of AODV classify it as a pure on-demand route acquisition system, since nodes that are not on a selected path do not maintain routing acquisition or participate in routing table exchanges.
The AODV routing protocol uses a reactive approach to finding routes and a proactive approach for identifying the most recent path. More specifically, it finds routes using the route discovery process and uses destination sequence numbers to compute fresh routes. The two phases are discussed in more detail.

Rout Discovery:
                                      Now let us see how a rout is discovered with the help of AODV protocol.
Consider the ad hoc network given below in which a process at node A wants to send a packet to node I.




(a) Range of A's broadcast. (b) After B and D have received A's broadcast.
(c) After C, F, and G have received A's broadcast. (d) After E, H, and I have received A's broadcast.

Shaded nodes are new recipients. Arrows show possible reverse routes.

To locate I, A constructs a special ROUT REQUEST packet and broadcasts it. The format of the ROUT REQUEST is shown below.
 


When a route request arrive (B and D):

• Source address and request ID pair is looked up in a table to check duplicity. If duplicate, then discarded otherwise it is entered into table for future operation.
• If route is known then ROUTE REPLY, means that the receiver looks up the destination in its route table if a fresh route to the destination is known, a ROUT REPLY packet is sent back to the source. else next step
• As the receiver does not know a fresh route to the destination, it increments hop count and rebroadcast the ROUTE REQUEST packet. It also extracts data from the packet and stores it as a new entry in its reverse rout table. This information is used to construct the reverse rout table so that the reply can get back to the source later.

Now we will discuss the format of ROUTE REPLY packet.



Node I will now response back to node A.

• The source address, destination address and Hop count are copied from incoming request, but destination sequence number is taken from its counter in memory.
• The Hop count field count is set to 0.
• The Life time field controls how long the route is valid.
• This ROUTE REPLY packet is sent back and Hop count is incremented at each node so the node can see how far from the destination it is. It follows the reverse path to node G to node D and finally at node A [18].

Zone Routing Protocol (ZRP):
                                                                      The Zone Routing Protocol is a hybrid protocol which combines the best features of both reactive and proactive routing protocols [23]. The protocol itself consists of three components:

1. The Intra Zone Routing Protocol (Pro-actively maintain state information for links within a short distance from any given node)
2. The reactive Inter zone Routing Protocol (Use a route discovery protocol for determining routes to far away nodes) [24].
3. Border cast Resolution Protocol (uses unicast routing to deliver packets directly to the border nodes).

The working principle of ZRP is as follows.
                                                                      The whole network is effectively divided into zones, where each zone represents a small part of the network. Every node in the zone maintains a routing table having an entry for every other node in its zone. It also specifies a zone radius which represents the maximum number of hops to reach the farthest node in the zone. Within a zone, the routing is done by a table-driven mechanism using the Intra Zone Routing Protocol. A node can belong to more than one zone. Figure below depicts the concept of routing zone and zone radius. The nodes within a zone exchange periodic route updates. Between zones, the communication occurs using the IERP, in which a node wishing to communicate with a node in a different zone sends a route request packet to all nodes on the border of the zone. For example, in Figure below if node S wishes to communicate with node D, it will send request packets to nodes C, E and finally at D.

                                               Routing zone and zone radius [25]



                        Comparison between Proactive and Reactive Protocols







References:

1. http://www.techiesouls.com/2009/08/10/definition-of-network/
2. Y. Bing Lin and I. Chlamtac, Wireless and Mobile Network Architectures, Wiley, 2000.
3.Mobile computing by Asoke k Talukder and Roopa R Yavagal
4,5. Mobile adhoc netwroking by Stefano Basagni and Marco Conti
6.Routing Protocols in Mobile Ad-hoc Networks by Krishna Gorantala
7.presentation on manet By Donatas Sumyla
8 21. reaserch on mobile ad hoc networking By Humayun Bakht
9 ,11. PERFORMANCE AND SECURITY IN MOBILE AD HOC NETWORKS by Karthik Sadasivam, B.S
10 22. A Review of Current Routing Attacks in Mobile Ad Hoc Networks by Rashid Hafeez Khokhar
12 13. C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector
Routing (DSDV) for Mobile Computers
14. Dr. Uwe Roth. Highly dynamic destination-sequenced distance-vector routing.
15 Danny D. Patel. Energy in ad-hoc networking for the pico radio. Technical report.
16 Guoyou He. Destination-sequenced distance vector (DSDV) protocol. Technical
report, Helsinki University of Technology, Finland.
17.Shree Murthy, J.J. Garcia-Luna-Aveces, "A Routing Protocol for Packet Radio Networks," Proc. ACM International Conference on Mobile Computing and Networking, pp. 86-95, November, 1995
18 computer networks fourth edition by Andrew S. Tanenbaum
19. Wireless Communications(and Networks) by DAYANANDA SAGAR COLLEGE OF ENGINEERING, BANGALORE
23] Haas Z.J, A new routing protocol for the reconfigurable wireless network”. In Proceedings of the 1997 IEEE 6th International Conference on Universal Personal Communications, ICUPC '97, San Diego, CA, October 199- 566.
http://www.ics.uci.edu/~atm/adhoc/paper-collection/haas-routing-protocol-icupc97.ps.gz
24 25. CS653: Mobile Computing a presentation on Mobile Adhoc Networks and Routing in MANETS
(most of the slides borrowed from Prof. Sridhar Iyer
26. Mobile Ad Hoc Networks Security by G.V.S. Raju Peter T. Flawn Professor
University of Texas at San Antonio, Institute for Electrical and Electronics Engineers and Rehan Akbani Ph.D. Student University of Texas at San Antonio