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

这项研究的目标是开发更好的算法来解决各种定位问题。这些问题的示例应用包括传感器定位{在无线传感器网络中计算每个传感器节点的位置，中继节点布局{在传感器网络中计算功能更强大但更昂贵的最小数量的光路节点的位置，以及放大器布局{在广域光网络中计算最少数量的光学放大器的位置。在欧几里得平面上的定位是定位科学研究人员很好地研究的问题，并且在交通和物流中有应用。传感器网络因其在国土安全、医疗等诸多领域的应用而成为一个蓬勃发展的新研究领域。传感器位置的知识可以极大地改进各种路由算法。然而，由于传感器网络中的能量限制，GPS不能使用。另外，由于无线传感器网络的自组织特性和能量限制，定位等算法必须是局部的或分布式的。因此，将传统的定位技术直接应用于传感器网络是很困难的。本研究的目标之一是利用PI在定位理论和数值优化方面的专业知识，设计出更好的适合于无线传感器网络的传感器定位算法。该研究的另一个目标是利用数值和组合优化技术设计更好的中继节点布局算法。我们的传感器定位问题本质上是数值方法，包括研究分布式传感器定位中的数值稳定性。我们对中继节点位置的方法本质上是组合的。由于程序的非凸性，数值优化仅用于子问题或松弛。值得注意的是，在AT传感器网络中的中继节点布置和在广域光网络中的放大器布置中都存在相同的问题。我们想指出的是，我们的研究重点是解决一些具有广泛应用范围的基本问题的有效算法，而不是与具体应用相关的硬问题。本研究的智力优势包括：(A)更准确、更高效、更具可扩展性的传感器局部化数值算法；(B)分布式传感器定位的稳定性分析以及可用于其他分布式算法的差错传播控制方法，如无线传感器网络中的时间同步；(C)更好的算法(包括数值和组合)用于中继节点布局和相关问题。这项研究的更广泛影响包括：(A)国土安全{先进的定位算法可以帮助提高我军的技术。(B)人力资源：将培训高技能研究生。(C)通过高质量出版物传播研究成果：国际和平协会积极在高质量的期刊和会议上发表研究成果。

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.