This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Mobile Ad hoc Network is a collection of wireless mobile devices such as laptops, handheld digital devices, personal digital assistants and wearable computers forming a temporary network without the aid of any infrastructure or centralized administration. The vision of MANET (Corson and Macker 1999) is to form a wireless Internet, where users can move anywhere anytime with the rest of the world and by incorporating routing functionality into mobile nodes. The Internet Engineering Task Force (IETF) has created a MANET working group to standardize the Internet Protocol (IP) routing protocol functionality suitable for wireless routing application within both static and dynamic network topologies.
MANETs are self-organized and self-configured multi-hop wireless networks where the structure of the network changes dynamically due to the mobility of mobile nodes. MANETs are being increasingly used due to their decentralized and dynamic nature as well as the fact that they do not require any fixed, preexisting infrastructure. In general, there are two distinct approaches for enabling wireless mobile units to communicate with each other. They are Infrastructure-based Wireless Local Area Networks (Wireless LANs) (Murthy and Manoj 2004) and Infrastructure-less Ad hoc Wireless LANs (Jochen Schiller 2003).
Infrastructure-based Wireless Network: Wireless networks have traditionally been based on the cellular concept and relied on good infrastructure support such as Access Point (AP) and backbone. Here mobile devices communicate with access points as base stations connected to the fixed network infrastructure. It is depicted in Figure 1.1(a).
Infrastructure-less Wireless Network: Figure 1.1(b) shows infrastructure-less approach namely ad hoc wireless network, wherein the wireless devices can communicate with each other, which is commonly known as a MANET. A MANET is a collection of wireless nodes that can dynamically form a network to exchange information without using any pre-existing fixed network infrastructure.
Figure 1.1 MANET Approaches
Like wired Local Area Networks, a Wireless LAN has a communication range typical of a single building or a cluster of buildings, i.e., 100-500 meters. A Wireless LAN should satisfy the same requirements typical of any LAN, including high capacity, full connectivity among attached stations and broadcast capability. However, to meet these objectives, Wireless LANs should be designed to face some issues specific to the wireless environment, such as security on the air, power consumption, mobility and bandwidth limitation of the air interface. Infrastructure-based Wireless LANs require a special node called Access Point, which hosts or terminal connects via existing wired LANs. APs can act as a router and arbiter between mobile devices and the rest of the networks. This approach is used in Wireless-Fidelity (Wi-Fi) hotspots to provide wireless Internet access at coffee shops, airports, conferences and other public places.
The set of mobile nodes that are associated with a particular AP is called the Basic Service Set (BSS). A number of BSSs can be connected together by means of a backbone network to form an Extended Service Set (ESS), in order to extend the Wi-Fi coverage area. In ESS, every AP is given with the same service set identifier, which serves as a network "name" for the network users. In many dynamic environments such as disaster sites, battlefields and temporary conference meetings where people and/or vehicles need to be temporarily interconnected, it may be difficult and/or expensive to deploy infrastructure-based Wireless LANs. For these environments, infrastructure-less or ad hoc Wireless LANs provide a viable alternative solution.
Ad hoc Wireless LANs do not need any fixed infrastructure and require only the mobile nodes to cooperate in a peer-to-peer fashion to form a temporary network in order to exchange data. However, this configuration of the Institute of Electrical and Electronics Engineering (IEEE) 802.11 standard is limited to single-hop communication which is only applicable to mobile nodes within a mutual transmission range.
Due to increase in the processing power and transceiver capability of the mobile nodes, it has become feasible to increase the communication range of the temporary network using the mobile nodes itself as forwarding agents and relying on the upper layers of the protocol stack for multi-hop path formation. Therefore, mobile nodes acting as routers and it may form the backbone of a spontaneous network that extends the range of the ad hoc wireless LAN beyond the transmission radius of the source. This latter category of ad hoc wireless LANs is popularly referred as MANET.
The MANET is characterized by energy constrained nodes, bandwidth constrained links and dynamic topology. In real-time applications, such as audio, video, and real-time data, the ad hoc networks need Quality of Service (QoS) in terms of delay, bandwidth, and packet loss is important. Providing QoS in ad-hoc networks is a challenging task because of the dynamic nature of network topology and imprecise state information. Hence it is important to have a dynamic routing protocol with fast re-routing capability, which also provides stable route during the life-time of the flows. The infrastructure-less approach is increasingly becoming a very important part of communication technology, because in many contexts, information exchange between mobile units cannot rely on any fixed network infrastructure, but on rapid configuration of wireless connections on-the-fly.
In Infrastructure-less network, a MANET consists of a set of mobile nodes that may communicate with one another from time to time where no base stations are present. In MANET, each host is equipped with a Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) (Crow et al 1997) transceiver. In such cases, a mobile node may communicate with each other directly or indirectly. If it is an indirect communication, a multi-hop scenario occurs, where the packets originated from the source host are relayed by several intermediate mobile nodes before reaching the destination. The traffic types in ad hoc networks are quite different from those in an infrastructure-based wireless network, including:
Peer-to-Peer: Communication between two nodes that are within one hop. The peer-to-peer is shown in Figure 1.2.
Figure 1.2 Peer-to-Peer Communication
Remote-to-Remote: Figure 1.3 depicts the communication between two nodes beyond a single hop but which maintain a stable route between them. This may be the result of several nodes staying within the communication range of each other in a single area or possibly moving as a group. The traffic is similar to standard network traffic.
Figure 1.3 Remote-to-Remote Communication
There are various types of communications based on the type of recipients namely unicasting, anycasting, multicasting and broadcasting.
Unicasting: One to one communication is called unicasting. In unicasting, the packet is transmitted to a specific recipient.
Anycasting: From a single node to any one node, out of a set of nodes.
Multicasting: Multicasting is a limited case of broadcasting in which a subset of nodes from the entire nodes participates and communicates among them. It is the transmission of datagrams to a group of nodes identified by a single destination address.
Broadcasting: One to all communication is referred to as broadcasting. The packet is transmitted to each and every node of the network. Broadcasting is often used as a building block for route discovery in on-demand ad hoc routing protocols. For designing the ad hoc networks, one of the primary goal is to reduce the broadcast overhead (redundant retransmission, channel contention and packet collision) while reaching all the nodes in the network.
The nodes in the MANET are not only acting as hosts but also as routers that route data to or from other nodes in a network. In MANET, where there is no infrastructure support as is the case with wired network since a destination node might be out of range of a source node transmitting packets, a routing procedure (Ramanathan and Steenstrup 1996) is always needed to find a path as it forwards the packets appropriately between the source and the destination. Network-wide broadcasting (Jetcheva et al 2001) provides route establishment and control functionality for a number of unicast and multicast protocols.
1.1.1 MANET Characteristics
A MANET is an autonomous system consisting of mobile nodes which are free to move in a random manner. In MANET, mobile nodes are equipped with wireless transceivers to communicate with each other. MANET has the following salient characteristics (Corson and Macker 1999):
Dynamic Network Topologies: In MANET, mobile nodes location changes as they move around causing the network topology. Typically the multi-hop may change arbitrarily and rapidly at un predictable times.
Bandwidth constrained variable constraints links: The bandwidth of the wireless links in MANET are significantly lower than the wired links. MANET has relatively low bandwidth links, high bit error rates, unstable and asymmetric links.
Energy constrained operations: Mobile devices such as laptops and personal digital assistants rely on battery power for their energy sources. Mobile devices act as both an end system and a router for forwarding operation at the same time. The important tasks of mobile devices in MANET are wireless signal transmission, retransmission and broadcasting operations which require battery power.
Physical Security: Wireless networks are more prone to the physical security threats of eavesdropping, denial-of-service and routing attacks when compared to wired networks.
1.1.2 MANET Features
Regardless of the application, there are certain features that can determine the effectiveness and efficiency of a MANET. MANETs share many of the properties of wired-infrastructure LANs and it posses the following unique features (Corson and Macker 1999):
Autonomous nodes: In MANET, each mobile node is an autonomous node, which may function as a host and also as a router that relays packets along network paths.
Distributed operation: The nodes in a MANET should associate among itself and each node act as a relay to implement routing and security functions. Since there is no background network for the central control of the network operations, the control and management of the network must be distributed among nodes.
Multi-hop routing: When delivering packets from a source to its destination (when the sender node are not directly connected with destination node), the packets should be forwarded via one or more intermediate nodes.
Infrastructure-less network: The MANET is an autonomous system of mobile nodes that are connected without any infrastructure or centralized administration. Each node also acts as a router for forwarding message to other nodes that may not be within the same transmission range.
Heterogeneity: The scope of MANET applications show that the number of mobile nodes can range from small number of nodes to tens of thousands of nodes. The size, memory, computational power and battery power of theses mobile nodes are different from one another.
1.1.3 Applications of MANET
With the increase of portable devices as well as progress in wireless communication, MANET is gaining more importance with the increasing number of widespread applications. MANET can be applied anywhere where there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use.
Significant examples of MANETs include establishing survivable, efficient and dynamic communication for emergency/rescue operations, disaster relief efforts, and military networks. Such network scenarios cannot rely on centralized or organized connectivity, but it can be conceived as applications of MANET. However, MANETs are not solely intended for disconnected autonomous operations or scaled scenarios (i.e. hundreds or even thousands of cooperation wireless nodes in a region). They may be used as hybrid infrastructure extensions in fixed infrastructure operations. A hybrid infrastructure extension is a dynamic enhancement to a home or campus wireless networking environment. It provides an extended service and allows low-cost, low complexity dynamic adjustments to provide coverage regions and range extensions away from the more fixed infrastructures networks.
The majority of applications for the MANET technology are in areas where rapid deployment and dynamic reconfiguration are necessary and the wired network is not available. There are numerous scenarios that do not have an available network infrastructure and could benefit from the creation of an ad hoc network. Typical applications include (Corson and Macker 1999):
Military battlefield: MANET would allow the military to take advantage of commonplace network technology to maintain an information network between the soldiers, vehicles, and military information head quarters.
Rescue/Emergency operations: Rapid installation of a communication infrastructure during a natural/environmental disaster that demolished the existing communication infrastructure like telephone lines, backbones and access points.
Commercial sector: Emergency rescue operations (like fire, flood, earthquake, etc.,) must take place where non-existing or damaged communications infrastructure need rapid deployment of a communication network.
Local level: MANET can autonomously link an instant and temporary multimedia network using notebook computers or palmtop computers to spread and share information among participants at a conference or classroom.
Personal Area Network (PAN): Short-range MANET can simplify the intercommunication between various mobile devices such as Personal Digital Assistants (PDAs), a laptop, and a cellular phone.
Educational classrooms: Simple installation of a communication infrastructure to create an interactive classroom on demand.
Commercial projects: Simple installation of a communication infrastructure for commercial gatherings such as conferences, exhibitions, workshops and meetings.
1.1.4 Challenges Faced in MANET
Regardless of the attractive applications, the features of MANET introduce several challenges that must be studied carefully before a wide commercial deployment can be expected. These include (Corson and Macker 1999):
Routing: Since the topology of the network is constantly changing, the issue of routing packets between any pair of nodes becomes a challenging task. Most protocols should be based on reactive routing instead of proactive.
Security and Reliability: MANET has security problems particularly due to nasty neighbour relaying packets. Further, wireless link characteristics introduce reliability problems, because of the limited wireless transmission range, the broadcast nature of the wireless medium (e.g. hidden terminal problem), mobility-induced packet losses, and data transmission errors.
Quality of Service (QoS): Providing different quality of service levels in a constantly changing environment will be a challenge.
Internetworking: The coexistence of routing protocols, for the sake of internetworking a MANET with a fixed network, in a mobile device is a challenge for the mobility management.
Power Consumption: For most of the lightweight mobile terminals, the communication-related functions should be optimized for less power consumption (Toh 2001).
1.1.5 MANET Mobility Models
To thoroughly and systematically study a new MANET protocol, it is important to evaluate its performance. Protocol simulation (Kurkowski et al 2005) has several key parameters, including mobility model and communicating traffic pattern, among others. The Mobility model (Lin et al 2004) is designed to describe the movement pattern of mobile users, and how their location, velocity and acceleration change over time. Since mobility patterns may play a significant role in determining the protocol performance, it is desirable for mobility models to emulate the movement pattern of targeted real life applications in a reasonable way. Camp et al (2002) described seven different synthetic entity mobility models for ad hoc networks which are listed below:
Random Walk Mobility Model (including its many derivatives): A simple mobility model based on random directions and speeds.
Random Waypoint Mobility Model: A model that includes pause times between changes in destination and speed.
Random Direction Mobility Model: A model that forces mobile nodes to travel to the edge of the simulation area before changing direction and speed.
A Boundless Simulation Area Mobility Model: A model that converts a two dimensional rectangular simulation area into a torus-shaped simulation area.
Gauss-Markov Mobility Model: A model that uses one tuning parameter to vary the degree of randomness in the mobility pattern.
A Probabilistic Version of the Random Walk Mobility Model: A model that utilizes a set of probabilities to determine the next position of an MN.
City Section Mobility Model: A simulation area that represents streets within a city.
1.2 MANET AND OSI REFERENCE MODEL
The International Organization for Standardization (ISO) proposed the Open System Interconnection (OSI) reference model (Day and Zimmerman 1983). In OSI reference model, there are seven layers: physical, datalink, network, transport, session, presentation and application layer. It is primarily designed to enable multi-vendor computers to interact and communicate. OSI defines seven layers in a hierarchy that goes from physical to application layers as shown in Figure 1.4. OSI is still a reference model, often used to describe and outline the different levels of networking protocols and their relationships with each other. The communication mechanisms of a MANET are mainly associated with the protocols operating at layers 1 to 3 of the OSI reference model.
1.2.1 Physical Layer
The IEEE 802.11 standards (Crow et al 1997) specify a Physical Layer (PHY) and Medium Access Control (MAC) layer for Wireless LAN. The physical layer serves as an interface between the MAC sub layer and wireless medium where frames are transmitted and received. The physical layer variants include the provision of Clear Channel Assessment (CCA), which is needed for sensing the wireless medium and indicating to the MAC layer when a signal is detected or when the channel is busy. The Physical Layer is subdivided into the Physical Layer Convergence Protocol (PLCP) and Physical Medium Dependent (PMD) sub layer.
Figure 1.4 The OSI Reference Model and its Relationship with MANET
The PLCP sub layer provides a carrier channel assessment and provides a common PHY Service Access Points (SAP) with 1 / 2 Mbps transfer rate. Finally the Physical Medium Dependent (PMD) sub layer handles modulation and encoding and decoding of signals.
The IEEE 802.11 wireless standard support three different physical layers: one layer based on Infra Red (IR) (Kahn and Barry 1997) and other two layers based on radio transmission. Radio based standards operate within the 2.4 Giga Hertz (GHz) ISM band. The 802.11 standard defines data rates of 1 Mbps and 2 Mbps via radio waves using Frequency Hopping Spread Spectrum (FHSS) and Direct Sequence Spread Spectrum (DSSS).
Using FHSS techniques, the 2.4 GHz band is divided into 75 channels of 1 MHz each. The sender and receiver agree on a hopping pattern, and data is sent over a sequence of the sub channels. Each conversation within the 802.11 network occurs over a different hopping pattern, and the patterns are designed to minimize the chance of two senders using the same sub channel simultaneously. The standard specifies Gaussian Shaped Frequency Shift Keying (GSFSK) modulation scheme for the FHSS PHY. For 1 Mbps a 2 level Digital GSFSK (Chang and Shiu 2006) is used, (1 bit is mapped to one frequency) a 4 level GFSK for 2 M bit/s (i.e., 2 bit are mapped to one frequency).
Direct Sequence Spread Spectrum (DSSS) is the alternative spread spectrum techniques separated by code and not by frequency. In 802.11, DSSS spreading is achieved using a chipping sequence. IEEE 802.11 DSSS PHY also uses a 2.4 GHz ISM band and offers both 1 and 2 Mbps data rates. The system uses Differential Binary Phase Shift Keying (DBPSK) (Lo et al 1993) for 1 Mbps transmission and Differential Quadrature Phase Shift Keying (DQPSK) for 2 Mbps as modulation scheme.
1.2.2 Datalink Layer
The IEEE 802.11 standard specifies a MAC layer and a Physical Layer for Wireless LANs. The MAC layer provides to its users both contention-based and contention-free access control on a variety of physical layers. The basic access method in the IEEE 802.11 MAC protocol is the Distributed Coordination Function (DCF), which is a CSMA/CA MAC protocol. Besides the DCF, the IEEE 802.11 also incorporates an alternative access method known as the Point Coordination Function (PCF). As the PCF access method cannot be adopted in ad hoc networks. In wireless network, the sender may apply carrier sense and detect an idle medium. The sender starts sending but a collision happens at the receiver due to a second sender. The sender detects no collision, assumes that the data has been transmitted without errors, but actually a collision might have destroyed the data at the receiver. Thus, this common MAC Scheme from wired network fails in a wireless network. The major challenge of the MAC sublayer is the hidden node problem (Crow et al 1997).
Figure 1.5 Hidden Node Problem
The Hidden Node Problem is depicted in Figure 1.5, when node A wants to transmit a frame to node B, node C is not aware of this transmission due to its distance from node A (node C is a hidden terminal for node A). If node C simultaneously transmits a frame to node B, a collision occurs at node B. In wireless network, many MAC protocols (Xu and Saadawl 2002) have been designed to solve this hidden node problem through CSMA/CA scheme. This scheme is sender initiated including an exchange of channel reservation control frames between the communicating nodes prior to data transmission. In this case, all the neighbouring nodes of a given communicating node need to be informed that the channel will be occupied for a time period. As shown in Figure 1.5, node A wishing to transmit a data packet to node B, node A first broadcasts a Request To Send (RTS) control frame (Ju et al 2003) containing the length of the data and address of node B. Upon receiving the RTS, node B responds by broadcasting a Clear To Send (CTS) control frame containing the length of data and address of node A. Any node overhearing either of these two control frames remains silent for the entire transmission period.
Considering the situation inÂ wireless networks, where theÂ exposed terminal problemÂ occurs when a node is prevented from sending packets to other nodes due to a neighbouring transmitter. As shown in Figure 1.6, four nodes labeled R1, S1, S2, and R2, where the two receivers (R1 and R2) are out of range of each other, yet the two transmitters (S1 and S2) in the middle are in range of each other. Here, if a transmission between S1 and R1 is taking place, node S2 is prevented from transmitting to R2 as it concludes afterÂ carrier senseÂ that it will interfere with the transmission by its neighbour S1. However, it is to be noted that R2 could still receive the transmission of S2 without interference because it is out of range from S1. This is known as Exposed Terminal Problem, depicted in Figure 1.6.
Figure 1.6 Exposed Terminal Problem
1.2.3 Network Layer
Residing above the data link layer, the network layer (Basagani
et al 2004) is responsible for routing packets from source to destination. In wired network, routing paths are usually fixed since nodes are static. However, in wireless networks, mobile nodes are free to move, resulting in frequently changed routing paths. The wireless network layer hence needs to take care of mobility management, such as location tracking or update information, which is not considered in static wired networks. Network layer provides end-to-end transmission service. Due to the dynamic nature of MANET, the destination node may not be located within the transmission range of the source node. Therefore, the need for a routing protocol to set up route from source to destination and a mechanism to maintain the route, since some links may be broken due to node mobility. The important task of network layer includes the exchange of routing information, finding a route to a destination and providing efficient utilization of the available communication bandwidth of the network. As a result, a good routing protocol should be able to solve the above issues with a low communication overhead.
1.3 BROADCASTING IN MANET
Network-wide broadcasting (Jetcheva et al 2001) means one node sends a packet to all other nodes in a network. Broadcasting is a building block for unicast routing protocols such as Dynamic Source Routing(DSR) (Johnson et al 2007), Ad hoc On-Demand Distance Vector(AODV) (Perkins 2003), Zone Routing Protocol(ZRP)(Haas et al 2002), and Location Aided Routing(LAR) (Ko and Vaidya 1998) use broadcasting to establish routes for delivery of packets. A MANET consists of a set of wireless mobile hosts that may communicate with one another from time to time. In MANET, no base stations are supported for communication among the mobile hosts. Each host is equipped with a CSMA/CA transceiver. In such an environment, a host may communicate with another directly or indirectly. In the latter case, a multi-hop scenario occurs, where the packets originated from the source host are relayed by several intermediate hosts before reaching the destination. Hence it is important to carefully design an efficient broadcasting method so as to avoid redundancy in the dissemination process for discovering the route in the multi-hop network. Broadcasting is a major communication primitive required by many applications and protocols in MANETs. Traditional broadcast method often causes unproductive and harmful bandwidth congestion and wastes node resources.
Further, broadcasting is frequently used to discover and advertise resources. A simple example of resource discovery is the route discovery in many reactive routing protocols. Broadcasting is also frequently used to distribute content to all network participants, such as alarm signals or announcements. In highly dynamic scenarios, broadcasting serves as a robust way of realizing other communication primitives, such as multicast.
1.3.1 Design Issues
MANET consists of a set of mobile hosts that may communicate with each other without any infrastructure and centralized administration. Each mobile node is equipped with wireless transceiver which can access the air medium. The nature of broadcasting is spontaneous; any mobile node can issue a broadcast operation at any time. Collision avoidance is difficult in overcoming the hidden node problem, where a node is able to determine whether its neighbours are busy receiving transmissions from an uncommon neighbour.
The 802.11 MAC (I. C. S. L. M. S. Committee 1997) utilizes a Request To Send (RTS) / Clear To Send(CTS) / Data / Acknowledgement (ACK) procedure used for hidden node problem when unicasting packets. However, the RTS/CTS/Data/ACK procedure is too difficult to implement for broadcast packets as it would be difficult to coordinate. Therefore, the only requirement made for broadcasting nodes is that they assess a clear channel before broadcasting. Unfortunately, clear channel assessment does not prevent collisions from hidden nodes. Additionally, no recource is provided for collision when two neighbours assess a clear channel and transmit simultaneously.
Suppose a source node originates a broadcast packet, the radio waves propagate at the speed of light, all neighbours will receive the transmission simultaneously and also rebroadcast the packet at the same time. To overcome this problem, broadcast protocols jitter the scheduling of broadcast packets from the network layer to the MAC layer by some uniform random amount of time. This (small) offset allows one neighbour to obtain the channel first, while other neighbours detect that the channel is busy (clear channel assessment fails). The jitter time can be relatively small, just enough to allow one node access to the channel before the others.
Broadcasting protocols require a node to keep track of the redundant packets received over a short time interval in order to determine whether to rebroadcast or not. That time interval is termed as Random Delay Time (RDT), it is randomly chosen from a uniform distribution between 0 and Tmax seconds, where Tmax is the highest possible delay interval. This delay in transmission accomplishes two things. First, it allows nodes sufficient time to receive redundant packets and assess whether to rebroadcast. Second, the randomized scheduling prevents the collisions.
An important design consideration is the implementation of the random delay time. One approach is to send broadcast packets to the MAC layer after a short random time similar to the jitter. In this case, packets remain in the InterFace Queue (IFQ) until the channel becomes clear for broadcast. While the packet is in the IFQ, redundant packets may be received, allowing the network layer to determine if rebroadcasting is still required. If the network layer protocol decides the packet should not be rebroadcast, it informs the MAC layer to discard the packet.
A second approach is to implement the random delay time as a longer time period and keep the packet at the network layer until the RDT expires. Retransmission assessment is done considering all redundant packets during the RDT. After RDT expiration, the packet is either sent to the MAC layer or dropped. No attempts are made by the network layer to remove the packet after sending it to the MAC layer. Each broadcast protocol requires node to rebroadcast a given packet not more than one time in order to prevent infinite transmission loops. Thus, each broadcast protocol requires that node cache the original source node ID of the packet and the packet ID. It allows the protocol to uniquely identify each broadcast packet and assign appropriate behavior upon reception of a packet. This characteristic strictly avoids the infinite loops behavior of broadcasting.
1.3.2 Applications of Broadcasting
Content Distribution Applications
A typical application for broadcasting in MANETs is news spreading. Examples are the broadcasting of aid information in a disaster area to coordinate relief actions (e.g. fire fighting (Karumanchi et al 1999)), the dissemination of parking availability information in a city scenario, dissemination of accident information in Vehicle Ad hoc NETwork (VANET) and the dissemination of alarms and announcements. Further content distribution applications are publish-subscribe applications, where some nodes are subscribers to content providers. These applications typically run in the background for a few hours or even a few days. Examples are Usenet-on-fly (Becker et al 2002), latency insensitive data (Su et al 2004) and file sharing in a peer-to-peer (P2P) manner (Lindemann and Waldhorst 2005).
Resource Discovery and Advertisement
Further typical broadcast scenarios are resource (or service) discovery and advertisement. MANET nodes may have little or no knowledge at all about the capabilities and services offered by each other. Therefore, mechanisms for resource discovery or advertisement are important for these self-configurable networks. Due to the decentralized and highly dynamic nature of MANETs, service discovery and service advertisement frequently use broadcasting strategies. An example of resources is a multi-hop routing path to a given destination. For highly dynamic topologies the route is continuously changing and the resource is so highly dynamic that maintaining a route to all nodes at every time is very costly. However, most of the time, it is not necessary to have an up-to-date route to all other nodes. Hence, a novel class of reactive routing protocols, such as DSR and AODV has been developed. Reactive routing protocols only set up routes to nodes they communicate with and these routes are kept alive as long as they are needed. This is realized by a route discovery mechanism, which uses broadcasting strategies to distribute control messages for route discovery.
Sensor Data Dissemination
Another important application of broadcasting is the sensor data dissemination. Real-time sensor data may be disseminated to other nodes in order to realize a fully-replicated database, where every database node has a consistent view of real time events. Data consistency algorithms act on disseminated observation data and chronologically order observed events in MANETs.
1.4 PROBLEM DEFINITION
Broadcasting is a communication primitive and important network service for routing protocols in MANET. On-demand routing protocols such as DSR and AODV use flooding as the basic mechanism to propagate control message namely Route REQuest (RREQ) for determining the route in the MANET. This simplest mechanism is known as simple flooding. Despite its simplicity, simple flooding generates excessive amount of redundant retransmission, channel contention and packet collision. Such a phenomenon is referred to as broadcast storm problem and it can lead to a collapse in the operation of the network, since it requires every node involved to retransmit the message. Broadcasting a large number of RREQ packets may guarantee a high chance of discovering routes to the destinations. But, this will consume a lot of energy resources of mobile node and cause congestion of the network. Therefore, a route discovery method that can guarantee an efficient utilization of these limited system resources while achieving acceptable levels of other performance metrics such as overhead and power consumption is required.
In most existing probabilistic approaches of network-wide broadcasting, the rebroadcast probability at a given node is fixed. Here, every node in the network has the same probability to rebroadcast a packet regardless of the number of its neighbouring nodes. This could lead to poor reachability or more number of redundant retransmissions. In counter-based scheme, packets received at a node are less than that of a threshold value. However, most of the existing solutions are inadequate in reducing the number of redundant broadcast while still guarantee that most nodes receive the packet. In some cases, the schemes require near topological information or used additional hardware devices for distance measurement or location identification in order to reduce the redundant transmissions. The aim of this thesis is to propose an efficient probabilistic scheme for MANET in order to reduce the broadcast overhead and alleviate the broadcast storm problem.
1.5 ABOUT THE PROPOSED WORK
Simple flooding and Probability flooding are the broadcast methods to provide a solution for network-wide broadcasting but consume more network resources. Further k-means clustering based flooding is also evaluated and its performance is compared with the simple and probability flooding methods. Ideally, the rebroadcast probability p should be high in a node located in a sparse region and relatively low in a node located in a dense region. If the rebroadcast probability p is too low then the reachability might be poor while if the rebroadcast probability p is set too high then many redundant rebroadcasts might be generated.
In this work, an optimum density based model for probability flooding is proposed and its performance is compared with the existing broadcasting methods. This research work suggests and investigates the performance of a new method namely optimum density based model for probability flooding where the rebroadcast probability is determined at a transmitting node densities and as well as its previous neighbour node's densities instead of assigning fixed probability for each node. The primary goal of this research is to study the existing protocols for flooding through network simulator-2(ns-2) simulations (Hogie et al 2006) and device a new and efficient broadcasting method which will cause minimum broadcast overhead in the MANET.
Secondly, the another new method namely Flooding Reduced-Destination Sequenced Distance Vector routing protocol is proposed for reducing the overhead due to periodic and triggered update messages using optimum density based probability flooding in Destination Sequenced Distance Vector routing protocol. By doing an extensive literature survey, the resources for doing the proposed research on ns-2 and the required knowledge will be acquired from various resources. First a MANET with required number of nodes with suitable mobility and transmission power is proposed to be constructed on ns-2. This ns-2 is widely used by academia and the research community for simulation of MANETs and ad hoc routing protocols and can effectively simulate an 802.11 network. The CMU/Rice University Monarch group has made extensions to ns-2 to support mobility including ability to simulate multi-hop wireless ad-hoc networks. The key reason for selecting ns-2 is the fact that it supports the use of co-ordinate system by default and without major modification should serve our purposes. The other advantage is the simulator code for most protocols. The researchers are interested in comparing exist for ns-2 which are freely available. A suitable version of ns-2 is proposed to be installed on Red Hat Linux 9 for implementing the idea. While evaluation, the various standard metrics are proposed to be used for selecting suitable protocols. Suitable trace files will be used for measuring various performances. The trace files will be filtered and analyzed by using suitable perl scripts or grep utility to find the performance. Finally, based on the information gathered from the trace files, various graphs will be prepared for visualizing the performance of the flooding algorithms.
1.6 CONTRIBUTIONS OF THIS RESEARCH
A detailed study and analysis of the impact of broadcast mechanism in routing protocols on network performance is done. This analysis obviously proved the problems due to the overhead of broadcast or flooding algorithms in their design.
An improved version of broadcast algorithm based on K-means clustering algorithm is proposed and evaluated with suitable network scenario. The performance of cluster based broadcasting is compared with the simple flooding and probability flooding method.
This research proposes a density based broadcast approach namely optimum density based model for probability flooding for reducing the broadcast overhead in MANET. In several previous works, particularly in probability based flooding schemes, the rebroadcast of a message will be done only based on the density of a particular transmitting node. But in this algorithm, each node will forward or rebroadcast a message based on its density as well as its previous neighbour node's density. This characteristic makes this algorithm most unique and produced excellent improvements in its performance. The simulation results reveal that the new approach improves the route discovery process by reducing the Medium Access Control (MAC) load, routing load, collision and power consumption when compared to simple and probability flooding.
This research work also proposes a new method namely Flooding Reduced-Destination Sequenced Distance Vector routing protocol for reducing the broadcast overhead due to periodic and triggered update messages in Destination Sequenced Distance Vector routing protocol. The simulation results reveal that the new approach FR-DSDV improves the network performance by reducing the Medium Access Control (MAC) load, routing load, collision and power consumption when compared to DSDV.
1.7.1 Basic Routing Protocol Families
220.127.116.11 Distance Vector Routing Protocols
Elizabeth Royer and Chai-Keong Toh (1999) have described about routing protocols of MANET. In distance vector routing protocols, every host maintains a routing table containing the distance from itself to possible destinations. Each routing table entry contains the next hop to the destination and the distance to the destination. Nodes only feed the estimated link costs for each destination (e.g. the number of hops to destination) to their neighbours, instead of flooding the whole network. All nodes calculate the shortest paths to the destinations using that broadcasted information.
18.104.22.168 Link State Routing Protocols
Elizabeth Royer and Chai-Keong Toh (1999) have briefed about Link state routing protocols. These protocols keep a routing table for complete topology, which is built up by finding the shortest path of link costs. Link cost information is periodically transmitted and received by all nodes using a flooding technique; these periodic floods are called Link State Advertisements (LSA). Flooding means that a node sends out its information to all other neighbour nodes and they forward all received information to their neighbours and so on. Each node updates its table using the new link cost information gathered from these floods.
22.214.171.124 Source Routing Protocols
Elizabeth Royer and Chai-Keong Toh (1999) presented about source routing protocols. In source routing, all data packets carry their routing information as their header. The originating node could learn this routing information by means of a source routing protocol: When a node receives a (broadcast) route request packet for a destination, it adds its own address to the header and then forwards the packet. The destination uses the recorded route in reverse order to send a route reply to the requesting node. Thus, the originating node is provided with the complete route to the destination. The routing decision is made at departure. Loops are avoided, since nodes can determine if they are already in the packet header.
1.7.2 Types of Routing Protocols
Routing protocols are needed whenever delivered data packets need to be handed over several nodes to arrive at their destinations. Routing protocols have to find routes for packet delivery and make sure that the packets are delivered to the correct destinations. The existing routing protocols such as distance vector routing and link-state routing were originally designed for static, wired networks and dynamic topology was not considered. Mehran et al (2004) have classified the Routing protocols for ad hoc networks into different categories.
Pro-active, re-active and hybrid
Centralized or distributed
Dynamic or static
As for the second criterion, when a routing protocol is centralized, all decisions are made at a center node, whereas in a distributed routing protocol, all nodes cooperate, usually in a symmetric way, in order to reach a routing decision. The third criterion is concerned with the nature of the information used for the routing process.
A dynamic protocol may change behavior according to the network status, which can cause congestion on a link or many other possible factors. A link may fail unexpectedly, or a new link may be added. A dynamic routing protocol must discover these changes, automatically adjust its routing tables, and inform other routers of the changes. The process of rebuilding the routing tables based on new information is called convergence. Static protocols on the other hand do not change when the network status changes and the changes must be added manually. An example of a static protocol is flooding, in which a node always retransmits an incoming packet, unless it has already sent the same packet earlier.
Broadcasting may be used to disseminate data to all other nodes in the network or may be used by MANET unicast or multicast routing protocols to disseminate control information. For example, unicast protocols such as DSR, AODV, ZRP and LAR use broadcasting to establish routes. Currently these protocols all rely on a simple form of plain or blind flooding technique, in which each node retransmits each received unique packet exactly one time. The main role of broadcasting methods in routing protocols are route discovery process, when advising an error message to erase invalid routes from the routing table, or as an efficient mechanism for reliable multicast in a fast-moving MANET. Generally speaking, currently known routing protocols for ad hoc networks can be classified in three different classes: pro-active protocols, re-active protocols and the hybrid protocols. These three classes differ in a number of ways.
126.96.36.199 Proactive Routing Protocols
These routing protocols are similar to and come as a natural extension of those for the wired networks. In proactive routing (Das et al 1999), each node has one or more tables that contain the latest information of the routes to any node in the network. The two kinds of table updating in proactive protocols are the periodic update and the triggered update. In periodic update, each node periodically broadcasts its table in the network. Each node just arriving in the network receives that table. In triggered update, as soon as a node detects a change in its neighbourhood, it broadcasts entries in its routing table that have changed as a result.
Proactive routing tends to waste bandwidth and power in the network because of the need to broadcast the routing tables/updates. Furthermore, as the number of nodes in the MANET increases, the size of the table will increase; this can become a problem in and of itself. DSDV, which is not to be suitable for large dense network. A route table at each node enumerates all available destinations and the corresponding hop-count from the node. Each route table entry is tagged with a sequence number, which is created by a destination node. To maintain consistency of the route tables in a dynamically changing network topology, each node transmits table updates either periodically (periodic update) or when new significant information is available (triggered update).
Routing information is advertised by broadcasting or multicasting. The packets are transmitted periodically and incrementally as topological changes are detected. Topological changes include movement of a node from place to place or the disappearance of the node from the network. Information about the time interval between arrival of the very first routing solution and the arrival of the best routing solution for each particular destination is also maintained.
On the basis of this information, a decision may be made to delay advertising routes that are about to change, thus, reducing fluctuations in the route tables. The advertisement of possible unstable routes is delayed to reduce the number of rebroadcasts of possible route entries that normally arrive with the same sequence number. Some of the Proactive routing protocols are:
Destination-Sequenced Distance Vector (DSDV)
Wireless Routing Protocol (WRP)
Global State Routing (GSR)
Fisheye State Routing (FSR)
Source-Tree Adaptive Routing (STAR)
Distance Routing Effect Algorithm for Mobility (DREAM)
Multimedia Support in Mobile Wireless Network (MMWN)
Cluster-Head Gateway Switch Routing (CGSR)
Hierarchical State Routing (HSR)
Optimized Link State Routing (OLSR)
Topology Broadcast Reverse Path Forwarding (TBRPF)
Open Shortest Path First (OSPF)
188.8.131.52 Reactive Routing Protocols
Maltz et al (1999) presented on-demand routing protocols were designed to reduce the overheads in proactive protocols by maintaining information for active routes only. This means routes are determined and maintained for nodes that require sending data to a particular destination. Route discovery usually occurs by flooding a route request packets through the network.
Reactive protocols can be classified into two categories: source routing and hop-by-hop routing. In source routed on-demand protocols each data packets carry the complete source to destination address. Therefore, each intermediate node forwards these packets according to the information kept in the header of each packet. This means that the intermediate nodes do not need to maintain up-to-date routing information for each active route in order to forward the packet towards the destination. Furthermore, nodes do not need to maintain neighbour connectivity through periodic beacon messages.
The major drawback with source routing protocols is that in large networks they do not perform well. This is due to two main reasons; firstly as the number of intermediate nodes in each route grows, then so does the probability of route failure. Secondly, as the number of intermediate nodes in each route grows, then the amount of overhead carried in each header of each packet will grow as well. Therefore, in large networks with significant levels of multi-hoping and high levels of mobility, these protocols may not scale well.
In hop-by-hop routing (also called as point-to-point routing) each data packet only carries the destination address and the next hop address. Therefore, each intermediate node in the path to the destination uses its routing table to forward each data packet towards the destination. The advantage of this strategy is that routes are adaptable to the dynamically changing environment of MANETs, since each node can update its routing table when receive fresher topology information and hence forward the data packets over fresher and better routes. Using fresher route recalculations are required during data transmission.
The disadvantage of this strategy is that each intermediate node must store and maintain routing information for each active route and each node may require to be aware of their surrounding neighbours through the use of beaconing messages. Some of the reactive routing protocols are:
Ad hoc On-Demand Distance Vector (AODV)
Dynamic Source Routing (DSR)
Routing On-demand Acyclic Multi-Path (ROAM)
Light-Weight Mobile Routing (LMR)
Temporally Ordered Routing Algorithm (TORA)
Associated-Based Routing (ABR)
Signal Stability Adaptive (SSA)
Relative Distance Micro-discovery Ad hoc Routing (RDMAR)
Location-Aided Routing (LAR)
Ant-colony-based Routing Algorithm (ARA)
Flow Oriented Routing Protocol (FORP)
Cluster-Based Routing Protocol (CBRP)
184.108.40.206 Hybrid Routing Protocols
Hybrid protocols combine the advantages of both pro-active and re-active routing, by locally using pro-active routing and inter-locally using re-active routing. This is partly based on the assumption that most communication in MANETs takes place between nodes that are close to each other, and the assumption that changes in topology are only important if they happen in the vicinity of a node. When a link fails or a node disappears on the other side of the network, it has only effect on local neighbourhoods; nodes on the other side of the network are not affected. The ZRP is an example of a hybrid routing protocol.
In MANET, mobile nodes communicate with each other using multi-hop wireless transceivers. There is no infrastructure such as base stations. A big challenge in the design of ad hoc network is the development of dynamic routing protocols that can efficiently find or establish the routes between two communicating nodes. The routing protocol must be able to keep up with the high degree of node mobility that often changes the network topology frequently and unpredictably.
1.7.3 Broadcasting Methods
Ni et al (1999) classified several proposed broadcast algorithms in two categories: deterministic and probabilistic. In a deterministic broadcast protocol, the set of relay nodes is chosen deterministically to cover the entire network. When a node receives a broadcast message, it will decide deterministically whether to forward the message or not. The probabilistic approaches require each node to rebroadcast the packet to its neighbours with a given forwarding probability. The advantages of deterministic broadcast schemes are low broadcast overhead and low potential packet collisions. In contrast to deterministic broadcast, a probabilistic broadcast protocol usually causes redundant retransmissions, which incurs relatively more overhead and potential packet collisions. To solve the impact of the broadcast storm problem several broadcast schemes have been proposed. Each of these methods operates differently according to their inherent characteristics.
These methods can be broadly categorized into four groups as follows:
1. Simple Flooding
2. Probability Based Methods
a. Probabilistic Scheme
b. Counter-Based Scheme
3. Area Based Methods
a. Distance-Based Scheme
b. Location-Based Scheme
4. Neighbour Knowledge Methods
a. Flooding with Self Pruning
b. Scalable Broadcast Algorithm (SBA)
c. Dominant Pruning
d. Multipoint Relaying
e. Ad Hoc Broadcast Protocol (AHBP)
f. Connected Dominating Set (CDS)-Based Broadcast Algorithm
g. Lightweight and Efficient Network-Wide Broadcast (LENWB)
1.7.4 Simple Flooding Method
Ni et al (1999) described about the simple flooding with broadcast storm problem. In simple flooding, source node broadcasts a packet to all its neighbours. Each of those neighbours in turn rebroadcasts the packet it receives the packet for the first time. This behaviour continues until all reachable network nodes have received and rebroadcast the packet once. The dissemination of packets in this way often consumes valuable network resources such as bandwidth and node power due to redundant retransmissions of broadcast packets. These redundant retransmissions of packets cause high contention and collision in the network. This is known as broadcast storm problem which can lead to a total collapse in the operation of the network.
Jetcheva et al (2001) proposed in IETF internet draft, the use of flooding as s simple protocol for broadcasting and multicasting in ad hoc networks which are characterized by low node densities and/or high mobility. Williams and Camp (2002) compared the performance of several proposed broadcast approaches including the probabilistic, counter-based, area based and neighbour knowledge methods.
1.7.5 Probability Based Methods
220.127.116.11 Probabilistic Scheme
Probability based method is one of the simplest and most efficient broadcast method that have been suggested by Ni et al (1999). This method is similar to simple flooding, except that nodes only rebroadcast with a pre determined forwarding probability p so that every node has the same probability to rebroadcast the message, regardless of its number of neighbours.
The study of Ni et al (1999) and Tseng et al (2003) shown that the probability scheme has poor reachability. The problem comes from the uniformity of the algorithm; every node has the same probability to rebroadcast the packet regardless of network topology.
Zhang and Agrawal (2005) suggested dynamic probabilistic algorithm that combines the properties of probabilistic and counter-based methods. In this method the forwarding probability at a node is set based on the number of duplicate packets received at a node. But the values of a packet counter at a node does not necessarily correspondent to the exact number of neighbours of the node, since some of its neighbours may have suppressed their rebroadcasts according to their local rebroadcast probability.
Cartigny and Simplot (2003) described a probabilistic scheme where the forwarding probability p is computed from the local density n. The authors have also introduced a fixed value parameter k to achieve high reachability. This broadcast scheme has a drawback of being locally uniform. This is because each node in the network determines its forwarding probability based on the fixed efficiency parameter k which is not globally optimal.
18.104.22.168 Counter Based Scheme
In the counter-based techniques, when a node receives a broadcast packet, it initiates a Random Assessment Delay (RAD) timer and a counter which counts the number of received duplicate packets. When the timer expires, if the counter exceeds the threshold value, the node assumes that all its neighbours might have received the same packet and will not rebroadcast the packet. Otherwise, the node will broadcast the packet. The predefined counter threshold is the key parameter of this technique and it has been shown in Tseng et al (2003) that transmission redundancy could be reduced by choosing a threshold value between 2 and 4. The algorithm for counter-based scheme is described as follows:
Algorithm: Counter-Based Scheme
Upon reception of a broadcast packet 'm' at a node X for the first time
Initialize the packet counter C=1
Set the RAD timer
Wait for RAD timer to expire
For every duplicate packet m received
increment C by 1
if (c < C) (here c is the counter threshold value)
Forward the packet m
Drop the packet m
1.7.6 Area Based Methods
Suppose a node receives a packet from a sender that is located only one meter away. If the receiving node rebroadcasts, the additional area covered by the retransmission is quite low. On the other side, if a node is located at the boundary of the sender node's transmission distance, then a rebroadcast would reach significant additional area. Area based methods only consider the coverage area of a transmission; they don't consider whether nodes exist within that area.
22.214.171.124 Distance-Based Scheme
Ni et al (1999) described the distance based scheme for reducing the redundant rebroadcast, contention and collision. In distance-based scheme, a node compares the distance between itself and each neighbouring node that has previously forwarded a given packet. In this scheme, a node upon reception of a broadcast packet for the first time initiates a RAD timer. Before the expiration of the RAD timer, the node checks the location of the senders of each received packet. If any sender is closer than a threshold distance value (D), the node will not rebroadcast the packet. Otherwise, the node rebroadcast it when the RAD expires. The algorithm for distance-based scheme is described as follows:
Algorithm: Distance-Based Scheme
Upon reception of a broadcast packet m at a node X for the first time
Initialize a RAD timer
Before the timer expires:
Check the location of the sender of packet m.
If the sender is closer than the threshold distance D
The packet m is dropped
Forward the packet m after the RAD expires
Here, a node using the distance-based scheme requires the knowledge of the geographical location of its neighbours in order to make a rebroadcast decision. This can be achieved by Global Positioning System (GPS) receiver, where nodes could include their location information in each packet transmitted. Although distance-based scheme achieve high reachability they suffer from high number of redundant broadcast packets because a node that has received a broadcast many a time may still rebroadcast the packet if all the neighbouring nodes transmission distances are greater than the threshold value.
126.96.36.199 Location-Based Scheme
Tseng et al (2002) have described the location-based scheme, where each node is expected to know its own position relative to the sender's position using geo-location technique such as GPS (Latiff et al 2005). Whenever a node originates or forwards a broadcast packet it adds its own location to the header of the packet. Upon the reception of a previously unseen packet, the node initiates a waiting timer and accumulates the coverage area that has been covered by the arrived packet. When the waiting timer expires, if the accumulated coverage area is larger than a threshold value, the node will not rebroadcast the packet. Otherwise, the node broadcast the packet. The operation of the location-based scheme is summarized as follows:
Algorithm: Location-Based Scheme
Upon reception of a broadcast packet m at a node X for the first time
Initiate a waiting timer(RAD)
Before the timer expires
Calculate the coverage area covered by the received packet m
When the waiting timer expires:
If the coverage area is larger than the threshold location L
The packet m is dropped
Forward the packet m
Deterministic scheme requires some sort of topological knowledge of the network to build a fixed backbone that guarantees full coverage of the network for a broadcast operation. The topological knowledge of the network is collected by maintaining information about nodes neighborhood via periodic exchange of hello packets. This deterministic scheme uses only a subset of nodes in the network to forward the broadcast packet. Williams and Camp (2002) referred to this category as neighbour knowledge-based algorithm. The descriptions of the various neighbour knowledge-based schemes are presented below:
1.7.7 Neighbour Knowledge Method
188.8.131.52 Flooding with Self-Pruning
Lim and Kim (2000) and Wu and Dai (2003) presented the simple neighbour knowledge-based method namely flooding with self-pruning. This protocol requires that each node have knowledge of its one-hop neighbours, which is obtained via periodic hello packets. A node includes its list of known neighbours in the header of each rebroadcast packet. A node receiving a broadcast packet compares its neighbour list to the sender's neighbour list. If the receiving node would not reach any additional nodes, it refrains from rebroadcasting; otherwise the node rebroadcasts the packet.
Figure 1.7 Self Pruning Approach
In Figure 1.7, after receiving a message from node 2, node 1 will rebroadcast the message to node 4 and node 3 as its only additional nodes. It is noted that node 5 also will rebroadcast the same message to node 4 as it's only additional node. In this situation still the message redundancy takes place in the network.
1.7.8 Forwarding Neighbour Schemes
In forwarding neighbours schemes, the forwarding status of each node is determined by its neighbours. Specifically, the sender proactively selects a subset of its 1-hop neighbours as forwarding nodes. The forwarding nodes are selected using a Connected Dominating Set (CDS) (Ivan et al 2002) algorithm and the identifiers (IDs) of the selected forwarding nodes are piggybacked on the broadcast packet as the forwarder list. Each designated forward node in turn designates its own list of forward nodes before forwarding the broadcast packet.
The Dominant Pruning algorithm is a typical example of the forwarding neighbour's schemes. Ideally, the number of forwarding nodes should be minimized to decrease the number of redundant transmissions. However, the optimal solution is NP-complete and requires that nodes know the entire topology of the network.
184.108.40.206 Scalable Broadcast Algorithm
Peng and Lu (2000) presented the Scalable Broadcast Algorithm (SBA). It requires that all nodes have kno