Distributed optimal resource allocation of second‐order multiagent systems

In this paper, the resource allocation problems of multiagent systems are investigated. Different from the well‐studied resource allocation problems, the dynamics of agents are taken into account in our problem, which results that the problem could not be solved by most of existing resource allocation algorithms. Here, the agents are in the form of second‐order dynamics, which causes the difficulties in designing and analyzing distributed resource allocation algorithms. Based on gradient descent and state feedback, two distributed resource allocation algorithms are proposed to achieve the optimal allocation, and their convergence are analyzed by constructing suitable Lyapunov functions. One of the two algorithms can ensure that the decisions of all agents asymptotically converge to the exact optimal solution, and the other algorithm achieves the exponential convergence. Finally, numerical examples about the economic dispatch problems of power grids are given to verify the effectiveness of the obtained results.     

A Heuristic Genetic Algorithm for Solving Resource Allocation Problems

In the paper, a heuristic genetic algorithm for solving resource allocation problems is proposed. The resource allocation problems are to allocate resources to activities so that the fitness becomes as optimal as possible. The objective of this paper is to develop an efficient algorithm to solve resource allocation problems encountered in practice. Various genetic algorithms are studied and a heuristic genetic algorithm is proposed to ameliorate the rate of convergence for resource allocation problems. Simulation results show that the proposed algorithm gives the best performance.     

Honey bee social foraging algorithms for resource allocation: Theory and application

A model of honey bee social foraging is introduced to create an algorithm that solves a class of dynamic resource allocation problems. We prove that if several such algorithms (“hives”) compete in the same problem domain, the strategy they use is a Nash equilibrium and an evolutionarily stable strategy. Moreover, for a single or multiple hives we prove that the allocation strategy is globally optimal. To illustrate the practical utility of the theoretical results and algorithm we show how it can solve a dynamic voltage allocation problem to achieve a maximum uniformly elevated temperature in an interconnected grid of temperature zones.     

Cooperative game-based distributed resource allocation in horizontal dynamic cloud federation platform

Distributed resource allocation is a very important and complex problem in emerging horizontal dynamic cloud federation (HDCF) platforms, where different cloud providers (CPs) collaborate dynamically to gain economies of scale and enlargements of their virtual machine (VM) infrastructure capabilities in order to meet consumer requirements. HDCF platforms differ from the existing vertical supply chain federation (VSCF) models in terms of establishing federation and dynamic pricing. There is a need to develop algorithms that can capture this complexity and easily solve distributed VM resource allocation problem in a HDCF platform. In this paper, we propose a cooperative game-theoretic solution that is mutually beneficial to the CPs. It is shown that in non-cooperative environment, the optimal aggregated benefit received by the CPs is not guaranteed. We study two utility maximizing cooperative resource allocation games in a HDCF environment. We use price-based resource allocation strategy and present both centralized and distributed algorithms to find optimal solutions to these games. Various simulations were carried out to verify the proposed algorithms. The simulation results demonstrate that the algorithms are effective, showing robust performance for resource allocation and requiring minimal computation time.     

Comparing various approaches to resource allocation in data centers

In this paper, abstractions for describing resource requests and physical resources of data centers are chosen. A mathematical model of a data center is developed; this model provides an opportunity for describing a wide class of data center architectures. In terms of this model, a mathematical formulation of the resource allocation problem is given that admits migration of virtual machines and replication of data storage elements. Resource allocation algorithms for data centers with a unified scheduler for all types of resources, algorithms for data centers with specific schedulers for each type of resources, and similar algorithms from the OpenStack platform are compared; the comparison results are presented.     

到达时间依赖于资源分配的单机排序问题*

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。     

具有用户体验保障的资源优化分配算法

在研究智能电视用户体验质量(Quality of Experience,QoE)量化的基础上,提出一种具有用户体验保障的资源分配模型,并针对该模型提出两种资源分配算法:RA_BAT算法和RA_GHEU算法.实验结果表明,基于回溯法的RA_BAT能够求得问题的最优解,可作为算法比较的参照系,而启发式算法RA_GHEU可在极短的运行时间内求出接近于最优的解,适合用于智能电视资源分配的实时处理.     

基于连续时间的二阶多智能体分布式资源分配算法

针对二阶多智能体系统中的分布式资源分配问题, 本文设计两种连续时间算法. 基于KKT (Karush−Kuhn−Tucker, 卡罗需−库恩−塔克)优化条件, 第一种控制算法利用节点局部不等式及其梯度信息来约束节点状态. 与上述梯度方法不同, 第二种控制算法包括一致性梯度下降法和固定时间收敛映射算子, 其中固定时间收敛映射算子确保算法的节点状态在固定时间收敛到局部约束集, 一致性梯度下降法目的是确保节点迭代到资源分配问题最优解. 两种控制算法都对状态无初始值约束, 且控制参数都是常数. 利用凸优化理论和固定时间李雅普诺夫方法, 分别分析了上述控制策略在有向平衡网络条件下的渐近和指数收敛性. 最后通过数值仿真验证了所设计算法在一维和高维资源分配问题的有效性.     

