楊小漫，李曉宇

（鄭州大學 信息工程學院，河南 鄭州450001）

0 引 言

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

1 基于LBS的購物導航

1.1 LBS簡介

LBS涉及到地理信息服務、計算機應用互操作、無線通訊、用戶終端、定位技術、系統(tǒng)構架和相關軟件等技術，屬于空間信息、計算機網絡協(xié)同計算交叉學術領域。LBS是將移動用戶不斷變化的位置和對應的地理位置信息相聯(lián)系，并在移動通信設備上，面向用戶提供基于空間信息的相關服務總稱。當移動用戶需要基于位置的信息服務時，終端通過定位設備 （如GPS）獲得當前的位置數(shù)據(jù)，并實時地通過無線通信把數(shù)據(jù)上傳送到服務中心，然后服務中心服務器根據(jù)位置和服務要求進行分析、決策，進而再下傳到移動終端?；谖恢梅盏木薮篦攘φ窃谡_的時間、正確的地點把正確的信息發(fā)送給正確的人。

1.2 模型主要功能

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

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

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

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

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

圖2 LBS請求流程

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

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

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

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

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

圖3 “預取”模式中的請求流程

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

2.1.2 提高命中率策略

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

2.1.3 可行性分析

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

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

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

2.2.1 操作步驟

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

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

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

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

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

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

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

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

算法2：服務器端算法

2.3 基于預處理的查詢策略

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

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

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

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

3 實驗驗證及結果

3.1 平臺搭建

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

3.2 實驗結果與分析

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

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

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

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

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

4 結束語

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

［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在移動導游系統(tǒ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）.［周傲英，楊彬，金澈清，等.基于位置的服務：架構與進展 ［J］.計算機學報，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網絡下的LBS架構研究及實現(xiàn) ［J］.信息安全與技術，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)網社交模型 ［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的服務匹配方法研究［J］.計算機科學，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ù)路徑預測 ［D］.杭州：浙江大學碩士論文，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)應用，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］.計算機應用研究，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核心技術與實例詳解 ［M］.北京：電子工業(yè)出版社，2010.］

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

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