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

Huang, Pei-Qiu, Wang, Yong and Wang, Kezhi (2021) A Divide-and-Conquer Bilevel Optimization Algorithm for Jointly Pricing Computing Resources and Energy in Wireless Powered MEC. IEEE Transactions on Cybernetics. pp. 1-13. ISSN 2168-2267 (In Press)

[img]
Preview
Text
DACBO.pdf - Accepted Version

Download (6MB) | Preview
Official URL: https://doi.org/10.1109/TCYB.2021.3103840

Abstract

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.

Item Type: Article
Additional Information: Funding information: This work was supported by the National Natural Science Foundation of China under Grants 61976225.
Uncontrolled Keywords: Bilevel optimization, differential evolution, divide and conquer, mobile edge computing (MEC), variable neighborhood search (VNS)
Subjects: G400 Computer Science
G500 Information Systems
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Rachel Branson
Date Deposited: 13 Dec 2021 12:02
Last Modified: 13 Dec 2021 12:15
URI: http://nrl.northumbria.ac.uk/id/eprint/47967

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics