An Efficient Resource Allocation Approach based on a Genetic Algorithm for Composite Services in IoT Environments

As various types of Internets of Things (IoT) are deployed in a wide range of areas, the need arises to utilize various IoT resources dynamically to accomplish user tasks. We call this environment an urban-scale IoT environment, where various IoT resources that are necessary to accomplish user tasks are directly connected to each other via users' mobile devices, such as their smart phones. IoT resources are utilized as resources with which to run a composite service that supports user tasks. In this urban-scale IoT environment, it is essential to create efficient binding between a service and an IoT resource so as to execute a composite service for a task successfully. In this paper, we propose a service resource allocation approach which minimizes data transmissions between users' mobile devices and which effectively deal with the constraints of these types of environments. We transformed the resource allocation problem into a variant of the degree-constrained minimum spanning tree problem and applied a genetic algorithm to reduce the time needed to produce a near-optimal solution. We also defined a fitness function and an encoding scheme to apply the genetic algorithm in an efficient manner. The proposed approach shows a 97% success rate on average when used to find near-optimal solutions. In addition, it takes significantly less time than the brute force approach.