基于快速排序算法的模块化多电平换流器电容电压均衡策略*

王坤，刘开培，张志轩，李威，秦亮

(1. 武汉大学 电气工程学院，武汉 430072； 2. 南京南瑞集团公司(国网电力科学研究院)，南京 210003)

0 引 言

基于电压源型换流器的高压直流输电技术(Voltage Source Converter-High Voltage Direct Current, VSC-HVDC)可以将分布式能源以经济、环保的方式并入电网[1-2]。目前在高压大功率领域，VSC-HVDC中常用的是模块化多电平换流器(Modular Multilevel Converter，MMC)[3]。MMC结构上高度模块化，易于扩展到不同的电压和功率等级，避免了IGBT的直接串联。同时，MMC具有开关频率低、输出波形好、故障保护能力强等优势，成为中高压领域的研究热点[4-5]。

MMC中作为储能元件的电容分布于子模块中，彼此独立，电容的充放电时间、损耗和参数的不同会造成子模块电容电压的差异，使模块电容电压之间出现不平衡，从而危害换流器的正常运行[6]。因此在MMC运行过程中，需要采取适当的子模块电容电压均衡策略来保证系统的正常运行[7-8]。

国内外学者对MMC电容均压策略进行了大量详实的研究并取得了丰硕的成果。目前，主要有电容电压排序法和通过附加控制器输出调制波补偿值两种方法实现电容电压的均衡。文献[9]提出了一种基于排序算法的电容电压均衡策略，适用于阶梯波调制技术，原理简单，效果优异，但是排序计算量将随着模块数的增多而增加。文献[10]在文献[9]的基础上引入了子模块最大电压偏差量，避免了同一模块不必要的反复投切，大大减少了开关次数，但是该方法对偏差允许值的选择较为敏感。文献[11]基于文献[12]中的质因子分解法提出一种优化的混合排序法，引入希尔排序算法降低排序次数，减少仿真时间，但是由于分组排序处理，排序精度和均压效果都有所下降。文献[13-14]基于载波移相SPWM调制提出通过附加控制器输出调制波补偿值，对每个子模块的调制波进行调节以实现电容电压均衡。通过上述分析，传统均衡策略在模块数较多时占据大量的计算资源，将会降低系统的运行速度甚至动态响应特性，对硬件要求较高[15]。而现有的改进策略为达到降低计算量的目的，不同程度地牺牲了部分电压均衡效果。

首先根据MMC拓扑分析模块电压不均衡的原因，为了减少电压均衡策略的计算量，改善均衡策略性能，以传统电容电压排序法为基础，提出一种基于快速排序算法的电容电压均衡策略。该策略能够大幅降低排序次数，提高运行速度，维持电压平衡效果不变，且不会对系统的外特性产生影响。最后，通过DSP控制器TMS320F28335及PSCAD/EMTDC中搭建的仿真模型，验证了所提出的均衡控制策略的正确性和有效性。

1 MMC拓扑和工作原理

MMC每相有两个桥臂，每个桥臂由一个电感L和N个完全相同的子模块(Sub-module，SM)串联组成，如图1所示。直流侧中性点为O，正负直流母线间的直流电压为Vd，从上下桥臂的结合点输出交流电压。

图1 MMC拓扑结构

子模块由两个IGBT管开关器件TU、TL和一个直流电容C组成，可以实现四象限运行，在正常工作情况下，TU和TL处于互补工作状态，交替开通和关断。子模块有三种工作状态，分别称为投入、切除和闭锁。MMC正常工作时，子模块应当处于投入或者切除状态，子模块输出电压uo在电容电压VC和0之间变化。为了保证直流电压恒定和系统稳定运行，桥臂中处于投入状态的子模块数应当保持一致。

