王鈺寧，劉曉霞，李 芳

(1 四川水利職業(yè)技術(shù)學(xué)院信息工程系，四川崇州 611231;2 重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044)

0 引言

隨著無(wú)人機(jī)(unmanned aerial vehicular,UAV)的快速發(fā)展，無(wú)線無(wú)人機(jī)網(wǎng)絡(luò)(UAV network,UN)[1-2]已成為空間區(qū)域數(shù)據(jù)采集的有效平臺(tái)。一個(gè)UN可能有幾個(gè)至上百個(gè)UAV組成。實(shí)質(zhì)上，UN是漂浮在空中移動(dòng)自組織網(wǎng)絡(luò)。然而，與傳統(tǒng)的移動(dòng)自組織網(wǎng)絡(luò)不同，由于UAV節(jié)點(diǎn)的三維空間移動(dòng)，UN的拓?fù)浣Y(jié)構(gòu)更為復(fù)雜。

部署UN的目的在于收集監(jiān)測(cè)空間內(nèi)的數(shù)據(jù)。因此，對(duì)空間區(qū)域?qū)崿F(xiàn)無(wú)縫、連續(xù)網(wǎng)絡(luò)覆蓋是基本要求。據(jù)此，估計(jì)維持網(wǎng)絡(luò)覆蓋的臨界節(jié)點(diǎn)密度(critical node density,CND)成為UN的研究熱點(diǎn)之一[3]。如果節(jié)點(diǎn)密度高于CND，則就能保持網(wǎng)絡(luò)覆蓋。但是，由于UN是一個(gè)三維隨機(jī)網(wǎng)絡(luò)，估計(jì)CND是一項(xiàng)挑戰(zhàn)工作。此外，由于不同類型UAV的覆蓋區(qū)域不同，這些不同類型的UAV構(gòu)成的網(wǎng)絡(luò)屬異構(gòu)網(wǎng)絡(luò)，這又增添了估計(jì)CND的難度。

為此，對(duì)無(wú)人機(jī)網(wǎng)絡(luò)的覆蓋性能進(jìn)行分析。將監(jiān)測(cè)進(jìn)行六邊形和正方形網(wǎng)格化，再結(jié)合滲透理論，推導(dǎo)維持監(jiān)測(cè)區(qū)域內(nèi)無(wú)縫、連續(xù)覆蓋的單網(wǎng)格的節(jié)點(diǎn)密度。并利用試驗(yàn)數(shù)據(jù)分析所推導(dǎo)的單網(wǎng)格的節(jié)點(diǎn)密度的準(zhǔn)確性。

1 系統(tǒng)模型

考慮如圖1所示的系統(tǒng)模型。UN內(nèi)有m個(gè)UAV組成，第i個(gè)UAV表示為ni，且i=1,2,…,m。令ri表示節(jié)點(diǎn)ni的通信半徑。每個(gè)UAV在地面上覆蓋區(qū)域?yàn)閳A形區(qū)域[4]。對(duì)于節(jié)點(diǎn)ni，它的覆蓋區(qū)域是以其位置ci為圓心，半徑為Ri。為了表述簡(jiǎn)單，將此圓心稱為節(jié)點(diǎn)的覆蓋區(qū)足心。

圖1 系統(tǒng)模型(m=3)

令(xi,yi,zi)表示節(jié)點(diǎn)ni的三維位置坐標(biāo)。由于覆蓋區(qū)域是投射至地面上的區(qū)域，其是二維區(qū)域，因此, 覆蓋區(qū)足心ci的位置為(xi,yi,0)。

在理想情況下，所有節(jié)點(diǎn)的覆蓋半徑相等，即Ri=R。由這些節(jié)點(diǎn)構(gòu)成的UN也稱為同構(gòu)網(wǎng)絡(luò)[5]。此外，為了保證對(duì)監(jiān)測(cè)區(qū)域的連續(xù)、無(wú)縫覆蓋，節(jié)點(diǎn)的覆蓋區(qū)域應(yīng)存在重疊。

為對(duì)無(wú)人機(jī)網(wǎng)絡(luò)的覆蓋性能進(jìn)行分析，需要估計(jì)維持UN的連續(xù)、無(wú)縫覆蓋的節(jié)點(diǎn)密度(稱為臨界節(jié)點(diǎn)密度)。

2 覆蓋性能分析模型

2.1 基于六邊形覆蓋的覆蓋區(qū)足心距離

先將覆蓋的圓形區(qū)域近似為六邊形，如圖2所示。圖中給出了兩個(gè)節(jié)點(diǎn)的覆蓋區(qū)域剛達(dá)到重疊的情況(稱臨界重疊)。當(dāng)節(jié)點(diǎn)的覆蓋區(qū)域達(dá)到臨界重疊時(shí)，這兩個(gè)節(jié)點(diǎn)的覆蓋區(qū)足心間最大距離記為dmax。即如果兩節(jié)點(diǎn)的覆蓋區(qū)足心在平面上的距離大于dmax，則它們的覆蓋區(qū)域不會(huì)重疊。

