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
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.
1906525
A Robust and Secure RFID-Based Pedigree System (Short Paper)
There has been considerable interest recently on developing a system to track items like pharmaceutical drugs or food products. Such a system can help prevent counterfeits, aid product recall, and improve general logistics. In this paper, we present such system based on radio frequency identity (RFID) technology. Our solution provides the means of storing the entire movement of the item from original manufacturer to final consumer on the RFID tag itself, and also makes it more difficult to introduce large numbers of counterfeits. The solution also allows the end user to easily verify the authenticity of the item.
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].
14645772
Three power-aware routing algorithms for sensor networks
Summary This paper discusses online power-aware routing in large wireless ad hoc networks (especially sensor networks) for applications in which 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. Finally, we describe a distributed version of this algorithm that does not depend on any centralization. Copyright  2003 John Wiley & Sons, Ltd.
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.
17714396
Reliability Analysis of the Retrial Queue with Server Breakdowns and Repairs
Retrial queues have been widely used to model many problems arising in telephone switching systems, telecommunication networks, computer networks and computer systems, etc. It is of basic importance to study reliability of retrial queues with server breakdowns and repairs because of limited ability of repairs and heavy influence of the breakdowns on the performance measure of the system. However, so far the repairable retrial queues are analyzed only by queueing theory. In this paper we give a detailed analysis for reliability of retrial queues. By using the supplementary variables method, we obtain the explicit expressions of some main reliability indexes such as the availability, failure frequency and reliability function of the server. In addition, some special queues, for instance, the repairable M/G/1 queue and repairable retrial queue can be derived from our results. These results may be generalized to the repairable multi-server retrial models.
1550828
Two-Dimensional Linear Discriminant Analysis
Linear Discriminant Analysis (LDA) is a well-known scheme for feature extraction and dimension reduction. It has been used widely in many applications involving high-dimensional data, such as face recognition and image retrieval. An intrinsic limitation of classical LDA is the so-called singularity problem, that is, it fails when all scatter matrices are singular. A well-known approach to deal with the singularity problem is to apply an intermediate dimension reduction stage using Principal Component Analysis (PCA) before LDA. The algorithm, called PCA+LDA, is used widely in face recognition. However, PCA+LDA has high costs in time and space, due to the need for an eigen-decomposition involving the scatter matrices. 
 
In this paper, we propose a novel LDA algorithm, namely 2DLDA, which stands for 2-Dimensional Linear Discriminant Analysis. 2DLDA overcomes the singularity problem implicitly, while achieving efficiency. The key difference between 2DLDA and classical LDA lies in the model for data representation. Classical LDA works with vectorized representations of data, while the 2DLDA algorithm works with data in matrix representation. To further reduce the dimension by 2DLDA, the combination of 2DLDA and classical LDA, namely 2DLDA+LDA, is studied, where LDA is preceded by 2DLDA. The proposed algorithms are applied on face recognition and compared with PCA+LDA. Experiments show that 2DLDA and 2DLDA+LDA achieve competitive recognition accuracy, while being much more efficient.
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.
3013042
Feature extraction via generalized uncorrelated linear discriminant analysis
Feature extraction is important in many applications, such as text and image retrieval, because of high dimensionality. Uncorrelated Linear Discriminant Analysis (ULDA) was recently proposed for feature extraction. The extracted features via ULDA were shown to be statistically uncorrelated, which is desirable for many applications. In this paper, we will first propose the ULDA/QR algorithm to simplify the previous implementation of ULDA. Then we propose the ULDA/GSVD algorithm, based on a novel optimization criterion, to address the singularity problem. It is applicable for undersampled problem, where the data dimension is much larger than the data size, such as text and image retrieval. The novel criterion used in ULDA/GSVD is the perturbed version of the one from ULDA/QR, while surprisingly, the solution to ULDA/GSVD is shown to be independent of the amount of perturbation applied. We did extensive experiments on text and face image data to show the effectiveness of ULDA/GSVD and compare with other popular feature extraction algorithms.