可以看出，MMC中能量分布在各个子模块悬浮电容中，能够减小直流侧故障时的电容冲击电流，提高系统故障保护能力，但是由于任意时刻桥臂子模块处于投入和切除状态并不一致，电容冲放电时间以及器件参数等差异将会造成子模块电容电压不平衡，因此需要采取电容电压均衡策略保障系统稳定运行。电容电压的均衡控制策略受制于采用的调制控制策略，对于不同的调制策略，相应的电压均衡策略也就不同。

2 MMC调制

MMC调制方式有很多，主要分为两类。一类是基于较高开关频率的PWM调制，如载波移相PWM、载波层叠PWM等，在同一电平处反复斩波，通过高频的开关动作以减小输出波形的谐波含量，但是PWM调制会带来较大的器件损耗，并不适用于模块数较多的场景。另一类是低频的阶梯波调制技术，主要有空间矢量调制(Space Vector Modulation, SVM)、最近电平逼近调制(Nearest Level Modulation, NLM)等。SVM所需的电压矢量和开关状态随着电平数的增多呈几何级数增长，算法的实现变得非常困难，因此在MMC中基本不使用SVM。NLM实现简单，效果优异，特别适用于模块数较多的场景，在实际工程中得到了广泛应用，其基本思想是利用阶梯波逼近正弦调制波，随着电平数的增加，阶梯波越来越接近调制波形。以A相为例，具体过程如图2所示。

图2 最近电平逼近调制

Fig.2 Nearest level approximation modulation

根据换流站级控制输出的调制波瞬时值uam，除以模块电压的额定值VC，取最近整数，得到上、下桥臂投入的模块数na1和na2，最后根据电压均衡控制选取相应的模块投入。其中，na1和na2满足:

(1)

式中N桥臂子模块数量，Round是取最近整数函数，上、下桥臂投入的子模块总数是恒定值N，这样可以维持直流电压恒定，保证系统正常稳定运行。根据投入的子模块数和采用的模块电容电压均衡策略触发子模块，可以在控制输出交流电压的同时实现桥臂各模块的电压平衡。

3 基于快速排序算法的电容电压均衡策略

由前文分析可知，MMC子模块投切状态的不一致和器件参数的离散性，将会导致正常工作时同一桥臂的子模块电容电压之间存在差异，因此实现模块电压均衡是MMC稳定运行的必要条件。利用MMC调制自由度多的特点，将电容电压均衡策略和调制策略结合，在实现调制的同时实现电压均衡。工程上主流的调制策略是最近电平逼近调制，通过对模块电压大小排序选择触发实现均衡。随着模块数的增加，电容电压排序将占据大量的计算资源，合理高效的排序算法显得尤为重要。

3.1 快速排序算法基本原理

在实际工程中，无论是软件还是硬件均有足够的存储空间满足空间复杂度的需求，因此，基于时间复杂度分析，采用高效、快捷的排序算法将会降低实际工程控制器的设计难度和硬件要求。

传统的冒泡排序算法简单、稳定、可靠，适用于各种场景。主要思想是交换排序，相邻两个元素依次进行比较，按照从大到小或从小到大的顺序进行交换。以n个元素序列为例，第一趟交换次数为n-1，第二趟交换次数为n-2，并以此类推，我们可以得到冒泡算法的交换次数S，时间复杂度为O(n2)。

(2)

Tony Hoare在1962年首次提出了快速排序算法[16-17]，在过去50多年里，对快速排序方法的研究表明，快速排序算法至今仍然是流传久远的最实用的排序算法。以排序元素A[low,…,high]为例，快速排序最简单的形式概况如下：通过简单的划分算法使得原先A[low]中的元素占据其正确的顺序位置A[w]，并且所有小于或等于A[w]的元素所处的位置为A[low,…,w-1]，而所有大于A[w]的元素所处的位置为A[w+1,…,high]。子数组A[low,…,w-1]和A[w+1,…,high]按照以上过程进行递归，从而产生整个排序数组。以排序8个子模块为例，假设8个子模块的电压大小排序为[4,6,3,1,8,7,2,5]，则具体的快速排序过程如图3所示。

