基于最小連通支配集的CRL分發(fā)系統(tǒng)研究*

高申勇 ，張 穎 ，戴國駿

(1.浙江水利水電?？茖W校計算機與信息工程系 杭州310018；2.杭州電子科技大學計算機學院 杭州 310018）

1 引言

PKI（public key infrastructure，公鑰基礎設施）是一種普遍適用的網(wǎng)絡安全基礎設施。目前，PKI通常用來解決有線網(wǎng)絡的安全問題，隨著無線網(wǎng)絡的迅速發(fā)展，網(wǎng)絡安全成為一個關鍵問題，它關系到整個網(wǎng)絡底層運行的可靠性、正確性以及網(wǎng)絡上層應用的保密性、完整性、可認證性和不可否認性。近年來PKI正在被無線網(wǎng)絡所采納，將PKI技術應用于無線網(wǎng)絡已經(jīng)成為發(fā)展趨勢，且已初步形成無線 PKI標準[1,2]。而證書撤銷是PKI中一項關鍵操作，撤銷的證書信息保存于 CRL（certification revocation list，證書撤銷列表），如何分發(fā)CRL，使得用戶能及時獲取最新證書撤銷信息是PKI應用面臨的重要問題之一。

目前CRL分發(fā)有基于“推”方式的服務器主動分發(fā)和基于“拉”方式的服務器被動分發(fā)?！巴啤狈绞剑疵慨擟RL文件更新時，CA（certification authority，認證機構(gòu)）將最新的CRL“推送”給所有相關的用戶；采用“拉”方式時，僅當用戶的當前CRL文件過期時才主動向CA“拉取”最新的CRL文件。與“拉”方式相比，“推”技術能使CA更及時主動地分發(fā)最新CRL，同時較好地避免由于大量用戶同時訪問服務器造成的負載過重問題，因此“推”方式更適合于能量有限的無線網(wǎng)絡。

在無線網(wǎng)絡中，實現(xiàn)全網(wǎng)廣播分發(fā)的最基本的途徑是“洪泛”，但通過“洪泛”進行廣播容易引起廣播風暴，為此通常在廣播中尋找最小化參與轉(zhuǎn)發(fā)節(jié)點數(shù)，本文基于最小連通支配集算法分發(fā)方法，構(gòu)造虛擬骨干網(wǎng)絡進行廣播，一定程度上緩解了廣播風暴，避免了大量的傳輸沖突和碰撞，提高了網(wǎng)絡的吞吐量，從而保證網(wǎng)絡中的節(jié)點及時收到CRL文件。本文的研究結(jié)果對無線網(wǎng)絡下CRL分發(fā)具有一定的理論參考價值和實際應用價值。

2 分發(fā)協(xié)議設計

本文設計的廣播協(xié)議屬于應用層協(xié)議，位于傳輸層之上，下層協(xié)議為其提供服務。協(xié)議作如下假定。

·該協(xié)議運行于具有全分布式平面結(jié)構(gòu)無線網(wǎng)絡內(nèi)。

·一段時間內(nèi)，網(wǎng)絡都為連通且處于不移動狀態(tài)，節(jié)點采用無向天線。

·無線信道為網(wǎng)絡中所有節(jié)點共享，MAC協(xié)議采用類似IEEE 802.11標準的隨機信道訪問協(xié)議；并且假設通信鏈路為雙向，所有數(shù)據(jù)分組能按順序到達目的節(jié)點。

協(xié)議設計分為兩個階段：廣播樹構(gòu)造及沿著廣播樹傳輸文件。廣播樹構(gòu)造是該協(xié)議設計的核心，也是文件傳輸基礎。首先，源節(jié)點與相鄰節(jié)點交換Hello分組，獲得2跳網(wǎng)絡拓撲信息，利用貪婪集合覆蓋算法 （greedy set cover algorithm）[3]，在1跳鄰節(jié)點集合中，反復地選取那些覆蓋最多2跳鄰節(jié)點數(shù)量的節(jié)點作為下一步用于轉(zhuǎn)播文件的轉(zhuǎn)播節(jié)點，重復該過程，直到所有2跳鄰節(jié)點都被覆蓋，最終由轉(zhuǎn)播節(jié)點形成一棵廣播樹，沿著這個廣播樹傳輸文件，將文件廣播至所有終端用戶。

2.1 數(shù)據(jù)結(jié)構(gòu)和報文格式

為了實現(xiàn)廣播樹構(gòu)造，每個節(jié)點都需維護一個重復消息表和一個消息緩存區(qū)、節(jié)點標識、是否獲知1跳鄰居標識、轉(zhuǎn)發(fā)節(jié)點集合以及二步鄰接表。具體描述如下。

重復消息表(duplicate_message_table)：記錄節(jié)點接收到的廣播消息內(nèi)的源節(jié)點地址和消息標識；當節(jié)點收到廣播消息時，首先檢查重復消息表。

消息緩存區(qū)(message_buffer)：由動態(tài)數(shù)組組成，臨時存放接收到的若干個廣播消息。

節(jié)點標識(node_identifier)：用來標識節(jié)點為轉(zhuǎn)播節(jié)點或普通節(jié)點，每個節(jié)點初始狀態(tài)賦為普通節(jié)點。

是否獲知1跳鄰節(jié)點信息 (get-one-hop)標識：為每個節(jié)點分配布爾變量，標識節(jié)點是否獲得或正在獲得其1跳范圍內(nèi)的鄰居信息，True表示已獲得或正在獲得鄰居信息，否則為False。

轉(zhuǎn)發(fā)節(jié)點集合(forward_node_set)：存放轉(zhuǎn)播節(jié)點的集合。

二步鄰接表(two_hop_adjacency_list)：每個節(jié)點維護一個二步鄰接表，記錄鄰居節(jié)點信息以及相鄰節(jié)點的鄰居信息。

2.2 廣播樹構(gòu)造

廣播樹構(gòu)造是整個協(xié)議的核心，如何獲得2跳鄰節(jié)點信息是廣播構(gòu)造樹的關鍵步驟，本文參考AODV路由協(xié)議[4，5]，采用定時器策略實現(xiàn)節(jié)點等待鄰居信息，若超過定時器設定的合理等待時間，相鄰節(jié)點未回復，則認為此節(jié)點與它不相鄰。根據(jù)獲得的2跳鄰節(jié)點信息，每個源節(jié)點執(zhí)行貪婪集合覆蓋算法計算1跳鄰居中哪些節(jié)點為轉(zhuǎn)發(fā)節(jié)點，所有的轉(zhuǎn)發(fā)節(jié)點組成了最小連通支配集，也為廣播樹中的非葉子節(jié)點，普通節(jié)點構(gòu)成葉子節(jié)點并直接相連于一個非葉子節(jié)點。廣播樹的具體構(gòu)造過程如下所示。

（1）源節(jié)點向其鄰居廣播 RREQ（user request）分組用于發(fā)現(xiàn)廣播樹路由，分組中跳計數(shù)（hop count）初始化為0，啟動定時器用來等待收集2跳鄰居節(jié)點集；定時器開始計時。

（2）當節(jié)點接收到RREQ分組，首先檢查重復消息表，若為重復消息，不再進行轉(zhuǎn)發(fā)，并拋棄該分組；否則，更新重復消息表及RREQ分組，將hop count增加1。

（3）判斷 hop count的值，若為 1，設置 get-one-hop 為True，轉(zhuǎn)發(fā)更新后的RREQ分組，同時設置合理的時延啟動定時器；否則，不再轉(zhuǎn)發(fā)RREQ分組，僅回復路由應答分組 RREP（user reply）。

（4）當節(jié)點收到 RREP分組，更新 RREP分組，判斷hop count值，若為0，提取 RREP信息，將RREP保存到二步鄰接表的鄰居節(jié)點列表內(nèi)，如果定時器到零，回復RREP，否則，繼續(xù)等待RREP；若為1，將其保存到二步鄰接表中的鄰居節(jié)點列表及相鄰鄰居節(jié)點列表中。

（5）判斷定時器是否到零，為零時，計算轉(zhuǎn)播節(jié)點，并向其鄰居廣播Join分組；否則，繼續(xù)等待RREP。

（6）當節(jié)點收到Join分組后，提取轉(zhuǎn)播列表。若包含該節(jié)點，則設置節(jié)點為轉(zhuǎn)播節(jié)點，并且提取鄰居節(jié)點信息，將其保存到二步鄰接表中的鄰居節(jié)點列表；否則，拋棄該數(shù)據(jù)包，設為普通節(jié)點。

3 分發(fā)系統(tǒng)設計

利用設計分發(fā)協(xié)議來開發(fā)一個CRL文件快速分發(fā)系統(tǒng)，實現(xiàn)CRL文件的快速“推送”功能，如圖1所示。本系統(tǒng)要求能夠?qū)崿F(xiàn)CRL文件快速地傳輸?shù)矫恳粋€請求的終端。具體功能設計如下。

