计算机叠代算法分析论文

评职称或毕业的时候，都会遇到论文的烦恼，为此精选了《计算机叠代算法分析论文(精选3篇)》仅供参考，希望能够帮助到大家。摘要：地震资料计算机解释系统是集地震数据存储、数据分析和图形显示于一体的系统，其架构经历了不同的发展阶段。最初的系统架构利用单一站点进行解释，随着地震勘探中数据量的不断增大和三维可视化技术的应用，计算机解释系统由单一站点向网络化和集群化方向发展。

计算机叠代算法分析论文 篇1：

浅谈递归算法的教学策略

【摘要】    递归是计算机学科中的核心技术思想之一，也是程序设计教学的难点，本文简要分析的难点成因并结合实例给出应对策略。文中的例题用Python语言描述。

【关键词】    递归    组合数学    迁移

在程序设计中，我们把程序调用自身的编程技巧称为递归 [1]。它是计算机学科中的核心技术思想之一，其本质反映的是一种将复杂问题简单化的思维方法[2]。递归的思想可以概括为一个问题的解法可以通过把该问题划分成若干子问题，若子问题比较简单，则直接求解;否则，采用与原问题相同的方法对这些子问题进行再划分、求解，依次类推，直到子问题变得较为简单，可以直接求解，当求出所有子问题的解后再对其进行汇总即可得到原问题的解，则称该问题为递归问题[3]。递归这种算法设计策略，是程序设计和描述算法的一种有力工具，它将复杂的过程简单化、自动化，减轻程序的代码量，是窥视程序奥秘的一把钥匙。但通过对初学编程的学习者调查发现，相比于分支、循环、二分等概念，学习者对递归显得陌生。例如分支结构，学生可以联系生活中的分支图形，可以联系“如果、否则”等言语意义。对于递归很多学生缺乏进行联系的已有知识和经验。且大部分递归在执行过程中递归调用和回归过程是相互交替，使得学生在调试跟踪步骤时倍加困难。针对递归教学，可采取以下教学策略：

一、构造情境，理解递归思想的奥秘

递归思想的一个核心就是把大问题分解成类似的小问题，在介绍一些经典模型的时，要把递归的思想融入分析问题的过程中，构造类似的情景，让学生体会递归思想的奥妙。不能为了讲递归而单纯地讲递归，例如斐波拉契数列，如果只讲递归程序如何去求斐波拉契数列的第n项，教学到此为止则就有浅尝辄止的感觉，学生难得其味。且只讲递归的实现方法，学生会产生这样的疑惑，这个数列可用循环实现，为什么还需要用递归呢？如果我们把情境变化一下，问题设计如下：

例1：有一个宽为2，长为n的矩形，现在用宽为2长为1的瓷砖去铺，有多少种不同的铺法？例如2*2的矩形就有如图1所示的2种铺法。

对此问题的分析，还是引导学生怎样把长为n的大问题分解成规模小的子问题，和爬楼梯问题一样，从最后的一次铺设来考虑，如果是竖铺，则前面是n-1的铺地砖问题，如果是横铺，则前面是n-2的铺地砖问题，根据加法原理f（n）=f（n-1）+f（n-2），还是一个斐波拉契数列。通过这两个例子能让学生对模型意义的有了重新认识，由于这2个模型边界条件跟传统的斐波拉契数列不一样，学生加深了对边界条件重要性的认识，同时也掌握了递归解决问题的一般性思路。

二、培养整体系统性思维，克服过程恐惧心理

递归在解决问题过程中不仅包括分解的思想，也蕴含整体系统性的思想，由于递归的过程是计算机自动执行的，程序設计者无需过分的关注执行的过程，而是把子问题抽象成一个已解决的整体。

例2：汉诺塔问题，有三根柱子 （编号A、B、C），在A柱自下而上、由大到小按顺序放置n个盘子。现要求将A柱上的盘子全部移到C柱上，并保持原有大小顺序叠好。每次只能移动一个盘子，并且在移动过程中三根柱上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一柱上。

汉诺塔问题是递归教学中的一个经典案例，在教学过程中一般会让学生通过游戏体验过程，当n比较大的时候，过程就很复杂。如果跟踪每一个步骤，通过步骤来找规律，学生则很难分析出程序的框架。这时可用整体系统性的思想引导学生，要把最大的盘子从A柱移到C柱上就先要把上面的n-1个盘子移到B柱上，这里把n-1个盘子看成一个整体并把这个整体借助C柱移动到B柱，则A柱上最大的盘子可以直接到C，接下来还是把B柱上的n-1盘子看成一个系统的整体借助A柱移动到C柱。通过整体系统的方法则让学生容易理解程序的框架。

