師雪霖，徐恪

計(jì)算機(jī)科學(xué)技術(shù)

云虛擬機(jī)資源分配的效用最大化模型

師雪霖，徐恪

隨著云計(jì)算和虛擬化技術(shù)的發(fā)展，為云資源管理提供了一種更高層次的調(diào)度選擇：一個(gè)作業(yè)不再只能分配到一臺(tái)物理機(jī)上，而是可將一臺(tái)或多臺(tái)物理機(jī)的計(jì)算資源虛擬化成一臺(tái)虛擬機(jī)來(lái)運(yùn)行該作業(yè)。根據(jù)作業(yè)需要，高效分配定量的物理資源放置虛擬機(jī)，是決定云系統(tǒng)性能的關(guān)鍵因素，即云資源調(diào)度問(wèn)題實(shí)質(zhì)就是一個(gè)虛擬機(jī)和物理機(jī)之間的映射問(wèn)題。文中借鑒網(wǎng)絡(luò)效用最大化模型，提出了一種云資源調(diào)度模型——云效用最大化（Cloud Utility Maximization，XUM）模型，與傳統(tǒng)調(diào)度模型相比，目標(biāo)函數(shù)不再是最小化最大完工時(shí)間，而是以達(dá)到效用最大為調(diào)度目標(biāo)，可以充分提高用戶的滿意程度。通過(guò)求解CUM優(yōu)化問(wèn)題得到最優(yōu)的虛擬機(jī)和物理機(jī)映射關(guān)系。設(shè)計(jì)了針對(duì)該模型的分解優(yōu)化算法——簡(jiǎn)化次梯度算法求解拉格朗日對(duì)偶問(wèn)題，證明了該算法可以獲得原始模型問(wèn)題的最優(yōu)解。仿真實(shí)驗(yàn)表明算法可行且具有良好的收斂特性，并給出了CUM模型在真實(shí)云環(huán)境下的應(yīng)用場(chǎng)景。在云環(huán)境中，不僅資源的地理位置分布廣泛，甚至屬于不同的自治系統(tǒng)，而且資源往往具有異構(gòu)性、動(dòng)態(tài)性，如何有效分配計(jì)算資源是決定整個(gè)云性能、效率的關(guān)鍵問(wèn)題。因此，隨著云計(jì)算技術(shù)的日益普及，有效的云資源調(diào)度模型和算法將成為高效利用這些資源的關(guān)鍵。由于云計(jì)算模式從提出伊始即考慮到其商業(yè)實(shí)現(xiàn)，所以從經(jīng)濟(jì)效用度量的調(diào)度模型更具意義。本文提出的云資源CUM調(diào)度模型，和以往0-1整數(shù)規(guī)劃的調(diào)度方法不同，利用計(jì)算機(jī)網(wǎng)絡(luò)中NUM模型思路，實(shí)現(xiàn)了對(duì)物理機(jī)計(jì)算資源的更高層次分配：以效用最大為調(diào)度目標(biāo)，一臺(tái)或多臺(tái)物理機(jī)資源如同網(wǎng)絡(luò)鏈路的帶寬一樣，通過(guò)虛擬化技術(shù)分配給一個(gè)或多個(gè)作業(yè)。此外給出了該模型的優(yōu)化算法，通過(guò)簡(jiǎn)化的次梯度算法求解該模型的拉格朗日對(duì)偶問(wèn)題。通過(guò)模擬實(shí)驗(yàn)表明，算法具有可行性和260計(jì)算機(jī)學(xué)報(bào)2013年較好的收斂性。

來(lái)源出版物：計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 252-262

入選年份：2014

基于云模型的信任評(píng)估方法研究

張仕斌，許春香

摘要：復(fù)雜的網(wǎng)絡(luò)環(huán)境下存在的隨機(jī)性、模糊性和不可預(yù)測(cè)性等不確定性因素給網(wǎng)絡(luò)交易帶來(lái)了諸多安全問(wèn)題，而在網(wǎng)絡(luò)交易中，信任是交易能夠順利進(jìn)行的前提和關(guān)鍵。文中以復(fù)雜的網(wǎng)絡(luò)環(huán)境為研究背景，通過(guò)對(duì)復(fù)雜的網(wǎng)絡(luò)環(huán)境中信任、信任影響因素及信任機(jī)制等問(wèn)題的研究，引入云模型理論，研究并提出了基于云模型的信任評(píng)估方法，實(shí)現(xiàn)了信任的定性與定量的轉(zhuǎn)換，客觀地反映了信任的隨機(jī)性、模糊性和不可預(yù)測(cè)性；為了有效地防止不法分子的信用炒作和欺騙行為，文中提出了特殊屬性評(píng)價(jià)方法和信任懲罰方法。通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了文中研究的信任評(píng)估方法能夠?qū)?fù)雜的網(wǎng)絡(luò)環(huán)境中實(shí)體的信任做出合理的評(píng)價(jià)；通過(guò)防信用炒作實(shí)驗(yàn)和防周期行騙實(shí)驗(yàn)，進(jìn)一步驗(yàn)證了基于云模型的信任評(píng)估方法的可行性和合理性，為復(fù)雜的網(wǎng)絡(luò)環(huán)境中信任評(píng)估的研究提供了有價(jià)值的新思路。在復(fù)雜的網(wǎng)絡(luò)環(huán)境中有許多不確定因素（隨機(jī)性、模糊性和不可預(yù)測(cè)性等）都會(huì)對(duì)用戶的信任產(chǎn)生一定影響，而在網(wǎng)絡(luò)交易（例如電子商務(wù)交易）中，只有在交易雙方相互信任的情況下，交易才有可能順利地進(jìn)行下去，所以信任是進(jìn)行交易活動(dòng)的前提和關(guān)鍵。本文以復(fù)雜的網(wǎng)絡(luò)環(huán)境為研究背景，引入云模型理論和借鑒已有工作，研究并提出了針對(duì)復(fù)雜的網(wǎng)絡(luò)環(huán)境下的基于云模型的信任評(píng)估方法；通過(guò)模擬實(shí)際場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)，進(jìn)一步驗(yàn)證了基于云模型的信任評(píng)估方法的可行性和合理性。目前，盡管我們?cè)谛湃卧u(píng)估方面進(jìn)行了一些研究，取得了一些階段性的成果，但是有很多技術(shù)還停留在實(shí)驗(yàn)室中，距離推廣還有很多實(shí)際問(wèn)題需要進(jìn)一步研究解決；除此之外，研究如何防范具有信任詆毀的信任評(píng)估模型也是下一步主要研究的工作。使用本文所研究的基于云模型的信任評(píng)估方法，可以使具有欺騙行為的賣家的信任值陡降，這也證明了基于云模型的信任評(píng)估方法能有效地防止具有欺騙行為的買家，同時(shí)也進(jìn)一步說(shuō)明本文研究的基于云模型的信任評(píng)估方法的可行性和合理性。

