Point cloud classification, crucial for discriminative 3D shape analysis, has witnessed significant progress through the application of deep learning. A significant research focus has been on aggregating local point cloud features. A key limitation of previous methods lies in their inherent opacity, making it challenging to understand the underlying reasons for their predictions. Furthermore, these methods frequently exhibit poor generalization performance, struggling to maintain their efficacy when applied to data that deviates from their training distribution. Our method aims to tackle these challenges. We propose ICP-Classifier, a neural-network-free and training-free paradigm that uses Iterative Closest Point (ICP) for classification, which is simple yet robust. The inherent transparency of our method allows for straightforward interpretation of its predictions and underlying mechanisms. By comparing test samples with a reference library, ICP-Classifier predicts labels based on overlap ratios, showing strong generalization on out-of-distribution datasets and robustness facing perturbed data. While capable of achieving high accuracy, our work is exploratory in nature, aiming to explore potential solutions for existing challenges. In contrast to the current focus on complex local feature aggregation, our findings suggest that the inherent shape of 3D objects holds significant discriminative potential, opening up new avenues for exploring robust methods and deepening our understanding of 3D shape analysis.

Neural Radiance Fields (NeRF) have shown significant potential in encoding complex 3D geometries and visual properties, making them a promising alternative to traditional dense SLAM systems. We propose Proud-SLAM, a dense SLAM framework that merges a neural point-based hybrid scene representation. Our key innovation is the HPoint method, which integrates color features into the point cloud, preserving real-world fidelity and enhancing scene rendering. Additionally, we design a hashV structure to efficiently manage and expand point clouds incrementally. Experiments on Replica and Scan-Net datasets demonstrate that Proud-SLAM excels in tracking precision, reconstruction accuracy, and scene rendering quality.

We introduce NeuV-SLAM, a novel dense simultaneous localization and mapping pipeline based on neural multiresolution voxels, characterized by ultra-fast convergence and incremental expansion capabilities. This pipeline utilizes RGBD images as input to construct multiresolution neural voxels, achieving rapid convergence while maintaining robust incremental scene reconstruction and camera tracking. Central to our methodology is to propose a novel implicit representation, termedVDFthat combines the implementation of neural signed distance field (SDF) voxels with an SDF activation strategy. This approach entails the direct optimization of color features and SDF values anchored within the voxels, substantially enhancing the rate of scene convergence. To ensure the acquisition of clear edge delineation, SDF activation is designed, which maintains exemplary scene representation fidelity even under constraints of voxel resolution. Furthermore, in pursuit of advancing rapid incremental expansion with low computational overhead, we developedhashMV, a novel hash-based multiresolution voxel management structure. This architecture is complemented by a strategically designed voxel generation technique that synergizes with a two-dimensional scene prior. Our empirical evaluations, conducted on the Replica and ScanNet Datasets, substantiate NeuV-SLAM's exceptional efficacy in terms of convergence speed, tracking accuracy, scene reconstruction, and rendering quality.

With 52.8 billion RFID tags used worldwide in 2024, a common basic functionality needed by RFID-enabled applications is cardinality estimation — to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator — the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is$4.2\times $faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

Recent advancements in neural rendering methods, such as Neural Radiance Fields (NeRF) and 3D Gaussian Splatting (3D-GS), have significantly revolutionized photo-realistic novel view synthesis of scenes with multiple photos or videos as input. However, existing approaches within the NeRF and 3D-GS frameworks often assume the independence of point sampling and ray casting, which are intrinsic to volume rendering and alpha-blending techniques. These underlying assumptions limit the ability to aggregate context within subspaces, such as densities and colors in the radiance fields and pixels on the image plane, leading to synthesized images that lack fine details and smoothness. To overcome this, we propose a universal framework, MixRF, comprising a Radiance Field Mixer (RF-mixer) and a Color Domain Mixer (CD-mixer), to sufficiently aggregate and fully explore information in neighboring sampled points and casting rays, separately. The RF-mixer treats sampled points as an explicit point cloud, enabling the aggregation of density and color attributes from neighboring points to better capture local geometry and appearance. Meanwhile, the CD-mixer rearranges rendered pixels on the sub-image plane, improving smoothness and recovering fine details and textures. Both mixers employ a kernel-based mixing strategy to facilitate effective and controllable attribute aggregation, ensuring a more comprehensive exploration of radiance values and pixel information. Extensive experiments demonstrate that our MixRF framework is compatible with radiance field-based methods, including NeRF and 3D-GS designs. The proposed framework dramatically enhances performance in both qualitative and quantitative evaluations, with less than a $ 25\%$25% increase in computational overhead during inference.

Accurate pose estimation over SE(3) is fundamentally crucial for numerous perception tasks, including camera re-localization. While existing learning-based methods estimated from a series of RGB images have significantly improved the accuracy of pose, the majority of models still face one or two limitations. First, few representations on SE(3) are smooth and differential, making them difficult to apply in deep learning frameworks. Second, they often require high computational resources due to complex deep network designs. We in this paper propose the DL-PoseNet to address these issues. Specifically, we present a novel representation for SE(3) which follows the property of smoothness of the pose. We then design a lightweight neural network to regress the pose by developing a differential pose layer. Finally, we introduce a novel loss function and gradient descent method to better supervise the proposed lightweight pose network. Extensive experiments on the camera re-localization task on the Cambridge Landmarks and 7-Scenes datasets demonstrate the superior predictive accuracy and benefits of our method in comparison with the state-of-the-art.

A boundary is a physical or virtual line that marks the edge or limit of a specific region, which has been widely used in many applications, such as autonomous driving, virtual wall, and robotic lawn mowers. However, none of existing work can well balance the cost, the deployability, and the scalability of a boundary. In this paper, we propose a new RFID-based boundary scheme together with its detection algorithm called RF-Boundary, which has the competitive advantages of being battery-free, low-cost, and easy-to-maintain. We develop two technologies of phase gradient and dual-antenna DoA to address the key challenges posed by RF-boundary, in terms of lack of calibration information and multi-edge interference. We implement a prototype of RF-Boundary with commercial RFID systems and a mobile robot. Extensive experiments verify the feasibility as well as the good performance of RF-Boundary.

Weak-signal detection underlies a variety of ubiquitous computing applications, such as wireless sensing and machinery fault diagnosis. Stochastic resonance (SR) provides a new way for weak-signal detection by boosting undetectable signals with added white noise. However, existing work has to take a long time to search optimal parameter settings for SR, which cannot fit well some time-critical applications. In this paper, we propose an adaptive SR scheme (ASR) that can amplify the original signal at a low cost in time. The basic idea is that we find that the potential parameter is a key factor that determines the performance of SR. By treating the system as a feedback loop, we can dynamically adjust the potential parameters according to the output signals and make SR happen adaptively. ASR answered two technical questions: how can we evaluate the output signal and how can we tune the potential parameters quickly towards the optimal. In ASR, we first design a spectral-analysis based solution to examine whether SR happens using continuous wavelet transform. After that, we reduce the parameter tuning problem to a constrained non-linear optimization problem and use the sequential quadratic programming to iteratively optimize the potential parameters. We implement ASR and apply it in two ubiquitous computing applications: respiration-rate detection and machinery fault diagnosis. Extensive experiments show that ASR outperforms the state-of-the-art.

