{'fraction_non_alphanumeric': 0.033057283254870964, 'fraction_numerical': 0.007937871550805815, 'mean_word_length': 4.285506719941882, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Utilizing hyperplanar substructures to perform efficient range-based WSN localization

A wireless sensor network (WSN) consists of multiple wireless sensor nodes that communicate each other to fulfill a particular task. In this paper, we emphasize on the networks whose deployments admit lower dimensional substructures, such as collinear groups in 2D, or coplanar groups in 3D. When these groups are given as a part of the input, we describe an algorithm to utilize this information to perform a low-cost localization. In emergency situations such as fire, earthquake etc. inside a building, wireless sensor networks might be very crucial to provide critical information and help the rescue teams to move very quickly by decreasing their burden of exploring the environment. Thus, it is very important to develop a system that provides information quickly and without consuming too much energy. We observe that in these type of environments, sensor nodes tend to form hyperplanar groups. A hyperplane is a subspace of one dimension less than its ambient space, and accordingly, a hyperplanar group of sensor nodes is a group of nodes that sit on the same hyperplane. When we consider a floor of a building, the nodes can be deployed on the corridors to form collinear groups, and when we consider the whole building, the sensor nodes will sit on the floors to form coplanar groups. Therefore, we study range-based WSN localization problem in 3D environments that induce hyperplanar groupings. First, we show that it is an \NP-hard problem to obtain hyperplanar groups, even if we are given the equations of the hyperplanes. Then, we describe an algorithm that assumes each sensor node is aware of its hyperplanar group, and performs a localization when the sensor nodes are deployed in the corridors on each floor of a building. In this case, grouping information allows us to localize a network, which cannot be localized by conventional range-based localization algorithms.


Introduction
Recent developments in technology pose a need for wireless sensor network technologies to be used broadly [3]. A wireless sensor node is a small device that is equipped with a radio transmitter. A wireless sensor network, in short WSN, is the collection of many wireless sensor nodes. Each node is able to communicate and measure its distance to another node within the radio's distance. Independent of the application area, the location information of wireless sensors in a WSN is crucial to improve the quality of service. The information of positions increases the quality of the applications such as geographical based queries. When equipped with proper devices, a sensor node can measure its distance to another node in the network using the communication links. For all types of applications, the information of positions can be appended to the data that is gathered from the sensor nodes, easing the traceability of the sensors, as in WSNs that work in geographical routing.
Range-based wireless sensor network localization problem [3,8,12,16,18] is estimating the positions of the wireless sensor nodes in a network by only using pairwise distances. Estimating the position of a node is called localizing the node. In order to localize a node in 3D, we need four pairwise distances from four different localized nodes in general position.
Network localization problem is proved to be a hard problem [3,5,16] but still preferred over Global Positioning System (GPS) [14] because GPS is usually not applicable for small-scale networks and indoors [1,2,8,17,20].
Generally, sensor nodes are assumed to have identical sensing ranges while dealing with range-based localization. Thus, the unit disk graph model is used to model the network. It should be noted that realizing UDG is also an NP-hard problem, by reduction from Unit disk graphs recognition [7,10,15]. Since range-based localization uses UDG model, one can easily see that it is also NP-hard [5].
In [9], it was observed, and experimentally verified that knowing which nodes are in the same group increases the accuracy, and decreases the computational time, when the number of groups is much smaller than the number of sensors. This is because conventional distance-based localization methods, such as trilateration [13] and quadrilateration [9], use distances from points (in our case sensors) in general position. However, in practice, objects lie on planar surfaces to form coplanar groups. Which means a large amount of computational power is spent on finding correct nodes to localize another node.
In an effort to perform a more efficient localization, we can exploit the information on the hyperplanar substructures, if provided. That is, a function h : S → {1, 2, . . . , k}, called hyperplanar grouping function. Two sensor nodes s i and s j are said to be on the same hyperplanar group if, and only if, h(i) = h(j). The task of finding hyperplanar grouping function in 2D from given UDG, and hyperplanes is called hyperplanar substructures recognition. In case where hyperplanar substructures are realized, i.e. the mapping h is given, we are able to perform a lower dimensional localization for each hyperplanar group separately, and then localize the groups globally with respect to each other.
In this paper, we show that discovering the mapping function h is an NP-hard problem, even if the hyperplanes are given as a part of the input by their equations. Then, we describe an algorithm to perform an efficient localization in case where h is given as input. Afterwards, we describe an algorithm to utilize the grouping function, when available, and show that our algorithm is able to localize a network which cannot be localized by using only pairwise distances.

Motivation
The physical world we live in is a 3D environment. Therefore, many applications require wireless noeds to be localized in 3D. Most of the scenarios in real-world WSN applications that need localization have usually deployments where the sensor nodes sit on planar regions to form sets of planar clusters. Examples of these surfaces include structures seen in both indoor (e.g. floors, doors, walls, tables etc.) and outdoor (e.g. mountains, valleys, hills etc.) environments. It is hence observed that a method for exploiting the information of structural information in 3D is very much needed in order to improve the quality of localization achieved.
In this paper, we particularly study the scenario where there is an emergency inside a building, such as fire, earthquake, hostage situation etc. When the members of a search and rescue team have limited time, our work aims to utilize wireless sensor networks to release the burden of searching, and allowing team to go for rescuing.
Suppose that the wireless nodes are deployed onto the corridors of a building. Each corridor can be interpreted as a collinear group (i.e. hyperplanar group in 2D). Moreover, since the building probably has multiple floors, each floor is a coplanar group (i.e. hyperplanar group in 3D).
In Figure 1, we give an example of a network deployed onto the corridors of a three-floor building. The dots denote the wireless nodes inside the building, and colored rectangles denote three different floors. A pair of nodes denoted by the same color sit on the same floor.

Basic terminology
In this section, we give the basic terminology that we use in the described algorithm.
Localizing of a sensor network is assigning relative positions to each sensor node in the ambient space (in our case, 3D). When we assign positions to each node, we obtain a point formation. The point formation of a network is denoted by F. It is a table that contains 2 columns, and n rows, where n is the number of nodes in the network. The first column contains the IDs of the nodes, and the second column contains each node's position in 3D Euclidean space.
A wireless sensor network is said to be localizable in R d when the corresponding distance graph G = (V, E) is globally rigid. In other words, every embedding of the vertices in V with respect to the pairwise Euclidean distances determined by the edge set E is isometric in R d . For more details on the localizability, we refer the reader to [4,11,19].
Every sensor node in the given network is initially unlocalized, i.e. it is not aware of its position. When we fix the position of a node, we mark it as localized. To fix the position, we need to reduce its degrees of freedom to zero by obtaining d + 1 Euclidean distances from its localized neighbors in general position. Intuitively, one expects a localizable network to be dense enough. Our algorithm, however, is able to perform localization in very sparse graphs if the grouping function is provided.
Observe that each hyperplanar group is an induced subgraph of the network graph G = (V, E), and each pair (u, v) of vertices in that induced subgraph satisfies h(u) = h(v). The set of all vertices in a particular hyperplanar group can be retrieved by taking the inverse of h. In other words, h −1 (i) gives us the set of all vertices in the hyperplanar group i.
We refer to the hyperplanar groups in 2D and 3D as collinear groups, and coplanar groups respectively. An edge is called interlinear (respectively, interplanar ) edge, if it corresponds to a connection between two nodes from different collinear (respectively, coplanar ) groups. Otherwise, it is a collinear (respectively, coplanar ) edge.

Our contributions
Our main contributions are listed as follows.
• We exploit the fact that the sensor nodes tend to form hyperplanar groups in real-world scenarios.
• We prove that extracting the grouping information is a hard task.
• We give an efficient and sustainable localization algorithm to utilize provided grouping function. Our algorithm does not require a dense network graph.

Hyperplanar substructures recognition
In this section, we formally define the problem of recognizing hyperplanar substructures, and then prove that the problem is NP-hard.

Problem definition
. . , n}. The task is to find a mapping h :

