Power Aware Real Time Scheduling in Constrained Devices

Real-time scheduling algorithms, such as Rate Monotonic and Earliest Deadline First, guarantee that calculations are performed within a pre-defined time. As many real-time systems operate on limited battery power, these algorithms have been enhanced with power-aware properties. In this thesis, 13 power-aware real-time scheduling algorithms for processor, device and system-level use are explored.

Dessy : desktop search and synchronization

Current smartphones have a storage capacity of several gigabytes. More and more information is stored on mobile devices. To meet the challenge of information organization, we turn to desktop search. Users often possess multiple devices, and synchronize (subsets of) information between them. This makes file synchronization more important. This thesis presents Dessy, a desktop search and synchronization framework for mobile devices. Dessy uses desktop search techniques, such as indexing, query and index term stemming, and search relevance ranking. Dessy finds files by their content, metadata, and context information. For example, PDF files may be found by their author, subject, title, or text. EXIF data of JPEG files may be used in finding them. User–defined tags can be added to files to organize and retrieve them later. Retrieved files are ranked according to their relevance to the search query. The Dessy prototype uses the BM25 ranking function, used widely in information retrieval. Dessy provides an interface for locating files for both users and applications. Dessy is closely integrated with the Syxaw file synchronizer, which provides efficient file and metadata synchronization, optimizing network usage. Dessy supports synchronization of search results, individual files, and directory trees. It allows finding and synchronizing files that reside on remote computers, or the Internet. Dessy is designed to solve the problem of efficient mobile desktop search and synchronization, also supporting remote and Internet search. Remote searches may be carried out offline using a downloaded index, or while connected to the remote machine on a weak network. To secure user data, transmissions between the Dessy client and server are encrypted using symmetric encryption. Symmetric encryption keys are exchanged with RSA key exchange. Dessy emphasizes extensibility. Also the cryptography can be extended. Users may tag their files with context tags and control custom file metadata. Adding new indexed file types, metadata fields, ranking methods, and index types is easy. Finding files is done with virtual directories, which are views into the user’s files, browseable by regular file managers. On mobile devices, the Dessy GUI provides easy access to the search and synchronization system. This thesis includes results of Dessy synchronization and search experiments, including power usage measurements. Finally, Dessy has been designed with mobility and device constraints in mind. It requires only MIDP 2.0 Mobile Java with FileConnection support, and Java 1.5 on desktop machines.

Describing and validating functional requirements as use cases

Requirements engineering is an important phase in software development where customer's needs and expectations are transformed into a software requirements specification. The requirements specification can be considered as an agreement between the customer and the developer where both parties agree on the expected system features and behaviour. However, requirements engineers must deal with a variety of issues that complicate the requirements process. The communication gap between the customer and the developers is among typical reasons for unsatisfactory requirements. In this thesis we study how the use case technique could be used in requirements engineering in bridging the communication gap between the customer and development team. We also discuss how a use case description can be use cases can be used as a basis for acceptance test cases.

Normalisoitu kompressioetäisyys : katsaus sovelluksiin

Normalisoitu kompressioetäisyys NCD on mitta kahden dataobjektin välisen keskinäisen etäisyyden laskemiseen. Etäisyysmitta kuvaa sitä, kuinka paljon kahdessa vertailtavassa dataobjektissa on samankaltaisuutta. NCD on normalisoidun informaatioetäisyyden NID:n approksimointi. NID perustuu dataobjektien Kolmogorov-kompleksisuuteen. Dataobjektit kuvataan bittijonoina ja niissä on sitä enemmän samankaltaisuutta, mitä enemmän ne sisältävät keskinäisinformaatiota. NID on universaali siinä mielessä, että se poikkeaa korkeintaan vakiotermin verran optimaalisesta menetelmästä. Vakiotermi ei puolestaan riipu lainkaan vertailtavista dataobjekteista. NCD approksimoi NID:tä reaalimaailman tiivistäjillä, minkä vuoksi se on vain näennäisuniversaali, mutta siitä huolimatta käyttökelpoinen. NCD:n nojalla muodostetaan datasta etäisyysmatriisi, jonka avulla alkiot voidaan ryvästää ja havainnollistaa erityisen kvartettimenetelmän avulla puurakenteeseen. Menetelmää on sovellettu lupaavasti monella alalla. Tutkielma käy läpi menetelmän taustalla olevan teorian ja esittelee sen sovelluskohteita sekä paneutuu erityisesti stemmatologiseen Heinrichi-aineistoon, jota testataan CompLearn-ilmaisohjelmalla, joka tuottaa etäisyysmatriisin sekä muodostaa puurakenteen kvartettimenetelmällä.

