王能輝

（寶雞文理學院 寶雞 721013）

1 引言

近年來，移動互聯(lián)網、智能手機與GPS技術的大規(guī)模應用帶動了基于位置服務（LBS）的發(fā)展。隨著位置服務的飛速發(fā)展，LBS已開始應用到圖書館這一個綜合性、多功能、立體化服務體，基于位置的服務應用將使圖書館服務由內容驅動轉化為內容與情境共同驅動，圖書館的所有資源與讀者的身份、時間、空間要素相結合，嵌入讀者的活動情境中，給讀者能帶來立體化、個性化、多樣化的服務體驗［1］。LBS首先要利用定位技術確定讀者所在位置，隨后通過圖書館綜合服務平臺將圖書館相關資源和信息反饋給讀者。對LBS而言，其核心是定位技術，定位技術的優(yōu)劣決定了LBS服務質量。由于衛(wèi)星信號容易受到圖書館建筑的阻擋，GPS技術并不適用于圖書館室內定位。在此背景下國內外學者提出了許多基于無線通信技術的室內定位方法。高明等將ZigBee技術應用在室內定位［2］；劉鵬等討論了基于射頻識別的室內定位技術的優(yōu)缺點［3］；寧靜將紅外織網應用到室內定位并且給出了具體實施方案［4］；韓旭海等針對室內定位服務的社會需求［5］，搭建了利用線性加權算法實現(xiàn)室內移動藍牙設備的實時定位系統(tǒng)［6］；楊狄等對基于超寬帶的室內定位技術進行了分析研究［7］；楊陽等基于超聲波建立了三維室內定位系統(tǒng)［8］；林澤斐利用微信公眾平臺構建了圖書館二維碼定位系統(tǒng)［9］；石高濤綜合論述了現(xiàn)有的基于WIFI與移動智能終端的室內定位方法［10］。WLAN技術與其他技術相比，具有通信速率高、部署方便、覆蓋率高等特點，因此基于WLAN網絡的室內定位成為位置感知領域的一個研究熱點。

基于WLAN的定位算法分為近似感知、幾何測量和場景分析三大類。近似感知方法為最強基站法，幾何測量方法包括TOA（Time of Arrival）、TDOA（Time of Different of Arrival）和 AOA（Angle of Arrival）［11～13］，場景分析方法包括位置指紋法和信號傳播模型方法。綜合分析以上算法，考慮到定位精度、實施成本、實施難度，很多學者選用位置指紋法來構建定位系統(tǒng)。

2 位置指紋定位方法

基于WLAN的指紋的定位方法大致分為兩個階段：離線采樣階段和在線定位階段［14～15］，具體定位過程如圖1所示。

圖1 定位過程圖

在離線采樣階段，通過人工方式記錄在每個參考點接收到的來自所有AP的RSS信息及參考點位置構成位置指紋數據庫。在線定位階段，定位系統(tǒng)利用定位算法根據讀者移動終端收集到的無線信號特征信息與指紋數據庫中每個指紋的RSS信息計算比較，從指紋數據庫中找到最佳的匹配位置，將匹配的位置做為目標節(jié)點位置。

2.1 指紋庫的建立

將圖書館需要定位區(qū)域按照一定的大小，劃分為一個一個的參考點，在每個參考點，收集周圍定位AP的RSSI（接收信號強度指示），將參考點位置信息與RSSI平均值一一對應存儲于數據庫，形成一個二維矩陣。用n表示定位區(qū)域劃分的參考點的數量，L= { l1，l2，l3…，ln} 為各個參考點的位置信息，第個i參考點的位置li={xi， yi}表示，xi、yi是該參考點的坐標。R表示某一個參考點位置所采集的RSSI向量集合。用rj表示第 j個AP的RSSI信號強度，用向量 ri={r1，r2，r3…，rp}表示一組RSSI測量值，用R表示某個參考點的所有RSSI測量值。由(r ， l)組成數據組合，其中r∈R是一組測量值，l∈L是測量位置信息。

2.2 樸素貝葉斯概率指紋算法

