Advances in mobile computing capabilities and an increasing number of Internet of Things (IoT) devices have enriched the possibilities of the IoT but have also increased the cognitive load required of IoT users. Existing context-aware systems provide various levels of automation in the IoT. Many of these systems adaptively take decisions on how to provide services based on assumptions made a priori. The approaches are difficult to personalize to an individual's dynamic environment, and thus today's smart IoT spaces often demand complex and specialized interactions with the user in order to provide tailored services. We propose rIoT, a framework for seamless and personalized automation of human-device interaction in the IoT. rIoT leverages existing technologies to operate across heterogeneous devices and networks to provide a one-stop solution for device interaction in the IoT. We show how rIoT exploits similarities between contexts and employs a decision-tree like method to adaptively capture a user's preferences from a small number of interactions with the IoT space. We measure the performance of rIoT on two real-world data sets and a real mobile device in terms of accuracy, learning speed, and latency in comparison to two state-of-the-art machine learning algorithms.

Recent years have seen the emergence of wireless cyber-physical systems that must support real-time queries of physical environments through wireless sensor networks. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in wireless sensor networks. First, we show that there is an inherent tradeoff between latency and real-time capacity in query scheduling. We then present three new real-time schedulers. The nonpreemptive query scheduler supports high real-time capacity but cannot provide low response times to high-priority queries due to priority inversions. The preemptive query scheduler eliminates priority inversions at the cost of reduced capacity. The slack stealing query scheduler combines the benefits of the preemptive and nonpreemptive schedulers to improve the capacity while meeting the end-to-end deadlines of queries. We provide schedulability analysis for each scheduler. The analysis and advantages of our approach are validated through NS2 simulations.

With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose workloads, DCQS is specifically designed for query services in wireless sensor networks. DCQS has several unique features. First, it optimizes the query performance through conflict-free transmission scheduling based on the temporal properties of queries in wireless sensor networks. Second, it can adapt to workload changes without explicitly reconstructing the transmission schedule. Furthermore, DCQS also provides predictable performance in terms of the maximum achievable query rate. We provide an analytical capacity bound for DCQS that enables DCQS to handle overload through rate control. NS2 simulations demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and 802.11b in terms of query latency and throughput.

The robust operation of many sensor network applications depends on deploying relays to ensure wireless coverage. Radio mapping aims to predict network coverage based on a small number of link measurements. This problem is particularly challenging in complex indoor environments where walls significantly affect radio signal propagation. Nevertheless, we show that it is feasible to accurately predict coverage through a two-step process: a propagation model is used to predict signal strength at a recipient node, which is then mapped to a coverage prediction. Through an in-depth empirical study, we show that complex models do not necessarily produce accurate estimates of signal strength: there is an important tradeoff between model accuracy and the number of parameters that must be estimated from limited training data. We find that the best performance is achieved by a family of models which classify walls based on their attenuation into a small number of classes and develop an algorithm to perform this classification automatically. Based on these insights, we build a novel Radio Mapping Tool (RMT) for predicting radio converge in indoor environments. Experimental results demonstrate RMT's effectiveness in two buildings: RMT reduces the number of locations where coverage is erroneously predicted to exist by as much as 39% and 54% compared to the classic log-normal radio propagation model.

Wireless sensor networks are evolving from dedicated application-specific platforms to integrated infrastructure shared by multiple applications. Shared sensor networks offer inherent advantages in terms of flexibility and cost since they allow dynamic resource sharing and allocation among multiple applications. Such shared systems face the critical need for allocation of nodes to contending applications to enhance the overall Quality of Monitoring (QoM) under resource constraints. To address this need, this paper presents Utility-based Multi-application Allocation and Deployment Environment (UMADE), an integrated application deployment system for shared sensor networks. In sharp contrast to traditional approaches that allocate applications based on cyber metrics (e.g., computing resource utilization), UMADE adopts a cyber-physical system approach that dynamically allocates nodes to applications based on their QoM of the physical phenomena. The key novelty of UMADE is that it is designed to deal with the inter-node QoM dependencies typical in cyber-physical applications. Furthermore, UMADE provides an integrated system solution that supports the end-to-end process of (1) QoM specification for applications, (2) QoM-aware application allocation, (3) application deployment over multi-hop wireless networks, and (4) adaptive reallocation of applications in response to network dynamics. UMADE has been implemented on TinyOS and Agilla virtual machine for Telos motes. The feasibility and efficacy of UMADE have been demonstrated on a 28-node wireless sensor network testbed in the context of building automation applications.

This paper presents the design, deployment, and empirical study of a wireless clinical monitoring system that collects pulse and oxygen saturation readings from patients. The primary contribution of this paper is an in-depth clinical trial that assesses the feasibility of wireless sensor networks for patient monitoring in general hospital units. We present a detailed analysis of the system reliability from a long term hospital deployment over seven months involving 41 patients in a step-down cardiology unit. The network achieved high reliability (median 99.68%, range 95.21% -- 100%). The overall reliability of the system was dominated by sensing reliability of the pulse oximeters (median 80.85%, range 0.46% -- 97.69%). Sensing failures usually occurred in short bursts, although longer periods were also present due to sensor disconnections. We show that the sensing reliability could be significantly improved through oversampling and by implementing a disconnection alarm system that incurs minimal intervention cost. A retrospective data analysis indicated that the system provided sufficient temporal resolution to support the detection of clinical deterioration in three patients who suffered from significant clinical events including transfer to Intensive Care Units. These results indicate the feasibility and promise of using wireless sensor networks for continuous patient monitoring and clinical deterioration detection in general hospital units.