In recent years, Neural Radiation Fields (NeRF) have shown tremendous potential in encoding highly-detailed 3D geometry and environmental appearance, thus making it a promising alternative to traditional explicit maps for robot localization. However, current NeRF localization methods suffer from significant computational overheads, primarily resulting from the large number of iterations or particle samples required, as well as the additional computational demands associated with the estimation of the initial pose through multimodal sensors. To overcome these challenges, we propose a novel and time-efficient NeRF localization pipeline, named FVLoc-NeRF. This pipeline solely employs RGB monocular images as input and leverages a retrieval method to obtain the initial pose. Subsequently, the pose update is derived using the Perspective-n-Point (PnP) algorithm, thereby considerably reducing the number of iterations and accelerating the localization process. Our extensive experimental results clearly demonstrate that FVLoc-NeRF is much faster than the state-of-the-art method.

With 30 billion RFID tags sold worldwide in 2021, a common basic functionality needed by RFID-enabled applications is cardinality estimation --- to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator --- the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is 4.2× faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

Abstract Orientation estimation is one of the core problems in several computer vision tasks. Recently deep learning techniques combined with the Bingham distribution have attracted considerable interest towards this problem when considering ambiguities and rotational symmetries of objects. However, existing works suffer from two issues. First, the computational overhead for calculating the normalisation constant of the Bingham distribution is relatively high. Second, the choice of loss functions is uncertain. In light of these problems, we present an online deep Bingham network to estimate the orientation of objects. We sharply reduce the computational overhead of the normalisation constant by directly applying a numerical integration formula. Additionally, we are the first to give theorems on the convexity and Lipschitz continuity of the Bingham distribution's negative log‐likelihood, which formally indicates that it is a proper choice of the loss function. We test our method on three public datasets, namely the UPNA, the T‐LESS and Pascal3D+, showing that our method outperforms the state‐of‐the‐art in terms of orientation accuracy and time efficiency, which can reduce the runtime by more than 6 h compared to the offline methods. The ablation experiments further demonstrate the effectiveness and robustness of our model.

In this paper, we study the problem of jointly estimating the optical flow and scene flow from synchronized 2D and 3D data. Previous methods either employ a complex pipeline that splits the joint task into independent stages, or fuse 2D and 3D information in an “early-fusion“ or “late-fusion“ manner. Such one-size-fits-all approaches suffer from a dilemma of failing to fully utilize the characteristic of each modality or to maximize the inter-modality complementarity. To address the problem, we propose a novel end-to-end framework, called CamLiFlow. It consists of 2D and 3D branches with multiple bidirectional connections between them in specific layers. Different from previous work, we apply a point-based 3D branch to better extract the geometric features and design a symmetric learnable operator to fuse dense image features and sparse point features. Experiments show that CamLiFlow achieves better performance with fewer parameters. Our method ranks 1st on the KITTI Scene Flow benchmark, outperforming the previous art with 1/7 parameters. Code is available at https://github.com/MCG-NJU/CamLiFlow.

Fast and accurate pose estimation is essential for many robotic applications such as SLAM, manipulation, and 3D point registration. Existing solutions to this problem suffer from either high computation overhead due to the nonlinear features or accuracy loss due to linear approximation. In this paper, we propose a dual quaternion feedback particle filter (DQFPF) that can capture the nonlinear factors in the observation model and use the optimal control theory to estimate the pose. To avoid particle degeneracy caused by sequential importance sampling and resampling, we present a feedback particle update formula to speed up the optimization with fewer particles being sampled. Simulation results show that in known corresponding cases our approach can converge to the correct pose more efficiently than the state-of-the-art. A similar conclusion can also be drawn in real applications of unknown corresponding cases, i.e., point cloud stitching and visual odometry estimation.

RFID technologies have been widely used for item-level object monitoring and tracking in industrial applications. In this paper, we study the problem of range detection in a commodity RFID system, which aims to quickly figure out whether there are any target tags that hold specific data between a lower and upper boundary. This is important to help users pinpoint tagged objects of interest (if any) and give an early warning for reducing the potential risk, e.g., temperature monitoring for fire safety. We propose a time-efficient protocol called encoding range query (EnRQ). The basic idea is to use a sparse vector to separate target tags from the others with a few select commands. The sparse vector is specifically designed by encoding the tag’s data based on notational systems. We implement EnRQ in commodity RFID systems with no need for any hardware modifications. Extensive experiments show that EnRQ can improve the time efficiency by more than 40% on average, compared with the state-of-the-art.

Radio frequency identification (RFID) based localization has attracted increasing attentions due to competitive advantages of RFID tags: unique identification, low-cost, and battery-free. Although many advanced phase-based localization methods are proposed, few of them take fully the unknown phase center (PC) and the phase offset (PO) into account, which however are the key factors in fine-grained localization. In this paper, we propose a novel localization algorithm called Segment Aligned Hologram (SAH) that jointly calibrates the PC and the PO. SAH first builds a phase matrix and then designs a phase alignment algorithm based on the phase matrix for reducing the multi-path effect. Afterwards, SAH constructs a hologram for calibration and localization, which greatly reduces the system errors. We implement SAH through commercial RFID devices. Extensive experiments show that SAH can achieve a fine-grained localization accuracy in both the lateral and the radial directions with only a single antenna.

Accurate absolute pose regression is one of the key challenges in robotics and computer vision. Existing direct regression methods suffer from two limitations. First, some noisy scenarios such as poor illumination conditions are likely to result in the uncertainty of pose estimation. Second, the output n-dimensional feature vector in the Euclidean space $\mathbb{R}^n$ cannot be well mapped to $SE(3)$ manifold. In this work, we propose a deep dual quaternion network that performs the absolute pose regression on $SE(3)$. We first develop an antipodally symmetric probability distribution over the unit dual quaternion on $SE(3)$ to model uncertainties and then propose an intermediary differential representation space to replace the final output pose, which avoids the mapping problem from $\mathbb{R}^n$ to $SE(3)$. In addition, we introduce a backpropagation method that considers the continuousness and differentiability of the proposed intermediary space. Extensive experiments on the camera re-localization task on the Cambridge Landmarks and 7-Scenes datasets demonstrate that our method greatly improves the accuracy of the pose as well as the robustness in dealing with uncertainty and ambiguity, compared to the state-of-the-art.

