[發明專利]一種基于無向圖的無人機基站部署方法

有效

• 申請號: 202011219855.5
• 申請日: 2020-11-04
• 公開（公告）號: CN112351438B
• 公開（公告）日: 2022-12-02
• 發明（設計）人: 許娟;武迪
• 申請（專利權）人: 南京航空航天大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04B7/185
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于無向圖的無人機基站部署方法，其特征在于，包括以下步驟：

步驟1，建立無人機通信的系統模型，具體如下：

(1)任意時刻，無人機的位置信息為：u(t)＝(x_u(t)，y_u(t))，其中x_u(t)為任意時刻t下無人機橫坐標的位置，y_u(t)為任意時刻t下無人機縱坐標的位置，初始時刻，無人機的坐標為坐標系原點；地面終端的位置信息為：q_i＝(x_i，y_i)，其中x_i，y_i分別為地面終端i在坐標系上的橫坐標和縱坐標信息；

(2)任意地面終端i，j之間距離為Distance(i，j)：

其中，x_i，y_i為地面終端i的橫坐標與縱坐標信息，x_j，y_j為地面終端j的橫坐標與縱坐標信息；

(3)無人機與地面終端之間最遠的水平通信距離r為：

r²＝R²-H²

其中，R為無人機和各地面終端之間允許的最遠通信距離，H為無人機固定飛行高度；

(4)最小化無人機基站數目K的問題，可以用公式化描述為：

其中，q_i為地面終端的位置信息，u_j為無人機的位置信息，N為地面終端的數目，i為地面終端的編號，j為無人機編號；

(5)根據地面終端之間的距離信息構建無向圖，并確定無向圖中任意頂點的度數，基于無向圖中頂點之間的相鄰信息，初步判斷地面終端能否被一個無人機基站所覆蓋；

步驟2，對無向圖中度數為0或1的頂點進行預處理，對相應的地面終端部署無人機基站，減少步驟3的工作量；具體包括：基于系統模型，對無向圖中度數為0和1的頂點進行預處理，循環執行步驟(1)-(2)，循環終止條件：無向圖G為空圖或無向圖中所有點的度數大于等于2；

(1)尋找無向圖G中度為0的孤立點，即該點Degree(i)＝0；以這些孤立點為中心部署無人機基站，并將這些點從無向圖G中刪除；

(2)尋找無向圖G中是否存在度數為1的懸掛頂點；對于G中的每個懸掛頂點和其唯一連接的頂點組成的每個樹結構，執行以下操作：(2a)對樹結構中的父節點與任意一個葉子節點部署一個無人機基站，基站中心為它們的質心，余下每個葉子節點分別單獨設置無人機基站，中心為它們本身；

步驟3，隨機構造若干個無人機基站，并不斷調整合并無人機基站，減少基站的數目；所述不斷調整合并無人機基站，包括：根據無向圖中任意不相鄰的頂點對應的地面終端不能被一個無人機基站所覆蓋的結論，先隨機構造若干個一階及二階完全子圖，之后通過檢驗頂點是否構成完全子圖，檢驗頂點構成的最小包圍圓的直徑是否大于無人機基站的直徑的方法，不斷調整無人機基站的范圍，合并無人機基站，優化部署方案，具體實施方案如下：

(1)將無向圖G中相鄰的點，兩兩組成若干個二階完全子圖，如果頂點無法組成二階子圖，則其單獨組成一個一階完全子圖，基于這些完全子圖，設置無人機基站，得到無人機基站放置的一個初步方案；

(2)對部署方案進行不斷優化，依照無向圖G中頂點度數大小，從小到大順序遍歷G中所有頂點，執行過程(2a)與(2b)，直到遍歷完所有的頂點；

(2a)假設任意選取的頂點為a，a所屬于的無人機基站為MBS_a，{SAME_a}表示為與a在相同無人機基站的頂點的集合，{Connection_a}表示為與a相鄰頂點的集合，若a所屬的無人機基站被處理過，則跳過a點，否則向下執行過程2b)；

(2b)依照度數順序，從小到大遍歷集合{Connection_a}-{SAME_a}中所有的頂點，執行過程(2b1)-(2b3)，直到遍歷完所有{Connection_a}-{SAME_a}中的點；

(2b1)假設任意選取的頂點為z，如果z與{SAME_a}中所有頂點均相鄰，則繼續，否則跳過頂點z；

(2b2)如果z所屬的無人機基站MBS_z中頂點的數目小于或等于MBS_a，則繼續，否則跳過頂點z；

(2b3)如果z與a，以及{SAME_a}中所有點形成的最小包圍圓的半徑不大于r，則將z從z所屬于的無人機基站MBS_z中刪除，并將z添加到a點目前所屬的無人機基站MBS_a中，否則跳過z點；

步驟4，循環執行S3，直到達到以下終止條件：1).達到最大循環次數；2).連續m次最優解未發生變化，其中m為5。