Genetic Algorithm Based Combinatorial Auction Method for Multi-Robot Task Allocation

An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.

Privacy-Aware Service Subscription in People-Centric Sensing:A Combinatorial Auction Approach

With the emergence of ambient sensing technologies which combine mobile crowdsensing and Internet of Things,large amount of people-centric data can be obtained and utilized to build people-centric services.Note that the service quality is highly related to the privacy level of the data.In this paper,we investigate the problem of privacy-aware service subscription in people-centric sensing.An efficient resource allocation framework using a combinatorial auction(CA)model is provided.Specifically,the resource allocation problem that maximizes the social welfare in view of varying requirements of multiple users is formulated,and it is solved by a proposed computationally tractable solution algorithm.Furthermore,the prices of allocated resources that winners need to pay are figured out by a designed scheme.Numerical results demonstrate the effectiveness of the proposed scheme.

Combinatorial auction algorithm for project portfolio selection and scheduling to maximize the net present value

Scheduling projects at the activity level increases the complexity of decision making of project portfolio selection but also expands the search space to include better project portfolios. An integer programming model is formulated for the project portfolio selection and scheduling problem. An iterative multi-unit combinatorial auction algorithm is proposed to select and schedule project portfolios through a distributed bidding mechanism. Two price update schemes are designed to adopt either a standard or an adaptive Walrasian tatonnement process. Computational tests show that the proposed auction algorithm with the adaptive price update scheme selects and schedules project portfolios effectively and maximizes the total net present value. The price profile generated by the algorithm also provides managerial insights for project managers and helps to manage the scarce resources efficiently.

Using a combinatorial auction-based approach for simulation of cooperative rescue operations in disaster relief

In practice,we experience low efficiency of search and rescue(SAR)frequently in disaster relief.Here,we will optimize the SAR through agent-based simulation.In the kind of cases described here,rescue teams are characterized by different capabilities,and the tasks often require different capabilities to complete.To this end,a combinatorial auction-based task allocation scheme is used to develop a cooperative rescue plan for the heterogeneous rescue teams.Then,we illustrate the proposed cooperative rescue plan in different scenarios with the case of landslide disaster relief.The simulation results indicate that the combinatorial auction-based cooperative rescue plan would increase victims’relative survival probability by 13.8–16.3%,increase the ratio of survivors getting rescued by 10.7–12.7%,and decrease the average elapsed time for one site getting rescued by 19.0–26.6%.The proposed rescue plan outperforms the rescue plan based on the F-Max-Sum a little bit.The robustness analysis shows that the proposed rescue plan is relatively reliable on condition that both the search radius and scope of cooperation are larger than thresholds.Furthermore,we have investigated how the number of rescue teams influences the rescue efficiency.

A Combinatorial Auction-Based Collaborative Cloud Services Platform

In this paper, we present a novel, dynamic collaboration cloud platform in which a Combinatorial Auction（CA）-based market model enables the platform to run effectively. The platform can facilitate expense reduction and improve the scalability of the cloud, which is divided into three layers： The user-layer receives requests from end-users, the auction-layer matches the requests with the cloud services provided by the Cloud Service Provider（CSP）, and the CSP-layer forms a coalition to improve serving ability to satisfy complex requirements of users.In fact, the aim of the coalition formation is to find suitable partners for a particular CSP. However, identifying a suitable combination of partners to form the coalition is an NP-hard problem. Hence, we propose approximation algorithms for the coalition formation. The Breadth Traversal Algorithm（BTA） and Revised Ant Colony Algorithm（RACA） are proposed to form a coalition when bidding for a single cloud service in the auction. The experimental results show that RACA outperforms the BTA in bid price. Other experiments were conducted to evaluate the impact of the communication cost on coalition formation and to assess the impact of iteration times for the optimal bidding price. In addition, the performance of the market model was compared to the existing CA-based model in terms of economic efficiency.

Negotiation Based Combinatorial Double Auction Mechanism in Cloud Computing

Cloud computing is a demanding business platform for services related to the field of IT.The goal of cloud customers is to access resources at a sustainable price,while the goal of cloud suppliers is to maximize their services utilization.Previously,the customers would bid for every single resource type,which was a limitation of cloud resources allocation.To solve these issues,researchers have focused on a combinatorial auction in which the resources are offered by the providers in bundles so that the user bids for their required bundle.Still,in this allocation mechanism,some drawbacks need to be tackled,such as due to the lower average bid price the users are dropped from the auction process.To solve this problem,we proposed a“Negotiation based Combinatorial Double Auction Mechanism for Resource Allocation(N-CDARA)in cloud computing”.The proposed method negotiates with dropped users.Lower average bid price users are asked by our proposed mechanism to increase their bids,as by the quoted bids they will be dropped by the auctioneer.Most of the users that are close to winning accept the proposal and increase their bid prices.The proposed mechanism is implemented in a CloudSim simulation toolkit.Results are compared with the latest model and performance study shows that in our proposed scheme more users win and get their requested services and the utilization of offered services is increased up to 18.4%than the existing schemes.

Low Complexity Joint Spectrum Resource and Power Allocation for Ultra Dense Networks

In this paper,we propose a low complexity spectrum resource allocation scheme cross the access points(APs)for the ultra dense networks(UDNs),in which all the APs are divided into several AP groups(APGs)and the total bandwidth is divided into several narrow band spectrum resources and each spectrum resource is allocated to APGs independently to decrease the interference among the cells.Furthermore,we investigate the joint spectrum and power allocation problem in UDNs to maximize the overall throughput.The problem is formulated as a mixed-integer nonconvex optimization(MINCP)problem which is difficult to solve in general.The joint optimization problem is decomposed into two subproblems in terms of the spectrum allocation and power allocation respectively.For the spectrum allocation,we model it as a auction problem and a combinatorial auction approach is proposed to tackle it.In addition,the DC programming method is adopted to optimize the power allocation subproblem.To decrease the signaling and computational overhead,we propose a distributed algorithm based on the Lagrangian dual method.Simulation results illustrate that the proposed algorithm can effectively improve the system throughput.

Pricing in combinatorial double auction-based grid allocation model

This article proposes a novel grid resource allocation model, in which the users and the grid service providers participate in the combinatorial double auction for the resource allocation. To obtain the detailed resource allocation status and the price information, a novel pricing algorithm is designed for the allocation model. Simulation results demonstrate that the proposed algorithm completes the resource allocation and pricing efficiently, and exhibits incentive compatible characteristic. Moreover, users with the higher average price and providers with the lower average price get compensation during the pricing process.

A strategy-proof auction mechanism for service composition based on user preferences

Service composition is an effective method of combining existing atomic services into a value-added service based on cost and quality of service(QoS).To meet the diverse needs of users and to offer pricing services based on QoS,we propose a service composition auction mechanism based on user preferences,which is strategy-proof and can be beneficial in selecting services based on user preferences and dynamically determining the price of services.We have proven that the proposed auction mechanism achieves desirable properties including truthfulness and individual rationality.Furthermore,we propose an auction algorithm to implement the auction mechanism,and carry out extensive experiments based on real data.The results verify that the proposed auction mechanism not only achieves desirable properties,but also helps users find a satisfactory service composition scheme.