Queries are convenient abstractions for the discovery of information and services, as they offer content-based information access. In distributed settings, query semantics are well-defined, for example, queries are often designed to satisfy ACID transactional properties. When query processing is introduced in a dynamic network setting, achieving transactional semantics becomes complex due to the open and unpredictable environment. In this article, we propose a query processing model for mobile ad hoc and sensor networks that is suitable for expressing a wide range of query semantics; the semantics differ in the degree of consistency with which query results reflect the state of the environment during query execution. We introduce several distinct notions of consistency and formally express them in our model. A practical and significant contribution of this article is a protocol for query processing that automatically assesses and adaptively provides an achievable degree of consistency given the operational environment throughout its execution. The protocol attaches an assessment of the achieved guarantee to returned query results, allowing precise reasoning about a query with a range of possible semantics. We evaluate the performance of this protocol and demonstrate the benefits accrued to applications through examples drawn from an industrial application.

This article presents Agilla, a mobile agent middleware designed to support self-adaptive applications in wireless sensor networks. Agilla provides a programming model in which applications consist of evolving communities of agents that share a wireless sensor network. Coordination among the agents and access to physical resources are supported by a tuple space abstraction. Agents can dynamically enter and exit a network and can autonomously clone and migrate themselves in response to environmental changes. Agilla's ability to support self-adaptive applications in wireless sensor networks has been demonstrated in the context of several applications, including fire detection and tracking, monitoring cargo containers, and robot navigation. Agilla, the first mobile agent system to operate in resource-constrained wireless sensor platforms, was implemented on top of TinyOS. Agilla's feasibility and efficiency was demonstrated by experimental evaluation on two physical testbeds consisting of Mica2 and TelosB nodes.

Context-aware computing is characterized by the software's ability to continuously adapt its behavior to an environment over which it has little control. This style of interaction is imperative in ad hoc mobile networks that consist of numerous mobile hosts coordinating opportunistically via transient wireless connections. In this paper, we provide a formal abstract characterization of an application's context that extends to encompass a neighborhood within the ad hoc network. We provide a context specification mechanism that allows individual applications to tailor their operating contexts to their personalized needs. We describe a context maintenance protocol that provides this context abstraction in ad hoc networks through continuous evaluation of the context. This relieves the application developer of the obligation of explicitly managing mobility and its implications on behavior. We also characterize the performance of this protocol in ad hoc networks through simulation experiments. Finally, we examine real-world application examples demonstrating its use.

No abstract available.

Recent years have seen the emergence of wireless sensor network systems that must support high data rate and real- time queries of physical environments. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in wireless sensor networks. First, we show that there is an inherent trade-off between prioritization and throughput in conflict-free query scheduling. We then present three new real-time scheduling algorithms. The non-preemptive query scheduling algorithm achieves high throughput while intro- ducing priority inversions. The preemptive query schedul- ing algorithm eliminates priority inversion at the cost of reduced throughput. The slack stealing query scheduling algorithm combines the benefits of preemptive and non- preemptive scheduling by improving the throughput while meeting query deadlines. Furthermore, we provide schedu- lability analysis for each scheduling algorithm. The anal- ysis and advantages of our scheduling algorithms are vali- dated through NS2 simulations.

Queries are convenient abstractions for the discovery of information and services, as they offer content-based information access. In distributed settings, query semantics are well-defined, e.g., they often satisfy ACID transactional properties. In a dynamic network setting, however, achieving transactional semantics becomes complex due to the openness and unpredictability. In this paper, we propose a query processing model for mobile ad hoc and sensor networks suitable for expressing a wide range of query semantics; the semantics differ in the degree of consistency with which results reflect the state of the environment during execution. We introduce several distinct notions of consistency and formalize them. A practical contribution of this paper is a protocol for query processing that automatically assesses and adaptively provides an achievable degree of consistency given the state of the operational environment throughout its execution. The protocol attaches an assessment of the achieved guarantee to returned query results, allowing precise reasoning about a query with a range of possible semantics.

The decoupled nature of computing in mobile ad hoc networks (MANETs) can result in disconnections at inopportune times during an interaction between a pair of hosts. We introduce the notion of a priori selection of partner hosts to reduce the likelihood of disconnection during such interactions. An application may specify the times when and the physical locations where it requires interactions with peer applications on partner hosts. A knowledge base of the physical motion profiles of various hosts maintained on each mobile host is used to select partner hosts that are co-located with the reference host at the required time and are least likely to disconnect. In this paper, we present a formal model for such knowledge management, along with an algorithm used to determine suitable partner hosts. We also provide details of our implementation of partner selection, which has been used in the context of a service-oriented computing middleware for MANETs, developed previously by our group. Finally, we present simulation results of our approach.

No abstract available.

LIME (Linda in a mobile environment) is a model and middleware supporting the development of applications that exhibit the physical mobility of hosts, logical mobility of agents, or both. LIME adopts a coordination perspective inspired by work on the Linda model. The context for computation, represented in Linda by a globally accessible persistent tuple space, is refined in LIME to transient sharing of the identically named tuple spaces carried by individual mobile units. Tuple spaces are also extended with a notion of location and programs are given the ability to react to specified states. The resulting model provides a minimalist set of abstractions that facilitates the rapid and dependable development of mobile applications. In this article we illustrate the model underlying LIME, provide a formal semantic characterization for the operations it makes available to the application developer, present its current design and implementation, and discuss lessons learned in developing applications that involve physical mobility.

Today's mobile applications require constant adaptation to their changing environments, or contexts. Technological advances have increased the pervasiveness of mobile computing devices such as laptops, handhelds, and embedded sensors. The sheer amount of context information available for adaptation places a heightened burden on application developers as they must manage and utilize vast amounts of data from diverse sources. Facilitating programming in this data-rich environment requires a middleware that provides context information to applications in an abstract form. In this paper, we demonstrate the feasibility of such a middleware that allows programmers to focus on high-level interactions among programs and to employ declarative abstract context specifications in settings that exhibit transient interactions with opportunistically encountered components. We also discuss the novel context-aware abstractions the middleware provides and the programming knowledge necessary to write applications using it. Finally, we provide examples demonstrating the infrastructure's ability to support differing tasks from a wide variety of application domains

This paper proposes Efficient Sleep Scheduling based on Application Timing (ESSAT), a novel power management scheme that aggressively exploits the timing semantics of wireless sensor network applications. We present three ESSAT protocols each of which integrates (1) a lightweight traffic shaper that actively shapes the workload inside the network to achieve predictable timing properties over multiple hops, and (2) a local scheduling algorithm that wakes up nodes just-in-time based on the timing properties of shaped workloads. Our ESSAT protocols have several distinguishing features. First, they can save significant energy with minimal delay penalties. Second, they do not maintain TDMA schedules or communication backbones; as such, they are highly efficient and suitable for resource constrained sensor platforms. Moreover, the protocols are robust in highly dynamic network environments, i.e., they can handle variable multi-hop communication delays and aggregate workloads involving multiple queries, and can adapt to varying workload and network topologies. Our simulations showed that DTS-SS, an ESSAT protocol, achieved an average node duty cycle 38-87% lower than SPAN, and query latencies 36-98% lower than PSM and SYNC.

Wireless sensor networks (WSNs) are difficult to program and usually run statically-installed software limiting its flexibility. To address this, we developed Agilla, a new middleware that increases network flexibility while simplifying application development. An Agilla network is deployed with no pre-installed application. Instead, users inject mobile agents that spread across nodes performing application-specific tasks. Each agent is autonomous, allowing multiple applications to share a network. Programming is simplified by allowing programmers to create agents using a high-level language. Linda-like tuple spaces are used for inter-agent communication and context discovery. This preserves each agent’s autonomy while providing a rich infrastructure for building complex applications, and marks the first time mobile agents and tuple spaces are used in a unified framework for WSNs. Our efforts resulted in an implementation for MICA2 motes and the development of several applications. The implementation consumes a mere 41.6KB of code and 3.59KB of data memory. An agent can migrate 5 hops in less than 1.1 seconds with 92% reliability. In this paper, we present Agilla and provide a detailed evaluation of its implementation, an empirical study of its overhead, and a case study demonstrating its use.

Many mission-critical applications require spatiotemporal data services for mobile users or objects. Examples include distributed object tracking and fire monitoring by firefighters. To support such applications, wireless sensor networks must satisfy a set of stringent spatiotemporal constraints despite having low network duty cycles and scarce resources. We have developed two new wake-up and topology maintenance protocols, directional tree maintenance (DTM) and omnidirectional tree creation (OTC), to support spatiotemporal services in mobile environments. A key feature of our protocols is that they provide robust spatiotemporal performance while maintaining low overhead and energy consumption. Our simulations showed that both DTM and OTC can successfully deliver over 85% of query results to a mobile user within desired spatiotemporal constraints, even when the sleep schedule is as long as 15 s, the user changes direction every minute, and the location error is as high as 10 m. The benefits of our protocols have been validated through theoretical analysis and empirical results on a testbed of Mica2 motes.

Agilla is a mobile agent middleware that facilitates the rapid deployment of adaptive applications in wireless sensor networks (WSNs). Agilla allows users to create and inject special programs called mobile agents that coordinate through local tuple spaces, and migrate across the WSN performing application-specific tasks. This fluidity of code and state has the potential to transform a WSN into a shared, general-purpose computing platform capable of running several autonomous applications at a time, allowing us to harness its full potential. We have implemented and evaluated a fire tracking application to determine how well Agilla achieves its goals. Fire is modeled by agents that gradually spread throughout the network, engulfing nodes by inserting fire tuples into their local tuple spaces. Fire tracker agents are then used to form a perimeter around the fire. Using Agilla, we were able to rapidly create and deploy 47 byte fire agents, and 100 byte tracker agents on a WSN consisting of 26 MICA2 motes. Our experiments show that the tracker agents can form an 8-node perimeter around a burning node within 6.5 seconds and that it can adapt to a fire spreading at a rate of 7 seconds per hop. We also present the lessons learned about the adequacy of Agilla's primitives, and regarding the efficiency, reliability, and adaptivity of mobile agents in a WSN.

