Numerical and Combinatorial Algorithms for Location Problems arising in Wireless Sensor Networks and Other Applications

点击翻译按钮获取中文摘要

The objective of the proposed research is to develop better algorithms for solving various locationproblems. Sample applications of these problems include sensor localization{where we compute thelocation of every sensor node in a wireless sensor network, relay node placement{where we computethe locations for the placement of the minimum number of more powerful but more expensiverelay nodes into a sensor network, and amplier placement{where we compute the locations for theplacement 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 locationscience 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. Knowledgeof sensor locations can greatly improve various routing algorithms. However, due to the energyconstraint in sensor networks, GPS can not be used. Also due to the ad hoc nature and the energyconstraint, localization and other algorithms in wireless sensor networks have to be localized ordistributed. Therefore it is diffcult to apply traditional location techniques to sensor networksdirectly.One of the goals of the proposed research is to take advantage of the PI's expertise in locationtheory and numerical optimization to design better sensor localization algorithms that are suitablefor wireless sensor networks. Another goal of the proposed research is to design better algorithmsfor relay node placement using techniques from both numerical and combinatorial optimization.Our approach to the sensor localization problem is numerical in nature, including investigationsof numerical stability in distributed sensor localization. Our approach to the relay node placementis combinatorial in nature. Due to the non-convex nature of the program, numerical optimizationis used only for subproblems or for relaxations. It is worth noting that the same problem findsapplications in both relay node placement in a at sensor network, and in amplifier placement in awide 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 hardwarerelated 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 sensorlocalization and a methodology for error propagation control that may be used in other distributedalgorithm such as time synchronization in wireless sensor networks; (c) better algorithms (bothnumerical 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) Humanresources{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 journalsand conferences.