蔡 濤，倪曉蓉，王偉生，牛德姣

(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江212013)

1 概述

檢測(cè)器生成算法是影響人工免疫系統(tǒng)(Artificial Immune System，AIS)檢測(cè)性能和效率的重要因素之一。檢測(cè)器生成算法的主要工作是從初始檢測(cè)器中篩選成熟檢測(cè)器，使用匹配算法檢查初始檢測(cè)器與自體是否匹配，選擇與所有自體均不匹配的初始檢測(cè)器作為成熟檢測(cè)器。Forrest等研究者給出了經(jīng)典的檢測(cè)器生成算法，并不斷有研究者進(jìn)行各種改進(jìn)。為保證所選擇成熟檢測(cè)器對(duì)非自體的覆蓋率，需要計(jì)算全部初始檢測(cè)器與自體的匹配度后進(jìn)行篩選，這使得篩選檢測(cè)器的時(shí)間和空間開(kāi)銷與初始檢測(cè)器的數(shù)量密切相關(guān)，在初始檢測(cè)器數(shù)量較少的情況下，檢測(cè)器生成算法能較快地完成篩選檢測(cè)器的工作。而將人工免疫算法用于大數(shù)據(jù)系統(tǒng)時(shí)，初始檢測(cè)器的數(shù)量會(huì)達(dá)到幾十萬(wàn)、甚至上億的規(guī)模，篩選檢測(cè)器所需的時(shí)間與空間開(kāi)銷將非常巨大，導(dǎo)致無(wú)法使用現(xiàn)有的人工免疫算法。在現(xiàn)有檢測(cè)器生成算法的研究中，主要是針對(duì)如何提高對(duì)非自體的識(shí)別率、優(yōu)化自體和檢測(cè)器的匹配規(guī)則，缺乏針對(duì)海量初始檢測(cè)器時(shí)可計(jì)算性的考慮。因此，在大數(shù)據(jù)系統(tǒng)中應(yīng)用人工免疫算法時(shí)，如何提高篩選檢測(cè)器的效率是急需解決的重要問(wèn)題。

并行化是提高算法執(zhí)行速度的常用手段，通過(guò)將復(fù)雜的計(jì)算過(guò)程分解為多個(gè)可以并行執(zhí)行的部分，并分布到在多個(gè)處理核心上運(yùn)行以提高執(zhí)行的速度。但檢測(cè)器生成算法中匹配規(guī)則的計(jì)算復(fù)雜度較低，傳統(tǒng)并行計(jì)算方法所提高的計(jì)算效率很有限。而在初始檢測(cè)器數(shù)量龐大時(shí)，影響篩選檢測(cè)器時(shí)間和空間開(kāi)銷的主要因素是海量初始檢測(cè)器所導(dǎo)致的巨大匹配檢查次數(shù)，這是很典型的大數(shù)據(jù)應(yīng)用。因此通過(guò)構(gòu)建分布式的海量初始檢測(cè)器存儲(chǔ)系統(tǒng)，引入Map/Reduce模型設(shè)計(jì)新型的檢測(cè)器快速篩選算法，利用分布存儲(chǔ)節(jié)點(diǎn)的并行計(jì)算能力提高篩選海量初始檢測(cè)器的效率是良好的選擇。

本文分析初始檢測(cè)器數(shù)量巨大時(shí)，影響檢測(cè)器生成算法執(zhí)行速度的因素，在此基礎(chǔ)上構(gòu)建混合式的海量初始檢測(cè)器快速篩選架構(gòu)，設(shè)計(jì)海量初始檢測(cè)器分區(qū)檢查策略和成熟檢測(cè)器集優(yōu)化策略，從而對(duì)海量初始檢測(cè)器進(jìn)行快速篩選。本文同時(shí)實(shí)現(xiàn)了面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法的原型系統(tǒng)，并使用通用數(shù)據(jù)集進(jìn)行測(cè)試與分析。

2 相關(guān)工作

