无线传感器网络点定位技术学习教案

1、会计学1无线传感器网络点定位无线传感器网络点定位(dngwi)技术技术第一页，共40页。无线传感器网络节点定位：依靠网络中少量的位置已知的节点，无线传感器网络节点定位：依靠网络中少量的位置已知的节点，通过邻居节点间有限的通信和某种定位机制通过邻居节点间有限的通信和某种定位机制(jzh)确定网络中所确定网络中所有未知节点的位置。有未知节点的位置。节点定位在实际应用中包含两种含义：节点定位在实际应用中包含两种含义： 自定位自定位确定节点自身在系统中的位置确定节点自身在系统中的位置 目标定位目标定位确定目标节点在系统中的位置确定目标节点在系统中的位置第八章 无线传感器网络节点定位(dngwi)技术l

2、 节点定位技术(jsh)概述第2页/共39页第1页/共39页第二页，共40页。信标节点：已知自身位置信息的节点，可通过信标节点：已知自身位置信息的节点，可通过GPS定位设备或手工配置、定位设备或手工配置、确定部署等方式预先获取确定部署等方式预先获取(huq)位置信息，为其他节点提供参考坐标。位置信息，为其他节点提供参考坐标。未知节点：信标节点以外的节点统称为未知节点，也有文献称为盲节点。未知节点：信标节点以外的节点统称为未知节点，也有文献称为盲节点。邻居节点：一个节点通信距离范围内的所有节点的集合。邻居节点：一个节点通信距离范围内的所有节点的集合。跳数：两个节点之间跳段的总数。跳数：两个节点之

3、间跳段的总数。跳距：两个节点之间各跳段的距离之和。跳距：两个节点之间各跳段的距离之和。节点连接度：节点可以探测发现到的邻居节点个数。节点连接度：节点可以探测发现到的邻居节点个数。网络连接度：所有节点的邻居个数取平均值，可反映传感器配置的密集网络连接度：所有节点的邻居个数取平均值，可反映传感器配置的密集程度程度第八章 无线传感器网络(wnglu)节点定位技术l 节点定位技术概述(i sh)一些概念第3页/共39页第2页/共39页第三页，共40页。传感器网络的定位算法通常需要具备以下特点：自组织性：传感器网络的节点随机部署，不依赖于全局基础设施协助定位；健壮性：传感器节点的硬件配置低，能量有限，可

4、靠性较差，定位算法必须能够容忍节点失效和测距误差；节能性：尽可能地减少算法中计算的算法复杂度，减少节点间的通信开销，以尽量延长网络的生存周期；分布式：无线传感器网络通常是大规模部署网络，节点数目多，定位任务将不会是单个节点所能承担的，这就需要定位算法具有一定的分布式，把任务分派到各个节点；可扩展性：无线传感器网络中的节点数目可能是成千上万(chng qin shng wn)甚至更多，为了满足对不同规模的网络的适用性，定位算法必须具有较强的可扩展性。第八章 无线传感器网络(wnglu)节点定位技术l 节点(ji din)定位技术概述要求第4页/共39页第3页/共39页第四页，共40页。作为一种全

5、新的技术，无线传感器网络具有许多挑战性的研究课题，而定位就是其中之一，定位也是大多数应用的基础和前提传感器节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大的限制，低功耗是其最主要的设计目标。必须针对密集性，节点的计算、存储和通信等能力都有限的特定场合设计有效的低功耗定位算法近十年来，无线传感器网络自身定位问题研究有了许多新颖的解决方案和思想，但是每种系统和算法都是用来解决不同的问题或支持不同的应用的，它们用于定位的物理现象、传感器设备的组成(z chn)、能量需求、基础设施和时空的复杂性等许多方面有所不同。对现有的WSN定位研究成果研究比较发现，没有一种定位方案能在有效减少通信开