Model Predictive Control for Stochastic Resource Allocation

In this paper, we consider a class of stochastic resource allocation problems where resources assigned to a task may fail probabilistically to complete assigned tasks. Failures to complete a task are observed before new resource allocations are selected. The resulting temporal resource allocation problem is a stochastic control problem, with a discrete state space and control space that grow in cardinality exponentially with the number of tasks. We modify this optimal control problem by expanding the admissible control space, and show that the resulting control problem can be solved exactly by efficient algorithms in time that grows nearly linear with the number of tasks. The approximate control problem also provides a bound on the achievable performance for the original control problem. The approximation is used as part of a model predictive control (MPC) algorithm to generate resource allocations over time in response to information on task completion status. We show in computational experiments that, for single resource class problems, the resulting MPC algorithm achieves nearly the same performance as the optimal dynamic programming algorithm while reducing computation time by over four orders of magnitude. In multiple resource class experiments involving 1000 tasks, the model predictive control performance is within 4% of the performance bound obtained by the solution of the expanded control space problem.     

Game Theoretic subcarrier and power allocation for wireless OFDMA networks

This paper proposes a bargaining game theoretic resource(including the subcarrier and the power) allocation scheme for wireless orthogonal frequency division multiple access(OFDMA) networks.We define a wireless user s payoff as a function of the achieved data-rate.The fairness resource allocation problem can then be modeled as a cooperative bargaining game.The objective of the game is to maximize the aggregate payoffs for the users.To search for the Nash bargaining solution(NBS) of the game,a suboptimal subcarrier allocation is performed by assuming an equal power allocation.Thereafter,an optimal power allocation is performed to maximize the sum payoff for the users.By comparing with the max-rate and the max-min algorithms,simulation results show that the proposed game could achieve a good tradeoff between the user fairness and the overall system performance.     

Incorporating structural improvement into resource allocation for business process execution planning

Resource management has been recognised as an important topic for business process execution for a long time. Most existing works on resource allocation for business processes simply assume that the structure of a business process is always fixed, and therefore do not discuss the possibility of optimising resource allocation by adapting process structures to actual resource situations. To fill this gap, we propose a resource optimisation approach of improving process structures according to resource situations and thereby pursuing the best resource utilisation efficiency. This approach comprises a role‐based business process model for resource allocation and the strategies for optimising resource allocation in conjunction with a business process improvement. A set of heuristic rules are established to guide the resource allocation for the purposes of preventing resource conflicts, shortening the total execution time, minimising the total cost, etc. Particular algorithms are also developed to implement the resource allocation according to these rules. In addition, an experimental study is conducted to discuss the incorporation of business process improvement into resource allocation for optimal process execution. Copyright © 2012 John Wiley & Sons, Ltd.     

Resource allocation for primary-site fault-tolerant systems

Resource allocation for a distributed system employing the primary site approach for fault tolerance is discussed. Two kinds of systems are considered. The first consists of fault-tolerant nodes where each node has many duplicated servers. One server is the primary, which serves user requests, and the rest are backup. The second does not have fault-tolerant nodes. To tolerate node failures, each node uses other nodes as backups. When a node fails, all requests initially allocated to the node are served by one of its backups. To study the resource allocation for such systems, an approximate model for each system is developed. Using these models, efficient allocation algorithms that take into account the failure/repair rates of the system and the fault-tolerant overheads are presented. Using experimental results, it is shown that the algorithms give the optimal or suboptimal allocations. The algorithms, which incur little overhead, can improve the system performance significantly over an intuitive allocation algorithm     

Resource Allocation Based on User Pairing and Subcarrier Matching for Downlink Non-Orthogonal Multiple Access Networks

The traditional orthogonal multiple access(OMA)is unable to satisfy the needs of large number of smart devices.To increase the transmission rate in the limited spectrum resource,implementation of both non-orthogonal multiple access(NOMA)and successive interference cancelation(SIC)is essential.In this paper,an optimal resource allocation algorithm in NOMA is proposed to maximize the total system rate in a multi-sector multi-subcarrier relay-assisted communication network.Since the original problem is a non-convex problem with mixed integer programming which is non-deterministic polynomial-time(NP)-hard,a three-step solution is proposed to solve the primal problem.Firstly,we determine the optimal power allocation of the outer users by using the approach of monotonic discrimination,and then the optimal user pairing is determined.Secondly,the successive convex approximation(SCA)method is introduced to transform the non-convex problem involving central users into convex one,and the Lagrangian dual method is used to determine the optimal solution.Finally,the standard Hungarian algorithm is utilized to determine the optimal subcarrier matching.The simulation results show that resource allocation algorithm is able to meet the user performance requirements with NOMA,and the total system rate is improved compared to the existing algorithms.     

Distributed envy minimization for resource allocation

Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, Distributed Envy Minimization Problems (DEMP) are formulated as Distributed Constraint Reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents.     

