基于信息熵的WLAN室内定位Radio Map更新方法

摘要

基于信息熵的WLAN室内定位Radio Map更新方法，涉及WLAN室内定位方法。解决了现有WLAN室内定位Radio Map更新方法存在的定位精度差、定位复杂以及更新的工作量大等问题。本发明通过在各参考点测量到的AP信号强度RSS值存储在Radio Map中，选择其中信息熵增益较大的AP并计算两两之间的互信息熵，依次选择互信息熵较大的AP后，利用隐马尔科夫模型对离线阶段的Radio Map进行更新，使用KNN算法分别对比离线阶段的Radio Map和更新后的Radio Map对在线阶段测得的RSS向量的定位准确度，更新后的Radio Map较更新前的Radio Map有助于提高定位精度。本发明适用于WLAN室内定位。

说明书

技术领域

本发明涉及一种信息论领域WLAN室内定位的Radio Map更新方法，具体涉及WLAN室内定位方法。 

背景技术

随着智能手机的普及，位置定位服务越来越受到人们的重视。而现如今的卫星定位只解决了室外定位的问题，室内定位仍未得到统一。IEEE802.11标准的提出，使得无线局域网(Wireless Local Area Networks)的部署越来越广泛。而基于WLAN的室内定位方法由于其部署方便，无需添加其他硬件设备而得到广泛的关注。 

WLAN室内定位技术通过测量来自接入点AP(Access Point)的接收信号强度RSS(Received Signal Strength)估计出移动设备的位置。通常该定位系统分为两步即建立Radio Map的离线阶段和在线的定位估计阶段。Radio Map是由测量环境中的每个点接收到来自该环境中各个AP的信号强度值向量组成。由于无线电在室内传播易受到门的开启及闭合，人的走动，墙壁的阻挡等多重因素影响，为提高室内定位精度，需要在参考点处多次测量并定期更新来自各AP的信号强度弥补由于随机噪声对Radio Map产生的影响。然而为获得该信号向量，对信号向量进行位置标注是一件很耗时的工作。因而本发明提出一种基于隐马尔科夫模型(Hidden Markov Model,HMM)的Radio Map更新方法，即在已知一连串的接收信号强度下，通过训练隐马尔科夫模型得到该信号的位置坐标。 

同时，在实际观测环境中，我们注意到在不同的区域不同的AP具有不同的定位能力，特别是在一个较大环境中，某些区域接收不到与该区域距离较远的一些AP的辐射信号。因为我们引出一些原则来区分不同AP的定位能力，若在该区域中AP的定位能力强，则在更新Radio Map阶段也将主要更新这些定位能力较强的AP。传统方法一般选择均值最大的AP作为定位AP，在Radio Map更新时也只更新这些AP的值，该方法未能考虑AP的对于各个参考点的区分能力。 

发明内容

本发明为了解决现有WLAN室内定位Radio Map更新方法存在定位精度差、定位复杂以及更新的工作量大等问题，进而提供了一种基于隐马尔科夫模型(HMM)的RadioMap更新方法。 

本发明的基于信息熵的WLAN室内定位Radio Map更新方法的过程为： 

步骤1：根据无线电在室内传播的有关特点及AP能使用的频段合理部署AP，保证环境中任意位置均可采集到来自至少2个AP的信号强度，且信号功率大于或等于-95dBm； 

步骤2：根据需要定位的室内环境，选择合适的坐标原点以建立二维直角坐标系，均匀设置参考点并根据该直角坐标系标定各参考点坐标，在每个参考点处测量来自各AP的辐射信号强度并将该参考点的二维坐标及测量到的AP信号强度保存在Radio Map中； 

步骤3：对预更新的区域引入信息熵增益模型，选择其中r个信息熵增益较大的AP用于后续定位及更新操作； 

步骤4：在选择r个信息熵增益较大的AP后，对r个AP计算两两之间的互信息熵，依次选择互信息熵较大的两AP作为定位及更新操作直到AP数量达到需求值m为止； 

