基于网格划分的骨干网设计

参考文献（Xu et al.，2001）提出了一种用于骨干网构建的、称为地理自适应保真（Geographical Adaptive Fidelity，GAF）的网格划分算法。它假设通过使用GPS，位置信息是可用的，每个节点都知道它相对于其他节点的当前位置。该算法将整个网络区域划分为多个虚拟网格。定义了虚拟网格后，对于任意两个相邻网格，一个网格中的任意节点能够直接与其他网格中的任意节点直接进行通信。也就是说，从路由或广播的角度来看，同一网格中的所有节点是“等价”的。因此，每个网格中的一个代表性节点足以构建一个连通骨干网。

假定r是虚拟网格的长度（边长），R为传输范围。为了确保相邻网格中的任意两个节点能够互相进行通信，需要满足如下关系：r²+（2r）2≤R²。于是，我们得到：r≤R/5。

参考文献（Basagni et al.，2004）对地理自适应保真进行了深入研究。研究成果表明，由GAF构建的骨干网可能会使图处于断开状态。原因在于节点在网格中不是均匀分布的。对于包含一个或多个节点的网格来说，它可能与一个或多个空网格相邻。当网格中所有节点处于激活状态时，两个不相邻非空网格可能处于连接状态。但是，根据GAF计算出的特殊前导序列可能处于非连通状态，这会导致骨干网分离。骨干网分离情况如图2-1所示（图中并未画出UDG的所有边）。其他缺点包括需要用到网格边界参数（网格尺寸）和全局同步。(www.xing528.com)

图2-1 采用GAF时出现的骨干网分离