·生成種子文件功能：對文件進行分塊，并且分別對每一塊進行散列運算；

·廣播樹構(gòu)造功能：按照控制消息構(gòu)造廣播樹；

·數(shù)據(jù)分組廣播功能：填充協(xié)議頭部，構(gòu)造UDP（user datagram protocol,用戶數(shù)據(jù)報協(xié)議）廣播分組；

·數(shù)據(jù)分組轉(zhuǎn)發(fā)功能：解析接收到的數(shù)據(jù)分組的頭部，并按照解析的結(jié)果和相應的規(guī)則轉(zhuǎn)發(fā)該數(shù)據(jù)分組；

·數(shù)據(jù)分組存儲功能：登記每個收到的數(shù)據(jù)分組，生成塊位圖和子塊位圖，同時緩存數(shù)據(jù)分組，緩沖區(qū)滿后再將數(shù)據(jù)轉(zhuǎn)存入磁盤文件。

系統(tǒng)功能模塊如圖2所示。

4 模擬實現(xiàn)與性能評估

本文采用網(wǎng)絡模擬器NS-2作為實驗的仿真平臺，進行模擬并分析其性能。NS-2支持從數(shù)據(jù)鏈路層到應用層的各種網(wǎng)絡協(xié)議的模擬，如以太網(wǎng)協(xié)議、TCP、FTP等，可以用于路由協(xié)議、傳輸協(xié)議、多播協(xié)議、應用協(xié)議等的研究。當前NS-2已被用于移動自組網(wǎng)路由協(xié)議性能的評估中[6,7]。模擬網(wǎng)絡中共有Node_num個節(jié)點，整個實驗場景的區(qū)域為長為Length、寬為Width的平面區(qū)域。具體模擬參數(shù)及協(xié)議參數(shù)如表1所示。

