基于拥塞的改进遗传算法WSNs拓扑控制*

马亚军，王宏亮，国林勇

（辽宁石油化工大学计算机与通信工程学院，抚顺113001）

·微机网络与通信·

基于拥塞的改进遗传算法WSNs拓扑控制*

马亚军，王宏亮，国林勇

（辽宁石油化工大学计算机与通信工程学院，抚顺113001）

WSNs分层路由树是计算几何方法拓扑控制的一种，结合真实约束条件在广播构建的最小生成树（MST）基础上优化分层路由树，有利于提高网络吞吐量、降低网络干扰、节约结点资源。从网络负荷均衡思想出发，研究了降低网络结构带来的拥塞几率问题。提出基于拥塞重构分层路由树的方法，并结合网络拓扑控制需满足的连通性、稀疏性、平面性和结点度数有界性改进遗传算法实现分层路由树重构的优化仿真，验证了研究的有效性。

WSNs网络；MST结构；拥塞；拓扑控制；遗传算法；优化仿真

1 引言

拓扑控制技术是无线传感器网络中最重要的技术之一。在由无线传感器网络生成的网络拓扑中存在大量的边，从而导致网络拓扑信息量大、路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感器网络中的拓扑控制问题，在维持拓扑的某些全局性质如连通性、稀疏性、平面性、结点度数有界等的前提下，减少拓扑中的边数并避免边的交叉和通信环路的形成。

目前对拓扑控制的研究可以分为两大类：计算几何方法和概率分析方法[1]。其中，层次路由算法作为计算几何方法的一种，构建MST拓扑保证了网络的连通性，并有效规避了通信边的交叉问题，成为WSNs研究的一个热点，并取得了一定的进展[2]。文献[3-5]就是在节点布置完成以后，通过拓扑控制为汇聚节点（Sink）与目的节点之间的所有节点设置单调递增的层次号，从而把整个网络从源节点（第1层）开始分成了多个层次，并最终建立了一个分层路由树，在此分层路由树的基础上解决网络拥塞和能耗优化问题。

但是MST拓扑过于理想化，以结点间欧式距离为度量的最小生成树仅仅保证了网络的连通性、平面性以及距离的优化，为了得到更符合实际的量化结果，则需要使用更真实的模型。以负荷均衡为例，MST在网络拓扑结构上就无法兼顾结构本身对应用的支持，从而无法有效抑制拥塞问题的发生。因此，需引进约束条件进一步优化MST构建的符合应用实际的分层路由树。基于遗传算法的改进就是其中一个方向。

2 WSNs网络模型与广播模型

2.1 WSNs网络模型假定

假设WSNs网络为层次型结构，由多个簇组成，每一个簇都由一个簇头节点和若干普通节点构成。簇头节点形成一个处理并转发数据的骨干网，将数据融合结果通过多跳路由发送给基站（Sink），如图1。

基于T-MAC协议做如下问题假定：WSNs所有节点随机映射在二维平面上，节点位置固定；所有无线传感器节点通信半径相同。依据WSNs通信原理，由Sink节点发起网络广播通过拓扑控制形成分层路由树。

图1 WSNS网络模式

规定 WSNs每个节点具有 id，parent，level，energy，t等多个属性。Sink节点的parent为尽可能大的一个规模值（如9000）；t为以本节点为根的子树的节点个数；level和t的初值为0。在节点布置完成后，由Sink节点发出广播信息。各节点energy值初始定义均为电池满电量E；其它节点随着距离Sink节点的远近具有不同的level值（增量加1），具体的level值通过网络广播获得；parent值在网络广播时与level同时获得。记录消息“单跳”传播的父节点，即信息接收节点的parent值为信息发送节点的id，t则记录本节点id作为parent值的所有子树中节点的总个数，表现为节点负荷，在广播结束后赋值。

2.2 WSNs广播模型

在节点随机布置完成以后，通过拓扑控制由Sink节点开始广播消息，见图2。

图2 网络广播模型

接收到广播消息的节点将发送节点的level值加1作为自己的level值，同时，记录发送节点的id作为本节点的parent值。当节点再次收到不同的发送节点传来的消息时，如果新节点的level值小于原来发送节点的level值，则替换掉原来发送节点的数据，使用新的发送节点的level及parent，反之，将新的发送节点的消息抛弃。

