基于位置的服務(wù)中數(shù)據(jù)預(yù)處理技術(shù)的研究

楊小漫，李曉宇

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

隨著無線通信技術(shù)、移動互聯(lián)網(wǎng)和智能移動終端的迅速發(fā)展，基于位置的服務(wù) （location based services，LBS）在軍事、交通、物流等諸多領(lǐng)域得到了廣泛應(yīng)用，并為人們?nèi)粘Ｉ顜砹撕艽髱椭?。?jù)統(tǒng)計，在人們?nèi)粘Ｉ钪?，?0%的信息與位置相關(guān)。為了查找某個人、某個地點，常常耗去人們大量的精力。因此，為適應(yīng)節(jié)奏越來越快的社會生活加，省時、快速、高效的位置信息查詢將成為一種普遍的追求［1］。結(jié)合無線通信技術(shù)的即時性和互聯(lián)網(wǎng)豐富信息的全球共享性，LBS使隨時隨地的信息溝通和處理成為可能［2，3］。然而，由于移動網(wǎng)絡(luò)的不穩(wěn)定性和移動終端資源的有限性，目前LBS應(yīng)用出現(xiàn)查詢反應(yīng)慢等諸多問題?，F(xiàn)有的LBS領(lǐng)域的研究多集中在無線網(wǎng)絡(luò)的傳輸和LBS應(yīng)用層面的擴展，在服務(wù)器端很多學(xué)者引入云計算，但在LBS系統(tǒng)中的應(yīng)用云計算還比較少，要真正實現(xiàn)LBS的廣泛應(yīng)用，還應(yīng)解決數(shù)據(jù)的收集和處理問題。在移動客戶端和服務(wù)器端頻繁斷接情況下，結(jié)合移動終端較高的處理能力和存儲能力等優(yōu)點，本文提出基于數(shù)據(jù)預(yù)處理策略的“預(yù)取”模式，以此來縮短查詢等待時間、改善斷接時查詢的有效性，并運用智能學(xué)習(xí)策略提高數(shù)據(jù)預(yù)處理后的命中率，從而提高LBS應(yīng)用率。

1 基于LBS的購物導(dǎo)航

1.1 LBS簡介

LBS涉及到地理信息服務(wù)、計算機應(yīng)用互操作、無線通訊、用戶終端、定位技術(shù)、系統(tǒng)構(gòu)架和相關(guān)軟件等技術(shù)，屬于空間信息、計算機網(wǎng)絡(luò)協(xié)同計算交叉學(xué)術(shù)領(lǐng)域。LBS是將移動用戶不斷變化的位置和對應(yīng)的地理位置信息相聯(lián)系，并在移動通信設(shè)備上，面向用戶提供基于空間信息的相關(guān)服務(wù)總稱。當(dāng)移動用戶需要基于位置的信息服務(wù)時，終端通過定位設(shè)備 （如GPS）獲得當(dāng)前的位置數(shù)據(jù)，并實時地通過無線通信把數(shù)據(jù)上傳送到服務(wù)中心，然后服務(wù)中心服務(wù)器根據(jù)位置和服務(wù)要求進行分析、決策，進而再下傳到移動終端。基于位置服務(wù)的巨大魅力正是在正確的時間、正確的地點把正確的信息發(fā)送給正確的人。

1.2 模型主要功能

近年來，隨著越來越繁華的大規(guī)模商業(yè)區(qū)的出現(xiàn)，購物已不再是件容易的事情。當(dāng)移動用戶進入毫不熟悉的商業(yè)熱區(qū)時，急需知道 “我在哪里？附近是什么？附近哪些商店最受歡迎？最省時最簡便的到達路線是？”等信息。攜帶基于LBS購物導(dǎo)航的用戶則能隨時隨地獲取當(dāng)前的地理位置及其附近各種場所的LBS資訊，讓購物變得即省時又省力。這種購物導(dǎo)航不僅為用戶購物提供便利而且還能提高商業(yè)區(qū)的銷售量。

基于LBS的購物導(dǎo)航所提供的功能：顯示用戶當(dāng)前位置；顯示附近興趣點 （POI）及其詳細(xì)信息；依據(jù)用戶偏好提供推薦列表；提供最佳路徑。如圖1所示。