No abstract available.

This article presents FAR, a Face-Aware Routing protocol for mobicast---a spatiotemporal variant of multicast tailored for sensor networks with environmental mobility. FAR features face-routing and timed-forwarding for delivering a message to a mobile delivery zone. Both analytical and statistical results show that FAR achieves reliable spatial and just-in-time message delivery with only moderate communication and memory overhead. This article also presents a novel distributed algorithm for spatial neighborhood discovery for FAR bootstrapping. The spatiotemporal performance and reliability of FAR are demonstrated via network simulations.

Service oriented computing, with its aim of unhindered interoperability, is an appropriate paradigm for ad hoc networks, which are characterized by physical mobility of heterogenous hosts and by the absence of standardized application level protocols. The decoupled nature of computing in ad hoc networks can result in disconnections at inopportune times during the client-service interaction process. We introduce the notion of a priori selection of services to reduce the likelihood of disconnection during service usage. A client may specify the times when it requires certain services. A knowledge base of the physical motion profiles of various service providers is used to select instances of a service that are co-located with the client at the required time and least likely to disconnect. A system for constructing the knowledge base is presented in this paper, along with the implementation details and the algorithm used to determine the service usage pattern.

This work presents a novel protocol for a spatiotemporal variant of multicast called mobicast, designed to support message delivery in ad hoc sensor networks. The spatiotemporal character of mobicast relates to the obligation to deliver a message to all the nodes that will he present at time t in some geographic zone Z, where both the location and shape of the delivery zone are a function of time over some interval (t/sub start/, t/sub end/). The protocol, called face-aware routing (FAR), exploits ideas adapted from existing applications of face routing to achieve reliable mobicast delivery. The key features of the protocol are a routing strategy, which uses information confined solely to a node's immediate spatial neighborhood, and a forwarding schedule, which employs only local topological information. Statistical results shows that, in uniformly distributed random disk graphs, the spatial neighborhood size is usually less than 20. This suggests that FAR is likely to exhibit a low average memory cost. An estimation formula for the average size of the spatial neighborhood in a random network is another analytical result reported in this paper. This paper also presents a novel and low cost distributed algorithm for spatial neighborhood discovery.

The design of ad hoc mobile applications often requires the availability of a consistent view of the application state among the participating hosts. Such views are important because they simplify both the programming and verification tasks. We argue that preventing the occurrence of unannounced disconnection is essential to constructing and maintaining a consistent view in the ad hoc mobile environment. In this light, we provide the specification for a partitionable group membership service supporting ad hoc mobile applications and propose a protocol for implementing the service. A unique property of this partitionable group membership is that messages sent between group members are guaranteed to be delivered successfully, given appropriate system assumptions. This property is preserved over time despite movement and frequent disconnections. The protocol splits and merges groups and maintains a logical connectivity graph based on a notion of safe distance. An implementation of the protocol in Java is available for testing. This work is used in an implementation of LIME, a middleware for mobility that supports transparent sharing of data in both wired and ad hoc wireless environments.

Sensor networks often involve the monitoring of mobile phenomena. We believe this task can be facilitated by a spatiotemporal multicast protocol which we call "mobicast". Mobicast is a novel spatiotemporal multicast protocol that distributes a message to nodes in a delivery zone that evolves over time in some predictable manner. A key advantage of mobicast lies in its ability to provide reliable and just-in-time message delivery to mobile delivery zones on top of a random network topology. Mobicast can in theory achieve good spatiotemporal delivery guarantees by limiting communication to a mobile forwarding zone whose size is determined by the global worst-case value associated with a compactness metric defined over the geometry of the network (under a reasonable set of assumptions). In this work, we first studied the compactness properties of sensor networks with uniform distribution. The results of this study motivate three approaches for improving the efficiency of spatiotemporal multicast in such networks. First, spatiotemporal multicast protocols can exploit the fundamental tradeoff between delivery guarantees and communication overhead in spatiotemporal multicast. Our results suggest that in such networks, a mobicast protocol can achieve relatively high savings in message forwarding overhead by slightly relaxing the delivery guarantee, e.g., by optimistically choosing a forwarding zone that is smaller than the one needed for a 100% delivery guarantee. Second, spatiotemporal multicast may exploit local compactness values for higher efficiency for networks with non uniform spatial distribution of compactness. Third, for random uniformly distributed sensor network deployment, one may choose a deployment density to best support spatiotemporal communication. We also explored all these directions via simulation and results are presented in this paper.

Context-aware computing is characterized by the ability of a software system to continuously adapt its behavior to a changing environment over which it has little or no control. Previous work along these lines presumed a rather narrow definition of context, one that was centered on resources immediately available to the component in question, e.g., communication bandwidth, physical location, etc. This paper explores context-aware computing in the setting of ad hoc networks consisting of numerous mobile hosts that interact with each other opportunistically via transient wireless interconnections. We extend the context to encompass awareness of an entire neighborhood within the ad hoc network. A formal abstract characterization of this new perspective is proposed. The result is a specification method and associated context maintenance protocol. The former enables an application to define an individualized context, one that extends across multiple mobile hosts in the ad hoc network. The latter makes it possible to delegate the continuous reevaluation of the context and the performance of operations on it to some middleware operating below the application level. This relieves application development of the obligation of explicitly managing mobility and its implications on the component's behavior.