In RFID systems, the privacy problem has attracted increasing attention as the tags have extremely limited on-chip resources and may blindly respond to unauthorized readers. One widely used solution is to deploy one or more blocker tags to collide the RF signal sent from protected tags all the time. We in this paper investigate tag identification in privacy-sensitive RFID systems when we have the authorized reader(s). The tag identification under the blocker environment becomes more challenging since the protected tags and blocker tags will always respond concurrently, leading to unreconciled collisions. Therefore, we propose three tag identification protocols IIP, SIP and SUIP, which meet three application requirements: privacy, accuracy, and efficiency. IIP iteratively deactivates blocking tags as well as labeling genuine tags, and finally identifies tags by avoiding all the unreconciled collisions. SIP further avoids the slot waste by carrying out a filter to separate genuine tags from others in advance. Furthermore, SUIP separates the incremental unknown tags from others by using a filter with improved performance and proposes a collision reconciliation technique to accelerate the identification process. Simulation results demonstrate that our protocols are able to guarantee any identification accuracy in a privacy-protected way.

RFID is becoming ubiquitously available in our daily life. After RFID tags are deployed to make attached objects identifiable, a natural next step is to communicate with the tags and collect their information for the purpose of tracking tagged objects or monitoring their surroundings in real-time. In this paper, we study an under-investigated problem range detection in a commodity RFID system, which aims to check if there are any tags with the data between an upper and lower boundary in a time-efficient way. This is important especially in a large RFID system, which can help users quickly pinpoint the target tags (if any) and give an early warning to users for taking urgent actions and reducing the potential risk in the nascent stage. We propose two tailored protocols, selective query and range query, to achieve range detection within the scope of the C1G2 standard. The novelty is that, instead of querying each tag, we exploit the capability of C1G2-compatible selection and quickly separate target tags from others by silencing most of tags. The final result is that range query is able to achieve a range detection with only one query command. We implement the proposed protocols in commodity RFID systems, with no need for any hardware modifications. Extensive experiments show that range query is able to improve the time efficiency by an order of magnitude, compared with the baseline.

Temperature sensing plays a significant role in upholding quality assurance and meeting regulatory compliance in a wide variety of applications, such as fire safety and cold chain monitoring. However, existing temperature measurement devices are bulky, cost-prohibitive, or battery-powered, making item-level sensing and intelligence costly. In this paper, we present a novel tag-based thermometer called Thermotag, which uses a common passive RFID tag to sense the temperature with competitive advantages of being low-cost, battery-free, and robust to environmental conditions. The basic idea of Thermotag is that the resistance of a semiconductor diode in a tag's chip is temperature-sensitive. By measuring the discharging period through the reverse-polarized diode, we can estimate the temperature indirectly. We propose a standards-compliant measurement scheme of the discharging period by using a tag's volatile memory and build a mapping model between the discharging period and temperature for accurate and reliable temperature sensing. We implement Thermotag using a commercial off-the-shelf RFID system, with no need for any firmware or hardware modifications. Extensive experiments show that the temperature measurement has a large span ranging from 0 °C to 85 °C and a mean error of 2.7 °C.

In RFID systems, tag grouping is to inform each tag in the interrogator's RF field which group it belongs to by assigning them a group ID. With this information, the reader can write the same data into a group of tags in one transmission by taking their shared group ID as the destination address, which plays a vital role in improving inventory efficiency. Existing work proposes some efficient protocols but suffers from two defects: slot waste and data redundancy. To address these problems, we in this paper propose a two-phase grouping scheme that improves the grouping efficiency via slot reuse as well as data compression. For slot waste, we try to reconcile collision slots and turn some of them into useful again by re-assigning a new slot to collision tags, which increases the number of useful slots and reduces slot waste. For data redundancy, we encode group IDs with lossless coding algorithms and reduce the data redundancy caused by repetitive transmission of group IDs. Two coding methods,Huffman codingandarithmetic coding, are adopted to shorten the length of the bit vector comprised by group IDs. Theoretical analyses and extensive simulations show that our best protocol improves the time efficiency by 51.9 percent compared with the state-of-the-art.

RFID is becoming ubiquitously available in our daily life. After RFID tags are deployed to make attached objects identifiable, a natural next step is to communicate with the tags and collect their information for the purpose of tracking tagged objects or monitoring their surroundings in real time. In this paper, we study an under-investigated problem range detection in a commodity RFID system, which aims to check if there are any tags with the data between an upper and lower boundary in a time-efficient way. This is important especially in a large RFID system, which can help users quickly pinpoint the target tags (if any) and give an early warning to users for taking urgent actions and reducing the potential risk in the nascent stage. We propose two tailored protocols, selective query and range query (RQ), to achieve range detection within the scope of the C1G2 standard. The novelty is that, instead of querying each tag, we exploit the capability of C1G2-compatible selection and quickly separate target tags from others by silencing most of tags. The final result is that our best protocol RQ is able to achieve a range detection with only one query command. We implement the proposed protocols in commodity RFID systems, without any modifications of hardware. Extensive experiments show that RQ is able to improve the time efficiency by near 30×, compared with the baseline.

Shelf scanning is one of the most important processes for inventory management in a library, which is able to help library users find the misplaced books and pinpoint where they are. Traditional solutions suffer from intensive manual labor, long scanning delay, or high-cost infrastructure renewal, which is a great barrier to commercial adoption. In this paper, we propose an HF RFID system that can perform the shelf scanning automatically by combining robotics and RFID technology, where the mobile robot is used for replacing the library staff and the RFID is for locating the tagged books on the bookshelves. The biggest challenge is that the commodity HF RFID device cannot capture RF phase, which is a fine-grained metric with high resolution for locating. To address this problem, we break down the task of localization into two stages, tier-level localization and order estimation, and use fuzzy logic to model and estimate the tagged book’s position. We implement the system and deploy it into four libraries for practical use. Long-term extensive experimental results demonstrate that our system provides a finegrained book localization with an accuracy of a few centimeters.

Determining an object’s spatial pose (including orientation and position) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained pose sensing system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object’s pose by determining the spatial orientation and position of the tag. We exploit thepolarizationproperties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader’s antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag’s pose through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of Tag-Compass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate estimate of object orientation with a median error of just 2.5° when the tag’s position is known and a median error of 3.8° when the tag’s position is unknown. In the latter case, Tag-Compass will provide an estimate of tag position as a byproduct of orientation sensing, with an accuracy comparable to the state of the art. It is practically appealing to find both the orientation and the position of an object using a single method, instead of having to deploy two different methods.

Radio Frequency IDentification (RFID) technology has been widely used in missing tag identification to reduce the economic loss caused by theft. Although many advanced works have been proposed, they cannot work properly in an open RFID system with unexpected tags. That is because the unexpected tags may reply to the reader when it is the missing tags’ turn, such that the replies are mistakenly treated as the missing tags’, leading to failure to detect the missing tags. To solve the problem, this article proposes an order-based missing tag identification protocol (OMTI) that efficiently identifies all missing tags even with the presence of unexpected tags. The key of OMTI is that we dynamically assign each tag an exclusive slot rather than use random hashes in traditional design. Namely, OMTI off-line serializes all known tags in advance by assigning each of them a unique and continuous slot, on-line identifies missing tags by checking tags’ responses in each slot, and dynamically updates the slot assignment to ensure the high efficiency of the next execution. Besides, we enhance OMTI to make it embrace newly added tags and spread to the multi-reader case from the single one. The simulation results demonstrate that OMTI can significantly reduce the identification time compared to the state-of-the-art.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems, in terms of energy cost and execution time. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistant communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that the system-level applications through CCM are able to reduce the energy cost and execution time by one order of magnitude, compared with the ID-collection based solution.

