基于電源線和位置指紋的室內定位技術

何 堅 萬志江 劉金偉

?

基于電源線和位置指紋的室內定位技術

何 堅①萬志江*①劉金偉②

①(北京工業(yè)大學軟件學院 北京 100124)②(北京工業(yè)大學信息中心 北京 100124)

該文提出將室內環(huán)境不可或缺的電源線作為天線，通過在電源線上注入寬帶高頻信號構造室內空間的位置指紋，進而實現(xiàn)室內空間精確定位。首先介紹了電源線上寬帶高頻信號注入模塊的實現(xiàn)技術，以及室內空間位置指紋的構造方法；其次，介紹了基于樸素貝葉斯分類算法的室內定位原理；最后，通過實驗分析證明在多訓練樣本情況下，基于樸素貝葉斯分類算法的定位算法比基于K最鄰近點(KNN)分類算法的定位算法有更好的定位準確率和時間遷移適應能力。

室內定位；位置指紋；樸素貝葉斯分類算法；K最鄰近點

1 引言

本文首先介紹基于電源線的室內定位原理，220 V電源線上寬帶高頻信號注入模塊的實現(xiàn)技術，以及室內空間位置指紋的構造方法；其次，介紹基于樸素貝葉斯的室內空間定位原理和實現(xiàn)方法；最后，通過實驗分析證明在多訓練樣本情況下，基于樸素貝葉斯的定位算法比基于KNN的定位算法有更好的定位準確率和時間遷移適應能力。

2 相關基礎工作

本文將室內空間劃分為等間距的不同節(jié)點，并以部署在房間墻體內的電源線作為天線，在電源線上輸入寬帶高頻信號。寬帶高頻信號在室內傳播過程中會有信號衰減，若合理設定電源線上注入信號的頻段，使每個節(jié)點接收到的信號強度不同(即構造室內空間的位置指紋)，就可依據(jù)定位目標在室內空間接收到的信號強度確定其所在室內空間的位置。基于電源線的定位需要解決電源線上寬帶信號注入、位置指紋構造和定位算法3方面的問題。

2.1電源線上寬帶高頻信號注入模塊

向電源線注入抗干擾能力強、失真度小的信號是基于電源線的定位技術的基礎。Shwetak等[10]通過濾除110 V電源(美國民用電壓為110 V)，并直接使用昂貴的Agilent 33220A信號發(fā)生器向電源線上注入信號。目前國內外尚未有針對220 V電源線的專用信號發(fā)生器，而已有信號發(fā)生器無法濾除電源線上220 V的50~60 Hz的工頻信號，會被強電燒壞。因此本文采用Arduino Mega開發(fā)板和通用高頻信號發(fā)生器AD9850構造了220 V電源線上的寬帶高頻信號注入模塊，模塊結構圖如圖1所示。

在圖1中，用Arduino Mega開發(fā)板上的處理器是信號注入設備的控制器。其接收用戶輸入的頻率值，按照式(1)計算出頻率控制字，并將頻率控制字送往AD9850信號發(fā)生器。AD9850信號發(fā)生器根據(jù)頻率控制字輸出高頻正弦信號。由于AD9850產生的正弦高頻信號的最大電壓只有1 V左右，該高頻信號在電源線上傳播時，會受到電源線上220 V的工頻信號及其他干擾信號的影響，且1 V的信號電壓太低導致信號迅速衰減。因此本文采用LT1226CS8運算放大器對AD9850產生的高頻信號進行二級放大，使得AD9850產生的1 V高頻正弦波被放大到10 V高頻正弦波，并且波形不失真。最后，放大后的高頻信號通過220 V電壓濾波器注入電源線。220 V電壓濾波器具有通高頻阻低頻的特點，可以濾除220 V工頻信號，保護LT1226CS8運算放大器和AD9850信號發(fā)生器，以防其被電源線上的220 V電壓擊穿。盡管AD9850信號發(fā)生器可以產生100 kHz~30 MHz的信號，但圖1所示模塊生成的信號超過20 MHz時不穩(wěn)定，因此本文采用頻率低于20 MHz的寬帶高頻信號作為注入信號。

2.2 位置指紋構造

