摘  要： 為滿足移動自組網(wǎng)（MANETS）多級事務(wù)處理的安全性和并發(fā)性要求,，將多版本兩段鎖協(xié)議運用到MANETS多級事務(wù)中。該協(xié)議有效地解決了由于競爭產(chǎn)生的錯誤的事務(wù)調(diào)度以及安全問題,。模擬仿真結(jié)果表明,，多版本兩段鎖協(xié)議在延遲截至?xí)r間率和重啟動率方面比單一的多版本協(xié)議或者單一的兩段鎖協(xié)議都要低。
關(guān)鍵詞： MANET,；多級安全,；并發(fā)控制；多級事務(wù)

　移動自組網(wǎng)MANETS（Mobile Ad Hoc Networks）是由多個移動節(jié)點通過無線鏈路相連接，具有時變拓撲結(jié)構(gòu)的一個多跳,、臨時性自治系統(tǒng),。MANETS中的數(shù)據(jù)庫系統(tǒng)是由許多移動主機組成的動態(tài)分布式數(shù)據(jù)庫系統(tǒng)。通常分布式數(shù)據(jù)庫中總是有若干個事務(wù)在運行,，這些事務(wù)可能并發(fā)地存取相同的數(shù)據(jù),。當(dāng)數(shù)據(jù)庫中有多個事務(wù)并發(fā)運行時，系統(tǒng)必須對并發(fā)事務(wù)之間的相互作用加以控制,，即通過并發(fā)控制機制來實現(xiàn),。然而，由于在MANET網(wǎng)絡(luò)中節(jié)點到處移動導(dǎo)致網(wǎng)絡(luò)拓撲結(jié)構(gòu)頻繁變化,，使得很多有線網(wǎng)絡(luò)中的并發(fā)技術(shù)在MANET網(wǎng)絡(luò)中行不通,。例如鎖機制或時間戳機制，這些并發(fā)控制機制被應(yīng)用到MANET的多級事務(wù)時,將會產(chǎn)生很多問題,，如隱通道,、高級事務(wù)被餓死和檢索異常等[1]。因此解決MANETS中多級事務(wù)的并發(fā)控制具有重要的意義,。
    MANETS中的數(shù)據(jù)庫管理系統(tǒng)（DBMS）是一個由不同訪問權(quán)限的用戶共享的,、包含多安全等級數(shù)據(jù)的安全系統(tǒng)。系統(tǒng)中的每一個數(shù)據(jù)項具有其安全等級,，并且每一個用戶被賦予不同的訪問權(quán)限,。由于這些特點，并發(fā)執(zhí)行的事務(wù)可能導(dǎo)致不同的主體為了獲取數(shù)據(jù)而產(chǎn)生競爭,，進而競爭會導(dǎo)致安全問題,，于是就要求DBMS對并發(fā)操作進行正確調(diào)度[2]，即允許非沖突的事務(wù)并行執(zhí)行,，而沖突的事務(wù)必須被串行化,，即實現(xiàn)可串行化調(diào)度,。
    為保證MANETS中多級安全數(shù)據(jù)庫的完整性和一致性,，本文提出一種運用在MANET中的多版本兩段鎖并發(fā)控制協(xié)議。
1 多級事務(wù)
    首先,，看一個多級事務(wù)的例子：
    T1：R（x,U,S）  W（y,S,S）
    這里R（x,U,S）表示具有秘密密級的主體在具有公開安全級的對象x上的一個讀操作,；同樣，W（y,S,S）表示具有秘密密級的主體在具有秘密安全級的對象y上的一個寫操作,。對于這類多級事務(wù),，定義被簡化為如下形示：
    T1(S):  R（x,U）   W(y,S）
這個主體的分類級別與事務(wù)名有關(guān)聯(lián)。
1.1 多級事務(wù)處理系統(tǒng)
    目前多級安全事務(wù)處理系統(tǒng)有4種主要的體系結(jié)構(gòu)：基于完整性鎖的體系結(jié)構(gòu),、基于內(nèi)核化的體系結(jié)構(gòu),、基于數(shù)據(jù)復(fù)制的體系結(jié)構(gòu)和基于可信主體的體系結(jié)構(gòu)。這里以基于可信主體的體系結(jié)構(gòu)為例，由DBMS自身實現(xiàn)強制訪問控制,。要求運行在多級安全局域網(wǎng)上,，通過安全網(wǎng)絡(luò)進行通信，所有對數(shù)據(jù)庫的訪問必須通過可信DBMS,，DBMS在多個文件中存儲多級數(shù)據(jù)庫,。在可信主體體系結(jié)構(gòu)中實現(xiàn)多級安全的事務(wù)處理所遵循的機制如圖1所示。

    圖中事務(wù)管理器TM(Transaction Manager)由可信事務(wù)管理器和各安全級上的不可信事務(wù)管理器組成,。事務(wù)管理器負責(zé)管理所有事務(wù)的執(zhí)行,，事務(wù)的每一個操作都需要事務(wù)管理器的調(diào)解。對于單級事務(wù),，系統(tǒng)將它發(fā)送給該安全級上的不可信事務(wù)管理器進行處理,。對于多級事務(wù)，事務(wù)管理器用單級事務(wù)的處理機制來實現(xiàn)多級事務(wù)的處理,。系統(tǒng)首先將多級事務(wù)發(fā)送給可信事務(wù)管理器,，然后可信事務(wù)管理器將多級事務(wù)劃分為單安全級的子事務(wù)，將這些子事務(wù)分別發(fā)送給相應(yīng)安全級的不可信事務(wù)管理器,?？尚沛i管理器負責(zé)安全鎖協(xié)議的實現(xiàn)，它的主要功能是提供對數(shù)據(jù)項的加鎖和解鎖操作,?？尚盼募芾砥鞴芾韺?shù)據(jù)項的物理訪問。
