黃雙雙

摘 要：分析了當(dāng)前市場(chǎng)上主流室內(nèi)定位技術(shù)的優(yōu)缺點(diǎn)，描述了基于NFC的博物館智能導(dǎo)航系統(tǒng)的實(shí)現(xiàn)原理。用戶只需要使用智能手機(jī)接觸室內(nèi)用于定位的讀寫(xiě)標(biāo)簽，不僅能獲取展覽文物的詳細(xì)信息，還能獲取當(dāng)前所在的位置。文中采用啟發(fā)式A*算法，就能快速計(jì)算從出發(fā)點(diǎn)到目的地的最短路徑。

關(guān)鍵詞：室內(nèi)定位；NFC；A*算法；最短路徑

中圖分類號(hào)：TN929.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）11-00-03

0 引 言

作為位置信息服務(wù)的代表，全球定位系統(tǒng)已被廣泛用于車(chē)輛導(dǎo)航、工程測(cè)量、海洋救援、飛機(jī)導(dǎo)航、航空遙感等許多領(lǐng)域。在室內(nèi)環(huán)境中，無(wú)線信號(hào)通常比較差，GPS定位準(zhǔn)確度比較差，甚至失效。但是在商場(chǎng)、醫(yī)院、博物館等大型室內(nèi)建筑場(chǎng)所，一套好的定位系統(tǒng)將會(huì)給群眾的生活帶來(lái)極大的便利，基于如此廣闊的應(yīng)用場(chǎng)景，室內(nèi)定位技術(shù)正成為市場(chǎng)競(jìng)爭(zhēng)的一個(gè)熱點(diǎn)。

業(yè)界目前的室內(nèi)定位解決方案主要有紅外技術(shù)、超聲波（Ultrasound）技術(shù)、藍(lán)牙（Bluetooth）技術(shù)、WiFi技術(shù)、超寬帶（UWB）技術(shù)及射頻識(shí)別（RFID）技術(shù)等。這些技術(shù)都有各自的優(yōu)勢(shì)和不足，下面對(duì)其作簡(jiǎn)要比較：

（1）紅外室內(nèi)定位技術(shù)。系統(tǒng)通過(guò)紅外線發(fā)射器發(fā)射調(diào)制的紅外線，通過(guò)安裝在室內(nèi)的光學(xué)接收器進(jìn)行定位。紅外線定位技術(shù)定位精度較高，但紅外線不能穿越障礙物，一旦標(biāo)識(shí)物被遮擋，系統(tǒng)便無(wú)法定位，且紅外線衰減速度快，傳輸距離短，易受燈光干擾等缺點(diǎn)使其用于室內(nèi)定位時(shí)效果很差，并且系統(tǒng)的造價(jià)較高。

（2）超聲波定位技術(shù)。系統(tǒng)通過(guò)主測(cè)距器向位置固定的應(yīng)答器發(fā)射一定頻率的信號(hào)，應(yīng)答器產(chǎn)生回波，根據(jù)回波和發(fā)射波的時(shí)間差計(jì)算出兩者之間的距離，當(dāng)有三個(gè)或三個(gè)以上不在同一直線上的應(yīng)答器做出回應(yīng)時(shí)，根據(jù)三球定位等算法確定被測(cè)物所在的位置。超聲波定位精度較高，原理簡(jiǎn)單，易實(shí)現(xiàn)。但超聲波易受多徑效應(yīng)和非視距傳播等因素的影響，而且硬件成本比較高。

（3）藍(lán)牙定位技術(shù)。藍(lán)牙是一種近距離無(wú)線通信技術(shù)，通過(guò)利用發(fā)射信號(hào)和接收信號(hào)的強(qiáng)度差來(lái)實(shí)現(xiàn)定位。藍(lán)牙集成電路簡(jiǎn)單，易于集成在手機(jī)等移動(dòng)電子設(shè)備中，且信號(hào)傳輸不受視距的影響，設(shè)備易被發(fā)現(xiàn)，但在復(fù)雜的室內(nèi)環(huán)境中，藍(lán)牙系統(tǒng)容易被噪聲信號(hào)干擾，穩(wěn)定性不好。