3 网络拓扑拥塞问题分析及拓扑控制依据

3.1 网络拓扑拥塞问题分析

对于一棵数据汇集树,假设其深度为N，给定层次 i，i＜N。从i+1到N的所有节点，若总共有M个节点,则这M个节点产生的数据流必然全部通过第i层。假设节点x 为根的子树中的节点个数为 tx，第i层上有n个节点，其t值分别为且最大时，之间的差值最小，负荷最均衡，拥塞问题产生的几率最小。

其中，ti表j示第i层节点的t值。

根据公式（1）的拥塞度权值定义，网络拥塞度权值的最小生成树定义为：

由此网络中的每棵子树都能计算出各自的拥塞度权值，继而求得全网络的拥塞度权值

3.2 拓扑控制优化依据分析

网络拓扑结合拥塞抑制的优化，即在初始广播建立的MST基础上在不改变层次关系前提下基于拥塞度权值利用智能算法进一步实施优化，实现拥塞均衡控制基础上的MST分层路由树重构。问题的实现上表现为结合广播优化分层路由树求解网络拓扑的以拥塞度为权值的最小生成树问题。

拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质，以延长网络生命周期，降低网络干扰，提高吞吐率[7]。

这里我们考查以下几个性质，作为优化的依据：

1.连通性。为了实现结点间的互相通信，生成的拓扑必须保证连通性，即从任何一个结点都可以发送消息到另外一个结点。连通性是任何拓扑控制算法都必须保证的一个性质。

2.稀疏性。指生成的拓扑中的边数为o(n)，其中n是结点个数。减少拓扑中的边数可以有效减少网络中的干扰，提高网络的吞吐率，稀疏性还可以简化路由计算。

3.平面性。指生成的拓扑中没有两条边相交。由图论可知，满足平面性一定满足稀疏性。

4.结点度数有界。指在生成的拓扑中结点的邻居个数小于一个常数d。降低结点的度数可以减少结点转发消息的数量和路由计算的复杂度。

4 基于拥塞利用改进遗传算法实施网络拓扑控制

遗传算法利用简单的编码技术和繁殖机制来表现复杂的对象，从而解决非常困难的问题（如全局最优化问题）。它不受搜索空间的限制性假设约束，不必要求诸如连续性、可导性、单峰性等假设，以及其固有的并行性，遗传算法目前已经在最优化、机器学习和并行计算等领域取得了越来越广泛的应用[8]。

4.1 遗传算法适应度函数设计

依据前文对网络拥塞问题的分析，取网络拥塞度权值为进化判据：

4.2 遗传编码数据结构设计

WSNs网络拓扑表述采用邻接表描述，见图3。此种数据结构便于划分网络拓扑生成树子树以及遍历记录节点总负荷值（t+1），并于每代进化完成后给节点属性t赋值。

遗传基因表述则采用邻接矩阵描述，见图4。便于解决平面性问题，即生成的拓扑中不能有两条边相交，分层路由思想很好地解决了这个问题，继而将约束进化过程中相同level值节点间的边舍去。

图3 WSN网络的拓扑及节点间的关系的邻接表描述

图4 以邻接矩阵表示基因示意图

结点度数有界控制：设定节点度数上界（假定为每个节点可以同时与3个以下的节点通信），同时建立节点负荷伴随矩阵，记录优化过程中生成树的各个节点直接负荷，节点度数上界结合负荷伴随矩阵作为遗传进化约束条件[9]。

4.3 遗传进化效率改进

4.3.1 遗传算法问题域空间的收缩

广播形成的MST作为初始种群的基因之一，其他基因在MST层次特性约束下随机产生，WSNs拓扑布局要求网络节点全连通，且满足稀疏性和平面性。依据图论思想，由图论可知n个节点网络全连通至少拥有n+1条边，故对于少于n+1条边的生成网络直接舍弃；依据分层路由思想，相同level值的节点间边舍去；对符合上述条件的基因从Sink节点进行深度优先全连通检测。

4.3.2 交叉、变异过程中环路问题破圈改进