表1 廣播協(xié)議模擬參數(shù)設置

（1）傳輸成功率

傳輸成功率定義為實際收到的有效消息個數(shù)與應接收的消息個數(shù)之比，即DR=RXusr/(TXsrc(Node_num-1))。其中，RXusr是用戶實際接收到的非重復的廣播消息個數(shù)，TXsrc是廣播源產(chǎn)生的廣播消息總數(shù)，Node_num是節(jié)點總數(shù)。傳輸成功率反映了廣播協(xié)議的可靠性或魯棒性。顯然，0≤DR≤1。

（2）傳輸開銷

傳輸開銷為傳輸一個用戶消息時平均每個節(jié)點的開銷，即 DC=TXall/(TXsrc·Node_num)。其中，TXall是運行過程中所有節(jié)點發(fā)送的消息總數(shù)，包括廣播消息和廣播協(xié)議的控制消息。本文考慮了節(jié)點的發(fā)送開銷，而未計入接收開銷。由于發(fā)送操作要占用網(wǎng)絡帶寬，因此在計算傳輸開銷時主要計入節(jié)點的發(fā)送開銷。

（3）傳輸時間

傳輸時間為源節(jié)點分發(fā)一個文件到全網(wǎng)所有用戶的傳輸時間，包括廣播樹構(gòu)造時間和文件傳輸時間。其中模擬實驗中文件大小為255 byte。

