1、云計算及免疫調度算法研究,制作人：楊曉飛 學號：M100786 QQ: 296754711 E-mail：yang-,計算模式分合演義,主機系統(tǒng)與集中計算 大型主機的一個特點就是資源集中，計算、存儲集中。這是集中計 算模式的典型代表。 效用計算 關鍵技術是自愿使用計量，它保證了按使用付費的準確性。,個人計算機與桌面計算,分布式計算網(wǎng)絡的出現(xiàn) 網(wǎng)格計算 可以說，網(wǎng)格計算是超級計算機和集群計算機的延伸。其核心還是試圖去 解決一個巨大的單一的計算問題 SaaS通過Internet來提供軟件,大 綱,一、云計算 1. 起源和定義 2. 相關比較 3. 應用案例 二、相關免疫調度算法應用 1.免疫算法簡

2、介 1.分布式 2.網(wǎng)格 3.對等網(wǎng)絡 三、云計算中的免疫調度研究 參考文獻,一、云計算 1. 起源和定義,“全世界只需要5臺電腦就足夠了!”托馬斯沃森 “無論對誰來說,640K內(nèi)存都足夠了?！北葼柹w茨,計算模式發(fā)展歷史 縱觀計算模式的演變歷史，基本可總結為：集中 分散 集中 其發(fā)展歷史如下圖所示：,云計算發(fā)展歷程,2006年亞馬遜(Anmzon) 推出了彈性計算云(Elastic Computer Cloud ES2)服務 2007年，Sun公司推出了移動數(shù)據(jù)中心SunBhckbox 2007年11月，IBM宣布了“藍云”計劃 2008年4月，google開放google app engin

3、e平臺 2009年，思科先后發(fā)布統(tǒng)一計算系統(tǒng)（UCS）、云計算服務平臺，并與EMC，Vmware建立虛擬計算環(huán)境聯(lián)盟。 2009年7月，中國首個企業(yè)云計算平臺（中化企業(yè)云計算平臺）誕生 2010年1月，微軟公司正式發(fā)布WindowsAzure云平臺服務 2010年4月，Dell推出源于DCS部門設計的PowerEdgeC系列云計算服務器及相關服務。 2010年5月，中國電信正式啟動星云計劃，目前已在4個城市開展云計算現(xiàn)場試驗,云計算,云計算到底是什么？許多人對云計算的理解就如同盲人摸象：,云計算（Cloud Computing）是一種新型的計算模式，Sun公司最早提出了“網(wǎng)絡就是計算機”的理念

4、，算是對云計算的一個最初描述和定義，也表明了Sun公司的遠見5。 在這種模式中，應用、數(shù)據(jù)和IT資源以服務的方式通過網(wǎng)絡提供給用戶使用。 描述 云計算是一種有大規(guī)模商業(yè)驅動的計算模式，它能夠根據(jù)外部用戶需求，從一個抽象的虛擬的可動態(tài)增長的資源池中動態(tài)地提供用戶需求的計算能力、存儲能力和服務等其他請求。,云 是一組數(shù)量眾多的、互聯(lián)到一起的計算機，這些計算機可以是個人電腦或網(wǎng)絡服務器，它們可以是公共或私有的4。,云計算超越桌面,在云時代，程序和數(shù)據(jù)一切托管在一個云狀的、可通過因特網(wǎng)訪問的、有個人計算機和服務器構成的集合中，不再受到桌面的限制。 從計算機方式來說，云計算的出現(xiàn)相當于一個世紀以前的電力

5、革命。從公用企業(yè)購買電力，其價格比他們自己生產(chǎn)更低（可靠性更高）,云計算通過將物理資源轉換成可伸縮的虛擬共享資源，使得企業(yè)能夠將資源分配到需要資源的應用上，即根據(jù)需求來訪問資源（計算機處理器和存儲系統(tǒng)等）。,之所以稱為“云”，是因為它在某些方面具有云的特征： -云一般都較大； -云的規(guī)模可以動態(tài)伸縮，它的邊界是模糊的； -云在空中飄忽不定，你無法也無需確定它的具體位置，但它確實存在于某處。 -之所以稱為“云”，還因為云計算的鼻祖之一亞瑪遜公司將曾經(jīng)大家稱作為網(wǎng)格計算的東西，取了一個新名稱“彈性計算云”(EC2)，并取得了商業(yè)上的成功。,通過云計算，用戶可以訪問大量的計算和存儲資源，并且不需要了