文獻(xiàn)［1-2］給出了人工免疫系統(tǒng)中經(jīng)典的否定選擇算法、貪心檢測(cè)器生成算法、r連續(xù)位匹配規(guī)則等;文獻(xiàn)［3］引入多種群遺傳算法，提高所生成檢測(cè)器對(duì)非自體的覆蓋率，雖然提高了非自體的覆蓋率，但是隨著問(wèn)題規(guī)模的不斷擴(kuò)大和搜索空間的更加復(fù)雜，遺傳算法在實(shí)際應(yīng)用中有一定的局限性，不能表現(xiàn)出算法的優(yōu)越性，易出現(xiàn)迭代次數(shù)多、收斂速度慢、易陷入局部最優(yōu)值和過(guò)早收斂等問(wèn)題;文獻(xiàn)［4-5］給出了檢測(cè)器克隆選擇算法;文獻(xiàn)［6］設(shè)計(jì)了動(dòng)態(tài)的克隆選擇算法，這些算法都能提高動(dòng)態(tài)環(huán)境下克隆選擇算法的適應(yīng)能力，但未考慮檢測(cè)器和自體數(shù)量對(duì)檢測(cè)器生成效率的影響;文獻(xiàn)［7-8］給出了抗獨(dú)特型克隆選擇算法，提高了生成檢測(cè)器的效率;文獻(xiàn)［9］引入聚類算法提高檢測(cè)器的生成速度;文獻(xiàn)［10］針對(duì)基于海明距離的匹配規(guī)則，給出了啟發(fā)式檢測(cè)器生成算法;文獻(xiàn)［11］通過(guò)改變初始檢測(cè)器的生成方法，提高了生成成熟監(jiān)測(cè)器的效率及其檢測(cè)非自體的效率和準(zhǔn)確性。此外還有大量對(duì)現(xiàn)有檢測(cè)器生成算法的改進(jìn)，但均集中在提高識(shí)別非自體準(zhǔn)確性和少量數(shù)據(jù)環(huán)境下提高效率等方面，沒(méi)有考慮人工免疫算法用于大數(shù)據(jù)環(huán)境時(shí)會(huì)出現(xiàn)的問(wèn)題以及相應(yīng)的優(yōu)化方法。

文獻(xiàn)［12］設(shè)計(jì)了 Map/Reduce計(jì)算模型，用于解決分布式存儲(chǔ)系統(tǒng)中海量數(shù)據(jù)的計(jì)算問(wèn)題;文獻(xiàn)［13］給出了大數(shù)據(jù)系統(tǒng)的特征，針對(duì)流式計(jì)算系統(tǒng)，分析了目前大數(shù)據(jù)流式計(jì)算在低延遲、高吞吐、持續(xù)可靠運(yùn)行方面存在的技術(shù)挑戰(zhàn);文獻(xiàn)［14-16］給出了大數(shù)據(jù)流式計(jì)算系統(tǒng)的架構(gòu)，以及大數(shù)據(jù)流式計(jì)算與復(fù)雜事件處理的關(guān)鍵技術(shù);文獻(xiàn)［17］介紹了Map/Reduce和傳統(tǒng)數(shù)據(jù)庫(kù)技術(shù)的融合。當(dāng)前主要利用Map/Reduce提高數(shù)據(jù)分析的效率、對(duì)大數(shù)據(jù)流進(jìn)行處理、提高數(shù)據(jù)處理的準(zhǔn)確度、以及與傳統(tǒng)數(shù)據(jù)庫(kù)技術(shù)的融合等方面，較少有關(guān)于利用MapReduce模型提高大數(shù)據(jù)環(huán)境下人工免疫系統(tǒng)檢測(cè)器生成算法效率方面的研究。

3 海量初始檢測(cè)器快速篩選算法

