Improved Efficient Routing And Data Management 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.

This paper represent Virtual Cord Protocol, which take advantage of virtual Coordinates to provide efficient routing and data management in wireless sensor networks. VCP interconnecting all the nodes in the network. The operations of VCP are similar to a Distributed Hash Table (DHT), i.e. for inserting data fragments into sensor nodes and retrieving them. VCP uses two method for finding paths to nodes and associated data items. In the First case, the virtual cord always tends towards the destination. In second case, locally available nodes information is used for greedy routing. The routing performance of VCP, which clearly performs better than other ad hoc routing protocols such as Dynamic MANET on Demand (DYMO) or Virtual Ring Routing (VRR) and Ad Hoc on Demand Distance Vector (AODV). The simulation results show that VCP is able to find paths close to the shortest path with very low overhead. To improve failure handling, VCP is expanded with data replication mechanisms. This paper gives idea about proposed altenative solution for failure node management and Propose technique for Inter domain routing in cluster based, also explain different application using concept of VCP.

Keywords: - Virtual cord, data replication, data management, Virtual coordinates, sensor networks.

1. Introduction

Virtual coordinates is presently using for efficient routing in Wireless Sensor Networks (WSNs)[1][2]. With help of new technology, makes it possible to produce small size computing devices that can sense the surrounding environment. These devices are called sensor nodes. In general, WSNs provide an environment as like distributed systems. In this way, nodes are work as like to short out scalability problems. Additionally, WSNs have a resource limitation, that is way, so many sensor nodes with strong CPU, energy, and bandwidth restrictions need to be operated to construct stable and operational

networks. The last decades, discuss on wide variety of routing protocols has been developed in the field of sensor networks. Such as standard Mobile Ad Hoc

Network (MANET) protocols. And other is Ad Hoc on Demand Distance Vector (AODV), Dynamic MANET on Demand (DYMO), or Dynamic Source Routing (DSR). With the help of database technology such as data stream query processing, optimization can be achieved. Here, Distributed Hash Tables (DHTs) are successfully used to distribute data over a large number of peers and to find optimal paths toward these data [11]. The main concept work behind as like that, Data items are associated with numbers and each node in the network is responsible for a range of these numbers. Therefore, it is easy to find the node at which a data item is stored. Generally, DHTs are implemented on the application layer. This is underlying routing protocol that provides connectivity between the nodes. On the other hand, routing protocols that use geographic location like Greedy Perimeter Stateless Routing (GPSR) and Geographic Routing without Location Information (GRWLI) can perform well. Unfortunately, obtaining the location is not only costly and susceptible to localization errors, but sometimes even not feasible. Thus, greedy forwarding cannot guarantee reachability of all destinations because of possible dead ends. Mapping of geographic coordinates can be considered as a first step toward the use of virtual coordinates only. Also, hierarchical approaches using a mixture of geographical coordinates.This paper, present an improved version of our Virtual Cord Protocol (VCP), which directly using the advantages of virtual addressing schemes in WSNs [6]. Consider on two objectives, efficient routing toward clearly identified data items and fault tolerance with respect to frequent node failures. extended the protocol to support data replication on the virtual cord in order to improve the frequent node failures in the network. The VCP is a DHT like protocol that provides addition to standard DHT functions (e.g., insert, get, and delete) an efficient routing mechanism. The results demonstrate that the routing performance of VCP is similar to VRR in the optimal case, i.e., considering no node failures. However, in the case of node failures, VCP provides efficient cord management. VCP achieves much better tolerance to node failures Compared to VRR due to its low maintenance overhead.

2. Related Works

There has been a large amount of work on wireless routing protocols.In WSNs DHT-based approaches support for data management, which can be classified into three main categories real location-based, virtual location-based, and location independent. VCP used a virtual cord for efficient routing. It features a predefined hashing range allowing applications to clearly associate data items to places in the virtual cord. The main problem of this protocol is dead ends and the possibly inefficient routing. Short out of this problem have been investigated in a number of approaches. For example, the Visibility-Graph based Routing Protocol (VIGOR) uses a hierarchical approach relying on typical MANET protocols. This approach has been further extended to completely transfer in to virtual coordinates, by performing some coordinate transformation.

