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

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

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

1 引言

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

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

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

2 位置索引

2.1 移動互聯網應用對位置的需求

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

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

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

2.2 移動互聯網應用中位置的定義

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

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

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

其中，C表示移動通信基 站，W表示Wi-Fi熱點，R表示道路，P表示POI。

2.3 綜合位置索引

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

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

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

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

P：POI編號（PID）、名稱、城市區位碼、類型、坐標（X,Y）。

在以上4類位置索引數據對象中，每一類數據對象都有確定的地理坐標，能夠確定一個具體的地理位置，但是，其在定位技術實現中的意義和使用是完全不同的。基站信號和Wi-Fi信號是移動終端能夠獲得的無線參數，既是移動終端與環境交互的媒介，也是計算移動終端理論位置的基礎信息；道路和POI是對環境的描述，能夠更合理地推算出用戶的實際位置。

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

圖1 位置合理性示意

3 位置計算

3.1 位置計算策略

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

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

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

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

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

3.2 索引權重設置

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

·靜態權重：道路和POI可以按類型和等級兩個屬性設置權重。

·動態權重：道路和POI按照距離設置權重，采用二次函數計算距離的權重，如式（2）所示。本文暫不考慮時間權重。

圖2 位置計算策略示意

其中，a、c是調節因子，d為距離。

3.3 定位算法及流程設計

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

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

（1）坐標計算

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

圖3 定位算法流程示意

其中，Wix為Wi-Fi的經度坐標，W1y為Wi-Fi的緯度坐標。

（2）位置計算

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

4 實驗結果

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

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

5 結束語

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

圖4 定位測試結果

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

2 斯托林斯.無線通信與網絡.何軍等譯.北京：清華大學出版社，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)