吳春輝，徐萬和

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

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

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

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

1 移動(dòng)數(shù)據(jù)庫(kù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

解決方法：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

④它在無線數(shù)據(jù)廣播本身易錯(cuò)性通信環(huán)境下非?？煽?，客戶可以恢復(fù)，而不用重新開始，在錯(cuò)誤發(fā)生時(shí)查詢處理操作大大減少.

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

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

3 結(jié)論

本文對(duì)移動(dòng)時(shí)空數(shù)據(jù)庫(kù)中的一些技術(shù)及前沿方法進(jìn)行了簡(jiǎn)要的介紹，主要從同步技術(shù)、數(shù)據(jù)廣播技術(shù)、基于位置的最近鄰查詢技術(shù)進(jìn)行了闡述，重點(diǎn)以文獻(xiàn)［6，11，14］介紹了基于位置的最近鄰查詢技術(shù)，并且提出了一些自己想法和有待于研究的問題，主要是能否將二維空間的查詢擴(kuò)展到三維空間中去，如何提高查詢的準(zhǔn)確度和實(shí)時(shí)性等都有待于研究者進(jìn)一步研究解決，并且三維空間的查詢應(yīng)用將會(huì)越來越廣泛，越來越迫切，總之，在移動(dòng)時(shí)空數(shù)據(jù)庫(kù)中最近鄰查詢這個(gè)領(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］錢希志，陳志泊.移動(dòng)數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)及其研究應(yīng)用［J］.微計(jì)算機(jī)信息，2010，26，（102）.

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

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

［5］吳海.移動(dòng)數(shù)據(jù)庫(kù)同步技術(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.