基于WiFi三角定位原理语音寻物探测方法研究

下面是小编为大家整理的基于WiFi三角定位原理语音寻物探测方法研究,供大家参考。希望对大家写作有帮助!

基于WiFi三角定位原理的语音寻物探测方法研究2篇

第1篇: 基于WiFi三角定位原理的语音寻物探测方法研究

1前言

近年来，随着无线通信技术与网络技术的不断发展和全面普及，各种新业务

与新需求层出不穷，其中位置感知计算(Location-aware Computing)和基于位置的服务LBS 在人们的生产生活中起到了至关重要的作用，如何确定用户位置是实施前述应用的首要问题，因此定位技术是位置感知计算和基于位置的服务的核心问题。

根据应用环境与场景的不同，定位技术可分为室内定位技术和室外定位技术。室外定位系统主要有蜂窝定位和全球定位系统 GPS。

蜂窝无线定位即手机定位，是基于移动蜂窝网的基站定位，其定位精度依赖于基站的分布和基站信号覆盖范围的大小。1996 年，美国 FCC 颁布了E-911(Emergency call ‘911’)条例提出了相关的技术要求，要求移动通信提供商必须为用户提供定位准确度在 125m 以内的室外定位服务，2001 年以后，美国 FCC 提出了更严格的准确度和三维空间定位的需求。在政府的要求和市场利润的驱动下，使基于蜂窝移动网的定位技术得到了广泛的应用。

美国的 GPS 系统是目前使用最广泛、用户人数量最多的全球性定位系统。GPS系统由 24 颗卫星组成，在任何时间任何地点地面接收终端都可以同时接受到 4 颗以上的卫星发出的信号。根据电磁波的传播原理，通过卫星信号的到达时间差来计算出搜索到的卫星和终端用户之间的距离，采用三边定位法计算出终端用户的具体位置，其民用定位精度可以达到 15m 以内。同时，其他国家也陆续研究开发出了具有自主知识产权的定位系统，包括和中国的北斗卫星定位系统、俄罗斯的Glonass 定位系统和欧盟的 Galileo 定位系统。

但是在城市环境中，由于 GPS 卫星发射的电磁信号太微弱，楼宇等建筑物阻碍了卫星信号的传播，所以导致了所谓的“都市峡谷”（Urban Canyon）效应，使得 GPS 系统无法正确定位。因此，虽然 GPS 系统在室外环境能够有效地定位，但是在室内环境却无法进行有效的定位。

以上两种定位系统是应用比较广泛的室外定位系统，但应用于室内的时候，

这两种定位系统并不能提供很好的定位服务。首先，由于室内环境复杂，信号在

室内传播的情况要复杂于室外传播的情况。其次，室外定位应用大都是开阔环境中，几十米的定位误差并不影响用户的使用感受；
但对于室内定位应用而言，需

要将定位精度控制在若干米以内，才能为用户提供达可具使用性的室内定位系统。针对室内定位的难点，即克服信号受到环境噪声的干扰，对移动用户的快速定位，对定位精度的高要求，国内外研究人员都进行了有针对性的研究，这些研究涉及到无线网络、传感器技术、随机信号处理等众多交叉领域。

2总体方案设计2.1WiFi室内定位技术的分类

2.1.1 几何法

几何法是利用几何学原理估计用户位置的定位方法，几何法包括三边定位法

和三角定位法，其中前者使用距离作为几何参数，后者使用角度作为几何参数，

以下将简述三边定位法的定位原理。

三边定位法是一种基于测距的定位算法，GPS 全球定位系统是典型的使用三

边定位法进行位置估计的定位系统，根据定位目标与各个参考点的距离使用几何方法得到估计坐标。在二维空间坐标系中，选取三个点作为参考点，这三个点必须是不共线的，在得知它们与定位目标之间距离的情况下即可以计算出定位目标的位置。

如图 2.1.1 所示，已知参考节点 A 、 B 、C 的坐标分别为 ( Xa,Ya )、（Xb，Yb）、（Xc，Yc），测得它们到待定位节点 D 的距离分别为Da 、Db 、Dc，假设节点 D 的坐标为 (x, y) 。

图2-1-1三边定位法示意图

当测得未知节点与信标节点的距离为 d 时，在理想情况下，可认为未知节点在以参考节点为圆心半径为 d 的圆上，三个相交的圆可唯一确定一个点或一个区域，这个点或者这个区域的中心即为未知节点的位置。根据已知参数，可建立如下一组方程：

2.1.2近似法

近似法的原理为在某一范围内监测附近用户，若感知到用户在接近某锚节点时，即可以使用锚节点位置近似计算用户的位置。如图 2-4 所示。

在无线网络中，每个接入点都有一定的覆盖范围，它是连接用户从无线通信

到有线通信的纽带，为无用户提供通信服务，所有进入这一信号区域的无线用户

都可以通过与它的关联实现网络通信。此定位方法是通过 AP 接入点的位置来估计用户的位置，其最大优点是简单，易于实施使用，无需在终端安装任何额外的硬件设备和软件程序，可以使用服务器进行集中监控，常用的服务器接入监控程序可以基于 RADIUS(Remote Authentication Dial-In User Service)协议或者基于SNMP(Simple Network Management Protocol)协议。近似法的定位精度主要依赖于AP 接入点的接入距离，IEEE 802.11 的理论接入距离是室内

100米和室外300 米，但在实际使用中有各种障碍物，如混凝土墙壁和铁对射频信号的屏蔽最大，玻璃、木板、石膏墙等对无线信号的影响最小，所有AP 接入点的有效接入距离是室内3米、室外100米。

图2-1-2 近似法位置估计示意图

2.1.3场景分析法

该方法首先将观察到的环境信息简化成易于量化与计算的信息量，使用相关

的信息量描述物理位置，将所有位置的位置信息量汇总构成环境数据库。在位置

匹配阶段，利用在某一地点观察到的场景特征信息量，使用特定的匹配算法进行

位置匹配，从而分析推断用户的估计位置。

