一种基于多用户协同计算的室内定位方法研究

何荣毅 王小群 王 宁

1(山东大学网络与信息管理中心 山东 威海 264209) 2(郑州大学信息工程学院 河南 郑州 450001)

0 引 言

精确的室内位置和设备的运动信息为定位服务[1]和新兴的个性化运动监测应用提供了许多契机。诸如用户室内向导、定位购物中心内的各类服务点，或者追踪用户每日步行和上楼梯次数，以便了解其日常锻炼情况。设备对定位信息的精准计算使此类服务成为可能。目前，在没有昂贵的设备或复杂的基础设施支持的建筑物内，准确地获得室内位置信息仍然是一个挑战[2]。

传统的室内定位方法可以分为两类。(1) 设备辅助法。部署特定的基础设施或要求用户携带特定的设备，以获得准确的定位结果。例如，基于蓝牙信号强度的定位系统[3]、超声波定位系统Cricket[4-5]、基于无线射频识别的定位系统[6-7]等。该类方法通常具有很高的精度，但是它们的成本很高，而且在很多应用环境中的部署难度较大。(2) 免设备定位方法[8-10]。用户不需要额外的设备，通常使用指纹算法(或其他机器学习技术)来训练所在环境中的离线信号强度来获得理想的位置精度。该类方法降低了定位的成本，但无需设备的室内定位的准确性取决于训练数据的大小，而数据收集和训练是复杂而耗时的。

目前，智能手机或平板电脑都配备了加速度计、回转仪、旋转矢量和方向传感器等多种传感器，以及可以检测运动和预测位置的多种类型的无线电。智能手机上的航位推算应用程序[11-12]被广泛应用于对移动人员的跟踪或在室内环境中进行人员定位。航位推算可以通过使用先前确定的位置来计算一个人的当前位置。而航位推算所需的参数可通过智能手机上的加速度计和方向传感器获得。因此，航位推算的性能取决于这些传感器的测量精度。目前来看，智能手机的定位应用仍然不够精确。例如，UM6[13]是一种用于定位的常用传感器，在其应用中，定向估计的小误差会导致计算位置的严重偏差。方位传感器只需出现0.5度的误差，在1 min之内就会造成308 m的误差。

为此，本文提出了一种基于多用户协同计算的室内定位方法(ILM-MUCC)。针对传统的航位推算方法的不足，利用多个智能手机交互的机会来提高定位准确性。每个智能手机计算自己的位置，然后与附近的智能手机共享。此外，智能手机使用多个无线电的信号强度来估计设备之间的距离，随着信息共享和位置计算的多次迭代，极大地提供了室内定位的精度。最后的室内仿真实验也验证了本文方法的有效性。

1 系统设计

1.1 系统概述

本文提出的ILM-MUCC方法的总体架构如图1所示。

图1 本文方法的框架图

ILM-MUCC方法在用户的移动设备上有两种工作机制：(1) 周期性地测量用户移动设备上的加速度计，模拟用户的行走模式，并通过航位推算来计算用户的位置；(2) 当用户遇到其他用户时，ILM-MUCC会周期性地向附近其他用户发送蓝牙、Zigbee和WiFi信号。移动终端通过获得来自其他检测设备的接收信号强度(RSSI)值，分析每个时段的RSSI的变化来进行航位推算。由于WiFi信号对干扰比较敏感，如果WiFi接收信号强度的变化超过门限，则认为此时间段内收到的接收信号强度值因干扰而无效，此时使用历史数据重新计算。

