A Divide-and-Conquer Bilevel Optimization Algorithm for Jointly Pricing Computing Resources and Energy in Wireless Powered MEC

This article investigates a wireless-powered mobile edge computing (MEC) system, where the service provider (SP) provides the device owner (DO) with both computing resources and energy to execute tasks from Internet-of-Things devices. In this system, SP first sets the prices of computing resources and energy whereas DO then makes the optimal response according to the given prices. In order to jointly optimize the prices of computing resources and energy, we formulate a bilevel optimization problem (BOP), in which the upper level generates the prices of computing resources and energy for SP and then under the given prices, the lower level optimizes the mode selection, broadcast power, and computing resource allocation for DO. This BOP is difficult to address due to the mixed variables at the lower level. To this end, we first derive the relationships between the optimal broadcast power and the mode selection and between the optimal computing resource allocation and the mode selection. After that, it is only necessary to consider the discrete variables (i.e., mode selection) at the lower level. Note, however, that the transformed BOP is still difficult to solve because of the extremely large search space. To solve the transformed BOP, we propose a divide-and-conquer bilevel optimization algorithm (called DACBO). Based on device status, task information, and available resources, DACBO first groups tasks into three independent small-size sets. Afterward, analytical methods are devised for the first two sets. As for the last one, we develop a nested bilevel optimization algorithm that uses differential evolution and variable neighborhood search (VNS) at the upper and lower levels, respectively. In addition, a greedy method is developed to quickly construct a good initial solution for VNS. The effectiveness of DACBO is verified on a set of instances by comparing with other algorithms.