基于无线传感器网络的拓扑控制算法

蒋国帅 程 璞

（安徽理工大学电气与信息工程学院，安徽 淮南232001）

基于无线传感器网络的拓扑控制算法

蒋国帅 程 璞

（安徽理工大学电气与信息工程学院，安徽 淮南232001）

拓扑控制在无线传感器网络中具有举足轻重的作用，对于延长生命周期、减小通信干扰、提高通信效率方面具有重要作用。在提出了无线传感器网络拓扑控制的设计目标后，从功率控制和分簇拓扑控制两个方向去举例解释当前两个主流算法的现象。

无线传感器网络；拓扑控制；功率控制；分簇拓扑控制

0 引言

随着德国工业4.0的推进，无线传感器网络也得到了很大的发展，而无线传感器网路在社会各个领域有着无可替代的作用。无线传感器网络是由在监测区域内部署大量的网络节点并且通过无线通行方式通信的网络。但是在无线传感器网络中，节点通常使用电池供电，而一般无线传感器网路都是比较庞大的，并且由于其环境条件使其更换电池相当的不方便，所以，想要充分利用节点有限的能量去完成数据的融合和转发，就必须有一个好的拓扑控制机制来优化网络的拓扑结构，这样可以合理利用能量来达到延长网络的生命周期。

1 无线传感器网络拓扑控制的设计目标

对于无线传感器网络来说，一个良好的网络拓扑结构能够有效的提高路由协议和MAC协议的效率；在保证网络节点的连通性、降低能量的损耗、延长网络生命周期、减小节点间的通信干扰、提高通信效率等方面具有很好的作用，所以，在以下几个方面作为无线传感器网络拓扑结构的设计目标。

1.1 保证监测区域覆盖和网络连通

由于覆盖控制是拓扑控制的基本问题，故网络覆盖质量成为首要考虑的目标。即在保证一定覆盖质量的前提下，也要保证网络的连通性，这样才能既能有效的监测目标区域内的问题和现象，又能保证及时的将监测结果传递给其它网络节点，让其做出处理。

1.2 合理利用能量，延长网络生命周期

由于传感器网路中的节点能量是由电池提供的，能量有限，所以合理利用能量也是保证网路生命周期不可忽视的问题之一。拓扑控制的一个重要目标就是在保证网络连通性和覆盖质量的情况下，尽量合理高效地使用网络能量，延长整个网络的生存时间。

1.3 减小节点间的通信干扰，提高网络通信效率

一般情况下无线传感器网络中节点数目比较多且布置密集，如果每个节点都由其自身最大的功率进行通信时，会加剧节点间的通信干扰，减低通信效率，同时也会造成能量的浪费；同时如果选择太小的发射功率，无法保证网络的连通性质量。所以要在连通性和通信干扰间寻找一个平衡点。

1.4 确定移动节点和骨干节点，便于数据的传输与处理

在无线传感器网络中，数据的转发需要通过移动的节点，而移动节点的确定则是由拓扑控制来选择确定的。而传感器网络中的数据还需要进行融合，数据的融合则需要通过骨干节点发给专门收集数据的节点。所以，对无线传感器网络拓扑结构的优化，是对路由协议、数据融合和数据传输提供很好的基础。

2 无线传感器网路拓扑控制的算法

无线传感器网络的拓扑控制主要研究的方向是在保证一定的网络连通性和覆盖质量的前提下，通过功率控制和簇头节点的选择，适当地去除一些不必要的通信链路，形成一个数据处理和转发的网络结构优化。即无线传感器网路的拓扑控制方式按照研究方向可以分为两类：功率控制和分簇拓扑控制。功率控制就是通过选择合适的发射功率，在保证网络连通性和覆盖质量的前提下，将其能量损耗降到最低。分簇拓扑控制就是利用合理的分簇算法，选择出一些节点成为簇头节点形成一个处理和转发数据的骨干网络，其他非簇头节点可以通过休眠机制来选择关闭节点，来达到节能的目的。

2.1 功率控制算法

无线传感器网络中节点的功率控制是通过对节点发射功率的动态调整和合理设置，在保证网络连通性、覆盖质量的同时，通过一些方法使得整个网路中节点的能量消耗最小，从而延长网络的生命周期。目前，功率控制算法主要有基于邻近图的DRNG算法和DLMST算法，基于方向控制的CBTC算法，基于节点度的LMA算法和LMN算法，与路由协议结合的COMPOW算法等等。