针对不同类型的环路，有以下三种不同的破图方法：

（1）环路类型1及破圈方法

在Level层次大于3的前提下，某一节点同时收到上一层次Level中的两个节点的数据传输，而这两个节点又同时拥有同一个父节点，则形成了至少横跨三层Level类似于“菱形”的环路。环路类型如图5所示。

图5 环路类型1

类型1破圈方法：

在level（0）层，z节点作为x,y节点的共同子节点，图中出现环路，每条边上的权值代表着此路径的能量消耗值。如果在不考虑能量消耗的前提下，可以删掉x,y到z节点之间的任意一条边。但在实际情况下，能量消耗是必须要考虑的条件之一。根据能耗最小的原则，应该删掉能耗较大的传输线路，即图中权值较大的边。综述应删掉y节点到z节点之间的边。破圈后如图6所示。

图6 类型1破圈

（2）环路类型2及破圈方法

同样在Level层次大于3的前提下，在通过广播确定层次后，选取某一个节点，它与同一层次的另一节点建立了数据传输关系，而两个节点的父节点同时拥有同一父节点，形成了至少横跨三层Level类似于“五边形”的环路。环路类型2如图7所示。

图7 环路类型2

类型2破圈方法：

在通过跳数得到各节点的层次后，分析发现处在同一Level层次的俩个节点之间建立了数据流连接。而在实际应用中，这种同层次的连接会造成网络数据的重复收集，进而造成了能源浪费。在遵从能耗最小的原则下，为了使无线路由拥有更长久的使用寿命，应当采取适当措施。相比于第一类环路类型，该类型处理方法比较简单，只需要删除同一层次中两个节点间的连接，即可打破环路。破圈后如图8所示。

图8 类型2破圈

（3）环路类型3及破圈方法

同样在Level层次大于3的前提下，在通过广播确定层次后，选取某一个节点。此节点拥有两个不同Level层次的父节点，而两个父节点之间又为父子关系，进而形成了一种类似于“三角形”的环路。环路类型3如图9所示。

图9 类型2破圈

类型3破圈方法：

图10 类型3破圈

假设图中sink为层次最低的节点，x和y同为它的两个不同Level层次的子节点，与此同时x和y又同为父子关系。可以得知x节点与sink节点之间的跳数至少为1，y节点与sink节点的跳数至少为2。在与sink节点的连接中，y节点通过x节点建立的连接与y节点直接建立的连接相比,y节点通过x节点建立的连接层次更深且跳数更多。在实际情况中因为跳数过多，容易造成数据丢失的情况，且加大了x节点传感器的能源消耗，所以我们在该情况下应该选择破跳数最多，且层次最深的一条边。

在此种情况下，遵从路径最短、能耗最小的条件，应当破除跳数最多且层次最深的一条边，即破除x节点与y节点间的网络数据连接。破圈后如图10所示。

根据上述3个基本破圈方法，可在最大化保证网络数据汇集树能耗最小、路径最短、数据传输最高效化的前提下，合理的去边破除环路。

5 系统仿真

改进的遗传算法设计按照MVC架构开发，采用多线程、多目标并行优化策略，即网络拥塞度和路由优化过程在广播数据的基础上并行进行，仿真测试采用35节点网络随机布局，结点度数上界设为3。模拟节点布置完成，遗传种群基因规模设定为20，交叉因子取0.6，变异因子取0.05，进化代数为从50代至250进行了测试，优化结果以绘图和数值的形式显示在主窗口上，见图11，图中红色的路径为最优数据传输路径。

图11 遗传算法优化仿真

仿真实验结果见表1，结果显示网络拥塞度（为便于考查拥塞与负荷均衡关系，设计输出为拥塞度而非拥塞度权值）随着进化代数递增而优化（越大，负荷越均衡），表明网络各节点的负荷越均衡拥塞概率越小，拥塞问题得到很好解决，全网能量消耗从4E降低到2E，同时保证了数据汇集能耗的优化。

表1 部分仿真测试数据结果

6 结束语

仿真结果验证了基于拥塞的WSNs拓扑控制研究的可行性，以及改进遗传算法解决方案的有效性，达到了WSNs数据汇集一定程度的优化效果。

