一种无线传感器网络中的启发式节点定位方法

摘要

本发明是一种无线传感器网络中的启发式参数自适应定位方法，通过在网络中设置一个RSSI-d自动训练区，有效实现RSSI-d模型训练，并将网络中的锚节点按照等边三角形布置，并且锚节点设置为统一设备，未知设备进入网络区域后，首先进入RSSI-d自动训练区进行RSSI-d模型训练，获得与当前网络锚节点之间的RSSI-d模型曲线，以消除设备差异性带来的测距误差。仿真结果表明，本发明克服了现有技术的缺点，提高无线传感器网络未知节点的定位精度，有效平衡定位精度，定位能耗，定位时间三者之间的矛盾，从而改善未知节点的定位性能。在相关定位参数相同的情况下，定位精度高于现有技术方案。

说明书

技术领域

本发明是一种适用于无线传感器网络的节点定位方法，属于无线通信的技 术领域。

背景技术

缩略语和关键术语定义

WSN    Wireless Sensor Networks               无线传感器网络

LQI    Link Quality Indication                链路质量指示

RSSI   Received Signal Strength Indication    接收信号强度指示

无线传感器网络(WSN)是信息技术领域中一个新的发展方向，同时也是新兴 学科与传统学科进行学科交叉的结果。它综合了传感器技术、嵌入式计算技术、 分布式信息处理技术和网络通信技术，是信息技术中的一个新领域，被认为是 对21世纪产生巨大影响的技术之一。由于无线传感器网络的巨大应用价值，其 已引起了世界许多国家的军事部门、工业界和学术界的关注。国内外诸多高校 与企业以及标准化组织都开始了无线传感器网络基础理论与关键技术的研究。

节点定位技术是无线传感器网络的主要支撑技术之一，在无线传感器网络 的各种应用方案中，节点自身的正确定位是提供监测事件位置信息的前提。节 点定位问题就是根据少数已知位置的节点(锚节点)，按照某种定位机制确定 自身的位置。只有在节点自身正确定位之后，才能确定传感器节点监测到的事 件的具体位置，这需要监测到该事件的多个传感器节点之间相互协作，并利用 他们自身的定位机制确定事件发生的位置。目前无线传感器网络自身定位系统 和算法的分类可以基于以下几个方面：基于测距(Range-based)的定位和无 需测距(Range-free)的定位；绝对定位与相对定位；集中式计算(Centralized Computation)的定位与分布式计算(Distributed Computation)的定位；紧 密耦合(tightly coupled)的定位与(loosely coupled)的定位；粗粒度的 定位与细粒度的定位。在无线传感器网络定位的诸多算法与系统中，比较典型 的有Cricket定位系统，质心定位算法，SPA相对定位算法，凸规划定位算法， APS，Cooperative ranging和Two-Phase positioning定位算法，MDS-MAP定位 算法。

基于RSSI测距的无线传感器网络定位方法由于其成本的低廉以及算法的 简便而成为当前应用广泛的定位方法。但其自身存在的缺点，如测距误差受环 境影响大，不同设备之间存在测距差异，从而导致其定位精度不高。

传统基于RSSI测距的定位方法，在定位区域内按照一定规则布置若干锚节 点(位置已知的传感器节点)，未知节点进入定位区域后，向锚节点发送数据 请求并获取RSSI值，然后根据无线信号传输中普遍采用的理论模型—— Shadowing模型计算与锚节点之间的实际距离，计算公式如下：

${\left[\overline{p_r\left(d\right)}\right]}_{\mathrm{dBm}}={\left[p_r\left(d_0\right)\right]}_{\mathrm{dBm}}-10\mathrm{nlg}\left(\frac{d}{d_0}\right)+X_{\mathrm{dBm}}$

上式中，d为接收端与发射端之间的距离，d₀为参考距离，一般取1m，为接收端接收信号功率，P_r(d₀)为参考距离d₀点对应的接收信号功率，X_dBm是 一个平均值为0的高斯随机变量，n为路径损耗指数，是一个与环境相关的值。 当未知节点计算得到与三个锚节点之间的实际距离之后，便可利用三边测量法计 算自身的位置坐标，假设未知节点P(x_p，y_p)与三个锚节点L₁(x_l1，y_l1)、L₂(x_l2，y_l2)、 L₃(x_l3，y_l3)之间的距离为d₁，d₂，d₃，则三边测量法计算公式如下：

$\left(\begin{array}{c}\sqrt{{(x_p-x_{l1})}^2+{(y_p-y_{l1})}^2}=d_1\\ \sqrt{{(x_p-x_{l2})}^2+{(y_p-y_{l2})}^2}=d_2\\ \sqrt{{(x_p-x_{l3})}^2+{(y_p-y_{l3})}^2}=d_3\end{array}\right)$

