吳春輝，徐萬和

（1.湖北科技學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 咸寧 437100；

2.通城縣地方稅務(wù)局，湖北 通城 437400）

隨著移動通信技術(shù)的迅速發(fā)展和使用，許多計算結(jié)點(diǎn)已經(jīng)可以在自由移動的過程中保持與網(wǎng)絡(luò)的連接.于是人們迫切需求能在任何時候、任何地點(diǎn)訪問任何數(shù)據(jù)，這使得原來基于有線網(wǎng)絡(luò)和固定主機(jī)的分布式數(shù)據(jù)庫不再適應(yīng)，因而移動數(shù)據(jù)庫技術(shù)便應(yīng)運(yùn)而生.新的應(yīng)用對移動環(huán)境下的事務(wù)處理提出了新的需求，如實(shí)時交通信息管理系統(tǒng)、海上導(dǎo)航系統(tǒng)及股票交易系統(tǒng)等，該類應(yīng)用普遍要求在移動環(huán)境下實(shí)現(xiàn)實(shí)時事務(wù)處理.移動實(shí)時數(shù)據(jù)庫系統(tǒng)（MRTDBS）正開始受到越來越多的研究人員的關(guān)注.一般認(rèn)為移動實(shí)時數(shù)據(jù)庫系統(tǒng)就是移動環(huán)境（如GSM網(wǎng)絡(luò)和無線局域網(wǎng)）所支持的實(shí)時數(shù)據(jù)庫系統(tǒng)［1］.

以計算機(jī)網(wǎng)絡(luò)為中心的移動計算技術(shù)得到廣泛應(yīng)用，隨著智能移動終端的普及，人們對移動數(shù)據(jù)的實(shí)時處理和管理要求不斷提高，同時在對無線網(wǎng)絡(luò)和時空要求也越來越迫切，因此在分布式計算、實(shí)時處理、移動通信、無線實(shí)時查詢等各個方面都有著非常廣泛的應(yīng)用.

1 移動數(shù)據(jù)庫

移動數(shù)據(jù)庫是伴隨著移動計算誕生的.移動計算是一種新型的技術(shù)，它使得計算機(jī)或其它信息設(shè)備，在沒有與固定的物理連接設(shè)備相連的情況下，能夠傳輸數(shù)據(jù).移動計算的作用在于，將有用準(zhǔn)確及時的信息與中央信息系統(tǒng)相互作用，分擔(dān)中央信息系統(tǒng)的計算壓力，使有用準(zhǔn)確及時的信息能提供給在任何時間任何地點(diǎn)需要它的任何用戶.移動計算環(huán)境比傳統(tǒng)的計算環(huán)境更為復(fù)雜和靈活.凡是有數(shù)據(jù)的地方，就要用到數(shù)據(jù)庫來協(xié)助管理數(shù)據(jù)移動計算也是對數(shù)據(jù)的處理，離開對數(shù)據(jù)的管理處理，計算機(jī)就毫無意義移動計算同時又強(qiáng)調(diào)其移動性，傳統(tǒng)的 PC機(jī)要做到移動，同時在苛刻的環(huán)境下作到良好的運(yùn)作也是不可能的，當(dāng)然，嵌入式很好的滿足了移動計算對移動客戶端計算的要求三者從這一點(diǎn)上結(jié)合就產(chǎn)生了當(dāng)今數(shù)據(jù)庫的一個新的發(fā)展空間：嵌入式數(shù)據(jù)庫技術(shù)移動數(shù)據(jù)庫是指支持移動計算環(huán)境的分布式數(shù)據(jù)庫［2］.