Misshelving is an age-old problem in a library. If this happens, users can hardly find their wanted books, leading to a waste of book resources. In this paper, we investigate the problem of book localization through mobile RFID scanning. According to extensive experiments, we find that the phase data (that are used to do localization) beyond the reader antenna's main lobe are noisy; taking these data as the input of book localization is likely to lower the localization accuracy. However, it is not easy to figure out which data are noisy. To address this problem, we propose a fine-grained localization method called FILM, which can achieve cm-level book localization through the following three steps. First, it collects the phase profile for each tagged book as is. Second, it sophisticatedly chooses three samples from the phase profile and locates the tagged book by modeling the three samples. Since there are a great number of 3-combinations, we can get many candidates of the book localization. Third, it uses the Gaussian kernel density model to determine whether the candidates are good or not. The basic idea is that, the noisy data give rise to uncertain estimates, whereas the clean data will always get an estimate close to the ground truth. Therefore, the position with the highest density is the most likely to be the tag's position. By this means, the noisy data do not contribute to the final estimate, which improves the localization accuracy. We setup a prototype of FILM and experiment results show that FILM is superior to the state-of-the-art, with a small localization error of 1.3cm.

Sleep monitoring plays an important role in many medical applications, including SIDS prevention, care of patients with pressure ulcers, and assistance to patients with sleep apnea, where studies have shown that autonomous and continuous monitoring of sleep postures provides useful information for lowering health risk. Existing systems are designed based on electrocardiogram, cameras and pressure sensors, which are expensive to deploy, intrusive to privacy, or uncomfortable to use. This paper presents TagSheet, the first sleep monitoring system based on passive RFID tags, which provides a convenient, non-intrusive, and comfortable way of monitoring the sleeping postures. It does not require attaching any tag directly to a patient’s body. Tags are taped under a bed sheet. With a combination of hierarchical recognition, image processing and polynomial fitting, the proposed system identifies body postures based on the observed variation caused by the patient body to the backscattered signals from tags. The system does not require any personalized data training, making it plug-n-play in use. One additional advantage is that the system can also estimate the patient’s respiration rate. This is particularly helpful in assisting patients with sleep apnea. We have implemented a prototype system, and experiments show that the system performs posture identification with an accuracy up to 96.7% and in the meantime it measures the respiration rate with a small error of about 0.7 bpm (breath per minute).

High write throughput plays a vital role in improving the time efficiency of RFID-enabled applications, such as password update and over-the-air programming. In this paper, we make a fresh attempt to study the under-investigated problem of group write and discuss how to improve the write throughput in the commodity RFID system. By conducting extensive experiments, we reveal that the select operation specified by the C1G2 standard takes up the large overhead of a write cycle, which is the key factor in determining the write efficiency. Based on this finding, we propose an efficient write bundling (WB) scheme that bundles multiple writes up and executes them together in a burst mode, which greatly reduces the number of selects and thereby amplifies the write throughput. In WB, a carefully designed bit vector is assigned to each tag for connecting multiple tags into a run, such that a single select command is able to pick these tags concurrently. Besides, WB integrates multiple select commands into one by running a series of logic operations on the inventoried flags, which are used to indicate whether or not a tag is active. We implement WB in a commodity RFID system, with no need of any software modifications or hardware argument. Extensive experiment results show that WB is able to reduce the number of selects by 87.5% and produce a $2\times$ write amplification, compared with the C1G2-compatible exclusive write.

In RFID-enabled applications, when a tag is put into use and associated with a specific object, the category-related information (e.g., the brands of clothes) about this object might be preloaded into the tag’s memory for the purpose of live query. Since such information reflects category attributes, all tags in the same category carry identical category information. To collect this information, we do not need to repeatedly interrogate each tag; one tag’s response in a category is sufficient. In this paper, we investigate the problem of category information collection in a multi-category RFID system, which is referred to asinformation sampling. We propose two time-efficiency protocols. The first is a two-phase sampling protocol (TPS) that works in the case of knowing tag IDs. By quickly zooming into a category and isolating a tag from this category, TPS is able to sample a category with small overhead. The second protocol, called back-and-forth sampling protocol (BFS), relaxes a key assumption in TPS and performs the sampling task efficiently without knowing any tag IDs or category IDs. By carrying out a step-forward frame and using the step-backward scheme, BFS is able to interrogate only 1.45 tags (close to the lower bound of one tag) on average for each category. We theoretically analyze the protocol performance of TPS and BFS and discuss the optimal parameter settings that minimize the overall execution time. Extensive simulations show that both the protocols outperform the benchmark, greatly improving the sampling performance.

RFID tags have been widely deployed to report valuable information about tagged objects or surrounding environment. To collect such information, the key is to avoid the tag-to-tag collision in the open wireless channel. Polling, as a widely used anti-collision protocol, provides a request-response way to interrogate tags. The basic polling however needs to broadcast the tedious tag ID (96 bits) to query a tag, which is time-consuming. For example, collecting only 1-bit information (e.g., battery status) but with 96-bit overhead is a great limitation. This paper studies how to design efficient polling protocols to collect tag information quickly. The basic idea is to minimize the length of the polling vector as well as to avoid useless communication. We first propose an efficient Hash polling protocol (HPP) that uses hash indices rather than tag IDs as the polling vector to query each tag. The length of the polling vector is dropped from 96 bits to no more than 16 bits (the number of tags is less than 100,000). We then propose a tree-based polling protocol (TPP) that avoids redundant transmission in HPP. By constructing a binary polling tree, TPP transmits only different postfix of the neighbor polling vectors; the same prefix is reserved without any retransmission. The result is that the length of the polling vector reduces to only 3.4 bits. Finally, we propose an incremental polling protocol (IPP) that updates the polling vector based on the difference in value between the current polling vector and the previous one. By sorting the indices and dynamically updating them, IPP drops the polling vector to 1.6 bits long, 60 times less than 96-bit IDs. Extensive simulation results show that our best protocol IPP outperforms the state-of-the-art information collection protocol.

