一種基于綜合空間位置索引模型的移動位置計算方法

孔勇平，張玉良，鐘致民，楊廣龍

（中國電信股份有限公司廣州研究院 廣州510630）

1 引言

隨著移動互聯(lián)網(wǎng)的快速發(fā)展，位置成為移動互聯(lián)網(wǎng)業(yè)務(wù)的重要需求，是移動互聯(lián)網(wǎng)的基礎(chǔ)技術(shù)和核心概念。各類移動互聯(lián)網(wǎng)應(yīng)用大多已成為了廣義上的基于位置的服務(wù)（location based service，LBS），應(yīng)用通過使用位置信息，可為用戶提供更好的體驗、拓展新的業(yè)務(wù)模式等。如何獲取或感知移動用戶的位置，是移動互聯(lián)網(wǎng)業(yè)務(wù)應(yīng)用需要解決的首要問題之一。

目前，GPS（global positioning system，全球定位系統(tǒng)）芯片已經(jīng)逐步成為智能移動終端的標(biāo)準(zhǔn)配置，用戶可以通過GPS很方便地獲取其所在的位置。雖然GPS服務(wù)免費、定位精度較高，但是GPS定位卻存在以下兩個重要缺陷，限制了其應(yīng)用范圍：一是GPS耗電量較大，一般手機持續(xù)打開GPS定位時，電池只能堅持使用幾個小時；二是GPS對定位環(huán)境要求較高，在定位衛(wèi)星被遮蔽的情況下不能定位，不具有環(huán)境的普適性。為了解決GPS定位的不足，后來逐步發(fā)展了基于無線網(wǎng)絡(luò)的定位技術(shù)，即通過無線網(wǎng)絡(luò)來確定移動用戶的位置。移動網(wǎng)絡(luò)定位技術(shù)的基本原理是通過移動用戶接收的基站、Wi-Fi等信號的設(shè)備位置來計算移動用戶的位置，其定位誤差和基站或Wi-Fi設(shè)備的分布相關(guān)，一般在100～5 000 m。

在各類實際的應(yīng)用環(huán)境中，位置的概念和需求是有區(qū)別的，位置不只是一個具有高精度的物理位置坐標(biāo)，而與用戶的行為、目標(biāo)和所在環(huán)境緊密相關(guān)。例如：在高速公路、風(fēng)景區(qū)等地方，在GPS定位受限時，由于基站或Wi-Fi的分布比較稀疏，而且往往只有1個服務(wù)基站信號覆蓋，缺乏三角定位所需的足夠多的基站信息，因此定位精度常常較低，只能確定用戶所在的幾百米到幾公里的區(qū)域，用戶體驗不好。因此，本文提出了一種適合移動互聯(lián)網(wǎng)應(yīng)用的基于綜合空間位置索引模型的移動位置計算方法。

2 位置索引

2.1 移動互聯(lián)網(wǎng)應(yīng)用對位置的需求

在不同的移動互聯(lián)網(wǎng)應(yīng)用中，用戶對定位精度的需求是有差別的。例如在“周邊搜”應(yīng)用中，用戶的需求是能夠查找周邊的商場、餐館、酒店等POI（point of interesting，興趣點）信息，對位置的精度要求不是特別高，一般誤差在幾百米之內(nèi)即能夠滿足用戶需求；而在“步行導(dǎo)航”這種應(yīng)用中，則必須知道準(zhǔn)確的起點、終點以及步行過程中的精確位置，以此來計算“步行”路徑，實現(xiàn)精確導(dǎo)航，這種應(yīng)用場景對位置的精度要求較高。定位服務(wù)的覆蓋應(yīng)該是連續(xù)的，即不論用戶處于何種環(huán)境下（至少具備使用數(shù)據(jù)網(wǎng)絡(luò)的條件），均可使用相應(yīng)的服務(wù)。通過識別用戶所處的不同場景，并以合理的代價提供滿足應(yīng)用精度要求的位置信息具有現(xiàn)實的意義。