6、解服務器在哪里，不用關心內(nèi)部如何運作，通過高速互聯(lián)網(wǎng)就可以透明地使用各種資源。,云計算并不是一個單獨的服務，而是一個服務集合。 根據(jù)其服務集合所提供的服務類型，整個云計算服務集合被劃分成4個層次：應用層、平臺層、基礎設施層和虛擬化層。這些層定義了提供的服務的級別，每一層都對應著一個子服務集合，為云計算服務層次如下圖所示：,云計算的層次及服務,相關云產(chǎn)品,在云計算服務體系結構中各層次與相關云產(chǎn)品對應： 應用層對應SaaS軟件即服務如：Google APPS、SoftWare+Services； 平臺層對應PaaS平臺即服務如：IBM IT Factory、 Google APPEngine、F；

7、 基礎設施層對應IaaS基礎設施即服務如：Amazon Ec2、 IBM Blue Cloud、Sun Grid； 虛擬化層對應硬件即服務結合Paas提供硬件服務，包括 服務器集群及硬件檢測等服務。,云系統(tǒng)的結構,由下圖可以看出，云計算是一種生產(chǎn)者消費者模型，云計算系統(tǒng)采用以太網(wǎng)等快速網(wǎng)絡將若干集群連接在一起，用戶通過因特網(wǎng)獲取云計算系統(tǒng)提供的各種數(shù)據(jù)處理服務。,云計算的系統(tǒng)結構,三、應用案例,Google Apps Google Docs：將文檔存儲在Google的服務器上，而不是自己的電腦上。Google Gmail ：當用戶需求激增，Google的云計算系統(tǒng)會自動為Gmail增加容量和處

8、理器的數(shù)量，而無需人工干預。 依賴云計算，谷歌能以幾乎可以忽略不計的成本增加新的服務 如果新增的服務失敗了，那沒關系，關掉并且忘掉它就可以。 如果成功了，系統(tǒng)會自動為它增加空間和處理能力。 IBM 合資與Google建立數(shù)據(jù)中心，支持向卡耐基-梅隆大學、麻省理工大學、斯坦福大學、加州大學伯克萊分校、馬里蘭州大學和華盛頓大學等6所大學的計算機科學研究者提供資金與設備，推動云計算的研究。 IBM有著得天獨厚的優(yōu)勢：應用服務器、存儲、管理軟件，樣樣具備。 IBM通過向客戶出售云計算方案與終端，協(xié)助企業(yè)建立屬于自己的云計算模型的數(shù)據(jù)中心。,云的案例,Windows live 面對Google的挑戰(zhàn)，微

9、軟試圖以Windows Live為基礎，聯(lián)結起數(shù)以億計的Windows用戶，并向他們提供云計算，在線存儲是微軟邁出的關鍵一步，比爾蓋茨在2007年夏天說：“當你想到存儲，就會想到Windows Live?！?Amazon “彈性計算云”服務 企業(yè)可以以極低的成本投入獲得極高的計算能力，不用再投資購買昂貴的硬件設備，負擔頻繁的保養(yǎng)與升級。 云計算的妙處之一，即是按需分配的計算方式能夠充分發(fā)揮大型計算機群的性能。如果你只需使用5%的資源，就只需要付出5%的價格，而不必像以前那樣，為100%的設備買單。,云的價值,云計算的本質就是通過整合、共享和動態(tài)的提供資源來實現(xiàn)IT投資利用率的最大化，它包括了新

10、投資的資源和已投資的資源。 因此，實施云計算不需要舍棄原有的IT基礎設施資源。 云計算的實施不僅可以利用已有的IT基礎設施資源，而且云計算可以高效地監(jiān)控管理IT基礎設施資源。 因此，實施云計算將使資源更容易被充分利用。 云計算的按使用量付費的經(jīng)濟模式，特別是云計算的彈性，能夠使企業(yè)快速應對市場變化,三、相關比較,云計算的服務層次是根據(jù)服務類型即服務集合來劃分，與大家熟悉的計算機網(wǎng)絡體系結構中層次的劃分不同： 計算機網(wǎng)絡分為七層結構：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡層、傳輸層、會話層、表示層、應用層。 每個層次都實現(xiàn)一定的功能，層與層之間有一定關聯(lián)。 云計算體系結構中的層次是可以分割的，即某一層次可以單