步骤5：利用测得的RSS值使用隐马尔科夫模型更新Radio Map。 

本发明提出引入信息熵增益及互信息熵模型对Radio Map进行化简，然后使用机器学习领域中的隐马尔科夫模型对测量得到的数据应用到原始数据从而更新Radio Map。 

本发明的意义在于利用隐马尔科夫模型模拟用户行为，从而能够利用未标记位置的更新阶段测得数据更新原有的Radio Map，减少Radio Map更新的工作量。同时引入信息熵模型选取对定位贡献大的AP进行更新操作，并利用这些AP进行定位，可以减少定位复杂度。使用KNN算法分别对比离线阶段的Radio Map和更新后的Radio Map，本方法定位精度可以提高7％以上。 

附图说明

图1为具体实施例的定位实验场景，其中，面积为66.4×24.9m²，层高3m，砖质墙面，铝合金窗户和金属门，27个AP放置在同一楼层，AP选择为Linksys WAP54G，固定在2m高度，支持IEEE802.11b/g标准，传输速率54Mbps，接收端采用装有Intel PRO/Wireless3945ABG无线网卡的ASUS A8F笔记本电脑，距地面1.2m； 

图2为具体实施例的更新Radio Map区域，其中，包括40个参考点； 

图3(a)为实验场景中各AP的自信息熵； 

图3(b)为实验场景中部分AP组合的互信息熵； 

图4为使用隐马尔科夫模型更新前与更新后的Radio Map对定位误差的影响的对比； 

图5为2m内改变使用AP数量即m值对定位误差的影响的对比图。 

具体实施方式

具体实施方式一：基于信息熵的WLAN室内定位Radio Map更新及定位方法。它包括下述步骤： 

步骤1：根据无线电在室内传播的有关特点及AP能使用的频段合理部署AP，保证环境中任意位置均可采集到来自至少2个AP的信号强度，且信号功率大于或等于-95dBm； 

步骤2：根据需要定位的室内环境，选择合适的坐标原点以建立二维直角坐标系，均匀设置参考点并根据该直角坐标系标定各参考点坐标，在每个参考点处测量来自各AP的辐射信号强度并将该参考点的二维坐标及测量到的AP信号强度保存在Radio Map中； 

步骤3：对预更新的区域引入信息熵增益模型，选择其中r，r≤M个信息熵增益较大的AP用于后续定位及更新操作； 

步骤4：在选择r个信息熵增益较大的AP后，对r个AP计算两两之间的互信息熵，依次选择互信息熵较大的两AP作为定位及更新操作直到AP数量达到需求值m，m<r为止； 

步骤5：利用测得的RSS值使用隐马尔科夫模型更新Radio Map； 

步骤6：依据在各参考点处测得的RSS值使用离线阶段的Radio Map和更新后的RadioMap分别计算该测量数据的二维坐标，并计算该二维坐标与实际位置的误差。使用KNN算法分别对比离线阶段的Radio Map和更新后的Radio Map对在线阶段测得的RSS向量(在同一位置处测得的接收到多个AP的RSS值组成)的定位准确度；分别对比更新不同数量的AP对定位准确度的影响。 

具体实施方式二：本实施方式的步骤2中“在每个参考点处测量来自各AP的辐射信号强度并将该参考点的二维坐标及测量到的AP信号强度保存在Radio Map中”的具体操作步骤为： 

在待更新区域中的每个参考点处利用信号接收机采集并记录来自每一个AP的接收信号强度RSS值n次并记录该参考点的二维坐标，形成N×n×(M+2)矩阵，其中N为待更新区域中参考点个数，n为在每一个参考点处采集信号的次数，M+2中M代表该环境中AP的数量，2代表二维坐标，保存在Radio Map中。 

其它实施方式与具体实施方式一相同。 

