Online Context-Adaptive Energy-Aware Security Allocation in Mobile Devices: A Tale of Two Algorithms

Cryptographic operations involved in securing communications are computationally intensive and contribute to energy drain in mobile devices. Thus, varying the level of security according to the user’s location may provide a convenient solution to energy management. Context-adaptive energy-aware security allocation for mobile devices is modeled in this paper as a combinatorial optimization problem. The goal is to allocate security levels effectively so that user utility is maximized while bounding the maximum energy cost to a constant E. Although the offline version of the problem has been previously studied in the literature where both the security levels and the locations to which a user may travel to is known a priori, this is the first work that formulates and solves an online version of the problem where the locations may be known a priori but the security levels are revealed only upon reaching the locations. We provide two different algorithms for the solution of this online problem by mapping it to the online multi-choice knapsack problem. We study competitive ratios of our two algorithms by comparing the solutions they yield to the optimal solution obtained for the corresponding offline problem. We also present simulation experiments on realistic datasets to validate the scalability and efficiency of our approaches (taking in order of milliseconds for up to 100 locations and providing near-optimal competitive ratios).