檢測(cè)器生成算法中需要使用匹配規(guī)則檢查每個(gè)自體和每個(gè)初始檢測(cè)器，才能選擇出成熟的檢測(cè)器，因此篩選檢測(cè)器的效率與初始檢測(cè)器和自體數(shù)量密切相關(guān)，所需進(jìn)行匹配檢查的次數(shù)與初始檢測(cè)器和自體數(shù)量之間呈指數(shù)級(jí)遞增關(guān)系。在大數(shù)據(jù)環(huán)境下，必然出現(xiàn)海量的初始檢測(cè)器或自體，現(xiàn)有檢測(cè)器生成算法無(wú)法在有限時(shí)間內(nèi)完成篩選初始檢測(cè)器的任務(wù)。因此，在大數(shù)據(jù)環(huán)境下提高篩選檢測(cè)器的效率是急需解決的關(guān)鍵問(wèn)題。

在人工免疫算法中，自體與初始檢測(cè)器是2個(gè)互補(bǔ)的集合，因此，在大數(shù)據(jù)環(huán)境下，當(dāng)自體的數(shù)量較少時(shí)，初始檢測(cè)器必然非常巨大，反之亦然。本文針對(duì)初始檢測(cè)器數(shù)量巨大的情況，設(shè)計(jì)快速初始檢查器篩選算法，利用多個(gè)節(jié)點(diǎn)的分布式計(jì)算能力提高與自體匹配檢查的速度，再進(jìn)行匯總，從而快速構(gòu)建成熟監(jiān)測(cè)器集。

本文首先給出海量初始檢測(cè)器快速篩選算法的結(jié)構(gòu)，再給出各階段的具體流程。

3．1 混合式海量初始檢測(cè)器快速篩選架構(gòu)

本文針對(duì)大數(shù)據(jù)環(huán)境下海量初始檢測(cè)器和有限自體的特點(diǎn)，根據(jù)初始檢測(cè)器篩選算法的要求，通過(guò)初始檢測(cè)器和自體的合理冗余與分布，構(gòu)建適合快速篩選海量初始檢測(cè)器的環(huán)境。首先改變現(xiàn)有檢測(cè)器生成算法中集中存儲(chǔ)初始檢測(cè)器的方式，將海量初始檢測(cè)器分散存儲(chǔ)到Hadoop集群中的各個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)中，為快速篩選初始檢測(cè)器奠定基礎(chǔ)。同時(shí)改變自體的存儲(chǔ)方式，在每個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)中均存儲(chǔ)數(shù)量較小的自體集，為篩選初始檢測(cè)器提供依據(jù)。由此本文設(shè)計(jì)的混合式的海量初始檢測(cè)器快速篩選架構(gòu)如圖1所示。

圖1 混合式海量初始檢測(cè)器快速篩選架構(gòu)

在Hadoop集群中分散存儲(chǔ)海量的初始檢測(cè)器，能利用存儲(chǔ)與計(jì)算節(jié)點(diǎn)的并行計(jì)算能力提高檢查初始檢測(cè)器與自體匹配的效率;而在各個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)中冗余保存數(shù)量相對(duì)較少的自體，能使得各個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)都能分擔(dān)檢查初始檢測(cè)器的任務(wù)。

使用Map/Reduce模型，能將海量初始檢測(cè)器篩選算法分為分區(qū)檢查和匯總優(yōu)化2個(gè)階段，首先利用Hadoop集群中的存儲(chǔ)與計(jì)算節(jié)點(diǎn)分布式檢查海量初始檢測(cè)器是否與自體匹配，并將相應(yīng)結(jié)果提交給優(yōu)化節(jié)點(diǎn)，優(yōu)化節(jié)點(diǎn)再根據(jù)檢查結(jié)果挑選最優(yōu)的若干初始檢測(cè)器構(gòu)成成熟檢測(cè)器集。

3．2 海量初始檢測(cè)器分區(qū)檢查策略

本文利用Map/Reduce模型中Map階段在各存儲(chǔ)與計(jì)算節(jié)點(diǎn)中分布式并發(fā)執(zhí)行的特點(diǎn)，在將海量初始檢測(cè)器子集保存到各存儲(chǔ)與計(jì)算節(jié)點(diǎn)的基礎(chǔ)上，設(shè)計(jì)海量初始檢測(cè)器分區(qū)監(jiān)測(cè)策略。

