基于LightGBM的LoRa室外指紋定位算法

張子凡 龐成鑫* 冉浦東 范 磊 刁志峰 張 軍

1(上海電力大學(xué)電子與信息工程學(xué)院 上海 201306)

2(同濟(jì)大學(xué)設(shè)計(jì)創(chuàng)意學(xué)院 上海 200092)

3(國家電網(wǎng)南瑞南京控制系統(tǒng)有限公司 江蘇 南京 210000)

0 引 言

物聯(lián)網(wǎng)技術(shù)的發(fā)展,在諸如物流檢測(cè)、生產(chǎn)監(jiān)控、河道檢測(cè)等領(lǐng)域內(nèi)產(chǎn)生了越來越多基于物聯(lián)網(wǎng)應(yīng)用的位置信息服務(wù)。LoRaWAN是低功耗廣域網(wǎng)(LPWAN)技術(shù)之一。它由Semtech開發(fā),是在Sub—GHz免許可頻段中使用最廣泛的LPWAN技術(shù)之一,具有低成本、低功耗和較長(zhǎng)距離通信的優(yōu)點(diǎn)[1]。在學(xué)校校區(qū)和工業(yè)園區(qū)這樣若干平方公里的區(qū)域進(jìn)行企業(yè)級(jí)組網(wǎng)較為合適。例如學(xué)校和廠區(qū)中的貨物推車經(jīng)常在各個(gè)時(shí)段被不同的人員推到不同的地點(diǎn),這通常導(dǎo)致重要的公有財(cái)產(chǎn)在使用的時(shí)候反而難以找到甚至導(dǎo)致推車的損壞及丟失。

為了解決這個(gè)問題,可以使用具有LoRaWAN技術(shù)的智能推車。智能推車既可對(duì)自身進(jìn)行定位幫助后勤人員尋找、使用和統(tǒng)計(jì),又可從低功耗方面受益,因?yàn)闆]有人希望找到并頻繁更換相當(dāng)數(shù)量智能推車的電池。

如今,國內(nèi)外學(xué)者在嘗試各種方法在LoRaWAN中實(shí)現(xiàn)精確定位。在較為廣闊的地段單純使用接收信號(hào)強(qiáng)度(Received Signal Strength Indicate,RSSI)模型,其原理是使用基站接收到的信號(hào)強(qiáng)度計(jì)算出信號(hào)的傳播損耗,再將其以理論與經(jīng)驗(yàn)?zāi)Ｐ娃D(zhuǎn)化為距離,通過多個(gè)基站的重疊覆蓋范圍運(yùn)用樸素貝葉斯原理計(jì)算出節(jié)點(diǎn)的最大概率位置。計(jì)算估計(jì)位置時(shí),誤差約為1 000～2 000 m[2]。Ha等[3]針對(duì)這個(gè)問題提出了使用指紋定位輔助ToA的定位系統(tǒng),利用LoRa信號(hào)在空間中的傳播時(shí)間來計(jì)算信號(hào)發(fā)射端與接收端的距離。其方法特點(diǎn)是比較少的基站數(shù)目同樣能夠進(jìn)行定位,但是這種算法在空曠地帶的精度很高而在城市范圍內(nèi)則精度欠佳(200 m左右)。Fargas等[4]使用TDoA方法來估計(jì)物體在農(nóng)村地區(qū)的位置。通過研究人員進(jìn)行的實(shí)驗(yàn)驗(yàn)證結(jié)果,但是該算法定位誤差在某些情況下超過1 km,誤差較大。即使在一些情況下將定位誤差縮小到100 m左右,但是算法框架中數(shù)據(jù)包的發(fā)送數(shù)量卻超過10 000,并且算法總處理時(shí)間較長(zhǎng)。還有不少研究針對(duì)室內(nèi)定位和室外小范圍定位取得了不錯(cuò)的定位精度[5-7],但是在基站與終端距離更遠(yuǎn)、地理環(huán)境更復(fù)雜、干擾更多樣的環(huán)境下精度還是不理想。

本文提出基于LightGBM的指紋定位算法進(jìn)行室外定位。通過在學(xué)校整個(gè)校區(qū)內(nèi)的實(shí)驗(yàn)估算了在類似大小中應(yīng)用本文算法得出的定位準(zhǔn)確性和算法實(shí)時(shí)性。

1 定位算法