但是受限于所采用数学模型的局限性，以及遗传算法收敛早熟的处置还不够完善，算法效率仍有待于进一步的研究提高，以期获更接近于最优解的实际应用验证。

[1]楼俐,范建华,徐诚.基于局部稳定性测度的战术移动自组织网络拓扑优化抗干扰技术研究 [J].兵工学报,2016,37(9):1662-1669.Lou Li,Fan Jianhua,Xu Cheng.Research of Anti-interference Technology Based on the Measure for Local Stability of Tactical Mobile Self-organizing Network Topology Optimization[J].Acta Armamentarii 2016,37(9):1662-166

[2]Andrew S.Tanenbaum.Computer Networks,5th Edition[M].Pearson,2010,10.

[3]Sergiou C,Vassiliou V,Paphitis A.Hierarchical tree alternative path(HTAP)Algorithm for congestion control in wireless sensor networks[J].Ad Hoc Networks,2013,11(1):257-272.

[4]Sergiou C,Vassiliou V,Paphitis A.Congestion control in wirelesssensor networks through dynamic alternative path selection[J].Computer Networks,2014,75(A):226-238.

[5]陈文广,牛玉刚,邹媛媛.基于改进AODV路由协议的WSNs拥塞控制和能耗均衡策略[J].计算机工程与科学,2016,38(9):1776-1783.Chen Wenguan,Niu Yugang,Zou Yuanyuan.WSNs Congestion Control and Energy Consumption Balancing Strategy Based on Improved AODV Routing Protocol[J].Computer Engineering and Science,2016,38(9):1776-1783.

[6]石为人,唐云建,王燕霞.基于拥塞控制的无线传感器网络数据汇集树生成算法[J].自动化学报,2010,36(6):823-828.Shi Weiren,Tang Yunjian,Wang Yanxia.Wireless Sensor Network Data Collection Tree Generation Algorithm Based on Congestion Control[J].Acta Automatica Sinical,2010,36(6):823-828.

[7]樊庆亮,武卫东,王光兴.传感器网络MAC协议能量有效性的研究与MATLAB的仿真[J].沈阳航空工业学院学报,2006,23(2).Fan Qingliang,Wu Weidong,Wang Guangxing.Study on Energy Effectiveness of Sensor Network MAC Protocol and Simulation of MATLAB[J].Journal of Shenyang Institute of Aeronautical Engineering,2006,23(2).

[8]David E.Goldberg.Genetic Algorithms in Search,Optimization,and Machine Learning[M].Addison-Wesley Professional,1989,1.

[9]陈柯君,王宏亮,李东生.利用遗传算法实现基于多目标约束的网络规划[J].微处理机,2015,36(2):24-28.Chen Kejun,Wang Hongliang,Li Dongsheng.Using Genetic Algorithm for Network Planning Based on Multi-objective Restriction[J].Microprocessors,2015,36(2):24-28.

Improved Genetic Algorithm WSNs Topology Control Based on Congestion

Ma Yajun，Wang Hongliang，Guo Linyong
(School of Computer and Communication Enginering,Liaoning Shihua University,Fushun 113001,China)

WSNs hierarchical routing tree is a kind of topological control of geometric methods,optimizing hierarchical routing tree based on the minimum spanning tree (MST)of broadcast construction combining real constraints is helpful to improve network throughput,reduces network interference,and saves nodes resources.This paper studies the problem that reducing the congestion probability caused by network structure,and proposes a method of rebuilding hierarchical routing tree based on congestion.Then the optimal simulation is realized by combining the connectivity,sparseness,flatness and node degree of network topology control to improve the genetic algorithm,and the validity of the research is verified.

WSNs;MST;Congestion;Topological control;Genetic algorithm;Optimization simulation

10.3969/j.issn.1002-2279.2017.05.010

TP311.52

A

1002-2279-（2017）05-0035-05

辽宁省教育厅资助科研项目（L2014153）；辽宁省教育科学“十二五”规划项目（JG14DB229）

马亚军（1995—），男，江苏省如皋市人，本科生，主研方向：软件工程。

王宏亮（1971—），男，辽宁省抚顺市人，副教授，主研方向：计算机集成制造，软件工程。