文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2020, Vol. 32 Issue (3): 477-486  DOI: 10.3979/j.issn.1673-825X.2020.03.018
0

引用本文 

李烁, 郭天成. 基于WSN的受限空间逃生路径搜索算法[J]. 重庆邮电大学学报(自然科学版), 2020, 32(3): 477-486.   DOI: 10.3979/j.issn.1673-825X.2020.03.018.
LI Shuo, GUO Tiancheng. Restricted space escape path search algorithm based on WSN[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2020, 32(3): 477-486.   DOI: 10.3979/j.issn.1673-825X.2020.03.018.

基金项目

国家自然科学基金(61502055)

Foundation item

The National Natural Science Foundation of China(61502055)

作者简介

李烁(1983-),男,湖南长沙人,讲师,博士,主要研究方向为无线传感器网络,拓扑控制,移动自组织网络。E-mail: lishuo@csust.edu.cn; 郭天成(1994-),男,湖南常德人,硕士研究生,主要研究方向为无线传感器网络和移动计算。E-mail: gtc940921@163.com.cn

通讯作者

李烁 lishuo@csust.edu.cn.

文章历史

收稿日期: 2019-01-09
修订日期: 2020-02-13
基于WSN的受限空间逃生路径搜索算法
李烁, 郭天成     
长沙理工大学 电气与信息工程学院,长沙 410114
摘要: 针对地下矿井、隧道等受限环境事故后受困人员营救或逃生困难的问题,通过构建基于混合信道模型的无线传感器网络,提出可信锚节点选择算法,实现在事故后稀疏锚节点环境下的无线传感器网络节点精确位置估计,并在此基础上实现最优的逃生救援路径生成及实时导航。仿真结果表明,算法在稀疏锚节点场景下,相比较于已有研究具有更高的节点定位精度,并且能够在动态障碍物识别的基础上准确进行救援或逃生路径的搜索。
关键词: 无线传感器网络    地下无线通信    灾难救援    路径搜索    定位算法    
Restricted space escape path search algorithm based on WSN
LI Shuo , GUO Tiancheng     
School of Electrical & Information Engineering, Changsha University of Science and Technology, Changsha 410114, P.R.China
Abstract: Aiming at the rescue or escape of trapped people after a confined environmental accident such as an underground mine or tunnel, this paper proposes a trusted anchor node selection algorithm through constructing a wireless sensor network based on hybrid channel model to realize the accurate location estimation of wireless sensor network nodes in sparse anchor node environment after an accident, generate the optimal escape rescue path, and realize real-time navigation. The simulation results show that the algorithm has higher node positioning accuracy than the existing research in the sparse anchor node scenario, and can accurately search the rescue or escape path based on the dynamic obstacle recognition.
Keywords: wireless sensor network    underground wireless communication    disaster relief    route search    location algorithm    
0 引言

当今社会在不断提高应对各种灾害的能力,可灾害来临后依然会对人们的生命财产带来巨大的损失。绝大多数受灾环境会呈现出一个受限空间,被困人员的自身位置无法通过传统的全球定位系统(global positioning system, GPS)确定。以往灾难环境路径搜索主要利用仿生机器人[1]或者生命探测器来确定被困人员基本位置,这些研究虽然适用受限空间中的救援,但是其对被困人员的搜索范围与速率都存在一定局限性。随着无线传感器网络(wireless sensor network, WSN)的广泛应用,WSN强大的自组织性和环境感知能力被越来越多的人应用到灾难救援中[2]

使用WSN可以快速实现受灾环境的监测、人员定位、目标追踪等一系列工作[3]。这些工作的前提都基于节点定位,无线传感器网络节点自身定位算法从定位手段上可以分为基于测距(Range-based)和距离无关(Range-free)2类[4]。Range-based算法通过测量点到点之间的距离和角度信息来实现对未知节点的定位,常用的Range-based定位测距技术有接收信号强度指示(received signal strength indication, RSSI),到达时间(time of arrival, TOA),到达时间差(time difference of arrival, TDOA),到达角度(angle of arrival, AOA)。Range-based定位算法中,文献[5]提出了一种分层定位方法,该算法通过筛选具有固定连接度的框架节点并分步定位。实验表明,该方法可以简化计算和减少通信开销。文献[6]结合RSSI测距技术实现节点定位估计,实验表明,节点的定位估计不仅需要准确测量RSSI值,同样需要高精度的节点定位方法。文献[7]将人工神经网络和支持向量机应用在节点定位估计上,虽然能够有效降低RSSI测量的不确定因素,但是算法复杂而难以实现。

Range-free算法则无需距离和角度信息就能实现定位,常见的Range-free定位算法有基于距离矢量计算跳数(distance vector-hop, DV-Hop)算法,凸规划,基于多维标度定位算法(multidimensional scaling, MDS)等。Range-free算法在面对各向同性网络时有着很高的准确性,并且无需额外的硬件支持。文献[8]在DV-Hop算法的基础上预先设置max-hop,当未知节点接收到的锚节点跳数信息大于max-hop,则忽略该锚节点的信息。该算法能够更快更准估计网络,相对DV-Hop算法有着更高的精度。文献[9]提出了一种选择可信锚节点的定位算法,算法主要寻找最小跳跃长度来近似锚节点与节点之间的距离,并且将定位完成的节点升级成锚节点来降低锚节点密度。实验表明,通过使用可信锚节点可以提高定位精度。若将Range-free算法应用到受限空间,受多种因素的影响,往往无法达到理想的精度,并且面对锚节点稀疏的网络时,Range-free算法的定位精度很低。

为快速得到灾后环境逃生救援路径与稀疏锚节点和受限环境节点定位难问题,论文提出了一种基于混合信道模型无线传感器网络的受困人员及逃生路径快速生成及导航算法。文章主要贡献如下。

1) 提出了地下矿井、隧道等受限空间逃生或救援路径搜索的基本框架,为此类场景下实现以安全预警和逃生救援为目标的无线传感器网络部署提供了参考。