NP-hardness reduction for 2D environment
We first show that Hyperplanar substructures recognition is NP-hard when the sensor nodes are in 2D, and then move onto higher dimensions.

Lemma 1 Hyperplanar substructures recognition is
Proof. We give a reduction of this problem from 2coloring of 3-uniform hypergraphs. The polynomialtime reduction from a given graph to is as follows. Let H = (X, F ) be an instance of a 3-uniform hypergraph.
H is said to be 2-colorable if there is an assignment of two colors with no monochromatic edge. In the following part, when we write "uniformly distributed," we mean the Euclidean distance between two sensor nodes is less than one unit. We construct the gadget to perform the reduction as follows.
1. We have |X| vertical, and 2|F | + 2 horizontal straight lines. Each of them are parallel to either x-axis or y-axis.
2. All the vertical lines are colored black, and spaced equally. These lines are called vertex lines, that represent the vertex set of H. The Euclidean distance between each pair of vertical line is greater than two units, and less than three units.
3. One of the horizontal lines, called the main line, is given by the equation y = 0. This line is colored black. There are sufficient number of uniformly distributed wireless sensor nodes on the main line, including the intersection points of the main line and the vertex lines. 4. In order to fix the configuration, there exists a support line, which is placed horizontally, and sufficiently close the main line. This line contains only two vertices that forms a K 4 with two vertices from the main line.
5. Beginning from one unit above and below the main line, there are uniformly distributed sensor nodes on the vertex lines.
6. Remaining 2|F | horizontal lines are distributed equally above and below the main line. The ones above the main line are colored red. The rest of the horizontal lines are colored blue. All the colored lines are sufficiently far from the main line. Each r i and b i represent two mirrored copies of an edge i of H, and we refer to them as edge lines. We, later on, will use the edge lines to determine the color of an edge in H.
7. The Euclidean distance between each consecutive pairs of horizontal lines with the same color are equal, and greater than one unit.
8. There exist wireless nodes on the edge lines, each neighboring exactly two sensor nodes from a vertex line, forming a triangle. These triangles are referred to as flags, and the vertices are referred to as flag vertices in the following part of the proof.
In Figure 2, we draw the described configuration. The support line is indicated with dashes. The main line is just below the support line. There are six vertex lines, and six edge lines. That means in the hypergraph H = (X, F ), |X| = 6 and |F | = 3. Since every wireless node on the main line and the vertex lines are distributed uniformly, and the Euclidean distance between parallel lines is always greater than one unit, it is easy to fix the groups of the nodes on the main line and the vertex lines. Moreover, notice the flags on the leftmost and the rightmost vertex lines. These flags help us to fix the flag vertices those contain them.
All fixed nodes are indicated with white circles. The remaining nodes, flag nodes, are indicated with black circles. Now, our task is to find which flag nodes form a collinear group on an edge line.
The edge lines are two symmetrical copies of the edges in F with different colors with respect to the main line. We denote the two copies of an edge f ∈ F as b f and r f , for blue and red colors respectively.
If a vertex line that represents x ∈ X has its missing flag on an edge line b f or r f , then this indicates that the vertex x ∈ X is covered by the edge f ∈ F in the hypergraph H. In that case, the color of x is determined by flipping the configuration (either upside down or left to right) on the vertex line that corresponds to x. As demonstrated in Figure 4, the colors of some vertices in H might be determined by the vertices in V . In this particular example, u, v ∈ V are adjacent vertices, and w is neighboring none of them. Therefore, neither u nor v can flip horizontally, and they must flip vertically together. This means that the color of the vertices x, y ∈ X covered by the edge f ∈ F in H is determined by the vertices u, v, w ∈ V .
On each vertex line, there are five flags. If an edge has a "missing" flag on one side then that means that edge covers the vertex, and is colored according to the color of the edge line which is missing the flag. Remember that the Euclidean distance between consecutive vertex lines is less than 3 units. Hence, if two flag nodes are facing to each other, they must be neighbors in our configuration. Given this information, there can be only one mapping for hyperplanar grouping function for the input UDG G = (V, E), and only one corresponding coloring of its corresponding hypergprah H = (X, F ).
Therefore, an algorithm to solve the problem in polynomial time can also be used to solve 2-coloring of 3uniform hypergraphs in polynomial time.  Figure 3: Corresponding hypergraph of the configuration given in Figure 2 x y Figure 4: The color of the edge that covers vertex u is forced by vertices v and w.

