[發明專利]一種針對室內信號源部署方案篩選的指紋定位快速實現方法

有效

• 申請號: 201910796635.X
• 申請日: 2019-08-27
• 公開（公告）號: CN110830938B
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 趙儉輝;鐘姍杉;蔡波
• 申請（專利權）人: 武漢大學
• 主分類號: H04W4/33
• 分類號: H04W4/33;H04W64/00;G06F15/163
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魯力

1.一種針對室內信號源部署方案篩選的指紋定位快速實現方法,其特征在于,包括:

步驟1、生成部署方案對應的子指紋庫，其中生成子指紋庫時調用多核并行嵌套哈希查找的多層級加速方法；包含以下子步驟：

步驟1.1首先采集相關數據并生成總指紋庫；在室內部署n個AP，作為部署方案的選擇范圍；每個AP都有唯一的ID標識；接著，取這n個AP位置作為測試點和參考點；其中，在每個測試點收集n個AP信號值作為該測試點的RSS_t，寫作(r₁,r₂,…r_n)行向量形式；每個參考點收集n個AP信號值，作為該參考點的RSS_r，寫作(R₁,R₂,…R_n)的行向量形式，并匯集成大小為n*n的總指紋庫；總指紋庫具體形式如下：

步驟1.2確定某個部署方案；在n個AP里選取m個AP作為部署方案,m≤n，并記錄這m個AP的ID；

步驟1.3針對確定的部署方案，利用多核或多GPU并行加速遍歷總指紋庫中每行，并行加工多個RSS_r，得到部署方案對應的子指紋庫；以下子步驟針對一個RSS_r工作；

步驟1.3.1利用哈希查找算法優化加速RSS_r加工；根據部署方案中AP成員的ID，查找對應的m個AP信號值；為了加速AP信號值R_i的查找，根據ID與RSS_r中對應元素下標i映射關系，確定哈希函數Hash(key)，構造哈希表；其中，取ID值為key值，Hash(ID)輸出的是ID對應的元素下標i；這樣，便可以直接將ID代入到哈希表中，實現時間復雜度為O(1)的查找；

步驟1.3.2根據上一步依次查找出來m個R_i，按照下標i遞增順序組成部署方案下的參考點RSS′_r，寫作(R′₁,R′₂,…R′_m)行向量形式；

步驟1.3.3所有的RSS′_r匯集成大小為n*m的子指紋庫；子指紋庫具體形式如下：

其中R′_i′j表示第i′個參考點接收到第j個AP的信號值；

步驟2、定位所有測試點位置并確定部署方案定位誤差，定位過程中調用多核并行嵌套哈希查找+SIMD組合的多層級加速方法；包括以下子步驟：

步驟2.1利用多核并行加速遍歷每個測試點，并行多個測試點位置定位；以下子步驟針對一個測試點工作；

步驟2.1.1讀取測試點RSS_t；

步驟2.1.2利用哈希查找算法優化加速RSS_t加工；同子指紋庫建立一樣，RSS_t需要篩選出部署方案中m個對應AP信號值；這里的過程與步驟1.3.1，1.3.2一致，不進行多余講解；最后構建部署方案下的測試點RSS′_t，寫作(r′₁,r′₂,…r′_m)行向量形式；

步驟2.1.3遍歷子指紋庫，將RSS′_t與庫中每行RSS′_r進行距離計算；其中距離記為distance_row,row為RSS′_r在子指紋庫的行號；以下子步驟針對一行RSS′_r與該RSS′_t距離計算工作；

步驟(1)利用SIMD加速RSS_r′與RSS_t′距離計算；距離計算公式具體定義為根據AVX指令集，利用三個256位通用寄存器x，y，z；其中前兩個寄存器分別存儲4個下標連續的R_i′和r_i′,R_i′和r_i′的數據類型設為double,占64位，第三個寄存器存儲結果，初始存儲值為0；對于RSS_r′與RSS_t′中前維的元素有如下子步驟，其中子步驟針對一組4個連續維度的元素工作；

①從RSS_r′與RSS_t′分別加載4個連續維度的元素到x，y；

②使用_mm256_sub_pd計算x與y的數據差值，并存入256位寄存器temp；

③使用_mm256_mul_pd計算temp的平方值，并將結果再次存入temp；

④使用_mm256_add_pd計算temp與z的和，并將結果存入z；

步驟(2)將z中256位數據平分4個64位長的子數據，這些子數據轉為double類型后相加得到結果result1；

步驟(3)若m為4的倍數，那么上一步的結果result1設為distance值；否則，將不被整除的部分按照普通方式計算，得到結果result2；那么distance值為result1與result2之和；

步驟2.1.4找出子指紋庫中的k個最近距離的distance_row；

步驟2.1.5利用哈希查找算法根據最近距離加速查找對應參考點位置；由于參考點位置取AP位置，所以參考點位置需要所取的AP的ID來確定；因此需要依次遍歷上一步k個distance_row，依據其中行號下標row與ID的映射關系，查找出對應ID才能獲取位置信息；依據映射關系，確定哈希函數Hash(key)，建立對應的哈希表；其中，取行號下標row值為key值，Hash(row)輸出的是row對應的ID；這樣，便可以直接將行號row代入到哈希表中，實現時間復雜度為O(1)的查找；

步驟2.1.6從k個參考點位置綜合計算出測試點位置；

步驟2.1.7計算預測的位置與實際位置的誤差；并將誤差存入誤差數組rate；

步驟2.2將誤差數組rate中所有元素相加求和再求平均，得到該部署方案的平均定位誤差；

步驟3、從所有的信號源部署方案中篩選得到最優方案，具體是以部署方案平均定位誤差為評價標準，對所有信號源部署方案進行篩選，得到最優方案。