场景分析法的优点在于不用依赖于几何量就可以通过非几何的角度或距离这些的特征估计出物体的位置。测量角度或距离需要添加额外的设备，实施复杂度高，也不利于实际实施。但是，场景分析法也有其不足之处，系统需要获得具体定位环境的特征集，从而与其实时场景特征量进行匹配和定位。而且，环境中的某些环境参数的改变可能会导致先期的环境特征量不再适用，从而可能要重新构建新的特征集。

2.2方案的选择比较

2.2.1定位方法的选取

基于WIFI的室内定位有三种基本定位思路，包括几何法、近似法和场景分析法，表2-2为几种定位方法的对比情况。

表2-2室内定位方法的比较

与基于传播模型的几何法相比，基于位置指纹的定位模型可以提供更高精度

的定位要求，而且具有良好的鲁棒性，可以有效避免由于传播模型不准确所带来

的定位误差，所以基于位置指纹的定位方法成为目前室内定位的主流方向。因此

将基于 Wi Fi和位置指纹的室内定位方法作为本课题的研究对象。

2.2.2定位算法的选取

基于WIFI的室内定位有两种基本的定位算法，分别是最近邻法和朴素贝叶斯法。

3.1.1服务器程序

服务器程序主要由以下功能模块组成：网络通信模块、定位算法模块、

RSSI指纹数据库模块和地图信息模块，其结构如图3-1-1所示。

图3-1-1服务器系统结构图

其中网络通信模块与移动终端进行通讯，需要接收来自多个移动终端的定位

请求，并能将定位结果和位置应用等相关信息返回给相应的移动终端。

RSSI 位置指纹数据库模块在服务器启动之初，需要对离线阶段所采集的位置

指纹信息进行解析，结合实际环境中的建筑布局进行定位空间建模，将位置指纹

信息和定位环境相关联。并根据定位算法的要求，对数据库中的位置指纹进行滤

波处理，保证指纹信息的准确性，以提高定位系统的定位精度。

定位算法模块是整个系统中最核心的功能模块，对室内定位结果有着极大的

影响。由于目前有很多种基于位置指纹的定位算法，且各算法对系统要求各异，

因此在系统设计之初，应选择合适的设计模式和数据结构以保证能定位系统可以

兼容多种定位算法，为以后的系统拓展和改进提供必要的基础。

3.1.2终端程序

终端程序主要由以下功能模块组成：RSSI 测量模块、UI 界面和网络通信模块，其结构如图3-1-2所示。

图3-1-2终端系统功能结构图

网络通信模块与服务器端通信模块为通信对等实体，不再详述。

RSSI 测量模块使用无线网卡底层驱动，读取接收自各个AP 的 Beacons 帧信息，得到所需要的 RSSI 信息，并将位置指纹与位置信息相关联。

位置信息显示模块即为 UI 界面，由于终端界面需要使用在离线阶段和定位阶段，并且两个阶段的功能作用不同，因此需要有两种 UI 界面。一种为系统维护人员所使用的位置信息采集界面，需要输入位置信息，并可设置时间间隔在某一参考点处连续采集一组 RSSI 数据；
另一种为用户使用的定位查询界面，将由服务器返回的位置信息显示在 UI 界面中。

4 WiFi定位系统的设计与实现

定位系统的服务流程如图4所示。

(1)离线训练阶段，在定位区域使用移动终端测量收集各个AP的 RSSI 信息，并将RSSI信息存储在位置指纹数据库中供服务器程序进行定位使用。

(2)在线定位阶段，启动定位服务器中的程序，完成系统初始化工作，并做好监听定位请求的准备。

(3)开启移动终端上的终端程序，根据 Wi Fi 网络初始化通信网络，关联通信AP，

图4定位系统服务流程图

并读取配置文件进行UI界面初始化。

(4)移动终端扫描无线信号，将对应AP的MAC和RSSI列表发送给定位服务器。

(5)服务器程序接收到用户的定位请求后，使用指定的位置匹配算法计算出用户

的当前位置，并结合当前位置的其他应用信息，一同返回给移动终端。

(6)终端程序收到服务器程序返回的位置结果后，将用户位置显示在地图显示模

块中，为用户提供直观的显示效果。

4.1硬件平台

4.1.1无线AP

系统中使用的无线 AP 是Linksys WRT54G，有很多种开源无线路由固件都支持此款 AP，如 Tomato Dual WAN，DD-WRT，Way OS和Open WRT，因此，可以提供给用户多于默认固件的功能，有助于提升用户的使用感受。WRT54GZ 的详细配置参数如表4-1-1示。

表4-1-1WRT54G参数

4.1.2移动终端

在本系统中采用的移动终端是Lenovo的LePad A1，这是一款基于android系统的平板电脑，其中CPU主频1GHz，并拥有7英寸,1024*600的大屏幕，A1的

详细配置参数如表4-1-2所示：

表4-1-2 LePad参数

4.2服务器系统

服务器系统的功能结构主要包括网络通信模块、定位算法模块和RSSI指纹数据库模块，服务器系统的逻辑关系如图4-2所示，箭头方向代表数据流向。服务器程序在VS2010下实现，各个功能模块在同一主机中，后期可以考虑将服务程序和数据库分离在不同的机器中。

图4-2服务器系统逻辑图

4.2.1数据库模块

数据库模块中首要功能是保存位置指纹数据，需要对离线阶段所采集的位置指纹信息进行解析，结合实际环境中的建筑布局进行定位空间建模，将位置指纹信息和定位环境相关联。本系统将定位区域划分成大小为 1*1m的栅格，定位算法最终实际定位目标为栅格的标号，因此，即使定位在同一标号的栅格中，也存在由于栅格划分而产生的定位误差，即位置指纹识别法的定位精度存在理论下限。所以，需要根据实际定位范围和训练阶段的采样间隔距离来决定栅格大小的划分。RSSI数据库的定义如表 4-2-1所示。

表4-2-1RSSI数据库表

4.2.2定位算法模块