从近年来的研究情况看，现有的无线传感器网络节点定位算法普遍存在着 测距方法受环境影响大、算法复杂度高、能耗大、不适用于移动节点定位等问 题，许多算法和系统的定位精度都还有很大的提高空间，定位技术的研究仍旧 是无线传感器网络的一个技术难点，而随着无线传感器网络技术的不断进步成 熟，其应用将会越来越广泛，实用化的节点定位技术研究对于无线传感器网络 技术性能提高和实用性保证有重要的理论意义和应用价值。

现有基于RSSI测距的定位技术方案分为两个步骤，分别是RSSI与实际距离d 之间关系曲线(RSSI-d曲线)拟合与实际定位过程：

RSSI-d曲线拟合过程如下：

(1)在定位区域内，布置若干数量的已知自身位置的锚节点(Anchor)，选择一 个未知节点(Unknow)，向各Anchor发送广播包；

(2)各Anchor接收未知节点发来的信号后，记录各广播包的RSSI值；

(3)测量各Anchor与未知节点之间的距离d，并不断移动未知节点，因此每一个 Anchor得到数据组：

(d₁，RSSI₁)，(d₂，RSSI₂)，(d₃，RSSI₃)，....，(d_n，RSSI_n)

(4)由(3)得到的数据组进行最小二乘拟合，得到该Anchor的RSSI-d曲线。

实际定位过程如下：

(1)需要实际定位的未知节点，进入定位区域后，向每个Anchor发送一定数量的 数据包，并获得相应的RSSI值，并计算RSSI均值，然后根据相应的RSSI-d曲

线计算d值；

(2)当得到与三个Anchor的(d，RSSI)数据信息后，便可根据三边测量法，计算自 身坐标。如：未知节点的坐标为(x_u，y_u)，三个Anchor的坐标分别为 (x_a1，y_a1)，(x_a2，y_a2)，(x_a3，y_a3)，未知节点计算得到与三个Anchor之间的距离分别 为d₁，d₂，d₃，则可得到以下方程组：

$\left(\begin{array}{c}\sqrt{{(x_u-x_{a1})}^2+{(y_u-y_{a1})}^2}=d_1\\ \sqrt{{(x_u-x_{a2})}^2+{(y_u-y_{a2})}^2}=d_2\\ \sqrt{{(x_u-x_{a3})}^2+{(y_u-y_{a3})}^2}=d_3\end{array}\right)$

计算可得：

$\left(\begin{array}{c}{x}_u\\ y_u\end{array}\right)={\left(\begin{array}{c}2(x_{a1}-x_{a3})2(y_{a1}-y_{a3})\\ 2(x_{a2}-x_{a3})2(y_{a2}-y_{a3})\end{array}\right)}^{-1}\left(\begin{array}{c}{x_{a1}}^2-{x_{a3}}^2+{y_{a1}}^2-{y_{a3}}^2+{d_3}^2-{d_1}^2\\ {x_{a2}}^2-{x_{a3}}^2+{y_{a2}}^2-{y_{a3}}^2+{d_3}^2-{d_2}^2\end{array}\right)$

现有技术方案的缺点：

基于RSSI测距定位技术方案普遍存在定位精度不高的缺点，其中定位误差的 主要来源之一就是硬件设备差异所带来的测距误差。已有研究表明，同种类型设 备的RSSI-d模型曲线相近，而不同类型设备之间的RSSI-d模型曲线存在差异，从 而导致在一个存在多种类型设备的网络中，测距计算时使用统一的RSSI-d模型曲 线带来较大的计算误差。

现有技术一只能够部分解决以上问题，但仍存在以下几方面缺点：

(1)在图1场景中，锚节点的设备类型为M1，M2，同时网络中存在A，B，C三种类 型的未知设备节点，现有技术方案一只选择了一个任意的未知节点进行 RSSI-d曲线拟合训练，如选择A，则得到两种模型曲线：

RSSI-d_AM1，RSSI-d_AM2，而该网络中实际存在的模型曲线有六种：

RSSI-d_AM1，RSSI-d_BM1，RSSI-d_CM1，RSSI-d_AM2，RSSI-d_BM2，RSSI-d_CM2

因此，现有技术方案一并未完全消除未知设备差异性所带来的计算误差。

(2)该方案针对每个锚节点都进行相应的RSSI-d模型训练，当锚节点设备类型相 同时，训练成本与代价过高，如图1中，共4个锚节点，该方案需进行4次锚 节点的RSSI-d模型训练。而实际上，考虑成本与代价因素，只要分别对M1 与M2两种设备个分别进行一次RSSI-d模型训练即可。