基于指紋的定位過程可以看成一個對采集的無線信號特征進行分類的過程：離線階段就是訓練一個分類器模型，將采集的指紋信息作為分類器的輸入，參考點的位置作為分類器的輸出，從而訓練出符合目標無線環(huán)境的分類器模型；在線階段就是應用分類器進行定位，將新采樣的指紋信息輸入到訓練好的分類器，對應的輸出即為參考點的坐標，并以此作為待定位設備的估計坐標。分類器按照其訓練過程的不同可以分為三類：確定性分類器、概率型分類器和基于人工神經網絡的分類器。常用的最近鄰法NNSS算法、KNN算法、WKNN算法屬于確定行分類器。文獻［16］中，特倫托大學的Battiti等提出了基于人工神經網絡分類器的指紋定位算法。神經網絡算法（ANN）的優(yōu)勢在于對訓練集的個數要求不高。樸素貝葉斯法（Naive Bayes）與前面介紹的算法不同，前面的算法都是確定型定位匹配算法，而樸素貝葉斯算法是一種概率型算法，是概率型分類器的代表［17］。在訓練階段，他們首先采樣每個參考點的信號強度，即已知坐標的條件下信號強度的概率分布。在線階段，根據貝葉斯定理計算上報的信號強度指紋向量在每個參考點的概率，并以概率最大的參考點的坐標作為待定位設備的估計坐標。定位階段時測量得到的RSSI測量向量 ri={r1，r2，r3…，rp}，在某個參考點的后驗概率P(r | li)，P(r | li)表示在位置li出現(xiàn)信號向量r的概率。

可以通過參考點的先驗概率和似然函數，通過貝葉斯計算式（1）～（3）求得，其計算公式如下所示。

式（1）～（3）中，P(li)是在位置處的先驗概率，實際中通常假設其出現(xiàn)在各個參考區(qū)域的概率是等可能性的，即，由于樸素貝葉斯算法假設每個參考點采集的RSSI相互獨立，因此有：

最后，以后驗概率為權重，可以估算出比較精確的待測點位置坐標(? ，?)。

3 定位服務器存在的問題及解決思路

圖書館有著龐大的服務人群，定位系統(tǒng)一旦投入使用，定位服務器必然會承擔很大壓力。單純地增加服務器的硬件配置不能從根本上解決由于高并發(fā)制約定位服務質量的問題，綜合分析，應先硬件和軟件兩方面著手。軟件方面應先從核心算法樸素貝葉斯算法分析問題，樸素貝葉斯算法的計算主要集中在樣本訓練階段，它需要計算出每個屬性的每個取值的先驗概率［18］。樸素貝葉斯算法在處理數據量小的數據時，傳統(tǒng)的串行算法消耗計算資源很小，計算結果準確且速度快。一旦處理大規(guī)模數據數據或分類屬性增加時，傳統(tǒng)的算法需要消耗大量的計算資源，得出計算結果的時間增長。因此，傳統(tǒng)的串行樸素貝葉斯算法在處理大規(guī)模數據時有一定的局限性，這就需要對樸素貝葉斯算法進行改進。硬件方面，盡量采用大規(guī)模計算集群，以提高硬件計算能力。綜合軟件和硬件的需求，文章通過引入支持并行貝葉斯算法的云計算平臺來滿足定位服務軟件和硬件的需求，最終解決定位服務器處理大規(guī)模定位數據時計算時間太長問題，以提高定位服務質量。

4 基于MapReduce的并行貝葉斯指紋定位算法的實現(xiàn)

4.1 Hadoop云計算平臺

Hadoop是Apache基金會下的一個開源分布式平臺，作為云計算實現(xiàn)的一種方式，其以HDFS（Hadoop Distributed File System）和MapReduce為核心［19］，為使用者提供了簡單易用的分布式基礎設施，使用者不需要了解底層復雜細節(jié)就可以使用Hadoop提供的工具。Hadoop現(xiàn)在己經發(fā)展成為了一個包含核心項目、跟核心密切相關項目、面向應用項目等多個相關項目的軟件生態(tài)系統(tǒng)［20］，這些項目和外圍支撐系統(tǒng)之間提供互補性服務，共同搭建了一個可以處理海量數據的生態(tài)系統(tǒng)，生態(tài)系統(tǒng)架構如圖2所示。

圖2 Hdoop生態(tài)系統(tǒng)架構

如圖2所示，此系統(tǒng)由Ambari（安裝、部署、配置工具）、ZooKeeper（分布式協(xié)作服務）、HBase（分布式數據庫）、Hive（數據倉庫）、Pig（數據流處理）和面向具體領域的Mahout（數據流處理）等項目以及主要用于數據交換、開發(fā)環(huán)境等功能的Flume（舊志收集工具）、Sqoop（數據庫ETL工具）等外圍支撐系統(tǒng)和核心（HDFS和MapReduce）組成［21］。

