定位问题是无线传感器网络中最基本的问题之一,本文研究的重点是定位问题中的可定位性问题和定位算法问题。对于任一给定网络,并非其中所有节点的位置都可以通过距离测量计算出相应的位置。可定位性问题就是判断一个网络或者网络中的某个节点,在给定的距离约束下,是否可以唯一确定其位置。从图论角度出发,可以得到图的可定位性条件；从解的存在性出发,可以得到代数的可定位性条件。在识别出可定位节点之后,如何来计算这些节点的坐标,尤其是,如何只利用局部信息来计算坐标,就是定位算法所要关心的问题。本文首先利用图的刚性理论,研究了二维平面下传感器网络的可定位性条件以及定位算法。我们给出了一组以簇集为单位的可定位性的充要条件。基于这组条件,我们提出了一种新的序贯式的、以簇为单位的定位算法。该算法从一组锚节点集合出发,序贯式的扩展这个集合,直到所有的可定位节点都被识别出来。该算法可以通过分布式的方式来实现,只需要利用局部信息就可以判断以簇为单位的节点的可定位性。当距离测量带噪音时,该定位算法可以通过求解一个最小二乘的优化问题来计算节点坐标。我们给出了针对此优化算法的一种新的初始化方法,来提高定位精度,并且获得了更好的鲁棒性。接下来,本文还研究了如何利用质心坐标来分布式的计算传感器节点的位置。质心坐标的绝对值可以完全由节点间的距离测量计算得来。使用质心坐标,可以将距离与坐标间的非线性约束转化成线性约束,并且,可以得到一个线性系统来计算节点坐标。但是,引入质心坐标之后,需要面临两个问题：首先,如何只利用距离信息,来判定质心坐标的符号；其次,如何设计一个稳定器,使得计算坐标的线性系统能够保证收敛。在本文中,我们给出了利用距离信息来判定符号的准则,并且,还给出了一个稳定器存在的充分条件,以及如何用集中式或者局部集中式的方法来设计这个稳定器的方法。除此之外,我们还从图的角度和代数角度,分别给出了网络可定位性的充要条件。最后,我们解决了如何利用相对位置信息来对传感器网络中的节点进行分布式定位的问题。当每一个传感器节点都拥有一个独立的局部坐标系,并且可以测量到一定距离和角度范围内的邻居节点的相对位置时,一个传感器网络可以被建模成有向图。从解的存在性角度,我们给出了这一类传感器网络可定位性的代数条件。同时,从代数图论的角度出发,利用有向图的性质,我们发现这一类传感器网络能够被定位,等价于每个节点相对于锚节点来说都应该是2-可达的。基于此,对于一个满足可定位条件的传感器网络,我们给出了如何利用它的局部信息,来分布式的、迭代的计算节点的全局坐标。这一定位算法的收敛同样依赖于一个对角稳定器的设计。我们证明了,该对角稳定器的存在依赖于有向图的拓扑性质。我们定义了一个一般性的框架,并且证明,在此框架下,只要网络所对应的有向图中每个点都是对于锚节点2-可达的,那么几乎一定存在一个对角稳定器使得算法收敛。