对于室内定位而言，面临的主要挑战是如何在无需任何额外设备的情况下使用RSSI值来帮助用户准确定位自己。在ILM-MUCC方法中，用户通过检测到的设备获得接收信号强度后，可利用接收信号强度与欧几里德距离的映射关系来估计这些设备之间的距离。这些不同移动设备之间的关系是在离线状态下训练的，可以在云端进行访问。在获得每一对设备之间的距离之后，被检测范围内的所有设备形成三角形或多边形。每个顶点的初始位置由航位推算生成，用户通过使用到其他设备的距离以及其他设备之间的位置关系来计算自己的位置。通过迭代，所估计的位置的误差可以有效地降低。此外，ILM-MUCC还设计了一个计算用户行走步数的模型，以减少智能手机上常见的计步器错误。最后需要指出的是，ILM-MUCC是一个轻量级的应用程序，它将参与定位的移动设备看作一个多边形，然后将多边形分解为三角形来进行定位计算，计算用户的设备位置的过程部署在云服务器上，而不是在移动设备上运行。

1.2 航位推算

在移动设备中，加速器是一种适合用户活动识别的惯性传感器，移动设备周期性地在彼此正交的三个轴上检测可获得用户活动的加速度。假设每个时间段的时间长度为1 s，加速度的计算公式如下：

(1)

式中：g指地球引力，ax、ay和az是在Ox、Oy和Oz三个轴上检测到的加速度。利用在每个周期中获得的加速度，移动设备在时间段n中的移动距离也可基于式(1)计算得到。vn-1和an-1指前一时间段的速度和加速度；tn指当前时段的时间长度；Sn指当前时期的移动距离向量。如图2所示，如果智能手机上的应用程序通过式(1)连续计算每个时间段的移动距离，则可以获得移动设备的整个轨迹。

图2 航位推算方法

1.3 距离和接收信号强度(RSSI)

在大多数移动设备上可以轻易地收集到接收信号强度。尽管RSSI值经常因干扰和路径损耗而变化，但是从其他设备获得的接收信号强度值与设备之间的距离高度相关。较短的距离往往代表更强的接收信号强度。在ILM-MUCC中，通过收集表示各类型广泛应用的移动设备的距离和接收信号强度值的数据来建立接收信号强度-距离映射关系。

RSSI可从蓝牙适配器获得，例如，当华为Mate10智能手机与华为MateBook X平板电脑之间的距离在空房间中为5 m时，则接收信号强度一般为-66 dBm。接收信号强度-距离映射关系的训练不考虑干扰等因素对接收信号强度值的影响，这些噪声和例外情况将由WiFi过滤器处理。由此得到的映射关系将存储在云服务器上的数据库中。另外，虽然训练映射关系需要一定的人工和时间成本，但由于我们所采用的移动设备的类型较为普遍，所获得的映射关系可以服务于普通的基于Android的移动设备。

1.4 三角计算定位

1) 三角形计算模型 在ILM-MUCC中，三角形计算的目的是通过了解其他检测设备的位置和接收信号强度值来定位用户的位置。如图3所示，三个用户(Alice、Bob和Carson)持有具有蓝牙适配器的移动设备。在每个时期，假设他们形成一个三角形。打开蓝牙选项后，每个用户都会收到其他两个用户的接收信号强度值。然后用距离-接收信号强度映射关系得到三角形三边的长度。如果Alice希望找到自己，在她知道Bob和Carson的位置的情况下(Bob和Carson的位置通过航位推算方法计算得到，当他们相遇时会发送给Alice)，Alice的位置可以通过式(2)计算得到。其中，(xa,ya)表示设备a在二维平面上的位置；AB和AC分别表示Alice和Bob，以及Alice和Carson之间的距离。在本文中，由于蓝牙检测的范围是10 m，所以在一个三角形中每条边的上限是10 m。

(2)

图3 三角形模型

然而，航位推算方法有时不足以提供令人满意的位置信息，如图4所示。假设三角形ABC上的顶点指的是三位用户的真实位置。三位用户使用航位推算方法来预估他们的初始位置，并且这种预估并不准确。预估的位置为是A′B′和C′，A和A′，B和B′，以及C和C′之间的距离是2 m。Alice通过三角计算可得到Bob和Carson的接收信号强度值，利用接收信号强度-距离映射关系，可以得到Bob和Carson的估计距离。

