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 feedback-coupled resource allocation policy for multiprogrammed computer systems

Summary An earlier paper on an adaptive workload balancing strategy to achieve efficient resource utilization is extended to include memory cost. The scheme corrects for the imbalance in resource utilization by bringing into play the “Invisible Hand” of classical economics. In this framework, the memory price and the bid, W _ij, of each user program U _jfor resource R _iare calculated adaptively. These prices are not apparent to the users, but they are rather shadow prices determined from the characteristics of user programs, the current resource congestion, and the budget constraints of users. There emerge a set of effective priorities for user programs based on the bid prices, W _ij, and these determine the scheduling of programs. An imbalance due to high congestion of some resource will result in a relative decrease of priority for heavy users ofthat resource and a relative increase for light users. Some ideas on an actual implementation scheme are described based on an approximation to the above abstract scheme. It is shown that this approximate scheme will also tend to balance resource utilization.     

A flexible layered control policy for resource allocation in a sensor grid

The paper proposes a flexible layered control policy for sensor resource allocation in a sensor grid. In order to allocate sensor resources in the system to maximize the sensor grid utility, different controllers are deployed at three levels: a job-level controller, an application group controller, and a sensor grid system controller. At the lowest levels, job-level controllers perform fast, frequent, local adaptation for optimizing a single sensor grid application at a time, while, at the highest levels, sensor grid system controllers perform less frequent control actions to optimize all applications. Sensor grid system control considers all sensor grid applications in response to large system changes at coarse time granularity. Sensor grid system control exploits the interlayer coupling of the resource layer and the application layer to achieve a system-wide optimization based on the sensor grid users’ preferences. Job-level control adapts a single application to small changes at fine granularity. The layered control system uses a set of utility functions to evaluate the performance of sensor grid applications and groups. The control system chooses control actions that would result in a higher level of utility. In the simulation, a performance evaluation of the algorithm is carried out.     

无线供能协作计算网络中的时延最小化资源分配方案

在单专用能量站为多个用户无线供能的场景下,为缩短任务处理时延,设计了一种新型多用户协作计算方案。建立了关于匹配决策和资源分配的优化问题,在用户间一对一匹配情况下提出了一种基于交替优化和匈牙利算法的高性能求解方案和一种基于重构线性化方法的低复杂度求解方案;针对一对多匹配情况提出了一种改进的贪婪算法。实验结果表明,在用户间一对一匹配时所提方案能够较对比方案降低最多12.6%的任务处理时延;一对多匹配情况下所提方案节省了5%的任务处理时延,即所提方案能有效保障用户端的时延需求。     

抗时延敏感性跨层自适应资源分配方案*

为了对抗多用户OFDM系统中用户实时业务对时延的敏感性,提出一种利用Hopfield神经网络(HNN)算法的跨层自适应资源分配方案。该方案设置用户调度优先级时同时考虑物理层的信道状态信息,及媒体接入层的用户队列状态信息和等待时间等;采用HNN算法,最大化系统容量的同时降低了平均时延和丢包率。仿真结果表明,相比于传统资源分配方案,该方案可以有效保障用户的服务质量,并提高了系统的整体性能。     

sensitivity minimization for delay systems

This paper announces results on the problem of feedback compensator design for ^∞ norm weighted sensitivity minimization when the plant contains a delay in the input. A complete solution is presented for the case of one pole/zero weighting function and a single-input/single-output plant for stable minimum-phase rational part. Generalizations and proofs will be published elsewhere.     

A modular algorithm for resource allocation

This paper concerns resource allocation in distributed message passing systems, i.e., the scheduling of accesses to exclusive system resources shared among concurrent processes. An efficient modular resource allocation algorithm is presented that uses any arbitrary resource allocation algorithm as a subroutine. It improves the performance of the subroutine by letting each process wait only for its currently conflicting processes, and therefore, allows more concurrency. For appropriate choices of the subroutine, we obtain resource allocation algorithms with the minimum worst case response times. Simulation studies were conducted which also indicate that on average, the obtained algorithms perform faster and require a smaller number of messages than other previously known algorithms, especially when resource contention among processes is high and the average time that a process remains in the critical region is large. Received: May 1997 / Accepted: May 1998     

