The objective of the proposed research is to develop better algorithms for solving various location problems. Sample applications of these problems include sensor localization{where we compute the location of every sensor node in a wireless sensor network, relay node placement{where we compute the locations for the placement of the minimum number of more powerful but more expensive relay nodes into a sensor network, and amplier placement{where we compute the locations for the placement of the minimum number of optical ampliers in a wide area optical network. Location in the Euclidean plane is a problem that is well studied by researchers in location science and has applications in transportation and logistics. Sensor networks is a booming new re- search field due to its applications in homeland security, medical, and many other areas. Knowledge of sensor locations can greatly improve various routing algorithms. However, due to the energy constraint in sensor networks, GPS can not be used. Also due to the ad hoc nature and the energy constraint, localization and other algorithms in wireless sensor networks have to be localized or distributed. Therefore it is diffcult to apply traditional location techniques to sensor networks directly. One of the goals of the proposed research is to take advantage of the PI's expertise in location theory and numerical optimization to design better sensor localization algorithms that are suitable for wireless sensor networks. Another goal of the proposed research is to design better algorithms for relay node placement using techniques from both numerical and combinatorial optimization. Our approach to the sensor localization problem is numerical in nature, including investigations of numerical stability in distributed sensor localization. Our approach to the relay node placement is combinatorial in nature. Due to the non-convex nature of the program, numerical optimization is used only for subproblems or for relaxations. It is worth noting that the same problem finds applications in both relay node placement in a at sensor network, and in amplifier placement in a wide area optical network. We would like to point out that our research focus is on effective algo- rithms for solving some basic problems with wide ranges of applications, rather than on hardware related issues of specific applications. The Intellectual Merits of this research include: (a) numerical algorithms for sensor local- ization that are more accurate, efficient, and scalable; (b) stability analysis of distributed sensor localization and a methodology for error propagation control that may be used in other distributed algorithm such as time synchronization in wireless sensor networks; (c) better algorithms (both numerical and combinatorial) for relay node placement and related problems. The Broader Impacts of this research include the following: (a) Homeland security{ advanced localization algorithms can help improve the technology our military. (b) Human resources{highly skilled graduate students will be trained. (c) Dissemination of research re- sults through high-quality publications{the PI is actively publishing in high quality journals and conferences.