图4 三角校准示例

然后，通过计算出的两个距离(AB′和AC′以及B′和C′(B′C′)之间的距离)，我们可以计算A′的估计位置A″，即由式(1)计算出A的估计位置。与A′相比，A与A″更接近，我们也可以计算B′和C‴的位置，因此，新形成的三角形A“B”C“能够减少距离航位推算造成的错误。

2) 从三角形到多边形的扩展 基于上述包含三个用户的例子，Alice可以通过三角形计算获得自己的位置。在实际情况中，房间或走廊中可能有三台以上的设备。如同以上示例所述，如果David进入房间，那么就可以形成一个四边形。用户设备可以被视为四边形的顶点。那么，在包含顶点Alice的四边形中有三个三角形即三角形ABC、ABD、ACD，如图5所示。将Alice的新位置定义为从三个三角形估计的Alice位置的平均值：

xa=(xa(abc)+xa(abd)+xa(acd))/3

y=(ya(abc)+ya(abd)+ya(acd))/3

(3)

式中：xa(abc)和ya(abc)是由三角形ABC计算出的Alice的x和y值。如果房间包含4个以上的设备，则所有的设备都可以被抽象为多边形的顶点。对于每个设备，我们可以使用多边形中的三角形来进行定位。然后，通过计算从不同三角形获得的位置的平均值，设备的用户可以准确地计算得到自身位置。如果一个用户在一个具有更多的移动设备的环境中并形成更复杂的多边形，则定位结果会更准确。

图5 将四边形分解成三角形

1.5 WiFi滤波器

大多数智能手机和平板电脑都支持蓝牙和WiFi。蓝牙RSSI值不仅对干扰敏感，而且对两个侦测设备之间的距离也很敏感。蓝牙RSSI值通常在10 m范围内从最大值到最小值变化。距离越短，则其RSSI值越大。WiFi接收信号强度值对发送者和接收者之间的人体或墙壁等干扰较为敏感，但对于大多数为移动设备提供WiFi的无线路由器来说，在1～10 m之间的距离内，WiFi接收信号强度值变化不大。蓝牙适配器使用扫描和查询程序进行操作。目前的移动设备通常需要5～15 s的操作时间。因此，蓝牙RSSI的采样频率是有限的。在移动设备快速移动的情况下，用户可能会失去记录蓝牙RSSI值的机会。为此，本文引入了Zigbee协议中的接收信号强度。Zigbee的接收信号强度的特性与蓝牙接收信号强度相似，但Zigbee不需要进行长时间的扫描和连接其他设备。另外，Zigbee可以由编程器设置信号强度的采样频率(1 Hz或0.5 Hz)作为常用的接收信号强度采样频率。

众所周知，RSSI在室内环境中表现差强人意。RSSI值的一些变化可能会导致接收信号强度距离-映射关系错误。例如，如果有移动物体位于两个Zigbee(或蓝牙适配器)之间，则RSSI的接收值将降低。此时如果在训练数据集中使用接收信号强度距离-映射，相应的距离将会增加。因此，我们需要过滤这个干扰(噪声)。如前所述，尽管WiFi对距离不敏感，但它对干扰十分敏感。为此，本文设计了WiFi滤波器算法减少干扰对定位的影响，如算法1所示。

算法1WiFi滤波器算法

输入：从蓝牙、Zigbee和WiFi适配器收集的接收信号强度样本，WiFi滤波器的阈值

输出：蓝牙和Zigbee中经过过滤的接收信号强度值

1：for i=1;i<周期数;执行一次循环体

2：if WiFi接收信号强度值变幅>阈值，那么

3： //找到最近一个周期的无线传感器网络值

4： 调用WiFi滤波器(i-1);

5： //替换NP中的异常接收信号强度值

6. for j=1;j

8： end for