(3)现有技术方案一与其他定位方案存在一种共性的缺点：未能充分考虑未知节 点对自身定位的启发性与决定性。未知节点有权决定自身定位参数，并可根 据自身情况进行启发式的自适应定位。如，未知节点向Anchor发送一定量数 据包并获取RSSI均值，以消除少量或单次RSSI所带来的不稳定误差，当数据 包数量越大时，RSSI值越准确，然而未知节点与Anchor消耗的能量与定位时 间却会增加。因此，在定位精度与定位能量消耗、定位时间三个指标上存在 矛盾，可以设计有效的算法平衡三者之间的矛盾，当前的技术方案均未考虑 此因素。

发明内容

技术问题：本发明是在现有技术方案上，提出的一种无线传感器网络中的启 发式参数自适应定位方法，本发明克服了现有技术的缺点，提高无线传感器网络 未知节点的定位精度，有效平衡定位精度，定位能耗，定位时间三者之间的矛盾， 从而改善未知节点的定位性能。

技术方案：针对现有技术方案的缺点，通过在网络中设置一个RSSl-d自动 训练区，有效实现RSSl-d模型训练，并将网络中的锚节点按照等边三角形布置， 并且锚节点设置为统一设备，未知设备进入网络区域后，首先进入RSSl-d自动 训练区进行RSSl-d模型训练，获得与当前网络锚节点之间的RSSl-d模型曲线， 以消除设备差异性带来的测距误差。同时，RSSl-d自动训练区设置一个节点， 记录以往设备类型的RSSl-d模型数据，当未知设备未能查询到与己相关的模型 信息后才进行模型训练，有效的简化了RSSl-d模型训练的步骤，降低训练成本 与代价；针对现有技术方案的缺点(3)，设计了一种最优性能评价模型，将定位 精度、定位能耗、定位时间三者纳入性能评价体系，由未知节点自身给出三者在 定位性能中所占权重，通过最优性能评价函数计算相关定位参数，以获得最优定 位性能。仿真结果表明，本发明在相关定位参数相同的情况下，定位精度高于现 有技术方案。

本发明的一种无线传感器网络中的启发式节点定位方法具体包括以下两个 过程：

步骤一.接收信号强度指示RSSI与实际距离d之间的模型曲线训练 RSSI-d模型训练在RSSI-d自动训练区内完成，步骤如下：

1)未知节点进入RSSI-d自动训练区，向RSSI-d模型存储节点M_E发送RSSI-d 模型查询请求数据包Rd_search_request，M_E根据自身存储情况响应，向 未知节点发送RSSI-d模型查询回复数据包Rd_search_reply；

2)未知节点根据Rd_search_reply数据包内容，若得到本类型设备的RSSI-d 模型数据，则本过程结束，进入步骤二未知节点自身定位过程；若未查 询到本类型设备的RSSI-d模型数据，则进行步骤3)；

3)未知节点向RSSI-d自动训练区内的训练锚节点M_T广播RSSI-d模型训练 请求数据包Rd_train_request，Rd_train_request广播次数为N_T，广播间隔 为T_T；

4)RSSI-d自动训练区内的训练锚节点在收到来自未知节点的 Rd_train_request包后，回复RSSI-d模型训练回复数据包Rd_train_reply；

5)未知节点在收到各训练锚节点M_T的Rd_train_reply数据包之后，计算与各 M_T之间的RSSI均值，并根据已知的距离信息d_1...m，使用最小二乘法进 行拟合，得到本类型设备与网络锚节点之间的RSSI-d模型；

6)未知节点向存储节点M_E发送自身的RSSI-d模型数据包，M_E收到后存储 该未知节点类型设备的RSSI-d模型数据；

步骤二.未知节点自身定位

21)未知节点进入定位区，根据自身状况确定定位精度、定位时间、定位 能耗三者所占权重a₁，a₂，a₃，然后根据最优性能评价函数计算定位参数： 定位请求包个数N_L；定位请求包发送间隔T_L；

其中，最优性能评价函数的构造方法遵循以下步骤：

a)确定性能评价指标定位精度、定位时间、定位能耗三者所占权重 a₁，a₂，a₃，且a₁+a₂+a₃＝1；

b)确定定位精度、定位时间、定位能耗三者与定位请求包个数n以及定位请求包发 送间隔t之间的函数关系f(n，t)、g(n，t)、h(n，t)，函数关系如下：

$f(n,t)=\frac{{\sigma }^2}{n}$