移動互聯(lián)網(wǎng)應(yīng)用在定位（非GPS定位）時，主要依賴周邊的基站、Wi-Fi等無線信號，但是由于受周邊環(huán)境的影響，無線信號在傳輸過程中會發(fā)生折射、反射、多路徑傳輸現(xiàn)象，使得這些無線信號具有很大的隨機性，導(dǎo)致定位結(jié)果有較大的誤差。一般情況下，在基站和Wi-Fi信號覆蓋的交疊區(qū)域會發(fā)生嚴重的小區(qū)域信號漲落現(xiàn)象，移動終端接收到的基站或Wi-Fi信號會頻繁切換，導(dǎo)致終端接收的無線信號處在一個動態(tài)變化過程中，體現(xiàn)在移動互聯(lián)網(wǎng)應(yīng)用中是出現(xiàn)位置的“跳躍”。例如當(dāng)用戶在連續(xù)定位過程中，即使用戶位置還未發(fā)生較大的變化，但是受無線參數(shù)隨機性變化的影響，也將導(dǎo)致定位結(jié)果相差較大，出現(xiàn)定位結(jié)果隨機“跳躍”的現(xiàn)象。因此，需要尋找一種相對更合理穩(wěn)定的定位方法，使定位結(jié)果盡可能趨于穩(wěn)定，避免“跳躍”。

基于以上兩種情況，可以通過對一個“小區(qū)域”位置建立多種位置索引描述的方法，計算位置信息。位置索引既能夠滿足不同應(yīng)用對位置精度的需求，又能夠保證在部分參數(shù)發(fā)生隨機變化的情況下，通過參數(shù)之間的相關(guān)性，計算出比較準(zhǔn)確的結(jié)果，避免出現(xiàn)較大的跳躍。

2.2 移動互聯(lián)網(wǎng)應(yīng)用中位置的定義

狹義的位置（location）指的是地理上的一個物理坐標(biāo)或區(qū)域，一般采用經(jīng)緯度坐標(biāo)（longitude,latitude）來表示。在移動互聯(lián)網(wǎng)中，基于無線網(wǎng)絡(luò)的定位方法是通過基站、Wi-Fi等無線信號運算獲得位置信息的。由于基站、Wi-Fi等無線信號具有一定的覆蓋區(qū)域，而并不是一個準(zhǔn)確的點位置，因此定位結(jié)果往往采用基站或Wi-Fi的中心點坐標(biāo)和信號覆蓋半徑來表示其位置，本文采用P（X,Y,R）來表示。其中，X表示經(jīng)度，Y表示緯度，R表示信號覆蓋半徑（即誤差范圍，單位是m）。

由于用戶的位置與其生活環(huán)境是緊密相關(guān)的，因此用戶的生活環(huán)境對用戶的位置具有很大的約束作用。例如，在城市內(nèi)，道路、商業(yè)中心、寫字樓、廣場和生活小區(qū)等一般是人們的活動區(qū)域，人們一般不會出現(xiàn)在河道、綠地和湖面等區(qū)域；在城市外，旅游景點、道路和鄉(xiāng)村居民點等一般是人們的活動區(qū)域，而農(nóng)田和山坡等一般不是人們的主要活動區(qū)域（在田地中勞作一般不是移動互聯(lián)網(wǎng)應(yīng)用的使用場景）?；驹谑袇^(qū)的覆蓋范圍在幾百米到1 000 m，Wi-Fi的覆蓋范圍在300 m以內(nèi)。單純以基站和Wi-Fi的位置來確定用戶位置，很難滿足用戶對位置合理性的要求，因此需要結(jié)合用戶活動的路網(wǎng)和周邊POI等信息進一步提高用戶位置的合理性和精準(zhǔn)度。

基于以上對移動互聯(lián)網(wǎng)應(yīng)用位置的定義分析，本文采用基站、Wi-Fi、道路和POI作為索引確定一個位置，并采用一個四元組來表示：

其中，C表示移動通信基 站，W表示W(wǎng)i-Fi熱點，R表示道路，P表示POI。

2.3 綜合位置索引

本文中采用四元組來表示一個位置，這個位置不是一個最終確定的地理坐標(biāo)，而是一個小區(qū)域位置描述的綜合空間索引。在位置四元組中，每一個元素代表一類數(shù)據(jù)對象，C代表的是移動網(wǎng)絡(luò)通信基站數(shù)據(jù)對象，W代表Wi-Fi熱點數(shù)據(jù)對象，R代表道路數(shù)據(jù)對象，P代表的是POI數(shù)據(jù)對象。每一個對象包含多種屬性定義，其詳細定義如下。

C：基站編號（CID）、基站坐標(biāo)（X,Y）、覆蓋半徑（R）；