代码如下：

n=int（input（“输入盘子的数目：”））

def Hanoi（n，A，B，C）： #将A柱上面n盘子借助B柱移到C柱

if n==1：

print（A，”->”，C）#只有一个盘子，直接移动

else：

Hanoi（n-1，A，C，B） #将A上面n-1盘子借助C柱移到B柱

print（A，”->”，C）   #A移到C

Hanoi（n-1，B，A，C）  #将B柱上面n-1盘子借助A柱移到C柱

Hanoi（n，’A’，’B’，’C’）

例3：取数问题，给出长度为N的数列{a_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i×a_j，求价值之和最大的取数方案。

如对于1 3 1 5 2这5个数的最优结果是43，取数过程如下：分别取1、2、3、1、5，结果为1×1+2×2+3×3+4×1+5×5=43

初看这个问题，有点无从下手，它和递归的联系是什么？这时候可以启发学生用整体的思想取思考，如果能把1到n-1的数取法抽象成一个已知的整体，取名为f（1，n-1），而2到n的数的取法也看成一个已知的整体，取名为f（2，n），这样1到n的取数问题就被分解成a[1]*1+f（2，n）和a[n]*1+f（1，n-1）这2个子问题，在实际计算中，再把第几次取的这个参数加入进去就可以了，具体算法分析如下：设f（i ，j ， k）表示从a[i]～a[j]的第k次开始取数的最优结果。对于这N个数，编号为1、2、…、n，那么第一次只能取a[1]或者a[n]，如果取a[1]，把2～n的数的取法看成一个整体，如果取a[n]，则把1～n-1的数的取法看成一个整体。最终的结果选择a[1]×1+f（2，n，2），a[n]×1+f（1，n-1，2）两者的最大值。递归方程如下：

f（i， j， k）= max（f（i+1，j，k+1）+k×a[i] ， f（i，j-1，k+1）+a[j]×k）

边界条件：

当i等于j时表示数列中只有一个数则是必取，直接返回k×a[i]，主要代码如下：

def f（i， j， k）#i，j为取数的区间，k为第几次取数

{   if（i==j）

return k×a[i];

else

return max（f（i+1，j，k+1）+k×a[i]，f（i，j-1，k+1）+a[j]×k）;

}

三、注重知识的相互迁移，多角度思考问题

缺乏已有知识和经验是造成学习递归困难因素之一，教学中则可以利用学生已知的其他学科知识进行相互迁移。下面就以数学中的组合数学为例，让学生尝试用递归的思想来解决。在解决问题的过程中，既结合了学生原有的知识，消除学生对问题本身的陌生感。又为学生开启了另一种思路。

例4：组合数公式是指从n个不同元素中取出m（ m ≤ n ）个元素的所有组合的个数，叫做n个不同元素中取出m个元素的组合数。用符号c（ n， m） 表示。其中有这样一个公式：c（ n， m）=c（ n-1， m-1）+c（ n-1， m）。

学习者在证明这个公式时一般采用的分别计算等式的两边来证明等式成立。在程序设计教学中则可以结合递归的思想分析这个公式成立的理由，具体过程如下：首先考虑就是如何把这个大问题分解成一个较小的问题，会自然地想到，如果n变小就会把问题变得简单。对于这n个元素，用递归思想的一般方法，考虑最后一个元素的选取情况，把n个元素的问题变成n-1个元素的问题。对于最后一个元素只有取或不取这两种情况：1.如果最后的第n个元素被选中了，问题就变成了在前面1到n-1个元素中再选m-1个元素，即 c（n-1，m-1）。2.如果最后的第n个元素没有被选中了，问题就变成了在前面1到n-1个元素中要选出m个元素，即 c（n-1，m）。根据加法原理即可得出：

c（ n， m）=c（ n-1， m-1）+c（ n-1， m）

再引导学生研究边界条件，随着n的减少问题规模越来越小，规模小到什么时候就有明确的答案。完整的python代码如下：

def c（n，m）：# n个不同元素中取出m（ m ≤ n ）个元素的所有组合

if m==n：#就相当于全部选

return 1

elif m==1： #n个元素选其中的一个

return n

else：

return c（n-1，m-1）+c（n-1，m）

n=int（ input（?请输入n：”） ）

m=int（ input（?请输入m（m<=n）：”） ）

print（ c（n，m） ）

不同的人，由于知识背景和思维习惯不同，对于同一个问题，会得到不同的解决问题的思路。教师在教学过程中，应充分发挥学生的能动性，鼓励学生一题多解，用不同的方面、角度或者知识去解答问题，让学生体验不同知识、方法间的相互联系。在一题多解的过程中，完成知识的相互迁移，发散学生的思维。

参  考  文  献

[1]谭浩强. C 程序设计 [M]. 4 版. 北京：清华大学出版，2010.

[2]江苏省教育科学“十二五”规划2015年度课题“基于活动理论的信息技术教学设计研究”（项目编号：D/2015/02/405）研究成果

[3]殷人昆. 数据结构（用面向对象方法与C++语言描述）[M]. 2版. 北京：清华大学出版社， 2007： 101-102.

作者单位：徐安西    南京师范大学附属中学

[4]广东汕头聿怀初中 Train#2 Problem2

[5] 单墫.组合数学的问题与方法. 上海：华东师范大学出版社，2010

[6] 王青梅，赵革.国外案例教法研究综述[J].宁波大学学报（教育科学版）2009，第31卷，第3期，7-11.

徐安西（1982.2-），男，汉族，江苏江宁，本科，高中信息技术一级教师，研究方向：信息技术教学。

作者：徐安西

计算机叠代算法分析论文 篇2：

地震资料计算机解释系统架构的发展与展望

摘  要：地震资料计算机解释系统是集地震数据存储、数据分析和图形显示于一体的系统，其架构经历了不同的发展阶段。最初的系统架构利用单一站点进行解释，随着地震勘探中数据量的不断增大和三维可视化技术的应用，计算机解释系统由单一站点向网络化和集群化方向发展。而近来随着虚拟化和云计算技术的应用，石油勘探开发一体化云平台被广泛运用，解释系统作为云平台的一个功能模块，变得更加完善和高效。通过部署虚拟化、大数据和云计算等技术，解释系统呈现了智能化和协同化的发展趋势。

关键词：地震资料计算机解释系统;工作站;集群;虚拟化;云计算

1   引言（Introduction）

地震资料解释就是把经過处理的地震波信息利用专业的地学软件将其转变成人们可认知的地质成果的过程，是石油勘探研究中的一项重要技术手段。由于在解释过程中需要利用复杂的地学软件处理海量的地震数据，显示地下三维剖面图，因此对计算机硬件的配置要求较高，对IT资源和技术比较敏感[1]。随着软硬件的不断发展和石油勘探事业的不断进步，地震资料解释系统也经过了由简单到复杂、由单一化到网络化的发展过程。本文结合作者自身工作经历，分析了各种系统架构的特点及解释系统的未来发展趋势。

2   地震资料计算机解释系统的发展历程（Development   stages of computer interpretation system for     seismic data）

地震资料计算机解释系统经过多年的发展变化，其系统架构经历了以下几个发展阶段。

2.1   工作站单机模式

所谓工作站单机模式，就是将解释软件和数据库全部安装在一台工作站上进行解释工作。工作站安装的操作系统是Unix系统，包括Oracle公司的solaris、IBM公司的AIX和SGI公司的IRIX。这是Unix工作站进入地震资料解释领域的最初模式，由于工作站内置硬盘容量有限，因此需要在工作站上外接磁盘阵列用于存储数据，为了便于显示地震剖面，每台工作站都会配置双屏显示器。至此，工作站就具有了存储、解释和显示等功能，利用单机资源即可完成所有的解释工作，其系统架构如图1所示。这种系统架构简单、易于实现，由于早期的地震数据和解释规模都不大，因此这种架构应用比较普遍，广泛用于单个项目组或某个区块的石油勘探研究中。随着勘探解释规模的不断扩大，工作站的性能瓶颈弊端便显露出来，而且单一机器解释不利于地震工区数据的共享和多人协同工作，因此这一架构逐渐被新的模式架构所取代。

2.2   基于X-window协议的仿真登录模式架构

随着地震解释工区规模的扩大和解释用户的增多，单一工作站已不能满足石油勘探中地震资料解释工作的需要，为了满足多用户多工区的共同解释和数据资源共享，需要性能更高的计算机和容量更大的存储设备。由于Unix系统是多用户多任务的操作系统，通过将专业软件和数据统一集中安装存放，每台Unix机器即可成为一台解释服务器，再通过X-window协议利用仿真登录即可从PC终端登录到服务器进行解释工作，其架构如图2所示。

基于X-window协议的仿真登录模式彻底改变了过去的工作方式，研究人员不用再去机房上机，在办公室利用PC机就可以完成工作。在这一系统架构中，多项网络技术和服务被利用，极大方便了系统配置和管理。

2.2.1   网络附加存储（NAS： Network Attached Storage）

NAS被定义为一种特殊的专用数据存储服务器，由存储控制器、磁盘阵列和功能软件模块组成，用于为网络中的各种计算机提供数据存储、共享和备份[2]。NAS存储设备将地震工区数据统一集中管理，能实现不同用户间的使用和共享，为地震勘探解释中多用户多工区的共同解释提供了重要保障[3];同时利用NAS存储的数据快照功能，可以方便地对数据进行在线备份，有效保障了数据的安全。

2.2.2   网络文件系统（NFS： Network File System）

NFS是一种网络协议，用于网络中的计算机之间通过TCP/IP网络共享文件系统资源，利用NFS协议，可以在Unix工作站上挂载NAS存储设备，从而可以像访问本地文件一样访问NAS存储设备上的工区数据。NAS和NFS的结合使得NAS存储设备得以充分共享和高效利用，不仅解决了海量工区数据的存放问题，还能够作为各种专业软件的安装目录，各Unix工作站通过共享即可调用所有专业软件。

2.2.3   网络信息服务（NIS： Network Information Service）

NIS服务主要用来统一管理Unix账户信息，通过设置NIS域服务器，在服务器上建立用户账号，即可在域内所有Unix机器上同步账号和hosts文件等信息，从而可在域内所有主机上登录。此外还能对所有用户实现统一管理，包括设置不同权限和共享目录、分配存储空间以及用户的环境设置等。

基于X-window协议的仿真登录模式是目前应用比较广泛的系统架构，其具有工作高效、计算机资源配置使用灵活、系统冗余度高等优点，但也有其缺点，主要是通过仿真登录无法显示三维地震剖面，需要新技术、新方法来实现。

2.3   勘探开发一体化云平台

随着大数据及云计算等IT技术的不断发展，石油勘探开发业务对信息化、智能化、协同化的要求也越来越高，勘探开发一体化云平台便是适应这一新要求的模式架构。利用云平台可以实现油田数据资料共享、勘探开发数据集中管理、高性能计算、多种专业软件同时调用、远程三维显示等多种功能。地震资料计算机解释系统是云平台的重要组成部分，用户利用云平台可随时随地调用云平台上的资源，进行地震资料解释，极大地提高了工作效率。

勘探开发云平台系统架构由三部分组成：基础设施层（IaaS）、平台服务层（PaaS）和软件应用层（SaaS）。基础设施层主要包括各种服务器、存储设备和网络设备等硬件资源，以及在物理设备上虚拟出来的各种虚拟资源，它们是整个云平台的基础构件;平台服务层主要指在基础设施上搭建的各种应用平台，包括操作系统安装、数据库及专业软件配置、用户权限管理、集群系统配置、资源监控及调度、软件许可证管理等，该平台实现了所有的功能应用，即具备了向用户提供各种应用服务的条件;软件应用层提供了用户应用接口，用户通过互联网即可调用云平台上的各项应用服务，打破了时间和空间限制，实现了IT资源的高效利用[4]。云平台的系统架构如图3所示。

勘探开发云平台改变了过去不同应用系统相互独立的局面，将所有数据资料和专业软件整合起來，将各种应用建在“云端”，用户不用关心其底层架构，也不用担心计算机硬件资源性能瓶颈，只需要互联网和终端，即可按需使用相关应用服务，真正实现了IT资源最大化利用。

3 地震资料计算机解释系统的发展趋势（Development trend of computer interpretation system for seismic data）

IT技术的发展对计算机解释系统的硬件配置要求不断提高，特别是解释软件的不断升级使得相应的系统平台配置也随之提高，随着软件和硬件的共同发展，在地震资料解释领域，计算机解释系统的发展将呈现以下趋势。

3.1   计算机集群系统的应用

随着石油勘探开发中一些新技术和大型软件的不断应用，其对计算机硬件的要求越来越高，需要运算速度更快的计算机、容量更大的存储设备、IO性能更高的网络环境。特别是在地震资料的叠前反演和油田开发数值模拟中，都需要大规模的并行计算来支持，而计算机集群技术则能充分利用已有的服务器和工作站解决这一问题。

计算机集群技术通过各节点协同工作，能有效整合各节点计算资源，进行复杂的数学运算，从而完成单一机器不能完成的工作[5-6]。集群系统有如下优点：（1）负载均衡。集群系统使用专门的负载均衡算法分析各节点的负载能力，保证系统资源的充分利用，使系统的性能达到最优化。（2）系统可用性高。集群系统通过多个节点并行运算，当其中某个节点出现故障时，系统仍然能够正常工作，从而避免了过去单一服务器出现故障导致无法运算的情况。（3）系统可扩展性强。集群系统具有灵活的扩展性，当系统硬件资源无法满足解释处理业务的增长需求时，可以增加节点提高系统整体性能，利用较少的投入即可适应业务的增长需求。

3.2   虚拟化技术的部署

虚拟化是一种资源管理技术，是将计算机的各种实体资源，如服务器、内存及存储等，通过各种软件根据需要虚拟出相应的资源[7-8]。随着勘探开发云平台的不断运用，虚拟化技术作为其必要技术，在云平台上广泛部署。通过部署虚拟化技术，减少了物理服务器数量，有效整合了硬件资源，在使用中具有以下优势：降低了硬件成本和能源消耗，节省了机房空间以及管理成本;设备利用率大大提高，宿主机的优越性能得以充分利用，同时虚拟机的资源可以灵活动态调整，真正做到了按需分配;系统运维更加方便快捷，利用管理工具，大大简化了服务器的部署、管理和维护工作;系统安全性更高，虚拟化技术支持虚拟机的快速复制、备份和迁移，当系统出现故障时能快速恢复和还原，大大提高了系统的可用性和冗余度。

3.3   人工智能技术崭露头角

人工智能技术（AI）作为目前的一项前沿技术，在众多领域已经得到广泛应用，但在石油行业还处于起步阶段，虽然在有些油田的数据采集和管网监测方面有所运用，但有关地震资料解释处理的应用还在研究中[9]。目前几大国际石油公司和IT巨头纷纷开展合作，针对石油行业的智能化开展研究，相信在不久的将来，石油行业将会变得更加智能化，特别是在前期的勘探开发研究中，通过大数据分析和机器学习，由高度智能化的软件程序即可完成地震资料的处理和分析解释工作。

4   结论（Conclusion）

随着计算机技术的不断发展，地震资料计算机解释系统也经历了由简单到复杂、由单一化到并行化和集约化的发展过程，其系统架构随着IT技术的发展也越来越完善。而大数据、云计算和人工智能是当今IT技术发展的主流，相信在今后的发展过程中，这些主流技术将在地震资料计算机解释系统中发挥更大的作用，使一体化云平台架构更加完善和先进，使石油勘探研究变得更加高效和智能。

参考文献（References）

[1] CAO S Y， YUAN D. Summary of high-resolution seismic data processing technology[J]. Xinjiang Petroleum Geology， 2016， 37（1）：112-119.

[2] 汪生珠，何庆兵，欧阳欣.集群NAS存储技术在石油勘探高性能计算中的应用[J].中国科技信息，2016（6）：29-31.

[3] 曾薇，杨乐，谭颖.网络存储技术在地震数据存储中的应用[J].震灾防御技术，2011，6（3）：335-342.

[4] 于会松.勘探协同研究云平台的设计及应用[J].计算机仿真，2014，31（6）：155-157.

[5] YIN L. Discussion on the application of large-scale computer cluster in  seismic exploration data processing[J]. Computer Age， 2016（08）：1-3.

[6] HUANG Y， SHI X M. Parallel computing technology and its present situation and prospect in exploration geophysics[J]. Progress in Geophysics， 2010， 25（2）：642-649.

[7] 罗红梅.利用虚拟化技术提升地震解释软件应用能力[J].信息系统工程，2015（12）：90-91.

[8] 章婷.虚拟化技术在地震行业应用的综述[J].中国科技信息，2016（20）：51-52.

[9] 韩晓山，何庆兵.云计算技术在地震处理解释中的应用探讨[J].      電子技术与软件工程，2018（13）：9-10.

作者简介：

叶虹余（1984-），男，本科，高级工程师.研究领域：勘探开发软硬件运维，信息系统开发和管理.

作者：叶虹余

计算机叠代算法分析论文 篇3：

基于Euclidean修正的分布式加权定位算法

摘 要:传统的多维定标（MDS）算法由于采用多跳距离代替节点间的直接距离，生成的局部网络准确度低，在不规则网络中定位误差大。相对于现有的算法，引入Euclidean方法来产生多跳节点间的准确距离，并采用一种加权机制来改进协强系数，以抑制累积误差。仿真结果表明该方法在C型网络和低连通度的矩形网络定位中能取得更好的效果。

关键词:加权多维标度； 多跳距离；局部地图； 接收信号强度指示； 节点定位； 无线传感器网络

Key words: weighted MDSMAP；multihop distance；local map；Received Signal Strength Indication (RSSI)；node localization；Wireless Sensor Network (WSN)

0 引言

对于无线传感器网络（Wireless Sensor Network,WSN），不仅需要采集数据，还需要明白这些数据所来自的空间位置[1-2]。通常的定位方法按照有无锚节点分为两类。有锚节点的定位方法通常简单易行，但是缺点在于对锚节点精度的依赖性比较高，而且每个节点都要能够直接与锚节点进行通信。实际情况中，由于有的节点和锚节点距离太远，导致无法定位，无锚节点的定位算法刚好弥补了这种不足。多维定标(MultiDimensional Scaling,MDS)［3-4］技术是一种有锚节点和无锚节点相结合的算法，它利用节点间相对位置关系进行定位，在没有锚节点时也能得到节点间的相对坐标。在大型网络，尤其是那些联通度较高的网络有很好的定位效果，但是对于联通度较低的网络，定位误差非常明显。在此基础上产生了许多改进的算法：MDSMAP(P)[5]算法采用生成局部地图的方法，将多跳跳数限定在4跳范围内，之后再将局部地图进行融合，然而如果局部地图不够准确，多次融合的过程中会产生较大的累积误差。MDSMAP(P，O，R)[6]算法，用迭代更新的方式求解相异性矩阵，使得生成的相对地图更为准确。MDSMAP(W) [7]算法考虑到相隔越远的节点间其距离误差也越大，在约束条件中引入了加权系数以抑制累积误差。然而这些方法都没有从根本上计算出准确的多跳距离。本文对以上问题进行了研究，结合以上各算法优点，提出了MDSMAP(E)算法，采用Euclidean方法得到准确的多跳距离，从而明显降低了低连通度网络中的定位误差。

1 经典MDSMAP算法

若一个图的每条边长度确定且具有刚性，那么由这些边连接而成的几何图形就被完全确定了［8］。

MDSMAP(C)［9］算法通过实体间的相异性来建立相对坐标。用pij表示实体i，j之间的相异性。用dij=(xi-xj)2+(yi-yj)2表示实体i，j的欧氏距离。实体间越相似，它们的距离就越接近。用式ij=f(pij)表示估计距离。并定义代价函数

Stressl=∑ij,i≠j(ij-dij)2(1)

求解相对坐标的问题就转化为了求式(1)的最小值的问题。在经典MDS中，取ij=a+b•pij。求解式(1)的步骤是首先令P2=(p2ij)，双中心化P2得到

A=-12(I-1nE)•P2•(I-1nE) (2)

其中I为单位矩阵，E为元素全为1的矩阵。对得到的A矩阵进行奇异值分解(Singular Value Decomposition,SVD)得到矩阵B=VAV′。求得坐标矩阵

X=VA12(3)

该算法的结果并不理想，其误差主要来源于两个方面：1)对于不能直接测距的节点采用多跳距离代替其欧氏距离，结果误差较大。2)在实际情况中相异性与欧氏距离并非满足简单的线性关系，采用ij=a+b•pij表示ij=f(pij)显然是不够准确的。特别是C型网络，这些误差往往高达通信半径的1.5倍甚至更高。