A cross-layer resource allocation scheme for ICIC in LTE-Advanced

As a new technology, inter-eNB coordination has been included in LTE-Advanced study items. Moreover, the network architecture in LTE-Advanced system is modified to take into account coordinated transmission. In our study, we explore the problem of jointly optimizing the power level and scheduling of resource blocks for LTE-Advanced network based on orthogonal frequency division multiplexing (OFDM). We propose a distributed optimization scheme based on evolutionary potential games, and in the process of objective function modeling we employ the Lagrangian multiplier method to solve the constraint objective optimization problem. Then particle swarm optimization (PSO) method is adopted to find the optimal power allocation and scheduling for each resource block in the multi-cell framework. Numerical results prove that proposed algorithm notably improves the overall throughput, while user fairness is guaranteed. Importantly, additional computation and communication cost introduced by cross-layer optimization is also evaluated.     

A systematic approach for resource allocation in software projects

The completion of reliable software products within their expected time frame represents a major problem for companies that develop software applications. Today, the software industry continues to struggle with delivering products in a timely manner. A major cause for delays is the training time required for engineers and other personnel to acquire the necessary skills to complete software tasks. Therefore, it is important to develop systematic personnel assignment processes that consider complete skill sets of candidates to provide solutions that reduce training time. This paper presents a novel methodology to assign resources to tasks when optimum skill sets are not available. The methodology takes into account existing capabilities of candidates, required levels of expertise, and priorities of required skills for the task. A sample case is used to show the model capabilities, and the results are compared with the current resource assignment approach.     

一种容量最大化的OFDMA资源分配算法

针对功率受限的多用户OFDMA系统,提出了一种简化的子载波和功率分配算法,此算法在最大化系统容量的同时兼顾了用户间的公平性。算法首先依据当前的信道状况计算出各用户所需的载波数量,并分配子载波,然后以注水算法对各载波上的功率进行分配。仿真结果表明,以此算法对OFDMA的系统资源进行分配可显著提高系统的多项性能。     

A distributed resource allocation algorithm for many processes

Resource allocation is the problem that a process may enter a critical section CS of its code only when its resource requirements are not in conflict with those of other processes in their critical sections. For each execution of CS, these requirements are given anew. In the resource requirements, levels can be distinguished, such as e.g. read access or write access. We allow unboundedly many processes that communicate by reliable asynchronous messages and have finite memory. A simple starvation-free solution is presented. Processes only wait for one another when they have conflicting resource requirements. The correctness of the solution is argued with invariants and temporal logic. It has been verified with the proof assistant PVS.     

A macroeconomic model for resource allocation in large-scale distributed systems

In this paper we discuss an economic model for resource sharing in large-scale distributed systems. The model captures traditional concepts such as consumer satisfaction and provider revenues and enables us to analyze the effect of different pricing strategies upon measures of performance important for the consumers and the providers. We show that given a particular set of model parameters the satisfaction reaches an optimum; this value represents the perfect balance between the utility and the price paid for resources. Our results confirm that brokers play a very important role and can influence positively the market. We also show that consumer satisfaction does not track the consumer utility; these two important performance measures for consumers behave differently under different pricing strategies. Pricing strategies also affect the revenues obtained by providers, as well as, the ability to satisfy a larger population of users.     

一种基于QoE效用函数的资源分配算法

针对多用户MIMO-OFDM系统,立足业务体验方,给出了一种最大化用户QoE的资源分配算法。通过设计QoE效用函数,将用户QoE与系统QoS参数关联起来,在发送功率和目标误码率的约束条件下,以最大化用户平均QoE为目标,通过QoE效用函数获取用户当前时刻QoE增量,据此确定用户时频资源分配优先级,进而进行注水功率分配。仿真结果表明,该算法能够充分利用系统资源,有效提高用户平均QoE。     

