大型商場(chǎng)室內(nèi)定位與導(dǎo)航設(shè)計(jì)

夏晨航 龔俊

摘 要：本文以商場(chǎng)作為模型的設(shè)置室內(nèi)導(dǎo)航，借助于云子實(shí)現(xiàn)位置定位。從實(shí)物定位，到路徑規(guī)劃實(shí)施室內(nèi)導(dǎo)航技術(shù)。

關(guān)鍵詞：空間定位；室內(nèi)導(dǎo)航；移動(dòng)設(shè)備；云子

定位導(dǎo)航給生活帶來了諸多便利，大家對(duì)GPS比較了解，其在室外非常好用，但在室內(nèi)卻不精確，甚至無法使用。為了方便人們?cè)谑覂?nèi)商場(chǎng)快捷找到目的地，本文提出了一個(gè)可行的適用于室內(nèi)定位與導(dǎo)航的方法。

1 室內(nèi)導(dǎo)航的實(shí)物定位

室內(nèi)的貨架按照一定距離鋪設(shè)釋放信號(hào)的云子，并記錄好每個(gè)云子的坐標(biāo)及其編號(hào)，當(dāng)客戶進(jìn)入室內(nèi)后，其攜帶的藍(lán)牙設(shè)備會(huì)接收到多顆云子發(fā)出的RSSI值并得到對(duì)應(yīng)云子的信號(hào)強(qiáng)度，并根據(jù)其中最強(qiáng)的三個(gè)云子得到客戶的位置。分兩種情況陳述。

1.1 位置指紋識(shí)別算法

如客戶所在位置附近阻擋物體較多，云子的RSSI值波動(dòng)幅度較大會(huì)導(dǎo)致定位不精確，為了使定位精確，使用位置指紋識(shí)別算法：首先，根據(jù)合理的測(cè)算設(shè)定參考點(diǎn)，測(cè)出每個(gè)參考點(diǎn)上的信號(hào)強(qiáng)度存入位置指紋數(shù)據(jù)庫，格式為RSSI[R1，R2，R3]。然后，用戶會(huì)在相應(yīng)位置得到RSSI信號(hào)大小，系統(tǒng)會(huì)把此用戶測(cè)得的數(shù)據(jù)與數(shù)據(jù)庫中的信息進(jìn)行 s2=（RR1-R1）2+（RR2-R2）2+（RR3-R3）2的遍歷計(jì)算得到方差值。如果小于一定值（根據(jù)參考點(diǎn)密度而定），則認(rèn)為此地點(diǎn)與位置指紋數(shù)據(jù)庫中的地點(diǎn)匹配，得到相應(yīng)參考點(diǎn)的位置坐標(biāo)。

1.2 圓形定位算法

如沒有符合的參考點(diǎn)，說明用戶此時(shí)位置不是事先確定的阻擋物較多的位置，可以使用圓形算法：通過判斷 iBeacon 的 RSSI 值，如果某個(gè) iBeacon 信號(hào)覆蓋范圍為30米，在它1米處檢測(cè)到的信號(hào)是-50，3米時(shí)是-70…因此，能夠得到用戶離的最近的三個(gè)云子的坐標(biāo)及用戶分別與三個(gè)云子的距離。云子a圓心坐標(biāo)[x1，y1]，覆蓋范圍d1。云子b圓心坐標(biāo)[x2，y2]，覆蓋范圍d2。云子c圓心坐標(biāo)[x3，y3]，覆蓋范圍d3。同時(shí)覆蓋到的那個(gè)點(diǎn)就是用戶的坐標(biāo)。

2 室內(nèi)導(dǎo)航的路徑盤查

2.1 獲取用戶搜索物品的位置和用戶的位置

把每個(gè)云子的位置，綁定到該云子所在位置正對(duì)面的轉(zhuǎn)角坐標(biāo)連上線。用戶搜索物品地點(diǎn)和用戶所在地點(diǎn)連入的云子，都對(duì)應(yīng)一個(gè)位置。這時(shí)，就能知道用戶搜索物品和用戶所在地離哪個(gè)轉(zhuǎn)角坐標(biāo)最近，然后，用室內(nèi)最近路線算法，算出這兩個(gè)轉(zhuǎn)角坐標(biāo)的最短路線，最后把首位轉(zhuǎn)角坐標(biāo)點(diǎn)和搜索物品，用戶坐標(biāo)連接起來，就得到用戶到搜索物品最近的路線。

2.2 室內(nèi)最近路線算法

2.2.1算法思路

