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.