基于布谷鸟搜索的模糊PID拥塞控制方法

石 优,林 琳,吴 岩

(江苏大学 计算机科学与通信工程学院,江苏 镇江 212013)

0 概述

当前无线传感器网络(Wireless Sensor Networks,WSNs)技术发展迅速,该技术因具有设备组建方式灵活、网络强度较高等特性得到广泛应用,然而其大规模应用容易造成网络拥塞等问题[1]。无线传感器网络节点经串联后以“携带-发送”的方式传输数据,各节点均具有自主收集、接收和发送数据的能力,极大提高了网络传输数据量。此外,由于无线传感器网络部署规模庞大、节点数量多、数据采集和转发无固定时间限制,导致网络节点可能会在某个时间点瞬间接收大量数据,这进一步增大了网络传输数据量[2],因此对网络吞吐量有较高要求[3]。当数据接收速率大于数据发送速率时,节点内消息队列会迅速堆积形成网络拥塞。严重的网络拥塞会对无线传感器网络数据传输造成很大影响。发生网络拥塞后,因为节点内的数据来不及发送出去,其他数据也无法进入节点内的消息队列,所以消息被不断丢弃和滞后,造成大量数据丢失、网络延时加大以及网络吞吐量缩减,从而降低网络服务质量,甚至会引起网络瘫痪,而网络节点长期处于高负荷的满队列状态也会大幅缩短其使用寿命[4]。因此,有效解决网络拥塞问题至关重要。

由于无线传感器网络数据采集无固定时间和数据量大小限制,即数据采集具有不规律性,加上网络节点持续移动造成网络拓扑不断变化,导致网络节点拥塞情况更复杂,需要一种高效且自适应能力强的拥塞控制方案来解决上述问题。文献[5]将比例-积分-微分(Proportional-Integral-Derivative,PID)控制器引入网络拥塞控制问题,利用PID控制器适应性强、操作简单和效率高等特性,有效缩短消息队列长度,缓解了网络拥塞。但是PID控制器自身具有诸多缺陷。研究人员提出多种PID控制器改进方案,但是其应用于无线传感器网络时仍存在不足。文献[6]将信用分配小脑模型与PID控制器相结合提高计量效果,但由于未考虑PID控制器的参数无法与输入量保持同步变化,因此其后期数据可信度较低。文献[7]提出一种改进PID控制器,在不影响传输链路质量的前提下,提高了控制效果并降低能耗,但该PID控制器精度不高。文献[8]将元启发灰狼优化算法与PID控制器相结合,利用元启发算法优秀的全局搜索能力提高了PID控制器自适应能力,但忽略其后期会陷入局部最优的精度较低问题。文献[9]将非线性自回归移动平均算法引入PID控制过程,并实现其参数自整定,但是该算法收敛速度较慢。因此,在无线传感器网络的拥塞控制中引入PID控制器时,需考虑PID控制器自适应能力不高所导致计算精度较低的问题。

针对上述网络拥塞控制方法计算精度不高的问题,本文结合网络拥塞特征和模糊PID控制器与元启发算法的特点,提出一种基于布谷鸟搜索(Cuckoo Search,CS)算法的模糊PID网络拥塞控制方法。利用PID控制器的快速收敛能力调控无线传感器网络拥塞程度,使用模糊控制算法整定PID控制器参数,通过优化其自适应能力提高计算精度,并采用布谷鸟搜索算法优化模糊PID控制器所得丢包率进一步提升计算精度。

1 布谷鸟模糊PID控制模型

将传统PID控制器引入无线传感器网络的拥塞控制中,可计算消息队列的瞬时队列长度与实时丢包率。由于网络环境和数据收集具有不规律性,因此要求PID控制器具有较高精度。本文将模糊控制与传统PID控制器相结合实现其参数自整定,从而提高其优化精度。同时,重新计算实时丢包率,并在此基础上,引入全局搜索性能优异且收敛速度较快的元启发布谷鸟搜索算法,进一步优化实时丢包率的计算精度,并通过丢包率控制瞬时队列长度以实现拥塞控制。根据上述思路,本文模型设计分为2个步骤:1)将无线传感器网络节点的队列长度作为控制对象设计模糊PID控制器(FPID);2)采用布谷鸟搜索算法优化调整FPID(CFPID)。

