Data transmission over WiFi quickly drains the batteries of mobile devices. Although the IEEE 802.11 standards provide power save mode (PSM) to help mobile devices conserve energy, PSM fails to bring expected benefits in many real scenarios. In particular, when multiple PSM mobile devices associate to a single access point (AP), PSM does not work well under transmission contention. Optimizing power saving of multiple PSM clients is a challenging task, because each PSM client expects to complete data transmission early so that it can turn to low power mode. In this paper, we define an energy conserving model to describe the general PSM traffic contention problem. We prove that the optimization of energy saving for multiple PSM clients under constraint is an NPcomplete problem. Following this direction, we propose a solution called harmonious power saving mechanism (HPSM) to address one specific case, in which multiple PSM clients associate to a single AP. In HPSM, we first use a basic sociological concept to define the richness of a PSM client based on the link resource it consumes. Then, we separate these poor PSM clients from rich PSM clients in terms of link resource consumption and favor the former to save power when they face PSM transmission contention. We implement prototypes of HPSM based on the open source projects Mad-wifi and NS-2. Our evaluations show that HPSM can help the poor PSM clients effectively save power while only slightly degrading the rich PSM clients' performance in comparison with the existing PSM solutions.

Body sensor networks (BSNs) have been developed for a set of performance-critical applications, including smart healthcare, assisted living, emergency response, athletic performance evaluation, and interactive controls. Many of these applications require stringent performance assurance in terms of communication throughput and bounded time delay. While solutions exist in literature for providing joint throughput and time delay assurance by proposing specific MAC protocols or extensions, we provide this joint assurance in a novel radio-agnostic manner. In our approach, the underlying MAC and PHY layers can be heterogeneous and their details do not need to be known to upper layers like the resource management. Such a radio-agnostic performance assurance is critical because a range of radio platforms are adopted for practical body sensor usage. Our approach is based on a group-polling scheme that is essential for radio-agnostic BSN design. Through theoretical analysis, we prove that with the group-polling scheme, achieving joint throughput and time delay assurance is an NP-hard problem. For practical system deployment, we propose the BodyT2 framework that assures throughput and time delay performance in a heterogeneous BSN. Through both TelosB mote lab tests and real body experiments in an Android phone-centric BSN, we demonstrate that BodyT2 achieves superior performance over existing solutions.

Deploying road-side WiFi access points has made possible internet access in a vehicle, nevertheless it is challenging to maintain client performance at vehicular speed especially when multiple mobile users exist. This paper considers the association control problem for vehicular WiFi access in the Drive-thru Internet scenario. In particular, we aim to improve the efficiency and fairness for all users. We design efficient algorithms to achieve these objectives through several techniques including approximation. Our simulation results demonstrate that our algorithms can achieve significantly better performance than conventional approaches.

Driven by the market demand for high-definition 3D graphics, commodity graphics processing units (GPUs) have evolved into highly parallel, multi-threaded, many-core processors, which are ideal for data parallel computing. Many applications have been ported to run on a single GPU with tremendous speedups using general C-style programming languages such as CUDA. However, large applications require multiple GPUs and demand explicit message passing. This paper presents a message passing toolkit, called GMH (GPU Message Handler), on NVIDIA GPUs. This toolkit utilizes a data-parallel thread group as a way to map multiple GPUs on a single host to an MPI rank, and introduces a notion of virtual GPUs as a way to bind a thread to a GPU automatically. This toolkit provides high performance MPI style point-to-point and collective communication, but more importantly, facilitates event-driven APIs to allow an application to be managed and executed by the toolkit at runtime.

Radio Frequency IDentification (RFID) technology has attracted much attention due to its variety of applications, e.g., inventory control and object tracking. One important problem in RFID systems is how to quickly estimate the number of distinct tags without reading each tag individually. This problem plays a crucial role in many real-time monitoring and privacy-preserving applications. In this paper, we present an efficient and anonymous scheme for tag population estimation. This scheme leverages the position of the first reply from a group of tags in a frame. Results from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the previous work.

RFID is an emerging technology with many potential applications such as inventory management for supply chain. In practice, these applications often need a series of continuous scanning operations to accomplish a task. For example, if one wants to scan all the products with RFID tags in a large warehouse, given a limited reading range of an RFID reader, multiple scanning operations have to be launched at different locations to cover the whole warehouse. Usually, this series of scanning operations are not completely independent as some RFID tags can be read by multiple processes. Simply scanning all the tags in the reading range during each process is inefficient because it collects a lot of redundant data and consumes a long time. In this paper, we develop efficient schemes for continuous scanning operations defined in both spatial and temporal domains. Our basic idea is to fully utilize the information gathered in the previous scanning operations to reduce the scanning time of the succeeding ones. We illustrate in the evaluation that our algorithms dramatically reduce the total scanning time when compared with other solutions.

Data storage has become an important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. Storage nodes are introduced in this paper to store the data collected from the sensors in their proximities. The storage nodes alleviate the heavy load of transmitting all data to a central place for archiving and reduce the communication cost induced by the network query. The objective of this paper is to address the storage node placement problem aiming to minimize the total energy cost for gathering data to the storage nodes and replying queries. We examine deterministic placement of storage nodes and present optimal algorithms based on dynamic programming. Further, we give stochastic analysis for random deployment and conduct simulation evaluation for both deterministic and random placements of storage nodes.

