22550674
Timing-sync protocol for sensor networks
Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.
2162080
Harbor: software-based memory protection for sensor nodes
Many sensor nodes contain resource constrained microcontrollers where user level applications, operating system components, and device drivers share a single address space with no form of hardware memory protection. Programming errors in one application can easily corrupt the state of the operating system or other applications. In this paper, we propose Harbor, a memory protection system that prevents many forms of memory corruption. We use software based fault isolation ("sandboxing") to restrict application memory accesses and control flow to protection domains within the address space. A flexible and efficient memory map data structure records ownership and layout information for memory regions; writes are validated using the memory map. Control flow integrity is preserved by maintaining a safe stack that stores return addresses in a protected memory region. Run-time checks validate computed control flow instructions. Cross domain calls perform low-overhead control transfers between domains. Checks are introduced by rewriting an application's compiled binary. The sand-boxed result is verified on the sensor node before it is admitted for execution. Harbor's fault isolation properties depend only on the correctness of this verifier and the Harbor runtime. We have implemented and tested Harbor on the SOS operating system. Harbor detected and prevented memory corruption caused by programming errors in application modules that had been in use for several months. Harbor's overhead, though high, is less than that of application-specific virtual machines, and reasonable for typical sensor workloads.
47199334
Computation Hierarchy for In-Network Processing
In this paper we explore the network level architecture of distributed sensor systems that perform in-network processing. We propose a system with heterogeneous nodes that organizes into a hierarchical structure dictated by the computational capabilities. The presence of high-performance nodes amongst a sea of resource-constrained nodes exposes new tradeoffs for the efficient implementation of network-wide applications. Our experiments show that even for a low relative density of resource-constrained nodes to high-performance nodes there are certain gains in performance for a heterogeneous and hierarchical network over a homogeneous one. The introduction of hierarchy enables partitioning of the application into sub-tasks that can be mapped onto the heterogeneous nodes in the network in multiple ways. We analyze the tradeoffs between the execution time of the application, accuracy of the output produced and the overall energy consumption of the network for the different mapping of the sub-tasks onto the heterogeneous nodes. We evaluate the performance and energy consumption of a typical sensor network application of target tracking via beamforming and line of bearing (LOB) calculations on the different nodes. Our experiments also include the study of the overall performance and energy consumption of the LOB calculation using two different types of resource constrained sensor nodes (MICA and MICA2 nodes) and show how these metrics are affected by changes in the node architecture and operation. Our results indicate that when using MICA motes as resource-constrained nodes, 85% of the time on average the hierarchical network outperforms a homogeneous network for approximately the same energy budget. When using MICA2 motes as resource-constrained nodes, 54% of the time the hierarchical network performs better than a homogeneous network with approximately the same energy budget.
1384171
Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks
Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks
8183809
Realization of multimethods in single dispatch object oriented languages
The need for multimethods is preeminent in the domain of object-oriented programming. However, multimethods are far from universally acknowledged. Commonly used languages - C++, Java & C# - are single dispatching languages. In this paper, we demonstrate the alternatives for multimethods in such languages. The techniques discussed, in this paper, include double dispatching (a well known technique), technique of message dispatching using RTTI (explored in detail by us in this paper), and reflection (a feature provided by some compilers). We implement these techniques for C++, Java and C# languages and discuss issues associated with encapsulating multimethods in single dispatch languages. We also compare techniques in terms of their efficiency, ease of (re)use and type safety.
2138355
Specification of secure distributed collaboration systems
The focus of this paper is on a specification model for defining security and coordination policies for distributed collaboration and workflow systems. This work is motivated by the objective to build distributed collaboration systems from their high level specifications. We identify here unique requirements for secure collaboration, specifically role admission and activation constraints, separation of duties, dynamic access control, and a model for multiuser participation in a role. We present a role-based model for specifying coordination and dynamic security requirements in collaboration systems. It also supports hierarchical structuring of a large collaboration environment using the concept of activities, which define a naming scope and a protection domain to specify security and coordination policies. We have implemented this specification model in XML and used it to construct the runtime environments for distributed collaboration systems using a policy based middleware.
5316084
On Improving Wireless Broadcast Reliability of Sensor Networks Using Erasure Codes
Efficient and reliable dissemination of information over a large area is a critical ability of a sensor network for various reasons such as software updates and transferring large data objects (e.g., surveillance images). Thus efficiency of wireless broadcast is an important aspect of sensor network deployment. In this paper, we study FBcast, a new broadcast protocol based on the principles of modern erasure codes. We show that our approach provides high reliability, often considered critical for disseminating codes. In addition FBcast offers limited data confidentiality. For a large network, where every node may not be reachable by the source, we extend FBcast with the idea of repeaters to improve reliable coverage. Simulation results on TOSSIM show that FBcast offers higher reliability with lower number of retransmissions than traditional broadcasts.
15931484
Optimal slope bin classification in gradient adjusted predictor for lossless compression of medical images
Gradient adjusted predictor (GAP) uses seven fixed range of slope quantization bins and different predictors associated with each bin, for prediction of pixels of all kinds of images. Criteria for range of slope in the bins and associated predictors are not reported in the literature. This paper presents a technique for slope quantization bins which are optimum for a given set of images. It also presents a technique for finding a statistically optimal predictor for a given range of slope bin. Simulation results, for medical images, using optimal slope bins and associated predictors show a significant better compression performance as compared to the other methods such as GAP and edge-directed prediction (EDP) method. The proposed method and GAP has same order of computational complexity while EDP is computationally much expensive.