Geographical routing without location information (GRWLI) [3] [4] is one of the first virtual coordinate-based protocols. It makes an n-dimensional virtual coordinate system, which is based on finding the perimeter nodes and their locations instead of using real node locations. However, the drawback is virtual coordinates require a long time to converge. Hence, it consumes large amount of communication power. Again, the dead end problem may be exists, so the greedy forwarding algorithm cannot guarantee a path toward the final destination.

Virtual Ring Routing (VRR) [5] organizes the nodes into a virtual ring based on the order of increasing identifiers. So each node maintains a physical neighbour set with the identifiers of nodes it can communicate directly. The forwarding algorithm used by VRR is very simple. VRR chose the node closest to the destination from the routing table and forwards the message toward that node. The problem of such protocols is that the adjacent nodes in the virtual ring can be far away in the real network. As a result, forwarding to the nearest node can result in a very long path. Moreover, the scalability is a big issue when the network gets larger or increasing size of the routing tables.

The greedy spring improve the performance of greedy forwarding [14]. As like that, each node assigns itself an initial coordinate. Adjust each nodes their coordinates by simulating a system of springs and repulsion forces.

In case of hop id routing s [15], every node maintains a hop id, and using a multidimensional coordinate which based on the distance to some landmark nodes. Landmarks can be randomly selected in the network, that is provides better performance and to short out problem of dead ends. Selection of landmark follows as like that; firstly construct and maintain the hop id system, and one node floods the entire network to make a shortest path tree. Then, landmarks are selected. Finally, every node time to time updates our hop id and broadcasts it using a hello message. When greedy forwarding not short out dead ends, a landmark guided is designed and is used with an expanding ring search algorithm to route out of dead ends.

The unidirectional links has been investigated. [16]. the developed virtual coordinate assignment protocol (ABVCap_Uni) supports routing in sensor networks with unidirectional links, which using the availability of unique network IDs of all nodes. The protocol tries to put nodes with unidirectional links into rings and to treat a ring as an extended node. Routing is performed on virtual addresses assigned to real nodes and extended nodes.

Data-centric routing scheme based on a virtual polar coordinate.The virtual polar coordinate System (VPCS) which is used by Virtual Polar Coordinate Routing (VPCR) for routing. The problem is that when nodes or links fail, a large number of nodes in the systems need to reconstruct routing information. data-centric storage system that requires a tree construction for routing [17]. It takes help from landmarks that is used to direct packets in the routing process.

3. Working principle of virtual cord protocol

VCP connect all nodes on a virtual cord, it is based on the concept of DHTs and it was designed to be used in Wireless sensor network. It support both routing and Data management services. A hash function is used to create values in a predefined range (Start, End) and every node in the network maintains range. The routing has two concepts; First, the virtual cord path always tends to destination in the network.Second, greedy routing concern toward the destination by using available neighborhood information. The operation of VCP is given below.

(a) Joining of nodes

Recently implementation of VCP, a node joins the VCP network; it required three variables, its position, predecessor, and successor in the virtual cord. Every node finds out these values based on the positions of its hop-id neighbors. The hello messages are required to broadcasting, i.e. every node broadcasts a hello message periodically. Based on the hello messages, the joining node gets information about its physical neighbors and their adjacent nodes. At the start of network, one node must be pre-programmed as first node, i.e. initial position Start. The second node joining the network gets the largest number of this range i.e. End position. One by one, nodes joining, after all to discover the network structure, which means, all neighboring and adjacent nodes find out our position in the cord. The joining node sends a hello request message (hello-req) in VCP. This is response by the nodes that already joined the network; messages are broadcasted to all neighbors. To avoid collisions problem that can occur during the exchange of hello message, every node must wait a random period of time before starting to send the hello message. With the help of this massage acknowledgment, every node will get a unique position in the cord. Based upon the received hello messages, the joining node gets information about its physical neighbors and their adjacent nodes. In Fig.1, it shows that the joining process of nodes in network. The outer circle denotes the communication range of new joining node. In the first step, nodes are placed in the cord either at a start or end of the cord. One by one, other nodes connect to the cord.

Fig.1. Basic joining operation in VCP

Fig 2 Creation of a virtual node 6

The above figure shows that, node 5 has only one adjacent node. So the VCP creates a virtual node 6 to interconnect the nodes properly. The creation of virtual node is required to balance the cord, otherwise DHT, not work properly.

(b) Routing