首先將數(shù)量有限的自體保存到存儲(chǔ)與計(jì)算節(jié)點(diǎn)的內(nèi)存中，依據(jù)匹配規(guī)則，與該存儲(chǔ)與計(jì)算節(jié)點(diǎn)海量初始檢測(cè)器子集中的檢測(cè)器進(jìn)行匹配檢查，判斷該海量初始檢測(cè)器子集中的那些初始檢測(cè)器能成為候選成熟檢測(cè)器，同時(shí)將候選成熟檢測(cè)器以及與自體之間的最大匹配值發(fā)送給優(yōu)化節(jié)點(diǎn)，具體步驟如下述算法所示。其中，detector_subset表示某個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)中保存的海量初始檢測(cè)器子集;self_set表示自體集。

算法通過(guò)循環(huán)取出未檢測(cè)的初始檢測(cè)器對(duì)其進(jìn)行初始設(shè)置，最大匹配度為0、候選成熟檢測(cè)器的初始標(biāo)志位1;然后循環(huán)與系統(tǒng)中未檢測(cè)的自體進(jìn)行匹配，如果匹配度小于系統(tǒng)設(shè)定的閾值且大于最大匹配度則設(shè)置該初始檢測(cè)器的候選成熟標(biāo)志為1，反之則設(shè)置非成熟標(biāo)志為0;確定了檢測(cè)器為候選的成熟的檢測(cè)器之后，向優(yōu)化節(jié)點(diǎn)輸出該候選成熟檢測(cè)器、以及與自體之間的最大匹配度max_match，進(jìn)行下一步的優(yōu)化;該算法的計(jì)算量主要依賴于該大數(shù)據(jù)系統(tǒng)中初始檢測(cè)器的數(shù)量，隨著初始檢測(cè)器數(shù)量的增長(zhǎng)呈線性增長(zhǎng)趨勢(shì);算法的復(fù)雜度為小于O(n2)。

海量初始檢測(cè)器分區(qū)檢查策略利用了Map/Reduce模型中Map階段分布式執(zhí)行的特點(diǎn)，在將海量初始檢測(cè)器分區(qū)分布存儲(chǔ)到集群中不同存儲(chǔ)與計(jì)算節(jié)點(diǎn)的基礎(chǔ)上，每個(gè)存儲(chǔ)與計(jì)算節(jié)點(diǎn)中分別檢查對(duì)應(yīng)分區(qū)中初始檢測(cè)器是否能成為候選成熟檢測(cè)器，能利用大量存儲(chǔ)與計(jì)算節(jié)點(diǎn)的分布式并行計(jì)算能力提高檢查初始檢測(cè)器效率;同時(shí)各存儲(chǔ)與計(jì)算節(jié)點(diǎn)僅將候選成熟檢測(cè)器提交給優(yōu)化節(jié)點(diǎn)，能有效減少網(wǎng)絡(luò)通信量。

3．3 成熟檢測(cè)器集優(yōu)化策略

人工免疫系統(tǒng)中一般僅使用一定數(shù)量的成熟檢測(cè)器檢測(cè)非自體，各存儲(chǔ)與計(jì)算節(jié)點(diǎn)篩選的候選成熟檢測(cè)器通常遠(yuǎn)多與檢測(cè)非自體所需的成熟檢測(cè)器，但各個(gè)候選成熟檢測(cè)器在檢測(cè)非自體能力等方面存在差異，因此，需要合理選擇部分候選成熟檢測(cè)器用于人工免疫系統(tǒng)檢測(cè)非自體。

集群中各存儲(chǔ)與計(jì)算節(jié)點(diǎn)在反饋候選成熟檢測(cè)器的同時(shí)也反饋了與自體之間的最大匹配度，這反映了候選成熟檢測(cè)器與自體之間的相識(shí)程度，而候選成熟檢測(cè)器對(duì)非自體的覆蓋能力則與之相反。本文設(shè)計(jì)成熟檢測(cè)器優(yōu)化策略，在優(yōu)化節(jié)點(diǎn)中利用Reduce階段對(duì)候選成熟檢測(cè)器進(jìn)行整理和優(yōu)化，挑選最適合的候選成熟檢測(cè)器用于檢測(cè)非自體，具體步驟如下述算法所示。其中，detector_set表示候選成熟檢測(cè)器集，保存全部存儲(chǔ)與計(jì)算節(jié)點(diǎn)發(fā)送給優(yōu)化節(jié)點(diǎn)的候選成熟檢測(cè)器;detector_mature表示成熟檢測(cè)器集，保存優(yōu)化后用于檢測(cè)非自體的成熟檢測(cè)器。

