Gabriel图的性质和应用

我们对单位圆盘图（Unit Disk Graph，UDG）中的面路由感兴趣，而不是对平面几何图中的面路由感兴趣。原因在于UDG可用于对无线Ad Hoc和传感器网络建模。一般来说，任意UDG不是平面的。因此，我们需要从UDG派生出一种几何结构，并以局部方式提供一个平面图。目前，路由应用最方便的结构是GG。

Gabriel图最早是由参考文献（Gabriel and Sokal，1969）引入的。当直径为|uv|的圆盘未包含给定点集的其他点时，点u和v可以通过GG中的某个边连接起来。在图4-7a中，虚线圆是GG的禁区，在该禁区中不存在其他点。图4-8所示为由UDG构建的一个Gabriel图。粗边属于GG，而所有边属于UDG。在GG的3D定义中，如果以两个点为直径端点画出的某个球体不包含点集中的其他点，则可以将两个点连接起来。

图4-7 禁区

a）Gabriel图中的禁区 b）Delaunay三角网中的禁区

图4-8 Gabriel图（粗边）和单位圆盘图（所有边）

GG概念可应用于UDG上。假设S是一个平面点集，U（S）是UDG中的一个平面点集，它包含了S中的所有点。假定GG（S）表示由S派生的GG。下面的定理表明GG保持了UDG的连通性。

定理4-1 （Bose et al.，1999）：如果U（S）是连通的，则GG（S）∩U（S）是连通的。(www.xing528.com)

证明：我们将证明这两个图形都包含同一集合S的最小生成树MST（S），因而它们的交集也包含MST（S），从而得出GG（S）∩U（S）是连通的。我们将通过反证法来证明MST（S）⊆GG（S）。如果MST（S）不是GG（S）的子集，则存在某个边PQ∈MST（S），PQ∉GG。由于PQ不在GG中，直径为PQ的圆盘内存在节点W。节点W满足PW＜PQ，QW＜PQ。因为PQ在MST（S）中，所以PW或QW都不在MST中。假定PW∉MST（S）。在MST（S）中，用PW来代替PQ。新的MST（S）边长总数变小，这是一个矛盾。因此，GG（S）包含MST（S），因而是连通的。假定U（S）的半径为R。所有U（S）的边都不会大于R。根据Kruskal算法（Kruskal，1956），在构建MST（S）时，在考虑其他长度大于R的边之前，首先考虑这些边。考虑完连通U（S）中的所有边后，MST（S）包含了所有来自于S的节点，因而已经完成。也就是说，MST（S）⊆U（S）。因此GG（S）∩U（S）是连通的。

定理4-2 （Bose et al.，1999）：Gabriel图是平面图。

证明：反证法。假定Gabriel图不是平面图，则存在两个相交的边UV和PQ。根据UV，PQ∈GG（S），可以推出∠PUQ＜π/2，∠PVQ＜π/2，∠UPV＜π/2，∠UQV＜π/2。这样，四边形UPVQ的角度总和小于2π，这是一个矛盾。

从GG的定义可以看出，它的结构非常简单。为了测试边uv是否属于GG，节点u可以检查其他节点与线段UV中心的距离是否大于|UV|/2。另一种方法是，u可以验证uv与邻近点的夹角是否为锐角。如果是，则该边属于GG，否则它不属于GG。用于检验某个节点所有边是否属于GG的算法，其计算时间复杂性为O（d²），其中d为网络节点的最大度。但是，无线网络通信成本要比计算成本高。如果节点u已经获知自身及其所有邻居的地理位置信息，则在构建GG时不需要其他附加消息。这使得GG变成一种局部方案。同时，它是一种零消息平面图构建方法，一种非常理想的特性。

第2章对相对邻域图（RNG）进行了描述。参考文献（Li et al.，2001）指出，RNG和GG的边数分别受到3n-10和3n-8条件的限制，其中n为网络的节点数。这样，RNG和GG的节点平均度最高为6。事实上，RNG的节点平均度大约为2.5（Hou et al.，2005），而GG的节点平均度大约为3.8（Huang et al.，2004）。RNG每个节点的平均度可以减小到5，如果每边长度是唯一的。假定RNG中某个节点u的度数大于5。必定存在两个邻居v和w，使得∠vuw≤60^o。由于uv≠uw（假定uv>uw），节点w一定位于uv的禁区内，这与uv属于RNG相矛盾。为了确保所有边唯一，分别将（|uv|，min（u，v），max（u，v））看做是主、次、第三键值记录就可以了。

我们简要讨论一下子Delaunay三角网（Delaunay Triangulation，DT）作为GG平面图方案的可能性。如果存在一个圆，其弦为uv，且在内部不包含任何其他节点，则边uv在DT中。或者，DT包含所有三角形uvw，它满足如下条件：通过u、v、w的圆中不包含其他节点（见图4-7）。但是，DT无法通过局部算法构建。原因在于单单依靠节点的邻居信息无法确定任意节点为端点的三角形是否属于DT。如果节点x位于圆内，但位于节点u的通信区外，则u可能不知道x的存在。也就是说，定义中圆的半径是没有限制条件的，于是局部知识不足以支持结论的推导。

从DT的第一个定义，我们可以看出GG⊆DT。假定某个边uv属于RNG。这意味着不存在满足uv＞uw条件的节点w。这样，w不在直径为uv的圆内。也就是说，RNG⊆GG。因此，我们有MST⊆RNG⊆GG⊆DT（Hou et al.，2005）。