We live in a time of unprecendented wireless connectivity as seen from the widespread use of wireless cellular phones and wireless LAN devices. Today, there is great interest in developing location estimation service in wireless networks such as wireless cellular networks and wireless sensor networks. The location estimation service opens the door to many applications that we call Location Based Services (LBS). The current technology, however, fails to meet the requirements for many applications including wireless 911 services, as highlighted by the failure of all major U.S. service operators to meet the October 1, 2001 Phase I deadline of E911---a Federal Communications Commission (FCC) wireless 911 mandate. The service operators are currently under great pressure to meet the December 31, 2005 Phase II deadline. Localization is also important in wireless sensor networks, a technology on the rise. The momentum for commercialization of wireless sensor networks was increased recently when Walmart adopted Radio Frequency IDentification (RFID) for its inventory management.; In this thesis, we investigate location estimation. In particular, we study censored distance estimation algorithms and localization algorithms. A distance between a pair of nodes is censored if the distance cannot be reliably measured. We classify existing censored distance estimation algorithms into simple substitution, shortest path methods, and trigonometric resolution methods. Trigonometric k-clustering is a multiple trigonometric resolution method that uses geometric contraints to estimate censored distances. The second part of this thesis discusses localization algorithms. In surveying existing localization algorithms, we identify two major computational components: geometrical bounds and refinement. We classify and evaluate existing localization algorithms with respect to these components.; We introduce Localization using Multidimensional Scaling or LMDS, a location estimation algorithm, which takes an expanded set of measurements to increase reliability. The two algorithms introduced are compared with existing algorithms using both experimental and simulational data.
展开▼
