RUI: Proximity Structures Motivated by Wireless Networks

无线和传感器网络的激增加剧了对其基础设施进行智能化设计的需求。对于任何特定的通信突发，最好只涉及一小部分节点和链路，以减少干扰并降低节点功率(电池)需求。但是，最好还是在节点之间使用尽可能短的路径。同时实现这些(和其他)网络设计中的各种运营目标，需要深入理解什么是所谓的邻近结构、？封装网络中相关几何关系和通信关系的数学模型。本文研究了无线自组网/传感器网络的网络拓扑和算法，目的是构建和处理稀疏分布式结构的动态更新，以实现最佳干扰、节点对之间的扳手路径、低权重(在最小生成树权重的恒定因子内)和有界度。最优干扰拓扑的高效局部构造将与剪枝机制相结合以滤除不必要的边，并与链路重分布方法相结合以降低每个节点的最大度。这些方法寻求实现可在大规模网络中使用的低通信复杂性(通信轮数恒定到多对数)。这项研究工作还调查了无线网络中的安全问题对无线定位概念的扩展。

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.