11、獨完成一項用戶的請求而不需要其他層次為其提供必要的服務和支持。,云計算由網(wǎng)格計算演變而來,并將網(wǎng)格計算作為其骨干和基本結構?？梢哉f,云計算是網(wǎng)格計算的一種更高級的形式但是,這兩者之間在現(xiàn)實中存在著巨大的區(qū)別如圖所示，具體可以參見文獻5,云計算與網(wǎng)格計算,云計算與網(wǎng)格計算的層次比較,網(wǎng)格計算分別在五層體系框架上提供不同的協(xié)議和服務。在基礎架構層，網(wǎng)絡提供對不同資源的接入控制，例如計算資源、存儲資源、網(wǎng)絡資源等。網(wǎng)格計算通常依賴于已存在的組件，如本地資源管理等。,構造層包括原始的硬件級資源，如計算資源、存儲資源、網(wǎng)絡資源等。 虛擬資源層包括虛擬化和抽象化的資源，呈現(xiàn)給用戶和上集成的資源形式。 平臺

12、層即所謂的管理中間件，提供用戶管理、安全管理、資源管理、映像部署等。 應用層提供運行在云上的應用和服務。云計算可向用戶提供三種級別的服務，即SaaS，PaaS，IaaS8,網(wǎng)格協(xié)議體系結構,云計算體系結構,云計算與Web2.0,云計算是通過其基礎架構和基礎設施（互聯(lián)的計算機/服務器構成的作為一個整體運行的網(wǎng)絡）來定義的。 web2.0是通過使用者如何看待系統(tǒng)/使用系統(tǒng)提供的服務來定義的。換言之，云計算是關于計算機的，而web2.0是關于人的。 云計算專指將因特網(wǎng)作為一個計算平臺使用。 web2.0試圖探究和解釋該平臺的業(yè)務規(guī)則。 Web2.0的普及需要云計算的幫助，尤其是在Web2.0服務幾何

13、級增長的今天，云計算的發(fā)展如果跟不上，肯定是不行的。在云計算時代，如何更順暢地把應用交付到用戶，以保證用戶良好的體驗，對于Web2.0服務商來說，是必須要考慮的一個問題。 可以這樣說，云計算的發(fā)展和Web2.0的發(fā)展將是息息相關的，兩者相互推動的力量是巨大的。,幾種計算體系的關系,左側的超級計算和集群計算主要設計目標是解決大型的具體的計算問題。 中間是網(wǎng)格，其與云計算有一定的交集，起源于左側。 右側的云計算是以提供服務為目的。是從網(wǎng)格計算演化過來的，網(wǎng)格計算為其提供了基本的框架支持10,Ian Foster 眼中的計算體系關系,云計算的擔憂,下一個互聯(lián)網(wǎng)泡沫 企業(yè)數(shù)據(jù)的安全殺手 低成本面具下的

14、陰謀 企業(yè)IT人員的潛在殺手 其實，這樣的擔憂不難理解。云計算是一種全新的商業(yè)模式，并無章法可循。任一項新技術，從模糊的概念發(fā)展成為一個完整的朝陽產(chǎn)業(yè)，都會經(jīng)歷一個復雜的“蛻變”過程。所謂好事多磨，霧里看花，并不能抹殺花之美。 ,二、免疫算法的調度,1.免疫算法介紹,免疫算法的產(chǎn)生,生物免疫系統(tǒng)是一個高度進化、復雜的功能系統(tǒng)。當生物遭遇不同的抗原侵入時，其自身能快速的識別抗原，并產(chǎn)生相應的抗體。生物體中的抗原和抗體之間、抗體和抗體之間的相互作用，構成了生物系統(tǒng)的免疫平衡。人們借鑒生物免疫系統(tǒng)的學習、記憶和自適應調節(jié)的能力，形成了一種模擬免疫系統(tǒng)智能行為的仿生算法免疫算法IA（immune al

15、gorithm）,一般的免疫算法可分為三種情況: 模仿免疫系統(tǒng)抗體與抗原識別，結合抗體產(chǎn)生過程而抽象出來的免疫算法; 基于免疫系統(tǒng)中的其他特殊機制抽象出的算法，例如克隆選擇算法; 與遺傳算法等其他計算智能融合產(chǎn)生的新算法，例如免疫遺傳算法。,免疫系統(tǒng)的作用關系如下圖所示：,記憶細胞獲取,克隆選擇,細胞克隆,親和突變,克隆抑制,動態(tài)平衡維持,抗原,刺激應答,清除,免疫系統(tǒng)與一般免疫算法之間的比較,抗原要解決的問題 抗體最佳解向量 抗原識別問題識別 從記憶細胞產(chǎn)生抗體聯(lián)想過去的成功 淋巴細胞分化優(yōu)良解(記憶)的保持 細胞抑制剩余候選解的消除 抗體增加(細胞克隆)利用遺傳算子產(chǎn)生新抗體,免疫算法的工

