疫苗接種免疫遺傳可信QoS重路由機(jī)制.docx

1、E-mail:fcstTel:+86-10-89056056ISSN1673-9418CODENJKYTA8JournalofFrontiersofComputerScienceandTechnology1673-9418/2013/07（07）-0602-09doi:10.3778/j.issn.1673-9418.1304006疫苗接種免疫遺傳可信QoS重路由機(jī)制TheNationalNaturalScienceFoundationofChinaunderGrantNos.61070162,71071028,70931001（國(guó)家自然科學(xué)基金）;theN

2、ationalScienceFoundationforDistinguishedYoungScholarsofChinaunderGrantNo.61225012（國(guó)家杰出青年科學(xué)基金）;theSpecializedResearchFundoftheDoctoralProgramofHigherEducationofChinafbrthePriorityDevelopmentAreasunderGrantNo.20120042130003（高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金優(yōu)先發(fā)展領(lǐng)域）;theSpecializedResearchFundfbrtheDoctoralProgramofHigher

3、EducationofChinaunderGrantNos.20100042110025,20110042】10024（高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金）;theSpecializedDevelopmentFundfortheInternetofThingsfromtheMinistryofIndustryandInformationTechnologyofChina（匚信部物聯(lián)網(wǎng)發(fā)展專項(xiàng)資金）；theFundamentalResearchFundsfbrtheCentralUniversitiesofChinaunderGrantNos.N110204003,N120104001（中央高?；?/p>

4、科研業(yè)務(wù)費(fèi)專項(xiàng)資金）.Received2013-03,Accepted2013-05.CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-03,疫苗接種免疫遺傳可信QoS重路由機(jī)制TheNationalNaturalScienceFoundationofChinaunderGrantNos.61070162,71071028,70931001（國(guó)家自然科學(xué)基金）;theNationalScienceFoundationforDistinguishedYoungScholarsofChinaunderGrantNo.61225012（國(guó)家杰出青年科學(xué)基金）;theSpecializedResearchFund

5、oftheDoctoralProgramofHigherEducationofChinafbrthePriorityDevelopmentAreasunderGrantNo.20120042130003（高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金優(yōu)先發(fā)展領(lǐng)域）;theSpecializedResearchFundfbrtheDoctoralProgramofHigherEducationofChinaunderGrantNos.20100042110025,20110042】10024（高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金）;theSpecializedDevelopmentFundfortheInternet

6、ofThingsfromtheMinistryofIndustryandInformationTechnologyofChina（匚信部物聯(lián)網(wǎng)發(fā)展專項(xiàng)資金）；theFundamentalResearchFundsfbrtheCentralUniversitiesofChinaunderGrantNos.N110204003,N120104001（中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金）.Received2013-03,Accepted2013-05.CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-03,楊蕾，王興偉,，黃敏東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)110819VaccinationImmuneGeneti

7、cTrustworthyQoSReroutingScheme*YANGLei,WANGXingwei4,HUANGMinCollegeofInformationScienceandEngineering,NortheasternUniversity,Shenyang110819,China+Correspondingauthor:E-mail:wangxwYANGLei,WANGXingwei,HUANGMin.VaccinationimmunegenetictrustworthyQoSreroutingscheme.JournalofFrontiersofComputerScienceand

8、Technology,2013,7（7）：602-610.Abstract:AccordingtothecharacteristicsoftheQoS（qualityofservice）reroutingintrustworthynetwork,thispaperproposesavaccinationimmunegeneticQoSreroutingscheme.Then,thispaperpresentsthenetworkmodel,thedescriptionofusers1requirementsandthecalculationmethodsofusers*satisfaction

9、.InordertoresolvethetrustworthyproblemofQoSrouting,thispaperestablishesatrustworthyevaluationmodel.Onthisbasis,consideringtheusers'QoSrequirements,theusers'trustworthyrequirementsandthereuseoflinksontheoriginalpath,thispaperalsoproposestheQoSreroutingalgorithm.Thesimulationresultsshowthatthe

10、proposedschemehasbetterperformancethanexistingalgorithms,andcansatisfyusers'demandswiththereroutingsuccessrateandtheusersatisfactionincreased.Keywords:trustworthynetwork;QoS（qualityofservice）rerouting;vaccination;immunegenetic;trustworthyevaluation摘要:針對(duì)可信網(wǎng)絡(luò)中服務(wù)質(zhì)量QoS(qualityofservice)重路由的特點(diǎn)，提出了一種基

