# Transfer-Efficient Face Routing Using the Planar Graphs of Neighbors in High Density WSNs
###### Abstract  
Face routing has been adopted in wireless sensor networks (WSNs) where topological changes occur frequently or maintaining full network information is difficult. For message forwarding in networks, a planar graph is used to prevent looping, and because long edges are removed by planarization and the resulting planar graph is composed of short edges, and messages are forwarded along multiple nodes connected by them even though they can be forwarded directly. To solve this, face routing using information on all nodes within 2-hop range was adopted to forward messages directly to the farthest node within radio range. However, as the density of the nodes increases, network performance plunges because message transfer nodes receive and process increased node information. To deal with this problem, we propose a new face routing using the planar graphs of neighboring nodes to improve transfer efficiency. It forwards a message directly to the farthest neighbor and reduces loads and processing time by distributing network graph construction and planarization to the neighbors. It also decreases the amount of location information to be transmitted by sending information on the planar graph nodes rather than on all neighboring nodes. Simulation results show that it significantly improves transfer efficiency. face routing; distributed processing; planar graph; transfer efficiency; high density WSN 2017  
1724022017172  
Greedy routing forwards a message to the neighbor node closest to the destination, but routing fails if there is no neighbor node closer to the destination than the message transfer node. However, face routing transmits a message along the face boundary of a planar graph built by eliminating intersecting edges that can cause loops in a network graph. It is used as one of the methods for handling communications in a void area where a message cannot be forwarded by greedy routing [13]. In order to detour void areas, other routing protocols (e.g., ITGR [14], HDAR [15]) have been proposed to deliver messages along a path that is unaffected by holes after hole detection. Face routing involves a planarization process that removes intersecting edges in a network graph in order to construct a planar graph, whereby the generated planar graph should not be segmented due to the eliminated edges. The Gabriel graph (GG) [16] and the relative neighborhood graph (RNG) [17] are representative planar graphs in which the network is not cut off when they are constructed using only local information [18]. In order to perform planarization while preventing the segmentation of a network, GG and RNG remove long edges that might be an intersecting edge in a network graph. Therefore, planarization results in a planar graph consisting of only short edges. However, this causes inefficiency because a message is sequentially transferred to the remote node within the radio range along the nodes on a face boundary made up of short edges even though it could be directly forwarded. In order to mitigate the inefficiency, face routing using the location information on all nodes within 2-hop range has been proposed [19]. It forwards a message directly to the most remote neighbor located on the routing path within radio range. In this method, a message transfer node builds a local full network graph within radio range using 1- and 2-hop node information, performs planarization to construct a local full planar graph within radio range, discovers the most remote node to which a message can be forwarded, and sends a message directly to the selected node without traveling via intermediate nodes. Since the location information on all the 2-hop nodes as well as the immediate neighboring nodes must be transmitted to the message transfer node, the amount of information to be transmitted is increased compared to legacy face routing.