（4）WiFi定位技術(shù)。系統(tǒng)通常由無(wú)線接入點(diǎn)和定位服務(wù)器組成，定位服務(wù)器通過(guò)分析接入點(diǎn)的信號(hào)強(qiáng)弱和信號(hào)特征進(jìn)行位置計(jì)算。WiFi定位系統(tǒng)采用信號(hào)傳播模型與經(jīng)驗(yàn)測(cè)試相結(jié)合的方式，易于安裝且需要很少基站。WiFi網(wǎng)絡(luò)穩(wěn)定性好，傳輸速率高，但WiFi信號(hào)收發(fā)器只能覆蓋半徑90米以內(nèi)的區(qū)域，且容易受到其他信號(hào)的干擾，系統(tǒng)的能耗也較高。

（5）超寬帶（UWB）技術(shù)。超寬帶技術(shù)通過(guò)發(fā)送許多間隔極小的脈沖進(jìn)行測(cè)距。超寬帶系統(tǒng)穿透材料能力強(qiáng)、功耗較低、時(shí)間分辨率高、抗多徑效果好、系統(tǒng)易實(shí)現(xiàn)。其可應(yīng)用于室內(nèi)靜止及移動(dòng)物體的定位和導(dǎo)航，系統(tǒng)的定位精度較高。但UWB難以實(shí)現(xiàn)大范圍室內(nèi)覆蓋，且手機(jī)不支持UWB，定位成本高。

（6）射頻識(shí)別技術(shù)（FRID）。射頻識(shí)別技術(shù)利用射頻信號(hào)，通過(guò)非接觸式雙向通信交換數(shù)據(jù)實(shí)現(xiàn)信息傳遞，并通過(guò)所傳遞的信息進(jìn)行識(shí)別和定位，通常通信距離為幾十米。RFID系統(tǒng)的防碰撞算法使得讀寫(xiě)器能在短時(shí)間內(nèi)識(shí)別大量的標(biāo)簽，為實(shí)現(xiàn)實(shí)時(shí)定位提供了可能。隨著集成電路設(shè)計(jì)技術(shù)日益成熟，RFID標(biāo)簽制造成本較低，但其定位距離有限且不能進(jìn)行信息的傳遞[1]。

1 NFC技術(shù)

NFC近場(chǎng)通信（Near Field Communication，NFC），也就是近距離無(wú)線通信，是一種短距離的高頻無(wú)線通信技術(shù)，它允許電子設(shè)備之間進(jìn)行非接觸式點(diǎn)對(duì)點(diǎn)數(shù)據(jù)傳輸（在十厘米內(nèi)）交換數(shù)據(jù)。該技術(shù)由免接觸式射頻識(shí)別（RFID）演變而來(lái)，并向下兼容RFID，最早由Sony和Philips各自開(kāi)發(fā)成功，主要為手機(jī)等手持設(shè)備提供M2M（Machine to Machine）的通信。NFC 技術(shù)和藍(lán)牙相比操作簡(jiǎn)單、配對(duì)快速；和 RFID 技術(shù)相比適用范圍廣泛、可讀可寫(xiě)、能直接集成在手機(jī)中；和紅外線相比數(shù)據(jù)傳輸較快、安全性高、能耗低（可以無(wú)電讀?。缓投S碼相比識(shí)別快速、信息類型多樣。NFC 技術(shù)可適用于很多場(chǎng)景，比如移動(dòng)支付、公交卡、智能海報(bào)等[2]。

NFC標(biāo)簽是一種可讀寫(xiě)的電子芯片，通過(guò)帶有NFC功能的電子設(shè)備掃描NFC標(biāo)簽就能讀寫(xiě)標(biāo)簽中的內(nèi)容。由于是無(wú)源器件，只需將線圈設(shè)計(jì)好便可制成NFC標(biāo)簽，因此NFC標(biāo)簽價(jià)格低廉。比起藍(lán)牙等傳統(tǒng)產(chǎn)品，NFC在使用上更為簡(jiǎn)單高效，可以給用戶帶來(lái)更好的體驗(yàn)。因此，在不久的將來(lái)，NFC會(huì)越來(lái)越多地出現(xiàn)在我們的生活中。