1.1 WSNs中模糊PID网络拥塞控制器设计

传统PID控制算法是一种将主动队列管理系统的各类算法转化为控制器形式的经典控制算法,该算法可使控制对象的瞬时值保持接近期望值[10]。本文将PID控制器引入无线传感器网络,以队列长度为控制对象,经过比例(P)、积分(I)和微分(D)调整,得到消息丢包率p[11],通过丢包率限制队列长度从而对拥塞程度进行控制。本文PID控制系统结构如图1所示,其中⊗表示多个控制步骤在此处结合同时控制下一步操作。

图1 PID控制系统结构Fig.1 PID control system structure

在PID控制系统结构中,yd为期望队列长度,y为瞬时队列长度,k时刻瞬时队列长度记为y(k),p为消息丢包率,队列长度的控制偏差变量为e,在k时刻e的瞬时值表达式如下:

e(k)=yd-y(k)

(1)

以期望队列长度yd作为PID控制器的输入、丢包率p作为PID控制器的输出对瞬时队列长度进行控制,PID控制器的控制规则表示如下:

(2)

(3)

1.2 基于模糊PID的拥塞控制器设计

通过模糊控制算法对PID控制器进行参数整定,可优化其自适应能力并提高拥塞控制计算精度。以下对基于模糊PID的拥塞控制器(FPID)设计原理和模糊规则进行介绍。

1.2.1 FPID控制器设计原理

在传统PID控制器设计中,比例、积分和微分参数均固定,自适应调节能力较差,导致控制器精度较低[12]。本文利用模糊控制技术对PID控制器参数进行调整。模糊控制技术是根据模糊规则将控制对象进行模糊化、模糊推理和反模糊化,其无需精确的被控对象数学模型,能较好控制并优化非线性变化与实时变化的复杂情况[13]。本文设计一种基于模糊PID的FRID控制器,FRID控制系统结构如图2所示,该系统设计过程为:将模糊控制引入PID控制器并对其进行参数寻优,通过模糊规则和模糊推理获得PID参数增量,并对初始参数进行加权调整得到新的PID参数,从而实现PID参数的自整定优化。

图2 FPID控制系统结构Fig.2 FPID control system structure

在FPID控制系统结构中,e为网络节点内队列长度的偏差量,ec为偏差变化率,Δkp、Δki、Δkd分别为由模糊推理所得比例、积分、微分参数增量。将队列长度偏差量e和偏差变化率ec作为模糊控制器的输入,参数增量Δkp、Δki、Δkd作为模糊控制器的输出,得到最终的FPID整定参数形式如下:

kp=kp0+Δkp

(4)

ki=ki0+Δki

(5)

kd=kd0+Δkd

(6)

其中,kp0、ki0、kd0分别为比例、积分、微分参数初始值。

1.2.2 FPID控制器的模糊规则

在参数整定过程中,需考虑参数之间的关联。将e、ec、Δkp、Δki、Δkd的模糊论域分别设置为[-3,3]、[-3,3]、[-3,3]、[-0.3,0.3]、[-0.3,0.3],并将输入变量和输出变量分为{NB(负大)、NM(负中)、NS(负小)、Z(零)、PS(正小)、PM(正中)、PB(正大)}7个等级。利用模糊控制器量化因子进行PID控制器参数整定的关键是确定系统的稳定边界[14]。当队列长度的控制偏差量逐渐减小时,PID参数增益会随之减小,系统逐步稳定,确保最大偏差在稳定区域内,并通过模糊校正让系统自动收敛。设置量化因子ke=0.5、kec=1以及对应的比例因子kΔp=1、kΔi=1、kΔd=1[15]。

对参数增量Δkp、Δki、Δkd具体要求如下:

1)若网络节点中消息队列长度偏差量绝对值|e|为大(e取正大或者负大),则Δkp为正数,即增大kp,以提高调节响应速度;为防止出现较大的超调量,通常设置Δki=0用于限制积分;为防止队列长度偏差量e的瞬间变化导致微分饱和并超出控制范围,Δkd应取较小值。

2)若|e|和|ec|为中等大小(e和ec取正中或者负中),则Δki和Δkd取适中值,使系统具有较小的超调量。

3)若|e|较小(e取正小、负小或者零),则Δkp、Δki取正数,即kp、ki的值增加,以保证系统具有良好的稳态性。

根据上述要求,本文结合使用三角形隶属度函数和Sigmoid型隶属度函数以提高控制效果。

三角形隶属度函数的解析函数形式为:

(7)

Sigmoid型隶属度函数的解析函数形式为:

(8)

将上述两种函数结合使用后,输入和输出变量的隶属度函数曲线如图3～图6所示,表1为FPID模糊规则。

图3 ec的隶属度函数曲线Fig.3 Degree of membership function curve of ec

图4 Δkp的隶属度函数曲线Fig.4 Degree of membership function curve of Δkp

图5 Δki的隶属度函数曲线Fig.5 Degree of membership function curve of Δki

图6 Δkd的隶属度函数曲线Fig.6 Degree of membership function curve of Δkd

表1 FPID模糊规则Table 1 FPID fuzzy rule

1.2.3 反模糊化

根据上述模糊规则,输入队列长度偏差量e和偏差变化率ec后得到的输出变量为模糊变量,需通过反模糊化得到准确值。反模糊化的方法主要包括面积中心法[16]、最大隶属度法和面积积分法[17]。本文采用面积中心法求出参数增量Δkp、Δki、Δkd的隶属度,计算公式如下:

μ(Δkp)=min{μNB(e),μNB(ec)}

(9)

μ(Δki)=min{μNB(e),μNB(ec)}

(10)

μ(Δkd)=min{μNB(e),μNB(ec)}

(11)

经过模糊规则调整后,根据队列长度偏差量e和偏差变化率ec的测量值可求得参数增量Δkp、Δki、Δkd,计算公式如下:

(12)

(13)

(14)

其中,μpj表示j时刻μ(Δkp)的值,Δkpj表示j时刻Δkp的值,μij表示j时刻μ(Δki)的值,Δkij表示j时刻Δki的值,μdj表示j时刻μ(Δkd)的值,Δkdj表示j时刻Δkd的值。将计算所得参数增量Δkp、Δki、Δkd代入式(4)～式(6)得到经过模糊控制更新后的PID控制器参数,即FPID控制器最终参数,再将其代入式(2)中,计算得到更新后的丢包率p。

1.3 布谷鸟搜索算法对FPID的优化调整

FPID控制器相较传统PID控制器精度有所提高,但其精度仍有提升空间。由于通过FPID控制器计算得到的丢包率趋近最优解,却并非最优解[18],因此可利用布谷鸟搜索算法良好的寻优能力对丢包率再进行优化,得到丢包率准确值,从而更精准地控制队列长度。

自然界中布谷鸟不筑巢,而是寻找其他鸟类的巢穴产卵,让其他鸟类作为宿主帮助其孵化繁衍[19],宿主有一定概率能发现布谷鸟的蛋,然后宿主会选择清除此蛋或者放弃巢穴[20]。布谷鸟搜索算法正是模拟布谷鸟上述特殊孵化繁衍方式提出的一种高效元启发式优化算法[21],该算法满足如下规则:1)优质的宿主巢将被传递到下一代;2)宿主有固定概率pa∈[0,1]发现布谷鸟的蛋并清除此蛋或放弃巢穴;3)每只布谷鸟每次只生1个蛋,并放置到随机选择的宿主巢中且宿主巢数量固定。

基于上述规则,为得到最佳的消息丢包率,以FPID模型中消息丢包率p为目标对象,建立基于布谷鸟搜索的模糊PID控制器模型(CFPID),其结构如图7所示。