來(lái)源出版物：計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 422-431

入選年份：2014

社交網(wǎng)絡(luò)的結(jié)構(gòu)支撐理論

韓毅，許進(jìn)，方濱興，等

摘要：社交網(wǎng)絡(luò)分析是近年來(lái)的研究熱點(diǎn)之一，常見(jiàn)的分析方法包括度分布分析、個(gè)體排名、社區(qū)發(fā)現(xiàn)、模式發(fā)現(xiàn)等。本文中，我們認(rèn)為一個(gè)人的社會(huì)地位與其所在的網(wǎng)絡(luò)結(jié)構(gòu)具有緊密的聯(lián)系，而這種網(wǎng)絡(luò)結(jié)構(gòu)對(duì)成員社會(huì)地位的影響程度是可以被表示和量化的。通過(guò)分析社交網(wǎng)絡(luò)的鏈接結(jié)構(gòu)，將社交網(wǎng)絡(luò)中個(gè)體與個(gè)體間的依賴關(guān)系從一般社會(huì)關(guān)系中抽取出來(lái)，提出了一種基于依賴模型的支持力衡量方法，并基于此給出了一種高效的計(jì)算最具支持力的節(jié)點(diǎn)計(jì)算方法。此外，基于上述模型，設(shè)計(jì)了一種基于依賴關(guān)系的支撐結(jié)構(gòu)模型及其計(jì)算方法，用于刻畫(huà)社交網(wǎng)絡(luò)中特定節(jié)點(diǎn)的影響力來(lái)源。我們?cè)诖笠?guī)模的真實(shí)數(shù)據(jù)環(huán)境下對(duì)模型和算法的正確性、效率和伸縮性進(jìn)行了驗(yàn)證。在社交網(wǎng)絡(luò)全面進(jìn)入人們生活的同時(shí)，也可以發(fā)現(xiàn)微博等社交網(wǎng)絡(luò)上虛假謠言信息盛行、網(wǎng)絡(luò)推手和欺詐活動(dòng)猖獗、甚至針對(duì)社交網(wǎng)絡(luò)的蓄意的煽動(dòng)破壞等現(xiàn)象也給正常的互聯(lián)網(wǎng)社會(huì)活動(dòng)帶來(lái)了有害的影響。本文在分析了社交網(wǎng)絡(luò)中節(jié)點(diǎn)影響力度量函數(shù)及其相互影響的基礎(chǔ)上，給出了社交網(wǎng)絡(luò)上依賴模型、支持力和支撐社區(qū)的定義、性質(zhì)和計(jì)算方法，實(shí)驗(yàn)結(jié)果證明了本文的模型和方法是正確且高效的。社交網(wǎng)絡(luò)上的結(jié)構(gòu)支撐理論分析具有廣泛的應(yīng)用前景，例如，例如，在在線社交網(wǎng)站上，通過(guò)分析節(jié)點(diǎn)在結(jié)構(gòu)中的支持力，可以綜合分析其承載的輿情信息的傳播能力，從而可以進(jìn)行商業(yè)推廣，或進(jìn)行輿論導(dǎo)向等研究。在Web結(jié)構(gòu)上，對(duì)于一個(gè)給定節(jié)點(diǎn)，必定會(huì)有一組節(jié)點(diǎn)共同組成其支持社團(tuán)，通過(guò)分析支持社團(tuán)的互聯(lián)結(jié)構(gòu)，可以有效地識(shí)別人為構(gòu)造的網(wǎng)絡(luò)鏈接垃圾結(jié)構(gòu)等。在線社交網(wǎng)絡(luò)是一個(gè)異質(zhì)復(fù)雜網(wǎng)絡(luò)，在社交網(wǎng)絡(luò)的結(jié)構(gòu)支撐理論方面，下一步可以將本文的工作進(jìn)一步深化，研究社交網(wǎng)絡(luò)中內(nèi)容和結(jié)構(gòu)的互依賴和支持關(guān)系，必將具有良好的研究前景。此外，如何利用網(wǎng)絡(luò)大數(shù)據(jù)管理系統(tǒng)對(duì)本文提出的算法進(jìn)行優(yōu)化，也是一個(gè)下一步值得研究的問(wèn)題。

來(lái)源出版物：計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 905-914

入選年份：2014