11、于疫苗接種免疫遺傳的QoS重路由機(jī)制。對(duì)網(wǎng)絡(luò)模型、用戶需求以及滿意度計(jì)算方法進(jìn)行了描述。為解決QoS選路的可信問(wèn)題，構(gòu)造了鏈路信任評(píng)估模型。在此基礎(chǔ)上，考慮到用戶QoS和可信需求，以及對(duì)原有路徑鏈路的復(fù)用，提出了QoS重路由算法。仿真結(jié)果表明，該機(jī)制與現(xiàn)有算法相比，具有更好的性能，在滿足用戶需求的同時(shí)，提高了重路由成功率和用戶滿意度。關(guān)鍵詞：可信網(wǎng)絡(luò);服務(wù)質(zhì)量重路由；疫苗接種;免疫遺傳;信任評(píng)估文獻(xiàn)標(biāo)志碼:A中圖分類號(hào):TP3931引言隨著網(wǎng)絡(luò)規(guī)模的持續(xù)擴(kuò)大和新業(yè)務(wù)的不斷增長(zhǎng)，互聯(lián)網(wǎng)正面臨著安全性、動(dòng)態(tài)性和異構(gòu)性等多方面的挑戰(zhàn)。新業(yè)務(wù)的不斷涌現(xiàn)使得人們對(duì)網(wǎng)絡(luò)的服務(wù)質(zhì)量(qualityofser

12、vice,QoS)提出了更高的要求。同時(shí)，大屋的網(wǎng)絡(luò)安全問(wèn)題導(dǎo)致人們對(duì)現(xiàn)有網(wǎng)絡(luò)的不信任。在這種情況下，提出了可信網(wǎng)絡(luò)的概念。網(wǎng)絡(luò)的可信性是指網(wǎng)絡(luò)和用戶的行為及其結(jié)果總是可預(yù)期與可管理的,能夠做到行為狀態(tài)訶監(jiān)測(cè)，行為結(jié)果可評(píng)估，異常行為可管理網(wǎng)?？尚啪W(wǎng)絡(luò)的研究主要包括服務(wù)提供者的可信、網(wǎng)絡(luò)信息傳輸?shù)目尚藕陀脩艚K端的可信。用戶移動(dòng)、網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路故障等原因可能導(dǎo)致原有路由失效，需要進(jìn)行重路由?？尚臦oS重路由必須滿足一系列約束條件，而含有兩個(gè)或兩個(gè)以上加性或乘性參數(shù)的重路由間題已被證明是NP難問(wèn)題氣需使用啟發(fā)式或智能優(yōu)化方法來(lái)解決。文獻(xiàn)5提出了一種連接層的主動(dòng)重路由算法，以最小化網(wǎng)絡(luò)阻塞率為目標(biāo)，

13、在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間重路由已存在的路徑連接以獲得重路由路徑。該算法用較低的網(wǎng)絡(luò)開(kāi)銷提高了重路由成功率。文獻(xiàn)6提出了-種QoS重路由策略，為優(yōu)先級(jí)別高的即時(shí)請(qǐng)求評(píng)估未來(lái)資源的占用情況,確定可能的候選連接,并啟動(dòng)重路由過(guò)程實(shí)現(xiàn)這些連接。該策略提高了重路由成功率，但要預(yù)約大量的網(wǎng)絡(luò)資源。為了減輕波K連續(xù)性約束對(duì)網(wǎng)絡(luò)阻塞性能的影響，文獻(xiàn)7給出了基于波長(zhǎng)再分配與路徑偏離的重路由算法。該算法能夠利用較少的波長(zhǎng)提高網(wǎng)絡(luò)的阻塞性能，但并沒(méi)有考慮用戶對(duì)路徑的QoS需求和可信需求。文獻(xiàn)8設(shè)計(jì)了一種基于最短路徑樹(shù)搜索策略的重路由機(jī)制。以用戶延遲請(qǐng)求為約束條件，路徑端到端延遲抖動(dòng)最小為優(yōu)化目標(biāo)，執(zhí)行Bellman-

14、Ford算法為每個(gè)節(jié)點(diǎn)生成最短路徑樹(shù)。根據(jù)故障情況對(duì)最短路徑樹(shù)進(jìn)行“偏轉(zhuǎn)”，從而找到重路由路徑。然而，該機(jī)制只考慮了部分QoS參數(shù),導(dǎo)致其重路由成功率和用戶滿意度較低。文獻(xiàn)4提出了一種能夠減少網(wǎng)絡(luò)開(kāi)銷的混合重路由策略，其綜合了幾種恢復(fù)策略,包括路徑多樣性、限制性恢復(fù)和全局重路由策略。該策略需要每個(gè)路由節(jié)點(diǎn)保存大量的連接信息，其可擴(kuò)展性較差。文獻(xiàn)9提出了一種基于鏈路生存時(shí)間概率的傳輸控制協(xié)議。該協(xié)議跨層結(jié)合鏈路穩(wěn)定性路由.通過(guò)收集路由層鏈路生存時(shí)間的概率信息實(shí)現(xiàn)對(duì)端到端連接穩(wěn)定性的認(rèn)知，具有對(duì)由于移動(dòng)造成的路由中斷進(jìn)行提前預(yù)判和有效處理的能力，但沒(méi)有提供用戶QoS支持。文獻(xiàn)10提出了一種快速重路