具体实施方式三：本实施方式的步骤3中“选择其中r个信息熵增益较大的AP”的具体操作步骤为： 

步骤3.1：计算待更新区域中每个AP的信息熵增益(Information Gain,IG)，根据公 式(1)计算，其中H(l)代表用户位置的信息熵，如公式(2)所示，其中p(l_g)表示在用户在位置l_g,g＝{1,2,…N}处的概率，为使用方便认为用户在各参考点处的概率相等即为 从而公式(2)如公式(4)所示，当测试点获得的来自第i个AP(AP_i)的信号强度RSS值已知时，测试点实际位置的不确定度，即条件熵值H(l|AP_i)的计算如式(4)所示，其中p(l_g|AP_i＝v_e)代表在AP_i＝v_e的条件下，测试点在l_g处的条件概率，其计算如式(5)所示，式中p(AP_i＝v_e|l_g)表示在位置l_g处测得AP_i的RSS值为v_e的概率(v_e＝{0,-1,-2,…-100})，该概率值可通过离线阶段测得的Radio Map统计结果得知，即在同一位置处通过n次测量统计出在该位置处AP_i＝v_e的概率。p(AP_i＝v_e)表示在所有参考点处测得AP_i的RSS值为v_e的概率，即公式(5)中p(l_g,AP_i＝v_e)＝p(AP_i＝v_e|l_g)p(l_g)代表测试点在l_g处的同时AP_i＝v_e的联合概率； 

IG(AP_i)＝H(l)-H(l|AP_i)(1) 

$>H\left(l\right)=-{\Sigma }_{g=1}^{N}p\left(l_g\right){\log }_{2}p\left(l_g\right)---\left(2\right)$>

H(l)＝log₂N    (3) 

$>H\left(l\right|{\mathrm{AP}}_i)=-{\Sigma }_{v_e}{\Sigma }_{g=1}^{N}p(l_g,{\mathrm{AP}}_i=v_e){\log }_{2}p\left(l_g\right|{\mathrm{AP}}_i=v_e)---\left(4\right)$>

p(l_g|AP_i＝v_e)＝p(l_g,AP_i＝v_e)/p(AP_i＝v_e)＝p(AP_i＝v_e|l_g)p(l_g)/p(AP_i＝v_e)    (5) 

步骤3.2：对步骤3.1中计算出的M个的信息熵增益IG(AP_i)的大小进行排序(i＝(1,2,…M))，选取r，r≤M个信息熵增益大的AP，； 

其它实施方式与具体实施方式二相同。 

具体实施方式四：本实施方式的步骤4的具体操作步骤为： 

步骤4.1：对选取出的r个AP进行两两互信息熵(Mutual Information Entropy,MIE)的计算，计算公式如式(6)所示，其中H(l)如式(3)所示，在已知AP_i和AP_j，j＝(1,2,…M)，的RSS值用户位置的不确定度H(l|AP_i,AP_j)的计算如式(7)所示，其中Pa＝p(l_g,AP_i＝v_e,AP_j＝v_e′)＝p(AP_i＝v_e,AP_j＝v_e′|l_g)p(l_g)代表测试点在l_g处的同时测量 到的AP_i的RSS值为v_e，AP_j的RSS值为v_e′的概率(v_e′＝{0,-1,-2,…-100})，p(AP_i＝v_e,AP_j＝v_e′|l_g)代表在测试点在l_g测得AP_i的RSS值为v_e，AP_j的RSS值为v_e′的概率，该概率可由离线阶段测得的Radio Map的统计结果得知。Pb＝p(l_g|AP_i＝v_e,AP_j＝v_e′)代表测量得到AP_i的RSS值为v_e，AP_j的RSS值为v_e′的位置在l_g处的概率。其计算公式如式(8)所示，其中v_e′与v_e取值集合相同。式中 $>p({\mathrm{AP}}_i=v_e,{\mathrm{AP}}_j=v_{e^{\prime }})={\Sigma }_{g=1}^{N}p({\mathrm{AP}}_i=v_e,{\mathrm{AP}}_j=v_{e^{\prime }}|l_g);$>

