大型商場室內定位與導航設計

夏晨航 龔俊

摘 要：本文以商場作為模型的設置室內導航，借助于云子實現位置定位。從實物定位，到路徑規劃實施室內導航技術。

關鍵詞：空間定位；室內導航；移動設備；云子

定位導航給生活帶來了諸多便利，大家對GPS比較了解，其在室外非常好用，但在室內卻不精確，甚至無法使用。為了方便人們在室內商場快捷找到目的地，本文提出了一個可行的適用于室內定位與導航的方法。

1 室內導航的實物定位

室內的貨架按照一定距離鋪設釋放信號的云子，并記錄好每個云子的坐標及其編號，當客戶進入室內后，其攜帶的藍牙設備會接收到多顆云子發出的RSSI值并得到對應云子的信號強度，并根據其中最強的三個云子得到客戶的位置。分兩種情況陳述。

1.1 位置指紋識別算法

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

1.2 圓形定位算法

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

2 室內導航的路徑盤查

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

把每個云子的位置，綁定到該云子所在位置正對面的轉角坐標連上線。用戶搜索物品地點和用戶所在地點連入的云子，都對應一個位置。這時，就能知道用戶搜索物品和用戶所在地離哪個轉角坐標最近，然后，用室內最近路線算法，算出這兩個轉角坐標的最短路線，最后把首位轉角坐標點和搜索物品，用戶坐標連接起來，就得到用戶到搜索物品最近的路線。

2.2 室內最近路線算法

2.2.1算法思路

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

2.2.2算法過程

如果用戶和搜索物品最近轉角坐標同為一個，則跳過室內最近路線算法，直接畫物品坐標—轉角坐標—用戶坐標的連線。

如果用戶和搜索物品的最近轉角坐標點能直接相連，則也跳過室內最近路線算法， 直接畫物品坐標—轉角坐標—轉角坐標—用戶坐標 的連線。

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

2.3 算法示例

設某商場的位置由12個點組成的無向圖（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）

下面就是算法的具體實現：首先，會得到用戶坐標，并得到離用戶最近的轉角坐標點（假設a），然后，會得到牛奶的坐標，并得到離牛奶最近的轉角坐標點（假設t）。求a到t最近的路線：（只說明關鍵的步驟和特殊的情況步驟，其他的步驟同理）

（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。由于該行為是只有一個路徑，直接存入。

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

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

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

3 總結

本文是基于“sensoro 云子”傳感器實現商場室內定位與導航設計，實現過程是首先通過云子的獲得用戶和商品的位置，然后在通過算法來找到用戶相對于該商品的最短路徑，最后只要在用戶的界面上通過直線描繪直觀的表示出這條路徑即可，關鍵點是對商場中地點信息的采集。隨著物聯網的普及和發展，基于傳感器的定位系統也會逐步的占據市場。

參考文獻：

[1] 方震，趙湛，郭鵬，等.基于RSSI測距分析[J].傳感器技術學報，2011，20（11）：2526-2530.

[2] 王小輝.基于FRID的室內定位技術評論[J].傳感器與微系統，2009，28（2）：1-3.