This paper studies the problem of integrated optical camera communication and scene sensing. Due to the tight coupling between background images and stripe information in low signal-to-noise ratio (SNR) encoded images, existing methods cannot simultaneously achieve high-quality optical signal decoding for LED-to-camera communication and background image reconstruction for scene sensing. To address this challenge, this paper analyzes the adversarial characteristics between stripe information and background images, and proposes GANOCCAS, a generative adversarial learning framework tailored for integrated optical camera communication and scene sensing that effectively resolves mutual interference between stripes and background content. First, we design a generator using a CondConv-based 4-layer U-NET architecture with SimAM modules on the last three residual layers and CondConv+PixelShuffle combinations as upsampling layers. Second, we develop a discriminator that combines multi-scale convolutional networks, pooling layers, and residual networks to output stripe sequences for optical signal decoding. Third, by leveraging pixel loss, multi-scale structural similarity loss, and adversarial loss, we ensure that the generator outputs clean background images suitable for scene sensing while the discriminator decodes optical signals for communication in complex environments. Experiments on synthetic and real-world datasets demonstrate that GANOCCAS effectively reduces communication interference from background images and accurately reconstructs stripe-free background images across various SNR scenarios, outperforming current state-of-the-art methods in both reflected OCC and scene sensing tasks.

Light Detection and Ranging (LiDAR) odometry is a critical technology widely applied in pose estimation for autonomous driving and in Simultaneous Localization and Mapping (SLAM). By using a laser scanner, LiDAR captures environmental information to enable precise spatial localization and mapping. However, traditional LiDAR odometry methods mainly depend on static environmental features for positioning and mapping, limiting adaptability in dynamic settings and reducing pose estimation accuracy. To overcome this limitation, we propose ALO, a novel adaptive LiDAR odometry approach designed for dynamic environments. First, an adaptive constant velocity model predicts the expected motion trajectory, supplying prior pose information, while a first-in-first-out voxel grid manages the local map in dynamic conditions. Next, a linear system with dynamic weights based on point-surface residuals is established, minimizing the influence of dynamic features on pose estimation. Finally, the predicted prior pose serves as the initial value for adaptive Iterative Closest Point (ICP) registration, enhancing pose estimation accuracy and enabling real-time local map updates. Extensive experiments on the public KITTI dataset demonstrate that the proposed method achieves at least a 23.69% improvement in pose estimation accuracy over existing solutions.

The location context can benefit a broad range of context-aware applications, where recognizing and locating contextual objects, such as hair dryers, coffee machines, or water faucets, which are not equipped with any smart modules and thus unable to emit modulated signals, provide fine-grained contextual information. While there have been extensive researches on localizing smart mobile devices, little has been done for locatingcontextual objects, let alone for recognizing and locating them together. In this article, we aim to study the problem of simultaneously recognizing and locating such contextual objects and present CORAL, a contextual object recognition and locating scheme by the usage of unmodulated acoustic signals from the working contextual objects recorded by the commercial off-the-shelf smartphones of users. Specifically, CORAL exploits the frequency and power features of these signals to build a mel-frequency cepstral coefficients (MFCCs) data set for contextual objects, and constructs a classifier for contextual object recognition by using bidirectional LSTM (BiLSTM) and a regression model for object-to-device distance computation by using LightGBM, which is then used for object locating with the help of the user’s trace. We implement a prototype of CORAL and extensive experiments show that the CORAL achieves high recognition accuracy and locating accuracy, even when there are concurrent working contextual objects or ambient noises.

We develop WiDE, a WiFi-distance estimation based group profiling system using LightGBM. Given the uploaded WiFi information by users, WiDE can automatically learn powerful hidden features from the proposed features for between-user distance estimation, and infer group membership with the estimated distance. For each group, WiDE classifies the mobility level, and recognizes the group structure by applying the multi-dimensional scaling technique on the matrix of distance between pairwise users within the same group. We first validate the performance of between-user distance estimation via conducting extensive experiments in a three-floor campus building and a shopping center, and the results show that WiDE outperforms other machine learning based approaches for between-user distance estimation, with the average absolute error (AAE) of 0.69m and 1.14m for the campus building and shopping center, respectively, and the corridor identification accuracy for the campus building is over 99 percent. In addition, the experiments in the shopping center show that our approach can accurately detect groups, classify group mobility into fine-grained level and recognize the group structure.