定位算法模块是整个定位系统的核心模块，模块的运行由位置查询报文的到

达事件触发，定位匹配流程如图4-2-2所示。

图4-2-2-1匹配算法流程图

本定位系统所在的定位区域大小在500平方米左右，定位区域将被划分500多个栅格标号，因此建立以栅格标号为键值的静态数组作为主数据索引，并将属于同一个标号的所有指纹数据串联起来，方便匹配算法使用，因为每个位置指纹包含的 AP 可能不同，使用MAC为键和RSSI为值组成键值对保存在结构map中。定位匹配算法的指纹数据组织结构如图4-2-2-2所示。由于本系统所采用的基础匹配算法为基于概率性的朴素贝叶斯法，在位置匹配过程中，每个栅格位置都会计算出相应的后验匹配概率，根据前文所提出的联合定位方法，初定位阶段需要保存 M 个概率最高的栅格标号，因此，匹配模块采用大小为M 的最小堆保存栅格标号与其相对应的概率，以便联合定位阶段不需要重新计算系统布置AP的RSSI 的匹配概率，降低匹配算法的时间复杂度。

图4-2-2-2数据组织结构图

4.2.3通信模块

定位系统的基础设施是Wi Fi无线网络，因为局域网中通信过程中的丢包率很低，而且系统的主要服务是定位服务，定位阶段正常的数据交互仅进行一次往返通信过程即可完成服务，因此，本系统在传输层采用无连接的UDP协议作为传输层协议，考虑到少概率丢包情况，在应用层增加重传机制，当终端发送定位请求之后，如果1s之后没有收到回复，则重传上次的报文请求。本小节将详细说明终端系统与服务器系统之间的通信协议格式。

应用层的通信协议采用扩展方便的 TLV(Type-Length-Value)协议格式。其中，Type域是signed short 类型，长度为 2个字节；
Length 域是unsigned int类型，长度为4个字节；
Value域是可变长度，其中存储应用层载荷数据。以下为通信功能中的几种典型应用分析数据包的类型，包括：定位请求、位置响应和RSSI指纹更新。

定位请求的数据定义如表4-2-3-1和表4-2-3-2所示：

表4-2-3-1定位请求格式

表4-2-3-2定位请求载荷数据格式

位置响应的数据定义如表4-2-3-3和表4-2-3-4所示：

表4-2-3-3位置响应格式

表4-2-3-4位置响应载荷数据格式

RSSI 指纹更新的数据定义如表4-2-3-5和4-2-3-6所示：

表4-2-3-5 RSSI指纹更新格式

表4-2-3-6 定位请求载荷数据格式

4.3终端系统

终端系统的功能结构主要包括RSSI测量模块UI界面及终端通信模块三个子模块，终端系统的逻辑关系如图4-3所示，箭头方向代表数据流向。

图4-3终端系统逻辑图

终端系统在平板电脑Le Pad中实现，操作系统为Android，开发软件使用Eclipse。现如今基于Android系统的手持终端的数量急速增长，并且由于手持终端体积小巧，便于携带，相比于笔记本电脑，更能满足用户对于实时定位的要求。Android 系统提供丰富的类库和控件，便于开发者使用，大大提高了软件的开发效率，缩短了项目开发周期，使开发者可以把更多的时间花费在业务逻辑中。因此，本系统采用 Android平台作为开发环境，有助于不同终端接入使用本定位系统，提高本定位系统的实用性。

4.3.1RSSI测量模块

RSSI测量模块的功能是测量终端所能扫描到的所有AP的RSSI值，RSSI 测量模块的工作流程如图4-3-1所示。

Google公司发布的基于Android 操作系统进行应用软件开发的开源SDK工具包，包含了功能丰富的WiFi Manager类库，不仅可以使应程序方便地实现Wi Fi连接，而且其中封装好的Wi Fi 扫描函数可轻松扫描设备通信范围内的AP 热点，同时可显示接入点的SSID、MAC地址、IP 和经量化处理的RSSI。Wi Fi Manager提供了一个面向底层硬件驱动程序的抽象接口，使上层应用软件不必知道下层硬件的具体实现方式，直接从驱动程序所更新的参数数据中得到各个AP的RSSI信息。程序中主要使用了该类的两个方法startScan和getScanResults。

图4-3-1 RSSI测量模块流程图

4.3.2UI界面

UI界面的主要功能是显示地图信息，并与用户进行交互，如图4-3-2所示为离线训练阶段所用的UI界面。其中界面主题显示为本系统所在的定位区域，定位区域以实验室120B左下角作为起始坐标(0，0)的参考点的二维相对坐标，横向为

X 轴，纵向为 Y 轴，坐标轴单位为 cm。因为平板电脑带有触摸屏，所以可以直接触摸用户所在位置，由程序计算得出离线阶段的相对坐标，便于训练阶段使用。由于训练阶段的位置指纹数据的准确性会对定位系统的定位精度产生巨大的

影响，因此增加以每个房间的左下角为参考点的局部相对坐标系。训练阶段使用

激光测距仪测量出局部相对坐标，填入文本框中，由程序算出全局相对坐标。UI界面中左上角区域显示位置坐标，第一列为室内相对局部相对坐标，第二列为全局相对坐标。如图4-3-2所示，实验室 125 中的红点的位置即为用户位置，局部相对坐标为(200,300)，全局相对坐标为(1201cm，1392)。定位阶段所用的

UI界面与训练阶段的相似，只是位置坐标由定位服务器返回所得，所以此节不再做描述。

图4-3-2 UI界面

4.3.3终端通信程序

终端通信模块的主要功能是接收和发送通信数据，终端通信程序由RSSI测量模块触发。终端通信模块的工作流程图如图4-3-3所示，具体通信协议前文已经进行介绍。

图4-3-3 终端系统通信流程图

5实验平台5.1软件环境

在研究射频无线信号的空间传播特性之前，首要任务是使用终端在指定位置测量实时 RSSI。本节将介绍后续实验中所用到的Wi Fi 网络实验环境，以及测量射频无线信号等相关信息的方法。