为了减小欧氏距离带来的误差，MDSMAP(P，C)算法［7］构建两跳内的局部地图，距离误差得以控制，之后再将所有的局部地图通过旋转，平移变换“融合”到一起，该方法取得一定的效果。但局部地图内的最大跳数为4跳，一些实体间的欧氏距离仍然不准确，这将导致局部地图的变形。这种变形虽然十分微小，但是在多次的地图融合过程中会产生较大的误差积累，特别是在网络不规则分布的边缘处。

2 现有的改进算法

继经典MDSMAP算法之后陆续出现了一些非线性关系的MDS算法， 它们的特点都是将ij=f(pij)的关系用一个满足单调关系的表达式代替，如表1所示。

而相异性和欧氏距离并没有这么强的单调约束，pij和ij只需要满足，对于任意i，j相异性小的实体距离更近，即当pij<pkl时，ij≤kl。为了得到ij，非度量MDSMAP(P，O)［6,10］算法采用一种有效的PAV(Pool Adjacent Violators)单调回归近似计算。PAV算法将pij按照从小到大的顺序排列，然后依次检测当pij

xki=xk-1i+αn-1∑j∈M,j≠i(1-k-1ijdk-1ij)(xk-1j-xk-1i)(4)

yki=yk-1i+αn-1∑j∈M,j≠i(1-k-1ijdk-1ij)(yk-1j-yk-1i)(5)