1.2 一種安全調(diào)度框架
    要實現(xiàn)一個多級事務(wù)調(diào)度的安全性能需實現(xiàn)以下兩方面安全性：
    （1）調(diào)度協(xié)議的安全性,；
    （2）執(zhí)行的安全性,。
    本文只關(guān)注第一部分,通過分析協(xié)議，可以估計一個調(diào)度的內(nèi)在的安全性,。無需考慮調(diào)度的執(zhí)行就可以評估調(diào)度,。不安全的調(diào)度協(xié)議能夠在執(zhí)行之前被發(fā)現(xiàn)。如果調(diào)度協(xié)議是安全的,，則可以考慮對執(zhí)行問題做分析,；否則，很可能將對協(xié)議的分析簡化為對執(zhí)行情況的分析,。
1.3 多版本調(diào)度
    在數(shù)據(jù)庫中,，多版本調(diào)度允許一個元素有多個版本。這種特征降低了對一個元素的爭奪,。一個多版本調(diào)度產(chǎn)生的調(diào)度表稱為一個完整的調(diào)度時間表,，表示為（s，V）,。其中s代表輸出操作,，V代表版本類型,。它映射了輸出操作s與被訪問元素版本V之間的關(guān)系。其中版本V有3種類型：(1)到寫版本的先前操作的參考,；(2)到新版本的參考,，即寫操作創(chuàng)建一個新版本；(3)到空版本的參考,，即一個元素的寫操作會被丟棄,。當(dāng)操作到達時，調(diào)度程序會做出3個基本決定：(1)操作是否可以立即執(zhí)行,；(2)讀操作或?qū)懖僮鞯膶嶓w是什么版本,；(3)調(diào)度是否可以繼續(xù)。而調(diào)度程序會根據(jù)本身的間隔狀態(tài)做出決定,。
    現(xiàn)在,，定義一種調(diào)度程序，把這個程序之前的輸出操作定義為調(diào)度狀態(tài),，這里只討論調(diào)度程序的輸出操作,，不考慮為讀或?qū)懖僮鞣峙浒姹尽?br />     定義1 一個調(diào)度程序是輸出狀態(tài)等價,當(dāng)且僅當(dāng)任意兩個狀態(tài)st1、st2有各自的輸出（s1,，V1）,、（s2，V2）,，如果s1等于s2,，則s1對一個即將被調(diào)度的程序的操作決策與s2對該程序做出的操作決策是相同的。換言之,，一個輸出狀態(tài)等價調(diào)度,，如果兩個不同狀態(tài)調(diào)度的輸出操作是相同的，則這兩個狀態(tài)是等價的,。這意味著到達的操作即將被調(diào)度,，但發(fā)生了延遲，不過不影響調(diào)度程序所做的決定,。
    現(xiàn)在定義一個輸出狀態(tài)等價的弱版本,。在這種情況下，輸出操作僅決定帶有決策的調(diào)度行為,。
    定義2  一個調(diào)度程序是輸出調(diào)度沖突,當(dāng)且僅當(dāng)任意兩個狀態(tài)st1,、st2有各自的輸出（s1，V1）,、（s2，V2）,。如果s1等于s2,，則s1對一個即將被調(diào)度的程序的操作決策與s2對該程序做出的操作決策是相同的。
    如圖2所示的簡單調(diào)度模型中，操作從左邊輸入,，右邊輸出,。如果一個操作不能被立即調(diào)度，它將被排在隊列中,。調(diào)度問題主要關(guān)注事務(wù)操作的順序,，以便保持正確性，并允許同一時間的并發(fā)性,。如果兩個事務(wù)之間出現(xiàn)沖突,，就將事務(wù)串行化。