MIE(AP_i,AP_j)＝H(l)-H(l|AP_i,AP_j)    (6) 

$>H\left(l\right|{\mathrm{AP}}_i,{\mathrm{AP}}_j)=-{\Sigma }_{v_e}{\Sigma }_{v_{e^{\prime }}}{\Sigma }_{g=1}^N\mathrm{Pa}·{\log }_2\mathrm{Pb}---\left(7\right)$>

Pb＝Pa/p(AP_i＝v_e,AP_j＝v_e′)    (8) 

步骤4.2：对步骤4.1中的种AP组合的互信息熵进行排序，从大到小依次选取m，m<r个AP用于Radio Map更新的处理。 

其它实施方式与具体实施方式三相同。 

具体实施方式五：本实施方式的步骤5的具体操作步骤为： 

步骤5.1：Radio Map更新第一阶段为隐马尔科夫过程建立，隐马尔科夫过程是马尔科夫过程的一种，具有有限状态并且每个状态都与观测值之间有一套随机概率密度函数，隐马尔科夫过程由五部分组成： 

(1)模型中的状态数L＝{l₁,l₂,…l_N}，l₁,l₂,…l_N代表用户位置数，即N个参考点； 

(2)从一个状态可能输出的不同的符号数V＝{v₁,v₂,…v₁₀₁}，v₁,v₂,…v₁₀₁代表在某一参考点处接收到的某个AP的RSS信号值，其取值范围为(0,-1,-2,…-100)dBm； 

(3)状态转移概率A＝{a_cd＝p(q_t+1＝l_c|q_t＝l_d)},1≤c,d≤N，a_cd代表用户位置转移概率即从t时刻在位置l_d处到t+1时刻到达位置l_c处的概率，a_cd满足a_cd≥0，且仅考虑直线行走的概率； 

(4)在状态l_g处观测到特定符号v_e,1≤e≤101的概率矩阵B＝{b_g(e)＝p(O_t＝v_e|q_t＝l_g)}，b_g(e)＝p(O_t＝v_e|q_t＝l_g)表示t时刻在位置l_g 处的条件下接收到的某个AP辐射的RSS信号值v_e的条件概率，其中b_g(e)满足b_g(e)≥0，$>{\Sigma }_{e=1}^{101}{b}_g\left(e\right)=1;$>

(5)初始位置概率分布矩阵π＝{π_g＝p(q₁＝l_g)}，π_g满足π_g≥0，指定4个初始点，均匀概率，其他参考点处初始概率为0； 

在建立好隐马尔科夫模型θ＝(A,B，π)后，对于观测序列O＝O₁O₂...O_T即在环境中测到的一序列RSS值，通过解码方法得到相应的位置输出Q＝q₁q₂...q_T即测量时这一序列RSS值时所处的位置，使得该位置输出能最好的解释观测序列。 

步骤5.2：Radio Map更新第二阶段为对隐马尔科夫过程进行参数训练，对Radio Map实现更新，它包括以下步骤： 

步骤5.2.1：由离线阶段测得的Radio Map计算每个参考点处接收到的各AP信号值的概率从而得到隐马尔科夫模型中的B矩阵，在该矩阵中，每个AP对应一个B矩阵，隐马尔科夫模型建立中的五个元素中的B矩阵描述可得出该矩阵的维数为N×101即N个参考点，每个参考点处得到某AP的RSS值的个数为101个即0dBm到-100dBm； 

步骤5.2.2：依据选择出的m个AP逐个AP对离线阶段测得的Radio Map中的B矩阵进行更新操作，更新步骤如下所述； 

