SpringerBriefs in Computer Science Series Editors Stan Zdonik Peng Ning Shashi Shekhar Jonathan Katz Xindong Wu Lakhmi C. Jain David Padua Xuemin Shen Borko Furht V. S. Subrahmanian Martial Hebert Katsushi Ikeuchi Bruno Siciliano For furthervolumes: http://www.springer.com/series/10028 José Viterbo Markus Endler • Decentralized Reasoning in Ambient Intelligence 123 JoséViterbo MarkusEndler Department of Computer Science Department of Informatics Universidade FederalFluminense (UFF) PontifíciaUniversidade Católica do Niterói, RJ Rio deJaneiro (PUC-Rio) Brazil Rio deJaneiro, RJ Brazil ISSN 2191-5768 ISSN 2191-5776 (electronic) ISBN 978-1-4471-4167-9 ISBN 978-1-4471-4168-6 (eBook) DOI 10.1007/978-1-4471-4168-6 SpringerLondonHeidelbergNewYorkDordrecht LibraryofCongressControlNumber:2012938143 (cid:2)TheAuthor(s)2012 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyrightLawofthePublisher’slocation,initscurrentversion,andpermissionforusemustalways beobtainedfromSpringer.PermissionsforusemaybeobtainedthroughRightsLinkattheCopyright ClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problem Setting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Organization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Fundamental Concepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Ambient Intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Context-Awareness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Ontology-Based Context Model. . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 Context Reasoning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6 Rule-Based Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1 Distributed Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Gaia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 OWL-SF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 DRAGO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.5 P2P-DR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.6 P2PIS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 v vi Contents 4 Cooperative Reasoning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1 System Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Patterns of Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.1 User Side Reasoning. . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.2 Ambient Side Reasoning . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.3 Cooperative Reasoning . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Design Strategies for a Reasoning Service . . . . . . . . . . . . . . . . 38 4.3.1 Functional Attributes. . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.3.2 Non-Functional Attributes . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Cooperative Reasoning Formalization . . . . . . . . . . . . . . . . . . . 42 4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Our Approach for Cooperative Reasoning . . . . . . . . . . . . . . . . . . 47 5.1 Strategy for Rule-Based Context Reasoning . . . . . . . . . . . . . . . 47 5.1.1 Synchronous Interaction. . . . . . . . . . . . . . . . . . . . . . . . 48 5.1.2 Asynchronous Interaction. . . . . . . . . . . . . . . . . . . . . . . 51 5.1.3 Stability of Context Data. . . . . . . . . . . . . . . . . . . . . . . 53 5.2 Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3 Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.1 Synchronous Interaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.2 Asynchronous Interaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.1 Architecture Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.2 Ontology Management and Reasoning. . . . . . . . . . . . . . . . . . . 68 7.3 Context Model Service (CMS) . . . . . . . . . . . . . . . . . . . . . . . . 69 7.4 The Decentralized Reasoning Service (DRS) . . . . . . . . . . . . . . 70 7.5 Prototype Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 8 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.1 Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.2 Functional Test. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.3 Performance Test. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.3.1 Response Time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.3.2 Communication Traffic and Memory Footprint. . . . . . . . 87 8.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Reference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Contents vii 9 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 9.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 9.2 Why Two-Tier?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 9.3 Future Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Acronyms ABox Assertional box AmI Ambient Intelligence API Application programming interface CMS Context model service ConfComp Conference companion application ConfOrg Conference organizer application DL Description logics DRS Decentralized reasoning service DRS/A Ambient decentralized reasoning service DRS/D Device decentralized reasoning service FOL First order logic HTTP Hypertext transfer protocol IP Internet protocol J2ME Java 2 Platform, Micro edition MoCA Mobile collaboration architecture OWL Web ontology language P2P Peer-to-peer RDF Resource description framework SWRL Semantic Web Rule Language TBox Terminological box ix Chapter 1 Introduction Abstract In this chapter we clarify the motivations and purpose of this work. Initially, in the next section, in order to explain what instigated our research, we presentabriefoverviewaboutAmbientIntelligence,theresearchareainwhichlies theobjectofthiswork.InSect.1.2wediscuss,indetail,theproblemaddressedin this work and its main characteristics, setting the scope of the proposed approach. InSect.1.3weclearlydefinethegoalwepursuedduringourresearchwork.Finally, inSect.1.4wedescribethegeneralorganizationofthiswork. · · · Keywords Ambient Intelligence Ubiquitous computing Context-awareness · · Rule-basedreasoning Decentralizedreasoning Cooperativereasoning 1.1 Overview Ubiquitous computing features the seamless integration of computer systems into the everyday lives of users to provide information and functionalities anytime and anywhere[33].Itinvolvestheinteractionofdiversecomputationaldevicesaiming atprovidingservicestosupportusersinatransparentandcontinuousway.Forthis purpose,ubiquitouscomputingenvironmentsencompassdifferentkindsofsensors andmobiledevices(e.g.,PDAs,notebooks,smartphones),interconnectedthrougha combinationofseveralwirelessnetworktechnologies. Compared to traditional distributed systems, ubiquitous computing systems are characterizedbyanincreaseddynamismandheterogeneityofdevices,applications and services [29]. The underlying ubiquitous computing infrastructures are more complexandbringintotheforegroundissuessuchasusermobility,devicediscon- nections,joinandleaveofdevices,heterogeneousnetworks,aswellastheneedto integrate the physical environment with the computing infrastructure [18]. A soft- ware infrastructure to support the execution of ubiquitous applications has to be flexible and reactive to deal with the unpredictable, heterogeneous and dynamic J.ViterboandM.Endler,DecentralizedReasoninginAmbientIntelligence, 1 SpringerBriefsinComputerScience,DOI:10.1007/978-1-4471-4168-6_1, ©TheAuthor(s)2012 2 1 Introduction natureofthecomputingenvironmentsencounteredwhenusersmovearounddiffer- entlocations[21]. Inubiquitouscomputingenvironments,alargenumberofautonomoussoftware entities,i.e.,ubiquitousapplicationsandservices,worktogethertotransformphysi- calspacesintosmartandinteractiveenvironments[23].Insuchscenarios,newissues arebeginningtoarise,suchashowtoenableuserstocontinuouslyperformtheircom- putationaltaskswhilemovingthroughdifferentlocations[30],howtoenableusers tocooperatewhilelocatedindifferentplaces[22],orhowtopromotead-hoccoop- erationinsituationswhenagroupofuserssharingcommoninterestsunexpectedly meetatthesamelocationandneedtoengageincollectiveactivities[7]. Theapproachesandtechnologiesforsupportingthesenewwaysofworkingare stillunderinvestigation.Nevertheless,aparticularlyinterestingtrendinubiquitous computingisexploringtheAmbientIntelligence(AmI)paradigm,amultidisciplinary approach that aims at the integration of innovative sensing, communication and actuationtechnologiestocreatecomputer-mediatedenvironmentsthatsupportuser activities through specific services of the environment, provisioned with minimal userintervention[31]. AprominentexampleofanenvironmentenrichedwithAmIisa“smarthome”, a house equipped to bring advanced services to its users [3]. In such an environ- ment, several domestic artifacts and items can be enriched with sensors to gather information about their use and in some cases even to act independently without humanintervention[11].Forinstance,doorlocksinasmarthomecouldbecapable ofidentifyingpersonsandpermittinghands-freeopening,whichcouldbeauseful functionality for elderly, children and disabled people, as well as parents entering thehomewithbothhandsoccupiedwithcarryingshoppingbagsandguidingseveral childrenalong[15]. Another class of applications for AmI focuses on providing health monitoring andsupporttoindividualswithcognitiveorphysicalimpairments,aimingathelping these people to live independently by improving their access to a wide range of services and facilities [24]. For example, in the case of people at an early stage of senile dementia—the most frequent case being elderly people suffering from Alzheimer’sdisease—suchasystemcouldbetailoredtoensureappropriatecareat criticaltimesbymonitoringactivities,diagnosingrisksituations—suchasastroke orheartattack—andadvisingacarerordoctorincaseofneed[4]. TherehasbeenalsoalotofsignificantworkontheuseofAmItechnologiesforfa- cilitatinginteractioninacademicenvironments,suchasuniversities[26,27],research centers[12],conferencefacilities[25,9],i.e.,environmentswhereresearchers,teach- ers and students gather to engage in learning activities or participate in technical meetingsandpresentations.Insuchascenario,forinstance,afterdetectingthatall listedkeyparticipantsinapre-arrangedmeetinghavealreadyarrivedintherespec- tiveroom,anAmIservicecoulddimthelights,stopthebackgroundmusicandturn ontheprojectorinthatroom[10]. Essentially, an AmI system should be aware of the presence of people in the geographical space, perceive their needs and be able to autonomously personalize andmakeavailableservicestohelpuserstoperformtheirtasks[14].Forthatreason, 1.1 Overview 3 as a fundamental requirement, AmI applications must be capable of automatically responding to dynamic changes in the environment—such as a person entering or leavingaroom,asteepincreaseinthetemperatureindicatedbyasensororanew deviceconnectingtothelocalnetwork,etc—withnoneorminimalhumaninterfer- ence.Hence,applicationsexecutinginAmIsystemsareintrinsicallycontext-aware, i.e.,theyhavetostronglyrelyoncontextdatacollectedfromsensorsembeddedinto the environment and in the user’s devices to trigger adaptations at different levels, suchasinthewirelesscommunicationlinks,middlewareandapplicationservices, ortheuserinterfaces. AmIrequiresmiddlewaresupportforsoftwaredevelopment—anddeployment— capableofintegratinglargequantitiesofdifferentdevicesandsensorsandbuilding a programmable and auto-configurable infrastructure [23]. Several projects, e.g., Gaia[25],CoBrA[9],CHIL[28],etc.,havedevelopedprototypesofsuchenviron- ments, usually focusing on specific use cases, user tasks or application domains. Ingeneral, these middleware systems provide not only services to store,distribute andprocesscontextdatacollectedfromdifferentsources,butalsoservicesforrea- soning about context information, which may be based on logical inference using some type of derivation rule mechanism, e.g., first-order logic, descriptive logic, case-basedreasoningorfuzzylogic,orotherspecializedtechniques,suchasneural networks,Bayesiannetworks,etc[17]. InAmIsystems,asinmostubiquitoussystems,reasoningisnecessaryforseveral purposes.First,itisrequiredfordealingwiththeintrinsicimperfectionanduncer- tainty of context data [16]. In this way, reasoning allows the detection of possible errors,toestimatemissingvalues,todeterminethequality,precisionandvalidityof thecontextinformation.Itcouldbeused,forinstance,forresolvingconflictswhen differentpositioningmethodsinformdifferentlocationsforasameentity.Forexam- ple,whenauserforgetshisGPS-enabledsmartphoneinameetingroomandlogs intohisoffice’sworkstation[8],bothpiecesofinformationareprovidedtothemid- dleware. Second, reasoning may also be used for determining higher-level context information,i.e.,inferringnew,implicitpiecesofcontextinformationderivedfrom rawcontextdata.Forexample,reasoningcouldbeusedtodeterminethataseminar hasstartedbasedoninformationaboutthelocationofaspeakerinaconferenceroom andonthevolumeofnoiseproceedingfromthepulpitarea[29].Third,reasoningis fundamentalfortriggeringactionsoradaptationsaccordingtospecificsituationsthat maybemeaningfulandrelevanttosomeapplications[13].Forexample,reasoning could be used to identify that a user is busy when he is in a meeting room with at least one other colleague, his coffee cup and at least one of his colleagues’ coffee cupsareco-locatedinthesameroomandarewarm[19]. In most cases, context reasoning in AmI systems is very complex due to the dynamic, imprecise and ambiguous nature of context information and the need to process large volumes of data collected from a large number of context providers. This complexity is increased by the fact that in some conditions reasoning needs tobeperformedinadecentralizedwayinvolvingseveralentitiesofthesystem[5]. Decentralization takes the form of physical distribution of computing and sensor