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

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

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

2(同濟大學設計創意學院 上海 200092)

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

0 引 言

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

為了解決這個問題,可以使用具有LoRaWAN技術的智能推車。智能推車既可對自身進行定位幫助后勤人員尋找、使用和統計,又可從低功耗方面受益,因為沒有人希望找到并頻繁更換相當數量智能推車的電池。

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

本文提出基于LightGBM的指紋定位算法進行室外定位。通過在學校整個校區內的實驗估算了在類似大小中應用本文算法得出的定位準確性和算法實時性。

1 定位算法

考慮到并非所有應用都需要在整個LoRa的最大有效范圍內定位,本文專注于一片廠區或者校園大小的區域,本文采用機器學習融合指紋定位的算法實現LoRa的室外定位。離線階段包括指紋庫的構建以及LightGBM算法的參數訓練。

1.1 指紋定位原理及指紋庫的創建

當在空間范圍內安置數目大于三個、位置較分散的網關后,區域內終端與網關通信將在各個基站分別多組產生各自的RSSI值(rssigw1,rssigw2,…,rssigwn)?？臻g中干擾眾多,城市環境的高樓會嚴重影響附近被遮擋的樣本點。因此需要對數據進行預處理。

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

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

表1 指紋數據庫

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

圖1 LoRa指紋定位過程

1.2 LightGBM算法

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

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

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

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

(1)

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

(2)

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

(3)

通過近似擬合來優化損失函數,在每次迭代中減少損失函數的值并形成新的基學習器,通過之前每次迭代產生的基學習器線性相加,最后可以得到強學習器。

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

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

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

圖2 LightGBM樹生長策略改進

1.3 基于LightGBM的LoRa指紋算法

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

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

(4)

式中：f(Xi)表示i點處的算法預測值(xi,yi),而Yi代表真實的地理位置(xi,yi)。

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

圖3 算法框架流程

2 實驗及結果分析

本文于上海電力大學浦東校區內部設置了約800 m×500 m的實驗區域,區域內包括樓宇、人員、車輛等其他各種障礙物,對其他的場地也具有一定代表性。選取學?？拷吔堑?棟樓樓頂上安裝了ZTE-IWG200的LoRa網關如圖4所示。

圖4 網關3位置及移動測試終端

該網關在擴頻因子固定為12的情況下靈敏度≤-140 dBm,保證了測試區域室外LoRa信號全覆蓋不斷流。測試人員通過手持ZTE-T20移動測試終端獲得測試區域內各個樣本點的RSSI值。

LoRa通信終端參數設置如表2所示。

表2 通信終端參數設置

實驗總共設置了樣本點300個。這些點涵蓋了停車場、樓宇附近、田徑場、室外籃球場、人行道等各種位置,對校園室外環境有充分的代表性。根據訓練集和測試集的樣本比例,我們設置了270個訓練點以及30個測試點,樣本的劃分由train_test_split分配。圖5所示范圍為實驗區域、樣本點選取及其中一種劃分方法的示意。其中標數字點位為LoRa網關,其他實心點位為訓練點或測試點。

圖5 實驗區域示意圖

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

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

上面的四種算法的對比測試一共分為10組,每組測試都采用train_test_split的方法將300組樣本分別按照test_size等于0.1的分法分為270個訓練集合和30個測試集。為確保每組四個算法間訓練集測試集樣本相同并且組與組之間不同,我們在不同組之間使用了不同的random_state種子使劃分方法不一,測試結果如圖6所示。

圖6 四種算法誤差結果對比

統計各個算法在10組樣本上誤差平均值如表3所示。

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

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

同時,針對指紋定位可能存在的線下指紋數量大、訓練復雜耗時、線上定位對實時性要求高的特點,我們利用循環結構模擬了線上同時100個終端請求位置計算的訓練時間以及線下一次數據集的訓練時間。公平起見,四個算法統一使用CPU版本。平臺CPU為Intel Core i7-9750H處理器,操作系統為Windows 10 64位家庭版。

線下訓練四種算法的平均訓練時間如表4所示。

表4 算法平均訓練時間 單位：ms

可以清楚地看出kNN訓練效率遠超另外三種算法。而LightGBM與其他算法相比效率提高了不少,但還是在一個數量級。

線上定位時間如圖7所示。

圖7 四種算法計算時間對比

通過上面的數據我們可以清楚地發現此算法的位置誤差,相比kNN和BP神經網絡,分別縮小了37.2%和35.3%,相比XGBoost縮小了2.4%,相差不大。而根據圖7的線上定位時間數據,在實時位置計算上該算法相較于XGBoost效率提升了350%,與BP神經網絡相差不大,遜于kNN。

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

3 結 語

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