由于博物館展覽品數(shù)量龐大，每個(gè)展覽品的展示空間有限，所以很難在展柜上充分描述展覽品的詳細(xì)資料。通過(guò)把展覽品的詳細(xì)資料存儲(chǔ)到NFC標(biāo)簽中，觀眾可以用手機(jī)讀寫(xiě)NFC標(biāo)簽，獲取到更多的信息。盡管NFC標(biāo)簽存儲(chǔ)容量有限，但其存儲(chǔ)形式多樣，可以存儲(chǔ)小量文本，還可以存儲(chǔ)網(wǎng)址，通過(guò)網(wǎng)頁(yè)向觀眾進(jìn)行詳細(xì)展示[3]。

2 系統(tǒng)結(jié)構(gòu)

系統(tǒng)主要由移動(dòng)前端和服務(wù)后臺(tái)組成，移動(dòng)前端主要是手機(jī)、pad等電子設(shè)備，通過(guò)下載App實(shí)現(xiàn)位置導(dǎo)航和展覽品信息獲取。前端App采用時(shí)下廣泛使用的Android平臺(tái)，結(jié)合當(dāng)前大熱的NFC技術(shù)進(jìn)行開(kāi)發(fā)。系統(tǒng)后端服務(wù)器采用ubuntu+tomcat+java+mysql的方式搭建，系統(tǒng)穩(wěn)定性好且易于多平臺(tái)移植。

3 系統(tǒng)功能設(shè)計(jì)

系統(tǒng)的前端主要實(shí)現(xiàn)游客實(shí)時(shí)定位、目的地路線導(dǎo)航、展覽品信息獲取、地圖更新等功能。后端為博物館信息管理平臺(tái)，博物館管理員可以對(duì)館藏物品進(jìn)行增加、修改、刪除等操作，后臺(tái)還包含了博物館所有展覽品的詳細(xì)信息、展柜地理位置、室內(nèi)地圖等數(shù)據(jù)，同時(shí)為前端提供數(shù)據(jù)接口。系統(tǒng)的功能結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)功能結(jié)構(gòu)圖

當(dāng)游客想獲取展覽品的詳細(xì)信息時(shí)，只需用NFC手機(jī)接觸展柜上的NFC標(biāo)簽，或者手動(dòng)輸入展覽物品名稱，手機(jī)便自動(dòng)跳轉(zhuǎn)到展覽品信息界面，顯示當(dāng)前展覽品的簡(jiǎn)要信息，游客可選擇“獲取詳細(xì)信息”或“語(yǔ)音介紹”等高級(jí)功能菜單，獲取展覽品更加詳盡的文字及圖片介紹或者語(yǔ)音解說(shuō)。

當(dāng)游客想搜尋路線時(shí)，只需進(jìn)入路線搜尋界面，將手機(jī)靠近NFC標(biāo)簽，手機(jī)將獲取游客當(dāng)前位置，并在地圖上標(biāo)注，顯示的地圖上會(huì)標(biāo)示當(dāng)前館藏的所有物品，并顯示物品名稱和簡(jiǎn)要介紹，游客在地圖上點(diǎn)擊想?yún)⒂^的物品，系統(tǒng)將顯示當(dāng)前位置到目的地的最佳路線，從而游客將在復(fù)雜的場(chǎng)館內(nèi)輕松自如的找到自己想看的文物。圖2所示為室內(nèi)環(huán)境模擬圖。

圖2 室內(nèi)環(huán)境模型圖

當(dāng)博物館處于地下時(shí)，手機(jī)信號(hào)不佳，游客可通過(guò)離線下載數(shù)據(jù)界面，提前下載好館內(nèi)最新地圖，展覽品簡(jiǎn)介等小量數(shù)據(jù)存儲(chǔ)到客戶端數(shù)據(jù)庫(kù)中，這樣即使在信號(hào)不好的場(chǎng)地，游客也可以獲取到展覽文物的簡(jiǎn)要介紹，及位置定位和導(dǎo)航。

4 算法分析與實(shí)例

4.1 Dijkstra算法與最佳優(yōu)先搜索（BFS）

