Distributed rule-based resource allocation in smart spaces
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2011
Department
Major/Subject
Tietojenkäsittelyteoria
Mcode
T-119
Degree programme
Language
en
Pages
vi + 67
Series
Abstract
A smart space is an abstract and distributed entity composed of interacting digital devices. Creation of smart spaces whose components can share information interoperable is one of the challenges in the field of ubiquitous computing. Smart-M3 is an implementation that provides interoperability in smart spaces using the ideas of Semantic Web. In these smart spaces, at any given time, there are resources as well as consumers that wish to use those resources. Since these resources, or capabilities, have limited capacities, some mechanism of resource allocation must be devised. Unfortunately, as the number of resources and their consumers grow, doing resource allocation efficiently demands more computation. Moreover, allocating resources in a competitive environment could also give rise to deadlocks in the system in which each user involved in the deadlock is unable to proceed for an indefinite period of time. Therefore, a strategy to detect and eliminate these deadlocks also needs to be in place. Deadlock handling also requires more computation time and memory as the size of the smart space increases. In this thesis, we present a distributed approach to resource allocation and deadlock handling in smart spaces using Answer Set Programming (ASP) techniques. ASP is a declarative programming paradigm and it is a useful way of defining policies for capabilities to resolve conflicts since policies can be expressed in terms of rules. A centralized approach using a single ASP rule-engine was already discussed, along with its shortcomings in previous work. The centralized approach fails to scale efficiently for larger smart spaces. Distributing resource allocation and deadlock detection however, introduces complexities that arise due to splitting the problem instance into several smaller instances. This thesis extends the centralized approach and applies it to a distributed setting by catering for these complexities using two approaches: distributed deadlock detection and deadlock prevention. Other than merely devising strategies to distribute the problem -and to some extent because of it we also introduce modularity in the new approach resulting in a more structured and optimized solution. Several comparisons between the central and distributed approaches are given in terms of execution time and amount of traffic. Our results show that the new distributed approach exploits parallelism and is efficient to be applied for smart spaces of larger sizes.Description
Supervisor
Janhunen, TomiThesis advisor
Luukkala, VesaKeywords
smart spaces, ubiquitous computing, answer set programming, resource allocation, deadlock detection, deadlock resolution