Multi Convex Hull Tree Based Geographic Routing without Planarization in Wireless Sensor Networks

Multi Convex Hull Tree Based Geographic Routing without Planarization in Wireless Sensor Networks

A. S. Nithya

1. Phil Research Scholar: Computer Science, Government Arts. College,

   Coimbatore, India.

   Dr. K. Saraswathi

   Asst. Professor of Computer Science, Government Arts. College, Coimbatore, India.

   Abstract Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. The most of the existing system using position information to route the packet. One of the existing protocol GOR(geographic opportunistic routing) schemes typically involve as many as existing next-hop neighbors into the locally based forwarding and give the nodes closer to the destination higher relay priorities. The drawbacks of existing take more delay. The proposed routing protocol based on multi- hull tree used for neighbors of the sender node overhears the transmission and formed multiple hops from source to the destination for transfer of the packet. In this paper using hull tree algorithm and GDSTR switches to routing on a multi -hull tree instead of a planar graph when packets end up at dead ends during greedy forwarding and avoid looping the packet. GDSTR node maintains a summary of the area covered by the sub-tree below each of its tree neighbors using convex hulls. It achieves better routing performance with low delay than existing opportunistic based geographic routing algorithms.

   Keywords Wireless sensor networks; Tree; Geographic Opportunistic Routing; Hull Trees.

   1. INTRODUCTION

      There are various approaches, such as single-path, multi- path and flooding-based strategies. Most single-path strategies rely on two techniques: greedy forwarding and face routing. Greedy forwarding tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. The most suitable neighbor can be the one who minimizes the distance to the destination in each step (Greedy). Alternatively, one can consider another notion of progress, namely the projected distance on the source-destination-line, or the minimum angle between neighbor and destination (Compass Routing). A most favorable routing protocol for WNs based on multi-hop path rapidly, avoid traffic congestion, and if the network scale increases [1]. The conventional approach to route traffic in WNs is to assume shortest path routing techniques which are similar to the methods used in existing wired networks. While these techniques are effective only in wired networks, where a

      transmission link is either successful or failed, they cannot handle with the unreliable or unpredicted medium of wireless networks. The existing opportunistic routing [2, 3, 4, 5] is a novel research area for wireless networks to deal with the trustless standard. Opportunistic routing broadcasts packets initially and then chooses the next hop receiver based on which neighbor has the shortest form.

      Most of the previous works do not provide an efficient tree- based routing to work in large scale networks. The cause is that the coordination overhead increases as the network scale does. In this paper, author proposed geographic probabilistic routing (GPR), a novel opportunistic routing workings well in large -scale networks, but it take more time to take reach the destination. In this paper preventing ACK lost, GPR analysis, that missing ACK message is predictable in wireless networks and estimates the likelihood at which this state would happen. GPR is based on the geographic routing since the geographic distance a packet moved forward can be simply and clearly weighed.

      An additional problem of existing geographic routing techniques relies on the idea that the network is connected, that is, there is an end-to-end path between any sources to destination. However, node mobility, node sparseness or the broadcast variations could lead to situations where the network is disconnected. Under this situation, existing geographic routing protocols are unable to work. But the communication could be effective if intermediate nodes store the message to send and they get connected to the final destination in a near future.

      Two important issues of opportunistic routing are forwarding candidates selection and relay priority assignment. Several variants of opportunistic routing [6] leverage the location information of nodes to select forwarding candidates and prioritize them. For example, in

      [7] paper, all the available next-hop neighbors that are nearer than the sender to the destination are selected as the candidates and the nodes closer to the destination are given higher relay priorities.

      Another existing protocol like energy efficient opportunistic routing is one of the multi hops routing protocol for wireless sensor networks. It makes use of the forwarders list of the node to choose the forwarding node to transfer the data towards the target. Priorities are assigned for

      the neighbors of a node to choose the forwarding node. Parameters analyzed for the network of interest are Energy consumption, packet loss ratio, and delivery delay. Efficient protocols are required to reduce delay in transmission and to prolong the network lifetime. EEOR [8] protocol gives better results compared to EXOR [9] protocol in terms of packet loss ratio, average delivery delay, and energy consumption.

   2. RELATED WORK

      Opportunistic based routing protocol aims to improve wireless performance by exploiting spatial range in dense wireless networks [10]. A many of opportunistic routing protocols have been proposed [11-14] in the literature. Geographic opportunistic routing [15] is a branch of the opportunistic routing, where location information is available at each node. Opportunistic routing work at the network layer a set of forwarding node are selected while at the MAC layer only one node is chosen as the actual relay node based on the reception results in an a posteriori manner.

      S. Biswas (2005) used to improve the basic EXOR forward scheme [9] that named as EXOR version 2. It severely schedules the routers access to the medium before a batch of packets is broadcast by the source. ExOR-2 uses the batch of packet map to record which packets each node has received and diffuse it with the data packets; every relay node only forwards the packets that have not been acknowledged by nodes closer to destination. ExOR2 reduce the duplicated transmissions and provide significant throughput enhancement. But, supporting multiple simultaneous flows is still some problem in ExOR-2.

      Another geographic routing protocol SOAR (simple opportunistic adaptive routing) [16] introduced the priority based packet forwarding techniques to avoid duplicate transmissions. It spreads ACK message in the network in a despicable way to limit duplications and improves the throughput significantly. In SOAR, there must be more intra- flow interfering for the relay nodes when there are multiple packets transmitted between the particular source-destination pair.

      Another geographic routing protocol MORE (Most opportunity based on radius energy) [17] combines network coded and opportunistic routing to support multiple simultaneous flows path. In MORE protocol, the source node creates random linear combinations of packets and broadcasts and coded packets continually. The relay nodes combine the independent packets and forward thm. The destination sends an ACK message to the source along the shortest path when it can decode the independent packets. The most of existing system relay only in duplicate transmission.

   3. PROPOSED APPROACH