其中:α为步长因子，M表示节点i两跳范围内所有节点的集合， n为M中的所有节点个数。

直到非度量MDS协强系数S小于容许误差ε，如式(6)所示：

S=Stressl=∑ij,i≠j(ij-dij)2∑ij,i≠jd2ij < ε(6)

非度量MDS(P，O)虽然解决了相异性和欧氏距离非线性的问题，但未解决节点多跳距离不准确的问题。

3 MDSMAP(E)

针对以上问题，对非度量MDS算法进行了以下改进：1)使用Euclidean算法计算多跳节点的间距，从而比MDS算法得到的相对地图更为精确；2)由于协强系数反映的是估算位置的欧氏距离和实际位置欧氏距离的偏差大小，因而一跳节点的间距对图形“刚度”的影响更大，跳数越多影响越小。定义加权协强系数［7］：

S = WStressl = ∑ij,i≠jωij(ij-dij)2∑ij,i≠jd2ij(7)

式中ωij=1/pij。定位步骤如下。

3.1 计算多跳节点的距离

每个节点和它附近两跳范围内的节点通信组成局部地图，通过RSSI值获得每对可通信节点间的距离。用Euclidean算法代替Floyd算法获得最短路径距离矩阵Pij。

Euclidean的具体算法如下：D是A的两跳邻居,

