DSU數(shù)據(jù)庫存儲單元在CBTC系統(tǒng)中方案

職業(yè)技術學院畢業(yè)設計（論文）論文題目 DSU數(shù)據(jù)庫存儲單元在CBTC系統(tǒng)中的 應用方案 系 別 專業(yè)班級 學 號 姓 名 指導教師 2011 年 月 日目錄一、引言1二、 數(shù)據(jù)庫技術發(fā)展現(xiàn)狀1（一）數(shù)據(jù)庫技術的發(fā)展1（二）嵌入式數(shù)據(jù)庫2（三）實時數(shù)據(jù)庫2三、 系統(tǒng)需求以及設計問題的提出3四、 DSU數(shù)據(jù)庫在CBTC系統(tǒng)中的作用3五、基于二叉樹的CBTC數(shù)據(jù)庫構建與搜索算法5六、結論78DSU數(shù)據(jù)庫存儲單元在CBTC系統(tǒng)中的應用方案內容摘要摘要：基于通信的列車運行控制(CBTC)系統(tǒng)是目前世界上研究應用最為廣泛的列控系統(tǒng),是利用連續(xù)、大容量的車地雙向通信來實現(xiàn)數(shù)據(jù)傳輸?shù)牧锌叵到y(tǒng)。其中，DSU是數(shù)據(jù)庫存儲單元的簡稱,它是CBTC系統(tǒng)所包含的諸多子系統(tǒng)之一。DSU存在的意義在于為CBTC系統(tǒng)存儲和提供所有的系統(tǒng)數(shù)據(jù)。分析了各種數(shù)據(jù)處理方式的具體實現(xiàn)方案,對DSU所包含的數(shù)據(jù)存儲處理子系統(tǒng)(DSMS)進行了模塊化構建。論文提出了在安全計算機的環(huán)境中開發(fā)DSU系統(tǒng)的理念,并在嵌入式實時操作系統(tǒng)VxWorks的環(huán)境下,此外,論文還對DSU中的數(shù)據(jù)安全以及數(shù)據(jù)庫安全性特點進行了的定性研究。最后論文對所作的工作進行了總結,并對今后的實際設備投入工作進行了展望。 關鍵詞：CBTC 數(shù)據(jù)庫存儲單元 DSU 數(shù)據(jù)庫設計 二叉樹 動態(tài)圖一、引言目前在全世界范圍內，隨著社會經濟發(fā)展和城市化進程的加快，城市軌道交通(包括地鐵、輕軌、城際快速鐵路等)正以其客運量大、效率高、污染小、受干擾少、安全系數(shù)高的優(yōu)勢，成為許多大城市解決交通問題的首要方案。近年來中國的城市軌道交通建設有了很大發(fā)展，到2007年我國已有10個城市18條線路425公里的軌道交通系統(tǒng)投入運營，2007年10月北京地鐵5號線正式開通，而且7個城市的軌道交通項目正在建設，建設項目總長度為400多公里。到2010年，我國計劃新建城市軌道交通項目總長度將近1300公里，預計總投資約5000億元 。為了提高城市軌道交通系統(tǒng)運營效率和運行安全，現(xiàn)代的列車控制系統(tǒng)正朝著自動化、智能化、系統(tǒng)化、網絡化和信息化的方向發(fā)展，基于通信的列車控制(CBTC：Communication Based Train Contr01)技術(以下簡稱CBTC)是目前國際最先進的列車控制技術，它代表著當今世界范圍內控制領域信號技術的發(fā)展趨勢。隨著近年來世界多個城市的CBTC線路的成功運行，CBTC系統(tǒng)已被證明可以有效地提高城市軌道交通的運輸效率與安全性。一個完善的信號系統(tǒng)離不開數(shù)據(jù)庫的支持，CBTC系統(tǒng)作為一個復雜的列車自動運行控制系統(tǒng)，需要一個為系統(tǒng)提供必須數(shù)據(jù)并進行數(shù)據(jù)庫管理的數(shù)據(jù)庫存儲單元(DSU：Database Storage Unit)，它包含了CBTC系統(tǒng)中各子系統(tǒng)使用的所有數(shù)據(jù)庫和配置文件。數(shù)據(jù)庫存儲單元是一個安全型設備，負責存儲整個軌道線路的數(shù)據(jù)以及各種控制信息，它的可靠性以及安全性直接關系到CBTC系統(tǒng)中的列車運行效率以及行車安全，因此DSU的研究與開發(fā)在CBTC系統(tǒng)的設計中扮演著相當重要角色，良好的DSU設計對提高整個CBTC系統(tǒng)的性能以及安全性都具有十分重要的意義，整個CBTC系統(tǒng)的設計對DSU子系統(tǒng)的設計也提出了很高的要求。面對目前國內相關研究還比較貧乏的現(xiàn)狀，本文對CBTC系統(tǒng)中數(shù)據(jù)庫存儲單元的設計進行了有益的探索和實踐，對我國具有自主知識產權的CBTC技術的發(fā)展具有積極意義。二、 數(shù)據(jù)庫技術發(fā)展現(xiàn)狀（一）數(shù)據(jù)庫技術的發(fā)展數(shù)據(jù)庫技術是當今數(shù)據(jù)信息管理的最新技術，它的發(fā)展已經成為先進信息技術的重要組成部分，是現(xiàn)代計算機信息系統(tǒng)和計算機應用系統(tǒng)的基礎和核心。數(shù)據(jù)庫技術最初產生于20世紀60年代中期，根據(jù)數(shù)據(jù)模型的發(fā)展，可以劃分為三個階裂：第一代的網狀、層次數(shù)據(jù)庫系統(tǒng)：第二代的關系數(shù)據(jù)庫系統(tǒng)；第三代的以面向對象模型為主要特征的數(shù)據(jù)庫系統(tǒng)。第一代數(shù)據(jù)庫的代表是1969年IBM公司研制的層次模型的數(shù)據(jù)庫管理系統(tǒng)IMS。以及70年代美國數(shù)據(jù)庫系統(tǒng)語言協(xié)商CODASYL下屬數(shù)據(jù)庫任務組DBTG提議的網狀模型。層次模型的數(shù)據(jù)庫管理系統(tǒng)是定向有序樹，網狀模型對應的是有向圖。第二代數(shù)據(jù)庫的主要特征是支持關系數(shù)據(jù)模型，它具有以下特點：(1)關系模型概念單一，實體和實體之間的聯(lián)系用關系來表示；(2)以關系數(shù)學為基礎；(3)數(shù)據(jù)的物理存儲和存取路徑對用戶不透明；(4)關系數(shù)據(jù)庫語言是非過程化的。第三代數(shù)據(jù)庫出現(xiàn)于上世紀80年代，是科學技術進步和商業(yè)領域需求的必然產物。第三代數(shù)據(jù)庫技術呈現(xiàn)出阿絡化、智能化、標準化和超大型化的發(fā)展趨勢，它具有以下特征：(1)支持數(shù)據(jù)管理、對象管理和知識管理；(2)保持和繼承了第二代數(shù)據(jù)庫系統(tǒng)的技術；(3)對其它系統(tǒng)開放。支持數(shù)據(jù)庫語言標準，支持標準網絡協(xié)議。具有良好的可移植性，可連接性、可擴展性和互操作性。 （二）嵌入式數(shù)據(jù)庫嵌入式數(shù)據(jù)庫系統(tǒng)是指支持移動計算或某種特定計算模式的數(shù)據(jù)庫管理系統(tǒng)，它通常與操作系統(tǒng)和具體的應用集成在一起，運行在嵌入式或移動設備上。嵌入式實時數(shù)據(jù)庫技術涉及數(shù)據(jù)庫、實時系統(tǒng)、分布式計算以及移動通信等多個學科，已成為數(shù)據(jù)庫技術發(fā)展的一個新方向嵌入式數(shù)據(jù)庫系統(tǒng)能夠和嵌入式操作系統(tǒng)有機地結合在一起，為應用開發(fā)人員提供有效的本地數(shù)據(jù)管理手段，同時提供各種定制條件和方法。國外Sybase、Oracle和IBM已經為移動和嵌入式計算提出了業(yè)界領先的解決方案，國內也已經開發(fā)出了多個嵌入式數(shù)據(jù)庫。這些嵌入式數(shù)據(jù)庫系統(tǒng)一般對資源要求較低，占用內存空間較小，從幾十K到幾百K不等；并支持C語言API函數(shù)和標準SQL子集的開發(fā)接口，并提供了數(shù)據(jù)同步的功能。隨著計算機技術和通信技術的發(fā)展，嵌入式數(shù)據(jù)庫技術會在軌道交通、移動通信、工業(yè)控制等越來越多的領域得到應用。（三）實時數(shù)據(jù)庫實時數(shù)據(jù)庫(RTDB：Real Time DataBase)是數(shù)據(jù)和事務都有顯式定時限制的數(shù)據(jù)庫，其系統(tǒng)的正確性不僅依賴于事務的邏輯結果，還依賴于邏輯結果產生的時間。RTDB是數(shù)據(jù)庫技術的一個發(fā)展分支，它最早出現(xiàn)在1988年3月的ACMSIGMOD Record的一期?？?。同時這也標志著實時系統(tǒng)領域與數(shù)據(jù)庫領域融合的開始，標志著實時數(shù)據(jù)庫這個新興研究領域的確立。隨后，一個成熟的研究群體逐漸出現(xiàn)，尤其是美國、英國、德國、瑞典等國對RTDB的研究非常關注。此后，世界范圍內出現(xiàn)了大批有關實時數(shù)據(jù)庫方面的論文和原型系統(tǒng)。繼而又出現(xiàn)許多成功的實驗系統(tǒng)，有的甚至已商品化，典型的有HiPAC、Zip RTDBMS等系統(tǒng)。與此同時，國內對于RTDB的研究起步雖然稍晚，基本上是在上世紀80年代末、90年代初才開始，但是發(fā)展卻非常之快，目前己經有了許多成功的實時數(shù)據(jù)庫實驗系統(tǒng)?，F(xiàn)代的RTDB技術適用于處理不斷更新變化的數(shù)據(jù)及具有時間限制的實時事務。它是實時系統(tǒng)和數(shù)據(jù)庫技術相結合的產物，研究人員希望利用數(shù)據(jù)庫技術來解決實時系統(tǒng)中的數(shù)據(jù)管理問題，同時利用實時技術為實時數(shù)據(jù)庫提供時間驅動調度和資源分配算法。然而，實時數(shù)據(jù)庫并非實時系統(tǒng)和數(shù)據(jù)庫在概念、結構和方法上的簡單集成，而需要針對不同的應用需求與應用特點，對實時數(shù)據(jù)模型、實時事務調度與資源分配策略、實時數(shù)據(jù)查詢語言、實時數(shù)據(jù)通信等大量問題進深入的理論研究。進入二十一世紀以來，RTDB己經成為現(xiàn)代數(shù)據(jù)庫研究的主要方向，Sang H13習相關數(shù)據(jù)庫與實時操作系統(tǒng)內核相結合，研究了對實時數(shù)據(jù)庫并發(fā)處理的靈活控制；Kang14對實際環(huán)境中RTDB的性能評估進行了試驗與研究；Jisul5設計了以管理實時數(shù)據(jù)庫性能的一個RTDB詳細控制模型；Nero16使用有色Petri網對時數(shù)據(jù)庫的周期處理與并發(fā)控制進行了分析和研究。目前，RTDB技術已經形成了一個系統(tǒng)體系，RTDB技術的研究也朝著系統(tǒng)化與多元化的方向不斷前進。三、 系統(tǒng)需求以及設計問題的提出CBTC系統(tǒng)是一個具有很高實時性要求的嵌入式系統(tǒng)，傳統(tǒng)的企業(yè)級數(shù)據(jù)庫如Oracle、Sybase等在實時嵌入式環(huán)境下很難發(fā)揮作用，尤其在實時性要求很高的控制系統(tǒng)(如CBTC系統(tǒng))中，傳統(tǒng)數(shù)據(jù)庫更顯得無能為力，所以構建嵌入式實時數(shù)據(jù)庫系統(tǒng)成為了嵌入式開發(fā)中必須解決的問題。在CBTC系統(tǒng)中，嵌入式實時數(shù)據(jù)庫系統(tǒng)以高可靠性、高安全性、高實時性和高信息吞吐量為目標，對DSU的設計提出了很高的要求。DSU數(shù)據(jù)庫即嵌入式實時數(shù)據(jù)庫是嵌入式實時數(shù)據(jù)庫系統(tǒng)(DSU)的基礎和底層架構，需要針對選用的實時操作系統(tǒng)和嵌入式硬件平臺設計合理的數(shù)據(jù)模型和物理結構。本文依托的CBTC項目采用VxWorks實時操作系統(tǒng)和安全計算機平臺進行系統(tǒng)設計，因此DSU數(shù)據(jù)庫的開發(fā)基于VxWorks實時操作系統(tǒng)和安全計算機平臺，并要在此基礎上能夠滿CBTC系統(tǒng)與各個子系統(tǒng)的功能和需求。CBTC系統(tǒng)是以移動閉塞模式控制列車運行的，列車在線路上行駛時，列車的位置不是分段(如軌道電路)的，而是連續(xù)的，說明線路數(shù)據(jù)是有序的，DSU數(shù)據(jù)庫要能夠對這種位置連續(xù)的軌道線路進行描述。列車在行駛過程中，車載控制器VOBC需要通過DSU數(shù)據(jù)庫進行列車定位，而區(qū)域控制器ZC需要通過DSU數(shù)據(jù)庫來完成列車移動授權(MA：Movement Authority)的計算，列車自動防護(ATP：AutomaticTrain Protection)功能也需要DSU數(shù)據(jù)庫的支持基于上述系統(tǒng)功能與需求，本文以CBTC項目為背景，對DSU數(shù)據(jù)庫的設計與構建進行研究，對DSU數(shù)據(jù)庫的網絡拓撲結構和關系模型進行了研究與實現(xiàn)，使DSU數(shù)據(jù)庫適合CBTC系統(tǒng)的嵌入式環(huán)境，不僅能夠很好地對線路進行描述，還能夠滿足系統(tǒng)以及各個子系統(tǒng)的功能需求，并為將來的DSU實時數(shù)據(jù)庫管理系統(tǒng)的設計打下基礎。四、 DSU數(shù)據(jù)庫在CBTC系統(tǒng)中的作用CBTC系統(tǒng)作為一個先進的列車運行控制系統(tǒng)，需要一個統(tǒng)一數(shù)據(jù)庫來實現(xiàn)整個系統(tǒng)的調度和統(tǒng)一，數(shù)據(jù)庫存儲單元DSU是其重要的組成部分。CBTC系統(tǒng)是具有很高的實時性要求的嵌入式系統(tǒng)，因此DSU是一種嵌入式實時數(shù)據(jù)庫管理系統(tǒng)(RTDBS：Real-Time Database System)，DSU數(shù)據(jù)庫是一種嵌入式實時數(shù)據(jù)庫(RTDB：Real一Time Database)。數(shù)據(jù)庫存儲單元DSU位于CBTC數(shù)據(jù)通信系統(tǒng)的骨干網上，通過骨干網與其它子系統(tǒng)相連，圖4-1是DSU在CBTC系統(tǒng)中的接口框圖。它表明了DSU子系統(tǒng)與其它子系統(tǒng)的相互關系。其中，DSU與VOBC和ZC共同構成ATC系統(tǒng)(Automatic Train Control System)的安全控制部分。各個設備之間的通信是通過非安全的數(shù)據(jù)通信系統(tǒng)DCS來完成的數(shù)據(jù)庫存儲單元對整個信號系統(tǒng)的數(shù)據(jù)庫進行管理，是CBTC系統(tǒng)的安全組成部分之一。圖4-1 DSU在CBTC系統(tǒng)中的接口框圖Figur 4-1 the interfaces of DSU in CBTC systemDSU存儲著CBTC系統(tǒng)內所有子系統(tǒng)所使用的所有數(shù)據(jù)信息和配置文件，數(shù)據(jù)庫包括靜態(tài)數(shù)據(jù)庫、動態(tài)數(shù)據(jù)庫、配置數(shù)據(jù)庫和兼容性數(shù)據(jù)庫等。靜態(tài)數(shù)據(jù)庫是一個非常強大、靈活的數(shù)據(jù)庫，它允許系統(tǒng)對用戶的不同需求做出響應；它提供了線路描述(軌道線路特征等信息)，也提供允許系統(tǒng)實現(xiàn)不同功能的系統(tǒng)構成(如防淹門的位置以及關閉區(qū)域)。動態(tài)數(shù)據(jù)庫存儲軌道線路上的各種l|缶時線路信息和控制信息，這些信息可以被ATS設置與修改。配置數(shù)據(jù)庫包含各個子系統(tǒng)如ZC和VOBC以及系統(tǒng)中的各種信號設備的配置信息和變量參數(shù)，每個子系統(tǒng)都具有特定的子系統(tǒng)配置數(shù)據(jù)庫，它們被用于初始化裝載，使每個子系統(tǒng)在啟動時有足夠的引導信息。兼容性數(shù)據(jù)庫包括了子系統(tǒng)使用的軟件、接口和數(shù)據(jù)庫版本之聞所有許可的兼容性，規(guī)定TCBTC系統(tǒng)中每個子系統(tǒng)的軟件類型、軟件特征，與其它系統(tǒng)的接口特征以及對應該子系統(tǒng)應用的數(shù)據(jù)庫版本號。本文研究的具體對象為靜態(tài)數(shù)據(jù)庫、動態(tài)數(shù)據(jù)庫和配置數(shù)據(jù)庫。五、基于二叉樹的CBTC數(shù)據(jù)庫構建與搜索算法線路描述即線路網絡拓撲結構的構建是DSU數(shù)據(jù)庫設計的首要問題，是數(shù)據(jù)庫整體構建的基礎，根據(jù)CBTC系統(tǒng)中列車控制的特點以及城市軌道線路特征，本文運用圖論知識和二叉樹建立DSU數(shù)據(jù)庫線路網絡模型，利用數(shù)據(jù)結構相關知識研究線路數(shù)據(jù)存儲結構，并結合圖、二叉樹相關算法探索DSU數(shù)據(jù)庫的有效搜索算法。樹型結構是一類非常重要的非線性數(shù)據(jù)結構，其中以樹和二叉樹最為常用。樹是以分支關系定義的層次結構。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種組織機構都可以用樹來形象表示。樹在計算機領域中也得到了廣泛應用，如在編譯程序中，可用樹來表示源程序的語法結構。又如在數(shù)據(jù)庫系統(tǒng)中，樹形結構也是信息的重要組織形式之一。定義1樹(tree)是無環(huán)連通無向圖。樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結點擁有的子樹數(shù)稱為結點的度(degree)。度為0的結點稱為葉子(1eaf)或終端結點。度數(shù)不為0的結點稱為非終端結點或分支結點。定義2樹也是n(nO)個結點的有限集。在任意一棵非空樹中：(1)有且僅有一個特定的稱為根(root)的結點；(2)當開I時，其余結點可分為m(mO)個不相交的有限集互，互，乏，其中每個集合本身又是一棵樹，稱為根的子樹(subee)。定義3結點的子樹的根稱為該結點的孩子(child)，相應地該結點稱為孩子的雙(parent)。同一個雙親的孩子之間互稱兄弟(sibling)。結點的祖先是從根到該結點所經分支上的所有結點，反之，以某結點為根的子樹中的任一結點都稱為該結點的子孫。定義4結點的層次(1evel)從根開始定義起，根為第一層，根的孩子為第二層。若菜結點在第z層，則其子樹的根就在l+1層。樹中結點的最大層數(shù)稱為樹的深度(depth)或高度。定義5森林(forest)是m(mo)棵互不相交的樹的集合。對樹中每個結點而言，其子樹的樹，否則稱為無序樹。二叉樹(binary tree)21,231是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹(即二叉樹中不存在度大于2的結點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。如圖5-1所示。集合即為森林。定義6如果將樹中結點的各子樹看成從左至右是有次序的(即不能互換)，則稱該樹為有序圖5-1 二叉樹邏輯上二叉樹有五種基本形態(tài)：空二叉樹；只有一個根結點的二叉樹；右子樹為空的二叉樹；左子樹為空的二叉樹；完全二叉樹。滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。完全二叉樹：如果一棵深度為k，有n個結點的二叉樹中各結點能夠與深度為k的順序編號的滿二叉樹從1到n標號的結點相對應的二叉樹稱為完全二叉樹。二叉樹結點問的拓撲關系在數(shù)據(jù)庫中集中反映為二叉樹的數(shù)據(jù)結構，二叉樹一般有兩種數(shù)據(jù)存儲結構：（1）順序存儲結構用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結點元素即將完全二叉樹上編號為i的結點元素存儲在如上定義的一維數(shù)組中下標為i-1的分量中。例如圖5-2中(a)所示為圖5-1中(a)所示完全二叉樹的存儲結構。對于一般二叉樹，則應將其每個結點與完全二叉樹上的結點相對照，存儲在一維數(shù)組的相應分量中，圖5-2中(b)所示的二叉樹的順序存儲結構如圖5-1中(b)所示，圖中以“0”表示不存在的結點。由此可見，這種順序存儲結構僅適用于完全二叉樹。圖5-2 二叉樹的順序存儲結構（2）鏈式存儲結構由二叉樹的定義可知，二叉樹的結點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支構成，則表示二叉樹的鏈表中的結點至少包含3個域：數(shù)據(jù)域和左右指針域。有時為了便于找到結點的雙親，還可以在結點結構中增加一個指向其雙親結點的指針域。利用這兩種結點結構所得的二叉樹的存儲結構分別稱之為二叉鏈表和三叉鏈表。鏈表