首先，當(dāng)移動用戶通過定位系統(tǒng)確定自己當(dāng)前的精確位置后，以用戶的位置偏移量為觸發(fā)條件，依照設(shè)置的搜索條件 （包括搜索范圍和所屬類別）搜索，動態(tài)更新移動終端的服務(wù)信息。其次，通過以往經(jīng)驗進行知識學(xué)習(xí)，并依據(jù)用戶時空位置和偏好提供個性化的推薦列表。然后，用戶參考推薦列表，通過多方面比較選定目標(biāo)點，購物導(dǎo)航依據(jù)交通方式 （步行、公交、開車等）提供最佳行程路線。因此，攜帶基于LBS購物導(dǎo)航的移動用戶能夠?qū)γＣＩ虡I(yè)區(qū)的信息了如指掌，讓用戶體驗一個輕松愉快的購物旅程。

2 LBS中的數(shù)據(jù)預(yù)處理技術(shù)

基于LBS購物導(dǎo)航的請求流程如下：移動客戶端首先發(fā)送相關(guān)位置查詢請求到服務(wù)器端；服務(wù)器端接收到請求后進行服務(wù)器端數(shù)據(jù)庫查詢，并返回查詢結(jié)果，客戶端顯示附近POI位置；若移動用戶繼續(xù)查看某POI的詳細(xì)信息時，需再次發(fā)送查詢請求給服務(wù)器；服務(wù)器再次依據(jù)請求執(zhí)行數(shù)據(jù)庫查詢，返回結(jié)果給客戶端［4，5］。如圖2所示。

圖2 LBS請求流程

2.1 數(shù)據(jù)預(yù)處理策略

從圖2中可看出，用戶每查看一次就發(fā)送一次請求，服務(wù)器端也隨之不斷地查詢服務(wù)器端數(shù)據(jù)庫，并返回查詢結(jié)果。由于無線網(wǎng)絡(luò)的不穩(wěn)定特性和帶寬有限性，這種策略不但繁瑣、查詢時間慢、浪費用戶等待時間，而且消耗客戶端能量資源、加重服務(wù)器端負(fù)載。本文對此作出改進，提出基于查詢數(shù)據(jù)預(yù)處理的 “預(yù)取”模式，改善LBS的查詢效率。

2.1.1 LBS中數(shù)據(jù)預(yù)處理策略分析

本文是通過對服務(wù)器端和移動終端的查詢數(shù)據(jù)預(yù)處理，來改進繁瑣的查詢請求所帶來的查詢遲緩問題。在服務(wù)器端實現(xiàn)一次查詢所有，即：查詢到POI的同時也一并把相應(yīng)的詳細(xì)信息查詢出來，并生成推薦列表；在移動終端上，對接收到的查詢結(jié)果集進行本地移動數(shù)據(jù)庫存儲。當(dāng)移動用戶查詢某興趣點的詳細(xì)信息時，實際上是查詢本地數(shù)據(jù)庫，或在服務(wù)器端的查詢結(jié)果中匹配要查詢的信息［6］。

改進的請求流程如圖3所示。

圖3 “預(yù)取”模式中的請求流程

從圖3中可明顯看出，改進的基于數(shù)據(jù)預(yù)處理模式可明顯減少無線網(wǎng)絡(luò)中查詢請求次數(shù)及傳輸次數(shù)，進而提高查詢效率。

2.1.2 提高命中率策略

在改進的 “預(yù)取”模式中，服務(wù)器端是在未再次接收請求之前而采取預(yù)取策略，那么就涉及到預(yù)取的信息是否滿足移動用戶的當(dāng)前需要，即預(yù)取策略能否提高查詢命中率。目前大部分LBS研究都處于為移動用戶提供信息的階段，缺乏對信息的智能化推理過程。本文采用基于經(jīng)驗的智能學(xué)習(xí)，服務(wù)器端通過對歷史時空路徑數(shù)據(jù)學(xué)習(xí)，以最大概率查詢出滿足移動用戶當(dāng)前需求的信息，生成推薦列表，確保在正確地點、正確時間為用戶提供正確的、個性化服務(wù)［7］。從而提高服務(wù)器端推送信息的命中率，進而使LBS應(yīng)用更人性化、更貼近人們的生活。

2.1.3 可行性分析

本文 “預(yù)取”模式的關(guān)鍵是服務(wù)器端在再次接收查詢請求之前預(yù)先查詢出有關(guān)詳細(xì)信息和服務(wù)推薦信息，并在客戶端本地移動數(shù)據(jù)庫中存儲這些信息。這種策略是以犧牲數(shù)據(jù)傳輸量和移動客戶端的存儲量來換取查詢響應(yīng)時間。目前，移動設(shè)備迅速發(fā)展，性能得到很大提高，移動終端（如智能手機）的計算能力和存儲能力已逐漸接近計算機性能，因此這種基于數(shù)據(jù)預(yù)處理的改進策略對目前市場流行的移動智能終端來說是可行的。