NP-hardness reduction for every dimension
In Section 2.2, we have proved that the mentioned problem is NP-hard in 2D by a reduction from 2-coloring of 3-uniform hypergraphs. Now, let us give the proof for the case where the wireless sensors are deployed in 3D.
Proof. This reduction is hyperplanar substructures realization in 2D. Consider the gadget given in Figure 2 from Section 2.2. Suppose that each line is a plane seen from xy-plane in 3D. That is, each wireless node in Figure 2 has z-coordinate zero. In order to obtain a deployment in 3D, we just make a copy for each wireless node with the same x and y-coordinates, and let their z-coordinates be equal to 1. From this point on, it is trivial to see that each wireless node is connected to its copy in 3D, and no other from the copies. Thus, the triangle flags become triangle prisms. And we can easily apply the proof given in Section 2. Now that we have proved that proof given in Lemma 1 can be extended to 3D by Lemma 2, we can use the same method and extend the claim to higher dimensions.

Theorem 3 Hyperplanar substructures recognition is NP-hard in every dimension.
Proof. We already know that the problem is NP-hard in 2D by Lemma 1, and the hardness reduction can be extended to 3D by Lemma 2. In this proof, we show that the very same reduction can be used to prove the claim for 4D, and recursively, to higher dimensions.
In 2D, every node has 2 components, namely x and y. If we include one one component, z, and assign 1 to all third components of the sensors, Lemma 1 remains true.
Every component, in the context of this paper, adds an extra dimension to the nodes. Thus, for higher dimensions, we are able to set the new component's value to 1. The new copies of the sensor nodes will not be neighbors of the older ones. Also, the flags will be preserved. Therefore, the problem remains NP-hard in higher dimensions.