W：Wi-Fi地址（MAC）、覆蓋半徑（R）；

R：道路編號（RID）、名稱、城市區(qū)位碼、寬度、等級、道路坐標(biāo)串（X1,Y1;X2,Y2;…;Xn,Yn）；

P：POI編號（PID）、名稱、城市區(qū)位碼、類型、坐標(biāo)（X,Y）。

在以上4類位置索引數(shù)據(jù)對象中，每一類數(shù)據(jù)對象都有確定的地理坐標(biāo)，能夠確定一個具體的地理位置，但是，其在定位技術(shù)實現(xiàn)中的意義和使用是完全不同的?；拘盘柡蚖i-Fi信號是移動終端能夠獲得的無線參數(shù)，既是移動終端與環(huán)境交互的媒介，也是計算移動終端理論位置的基礎(chǔ)信息；道路和POI是對環(huán)境的描述，能夠更合理地推算出用戶的實際位置。

綜上所述，基站、Wi-Fi、道路、POI是對一個小區(qū)域位置的綜合性描述，可以通過它們的相對關(guān)系來確定移動用戶具體的位置。因此，可根據(jù)基站、Wi-Fi、道路、POI構(gòu)成的位置綜合空間索引四元組來對定位基礎(chǔ)數(shù)據(jù)進行構(gòu)造和組織。

圖1 位置合理性示意

3 位置計算

3.1 位置計算策略

在移動互聯(lián)網(wǎng)應(yīng)用中，在難以獲得準(zhǔn)確的高精度位置信息的情況下，獲取更合理的位置信息顯得頗為重要（誤差450 m比誤差500 m并不一定更有優(yōu)勢）。所謂合理性，是指定位結(jié)果與用戶所在的生活環(huán)境具有相容性，能與人的正常生活環(huán)境相關(guān)聯(lián)。如圖1所示，A點是用戶的真實位置，B點是通過普通的定位算法計算的結(jié)果（公園內(nèi)人跡罕至的小樹林），C點是通過綜合空間位置索引的移動位置計算方法計算的結(jié)果。從地圖上可以看出，B點距離用戶真實位置A點更近，從物理上來說B點的精度比C點的精度更高，但是從用戶的角度來看，C點與用戶在道路上的感知體驗是一致的，位置基本感覺不到偏差，而B點會明顯感覺到偏差，因此C點比B點更趨合理。

因此，本文提出的基于綜合空間位置索引的移動位置計算方法中，采用以下兩個位置計算策略。

·由粗到細逐步求精策略。在位置空間索引四元組中，基站的覆蓋范圍遠遠大于Wi-Fi的覆蓋范圍，覆蓋半徑可看作定位結(jié)果的誤差，因而基站定位的誤差遠大于Wi-Fi定位誤差，因此用戶位置確定順序采用基站到Wi-Fi的優(yōu)先順序。

·位置計算合理性優(yōu)先策略。在用戶周邊往往同時存在多條道路和多個POI，不同道路具有不同的等級、寬度等，不同的POI也同樣具有不同的類型、大小等，這些屬性反應(yīng)了位置合理性的大小，通過不同權(quán)重的設(shè)置可反映位置的合理性。

圖2為位置計算策略示意。

3.2 索引權(quán)重設(shè)置

權(quán)重設(shè)置主要是設(shè)置道路和POI的權(quán)重。一般情況下，道路和POI權(quán)重更能反映用戶位置的合理性。本方法的權(quán)重包含靜態(tài)權(quán)重和動態(tài)權(quán)重兩部分。道路和POI具有一些靜態(tài)屬性，如道路的等級、寬度、POI的類型、大小等，這些靜態(tài)屬性都會影響用戶位置的合理性，因此把這些屬性設(shè)置的權(quán)重稱為靜態(tài)權(quán)重；另外，由于基站、Wi-Fi計算出來的用戶位置（X,Y）與附近各道路和POI之間具有不同的距離，在不同的時間，人們在道路和POI內(nèi)的概率會有所不同。因此，把這些距離、時間等具有隨機性的因素稱為動態(tài)權(quán)重。

·靜態(tài)權(quán)重：道路和POI可以按類型和等級兩個屬性設(shè)置權(quán)重。

·動態(tài)權(quán)重：道路和POI按照距離設(shè)置權(quán)重，采用二次函數(shù)計算距離的權(quán)重，如式（2）所示。本文暫不考慮時間權(quán)重。

