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