NR: Routing Overhead In Variable Topology Networks - A Theoretical Framework With Practical Implications

该项目的目标是进行严格的分析，从而对可变拓扑网络中路由协议的性能限制和设计原则有基本的了解，特别是与路由开销相关的关键参数。对于拓扑变化频繁的ad-hoc网络，这种开销可能成为可伸缩性和有效容量的重大限制。本研究提出将可变拓扑网络视为具有随机（拓扑）变化的物理系统。最小路由开销与识别系统当前状态（即当前网络拓扑）所需的最小信息量有关。拓扑变化的分布来源于描述单个节点移动的概率分布。因此，路由开销可以与系统的熵率相关。此外，基于与所研究的特定协议类相关的变化子集，对不同类型的路由协议进行了区分。例如，主动协议跟踪任何拓扑变化，而被动协议仅跟踪影响主动参与路由数据包的节点/链路的拓扑变化的子集。与之前在ad-hoc网络路由领域的工作相比，这项工作开发了一种新的分析，而不是模拟，研究可变拓扑网络中的路由开销，并提供了一种通用的处理方法，可以比较不同竞争协议的路由开销。关键的新方法是用信息论的概念来描述网络拓扑变化。

The goal of this project is to develop rigorous analysis leading to fundamental understanding of the performance limits and design principles of routing protocols in variable topology networks, in particular related to the routing overhead as a key parameter of interest. For ad-hoc networks with frequent topology changes, such overhead may become a significant limit on the scalability and effective capacity. This research proposes to treat a variable topology network as a physical system that exhibits random (topology) changes. The minimum routing overhead is related to the minimum amount of information needed to identify the current state of the system (i.e. the current network topology). The distribution of topology changes is derived from the probability distributions describing the individual node mobility. Thus, the routing overhead can be related to the entropy rate of the system. Further, it is differentiated between different types of routing protocols based on the subset of changes that are relevant to the specific class of protocols under study. For example, proactive protocols keep track of any topology change, while reactive protocols track only the subset of the topology changes that affect nodes/links actively participating in routing packets. In contrast to the previous work in the ad-hoc networks routing area, this work develops a new analytic, rather than simulative, study of routing overhead in variable topology networks and, a general treatment that provides reference curves against which the routing overhead of different competing protocols can be compared. The key new approach is the concept of information theoretic characterization of network topology variation.