一種基于多用戶協同計算的室內定位方法研究

何榮毅 王小群 王 寧

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最近鄰的位置指紋室內定位方法。