Routing in VCP is using with help of the virtual cord. Additionally, local node neighborhood information is used for greedy routing. The greedy forwarding works as like that, a node with relative position, forwards a packet to its neighbors node. That has the closest virtual position to the destination. The forwarding is terminated if no more progress is possible. Based on the established cord, VCP routing will always lead to a path to the destination, and it is not possible to run into a dead end. VCP always try to take shortcuts path, whenever a physical neighbor with a virtual position number is available that is very closer to the destination. This is necessary, because vcp does not ensure for shortest path routing.

Fig.3. routing path using greedy routing along the virtual cord and using local neighborhood information.

above figure shows, the network that adding 10 nodes. In this example, node 1 has a message to transmit to node 15. Thus, it will forward the message toward the destination node via node 5, which has the closest position to the value among the physical neighbors. Afterward, node 5 will send it to node 10, and finally node 10 will forward it to node destination node 15.

(c) Node Failure Management

The VCP always try to tend node towards destination, only if there is no failure. It follow, greedy forwarding for routing. But, in case of node failures, greedy forwarding might fail and the cord becomes unstable. To avoid this type of problem, finding a path toward the destination in case of node failures, apply new scheme to find an alternative path. The hello messages are used to identify failed nodes. During packet routing, there are two cases in which greedy forwarding cannot reach the correct destination because of a dead end in the cord. In the first case, the failing node could be the final destination. In this case, the packet can be either dropped or stored within the neighbor of the failed node. In the second case, the failing node could be the next node toward the destination but not the final destination itself. In this case, apply different alternative path to find destination. In first alternative path, explain with example for packet forwarding in case of a node failure is shown in Fig. 4. In this example, node 10 is starting to send a data packet on destined address 25. As per, greedy routing principles of VCP, the data packet will be forwarded by nodes 11 and 12 until it reaches node 15. At this node, a dead end is detected because the already existing node 17 has failed. Thus, node15 will create a no path interval and, send a No Path (NP) packet back to node 12. Similarly, the NP packet is forwarded until it reaches node 13. According to the programmed rules, tries node 15 again, however, 15 detects a loop and sends a No path back (NPB) packet to node 13. In turn, node 13 tries to find another path by sending an NP packet to node 20. Finally, this node can resume greedy forwarding toward destination node 25.

Fig.4. Routing in the case of a node failure.

Propose solutions to find out different alternative path

Second alternative path, as above explain, at node 15. The next node is fail, then create virtual node 23. Forward the data packet, with the help of virtual node to destination node 25.

Third alternative path, as shown above figure it is clear that at node 15, next node fail. In this case, try to establish new link to fail node, after this, check the node is dead or alive. If the node 17, is dead then leave that path otherwise link to successor node and send data packet to destination node 25.

Fourth alternative path, as shown above figure, at node 15, create new link with neighboring successor node as like node 20, and forward packet to destination node 25. As shown in figure 4.

(d) Replication

Improve the reliability of VCP in the case of node failures, it follow, data replication techniques. Data Replication requires two ideal steps. First, it tells about the creation and maintenance of replica. Second, in the case of failures, available replicas should be recognized. It uses two ways to handling the failure of VCP. In first approach, one is the replica management in the physical neighborhood of a node. The main merit of this approach is the easy creation and maintenance of replicas. In this case of failures, the virtual cord can be used to find a node close to the original location. Then, a ring search can be performed, again, using broadcast messages, to identify a replica. The simplified creation and maintenance of replicas is accompanied by a slightly more expensive and time consuming ring search for available replicas. In a second approach, it gives the possibility to take advantage of available cord structure of VCP to maintain replicas along the cord. In this case, the amount of replicas must be controlled by storing duplicates on the n nearest nodes in each direction. At least 2n messages need for the creation and maintenance of replicas.

4. Routing performance of protocols

(a) Quality of Routing Paths

The qualities of the routing paths depend upon stretch ratio. To find out the stretch ratio, which is ratio between the length of the path move by VCP and the shortest path, i.e.

Stretch ratio = (length of the path by VCP) / (shortest path)

The stretch ratio slightly increases with the network size; this low stretch level selects the optimal path of VCP. This indicates that in VCP, messages are tends near optimal paths.

(b) Effect on the Network Size

The effect of network size on the performance of VCP. Every node in the network sends packets to the same destination, which simulates storing the same data item collected from all the sensor nodes in the network. The path length increases with the network size increases.

(c) Effect on the Traffic Load (for bursty and constant)