另外，預(yù)查詢的推薦信息是服務(wù)器端通過大量移動用戶歷史時空路徑經(jīng)驗進行知識學(xué)習(xí)，依據(jù)所形成的智能策略選擇令用戶滿意的POI信息。它改變了傳統(tǒng)固定排名壟斷的現(xiàn)象，提供給移動用戶基于環(huán)境的個性化推薦，因此推薦信息命中率也將會有所提高。

2.2 基于數(shù)據(jù)預(yù)處理的LBS購物導(dǎo)航模型

2.2.1 操作步驟

（1）當(dāng)移動終端成功從定位系統(tǒng)獲取當(dāng)前精確位置后，移動終端采用主動請求連接方式與服務(wù)器端建立無線網(wǎng)絡(luò)連接，由客戶端發(fā)送網(wǎng)絡(luò)連接請求，服務(wù)器端做連接回應(yīng)；

（2）移動用戶設(shè)置定位觸發(fā)規(guī)則和搜索程序觸發(fā)規(guī)則（包括搜索范圍、商品類別、用戶偏好等信息）。依據(jù)設(shè)置的觸發(fā)條件和搜索條件對用戶附近進行相應(yīng)的搜索，即：當(dāng)用戶位移量超過某范圍時，重新定位搜索，動態(tài)更新終端的服務(wù)信息；

（3）移動客戶端發(fā)送附近信息查詢請求給服務(wù)器端。其中發(fā)送的請求數(shù)據(jù)包含步驟2中所設(shè)置的信息；

（4）服務(wù)器端執(zhí)行查詢請求。在服務(wù)器端數(shù)據(jù)庫中查詢用戶周圍的POI及相應(yīng)的詳細(xì)信息，同時依據(jù)智能策略在結(jié)果集中生成推薦列表，然后通過無線網(wǎng)絡(luò)把這些信息數(shù)據(jù)都發(fā)送到移動客戶端；

（5）移動客戶端接收到服務(wù)器端的查詢結(jié)果集，將POI位置標(biāo)示在電子地圖上，并向用戶推薦最佳列表；同時把搜索到的結(jié)果集作為添加數(shù)據(jù)存儲到本地移動數(shù)據(jù)庫中；

（6）當(dāng)用戶點擊POI查看其詳細(xì)信息時，這時的查詢請求會在本地移動數(shù)據(jù)庫中執(zhí)行［8，9］，若查詢不到結(jié)果就在服務(wù)器端的查詢結(jié)果集中匹配；

（7）查看多個詳細(xì)信息，經(jīng)過比較后，選定某一興趣點作為目標(biāo)點，這時基于LBS的購物導(dǎo)航就依據(jù)交通方式為顧客提供最佳路徑。

2.2.2 算法實現(xiàn)算法1：移動客戶端過程算法

算法2：服務(wù)器端算法

2.3 基于預(yù)處理的查詢策略

在對查詢數(shù)據(jù)做預(yù)處理后，用戶點擊某POI查看詳細(xì)信息時，這時在移動客戶端的查詢有兩種情況：

（1）查看的詳細(xì)信息在本地移動數(shù)據(jù)庫中。查詢結(jié)果已從服務(wù)器端傳送并存儲到本地移動數(shù)據(jù)庫中，這時客戶端只需要查詢本地數(shù)據(jù)庫即可。這種情況下，即使移動終端與服務(wù)器斷接也能查詢到結(jié)果。另外，本地移動數(shù)據(jù)庫查詢響應(yīng)相當(dāng)迅速而且查詢結(jié)果無需網(wǎng)絡(luò)傳輸，因而降低了對不穩(wěn)定無線網(wǎng)絡(luò)的依賴性、縮短了查詢時間。

（2）查看的詳細(xì)信息不在本地移動數(shù)據(jù)庫中。由于數(shù)據(jù)的傳輸時延，服務(wù)器端所查詢到的詳細(xì)信息還未來得及傳輸?shù)娇蛻舳吮镜匾苿訑?shù)據(jù)庫中。這種情況下，客戶端發(fā)送查看請求，服務(wù)器端執(zhí)行請求并返回結(jié)果。這樣的查詢貌似沒什么改進，但實際上它減少了查詢時間。因為服務(wù)器已經(jīng)在用戶思考和網(wǎng)絡(luò)傳輸請求的這段時間中查詢到了詳細(xì)信息，只是沒來得及返回給客戶端而已。這時服務(wù)器端只需在服務(wù)器端查詢結(jié)果中匹配不需要再次查詢，與傳統(tǒng)的LBS查詢相比，節(jié)省了服務(wù)器端數(shù)據(jù)庫查詢時間。