考慮到并非所有應(yīng)用都需要在整個(gè)LoRa的最大有效范圍內(nèi)定位,本文專注于一片廠區(qū)或者校園大小的區(qū)域,本文采用機(jī)器學(xué)習(xí)融合指紋定位的算法實(shí)現(xiàn)LoRa的室外定位。離線階段包括指紋庫的構(gòu)建以及LightGBM算法的參數(shù)訓(xùn)練。

1.1 指紋定位原理及指紋庫的創(chuàng)建

當(dāng)在空間范圍內(nèi)安置數(shù)目大于三個(gè)、位置較分散的網(wǎng)關(guān)后,區(qū)域內(nèi)終端與網(wǎng)關(guān)通信將在各個(gè)基站分別多組產(chǎn)生各自的RSSI值(rssigw1,rssigw2,…,rssigwn)。空間中干擾眾多,城市環(huán)境的高樓會(huì)嚴(yán)重影響附近被遮擋的樣本點(diǎn)。因此需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。

本文的數(shù)據(jù)預(yù)處理分為三個(gè)部分,按照先后順序第一是對(duì)采集樣本中的空缺值進(jìn)行填補(bǔ)。實(shí)際使用網(wǎng)關(guān)的性能會(huì)存在差異。例如唐周益丹等[5]的論文中使用了靈敏度為-90 dBm的網(wǎng)關(guān),不能識(shí)別接收功率小于-90 dBm的LoRa信號(hào),導(dǎo)致其難以接收長(zhǎng)距離或是復(fù)雜環(huán)境下的終端信號(hào)。本文中實(shí)驗(yàn)使用的中興ZTE-IWG200網(wǎng)關(guān)靈敏度為-140 dBm,對(duì)于實(shí)際信號(hào)強(qiáng)度弱于-140 dBm的信號(hào)沒有分辨能力。這個(gè)靈敏度已經(jīng)相當(dāng)高了,因此我們將某樣本點(diǎn)可能出現(xiàn)的RSSI空缺值由-140 dBm代替,也不會(huì)對(duì)結(jié)果產(chǎn)生較大影響。第二步是針對(duì)噪聲和環(huán)境的復(fù)雜性對(duì)同一地點(diǎn)的多組信號(hào)采用中值濾波。最后為了提高模型的泛化能力和收斂速度,將數(shù)據(jù)作歸一化處理。

數(shù)據(jù)在經(jīng)過預(yù)處理之后將構(gòu)成一組大于三維的向量,再附上某地本身的二維地理位置(xi,yi)便是指紋(rssigw1,rssigw2,…,rssigwn,xi,yi)。通過一定數(shù)量[8]的指紋可以構(gòu)建好離線指紋庫。表1展示了帶4個(gè)基站、共n個(gè)樣本點(diǎn)的指紋數(shù)據(jù)庫。

表1 指紋數(shù)據(jù)庫

最后的在線階段使用未知位置的指紋經(jīng)過數(shù)據(jù)預(yù)處理后作為離線算法輸入,最終算法模型計(jì)算出相應(yīng)的位置輸出,整個(gè)過程如圖1所示。

圖1 LoRa指紋定位過程

1.2 LightGBM算法

LightGBM是微軟于2016年開源發(fā)布的一種基于決策樹的梯度提升算法[9],其具有支持并行處理、訓(xùn)練速度快、準(zhǔn)確率高、內(nèi)存占用量小的特點(diǎn),是基于梯度提升樹算法的優(yōu)化版本,目前在Kaggle等各種比賽上取得了很好的成績(jī)[10]。

介紹LightGBM前,首先要介紹梯度提升(Gradient Boosting)[11]。集成學(xué)習(xí)中的提升方法(Boosting)通過將若干個(gè)弱分類器通過組合,構(gòu)造出一個(gè)強(qiáng)分類器[12]。在此之上,梯度提升的核心思想通過計(jì)算負(fù)梯度近似計(jì)算殘差來逐步提升模型,它采用決策樹作為基分類器。

當(dāng)定義初始值f0(x)=0后,之后的第n步迭代的模型可以表示為：

fn(x)=fn-1(x)+T(x;Θn)

(1)

式中：fn-1(x)是當(dāng)前模型;T(x;Θn)所代表的殘差為模型優(yōu)化的關(guān)鍵參數(shù)。下一個(gè)基分類器的Θn可以通過式(2)確定。