In RFID systems, a cloning attack is to fabricate one or more replicas of a genuine tag, so that these replicas behave exactly the same as the genuine tag and fool the reader for getting legal authorization, leading to potential financial loss or reputation damage for the corporations. These replicas are called clone tags. Although many advanced solutions have been proposed to combat cloning attack, they need to either modify the MAC- layer protocols or increase extra hardware resources, which cannot be deployed on commercial off-the-shelf (COTS) RFID devices for practical use. In this paper, we take a fresh attempt to counterattack tag cloning based on COTS RFID devices and the universal C1G2 standard, without any software redesign or hardware augment needed. The basic idea is to use the RF signal profile to characterize each tag. Since these physical-layer data are measured by the reader and susceptible to various environmental factors, they are hard to be estimated by the attackers; let alone be cloned. Even so, we assert that it is challenging to identify clone tags as the signal data from a genuine tag and its clones are all mixed together. Besides, the tag moving has a great impact on the measured RF signals. To overcome these challenges, we propose a clustering-based scheme that detects the cloning attack in the still scene and a chain- based scheme for clone detection in the dynamic scene, respectively. Extensive experiments on COTS RFID devices demonstrate that the detection accuracy of our approaches reaches 99.8% in a still case and 99.3% in a dynamic scene.

The weighted K‐nearest neighbour (WKNN) algorithm is widely applied to fingerprint positioning. However, the node position estimated by the WKNN algorithm is not optimal in a noisy environment. To obtain the optimised node location estimate, the authors propose an optimal WKNN (OWKNN) algorithm for wireless sensor network (WSN) fingerprint localisation in a noisy environment. The proposed OWKNN algorithm is composed of an adaptive Kalman filter (AKF) and a memetic algorithm (MA). First, the AKF is utilised to reduce the measurement noise of the received signal strength indication (RSSI) between the nodes in the WSN. Then, the MA is employed to optimise the calibration point weight for estimating the position of a target node in the WSN according to the filtered RSSI and a calibrated radio map. Finally, an optimal node location estimate is achieved based on the optimised weight. The extensive experimental results reveal that the localisation accuracy of the proposed algorithm is at least ∼50% higher than those of the state‐of‐the‐art fingerprint localisation algorithms regardless of the placement of the target node, number of beacon nodes, and size of the calibration cell.

Radio Frequency Identification (RFID) technology has been widely used in missing tag identification to reduce the economic loss caused by theft. Although many advanced works have been proposed, they cannot work properly in an open RFID system with unexpected tags. To solve the problem, this paper proposes an order-based missing tag identification protocol (OMTI) that efficiently identifies all missing tags even with the presence of unexpected tags. The key of OMTI is that we dynamically assign each tag a slot rather than use random hashes in traditional design. Namely, OMTI off-line sorts all known tags in advance by assigning each of them a unique and continuous slot, on-line identifies missing tags by checking tags' responses in each slot, and dynamically updates the slot assignment to ensure the high efficiency of the next execution. Besides, we enhance OMTI to make it works in the case of newly added tags. The simulation results demonstrate that OMTI can reduce the execution time by a factor of 12, compared with the polling-based approach.

In RFID-enabled applications, when a tag is put into use and associated with a specific object, the category-related information (e.g., the brands of clothes) about this object might be preloaded into the tag's memory as required. Since such information reflects the category attributes, all tags in the same category carry the identical category information. To collect this information, we do not need to repeatedly interrogate each tag; one tag's response in a category is sufficient. In this paper, we investigate the new problem of category information collection in a multi-category RFID system, which is referred to as information sampling. We propose an efficient two-phase sampling protocol (TPS). By quickly zooming into a category and isolating a tag from this category, TPS is able to sample a category by broadcasting only 7.5-bit polling vector (very efficient when compared to the 96-bit tag ID). We theoretically analyze the protocol performance and discuss the optimal parameter settings that minimize the overall execution time. Extensive simulations show that TPS outperforms the benchmark, greatly improving the sampling performance.

Identifying an object's spatial direction (or orientation) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained direction finding system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object's orientation by determining the spatial direction of the tag. We exploit the polarization properties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader's antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag's direction through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of TagCompass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate direction estimates with a median error of just 2.5° when the tag's position is known and a median error of 3.8° when the tag's position is unknown.

Shelf scanning is one of the most important processes for inventory management in a library. It helps the librarians and library users discover the miss-shelved books and pinpoint where they are, improving the quality of service. By traditional means, however, manually checking each bookshelf suffers from extremely intensive labor and long scanning delay. Although some existing RFID-enabled approaches have been proposed, they suffer from either high-cost infrastructure or complicated system deployment, forming a great barrier to commercial adoption. In light of this, we in this paper propose a smart system called RF-Scanner that can perform the shelf scanning automatically by combining the robot technology and the RFID technology. The former is used for replacing the librarians and liberating them from intensively manual labor. The later is installed on the robot and moves with the robot to scan the on-the-shelf books. We formulate two important issues concerned by librarians, the book localization and the lying-down book detection, and give the sophisticated solutions to them. Besides, we implement RF-Scanner and put it into practical use in our school library. Long-term experiments and studies show that RF-Scanner provides fine-grained book localization with a mean error of just 1.3 cm and accurate detection accuracy of lying-down books with a mean error of 6%.

In RFID systems, the privacy problem has attracted increasing attention as the tags have extremely limited on-chip resources and may blindly respond to unauthorized readers. To protect the privacy, one widely used solution is to deploy one or more blocker tags to collide the RF signal sent from protected tags all the time. In this paper, we investigate the problem of tag identification in privacy-sensitive RFID systems when we have the authorized reader(s). Due to the presence of blocker tags, the tag identification becomes more challenging since the protected tags and blocker tags will always respond concurrently, leading to unreconciled collisions. To overcome this challenge, we in this paper propose two efficient tag identification protocols IIP and SIP, which meet three application requirements: privacy, accuracy, and efficiency. IIP iteratively deactivates blocking tags as well as labeling genuine tags, and finally identifies tags by avoiding all the unreconciled collisions. On top of IIP, SIP further avoids the slot waste by carrying out a filter to separate genuine tags from others in advance. Simulation results demonstrate that our protocols are able to guarantee any identification accuracy in a time-efficient and privacy-protected way.

Radio Frequency Identification (RFID) technology brings a revolutionary change in warehouse management by automatically monitoring and tracking products. The grouping problem is to efficiently inform all tags which groups they belong to, such that tags in the same group have the same group ID. With this information, the reader can transmit data through efficient multicast rather than tedious unicast. However in the dynamic RFID system, where the group IDs change frequently, existing works suffer from low time- efficiency. In light of this, this paper proposes the binary grouping (BIG) protocol to improve the grouping performance in the dynamic RFID system. BIG follows three design principles. First, for the to-be-grouped tags, BIG separates them from the entire tag set before grouping, so that the not-to-be-grouped tags will not participate in the following grouping, reducing the running delay. Second, for the update of group ID, BIG flips only the bits of group ID which differ from the previous ones, instead of updating all bits of the group ID, saving the communication overhead. Third, BIG adopts a Huffman coding based grouping scheme, which classifies tags into different groups in an efficient way. The extensive simulations show BIG outperforms the existing promising works.

