摘 要：隨著互聯(lián)網(wǎng)絡(luò)技術(shù)和無線通信技術(shù)的發(fā)展，嵌入式移動數(shù)據(jù)庫技術(shù)已成為目前數(shù)據(jù)庫領(lǐng)域的一個新的研究分支。文中分析了嵌入式移動數(shù)據(jù)庫的體系結(jié)構(gòu)，系統(tǒng)地闡述了嵌入式移動數(shù)據(jù)庫的關(guān)鍵技術(shù)，并完善了相應(yīng)的解決方案。 關(guān)鍵字：嵌入式系統(tǒng); 體系結(jié)構(gòu); 移動數(shù)據(jù)庫 1 引言 　　隨著嵌入式系統(tǒng)和無線通信網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，出現(xiàn)了移動辦公、移動通信等嶄新的移動服務(wù)理念，人們對獲取信息和使用信息的場合、時間、方式及方法提出了越來越多的需求。在這種應(yīng)用需求推動的背景下，嵌入式移動數(shù)據(jù)庫應(yīng)運而生，成了近年來數(shù)據(jù)庫發(fā)展的一個重要分支。本文對嵌入式移動數(shù)據(jù)庫系統(tǒng)進(jìn)行了深入的研究，完善和解決了嵌入式移動數(shù)據(jù)庫系統(tǒng)的關(guān)鍵技術(shù)。 2 嵌入式移動數(shù)據(jù)庫的系統(tǒng)模型 　　在傳統(tǒng)的分布式計算系統(tǒng)中，各個計算節(jié)點是通過固定網(wǎng)絡(luò)連接并保持網(wǎng)絡(luò)的技術(shù)連接性的，而移動計算系統(tǒng)改變了這種假設(shè)條件。移動計算系統(tǒng)是固定節(jié)點和移動節(jié)點構(gòu)成的分布式計算系統(tǒng)。移動計算的網(wǎng)絡(luò)環(huán)境具有鮮明的特點：移動性、斷接性、帶寬多樣性、可伸縮性、弱可靠性、網(wǎng)絡(luò)通信的非對稱性、電源能力的局限性等。移動環(huán)境中的分布式數(shù)據(jù)庫就是移動數(shù)據(jù)庫。它是傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)的擴(kuò)展，可以看作客戶與固定服務(wù)器節(jié)點動態(tài)連接的分布式系統(tǒng)。移動數(shù)據(jù)庫系統(tǒng)的模型[2][6]如圖1所示。 　　其中，移動客戶機(jī)MC（Mobile Client）包括便攜式電腦、PDA等;MSS（Mobile Support Station）支持移動計算的固定節(jié)點，具有無線通信接口;FH（Fixed Host）沒有無線通信接口，安裝有數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)。 3 嵌入式移動數(shù)據(jù)庫的關(guān)鍵技術(shù) 　　移動數(shù)據(jù)庫涉及的理論和技術(shù)涵蓋了當(dāng)今通信和計算機(jī)發(fā)展的最新的成果，其中，在移動環(huán)境下如何進(jìn)行數(shù)據(jù)管理是實現(xiàn)移動數(shù)據(jù)庫的關(guān)鍵。在移動數(shù)據(jù)庫系統(tǒng)設(shè)計中，需要考慮諸多在傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)中不需要考慮的問題，如客戶端的移動、客戶端與網(wǎng)絡(luò)的頻繁斷接、網(wǎng)絡(luò)條件多樣性、網(wǎng)絡(luò)通信非對稱、移動計算部件電源容量有限、可靠性低、伸縮性高、客戶端與服務(wù)器數(shù)據(jù)的不一致性、移動數(shù)據(jù)查詢等問題。為了解決上述問題，關(guān)于數(shù)據(jù)復(fù)制/緩存技術(shù)、數(shù)據(jù)廣播技術(shù)、位置相關(guān)的查詢優(yōu)化等技術(shù)的研究，在移動數(shù)據(jù)庫中具有特別重要的意義。這些技術(shù)都是解決由于客戶端移動而帶來的一系列問題的關(guān)鍵性技術(shù)。下面對移動數(shù)據(jù)庫所涉及的幾個關(guān)鍵性技術(shù)進(jìn)行詳細(xì)的闡述。 　　3.1 數(shù)據(jù)復(fù)制/緩存技術(shù) 　　該技術(shù)是解決移動數(shù)據(jù)庫斷接性的關(guān)鍵技術(shù)。傳統(tǒng)的復(fù)制/緩存技術(shù)都是假設(shè)客戶機(jī)和服務(wù)器之間是經(jīng)常保持連接的，并基于這個前提來維護(hù)一致性。這在移動計算中是不適用的。目前，人們已經(jīng)提出了多種移動復(fù)制算法，最典型的一個算法是:三層復(fù)制體系結(jié)構(gòu)（Three-Tier Replication Architecture，簡稱TTR結(jié)構(gòu)），下面我們就以TTR為例來介紹復(fù)制。三層復(fù)制體系結(jié)構(gòu)[3]，如圖2所示。 　　第一層復(fù)制是指服務(wù)器之間利用傳統(tǒng)的復(fù)制技術(shù)在固定高速網(wǎng)絡(luò)中所進(jìn)行的復(fù)制，稱之為“服務(wù)器級復(fù)制”。為了支持移動計算環(huán)境，一般采用一種弱一致性服務(wù)器級復(fù)制機(jī)制（ Weakly Consistent Server Replication，簡稱WCSR）。這種策略讓每個復(fù)制服務(wù)器都支持查詢與更新操作，并且允許各個復(fù)制之間存在暫時的不一致。因此，一個用戶在訪問數(shù)據(jù)庫時，只需要訪問一個復(fù)制服務(wù)器即可，而且不僅可以執(zhí)行查詢事務(wù)，還支持更新事務(wù)。為了降低通信開銷，提高可靠性，WCSR采用了一種周期成對同步的方式，即每個服務(wù)器周期地選擇另一個服務(wù)器，兩個服務(wù)器之間交換各自的暫時事務(wù)日志，經(jīng)過有限次的成對同步過程，最終使所有數(shù)據(jù)庫狀態(tài)達(dá)成一致。 　　第二層復(fù)制是指服務(wù)器利用無線網(wǎng)絡(luò)固有的廣播能力將數(shù)據(jù)庫中經(jīng)常被大部分用戶訪問的公共熱點數(shù)據(jù)組織起來，經(jīng)由MSS向無線網(wǎng)絡(luò)單元內(nèi)的所有MC廣播，這實際上是在無線廣播信道上做數(shù)據(jù)復(fù)制，稱之為“空中復(fù)制”，空中復(fù)制充分利用了無線網(wǎng)絡(luò)非對稱性的特點。首先，因為無線網(wǎng)絡(luò)特有的廣播能力與普通網(wǎng)絡(luò)中的廣播顯著不同，它可以支持大量MC同時接收，而且不管接收的客戶數(shù)有多少，MSS的廣播代價并不改變，這就允許大規(guī)模的移動用戶同時訪問被廣播的熱點數(shù)據(jù)，極大地提高系統(tǒng)的可伸縮性;其次，由于MC可以從空中復(fù)制取得常用的熱點數(shù)據(jù)，使得其向服務(wù)器發(fā)送訪問請求的頻率也大幅減少，甚至沒有必要再與服務(wù)器聯(lián)機(jī)，這不僅可以使MC更有效地使用上行鏈路或避免代價較高的無線通信，而且減少了服務(wù)器處理每個聯(lián)機(jī)MC的開銷，進(jìn)而使服務(wù)器可以同時接收更多聯(lián)機(jī)MC的訪問?？梢?，空中復(fù)制是一項開銷不大，但卻很有實際應(yīng)用意義的技術(shù)。 　　第三層復(fù)制是為了支持移動用戶的斷接操作，MC利用本身的處理和存儲能力緩存數(shù)據(jù)庫中部分?jǐn)?shù)據(jù)，稱之為“客戶機(jī)緩存”。由于MC的存儲容量無法與數(shù)據(jù)庫服務(wù)器相比，而且普通用戶也不需要在斷接期間訪問整個數(shù)據(jù)庫系統(tǒng)，因此在TTR體系中一般采用一種支持?jǐn)?shù)據(jù)庫的子集緩存的MC緩存機(jī)制，稱作MCC（Mobile Client Caching）機(jī)制。MCC緩存機(jī)制的核心是緩存管理器，它在不同的網(wǎng)絡(luò)連接條件下具有三種不同的工作狀態(tài)，即聯(lián)機(jī)狀態(tài)、脫機(jī)狀態(tài)、集成狀態(tài)。在聯(lián)機(jī)狀態(tài)下，緩存管理器將MC用戶的事務(wù)轉(zhuǎn)交給服務(wù)器執(zhí)行，并負(fù)責(zé)建立與維護(hù)MC的緩存:在脫機(jī)狀態(tài)下，緩存管理器仿真服務(wù)器的功能，并將用戶更新事務(wù)記錄在本地的脫機(jī)事務(wù)日志中:在集成狀態(tài)下，緩存管理器與服務(wù)器合并，并回到聯(lián)機(jī)狀態(tài)。 　　3.2 數(shù)據(jù)廣播 　　通俗地講，數(shù)據(jù)廣播[4]是指在移動計算環(huán)境中，利用客戶機(jī)與服務(wù)器通信的不對稱性，以周期性廣播的形式向客戶機(jī)發(fā)送數(shù)據(jù)。其最大的優(yōu)點是，廣播開銷不依賴移動用戶數(shù)量的變化而變化，借助數(shù)據(jù)廣播，可以在一定程度上解決移動數(shù)據(jù)庫系統(tǒng)的斷接問題。 　　數(shù)據(jù)廣播技術(shù)研究的關(guān)鍵問題是:數(shù)據(jù)廣播調(diào)度問題。而數(shù)據(jù)廣播調(diào)度的關(guān)鍵是采用什么樣的調(diào)度算法，如何確定廣播的周期。日前，有關(guān)數(shù)據(jù)廣播調(diào)度的研究主要集中在訪問時間和調(diào)諧時間的優(yōu)化問題上，但存在較大的局限性，如只考慮訪問時間的優(yōu)化或調(diào)諧時間的優(yōu)化，不能較好地將兩者結(jié)合起來，且現(xiàn)有的數(shù)據(jù)廣播的調(diào)度機(jī)制大都缺乏可操作性，不支持移動數(shù)據(jù)庫系統(tǒng)的實際應(yīng)用。針對這些不足，數(shù)據(jù)廣播技術(shù)研究中有必要從理論上分析訪問時間和調(diào)諧時間的最優(yōu)值，并以理論分析為指導(dǎo)，提出一種能在優(yōu)化調(diào)諧時間的同時仍保持較低訪問時間的數(shù)據(jù)廣播調(diào)度算法。 　　數(shù)據(jù)廣播的調(diào)度可以看作一個帶寬分配問題:給定所有客戶機(jī)訪問數(shù)據(jù)項的概率分布，服務(wù)器試圖確定每個數(shù)據(jù)項在廣播帶寬中所占的最佳比例，然后根據(jù)這個比例產(chǎn)生廣播程序。一種最簡單的調(diào)度方法是將所有待廣播的數(shù)據(jù)項簡單地并在一起，在每個廣播周期里任意數(shù)據(jù)項都出現(xiàn)一次且只有一次，且每個數(shù)據(jù)項的平均訪問時間都是相同的（即廣播周期的一半），這種調(diào)度稱為平坦調(diào)度。如果在一個廣播調(diào)度中，各個數(shù)據(jù)項出現(xiàn)的次數(shù)不一定為1，即所占的帶寬比例不一定相同，則將該調(diào)度稱作非平坦調(diào)度。但是，僅僅確定各數(shù)據(jù)項的帶寬比例是不夠的，如果在一個廣播周期中數(shù)據(jù)項的間距（即兩次出現(xiàn)之間的時間差）不均勻，那么非平坦調(diào)度并不能產(chǎn)生好的效果。這里可以通過一個簡單的例子說明這一點。如圖3所示，包含3個數(shù)據(jù)項的數(shù)據(jù)廣播可以有3種不同的調(diào)度方式:程序a是平坦調(diào)度;而程序b和程序c是非平坦調(diào)度，其中數(shù)據(jù)項d1在一個廣播周期中出現(xiàn)兩次，而數(shù)據(jù)項d2和d3只出現(xiàn)一次。程序b是一種偏斜調(diào)度，因為在一個周期里，數(shù)據(jù)項d1的兩次出現(xiàn)連在一起，使得d1的廣播間隔時間不均勻。程序a則是一種均勻調(diào)度，其廣播周期中每個數(shù)據(jù)項在廣播帶寬中所占的間隔時間都是均勻的，這樣，數(shù)據(jù)項dl好像存在一個速度比d2和d3快一倍的磁盤上，這種調(diào)度稱為多盤調(diào)度（Multi-Disk schedule）。假設(shè)移動客戶機(jī)數(shù)據(jù)項訪問請求的到達(dá)是完全隨機(jī)的，即可能落在數(shù)據(jù)廣播周期內(nèi)的任意時刻.表1列出了在不同的數(shù)據(jù)項訪問概率分布下三種調(diào)度程序的平均訪問時間。 [align=center] [/align] 　　表1說明了三個問題：首先，當(dāng)數(shù)據(jù)項訪問概率均勻分布時（即為1/3）平坦調(diào)度的平均訪問時間最低。這說明多盤調(diào)度技術(shù)不能隨意使用，在某些場合下可能得不償失。其次，當(dāng)數(shù)據(jù)項訪問概率分布趨向偏斜時，非平坦調(diào)度的性能將優(yōu)于平坦調(diào)度。最后，在兩種非平坦調(diào)度中，多盤調(diào)度的性能都將優(yōu)于偏斜調(diào)度，這說明均勻的非平坦調(diào)度可以獲得更好的性能。 　　多盤調(diào)度算法構(gòu)造一個廣播調(diào)度程序的過程為： 　?。?）將所有數(shù)據(jù)對象按照訪問概率遞減次序排序。 　?。?）將這些數(shù)據(jù)對象依次分割到K個相鄰的租，稱為“磁盤”。定義磁盤Bi的容量Ci為磁盤對象的個數(shù)。 　?。?）確定各盤的相對廣播頻率fi，即各盤對象在廣播中所占的帶寬之比。fi必須是互質(zhì)的整數(shù)，i=1，2，……, k。 　?。?）產(chǎn)生廣播調(diào)度程序。 　　● 將每個盤分割成若干塊。首先，求得所有盤的廣播頻率的最小公倍數(shù)LCM;然后,將每個盤Bi分割為num_chunks（i）=LCM/fi個相同大小的塊,記為Cij ，j=1，……，num_chunks（i）。若Bi不能整分，則在不滿的塊中填充空閑數(shù)據(jù)。 　　● 按如下程序交錯廣播各盤的塊，生成廣播調(diào)度。 　　For（i=0; i 　　 For（j=1; j=k; j++） 　　 廣播塊 C[sub]j（i mod num_chunks（j））[/sub]; 　　3.3 位置相關(guān)查詢優(yōu)化 　　在移動數(shù)據(jù)庫中，存在著與位置相關(guān)信息的查詢及更新。查詢通常是與位置相關(guān)的，即使是同一個問題，在不同的地方，所得查詢結(jié)果是不同的，如“最近的醫(yī)院在哪里?”。移動查詢優(yōu)化技術(shù)是指在傳統(tǒng)分布式數(shù)據(jù)庫查詢優(yōu)化技術(shù)的基礎(chǔ)上，利用多種方法，消除帶寬多樣性、斷接等因素造成的影響，使查詢引擎能夠根據(jù)當(dāng)前可用網(wǎng)絡(luò)條件采取恰當(dāng)?shù)膬?yōu)化策略;同時，針對移動計算機(jī)有限電源能力，合理地組織本地數(shù)據(jù)庫管理、遠(yuǎn)程數(shù)據(jù)庫訪問等耗電能較多的操作，達(dá)到節(jié)能目的，延長關(guān)鍵數(shù)據(jù)的可用時間。 　　采用基于分割的地址更新策略時，由位置服務(wù)器維護(hù)的移動用戶對象包含以下數(shù)據(jù)成員和方法： 　　分割集合——記錄MSS的分割情況，例如｛Cell1,Cell2｝,｛Cell3,Cell4,Cell5｝; 　　LOC——記錄移動用戶最近報告的地址（無線單元的ID），例如Cell1; 　　ERR——移動用戶當(dāng)前所在的分割，例如，若LOC=Cell1,則ERR=｛Cell1,Cell2｝; 　　loc（）——一個方法，用于返回該用戶的實際地址，即上面介紹的地址查詢過程。 　　在移動查詢的應(yīng)用中，有各種各樣涉及地址的查詢，例如“請尋找一名校園附近的醫(yī)生”，“查找X，Y，Z，這三人都在同一條公路上，且Y在X與Z之間”，等等。一般地，可以把這一類地址相關(guān)查詢表示為： 　　SELECT x1,x2,…，xn 　　FROM Users 　　WHERE（x1.loc=11∧…∧xn.loc=1n）∧C（11,…，1n）∧W（x1,…,xn） 　　其中C（11,…，1n）是關(guān)于地址11，…，1n的n元約束條件，而W（x1,…,xn）是關(guān)于對象x1,x2,…，xn非地址屬性的n元約束條件，Users是所有移動用戶的集合。 　　這種位置相關(guān)查詢需要檢查各個對象的實際地址是否滿足約束條件而這些實際地址必須進(jìn)行地址查詢才能得到,因為位置服務(wù)器只提供分到一級不精確的地址。因此，要求得位置相關(guān)查詢的最終答案，必須先查詢足夠的精確地址信息。若對這一類查詢進(jìn)行適當(dāng)?shù)膬?yōu)化，可以大大減少查詢地址信息所需的通信開銷。 4 結(jié)束語 　　嵌入式移動數(shù)據(jù)庫將隨著各種移動設(shè)備、智能計算設(shè)備、嵌入式設(shè)備的發(fā)展而迅速發(fā)展。它將在未來的軍事、航空、國土資源管理、移動醫(yī)療等領(lǐng)域中扮演越來越重要的角色。嵌入式移動數(shù)據(jù)庫是一個嶄新的研究課題，至今還有許多問題有待解決，在移動數(shù)據(jù)庫技術(shù)逐步走向成熟的時候，必將產(chǎn)生巨大的商業(yè)和社會價值。 本文作者創(chuàng)新點： 　　鑒于移動計算環(huán)境中客戶機(jī)與服務(wù)器通信的不對稱性和數(shù)據(jù)傳輸?shù)臄嘟有詥栴}，筆者提出了三層復(fù)制體系結(jié)構(gòu)和多盤調(diào)度算法，并對部分問題探討了其初步的解決方式。 參考文獻(xiàn)： 　　[1]D Barara. Mobile computing and database — A survey. IEEE Trans on Knowledge and Data Engineering. 1999,11（1）:108～117. 　　[2]王珊 ,丁治明. 移動計算中的移動數(shù)據(jù)庫[N]. 微電腦世界, 2001,8.25 　　[3]胡虛懷，鄭若忠.移動數(shù)據(jù)庫及其關(guān)鍵技術(shù)[J]. 計算機(jī)系統(tǒng)應(yīng)用，2000,5（1）:29～32. 　　[4]王磊，邵時.移動數(shù)據(jù)庫中廣播技術(shù)的研究：[碩士學(xué)位論文][D]. 上海：華東師范大學(xué)計算機(jī)科學(xué)技術(shù)系，2004. 13～15. 　　[5]李東，曹忠升. 移動數(shù)據(jù)庫技術(shù)研究綜述[J]. 計算機(jī)應(yīng)用研究， 2000,（10）:4～7 　　[6]牛立新，關(guān)永，劉旭敏. 嵌入式移動數(shù)據(jù)庫研究[J], 微計算機(jī)信息， 2006，第22卷第1-2期，85-87頁轉(zhuǎn)251頁.