以COMPOW算法为例，其基本的原则就是所有的传感器节点使用相同的发射功率，在保证一定的网络连通性的前提下，使其功率最小。功率的最小化是为了在降低传输过程中能耗的同时提高网络的吞吐量，因此，COMPOW在延长网络生命周期、降低MAC层冲突中占据优势。COMPOW在不同功率层上建立路由表，在每个路由表中同时反映出节点连通性的数据，最终选择在全局连通性相同的条件下选择最低功率。当然，功率的一致性也导致了在节点分布不均匀是会导致所有节点选择过大的发射功率，这是违背设计原则的，同时功率的最小化也使得拓扑结构不具备较好的容错能力。

2.2 分簇拓扑控制算法

分簇拓扑控制算法主要原则就是由簇头节点组成骨干网络，让骨干网络的通信模式始终处于开启状态，而其它的普通节点则进入睡眠状态（当然也不一定），这样就可以有效的降低网络中能量的损耗，延长网络的生命周期。

具体的过程是先将全局网络拓扑划分为相连的簇区域，在每个簇区域内用合理的分簇算法选择簇头，由各个区域的簇头组成骨干网络，其他的节点则是普通节点网络，在通常情况下，骨干网络正常运行，负责执行网路的数据融合和转发的任务，而普通节点网络则处于休眠状态。当然簇头也不是一成不变的，当通信的链路有更好的选择时，分簇算法会重新选择簇头，这样可以始终让整个网络的能耗最低。分簇拓扑控制算法主要有 GAF算法、LEACH算法，TopDisc算法、CLUSTERPOW算法等。

以GAF算法为例，该算法是由Xu等人提出一种基于地理位置的拓扑算法，它将监测区域划分成非常小的簇区域，并在每个区域中利用分簇算法选择产生一个簇头节点，此时只有簇头节点保持活跃状态，保证骨干网络正常运行，而其它普通节点则处于睡眠状态。GAF算法具体有两个执行阶段。第一个阶段就是簇区域的划分，为了保证相邻区域中节点能够正常通信，就必须保证节点发射半径R和区域边长r满足一定的关系即。第二个阶段就是簇区域中簇头的选择，每个节点都处于活跃、被发现和睡眠三个状态。在网络初始阶段，所以节点都处于被发现阶段，通过分簇算法选择出簇头，同时发出信息抑制同一区域内其它节点成为簇头，而其它节点则自动处于睡眠状态，当经过一定的周期时间时，会再次选择簇头选择，以达到链路最优。但是这种侦听占用不少能量也是无法避免的。

2.3 分簇拓扑结构和功率控制相结合的算法

分簇拓扑控制和功率控制是网络拓扑控制两个主流研究方向，当然也有将这两种方式结合起来的算法，比较成功的是Ad hoc网络设计算法（ANDA）。该算法可以用簇头通过功率控制来控制簇的大小，因为在此网络中可以看成其生命周期主要是由簇头的生命周期来决定，毕竟簇头要完成该网络的大部分工作，故能量消耗应该在簇头之间寻找平衡。

Ad hoc网络设计算法的假设条件是普通节点和簇头的位置是已经确定的，并且通信量在节点之间是均匀分布的，而簇头的生命周期是与其初始能量供应成正比，与br∂+cm成反比，其中b、c是常数，r是簇头覆盖区域的半径，∂是路径损耗系数，m是簇内节点数目。为了延长网络生命周期其实就是为了使簇头中的最小生命周期最长。该算法对于静态网络来说可以通过贪婪算法来求得最优解，将节点分配给最长生命周期的簇头，对于所有节点都有此操作，而对于动态网络来说需要一个额重新的分配过程，虽然无法求得最优解，但是其实际性能还是相当不错的。

3 结束语网络拓扑结构对于无线传感器的发展有着不可忽视的作用，虽然大部分的研究还只限于理论研究，运用到实际中的还比较少，这与其技术发展的不成熟息息相关。比如说目前研究的网络拓扑结构都是在理想状况下，而现实中有诸多影响因素都没有考虑进去，导致其实用性很差，另外网络拓扑结构的容错性、可靠性、扩展性、网络延迟等性能研究的还不够深入。但是相信随着网络拓扑结构研究的深入，其技术日益成熟，无线传感器网络必将迎来崭新的未来。

［1］邱天爽，唐洪，等.无线传感器网络协议与体系结构[M].北京：电子工业出版社，2007．

［2］刘林峰，金杉.无线传感器网络的拓扑控制算法综述[J].计算机科学，2008．

［3］徐平平.无线传感器网络[M].北京：电子工业出版社，2013．

［4］张燕．无线传感器网路、原理、设计和应用[M].北京：机械工业出版社，2015．

［责任编辑：田吉捷］