由前文的介绍可知，WiFi无线局域网中的终端通过与AP 接入点通过通信连接进行信息交互。在某时刻，如果不指定 AP 接入点的SSID，无线网卡将以附近AP 接入点的信号强度为标准，选取信号强度最高的AP建立连接请求。同终端与AP 进行关联从而通信的方式不同，定位系统需要终端探测感知所在区域内所有AP 接入点的信号强度。在 IEEE802.11 协议中，终端可以使用两种方式获取各个AP 的 RSSI 信息，即被动扫描(Passive Scanning)模式和主动扫描(Active Scanning)模式。

被动扫描模式的优点是可以降低功耗，但由于 AP 接入点可以被设置为不发送Beacons 帧，终端可能无法获得所有AP接入点的RSSI 信息，所以本文选择使用主动扫描模式实现RSSI 的获取功能。在主动扫描过程如图5-1所示，终端将扫描所有的802.11信道，在每个信道中，终端将以广播的方式发送 Probe Request帧，当AP收到此广播帧后，就会选择合适的时序发送Probe Response

帧。随着终端接收到工作在各个信道上的AP返回的Probe Response帧，主动扫描过程结束，终端将会获取到所有可以观察到的AP列表，其中包括定位所需要的各个AP的MA地址和RSSI信息。

图5-1 802.11协议中的主动扫描过程

目前虽然有很多种网络嗅探工具可以收集Wi Fi局域网中的各个AP的RSSI，如Net Stumbler，但此工具只支持windows平台，并且不可以得到开源代码。为了提高训练阶段的效率，更符合系统实际的定位需求，本文采用较为轻薄的平板电脑LePad作为终端，并在此终端上开发了RSSI采集程序。

5.2实验场景

5.2.1AP的搭建

本文的实验地点是电子科技大学清水河校区科研B座，由实验室B120~B127以及走廊所组成的区域，即图5-2-1中虚线所包围的区域，总面积为

17m*34m，整个区域已经被 Wi Fi 无线局域网覆盖，其中5个AP 接入点是为定位系统所布置，AP1部署在实验室125的(10m，5m)位置，AP2部署在实验室127 的(10m，5m)位置，AP3部署在实验室125A 的(3.5m，6m)位置，AP4部署在实验室122B 的(1m，6m)位置，AP5部署在实验室120B 的(3m，6m)位置，同时实验区域还可以搜索到其它8个无线 AP 接入点。本系统训练阶的主要工作为采集 RSSI 训练数据，建立位置指纹数据库，在整个实验场景中以1m 为采样间隔，一共在271个位置参考点进行数据采样，每个训练点连续采集一定数量的位置指纹，训练阶段共花费两个工作日的时间。

图5-2-1 实验场景图

5.2.2RSSI的测量

5.2.2.1RSSI的与位置的关系

从实验环境中的走廊最左侧处开始，每隔1 米进行一次采样，沿直线向右方向移动，如图 5-2-2-1 所示接收自两个 AP 的 RSSI，它们分别是左侧的 AP5和右侧的 AP2，其中 X 轴为与走廊最左侧的距离。可以看出，当终端越靠近 AP 时，网卡所接收到的RSSI值越强，但由于其它干扰因素，相邻的采样点间的RSSI可能会发生波动。

图5-2-2-1眼走廊行走时的RSSI情况

5.2.2.2RSSI的概率分布

在实际环境中200多个采样点所采集的位置指纹数据，它们的正规化直方图都符合或近似符合正态分布，实际测量值在一个稳定值附近变动，是一个取决于均值的正态随机变量。

图5-2-2-2 概率分布直方图

如图5-2-2-2所示，虽然信号强度的概率分布符合正态分布，但有很严重的拖尾现象。和室内环境中的家具、墙壁、电器设备及门窗位置等固定的干扰源不同，人员是位置时常改变的干扰因素，由于802.11的通信频率为2.4GHz，而人体内水分子所占的比例超过70%，其共振频率同样是2.4GHz，所以人体是干扰射频无线信号传播的一个重要因素。而且由于不同的时间段内，人员的密集程度和流动程度都有很大的区别，因此，有必要选取合适的时间进行离线训练阶段的位置指纹数据库采集工作。

5.2.2.3RSSI的收敛速度

位置指纹是否可以正确反映信号强度的实际情况将极大地影响定位阶段位置估计的可信性。构建位置指纹数据库需要保存大量的位置指纹，尤其是使用概率性定位算法的定位系统，为了得到比平均值更多的信号分布信息，需要在每个位置点采集一定数量的瞬时RSSI样本，用以得到在此位置点的RSSI的概率分布情况。显然在同一参考点采集的RSSI样本值越多，获得关于信号分布的信息越详细准确，但是在系统训练阶段将会花费更多的训练时间。为了得到可信的信号强度概率分布情况，需要在位置指纹的完整性和训练时间成本之间找到一个平衡点。

为了研究信号强度均值的收敛情况，本文连续采集5分钟的样本数据，采样点距离AP3为5米，与AP4中间相隔两堵墙距离5米，与AP2中间相隔一堵墙距离15米。随着时间的推移，计算了不同时间点的信号强度的平均值，结果如图 3-5所示。可以看出，所有 AP 的RSSI都满足一个趋势，即平均值经过一段时间的波动后，RSSI的均值趋于稳定。信号的平均强度在30秒时都已经趋于稳定，因此，本系统在训练阶段的每个位置点的采样时间为30秒，采样频率为每秒钟1个样本。

图5-2-2-3 RSSI平均值的变化趋势

6性能评估

对于定位系统而言，最重要的衡量指标就是系统的定位精度，定位精度可以从定位的准确性和精确性两个方面进行对比，本文采用以下的各项指标来衡量定位系统的性能。

●平均均方根定位误差

本文采用平均均方根定位误差(Average Root Mean Square Error ,ARMSE)作为评估定位算法准确性的参数指标，该指标从评价定位误差的角度衡量了定位系统的定位精度，其具体定义为：

