Search

Desynchronization is useful for scheduling nodes to perform tasks at different time. This property is desirable for resource sharing, TDMA scheduling, and collision avoiding. Inspired by robotic circular formation, we propose DWARF (Desynchronization With an ARtificial Force field), a novel technique for desynchronization in wireless networks. Each neighboring node has artificial forces to repel other nodes to perform tasks at different time phases. Nodes with closer time phases have stronger forces to repel each other in the time domain. Each node adjusts its time phase proportionally to its received forces. Once the received forces are balanced, nodes are desynchronized. We evaluate our implementation of DWARF on TOSSIM, a simulator for wireless sensor networks. The simulation results indicate that DWARF incurs significantly lower desynchronization error and scales much better than existing approaches.

Advances in processor, memory, and radio technology will enable small and cheap nodes capable of sensing, communication, and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed-diffusion paradigm for such coordination. Directed diffusion is data-centric in that all communication is for named data. All nodes in a directed-diffusion-based network are application aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network (e.g., data aggregation). We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network analytically and experimentally. Our evaluation indicates that directed diffusion can achieve significant energy savings and can outperform idealized traditional schemes (e.g., omniscient multicast) under the investigated scenarios.

Several prospective applications on vehicular networks have been defined. Most applications rely on beaconing mechanisms to broadcast the presence and updated information of a vehicle to surrounding neighbors. However, due to the broadcasting nature, no acknowledgement mechanism is provided. Therefore, vehicles do not perceive beacon collision if two or more vehicles simultaneously broadcast the beacons. Consequently, vehicles miss updated information from their neighbors. In this paper, we propose V-DESYNC, an algorithm that distributively desynchronizes vehicles to broadcast beacons at different times based on only timing information. V-DESYNC is designed to avoid the beacon collision and tolerate the highly dynamic behavior of vehicular networks. Our evaluation results indicate that V-DESYNC can significantly reduce the number of beacon collisions without decreasing the beaconing rate on vehicular networks.

In recent years, there are several studies on desynchronization for wireless sensor networks. In order to propose new desynchronization protocols, unavoidably, researchers have to implement previous desynchronization works to compare with their own protocols. However, validating the implementations takes time and effort. In this paper, we propose DeVise, a visualizer for validating desynchronization protocols on multi-hop wireless sensor networks. DeVise reads configuration and trace files, and visualizes the protocol behavior. DeVise provides sufficient and useful information to help researchers reduce time and effort in the protocol validation process. We have evaluated DeVise with several desynchronization protocols. The result shows that DeVise helps researchers validate the implementations and effectively helps explore advantages and drawbacks when comparing different desynchronization protocols.

Logic macroprogramming paradigms for wireless sensor networks (WSNs) are rule-based abstractions for programming a network as a whole. Programmers only focus on the main objective of the network rather than the low-level implementation details on each node. Therefore, the low-level details are automatically handled by underlying middleware of the paradigms. To be viable, the middleware must efficiently handle the underlying issues as well as effectively minimize energy consumption and communication overhead. Not surprisingly, one major underlying issue in logic macroprogramming systems is deductive-query processing. In this paper, we analyze the characteristics of deductive-query processing and identify what have been overlooked in those previous approaches. Furthermore, we overview, analyze, and compare several recent approaches for deductive-query processing of logic macroprograms in WSNs. Our analysis reveals several important aspects that should be considered when designing such systems.

Push-pull approaches for peer-to-peer live streaming systems have gained tremendous popularity due to their high scalability and low latency. However, such approaches rely on buffer-map information of all neighbors to determine which piece to push and which peer to pull. Therefore, those approaches incur significant overhead in order to maintain the up-to-date buffer-maps of all neighbors. In this paper, we propose an algorithm to predict the buffer-map of a neighbor. Peers in our approach no longer need to frequently exchange their buffer-maps. We have implemented and evaluated our algorithm on ns-2. Under investigated scenarios, our approach can reduce up to 97% of overhead as well as simultaneously decrease duplicates of the previous system.

