Distributed rule-based resource allocation in smart spaces

Thumbnail Image

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

Authors

Date

2011

Department

Tietotekniikan laitos

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, Tomi

Thesis advisor

Luukkala, Vesa

Keywords

smart spaces, ubiquitous computing, answer set programming, resource allocation, deadlock detection, deadlock resolution

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-2020122358350

Collections

[dipl] Perustieteiden korkeakoulu / SCI