Some of the most dynamic systems being built today consist of physically mobile hosts and logically mobile agents. Such systems exhibit frequent configuration changes and a great deal of resource variability. Applications executing under these circumstances need to react continuously and rapidly to changes in operating conditions and must adapt their behavior accordingly. The development of such applications demands a reexamination of the notion of context and the mechanisms used to manage the application's response to contextual changes. This paper introduces EgoSpaces, a coordination model and middleware for ad hoc mobile environments. EgoSpaces focuses on the needs of application development in ad hoc environments by proposing an agent-centered notion of context, called a view, whose scope extends beyond the local host to data and resources associated with hosts and agents within a subnet surrounding the agent of interest. An agent may operate over multiple views whose definitions may change over time. An agent uses declarative specifications to constrain the contents of each view by employing a rich set of constraints that take into consideration properties of the individual data items, the agents that own them, the hosts on which the agents reside, and the physical and logical topology of the ad hoc network. This paper formalizes the concept of view, explores the notion of programming against views, discusses possible implementation strategies for transparent context maintenance, and describes our current prototype of the system. We include examples to illustrate the expressive power of the view abstraction and to relate it to other research on coordination models and middleware.

As computing components get smaller and people become accustomed to having computational power at their disposal at any time, mobile computing is developing as an important research area. One of the fundamental problems in mobility is maintaining connectivity through message passing as the user moves through the network. An approach to this is to have a single home node constantly track the current location of the mobile unit and forward messages to this location. One problem with this approach is that, during the update to the home agent after movement, messages are often dropped, especially in the case of frequent movement. In this paper, we present a new algorithm which uses a home agent, but maintains information regarding a subnet within which the mobile unit must be present. We also present a reliable message delivery algorithm which is superimposed on the region maintenance algorithm. Our strategy is based on ideas from diffusing computations as first proposed by Dijkstra and Scholten. Finally, we present a second algorithm which limits the size of the subnet by keeping only a path from the home node to the mobile unit.

LIME is a middleware supporting the development of applications that exhibit physical mobility of hosts, logical mobility of agents, or both. LIME adapts a coordination perspective inspired by work on the Linda model. The context for computation, represented in Linda by a globally accessible, persistent tuple space, is represented in LIME by transient sharing of the tuple spaces carried by each individual mobile unit. Linda tuple spaces are also extended with a notion of location and with the ability to react to a given state. The hypothesis underlying our work is that the resulting model provides a minimalist set of abstractions that enable rapid and dependable development of mobile applications. In this paper, we illustrate the model underlying LIME, present its current design and implementation, and discuss initial lessons learned in developing applications that involve physical mobility.

The design of ad hoc mobile applications often requires the availability of a consistent view of the application state among the participating hosts. Such views are important because they simplify both the programming and verification tasks. Essential to constructing a consistent view is the ability to know what hosts are within proximity of each other, i.e., form a group in support of the particular application. We propose an algorithm that allows hosts within communication range to maintain a consistent view of the group membership despite movement and frequent disconnections. The novel features of this algorithm are its reliance on location information and a conservative notion of logical connectivity that creates the illusion of announced disconnection. Movement patterns and delays are factored in the policy that determines which physical connections are susceptible to disconnection.

Advancements in network technology have led to the emergence of new computing paradigms that challenge established programming practices by employing weak forms of consistency and dynamic forms of binding. Code mobility, for instance, allows for invocation-time binding between a code fragment and the location where it executes. Similarly, mobile computing allows hosts (and the software they execute) to alter their physical location. Despite apparent similarities, the two paradigms are distinct in their treatment of location and movement. This paper seeks to uncover a common foundation for the two paradigms by exploring the manner in which stereotypical forms of code mobility can be expressed in a programming notation developed for mobile computing. Several solutions to a distributed simulation problem are used to illustrate the modeling strategy and the ability to construct assertional-style proofs for programs that employ code mobility.

Mobile computing defines a very dynamic and challenging scenario for which software engineering practices are still largely in their initial developments. LIME is a middleware designed to enable the rapid development of dependable applications in the mobile environment. The model underlying LIME allows for coordination of physical and logical mobile units by exploiting a reactive, transiently shared tuple space whose contents changes according to connectivity. In this demonstration, we report about initial experiences in developing applications for physical mobility using LIME.

Article LIME: Linda meets mobility Share on Authors: Gian Pietro Picco Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MOView Profile , Amy L. Murphy Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MOView Profile , Gruia-Catalin Roman Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO Dept. of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MOView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 368–377https://doi.org/10.1145/302405.302659Online:16 May 1999Publication History 239citation755DownloadsMetricsTotal Citations239Total Downloads755Last 12 Months30Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

With recent advances in wireless communication technology, mobile computing is an increasingly important area of research. A mobile system is one where independently executing components may migrate through some space during the course of the computation, and where the pattern of connectivity among the components changes as they move in and out of proximity. Mobile UNITY is a notation and proof logic for specifying and reasoning about mobile systems. In this article it is argued that Mobile UNITY contributes to the modular development of system specifications because of the declarative fashion in which coordination among components is specified. The packet-fowarding mechanism at the core of the Mobile IP protocol for routing to mobile hosts is taken as an example. A Mobile UNITY model of packet forwarding and the mobile system in which it must operate is developed. Proofs of correctness properties, including important real-time properties, are outlined, and the role of formal verification in the development of protocols such as Mobile IP is discussed.