（6-1）

●误差累积分布函数

本文采用误差累积分布函数(Cumulated Denstiy Function，CDF)作为定位算法精确性的衡量指标，通过大量的定位测试，从定位误差概率分布的角度衡量了系统的稳定性，其具体定义如式(6-2)其中，表示定位误差小于 x 的概率。

（6-2）

●最大定位误差

本文采用最大定位误差作为衡量定位系统稳定性和鲁棒性的指标，其定义为定位系统所有测试后的最大误差，其表达式为：

（6-3）

7定位精度测试

定位性能测试时间是在训练阶段的一周之后，但是在相同的WiFi 无线网络环境中进行。如图7-1定位误差的累积分布函数，其中X轴为定位误差的距离，Y轴为定位误差所对应的概率。

如表7-1 ，对定位结果分析得知，基础型定位误差比较大的位置点大都分布在实验场景的边缘地带，由于边缘地带能搜索到的系统布置AP的数量要小于中心区域。因此，更能证明联合定位算法可以提高系统的鲁棒性，可以降低定位系统对系统布置AP的覆盖范围和分布问题的要求，从侧面解决了定位系统因不同环境布置AP差异较大，理论依据不充足的问题。

图7-1误差累积分布函数

表7-2基本型定位的定位精度

8设计总结

本文以基于WiFi无线网络和位置指纹的定位技术为研究对象，系统的阐述了此类室内定位技术的发展现状、特点和研究意义，最后，设计、开发了一个以实际应用为目的的基于位置指纹的WiFi室内定位系统原型。

通过实际WiFi 环境中采样所得的RSSI位置指纹数据，从室内定位的角度分析了射频信号在室内的传播特性与距离、外界干扰等的关系，为定位算法的设计与定位系统的部署提供了一定的理论依据。

设计并实现了一个基于位置指纹的WiFi 室内定位系统原型，并在实际的 WiFi无线局域网环境里对本文所提出的方法进行了实验验证。

定位系统边缘定位能力不足，应该以迭代的思想，利用定位环境中已有的非定位系统布置的 AP 接入点进行联合辅助定位，进一步提高原有系统的定位精度和定位鲁棒性，降低对 AP 布置的要求。

9工作展望

指纹数据库的建立：指纹数据库的构建需要花费大量的人力成本与时间成本，并且一旦室内布局或者建筑结构发生变化，之前所构建的指纹数据库将不再适用，因而无法提供有效的定位服务，必须重新构建指纹数据库，因此可以针对此方面展开一定的研究。

本文所研究的定位技术只针对静态定位，并未考虑动态定位的相关问题。但正

如GPS所提供的室外导航服务已经成为人们出行必不可少的基础类服务，室内导

航也存在巨大的市场需求，因此可以针对动态定位展开研究，从而将单纯的定位

服务扩展成为导航服务。
参考文献

第2篇: 基于WiFi三角定位原理的语音寻物探测方法研究

