无线传感器网络中基于博弈方法的分布式定位装置与方法

摘要

一种无线传感器网络中基于博弈方法的分布式定位装置与方法，属于无线传感器定位技术领域。节点状态获取器、测量距离计算器、邻居节点集建立器、锚节点信息过滤器、位置策略空间生成器、节点位置计算器、阈值设置器、比较器节点转换器和节点状态广播器。本发明在定位过程中仅需要与邻居节点进行沟通协商，能大大减少定位的负载开销，节省定位过程的能耗。进一步，在博弈开始前通过与锚邻居节点协商以确定博弈策略空间，以及利用连续精确定位次数确定精确定位条件，能加速定位算法的快速收敛，本发明方法能够快速、有效地定位传感器节点的准确位置，在高密度、少量锚节点部署的环境中同样表现良好，具有较好的可扩展性。

说明书

技术领域

本发明属于无线传感器定位技术领域，特别涉及一种无线传感器网络中基于博弈方法的 分布式定位装置与方法。

背景技术

无线传感器网络由部署在监测区域内大量的微型、低能量、低成本的传感器节点组成， 通过无线通信方式形成一个自组织的多跳网络系统。节点定位是大多数无线传感器网络应用 能够顺利开展的重要前提，如环境监测、目标追踪、矿井信息采集、灾难救援等应用本质上 都需要能够快速准确地获取每个传感器节点的位置信息。另外，精确提供每个传感器节点的 位置信息还有助于增强网络覆盖质量，提升网络拓扑自配置能力与路由效率，并为实现网络 负载均衡提供重要支撑。

近年来，已有部分文献开始关注传感器网络的定位问题，这些定位算法可大致可以分为 粗粒度定位和细粒度定位。前者依赖于低成本硬件，但是定位不够精确；相比较而言，后者 通过挖掘与重构网络中节点的拓扑关系，具有更高的定位精度，被认为是传感器网络定位问 题研究中的重要内容。在细粒度定位技术中，通常假设存在少部分节点能够通过GPS或人工 部署等方式获取其精确位置坐标，这些节点一般称之为锚节点，并通过测距机制估算邻居节 点之间的距离。目前，测距技术一般使用接收信号强度(RSS)、到达角度(AOA)、或到达时间 (TOA)等物理参数进行距离估计。基于事先部署的锚节点位置与各节点间的测量距离，考虑 到定位所有未知节点属于多变量非凸优化范畴，且属于NP难问题，目前业界主要提出的方 法大都为集中式算法，在网络规模较大时，全网消息的集中式交互易引发较大能耗，成为算 法实施的瓶颈。虽然已有一些研究工作开始研究分布式细粒度定位问题，但与集中式方法相 比，当前的分布式定位算法还存在定位精度较差等问题，如何设计高精度的分布式定位方法， 已成为传感器网络定位研究中亟需解决的难点问题。

发明内容

针对现有技术存在的问题，本发明的目的是提供一种无线传感器网络中基于博弈方法的 分布式定位装置与方法，以达到快速、有效地定位传感器节点的目的。

本发明的技术方案是这样实现的：一种无线传感器网络中基于博弈方法的分布式定位装 置，包括:

节点状态获取器：用于获取邻居传感器节点广播的状态消息，主要包括邻居传感器节点 的标号、型号及邻居传感器节点估计的自身位置坐标值;

测量距离计算器:用于提取邻居传感器节点状态消息中表示接收信号强度RSSI的值，并 对RSSI值进行变换计算与邻居传感器节点之间的测量距离，并将该测量距离值发送给节点位 置计算器;

邻居节点集建立器:用于根据节点状态获取器提供的邻居传感器节点的标号及型号，建 立传感器节点的邻居集合，并将建立的邻居节点集发送给节点位置计算器;

锚节点信息过滤器:用于在邻居传感器节点中提取型号为锚节点的传感器节点，并将获 取的锚邻居节点信息发送给位置策略空间生成器;