(2)

梯度提升使用了模型負(fù)梯度值近似計(jì)算T(x;Θn),從而使之后的每次迭代減少了整體的損失函數(shù)值。當(dāng)訓(xùn)練第i個(gè)樣本時(shí),該處的負(fù)梯度近似值為：

(3)

通過近似擬合來優(yōu)化損失函數(shù),在每次迭代中減少損失函數(shù)的值并形成新的基學(xué)習(xí)器,通過之前每次迭代產(chǎn)生的基學(xué)習(xí)器線性相加,最后可以得到強(qiáng)學(xué)習(xí)器。

LightGBM作為梯度提升算法的一種,最重要的是改進(jìn)采用了直方圖(Histogram)算法和帶有深度限制的按葉子生長(zhǎng)(leaf-wise)算法。

直方圖算法通過把連續(xù)的浮點(diǎn)型特征離散化成K個(gè)整數(shù),從而構(gòu)造出一個(gè)寬度為K的直方圖。遍歷數(shù)據(jù)時(shí),根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量,當(dāng)遍歷一次數(shù)據(jù)后,直方圖累積了需要的統(tǒng)計(jì)量,然后從直方圖的離散值中,遍歷出最優(yōu)的分割點(diǎn)。對(duì)比精確分割,雖然有一定準(zhǔn)確度降低。但由于弱分類器對(duì)準(zhǔn)確度要求不高,因此這種方法在梯度提升框架下影響不大且可以有效防止過擬合。

傳統(tǒng)的樹生長(zhǎng)策略使用層生長(zhǎng)(level-wise)策略,但很多葉子的分裂增益較低,沒有生長(zhǎng)的必要。因此LightGBM使用葉子生長(zhǎng)(leaf-wise)策略：每次從當(dāng)前所有葉子中具有最大delta loss的節(jié)點(diǎn)來生長(zhǎng),這種生長(zhǎng)方式需要配合參數(shù)最大深度限制(max_depth)以及葉子數(shù)(number_leaves)使用,在保證高效的同時(shí)又限制了樹過深或者葉子過多,防止模型出現(xiàn)過擬合。改進(jìn)策略如圖2所示。

圖2 LightGBM樹生長(zhǎng)策略改進(jìn)

1.3 基于LightGBM的LoRa指紋算法

將指紋庫訓(xùn)練數(shù)據(jù)(rssigw1,rssigw2,…,rssigwn)當(dāng)作特征輸入,以地理位置信息(xn,yn)作為標(biāo)簽輸出,使用LGBMRegressor做監(jiān)督學(xué)習(xí),通過K折交叉驗(yàn)證(K-Fold Cross Validation)調(diào)參就訓(xùn)練出該區(qū)域的算法模型。K折交叉驗(yàn)證是將總體樣本集分成k份,分別使用其中的(k-1)份作為訓(xùn)練集,剩下的1份作為交叉驗(yàn)證集,最后取每次的平均誤差來評(píng)估這個(gè)模型。

最適合判斷平面地理位置信息準(zhǔn)確率的損失函數(shù)是歐氏距離,因此算法采用RMSE作為損失函數(shù),其公式定義如式(4)所示。

(4)

式中：f(Xi)表示i點(diǎn)處的算法預(yù)測(cè)值(xi,yi),而Yi代表真實(shí)的地理位置(xi,yi)。

值得注意的是,平面位置信息是二維數(shù)據(jù)。但是包括XGBoost、LightGBM在內(nèi),相當(dāng)多的深度學(xué)習(xí)流行算法使用回歸樹作為基分類器,導(dǎo)致其無法進(jìn)行多輸入多輸出(MIMO)。因此,本文使用多輸出回歸器(MultiOutputRegressor)對(duì)LGBMRegressor進(jìn)行包裝組合從而使得算法框架能夠訓(xùn)練并輸出多維標(biāo)簽,整個(gè)算法框架的流程如圖3所示。

圖3 算法框架流程

2 實(shí)驗(yàn)及結(jié)果分析

本文于上海電力大學(xué)浦東校區(qū)內(nèi)部設(shè)置了約800 m×500 m的實(shí)驗(yàn)區(qū)域,區(qū)域內(nèi)包括樓宇、人員、車輛等其他各種障礙物,對(duì)其他的場(chǎng)地也具有一定代表性。選取學(xué)?？拷吔堑?棟樓樓頂上安裝了ZTE-IWG200的LoRa網(wǎng)關(guān)如圖4所示。