可以看出，快速排序算法基于比较、划分，采用分治技术，首先将模块电压将子模块根据电压大小分成若干大小不同的模块组，再通过递归分别对每一个模块组进行排序，最后将每组排序结果合并，实现每相桥臂的模块电压排序。

3.2 快速排序平均时间复杂度分析

为了简便起见，假定输入数据是互不相同的，注意算法的性能与输入数据值无关，有关系的是它们之间的相对次序。由于这个原因可以不失一般性地假定进行排序的元素是前n个正整数1,2,…,n。进一步假定元素的每个排序出现是等可能的，这一点确保了在数组中的每个数以同样可能作为第一个元素，并被选为主元，也就是说，数组中的任意一个元素被选为主元的概率为1/n。设C(n)表示对大小为n的输入数据算法所做的平均比较次数，从假设中可以知道，所有的元素是互不相同的，并且成为主元的概率是相同的，这样算法的平均耗费可以如下方法计算得到。

观察图3的第1次，第2次和第5次调用，以此类比大小为n个元素的排序过程，这三次分别耗费了n-1，C(w-1)和C(n-w)次比较，因此总的比较次数为：

(3)

由于：

(4)

对式(3)进行简化处理，可得:

(5)

令D(n)=C(n)/(n+1)，得：

(6)

解得:

≈ 1.44log2n

(7)

故可以得到快速排序的时间复杂度为:

C(n)=(n+1)D(n)≈1.44nlog2n

(8)

3.3 基于快速排序算法的电容电压均衡策略

以最近电平逼近调制为基础，引入快速排序算法，根据电流方向选择模块触发，形成基于快速排序算法的电容电压均衡策略，具体过程如图4所示。

首先利用快速排序算法桥臂子模块电压大小进行比较、划分，得到桥臂模块的有序排列，过程如图3所示，通过调制波和模块电压额定值得到当前时刻投入模块数量n。判断电流i的方向，若桥臂电流是给子模块电容充电，则将桥臂中子模块电压最低的n个子模块投入运行，其余子模块切除；若桥臂电流方向为放电方向，则将上、下桥臂中子模块电压最高的n个子模块投入运行，其他的子模块均切除。该策略可以迅速使桥臂各子模块电压趋于一致，进入均衡状态。

图4 快速排序过程

均衡策略的核心环节是有序电压序列的生成和触发模块的选择，相比于传统冒泡排序，快速排序算法不改变有序电压序列的准确性，进而保证模块触发机制和电压平衡效果不变，同时能够大幅提升模块电压的排序效率。实际工程中随着MMC-HVDC电压和功率等级要求的提高，模块数不断增加(最新投入运行的厦门柔性直流输电工程单个桥臂子模块数多达216个)，传统冒泡排序算法交换次数和时间复杂度将按照几何倍数提高，占用大量计算资源，导致系统运行速度下降，控制器负担加重。当MMC-HVDC处于高频运行时，排序运算带来的延时将无法满足控制系统的要求，甚至影响控制系统的动态响应特性。基于以上分析，快速排序算法时间复杂度低，排序效率高，能够节省大量计算资源，改善MMC均衡控制策略的性能。随着子模块数量的增加，基于快速排序算法的电容电压均衡策略在排序效率和计算量上的优势愈加明显，进一步可以提高控制系统的动态响应特性。

4 仿真验证

4.1 算法时间复杂度验证

在Matlab中对算法进行随机实验，对传统冒泡排序和快速排序算法的比较次数进行测量，排序元素个数分别为100、200、300、400，取5 000次测量的平均值为实验结果，并和利用3.2节所推导的公式计算的理论值曲线进行对比分析，如图5所示。可以看出，排序次数的实测值基本吻合理论计算值，验证了式(2)和式(8)的正确性。同时，可以很明显地发现，随着排序元素(模块数)的增加，两种算法的排序次数差值越来越大，算法的选择显得越来越重要。实际中MMC的桥臂子模块数量已经达到200，此时传统冒泡算法的排序次数将是快速排序算法的9倍。