9： for k=1;k<周期i(nz)中的Zigbee样本数；执行k++

11. end for

12 else

13 返回BluetoothRSSI[i][nb];

14. 返回ZigbeeRSSI[i][nz];

15. end for

由于用户的移动一般不会突然发生改变，如果接收到的WiFi接收信号强度每10 s变化超过5 dBm，则认为接收信号强度的这种明显变化是由干扰造成的。在算法1中，我们将10 s时间段定义为“噪声时期(NP)”，并采用了最近时间段中的一个非NP的接收信号强度值代替NP中的接收信号强度值。如图6所示，当WiFi信号在两个NP(116～119 s，166～169 s)处遇到干扰时，接收信号强度值急剧下降。在使用WiFi滤波器来检测NP之后，蓝牙和Zigbee的噪声样本被在先前最近的时间段中的平均接收信号强度值校正。在大多数室内场景中，人们通过无线路由器接收WiFi信号。但是，一些室内环境没有这样的基础设施，WiFi直连是大多数主流移动设备(如iPhone、iPad和Android智能手机)采用的WiFi标准。这种技术使设备能够彼此连接而不需要无线接入点，例如无线路由器。每个智能手机/平板电脑都可以打开WiFi直连选项，这意味着每个移动设备都可以通过WiFi检测到其他设备，并从这些设备获取接收信号强度值。如果WiFi直连获得的WiFi值急剧变化，也可以看成是NP，并由WiFi滤波器处理。

图6 WiFi滤波器

1.6 组合算法：三角形计算与航位推算

尽管三角形计算与实际数据十分接近，但仍然存在由映射引起的误差。事实上，航位推测的误差是由加速度计的变化引起的。再加上预测误差的范围有一定困难，因此，理想的情况是在每个时间段从两种方法中选择更好的定位结果。为了实现这一目标，文中定义以下两个事件来指示航位推算方法何时不可靠：

事件1：在某个时间段i内，与前一时间段i-1相比，加速度计急剧变化，ax或ay或az变化超过1 m/s2。

事件2：在某个时间段i内，与前一时间段i-1相比，移动设备的位置急剧变化，x或y的变化超过5 m。

当WiFi滤波器检测到噪声周期时，三角形计算方法不可靠。为此，提出了一种基于航位推算和三角计算的组合算法来实现室内定位，如算法2所示。

算法2组合算法

输入：用户通过航位推算法和三角形计算出在时间段i的位置：(xi,yi)d，(xi,yi)t

输出：在时间段i的组合位置结果：(xi,yi)c

1：while在每个时间段i do

2： if 时间段i是噪声时段(NP)，then

3： 调用WiFi滤波器(i);

4： 用更新的BluetoothRSSI[i][nb]和ZigbeeRSSI[i][nz]重新计算(xi,yi)t

5： else

6： (xi,yi)c=(xi,yi)d

7： if 事件1或事件2 then

8： (xi,yi)c=(xi,yi)t

9： end if

10： end if

11：返回(xi,yi)c

12：end while

1.7 步数计算

利用智能手机上的步数计数器可以计算步数。然而，大多数计步器是非常不准确的[14]。一个直观的原因就是智能手机上集成的计步器依赖于加速度计。由于智能手机上的加速度计值并不等于人体的加速度，很难在人体行走模式中无误地识别加速度。不同的人有不同的跨步长度，要启用ILM-MUCC来计算步数，有必要估计每个用户的步长，步长dk的计算模型如式(3)所示。其中，fk表示在短训练周期k内可手动计数的步进频率，其最小时间长度设置为20 s。式(3)属于线性模型，为了估计其中的参数a和b，我们征集了七组志愿者来进行训练，分析了他们的平均步频与平均步长的关系(见图7)，采用最小二乘法来进行参数拟合，通过进行轻量级的训练阶段，用户可以得到自己的步长，从而计算步数，见式(4)。最后，通过添加在每个时间段中记录的步数，用户可以确定他们总共走过的步数。

