29456782
Query privacy in wireless sensor networks
Existing mechanisms for querying wireless sensor networks leak client interests to the servers performing the queries. The leaks are not only in terms of specific regions but also of client access patterns. In this paper we introduce the problem of preserving the privacy of clients querying a wireless sensor network owned by untrusted organizations. We investigate two architectures and their corresponding trust models. For the first model, consisting of multiple, mutually distrusting servers governing the network, we devise an efficient protocol, SPYC, and show that it provides full query privacy. For the second model, where all queries are performed through a single server, we introduce two metrics for quantifying the privacy achieved by a client's query sequence. We propose a suite of practical algorithms, then analyze the privacy and efficiency levels they provide. Our TOSSIM simulations show that the proposed query mechanisms are communication efficient while significantly improving client query privacy levels.
6083994
On communication models for algorithm design in networked sensor systems: A case study,
Towards building a systematic methodology of algorithm design for applications of networked sensor systems, we formally define two link-wise communication models, the Collision Free Model (CFM) and the Collision Aware Model (CAM). While CFM provides ease of programming and analysis for high level application functionality, CAM enables more accurate performance analysis and hence more efficient algorithms through cross-layer optimization, at the expense of increased programming and analysis complexity. These communication models are part of an abstract network model, above which algorithm design and performance optimization is performed. We use the example of optimizing a probability based broadcasting scheme under CAM to illustrate algorithm optimization based on the defined models. Specifically, we present an analytical framework that facilitates an accurate modeling and analysis for the probability based broadcasting in CAM (PB_CAM). Our analytical results indicate that (1) the optimal broadcast probability for either maximizing the reachability within a given latency constraint or minimizing the latency for a given reachability constraint decreases rapidly with node density, and (2) the optimal probability for either maximizing the reachability with a given energy constraint or minimizing the energy cost for a given reachability constraint varies slowly between 0 and 0.1 over the entire range of the variations in node density. Our analysis is also confirmed by extensive simulation results.
39238334
Information Processing and Routing in Wireless Sensor Networks
Introduction of Wireless Sensor Networks Background Energy Models Information Processing within a Collocated Cluster Information Transportation over a Tree Substrate Information Routing with Tunable Compression.
15352374
Network-Aware State Update For Large Scale Mobile Games
In large scale mobile gaming environments, efficient mechanisms for state update is crucial to allow graceful real-time interaction of a large number of players, under limited wireless network bandwidth. By using the state updating threshold as a key parameter that bridges the resulting state inconsistency (or distortion) and the network traffic, we are able to model the fundamental traffic-distortion tradeoffs. Given the tradeoffs for all users, an optimal bandwidth allocation can be derived using well-known convex programming techniques. By exploring the temporal locality of gaming behavior, we also propose a prediction method to realize on-line bandwidth adaptation. Using real data trace from a multi-player driving game, the proposed network aware bandwidth allocation method, NABA, is able to achieve significant reduction in state distortion compared to two baselines: Uniform and Proportional policies. NABA is also adaptable to variations in system parameters, including bandwidth constraint and network delay.
2701730
Data Gathering with Tunable Compression in Sensor Networks
We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computationally intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective trade-offs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology, as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant-factor approximation for the grid topology and good average performance on the general graphs. Although, theoretically, a more complicated randomized algorithm offers a polylogarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation.
17009533
Utility-Driven Spatiotemporal Sampling Using Mobile Sensors
Many real-world applications for sensor networks require event sampling with sufficient resolution over both spatial and temporal dimensions. When the deployed nodes are insufficient to fully cover the sensor field to satisfy this spatiotemporal sampling requirements of all events, nodes with intelligent mobility are crucial to improve the sampling quality. We measure the sampling quality using a utility function that incorporates both the importance and spatiotemporal properties of events. We then describe a Utility Driven Mobility (UDM) scheme, which enables autonomous mobility scheduling of nodes in a distributed fashion. We evaluate the performance of UDM via extensive simulation studies. Our work provides a practical framework for spatiotemporal sampling using mobile sensor networks.
33694964
Workflow scheduling in grids: an ant colony optimization approach
Grid applications in virtue of open service grid architecture (OGSA) are promising next-generation computation techniques. One of the most important and challenging problems about grid application is the workflow scheduling problem to achieve the users' QoS (quality of service) requirements as well as to minimize the cost. This paper proposes an ant colony optimization (ACO) algorithm to tackle this problem. Several new features are introduced to the algorithm. First, we define two kinds of pheromone and three kinds of heuristic information to guide the search direction of ants for this bi-criteria problem. Each ant uses either one from these heuristic types and pheromone types in each iteration based on the probabilities controlled by two parameters. These two parameters are adaptively adjusted in the process of the algorithm. Second, we use the information of partial solutions to modify the bias of ants so that inferior choices will be ignored. Moreover, the experimental results in 3 workflow applications under different deadline constraints show that the performance of our algorithm is very promising, for it outperforms the Deadline-MDP algorithm in most cases.
52872567
A Clustering Approach to Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-Hop Relay Networks
In this paper, a clustering approach to solve a network planning problem for 802.16J relay networks is considered. Our clustering approach consists of three basic steps: (1) divide the nodes into k distinct clusters, (2) solve the planning problem separately for each cluster, and (3) perform a final optimization to reduce issues arising at cluster boundaries. Simulation results show that our approach is more efficient than existing approaches: solutions of equivalent quality can be found in 40% of the time. Thus our technique can be used to solve larger problems with similar hardware, or similar size problems in less time.
14595772
Performance analysis of practical RDT interconnection networks with SINOMP
RDT (recursive diagonal torus) consisting of recursively structured mesh/torus connections is a class of interconnection networks for massively parallel computers (MFCs). RDT(2,2,1)//spl alpha/ is one of its practical structure. It is suitable for the practical parallel computers due to its simple torus assignment and routing algorithm. In this paper, the method to compute its theoretical average distance, which is the performance index, is proposed. According to this method, the theoretical performance of RDT(2,2,1)//spl alpha/ is evaluated. The indices showing the performances of the practical communication process are obtained with an interconnection network simulator named SINOMP. After analyzing these performances, the suitable for the middle-size parallel computers is validated.
14236359
Semi-naive Exploitation of One-Dependence Estimators
It is well known that the key of Bayesian classifier learning is to balance the two important issues, that is, the exploration of attribute dependencies in high orders for ensuring a sufficient flexibility in approximating the ground-truth dependencies, and the exploration of low orders for ensuring a stable probability estimate from limited training samples. By allowing one-order attribute dependencies, one-dependence estimators (ODEs) have been shown to be able to approximate the ground-truth attribute dependencies whilst keeping the effectiveness of probability estimation, and therefore leading to excellent performance. In previous studies, however, ODEs were exploited in simple ways, such as by averaging, for classification. In this paper, we propose a semi-naive exploitation of ODEs that fits a function of ODEs to pursue higher-order attribute dependencies. Extensive experiments show that the proposed SNODE approach can achieve better performance than many state-of-the-art Bayesian classifiers.
15348979
Cocktail Ensemble for Regression
This paper is motivated to improve the performance of individual ensembles using a hybrid mechanism in the regression setting. Based on an error-ambiguity decomposition, we formally analyze the optimal linear combination of two base ensembles, which is then extended to multiple individual ensembles via pairwise combinations. The Cocktail ensemble approach is proposed based on this analysis. Experiments over a broad range of data sets show that the proposed approach outperforms the individual ensembles, two other methods of ensemble combination, and two state-of-the-art regression approaches.