We present a framework for analyzing the effects of random and selective compromises (using order statistics) in sensor networks. We discuss the problem of ensuring data integrity at the source and during transit in sensor networks, and present an analysis of the reliability of reports from mobile collectors. No analysis has appeared in the literature of source integrity for mobile nodes, or of selective attacks in sensor networks. We address transit data integrity by presenting mGKE, a key establishment scheme for general group-based sensor deployments, and present a detailed analytical and experimental comparison of mGKE with current schemes. mGKE outperforms current methods in terms of resilience, connectivity, and memory and communication overhead.

Applications such as traffic management and resource scheduling for location-based services commonly need to identify regions with high concentrations of moving objects. Such queries are called dense region queries in spatio-temporal databases, and desire regions in which the density of moving objects exceeds a given threshold. Current methods for addressing this important class of queries suffer from several drawbacks. For example, they may fail to find all dense regions, provide ambiguous answers, impose restrictions on size, or lack a notion of local density. We address these issues in this paper, starting with a new definition of dense regions. We show that we are able to answer dense region queries completely and uniquely using this definition. Dense regions in our approach may have arbitrary shape and size, as well as local density guarantees. We present two methods, the first, an exact method, and the second, an approximate method. We demonstrate through extensive experiments that our exact method is efficient and is superior to current approaches. Our approximate method runs orders of magnitude faster than our exact method, at the cost of a tolerable loss of accuracy.

Complex queries on trajectory data are increasingly common in applications involving moving objects. MBR or grid-cell approximations on trajectories perform suboptimally since they do not capture the smoothness and lack of internal area of trajectories. We describe a parametric space indexing method for historical trajectory data, approximating a sequence of movement functions with single continuous polynomial. Our approach works well, yielding much finer approximation quality than MBRs. We present the PA-tree, a parametric index that uses this method, and show through extensive experiments that PA-trees have excellent performance for offline and online spatio-temporal range queries. Compared to MVR-trees, PA-trees are an order of magnitude faster to construct and incur I/O cost for spatio-temporal range queries lower by a factor of 2-4. SETI is faster than our method for index construction and timestamp queries, but incurs twice the I/O cost for time interval queries, which are much more expensive and are the bottleneck in online processing. Therefore, the PA-tree is an excellent choice for both offline and online processing of historical trajectories

Abstract — Sensor deployments may be static, but researchers have recently been making a case for mobile collector nodes to enhance data acquisition. Since mobile nodes are often more privileged, their compromise can give the adversary a significant advantage. Hence, security mechanisms for such networks must tolerate mobile node compromises. Unlike static sensors, which communicate mostly with their neighbors, mobile nodes may communicate with nodes all over the network. Hence, key establishment is a much harder challenge with mobile nodes. We first analyze the impact of mobile collector compromises on the reliability of data received by the base station, and the circumstances under which reliability can be guaranteed. Second, we present mGKE, a key predistribution scheme for very general group-based sensor deployments. mGKE allows any pair of neighboring sensors to establish a unique pairwise key, regardless of sensor density or distribution. It is also usable by mobile collectors. Our analysis and evaluation show the superiority of mGKE over current methods in terms of resilience, connectivity, communication overhead, and memory requirements. I.

Location-dependent data are central to many emerging applications, ranging from traffic information services to sensor networks. The standard pull- and push-based data dissemination models become unworkable since the data volumes and number of clients are high.We address this problem using locale covers, a subset of the original set of locations of interest, chosen to include at least one location in a suitably defined neighborhood of any client. Since location-dependent values are highly correlated with location, a query can be answered using a location close to the query point.We show that location-dependent queries may be answered satisfactorily using locale covers, with small loss of accuracy. Our approach is independent of locations and speeds of clients, and is applicable to mobile clients.

We present a group-based key predistribution scheme, GKE, which enables all pairs of neighboring sensors to establish a unique pairwise key, regardless of sensor density or distribution. Since pairwise keys are unique, security in GKE degrades gracefully as the number of compromised nodes increases. In addition, GKE is very efficient since it requires only localized communication to establish pairwise keys, significantly reducing communication overheads. Our security analysis and performance evaluation show that GKE performs very well in terms of resilience, connectivity, communication overhead and memory requirements