Semanttinen tiedonhaku

Perinteisillä tiedonhakumenetelmillä ei aina tavoiteta riittävän hyvin tekstien merkitystasoa. Tutkielman aiheena olevan semanttisen tiedonhaun tarkoituksena onkin päästä paremmin kä-siksi sanojen ilmaisemiin merkityksiin. Tämä tapahtuu käyttämällä hyväksi itse tekstiin tai sen esitys-/tallennusrakenteisiin tuotettua semanttista metatietoa. Tutkielmassa tarkastellaan lähemmin kahteen ryhmään kuuluvia semanttisia hakumenetelmiä. Toisen ryhmän muodostavat XML-tekstidokumenttien ominaisuuksia hyödyntävät, toisen taas semanttisen webin mahdollisuuksiin perustuvat järjestelmät. Lisäksi tutkielmassa luonnostellaan ideaalinen semanttinen tiedonhakujärjestelmä, johon tarkasteltuja järjestelmiä verrataan. Vertailussa todetaan, että lähes kaikki ideaalisen hakujärjestelmän piirteet tulevat jossain muodossa toteutetuiksi, joskaan eivät yhdessäkään järjestelmässä samalla kertaa. Semanttisilta hakuominaisuuksiltaan monipuolisimmaksi osoittautuu XML-perustainen SphereSearch-hakukone, joka esimerkiksi sallii käsitehaut ja kykenee muodostamaan vastauselementeistä dokumenttirajat ylittäviä kokonaisuuksia. Toisaalta kaikki tarkastellut järjestelmät noudattavat semanttisen tiedonhaun perusperiaatetta, jonka mukaan etsityn merkityssisällön tavoittamiseksi ei riitä pelkkä hakutermien paikallisten esiintymien löytäminen kohdeaineistosta. Tyypillisimmin periaate on toteutettu ottamalla tiedollisen yksikön (XML-elementin tai semanttisen webin ontologian mukaisen ilmentymäsolmun) relevanssia arvioitaessa huomioon myös siihen rakenteellisesti kytkeytyneiden yksiköiden sisältö ja näiden kytkösten laatu.

Architectural Solutions for Mobile RFID Services on Internet of Things

Mobile RFID services for the Internet of Things can be created by using RFID as an enabling technology in mobile devices. Humans, devices, and things are the content providers and users of these services. Mobile RFID services can be either provided on mobile devices as stand-alone services or combined with end-to-end systems. When different service solution scenarios are considered, there are more than one possible architectural solution in the network, mobile, and back-end server areas. Combining the solutions wisely by applying the software architecture and engineering principles, a combined solution can be formulated for certain application specific use cases. This thesis illustrates these ideas. It also shows how generally the solutions can be used in real world use case scenarios. A case study is used to add further evidence.

Julkisen avaimen menetelmä ja ETSI:n MSS-määritys