位置指紋構造是基于電源線的室內定位的關鍵。Shwetak等人[10]選取房間中相距最遠的兩個電源插座作為信號注入點，分別注入447 kHz和33 kHz的信號構造位置指紋，即每個節(jié)點的位置指紋由接收到的447 kHz和33 kHz信號的強度來確定。該方法構造的位置指紋時間遷移適應能力較弱，定位準確率隨著定位時間與位置指紋構造時間的時間差增加而快速下降。因此本文分別在電源線上注入頻率為1 MHz~8 MHz(步長為500 kHz)共15種頻率信號來構造位置指紋，即房間中每個節(jié)點的位置指紋由接收到的15種頻率值的信號強度共同確定。

位置指紋構造環(huán)境如圖2所示。其中，選取819A室東北角墻上的電源插座作為信號注入點，注入1~8 MHz共15種頻率值的高頻信號；選擇819B室(面積3.6 m×8.1 m)作為位置指紋構造及實驗房間。在819B室中，以0.9 m×0.9 m的正方形為單位，將房間劃分為36個子空間(本文將每個子空間稱為一個節(jié)點)，每個節(jié)點分別標記為A1~I4，其中，字母A~I為行標記，數(shù)字1~4為列標記。

圖2 室內位置指紋構造環(huán)境

2012年課題組從10月6日至12月1日按照每周2次的數(shù)據(jù)采樣頻度，共采集了12組位置指紋數(shù)據(jù)。為了保證采集數(shù)據(jù)的可對比性，實驗人員每次均從傍晚7點開始采集數(shù)據(jù)，每次數(shù)據(jù)采集花費1.5 h。表1所示為1 MHz信號在819B室36個節(jié)點上的信號強度。表中G1和H1(靠近電源線插座)節(jié)點的信號較強，表明信號確實在電源線上傳播，將電源線作為天線的方法確實可行。

表1 1 MHz信號在36個節(jié)點上的信號強度(dB)

3 基于樸素貝葉斯的室內定位算法

室內環(huán)境中通常包含多種電器設備，且具有人員隨機活動，環(huán)境經(jīng)常變化等特征。因此選擇和構造適應環(huán)境變化的算法是實現(xiàn)基于電源線的室內空間準確定位的關鍵。Shwetak在WPLP[16]中采用了KNN算法。雖然提高了KNN算法的時間遷移適應能力，但是該算法在精確度為0.9 m×0.9 m的子空間中得到的定位準確率具有較大波動。本文采用基于樸素貝葉斯分類的位置指紋匹配算法。

3.1 樸素貝葉斯分類算法

樸素貝葉斯分類算法的思想基礎是：對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個最大，就認為此待分類項屬于哪個類別。樸素貝葉斯分類的工作過程如下：

在引入訓練樣本集后，可采用如下步驟計算第3步中的各個條件概率：

步驟..1 找到一個已知分類的待分類項集合，這個集合叫做訓練樣本集；

步驟.3 如果各特征屬性是條件獨立的，則根據(jù)貝葉斯定理有如下推導：

在式(2)中，由于分母對于所有類別為常數(shù)，因此只要使分子最大化即可。此外，由于各屬性是條件獨立的，根據(jù)式(2)可知：

3.2 基于樸素貝葉斯分類的定位原理

若將室內空間中特定區(qū)域對應于分類算法中特定類別，就可將室內空間定位視作采用樸素貝葉斯分類算法判斷待確定節(jié)點屬于哪個區(qū)域。

采用樸素貝葉斯分類算法進行室內定位，其流程包括以下3個階段：

(1)準備工作階段：主要工作是對智能空間中的不同位置進行劃分。在圖2所示的819B室中，包含A1~I4累計64個節(jié)點，每個節(jié)點由15個不同強度的高頻信號標識(即每個節(jié)點包含15維屬性)。此外，為了分析室內定位算法精度與準確率間的關系，課題組將819B室分別劃分為包含3, 6, 10及36類子空間(如圖3所示)。其中，3, 6, 10和36類子空間的定位精度分別為3.6 m×2.7 m, 1.8 m×2.7 m, 1.8 m×1.8 m和0.9 m×0.9 m。針對這些不同類別子空間，由人工對樣本分類訓練，以形成訓練樣本集合。

(2)分類器訓練階段：主要工作是計算每個類別在訓練樣本中的出現(xiàn)頻率及每個特征屬性劃分對每個類別的條件概率估計，得到貝葉斯分類器。此階段由程序根據(jù)式(2)自動計算完成。

(3)應用階段：其任務是使用分類器對測試樣本中的每個測試元組進行分類，其輸入是測試樣本，輸出是測試樣本中每個測試元組的類別，此階段由程序完成。