2 多版本兩段鎖協(xié)議
    參考文獻[3]提出了一種使用多版本數(shù)據(jù)的安全的并發(fā)控制機制,。當(dāng) Ti試圖寫一個數(shù)據(jù)對象x時發(fā)現(xiàn)Ts已經(jīng)在x上請求了一個讀鎖,，Ti就創(chuàng)建了x的一個新的版本。因為通過給每一個多級事務(wù)一個不同的版本已經(jīng)解決了沖突,， 所以就避免了隱通道的創(chuàng)建,。然而，這樣做帶來了新的問題,，即高級事務(wù)的讀操作讀到的可能是不一致的版本,，即所謂的檢索異常。但是在兩段鎖協(xié)議中,，一個事務(wù)應(yīng)當(dāng)在確定其不再需要其他加鎖的情況后才釋放所持有的鎖,。于是下面提到的多版本兩階段封鎖協(xié)議可以解決檢索異常問題。
2.1 多版本兩段鎖協(xié)議概述
    每一個只讀事務(wù)Ti發(fā)出讀數(shù)據(jù)項Q時,，返回值是小于Ts(Ti)時間戳的最大版本Qk的內(nèi)容,。這是因為一個事務(wù)應(yīng)讀取在它之前的最近版本。更新事務(wù)執(zhí)行兩段鎖協(xié)議,，在提交之前不釋放任何鎖,，事務(wù)可以按其提交的順序串行化，更新事務(wù)Ti,。讀取數(shù)據(jù)項Q時,，Ti在獲得數(shù)據(jù)項Q上的共享鎖后讀取Q最新版本的值。更新事務(wù)Ti,。想寫數(shù)據(jù)項Q時,，Ti首先要獲得數(shù)據(jù)項Q上的排它鎖，然后為Q創(chuàng)建一個新版本,，寫操作在新版本上進行,。新版本的時間戳初值為∞，它大于任何可能的時間戳值,。在創(chuàng)建此版本的事務(wù)Ti完成之前,，阻止其他只讀事務(wù)對此版本進行讀操作,。當(dāng)更新事務(wù)Ti完成后，Ti將它創(chuàng)建的每一個版本的時間戳設(shè)為Counter+1,。然后Ti將Counter增加1,。在Counter增加之前啟動的只讀事務(wù)將看到被Ti更新之前的值。無論是哪種情況,，只讀事務(wù)均不必等待加鎖[4],。
2.2 多版本兩段鎖調(diào)度算法
    多版本調(diào)度允許同一實體有多個版本，通過限制訪問一個實體的競爭加強并發(fā)性,。這種競爭會引起不安全調(diào)度或者不安全恢復(fù),。這里考慮到的調(diào)度之一是沖突集調(diào)度。這個調(diào)度的輸出是有序沖突調(diào)度的集合,。有序沖突的定義如下：
    定義3 一個調(diào)度是有序沖突的,，當(dāng)且僅當(dāng)它能通過一系列0次或者多次轉(zhuǎn)換變成一個有序調(diào)度。在這些轉(zhuǎn)換中,，任何一對來自不同事務(wù)的相鄰步驟可以互換,除非它們相沖突,。即兩個事務(wù)沖突，如果它們訪問相同實體并且這兩個實體中至少有一個正在執(zhí)行寫操作,。接下來定義一種調(diào)度屬性——安全級別有序,。
    定義4  一個調(diào)度是安全級別有序的,當(dāng)且僅當(dāng)調(diào)度中所有的事務(wù)對p和q共享一個單一主題的分類等級，且在一個序列順序中p緊跟q或q緊跟p,。
    根據(jù)上述描述,，設(shè)計多版本兩段鎖并發(fā)控制調(diào)度算法,其算法描述如下：
    (1)在沖突集Ci（Q）上搜索在數(shù)據(jù)項Q的持鎖事務(wù)Ti和優(yōu)先級最高事務(wù)Tj；
    (2)如果Tj估計運行時間+系統(tǒng)時間≤Tj截止時間并且Ti截止時間<Tj截止時間,，則進行下一步驟,；反之結(jié)束；
    (3)判斷Tj在數(shù)據(jù)項Q上是否持有排他鎖,，若沒有則轉(zhuǎn)到步驟（7）,；
    (4)判斷Ti是否申請共享鎖，若沒有,，則轉(zhuǎn)到步驟(6),；
    (5)在沖突集Ci（Q）上，每個申請共享鎖的事務(wù)獲準(zhǔn)共享鎖,，執(zhí)行步驟（9）,；
    (6)獲準(zhǔn)Ti排它鎖，執(zhí)行步驟（9）,；
    (7)判斷Tj在數(shù)據(jù)項Q上是否持共享鎖,，若沒有，則轉(zhuǎn)到步驟（9）,；
    (8)Ti獲得排他鎖,，Tj重啟動,；
    (9)算法結(jié)束,。
    本算法中只讀事務(wù)不必等待任何鎖,。更新事務(wù)在對數(shù)據(jù)項加鎖發(fā)生沖突時，若持鎖的事務(wù)優(yōu)先級低,，而重啟動不會延誤截止時間,，則持鎖的事務(wù)重啟動。在該協(xié)議中,，一次只允許一個更新事務(wù)提交,。
