使用最小连接支配集的自行网路路由

我们在自组网络上施加了一个虚拟主干结构，以支持自组网络内的单播、多播和容错路由。这个虚拟主干与蜂窝网络的有线主干在两个关键方面不同：(a) 它会随着节点的移动而变化，(b) 它不是主要用于路由数据包或流量，而仅用于计算和更新路由。数据包和流量的主要路由仍然是通过最短路径计算得出的；如果必要，虚拟主干可以提供备份路由以应对临时故障。由于虚拟主干的动态特性，我们的方法将路由问题分为两个层面：(a) 查找并更新虚拟主干，(b) 然后查找并更新路由。本文的主要贡献是描述寻找和更新虚拟主干的第一部分的几种替代方案。为了尽可能保持虚拟主干的规模最小，我们使用自组网络拓扑的最小连接支配集(MCDS)的近似值作为虚拟主干。MCDS中的主机维护网络的全局拓扑的本地副本，以及所有节点对之间的最短路径。