基于蚁群算法和BP神经网络的信道分配策略的研究*

翟学明，王　佳，李金泽（华北电力大学（保定）控制与计算机工程学院，河北保定071003）



基于蚁群算法和BP神经网络的信道分配策略的研究*

翟学明*，王佳，李金泽
（华北电力大学（保定）控制与计算机工程学院，河北保定071003）

摘要：研究无线传感器网络信道分配策略的主要目标是提高网络吞吐量和容量，减小网络的传输时延，最大限度的利用有限的网络带宽资源。多信道MAC协议的应用，可以有效地提高网络通信的可靠性和吞吐量，以及解决由于信道受干扰而造成的网络瘫痪等问题。根据无线传感器网络多信道的特点提出了一种基于蚁群算法的动态反馈负载均衡信道分配策略。本策略首先应用BP神经网络对信道负载情况进行预测，然后通过基于蚁群算法的负载均衡算法对信道进行筛选，最后利用最大离散化算法进行信道分配。在NS2平台下对所设计的协议进行了仿真实现，并与应用最为广泛的多信道MMAC协议以及SMAC进行了对比分析。根据仿真结果可知，本文设计的MAC协议在网络吞吐量、网络传输时延等性能方面比MMAC协议及SMAC都有了很大程度的提升。可以有效减小网络传输时延，提高网络吞吐量和抗干扰能力。

关键词：无线传感器网络；信道分配机制；蚁群算法；BP神经网络；最大离散化；NS2仿真

项目来源：国家自然科学基金项目（60974125）

目前，无线传感器网络在实际应用中主要采用单信道MAC协议，它简化了协议的实现方式，降低了节点间相互发现的难度，使得组网更加迅速、便利。但是当数据量非常大时，众多节点将会同时对这条信道提出通信申请，造成通信竞争加剧［1］。节点之间干扰严重，并发性强时还可能导致严重的冲突，并影响数据传输的可靠性［2］。此外，无线传感器网络工作在2.4 GHz ISM频段，如果周围存在WiFi等无线网络，它们共用这一频段，无线信道开放共享的特征可能会引起单信道传感网络与这些无线网络之间的相互干扰［3］。

多信道协议可以使无线传感器网络的众多节点利用多个信道进行并行通信，从而大大提高了网络带宽资源的利用率，减少了通信竞争，提高了网络通信的吞吐量。同时，当某一个信道受到干扰时，节点可以使用其他信道进行通信，提高了网络的抗干扰能力［4］。

通过对多信道MAC层的通信协议进行改进来提高网络的服务质量已经成为当前研究的热点［5］。文献［6-8］应用低复杂度的贪心算法实现信道的分配，并从无线信道分配策略以及对网络吞吐量、时延的影响等方面进行了研究。研究结果表明利用贪心算法模型能够能够使信道分配达到局部最优分配的目的。但是当网络中节点数量众多，且节点密度大时，往往不能达到令人满意的效果，网络的QOS会下降的特别明显。其原因在于贪心算法不能达到全局最优分配的目的。文献［9］提出了基于虚拟链路的多信道协议，能够很好的避免信道干扰，但是没有很好的解决时间同步问题。文献［10］提出了一种基于忙音的IABTM（Interference-Aware Busy Tone based Multi-Channel MAC Protocol）协议。该协议使用忙音信道传递控制信息可以很好的解决多信道协议存在的隐终端、暴露终端以及“Deaf⁃ness”等问题，提高了网络的吞吐量。但是这种MAC协议在每次数据传输前，所有的节点都监听同一个控制信道，发送节点和接收节点首先跳转到同一个控制信道协商传输控制信息，以便节点间无干扰通信。由于该协议仅预留了一个控制信道来传递控制信息，节点数目较多且网络中要同时传输数据的节点对较多时，控制信息之间容易发生较为严重的冲突。

基于以上分析，本文提出一种基于BP神经网络与蚁群算法的动态反馈负载均衡信道分配策略。该策略的核心思想为：在数据传输的过程中，首先根据BP神经网络的基本原理，通过反馈得到下一阶段可能不存在干扰的信道。然后应用基于蚁群算法的负载均衡策略对信道进行筛选，将不存在干扰且负载较小的信道序列记录在优先选择列表PCL（Priority Choice Lists）中。然后应用最大离散化的算法从PCL中选择信道进行信道离散化，信道最大离散化完成之后，将信道序列分配给有通信请求的节点对。

