一種基于商超WiFi環(huán)境的室內(nèi)定位算法及實現(xiàn)

（中國科學技術(shù)大學，安徽 合肥230088）

一、引言

發(fā)過快遞包裹或者有過線上購物經(jīng)歷的人都了解，快遞信息是可以實時跟蹤的，這是一套復(fù)雜的應(yīng)用系統(tǒng)，其核心技術(shù)在于定位系統(tǒng)。在大型超市購物，通過手機可以實時查到各種商品的擺放位置，甚至能根據(jù)個人喜好收到商超的推薦產(chǎn)品，這種應(yīng)用場景在萬達部分區(qū)域已經(jīng)實現(xiàn)了，其核心點也在于定位技術(shù)。常見的定位方式是通過衛(wèi)星實現(xiàn)的，美國的全球衛(wèi)星定位導(dǎo)航系統(tǒng)（GPS）最為知名，應(yīng)用也最為廣泛。歐洲有伽利略（GALILEO），俄羅斯有格羅納斯（GLONASS），中國有北斗導(dǎo)航衛(wèi)星。但是衛(wèi)星定位具有一定的局限性，在民用領(lǐng)域，衛(wèi)星定位具有首次定位緩慢，定位精度不高，難以逾越障礙物等缺陷。一方面由于受大氣層等影響，信號衰減不一，會有一定誤差；另一方面衛(wèi)星信號易于被遮擋，信號波長難選，波長長了便于繞過障礙物，但是接收信號能力就會降低，波長短了，信號很容易被障礙物遮擋，就收不到信號了。本文通過討論衛(wèi)星定位原理，進而提出一種簡便易行的室內(nèi)定位算法，以期在商超這種特定的區(qū)域內(nèi)實現(xiàn)精準定位。

二、三邊測量（Silent River）原理及衛(wèi)星定位應(yīng)用

常見的定位的算法主要分為兩類，基于測距技術(shù)的定位算法和距離無關(guān)的算法。基于測距技術(shù)的算法一般是通過節(jié)點之間的距離或者角度來計算出未知節(jié)點的位置。距離無關(guān)的算法有，質(zhì)心法、APIT算法、凸規(guī)劃算法等。這些算法都是利用節(jié)點之間的鄰近關(guān)系實現(xiàn)定位的。一般來說，基于測距技術(shù)的算法比無需測距的精度要高，通訊衛(wèi)星一般采用的是基于測距技術(shù)的定位算法。

從幾何的角度來看，已知空間中三個點的位置為坐標 A(x1,y1,z1)，B(x2,y2,z2)，C(x3,y3,z3)和到到 D（x,y,z）的距離d1,d2,d3,求D點的坐標。用下面公式一即可，三個方程求三個未知數(shù)，能求出唯一解。

衛(wèi)星定位原理用的也是三邊測距算法，從原理上來說，只要用三個衛(wèi)星就可以定位一個目標位置了。以個人智能手機為例，大多內(nèi)置輔助全球衛(wèi)星定位系統(tǒng)(A-GPS)，接收各個衛(wèi)星發(fā)送的消息。接收的消息包含兩種主要的信息，一是衛(wèi)星的空間坐標，另一個就是衛(wèi)星發(fā)送的時間。手機在接收到衛(wèi)星發(fā)送消息后，通過比對手機自帶的時間，就可以得出從衛(wèi)星發(fā)送到手機端的時間差，通過這個時間差，就能計算出衛(wèi)星距離手機的距離。通過下面公式看一下：

其中，di是衛(wèi)星到手機的距離，Tm是手機端接收到消息的時間，Ts是衛(wèi)星發(fā)送消息時間，C為光速。

在現(xiàn)實生活中，就存在很多問題，比如手機端時鐘系統(tǒng)有誤差，衛(wèi)星在發(fā)送信息時會收到大氣層氣流的影響，到了地面接收點，會受到建筑物等障礙物的遮擋等。一般為了使得定位更為準確，把這些因素綜合考慮進去，可以給出一個誤差范圍值。事實上，衛(wèi)星定位也是這樣做的。衛(wèi)星到接收終端的距離，就變成了具有修正誤差值的一個概念。把公式二做個簡單的修改：

其中de為估算誤差值。這樣一來，三邊測距的方程公式，就變成了如下公式四：

這樣以來，三顆衛(wèi)星就不能解決問題了，必須有最少有四顆衛(wèi)星才能解決問題。GPS的空間部分是由24顆工作衛(wèi)星組成，它位于距地表20200km的上空，均勻分布在6個軌道面上 (每個軌道面4顆),軌道傾角為55°[1]。這也是GPS每個軌道面有四顆衛(wèi)星的主要原因。

圖2　

在視野比較開闊的地帶，一般終端能接收到大于四顆衛(wèi)星的信號。原理上，有兩種解決辦法：一是，在這些衛(wèi)星中挑選信號最好的四顆按照公式四計算出具體坐標；二是，能接收多少衛(wèi)星消息，就使用多少衛(wèi)星消息數(shù)據(jù)參與計算。公開的數(shù)據(jù)顯示，GPS實際應(yīng)用中，一般采用第二種方式，能在一定程度上提高計算的精度。