图7 CFPID控制器模型结构Fig.7 CFPID controller model structure

消息丢包率p随着参数增量Δkp、Δki、Δkd的变化而改变,其表达式记为p(k)。将p(k)作为布谷鸟搜索的目标函数,以莱维飞行路径为搜索路径,通过不断迭代更新,计算出PID参数变化时消息丢包率p(k)的最大值。布谷鸟搜索路径公式更新如下:

(15)

(16)

布谷鸟搜索算法的具体步骤如下:

(17)

2)计算p(k)在各时间点的值,利用Levy(s,λ)对时间点进行更新,计算时间点的目标函数值r并与pa进行对比,若r>pa,则记录r为当前最优值时间点,同时更新鸟巢时间点,否则时间点不变。

3)若满足最大迭代次数,则继续下一步,否则返回步骤2。

4)输出全局最优解,选择最佳丢包率。

布谷鸟搜索算法的伪代码如下:

输入Δkp,Δki,Δkd,M,N

输出pa

1.While (迭代次数m

2.生成N个随机鸟巢位置k0,i(i=1,2,…,N)

3.计算初始巢的目标函数值p(k0,i)

4.Levy-flights寻找新巢位置kx,j(i=1,2,…,N)

5.计算新巢目标函数值p(kx,j)

6.If(p(kx,j)>pa)then

7.pa=p(kx,j)

8.End If

9.保留最好的pa解以及解的位置

10.m←M+1

11.End While

在布谷鸟搜索算法中,最大迭代计算次数为M,由于其中无嵌套循环,因此每次迭代计算最优解的计算复杂度不超过O(M),最大种群规模为N,算法的空间复杂度为O(N)。

2 实验结果与分析

本文在PID控制器的基础上增加模糊控制器和布谷鸟搜索算法,构建出基于布谷鸟搜索的模糊PID拥塞控制方法。将本文提出的CFPID方法与传统PID方法、IBLUE方法[21]3种控制方法在无线传感器网络拥塞控制时的队列长度、丢包率和吞吐量进行对比,以验证本文方法的可行性。实验采用MATLAB R2018a软件,具体参数设置如表2所示。

表2 实验参数设置Table 2 Experimental parameter setting

2.1 队列长度对比

将网络节点数量设置为100,图8为采用CFPID方法、PID方法和IBLUE方法所得节点内消息队列长度随传输时间的变化。消息队列长度直接反映消息队列的传输流畅性,如果该长度超过期望值,则说明发生拥塞,需要进行丢包调整,但是队列长度太短又会导致网络资源利用度较低,因此,需将队列长度保持在期望值附近。可以看出,当数据传输开始时,3种控制方法的消息队列长度均迅速增加,随后超过期望值从而引发网络拥塞。在感应到网络拥塞后,控制机制立刻开始调节队列长度。其中:PID和IBLUE方法均在队列长度达到最高点后才启动控制机制,且将队列长度收敛到期望值的速度较慢;CFPID方法采用比PID方法、IBLUE方法更快的收敛速度和更小的震荡幅度将队列长度控制到期望值,表现出更好的控制性能。

图8 网络节点数量为100时3种方法所得队列长度随传输时间的变化Fig.8 The change of queue length obtained by three methods with transmission time when the number of network nodes is 100

为观测复杂场景中CFPID方法的控制性能,将网络节点数量从100调整为200,增加了整体网络的数据传输负荷以及单个节点的工作量,再次对比采用CFPID方法、PID方法和IBLUE方法所得节点内消息队列长度随传输时间的变化,结果如图9所示。可以看出:当节点数量增加后,数据传输消息量和网络节点的工作负荷大幅增加,3种控制方法得到的节点内消息队列长度曲线均出现明显震荡,单位时间内单个节点待传输数据包数量增多,主要体现在震荡幅值增大和收敛时间增加。其中:PID方法所得消息队列长度曲线震荡幅度最大;IBLUE方法的收敛速度变慢,位于CFPID和PID方法之后;CFPID方法所得消息队列长度曲线震荡幅度小于PID和IBLUE方法,且收敛速度最快,说明其在复杂场景中控制能力仍较强。

图9 网络节点数量为200时3种方法所得队列长度随传输时间的变化Fig.9 The change of queue length obtained by three methods with transmission time when the number of network nodes is 200

2.2 丢包率对比

当网络节点分布密度增大时,网络中数据总量会提高,节点内消息队列中待传输数据包增多,从而造成队列长度增加。当队列长度超过期望值时,会加剧网络拥塞,此时需进行丢包操作,即以一定的消息丢包率丢弃掉节点内部分数据包来控制队列长度,丢包率随队列长度的变化而改变,并将队列长度控制为接近期望值。而丢包率的变化会使消息队列长度不断变化,导致网络出现波动,网络不稳定会间接影响整体网络工作状态。因此,丢包率的收敛速度和稳定性决定网络性能。

在本文实验中,将初始节点数量设置为100,图10为CFPID方法、PID方法和IBLUE方法控制下节点丢包率随传输时间的变化。可以看出,随着传输时间的增加,当消息队列大幅增长时,CFPID方法较PID方法和IBLUE方法控制更迅速,能采用最大丢包率限制队列长度进一步增加,有效抑制了网络拥塞的加重,且经过少量震荡后以最快速度找到平衡点,仅需小幅调整就能让队列长度维持在相对稳定的状态。

图10 网络节点数量为100时3种方法控制下丢包率随传输时间的变化Fig.10 The change of packet loss rate with transmission time under the control of three methods when the number of network nodes is 100

为观测复杂场景中节点内消息丢包率的收敛速度和稳定性,将网络节点数量增加到200,网络整体数据量和各网络节点的待传输数据包均增加,再次对比CFPID方法、PID方法和IBLUE方法控制下节点丢包率随传输时间的变化,结果如图11所示。可以看出:随着网络节点数量和整体数据量的增加,3种方法控制下的丢包率均出现不同程度的震荡;PID方法控制下丢包率震荡幅度最大;IBLUE方法控制下丢包率收敛速度明显变慢,使得其收敛周期明显增长;CFPID方法控制下的丢包率能在适度震荡后保持较快的收敛速度,说明其在复杂场景中具有较好的控制能力,且自适应调节能力较强。

图11 网络节点数量为200时3种方法控制下丢包率随传输时间的变化Fig.11 The change of packet loss rate with transmission time under the control of three methods when the number of network nodes is 200

2.3 吞吐量对比

增加节点数量可间接增大网络传输的消息数量。图12为CFPID方法、PID方法和IBLUE方法控制下网络吞吐量随节点数量的变化。吞吐量是评价网络性能的指标,受硬件设备计算性能的影响,吞吐量大小变化不会过于明显。由图12可以看出:随着节点数量的增加,网络传输的消息数量增大,且节点间数据传输时间缩短,造成吞吐量增大;当节点数量增加时,3种方法控制下网络吞吐量都呈现出不同程度的增大;当节点数量较少时,CFPID方法控制下网络吞吐量最大,且随着节点数量的增长,IBLUE和PID方法控制下网络吞吐量的增幅低于CFPID方法,说明CFPID方法在后期具有较强的抗干扰性,在复杂场景下具备较好的自适应调节性能。

图12 3种方法控制下网络吞吐量随节点数量的变化Fig.12 The change of network throughput with the number of nodes under the control of three methods

3 结束语

本文针对无线传感器网络拥塞控制方法计算精度较低的问题,将模糊控制、PID控制器和布谷鸟搜索算法相结合,提出一种新的网络拥塞控制方法。使用PID控制器计算丢包率并控制节点的队列长度,利用模糊控制调整PID参数来提高计算精度,同时给出相应的模糊规则,并采用布谷鸟搜索算法进一步提高丢包率的准确性。实验结果表明,该方法较PID、IBLUE等传统控制方法所得网络吞吐量更高。后续将融合更多元启发式优化算法并优化PID控制器模糊规则,以进一步提高布谷鸟搜索算法的计算速率。