15、由的增強(qiáng)保護(hù)圈e-cycle(enhancedprotectioncycle)算法,通過(guò)使用不同的標(biāo)識(shí)符區(qū)分虛擬圈，保證了路由保護(hù)的有效性和網(wǎng)絡(luò)部署的擴(kuò)展性。文獻(xiàn)11提出了一種針對(duì)關(guān)鍵流的重路由算法LCBA(length-constrainedmostbalancedalgorithm)，在滿足關(guān)鍵流路徑長(zhǎng)度要求的前提下提高網(wǎng)絡(luò)的最大帶寬利用率。該算法適合處理網(wǎng)絡(luò)中單個(gè)位置發(fā)生擁塞的情況，但不能很好地解決多故障問(wèn)題。綜上所述，現(xiàn)有的重路由算法均存在一些問(wèn)題：重路由路徑有可能大大偏離最優(yōu)化路徑；網(wǎng)絡(luò)資源利用率低；大部分重路由算法沒(méi)有考慮應(yīng)用對(duì)QoS參數(shù)和路徑可信的需求。本文重點(diǎn)考慮了這幾個(gè)方面，

16、提出了既能夠?yàn)橛脩籼峁㏎oS保證和可信需求，又能夠合理利用網(wǎng)絡(luò)資源的重路由策略。2問(wèn)題描述2.1網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型表示為圖G（匕/是節(jié)點(diǎn)集，代表網(wǎng)絡(luò)中的路由節(jié)點(diǎn)；E是邊集，代表實(shí)際網(wǎng)絡(luò)的通信鏈路。為了簡(jiǎn)單起見(jiàn)，本文把節(jié)點(diǎn)的延遲、延遲抖動(dòng)、出錯(cuò)率歸并到邊上。這樣，V*V（i=l,2,，|玲,考慮如下參數(shù)：資源占用率金、穩(wěn)定度sf;（/=1,2,，劇，考慮如F參數(shù)：總帶寬必叭可用帶寬bw、延遲冰、延遲抖動(dòng)力、出錯(cuò)率/s、信任值roc=max(ucpusmtcpu'tmem其中，沖為節(jié)點(diǎn)當(dāng)前使用的CPU周期數(shù)；tcpu為節(jié)點(diǎn)CPU周期總數(shù)；umem為節(jié)點(diǎn)當(dāng)前使用的內(nèi)存數(shù)量；伽e/n為節(jié)點(diǎn)內(nèi)存總

17、量。根據(jù)節(jié)點(diǎn)當(dāng)前的資源占用率，節(jié)點(diǎn)穩(wěn)定度st的計(jì)算如下：1，七%51+。（尸8-，）°ocrH其中，尸l、，h分別表示節(jié)點(diǎn)在低和高負(fù)載時(shí)的資源占用率閾值；。、為調(diào)節(jié)因子。顯然，節(jié)點(diǎn)當(dāng)前資源占用率越高，節(jié)點(diǎn)運(yùn)行的穩(wěn)定度越差。如果擊點(diǎn)的穩(wěn)定度ststL（stL為節(jié)點(diǎn)穩(wěn)定度閾值），說(shuō)明節(jié)點(diǎn)當(dāng)前已經(jīng)超負(fù)荷運(yùn)行，則不再考慮對(duì)其進(jìn)行信任評(píng)估及QoS重路由。2.2鏈路信任評(píng)估解決QoS重路由的可信問(wèn)題，首先需要解決網(wǎng)絡(luò)中鏈路的信任問(wèn)題。鏈路的可靠性為重路由機(jī)制找到端到端的可信路徑提供保證，而計(jì)算鏈路的信任值叮以轉(zhuǎn)化為計(jì)算該鏈路節(jié)點(diǎn)對(duì)之間的信任值。本文基于貝葉斯推理（設(shè)計(jì)了一套完整的評(píng)估模型,該模型

18、根據(jù)節(jié)點(diǎn)間的歷史交互信息，動(dòng)態(tài)計(jì)算節(jié)點(diǎn)間的信任值。根據(jù)網(wǎng)絡(luò)中的惡意行為對(duì)網(wǎng)絡(luò)信任程度的影響，將節(jié)點(diǎn)信任危機(jī)分為四個(gè)等級(jí)。輕微危機(jī):包括網(wǎng)絡(luò)元素（節(jié)點(diǎn)或鏈路）故障而引起的業(yè)務(wù)中斷行為，資源不足導(dǎo)致的網(wǎng)絡(luò)阻塞或節(jié)點(diǎn)休眠引起的改道行為。中度危機(jī):包括無(wú)理由中斷業(yè)務(wù)，竊聽(tīng)數(shù)據(jù)包信息及進(jìn)行路由欺詐等惡意行為。嚴(yán)重危機(jī):包括會(huì)話劫持,對(duì)數(shù)據(jù)包信息進(jìn)行箓改和偽造等行為。致命危機(jī):包括傳播木馬病毒,DoS攻擊等可能導(dǎo)致節(jié)點(diǎn)或網(wǎng)絡(luò)癱瘓等惡意行為。（1）直接信任值的計(jì)算若在周期i內(nèi)節(jié)點(diǎn)A與B有N次交互行為，節(jié)點(diǎn)A記錄與節(jié)點(diǎn)B交互行為的正面評(píng)價(jià)次數(shù)為負(fù)面評(píng)價(jià)次數(shù)為氣。其中輕微危機(jī)、中度危機(jī)、嚴(yán)重危機(jī)行為導(dǎo)致的負(fù)面評(píng)

19、價(jià)次數(shù)分別為、七、七，如果節(jié)點(diǎn)出現(xiàn)一次致命危機(jī)行為，則宜接將該節(jié)點(diǎn)關(guān)閉整頓。對(duì)不同的信任危機(jī)行為等級(jí)進(jìn)行不同程度的“懲罰”，“懲罰”后的負(fù)面評(píng)價(jià)次數(shù)為：其中，化l（i=1,2,3）為懲罰因子，且們v約v%。由式（3）可知，信任危機(jī)行為越惡劣,懲罰尺度越大°節(jié)點(diǎn)A對(duì)B的期望信任值計(jì)算如下：TVyxp=-_皿（4）2+為虹胃邛F；）其中，崗、月為時(shí)間消逝因子，且081瞄1。七表示當(dāng)前的時(shí)間周期表示第，個(gè)時(shí)間周期，N表示周期數(shù)。S和F/分別為第，個(gè)周期內(nèi)A記錄B在交互過(guò)程中的正面評(píng)價(jià)次數(shù)和經(jīng)過(guò)“懲罰”后的負(fù)面評(píng)價(jià)次數(shù)?？尚哦染哂袃蓚€(gè)更要屬性：交互過(guò)程中正面評(píng)價(jià)和負(fù)面評(píng)價(jià)次數(shù)總和越大，不確定

20、的評(píng)價(jià)次數(shù)越少，可信度越大；正面評(píng)價(jià)和負(fù)面評(píng)價(jià)次數(shù)差值越大，信任的不確定性越低,可信度越大?？尚哦萩的定義如下：c=1一(s&+ny(s&+A+D其中，0cWl,c越接近于1,說(shuō)明式（4）計(jì)算的期望信任值越可信;相反，c值越接近于0,說(shuō)明計(jì)算的期望信任值越不可信。slL虹&為衰減后的正面評(píng)價(jià)次數(shù),F&=fjF：為衰減后的負(fù)面評(píng)價(jià)次數(shù)。1-1直接信任值由期望信任值和可信度共同決定，其計(jì)算公式如下：其中，是期望信任值與可信度之間相對(duì)重要程度的調(diào)節(jié)因子。由式(6)可以看出，直接信任值隨著期望信任值與可信度的增大而增大。(2) 間接信任值的計(jì)算當(dāng)可信度C<CL(C

21、L為可信度闕值)時(shí)，說(shuō)明節(jié)點(diǎn)缺乏待評(píng)估節(jié)點(diǎn)的行為記錄，需要其他節(jié)點(diǎn)信任推薦，為此引入了間接信任值網(wǎng)。本文只考慮鄰居節(jié)點(diǎn)對(duì)評(píng)估節(jié)點(diǎn)的推薦信任。為防止詆毀或者過(guò)度評(píng)價(jià)現(xiàn)象的發(fā)生，對(duì)各個(gè)推薦信任值進(jìn)行背離度測(cè)試RC-test(recommender'stest),以驗(yàn)證推薦信任的實(shí)用性，計(jì)算公式如下：叱b-心心(7)其中，為背離度門(mén)限，0<<1。TTg為某個(gè)鄰居節(jié)點(diǎn)對(duì)B的推薦信任值，推薦信任值的計(jì)算方法同直接信任值。假設(shè)通過(guò)RC-test的推薦信任值有m個(gè),則間接信任值計(jì)算公式如下：吧=瑟"(3) 綜合信任值的計(jì)算節(jié)點(diǎn)A對(duì)節(jié)點(diǎn)B的綜合信任值是對(duì)其直接信任值與間接信任值進(jìn)

22、行計(jì)算得到的，計(jì)算公式如下：其中，。為直接信任權(quán)重，一般有a>0.5o節(jié)點(diǎn)A對(duì)B的綜合信任值可以看成連接節(jié)點(diǎn)A和節(jié)點(diǎn)B鏈路的信任值，即將信任值歸結(jié)到邊上形成的一種“特殊”的QoS參數(shù)。2.3用戶需求與滿意度2.3.1用戶需求描述當(dāng)重路由條件觸發(fā)時(shí)，用戶可信QoS重路由請(qǐng)求為RReqgvd,APpTLJD)O其中，七,均w匕vs表示源節(jié)點(diǎn)，vd表示目的節(jié)點(diǎn)。4己表示用戶請(qǐng)求的第i種應(yīng)用類型。bw_r1bw_rdl_rlL,冰_尸山,L/V；'jVh和«_，分別表示第，種應(yīng)用類型的帶寬、延遲、延遲抖動(dòng)和出錯(cuò)率需求區(qū)間。TL表示用戶請(qǐng)求的網(wǎng)絡(luò)鏈路信任等級(jí)，不同的信任等級(jí)對(duì)應(yīng)不

23、同的信任值區(qū)間rv_rL,tv_rH,如表1所示。力表示會(huì)話編號(hào)，用來(lái)保證重路由請(qǐng)求的唯一性，各節(jié)點(diǎn)會(huì)根據(jù)刀號(hào)來(lái)判斷是否為其發(fā)起重路由。Table1Usertrustrequirementgrade表1用戶信任需求等級(jí)信任等級(jí)信任需求說(shuō)明信任值區(qū)間第一級(jí)高度可信(0.8,1.0第二級(jí)非?？尚?0.6,0.8第三級(jí)-般可信(0.3,0.6第四級(jí)輕微可信(0,0.3第五級(jí)無(wú)信任需求0,1.02.3.2滴意度函數(shù)(1) 帶寬滿意度函數(shù)當(dāng)實(shí)際路徑提供的帶寬為時(shí),用戶的帶寬滿意度函數(shù)示意圖如圖1所示,其定義如下：(10)城+2E.=二bw-，w-r'n人*_,；I，0,8%<bw_r=Zn

24、v_*1 i.(11)+2SlnEf機(jī)刀v虬其中3是一個(gè)非常小的正數(shù)。圖1帶寬潛意度函數(shù)示意圖(2) 延遲滿意度函數(shù)當(dāng)實(shí)際路徑提供的延退為dlp時(shí),用戶的延遲滿意度函數(shù)示意圖如圖2所示,其定義如下：=dl*(13)(12)Fig.2Thediagramofdelaysatisfactiondegree圖2延遲漪意度函數(shù)示意圖(3) 延遲抖動(dòng)滿意度函數(shù)當(dāng)實(shí)際路徑提供的延遲抖動(dòng)為加時(shí)，用戶的延遲抖動(dòng)滿意度函數(shù)示意圖與圖2類似,其定義如下：(14)SW，p)=SW，p)=(15)0,人兀4E'jtp=jM*-|sin以JVhl，jtp；Vh(4) 出錯(cuò)率滿意度函數(shù)當(dāng)實(shí)際路徑提供的出錯(cuò)率為給時(shí)

25、，用戶的出錯(cuò)率滿意度函數(shù)示意圖與圖2類似,其定義如下：5+2(16)E.=工-/s-，y官I(mǎi)ls_r'L<Is<ls_r'H(5) 信任值滿意度函數(shù)當(dāng)實(shí)際路徑提供的信任值為rvp(取路徑所經(jīng)過(guò)就路綜合信任值的最小值)時(shí),用戶的信任值滿意度(18)(18)Sat(tvp)=-函數(shù)示意圖與圖1類似,其定義如下：.rv9Zv_r一tv_r'LVp20,/vprv_®=心：1 1(19)+2S,nE%，Dptv_r由式(10)式(19)可以看出，當(dāng)用戶帶寬、延遲、延遲抖動(dòng)、出錯(cuò)率和信任值在接近各自的需求值上限和下限位置時(shí),相應(yīng)的用戶滿意度變化比較緩慢,在中

26、間值部分變化明顯，這種變化符合人的正常心理。如圖1所示，用戶獲得的帶寬和信任值越大，相應(yīng)的滿意度越大。如圖2所示，用戶獲得的延遲、延遲抖動(dòng)和出錯(cuò)率越小，相應(yīng)的滿意度越大。2.3.3滿意度計(jì)算定義用戶QoS滿意度Qsat與綜合滿意度/sm如下:Qsat=w,Sat(bw)+wdlSat(dl)+wjtSat(jt)+wSatUs)(20)Isat=pQsat+(!-p)Sat(tv)(21)其中，印機(jī)、心、小和叫,分別表示帶寬、延遲、延退抖動(dòng)和出錯(cuò)率在QoS滿意度中的權(quán)重，且取值均介于0和1之間,其和為1。p為Q。S滿意度權(quán)重，取值介于0和1之間，一般大于0.5,即QoS滿意度權(quán)重要大,這是因?yàn)?/p>

27、如果用戶QoS需求都無(wú)法滿足，路徑可信便失去了意義。2.4數(shù)學(xué)模型QsatTmaxQsat(22)IsatmaxIsat(23)s.t.(24)Zd/d頃(25)£jhk(26)虹P«ii-n(fgw(27)本文QoS重路由機(jī)制的設(shè)計(jì)目標(biāo)是：在滿足用戶QoS約束的情況下，最大化用戶QoS滿意度Qsat和用戶綜合滿意度Isat，描述如下：其中，i表示用戶請(qǐng)求的應(yīng)用類型；表示從源節(jié)點(diǎn)v$到目的節(jié)點(diǎn)vd的路徑；bwlk、dllk、力快和人獨(dú)分別表示鏈路么上的帶寬、延退、延退抖動(dòng)及出錯(cuò)率。3算法設(shè)計(jì)智能優(yōu)化算法已經(jīng)成功應(yīng)用于很多工程領(lǐng)域中NP類問(wèn)題的求解*氣本文采用基于疫苗接種的免

28、疫遺傳算法啊尋找滿足2.4節(jié)所述目標(biāo)的優(yōu)化的重路由路徑?；谝呙缃臃N的免疫遺傳算法是一種利用免疫系統(tǒng)的機(jī)理改進(jìn)遺傳算法的智能優(yōu)化算法。該算法通過(guò)免疫接種來(lái)抑制優(yōu)化過(guò)程中出現(xiàn)的退化現(xiàn)象,在保持種群多樣性的同時(shí)，防止算法陷入局部最優(yōu)。3.1解的表達(dá)、生成和適依購(gòu)數(shù)文中每條染色體代表一條解路徑(即解向量:)，每個(gè)基因位對(duì)應(yīng)解向仙中的一個(gè)元素(即節(jié)點(diǎn)編號(hào))。當(dāng)重路由條件觸發(fā)時(shí)，在當(dāng)前失效節(jié)點(diǎn)或鏈路的前一個(gè)節(jié)點(diǎn)隨機(jī)找到一條到目的節(jié)點(diǎn)Vd的端到端QoS路徑，與原有路徑進(jìn)行拼接,若重路由路徑出現(xiàn)環(huán)路則去環(huán)。如果形成的七到*的路徑滿足用戶QoS需求，則隨機(jī)選出的路徑可以作為初始解，否則需重新生成初始解。解的適

29、應(yīng)值定義如下：fitness(x)=/sat(28)Jitness(x)=Qsat(29)其中，式(28)和式(29)分別表示用戶對(duì)路徑有信任需求和無(wú)信任需求時(shí)的適應(yīng)值函數(shù)?？梢钥闯?，用戶滿意度越大，適應(yīng)值越大，解越優(yōu)。3.2免疫遺傳算十(1) 選擇算子這里采用精英解保留和輪盤(pán)賭選擇策略相結(jié)合的選擇方式，從父代中選取適應(yīng)值最大的個(gè)體作為精英解宜接進(jìn)入卜一代，其余個(gè)體按照輪盤(pán)賂策略進(jìn)行選擇，第，個(gè)個(gè)體被選擇的概率P,為：p"5)(30)其中，N為種群規(guī)模；川esM)為個(gè)體，的適應(yīng)值。從種群中選取M(MWN)個(gè)個(gè)體作為交叉?zhèn)€體進(jìn)行交叉操作。(2) 交叉算子采用改進(jìn)的單點(diǎn)交叉,在兩條染色體

30、中選取除源、目的節(jié)點(diǎn)外的公共節(jié)點(diǎn)，組成備選交叉節(jié)點(diǎn)集合。從源節(jié)點(diǎn)到交叉節(jié)點(diǎn)的節(jié)點(diǎn)編號(hào)序列不變，將交叉點(diǎn)與目的節(jié)點(diǎn)間的節(jié)點(diǎn)編號(hào)序列交換，從而產(chǎn)生兩個(gè)新個(gè)體。如果備選交叉節(jié)點(diǎn)集合為空，則不進(jìn)行交叉操作;否則，從備選交叉節(jié)點(diǎn)集合中隨機(jī)選擇一個(gè)交叉點(diǎn)。簡(jiǎn)單示意如圖3所示,交叉操作的具體步驟如下。假設(shè)交叉?zhèn)€體對(duì)應(yīng)的路徑分別為&和。步馨1將路徑與&共同經(jīng)過(guò)的節(jié)點(diǎn)編號(hào)(源節(jié)點(diǎn)和目的節(jié)點(diǎn)除外),放進(jìn)備選交叉節(jié)點(diǎn)集合。步驟2從備選交叉節(jié)點(diǎn)集合中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為交叉操作的交叉節(jié)點(diǎn)。步驟3將&和犬2位于交叉節(jié)點(diǎn)后的子路徑進(jìn)行交換，得到新路徑川和心。Fig.3Crossoverpositi

31、on圖3交義位置(3) 變異算子變異算子提供初始種群中不含有的基因，保證進(jìn)化過(guò)程中種群的多樣性。相應(yīng)的操作為:從路徑中隨機(jī)選擇兩個(gè)不同的節(jié)點(diǎn)，并按深度優(yōu)先策略隨機(jī)選出連接這兩個(gè)節(jié)點(diǎn)的路徑片段，若該路徑片段滿足QoS需求,替換原始片段構(gòu)成新路徑。如果交叉與變異算子在路徑操作過(guò)程中出現(xiàn)環(huán)路，則去環(huán)。(4) 疫苗提取與接種在交叉操作后計(jì)算每個(gè)個(gè)體的適應(yīng)值,并選取適應(yīng)值最大的個(gè)體,將其全部基因位作為疫苗。接種操作與交叉操作類似，只是疫苗全部基因位不進(jìn)行變動(dòng)。具體接種操作為:在接種個(gè)體與疫苗中選擇公共交叉點(diǎn)（兩個(gè)或多個(gè)），進(jìn)行路徑片段的交換，然后將多個(gè)交換后的片段拼接成一條新染色體。接種后的個(gè)體含有疫苗

32、良好的基因片段，可以加快算法的收斂速度。3.3算法流程基于疫苗接種免疫遺傳的QoS重路由機(jī)制的具體流程如下：步馨1初始化算法各參數(shù)，即交叉概率乙，變異概率Pm，種群規(guī)模N,最大進(jìn)化代數(shù)當(dāng)前迭代次數(shù)，=0,遺傳操作選擇的個(gè)體數(shù)檢查算法是否陷入局部最優(yōu)的閾值£。步驛2在原始路徑中，以失效節(jié)點(diǎn)或鏈路的前一節(jié)點(diǎn)vp作為源節(jié)點(diǎn)，隨機(jī)生成N個(gè)初始解，形成初始種群X（t計(jì)算每個(gè)個(gè)體的適應(yīng)值。步驟3對(duì)X"）進(jìn)行選擇操作，保留最佳個(gè)體，并選出M個(gè)個(gè)體形成種群X,（0。步算4對(duì)種群4（f）中M個(gè)個(gè)體按交叉概率R進(jìn)行交叉操作，形成種群X2（t）O步驟5計(jì)算種群擊）中各個(gè)體的適應(yīng)值，提取疫苗匕將其

33、余個(gè)體按變異概率Pm執(zhí)行變異操作，形成種群%3（0o步驟6計(jì)算X.（t）中各個(gè)體的適應(yīng)值Fg與當(dāng)前種群的平均適應(yīng)值F（X）>并計(jì)算均值偏差|F（x,）-FX）。=1,2，,M）,當(dāng)種群中3/4個(gè)體滿足|F（x,）-7X）<£時(shí),認(rèn)為算法可能陷入局部最優(yōu),則轉(zhuǎn)到步驟7;否則，轉(zhuǎn)到步驟8。步驟7對(duì)種群又3（。中一定數(shù)量M=0M（OvKl）的個(gè)體進(jìn)行疫苗接種操作。步驊8將M個(gè)個(gè)體按適應(yīng)值由大到小排序，并選出A/-1個(gè)適應(yīng)值最大的個(gè)體與X（t）中保留的最佳個(gè)體形成新種群X0+1）。步驟9若進(jìn)化代數(shù)達(dá)到，則新種群中最優(yōu)解作為端到端QoS路徑,轉(zhuǎn)步驟10;否則f=f+l,轉(zhuǎn)步驟2。步

34、魏10將求解的QoS路徑與原有路徑片段拼接并去環(huán)，得到最終重路由路徑。4仿真實(shí)現(xiàn)與性能評(píng)價(jià)基于MicrosoftVisualStudio,對(duì)本文提出的重路由機(jī)制（簡(jiǎn)稱機(jī)制A）進(jìn)行了仿真實(shí)現(xiàn).并與文獻(xiàn)8中的偏轉(zhuǎn)重路由算法（簡(jiǎn)稱機(jī)制B）進(jìn)行了對(duì)比分析。為了更好地模擬網(wǎng)絡(luò)流量.在表2中設(shè)置了5種流量等級(jí)。在等級(jí)1下，網(wǎng)絡(luò)提供原始QoS信息，這里用單位1表示，其他等級(jí)參數(shù)均為等級(jí)1的相對(duì)值。算法中相關(guān)參數(shù)的具體取值見(jiàn)表3。Table2Networktrafficlevelsetting表2流域等級(jí)設(shè)定流雖等級(jí)帶寬延遲延遲抖動(dòng)出錯(cuò)率11.001.001.001.0020.801.051.051.0130

35、.60240.40301.04Table3ParametersettingJU參數(shù)設(shè)置參數(shù)參數(shù)含義取值P,交叉概率0.80P.變異概率0.30N種群規(guī)模10Gm域大進(jìn)化代數(shù)20M遺傳操作個(gè)體數(shù)10£局部最優(yōu)閡值0.05fi疫苗接種個(gè)體比例0.30表4和表5分別是重路由成功率和用戶滿意度在中國(guó)教育和科研計(jì)算機(jī)網(wǎng)CERNET（拓?fù)?）、第二代中國(guó)教育和科研計(jì)算機(jī)網(wǎng)CERNET2（拓?fù)?）、美國(guó)下一代互聯(lián)網(wǎng)INTERNET2C拓?fù)?）和歐洲下一代互聯(lián)網(wǎng)GcANT2（拓?fù)?）上的性能比較結(jié)果。Table4Thecompari