p2AD = p2AC + p2CD-2cos∠ACD(8)

cos∠BCD = p2BC + p2CD-p2BD2pBCpCD(9)

cos∠BCA = p2BC + p2CA-p2BA2pBCpCA(10)

当B，C在AD同侧时∠ACD=∠BCD-∠BCA，在异侧时∠ACD=∠BCD+∠BCA。

以上两种情况均有可能，但是正确的结果必须满足：

1）由于D为A的两跳邻居，故max{pAB，pBC，pCD，pBD，pAC}<pAD<min{pAB+pBD，pAC+pCD}。

2）若两种情况计算出来的pAD都满足步骤1）中的表达式，则找到D的一个邻跳邻居E，且E是B(或C)的邻居，那么用E代替C(或B)，来计算同侧和异侧情况的pAD，从4个距离值中选出两个最接近的值作为pAD。

如图3，在计算出2跳距离pAD，pAE的基础上可以计算出3跳距离pAF。

3.2 生成局部地图[11]

对每一个节点执行以下算法：

步骤1 执行经典MDS算法生成初始估计坐标(x0i,y0i)。

步骤2 计算初始欧氏距离：

d0ij = (x0i-x0j)2 + (y0i-y0j)2

步骤3 用PAV单调回归算法计算出0ij。