2) 建立了无线传感器网络的混合信道模型,通过该模型可实现复杂乃至动态环境下的障碍物检测,构建自动避障的网络拓扑,完成多条可能逃生路径的快速搜索。同时,根据障碍物的检测结果及接收信号强度,该模型可实现节点间距离的精确估计。

3) 设计了可信锚节点选择算法,结合混合信道模式,实现稀疏锚节点环境中无线传感器网络节点的精确位置估计,以确定最优的逃生救援路径。最后,采用文献[10]提出的历史信息定位算法解决逃生导航的移动节点定位问题。

本文所用符号及其意义如表 1

表 1 符号以及其意义 Tab.1 Symbol and its meaning
1 基于WSN的逃生救援路径搜索框架

无线传感器网络节点均匀地分布在受限空间环境中,要求节点平均邻居节点密度不小于12,每个工作人员自身带有传感器节点,称为目标节点(target node)。灾难事故逃生救援路径搜索框架如图 1

图 1 基于混合信道模型无线传感器网络的逃生救援路径搜索框图 Fig.1 Block diagram of escape rescue path search based on hybrid channel model wireless sensor network

事故前后网络拓扑图及可能逃生的救援路径如图 2

图 2 事故前后网络拓扑变化及可能逃生救援路径 Fig.2 Network topology changes before and after the accident and possible escape routes

假设事故前后网络环境会发生如下变化。

1) 未发生事故前见图 2a,所有节点位置被认为是已知的。

2) 发生事故后,环境及网络发生以下变化:①部分节点失效(节点密度降低);②环境中障碍的数量或形状发生变化;③大部分节点的位置改变,少量位置不变的节点为锚节点,形成稀疏锚节点场景,见图 2b

3) 基于混合信道模型的无线传感器网络利用自组织性对网络进行重构,从而确定所有可能的逃生救援路径,见图 2c。通过节点位置的精确估计实现最优的逃生或救援路径选择。

2 混合信道模型

受限空间无线信道具有传播距离小、环境复杂等特点。因此,要求无线信号不仅具有反射、绕射、多径效应等机理,同时还要排除障碍物等因素的影响。在RSSI基础上构建混合信道模型实现逃生救援路径的搜索,其主要解决了节点间障碍的检测和距离估计。

2.1 障碍检测

结合RSSI信号特性及空间特性,利用30个收发天线对分别在有障碍和无障碍的情况下测量RSSI变化值的平均值Δϕk作为判断无障碍的依据。直接计算Δϕk=|RSSI无障碍, kRSSI有障碍, k|,其中,Δϕk为不同天线中对应的RSSI变化值(k∈[1, 30]),最终用于障碍检测为