4.2 MapReduce編程模型

隨著Google搜索的后臺數據處理規(guī)模越來越大，隨之而來的需要處理數據的計算量也隨之增大，用戶請求的時間也逐漸變長。為了更加有效地解決此類問題，Google于2004年推出了MapReduce編程模型，此模型運行在云計算平臺采用并行算法處理海量數據，使得并行與分布式編程更加方便。MapReduce編程模型的核心思想是采用“分而治之”，即將要處理的數據或被求解的問題分解成若干個數據塊，各數據塊均由一個節(jié)點處理，再將各個節(jié)點的執(zhí)行結果進行匯總，以達到并行計算的目標，從而得到最終的結果。MapReduce編程模型依據某種特征項對要處理的對象進行歸類處理，然后按照特征值匯總處理結果，其處理過程可以分為Map（映射）、階段 Shuffle（打亂）、Reduce（化簡）三個階段［22］，具體架構如圖3所示。

圖3 MapReduce模型架構圖

如圖3所示，Map階段依據用戶設定的某種特征解析每一條數據并從中提取出特征值Key及對應值Value，得到中間處理數據；Shuffle表示數據從Map Task輸出到Reduce Task輸入的這段過程［23］，Shuffle階段對中間處理數據進行合并排序；Reduce階段對Shuffle階段歸納好的數據經合并Key相同的Value值后，產生另外一系列Key及對應Value值。

4.3 基于MapReduce樸素貝葉斯概率指紋算法并行化實現(xiàn)

將樸素貝葉斯算法部署在基于MapReduce計算模型的Hadoop分布式平臺上，使得MapReduce化的樸素貝葉斯算法能夠分布式運行在Hadoop云計算平臺上。

樸素貝葉斯定位算法進行MapReduce并行化實現(xiàn)方法：主節(jié)點先從HDFS文件系統(tǒng)中將離線指紋數據庫和需要定位服務的移動終端接收到的附近無線AP的RSS下載到本地節(jié)點，之后對每個待定位移動終端的指紋信息進行一次Map計算，然后將中間計算結果送到Reduce節(jié)點進行規(guī)約操作，完成定位判定，并生成最終結果。

1）Map函數的設計

Map函數的任務是通過InputFormat將對應的InputSpli（t函數對象為離線指紋數據庫）解析成一系列鍵值對［24］。首先通過調用內置函數Split讀取離線指紋數據（已按照行形式存儲）并將離線指紋數據轉換成特定格式的文件以備后用。然后遍歷每個移動終端接收到指紋數據，逐個計算上報的信號強度指紋向量在每個參考點的概率，并以概率最大的參考點的坐標作為待定位設備的估計坐標，最終將計算結果存入Context集合。輸入數據形式為＜行號，離線指紋數據＞，行號選擇Object類型，其值即離線指紋數據選擇為Text類型；輸出數據形式為＜行號，離線指紋數據的類標識和相似度計算值組成的向量集合＞，計算結果設置輸出類型為Context類型。

2）Combine函數的設計

Hadoop中的Combine函數，本質上是一個本地的Reducer。其設計初衷是在本地將需要Reduce操作的數據就行合并，以減少不必要的通信代價，Combine可以提高Hadoop的運行性能。當所有數據處理完后，Map Task對所有臨時文件進行一次合并，并保存到文件output/file.out中，以確保最終只會生成一個數據文件。

3）Reduce函數的設計

Reduce函數用來進行規(guī)約操作，即把一個序列壓縮成一個值。其主要的任務以后驗概率為權重，通過Map找到的估計坐標計算出比較精確的待測點位置坐標。為了將不同Map節(jié)點上相同值（即同一個需要定位服務的指紋數據）的數據送到同一個Reduce節(jié)點需要執(zhí)行Shuffle操作［23］。其中輸入數據形式是＜定位ID，離線指紋數據(xi，yi) ＞，經Reduce函數處理后的輸出數據形式是＜定位ID，(?＞。

5 基于MapReduce的并行樸素貝葉斯在指紋法定位的應用

在指紋法定位系統(tǒng)中應用基于MapReduce的并行化樸素貝葉斯算法，其并行算法實現(xiàn)定位的過程如圖4所示。

與圖1的實現(xiàn)過程相比，增加了Hadoop云計算平臺和并行的樸素貝葉斯算法，由原來單臺服務器匹配整個指紋庫變?yōu)橹С諬adoop的云計算機平臺匹配指紋庫，可以有效地減少計算量，縮短計算時間。

