17234499
AMRoute: Ad Hoc Multicast Routing Protocol
The Ad hoc Multicast Routing protocol (AMRoute) presents a novel approach for robust IP Multicast in mobile ad hoc networks by exploiting user-multicast trees and dynamic logical cores. It creates a bidirectional, shared tree for data distribution using only group senders and receivers as tree nodes. Unicast tunnels are used as tree links to connect neighbors on the user-multicast tree. Thus, AMRoute does not need to be supported by network nodes that are not interested/capable of multicast, and group state cost is incurred only by group senders and receivers. Also, the use of tunnels as tree links implies that tree structure does not need to change even in case of a dynamic network topology, which reduces the signaling traffic and packet loss. Thus AMRoute does not need to track network dynamics; the underlying unicast protocol is solely responsible for this function. AMRoute does not require a specific unicast routing protocol; therefore, it can operate seamlessly over separate domains with different unicast protocols. Certain tree nodes are designated by AMRoute as logical cores, and are responsible for initiating and managing the signaling component of AMRoute, such as detection of group members and tree setup. Logical cores differ significantly from those in CBT and PIM-SM, since they are not a central point for data distribution and can migrate dynamically among member nodes. Simulation results (using ns-2) demonstrate that AMRoute signaling traffic remains at relatively low level for typical group sizes. The results also indicate that group members receive a high proportion of data multicast by senders, even in the case of a highly dynamic network.
9147389
Data-gathering wireless sensor networks: organization and capacity
In this paper we study the transport capacity of a data-gathering wireless sensor network under different communication organizations. In particular, we consider using a flat as well as a hierarchical/clustering architecture to realize many-to-one communications. The capacity of the network under this many-to-one data-gathering scenario is reduced compared to random one-to-one communication due to the unavoidable creation of a point of traffic concentration at the data collector/receiver. We introduce the overall throughput bound of λ = W/n per node, where W is the transmission capacity, and show under what conditions it can be achieved and under what conditions it cannot. When those conditions are not met, we constructively show how λ = Θ(W/n) is achieved with high probability as the number of sensors goes to infinity. We also show how the introduction of clustering can improve the throughput. We discuss the trade-offs between achieving capacity and energy consumption, how transport capacity might be affected by considering in-network processing and the implications this study has on the design of practical protocols for large-scale data-gathering wireless sensor networks.
7940393
Partial clustering: maintaining connectivity in a low duty-cycled dense wireless sensor network
We consider a dense wireless sensor network where the radio transceivers of the sensor nodes are heavily duty-cycled in order to conserve energy. The chief purpose of the sensor network is surveillance and monitoring, where upon observation of certain event of interest, a sensor node generates a message and forwards it to a gateway located somewhere in or near the network. This forwarding relies on routes constructed using sensors whose radios are on/active. In order for such messages to reach the gateway with minimal delay, any sensor in the network should ideally have a route to the gateway consisting of active sensors at all times. Prior approaches to similar problems include clustering, virtual backbone, and connected dominating sets. Low energy consumption and good connectivity are potentially conflicting objectives. Our principal goal is to find an approach that results in the lowest possible duty cycle, and that provides better trade-off between the two objectives. In this paper we introduce the concept of partial clustering, which may be viewed as a generalized method of clustering. We compare the theoretical performance of different instances of partial clustering to that of standard clustering, and show that partial clustering can achieve lower duty cycle and provide greater flexibility in the trade-off between energy efficiency and connectivity. We then present a distributed algorithm based on the partial clustering method. Simulation results are provided to evaluate their effectiveness and energy efficiency.
35466588
Modeling and Analysis of TCP Enhancement over Heterogeneous Links
In this paper we focus on one type of TCP enhancement commonly used to improve performance for connections over heterogeneous physical layer, namely, TCP connection splitting or split TCP, where the end-to-end TCP connection is split in segments so that each segment runs over a homogeneous environment and is optimized separately. This paper presents a simple model capturing some of the features of this scheme where split segments are essentially "coupled" TCP connections. We use simulation to validate our models and use our model to analyze situations where split TCP is preferred to the end-to-end scheme, and where the performance gain of splitting vanishes by investigating factors including initial window size, file size, number of on-going connections and loss.
18560533
On the Many-to-One Transport Capacity of a Dense Wireless Sensor Network and the Compressibility of Its Data
In this paper we investigate the capability of large-scale sensor networks to measure and transport a two-dimensional field. We consider a data-gathering wireless sensor network in which densely deployed sensors take periodic samples of the sensed field, and then scalar quantize, encode and transmit them to a single receiver/central controller where snapshot images of the sensed field are reconstructed. The quality of the reconstructed field is limited by the ability of the encoder to compress the data to a rate less than the single-receiver transport capacity of the network. Subject to a constraint on the quality of the reconstructed field, we are interested in how fast data can be collected (or equivalently how closely in time these snapshots can be taken) due to the limitation just mentioned. As the sensor density increases to infinity, more sensors send data to the central controller. However, the data is more correlated, and the encoder can do more compression. The question is: Can the encoder compress sufficiently to meet the limit imposed by the transport capacity? Alternatively, how long does it take to transport one snapshot? We show that as the density increases to infinity, the total number of bits required to attain a given quality also increases to infinity under any compression scheme. At the same time, the single-receiver transport capacity of the network remains constant as the density increases. We therefore conclude that for the given scenario, even though the correlation between sensor data increases as the density increases, any data compression scheme is insufficient to transport the required amount of data for the given quality. Equivalently, the amount of time it takes to transport one snapshot goes to infinity.
3019893
An Efficient and Robust Computational Framework for Studying Lifetime and Information Capacity in Sensor Networks
In this paper we investigate the expected lifetime and information capacity, defined as the maximum amount of data (bits) transferred before the first sensor node death due to energy depletion, of a data-gathering wireless sensor network. We develop a fluid-flow based computational framework that extends the existing approach, which requires precise knowledge of the layout/deployment of the network, i.e., exact sensor positions. Our method, on the other hand, views a specific network deployment as a particular instance (sample path) from an underlying distribution of sensor node layouts and sensor data rates. To compute the expected information capacity under this distribution-based viewpoint, we model parameters such as the node density, the energy density and the sensed data rate as continuous spatial functions. This continuous-space flow model is then discretized into grids and solved using a linear programming approach. Numerical studies show that this model produces very accurate results, compared to averaging over results from random instances of deployment, with significantly less computation. Moreover, we develop a robust version of the linear program, which generates robust solutions that apply not just to a specific deployment, but also to topologies that are appropriately perturbed versions. This is especially important for a network designer studying the fundamental lifetime limit of a family of network layouts, since the lifetime of specific network deployment instances may differ appreciably. As an example of this model's use, we determine the optimal node distribution for a linear network and study the properties of optimal routing that maximizes the lifetime of the network.
13585707
A High Population, Fault Tolerant Parallel Raytracer
We present hierarchical master-slave architecture for performing parallel raytracing algorithms that can support a large population of participating clients and at the same time maintain fault tolerance at the application level. Our design allows for scalability with minimal data redundancy and maximizes the utilization of each client involved in the raytracing process. Our results show that this three-layer system can survive any type or number of client failures, and any non-concurrent server failures, while maintaining a near linear increase in performance with the addition of each new processing client.
15259508
On the retention of female computer science students
12646584
An Evaluation of the Use of Problem-Based Learning Software By Middle School Students
Research has shown the potential of a problem-based approach to enhance students' learning. The interactive nature of hypermedia technology and its ability to deliver information in different media formats can provide unique capabilities for implementing problem-based learning (PBL) environments. Yet, we know little about the types of tools that are effective in supporting students' learning in a hypermedia supported PBL environment. The purpose of this study was to investigate both the use of tools and design features in a piece of PBL software and their effectiveness on middle school students' learning. The findings of this study show that students who were exposed to the PBL environment increased their achievement scores from pre to posttest more than those students who learned the same content in the traditional classroom. Students' reading ability was found to be a better predictor for their achievement in PBL than their math ability. However, the brief treatment of the study had only limited impact on students' attitude toward learning science. The findings of the study and their implications are discussed in detail.
18228951
Combinatorial constructions for optimal supersaturated designs
Abstract Combinatorial designs have long had substantial application in the statistical design of experiments, and in the theory of error-correcting codes. Applications in experimental and theoretical computer science, communications, cryptography and networking have also emerged in recent years. In this paper, we focus on a new application of combinatorial design theory in experimental design theory. E ( f NOD ) criterion is used as a measure of non-orthogonality of U-type designs, and a lower bound of E ( f NOD ) which can serve as a benchmark of design optimality is obtained. A U-type design is E ( f NOD )-optimal if its E ( f NOD ) value achieves the lower bound. In most cases, E ( f NOD )-optimal U-type designs are supersaturated. We show that a kind of E ( f NOD )-optimal designs are equivalent to uniformly resolvable designs. Based on this equivalence, several new infinite classes for the existence of E ( f NOD )-optimal designs are then obtained.