We study the problem of cross-modality person reidentification (ReID) and tracking with dual visible-infrared (VI) cameras, while most existing efforts on tracking-by-detection have been paid on single-modality visible ReID which is inapplicable for poor-light environments. The major difficulties for cross-modality (e.g., VI) ReID stem from the large modality gap between three-channel visible images and one-channel infrared images and such unknown environmental factors as background clutter, occlusions, etc. To tackle these issues, we propose to enrich the diversities of visible and infrared images for intra- and cross-modality matching by using both the channel-aware data augmentation (DA) techniques (e.g., channel exchanged augmentation and random occlusions) and standard DA techniques. On top of these DA techniques, we incorporate ResNet50 and vision transformer (ViT) into the feature extraction backbone network and apply the dynamic weight average (DWA) strategy for learning loss weights by regarding the minimization of identity loss and triplet loss as a multitask learning problem. We then apply the proposed ReID approach for person tracking in the field of interests. The experiments on two public data sets, i.e., RegDB and SYSU-MM01, show that our approach can improve the performance of state-of-the-art rank-1, mAP, and mINP for cross-modality matching. In addition, the experiments on our data set show that tracking by VI-ReID using dual VI cameras can achieve an accuracy of around 0.24 m.

In this article, we study the problem of passive human localization using an infrared (IR) thermal imaging camera which detects IR radiation emitted by human without carry-on devices and thereby generates a heat map of human body. Rather than directly using the heat map, we propose to exploit temperature of human body and design a lightweight approach for human localization using machine learning techniques. We observe that person-to-camera distance is closely related with the position and the size of a person’s head in the heat map, and several other features, such as variance, skewness, and kurtosis of temperatures in the head region are also good indicators of person-to-camera distance estimation. Accordingly, we propose a set of features and construct a model for inferring person-to-camera distance using machine learning techniques. With the estimated distance, we further compute human localization based on the relative position of the person in the heat map, the estimated person-to-camera distance, and the location and the DFoV of the IR thermal camera. Our experiments in real environments show that the proposed approach can accurately estimate person-to-camera distance and human localization with submeter errors.

Existing studies on indoor navigation often require such a pre-deployment as floor map, localization system and/or additional (customized) hardwares, or human motion traces, making them prohibitive when the situation deviates from these requirements (e.g., navigating a crowd of panicking people where no localization system or motion traces are available). The main observation inspiring our work without reliance on such pre-deployment is that when there are sufficient participants (e.g., a crowd of panicking people), the WiFi signatures collected by participants can serve as the fingerprints (referred to as location fingerprints) of their unknown locations. By computing relative positions of these location fingerprints we can connect them to form a global map. Such a map reflects the topology of the underlying walkable space and thus holds the potential of offering a navigation path for any intended users. Based on this observation, we design Fly-Navi, a crowdsourcing based indoor navigation system via on-the-fly map generation, and primarily designed for indoor environments with rectilinear and narrow corridors. Specifically, each participant uploads sensory data, and the server then generates a global map (on-the-fly map) through a series of operations such as local map generation, local map stitch and edge computation. On top of the global map, Fly-Navi computes a navigation path to the given destination and tracks the progress. We implement the prototype of Fly-Navi and our experiments show that Fly-Navi can quickly generate a correct global map with the 80-percentile of between-fingerprint distance error less than 3 meters, which is important for computing turning points of the map and hereon offering turn-by-turn instructions, and correctly navigate the intended users to their destinations.

The number of vehicles has increased year by year, especially individual vehicles. In addition to meeting basic transportation needs, vehicles are expected to serve varied location-based services and applications for humans. However, it can constitute severe risks for privacy. In this article, we concentrate on one of the most sensitive information, namely, social relationships, that can be inferred from the vehicle mobility data. We propose a social relationship inference model, which provides a new perspective for privacy preservation in human mobility data. In particular, we extract discriminative features from both the spatial and temporal dimensions. Then, the heterogeneous features are being merged with a fusion model to improve the performance of inference. Extensive experiments on the real-world data set validate the effectiveness of the extracted features in estimating social connections and demonstrate that our method significantly outperforms the baseline models.