6、销、降低功耗、节省网络带宽的同时获得较高的定位精度。而且大部分停留在仿真和实验阶段。因此，该领域还有待更多的人提出更好的方法，以求更好地解决定位问题，使得无线传感器网络能够真正在实际生活中得到广泛的应用。第八章 无线传感器网络节点(ji din)定位技术l 节点定位(dngwi)技术的研究现状和发展第5页/共39页第4页/共39页第五页，共40页。目前，在节点定位应用中，由于受传感器节点能量有限、可靠性差、网络规模大且节点随机布放、无线模块的通信距离有限等影响，对定位算法和定位技术提出了很高的要求。一般来说我们从定位区域与精确度、实时性和能耗三个方面来衡量节点定位技术的好坏。1定位区域与精确度

7、定位区域与精确度是传统定位方法和无线传感器网络定位都具有的衡量指标，而且定位区域和精度一般都是互补存在的，定位区域越大，意味着精度越小。2实时性实时性是定位技术的另外(ln wi)一个关键指标，实时性与位置信息的更新频率密切相关，位置信息更新频率越高，实时性越强3能耗能耗是无线传感器网络独有的一个衡量指标。在无线传感器网络中，节点的电能靠电池来供应，电池是不可替换的，因此节省能量就成了无线传感器网络中一个重要的问题。另外(ln wi)，还有一些小的方面来衡量无线传感器网络定位技术的好坏，如定位技术的扩展性、鲁棒性和节点带宽的占用等。第八章 无线传感器网络节点(ji din)定位技术l 节点定位

8、技术(jsh)的研究现状和发展第6页/共39页第5页/共39页第六页，共40页。利用信标节点的位置，通过测量和估计信标节点与目标节点的距离，我们就能够利用它们之间的关系很容易地算出目标节点的位置。基于测距的定位(dngwi)技术涉及几何中的图形问题，已知节点的位置，求另外几个节点的位置，比较常用的方法有：三边定位(dngwi)法角度定位(dngwi)法角度定位(dngwi)需要另外测量接收信号夹角，测量出夹角后使用数学几何条件，确定节点的位置。因为测量的信号夹角不可能很精确，所以AOA的精度不理想。第八章 无线传感器网络节点定位(dngwi)技术l 节点定位技术(jsh)基于测距的定位第7页/

9、共39页第6页/共39页第七页，共40页。1基本思想基本思想三边三边(sn bin)定位法如图所示，已知定位法如图所示，已知A、B、C三个节点的坐标分别三个节点的坐标分别为（为（x1，y1）、（）、（x2，y2）、（）、（x3，y3）。测得它们到未知节点）。测得它们到未知节点D的的距离分别为距离分别为d1、d2、d3。假设节点。假设节点D的坐标为（的坐标为（x，y）。以）。以A、B、C三点为圆心，三点为圆心，d1、d2、d3为半径做圆，三圆的焦点即为节点为半径做圆，三圆的焦点即为节点D的坐标。的坐标。第八章 无线传感器网络节点定位(dngwi)技术l 基于测距的定位(dngwi)技术三边定位(

10、dngwi)法那么，我们可以列出以下公式：第8页/共39页第7页/共39页第八页，共40页。将第一个方程和第二个方程同时(tngsh)减去第三个方程，得到结果222222131313131322222223232323232()2()2()2()xx xyy yxxyyddxx xyy yxxyydd将其写成线性方程(xin xn fn chn)的形式，AX=B，其中222222131313131322222223232323232()2()2()2()xxyyxxyyddxxxyyyxxyydd ABXl 基于测距的定位(dngwi)技术三边定位(dngwi)法第八章 无线传感器网络节点定位

11、技术由此可以得出节点D的坐标为1222222131313131322222223232323232()2()2()2()xxyyxxyyddxyxxyyxxyydd 第9页/共39页第8页/共39页第九页，共40页。l 基于(jy)测距的定位技术三边定位法第八章 无线传感器网络节点(ji din)定位技术三边定位技术的计算方法比较简单，在已知两点之间距离的情况下，采用单纯的数学公式就可以计算出来，节点之间距离的测量才是三边定位技术的最难点，一般来说，有三种算法(sun f)可以测量两个节点之间的距离：根据接收信号的强度来计算距离；根据信号传播时间或者时间差来计算距离；根据接收信号相位差定位。2