步骤4 对两跳范围内的所有节点，采用下面两式叠代更新局部地图坐标

xk+1i = xki-αSx/Sx(11)

yk+1i = yki-αSy/Sy(12)

作如下近似:

xki=xk-1i+αn-1∑j∈M,j≠iωij(1-k-1ijdk-1ij)(xk-1j-xk-1i)(13)

yki=yk-1i+αn-1∑j∈M,j≠iωij(1-k-1ijdk-1ij)(yk-1j-yk-1i)(14)

取α=0.1。

步骤5 更新计算欧氏距离：

dkij = (xki-xkj)2 +(yki-ykj)2

步骤6 用PAV算法更新估计欧氏距离kij。

步骤7 计算协强系数。

WStressl = ∑ij,i≠jωij(kij-dkij)2∑ij,i≠j(dkij)2(15)

步骤8 若协强系数WStressl<ε，停止算法；

3.3 地图融合

首先选择一块具有最多节点的地图作为中心地图，然后选择与这块中心地图有最多公共交点的地图作为下一次将融合的地图。本文通过旋转、镜像、平移和缩放将融合地图投影到中心地图上，可以通过公共点坐标的对比来实现，实现变换后的坐标点与其本身在主地图中坐标均方误差最小。

设Y为公共点在融合地图中的坐标矩阵，X为公共点在主地图中的坐标矩阵。Y^为投影后的坐标矩阵。于是问题变为求如下坐标变换：

