论文部分内容阅读
在网络互连中,路由发挥了重要的作用。利用它一方面能够找到最优的路径;另一方面能够尽可能减小由路由引起的开销,从而提高路由协议的性能。迄今为止,大量的路由方案已被广泛研究。根据不同的需求,路由方案可以被分成多种类型。根据路由中利用信息的多少,现存的方案主要可以被分成两类,即基于图拓扑的路由和基于地理位置的路由。对于基于图拓扑的路由,它总能保证找到最优路径,但路由表中包含了大量的表项。与基于图拓扑路由中路由表的大小相比,基于地理位置路由的路由表相当的小。然而,后者一般找不到全局最优的路径。本论文旨在现有的路由机制上改进,结合了上述两种路由机制的优点,同时回避了二者的缺点。论文主要贡献如下:提出了一种基于四叉树的最优路径路由机制QOPR-一利用图拓扑路由的思想,它能够保证最优路径。此外,通过使用地理位置信息和四叉树结构,路由表的大小可以被压缩至其信息论的下界。为了保证最优路径且能将路由表尽可能的压缩,文献中已提出了大量的方案。通过利用地理位置信息,我们的理论结果比现存文献中的最好的结果(基于IP的方案)还要好。与其它方案相比,QOPR路由机制有两大优势。一方面,它的编码方案比IP地址更加直观。路由表中的目的节点由四叉树编码,它可以直观的划分、编码节点。另一方面,我们得到的路由表大小优于现存文献中的结果。仿真实验表明,一般情况下,本方案无论在路由表大小还是路由表的构建、查找性能上均优于基于IP的方案。提出了一种QOPR+路由机制——针对QOPR路由机制中,当插入新节点时引起的路由更新的不足,在QOPR路由机制的基础上,提出QOPR+路由机制。通过采用一种新型的proper四叉树-位图混合结构(proper quadtree bitmap hybrid structure,简称pqbh(T))作为路由表,它能够进一步降低更新复杂度,兼顾查找速度和更新性能。此外,本文从理论上证明pqbh(T)也是一个很省空间的数据结构。与QOPR路由机制中路由表的大小只相差了一个很小的常数因子。仿真实验表明,一般情况下,QOPR+路由机制的路由表构建、查找、更新性能均优于QOPR路由机制中的性能,但这是通过牺牲部分路由表大小实现的。