一种基于弱感知通信芯片的动态精度无线定位方法

赵荣阳，李小龙，梁家海

1(北部湾大学 电子与信息工程学院，广西 钦州 535011) 2(湖南工商大学 新零售虚拟现实技术湖南省重点实验室，长沙 410205)

1 引 言

室内定位能在室内环境下为指定对象和用户提供有效的跟踪[1]、定位和导航服务，停车场、商场、火车站等场所对定位和导引的需求日趋强烈.这些需求为室内定位系统[2](Indoor Positioning System，IPS)提供了巨大的机会.对比于其它的室内定位技术，如视频分析定位[3]、基于可见光通信的定位[4]等，无线定位技术具有覆盖区域广、定位精度高[5]、成本低等特点[6].目前，不同的无线室内定位系统(Wireless Indoor Positioning System，WIPS)依赖于不同的无线基础设施[7]，如ZIGBEE、蓝牙[8](Bluetooth)、WIFI[9]和RFID等.为了促进无线室内定位技术的快速发展和推广应用，关键的问题是在保持定位准确性的同时、尽可能地降低系统成本，以促进无线室内定位行业的快速推广和健康发展.

对于WIPS中的无线节点来说，系统芯片的价格在其生产成本上占据着较高的比例.目前，常见的通信芯片有Nordic Semiconductor公司的nRF24系列芯片，广泛应用于蓝牙产品、兼容于IEEE 802.15的Texas Instruments公司的CC2540系列芯片，广泛应用于WIFI产品、兼容于IEEE 802.11协议的Atmel公司的Atmel®Smart Connect WIFI系列芯片等.通过比较这些广泛应用于无线产品的商业芯片，运行在2.4GHz的nRF24系列芯片，如nRF24L01+，在价格成本上最有优势[10].这种芯片具有能耗低、传输速率快、数据帧的有效载荷比高等优点，然而这些芯片存在着如下的功能限制：没有RSSI(Received Signal Strength Indicator)的感知能力，也就是无法测量收到的信号强度[11]，仅提供多个无线射频输出功率来调节信号的传输范围，并且接收节点收到发送节点的最小离散输出功率(Received Minimum Discrete Output Power，RMDOP)与其传输范围之间不服从均匀分布[12].

图1 芯片功率档位关系示意图Fig.1 Schematic diagram of the relationship between chip power and distance

如图1所示，假设此类芯片的L个离散输出功率的档位从P1～PL逐渐增大，相应功率档位的最大传输距离为r1，r2…rL(rL-1

2 问题描述

2.1 网络模型

考虑弱信号感知能力通信芯片的功能限制，当芯片作为无线定位系统参考节点，随机部署在二维平面的待定位区域内时，区域内的接收点无法预先确定其接收到的各参考节点的RMDOP值，故对弱感知芯片无线定位系统做如下性质假设：

1)仅考虑RMDOP与其传输范围(距离)之间的关系，忽略环境对信号传输的干扰；

2)数量为n的弱感知芯片作为定位系统的参考节点，随机部署之后，参考节点的物理位置已知且静止；

3)弱感知芯片具有P1～PL+1，共L+1个离散功率输出档位，其中P1～PL功率档位为接收点能够收到的功率值，各档位对应呈递增关系的最大传输距离：r1，r2，rl…rL(rl-1rL；

4)待定位区域以网格方式划分，每一个单元网格的物理位置由其中心点的坐标表示；

5)待定位区域内每一个单元网格的指纹向量，由其中心点的指纹向量表示；

2.2 问题建模

弱感知芯片的离散功率输出特性，是产生本文所研究问题的主要原因之一.在提出具体问题模型之前，首先给出相关定义.