縱觀數(shù)據(jù)庫技術(shù)發(fā)展過程，計算環(huán)境和數(shù)據(jù)庫技術(shù)基本保持著一種同步發(fā)展的態(tài)勢，它們互相影響，互相促進(jìn).計算環(huán)境先后經(jīng)歷了集中式、分布式、網(wǎng)絡(luò)以及目前受到廣泛關(guān)注的移動計算環(huán)境MCE（Mobile Computing Environment）等多種計算模式.相應(yīng)地，數(shù)據(jù)庫系統(tǒng)的發(fā)展也經(jīng)歷了集中式數(shù)據(jù)庫系統(tǒng)、分布式數(shù)據(jù)庫系統(tǒng)、B/A/S多層結(jié)構(gòu)的數(shù)據(jù)庫系統(tǒng)、嵌入式數(shù)據(jù)庫系統(tǒng)和移動數(shù)據(jù)庫系統(tǒng)等多個階段［3］.

與基于固定網(wǎng)絡(luò)的傳統(tǒng)分布計算環(huán)境相比，移動計算環(huán)境具有移動性、頻繁斷接性、網(wǎng)絡(luò)條件多樣性、網(wǎng)絡(luò)通信的非對稱性、不可靠性、規(guī)模易變性及電源能力有限等特點(diǎn)［1］.這些特點(diǎn)都要求移動實(shí)時數(shù)據(jù)庫系統(tǒng)必須具有比傳統(tǒng)客戶/服務(wù)器及分布式數(shù)據(jù)庫系統(tǒng)高得多的可伸縮性.同時，那些傳統(tǒng)分布式計算和分布式數(shù)據(jù)庫的研究基于有線網(wǎng)絡(luò)和固定主機(jī)的默認(rèn)隱含假設(shè)，如固定網(wǎng)絡(luò)連接、對等通訊代價、主機(jī)節(jié)點(diǎn)固定不變等在此也已不再成立.

移動實(shí)時數(shù)據(jù)庫系統(tǒng)可以定義為：事務(wù)和數(shù)據(jù)可以具有定特性或顯示定時限制，并運(yùn)行在移動計算環(huán)境的數(shù)據(jù)庫系統(tǒng).移動實(shí)時數(shù)據(jù)庫是在移動計算環(huán)境下的分布式、實(shí)時數(shù)庫，其本質(zhì)特征是實(shí)時處理、分布式計算和移動服務(wù).一個移實(shí)時數(shù)據(jù)庫系統(tǒng)包括移動客戶機(jī)（MHS）、固定主機(jī)（Fhs）、位置服務(wù)器（LS）、移動支持基站（MSSs）、固定網(wǎng)絡(luò)和移動網(wǎng)絡(luò)［3］.

2 移動時空數(shù)據(jù)庫中的關(guān)鍵技術(shù)

2.1 同步機(jī)制：在移動數(shù)據(jù)庫的實(shí)際應(yīng)用中，如何在錯綜復(fù)雜的移動環(huán)境下高效地實(shí)現(xiàn)數(shù)據(jù)的最終收斂：即保持?jǐn)?shù)據(jù)的一致性是關(guān)鍵問題，而這數(shù)據(jù)的最終一致性是整個系統(tǒng)的根本所在，也是同步過程所要達(dá)到的目標(biāo)，數(shù)據(jù)的一致性有緊密一致性和松散一致性兩種類型，傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)屬于緊密一致性，也就是說在傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)可以在任何時候都保持一致性，在固定征稽系統(tǒng)中即是如此，而在移動征稽系統(tǒng)中由于移動環(huán)境與網(wǎng)絡(luò)的斷連接，資源有限，要實(shí)現(xiàn)數(shù)據(jù)的緊密一致性往往是不現(xiàn)實(shí)的.因此，數(shù)據(jù)的收斂通常是采用松散一致性來完成的，即不能保持?jǐn)?shù)據(jù)的時刻一致，但是可以允許暫時不一致，進(jìn)而可以采用同步技術(shù)來保證數(shù)據(jù)的一致性［4］.

