【《无线网络传感器定位技术概述》6400字】

无线网络传感器定位技术概述目录TOC\o"1-3"\h\u28870无线网络传感器定位技术概述 -1-281371.1无线网络传感器定位 -1-278311.1.1无线网络传感器 -1-59771.1.2无线网络传感器定位基本专用术语 -1-177271.1.3无线网络传感器定位原理 -2-23931.2半正定规划 -4-36071.1.1半正定规划概述 -4-75281.1.2半正定规划形式 -5-94141.1.3半正定规划模型的建立 -5-12611.3计算机图形学基础 -7-325511.3.1计算机图形学概述 -7-20771.3.2形体在计算机内的表示 -7-284731.3.3计算机图形学在大型设备定位中的应用 -10-1.1无线网络传感器定位1.1.1无线网络传感器无线网络传感器是一种通过感知外部环境所传递的特殊物理信息，并通过自身的规律对接收到的信息做出反应，继而将获取得到的信息导出的器件或装置。由于它的感知功能和信息处理功能的需要，内部一般含有转换元件以及敏感元件。它是一种嵌入式设备，包括控制器、传感器、通信能力、计算能力。它通过对外界物理环境的感应来收集信息，再通过传感器网络把信息传送给其它的计算设备。由于近些年来与无线网络传感器相关的制造技术以及信息服务技术的飞速发展，我们已经可以制造出微型、具有弹性且低能耗的无线网络传感器。通常来说，单个传感器很难发挥大的作用，只有把它们适量地按照一定规律摆放到需要的空间环境中，这样一来可以组成一个传感器网络，再通过运用与其相适应的系统软件平台作为辅助，就能够实现状态监测、实时跟踪、环境监测等强大功能。1.1.2无线网络传感器定位基本专用术语锚节点:指那些具体位置固定且位置信息可以直接知道的节点。也叫做信标节点。未知节点：顾名思义，也就是位置不确定，需要利用已知位置与未知位置节点之间的位置信息来计算其位置的节点。邻居节点：邻居，指某些节点与某一指定节点所在的位置关系。在以某节点为圆心，传感器最大通信距离为半径所确定的圆的面积内的其他节点，即可以和某一传感器节点直接通信的其他全部节点叫做该节点的邻居节点。1.1.3无线网络传感器定位原理无线网络传感器定位技术主要是通过一些定位算法来实现的，定位算法的基本原理是通过直接或间接的方法，得到相关节点之间的距离、方位角或者其他相关联的一些信息数据。通过对这些已知信息的计算分析，并对计算结果加以修正，从而得到未知节点的准确位置信息。其中的距离信息可以通过信号发送接收时间差以及信号传送速率来间接得到。以二维平面定位为例，容易知道在二维平面中，一个未知节点需要三个已知节点来对其进行位置计算。假设三个已知节点的位置坐标分别为A（）、B（）、C（），一个未知节点的坐标为P（），在平面范围内，传感器接收传递信息的范围就是一个圆形区域，传感器由于距离信息可以测出，也就是说三个已知节点到未知节点的距离为已知的，分别为,,,那么通过平面坐标距离公式可以得到以下方程组：（2-1）对上述方程进行求解得到：上述求解过程针对的是一种理想条件下的传感器定位，如图2-1左所示，是在认为传感器之间的距离信息准确无误的情况下进行的，但在实际操作中，节点之间的信号传送往往会受到干扰，如传感器布置区域存在一些无法移动的障碍物，信号穿过障碍物比穿过空气的时间长，这种情况下测得的距离信息则是不准确的，比实际距离偏大的。如图2-1右所示，由三个传感器测量确定的三个圆相交得到一个确定的公共区域。容易知道我们所需要确定的未知节点的位置在这一确定区域内，而传感器网络定位算法，就是要通过计算在这一确定区域中找到这一未知节点，并通过优化使得计算得到的未知节点的位置与未知节点的真实位置之间的误差最小化。而无线传感器的通信距离有限，对定位的算法要求一般也比较高，以致于评价定位算法好坏的重要标准之一就是运用相应的定位算法计算得到的未知节点的位置与其实际位置的偏差大小。关于无线网络传感器定位技术的定位算法也有很多，如DV-HOP算法、凸规划算法、质心算法、APIT算法、半正定规划算法，而本论文正是基于半正定规划算法来进行计算的。图2-1无线网络传感器平面定位示意以上是以二维平面为例来解释无线网络定位的原理，在三维立体空间中，利用无线网络传感器定位的原理也是一样的，假设空间中有三个不在同一直线上的已知节点，那么每个节点所能传递并接收信息的空间范围就是一个球形空间，如果三个已知传感器的位置是在地面，那么每个节点能够传递并接收的信息的空间范围就变成半球形（地面以下可以不用考虑），如下图2-2，两个半球形相交，相交的公共部分为一个半圆形，第三个半球形与半圆形相交有一个公共点，这一点就是所要确定的未知节点的位置。图2-2空间定位示意图1.2半正定规划1.1.1半正定规划概述半正定规划（Semi-positiveDefiniteProgramming,简称SDP)问题其实是凸优化问题的一种特殊形式，它具有线性目标函数，约束条件之一是对称矩阵的仿射组合半正定，目的是对线性目标函数的极值进行求解。这个约束条件是凸的，非线性的。二十世纪六十年代，半正定规划的研究就已经开始了，Fan和Belman[38]两人在1963年第一次提出一个半正定规划问题，后来又有学者将半正定规划与控制论联系起来进行分析研究，二十世纪七十年代初期，Wolf,Donath和Cullumn[39]等人利用半正定规划对图划分算法进行研究，使得原来复杂的问题变得简单起来。而让半正定规划成为求解组合优化问题的重要工具的标志，是Shor[40]解决组合优化问题时提出利用半正定规划松弛。二十世纪九十年代，多项式时间内点算法理论由Nesterov[41]和Nemirovski[42]提出，这对于一般凸优化问题的求解是很好的。时间到达二十一世纪，也就是近些年，YinyuYe[43]将线性规划内点算法推广到半正定规划，使得半正定规划的发展再上新台阶。其相关文献中，有关传感器定位问题对应的特殊半正定规划模型可以表示为：mins.t.（2-2）如果是一个关于Z的凸函数，那么上述模型就成为一个凸优化问题，特殊情况下，如果是关于Z的线性函数，并且是一个凸集，则上述模型是一个半正定规划模型。半正定规划是一种定义在实数域上的半正定矩阵锥上的规划，它也是线性规划的一种推广。半正定线性规划的目标函数及其可行域都为线性，半正定非线性规划则容易知道，是目标函数为非线性或者其可行域为非线性[44]。半正定规划这一算法自提出至今，广泛应用于各种优化问题当中，对解决优化方面相关问题起着重要的积极作用。也正因为它是一种相当有效的算法，能够解决很多优化问题，因而本论文使用半正定规划算法作为相关定位的算法来进行定位计算。1.1.2半正定规划形式半正定规划算法的标准形式可如下：mins.t.（2-3）其中，、是实数矩阵，，是已知数据。一般来说，半正定规划问题的解为一个矩阵,且矩阵，如果矩阵满足所有的约束条件并且，那么求得的解叫做内部可行解或者严格可行解。在一些情况中也会用到SDP的对偶形式去解决相关问题，SDP的对偶形式可如下：maxs.t.（2-4）其中,,求得的解满足所有的约束条件，则称其为对偶内点内部可行解。1.1.3半正定规划模型的建立假设在一个d维空间中，有m个已知锚点（），n个未知节点(）。任意两个未知节点i和j之间的距离数据可以测量出来，也就是已知，记为，任意两个已知节点k与未知节点j之间的距离也可以通过测量知晓，记为，且任意两点距离的下界为R。由于任意节点之间传递信息过程中，信号穿过不同介质速度不一样，导致信号接收时间偏长，测量距离偏大。因此，定位问题可以描述为一个混合等式和不等式的误差最小化问题,问题模型如下：mins.t.（2-5）令为需要确定的矩阵，为第个位置为1，其余位置为0的向量，为第个位置为1，第个位置为-1，其余位置为0的向量。令,将变量松弛，并且引入松弛变量Z,则：,（2-6）原问题即可松弛为半正定规划问题，如下：mins.t.（2-7）可知矩阵有个未知变量。如果全部的测量结果都是准确无误的并且其他距离边界是可行的，即误差项和为0，那么式（2-7）即有唯一取得最小值解:（2-8）此时，必须要有，而即是我们所要确定的未知传感器的位置。通过以上分析可知，原问题的求解范围由于松弛变换的原因增加了，但所求得的最优解仍能满足原问题的约束条件。1.3计算机图形学基础1.3.1计算机图形学概述计算机图形学指的是利用计算机研究图形的表示、生成、处理和显示的一门重要的计算机学科分支。随着世界科技的进步，在过去十几年里，计算机系统的硬件、软件也发展的十分快，就目前来看，图形处理功能对于计算机来说已是十分容易实现，而且现在很多领域都在应用计算机图形学，如CAD设计、广告设计、影视娱乐等等。同时，计算机图形学技术凭借着本身的不断进步及其宽泛的应用，已成为计算机科学技术与其他应用学科之间沟通的一座桥梁。计算机图形学是一门研究图形在计算机中的处理以及显示的科学，我们平常在书籍、手机、电脑和电视等平台看到的图形，往往都有一些共同的属性，例如，他们都有几何元素和几何属性，而图片中的点、线、面、体就是几何元素，有些我们平时学习中遇到的图形，像地理中的等高线图、山体剖面图，工程制图中的工程图等，这些图形所传达的信息都是用线条表达的，具有几何元素；色彩、灰度、线宽、线型就是几何属性，而生活中比较常见的风景图等实物图，这些图形看起来比较真实，有明暗对比，也叫做明暗图，具有几何属性。通过对图形的分类，我们对不同类别的图形的处理技术也不同。在当今社会生活中，我们在学习或者工作中往往会应用到很多图片，有时是为了记录自己的生活，有时是为了更好地完成工作或者学习任务，这时候，一张出色的图片往往会起到令人意想不到的好反馈，而利用计算机对图形进行一系列的加工改造，正好可以满足我们的需求。实际应用当中，有时图形的加工处理仅仅依靠计算机图形学是不可以单独完成的，还需要靠计算机辅助几何设计和图像处理技术来共同处理完成。因此，计算机图形学这一学科的研究内容也很宽泛，涉及各个行业各个领域。同样，在当今时代背景下，我们很多人的工作学习甚至生活都离不开计算机图形学。1.3.2形体在计算机内的表示由于线框模型和表面模型都无法完整地表达出形体的三维信息，而实体模型则可以，因此对实体模型的研究很早就已经开始了，但是，由于早期没有受到关注，一直到20世纪60年代后半期，关于实体造型的相关报道一直都极少。到了70年代初期时候，美国罗彻斯特大学的PADL-1,PADL-2系统、英国剑桥大学的BUILD-1系统、日本北海道大学的TIPS-1系统、德国柏林工业大学的COMPAC系统等一些实体造型系统相继诞生。靠多面体表示形体,无法精确用曲面表示是早期的实体造型系统的共同特点。数据结构相对来说较简单、能够快速地生成和显示明暗图、集合运算是多面体模型的优点。但是，精确的曲面表示和近似的多面体逼近表示同时存在于同一系统中违背了几何定义的惟一性原则，而且，多面体模型不可以准确表示曲面模型，用多面体表示出来的模型有误差，简单地增加平面片的数量并不能够解决这个问题。所以，想要很好地解决这个问题，就需要在表示模型时采用更加精确的形体。

虽然Coons曲面、B样条曲线和曲面、Bezier曲线和曲面等设计方法在1960-1970年间被提出，但曲面造型系统自身有一定的缺陷，很难构造封闭的形体。因为复杂曲面这一问题不能被实体造型系统合理有效地解决，这在相当大程度上使得几何造型的覆盖域受束缚。于是，人们开始了新的研究。在1978年,实体造型系统Romulus被英国ShapeData公司推出,这是一次巨大的飞跃，因为它首次引入应用代数方程的形式精确表示的二次曲面。

直到20世纪80年代末,NURBS曲线曲面设计方法的出现使得形体表示有了飞速发展，它能够精确的表示出形体，使得形体的表示问题得到有效的解决。线框模型、曲面模型和实体模型是几何造型系统里3种能够有效对物体进行描述的三维模型。其中，线框模型在计算机图形学和CAD/CAM领域是最先用于表示物体的模型。线框模型，顾名思义，看上去只有一些线组成的框架，而这个框架是由点和边组成，很显然一个框架是不能表示出曲面信息的。而且它也无法明确对给定点与物体之间的关系给出定义，因此很多重要问题不能用线框模型去处理,这在很大程度上限制了它的应用范围。线框模型，也可以说是多边形网络。从直观上来说，一个多边形网络是通过运用多边形单元，最常见的如三角形，来对一个连续曲面进行分割。这也可以更加形式化描述为：用一个多元组（V，K）来定义网格M，其中模型的顶点集合（R3中的点），K是包含点之间的连接信息（Adjacencyinformation）还有顶点的连接方式以形成网格的边和面。例如，可以这样表示一个三角形构成的网络：。其中，多元组中的元素分别代表三个顶点、三条边还有其构成的三角形。

曲面模型其实是对线框模型的完善，在框架上填充了面的信息。曲面模型的建立需要参数曲线与参数曲面。而在三维空间中，参数曲线定义为参数空间（的子集）到三维空间的映射：（2-9）其中，是曲线参数，通常的取值范围是在0-1之间，曲线的起点为，终点为。典型的参数曲线公式为：（2-10）其中，是控制点，（）是调和函数，控制点集合也叫控制多边形。贝塞尔曲线是计算机图形学最常用的参数曲线之一，贝塞尔曲线的数学定义如下：（2-11）其中，是控制点，是次伯恩斯坦多项式（BernsteinPolynomial）。次伯恩斯坦多项式定义如下：（2-12）我们能够比较容易地从参数曲线扩展到参数曲面，参数曲面的参数域是的子集而不是的子集，并且需要使用三个二元函数来进行定义从参数到三维空间的映射，相关定义如下：（2-13）其中，和是曲面参数。通常，参数曲面的参数和的取值范围为0-1。参数曲面常用形式之一是张量积曲面（TensorProductSurface）,定义如下：（2-14）其中，是初始控制点，和是调和函数，此时，控制点称为曲面的控制网络（ControlNet）。依据张量积曲面，贝塞尔曲线的定义可以扩展为如下曲面形式：（2-15）其中，是控制网络中的点，是n阶伯恩斯坦多项式，是m阶伯恩斯坦多项式。但在曲面模型中，只有一些面的信息，据此并不能准确知道该物体与其他物体的位置关系，也无法得到的一些准确信息，如体积、表面积等。作为最高级的模型，物体的全部形状信息都可以被实体模型完整地表示出来,它还可以准确地表示出一个点在物体上的具体位置,这种模型能够满足物性计算和有限元分析等一些应用的要求。而实体模型的表示也有很多方式，一般分为边界表示、构造表示、分解表示。边界表示是利用形体的边界信息以及边界围成的曲面的定义来表示形体，如果可以知道一个实体所有的边界信息，这些边界就可以构成一个框架，这个框架上所具有的信息，就是形体的拓扑信息，而如果知道这些边界所围成的曲面的曲面方程，也就是形体的几何信息，那么就可以将