第３１卷第１期　
文章编号：１００６—９３４８（２０１４）０ｌ一０２８６—０４　
计算机仿真　２０１４年１月　
基于贪婪思想的气体泄漏源探测与定位研究　
毕瑛炜　，谷源涛　
（１．清华大学电子工程系，北京１０００８４；
２．总后勤部军事交通运输研究所，天津３００１６１）　
摘要：快速准确地探测和定位有毒气体泄漏源，对保障人民群众的生命和财产安全、制定应急方案有重要的意义。为明确探　
测定位，将无线传感器网络应用于有害气体监测，综合使用假设检验法和卡尔曼滤波方法同时完成泄漏源的探测与定位。　但传统算法随着泄露源个数增加，可能的位置和时间组合的数量呈指数增长，严重影响计算可行性。针对上述问题，利用传　感器的测量残差，根据贪婪思想对潜在源进行逐一探测，保证“假设”数量的增长与源的个数呈线性关系，并最终完成对所有　源的探测与定位。仿真结果表明，所提算法在保证低复杂度的前提下，实现了多个气体泄漏源的探测与定位，并准确地估计　出泄漏时间和强度信息，为解决有毒气体泄露的探测问题提供了可行的参考方案。　
关键词：探测；
定位；
气体泄漏源；
无线传感器网络；
贪婪算法　
中图分类号：ＴＰ３９１．９　
文献标识码：Ａ　
Ｓｔｕｄｙ　ｏｎ　Ｇａｓ　Ｌｅａｋ　Ｓｏｕｒｃｅ　Ｄｅｔｅｃｔｉｏｎ　ａｎｄ　Ｌｏｃａｌｉｚａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｇｒｅｅｄｙ　Ａｐｐｒｏａｃｈ　
ＢＩ　Ｙｉｎｇ—ｗｅｉ　．ＧＵ　Ｙｕａｎ—ｔａｏ　
（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ；
　
２．Ｔｈｅ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｍｉｌｉｔａｒｙ　Ｔｒａｎｓｐｏ￣ａｔｉｏｎ，Ｔｉａｎｊｉｎ　３００１６１，Ｃｈｉｎａ）　
ＡＢＳＴＲＡＣＴ：Ｑｕｉｃｋ　ｄｅｔｅｃｔｉｏｎ　ａｎｄ　ａｃｃｕｒａｔｅ　ｌｏｃａｌｉｚａｔｉｏｎ　ｏｆ　ｇａｓ　ｌｅａｋ　ｓｏｕｒｃｅ　ａｒｅ　ｃｒｕｃｉａｌ　ｆｏｒ　ｅｍｅｒｇｅｎｃｙ　ｒｅｓｐｏｎｓｅｓ，ｐｒｅ－　
ｄｉｃｔｉｎｇ　ｄｉｓｐｅｒｓｉｏｎ，ａｎｄ　ｅｖａｃｕａｔｉｎｇ　ｐｅｏｐｌｅ　ｆｒｏｍ　ａｆｆｅｃｔｅｄ　ａｒｅａｓ．Ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｍｏｎｉｔｏｒｉｎｇ　ｔｈｅ　ｇａｓ　ｌｅａｋ　ｓｏｕｒｃｅｓ　ｗａｓ　
ｓｔｕｄｉｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｕｓｉｎｇ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．Ｗｅ　ｐｒｏｐｏｓｅｄ　ａ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｄｅｔｅｃｔ　ａｎｄ　ｌｏｃａｌｉｚｅ　ｍｕｌｔｉｐｌｅ　ｓｏｕｒｃｅｓ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ　ｂａｓｅｄ　ｏｎ　Ｋａｌｍａｎ　ｆｉｌｔｅｒ　ａｎｄ　ｈｙｐｏｔｈｅｓｉｓ　ｔｅｓｔｉｎｇ．Ｔｏ　ｄｅｃｒｅａｓｅ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　
ｔｒａｄｉｔｉｏｎａｌ　ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ　ｒｉｓｅｓ　ｅｘｐｏｎｅｎｔｉａｌｌｙ　ｗｉｔｈ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｓｏｕｒｃｅ　ｉｎｃｒｅａｓｅｓ，ｗｅ　ｕｓｅｄ　ｇｒｅｅｄｙ　ａｐｐｒｏａｃｈ　ｔｏ　ｉｔｅｒ—　
ａｔｉｖｅｌｙ　ｄｅｔｅｃｔ　ｐｏｔｅｎｔｉａｌ　ｓｏｕｒｃｅｓ　ｏｎｅ　ｂｙ　ｏｎｅ　ｕｔｉｌｉｚｉｎｇ　ｔｈｅ　ｍｅａｓｕｒｅｍｅｎｔ　ｒｅｓｉｄｕａｌｓ　ｏｆ　ｓｅｎｓｏｒｓ．Ｓｉｍｕｌａｔｉｏｎｓ　ｖｅｒｉｆｙ　ｔｈｅ　ｐｅｒ－　
ｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｓｕｇｇｅｓｔ　ｉｔ　ｃａｎ　ｂｅ　ａ　ｆｅａｓｉｂｌｅ　ｒｅｆｅｒｅｎｃｅ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｇａｓ　ｌｅａｋ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｐｒａｃｔｉ—　
ｃａｌ　ｓｃｅｎａｒｉｏｓ．　
ＫＥＹＷＯＲＤＳ：Ｄｅｔｅｃｔｉｏｎ；
Ｌｏｃａｌｉｚａｔｉｏｎ；
Ｇａｓ　ｌｅａｋ　ｓｏｕｒｃｅ；
Ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ（ＷＳＮ）；
Ｇｒｅｅｄｙ　ａｐｐｒｏａｃｈ　
１　引言　
发生有毒气体泄漏事故后，快速准确地判定泄漏源的位　
决了二维平面内无风条件下对已知泄漏时间的化学物质烟　
羽的定位问题。文献［３］在已知风速和风向的前提下，采用　多假设追踪，配合定制的预测器完成了烟羽的探测与追踪。　文献［４］首先讨论了气体扩散模型，然后分别采用广义似然　比检测和最大似然估计实现了移动源的探测与定位。文献　
置、强度和泄漏时问等信息具有重要意义。利用泄漏源的相　关信息，可以估算有毒气体的扩散和影响范围，为制定疏散　方案、选择避难场所和处理有毒物品提供重要依据。由于泄　漏事件具有突发性和不可预测性，只能在事件发生后通过特　定的传感器测量环境中的有毒气体浓度，并结合扩散模型估　计泄漏源的相关信息。　
近年来，随着有毒气体泄漏带来的安全问题引起广泛关　
［５］基于假设检验架构，提出了一种同时实现单源探测与定　
位的方法，并证明该方法只需较少的传感器即可实现。然而　对多源并存情况，如果简单地将假设检验方法应用于所有可　能的源组合，将造成“假设”数量随源数量呈指数增长，不具　有计算上的可行性。本文基于贪婪思想，在假设检验的基础　上，通过对源的逐一探测，将“假设”数量与源数量的关系控　制在线性范围，最终为解决多源的探测与定位问题提供了可　
注，相关研究也逐渐增多，包括泄漏源的快速探测、位置和强　度估计等…。文献［２］利用集合卡尔曼滤波求解逆问题，解　
收稿日期：２０１３—０４—０１　
－－－－—
—
行的解决方案。仿真结果表明，本文提出的算法可以实现多　
２８６．－—・——　