2.2 數(shù)據(jù)廣播技術(shù)：無線通信網(wǎng)絡(luò)的迅猛發(fā)展使得移動計算成為現(xiàn)實(shí).移動支持站點(diǎn)把被頻繁請求的數(shù)據(jù)組織起來，以廣播的形式傳送給移動客戶.移動實(shí)時環(huán)境里數(shù)據(jù)廣播的首要問題是廣播內(nèi)容的選擇.被頻繁請求的熱點(diǎn)數(shù)據(jù)能夠及時廣播，將會滿足大量客戶的需求，提高系統(tǒng)效率.傳統(tǒng)的頻繁元素獲取通常采用計數(shù)、概要、分位數(shù)和散列等技術(shù)，時間性能最好的是散列類算法.在伯努利大數(shù)定理和馬爾科夫不等式的基礎(chǔ)上，通過統(tǒng)計散列沖突估算頻繁元素出現(xiàn)的次數(shù)，利用多個散列函數(shù)和散列表可以使得誤差被控制到精度許可的范圍內(nèi).多散列計算可以充分利用現(xiàn)在主流多核微型處理器的計算能力.只需要增加散列函數(shù)的.

數(shù)量就可以提高統(tǒng)計精度，而增加的計算時間卻很少.以最少的時間和能源消耗獲得最多有用的數(shù)據(jù)是移動客戶在數(shù)據(jù)廣播中獲取的最大效益.數(shù)據(jù)廣播調(diào)度從客戶效益出發(fā)，采用基于優(yōu)先權(quán)的調(diào)度策略.優(yōu)先權(quán)綜合考慮了數(shù)據(jù)截止期，數(shù)據(jù)的被請求頻率和數(shù)據(jù)請求的到達(dá)時間.通過參數(shù)來調(diào)整它們的權(quán)重，使得調(diào)度策略能夠在滿足數(shù)據(jù)請求成功率的基礎(chǔ)上，權(quán)衡平均訪問時間和調(diào)諧時間.在調(diào)度策略的實(shí)施過程中將同一客戶請求的數(shù)據(jù)盡可能地放在一起調(diào)度播出.數(shù)據(jù)組織結(jié)構(gòu)里增加了熱點(diǎn)數(shù)據(jù)指示器，移動客戶在偵聽信道的時候，可以根據(jù)自己設(shè)備的電源情況，有選擇地下載各級熱點(diǎn)數(shù)據(jù)，提高緩存命中率，降低上行信道負(fù)荷和平均訪問時間，提高系統(tǒng)的處理能力.實(shí)時系統(tǒng)中數(shù)據(jù)訪問偏斜時，數(shù)據(jù)廣播的索引技術(shù)鮮有研究.建立索引一方面要考慮數(shù)據(jù)的訪問概率，另一方面要考慮數(shù)據(jù)的時間限制；同時構(gòu)建索引的算法本身的時間復(fù)雜度要低.近似最優(yōu)二叉索引樹參考靜態(tài)最優(yōu)查找樹的構(gòu)造思想，在處理節(jié)點(diǎn)概率權(quán)重時引入實(shí)時加權(quán)，快速構(gòu)造出查找效果近似最優(yōu)的二叉索引樹.其查找過程類似于折半查找，平均查找長度和logN成正比，即調(diào)諧時間至多l(xiāng)ogN個時間單位.因?yàn)榭紤]數(shù)據(jù)訪問概率，被頻繁訪問的數(shù)據(jù)放在廣播序列的前端，縮短了平均調(diào)諧時間；因?yàn)榭紤]了實(shí)時加權(quán)，時限較短的數(shù)據(jù)也放在了廣播序列的前端，提高了實(shí)時系統(tǒng)中數(shù)據(jù)請求的成功率［5］.

2.3 路網(wǎng)下的最近鄰動態(tài)查詢：對于快速發(fā)展的無線技術(shù)，基于位置的服務(wù)（LBSs）成為可能，其中基于位置的查詢（LBQs）技術(shù)是一個非常熱門的研究課題，而在基于位置的查詢（LBQs）中最近鄰查詢（NN）又是最多最實(shí)用的一種查詢.當(dāng)然這其中涉及了很多方面的問題，比如：

