Recent advances in training-free attention control methods have enabled flexible and efficient text-guided editing capabilities for existing image and video generation models. However, current approaches struggle to simultaneously deliver strong editing strength while preserving consistency with the source. For instance, in color-editing tasks, they struggle to maintain structural consistency in edited regions while preserving the rest intact. This limitation becomes particularly critical in multi-round and video editing, where visual errors can accumulate over time. Moreover, most existing methods enforce global consistency, which limits their ability to modify individual attributes such as texture while preserving others, thereby hindering fine-grained editing. Recently, the architectural shift from U-Net to Multi-Modal Diffusion Transformers (MM-DiT) has brought significant improvements in generative performance and introduced a novel mechanism for integrating text and vision modalities. These advancements pave the way for overcoming challenges that previous methods failed to resolve. Through an in-depth analysis of MM-DiT, we identify three key insights into its attention mechanisms. Building on these, we propose ConsistEdit, a novel attention control method specifically tailored for MM-DiT. ConsistEdit incorporates vision-only attention control, mask-guided pre-attention fusion, and differentiated manipulation of the query, key, and value tokens to produce consistent, prompt-aligned edits. Extensive experiments demonstrate that ConsistEdit achieves state-of-the-art performance across a wide range of image and video editing tasks, including both structure-consistent and structure-inconsistent scenarios. Unlike prior methods, it is the first approach to perform editing across all inference steps and attention layers without handcraft, significantly enhancing reliability and consistency, which enables robust multi-round and multi-region editing. Furthermore, it supports progressive adjustment of structural consistency, enabling finer control. ConsistEdit represents a significant advancement in generative model editing and unlocks the full editing potential of MM-DiT architectures.

The field of artificial intelligence (AI) in quantitative investment has seen significant advancements, yet it lacks a standardized benchmark aligned with industry practices. This gap hinders research progress and limits the practical application of academic innovations. We present QuantBench, an industrial-grade benchmark platform designed to address this critical need. QuantBench offers three key strengths: (1) standardization that aligns with quantitative investment industry practices; (2) flexibility to integrate various AI algorithms; (3) full-pipeline coverage of the entire quantitative investment process. Our empirical studies using QuantBench reveal some critical research directions, including the need for continual learning to address distribution shifts, improved methods for modeling relational financial data, and more robust approaches to mitigate overfitting in low signal-to-noise environments. By providing a common ground for evaluation and fostering collaboration between researchers and practitioners, QuantBench aims to accelerate progress in AI for quantitative investment, similar to the impact of benchmark platforms in computer vision and natural language processing. The code is open-sourced on GitHub at https://github.com/SaizhuoWang/quantbench .

Although large language models (LLMs) have achieved significant success in various tasks, they often struggle with hallucination problems, especially in scenarios requiring deep and responsible reasoning. These issues could be partially addressed by introducing external knowledge graphs (KG) in LLM reasoning. In this paper, we propose a new LLM-KG integrating paradigm ``$\hbox{LLM}\otimes\hbox{KG}$'' which treats the LLM as an agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. We further implement this paradigm by introducing a new approach called Think-on-Graph (ToG), in which the LLM agent iteratively executes beam search on KG, discovers the most promising reasoning paths, and returns the most likely reasoning results. We use a number of well-designed experiments to examine and illustrate the following advantages of ToG: 1) compared with LLMs, ToG has better deep reasoning power; 2) ToG has the ability of knowledge traceability and knowledge correctability by leveraging LLMs reasoning and expert feedback; 3) ToG provides a flexible plug-and-play framework for different LLMs, KGs and prompting strategies without any additional training cost; 4) the performance of ToG with small LLM models could exceed large LLM such as GPT-4 in certain scenarios and this reduces the cost of LLM deployment and application. As a training-free method with lower computational cost and better generality, ToG achieves overall SOTA in 6 out of 9 datasets where most previous SOTAs rely on additional training.

Quantitative investment (abbreviated as “quant” in this paper) is an interdisciplinary field combining financial engineering, computer science, mathematics, statistics, etc. Quant has become one of the mainstream investment methodologies over the past decades, and has experienced three generations: quant 1.0, trading by mathematical modeling to discover mis-priced assets in markets; quant 2.0, shifting the quant research pipeline from small “strategy workshops” to large “alpha factories”; quant 3.0, applying deep learning techniques to discover complex nonlinear pricing rules. Despite its advantage in prediction, deep learning relies on extremely large data volume and labor-intensive tuning of “black-box” neural network models. To address these limitations, in this paper, we introduce quant 4.0 and provide an engineering perspective for next-generation quant. Quant 4.0 has three key differentiating components. First, automated artificial intelligence (AI) changes the quant pipeline from traditional hand-crafted modeling to state-of-the-art automated modeling and employs the philosophy of “algorithm produces algorithm, model builds model, and eventually AI creates AI.” Second, explainable AI develops new techniques to better understand and interpret investment decisions made by machine learning black boxes, and explains complicated and hidden risk exposures. Third, knowledge-driven AI supplements data-driven AI such as deep learning and incorporates prior knowledge into modeling to improve investment decisions, in particular for quantitative value investing. Putting all these together, we discuss how to build a system that practices the quant 4.0 concept. We also discuss the application of large language models in quantitative finance. Finally, we propose 10 challenging research problems for quant technology, and discuss potential solutions, research directions, and future trends.

We present in this paper a novel denoising training method to speed up DETR (DEtection TRansformer) training and offer a deepened understanding of the slow convergence issue of DETR-like methods. We show that the slow convergence results from the instability of bipartite graph matching which causes inconsistent optimization goals in early training stages. To address this issue, except for the Hungarian loss, our method additionally feeds GT bounding boxes with noises into the Transformer decoder and trains the model to reconstruct the original boxes, which effectively reduces the bipartite graph matching difficulty and leads to faster convergence. Our method is universal and can be easily plugged into any DETR-like method by adding dozens of lines of code to achieve a remarkable improvement. As a result, our DN-DETR results in a remarkable improvement ( +1.9AP) under the same setting and achieves 46.0 AP and 49.5 AP trained for 12 and 50 epochs with the ResNet-50 backbone. Compared with the baseline under the same setting, DN-DETR achieves comparable performance with 50% training epochs. We also demonstrate the effectiveness of denoising training in CNN-based detectors (Faster R-CNN), segmentation models (Mask2Former, Mask DINO), and more DETR-based models (DETR, Anchor DETR, Deformable DETR).

In this paper we present Mask DINO, a unified object detection and segmentation framework. Mask DINO extends DINO (DETR with Improved Denoising Anchor Boxes) by adding a mask prediction branch which supports all image segmentation tasks (instance, panoptic, and semantic). It makes use of the query embeddings from DINO to dot-product a high-resolution pixel embedding map to predict a set of binary masks. Some key components in DINO are extended for segmentation through a shared architecture and training process. Mask DINO is simple, efficient, and scalable, and it can benefit from joint large-scale detection and segmentation datasets. Our experiments show that Mask DINO significantly outperforms all existing specialized segmentation methods, both on a ResNet-50 backbone and a pre-trained model with SwinL backbone. Notably, Mask DINO establishes the best results to date on instance segmentation (54.5 AP on COCO), panoptic segmentation (59.4 PQ on COCO), and semantic segmentation (60.8 mIoU on ADE20K) among models under one billion parameters. Code is available at https://github.com/IDEA-Research/MaskDINO.

Recent DEtection TRansformer-based (DETR) models have obtained remarkable performance. Its success cannot be achieved without the re-introduction of multi-scale feature fusion in the encoder. However, the excessively increased tokens in multi-scale features, especially for about 75% of low-level features, are quite computationally inefficient, which hinders real applications of DETR models. In this paper, we present Lite DETR, a simple yet efficient end-to-end object detection framework that can effectively reduce the GFLOPs of the detection head by 60% while keeping 99% of the original performance. Specifically, we design an efficient encoder block to update high-level features (corresponding to small-resolution feature maps) and low-level features (corresponding to large-resolution feature maps) in an interleaved way. In addition, to better fuse cross-scale features, we develop a key-aware deformable attention to predict more reliable attention weights. Comprehensive experiments validate the effectiveness and efficiency of the proposed Lite DETR, and the efficient encoder strategy can generalize well across existing DETR-based models. The code will be available in https://github.com/IDEA-Research/Lite-DETR.

We present a mask-piloted Transformer which improves masked-attention in Mask2Former for image segmentation. The improvement is based on our observation that Mask2Former suffers from inconsistent mask predictions between consecutive decoder layers, which leads to inconsistent optimization goals and low utilization of decoder queries. To address this problem, we propose a mask-piloted training approach, which additionally feeds noised ground-truth masks in masked-attention and trains the model to reconstruct the original ones. Compared with the predicted masks used in mask-attention, the ground-truth masks serve as a pilot and effectively alleviate the negative impact of inaccurate mask predictions in Mask2Former. Based on this technique, our MP-Former achieves a remarkable performance improvement on all three image segmentation tasks (instance, panoptic, and semantic), yielding +2.3AP and +1.6mIoU on the Cityscapes instance and semantic segmentation tasks with a ResNet-50 backbone. Our method also significantly speeds up the training, outperforming Mask2Former with half of the number of training epochs on ADE20K with both a ResNet-50 and a Swin-L backbones. Moreover, our method only introduces little computation during training and no extra computation during inference. Our code will be released at https://github.com/IDEA-Research/MP-Former.

We present in this paper a novel denoising training method to speedup DETR (DEtection TRansformer) training and offer a deepened understanding of the slow convergence issue of DETR-like methods. We show that the slow convergence results from the instability of bipartite graph matching which causes inconsistent optimization goals in early training stages. To address this issue, except for the Hungarian loss, our method additionally feeds ground-truth bounding boxes with noises into Transformer decoder and trains the model to reconstruct the original boxes, which effectively reduces the bipartite graph matching difficulty and leads to a faster convergence. Our method is universal and can be easily plugged into any DETR-like methods by adding dozens of lines of code to achieve a remarkable improvement. As a result, our DN-DETR results in a remarkable improvement (+1.9AP) under the same setting and achieves the best result (AP 43.4 and 48.6 with 12 and 50 epochs of training respectively) among DETR-like methods with ResNet-50 backbone. Compared with the baseline under the same setting, DN-DETR achieves comparable performance with 50% training epochs. Code is available at https://github.com/FengLi-ust/DN-DETR.

Learning human mobility behaviors from location-sensing data are crucial to mobility data mining because of its potential to address a range of analytical purposes in mobile context reasoning, including exploration, inference, and prediction. However, existing approaches suffer from two practical problems: temporal and spatial sparsity. To address these shortcomings, we present two unsupervised learning methods to model the mobility behaviors of multiple users (i.e., a population), considering efficiency and accuracy. These methods intelligently overcome the sparsity in individual data by seeking temporal commonality among users’ heterogeneous location behaviors. The advantages of our models are highlighted through experiments on several real-world mobility data sets, which also show how our methods can realize the three analytical purposes in a unified manner.

A passenger is overcharged by the taxi driver is one common type of fraudulent trip, and it brings negative impacts to modern cities. Most existing fraudulent trip detection works rely on the assumption that the trip is correctly recorded by the taximeter. However, there are many taxi drivers in China carrying passengers without activating the taximeter, especially when the taxi driver is trying to overcharge the passengers. Hence, existing detection methods cannot be directly applied to such real-world scenario. In this article, we propose a system, called “FraudTrip,” which detects “unmetered” taxi trips based on a novel fraud detection algorithm and a heuristic maximum fraudulent trajectory construction algorithm. Based on the experiments on both synthetic and real-world trajectory data sets, FraudTrip can effectively and efficiently detect fraudulent trips without the help of taximeters.

Convolutional sparse coding (CSC) can learn representative shift-invariant patterns from multiple kinds of data. However, existing CSC methods can only model noises from Gaussian distribution, which is restrictive and unrealistic. In this paper, we propose a generalized CSC model capable of dealing with complicated unknown noise. The noise is now modeled by Gaussian mixture model, which can approximate any continuous probability density function. We use the expectation-maximization algorithm to solve the problem and design an efficient method for the weighted CSC problem in maximization step. The crux is to speed up the convolution in the frequency domain while keeping the other computations involving weight matrix in the spatial domain. Besides, we simultaneously update the dictionary and codes by nonconvex accelerated proximal gradient algorithm without bringing in extra alternating loops. The resultant method, called generalized convolutional sparse coding (GCSC), obtains the same space complexity and a smaller running time compared with existing CSC methods. Extensive experiments on synthetic and real-world noisy data sets validate that GCSC can model noise effectively and obtain high-quality filters and representations.

A novel scheme of edge detection based on the physical law of diffusion is presented in this paper. Though the most current studies are using data based methods such as deep neural networks, these methods on machine learning need big data of labeled ground truth as well as a large amount of resources for training. On the other hand, the widely used traditional methods are based on the gradient of the grayscale or color of images with using different sorts of mathematical tools to accomplish the mission. Instead of treating the outline of an object in an image as a kind of gradient of grayscale or color, our scheme deals with the edge detection as a character of an energy diffusing in the space of media such as charge-coupled device. By using the characteristic function of diffusion, the information of the energy will be extracted. The scheme preserves the structural information of images very well. Because it comes from the inhere law of images' physical property, it has a unified mathematical framework for images' edge detection under different conditions, for example, multiscales, diferent light conditions, and so on. Moreover, it has low computational complexity.

Efficient spectrum sensing is essential for the successful application of the Dynamic Spectrum Assignment (DSA) technology in Cognitive Radio Networks (CRNs). In conventional spectrum sensing schemes, secondary users (SUs) have to intelligently schedule their sensing and accessing so that the spectrum opportunities are thoroughly exploited while the primary users are not harmed. In this article, we propose a new sensing service model in which a Spectrum Sensor Network (SSN) is employed for spectrum sensing tasks. We will describe the general framework for this SSN-enabled CRN and present the major challenges in such an architecture. We will address one of these challenges and formulate it as a boundary detection problem with unknown erroneous inputs. A novel cooperative boundary detection algorithm is designed which explores recent advances in Support Vector Machines (SVM) and computational geometry. We prove that cooperative spectrum sensing can asymptotically approach the optimal solution. Real testbed as well as comprehensive simulation experiments are conducted, and the results show that, compared with the traditional schemes, cooperative boundary detection can dramatically reduce the spectrum sensing overhead and improve the effectiveness of DSA.

Profiling driver behaviors and designing appropriate pricing models are essential for auto insurance companies to gain profits and attract customers (drivers). The existing approaches either rely on static demographic information like age, or model only coarse-grained driving behaviors. They are therefore ineffective to yield accurate risk predictions over time for appropriate pricing, resulting in profit decline or even financial loss. Moreover, existing pricing strategies seldom take profit maximization into consideration, especially under the enterprise constraints. The recent growth of vehicle telematics data (vehicle sensing data) brings new opportunities to auto insurance industry, because of its sheer size and fine-grained mobility for profiling drivers. But, how to fuse these sparse, inconsistent and heterogeneous data is still not well addressed. To tackle these problems, we propose a unified PPP (Profile-Price-Profit) framework, working on the real-world large-scale vehicle telematics data and insurance data. PPP profiles drivers' fine-grained behaviors by considering various driving features from the trajectory perspective. Then, to predict drivers' risk probabilities, PPP leverages the group-level insight and categorizes drivers' different temporal risk change patterns into groups by ensemble learning. Next, the pricing model in PPP incorporates both the demographic analysis and the mobility factors of driving risk and mileage, to generate personalized insurance price for supporting flexible premium periods. Finally, the maximal profit problem proves to be NP-Complete. Then, an efficient heuristic-based dynamic programming is proposed. Extensive experimental results demonstrated that, PPP effectively predicts the driver's risk and outperforms the current company's pricing strategy (in industry) and the state-of-the-art approach. PPP also achieves near the maximal profit (difference by only 3%) for the company, and lowers the total price for the drivers.

Convolutional sparse coding (CSC) has been popularly used for the learning of shift-invariant dictionaries in image and signal processing. However, existing methods have limited scalability. In this paper, instead of convolving with a dictionary shared by all samples, we propose the use of a sample-dependent dictionary in which each filter is a linear combination of a small set of base filters learned from data. This added flexibility allows a large number of sample-dependent patterns to be captured, which is especially useful in the handling of large or high-dimensional data sets. Computationally, the resultant model can be efficiently learned by online learning. Extensive experimental results on a number of data sets show that the proposed method outperforms existing CSC algorithms with significantly reduced time and space complexities.