12、主要技术主要技术第10页/共39页第9页/共39页第十页，共40页。1）根据接收信号(xnho)强度定位，信号(xnho)衰减模型如下式：式中，P(d)、P(d0)分别(fnbi)表示在距离基站d、d0处的信号强度，P(d)是接收节点实际测得的信号强度RSSI，P(d0)一般可以距天线d0米处的路径衰减来代替。l 基于测距的定位技术(jsh)三边定位法第八章 无线传感器网络节点定位技术第11页/共39页第10页/共39页第十一页，共40页。2）根据信号传播时间测距（TOA）该技术是采用信号到达时间来测量距离的，是一种基于电波(din b)传输时间的定位技术。己知信号传播速度，通过测量信号从发射

13、机传播到多个接收机所消耗的传播时间来确定移动用户的位置TOA测距的基本思想是测量移动台发射信号的到达时间，并且在发射信号中要包含发射时间标记以便接收基站确定发射信号所传播的距离，该方法要求移动台和基站的时间精确同步为了测量移动台的发射信号的到达时间，需要在每个基站处设置一个位置测量单元，为了避免定位点的模糊性，该方法至少需要三个位置测量单元或基站参与测量l 基于(jy)测距的定位技术三边定位法第八章 无线传感器网络节点定位(dngwi)技术第12页/共39页第11页/共39页第十二页，共40页。如图所示，有A、B、C三个基站，因为节点间的距离测量都是一样的，这里我们就假定先测量基站A到目的节点

14、的距离。假设基站A到目的节点D的距离为d，声波传播速度为v，在T1时刻基站A发射机发射一个声波信号给目的节点D，D节点在T2时刻接收到该声波信号，经过短暂的处理之后，在T3时刻目的节点D回送一个声波测距信号给A节点，在T4时刻A节点接收到该信号。由此可以(ky)得出声波信号在介质中传播的时间为：( 21)( 43)tTTTTl 基于测距的定位技术(jsh)三边定位法第八章 无线传感器网络节点(ji din)定位技术第13页/共39页第12页/共39页第十三页，共40页。在这段时间内，声波传播的距离为2d，我们(w men)就可以得到值得注意的是，这里的T1和T4时刻是由节点A测得的，T2和T3

15、时刻是由目的节点D测得的，由于时钟漂移、定位误差等的存在(cnzi)，两者的时间会有一定的时间差，但是由于无线采用双向通信的方式，两者的时间差相互抵消，对结果没有太大影响l 基于(jy)测距的定位技术三边定位法第八章 无线传感器网络节点定位技术第14页/共39页第13页/共39页第十四页，共40页。3）根据到达时间差测距（Time Difference Of Arrival，TDOA）在基于到达时间差TDOA的定位机制中，发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及(yj)已知这两种信号的传播速度，计算两个节点之闻的距离，再通过已有基本的定位算法计算出节点的

16、位置。l 基于(jy)测距的定位技术三边定位法第八章 无线传感器网络节点(ji din)定位技术第15页/共39页第14页/共39页第十五页，共40页。如图所示，发射节点在时刻T0同时发射无线射频信号和超声波信号，接收节点记录两种信号到达的时间T1和T2，己知无线射频信号和超声波的传播速度分别为c1和c2，那么我们(w men)可以知道射频信号和超声波信号传播的时间为：TDOA有一些固有的缺陷需要考虑。首先利用TDOA进行定位要求传感节点上必须附加特殊的硬件（声波或者超声波的收发器等），这会增加传感节点的成本；其次，声波或者超声波在空气中的传输特性和一般的无线电波并不一样，空气的温度(wnd)

17、、湿度或者风速都会对声波的传输速度产生很大的影响，这就使得距离的估计可能出现较大偏差；最后，TDOA测速的一个很大的假设是发送节点和接收节点之间是没有障碍物阻隔的，在有障碍物的情况下会出现声波的反射、折射和衍射，此时得到的实际传输时间将变大，在这种传输时间下估算出来的距离也将出现较大的误差。2120102121() ()ddttTTTTTTccl 基于测距的定位技术(jsh)三边定位法第八章 无线传感器网络节点定位技术可以得出 即：第16页/共39页第15页/共39页第十六页，共40页。222ccfcfcdl 基于测距的定位技术(jsh)三边定位法第八章 无线传感器网络节点(ji din)定位

