[發(fā)明專利]一種針對(duì)室內(nèi)信號(hào)源部署方案篩選的指紋定位快速實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910796635.X
• 申請(qǐng)日: 2019-08-27
• 公開(kāi)（公告）號(hào): CN110830938B
• 公開(kāi)（公告）日: 2021-02-19
• 發(fā)明（設(shè)計(jì)）人: 趙儉輝;鐘姍杉;蔡波
• 申請(qǐng)（專利權(quán)）人: 武漢大學(xué)
• 主分類號(hào): H04W4/33
• 分類號(hào): H04W4/33;H04W64/00;G06F15/163
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 魯力

本發(fā)明涉及一種針對(duì)室內(nèi)信號(hào)源部署方案篩選的指紋定位快速實(shí)現(xiàn)方法。首先生成部署方案對(duì)應(yīng)的子指紋庫(kù)，其中生成子指紋庫(kù)時(shí)調(diào)用多核并行嵌套哈希查找的多層級(jí)加速方法，然后定位所有測(cè)試點(diǎn)位置并確定部署方案定位誤差，定位過(guò)程中調(diào)用多核并行嵌套哈希查找+SIMD組合的多層級(jí)加速方法，最后從所有的信號(hào)源部署方案中篩選得到最優(yōu)方案。本發(fā)明運(yùn)用SIMD技術(shù)，在RSS距離計(jì)算過(guò)程中實(shí)現(xiàn)多數(shù)據(jù)并行計(jì)算，提升了定位速度。本發(fā)明運(yùn)用多核或多GPU技術(shù)，并行處理多個(gè)參考點(diǎn)RSS以及多個(gè)測(cè)試點(diǎn)定位，大大提升了計(jì)算速度。本發(fā)明運(yùn)用哈希查找算法，解決指紋庫(kù)數(shù)組下標(biāo)查找信號(hào)源ID標(biāo)識(shí)時(shí)由于頻繁查找導(dǎo)致耗時(shí)過(guò)久的問(wèn)題。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)應(yīng)用技術(shù)與室內(nèi)定位技術(shù)領(lǐng)域，主要是將SIMD指令、多核或多GPU并行、以及哈希查找算法進(jìn)行耦合，形成一種針對(duì)室內(nèi)信號(hào)源部署方案篩選的指紋定位快速實(shí)現(xiàn)方法。

背景技術(shù)

目前，全球定位系統(tǒng)GPS已經(jīng)被應(yīng)用到人們生活中的各個(gè)方面。雖然GPS在戶外世界中廣泛活躍著，但到了室內(nèi)，由于室內(nèi)復(fù)雜的環(huán)境以及眾多的障礙物，GPS的信號(hào)衰減十分嚴(yán)重，難以精確定位，因此室內(nèi)定位就成為了目前人們研究的熱門問(wèn)題。

室內(nèi)定位技術(shù)可采用多種信號(hào)進(jìn)行定位，例如WIFI定位技術(shù)，藍(lán)牙定位技術(shù)，紅外線定位技術(shù)，ZigBee定位技術(shù)等等。以廣泛應(yīng)用WIFI定位技術(shù)為例，目前大多數(shù)室內(nèi)布設(shè)了多個(gè)WIFI設(shè)備，作為無(wú)線訪問(wèn)接入點(diǎn)AP。每一個(gè)AP都有一個(gè)獨(dú)一無(wú)二的MAC地址。許多移動(dòng)終端如手機(jī)，平板等，可掃描收集周圍AP信號(hào)。移動(dòng)終端收集到各個(gè)AP信號(hào)后，將AP所對(duì)應(yīng)的MAC地址，以及AP信號(hào)強(qiáng)度，通過(guò)某種算法確定移動(dòng)終端位置。