（1）居住在某小區(qū)的人想要找到離家最近的超市，這個問題可以抽像為這個問題，把其周邊可以設(shè)置一個范圍如100公里之內(nèi)的超市，把超市作為一個一個的節(jié)點(diǎn)，構(gòu)造一個圖，然后此人就可以通過查找離他家最近的那個節(jié)點(diǎn)即可，這類問題是最簡單的一個問題，因?yàn)椴檎艺吆筒檎覍ο蠖际庆o態(tài)不變的.

（2）行駛在公路上的汽車查找最近的加油站，這個問題實(shí)際上就是最近鄰查詢問題，可以把加油站想成一個一個的節(jié)點(diǎn)，汽車查找最近的那個節(jié)點(diǎn)即可.當(dāng)然在此類問題中在路上行駛的汽車是運(yùn)動的，查找對象時靜態(tài)的，此類問題就要復(fù)雜，因?yàn)樵诓檎疫^程中，汽車是移動的如果查詢結(jié)果延遲過高，那么查詢的準(zhǔn)確性就不高，所以其中存在很多問題值得研究.

（3）路上的行人搭乘出租車，這個問題也是最近鄰查詢問題，但是比上個問題還要復(fù)雜些，因?yàn)樾腥耸窃谛凶叩?，是動態(tài)的，而出租車是在行駛的，也是動態(tài)的，所以查詢者和查詢對象都是動態(tài)的，在查找過程及查找準(zhǔn)確度上都要負(fù)責(zé)的多.

基于位置的查詢（LBQs）的返回結(jié)果是基于某些位置信息.在無線技術(shù)中有兩種基本的方法訪問位置信息：請求訪問和周期廣播［7］.請求訪問使用的是一個基本的客戶－服務(wù)器模型，移動客戶（MC）提交一個查詢給服務(wù)器，服務(wù)器就會處理這個查詢并且通過點(diǎn)對點(diǎn)的專用信道返回一個結(jié)果給客戶.這種訪問請求數(shù)據(jù)方法適用于負(fù)載競爭信道小的系統(tǒng).然而，當(dāng)沒有上行信道時，移動客戶（MC）就不能發(fā)送查詢給服務(wù)器，更不能實(shí)時的獲得結(jié)果.還有，所有的查詢請求都是在中心服務(wù)器處理，這將導(dǎo)致很多問題：服務(wù)器將變成系統(tǒng)的瓶頸，所以系統(tǒng)性能會很低；服務(wù)器必須同時處理大量的查詢請求這將影響結(jié)果的實(shí)時性.為了克服以上缺點(diǎn)，周期廣播方法被提出，在周期廣播中數(shù)據(jù)項(xiàng)通過無線信道被周期廣播，移動客戶（MC）負(fù)責(zé)查詢處理.無需發(fā)送任何信息給服務(wù)器，客戶只需簡單的偵聽廣播信息來查找與自己查詢相關(guān)的數(shù)據(jù)，然后處理查找到的數(shù)據(jù)并自動的返回查詢結(jié)果即可.這種周期廣播方法相對來說非常適用于高負(fù)載系統(tǒng)，并且移動客戶可以分布式的自動處理.

當(dāng)然，有很多基于點(diǎn)對點(diǎn)方式進(jìn)行基于位置查詢的研究，但是性能不是很好，最近有很多研究者開始瞄準(zhǔn)適用周期廣播方式進(jìn)行基于位置查詢的研究.很多研究結(jié)果已經(jīng)出現(xiàn)在以下文獻(xiàn)中［8～14］.并且所有存在的基于周期廣播位置查詢方法都是用的歐氏空間，沒有人用在網(wǎng)絡(luò)空間.實(shí)際上移動客戶經(jīng)常會在某系網(wǎng)絡(luò)中移動，如路網(wǎng)、鐵路網(wǎng)、飛行網(wǎng)等.