步骤5.2.3：由参考点的所在环境中的部署，确定合理的物理轨迹(考虑到人的走向问题，本发明选用了4条物理轨迹，即人员的走动限定为直线行走)。通过在该环境中得到的RSS轨迹即实测轨迹(在同一个AP下得到的不同位置处的RSS值)计算实测轨迹与物理轨迹之间的吻合度，计算公式如式(9)所示。式中为长度为n_t的同一个AP处得到的RSS值构成的轨迹，该轨迹称为实测轨迹，其物理位置未知。 是长度与t相等的所有可能的位置序列也称为物理轨迹，θ为当前模型参数，v₁即RSS轨迹中第一个RSS值，l₁即为选定的初始点中的一个； 

$>\left(\begin{array}{c}p(t,q)=p\left(t\right|q,\theta )p\left(q\right|\theta )\\ =p\left(l_1\right|\theta )p\left(v_1\right|l_1,\theta )\times \underset{g=2}{\overset{n_t}{\Pi }}p\left(l_g\right|l_{g-1},\theta )p\left(v_e\right|l_g,\theta )\end{array}\right)---\left(9\right)$>

步骤5.2.4：由于每条物理轨迹是由对应的参考点组成，因此可以通过实测轨迹与物理轨迹之间的吻合度计算对应参考点处的RSS值的概率。经过f次迭代后，对每个参考点l_i,i＝1,2,…N分别根据步骤5.2.3中得到的轨迹吻合度p(t,q)计算相应的RSS值v_e的概 率，由公式(10)计算出。式中p(l_g＝l_i|θ^f,t)即为对应p(t,q)的值，θ^f代表第f次迭代后的模型参数。其中δ(v_e,v_e′)由式(11)表示； 

$>p{\left(v_e\right|l_i)}^{f+1}=\frac{\underset{t\in T}{\Sigma }\underset{g=1}{\overset{t_n}{\Sigma }}p(l_g=l_i|{\theta }^f,t)\delta (v_{e^{\prime }},v_e)}{\underset{t\in T}{\Sigma }\underset{g=1}{\overset{t_n}{\Sigma }}p(l_g=l_i|{\theta }^f,t)}---\left(10\right)$>

$>\delta (v_e,v_{e^{\prime }})=\left(\begin{array}{cc}1& v_e=v_{e^{\prime }}\\ 0& v_e\ne v_{e^{\prime }}\end{array}\right)---\left(11\right)$>

步骤5.2.5：由步骤5.2.4得到的每个参考点处的概率信息乘以相应的RSS值得到更新该AP后的Radio Map。并由式(12)计算每条实际轨迹与所有物理轨迹的吻合度之和的乘积。式中T为未标示位置集合，通过计算p(T|θ)判断收敛，若p(T|θ)不再发生变化或变化很小(0.0001范围内)，则认为已得到合适的吻合度。并与更新前的Radio Map作比较，若p(T|θ)相差小于一个阈值(0.0001范围内)，则算法终止； 

$>\left(\begin{array}{c}p\left(T\right|\theta )=\underset{t\in T}{\Pi }p\left(t\right|\theta )=\underset{t\in T}{\Pi }\underset{q}{\Sigma }p\left(t\right|q,\theta )p\left(q\right|\theta )\\ =\underset{t\in T}{\Pi }\underset{q}{\Sigma }(p\left(l_1\right|\theta )p\left(v_1\right|l_1,\theta )\times \underset{g=2}{\overset{n_t}{\Pi }}p\left(l_g\right|l_{g-1},\theta )p\left(v_e\right|l_g,\theta ))\end{array}\right)---\left(12\right)$>

步骤5.2.6：重复步骤5.2.3、步骤5.2.4、步骤5.2.5，直到选择出的m个AP全部更新完成，得到最终更新后的Radio Map。 

其它实施方式与具体实施方式四相同。 

具体实施方式六：本实施方式的步骤6它包括以下几个步骤： 

6.1：对离线阶段的Radio Map每个参考点处测量的n次RSS向量取平均，得到一个1×(M+2)的向量，向量中前两个元素代表参考点位置，后M个元素代表在该参考点测得的分别来自M个AP的RSS均值； 

