图2-5凸规划算法示意图
Figure 2-5 Diagram of Convex Optimization Principle
（5） MDS-MAP定位算法
MDS-MAP定位算法是University of Missouri-Columbia的Yi Shang等提出来的。该算法属于集中式定位算法，它是利用节点间的连通信息通过Dijkstra或Floyd算法生成节点间距矩阵，然后利用多维尺度分析技术来获得节点间的位置信息。
MDS-MAP定位算法的实现主要分为以下三个步骤：
（1）首先从全局角度出发生根据给出的节点间的连通信息，如具备测距能力的邻居节点间的测量距离和不具备测量能力的节点间所赋予的距离值，生成网络拓扑连通图，然后通过最短路径法（Shortest Path Algorithm）粗略地估计每对节点间的距离，生成节点间距矩阵。
（2）将经典多维尺度分析技术应用于节点间距矩阵，从而计算出整个网络的2维或3维相对坐标系统，该坐标为相对坐标。
（3）根据信标节点的位置及信标节点的密度对（2）中所得的节点相对坐标进行转换，使之成为绝对坐标系统。
MDS-MAP定位算法基于多维尺度分析技术来进行节点定位，该算法对网络节点密度要求严格，在节点分布均匀的情况下，较少的信标节点就可以获得很好的定位结果。
MDS-MAP算法中假设每一对节点之间都是连通的，当节点密度较小时，不仅节点的定位误差会非常大，两外还会导致许多节点无法进行定位。只有网络的连通度达到一定的程度时，所有的未知节点才能够实现定位。采用该算法获得的节点坐标一般为相对位置坐标，将其转化为绝对坐标需要进行矩阵运算，在二维空间中将未知节点的相对坐标转换为绝对坐标一般至少需要3个信标节点进行辅助
运算，在三维空间中至少需要4个信标节点，因此该算法计算量和能耗一般都比较大。
表2-2对以上六种无需测距定位算法进行了比较。
表2-2无需测距定位算法比较
Table2-2 Comparison of range-free algorithm 名称 DV-HOP Centroid Amorphous APIT 凸规划 MDS-MAP 类别 分布式 分布式 分布式 分布式 集中式 集中式 网络 节点密影响较大 影响较大 影响较小 影响最大 影响较小 影响较大 信标节 点密度 影响较大 影响较大 影响较大 影响较小 影响较小 影响较大 是否需信标节定位 要额外点定位精度 否 否 是 否 否 是 好 好 一般 好 好 一般 良好 一般 一般 一般 较好 良好
2.4 本章小结
本章首先介绍了无线传感器网络的基本概念、定位的基本概念、无线传感器网络中一些常用术语、节点定位技术的性能评价标准、定位算法分类及节点定位计算方法；接着重点分析了基于测距的定位算法和无需测距的定位算法，详细介绍了各种算法的定位过程、并介绍了各种算法的性能及适用范围，然后通过表格等形式分别对基于测距的定位算法和无需测距的定位算法的网络节点和信标节点密度、定位误差和定位精度等参数进行了比较说明，分析了各个算法的优劣，并指出了针对不同定位算法所存在的问题。
各种定位算法都有各自不同的应用领域，针对不同的情况有不同的定位算法可供
选择，没有那一种算法拥有绝对的优势，在某一种场合比较适用，但应用环境一旦改变，可能这种算法的性能就会发生变化。在具体的应用环境中要综合考虑算法的特点和实际情况，对于安全和定位的各种参数要有所取舍。另外，在不同的应用中还应考虑把几种算法综合起来使用，针对同一种环境进行区域划分，不同的区域适用不同的定位算法，然后再把这些算法结合起来，这也是今后研究的一个重点。