The aim of proposed routing protocols is to improve the performance of wireless sensor networks based on tree- based routing. The hull tree technique is important parameters, to be improved are the lifetime of the network, the delay in transmission and the network throughput.

The proposed algorithm is to efficient way to reduce the energy consumed by the sensor nodes in receiving, transmitting of information and to decrease the delay in transmission of data from source to destination in a wireless sensor network.

The following steps in the wireless sensor networks considered:

1. Initially all node is static.

2. The uniform topology is deployed.

3. All the wireless sensor node has same initial energy.

4. The data generation in the network is uniform.

5. Given a network of nodes with no location information, assign coordinates to the nodes to maximize the greedy forwarding success rate of the network.

This algorithm choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the multi- sub-tree below each of its tree neighbors. While GDSTR requires only multi- tree for correctness, it use loop – free routing.

1. Multi Greedy Distributed Spanning Tree Routing (GDSTR)

   The GDSTR is able to guarantee the delivery of packets in a connected network is that the tree traversal forwarding mode is guaranteed to deliver the packet to any node in the routing based on without free planning of source to destination routing. In other words, even though greedy forwarding tends to be the more common forwarding mode in practice, we can think of the tree traversal forwarding mode as the basic routing algorithm and greedy forwarding as a best effort first try because it tends to be more efficient.

   Fig. 1. Multiple Spanning Tree with a hull.

   The proposed tree travel the destination is not found in the tree, and then it can terminate the traversal in exactly 2n- 2 hops and store information about the starting node in the packet. A major contribution of this work is the spanning tree that call a hull tree that allows us to restrict the above search problem to a small sub-tree of the full spanning tree for a given destination thereby guaranteeing packet delivery in much fewer than 2n-3 hops.

2. Group of Candidate Subset

   The nodes in the network maintain the topology map of the wireless network. Suppose a node wants to send the packets, it's can get the location of the destination and its neighbors, then uses these information to get the candidate node subset.

   Grouping the candidate node based on a neighbor reach in the hull tree will be explained in detailed. In Fig.2, nodes 1 to 7 are the neighbors of source S1. When S1 wants to send packets to destination D7, it looks up the neighbor routing table, and selects the neighbors that fall within an angle convex hull tree in the direction of D.

   Fig. 2. Choose candidate node for grouping.

   The value of theta is chosen high sufficient to guarantee that there are nodes fall into this area in a dense network, but must be smaller than 180 degree.

   The value of theta is chosen high sufficient to guarantee that there are nodes fall into this area in a dense network, but must be smaller than 180 degree. Thus, no packet is sent in the backward direction. When node I gets its forward dependability Pij(i) and backward dependability Pji(i) with neighbor j, then calculate the ETXij (i) (Expected Transmission Times) between these two nodes is:

   In the Fig.3 shows, a is the relative learning between the line from S to D and the line from S to the intermediate node

   1. calculate Distsi is the distance between source S and forwards node I. Thus, Distsi*cos is the effective forward distance from S to node i in the direction of the destination. ETD is the expected transmission distance between S and node I over a time interval.