位置策略空间生成器:用于根据锚节点信息过滤器输出的锚邻居节点信息，确定作为锚 节点的相邻两个传感器的测量范围交集，该测量范围交集即为传感器自身存在的区域;

节点位置计算器:用于根据测量距离计算器的输出、邻居节点集建立器的输出、锚节点 信息过滤器的输出和位置策略空间生成器的输出，利用博弈方法计算传感器自身的坐标及当 前的效益函数值;

阈值设置器:用户自行设定邻居节点传感器转换为锚节点传感器的阈值，该阈值包括效益 函数阈值与连续精确定位次数阈值;

比较器:节点位置计算器的输出的目标函数值与阈值设置器输出的效益函数阈值进行比 较，若小于阈值，则该传感器标记为可能的锚节点传感器;

节点转换器:若比较器中可能的锚节点传感器被标记的次数大于连续精确定位次数阈值 时，则将该传感器节点的型号设置为锚节点传感器;

节点状态广播器:用于传感器本身向其邻居节点广播节点新的标号、新确定的型号值及 新估计的自身位置坐标信息.

所述的节点状态广播器，广播的信息包括两种:

一种是将自身新计算出位置坐标广播给邻居传感器节点;另一种是为已经转换为锚节点 的传感器或本身就是锚节点的传感器，广播他们实际的坐标值给邻居传感器节点.

所述的测量距离计算器，测量的距离包括:所有与本传感器节点相邻的传感器节点、与 本传感器之间的距离.

传感器节点的型号为待定位传感器节点或者为锚传感器节点.

所述的传感器节点的标号是用来唯一标识传感器的.

采用上述装置在无线传感器网络中确定待定位传感器位置的方法，包括以下步骤:

步骤1:传感器节点获取自身的状态信息，如果为锚节点，则执行步骤9，否则，执行步 骤2;

步骤2:传感器节点设置最大迭代次数T，设置效益函数阈值为Θ_h，连续精确定位次数 阈值W_h，初始迭代次数t为1，连续精确定位次数w为0;

步骤3:传感器节点获取邻居传感器节点广播的节点状态信息，包括邻居节点的标号、 型号和节点坐标;

步骤4:利用传感器节点自身的接收信号强度指示RSSI，计算其与各邻居节点之间的距 离;

步骤5:传感器节点根据获取的邻居传感器节点状态信息，将所有的邻居传感器节点标 记号保存至邻居节点集中;

步骤6:传感器节点从接收到的邻居传感器节点状态信息中提取所有型号为锚节点的传 感器的状态信息，将所有锚邻居节点的标记号保存在锚邻居节点集中;

步骤7:计算传感器节点可能存在的空间范围;

步骤8:利用博弈方法计算传感器节点具体的位置;

步骤9:迭代次数t加1，并判断迭代次数是否大于最大迭代次数T，如是，算法终止; 否则进入节点状态广播，主要向其邻居节点广播节点的标号、新确定的型号值、及新估计的 位置坐标信息，执行步骤1。

步骤3所述的计算传感器与各邻居节点之间的距离，公式如下：

$d=2^{\frac{P_k-P_d}{100}}---\left(1\right)$

式中，d为传感器节点与它的邻居传感器之间的距离，P_k为由用户设定的基准参考值km 时，传感器节点能获取的RSSI值；P_d为当前获取的RSSI值。

步骤7所述的计算传感器节点可能存在的空间范围，过程如下:

步骤7-1:计算锚邻居节点集中节点的数量;

步骤7-2:判断锚邻居节点的数量是否大于或者等于3，如果是，则直接确定传感器节点 位置，公式为：

设待定位传感器节点v_i的所有锚邻居节点的位置为：

{s_j:(x_i,j,y_i,j)|j=1,2,...,|N_i|}，