In our daily life, some sensitive cargos (e.g., refrigerators) are required to keep one right side up. If these items are turned upside down due to incorrect transportation or wrong storage, some unpredictable exception will happen, leading to potential economic loss. In this paper, we propose a lightweight system TagUP that uses RFID to detect the upside-down exception. By dynamically changing the frequency of the electromagnetic wave and comparing the phase difference between two measurements, TagUP is able to achieve the detection accuracy of 98.0% when two tags are placed 60cm apart.

In RFID systems, tags may blindly respond to any readers authorized or not, leading to privacy leakage. A feasible solution to this issue is to deploy blocker tags that emulate and behave like the genuine tags. With the blocker tags, there is always a virtual tag produced by the blocker tag that responds to the reader when the genuine tag to be protected replies, leading to irreconcilable collisions and thus preventing privacy-leakage. In this paper, we take the fresh attempt to study the problem of missing tag identification in blocker- enabled RFID systems. Unlike traditional missing tag identification, the reader in our problem will always get the responses from blocker tags even the genuine tags are lost, which makes the existing solutions unavailable. To address this problem, we propose a Group-based Missing Tag Identification (GMTI) protocol that first uses the grouping technology to divides the entire tag set into three subsets and later separately deals with each of them in different ways. The final result is that GMTI is able to identify any missing tags in a time-efficient, privacy-protected, and complete way.

Fingerprint localisation technology using received signal strength indication (RSSI) has become one of the hot spots in the research field of indoor positioning based on wireless sensor networks (WSNs). Due to the presence of the measurement noise of the RSSI, the weight of the calibration point in the current fingerprint positioning algorithm is not optimised. The authors propose a fingerprint localisation algorithm for noisy WSNs based on an innovative multi‐objective evolutionary model. The proposed algorithm at first employs the Kalman filter to filter the abnormal RSSI value, and then utilises a noise covariance estimator to perceive the noise covariance of the RSSI. Finally, the multi‐objective evolutionary model is used to search for the optimised weight of the calibration point via the filtered RSSI and the perceived noise covariance. That the novel evolutionary model can find the best fingerprint estimate with the optimised weight has been proven theoretically in this work. Extensive experimental results on an off‐the‐shelf WSN testbed show that the authors’ proposed algorithm improves the accuracy of the state‐of‐the‐art fingerprint positioning algorithm by at least 50% regardless of the placement of the target node, the number of beacon nodes, the size of the calibration cell, and the number of nearest neighbours.

Fingerprint localisation technology based on received signal strength indication (RSSI) is an active area of study in wireless sensor network (WSN) research, mainly because it is cheap and easy to implement. However, due to measurement noise and the multipath effect in RSSI, the accuracy of state‐of‐the‐art fingerprint positioning algorithms is diminished. To solve this problem, the authors propose a multi‐channel fingerprint localisation algorithm for WSNs in multipath environments. This algorithm also addresses the issue of existing techniques based on multi‐channel signal strength requiring an accurate initial estimate of target–beacon distance or prior knowledge of the target–reference distance. Their proposed algorithm first uses an adaptive Kalman filter to reduce the noise in RSSI measured in different channels, and then calculates the matched fingerprint according to the weight of different channels. Finally, a memetic algorithm is utilised to generate the optimised estimate of fingerprint and location. Extensive experimental results on an actual WSN testbed show that the proposed algorithm improves the accuracy of the existing fingerprint localisation algorithm by at least 50%, regardless of the placement of target node, the number of beacon nodes, and the number of calibration points.

Radio frequency identification (RFID) is an automatic identification technology that brings a revolutionary change to quickly identify tagged objects from the collected tag IDs. Considering the misplaced and newly added tags, fast identifying such unknown tags is of paramount importance, especially in large-scale RFID systems. Existing solutions can either identify all unknown tags with low time-efficiency, or identify most unknown tags quickly by sacrificing the identification accuracy. Unlike existing work, this paper proposes a protocol that utilizes physical layer (PHY) information to identify the intact unknown tag set with high efficiency. We exploit the physical signals in collision slots to separate unknown tags from known tags, a new technique to speed up the ID collection. Such new technique was verified in an RFID prototype system using the USRP-based reader and WISP tags. We also evaluated our protocol to show the efficiency of leveraging PHY signals to successfully get all unknown tag IDs without wasted known tag ID transmission. Simulation results show that our protocols outperform prior unknown tag identification protocols. For example, given 1000 unknown tags and 10 000 known tags, our best protocol has 56.8% less time to the state-of-the-art protocol when collecting all unknown tag IDs.

Radio Frequency Identification (RFID) brings a revolutionary change in a range of applications by automatically monitoring and tracking products. With the proliferation of RFID-enabled applications, multiple readers are needed for ensuring the full coverage of numerous RFID tags. In this paper, we focus on the tag distribution problem in multi-reader RFID systems. The problem is to fast identify the tag set beneath each reader, which is a fundamental premise of efficient product inventory and management. Only with such tag set information can we localize specific tags in a reader and expedite the tag query information collection. As an RFID system usually contains a large number of tags and multiple readers, the traditional solution to identify tags by individual readers is highly time inefficient. We propose an Inference-Based protocol (IB) that identifies the tag distribution based on information inference rules and the aggregated physical signals to improve operational efficiency. In our protocol, three kinds of inference rules based on internal information reported by a single reader, external information shared by multiple readers, and history information retained by the system are fully exploited to infer tag distribution. With these rules, all readers can cooperatively work together and quickly obtain the tag distribution in the system. We also build a prototype RFID system using the USRP-based reader and WISP programmable tags, and then implement the IB protocol. The experimental results and extended simulations show that IB outperforms the state-of-the-art protocols.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistent communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that system-level applications through CCM outperform those through ID collection.

Polling is a widely used anti-collision protocol that interrogates RFID tags in a request-response way. In conventional polling, the reader needs to broadcast 96-bit tag IDs to separate each tag from others, leading to long interrogation delay. This paper takes the first step to design fast polling protocols by shortening the polling vector. We first propose an efficient Hash Polling Protocol (HPP) that uses hash indices rather than tag IDs as the polling vector to query each tag. The length of the polling vector is dropped from 96 bits to no more than log(n) bits (n is the number of tags). We then enhance HPP (EHPP) to make it not only more efficient but also more steady with respect to the number of tags. To avoid redundant transmissions in both HPP and EHPP, we finally propose a Tree-based Polling Protocol (TPP) that reserves the invariant portion of the polling vector while updates only the discrepancy by constructing and broadcasting a polling tree. Theoretical analysis shows that the average length of the polling vector in TPP levels off at only 3.44, 28 times less than 96-bit tag IDs. We also apply our protocols to collect tag information and simulation results demonstrate that our best protocol TPP outperforms the state-of-the-art information collection protocol.

