基于最小連通支配集的CRL分發系統研究*

高申勇 ，張 穎 ，戴國駿

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

1 引言

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

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

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

2 分發協議設計

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

·該協議運行于具有全分布式平面結構無線網絡內。

·一段時間內，網絡都為連通且處于不移動狀態，節點采用無向天線。

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

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

2.1 數據結構和報文格式

為了實現廣播樹構造，每個節點都需維護一個重復消息表和一個消息緩存區、節點標識、是否獲知1跳鄰居標識、轉發節點集合以及二步鄰接表。具體描述如下。

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

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

節點標識(node_identifier)：用來標識節點為轉播節點或普通節點，每個節點初始狀態賦為普通節點。

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

轉發節點集合(forward_node_set)：存放轉播節點的集合。

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

2.2 廣播樹構造

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

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

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

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

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

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

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

3 分發系統設計

利用設計分發協議來開發一個CRL文件快速分發系統，實現CRL文件的快速“推送”功能，如圖1所示。本系統要求能夠實現CRL文件快速地傳輸到每一個請求的終端。具體功能設計如下。

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

·廣播樹構造功能：按照控制消息構造廣播樹；

·數據分組廣播功能：填充協議頭部，構造UDP（user datagram protocol,用戶數據報協議）廣播分組；

·數據分組轉發功能：解析接收到的數據分組的頭部，并按照解析的結果和相應的規則轉發該數據分組；

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

系統功能模塊如圖2所示。

4 模擬實現與性能評估

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

表1 廣播協議模擬參數設置

（1）傳輸成功率

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

（2）傳輸開銷

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

（3）傳輸時間

傳輸時間為源節點分發一個文件到全網所有用戶的傳輸時間，包括廣播樹構造時間和文件傳輸時間。其中模擬實驗中文件大小為255 byte。

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

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

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

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

5 結束語

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

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移動無線網絡.北京：國防工業出版社，2004

5 任智.移動Ad Hoc網絡路由算法及協議研究.電子科技大學博士學位論文，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