基于滲透理論的無人機網絡的覆蓋性能分析

王鈺寧，劉曉霞，李 芳

(1 四川水利職業技術學院信息工程系，四川崇州 611231;2 重慶大學計算機學院，重慶 400044)

0 引言

隨著無人機(unmanned aerial vehicular,UAV)的快速發展，無線無人機網絡(UAV network,UN)[1-2]已成為空間區域數據采集的有效平臺。一個UN可能有幾個至上百個UAV組成。實質上，UN是漂浮在空中移動自組織網絡。然而，與傳統的移動自組織網絡不同，由于UAV節點的三維空間移動，UN的拓撲結構更為復雜。

部署UN的目的在于收集監測空間內的數據。因此，對空間區域實現無縫、連續網絡覆蓋是基本要求。據此，估計維持網絡覆蓋的臨界節點密度(critical node density,CND)成為UN的研究熱點之一[3]。如果節點密度高于CND，則就能保持網絡覆蓋。但是，由于UN是一個三維隨機網絡，估計CND是一項挑戰工作。此外，由于不同類型UAV的覆蓋區域不同，這些不同類型的UAV構成的網絡屬異構網絡，這又增添了估計CND的難度。

為此，對無人機網絡的覆蓋性能進行分析。將監測進行六邊形和正方形網格化，再結合滲透理論，推導維持監測區域內無縫、連續覆蓋的單網格的節點密度。并利用試驗數據分析所推導的單網格的節點密度的準確性。

1 系統模型

考慮如圖1所示的系統模型。UN內有m個UAV組成，第i個UAV表示為ni，且i=1,2,…,m。令ri表示節點ni的通信半徑。每個UAV在地面上覆蓋區域為圓形區域[4]。對于節點ni，它的覆蓋區域是以其位置ci為圓心，半徑為Ri。為了表述簡單，將此圓心稱為節點的覆蓋區足心。

圖1 系統模型(m=3)

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

在理想情況下，所有節點的覆蓋半徑相等，即Ri=R。由這些節點構成的UN也稱為同構網絡[5]。此外，為了保證對監測區域的連續、無縫覆蓋，節點的覆蓋區域應存在重疊。

為對無人機網絡的覆蓋性能進行分析，需要估計維持UN的連續、無縫覆蓋的節點密度(稱為臨界節點密度)。

2 覆蓋性能分析模型

2.1 基于六邊形覆蓋的覆蓋區足心距離

先將覆蓋的圓形區域近似為六邊形，如圖2所示。圖中給出了兩個節點的覆蓋區域剛達到重疊的情況(稱臨界重疊)。當節點的覆蓋區域達到臨界重疊時，這兩個節點的覆蓋區足心間最大距離記為dmax。即如果兩節點的覆蓋區足心在平面上的距離大于dmax，則它們的覆蓋區域不會重疊。

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

令σ表示六邊形的邊長，依據幾何理論可得：

(1)

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

(2)

2.2 基于正邊形覆蓋的覆蓋區足心距離

與2.1節類似，推導正邊形的邊長σ與覆蓋半徑R的關系：

(3)

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

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

(4)

2.3 基于網格化的節點密度的估計

先將監測區域進行網格化，再推導單網格內的節點密度與覆蓋區域的關系，即得出維持監測區域無縫覆蓋時的網格-節點密度(lattice-node density,LND)。

2.3.1 基于六邊形網格

依據六邊形網格模型[6]，將監測區域進行六邊形網格化，如圖4所示。如果網格包含一個覆蓋區足心，則該網格為綠色的，表示該網格被全覆蓋。

圖4 基于六邊形網格

依據滲透理論，六邊形網格的滲透的臨界概率為ρ0。類似的，令ρ表示泊松過程的節點密度。要實現滲透，需滿足[7]：

1-exp(-ρA)>ρ0

(5)

依據式(5)，可得出：

(6)

(7)

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

(8)

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

(9)

(10)

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

(11)

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

(12)

2.3.2 基于正邊形網格

圖5 基于正方形網格

(13)

令ρ0表示正邊形網格的滲透的臨界概率，ρ表示泊松過程的節點密度。要實現滲透，需滿足[7]：