Localization process
In this section, we discuss the details of utilizing the grouping function. First, we describe an algorithm to localize two collinear groups with respect to each other. Then, we use the same idea to localize two coplanar groups with respect to each other. Finally, we show that our algorithm is able to perform localization easily where the quadrilateration algorithm fails.
For the sake of completeness, we give the quadrilateration algorithm in Algorithm 1. We would like to point out that algorithms given in this section do not use any GPS, and therefore they can only produce a point formation isometric (i.e. up to sign ambiguity) to the original network in the best case. if v can be localized in 3D then 11: enqueue(v, Q localized ) 12: return F Basically, the algorithm takes the network graph G = (V, E) as the input, and assigns positions to each vertex in v ∈ V , based on the pairwise distances given by E.
We begin by initializing the point formation in Line 1. In Line 2, we find a non-coplanar K 4 in G to begin the localization. The vertices of this complete subgraph are called the seeds. Since every pairwise distance is available, we can assign positions to these vertices in Line 3. In Line 4, we initialize a queue, called Q localized , that contains the localized vertices. Initially, it contains only the seeds. In Line 5, we start a loop, and continue until Q localized is empty. In the loop, we first dequeue the first node in Line 6, and then store its position into the point formation F in Line 7. Now that we have a localized vertex u, we iterate all its neighbors and broadcast the position of u. In Line 9, we use a variable v.Count, which indicates the number of localized neighbors of v. Thus, if some neighbor v of u has at least 4 localized neighbors, we check if it can be localized with respect to these neighbors in Line 10. Remember that if the localized neighbors are coplanar, then we cannot fix the position of v. If v can be localized, then we add it to Q localized , and continue the algorithm until the queue is empty. Finally, we return the point formation in Line 12.
Complexity analysis. In a network graph with n vertices and m edges, Algorithm 1 runs in O(n 4 m) time in the worst case.
Notice that even though the network graph admits a proper ordering to run the algorithm, the first K 4 we find in Line 2 might not be the correct vertices to start [4]. As four distance measurements from four vertices in general position are sufficient to localize a node, O(m) time is spent in each phase by using the queue data structure keeping the track of localized nodes. This can be accomplished by keeping the track of the number of localized neighbors of every node and inserting a node when the count hits the score of three. An effective three is the smallest count ≥ 4 with three non-coplanar neighbors. When we reach the count 4 for the first time, we check coplanarity. From then on, every new increment checks only the new one with any two previous neighbors. Therefore, it terminates after at most O(n 4 m) steps.
As seen above, the worst-case analysis gives us quartic running time. But notice that when the sensor nodes are deployed to form coplanar groups in 3D, and the communication between groups are held by a limited number of nodes (i.e. the number of interplanar edges are low), most of the neighbors of an unlocalized node will be coplanar. On the other hand, in the algorithm that we describe to utilize grouping function, this type of deployment is an advantage. Thus, it is safe to say that these two algorithms complete each other, in terms of their functionalities with respect to sparsity.
While describing our algorithms, we use the following data structure for a vertex of the network graph. A sensor node s u , represented by a vertex u in the network graph has three positions for each dimension. Namely, pos 1 , pos 2 , and pos 3 . u.pos 1 is a number that indicates the relative position of u with respect to other vertices in the same collinear group. Similarly u.pos 2 is the position of u with respect to the other vertices in the same coplanar group. Finally, u.pos 3 is the actual position of u in R 3 .