1　协议算法

多信道协议的执行过程主要分为信道预测、信道筛选以及信道分配等3个主要过程［11］。

1.1信道预测

在信道预测方面，本文采用BP神经网络可靠性预测机制。信道可靠性预测机制BP神经网络预测模型如图1所示。

图1　信道可靠性预测机制BP神经网络预测模型

以理想因子m、当前信道列表CCL（Current Channel List）、接收信号强度指示的标准差δRSSI作为输入量，以优先选择信道列表PCL、接收信号强度的退化量ΔRSSI以及丢包率的退化量ΔPLR作为输出量。根据神经网络系统的研究成果可知，隐层的节点如果取足够多的数量，单一隐层的神经网络便可以满足逼近非线性函数的精度要求，因此本文只应用了一个隐层。

BP神经网络通过对连接权值的调整完成自我学习的功能。BP神经网络的自我学习过程主要包括信号的前向传递过程和误差的反馈过程［12］，信号前向传递过程如式（1）所示：

式中netj和netk分别表示模型中隐层节点和输出层节点的净输入量，xi和yk分别表示模型的输入和模型的输出，M和N分别表示模型中输入层节点的个数和隐层节点的数量，Wij和Wjk表示模型中输入层、隐层以及输出层之间连接时的权重，Oj表示模型中隐层节点产生的输出，f表示功能函数，f采用sig⁃moid函数：

式（2）中θ表示节点阈值。

网络的误差函数可以用式（3）表示：

式（3）中L表示输出层节点的数量，dk表示期望得到的输出。

本文采用使误差梯度函数的方向下降的方法修正网络中的权值，从而达到误差反馈的目的。输入层和隐层误差反馈的权重设置如下：

式（4）中，μ表示学习速率，0<μ

输出层和隐层误差反馈的权重设置如下：

模型中阈值的修正量如下：

在算法初始化时，预先设定阈值与权重。然后根据输出的接收信号强度的退化量ΔRSSI以及丢包率的退化量ΔPLR的值不断地对阈值和权值进行调整。直到ΔRSSI及ΔPLR值满足要求，或者算法的学习次数超过设定的限定值退出。

经过BP神经网路多次自我学习之后，预测算法预测的信道序列接收信号强度指示的标准差与实际的信道序列接收信号强度指示的标准差的关系如图2所示。

图2　接收信号强度指示标准差的预测值与实际值的关系图

2.2基于蚁群算法的负载均衡

蚁群优化算法ACO（Ant Colony Optimization algorithm）是一种启发式搜索的算法，算法从初始状态开始根据启发条件不断向全局最优的解空间逼近，直到找到全局最优解为止。这里蚁群算法的启发条件就是一种被称为信息素的物质［13］，在本文算法中指的是单一信道的负载占总负载的比重。

2.2.1负载均衡对无线传感网络性能的影响

负载均衡问题对于无线传感器网络信道分配来说就是使数据业务均衡的分配给各个信道。负载均衡对于无线传感器网络的总吞吐量、平均时延的性能都十分关键。尤其是对于总吞吐量性的作用更加明显。原因在于，如果网络负载不能均衡分布时，负载过大信道会导致数据业务的积压，而负载较小的信道会产生信道在传输完数据业务后空闲的现象，从而影响无线传感网络的总吞吐量［14］。

2.2.2基于蚁群算法的负载均衡算法

本文设计了低开销的跨MAC层与网络层设计的蚁群系统优化算法。跨MAC层与网络层算法设计的思想为：使数据链路层、网络层之间进行信息的融合与交流，建立一定的联系，协同地工作，去除冗余操作，更有效地分配网络资源、提高网络性能优化的效率。从链路层统计获得的接收信号质量指示RSSI，负载度等参数与路径延迟、跳数等参数一并作为路由选择的依据，根据由以上参数定义的路由代价函数作为低开销的蚁群算法的启发因子。为了减小开支算法在路由层应用了三种全新的机制：在路由发现阶段，采用新的广播机制，每个节点向它的邻居节点广播一个控制信息，但是只有其中的一个节点再次广播这个消息；在路由维护阶段，使用数据包只更新活跃路径的信息，从而进一步降低开销；在路由恢复阶段，采用深度搜索的方法来修复路径，该算法在断开链路两端的节点之间尝试用深度搜索发现新路径。

