# Transfer-Efficient Face Routing Using the Planar Graphs of Neighbors in High Density WSNs
###### Abstract
In addition, because the method requires the construction of a network graph using the increased information and then performing planarization, the number of calculations is increased, as is the consumption of resources such as memory and energy. This phenomenon makes the efficiency drop sharply due to the long computation time and the high energy consumption caused by the large number of nodes deployed within radio range and their position information in a high density WSN. In addition, whenever a node within 2-hop range is added or deleted and regardless of whether it affects the routing, the message transfer node always receives information on the changed node and performs network graph generation, planarization, and routing again. In this paper, we propose a novel face routing method that uses the planar graphs of the message transfer node's neighbors to forward a message to the most remote neighbor on the route within radio range without traveling via intermediate nodes to improve transfer efficiency and to solve the problems previously mentioned in existing face routing methods. In the proposed face routing, a message transfer node receives the information on the planar graph of its neighbors and it constructs a local full planar graph within radio range. Using the generated planar graph, the most remote neighbor node on a routing path is discovered and the message is transferred directly to the node without traveling via intermediate nodes. Unlike face routing using 2-hop node information, the load for generating the local planar graph is distributed to each neighbor, which reduces the amount of location information to be transmitted by sending only the information on the planar graph nodes rather than on all of the neighboring nodes. In addition, the efficiency can be improved by virtue of only receiving information when a node changes and recalculating the routing if there is an influence on the planar graph rather than every time a node is added or destroyed. That is to say, if a node is added to the network but it is removed during the planarization process of the neighbor, the changed node information need not be transmitted to the message transfer node and it is not necessary to recalculate the routing. In addition, if a node is removed from the network but has already been deleted in the existing planar graph, the changed topology need not be transmitted. Furthermore, in order to improve transfer efficiency while balancing energy consumption of each node, the message transfer node, if its remaining power is low, sends the message to the nearest neighbor along the face boundary instead of forwarding it to the remote node to minimize energy consumption. The rest of the paper is organized as follows. In Section 2, we provide a review of related work. In Section 3, we discuss the problem of planar graphs and planarization, and, in Section 4, we explain the proposed face routing in detail. In Section 5, a comparison of its performance with existing research through experiments is reported, and conclusions are drawn in Section 6.