因此，無論是哪種情況，這種改進的 “預(yù)取”模式都能提高傳統(tǒng)LBS的查詢響應(yīng)時間，改善無線網(wǎng)絡(luò)的不穩(wěn)定性給LBS應(yīng)用帶來的查詢遲緩問題，同時減少了由于網(wǎng)絡(luò)問題引起的數(shù)據(jù)錯誤和重發(fā)。

3 實驗驗證及結(jié)果

3.1 平臺搭建

以三星I9250（android智能手機）作為移動客戶端，它自帶SQLite數(shù)據(jù)庫作為LBS的移動數(shù)據(jù)庫。以CPU是Pentium （R）、主頻是3.20GHz、內(nèi)存是1.96GB的PC機做Web服務(wù)器端，并安裝Tomcat 6.0和服務(wù)器端數(shù)據(jù)庫MySql 5.0。 用 JSP 做 頁 面 處 理、Servlet響 應(yīng) 客 戶 端請求［10－12］。

3.2 實驗結(jié)果與分析

圖4橫軸為移動終端的個數(shù)，縱軸為多次成功的數(shù)據(jù)訪問所花費的平均時間。圖中共有5條曲線，其中 “未處理”圖線代表未做數(shù)據(jù)預(yù)處理，移動終端直接查詢服務(wù)器數(shù)據(jù)庫的平均訪問時間?！懊新省贝硪苿咏K端訪問的數(shù)據(jù)恰好是經(jīng)過預(yù)處理之后在移動終端的本地緩存中可以找到備份數(shù)據(jù)的概率。其余四條圖線分別是命中率為90%、80%、70%、60%時的移動終端查詢數(shù)據(jù)的平均訪問時間。

圖4 平均訪問時間——移動終端數(shù)目

實驗結(jié)果表明，做了數(shù)據(jù)預(yù)處理之后，移動終端查詢數(shù)據(jù)庫的平均訪問時間明顯降低，甚至在命中率僅僅剛剛超出一半的情況 （命中率60%）下仍然如此?？梢姅?shù)據(jù)預(yù)處理技術(shù)可以有效地提高在基于位置的購物導(dǎo)航中移動終端的訪問效率。事實上，考慮到現(xiàn)實中大部分顧客的購物興趣是趨向一致的，例如大商場、口碑好的商店等往往是絕大部分顧客共同的優(yōu)先選擇，因此通過對顧客購物歷史數(shù)據(jù)做簡單的智能學(xué)習(xí)就可以得到最優(yōu)的推薦排名，而語句預(yù)處理中排名靠前的商店的信息是優(yōu)先做預(yù)處理的。所以，現(xiàn)實中移動終端查詢時命中率達到80%～90%并不困難。換句話說，本文的數(shù)據(jù)預(yù)處理模型在現(xiàn)實中可以大大提高終端用戶的訪問效率，節(jié)約用戶的時間。

另外，注意到隨著移動終端數(shù)目的增長，雖然用戶的平均訪問時間在增加，但是預(yù)處理之后的訪問時間相對未作預(yù)處理的訪問時間的差距仍維持穩(wěn)定，并未明顯縮小?？梢姳疚牡幕跀?shù)據(jù)預(yù)處理的模型具有較好的穩(wěn)定性，能夠在移動終端數(shù)目較多的時候仍然保持可觀的效率收益，具有較好的實用價值。

最后，在無線網(wǎng)絡(luò)斷開時，基于數(shù)據(jù)預(yù)處理的模型還能以一定的概率在終端的本地數(shù)據(jù)庫中查詢到用戶需要的數(shù)據(jù)，而傳統(tǒng)的模型則不能，這說明基于數(shù)據(jù)預(yù)處理的模型能夠減少對無線網(wǎng)絡(luò)的依賴性，提高購物導(dǎo)航的可靠性。

4 結(jié)束語