The Big Data era and intelligent educational systems have empowered personalized learning. As one of the most effective personalized learning tools, Recommender Systems (RS) are applied for student performance prediction, and personalized content replenishment for learning remediation. A wide variety of context-aware RS for personalized learning have been devised and implemented, adherent with student's learning contexts such as location, time, and activity. Due to the physical constraints, today's education is still carried out at schools, making classes the indispensable and easily achievable context. Leveraging such information can be beneficial for performance improvement and effective learning recommendation in common classroom settings. In this work, we propose a novel approach, `Class Contextual Factor' (CCF)-based RS that synthesizes students' personal and class-level factors for better performances. More specifically, we first derive the CCF from a weighted Q-matrix to estimate students' mastery levels over KCs using an attribute-based recommendation technique. Then, we ensemble an item-based collaborative filtering algorithm for remedial exercise recommendation. By using a real world dataset from an online intelligent tutoring system, evaluations show that our CCF -based method outperforms the popular counterparts (i.e., IRT, RS with collaborative filtering), and is able to provide interpretable results for traceable learning remediation.

Convolutional sparse coding (CSC) improves sparse coding by learning a shift-invariant dictionary from the data. However, most existing CSC algorithms operate in the batch mode and are computationally expensive. In this paper, we alleviate this problem by online learning. The key is a reformulation of the CSC objective so that convolution can be handled easily in the frequency domain, and much smaller history matrices are needed. To solve the resultant optimization problem, we use the alternating direction method of multipliers (ADMMs), and its subproblems have efficient closed-form solutions. Theoretical analysis shows that the learned dictionary converges to a stationary point of the optimization problem. Extensive experiments are performed on both the standard CSC benchmark data sets and much larger data sets such as the ImageNet. Results show that the proposed algorithm outperforms the state-of-the-art batch and online CSC methods. It is more scalable, has faster convergence, and better reconstruction performance.

Many trajectory-based applications require an essential step of mapping raw GPS trajectories onto the digital road network accurately. This task, commonly referred to as map matching, is challenging due to the measurement error of GPS devices in critical environment and the sampling error caused by long sampling intervals. Traditional algorithms focus on either a local or a global perspective to deal with the problem. To further improve the performance, this paper develops a novel map matching model that considers local geometric/topological information and a global similarity measure simultaneously. To accomplish the optimization goal in this complex model, we adopt an ant colony optimization algorithm that mimics the path finding process of ants transporting food in nature. The algorithm utilizes both local heuristic and global fitness to search the global optimum of the model. Experimental results verify that the proposed algorithm is able to provide accurate map matching results within a relatively short execution time.

In modern big data warehouse systems, we observe a common phenomenon that a column of data values can be derived from one or several other columns by transforming and concatenating these columns. We call this relationship between columns a Soft Concatenation Mapping (SCM). SCMs imply significant redundancy in the schema or data, and therefore can be exploited for data integration or data compression. In this paper, we formalize the problem of SCM detection and prove it is NP-hard. We then propose efficient approximate algorithms to detect all SCMs or an optimal set of SCMs in a table. Our experiments on both real-world and synthetic datasets show promising results.

The wireless network that integrates a heterogeneous cellular network and a WLAN is referred to as a WLAN/cellular integrated network (WCIN). In a fourth generation WCIN, in order to achieve collision-avoidance between the LTE-A and IEEE 802.11 family, some interference-free mechanisms, such as carrier sense adaptive transmission and listen-before-talk, are proposed. However, the interference-free medium access mechanisms leave some unexploited partially overlapped 802.11ac channels, which result in a waste of spectrum. In this paper, we propose an interference-tolerant medium access method to optimize the WCIN throughput by utilizing those partially overlapped channels (POCs). First, we show the feasibility of enhancing WLAN throughput by utilizing 802.11ac POCs in a WCIN. Second, we mathematically model the partial overlap when an 802.11ac channel is partially overlapping with an LTE-A component carrier. Third, we propose an interference-tolerant medium access mechanism to optimize the WCIN throughput. The interference-tolerant one ensures that the interference to LTE-A users is tolerable in a given WCIN. Finally, we construct a hardware-in-the-loop testbed to evaluate and compare our proposed mechanism with three other state-of-the-art mechanisms. The experimental results show that our approach achieves at most 39% more throughput than one of the state-of-the-art collision-avoidance mechanisms regarding the entire WCIN.

With the acceleration of urbanization and modern civilization, more and more complex regions are formed in urban area. Although understanding these regions could provide huge insights to facilitate valuable applications for urban planning and business intelligence, few methods have been developed to effectively capture the rapid transformation of urban regions. In recent years, the widely applied location-acquisition technologies offer a more effective way to capture the dynamics of a city through analyzing people's movement activities based on mobility data. However, several challenges exist, including data sparsity and difficulties in result understanding and validation. To tackle these challenges, in this paper, we propose MobiSeg, an interactive visual analytics system, which supports the exploration of people's movement activities to segment the urban area into regions sharing similar activity patterns. A joint analysis is conducted on three types of heterogeneous mobility data (i.e., taxi trajectories, metro passenger RFID card data, and telco data), which can complement each other and provide a full picture of people's activities in a region. In addition, advanced analytical algorithms (e.g., non-negative matrix factorization (NMF) based method to capture latent activity patterns, as well as metric learning to calibrate and supervise the underlying analysis) and novel visualization designs are integrated into our system to provide a comprehensive solution to region segmentation in urban areas. We demonstrate the effectiveness of our system via case studies with real-world datasets and qualitative interviews with domain experts.

Strategy design and analysis is important in team sports, such as basketball and soccer. In this paper, we take basketball as an example and study how to cluster movement trajectories in the games to identify the strategies. This problem is challenging in that the trajectories are diverse and that it is unknown how many or what strategies are employed in the games. As a result, traditional parametric clustering methods are not directly applicable to the raw trajectory data. Therefore, we propose to align trajectories around the basket and simplify them based on movement directions and game events, including dribbling, passing, and shooting. Furthermore, we propose a non-parametric density peak (NPDP) method to cluster these simplified event trajectories. Our experiments on an NBA game dataset of 50,000 offenses show that, without parameter tuning, NPDP clusters all trajectories into groups of high similarity and identifies distinguishing movement strategies.

Taxi fraud has become a serious problem in many large cities, where passengers are overcharged by taxi drivers in various ways. Researchers have developed a number of methods to detect taxi frauds with the assumption that fraudulent trips, among normal trips, are recorded by taximeters. In this paper, different from the previous work, we identify a new type of taxi fraud called unmetered taxi rides, where taxi drivers carry passengers without activating the taximeters. Since these fraudulent rides are not recorded by taximeters, previous detection approaches cannot directly apply to them. Hence, we propose a novel fraud detection system specifically designed for unmetered taxi rides. Our system uses a learning model to detect unmetered trajectory segments that are similar to metered rides, and introduces a heuristic algorithm to construct maximum fraudulent trajectories from the trajectory dataset. We have conducted detailed experiments on real-world datasets, and the results show that the proposed system can detect unmetered taxi rides effectively and efficiently.

In this paper, we present TICC, an automatic data compression component that can transparently eliminate data redundancies across columns in column-oriented database systems. We further propose two approaches to integrate inter-column compression into existing database systems. One approach is to use User Defined Functions (UDFs), and the other is native. We implement these two approaches on top of Hive based on the ORC file, a common data format in column stores, and evaluate the performance of TICC using real-world datasets. The experimental results demonstrate that TICC can significantly reduce the storage overhead and process a variety of queries over large-scale data with up to 20% performance improvement over the original Hive.

Active learning has been widely used to select the most informative data for labeling in classification tasks, except for time series classification. The main challenge of active learning in time series classification is to evaluate the informativeness of a time series instance. Specifically, many informativeness metrics have been proposed for traditional active learning, however, none of them is particularly effective on time series data. In this paper, we design an informativeness metric that considers the characteristics of time series data in defining our instance uncertainty and utility. We prove that our informativeness metric is a submodular set function, and further develop an effective and efficient algorithm to select the most informative time series instances for training. In the experiment, we validate our method on a variety of datasets in the UCR Time Series Data Archive. The results show that our method achieves a higher classification accuracy than existing methods, using only 50% of the training instances.

Attributes are human-annotated semantic descriptions of label classes. In zero-shot learning (ZSL), they are often used to construct a semantic embedding for knowledge transfer from known classes to new classes. While collecting all attributes for the new classes is criticized as expensive, a subset of these attributes are often easy to acquire. In this paper, we extend ZSL methods to handle this partial set of observed attributes. We first recover the missing attributes through structured matrix completion. We use the low-rank assumption, and leverage properties of the attributes by extracting their rich semantic information from external sources. The resultant optimization problem can be efficiently solved with alternating minimization, in which each of its subproblems has a simple closed-form solution. The predicted attributes can then be used as semantic embeddings in ZSL. Experimental results show that the proposed method outperform existing methods in recovering the structured missing matrix. Moreover, methods using our predicted attributes in ZSL outperforms methods using either the partial set of observed attributes or other semantic embeddings.

Object differentiation plays a vital role in our daily life and such systems are widely deployed with RFID tags or bar codes attached on goods. In certain scenarios, however, attaching tags to objects may be impractical due to cost and protection issues. In this paper, we propose TagFree, a novel object differentiation scheme without attaching tags. Instead of relying on external tags, we exploit the inherent radiometric properties of different objects as their signatures. To improve the robustness and efficiency of TagFree, we empirically determine a spatial safe zone and harness successive cancellation to distinguish multiple objects simultaneously. We prototype TagFree on commercial WiFi infrastructure and evaluate its performance in various indoor scenarios. Experimental results demonstrate that TagFree achieves single object distinguishing accuracy of 96% measured at the same location, and over 80% within the safe zone range of up to 3m along a 7m link. TagFree can also differentiate up to 3 objects with acceptable accuracy.

In this work, we focus on two fundamental questions that are unprecedentedly important to urban planners to understand the functional characteristics of various urban regions throughout a city, namely, (i) how to identify regional weather-traffic sensitivity index throughout a city, that indicates the degree to which the region traffic in a city is impacted by weather changes; (ii) among complex regional features, such as road structure and population density, how to dissect the most influential regional features that drive the urban region traffic to be more vulnerable to weather changes. However, these two questions are nontrivial to answer, because urban traffic changes dynamically over time and is essentially affected by many other factors, which may dominate the overall impact. We make the first study on these questions, by developing a weather-traffic index (WTI) system. The system includes two main components: weather-traffic index establishment and key factor analysis. Using the proposed system, we conducted comprehensive empirical study in Shanghai, and the weather-traffic indices extracted have been validated to be surprisingly consistent with real world observations. Further regional key factor analysis yields interesting results. For example, house age has significant impact on the weather-traffic index, which sheds light on future urban planning and reconstruction.

Among various ranging techniques, Radio Signal Strength (RSS) based approaches attract intensive research interests because of its low cost and wide applicability. RSS-based ranging is prone to be affected by the multipath phenomenon which allows the radio signals to reach the destination through multiple propagation paths. To address this issue, previous works try to profile the environment and refer this profile during run-time. In a practical dynamic environment, however, the profile frequently changes and the painful retraining is needed. Ratherthan such static ways of profiling the environments, in this paper, we tryto accommodate the environmental dynamics automatically in real-time. The key observation is that given a pair of nodes, the RSS at different spectrum channels will be different. This difference carries the valuable phase information of the radio signals. By analyzing these RSS values, we are able to identify the amplitude of signals solely from the Line-of-Sight (LOS) path. This LOS amplitude is a simple function of the path length (the physical distance). We find that the analysis is a typical non-linear curvature fitting problem that has no general routing algorithms. We prove that, this problem format is ill-conditioned which has no stable and trustable solutions. To deal with this issue, we further explore the practical considerations for the problem and modify it to a greatly improved conditioning shape. We solve the problem by numerical iterations and implement these ideas in a real-time indoor tracking system called MuD. MuD employs only three TelosB nodes as anchors. The experiment results show that in a dynamic environment where five people move around, the averaged localization error is about 1 meter. Compared with the traditional RSS-based approaches in dynamic environments, the accuracy improves up to 10 times.

Injuries that are caused by falls have been regarded as one of the major health threats to the independent living for the elderly. Conventional fall detection systems have various limitations. In this work, we first look for the correlations between different radio signal variations and activities by analyzing radio propagation model. Based on our observation, we propose WiFall, a truly unobtrusive fall detection system. WiFall employs physical layer Channel State Information (CSI) as the indicator of activities. It can detect fall of the human without hardware modification, extra environmental setup, or any wearable device. We implement WiFall on desktops equipped with commodity 802.11n NIC, and evaluate the performance in three typical indoor scenarios with several layouts of transmitter-receiver (Tx-Rx) links. In our area of interest, WiFall can achieve fall detection for a single person with high accuracy. As demonstrated by the experimental results, WiFall yields 90 percent detection precision with a false alarm rate of 15 percent on average using a one-class SVM classifier in all testing scenarios. It can also achieve average 94 percent fall detection precisions with 13 percent false alarm using Random Forest algorithm.

Gesture recognition has emerged recently as a promising application in our daily lives. Owing to low cost, prevalent availability, and structural simplicity, RFID shall become a popular technology for gesture recognition. However, the performance of existing RFID-based gesture recognition systems is constrained by unfavorable intrusiveness to users, requiring users to attach tags on their bodies. To overcome this, we propose GRfid, a novel device-free gesture recognition system based on phase information output by COTS RFID devices. Our work stems from the key insight that the RFID phase information is capable of capturing the spatial features of various gestures with low-cost commodity hardware. In GRfid, after data are collected by hardware, we process the data by a sequence of functional blocks, namely data preprocessing, gesture detection, profiles training, and gesture recognition, all of which are well-designed to achieve high performance in gesture recognition. We have implemented GRfid with a commercial RFID reader and multiple tags, and conducted extensive experiments in different scenarios to evaluate its performance. The results demonstrate that GRfid can achieve an average recognition accuracy of 96.5 and 92.8 percent in the identical-position and diverse-positions scenario, respectively. Moreover, experiment results show that GRfid is robust against environmental interference and tag orientations.

Big trajectory data introduces severe challenges for data storage and communication. In this paper, we propose a novel compression framework called Clockwise Compression Framework (CCF) for big trajectory data compression under road network constraints. In CCF, we design several new methods: 1) a spatial compression algorithm called Enhanced Clockwise Encoding (ECE), 2) a temporal compression algorithm called Fitting-based Temporal Simplification (FTS), and 3) a dedicated querier that processes queries based on the above spatial and temporal compression algorithms, without fully decompressing the trajectroy data. By leveraging the topological information of the road network, CCF is able to perform both spatial compression and temporal compression in on-line modes. We perform extensive experiments in a real big trajectory dataset to verify both effectiveness and efficiency of our methods. CCF shows promising performances in various metrics and outperforms the state-of-the-art methods.

Collective behavior is an important concept defined to capture behavioral patterns emerged among the crowd spontaneously. In social science, people's behaviors can be regarded as temporal transitions between a set of typical states (e.g., home and work) which are always associated with certain locations. This fact leads to an interesting research topic in developing ways to explore people's collective behavior patterns through movement analysis, which is our focus in this paper. In recent years, massive volumes of spatiotemporal data generated by mobile phones, called telco data, bring an unprecedented opportunity to study collective behaviors in terms of large coverage and fine-grained resolution. However, distilling valuable collective behavior patterns from the large scale of telco data is not an easy task. The challenge is rooted in two aspects, including the data uncertainty as well as the lack of methods to characterize, compare and understand dynamic crowd behaviors, which triggers the use of visual analytics to take full advantage of machines' computational power as well as human's domain knowledge and cognitive abilities. In this paper, we propose TelcoFlow, a comprehensive visual analytics system which incorporates advanced quantitative analyses (e.g., statebased behavior model) and intuitive visualizations (e.g., an extended flow view embedded with state glyphs) to support an efficient and in-depth analysis of collective behaviors based on telco data. Case studies with a real-world dataset and expert interviews are carried out to demonstrate the effectiveness of our system for analysts to gain insights into collective behaviors and facilitate various analytical tasks.

Nowadays, various data collected in urban context provide unprecedented opportunities for building a smarter city through urban computing. However, due to heterogeneity, high complexity and large volumes of these urban data, analyzing them is not an easy task, which often requires integrating human perception in analytical process, triggering a broad use of visualization. In this survey, we first summarize frequently used data types in urban visual analytics, and then elaborate on existing visualization techniques for time, locations and other properties of urban data. Furthermore, we discuss how visualization can be combined with automated analytical approaches. Existing work on urban visual analytics is categorized into two classes based on different outputs of such combinations: 1) For data exploration and pattern interpretation, we describe representative visual analytics tools designed for better insights of different types of urban data. 2) For visual learning, we discuss how visualization can help in three major steps of automated analytical approaches (i.e., cohort construction; feature selection & model construction; result evaluation & tuning) for a more effective machine learning or data mining process, leading to sort of artificial intelligence, such as a classifier, a predictor or a regression model. Finally, we outlook the future of urban visual analytics, and conclude the survey with potential research directions.

Channel condition varies frequently in wireless networks. To achieve good performance, devices need rate adaptation. In rate adaptation, choosing proper modulation schemes based on channel conditions is vital to the transmission performance. However, due to the natural character of discrete modulation types and continuous varied link conditions, we cannot make a one-to-one mapping from modulation schemes to channel conditions. This matching gap causes either over-select or under-select modulation schemes which limits throughput performance. To fill-in the gap, we propose time-line modulation (TiM), a novel three-Dimensional modulation scheme by adding time dimension into current amplitude-phase domain schemes. With estimation of channel condition, TiM changes base-band data transmission time by artificially interpolating values between original data points without changing amplitude-phase domain modulation type. We implemented TiM on USRP2 and conducted comprehensive simulations. Results show that, compared with rate adaptation choosing from traditional modulation schemes, TiM can improve channel utilization up to 200 percent.

Recent literature advances Wi-Fi signals to “see” people's motions and locations. This paper asks the following question: Can Wi-Fi “hear” our talks? We present WiHear, which enables Wi-Fi signals to “hear” our talks without deploying any devices. To achieve this, WiHear needs to detect and analyze fine-grained radio reflections from mouth movements. WiHear solves this micro-movement detection problem by introducing Mouth Motion Profile that leverages partial multipath effects and wavelet packet transformation. Since Wi-Fi signals do not require line-of-sight, WiHear can “hear” people talks within the radio range. Further, WiHear can simultaneously “hear” multiple people's talks leveraging MIMO technology. We implement WiHear on both USRP N210 platform and commercial Wi-Fi infrastructure. Results show that within our pre-defined vocabulary, WiHear can achieve detection accuracy of 91 percent on average for single individual speaking no more than six words and up to 74 percent for no more than three people talking simultaneously. Moreover, the detection accuracy can be further improved by deploying multiple receivers from different angles.

Seeing through walls and knowing clearly what exist inside just like a superman are not only fantastic wishes for humans, but also of much practical significance. For example, you would like to know whether there are pipes, or rebars inside a wall before drilling into it. Moreover, knowing how pipes are configured in a wall before attempting to fix defects would definitely prevent unnecessary damages. Existing methods that intend to address this issue are either costly due to the use of high-end technology, or restrictive for reasons of some strong assumptions. However, in this paper, we present a novel system, SmartScanner, which is based on off-the-shelf sensors embedded in a smartphone. SmartScanner makes full use of in-built sensors, namely, the accelerometer, gyroscope, and magnetometer to achieve this goal inexpensively and conveniently. Specifically, by combining these sensors, we are able to clearly distinguish certain objects inside a wall and map out the layout of an in-wall pipeline system. We implement SmartScanner on two smartphone platforms, namely iPhone 4 and Xiaomi Mi2S, and conduct extensive experiments to evaluate its performance. Experiments show that SmartScanner can achieve high accuracies in distinguishing objects in various scenarios. Meanwhile, as for layout mapping, 90 percent of length errors are limited to several centimeters for horizontal and vertical pipeline segments, respectively. Also, SmartScanner can achieve centimeter-level position errors of turning points in horizontal and vertical directions in the testbed.

Understanding co-occurrence in urban human mobility (i.e. people from two regions visit an urban place during the same time span) is of great value in a variety of applications, such as urban planning, business intelligence, social behavior analysis, as well as containing contagious diseases. In recent years, the widespread use of mobile phones brings an unprecedented opportunity to capture large-scale and fine-grained data to study co-occurrence in human mobility. However, due to the lack of systematic and efficient methods, it is challenging for analysts to carry out in-depth analyses and extract valuable information. In this paper, we present TelCoVis, an interactive visual analytics system, which helps analysts leverage their domain knowledge to gain insight into the co-occurrence in urban human mobility based on telco data. Our system integrates visualization techniques with new designs and combines them in a novel way to enhance analysts' perception for a comprehensive exploration. In addition, we propose to study the correlations in co-occurrence (i.e. people from multiple regions visit different places during the same time span) by means of biclustering techniques that allow analysts to better explore coordinated relationships among different regions and identify interesting patterns. The case studies based on a real-world dataset and interviews with domain experts have demonstrated the effectiveness of our system in gaining insights into co-occurrence and facilitating various analytical tasks.

The availability of massive volumes of trajectory data has made it convenient for the study of different types of movement behaviors. Among them, bi-directional movement behaviors exist ubiquitously in our daily life, from urban traffic to animal migration, and from sports to wars. To analyze bi-directional movement behaviors, people need to compare movements in two directions simultaneously for detecting similarities or differences in the movement patterns. If the movement involves tens of thousands items like vehicles or bird migration during a ten-year time span, the comparisons need to be done at both macro level and micro level. Due to the complexities of data and the challenges of analytical tasks, visual analytics is often used to take full advantage of machines' computational power as well as human's domain knowledge and cognitive abilities. In this paper, we present a comprehensive visual analytics system with three major visualization modules, including Global View, OD-pair Flow View and Isotime Storyline View, to depict bi-directional movement behaviors in a novel way, which enables a three-level exploration to help users gain insights into both macro and micro patterns. Quantitative analyses (e.g. movement model construction, modular Dol specification and key node extraction) and intuitive visualizations (e.g. parallelized flow map, bidirectional storyline chart with contour map and multi-layer heat map) are integrated into our system to provide an efficient and intuitive solution to the analysis of bi-directional movement behaviors based on big movement data. Case studies with two real-world datasets and expert interviews are carried out to demonstrate the effectiveness and usefulness of our system.

This paper studies the critical problem of maximizing the aggregate data utility under the practical constraint on budget in mobile crowd sourced sensing. This problem is particularly challenging given the redundancy in sensing data, self-interested and strategic user behaviors, private cost information of smartphones and budget constraint. In this paper, we propose a combinatorial auction mechanism based on a redundancy-aware reverse auction framework. It consists of an approximation algorithm for winning bids determination and a critical payment scheme. Our mechanism achieves truthfulness, individual rationality, computational efficiency, budget feasibility and high redundancy-aware data utility.

Wireless-based device-free human sensing has raised increasing research interest and stimulated a range of novel location-based services and human-computer interaction applications for recreation, asset security and elderly care. A primary functionality of these applications is to first detect the presence of humans before extracting higher-level contexts such as physical coordinates, body gestures, or even daily activities. In the presence of dense multipath propagation, however, it is non-trivial to even reliably identify the presence of humans. The multipath effect can invalidate simplified propagation models and distort received signal signatures, thus deteriorating detection rates and shrinking detection range. In this paper, we characterize the impact of human presence on wireless signals via ray-bouncing models, and propose a measurable metric on commodity WiFi infrastructure as a proxy for detection sensitivity. To achieve higher detection rate and wider sensing coverage in multipath-dense indoor scenarios, we design a lightweight sub carrier and path configuration scheme harnessing frequency diversity and spatial diversity. We prototype our scheme with standard WiFi devices. Evaluations conducted in two typical office environments demonstrate a detection rate of 92.0% with a false positive of 4.5%, and almost 1x gain in detection range given a minimal detection rate of 90%.

The impact of inclement weather to urban traffic has been widely observed and studied for many years, with focus primarily on individual road segments by analyzing data from roadside deployed monitors. However, two fundamental questions are still open: (i) how to identify regional weather-traffic sensitivity index throughout a city, that indicates the degree to which the region traffic in a city is impacted by weather changes, (ii) among complex regional features, such as road structure and population density, how to dissect the most influential regional features that drive the urban region traffic to be more vulnerable to weather changes. Answering these questions is unprecedentedly important for urban planners to understand the functional characteristics of various urban regions throughout a city, and to improve traffic prediction and learn the key factors in urban planning. However, these two questions are nontrivial to answer, because urban traffic changes dynamically over time and is essentially affected by many other factors, which may dominate the overall impact. In this work, we make the first study on these questions, by developing a weather-traffic index (WTI) system. The system includes two main components: WTI establishment and key factor analysis. Using the proposed system, we conducted comprehensive empirical study in Shanghai, and the WTI extracted have been validated to be surprisingly consistent with real world observations. Further regional key factor analysis yields interesting results. For example, house age has significant impact on WTI, which sheds light on future urban planning and reconstruction.

The IEEE 802.11 is a set of Media Access Control (MAC) and Physical Layer (PHY) specifications which concern the Wireless Local Area Network (WLAN) service. However, most IEEE 802.11 WLAN services are easily affected by external elements, such as the homogeneous interference caused by the high-density deployment of IEEE 802.11 devices, the attenuation effect caused by complicated indoor obstacles, and the heterogeneous interference caused by other devices which operate out of unlicensed 2.4GHz ISM bands. In this paper, we first present a method to capture IEEE 802.11n Bit Error Patterns (BEP) under the network effect such as the homogeneous interference and the signal attenuation caused by obstacles. We separate the two issues by showing the specific BEP distributions under different channel conditions. In addition to the IEEE 802.11n BEP analysis, we further simulated the impact of the LTE-Unlicensed (LTE-U) signal to the IEEE 802.11ac at the 5GHz, and analyzed similar BEPs through a purely experiment based method.

This paper studies the critical problem of maximizing the aggregate data utility under budget constraint in mobile crowd sourced sensing. This problem is particularly challenging given the redundancy in sensing data, self-interested and strategic user behaviors, and private cost information of smartphones. Most of existing approaches do not consider the important performance objective - maximizing the redundancy-aware data utility of sensing data collected from smartphones. Furthermore, they do not consider the practical constraint on budget. In this paper, we propose a combinatorial auction mechanism based on a reverse auction framework. It consists of an approximation algorithm for winning bids determination and a critical payment scheme. The approximation algorithm guarantees a constant approximation ratio at polynomial-time complexity. The critical payment scheme guarantees truthful bidding. The rigid theoretical analysis demonstrates that our mechanism achieves truthfulness, individual rationality, computational efficiency, and budget feasibility. Extensive simulations show that the proposed mechanism produces high redundancy-aware data utility.

Crowd sourced sensing over smartphones presents a new paradigm for collecting sensing data over a vast area for real-time monitoring applications. A monitoring application may require different types of sensing data, while under a budget constraint. This paper explores the crucial problem of maximizing the aggregate data utility of heterogeneous sensing tasks while maintaining utility-centric fairness across different tasks under a budget constraint. In particular, we take the redundancy of sensing data into account. This problem is highly challenging given its unique characteristics including the intrinsic trade off between aggregate data utility and fairness, and the large number of smartphones. We propose a fairness-aware distributed approach to solving this problem. To overcome the intractability of the problem, we decompose it to two sub problems of recruiting smartphones under a budget constraint and allocating workloads of sensing tasks. For the first sub problem, we propose an efficient greedy algorithm which has a constant approximation ratio of two. For the second problem, we apply dual based decomposition based on which we design a distributed algorithm for determining the workloads of different tasks on each recruited smartphone. We have implemented our distributed algorithm on a windows-based server and Android-based smartphones. With extensive simulations we demonstrate that our approach achieves high aggregate data utility while maintaining good utility-centric fairness across sensing tasks.

The continual proliferation of mobile devices has stimulated the development of opportunistic encounter-based networking and has spurred a myriad of proximity-based mobile applications. A primary cornerstone of such applications is to discover neighboring devices effectively and efficiently. Despite extensive protocol optimization, current neighbor discovery modalities mainly rely on radio interfaces, whose energy and wake up delay required to initiate, configure and operate these protocols hamper practical applicability. Unlike conventional schemes that actively emit radio tones, we exploit ubiquitous audio events to discover neighbors passively. The rationale is that spatially adjacent neighbors tend to share similar ambient acoustic environments. We propose AIR, an effective and efficient neighbor discovery protocol via low power acoustic sensing to reduce discovery latency. Especially, AIR substantially increases the discovery probability of the first time they turn the radio on. Compared with the state-of-the-art neighbor discovery protocol, AIR significantly decreases the average discovery latency by around 70%, which is promising for supporting vast proximity-based mobile applications.

Data collection is required to be safe and efficient considering both data privacy and system performance. In this paper, we study a new problem: distributed data sharing with privacy-preserving requirements. Given a data demander requesting data from multiple distributed data providers, the objective is to enable the data demander to access the distributed data without knowing the privacy of any individual provider. The problem is challenged by two questions: how to transmit the data safely and accurately; and how to efficiently handle data streams? As the first study, we propose a practical method, Shadow Coding, to preserve the privacy in data transmission and ensure the recovery in data collection, which achieves privacy preserving computation in a data-recoverable, efficient, and scalable way. We also provide practical techniques to make Shadow Coding efficient and safe in data streams. Extensive experimental study on a large-scale real-life dataset offers insight into the performance of our schema. The proposed schema is also implemented as a pilot system in a city to collect distributed mobile phone data.

Reliable people counting is crucial to many urban applications. However, most existing people counting systems are sensor-based and can only work in some fixed gateways or checkpoints where sensors have been installed. This high dependence on the exact locations of sensors leads to low accuracy. To overcome these limitations, in this paper, we propose a smartphone-based people counting system, Wi-Counter, by leveraging the pervasive Wi-Fi infrastructure. To collect comprehensive Wi-Fi signals and people count information based on crowdsource, Wi-Counter first adopts a preprocessor to overcome the noisy, discrepant, and fragile data based on the Wiener filter and Newton interpolation. It then makes use of the designated five-layer neural network to learn the relation model between the Wi-Fi signals and the number of people. By analyzing the received Wi-Fi signals, Wi-Counter can estimate the number of people based on the resulting model. We have conducted experiments by implementing a prototype of Wi-counter based on smartphones and evaluated the system in terms of accuracy and power consumption in an indoor testbed covering an area of 96 m $^2$. Wi-Counter achieved a counting accuracy of up to 93% and exhibited reliable and robust performance resisting temporal environmental changes with negligible power usage.

Multicast is a crucial routine operation for vehicular networks, which underpins important functions such as message dissemination and group coordination. As vehicles may distribute over a vast area, the number of vehicles in a given region can be limited which results in sparse node distribution in part of the vehicular network. This poses several great challenges for efficient multicast, such as network disconnection, scarce communication opportunities and mobility uncertainty. Existing multicast schemes proposed for vehicular networks typically maintain a forwarding structure assuming the vehicles have a high density and move at low speed while these assumptions are often invalid in a practical vehicular network. As more and more vehicles are equipped with GPS enabled navigation systems, the trajectories of vehicles are becoming increasingly available. In this work, we propose an approach called TMC to exploit vehicle trajectories for efficient multicast in vehicular networks. The novelty of TMC includes a message forwarding metric that characterizes the capability of a vehicle to forward a given message to destination nodes, and a method of predicting the chance of inter-vehicle encounter between two vehicles based only on their trajectories without accurate timing information. TMC is designed to be a distributed approach. Vehicles make message forwarding decisions based on vehicle trajectories shared through inter-vehicle exchanges without the need of central information management. We have performed extensive simulations based on real vehicular GPS traces and compared our proposed TMC scheme with other existing approaches. The performance results demonstrate that our approach can achieve a delivery ratio close to that of the flooding-based approach while the cost is reduced by over 80 percent.

Wireless LANs, particularly WiFi, have been pervasively deployed and have fostered myriad wireless communication services and ubiquitous computing applications. A primary concern in designing these applications is to combat harsh indoor propagation environments, particularly Non-Line-Of-Sight (NLOS) propagation. The ability to identify the existence of the Line-Of-Sight (LOS) path acts as a key enabler for adaptive communication, cognitive radios, and robust localization. Enabling such capability on commodity WiFi infrastructure, however, is prohibitive due to the coarse multipath resolution with MAC-layer received signal strength. In this paper, we propose two PHY-layer channel-statistics-based features from both the time and frequency domains. To further break away from the intrinsic bandwidth limit of WiFi, we extend to the spatial domain and harness natural mobility to magnify the randomness of NLOS paths while retaining the deterministic nature of the LOS component. We propose LiFi, a statistical LOS identification scheme with commodity WiFi infrastructure, and evaluate it in typical indoor environments covering an area of 1500 m2. Experimental results demonstrate that LiFi achieves an overall LOS detection rate of 90.42% with a false alarm rate of 9.34% for the temporal feature and an overall LOS detection rate of 93.09% with a false alarm rate of 7.29% for the spectral feature.

Inverse reinforcement learning (IRL) aims to recover the reward function underlying a Markov Decision Process from behaviors of experts in support of decision-making. Most recent work on IRL assumes the same level of trustworthiness of all expert behaviors, and frames IRL as a process of seeking reward function that makes those behaviors appear (near)-optimal. However, it is common in reality that noisy expert behaviors disobeying the optimal policy exist, which may degrade the IRL performance significantly. To address this issue, in this paper, we develop a robust IRL framework that can accurately estimate the reward function in the presence of behavior noise. In particular, we focus on a special type of behavior noise referred to as sparse noise due to its wide popularity in real-world behavior data. To model such noise, we introduce a novel latent variable characterizing the reliability of each expert action and use Laplace distribution as its prior. We then devise an EM algorithm with a novel variational inference procedure in the E-step, which can automatically identify and remove behavior noise in reward learning. Experiments on both synthetic data and real vehicle routing data with noticeable behavior noise show significant improvement of our method over previous approaches in learning accuracy, and also show its power in de-noising behavior data.

Far beyond relationship topology, today's online social networks are also characterized by semantically rich text messages exchanged among users as well as GPS locations associated with those messages, as evidenced by Twitter's geotagged tweets. Textual contents help characterize users' personal interests, while geographical features help link users' behaviors in the online world to those in the physical world such as their mobility patterns. In this paper, instead of studying each aspect separately, as done by most previous works, we combine textual contents and spatial features in a joint way using Bayesian latent topic model in order to construct better algorithms for user characterization and social network study. Specifically, the integration of contents and spatial features in a user-centered environment can not only discover geographic topics but also enable the characterization of users' latent interests with geographic semantics. Such a novel characterization can be leveraged to benefit many interesting studies regarding social network heterogeneity and relationships between online networks and physical world. Using a large-scale twitter data set with broad geographical coverage, we systematically evaluate our framework in several typical inference tasks surrounding user, content and location, as well as carry out empirical studies in real world scenarios. Experimental results demonstrate the advantages of our joint modeling approach, as well as its potentials to facilitate user understanding, both in online world and physical world.

Road latent cost, which quantifies how desirable each road is for traveling, is important information to enable many smartcity applications such as route recommendation. Arguably, vehicle trajectories are a good source to learn these costs as drivers intelligently incorporate them into their routing decisions. However, major past approaches misinterpret drivers' behaviors and suffer from trajectory sparsity problem, mainly because they adopt an edge-centric perspective which fails to exploit the sequential information in the entire trajectories. To address these shortcomings, we model drivers' routing decision process which targets at global path optimality, and present a framework to reliably discover those costs by exploiting entire trajectories while isolating the influence of heterogeneous destinations. Extensions are also made to address several issues in practice. Extensive experiments on real world data show that the road costs learned in this way significantly outperform past approaches in several urban computing tasks and require less data for learning.

The value of large amount of location tracking data has received wide attention in many applications including human behavior analysis, urban transportation planning, and various location-based services (LBS). Nowadays, both scientific and industrial communities are encouraged to collect as much location tracking data as possible, which brings about two issues: 1) it is challenging to process the queries on big location tracking data efficiently, and 2) it is expensive to store several exact data replicas for fault-tolerance. So far, several dedicated storage systems have been proposed to address these issues. However, they do not work well when the query ranges vary widely. In this paper, we present the design of a storage system using diverse replica scheme which improves the query processing efficiency with reduced cost of storage space. To the best of our knowledge, we are the first to investigate the data storage and processing in the context of big location tracking data. Specifically, we conduct in-depth theoretical and empirical analysis of the trade-offs between different spatio-temporal partitioning schemes as well as data encoding schemes. Then we propose an effective approach to select an appropriate set of diverse replicas, which is optimized for the expected query loads while conforming to the given storage space budget. The experiment results confirm that using diverse replicas can significantly improve the overall query performance. The results also demonstrate that the proposed algorithms for the replica selection problem is both effective and efficient.

Channel condition varies frequently in wireless networks. To achieve good performance, devices need rate adaptation. In rate adaptation, choosing proper modulation schemes based on channel conditions is vital to the transmission performance. However, due to the natural character of discrete modulation types and continuous varied link conditions, we cannot make a one-to-one mapping from modulation schemes to channel conditions. This matching gap causes either over-select or under-select modulation schemes which limits throughput performance. To fill-in the gap, we propose TiM (Time-line Modulation), a novel 3-Dimensional modulation scheme by adding time dimension into current amplitude-phase domain schemes. With estimation of channel condition, TiM changes base-band data transmission time by artificially interpolating values between original data points without changing amplitude-phase domain modulation type. We implemented TiM on USRP2 and conducted comprehensive simulations. Results show that, compared with rate adaptation choosing from traditional modulation schemes, TiM can improve channel utilization up to 200%.

Newly popular indoor location-based services (ILBS), when integrated with commerce and public safety, offer a promising land for wireless indoor localization technologies. WLAN is suggested to be one of the most potential candidates owing to its prevalent infrastructure (i.e., access points (APs)) and low cost. However, the overall performance can be greatly degraded by the spatial localizability variance problem, i.e., the localization accuracy across various locations may have significant differences given any fixed AP deployment. As a result, it brings in user experience inconsistency which is unfavorable for ILBS. In this paper, we propose NomLoc - an indoor localization system using nomadic APs to address the performance variance problem. The key insight of NomLoc is to leverage the mobility of nomadic APs to dynamically adjust the WLAN network topology. A space partition (SP)-based localization algorithm is tailored for NomLoc to perform calibration-free positioning. Moreover, fine-grained channel state information (CSI) is employed to mitigate the performance degradation of the SP-based method due to multipath and none-line-of-sight (NLOS) effects. We have implemented the NomLoc system with off-the-shelf devices and evaluated the performance in two typical indoor environments. The results show that NomLoc can greatly mitigate spatial localizability variance and improve localization accuracy with the assistance of nomadic APs as compared with the corresponding static AP deployment. Moreover, it is robust to the position error of nomadic APs.

Stimulating participation from smartphone users is of paramount importance to mobile crowd sourcing systems and applications. A few incentive mechanisms have been proposed, but most of them have made the impractical assumption that smartphones remain static in the system and sensing tasks are known in advance. The existing mechanisms fail when being applied to the realistic scenario where smartphones dynamically arrive to the system and sensing tasks are submitted at random. It is particularly challenging to design an incentive mechanism for such a mobile crowd sourcing system, given dynamic smartphones, uncertain arrivals of tasks, strategic behaviors, and private information of smartphones. We propose two truthful auction mechanisms for two different cases of mobile crowd sourcing with dynamic smartphones. For the offline case, we design an optimal truthful mechanism with an optimal task allocation algorithm of polynomial-time computation complexity of O (n+γ)3, where n is the number of smartphones and γ is the number of sensing tasks. For the online case, we design a near-optimal truthful mechanism with an online task allocation algorithm that achieves a constant competitive ratio of 1:2. Rigorous theoretical analysis and extensive simulations have been performed, and the results demonstrate the proposed auction mechanisms achieve truthfulness, individual rationality, computational efficiency, and low overpayment.

Transceiver-free object localization is essential for emerging location-based service, e.g., the safe guard system and asset security. It can track indoor target without carrying any device and has attracted many research effort. Among these technologies, Radio Signal Strength (RSS) based approaches are very popular because of their low-cost and wide applicability. In such work, usually a large number of reference nodes have to be deployed. However, if in a very large area, many labor work to measure the positions of the reference nodes have to be performed, result in not practical in real scenario. In this paper, we propose Double Free, which can accurately track transceiver-free object without measuring the positions of the reference nodes. Users may randomly deploy nodes in a 2D area, e.g., the ceiling of the floor. Our Double Free contains two steps: reference node localization and target localization. The key to achieve the first step is to utilize the RSS difference in different channel to distinguish the Line-Of-Sight (LOS) signal from combined multiple paths' signal. Thus, the reference nodes can be accurately localized without additional hardware. In the second step, we propose two algorithms: Influential Link & Node (ILN) and MultiPath Distinguishing (MD). ILN is simple to implement, while MD can accurately model the additional signal caused by the target, then accurately localize the target. To implement this idea, 16 TelosB nodes are placed randomly in a 25×10m2laboratory. The experiment results show, the average localization error is only round 2 meters without requiring to measure the positions of reference nodes in advance. It shows enormous potential in those localization areas, where manual measurement is hard to perform, or hard labor work want to be saved.

In this paper, we tackle the problem of stimulating smartphone users to join mobile crowdsourcing applications with smartphones. Different from existing work of mechanism design, we uniquely take into consideration the crucial dimension of location information when assigning sensing tasks to smartphones. However, the location awareness largely increases the theoretical and computational complexity. In this paper, we introduce a reverse auction framework to model the interactions between the platform and the smartphones. We rigorously prove that optimally determining the winning bids is NP hard. In this paper we design a mechanism called TRAC which consists of two main components. The first component is a near-optimal approximate algorithm for determining the winning bids with polynomial-time computation complexity, which approximates the optimal solution within a factor of 1 + ln(n), where n is the maximum number of sensing tasks that a smartphone can accommodate. The second component is a critical payment scheme which, despite the approximation of determining winning bids, guarantees that submitted bids of smartphones reflect their real costs of performing sensing tasks. Through both rigid theoretical analysis and extensive simulations, we demonstrate that the proposed mechanism achieves truthfulness, individual rationality and high computation efficiency.

Sensing data from mobile phones provide us exciting and profitable applications. Recent research focuses on sensing indoor environment, but suffers from inaccuracy because of the limited reachability of human traces or requires human intervention to perform sophisticated tasks. In this paper, we present ShopProfiler, a shop profiling system on crowdsourcing data. First, we extract customer movement patterns from traces. Second, we improve accuracy of building floor plan by adopting a gradient-based approach and then localize shops through WiFi heat map. Third, we categorize shops by designing an SVM classifier in shop space to support multi-label classification. Finally, we infer brand name from SSID by applying string similarity measurement. Based on over five thousand traces in three big malls in two different countries, we conclude that ShopProfiler achieves better accuracy in building refined floor plan, and characterizes shops in terms of location, category and name with little human intervention.

The world population is in the midst of a unique and irreversible process of aging. Fall, which is one of the major health threats and obstacles to independent living of elders, will aggravate the global pressure in elders' health care and injury rescue. Thus, automatic fall detection is highly in need. Current proposed fall detection systems either need hardware installation or disrupt people's daily life. These limitations make it hard to widely deploy fall detection systems in residential settings. In this work, we analyze the wireless signal propagation model considering human activities influence. We then propose a novel and truly unobtrusive detection method based on the advanced wireless technologies, which we call as WiFall. WiFall employs the time variability and special diversity of Channel State Information (CSI) as the indicator of human activities. As CSI is readily available in prevalent in-use wireless infrastructures, WiFall withdraws the need for hardware modification, environmental setup and worn or taken devices. We implement WiFall on laptops equipped with commercial 802.11n NICs. Two typical indoor scenarios and several layout schemes are examined. As demonstrated by the experimental results, WiFall yielded 87% detection precision with false alarm rate of 18% in average.

Wireless video stream delivery is choppy. This problem becomes much severer in MU-MIMO's simultaneous video transmission within the same band. Conventional schemes achieve graceful video delivery by harnessing from high data redundancy. However, with concurrent transmission in the same band, the leverage of high data redundancy leads to high probability of collisions and packets loss, which limits the performance. In concurrent video transmission, achieving efficiency over varied link condition is the main issue. To address this issue, this paper presents SimCast (Simultaneous), a cross-layer design for achieving efficient concurrent video uploading/downloading in MU-MIMO WLANs. The key idea of SimCast is to harness frequency diversity of the channel and spatial similarity of users. We implemented SimCast on USRP2 and conducted extensive simulations. Result shows that SimCast achieves higher throughput than traditional schemes by 1.2× on average. Video quality of SimCast outperforms competitive schemes, which is up to 5 dB in PSNR.

Seeing through walls and knowing clearly what exist inside just like a superman are not only fantastic wishes for humans, but also of much practical significance. For example, you would like to know whether there are pipes, or rebars inside a wall before drilling into it. Moreover, knowing how pipes are configured in a wall before attempting to fix defects would definitely prevent unnecessary damages. Existing methods that intend to address this issue are either costly due to the use of high-end technology, or too restrictive for reasons of some strong assumptions. However, in this paper, we present a novel system, SmartSening, which is based on off-the-shelf sensors embedded in smartphones. SmartSensing makes full use of in-built sensors, namely, the accelerometer, the gyroscope, and the magnetometer to achieve this goal inexpensively and conveniently. Specifically, by combining these sensors, we are able to clearly distinguish certain objects inside a wall. In addition, the layout of a pipeline system can be mapped out automatically in an economical and laborsaving way. We implement this system on two different kinds of smartphone platforms, namely iPhone4 and Xiaomi Mi2S. We conduct experiments in a proof-of-concept testbed of size 1.8m×1.0m. Experimental results show that SmartSensing can achieve no less than an average accuracy of 96%, 89% and 77% in distinguishing objects under three different depths, respectively. Also, as for layout mapping, it can achieve less than 32cm and 28cm length error with 90% probability on average for whole horizontal and vertical pipeline segments, with a 6.8m and 4.0m total length, respectively.

The extraction of macroscopic mobile context reflecting users' personal and social behavior patterns from smartphone sensor data (e.g., GPS/Bluetooth signals) is crucial in building intelligent pervasive systems. Hierarchical Dirichlet Processes (HDP), a well known Bayesian nonparametrics model for grouped data, is a promising option to achieve this objective due to its ability of discovering high-level semantics behind raw signals and establishing connections between individuals. However, applying HDP in a straightforward manner may not work as it does not take certain unique characteristics in mobile context into account. Particularly, while traditional HDP typically models a single aspect (e.g., Word), the characterization of a mobile context normally involves multiple heterogeneous aspects (e.g., Time, location, Bluetooth proximity). In addition, the presence of multiple aspects dictates a flexible way of clustering users and organizing mobile contexts in a hierarchical manner in serving different pervasive applications, a feature that traditional HDP lacks. Therefore, in this paper, we propose several extensions on traditional HDP to adapt it to the task of mobile context discovery. The key features in our extensions are: i) fusing multiple aspects naturally in HDP to achieve effective extraction of complex mobile context, ii) treating different aspects heterogeneously (globally or personally) in HDP to enable flexible user behavior clustering at various granularities in accordance with applications' needs, and iii) organizing mobile contexts in a hierarchical manner for natural behavior representation and overcoming data sparsity. Based on the experiments in a popular real-world mobile data set, we illustrate the ability of the framework in extracting useful mobile contexts such as characterizing personal life routines, discovering dominant temporal habits in a population, and inferring social group patterns, as well as its potential in improving individual mobility prediction under data sparsity.

Recent literature advances Wi-Fi signals to "see" people's motions and locations. This paper asks the following question: Can Wi-Fi "hear" our talks? We present WiHear, which enables Wi-Fi signals to "hear" our talks without deploying any devices. To achieve this, WiHear needs to detect and analyze fine-grained radio reflections from mouth movements. WiHear solves this micro-movement detection problem by introducing Mouth Motion Profile that leverages partial multipath effects and wavelet packet transformation. Since Wi-Fi signals do not require line-of-sight, WiHear can "hear" people talks within the radio range. Further, WiHear can simultaneously "hear" multiple people's talks leveraging MIMO technology. We implement WiHear on both USRP N210 platform and commercial Wi-Fi infrastructure. Results show that within our pre-defined vocabulary, WiHear can achieve detection accuracy of 91% on average for single individual speaking no more than 6 words and up to 74% for no more than 3 people talking simultaneously. Moreover, the detection accuracy can be further improved by deploying multiple receivers from different angles.

Anomaly detection (a.k.a., outlier or burst detection) is a well-motivated problem and a major data mining and knowledge discovery task. In this article, we study the problem of population anomaly detection, one of the key issues related to event monitoring and population management within a city. Through studying detected population anomalies, we can trace and analyze these anomalies, which could help to model city traffic design and event impact analysis and prediction. Although a significant and interesting issue, it is very hard to detect population anomalies and retrieve anomaly trajectories, especially given that it is difficult to get actual and sufficient population data. To address the difficulties of a lack of real population data, we take advantage of mobile phone networks, which offer enormous spatial and temporal communication data on persons. More importantly, we claim that we can utilize these mobile phone data to infer and approximate population data. Thus, we can study the population anomaly detection problem by taking advantages of unique features hidden in mobile phone data. In this article, we present a system to conduct Population Anomaly Detection (PAD). First, we propose an effective clustering method, correlation-based clustering , to cluster the incomplete location information from mobile phone data (i.e., from mobile call volume distribution to population density distribution). Then, we design an adaptive parameter-free detection method, R-scan , to capture the distributed dynamic anomalies. Finally, we devise an efficient algorithm, BT-miner , to retrieve anomaly trajectories . The experimental results from real-life mobile phone data confirm the effectiveness and efficiency of the proposed algorithms. Finally, the proposed methods are realized as a pilot system in a city in China.

Radio frequency (RF) based technologies play an important role in indoor localization, since Radio Signal Strength (RSS) can be easily measured by various wireless devices without additional cost. Among these, radio map based technologies (also referred as fingerprinting technologies) are attractive due to high accuracy and easy deployment. However, these technologies have not been extensively applied on real environment for two fatal limitations. First, it is hard to localize multiple objects. When the number of target objects is unknown, constructing a radio map of multiple objects is almost impossible. Second, environment changes will generate different multipath signals and severely disturb the RSS measurement, making laborious retraining inevitable. Motivated by these, in this paper, we propose a novel approach, called Line-of-sight radio map matching, which only reserves the LOS signal among nodes. It leverages frequency diversity to eliminate the multipath behavior, making RSS more reliable than before. We implement our system MODLoc based on TelosB sensor nodes and commercial 802.11 NICs with Channel State Information (CSI) as well. Through extensive experiments, it shows that the accuracy does not decrease when localizing multiple targets in a dynamic environment. Our work outperforms the traditional methods by about 60 percent. More importantly, no calibration is required in such environment. Furthermore, our approach presents attractive flexibility, making it more appropriate for general RF-based localization studies than just the radio map based localization.

Geocast in vehicular networks aims to deliver a message to a target geographical region, which is useful for many applications such as geographic advertising. This is a highly challenging task in vehicular network environments due to the rare encounter opportunities and uncertainty caused by vehicular mobility. As more vehicles are equipped with on-board navigation systems, vehicle trajectories are ready for exploitation. We observe that a vehicle has a higher capability of delivering a message to the target region if its own future trajectory or trajectories of those vehicles to be encountered overlap the target region. Motivated by this observation, we develop a message forwarding metric, called coverage capability, to characterize the capability of a vehicle to successfully geocast the message. When calculating the coverage capability, we are facing the major challenge raised by the absence of accurate vehicle arrival time. Through an empirical study using real vehicular GPS traces of 2,600 taxis, we verify that the travel time of a vehicle, which is modeled as a random variable, follows the Gamma distribution. The travel time modeling helps us to make accurate predictions for inter-vehicle encounters. We perform extensive trace-driven simulations and the results show that our approach achieves 37.4 percent higher delivery ratio and 43.1 percent lower transmission overhead comparing with GPSR which is a representative geographic routing protocol.

Improving channel utilization is a well-known issue in wireless networks. In traditional point-to-point wireless communication, significant efforts had been made by the existing studies on enhancing the utilization of the channel access time. However, in the emerging wireless network using MU-MIMO, considering only the time domain in channel utilization is not sufficient. As multiple transmitters are allowed to transmit packets simultaneously to the same AP, allowing more antennas at AP would lead to higher channel utilization. Thus, the channel utilization in MU-MIMO should consider both time and spatial domains, i.e., the channel access time and the antenna usage, which have not been considered in the existing methods. In this paper, we point out that the fundamental problem is lacking of the antenna information of contention nodes in channel contention. To address this issue, we propose a new MAC-PHY architecture design, CUTS, to allow distributed nodes effectively contend for the channel and utilize the channel in both domains. Particularly, CUTS adopts interference nulling to attach the antenna information in channel contention. Meanwhile, techniques such as channel contention in frequency domain and ACK in frequency domain using self-jamming are adopted. Through the software defined radio-based real experiments and extensive simulations, we demonstrate the feasibility of our design and illustrate that CUTS provides better channel utilization with the gain over IEEE 802.11 reaching up to 470 percent.

In this paper, we first propose a very interesting and practical problem, pattern matching in a distributed mobile environment. Pattern matching is a well-known problem and extensive research has been conducted for performing effective and efficient search. However, previous proposed approaches assume that data are centrally stored, which is not the case in a mobile environment (e.g., mobile phone networks), where one person's pattern could be separately stored in a number of different stations, and such a local pattern is incomplete compared with the global pattern. A simple solution to pattern matching over a mobile environment is to collect all the data distributed in base stations to a data center and conduct pattern matching at the data center afterwards. Clearly, such a simple solution will raise huge amount of communication traffic, which could cause the communication bottleneck brought by the limited wireless bandwidth to be even worse. Therefore, a communication efficient and search effective solution is necessary. In our work, we present a novel solution which is based on our well-designed weighted bloom filter (WBF), called, D istributed Incomplete pattern matching ( DI-matching), to find target patterns over a distributed mobile environment. Specifically, to save communication cost and ensure pattern matching in distributed incomplete patterns, we use WBF to encode a query pattern and disseminate the encoded data to each base station. Each base station conducts a local pattern search according to the received WBF. Only qualified IDs and corresponding weights in each base station are sent to the data center for aggregation and verification. Through non-trivial theoretical analysis and extensive empirical experiments on a real city-scale mobile networks data set, we demonstrate the effectiveness and efficiency of our proposed solutions.

In traditional radio-based localization methods, the target object has to carry a transmitter (e.g., active RFID), a receiver (e.g., 802.11 × detector), or a transceiver (e.g., sensor node). However, in some applications, such as safe guard systems, it is not possible to meet this precondition. In this paper, we propose a model of signal dynamics to allow the tracking of a transceiver-free object. Based on radio signal strength indicator (RSSI), which is readily available in wireless communication, three centralized tracking algorithms, and one distributed tracking algorithm are proposed to eliminate noise behaviors and improve accuracy. The midpoint and intersection algorithms can be applied to track a single object without calibration, while the best-cover algorithm has higher tracking accuracy but requires calibration. The probabilistic cover algorithm is based on distributed dynamic clustering. It can dramatically improve the localization accuracy when multiple objects are present. Our experimental test-bed is a grid sensor array based on MICA2 sensor nodes. The experimental results show that the localization accuracy for single object can reach about 0.8 m and for multiple objects is about 1 m.

Energy efficiency is the main concern in wireless sensor networks (WSNs) due to devices' limited battery power. Because the heavy burden of nodes that near the sink, this "energy hole problem" makes nodes near the sink have faster energy depletion than others. Because of this, the lifetime of WSNs, to some extent, is determined by the power consumption of communication between sink and sensing nodes that near the sink. To address this issue, we propose CSMA/SF (Shortest First) protocol to reduce power consumption of sink-node communication by minimizing energy cost in carrier sense during nodes' channel contention. CSMA/SF modifies existed CSMA/CA MAC protocol. Instead of complete contention-based, CSMA/SF ensures nodes remaining shorter message has higher priority in contention by implementing a distributed scheduling algorithm and incorporating Length Detection scheme. Further, CSMA/SF employs an Anti-Starvation mechanism to solve the starvation problem of shortest-first protocol. CSMA/SF also optimizes channel utilization by reducing the probability of collisions. We have implemented CSMA/SF into USRP2 platform and also conducted comprehensive simulations. The experimental results show that CSMA/SF can reduce overall energy consumption by around 20%. CSMA/SF can improve channel utilization up to 40%.

Road travel costs are important knowledge hidden in large-scale GPS trajectory data sets, the discovery of which can benefit many applications such as intelligent route planning and automatic driving navigation. While there are previous studies which tackled this task by modeling it as a regression problem with spatial smoothness taken into account, they unreasonably assumed that the latent cost of each road remains unchanged over time. Other works on route planning and recommendation that have considered temporal factors simply assumed that the temporal dynamics be known in advance as a parametric function over time, which is not faithful to reality. To overcome these limitations, in this paper, we propose an extension to a previous static trajectory regression framework by learning the temporal dynamics of road travel costs in an innovative non-parametric manner which can effectively overcome the temporal sparsity problem. In particular, we unify multiple different trajectory regression problems in a multi-task framework by introducing a novel cross-task regularization which encourages temporal smoothness on the change of road travel costs. We then propose an efficient block coordinate descent method to solve the resulting problem by exploiting its separable structures and prove its convergence to global optimum. Experiments conducted on both synthetic and real data sets demonstrate the effectiveness of our method and its improved accuracy on travel time prediction.

Understanding a user's social interactions in the physical world proves important in building context-aware ubiquitous applications. A good way towards that objective is to categorize people to whom a user is socially related into what we call as social circles. In this note, we propose a novel unsupervised approach that learns from the Bluetooth (BT) sensed data recording one's dynamic proximity relations with others to identify her social circles, each of which is formed along a semantically coherent aspect. For each circle we learn its members as well as the temporal dimensions along which it is formed. Our method is innovative in that it well overcomes data sparsity by information sharing, and allows for circle overlaps which is common in reality. Experiments on real data demonstrate the effectiveness of our method, and also show the potentials of relational mobile data in sensing personal behaviors beyond personal data.

Many emerging applications such as intruder detection and border protection drive the fast increasing development of device-free passive (DfP) localization techniques. In this paper, we present Pilot, a Channel State Information (CSI)-based DfP indoor localization system in WLAN. Pilot design is motivated by the observations that PHY layer CSI is capable of capturing the environment variance due to frequency diversity of wideband channel, such that the position where the entity located can be uniquely identified by monitoring the CSI feature pattern shift. Therefore, a ``passive'' radio map is constructed as prerequisite which include fingerprints for entity located in some crucial reference positions, as well as clear environment. Unlike device-based approaches that directly percepts the current state of entities, the first challenge for DfP localization is to detect their appearance in the area of interest. To this end, we design an essential anomaly detection block as the localization trigger relying on the CSI feature shift when entity emerges. Afterwards, a probabilistic algorithm is proposed to match the abnormal CSI to the fingerprint database to estimate the positions of potential existing entities. Finally, a data fusion block is developed to address the multiple entities localization challenge. We have implemented Pilot system with commercial IEEE 802.11n NICs and evaluated the performance in two typical indoor scenarios. It is shown that our Pilot system can greatly outperform the corresponding best RSS-based scheme in terms of anomaly detection and localization accuracy.

Improving channel utilization is a well-known issue in wireless networks. In traditional point-to-point wireless communication, significant efforts had been made by the existing study on enhancing the utilization of the channel access time. However, in the emerging wireless network using MU-MIMO, considering only the time domain in channel utilization is not sufficient. As multiple transmitters are allowed to transmit packets simultaneously to the same AP, allowing more antennas at AP would lead to higher channel utilization. Thus the channel utilization in MU-MIMO should consider both time and spatial domains, i.e., the channel access time and the antenna usage, which has not been considered in the existing methods. In this paper, we point out that the fundamental problem is lacking of the antenna information of contention nodes in channel contention. To address this issue, we propose a new MAC-PHY architecture design, CUTS, to utilize the channel in both domains. Particularly, CUTS adopts interference nulling to attach the antenna information in channel contention. Meanwhile, techniques such as channel contention in frequency domain and ACK in frequency domain using self-jamming are adopted. Through the software defined radio based real experiments and extensive simulations, we demonstrate the feasibility of our design and illustrate that CUTS provides better channel utilization with the gain over IEEE 802.11 reaching up to 470%.

Nowadays, there are many taxis traversing around the city searching for available passengers, but their hunts of passengers are not always efficient. To the dynamics of traffic and biased passenger distributions, current offline recommendations based on place of interests may not work well. In this paper, we define a new problem, global-optimal trajectory retrieving (GOTR), as finding a connected trajectory of high profit and high probability to pick up a passenger within a given time period in real-time. To tackle this challenging problem, we present a system, called HUNTS, based on the knowledge from both historical and online GPS data and business data. To achieve above objectives, first, we propose a dynamic scoring system to evaluate each road segment in different time periods by considering both picking-up rate and profit factors. Second, we introduce a novel method, called trajectory sewing, based on a heuristic method and the Skyline technique, to produce an approximate optimal trajectory in real-time. Our method produces a connected trajectory rather than several place of interests to avoid frequent next-hop queries. Third, to avoid congestion and other real-time traffic situations, we update the score of each road segment constantly via an online handler. Finally, we validate our system using a large-scale data of around 15,000 taxis in a large city in China, and compare the results with regular taxis' hunts and the state-of-the-art.

Nowadays, big cities are suffering from severe traffic congestion as a result of the continuing increase in vehicles. Taxis equipped with GPS can be viewed as sensors of the traffic situation in city. However, trajectory data generated by taxi's GPS traces are often high-dimensional and contain large spatial and temporal attributes, which pose challenges for analysts. In this paper, based on taxi trajectory data, we present an interactive visual analytics system, T-Watcher, for monitoring and analyzing complex traffic situations in big cities. Users are able to use a carefully designed interface to monitor and inspect data interactively from three levels (region, road and vehicle views). We develop a visualization method to monitor and analyze traffic patterns for abnormal behaviors detection. In the region view of our system, global temporal changes in spatial evolution will be presented to users and can be interactively explored. The road view shows temporal changes to the traffic situations of significant segments of roads. The vehicle view uses a novel visualization method to track individual vehicles. Furthermore, the three views integrate important statistical and historical information related to traffic, which illustrate temporal changes of the traffic. We find that this design can help users explore historical information while monitoring traffic. We test our system on a real-life vehicle dataset collected from thousands of taxis and obtained some interesting findings. The experimental results confirm the effectiveness and efficiency of the proposed visual detection method. The analysis of the results also shows that our system is capable of effectively monitoring traffic and detecting abnormal traffic patterns.

Recognizing and classifying users' routine behavior patterns from sensor data has been a hot topic in pervasive computing. Its objective is to automatically discover recurrent routine patterns in a user's daily life by leveraging the multimodal data generated from wearable sensors such as mobile phones. This kind of knowledge can be utilized in many ways such as identifying similar users in terms of their behaviors, providing behavior contexts to enable advanced human-centered applications, etc. While numerous works have been done in this area, most of them rely on densely sampled mobile data collected from specially-programmed sensors that can “follow” people throughout the day. In this paper, we study how to achieve the same objective when the mobile data presented is much sparser, such as traditional mobile phone data where a user's location is reported only when he makes a call. Although a single user's mobile data is far from sufficient to reveal his characteristic behavior, we show that when exploiting a large number of users' mobile data in a principled collaborative way which facilitate similar users' data to complement each other, representative routine patterns can be revealed and each user can be characterized properly. Experiments on synthetic and real mobile phone data set demonstrate the effectiveness of our methods, and also show our model's ability in predicting human activity using the patterns learned.

The rise of GPS-equipped mobile devices has led to the emergence of big trajectory data. In this paper, we study a new path finding query which finds the most frequent path (MFP) during user-specified time periods in large-scale historical trajectory data. We refer to this query as time period-based MFP (TPMFP). Specifically, given a time period T, a source v_s and a destination v_d, TPMFP searches the MFP from v_s to v_d during T. Though there exist several proposals on defining MFP, they only consider a fixed time period. Most importantly, we find that none of them can well reflect people's common sense notion which can be described by three key properties, namely suffix-optimal (i.e., any suffix of an MFP is also an MFP), length-insensitive (i.e., MFP should not favor shorter or longer paths), and bottleneck-free (i.e., MFP should not contain infrequent edges). The TPMFP with the above properties will reveal not only common routing preferences of the past travelers, but also take the time effectiveness into consideration. Therefore, our first task is to give a TPMFP definition that satisfies the above three properties. Then, given the comprehensive TPMFP definition, our next task is to find TPMFP over huge amount of trajectory data efficiently. Particularly, we propose efficient search algorithms together with novel indexes to speed up the processing of TPMFP. To demonstrate both the effectiveness and the efficiency of our approach, we conduct extensive experiments using a real dataset containing over 11 million trajectories.

With the increasing availability of metropolitan transportation data, such as those from vehicle Global Positioning Systems (GPSs) and road-side sensors, it has become viable for authorities, operators, and individuals to analyze the data for better understanding of the transportation system and, possibly, improved utilization and planning of the system. We report our experience in building the Visual Analytics for Intelligent Transportation (VAIT) system, which is the first system on real-life large-scale data sets for intelligent transportation. Our key observation is that metropolitan transportation data are inherently visual as they are spatio-temporal around road networks. Therefore, we visualize and manage traffic data, together with digital maps, and support analytical queries through this interactive visual interface. As a case study, we demonstrate VAIT on real-world taxi GPS and meter data sets from 15 000 taxis running for two months in a Chinese city of over 10 million people. We discuss the technical challenges in data calibration, storage, visualization, and query processing and offer first-hand lessons learned from developing the system. Based on our extensive empirical experiment results, VAIT beats state-of-the-art methods and systems in terms of scalability, efficiency, and effectiveness and offers us an easy-to-use, efficient, and scalable platform to shed more light on intelligent transportation research.

Effective coordination can dramatically reduce radio interference and avoid packet collisions for multistation wireless local area networks (WLANs). Coordination itself needs consume communication resource and thus competes with data transmission for the limited wireless radio resources. In traditional approaches, control frames and data packets are transmitted in an alternate manner, which brings a great deal of coordination overhead. In this paper, we propose a new communication model where the control frames can be "attachedâ to the data transmission. Thus, control messages and data traffic can be transmitted simultaneously and consequently the channel utilization can be improved significantly. We implement the idea in OFDM-based WLANs called hJam, which fully explores the physical layer features of the OFDM modulation method and allows one data packet and a number of control messages to be transmitted together. hJam is implemented on the GNU Radio testbed consisting of eight USRP2 nodes. We also conduct comprehensive simulations and the experimental results show that hJam can improve the WLANs efficiency by up to 200 percent compared with the existing 802.11 family protocols.

The growing importance of operations such as identification, location sensing, and object tracking has led to increasing interests in contactless Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are in large numbers, most existing collision arbitration protocols do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides efficient RFID identification for both small and large deployment of RFID tags, in terms of time and energy cost. Theoretical analysis and simulation evaluation show that the performance of ASAP is better than most existing collision-arbitration solutions and the time efficiency is close to the theoretically optimal values.

Indoor positioning systems have received increasing attention for supporting location-based services in indoor environments. WiFi-based indoor localization has been attractive due to its open access and low cost properties. However, the distance estimation based on received signal strength indicator (RSSI) is easily affected by the temporal and spatial variance due to the multipath effect, which contributes to most of the estimation errors in current systems. In this work, we analyze this effect across the physical layer and account for the undesirable RSSI readings being reported. We explore the frequency diversity of the subcarriers in orthogonal frequency division multiplexing systems and propose a novel approach called FILA, which leverages the channel state information (CSI) to build a propagation model and a fingerprinting system at the receiver. We implement the FILA system on commercial 802.11 NICs, and then evaluate its performance in different typical indoor scenarios. The experimental results show that the accuracy and latency of distance calculation can be significantly enhanced by using CSI. Moreover, FILA can significantly improve the localization accuracy compared with the corresponding RSSI approach.

Transceiver-free object tracking is to trace a moving object that does not carry any communication device in an environment with some monitoring nodes predeployed. Among all the tracking technologies, RF-based technology is an emerging research field facing many challenges. Although we proposed the original idea, until now there is no method achieving scalability without sacrificing latency and accuracy. In this paper, we put forward a real-time tracking system RASS, which can achieve this goal and is promising in the applications like the safeguard system. Our basic idea is to divide the tracking field into different areas, with adjacent areas using different communication channels. So, the interference among different areas can be prevented. For each area, three communicating nodes are deployed on the ceiling as a regular triangle to monitor this area. In each triangle area, we use a Support Vector Regression (SVR) model to locate the object. This model simulates the relationship between the signal dynamics caused by the object and the object position. It not only considers the ideal case of signal dynamics caused by the object, but also utilizes their irregular information. As a result, it can reach the tracking accuracy to around 1 m by just using three nodes in a triangle area with 4 m in each side. The experiments show that the tracking latency of the proposed RASS system is bounded by only about 0.26 m. Our system scales well to a large deployment field without sacrificing the latency and accuracy.

Wireless technology has become ever more popular in recent years, which results in a higher and higher density of wireless devices. In order to cope with this high density, researchers are proposing the provision of multiple concurrent transmissions by dividing a broadband channel into separate narrow band subchannels. In particular, a fine-grained channel access approach calls for efficient channel allocation mechanisms, especially in distributed networks. However, most of the current multi-channel access methods rely on costly coordination, which significantly degrades network performance. Motivated by this, we propose a cross layer design, termed Attachment Learning (AT-Learning), to achieve multi-channel allocation with low cost and high efficiency in distributed OFDMA based networks. AT-Learning utilizes a jamming and cancellation technique to attach identifier signals to data traffic, without degrading the effective throughput of the original data transmission. These identifier signals help mobile stations learn the allocation strategy by themselves. After the learning stage, mobile stations can achieve a TDMA-like performance, where stations will know exactly when to transmit and on which channel without further collisions. We conduct comprehensive simulations, comparing AT-Learning with a traditional multi-channel access method like Slotted ALOHA. The experimental results demonstrate that AT-Learning can improve the throughput by up to 300% over Slotted ALOHA.

During the past decade, various GPS-equipped devices have generated a tremendous amount of data with time and location information, which we refer to as big spatio-temporal data. In this paper, we present the design and implementation of CloST, a scalable big spatio-temporal data storage system to support data analytics using Hadoop. The main objective of CloST is to avoid scan the whole dataset when a spatio-temporal range is given. To this end, we propose a novel data model which has special treatments on three core attributes including an object id, a location and a time. Based on this data model, CloST hierarchically partitions data using all core attributes which enables efficient parallel processing of spatio-temporal range scans. According to the data characteristics, we devise a compact storage structure which reduces the storage size by an order of magnitude. In addition, we proposes scalable bulk loading algorithms capable of incrementally adding new data into the system. We conduct our experiments using a very large GPS log dataset and the results show that CloST has fast data loading speed, desirable scalability in query processing, as well as high data compression ratio.

Human behavior understanding is a fundamental problem in many ubiquitous applications. It aims to automatically uncover and quantify characteristic behavior patterns in users' daily lives as well as disclose behavior clustering structure among multiple users. The key challenge is how to define a naturally interpreted representation for users' daily behavior patterns, which can be easily exploited to not only uncover the behavior similarity among multiple users but also predict users' future activities. In this paper, we define such a representation, and propose a probabilistic framework which can automatically learn it from mass amount of mobile data in unsupervised setting and exploit it to predict user activities. By an appropriate information sharing among multiple users, this framework overcomes single-user data sparsity problem and effectively identifies behavior clustering structures in a set of users. Experiments conducted on a public reality mining data set demonstrate the effectiveness and accuracy of our methods.

WLAN-based indoor location fingerprinting has been attractive owing to the advantages of open access and high accuracy. Most fingerprinting-based systems so far rely on the received signal strength (RSS), which can be easily measured at the receiver with commercial WLAN equipment. However, RSS is a coarse value which simply measures the received power for a whole channel. Thus, it fluctuates over time in typical indoor environments with rich multipath effects and not unique for a specific location. In this paper, we present the design, implementation, and evaluation of a Fine-grained Indoor Fingerprinting System (FIFS). FIFS explores a PHYlayer Channel State Information (CSI) that specifies the channel status over all the subcarriers for location fingerprinting in WLAN. The system leverages the CSI values including different amplitudes and phases at multiple propagation paths, known as the frequency diversity, to uniquely manifest a location. Moreover, the multiple antennas provides the spatial diversity that can be further augmented in fingerprinting. We also present a coherence bandwidth-enhanced probability algorithm with a correlation filter to map object to the fingerprints. We conducted experiments in two typical indoor scenarios with commercial IEEE 802.11 NICs. The experimental results demonstrate that the overall positioning accuracy can be improved compared with the RSS-based Horus system.

Radio Frequency (RF) based technologies play an important role in indoor localization, since Radio Signal Strength (RSS) is easily achieved by various wireless devices without additional cost. Among these, radio map based technologies (also referred as fingerprinting technologies) are attractive. They are able to accurately localize the targets without introducing many reference nodes. Therefore, their hardware cost is low. However, this technology has two fatal limitations. First, it is hard to localize multiple objects, since radio map has to collect all the RSS information when targets are at different possible positions. But due to the multipath phenomenon, different number of target nodes at different positions often generates different multipath signals. So when the target object number is unknown, constructing a radio map of multiple objects is almost impossible. Second, environment changes will generate different multipath signals and severely disturb the RSS measurement, making laborious retraining inevitable. In this paper, we propose a novel method, called Line-Of-Sight (LOS) map matching. It leverages frequency diversity of wireless nodes to eliminate the multipath behavior, making RSS more reliable than before. These reliable RSS signals are able to construct the radio map, which only reserves the LOS signal among nodes. We call it LOS radio map. The number of objects and environment changes will not affect the LOS signal between the targets and reference nodes. Such map is able to be constructed easily and require no training if reference nodes are carefully redeployed. Our basic idea is to utilize the frequency diversity of each wireless node to transmit data in different spectrum channel. Then it solves the optimization problem to get the LOS signal. Our experiments are based on TelosB sensor platform with three reference nodes. It shows that the accuracy will not decrease when localizing multiple targets in a dynamic environment. It outperforms the traditional methods by about60%. More importantly, no calibration is required in such environment. Furthermore, our approach presents attractive flexibility, making it more appropriate for general RF-based localization studies than just the radio map based localization.

In this paper, we first propose a very interesting and practical problem, pattern matching in a distributed mobile environment. Pattern matching is a well-known problem and extensive research has been conducted for performing effective and efficient search. However, previous proposed approaches assume that data are centrally stored, which is not the case in a mobile environment (e.g., mobile phone networks), where one person's pattern could be separately stored in a number of different stations, and such a local pattern is incomplete compared with the global pattern. A simple solution to pattern matching over a mobile environment is to collect all the data distributed in base stations to a data center and conduct pattern matching at the data center afterwards. Clearly, such a simple solution will raise huge amount of communication traffic, which could cause the communication bottleneck brought by the limited wireless bandwidth to be even worse. Therefore, a communication efficient and search effective solution is necessary. In our work, we present a novel solution which is based on our well-designed Weighted Bloom Filter (WBF), called, Distributed Incomplete pattern matching (DI-matching), to find target patterns over a distributed mobile environment. Specifically, to save communication cost and ensure pattern matching in distributed incomplete patterns, we use WBF to encode a query pattern and disseminate the encoded data to each base station. Each base station conducts a local pattern search according to the received WBF. Only qualified IDs and corresponding weights in each base station are sent to the data center for aggregation and verification. Through extensive empirical experiments on a real city-scale mobile networks data set, we demonstrate the effectiveness and efficiency of our proposed solutions.

Device-free passive (Dfp) motion detection seeks to monitor the position change of entities without actively carrying any physical devices. Recently, WLAN with a rich set of installed wireless infrastructures enables motion detection in the area of interest. WLAN-enabled DfP motion detection rely on received signal strength (RSS) is verified to be able to provide acceptable high accuracy. Although RSS can be easily measured with commercial equipments, it is suspectable to measurement itself due to multipath effect in indoor environment. In this paper, we present an Indoor device-free Motion Detection system (FIMD) to overcome the preceding RSS-based limitation. FIMD explores properties of Channel State Information (CSI) from PHY layer in OFDM system. FIMD is designed based on the insight that CSI maintains temporal stability in static environment, while exhibits burst patterns when motion takes place. Motivated by this observation, FIMD uses a novel feature extracted from CSI to leverage its temporal stability and frequency diversity. The motion detection is conducted with outliers identification from normal features in continuous monitoring using density-based DBSCAN algorithm. Moreover, we leverage two schemes including false alert filter and data fusion to enhance the detection accuracy. We implement FIMD system with commercial IEEE 802.11n NICs and evaluate its performance in two typical indoor scenarios. Experiment results show that FIMD can achieve high detection rate. Moreover, comparing with RSSI, the feature extracted from CSI enables better detection performance in accuracy and robustness to narrowband interference.

Nowadays, cyber-physical system (CPS) relies on wireless networks for devices control and information backhaul. But the mass deployment CPS devices make operators' spectrum scarce situations even more worse. Hence, cellular network operators anticipate the Dynamic Spectrum Access (DSA) technology to solve the spectrum shortage problem in the context of cognitive radio (CR). Femtocells, acting as gateways in CPS, integrate CPS devices into cellular networks in a seamless manner. The concept of cognitive femtocell can solve the spectrum congestion problem even within a massive network on the CPS scale. However, in practical systems, cellular white space spectrum should be quantitatively measured to guide cognitive femtocell access algorithms design. We are the first to conduct a comprehensive measurement study for the purpose of measurement, discovery and model features of GSM white space spectrum. We evaluate availabilities of extra 21.4 MHz capacity in GSM white space spectrum as a reason of artificial GSM network spectrum planning. In our study, we find out that perfect results can hardly be obtained because of inherent measurement trade-offs, even when extremely high sweep speed of 16 GHz/s is applied at the receiver. Based on statistical analysis of real-scene traces, we propose an Efficient Duty Cycle (EDC) model to accurately characterize the white space in GSM network by considering miss-detection probabilities. Cross-validating evaluation results show that the EDC model can well decrease interference probabilities at high time-granularity measurement periodicity scenarios. Our results confirm the feasibility of cognitive femtocells access in an intra-operator scenario and can be applied to future wireless networks.

Effective coordination can dramatically reduce radio interference and avoid packet collisions for multi-station wireless local area networks (WLANs). Coordination itself needs consume communication resource and thus competes with data transmission for the limited wireless radio resources. In traditional approaches, control frames and data packets are transmitted in an alternate manner, which brings a great deal of coordination overhead. In this paper we propose a new communication model where the control frames can be “attached” to the data transmission. Thus, control messages and data traffic can be transmitted simultaneously and consequently the channel utilization can be improved significantly. We implement the idea in OFDM-based WLANs called hJam, which fully explores the physical layer features of the OFDM modulation method and allows one data packet and a number of control messages to be transmitted together. hJam is implemented on the GNU Radio testbed consisting of eight USRP2 nodes. We also conduct comprehensive simulations and the experimental results show that hJam can improve the WLANs efficiency by up to 72% compared with the existing 802.11 family protocols.

Indoor positioning systems have received increasing attention for supporting location-based services in indoor environments. WiFi-based indoor localization has been attractive due to its open access and low cost properties. However, the distance estimation based on received signal strength indicator (RSSI) is easily affected by the temporal and spatial variance due to the multipath effect, which contributes to most of the estimation errors in current systems. How to eliminate such effect so as to enhance the indoor localization performance is a big challenge. In this work, we analyze this effect across the physical layer and account for the undesirable RSSI readings being reported. We explore the frequency diversity of the subcarriers in OFDM systems and propose a novel approach called FILA, which leverages the channel state information (CSI) to alleviate multipath effect at the receiver. We implement the FILA system on commercial 802.11 NICs, and then evaluate its performance in different typical indoor scenarios. The experimental results show that the accuracy and latency of distance calculation can be significantly enhanced by using CSI. Moreover, FILA can significantly improve the localization accuracy compared with the corresponding RSSI approach.

Among the various ranging techniques, Radio Signal Strength (RSS) based approaches attract intensive research interests because of its low cost and wide applicability. RSS-based ranging is apt to be affected by the multipath phenomenon which allows the radio signals to reach the destination through multiple propagation paths. To address this issue, previous works try to profile the environment and refer this profile in run-time. In practical dynamic environments, however, the profile frequently changes and the painful retraining is needed. Rather than such static ways of profiling the environments, in this paper, we try to accommodate the environmental dynamics automatically in real-time. The key observation is that given a pair of nodes, the RSS at different spectrum channels will be different. This difference carries the valuable phase information of the radio signals. By analyzing these RSS values, we are able to identify the amplitude of signals solely from the Line-of-Sight (LOS) path. This LOS amplitude is a simple function of the path length (the physical distance). We find that the analysis is a typical non-linear curvature fitting problem that has no general routing algorithms. We prove this problem format is ill-conditioned which has no stable and trustable solutions. To deal with this issue, we further explore the practical considerations for the problem and reform it to a greatly improved conditioning shape. We solve the problem by numerical iterations and implement these ideas in a real-time indoor tracking system called MuD. MuD employs only three TelosB nodes as anchors. The experiment results show that in a dynamic environment where five people move around, the averaged localization error is 1 meter. Compared with the traditional RSS-based approaches in dynamic environment, the accuracy improves up to 10 times.

The Radio Frequency Identification (RFID) technology has been widely applied to labeling moving objects. In some RFID application scenarios, e.g., product checking on conveyor belt, the tags labeled on the products need to be identified and accessed before moving out of the reader's probing range. Due to the uncertainty of ALOHA protocol and unreliability of wireless links, passing tags will suffer from collisions and link failures, and then move away without successful response. One important requirement for RFID systems is to reliably identify and access all the tags. There is naturally a tradeoff between system throughput and reliability, e.g., tag may have no chance to successfully respond in high moving speed and system throughput drops in low tag moving speed. In this paper, we introduce an integrated software system Reliable Splitting Aware ALOHA (RSAA), which is used to improve system throughput while maintaining a threshold of tag loss probability. Given a tag loss probability, RSAA is able to approach to the optimal system throughput. We implement RSAA on our NI EPC Class 1 Generation 2 UHF RFID Reader Emulator to read and access commercial tags. Experiments in indoor and outdoor scenarios are conducted to demonstrate the efficiency of RSAA. Compared with moving unaware schemes, RSAA can reliably enhance the throughput by 50%~100%. We further use trace-driven simulation to show that RSAA is able to support diverse tag density and large-scale UHF RFID systems.

Most existing connectivity-based localization algorithms require high node density which is unavailable in many large-scale sparse mobile networks. By analyzing large datasets of real user traces from Dartmouth and MIT, we observe that user mobility exhibits high spatiotemporal regularity and, more importantly, that user mobility is strongly correlated with the user's social encounters (including so called Familiar Strangers). Motivated by these important observations, we propose a distributed localization scheme called SOMA that is particularly suitable for sparse mobile networks. To exploit the correlation between mobility and social encounters, we formulate the localization process as an optimization problem with the objective of maximizing the probability of visiting a sequence of locations when the user witnesses the given social encounters at different time. Employing the Hidden Markov Model (HMM), we design an efficient algorithm based on dynamic programming for solving the optimization problem. SOMA is fully distributed, in which each user only makes use of the connectivity information with other users. Experimental results based on large-scale real traces demonstrate that SOMA achieves much smaller localization error than many state-of-the-art localization schemes, but requires minimal running time.

An accurate and sufficient vehicle trajectory data set is the basis to many trajectory-based data mining tasks and applications. However, vehicle trajectories sampled by GPS devices are usually at a relatively low sampling rate and contain notable location errors. To address these two problems in GPS trajectory data, we propose WI-matching, the first vehicle trajectory calibration framework to take advantage of road networks topology and geometry information and trajectory historical information in large scale. WI-matching consists of a Weighting-based map matching algorithm and a trajectory Interpolation-based matching algorithm. In our WI-matching framework, we first integrate the vehicle GPS data with digital road networks data, to identify the roads where a vehicle traveled and the vehicle locations along the roads. Then our weighting-based map matching algorithm considers (1) the geometric and topological information of the road networks and (2) the spatiotemporal trajectory information to efficiently and effectively calibrate the GPS data points. Finally, our interpolation algorithm identifies paths between consecutive GPS points, and adds points with estimated vehicle status (location and time stamp) along the paths to construct sufficient vehicle trajectories. We have evaluated our algorithms on a large-scale real life data set in comparison with the state of the art. Our extensive and empirical results indicate that our WI-matching achieves a high accuracy as well as a high efficiency on real-world data which beats the state of the art.

High-dimensional similarity join (HDSJ) is critical for many novel applications in the domain of mobile data management. Nowadays, performing HDSJs efficiently faces two challenges. First, the scale of datasets is increasing rapidly, making parallel computing on a scalable platform a must. Second, the dimensionality of the data can be up to hundreds or even thousands, which brings about the issue of dimensionality curse. In this paper, we address these challenges and study how to perform parallel HDSJs efficiently in the MapReduce paradigm. Particularly, we propose a cost model to demonstrate that it is important to take both communication and computation costs into account as dimensionality and data volume increases. To this end, we propose DAA (Dimension Aggregation Approximation), an efficient compression approach that can help significantly reduce both these costs when performing parallel HDSJs. Moreover, we design DAA-based parallel HDSJ algorithms which can scale up to massive data sizes and very high dimensionality. We perform extensive experiments using both synthetic and real datasets to evaluate the speedup and the scale up of our algorithms.

Many emerging mobile applications require analyzing large spatial datasets. In these applications, efficient query processing relies on spatial access methods such as R-trees. For datasets that are fairly static, R-trees are often built as a data loading process using packing techniques. However, traditional R-tree packing algorithms can only run on a single machine and thereby cannot scale to very large datasets. In this paper, we design and implement a general framework for parallel Rtree packing using MapReduce. This framework sequentially packs each R-tree level from bottom up. For lower levels that have a large number of rectangles, we propose a partition based algorithm for parallel packing. We also discuss two spatial partitioning methods that can efficiently handle heavily skewed datasets. To evaluate the performance, we conducted extensive experiments using large real datasets. The size of the datasets is up to 100GB and the number of spatial objects is up to 2 billion. Besides range queries, k-nearest neighbor searches and spatial joins are also used for evaluation. To the best of our knowledge, it is the first work that evaluates the query performance of packed R-trees on such large datasets with spatial queries other than range queries. The results confirm the scalability of our proposed framework and parallel packing algorithms. It is also shown that our packed R-trees have good query performance and optimal space utilization.

Topology control is an effective method to improve the energy-efficiency and increase the communication capacity of Wireless Sensor Networks (WSNs). Traditional topology control algorithms are based on deterministic model that fails to consider lossy links which provide only probabilistic connectivity. Noticing this fact, we propose a novel probabilistic network model. We meter the network connectivity using network reachability. It is defined as the minimal of the upper limit of the end-to-end delivery ratio between any pair of nodes in the network. We attempt to find a minimal transmission power for each node while the network reachability is above a given application-specified threshold. The whole procedure is called probabilistic topology control (PTC). We prove that PTC is NP-hard and propose a fully distributed algorithm called BRASP. We prove that BRASP has the guaranteed performance and the communication overhead is O(|E| + |V|). The experimental results show that the network energy-efficiency can be improved by up to 250% and the average node degree is reduced by 50%.

Recent years have witnessed the growing popularity of sensor and sensor-network technologies, supporting important practical applications. One of the fundamental issues is how to accurately locate a user with few labeled data in a wireless sensor network, where a major difficulty arises from the need to label large quantities of user location data, which in turn requires knowledge about the locations of signal transmitters or access points. To solve this problem, we have developed a novel machine learning-based approach that combines collaborative filtering with graph-based semi-supervised learning to learn both mobile users' locations and the locations of access points. Our framework exploits both labeled and unlabeled data from mobile devices and access points. In our two-phase solution, we first build a manifold-based model from a batch of labeled and unlabeled data in an offline training phase and then use a weighted k-nearest-neighbor method to localize a mobile client in an online localization phase. We extend the two-phase colocalization to an online and incremental model that can deal with labeled and unlabeled data that come sequentially and adapt to environmental changes. Finally, we embed an action model to the framework such that additional kinds of sensor signals can be utilized to further boost the performance of mobile tracking. Compared to other state-of-the-art systems, our framework has been shown to be more accurate while requiring less calibration effort in our experiments performed on three different testbeds.

Peer-to-Peer multikeyword searching requires distributed intersection/union operations across wide area networks, raising a large amount of traffic cost. Existing schemes commonly utilize Bloom Filters (BFs) encoding to effectively reduce the traffic cost during the intersection/union operations. In this paper, we address the problem of optimizing the settings of a BF. We show, through mathematical proof, that the optimal setting of BF in terms of traffic cost is determined by the statistical information of the involved inverted lists, not the minimized false positive rate as claimed by previous studies. Through numerical analysis, we demonstrate how to obtain optimal settings. To better evaluate the performance of this design, we conduct comprehensive simulations on TREC WT10G test collection and query logs of a major commercial web search engine. Results show that our design significantly reduces the search traffic and latency of the existing approaches.

Interference is a critical issue in wireless communications. In a typical multiple-user environment, different users may severely interfere with each other. Coordination among users therefore is an indispensable part for interference management in wireless networks. It is known that coordination among multiple nodes is a costly operation taking a significant amount of valuable communication resource. In this paper, we have an interesting observation that by generating intended patterns, some simultaneous transmissions, i.e., "interference,” can be successfully decoded without degrading the effective throughput in original transmission. As such, an extra and "free” coordination channel can be built. Based on this idea, we propose a DC-MAC to leverage this "free” channel for efficient medium access in a multiple-user wireless network. We theoretically analyze the capacity of this channel under different environments with various modulation schemes. USRP2-based implementation experiments show that compared with the widely adopted CSMA, DC-MAC can improve the channel utilization efficiency by up to 250 percent.

IEEE 802.15.4 standard specifies physical layer (PHY) and medium access control (MAC) sublayer protocols for low-rate and low-power communication applications. In this protocol, every 4-bit symbol is encoded into a sequence of 32 chips that are actually transmitted over the air. The 32 chips as a whole is also called a pseudonoise code (PN-Code). Due to complex channel conditions such as attenuation and interference, the transmitted PN-Code will often be received with some PN-Code chips corrupted. In this paper, we conduct a systematic analysis on these errors occurring at chip level. We find that there are notable error patterns corresponding to different cases. We then show that recognizing these patterns enables us to identify the channel condition in great details. We believe that understanding what happened to the transmission in our way can potentially bring benefit to channel coding, routing, and error correction protocol design. Finally, we propose Simple Rule, a simple yet effective method based on the chip error patterns to infer the link condition with an accuracy of over 96 percent in our evaluations.

Efficient and effective full-text retrieval in unstructured peer-to-peer networks remains a challenge in the research community. First, it is difficult, if not impossible, for unstructured P2P systems to effectively locate items with guaranteed recall. Second, existing schemes to improve search success rate often rely on replicating a large number of item replicas across the wide area network, incurring a large amount of communication and storage costs. In this paper, we propose BloomCast, an efficient and effective full-text retrieval scheme, in unstructured P2P networks. By leveraging a hybrid P2P protocol, BloomCast replicates the items uniformly at random across the P2P networks, achieving a guaranteed recall at a communication cost of O(√N), where N is the size of the network. Furthermore, by casting Bloom Filters instead of the raw documents across the network, BloomCast significantly reduces the communication and storage costs for replication. We demonstrate the power of BloomCast design through both mathematical proof and comprehensive simulations based on the query logs from a major commercial search engine and NIST TREC WT10G data collection. Results show that BloomCast achieves an average query recall of 91 percent, which outperforms the existing WP algorithm by 18 percent, while BloomCast greatly reduces the search latency for query processing by 57 percent.

RFID has been gaining popularity due to its variety of applications, such as inventory control and localization. One important issue in RFID system is tag identification. In RFID systems, the tag randomly selects a slot to send a Random Number (RN) packet to contend for identification. Collision happens when multiple tags select the same slot, which makes the RN packet undecodable and thus reduces the channel utilization. In this paper, we redesign the RN pattern to make the collided RNs decodable. By leveraging the collision slots, the system performance can be dramatically enhanced. This novel scheme is called DDC, which is able to directly decode the collisions without exact knowledge of collided RNs. In the DDC scheme, we modify the RN generator in RFID tag and add a collision decoding scheme for RFID reader. We implement DDC in GNU Radio and USRP2 based testbed to verify its feasibility. Both theoretical analysis and testbed experiment show that DDC achieves 40 percent tag read rate gain compared with traditional RFID protocol.

RFID tag identification is a crucial problem in UHF RFID systems. Traditional tag identification algorithms can be classified into two categories, ALOHA-based and tree-based. Both of them are inefficient due to the incidental high coordination cost. In this paper, we bring CSMA into UHF RFID systems to enhance tag read rate by reducing coordination cost. However, it is not straightforward due to the simple hardware design of passive RFID tags, which is unable to sense the transmissions or collisions of other tags. To tackle this challenge, we propose receiver-based CSMA (RCSMA) in this paper. In RCSMA, the reader notifies the tags channel condition. According to different sensing results of reader's notifications, the tags take corresponding actions, e.g., random back off. RCSMA does not require special RFID tag hardware design. An absorbing Markov chain model is presented to analyze the performance of RCSMA and shown to be consistent with the simulation results. Compared with optimized ALOHA-based algorithms and optimized tree-based algorithms, RCSMA can enhance the tag read rate by 30-70 percent under different reader and tag data rates.

Surveillance is a critical problem for harbor protection, border control or the security of commercial facilities. The effective protection of vast near-coast sea surfaces and busy harbor areas from intrusions of unauthorized marine vessels, such as pirates smugglers or, illegal fishermen is particularly challenging. In this paper, we present an innovative solution for ship intrusion detection. Equipped with three-axis accelerometer sensors, we deploy an experimental Wireless Sensor Network (WSN) on the sea's surface to detect ships. Using signal processing techniques and cooperative signal processing, we can detect any passing ships by distinguishing the ship-generated waves from the ocean waves. We design a three-tier intrusion detection system with which we propose to exploit spatial and temporal correlations of an intrusion to increase detection reliability. We conduct evaluations with real data collected in our initial experiments, and provide quantitative analysis of the detection system, such as the successful detection ratio, detection latency, and an estimation of an intruding vessel's velocity.

With the increasing availability of metropolitan transportation data, such as those from vehicle GPSs (Global Positioning Systems) and road-side sensors, it becomes viable for authorities, operators, as well as individuals to analyze the data for a better understanding of the transportation system and possibly improved utilization and planning of the system. We report our experience in building the VAST (Visual Analytics for Smart Transportation) system. Our key observation is that metropolitan transportation data are inherently visual as they are spatio-temporal around road networks. Therefore, we visualize traffic data together with digital maps and support analytical queries through this interactive visual interface. As a case study, we demonstrate VAST on real-world taxi GPS and meter data sets from 15, 000 taxis running two months in a Chinese city of over 10 million population. We discuss the technical challenges in data cleaning, storage, visualization, and query processing, and offer our first-hand lessons learned from developing the system.

Surveillance is a vital problem for harbor protection, border control or the security of other commercial facilities. It is particularly challenging to protect the vast near-coast sea surface and busy harbor areas from intrusions of unauthorized marine vessels, such as trespassing boats and ships. In this paper, we present an innovative solution for ship intrusion detection. Equipped with three-axis accelerometer sensors, we deploy an experimental wireless sensor network on the sea surface to detect ships. Using signal processing techniques and cooperative signal processing, we can detect the passing ships by distinguishing the ship-generated waves and the ocean waves. We design an intrusion detection system in which we propose to exploit spatial and temporal correlations of the intrusion to increase detection reliability. We conduct evaluations with real data collected by our initial experiments, and provide quantitative analysis on the detection system, such as the successful detection ratio and the estimation of the intruding ship velocity.

Energy efficiency is a critical criterion in wireless sensor networks (WSN). Given the energy consumption of a node, or even the whole network, is precisely measured. Great improvement can be expected in the WSN system optimization. In this paper, we propose a versatile nodal energy consumption monitoring schema, which precisely measures the energy consumption of each node at any moment. In addition, our schema can be integrated with existing test bed technologies to measure the energy consumption of the overall network. Results show that our method can fulfill various challenges in energy consumption measurement in wireless sensor network. We believe the design and implementation of this monitoring schema is an important move towards accurate and flexible energy efficiency analysis.

Wireless technologies have gained tremendous popularity in recent years, resulting in a dense deployment of wireless devices. Therefore, it is desired to provide multiple concurrent transmissions by dividing a broadband channel into separate sub channels. This fine-grained channel access calls for efficient channel allocation mechanisms, especially in distributed networks. However, most of the current multichannel access methods rely on costy coordination, which significantly degrade their performance. Motivated by this, we propose a cross layer design called Attachment Learning (AT-learning) in distributed OFDMA (Orthogonal Frequency Division Multiple Access) based networks. AT-learning utilizes jamming technique to attach identifier signals on data traffic, where the identifier signals can help mobile stations to learn allocation strategy by themselves. After the learning stage, mobile stations can achieve a TDMA-like performance, where stations can know when exactly to transmit on which channel without further collisions. We conduct comprehensive simulations and the experimental results show that AT-learning can improve the throughput by up to 300% compared with traditional multichannel access method which asks mobile stations to randomly choose channels without learning.

Transceiver-free object tracking is to trace a moving object without carrying any communication device in an environment where the environment is pre-deployed with some monitoring nodes. Among all the tracking technologies, RF-based technology is an emerging research field facing many challenges. Although we proposed the original idea, until now there is no method achieving scalability without sacrificing latency and accuracy. In this paper, we put forward a real-time tracking system RASS, which can achieve this goal and is promising in the applications like the safeguard system. Our basic idea is to divide the tracking field into different areas, with adjacent areas using different communication channels. So the interference among different areas can be prevented. For each area, three communicating nodes are deployed on the ceiling as a regular triangle to monitor this area. In each triangle area, we use a Support Vector Regression (SVR) model to locate the object. This model simulates the relationship between the signal dynamics caused by the object and the object position. It not only considers the ideal case of signal dynamics caused by the object, but also utilizes their irregular information. As a result it can reach the tracking accuracy to around 1m by just using three nodes in a triangle area with 4m in each side. The experiments show that the tracking latency of the proposed RASS system is bounded by only about 0.26s. Our system scales well to a large deployment field without sacrificing the latency and accuracy.

The large amount of phone call records from mobile operators in a city can inform us how many people are present in any given area and how many are entering or leaving. Each phone call record usually contains the caller and callee IDs, date and time, and the base station where the phone calls are made. As mobile phones are widely used in our daily life, many human behaviors can be revealed by analyzing mobile phone data. In this paper, we propose a comprehensive visual analysis system which can be used to analyze the population's mobility patterns from millions of phone call records. Our system consists of three major components: 1) visual analysis of user groups in a base station; 2) visual analysis of the mobility patterns on different user groups making phone calls in certain base stations; 3) visual analysis of handoff phone call records. Some well-established visualization techniques such as parallel coordinates and pixel-based representations have been integrated into our system. We also develop a novel visualization schemes, Voronoi-diagram-based visual encoding to reveal the unique features of mobile phone data. We have applied our system to real mobile phone data collected in a large city and obtained some interesting findings regarding people's mobility pattern.

Reliable communications are essential for most applications in wireless sensor networks (WSNs). In traditional approaches, the per-hop and end-to-end (E2E) recovery schemes are widely used. These schemes, however, suffer from low E2E success rate and poor energy efficiency in large-scale real environments. Through empirical studies, in this paper we identify three major problems that hinder the efficient and reliable communications. To address these problems, we propose a novel in-middle recovery scheme and realize it by designing and implementing a proliferation routing. Proliferation routing integrates three core technologies, namely, capability-based path finder, a randomized dispersity, and reproduction. Proliferation routing offers great flexibilities for transmissions. It cannot only be applied with any Medium Access Control (MAC) protocols and routing metrics, but also obtains a desired service quality (i.e., transmission success rate, energy cost, etc.) by controlling the system parameters. To demonstrate the effectiveness of proliferation routing, we thoroughly analyze its performance. We also conduct performance evaluations through implementation experiments as well as simulations. In a specific experimental setup, proliferation routing can increase the E2E transmission success rate up to 80 percent compared with the well-known hop-based routing and flooding.

Counting the number of RFID tags (cardinality) is a fundamental problem for large-scale RFID systems. Not only does it satisfy some real application requirements, it also acts as an important aid for RFID identification. Due to the extremely long processing time, slotted ALOHA-based or tree-based arbitration protocols are often impractical for many applications, because tags are usually attached to moving objects and they may have left the readers interrogation region before being counted. Recently, estimation schemes have been proposed to count the approximate number of tags. Most of them, however, suffer from two scalability problems: time inefficiency and multiple-reading. Without resolving these problems, large-scale RFID systems cannot easily apply the estimation scheme as well as the corresponding identification. In this paper, we present the Lottery Frame (LoF) estimation scheme, which can achieve high accuracy, low latency, and scalability. LoF estimates the tag numbers by utilizing the collision information. We show the significant advantages, e.g., high accuracy, short processing time, and low overhead, of the proposed LoF scheme through analysis and simulations.

Intercontact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on intercontact time in urban vehicular environments. In this paper, we carry out an extensive experiment involving thousands of operational taxies in Shanghai city. Studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the intercontact time, that is, the time gap separating two contacts of the same pair of taxies, exhibits an exponential decay, over a large range of timescale. This observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the intercontact time obeys a power law. By analyzing a simplified mobility model that captures the effect of hot areas in the city, we rigorously prove that common traffic influxes, where large volume of traffic converges, play a major role in generating the exponential tail of the intercontact time. Our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis.

Passive tags are widely used in many applications, for example, the supply chain, the food industry and ware-house management. In such applications, the location information of tags is very important. However, the uncertain proper-ties of Received Signal Strength Indicators (RSSI), various backscattering events on different power levels and the directivity of readers prevent traditional ranging-based approaches working well in passive RFID systems. In accordance with our observations during experiments, we create a novel approach to locate a specific tag among objects. Although absolute positions are difficult to obtain, we can estimate locations by building a relative relationship between tags. To reduce the effect of the above limitations, we propose a range-free approach named LocaToR to establish a relative neighborhood graph. We implement our method on a real passive system. Taking environmental factors into consideration, we look at two situations: a controlled chamber and a semi-open space. Experimental results show that our approach can obviously improve the accuracy of the localization system as well as save readers' energy.

Recent years have seen an increasing need of wireless networks in a mobile environment serving for more complex tasks and applications. Mobility becomes an indispensable factor of the system design and has been widely recognized as a general cause of packet loss. Though many works have been done on mobility study, to the best of our knowledge, they are mainly based on simulations or analytical studies that assume idealized link conditions. In this work, we experimentally investigate the nature of the error characteristics of mobility-induced packet losses at "chip-level" in IEEE 802.15.4. We believe this more understanding of mobility-induced packet losses can bring great potential benefits for further study on channel coding, routing and protocol design. Toward this end, we design and implement an efficient algorithm to distinguish mobility-induced packet losses from other packet losses of static environments such as attenuation. Our algorithm is greatly advantaged as it needs no training data even when environment changes. Collecting three corrupted packets is sufficient to obtain a satisfactory performance. This feature makes our design in particular suitable for dynamic and mobile environments, allowing real-time mobility induced loss detection in an online manner. Experiments based on GNU Radio testbed show that our algorithm can provide an accuracy of up to 96%.

Traditional RF-based indoor positioning approaches use only Radio Signal Strength Indicator (RSSI) to locate the target object. But RSSI suffers significantly from the multi-path phenomenon and other environmental factors. Hence, the localization accuracy drops dramatically in a large tracking field. To solve this problem, this paper introduces one more resource, the dynamic of RSSI, which is the variance of signal strength caused by the target object and is more robust to environment changes. By combining these two resources, we are able to greatly improve the accuracy and scalability of current RF-based approaches. We call such hybrid approach COCKTAIL. It employs both the technologies of active RFID and Wireless Sensor Networks (WSNs). Sensors use the dynamic of RSSI to figure out a cluster of reference tags as candidates. The final target location is estimated by using the RSSI relationships between the target tag and candidate reference tags. Experiments show that COCKTAIL can reach a remarkable high degree of localization accuracy to 0:45m, which outperforms significantly to most of the pure RF-based localization approaches.

The growing importance of operations such as identification, location sensing and object tracking has led to increasing interests in contact less Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are mobile and with large numbers, two classical MAC layer collision-arbitration protocols, slotted ALOHA and Tree-traversal, do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides low-latency RFID identification and has stable performance for massive RFID networks. Theoretical analysis and experimental evaluation show that ASAP outperforms most existing collision-arbitration solutions. ASAP is efficient for both small and large deployment of RFID tags, in terms of time and energy cost. Hence it can benefit dynamic and large-scale RFID systems.

Sensing coverage is essential for most applications in wireless networks. In traditional coverage problem study, the disk coverage model has been widely applied because of its simplicity. Though notable recent works point out that the disk model has many critical limitations when applied in practice, few successful works have been conducted to comprehensively study the issue. Motivated by this, in this paper we propose a new coverage model called T-R model. T-R model is derived from a real application of transceiver-free object detection. Compared with the traditional disk model, T-R model is able to describe many new coverage features such as the probabilistic coverage, the link-centric coverage units and the correlations between multiple coverage units. These new capabilities make T-R model a better abstraction of individual sensors. To evaluate the performance of T-R model, we conduct comprehensive empirical studies based on a test-bed of 30 telosB nodes. Experimental results show that the TR model can adequately describe the sensing behavior in the transceiver-free object detection applications. The average error between the model and the reality is only 8%. Moreover, T-R model presents attractive flexibility, making it more appropriate for general coverage problem studies than the transceiver-free object detection.

Spectrum sensing is essential for the success of the cognitive radio networks. In traditional spectrum sensing schemes, Secondary Users (SUs) are responsible for the spectrum sensing which could be very time and resource consuming. It leads to a great deal of inefficiency in spectrum usage and introduces many practical challenges. To tackle these challenges and leverage the spectrum opportunity more efficiently, we propose a new system that provides a spectrum sensing service for SUs using dedicated wireless spectrum sensor networks (WSSNs). In this paper we focus on the sensing channel assignment problem in WSSNs and formulate the problem as a Sensing Effectiveness Maximization Problem (SEMP). We prove that SEMP is NP-complete under the ideal case, and show that the more challenges arises in real environments. To address the issues, we systematically study the design tradeoff and critical factors when maximizing the sensing effectiveness. Based on these study results we propose a Sensing Channel Assignment algorithm (SCAS). We conduct test-bed empirical investigations as well as comprehensive simulations. Performance evaluation results show that for both the scenarios of given deployments and manual deployments, SCAS is able to sense more channels to improve the sensing effectiveness. The improvement is up to 300% and the average improvement is 150% compared with other simple alternatives.

Nowadays, datasets grow enormously both in size and complexity. One of the key issues confronted by large-scale dataset analysis is how to adapt systems to new, unprecedented query loads. Existing systems nail down the data organization scheme once and for all at the beginning of the system design, thus inevitably will see the performance goes down when user requirements change. In this paper, we propose a new paradigm, Data Vitalization, for large-scale dataset analysis. Our goal is to enable high flexibility such that the system is adaptive to complex analytical applications. Specifically, data are organized into a group of vitalized cells, each of which is a collection of data coupled with computing power. As user requirements change over time, cells evolve spontaneously to meet the potential new query loads. Besides basic functionality of Data Vitalization, we also explore an envisioned architecture of Data Vitalization including possible approaches for query processing, data evolution, as well as its tight-coupled mechanism for data storage and computing.

IEEE 802.15.4 standard specifies physical layer (PHY) and medium access control (MAC)sublayer protocols for low-rate and low-power communication applications. In this protocol, every 4-bit symbol is encoded into a sequence of 32 chips that are actually transmitted over the air. The 32 chips as a whole is also called a pseudo-noise code (PN-Code). Due to complex channel conditions such as attenuation and interference, the transmitted PN-Code will often be received with some PN-Code chips corrupted. In this paper, we conduct a systematic analysis on these errors occurring at chip-level. We find that there are notable error patterns corresponding to different cases. Recognizing these patterns will enable us to identify the channel condition in great details. We believe that understanding what happened to the transmission in our setup can potentially bring benefit to channel coding, routing and error correction protocol design.

Spectrum sensing is one of the key enabling technologies in Cognitive Radio Networks (CRNs). In CRNs, secondary users (SUs) are allowed to exploit the spectrum opportunities by sensing and accessing the spectrum, which exhibit many critical limitations in practical environments. In this paper, we propose a new sensing service model that uses dedicated wireless spectrum sensor networks (WSSN) for spectrum sensing. The major challenge in WSSN is the design of data fusion, for which the traditional fusion scheme will produce a large amount of errors. We formulate the problem as a boundary detection problem with notable unknown erroneous inputs. To solve the problem, we propose a novel cooperative boundary detection scheme that intelligently incorporates the cooperative spectrum sensing concept and the recent advances in support vector machine (SVM). Cooperative boundary detection consists of two major components, a declaration calibration algorithm and a boundary derivation algorithm. We prove that cooperative spectrum sensing can asymptotically approach the optimal solution. A prototype system as well as simulation experiments show that compared with the traditional approaches, cooperative boundary detection can reduce the errors by up to 95% with an average reduction about 85%.

Inter-contact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on inter-contact time in urban vehicular environments. In this paper, we carry out an extensive experiment involving thousands of operational taxies in Shanghai city. Studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the inter-contact time, that is the time gap separating two contacts of the same pair of taxies, exhibits a light tail such as one of an exponential distribution, over a large range of timescale. This observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the inter-contact time obeys a power law. By performing a least squares fit, we establish an exponential model that can accurately depict the tail behavior of the inter-contact time in VANETs. Our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis.

Identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. The practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. All these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. In this paper we propose a novel, non-density-based approach called mobility-based clustering. The key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". As such the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. We evaluate the performance of mobility-based clustering based on real traffic situations. Experimental results show that using 0.3% of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm UMicro.

Interference is a critical issue in wireless communications. In a typical multiple-user environment, different users may severely interfere with each other. Coordination among users therefore is an indispensable part for interference management in wireless networks. It is known that, coordination among multiple nodes is a costly operation taking a significant amount of valuable communication resource. In this paper, we have an interesting observation that by generating intended patterns, some simultaneous transmissions, i.e., "interference", can be successfully decoded without degrading the effective throughput in original transmission. As such, an extra and "free" coordination channel can be built. Based on this idea we propose a DC-MAC to leverage this "free" channel for efficient medium access in a multiple-user wireless network. We theoretically analyze the capacity of this channel under different environments with various modulation schemes. USRP2-based implementation experiments show that compared with the widely adopted CSMA, DC-MAC can improve the channel utilization efficiency by up to 250%.

Abstract A mobile node in a MANET must be assigned a free IP address before it may participate in unicast communications. This is a fundamental and difficult problem in the practical application of any MANET. There have been several solutions proposed, among which prophet address allocation outperforms others in terms of communication overhead, latency, and scalability. However, none of the approaches can survive attacks in an insecure environment. Although there are a few secure autoconfiguration schemes proposed, they all have some disadvantages. Based on studies of insecure scenarios, attack schemes, and our previous work, a secure autoconfiguration algorithm, namely secure prophet address allocation, is proposed in the paper. The proposed approach is able to maintain uniqueness of address assignment in the presence of IP spoofing attacks, [state pollution] attacks, and Sybil attacks. The invulnerability of the scheme is supported by both theoretical analysis and simulation results. Copyright © 2009 John Wiley & Sons, Ltd.

Previous multikeyword search in DHT-based P2P systems often relies on multiple single keyword search operations, suffering from unacceptable traffic cost and poor accuracy. Precomputing term-set-based index can significantly reduce the cost but needs exponentially growing index size. Based on our observations that 1) queries are typically short and 2) users usually have limited interests, we propose a novel index pruning method, called TSS. By solely publishing the most relevant term sets from documents on the peers, TSS provides comparable search performance with a centralized solution, while the index size is reduced from exponential to the scale of O(nlog(n)). We evaluate this design through comprehensive trace-driven simulations using the TREC WT10G data collection and the query log of a major commercial search engine.

Topology control is an effective method to improve the energy efficiency of wireless sensor networks (WSNs). Traditional approaches are based on the assumption that a pair of nodes is either "connected" or "disconnected." These approaches are called connectivity-based topology control. In real environments, however, there are many intermittently connected wireless links called lossy links. Taking a succeeded lossy link as an advantage, we are able to construct more energy-efficient topologies. Toward this end, we propose a novel opportunity-based topology control. We show that opportunity-based topology control is a problem of NP-hard. To address this problem in a practical way, we design a fully distributed algorithm called CONREAP based on reliability theory. We prove that CONREAP has a guaranteed performance. The worst running time is O(\vert E\vert ), where E is the link set of the original topology, and the space requirement for individual nodes is O(d), where d is the node degree. To evaluate the performance of CONREAP, we design and implement a prototype system consisting of 50 Berkeley Mica2 motes. We also conducted comprehensive simulations. Experimental results show that compared with the connectivity-based topology control algorithms, CONREAP can improve the energy efficiency of a network up to six times.

Efficient and effective full-text retrieval in unstructured peer-to-peer networks remains a challenge in the research community. First, it is difficult, if not impossible, for unstructured P2P search protocols to effectively locate items with guaranteed recall rate. Second, existing schemes to improve search successful rate often rely on replicating a large number of item replicas across the wide area network, incurring a large amount of communication and storage cost. In this paper we propose BloomCast, an efficient and effective full-text retrieval scheme, in unstructured P2P networks. BloomCast is effective because it guarantees perfect recall rate with high probability. It is efficient because the overall communication cost of full-text search is reduced below a formal bound. Furthermore, by casting Bloom Filters instead of the raw documents across the network, BloomCast significantly reduces the communication cost and storage cost for replication. We demonstrate the power of BloomCast design through both mathematical proof and comprehensive simulations. Results show that BloomCast outperforms existing schemes in terms of both recall rate and communication cost.

Topology control is an effective method to improve energy-efficiency and increase the capacity in Wireless Sensor Networks (WSNs). To fully characterize WSNs with lossy links, we propose a novel probabilistic network model. Under this model, we meter the network quality using network reachability defined as the minimal of the upper limit of the end-to-end delivery ratio between any pair of nodes in the network.We attempt to find a minimal transmitting power for each node while the network reachability is above a given application- specified threshold, called probabilistic topology control (PTC). We prove that PTC is NP-hard and propose a fully distributed algorithm called BRASP. We prove that BRASP has the guaranteed performance. Two rules that must be followed by any algorithm have been identified. We conduct both simulations and prototype implementations based an 18-TelosB-node test- bed. The experimental results show that the network energy- efficiency can be improved by up to 250%. The average node degree is reduced by 50% which will lead to a great benefit for the network capacity.

Intelligent transportation systems have become increasingly important for the public transportation in Shanghai. In response, Shanghai Grid (SG) aims to provide abundant intelligent transportation services to improve the traffic condition. A challenging service in SG is to estimate the real-time traffic condition on surface streets. In this paper, we present an innovative approach SEER to tackle this problem. In SEER, we deploy a cost-effective system of taxi traffic sensors. These taxi sensory data are found to be noisy and very lossy in both time and space. By intensively mining the spatio-temporal correlations along with the evolution of traffic condition, SEER provides wealthy knowledge to setup statistical models for inferring traffic condition when they cannot be directly calculated. As an example, we demonstrate utilizing multichannel singular spectrum analysis (MSSA) to iteratively produce estimates of traffic condition in a metropolitan scale. The optimal window width of MSSA is determined with the basic periodicity found in traffic condition. Moreover, we minimize the number of channels required by MSSA to estimate traffic condition at any location. Given a desired estimation granularity, we optimize the MSSA parameters to minimize the estimation error.

In this paper, we study the trade-off between network throughput and fairness in a multi-channel enabled wireless sensor network (WSN). Traditional approaches attempt to solve the two problems in an isolated manner without a joint design. Our empirical studies show that solutions to these two problems cannot be simply combined. Away from the traditional belief, the number of channels in WSNs with Telosb sensor nodes operating at 2.4 GHz band can be up to 83 and the orthogonal channels can be up to 27. The switching overhead in terms of time and energy cost is relatively small. Furthermore, we observe a buffer wall phenomenon which is one of the main reasons causing network throughput degradation and unfairness. To strike a better trade-off between the network throughput and fairness, we design a novel multi-channel assignment algorithm, targeting at maximizing the minimal data sending rate. The key idea of the proposed algorithm is to level down the buffer wall so that the buffer usage of nodes can be evenly distributed. As such, the bandwidth of bottleneck nodes can be fully utilized and the unfairness due to the node locality can be removed. We prove that the achieved data sending rate is no less than 4/9 of the optimal rate in theory. Our experimental results show that the minimal data sending rate can be improved by up to 100% comparing with the existing work TMCP.

Security is extremely important for the deployment of a mobile ad-hoc networks (MANET) due to its openness to attackers, the absence of an infrastructure, and the lack of centralized administration. Most research efforts have been focused on secure routing protocols, the distributed certificate authority, and key distribution, while a few projects have focused on secure autoconfiguration. However, the importance of integration of a secure autoconfiguration and public-key distribution has been neglected. This paper presents a secure autoconfiguration and public-key distribution algorithm to achieve uniqueness of address allocation and secure public-key distribution when a new node joins a MANET, which provides the bootstrapping for building a distributed certificate authority (DCA) in the network where a trust relationship is absent.

RF-based transceiver-free object tracking, originally proposed by the authors, allows real-time tracking of a moving object, where the object does not have to be equipped with an RF transceiver. Our previous algorithm, the best cover algorithm, suffers from a drawback, i.e., it does not work well when there are multiple objects in the tracking area. In this paper, we propose a localization model of distance, transmission power and the signal dynamics caused by the objects. The signal dynamics are derived from the measured radio signal strength indication (RSSI). Using this new model, we propose the ldquoprobabilistic cover algorithmrdquo which is based on distributed dynamic clustering thus it can dramatically improve the localization accuracy when multiple objects are present. Moreover, the probabilistic cover algorithm can reduce the tracking latency in the system. We argue that the small overhead of the proposed algorithm makes it scalable for large deployment. Experimental results show that in addition to its ability to identify multiple objects, the tracking accuracy is improved at a rate of 10% to 20%.

Recently, System-on-Chip (SoC) technology has been adopted to design smaller, lower-power and cheaper tamper-resistant sensor nodes. In these nodes, we find that there exists a lifetime-secure memory fraction which stores the anterior part of the application executable binary code, namely "fingerprint". We propose a key management protocol based on this secure finger- print-FKM. In this protocol, any pair of nodes can build a secret key by combining two raw key elements randomly selected by both nodes from their fingerprints respectively. To further strengthen the security, we also present two multi-dimension grid key reinforcement schemes. To the best of our knowledge, this paper is the first attempt at the use of application executable binary code itself to develop a key management protocol A thorough analysis shows that FKM supports higher security and superior operational properties while consuming less memory resource compared to the existing key establishment schemes.

By combining an unstructured protocol with a DHT-based index, hybrid Peer-to-Peer (P2P) improves search efficiency in terms of query recall and response time. The key challenge in hybrid search is to estimate the number of peers that can answer a given query. Existing approaches assume that such a number can be directly obtained by computing item popularity. In this work, we show that such an assumption is not always valid, and previous designs cannot distinguish whether items related to a query are distributed in many peers or are in a few peers. To address this issue, we propose QRank, a difficulty-aware hybrid search, which ranks queries by weighting keywords based on term frequency. Using rank values, QRank selects proper search strategies for queries. We conduct comprehensive trace-driven simulations to evaluate this design. Results show that QRank significantly improves the search quality as well as reducing system traffic cost compared with existing approaches.

Intelligent transportation systems have become increasingly important for the public transportation in Shanghai. In response, ShanghaiGrid (SG) project aims to provide abundant intelligent transportation services to improve the traffic condition. A challenging service in SG is to accurately locate the positions of moving vehicles in real time. In this paper, we present an innovative scheme, hierarchical exponential region organization (HERO), to tackle this problem. In SG, the location information of individual vehicles is actively logged in local nodes which are distributed throughout the city. For each vehicle, HERO dynamically maintains an advantageous hierarchy on the overlay network of local nodes to conservatively update the location information only in nearby nodes. By bounding the maximum number of hops the query is routed, HERO guarantees to meet the real-time constraint associated with each vehicle. A small-scale prototype system implementation and extensive simulations based on the real road network and trace data of vehicle movements from Shanghai demonstrate the efficacy of HERO.

In a realistic sensor network, in particular with a non-uniform deployment, sensor nodes inevitably have varying workloads. This causes a natural problem that some sensor nodes are subject to excessive power consumption and thus become hot. These hot nodes deplete much earlier resulting in system performance degradation. This paper proposes a systematic approach to design a hotness-aware sensor network where each node is able to obtain its own hotness information. Based on these vital information, the system is able to provide various technologies to protect the critical set of hot nodes. More specifically, we design a centralized optimal algorithm to derive the precise hotness of each node. In addition, we develop a completely distributed algorithm to estimate hotness with high accuracy. An effective hotness-aware MAC is developed to offer medium access priority to the nodes with higher hotness to protect and prolong their lifetimes. It is demonstrated, through both theoretical analysis and comprehensive simulations, that our approach is valuable to improving system performance of practical sensor networks.

Topology control is an effective method to improve the energy efficiency of wireless sensor networks (WSNs). Traditional approaches are based on the assumption that a pair of nodes is either "connected" or "disconnected". These approaches are called connectivity-based topology control. In real environments however, there are many intermittently connected wireless links called lossy links. Taking a succeeded lossy link as an advantage, we are able to construct more energy-efficient topologies. Towards this end, we propose a novel opportunity-based topology control. We show that opportunity-based topology control is a problem of NPhard. To address this problem in a practical way, we design a fully distributed algorithm called CONREAP based on reliability theory. We prove that CONREAP has a guaranteed performance. The worst running time is O(jEj) where E is the link set of the original topology, and the space requirement for individual nodes is O(d) where d is the node degree. To evaluate the performance of CONREAP, we design and implement a prototype system consisting of 50 BerkeleyMica2 motes. We also conducted comprehensive simulations. Experimental results show that compared with the connectivity-based topology control algorithms, CONREAP can improve the energy efficiency of a network up to 6 times.

Underwater sensor networks (UWSN) are widely used in many applications, such as oceanic resource exploration, pollution monitoring, tsunami warnings and mine reconnaissance. In UWSNs, determining the location information of each sensor node is a critical issue, because many services are based on the localization results. In this paper, we introduce a novel underwater localization approach based on directional signals, which are transmitted by an autonomous underwater vehicle (AUV). Our method utilizes directional beacons (UDB) to replace traditional omni-directional localization which provides more accurate and efficient ways to locate the sensors themselves by simple calculations. The advantage of this novel scheme is that the communications between AUV and sensors are not necessary because the AUV broadcasts signals and sensors only need to passively listen to the signals. Since the energy consumption for transmissions in underwater environments is a nontrivial factor, our localization scheme not only supports accurate positioning, but also reduces energy consumption of sensors. We evaluate our scheme by simulations. The results show that our new approach is very precise in a strap area. At the same time, we minimize the number of beacons issued from the AUV.

It has been of significant importance to provision network-wide guaranteed QoS for a wide range of event detection applications in wireless sensor networks (WSNs). This paper investigates solutions to this QoS provision problem. For event detection applications, there are two key performance metrics, i.e., detection probability and detection latency. This paper focuses on dual-objective QoS provision, taking both metrics into account. This is very challenging due to the stringent resource constraint of sensor nodes and unpredictable randomness of physical events. We propose a novel probabilistic approach to provisioning due-objective QoS. Following a unified framework, we design a distributed algorithm that determines the active probability of every sensor node. The probability is minimized while being sufficient for QoS provision. Our approach is flexible and supports different requirements that may be posed by different applications. Theoretical analysis and comprehensive simulation experiments have been conducted, which jointly demonstrate that our approach is able to deliver guaranteed QoS for distributed event detection while prolonging the system lifetime significantly compared with other alternative schemes.

Intelligent transportation systems have become increasingly important for the public transportation in Shanghai. In response, ShanghaiGrid (SG) aims to provide abundant intelligent transportation services to improve the traffic condition. A challenging service in SG is to accurately locate the positions of moving vehicles in real time. In this paper we present an innovative scheme HERO to tackle this problem. In SG, the location information of individual vehicles is actively logged in local nodes which are distributed throughout the city. For each vehicle, HERO dynamically maintains an advantageous hierarchy on the overlay network of local nodes to conservatively update the location information only in nearby nodes. By bounding the maximum number of hops the query is routed, HERO guarantees to meet the real-time constraint associated with each vehicle. Extensive simulations based on the real road network and trace data of vehicle movements from Shanghai demonstrate the efficacy of HERO.

In wireless sensor networks (WSNs), QoS topology control achieves energy-efficiency by turning off redundant nodes and links, while still satisfying the given QoS requirement. However, existing topology control algorithms assume that links are either connected or disconnected. Recent experiments have shown that, besides the connected and disconnected region, a large percentage of links reside in the transitional region with fluctuating link qualities. In this paper, we propose both centralized and distributed solutions for QoS topology control, where we employ the opportunistic transmission to catch the best transmission opportunities on transitional links. Our simulations demonstrate that opportunistic transmission based approach can significantly improve energy-efficiency in QoS topology control with low communication overhead. A unique contribution of this paper is to consider link quality and apply opportunistic communication in topology control for WSNs.

Geographical hash table (GHT) has been widely used to provide energy efficiency for data-centric storage in wireless sensor networks. Such a mechanism, however, suffers from high communication cost when we apply multi-dimensional event search in the network. In this work, we present MDS, a flexible, complete, and efficient multi-dimensional search mechanism atop traditional GHT based data-centric storage architecture. MDS utilizes bloom filters to reduce the communication cost of in-network intersection and union operations for multi-dimensional queries in wireless sensor networks. This scheme can be easily extended to support multi-dimensional range queries. Our mathematical analysis indicates the optimal settings for the bloom filters that maximize the traffic savings according to the information popularities. We conduct comprehensive simulations to evaluate our design. Results show that MDS achieves significant performance improvement in terms of energy consumptions and thus improves the applicability of the multi-dimensional search over the GHT based data-centric storage in sensor networks.

Current search mechanisms of DHT-based P2P systems can well handle a single keyword search problem. Other than single keyword search, multi-keyword search is quite popular and useful in many real applications. Simply using the solution for single keyword search will require distributed intersection/union operations in wide area networks, leading to unacceptable traffic cost. As it is well known that Bloom Filter (BF) is effective in reducing traffic, we would like to use BF encoding to handle multi-keyword search. Applying BF is not difficult, but how to get optimal results is not trivial. In this study we show, through mathematical proof, that the optimal setting of BF in terms of traffic cost is determined by the global statistical information of keywords, not the minimized false positive rate as claimed by previous methods. Through extensive experiments, we demonstrate how to obtain optimal settings. We further argue that the intersection order between sets is important for multi-keyword search. Thus, we design optimal order strategies based on BF for both "and" and "or" queries. To better evaluate the performance of this design, we conduct extensive simulations on TREC WT10G test collection and the query log of a commercial search engine. Results show that our design significantly reduces the search traffic of existing approach by 73%.

In wireless networks, a client's locations can be estimated using the signals received from various signal transmitters. Static fingerprint-based techniques are commonly used for location estimation, in which a radio map is built by calibrating signal-strength values in the offline phase. These values, compiled into deterministic or probabilistic models, are used for online localization. However, the radio map can be outdated when the signal-strength values change with time due to environmental dynamics, and repeated data calibration is infeasible or expensive. In this paper, we present a novel algorithm, known as LEMT (Location Estimation using Model Trees), to reconstruct a radio map using real-time signal- strength readings received at the reference points. This algorithm can take into account real-time signal-strength values at each time point and make use of the dependency between the estimated locations and reference points. We show that this technique can effectively accommodate the variations of signal strength over different time periods without the need to rebuild the radio maps repeatedly. We demonstrate the effectiveness of our proposed technique on realistic data sets collected from an 802.11b wireless network and a RFID-based network.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so that peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the security and the anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype PT-enabled P2P network. The strengths of our design include (1) no need for a centralized trusted party or CA, (2) high scalability and security, (3) low traffic and cryptography processing overheads, and (4) man-in-middle attack resistance.

A sustainable market-like computational grid has two characteristics: it must allow resource providers and resource consumers to make autonomous scheduling decisions, and both parties of providers and consumers must have sufficient incentives to stay and play in the market. In this paper, we formulate this intuition of optimizing incentives for both parties as a dual-objective scheduling problem. The two objectives identified are to maximize the success rate of job execution and to minimize fairness deviation among resources. The challenge is to develop a grid scheduling scheme that enables individual participants to make autonomous decisions while producing a desirable emergent property in the grid system; that is, the two systemwide objectives are achieved simultaneously. We present an incentive-based scheduling scheme, which utilizes a peer-to-peer decentralized scheduling framework, a set of local heuristic algorithms, and three market instruments of job announcement, price, and competition degree. The performance of this scheme is evaluated via extensive simulation using synthetic and real workloads. The results show that our approach outperforms other scheduling schemes in optimizing incentives for both consumers and providers, leading to highly successful job execution and fair profit allocation.

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Loop scheduling schemes for parallel computers and computer clusters have been proposed in the past. All these schemes are one-dimensional because they partition only the outermost loop of a nested loop construct. In this work, we consider scheduling nested loops with many dimensions. We propose a new methodology which partitions many levels (or dimensions) of nested loops. These new schemes show superior performance over the existing schemes. We implement our new schemes on a network of computers and make performance comparisons with other existing schemes. We expect the new schemes to be particularly useful for multi-core systems because of the fine granularity of the generated tasks.

There exist several scheduling schemes for parallelizing loops without dependences for shared and distributed memory systems. However, efficiently parallelizing loops with dependences is a more complicated task. This becomes even more difficult when the loops are executed on a distributed memory cluster where communication and synchronization can be a bottleneck. The problem lies in the processor idle time which occurs during the beginning and final stages of the execution. In this paper we propose a new scheduling scheme that minimizes the processor idle time and thus it enhances load balancing and performance. The new scheme is applied to two-dimensional iteration spaces with dependences. The proposed scheduling scheme follows a tiled wavefront pattern in which the tile size gradually decreases in all dimensions. We have tested the proposed scheme on a dedicated and homogeneous cluster of workstations and we verified that it significantly improves execution times over scheduling using traditional tiling.

This paper presents the design, implementation and performance evaluation of a new MAC protocol, called A- MAC, for wireless sensor networks. A-MAC combines the strengths of TDMA and CSMA to achieve the goal of low power transmissions for long-term surveillance and monitoring applications, where sensor nodes are typically vigilant for a long time and inactive most of the time until some event is detected. A-MAC employs an advertisement mechanism to eliminate collisions and reduce the overhearing and idle listening, which are the major energy wastes in wireless sensor networks. The distinctive feature of A-MAC is that a node needs to be active only when necessary as it is the transmitter or the receiver. During other times it can safely turn off its radio. Furthermore, to meet different application requirements, A-MAC supports two operation modes by which nodes can adaptively switch their operation modes according to the instant requirements and conditions of the network. A-MAC is implemented in TinyOS. By comparing A-MAC with existing MAC protocols, we show that A-MAC presents significant improvements in terms of power consumption and throughput.

This paper describes the considerations taken in designing cost effective embedded processor development kits to support the take-home self-practice pedagogical strategy. Since each student is issued with such a take-home development kit, special design considerations were given to the choice of processor, the on-board peripheral support, the mode of software development and the development tool support. Two embedded processor development platforms of different complexity are described. One is an 8051 based kit and the other is based on the ARM RISC processor.

By combining an unstructured protocol with a DHT-based global index, hybrid peer-to-peer (P2P) improves search efficiency in terms of query recall and response time. The key challenge in hybrid search is to estimate the number of peers that can answer a given query. Existing approaches assume that such a number can be directly obtained by computing item popularity. In this work, we show that such an assumption is not always valid, and previous designs cannot distinguish whether items related to a query are distributed in many peers or are in a few peers. To address this issue, we propose QRank, a difficulty-aware hybrid search, which ranks queries by weighting keywords based on term frequency. Using rank values, QRank selects proper search strategies for queries. We conduct comprehensive trace-driven simulations to evaluate this design. Results show that QRank significantly improves the search quality as well as reducing system traffic cost compared with existing approaches.

RFID technologies are gaining much attention as they are attractive solutions to many application domains. Localization based on active RFID technologies provides a much needed added-value to further expand the application domain. LANDMARC was the first attempt using active RFID for indoor location sensing with satisfactory results. However, the LANDMARC approach suffers from two drawbacks. First, it does not work well in a closed area with severe radio signal multi-path effects. Second, to further improve the localization accuracy, more reference tags are needed which is costly and may trigger the RF interference phenomenon. The proposed VIRE approach can overcome the above drawbacks without additional cost. Based on the concept of virtual reference tags, a proximity map is maintained by each reader. An elimination algorithm is used to eliminate those unlikely locations to reduce the estimation error. Our experimental results show that the new method consistently enhances the precision of indoor localization from 17 to 73 percent over the LANDMARC approach at different tag locations in different environments.

Surveillance is an important class of applications for wireless senor networks (WSNs), whose central task is to detect events of interest. Existing approaches seriously suffer from blind spots and low energy efficiency. In this paper, we propose a fully distributed algorithm GAP for energy-efficient event detection for surveillance applications. The unique features of GAP are threefold. First, it provides guaranteed detectability for any event occurring in the sensing field. Second, it exposes a convenient interface of the user to specify the desired detectability. Finally, it significantly reduces the duty cycle of each sensor and therefore prolongs system lifetime remarkably. Without relying on costly time synchronization, GAP is a lightweight distributed protocol and is truly scalable to network scale and sensor density. Comprehensive experiments are conducted, which demonstrate the efficacy of the GAP algorithm.

Intelligent transportation systems have become increasingly important for the public transportation in Shanghai. In response, ShanghaiGrid aims to provide abundant intelligent transportation services to improve the traffic condition. A fundamental service in ShanghaiGrid is to locate the nearest desirable vehicles for users. In this paper we propose an innovative protocol ANTS to locate a desirable vehicle close to the querying user. The protocol finely mimics the efficient searching strategy adopted by a lost desert ant in searching for its nest. Taking query locality into account, ANTS can retrieve the nearest vehicles satisfying the query with high probability but incurs small query latency and modest network traffic. ANTS is a fully distributed and robust protocol and therefore has good scalability. Extensive simulations based on the real road network and the trace data of vehicle movements in Shanghai demonstrate the efficacy of ANTS.

In this paper we address the problem of energy-efficient event detection in wireless sensor networks (WSNs). Duty cycling is a fundamental approach to conserving energy in WSNs. However, it brings challenges to event detection in the sense that an event may be undetected or undergo a certain delay before it is detected, in particular when sensors are low duty-cycled. We investigate the fundamental relationship between event detection and energy efficiency. Based on a simplified network model, we quantify event detection performance by deriving the closed forms of detection delay and detectability. We also characterize the intrinsic tradeoff that exists between detection performance and system lifetime, which helps flexible design decisions for WSNs. In addition, we propose a completely localized algorithm, CAS, to cooperatively determine sensor wakeups. Without relying on location information, CAS is easy to implement and scalable to network density. Theoretical bounds of event detection are also studied to facilitate the comparative study. Comprehensive experiments are conducted and results demonstrate that CAS significantly improves detection performance.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the levels of security and anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype implementation. The strengths of pseudo trust include the lack of need for a centralized trusted party or CA, high scalability and security, low traffic and cryptography processing overheads, and man-in-middle attack resistance. We aim for the pseudo trust design to be included in the P2P trust and anonymity context.

In a hybrid peer-to-peer (P2P) system, flooding and DHT are both employed for content locating. The decision to use flooding or DHT largely depends on the population of desired data. Previous works either use local information only, or do not consider dynamic factors of P2P systems. In this paper, we propose a popularity adaptive search method for hybrid (PASH) P2P systems. By dynamically detecting the content popularity, PASH properly selects search methods and efficiently saves query traffic cost and response time. We comprehensively evaluate PASH through synthetic and trace-driven simulations. The results show that PASH outperforms existing approaches and it also scales well.

Having an ID being unique within the application domain for each sensor node is the basic assumption in many WSN applications. In traditional assignments, fixed-length ID schemes, which are severely limited by scalability, flexibility and energy efficiency, are adopted. To solve these problems, we propose a novel variable-length ID scheme that allows different nodes to have different ID lengths. To realize this idea, we propose a fully localized ID assignment algorithm called emphself-organized ID assignment (SIDA). SIDA presents great potential on scalability, flexibility and energy efficiency by enabling online ID assignment and various optimizations according to different communication paradigms. Analytical and simulation results show that SIDA has a comparable static ID length while the accumulated communication overhead for multi-hop transmissions can be saved by 20%; the control overhead of the new deployment assignment can be reduced to about 30% compared with fixed-length schemes.

Reliable transmission service is in dire need for many applications in wireless sensor networks (WSNs). Most existing routing protocols however, seriously suffer from low end-to-end success rates in real deployments. Through extensive experiments on a test-bed of Mica2 nodes, we identify three key problems that hinder the reliable packet delivery. In order to address these problems and therefore to provide a reliability-oriented transmission service, we propose a novel in-middle recovery mechanism that fills the gap between the traditional per-hop recovery and end-to-end recovery mechanisms. To realize such an idea, we design and implement proliferation routing that leverages randomized dispersity and reproduction. The distinctive feature of proliferation routing is its great flexibility. Not only can it be applied with any medium access control (MAC) protocol and routing metric, but also a desired service quality can be effectively derived by controlling the system parameters. Such a feature is revealed by theoretical analysis and confirmed by implementation and simulation experiments. In a specific experiment setup, proliferation routing can increase the end-to-end transmission success rate up to 70% compared with the well-known hop-based routing and flooding.

In wireless sensor networks, connected dominating set (CDS) has become a key technique to identify redundant nodes and extend network lifetime. Most CDS-based algorithms focus on building the minimal CDS to find as many redundant nodes as possible. However, role rotation is not considered so that the dominating nodes will run out of energy much faster than the non-dominating nodes. Existing CDS-based algorithms for maximizing network lifetime rely on the up-to-date remaining energy level (REL) information within h-hop neighborhood to rotate node roles iteratively. Furthermore, global time synchronization is required to synchronize every round. The overhead on REL updating and time synchronization can lead to energy waste and packet collision. In this paper, we first propose a randomized rotation algorithm, which can totally avoid REL updating. Then, dominating node history is added as an enhancement to further extend network lifetime. Finally, we propose a broadcast-based synchronization mechanism to reduce the synchronization overhead and assist dominating node selection. Extensive simulations show that our proposed algorithm can significantly reduce overhead without sacrificing network lifetime.

The persistent nature of physical events makes it possible to detect events using lowly duty-cycled sensors. However, it raises a serious over-detection problem when every sensor blindly wakes up in each cycle, in particular, if sensor density is high. In this paper, we propose an innovative probabilistic wakeup protocol for energy-efficient event detection in wireless sensor networks. The central idea is to reduce the duty cycle of every sensor via probabilistic wakeup, exploiting the dense deployment of sensor networks. A distinctive feature is that the system ensures that the detection delay of any event occurring anywhere in the sensing field is statistically bounded. In addition, the algorithm exposes a convenient interface for users to define the requirement on detection latency, thereby tuning the intrinsic tradeoff between energy efficiency and event detection performance. The algorithm is a lightweight and completely localized protocol, and introduces minimal communication overhead. Extensive experiments have been conducted and results demonstrate that this algorithm significantly prolongs the system lifetime.

The objective of private authentication for radio frequency identification (RFID) systems is to allow valid readers to explicitly authenticate their dominated tags without leaking tags' private information. To achieve this goal, RFID tags issue encrypted authentication messages to the RFID reader, and the reader searches the key space to locate the tags. Due to the lack of efficient key updating algorithms, previous schemes are vulnerable to many active attacks, especially the compromising attack. In this paper, we propose a strong and lightweight RFID private authentication protocol, SPA. By designing a novel key updating method, we achieve the forward secrecy in SPA with an efficient key search algorithm. We also show that, compared with existing designs, SPA is able to effectively defend against both passive and active attacks, including compromising attacks. Through prototype implementation, we observe that SPA is practical and scalable in current RFID infrastructures

In traditional radio-based localization methods, the target object has to carry a transmitter (e.g., active RFID), a receiver (e.g., 802.11x detector), or a transceiver (e.g., sensor node). However, in some applications, such as safe guard systems, it is not possible to meet this precondition. In this paper, we propose a model of signal dynamics to allow tracking of transceiver-free objects. Based on radio signal strength indicator (RSSI), which is readily available in wireless communication, three tracking algorithms are proposed to eliminate noise behaviors and improve accuracy. The midpoint and intersection algorithms can be applied to track a single object without calibration, while the best-cover algorithm has potential to track multiple objects but requires calibration. Our experimental test-bed is a grid sensor array based on MICA2 sensor nodes. The experimental results show that the best side length between sensor nodes in the grid is 2 meters and the best-cover algorithm can reach localization accuracy to 0.99 m

In order to provide scalable live-streaming services, we propose an Inter-Overlay Optimization scheme, IOO. Instead of selecting better paths in the same overlay, IOO constructs efficient paths using peers in different overlays, so as to (i) improve global resource utilization of P2P streaming networks; (ii) assign resources based on their locality and delay; (iii) guarantee streaming service quality by using the nearest peers, even when such peers might belong to different overlays; and (iv) balance the load among the group (streaming overlay) members. We compare the performance of IOO with existing approaches through trace driven simulations. Results show that IOO outperforms previous schemes in terms of resource utilization and the QoS of streaming services. IOO scheme has been implemented in an Internet based live streaming system, called AnySee. AnySee was successfully released in the summer of 2004 in CERNET of China. Over 60,000 users enjoy massive entertainment programs, including TV programs, movies, and academic conferences videos.

The peer-to-peer (P2P) model, being widely adopted in today's Internet computing, suffers from the problem of topology mismatch between the overlay networks and the underlying physical network. Traditional topology optimization techniques identify physically closer nodes to connect as overlay neighbors, but could significantly shrink the search scope. Efforts have been made to address the mismatch problem without sacrificing the search scope, but they either need time synchronization among peers or have a low convergent speed. In this paper, we propose a scalable bipartite overlay (SBO) scheme to optimize the overlay topology by identifying and replacing the mismatched connections. In SBO, we employ an efficient strategy for distributing optimization tasks in peers with different colors. We conducted comprehensive simulations to evaluate this design. The results show that SBO achieves approximately 85 percent of reduction on traffic cost and about 60 percent of reduction on query response time. Our comparisons with previous approaches to address the topology mismatch problem have shown that SBO can achieve a fast convergent speed, without the need of time synchronization among peers.

Sensor networks have emerged as a promising technology with various applications, where power efficiency is one of the critical requirements. The recent IEEE 802.15.4 standard offers a promising platform for wireless sensor networks. Since each node can act as a coordinator or a device in the IEEE 802.15.4 standard, 802.15.4-based sensor networks have various possible network topologies. To reduce power consumption, in this paper, we try to construct network topologies with a small number of coordinators while still maintaining network connectivity. By reducing the number of coordinators, the average duty cycle is reduced and the battery life is prolonged. Three topology control algorithms are proposed in this paper. Self-pruning (SP) is the simplest one with O(1) running time and provides the shortest path to the sink node. Ordinal pruning (OP) can significantly improve SP in terms of power saving with O(n) running time. Layered pruning (LP) is a trade off between the first two pruning algorithms with O(radicn) running time and has a slightly higher power consumption than OP. Furthermore, all three algorithms are independent of the physical radio propagation characteristics. Extensive simulations have been performed to verify the effectiveness of the proposed topology control schemes

Many research activities on wireless sensor networks (WSNs) need detailed performance statistics about protocols, systems, and applications; however, current simulation tools and testbeds lack mechanisms to report these statistics realistically and conveniently. To address this need, we have developed a WSN emulator, VMNet. VMNet emulates networked sensor nodes at the level of CPU clock cycles and executes the binary code of real applications directly. It emulates the radio channel with loss and noise as well as emulates the peripherals in sufficient detail. Moreover, VMNet takes parameter values from the real world and logs detailed runtime information of emulated nodes. Consequently, the application performance, both in response time and in power consumption, is reported realistically in VMNet, as demonstrated by our comparison studies with real sensor networks

The involvement of only the necessary users and service providers for service discovery in pervasive computing environments is challenging. Without prudence, users' and service providers' requests or service information, their identities, and their presence information may be sacrificed. We identify that the problem may be as difficult as a chicken-and-egg problem, in which both users and service providers want the other parties to expose sensitive information first. In this paper, we propose a progressive and probabilistic approach to solve the problem. Users and service providers expose partial information in turn and avoid unnecessary exposure if there is any mismatch. Although 1 or 2 bits of information are exchanged in each message, we prove that the process converges and that the false-positive overhead decreases quickly. Experiments and hypothesis tests show that security properties hold. We implemented the approach and the performance measurements show that the approach runs efficiently on PDAs.

In wireless mobile ad hoc networks (MANETs), energy is a crucial resource. Topology control technology allows network nodes to reduce their transmission power while preserving the network connectivity. A MANET is a non-cooperative system so that only when a node earns its payment, which can cover its cost, the cooperation can be stimulated. We design a truthful topology control mechanism (TRUECON) for MANETs to induce the selfish, but rational, network nodes to collaborate. Truth-telling is a dominant strategy in TRUECON. A node needs to reveal its true value in order to obtain the maximum expected utility. We prove the overpayment of TRUECON has a bound depending on different radio propagation models

Abstract — Efficient and scalable live-streaming overlay construction has become a hot topic recently. In order to improve the performance metrics, such as startup delay, source-to-end delay, and playback continuity, most previous studies focused on intra-overlay optimization. Such approaches have drawbacks including low resource utilization, high startup and source-to-end delay, and unreasonable resource assignment in global P2P networks. Anysee is a peer-to-peer live streaming system and adopts an inter-overlay optimization scheme, in which resources can join multiple overlays, so as to (1) improve global resource utilization and distribute traffic to all physical links evenly; (2) assign resources based on their locality and delay; (3) guarantee streaming service quality by using the nearest peers, even when such peers might belong to different overlays; and (4) balance the load among the group members. We compare the performance of our design with existing approaches based on comprehensive trace driven simulations. Results show that AnySee outperforms previous schemes in resource utilization and the QoS of streaming services. AnySee has been implemented as an Internet based live streaming system, and was successfully released in the summer of 2004 in CERNET of China. Over 60,000 users enjoy massive entertainment programs, including TV programs, movies, and academic conferences. Statistics prove that this design is scalable and robust, and we believe that the wide deployment of AnySee will soon benefit many more Internet users.

Due to critical resource constraints, associating each sensor node with a global ID is not feasible in wireless sensor networks (WSNs). However, having an ID in each sensor node is the basic assumption in many WSN applications. Therefore, efficient local ID generation schemes, which have not been carefully considered in the past, is of great importance. In this paper, we propose a novel local ID assignment scheme, called GREENWIS. Without having the explicit location information in advance, each node is able to generate a 5-tuple local ID within an application field in a distributed manner using the GREENWIS algorithm. We prove the correctness and show the effectiveness of GREENWIS by comprehensive analysis. A GREENWIS prototype is also deployed in our lab. We introduce our early experience with this design and implementation. We evaluate GREENWIS through intensive experiments. The results show that GREENWIS provides effective local ID assignment in a real WSN environment

We propose a novel entity authentication approach for pervasive computing environments. A person uses a single device, the master key, which aggregates all his digital forms of access tokens for entity authentication. The master key discovers and selects proper tokens for its owner. With an emphasis on usability, the master key secures authentication, protects privacy information from outsiders and insiders, and supports various claimant-verifier relations. We analyze privacy and security properties of our approach and protocols, and we investigate the overhead. Performance measurements show that our protocols are efficient

Abstract With the rapid development of high‐speed wide‐area networks and powerful yet low‐cost computational resources, Grid computing has emerged as an attractive computing paradigm. In typical Grid environments, there are two distinct parties, resource consumers and resource providers. Enabling an effective interaction between the two parties (i.e. scheduling jobs of consumers across the resources of providers) is particularly challenging due to the distributed ownership of Grid resources. In this paper, we propose an incentive‐based peer‐to‐peer (P2P) scheduling for Grid computing, with the goal of building a practical and robust computational economy. The goal is realized by building a computational market supporting fair and healthy competition among consumers and providers. Each participant in the market competes actively and behaves independently for its own benefit. A market is said to be healthy if every player in the market gets sufficient incentive for joining the market. To build the healthy computational market, we propose the P2P scheduling infrastructure, which takes the advantages of P2P networks to efficiently support the scheduling. The proposed incentive‐based algorithms are designed for consumers and providers, respectively, to ensure every participant gets sufficient incentive. Simulation results show that our approach is successful in building a healthy and scalable computational economy. Copyright © 2006 John Wiley & Sons, Ltd.

Service Discovery as an essential element in pervasive computing environments is widely accepted. Much research on service discovery has been conducted, but privacy and security have been ignored and may be sacrificed. While it is essential that legitimate users should be able to discover services, it is also necessary that services be hidden from illegitimate users. Since service information, service provider's information, service requests, user presence information, and user's identities may be sensitive, we may want to keep them private during service discovery processes. There appears to be no existing service discovery protocols that solve these problems. We present a user-centric model, called Prudent Exposure, which exposes minimal information privately and securely. Users and service owners exchange code words in an efficient and scalable form to establish mutual trust. Based on the trust, secure service discovery sessions are set up. The model is further improved to counter attacks. We analyze the mathematical properties of our model, formally verify our security protocol, and measure the performance of our prototype system.

Most prevalent distributed certificate authority (DCA) schemes in the MANET are based upon threshold cryptography, which is invulnerable to mobile adversaries and tolerable to missing or faulty DCA server nodes, and thus becomes the "de facto" standard for the security framework in the MANET. However, this scheme cannot defeat Sybil attacks, in which a malicious node impersonates many identities. To solve the problem, a multiple-key cryptography-based DCA scheme, namely the MC-DCA scheme, is proposed in the paper. It is invulnerable to Sybil attacks, and achieves lower communication overhead and moderate latency compared with the threshold-based scheme, which is supported by the simulation results.

In a potential distributed application, automobile tracking system (ATS), automobile location data is continuously generated, kept in a distributed manner. As large amount of traffic will be incurred during search process, it is critical to construct an efficient overlay multicast structure for the ATS so as to distribute traffic to all the physical links evenly, as well as balance the load among group members. In this paper, we propose a distributed protocol, MMT scheme, in which end hosts self-organize into multiple multicast trees. We evaluate the performance of MMT with comprehensive simulations. Experimental results show that MMT outperforms existing approaches in load balance, and its performance penalties are low from the network and the application perspectives.

Sensor networks have emerged as a promising technology with various applications, and power consumption is one of the key issues. Since each full function device can act as a coordinator or a device in IEEE 802.15.4 standard, 802.15.4-based sensor networks have various possible network topologies. In this paper, we try to construct network topologies with small number of coordinators while still maintaining network connectivity. By reducing the number of coordinators, the average duty cycle is reduced and the battery life is prolonged. Three topology control algorithms are proposed in this paper. Self-pruning is the simplest one with O(1) running time. Ordinal pruning significantly improves self-pruning in terms of power saving with O(n) running time. Layered pruning is a tradeoff between the first two pruning algorithms with 0(\sqrt n) running time and a little higher power consumption than ordinal pruning. Furthermore, all three algorithms are independent of the physical radio propagation characteristics.

Database queries, in particular, event-driven continuous queries, are useful for many pervasive computing applications, such as video surveillance. In order to enable these applications, we have developed a pervasive query processing framework called Aorta. Unlike traditional database systems, a pervasive query processor requires systems support for managing a large number of networked, heterogeneous devices. In this paper, we present the communication, synchronization, and scheduling mechanisms in Aorta. Even though these techniques have their roots in distributed and parallel systems, we show how these techniques are customized and applied for pervasive query processing. In essence, communication between heterogeneous devices enables network data independence, synchronization on devices protects action atomicity, and scheduling works for adaptive, cost-based multi-query optimization. We have conducted empirical studies on our prototype as well as simulation studies to evaluate the system performance.

Wireless sensor networks have been widely deployed for monitoring environments of interest. The diffusion stimulus (DS) is a very common and important one in real environments, which is characterized by originating at a source spot and continuously spreading outward. DS-based applications are usually time-sensitive and require high accuracy. It is very challenging, however, for sensor networks to monitor a DS when those sensors could usually monitor one point (the sensing range is zero) only. No existing algorithm is effective and energy-efficient for DS monitoring. In this paper, we propose stimulus-based adaptive sleeping (SAS), to tackle this unique challenge. With SAS, each node independently determines its sleep duration based on its local observations on the stimulus. SAS enables sensors near the stimulus boundary to stay alert to accurately capture the stimulus arrival, and those far away from the stimulus to safely sleep longer for energy efficiency.

In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.

Globally unique ID allocation is usually not applicable in a sensor network due to the massive production of cheap sensor nodes, the limited bandwidth, and the size of the payload. However, locally unique IDs are still necessary for nodes to implement unicast communications to save power consumption. Several solutions have been proposed for locally unique ID assignment in sensor networks. However, they bring much communication overhead, which is not desirable due to the limited power supply in a sensor node. Combined with a directed diffusion communication paradigm, a reactive ID assignment scheme with security mechanisms is proposed in this paper. It defers ID conflict resolution until data communications are initiated and thus saves communication overhead.

In this paper, we present a novel method to adapt the temporal radio maps for indoor location estimation by off-setting the variational environmental factors using data mining techniques and reference points. Environmental variations, which cause the signals to change from time to time even at the same location, present a challenging task for indoor location estimation in the IEEE 802.11b infrastructure. In such a dynamic environment, the radio maps obtained in one time period may not be applicable in other time periods. To solve this problem, we apply a regression analysis to learn the temporal predictive relationship between the signal-strength values received by sparsely located reference points and that received by the mobile device. This temporal prediction model can then be used for online localization based on the newly observed signal-strength values at the client side and the reference points. We show that this technique can effectively accommodate the variations of signal-strength values over different time periods without the need to rebuild the radio maps repeatedly. We also show that the location of mobile device can be accurately determined using this technique with lower density in the distribution of the reference points.

In pervasive computing environments, service discovery facilitates users to access network services by automating tedious manual configurations. When network services become pervasive, the number of service providers also increase dramatically. Because of security and privacy concerns, network services are segmented by service providers. Existing service discovery protocols, however, do not address how to facilitate users to properly identify and authenticate with existing service providers. Without prudence, sensitive information may be exposed. Conversely, with prudence both users and service providers prefer the other party to expose sensitive information first. We identify that even among legitimate users and service providers, there are privacy concerns that may be expressed as a chicken-and-egg problem. In this paper, we propose a progressive approach to solve the problem. Users and service providers expose minimal sensitive information in turn and identify necessary exposure during the process. Theoretical analysis, simulation, and experiments show that our approach protects sensitive information with little overhead.

In March 2004, recognizing the importance of sensor networks, the Chinese Academy of Sciences and the Hong Kong University of Science and Technology launched a joint effort to investigate both fundamental and practical research issues in sensor networks. The goal of this research is to build lightweight optimized sensor systems on a massive scale, namely the BLOSSOMS project. The objective of this research project is to identify research issues at all levels from practical applications down to the design of sensor nodes. This paper reports the status of the project as of April 2005. First, other than making MOTE-compatible sensor nodes, this project has studied the hardware and software co-design and the associated "sensor node on a chip" technology with the aim to make sensor nodes small in size, light in weight, cheap in cost, and low in power consumption. Second, additional toolkits for simulation/emulation and evaluation of sensor networks have been developed to support research at different levels. Third, a number of applications have been investigated and implemented since the launch of this project, and this paper will address two of them. One is an embedded remote health care system based on wireless sensor network technologies to introduce a scalable wireless personal medical network around human's body. The other is a moving object counting system based on an ultrasonic sensor network, which can be used but not limited to crowd estimation and traffic monitoring and coordination.

In unstructured peer-to-peer (P2P) systems, the mechanism of a peer randomly joining and leaving a P2P network causes a topology mismatch between the P2P logical overlay network and the physical underlying network, incurring a large volume of redundant traffic in the Internet. In order to alleviate the topology mismatch problem, we propose adaptive connection establishment (ACE), an algorithm for building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer and further optimizing the neighbor connections that are not on the tree while retaining the search scope. Our simulation study shows that this approach can effectively solve the mismatch problem and significantly reduce P2P traffic. We further study the trade-offs between the topology optimization rate and the information exchange overhead by changing the diameter used to build the tree.

Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies.

Broadcasting is an effective technique to reduce network traffic, and is inherently supported by wireless networks. It thus has been advocated by numerous on-demand data access protocols. In a wireless cellular network, broadcasting can be implemented within a single cell. However, the data owned by different cells could be different. If a client requests a data item available only in a remote cell, an inter-cell data transmission over some wired link is needed, which introduces additional access delay. In this paper, we demonstrate that such delay can be minimized through the use of remote caching. Specifically, we propose a novel cooperative caching scheme, in which each cell dynamically allocates the cache spaces for data from different remote cells. It makes replacement decisions according to several important factors: data item access frequency, cell traffic, and retrieval delay. Simulation results show that the proposed scheme can significantly reduce the response time over the non-cooperative caching scheme under various system configurations.

In unstructured peer-to-peer (P2P) systems, the mechanism of a peer randomly joining and leaving a P2P network causes topology mismatching between the P2P logical overlay network and the physical underlying network, causing a large volume of redundant traffic in the Internet. In order to alleviate the mismatching problem, we propose adaptive connection establishment (ACE), an algorithm of building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer, and further optimizing the neighbor connections that are not on the tree, while retaining the search scope. Our simulation study shows that this approach can effectively solve the mismatching problem and significantly reduce P2P traffic. We further study the tradeoffs between the topology optimization rate and the information exchange overhead by changing the diameter used to build the tree.

Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources, complementing the available client-server services. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatching between the P2P overlay network and the physical underlying network. The topology mismatching problem brings a great stress in the Internet infrastructure and greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique, an algorithm of building an efficient overlay by disconnecting low productive connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network when each node is optimizing the organization of its logical neighbors. The effectiveness of LTM is demonstrated through simulation studies.

When compared with a fixed host that is connected to a hardwired network, a mobile nude in the MANET may change its IP address more frequently due to the deployment of autoconfiguration, global connectivity, and hierarchical addressing schemes. When an IP address changes, the performance of unicast routing protocols and real-time communications may degrade, and privacy may be compromised within the MANET. Although there have been some autoconfiguration algorithms proposed for the assignment of unique IP addresses to mobile nodes, the overhead resulting from address changes has not been carefully examined. Based on studies of the overhead caused by address change, an IP address handoff solution, which extends the unicast routing protocol and network address translation (NAT) scheme, is proposed in the paper. The proposed approach is able to offset the overhead of broken routing fabrics and on-going communications, which is supported by our analysis and a prototype implementation.

Summary form only given. In unstructured peer-to-peer (P2P) systems, the stochastic peer connection and peers' randomly joining and leaving a P2P network without any knowledge about underlying physical topology can cause serious topology mismatching between the P2P overlay network and the physical underlying network. Some existing techniques have been proposed to address topology mismatching problem without shrink search scope. However, these techniques involve considerable amount of overhead, and have other disadvantages, such as slow convergence speed and synchronization requirement. To address the limits of existing solutions, we propose a scalable bipartite overlay (SBO) among peers in Gnutella-like systems or among the super-peers in KaZaA-like systems. SBO employs an efficient strategy to reduce optimization overhead by intelligently distributing optimization tasks in different peers. Our evaluations show that the total traffic and response time of the queries can be significantly reduced by optimized SBO without shrinking the search scope.

Overlay networks have made it easy to implement multicast functionality in wireless ad hoc networks. Their flexibility to adapt to different environments has helped in their steady growth. In MANET, the position of nodes constantly changes; as a result, overlay multicast trees that are built using location information to account for node movement would certainly have a low latency. However, the performance gains of such a tree are offset by the overhead involved in maintaining precise location information. As the degree of (location) accuracy increases, the performance improves but the overhead required to store and broadcast this information also increases. In this paper, we present SOLONet, a design to build a sub-optimal location aided overlay multicast tree, where location updates of each member node are event based. Our simulation results indicate that such a sub-optimal tree does not compromise the performance gains of a location aided overlay multicast tree.

Without assuming any knowledge of the underlying physical topology, the conventional P2P mechanisms are designed to randomly choose logical neighbors, causing a serious topology mismatch problem between the P2P overlay network and the underlying physical network. This mismatch problem incurs a great stress in the Internet infrastructure and adversely restraints the performance gains from the various search or routing techniques. In order to alleviate the mismatch problem, reduce the unnecessary traffic and response time, we propose two schemes, namely, location-aware topology matching (LTM) and scalable bipartite overlay (SBO) techniques. Both LTM and SBO achieve the above goals without bringing any noticeable extra overheads. More-over, both techniques are scalable because the P2P over-lay networks are constructed in a fully distributed manner where global knowledge of the network is not necessary. This paper demonstrates the effectiveness of LTM and SBO, and compares the performance of these two approaches through simulation studies. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Service discovery as an essential element in pervasive computing environments is widely accepted. Much active research on service discovery has been conducted, but privacy has been ignored and may be sacrificed. While it is essential that legitimate users should be able to discover services of which they have credentials, it is also necessary that services be hidden from illegitimate users. Since service information, service provider's information, service requests, and credentials to access services via service discovery protocols may be sensitive, we may want to keep them private. Existing service discovery protocols do not solve these problems. We present a user-centric model, called Prudentexposure, as the first approach designed for exposing minimal information privately, securely, and automatically for both service providers and users of service discovery protocols. We analyze the mathematical properties of our model and formally verify our security protocol.

Network research generally requires a simulation or emulation environment to test protocol implementations, to evaluate the performance of a scheme or a system, and to study complicated and highly varying network operations. For large network simulation, simulators consume a large amount of time and memory; and its result is largely based on some modeling assumptions that may not hold in the real world. Emulators are difficult to scale for large network emulation because of the high cost of equipment if a one-to-one mapping scheme is employed. Otherwise, the target network has to be abstracted to a single router modeled with some performance metrics. We present a distributed IP network emulator cluster EMPOWER, which not only can be used to emulate a large network with a limited number of commodity computers, but also can generate user-defined arbitrary network conditions and traffic dynamics at packet level for specific test scenarios. EMPOWER is highly scalable in that each emulator node could be configured to emulate multiple network nodes, and the increment of the number of emulator nodes does not affect emulation validity. Some significant research issues such as network mapping and mobile wireless network emulation are discussed and addressed. Preliminary emulation results show that EMPOWER is capable of assisting the study of both wireline and wireless network protocols and applications.

Securely accessing unfamiliar services in public environments using ad hoc wireless networks is challenging. We present a proxy-based approach that uses other existing network channels to set up a secure and trust relationship between communication parties to facilitate ad hoc wireless communications. Based on a service discovery protocol, our models achieve secure, trusted, anonymous, efficient, and economical communications between unfamiliar parties. Our protocols are formally verified using BAN logic.

Peer-to-peer (P2P) systems are self-organized and decentralized. However, the mechanism of a peer randomly joining and leaving a P2P network causes topology mismatching between the P2P logical overlay network and the physical underlying network. The topology mismatching problem brings great stress on the Internet infrastructure and seriously limits the performance gain from various search or routing techniques. We propose the adaptive overlay topology optimization (AOTO) technique, an algorithm for building an overlay multicast tree between each source node and its direct logical neighbors so as to alleviate the mismatching problem by choosing closer nodes as logical neighbors, while providing a larger query coverage range. AOTO is scalable and completely distributed in the sense that it does not require global knowledge of the whole overlay network when each node is optimizing the organization of its logical neighbors. The simulation shows that AOTO can effectively solve the mismatching problem and reduce more than 55% of the traffic generated by the P2P system itself.

Network emulation offers real-time simulation that enables test and evaluation of real network systems, protocols, and applications in a reconfigurable and controllable hardware and software environment. Real network traffic is processed by the protocol stacks of physical systems across the entire emulation environment. Standalone emulators can only be used to test end-to-end protocols and applications; simple emulator testbeds are non-scalable due to the one-to-one mapping scheme. We present a distributed emulator cluster that can faithfully emulate large-scale wide area networks with only a considerably smaller number of workstations. In the emulator cluster, a network topology is accurately mapped to a virtual topology in which certain number of virtual nodes are properly configured and emulated. We have developed an algorithm to partition a target network such that each partition can be emulated by a physical node. The emulator cluster can emulate a variety of network conditions and traffic dynamics, as well as incorporating new protocols and models. Preliminary test results show the high scalability of emulator cluster in terms of emulation validity and accuracy with a single physical node and in the entire environment.

Blind flooding is a popular search mechanism used in current commercial P2P systems because of its simplicity. However, blind flooding among peers or super-peers causes large volume of unnecessary traffic although the response time is short. Some improved statistics-based search mechanisms can reduce the traffic volume but also significantly shrink the query coverage range. In some search mechanisms, not all peers may be reachable creating the so-called partial coverage problem. Aiming at alleviating the partial coverage problem and reducing the unnecessary traffic, we propose an efficient and adaptive search mechanism, hybrid periodical flooding (HPF). HPF retains the advantages of statistics-based search mechanisms, alleviates the partial coverage problem, and provides the flexibility to adaptively adjust different parameters to meet different performance requirements. The effectiveness of HPF is demonstrated through simulation studies

The increasing need of protocol development environments and network performance evaluation tools gives rise to the research of flexible, scalable, and accurate network emulators. The desired network emulator should be able to facilitate the emulation of either wireline or wireless networks. In the case when network topology is critical to the underlying network protocol, the emulator should provide specific mechanisms to emulate network topology. In this paper, we present a distributed network emulation system EMPOWER, which not only can fulfill those requirements, but also can generate user-defined network conditions and traffic dynamics at packet level. EMPOWER is highly scalable in that each emulator node could be configured to emulate multiple network nodes. Some significant research issues such as topology mapping scheme and scalability of the emulator are discussed and addressed. Preliminary emulation results show that EMPOWER is capable of assisting the study of both wireless and wireline network protocols and applications.

A mobile device in a MANET must be assigned a free IP address before it may participate in unicast communication. This is a fundamental and difficult problem in the practical use of any MANET. Several solutions have been proposed. However, these approaches have different drawbacks. A new IP address allocation algorithm, namely prophet allocation, is proposed in the paper. The proposed scheme may be applied to large scale MANETs with low complexity, low communication overhead, even address distribution, and low latency. Both theoretical analysis and simulation experiments are conducted to demonstrate the superiority of the proposed algorithm over other known algorithms. Moreover, the proposed prophet allocation is able to solve the problem of network partition and merger efficiently.

Growing convergence among mobile computing devices and embedded technology sparks the development and deployment of "context-aware" applications, where location is the most essential context. We present LANDMARC, a location sensing prototype system that uses Radio Frequency Identification (RFID) technology for locating objects inside buildings. The major advantage of LANDMARC is that it improves the overall accuracy of locating objects by utilizing the concept of reference tags. Based on experimental analysis, we demonstrate that active RFID is a viable and cost-effective candidate for indoor location sensing. Although RFID is not designed for indoor location sensing, we point out three major features that should be added to make RFID technologies competitive in this new and growing market.

In pervasive computing environments, powerful handheld devices with wireless connections create opportunities for many new nomadic applications. We propose a new service discovery model, called Splendor, supporting nomadic users and services in public environments. Splendor emphasizes security and supports privacy. Location awareness is integrated for location dependent services discovery and is used to lessen service discovery network infrastructure requirements. We analyze the Splendor system performance and provide our experimental results.

This paper presents a new handoff protocol named HOPOVER (HandOff Protocol for OVERlay networks). This protocol is compatible with Mobile IP and is designed specifically for overlay networks where handoffs happen both horizontally and vertically. Handoff performance is enhanced by a number of measurements including pre-reserving resources, packet buffering in the new network and packet forwarding from the old network to the new network. Our simulation proved the effectiveness of these measurements.

Differentiated Services (DiffServ) architecture has been proposed as a scheme to provide scalable end-to-end QoS by employing a simple classification based on the DSCP in IP header. One of the major reasons that hinder ISPs to provide DiffServ is that the service level cannot be guaranteed when a specific traffic flow traverses a number of DS and non-DS domains. The issue of the impact of non-DS domains or non-DS routers in a hybrid multi-domain DiffServ network on the performance of Premium Services and Assured Services has been largely ignored by the research community. In this paper, we first present a preliminary queueing analysis of the hybrid multidomain DiffServ network based on a tandem queue model. Then we propose a performance metric called SPI (Service Provision Index) to measure the service level degradation of preferred services in a hybrid multi-domain DiffServ network with respect to an All-DS network. Network simulations and emulations are conducted on a variety of scenarios with different parameter settings to explore the performance of a hybrid multi-domain DiffServ network. Based on the quantitative analysis, the simulation and emulation results, we make some observations on the underlying problem, which could help ISPs or researchers determine the major factors of service degradation, as well as possible directions to improve the services.

We propose a storage cluster architecture CoStore, which evenly distributes system responsibilities across all collaborating cluster members without a separate central file manager. The serverless CoStore architecture has the potential to provide scalable high-performance high-capacity storage services with strong reliability and availability, traditionally only achievable by high-end storage systems. A prototype CoStore system has been implemented using cost-effective COTS-based network attached storage devices on commodity operating systems. The performance of the CoStore prototype has been measured and compared with those of other commonly available distributed file systems. Preliminary test results show that a single node CoStore has a comparable performance to that of NFS and that CoStore outperforms CIFS on Windows 2000.

Network emulation systems are widely used to explore the behavior of network protocols and to test and evaluate protocol implementations and applications. The major problem of a network emulation system is its scalability in terms of emulation capacity and emulation capability of specific network parameters such as maximum emulated bandwidth and emulated packet delay of the system. In particular, an emulator with a large number of workstations is generally too costly for researchers to afford. We present our experience in building a scalable distributed network emulation system named "EMPOWER". EMPOWER provides the unique feature of precisely emulating multiple nodes with a single workstation, making it possible to support large network emulation with a limited number of commodity computers. We describe some critical design issues such as the system resource competition within an emulator node and its impact on the emulation of network throughput and packet delay. We present our methods to determine the maximum number of virtual routers an emulator node can generate and some techniques to improve maximum throughput and packet delay accuracy of an emulator node. We believe such experiences are valuable for the study, design and implementation, performance tuning of a variety of systems such as network emulators and high performance host-based routers.

The development and implementation of new network protocols and applications need accurate, scalable, reconfigurable, and inexpensive tools for debugging, testing, performance tuning and evaluation purposes. Network emulation provides a fully controllable laboratory network environment in which protocols and applications can be evaluated against predefined network conditions and traffic dynamics. In this paper, we present a new framework of network emulation EMPOWER. EMPOWER is capable of generating a decent network model based on the information of an emulated network, and then mapping the model to an emulation configuration in the EMPOWER laboratory network environment. It is highly scalable not only because the number of emulator nodes may be increased without significantly increasing the emulation time or worrying about parallel simulation, but also because the network mapping scheme allows flexible ports aggregation and derivation. By dynamically configuring a virtual device, effects such as link bandwidth, packet delay, packet loss rate, and out-of-order delivery, can be emulated.

This paper studies the statistical model of MPEG video over wireless networks. A real-time MPEG video traffic workload was generated and transmitted over a wireless network. The model parameters of I, B and P frames were measured before and after wireless transmission. The results we got were very interesting. Intuitively, larger frames are more sensitive to network errors. The parameters associated with the statistical model should change after transmission. However, the results of the experiments showed that the statistical models of all I, B and P frames remain almost unchanged after transmission. We repeated the experiment under different wireless link layer error rates and got the same results. To simulate errors, we designed a controllable wireless link layer error model by modifying the WaveLAN device driver which is a Linux kernel module.

Dispersity multicasting is an extension of dispersity routing for multicast communication. In dispersity multicasting, m arc-disjoint subtrees are used for source-destination message delivery. If the bottleneck flow control is applied to each of the m arc-disjoint subtrees, there might still exist extra bandwidth for the multicast communication. To exploit the extra bandwidth, we introduce the concept of virtual connections. We design a flow control algorithm for the available-bit-rate dispersity multicasting with two arc-disjoint subtrees and one virtual connection. Issues in applying the algorithm to ATM networks are discussed. Simulation studies show that, in general, our algorithm enhances the throughput of dispersity multicasting.

In this paper, we present an incremental design of scalable interconnection networks in multicomputer systems using basic building blocks. Both network topologies and routing algorithms are considered. We use wormhole-routed small-scale 2D meshes as basic building blocks. The minimum requirement to expand these networks is a single building block. This implies that the network does not have to maintain the regular 2D mesh topology. Some new topologies are introduced: incomplete meshes based on those adaptive routing algorithms designed from the turn model and extended incomplete meshes based on XY routing. We show that the original routing algorithm can be adopted to send a message between any source and destination without using store-and-forward and causing deadlock. The way that the network is constructed incrementally requires no or a very small amount of rewiring and keeps high bisection density and short diameter of the network. The design methods can be used to economically and incrementally build expandable and scalable parallel computers.

An important part of secure multicast is key management. Up to now, no completely satisfying scheme has been proposed, which might explain why secure multicast is not used extensively. In this paper, we discuss some representative solutions to the key management problem and summarize the advantages and disadvantages of them. Then we propose a new scheme, secure transmission backbone (STB), which provides a general solution for both secure multicast and unicast. In our method, a secure transmission backbone is constructed. With such a backbone, it is no longer necessary for each individual multicast group to maintain keys. The key management problem is thus solved/avoided completely. STB avoids using global keys and protects transmissions on each hop using local keys. STB is based on existing routing protocols, and it is highly robust, reliable and cost effective.

Switching techniques are capable of providing scalable forwarding performance, traffic engineering and quality of service, which are necessary for the next-generation Internet. Switching techniques achieve this by forwarding packets below the network layer, setting up aggregated flows, and laying explicit routes. The proposed framework improves on the current switching techniques. A virtual network port provides a conduit below layer-3 to network ports on remote nodes. It eliminates the need for explicit stack operations and packet fragmentation. It has active controls that allow processing of packets flowing through. We feel that it is conceptually simpler and has better semantics than the other techniques. In this paper we describe an implementation of the framework.

Cut-through switching promises low latency delivery and has been used in new generation switches, especially in high speed networks demanding low communication latency. The interconnection of cut-through switches provides an excellent network platform for high speed local area networks (LANs). For cost and performance reasons. Irregular topologies should be supported in such a switch-based network. Switched irregular networks are truly incrementally scalable and have potential to be reconfigured to adapt to the dynamics of network traffic conditions. Due to the arbitrary topologies of networks, it is critical to develop an efficient deadlock-free routing algorithm. A novel deadlock-free adaptive routing algorithm called adaptive-trail routing is proposed to allow irregular interconnection of cut-through switches. The adaptive routing algorithm is based on two unidirectional adaptive trails constructed from two opposite unidirectional Eulerian trails. Some heuristics are suggested in terms of the selection of Eulerian trails, the avoidance of long routing paths, and the degree of adaptivity. Extensive simulation experiments are conducted to evaluate the performance of the proposed and two other routing algorithms under different topologies and traffic workloads.

Switch-based networks have received much attention in local area networks (LANs) due to their higher network bandwidth and greater interconnect scalability than shared-medium networks. While arbitrary topologies are allowed to provide the needed flexibility and scalability, the design of an appropriate network topology is a challenging issue. In this paper, we discuss design considerations and propose efficient methods for network planning and tuning in switch-based LANs. The idea of block design is applied to initial topology design. For network tuning, a systematic method is proposed to reduce message latency and increase network throughput. Simulations are conducted to demonstrate the performance improvement by applying our method.

Both IP switching and Tag switching were recently proposed to improve the performance of IP routers. They are all based on a multi-layer label-swapping mechanism, but their implementations are quite different. In this paper, we present an overview of both switching mechanisms, compare their key features, identify their constraints, and analyze the effect of these constraints on performance. Our study shows that both IP switching and Tag switching are better than the conventional IP routing, but neither of them is universally superior to the other.

High-speed switches play an important role in building switched LANs. Among different techniques used in switch design, cut-through switching promises short latency delivery and thus is well suited to distributed/parallel applications. The back pressure flow control of cut-through switching also prevents packet loss due to buffer overflow. This paper presents an incremental switch design based on modular building blocks using cut-through switching technique. The switch can be either nonblocking with full configuration and deterministic routing, or blocking but having more flexibility in configuration and fault tolerance. A kind of switch configuration that fits the client/server computing paradigm is presented. Simulation results are given for various switch configurations and traffic loads. The switch also has built-in hardware multicast capability. Issues of physical layout and integration into practical LANs are also discussed.

Multistage interconnection networks (MINs) are a popular class of switch-based network architectures for constructing scalable parallel computers. Four wormhole MINs built from k/spl times/k switches, where k=2/sup i/ for some j, are considered in this paper: traditional MINs (TMINs), dilated MINs (DMINs), MINs with virtual channels (VMINs), and bidirectional MINs (BMINs). The first three MINs are unidirectional networks, and we show that the cube interconnection pattern can provide contention-free and channel-balanced partitioning of binary cube clusters. BMINs based on butterfly interconnection are essentially a fat tree, and their routing properties are described. Performance comparison among these four networks using simulation experiments is presented with respect to different network traffic patterns. Both DMINs (dilation two) and BMINs have a similar hardware complexity. We conclude that a two-dilated MIN outperforms the corresponding BMIN (or fat tree) for most of the traffic conditions and is a better choice for the design of scalable parallel computers.

Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of this paper is on the multistage network system which supports wormhole routed turnaround routing. Existing machines characterized by such a system model include the IBM SP-1 and SP-2, TMC CM-5, and Meiko CS-2. Efficient collective communication among processor nodes is critical to the performance of SPCs. A system-level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application-level broadcast, reduction, and barrier synchronization. This paper addresses how to efficiently implement multicast services in wormhole-routed multistage networks, in the absence of hardware multicast support, by exploiting the properties of the turnaround switching technology. An optimal multicast algorithm is proposed. The results of implementations on a 64-node SP-1 show that the proposed algorithm significantly outperforms the application-level broadcast primitives provided by currently existing collective communication libraries including the public domain MPI.

A fundamental trend for servers in network-centric computing environments is to evolve from traditional database and transaction servers to information distribution and handling systems. In addition to documents written in the HyperText Markup Language (HTML), data stored in other forms can be retrieved through the Common Gateway Interface (CGI). A significant performance bottleneck is the initialization and setup phase for a CGI process to gain access to a backend server. In this paper, we describe the design and implementation of distributed Web server for CGI processes to acquire services efficiently. A Connection Manager Daemon (CMD) is developed to provide a number of cliettes, which are connected to backend servers to eliminate initialization costs for incoming requests. A Cache Manager is implemented to speedup response time in case of repeated requests. We also trace and monitor the Connection Manager Daemon as well as its clients using extended UTE (Unified Trace Environment) tools, and present its performance analysis and visualization. The platforms where we conduct this study include a single-node workstation, a cluster of workstations, and an IBM Scalable Parallel (SP) system.

In essence, the World Wide Web is a worldwide string of computer databases using a common information retrieval architecture. With the increasing popularity of the World Wide Web, more and more functions have been added to retrieve not only documents written in HTML (Hypertext Markup Language), but also those in other forms through the Common Gateway Interface (CGI), by constructing HTML documents dynamically. Dynamic construction of HTML documents for handling information such as digital libraries is slow and requires much more computer power. A significant performance bottleneck is the initialization and setup phase for a CGI process to gain access to the system containing the data. In this paper we describe the design and implementation of a Connection Manager Interface on IBM SP systems. The Connection Manager provides cliette processes to serve CGI requests and eliminates such bottlenecks. An IBM SP system is used for this emerging area to show that our design and implementation is flexible enough to take advantage of the High-Performance Switch in an IBM SP system. We trace and monitor this scalable Web services using UTE (Unified Trace Environment) tools, and present its performance analysis and visualization.

On large-scale multiprocessors, access to common memory is one of the key performance limiting factors. The shared-memory performance depends not only on the characteristics of the memory hierarchy itself, but also upon the characteristics of the memory address streams and the interaction between the two. We present a technique for multiprocessor workload construction and a family of artificial kernels, called MAD-kernels, to systematically investigate the behavior of the memory hierarchy. The measured performance is independent of any particular application or algorithm. The proposed methodology is demonstrated on two commercial shared-memory systems.

Traditionally, each job in a hypercube multiprocessor is allocated with a subcube so that communication interference among jobs may be avoided. Although the hypercube is a powerful processor topology, the 2D mesh is a more popular application topology. This paper presents a 2D-mesh cluster allocation strategy for hypercubes. The proposed auxiliary free list processor allocation strategy can efficiently allocate 2D-mesh dusters without size constraints, can reduce average job turnaround time compared with that based on subcube allocation strategies, and can guarantee no communication interference among allocated clusters when the underlying hypercube implements deadlock-free E-cube routing. The proposed auxiliary free list strategy can be easily implemented on hypercube multicomputers to increase processor utilization.>

Run-time data redistribution can enhance algorithm performance in distributed-memory machines. Explicit redistribution of data can be performed between algorithm phases when a different data decomposition is expected to deliver increased performance for a subsequent phase of computation. Redistribution, however, represents increased program overhead as algorithm computation is discontinued while data are exchanged among processor memories. In this paper, we present a technique that minimizes the amount of data exchange for BLOCK to CYCLIC(c) (or vice-versa) redistributions of arbitrary number of dimensions. Preserving the semantics of the target (destination) distribution pattern, the technique manipulates the data to logical processor mapping of the target pattern. When implemented on an IBM SP, the mapping technique demonstrates redistribution performance improvements of approximately 40% over traditional data to processor mapping. Relative to the traditional mapping technique, the proposed method affords greater flexibility in specifying precisely which data elements are redistributed and which elements remain on-processor.

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.>

Data decomposition across processors is critical to the performance of data parallel programs on distributed-memory machines. The data decomposition problem involves data alignment and data distribution. This paper addresses the data alignment phase, which can be classified into slope alignment and offset alignment. We propose a data reference graph (DRG) model, based on which a slope alignment heuristic algorithm and an offset alignment heuristic algorithm are proposed for the purpose of minimizing interprocessor communication. Such a DRG-based data alignment framework makes our work unique from other related work. The time complexity of both proposed algorithms are in the linear order of distinct references given in a program structure.>

Parallel processing has been a subject of extensive research for over 20 years, especially in the last 10 years, with many commercial parallel machines becoming available, from small scale parallel machines to massively parallel machines. At one time, it was claimed that parallel machines will become the mainstream computers. However, more recently, some parallel computer vendors have gone out of business and some others are struggling. Some pessimists even claimed that this is a dying field. So, what’s wrong? Five distinguished panelists are invited to share their views on this issue. The panelists are also expected to address what could be done and could be done in order to make parallel computers truly mainstream computers. Panelists

A critical issue in achieving the performance of data parallel programs is how to efficiently decompose data across processors. On distributed-memory machines, a good data decomposition should increase processor workload balance and reduce interprocessor communication. Data decomposition consists of data distribution and data alignment. In this paper, we propose a trapezoid data distribution pattern and new data alignment algorithms using alignment graph (AG). Our AG-based alignment framework is unique from other related work because it takes advantage of the effect of optimal expression evaluation with regard to multiple assignment statements.

The clustered parallel computer (CPC), based on a workstation cluster, is becoming popular as a choice for high-performance network or parallel computing. However, operating system overheads, network protocols, and higher message-passing latency contribute to a lower overall communication performance in a cluster of workstations, increasing the likelihood that timesharing of parallel jobs can be used to improve system throughput in a workstation cluster. The traditional means by which the CPC minimizes user job turnaround time (JTT) is through space sharing, in which user jobs are given exclusive control over clusters of processors. The objective of this study is to examine methods by which system utilization may be increased by giving timeshared access to parallel jobs without sacrificing the primary goal of minimizing user JTT.>

Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of the paper is on wormhole routed multistage networks supporting turnaround routing. Existing machines characterized by such a system model include the IBM SP-1, TMC CM-5, and Meiko CS-2. Efficient collective communication among processor nodes is critical to the performance of SPCs. A system level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application level broadcast, reduction, and barrier synchronization. The paper addresses how to efficiently implement multicast services in wormhole routed multistage networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. An optimal multicast algorithm is proposed. The results of implementations on a 64-node SP-1 show that the proposed algorithm significantly outperforms the application level broadcast primitives provided by currently existing collective communication libraries including the public domain MPI.>

This paper presents a model for designing wormhole routing algorithms, A unique

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms.>

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given.>

In order to efficiently exploit global parallelism, it is essential to find a good way to distribute data among the processors in distributed-memory parallel computer systems. A formal technique utilizing augmented data access descriptors (ADADs) to determine this distribution is presented. This technique differs from previous approaclies in that it views the problem of finding a good distribution as an extension of data dependence analysis. The importance of this difference is demonstrated through an explanation of how ADADs facilitate interprocedural analysis, directed loop transformations, and incremental analysis, which may lead to improvements in the eficieiicy of both program developn~enta nd the program itself.

Determining an appropriate data distribution among different memories is critical to the performance of data-parallel programs on distributedmemory machines. By analyzing the computational load of data arrays and the communication cornplexity of various data movement operations in a program, this paper suggests a first-order cost model for determining a small set of appropriate data distribution patterns among many possible choices. A new data distribution specification, name! y CYBLOCK, is proposed to enhance the expressiveness of data distribution specifications being proposed in High Performance Fortran. Cost analysis of two case studies: a linear system solver and a Purdue-set benchmark loop, are used to illustrate the proposed evaluation method. The model correctly predicts the relative performance of the case studies when implemented with various regular data distributions on an nCUBE- 2 multicomputer.

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to develop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

This paper presents the Conflict-Free Mem ory (CFM) architecture for designing scalable sharedmemory multiprocessors. For a single-level CFM archi tecture, the architecture improves multiprocessor perfor mance by eliminating memory and interconnection net work contention and reducing network latency. A hierar chical CFM architecture is introduced in this paper, which presents a new approach in implementing scalable sharedmemory multiprocessors. An invalidation-based write-back cache protocol is proposed for the CFM architecture. This cache coherence protocol preserves the low storage overhead of snoopy cache protocols, while it offers the high scalability of directory-based protocols. Furthermore, with the CFM cache protocol, efficient synchronization operations can be implemented.

Tkaditionally, each job in a hypercube multiprocessor is allocated with a subcube so that communication interference among jobs may be avoided. Although the hypercube is a powerful processor topology, the 2D mesh is a more popular application topology. This paper predents a 2Dmesh cluster allocation strategy for hypercubes. The proposed auxiliary free list procwor allocation strategy can efficiently allocate 2D-mesh clusters without size constraints, can reduce average job turnaround time compared with that based on subcubc allocation strategies, and can guarantee no communication interference among allocated clusters when the underlying hypercube implements deadlockfree Ecube routing. The proposed auxiIiary free list strategy can be easily implemented on hypercube multicomputers to increage processor utilization.

This paper examines some crtttcal tssues raised in the design of libraries for MPCS, such as scalability, portability, recompilation, and flexibility.we adUocate a layered structure of it brary design, comprising a high-level language layer, a machine-independent node layer, a machine-dependent node layer, and an object code layer for diflerent demands and requirements.We discuss the impact of various data decomposition strategies on program performance and the computation and communication analysts techniques employed at different layers.We also propose the concept of the range of scalability as a metric for selectzng the most appropriate implementation.A linear system solver based on the Gaussian elimination method is used as an example to illustrate various design alternates.nessee and Oak Ridge National Laboratory attempts to provide a scalable LAPACK package for dense and banded matrix computations [3].The ComPaSS library being developed at Michigan State University attempts to provide a set of scalable communication

Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed.>

A practical processor self-scheduling scheme, trapezoid self-scheduling, is proposed for arbitrary parallel nested loops in shared-memory multiprocessors. Generally, loops are the richest source of parallelism in parallel programs. To dynamically allocate loop iterations to processors, one may achieve load balancing among processors at the expense of run-time scheduling overhead. By linearly decreasing the chunk size at run time, the best tradeoff between the scheduling overhead and balanced workload can be obtained in the proposed trapezoid self-scheduling approach. Due to its simplicity and flexibility, this approach can be efficiently implemented in any parallel compiler. The small and predictable number of chores also allow efficient management of memory in a static fashion. The experiments conducted in a 96-node Butterfly GP-1000 clearly show the advantage of the trapezoid self-scheduling over other well-known self-scheduling approaches.>

Data dependence uniformization, a method for overcoming the difficulties in parallelizing a doubly nested loop with irregular dependence constraints is proposed. This approach is based on the concept of vector decomposition. A simple set of basic dependences is developed from which all dependence constraints can be composed. The set of basic dependences is added to every iteration to replace all original dependences so that the dependence constraints become uniform. An efficient synchronization method is presented to obey the uniform dependence constraints in every iteration.>

The authors propose a method to characterize the performance of multiprocessor systems at the level of a single grain, called a unit grain, of execution. The characterization is via experimental measurement of individual components of performance. The authors introduce a family of artificial workload kernels, called SAD-kernels, as an effective tool for measuring this performance. The usefulness of these kernels lies in their ability to selectively assess a given shared-memory multiprocessor along several performance dimensions that can be controlled by the person performing the evaluation. The proposed methodology was demonstrated by measuring and comparing the performance of two commercial shared-memory machines currently in use.>

It is shown that wormhole routing in mesh-connected networks can be deadlock free and adaptive without the addition of channels to the basic topology. Several partially adaptive routing algorithms for 2-D and 3-D meshes are described and simulated for a variety of conditions. Simulations of policies for selecting input channels show that transmitting extra information in the header flits can reduce communication latencies at high network throughputs. Simulations of policies for selecting output channels show that avoiding turns reduces latencies at high throughputs. Unrestricted nonminimal routing is found to reduce latencies slightly at low throughputs but increase latencies significantly at high throughputs. For nonuniform traffic patterns, a partially adaptive routing algorithm performs better than a nonadaptive one.>

Practical and efficient implementations of barrier synchronization for wormhole-routed hypercube multicomputers are presented. Both broadcast and multicast barrier synchronization are considered. For systems that do not support hardware broadcast or multicast, a software U-cube tree is proposed. This method generalizes to n-dimensional meshes. Performance measurements for several barrier synchronization techniques implemented on a 64-node nCUBE-2 are given.>

We present a model for designing wormhole routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive. A unique feature of this model is that it is not based on adding physical or virtual channels to network topologies (though it can be applied to networks with extra channels). Instead, the model is based on analyzing the directions in which packets can turn in a network and the cycles that the turns can form. Prohibiting just enough turns to break all of the cycles produces routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive for the network. In this paper, we focus on the two most common network topologies for wormhole routing, n-dimensional mesh, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns permit partial adaptiveness in routing. Partially adaptive routing algorithms are described for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations of partially adaptive and nonadaptive routing algorithms for 2D meshes and hypercubes show that which algorithm has the lowest latencies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, partially adaptive routing algorithms perform better than non-adaptive ones.

The authors describe the initial implementation of the ComPaSS communication library to support scalable software development in massively parallel processors. ComPaSS provides high-level global communication operations for both data manipulation and process control, many of which are based on a small set of low-level communication primitives. The ComPaSS library is unique in that these low-level operations are provably optimal for a class of architectures representative of many commercial scalable systems-in particular, those using wormhole routing and n-dimensional mesh network topologies. The authors concentrate on the multicast component of the ComPaSS library, which is useful in several data parallel operations. The design of the multicast primitive is described, and an example of its use in a data parallel application is given. Improvements in performance resulting from use of the library on a 64-node nCUBE-2 are presented.>

A comprehensive benchmark workload generation and performance characterization methodology is described for multiprocessors supporting the shared-variable computational paradigm. The method can be tailored to meet the selective assessment needs of each individual situation. The approach is based on characterizing a unit grain of computation to generate a desired benchmark workload, and using a family of workload emulation kernels to systematically investigate the effect of each parameter in the workload on the multiprocessor performance. The resultant characterization is independent of any particular application or algorithm.>

Three parallel algorithms, namely, the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm, are proposed for solving tridiagonal linear systems on multicomputers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and nonpivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals the exact solution within machine accuracy. Computation and communication complexities of the three algorithms are presented. All three methods have been implemented on a 64-node nCUBE-1 multicomputer. The analytic results closely match the results measured from the nCUBE-1 machine.>

A fault-tolerant parallel sorting algorithm developed using the application-oriented fault tolerance paradigm is presented. The algorithm is tolerant of one processor/link failure in an n-cube. The addition of reliability to the sorting algorithm results in a performance penalty. Asymptotically, the fault-tolerant algorithm is less costly than host sorting. Experimentally it is shown that fault-tolerant sorting quickly becomes more efficient that host sorting when the bitonic sort/merge is considered. The main contribution is the demonstration that the application-oriented fault tolerance paradigm is applicable to problems of a noniterative-convergent nature.>

The authors identify and incorporate the critical factors that influence nonuniform memory access (NUMA) memory management into their performance metrics. Using trace-driven simulations, it is shown that under certain conditions no replication is better than replication. It is also concluded that the effectiveness of replication depends on: (1) the ratio of access times to remote and local memory, (2) virtual address assignment to data, (3) data sharing characteristics, (4) overhead of enforcing consistency, and (5) amount of physical memory available relative to the data sharing characteristics.>

Efficient routing of messages is the key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. Wormhole routing is the most promising switching technique used in new generation multicomputers. In this paper, we present multicast wormhole routing methods for multicomputers adopting 2D-mesh and hypercube topologies. The dual-path routing algorithm requires less system resource, while the multi-path routing algorithm creates less traffic. More importantly, both routing algorithms are deadlock-free, which is essential to wormhole networks. Keywords: Multicomputers, Heuristic Algorithms, Hypercube Topology, 2D Mesh Topology, Multicast Communication, Wormhole Routing, NP-completeness, Grid Graphs. This work was supported in part by the NSF grants ECS-8814027 and MIP-8811815 ii 1 Introduction The performance of multicomputers is highly dependent on the underlying communicat...

The authors introduce a novel scheme of shared memory organization and interconnection network structure which supports conflict-free accesses to the shared memory in multiprocessors. This scheme also provides a low latency and low cost mechanism for process synchronization. The hot spot problem observed in many multiprocessors can easily be eliminated with this memory organization and interconnection network structure. Extensions to the architecture for supporting large-scale multiprocessors are discussed. It is demonstrated how data consistency can be maintained among concurrent accesses to the same location in a shared memory. In addition, higher level process synchronization supports based on the conflict-free memory architecture are explained.

It is shown that by exchanging any two independent edges in any shortest cycle of the n-cube (n>or=3), its diameter decreases by one unit. This leads to the definition of a new class of n-regular graphs, denoted TQ/sub n/, with 2/sup n/ vertices and diameter n-1, which has the (n-1)-cube as subgraph. Other properties of TQ/sub n/ such as connectivity and the lengths of the disjoints paths are also investigated. Moreover, it is shown that the complete binary tree on 2/sup n/-1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQ/sub n/. How these results can be used to enhance hypercube multiprocessors is discussed.>

The authors present a parallel programming paradigm, resource binding, which offers an architecture-independent environment for various parallel computation models. The resource binding technique, with a simple set of primitives, enables a flexible and consistent way of handling process synchronization, shared resource management, and other problems in parallel programming. High portability can be maintained without losing performance. For a clear introduction to the technique, comparisons are made among resource binding and other well-defined schemes such as semaphore, monitor, message passing, and Linda.>

Three models of parallel speedup are studied: fixed-size speedup, fixed-time speedup, and memory-bounded speedup. Two sets of speedup formulations are derived for these three models. One set requires more information and gives more accurate estimation. Another set considers a simplified case and provides a clear picture of possible performance gain of parallel processing. The simplified fixed-size speedup is Amdahl's law. The simplified fixed-time speedup is Gustafson's scaled speedup. The simplified memory-bounded speedup contains both Amdahl's law and Gustafson's scaled speedup as its special cases. A metric for performance evaluation is proposed.

The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation and by a simple example (a pipeline image distance transformation algorithm). Pipelined data-parallel algorithms are a class of algorithms which use pipelined operations and data level partitioning to achieve parallelism. Applications which involve data parallelism and recurrence relations are good candidates for this kind of algorithm. The computations are ideal for distributed-memory multicomputers. By controlling the granularity through data partitioning and overlapping the operations through pipelining, it is possible to achieve a balanced computation on multicomputers. An analytic model is presented for modeling pipelined data-parallel computation on multicomputers. The model uses timed Petri nets to describe data pipelining operations. As a case study, the model is applied to a pipelined matrix multiplication algorithm. Predicted results match closely with the measured performance on a 64-node NCUBE hypercube multicomputer.>

For pt.I see ibid., p.470-85. A methodology for designing pipelined data-parallel algorithms on multicomputers is studied. The design procedure starts with a sequential algorithm which can be expressed as a nested loop with constant loop-carried dependencies. The procedure's main focus is on partitioning the loop by grouping related iterations together. Grouping is necessary to balance the communication overhead with the available parallelism and to produce pipelined execution patterns, which result in pipelined data-parallel computations. The grouping should satisfy dependence relationships among the iterations and also allow the granularity to be controlled. Various properties of grouping are studied, and methods for generating communication-efficient grouping are given. Given a grouping and an assignment of the groups to the processors, an analytic model is combined with the grouping results to describe the behavior and to estimate the performance of the resultant parallel program. Expressions characterizing the performance are derived.>

The design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions in general are discussed and the bitonic sort algorithm is introduced. Faulty behavior is discussed and a fault-tolerant parallel bitonic sort developed using this paradigm is presented. The error coverage and the response of the fault-tolerant algorithm to faulty behavior are presented. Both asymptotic complexity and the results of run-time experimental measurements on an Ncube multicomputer are given. The authors demonstrate that the application-oriented fault tolerance paradigm is applicable to problems of a noniterative nature.>

Three parallel algorithms, namely the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm are proposed for solving tridiagonal linear systems on multicomputers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.

Computing queries from derived relations, optimizing queries from a group of queries, and updating materialized views are important database problems and have attracted much attention. One thing common to these problems is their demand to quickly solve the implication problem — given two predicates σQ and στ, can σQ imply στ (σQ→στ)? The implication problem has been solved by converting it into a satisfiability problem. Based on a graph representation, a detailed study of the general implication problem on its own is presented in this paper. We proved that the general implication problem, in which all six comparison operators: =, ≠, <, >, ≤, ≥, as well as conjunctions and disjunctions are allowed, is NP-hard. In the case when “≠” operators are not allowed in σQ and disjunctions are not allowed in στ, a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the “≠” operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the “≠” operator or disjunctions in the predicates. Necessary conditions for detecting when the “≠” operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods.

Several parallel convolution algorithms for array processors with N/sup 2/ processing elements (PEs) connected by mesh, hypercube, and shuffle-exchange topologies, respectively, are presented. The computation time complexity is the same for array processors with different interconnection networks. The communication time complexity, however, varies from network to network, and is the main focus. It is shown that by using inter-PE communication networks efficiently, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the overall time complexity (including computation and communication) of algorithms is reduced to O(M/sup 2/).>

A potential system software bottleneck is demonstrated in designing an efficient process scheduling method for multiprocessor systems with shared-memory communication mechanism. The process scheduling overhead is considered. The main contribution of this work is to find the design tradeoffs between monitor bottleneck due to scheduling overhead and low process utilization due to load imbalancing. Choosing an optimum number of scheduling monitors is the key to resolve the bottlenecks. Because of the excessive number of memory requests generated by the dynamic monitor selection method, the use of the fixed monitor selection method is recommended. An analytic estimation provides a lower bound in determining the optimum number of monitors. Hill-climbing simulation is then used to find the optimum number of monitors.>

The ability to quickly determine how to derive a given query from a set of prestored fragments is highly demanded in many database applications, especially in distributed database systems, where the communication cost is a major concern. The main difficulty in solving this problem lies in the implication problem given two predicates σQ and σT, can σQ imply σT(σQ → σT)? The implication problem has been solved by converting it into a satisfiability problem. No detailed study of the implication problem on its own has been presented. In this paper, we study the general implication problem in which all six comparison operators: = , ǂ <, =, ≤, ≥, as well as conjunctions and disjunctions are allowed. We proved that the general implication problem is NP-hard. In the case when “ ǂ” operators are not allowed in σQ and disjunctions are not allowed in σT, a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the “ ǂ ” operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the operator or disjunctions in the predicates. Necessary conditions for detecting when the operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods. © 1989 IEEE

The use of executable assertions is a powerful tool with which to perform program verification, provide software fault-tolerance, and provide hardware fault-tolerance via the application-oriented paradigm. The authors show that assertions commonly used in the sequential programming environment are inadequate for the distributed parallel environment. In particular, it is shown that even design-based assertions are myopic and provide inadequate error coverage. In their place, a triad of basic metrics is proposed for certain classes of problems that, when applied beginning with the specification phase of the life cycle, produce assertions that are better suited to the parallel environment. This method is applied to a well-known parallel computing problem in order to demonstrate the effectiveness of the method. Error coverage is modeled probabilistically so that the dominance of assertions may be quantified.>

A new style of efficient parallel algorithms on distributed-memory multiprocessors is introduced, which exploits parallelism through pipelined parallel computation, or large-grain pipelining. By using macro-pipelining between nodes in the system, large-grain pipelining regulates the flows of data in the multiprocessor so that the degree of overlapping can be maximized and the effect of communication overhead can be minimized. To model pipelined parallel computations, an analytic model is presented, which takes into account both underlying architecture and algorithm behavior. The resultant model is accurate enough to not only predict the performance of a given algorithm, but also assist in algorithm designs for determining optimal design parameters such as the granularity. Results from experiments performed on a 64-node NCUBE multiprocessor match closely to the predicted performance. A systematic procedure for designing pipelined data parallel algorithms from nested loop programs is described. The impact of the second generation distributed-memory multiprocessors on the pipelined parallel computations is also discussed.

The authors present a general model which can be used to analyze and compare the steady-state behavior of these protocols in a unified manner. The global behavior of a multiaccess protocol for a bus network is characterized by a transmission phase, a resolution phase, and an idle phase. Steady-state equations for a general service distribution are derived for each phase using the method of supplementary variables. The resulting model is then used to determine the steady-state behavior of two classes of networks: those with a finite number of stations and those with a number of stations large enough to be considered infinite. Numerical examples are then given for two specific service distributions to illustrate the effect of specific parameters on the performance of a multiaccess protocol.>

Using the framework of cyclic-service systems with a single server, two different token-passing models are investigated. The first model is approximate, obtaining the free-tokens cycle-time distribution on an asymmetric system with infinite capacity buffers and single-token operation. The second model is exact, yielding the cycle-time distribution of the free token on an asymmetric system with unit-capacity buffers, and single-token operation. The latter result is verified using known results for symmetric, unit-capacity buffer systems. To demonstrate the positive effects of buffering, a small variation of the unit-capacity buffering scheme is introduced. Computational results include performance measures such as throughput, utilization, loss probabilities, mean cycle times, cycle-time distributions, and a comparison of two buffering schemes.>

A novel rule-based circuit representation is proposed to describe the connectivities of CMOS circuits at the transistor level. The unique feature of the rule-based representation is its ability to automate CMOS circuit design and verification. A precise symbolic description of the functionality of a transistor-level circuit can be derived based on a set of production rules in linear time. Automated synthesis and verification of CMOS logic circuits are demonstrated.

This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 N/K + log2 N * log2 K) for the N2K2-PE system (1 ¿ K ¿ M), or to O(N2M2/L2) for the L2-PE system (L ¿ N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.

In the above paper, an error was made in the Load Balancing Algorithm. A more clear recursive way to present this algorithm is to modify steps S3 to S5 as follows.

The hypergeometric distribution is a widely used arithmetic function and is fundamental to many statistical sampling and statistical pattern recognition problems. Computation of the cumulative hypergeometric distribution function, H(a), is extremely time-consuming. As a result, many approximation algorithms have been proposed to evaluate the cumulative hypergeometric distribution. This paper describes a two-level pipeline architecture for computing H(a) with computation complexity reduced to c+a, where c is a constant. The main part of the design is a type of recurrence computation. A modular and systematic approach is suggested to implement the recurrence formula. The computation complexity of the proposed architecture is also compared with various other known methods. The highly regular structure of the design can lead to efficient VLSI implementation.

Cluster analysis is a valuable tool in exploratory pattern analysis, especially when very little prior information about the data is available. In unsupervised pattern recognition and image segmentation applications, clustering techniques play an important role. The squared-error clustering technique is the most popular one among different clustering techniques. Due to the iterative nature of the squared-error clustering, it demands substantial CPU time, even for modest numbers of patterns. Recent advances in VLSI microelectronic technology triggered the idea of implementing the squared-error clustering directly in hardware. A two-level pipelined systolic pattern clustering array is proposed in this paper. The memory storage and access schemes are designed to enable a rhythmic data flow between processing units. Each processing unit is pipelined to further enhance the system performance. The total processing time for each pass of pattern labeling and cluster center updating is essentially dominated by the time required to fetch the pattern matrix once. Detailed architectural configuration, system performance evaluation, and simulation experiments are presented. The modularity and the regularity of the system architecture make it suited for VLSI implementations.

Vector-reduction arithmetic accepts vectors as inputs and produces scalars as outputs. This class of vector operation forms the basis of many scientific computations, such as inner product and finding the maximum among the vector components. Vector reduction on a pipeline processor demands a feedback connection around the pipeline. Since the output of such a pipeline depends on the previous output, improper control of the feedback input may destroy the benefit from pipelining. Two new vector-reduction techniques are proposed in this paper. In addition to saving reduction time and eliminating intermediate storage (as compared to Kuck's method and Kogge's method), the new methods will greatly simplify the machine-level programming effort needed to implement vector-reduction operations. An interleaved technique is introduced to reduce multiple vectors to corresponding scalars using the same arithmetic pipeline. The pipeline can be fully utilized by interleaving multiple vector-reduction processes. The proposed techniques can be applied to improve the performance of vector-arithmetic pipelines in scientific supercomputers.

A loosely coupled multiprocessor system contains multiple processors which have their own local memories. To balance the load among multiple processors is of fundamental importance in enhancing the performance of such a multiple processor system. Probabilistic load balancing in a heterogeneous multiple processor system with many job classes is considered in this study. The load balancing scheme is formulated as a nonlinear programming problem with linear constraints. An optimal probabilistic load balancing algorithm is proposed to solve this nonlinear programming problem. The proposed load balancing method is proven globally optimum in the sense that it results in a minimum overall average job response time on a probabilistic basis.

It is desirable for the load in a distributed system to be balanced evenly. A dynamic process migration protocol is needed in order to achieve load balancing in a user transparent manner. A distributed algorthim for load balancing which is network topology independent is proposed in this paper. Different network topologies and low-level communications protocols affect the choice of only some system design parameters. The "drafting" algorithm attempts to compromise two contradictory goals: maximize the processor utilization and minimize the communication overhead. The main objective of this paper is to describe the dynamic process migration protocol based on the proposed drafting algorithm. A sample distributed system is used to further illustrate the drafting algorithm and to show how to define system design parameters. The system performance is measured by simulation experiments based on the sample system.

Vector reduction arithmetic accepts a vector as input and produces a scalar output. This class of vector operations forms the basis of many scientific computations. In a pipelined processor, a feedback loop is required to reduce vectors. Since the output of the pipeline depends on previous outputs, improper control of the feedback loop will destroy the benefit from pipelining. A generalized computing model is proposed to schedule the activities in a vector reduction pipeline. Two new vector reduction methods, symmetric and asymmetric, are proposed and analyzed for pipelined processing. These two methods compare favorably with the known recursive reduction method in achieving higher pipeline utilization and in eliminating large memory for intermediate results. An interleaving method is proposed to reduce multiple vectors to multiple scalars in a single arithmetic pipeline. The pipeline can be fully utilized by interleaved multiple vector processing.

Carrier sense multiple access with collision detection (CSMA/CD) protocols have been extensively studied and developed for local area networks. In CSMA/CD protocols, all messages are treated equally in competing for the communication channel. Thus, important or time-critical messages may be severely delayed. In this paper, a new CSMA/CD protocol with message-based priority functions is proposed. A priority code comparison period is needed to determine the highest priority class that can compete for the comunication channel. A contention period based on CSMA/CD scheme is then followed. Both nonpreemptive discipline and preemptive discipline are discussed. In each discipline, both the single mode and the batch mode are considered and compared. The overhead in implementing the proposed protocol, either for a few or for a large number of priority classes, is shown to be minimal. In general, a preemptive single mode scheme provides a better performance. The requirements of hierarchical independence of performance and fairness are satisfied.

This paper presents a multiprocessor system architecture and the scheduling policies of the processors which can off-load a host computer in the image processing of office documents. The objective of this system is to provide extensive image processing capabilities at minimum cost and with an acceptable interactive response time. Multiprocessor system architecture, image partitioning strategies, image processing algorithm characteristics, performance modeling, and processor scheduling policies are investigated. A prototype multiprocessor image processing system has been built at the IBM San Jose Research Laboratory.

This paper presents a Markov chain model to analyze the performance of shared-resource array processors for multiple vector processing. Such a parallel processor contains multiple control units sharing a resource pool of processing elements and operating with multiple single-instruction multiple-data streams (MSIMD). In the steady state, the Markov model corresponds to a two-dimensional Markov chain, which can be expressed by a set of equilibrium equations. An iterative method is developed to solve the Markov chain after projecting the equilibrium equations onto a one-dimensional state space. The convergence rate of the iterative method can be greatly enhanced by choosing starting values corresponding to the approximated analytical results obtained earlier by the authors.

Performance optimization of a shared-resource parallel computer is studied in this correspondence. Such a parallel computer contains multiple control units (CU's) sharing a resource pool of processing elements (PE's) and operating with multiple single-instruction-multiple-data (MSIMD) streams. A formal queueing model is proposed for MSIMD machines used in multiple array processing. Analytic results are obtained to evaluate the performance of MSIMD computers. Systematic procedures are given to optimize the size of PE resource pool and to determine the sufficient job queue size for a given vector workload distribution.