圖2 基于六邊形近似的臨界重疊

令σ表示六邊形的邊長(zhǎng)，依據(jù)幾何理論可得：

(1)

由式(1)可知，基于六邊形近似的臨界重疊條件，六邊形的邊長(zhǎng)σ與覆蓋半徑R相等。再利用式(1)，并結(jié)合圖2模型，可推導(dǎo)dmax為：

(2)

2.2 基于正邊形覆蓋的覆蓋區(qū)足心距離

與2.1節(jié)類似，推導(dǎo)正邊形的邊長(zhǎng)σ與覆蓋半徑R的關(guān)系：

(3)

如圖3所示，計(jì)算在正邊形挖掘的臨界重疊條件下的dmax：

圖3 基于正邊形近似的臨界重疊

(4)

2.3 基于網(wǎng)格化的節(jié)點(diǎn)密度的估計(jì)

先將監(jiān)測(cè)區(qū)域進(jìn)行網(wǎng)格化，再推導(dǎo)單網(wǎng)格內(nèi)的節(jié)點(diǎn)密度與覆蓋區(qū)域的關(guān)系，即得出維持監(jiān)測(cè)區(qū)域無(wú)縫覆蓋時(shí)的網(wǎng)格-節(jié)點(diǎn)密度(lattice-node density,LND)。

2.3.1 基于六邊形網(wǎng)格

依據(jù)六邊形網(wǎng)格模型[6]，將監(jiān)測(cè)區(qū)域進(jìn)行六邊形網(wǎng)格化，如圖4所示。如果網(wǎng)格包含一個(gè)覆蓋區(qū)足心，則該網(wǎng)格為綠色的，表示該網(wǎng)格被全覆蓋。

圖4 基于六邊形網(wǎng)格

依據(jù)滲透理論，六邊形網(wǎng)格的滲透的臨界概率為ρ0。類似的，令ρ表示泊松過(guò)程的節(jié)點(diǎn)密度。要實(shí)現(xiàn)滲透，需滿足[7]：

1-exp(-ρA)>ρ0

(5)

依據(jù)式(5)，可得出：

(6)

(7)

結(jié)合式(6)和式(7)可得到ρ的值：

(8)

若ρ0=0.7[7],則可計(jì)算六邊形覆蓋條件下的LND值ρh：

(9)

(10)

結(jié)合式(6)和式(10)可得到ρ的值：

(11)

若ρ0=0.7[7],則可計(jì)算在正邊形覆蓋條件下的LND值ρs:

(12)

2.3.2 基于正邊形網(wǎng)格

圖5 基于正方形網(wǎng)格

(13)

令ρ0表示正邊形網(wǎng)格的滲透的臨界概率，ρ表示泊松過(guò)程的節(jié)點(diǎn)密度。要實(shí)現(xiàn)滲透，需滿足[7]：

(14)

結(jié)合式(13)和式(14)，可得：

(15)

在正邊形網(wǎng)格條件下，依據(jù)文獻(xiàn)[7-8]，ρ0=0.59。結(jié)合式(15)，可得：

(16)

(17)

結(jié)合式(17)和式(14)可得：

(18)

2.4 LND與覆蓋間關(guān)系

從所推導(dǎo)的4個(gè)LND的臨界值可知，最小的為1.5/R2，最大為3/R2。因此，若單網(wǎng)格內(nèi)的節(jié)點(diǎn)密度小于1.5/R2時(shí)，不能保證監(jiān)測(cè)區(qū)域的全覆蓋；若單網(wǎng)格內(nèi)的節(jié)點(diǎn)密度達(dá)到3/R2時(shí)，就能保證監(jiān)測(cè)區(qū)域的全覆蓋。

3 性能分析

3.1 試驗(yàn)參數(shù)

引用MATLAB R2016a軟件建立仿真平臺(tái)，驗(yàn)證推導(dǎo)的臨界節(jié)點(diǎn)密度的準(zhǔn)確性?？紤]如圖1所示的模型，監(jiān)測(cè)區(qū)域?yàn)?0 m×50 m。所有節(jié)點(diǎn)的覆蓋區(qū)域的半徑R=7 m，通信半徑r=7 m。令ρ表示單網(wǎng)格內(nèi)節(jié)點(diǎn)的密度，且ρ服從泊松點(diǎn)過(guò)程，即ρ也可理解成節(jié)點(diǎn)的到達(dá)率。

3.2 ρ=3/R2的網(wǎng)絡(luò)覆蓋性能

