Represent Time State That The Node Computer Science

Add: 22-11-2017, 19:12   /   Views: 116

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


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.


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 >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.

013245THOP0:{1}21:{0, 2, 3}12:{5, 1, 4}23:{1, 4}04:{5, 2, 3}15:{2, 4}2THOP0:{1}21:{0, 2, 3}22:{5, 1, 4}13:{1, 4}14:{5, 2, 3}05:{2, 4}1THOP0:{1}11:{0, 2, 3}02:{5, 1, 4}13:{1, 4}14:{5, 2, 3}25:{2, 4}2Figure 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.