Content dissemination in Vehicular Ad-Hoc Networks (VANET) has attracted wide interest in the research community. The use of network coding for file sharing has been proved to overcome several problems such as highly dynamic topology and intermittent connectivity. Prior works have originally been designed to work well even with only single hop communication. However, the previous works are not entirely suitable for networks with low node density or low percentage of interested nodes. We, therefore, propose CarCode, an adaptive request mechanism to improve the speed and efficiency of network-coded file distribution in such networks. Each node adaptively requests coded pieces of the file from the source when it does not receive any useful coded piece from its current neighbors within a calculated timeout. Our adaptive timer is proportional to the rate of new incoming neighbors whereas the number of requested pieces is inversely proportional. We have incorporated our approach with CodeTorrent and evaluated its performance on NS-2 simulator. Our result indicates that CarCode can significantly improve the efficiency and download latency of CodeTorrent under investigated scenarios.

This paper proposes an Orthodontics-inspired desynchronization algorithm for scheduling wireless sensor nodes to avoid conflicts on resource sharing by not accessing the resource at the same time. Applications of desynchronization include TDMA scheduling, wake-sleep scheduling, and collision avoiding. Although existing desynchronization approaches perform reasonably well, their errors highly fluctuate. This high fluctuation implies overshooting and results in high errors even after convergence. For smoother convergence and lower error, we design a mechanism analogous to an orthodontic teeth-alignment technique. In Orthodontics, an orthodontist prevents the already-correct-positioning teeth from moving by tying them with a power chain. We apply the similar concept to the existing desynchronization method to prevent nodes with correct phases from adjusting their time phases. We evaluate our implementation of DESYNC-ORT on TOSSIM, a simulator for wireless sensor networks. The simulation result indicates that our method significantly helps the existing desynchronization algorithm to converge smoothly with lower error (reducing approximately 20–60% of errors caused by existing approaches).

Existing mesh-push approaches for peer-to-peer live streaming systems have been reported to significantly reduce diffusion latency, overlay- construction difficulty, maintenance complication, and churning impact. However, those approaches incur excessive duplicate data and result in bandwidth inefficiency due to stale information as well as chunk synchronicity problems. In this paper, we propose a reinforcement-based push-pull approach for peer-to-peer live streaming over mesh overlays to overcome the mentioned problems. We design a probabilistic push scheme with a reinforcement mechanism as a part of our hybrid approach. The mechanism encourages non- duplicate-sending nodes to push chunks and discourages duplicate-sending nodes from pushing chunks. As a result, duplicate data is significantly reduced and bandwidth efficiency is tremendously improved. We implement and evaluate our approach on NS-2. The simulation results indicate that our approach can reduce 73\% of duplicate data under investigated scenarios.

Wireless sensor network (WSN) applications usually demand a time-synchronization protocol for node coordination and data interpretation. In this paper, we propose an Energy-Efficient Gradient Time Synchronization Protocol (EGTSP) for Wireless Sensor Networks. In contrast to FTSP, a state-of-the-art synchronization protocol for WSNs, EGTSP is a completely localized algorithm that achieves a global time consensus and gradient time property using effective drift compensation and incremental averaging estimation. In contrast with GTSP, a gradient-based fixed-rated time synchronization protocol, our protocol provides adaptive beaconing for applications to optimize energy savings by selecting appropriate message-broadcast periods. The protocol is implemented and evaluated on multi-hop networks that consist of Telosb motes running TinyOS. The experimental results indicate that our protocol achieves a network-wide global notion of time, attains small synchronization errors, and utilizes energy efficiently.

Bittorrent is currently one of the most popular peer-to-peer (P2P) file sharing protocols. However, it incurs such excessive amount of traffic that it may adversely affect users of legacy internet applications. To limit this adverse impact, an efficient methodology for bittorrent identification may be needed. In this paper, we propose a novel approach to identify local bittorrent peers. Our approach is based on behaviors of the choke algorithm, a main algorithm used in bittorrent. An advantage of our approach is that we can identify bittorrent peers without examining the packet pay-load. Therefore, our approach is free from privacy issues and still effective even though the packet payload is encrypted. Unlike previous works, we identify bittorrent hosts at the peer level instead of the flow level. Given that we use only information from network layer instead of transport layer, our work maintains fewer states and achieves robustness to changes in the transport layer. Furthermore, our work is effective even in restricted environments such as networks equipped with NAT devices or firewalls without modifications to existing network equipments. Our experimental result indicates that our approach can efficiently identify most of excessive bandwidth-consuming peers (i.e., peers transfer a large amount of data in our traces) with a low false-positive rate.