6.2：根据定位能力较强的m个AP，计算第p,p＝(1,2,…P)个测试点(Test Point,TP)测得的该m个AP的RSS向量(RSS_p1,RSS_p2,…RSS_pm)与第g,g＝(1,2,…N)个参考点(Reference Point,RP)m个AP的RSS向量(RSS_g1,RSS_g2,…RSS_gm)之间的欧氏距离d_gp,P代表总的测试点个数，计算公式如式(13)所示； 

$>d_{\mathrm{gp}}={\left({\Sigma }_{i=1}^m{|{\mathrm{RSS}}_{\mathrm{gi}}-{\mathrm{RSS}}_{\mathrm{pi}}|}^2\right)}^{1/2}---\left(13\right)$>

6.3：从步骤6.2中得到的N个d_gp中选择K个与测试点特征向量距离最小的参考点，根据K个参考点二维坐标由式(14)所示计算出测试点的定位坐标，式中(x_p,y_p)代表第p个测试点的二维坐标，(x_g,y_g)代表第g个参考点的二维坐标。并与实际位置对比，统计定位误差； 

$>(x_p,y_p)=\frac{1}{K}\underset{g=1}{\overset{K}{\Sigma }}(x_g,y_g)---\left(14\right)$>

6.4：对更新后的Radio Map重复步骤6.1、步骤6.2、步骤6.3，得到由更新后Radio Map测得的测试点定位坐标并与实际位置对比，统计定位误差。对比两种Radio Map得到的测试点定位坐标的累积定位误差(即定位误差在几m内的累积概率，累积概率越大，说明误差在这个范围内出现的概率越大，如果该范围越小，说明定位误差越小)； 

其它实施方式与具体实施方式五相同。 

实施例 

在图1所示的室内场景中进行实验，该环境中包括19个实验室，1个会议室和一个乒乓球室，墙的材料是砖块，铝合金窗户和金属门，各接入点AP为Cisco，且用AP1、AP2、……、AP27标示1至27号AP，各AP固定在距地面2m高度的位置。信号接收机离地面1.2m，选择走廊作为实验场所，发明选取图1中的一部分区域如图2所示进行实验。相邻参考点之间间隔为0.5m，共40个参考点。 

根据具体实施方式二、三、四，在每个参考点处使用Intel PRO/Wireless3945ABGnetwork connection的无线网卡连接入网，在Windows XP操作系统下收集来自27个接入点AP的信号强度RSS值；对于每一个参考点，每秒采样1次。一共采集200次，形成离线数据库Radio Map。并对离线Radio Map进行信息熵及互信息熵处理，处理结果如图3(a)所示。由图3(a)可知，每个AP的信息熵增益不同信息熵增益最大的为第21个AP，其次为第11个AP。信息熵增益大的对定位贡献也大。由图3(b)可知，信息熵增益大的AP其相应的互信息熵也较大。发明只列出信息熵增益较大的几个AP的互信息熵。图中每个点处所示为相应的AP组合。 

根据具体实施方式五，构建隐马尔科夫模型，并更新该区域的Radio Map，并依据具体实施方式六，比较两种情况下的Radio Map对在线数据的定位影响。定位结果如图4所示，从图中可看出，更新后的Radio Map较更新前的Radio Map对定位精度的提高有一 定的帮助如在误差距离为1.5m处，更新前的Radio Map得到的累计定位误差概率(累计定位误差概率表示所有测试点定位误差落在该误差范围内的测试点个数与总的测试点个数的比)为0.5325，而更新后的Radio Map用于定位得到的累计定位误差概率为0.57。 

图5所示为改变m值对2m内定位误差的影响的对比，从图中可看出m值的变化对定位误差是有影响的。m值增大并不一定提高定位准确度。如AP数量为3时2m内累计定位误差概率达到最大，即定位误差在2m范围内的测试点个数更多。