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

 

　　计算机网络的拓扑结构是引用拓扑学中研究与大小，形状无关的点，线关系的方法。把网络中的计算机和通信设备抽象为一个点，把传输介质抽象为一条线，由点和线组成的几何图形就是计算机网络的拓扑结构。网络的拓扑结构反映出网中各实体的结构关系，是建设计算机网络的步，是实现各种网络协议的基础，它对网络的性能，系统的可靠性与通信费用都有重大影响。指连接各结点的形式与方法。 把网络中的工作站和服务器等网络单元抽象为"点". 网络中的电缆等抽象为"线". 影响网络性能、系统可靠性、通信费用 ① 总线拓扑结构 是将网络中的所有设备通过相应的硬件接口直接连接到公共总线上，结点之间按广播方式通信，一个结点发出的信息，总线上的其它结点均可"收听"到。 优点：结构简单、布线容易、可靠性较高，易于扩充，是局域网常采用的拓扑结构。缺点：所有的数据都需经过总线传送，总线成为整个网络的瓶颈；出现故障诊断较为困难。着名的总线拓扑结构是以太网（Ethernet）。

　　网状型拓扑结构：将多个子网或多个网络连接起来构成网际拓扑结构。在一个子网中，集线器、中继器将多个设备连接起来，而桥接器、路由器及网关则将子网连接起来。根据组网硬件不同，主要有三种网际拓扑：网状网：在一个大的区域内，用无线电通信链路连接一个大型网络时，网状网是的拓扑结构。通过路由器与路由器相连，可让网络选择一条快的路径传送数据。主干网：通过桥接器与路由器把不同的子网或LAN连接起来形成单个总线或环型拓扑结构，这种网通常采用光纤做主干线。星状相连网：利用一些叫做超级集线器的设备将网络连接起来，由于星型结构的特点，网络中任一处的故障都可容易查找并修复。

　　网状拓扑的优点：（1） 网络可靠性高，一般通信子网中任意两个节点交换机之间，存在着两条或两条以上的通信路径，这样，当一条路径发生故障时，还可以通过另一条路径把信息送至节点交换机。（2） 网络可组建成各种形状，采用多种通信信道，多种传输速率。（3） 网内节点共享资源容易。（4） 可改善线路的信息流量分配。（5） 可选择路径，传输延迟小。网状拓扑的缺点：（1） 控制复杂，软件复杂。2） 线路费用高，不易扩充。网状拓扑结构一般用于Internet骨干网上，使用路由算法来计算发送数据的路径。

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

　　连通性-为了实现结点间的互相通信，生成的拓扑必须保证连通性，即从任何一个结点都可以发送消息到另外一个结点。连通性是任何拓扑控制算法都必须保证的一个性质。由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选择在扇区中轴投影短的结点建立链路。

　　2.概率分析方法

　　发展成熟的随机图理论不适合无线传感器网络。事实上，随机图假设任意两个结点间的边的存在与否是互相独立的，这一假设不符合无线传感器网络的特点。为解决这个问题，研究人员提出了几何随机图理论。在该理论中，结点按照某种概率密度分布在d维区域R中。研究人员研究了这种结点分布下的某些性质，诸如：到近邻居的长链路，欧式生成树中长边的长度，MST的总开销。近，研究人员使用几何随机图理论研究无线ad hoc网络的某些基本的性质，如连通性。

　　另外两种理论是连续渗流（continuum percolation）和占位理论（occupancy theory）。在连续渗流理论中，结点以Poisson密度λ分布在二维平面中，如果结点间距离小于r则两个结点相连。已经证明，对于λ>0,至多以大概率存在一个无限阶的组件（由连通的结点组成的集合称为组件，组件的阶是结点集合中结点的个数）。但是，只存在一个无限阶的组件不能保证网络的连通性。事实上，可能存在许多（无限多）结点不属于这个大组件，这样就导致不连通的网络通信图。因此，连通性与属于大组件的结点占所有结点的比例相关，这个比例又与渗流概率相关。但是，目前还没有关于渗流概率的显式表达式。由于连续渗流理论的模型与ad hoc的网络模型相吻合，因此连续渗流理论被用于分析ad hoc网络的连通性。

　　在占位理论中，假设n个球独立地放入C个格子中。球放入格子中的放法由描述格子的某些属性的随机变量确定。占位理论的目标是确定当n和C趋近无穷时这些变量的概率分布（极限概率分布）。占位理论可以用于分析ad hoc网络的连通性，可以抽象为把区域R分割成相同大小的rd个小区域（格子），确定在这种情况下每个格子中至少有一个结点（球）的概率。

　　概率方法研究的重要的问题是临界传输范围（CTR）问题，即结点都是同构的，传输范围相同，使网络连通的传输范围是多少。研究这个问题的原因在于在无线传感器网络中廉价的无线通信部件不可能动态调整传输范围。在无线传感器网络中，只能把所有结点的传输范围设为相同的值。减少功耗、增加网络容量的惟一办法是把传输范围设为保持网络连通的值。适合解决CTR问题的概率理论是几何随机图理论。因为临界传输范围就是MST中的长边，从长MST边的概率分布中可以推导出CTR的概率解。但几何随机图理论只适用于密集的ad hoc网络。因为理论假设放置结点的空间是固定的，当结点个数趋于无穷时，结点的密度也趋于无穷。但在实际情况中，网络的密度不可能很大。事实上，一个结点传输时，在它通信范围内的其他结点必须保持沉默。如果结点密度非常大，当一个结点传输时，许多结点都必须保持沉默，将降低整个网络的容量。

　　研究人员还用占位理论分析稀疏ad hoc网络中保证连通性的临界传输范围问题。

　　近年来拓扑控制技术已成为研究的热点，目前在这个研究领域中还存在着许多问题。首先，用于建模无线传感器网络的模型过于理想化。为了得到更符合实际的量化结果，需要使用更真实的模型。其次，结点的分布假设过于理想化。一般的研究都假定结点是均匀分布的。虽然在某些情况下这种假设是合理的，但是在大多数情况下这样的假设是过于理想化的。，安放无线传感器的区域假设过于理想化。一般假设安放无线传感器的区域是平坦的二维平面，没有考虑地形的因素。