Nodes Moving In Different Directions And Speeds Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A mobile ad hoc network is a collection of mobile nodes that dynamically form a network without any infrastructure or pre-defined topology. Mobile nodes are continuously moving in different direction with different speed. In this network environment, each node acts as an information source as well as a router to spread packets to its neighbors. The network is fully autonomous and can be formed at any time and also can be changed. It is characterized by limited battery power, limited bandwidth, frequent network topology changes, and rapid mobility. The topology of the network changes with time as a result of mobility of nodes. Nodes may also enter or leave the network.

Figure.2.1 An ad hoc network with nodes moving in different directions and speeds

MANETs have many salient features such as dynamic topology, bandwidth constrained applications, energy constrained operations and limited physical security.

1 Dynamic Topology

In MANET, the movement of the nodes is random and hence the topology of the network may change arbitrarily and rapidly at unpredictable times.

2 Bandwidth Constrained applications

In the MANET, Nodes are having limited bandwidth constrained and have lower link capacity than the traditional wired networks. The maximum transmission rate of a node is always lowered because of various factors in the network like multiple access, noise, fading and interference etc.

3 Energy Constrained Operations

Some or all of the nodes in a MANET may rely on batteries or other exhaustible resources for their energy. For these nodes, the operations should have optimized design criteria for conserving energy.

4 Limited Physical Security

Mobile ad hoc Network is more vulnerable to security threats than the traditional wired network. The attacks such as eavesdropping, spoofing and denial of service are rapidly growing and must be taken into consideration. Some of the security techniques existing for the wired network are also applied to the MANET for reducing the threats. In MANET, the decentralized nature of the network topology helps the network to be more robust against single point of failure that is often occurred in a wired network. The task of making a network scalable and preventing it against the security threats at the same time is very complex.

3.1 Performance metrics

Below are some of the most used metrics used to give a proper view of the performance of the ad hoc routing protocols under various environments via simulations. Conclusions are inferred after the evaluation of these metrics to improve the existing protocols.

1 Protocol Efficiency/ Successful packets delivery (in percentage)

The fraction of successful received packets, which survive while finding its destination. This metric also determines the completeness and correctness of the routing protocol.

2 Routing Overhead

The ratio of routing and control packets to the total number of packets.

3 Normalized Routing Load

The number of routing & control packets transmitted per data packet delivered at the destination.

4 Bandwidth

During discovery or routing related information flow, the protocol uses the available bandwidth. Control packets may not be consuming large amount of bandwidth, but they may be too much to interfere with the transmissions.

5 Throughput

The rate of successfully transmitted data per second in the network during the simulation

6 Average network delay

Average end-to-end delay of talking parties in simulation.

3.2 Factors Influencing Protocol Performance

There are various factors influencing routing protocol performance in a mobile ad hoc network due to absence of a fixed infrastructure and mobility of nodes. Some of those factors influencing that effect the performance of mobile ad hoc network are following:

1 Mobility Pattern

Mobility pattern determines the performance of the protocol. Mobility pattern may significantly contribute to vary network results. Different mobility patterns impact links, and routes stability, that obviously have an effect on the overall network performance.

2 Environmental Factors

This factor is related to the node density. If area shape is more rectangular, it leads to longer routes. Additionally, the topological characteristics of the environment also affect the performance.

3 Network Environment Parameter

The network context has a strong impact on the performance of routing protocols. The essential network parameters include network size i.e. presented as number of nodes; connectivity i.e. the average degree of a node, normally presented as number of neighbors; mobility i.e. the topology of the network, relative position and speed of the nodes; and lastly link capacity i.e. bandwidth and bit error rate (BER).

4 Radio Range

The propagation model and transmission power determines the received signal power of each packet. The packet cannot be correctly received if the received power is below a receive power threshold.

5 Amount of deviation from optimal path, in hop counts

Optimal path is normally defined by shortest hop to destination. The path routing protocol made packet traverse through may not be optimal. At that instant, we can observe the difference between the non-optimal and optimal hop counts, and give an average deviation for optimality.

Clustering in Mobile Ad hoc Network