18、技术第17页/共39页第16页/共39页第十七页，共40页。常用的角度定位方法有：已知两个顶点和夹角的射线确定一点，以及已知三点和三个夹角确定一点。1已知两个顶点和夹角的射线确定一点如图所示，测得参考点A(x1,y2)和B(x2,y2)收到的信号夹角分别是和，根据(gnj)可以计算出待测节点N的位置坐标(x,y)。这是一种参考节点A和B自身在坐标系已经矫正的情形，如果参考点A和B方向没有校正，需要在计算时补偿方向偏差。l 基于测距的定位技术(jsh)三角定位法第八章 无线传感器网络节点定位(dngwi)技术22112211(tan) (tan)tantan(cot) (cot)cotcotyx

19、yxxxyxyy第18页/共39页第17页/共39页第十八页，共40页。如图所示，在测量出角、角和角后，可以(ky)使用三角定位的方法计算出N点的位置(x,y)。对于参考点A(x1,y1)、B(x2,y2)和夹角，根据圆的内接四边形对角互补和弦所对的圆周角等于它所对的圆心角的性质，得到弦AB所对应的圆心角=22。可以(ky)由A、B和N确定一个内接圆O的圆心C1（xc1,yc1）和半径rc1，同理由A、C和N三点就可以(ky)确定O2(xc2,yc2,rc2)，由B、C和N三点就可以(ky)确定O3(xc3,yc3,rc3)。根据圆O1、O2、O3，再根据如下方程组，就可以(ky)确定点D(x

20、D,yD)的坐标。222221111122222222233333()()()()()()cccccccccxxyyrxxyyrxxyyrl 基于(jy)测距的定位技术三角定位法第八章 无线传感器网络节点定位(dngwi)技术第19页/共39页第18页/共39页第十九页，共40页。在无线传感器网络中，基于测距的定位技术往往具有很大的优势，算法比较简单，实现容易，研究人员一般从几个(j )方面来评判这些定位技术的优略。（1）定位精度，即测距误差，为测得的距离与实际距离的差值，一般来说采用超声波的TDOA协议最小，而采用功率衰减来判别距离的RSSI测距误差最大。（2）覆盖范围。GPS是全球定位系统

21、，一次覆盖范围最好，其次是采用功率衰减的RSSI。而TOA和TDOA定位技术采用超声波短波，传播距离最短，因此覆盖范围最小。（3）抗干扰能力。当有干扰如电磁干扰，多径干扰等存在时，节点是否能够正常稳定工作成为测距定位技术性能的一个重要指标。（4）实现成本。l 测距定位(dngwi)技术比较第八章 无线传感器网络节点定位(dngwi)技术第20页/共39页第19页/共39页第二十页，共40页。1基于连通性的定位基于连通性的定位连通性（连通性（Connectivity）是指两个节点是否连通。基于连通性的定位可以根据一个节）是指两个节点是否连通。基于连通性的定位可以根据一个节点能否成功点能否成功(c

22、hnggng)解调其他节点传来的数据包作为依据。解调其他节点传来的数据包作为依据。如果节点如果节点i和节点和节点j连通，则表示节点连通，则表示节点i能够通过感知、通信等途径，确定节点能够通过感知、通信等途径，确定节点j在自己周在自己周围的一定范围内，但不知道具体的距离和方向。确切地说，节点围的一定范围内，但不知道具体的距离和方向。确切地说，节点i和节点和节点j之间的连通之间的连通性测量性测量Qij，可以依据接收信号强度表示成，可以依据接收信号强度表示成0或或1的二元变量模型，即：的二元变量模型，即： 式中，Pij是节点i收到的从节点j发出(fch)的信号的强度，单位是dBm；Pi是数据包刚好能