Julkisen avaimen menetelmä on ollut käytössä Suomessa jo jonkin aikaa esimerkiksi HST-korteilla, joissa on Väestörekisterikeskuksen myöntämä kansalaisvarmenne. Kansalaisvarmenteella voidaan tehdä mm. laillisesti sitovia digitaalisia allekirjoituksia ja salata sähköpostia. Viime aikoina myös eri matkapuhelinoperaattorit ovat alkaneet tarjota mobiilia kansalaisvarmennetta, jossa salainen avain on sijoitettu matkapuhelimen SIM-kortille. Tässä pro gradu -työssä kuvataan ensin julkisen avaimen menetelmä ja sen käyttöalueet. Lisäksi mainitaan muutamia julkisen avaimen algoritmeja ja julkisen avaimen menetelmiin liittyviä ongelmia. Tämän jälkeen kuvataan ETSI:n MSS-määritys. ETSI:n MSS-määritys kuvaa palvelun rajapinnan, jossa loppukäyttäjältä pyydetään digitaalinen allekirjoitus. Lopuksi kuvataan Valimo Wireless Oy:n toteutus ETSI:n MSS-määrityksestä.

Harmoninen tonaalisuus ja nuottien hakumenetelmät

Musiikkitiedonhaku on poikkitieteellinen ala, jonka mielenkiintoisimpia sovelluksia ovat hyräilykyselykoneet. Symbolisen eli nuotteihin perustuvan musiikkitiedonhaun ydinkysymyksiä ovat, milloin sävelkulut muistuttavat jossakin musiikillisessa mielessä toisiaan, ja miten tätä voidaan mallinta ja mitata. Jos MIDI-muotoisesta nuottitietokannasta etsitään sävelkulun likimääräisiä esiintymiä, tarvitaan etäisyysmitta, joka kertoo, millaiset muunnokset säilyttävät sävelkulun oleellisesti samana ja mitkä ovat pieniä tai suuria virheitä. Tässä tutkielmassa perehdytään musiikin tonaaliseen ulottuvuuteen. Tonaalisuuden perustavanlaatuinen ilmenemismuoto länsimaisessa musiikissa ovat sävellajit. Sävellajit voidaan tunnistaa melko luotettavasti dynaamiseen ohjelmointiin perustuvalla algoritmilla, jossa verrataan nuottisegmentissä esiintyvien sävelten joukkoa eri sävellajien mukaisiin odotuksiin. Havaitaan, että harmonisen analyysin kannalta menetelmä on kuitenkin hieman epätarkka, koska siinä ei huomioida harmonisten sointujen vuorovaikutuksen merkitystä. Sävelkulkujen etäisyysvertailujen kannaltaa kriittisin tonaalisuuden ominaisuus on ihmisen sävelkorvan suhteellisuus, mikä tarkoittaa, että sävelten absoluuttiset korkeudet aistitaan keskimäärin melko epätarkasti, mutta sävelten väliset korkeuserot aistitaan tarkasti. Tutkielmassa esitetään sävelasteaakkosto, jonka merkkijonoina yksiääniset sävelkulut voidaan esittää vaihtoehtoisilla tavoilla suhteutettuina, ja pohditaan yleisesti sävelten suhteiden mittaamiseen liittyviä ongelmia sekä yksiäänisten sävelkulkuhakujen että polyfonisten ja homofonisten sävelkudosvertailujen kannalta.

Free/Open Source Software Development : Results and Research Methods

Free and open source software development is an alternative to traditional software engineering as an approach to the development of complex software systems. It is a way of developing software based on geographically distributed teams of volunteers without apparent central plan or traditional mechanisms of coordination. The purpose of this thesis is to summarize the current knowledge about free and open source software development and explore the ways on which further understanding on it could be gained. The results of research on the field as well as the research methods are introduced and discussed. Also adapting software process metrics to the context of free and open source software development is illustrated and the possibilities to utilize them as tools to validate other research are discussed.

Monilinjaus fylogeniapuun ohjaamana