在文獻(xiàn)［6］中，作者提出一種數(shù)據(jù)廣播環(huán)境下路網(wǎng)中最近鄰查詢處理的方法（NBNN），其中最主要的問題是如何分割基本的網(wǎng)絡(luò)和將網(wǎng)絡(luò)和其中的對象組織在一個序列包集合中，從而信息能夠在網(wǎng)絡(luò)中廣播.作者使用了網(wǎng)絡(luò)維諾圖（NVD），維諾圖包含很多多邊形，多邊形中的任何點(diǎn)的最近鄰都是多邊形的節(jié)點(diǎn)對象.作者就是通過維諾圖來構(gòu)建路網(wǎng)模型，然后作者又提出一種有效的方法叫NVD方格分割，把NVD分割成很多網(wǎng)格從而形成一個網(wǎng)格樹，叫NVD網(wǎng)格樹，從而保持每個單元的NVD結(jié)構(gòu).同時給出了GC－code編碼為樹中每個節(jié)點(diǎn)，只要給定一個空間的點(diǎn)，即可計算出其對應(yīng)的網(wǎng)格的GC－code編碼，然后以后序遍歷方式線性化樹中各葉子節(jié)點(diǎn)即格子編碼即可得到一個廣播序列.

當(dāng)然在無線廣播中，調(diào)諧時間和訪問時間是能量消耗和訪問延遲的兩個重要指標(biāo).因此使用索引結(jié)構(gòu)以使得移動客戶有選擇的偵聽廣播信息將有助于節(jié)省能量.在文獻(xiàn)［6］中作者提出一種基于NVD的分布式索引結(jié)構(gòu)，叫NVD－ID.這種索引允許最近鄰查詢可以在任意的時間開始執(zhí)行，并且每個查詢操作可以在一個廣播周期內(nèi)完成.同時，這種索引結(jié)構(gòu)也大大減少了能量消耗和訪問時間延遲.

文獻(xiàn)［6］中提出的NBNN方法主要有以下幾步完成：

（1）通過使用一個對象屬性標(biāo)記路網(wǎng)中每條邊，這些邊屬于維諾多邊形中的一個特定對象，即需要根據(jù)實(shí)際需要，根據(jù)實(shí)際對象構(gòu)建相應(yīng)的維諾圖.

（2）NVD方格分割，即將1）中建好的NVD圖分割成很多格子單元，把這些劃分的單元構(gòu)建一方格樹，即NVD方格樹，保持NVD結(jié)構(gòu)，特別是，NVD樹很好的平衡了大小和很好的位置保護(hù)行為.

（3）然后對NVD樹提出了一種數(shù)字編碼技術(shù)，即用二進(jìn)制對NVD圖中的每個格子單元即樹中所有節(jié)點(diǎn)進(jìn)行二進(jìn)制編碼，并且米格查詢客戶都可以通過自己的位置坐標(biāo)計算出其所在的格子單元，從而轉(zhuǎn)換為相應(yīng)的GC編碼.

（4）針對于移動客戶的能量消耗和訪問延遲，提出了一種比較好的索引方法，基于NVD分布式索引，這種索引方式不但使得每個客戶都可以隨時執(zhí)行自己的查詢并且都可以在一個廣播周期內(nèi)就可以得到相應(yīng)，同時大大減少了能量消耗和時間延遲.

但是盡管文獻(xiàn)［6］提出的方法新穎并且效率也很好，但是本人認(rèn)為很存在一些問題，首先存在以下一些局限性：

（1）查詢對象只考慮了一種類型對象，對多種類型對象并存時如何有效查詢，并且若對象很密集，此時若為每一對象分配一區(qū)域，將會使區(qū)域很小，從而會導(dǎo)致區(qū)域個數(shù)很大，那每個對象對應(yīng)的編碼就會越長，生成的樹也會越深，在轉(zhuǎn)換成一個廣播幀時，幀長會很大，也會導(dǎo)致廣播及接收能耗增大.

