AF:Small:Geometric Embedding and Covering: Sequential and Distributed Approximation Algorithms

在过去的十年中，各种各样的无线网络，包括蜂窝网络、无线局域网、传感器网络、社区网络等已经变得无处不在。该奖项的重点是由这些网络的协议和应用程序设计引起的算法问题。该提案试图利用这些网络的一个特征，即网络节点通常位于平面或三维空间中，并且这些节点的通信和传感范围也可以以几何方式建模（例如，欧几里得空间中的磁盘或球体）。因此，该奖项侧重于几何背景下的优化问题，目标是为这些问题设计最终可以在网络节点上有效实现的算法。考虑的一类问题是几何嵌入问题，其中网络节点仅根据通信范围内的其他节点的信息来寻找它们的位置。这些问题的解决方案有可能改进这些网络上的路由协议。pi考虑的另一类问题是几何覆盖问题，其目的是最优地放置具有给定传感能力的传感器节点，以覆盖特定的目标区域。这种覆盖问题出现在各种传感器网络应用中，例如监控桥梁、葡萄园和工厂车间。

Over the last decade, wireless networks of various kinds, including cellular networks, wireless LANs, sensor networks, community networks, etc. have become ubiquitous. This award focuses on algorithmic problems motivated by the design of protocols and applications for some of these networks. One feature of these networks, that the proposal attempts to take advantage of, is that network nodes typically reside in the plane or in 3-dimensional space and furthermore communication and sensing ranges of these nodes may also be modeled geometrically (for example, as disks or spheres in Euclidean space). As a result the award focuses on optimization problems in the geometric context and the goal is to design algorithms for these problems that can eventually be implemented efficiently on the network nodes. One class of problems considered are geometric embedding problems in which network nodes seek to discover their locations based only on information about which other nodes are within communication range. Solutions to these problems have the potential to improve routing protocols on these networks. Another class of problems PIs consider are geometric coverage problems whose aim is to optimally place sensor nodes with given sensing abilities so as to cover certain target regions. Such coverage problems arise in a variety of sensor network applications such as monitoring bridges, vineyards, and factory floors.