算法對(duì)海量初始檢測(cè)器分區(qū)監(jiān)測(cè)策略的結(jié)果進(jìn)行統(tǒng)計(jì)優(yōu)化，對(duì)海量候選的成熟的檢測(cè)器按照最大匹配度從小到大進(jìn)行排序并構(gòu)建集合，然后循環(huán)取出這些候選成熟的檢測(cè)器并同時(shí)判斷是否檢測(cè)器數(shù)量達(dá)到系統(tǒng)的設(shè)定值，如果未達(dá)到則取出集合中第一個(gè)候選成熟檢測(cè)器放入優(yōu)化的集合中;該算法主要依賴于分區(qū)檢查策略的產(chǎn)生的候選成熟檢測(cè)器的數(shù)量，并且隨著該數(shù)量的增長(zhǎng)呈線性增長(zhǎng)趨勢(shì);該算法的時(shí)間復(fù)雜度小于O(n)。

成熟檢測(cè)器集優(yōu)化策略能依據(jù)候選成熟檢測(cè)器與自體的匹配度，優(yōu)先選擇與自體匹配度小的檢測(cè)器構(gòu)建成熟檢測(cè)器集，從而提高所構(gòu)建的成熟檢測(cè)器集對(duì)非自體的檢測(cè)率和檢測(cè)效率;集群中各存儲(chǔ)與計(jì)算節(jié)點(diǎn)使用海量初始檢測(cè)器分區(qū)檢查策略時(shí)僅將候選成熟檢測(cè)器提交給了優(yōu)化節(jié)點(diǎn)，因此，優(yōu)化節(jié)點(diǎn)中所需處理的候選成熟檢測(cè)器數(shù)量非常有限，保證了從候選成熟檢測(cè)器集中選擇成熟檢測(cè)器時(shí)的效率。

4 原型系統(tǒng)的測(cè)試與分析

本文構(gòu)建了擁有4個(gè)節(jié)點(diǎn)的Hadoop集群，采用二進(jìn)制字符串的形式表示自體、初始檢測(cè)器和成熟檢測(cè)器，使用r連續(xù)位匹配規(guī)則判斷初始檢測(cè)器與自體是否匹配，在存儲(chǔ)和計(jì)算節(jié)點(diǎn)增加海量初始檢測(cè)器分區(qū)檢查子模塊，主控節(jié)點(diǎn)增加成熟檢測(cè)器優(yōu)化子模塊構(gòu)成優(yōu)化節(jié)點(diǎn)，實(shí)現(xiàn)面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法的原型系統(tǒng)。在原型系統(tǒng)中，包括一個(gè)主控節(jié)點(diǎn)和3個(gè)存儲(chǔ)和計(jì)算節(jié)點(diǎn)，配置如表1所示。

表1 原型系統(tǒng)的配置

使用用于E-mail安全檢測(cè)的標(biāo)準(zhǔn)數(shù)據(jù)集CERT synthethic sendmail data作為測(cè)試數(shù)據(jù)集，通過(guò)抽取CERT synthethic sendmail data中的記錄，解析成24位二進(jìn)制字符串構(gòu)建自體集。

4．1 生成檢測(cè)器所需的時(shí)間開(kāi)銷

本文同時(shí)也實(shí)現(xiàn)了傳統(tǒng)檢測(cè)器生成算法的原型系統(tǒng)，用于比較。設(shè)置初始檢測(cè)器的數(shù)量分別為5×104，10 × 104，2 × 105，5 × 105，1 × 106，自體數(shù)據(jù)為5 000，測(cè)試傳統(tǒng)檢測(cè)器生成算法和面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法的時(shí)間開(kāi)銷，結(jié)果如圖2所示。

