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

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

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

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

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

    該文提出了在MANETS中處理多級(jí)安全事務(wù)要采用的多版本兩段鎖并發(fā)控制協(xié)議,。該協(xié)議結(jié)合了多版本和兩段鎖協(xié)議的優(yōu)點(diǎn),，在MANETS中提高了事務(wù)的并發(fā)度，讀請(qǐng)求從不失敗且不必等待,，事務(wù)間沖突通過(guò)等待解決而不是通過(guò)回滾解決,。
    該協(xié)議與兩段鎖協(xié)議、多版本協(xié)議相比,，在多級(jí)事務(wù)的處理上能更好地保證數(shù)據(jù)的完整性和一致性,。仿真結(jié)果表明,在正常負(fù)載下其延誤截止時(shí)間率和重啟動(dòng)率都要低得多，性能較好,。
參考文獻(xiàn)
[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] 曲立平.基于多版本的多級(jí)安全并發(fā)控制機(jī)制的研究[J].信息技術(shù),2005,52（6）：14-16.
[3] 李麗萍，何守才.數(shù)據(jù)庫(kù)多級(jí)安全模型的研究[J].上海第二工業(yè)大學(xué)學(xué)報(bào),，2006,，23（3）：218-222.
[4] 雷向東，袁曉莉.并行實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)多版本兩階段封鎖并發(fā)控制協(xié)議[J].中南工業(yè)大學(xué)學(xué)報(bào),，2003,34（3）：298-301.
[5] 雷向東,，袁曉莉.多版本兩階段封鎖并發(fā)控制協(xié)議性能研究[J].計(jì)算機(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.