A parallel hypercube algorithm for discrete resource allocation problems

It has been suggested that parallel processing helps in the solution of difficult discrete optimization problems, in particular, those problems that exhibit combinatorial search and require large-scale computations. By using a number of processors that are connected, coordinated and operating simultaneously, the solutions to such problems can be obtained much more quickly. The purpose of this paper is to propose an efficient parallel hypercube algorithm for the discrete resource allocation problem (DRAP). A sequential divide-and-conquer algorithm is first proposed. The algorithm is then modified for a parallel hypercube machine by exploiting its inherent parallelism. To allocate N units of discrete resources to n agents using a d-dimensional hypercube of p=2/sup d/ nodes, this parallel algorithm solves the DRAP in O((n/p+log/sub 2/p)N/sup 2/) time. A simulation study is conducted on a 32-node nCUBE/2 hypercube computer to present the experimental results. The speedup factor of the parallel hypercube algorithm is found to be more significant when the number of agents in the DRAP is much greater than the number of processing nodes on the hypercube. Some issues related to load balancing, routing, scalability, and mappings of the parallel hypercube algorithm are also discussed.     

A financial resource allocation model for regional water systems

The public water supply sector is facing significant external pressures for change from decreasing water resource availability, stricter water quality regulations, decreasing federal subsidies, increasing public scrutiny, decreasing financial health, and increasing infrastructure replacement costs. These forces necessitate greater accountability by community water systems (CWS) to their stakeholders. This paper presents a method for comparative efficiency analysis to improve the accountability of CWS to their stakeholders while maintaining the level of service. The method is achieved through three objectives, namely: (1) to construct standard efficiency metric parameters based on the techniques of data envelopment analysis; (2) to incorporate these uniform efficiency metric parameters into a transparent decision support system (DSS) based on the standard linear programming resource allocation problem; and (3) to utilize the DSS to determine the efficient allocation of limited budgetary resources among CWS operating as a regional water system (RWS). The paper is a significant departure, in three ways, from the current planning and management approach, which treats CWS as independent entities. First, it provides an open and transparent method for planning and management of CWS; second, it provides a uniform and consistent method for evaluating relative efficiencies across the CWS. Third, the DSS facilitates comparative efficiency analysis across the RWS, and guides financial allocation decisions among CWS operating as a RWS.     

A fair resource allocation protocol for multimedia wireless networks

Wireless networks are expected to support real-time interactive multimedia traffic and must be able, therefore, to provide their users with quality-of-service (QoS) guarantees. Although the QoS provisioning problem arises in wireline networks as well, mobility of hosts and scarcity of bandwidth makes QoS provisioning a challenging task in wireless networks. It has been noticed that multimedia applications can tolerate and gracefully adapt to transient fluctuations in the QoS that they receive from the network. The additional flexibility afforded by the ability of multimedia applications to tolerate and adapt to transient changes in QoS can be exploited by protocol designers to significantly improve the overall performance of wireless systems. This paper presents a fair resource allocation protocol for multimedia wireless networks that uses a combination of bandwidth reservation and bandwidth borrowing to provide network users with QoS in terms of guaranteed bandwidth, call blocking, and call dropping probabilities. Our view of fairness was inspired by the well-known max-min fairness allocation protocol for wireline networks. Simulation results are presented that compare our protocol to similar schemes.     

A population game approach for dynamic resource allocation problems

We consider a water distribution system as an example of resource allocation, and investigate the use of a population game for its control. We use a game-theoretic approach based on two evolutionary dynamics, the Brown–von Neumann–Nash and the Smith dynamics. We show that the closed-loop feedback interconnection of the water distribution system and the game-theoretic-based controller has a Nash equilibrium as an asymptotically stable equilibrium point. The stability analysis is performed based on passivity concepts and the Lyapunov stability theorem. An additional control subsystem is considered for disturbance rejection. We verify the effectiveness of the method by simulations under different scenarios.     

A deadlock avoidance approach for nonsequential resource allocation systems

