Theoretical aspects and algorithms for architectural design and communication in current networks

传感器网络设计和管理中产生的问题所固有的数学结构使它们成为理论计算机科学界的中心，因为它们利用了来自图论、计算几何、设计理论和代数组合学等领域的不同技术。我的目标是在我的专业知识的基础上，回答一些特别和传感器网络领域的新出现的问题：我建议研究和更好地理解几何信息在计算中的潜力。经典的图论算法是为离线模型开发的，对于许多现代应用程序来说，这是不够的，因为我们正在处理巨大的网络，并且我们一次只能访问其中的一些局部部分。越来越明显的是，几何信息对于处理这些设置是有用的。 高连通性是通信网络的一个基本指标，在一些研究工作中，通过在平面图/UDG中添加/删除边来构建具有更高连通性的UDG的平面子图，从而对其进行了攻击。然而，现有的结果并不能完全理解这里的权衡取舍。我想要攻击的中心问题是，对于某些类型的UDG，类似于Gabriel测试或相对邻域图的技术是否可以产生具有更高(2-4)连通性(顶点或边)的平面子图。今天我们知道，对于高于1的连通性，这不可能是没有额外条件的整个UDG类，并且可能需要一些拓扑要求。 定向天线在无线网络中得到了广泛的应用，不仅可以降低能耗和干扰，还可以提高路由效率和安全性。研究了建立互联网络所需的天线数目和传输距离之间的权衡问题。现有的结果只部分解决了拉伸系数的问题。此外，还必须更好地了解各种技术限制要求的影响，例如每个节点允许的天线数量或允许的天线总数。我计划解决其中的一些问题。

The mathematical structure inherent in problems originated in design and administration of sensor networks has made them central to the theoretical computer science community as they utilize different techniques from areas like graph theory, computational geometry, design theory, and algebraic combinatorics. My goal is to build on my expertise and to answer some of the emerging questions in the area of ad-hoc and sensor networks: I propose to study and better understand the potential of geometric information in computation. The classical theory of graph algorithms was developed for offline models and is not sufficient for many modern applications where we are dealing with huge networks and we have only access to some local part of it at a time. It is more and more apparent that geometric information is useful to handle these settings. High connectivity is a fundamental criteria on communication network and it has been attacked in several research works where a planar subgraph of UDG with higher connectivity was build by adding/deleting edges to/from planar graph/UDG. However, existing results do not give complete understanding of tradeoffs here. Central question, which I would like to attack, is whether for some class of UDGs a similar technique as Gabriel Test or Relative Neighborhood Graph can result in a planar subgraph with higher (2-4) connectivity (vertex or edge). Today we know that for higher than 1-connectivity this cannot be the whole class of UDGs without extra conditions, and perhaps some topological requirements are necessary. Directional antennae are widely being used in wireless networks not only for reducing energy consumption and interference, but also for improving routing efficiency and security. The tradeoffs are studied between number of antennae and transmission range necessary to establish connected network. Existing results only partially address the issue of stretch factor. Also the effect of various technology limiting requirements such as allowed number of antennae at each node or allowed total number of antennae have to be better understood. I plan to attack some of these problems.