23、被解调所需的最小接收信号阈值强度。l 无需测距的定位技术(jsh)基于连通性第八章 无线传感器网络节点定位技术第21页/共39页第20页/共39页第二十一页，共40页。2基于基于(jy)跳数的定位跳数的定位在无线传感器网络中，节点间最基本的通信在无线传感器网络中，节点间最基本的通信方式是洪泛，所以很多节点定位机制都是采方式是洪泛，所以很多节点定位机制都是采用两个节点之间的跳数（用两个节点之间的跳数（Hop）来估计节点）来估计节点之间的距离的。之间的距离的。跳数原理就是对信标节点信息洪泛的过程进跳数原理就是对信标节点信息洪泛的过程进行跳数统计，通过统计未知节点与信标节点行跳数统计，通过统计未知节

24、点与信标节点之间的跳数，然后根据信标节点之间的距离之间的跳数，然后根据信标节点之间的距离和跳数估算出全网每一跳的平均距离，二者和跳数估算出全网每一跳的平均距离，二者相乘，即可得到两个节点之间的距离。相乘，即可得到两个节点之间的距离。l 无需测距的定位技术(jsh)基于跳数第八章 无线传感器网络(wnglu)节点定位技术第22页/共39页第21页/共39页第二十二页，共40页。质心质心(zh xn)定位算法的核心思想是：全网约定一段时间定位算法的核心思想是：全网约定一段时间t为定位时间。时间为定位时间。时间t为为(1)tST 式中，T为发信号的时间间隔；S为t时间内要发送的消息个数；为小于1、大

25、于0的常数。在这段时间t内，信标节点(ji din)每隔时间T向邻居节点(ji din)广播一个信标信号，信号中包含自身的位置信息。未知节点(ji din)记录从每个发来信号的信标节点(ji din)接收到的信标信号数量。i时间结束后，未知节点(ji din)计算与各个信标节点(ji din)之间的通信成功率指标CMi，即： l 无需测距的定位(dngwi)技术质心定位(dngwi)算法第八章 无线传感器网络节点定位技术第23页/共39页第22页/共39页第二十三页，共40页。假设这些坐标分别(fnbi)为（x1，y1）、（x2，y2）、（xk，yk），则未知节点的坐标（xest，yest）可

26、用质心公式计算为：11estest(,),kkxxyyxykkl 无需测距的定位技术质心(zh xn)定位算法第八章 无线传感器网络节点定位(dngwi)技术第24页/共39页第23页/共39页第二十四页，共40页。APIT定位算法的理论基础是最佳三角形内点测试法PIT。PIT理论为判断某一点M是否在三角形ABC内，假如存在一个方向，沿着这个方向M点会同时远离或接近三角形ABC的三个顶点A、B、C，那么点M位于(wiy)三角形ABC外；否则，点M位于(wiy)三角形ABC内。l 无需测距的定位技术(jsh)APTI定位算法第八章 无线传感器网络节点(ji din)定位技术第25页/共39页第2

27、4页/共39页第二十五页，共40页。在图（a）中,位置未知节点M通过与邻居节点1交换信息，得知自身如果运动至节点1，将远离信标节点B和C，但会接近信标节点4，与邻居节点2、3、4的通信(tng xn)和判断过程类似，最终确定自身位于三角形ABC中；而在图（b）中，当节点4可知自身运动至邻居节点2处，将同时远离信标节点A、B、C，故判断自身不在ABC中。l 无需测距的定位(dngwi)技术APTI定位(dngwi)算法第八章 无线传感器网络节点定位(dngwi)技术第26页/共39页第25页/共39页第二十六页，共40页。APIT定位的具体步骤如下(rxi)：（1）收集信息：未知节点收集邻近信标

28、节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息。（2）APIT测试：测试未知节点是否在不同的信标节点组合的三角形内部。（3）计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域。（4）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。l 无需测距的定位(dngwi)技术APTI定位(dngwi)算法第八章 无线传感器网络节点(ji din)定位技术第27页/共39页第26页/共39页第二十七页，共40页。DV-Hop算法的基本思想是将未知节点到信标节点之间的距离用网络中节点的平均算法的基本思想是将未知节点到信标节点之间的距离用

