The effects of random geometric graph structure and clustering on localizability of sensor networks
Graph rigidity provides the conditions of unique localizability for cooperative localization of wireless ad hoc and sensor networks. Specifically, redundant rigidity and 3-connectivity are necessary and sufficient conditions for unique localizability of generic configurations. In this article, we in...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-12-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1177/1550147717748898 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850228771571892224 |
|---|---|
| author | Tolga Eren |
| author_facet | Tolga Eren |
| author_sort | Tolga Eren |
| collection | DOAJ |
| description | Graph rigidity provides the conditions of unique localizability for cooperative localization of wireless ad hoc and sensor networks. Specifically, redundant rigidity and 3-connectivity are necessary and sufficient conditions for unique localizability of generic configurations. In this article, we introduce a graph invariant for 3-connectivity, called 3-connectivity index. Using this index along with the rigidity and redundancy indices provided in previous work, we explore the rigidity and connectivity properties of two classes of graphs, namely, random geometric graphs and clustered graphs. We have found out that, in random geometric graphs and clustered graphs, it needs significantly less effort to achieve 3-connectivity once we obtain redundant rigidity. In reconsidering the general conditions for unique localizability, the most striking finding in random geometric graphs is that it is unlikely to observe a graph, in which 3-connectivity is satisfied before the graph becomes redundantly rigid. Therefore, in random geometric graphs, it is more likely sufficient to test only 3-connectivity for unique localizability. On the contrary to random geometric graphs, our findings indicate that 3-connectivity may be satisfied before the graph becomes redundantly rigid in clustered graphs, which means that, in clustered graphs, we have to test both redundant rigidity and 3-connectivity for unique localizability. |
| format | Article |
| id | doaj-art-26da43e0f2e44efb984f9ec693ef4046 |
| institution | OA Journals |
| issn | 1550-1477 |
| language | English |
| publishDate | 2017-12-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-26da43e0f2e44efb984f9ec693ef40462025-08-20T02:04:25ZengWileyInternational Journal of Distributed Sensor Networks1550-14772017-12-011310.1177/1550147717748898The effects of random geometric graph structure and clustering on localizability of sensor networksTolga ErenGraph rigidity provides the conditions of unique localizability for cooperative localization of wireless ad hoc and sensor networks. Specifically, redundant rigidity and 3-connectivity are necessary and sufficient conditions for unique localizability of generic configurations. In this article, we introduce a graph invariant for 3-connectivity, called 3-connectivity index. Using this index along with the rigidity and redundancy indices provided in previous work, we explore the rigidity and connectivity properties of two classes of graphs, namely, random geometric graphs and clustered graphs. We have found out that, in random geometric graphs and clustered graphs, it needs significantly less effort to achieve 3-connectivity once we obtain redundant rigidity. In reconsidering the general conditions for unique localizability, the most striking finding in random geometric graphs is that it is unlikely to observe a graph, in which 3-connectivity is satisfied before the graph becomes redundantly rigid. Therefore, in random geometric graphs, it is more likely sufficient to test only 3-connectivity for unique localizability. On the contrary to random geometric graphs, our findings indicate that 3-connectivity may be satisfied before the graph becomes redundantly rigid in clustered graphs, which means that, in clustered graphs, we have to test both redundant rigidity and 3-connectivity for unique localizability.https://doi.org/10.1177/1550147717748898 |
| spellingShingle | Tolga Eren The effects of random geometric graph structure and clustering on localizability of sensor networks International Journal of Distributed Sensor Networks |
| title | The effects of random geometric graph structure and clustering on localizability of sensor networks |
| title_full | The effects of random geometric graph structure and clustering on localizability of sensor networks |
| title_fullStr | The effects of random geometric graph structure and clustering on localizability of sensor networks |
| title_full_unstemmed | The effects of random geometric graph structure and clustering on localizability of sensor networks |
| title_short | The effects of random geometric graph structure and clustering on localizability of sensor networks |
| title_sort | effects of random geometric graph structure and clustering on localizability of sensor networks |
| url | https://doi.org/10.1177/1550147717748898 |
| work_keys_str_mv | AT tolgaeren theeffectsofrandomgeometricgraphstructureandclusteringonlocalizabilityofsensornetworks AT tolgaeren effectsofrandomgeometricgraphstructureandclusteringonlocalizabilityofsensornetworks |