# Transfer-Efficient Face Routing Using the Planar Graphs of Neighbors in High Density WSNs
## 4 Transfer-Efficient Face Routing
### Analysis  
TEFR utilizing the local planar graphs of the message transfer node's neighbors needs more location information compared with legacy face routing using local information but uses less position information than face routing using the information on all nodes within 2-hop range. Equation (1) compares the quantity of location information transmitted to a message transfer node. In the equation, the left-hand side is legacy face routing, the middle is TEFR, and the right-hand side is face routing using 2-hop node information:  
\[n\times m\leq n\times m+n\times((1-\lambda)\times n)\times m\leq n\times m+n^{2 }\times m, \tag{1}\]  
where \(n\) is the average number of neighboring nodes per node, \(m\) is the data size of location information for one node, and \(\lambda\) is the ratio of nodes removed in planarization (\(0\leq\lambda<1\)). Figure 9: Phases of TEFR node selection: (**a**) the start of simulating face routing, (**b**,**c**) select the next nodes of nodes \(i_{2}\) and \(i_{6}\), respectively, and (**d**) the termination of node selection. The arc signifies the distance between the destination (\(t\)) and node \(u\) where face routing started. ```
\(lhn:\) a node according to left hand rule \(ctn:\) a current traversal node \(mtn:\) a message transfer node \(frn:\) a node where face routing started \(thd:\) the power threshold for direct transmission select \(lhn\) of \(ctn\) from GG edge list if( the power level of \(ctn<thd\)) then  send message to \(lhn\), exit endif while(\(lhn\) is located within radio range of \(mtn\)) do if(\(lhn\) is closer to the destination than \(frn\)) then  change mode to greedy routing  send message to \(lhn\), exit elseif(the edge between \(lhn\) and \(ctn\) intersects \(\overline{st}\)) then  send message to \(ctn\), exit else  set \(ctn\) with \(lhn\)  select \(lhn\) of \(ctn\) from GG edge list endif endwhile  send message to \(ctn\), exit
```  
**Algorithm 2** Selecting the most remote node using the GG edge list and sending a message. In Equation (1), in legacy face routing, a message transfer node only receives location information on the average number of neighboring nodes, while TEFR receives the location information on the immediate neighbors and their planar graph nodes after planarization. Face routing using 2-hop node information receives the location information on the immediate neighbors and all of their neighbors as well. The amount of location information required for TEFR is the same as that for face routing using 2-hop node information when nodes are not removed in the planarization step (\(\lambda=0\)) and becomes close to that of legacy face routing as the number of removed nodes increases. In a high density WSN, TEFR does not rapidly increase the amount of position information to be transmitted because, even if the number of nodes increases, those removed by planarization increases and \(\lambda\) becomes bigger as the density of the nodes increases. TEFR uses the location information on more nodes than the legacy face routing to improve transfer efficiency, but it reduces the amount of position information in comparison with face routing using 2-hop node information because message transfer nodes only receive the information on the planar graph nodes of their neighbors. The space complexity of a node for each face routing can be determined using Equation (1). \(\mathcal{O}(n)\), \(\mathcal{O}(n^{2})\), and \(\mathcal{O}(n^{2})\) are respectively the space complexity of each node for legacy face routing using local information, face routing using 2-hop node information, and TEFR, where \(n\) is the number of deployed nodes. Equation (2) compares the end-to-end delay of face routing within radio range.