$ \Delta {\phi _{{\rm{Thr}}}} = \frac{{\sum\limits_{k = 1}^{30} \Delta {\phi _k}}}{{30}} $ (1)

通过对比事故前后相同节点之间的RSSI测量值,Δϕ在无障碍和有障碍情形下具有不同的情况:无障碍情况下,Δϕ值较小;有障碍情形下,Δϕ值普遍比较大。通过与预先设定阈值ΔϕThr作比较,当Δϕ≤ΔϕThr时,则判定为无障碍,否则为有障碍。

2.2 基于混合信道模型距离估计

为了准确搜索出受限环境中目标节点与出口之间的最优路径,需要高精度的节点定位,所以需要构建混合信道模型来提高节点距离估计以提高节点定位精度。考虑到受限空间的多种因素,使用对数正态阴影模型[11]来估计节点间的距离,传播模型损耗为

$ {L_{\rm{p}}}(d) = {L_{\rm{p}}}({d_0}) + 10{n_{\rm{p}}}\left( {\frac{d}{{{d_0}}}} \right) + {X_\sigma } $ (2)

(2) 式中:d为传播距离(单位:m);d0为参考距离;np表示发送端与接收端的路径损耗指数;Lp(d0)为距离d0处的信号强度;Xσ服从均值0,标准差为σ2的高斯分布。

当节点间存在障碍时,将隔墙的损耗等因素引入到对数正态阴影模型中,传播模型损耗为

$ {L_{\rm{p}}}(d) = {L_{\rm{p}}}({d_0}) + 10{n_{\rm{p}}}\left( {\frac{d}{{{d_0}}}} \right) + {X_\sigma } + \sum\limits_{m = 1}^{{N_{\rm{b}}}} {{\omega _m}} $ (3)

(3) 式中:Nb代表隔墙层数;ωm表示第m个隔墙的衰减因子。通过确定墙壁的衰减因子,可以计算出发射与接收节点之间的距离。

混合信道模型为

$ \left\{ \begin{array}{l} {L_{\rm{p}}}(d) = {L_{\rm{p}}}({d_0}) + 10{n_{\rm{p}}}\left( {\frac{d}{{{d_0}}}} \right) + {X_\sigma },\Delta \phi \le \Delta {\phi _{{\rm{Thr}}}}\\ {L_{\rm{p}}}(d) = {L_{\rm{p}}}({d_0}) + 10{n_{\rm{p}}}\left( {\frac{d}{{{d_0}}}} \right) + {X_\sigma } + \sum\limits_{m = 1}^{{N_{\rm{b}}}} {{\omega _m}} ,\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \Delta \phi > \Delta {\phi _{{\rm{Thr}}}} \end{array} \right. $ (4)

1) 对于无障碍而言,无线信号发射端与接收端之间无隔墙等障碍物的阻挡,在推导路径损耗与信号传播距离之间的关系时可采用对数正态阴影模型。

2) 对于有障碍而言,只有对对数正态阴影模型进行衰减补偿才能正确反映路径损耗与信号传播距离之间的关系,且收发双方之间障碍物材质或层数不同时,需补偿的衰减因子也不尽相同。

3 可信锚节点选择定位及最佳路径选择算法

在稀疏锚节点的网络中,存在位置未知节点的邻居节点集合中包含锚节点的个数小于3的情况,无法直接采用已有的定位算法实现对此类节点的位置估计。

可信锚节点判断如图 3,节点1的邻居节点集合中只包含2个锚节点,无法直接对其实现位置估计,因此,节点1需要寻找其一跳范围之外的远端锚节点作为位置估计算法的参考节点。而在存在障碍物的网络中,并非所有的远端锚节点都可以作为位置估计算法的参考节点。节点2和节点3都为节点1的远端锚节点,但因为障碍物的存在,节点1与节点3之间的实际距离远小于通过RSSI测距结合跳数信息所估算出的距离,定义节点2为节点1的非可信锚节点。而节点3与节点1的实际距离与估算距离近似,定义节点3为节点1的可信锚节点。

图 3 可信锚节点判断 Fig.3 Trusted anchor node judgment