dk=a×fk+b

(3)

(4)

图7 步长与步频之间的关系

2 仿真实验

2.1 实验设置

本文在基于Android的移动设备上构建了一个ILM-MUCC原型。在每个设备的模拟实验中，我们将蓝牙、Zigbee和WiFi直连滤波器结合起来进行三角形计算。由于Android OS不支持Zigbee模式，我们通过共享时间标记同步记录Zigbee和蓝牙数据。Zigbee和WiFi直连采样频率分别为1 Hz和0.25 Hz。蓝牙接收信号强度的采样频率为0.1～0.2 Hz。对于每个数据样本，在接收到经过训练的映射关系转换后的蓝牙和Zigbee接收信号强度值之后，我们可以确定每对设备之间的距离。在评估中引入了两个度量标准：1) 距离误差，表示实际位置与估计位置之间的距离(单位为m)。2) 累积步数的误差，表示第三方应用程序与ILM-MUCC之间计算的步数不同。

主要分析和讨论如下的四个问题：1) 本文方法是否有助于改善移动设备在不同环境中的定位精度？2) 本文方法是否可以有效地计算用户的步行步数？ 3) Zigbee模型和WiFi滤波器如何协助蓝牙模型？ 4) 对于一个用户来说，遇到更多也使用ILM-MUCC的用户是否有助于她/他提高自己的定位准确性？

2.2 不同情景下的定位精度分析

如图8所示，我们在本校的某一教学大楼的一个房间里进行了45 min的实验，实验重复200次。在实验中三个用户携带移动设备并自由行走。所有人都使用ILM-MUCC并经常与他人互动。如图8(b)所示，X轴为实验时间，Y轴为用户A的距离误差。不同灰度曲线分别为航位推算法、三角形计算法和组合算法的距离误差。图9所示为我们在走廊中进行的类似实验。从这两类实验可以看到，三角形计算的组合方法效果最好，航位推算的平均偏差可减少到0.5 m。

图8 室内试验

图9 走廊试验

在模拟航位推算方法时，文中采用式(1)定期从智能手机上的加速度计获取加速度值。然后，在x,y,z轴上引入随机的加速度误差，误差范围从-1 m/s2到1 m/s2。对于三角形计算，我们随机地为三角形的每一边添加-10到10的百分比的距离误差。每个实验组的时间从45 min减少到1 000 s。如图8(c)和图9(c)所示，在一个特定的时间点，每一行的数据样本是指在50次模拟中获得的距离误差的平均值，每行的阴影是计算值的置信区间。这两个数字表明，经过多次模拟，组合算法比航位推算和三角形计算具有更准确的定位结果，误差范围可被限定为1 m以内。

我们将实验从单一的区域扩展到具有多个房间和走廊的室内建筑：用户携带移动设备四处行走，并同时与其他设备进行通信。所有设备都安装并运行ILM-MUCC。如图10所示，虚线表示用户进入另一房间时的时间点。例如，在第50 s，用户离开房间进入走廊。组合算法的定位结果比其他两种方法更准确(特别是航位推算方法)。使用ILM-MUCC的定位误差仍在1 m以内。

图10 在复杂的室内环境中进行ILM-MUCC测量

此外，图11给出了ILM-MUCC方法与目前两款流行的计步器应用程序[15](Noom Walk，ACCUPEDO)的步数误差比较情况。从图中可以看到，随着用户行走时间的增加，Noom Walk和ACCUPEDO的步数误差数量呈线性增长，而ILM-MUCC在整个过程中比其他两个计步器的误差更少，且步数误差数量的增长趋势较为平缓，这表明ILM-MUCC方法的鲁棒性更高。

图11 三个应用程序的累计步数误差比较

2.3 不同的移动设备数量下的定位精度分析