图5 两种算法排序元素个数和排序次数的关系

进一步，采用DSP控制器TMS320F28335测量快速排序算法在不同排序元素数量时对模块电压进行排序的实际执行时间，并和传统冒泡算法进行对比分析，结果如图6所示。控制芯片中ECAP模块含有一个TSCTR计数器，每一个时钟脉冲后计数器数值加1。实验中，时钟频率设定为150 MHz，即计数器数值每0.67 ns增加1。因此，通过记录计数器在算法开始和结束时的数值，用差值乘以0.67 ns即可测得算法的执行时间。测试结果表明，随着排序元素(模块数)的增加，冒泡排序算法实际执行时间迅速增长，曲线符合O(n2)；快速排序算法执行时间的增长较为平缓，执行时间远远低于快速排序算法，曲线符合O(nlog2n)。

图6 两种算法执行时间

4.2 算法对仿真用时的影响

为验证所提出的基于快速排序算法电容电压均衡策略的有效性和正确性，在PSCAD/EMTDC中分别搭建三相21、31、41电平MMC-HVDC仿真平台，对应模块数分别20、30、40。采取NLM调制方式，具体仿真参数见表1。

表1 主电路参数

为了全面、系统地验证快速排序算法的有效性和正确性，MMC-HVDC仿真平台进行了三类情况下的验证，分别是:(1)不同子模块数。仿真时间设定为5 s，仿真步长为50 μs，子模块数分别为20、30、40；(2)不同仿真时间。模块数设置为40，仿真步长为50 μs，仿真时间为5 s、8 s、10 s；(3)不同仿真步长。模块数设置为40，仿真时间5 s，仿真步长分别为50 μs、100 μs、150 μs。经过多次仿真实验取平均值，得到三种情况下采用两种不同电压均衡策略的仿真实际用时(四舍五入取整)如图7所示。由图7可知，在不同模块数、仿真步长和仿真设定时间三种情况下，基于快速排序的电容电压均衡策略比经典冒泡排序的实际仿真用时要短，证明了快速排序对MMC-HVDC系统提高排序效率、降低运算量、减少仿真用时具有显著的作用。同时，可以看出，模块数越多、仿真设定时间越长，其优势越加明显。

4.3 电压均衡效果及系统外特性

最后，分析两种算法对电压均衡效果及系统外特性的影响。仿真设置子模块数为20，仿真步长50 μs，仿真时间设定为5 s，主电路参数如表1所示。图8是采用传统算法和快速排序算法时MMC的电容电压，可以看出两种算法的电容电压波形完全相同，每个子模块电压额定值为20 kV，电压波动值0.1 kV，表明快速排序算法并不会改变模块的触发机制，电压平衡效果不变，均可以较好地实现电容电压均衡。图9是采用两种算法时的直流电压、交流输出电压和交流电流波形。由图可知，两种算法中直流电压、交流输出电压和交流电流等特征量完全一致，快速排序算法在提升排序效率缓解控制器负担的同时并不会改变系统的外特性，算法适应性较好。

图7 两种算法仿真速度比较

图8 两种算法电容电压

图9 两种算法系统外特性

5 结束语

提出一种基于快速排序算法的电容电压均衡策略，通过比较、划分的递归处理快速实现模块电压的排序，算法时间复杂度仅为O(nlog2n)。采用DSP控制器TMS320F28335测量算法的实际执行时间并在PSCAD/EMTDC中搭建仿真验证平台，表明和传统算法相比，基于快速排序算法的电容电压均衡策略可以有效减少排序次数，提高排序效率，缩短仿真时间，同时模块电压均衡效果和系统的外特性并不会发生改变，具有较好的算法适应性，适用于含大量子模块的MMC。