Dijkstra算法從源節(jié)點(diǎn)開(kāi)始層層向外擴(kuò)展，遍歷圖中的各個(gè)節(jié)點(diǎn)，找到距離源節(jié)點(diǎn)最短路徑的節(jié)點(diǎn)，并標(biāo)記為已查節(jié)點(diǎn)，重復(fù)這一過(guò)程直到所有節(jié)點(diǎn)都被標(biāo)記過(guò)。通過(guò)從初始節(jié)點(diǎn)向外擴(kuò)展，直到到達(dá)目標(biāo)節(jié)點(diǎn)。Dijkstra算法能夠算出從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑。

BFS算法與Dijkstra算法的原理相似，不同的是BFS能夠評(píng)估（稱為啟發(fā)式的）任意節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)。與Dijkstra算法每次選擇離源節(jié)點(diǎn)最近的節(jié)點(diǎn)不同的是，BFS算法每次選擇離目標(biāo)最近的節(jié)點(diǎn)。BFS不能保證找到一條最短路徑，但通過(guò)使用啟發(fā)式函數(shù)（heuristic function）可以快速地導(dǎo)向目標(biāo)節(jié)點(diǎn)，因而比Dijkstra算法快很多[4]。

4.2 A*算法

A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是最優(yōu)優(yōu)先路徑算法。該算法在節(jié)點(diǎn)擴(kuò)展過(guò)程中使用了啟發(fā)信息，算法的搜索方向智能地趨向目標(biāo)節(jié)點(diǎn)，算法的效率得到很大的提高[5]。A*算法是啟發(fā)式方法（heuristic approaches）如BFS，其是與常規(guī)方法如Dijsktra算法相結(jié)合的一種更高效的算法。類似BFS的啟發(fā)式方法經(jīng)常給出一個(gè)近似解而不是保證最佳解，盡管A*基于無(wú)法保證最佳解的啟發(fā)式方法，A*卻能保證找到一條最短路徑。A*算法成功的秘決在于它把Dijkstra算法（靠近初始點(diǎn)的節(jié)點(diǎn)）和BFS算法（靠近目標(biāo)點(diǎn)的節(jié)點(diǎn)）的信息塊結(jié)合起來(lái)。A*算法的估價(jià)函數(shù)可表示為：f（n） = g（n） + h（n），其中g(shù)（n）表示從初始結(jié)點(diǎn)到任意節(jié)點(diǎn)n的最短路徑，h（n）表示從節(jié)結(jié)點(diǎn)n到目標(biāo)點(diǎn)的最短路徑的啟發(fā)值，h（n）啟發(fā)函數(shù)選取的越好，算法就越高效。當(dāng)從初始點(diǎn)向目標(biāo)點(diǎn)移動(dòng)時(shí)，A*權(quán)衡這兩者，每次進(jìn)行主循環(huán)時(shí)，它檢查f（n）最小的節(jié)點(diǎn)n，其中f（n）= g（n） + h（n）。

4.3 算法分析

首先將搜索區(qū)域劃分成方形網(wǎng)格，網(wǎng)格的邊長(zhǎng)為10，對(duì)角線距離近似為14。網(wǎng)格分為兩種狀態(tài)，淺色為可行狀態(tài)，深色為展位或墻壁，即不可行狀態(tài)，每個(gè)網(wǎng)格都有一個(gè)坐標(biāo)值，左上角為坐標(biāo)的原點(diǎn)，如圖3所示。

本文采取A*算法進(jìn)行路徑搜索，路徑搜索的關(guān)鍵是f（n）的計(jì)算，其中：

g（n）表示從起始點(diǎn)，沿著生成的路徑移動(dòng)到網(wǎng)格n的移動(dòng)耗費(fèi)；

h（n）表示從網(wǎng)格n移動(dòng)到目標(biāo)方格的預(yù)估移動(dòng)耗費(fèi)。

如上所示，G表示沿路徑從起始點(diǎn)到網(wǎng)格n的移動(dòng)耗費(fèi)。本文中，我們令水平方向和垂直方向的移動(dòng)耗費(fèi)為10，對(duì)角線方向耗費(fèi)近似為14。沿生成的路徑通往網(wǎng)格n的G值，就是取網(wǎng)格n的父節(jié)點(diǎn)的G值，如果網(wǎng)格n相對(duì)父節(jié)點(diǎn)是對(duì)角線方向則其G值為父節(jié)點(diǎn)的G值加14，如果是直角方向則網(wǎng)格n的G值為父節(jié)點(diǎn)的G值加10。