Y^=sYT+lt′(16)

其中:T为旋转镜像矩阵，要求T′T=E(E为单位矩阵)，s为缩放系数，l与Y相同列数的全1向量，t为坐标平移向量矩阵，使得Y^与X的均方误差最小，即要求最小化L(s,t,T)：

L(s,t,T)=tr［X-(sYT+lt′)］′［X-

(sYT+lt′)］(17)

其中tr代表矩阵的迹(取矩阵对角元素和的操作)。

通过普鲁克分析求出使该代价函数最小的变换矩阵：

1)计算矩阵C=X′JY，其中

J=I-n-1E(18)

2)计算矩阵C的SVD分解:

C=PΦQ′(19)

3)求得旋转变换矩阵:

T=QP′(20)

4)求得缩放系数:

s=tr(X′JYT)/tr(Y′JY)(21)

5)求得平移向量矩阵

t=n-1(X-sYT)′l (22)

执行变换=sAT+lt′，将融合地图的所有节点矩阵A投影到主地图上，形成新的主地图，重复以上过程直到主地图包含所有节点，得到整张地图后再通过所有锚节点位置将相对地图通过旋转、镜像、平移和缩放变换为绝对地图。

4 算法分析

在Matlab环境下分别对矩形随机网络和C型随机网络进行了仿真。图4是200个节点随机分布在100m×100m区域内的矩形网络的一个例子。该网络通信半径15m，测距误差5%，平均网络连通度12.5，含4个锚节点(图中▲表示锚节点，○表示待定位节点)。采用MDSMAP(E)算法的误差仅为3.11%。图5是不同算法定位结果，其中○表示估计位置，线段指向实际位置。

