王云哲,徐國寧,*,王生,李兆杰,蔡榕
1.中國科學院 空天信息創(chuàng)新研究院,北京 100094 2.中國科學院大學,北京 100049
近年來,蜂群無人機由于可以體現(xiàn)出蜂群的整體優(yōu)勢,完成較復雜的任務(wù),相比單一無人機,蜂群可以對多無人機執(zhí)行任務(wù)帶來很多的優(yōu)勢,成為國內(nèi)外研究的熱點[1-3]。但是由于電源技術(shù)的水平和限制,現(xiàn)有無人機續(xù)航時間短,需要經(jīng)常充電,因此蜂群無人機快速充電以及充電排隊問題成為制約其快速發(fā)展和大面積應(yīng)用的瓶頸技術(shù),特別是充電排隊問題影響著蜂群無人機執(zhí)行任務(wù)的效率和效果。據(jù)現(xiàn)有文獻查詢,蜂群無人機充電排隊的研究未曾報道,本文基于排隊理論對蜂群無人機充電排隊技術(shù)進行研究。
在常規(guī)的電動汽車排隊充電研究中,文獻[4]基于排隊理論建立了充電設(shè)施系統(tǒng)排隊模型,通過合理配置充電設(shè)施,提高了電網(wǎng)負荷率。文獻[5] 基于排隊理論對電動汽車充電站的24小時充電負荷曲線進行建模,使用隨機最優(yōu)潮流和模型預測控制方法研究了不確定性的影響。文獻[6]基于排隊理論中的M/M/s模型和流體方程,計算了高速公路充電站的電動汽車到達率。文獻[7]針對電動出租汽車充電站排隊系統(tǒng),對M/G/k排隊模型和M/M/k排隊模型進行了對比,分析了電動汽車到站的荷電狀態(tài)對排隊系統(tǒng)的影響,并提出了提高系統(tǒng)服務(wù)能力的措施。文獻[8]利用排隊理論在服務(wù)系統(tǒng)優(yōu)化設(shè)計方面的優(yōu)勢,構(gòu)建了電動汽車充電樁的最優(yōu)臺數(shù)設(shè)計模型,同時利用排隊理論分析了充電站的服務(wù)水平和運行效率。文獻[9]采用基于排隊論的充電機配置方法,提出了布局最優(yōu)化的數(shù)學模型,并基于M/M/s模型,以平均等待時間為標準確定充電站的規(guī)模。文獻[10]利用電動汽車充電站排隊論模型,研究了基于路徑需求和基于點需求下的充電站選址定容問題。文獻[11]基于排隊理論進行了充電站的容量優(yōu)化配置。
在面向蜂群無人機充電時,由于其工作環(huán)境的特殊性,可能需要懸停等待充電,比常規(guī)充電工況多,因此需要加入系統(tǒng)容量的限制。即,當某一充電平臺可容納的無人機數(shù)量達到限定值后,無人機將不再前往這一平臺,從而避免了無人機在懸停等待的隊列中將電量耗盡。
目前充電方法包括集中式充電和分布式充電2種,其中集中式充電(Concentrated Charging,文中用下標“c”表示)將充電平臺集中在一處,對蜂群無人機進行充電。而分布式充電(Distributed Charging,文中用下標“d”表示)將充電平臺分散放置。本文基于M/M/1/m[12]模型和M/M/n/m[13-16]模型對多充電平臺的2種排布方式展開研究。
在排隊論中,通常采用6個特性,實現(xiàn)對一個排隊系統(tǒng)的分析[17]。它們的描述通常依據(jù)Kendall提出的方法[18]:
A/B/N/S/C/Z
式中:A為輸入過程;B為服務(wù)時間;N為服務(wù)員數(shù)量;S為系統(tǒng)容量;C為客源數(shù)量;Z為排隊規(guī)則[17-19]。
當系統(tǒng)容量為固定值,且排隊規(guī)則為先到先服務(wù)時。依據(jù)Kendall提出的方法,該類排隊模型可表示為
A/B/N/S
第2節(jié)中,將著重對M/M/1/m和M/M/n/m2種排隊模型進行分析。其中M表示顧客之間的到達時間間隔和服務(wù)員為顧客提供服務(wù)的時間服從指數(shù)分布[19];m代表排隊系統(tǒng)中的系統(tǒng)容量;n代表排隊系統(tǒng)中的服務(wù)員數(shù)量
M/M/1/m模型的狀態(tài)轉(zhuǎn)移圖如圖1所示,圖中:λ和μ為上述指數(shù)分布對應(yīng)的參數(shù)。
圖1 M/M/1/m模型狀態(tài)轉(zhuǎn)移圖Fig.1 State transition diagram of M/M/1/m model
由圖1可以列出平衡方程為
(1)
式中:Pk為系統(tǒng)中有k位顧客時的概率。定義M/M/1/m模型中系統(tǒng)的服務(wù)強度為
(2)
經(jīng)過推導,可以得到M/M/1/m模型,隊列中顧客的平均數(shù)量為
(3)
因此,借助Little定理[20-21],可以求得顧客在隊列中等待的時間為
(4)
M/M/n/m模型也可采用如圖2所示的狀態(tài)轉(zhuǎn)移圖求解概率分布。
圖2 M/M/n/m模型狀態(tài)轉(zhuǎn)移圖Fig.2 State transition diagram of M/M/n/m model
由圖2可列出平衡方程為
(5)
定義M/M/n/m模型中系統(tǒng)的服務(wù)強度為
(6)
通過推導,可得到M/M/n/m模型中的平均隊列長度為
(7)
基于Little定理,可以計算出M/M/n/m模型中,顧客在隊列中等待的時間為
(8)
面向蜂群無人機的分布式充電的示意圖如圖3所示。
圖3 分布式充電示意圖Fig.3 Schematic diagram of distributed charging
圖4 分布式充電等效圖Fig.4 Equivalent diagram of distributed charging
(10)
基于2.1節(jié)對M/M/1/m的分析,以及式(10),可以計算出分布式充電的平均隊列長度Ld和平均等待時間Td分別為
(11)
Td=
(12)
針對蜂群無人機的集中式充電的示意圖如圖5 所示,n個充電平臺集中放置在一起。無人機到達后,在單一共享的隊列中等待充電。依據(jù)3.1節(jié) 所述,M/M/1/m模型可用于描述其中一個充電平臺。因此,在集中式充電的背景下,n個充電平臺可等效為M/M/n/nm模型。
圖5 集中式充電示意圖Fig.5 Schematic diagram of concentrated charging
基于本文2.2節(jié)對M/M/n/m模型的分析,經(jīng)計算可得到,集中式充電的平均隊列長度Lc和平均等待時間Tc分別為
(13)
Tc=
(14)
(15)
(16)
基于第3節(jié)的公式推導以及對分布式充電的等效,如式(17)所示,2種排隊充電方式的服務(wù)強度相等。而針對蜂群無人機,服務(wù)強度即為:“單位時間返回充電平臺的無人機數(shù)量與單位時間離開充電平臺的無人機數(shù)量的比值”。在下文中,將使用無量綱量ρ來表述這一相等的服務(wù)強度。
(17)
本文基于MATLAB軟件,對2種排隊方式的平均隊列長度和平均等待時間進行計算。具體的參數(shù)設(shè)置如表1所示。
表1 參數(shù)設(shè)置Table 1 Parameter setting
當系統(tǒng)容量設(shè)定為6時,隨著服務(wù)強度和充電平臺數(shù)量的變化,2種充電方式的平均隊列長度對比如圖6所示。
依據(jù)圖6可以看出,在服務(wù)強度的區(qū)間為[0,2]時,若以平均隊列長度作為評價充電方式優(yōu)劣的指標。隨著服務(wù)強度的增加,兩者的隊列長度均隨之增長,但存在一個分界點。即分布式充電的隊列長度曲線會與集中式充電的隊列長度曲線產(chǎn)生交叉點,在交叉點前,服務(wù)強度較小時,分布式充電的隊列長度高于集中式充電的隊列長度。在這一交叉點后,分布式充電的隊列長度低于集中式充電的隊列長度。下面,將系統(tǒng)容量依次設(shè)置為7、8和9時,繼續(xù)對比2種充電方式的平均隊列長度。
圖6 系統(tǒng)容量為6時的平均隊列長度對比Fig.6 Comparison of average queuing length when system capacity is 6
從圖7~圖9中可以看到,隨著服務(wù)強度的增加,將會觀察到與系統(tǒng)容量為6時一樣的現(xiàn)象。通過數(shù)值分析中的二分法,取區(qū)間為(0.7,0.9),精度為0.000 1,可以求解出每一個交叉點的橫坐標,如表2所示。綜合上述曲線,可以觀察到,服務(wù)強度較低時,在以平均隊列長度作為評判指標時,集中式充電比較有優(yōu)勢,但隨著服務(wù)強度的增加,分布式充電的優(yōu)勢逐漸體現(xiàn)。
圖7 系統(tǒng)容量為7時的平均隊列長度對比Fig.7 Comparison of average queuing length when system capacity is 7
圖8 系統(tǒng)容量為8時的平均隊列長度對比Fig.8 Comparison of average queuing length when system capacity is 8
圖9 系統(tǒng)容量為9時的平均隊列長度對比Fig.9 Comparison of average queuing length when system capacity is 9
表2 2種充電方式平均隊列長度曲線的交叉點Table 2 Intersection of average queuing length curves of two charging methods
觀察3.1節(jié)的式(12)和3.2節(jié)的式(14),其中均有共同的因子λ的倒數(shù)。將其消去后,如式(18)和式(19)所示。因此,可以通過計算td和tc之間的大小關(guān)系,實現(xiàn)對2種充電方式的比較。
(18)
(19)
與4.1節(jié)處理方法一致,首先將系統(tǒng)容量設(shè)定為6。繪制2種充電方式的平均等待時間,即td和tc隨服務(wù)強度及平臺數(shù)量變化的曲線圖,如圖10所示。
依據(jù)圖10可以發(fā)現(xiàn),在服務(wù)強度的區(qū)間為[0,2]時,隨著服務(wù)強度的增長,2種充電方式的平均等待時間隨之增長。服務(wù)強度較小時,集中式充電的平均等待時間低于另一者。但兩者在服務(wù)強度為1附近產(chǎn)生交叉點,在這一交叉點后,集中式充電的平均等待時間會高于另一者。
圖10 系統(tǒng)容量為6時的平均等待時間對比Fig.10 Comparison of average waiting time when system capacity is 6
從圖11~圖13中可以看到,隨著服務(wù)強度的增加,與4.1節(jié)類似。服務(wù)強度較低時,若以平均等待時間作為評判指標,集中式充電比較有優(yōu)勢。但隨著服務(wù)強度的增加,分布式充電的優(yōu)勢逐漸體現(xiàn)。通過數(shù)值分析中的二分法,取區(qū)間為(1.000 1,1.125),精度為0.000 1,可以求解出每一個交叉點的橫坐標,如表3所示。
圖11 系統(tǒng)容量為7時的平均等待時間對比Fig.11 Comparison of average waiting time when system capacity is 7
圖12 系統(tǒng)容量為8時的平均等待時間對比Fig.12 Comparison of average waiting time when system capacity is 8
表3 2種充電方式平均等待時間曲線的交叉點Table 3 Intersection of average waiting time curves of two charging methods
1) 在服務(wù)強度的區(qū)間為[0,2]時,隨著服務(wù)強度的增強,評價指標對應(yīng)的曲線存在交叉點。交叉點前,即服務(wù)強度較低的情形下,集中式充電的兩項評價指標優(yōu)于分布式充電。但在交叉點后,隨著服務(wù)強度的增大,分布式充電的兩項評價指標優(yōu)于集中式充電。
2) 對于不同充電平臺數(shù)量和系統(tǒng)容量給出了選擇集中式充電和分布式充電的交叉參考點,對蜂群無人機充電排隊提供重要的參考。