4 實驗結果分析

課題組將采集的12組數(shù)據(jù)中第1~11組數(shù)據(jù)作為訓練樣本，將第12組數(shù)據(jù)作為測試樣本。此外，課題組同時設計實現(xiàn)了基于KNN的定位算法，以便與基于樸素貝葉斯的定位算法進行對比分析。課題組在進行單樣本訓練時分析發(fā)現(xiàn)：KNN算法中K取值2時，算法對3, 6, 10和36類子空間都有最高定位準確率，因此本文中K值取2。

4.1 KNN和樸素貝葉斯定位算法的準確率對比

為了比較KNN算法和樸素貝葉斯算法的定位效果，課題組采用式(5)來計算兩種位置指紋匹配算法的定位準確率。

準確率=[TP/(TP+TN)]×100% (5)

其中，TP為正確分類的測試元組數(shù)量，即算法輸出的測試樣本中每個測試元組的類別和實際類別一致。TN為錯誤分類的測試元組數(shù)量，即算法輸出的測試樣本中每個測試元組的類別和實際類別不一致。

KNN算法和樸素貝葉斯算法在單訓練樣本情況下的定位準確率對比如圖4所示。圖4中，縱軸表示定位準確率，橫軸表示數(shù)據(jù)采集相對時間點，即測試樣本和訓練樣本間以天為單位的時間偏移值。從圖中可以發(fā)現(xiàn)：以1天為間隔，KNN算法針對3, 6, 10和36類子空間的定位準確率都達到100%，樸素貝葉斯算法定位準確率達到70%以上，說明兩種算法均可有效區(qū)分位置指紋。此外，隨著時間的推移，兩種算法的匹配準確率下降，并且定位精度越高，定位準確率越低。因此課題組采用多組數(shù)據(jù)構成訓練樣本，以分析兩種算法在多訓練樣本下的定位精度和準確率。

圖5所示為在多訓練樣本情況下，基于KNN和樸素貝葉斯的定位算法針對3, 6, 10和36類子空間的定位準確率對比。圖中縱軸表示定位準確率，橫軸表示3, 6, 10和36類子空間。其中，圖5(a)選取第1~6組數(shù)據(jù)作為訓練樣本；圖5(b)選取第1~9組數(shù)據(jù)作為訓練樣本；圖5(c)選取第1~11組數(shù)據(jù)作為訓練樣本。為確保定位結果可對比，共同選取第12組數(shù)據(jù)作為測試樣本。由圖5可發(fā)現(xiàn)如下規(guī)律：

(1)隨著樣本數(shù)量的增加，基于樸素貝葉斯的定位算法的定位準確率逐步提高，基于KNN的定位算法的定位精確度基本保持不變。例如，在6組訓練樣本情況下，基于樸素貝葉斯的定位算法針對36類和10類子空間的定位準確率分別為41.67%和72.22%；在11組訓練樣本情況下，基于樸素貝葉斯的定位算法針對36類和10類子空間的定位準確率分別為63.89%和75.00%；而基于KNN的定位算法在6組、11組訓練樣本情況下，針對36類和10類子空間的定位準確率基本維持在50.00%和72.22%。

圖3 子空間分類

圖4 單訓練樣本下KNN和樸素貝葉斯定位算法準確度對比

圖5 KNN算法和樸素貝葉斯算法在多訓練樣本情況下定位準確率的比較結果

(2)在11組訓練樣本情況下，基于樸素貝葉斯的定位算法針對6, 10和36類子空間的定位準確率基本上都高于基于KNN定位算法的準確率。因此，在較高定位精度情況下，基于樸素貝葉斯定位算法的定位準確率高于基于KNN的定位算法。

4.2 KNN和樸素貝葉斯定位算法時間遷移適應能力對比

在基于位置指紋的室內定位技術中，隨著時間遷移室內環(huán)境經(jīng)常發(fā)生變化，這將影響定位準確率，因此定位算法能否具有較強的時間遷移適應能力非常重要。本文依據(jù)已采樣的12組數(shù)據(jù)，對基于KNN和樸素貝葉斯定位算法的時間遷移適應能力進行了比較分析。