由仿真实验结果可以看出，在网络有较大空洞处(连通度较低)，MDSMAP(C)会产生较大的定位误差，MDSMAP(P，C)通过局部地图信息融合的方法，有效控制了这些误差。而MDSMAP(P，O，R)在此基础上改进了欧氏距离和相异性关系，对全局地图进行了修正，取得了明显的效果。MDSMAP(E)使用Euclidean得到了更加准确的多跳距离，并采用加权误差度量机制，从进一步提高了算法定位的准确性。

图6是160个节点随机分布在100m×100m区域内的C型网络，通信半径15m，测距误差5%，平均网络连通度10.95，锚节点个数为4(图中▲表示锚节点， ○表示待定位节点)。定位误差图7中○表示估计位置，线段指向实际位置。

由图7可以看出，部分区域连通度相对较低的C型网络，MDSMAP(C)算法的误差达到了130%，MDSMAP(P，C)算法的误差为35.29%，较大的误差主要集中在连通度较低的C型网络“两端”，MDSMAP(P，O，R)算法通过修正的办法将误差控制在了18.7%。而MDSMAP(E )算法获得了准确的多跳距离，这相当于提高了网络的连通度，误差仅为9.93%。仿真结果表面MDSMAP(E)算法更能适应不规则网络的定位要求。

图8是50次定位实验的平均误差和连通度的关系曲线，在节点数目固定的情况下，我们通过扩大通信半径来增加连通度。由图可以看出，在连通度较低的情况下，锚节点数目对定位结果的影响较大，而连通度较高的情况下，影响较小。在平均连通度增加到30时各算法都有较小的定位误差，MDSMAP(C)算法在C型网络中的定位除外，因为虽然连通度增加了，但多跳距离的误差随着通信半径的增大也更高。而在连通度较低时MDSMAP(E)算法具有明显的优势。

5 结语

在研究了MDSMAP(C)算法和MDSMAP(P，O，R)算法的缺陷后，提出了MDSMAP(E)算法。该算法从多跳距离的计算和融合过程中误差的控制两个方面来提高定位精度。经理论分析和实验证明，在连通度较低的情况下该算法优势明显，但不足之处在于该算法复杂度高、节电能量消耗大。在无线传感器网络的实际应用上，对定位精度和能耗往往要进行折中考虑，下一步还需要设计一种分簇机制减少局部地图融合次数。

参考文献:

[1] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法 ［J］. 软件学报， 2005，16(5): 857-868.

[2] 廖先林，张铨荣，王光兴，等.无线传感器网络节点定位问题研究［J］. 武汉理工大学学报:信息与管理工程版,2007，12(5):47-51.

[3] BORG I, GROENER P. Modern multidimensional scaling theory and applications［M］.New York: SpringerVerlag，1997.

[4] COX M. Multidimensional scaling［M］. London: Chapman and Hall，1994.

[5] SHANG Y， RUML W， ZHANG Y. Improved MDSbased localization［C］// Proceedings of IEEE International Conference on Computer Communications 2004. New York:IEEE,2004:2640-2651.

[6] VIVEKANANDAN V,WONG V. Ordinal MDSbased localization for wireless sensor networks［J］. International Journal of Sensor Networks,2006,1(3/4):1-5.

[7] VO N, VO D S, CHALLA S. Weighted nonmetric MDS for sensor localization［C］// International Conference on Advanced Technologies for Communications 2008. Berlin:SpringerVerlag, 2008: 391-394.

[8] EREN T， GOLDENBERG D，WHITELEY W， et al. Rigidity computation and randomization in network localization［C］// 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.New York:IEEE，2004: 2673-2684.

[9] SHANG Y，RUML W，ZHANG Y，et al. Localization from mere connectivity［C］// Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York:ACM,2003: 201-212.

[10] 肖玲，李仁发，罗娟. 基于非度量多维标度的无线传感器网络节点定位算法［J］.计算机研究与发展，2007，44(3):399-405.

[11] 马震，刘云，沈波. 分布式无线传感器网络定位算法MDSMAP(D) ［J］.通信学报，2008，29(6):57-62.

作者：付锴 雷勇 颜嘉俊