14-02-2009, 11:51 PM
AD HOC NETWORK
1. Introduction:-
Computer network is interconnected collection of autonomous computers. Roughly speaking, networks can be divided into LANs, MANs, WANs and internetworks, each with their own characteristics, technologies, speeds, and functions. Cellular network is nothing but wireless WAN. It has predetermined infrastructure with static backbone.
2. Need Of Ad Hoc Networks:
Some times the situation occurs where a fixed communication infrastructure, wired or wireless, does not exist or has been destroyed. Then it is very difficult to provide the necessary infrastructure but it is a challenging task to enable fast and reliable communication within such a network. Ad hoc networks are required in these situations. Ad hoc networks are the network architecture that can be rapidly deployed, without preexistence of any fixed infrastructure.
3. What Is Ad Hoc Network?
An ad hoc network is a (possibly mobile) collection of communications devices (nodes) that wish to communicate, but have no fixed infrastructure available, and have no pre-determined organization of available links. Individual nodes are responsible for dynamically discovering which other nodes they can directly communicate with. A key assumption is that not all nodes can directly communicate with each other, so nodes are required to relay packets on behalf of other nodes in order to deliver data across the network. Thus the nodes in ad hoc form multi-hop radio network.
The nodes communicate with each other over wireless links. Each node in a wireless ad hoc network functions as both a host and a router, and the control of the network is distributed among the nodes. The network topology is in general dynamic, because the connectivity among the nodes may vary with time due to node departures, new node arrivals, and the possibility of having mobile nodes. There are no explicit links in an ad hoc network, and all communication is by broadcast.
Fig2. Ad hoc network representation.
Fig.:- Ad hoc network representation
4. Features of Ad Hoc Networks:
q It is wireless multihop network.
q Rapid changes in connectivity and page link characteristics are introduced due to node mobility and power control practices.
q Ad hoc networks can be built around any wireless technology, including infrared and radio frequency (RF).
q It supports large network radius, large number of network nodes and large range of nodal velocities (from stationary to highly mobile).
q Rapidly deployable network architecture without pre-existence of any fixed infrastructure.
q Highly mobile nodes and dynamically changing topology.
5. Types of Ad Hoc Networks:
There are two major types of wireless ad hoc networks
i. Mobile ad hoc networks
ii. Smart sensor networks.
Mobile ad hoc networks (MANETs):
A MANET is an autonomous collection of mobile users that communicate over relatively bandwidth constrained wireless links. Since the nodes are mobile, the network topology may change rapidly and unpredictably over time. The network is decentralized, where all network activity including discovering the topology and delivering messages must be executed by the nodes themselves, i.e., routing functionality will be incorporated into mobile nodes. The network scenarios such as establishing survivable, efficient, dynamic communication for emergency/rescue operations, disaster relief efforts, and military networks cannot rely on centralized and organized connectivity, and can be conceived as applications of MANETs.
Factors such as variable wireless page link quality, propagation path loss, fading, multi-user interference, power expended, and topological changes affect performance and dependability of the network
Requirements of MANET:
§ The design of network protocols regardless of the application. (A complex issue.)
§ Efficient distributed algorithms to determine network organization, page link scheduling, and routing.
§ Determinination of viable routing paths and delivering messages in a decentralized environment where network topology fluctuates. (Which is not a well-defined problem.)
§ The network should be able to adaptively alter the routing paths to alleviate any of the above-mentioned effects.
§ Preservation of security, latency, reliability, intentional jamming, and recovery from failure.
Smart sensor networks:
A smart sensor network consists of a number of sensors spread across a geographical area. Each sensor has wireless communication capability and sufficient intelligence for signal processing and networking of the data. Some examples of smart sensor networks are the following:
· Military sensor networks to detect enemy movements, the presence of hazardous material (such as poison gases or radiation), explosions, etc.
· Environmental sensor networks (such as in plains or deserts or on mountains or ocean surfaces) to detect and monitor environmental changes.
· Wireless surveillance sensor networks for providing security in a shopping mall, parking garage, or other facility.
Basic goals of a smart sensor network are to determine the value of some
parameter at a given location, determine the occurrence of events of interest and estimate parameters of the detected event(s), detect an object and track the object.
Sensor network requirements:
§ Large number of (mostly stationary) sensors.
§ Low energy use.
§ Network self-organization.
§ Collaborative signal processing.
§ Querying ability.
6. Architecture of ad hoc network:-
A set of layers and protocols is called network architecture.
Layered Approach:
To reduce design complexity networks are organized as series of levels called Layers. Ad hoc network is multi-layer containing physical layer, multiple access control layer (MAC), network layer, transport layer and application layer. Flat-routed and two-tired design approaches in ad hoc are discussed in sub-point Connectivity in ad hoc network.
Protocol:
Layer Ëœnâ„¢ on one machine carries on a conversation with layer Ëœnâ„¢ on another machine. The rules and conventions used in this conversation are collectively known as layer Ëœnâ„¢ protocol. TCP/IP protocol is making universal service possible. It is used in Internetworks, Novell NetWare, APRANET etc. networks. But there are some problems using TCP/IP for ad hoc as TCP performs less predictable on wireless networks than the wired.
Two critical problems over wireless multi-hop are:
§ Conflicts between data packets and ACKs which causes TCP performance to degrade for window sizes greater than 1 packet.
§ The interaction between MAC and TCP layer backoff timers which cause severe unfairness and capture conditions.
Thus special protocols used for wireless, multi-hop ad hoc networks are Distance vector routing protocol (DVRP), Line state protocol, Dynamic source routing protocol, Destination sequence distance vector routing protocol (DSDVRP), Multicast routing protocol, zone routing protocol (ZRP) and Novel distributed routing protocol. These are discussed in protocol section with detail working of Novel distributed routing protocol.
Connectivity In Ad Hoc Network:
Basically, there are two approaches in providing ad-hoc network connectivity:
i. Flat-routed network architectures.
ii. Hierarchical network architectures.
An example of a flat-routed network is shown in Figure 3 and that of a two-tiered hierarchical network in Figure 4.
Fig.3 A flat-routed ad hoc network
In flat-routed networks, all the nodes are equal and the packet routing is done based on peer-to-peer connections, restricted only by the propagation conditions.
Fig.4 A two tiered ad hoc network
In hierarchical networks, there are at least two tiers; on the lower0 tier, nodes in geographical proximity create peer-to-peer networks. In each one of these lower-tier networks, at least one node is designated to serve as a "gateway to the higher tier. These gateway nodes create the higher-tier network, which usually requires more powerful transmitters/receivers. Although routing between nodes that belong to the same lower-tier network is based on peer-to-peer routing, routing between nodes that belong to different lower-tier networks is through the gateway nodes.
We note that the flat-routed networks are more suitable for the highly versatile communication environment as the RWN-s. The reason is that the maintenance of the hierarchies (and the associated cluster heads) is too costly in network.
Protocols:
Classification:
Protocols are broadly classified as
a. Proactive protocols.
b. Reactive protocols.
Proactive protocols:
These attempts to continuously evaluate the routes within the network, so that when a packet needs to be forwarded, the route is already known and can be immediately used. The advantage of the proactive schemes is that, once a route is requested, there is little delay until route is determined. Pure proactive schemes are not appropriate for the ad-hoc (e.g.RWN) environment, as they continuously use large portion of the network capacity to keep the routing information current. Since in an ad-hoc nodes move quite fast, and as the changes may be more frequent than the routing requests, most of this routing information is never used. This results in an excessive waste of the network capacity.
Reactive protocols:
These on the other hand, invoke the route determination procedures on demand only. Thus, when a route is needed, some sort of global search procedure is employed.
In reactive protocols, because route information may not be available at the time a routing request is received; the delay to determine a route can be quite significant. Because of this long delay, pure reactive routing protocols may not be applicable to real-time communication.
What is needed is a protocol that, on one hand, initiates the route determination procedure on demand, but with limited cost of the global search. The wired Internet uses routing protocols based on topological broadcast, such as the SPF. These protocols are not suitable for the RWN due to the relatively large bandwidth required for update messages.
7. Protocols used in ad-hoc networks:
The following routing protocols are generally used in ad hoc networks.
§ Distance vector RP.
§ Link state RP.
§ Dynamic source RP.
§ Novel distributed RP
§ Destination sequence distance vector RP.
§ Zone routing.
§ Multicast routing.
Distance-vector routing protocol:
In distance vector routing, each router maintains a table giving the distance from itself to all possible destinations. Each router periodically broadcasts this information to each of its neighbor routers, and uses the values received from its neighbors to compute updated values for its own table. By comparing the distances received for each destination from each of its neighbors, a router can determine which of its neighbors is the correct next hop on the shortest path toward each destination. The salient advantage of DVRP is the considerable reduction in the probability of loops in the calculated routes. The main disadvantage of DVRP for the RWN is in the fact that routing nodes constantly maintain full routing information in each network node, which was obtained at relatively high cost in wireless resources. Examples of distance vector routing protocols include the routing protocol used in the DARPA Packet Radio Network; the original routing protocol for the ARPANET; RIP (used in parts of the Internet, in Novellâ„¢s IPX, and in Xeroxâ„¢s XNS); and RTMP (used in AppleTalk).
Link state routing protocol:
In this protocol each router maintains a complete picture of the topology of the entire network. Each router monitors the cost of the page link to each of its neighbor routers, and periodically broadcasts an update of this information to all other routers in the network. Given this information of the cost of each page link in the network, each router computes the shortest path to each possible destination. Examples of page link state routing protocols include the new routing protocol that replaced the original protocol for the ARPANET, IS-IS (adopted by ISO as a standard routing protocol), and OSPF (used in parts of the Internet).
Dynamic source routing protocol:
It is a protocol for routing packets between wireless mobile hosts in an ad hoc network. Unlike routing protocols using distance vector or page link state algorithms, this protocol uses dynamic source routing which adapts quickly to routing changes when host movement is frequent, yet requires little or no overhead during periods in which hosts move less frequently. Here to send a packet to another host, the sender constructs a source route in the packetâ„¢s header, giving the address of each host in the network through which the packet should be forwarded in order to reach the destination host. The sender then transmits the packet over its wireless network interface to the first hop identified in the source route. When a host receives a packet, if this host is not the final destination of the packet, it simply transmits the packet to the next hop identified in the source route in the packetâ„¢s header. Once the packet reaches its final destination, the packet is delivered to the network layer software on that host. Dynamic source routing protocol utilizes flooding to discover a route to a destination. Optimization techniques, such as route caching reduce the route determination or maintenance overhead. In a highly dynamic environment, such as the RWN is, this type of protocols lead to a large delay and the techniques to reduce overhead may not perform well.
Multicast routing protocol:
As ad-hoc networks are multi-hop wireless networks they use Multicast Routing Protocol. A multicast protocol builds upon a cluster based wireless network infrastructure. The multicast protocol is inspired by the Core Based Tree (CBT) scheme. Each multicast group has a unique multicast identifier (Mid). Each multicast address identifies a host group, the group of hosts that should receive a packet sent to that address. Each multicast group is initialized and maintained by a multicast server (MS) which becomes the core of the CBT for this multicast group. Initially the multicast server broadcasts the Mid and its own node id (MSid) using a flooding algorithm. When a node receives this information, it records the pair Mid and MSid into its multicast database which can be used to join or quit this multicast group. Alternatively to avoid flooding, the multicast server registers themed on a directory server. Any node which wants to join a particular multicast group can query the directory server. Future research directions include:
(1) The extension of the Internet (or ATM) multicast tree solutions to the wireless segments and
(2) QoS multicasting
DSDV protocol:
Destination sequence distance vector protocol is enhancement to the distance-vector Bellman-Ford routing protocol made to support ad hoc MHs. Because each MH periodically advertises its view of network topology, this scheme is inefficient. Similar to cluster based routing this scheme uses broadcast routing and connectionless and packet forwarding approach.
Zone routing protocol:
In this protocol routing in the RWN is based on the notion of a routing zone, which is defined for each node and includes the nodes whose distance (e.g., in hops) is at most some predefined number. This distance is referred to here as the zone radius. Each node is required to know the topology of the network within its routing zone only and nodes are updated about topological changes only within their routing zone. Thus, even though a network can be quite large, the updates are only locally propagated. Since for radius greater than 1 the routing zones heavily overlap, the routing tends to be extremely robust. The routes within the network are specified as a sequence of nodes separated by approximately the zone radius.
:
Fig.5 An example of zone routing
8. Novel Distributed Routing Protocol:-
This is new, simple and bandwidth efficient distributed routing protocol for ad hoc networks. Unlike conventional distributed routing algorithms this protocol does not attempt to consistently maintain routing information in every node. In ad hoc networks mobile hosts are acting as routers and routes are made inconsistent by their movement. A new associativity based routing scheme is employed here. Route is selected based on nodes having associativity states that imply period of stability. Thus routes selected are long lived and no need to restart frequently, resulting in higher attainable throughput. Association property also allows integration of ad hoc routing into BS-oriented wireless LAN (WLAN) providing fault tolerance in times of base stations (BSs) failures. This protocol is free from loops, deadlocks and packet duplicates and has scalable memory requirements.
Associativity-Based Routing (ABR):-
Routing scheme is compromise between broadcast and point-to-point routing. Routes for sources that actually desire routes are only maintained. RRC (Route Re-Construction) based on alternate route information existing in intermediate nodes (INs) is not employed, hence avoiding stale routes. In addition, route decision is performed at the destination node and only best-selected route will be valid while all other possible routes are made passive, thus avoid packet duplication
Principles of ABR:
The essence of ABR lies on the fact that MHâ„¢s (mobile host) association with its neighbour changes as it is migrating and its transiting period can be identified by associativity ticks. The migration is such that after this unstable period, there exists period of stability, where MH will spend some dormant time within cell before it starts to move again. Atheshold, as shown in figure, defines the threshold where association transitions take place. Associativity ticks are updated by the MHâ„¢s DLL protocol, which periodically broadcasts beacons identifying itself and constantly updates its associativity ticks in accordance MHs sighted in its neighborhood. In scenario where an ad hoc WLAN has wireless cell size 10m with MHâ„¢s minimum migration speed 2 m/s and beacon transmission interval of a second, the maximum associativity ticks of migrating MH with its neighbour is 5. Likewise neighboring MHs will also record associativity ticks of no more than 5.value of Athreshold and greater implies association stability.
Properties of ABR:
A MH is said to exhibit high state of mobility when it has low associativity tick with its neighbors. Also when high associativity ticks are observed, then MH is in stability state and this is ideal point to select MH to perform ad-hoc routing. Associativity ticks are reset when neighbors or the MH itself moves out of proximity, not when communication session is completed.
ABR route selection:
Among the all-possible routes from source to destination node best route is computed based on degree of association stability, route relaying load and shorter paths.
9. Applications :-
Ad hoc networks are required in situations where a fixed communication infrastructure, wired or wireless, does not exist or has been destroyed. The applications of ad hoc networks span several different sectors of society. The main applications are as below.
v Military (tactical) communication: -
For fast establishment of communication infrastructure during deployment of forces in a foreign region ad hoc networks are used. It is essential to build rapid and reliable communication. This is achieved by using ad hoc network.
v Rescue missions: -
At the time of rescue operations communication in areas without adequate wireless coverage becomes possible only due to ad hoc networks.
v National security: -
In times of national crises if the existing infrastructure becomes non operational due to some natural disaster ad hoc network is the only alternative.
v Law enforcement: -
Similar to tactical communication ad hoc networks play an important role in law enforcement e.g. in application such as crowd control.
v Commercial use: -
Now it is a trend to adopt ad hoc networks for commercial uses due to their unique properties. They are mainly used for setting up communication in exhibitions, conferences, or sale presentations.
v Education: -
The network can be used to interconnect workgroups moving in an area or campus. Distributed scientific experiments can be carried out and concept of virtual classrooms can be implemented.
10. Advantages :-
1) Use of ad-hoc networks could increase mobility and flexibility, as ad-hoc networks can be brought up and torn down in very short time.
2) Ad-hoc networks could be more economical in some cases as they eliminate fixed infrastructure costs and reduce power consumption at mobile nodes
3) Ad-hoc networks are more robust than conventional wireless networks because of their non-hierarchical distributed control and management mechanisms.
4) Because of short communication links (node-to-node instead of node to a central base station), radio emission levels could be kept at low level. This increases spectrum reuse possibility or possibility of using unlicensed bands.
5) Because of multi-hop support in ad-hoc networks, communication beyond Line Of Sight (LOS) is possible at high frequencies.
11. Limitations :-
Ad-hoc networks are yet far from being deployed on large-scale commercial basis. Some fundamental ad-hoc networking problems remain unsolved or need optimized solutions.
1) Although various routing protocols are suggested and tested for mobile ad-hoc networks, performance metrics like throughput, delay and protocol overhead in relation to successfully transmitted data need better optimization.
2) An additional complexity factor in ad-hoc network design is that different layers of the system are highly interdependent. Therefore, layers one, two and three of the standard OSI model could probably not be separated and optimized independent from the function of other layers.
3) Further, it is conceivable that public use of ad-hoc network requires specific regulations and charging mechanisms.
12. Future Scope :-
Yet, research in the area of ad hoc networks is very essential. Since these networks pose many complex issues, there are many open problems for research and opportunities for making significant contributions. Hence, there is a need for efficient routing protocols to allow the nodes to communicate over multihop paths consisting of possibly several links in a way that does not use any more of the network "resources" than necessary. It is required to free the ad hoc network from the problems of scalability, quality of service, security, compatibility with new hardware. The further research and developments along with implementation are its future scope.
13. CASE STUDY (In Brief):
IWAHN 2002:
IWAHN 2002, The International Workshop, on ad hoc network- was arranged in conjunction with 2002 International Conference on Parallel Processing at The Renaissance Vancouver Hotel Harbourside, Vancouver, British Columbia, Canada, dated August 18-21, 2002.This workshop provided a forum for engineers and scientists in academia, industry and government to present their latest research findings in any aspect of ad hoc networking.
Papers were invited for the following topics and related subjects with them. During the workshop the all topics were discussed.
§ Ad Hoc Routing Protocols
§ Ad Hoc Multicasting.
§ Ad Hoc Transport Layer Issues
§ Media Access Techniques.
§ Low Power and Energy-Efficient Algorithm and Protocol Designs.
§ Sensor and Data Fusion Ad Hoc Networks.
§ Quality of Service Issues
§ Network Architectures.
§ Mobile IP with Ad Hoc
§ Peer-to-Peer Networking.
§ Ad Hoc Networking over Bluetooth.
§ Application, Security in Ad Hoc
§ Fault-Tolerance Issues for Ad Hoc Networks.
14. Conclusion :-
This paper has proposed a standalone technology, ad hoc network which is multi-hop, rapidly deployable and can automatically form and adapt the changes. The current cellular network is fixed with pre-located cell sites, base stations and without multi-hop support. Though ad hoc has hostile environment, it is very important for fast and reliable communication when there is no infrastructure available. Conventional distributed protocols include extensive bandwidth, power and computation overheads for MHs in ad hoc network, a bandwidth efficient distributed routing protocol based on novel concept of associativity, proposed here, is very suitable.