The paper concentrates on the deadlock-avoidance problem for a class of resource allocation systems modeling manufacturing systems. In these systems, a set of production orders have to be executed in a concurrent way. To be executed, each step of each production order needs a set of reusable system resources. The competition for the use of these resources can lead to deadlock problems. Many solutions, from different perspectives, can be found in the literature for deadlock-related problems when the production orders have a sequential nature [sequential resource allocation systems (S-RAS)]. However, in the case in which the involved processes have a nonsequential nature [nonsequential resource allocation systems (NS-RAS)], the problem becomes more complex. In this paper, we propose a deadlock avoidance algorithm for this last class of systems. We also show the usefulness of the proposed solution by means of its application to a real system.     

一种启发式网络虚拟化资源分配算法

网络虚拟化是克服当前Internet僵化问题的一种重要方法,而资源分配是网络虚拟化技术的核心.为了平衡负载,本文提出了一种启发式资源分配算法HVNE.该算法充分利用虚拟节点和虚拟链路间的关联因素(虚拟网络拓扑),将节点映射和链路映射两个过程合并为一个统一的过程,改善了传统映射算法在拓扑稀疏时,算法性能不理想的问题.此外,HVNE允许同一个虚拟请求中的多个虚拟节点映射到同一个物理节点,节约了物理链路资源.HVNE将无向图的"k-区域划分优化"理论与传统的拓扑分割理论相结合,定义了虚拟拓扑间节点的关联因子,改进了传统的星形分割方法,使之能适用于大规模网络.仿真实验表明,HVNE在保证网络负载的情况下,获得了较好的虚拟请求接受率,较高的资源利用率和网络收益.     

A futures market-based model for dynamic network resource allocation

Management of telecommunication network requires quick, continuous and decentralized allocation of network bandwidth to various sorts of demands. So as to achieve the efficient network resource allocation, this paper describes a market-based model combining futures market with the agent-based approach. That is, utilization time is divided into many timeslots, and futures markets in hereafter use of bandwidth are opened. In our model, all market participants (software agents) observe only market prices and decide to buy or sell bandwidth trying to maximize their utilities over time so that they can secure enough network resources. The authors discuss network resource allocation through simulation using the proposed model. Masayuki Ishinishi, Ph.D.: He graduated from National Defense Academy in 1995 and 2000. He received the B.E. (1995) and M.E.(2000) degrees in computer science from National Institution for Academic Degrees (NIAD). He received his Ph.D. degree from Tokyo Institute of Technology in 2003. He has been a communications officer at Air Communications and Systems Wing in Japan Air Self-Defence Force (JASDF) since 2003. His research interests include information assurance, agent-based modeling and simulation, multi-agent system and market-based control. He is a member of IEEJ, IPSJ and JSAI. Yuhsuke Koyama, Ph.D.: He received the B.Econ., M.Econ., and Ph.D. degrees in economics from Kyoto University, in 1996, 1998, 2002, respectively. He has been a research associate of Tokyo Institute of Technology since 2002. His research field is evolutionary economics, mathematical sociology and experimental economics. He is a member of JAFEE, JAMS, JASESS and JASAG. Hiroshi Deguchi, Ph.D.: He received his Ph.D. degree in systems science from Tokyo Institute of Technology, in 1986. He also received the Dr. Econ. degree from Kyoto University in 2001. He has been a Professor of Tokyo Institute of Technology since 2002. His research field is evolutionary economics, computational organization theory, agent-based modeling, social system theory, gaming simulation, and philosophy of science. He is a member of SICE, JAMS, IPSJ, PHSC, JASAG and JAFEE. Hajime Kita, Ph.D.: He received the B.E., M.E., and Ph.D. degrees in electrical engineering from Kyoto University, in 1982, 1984, 1991, respectively. He has been a Professor of Kyoto University since 2003, His research field is systems science/engineering, and his research interests are evolutionary computation, neural networks and socio-economic analysis of energy systems, and agentbased modeling. He is a member of IEEJ, IEICE, ISCIE, JNNS, JSER, ORSJ and SICE.