利用NS-2中的場景生成程序隨機產(chǎn)生一個網(wǎng)絡，在網(wǎng)絡上分別運行模擬程序100次得到統(tǒng)計平均值。令等待2跳鄰居節(jié)點信息的定時器T的值分別取0.08 s、0.15 s和0.22 s，模擬結(jié)果如圖3～5所示，網(wǎng)絡和協(xié)議的其他參數(shù)均取缺省值。

由圖 3可知，T值設置越長，傳輸成功率（delivery ratio）越高，主要由于源節(jié)點有相對足夠的時間等待接收所有的2跳鄰節(jié)點信息，但卻增加了一定的傳輸開銷（delivery cost），如圖4所示；另外，T值對網(wǎng)絡節(jié)點少的傳輸成功率影響不大，但是隨著節(jié)數(shù)增加，若T值設置較短，會導致源節(jié)點可能無法收到離它較遠的節(jié)點信息，因此傳輸成功率下降，但因為執(zhí)行轉(zhuǎn)播操作的時間較短，傳輸開銷較低。

如圖5可知，T值對傳輸時間有影響，一般情況下，T值設置越長，傳輸時間增加，但是能保證較高的傳輸成功率而且傳輸時間也較短，例如，當T=0.22 s時，全網(wǎng)60個節(jié)點收到包含255 byte的文件只需6 s。

由以上仿真結(jié)果表明，定時器值的設置對傳輸成功率、傳輸開銷和傳輸時間這3個主要性能指標有一定的影響。當合理設置定時器等待時間時，不僅能適應節(jié)點較多的網(wǎng)絡，而且保證較好的傳輸率、較低的傳輸開銷及較短的傳輸時間。

5 結(jié)束語

無線網(wǎng)絡是一種具有重要應用價值的網(wǎng)絡，其網(wǎng)絡安全仍是一個全新的問題，通過PKI可在一定程度上解決該問題，如何使用戶及時獲取最新CRL是PKI應用面臨的主要問題之一。因此，研究無線網(wǎng)絡下CRL分發(fā)方法具有一定的理論及應用價值，本文設計了一個基于最小連通支配集算法分發(fā)方法的分發(fā)協(xié)議及CRL分發(fā)系統(tǒng)，并利用NS-2對協(xié)議進行模擬仿真分析其性能。本文研究的CRL分發(fā)系統(tǒng)是一個比較理想的系統(tǒng)，系統(tǒng)假設各節(jié)點的數(shù)據(jù)傳輸都是可靠的，對于數(shù)據(jù)分組丟失處理和數(shù)據(jù)分組重傳問題考慮不夠，有待進一步研究和完善。

1 ISO/IEC 8802-11.IEEE Standard for Wireless LAN Medium Access Control and Physical Layer Specifications,1999

2 WAP Public Key Infrastructure Specification. Wireless Application Protocol Public Key Infrastructure Definition.http://www.openmobilealliance.org/tech/affiliates/LicenseAgreement.asp?DocName=/wap/wap-217-wpki-20010424-a.pdf,2001

3 Lim H,Kim C.Flooding in wireless ad hoc networks.Computer Communications.2001,24(3-4):353～363

4 王金龍，王呈貴，吳啟暉.Ad Hoc移動無線網(wǎng)絡.北京：國防工業(yè)出版社，2004

5 任智.移動Ad Hoc網(wǎng)絡路由算法及協(xié)議研究.電子科技大學博士學位論文，2005

6 Das S R,Perkins C E,Royer E M.Performance comparison of two on-demand routing protocols for ad hoc networks.Proceedings of IEEE INFOCOM,Israel,2000

7 Maltz D A,Broch J,Jetcheva J,et al.The Effects of on-demand behaviorin routingprotocolformultihop wirelessad hoc networks.IEEE Journal on Selected Areas in Communications,1999,17(8):1 439～1 453