16、作原理如圖所示：,記憶細胞演化,抗原識別及參數(shù)確定,募集新成員,編碼及初始抗體群,克隆選擇,親和突發(fā),細胞克隆,克隆抑制,免疫選擇,滿足終止條件,輸出結果,滿足,不滿足,免疫算法的一般步驟,Y,N,基于抗體克隆選擇學說和免疫網(wǎng)絡學說的一般免疫算法框架：,1.輸入抗原（說明：一般將目標函數(shù)和各種約束作為算法的抗原）； 2.產(chǎn)生初始抗體（說明：再接空間中用隨機的方法產(chǎn)生）； 3.當不滿足終止條件（通過限定迭代次數(shù)或在連續(xù)若干次的迭代中的最好解都無法改善，以及二者的混合形式作為終止條件)時，重復執(zhí)行下列步驟： 3.1 計算親和度； 3.2 更新記憶單元； 3.3 促進或抑制新抗體產(chǎn)生； 3.4 產(chǎn)生

17、新抗體； 4.輸出計算結果；,(1)識別抗原：免疫系統(tǒng)確認抗原入侵。 (2)產(chǎn)生初始抗體群體：激活記憶細胞產(chǎn)生抗體，清除以前出現(xiàn)過的抗原，從包含最優(yōu)抗體(最優(yōu)解)的數(shù)據(jù)庫中選擇出來一些抗體。 (3)計算親和力：計算抗體和抗原之間的親和力。 (4)記憶細胞分化：與抗原有最大親和力的抗體加給記憶細胞。由于記憶細胞數(shù)目有限，新產(chǎn)生的與抗原具有更高親和力的抗體替換較低親和力的抗體。 (5)抗體促進和抑制：高親和力抗體受到促進，高密度抗體受到抑制。通常通過計算抗體存活的期望值來實施。 (6)抗體產(chǎn)生:對未知抗原的響應，產(chǎn)生新淋巴細胞,免疫算法中的親和力計算方法,免疫算法中最復雜的計算是親和力計算。由于產(chǎn)

18、生于確定克隆類型的抗體分子獨特型是一樣的，抗原與抗體的親和力也是抗體與抗體的親和力的測量。 一般計算親和力的公式 : 其中，tk是抗原和抗體k的結合強度。,免疫算子,同生命科學中的免疫理論類似，免疫算子也分兩種類型：全免疫和目標免疫，二者分別對應于生命科學中的非特異性免疫和特異性免疫。其中，全免疫是指群體中每個個體在變異操作后，對其每一環(huán)節(jié)都進行一次免疫操作的免疫類型；目標免疫則指個體在進行變異操作后，經(jīng)過一定判斷，個體僅在作用點處發(fā)生免疫反應的一種類型。前者主要應用于個體進化的初始階段，而在進化過程中基本上不發(fā)生作用，否則將很有可能產(chǎn)生通常意義上所說的“同化現(xiàn)象”；后者一般而言將伴隨群體進化

19、的全部過程,也是免疫操作的一個常用算子。 免疫算子是由接種疫苗和免疫選擇兩部分操作構成的.,免疫算法流程 隨機產(chǎn)生初始父代種群A1 根據(jù)先驗知識抽取疫苗; 若當前群體中包含最佳個體,則算法停止運行并輸出結果;否則繼續(xù); 對于目前的第k 代父本種群Ak 進行交叉操作,得到種群Bk ; 對Bk 進行變異操作, 得到種群Ck ; 對Ck 進行接種疫苗操作,得到種群Dk ; 對Dk 進行免疫選擇操作,得到新一代父本Ak + 1 ,轉至其中 接種疫苗是為了提高適應度,免疫選擇則為了防止群體的退化.,免疫算法流程圖,免疫算法是概率1 收斂的. 算法收斂是指當算法迭代到足夠多的次數(shù)以后,群體中包含全局最佳個

20、體的概率接近于1. 這種定義即為通常所說的概率1 收斂.,免疫算法的收斂性,免疫算法的應用對象,免疫算法的應用對象主要是針對一些難度隨規(guī)模擴大而迅速增大的問題. 這類問題的特點是在規(guī)模較小時,問題一般易于求解或者說易于發(fā)現(xiàn)其局部條件下的求 解規(guī)律. 針對這一類問題選取疫苗時(可以推廣到一般問題) ,既可以根據(jù)問題的特征信息來制作免疫疫苗,也可以在具體 分析的基礎上,考慮降低原問題的規(guī)模,增設一些局部條件來簡化問題. 這種簡化后的問題求解規(guī)律就可做為選取疫苗的 一種途徑. 不過在實際的選取過程中,應考慮到:一方面,原問題局域化處理越徹底,局部條件下的求解規(guī)律就越明顯,這雖然易于獲取疫苗,但尋找所