圖2 不同檢測(cè)器生成算法的時(shí)間開(kāi)銷

從圖2可知，在初始檢測(cè)器的數(shù)量分別從5×104增加到1×106，相比傳統(tǒng)的檢測(cè)器生成算法，面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法均能明顯減少生成檢測(cè)器所需的時(shí)間開(kāi)銷，所減少的時(shí)間開(kāi)銷在58．87% ～83．17%之間;同時(shí)隨著初始檢測(cè)器數(shù)量的大幅度增加，面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法所減少的時(shí)間開(kāi)銷呈現(xiàn)緩慢上升，這是由于存儲(chǔ)和計(jì)算節(jié)點(diǎn)的數(shù)量沒(méi)有增加，而每個(gè)存儲(chǔ)和計(jì)算節(jié)點(diǎn)中需要處理的初始檢測(cè)器數(shù)量上升，從而導(dǎo)致了總時(shí)間開(kāi)銷的增加;但相比傳統(tǒng)檢測(cè)器生成算法，時(shí)間開(kāi)銷的增加幅度明顯減少;這驗(yàn)證了面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法具有顯著減低生成檢測(cè)器所需時(shí)間開(kāi)銷的能力。

4．2 初始檢測(cè)器數(shù)量變化時(shí)分區(qū)檢查的時(shí)間開(kāi)銷

設(shè)置初始檢測(cè)器的數(shù)量分別為5×104，1×105，2 ×105，5 ×105，1 ×106，5 ×106，1 ×107，自體數(shù)據(jù)為5 000，測(cè)試海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷，與面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法總時(shí)間開(kāi)銷進(jìn)行比較，結(jié)果如圖3所示。

圖3 初始檢測(cè)器數(shù)量變化時(shí)的時(shí)間開(kāi)銷

從圖3中可知，海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷隨著初始檢測(cè)器數(shù)量的增加而上升，上升幅度與面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法總的時(shí)間開(kāi)銷基本一致;同時(shí)海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷占據(jù)了生成檢測(cè)器總時(shí)間開(kāi)銷的75%以上;因此海量初始檢測(cè)器的分區(qū)檢查是影響面向大數(shù)據(jù)系統(tǒng)檢測(cè)器篩選算法效率的主要因素。當(dāng)前Hadoop集群中僅有3個(gè)節(jié)點(diǎn)執(zhí)行海量初始檢測(cè)器分區(qū)檢查子模塊，在增加節(jié)點(diǎn)數(shù)量后可有效的減低海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷，進(jìn)而提高面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法的效率。

4．3 節(jié)點(diǎn)數(shù)量變化時(shí)分區(qū)檢查的時(shí)間開(kāi)銷

設(shè)置初始檢測(cè)器的數(shù)量為100萬(wàn)，增加集群中存儲(chǔ)和計(jì)算節(jié)點(diǎn)的數(shù)量，分別為3個(gè)、4個(gè)、5個(gè)和6個(gè)，測(cè)試海量初始檢測(cè)器分區(qū)檢查的時(shí)間開(kāi)銷，并與檢測(cè)器快速篩選算法的總時(shí)間開(kāi)銷進(jìn)行比較。結(jié)果如圖4所示。

圖4 存儲(chǔ)和計(jì)算節(jié)點(diǎn)數(shù)量變化時(shí)的時(shí)間開(kāi)銷

從圖4中可以發(fā)現(xiàn)，通過(guò)增加集群的存儲(chǔ)和計(jì)算節(jié)點(diǎn)數(shù)量，海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷明顯減少，當(dāng)節(jié)點(diǎn)數(shù)從3增加到6后時(shí)間開(kāi)銷減少了接近一半，同時(shí)面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法的時(shí)間開(kāi)銷也呈現(xiàn)明顯下降趨勢(shì);這是由于增加存儲(chǔ)和計(jì)算節(jié)點(diǎn)，能有效地減少每個(gè)存儲(chǔ)和計(jì)算節(jié)點(diǎn)需要檢查的初始檢測(cè)器數(shù)量，從而減少了檢查海量初始檢測(cè)器所需的時(shí)間開(kāi)銷。以上結(jié)論驗(yàn)證了:雖然海量初始檢測(cè)器分區(qū)檢查所需的時(shí)間開(kāi)銷占生成檢測(cè)器總時(shí)間開(kāi)銷的75%以上，但通過(guò)增加集群節(jié)點(diǎn)數(shù)量能明顯減少所需的時(shí)間開(kāi)銷，從而在初始檢測(cè)器數(shù)量不斷增加時(shí)，仍然能快速生成檢測(cè)器。