圖2 位置計算策略示意

其中，a、c是調(diào)節(jié)因子，d為距離。

3.3 定位算法及流程設(shè)計

基于無線網(wǎng)絡(luò)的定位技術(shù)，采用兩步計算方法：通過基站和Wi-Fi計算出用戶位置坐標(biāo)，通過這個坐標(biāo)與周邊的道路和POI進行比較，計算出最終用戶的合理位置。

圖3為定位算法流程示意。

（1）坐標(biāo)計算

如果掃描到Wi-Fi信號參數(shù)，則使用Wi-Fi算法計算用戶位置坐標(biāo)，多個Wi-Fi參數(shù)用戶位置坐標(biāo)計算式如式（3）和式（4）所示，否則使用基站計算用戶位置坐標(biāo)。

圖3 定位算法流程示意

其中，Wix為Wi-Fi的經(jīng)度坐標(biāo)，W1y為Wi-Fi的緯度坐標(biāo)。

（2）位置計算

通過步驟（1）計算出的坐標(biāo)（X,Y）檢索周邊500 m（可調(diào)整）道路和POI數(shù)據(jù)，對每一個道路和POI數(shù)據(jù)根據(jù)權(quán)重設(shè)置計算其得分，得分最高者為最終用戶位置，道路是用戶坐標(biāo)（X,Y）到道路的垂直位置，POI是POI坐標(biāo)位置。

4 實驗結(jié)果

文章的實驗設(shè)計如下，采用配置了GPS模塊的智能手機，在不同區(qū)域采集基站和Wi-Fi數(shù)據(jù)，并同時記錄下當(dāng)前位置的GPS坐標(biāo)，數(shù)據(jù)記錄格式：<基站ID,W1,W2,…,Wn,X,Y>。然后采用本文提出的定位模型和算法，使用收集的基站與Wi-Fi熱點作為參數(shù)進行位置計算，最后計算定位結(jié)果與GPS坐標(biāo)之間的距離，作為實際定位誤差，并與沒有路網(wǎng)、POI參與的單純基站和Wi-Fi定位結(jié)果相比較。本次試驗在不同區(qū)域共采集了測試數(shù)據(jù)10 000條，測試結(jié)果如圖4所示，從圖中可看出70%以上的定位結(jié)果誤差小于100 m。

從測試結(jié)果可明顯看出，采用本文的定位模型和算法，不只是定位結(jié)果的合理性增強，定位精度同樣可明顯提高。

5 結(jié)束語

本文提出了一種基于基站、Wi-Fi、道路和POI的綜合空間位置索引的移動位置計算方法，在目前的定位技術(shù)中，首先提出了位置合理性概念，并給出了基于合理性設(shè)計的位置計算策略和方法。經(jīng)實驗表明，采用本文提出的定位方法得到了較好的定位結(jié)果。同時，本文對行為空間索引數(shù)據(jù)的基站、Wi-Fi、道路和POI等數(shù)據(jù)對象作了適當(dāng)?shù)暮喕?，如基站和Wi-Fi的信號強度等；對道路和POI的權(quán)重設(shè)置同樣采用的是經(jīng)驗?zāi)Ｐ?。為了進一步提高定位的精確性和為用戶提供更良好的體驗，接下來將進一步研究可以采用機器學(xué)習(xí)等智能化大數(shù)據(jù)處理算法，給出更精確的模型。

圖4 定位測試結(jié)果

1 Chen G L,Kotz D.A Survey of Context-Aware Mobile Computing Research.Dartmouth Computer Science Technical Report TR2000-38，2000

2 斯托林斯.無線通信與網(wǎng)絡(luò).何軍等譯.北京：清華大學(xué)出版社，2005

3 Jiang C,Steenkiste P.A hybrid location model with a computable location identifier for ubiquitous computing.UbiComp 2002:Ubiquitous Computing,Goteborg,Sweden,2002

4 Becker C,Dürr F.On location models for ubiquitous computing.Personal and Ubiquitous Computing,2005(1)

5 Smailagic A,Small J,Siewiorek D P.Determining User Location for Context Aware Computing Through the Use of a Wireless LAN Infrastructure.Institute for Complex Engineered,2000

6 Hightower J,Borriello G.A survey and taxonomy of location systems for ubiquitous computing.IEEE Computer,2001(18)