论文部分内容阅读
摘 要：通过对典型WLAN定位方法的研究与分析，本文设计并实现了一种基于位置指纹的WLAN室内定位系统。同时，将NNSS、KWNN和基于概率密度三个经典WLAN定位算法应用于该系统中，进行了实际测试和分析，结果表明，本文所实现的系统具有很好的可靠性和实用性。
关键词：WLAN；室内定位；RSSI；位置指纹
中图分类号：TN929.5
1 前言
基于位置的服务（LBS）越来越受到人们的关注，越来越多的定位直接利用现成的无线通讯模块来估计对象节点的位置，应运而生的WLAN定位技术以低成本、低功耗成为室内定位的主要方法之一。
2 基于WLAN的定位算法
基于WLAN的定位算法主要有到达角度定位（Angle 0f Arrival，AOA）、到达时间定位（Time Of Arrival，TOA）、信号强度分析法（Received Signal Strength，RSS）以及位置指纹定位法（Location Fingerprint）。AOA和TOA需要专门的设备支持，而且受非视距以及多径影响比较严重；RSS对信道传输模型的依赖性非常强，多径效应、墙壁的遮挡以及环境条件的变化都会使其精度严重恶化。采用位置指纹定位技术则可以有效地克服以上定位算法的缺点。基于位置指纹的定位方法主要包括两个阶段：（1）构建指纹图（Radio Map）；（2）定位阶段。
3 基于位置指纹的WLAN定位的实现方法
3.1 定位网络构建
基于位置指纹的WLAN系统的实现，首先需要搭建一个室内无线局域网环境，使每个可能出现移动用户的位置被三个或三个以上AP信号覆盖。在初始情况下，根据经验和推测将AP放置在适当位置，保持一定的发射功率，然后选取一些关键点进行测量，如果发现盲区，则调整AP的位置，或者提高AP的发射功率，再进一步测量，直至可能出现移动用户的位置没有盲区为止 。定位网络系统由多个AP、多个移动客户端和一个定位服务器组成。移动客户端通过网卡获取其到各个AP的RSSI，并发送到定位服务器进行处理。
3.2 RSSI采样
参照室内平面图选择适当的采样点，在各个采样点多次测量和记录相应AP的RSSI值，并根据采样数据分析环境的无线信道情况。由于实验是构建环境RadioMap，因此必须采集尽可能多的数据。这就要求从多角度、多方面在同一采样点测量多次。
3.3 计算RadioMap
RadioMap是元组（ap，x，y，s）的集合，其中ap是某个特定的AP，（x，y）是每个采样点的平面坐标，s是（x，y）处ap的RSSI特征量，它被用作定位匹配算法的参考，直接影响定位精度，因此要求其中必须包含尽可能多的元组，而这些元组可以通过经验值法全部采样得到，也可以通过数学模型计算得到。
3.4 定位阶段（OnLine阶段）
当建立完RadioMap后，就可以运用相应的定位匹配算法，把实时测量的RSSI特征值和RadioMap中的位置指纹进行比较，找出最佳匹配，获得最佳定位效果。
4 定位算法
目前，在位置指纹定位算法中，典型的定位算法包括最近邻算法NNSS、加权k近邻KWNN和基于概率密度的方法。
4.1 最邻近算法
NNSS（Nearest Neighors in Signal Space）有n个AP，m个采样点。直接把RSSI平均值作为上述位置指纹，计算测量点的RSSI值和采样点的RSSI值之间的欧几里得距离，即假定第i个采样点的对各AP信号强度元组为（si1，si2…sin）用户当前位置测量得到的信号强度为（s1，s2……sn）。则测量点和第i个采样点的RSSI欧几里得距离为disi，i从1到m中，取dis最小的值所对应的采样点的位置为测量点的估计值。
4.2 加权K邻近算法（KWNN）
需要注意选择恰当的k值。因为如果k选取太大，则会将离用户实际位置并不是很近的点也包括进来，反而降低了定位精度。首先求测量点RSSI和各个采样点RSSI间的欧几里得距离，再取出k个欧几里得距离最小时对应的k个位置，求出该k个位置坐标的平均值作为该测量点的位置：
但直接求k个坐标的平均值作为测量点位置并不是很合适，应该距离越近的位置权值越大。根据该理论权值计算方法如下：
上述公式中k和q为两个参数，本系统中q被设为2。由此得出测量点坐标估计值为：
4.3 基于概率密度的定位算法（ProbabilityMethod）
在该定位方法中，一个采样点1处的位置指纹是RSSI值在该采样点上对各个AP的联合的概率密度。由于各个AP独立，因此联合概率可由各AP的边缘概率求得：
上式中 表示在l处AP1的RSSI为S1、AP2的RSSI为S2...APn的RSSI为Sn的联合概率密度， 表示在i处APi的RSSI为Si发生的边缘概率密度。
假设AP的所有RSSI样本都属于区间[min，max]，其中min和max是RSSI样本的最小值和最大值。该区间被划分成k个子区间，k是一个可调参数，影响着对概率密度估计的准确性。为了简化问题，把k个子区间设为等宽，每个子区间宽度w为：
而子区间的样本数量n的计算方法如下：
如图1所示，Si、Si+1、...、Si+j+1、Si+j+2都为RSSI样本，子区间宽度为w，由w1、w2、w3三部分组成，w1、w3为小数部分，w2为整数部分。
用上述直方图法求可求出采样点对各个AP的边缘概率密度进而求出各采样点的联合概率密度。在算法实现中为避免概率为0，在用直方图估计概率密度前给每个值设为1/N。测量点估计坐标为： 5 基于WLAN的定位系统实现
本系统的定位数据处理过程中，客户端核心工作是获取RSSI和发送RSSI，而服务器端的核心工作是接收RSSI，通过分析RSSI数据，计算并且形成RadioMap，最后通过定位计算，将位置呈现给用户。
5.1 系统服务器端
系统服务器端划分成如下。
实时定位模块：用户可以选择定位算法，接收来自数据采集的OnLine数据并根据用户选择的定位算法进行定位计算，然后将计算出的位置结果呈现给用户。
数据采集模块：负责与客户端的服务器通信模块进行通信，从客户端接收并解析RSSI数据包，将OnLine数据分发到实时定位模块，OffLine存入RSSI数据库，以便数据分析模块进行分析。
数据分析模块：分析数据采集模块得到的OffLine数据，计算RadioMap并用图表形式向用户呈现结果。
设备管理模块：负责AP以及移动终端的管理。
系统配置模块：用户可以配置数据库，SuperMap服务器，以及数据此采集模块的通信端口等。
5.2 系统客户端
系统客户端分为如下四个模块。读取RSSI模块：负责从网卡中读取RSSI值；服务器通信模块：负责和服务器进行通信，发送RSSI数据，解析服务器的发给客户端的配置信息。配置信息将影响读取RSSI模块的采集行为；客户端配置模块：读取本地配置文件；本地存取RSSI模块：当服务器通信模块发送RSSI数据失败时，负责将发送失败的RSSI数据存入本地文件中，以便后期处理。
6 实验结果与分析
本系统构建的定位区域为750cm*780cm的室内环境，为减少复杂环境对定位效果的影响，把每次数据采集布置成一个任务，每个任务对应一个位置指纹。定位所采用的指纹库是在上述定位环境内的13个采样点的指纹组成，共6个待测位置进行了定位实验。每个采样点采样次数为100次，采样周期为300ms，每个待测位置采集定位数据500-600次共3400次。
用三种定位算法进行定位，当取K=5时，三种算法的误差比较如图2所示。
从图中可以看出：基于概率密度的误差较小，NNSS的误差最大，KWNN次之。在位置6处的误差比其他位置处的误差要大一些，原因是该点处距离每一个AP的距离都比较远，因此误差较大。
7 结束语
本文通过研究与分析典型的WLAN定位方法，设计与实现了一个WLAN定位系统。系统采用NNSS、KWNN和基于概率密度三种定位算法，并在实际环境中进行了测试，结果表明本文系统具有较高的定位准确性。
关键词：WLAN；室内定位；RSSI；位置指纹
中图分类号：TN929.5
1 前言
基于位置的服务（LBS）越来越受到人们的关注，越来越多的定位直接利用现成的无线通讯模块来估计对象节点的位置，应运而生的WLAN定位技术以低成本、低功耗成为室内定位的主要方法之一。
2 基于WLAN的定位算法
基于WLAN的定位算法主要有到达角度定位（Angle 0f Arrival，AOA）、到达时间定位（Time Of Arrival，TOA）、信号强度分析法（Received Signal Strength，RSS）以及位置指纹定位法（Location Fingerprint）。AOA和TOA需要专门的设备支持，而且受非视距以及多径影响比较严重；RSS对信道传输模型的依赖性非常强，多径效应、墙壁的遮挡以及环境条件的变化都会使其精度严重恶化。采用位置指纹定位技术则可以有效地克服以上定位算法的缺点。基于位置指纹的定位方法主要包括两个阶段：（1）构建指纹图（Radio Map）；（2）定位阶段。
3 基于位置指纹的WLAN定位的实现方法
3.1 定位网络构建
基于位置指纹的WLAN系统的实现，首先需要搭建一个室内无线局域网环境，使每个可能出现移动用户的位置被三个或三个以上AP信号覆盖。在初始情况下，根据经验和推测将AP放置在适当位置，保持一定的发射功率，然后选取一些关键点进行测量，如果发现盲区，则调整AP的位置，或者提高AP的发射功率，再进一步测量，直至可能出现移动用户的位置没有盲区为止 。定位网络系统由多个AP、多个移动客户端和一个定位服务器组成。移动客户端通过网卡获取其到各个AP的RSSI，并发送到定位服务器进行处理。
3.2 RSSI采样
参照室内平面图选择适当的采样点，在各个采样点多次测量和记录相应AP的RSSI值，并根据采样数据分析环境的无线信道情况。由于实验是构建环境RadioMap，因此必须采集尽可能多的数据。这就要求从多角度、多方面在同一采样点测量多次。
3.3 计算RadioMap
RadioMap是元组（ap，x，y，s）的集合，其中ap是某个特定的AP，（x，y）是每个采样点的平面坐标，s是（x，y）处ap的RSSI特征量，它被用作定位匹配算法的参考，直接影响定位精度，因此要求其中必须包含尽可能多的元组，而这些元组可以通过经验值法全部采样得到，也可以通过数学模型计算得到。
3.4 定位阶段（OnLine阶段）
当建立完RadioMap后，就可以运用相应的定位匹配算法，把实时测量的RSSI特征值和RadioMap中的位置指纹进行比较，找出最佳匹配，获得最佳定位效果。
4 定位算法
目前，在位置指纹定位算法中，典型的定位算法包括最近邻算法NNSS、加权k近邻KWNN和基于概率密度的方法。
4.1 最邻近算法
NNSS（Nearest Neighors in Signal Space）有n个AP，m个采样点。直接把RSSI平均值作为上述位置指纹，计算测量点的RSSI值和采样点的RSSI值之间的欧几里得距离，即假定第i个采样点的对各AP信号强度元组为（si1，si2…sin）用户当前位置测量得到的信号强度为（s1，s2……sn）。则测量点和第i个采样点的RSSI欧几里得距离为disi，i从1到m中，取dis最小的值所对应的采样点的位置为测量点的估计值。
4.2 加权K邻近算法（KWNN）
需要注意选择恰当的k值。因为如果k选取太大，则会将离用户实际位置并不是很近的点也包括进来，反而降低了定位精度。首先求测量点RSSI和各个采样点RSSI间的欧几里得距离，再取出k个欧几里得距离最小时对应的k个位置，求出该k个位置坐标的平均值作为该测量点的位置：
但直接求k个坐标的平均值作为测量点位置并不是很合适，应该距离越近的位置权值越大。根据该理论权值计算方法如下：
上述公式中k和q为两个参数，本系统中q被设为2。由此得出测量点坐标估计值为：
4.3 基于概率密度的定位算法（ProbabilityMethod）
在该定位方法中，一个采样点1处的位置指纹是RSSI值在该采样点上对各个AP的联合的概率密度。由于各个AP独立，因此联合概率可由各AP的边缘概率求得：
上式中 表示在l处AP1的RSSI为S1、AP2的RSSI为S2...APn的RSSI为Sn的联合概率密度， 表示在i处APi的RSSI为Si发生的边缘概率密度。
假设AP的所有RSSI样本都属于区间[min，max]，其中min和max是RSSI样本的最小值和最大值。该区间被划分成k个子区间，k是一个可调参数，影响着对概率密度估计的准确性。为了简化问题，把k个子区间设为等宽，每个子区间宽度w为：
而子区间的样本数量n的计算方法如下：
如图1所示，Si、Si+1、...、Si+j+1、Si+j+2都为RSSI样本，子区间宽度为w，由w1、w2、w3三部分组成，w1、w3为小数部分，w2为整数部分。
用上述直方图法求可求出采样点对各个AP的边缘概率密度进而求出各采样点的联合概率密度。在算法实现中为避免概率为0，在用直方图估计概率密度前给每个值设为1/N。测量点估计坐标为： 5 基于WLAN的定位系统实现
本系统的定位数据处理过程中，客户端核心工作是获取RSSI和发送RSSI，而服务器端的核心工作是接收RSSI，通过分析RSSI数据，计算并且形成RadioMap，最后通过定位计算，将位置呈现给用户。
5.1 系统服务器端
系统服务器端划分成如下。
实时定位模块：用户可以选择定位算法，接收来自数据采集的OnLine数据并根据用户选择的定位算法进行定位计算，然后将计算出的位置结果呈现给用户。
数据采集模块：负责与客户端的服务器通信模块进行通信，从客户端接收并解析RSSI数据包，将OnLine数据分发到实时定位模块，OffLine存入RSSI数据库，以便数据分析模块进行分析。
数据分析模块：分析数据采集模块得到的OffLine数据，计算RadioMap并用图表形式向用户呈现结果。
设备管理模块：负责AP以及移动终端的管理。
系统配置模块：用户可以配置数据库，SuperMap服务器，以及数据此采集模块的通信端口等。
5.2 系统客户端
系统客户端分为如下四个模块。读取RSSI模块：负责从网卡中读取RSSI值；服务器通信模块：负责和服务器进行通信，发送RSSI数据，解析服务器的发给客户端的配置信息。配置信息将影响读取RSSI模块的采集行为；客户端配置模块：读取本地配置文件；本地存取RSSI模块：当服务器通信模块发送RSSI数据失败时，负责将发送失败的RSSI数据存入本地文件中，以便后期处理。
6 实验结果与分析
本系统构建的定位区域为750cm*780cm的室内环境，为减少复杂环境对定位效果的影响，把每次数据采集布置成一个任务，每个任务对应一个位置指纹。定位所采用的指纹库是在上述定位环境内的13个采样点的指纹组成，共6个待测位置进行了定位实验。每个采样点采样次数为100次，采样周期为300ms，每个待测位置采集定位数据500-600次共3400次。
用三种定位算法进行定位，当取K=5时，三种算法的误差比较如图2所示。
从图中可以看出：基于概率密度的误差较小，NNSS的误差最大，KWNN次之。在位置6处的误差比其他位置处的误差要大一些，原因是该点处距离每一个AP的距离都比较远，因此误差较大。
7 结束语
本文通过研究与分析典型的WLAN定位方法，设计与实现了一个WLAN定位系统。系统采用NNSS、KWNN和基于概率密度三种定位算法，并在实际环境中进行了测试，结果表明本文系统具有较高的定位准确性。