（2）移動客戶提出請求后有可能繼續(xù)移動，要判斷在等待延遲時間內(nèi)是否已經(jīng)運(yùn)動出了所在區(qū)域，若出了所在區(qū)域，則查詢將不準(zhǔn)確.同時只考慮了對靜態(tài)對象的查詢，未考慮對動態(tài)對象的查詢.

解決方法：

a.能否針對密集對象時不是為每個對象分配一區(qū)域，而是為一組相鄰的對象分配一個區(qū)域，從中選擇一個中心節(jié)點(diǎn)，負(fù)責(zé)其他信息的收集接收等工作.

b.針對編碼變長，能否對編碼進(jìn)行優(yōu)化，使編碼更短些，從而縮短幀長.

c.對移動客戶上安裝的傳感設(shè)備，能夠適量增加一些存儲空間用來存儲部分?jǐn)?shù)據(jù)，實(shí)現(xiàn)主動的通過鄰居節(jié)點(diǎn)信息進(jìn)行實(shí)時動態(tài)查詢.

d.在進(jìn)行劃分區(qū)域時，只考慮靜態(tài)情況，如何在動態(tài)增加某些對象時加快實(shí)時更新也是個問題.

e.能否進(jìn)行分布式的定位查找，以提高速率和實(shí)時性.

f.是否考慮傳感器也可以接收交通網(wǎng)中的任意一個移動客戶信息，從傳感器網(wǎng)絡(luò)的角度進(jìn)行查詢搜索信息，主動的發(fā)送和接收包.

2.4 無線廣播下連續(xù)近鄰查詢：此問題是本人針對上述文獻(xiàn)［6］中局限性2中的移動客戶提出請求后有可能繼續(xù)移動提出的，在基于位置查詢中連續(xù)近鄰查詢（CNNQ），此類查詢是在客戶從開始位置到目的地移動中連續(xù)查找離查詢位置最近的對象.與快照查尋只需評估一次相比，連續(xù)近鄰查詢（CNNQ）需要連續(xù)評估查詢結(jié)果直到滿足要求為止.連續(xù)近鄰（CNNQ）可以分為兩類：一類是靜態(tài)查詢移動對象，另一類是移動查詢移動對象.在文獻(xiàn)［11］中就針對第二類查詢即移動查詢移動對象進(jìn)行了研究，作者假設(shè)存在的移動對象集合和一個中心服務(wù)器用來檢測它們的位置信息并通過周期廣播它們的位置信息給分布在各個不同位置上的客戶.在移動連續(xù)近鄰查詢（MCNNQ）過程實(shí)際是，在客戶和查找對象都移動的情況下移動客戶連續(xù)的查找距離查詢位置最近的對象.在文獻(xiàn)［11］中，作者提出一種新的基于位置的三維查詢處理算法來支持無限網(wǎng)絡(luò)廣播環(huán)境下（MCNNQ）服務(wù)使用者和目標(biāo)對象都能移動.并且研究了同時執(zhí)行的性能問題、在移動對象和查詢增加情況下連續(xù)查詢問題.并且使用對象位置和移動速度定義了一保證區(qū)域（GR）.客戶在保證區(qū)域（GR）能確保最近鄰對象而不需等待和調(diào)諧廣播信道.此種方法是 Exponential Sequence Scheme with Guaranteed Region（ESS_GR），此方法適用于靜態(tài)和移動兩類查詢，具體步驟如下：

1）定義了保證區(qū)域（GR），實(shí)際是將查詢線分割成了一些分離的線，從而使得在每個保證區(qū)域（GR）中的點(diǎn)的最近鄰對象相同.保證區(qū)域（GR）使得移動客戶查找移動對象中找到準(zhǔn)確的答案.并且精心選擇調(diào)諧來節(jié)省移動客戶的能量資源.

2）ESS_GR算法支持無線廣播環(huán)境下動態(tài)連續(xù)的最近鄰查詢，并且對于很多客戶同時請求同一數(shù)據(jù)的查詢是非常適用.