Radio Frequency Identification (RFID) technology brings a revolutionary change in warehouse management by automatically monitoring and tracking products. For many RFID-enabled applications, fast searching a particular group of products is practically important in a large-scale RFID system. Different from previous searching protocols, we propose a physical layer tag searching (PLAT) protocol, which makes three fundamental improvements. First, PLAT can exactly pinpoint the search result without false positives at a small delay expense. Second, based on the physical layer signals, PLAT can interpret the accurate number of tags replying in a collision slot, speeding up the execution of tag searching. Third, PLAT can take the global view of the accurate replying information from slots to extract each tag identifier, further improving the protocol performance. We also implement a prototype system based on the USRP and WISP platform. Experimental results validate the feasibility of our protocol. The extensive simulations show PLAT produces the performance gain by a factor of above 2 compared with the state-of-the-art works.

The grouping problem in RFID systems is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of$m$tags simultaneously in multicast, which improves the efficiency by$m$times when comparing with unicast. This paper studies this practically important but not yet thoroughly investigated grouping problem in large RFID system. We start with a straightforward solution called the Enhanced Polling Grouping EPG protocol. We then propose a time-efficient Filter Grouping FIG protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping CCG protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. We further enhance CCG to make it perform better with very large groups. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.

In RFID systems, the grouping problem is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on the unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of m tags simultaneously in multicast, which improves the efficiency by m times when comparing with unicast. We study fast grouping protocols in large RFID systems. To the best of our knowledge, it is the first attempt to tackle this practically important yet uninvestigated problem. We start with a straightforward solution called the Enhanced Polling Grouping (EPG) protocol. We then propose a time-efficient FIltering Grouping (FIG) protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping (CCG) protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.

Radio Frequency Identification (RFID) technology brings a revolutionary change in warehouse management by automatically monitoring and tracking. Considering the misplaced and newly added tags, fast identifying such unknown tags is of paramount importance, especially in large-scale RFID systems. Unlike existing work, this paper proposes a fast Physical-layer Unknown Tag Identification (PUTI) protocol that gathers intact unknown tag set with high identification efficiency. PUTI utilizes physical layer aggregated signals to separate all unknown tags from known tags and then collects IDs from only the entire unknown tag set. We also optimize the parameter setting and analyze protocol performance in theory. Simulation results show that PUTI outperforms prior unknown tag identification protocols. For example, given a RFID system with 1,000 unknown tags and 10,000 known tags, PUTI represents reduction of 37.7% when compared with the state-of-the-art protocol.

Radio Frequency Identification (RFID) has dramatically streamlined supply chain management by automatically monitoring and tracking commodities. Considering the proliferation of RFID data volume, distributed storage is more applicable and scalable than centralized storage for distributed query processing. Traditional distributed RFID data storage requires each distribution center to locally store raw RFID data, leading to data redundancy, storage and query inefficiency. In this paper, we design an efficient distributed storage model by leveraging Bloom filters to save storage space and improve query efficiency. Meanwhile, we establish corresponding query processing schemes to locally support existence queries and path queries, which are two kinds of most popular queries in the supply chain management. A local query can be completed with constant time complexity regardless of data volume. Experiments demonstrate that our storage model outperforms the traditional one in terms of both space and time efficiency.

In wireless sensor networks, the connectivity-based localization protocols are widely studied due to low cost and no requirement for special hardware. Many connectivity-based algorithms rely on distance estimation between nodes according to their hop count, which often yields large errors in anisotropic sensor network. In this paper, we propose a virtual potential field algorithm, in which the estimated positions of unknown nodes are iteratively adjusted by eliminating the inconsistency to the connectivity constraint. Unlike current connectivity-based algorithms, VPF effectively exploits the connectivity constraint information, regardless of distance estimation between nodes, thus achieving high localization accuracy in both isotropic and anisotropic sensor networks. Simulation results show that VPF improves the localization accuracy by an average of 47% compared with MDS in isotropic network, and 42% compared with PDM in anisotropic network. As a refinement procedure, the average improvement factor of VPF is 56% and 50%, based on MDS and PDM respectively.

In recent years, there has been an increasing interest in the adoption of wireless sensor networks (WSNs) for structural health monitoring (SHM). However, considering the large amount of sampled data, limited power supply and wireless bandwidth of WSNs, it is generally not possible for sensor nodes to monitor structural condition continuously especially for long-term SHM. From SHM perspective, it is highly desirable to collect data during the occurrence of some certain kinds of events such as earthquakes, large wind, etc, since data collected during these periods are more informative for damage detection purpose. However, these events in SHM occur infrequently and if happen, only last for a very short period of time. To effectively capture these short events using energy-limited wireless sensor nodes is a challenging task that has not been addressed in literature. In this paper, we propose a fast and reliable scheme to capture these short-term events. In terms of hardware, the radio-triggered unit and the vibration-triggered unit are designed in our motes. From software perspective, we develop the event capture scheme to realize fast, reliable and energy-efficient event detection under noisy environment. We mainly study the very first problem of the scheme: sentry selection. The optimization problem is formulated and we show that the problem is a general case of the classical k-center problem. Then we propose a greedy algorithm to solve this problem, and conduct simulation to test the effectiveness of the proposed algorithm.

One primary issue which hinders large-scale Radio Frequency Identification (RFID) applications is the imperfect read rate. According to Friis equation and experiments, we find that the dipole tag's orientation plays a significant role in read performance both in theory and practice. In this paper, we consider how to deploy multiple reader antennas to alleviate the negative effect caused by uncontrollable tag orientations in item-level applications. Different from previous work, we expand the candidate antenna positions from the portal to real three dimensional space and establish two estimation functions based on sphere coverage models under different polarized environment. Meanwhile, we provide an improved enumeration scheme with leaping and layering search strategies based on sphere quadtree (SQT) model to find optimized deployment.

Sensor networks nowadays are widely used for structural health monitoring; for example, the sensor monitoring system deployed on the Guangzhou New TV Tower, China. While wired systems still dominate, it is commonly believed that wireless sensors will play a key role in the near future. One key difficulty for such systems is the data transmission from the sensor nodes to the base station. Given the long span of the civil structures, neither a strategy of long-range one-hop data transmission nor short-range hop-by-hop communication is cost-efficient. In this paper, we propose a novel scheme of using the elevators to assist data collection. A base station is attached to an elevator. A representative node on each floor collects and transmits the data to the base station using short range communication when the elevator stops at or passes by this floor. As such, communication distance can be minimized. To validate the feasibility of the idea, we first conduct an experiment in an elevator of the Guangzhou New TV Tower. We observe steady transmission when elevator is in movement. To maximize the gain, we formulate the problem as an optimization problem where the data traffic should be transmitted on time and the lifetime of the sensors should be maximized. We show that if we know the movement pattern of the elevator in advance, this problem can be solved optimally. We then study the online version of the problem and show that no online algorithm has a constant competitive ratio against the offline algorithm. We show that knowledge of the future elevator movement will intrinsically improve the data collection performance. We discuss how the information could be collected and develop online algorithms based on different level of knowledge of the elevator movement patterns. Theoretically, given that the links capacity assumptions we made, we can prove that our online algorithm can guarantee data delivery on time. In practice, we may set a buffer zone to minimize the possible data delivery violation. A comprehensive set of simulations and MicaZ testbed experiments have demonstrated that our algorithm substantially outperforms conventional multihop routing and naive waiting for elevator scheme. The performance of our online algorithm is close to the optimal offline solution.

