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

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

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.