Recent advances in wireless networking technology and the increasing demand for ubiquitous, mobile connectivity demonstrate the importance of providing reliable systems for managing the reconfiguration and disconnection of components. The design of such systems requires tools and techniques appropriate to the task. Many formal models of computation, including UNITY, are not adequate for expressing reconfiguration and disconnection and are, therefore, inappropriate vehicles for investigating the impact of mobility on the construction of modular and composable systems. Algebraic formalisms such as the /spl pi/-calculus have been proposed for modeling mobility. This paper addresses the question of whether UNITY, a state-based formalism with a foundation in temporal logic, can be extended to address concurrent, mobile systems. In the process, we examine some new abstractions for communication among mobile components that express reconfiguration and disconnection and which can be composed in a modular fashion.

With recent advances in wireless communication and the ubiquity of laptops, mobile computing has become an important research area. An essential problem in mobile computing is the delivery of a message from a source to either a single mobile node, unicast, or to a group of mobile nodes, multicast. Standard solutions used in Mobile IP and cellular phones for the unicast problem rely on tracking the mobile unit. Tracking solutions scale badly when mobile nodes move frequently, and do not generalize well to multicast delivery. Our paper proposes a new message delivery algorithm for micromobility based on a modification of classical snapshot algorithms and includes a proof outline using the UNITY logic. Our algorithm requires no tracking, provides stronger guarantees than existing protocols in micromobility, and generalizes easily to multicasting. Besides a particular solution to the delivery problem, our approach offers a new strategy for transferring established results from distributed computing to mobile computing. The general idea is to treat mobile nodes as messages that roam across the fixed network structure and to leverage off existing distributed algorithms that compute information about messages.

Mobile computing represents a major point of departure from the traditional distributed-computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns present designers with unprecedented challenges in the areas of modularity and dependability. So far, the literature on mobile computing is dominated by concerns having to de with the development of protocols and services. This article complements this perspective by considering the nature of the underlying formal models that will enable us to specify and reason about such computations. The basic research goal is to characterize fundamental issues facing mobile computing. We want to achieve this in a manner analogous to the way concepts such as shared variables and message passing help us understand distributed computing. The pragmatic objective is to develop techniques that facilitate the verification and design of dependable mobile systems. Toward this goal we employ the methods of UNITY. To focus on what is essential, we center our study on ad hoc networks , whose singular nature is bound to reveal the ultimate impact of movement on the way one computes and communicates in a mobile environment. To understand interactions we start with the UNITY concepts of union and superposition and consider direct generalizations to transient interactions. The motivation behind the transient nature of the interactions comes from the fact that components can communicate with each other only when they are within a a certain range. The notation we employ is a highly modular extension of the UNITY programming notation. Reasoning about mobile computations relies on extensions to the UNITY proof logic.

The current trend toward portable computing systems (e.g., cellular phones, laptop computers) brings with it the need for a new paradigm to facilitate thinking about and designing distributed applications. We use the term mobile to refer to distributed systems that include moving, autonomous agents which loosely cooperate to accomplish a task. The fluid nature of the interconnections among components of a mobile system provides new challenges and opportunities for the research community. While we do not claim to have fully grasped all the issues involved in specifying and modeling such systems, we believe that the notions of place, time, and action will play a central role in any model that is developed. We show that these concepts can be expressed and reasoned about in the UNITY logic with a minimal amount of additional notation. The formal derivation of a control system for a radio-dispatched elevator is used to show how considerations involving place, time, and actions impact the design process, be it formal or semiformal.

Formal derivation refers to a family of design techniques that entail the development of programs which are guaranteed to be correct by construction. Only limited industrial use of such techniques (e.g., UNITY-style specification refinement) has been reported in the literature, and there is a great need for methodological developments aimed at facilitating their application to complex problems. This article examines the formal specification and design of a message router in an attempt to identify those methodological elements that are likely to contribute to successful industrial uses of program derivation. Although the message router cannot be characterized as being industrial grade, it is a sophisticated problem that poses significant specification and design challenges—its apparent simplicity is rather deceiving. The main body of the article consists of a complete formal specification of the router and a series of successive refinements that eventually lead to an immediate construction of a correct UNITY program. Each refinement is accompanied by its design rationale and is explained in a manner accessible to a broad audience. We use this example to make the case that program derivation provides a good basis for introducing rigor in the design strategy, regardless of the degrees of formality one is willing to consider.

As critical computer systems continue to grow in complexity, the task of showing that they execute correctly becomes more difficult. For this reason, research in software engineering has turned to formal methods, i.e., rigorous approaches to demonstrating the correctness of software systems. Unfortunately, the formal methods currently used in the design of concurrent systems do not provide any mechanisms for specifying and reasoning about the mapping of software to hardware. As a result, architectural constraints, even though they play an important role in the design process, are left out of the formal framework. We show how to state architectural constraints in a formal notation, how to prove that programs are allocated correctly to the underlying architecture, and how to factor architectural considerations into a program derivation process which uses a mixture of specification and program refinements. The approach is illustrated by the derivation of two related programs that solve the same problem but are designed to work on distinct architectures.>

