# Represent Time State That The Node 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.

In general the ad hoc networks are represented through undirected graph. In our work we considered the graph G as. Here, E and V denote the set of undirected links and set of nodes in the network respectively. The nodes in the ad hoc network are detected using its unique identity and represents a host having a communication range of R, and has huge storage space. The speed and direction of each node in the network changes randomly. The link (i, j) represents that there exists a wireless communication link among the nodes (i, j). This link is formed only when the nodes i and j are with the communication range of each other. The link (i, j) is detached from E when the nodes i and j moves away from the transmission range.

FSR is a proactive protocol, which has three tables and one list for all the nodes in the network.

List: Neighbor List termed

Tables:

Distance table

Topology table

Next hop table

The neighbor list consists of nodes that are that are adjacent to the node i. For all the destination nodes a topology table is maintained. For example, the destination j has an entry in the table . This consists of two different parts that are as follows.

Express the link state information reported by a node j.

Represent time state that the node j has generated the link state information at node j.

Similarly, is used to denote the nodes that are used to forward the packets to the next hop to the desired destination through the shortest path. The distance between the nodes i and j is presented in the distance table . In addition to this list and table a bandwidth function is used. The bandwidth function can be represented in through the equation 1.

(1)

Equation 1 is used to manipulate the link's distance. This function in our network returns 1, if direct communication and high bandwidth among the nodes exist. If there is no direct communication then it returns ∞. This parameter can be changed depending on the requirement of routing protocol.

FSR is a hierarchical routing protocol, which uses the fisheye technique that reduces the information size needed to denote the graphical data. Deep knowledge about the nodes that are closer to the focal point is presented in the specified node. As the distance are higher the details will we lesser[40]. This denotes that the details of the nodes are inversely proportional to the distance of the node. Accurate distance and path information are maintained for the immediate neighbors. This protocol will not flood the state of the links. On the other hand each node maintains the list and exchanges the list with its immediate neighbors alone. This exchange process replaces the larger sequence table entries with the number that is of smaller sequence. Based on the sequence number or the time tamp of a node the is updated. The distance vector is propagated in FSR. However, all the nodes contain the detailed full topology map of the network. Depending on the topology map the shortest path to reach the destination node is determined.

In the wireless network the communication link between the nodes is frequently destructed or constructed. The exchange of topology information is not periodic rather it is event driven. This event driven technique highly reduces the overhead of control packets. The updating process becomes tedious when the network size grows larger since it requires huge part of bandwidth that depends on the period of updating. To reduce this overhead without disturbing the routing function, it uses fisheye technique. The application of fisheye in mobile ad hoc network can be studied through an example. Consider the Figure 2.35, which contains various shades of gray color to define the scope of fisheye with respect to the center node. Each scope has a set of nodes, which are reached within a given number of hops. In Figure 2.35, we have shown three different scopes for 1, 2 and &gt;2 hops respectively. The 1-hop nodes are colored green, 2-hop nodes are colored blue and the nodes that can be reached greater than 2 are colored using white. The scope level and radius are based on the network size.

The exchange periods are varied for different entries in the table of routing. With this we can reduce the routing overhead. The details of the nodes that are within smaller scope are entered and updated at higher frequency. Figure 2.36, illustrates this scenario of message reduction technique of Fisheye. The higher frequency is highlighted in the Figure 2.36. The bolded part is considered to have higher frequency where other nodes have low frequency. Whereas, other entries are sent at lower frequency, which compresses considerable link state updates update thereby reduces the message size. This generates timely update for the nearer node and latency for the nodes that are far away is higher. The best path for the destination nodes that are located far away from the source is compensated since the route is more accurate when the packets reach the nodes that are nearer to the destination. To reduce the overhead for larger network a plan named graded frequency update is used across the multiple scope.

## Figure 2.35: Scope of Fisheye Technique

Global State Routing (GSR) is the origin for FSR. In GSR, only one scope for fisheye is presented and the radius of the scope is considered as ∞. In which the topology map containing entire details are exchanged among neighbor. This method uses maximum bandwidth as the size of network increases. As FSR uses different frequency for different scope it scales well even for larger network without disturbing the accuracy in computing route while the destination is nearer. As it maintains the routing entry for the destination, FSR avoids the explicit detection of destination that helps to maintain low signal packet transmission latency. Routes to the remote destination become less accurate when the mobility increases. Nevertheless, as the packet are nearer to the destination the accuracy of route information increases and perfect route instructions are detected as it enters the scope with higher refreshing rate.

