2017-【技术驱动未来分会场】Graph_Realization_in_IoT：Theory_Practice_and_New_Trends_46页-22mb

报告摘要

文档总结：Graph Realization in IoT

核心内容

本文探讨了物联网（IoT）中图的实现问题，即如何根据部分测量的边长或相似性信息，确定图中各顶点在 $d$ 维空间中的坐标。图实现是IoT网络建模和分析的重要基础，尤其在定位、数据推断和网络可视化等方面有广泛应用。

主要观点

图实现的定义：给定图 $G = (V, E)$ 和每条边的权重 $\omega_{i,j}$，图实现是找到顶点坐标 $P = {p_1, p_2, \ldots, p_n} \in \mathbb{R}^d$，使得任意两个顶点 $i, j$ 之间的欧几里得距离等于对应的 $\omega_{i,j}$。
图实现的复杂性：图实现问题是NP难的，这意味着在某些特殊图结构下，很难找到有效的实现方法。
图的刚性：图的刚性意味着在外部力作用下，结构不会发生连续变形。一个图在 $\mathbb{R}^d$ 中刚性当且仅当其满足Laman条件（即每个子图的边数不超过 $2k - 3$）。
全局刚性：在 $\mathbb{R}^1$ 和 $\mathbb{R}^2$ 中，图全局刚性的必要和充分条件是图是 $(d + 1)$-连通且冗余刚性。在更高维度中，这些条件仅是必要条件。
应力矩阵与全局刚性：一个图在 $\mathbb{R}^d$ 中全局刚性当且仅当其存在一个应力矩阵 $\Omega$，其秩为 $|\mathbf{V}| - d - 1$。存在一个多项式时间的随机算法用于检测全局刚性。
图实现的算法：
- Trilateration：逐步确定每个节点的位置。
- 距离方程求解：每条边提供一个方程，用于推断节点位置。
- 全局优化：利用梯度下降法迭代优化结果。
- 组件拼接（Component Stitching）：将图分解为子图，分别求解后进行合并，适用于大规模网络。
冗余刚性（Redundant Rigid）：图在移除任意一条边后仍保持刚性。
MOCC（Most Over Constraint Components）：冗余刚性组件，具有较高的抗噪能力，是图实现中重要的可靠模块。
可扩展性与挑战：
- 在大规模网络中，计算效率和误差限制是主要挑战。
- 移动节点和非均匀分布可能导致图实现结果的翻转（flip ambiguity）。
- 图的形状影响抗噪能力，因此评估各组件的形状对提高实现精度至关重要。

关键信息

图实现问题在IoT中具有广泛应用，包括定位、数据推断和网络可视化。
图实现的复杂性取决于图的结构和边长的约束。
刚性图需要至少 $2n - 3$ 条独立边，且满足Laman条件。
全局刚性图需要满足 $(d + 1)$-连通性和冗余刚性。
算法包括Trilateration、距离方程求解、全局优化和组件拼接。
MOCC是实现过程中重要的可靠模块，有助于提高抗噪能力和计算效率。
在三维空间中，图实现用于SLAM和模式识别等3D建模任务。
在智能城市等大规模网络场景中，图实现面临计算效率和误差控制的挑战。

结构清晰要点

图实现的定义：通过部分测量的距离或相似性信息确定图中各顶点坐标。
图实现的复杂性：NP难问题，但存在某些特殊图结构使得实现可行。
刚性图的条件：
- 需要至少 $2n - 3$ 条边。
- 满足Laman条件（每个子图的边数不超过 $2k - 3$）。
全局刚性图的条件：
- 在 $\mathbb{R}^1$ 和 $\mathbb{R}^2$ 中，图必须是 $(d + 1)$-连通且冗余刚性。
图实现的算法：
- Trilateration：逐步确定节点位置。
- 距离方程：利用边长信息构建方程组。
- 全局优化：迭代优化以提高精度。
- 组件拼接：将图分解为子图，分别求解后合并。
MOCC：冗余刚性组件，具有抗噪能力，是实现过程中的关键模块。
可扩展性与挑战：
- 大规模网络面临计算效率和误差控制的问题。
- 移动节点和非均匀分布可能导致翻转和误差。
- 图的形状影响实现精度。

总结

图实现是物联网中一个关键问题，用于建模和分析网络结构。通过部分测量的距离或相似性信息，可以确定图中各顶点的坐标。图实现的复杂性取决于图的结构，而刚性图的条件包括边数和连通性。全局刚性图需要满足更严格的条件，如 $(d + 1)$-连通性和冗余刚性。多种算法可用于图实现，包括Trilateration、距离方程求解、全局优化和组件拼接。MOCC作为冗余刚性组件，在抗噪和计算效率方面具有优势。在三维空间和大规模网络中，图实现面临新的挑战，需要更高效的算法和更精确的误差控制。

展开完整摘要