圖4 并行定位算法定位過程

6 實驗與測試

6.1 搭建Hadoop平臺

本文的Hadoop云計算服務器集群的搭建四臺測試機，四臺測試機硬件配置均為

CPU：Inte（lR）Core（TM）i3 4170內存：8G測試軟件環(huán)境：OS版本：CentOS 6.8

Hadoop：2.7.1

Jdk：jdk1.8.0

namenode 192.168.0.1

datanode1 192.168.0.2

datanode2 192.168.0.3

datanode3 192.168.0.4

Hadoop平臺搭建步驟：

1）配置SSH，可以通過SSH管理四臺測試機；

2）java環(huán)境配置；

3）配置使用目錄；

4）配置core-site.xml，目的是定位文件系統(tǒng)的namenode；

5）配置 mapred-site.xml，目的在于定位 job?tracker所在的主節(jié)點；

6）配置 hdfs-site.xml，設置 HDFS副本數量為3［24］；

7）配置master與slave配置文檔；

8）拷貝Hadoop目錄下的文件到所有節(jié)點（datanode）；

9）格式化HDFS；

10）啟動hadoop守護進程；

11）在所有節(jié)點用 Jps查看Task、Tracker、Jps DataNode這三個進程有沒有正常工作。

6.2 建立指紋數據庫

為了建立離線指紋數據庫，選取寶雞文理學院新校區(qū)圖書館2層中間作為測試區(qū)域。圖書館2層總共架設了7個無線AP，所有區(qū)域完全覆蓋WIFI網絡。將圖書館2層區(qū)域按照1m*1m的單位劃分為網格，用xi和 yi表示區(qū)域里的參考點。在不同參考點的測試7個AP的RSSI，數據格式為：（1RS?SI，2RSSI，3RSSI，4RSSI，5RSSI，6RSSI，7RSSI，xi，yi）。此格式表示測試工具在位置（xi，yi）接收到的 周 圍 7 個 AP 的（1RSSI，2RSSI，3RSSI，4RSSI，5RSSI，6RSSI，7RSSI），將測試的數據整理成離線定位指紋庫。

6.3 算法實驗與分析

1）通過在Hadoop云平臺上namenode運行指紋匹配算法，輸入數據為同一離線指紋數據庫，計算定位匹配時間t1；

2）通過在Hadoop云平臺上多個datanode節(jié)點運行指紋匹配算法，輸入數據跟單節(jié)點相同，計算定位匹配時間tn；

采用公式計算時間加速比：

其中σ為時間加速比，n為節(jié)點數。

實驗結果如圖5所示。

由圖5可知，所有的σ都小于1，說明并行樸素貝葉斯指紋匹配算法比單機樸素貝葉斯匹配算法得出匹配結果的時間短；節(jié)點數越多，并行樸素貝葉斯指紋匹配算法比單機樸素貝葉斯算法優(yōu)勢越明顯。

圖5 不同節(jié)點數對應的加速比

7 結語

樸素貝葉斯指紋匹配算法應用廣泛，易于實現(xiàn)，但是面對海量數據時訓練過程需要消耗大量定位服務器系統(tǒng)資源，傳統(tǒng)串行樸素貝葉斯指紋匹配算法無法滿足圖書館大規(guī)模用戶使用。文章對傳統(tǒng)算法進行了改進，在Hadoop平臺實現(xiàn)了基于Ma?pReduce的樸素貝葉斯指紋匹配并行化算法，縮短了指紋匹配時間，提升了樸素貝葉斯分類算法對于大量定位請求處理能力。實驗驗證表明，基于Ma?pReduce的樸素貝葉斯指紋匹配并行化算法在同一離線指紋數據庫的情況下比串行貝葉斯指紋匹配算法得出匹配結果的時間短；Hadoop平臺節(jié)點數越多，并行樸素貝葉斯算法的優(yōu)勢越明顯?；贖adoop云平臺的定位系統(tǒng)能提供優(yōu)質的定位服務，滿足了圖書館用戶定位需求。