高申勇 ，張 穎 ，戴國(guó)駿

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

1 引言

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

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

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

2 分發(fā)協(xié)議設(shè)計(jì)

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

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

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

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

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

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

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

重復(fù)消息表(duplicate_message_table)：記錄節(jié)點(diǎn)接收到的廣播消息內(nèi)的源節(jié)點(diǎn)地址和消息標(biāo)識(shí)；當(dāng)節(jié)點(diǎn)收到廣播消息時(shí)，首先檢查重復(fù)消息表。

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

節(jié)點(diǎn)標(biāo)識(shí)(node_identifier)：用來(lái)標(biāo)識(shí)節(jié)點(diǎn)為轉(zhuǎn)播節(jié)點(diǎn)或普通節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)初始狀態(tài)賦為普通節(jié)點(diǎn)。

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

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

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

2.2 廣播樹構(gòu)造

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

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

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

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

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

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

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

3 分發(fā)系統(tǒng)設(shè)計(jì)

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

·生成種子文件功能：對(duì)文件進(jìn)行分塊，并且分別對(duì)每一塊進(jìn)行散列運(yùn)算；

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

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

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

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

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

4 模擬實(shí)現(xiàn)與性能評(píng)估

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

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

（1）傳輸成功率

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

（2）傳輸開銷

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

（3）傳輸時(shí)間

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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移動(dòng)無(wú)線網(wǎng)絡(luò).北京：國(guó)防工業(yè)出版社，2004

5 任智.移動(dòng)Ad Hoc網(wǎng)絡(luò)路由算法及協(xié)議研究.電子科技大學(xué)博士學(xué)位論文，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