下面讨论用户接触到的移动设备数量是否会影响定位精度。首先，假设Alice携带智能手机，并于500 s内在一个房间内自由行走。然后，通过应用ILM-MUCC，其他人的存在可以帮助Alice定位她自己。实验中设置了两个控制组：1) 组中包括Bob和Carson，他们将帮助Alice应用三角形计算；2) 组中包括Bob、Carson和David，他们使用“多边形分解”做三角形计算。从图12(a)可以看到，当用户接触到的移动设备数量越多，则定位的精度就越高。为了进一步支持以上结论，我们进行了更复杂的实验：ILM-MUCC的用户在室内建筑物中自由行走。在该过程中，会产生三种轨迹：1) 用户没有遇到任何其他用户(用户的位置通过航位推算得到)。2) 用户一直维持有其他两个用户协助他通过组合方法来定位自己。3) 用户一直维持有三到四位其他用户帮助他定位自己。实验结果见图12(b)，从中可以看到，轨迹1仅由航位推算法获得，该结果通常与地面真实情况有严重偏差(大约3 m)。轨迹3采用了组合方法，并且在过程中有更多的用户来辅助定位，该痕迹体现出了极佳性能。基于以上评估，如果所有用户都在自己的移动设备上运行ILM-MUCC，则每个用户的定位精度都可以提高，从而让更多的人获得极佳的定位性能。

(a) 遇到的不同数量的设备

(b) 控制组比较 图12 移动设备数量VS定位精度

2.4 WiFi滤波器的阈值

WiFi滤波器的阈值选取是关键因素。如果将P设置为滤波阈值，就会导致接收信号强度变化值的干扰小于P，从而干扰将被忽略。如果将WiFi滤波器的阈值设置得太低，则会将接收信号强度值的正常变化判断为干扰。基于华为Mate10智能手机和Google Nexus 7智能手机，我们在教学大楼的一个房间中运用了我们的方法，并按照实验设置所述进行实验，测试了不同的WiFi滤波器阈值下WiFi滤波器检测的成功率如表1所示。其中，实际干扰指实验中产生干扰的次数；检测干扰指WiFi滤波器检测到干扰的次数；错判干扰指发生干扰的误报数量。从表1中可以看到，当阈值等于5 dBm时，ILM-MUCC方法的表现最好。

表1 WiFi滤波器阈值

2.5 复杂性分析

最后，对ILM-MUCC方法的复杂性进行了分析。对于最坏的情况，假设所有设备都在蓝牙适配器(或无线传感器网络基站)的可达范围内，即应在每个移动设备之间建立连接。如果系统包含n个设备，则系统的复杂度为O(n2)。对于最理想的情况，用户只能访问蓝牙适配器(或Zigbee基站)的不同范围内的其他人，系统的复杂度为O(n)。因此，ILM-MUCC方法的复杂性在可接受的范围内，即使设备数量不是很少，我们也可以在大多数情况下应用它。

3 结 语

提出了一种基于多用户协同计算的室内定位方法(ILM-MUCC)。在ILM-MUCC中，我们建立了不同移动设备的接收信号强度和距离之间的关系，并使用几何计算来减少航位推算造成的误差。实验结果表明，如果一个行走的用户携带移动设备并在建筑物中使用ILM-MUCC，并且他/她遇到了同样使用ILM-MUCC的其他用户，则定位结果将会更加准确，误差范围可控制在1 m以内。我们将Zigbee的接收信号强度值与从蓝牙获得的接收信号强度相结合，以收集更多的样本，并辅助使用基于WiFi的滤波器，这两种技术都提高了室内定位精度。此外，利用已知的位置信息，ILM-MUCC可以计算步行者的步数，并有效克服了基于智能手机的计步器引起的常见错误。在以后的工作中，我们将对设备差异性造成的WiFi信号强度不确定问题做进一步研究，拟提出一种基于K最近邻的位置指纹室内定位方法。