源的快速探测和定位，并准确估计泄漏时间和强度。　
本文首先描述了采用无线传感器网络进行多气体泄漏　源探测和定位的问题；
随后详细介绍了利用假设检验法实现　探测与定位算法的数学框架，并提出基于贪婪思想的探测机　
残差，触发新的探测过程，对潜在的源进行逐一探测。下面　
分别介绍残差计算方法、假设检验法和基于贪婪思想的探测　定位算法的实现过程。　３．１　泄漏源的残差计算方法　
制和残差更新技术；
最后通过仿真对所提算法进行性能验　
证。　
２问题描述　
本文主要讨论利用传感器网络采集的气体浓度数据，结　合气体扩散模型和风速等环境信息，解决有害气体泄露的监　测问题。为便于分析讨论，本文仅考虑二维平面内的平流扩　散情况，并采用文献［６］中的高斯烟团模型。根据模型可　知，（　，　）处在Ａｔ＝ｔ—ｔ。时刻的气体浓度值为：　
ｒ　
（　ｘ０　
ｔ）０（ｙ一　一“　）０　
ｃ（　，　，Ａｔ）＝——　ｅ一—面　一一—　
（１）　
４￣ｒＡｔ￣／Ｄ　Ｄｙ　
其中（‰，Ｙｏ）为气体源位置，ｔ。表示泄漏时间，Ｃ。表示瞬　
时泄漏强度，Ｕ　和“　分别表示　和ｙ：Ｙ向的风速分量，可以通　过风速传感器阵列获得。Ｄ　和Ｄ　分别表示　和ｙ方向的扩　散系数。　
监测区域被均匀划分为Ⅳ个网格，其中部分网格内放置　
传感器节点，用于测量有害气体浓度。有毒气体的扩散过程　可采用如下系统方程描述　：　
，　
ｘ（ｔ＋１）＝Ａ（　＋１，ｔ；
ｕ）ｘ（ｔ）＋　（　）＋　
６　。　（　，竹）　
Ｊ＝１　
’　
Ｙ（ｔ）＝Ｃ（ｔ）　（ｔ）＋　（ｔ）　
（２）　
其中　（ｔ）∈豫　定义为ｔ时刻Ⅳ个网格的浓度状态向　量；
Ａ（ｔ＋１，ｔ；
ｕ）表示与风速“＝（ｕ　，ｕ　）和扩散系数有关的　状态转移矩阵；
　和　分别表示互相独立的系统噪声和测量　噪声序列，服从均值为０方差矩阵分别为Ｑ和Ｒ的高斯分布；
　（ｔ）Ｅ　
表示ｓ个传感器节点的测量值；
Ｃ（ｔ）∈　为０　
—
１矩阵，其各行中与传感器节点位置对应的元素值为１；
　
６　（ｔ，　）表示哆时刻在第ｚｏ　个网格内发生强度为　的　
瞬时泄漏，注意本文采用冲激函数组合来描述．，个潜在的气　
体泄漏源，这里假设源的泄漏模式为瞬时泄漏。　
根据系统方程（２）可知，气体泄漏扩散的浓度响应与状　
态向量　（ｔ）对应，因此可以利用假设检验法，通过观测一段　时间内传感器节点的测量值ｙ（ｔ），同时解决源的探测与定位　问题。　
３　探测与定位　
若监测区域内存在‘，个源，每个源可能出现的位置为Ⅳ　个，那么可能的“假设”数量为ｃ　一０（ＮＪ），当Ⅳ和．，较大　时，传统假设检验法中的“假设”数量过大，探测和定位算法　将难以在多项式时间内完成。本文在文献［５］的基础上，基　
于贪婪思想，每次迭代假设区域内仅存在单个源，利用假设　检验法对其进行探测与定位，然后根据源的信息估计值更新　
根据系统方程（２），可以利用卡尔曼滤波对浓度状态向　量　（ｔ）进行预测，得到如下的预测和更新方程：　
；
（ｔ　Ｉ　ｔ）＝互（ｔ　Ｊ　ｔ一１）＋Ｋ（ｔ）　（ｔ）　未（ｔ＋１　Ｉ　ｔ）＝Ａ（ｔ＋１，ｔ；
ｕ）　（ｔ　　１ｔ）　
（３）　
利用传感器节点的测量值和状态的预测值得到残差　
（ｔ）＝Ｙ（ｔ）一Ｃ（ｔ）　（ｔ　Ｉ　ｔ一１），其方差满足　
Ｖ（ｔ）＝Ｃ（ｔ）Ｐ（ｔ　Ｉ　ｔ一１）Ｃ　（ｔ）＋Ｒ（ｔ）　
（４）　
其中Ｋ（ｔ）表示卡尔曼滤波增益，Ｐ（ｔＩ　ｔ一１）表示预测误　
差协方差矩阵，二者可通过式（５）计算得到：　
Ｋ（　）＝Ｐ（　Ｉ　一１）Ｃ　（ｆ）　
）　
ｆ５）　
Ｐ（ｔ＋１　ｌ　ｔ）＝Ａ（ｔ＋１，ｔ；
“）Ｐ（ｔ　ｌ　ｔ）Ａ　（ｔ；
Ｍ）＋Ｑ（ｔ）　
根据系统的线性性质，将状态估计值和残差分解成两部　分：　
）＝　
　１
）＋　Ｉ　）　
（６）　
（ｔ）＝７０（ｔ）　７Ｒ（ｔ）　
其中，下标…０’部分表示无任何气体泄漏时ｔ时刻的浓　度和残差分量；
“尺”部分表示仅由气体泄露扩散至ｔ时刻产　生的效应，可以通过计算直接得到：　
Ｊ　
（　Ｉ　）＝∑Ｆ（　；
竹）　６　，（　，　）　
１　
ｉ　
（７）　
（　）＝∑ｙｊ（ｔ）＝∑Ｇ（　；
竹）　６　（　，　）　
其中Ｆ（　；
　）和Ｇ（ｔ；
　，）当且仅当ｔ≥　，时非零，并　且满足　
Ｆ（　；
竹）＝∑＠（　；
　）Ｋ（　）Ｃ（ｋ）Ａ（ｋ，竹；
　）　
ｑ　
Ｇ（ｔ；
　，）＝Ｃ（ｔ）［Ａ（ｔ，　，；
Ｍ）一Ａ（ｔ，ｔ一１；
ｕ）Ｆ（ｔ一１；
　，）］　
（８）　
这里　（　；
　）同样在　≥　时非零且满足　
（ｔ；
　）＝［，一Ｋ（ｔ）Ｃ（ｔ）］Ａ（ｔ，ｔ一１；
Ｍ）＠（ｔ一１；
　）　（　，；
　）＝，　
（９）　
其中　（ｔ）表示第　个泄漏源ｔ时刻对残差的贡献值，在　
已知源的位置、泄漏时间和强度的情况下，可以根据式（７）　
计算得到。请注意：上述迭代步骤中的矩阵Ｆ、Ｇ以及＠适用　
于所有的　，仅需计算一次即可。　３．２　多源的假设检验　
为描述多源问题，本文构造新的二元假设，用　表示对　
第　个源的假设，而　为无源泄漏的假设。二者的定义如　
下：　
：ｙ（ｔ）＝ｙｏ（ｔ）　
：　
（ｔ）＝ＲＪ（ｚ）　（ｔ）　
（１０）　
２８７．．．——　