Suoraviivainen monilinjauksen toteutus vie eksponentiaalisesti aikaa ja muistia. Siksi on kehitetty monia heuristisia menetelmiä. Tässä paperissa keskityn yhteen heurististen monilinjausmenetelmien luokkaan, progressiiviseen fylogeniapuun mukaan etenevään monilinjaukseen. Menetelmä on kehitetty globaaliin linjaukseen, lokaalin linjaamisen puolelta löytyy joitain samansuuntaisia menetelmiä. Olen soveltanut progressiivisen fylogeniapuun ohjaaman monilinjauksen lokaalisti geenien säätelyalueita etsivään EELohjelmaan. Koska selkeästi hyvää tapaa yleistää EELohjelman käyttämä linjauksen pisteytys ei ole, olen toteuttanut progressiiviseen monilinjaukseeni kolme erilaista pisteytystä: parien summa, parilinjauksen pisteytyksestä yleistetty pisteytys sekä edustavia sekvenssejä käyttävä, puun mukainen pisteytys. Monilinjauksen mahdollistama useamman sekvenssin käyttäminen tarkentaa parilinjauksella löydettyjä säätelyalueita ja vahvistaa säilyvien alueiden merkitystä.

An XML Messaging Service for Mobile Devices

In recent years, XML has been accepted as the format of messages for several applications. Prominent examples include SOAP for Web services, XMPP for instant messaging, and RSS and Atom for content syndication. This XML usage is understandable, as the format itself is a well-accepted standard for structured data, and it has excellent support for many popular programming languages, so inventing an application-specific format no longer seems worth the effort. Simultaneously with this XML's rise to prominence there has been an upsurge in the number and capabilities of various mobile devices. These devices are connected through various wireless technologies to larger networks, and a goal of current research is to integrate them seamlessly into these networks. These two developments seem to be at odds with each other. XML as a fully text-based format takes up more processing power and network bandwidth than binary formats would, whereas the battery-powered nature of mobile devices dictates that energy, both in processing and transmitting, be utilized efficiently. This thesis presents the work we have performed to reconcile these two worlds. We present a message transfer service that we have developed to address what we have identified as the three key issues: XML processing at the application level, a more efficient XML serialization format, and the protocol used to transfer messages. Our presentation includes both a high-level architectural view of the whole message transfer service, as well as detailed descriptions of the three new components. These components consist of an API, and an associated data model, for XML processing designed for messaging applications, a binary serialization format for the data model of the API, and a message transfer protocol providing two-way messaging capability with support for client mobility. We also present relevant performance measurements for the service and its components. As a result of this work, we do not consider XML to be inherently incompatible with mobile devices. As the fixed networking world moves toward XML for interoperable data representation, so should the wireless world also do to provide a better-integrated networking infrastructure. However, the problems that XML adoption has touch all of the higher layers of application programming, so instead of concentrating simply on the serialization format we conclude that improvements need to be made in an integrated fashion in all of these layers.

TCP Performance with Vertical Handoff

With the proliferation of wireless and mobile devices equipped with multiple radio interfaces to connect to the Internet, vertical handoff involving different wireless access technologies will enable users to get the best of connectivity and service quality during the lifetime of a TCP connection. A vertical handoff may introduce an abrupt, significant change in the access link characteristics and as a result the end-to-end path characteristics such as the bandwidth and the round-trip time (RTT) of a TCP connection may change considerably. TCP may take several RTTs to adapt to these changes in path characteristics and during this interval there may be packet losses and / or inefficient utilization of the available bandwidth. In this thesis we study the behaviour and performance of TCP in the presence of a vertical handoff. We identify the different handoff scenarios that adversely affect TCP performance. We propose several enhancements to the TCP sender algorithm that are specific to the different handoff scenarios to adapt TCP better to a vertical handoff. Our algorithms are conservative in nature and make use of cross-layer information obtained from the lower layers regarding the characteristics of the access links involved in a handoff. We evaluate the proposed algorithms by extensive simulation of the various handoff scenarios involving access links with a wide range of bandwidth and delay. We show that the proposed algorithms are effective in improving the TCP behaviour in various handoff scenarios and do not adversely affect the performance of TCP in the absence of cross-layer information.