Wireless sensor networks consist of a large number of sensor nodes with limited power and resource. To prolong network lifetime, the energy consumption must be somehow reduced. In this paper, we propose a localized density control algorithm for energy savings. The goals are to maintain a minimal number of active sensor nodes and to reduce radio-traffic intensity while conserving the sensing coverage of the network. Our localized algorithm is based on a greedy solution of a weighted set-cover problem. Each node locally computes whether to sleep or to stay active. Given that the local decision might worsen the sensing coverage, we also introduce a voting scheme for selecting active nodes to assure that a node can sleep if and only if its sensing area is completely covered by its active neighbors. We have implemented our localized algorithm and voting scheme on Tiny OS and evaluated on TOSSIM. The result indicates that our algorithm is efficient and viable for practical use.

During the next decade, emerging technologies will help populating the physical space with ubiquitous networks of embedded systems (NES). Programming NES requires new abstractions and computing models since the current programming, models are not designed for the scale and volatility encountered in these networks. This paper presents Spatial Programming (SP), a novel programming model for NES. The key idea in SP is to offer network-transparent access to data and services distributed on nodes spread across the physical space. SP programs access network resources using a high level abstraction, termed spatial reference, which addresses the nodes using their spatial and content properties. An underlying system takes care of mapping spatial references onto target nodes in the network. Our preliminary experience in developing SP applications suggests that SP can be a viable solution for distributed computing over NES.

Smart messages (SMs) are dynamic collections of code and data that migrate to nodes of interest in the network and execute on these nodes. A key challenge in programming pervasive computing environments using SMs is the ability to route SMs to nodes named by content. This paper describes the SM self-routing mechanism, which allows SMs to route themselves at each hop in the path toward a node of interest. SM applications can choose among multiple content based routing algorithms, switch dynamically the routing algorithm in use, or even implement the best suited routing algorithm for their needs. The main benefits provided by self-routing are high flexibility and resilience to adverse network conditions. To demonstrate these benefits, we present proof-of-concept implementation, simulation results, and analysis for the SM self-routing mechanism using several content-based routing algorithms. We also show preliminary results for SM routing algorithms executed over our SM prototype implementation.

Spatial programming (SP) is a space-aware programming model for outdoor distributed embedded systems. Central to SP are the concepts of space and spatial reference, which provide applications with a virtual resource naming in networks of embedded systems. A network resource is referenced using its expected physical location and properties. Together with other SP features, such as reference consistency and access timeout, they help programmers cope with highly dynamic network configurations in a network-transparent fashion. We present the SP design and its implementation using smart messages, a lightweight software architecture similar to mobile agents, that we developed for networks of embedded systems. We also describe the implementation and evaluation of a simple SP application over a testbed consisting of HP iPAQs running Linux and equipped with 802.11 cards for wireless communication. The experimental results indicate that SP is a viable programming model for outdoor distributed computing.

In-network data aggregation is essential for wireless sensor networks where energy resources are limited. In a previously proposed data dissemination scheme (directed diffusion with opportunistic aggregation), data is opportunistically aggregated at intermediate nodes on a low-latency tree. In this paper, we explore and evaluate greedy aggregation, a novel approach that adjusts aggregation points to increase the amount of path sharing, reducing energy consumption. Our preliminary results suggest that, under investigated scenarios, greedy aggregation can achieve up to 45% energy savings over opportunistic aggregation in high-density networks without adversely impacting latency or robustness.

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are external to the network topology and relevant to the application. When combined with dense deployment of nodes, this kind of named data enables in-network processing for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.

It is notoriously difficult and tedious to program wireless sensor networks (WSNs). To simplify WSN programming, we propose Sense2P, a logic macroprogramming system for abstracting, programming, and using WSNs as globally deductive databases. Unlike macroprograms in previous works, our logic macroprograms can be described declaratively and imperatively. In Sense2P, logic macroprogrammers can easily express a recursive program or query that is unsupported in existing database abstractions for WSNs. We have evaluated Sense2P analytically and experimentally. Our evaluation result indicates that Sense2P successfully realizes the logic macroprogramming concept while consuming minimal energy as well as maintaining completeness and soundness of the answers.