36、sonofreroutingsuccessrate（A:B）表4取路由成功率比較（A：B）拓?fù)涞燃?jí)1等級(jí)2等級(jí)3等級(jí)；等級(jí)5拓?fù)?0.99:0.960.98：0.890.95：0.790.90：0.590.83：0.54拓?fù)?0.98：0.960.97:0.880.93：0.760.84：0.580.77：0.51拓?fù)?0.98:0.950.93：0.860.89：0.740.8H0.570.72：0.52拓?fù)?0.99：0.970.99：0.910.96：0.810.91：0.640.87：0.56Table5Thecomparisonofusersatisfactiondegree（A：B

37、）表5用戶滴意度比較（A：B）拓?fù)涞燃?jí)I等級(jí)i岑級(jí)3等級(jí)4等級(jí)廠拓?fù)洹?.96：0.890.95：0.850.90：0.760.86：0.580.80：0.50拓?fù)?0.96：0.870.94：0.820.88：0.720.84：0.620.81：0.53拓?fù)?0.97=0.900.93:0.860.89:0.760.83：0.620.79：0.54拓?fù)?0.92：0.840.89：0.780.83：0.670.79：0.550.73：0.48由表4可以看出.隨著網(wǎng)絡(luò)流量級(jí)別的增大,A、B兩種機(jī)制的更路由成功率都在下降,并旦機(jī)制A下降較緩慢。這是因?yàn)榫W(wǎng)絡(luò)資源的減少，會(huì)導(dǎo)致重路由所選路徑無(wú)法滿足