## Figure 2.36: Message Reduction in FSR

The working of the FSR is described as follows. The nodes in the network start with the empty topology tablethe empty neighbor list. Once the node is configured in the network successfully, it learns about the neighbors. In the algorithm the NodeInit (i) is used to gather and collect the information about its neighbors. The PktProcess (i, pkt) procedure is used to process the received message regarding routing. After processing the routing messages, node i, re-builds the routing table depending on the newly manipulated topology table. The state of the link is exchanged with its neighbor. RoutingUpdate (i) scans through the topology table based on the entries in the distance table between the nodes x and i.

Likewise the FindSP (i) producer finds the shortest path tree rooted at i to create the tree. The node i, starts with, and continues till . The iterations are used to search the node j such that node j reduces the value of , where and . If the node j is detected; P is augmented with j, is assigned to and is assigned to. As a result, the shortest path beginning from i to j has to go all through k, descendant for i to j is the same descendant for i to k.

## 2.3.4 Hybrid Routing Component (ZRP)

The best parts of both proactive and reactive protocols are taken to construct a hybrid protocol named ZRP. This protocol is classified as hybrid proactive/reactive routing protocol. Usually maximum traffic exists at the nodes that are nearer. Separation of nodes that are locally neighbors from the global topology of the complete network allows for applying various approaches. The local neighbors are grouped together to form zones. Therefore, the ZRP decreases the proactive scope to a zone focused on every node. In such a limited zone, it is much easier to maintain the routing information. On the other hand, nodes that are far away are reached using the reactive protocol. With this it is possible to enquire the route to reach destination can be easily found without querying all the nodes of the network. ZRP has adaptive behavior. This depends on the present structure of the network and user's behavior. For each node a routing zone is defined along with the radius r, which is expressed in terms of hops. An example for ZRP is illustrated in the figure 2.37. In the figure the zone is formed with the radius of two hop nodes for the node 0. From the figure 1 it is explicit the routing zone of node 0 contains the node from 1-10, but not 11. Since the node 11 can be reached only at three hops.

## Figure 2.37: ZRP with r=2

The nodes inside a zone can be classified into two types of nodes as follows.

Interior nodes: The nodes whose distance are less than r. In the above example 1-6 are considered as interior nodes that are colored yellow.

Peripheral node: The nodes those are located exactly at a distance of r. In the above example the nodes are from 7-10, which is colored as green are called peripheral nodes.

## Figure 2.38: Block diagram of ZRP

Transmission power can be used to regulate the number of nodes in a given zone. If the number of nodes should be increased then the transmission power of a node can be increased and if the number of nodes should be decreased then the transmission power should be decreased. The figure 2.38 describes the block diagram of ZRP. Redundancy and reachability can be of the zone is depend on the number of neighboring nodes. If the coverage area is larger then it becomes hard to update the traffic information. There are two routing components in ZRP as mention below.

IntrA-zone Routing Protocol (IARP): It is locally proactive, which a family of restricted depth, proactive link-state routing protocols. It maintains the route information of the nodes that are within the zone.

IntEr-zone Routing Protocol (IERP): It is globally reactive, which provides enhanced route discovery and maintenance service depending on local connectivity that is supervised by IARP.

The local zone topology is known, which can be used to minimize the traffic when global route discovery is need. ZRP uses bordercasting technique is used to direct request of query to the border of the zone. This service is offered by the Bordercast Resolution Protocol (BRP). A bordercast tree is constructed depending on the maps of extended routing zone. ZRP uses Neighbor Discovery Protocol (NDP) to discover the link failure and new neighbor node. At regular intervals the NDP transmits the HELLO packets. On receiving the HELLO packet the tables of neighbors are updated. The nodes that have not received the beacon signal within a specific time are removed from the table. NDP triggers the route updates and alters IARP when the neighbor table is updated. To respond the route queries the IERP use the routing table of IARP. It also forwards the queries with BRP.

Initially, the node that needs to send the message packet will check the location of the destination node. If the receiving node falls with the zone of sender node then it uses the route information from the IARP. In this case the packets are delivered proactively. Likewise, if the destination node falls outside the zone region then it uses the reactive protocol for routing. The process of reactive routing is divided into two major phases.