29、网络中节点的平均每跳距离和两节点之间跳数的乘积来表示，然后再使用三边测量法或极大似然估计每跳距离和两节点之间跳数的乘积来表示，然后再使用三边测量法或极大似然估计法来获得未知节点的位置信息。法来获得未知节点的位置信息。DV-Hop算法的定位过程分为以下三个阶段：算法的定位过程分为以下三个阶段：1）计算未知节点与每个信标节点的最小跳数）计算未知节点与每个信标节点的最小跳数首先首先(shuxin)使用典型的距离矢量交换协议，使网络中所有节点获得与信标节点使用典型的距离矢量交换协议，使网络中所有节点获得与信标节点之间的跳数。在算法开始的时候，每个信标节点都发出一个包括自己位置信息、地之间的跳数。在算法

30、开始的时候，每个信标节点都发出一个包括自己位置信息、地址和跳数值为址和跳数值为0的位置信息包，它们周围所有跳数为的位置信息包，它们周围所有跳数为1的邻居都收到这样的信息，将的邻居都收到这样的信息，将信标节点的位置信息和跳数记录下来，并将收到信息包的跳数值加信标节点的位置信息和跳数记录下来，并将收到信息包的跳数值加1，再向自己的，再向自己的邻居节点广播。这个过程一直持续下去，直到网络中每个节点都获得每个信标节点邻居节点广播。这个过程一直持续下去，直到网络中每个节点都获得每个信标节点的位置信息和相应的跳数值为止。的位置信息和相应的跳数值为止。l 无需测距的定位技术(jsh)DV-Hop定位算法第八

31、章 无线传感器网络节点定位(dngwi)技术第28页/共39页第27页/共39页第二十八页，共40页。2）计算未知节点(ji din)与信标节点(ji din)的平均每跳距离在第二阶段，每个信标节点(ji din)根据第一阶段获得的其他信标节点(ji din)位置和相隔跳数之后，根据下式计算网络平均每跳距离HopSize。式中，（xi，xj）、（yi，yj）是信标节点i 和j 的坐标，hji是信标节点i和j（ij）之间的跳段数。在实验中，我们发现，当总跳数大于一定(ydng)的值之后，每个节点所计算的平均每跳距离基本一样。l 无需(wx)测距的定位技术DV-Hop定位算法第八章 无线传感器网络

32、节点定位技术第29页/共39页第28页/共39页第二十九页，共40页。3）利用三边测量法计算自身位置在未知节点获得与3个或3个以上信标(xn bio)节点的距离后，执行三边测量定位。该算法只需要较少的信标(xn bio)节点，计算和通信开销适中，不需要节点具备测距能力，是一个可扩展的算法，但是该算法对信标(xn bio)节点的密度要求较高，对于各向同性的密集网络，才可以得到合理的平均每跳距离，从而能够达到适当的定位精度。l 无需(wx)测距的定位技术DV-Hop定位算法第八章 无线传感器网络节点定位(dngwi)技术第30页/共39页第29页/共39页第三十页，共40页。将节点间点到点的通信连

33、接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用线性矩阵不等式、半判定规划或线性规划方法得到一个全局优化的解决方案，确定节点位置。同时也给出了一种计算未知节点有可能(knng)存在的矩形空间的方法。l 无需测距的定位(dngwi)技术凸优化方法第八章 无线传感器网络节点定位(dngwi)技术第31页/共39页第30页/共39页第三十一页，共40页。无线传感器网络自身定位算法的性能对其可用性有直接的影响，如何评价定位算法是一个需要研究的问题。可从是否需要信标节点、信标节点布置方式、计算模式、定位原理(yunl)和节点外加设备等角度对上述无须测

34、距节点定位技术进行了分析和比较，如下表所示。l 无需测距的定位(dngwi)技术分析比较第八章 无线传感器网络节点(ji din)定位技术第32页/共39页第31页/共39页第三十二页，共40页。刚性刚性(n xn)体理论概述体理论概述刚性，即在不考虑物质特性的理想条件下任何两个连接点之间的欧氏距离不随其运动状态改变(gibin)的特性。普通刚性理论是一种定义在光滑轨道上的运动特性。当图沿着光滑轨道运动时，任意两个节点qi(t)和qj(t)间的欧氏距离不随时间函数(hnsh)变化，则qi(t)和qj(t)具有普通刚性特性。用数学描述，即当几何图沿着轨道q(0, )做刚性运动时，则任意时刻的节点