Localizing the nodes of a collinear group
In this section, we describe a linear-time algorithm to localize the nodes in a given collinear group ambient in 2D. The induced graph of a collinear group is called a unit interval graph since all the vertices are considered to be in 1D. The algorithm takes an induced subgraph of the network graph as the input, and outputs the embedding of that subgraph onto a straight line. For the sake of simplicity, we embed the vertices onto x-axis. While describing the algorithm, we denote the subgraph as G ′ = (V ′ , E ′ ). We also assume that G ′ is a connected graph.
If there are no cycles in a collinear group, then we can assign position to each vertex in linear time. The algorithm to achieve this is pretty straightforward. In case where the collinear group contains cycles, we can use the algorithm proposed by Brandstädt et al. [6] to find the Hamiltonian path in (claw,net)-free graphs. A (claw,net)-free graph does not contain both of the graphs given in Figure 5 as an induced subgraph.
Let us first show that interval graphs are (claw,net)free graphs.

Lemma 4 Every unit interval graph is claw-free.
Proof. Suppose that K(a; b, c, d) is an induced claw, as shown in Figure 5. Since b and c are not neighbors, that means the Euclidean distance between them is greater a b d c a b c x y z Figure 5: A claw (on the left) and a net (on the right) than 1 unit. And also, both of them are neighbors with a, which means the Euclidean distance between them is less than 2 units. If we embed b, a, c onto a straight line respectively, then a must be between b and c. Wherever we place d, within one unit distance from a, it must be a neighbor of either b or c. If d is neighbors with neither, then the Euclidean distance between d and a must be greater than one unit, contradicting the unit interval property.

Lemma 5 Every unit interval graph is net-free.
Proof. Suppose that N (a, b, c; x, y, z) is an induced net, as shown in Figure 5. It is clear that a, b and c must be inside an interval of at most 1 unit. Note that a, x and c, z are pairwise disjoint neighbors, and moreover neither x nor z is a neighbor of b. This means that b must be between a and c.
Wherever we place y, within one unit distance from b, it must be a neighbor of either a or c (also, at least one of x, z). If y is a neighbor with neither, then the Euclidean distance between b and y must be greater than one unit, contradicting the unit interval property.
Corollary 6 Every unit interval graph is (claw,net)free.
When a Hamiltonian path is found, Algorithm 2 can use the induced path as input, and assign positions to the vertices in linear time.
Theorem 7 ( [6]) Every (claw,net)-free graph G has a Hamiltonian path and such a path can be found in O(n + m) time.
By Theorem 7, we can use the algorithm given in [6], and find a Hamiltonian path in a collinear group. Then, we can simply give the found path as the input of Algorithm 2, and obtain the relative positions of vertices in a collinear group in O(m + n) running time.