A model predictive control approach to the periodic implementation of the solutions of the optimal dynamic resource allocation problem

This paper proposes a model predictive control (MPC) approach to the periodic implementation of the optimal solutions of a class of resource allocation problems in which the allocation requirements and conditions repeat periodically over time. This special class of resource allocation problems includes many practical energy optimization problems such as load scheduling and generation dispatch. The convergence and robustness of the MPC algorithm is proved by invoking results from convex optimization. To illustrate the practical applications of the MPC algorithm, the energy optimization of a water pumping system is studied.     

A game-theoretic method of fair resource allocation for cloud computing services

As cloud-based services become more numerous and dynamic, resource provisioning becomes more and more challenging. A QoS constrained resource allocation problem is considered in this paper, in which service demanders intend to solve sophisticated parallel computing problem by requesting the usage of resources across a cloud-based network, and a cost of each computational service depends on the amount of computation. Game theory is used to solve the problem of resource allocation. A practical approximated solution with the following two steps is proposed. First, each participant solves its optimal problem independently, without consideration of the multiplexing of resource assignments. A Binary Integer Programming method is proposed to solve the independent optimization. Second, an evolutionary mechanism is designed, which changes multiplexed strategies of the initial optimal solutions of different participants with minimizing their efficiency losses. The algorithms in the evolutionary mechanism take both optimization and fairness into account. It is demonstrated that Nash equilibrium always exists if the resource allocation game has feasible solutions.     

Adaptive joint bandwidth and power allocation in heterogeneous wireless access environment

Joint bandwidth and power allocation for a multi-radio access(MRA)system in a heterogeneous wireless access environment is studied.Since both the number of users being served by the system and the wireless channel state are time-varying,the optimal resource allocation is no longer a static optimum and will change with the varying network state.Moreover,distributed resource allocation algorithms that require iterative updating and signaling interactions cannot converge in negligible time.Thus,it is unrealistic to assume that the active user number and the wireless channel state remain unchanged during the iterations.In this paper,we propose an adaptive joint bandwidth and power allocation algorithm based on a novel iteration stepsize selection method,which can adapt to the varying network state and accelerate the convergence rate.A distributed solution is also designed for the adaptive joint resource allocation implementation.Numerical results show that the proposed algorithm can not only track the varying optimal resource allocation result much more quickly than a traditional algorithm with fixed iteration stepsize,but can also reduce the data transmission time for users and increase the system throughput.     

Agent based sensors resource allocation in sensor grid

Sensor enabled grid may combine real time data about physical environment with vast computational resources derived from the grid architecture. One of the major challenges of designing a sensor enabled grid is how to efficiently schedule sensor resource to user jobs across the collection of sensor resources. The paper presents an agent based scheme for assigning sensor resources to appropriate sensor grid users on the basis of negotiation results among agents. The proposed model consists of two types of agents: the sensor resource agents that represent the economic interests of the underlying sensor resource providers of the sensor grid and the sensor user agents that represent the interests of grid user application using the grid to achieve goals. Interactions between the two agent types are mediated by means of market mechanisms. We model sensor allocation problems by introducing the sensor utility function. The goal is to find a sensor resource allocation that maximizes the total profit. This paper proposes a distributed optimal sensor resource allocation algorithm. The performance evaluation of proposed algorithm is evaluated and compared with other resource allocation algorithms for sensor grid. The paper also gives the application example of proposed approach.     

Joint spectrum allocation and scheduling for fair spectrum sharing in cognitive radio wireless networks

Cognitive radio and Dynamic Spectrum Access (DSA) enable wireless users to share a wide range of available spectrums. In this paper, we study joint spectrum allocation and scheduling problems in cognitive radio wireless networks with the objectives of achieving fair spectrum sharing. A novel Multi-Channel Contention Graph (MCCG) is proposed to characterize the impact of interference under the protocol model in such networks. Based on the MCCG, we present an optimal algorithm to compute maximum throughput solutions. As simply maximizing throughput may result in a severe bias on resource allocation, we take fairness into consideration by presenting optimal algorithms as well as fast heuristics to compute fair solutions based on a simplified max–min fairness model and the well-known proportional fairness model. Numerical results show that the performance given by our heuristic algorithms is very close to that of the optimal solution, and our proportional fair algorithms achieve a good tradeoff between throughput and fairness. In addition, we extend our research to the physical interference model, and propose effective heuristics for solving the corresponding problems.     

基于云计算的ACO-K中心点资源优化算法

云计算是计算网络模型研究的热点领域,能实现几种资源共享和资源动态配置。然而,云计算中存储资源如何快速路由,减少动态负荷,兼顾全局负载平衡是有待解决的问题。ACO是一种仿生优化算法,具有健壮性强、智能搜索、全局优化、易与其他算法结合等优点。K中心点算法是K均值的改进算法,鲁棒性强,不易受极端数据的影响。结合这两种算法的优点,提出一种基于云计算环境下的ACO-K中心点资源分配优化算法,得到最优的计算资源,提高云计算的效率。通过仿真验证了该算法的有效性。