文獻(xiàn)［11］確實(shí)是對文獻(xiàn)［6］中的局限性有了有力的補(bǔ)充，但文獻(xiàn)［11］在廣播建立索引及客戶能量消耗上沒有精心考慮，當(dāng)然如果能結(jié)合兩者優(yōu)點(diǎn)效果應(yīng)該會更好.同時對文獻(xiàn)［11］中盡管通過幾何方式得到保證區(qū)域（GR），但是在查詢線上仍存在一些盲區(qū)，當(dāng)然這也是不可避免的，能否尋求一種更好的方法使得盲區(qū)盡量小，是一個值得研究的問題；在已有的文獻(xiàn)中只考慮二維空間下的查詢，而三維空間下的查詢，研究甚少，事實(shí)上三維空間下的查詢將會更加有用如：飛行航線即為一三維空間下的查詢、海底潛艇的查詢等.

2.5 易錯無線數(shù)據(jù)廣播下分布式空間索引查詢的創(chuàng)建：此問題是本人針對上述文獻(xiàn)［6］中局限性1中對多種對象及容錯性方面進(jìn)行了探討，當(dāng)信息可用時，不僅僅是在正確的時間，而在正確的位置時，對于使用者來說也是非常重要的，當(dāng)然在基于位置數(shù)據(jù)訪問中，分布式索引（DSI）起著非常重要的作用，因?yàn)檫@種索引方式使得很多查詢路徑共享，從而使得查詢的容錯性大大提高，并且支持經(jīng)典的基于位置的快照和連續(xù)模型查詢，窗口查詢和kNN查詢等.窗口查詢是指查詢所有以一查詢點(diǎn)為中心的查詢窗口中的所有查詢對象，kNN查詢是指查詢查詢點(diǎn)最近的k個對象.在兩種情況下，查詢點(diǎn)可以是最近的用戶位置或者是預(yù)先的用戶移動軌跡.在文獻(xiàn)［14］中提出的DSI，考慮了三個方面因素：

1）性能需求上考慮了能量耗費(fèi)和訪問效率

2）本身的不可靠性和無線通信的易錯性

3）一般基于位置查詢的支持

考慮到客戶的移動性，不僅僅考慮了典型的查詢點(diǎn)固定的快照查詢，還考慮了查詢點(diǎn)按照預(yù)定軌跡移動的連續(xù)查詢.連續(xù)查詢用于客戶將來的移動是計劃好的情形下，DSI方法有很多的優(yōu)勢如下：

①它組織對象數(shù)據(jù)是以一定的線性順序.這樣自然的適合無線廣播數(shù)據(jù)媒介以提高索引效率和廣播任務(wù).

②它有一完全的分布式結(jié)構(gòu)允許查詢處理立即開始因而最小化了不必要的等待時間.這個性質(zhì)大大縮短了查詢數(shù)據(jù)的訪問延遲.

③它提供了對同一對象的多路徑查詢并且共享一般查詢路徑從而最小化了索引信息的帶寬負(fù)載.

④它在無線數(shù)據(jù)廣播本身易錯性通信環(huán)境下非?？煽浚蛻艨梢曰謴?fù)，而不用重新開始，在錯誤發(fā)生時查詢處理操作大大減少.

⑤它支持很多類型的基于位置的查詢，包括窗口查詢和kNN查詢.

在文獻(xiàn)［14］中，還有考慮多方向的擴(kuò)展DSI，DSI只考慮了同性質(zhì)類型的數(shù)據(jù)對象查詢，而未考慮多類型數(shù)據(jù)對象的查詢，并且在三維環(huán)境下查詢的處理會涉及到多類型數(shù)據(jù).并且要考慮復(fù)雜查詢下索引效率的提高及基本系統(tǒng)框架的構(gòu)建.并且可以把一些相關(guān)信息放在各個移動客戶上，因?yàn)楝F(xiàn)在內(nèi)存越來便宜，這樣就可以實(shí)現(xiàn)分布式的快速的高響應(yīng)的實(shí)時查詢.