Routing is challenging in Mobile Ad hoc Network due to the dynamic nature of the network topology because of mobility characteristics of nodes. There is a well-known method to reduce the amount of routing data exchanges and accordingly, to save the communication bandwidth and energy that method is clustering.

Table 2.1 Impact of clustering on protocol performance


Transport Protocol


Since routing and MAC protocol performances improve, transport protocol performance improves.


Cluster based routing incurs lower control signaling overhead and results in improved system performance.


Clustering allows efficient channel resource management and battery power usage.

Clustering is the process of dividing the nodes of a network into a few organized partitions called clusters. Clustering creates a backbone network of nodes, providing scalability for large networks, and stability for dynamic networks.

The objectives of clustering are to minimize the total transmission power aggregated over the nodes in the selected path, and to balance the load among the nodes for prolonging the network lifetime. Clustering is a sample of layered protocols in which a network is composed of several clusters of mobile nodes.

In a cluster-based environment, there are some nodes in the network called cluster-heads which have high processing speed and battery power than the other nodes.

These cluster-heads are responsible for cluster management and maintenance of the network.

A cluster-head allocates the resources to all the nodes that belong to its cluster. In addition to controlling and managing its own cluster, it also communicates with other clusters. It maintains the information about every node within its cluster. Therefore, choosing the appropriate number of cluster-heads that can use the network resources efficiently and adapt to the changing network conditions in MANETs is a challenging task. Choosing optimal number of cluster-heads is an NP-complete problem.

Clustering is a method of organizing things into meaningful groups with respect to their similarities. Elements in a group are similar to each other but are different from other groups.

The clustering also identifies the groups in such a way that the identified groups are exclusive so that any instance belongs to a single group. It is very similar to a graph partitioning problem. Optimally portioning a graph is an NP-hard problem with respect to certain parameters. First, we find the cluster-head and then neighbors of the cluster-head. The neighborhood of a cluster-head is the set of nodes that lie within its transmission range. The set S is called a dominating set in which every vertex of the graph belongs to S or has a neighbor in S. The set of cluster-heads is called the dominating set of the graph. Due to mobility of the network, the nodes can go outside the transmission range of their cluster-head and move into another cluster thus changing their neighborhood. This can change the number of clusters and number of nodes in a cluster but this does not result in a change of the dominant set at all. Clustering of nodes in MANETs is one of the biggest challenges. Finding the optimal number of clusters that cover the entire network becomes essential and an active area of research. Although, several authors have proposed different techniques to find the optimal number of clusters, none of them addresses all the parameters of a mobile ad hoc network. Clustering has several advantages in MANETs. The system performance can be improved by allowing the reuse of resources due to clustering because each group of nodes can communicate with each other without affecting the other groups. Secondly, it optimally manages the network topology by dividing the task among specified nodes called cluster-heads, which is very useful for network management and routing.

There are some requirements of clustering in MANETs. The clustering algorithm must be distributed, since every node in the network has only local knowledge and communicates outside its group only through its cluster-head as in case of cluster-based routing. The algorithm should be robust as the network size increases or decreases; it should be able to adapt to all the changes. The clusters should be reasonably efficient i.e. the selected clusterheads should cover a large number of nodes as much as possible.

Nodes in a cluster must be one of the following types:

1. Clusterhead (CH): An elected node that acts as the local controller for the cluster. The clusterhead's responsibilities may include: routing, relaying of inter-cluster traffic from cluster members, scheduling of intra-cluster traffic, and channel assignment for cluster members.

2. Cluster Member: A normal node belonging to a cluster. Cluster members usually do not participate in routing, and they are not involved in inter-cluster communication.

3. Gateway Node (CG): Cluster Gateway is a border node which is used to convey the routing information from one cluster to another. The clusterheads and gate way nodes form the backbone network. Gateway nodes selected among the border nodes. A border node is a mobile node which has at least one neighbor belonging to a different cluster. Border nodes are at the perimeter of the clusters.

Clustering in MANETs reduces congestion and increases the stability of dynamic networks. The cluster members don't participate in route establishment, thus the overall packet flooding is greatly reduced. In mobile networks with highly dynamic topologies, clustering can increase network stability. If clusters are designed and maintained with mobility in mind, then intra-cluster relative mobility can be minimized. This increased stability leads to more constant routes. In addition, changes to the network topology (a node joining or leaving) have a smaller impact on routing in a clustered network.

