Position location techniques and applications - Part 2: Ad hoc and sensor network scenarios

The basic scenario for a PL application in reconfigurable networks can be seen in Figure 5.11. We have nodes with random coordinates in a rectangular area with certain connectivity defining a network topology. Some of those nodes are the APs that are in charge of connectivity to other networks or the Internet.

APs are primary pieces of a wireless network and they have a finite range. APs are actually the "hub" of a wireless network. Each AP is connected to a wired network and every node on the wireless network speaks to an AP, which connects that node to the rest of the world. These APs can have multiple links. Also, when nodes establish a node discovery and service discovery algorithm, APs will be the objectives in terms of applications, connectivity, IP addresses, servers, gateways, and so on.

An AP can be a location mobile unit (LMU). In global systems for mobile communications (GSM), several LMUs are introduced. LMUs have limited capabilities to support PL functions. We propose supporting the location process in ad hoc networks through the use of three APs in a cluster or in any area of the ad hoc network. In most of the methods presented in Chapter 4 to solve the PL problem, three APs act as nodes in the network and provide fixed references in the network for PL purposes.

The evolution of network density and mobility makes necessary certain special nodes located at strategic points in the area so that connectivity is not compromised whenever node density is low. For example, at certain times during the day, there will be a few nodes in the area that might not be capable of establishing a multipath route to an AP. Those special nodes can then be turned on in order to provide coverage at those times every day. These special nodes can have features different from the regular nodes, such as higher transmission power to provide the needed coverage. Also, the nodes can have higher complexity and intelligence in order to turn themselves on and off according to network conditions, so they should be monitoring certain network and air interface variables.

The recent literature has reflected interest in location estimation algorithms for wireless sensor networks [55, 62]. Distributed location algorithms offer the promise of solving multiparameter optimization problems even with constrained resources at each sensor [70]. Devices can begin with local coordinate systems [7] and then successively refine their location estimates [1, 69]. Based on the shortest path from a device to distant reference devices, ranges can be estimated and then used to triangulate.

Distributed algorithms must be carefully implemented to ensure convergence and to avoid error accumulation in which errors propagate serially in the network. Centralized algorithms can be implemented when the application permits deployment of a central processor to perform location estimation. In Celebi and Arslan [9], device locations are solved by convex optimization. Both Moses et al. [55] and Patwari et al. [62] provide ML estimators for sensor location estimation when observations are AOA,TOA [55], and RSS [62].

Since a classical multilateration process cannot be applied directly in an ad hoc environment due to the lack of direct connectivity of users to well-located APs, multihop algorithms are needed. The goal of typical multihop localization schemes is to estimate the position of all nodes in the network based on a fewAPs with known positions. Nodes in the proximity of APs are located first and then these nodes become new land references (with a certain degree of uncertainty) used to locate a new set of neighbors. This process continues in an iterative fashion until positions of all the nodes in the network have been estimated. This type of iterative algorithm suffers from error accumulation throughout the iterations and requires a considerable amount of processing from all nodes in the network.

Many multihop localization algorithms such as APS [59, 60, 74] are geometric in nature and hence do not profit from statistical knowledge of the environment. Further, these methods require communication of the nodes with all immediate neighbors, and at some point they may even require the broadcasting of distance correction factors to the entire network, rendering them power inefficient.

In the literature, statistical multihop positioning schemes have been proposed in Savvides et al. [70], where the methods are based on accurate ranging measurements and linearized least-squares multilateration solutions. These methods require that each node with an unknown position be at a one-hop proximity from at least three land references (some may be APs, and some may be nodes that obtained position estimates from previous iterations of the positioning scheme). Further, the cited schemes rely on the solution of global nonlinear optimization problems to avoid error accumulation in the position estimates.

Even when the computations are distributed through the nodes in the network, the amount of computational load required at each node may render these schemes impractical in many situations. Efforts to statistically characterize error-inducing parameters in multihop localization schemes have appeared in Savvides et al. [71] where ranging andAOA estimation errors are assumed to be Gaussian distributed.

We divide cooperative localization into centralized algorithms,which collect measurements at a central processor prior to calculation, and distributed algorithms, which require nodes to share information only with their neighbors,but possibly iteratively. Both methods are described in the following.