综上所述,在有障碍物且锚节点稀疏的无线传感器网络中,对位置未知节点进行位置估计时,其关键问题是实现远端锚节点的可信判别。论文进行可信判别的基本思想是位置未知节点X根据已有的定位相关信息,计算其与某一远端锚节点A的可能的最短平均每跳距离hlshort,同时根据网络的节点分布密度计算和与远端锚节点的跳数信息,计算出理论的最小每跳距离hlmin。当hlshorthlmin时,说明位置未知节点X与远端锚节点A之间绕行严重,该远端锚节点AX的非可信锚节点;反之,则远端锚节点AX的可信锚节点。

3.1 稀疏锚节点网络中可信锚节点选择阈值的确定

选择最小每跳距离hlmin作为可信锚节点判别的阈值,节点的hlmin的大小取决于平均每跳长度hl与锚节点之间的跳数h。其中,平均每跳长度hl由邻居节点密度ρ决定,由文献[9]可知hl

$ hl = r\left( {1 + {{\rm{e}}^{ - \rho }} - \int_{ - 1}^1 {{{\rm{e}}^{\frac{\rho }{\pi }({\rm{arccost}} - t\sqrt {1 - {t^2}} )}}} {\rm{d}}t} \right) $ (5)

由(5)式可知,当邻居节点密度ρ越大,hl也越大。为保证网络的连通性,在计算hlmin时,一般要求邻居节点密度ρ不小于6[12]。当邻居节点密度过高时,hl的极限值为r,其中,r为通信半径,所以每跳距离最大为r