三、室內(nèi)定位技術(shù)概述

衛(wèi)星定位已經(jīng)廣泛應(yīng)用于生活中的各個領(lǐng)域。運動導(dǎo)航，軌跡記錄、大地測量、周邊信息查詢等。但是衛(wèi)星定位的局限性和缺陷也比較明顯，由于衛(wèi)星導(dǎo)航需要搜星和進行匹配，首次定位緩慢；衛(wèi)星定位的本質(zhì)是需要依靠授時系統(tǒng)，其精度取決于發(fā)送端和接收端授時系統(tǒng)的精度，往往具有一定的誤差，精度不高；接收端耗電量大也是衛(wèi)星定位很大的一個缺陷；受限于信號波長，難以突破障礙物，因此室內(nèi)衛(wèi)星定位幾乎難以發(fā)揮作用。上文提到的商超應(yīng)用場景無法實現(xiàn)。如何解決封閉空間定位問題[2]，受到了越來越多的學者的關(guān)注，綜合參考多種文獻，大致有以下三種：

1、ZigBee室內(nèi)定位技術(shù)通過若干個待定位的盲節(jié)點和一個已知位置的參考節(jié)點與網(wǎng)關(guān)之間形成組網(wǎng)，每個微小的盲節(jié)點之間相互協(xié)調(diào)通信以實現(xiàn)全部定位[3]。ZigBee具有功耗低，組網(wǎng)能力強，安全性高等優(yōu)點。但是也有顯著的缺陷，布局成本高，通信距離短，一般建議100米以內(nèi)，雖然市面上有開發(fā)出1000米的產(chǎn)品模塊，但是大大增加了功耗，違背了低功耗的基本宗旨，穿透性不好，障礙物厚度嚴重影響通訊距離。

2、UWB由于信號本身的特性，超寬帶信號時間分辨力高，抗室內(nèi)多徑性能強，室內(nèi)定位的精度很高，可到毫米級別，但是UWB系統(tǒng)成本很高，信號本身受到一定的功率限制和頻譜約束，還存在與當前常用頻譜信號之間的干擾問題。

3、RFID射頻識別，成本低廉，但是不具備通信能力，抗干擾差，一般用于倉儲貨物管理。

除了上述的三種應(yīng)用廣泛的技術(shù)外，還有GPS、藍牙、超聲，紅外、Wi-Fi、計算機視覺等室內(nèi)定位技術(shù)，綜合比較，其中以基于WiFi的室內(nèi)定位技術(shù)最為突出，無論從硬件投入、軟件投入、實施難度、可控性，還是定位效果方面考察，都是有優(yōu)勢的。

由于智能終端設(shè)備的廣泛普及，加上各大商超的WiFi布局，基本成了常設(shè)基礎(chǔ)設(shè)施。在商超現(xiàn)有的WiFi基礎(chǔ)上，從衛(wèi)星定位原理發(fā)散思考，基于測距的基本方法，用WiFi代替衛(wèi)星，通過WiFi信號RSSI測距，進而實現(xiàn)室內(nèi)定位，是一種不錯的選擇。一方面可以實現(xiàn)室內(nèi)高精準定位，另一方面在投入成本上也能大幅度降低開支；再次，基于WiFi環(huán)境的室內(nèi)定位能實現(xiàn)封閉區(qū)域的場景營銷，也能解決上文提到的商超購物模擬場景。

四、基于商超WiFi環(huán)境的室內(nèi)定位算法

商超內(nèi)實現(xiàn)購物個性化服務(wù)，離不開兩個要素，基于商超管理的軟件（也可以是APP，本文以APP作為闡述對象），商超內(nèi)基本固定的無線基礎(chǔ)設(shè)施，也就是WiFi環(huán)境。商超APP在請求定位的時候，會需要WiFi信號。商超客戶在使用手機時，會探測到周圍各個WiFi，包含兩個信息維度，一個是WiFi的標識（從實踐來看，具有WiFi唯一標識度的，就是物理地址，又稱MAC地址），一個是WiFi的信號強度（RSSI）[4]。這樣各個 WiFi就構(gòu)成了一個信號向量 （＜M1，R1＞＜M2，R3＞＜M3，R3＞...＜Mn，Rn＞）。服務(wù)端收到客戶端請求后，會將信號向量傳遞給定位引擎，定位引擎結(jié)合這些信息返回給服務(wù)端定位結(jié)果，定位精度等信息，服務(wù)端再將結(jié)果返回給APP。這里定位引擎起到了關(guān)鍵作用。定位引擎的工作，決定了定位的精度，取決于兩個方面，一個是大量的位置信號向量數(shù)據(jù)，另一個方面是采用的算法模型。本文重點討論算法模型。其過程如下：

圖3　

