感應式網路中的剛性性質以及唯一定位問題

Abstract

在感應式網路中，有些點知道本身的所在位置，而其他的點經由計算它們與鄰居之間的距離去決定自己的所在位置，我們將計算這些點的所在位置的過程稱之為網路定位。如果一個網路定位問題有唯一解，則稱之為可被解決的。在文獻[1]中證明了網路定位問題是可被解決的，如果其對應的基礎圖是具有全範圍剛性性質（亦即三連通、且具有多餘的剛性性質）。在文獻[5]中，Jacobs和Hendrickson提出了一個演算法來辨識一個給定的圖是否具有剛性性質。我們稱一個圖為具有多餘的剛性性質，假如我們移掉任何一個邊之後，此圖還具有剛性性質。在這篇論文中，我們將會提供數個從具有剛性性質的圖去建構一個新的具有剛性性質的圖的方法，我們也會提出一個電腦程式來解決唯一定位問題；換句話說，我們的程式可以判斷一個給定的圖是否具有全範圍剛性性質，我們也將會提出一些實驗的結果。

In a sensor network, some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. The process of computing the locations of the nodes is called network localization. A network localization problem is solvable if it has a unique solution. It has been proven in[1] that a network localization problem is solvable if and only if its corresponding grounded graph is globally rigid (i.e., 3-connected and redundantly rigid). A graph G is redundantly rigid if G-e is rigid for any edge e in G. In [5],Jacobs and Hendrickson have proposed an elegant algorithm to check if a given graph is rigid. In this thesis, we will provide several ways to construct rigid graphs from rigid graphs. We will also implement a computer program for solving the unique localization problem; in other words, our program can check if a given graph is globally rigid. Some experimental results will also be proposed.