圖6給出ρ=3/r2時(shí)，節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的覆蓋性能。由于r=R，則單網(wǎng)格內(nèi)的節(jié)點(diǎn)密度達(dá)到ρ=3/R2, 則可實(shí)現(xiàn)全覆蓋。而圖6的覆蓋圖也證實(shí)此點(diǎn)。在50 m×50 m內(nèi)無(wú)空白區(qū)(未覆蓋的區(qū)為空白區(qū))。

圖6 ρ=3/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

3.3 ρ=2.25/R2的網(wǎng)絡(luò)覆蓋性能

圖7給出ρ=2.25/R2時(shí)，節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的覆蓋性能。由圖可知，當(dāng)ρ=2.25/R2時(shí)，監(jiān)測(cè)區(qū)域幾乎被全部覆蓋，只有少數(shù)白點(diǎn)。這說(shuō)明只有少數(shù)位置未被覆蓋。原因在于：ρ=2.25/R2只滿足了正邊形網(wǎng)格條件下的正邊形覆蓋，在監(jiān)測(cè)區(qū)域內(nèi)存在少數(shù)點(diǎn)位置未能被覆蓋。

圖7 ρ=2.25/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

3.4 ρ=2/R2的網(wǎng)絡(luò)覆蓋性能

圖8給出ρ=2/R2時(shí)，節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的覆蓋性能。相比于圖7(ρ=2.25/R2), 圖8的未覆蓋區(qū)域更多。在50 m×50 m的監(jiān)測(cè)區(qū)域內(nèi)存在3處空白地點(diǎn)。原因在于：ρ=2/R2略小于ρ=2.25/R2。

圖8 ρ=2/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

3.5 ρ=1.5/R2的網(wǎng)絡(luò)覆蓋性能

圖9給出ρ=1.5/R2時(shí)，節(jié)點(diǎn)中對(duì)監(jiān)測(cè)區(qū)域的覆蓋性能。ρ=1.5/R2是圖5中推導(dǎo)出來(lái)的4個(gè)LND臨界值中的最小值。因此，相比于圖6～圖9中未覆蓋區(qū)域面積較大，但是整個(gè)監(jiān)測(cè)區(qū)域基本上都覆蓋，這符合預(yù)期。

圖9 ρ=1.5/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

3.6 ρ=1.3/R2的網(wǎng)絡(luò)覆蓋性能

圖10給出ρ=1.3/R2時(shí)的網(wǎng)絡(luò)覆蓋性能。ρ=1.3/R2小于圖5推導(dǎo)的LND臨界值的最小值(ρ=1.5/R2)，無(wú)法對(duì)檢測(cè)區(qū)域?qū)嵤┤采w。相比于圖10，ρ=1.3/R2留下更多的未覆蓋區(qū)域。

圖10 ρ=1.3/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

3.7 ρ=1.1/R2的網(wǎng)絡(luò)覆蓋性能

ρ=1.1/R2時(shí)對(duì)監(jiān)測(cè)區(qū)域的覆蓋情況如圖11所示。由于ρ=1.1/R2，未能達(dá)到LND的臨界值，在監(jiān)測(cè)區(qū)域內(nèi)留下較大的未覆蓋區(qū)域。

圖11 ρ=1.1/R2時(shí)監(jiān)測(cè)區(qū)域的覆蓋情況

通過(guò)上述測(cè)試，不難發(fā)現(xiàn)：當(dāng)節(jié)點(diǎn)密度ρ達(dá)到LND的臨界值(4個(gè)值)，基本上能夠?qū)崿F(xiàn)對(duì)監(jiān)測(cè)區(qū)域的全覆蓋。若未達(dá)到LND臨界值，就無(wú)法實(shí)現(xiàn)全覆蓋。這說(shuō)明所推導(dǎo)的LND臨界值具有重要的參考值，也側(cè)面反映了LND臨界值能夠準(zhǔn)確地估計(jì)對(duì)監(jiān)測(cè)區(qū)域的覆蓋情況。

4 小結(jié)

對(duì)無(wú)人機(jī)網(wǎng)絡(luò)的覆蓋問(wèn)題進(jìn)行分析，并提出基于滲透理論的節(jié)點(diǎn)密度估計(jì)策略。將覆蓋區(qū)域進(jìn)行網(wǎng)格化，并估計(jì)單網(wǎng)格的節(jié)點(diǎn)密度與實(shí)現(xiàn)區(qū)域的全覆蓋間關(guān)系，推導(dǎo)了實(shí)現(xiàn)覆蓋的單網(wǎng)格的節(jié)點(diǎn)密度的臨界值。通過(guò)試驗(yàn)分析，證實(shí)了所推導(dǎo)結(jié)果的準(zhǔn)確性。