Synchrony continues to be an important concern in concurrent programming. Existing languages and models have introduced a great diversity of constructs for expressing and managing synchronization among sequential processes or atomic actions. The authors put forth a model in which synchrony is viewed as a relation among atomic actions, a relation which may evolve with time. The model is shown to be convenient for expressing formally the semantics of synchrony as it appears in many of the languages and models proposed to date. Among such models Swarm is singled out for its use of dynamic synchrony. The Swarm notation is briefly reviewed. A new concurrent algorithm for the leader election problem illustrates the use of dynamic synchrony in Swarm.>

It is shown that a combination of specification and program refinement may be applied to deriving efficient concurrent rule-based programs. Specification refinement is used to generate an initial rule-based program that is refined into a program which is highly concurrent and efficient. This program derivation strategy is divided into two major tasks. The first task relies on specification refinement. Techniques similar to those employed in the derivation of UNITY programs are used to produce a correct rule-based program having a static knowledge base. The second task involves program refinement and is specific to the development of concurrent rule-based programs. It relies heavily on the availability of a computational model, such as Swarm, that has the ability to dynamically restructure the knowledge base. The ways in which a Swarm program can be translated to OPS5 specifically, given some restrictions, while maintaining the correctness criteria are discussed.>

A method for formal derivation of distributed programs is presented. The approach uses programwide assertions to formulate safety and progress properties of computations. Assertions are used to state functional requirements of the program as well as structural and behavioral constraints imposed by the choice of underlying architecture. The significance of this latter feature is that it offers a single, unified formal framework for integrating functional requirements and architectural constraints.>

In this paper program visualization is defined as a mapping from programs to graphical representations. Simple forms of program visualization are frequently encountered in software engineering. For this reason current advances in program visualization are likely to influence future developments concerning software engineering tools and environments. This paper provides a new taxonomy of program visualization research. The proposed taxonomy becomes the vehicle through which we carry out a systernatic review of current systems, techniques, trends, and ideas in program visualization.

This paper describes a formal approach for developing concurrent rule-based programs. Specification refinement is used to generate an initial version of the program. Program refinement is then applied to produce a highly concurrent and efficient version of the same program. Techniques for deriving concurrent programs through either specification or program refinement have been described in previous literature. The main contribution of this paper consists of extending the applicability of these techniques to a broad class of rule-based programs. To the best of our knowledge, this is the first time formal derivation is employed in the context of rule-based programming.

An effort has been made to develop a robust high-speed stereo matcher by exploiting parallel algorithms executing on general-purpose SIMD machines. This approach is based on several existing techniques dealing with the classification and evaluation of matches, the application of ordering constraints, and relaxation-based matching. The techniques have been integrated and reformulated in terms of parallel execution on a theoretical SIMD machine. An ideal machine topology for executing this parallel algorithm is identified through complexity analysis. Feasibility is demonstrated by implementation on a commercially available SIMD machine, and its performance is compared with that of the idealized machine. Sample results are shown for real and synthetic stereo pairs.>

The authors have developed a programming logic for Swarm that is similar in style to that of UNITY. They show how the proof logic for Swarm can be extended to accommodate the dynamic formation of synchronic groups specified by the run-time redefinition of the synchrony relation. The basic Swarm notation is reviewed, the notation for the synchrony relation is introduced, and the concept of a synchronic group is discussed. The use of synchronic groups is illustrated by means of a program for labeling regions in an image unbounded on one side. A UNITY-style assertional programming logic for Swarm without the synchrony relation is reviewed, and the logic is generalized to accommodate synchronic groups.>

A parallel algorithm for stereo matching that achieves high speed by exploiting the parallel architectures of typical single-instruction multiple-data (SIMD) processors is presented. The approach is based on several existing techniques dealing with the classification and evaluation of matches, the application of ordering constraints, and relaxation-based matching. The techniques have been integrated and reformulated in terms of parallel execution on a theoretical SIMD machine. Feasibility is demonstrated by implementation on a commercially available SIMD machine. An ideal machine, operating at 60 Hz, can accomplish stereo matching in 1.5 s using 88 machine cycles. On the commercial machine, stereo matching was achieved in 13.5 s using 404 cycles.>

A formal foundation for the specification of geographic data processing (GDP) requirements is established. Emphasis is on modeling data and knowledge requirements rather than processing needs. A subset of first-order logic is proposed as the principal means for constructing formalizations of the GDP requirements in a manner that is independent of the data representation. Requirements executability is achieved by selecting a subset of logic, compatible with the inference mechanisms available in Prolog. Concepts with GDP significance such as time, space, and accuracy are added for the formalization without losing Prolog implementability or separation of concerns. Rules of reasoning about time, space, and accuracy can be compactly stated in a subset of second-order predicate calculus and can be easily modified to meet the particular needs of a specific application. The feasibility of the approach is established with the aid of a prototype implementation of the formalism in Prolog. The implementation also provides the means for the graphical rendering of logical information on a high-resolution color display.>