38、用戶QoS需求而造成重路由失敗。機(jī)制A考慮了部分路徑端到端的QoS保證，并與原有可信QoS路徑片段拼接，所選路徑很容易滿足用戶需求，從而使機(jī)制A重路由成功率較高。機(jī)制B沒(méi)有考慮部分路徑是否可信，所選路徑很難滿足用戶的QoS需求，導(dǎo)致其童路由成功率較低。由表5可以看出，兩種重路由機(jī)制的用戶滿意度都隨著網(wǎng)絡(luò)流量級(jí)別的增大而下降°在網(wǎng)絡(luò)流最較小,資源較充足時(shí)，兩種重路由機(jī)制都能夠找到用戶滿意度較高的重路由路徑。而當(dāng)網(wǎng)絡(luò)流量增大時(shí)，機(jī)制B的滿意度比機(jī)制A下降明顯。這是因?yàn)闄C(jī)制A在選擇路徑片段時(shí)對(duì)QoS參數(shù)進(jìn)行了限制,使整體路徑提供的QoS參數(shù)較優(yōu),而機(jī)制B在路徑選擇時(shí)只考慮了延退和延退抖動(dòng)參

39、數(shù)，并沒(méi)有考慮其他QoS參數(shù)與用戶對(duì)路徑的可信需求。5結(jié)語(yǔ)本文設(shè)計(jì)了基于疫苗接種免疫遺傳的可信QoS重路由'機(jī)制，該機(jī)制綜合考慮了鏈路可信度和用戶QoS需求等因素。仿真結(jié)果表明，本文機(jī)制同現(xiàn)有算法相比，在用戶滿意度和重路由成功率上具有一定的優(yōu)勢(shì)。然而，由于本文機(jī)制考慮所有QoS參數(shù)，并在路徑尋優(yōu)過(guò)程中進(jìn)行了復(fù)雜的整合運(yùn)算，具有較高的時(shí)間復(fù)雜度，如何進(jìn)一步提高算法的執(zhí)行效率，以及更好地均衡重路由各項(xiàng)性能指標(biāo)是今后的研究重點(diǎn)CReferences:1 WangXingwci,QinPeiyu,HuangMin.ABCsupportingQoSunicastroutingschemebase

