黃雙雙

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

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

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

0 引 言

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

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

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

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

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

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

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

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

1 NFC技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

4 算法分析與實例

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

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

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

4.2 A*算法

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

4.3 算法分析

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

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

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

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

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

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

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

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

（1）從起點開始，將起點添加到一個數(shù)據(jù)列表中，簡稱“開啟列表”；

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

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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