3 模擬仿真和性能分析
    仿真的目的是研究新提出的并發(fā)控制協(xié)議在MANETS中的性能。為了對比,，選用多版本協(xié)議和兩段鎖協(xié)議作為基準(zhǔn)協(xié)議,。主要的性能指標(biāo)為延誤截止時間率和重啟動率。仿真模型由移動主機和廣播磁盤組成,。廣播磁盤傳輸數(shù)據(jù)項和控制信息,，數(shù)據(jù)項所有版本放在同一個磁盤上，每個數(shù)據(jù)項所有版本將相繼廣播,，熱數(shù)據(jù)的老版本位于最新版本之后,，都放在快速磁盤上。冷數(shù)據(jù)所有版本則位于慢速磁盤上,。一個數(shù)據(jù)項所有版本以相同的頻率廣播[5-6],。仿真參數(shù)如表1所示，一旦事務(wù)截止時間到,，事務(wù)立即結(jié)束,。

    從圖3、圖4可以看出,，在MANETS網(wǎng)絡(luò)中多版本兩階段封鎖協(xié)議的性能優(yōu)于多版本協(xié)議和兩段鎖協(xié)議,且事務(wù)到達率越高效果就越明顯,。前者的延誤截止時間率、重啟動率都比較低,。這是由于多版本機制消除了只讀事務(wù)和更新事務(wù)的沖突,，降低了只讀事務(wù)的響應(yīng)時間，又通過多版本動態(tài)調(diào)整串行次序,，而兩階段鎖協(xié)議保證了并發(fā)操作調(diào)度的正確性,，避免了一切不必要的事務(wù)重啟動。又因為移動事務(wù)在移動主機上進行了部分有效性確認,，從而及早地檢測了數(shù)據(jù)沖突,，進而減少了移動事務(wù)延誤截止時間率。此外,，多版本機制消除了移動只讀事務(wù)和移動更新事務(wù)之間沖突,，讀請求從不失敗且不必等待,。

    該文提出了在MANETS中處理多級安全事務(wù)要采用的多版本兩段鎖并發(fā)控制協(xié)議。該協(xié)議結(jié)合了多版本和兩段鎖協(xié)議的優(yōu)點,，在MANETS中提高了事務(wù)的并發(fā)度,，讀請求從不失敗且不必等待，事務(wù)間沖突通過等待解決而不是通過回滾解決,。
    該協(xié)議與兩段鎖協(xié)議,、多版本協(xié)議相比，在多級事務(wù)的處理上能更好地保證數(shù)據(jù)的完整性和一致性,。仿真結(jié)果表明,在正常負載下其延誤截止時間率和重啟動率都要低得多,，性能較好。
參考文獻
[1] KIM H W,，PARK D S.Advanced transaction scheduling protocol for multilevel secure database in wireless mobile network environment[C].Joint 4th IEEE International Conference on ATM(ICATM 2001) and High Speed Intelligent Internet Symposium, 2001.
[2] 曲立平.基于多版本的多級安全并發(fā)控制機制的研究[J].信息技術(shù),2005,52（6）：14-16.
[3] 李麗萍,，何守才.數(shù)據(jù)庫多級安全模型的研究[J].上海第二工業(yè)大學(xué)學(xué)報，2006,，23（3）：218-222.
[4] 雷向東,，袁曉莉.并行實時數(shù)據(jù)庫系統(tǒng)多版本兩階段封鎖并發(fā)控制協(xié)議[J].中南工業(yè)大學(xué)學(xué)報，2003,34（3）：298-301.
[5] 雷向東,，袁曉莉.多版本兩階段封鎖并發(fā)控制協(xié)議性能研究[J].計算機工程與科學(xué),，2003,25(04):46-49.
[6] RAHBAR A.A new data communication protocol for distributed mobile datbases in mobile Ad Hoc networks[C]. Sixth International Conference on Information Technology, 2009.