Localizing collinear groups with respect to each other
We have proposed a method to localize the vertices of a collinear group in 1D. Now, we describe an algorithm to find the position of two hyperplanar groups in their ambient space. This algorithm is described in general for R d , and therefore is applicable to both 2D and 3D.
It fixes the position of d vertices in a hyperplanar group, and then uses these positions to determine the equation of the hyperplane on which the vertices of that group lies. Finally, the positions of every other vertex in the same group can be found in the same ambient space by applying a transformation.
The hyperplanar group of a vertex x is denoted by h(x), and we can retrieve the set of vertices U where for each pair u, v ∈ U , h(u) = h(v) by taking the inverse of h(·) (denoted by h −1 (·)). Note that we can use h for both localization of collinear groups or coplanar groups without loss of generality. However, we operate only in one dimenstion i.e. we do not localize a collinear group with respect to a coplanar group, and vice versa. Similarly, when we write u.pos d , it is the relative position of u in d dimensional space.
The equation of the hyperplane that every vertex in the group i lies is denoted by eqn(i). We say that a hyperplanar group i is adjacent to j, if there exists at least one interlinear (or interplanar) edge between a vertex in i, and a vertex in j.
Complexity analysis. In a network graph with n vertices, m edges, k coplanar groups, and r collinear groups, Algorithm 3 runs in O(k 2 m) + O(r 2 m) + O(n + m) time in the worst case.
We spend O(n + m) time to find the 1D positions of the vertices using Algorithm 2 [6]. Note that we iterate on each collinear group only once, therefore the total running time is not affected by the number of the collinear groups. For each collinear group, we iterate all the other collinear groups to find proper edges to localize the support vertices. At each iteration, we also iterate the interlinear edges. Therefore, this phase takes O(r 2 m) time. Same reasoning is also true for k coplanar groups. Since these operations are not nested, the overall asymptotic running time of Algorithm 3 is O(k 2 m) + O(r 2 m) + O(n + m).

Conclusion
This paper describes an energy-efficient algorithm to localize a wireless sensor network. In general, localization problem is an NP-hard problem. However, we have utilized the observation that in some cases the sensor nodes form hyperplanar groups. Using this information, we have proposed methods to localize a network, whose localization will consume much more time using conventional trilateration and quadrilateration algorithms.
We have defined a function h, called hyperplanar grouping function, which maps the vertices to hyperplanar groups. Our algorithms work under the assumption of availability of the hyperplanar grouping function, since we proved that determining that function is an NP-hard problem.
Instead of iterating each vertex multiple times, our Algorithm 3 Localizing hyperplanar groups with respect to each other input: Network graph G = (V, E), hyperplanar grouping function h output: Point formation F of G in R d 1: Find v.pos 1 for each v ∈ V 2: Pick a group i 3: Mark the vertices in i as localized 4: for each group j adjacent to i do 5: for each u ∈ h −1 (j) do 6: if u has d neighbors in i then Mark u as support vertex 9: if There are d support vertices then 10: Determine eqn(j) 11: Find the transformation matrix 12: Apply the transformation to h −1 (j) 13: Add the positions into F

14:
Notify the neighbors of localized vertices 15: go to Line 16 16: if No collinear groups are localized then 17: return not localizable 18: for each non-localized group j do 19: for each u ∈ h −1 (j) do 20: if u was notified d + 1 times then 21: Determine u.pos d

22:
Mark u as support vertex 23: if There are d support vertices then continue the iteration 29: return F proposed algorithm breaks down the localization problem into lower-dimensional (and also smaller) problems, and thus reducing the quartic running time complexity with respect to the number of vertices. Since the number of hyperplanar groups is assumed to be much less than the number of vertices, the quadratic running time on the number of groups amortize itself as more crowded the groups get.
In addition, to the best of our knowledge, this paper is the first in the literature that proves unit interval graphs are (claw,net)-free graphs. Moreover, using this information, we have described a linear-time algorithm to embed a given unit interval graph on a straight line.