移動自組網中多級安全事務的并發控制

雷向東，陳莉莉

(中南大學 信息科學與工程學院，湖南 長沙 410083)

移動自組網 MANETS（Mobile Ad Hoc Networks）是由多個移動節點通過無線鏈路相連接，具有時變拓撲結構的一個多跳、臨時性自治系統。MANETS中的數據庫系統是由許多移動主機組成的動態分布式數據庫系統。通常分布式數據庫中總是有若干個事務在運行，這些事務可能并發地存取相同的數據。當數據庫中有多個事務并發運行時，系統必須對并發事務之間的相互作用加以控制，即通過并發控制機制來實現。然而，由于在MANET網絡中節點到處移動導致網絡拓撲結構頻繁變化，使得很多有線網絡中的并發技術在MANET網絡中行不通。例如鎖機制或時間戳機制，這些并發控制機制被應用到MANET的多級事務時,將會產生很多問題，如隱通道、高級事務被餓死和檢索異常等[1]。因此解決MANETS中多級事務的并發控制具有重要的意義。

MANETS中的數據庫管理系統（DBMS）是一個由不同訪問權限的用戶共享的、包含多安全等級數據的安全系統。系統中的每一個數據項具有其安全等級，并且每一個用戶被賦予不同的訪問權限。由于這些特點，并發執行的事務可能導致不同的主體為了獲取數據而產生競爭，進而競爭會導致安全問題，于是就要求DBMS對并發操作進行正確調度[2]，即允許非沖突的事務并行執行，而沖突的事務必須被串行化，即實現可串行化調度。

為保證MANETS中多級安全數據庫的完整性和一致性，本文提出一種運用在MANET中的多版本兩段鎖并發控制協議。

1 多級事務

首先，看一個多級事務的例子：

這里R（x,U,S）表示具有秘密密級的主體在具有公開安全級的對象x上的一個讀操作；同樣，W（y,S,S）表示具有秘密密級的主體在具有秘密安全級的對象y上的一個寫操作。對于這類多級事務，定義被簡化為如下形示：

這個主體的分類級別與事務名有關聯。

1.1 多級事務處理系統

目前多級安全事務處理系統有4種主要的體系結構：基于完整性鎖的體系結構、基于內核化的體系結構、基于數據復制的體系結構和基于可信主體的體系結構。這里以基于可信主體的體系結構為例，由DBMS自身實現強制訪問控制。要求運行在多級安全局域網上，通過安全網絡進行通信，所有對數據庫的訪問必須通過可信DBMS，DBMS在多個文件中存儲多級數據庫。在可信主體體系結構中實現多級安全的事務處理所遵循的機制如圖1所示。

圖中事務管理器TM(Transaction Manager)由可信事務管理器和各安全級上的不可信事務管理器組成。事務管理器負責管理所有事務的執行，事務的每一個操作都需要事務管理器的調解。對于單級事務，系統將它發送給該安全級上的不可信事務管理器進行處理。對于多級事務，事務管理器用單級事務的處理機制來實現多級事務的處理。系統首先將多級事務發送給可信事務管理器，然后可信事務管理器將多級事務劃分為單安全級的子事務，將這些子事務分別發送給相應安全級的不可信事務管理器?？尚沛i管理器負責安全鎖協議的實現，它的主要功能是提供對數據項的加鎖和解鎖操作?？尚盼募芾砥鞴芾韺祿椀奈锢碓L問。

1.2 一種安全調度框架

要實現一個多級事務調度的安全性能需實現以下兩方面安全性：

（1）調度協議的安全性；

（2）執行的安全性。

本文只關注第一部分,通過分析協議，可以估計一個調度的內在的安全性。無需考慮調度的執行就可以評估調度。不安全的調度協議能夠在執行之前被發現。如果調度協議是安全的，則可以考慮對執行問題做分析；否則，很可能將對協議的分析簡化為對執行情況的分析。

1.3 多版本調度

在數據庫中，多版本調度允許一個元素有多個版本。這種特征降低了對一個元素的爭奪。一個多版本調度產生的調度表稱為一個完整的調度時間表，表示為（s，V）。其中s代表輸出操作，V代表版本類型。它映射了輸出操作s與被訪問元素版本V之間的關系。其中版本V有3種類型：(1)到寫版本的先前操作的參考；(2)到新版本的參考，即寫操作創建一個新版本；(3)到空版本的參考，即一個元素的寫操作會被丟棄。當操作到達時，調度程序會做出3個基本決定：(1)操作是否可以立即執行；(2)讀操作或寫操作的實體是什么版本；(3)調度是否可以繼續。而調度程序會根據本身的間隔狀態做出決定。

現在，定義一種調度程序，把這個程序之前的輸出操作定義為調度狀態，這里只討論調度程序的輸出操作，不考慮為讀或寫操作分配版本。

定義1一個調度程序是輸出狀態等價,當且僅當任意兩個狀態 st1、st2有各自的輸出（s1，V1）、（s2，V2），如果s1等于s2，則s1對一個即將被調度的程序的操作決策與s2對該程序做出的操作決策是相同的。換言之，一個輸出狀態等價調度，如果兩個不同狀態調度的輸出操作是相同的，則這兩個狀態是等價的。這意味著到達的操作即將被調度，但發生了延遲，不過不影響調度程序所做的決定。

現在定義一個輸出狀態等價的弱版本。在這種情況下，輸出操作僅決定帶有決策的調度行為。

定義2 一個調度程序是輸出調度沖突,當且僅當任意兩個狀態 st1、st2有各自的輸出（s1，V1）、（s2，V2）。 如果s1等于s2，則 s1對一個即將被調度的程序的操作決策與s2對該程序做出的操作決策是相同的。