在MAC层，本文设计了基于蚁群算法的负载均衡信道分配策略。算法中信息素更新分为迭代最优更新和局部信息素更新。搜索解空间的搜索路径选择的方法包括按先验规律和按概率选择两种。本算法的目的是：在某一时刻，当网路中的数据业务集到来之时，利用蚁群系统算法找到一个使得负载最均衡分布的信道分配序列。信道负载分配是否均衡可以用信道负载分布的标准差来表示：标准差B为负载均衡度。式（7）中j表示可用信道的总量，xj表示信道j的负载比，q表示信道的平均负载比，B表示信道负载比的标准差。B越小表示信道负载的波动越小，负载分布越均衡。算法优先为低负载的信道更新信道负载比。而随着整体负载的上升，更新机制逐步放开负载比更新的限制条件，让更多相对负载比较高的信道加入到算法调度中；当系统负载下降，则又会在全局更新中关闭个别负载比较高的信道的调度。从而达到整体负载均衡的目的。

①迭代更新公式

在本协议中i（r，s）表示信道rs上的信息素含量，即信道rs的负载量占总负载量的比值，Δi(r,s)表示信道上的负载占总负载总量比值的增量，ρ表示迭代最优更新负载比的挥发因子，（1-ρ）表示跟新负载比的残留因子。通过改变ρ和K的取值调整信道负载增长的速度。σ(r,s)表示每次迭代产生最优信道序列负载的标准差，IOP（Iterative Optimal Path）表示迭代最优路径。

②局部更新公式ϑ表示局部更新负载比的挥发系数，(0)表示负载比的初值，ϑ的引入可以减少被选择过的信道上的负载比，有利于新路径的发现。