Existing localization algorithms for mobile sensor networks are usually based on the Sequential Monte Carlo (SMC) method. They either suffer from low sampling efficiency or require high beacon density to achieve high localization accuracy. Although papers can be found for solving the above problems separately, there is no solution which addresses both issues. In this paper, we propose an energy efficient algorithm, called WMCL, which can achieve both high sampling efficiency and high localization accuracy in various scenarios. In existing algorithms, a technique called bounding-box is used to improve the sampling efficiency by reducing the scope from which the candidate samples are selected. WMCL can further reduce the size of a sensor node's bounding-box by a factor of up to 87 percent and, consequently, improve the sampling efficiency by a factor of up to 95 percent. The improvement in sampling efficiency dramatically reduces the computational cost. Our algorithm uses the estimated position information of sensor nodes to improve localization accuracy. Compared with algorithms adopting similar methods, WMCL can achieve similar localization accuracy with less communication cost and computational cost. Our work has additional advantages. First, most existing SMC-based localization algorithms cannot be used in static sensor networks but WMCL can work well, even without the need of experimentally tuning parameters as required in existing algorithms like MSL*. Second, existing algorithms have low localization accuracy when nodes move very fast. We propose a new algorithm in which WMCL is iteratively executed with different assumptions on nodes' speed. The new algorithm dramatically improves localization accuracy when nodes move very fast. We have evaluated the performance of our algorithm both theoretically and through extensive simulations. We have also validated the performance results of our algorithm by implementing it in real deployed static sensor networks. To the best of our knowledge, we are the first to implement SMC-based localization algorithms for wireless sensor networks in real environment.

This paper presents the design of a decentralized storage scheme to support multi-dimensional range queries over sensor networks. We build a distributed k-d tree based index structure over sensor network, so as to efficiently map high dimensional event data to a two-dimensional space of sensors while preserving the proximity of events. We propose a dynamic programming based methodology to control the granularity of the index tree in an optimized approach, and an optimized routing scheme for range query processing to achieve best energy efficiency. The simulation results demonstrate the efficiency of the design.

Localization is an essential problem in Wireless Sensor Networks (WSNs). Many localization algorithms have been proposed, but few efforts have been paid on theoretical analysis on the accuracy of these algorithms. Because it is naturally to formalize range-based localization problems as deterministic parameter estimation problems, for range-based localization algorithms Cramér-Rao Lower Bound (CRLB) has been used to lower bound the variance on the estimation of sensor's positions. However, few similar works have been done for range-free localization algorithms. In this paper, based on geometry properties, we theoretically analyze bounds on accuracy for Region-Based Localization (RBL) algorithms which can be classified as one type of range-free localization algorithms. We prove that if in a RBL algorithm, the deployment region R with the area size s is partitioned into k regions (they can be with any shape and any area size), the localization accuracy is bounded below by no matter how the algorithm partitions R. Although the lower bound is not theoretically tight, our simulation results show that the gap between this bound and achievable accuracy is very small. We conjecture a tighter lower bound when k is large enough. We also observe that in order to achieve high localization accuracy, partitioned regions should have nearly the same size. We give three examples with simulation results to show how the results can be used to set the values of the parameters, like k and the corresponding anchor/event number, in a RBL algorithm in order to achieve desired localization accuracy.

Most of the proposed communication protocols for wireless sensor networks focus on the energy efficiency. However, it often brings poor latency performance. In this paper, we develop a novel cross-layer designed asynchronous protocol EEFF (Energy Efficient and Fast Forwarding) for wireless sensor networks regarding low latency and energy efficiency. EEFF improves low power listening approach and introduces dynamical routing selection to reduce the latency. We evaluate the performance of the EEFF protocol in a testbed of 16 MICAZ motes and perform larger scale experiments with NS-2. These experiments demonstrate that EEFF significantly improves the latency and energy performance compared with state-of-art asynchronous protocols, and it's especially suitable for large scale dense wireless sensor networks.

Data-centric storage is an effective and important technique in sensor networks, however, most data-centric storage schemes may not be energy efficient and load balanced due to non-uniform event and query distributions. This paper proposes EEBASS, it utilizes an approximation algorithm to solve the optimal storage placement problem according to the variance of event and query distributions, aiming to minimize the total energy consumption for data-centric storage scheme. And it further leverages a ring based replication structure to achieve the load balance goal. Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric storage mechanisms in sensor network.

Localization in mobile sensor networks is more challenging than in static sensor networks because mobility increases the uncertainty of nodes' positions. Most existing localization algorithms in mobile sensor networks use Sequential Monte Carlo (SMC) methods due to their simplicity in implementation. However, SMC methods are very time-consuming because they need to keep sampling and filtering until enough samples are obtained for representing the posterior distribution of a moving node's position. In this paper, we propose a localization algorithm that can reduce the computation cost of obtaining the samples and improve the location accuracy. A simple bounding-box method is used to reduce the scope of searching the candidate samples. Inaccurate position estimations of the common neighbor nodes is used to reduce the scope of finding the valid samples and thus improve the accuracy of the obtained location information. Our simulation results show that, comparing with existing algorithms, our algorithm can reduce the total computation cost and increase the location accuracy. In addition, our algorithm shows several other benefits: (1) it enables each determined node to know its maximum location error, (2) it achieves higher location accuracy under higher density of common nodes, and (3) even when there are only a few anchor nodes, most nodes can still get position estimations.

Data gathering is a major function of many applications in wireless sensor networks (WSNs). The most important issue in designing a data gathering algorithm is how to save energy of sensor nodes while meeting the requirement of applications/users such as sensing area coverage. In this paper, we propose a novel hierarchical clustering protocol for long-lived sensor network. EAP achieves a good performance in terms of lifetime by minimizing energy consumption for in-network communications and balancing the energy load among all nodes. EAP introduces a new clustering parameter for cluster head election, which can better handle the heterogeneous energy capacities. Furthermore, it also introduces a simple but efficient approach, namely intra-cluster coverage to cope with the area coverage problem. We evaluate the performance of the proposed protocol using a simple temperature sensing application. Simulation results show that our protocol significantly outperforms LEACH and HEED in terms of network lifetime and the amount of data gathered.

Topology control for fault tolerant communication is one of the important issues in wireless sensor networks. This paper presents a simple mechanism of fault tolerant topology control for generating undirected scale-free networks, where the network evolution is determined by the rules of growth and preferential attachment. The authors prove that this mechanism produces scale-free networks with degree exponent gamma = 1. The dynamic analysis found that this evolution model can maintain the character of scale-free networks and can improve the uniformity of the degree distribution of the networks as compared with Barabasi and Albert model.