圖4 網(wǎng)關(guān)3位置及移動(dòng)測(cè)試終端

該網(wǎng)關(guān)在擴(kuò)頻因子固定為12的情況下靈敏度≤-140 dBm,保證了測(cè)試區(qū)域室外LoRa信號(hào)全覆蓋不斷流。測(cè)試人員通過手持ZTE-T20移動(dòng)測(cè)試終端獲得測(cè)試區(qū)域內(nèi)各個(gè)樣本點(diǎn)的RSSI值。

LoRa通信終端參數(shù)設(shè)置如表2所示。

表2 通信終端參數(shù)設(shè)置

實(shí)驗(yàn)總共設(shè)置了樣本點(diǎn)300個(gè)。這些點(diǎn)涵蓋了停車場(chǎng)、樓宇附近、田徑場(chǎng)、室外籃球場(chǎng)、人行道等各種位置,對(duì)校園室外環(huán)境有充分的代表性。根據(jù)訓(xùn)練集和測(cè)試集的樣本比例,我們?cè)O(shè)置了270個(gè)訓(xùn)練點(diǎn)以及30個(gè)測(cè)試點(diǎn),樣本的劃分由train_test_split分配。圖5所示范圍為實(shí)驗(yàn)區(qū)域、樣本點(diǎn)選取及其中一種劃分方法的示意。其中標(biāo)數(shù)字點(diǎn)位為L(zhǎng)oRa網(wǎng)關(guān),其他實(shí)心點(diǎn)位為訓(xùn)練點(diǎn)或測(cè)試點(diǎn)。

圖5 實(shí)驗(yàn)區(qū)域示意圖

在每一個(gè)測(cè)試點(diǎn)位,我們都將終端放于地面上測(cè)試,保證天線垂直向上。終端設(shè)置為每隔30 s與網(wǎng)關(guān)通信1次,在每點(diǎn)進(jìn)行5次采集方便進(jìn)行數(shù)據(jù)處理。為了保證參數(shù)的一致性,我們關(guān)閉了終端自適應(yīng)功能(ADR)以確保擴(kuò)頻因子(SF)數(shù)值穩(wěn)定為12。

為了方便分析和比較定位準(zhǔn)確度和實(shí)時(shí)性,本文引入了其他常用的三種算法模型。它們分別為kNN、BP神經(jīng)網(wǎng)絡(luò)、XGBoost各自的回歸模型。在二維平面上kNN通過計(jì)算測(cè)試樣本與訓(xùn)練樣本的歐氏距離,找出與測(cè)試樣本距離最接近的k個(gè)訓(xùn)練樣本,輸出訓(xùn)練樣本的平均位置。其特點(diǎn)就是原理簡(jiǎn)單高效。對(duì)比實(shí)驗(yàn)中kNN中的k值根據(jù)經(jīng)驗(yàn)和Lemic等[8]的研究設(shè)置為4;BP神經(jīng)網(wǎng)絡(luò)是利用誤差反向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò),作為目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型,其特點(diǎn)是極強(qiáng)的泛化能力和適應(yīng)能力,在本實(shí)驗(yàn)中BP神經(jīng)網(wǎng)絡(luò)原生支持多維向量輸出。對(duì)比實(shí)驗(yàn)中BP神經(jīng)網(wǎng)絡(luò)設(shè)置中間層為4層;XGBoost同LightGBM一樣是梯度提升樹模型的改進(jìn)版本,相比傳統(tǒng)梯度提升樹,它將損失函數(shù)從平方損失推廣到二階可導(dǎo)的損失同時(shí)加入了L2正則化項(xiàng),其影響力已經(jīng)被許多機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的比賽所廣泛認(rèn)可[13]。

上面的四種算法的對(duì)比測(cè)試一共分為10組,每組測(cè)試都采用train_test_split的方法將300組樣本分別按照test_size等于0.1的分法分為270個(gè)訓(xùn)練集合和30個(gè)測(cè)試集。為確保每組四個(gè)算法間訓(xùn)練集測(cè)試集樣本相同并且組與組之間不同,我們?cè)诓煌M之間使用了不同的random_state種子使劃分方法不一,測(cè)試結(jié)果如圖6所示。

