无线传感器网络的拓扑控制技术

应满足的性质

　　拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质，以延长网络生命周期，降低网络干扰，提高吞吐率。
　　一般假设结点分布在二维平面上，所有结点都是同构的，都使用无向天线。以有向图建模无线传感器网络，如果结点i的传输功率Pi大于从结点i到结点j需要的传输功率Pij，则结点i到结点j之间有一条有向边。所有结点都以最大功率工作时所生成的拓扑称为UDG图(Unit Disk Graph)。

　　拓扑控制应使网络拓扑满足下列性质中的一个或几个：

　　连通性―为了实现结点间的互相通信，生成的拓扑必须保证连通性，即从任何一个结点都可以发送消息到另外一个结点。连通性是任何拓扑控制算法都必须保证的一个性质。由UDG图的定义可以知道，UDG图的连通性是网络能够提供的最大连通性，因此一般假定UDG图是连通的。所以，任何拓扑控制算法生成的拓扑都是UDG图的子图。

　　对称性―指如果从结点i到结点j有一条边，那么一定存在从结点j到结点i的边。由于非对称链路在目前的MAC协议中没有得到很好的支持，而且非对称链路通信的开销很大，因此一般都要求生成的拓扑中链路是对称的。

　　稀疏性―指生成的拓扑中的边数为O(n)，其中n是结点个数。减少拓扑中的边数可以有效减少网络中的干扰，提高网络的吞吐率。稀疏性还可以简化路由计算。
　　平面性―指生成的拓扑中没有两条边相交。由图论可知，满足平面性一定满足稀疏性。地理路由协议是一种十分适合计算和存储能力有限的无线传感器结点的路由协议，它不需要维护路由表和进行复杂的路由计算，只需要按照一定的规则转发消息。但当底层拓扑不是平面图时，地理路由协议不能保证消息转发的可达性。因此，当结点运行地理路由协议时，要求生成的拓扑必须满足平面性。
　　结点度数有界―指在生成的拓扑中结点的邻居个数小于一个常数d。降低结点的度数可以减少结点转发消息的数量和路由计算的复杂度。
　　Spanner性质―指在生成的拓扑中任何两个结点间的距离小于它们在UDG图中距离的常数倍。

研究方法

　　目前对拓扑控制的研究可以分为两大类。一类是计算几何方法，以某些几何结构为基础构建网络的拓扑，以满足某些性质。另一类是概率分析方法，在结点按照某种概率密度分布情况下，计算使拓扑以大概率满足某些性质时结点所需的最小传输功率和最小邻居个数。

　　1．计算几何方法

　　该方法常使用的几何结构有如下几种：

　　 最小生成树(MST) 网络拓扑是以结点间的欧式距离为度量的最小生成树。结点的传输半径设为与该结点相邻的最长边的长度。以MST为拓扑的网络能保证网络的连通性。由于在分布式环境下构造MST开销巨大，一种折中的方法是结点采用局部MST方法设置传输范围。
　　 GG图(Gabriel Graph) 在传输功率正比传输距离的平方时，GG图是最节能的拓扑。MST是GG图的子图，GG图也满足连通性。
　　 RNG图(Relative Neighbor Graph) 其稀疏程度在MST和GG图之间，连通性也在MST和GG图之间，优于MST，冲突干扰优于GG图，是两者的折中。RNG图易于用分布式算法构造。
　　DT图(Delaunay Triangulation) UDG与DT图的交集称为UDel图(Unit Delaunay Triangulation)。UDel图是稀疏的平面图，适合于地理路由协议、节能、简化路由计算，以及降低干扰，因此十分适合作为无线底层拓扑。
　　Yao Graph 研究人员提出了许多Yao Graph的变种，如在GG图上使用Yao Graph，在Yao Graph上使用GG图等，以减少Yao Graph中的边数并同时保持Spanner性质。
　　θ-Graph 与Yao Graph非常相似。不同之处在于，Yao Graph在每个扇区中选择最近的结点建立链路，而θ-Graph选择在扇区中轴投影最短的结点建立链路。