③路径转移规则公式q0(0q0时，按照概率对信道进行搜索。当q≤q0时按照先验规律选择信道。

④转移概率计算公式

式（12）中，Pkij(t)表示第k蚂蚁在t时刻选择信道ij的概率，allowedk表示所有与i节点有边相连的节点集合，即第k只蚂蚁在节点i处可选择的节点集合，如果节点在该集合之中，则其概率按负载比的浓度进行计算；反之，其概率为0。转移概率公式表示某一次迭代的第k只蚂蚁按照该信道负载占总负载的比例计算出的，如果该信道的负载占总负载的比重越大，则其转移的概率也越大。

基于蚁群算法的无线传感器网路多信道负载均衡调度算法的算法描述如表1所示。

表1　算法的负载均衡调度算法

2.3信道最大离散化

信道的最大离散化，将优先选择列表中的信道以公式（13）的方法进行最大离散化并分为4组：

G(i)=[i+0H,i+1H,i+kH] i=1,2,3,4 k=3（13）式（13）中，k表示满足不等式i+kH≤16的最大值。每组至少包括n个信道，如式（14）所示。

为了保证频段最大离散化能够最大限度的分开每组信道。第j组的信道表示如式（15）所示：

例如，某一时刻PCL中的信道依次为：1、3、4、6、8、9、11、12、14，则经过最大离散化算法得到的信道分配序列为：3、9、6、12、1、8、14、4、11。信道最大离散化完成。当有节点对要进行数据传输时，则从最大离散化之后的信道列表中根据贪心着色算法选择信道分配给节点对。

3　实验与仿真分析

为了对本文设计的MAC协议（在下文中记为MDMAC）的性能进行验证和评估，在NS2仿真平台上分别对本文提出的MDMAC协议、SMAC协议以及MMAC协议从网络总吞吐量、平均时延、丢包率等方面进行仿真测试和协议性能分析，从而验证本文提出的MDMAC协议的高效性。考虑到成本的因素，本协议适用于单收发器的节点，因此在仿真过程中，把节点设置为半双工工作模式。

3.1仿真配置

在NS2仿真平台中需要定义无线节点的参数，如表2所示。网络的仿真拓扑结构图如图3所示。

表2　无线节点参数设置

图3　网络拓扑结构图

3.2性能分析

图4能够看出，当包到达速率处于较低的水平时，MDMAC与SMAC及MMAC的吞吐量接近，这是由于网络负载较小时单信道协议可以满足网络的传输要求，不会发生严重的数据冲突；而当包到达速率高于某个临界值时，MDMAC协议的吞吐量明显高于SMAC协议及MMAC协议，而且随着包到达速率的不断增加，MDMAC协议的吞吐量增大的比SMAC协议及MMAC协议越来越明显。这是因为MDMAC协议应用蚁群算法实现负载的均衡分布，以及基于BP神经网络的信道预测机制降低了信道相互干扰的几率，使无线信道的频谱资源得到了充分的利用，从而提升了无线网络的吞吐量性能。

图5对比了MDMAC协议、SMAC协议以及MMAC协议在包到达速率发生变化的情况下网络平均时延的性能。从图中可以看出，当网络负载较低时，即包到达率较小时，三种MAC协议的网络平均时延都较小。但是多信道的MDMAC以及MMAC协议的平均时延要比SMAC的平均时延高，这是因为当网络负载较小时，单信道SMAC协议能够满足网络传输的需求，并且与MDMAC协议及MMAC协议相比不存在信道协商与切换的时延。而当网络负载增大时，包到达率超过某个特定值时，三种MAC协议的网络平均时延均增大。但是MDMAC协议平均时延的增长速度明显比SMAC协议及MMAC协议小。这是由于SMAC协议及MMAC协议均采用退避机制，网络负载较高时网络冲突节点的退避时间增大。而MDMAC协议能够根据信道的质量动态的进行信道切换，应用BP神经网络算法预测信道质量，并通过最大离散化的算法降低信道间的干扰以及冲突的发生概率。与本文设计的MDMAC协议相比，MMAC协议可能会持续的竞争信道直到竞争失败，这样就会造成网络的平均时延大大升高。由此可见本文设计的MDMAC协议的网络平均时延性能高于SMAC协议及MMAC协议。

图4　静态网络中吞吐量与包到达速率的关系

图5　静态网络中分组平均延迟与包到达速率的关系

通过对网络节点数据包发送速率进行调节，测试得到的丢包率结果如图6所示。由图可见网络节点发送速率较快即网络负载较重时，由于信道中的数据包量大而造成较大的碰撞和丢包率，导致了较为严重的网络拥塞。尤其是在使用单信道的SMAC协议中，丢包率的增加更为明显。而MDMAC协议及MMAC协议由于采用了多信道机制，有效降低了网络拥塞程度，降低了网络中的数据包碰撞概率。与MMAC协议相比，本文设计的MDMAC协议采用了基于BP神经网路的最大离散化信道分配策略，最大限度的减少了信道相互干扰的可能性以及数据碰撞的概率。综合来看，MDMAC协议比目前应用最为广泛的单信道的SMAC协议及典型的多信道MMAC协议具有更小的丢包率。

图6　不同发送速率下丢包率

4　结束语

在实际应用中，网络环境可能是复杂多变的。网络拓扑结构、节点间的干扰以及外界干扰如WiFi

信号的干扰都可能时刻在发生着变化。而上述问题在本文设计的MDMAC协议中都没有进行深入的探讨与分析研究。所以，为使本文提出的MD⁃MAC协议在网络拓扑结构发生快速变化及外界干扰环境复杂等情况下，网络性能仍然具有较高的可靠性，仍然存在很多问题需要研究与分析。

参考文献：

［1］任昊翔，郭达伟，邵凝宁.一种新型的无竞争的基于TDMA的MAC协议［J］.传感技术学报，2013，26（1）：89-94.

［2］张招亮，陈海明，黄庭培.无线传感器网络中一种抗无线局域网干扰的信道分配机制［J］.计算机学报，2012，35（1）：504-517.

［3］Zhang X，Shin K G. Enabling Coexistence of Heterogeneous Wire⁃ less Systems：Case for ZigBee and WiFi［C］//Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Network⁃ingand Computing（MobiHoc）. 2011：231-154.

［4］张龙妹，史浩山，陆伟. DTFMM：一种适应于WMSNs的多信道MAC协议［J］.传感技术学报，2011，24（3）：452-457

［5］张娜，陈曙.无线局域网MAC层协作通信改进方案［J］.传感技术学报，2012，25（2）：283-288

［6］王丰亮，吕卫锋，诸彤宇.基于贪心策略的多信道数据广播调度算法［J］.计算机工程，2011，12：179-181

［7］Wu X，Srikant R. Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks［C］//Proc IEEE Info⁃com，2006：595-605.

［8］秦绍华.无线传感器网络多信道技术的研究［D］.山东大学，2014：23-36.

［9］Juan L，HaiBo L，RenFa L. VL-MAC：Virtual Link Based Multichannel MAC Scheme in WSN［C］//Information Technology：New Generations，2009. ITNG’09. Sixth International Conference on. IEEE，2009：1600-1601.

［10］李蓥.无线自组织网MAC层协议关键技术的研究［D］.上海：上海交通大学，2007：41-66.

［11］Lei Hongjiang，Gao Chao，Guo Yongcai. Survey of Multi-Channel MAC Protocols for IEEE 802.11-Based Wireless Mesh Networks ［J］. The Journal of China Universities of Posts and Telecommuni⁃cations，2011（2）：33-44.

［12］孔玉静，侯鑫，华尔天.基于BP神经网络的无线传感器网络路由协议的研究［J］.传感技术学报，2013，26（2）：246-251.

［13］Dorigo M，Maniezzo V，Colorni A. The Ant System：Optimization by a Colony of Cooperatingagents［J］. IEEE Transactions on Sys⁃tems，Man and Cybernetics-PartB，1996，26（1）：29-41.

［14］王璟，王利利，游金阔.基于动态配置等价多路径技术的无线传感器网络负载均衡算法研究［J］.传感技术学报，2015，28 （5）：752-756.

翟学明（1967-），男，博士，副教授，主要从事电力系统自动化在线监测技术、绝缘监测技术、计算机网络及其应用的研究，zxm3165@126.com；

王佳（1989-），男，硕士研究生，2013年就读于华北电力大学（保定）控制与计算机科学学院计算机系，主要研究方向为无线传感器网络，1069695617@qq.com。

Research on Channel Allocation Strategy Based on Ant Colony Algorithm and BP Neural Network*

ZHAI Xueming*，WANG Jia，LI Jinze
（School of Control and Computer Engineering，North China Electric Power University，Baoding Hebei 071003，China）

Abstract：The main purpose of studying channel allocation strategy of wireless sensor network is to improve net⁃work throughput and capacity，reduce transmission delay of the network，and use the limited network bandwidth re⁃sources efficiently. Application of multi-channel MAC protocol can solve the problem of network paralysis caused by channel interference. Due to the characteristics of the wireless sensor network，this article proposed a dynam⁃icfeedback load balancing channel allocation strategy based onant colony algorithm. This strategy applied BP neural network to predict the channels’load，then filtered the channels by using the load-balancing algorithm based on ant colony，finally allocated the channel sequences by using the maximum discrete channel allocation algorithm. Final⁃ly，this protocol wassimulated and implemented on NS2 platform，and it was also compared with the MMAC protocol and the SMAC protocol. According to the simulation，the MAC protocol we proposed in this paper performed better than the MMAC protocol and the SMAC protocol in terms of network throughput，network delay to a large degree of improvement. It can effectively reduce the network delay，increase network throughput and enhance the anti-jam⁃mingcapability.

Key words：wireless senor network；multi-channeldistribution mechanism；ant colony algorithm；BP neural net⁃work；maximum discrete；NS2 simulation

doi：EEACC：1295；6150P；723010.3969/j.issn.1004-1699.2016.03.024

收稿日期：2015-08-22修改日期：2015-12-03

中图分类号：TP393

文献标识码：A

文章编号：1004-1699（2016）03-0445-06