40、dontheartificialfishswarmJ.ChineseJournalofComputers,2010,33(4):718-725.2 LinChuang,WangYuanzhuo,TianLiqin.DevelopmentoftrustworthynetworkandfacingscientificchallcngesJ.ZTECommunications,2008,14(1):13-16.3 AbMananJ-I,KhattakZA,SulaimanS.Practicableunifiedsecurity,trustandprivacy(STP)frameworkforfede

41、ratedaccessmanagement(FAM)C/Proceedingsofthe2012IEEE11thInternationalConferenceonTrust,SecurityandPrivacyinComputingandCommunications(TrustCom'12),Liverpool,2012.Washington,DC,USA:IEEEComputerSociety,2012:1411-1416.4 BashllariA,FundoA,NaceD,etal.AnoteonahybridreroutingschemeCJ/Proceedingsofthe20

42、113rdInternationalCongressonUltraModemTelecommunicationsandControlSystemsandWorkshops(ICUMT'll),Budapest,2011:1-5.5 WangShengwei,ChenYichiu.Trafficpatternbasedconnectionlevelactivereroutingalgorithminall-opticalWDMnet-worksC/Proceedingsofthe201218thAsia-PacificConferenceonCommunications(APCC'

43、;12),JejuIsland,2012:355-360.6 AhmadI,KamruzzamanJ,HabibiD.ReroutinginadvancefbrpreemptedIRcallsinQoS-enablednetworks!J.ComputerCommunications,2008,31(17):3922-3928.7 FawazWEEnhancementofblockingperformanceinall-opticalWDMnetworksviawavelengthreassignmentandroutedcviationJ.ComputerCommunications,201

44、2,35(8):929-935.8 LiXin,QinZhen,YuTao.OptimizingtheQoSperformanceoffastreroutingC/Procccdingsofthe20099thInternationalConferenceonHybridIntelligentSystems(HIS*09),Shenyang,China,2009.Washington,DC,USA:IEEEComputerSociety,2009:313-318.9 SunJie,GuoWei.Crosslayertransmissioncontrolprotocolinteractingwi

45、thlinkreliableroutinginMANETJ.JournalofSoftware,2011,22(5):1041-1052.10 LiQi,XuMingwei,WuJianping,etal.AunifiedapproachtoroutingprotectioninIPnetworksfJ.IEEETransactionsonNetworkandServiceManagement,2012,9(3):306-319.11 PeiYujie,WangHongbo,ChengShirui.Delay-guaranteedkeyflowroutingadjustmentalgorithmJ.JournalofSoftware,2010,21(3):528-538.12 ZouridakiC,MarkBL,HejmoM,etal.E-Hermes:arobustcooperativetrustestablishmentschemefbrmobileAdHocnetworksJ.AdHocNetworks,2009,7(6):1156-1168.13 LuoJunhai,LiuXue,FanMingyu.Atrustmodelbasedonfuzzyrecommendatio