隨著移動智能終端的快速升級，基于位置的服務(wù)在人們的生活中越來越被廣泛應(yīng)用。本文結(jié)合移動網(wǎng)絡(luò)和移動數(shù)據(jù)庫的特點提出了數(shù)據(jù)預(yù)處理技術(shù)。在基于LBS購物導(dǎo)航中，經(jīng)實驗驗證這種基于數(shù)據(jù)預(yù)處理技術(shù)對不同命中率情況下的數(shù)據(jù)訪問，能有效縮短查詢時間，并且在移動終端和服務(wù)器斷接情況下，基于數(shù)據(jù)預(yù)處理的模型依然能實現(xiàn)有效查詢，同時運用智能學(xué)習(xí)策略提高推薦列表命中率，提供基于環(huán)境的個性化推薦。因此，這種基于數(shù)據(jù)預(yù)處理的模型能有效改善查詢效率、減少對不穩(wěn)定無線網(wǎng)絡(luò)的依賴性，具有較好的穩(wěn)定性，對基于位置的服務(wù)應(yīng)用具有潛在的實用價值。

［1］WANG Shuai，LIU Houquan，CHENG Shuangshuang.The research and application of LBS in mobile guide system ［J］.Micro Computer Information，2010，26 （21）：97－153 （in Chinese）.［王帥，劉厚泉，程雙雙.LBS在移動導(dǎo)游系統(tǒng)中的應(yīng)用與研究 ［J］.微計算信息，2010，26 （21）：97－153.］

［2］ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Locationbased services：Architecture and progress ［J］.Chinese Journal of Computer，2011，34 （7）：1156－1167 （in Chinese）.［周傲英，楊彬，金澈清，等.基于位置的服務(wù)：架構(gòu)與進展 ［J］.計算機學(xué)報，2011，34 （7）：1156－1167.］

［3］GUO Ying.Research and implementation of a 3G－based LBS system architecture［J］.Information Security and Technology，2011 （5）：39－43 （in Chinese）.［郭盈.一種3G網(wǎng)絡(luò)下的LBS架構(gòu)研究及實現(xiàn) ［J］.信息安全與技術(shù)，2011（5）：39－43.］

［4］YANG Yuyao，ZHAO Fang，LUO Haiyong，et al.A geolocation－based social network model for mobile internet［J］.Journal of Computer Research and Development，2011，48 （z2）：307－313（in Chinese）.［楊煜堯，趙方，羅海勇，等.一種基于地理位置信息的移動互聯(lián)網(wǎng)社交模型 ［J］.計算機研究與發(fā)展，2011，48 （z2）：307－313.］

［5］WANG Lepeng，LI Chunli，WANG Ying.The foursquare model and explore in the development of Chinas countermeasures ［J］.Science ＆ Technology Informatio，2010 （23）：90－91 （in Chinese）.［王樂鵬，李春麗，王穎.Foursquare模式及在中國的發(fā)展對策探討 ［J］.科技信息，2010 （23）：90－91.］

［6］ZHANG Degan，WANG Dong.Research on service matching method for LBS［J］.Computer Science，2012，39 （3）：19－61（in Chinese）.［張德干，王冬.面向LBS的服務(wù)匹配方法研究［J］.計算機科學(xué)，2012，39 （3）：19－61.］

［7］YE Qian.The individual continuous path prediction based on path pattern mining ［D］.Hangzhou：Zhejiang University Thesis，2008（in Chinese）.［葉謙，基于路徑模式挖掘的個人連續(xù)路徑預(yù)測 ［D］.杭州：浙江大學(xué)碩士論文，2008.］

［8］HU Xiaohong，SHEN Hesong.Data query in embedded mobile database［J］.Microcontrollers ＆ Embedded Systems，2009（3）：14－16 （in Chinese）.［胡曉宏，沈賀嵩.嵌入式移動數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)查詢 ［J］.單片機與嵌入式系統(tǒng)應(yīng)用，2009（3）：14－16.］

［9］LI Dong，YE You，XIE Fangyong.Optimization technology of query trimming in semantic caching ［J］.Application Research of Computers，2008，25 （12）：3606－3609 （in Chinese）.［李東，葉友，謝芳勇.語義緩存查詢裁剪優(yōu)化 ［J］.計算機應(yīng)用研究，2008，25 （12）：3606－3609.］

［10］WU Yafeng，SUO Yina.The android core technologies and explain examples ［M］.Beijing：Publishing House of Electronics Industry，2010 （in Chinese）.［吳亞峰，索依娜.Android核心技術(shù)與實例詳解 ［M］.北京：電子工業(yè)出版社，2010.］

［11］Reto Meier.Android advanced programming［M］Beijing：Qinghua University press，2010 （in Chinese）.［Reto Meier.Android高級編程 ［M］.北京：清華大學(xué)出版社，2010.］

［12］GENG Xiangyi，ZHANG Yueping.JSP practical tutorial［M］.Beijing：Tsinghua University Press，2007 （in Chinese）. ［耿祥義，張躍平.JSP實用教程 ［M］.北京：清華大學(xué)出版社，2007.］