圖6和圖7所示為在單訓練樣本下KNN和樸素貝葉斯定位算法的時間遷移適應能力。其中，縱軸表示定位準確率，橫軸表示測試樣本和訓練樣本間以天數(shù)為單位的時間偏移量。對比圖6和圖7可發(fā)現(xiàn)KNN定位算法對時間遷移的適應能力曲線不平滑，說明KNN定位算法的時間遷移適應能力較弱。而基于樸素貝葉斯的定位算法的定位準確率隨時間遷移的變化曲線相對比較平緩(尤其在3類、6類和36類子空間情況下)。初步可以判斷基于樸素貝葉斯定位算法的時間遷移適應能力強于基于KNN的定位算法。

圖8和圖9所示為6組訓練樣本情況下，兩種定位算法的時間遷移適應能力對比。通過對比可發(fā)現(xiàn)，基于樸素貝葉斯的定位算法在3, 6和10類子空間情況下隨著時間遷移，定位精確度相對穩(wěn)定。其中，在3類子空間中，定位準確率基本維持在65%以上；在6類子空間中，定位準確率基本維持在68%以上；在10類子空間條件下，定位準確率基本維持在70%左右；在36類子空間中，在時間遷移小于20天時，定位準確率基本維持在70%以上，但在時間漂移至27天時，定位精度又急劇下降。與此相對，基于KNN的定位算法在3, 6, 10和36類子空間中，定位準確率均有較大波動。整體而言，基于樸素貝葉斯定位算法的時間遷移適應能力優(yōu)于基于KNN的定位算法。

圖6 單訓練樣本下KNN算法時間遷移適應能力

圖7 單訓練樣本下樸素貝葉斯算法的時間遷移適應能力

圖8 6組訓練樣本下KNN算法時間遷移適應能力

圖9 6組訓練樣本下樸素貝葉斯算法的時間遷移適應能力

4.3 樸素貝葉斯算法的適用性分析

實驗分析證明在多訓練樣本情況下，基于樸素貝葉斯算法比KNN算法具有更好的定位準確率和時間遷移能力，該結論符合樸素貝葉斯定位算法的特性。關于樸素貝葉斯定位算法對本文位置指紋數(shù)據(jù)分類的適用性分析描述為：

(2)從表1中可知G1和H1(靠近電源線插座)節(jié)點的信號較強，即電源線附近節(jié)點具有較高的寬頻信號強度，在越靠近電源線的位置，出現(xiàn)高強度的寬頻信號概率越大。因此，以條件概率為基礎的樸素貝葉斯算法將具有較高寬頻信號強度的節(jié)點分類到靠近電源線的區(qū)域。

綜上所述，由于樸素貝葉斯算法基于條件概率進行決策的特性和寬帶高頻信號在基于電源線的室內定位系統(tǒng)中信號強度分布的特點，不僅從整體上提高了該算法的定位準確率，而且較高的定位準確率也有效保證了樸素貝葉斯算法穩(wěn)定的時間遷移能力。因此，樸素貝葉斯算法對基于電源線和位置指紋分類具有較強的適用性。

5 結束語

本文將室內環(huán)境不可或缺的電源線作為天線，通過在電源線上注入寬帶高頻信號構造室內空間的位置指紋，設計實現(xiàn)了基于樸素貝葉斯的定位算法，實現(xiàn)室內空間的精確定位。同時，實驗分析證明基于樸素貝葉斯的室內定位算法在多訓練樣本情況下，比KNN算法有更高的定位準確率和時間遷移適應能力。下一步，課題組將設計開發(fā)電源線上傳輸?shù)膶拵Ц哳l信號接收模塊；探索應用支持向量機(SVM)、人工神經(jīng)網(wǎng)絡(ANN)等算法，進一步提高定位精度和準確率。

[1] Ward A, Jones A, and Harper A. A new location technique for the active office[J]., 1997, 4(5): 42-47.

[2] Bahl and Padmanabhan V N. RADAR. an in-building RF-based user location and tracking system[C]. Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Piscataway, NJ, USA, 2000: 775-784.

[3] Priyantha N B, Chakraborty A, and Balakrishnan H. The cricket location-support system[C]. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, New York, NJ, USA, 2000: 32-43.

[4] Lorincz K and Welsh M. MoteTrack. a robust, decentralized approach to RF -based location tracking[C]. Proceedings of the International Workshop on Location and Context- Awareness, Berlin, Germany, 2005: 63-82.

[5] Li H B, Shen X F, Zhao J,INEMO: distributed RF-based indoor location determination with confidence indicator[J]., 2007, 3(4): 86-96.

[6] 王珊珊, 殷建平, 蔡志平, 等. 基于 RSSI 的無線傳感器網(wǎng)絡節(jié)點自身定位算法[J]. 計算機研究與發(fā)展, 2008, 45(1): 385-388.

