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

師雪霖，徐恪

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

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

師雪霖，徐恪

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

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

入選年份：2014

基于云模型的信任評估方法研究

張仕斌，許春香

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

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

入選年份：2014

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

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

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

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

入選年份：2014