定义1.最小接收功率(RMDOP)：假设参考节点i的物理坐标为(xi，yi)，i∈(1，2，…，n)，待定位的二维平面区域，被划分为边长为d的G个正方形单元网格，其中网格j的中点物理坐标为(xj，yj)，j∈G，rij表示参考节点i到网格j中心点的距离，那么在此距离范围下，网格j接收能够接收到参考节点i的功率最小值，称为最小接收功率(RMDOP)，记为：Pij.

定义2.单元网格指纹：单元网格中心点接收各参考节点发送的RMDOP值序列，称为单元网格指纹，即：Fj=，i∈(1，2…n)，j∈G.

定义3.高差异度指纹：假设任意两个单元网格j与g的中心点之间的物理距离，等于两个单元网格边长之和的1/2，称它们为相邻网格；当采用欧式距离判断Fj与其所有的相邻网格指纹Fg存在的差异程度时，若存在一个较大的标量δ，使得不等式：|Fj-Fg|≥δ均成立，即满足公式(1)时，则称Fj为高差异度指纹；其中，设Nj为单元网格j的相邻网格数目，Fg=，i∈(1，2…n)，g∈Nj，Nj∈G.

Min(|Fj-Fg|)≥δ，j∈G，g∈Nj

(1)

考虑任意此类室内定位系统的指纹库内，皆可能存在高差异度指纹，本文针对存在的高差异度指纹采用迭代分割的方法，即将高差异度指纹的单元网格，分割成若干个边长更小的子网格，当子网格序列获得定义2的单元格指纹之后，构成了定位系统的一个具有动态精度的指纹库，以达到提高系统定位精度的目的.

假设待定位区域的总面积为S，初始指纹网格的边长为d0；通过迭代调度、动态分割高差异度指纹的单元网格后，未被分割的非高差异度指纹的单元网格总面积记为S0，指纹网格边长为d0，仅实现迭代一次的高差异度指纹的单元网格分割面积为S1，分割后的子网格边长为d1；实现二次迭代的高差异度指纹的单元网格分割面积为S2，分割后的子网格边长为d2；以此类推，实现K次迭代的高差异度指纹的单元网格分割面积为SK，分割后的子网格边长为dK；其中，d1，d2，…，dK之间的符合如下关系：d1=α×d2…dK=α×dK-1α<1.因此，此类室内无线定位系统的动态定位精度模型，如公式(2)所示，其中A为动态定位精度值.

(2)

针对基于弱感知通信芯片的定位系统，一般情况下动态精度方法的迭代次数，取决于某次迭代后，重构的指纹库内是否存在高差异度指纹.通常迭代次数越多，动态精度将越高，但是迭代次数的增加，将会增大指纹库建立阶段的采样耗时及系统开销.设有一个较小的系统定位精度标量值ε，当动态定位精度值符合条件A<ε时，停止迭代，称ε为动态精度无线定位方法的截止精度.

定义4.动态指纹库：设在初始指纹库建立之后，所有单元网格的边长均相等，为静态指纹库；当静态指纹库内存在定义3所述的高差异度指纹，并实现了高差异度指纹的K次迭代分割后，重构的含有不同单元格网格边长、具有动态定位精度的新指纹库，称为动态指纹库.

3 动态指纹库调整策略

随机部署的弱感知芯片作为室内无线定位系统参考节点，考虑芯片的功能限制，系统有如下特点：

1)参考节点芯片仅提供若干传输范围可调节的输出功率档位，具有离散性；

2)接收节点收到发送节点的RMDOP值与其传输范围之间不服从均匀分布；

3)芯片作为参考节点的部署情况随机，即：在芯片部署之前，参考节点的位置坐标、参考节点之间的距离等是不确定的.

4)室内定位系统的平均定位精度，取决于待定位区域网格化的单元网格划分情况；

因此，在网格化的待定位区域内，当任意单元网格j的指纹Fj为高差异度指纹时，可以通过迭代的方法，动态分割此高差异度指纹的单元网格，将其划分为m×m个子网格，以提高基于弱感知芯片随机部署的室内定位系统的定位精度.动态精度指纹库的调整策略，包括如下步骤：

