[發明專利]一種基于局部搜索算法的室內無線設備部署方法及系統

有效

• 申請號: 202111385992.0
• 申請日: 2021-11-22
• 公開（公告）號: CN114125711B
• 公開（公告）日: 2022-10-14
• 發明（設計）人: 蔡少偉;雷震東;何兵
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: H04W4/021
• 分類號: H04W4/021;H04W4/33;H04W16/18;H04W16/22
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 李文濤

1.一種基于局部搜索算法的室內無線設備部署方法，其特征在于，包括以下步驟：

1)將室內目標區域按照網格進行劃分，網格線的每個交點作為被至少k個無線設備信號覆蓋的目標點，并確定目標點的坐標；

2)提取目標區域的三維空間結構信息和障礙物的坐標信息，處理后得到目標區域的結構信息圖；

3)根據目標區域的結構信息圖構建針對每一個目標點的覆蓋集合，覆蓋集合中的元素為候選部署點，該候選部署點為無線設備信號覆蓋該覆蓋集合對應的目標點的其他所有目標點；其中，確定候選部署點的步驟為：根據目標點的坐標，計算任意兩目標點之間的距離L；根據無線設備的信號覆蓋區域半徑D，信號傳播中遇到每個障礙物后的衰減距離d，以及兩點之間的障礙物個數，如果L≤D-m*d，則將該兩目標點判定為互相的候選部署點，加入覆蓋集合；

4)從覆蓋集合中選擇任意兩個候選部署點，要求兩個候選部署點之間的距離大于一預設值；

5)以步驟3)和4)作為兩個約束條件，通過優化求解算法從全部目標點的覆蓋集合中選取最少的候選部署點，并作為無線設備部署的部署點；優化求解算法為：首先以全部覆蓋集合中的候選部署點作為變量，通過隨機或者貪心賦予每個變量一權重值，構造一個初始解；然后算法進入一個循環，在循環內部迭代改進當前解，直到達終止條件，返回找到的最優解；其中，算法在循環的過程中，如果找到一個更優的解，則更新當前最優解，否則算法會選擇一個變量翻轉并賦予權重值；如果算法進入局部最優，無法選擇變量時，則根據動態加權機制weighting-PMS更新權重，隨機挑選一個變量并翻轉其賦予的權重值。

2.如權利要求1所述的方法，其特征在于，根據目標區域的結構信息圖中的兩目標點之間的連線段與障礙物線段是否相交，來判斷兩個目標點之間是否存在障礙物。

3.如權利要求2所述的方法，其特征在于，通過快速過濾法或跨立實驗法，來判斷兩個目標點之間是否存在障礙物；其中，

快速過濾法為：若兩目標點之間的連線段和障礙物線段這兩條線段在x軸方向上不相交或在y軸方向上不相交，則兩條線段不相交，否則相交；

跨立實驗法：若兩目標點之間的連線段和障礙物線段這兩條線段跨立，跨立是指一條線段的兩個端點在另一條線段的兩端，則該兩條線段相交；通過向量乘積來判斷是否跨立，方法為：對于兩條線段AB和CD，如果以下兩個向量式子(CA×CD)*(CB×CD)＝0且(AC×AB)*(AD×AB)＝0，其中×表示向量乘積，*表示數字乘積，則判定兩條線段相交。

4.如權利要求1所述的方法，其特征在于，優化求解算法包括動態加權機制和啟發式函數，啟發式函數優選局部搜索算法。