4．4 優(yōu)化成熟檢測(cè)器集的時(shí)間開(kāi)銷

采用同樣的設(shè)置參數(shù)，測(cè)試成熟檢測(cè)器集優(yōu)化所需的時(shí)間開(kāi)銷，并與面向大數(shù)據(jù)系統(tǒng)檢測(cè)器快速篩選算法總時(shí)間開(kāi)銷進(jìn)行比較，結(jié)果如圖5所示。

圖5 分區(qū)檢查階段和成熟檢測(cè)器優(yōu)化階段的時(shí)間開(kāi)銷

從圖5中可以發(fā)現(xiàn)，優(yōu)化成熟檢測(cè)器集所需的時(shí)間開(kāi)銷同樣也隨著初始檢測(cè)器數(shù)量的增加而上升，但增加幅度明顯小于初始檢測(cè)器數(shù)量增加的幅度，這是由于海量初始檢測(cè)器分區(qū)檢查之后所產(chǎn)生的候選成熟檢測(cè)器數(shù)量已非常有限;同時(shí)優(yōu)化成熟檢測(cè)器集所需的時(shí)間開(kāi)銷僅占生成檢測(cè)器總時(shí)間開(kāi)銷的25%以內(nèi)，對(duì)面向大數(shù)據(jù)系統(tǒng)檢測(cè)器篩選算法效率的影響很小;因此，集群中一個(gè)節(jié)點(diǎn)足以完成優(yōu)化成熟檢測(cè)器集的任務(wù)。

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

檢測(cè)器生成算法是人工免疫系統(tǒng)的重要組成部分，也是決定人工免疫系統(tǒng)準(zhǔn)確性和效率的關(guān)鍵因素。在大數(shù)據(jù)環(huán)境下，現(xiàn)有檢測(cè)器生成算法難以在有限的時(shí)間內(nèi)完成對(duì)數(shù)量龐大的初始檢測(cè)器的篩選。本文針對(duì)初始檢測(cè)器數(shù)量龐大的情況，給出了混合式的初始檢測(cè)器快速篩選架構(gòu)，通過(guò)將海量初始檢測(cè)器分布存儲(chǔ)，為快速篩選檢測(cè)器奠定基礎(chǔ)。設(shè)計(jì)了海量初始檢測(cè)器分區(qū)檢查策略和成熟檢測(cè)器集優(yōu)化策略，利用 Map/Reduce模型中 Map和Reduce階段的不同特性，提高篩選初始檢測(cè)器的效率，優(yōu)化成熟檢測(cè)器;并在Hadoop集群中實(shí)現(xiàn)了原型系統(tǒng)，使用CERT synthethic sendmail data數(shù)據(jù)集進(jìn)行了測(cè)試與分析，結(jié)果表明，面向大數(shù)據(jù)系統(tǒng)的檢測(cè)器快速篩選算法能減少58．87%的時(shí)間開(kāi)銷，并能在初始檢測(cè)器數(shù)量不斷增加時(shí)保持時(shí)間開(kāi)銷的穩(wěn)定。

目前面向大數(shù)據(jù)系統(tǒng)的檢測(cè)器快速篩選算法的研究主要是針對(duì)如何提高篩選成熟檢測(cè)器時(shí)效率和保證算法在大數(shù)據(jù)環(huán)境下的可用性方面。下一步將針對(duì)大數(shù)據(jù)環(huán)境特點(diǎn)，對(duì)檢測(cè)器表示方法、匹配規(guī)則、檢測(cè)率和對(duì)非自體的覆蓋率等方面展開(kāi)研究。

