2. 中国科学院大学, 北京 100049
2. University of Chinese Academy of Sciences, Beijing 100049, China
近年来,蜂群无人机由于可以体现出蜂群的整体优势,完成较复杂的任务,相比单一无人机,蜂群可以对多无人机执行任务带来很多的优势,成为国内外研究的热点[1-3]。但是由于电源技术的水平和限制,现有无人机续航时间短,需要经常充电,因此蜂群无人机快速充电以及充电排队问题成为制约其快速发展和大面积应用的瓶颈技术,特别是充电排队问题影响着蜂群无人机执行任务的效率和效果。据现有文献查询,蜂群无人机充电排队的研究未曾报道,本文基于排队理论对蜂群无人机充电排队技术进行研究。
在常规的电动汽车排队充电研究中,文献[4]基于排队理论建立了充电设施系统排队模型,通过合理配置充电设施,提高了电网负荷率。文献[5]基于排队理论对电动汽车充电站的24小时充电负荷曲线进行建模,使用随机最优潮流和模型预测控制方法研究了不确定性的影响。文献[6]基于排队理论中的M/M/s模型和流体方程,计算了高速公路充电站的电动汽车到达率。文献[7]针对电动出租汽车充电站排队系统,对M/G/k排队模型和M/M/k排队模型进行了对比,分析了电动汽车到站的荷电状态对排队系统的影响,并提出了提高系统服务能力的措施。文献[8]利用排队理论在服务系统优化设计方面的优势,构建了电动汽车充电桩的最优台数设计模型,同时利用排队理论分析了充电站的服务水平和运行效率。文献[9]采用基于排队论的充电机配置方法,提出了布局最优化的数学模型,并基于M/M/s模型,以平均等待时间为标准确定充电站的规模。文献[10]利用电动汽车充电站排队论模型,研究了基于路径需求和基于点需求下的充电站选址定容问题。文献[11]基于排队理论进行了充电站的容量优化配置。
在面向蜂群无人机充电时,由于其工作环境的特殊性,可能需要悬停等待充电,比常规充电工况多,因此需要加入系统容量的限制。即,当某一充电平台可容纳的无人机数量达到限定值后,无人机将不再前往这一平台,从而避免了无人机在悬停等待的队列中将电量耗尽。
目前充电方法包括集中式充电和分布式充电2种,其中集中式充电(Concentrated Charging,文中用下标“c”表示)将充电平台集中在一处,对蜂群无人机进行充电。而分布式充电(Distributed Charging,文中用下标“d”表示)将充电平台分散放置。本文基于M/M/1/m[12]模型和M/M/n/m[13-16]模型对多充电平台的2种排布方式展开研究。
1 排队系统基本理论在排队论中,通常采用6个特性,实现对一个排队系统的分析[17]。它们的描述通常依据Kendall提出的方法[18]:
$ A/B/N/S/C/Z $ |
式中:A为输入过程;B为服务时间;N为服务员数量;S为系统容量;C为客源数量;Z为排队规则[17-19]。
当系统容量为固定值,且排队规则为先到先服务时。依据Kendall提出的方法,该类排队模型可表示为
$ A/B/N/S $ |
第2节中,将着重对M/M/ 1/m和M/M/n/m2种排队模型进行分析。其中M表示顾客之间的到达时间间隔和服务员为顾客提供服务的时间服从指数分布[19];m代表排队系统中的系统容量; n代表排队系统中的服务员数量
2 2种排队模型 2.1 M/M/1/m模型M/M/1/m模型的状态转移图如图 1所示,图中:λ和μ为上述指数分布对应的参数。
由图 1可以列出平衡方程为
$ \left\{ \begin{array}{l} \lambda {P_0} = \mu {P_1}\\ \lambda {P_{k - 1}} + \mu {P_{k + 1}} = (\lambda + \mu ){P_k}\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} k = 1,2, \cdots ,m - 1\\ \lambda {P_{m - 1}} = \mu {P_m} \end{array} \right. $ | (1) |
式中:Pk为系统中有k位顾客时的概率。定义M/M/1/m模型中系统的服务强度为
$ \rho = \frac{\lambda }{\mu } $ | (2) |
经过推导,可以得到M/M/1/m模型,队列中顾客的平均数量为
$ L = \left\{ {\begin{array}{*{20}{l}} {\frac{{\rho [(m - 1){\rho ^{m + 1}} - m{\rho ^m} + \rho ]}}{{(1 - \rho )(1 - {\rho ^{m + 1}})}}}&{\rho \ne 1}\\ {\frac{{{m^2} - m}}{{2(m + 1)}}}&{\rho = 1} \end{array}} \right. $ | (3) |
因此,借助Little定理[20-21],可以求得顾客在队列中等待的时间为
$ T = \left\{ {\begin{array}{*{20}{l}} {\frac{{\rho [(m - 1){\rho ^{m + 1}} - m{\rho ^m} + \rho ]}}{{\lambda (1 - \rho )(1 - {\rho ^{m + 1}})(1 - {P_m})}}}&{\rho \ne 1}\\ {\frac{{{m^2} - m}}{{2\lambda (m + 1)(1 - {P_m})}}}&{\rho = 1} \end{array}} \right. $ | (4) |
M/M/n/m模型也可采用如图 2所示的状态转移图求解概率分布。
由图 2可列出平衡方程为
$ \left\{ {\begin{array}{*{20}{l}} {\lambda {{\hat P}_0} = \mu {{\hat P}_1}}\\ {\lambda {{\hat P}_{k - 1}} + (k + 1)\mu {{\hat P}_{k + 1}} = (\lambda + {k_\mu }){{\hat P}_k}\quad 1 \le k < n}\\ {\lambda {{\hat P}_{k - 1}} + {n_\mu }{{\hat P}_{k + 1}} = (\lambda + n\mu ){{\hat P}_k}\quad {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} n \le k < m}\\ {n\mu {{\hat P}_m} = \lambda {{\hat P}_{m - 1}}} \end{array}} \right. $ | (5) |
定义M/M/n/m模型中系统的服务强度为
$ \hat \rho = \frac{\lambda }{{n\mu }} $ | (6) |
通过推导,可得到M/M/n/m模型中的平均队列长度为
$ \hat L = \left\{ {\begin{array}{*{20}{l}} {\frac{{{n^n}{{\hat \rho }^{n + 1}}{{\hat P}_0}}}{{n!{{(1 - \hat \rho )}^2}}}[1 - (m - n + 1){{\hat \rho }^{m - n}} + }&{}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (m - n){{\hat \rho }^{m - n + 1}}]}&{\hat \rho \ne 1}\\ {\frac{{{n^n}}}{{2n!}}(m - n)(m - n + 1){{\hat P}_0}}&{\hat \rho = 1} \end{array}} \right. $ | (7) |
基于Little定理,可以计算出M/M/n/m模型中,顾客在队列中等待的时间为
$ \begin{array}{l} \hat T = \\ \left\{ {\begin{array}{*{20}{l}} {\frac{{{n^n}{{\hat \rho }^{n + 1}}{{\hat P}_0}}}{{n!{{(1 - \hat \rho )}^2}\lambda (1 - {{\hat P}_m})}}[1 - (m - n + 1) \cdot }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\hat \rho }^{m - n}} + (m - n){{\hat \rho }^{m - n + 1}}]\quad {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \hat \rho \ne 1\quad }\\ {\frac{{{n^n}{{\hat P}_0}}}{{2n!\lambda (1 - {{\hat P}_m})}}(m - n)(m - n + 1)\ \ \ \ \ \quad \hat \rho = 1} \end{array}} \right. \end{array} $ | (8) |
式(7)和式(8)中
$ \begin{array}{l} {{\hat P}_0} = \\ \left\{ {\begin{array}{*{20}{l}} {{{\left[ {\sum\limits_{k = 0}^{n - 1} {\frac{{{{(n\hat \rho )}^k}}}{{k!}}} + \frac{{{{(n\hat \rho )}^n}}}{{n!}} \cdot \frac{{1 - {{\hat \rho }^{m - n + 1}}}}{{1 - \hat \rho }}} \right]}^{ - 1}}}&{\hat \rho \ne 1}\\ {{{\left[ {\sum\limits_{k = 0}^{n - 1} {\frac{{{n^k}}}{{k!}}} + \frac{{{n^n}}}{{n!}}(m - n + 1)} \right]}^{ - 1}}}&{\hat \rho = 1} \end{array}} \right. \end{array} $ | (9) |
面向蜂群无人机的分布式充电的示意图如图 3所示。
由于充电平台分散放置,蜂群无人机到达后排成n个独立队列。如图 4所示,可将其等效成n个M/M/1/m模型,则到达速率缩小为原来的1n。在描述分布式充电的各项指标时,只需考虑其任意一列。相应的服务强度缩小为
$ {\rho ^\prime } = \frac{\lambda }{{n\mu }} $ | (10) |
基于2.1节对M/M/1/m的分析,以及式(10),可以计算出分布式充电的平均队列长度Ld和平均等待时间Td分别为
$ {L_{\rm{d}}} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{\rho ^\prime }[(m - 1){\rho ^{\prime m + 1}} - m{\rho ^{\prime m}} + {\rho ^\prime }]}}{{(1 - {\rho ^\prime })(1 - {\rho ^{\prime m + 1}})}}}&{{\rho ^\prime } \ne 1}\\ {\frac{{{m^2} - m}}{{2(m + 1)}}}&{{\rho ^\prime } = 1} \end{array}} \right. $ | (11) |
$ \begin{array}{l} {T_{\rm{d}}} = \\ \left\{ {\begin{array}{*{20}{l}} {\frac{1}{\lambda } \cdot \frac{{n{\rho ^\prime }}}{{(1 - {\rho ^\prime })(1 - {\rho ^{\prime m}})}}[(m - 1){\rho ^{\prime m + 1}} - }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} m{\rho ^{\prime m}} + {\rho ^\prime }]{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rho ^\prime } \ne 1}\\ {\frac{1}{\lambda } \cdot \frac{{n(m - 1)}}{2}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ \ {\rho ^\prime } = 1} \end{array}} \right. \end{array} $ | (12) |
针对蜂群无人机的集中式充电的示意图如图 5所示,n个充电平台集中放置在一起。无人机到达后,在单一共享的队列中等待充电。依据3.1节所述,M/M/1/m模型可用于描述其中一个充电平台。因此,在集中式充电的背景下,n个充电平台可等效为M/M/n/nm模型。
基于本文2.2节对M/M/n/m模型的分析,经计算可得到,集中式充电的平均队列长度Lc和平均等待时间Tc分别为
$ {L_{\rm{c}}} = \left\{ \begin{array}{l} \frac{{{n^n}{{\hat \rho }^{n + 1}}{{\hat P}^\prime }_0}}{{n!{{(1 - \hat \rho )}^2}}}\left[ {1 - (nm - n + 1){{\hat \rho }^{nm - n}} + } \right.\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left. {{\kern 1pt} {\kern 1pt} (nm - n){{\hat \rho }^{nm - n + 1}}} \right]{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ \hat \rho \ne 1\\ \frac{{{n^n}}}{{2n!}}{{\hat P}^\prime }_0(nm - n)(nm - n + 1){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt}\ \hat \rho = 1 \end{array} \right. $ | (13) |
$ \begin{array}{l} {T_{\rm{c}}} = \\ \left\{ \begin{array}{l} \frac{1}{\lambda } \cdot \frac{{{n^n}{{\hat \rho }^{n + 1}}{{\hat P}^\prime }_0}}{{n!{{(1 - \hat \rho )}^2}(1 - {{\hat P}_{nm}})}}[1 - (nm - n + 1) \cdot \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\hat \rho }^{nm - n}} + (nm - n){{\hat \rho }^{nm - n + 1}}]{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \hat \rho \ne 1\\ \frac{1}{\lambda } \cdot \frac{{{n^n}{{\hat P}^\prime }_0}}{{2n!(1 - {{\hat P}_{nm}})}}(nm - n) \cdot \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (nm - n + 1){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt}\ \ \ \hat \rho = 1 \end{array} \right. \end{array} $ | (14) |
式(13)和式(14)中的
$ \begin{array}{l} {{\hat P}^\prime }_0 = \\ \left\{ {\begin{array}{*{20}{l}} {{{\left[ {\sum\limits_{k = 0}^{n - 1} {\frac{{{{(n\hat \rho )}^k}}}{{k!}}} + \frac{{{{(n\hat \rho )}^n}}}{{n!}} \cdot \frac{{1 - {{\hat \rho }^{nm - n + 1}}}}{{1 - \hat \rho }}} \right]}^{ - 1}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt}\ \ \ \ \ \ \hat \rho \ne 1}\\ {{{\left[ {\sum\limits_{k = 0}^{n - 1} {\frac{{{n^k}}}{{k!}}} + \frac{{{n^n}}}{{n!}}(nm - n + 1)} \right]}^{ - 1}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \hat \rho = 1} \end{array}} \right. \end{array} $ | (15) |
$ {\hat P_{nm}} = \frac{{{n^n}{{\hat \rho }^{nm}}{{\hat P}^\prime }_0}}{{n!}} $ | (16) |
基于第3节的公式推导以及对分布式充电的等效,如式(17)所示,2种排队充电方式的服务强度相等。而针对蜂群无人机,服务强度即为:“单位时间返回充电平台的无人机数量与单位时间离开充电平台的无人机数量的比值”。在下文中,将使用无量纲量ρ来表述这一相等的服务强度。
$ {\rho ^\prime } = \frac{\lambda }{{n\mu }} = \hat \rho $ | (17) |
本文基于MATLAB软件,对2种排队方式的平均队列长度和平均等待时间进行计算。具体的参数设置如表 1所示。
当系统容量设定为6时,随着服务强度和充电平台数量的变化,2种充电方式的平均队列长度对比如图 6所示。
依据图 6可以看出,在服务强度的区间为[0, 2]时,若以平均队列长度作为评价充电方式优劣的指标。随着服务强度的增加,两者的队列长度均随之增长,但存在一个分界点。即分布式充电的队列长度曲线会与集中式充电的队列长度曲线产生交叉点,在交叉点前,服务强度较小时,分布式充电的队列长度高于集中式充电的队列长度。在这一交叉点后,分布式充电的队列长度低于集中式充电的队列长度。下面,将系统容量依次设置为7、8和9时,继续对比2种充电方式的平均队列长度。
从图 7~图 9中可以看到,随着服务强度的增加,将会观察到与系统容量为6时一样的现象。通过数值分析中的二分法,取区间为(0.7, 0.9),精度为0.0001,可以求解出每一个交叉点的横坐标,如表 2所示。综合上述曲线,可以观察到,服务强度较低时,在以平均队列长度作为评判指标时,集中式充电比较有优势,但随着服务强度的增加,分布式充电的优势逐渐体现。
平台数量 | 系统容量 | |||
m=6 | m=7 | m=8 | m=9 | |
n=4 | 0.70751953125 | 0.73193359375 | 0.75205078125 | 0.76884765625 |
n=5 | 0.72783203125 | 0.75048828125 | 0.76904296875 | 0.78447265625 |
n=6 | 0.74345703125 | 0.76455078125 | 0.78193359375 | 0.79619140625 |
n=7 | 0.75576171875 | 0.77568359375 | 0.79208984375 | 0.80556640625 |
n=8 | 0.76611328125 | 0.78486328125 | 0.80029296875 | 0.81318359375 |
n=9 | 0.77470703125 | 0.79267578125 | 0.80751953125 | 0.81982421875 |
n=10 | 0.78193359375 | 0.79931640625 | 0.81357421875 | 0.82529296875 |
观察3.1节的式(12)和3.2节的式(14),其中均有共同的因子λ的倒数。将其消去后,如式(18)和式(19)所示。因此,可以通过计算td和tc之间的大小关系,实现对2种充电方式的比较。
$ {t_{\rm{d}}} = \left\{ {\begin{array}{*{20}{l}} {\frac{{n_\rho ^\prime [(m - 1){\rho ^{\prime m + 1}} - m{\rho ^{\prime m}} + {\rho ^\prime }]}}{{(1 - {\rho ^\prime })(1 - {\rho ^{\prime m}})}}}&{{\rho ^\prime } \ne 1}\\ {\frac{{n(m - 1)}}{2}}&{{\rho ^\prime } = 1} \end{array}} \right. $ | (18) |
$ {t_{\rm{c}}} = \left\{ \begin{array}{l} \frac{{{n^n}{{\hat \rho }^{n + 1}}{{\hat P}^\prime }_0}}{{n!{{(1 - \hat \rho )}^2}(1 - {{\hat P}_{nm}})}}[1 - (nm - n + 1) \cdot \\ {{\hat \rho }^{nm - n}} + (nm - n){{\hat \rho }^{nm - n + 1}}]{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \hat \rho \ne 1\\ \frac{{{n^n}{{\hat P}^\prime }_0}}{{2n!(1 - {{\hat P}_{nm}})}}(nm - n)(nm - n + 1){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \hat \rho = 1 \end{array} \right. $ | (19) |
与4.1节处理方法一致,首先将系统容量设定为6。绘制2种充电方式的平均等待时间,即td和tc随服务强度及平台数量变化的曲线图,如图 10所示。
依据图 10可以发现,在服务强度的区间为[0, 2]时,随着服务强度的增长,2种充电方式的平均等待时间随之增长。服务强度较小时,集中式充电的平均等待时间低于另一者。但两者在服务强度为1附近产生交叉点,在这一交叉点后,集中式充电的平均等待时间会高于另一者。
从图 11~图 13中可以看到,随着服务强度的增加,与4.1节类似。服务强度较低时,若以平均等待时间作为评判指标,集中式充电比较有优势。但随着服务强度的增加,分布式充电的优势逐渐体现。通过数值分析中的二分法,取区间为(1.0001, 1.125),精度为0.0001,可以求解出每一个交叉点的横坐标,如表 3所示。
平台数量 | 系统容量 | |||
m=6 | m=7 | m=8 | m=9 | |
n=4 | 1.019188720703125 | 1.013821923828125 | 1.010406689453125 | 1.008089208984375 |
n=5 | 1.014553759765625 | 1.010406689453125 | 1.007845263671875 | 1.006137646484375 |
n=6 | 1.011504443359375 | 1.008211181640625 | 1.006259619140625 | 1.004795947265625 |
n=7 | 1.009430908203125 | 1.006747509765625 | 1.005039892578125 | 1.003942138671875 |
n=8 | 1.007967236328125 | 1.005649755859375 | 1.004308056640625 | 1.003332275390625 |
n=9 | 1.006869482421875 | 1.004917919921875 | 1.003698193359375 | 1.002844384765625 |
n=10 | 1.006015673828125 | 1.004308056640625 | 1.003210302734375 | 1.002478466796875 |
1) 在服务强度的区间为[0, 2]时,随着服务强度的增强,评价指标对应的曲线存在交叉点。交叉点前,即服务强度较低的情形下,集中式充电的两项评价指标优于分布式充电。但在交叉点后,随着服务强度的增大,分布式充电的两项评价指标优于集中式充电。
2) 对于不同充电平台数量和系统容量给出了选择集中式充电和分布式充电的交叉参考点,对蜂群无人机充电排队提供重要的参考。
[1] |
王荣巍, 何锋, 周璇, 等. 面向无人机蜂群的航电云多层任务调度模型[J]. 航空学报, 2019, 40(11): 323183. WANG R W, HE F, ZHOU X, et al. Avionics cloud multi-layer task scheduling model for UAV swarm[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40(11): 323183. (in Chinese) |
Cited By in Cnki (0) | Click to display the text | |
[2] |
吕娜, 刘创, 陈柯帆, 等. 一种面向航空集群的集中控制式网络部署方法[J]. 航空学报, 2018, 39(7): 321961. LYU N, LIU C, CHEN K F, et al. A method for centralized control network deployment of aeronautic swarm[J]. Acta Aeronautica et Astronautica Sinica, 2018, 39(7): 321961. (in Chinese) |
Cited By in Cnki (11) | Click to display the text | |
[3] |
陈方舟, 黄靖皓, 赵阳辉. 美军无人"蜂群"作战技术发展分析[J]. 装备学院学报, 2016, 27(2): 34-37. CHEN F Z, HUANG J H, ZHAO Y H. Analysis on unmanned swarm flighting system of U.S. armed forces[J]. Journal of Equipment Academy, 2016, 27(2): 34-37. (in Chinese) |
Cited By in Cnki (20) | Click to display the text | |
[4] |
李如琦, 苏浩益. 基于排队论的电动汽车充电设施优化配置[J]. 电力系统自动化, 2011, 35(14): 58-61. LI R Q, SU H Y. Optimal allocation of charging facilities for electric vehicles based on queuing theory[J]. Automation of Electric Power Systems, 2011, 35(14): 58-61. (in Chinese) |
Cited By in Cnki (182) | Click to display the text | |
[5] | HAFEZ O, BHATTACHARYA K. Queuing analysis based PEV load modeling considering battery charging behavior and their impact on distribution system operation[J]. IEEE Transactions on Smart Grid, 2018, 9(1): 261-273. |
Click to display the text | |
[6] | BAE S, KWASINSKI A. Spatial and temporal model of electric vehicle charging demand[J]. IEEE Transactions on Smart Grid, 2012, 3(1): 394-403. |
Click to display the text | |
[7] |
张维戈, 陈连福, 黄彧, 等. M/G/k排队模型在电动出租汽车充电站排队系统中的应用[J]. 电网技术, 2015, 39(3): 724-729. ZHANG W G, CHEN L F, HUANG Y, et al. Application of M/G/k queuing model in queuing system of electric taxi charging station[J]. Power System Technology, 2015, 39(3): 724-729. (in Chinese) |
Cited By in Cnki (39) | Click to display the text | |
[8] |
冯亮.电动汽车充电站规划研究[D].天津: 天津大学, 2013: 70-96. FENG L. Electric vehicle charging station planning[D]. Tianjin: Tianjin University, 2013: 70-96(in Chinese). |
Cited By in Cnki (67) | Click to display the text | |
[9] |
熊虎, 向铁元, 祝勇刚, 等. 电动汽车公共充电站布局的最优规划[J]. 电力系统自动化, 2012, 36(23): 65-70. XIONG H, XIANG T Y, ZHU Y G, et al. Electric vehicle public charging stations location optimal planning[J]. Automation of Electric Power Systems, 2012, 36(23): 65-70. (in Chinese) |
Cited By in Cnki (84) | Click to display the text | |
[10] |
卢芳.基于排队论的电动汽车充电站选址定容研究[D].北京: 北京交通大学, 2015: 11-42. LU F. The location-sizing problem of electric vehicle charging station deployment based on queuing theory[D]. Beijing: Beijing Jiaotong University, 2015: 11-42(in Chinese). |
[11] |
葛少云, 冯亮, 刘洪, 等. 考虑车流信息与配电网络容量约束的充电站规划[J]. 电网技术, 2013, 37(3): 582-589. GE S Y, FENG L, LIU H, et al. Planning of charging stations considering traffic flow and capacity constraints of distribution network[J]. Power System Technology, 2013, 37(3): 582-589. (in Chinese) |
Cited By in Cnki (140) | Click to display the text | |
[12] |
赵玉荣, 高超, 方明. M/M/1/m系统算子的本征值特性(m=1, 2, 3, 4)[J]. 数学的实践与认识, 2010, 40(16): 184-187. ZHAO Y R, GAO C, FANG M. The characteristic of eigenvalue of M/M/1/m[J]. Mathematics in Practice and Theory, 2010, 40(16): 184-187. (in Chinese) |
[13] |
毛云峰.基于M/M/n/m模型网上报名系统连接池优化研究[D].昆明: 昆明理工大学, 2017: 27-38. MAO Y F. Research on optimization of connection pool of online registration system based on M/M/n/m model[D]. Kunming: Kunming University of Science and Technology, 2017: 27-38(in Chinese). |
[14] |
黄业文, 邝神芬. 非强占有限优先权M/M/n/m排队系统[J]. 应用概率统计, 2018, 34(4): 364-380. HUANG Y W, KUANG S F. M/M/n/m queuing model under nonpreemptive limited-priority[J]. Chinese Journal of Applied and Statistics, 2018, 34(4): 364-380. (in Chinese) |
Cited By in Cnki (4) | Click to display the text | |
[15] |
蔡金兵.两类服务率可变的M/M/n/m排队模型及应用研究[D].重庆: 重庆师范大学, 2010: 15-23. CAI J B. Two kind of servicing rate invariable M/M/n/m queuing model and applied research[D]. Chongqing: Chongqing Normal University, 2010: 15-23(in Chinese). |
[16] |
唐玉玉.具有可变输入率且有优先权的M/M/n/m排队模型研究[D].重庆: 重庆师范大学, 2012: 19-47. TANG Y Y. The research of M/M/n/m queuing system with variable input rate and the priority[D]. Chongqing: Chongqing Normal University, 2012: 19-47(in Chinese). |
[17] |
唐加山. 排队论及其应用[M]. 北京: 科学出版社, 2016: 1-20. TANG J S. Queuing theory and its application[M]. Beijing: Science Press, 2016: 1-20. (in Chinese) |
[18] | KENDALL, DAVID G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain[J]. The Annals of Mathematical Statistics, 1953, 24(3): 338-354. |
Click to display the text | |
[19] |
归敏丹, 蒋毅飞, 张志敏, 等. 多服务员时两种等待队列性能的比较[J]. 计算机工程与应用, 2008(13): 44-46, 66. GUI M D, JIANG Y F, ZHANG Z M, et al. Comparison of two queuing models with multiple servers[J]. Computer Engineering and Applications, 2008(13): 44-46, 66. (in Chinese) |
Cited By in Cnki (13) | Click to display the text | |
[20] | LITTLE, JOHN D C. A proof for the queuing formula:L=λW[J]. Operations Research, 1961, 9(3): 383-387. |
Click to display the text | |
[21] | WHITT W. A review of L=λW and extensions[J]. Queueing Systems, 1991, 9(3): 235-268. |
Click to display the text |