實現(xiàn)商超內(nèi)客戶精準定位的問題轉(zhuǎn)化為在大量的位置信號信息中，找到一個點D，使得這個位置盡可能的精確。這也是數(shù)學模型中的概率論問題。這個適用于貝葉斯定理。已知給定信號向量m（＜M1，R1＞＜M2，R3＞＜M3，R3＞...＜Mn，Rn＞），求解一個點D，是這種可能性最大，公式如下：

這個公式直接求解的難度很大，通過貝葉斯轉(zhuǎn)化一下,如公式六：

分母D(m)標識D在信號向量m中出現(xiàn)的概率，對于商超用戶來說，這個是毋庸置疑的，可以忽略不計。那么該貝葉斯公式就可以轉(zhuǎn)化為：

其中D(d)表示位置D出現(xiàn)的概率，D(m|d)表示在位置D出現(xiàn)信號向量m的概率。由于商超環(huán)境相比室外環(huán)境先對比較單一，為了簡化起見，這里假設(shè)位置D出現(xiàn)的概率均等。那么公式七就可以轉(zhuǎn)化為如下公式八：

Max(D(m|d))指的是在商超空間里找到一個點D，使得信號向量m出現(xiàn)的概率最大。由于商超空間有限，做到這點很容易。關(guān)于WiFi的物理位置，由于是商超環(huán)境，范圍太小，加之無法找到足夠精度的參考點，所以WiFi的物理位置無法使用GPS坐標，只能使用自定義坐標系，這里有2種選擇：

1、以商超內(nèi)的某一個點為參考原點，這樣就可以人工測量WiFi相對原點的坐標，包含Z軸，單位是米，甚至可以更小為厘米。

2、以商超的建筑設(shè)計測繪圖為參考，以WiFi在圖中的像素位置為坐標，單位是1像素點。

第二種方法相對簡便一些，通過電腦就可以實現(xiàn)，無需增加很大的工程量。在模擬測試中，采用的就是第二種方法。

圖4　

因此max（D(m|d)）就轉(zhuǎn)換為在地理空間找到一個像素點，使得信號向量m出現(xiàn)的概率最大。在商超內(nèi)，由于各個WiFi信號獨立，那么公式八可以轉(zhuǎn)換為：

現(xiàn)在問題關(guān)鍵是求解D(wfi＝RSSIi|d)，即在網(wǎng)格d內(nèi)，mac地址為Mi且信號強度為Ri出現(xiàn)的概率。這樣就可以實現(xiàn)精準的定位了。

利用這種樸素貝葉斯算法的難點在于計算精度上，一方面定位的精度取決于WiFi的個數(shù)，WiFi信號的穩(wěn)定程度；另一方面取決于區(qū)域面積大小，理論上用戶來一個請求，需要遍歷信號位置數(shù)據(jù)庫每個像素點對應(yīng)的概率，并將最大概率網(wǎng)格對應(yīng)的中心點返回[5]。如果是大范圍的應(yīng)用，比如一個城市，一個小區(qū)，哪怕是精確到米級別，計算量都將是海量的。但在商超環(huán)境下，由于采用了固定的測繪圖像素分割辦法，這種計算的工作量很小。計算效率很高，基本可以實現(xiàn)精確度很高的定位。

五、基于商超WiFi環(huán)境的室內(nèi)定位需要解決的問題

首先要建立一個基于商超WiFi環(huán)境的位置信號數(shù)據(jù)庫,至少需要如下信息，WIFI的MAC地址，也就是標識,WIFI的物理位置 （基于區(qū)域劃分的坐標位置）,WIFI的信號強度信息。

用一個簡單的程序?qū)崿F(xiàn)如下：

其次，上述數(shù)據(jù)庫的建立，有個先決條件就是將商超物理地址網(wǎng)格化，由于地理位置空間有限，這里采用了利用建筑測繪圖像素化的處理方法。

再次是選擇定位算法選擇，通過上文的討論，利用樸素貝葉斯模型，可以在給定商超環(huán)境下實現(xiàn)精準的室內(nèi)定位。

六、總結(jié)

室內(nèi)定位技術(shù)的成為目前研究的熱點，尤其實在電子商務(wù)應(yīng)用領(lǐng)域，各種基于室內(nèi)定位技術(shù)的應(yīng)用不斷涌現(xiàn)。在大型商超里借助室內(nèi)導(dǎo)航軟件，可以迅速的找到自己心儀的產(chǎn)品；商超管理者根據(jù)室內(nèi)定位的具體位置，可以推送個性化的商品組合等等。甚至在大型商超里購物不用擔心走丟這樣尷尬的事情發(fā)生。這些應(yīng)用服務(wù)于特定范圍的消費者，將會極大提高用戶的購物體驗。雖然商用的室內(nèi)定位技術(shù)已經(jīng)出現(xiàn)了很多，但是尋求一種成本低廉，部署方便，精準度較高的室內(nèi)定位技術(shù)將仍然是一項非常有意義的工作。