A proof system for a shared dataspace programming notation called Swarm (a programming logic similar in style to that of UNITY) is specified. Relevant aspects of the Swarm language and model are overviewed. To illustrate the proof system, the Swarm logic is used to verify the correctness of a program for labeling connected equal-intensity regions of a digital image. Like UNITY, the Swarm proof system uses an assertional programming logic which relies upon proof of programwide properties, e.g. global invariants and progress properties. The Swarm logic is defined in terms of the same logical relations as UNITY (unless, ensures, and leads-to), but several of the concepts are reformulated to accommodate Swarm's distinctive features.>

A simple language called Swarm is used as a vehicle for the investigation of the shared dataspace approach to concurrent computation. An important feature of Swarm is its ability to bring a variety of programming paradigms under a single, unified model. In a series of related examples Swarm's capacity to express shared-variable, message-passing, and rule-based computations; to specify synchronous and asynchronous processing modes; and to accommodate highly dynamic program and data structure is explored. Several illustrations make use of a programming construct unique to Swarm, the synchrony relation and explain how this feature can be used to construct dynamically structured, partially synchronous computations. An overview of the Swarm programming notation, an examination of Swarm programming strategies via a series of related example programs, and a discussion of the distinctive features of the shared dataspace model are given. A formal operational model for Swarm is presented.>

A language paradigm called shared dataspace is defined that causes computations to be performed using an anonymous, content-addressable communication medium acted upon by atomic transactions. To probe the essence of this paradigm, a relatively simple shared dataspace language called Swarm is defined. An overview is presented of the Swarm language. A formal operational model for the language is given and some of the programming implications and distinctive features of the model and language are discussed. Swarm programming strategies are examined using a series of related example programs.>

This paper is concerned with the use of program visualization as a means for the understanding, debugging, and monitoring of large-scale concurrent programs.Following an overview of the shared dataspace paradigm and the declarative approach to visualization, the paper discusses:(1) mechanisms for specifying declarative visualization in the shared dataspace paradigm and ways of relating the specifications to program verification; (2) a computational model which provides a unified framework for comparing both visual and nonvisual algorithms; and (3) strategies for implementing declarative visualization on parallel machines.

A methodology is presented for designing detectors which locate specific features in an image. The method is applied to the detection and segmentation of spherical features. A vital part of the detection and segmentation is the use of the gradient angle transform. An analysis of the gradient angle for ideal spheres is presented, with a discussion of how this may be used to locate the boundaries of the sphere. The algorithms used by a program which detects and segments spherical features are then presented. The results of applying the program to images with man-made spherical features are given.>

The authors are concerned with the development of a novel approach to edge-based stereo matching. In the context of an incremental matching strategy the authors have replaced the traditional hierarchical (coarse-fine) matching by an approach called complexity control based matching. The implementation of this method allows the user to select interactively features which (given the context provided by previous matches) are most likely to be matched successfully. The selection is done at the resolution of the original image and utilizes a rich set of feature properties (e.g. edge strength, orientation, length, texture etc.), either alone or in logical combinations. Both feature-selection and feature-matching algorithms execute at real-time rates, and all interactions are via a stereo workstation.>

The authors are currently evaluating the use of shared dataspace paradigm as the basis for a novel programming language, called SDL (Shared Dataspace Language), that supports large-scale concurrency. Their goal is to develop the software support needed for the design, analysis, understanding, and testing of programs involving many thousands of concurrent processes running on a highly parallel multiprocessor. The authors provide an overview of the key SDL features, using small examples to illustrate its power and flexibility.>

The design of a Software Development Environment (SDE) represents a very interesting point of contact between data engineering and software engineering. In this context data engineering becomes the cornerstone for successful software engineering practice. This paper attempts to bring about a better understanding of the difficulties associated with this task by considering sources of complexity in SDE design.

This paper establishes a formal foundation for the specification of Geographic Data Processing (GDP) requirements. The emphasis is placed on modelling data and knowledge requirements rather than processing needs. A subset of first order logic is proposed as the principal means for constructing formalizations of the GDP requirements in a manner that is independent of the data representation. Requirements executability is achieved by selecting a subset of logic compatible with the inference mechanisms available in Prolog. GDP significant concepts such as time, space and accuracy have been added to the formalization without losing Prolog implementability or separation of concerns. Rules of reasoning about time, space and accuracy (based on positional, temporal and fuzzy logic) may be compactly stated in a subset of second order predicate calculus and may be easily modified to meet the particular needs of a specific application. Multiple views of the data and knowledge may coexist in the same formalization. The feasibility of the approach has been established with the aid of a tentative Prolog implementation of the formalism. The implementation also provides the means for graphical rendering of logical information on a high resolution color display.

A new software engineering methodology called program control structuring is proposed. Its development is justified by the need to offer the designer the capability to improve the productivity and quality of software development in the conditions of a "highly imperfect" environment. Such an environment is shown to involve the use of transient and inexperienced programmers, frequent alterations to the design specifications, and continuous development. The philosophy behind program control structuring is that of minimizing the probability of error in the design and implementation of large programs by means of language-and problem-dependent standardization. The particular standardization approach used by program control structuring is shown to provide 1) a program structure that is simple and flexible, readily understood, easily developed, and inexpensively maintained, and 2) a high-quality and partially mechanizable structure-oriented documentation scheme. Subsequently, it is suggested that many of the standards are mechanizable in the immediate future as a necessary condition for achieving higher productivity and improved program quality. Finally, the mechanization of software production is proposed as a step needed to precede the development of automatic program generation systems.