The ubiquitous luminaries provide a new dimension for indoor navigation, as they are often well-structured and the visible light is reliable for its multipath-free nature. However, existing visible light-based technologies, which are generally frequency-based, require the modulation on light sources, modification to the device, or mounting extra devices. The combination of the cost-extensive floor map and the localization system with constraints on customized hardwares for capturing the flashing frequencies, no doubt, hinders the deployment of indoor navigation systems at scale in, nowadays, smart cities. In this paper, we provide a new perspective of indoor navigation on top of the virtual graph representation. The main idea of our proposed navigation system, named PILOT, stems from exploiting the peak intensities of ubiquitous unmodulated luminaries. In PILOT, the pedestrian paths with enriched sensory data are organically integrated to derive a meaningful graph, where each vertex corresponds to a light source and pairwise adjacent vertices (or light sources) form an edge with a computed length and direction. The graph, then, serves as a global reference frame for indoor navigation while avoiding the usage of pre-deployed floor maps, localization systems, or additional hardwares. We have implemented a prototype of PILOT on the Android platform, and extensive experiments in typical indoor environments demonstrate its effectiveness and efficiency.

Accurately estimating the distance between persons with COTS mobile devices can benefit many applications (e.g., group activity analysis, indoor navigation, etc.). In this paper we present WiDE, a deep learning-based system for estimating person-to-person distance based on surrounding WiFi signals. Specifically, WiDE has two phases: offline learning and online prediction. In offline learning phase, we apply a stacked autoencoder (SAE) for pre-training the weights of a deep neural network (DNN), and establish a DNN-based classifier for predicting between-person discretized distance and corridor identity using WiFi signals. During online prediction phase, based on the trained DNN with the SAE and newly uploaded WiFi information, we estimate the corridor identities and the distance between pairwise persons. We validate our system by conducting extensive experiments in a three-floor campus building, and the results show that WiDE achieves the corridor identification accuracy over 98 % and the median ranging error of 0.9m and 3.0m for two persons on the same corridor and on different corridors, respectively, which outperforms the state-of-the-art proximity inferring system [1].

We consider the navigation application of 3D sensor networks that can proactively guide the movement of internal users from potential dangers to a safe exit, where a 3D sensor network serves as a reactive system, instead of a monitoring tool or a medium of data acquisition. Most if not all existing efforts in this line concentrate on 2D cases only, and none of them can be readily applied to 3D sensor networks, posing it a non-trivial challenge to design an effective and light-weight navigation protocol in 3D sensor networks. In this paper, we propose the first location-free, distributed, and scalable navigation protocol that can provide a navigation route for users inside the 3D sensor network with guaranteed safety. More specifically, we formulate the navigation problem as the minimum cumulative exposure problem, and design SNP, a navigation protocol based on the so-called 1-manifold skeleton, which offers a safe path with a near-optimal cumulative exposure to dangers. Extensive simulations validate the effectiveness and efficiency of the proposed algorithm.

Offering the services of real-time tracking and arrival time prediction is a common welfare for bus riders and transit agencies, especially in urban environments. On the down side, the traditional GPS-based solutions work poorly in urban areas due to urban canyons, while the location systems based on cellular signal also suffer from inherent limitations. In this paper, we present a powerful tool named Signal Voronoi Diagram (SVD) to partition the radio-frequency (RF) signal space of WiFi Access Points (APs), distributed where a bus travels, into Signal Cells, and then into fine-grained Signal Tiles, tackling the problem of noisy received signal strength (RSS) readings and possible AP dynamics. On top of SVD, we present a novel framework so-called WiLocator, to track and predict the arrival time of an urban bus based on the surrounding WiFi information collected by the commodity off-the-shelf (COTS) smartphones of bus riders, the mobility constraint of a bus and the temporal consistency of travel time of buses on the overlapped road segments. We also show the WiLocator's power of generating an accurate and real-time traffic map with the predicted travel time on each road segment. We implement the prototype of WiLocator and conduct the in-situ experiment to demonstrate its accuracy.