室內(nèi)定位方法可劃分為四大類：傳播模型、區(qū)域單元、指紋法和多邊形方法。其中又以指紋法最為廣泛應(yīng)用。指紋法顧名思義，就是根據(jù)每個(gè)人的指紋有著獨(dú)一無(wú)二的特征，將指紋與室內(nèi)的某個(gè)位置關(guān)聯(lián)起來(lái)。某個(gè)位置接收或者發(fā)送信號(hào)，那么這個(gè)信號(hào)的特征可以作為該位置的指紋。具體來(lái)說(shuō)指紋法分為離線建庫(kù)階段以及在線定位階段。離線建庫(kù)階段主要是：在已知具體位置的參考點(diǎn)記錄該點(diǎn)所收到各個(gè)AP的信號(hào)值，這些信號(hào)值將組成該參考點(diǎn)的指紋，可用RSS表示。所有參考點(diǎn)的RSS將組成一個(gè)指紋庫(kù)。在線定位階段主要是：利用移動(dòng)設(shè)備在不同的測(cè)試點(diǎn)記錄該點(diǎn)的RSS，并到指紋庫(kù)中搜索與之最相近的RSS。算法根據(jù)最近RSS對(duì)應(yīng)的參考點(diǎn)位置，便可以推測(cè)出測(cè)試點(diǎn)的具體位置。

在實(shí)際應(yīng)用過(guò)程，人們通常希望以較少成本獲取較高的精度定位。因此，指紋算法會(huì)用于測(cè)試不同成本部署方案的定位誤差。然而，部署方案成百上千，因此對(duì)應(yīng)也需要頻繁運(yùn)行指紋算法。這將會(huì)耗費(fèi)巨大的時(shí)間，拖延評(píng)價(jià)選取方案進(jìn)度。基于上述原因，本發(fā)明提出一種針對(duì)室內(nèi)信號(hào)源部署方案篩選的指紋定位快速實(shí)現(xiàn)方法。

由于指紋法的在線定位階段需要進(jìn)行高維向量計(jì)算，因此本發(fā)明采用SIMD技術(shù)進(jìn)行加速優(yōu)化。SIMD是英文SingleInstruction Multiple Data的縮寫，指的是單指令處理多數(shù)據(jù)技術(shù)，可以同時(shí)對(duì)多個(gè)數(shù)據(jù)執(zhí)行相同操作，以此達(dá)到空間上的并行性。將SIMD運(yùn)用到高維向量運(yùn)算后，程序從原本一次計(jì)算指令只能操作一個(gè)維度的數(shù)值，提升到了兩個(gè)或四個(gè)維度。

參考點(diǎn)與測(cè)試點(diǎn)RSS都是事先采集記錄好的，數(shù)據(jù)之間無(wú)操作關(guān)聯(lián)性。因此，在篩選信號(hào)源部署方案中，某些操作可以并行操作，如對(duì)所有測(cè)試點(diǎn)定位確定部署方案定位誤差。本發(fā)明采用多核或多GPU并行編程技術(shù)實(shí)現(xiàn)并行加速。多核并行編程技術(shù)，就是將程序中的可并行的線程交托給多個(gè)核心處理，從而提高程序的運(yùn)行速度

由于在測(cè)試點(diǎn)定位過(guò)程中，需要調(diào)用查找算法，根據(jù)匹配RSS的序號(hào)確定對(duì)應(yīng)的參考點(diǎn)ID，進(jìn)而獲取參考點(diǎn)位置坐標(biāo)。但是，普通查找算法如順序查找，二分查找等，時(shí)間復(fù)雜度偏高。因此，本發(fā)明采用哈希查找算法，利用空間換時(shí)間的思想，實(shí)現(xiàn)時(shí)間復(fù)雜度為O(1)的查找。

發(fā)明內(nèi)容

針對(duì)上述存在的技術(shù)問(wèn)題，本發(fā)明的目的是提供一種針對(duì)室內(nèi)信號(hào)源部署方案篩選的指紋定位快速實(shí)現(xiàn)方法，以便于快速測(cè)評(píng)并確定最終部署方案。