摘要: 日前small world现象已经被证实大量存在于自然界和人类社会中，比如World Wide Web网络, actor网络, 生物网络等等。small world现象又被称为“six degrees of separation”，来源于著名心理学家Milgram在1967所作的实验。Milgram的small world实验暗示这个世界上的任何两个人都可能被一条短的social acquaintances链所连接。普遍存在的small world现象越来越受到各领域科学家的重视和研究。因为在现实当中我们几乎不可能得到整个small world网络的原始结构数据，我们有必要建立准确的理论模型来模拟现实的small world 网络。早期的理论模型一般侧重在网络的统计属性，而没有涉及到路由方面。为了弥补这方面的不足，Kleinberg提出了一种基于d维toroidal lattice 的理论模型。 在此模型中，每个节点除了跟网格的local 节点相连外，还跟long-range节点以d-harmonic 随机分布方式相连。Kleinberg证明了如果每个节点只用local的路由信息，简单的贪婪算法可以在O( (lg n)^2 )的期望时间内完成任何两点间的路由过程。日前基于Kleinberg理论模型的改进路由算法一般依靠增加local的awareness来提高路由效率。但此方案只能有限度改进路由时间复杂度。据本文作者所知，目前最好的基于small world网络的路由算法只能达到O( (lg n)^(1+1/d) )的时间复杂度。本文拓展了Kleinberg的理论模型，每个节点除了保持原有的local和long-range的连接边外，还增加了两条连接边。对于每个节点而言，新增的两条边以平均随机分布的方式连接到离该节点(lg n)^(2/d) 曼哈顿距离范围内的其它两个节点。本文称新增的这两条边为augmented local links，而称被augmented local links所连接的节点为前节点的augmented local neighbors。基于此理论模型，本文提出了一个能够在O(lg n)的期望时间内完成的路由算法。由于Martel和Nguyen已经证明了Kleinberg的 small world理论模型的直径为O(lg n)，本文的路由时间已经达到了最优复杂度。该算法有效地利用了新增加的两条边来提高可用的local路由信息。 在本文算法中，每个节点在作出路由决策之前，先探索一定距离的augmented local neighborhood，并且从其中选出一个满足一定条件的节点作为中转点，然后把message送到离中转点最近的下一个节点。在整个路由过程中，每个节点不需要保存前节点的路由历史记录。该算法只要求每个节点保持O(1)的degree，以及每个节点存储poly-logarithmic bits的信息量，因此具有良好的扩展性。据本文作者所知，本文应该是第一个在small world模型上提出达到最优路由复杂度并且只要求每个节点存储poly-logarithmic bits信息量的算法。类似于Symphony模型的设计原理，本文的理论成果可应用于大规模分布式网络的结构设计，比如Peer-to-Peer 网络逻辑层的结构设计。由于各连接边是根据随机分布生成，整个网络不易受攻击，因而具有良好的fault tolerance。