圖6 四種算法誤差結(jié)果對(duì)比

統(tǒng)計(jì)各個(gè)算法在10組樣本上誤差平均值如表3所示。

表3 各算法RMSE誤差平均值 單位：m

其中LightGBM在最好的第4組平均定位精度為72.33 m,在最差的第8組平均精度為95.25 m,10組總共平均精度為90.29 m。

同時(shí),針對(duì)指紋定位可能存在的線下指紋數(shù)量大、訓(xùn)練復(fù)雜耗時(shí)、線上定位對(duì)實(shí)時(shí)性要求高的特點(diǎn),我們利用循環(huán)結(jié)構(gòu)模擬了線上同時(shí)100個(gè)終端請(qǐng)求位置計(jì)算的訓(xùn)練時(shí)間以及線下一次數(shù)據(jù)集的訓(xùn)練時(shí)間。公平起見,四個(gè)算法統(tǒng)一使用CPU版本。平臺(tái)CPU為Intel Core i7-9750H處理器,操作系統(tǒng)為Windows 10 64位家庭版。

線下訓(xùn)練四種算法的平均訓(xùn)練時(shí)間如表4所示。

表4 算法平均訓(xùn)練時(shí)間 單位：ms

可以清楚地看出kNN訓(xùn)練效率遠(yuǎn)超另外三種算法。而LightGBM與其他算法相比效率提高了不少,但還是在一個(gè)數(shù)量級(jí)。

線上定位時(shí)間如圖7所示。

圖7 四種算法計(jì)算時(shí)間對(duì)比

通過上面的數(shù)據(jù)我們可以清楚地發(fā)現(xiàn)此算法的位置誤差,相比kNN和BP神經(jīng)網(wǎng)絡(luò),分別縮小了37.2%和35.3%,相比XGBoost縮小了2.4%,相差不大。而根據(jù)圖7的線上定位時(shí)間數(shù)據(jù),在實(shí)時(shí)位置計(jì)算上該算法相較于XGBoost效率提升了350%,與BP神經(jīng)網(wǎng)絡(luò)相差不大,遜于kNN。

綜合上述結(jié)果,基于LightGBM的LoRa室外定位是有效的,在較為準(zhǔn)確地預(yù)計(jì)實(shí)際地點(diǎn)的同時(shí)通過采用直方圖算法,與XGBoost相比效率得到了很大的提高。因此兼顧了優(yōu)秀的實(shí)時(shí)性。尤其考慮到LightGBM原生支持并行計(jì)算并且有更高的內(nèi)存使用效率,將來對(duì)有更多樣本數(shù)據(jù)的訓(xùn)練相比XGBoost,線下訓(xùn)練的效率和線上定位的實(shí)時(shí)性會(huì)更加明顯。

3 結(jié) 語

隨著低功耗物聯(lián)網(wǎng)的發(fā)展,應(yīng)用LoRa或者ZETA、SigFox、NB-IoT的服務(wù)也會(huì)越來越多,同時(shí)對(duì)終端定位的需求越發(fā)強(qiáng)烈。本文針對(duì)LoRa使用傳統(tǒng)RSSI傳播模型在室外定位結(jié)果較為不準(zhǔn)確的情況,提出基于LightGBM的LoRa室外指紋定位算法,在整片校園環(huán)境中精確度達(dá)到了90 m左右,相比傳統(tǒng)定位方法準(zhǔn)確度有提高的同時(shí)提高了計(jì)算效率。下一步可以通過以下幾個(gè)方面來對(duì)進(jìn)一步優(yōu)化：(1) 空間中的定位需求可能不是相等的,一些熱門位置應(yīng)該分配更多樣本點(diǎn)進(jìn)行訓(xùn)練和測(cè)試;(2) 樣本點(diǎn)數(shù)量相對(duì)Wi-Fi這種協(xié)議較少,尚不能發(fā)揮機(jī)器學(xué)習(xí)甚至深度學(xué)習(xí)的潛力;(3) 實(shí)驗(yàn)定位設(shè)備統(tǒng)一且規(guī)格較高,質(zhì)量稍差的標(biāo)簽可能不具備本實(shí)驗(yàn)路測(cè)設(shè)備的發(fā)射功率從而影響基站RSSI的獲取。而這些缺陷也是本文后續(xù)工作的重點(diǎn)研究方向。