設(shè)商場(chǎng)路線是個(gè)連通圖（v，e）（v頂點(diǎn)，e連線），把頂點(diǎn)集合V分成兩個(gè)組，第一組為已求出最短路徑的頂點(diǎn)集合（用a表示，初始時(shí)a中只有用戶轉(zhuǎn)角坐標(biāo)一個(gè)頂點(diǎn)，以后得到一條最短路徑 ， 就將加入到a中，直到b中剩余轉(zhuǎn)角坐標(biāo)全部加入到a中），第二組為剩余的轉(zhuǎn)角坐標(biāo)頂點(diǎn)集合（用b表示），每次求出與a中最后一個(gè)頂點(diǎn)坐標(biāo)直連的最短路徑，把他加入到b中。在加入的過程中，如果加入路徑短于原先就存在的路徑，那么就替換它，如果長(zhǎng)于原先的路徑，就不加入。最后，就能得到起點(diǎn)開始，到除他以外的所有點(diǎn)的最短路徑。

2.2.2算法過程

如果用戶和搜索物品最近轉(zhuǎn)角坐標(biāo)同為一個(gè)，則跳過室內(nèi)最近路線算法，直接畫物品坐標(biāo)—轉(zhuǎn)角坐標(biāo)—用戶坐標(biāo)的連線。

如果用戶和搜索物品的最近轉(zhuǎn)角坐標(biāo)點(diǎn)能直接相連，則也跳過室內(nèi)最近路線算法， 直接畫物品坐標(biāo)—轉(zhuǎn)角坐標(biāo)—轉(zhuǎn)角坐標(biāo)—用戶坐標(biāo) 的連線。

如果不是前兩種情況，則用室內(nèi)最近路線算法算出用戶和搜索物品最近的轉(zhuǎn)角坐標(biāo)點(diǎn)的相連最短路線，然后畫出物品坐標(biāo)—轉(zhuǎn)角坐標(biāo)—（最短路徑）—用戶坐標(biāo)的連線。

2.3 算法示例

設(shè)某商場(chǎng)的位置由12個(gè)點(diǎn)組成的無向圖（a-g：9，a-b：20，b-f：5，g-f：20，g-p：5，p-q：7，q-t：5，t-e：5，f-e：5，p-o：5，q-r：5，t-s：5，o-r：7，r-s：5，s-u：5）

下面就是算法的具體實(shí)現(xiàn)：首先，會(huì)得到用戶坐標(biāo)，并得到離用戶最近的轉(zhuǎn)角坐標(biāo)點(diǎn)（假設(shè)a），然后，會(huì)得到牛奶的坐標(biāo)，并得到離牛奶最近的轉(zhuǎn)角坐標(biāo)點(diǎn)（假設(shè)t）。求a到t最近的路線：（只說明關(guān)鍵的步驟和特殊的情況步驟，其他的步驟同理）

（1）a-g：5，a-b：20。a-g=5 存入a集合中，b返回b集合中。

（2）a-g-p：10，a-g-f：25。a-g-p：10存入a集合中，f返回b集合中。

（3）a-g-p-o：15，a-g-p-q：17。a-g-p-o：15存入a集合中，q存入b集合中。

（4）a-g-p-o-r：2。由于該行為是只有一個(gè)路徑，直接存入。

（5）比如a-g-p-o-r-q：27和a-g-p-o-r-s：27的路徑都是27，但是由于之前a集合中有a-g-p-q：17的路徑且小于這條路徑，那么當(dāng)前這倆個(gè)路徑刪除。

（6）如果有倆條路徑相等，比如a-g-p-q-t-s：27，a-g-p-q-t-e：27，且在a集合中沒有找到相等的結(jié)束位置，那么就隨機(jī)存入。a-g-p-q-t-s：27存入a集合?！?/p>

一共有12個(gè)頂點(diǎn)，經(jīng)過11次的重要運(yùn)算，這時(shí)b集合為空，則完成了室內(nèi)最近路線算法操作。此時(shí)，a集合中有11條記錄：這些記錄就是從a坐標(biāo)到除他外任意坐標(biāo)的最短路徑，從中找到我們需要的a-t路徑即可。最后，把a(bǔ)-g-p-q-t路徑連接起來，并把a(bǔ)和用戶坐標(biāo)，t和物品坐標(biāo)連接，得出的連線，就是用戶到物品的最佳路徑。

3 總結(jié)

本文是基于“sensoro 云子”傳感器實(shí)現(xiàn)商場(chǎng)室內(nèi)定位與導(dǎo)航設(shè)計(jì)，實(shí)現(xiàn)過程是首先通過云子的獲得用戶和商品的位置，然后在通過算法來找到用戶相對(duì)于該商品的最短路徑，最后只要在用戶的界面上通過直線描繪直觀的表示出這條路徑即可，關(guān)鍵點(diǎn)是對(duì)商場(chǎng)中地點(diǎn)信息的采集。隨著物聯(lián)網(wǎng)的普及和發(fā)展，基于傳感器的定位系統(tǒng)也會(huì)逐步的占據(jù)市場(chǎng)。

參考文獻(xiàn)：

[1] 方震，趙湛，郭鵬，等.基于RSSI測(cè)距分析[J].傳感器技術(shù)學(xué)報(bào)，2011，20（11）：2526-2530.

[2] 王小輝.基于FRID的室內(nèi)定位技術(shù)評(píng)論[J].傳感器與微系統(tǒng)，2009，28（2）：1-3.