An infrastructure-based network, such as a cellular network, uses fixed BS that are responsible for coordinating communications between mobile nodes. An ad hoc network consists of mobile nodes that communicate with each other using wireless medium without any fixed infrastructure. “Ad hoc” is a Latin word that means “for this purpose only”. An ad hoc network is a special network that is set up for a particular application.
A mobile ad hoc network (MANET) is a self-configuring network of mobile routers connected by wireless links that form an arbitrary topology. The routers are free to move randomly and organize themselves arbitrarily. The network’s wireless topology may change rapidly and unpredictably.
Why Use MANET?
- Ease of deployment,
- Speed of deployment,
- Flexible,
- Decreased dependence on infrastructure,
- Cost effective,
- Interoperability.
Characteristics:
- Decentralized,
- Self-organised,
- Self-deployed,
- Dynamic network topology,
- Bandwidth-constrained, variable capacity, asymmetric links.
Trade-offs:
- Limited bandwidth,
- Multihop router needed,
- Energy consumption problem,
- Security issues,
Examples of applications:
- Synchronizing contents between devices,
- Distributing contents over a network,
- Personal area networking, e.g. synchronization between cell phone, laptop and earphone,
- Emergency operations, e.g., search and rescue, policing and fire fighting, disaster recovery,
- Military use,
- Civilian environments, e.g., taxi cab network, meeting rooms, stadiums, boats, aircraft,
- Unrestricted local communications.
Initial Architecture
Initially, a MANET is usually small, relatively static, embedded ad hoc network., e.g. Bluetooth-type networks. Later on, it evolves to small- to medium-sized MANETs, e.g. 802.11-type network. As technology continues to evolve, multiple technologies can be used simultaneously. A standard-based approach at the network layer is needed.
MANET Routing Protocols
Routing protocols for MANET can divided into two categories: table-driven and source-initiated on-demand Routing Protocols
Table-driven routing protocols are also known as proactive protocols. The routing protocol requires each node to maintain one or more tables to store routing info. It relies on an underlying routing table update mechanism that involves constant propagation of routing information. Packets can be forwarded immediately since the routes are always available. The drawback of this approach is it causes a substantial signalling traffic and power consumption problem.
Routing protocols in this category are:
- Destination-sequenced distance vector routing (DSDV),
- Clusterhead gateway switch routing (CGSR),
- Wireless routing protocol (WRP).
Source-initiated on-demand routing are reactive protocols. The protocol initiates path discovery only when a node has packets to send. The packets at a source node must wait until a route is discovered. It does not require periodic route updates, and therefore, incurs lower overhead compare to proactive protocols.
Routing protocols in this category are:
- Ad hoc on-demand distance vector routing (AODV),
- Dynamic source routing (DSR),
- Temporally-ordered routing algorithm (TORA),
- Associativity-based routing (ABD),
- Signal stability routing (SSR).
DSDV
Each node maintains a routing table that lists all available destinations and the number of hops to each destination. The routing table is used by the nodes to transmit packets to one another. Each route table entry is tagged with a sequence number, which is originated by the destination station. In order to maintain a consistent routing table in a dynamically varying topology, each station periodically transmits updates. If there is significant new information available, the update is transmitted immediately.
Because we cannot assume that the mobile nodes maintain any sort of time synchronization, we cannot make any assumption about the phase relationship of the update periods between the mobile hosts. Routing information is advertised by broadcasting or multicasting the packets periodically as topological changes are detected. These packets indicate which nodes are accessible from each node and the number of hops to reach them. Data is also kept about the length of time between the arrival of the first and the arrival of the best route for each particular destination.
DSDV requires each mobile station to advertise its routing table to each of its current neighbors. The advertisement must be made often enough (say once every few seconds) to ensure that all nodes can almost always locate every other node in the network. Each node agrees to relay data packets to other nodes upon request so that a node may exchange data with any other node in the group even if the destination is not within range for direct communication.
The data broadcast by each station contains the following information for each new route:
- destination address,
- next hop,
- distance,
- sequence number.
CGSR
CGSR is a clustered multihop routing protocol. Mobile nodes are partitioned into clusters and a clusterhead is elected using a distributed algorithm. All nodes in the communication range of the clusterhead belong to its cluster.
A node that is in the communication range of two or more clusterheads is called a gateway node. Each node maintains 2 tables:
- A cluster member table, containing the cluster head for each destination node;
- A DV-routing table, containing the next hop to the destination.
The cluster member table is stored and broadcast periodically using DSDV algorithm. The node updates the entries in its cluster member table upon receiving a new one from its neighbour.
A clusterhead change occurs only when:
- two clusterheads come into one cluster, or
- one of the nodes moves out of the range of all the clusterheads.
If a node has to route a packet, it finds the nearest clusterhead along the route to the destination according to the cluster member table and the routing table. It consults its routing table to find the next hop. The source transmits the packet to its clusterhead. The clusterhead sends the packet to the gateway node. The gateway sends the packet to the next clusterhead. The process goes on until the destination clusterhead is reached. The destination clusterhead transmits the packet to the destination node.
DSR
This iss an on-demand routing protocol that is based on the concept of source routing. It initiates route discovery process by sending a route request message containing:
- destination and source addresses,
- resource ID,
- history of nodes it has visited.
Suppose node A is trying to discover a route to node E. Node A broadcasts a route request (RREQ) that is received by all nodes within transmission range. Each RREQ contains a record listing the address of each intermediate node to which the request is forwarded.
When a node received RREQ, it checks to see if it's the target. If it's not, it checks:
- If it has recently received a RREQ with the same ID and target from A,
- If its own address is in the route record.
When node E receives the RREQ and recognises itself as the target, it returns a route reply (RREP) to Node A. The RREP contains the accumulated route record from RREQ. When E returns the RREP, it examines if its own route cache contains a route for A.
- If not, E reverses the hop sequence to cache the route to A.
- It uses this information to deliver the RREP to A.
AODV
AODV provides a dynamic, self-starting, multi-hop routing between mobile nodes to establish and maintain an ad hoc network. Routes are only maintained for destinations in active communication. It provides a way for mobile nodes to respond to link breaks and changes in network topology in a timely manner. The algorithm also establishes a route between a source and a destination that is loop-free. It is designed to scale for thousands of mobile nodes and can handle low, moderate, and relatively high mobility rates with a variety of traffic levels.
If node 1 (originator) wants to deliver a data packet to node 2 (destination), and it does not know the route to node 2, it initiates a route discovery by broadcasting a RREQ. Node 1 may also initiate a route discovery if its routing table indicates that the route to node 2 has been marked as invalid. Node 1 increments its originator sequence number and inserts it in the RREQ. The Hop Count field is set to zero. Before node 1 broadcasts the RREQ message, it buffers the RREQ ID and Originator IP Address for a period of PATH_DISCOVERY_TIME.
When node 1 receives a RREQ from a neighbor, it compares the RREQ ID and Originator IP Address value in the message to the one in its buffer. If it recognizes it as the RREQ it has generated, it does not process nor forward the RREQ.
When node 2 receives the RREQ, it returns a RREP to node 1. A reverse route is set up to forward a RREP back to the originator.
Alternatively, if an intermediate node, let’s say node 7, has recently communicated with node 2 and it knows how to reach node 2, it returns RREP to node 1 and does not forward the RREQ. Node 7 can only return a RREP if it has a fresh-enough route, i.e. a valid route entry for the destination whose sequence number is at least equal to that contained in the RREQ.
Intermediate nodes (e.g., nodes 3 and 4) that receive the RREP caches a route back to the originator of the request. Node 1 stores the route to node 2 in its routing table. A route to a destination is said to be an active route if the route to the destination is marked as valid. Only active routes can be used to forward data packets.
If node 1 does not receive a RREP after NET_TRAVERSAL_TIME milliseconds, it may broadcast another RREQ.
- The maximum number of retries is determined by RREQ_RETRIES and the number of RREQs generated by node 1 should not exceed RREQ_RATELIMIT per second.
- The value of RREQ ID is increased for each RREQ generated.
- If after RREQ_RETRIES, node 1 still does not receive a RREP, data packets destined for node 2 are dropped and a Destination Unreachable message is delivered to the application.
- In order to reduce congestion, node 1 must execute a binary exponential backoff before attempting to broadcast another RREQ for node 2.
When a node receives a RREQ, it checks whether it has received a RREQ with the same Originator IP address and RREQ ID within the last PATH_DISCOVERY_TIME.
- If it has, the RREQ is discarded.
- Otherwise, it searches for a reverse route to the originator.
- If an entry for the originator does not exist in its routing table, one is created.
- Otherwise, the entry is updated using the Originator Sequence Number from the RREQ. The reverse route is needed if the node receives a RREP back to the node.
If the node does not know the route to the destination (therefore, it cannot generate a RREP) and the TTL value is greater than one, it updates the RREQ by increasing the Hop Count by one and decreasing the TTL by one. Then it broadcasts the RREQ on all of its configured interfaces.
Source
No comments:
Post a Comment