741471
Communication in disconnected ad hoc networks using message relay
An ad hoc network is formed by a group of mobile hosts upon a wireless network interface. Previous research in communication in ad hoc networks has concentrated on routing algorithms which are designed for fully connected networks. The traditional approach to communication in a disconnected ad hoc network is to let the mobile computer wait for network reconnection passively. This method may lead to unacceptable transmission delays. We propose an approach that guarantees message transmission in minimal time. In this approach, mobile hosts actively modify their trajectories to transmit messages. We develop algorithms that minimize the trajectory modifications under two different assumptions: (a) the movements of all the nodes in the system are known and (b) the movements of the hosts in the system are not known.
1740828
Design and Analysis of Sensing Scheduling Algorithms under Partial Coverage for Object Detection in Sensor Networks
Object detection quality and network lifetime are two conflicting aspects of a sensor network, but both are critical to many sensor applications such as military surveillance. Partial coverage, where a sensing field is partially sensed by active sensors at any time, is an appropriate approach to balancing the two conflicting design requirements of monitoring applications. Under partial coverage, we develop an analytical framework for object detection in sensor networks, and mathematically analyze average-case object detection quality in random and synchronized sensing scheduling protocols. Our analytical framework facilitates performance evaluation of a sensing schedule, network deployment, and sensing scheduling protocol design. Furthermore, we propose three wave sensing scheduling protocols to achieve bounded worst-case object detection quality. We justify the correctness of our analyses through rigorous proof, and validate the effectiveness of the proposed protocols through extensive simulation experiments
8816096
Distributed User Access Control in Sensor Networks
User access control in sensor networks defines a process of granting user the access right to the information and resources. It is essential for the future real sensor network deployment in which sensors may provide users with different services in terms of data and resource access. A centralized access control mechanism requires base station to be involved whenever a user requests to get authenticated and access the information stored in the sensor node, which is inefficient, not scalable, and is exposed to many potential attacks along the long communication path. In this paper, we propose a distributed user access control under a realistic adversary model in which sensors can be compromised and user may collude. We split the access control into local authentication conducted by the sensors physically close to the user, and a light remote authentication based on the endorsement of the local sensors. Elliptic Curve Cryptography (ECC), a public key cryptography scheme, is used for local authentication. We implement the access control protocols on a testbed of TelosB motes. Our analysis and experimental results show that our scheme is feasible for real access control requirement.
10818971
Efficient Implementation of Public Key Cryptosystems on Mote Sensors (Short Paper)
We report our implementation of the RSA and ECC public-key cryptosystem on Berkeley Motes. We detail the implementation of 1024-bit RSA and 160-bit ECC cryptosystems on MICA mote sensors. We have achieved the performance of 0.79s for RSA public key operation and 21.5s for private operation, and 1.3s for ECC signature generation and 2.8s for verification. For comparison, we also show our new ECC implementation on TelosB motes with a signature time 1.60s and a verification time 3.30s. For the detailed description of the implementation, we refer to our technical report [13].
17699208
A study on object tracking quality under probabilistic coverage in sensor networks
Sensor networks are used for a wide range of object tracking applications, such as vehicle tracking in military surveillance and wild animal tracking in habitat monitoring [1]. These applications, by their nature, enforce certain tracking quality and lifetime requirements. These two requirements, however, are two conflicting optimization goals due to the stringent energy constraints of sensor nodes.
1284934
Online power-aware routing in wireless Ad-hoc networks
This paper discusses online power-aware routing in large wireless ad-hoc networks for applications where the message sequence is not known. We seek to optimize the lifetime of the network. We show that online power-aware routing does not have a constant competitive ratio to the off-line optimal algorithm. We develop an approximation algorithm called max-min zPmin that has a good empirical competitive ratio. To ensure scalability, we introduce a second online algorithm for power-aware routing. This hierarchical algorithm is called zone-based routing. Our experiments show that its performance is quite good.
3052468
Performance Modeling and Analysis for Resource Scheduling in Data Grids
Data Grids normally deal with large data-intensive problems on geographically distributed resources; yet, most current research on performance evaluation of resource scheduling in Data Grids is based on simulation techniques, which can only consider a limited range of scenarios. In this paper, we propose a formal framework via Stochastic Petri Nets to deal with this problem. Within this framework, we model and analyze the performance of resource scheduling in Data Grids, allowing for a wide variety of job and data scheduling algorithms. As a result of our research, we can investigate more scenarios with multiple input parameters. Moreover, we can evaluate the combined effectiveness of job and data scheduling algorithms, rather than study them separately.
62165038
IDR/QR: An Incremental Dimension Reduction Algorithm via QR Decomposition
Dimension reduction is a critical data preprocessing step for many database and data mining applications, such as efficient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction algorithm is linear discriminant analysis (LDA). The common aspect of previously proposed LDA-based algorithms is the use of singular value decomposition (SVD). Due to the difficulty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there has been little work on designing incremental LDA algorithms that can efficiently incorporate new data items as they become available. In this paper, we propose an LDA-based incremental dimension reduction algorithm, called IDR/QR, which applies QR decomposition rather than SVD. Unlike other LDA-based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying efficient QR-updating techniques. Finally, we evaluate the effectiveness of the IDR/QR algorithm in terms of classification error rate on the reduced dimensional space. Our experiments on several real-world data sets reveal that the classification error rate achieved by the IDR/QR algorithm is very close to the best possible one achieved by other LDA-based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are inserted dynamically.
5061697
XISS/R: XML Indexing and Storage System using RDBMS
We demonstrate the XISS/R system, an implementation of the XML Indexing and Storage System (XISS) on top of a relational database. The system is based on the XISS extended preorder numbering scheme, which captures the nesting structure of XML data and provides the opportunity for storage and query processing independent of the particular structure of the data. The system includes a web-based user interface, which enables stored documents to be queried via XPath. The user interface utilizes the XPath Query Engine, which automatically translates XPath queries into efficient SQL statements.
2653165
Skyline index for time series data
We have developed a new indexing strategy that helps overcome the curse of dimensionality for time series data. Our proposed approach, called skyline index, adopts new skyline bounding regions (SBR) to approximate and represent a group of time series data according to their collective shape. Skyline bounding regions allow us to define a distance function that tightly lower bounds the distance between a query and a group of time series data. In an extensive performance study, we investigate the impact of different distance functions by various dimensionality reduction and indexing techniques on the performance of similarity search, including index pages accessed, data objects fetched, and overall query processing time. In addition, we show that, for k-nearest neighbor queries, the proposed skyline index approach can be coupled with the state of the art dimensionality reduction techniques such as adaptive piecewise constant approximation (APCA) and improve its performance by up to a factor of 3.
17702470
A framework of individually-focused teleconferencing (IFT) via an efficient 3D reprojection technique
In this paper, we propose a framework on individually-focused teleconferencing (IFT) which is supported by an efficient 3D reprojection technique. The goal of designing IFT is to provide sufficient 3D pose information to each teleconference participant in order to establish lively communication in a teleconference on low-bandwidth internet. A novel IFT deployment and an efficient 3D reprojection technique are two major contributions of this paper. Our 3D reprojection technique uses a mirror reference view in three-view epipolar geometry. It overcomes the inefficiency in previous techniques and provides visually good recovery of pose information of teleconference participants even though it is theoretically an approximation scheme.