RUI: Proximity Structures Motivated by Wireless Networks

无线网络和传感器网络的激增加剧了对其基础设施进行智能设计的需求。 对于任何特定的通信突发，最好只涉及一小部分节点和链路，以减少干扰并降低节点功率（电池）需求。 但是，最好在节点之间使用尽可能短的路径。 在网络设计中同时实现这些（和其他）各种运营目标需要深入了解什么是“？”接近结构，？封装网络中相关几何和通信关系的数学模型。 这种理解导致网络设计和路由算法，实现几乎最佳的权衡之间的冲突criterions.This研究网络拓扑结构和算法的无线ad hoc/传感器网络，与构建和处理动态更新的稀疏分布式结构，实现最佳的干扰，路由路径对节点之间，低权重（在最小生成树的权重的常数因子内）和有界度。 最佳干扰拓扑的有效局部构造将与修剪机制相结合，以过滤掉不必要的边缘，并与链路重新分配方法相结合，以减少每个节点的最大程度。 这些方法寻求实现低通信复杂度（恒定到多对数通信回合数）以在大规模网络中可采用。 这项研究工作还探讨了扩展的概念，在无线网络中的安全问题的动机无线定位。

The proliferation of wireless and sensor networks has intensified the need for intelligent design of their infrastructure. For any particular communication burst, it is best to involve only a small collection of nodes and links, in order to reduce interference and to lower node power (battery) demands. However, it is also best to use as short a path between nodes as possible. Simultaneously achieving these (and other) various operational goals in network design requires a deep understanding of what are called ?proximity structures,? mathematical models that encapsulate the relevant geometric and communication relationships in a network. Such understanding leads to network designs and routing algorithms that achieve nearly optimal tradeoffs among the conflicting criteria.This research investigates network topologies and algorithms for wireless ad hoc/sensor networks, with the goal of constructing and handling dynamic updates of sparse distributed structures that achieve optimum interference, spanner paths between pairs of nodes, low weight (within a constant factor of the weight of a minimum spanning tree) and bounded degree. Efficient local constructions of optimal interference topologies will be integrated with pruning mechanisms to filter out unnecessary edges and with link redistribution methods to reduce the maximum degree at each node. These methods seek to achieve low communication complexity (constant to polylogarithmic number of communication rounds) to be employable in large scale networks. This research work also investigates extensions to the concept of wireless localization motivated by security issues in wireless networks.