Wang Shan-shan, Yin Jian-ping, Cai Zhi-ping,A RSSI-based self-localization algorithm for wireless sensor networks[J]., 2008, 45(1): 385-388.

[7] Lionel M N, Liu Y H, Lau Y C,LANDMARC: indoor location sensing using active RFID[J]., 2004, 10(6): 701-710.

[8] 孫佩剛, 趙海, 張文波, 等. 普適計算中定位服務的參考點布置及選擇算法[J]. 電子學報, 2006, 34(8): 1456-1463.

Sun Pei-gang, Zhao Hai, Zhang Wen-bo,Research on reference nodes placement and selection of ubiquitous computing locating service[J]., 2006, 34(8): 1456-1463.

[9] 孫佩剛, 趙海, 羅玎玎, 等. 智能空間 RSSI 定位問題研究[J]. 電子學報, 2007, 35(7): 1240-1245.

Sun Pei-gang, Zhao Hai, Luo Ding-ding,Research on RSSI-based location in smart space[J]., 2007, 35(7): 1240-1245.

[10] Shwetak N P, Khai N T, and Gregory D A. PowerLine positioning: a practical sub-room-level indoor location system for domestic use[C]. Proceedings of the Eighth International Conference of Ubiquitous Computing, USA, 2006: 441-458.

[11] 張浩, 劉興, 崔學榮, 等. 基于單基站天線陣列的超寬帶定位 AOA 估計方法[J]. 電子與信息學報, 2013, 8(6): 2024-2028.

Zhang Hao, Liu Xing, Cui Xue-rong,AOA estimation for UWB positioning using a mono-station antenna array [J].&, 2013, 8(6): 2024-2028.

[12] Hossain S, Ariffin S H S, Fisal N,Accuracy enhancement of fingerprint indoor positioning system[C]. Intelligent Systems, Modelling and Simulation (ISMS), Malaysia, 2012: 600-605.

[13] Le Dortz N, Gain F, and Zetterberg P. WiFi fingerprint indoor positioning system using probability distribution comparison[C]. Acoustics, Speech and Signal Processing (ICASSP), Japan, 2012: 2301-2304.

[14] Zhang Yue-xing, Zhu Ying, Lu Ming-ming,Using compressive sensing to reduce fingerprint collection for indoor localization[C]. Wireless Communications and Networking Conference (WCNC), China, 2013: 4540-4545.

[15] Phimmasean S, Chuenurajit T, and Cherntonomwong P. Indoor localization system based on fingerprint technique using RFID passive tag[C]. Electrical Engineering/ Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), Thailand, 2013: 1-6.

[16] Stuntebeck E P, Patel S N, Robertson T,Wideband powerline positioning for indoorlocalization[C]. Proceedings of the 10th International Conference on Ubiquitous Computing, ACM, USA, 2008: 94-103.

何 堅： 男，1969年生，副教授，研究方向為嵌入式軟件與系統(tǒng)和普適計算.

萬志江： 男，1989年生，碩士生，研究方向為嵌入式軟件與系統(tǒng)和室內定位.

Indoor Positioning Technology Based onPowerline and Location Fingerprint

He Jian①Wan Zhi-jiang①Liu Jin-wei②

①(,,100124,)②(,,100124,)

The power line being indispensable under indoor environment is firstly introduced to be as the antenna, which wideband high-frequency signals are injected into it to obtain the location fingerprint so as to achieve precise indoor positioning. Firstly, the realization technology about the injection of the wideband high-frequency signal analysis is proposed, and the construction method of the indoor location fingerprint is deeply described. Meanwhile, the indoor positioning technology based on the naive Bias classification algorithm is discussed at detail. Finally, the experimental analysis shows that the positioning technology based on naive Bayes classification algorithm has higher positioning accuracy and better adaptive ability of time migration than the positioning technology based on K-Nearest Neighbor (KNN) classification algorithm, in the case of multiple training samples.

Indoor positioning; Location fingerprint; Naive Bayes classification algorithm; K-Nearest Neighbor (KNN)

TP391

A

1009-5896(2014)12-2902-07

10.3724/SP.J.1146.2013.02022

萬志江 wandndn@gmail.com

2013-12-25收到，2014-04-15改回

國家自然科學基金(61040039)，北京市自然科學基金(4102005)和北京市教委科研計劃(KM201210005029)資助課題