3 結(jié)論

本文對移動時空數(shù)據(jù)庫中的一些技術(shù)及前沿方法進(jìn)行了簡要的介紹，主要從同步技術(shù)、數(shù)據(jù)廣播技術(shù)、基于位置的最近鄰查詢技術(shù)進(jìn)行了闡述，重點(diǎn)以文獻(xiàn)［6，11，14］介紹了基于位置的最近鄰查詢技術(shù)，并且提出了一些自己想法和有待于研究的問題，主要是能否將二維空間的查詢擴(kuò)展到三維空間中去，如何提高查詢的準(zhǔn)確度和實(shí)時性等都有待于研究者進(jìn)一步研究解決，并且三維空間的查詢應(yīng)用將會越來越廣泛，越來越迫切，總之，在移動時空數(shù)據(jù)庫中最近鄰查詢這個領(lǐng)域還有很多問題值得人們?nèi)ニ伎?，研究和?shí)踐.

［1］E Kayan，O Ulusoy.An Evaluation of Real－ Time Transaction Management Issues in Mobile Database systems［J］.The Computer Journal，1999，42（6）：501 －510

［2］錢希志，陳志泊.移動數(shù)據(jù)庫關(guān)鍵技術(shù)及其研究應(yīng)用［J］.微計算機(jī)信息，2010，26，（102）.

［3］肖迎元，劉云生，廖國瓊.移動實(shí)時數(shù)據(jù)庫系統(tǒng)綜述［J］.計算機(jī)工程與應(yīng)用，2004.35：173～177.

［4］黎娜，張慶吉.移動數(shù)據(jù)庫同步技術(shù)及應(yīng)用［J］.現(xiàn)代計算機(jī)，2011，05：76 ～78.

［5］吳海.移動數(shù)據(jù)庫同步技術(shù)及應(yīng)用［D］.博士論文，2010，11.

［6］Yanhong Li，Guohui Li.Searching Nearest Neighbors in Road Networks on the Air［J］.The Elsevier Jairnal，2011，12.

［7］S.Berchtold，D.A.Keim，H.P.Kriegel，and T.Seidl，“Indexing thesolution space：A new technique for nearest neighbor search in high － dimensional space”［J］.IEEE TKDE 2000，12（1），pp.45～57.

［8］S.E.Hambrusch，E.Liu，W.G.Aref，and S.Prabhakar，“Query process － ing in broadcasted spatial index trees”，in SSTD（2001），pp.502～521.

［9］Chuan－Ming Liu and Shu－Yu Fu，“Effective protocols for knn search onbroadcast multi－dimensional index trees”［J］.Information Systems，2008，33（1），pp.18 ～35.

［10］K.Park，M.Song，and C.－S.Hwang，“Adaptive data dissemination schemes for location－awaremobile services”［J］.Journal of Systems and Software，2006，79（5），pp.674 ～688.

［11］ Kwangjin Park，Hyunseung Choo，and Patrick Valduriez，“A scalable energy － efficient continuous nearest neighbor search in wireless broadcast systems”［J］.in Wireless Netw ，2010：16，pp.1011～1031.

［12］B.Zheng，W.－C.Lee，and D.L.Lee，“Search continuous nearest neighbors on the air”，in Proc.MobiQ-uitous，2004，pp.236 ～245.

［13］B.Zheng，W.－C.Lee，and D.L.Lee，“On searching continuous k nearest neighbors in wireless data broadcast systems”［J］.in IEEE Transactions on Mobible Computing，2007，6（7），pp.748 ～761.

［14］B.Zheng，W.－ C.Lee，D.L.Lee，C.K.Lee，and M.Shao，“A distributedspatial index for error－ prone wireless data broadcast”［J］.in The VLDB Journal ，2009，18，pp.959～986.