Graph invariants for unique localizability in cooperative localization of wireless sensor networks: Rigidity index and redundancy index
Graph invariants for unique localizability in cooperative localization of wireless sensor networks: Rigidity index and redundancy index
复制标题
DOI：
10.1016/j.adhoc.2016.02.012
复制
发表时间：
2015-02
期刊：
影响因子：
4.8
通讯作者：
T. Eren
中科院分区：
文献类型：
--
作者：
T. Eren
刚性理论使我们能够明确无线传感器网络协作定位问题中唯一可定位的条件。针对无线传感器网络中的定位问题，提出了一种通过图不变量来度量图结构的(I)类刚性和(II)广义冗余刚性性质的组合刚性方法。我们将刚性指数定义为基于独立边集合的图不变量。它的值在0到1之间，它表明我们离刚性有多近。全局刚性需要冗余刚性，这与图的唯一实现有关。此外，冗余刚性还在网络系统中针对结构变化(例如链路损失)提供了刚性健壮性。这里，我们给出了一个更广泛的冗余边的定义，我们称之为“广义冗余边”。这种冗余度的定义对刚性图和非刚性图都有效。接下来，我们将冗余指数定义为基于广义冗余边的图不变量。它也有一个介于0和1之间的值，它表示图形中的冗余百分比。这两个指标让我们可以探索从非刚性到刚性的过渡，以及从刚性到冗余刚性的过渡。图上的例子演示了这种方法。从传感器网络的角度来看，这两个指标使我们能够评估传感器的感知半径对网络刚性特性的影响，从而检验传感器网络的局部化程度。在仿真中，我们利用随机几何图和聚类图，通过刚性指数和冗余度指数来评估定位所需的感知半径的变化。
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. 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. 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 and clustered graphs in simulations.