$ \left\{ {\begin{array}{*{20}{l}} {h = 1,h{l_{{\rm{min}}}} = 0}\\ {h = 2,h{l_{{\rm{min}}}} = \frac{r}{2}}\\ {h = 3,h{l_{{\rm{min}}}} = \frac{{r + hl}}{3}}\\ {h = k,h{l_{{\rm{min}}}} = \frac{{r + (k - 2)hl}}{k},k \ge 3} \end{array}} \right. $ (6)

下面给出理论最小每跳长度hlmin的估计方法:当跳数h=1时,未知节点可能无限接近锚节点,所以,$p{l_{\min }} = 0, h{l_{\min }} = \frac{{p{l_{\min }}}}{h} = 0$;当跳数h=2时,未知节点位置可能无限接近以锚节点自身坐标为圆心,通信半径为半径的圆上,所以最小路径长度plmin=r$h{l_{\min }} = \frac{{p{l_{\min }}}}{h} = \frac{r}{2}$;当h=3时,因为最小路径长度为plmin=r+hl,所以,$h{l_{\min }} = \frac{{p{l_{\min }}}}{h} = \frac{{r + hl}}{2}$;同理,当$h{l_{\min }} = \frac{{p{l_{\min }}}}{h} = \frac{{r + (k - 2)hl}}{2}, k \ge 3$

图 4为不同邻居节点密度下理论最小每跳距离。

图 4 不同邻居节点密度下理论平均每跳距离 Fig.4 Theoretical average hop distance for different neighbor node densities
3.2 稀疏锚节点网络中可信锚节点的选择

分情况计算不同邻居节点个数下未知节点与锚节点之间可能的最短距离,当最短平均每跳距离hlshort>理论最小每跳距离hlmin时,认为锚节点是可信的,其主要思想如算法1。

算法1  稀疏锚节点网络中可信锚节点选择。

变量定义:锚节点集A; 锚节点数m; 未知节点数k;

邻居锚节点集Neighbor_anchor_set;

可信锚节点集Reliable_anchor_set.

1:for i=1:kjA

2:Reliable_anchor_set(i)=Neighbor_anchor_set(i);

3:确定节点iρi,利用(5)式计算hl(i);

4:threshold=lookup(hl(i), hij);

5:if Neighbor_anchor_set(i)=1 (邻居锚节点A1)

6:节点i距离锚节点j可能的最短距离坐标X1(x1i, y1i);

7:计算X1与锚节点j之间的欧氏距离dshort ;

8:end if

9:if Neighbor_anchor_set(i)=2 (邻居锚节点A1A2)

10:确定圆C1与圆C2交点坐标X1(x1i, y1i)和X2(x2i, y2i);

11:计算交点与锚节点j之间的欧氏距离d1d2;

12:dshort=min{d1, d2};

13:end if

14:hlshort=dshort/hij;

15:if hlshort> threshold

16:reliable[j]=true;

17:Reliable_anchor_set(i)=j;

18:end if

19:end for

当邻居节点集合中锚节点个数n(i)=1时,确定未知节点与锚节点之间的可能的最短距离情况如图 5,锚节点A1为未知节点X邻居锚节点,结合混合信道模型得到锚节点A1与未知节点X之间的距离值d1_rssi。此时,可以认为未知节点X的位置位于以锚节点A1为圆心,d1_rssi为半径的圆C1上。

图 5 n(i)=1时,未知节点可能的位置情况 Fig.5 Possible position of unknown node when n(i)=1

为了判断锚节点A2是否为未知节点X的一个可信的锚节点,在圆C1上能够找到一个点到锚节点A2距离最短(即点X1,距离为dshort)。由(7)式可以计算出最短平均每跳距离hlshort。当hlshorthlmin时,可以认为A2锚节点为节点X的一个可信的锚节点。

$ h{l_{{\rm{ short }}}} = {d_{{\rm{ short }}}}/h $ (7)

当邻居节点集合中锚节点个数n(i)=2时,情况如图 6,锚节点A1A2为未知节点X邻居锚节点,利用混合信道模型确定锚节点A1A2分别与未知节点X之间的距离值d1_rssid2_rssi。未知节点X的位置为圆C1与圆C2的2个交点之一,点X1与点X2到锚节点A1之间的欧氏距离分别为d1d2。选择min{d1, d2}的距离作为锚节点与节点X之间的最短距离值,运用(7)式计算最短平均每跳距离。同理,当min{d1, d2}/hhlmin时,可以认为A3锚节点为节点X的一个可信的锚节点。

图 6 n(i)=2时,未知节点可能的位置情况 Fig.6 When n(i)=2, the possible location of the unknown node
3.3 基于节点定位的最佳路径搜索

通过确定目标节点与出口锚节点之间跳数与距离信息选择跳数最小且距离最近的路径作为最佳路径,其算法主要思想如算法2。

算法2   基于节点定位的最佳路径搜索。

变量定义:目标节点和出口锚节点最小跳数Mini_hop;

目标节点和出口锚节点最小跳数链路集Mini_hop_link_set;

目标节点和出口锚节点最小跳数链路条数link_number;

目标节点和出口锚节点最小跳数链路距离link_distance;

1:未知节点通过Flooding路由方式记录与之通信锚节点的坐标及最小跳数;

2:for i=1: Mini_hop-1

4:  if i=1(目标节点开始)

5:    搜索节点的邻居节点,使邻居节点到出口锚节点跳数满足Mini_hop-i;

6:  else if i>1 (目标节点邻居节点开始)

7:    搜索节点的邻居节点,使其到出口锚节点跳数满足Mini_hop-i;

8:   end if

9:  将搜索出来的节点信息录入Mini_hop_link_set(i, :);

10:end for

11:确定最小跳数链路条数link_number;

12:for i=1: link_number

13:  分别计算每条链路上节点间距离link_distance(i);

14:end for

15:选择min{link_distance}作为最佳路径

当未知节点确定了3或3个以上的可信锚节点,节点便可以通过可信锚节点对自身进行定位。当n(i)≥3时,结合混合信道模型能够测得未知节点与锚节点之间的距离。此时,采用三边测距定位算法[13]计算节点坐标。

当0 < n(i)≤2时,需要对未知节点进行可信锚节点选择,选出除了邻居锚节点外其他锚节点作为可信锚节点,结合混合信道模型以多跳的形式实现未知节点与锚节点的距离估计。此时,由于距离估计往往会大于实际距离,使得采用三边测距方法不能交于一点,以3个锚节点为圆心的圆不会相交于一点而会构成一个区域。此时采用三边测距算法与质心算法相结合的方法[14]估计未知节点坐标。

4 移动节点定位导航

通过对事故后的网络节点进行定位,最终确定了一条逃生路径。为了让目标节点在逃生时不偏离逃生路径,需要实时对目标节点进行导航。导航的关键在于受困人员自身位置的确定,此时,网络中除了目标节点,其他节点被认为是锚节点,在锚节点密度非常高的网络仅使用邻居锚节点来实现目标节点的定位。由于目标节点处于不断运动的状态,节点间距离的测量会存在延迟,同时距离本身也会存在一定的测量误差,因此,会导致节点定位的不准确。此外,由于节点运动的不确定性,可能会出现目标节点无邻居锚节点情况,运用文献[10]提出的历史信息定位算法来解决这一问题。

将目标节点前一次的定位信息作为虚拟邻居锚节点参与当前定位可以有效减小误差。使用目标节点前一次的定位信息参与此时节点定位时,要求目标节点可以存储其前一次的定位坐标以及节点此时与前一定位时刻的距离值,在此条件下,将前一次的定位坐标信息引入当前定位过程中,结合本次定位状态下移动目标节点通信范围内的邻居锚节点信息,得到移动目标节点的最终坐标。当目标节点通信半径内没有可以参与测距的锚节点时,通过储存的前一次的目标节点定位信息,利用角度定位算法[15]可以得到目标节点此时的位置信息。

假设t时刻目标节点坐标为(xt, yt),t时刻的绝对角度为φtt-1时刻的坐标为(xt-1, yt-1),相对移动角度为θt-1, t,相对移动位移为st-1, t,则t时刻目标节点坐标为

$ \left\{ {\begin{array}{*{20}{l}} {{x_t} = {x_{t - 1}} + {s_{t - 1,t}} \cdot {\rm{cos}}{\varphi _{t - 1}}}\\ {{y_t} = {y_{t - 1}} + {s_{t - 1,t}} \cdot {\rm{sin}}{\varphi _{t - 1}}}\\ {{\varphi _{t - 1}} = {\varphi _t} - {\theta _{t - 1,t}}} \end{array}} \right. $ (8)

历史信息节点估计算法如图 7

图 7 历史信息节点估计算法 Fig.7 Historical information node estimation algorithm

在目标节点导航算法中,要求目标节点定位信息包中可以储存最近一次的定位信息。假设当前时间为tn,此时,目标节点信息包中存储tn-1时刻的定位信息,其中,包括节点坐标、节点相对变化角度θ和节点之间的相对位移s。当目标节点的前一次记录更新一次时,信息包会自动覆盖上一条定位信息。目标节点初始位置由第3节的节点定位算法完成。

当最优路径确定后,人工为目标节点设定其v0aθ,此时目标节点开始移动。当节点速度超过规定范围会重新为节点给定一个随机速度;当节点面对超出边界或墙壁的位移时,重新给定一个角度移动。

5 仿真

论文使用matlab对上述算法进行仿真,可能逃生救援路径生成的网络拓扑变化仿真如图 8。假设未知节点N与锚节点Na随机散布在80 m×80 m的各向异性环境,通信半径r=18 m。图 8a代表事故发生前网络拓扑结构,105个节点位置已知且均匀分布。事故发生后的环境网络见图 8b,此时,其中未知节点80、锚节点5。对图 8b进行网络重构确定目标节点与出口之间可能的逃生路径,见图 8c。其障碍利用障碍生成算法随机生成。

图 8 可能逃生救援路径生成的网络拓扑变化仿真 Fig.8 Simulation of network topology changes generated by possible escape rescue paths
5.1 可信锚节点可信判断与定位误差分析

首先验证选择出来的可信锚节点准确性,然后比较相同环境下本文算法与DV-distance[16],RAL[9],SDP-URSS[17]来验证算法对节点定位的准确性。

在验证可信锚节点选择准确性方面,随机生成未知节点N=60,80,100,120,锚节点Na=10的各向异性网络,各场景分别做100次仿真。仿真过程如下:使用算法1确定未知节点第一次迭代可信锚节点集,在保证可信锚节点可信度在90%以上情况下,确定节点平均定位误差,当节点平均定位误差小于0.3r时认为选择的可信锚节点准确。

在运行100次实验得到的结果中随机选取一组作为实验结果。仿真结果如图 9,只有极少数未知节点存在选择错误的情况,可信锚节点的选择策略效果良好。x轴和y轴代表未知节点2维坐标,z轴代表可信锚节点集合中错误可信锚节点个数。

图 9 第一次迭代可信锚节点集准确性判断 Fig.9 Accuracy judgment of the set of trusted anchor nodes in the first iteration

在验证节点定位准确性方面,选择标准均方根误差(normalized root mean square error, NRMSE)作为评价定位精度的标准,NRMSE定义为

$ e=\frac{\sum\limits_{i=1}^{m}{\sqrt{{{({{x}_{i}}-{{x}^{'}}_{i})}^{2}}+{{({{y}_{i}}-{{y}^{'}}_{i})}^{2}}}}}{mr} $ (9)

图 10为不同节点数NRMSE计算结果。图 10中,在保证锚节点数Na=6情况下,NRMSE在不同节点数目时的情况。随着节点数目增加,本文提出的算法没有DV-distance与RAL算法下降趋势明显,这是由于定位过程中迭代次数随着节点数的增多而增加,使得定位精度没有得到相应的提高。尽管在节点数N=200时的精度低于SDP-URSS,但是其定位精度依然低于0.5r

图 10 不同节点数NRMSE计算结果 Fig.10 NRMSE calculation results for different node numbers

图 11表示NRMSE在N=80的各向异性网络通过改变锚节点Na的变化情况。随着锚节点数目的增加,节点的定位精度也越来越高。通过比较,本文提出的算法精度明显高于其他3种算法,即使在稀疏锚节点的情况下依然能够保证NRMSE低于0.4r

图 11 不同锚节点NRMSE计算结果 Fig.11 NRMSE calculation results for different anchor nodes

图 12为各向异性网络环境下NRMSE的累积分布函数(cumulative distribution function,CDF)图。使用本文提出的方法大约95%的未知节点的位置估计误差低于r。然而,同样的精确度下,RAL大约只有75%,DV-distance则更低。进一步说明了本文提出算法的有效性。

图 12 NRMSE的CDF分布图 Fig.12 CDF distribution of NRMSE
5.2 最佳路径确定及受困人员移动导航

利用网络路由协议为环境中的节点进行数据传输,最终未知节点能够记录锚节点的位置信息与最小跳数信息。使用论文提出的定位方法对图 8b进行节点定位。最终在路由协议收集的最小跳数信息节点集中找到一条距离最短的路径作为最佳的路线图,如图 13

图 13 最终路线图,NRMSE=0.31r Fig.13 Final route, NRMSE=0.31r

导航结果如图 14。假设受困人员移动速度为v=[3, 6] m/s。采用历史信息定位方式对受困人员进行移动定位。由图 14可以看出,通过对受困人员进行实时定位,受困人员大致沿着逃生路线进行移动,说明提出的算法具有比较高的定位精度。

图 14 导航结果 Fig.14 Navigation result
6 结束语

基于混合信道模型无线传感器网络的逃生路径搜索算法,通过构建混合信道模型实现对多障碍物的受限环境中的避障网络拓扑控制及节点间的距离估计,并结合稀疏锚节点选择算法对网络节点进行精确定位,完成灾难下的最优救援及逃生路径生成及导航。仿真表明,本文提出的算法相较现有研究,在稀疏锚节点环境下,可综合提升14.6%的定位精度,以此可实现更准确的最优路径搜索。但现有的可信锚节点选择策略在极端条件下,特别在网络边沿位置,有可能出现错误的可信节点选择,影响定位及路径搜索精度,在下一步研究工作中拟通过改进邻居节点密度估计方法来解决。

参考文献
[1]
白云, 侯媛彬. 煤矿救援蛇形机器人的研制与控制[J]. 西安科技大学学报, 2018(05): 800-808.
BAI Y, HOU Y B. Research on environment modeling method of the coal mine rescue snake-like robot[J]. Journal of Xi'an University of Science and Technology, 2018(05): 800-808.
[2]
张先华, 李政, 谭小慧, 等. 基于灰色马尔科夫的地铁火灾逃生最优路径规划及3D模拟[J]. 重庆理工大学学报(自然科学), 2019, 33(8): 118-123.
ZHANG Xianhua, LI Zheng, TAN Xiaohui, et al. Based on Grey Markov Prediction Algorithm Metro Fire Escape Route Planning and 3D Simulation[J]. Journal of Chongqing University of Technology(Natural Science), 2019, 33(8): 118-123.
[3]
董梦梦, 王翥. 面向机场环境监测的WSN组网技术[J]. 江苏大学学报(自然科学版), 2016, 37(5): 578-584.
DONG M M, WANG Z. WSN networking technology for airport environment monitoring[J]. Journal of Jiangsu University (Natural Science Edition), 2016, 37(5): 578-584. DOI:10.3969/j.issn.1671-7775.2016.05.014
[4]
HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on Mobile computing and networking.San Diego, CA, USA: ACM, 2003: 81-95.
[5]
冯立, 姚远程, 胡荣春. 基于分层定位的无线传感器网络定位研究[J]. 重庆邮电大学学报(自然科学版), 2008, 20(4): 427-430.
FENG L, YAO Y C, HU R C. Research on wireless sensor localization based on hierarchical localization[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2008, 20(4): 427-430.
[6]
ESPINOZA A, REYES E, RUIZ E, et al. Performance Comparison Between Simulated and Real Case Scenario of RSSI Based Localization Algorithms on a WSAN[J]. IEEE Latin America Transactions, 2016, 14(1): 115-121.
[7]
AHMADI H, VIANI F, BOUALLEGUE R. An accurate prediction method for moving target localization and tracking in wireless sensor networks[J]. Ad Hoc Networks, 2018(70): 14-22.
[8]
SHAHZAD F, SHELTAMI T R, SHAKSHUKIE M. DV-maxHop: A fast and accurate range-free localization algorithm for anisotropic wireless networks[J]. IEEE Transactions on Mobile Computing, 2016, 16(9): 2494-2505.
[9]
XIAO B, CHEN L, XIAO Q, et al. Reliable anchor-based sensor localization in irregular areas[J]. IEEE Trans Mobile Comput, 2010, 9(1): 60-72. DOI:10.1109/TMC.2009.100
[10]
刘洁琳.基于无线传感网络的室内移动节点定位技术研究[D].沈阳: 沈阳理工大学, 2018.
LIU J L. Research on Indoor Mobile Node Location Technology Based on Wireless Sensor Network[D]. Shenyang: Shenyang Institute of Technology, 2018. http://cdmd.cnki.com.cn/Article/CDMD-10144-1018141447.htm
[11]
WILLIS S, KIKKERT C J. Radio propagation model for long-range wireless sensor networks[C]//2007 6th International Conference on Information, Communications & Signal Processing. Singapore: IEEE, 2007: 1-5.
[12]
XIAO Q, XIAO B, CAO J, et al. Multihop range-free localization in anisotropic wireless sensor networks: A pattern-driven scheme[J]. IEEE Trans Mobile Comput, 2010, 9(11): 1592-1607. DOI:10.1109/TMC.2010.129
[13]
蓝威涛, 张卫强, 罗健宇. 一种自适应智能三边定位算法的设计与实现[J]. 传感技术学报, 2017, 30(07): 1089-1094.
LAN W T, ZHANG W Q, LUO J Y. Design and Implementation of an Adaptive Intelligent Triangulation Algorithm[J]. Journal of Sensing Technology, 2017, 30(07): 1089-1094. DOI:10.3969/j.issn.1004-1699.2017.07.020
[14]
张宏刚, 黄华. 基于RSSI路径损耗因子动态修正的三边质心定位算法[J]. 传感技术学报, 2016, 29(11): 1731-1736.
ZHANG H G, HUANG H. Trilateral centroid localization algorithm based on dynamic correction of RSSI path loss factor[J]. Journal of Sensing Technology, 2016, 29(11): 1731-1736. DOI:10.3969/j.issn.1004-1699.2016.11.017
[15]
罗雯雯.无线传感器网络自主移动节点定位技术研究[D].浙江: 浙江理工大学, 2013.
LUO W W. Research on Autonomous Mobile Node Location Technology in Wireless Sensor Networks[D]. Zhejiang: Zhejiang University of Technology, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10338-1013290560.htm
[16]
王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005, 16(5): 857-868.
WANG F B, SHI L, REN F Y. Self-positioning system and algorithm in wireless sensor networks[J]. Journal of Software, 2005, 16(5): 857-868.
[17]
OUYANG R W, WONG A K S, LEA C T. Received signal strength based wireless localization via semidefinite programming: Noncooperative and cooperative schemes[J]. IEEE Trans Veh Technol, 2010, 59(3): 1307-1318.