H值的計(jì)算方法比較多。本文使用的方法為曼哈頓方法，它計(jì)算網(wǎng)格n移動(dòng)到目標(biāo)網(wǎng)格之間需要經(jīng)過(guò)的水平方向和垂直方向的方格的數(shù)量總和（即兩點(diǎn)X軸坐標(biāo)差值的絕對(duì)值和Y軸坐標(biāo)差值的絕對(duì)值之和）的最小值，移動(dòng)方向不能為對(duì)角線方向，然后把結(jié)果乘以10。

F的值是G值和H值的總和。

下面以起始點(diǎn)（7，5），目標(biāo)點(diǎn)（1，2）為例敘述路徑獲取算法。網(wǎng)格模型如圖3所示，搜索步驟如下：

（1）從起點(diǎn)開(kāi)始，將起點(diǎn)添加到一個(gè)數(shù)據(jù)列表中，簡(jiǎn)稱“開(kāi)啟列表”；

（2）重復(fù)以下步驟：

a.搜索開(kāi)啟列表，找到F值最低的格子，如果F值相同，則取G值較低者，G值和H 值若都相同，則任選其一，并設(shè)為當(dāng)前格。

b.把它添加到另一個(gè)數(shù)據(jù)列表，簡(jiǎn)稱“關(guān)閉列表”。

c.搜索與當(dāng)前格相鄰網(wǎng)格，并進(jìn)行屬性設(shè)置：

①如果它不可通過(guò)或者處于關(guān)閉列表中，則不做設(shè)置，反之如②。

②如果它不在開(kāi)啟列表中，則把它添加到開(kāi)啟列表，并設(shè)置它的父節(jié)點(diǎn)為當(dāng)前格，計(jì)算它的F值、G值和H值。如果它已經(jīng)在開(kāi)啟列表中，重新計(jì)算它的G值并與之前的G值進(jìn)行比較，如果新的G值比較小則將其父節(jié)點(diǎn)設(shè)為當(dāng)前格，更新它的G值和F值，如果新的G值比大則更新它的屬性。

d.結(jié)束。當(dāng)目標(biāo)格被找到并添加到關(guān)閉列表中，則路徑被找到，從目標(biāo)格開(kāi)始，通過(guò)每個(gè)網(wǎng)格的父節(jié)點(diǎn)來(lái)遍歷關(guān)閉隊(duì)列，則可得到規(guī)劃路徑的反向序列，如果目標(biāo)格沒(méi)有找到且開(kāi)啟列表已經(jīng)為空，則路徑不存在。圖3所示為其網(wǎng)格的模型圖。

圖3 網(wǎng)格模型圖

5 結(jié) 語(yǔ)

本文提出了一種基于NFC的新型博物館定位導(dǎo)航系統(tǒng)，游客通過(guò)掃描NFC標(biāo)簽不僅能獲取展覽文物的信息還能進(jìn)行實(shí)時(shí)定位，系統(tǒng)采用了A*搜素算法，能以更快的速度獲取到達(dá)目的地的最短路徑。游客還可以通過(guò)客戶端從服務(wù)后臺(tái)獲取展覽文物的詳細(xì)信息、下載離線數(shù)據(jù)等高級(jí)功能。

參考文獻(xiàn)

[1]吳雨航，吳才聰，陳秀萬(wàn).介紹幾種室內(nèi)定位技術(shù)[N].中國(guó)測(cè)繪報(bào)，2008-1-003.

[2]林龍，張果，王劍平，等.基于NFC技術(shù)的標(biāo)簽?zāi)Ｊ皆O(shè)計(jì)[J].微處理機(jī)，2013，34（3）：31-36.

[3]吳連發(fā).NFC技術(shù)在博物館安防和展陳中的應(yīng)用分析[J].魅力中國(guó)，2014，9（25）：226-228.

[4]龔道雄，劉翔.迷宮搜索算法的比較研究[J].計(jì)算機(jī)應(yīng)用研究，2011，28（12）：4433-4436.

[5]房佳，杜震洪.應(yīng)用于城市道路網(wǎng)的啟發(fā)式深度優(yōu)先有向搜索算法[J].浙江大學(xué)學(xué)報(bào)（理學(xué)版），2013，40（4）：469-474.