Advantages of Clustering

Clustering in Ad Hoc networks has many advantages compared to the traditional networks. They are as follows:

1. It allows the better performance of the protocol for the Medium Access Control (MAC) layer by improving the spatial reuse, throughput, scalability and power consumption.

2. It helps to improve routing at the network layer by reducing the size of the routing tables.

3. It decreases transmission overhead by updating the routing tables after topological changes occur.

4. It helps to aggregate topology information as the nodes of a cluster are smaller when compared to the nodes of entire network. Here each node stores only a fraction of the total network routing information.

5. It saves energy and communication bandwidth in ad-hoc networks.

Issues of Clustering

The highly dynamic and unstable nature of MANET’s makes it difficult for the Cluster based routing protocol to divide a mobile network into clusters and determination of cluster heads for each cluster. Clustering reduces communication and control overheads due to pre determined paths of communication through cluster heads. It is vital for scalability of media access protocols, routing protocols and the security infrastructure. Routing protocols which considers only bidirectional links may have link asymmetry due inefficient or abnormal routing. Untapped network capacity is represented by the undiscovered unidirectional links, which reduces the network connectivity.

A large number of mobile terminals are managed by a MANET using a cluster topology. The construction and maintenance of a cluster structure requires additional cost compared with a topology control without cluster.

Clustering has some side effects and drawbacks. Some of those are listed below:

1. The maintenance cost for a large and dynamic mobile network requires explicit message exchange between mobile node pairs. As the network topology changes quickly and concerns many mobile nodes, the number of information message exchange grows to reach a critical point. This information exchange consumes a lot of network bandwidth and energy in mobile nodes.

2. A ripple effect of re-clustering occurs if any local events take place like the movement or the death of a mobile node, as a result it may lead to the re-election of a new cluster-head. When a new cluster-head is re-elected it may cause re-elections in the whole of the cluster structure. Thus, the performance of upper-layer protocols is affected by the ripple effect of re-clustering.

3. The major drawback of clustering in MANETs is that some mobile nodes consume more power when compared to others nodes of the same cluster. As special node like a cluster-head or a cluster-gateway manage and forward all messages of the local cluster their power consumption will be high compared to ordinary nodes. It may cause untimely shutdown of nodes.

Table 2.2 Evaluation Criteria for Clustering Algorithms

Message complexity

Number of signaling messages is required to form clusters and to decide which node will become clusterhead?

Time complexity

How long time will take the algorithm after a change in the topology to reâ€"create a valid cluster structure?

Load on nodes

How to change the traffic and processing load on nodes using a hierarchical group (e.g., link state advertisements, route computations, topology aggregation)?

Routing table size and routing optimality

The number of routing entries (compared to a flat routing) is reduced by a hierarchical network representation. However, the number of alternative paths available is smaller, and the information about remote network areas is blurred.

Cluster stability

How stable does the clustering algorithms maintain the cluster structure while changing network topology?

Level of adaptability

How adaptive is the algorithm with changes in the network? Which parameters are adaptive?

Decision speed

How much a node is dependent on the knowledge of its neighbors making a decision about its role?

Since our clustering technique aims to be used in wireless mobile ad-hoc environments that support multipoint communication among nodes that demonstrate group-oriented mobility patterns and tend to coordinate their movements, in this paper we introduce the concept of relative mobility, in order to characterize the degree of mobility a node exhibits with respect to its peers for a given period of time. A node with high relative mobility is more prone to unstable behavior than a node with less relative mobility and therefore should not be elected as clusterhead. A node may compute its relative mobility by exchanging its mobility profile with current and potential peer nodes. As a node moves, its relative mobility may also change. Therefore the relative mobility of a node must be periodically reevaluated to allow for adaptation to future states of the network. In the following let us denote by v(m, t), the velocity vector of node m and v(n, t), the velocity vector of node n at time t. The relative velocity v(m, n, t) between nodes m and n at time t is defined as:

V(m,n, t) = v(m, t)- v(n, t)