21、有這種疫苗的計算量會顯著增加;另一方面,每一個疫苗都是利用某一局部信息來探求全局 最優(yōu)解,即估計該解在某一分量上的模式,所以沒有必要對每個疫苗做到精確無誤. 因此一般可以根據(jù)對原問題局域化處理的具體情況,選用目前通用的一些迭代優(yōu)化算法來提取疫苗.,2.2 分布式中應用,分布式系統(tǒng)作為計算機領域的研究熱點之一，近年來受到了廣泛的關注。其中的任務調度問題，對發(fā)揮系統(tǒng)的并行性能和保持負載平衡具有重大意義。任務調度問題是指根據(jù)一定的調度策略，把一組并行處理的任務按規(guī)定的時序分配到系統(tǒng)的多個處理機節(jié)點上，以期獲得較好的系統(tǒng)執(zhí)行性能。由于該問題不能在多項式時間內(nèi)求得最優(yōu)解，因而被公認為一個NP完全問題。

22、對于NP完全問題，近年來興起的遺傳算法(GA，GeneticAlgorit)是一個較好的解決方案，即在較短的時間內(nèi)能找到較好的解。因此許多研究分布式系統(tǒng)的專家開始關注遺傳算法的研究。該算法在解決大空間、非線性、全局尋優(yōu)等復雜問題時具有傳統(tǒng)方法所不具備的獨特優(yōu)勢 分布式系統(tǒng)中的任務調度問題 及遺傳算法應用研究,2.3 網(wǎng)格中應用,研究了網(wǎng)格環(huán)境下任務調度問題,提出了一個任務調度機制:基于任務圖將每一個可能的任務 調度方案表示成一個任務- 資源分配圖,將網(wǎng)格任務調度問題轉化為任務- 資源分配圖優(yōu)化選取問題提出 了一種基于免疫遺傳算法的、實現(xiàn)任務- 資源分配圖優(yōu)化選取的任務調度算法該算法將任務- 資

23、源分配圖 的最長路徑作為抗原,每一個任務- 資源分配圖對應一個抗體實驗結果表明這個算法在全局優(yōu)化能力及收 斂速度上均有顯著提高 基于免疫遺傳算法的網(wǎng)格任務調度,2.4 對等網(wǎng)絡中應用,針對用于任務調度的遺傳算法所存在的缺陷, 提出了基于免疫算法的對等網(wǎng)絡環(huán)境下的任務調度策 略。首先定義了對等網(wǎng)絡任務調度的相關問題, 然后分別構造了考慮負載均衡和種群多樣性的種群初始化算子和 克隆選擇算子, 并設計了新穎的自適應變異算子和具有先驗知識的疫苗, 同時給出了對等網(wǎng)絡節(jié)點的獲取和管理 策略。在此基礎上, 利用所提出的任務調度策略, 完成了任務調度過程。實驗結果驗證了調度策略的有效性。 基于免疫算法的對等

24、網(wǎng)絡任務調度,三、云計算中的免疫調度研究,在云計算中，帶寬需要被充分利用，盡量為存儲節(jié)點的數(shù)據(jù)資源分配本地的計算資源或鄰近需求少的計算節(jié)點。 免疫調度算法具有學習、識別、記憶和特征提供能力，該算法有利于云計算分配識別本地資源，提高帶寬利用率。 生物免疫系統(tǒng)是一個高度進化的生物系統(tǒng)，旨在區(qū)分外部有害抗原和自我組織,從而清除病原并保持有機體的穩(wěn)定。 從計算的角度來看，生物免疫系統(tǒng)是一個高度并行、分布、自適應和自組織的系統(tǒng),具有很強的學習、識別、記憶和特征提取能力。將這些特點應用到調度問題中是非常有用的,作業(yè)調度與資源分配是云計算的兩個關鍵技術，云計算的商業(yè)性使其關注對用戶的服務質量，其虛擬化技術使得資源分配和作業(yè)調度不同于以往的并行分布式計算。 擴展了Cloudsim云計算仿真平臺 ，實現(xiàn)了本文提出的任務描述和基于伯格模型的作業(yè)調度算法，對Cloudsim平臺進行了重編譯生成，并在擴展后的Cloudsim平臺上實現(xiàn)了作業(yè)調度的仿真程序，對算法進行了模擬驗證和對比分析 -云環(huán)境下作業(yè)調度算法研究與實現(xiàn),參考文獻,1 Luis M.Vaquero,Luis Rodero-Merino,Juan Caceres,et al.A break in the Clouds:Towards a