Ad Hoc Location Determination Methods

Ad hoc wireless networks present a number of challenges for location determination because few or none of the nodes involved in the network need to be fixed. Most location determination methods require that certain nodes in the network have well-known locations. One consequence of the flexibility of ad hoc networks is that nodes with known locations can be quite sparsely distributed throughout the network. If the known locations are sparse, then determining the location of other nodes can be difficult.

Known locations in a wireless ad hoc network can be determined by external means. If a gateway node is used, then its means of access to the Internet can provide other means of locating it, such as those previously described for DSL, Ethernet, or cellular networks. It is quite possible that the location of a gateway may be known to the LIS. GPS is also a realistic possibility. There could be a number of nodes within the network that are equipped with a GPS capability; the LIS can use asserted location information in determination calculations, providing the LIS trusted the information that it was provided.

The difficulty with having a sparse distribution of known locations is that uncertainty accumulates as the distance from those known locations increases. The uncertainty in the location of a node is increased for each hop from the known location. This is because the uncertainty in determining location is compounded with any uncertainty that exists in the reference locations used to determine that location. For instance, if a device is located using a method with an uncertainty radius of 10 meters, but the transceiver location that this estimate is based on also has an uncertainty radius of 8 meters; the actual uncertainty radius in the final device location is 18 meters. The total area of uncertainty increases in proportion to the square of the number of hops from the known location.

Figure 7.7 shows how precision degrades the further from an access point the target node is. This example assumes that the location of another node can be determined using a single reference point. In reality, location estimates depend on multiple known points, but the overall impact of imprecision in those known locations is similar.

Figure 7.7: Degradation of precision caused by multiple hops in an ad hoc network.

The degradation of precision example demonstrates how improved location determination methods can contribute to the usability of location information. Even if the precision at one hop is far in excess of that which is required, the improvement can have a large impact in an ad hoc network. Figure 7.8 shows the effect that improving precision does to final accuracy over Figure 7.7; this demonstrates what an accuracy improvement can provide in the precision of the final location estimate.

Figure 7.8: The final precision is greatly affected by the precision at each hop.

Precision can be improved by a number of methods. The combination of multiple determination methods can often improve accuracy-for instance, combining angle and range measurements from one access point with a range measurement from another point can greatly improve precision. Another possibility is to combine network measurements with those from other sources; cellular networks, RFID beacons, and GPS are just some of the possible sources of other measurements. In particular, hybrid location determination methods have a greater yield, or probability of successfully determining a location.

In the spirit of using multiple sources to derive location information, this information can also come from the network. If a particular node can be reached through a number of paths, then location determination along each of those paths can be used to refine the location estimate. Figure 7.9 shows how an estimate by one method can be refined when another estimate is available.

Figure 7.9: Using multiple paths to refine a location estimate.

Network Topology in Location Determination

In the spirit of using multiple data points, there are a number of possibilities for ad hoc networks. The routing table that is maintained by each of the nodes in the network is a valuable location measurement. If it can be assumed that connectivity implies proximity, then routing information can be used to derive a possible network layout. The method proposed by Shang et al. (see Reference 1) minimizes each connection in the network to derive a network layout. This layout is not oriented and may be inverted, but if two or more nodes have known locations, it can be matched to the actual network with reasonable accuracy.