【摘要】：云計(jì)算是信息技術(shù)革命的產(chǎn)物,是一種大規(guī)模復(fù)雜計(jì)算系統(tǒng)。云計(jì)算系統(tǒng)時(shí)刻都在處理海量數(shù)據(jù)和應(yīng)用任務(wù),具有高度的動(dòng)態(tài)性。由于云計(jì)算系統(tǒng)具有資源規(guī)模龐大且異構(gòu)多樣、用戶群體廣泛、應(yīng)用任務(wù)類型各異且QoS目標(biāo)約束各異等特性,系統(tǒng)需要頻繁地對云平臺(tái)中的各種資源與應(yīng)用任務(wù)進(jìn)行實(shí)時(shí)調(diào)度和動(dòng)態(tài)管理。而云計(jì)算作為一種商業(yè)計(jì)算模式,其目的是實(shí)現(xiàn)資源共享與協(xié)同工作,并同時(shí)滿足用戶的服務(wù)請求和云服務(wù)提供商的服務(wù)收益。因此,如何對云資源進(jìn)行合理的分配,對海量應(yīng)用任務(wù)進(jìn)行高效管理與實(shí)時(shí)調(diào)度,在確保云計(jì)算系統(tǒng)負(fù)載均衡和提高云資源利用率的前提下,降低用戶的成本,提高云服務(wù)提供商的收益,是目前云計(jì)算環(huán)境下的研究熱點(diǎn)之一。從本質(zhì)上說,云計(jì)算環(huán)境下的任務(wù)調(diào)度是需要建立一種應(yīng)用任務(wù)與計(jì)算資源之間合適的映射關(guān)系的調(diào)度策略,其目的是實(shí)現(xiàn)計(jì)算資源的合理分配與應(yīng)用任務(wù)的高效執(zhí)行。早期傳統(tǒng)的分布式計(jì)算系統(tǒng)、網(wǎng)格計(jì)算系統(tǒng)等,通過系統(tǒng)吞吐量和任務(wù)完成時(shí)間等性能指標(biāo)衡量調(diào)度管理的效果。但是在云計(jì)算環(huán)境下,任務(wù)調(diào)度問題往往更加復(fù)雜。首先,云計(jì)算環(huán)境下應(yīng)用任務(wù)請求往往是非集中式的,而且規(guī)模巨大,傳統(tǒng)的集中式的資源管理系統(tǒng)已經(jīng)不再適用,云計(jì)算系統(tǒng)必須以一種分布式的并行模式對任務(wù)和資源進(jìn)行調(diào)度與管理;其次,云資源通常來自不同的云服務(wù)提供商,各個(gè)機(jī)構(gòu)的云資源往往是異構(gòu)的,如何將各種異構(gòu)資源組合成完整的服務(wù)提供給用戶是非常復(fù)雜的;再者,由于云計(jì)算系統(tǒng)具有動(dòng)態(tài)可擴(kuò)展的性質(zhì),相應(yīng)的任務(wù)調(diào)度也必須滿足可擴(kuò)展性與自適應(yīng)性;然后,云計(jì)算作為一種商業(yè)模式,云服務(wù)提供商首先要考慮的是如何提高自身的資源利用率,提升共享使用率從而降低成本,獲得盡可能多的服務(wù)收益,這就使得任務(wù)調(diào)度必須考慮云計(jì)算系統(tǒng)的整體負(fù)載均衡問題。最后,從用戶的角度而言,云服務(wù)提供商所提供的服務(wù)是否滿足用戶任務(wù)調(diào)度的QoS多目標(biāo)需求是任務(wù)調(diào)度策略必須考慮的問題。因此,針對上述目前云計(jì)算環(huán)境下任務(wù)調(diào)度存在的問題,本文對云環(huán)境下的任務(wù)調(diào)度技術(shù)做了詳細(xì)而系統(tǒng)的研究,其主要內(nèi)容包括四個(gè)方面:云環(huán)境下用戶任務(wù)調(diào)度的QoS多目標(biāo)優(yōu)化問題、云資源利用率與云計(jì)算系統(tǒng)負(fù)載均衡問題、云計(jì)算系統(tǒng)任務(wù)調(diào)度策略執(zhí)行效率問題、用戶任務(wù)調(diào)度成本與云服務(wù)提供商服務(wù)收益問題。本文在對這些問題進(jìn)行深入研究的基礎(chǔ)上,設(shè)計(jì)了一套云計(jì)算環(huán)境下的自主調(diào)度體系架構(gòu),并對其中重要功能都給出了詳細(xì)的算法與實(shí)驗(yàn)結(jié)果。論文的主要研究內(nèi)容包括以下幾個(gè)方面:1)在分析和研究了云計(jì)算環(huán)境下任務(wù)調(diào)度存在的問題及目標(biāo)要求的基礎(chǔ)上,提出了一種云計(jì)算環(huán)境下的自主調(diào)度體系架構(gòu)。在自主調(diào)度體系架構(gòu)中,系統(tǒng)為每個(gè)向云計(jì)算系統(tǒng)請求服務(wù)的用戶創(chuàng)建一個(gè)云代理進(jìn)行智能分析和決策,并為每個(gè)云代理設(shè)計(jì)了分析、評估、博弈等功能與算法。本文通過對云代理功能進(jìn)行分類,設(shè)計(jì)了一個(gè)兩層的自上而下的自主調(diào)度模型。其中,針對用戶與云服務(wù)提供商之間的協(xié)商問題,設(shè)計(jì)了云代理協(xié)商模型。云代理通過一系列約束規(guī)則與目標(biāo)規(guī)則選擇符合用戶QoS目標(biāo)約束的SLA協(xié)議,并對SLA協(xié)議進(jìn)行評估。其次,針對多個(gè)用戶對關(guān)鍵資源的競爭而導(dǎo)致的資源沖突問題,設(shè)計(jì)了云代理博弈模型。云代理將系統(tǒng)全局收益函數(shù)引入到用戶個(gè)體的收益函數(shù)中,在滿足用戶QoS多目標(biāo)優(yōu)化需求的前提下,云代理之間通過自主競爭博弈的模式,使整個(gè)系統(tǒng)達(dá)成全局利益最優(yōu)。云代理通過協(xié)商、自主博弈的方式實(shí)現(xiàn)了用戶任務(wù)的自主調(diào)度,提高了任務(wù)調(diào)度策略的執(zhí)行效率,并且降低了用戶的調(diào)度成本,也提高了云服務(wù)提供商的服務(wù)收益。2)針對在云計(jì)算環(huán)境下,用戶如何判斷云服務(wù)提供商在SLA中承諾的資源是否滿足用戶任務(wù)的QoS需求,本文提出了一種星型結(jié)構(gòu)下的SLA任務(wù)調(diào)度評估算法。該算法通過云代理將云服務(wù)提供商SLA中承諾的資源抽象為標(biāo)準(zhǔn)的虛擬資源,并將用戶任務(wù)與虛擬資源的映射關(guān)系抽象為星型拓?fù)浣Y(jié)構(gòu)的云計(jì)算系統(tǒng)。通過評估云計(jì)算系統(tǒng)的性能與可靠性,評估相應(yīng)云服務(wù)提供商所承諾的資源的服務(wù)質(zhì)量。用戶將SLA中承諾的服務(wù)質(zhì)量作為一種判斷標(biāo)準(zhǔn),判斷云服務(wù)提供商提供的服務(wù)是否能夠滿足用戶任務(wù)的QoS需求。3)針對用戶任務(wù)調(diào)度的QoS多目標(biāo)優(yōu)化問題,提出了一種基于NSGA-II的多目標(biāo)優(yōu)化調(diào)度算法。云計(jì)算環(huán)境下,用戶如何在一組有效的SLA集合中,選出符合其QoS多目標(biāo)優(yōu)化需求的調(diào)度策略依然是非常困難的問題。用戶請求的任務(wù)集通常包含多個(gè)任務(wù),每個(gè)任務(wù)都可以和不同的云服務(wù)提供商簽訂SLA協(xié)議,整個(gè)任務(wù)集的SLA協(xié)議由單個(gè)任務(wù)的SLA協(xié)議組合而成,組合過程往往呈現(xiàn)出指數(shù)級的復(fù)雜度。另一方面,用戶的QoS目標(biāo)之間往往是沖突的,例如,服務(wù)時(shí)間和服務(wù)成本之間是沖突的,要獲得快速響應(yīng)的服務(wù),就需要計(jì)算能力較高的資源,而計(jì)算能力越高其成本就越高,必然無法同時(shí)滿足兩個(gè)目標(biāo)。本文提出的算法為用戶提供了一種高效快速的選擇機(jī)制,通過NSGA-II算法對多個(gè)目標(biāo)進(jìn)行并行搜索,與傳統(tǒng)的將多個(gè)目標(biāo)轉(zhuǎn)化為單目標(biāo)問題相比,本文的算法能夠在滿足用戶QoS多目標(biāo)優(yōu)化需求的前提下,高效地為其選擇合理的最優(yōu)的SLA任務(wù)調(diào)度策略。4)在已經(jīng)簽訂了SLA協(xié)議的情況下,用戶任務(wù)選擇SLA中不同的云資源構(gòu)成了不同的任務(wù)調(diào)度策略。針對如何判斷哪些調(diào)度策略滿足用戶的QoS多目標(biāo)優(yōu)化需求,提出了一種虛擬樹型結(jié)構(gòu)下的調(diào)度評估算法。根據(jù)云資源的性質(zhì),將用戶任務(wù)與云資源的映射關(guān)系建模為由網(wǎng)絡(luò)連接起來的虛擬樹型結(jié)構(gòu)。在樹型結(jié)構(gòu)下,通常需要考慮共享傳輸通道失效引起的共因失效問題。針對此問題,本文利用最小生成樹算法對云資源與傳輸通道進(jìn)行數(shù)學(xué)建模。對于一個(gè)任務(wù)分配給多個(gè)資源節(jié)點(diǎn)冗余執(zhí)行的情況,只要存在一個(gè)資源節(jié)點(diǎn)不失效,該任務(wù)就能成功完成;對于多個(gè)任務(wù)共享同一資源的情況,算法通過在云資源節(jié)點(diǎn)上增加新的分支和葉子節(jié)點(diǎn),如果是并行任務(wù)就平均分配共享資源,如果是串行任務(wù)則獨(dú)享資源。因此,在樹型結(jié)構(gòu)下,用戶任務(wù)與云資源之間是一種動(dòng)態(tài)靈活的映射模式。本文提出的算法能夠?qū)θ我庖粋�(gè)任務(wù)調(diào)度策略的服務(wù)質(zhì)量進(jìn)行快速且準(zhǔn)確的評估,將其應(yīng)用于云代理博弈模型的效用函數(shù)計(jì)算中,在提高每個(gè)用戶的調(diào)度策略執(zhí)行效率的同時(shí),也提高了云服務(wù)提供商的資源利用率。5)針對大量用戶同時(shí)提交任務(wù)調(diào)度請求的問題,以及多個(gè)用戶之間對關(guān)鍵資源的競爭問題,本文在博弈論的基礎(chǔ)上提出了一種基于囚徒困境博弈的多代理自主調(diào)度算法。該算法假設(shè)每個(gè)用戶具有自己的偏好和自私性的特性,總是傾向最大化自己的利益,每個(gè)用戶都只會(huì)選擇對自己最有利的資源,不管是否對其他用戶產(chǎn)生影響。由于用戶的個(gè)體理性,形成了囚徒困境,導(dǎo)致了資源分配沖突,比如大多數(shù)用戶都選擇了同一個(gè)資源,使得系統(tǒng)負(fù)載不均衡。算法通過云代理之間的自主博弈過程,將云計(jì)算系統(tǒng)的全局效用目標(biāo)融入到每個(gè)用戶的局部效用目標(biāo)中,通過設(shè)計(jì)云代理之間的博弈規(guī)則和對應(yīng)的獎(jiǎng)勵(lì)因子,在每個(gè)云代理追求各自效用目標(biāo)的前提下,使得整個(gè)云計(jì)算系統(tǒng)獲得全局最優(yōu)收益。通過本文提出的自主調(diào)度算法,不僅使競爭性環(huán)境下的每個(gè)用戶都能找到最優(yōu)的任務(wù)調(diào)度策略,同時(shí)也降低了用戶的調(diào)度成本,提高了云服務(wù)提供商的整體收益。
[Abstract]:Cloud computing is the product of information technology revolution, it is a large-scale complex computing system. Cloud computing system is very dynamic in processing mass data and application tasks at all times. As the cloud computing system has the characteristics of large resource scale, diverse heterogeneity, wide user groups, different application task types and different QoS target constraints, the system needs to carry out real-time scheduling and dynamic management of various resources and application tasks in the cloud platform. As a kind of business computing model, cloud computing aims to realize resource sharing and cooperative work, and simultaneously meet user's service request and cloud service provider's service revenue. Therefore, how to allocate the cloud resources reasonably, carry out efficient management and real-time scheduling on the mass application tasks, reduce the user's cost on the premise of ensuring the load balance of the cloud computing system and improve the utilization rate of the cloud resources, improve the income of the cloud service provider, It is one of the research hot spots in the current cloud computing environment. In essence, task scheduling under cloud computing environment is a scheduling strategy that needs to establish a proper mapping relation between application task and computing resources, which aims to realize the efficient execution of the reasonable allocation and application task of computing resources. Early traditional distributed computing systems, grid computing systems, etc. measure the effect of scheduling management through performance metrics such as system throughput and task completion time. But in cloud computing environments, task scheduling problems are often more complex. firstly, the application task request in the cloud computing environment is often non-centralized, and the scale is huge; the traditional centralized resource management system is no longer applicable; the cloud computing system must schedule and manage the tasks and resources in a distributed parallel mode; secondly, cloud resources typically come from different cloud service providers, the cloud resources of each organization are often heterogeneous, how to combine heterogeneous resources into a complete service is very complex to the user; furthermore, since the cloud computing system has a dynamically expandable nature, The corresponding task scheduling must also meet scalability and adaptability; then, cloud computing as a business model, cloud service providers first consider how to improve their own resource utilization, increase share usage, reduce costs, and obtain as much service revenue as possible, This allows task scheduling to take into account the overall load balancing problem of the cloud computing system. Finally, from the perspective of the user, whether the service provided by the cloud service provider satisfies the QoS multi-target requirement of the user task scheduling is a problem that the task scheduling policy must consider. Therefore, aiming at the existing problem of task scheduling in cloud computing environment, this paper studies the task scheduling technology in cloud environment in detail, and its main content includes four aspects: multi-objective optimization problem of user task scheduling under cloud environment, Cloud resource utilization and cloud computing system load balancing problem, cloud computing system task scheduling policy implementation efficiency problem, user task scheduling cost and cloud service provider service revenue problem. On the basis of deeply studying these problems, this paper designs an architecture of autonomous scheduling system under a cloud computing environment, and gives detailed algorithm and experimental results for the important functions. The main research contents include the following aspects: 1) On the basis of analyzing and studying the problems and target requirements of task scheduling in cloud computing environment, a self-scheduling system architecture under cloud computing environment is proposed. In the architecture of autonomous scheduling system, the system creates a cloud agent for intelligent analysis and decision-making for each user requesting service to the cloud computing system, and designs the functions and algorithms such as analysis, evaluation, game, etc. for each cloud agent. In this paper, a two-tier top-down autonomous scheduling model is designed by classifying the functions of cloud agents. In this paper, a cloud broker negotiation model is designed for negotiation between users and cloud service providers. The cloud broker selects SLA agreements that conform to user QoS target constraints through a series of constraint rules and target rules, and evaluates SLA protocols. Secondly, a cloud agent game model is designed for resource conflict caused by competition of key resources by a plurality of users. The cloud agent introduces the global revenue function of the system into the income function of the user's individual, and under the premise of satisfying the multi-objective optimization requirement of the user's QoS, the cloud agent achieves the best global benefit through the mode of autonomous competition game between the cloud agents. the cloud agent realizes autonomous scheduling of the user task through negotiation and autonomous game mode, improves the execution efficiency of the task scheduling strategy, reduces the scheduling cost of the user and improves the service income of the cloud service provider. How users judge whether the resources committed by cloud service providers in SLA meet the QoS requirements of user's tasks. This paper presents an SLA task scheduling evaluation algorithm under star structure. The algorithm abstracted the resources promised in the cloud service provider SLA into the standard virtual resource through the cloud proxy, and abstracted the mapping relation between the user's task and the virtual resource into the cloud computing system of the star topology structure. By evaluating the performance and reliability of the cloud computing system, the quality of service of the resources committed by the respective cloud service providers is assessed. Based on NSGA-II, a multi-objective optimization scheduling algorithm based on NSGA-II is proposed. In a cloud computing environment, how users choose a scheduling strategy that fits their QoS multi-objective optimization needs in a set of valid SLA collections remains very difficult. The task set requested by the user usually contains a plurality of tasks, each task can enter into an SLA protocol with different cloud service providers, the SLA protocol of the whole task set is formed by the SLA protocol of a single task, and the combining process often presents the complexity of the exponential grade. On the other hand, the QoS target of the user is often conflict, for example, the service time and the service cost are conflicting, and a fast response service is obtained, resources with higher computing power are required, and the higher the computing power is, the higher the cost is, and the two targets cannot be simultaneously satisfied. The algorithm proposed in this paper provides a kind of efficient and fast selection mechanism, which can search multiple targets in parallel through the NSGA-II algorithm. Compared with the traditional single target problem, the algorithm can meet the requirement of user QoS multi-objective optimization. When SLA agreements have been signed, the user task selects different cloud resources in SLA to form different task scheduling strategies. Based on how to judge which scheduling strategies meet the QoS multi-objective optimization needs of users, a scheduling evaluation algorithm under virtual tree structure is proposed. according to the nature of the cloud resource, the mapping relationship between the user task and the cloud resource is modeled as a virtual tree type structure connected by a network. In tree-type structures, there is a general need to consider a CCF caused by a shared transmission channel failure. Aiming at this problem, this paper uses the minimum spanning tree algorithm to model the cloud resource and the transmission channel. for a case where a task is assigned to redundant execution of a plurality of resource nodes, the task can be successfully completed as long as there is a resource node which does not fail, and the algorithm increases the new branch and leaf nodes on the cloud resource node if the same resource is shared among a plurality of tasks, If it is a parallel task, the shared resource is evenly shared, and if it is a serial task, the resource is exclusive. Therefore, under the tree-type structure, the user task and the cloud resource are a dynamic and flexible mapping mode. The algorithm proposed in this paper can quickly and accurately evaluate the quality of service of any task scheduling policy, and apply it to the dynamic calculation of cloud proxy game model. At the same time, it can improve the execution efficiency of each user's scheduling policy. also improves the resource utilization rate of the cloud service provider (5) solves the problem that the task scheduling request is simultaneously submitted by a large number of users and the competition problem of the key resources among a plurality of users, Based on game theory, this paper proposes a multi-agent autonomous scheduling algorithm based on Prisoner's dilemma game. The algorithm assumes that each user has its own preferences and selfish characteristics, always tends to maximize his own interests, and each user will only choose the most favorable resource for himself, whether or not it has an impact on other users. Because of the individual reason of the user, the prisoner's dilemma is formed, resulting in resource allocation conflict, for example, most users choose the same resource, making the system load unbalanced. Through the autonomous game process between cloud agents, the global utility target of the cloud computing system is integrated into the local utility target of each user, so that the whole cloud computing system obtains the global optimal revenue. The autonomous scheduling algorithm proposed in this paper not only enables each user in a competitive environment to find the optimal task scheduling policy, but also reduces the scheduling cost of the user, and improves the overall revenue of the cloud service provider.
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 葛敬軍;胡長軍;劉歆;李揚(yáng);劉振宇;;領(lǐng)域科學(xué)數(shù)據(jù)云資源聚合模型[J];計(jì)算機(jī)科學(xué);2013年09期

2 李陶深;張希翔;;云計(jì)算下區(qū)分服務(wù)的演化博弈調(diào)度算法[J];北京郵電大學(xué)學(xué)報(bào);2013年01期

相關(guān)博士學(xué)位論文 前2條

1 徐昕;基于博弈論的云計(jì)算資源調(diào)度方法研究[D];華東理工大學(xué);2015年

2 鄧見光;云計(jì)算任務(wù)調(diào)度策略研究[D];華南理工大學(xué);2014年

相關(guān)碩士學(xué)位論文 前1條

1 高媛;非支配排序遺傳算法（NSGA）的研究與應(yīng)用[D];浙江大學(xué);2006年

，

本文編號：2256249