其中，Ｒｊ（ｔ）＝∑ｙｉ（ｔ）表示第　个源和所有未探测到的源对　
残差贡献的总和。　
增加源计数：　＝　＋１；
　
７）ｔ＝ｔ＋１，如果ｔ小于终止时间，转到步骤２）。　实际泄漏扩散过程中，一定时间后泄漏源的影响会逐渐　
假设检验法，首先对不同位置和不同时间出现的单位强　
度泄漏源进行假设，再根据式（７）计算相应的残差，然后计　
减弱甚至消失。因此，在步骤２）中，采用滑动时间窗口肘来　减少不必要的假设似然值的计算与存储。也就是说，在ｔ时　刻仅考虑利用［ｔ—Ｍ＋１，ｔ］内的假设似然值。因此，在基于　算其本身的归一化能量以及其与实际残差　（ｔ）之间的归一　
化相关性，二者的表达式如下：　
。（ｆ；
竹，ｆ０ｃｊ）＝∑ｆｒ％Ｇ　（．ｉ｝；
竹）Ｖ－ｌ（ｊ｝）Ｇ（｜ｊ｝；
竹）　
（１１）　
ｂ（ｔ；
￣ｏｊ，Ｚｏｃｊ）＝∑
Ｇ　（％；
竹）Ｖ－Ｉ（　）’，（　）　
其中　
∈　
，对应２ｏｃ　位置为１，其余位置为０。此时，　
可以计算得到假设　与风的似然比ｚ，（ｔ；
ｑ￣ｊ，ｆｏｃ，）＝　
，
找到似然比的最大值　（　；
　，ｚ　）　
ｍａｘ
ａ　ｔ　；
　，，　ＬＯＣｉ　Ｊ　
／　．（
ｆ；
　即
，，，ｌｏｃ　　，
竹，ｚ。　），根据检验法则　（￡；
　，ｚ　）囊ｖｌ，判断是否发生气体　源泄露。若最大似然值超过门限叼，认为探测到第　个源，　
（　）和ｌｏｃｉ（ｆ）分别是泄漏时间与位置的估计值，＆　（ｔ）＝　
笺丢　
是间接获得的强度估计值；
反之，认为未　发生源泄露。　
３．３　贪婪思想的探测与定位算法　
本文所提算法基于贪婪思想，每次迭代均假设区域内仅　存在一个源，通过３．１和３．２节所述方法找出与当前时刻残　差相关性最大的源，并利用传感器测量值估计源的泄漏时　
间、位置和强度信息，然后计算并消除该源对残差的贡献。　
随后触发新的探测过程，对区域内其它潜在源采用同样方法　进行逐一探测。本文算法的具体过程如下：　
基于贪婪思想的多源探测与定位算法如下：　
１）初始化残差Ｒ０（ｔ）：Ｙ（ｔ）一Ｃ（ｔ）ｘ（ｔ　ｌ　ｔ一１），泄漏源　
集合Ａ。（ｔ）＝　。设置源计数　＝１，初始时间ｔ＝１；
　
２）对　＝１，２，…，ｔ和ｌｏｃｊ＝ｌ，２，・・・，Ⅳ分别计算：　
；
竹，ｌｏｃｊ）＝　
；
　
３）找到　和ｆ　ｃ，，使得　
；
竹，如）垒　
（　；
竹，ｌｏｃ？；
　
４）比较？Ｊ（　；
　，，ｌｏｑ）与　大小，如果小于，７，转到步骤　
７），否则继续；
　
５）计算强度的估计值和第，个源对残差的贡献：　
）＝　
，　
（ｔ）＝Ｇ（ｔ；
竹（ｔ））　（ｆ）占　）（ｔ，竹（ｔ））；
　
６）更新：　
增加源集合：　
（ｔ）＝　一－（　）ｕ｛　（￡），ｌｏｃｊ（￡），＆，（　）），　
更新残差：Ｒｆ（ｔ）＝ＲＨ（ｔ）一ｙｆ（ｔ），　
．
．．—
—
２８８．－－——　
贪婪思想的算法中，每个源的“假设”数为ＭＮ。总体来说，　本算法将“假设”数从０（　
）的指数关系降为０（ＭＮＪ）的　
线性关系，有效地避免了计算和存储复杂度随源的个数迅速　增长的趋势，提高了算法的可行性。　
４仿真及分析　
本部分通过ＭＡＴＬＡＢ仿真验证所提算法并分析其探测　与定位性能。仿真区域大小设为２５ｘ２５，其中均匀布设了Ｎ　
＝
１４４个传感器节点。假设测量值为节点所在网格内的平均　
浓度，测量噪声标准差为１００。区域内存在源１、源２和源３　三个泄漏源，如图１所示，坐标位置（Ｘ，Ｙ）分别为（５，１５），　（１１，１１）和（１５，１５），网格序号与坐标的关系为：ｌｏｃ＝（Ｘ—１）　ｘ２５＋ｙ。假没ｔ＝２时刻，源１发生强度为１×ｌ０　的泄漏，随后　
ｔ＝４时刻源２与源３同时泄漏，强度分别为０．８×ｌ０　和０．６ｘ　
１０　。风速ｘ分量为１，Ｙ分量为０，扩散系数Ｄ　和Ｄ　均为０．　
５，系统噪声标准差为１００。判决门限　选取为１３．５，滑动时　间窗口Ｍ取为１１。　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　
■　
■　强　
制　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　０　
—　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　
０　０　０　０　０　０　０　０　０　０　０　０　
５　１０　１５　２Ｏ　２５　
横坐标　
０表示传感器节点　
■表示气体泄漏源　
图１传感器节点部署与泄漏源分布情况　
图２展示了所提算法的探测性能。若“假设”值为真，表　示探测到泄漏源；
反之，则表示未探测到源。从图中可以看　出，ｔ＝３时刻，Ｈ　为真；
ｔ＝５时刻，Ｈ：和Ｈ３为真，说明本算法　
准确地探测到气体源的泄漏。但不难发现，本方法在源泄漏　的下一时刻才探测到源，这是因为气体扩散到传感器节点需　
要时间。若要减少探测的延迟时间，可以增加传感器节点部　
署密度。　