The in-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table GHT is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to correctly define the bounding box. It is envisioned that the skeleton has the power to facilitate computing a precise bounding box. In existing works, the focus has been on skeleton extraction algorithms targeting for 2D sensor networks, which usually deliver a 1-manifold skeleton consisting of 1D curves. It faces a set of non-trivial challenges when 3D sensor networks are considered, in order to properly extract the surface skeleton composed of a set of 2-manifolds and possibly 1D curves. In this paper, we study the problem of surface skeleton extraction in 3D sensor networks. We propose a scalable and distributed connectivity-based algorithm to extract the surface skeleton of 3D sensor networks. First, we propose a novel approach to identifying surface skeleton nodes by computing the extended feature nodes such that it is robust against boundary noise, etc. We then find the maximal independent set of the identified skeleton nodes and triangulate them to form a coarse-grained surface skeleton, followed by a refining process to generate the fine-grained surface skeleton. Furthermore, we design an efficient updating scheme to react to the network dynamics caused by node failure, insertion, etc. We also investigate the impact of boundary incompleteness and present a scheme to extract the surface skeleton under incomplete boundary. Finally, we apply the extracted surface skeleton to facilitate the design of data storage protocol and curve skeleton extraction algorithm. Extensive simulations show the robustness of the proposed algorithm to shape variation, node density, node distribution, communication radio model and boundary incompleteness, and its effectiveness for data storage and retrieval application with respect to load balancing.

Efficient in-network information storage and retrieval is of paramount importance to sensor networks and has attracted a large number of studies while most of them focus on 2D fields. In this paper, we propose novel Reeb graph based information storage and retrieval schemes for 3D sensor networks. The key is to extract the line-like skeleton from the Reeb graph of a network, based on which two distance-sensitive information storage and retrieval schemes are developed: one devoted to shorter retrieval path and the other devoted to more balanced load. Desirably, the proposed algorithms have no reliance on the geographic location or boundary information, and have no constraint on the network shape or communication graph. The extensive simulations also show their efficiency in terms of sensor storage load and retrieval path length.

In sensor networks, skeleton extraction has emerged as an appealing approach to support many applications such as load-balanced routing and location-free segmentation. While significant advances have been made for 2D cases, so far skeleton extraction for 3D sensor networks has not been thoroughly studied. In this paper, we conduct the first work of a unified framework providing a connectivity-based and distributed solution forline-likeskeleton extraction in both 2D and 3D sensor networks. We highlight its practice as: 1) it has linear time/message complexity; 2) it provides reasonable skeleton results when the network has low node density; 3) the obtained skeletons are robust to shape variations, node densities, boundary noise and communication radio model. In addition, to confirm the effectiveness of the line-like skeleton, a 3D routing scheme is derived based on the extracted skeleton, which achieves balanced traffic load, guaranteed delivery, as well as low stretch factor.

Accurate localization in wireless sensor networks is the foundation for many applications, such as geographic routing and position-aware data processing. In this paper, we develop a new localization protocol based on approximate convex decomposition (ACDL), with reliance on network connectivity information only. ACDL can calculate the node virtual locations for a large-scale sensor network with a complex shape. We first examine one representative localization algorithm and study the influential factors on the localization accuracy, including the sharpness of the angle at the concave point and the depth of the concave valley. We show that after decomposition, the depth of the concave valley becomes irrelevant. We thus define the concavity according to the angle at a concave point, which reflects the localization error. We then propose ACDL protocol for network localization. It consists of four main steps. First, convex and concave nodes are recognized and network boundaries are segmented. As the sensor network is discrete, we show that it is acceptable to approximately identify the concave nodes to control the localization error. Second, an approximate convex decomposition is conducted. Our convex decomposition requires only local information and we show that it has low message overhead. Third, for each convex section of the network, an improved MDS algorithm is proposed to compute a relative location map. Fourth, a fast and low complexity merging algorithm is developed to construct the global location map. Besides, by slight modification on the third step, we propose a variant of ACDL, denoted by ACDL-Tri, which is fully distributed and scalable while the localization accuracy is still comparable. We finally show the efficiency of ACDL by extensive simulations.

Existing algorithms for topology extraction focus on only one topology feature, either skeleton or segmentation, in 2D or 3D sensor networks, most of which requiring complete boundary information. As boundary information is not easily obtained, especially in sparse 3D sensor networks, and extracting these two features separately is very expensive, in this study, we propose to simultaneously extract the line-like skeleton of 2D/3D sensor networks and decompose the network into nice pieces, by constructing the Reeb graph. The Reeb graph has been envisioned as a powerful tool for encoding the topology of an object in computer graphics and computational geometry, where the key is to select the right feature function f. Without using boundary information, we first construct a cut graph, and then regard the distance of a node to the nearest cut as the function f such that the corresponding Reeb graph is pose independent, based on which the skeleton extraction and network decomposition are simultaneously conducted. Some simulation results are presented to show the efficiency of the algorithm.