［1］ Forrest S，Helman P．An ImmunologicalApproach to Change Detection:Algorithms，Analysis，and Implications［C］//Proceedings of IEEE Symposium on Computer Security and Privacy．Washington D．C．，USA:IEEE Press，1996:192-211．

［2］ Forrest S，Perelson A S，Allen S，et al．Self-nonself Discrimination in a Computer［C］//Proceedings of IEEE Symposium on Research in Security and Privacy．Washington D．C．，USA:IEEE Press，1994:202-212．

［3］ 楊東勇，陳晉因．基于多種群遺傳算法的檢測(cè)器生成算法研究［J］．自動(dòng)化學(xué)報(bào)，2009，35(4):425-432．

［4］ de Castro L N，von Zuben F J．The Clonal Selection Algorithm with Engineering Applications［C］//Proceedings of GECCO’00．San Francisco，USA:Morgan Kaufmann Publishers，2000:36-37．

［5］ de Castro L N，von Zuben F J．Learning and Optimization Using the Clonal Selection Principle［J］．IEEE Transactions on Evolutionary Computation，2002，6(3):239-251．

［6］ Kim J，Bentley P J．Towards an Artificial Immune System for Network Intrusion Detection:An Investigation of Clonal Selection with a Negative Selection Operator［C］//Proceedings ofCongress on Evolutionary Computation．Piscataway，USA:IEEE Press，2001:1244-1252．

［7］ 焦李成，杜海峰，劉 芳，等．免疫優(yōu)化計(jì)算、學(xué)習(xí)與識(shí)別［M］．北京:科學(xué)出版社，2006．

［8］ 張立寧，公茂果，焦李成，等．抗獨(dú)特型克隆選擇算法［J］．軟件學(xué)報(bào)，2009，20(5):1269-1281．

［9］ Agrawal R，Srikant R．Fast Algorithms for Mining Association Rules［C］//Proceedings of the 20th VLDB Conference．Santiago，USA:Morgan Kaufmann，1994:487-499．

［10］ Luo Wenjian，Zhang Zeming，Wang Xufa．A Heuristic Detector Generation Algorithm for Negative Selection Algorithm with Hamming Distance Partial Matching Rule［C］//Proceedings of the 5th International Conference on Artificial Immune Systems．Oeiras，Portugal:［s．n．］，2006:229-243．

［11］ Jiang Hua，Wang Xin，F(xiàn)an Xiaofeng．Research on Linear Time Detector Generating Algorithm Based on Negative Selection Model［C］//Proceedings of CCDC’09．Washington D．C．，USA:IEEE Press，2009:3058-3061．

［12］ Dean J，GhemawatS．MapReduce:Simplified Data Processing on Large Clusters［J］．Communications of the ACM，2008，51(1):107-113．

［13］ 孫大為，張廣艷，鄭緯民．大數(shù)據(jù)流式計(jì)算:關(guān)鍵技術(shù)及系統(tǒng)實(shí)例［J］．軟件學(xué)報(bào)，2014，25(4):839-862．

［14］ Scalosub G，Marbach P，Liebeherr J．Buffer Management for Aggregated Streaming Data with Packet Depen-dencies［J］．IEEE Transactions on Parallel and Distributed Systems，2013，24(3):439-449．

［15］ Malensek M，Pallickara S L，Pallickara S．Exploiting Geospatial and ChronologicalCharacteristicsin Data Streams to Enable Efficient Storage and Retrievals［J］．Future Generation Computer Systems，2013，29(4):1049-1061．

［16］ Cugola G，Margara A．Processing Flows of Information:From Data Stream to Complex Event Processing［J］．ACM Computing Surveys，2012，44(3):151-162．

［17］ 覃雄派，王會(huì)舉，杜小勇，等．大數(shù)據(jù)分析——RDBMS與MapReduce的競(jìng)爭(zhēng)與共生［J］．軟件學(xué)報(bào)，2012，23(1):32-45．