35、集qi(t)和qj(t)是全等的。可用数学公式表示为( )0q Rq式中， R(q)是一个mn型的矩阵，称为刚体矩阵。l 协作定位技术第八章 无线传感器网络节点定位技术第33页/共39页第32页/共39页第三十三页，共40页。定理1：在二维的平面(pngmin)空间中，图形G=(v,L)拥有n个顶点，如果L（L为图形的边集）存在一个有2n3条边的子集E，且对任意一个非空边集E中有n个顶点且E中元素数量不超过2n3，那么图形G=(V,L)在二维平面(pngmin)空间中具有普通刚性。第八章 无线传感器网络节点定位(dngwi)技术定理2：在一个二维平面空间(kngjin)中图G内包含n4个定点，

36、如果图G中某个点具有3-连接（3-Connected）结构且该图形是冗余刚性的，那么图G就是全局刚性结构。l 协作定位技术第34页/共39页第33页/共39页第三十四页，共40页。协作体的定义协作体的定义将刚性理论引入网络结构拓扑中是无线传感器网络中基于协作模式节点定位的第一将刚性理论引入网络结构拓扑中是无线传感器网络中基于协作模式节点定位的第一步，用图形结构的方式描述网络拓扑结构。步，用图形结构的方式描述网络拓扑结构。定义定义1：在网络图形：在网络图形GN=(V,EN)中，存在中，存在(cnzi)节点节点u和和vG(V)，R(u,v)或或R(v,u)表示节点表示节点u和和v之间的几何距离，设

37、之间的几何距离，设r是网络中节点的最大无限传输距离，当是网络中节点的最大无限传输距离，当R(u,v)r时，时，u和和v之间可以无线连通，则称之间可以无线连通，则称u和和v为直接相邻节点或邻居节点。为直接相邻节点或邻居节点。定理定理322：在二维空间的无线传感器网络：在二维空间的无线传感器网络N中的节点以随机的形式分布，当网络中的节点以随机的形式分布，当网络中存在中存在(cnzi)m3个非共线导标节点，且网络个非共线导标节点，且网络N所对应的结构所对应的结构GN=(V,EN)是全是全局刚性，则网络局刚性，则网络N中的节点可以被定位。中的节点可以被定位。l 协作定位(dngwi)技术第八章 无线传

38、感器网络节点定位(dngwi)技术第35页/共39页第34页/共39页第三十五页，共40页。定义定义2：无线传感器网络中的一组连通的节点：无线传感器网络中的一组连通的节点C组成的局部网络拓扑组成的局部网络拓扑N，若，若N中所对应节点之间的连接特性及导标节点的物理位置的约束可以唯一确定中所对应节点之间的连接特性及导标节点的物理位置的约束可以唯一确定N中位置节点的位置信息，那么，称局部网络拓扑中位置节点的位置信息，那么，称局部网络拓扑N为定位协作体为定位协作体定义定义3：（单元定位协作体）对某一定为协作体：（单元定位协作体）对某一定为协作体 ，若不存在，若不存在(cnzi)定位协作体定位协作体 满

39、足满足 ，则称定位协作体，则称定位协作体Lu为单元定位协作体。包含为单元定位协作体。包含n（n=1,2,3）个两两相连的未知节点及）个两两相连的未知节点及m（m=3）个导标节点，且不含任何冗余边的）个导标节点，且不含任何冗余边的LCS成为最简单的定位协作体或最简定位协作体，如图成为最简单的定位协作体或最简定位协作体，如图8.12所示。所示。sLsuLLl 协作(xizu)定位技术第八章 无线传感器网络(wnglu)节点定位技术第36页/共39页第35页/共39页第三十六页，共40页。定理定理4：设：设L1和和L2为两个定位协作体，它们所对应的节点集分别为两个定位协作体，它们所对应的节点集分别(