(14)

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

(15)

在正邊形網格條件下，依據文獻[7-8]，ρ0=0.59。結合式(15)，可得：

(16)

(17)

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

(18)

2.4 LND與覆蓋間關系

從所推導的4個LND的臨界值可知，最小的為1.5/R2，最大為3/R2。因此，若單網格內的節點密度小于1.5/R2時，不能保證監測區域的全覆蓋；若單網格內的節點密度達到3/R2時，就能保證監測區域的全覆蓋。

3 性能分析

3.1 試驗參數

引用MATLAB R2016a軟件建立仿真平臺，驗證推導的臨界節點密度的準確性。考慮如圖1所示的模型，監測區域為50 m×50 m。所有節點的覆蓋區域的半徑R=7 m，通信半徑r=7 m。令ρ表示單網格內節點的密度，且ρ服從泊松點過程，即ρ也可理解成節點的到達率。

3.2 ρ=3/R2的網絡覆蓋性能

圖6給出ρ=3/r2時，節點對監測區域的覆蓋性能。由于r=R，則單網格內的節點密度達到ρ=3/R2, 則可實現全覆蓋。而圖6的覆蓋圖也證實此點。在50 m×50 m內無空白區(未覆蓋的區為空白區)。

圖6 ρ=3/R2時監測區域的覆蓋情況

3.3 ρ=2.25/R2的網絡覆蓋性能

圖7給出ρ=2.25/R2時，節點對監測區域的覆蓋性能。由圖可知，當ρ=2.25/R2時，監測區域幾乎被全部覆蓋，只有少數白點。這說明只有少數位置未被覆蓋。原因在于：ρ=2.25/R2只滿足了正邊形網格條件下的正邊形覆蓋，在監測區域內存在少數點位置未能被覆蓋。

圖7 ρ=2.25/R2時監測區域的覆蓋情況

3.4 ρ=2/R2的網絡覆蓋性能

圖8給出ρ=2/R2時，節點對監測區域的覆蓋性能。相比于圖7(ρ=2.25/R2), 圖8的未覆蓋區域更多。在50 m×50 m的監測區域內存在3處空白地點。原因在于：ρ=2/R2略小于ρ=2.25/R2。

圖8 ρ=2/R2時監測區域的覆蓋情況

3.5 ρ=1.5/R2的網絡覆蓋性能

圖9給出ρ=1.5/R2時，節點中對監測區域的覆蓋性能。ρ=1.5/R2是圖5中推導出來的4個LND臨界值中的最小值。因此，相比于圖6～圖9中未覆蓋區域面積較大，但是整個監測區域基本上都覆蓋，這符合預期。

圖9 ρ=1.5/R2時監測區域的覆蓋情況

3.6 ρ=1.3/R2的網絡覆蓋性能

圖10給出ρ=1.3/R2時的網絡覆蓋性能。ρ=1.3/R2小于圖5推導的LND臨界值的最小值(ρ=1.5/R2)，無法對檢測區域實施全覆蓋。相比于圖10，ρ=1.3/R2留下更多的未覆蓋區域。

圖10 ρ=1.3/R2時監測區域的覆蓋情況

3.7 ρ=1.1/R2的網絡覆蓋性能

ρ=1.1/R2時對監測區域的覆蓋情況如圖11所示。由于ρ=1.1/R2，未能達到LND的臨界值，在監測區域內留下較大的未覆蓋區域。

圖11 ρ=1.1/R2時監測區域的覆蓋情況

通過上述測試，不難發現：當節點密度ρ達到LND的臨界值(4個值)，基本上能夠實現對監測區域的全覆蓋。若未達到LND臨界值，就無法實現全覆蓋。這說明所推導的LND臨界值具有重要的參考值，也側面反映了LND臨界值能夠準確地估計對監測區域的覆蓋情況。

4 小結

對無人機網絡的覆蓋問題進行分析，并提出基于滲透理論的節點密度估計策略。將覆蓋區域進行網格化，并估計單網格的節點密度與實現區域的全覆蓋間關系，推導了實現覆蓋的單網格的節點密度的臨界值。通過試驗分析，證實了所推導結果的準確性。