In-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table (GHT) is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to correctly define the bounding box. It is envisioned that the skeleton has the power to facilitate computing a precise bounding box. In existing works, the focus has been on skeleton extraction algorithms targeting for 2D sensor networks, which usually delivers a 1-manifold skeleton consisting of 1D curves. It faces a set of non-trivial challenges when 3D sensor networks are considered, in order to properly extract the surface skeleton composed of a set of 2-manifolds and possibly 1D curves.

In sensor networks, skeleton extraction has emerged as an appealing approach to support many applications such as load-balanced routing and location-free segmentation. While significant advances have been made for 2D cases, so far skeleton extraction for 3D sensor networks has not been thoroughly studied. In this paper, we conduct the first work on the skeleton extraction in 3D sensor networks, and propose a unified framework for line-like skeleton extraction in both 2D and 3D sensor networks. Our algorithm has the following three steps: first, each node identifies itself as a skeleton node if the geodesic shortest paths between its nearest boundary nodes (referred to as feature nodes) decompose the boundary of the network into more than one connected component; second, each skeleton node is assigned a monotonically increasing importance measure according to the maximum Lebesgue measure of the connected components of the boundary such that the identified skeleton nodes are self-connected; and finally, the skeleton is pruned based on the proposed metric branch similarity. The proposed algorithm is connectivity-based, distributed and of low complexity. Extensive simulations show that it is robust to shape variations and boundary noise.

In sensor networks community, the skeleton (or medial axis), as an important infrastructure which can correctly capture the topological and geometrical features of the underlying network, has been widely used for facilitating routing, navigation, segmentation, etc. Even though there are a handful of skeleton extraction solutions, the measurement of the goodness of the derived skeleton is often application-oriented, and there is no quantitative metric for this task. In this paper, we study the problem of skeleton extraction and conduct the first work on quantitative evaluation of skeleton in sensor networks. Different from traditional schemes which assume complete or incomplete boundaries, the proposed skeleton extraction algorithm is based on mere connectivity information, without reliance on any boundary information. More specifically, for each node we compute its variability factor based on the neighborhood sizes of the node and its neighbors, which can reflect how central a sensor node is to the network, and a sensor node identifies itself as a skeleton node if its variability factor is locally maximal. Next, we present a light-weight scheme to connect these skeleton nodes. Finally, we proposed a metric, named visibility coefficient, to quantitatively evaluate the derived skeleton.

We study the problem of skeleton extraction for large-scale sensor networks with reliance purely on connectivity information. Existing efforts in this line highly depend on the boundary detection algorithms, which are used to extract accurate boundary nodes. One challenge is that in practical this could limit the applicability of the boundary detection algorithms. For instance, in low node density networks where boundary detection algorithms do not work well, the extracted boundary nodes are often incomplete. This paper brings a new view to skeleton extraction from a distance transform perspective, bridging the distance transform of the network and the incomplete boundaries. As such, we propose a distributed and scalable algorithm for skeleton extraction, called DIST, based on DIStance Transform, while incurring low communication overhead. The proposed algorithm does not require that the boundaries are complete or accurate, which makes the proposed algorithm more practical in applications. First, we compute the distance transform of the network. Specifically, the distance (hop count) of each node to the boundaries of a sensor network is estimated. The node map consisting of the distance values is considered as the distance transform (the distance map). The distance map is then used to identify skeleton nodes. Next, skeleton arcs are generated by controlled flooding within the identified skeleton nodes, thereby connecting these skeleton arcs, to extract a coarse skeleton. Finally, we refine the coarse skeleton by building shortest path trees followed by a prune phase. The obtained skeleton is robust to boundary noise or shape variations. Besides, we present two specific applications that benefit from the extracted skeleton: identifying complete boundaries and shape segmentation. First, with the extracted skeleton using DIST, we propose to identify more boundary nodes to form a meaningful boundary curve. Second, the utilization of the derived skeleton to segment the network into approximately convex pieces has been shown to be effective.

