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.

When emergencies happen, navigation services that guide people to exits while keeping them away from emergencies are critical in saving lives. To achieve timely emergency navigation, early and automatic detection of potential dangers, and quick response with safe paths to exits are the core requirements, both of which rely on continuous environment monitoring and reliable data transmission. Wireless sensor networks (WSNs) are a natural choice of the infrastructure to support emergency navigation services, given their relatively easy deployment and affordable costs, and the ability of ubiquitous sensing and communication. Although many efforts have been made to WSN-assisted emergency navigation, almost all existing works neglect to consider the hazard levels of emergencies and the evacuation capabilities of exits. Without considering such aspects, existing navigation approaches may fail to keep people farther away from emergencies of high hazard levels and would probably encounter congestions at exits with lower evacuation capabilities. In this paper, we propose SEND, a situation-aware emergency navigation algorithm, which takes the hazard levels of emergencies and the evacuation capabilities of exits into account and provides the mobile users the safest navigation paths accordingly. We formally model the situation-aware emergency navigation problem and establish a hazard potential field in the network, which is theoretically free of local minima. By guiding users following the descend gradient of the hazard potential field, SEND can thereby achieve guaranteed success of navigation and provide optimal safety. The effectiveness of SEND is validated by both experiments and extensive simulations in 2D and 3D scenarios.

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.

One of the major applications of wireless sensor networks (WSNs) is the navigation service for emergency evacuation, the goal of which is to assist people in escaping from a hazardous region safely and quickly when an emergency occurs. Most existing solutions focus on finding the safest path for each person, while ignoring possible large detours and congestions caused by plenty of people rushing to the exit. In this paper, we present CANS, a C ongestion-Adaptive and small stretch emergency Navigation algorithm with WSNs. Specifically, CANS leverages the idea of level set method to track the evolution of the exit and the boundary of the hazardous area, so that people nearby the hazardous area achieve a mild congestion at the cost of a slight detour, while people distant from the danger avoid unnecessary detours. CANS also considers the situation in the event of emergency dynamics by incorporating a local yet simple status updating scheme. To the best of our knowledge, CANS is the first WSN-assisted emergency navigation algorithm achieving both mild congestion and small stretch, where all operations are in-situ carried out by cyber-physical interactions among people and sensor nodes. CANS does not require location information, nor the reliance on any particular communication model. It is also distributed and scalable to the size of the network with limited storage on each node. Both experiments and simulations validate the effectiveness and efficiency of CANS.

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 wireless sensor networks (WSNs), a space filling curve (SFC) refers to a path passing through all nodes in the network, with each node visited at least once. By enforcing a linear order of the sensor nodes through an SFC, many applications in WSNs concerning serial operations on both sensor nodes and sensor data can be performed, with examples including serial data fusion and path planning of mobile nodes. Although a few studies have made efforts to find such SFCs in WSNs, they primarily target 2D planar or 3D surface settings and cannot be directly applied to 3D volumetric WSNs due to considerably more complex geometric features and topology shapes that the 3D volumetric settings introduce. This article presents BLOW-UP, a distributed, scalable, and connectivity-based algorithm to construct an SFC for a 3D volumetric WSN (or alternatively to linearize the 3D volumetric network). The main idea of BLOW-UP is to decompose the given 3D volumetric network into a series of connected and closed layers, and the nodes are traversed layer by layer, incrementally from the innermost to the outermost, yielding an SFC covering the entire network, provably at least once and at most a constant number of times. To the best of our knowledge, BLOW-UP is the first algorithm that realizes linearization in 3D volumetric WSNs. It does not require advance knowledge of location or distance information. It is also scalable with a nearly constant per-node storage cost and message cost. Extensive simulations under various networks demonstrate its effectiveness on nodes’ covered times, coverage rate, and covering speed.

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.