ABSTRACT
A significant role in the Internet of Things (IoT) will be taken by mobile and low-cost unstable devices, which autonomously self-organize and introduce highly dynamic and heterogeneous scenarios for the deployment of distributed applications. This entails the devices to cooperate to dynamically find the suitable combination of their involvement so as to improve the system reliability while following the changes in their status.
Focusing on the above scenario, we propose a distributed algorithm for resources allocation that is run by devices that can perform the same task required by the applications, allowing for a flexible and dynamic binding of the requested services with the physical IoT devices. It is based on a consensus approach, which maximizes the lifetime of groups of nodes involved and ensures the fulfillment of the requested Quality of Information (QoI) requirements. Experiments have been conducted with real devices, showing an improvement of device lifetime of more than 20%, with respect to a uniform distribution of tasks.
PAST WORKS
The IoT consists of intelligent objects connected to the Internet, which cooperate to support the execution of complex applications and services. These objects are equipped with sensors and actuators, which provide context-awareness and enable them to gather, process and exchange data, in order to react to external stimuli. The need to represent, store, discover, search, exchange and manage the huge amount of information generated by the objects, motivated the development of semantic technologies.
REFERENCE SCENARIO AND PROBLEM STATEMENT
Figure 1. The reference IoT cloud architecture
We refer to the Cloud-based IoT model that relies on virtualization technologies and includes three levels, as shown in Figure 1. A Real World Object (RWO) is a device that has the ability to observe the real world phenomena and to perform measurements or operate on other objects. The Virtual Object is its digital representation and guides its involvement in the implementation of the deployed IoT applications, by providing a description of the RWO with also semantic enrichment. It also supports discovery and a mash up of services, improving the objects’ energy management efficiency, as well as addressing heterogeneity and scalability issues.
Figure 4. Location of the proposed algorithm into three typical IoT scenarios with reference to objects resource allocation
The decentralized approach introduced in our proposal has the advantage of being able to better follow the changes of RWOs status. This is possible when the VO task allocation functionalities are implemented in the RWOs. We base on the consideration that nodes that are assigned to the same task are usually located close to each other, and thus they can be able to form a connected group relying on short-range communication technologies, as shown in Figure 4a. In this scenario, RWOs reside in the same area and are characterized by sufficient computational power and energy. The optimization process can be distributed on RWOs, in such a way that the management of resources is as close as possible to the point where they are used.
THE RESOURCE ALLOCATION MODEL
Figure 5. Communication constraints for the consensus algorithm to converge
The proposed consensus protocol represents a discrete-time application of the finite-time discontinuous average-based consensus algorithm discussed, respectively, in for a network of connected continuous time integrators for networks of perturbed, and possibly switching, spanned-tree topologies. It follows that, as long as the stability of the linear part of the problem in Equation is preserved, the convergent properties discussed in are in force.
THE PROPOSED IOT SYSTEM
In this section, the whole IoT resource allocation system proposed in this paper is described. Algorithm 1 provides the pseudo-code for the whole process. As soon as the service level receives a request for a task, it translates it into computer language, generating the query Qk, which is sent to the VO level. Based on Qk, the VO level finds the VO Information Model that best fits the characteristics required by Qk. The VO level than starts a search for the set Sk of VO instances that correspond to the required VO Information Model, i.e., the set of VOs that can respond to the query. Then, the VO level selects one of the VOs to whom forwarding the request, i.e., the candidate VO VO0.
EXPERIMENTS
Figure 6. Example plot for algorithm convergence
Figure 6 shows in an explanatory example how three devices reach consensus for five different tasks. Each line style is associated with a different device. Whenever a new task is activated, the devices that can perform that task initiate the consensus process. The initialization instants correspond to the peaks in the figures and are marked by the respective label. It is possible to see how, for each task, the convergence is reached in just a few steps. On average, the algorithm takes only less than seven steps per task to converge. For each task activation, the lifetime values of the three devices converge, as the frequency of execution is distributed in an optimized manner to reach the reference frequency.
Figure 9. Average values of convergence time
The behaviour of the algorithm was also evaluated from the time performance point of view. The convergence times measured during the testing phase and related confidence interval are shown in Figure 9 as a function of the number of tasks to be assigned. It goes from 440 ms when only two tasks are assigned to 2.14 s when 10 tasks are assigned, with an average convergence time of 214 ms per task.
CONCLUSIONS
We proposed the use of VOs to control and manage the heterogeneous resource-constrained objects that characterize the IoT, so as to find those that are able to perform some given tasks ensuring the required QoI. We then introduced a consensus-based algorithm where the resources of these objects, specifically their residual battery charge, are assigned to the execution of tasks so that the workload is distributed in a fair way. Tests on real devices showed that we can reach an average lifetime improvement of more than 20% using up to 10 devices, which decreases when the amount of available resources decreases.
Source: University of Cagliari
Authors: Virginia Pilloni | Luigi Atzori | Matteo Mallus