2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

图实现算法综述与评测分析

孙天元 王永才 李德英

孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
引用本文: 孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
Citation: SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561

图实现算法综述与评测分析


DOI: 10.16383/j.aas.2018.c170561
详细信息
    作者简介:

    孙天元  中国人民大学信息学院硕士研究生. 2015年获得中国人民大学信息学院学士学位.主要研究方向为图实现与虚拟现实. E-mail: suntyruc@163.com

    李德英  中国人民大学信息学院计算机科学与技术系教授. 1988年获得华中师范大学数学学士学位, 2004年获得香港城市大学计算机博士学位.主要研究方向为线传感器网络, 社会网络, 算法分析与设计. E-mail: deyingli@ruc.edu.cn

    通讯作者: 王永才  中国人民大学计算机系副教授. 2001年获得清华大学自动化系学习学位, 2006年获得清华大学自动化系博士学位.主要研究方向为物联网, 机器人, 大数据挖掘与分析, 算法设计与分析.本文通信作者. E-mail: ycw@ruc.edu.cn
  • 本文责任编委 段书凯
  • 基金项目:

    国家自然科学基金面上项目 11671400

    国家自然科学基金面上项目 61672524

    国家自然科学基金面上项目 61972404

A Survey and Evaluation of Graph Realization Algorithms

More Information
    Author Bio:

    SUN Tian-Yuan   Master student in the Department of Computer Sciences, Renmin University of China. He received his bachelor degree from the Department of Computer Sciences, Renmin University of China in 2015. His research interest covers graph realization and VR

    LI De-Ying   Professor in the Department of Computer Science, Renmin University of China. She received her master degree in mathematics from Huazhong Normal University in 1988 and Ph.D. degree in computer science from City University of Hong Kong, China in 2004. Her research interest covers wireless networks, mobile computin, algorithm design and analysis

    Corresponding author: WANG Yong-Cai   Associate professor in the Department of Computer Sciences, Renmin University of China. He received his bachelor and Ph.D. degrees from Department of Automation Sciences and Engineering, Tsinghua University in 2001 and 2006, respectively. His research interest covers network localization algorithms, simultaneously locating and mapping algorithms, combinatorial optimization and applications. Corresponding author of this paper
  • Recommended by Associate Editor DUAN Shu-Kai
  • Fund Project:

    National Natural Science Foundation of China 11671400

    National Natural Science Foundation of China 61672524

    National Natural Science Foundation of China 61972404

图(12) / 表(4)
计量
  • 文章访问数:  1458
  • HTML全文浏览量:  1043
  • PDF下载量:  454
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-10-21
  • 录用日期:  2018-07-15
  • 刊出日期:  2020-04-24

图实现算法综述与评测分析

doi: 10.16383/j.aas.2018.c170561
    基金项目:

    国家自然科学基金面上项目 11671400

    国家自然科学基金面上项目 61672524

    国家自然科学基金面上项目 61972404

    作者简介:

    孙天元  中国人民大学信息学院硕士研究生. 2015年获得中国人民大学信息学院学士学位.主要研究方向为图实现与虚拟现实. E-mail: suntyruc@163.com

    李德英  中国人民大学信息学院计算机科学与技术系教授. 1988年获得华中师范大学数学学士学位, 2004年获得香港城市大学计算机博士学位.主要研究方向为线传感器网络, 社会网络, 算法分析与设计. E-mail: deyingli@ruc.edu.cn

    通讯作者: 王永才  中国人民大学计算机系副教授. 2001年获得清华大学自动化系学习学位, 2006年获得清华大学自动化系博士学位.主要研究方向为物联网, 机器人, 大数据挖掘与分析, 算法设计与分析.本文通信作者. E-mail: ycw@ruc.edu.cn
  • 本文责任编委 段书凯

摘要: 图实现(Graph realization)问题研究基于节点间全部或部分距离关系测量, 在$d$维空间中计算图的顶点坐标, 使得在所实现图中各节点之间实现距离与测量距离尽可能一致.图实现问题是一个典型的优化问题, 在传感器网络定位、蛋白质结构重建、数据可视化、社交网络分析、机器人同步定位与构图等领域有着广泛应用.图实现的研究同图刚性理论有着紧密的联系, 图的刚性与全局刚性决定图的可实现性.在可实现图中, 现有工作提出几类典型的代表性图实现算法, 包括: 1)基于三边测距类方法; 2)求解距离方程类方法; 3)基于全局优化类方法; 4)基于模块拼合类方法.本文对图实现的刚性理论, 四类图实现算法的设计思想、适用条件、算法流程等进行综述分析, 通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和分析.

本文责任编委 段书凯

English Abstract

孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
引用本文: 孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
Citation: SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
  • 由于在无线传感器网络定位和蛋白质结构重建等问题中的广泛应用, 图实现(Graph realization)问题在近些年得到了理论界和应用界的关注[1-2].图实现问题可定义为给定包含$|V|=n$个节点的图模型, 已知部分节点之间的距离测量矩阵$\{d_{ij}\}$, 需在$d$维空间中求解图$G$的实现结果, 即所有顶点$V$的对应坐标$P=(p_1, p_2, \cdots, p_n)$, $p_i\in {\bf R}^d$, 使得所实现顶点位置间距离同给定距离测量的误差尽可能小的问题, 具体见式(1).

    图实现问题是众多应用问题的数学模型.传感器网络定位, 即通过节点之间的距离求解网络中传感器位置是一个典型的图实现问题[1-5].蛋白质结构重建是图实现问题另一个重要应用领域, 目前可通过多种生物及物理技术测得蛋白质中特定节点之间的距离[6-7], 从而利用所测得的距离信息将蛋白质结构在三维空间中重建[8-9].此外, 图实现问题在数据可视化、社交网络分析和机器人同步定位与地图构建等问题中也有应用, 例如数据可视化中图标分布[10], 社交网络分析中隐藏属性的挖掘[11]以及以图优化方式求解机器人同步定位与地图构建问题[12]等.

    图实现问题在1979年被Saxe证明即使在一维空间中也是NP完全问题[13], 在多维空间中为NP困难问题[14].但Saxe的证明考虑到所有图的特殊情况.在一般图(Generic graph)中, 即图中顶点坐标在有理数空间中没有整数系数使其线性组合为零的条件下, 在多项式时间内是可解的, 并且一般图在空间中是致密的, 这使得图实现问题引起应用和算法研究的广泛关注.

    图实现的主要挑战有两点:

    1) 图的唯一实现性问题:在众多应用中, 并不能提供充分的距离测量关系, 在图中边的数量较为稀疏情况下, 可能存在多个实现结果均满足已知的测量, 称为混淆的图实现(Realization ambiguity), 最终结果与真实结果产生偏差[2].为分析图实现的结果唯一性, 现有结果从图实现的刚性(Rigidity)、全局刚性(Global rigidity)、可定位性(Localizability)等方面进行了研究.相关概念介绍如下:刚性(Rigidity):如果一个图的实现$G(P)$, 在顶点邻域$U$内是可保持图的边长不变的唯一实现, 则称$G(P)$是刚性的.刚性意味着$G(P)$不存在可保持顶点间距离关系的连续形变.但刚性并不能保证$G(P)$是该图唯一的实现, 刚性图可能存在翻转混淆实现(Flipping ambiguity)或弯折混淆实现(Flex ambiguity)的情况, 即保持边距离关系不连续的混淆实现.

    全局刚性(Global rigidity)[15]:如果${\bf R}^d$空间的图实现$G(P)$的坐标是可以保持边长不变情况的唯一实现, 则称$G(P)$是全局刚性的.二维平面中图的刚性判定方法, 主要包括二维平面中的Pebble game[16]方法, 在高维空间中, 主要包括压力矩阵分析方法等.图的唯一实现性的相关综述可以参考文献[17].

    2) 图实现的算法研究:在实际应用中, 测量边通常是稀疏的, 而且距离的测量往往在有噪声的环境下获得, 使得即使图存在唯一的实现结果, 但图实现的结果有很大的误差.如传感器网络定位问题中, 距离测量一般通过信号强度的衰减或信号传播时间来确定, 受到环境影响较大; 而社会网络分析等问题中如何将节点之间的关系映射为欧氏距离也是一个关键问题.当距离的测量值存在一定的误差时, 会影响实现结果的准确性.所以图实现的算法研究, 主要是针对节点间的边的数量有限, 存在测量噪声的情况下, 研究顶点坐标计算的算法.

    现有算法主要可以分为4类: 1)基于多边测量的方法, 使用简单的多边测量手段进行节点坐标计算; 2)求解距离方程的方法, 将所有已知距离关系整体考虑求解距离方程组; 3)全局优化的方法, 将距离看作约束, 用优化模型描述坐标求解; 4)基于模块拼接的方法, 将网络划分为多个子模块, 在模块内部局部定位, 再通过全局调整将局部坐标转换到全局坐标.

    这些算法有其各自的优势和劣势, 例如多边测量方法计算简单, 但是会产生累积误差; 全局优化方法对噪声敏感; 模块拼接方法需要全局迭代.现有文献中, 仍非常缺乏对这一系列算法的深入比较和分析, 缺少对算法的适应性, 特点的分析和理解.

    为了解决此问题, 本文综述和深入比较了图实现的几种代表性算法, 包括三边测量法(Trilateration)[18]、多维尺度标定算法(Multi-dimensional scaling, MDS)[19]、半正定规划方法(Semidefinite programming, SDP)[20]、通用图优化方法(General graph optimization, $g^2 o$)[12]、优超函数算法(Scaling by majorizing a complicated function, SMACOF)[21]和几种代表性的模块拼合的方法: AAAP (As-affine-as-possible)[22]、ARAP (As-rigid-as-possible)[22]和ASAP (As-synchronized-as-possible)[23].

    本文对算法的设计思想、适用条件、算法流程等进行详细介绍, 并通过实验对比, 结合传感器网络定位这一具体应用, 对所介绍几种算法进行准确性、计算复杂度、可靠性等方面的比较和分析.

    • 图实现问题模型可抽象为:在$d$维空间中, 给定图模型$G(V, E)$, 其节点$V=(v_1, v_2, \cdots, v_n)$, 边$e(i, j)\in E$代表节点$i$与节点$j$之间有距离测量.在噪声环境下, 我们设其测量值为$d_{ij}$.给定该图中的边上距离测量集合$\{d_{ij}|(i, j)\in E\}$, 图实现问题求图中所有节点在$d$维空间中的坐标$P=(p_1, p_2, \cdots, p_n)$, $p_i\in {\bf R}^d$, 使得节点间距离$\|p_i-p_j\|$与测量的节点距离$d_{ij}$尽可能相符, 即求使(1)所示评价函数$F$最小的顶点坐标集合$P$:

      $$ F(p_1, p_2, \cdots, p_n)=\sum\limits_{(i, j)\in E} (\|p_i-p_j\|-d_{ij})^2 $$ (1)

      我们称$G(P)$为图的一个实现.图实现问题发展之初, 所讨论的距离关系一般为准确的测量, 但是随着实际应用的发展, 更多讨论在噪声环境下的测量结果[24].

      噪声模型.  设$P^0=(p_1^0, p_2^0, \cdots, p_n^0)$为该问题中节点的真实坐标, $p_i^0\in {\bf R}^d$.带有噪声的距离测量一般描述为$d_{ij}=\| p_i^0-p_j^0 \|+\varepsilon$, $\varepsilon\sim {\rm N}(0, \sigma^2)$, $\varepsilon$为距离测量的零均值高斯噪声.

      图实现按照算法设计思想, 可以划分为4类, 如表 1所示:

      表 1  算法分类表

      Table 1.  Algorithm classification

      方法类型 算法 算法特点
      三边测量类方法 Trilateration 基于几何性质, 增量式求解结果
      距离方程类方法 MDS 求解完全图的实现方法
      SDP 以半正定规划求解问题
      全局优化类方法 $g^2o$ 基于最小二乘法的迭代搜索方法
      SMACOF 基于构造辅助函数的迭代搜索方法
      模块拼合类方法 AAAP 将部分模块变形, 以仿射变换拼合模块
      ARAP 以迭代搜索的策略, 优化拼合后结果的形状偏差
      ASAP 以矩阵特征向量求解模块拼合结果

      1) 基于多边测量类方法, 例如在二维空间Trilateration[18]算法为例, 该类算法是求解图实现问题的基础算法, 由三个或三个以上已知点的坐标及已知点到目标点的距离, 通过几何方法求解目标点坐标, 并在后续计算中将新定位节点作为已知坐标节点, 继续定位其他节点.

      2) 求解距离方程类方法, 例如MDS[19]和SDP[20], 通过测距所形成的距离方程组, 求解目标点位置. MDS计算节点坐标$P_X$的变形矩阵$P_XP_X^{\rm{T}}$, 利用矩阵分解求解实现结果$P_X$, SDP算法将距离方程放缩为半正定规划问题求解.

      3) 基于全局优化类方法, 如$g^2o$[12]和SMACOF[21], 该类算法基于一组初始结果, 通过迭代搜索的方法不断提高实现结果的准确性, $g^2o$利用最小二乘法的搜索策略, SMACOF以构造辅助函数的方法获取迭代结果, 此外, 下文介绍的ARAP算法的部分过程也使用了全局优化的策略.

      4) 基于模块拼合类方法, 如AAAP[22]、ARAP[22]和ASAP[23], 该类算法将全图分解为若干个小模块, 模块之间可能存在重叠部分, 首先, 计算每个模块在局部坐标系下的实现结果, 然后, 以模块间重叠部分为约束条件, 将模块拼合到全局坐标系下.

    • 基于三边测量的方法是图实现问题的最基本解法.在二维空间中, 如果一个节点同时位于两个圆上, 则通过两个圆的圆心和半径可以确定该点两个可能的位置, 更多的测距信息可以进一步确定一个精确的位置.

      Trilateration算法[18]为典型的三边测量法, 其通过已知节点坐标和节点之间的距离测量, 增量式地求解所有节点的坐标.例如, 2维空间中, 当已知三个参考节点的坐标$(x_1, y_1)$, $(x_2, y_2)$和$(x_3, y_3)$, 以及目标节点$(x, y)$到三个节点的距离测量$d_1$, $d_2$和$d_3$, 通过求解如下方程组可获得目标节点坐标:

      $$ \left\{ \begin{array}{lr} (x_1-x)^2+(y_1-y)^2=d_1^2 \\ (x_2-x)^2+(y_2-y)^2=d_2^2 \\ (x_3-x)^2+(y_3-y)^2=d_3^2 \end{array} \right. $$ (2)

      当参考节点数量超过3时, 可以形成超定方程组.在节点位置被计算后, 将其作为已知位置节点, 再用于计算其他未知位置节点的坐标, 反复执行该过程, 直至所有节点坐标求解完毕即可.

      三边测量的算法计算简单, 但主要缺陷为:在节点连边数量不足时, 有可能出现未知节点到已知节点的连边数量均小于3, 无法精确计算下一目标节点的问题, 即对节点可定位的要求较高.此外, 在噪声环境中, 采用增量式的方法求解实现结果, 存在误差累积的问题, 即定位结果的误差会受到已计算节点的定位误差影响.尽管可结合优化方法对其进行改进[25-27], 但增量式三边定位方法在实际问题中难以大范围适用.

    • 一组距离测量通过其几何关系可表示为一个距离方程, 将图中所有连边对应的距离方程联立, 若连边数量充足且无环境噪声, 可求解得精确的实现结果.以节点$i$、$j$为例, 两个节点之间的距离可表达为以下形式:

      $$ ({\pmb e}_i-{\pmb e}_j)^{\rm{T}} P_X P_X^{\rm{T}} ({\pmb e}_i-{\pmb e}_j) =d_{ij}^2 $$ (3)

      其中, ${\pmb e}_i$是第$i$项为1, 其他项均为0的列向量.但是如上文中提及, 连边稀疏造成该方程组的解不唯一, 而测距噪声可能造成方程组中的等式并不严格成立, 因此求解距离方程的图实现方法一般对该方程变形后求解.

    • MDS (Multidimensional scaling)[19]算法最初应用于数据分析领域, 之后被应用到图实现问题中[28], 并被扩展为分布式的算法[29-30]. MDS算法对图的连通性要求较高, 要求图是完全图, 即要求已知全部的$n(n-1)/2$条边的测距值.在部分边距离未知的情况下, 常采用基于三角不等式猜边的方法, 给出所有边长[22]. MDS的算法思想为构造并求解矩阵$B$, $B=P_X P_X^{\rm{T}}$, 将矩阵$B$分解获得实现结果$P_X$.当图$G$为一个完全图时, 已知其全部的$n(n-1)/2$条边的测距值, 此时可根据距离方程求解矩阵$B$, 求解过程及算法流程如下:

      1) 获取距离矩阵的平方项$D^2=[d_{ij}^2]$;

      2) 计算半正定矩阵$B$, 矩阵中的每一项可通过距离矩阵计算得到, $B_{ij}=-\frac{1}{2}(d_{ij}^2-\frac{1}{n} \sum_{k} d_{ik}^2-\frac{1}{n}\sum_{k} d_{kj}^2 + \frac{1}{n^2}\sum_{k, l} d_{kl}^2)$

      3) 对矩阵$B$特征值分解, 求解最大的$d$个特征值$\lambda_1, \lambda_2, \cdots, \lambda_d$, 及对应的特征向量$v_1, v_2, \cdots, v_d$;

      4) 将特征值的依次置于矩阵对角线组成矩阵$A_d$, 对应的特征向量组成矩阵$V_d$, 实现结果为$P_X = V_d A_d^{\frac{1}{2}}$.

      测距噪声可能使MDS算法的计算结果出现严重误差.经典的MDS算法要求图$G$必须为完全图, 是其应用的一个主要限制.尽管可以估算节点之间距离, 将一般图补充为完全图, 但是估算得到的距离与真实情况可能存在更大的误差, 实现结果的准确性也不具备稳定性.因此在大规模的图实现中, MDS算法一般不单独使用, 更多应用于其他算法的某个环节中, 如AAAP和ASAP的初始求解过程中均使用了MDS算法.

    • SDP (Semidefinite programming)是一类算法的总称, 即将图实现问题通过条件放缩, 将距离方程转变为半正定规划问题求解, 牺牲一定的计算效率获得求解精度的提高[20].一般SDP问题定义中包括一些已知坐标的节点, 称为锚点, 标记为$P_A$, 第$k$个锚点则标记为$p_{Ak}$.定义图中的边, 若两点之间有一点为锚点, 则记为$E_A$, 若两点均为普通节点, 则记为$E_X$.设$P_X$为$n\times 2$的坐标矩阵, 则SDP问题的约束条件描述如下:

      $$ \left\{ \begin{array}{lr} Y = P_X P_X^{\rm{T}} \\ ({\pmb e}_i-{\pmb e}_j)^{\rm{T}}Y ({\pmb e}_i-{\pmb e}_j) =d_{ij}^2, \forall(i, j)\in E_X \\ \!\begin{pmatrix} p_{Ak} \\ -e_{j} \end{pmatrix}^{\rm{T}} \begin{pmatrix}I_2 & P^{\rm{T}}_X \\ P_X & Y \end{pmatrix} \begin{pmatrix} p_{Ak} \\ -e_{j} \end{pmatrix} = d^2_{kj} , \\\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad\forall(k, j)\in E_A\! \end{array} \right. $$ (4)

      以上公式即为联立之后的距离方程, 与式(3)形式相同.若所测量的边充足且无测距噪声, 通过求解以上方程组可得正确的实现结果.但是在噪声环境和问题拓扑结构是稀疏图的情况下, 以上等式并不严格成立, 所以可将上述条件放缩为半正定规划问题求解[31-33].

      若矩阵$A$为半正定矩阵, 以符号$A\succcurlyeq 0$表示, 即对任意$n$维向量${\pmb x}$, 均有$({\pmb x})^{\rm{T}}A({\pmb x})\geq 0$.将距离方程(3)转化为半正定规划问题求解的关键条件为, 将原条件$Y=P_X P_X^{\rm{T}}$放松为$Y\succcurlyeq P_X P_X^{\rm{T}}$[34].此时求解目标放松为满足半正定约束的矩阵$Y$.但在测距噪声的干扰下, 式(4)中等式约束条件之间可能冲突, 因此可通过放松等式约束避免此种情况[20].首先估计噪声强度, 将距离测量的约束放松为上界$\overline{d_{ij}}$和$\underline{d_{ij}}$下界约束的区间, 约束条件变换如下:

      $$ \left\{ \begin{array}{lr} \underline{d_{ij}}^2 \leq ({\pmb e}_i-{\pmb e}_j)^{\rm{T}} Y ({\pmb e}_i-{\pmb e}_j) \leq \overline{d_{ij}}^2, \forall(i, j)\in E_X \\ \!\underline{d_{kj}}^2 \leq \begin{pmatrix} p_{Ak} \\ -e_{j} \end{pmatrix}^{\rm{T}} \begin{pmatrix}I_2 & P^{\rm{T}}_X \\ P_X & Y \end{pmatrix} \begin{pmatrix} p_{Ak} \\ -e_{j} \end{pmatrix} \leq \overline{d_{kj}}^2 , \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad\forall(k, j)\in E_A&\! \end{array} \right. $$ (5)

      条件转换后保证了可行解的存在, 可在此约束条件下加入优化目标[32], 提高求解结果的准确性, 目标函数如(1)所示.该函数中的节点之间的距离计算$\|p_i-p_j\|$是一个非凸函数, 以此为目标函数求解半正定规划问题被证实需要昂贵的计算代价, 因此可通过变换目标函数形式近似求解该问题, 变换形式如下:

      $$ {\tilde F}(p_1, p_2, \cdots, p_n)=\sum\limits_{(i, j)\in E} |\|p_i-p_j\|^2-d^2_{ij}| $$ (6)

      式(6)以凸函数代替原始目标函数, 提高求解效率; 除此之外, 可以定义测距噪声的方差, 以最大似然函数为目标函数[35-36].

      SDP求解图实现问题在拓扑结构为稀疏图时, 由于连边数量稀少出现约束条件不足的情况, 使得实现结果的结构变形, 容易出现上文介绍翻转混淆实现和弯折混淆实现现象.此外半正定规划由于目标函数为非线性函数, 在求得可行解后, 通常以迭代搜索的方式对结果进行修正更新, 但这种方法增加了求解时间, 而且无法避免结果陷入局部最优解.实际应用中SDP算法的实现结果一般作为其他迭代算法(如SMACOF)的初始结果, 二者结合提高结果的准确率[30, 37-39], 或是在其他算法的某一过程中使用, 求解规模较小、连边数量充足的问题.

    • 图实现问题中, 基于全局优化类方法在初始实现结果的基础上, 通过目标函数确定优化策略, 迭代搜索实现结果.其迭代搜索的初始解可通过上文提及的三边测距法和求解距离方程等方法获得, 根据优化策略迭代更新每个节点的坐标取值.全局优化类算法的关键是如何通过目标函数确定迭代搜索方向和搜索步长, 不断逼近目标函数的极值点.

    • $g^2o$ (General graph optimization)[12]是一种对基于图模型的优化问题(包含图实现问题)的通用解法, 对于非线性的目标函数, 其算法思想为通过问题特质寻找其初始解, 利用目标函数的一阶泰勒展开式将其线性化, 然后对于替代后的目标函数, 一般使用高斯-牛顿法(Gauss-Newton)或莱文贝格-马夸特方法(Levenberg-Marquardt)[40]迭代优化.

      首先介绍通用的$g^2o$模型. $g^2o$的一般模型中, 定义${\pmb x}_i$为图中节点待求解状态(例如位置), $z_{ij}$为$i$节点和$j$节点之间的约束关系, $e({\pmb x}_i, {\pmb x}_j, z_{ij})$为$i$、$j$两个节点的信息对约束条件$z_{ij}$的满足程度, 其目标函数定义如下:

      $$ F(X) =\sum\limits_{(i, j)\in E} e({\pmb x}_i, {\pmb x}_j, z_{ij})^{\rm{T}}\Omega_{ij}e({\pmb x}_i, {\pmb x}_j, z_{ij}) $$ (7)

      其中, $\Omega_{ij}$为关于$i$、$j$两个节点的信息矩阵, 根据具体应用问题确定. $e({\pmb x}_i, {\pmb x}_j, z_{ij})$在当前结果${\tilde x}$处一阶泰勒展开式为

      $$ \begin{aligned} e({\tilde x_i}+\Delta x, {\tilde x_j}+\Delta x, z_{ij}) =\, &e_{ij}({\tilde x}+\Delta x) \approx \nonumber\\ & e_{ij}({\tilde x}) + J_{ij}\Delta x \end{aligned} $$ (8)

      其中, $J_{ij}$为函数$e({\pmb x}_i, {\pmb x}_j, z_{ij})$的雅克比矩阵.将一阶泰勒展开式替代原式, 变换目标函数如下:

      $$ \begin{aligned} F({\tilde x}+\Delta x)\approx&\sum\limits_{(i, j)\in E}(e_{ij}({\tilde x})+ \nonumber \\ &J_{ij}\Delta x)^{\rm{T}} \Omega_{ij}(e_{ij}({\tilde x}) + J_{ij}\Delta x) \nonumber =\\ &c + 2b^{\rm{T}}\Delta x + \Delta x^{\rm{T}} H\Delta x \end{aligned} $$ (9)

      式中, 定义$c_{ij} = e_{ij}^{\rm{T}} \Omega_{ij} e_{ij}$, $b_{ij} = e_{ij}^{\rm{T}} \Omega_{ij}J_{ij}$, $H_{ij} = J_{ij}^{\rm{T}} \Omega_{ij} J_{ij}$, 均为常数项, 且$c = \sum c_{ij}$, $b=\sum b_{ij}$, $H=\sum H_{ij}$.因此将原目标函数变换为向量$\Delta x$的二次方程, 令其导数为零, 可得以下方程:

      $$ H\Delta x^* = -b $$ (10)

      求解$\Delta x^*$即可获得此次运算的迭代结果$x^* = {\tilde x}+\Delta x^*$, 该结果为高斯-牛顿法求解的结果, 莱文贝格-马夸特方法通过在变换后方程的一阶微分中加入阻尼因子$\lambda$, 控制收敛速度[41], 其形式如下:

      $$ (H+\lambda I)\Delta x^* = -b $$ (11)

      $g^2o$算法的求解框架适用于各种基于图模型的问题, 或可以转化为图模型的问题, 该方法广泛应用于机器人同步定位与地图构建问题中[42-46].将图实现问题应用于$g^2o$算法的求解框架, $X$所表示的待求解状态即为节点的坐标, 节点之间的约束即为两个节点的欧氏距离, 约束信息即为距离的测量值, 因此$e({\pmb x}_i, {\pmb x}_j, z_{ij}) = \|p_i-p_j\|-d_{ij}$, 无额外约束信息, $\Omega$为单位矩阵, 迭代的初始解可通过三边测距法或是SDP算法求得. $g^2o$算法通过一阶泰勒展开式将目标函数的形式简化, 因此求解结果与目标函数实际的局部最优解可能存在一定偏差, 但相比于上文提及的三边测量法及求解距离方程类方法, 该算法具备更高的准确性和更强的鲁棒性.

    • SMACOF (Scaling by majorizing a complicated function)[21, 47]同样是一类基于全局优化的算法, 该算法主要应用于目标函数为复杂函数的问题中, 由于求解和解算目标函数的微分困难, SMACOF的算法思想为对目标函数$f(x)$, 如图 1所示, 以求解最小值为例, 每一次迭代中构造一个在目标区间内不小于目标函数的辅助函数$g(x, z)$, 该函数与目标函数相切于$z$点, 求解函数$g(x, z)$的最值点$x^*$, 为当前步骤的迭代结果.图 1中初始节点为$x_0$, 构建辅助函数$g(x, x_0)$, 取辅助函数的最小值点$x_1$为本次迭代结果, 本例中辅助函数为二次形式, 与原函数$f(x)$相切于点$(x_0, f(x_0))$, 之后每次迭代过程与该过程相似.

      图  1  SMACOF算法示意图

      Figure 1.  The diagram of SMACOF

      在此简单介绍SMACOF算法的推导过程.将SMACOF应用于图实现问题中的关键问题是如何构造辅助函数$g(x, z)$.构造该函数需将(1)所示图优化问题的目标函数放缩, 首先将函数$F(p_1, p_2, \cdots, p_n)$中每一个平方项展开如下:

      $$ \begin{aligned} F(p_1, p_2, \cdots, p_n) =\, & \sum\limits_{(i, j)\in E}(\|p_i-p_j\|^2 + d_{ij}^2-\nonumber\\ &2d_{ij}\|p_i-p_j\|) \end{aligned} $$ (12)

      在迭代过程中, 加入当前迭代结果$Z^{(i)}$, 即前一步搜索中辅助函数最小值对应的节点, 对上式以柯西不等式放缩, 可得:

      $$ \begin{aligned} d_{ij}\|p_i-p_j\| =\, & \frac{d_{ij}}{\|z_i-z_j\|}\|z_i-z_j\|\cdots \|p_i-p_j\|\geq \nonumber\\ & \frac{d_{ij}}{\|z_i-z_j\|}(z_i-z_j)(p_i-p_j)^{\rm{T}} \end{aligned} $$ (13)

      利用放缩后结果代替目标函数中一次项, 即可得该问题辅助函数$g(x, z)$, 形式如下:

      $$ \begin{aligned} g(x, z) = \sum\limits_{(i, j)\in E} &(\|p_i-p_j\|^2 + d_{ij}^2 -\nonumber\\ &\frac{d_{ij}}{\|z_i-z_j\|}(z_i-z_j)(p_i-p_j)^{\rm{T}} \end{aligned} $$ (14)

      求解(14)所示辅助函数的最小值点, 即可确定每次迭代过程中的迭代结果.设$N(i)$为节点$i$的邻居节点组成的集合, 每步迭代中依次选择每个节点, 固定其余$n-1$个节点, 令辅助函数$g(x, z)$对$x_{i}$的一阶微分为0, 求解结果作为本步的迭代结果:

      $$ g'(z^{(i+1)}z^{(i)}) = 0 $$ (15)
      $$ z^{(i+1)} = \frac{1}{N_i}\sum\limits_{j\in N(i)} \left(z^{(i)}_j+\frac{d_{ij}(z^{(i)}_i-z^{(i)}_j)}{\|z^{(i)}_i-z^{(i)}_j\|}\right) $$ (16)

      图实现问题中SMACOF算法每一步的迭代公式如式(16)所示, 算法实际使用时只需将该公式用于每步迭代过程中, 从初始解迭代搜索. SMACOF作为一种迭代的算法, 以辅助函数确定每次迭代的结果, 同样不可避免地可能陷入局部最优解, 因此在使用该算法时常与其他算法相结合, 例如以MDS或SDP得到初步结果, 然后作为SMACOF起始点进行迭代优化, 这种解决方法在多种模块拼合类算法的初步求解过程中得到广泛应用.

    • 基于模块拼合的算法将原图分解为多个模块, 每个模块中仅有较少节点, 如图 2所示.可定义每个模块包含选定节点及其邻居节点[29-30], 首先在模块自身的坐标系内, 计算模块内节点的局部坐标, 然后利用这些模块之间重叠的部分地将其拼接起来.这类方法中, 最简单的方法是首先局部求解, 增量式地拼合[48], 这样容易造成误差累积的现象.为了解决误差累积的问题, Patchwork[49]、LRE[50]和LLE[51]等算法通过改变拼合方式来消除误差累积, 对所有模块进行同时拼合, 避免累计误差. AAAP算法是Patchwork算法和LRE算法的一个改进版本, ARAP算法提出迭代方法进一步提高实现的准确性, ASAP通过求解矩阵特征向量将模块拼合, 有效规避了累积误差.

      图  2  模块拼合示意图

      Figure 2.  The diagram of module embedding

    • AAAP (As-affine-as-possible)[22]是基于模块拼合的算法. AAAP算法与增量式的模块拼合方法在原理上相似, 但是以构建并求解方程的方式间接降低误差的累积. AAAP算法定义模块$Q_i$为节点$i$与其所有的邻居节点组成的子图.算法第一步在每一个模块的局部坐标系中求解实现结果, 这一过程利用上文介绍的MDS和SMACOF算法, 获得$n$个局部坐标系, 第$i$个模块对应的实现结果记为$Q_i={q_{i1}, q_{i2}, \cdots, q_{iN_i }}$.

      无测距噪声影响的情况下, 可利用刚性变换(旋转、平移、翻转)将多个模块拼合在一起, 而在噪声环境中, 同一条边在不同的模块中实现结果可能不同, 因此在刚性变换时产生冲突, AAAP利用仿射变换将多个模块拼合在一起.以2维空间为例, 刚性变换中旋转和翻转可用矩阵$R$进行运算, 例如将点$(x, y)$旋转到点$(x', y')$处, 如下所示:

      $$ \begin{aligned} \left\{ \begin{array}{lr} (x', y')^{\rm{T}} = R(x, y)^{\rm{T}} \\ R = \begin{pmatrix}a & c \\ b & d \end{pmatrix} \\ a=d, b=-c, a^2+b^2=1 \end{array} \right. \end{aligned} $$ (17)

      如上文中介绍, 刚性变换为严格的平移、翻转和旋转变换, 如式(17)所示, 矩阵$R$对应刚性变换的约束条件. AAAP算法中所定义的仿射变换不考虑约束条件$a^2+b^2=1$, 而剩余条件及方程均为线性形式, 可通过线性方程组求解.该种方式求得的结果为刚性变换和缩放变换的结合, 从而规避不同模块之间的重叠部分可能存在的冲突.其求解过程为对每个模块中的每一条边, 构建以下方程:

      $$ \left\{ \begin{array}{lr} p_1 - p_k = R_1(q_{1(1)} - q_{1(k)}), k\in N(1)\\ ~~~~~~~~~~~~~~~~~~~~~~\vdots\\ p_i - p_k = R_i(q_{i(i)} - q_{i(k)}), k\in N(i) \\ a_i=d_i, b_i=-c_i, i=1, 2, \cdots, n \end{array} \right. $$ (18)

      $q_{(i(k)}$为节点$k$在模块$i$中所对应的节点.求解方程组即可获得每个模块的变换矩阵以及全图的实现结果$P$, $P=(p_1, p_2, \cdots, p_n)$. AAAP通过求解线性方程的方法将模块拼合, 其实现结果依旧存在累积误差的问题, 此外仿射变换造成的结构放缩降低了该算法的准确性, 因此在实际使用中, AAAP算法通常作为ARAP算法的初始结果, 并不单独使用.

    • ARAP (As-rigid-as-possible)[22]算法在计算机图形学中有广泛的应用[52-53]之后被应用于传感器网络定位问题.该算法提出刚性指标[54-56], 即拼合后的实现结果与每个模块自身的形状尽可能一致. ARAP算法使用AAAP算法获取初始果, 然后以全局优化的方法提高结果准确性. ARAP中迭代过程的初始结果由AAAP中的仿射变换获得, 模块之间拼合时仿射变换造成最终结果与局部求解结果不一致, 即全图的实现结果的形状与每个模块的形状存在差异, 因此可以凭借各条边的差异来体现这种差别, 定义误差函数为:

      $$ \sigma = \sum\limits_{i=1}^n \sum\limits_{j\in N(i)} \|(p_i-p_j) - R_i(q_{i(i)} - q_{i(j)}) \|^2 $$ (19)

      $q_{i(k)}$为$p_k$在第$i$个模块中对应的节点, $R_i$为模块$i$旋转到变换到最终结果对应的旋转矩阵.式(19)所示误差函数, 对于图中每一条边$(i, j)\in E$, 计算其在全局实现结果$P$相对于模块$i$和模块$j$的局部实现结果$Q_i$和$Q_j$的偏差, 通过求解误差函数的最小值使全局实现结果尽可能与每个模块的局部实现结果保持一致.给出当前全局结果$P_i$和局部求解结果$Q_i$, 式(19)中旋转矩阵$R_i$的求解定义如下:

      $$ R_{i} = \arg \min\limits_R \{ \|P_i - R_i Q_i\|_F^2 : R^{\rm{T}}R=I\} $$ (20)

      在约束条件$R^{\rm{T}}R=I$限制下$R_i$的最优解并不一定存在, 或是难以判定, 并且求解该最优化问题需要占据一定计算资源, 因此可通过普鲁克分析[57]或SVD分解[58-59]来求解变换矩阵$R_i$. ARAP算法的思想为尽可能满足最初每个模块的计算结果, 相比于AAAP和Patchwork等算法, 由于加入迭代过程, 该算法具有更好的鲁棒性.但是如果某个模块的最初实现结果较差, 将会直接影响ARAP算法的最终结果, 并且迭代过程需要更多的计算资源.因此若想在ARAP的基础上得到更优的实现结果, 可考虑如何使局部计算中的结果尽可能准确, 或是考虑如何判断局部实现结果是否可靠, 从而在最终迭代时调整每个模块的影响因子.

    • ASAP (As-synchronized-as-possible)[23]同样是首先局部求解各个模块的实现结果, 然后以模块重叠部分为约束条件将其拼合, 其特点在于拼合时采用基于矩阵特征向量的拼合方法[60]. ASAP在局部求解时使用的方法与AAAP类似, 对MDS算法提出优化, 另外该算法中可选择使用SDP算法进行局部求解.求得每个模块的局部坐标之后, 对于每两个有重叠部分的模块, 如果其重叠部分可计算两个模块的拼合所需的旋转角度, 则对下式用最小二乘法求解$r_{\theta}$:

      $$ f(\theta , t) = \sum\limits_{i=1}^S |p_i^{(k)} - (r_{\theta} p_i^{(l)}+t)|^2 $$ (21)

      其中, $S$为模块$k$和模块$l$的重叠部分的节点, $p_i^{(k)}$为节点$i$在模块$k$的局部坐标系中的坐标, $p_i^{(l)}$表示节点$i$在模块$l$的局部坐标系中的坐标, $r_{\theta}$为复数, 将求解的结果至于矩阵$R$的第$k$行, 第$l$列.如果两个模块无重叠部分或是重叠部分太少不足以求解$r_{\theta}$, 则将该位置赋值为0.之后对矩阵$R$做归一化处理, 定义对角矩阵$D$, $D_{ii} = \sum_{j=1}^N |r_ij|$, 定义$R^0 = D^{-1}R$.

      求矩阵$R^0$的特征值及特征向量, 取最大的特征值$\lambda_1^{R^0}$及所对应的特征向量$v_1^{R^0}$, 即取旋转矩阵R中的一组基向量, 向量中每一个元素包含每个模块的旋转角度[60].每个模块的旋转角度可通过式(23)确定, 每个模块旋转后可通过最小二乘法求得平移量$t_i$, 即可得一组实现结果.

      $$ r_i = e^{i\theta_i} = \frac{v_1^{R^0}(i)}{|v_1^{R^0}(i)|}, \quad i = 1, 2, \cdots , N $$ (22)

      ASAP通过一次矩阵特征向量的运算将所有模块拼合在一起, 矩阵中的每个元素通过最小二乘法求解, 增加对噪声和拓扑结构的鲁棒性.与ARAP算法类似, 每个模块的最初局部结果在之后运算中权重相等, 由于缺少判定机制, 如果局部实现结果较差将直接影响最终实现结果.

    • 本文借助传感器网络定位这一具体问题, 仿真实验比较评价上文提及的Trilateration、SDP、$g^2 o$、SMACOF、AAAP、ARAP和ASAP等算法.本文实验在二维空间中, 随机放置$N$个节点, 定义传感器传输范围$R$, 若两个节点之间的欧氏距离小于$R$, 可测得节点之间距离, 以上文介绍的噪声模型定义距离测量如下:

      $$ d_{ij}=d_{ji}=\| p_i^0 - p_j^0 \| + \varepsilon, \quad \varepsilon\sim {\rm N}(0, \sigma^2) $$ (23)

      $\| p_i^0 - p_j^0 \|$为节点$i$和节点$j$之间的真实距离, $\varepsilon$为测量噪声, 假设噪声服从均值为0, 方差为$\sigma^2$的正态分布.定义定位误差指标$\tau$如下:

      $$ \tau=\frac{1}{N} \sum\limits_{i=1}^N \| p_i - p_i^0 \| $$ (24)

      $p_i$为计算结果, $p_i^0$为实验中真值点坐标.本文在多个拓扑结构下对以上算法进行比较分析, 比较各个算法实现结果的准确性; 并调节传感器传输范围$R$, 以改变网络中节点平均度的大小, 测试以上算法在不同稠密度的拓扑结构中的执行效果; 以及调节噪声方差, 结合不同稠密度的拓扑结构, 测试各算法对环境噪声的鲁棒性.由于MDS算法需要获取图中任意两个节点之间的距离信息, 在大规模实验中并不适用, 所以在此不单独比较.仅将MDS算法应用于AAAP、ASAP算法的局部求解过程中.即在AAAP, ASAP的每个模块的局部求解过程中, 对模块中任意两个节点$i$和$j$, 若二者之间无连边, 则通过三角不等式估算二者之间的距离, 从而使测距关系满足MDS算法的需求, 然后使用MDS算法求解每个模块的实现结果.

      基于全局优化类算法所需的初始结果, 本文实验中通过SDP算法提供, 迭代次数$t$统一设置为1 000次.

    • 为比较各个算法实现结果的准确性, 设计实验在$100\times 100$的区域里随机放置100个节点, 测距噪声$\varepsilon$及拓扑结构的稠密度可调节.

      图 3所示的实验结果在节点平均度$degree_{ave}=10$, 测距噪声$\varepsilon\sim {\rm N}(0, 5^2)$的实验设定下完成.该图像为在多个拓扑结构下实验, 对不同结构中总计1 500个节点的定位结果进行统计所呈现的累计概率分布图像, 各个算法与图像的对应关系如图 3所示. AAAP算法和Trilateration算法明显劣于其他算法, 主要原因是其增量式的计算过程无法有效避免误差累积, 从而使最终实现结果仍然保留了较大的定位误差.圆形标记曲线代表的ARAP算法, 菱形标记曲线代表的SDP+$g^2 o$以及五角形标记曲线代表的ASAP算法实现结果的准确度相近, 实现结果准确度较高.以SDP算法提供初始结果的SMACOF算法和$g^2 o$, 两类算法的准确性在SDP初始结果上做出一定提升, $g^2 o$在该实验设置下优化效果更加明显.

      图  3  定位误差统计图

      Figure 3.  Location error statistics

      由于AAAP和Trilateration与其他算法在实现结果的准确性方面无可比性, 因此在准确性的实验对比中, 重点比较其余5类算法.首先考虑以上算法在不同噪声环境中的实现结果准确性.图 4所示的实验结果在节点平均度$degree_{ave}=10$, 测距噪声$\varepsilon\sim {\rm N}(0, 10^2)$的实验设定下完成.与图 3对比, 该实验增强了测距噪声, 该组实验结果的准确性明显下降, 但仍然维持在较高水平.此外, 各个算法之间的差距缩小, SDP算法的实现结果依然劣于其余4类算法.以上5类算法在实现过程中均加入优化策略以规避噪声对实现结果的影响, 对测距噪声有较强的鲁棒性.

      图  4  定位误差统计图

      Figure 4.  Location error statistics

      调节传感器传输半径$R$, 改变拓扑结构的稠密度, 再次比较各个算法的准确性.图 5所示的实现结果在节点平均度$degree_{ave}=8$, 测距噪声$\varepsilon\sim {\rm N}(0, 5^2)$的实验设定下完成.与图 3对比, SDP算法及以SDP算法为初始解的两类算法SMACOF和$g^2 o$, 三类算法的定位误差明显上升, 说明SDP算法对拓扑结构的稠密度较为敏感, 对于全局优化类算法, 确定相对准确的初始解至关重要. ARAP和ASAP两个算法的实现结果依旧保持比较良好的准确性, 两个模块拼合类算法对此范围内拓扑结构稠密度的降低有较强鲁棒性.

      图  5  定位误差统计图

      Figure 5.  Location error statistics

      为直观展示各个算法在不同稠密度的拓扑结构中的准确性, 本文以一个具体的拓扑结构为例, 通过调节节点的平均度$degree_{ave}$, 比较各类算法在不同稠密度的拓扑结构中的准确性.实验中测距噪声统一设置为$\varepsilon\sim {\rm N}(0, 5^2)$, 实验结果如图 6所示.该实验设计随机生成100个节点, 并固定这些节点的位置, 通过调节传感器传输范围$R$, 改变稠密度指标$degree_{ave}$. 图 6中真值结果所示结构为网络的实际拓扑结构, 其余拓扑图为5类算法在不同稠密度的拓扑结构中对应的实现结果.在节点的平均度$degree_ave$较大的拓扑结构中, 如$degree_{ave}=10$时, 各类算法均可获得较为准确的实现结果.当节点的平均度$degree_{ave}=8$时, 在图 6 (b)所示实验结果中, SDP算法的实现结果出现部分变形, 但是SMACOF算法及$g^2 o$算法对SDP提供的初始结果有一定程度的修正作用.当$degree_{ave}$取值继续下降, 在$degree_{ave}=6$, $degree_{ave}=4$和$degree_{ave}=3.5$三种实验设定中, SDP算法的实现结果完全变形, SMACOF算法及$g^2 o$算法的修正作用不足以弥补SDP算法的结果误差, 二者的实现结果同样出现严重变形. ARAP和ASAP两个模块拼合类的算法在节点的平均度$degree_{ave}$取值较小时, 仍然可以提供较为准确的实现结果, 如图 6 (a)中$degree_{ave}=6$所示, 但是当$degree_{ave}$取值为4和3.5时, 观察真值结果中的拓扑结果, 整个网络可以大致分为几个较为密集的部分, 各部分之间的连边较为稀疏, 此时ARAP算法和ASAP算法的实现结果出现了一定程度的变形, 关键原因为模块拼合时约束条件不足, 因此求解结果为错误的实现结果.

      图  6a  稠密度比较拓扑图

      Figure 6a.  Dense comparison topology

      图  6b  稠密度比较拓扑图

      Figure 6b.  Dense comparison topology

    • 为比较各个算法的计算效率, 统计算法在不同规模问题中的运行时间, 实验结果如图 7所示.图中横坐标为节点数目, 纵坐标为程序运行时间, 各个算法以图中所示的不同灰度值表示.为公平对比各个算法, 所有实验在相同的物理设备上完成.因为ASAP算法运行时间过长, 为方便各个算法之间的比较, 图中所显示的数据为ASAP算法运行时间的$1/2$次方.图中所示数据可以明显表明, ASAP算法的运行时间远超其他算法. ASAP算法第一阶段为计算每个模块的局部坐标, 这一过程与AAAP近似, 但是将模块拼合时, 若两个模块有重叠部分, 则需使用最小二乘法计算相应的旋转矩阵, 随着总节点数的增长, 所需计算的数量以节点数量平方的数量级增长, 因此在以上算法中ASAP执行效率最低. Trilateration算法的运行时间最短, 考虑其计算过程简单, 且实现效果较差, 因此该算法与其他算法并无可比性. SDP + SMACOF及SDP + $g^2 o$算法都以SDP算法的结果为迭代的初始结果, 二者相比, $g^2 o$比SMACOF更加高效, 且这一差距随着节点数量的增加而扩大.

      图  7  运行时间统计图

      Figure 7.  Time statistics

      为比较以上算法的计算效率, 各个算法的时间复杂度如表 3所示, 复杂度计算符号说明如表 2所示.尽管SMACOF的时间复杂度低于$g^2 o$的时间复杂度, 但是在算法实现中, SMACOF算法计算迭代结果通过循环求解, 而$g^2 o$通过矩阵运算实现, 其中加入大量优化过程, 在本文的性能评价实验中, 二者的实际运行时间受到其实现方式的影响.

      表 2  计算符号说明表

      Table 2.  Notation list

      符号 定义
      $n$ 节点数量, $|V|=n$
      $m$ 图中边的数量, $|E|=m$
      $t$ 迭代次数
      $g $ 节点最大度数
      $N $ 模块中节点数最大值

      表 3  算法时间复杂度

      Table 3.  Time complexity of different algorithms

      算法名称 时间复杂度
      Trilateration ${\rm O}(n^2)$
      MDS ${\rm O}(n^2)$
      SDP ${\rm O}(n^2m^{2.5}+m^{3.5})$
      $g^2o$ ${\rm O}(n^2t)$
      SMACOF ${\rm O}(n^2t)$
      AAAP ${\rm O}(mn^2)$
      ARAP ${\rm O}(mn^2+n^3t)$
      ASAP ${\rm O}(nN^2t+mn^2)$
    • 为比较各个算法的鲁棒性, 设计实验比较各个算法在不同稠密度的拓扑结构、不同噪声强度下的实现效果.对比各个算法准确性的试验中, AAAP和Trilateration由于其增量式的计算方法, 误差较大, 与其他算法无可比性, 因此在该实验中只比较ARAP、ASAP、SDP、SMACOF和$g^2 o$ 5类算法.该实验在$100\times 100$的区域内随机布置100个节点, 对于每一种随机分布的节点位置, 记录各个算法在不同稠密度、多个噪声强度下实现结果的定位误差, 对多个拓扑结构中的所有节点取平均值形成如图 8 $\sim$ 图 11的实验结果.在这些实验中节点的平均度$degree_{ave}$有4个取值, 分别为6, 8, 10和12, 对应图 8 $\sim$ 图 11, 测距噪声的方差强度有5种取值, 其方差分别为$1^2$, $2^2$, $5^2$, $8^2$, $10^2$, 对应图中5种不同的灰度值, 对应关系如图中所示.

      图  8  平均误差统计图

      Figure 8.  Average error statistics

      图  9  平均误差统计图

      Figure 9.  Average error statistics

      图  10  平均误差统计图

      Figure 10.  Average error statistics

      图  11  平均误差统计图

      Figure 11.  Average error statistics

      图 8中实验所示结果, SDP及以SDP算法为初始结果的$g^2 o$和SMACOF算法在节点平均度$degree_{ave}=6$的实验设定下, 实现结果明显差于ARAP和ASAP, 表明SDP算法对连边数量较为敏感; $g^2 o$算法的定位误差高于SDP算法, 表明基于错误的初始解, 优化类算法的优化指标已经丧失效用.图 9的实验结果中SDP算法的定位误差明显高于ARAP和ASAP两类算法, 略高于两类全局优化算法, 表明SDP算法在节点平均度较小的图中, 对噪声更为敏感.比较图 8 $\sim$ 图 11的实验结果, ARAP和ASAP算法对于拓扑结构的稠密度鲁棒性较强.但是图 10图 11的实验结果表明, 当节点的平均度较大时, 以上5类算法对噪声均有较强的鲁棒性.

    • 传感器网络定位是图实现问题的典型应用.大规模的传感器网络经常被布置在各种地理环境中, 搜集周围例如温度、湿度等环境信息并且在传感器之间相互通信, 如何将传感器网络实际应用于各种不同的环境, 如战场环境、水下环境和户外移动物体追踪, 也是近年来的研究热点问题.

      传感器所收集的信息需要有效传输, 需要知道信息的来源区域以及目的区域, 因此获取每个传感器的地理位置成为一个刚性需求, 然而在每一个传感器上装载GPS系统需要高昂的成本.传感器在信息传播时可利用信号强度的衰减以及信息传播时间等方式来估算两个传感器之间的距离, 在ad-hoc网络中, 若两个传感器的距离小于传输半径, 则可进行信息传输, 并估测两点之间的距离, 基于这些距离信息计算整个网络中节点的位置即为传感器网络定位问题[1-5], 是一个典型的图实现问题.

      本文所介绍的算法在传感器网络定位中均有应用. SDP算法和MDS算法最先应用于求解传感器网络定位问题[20, 28, 31-32], 但是此类方法在噪声较大、网络稠密度较低的情况下无法解算正确结果.文献[48]首先提出先局部求解, 然后拼合类的算法, 但该文献中的方法采用增量式的方法拼合各个模块, 存在累积误差的问题.为了解决累积误差的问题, AAAP和ARAP算法应用于传感器网络定位问题中[22]. ARAP和ASAP算法在实现结果的准确性和鲁棒性方面均表现出良好的性能, 若考虑计算效率, ARAP算法更适合求解传感器网络定位问题.传感器网络定位问题与实际应用相结合, 获得持续的关注和发展, 如在多跳网络中的应用[61-62], 如何增加定位结果的鲁棒性[63-64]和以分布式算法求解网络的实现结果[19, 48, 65-66].

    • 蛋白质在各项生物活动中扮演重要角色, 其组成通常由一组链式的氨基酸在空间中折叠为稳定的结构, 不同蛋白质之间结构的差异性是决定其功能的关键因素.实验测定蛋白质的三维结构主要采用核磁共振波谱法(Nuclearmagnetic resonance spectroscopy, NMR)[6]和电子顺磁共振波谱(Electron paramagnetic resonance, EPR)技术[67]与定点自旋标记(Site-directed spin label, SDSL)[68]相结合的EPR-SDSL方法[7].

      该问题中, 蛋白质中的每一个原子定义为一个节点, 实验可测得部分原子之间的距离, 需在三维空间中求解每个原子的坐标信息.蛋白质结构分析是一个典型的图实现问题, 实验测得的原子间距离包含准确距离[69-70]及带噪声的距离[8, 71]、传统的MDS算法[72]、全局优化类算法[8, 73]以及模块拼合类算法[9]在蛋白质结构分析中均有应用.考虑到该问题中距离测量噪声较小, 全局优化类方法及ASAP算法均适用于该问题, MDS和ARAP算法由于计算过程中需要猜测未知边的长度, 对实现结果造成不确定性的误差.

    • 可视化(Visualization)技术是利用计算机图形学和图像处理技术, 将数据转换成图形或图像, 并进行交互处理的理论、方法和技术.近些年来该技术快速更新和发展, 比较成熟的方法包括基于几何的技术、面向像素的技术、基于图标的技术和基于层次的技术[10].

      数据可视化问题需在低维空间中以图像的形式表示和分析高维度的原始数据, 对于两组原始数据, 可根据数据之间的相似性定义距离指标, 每组数据定义为一个节点, 利用生成的距离信息可在低维空间中求解基于原始数据的一组实现结果.当以散点图[74]和符号图[75]描述原始数据时, 可利用图实现问题的求解方法计算图中元素的状态信息.在数据可视化问题中, 图中边的测量较为稠密, 并且距离的测量并不严格符合几何结构, 全局性求解方法MDS和SDP算法更适用于该问题.

    • 社交网络是当前学术和产业界的研究热点, 其中每一个用户或个体可定义为一个节点, 节点之间的距离可通过用户之间属性的相似性定义.例如将行为定义为节点, 不同行为之间通过在同一个体上发生的次数定义距离, 基于距离信息通过图实现方法求解不同行为在二维空间中的坐标分布, 从而判定哪些行为更可能发生于同一个体[11].

      图实现问题可应用于分析网络的整体性质[11]和基于网络结构、用户行为的挖掘[76]等问题中.目前社交网络的构建通常基于用户之间的关注关系等.此外, 图实现问题可用于对已有结构的检测[77], 从而修正社交网络的拓扑结构.该问题中图中边的测量与数据可视化问题相似, MDS算法更适用于网络整体的性质分析, 而模块拼合类算法如ASAP更适合于局部性质的挖掘.

    • 机器人在一些无法使用GPS定位的环境中执行任务时, 一个重要的需求是确定自身位置, 同时构建周围环境地图, 进而搜集环境信息和导航, 该问题被称为机器人同步定位与地图构建(SLAM)问题.近些年来, 伴随着扫地机器人、服务机器人等日益流行, 该问题得到广泛关注.一种普遍的算法为采用滤波的方法求解此问题, 如基于卡尔曼滤波[78-79]、粒子滤波[80-81]、信息滤波[82-83]的方法; 另一类求解方法为图优化算法[84-87], 该算法模型为$p(X_{1: T}, M|Z_{1: T}, U_{1: T}, X_0)$. $X_{1: T}$为机器人每个时刻的位置, $M$为周围环境信息, 抽象为$K$个节点的位置, $Z_{1: T}$为观测信息, 即在每个时刻机器人测得的自身到环境中$K$个节点的距离(在感知范围以内), $U_{1: T}$为控制信息, 可以推测机器人相邻两个时刻$X_i$和$X_{i-1}$之间的相对位移, $X_0$为机器人的起始位置.该问题中已知节点$X_0$及由$Z_{1: T}$和$U_{1: T}$获得的距离信息, 需计算环境中$K$个节点和机器人自身所有时刻的位置.该问题定义与图实现相似, 但测量信息中通常包含角度测量, 已有较为成熟的求解工具包$g^2 o$[12], 通过迭代搜索的方法不断优化全局实现结果.

      此外, 三维的同步定位与地图构建问题中, 图实现问题在三维场景的还原和平面重现等问题中有广泛应用.该类问题通常以ARAP算法[22]为基础, 可通过图像信息与3D模型对周围场景进行3D建模[88-89].

    • 本文比较和分析了图实现的几类代表性算法, 包括三边测量法(Trilateration)、求解距离方程的方法(主要包括多维尺度标定算法(Multi-dimensional scaling, MDS)、半正定规划方法(Semidefinite programming, SDP))、基于全局优化的方法(主要包括通用图优化(General graph optimization, g2o)、优超函数算法(Scaling by majorizing a complicated function, SMACOF)方法)、基于模块拼合的算法(AAAP (As-affine-as-possible)、ARAP (As-rigid-as-possible)和ASAP (As-synchronized-as-possible)).以上算法性能分析对比情况如表 4所示.

      表 4  算法比较表

      Table 4.  Algorithm comparison

      方法类型 算法 准确性 计算效率 鲁棒性(稠密度) 鲁棒性(噪声)
      三边测量类方法 Trilateration $\bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar$
      距离方程类方法 MDS $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$ $\bigstar$ $\bigstar \bigstar$
      SDP $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar$
      全局优化类方法 $g^2o$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$
      SMACOF $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$
      模块拼合类方法 AAAP $\bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar$ $\bigstar$
      ARAP $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$
      ASAP $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar$ $\bigstar \bigstar \bigstar \bigstar \bigstar$ $\bigstar \bigstar \bigstar \bigstar$

      Trilateration算法和AAAP算法虽然可快速获得计算结果, 但是其实现结果的准确性存在累积误差问题, 基本不应用于实际问题.求解距离方程的两类算法, MDS算法对拓扑结构稠密度要求较高, SDP算法对拓扑结构稠密度十分敏感, 在图中边的数量较为稀疏的情况下, 此类算法的求解结果误差较大.基于全局优化的两类方法, 拥有较高的准确性和较强的鲁棒性, 但是其实现结果的优劣多数情况下取决于其初始结果的选取, 在图实现问题模型的求解过程中, 迭代优化过程仅需要较少的额外计算资源, 在众多实际问题中, 通常会选择全局优化类方法提高实现结果的准确性.基于模块拼合类方法中, ARAP算法和ASAP算法的拥有较高的准确性, 并且对拓扑结构的稠密度以及测距噪声的强度均有较强的鲁棒性, 但是ASAP算法需要占据大量的计算资源, 不适用于大规模的网络结构.

      本文的实验结果表明ARAP算法在准确性、计算效率和鲁棒性等方面均表现出良好的性能, 但是此类算法的结果与模块局部实现结果的准确性紧密相关.因此如何判别各个模块局部结果的准确度成为提高现有算法的关键问题.本文在讨论图的唯一性实现问题时简单介绍的刚性理论, 相关的理论结果可以为模块实现结果的准确性提供先验知识, 并且可以通过这些先验知识在拼合过程中对各个模块赋予权重, 进一步提高结果的准确性.此外, 可以根据刚性理论设计更多的模块划分的策略, 获得拥有更加准确的实现结果的模块.刚性理论不仅提供了图结构性质的判别方法, 若将其应用于图实现问题的求解阶段, 可以期望, 将显著提高实现结果的准确性和对稠密度、测距噪声的鲁棒性.

参考文献 (89)

目录

    /

    返回文章
    返回