3. Reduce Duplicated Transmission Based on Hull Tree Algorithm

   The proposed multiple hull tree algorithms is similar to the spanning tree where each node has a related convex hull that contains the locations of all its child nodes. Multi -hull trees provide a way of aggregating location information and they are built by aggregating convex hull information up the tree. This hull tree information is used to avoid duplicate packet transmission. The tree traverses a significantly reduced sub-tree, consider if only the nodes with convex hulls containing the destination node.

   = 1

   +

   (1)

   Fig. 4. (a) Spanning tree. (b) Convex hull tree.

   This equation calculates the source to destination of expected transmission after the information gathering some period of time, every node has constructed its neighbor table of the source.

   Fig. 3. Calculate ETX Distance.

   The figure contains the nodes it hears directly and the equivalent estimated link reliabilities distance. Suppose s node has a packet to send, it chooses the nodes from ETX calculate table to form the candidate subset. To make certain packets do not cycle in a loop, every time the packet is forwarded, it must never be send to nodes beyond than the destination. If the packet is received by a node predictable beyond the direct line between source-destination pair, it is dropped. It can be a lot of nodes can be chosen as forwarding nodes, and some of them have very low transmission reliabilities. Here choose the relay nodes based on ETD (Expected Transport Distance) calculated by (1):

   = (2)

   Each node in single hull tree stores information about the convex hulls that contain the coordinates of all the nodes in sub-trees associated with each of its child nodes. The convex hull information is aggregated up the tree. Each node computes its convex hull from the similar of its coordinate and the points on the convex hulls of all its child nodes, and this information is communicated to the parent node. Consequently, the convex hull associated with the root node is the convex hull of the entire network and contains all the nodes in the network.

   In multi convex hull tree for a set of points is the smallest convex polygon that contains all the points; it is smallest because the convex hull will be contained in any convex polygon that contains the given points. The multi- hull is representing as a set of nodes and set links partitioned. To make sure that the convex hulls use only storage instead of no of storage, where n is the network size; it can limit the number of vertices for a convex hull to a maximum of r nodes reach.

   To reduce a multi convex hull with nodes to a smaller one with' s-1' nodes, it can project the boundary lines to form an adjacent triangle at every feature. Because some time node medium has undeliverable of packet. The wireless medium, the following undesired location would occur. One of the candidates sends ACK message and forwards the packet. While the other candidate receives this ACK and drops the packet, just the sender miss it and retransmits the packet in ineffective. This is a major reason for duplicates ACK.

   In order to decrease this kind of duplications packets, each relay node remembers the packet it has processed. If it receives a packet more than once, the node only sends the ACK to inform the others that it received the packet.

4. Optimization of Undeliverable Packets

Suppose data-centric sensor network, where the