g(n，t)＝nt

h(n，t)＝ne_o+(n-1)te_m

其中σ²为噪声方差，节点发送一次请求包或回复包能耗为e_o，节点正常工作状态 的每秒平均能耗为e_m；

c)建立最优性能评价函数：

(M_fmin，M_fmax )，(M_gmin，M_gmax)，(M_hmin，M_hmax)分别为f(n，t)、g(n，t)、h(n，t)的 值域；

在构造最优性能评价函数之后，求取使得最优性能评价函数取最小值时的n，t值， 分别赋予N_L，T_L；

22)未知节点向定位区域内的定位锚节点M_L广播定位请求数据包 Lo_request，广播次数为步骤21)中计算所得N_L，发送间隔为步骤21)中 计算所得T_L；

23)定位锚节点M_L在收到来自未知节点的Lo_request请求包后，立即回复 定位回复数据包Lo_reply给未知节点；

24)未知节点在收到来自各定位锚节点M_L的Lo_reply回复包之后，计算 与各定位锚节点M_L之间的RSSI均值，然后根据自身的RSSI-d模型计算得 到与各定位锚节点M_L之间的距离值d_ML1...d_MLN；

25)未知节点可能收到来自三个以上定位锚节点的回复包，根据步骤24) 计算得到的距离值，选择出三个最小值d_ML1，d_ML2，d_ML3，并与相应定位锚 节点对应；

26)未知节点根据步骤25)选择出的与三个定位锚节点之间的距离信息， 使用三边测量法计算得到未知节点自身坐标。

有益效果：

(1)本发明考虑到现有技术方案未能有效解决基于RSSI测距定位时，由于设备 差异性所引入的测距误差问题，提出了一种RSSI-d模型自动训练机制。该 机制在网络中设置一块独立自主的RSSI-d模型训练区，同时将网络中所有 锚节点布置为统一类型，未知节点进入网络后，首先进行RSSI-d模型的查 询与训练，以获取未知节点与本网络中锚节点之间的RSSI-d模型，从而有 效的解决了由于设备差异性所引入的测距误差问题。对本发明的技术方案进 行了仿真，图4与图5分别显示了当未知节点个数与噪声变化时，定位精度 的变化趋势。定位精度的计算式为：AverageError

表示平均误差，其计算方法为R表示节点通信半 径，可以看出，定位精度值越小，定位精度越好。由图4可以看出当未知节 点的个数变化时，定位精度基本不变，因为网络中的定位精度与未知节点个 数无关，但是本发明技术方案的定位精度较现有技术方案的定位精度明显提 升；由图5可以看出，当噪声增加时，定位精度变差，但是本发明技术方案 比现有技术方案定位精度明显提升。

(2)本发明针对现有技术方案中未知节点对自身定位没有自主权，无法根据自身 生命状态决定定位参数等缺陷，引入了最有性能评价机制，使得未知节点能 够根据自身现状有效决定定位参数，使得定位精度、定位时间、定位能耗三 者达到有效平衡。图6的仿真结果显示了定位精度随定位请求报个数变化的 趋势。由图6可以看出，当定位回复包个数增加时，定位精度提升，相应的 定位时间增加，定位能耗增加。因此，未知节点可以根据自身状态决定定位 参数。

附图说明

图1是现有技术方案定位场景示意图，

图2是本发明定位区域场景示意图，

图3是本发明定位流程示意图，

图4是定位精度随未知节点个数变化关系示意图，

图5是定位精度随噪声变化关系示意图，

图6是定位精度随定位请求包个数变化关系示意图。

具体实施方式

实施例一：

本发明的具体实施场景如图2，本方案将定位区域分为两部分：

(1)RSSI-d自动训练区，用于未知节点与区域内锚节点之间RSSI-d模型的训练与 存储。未知节点进入该区后位于该区域的中心，用U标识，在不同方向上与U 相距分别为d₁，d₂，......，d₆的位置上布置有锚节点，未知节点通过广播数据包 给所有锚节点，获取与各锚节点之间的RSSI值信息，然后根据已知的距离信 息训练得到该未知节点与本网络中锚节点之间的RSSI-d模型曲线，得到模型 曲线后，由中心锚节点进行存储；

(2)定位区，当未知节点在RSSI-d自动训练区获得RSSI-d模型曲线后，进入定位 区进行实际定位。定位区锚节点与RSSI-d自动训练区的锚节点类型相同，因 此消除了设备差异性带来的测距误差。定位区锚节点按等边三角形布置，锚 节点位于三角形顶点处，如图2中的M，在定位区的边缘，等边三角形布置蜕 化为等腰直角三角形，等边三角形边长设为节点通信半径R。未知节点进入 定位区后，首先根据最优性能评价函数确定定位参数，定位参数有：