The behavior of this protocol under varying traffic load. Packets can be delayed at the MAC layer due to congestion. As a result, the end-to-end delay increases with increasing traffic load. The effect of increasing traffic was not so big on the packet delivery rate. The loss ratio was below 0.4 percent; therefore, the success rate was still above 99.6 percent. Repeat this experiment using a constant packet rate. The results are a little bit better than bursty traffic load.

5. VCP uses different Technique for routing and data management

(a) Cooperative Storage using VCP

The cooperative storage system that maximizes the usage of network storage [7]. In case of limited storage capacity nodes, using VCP. In this proposed scheme, each node maintains a Bloom filter-based compact list of the inserted data; it required storage record in a particular track.

Follow only successor node

Follow successor and predecessor node

Fig.5. VCP-based cooperative storage: Ring disabled (up) and Ring enabled (Bottom)

Nodes are the successors and predecessors on the cord. This way, if the storage capacity of a node is full, this node can send new data messages to either its successor or its predecessor node. If the storage capacity of successor and predecessors reached its limits, it can send the new data items to its own successor until reaching a node that can store the data item. Recall that successors (and predecessors) of a node are located in the same environment. In this case, either the cord as a ring (ring enabled) or simply drop the packets (ring disabled). If the ring is enabled, the successor of the end node is the node at the start of the cord, which shown red color in figure. If it follow predecessor node, then firstly it send data packet to end node. After this end node send packet to its predecessor node, shown in blue color. In the case of ring disable only follow successor node. If packet reached at end node then stop process. As shown in figure 5.

(b) Inter-Domain Routing in VCP

The inter-domain routing is provides adequate paths. The two networks are works separately, for example security, privacy, or search efficiency reasons, other different applications in the same region may be kept in two virtual networks [8]. The inter-domain routing necessary for efficient communication to different network [8].

VCP domain A VCP domain B

Fig.6. VCP inter-domain routing example

In this situation, the periodically exchanged hello messages. Node also contains the domain ID. If two networks are come close to each other’s communication range. Node receiving hello messages from other domain, this node automatically becomes a gateway node; more than one gateway node is possible which depends on node come close to each other in communication range. After this, all information about other domain node is stores into the local DHT. If the gateway node no receives long time hello messages from the detected domain node, it removes the gateway information from the local DHT. This way, the local DHT always contains the most updated gateway information and routing between neighboring domains. When a node wants to send a packet to another domain, it pulls the gateway address from the DHT and then forwards the message via the gateway node.

(c) Head-to-head connection with Cluster based in VCP

The VCP algorithm is apply with the technique of clusters based, all the advantages of VCP using in this technique. The cord establishment with help of virtual nodes coordinates, in this algorithm, only selected as the head nodes have the right to connect in the cord. First, select group of node which is called cluster. Every group has a predetermined node called head node. The communication radius of each head cluster node must be such as to communicate with at least two neighboring head nodes. This is required for connection to virtual cord of the VCP. Since the VCP algorithm operates only on the head nodes [10].

Fig.7. Network node according to the modified protocol VCP

(d) Propose technique: - Inter domain routing in cluster based.

The cluster based network provides cord to connect virtual node. In this situation, apply concept of inter domain routing, then more than one cluster based network are connect, so the storage capacity as well as improves routing algorithm. When nodes come to same communication range, then node send the message to other node. This event occurs through gateway node and information is storage in local DHT. Only head (cluster) node connects to code and send data packet to other head node. As shown in figure 8.

VCP domain A VCP domain B

Fig.8. Network node according to the modified protocol VCP

6 Challenges

(a) VCP includes further research on handling of node failures and rejoining partitioned networks.

(b) Future work includes studies of the suitability of different hash functions for content replication in sensor networks.

(c) VCP Does not ensure shortest path routing.


Virtual Cord Protocol is a routing protocol designed for efficient data management in sensor networks. VCP exploits the benefits of using virtual coordinates for efficient routing. Using application-specific hash functions, data Items can be associated with particular nodes. Furthermore, the protocol supports data replication in order to improve the failure performance. The VCP also gives idea for enhance storage capacity of node, with the help of inter domain concept. Extended storage capacity with help of cluster concept as well as cluster with inter domain.

Virtual cord protocol

Provides efficient routing in sensor networks

Developed for almost stationary networks

Low overhead + small stretch ratio

Provides efficient storage capacity of node