如圖2所示的簡單調度模型中，操作從左邊輸入，右邊輸出。如果一個操作不能被立即調度，它將被排在隊列中。調度問題主要關注事務操作的順序，以便保持正確性，并允許同一時間的并發性。如果兩個事務之間出現沖突，就將事務串行化。

2 多版本兩段鎖協議

[3]提出了一種使用多版本數據的安全的并發控制機制。當 Ti試圖寫一個數據對象x時發現Ts已經在x上請求了一個讀鎖，Ti就創建了x的一個新的版本。因為通過給每一個多級事務一個不同的版本已經解決了沖突，所以就避免了隱通道的創建。然而，這樣做帶來了新的問題，即高級事務的讀操作讀到的可能是不一致的版本，即所謂的檢索異常。但是在兩段鎖協議中，一個事務應當在確定其不再需要其他加鎖的情況后才釋放所持有的鎖。于是下面提到的多版本兩階段封鎖協議可以解決檢索異常問題。

2.1 多版本兩段鎖協議概述

每一個只讀事務Ti發出讀數據項Q時，返回值是小于Ts(Ti)時間戳的最大版本Qk的內容。這是因為一個事務應讀取在它之前的最近版本。更新事務執行兩段鎖協議，在提交之前不釋放任何鎖，事務可以按其提交的順序串行化，更新事務Ti。讀取數據項Q時，Ti在獲得數據項Q上的共享鎖后讀取Q最新版本的值。更新事務Ti。想寫數據項Q時，Ti首先要獲得數據項Q上的排它鎖，然后為Q創建一個新版本，寫操作在新版本上進行。新版本的時間戳初值為∞，它大于任何可能的時間戳值。在創建此版本的事務Ti完成之前，阻止其他只讀事務對此版本進行讀操作。當更新事務Ti完成后，Ti將它創建的每一個版本的時間戳設為Counter+1。然后Ti將Counter增加1。在Counter增加之前啟動的只讀事務將看到被Ti更新之前的值。無論是哪種情況，只讀事務均不必等待加鎖[4]。

2.2 多版本兩段鎖調度算法

多版本調度允許同一實體有多個版本，通過限制訪問一個實體的競爭加強并發性。這種競爭會引起不安全調度或者不安全恢復。這里考慮到的調度之一是沖突集調度。這個調度的輸出是有序沖突調度的集合。有序沖突的定義如下：

定義3一個調度是有序沖突的，當且僅當它能通過一系列0次或者多次轉換變成一個有序調度。在這些轉換中，任何一對來自不同事務的相鄰步驟可以互換,除非它們相沖突。即兩個事務沖突，如果它們訪問相同實體并且這兩個實體中至少有一個正在執行寫操作。接下來定義一種調度屬性——安全級別有序。

定義4 一個調度是安全級別有序的,當且僅當調度中所有的事務對p和q共享一個單一主題的分類等級，且在一個序列順序中p緊跟q或q緊跟p。

根據上述描述，設計多版本兩段鎖并發控制調度算法,其算法描述如下：

(1)在沖突集 Ci（Q）上搜索在數據項 Q的持鎖事務Ti和優先級最高事務 Tj；

(2)如果Tj估計運行時間+系統時間≤Tj截止時間并且Ti截止時間

(3)判斷 Tj在數據項 Q上是否持有排他鎖，若沒有則轉到步驟（7）；(4)判斷Ti是否申請共享鎖，若沒有，則轉到步驟(6)；(5)在沖突集Ci（Q）上，每個申請共享鎖的事務獲準共享鎖，執行步驟（9）；

(6)獲準 Ti排它鎖，執行步驟（9）；

(7)判斷Tj在數據項Q上是否持共享鎖，若沒有，則轉到步驟（9）；

(8)Ti獲得排他鎖，Tj重啟動；

(9)算法結束。

本算法中只讀事務不必等待任何鎖。更新事務在對數據項加鎖發生沖突時，若持鎖的事務優先級低，而重啟動不會延誤截止時間，則持鎖的事務重啟動。在該協議中，一次只允許一個更新事務提交。

3 模擬仿真和性能分析

仿真的目的是研究新提出的并發控制協議在MANETS中的性能。為了對比，選用多版本協議和兩段鎖協議作為基準協議。主要的性能指標為延誤截止時間率和重啟動率。仿真模型由移動主機和廣播磁盤組成。廣播磁盤傳輸數據項和控制信息，數據項所有版本放在同一個磁盤上，每個數據項所有版本將相繼廣播，熱數據的老版本位于最新版本之后，都放在快速磁盤上。冷數據所有版本則位于慢速磁盤上。一個數據項所有版本以相同的頻率廣播[5-6]。仿真參數如表1所示，一旦事務截止時間到，事務立即結束。

表1 仿真測試參數

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

該文提出了在MANETS中處理多級安全事務要采用的多版本兩段鎖并發控制協議。該協議結合了多版本和兩段鎖協議的優點，在MANETS中提高了事務的并發度，讀請求從不失敗且不必等待，事務間沖突通過等待解決而不是通過回滾解決。

該協議與兩段鎖協議、多版本協議相比，在多級事務的處理上能更好地保證數據的完整性和一致性。仿真結果表明,在正常負載下其延誤截止時間率和重啟動率都要低得多，性能較好。

參考文獻

[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].信息技術,2005,52（6）：14-16.

[3]李麗萍，何守才.數據庫多級安全模型的研究[J].上海第二工業大學學報，2006，23（3）：218-222.

[4]雷向東，袁曉莉.并行實時數據庫系統多版本兩階段封鎖并發控制協議[J].中南工業大學學報，2003,34（3）：298-301.

[5]雷向東，袁曉莉.多版本兩階段封鎖并發控制協議性能研究[J].計算機工程與科學，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.