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

提出的研究的目的是开发更好的算法来解决各种locationproblems。这些问题的示例应用包括传感器定位{我们计算无线传感器网络中每个传感器节点的位置，中继节点放置{我们计算传感器网络中最小数量的更强大但更昂贵的中继节点的位置，和更大的位置{其中我们计算广域光网络中最少数量的光路由器的位置。在欧几里得平面中的位置是一个很好的问题，研究人员在locationscience和应用在运输和物流。传感器网络由于其在国土安全、医疗等诸多领域的应用而成为一个新兴的研究领域。传感器位置的知识可以极大地改善各种路由算法。然而，由于传感器网络中能量的限制，GPS不能用于无线传感器网络。同时由于无线传感器网络的自组织特性和能量约束，使得定位等算法必须局部化或分布式.因此，传统的定位技术很难直接应用到传感器网络中，本文的研究目标之一就是利用PI在定位理论和数值优化方面的专长，设计出适合无线传感器网络的更好的传感器定位算法。本研究的另一个目标是利用数值优化和组合优化的方法设计更好的中继节点定位算法，我们的方法本质上是数值的，包括分布式传感器定位中数值稳定性的研究。我们的方法来中继节点placementis组合的性质。由于程序的非凸性，数值优化只用于子问题或松弛。值得注意的是，同样的问题在at传感器网络中的中继节点布置和广域光网络中的放大器布置中都有应用。我们的研究重点是解决一些具有广泛应用的基本问题的有效算法，而不是具体应用中与硬件相关的问题，本研究的智力价值包括：（a）更精确、有效和可扩展的传感器定位数值算法;（B）分布式传感器定位的稳定性分析和误差传播控制方法，该方法可用于其他分布式算法，如无线传感器网络中的时间同步;（c）更好的算法（数值和组合）用于中继节点的放置和相关问题。这项研究的更广泛的影响包括以下几点：（a）国土安全{先进的定位算法可以帮助提高我们的军事技术。(b)人力资源{高技能的研究生将得到培训。(c)通过高质量的出版物传播研究结果{PI积极在高质量的期刊和会议上发表。

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.