1. Performance Metrics

   PDR is the ratio of the number of data packets received by the destination node to the number of data packets sent by the source mobile node. It can be evaluatedin terms of percentage (%). This parameter is also called success rate of the protocols, and is described as follows:

   Send Packet no

   destination of packets frequently does not correspond to original nodes, this condition of the packet is unacceptable

   PDR =

   Receive packet no

   × 100 (3)

   packet. So looping problem arises because, through tree traversal, a node that receives a packet from its last child node does not know if there is any other multi convex hull in another part of the tree that contains the destination and has no choice but to forward the packet to the parent node.

   In this condition, maintain additional information in the tree to allow a node to make a decision if the destination no of a packet could maybe be in a tree branch of the tree reachable only by forwarding the packet up the multi- tree. In adding to its multi convex hull, each node maintains information about the set of convex hulls H that intersect with its own convex hull.

   Here overcome the conflict hulls or looping the packet. Suppose A node stores a conflict hull for related nodes that are not children node or associates. More accurately, it stores conflict hulls for nodes with which it shares a common children node, where that node is immediately below the common child node, and its convex hull intersects with this node's. With this extra information, a node that receives a packet from its last child during tree traversal will check if any of its conflict hulls contain the destination. If not, the packet will forward to its first child instead of the parent. Here effectively, the conflict hulls allow us to prune some nodes at the root of the routing sub-tree during tree traversal. So the proposed system improves the packet delivery performance and reduces the delay of the packet transmission.

   1. EXPERIMENTAL RESULTS

      For this simulations, use a random radio model: all nodes have same radio range with two nodes can communicate if and only if they are within radio range of each other and if their line-of-sight does not intersect an obstacle. Here add the obstacle simulator supports linear, polygonal and circular obstacles. Wireless losses are not simulated since our goal is to compare the algorithmic behavior of Tree- based GDSTR to other geographic routing algorithms.

      TABLE I. NETWORK PARAMETERS

      Throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node.

      X = C (4)

      T

      Where X is the throughput, C is the number of requests that are accomplished by the system, and T denotes the total time of system observation.

      Average end-to-end delay Average end-to-end delay signifies how long it will take a packet to travel from source to the destination node. It includes delays due to route discovery, queuing, propagation delay and transfer time.

      = ( + + (5)

      Where dend-end= end-to-end delay, dtrans= transmission delay,dprop= propagation delay,dproc= processing delay,dqueue= Queuing delay and N= number of links.

      This metric is useful in understanding the delay caused while discovering path from source to destination.

2. Performance Comparision

Performance of regular geographic opportunistic routing and minimum delay routing protocol tree based GDSTR based on the varying number of nodes in the chain topology is done on parameters like packet delivery ratio and better throughput.

TABLE II. NO OF PACKETS DELIVERED VS DELAY

Number of Packets Delivered

1200

1000

GOR

OGDSTR

800

600

400

200

0

100 500 1000 1500 2000

Delay(Sec)

Fig. 4. Compare delivery ratio with different protocol.

Fig. 4 illustrates the cumulative number of packets delivered within a certain time after sending. We observe that TGDSTR is able to deliver nearly 98% of the packets within twenty minutes in the 15km x 15km scenario. At the same time, Greedy delivered 72% of the packets whereas GOR 53%. These results indicate that can deliver the vast majority of the packets to the final destination. The GOR algorithm shows poor performance due to the fact that the current trajectories of the vehicles do not actually.

TABLE III. NO OF NODE VS % PACKETS DELIVERED

40

GOR

Tree GDSTR

35

30

Hops

25

20

15

10

5

0

50 100 150 200 250 300 350

Avg No of Nodes

% Packets Delivered

120

100

80

60

40

20

0

Avg No of Nodes

Fig. 6. Average number of hops for different network densities. Smaller

is better.

GOR

Tree GDSTR

Fig. 6 illustrates notice that the number of hops required for Greedy is much higher than for the other two algorithms, because it constantly attempts to forward the message to neighbors that are closer to the destination. However, tree- based GDSTR requires only a few encounters before finding a vehicle that drives near the destination of the packets. Furthermore, this number does not depend on the density of the network but only on the road topology (e.g., the probability to find in this road segment a vehicle that is going close to the destination of the packet).

1. CONCLUSION

Fig. 5. Delivery ratio for different densities.

In Fig. 5, we have plotted the delivery ratio of the algorithms for varying densities (TTL is 1800sec). Greedy shows acceptable performance only in dense networks (peak- time) due to the fact that it requires the presence of neighbors that are closer and closer to the final destination. In fact, GOR algorithm outperforms Greedy in sparse road traffic conditions where trajectory information is more important than the position of the neighbors. However, tree- based GDSTR is able to outperform both algorithms in any network conditions. It is adequate to find only one vehicle that will carry the message to its destination and thus, it is not required to have very frequent encounters like greedy and GOR.

Protocols

No of Nodes

50

100

150

200

250

300

350

GOR

16

18

21

23

27

32

38

TreeGDSTR

8

9

12

15

16

21

23

TABLE IV. AVERAGE NUMBER OF HOPS OF DELIVERED PACKETS – DENSITY

In this paper present novel, tree -based routing protocol and reduce the duplicate transmission, called Tree-GDSTR. First tree based geographic information of the source to destination pair to get the group of candidate subset. The relay nodes attention to the ACK messages from other candidates before their turn to send ACK and transmit the packet. Suppose there is no ACK messages have been received, the nodes acknowledge the packet and relay it at the transmission probability. The tree based geographic routing, it is no less efficient to use multi- hull trees instead of a planar graph as the backup routing topology when greedy forwarding fails, and it is significantly easier to build and maintain multi- hull trees than a planar graph.

Future research directions the main issue in opportunistic routing relies on the construction of the relay set selection. In this sense, the presence of obstacles should be taken into account. When dealing with mobile networks such as VANET.

REFERENCES

1. Akyildiz, I.F., Wang, X., Wang, W.: Wireless mesh networks: A survey. Computer Networks Journal (2005)

2. Chachulski, S., Jennings, M., Katti, S., Katabi, D.: Trading Structure for Randomness in Wireless Opportunistic Routing. In: Proc. of ACM SIGCOMM, ACM Press, New York (August 2007)

3. Rozner, E., Seshadri, J., Mehta, Y., Qiu, L.: Simple Opportunistic Routing Protocol for Wireless Mesh Networks. In: Proc of the 2nd IEEE Workshop on WiMesh, IEEE Computer Society Press, Los Alamitos (2006)

4. Biswas, S., Morris, R.: EXOR: Opportunistic multi-hop routing for wireless networks. In: Proc. of ACM SIGCOMM, ACM Press, New York (August 2005)

5. Biswas, S., Morris, R.: Opportunistic routing in multi -hop wireless networks. In: ACM HotNets (August 2003)

6. Fussler H, Widmer J, Kasemann M, Mauve M, Hartenstein H (2003) Contention-based forwarding for mobile ad-hoc networks. Elsevier's Ad Hoc Netw 1(4):351369, November

7. Zorzi M, Rao RR (2003) Geographic random forwarding (GRAF) for ad hoc and sensor networks: energy and latency performance. IEEE Trans Mob Comput 2(4):349365

8. X.F. Mao, S. Tang, X. Xu, X. Y, Li, and H. Ma, :Energy Efficient Opportunistic Routing in Wireless Networks, Proceedings of IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 11, pp. 19341942, November 2011.

9. S Biswas and R Morris, :EXOR: Opportunistic Multi-hop Routing for Wireless Networks, in Proceedings of ACM SICGOMM, 133-144, 2005.

10. R. Shah, S. Wietholter, A. Wolisz, and J. Rabaey, When Does Opportunistic Routing Make Sense? in Proc. IEEE PerCom Workshops, 2005, pp. 350-356.

11. S. Biswas and R. Morris, ExOR: Opportunistic Multi-Hop Routing for Wireless Networks, SIGCOMM Comput. Commun. Rev., vol. 35, no. 4, pp. 133-144, Oct. 2005.

12. R. Bruno and M. Burch is, Survey on Diversity-Based Routing in Wireless Mesh Networks: Challenges and Solutions, Comput. Commun., vol. 33, no. 3, pp. 269-282, Feb. 2010.

13. E. Rozner, M.K. Han, L. Qiu, and Y. Zhang, Model-Driven Optimization of Opportunistic Routing, SIGMETRICS Perform. Eval. Rev., vol. 39, no. 1, pp. 229-240, June 2011.

14. X. Mao, S. Tang, X. Xu, X.-Y. Li, and H. Ma, Energy-Efficient Opportunistic Routing in Wireless Sensor Networks, IEEE Trans. Parallel Distrib. Syst., vol. 22, no. 11, pp. 1934-1942, Nov. 2011.

15. M. Zorzi and R.R. Rao, Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance, IEEE Trans. Mobile Comput., vol. 2, no. 4, pp. 349- 365, Oct.Dec. 2003.

16. Rozner, E., Seshadri, J., Mehta, Y., Qiu, L.: Simple Opportunistic Routing Protocol for Wireless Mesh Networks. In: Proc of the 2nd IEEE Workshop on WiMesh, IEEE Computer Society Press, Los Alamitos (2006)

17. Chachulski, S., Jennings, M., Katti, S., Katabi, D.: Trading Structure for Randomness in Wireless Opportunistic Routing. In: Proc. of ACM SIGCOMM, ACM Press, New York (August 2007)