1)定位请求包个数n；

2)定位请求包发送间隔t。

最优性能评价函数为：

E(n，t)＝f(n，t)+g(n，t)+h(n，t)

其中f(n，t)为定位精度权重参数函数，g(n，t)为定位时间权重参数函数， h(n，t)为定位能耗权重参数函数，最优性能评价函数根据最优性能评价模型 进行设计，本发明设计的最优性能评价函数为：

$E(n,t)=a1\frac{\frac{{\sigma }^2}{n}-M_{f\min }}{M_{f\max }-M_{f\min }}+a_2\frac{\mathrm{nt}-M_{g\min }}{M_{g\max }-M_{g\min }}+a_3\frac{[{\mathrm{ne}}_o+(n-1)e_m]-M_{h\min }}{M_{h\max }-M_{h\min }}$

其中，节点发送一次请求包或回复包能耗为e_o，节点正常工作状态的每秒平 均能耗为e_m，a₁，a₂，a₃分别是节点自身对于定位精度、定位时间、定位能耗 的权重因子，且a₁+a₂+a₃＝1。(M_fmin，M_fmax )，(M_gmin，M_gmax)，(M_hmin，M_hmax)分 别为f(n，t)、g(n，t)、h(n，t)的值域。在实际定位前，需根据网络约束条件 求取使得E(n，t)最小的参数值(n，t)。

计算得到定位参数(n，t)之后，未知节点向锚节点广播定位请求，获取与锚节 点之间 的RSSI值，去均值最小的三个锚节点，根据与此三个锚节点之间的RSSI值计 算距离，最后采用三边测量法计算自身坐标。

本发明的具体实施过程包括以下两个过程：RSSI-d模型训练与实际定位。

(1)RSSI-d模型训练

RSSI-d模型训练在RSSI-d自动训练区内完成，步骤如下：

1)未知节点进入RSSI-d自动训练区，向RSSI-d模型存储节点ME发送RSSI-d 模型查询请求数

据包Rd_search_request，M_E根据自身存储情况响应，向未知节点发送 RSSI-d模型查询回复数据包Rd_search_reply；

2)未知节点根据Rd_search_reply数据包内容，若得到本类型设备的RSSI-d 模型数据，则本过

程结束，进入(2)未知节点自身定位过程。若未查询到本类型设备的 RSSI-d模型数据，则进行步骤3)；

3)未知节点向RSSI-d自动训练区内的训练锚节点M_T广播RSSI-d模型训练 请求数据包Rd_train_request，Rd_train_request广播次数为N_T，广播间隔 为T_T；

4)RSSI-d自动训练区内的训练锚节点在收到来自未知节点的 Rd_train_request包后，回复RSSI-d模型训练回复数据包Rd_train_reply；

5)未知节点在收到各训练锚节点M_T的Rd_train_reply数据包之后，计算与 各M_T之间的RSSI均值，并根据已知的距离信息d_1...m，使用最小二乘法 进行拟合，得到本类型设备与网络锚节点之间的RSSI-d模型；

6)未知节点向存储节点M_E发送自身的RSSI-d模型数据包，M_E收到后存储 该未知节点类型设备的RSSI-d模型数据。过程(1)结束。

(2)未知节点自身定位

1)未知节点进入定位区，根据自身状况确定定位精度、定位时间、定位能 耗三者所占权重a₁，a₂，a₃，然后根据最优性能评价函数计算定位参数：定 位请求包个数N_L；定位请求包发送间隔T_L；

2)未知节点向定位区域内的定位锚节点M_L广播定位请求数据包Lo_request， 广播次数为1)中计算所得N_L，发送间隔为1)中计算所得T_L；

3)定位锚节点M_L在收到来自未知节点的Lo_request请求包后，立即回复定 位回复数据包Lo_reply给未知节点；

4)未知节点在收到来自各定位锚节点M_L的Lo_reply回复包之后，计算与各 定位锚节点M_L之间的RSSI均值，然后根据自身的RSSI-d模型计算得到与 各定位锚节点M_L之间的距离值d_ML1.d_MLN；

5)未知节点可能收到来自三个以上定位锚节点的回复包，根据步骤4)计算 得到的距离值，选择出三个最小值d_ML1，d_ML2，d_ML3，并与相应定位锚节点 对应；

6)未知节点根据步骤5)选择出的与三个定位锚节点之间的距离信息，使用 三边测量法计算得到未知节点自身坐标。未知节点自身定位过程结束。

本发明定位技术方案的具体流程如图3。