步骤1.在待定位的MM二维区域内，根据起始点的物理坐标、待定位区域面积、静态指纹单元网格边长、面积，计算待定位区域内的静态指纹网格总数G、各单元网格中心点的位置坐标；

步骤2.计算待定位区域内任意单元网格j的中心点与参考节点i之间的距离，并比较参考节点传输功率的距离范围序列r1，r2，rl…rL(rl-1

步骤3.依据单元网格指纹与其相邻网格之间的指纹差异程度，判别指纹库内的高差异度指纹，通过迭代法动态分割高差异度指纹的单元网格，并重构一个含有不同单元网格边长的动态指纹库G1；

步骤3.1.遍历静态指纹库G，依据定义3，当单元网格的指纹Fj满足公式1时，记录Fj为高差异度指纹；将高差异度指纹的单元网格j，重新划分为m×m的子网格，每一个子网格的边长，为原高差异度指纹的单元网格边长的α倍，并根据定义2计算子网格的指纹，其中m≥2，0<α<1；当所有高差异度指纹的单元网格均被重新划分之后，全部指纹重新构建为一个，含有不同单元网格边长的动态指纹库G1；

步骤3.2.遍历动态指纹库G1，迭代执行步骤3.1，直到当前被遍历的动态指纹库G1内不存在高差异度指纹，或者定位精度小于精度标量ε，终止算法，从而获得室内定位系统最优的动态指纹库G1.

4 动态精度定位算法描述

4.1 静态指纹库的构建

静态指纹库是定位系统采用动态精度定位方法时的初始指纹库，根据定义2可知，单元网格指纹是其中心点接收各参考节点发送的RMDOP值序列，即：Fj=，i∈(1，2…n)，j∈G，n为参考节点的数目，G为单元网格的总数；由问题假设与定义1可知，弱感知芯片具有P1～PL+1，共L+1个与距离相关的离散功率输出档位，对于待定位区域内任意单元网格的RMDOP值，可以通过中心点与参考节点之间的距离关系获得.首先计算单元网格j的中心点与参考节点i之间的距离rij，然后在参考节点发送功率档位的传输距离序列内查找，如果存在一个大于rij的最小值rl(rl-1rL时，单元网格j接收到参考节点i的RMDOP值Pij=PL+1，j∈G，i∈(1，2…n)，l∈(1，2…L)，Pij的计算如公式(3)所示.

(3)

图2 静态指纹库建立流程图Fig.2 Chart of static radio map building

重复上述操作直至获得单元网格j与所有参考节点的RMDOP值，并以j接收到的各个参考节点的RMDOP值序列，构成单元网格j的指纹向量Fj，当待定位区域内的所有单元网格均被赋值后，获得定位系统的静态指纹库.静态指纹库建立的算法程序流程图，如图2所示.

4.2 动态指纹库的构建

动态指纹库的构建过程中，首先遍历静态指纹库G，若存在Fj，jG，满足公式(1)，则静态指纹库G内存在高差异度指纹，然后记录高差异度指纹，并迭代分割其单元网格.每一个高差异度指纹的单元网格被划分为m×m的子网格序列，以dj表示高差异度指纹Fj的单元网格j的边长，d表示分割后的子网格边长，其中d=αdj，m≥2，0<α<1.本文取m=2，d=1/2dj，算法执行的过程中，将根据高差异度指纹的单元网格中心点位置坐标、子网格边长，重新计算子网格的中心点坐标，然后利用静态指纹库的构建方法，生成高差异度指纹Fj的子网格指纹序列；最后，将新生成的各高差异度指纹的子指纹序列与静态指纹库，重构为一个含有不同单元网格边长的新指纹库-动态指纹库，指纹同样记为Fk=，i∈(1，2…n)，k∈G1，G1为动态指纹库内的指纹总量，n为参考节点的数目.

依据动态指纹库的构建步骤3.2，迭代遍历、重构动态指纹库G1.当动态指纹库G1内不存在高差异度指纹，或者动态定位精度值符合条件A<ε，即定位精度A小于系统的截止精度标量ε时，得到的指纹库G1被认为是系统的最优动态指纹库，终止迭代算法.动态指纹库的构建程序流程图，如图3所示.

图3 动态指纹库构建流程图Fig.3 Chart of dynamic radio map building

4.3 位置估计方法描述

目标点的位置估计，是室内无线定位系统最终的目标，即当系统获得目标点T的指纹向量FT后，在动态指纹库G1内寻找FT的匹配指纹Fg，g∈G1.在众多的指纹序列匹配方法中，本文选择了欧式距离函数，来求解两个指纹的匹配度，计算如公式(4).

(4)

公式(4)中dist表示目标指纹FT与G1内指纹Fg的匹配程度，当dist=0时，FT与Fg完全匹配；当dist0时，使得dist取最小值的Fg为FT的最优匹配值.因为指纹向量是由芯片参考节点的离散输出功率档构成，采用距离最邻近(NN)方法进行位置估计时，可能存在不唯一的最优匹配值，即：目标节点T可能存在k个估计值，k≥1.因此，本文在遍历动态指纹库、计算所有单元网格指纹与目标指纹FT的距离时，将目标点T的匹配指纹Fg以dist值的升序，存储于候选估计队列Q中，并选择k最近邻(KNN)匹配方法，计算k个最优匹配指纹的单元网格中心点平均坐标，作为目标点的位置估计结果，计算如公式(5).其中(xT，yT)为目标点的位置估计坐标，(xg，yg)为最优匹配指纹Fg的单元网格中心点坐标，k的值由候选估计队列Q内，最优匹配指纹Fg的数目决定.

(5)

5 实验仿真

设参考的接收功率为1-5档，传输距离分别为[3，5，7，8，9]，仿真模拟弱感知通信芯片作为参考节点，随机部署在20×20的二维平面；选取了各接收功率传输距离的均方差，作为高差异度指纹判别标量δ；静态指纹库边长的初始值d0=4；在参考节点数目n=7、n=10、n=20的条件下，分别完成15次独立实验.实验以动态指纹库的一次、二次迭代定位精度为考察目标，主要从参考节点数目与高差异度指纹的迭代次数、动态定位精度之间的关系；动态指纹库、静态指纹库的系统精度、节点定位误差等方面评估动态精度定位算法的性能.

5.1 定位精度分析

在动态精度定位算法的15次独立实验中，当参考节点数目n=7时，出现了1次不迭代(未出现高差异度指纹)、5次只进行一次迭代的情况；当n=10时，仅出现1次只进行一次迭代的情况；当n=20时，15次实验均进行了二次迭代.算法的一次、二次迭代精度如表1、表2所示.

表1 一次迭代定位精度Table 1 Resolution for positioning in the first iteration

表2 二次迭代定位精度Table 2 Resolution for positioning in the second iteration

在参考节点数目分别为n=7、n=10、n=20时，动态指纹库的一次、二次迭代分割后，定位精度的对比情况，如图4(a)-(c)所示.图4(a)是n=7时的精度对比、图4(b)是n=10时的精度对比，可以看出当n=7与n=10的条件下，根据公式(2)的计算方法，发现二次迭代与一次迭代相比较，对于系统定位精度的提高效果并不明显；但在图4(c)n=20时的精度对比图中，15次实验中，二次迭代后的定位精度均小于2，并随着迭代次数的增加，定位精度有较为明显的提高.

因此可知，在动态精度算法中，高差异度指纹的出现概率，随着参考节点数目的增加而增大；算法的迭代效果、定位精度，也随着参考节点数目的增加而提高，图4(d)是参考节点数目n=7、n=10、n=20条件下，算法二次迭代的定位精度效果对比图.

5.2 位置估计误差评估

由上述分析可知，待定位区域面积、初始的静态指纹网格边长固定时，高差异度指纹的出现概率、数目，将随着参考节点数目增加而增大，在动态分割高差异度指纹后，系统的动态精度提高也更为显著.

图4 定位精度对比图Fig.4 Chart of resolution comparing

文献[12]中详细介绍了一种基于弱感知芯片固定部署的室内定位技术—TrackCC，并在文中给出了TrackCC、LANDMARC、SAIL三种定位方法的位置评估误差CDF函数图，其中，基于弱感知芯片的TrackCC，定位误差小于0.5米的概率达到68%，而SAIL小于0.5米的定位误差的约为5%，LANDMARC则约为2.5%.

图5 位置估计误差对比图Fig.5 Chart of error comparing for position estimating

本文的仿真实验中，在参考节点数目n=10、n=20的条件下，待定位区域内随机生成目标节点，分别通过传统的静态指纹库方法、动态精度方法完成目标节点的位置估计，其定位误差的累积概率(CDF)、单个节点定位误差情况，如图5所示.

图5(a)是当参考节点n=10时的位置估计CDF分布图，其中动态精度方法的定位误差小于0.5的概率可达到约20%，定位误差小于1的概率可达到约40%，并且定位误差小于3的概率可达到85%以上.图5(b)是当参考节点数目n=20时的位置估计CDF，动态精度方法的定位误差小于0.5的概率可上升至约40%，定位误差小于1的概率可达到70%以上，并且在定位误差小于2.5时，概率逼近100%.与此同时，在图5(a)、(b)中可以看出静态指纹库方法的定位误差小于0.5米的概率可达到10%左右，定位误差小于1米的概率可达到约20%，而且当参考节点由n=10增加到n=20之后，动态精度定位方法与静态指纹库方法相比较，其定位精度的提升更为显著.

此外，仿真实验中选取了20个随机目标节点，观察单个节点的定位误差精度，如图5(c)、(d)所示.图5(c)为当n=10时的节点位置估计误差对比，图5(d)为n=20时的节点位置估计误差对比.通过单个目标节点采用动态精度法与静态指纹库方法，进行位置估计的单点误差对比，可以看出在参考节点数目n=20时，动态精度法的单个节点定位误差精度，相较于传统的静态指纹库方法，也有显著的提高.

6 结 论

仿真实验表明，在待定位区域面积、初始指纹单元格边长固定的条件下，动态精度的定位效果与参考节点的数目有较为重要的关联，增加参考节点的数目，使得指纹库内高差异度指纹的数目增大，进而提高了动态精度方法的迭代次数和迭代效果，但同时也增加了动态精度指纹库建立阶段的采样耗时.因此，适当的参考节点数目、适当的系统定位精度，对于本算法的应用效果较为重要.如图5所示，本文仿真环境下，当参考节点数目n=20时，动态精度方法获得了较好地定位效果.因此，动态精度的定位方法较静态指纹库方法，更适合弱感知通信芯片作为参考节点，在随机部署的情况，能够获得更高的定位精度.

定位精度是评价室内无线定位系统的主要指标之一.目前，关于低成本、弱感知能力传感器芯片，用于无线定位系统的研究，鲜有动态定位精度的相关文献.文献[12]中基于固定部署的弱感知芯片，提出了一种室内定位技术—TrackCC，虽然获得了较高的定位精度，但其精度并没有动态提高的特性，且芯片部署的人力投入较高.因此，本文提出了一种基于弱感知芯片的动态精度无线定位方法，考虑该类芯片存在的功能限制，通过接收点的最小接收功率建立指纹数据库，利用物理相邻指纹之间的差异程度，记录并重新划分高差异度指纹，构建动态精度指纹库，旨在提高此类传感器芯片，在随机部署的情况下，获得较高地系统定位精度.