This paper proposes a novel approach, named DIST, to skeleton extraction from incomplete boundaries using the idea of {\em distance transform}, a concept in the computer graphics area. The main contribution is a distributed and low-cost algorithm that produces accurate network skeletons without requiring that the boundaries be complete or tight. The algorithm first establishes the network's distance transform -- the hop distance of each node to the network's boundaries. Based on this, some {\em critical skeleton nodes} are identified. Next, a set of {\em skeleton arcs} are generated by controlled flooding, connecting these skeleton arcs then gives us a coarse skeleton. The algorithm finally refines the coarse skeleton by building shortest path trees, followed by a prune phase. The obtained skeletons are robust to boundary noise and shape variations.

In sensor networks, skeleton (also known as medial axis) extraction is recognized as an appealing approach to support many applications such as load-balanced routing and location free segmentation. Existing solutions in the literature rely heavily on the identified boundaries, which puts limitations on the applicability of the skeleton extraction algorithm. In this paper, we conduct the first work of a connectivity-based and boundary free skeleton extraction scheme, in sensor networks. In detail, we propose a simple, distributed and scalable algorithm that correctly identifies a few skeleton nodes and connects them into a meaningful representation of the network, without reliance on any constraint on communication radio model or boundary information. The key idea of our algorithm is to exploit the necessary (but not sufficient) condition of skeleton points: the intersection area of the disk centered at a skeleton point x should be the largest one as compared to other points on the chord generated by x, where the chord is referred to as the line segment connecting x and the tangent point in the boundary. To that end, we present the concept of \epsilon-centrality of a point, quantitatively measuring how "central" a point is. Accordingly, a skeleton point should have the largest value of \epsilon-centrality as compared to other points on the chord generated by this point. Our simulation results show that the proposed algorithm works well even for networks with low node density or skewed nodal distribution, etc. In addition, we obtain two by-products, the boundaries and the segmentation result of the network.

Accurate localization in wireless sensor networks is the foundation for many applications, such as geographic routing and position-aware data processing. An important research direction for localization is to develop schemes using connectivity information only. These schemes primary apply hop counts to distance estimation. Not surprisingly, they work well only when the network topology has a convex shape. In this paper, we develop a new Localization protocol based on Approximate Convex Decomposition (ACDL). It can calculate the node virtual locations for a large-scale sensor network with arbitrary shapes. The basic idea is to decompose the network into convex subregions. It is not straight-forward, however. We first examine the influential factors on the localization accuracy when the network is concave such as the sharpness of concave angle and the depth of the concave valley. We show that after decomposition, the depth of the concave valley becomes irrelevant. We thus define concavity according to the angle at a concave point, which can reflect the localization error. We then propose ACDL protocol for network localization. It consists of four main steps. First, convex and concave nodes are recognized and network boundaries are segmented. As the sensor network is discrete, we show that it is acceptable to approximately identify the concave nodes to control the localization error. Second, an approximate convex decomposition is conducted. Our convex decomposition requires only local information and we show that it has low message overhead. Third, for each convex subsection of the network, an improved Multi-Dimensional Scaling (MDS) algorithm is proposed to compute a relative location map. Fourth, a fast and low complexity merging algorithm is developed to construct the global location map. Our simulation on several representative networks demonstrated that ACDL has localization error that is 60%-90% smaller as compared with the typical MDS-MAP algorithm and 20%-30% smaller as compared to a recent state-of-the-art localization algorithm CATL.

Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction for the topology has shown great impact on the performance of such services as location, routing, and path planning in wireless sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications in wireless sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, are not immediately applicable for the discrete and distributed wireless sensor networks. In this paper, we present a novel Connectivity-bAsed Skeleton Extraction (CASE) algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, CASE is distributed as no centralized operation is required, and is scalable as both its time complexity and its message complexity are linearly proportional to the network size. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. We believe that CASE has broad applications and present a skeleton-assisted segmentation algorithm as an example. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms the state-of-the-art algorithms.

Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction has shown great impact on the performance of such services as location, routing, and path planning in sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications in sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, is not immediately applicable for the discrete and distributed sensor networks. In this paper we present CASE: a novel connectivity-based skeleton extraction algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, no centralized operation is required. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms state-of-the-art algorithms.