{'fraction_non_alphanumeric': 0.03850849526910164, 'fraction_numerical': 0.012768338589887069, 'mean_word_length': 4.29749393694422, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph invariants for unique localizability in cooperative localization of wireless sensor networks: rigidity index and redundancy index

Rigidity theory enables us to specify the conditions of unique localizability in the cooperative localization problem of wireless sensor networks. This paper presents a combinatorial rigidity approach to measure (i) generic rigidity and (ii) generalized redundant rigidity properties of graph structures through graph invariants for the localization problem in wireless sensor networks. We define the rigidity index as a graph invariant based on independent set of edges in the rigidity matroid. It has a value between 0 and 1, and it indicates how close we are to rigidity. Redundant rigidity is required for global rigidity, which is associated with unique realization of graphs. Moreover, redundant rigidity also provides rigidity robustness in networked systems against structural changes, such as link losses. Here, we give a broader definition of redundant edge that we call the"generalized redundant edge."This definition of redundancy is valid for both rigid and non-rigid graphs. Next, we define the redundancy index as a graph invariant based on generalized redundant edges in the rigidity matroid. It also has a value between 0 and 1, and it indicates the percentage of redundancy in a graph. These two indices allow us to explore the transition from non-rigidity to rigidity and the transition from rigidity to redundant rigidity. Examples on graphs are provided to demonstrate this approach. From a sensor network point of view, these two indices enable us to evaluate the effects of sensing radii of sensors on the rigidity properties of networks, which in turn, allow us to examine the localizability of sensor networks. We evaluate the required changes in sensing radii for localizability by means of the rigidity index and the redundancy index using random geometric graphs in simulations.


Introduction
Localization is an essential service for many applications of wireless sensor networks. A wireless sensor network consists of a small number of anchors (reference nodes) and a large number of small, cheap ordinary nodes (non-anchors). Anchors have a priori knowledge of their own positions, e.g., GPS, and ordinary nodes have no prior knowledge of their locations. If ordinary nodes were capable making measurements to multiple anchors, they could determine their positions. However, several ordinary nodes cannot directly communicate with anchors because of power limitations or signal blockage. A recent paradigm is cooperative localization, in which ordinary nodes help each other to determine their locations [1,2]. In cooperative localization, ordinary nodes not only make measurements with anchors, but also they make measurements with other ordinary nodes. The types of measurements usually include distance estimates and/or angle estimates [3].
The set of ordinary nodes is uniquely localizable if there is a unique set of positions satisfying the conditions resulting from measurements. Unique solvability of the cooperative localization problem is characterized by the results from "rigidity theory." Redundant rigidity is required for global rigidity, which is associated with unique realization of graphs. Use of rigidity theory in localization is well described in the literature [4−10]. More details will be given in Section 2.
Recent works introducing the rigidity theory into formation control has also provided provably correct methods to model and analyze the ad hoc network topologies within robotic teams [11][12][13][14][15]. For example, rigidity theory provides us tools for formation control using relative distance measurements instead of relative position measurements. Moreover, rigidity is necessary to estimate relative positions using only relative distance measurements [11].
Quantitative measures of rigidity have been proposed by researchers recently. Jacobs et al. provided a measure of rigidity within the context of microstructures of proteins, and their approach are based on chemical bonds [16]. Zhu and Hu studied quantitative measure of formation rigidity using stiffness matrix [17]. Zelazo et al. introduced the rigidity eigenvalue based on symmetric rigidity matrix [11]. The latter two studies employed rigidity based matrices and studied the properties of those matrices to explore the rigidity properties of networks.
In this paper, first we provide a measure of "generic rigidity" in 2-space for both rigid and non-rigid graphs. Then the concept of generalized redundancy is introduced, which allows us to provide a measure of "generalized redundancy" in 2-space for both rigid and non-rigid graphs. Our approach is based on the combinatorial characterizations of rigidity and redundancy. Specifically, the main contributions of this work are: (a) the translation of edge distribution in a network graph to that of a rigidity measure that we term the "rigidity index," (b) the translation of the generalized redundancy of edge distribution in a network graph to that of a redundancy measure on network rigidity that we term the "redundancy index." From a graph theory point of view, the benefits of these measures are as follows: They permit us (i) to quantify the distribution of edges in a graph in terms of rigidity and redundant rigidity, (ii) to compare various graphs for rigidity in terms of the distribution of their redundant and non-redundant edges.
From a sensor network point of view, these two measures enable us to evaluate the effects of sensing radii of sensors on the rigidity and redundancy properties of networks, which in turn allows us to examine the localizability of sensor network graphs. In particular, we are interested in the following questions: (i) how much change in sensing radii do we need to reach from non-rigidity to rigidity, and to reach from rigidity to redundant rigidity in random geometric graphs? (ii) given that redundant rigidity is associated with unique localizability, is redundant rigidity a heavy burden on the network once rigidity is achieved? We provide answers to these questions in this paper.
The localization process often needs to be repeated in mobile wireless sensor networks. Mobility brings the possibility of the loss of links, which enforces to have not only localizable network structures but also structures which remain localizable after the loss of links in the network. Since redundancy plays a role in robustness, redundancy measure also helps us to evaluate robustness to link losses.
The structure of the paper is as follows. We give preliminaries on rigidity in Section 2. Main results on the rigidity index, the redundancy index and the corresponding complexity analysis are provided in Section 3. Examples to illustrate those indices on graphs are presented in Section 4. Applications of these two indices in sensor network simulations are demonstrated in Section 5. Finally, the paper ends with a conclusion and some outlook on future directions in Section 6.

Rigidity
First we provide below some background on rigidity, redundant rigidity and global rigidity. We refer the reader to [18][19][20][21] and the references therein for more details.

Rigid frameworks and the rigidity matrix
We model a network by a finite graph G = (V, E). All graphs considered are finite without loops and multiple edges. Nodes of the network correspond to the vertices of G, and for every link in the network there is an edge joining the corresponding vertices of the graph. A framework G(p) is a graph G = (V, E) and a plane configuration to G(q), then p is congruent to q. Intuitively, we may consider the rigidity of bar-joint frameworks. Here, bars correspond to edges, and joints correspond to vertices. A barjoint framework is rigid if it has only trivial deformations, e.g., translations and rotations.
The rigidity matrix R(G,p) of a framework G(p) is the |E| × 2|V | matrix, whose rows correspond to the edges and whose columns correspond to the coordinates of the vertices, where | . | denotes the cardinality of a set. If e = v i v j  E, then the entry in the row e and the column v i is p(v i ) − p(v j ), the entry in the row e and the column v j is p(v j ) − p(v i ), and the other entries in the row e are zeros. If e = v i v j is not in E, then the entire row e is zeros. A framework (G, p) is called infinitesimally rigid if rank{R(G, p)} = 2|V| − 3. Infinitesimal rigidity of (G, p) implies rigidity. The converse is not true in general. However, if p is generic a configuration then rigidity also implies infinitesimal rigidity. Configuration p is generic if the coordinates of the points do not satisfy any non-zero polynomial equation with integer coefficients.

Rigid graphs
is called minimally rigid if G is rigid, and G loses its rigidity property when any one of the edges in E is removed. The combinatorial characterization of rigidity in 2-space was first given by Laman in [22]. For a subset V' V let G' = (V', E') denote the subgraph of G induced by V'.

Global rigidity and redundant rigidity
A framework (G, p) is globally rigid if, for every configuration q, framework (G, q) which is equivalent to framework (G, p) is congruent to (G, p). The essential characteristic of global rigidity is that the distance between every pair of nodes is preserved for different framework realizations, and not just those defined by the edge set. If a graph G = (V, E) is rigid but not minimally rigid, then G is called a redundantly rigid graph. For such a graph, G − e is rigid for all e  E. An edge is called a redundant edge if graph remains rigid after its removal. It is known that G has a unique generic realization in 2-space if and only if G is 3-connected and redundantly rigid [20]. A graph satisfying these two conditions, i.e., 3-connectivity and redundant rigidity, is called a globally rigid graph.

Rigidity index
Let E be a finite set and let I be a family of subsets of E. Then I forms the independent sets of a matroid M(G) if it satisfies the following three matroid axioms [20]: We refer the reader to the book of Oxley [23] for more information on matroid theory.
The rigidity matroid of the framework (G, p) is defined by linear independence of rows of the rigidity matrix R (G,p).
We note that Laman's Theorem characterizes the bases of the rigidity matroid of the complete graph on V [21].
Let G = (V, E) be a graph. Recall that a set of edges E'⊆E is independent if the subgraph induced by E' satisfies Equation (2). Let S be the collection of the sets satisfying Equation (2). We define the rigidity index, denoted by K r (G), as follows: This index is the ratio of the size of the set of independent edges over the maximal number of independent edges. Note that 0 ≤ K r (G) ≤ 1. A value of zero indicates the empty set, i.e., no links in the network. A larger value of K r indicates that the network is closer to rigidity. A value of 1 indicates a rigid network.

Redundancy index
Recall that an edge e in a rigid graph is redundant if the graph remains rigid after the removal of e. Here we give a broader definition of redundant edge that we call "generalized redundant edge." This definition of redundancy is valid for both rigid and non-rigid graphs. Let G = (V, E) be a graph, where G is not necessarily rigid. An edge e  E is called a generalized redundant edge if Let the set of generalized redundant edges in graph ) , ( E V G  be denoted by . Then the redundancy index, denoted by , is defined as, Note that 0 ≤ K u (G) ≤ 1. A value of zero indicates that there are no redundant edges in E. On the other hand, if K u (G) = 1, then this means that each edge in E is redundant. A larger value of K u indicates that a network is more robust to main its rigidity index.
It may suffice to know the redundancy index for most of the applications. However, it is possible to define higher types of redundancy indices, and that is what we will discuss next.
Let be a graph.
We generalize the notion of redundancy index for the removal of k edges, where .
Note that the redundancy index K u (G) defined above may also be called the "redundancy index of type 1," and may be denoted as K u 1 (G) to be consistent with the higher types of redundancy indices. However, in this paper, we will refer it as the "redundancy index" and use the notation K u (G) for convenience.

Complexity analysis of computing the rigidity index and the redundancy index
For a graph G with n vertices, there are polynomial algorithms for testing rigidity in O(n 2 ) time. Performing the independence test to compute the rigidity index takes the total running time of O(n 2 ) [21].
It is possible to test redundant rigidity, by removing one edge at a time, and by using the algorithm for rigidity repeatedly. So determining the redundancy index has O(mn 2 ) complexity, since rigidity has to be tested for the removal of each edge, where m is the number of edges in G. In general, determining the redundancy index of type k, has O(m k n 2 ) complexity, since rigidity has to be tested for the removal of every k-combination of m edges. There are more efficient algorithms for testing redundant rigidity in the literature, where redundant rigidity in 2-space can be decided in O(n 2 ) time. See [21,24] for more details on the algorithmic aspects.

Examples
In this section, we provide illustrative examples to demonstrate the rigidity index and the redundancy index.
A minimally rigid graph G 1 (V, E 1 ) is shown in Figure 1a. There are 2|V| − 3 edges in G 1 and the generic rigidity index K r (G 1 ) is 1. All the edges in E 1 are independent since there is no redundancy. Therefore the redundancy index K u (G 1 ) is zero. In fact, all the redundancy indices of higher orders are also zero.
A non-minimal rigid graph G 2 (V, E 2 ) is shown in Figure 1b. Its rigidity index K r (G 2 ) is 1. Note that |E|=18 and E u ( In Figure 2a, G 3 (V, E 3 ) is an example for a non-rigid graph with no redundant edges. All the edges are independent since there is no redundancy. Therefore Since the number of vertices is |V| = 9, maximal number of independent edges is 2|V| − 3 = 15. Therefore, the rigidity index K r (G 3 ) = 13/15 ≈ 0.8667. Since there is no redundancy at all in this graph, its redundancy index K u (G 3 ) is zero.
In Figure 2b, G 4 (V, E 4 ) is a non-rigid graph with redundant edges. The number of independent edges is 14. Since the number of vertices is |V| = 9, 2|V| − 3=15. Therefore its rigidity index K r (G 4 ) = 14/15 ≈ 0.9333. The set of generalized redundant The total number of edges is 16 in this graph. So its redundancy index K u (G 4 ) = 9/16 = 0.5625.

Simulation using random geometric graphs
In our simulations, we use random geometric graphs in modeling sensor networks. A set of n vertices are placed independently and uniformly at random. If the distance between any two vertices is at most the sensing radius r s , then there is an edge between these two vertices [4].
A uniform random distribution of n sensor nodes (n = 25) in an area of d×d, where the side length of the area d = 30 units, is shown in Figure 3. A depiction of a resulting graph for r s = 12 units, i.e., 40% of d (the side length of the area), is shown in Figure 4. For this random geometric graph, K r (G) = 1 and K u (G) = 1.
As r s changes, the values of the rigidity index K r (G), and the redundancy index K u (G) do also change. Plot of the rigidity index and the redundancy index against the ratio r s / d between the sensing radius r s and the side length of the area d, for the node distribution in Figure 3, are shown in Figure 5.

Average results of simulations
We generated 50 different uniform random distributions of 25 sensor nodes in an area of 30×30. Then, for each node distribution, we computed K r (G) and K u (G) as a function of the ratio r s /d between the sensing radius r s and the side length of the area d. Next, we took the average of these fifty simulations. The resulting plot is shown in Figure 6. Figure 7 presents a zoomed-in version of Figure 6 focusing on the region where K r (G) and K u (G) are getting close to the value of 1. For the average result, K r (G) becomes 1 when r s /d = 0.49, and K u (G) becomes 1 when r s /d = 0.57.

Discussion
From the simulations of the average result, we see that a network graph reaches rigidity when r s /d is approximately 0.49, and it reaches redundant rigidity when r s /d is approximately 0.57. Therefore, from the average result of K r (G) and K u (G), we observe that approximately 16 percent increase in r s transforms a rigid graph into a redundantly rigid graph. We conclude that achieving redundant rigidity imposes considerably less burden on the network once rigidity is achieved. Recall that these were the issues that we posed at the beginning of this paper. We also note that, for both the individual and the average result, K r (G) is a non-decreasing function of the ratio r s /d, while K u (G) is a non-monotonic function. Figure 1. (a) G 1 (V, E 1 ) is an example for a minimally rigid graph, and its rigidity index K r (G 1 ) = 1, and its redundancy index is zero. (b) G 2 (V, E 2 ) is a non-minimal rigid graph, and its rigidity index K r (G 2 ) = 1, and its redundancy index, = 10/18 ≈ 0.5556. Figure 2. (a) G 3 (V, E 3 ) is an example for a non-rigid graph with no redundant edges, and its rigidity index K r (G 3 ) = 13/15 ≈ 0.8667, and its redundancy index is zero. (b) G 4 (V, E 4 ) is a non-rigid graph with redundant edges, and its rigidity index K r (G 4 ) = 14/15 ≈ 0.9333, and its redundancy index K u (G 4 ) = 9/16 = 0.5625.

Conclusion and Future Work
This work presented identifications of graph invariants for generic rigidity and redundant rigidity that we termed the rigidity index and the redundancy index. These indices are scalars resulting from the combinatorial rigidity properties of a network graph. The results were demonstrated with examples and simulations.
We explored the transition from non-rigidity to rigidity and from rigidity to redundant rigidity. These indices are quantitative measures of network rigidity and they have properties that meet the demands in applications. Specifically, these indices are helpful to determine the necessary increase in sensing radii to transform a non-rigid graph to a rigid graph, and transform a rigid graph to a redundantly rigid graph.
Redundancy index can also be considered as a measure of robustness. A larger redundancy index indicates a more robust network against link losses. From a network point of view, redundant rigidity in networked systems is essential in unknown environments for a reliable performance against structural changes, where redundant rigidity ensures to maintain rigidity properties of the network when some communication links may become unavailable because of the dynamic conditions of the changing environment, such as obstruction.
Higher types of redundancy indices as defined in Section 3 will provide us information on robustness to multiple link losses and these indices deserve further investigation, which also constitutes our future work. Another possible future research direction is to determine and examine the rigidity index and the redundancy index in 3dimensional space.      Figure 5. Plot of the generic rigidity index K r (G) (plotted with solid blue line), and the redundancy index K u (G) (plotted with red dashed line), against the ratio r s /d between the sensing radius r s and the side length of the area d, for the node distribution shown in Figure 3.   Figure 6 focusing on the region where K r (G) and K u (G) are getting close to the value of 1.