Route Request

The sender node sends the route request to the peripheral node through BRP. If the receiving node knows the destination then it replies using the route reply packet. Otherwise, the broadcast of route request packet is continued. The reply packet contains the route to the destination node. This routing information can be recorded in two ways.

Route Request packet

Next-hop addresses in the node along the packet

The bordercasting node transmit route request packet to its peripheral nodes during bordercasting process. This type of transmission can be implemented as multicast in order to reduce the resource usage. The nodes in the zone should maintain the extended routing zone with the radius of 2r-1 hops. To maintain the route ZRP uses the knowledge of local topology. Sub-optimal route segments and link failure with a zone can be bypassed. Packets forwarded towards the broken link are redirected around the active multi-hop path. To shorten the route, the topology can be used. For example consider the Figure 2.39. In that the source node 0 and destination node 22 are highlighted using blue color. The source node needs to send a packet to the node 22. Node 0 searches inside its own zone using the IARP information. As there is no information regarding the destination node 22, the source node sends a route request packet to the boundary nodes namely 7, 8, 9, and 10. These nodes search their routing table for node 22. As these nodes do not have the information it broadcast the information to their peripheral nodes. In the example, node 9's broadcast alone is shown. The routing zone of node 9 is shown in the figure 2.40. Further the packets are broadcasted from the peripheral nodes of node 9. The peripheral nodes of node 9 are 0, 4, 6, 16, 17, and 18. These nodes search the routing table for finding the destination node. As the routing table of 18 contains the destination node 22, it replies the route to the source node through route reply packet. The zone area of 18 is as shown in figure 2.41.

## Figure 2.41: Node 18's routing zone

In this way the node 0 finds the route for node 22 to send the packet using the ZRP protocol.

In the routing zone, each node periodically exchanges IARP message including the routing table of each node in order to update the network topology and calculate the shortest path.

The IERP messages are based on the query/reply mechanism, which are used to find out and maintain routes to source and destination nodes that are beyond a node's routing zone. ZRP nodes use source routes accumulated in the IERP packets and cached routes stored in ZRP nodes. The cached routes in ZRP nodes provide a faster response to find out the destination, because queries are terminated before reaching the query destination based on the cached routes of node which finds the query destination. The Query Extension can be implemented for the node which reported cached routes to inform the destination about getting the reverse path towards the source. The requested Quality of Service (QoS) may need the explicit source route to propagate the QoS packets, which is provided by the source route mechanism from the IERP packets. The type in IERP packet indicates the type of IERP packet which can be Route Query, Query Extension or Route Reply. TTL shows the number of hops that a Route Query may continue to propagate. Hop count indicates the hop count from the source to the current node in Route Query, Query Extension messages or the hop count from the source to route destination in Route Reply, Route Accumulation and Route Optimization messages. Figure 2.38 comprises the functional description of zone routing protocol.

2.4PROVIDING QUALITY OF SERVICE FOR MOBILE AD-HOC NETWORKS

This chapter proposed a new method which delivers high throughput and less end to end delay while comparing with the routing protocols individually. The method incorporated the three types of routing protocol viz proactive, reactive and hybrid protocols in the same network at same time which is named as Consecutive Routing Process (CRP) and random early detection method was proposed to avoid congestion control. For the same network the protocols were tested for each protocol separately and their comparisons also were analyzed.

By observing the results it is clear that the new method delivers high throughput and packet delivery fraction while the end to end delay and jitter delivers very less compared with each routing protocols separately. The proactive routing protocol Fisheye delivers high delay and jitter with low throughput. DYMO reactive protocol delivers high throughput and packet delivery fraction next to the new proposed method. From the result analysis we can conclude that comparing with other protocols the new method delivers high throughput and packet delivery fraction with low delay and jitter. If the speed increases the mobility partition also increases. Likewise the speed of mobility increases as the number of events increases.

## 2.5 SUMMARY

MANET plays an important role in wireless communication. The various routing protocols like reactive, proactive and hybrid possesses great advantages in MANET. DYMO reactive protocol delivers high throughput and packet delivery fraction when compared to other existing protocols. Chapter 3 evaluates and performs comparative study to find out each protocols performance. Our proposed system works well for both large and small scale networks in Mobile ad hoc environment.