Deploying city-wide 802.11 access points has made possible internet access in a vehicle, nevertheless it is challenging to maintain client performance at vehicular speed especially when multiple mobile users exist. This paper considers the association control problem for vehicular networks in drive-thru Internet scenarios. In particular, we aim to improve the overall throughput and fairness for all users. We design efficient algorithms to achieve the objectives through several techniques including approximation. Our simulation results confirm the performance of our algorithms.

As RFID tags are increasingly attached to everyday items, it quickly becomes impractical to collect data from every tag in order to extract useful information. In this paper, we consider the problem of identifying popular categories of RFID tags out of a large collection of tags, without reading all the tag data. We propose two algorithms based on the idea of group testing, which allows us to efficiently derive popular categories of tags. We evaluate our solutions using both theoretical analysis and simulation.

Outlier detection has many important applications in sensor networks, e.g., abnormal event detection, animal behavior change, etc. It is a difficult problem since global information about data distributions must be known to identify outliers. In this paper, we use a histogram-based method for outlier detection to reduce communication cost. Rather than collecting all the data in one location for centralized processing, we propose collecting hints (in the form of a histogram) about the data distribution, and using the hints to filter out unnecessary data and identify potential outliers. We show that this method can be used for detecting outliers in terms of two different definitions. Our simulation results show that the histogram method can dramatically reduce the communication cost.

Data storage has become an important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. This paper introduces storage nodes to store the data collected from the sensors in their proximities. The storage nodes alleviate the heavy load of transmitting all the data to a central place for archiving and reduce the communication cost induced by the network query. This paper considers the storage node placement problem aiming to minimize the total energy cost for gathering data to the storage nodes and replying queries. We examine deterministic placement of storage nodes and present optimal algorithms based on dynamic programming. Further, we give stochastic analysis for random deployment and conduct simulation evaluation for both deterministic and random placements of storage nodes.

Recent progress in performance coupled with a decline in price for copper-based gigabit Ethernet (GigE) interconnects makes them an attractive alternative to expensive high speed network interconnects (NIC) when constructing Linux clusters. However traditional message passing systems based on TCP for GigE interconnects cannot fully utilize the raw performance of today's GigE interconnects due to the overhead of kernel involvement and multiple memory copies during sending and receiving messages. The overhead is more evident in the case of mesh connected Linux clusters using multiple GigE interconnects in a single host. We present a general message passing system called QMP-MVIA (QCD Message Passing over M-VIA) for Linux clusters with mesh connections using GigE interconnects. In particular, we evaluate and compare the performance characteristics of TCP and M-VIA (an implementation of the VIA specification) software for a mesh communication architecture to demonstrate the feasibility of using M-VIA as a point-to-point communication software, on which QMP-MVIA is based. Furthermore, we illustrate the design and implementation of QMP-MVIA for mesh connected Linux clusters with emphasis on both point-to-point and collective communications, and demonstrate that QMP-MVIA message passing system using GigE interconnects achieves bandwidth and latency that are not only better than systems based on TCP but also compare favorably to systems using some of the specialized high speed interconnects in a switched architecture at much lower cost.

We analyze the competitive ratio of two greedy online algorithms for routing permanent virtual circuits in a network with arbitrary topology and uniform capacity links. We show that the competitive ratio of the first algorithm, with respect to network congestion, is in and where m is the number of links in the network, 𝒟 is the maximum ratio, over all requests, of the length of the longest path for the request to the length of the shortest path for the request, and ℒ︁ is the ratio of the maximum-to-minimum bandwidth requirement. We show that the competitive ratio of the second greedy algorithm is in Ω(d + log(n −d)) and min{O(d log n), when the optimal route assignment is pairwise edge disjoint, where n is the number of network nodes and d is the length of the longest path that can be assigned to a request. It is known that the optimal competitive ratio for this problem is Θ(log n). Aspnes et al. designed a Θ(log n) competitive online algorithm that computes an exponential function of current congestion to make each decision. The greedy online algorithms, although not optimal, make each decision more quickly and still have good competitive ratios in many nontrivial situations. © 1999 John Wiley & Sons, Inc. Networks 34: 136–153, 1999

We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors {(xi, yi) ∣ i = 1, 2, …, k}, where (xi, yi) indicates that the ith message's recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this Isomorphic Routing. Our objective is to find the isomorphic routing schedule with the minimum makespan. We consider a number of variations on the problem, yielding complexity results from O(k) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.

The bin packing problem is to pack a list of reals in $( {0,1} ]$ into unit-capacity bins using the minimum number of bins. Let $R[A]$ be the limiting worst value for the ratio ${{A(L)} / {L^ * }}$ as $L^ * $ goes to $\infty $, where $A(L)$ denotes the number of bins used in the approximation algorithm A, and $L^ * $ denotes the minimum number of bins needed to pack L. Obviously, $R[A]$ reflects the worst-case behavior of A. For Next-k-Fit($NkF$ for short, $k \geqslant 2$), which is a linear time approximation algorithm for bin packing, it was known that $1.7 + \frac{3}{{10(k - 1)}} \leqslant R[NkF] \leqslant 2$. In this paper, a tight bound $R[NkF] = 1.7 + \frac{3}{{10(k - 1)}}$ is proved.