式中，s_j为节点v_i的第j个锚邻居节点，x_i,j为节点v_i的第j个锚邻居节点s_j的横坐标，y_i,j为节点v_i的第j个锚邻居节点s_j的纵坐标，|N_i|为节点v_i的锚邻居节点数量，且i=1,…,N,N为 网络中全部待定位节点的数量。

基于最小二乘法，v_i的坐标s_i:(x_i,y_i)计算公式为，

s_i=(A^TA)^-1A^Tb              (2)

其中，$A=-2*\left(\begin{array}{cc}(x_{i,1}-x_{i,\left|N_i\right|})& (y_{i,1}-y_{i,\left|N_i\right|})\\ (x_{i,2}-x_{i,\left|N_i\right|}^t)& (y_{i,2}-y_{i,\left|N_i\right|})\\ ···& ···\\ (x_{i,\left|N_i\right|-1}-x_{i,\left|N_i\right|})& (y_{i,\left|N_i\right|-1}-y_{i,\left|N_i\right|})\end{array}\right),$

$b=\left(\begin{array}{c}{d}_{i,1}^2-d_{i,k}^2-{\left(x_{i,1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2\\ d_{i,2}^2-d_{i,k}^2-{\left(x_{i,2}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,2}\right)}^2{\left(y_{i,{|N}_i|}\right)}^2\\ ···\\ d_{i,\left|N_i\right|-1}^2-d_{i,k}^2-{\left(x_{i,\left|N_i\right|-1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,\left|N_i\right|-1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2\end{array}\right)$

式中，d_i,j为侍定位节点v_i到其第j个锚邻居节点s_j的距离；执行步骤9；

步骤7-3：否则判断锚邻居节点的数量是否等于2，如果是，则确定传感器节点可能存在 的空间区域为：以与该传感器节点相邻的2个锚节点位置为圆心、节点有效通信距离为半径 的两个相交圆的重叠区域，执行步骤8；

步骤7-4：否则判断锚邻居节点的数量是否等于1，如果是，则确定传感器节点的可能存 在的空间区域为：以锚节点位置为圆心，锚节点有效通信距离为半径的圆覆盖区域，执行步 骤8：

步骤7-5：否则判断锚邻居节点的数量是否等于0，如果是，则确定传感器节点的可能存 在的空间区域为网络中的任何位置，执行步骤8。

步骤8所述的利用博弈方法计算传感器节点具体的位置，过程为：

步骤8-1：从策略空间中随机产生一个新的坐标值；

步骤8-2：保存该传感器节点原有的效益函数值为U_old，并计算新的坐标值的效益函数 U_new，具体为：

步骤8-2-1：初始化新的坐标节点的效益函数值为0；

步骤8-2-2：从邻居节点集中选择一个新的邻居；

步骤8-2-3：计算新产生坐标值与该邻居坐标之间的欧式距离，作为两个邻居节点间的 估计距离；

步骤8-2-4：计算两个邻居节点间的估计距离与测量距离差值的绝对值，并将该绝对值 与效益函数相加，作为效益函数的当前值；

步骤8-2-5判断是否选择完该传感器节点的所有邻居节点，如是，保存传感器节点的效 益函数值为U_new，否则转步骤8-2-2；

步骤8-3：根据步骤8-2新产生的效益函数值U_new及原效益函数值U_old，计算产生概 率值p，公式为：

$p=\frac{1}{1+t^z*e^{(U\_\mathrm{new}-U\_\mathrm{old})/10}}---\left(3\right)$

式中，t为当前的迭代次数，e为自然对数的底数；

步骤8-4：判断概率值p是否大于[0，1)区间内产生的随机数，如果大于，执行步骤 8-5，否则执行步骤8-6；

步骤8-5：

传感器节点的位置更新为新产生的位置坐标，将节点的原效益函数U_old更新为新效益 函数U_new;执行步骤8-7;

步骤8-6:节点位置策略与效益函数不更新，执行步骤9;

步骤8-7:判断传感器节点的效益函数U_old是否大于误差门限Θ_h，若是，执行步骤8-8; 否则，执行步骤8-9;

步骤8-8:将连续精确定位次数w设置为0，同时设置节点型号为待定位节点，转步骤9;

步骤8-9:将连续精确定位次数w加1，同时继续判断连续精确定位次数w是否大于连续 精确定位阈值W_h，若是，则将节点升级为锚节点，执行步骤9;否则设置节点型号为待定位 节点，转步骤9.

本发明的有益效果:本发明提出了一种基于博弈策略的分布式定位机制，在定位过程中 仅需要与邻居节点进行沟通协商，能大大减少定位的负载开销，节省定位过程的能耗.进一 步，在博弈开始前通过与锚邻居节点协商以确定博弈策略空间，以及利用连续精确定位次数 确定精确定位条件，能加速定位算法的快速收敛，本发明方法能够快速、有效地定位传感器 节点的准确位置，在高密度、少量锚节点部署的环境中同样表现良好，具有较好的可扩展性。

附图说明

图1为本发明一种实施方式无线传感器网络中基于博弈方法的分布式定位装置的结构框 图；

图2为本发明一种实施方式无线传感器网络节点部署本装置后的结构框图；

图3为本发明一种实施方式无线传感器网络确定待定位传感器位置的方法；

图4为本发明一种实施方式无线传感器网络中基于博弈方法的位置计算的流程图；

图5为本发明一种实施方式无线传感器网络中传感器节点可能存在的空间范围示意图；

图6为本发明一种实施方式无线传感器网络中计算待定位节点可能存在空间范围的流程 图；

图7为本发明一种实施方式传感器节点初始分布及最终定位结果示意图，其中，(a)为传 感器网络初始部署及节点之间的连接情况示意图，（b）为最终定位结果；

图8为本发明一种实施方式网络平均误差MLE随迭代次数变化情况示意图。

具体实施方式

下面结合附图对本发明的实施方式作进一步详细的说明。

本发明的实施方式给出一种分布式的传感器网络，如图1所示。包括待定位传感器节点 1，待定位传感器节点2，待定位传感器节点3，锚传感器节点4，上述传感器节点组成一个 无线传感器的分布式的网络，本实施方式的目的即是为了确定1，2，3号待定位传感器节点的 具体位置。本实施方式提出的基于博弈方法的分布式定位装置可以设置在任何的型号待定位 传感器节点中，如目前通用的TelosB型号的传感器节点均可满足需求。

在上述1，2，3号待定位传感器节点中均设置有基于博弈方法的分布式定位装置，如图2 所示。本实施方式中，通过3个待定位传感器节点对传感器的设置加以说明。首先同时在传 感器网络中所有的传感器节点上设置基于博弈方法的分布式定位装置，其中，待定位节点传 感器1利用自身的节点状态获取器来获取邻居传感器节点广播的状态消息，比如，待定位节 点传感器1获取信息包括：与它相邻的传感器包括待定位节点传感器2发送的状态广播信息、 待定位传感器3发送的状态广播信息；更为具体的，待定位节点2发送的状态广播信息为 <2，0，(x2，y2)>，分别表示节点2的ID号为2，型号为0表示节点为待定位节点，估计的坐 标值为（x2，y2)。又比如，待定位节点传感器3获取信息包括：与它相邻的传感器包括待定 位节点传感器1及待定位传感器节点2发送的状态广播信息、锚节点4发送的状态广播信息； 更为具体的，锚节点4发送的状态广播信息为<4，1，(x4，y4)>，分别表示节点4的ID号为4， 型号为1表示节点4为锚节点，真实坐标值为(x4,y4)。

之后，待定位节点传感器提取邻居传感器节点状态消息中表示接收信号强度RSSI的值， 如待定位节点传感器1提取待定位节点2与待定位节点3发送状态信息的RSSI值，并根据 RSSI值计算待定位节点1到待定位节点2与代定位节点3之间的距离。又比如待定位节点传 感器3提取待定位节点1、待定位节点2及锚节点4发送状态信息的RSSI值，并根据RSSI 值计算待定位节点3到待定位节点1、代定位节点2及锚节点之间的距离。

再之后，待定位传感器利用接受到的所有状态信息，建立传感器节点的邻居节点集合， 利用锚节点信息过滤器建立锚邻居节点信息集合为空集。比如待定位传感器1利用接受到的 所有状态信息，建立传感器节点的邻居集合为〈2，3〉；利用锚节点信息过滤器建立锚邻居节点 信息集合为空集。又比如，待定位传感器3利用接受到的所有状态信息，建立传感器节点的 邻居集合为<2，3，4>；利用锚节点信息过滤器建立锚邻居节点信息集合为<4>。

待定位传感器利用自身的位置策略空间生成器确定其可能存在的范围。比如待定位节点 1的锚节点信息集为空，其位置范围为网络中任何位置。又比如待定位节点3的锚节点信息 集为4号锚邻居节点，其位置范围为以4号锚节点坐标为圆心，通信半径为半径的圆形覆盖 区域。

待定位传感器1利用自身的节点位置计算器输出其自身的坐标及当前的效益函数值。

利用阈值设置器，用户自行设定所有待定位节点传感器的阈值，例如，待定位传感器1 的阈值设置中设置效益函数阈值为Θ_h=0.5，连续定位次数阈值为W_h=5次。

待定位节点传感器经过一次节点位置计算后得到新的坐标，利用自身的比较器对该新坐 标与效益函数阈值进行比较，判断传感器节点的效益函数U_old是否大于效益函数阈值Θ_h， 若是，将连续精确定位次数w设置为0，同时设置节点型号为待定位节点，继续执行定位过 程。

否则将连续精确定位次数w加1，同时继续判断连续精确定位次数w是否大于连续精确 定位阈值W_h，若是，则将节点升级为锚节点，停止博弈定位，只启动其装置中的节点状态广 播器，定期向其它节点广播状态信息。否则，继续执行定位过程。

采用上述装置在无线传感器网络中确定待定位传感器位置的方法，其流程如图3所示， 该过程由步骤301开始。在步骤302，传感器节点获取自身的状态信息，如果为锚节点，则 执行步骤310，否则，执行步骤303。

在步骤303，传感器节点设置最大迭代次数T，设置效益函数阈值为Θ_h一般设置为0.5，如本实施方式中，根据传感器网络的大小设置阈值为Θ_h=0.5，连续精确定位次数阈值W_h， 一般设置为5，如本实施方式中，根据传感器网络的大小设置阈值为W_h=5，初始迭代次数为 t为1，连续精确定位次数w为0。

在步骤304，传感器节点获取邻居传感器节点广播的节点状态信息，包括邻居节点的标 号、型号和节点坐标。邻居传感器节点广播的状态信息值包括<节点ID、节点型号、节点坐 标>。这其中，节点ID为节点的标记号码，表示为每个节点在全网中的唯一标记；节点型号 用于区分节点为锚节点或待定位节点，当节点型号为1时，节点为锚节点，否则，当节点型 号为0时，节点为待定位节点；节点坐标为节点最新时刻确定的坐标值，如果节点的型号为 1，节点的坐标为真实坐标，如果节点型号为待定位节点，则节点的坐标为计算坐标。

在步骤305，利用传感器节点自身的接收信号强度指示RSSI，计算其与各邻居节点之间 的距离，这里的距离可能包括一系列的距离，如果有多个相邻节点，则应分别计算出与每个 邻居节点的距离值。如图2中，待定位节点3的邻居为1，2，4号节点，则需要分别计算出节 点3与节点1、2、4号节点之间的距离。

在步骤306，传感器节点根据获取的邻居传感器节点状态信息，将所有的邻居传感器节点标记号保存至邻居节点集中。

在步骤307，传感器节点从接收到的邻居传感器节点状态信息中提取所有型号为锚节点 的传感器的状态信息，将所有锚邻居节点的标记号保存在锚邻居节点集中。

在步骤308，计算传感器节点可能存在的空间范围，如图4所示。图4的过程开始于步 骤401。在步骤402，计算锚邻居节点集中节点的数量。

在步骤403，判断锚邻居节点的数量是否大于或者等于3，如果是，则直接确定传感器节 点位置，公式为：

设待定位传感器节点v_i的所有锚邻居节点的位置为：

{s_j:(x_i,j,y_i,j)|j=1,2,...,|N_i|}，

式中，s_j为节点v_i的第j个锚邻居节点，x_i，j为节点v_i的第j个锚邻居节点s_j的横坐标， y_i，j为节点v_i的第j个锚邻居节点s_j的纵坐标，|N_i|为节点v_i的锚邻居节点数量，且i=1，…，N，N 为网络中全部待定位节点的数量。

基于最小二乘法，v_i的坐标s_i:(x_i,y_i)计算公式为，

s_i=(A^TA)^-1A^Tb               (2)

其中，$A=-2*\left(\begin{array}{cc}(x_{i,1}-x_{i,\left|N_i\right|})& (y_{i,1}-y_{i,\left|N_i\right|})\\ (x_{i,2}-x_{i,\left|N_i\right|}^t)& (y_{i,2}-y_{i,\left|N_i\right|})\\ ···& ···\\ (x_{i,\left|N_i\right|-1}-x_{i,\left|N_i\right|})& (y_{i,\left|N_i\right|-1}-y_{i,\left|N_i\right|})\end{array}\right),$

$b=\left(\begin{array}{c}{d}_{i,1}^2-d_{i,k}^2-{\left(x_{i,1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2\\ d_{i,2}^2-d_{i,k}^2-{\left(x_{i,2}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,2}\right)}^2{\left(y_{i,{|N}_i|}\right)}^2\\ ···\\ d_{i,\left|N_i\right|-1}^2-d_{i,k}^2-{\left(x_{i,\left|N_i\right|-1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2-{\left(y_{i,\left|N_i\right|-1}\right)}^2+{\left(y_{i,\left|N_i\right|}\right)}^2\end{array}\right)$

式中，d_i,j为待定位节点v_i到其第j个锚邻居节点s_j的距离，执行步骤310;

否则执行步骤404。

在步骤404，否则判断锚邻居节点的数量是否等于2，如果是，则确定传感器节点可能存 在的空间区域为：以与该传感器节点相邻的2个锚节点位置为圆心、节点有效通信距离为半 径的两个相交圆的重叠区域，如图5所示。其中，阴影的部分表示锚节点A和锚节点B的重 叠区域，也即待定位节点C可能存在的区域，执行步骤309；否则，执行步骤405。

在步骤405，否则判断锚邻居节点的数量是否等于1，如果是，则确定传感器节点的可能 存在的空间区域为：以锚节点位置为圆心，锚节点有效通信距离为半径的圆覆盖区域，执行 步骤309。

在步骤40际，否则判断锚邻居节点的数量是否等于0，如果是，则确定传感器节点的可能 存在的空间区域为网络中的任意区域，执行步骤309。

在过程结束于步骤407。

基于上述步骤，以图2为例，待定位节点1、2的锚节点信息集为空，其位置范围为网络 中任何位置。又比如待定位节点3的锚节点信息集为4号锚邻居节点，其位置范围为以4号 锚节点坐标为圆心，通信半径为半径的圆形覆盖区域。

在步骤309，利用博弈方法计算传感器节点具体的位置，如图6所示。图6的过程开始 于步骤601。在步骤602，从策略空间中随机产生一个新的坐标值。

在步骤603，保存该传感器节点原有的效益函数值为U_old,并计算新的坐标值的效益函 数U_new，具体为：

在步骤603-1，初始化新的坐标节点的效益函数值为0；

在步骤603-2，从邻居节点集中选择一个新的邻居；

在步骤603-3，计算新产生坐标值与该邻居坐标之间的欧式距离，作为两个邻居节点间 的估计距离；

在步骤603-4，计算两个邻居节点间的估计距离与测量距离差值的绝对值，并将该绝对 值与效益函数相加，作为效益函数的当前值；

在步骤603-5，判断是否选择完该传感器节点的所有邻居节点，如是，保存传感器节点 的效益函数值为U_new，否则转步骤603-2。

在步骤604，根据步骤603新产生的效益函数值U_new及原效益函数值U_old，计算产生 概率值p，公式为：

$p=\frac{1}{1+t^z*e^{(U\_\mathrm{new}-U\_\mathrm{old})/10}}---\left(3\right)$

式中，t为当前的迭代次数，e为自然对数的底数；

在步骤605，判断概率值p是否大于[0,1)区间内产生的随机数，如果大于，执行步骤 606，否则执行步骤607;

在步骤606，传感器节点的位置更新为新产生的位置坐标，将节点的原效益函数U_old 更新为新效益函数U_new；执行步骤608；

步骤607；节点位置策略与效益函数不更新，执行步骤310；

步骤608：判断传感器节点的效益函数U_old是否大于误差门限Θ_h，若是，执行步骤609； 否则，执行步骤610;

步骤609:将连续精确定位次数w设置为0，同时设置节点型号为待定位节点，转步骤 310；

步骤610：将连续精确定位次数w加1，同时继续判断连续精确定位次数w是否大于连续 精确定位阈值W_h，若是，则将节点升级为锚节点，执行步骤310；否则设置节点型号为待定 位节点，转步骤310。

该过程结束于步骤611。

在步骤310，迭代次数t加1，并判断迭代次数是否大于最大迭代次数T，如是，算法终 止；否则进入节点状态广播，主要向其邻居节点广播节点的标号、新确定的型号值、及新估 计的位置坐标信息，执行步骤302。

考察实施方式采用的定位方法的性能情况，以验证方法的有效性，具体如下：在100×100 的区域中随机部署165个传感器节点，其中，15个为锚传感器节点，其余150个为待定位传 感器节点。设置Rc=20。

图7示意了传感器节点初始分布及最终定位结果，其中，(a)示意了传感器网络初始部署 及节点之间的连接情况，(b)给出了迭代200次后的定位结果。其中，星号表示锚节点，圆圈 表示待定位节点的物理位置，加号表示待定位节点的估计位置，定位误差由虚线进行量化。 从(a)可见，仅有少量待定位节点拥有2个或2个以上锚节点邻居，还有部分节点的锚节点 邻居数量为0。迭代200次后，所有待定位节点基本上都能够被精确定位。

同时考虑博弈过程中，平均定位误差(mean localization error,MLE)，随迭代次数的 变化情况，其中评价定位误差如以下算式表示

$\mathrm{MLE}=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}\left|\right|{\hat{p}}_i-p_i\left|\right|---\left(4\right)$

其中N为待定位节点的总数，为节点i的定位位置，p_i为节点i的真实位置。||||为二 范数计算公式，表示定位位置与真实位置之间的欧式距离。

图8中可见，MLE随着博弈次数增加而减少。同时可见，在定位博弈中，通过使用博弈 策略空间决策机制与待定位节点升级技术，能够大大加快算法的收敛，表现为MLE曲线的直 线下降。

虽然以上描述了本发明的具体实施方式，但是本领域内的熟练的技术人员应当理解，这 些仅是举例说明，可以对这些实施方式做出多种变更或修改，而不背离本发明的原理和实质。 本发明的范围仅由所附权利要求书限定。