何 坚 万志江 刘金伟



基于电源线和位置指纹的室内定位技术

何 坚①万志江*①刘金伟②

①(北京工业大学软件学院 北京 100124)②(北京工业大学信息中心 北京 100124)

该文提出将室内环境不可或缺的电源线作为天线，通过在电源线上注入宽带高频信号构造室内空间的位置指纹，进而实现室内空间精确定位。首先介绍了电源线上宽带高频信号注入模块的实现技术，以及室内空间位置指纹的构造方法；其次，介绍了基于朴素贝叶斯分类算法的室内定位原理；最后，通过实验分析证明在多训练样本情况下，基于朴素贝叶斯分类算法的定位算法比基于K最邻近点(KNN)分类算法的定位算法有更好的定位准确率和时间迁移适应能力。

室内定位；位置指纹；朴素贝叶斯分类算法；K最邻近点

1 引言

本文首先介绍基于电源线的室内定位原理，220 V电源线上宽带高频信号注入模块的实现技术，以及室内空间位置指纹的构造方法；其次，介绍基于朴素贝叶斯的室内空间定位原理和实现方法；最后，通过实验分析证明在多训练样本情况下，基于朴素贝叶斯的定位算法比基于KNN的定位算法有更好的定位准确率和时间迁移适应能力。

2 相关基础工作

本文将室内空间划分为等间距的不同节点，并以部署在房间墙体内的电源线作为天线，在电源线上输入宽带高频信号。宽带高频信号在室内传播过程中会有信号衰减，若合理设定电源线上注入信号的频段，使每个节点接收到的信号强度不同(即构造室内空间的位置指纹)，就可依据定位目标在室内空间接收到的信号强度确定其所在室内空间的位置。基于电源线的定位需要解决电源线上宽带信号注入、位置指纹构造和定位算法3方面的问题。

2.1电源线上宽带高频信号注入模块

向电源线注入抗干扰能力强、失真度小的信号是基于电源线的定位技术的基础。Shwetak等[10]通过滤除110 V电源(美国民用电压为110 V)，并直接使用昂贵的Agilent 33220A信号发生器向电源线上注入信号。目前国内外尚未有针对220 V电源线的专用信号发生器，而已有信号发生器无法滤除电源线上220 V的50~60 Hz的工频信号，会被强电烧坏。因此本文采用Arduino Mega开发板和通用高频信号发生器AD9850构造了220 V电源线上的宽带高频信号注入模块，模块结构图如图1所示。

在图1中，用Arduino Mega开发板上的处理器是信号注入设备的控制器。其接收用户输入的频率值，按照式(1)计算出频率控制字，并将频率控制字送往AD9850信号发生器。AD9850信号发生器根据频率控制字输出高频正弦信号。由于AD9850产生的正弦高频信号的最大电压只有1 V左右，该高频信号在电源线上传播时，会受到电源线上220 V的工频信号及其他干扰信号的影响，且1 V的信号电压太低导致信号迅速衰减。因此本文采用LT1226CS8运算放大器对AD9850产生的高频信号进行二级放大，使得AD9850产生的1 V高频正弦波被放大到10 V高频正弦波，并且波形不失真。最后，放大后的高频信号通过220 V电压滤波器注入电源线。220 V电压滤波器具有通高频阻低频的特点，可以滤除220 V工频信号，保护LT1226CS8运算放大器和AD9850信号发生器，以防其被电源线上的220 V电压击穿。尽管AD9850信号发生器可以产生100 kHz~30 MHz的信号，但图1所示模块生成的信号超过20 MHz时不稳定，因此本文采用频率低于20 MHz的宽带高频信号作为注入信号。

2.2 位置指纹构造

位置指纹构造是基于电源线的室内定位的关键。Shwetak等人[10]选取房间中相距最远的两个电源插座作为信号注入点，分别注入447 kHz和33 kHz的信号构造位置指纹，即每个节点的位置指纹由接收到的447 kHz和33 kHz信号的强度来确定。该方法构造的位置指纹时间迁移适应能力较弱，定位准确率随着定位时间与位置指纹构造时间的时间差增加而快速下降。因此本文分别在电源线上注入频率为1 MHz~8 MHz(步长为500 kHz)共15种频率信号来构造位置指纹，即房间中每个节点的位置指纹由接收到的15种频率值的信号强度共同确定。

位置指纹构造环境如图2所示。其中，选取819A室东北角墙上的电源插座作为信号注入点，注入1~8 MHz共15种频率值的高频信号；选择819B室(面积3.6 m×8.1 m)作为位置指纹构造及实验房间。在819B室中，以0.9 m×0.9 m的正方形为单位，将房间划分为36个子空间(本文将每个子空间称为一个节点)，每个节点分别标记为A1~I4，其中，字母A~I为行标记，数字1~4为列标记。

图2 室内位置指纹构造环境

2012年课题组从10月6日至12月1日按照每周2次的数据采样频度，共采集了12组位置指纹数据。为了保证采集数据的可对比性，实验人员每次均从傍晚7点开始采集数据，每次数据采集花费1.5 h。表1所示为1 MHz信号在819B室36个节点上的信号强度。表中G1和H1(靠近电源线插座)节点的信号较强，表明信号确实在电源线上传播，将电源线作为天线的方法确实可行。

表1 1 MHz信号在36个节点上的信号强度(dB)

3 基于朴素贝叶斯的室内定位算法

室内环境中通常包含多种电器设备，且具有人员随机活动，环境经常变化等特征。因此选择和构造适应环境变化的算法是实现基于电源线的室内空间准确定位的关键。Shwetak在WPLP[16]中采用了KNN算法。虽然提高了KNN算法的时间迁移适应能力，但是该算法在精确度为0.9 m×0.9 m的子空间中得到的定位准确率具有较大波动。本文采用基于朴素贝叶斯分类的位置指纹匹配算法。

3.1 朴素贝叶斯分类算法

朴素贝叶斯分类算法的思想基础是：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。朴素贝叶斯分类的工作过程如下：

在引入训练样本集后，可采用如下步骤计算第3步中的各个条件概率：

步骤..1 找到一个已知分类的待分类项集合，这个集合叫做训练样本集；

步骤.3 如果各特征属性是条件独立的，则根据贝叶斯定理有如下推导：

在式(2)中，由于分母对于所有类别为常数，因此只要使分子最大化即可。此外，由于各属性是条件独立的，根据式(2)可知：

3.2 基于朴素贝叶斯分类的定位原理

若将室内空间中特定区域对应于分类算法中特定类别，就可将室内空间定位视作采用朴素贝叶斯分类算法判断待确定节点属于哪个区域。

采用朴素贝叶斯分类算法进行室内定位，其流程包括以下3个阶段：

(1)准备工作阶段：主要工作是对智能空间中的不同位置进行划分。在图2所示的819B室中，包含A1~I4累计64个节点，每个节点由15个不同强度的高频信号标识(即每个节点包含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)分类器训练阶段：主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，得到贝叶斯分类器。此阶段由程序根据式(2)自动计算完成。

(3)应用阶段：其任务是使用分类器对测试样本中的每个测试元组进行分类，其输入是测试样本，输出是测试样本中每个测试元组的类别，此阶段由程序完成。

4 实验结果分析

课题组将采集的12组数据中第1~11组数据作为训练样本，将第12组数据作为测试样本。此外，课题组同时设计实现了基于KNN的定位算法，以便与基于朴素贝叶斯的定位算法进行对比分析。课题组在进行单样本训练时分析发现：KNN算法中K取值2时，算法对3, 6, 10和36类子空间都有最高定位准确率，因此本文中K值取2。

4.1 KNN和朴素贝叶斯定位算法的准确率对比

为了比较KNN算法和朴素贝叶斯算法的定位效果，课题组采用式(5)来计算两种位置指纹匹配算法的定位准确率。

准确率=[TP/(TP+TN)]×100% (5)

其中，TP为正确分类的测试元组数量，即算法输出的测试样本中每个测试元组的类别和实际类别一致。TN为错误分类的测试元组数量，即算法输出的测试样本中每个测试元组的类别和实际类别不一致。

KNN算法和朴素贝叶斯算法在单训练样本情况下的定位准确率对比如图4所示。图4中，纵轴表示定位准确率，横轴表示数据采集相对时间点，即测试样本和训练样本间以天为单位的时间偏移值。从图中可以发现：以1天为间隔，KNN算法针对3, 6, 10和36类子空间的定位准确率都达到100%，朴素贝叶斯算法定位准确率达到70%以上，说明两种算法均可有效区分位置指纹。此外，随着时间的推移，两种算法的匹配准确率下降，并且定位精度越高，定位准确率越低。因此课题组采用多组数据构成训练样本，以分析两种算法在多训练样本下的定位精度和准确率。

图5所示为在多训练样本情况下，基于KNN和朴素贝叶斯的定位算法针对3, 6, 10和36类子空间的定位准确率对比。图中纵轴表示定位准确率，横轴表示3, 6, 10和36类子空间。其中，图5(a)选取第1~6组数据作为训练样本；图5(b)选取第1~9组数据作为训练样本；图5(c)选取第1~11组数据作为训练样本。为确保定位结果可对比，共同选取第12组数据作为测试样本。由图5可发现如下规律：

(1)随着样本数量的增加，基于朴素贝叶斯的定位算法的定位准确率逐步提高，基于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和朴素贝叶斯定位算法时间迁移适应能力对比

在基于位置指纹的室内定位技术中，随着时间迁移室内环境经常发生变化，这将影响定位准确率，因此定位算法能否具有较强的时间迁移适应能力非常重要。本文依据已采样的12组数据，对基于KNN和朴素贝叶斯定位算法的时间迁移适应能力进行了比较分析。

图6和图7所示为在单训练样本下KNN和朴素贝叶斯定位算法的时间迁移适应能力。其中，纵轴表示定位准确率，横轴表示测试样本和训练样本间以天数为单位的时间偏移量。对比图6和图7可发现KNN定位算法对时间迁移的适应能力曲线不平滑，说明KNN定位算法的时间迁移适应能力较弱。而基于朴素贝叶斯的定位算法的定位准确率随时间迁移的变化曲线相对比较平缓(尤其在3类、6类和36类子空间情况下)。初步可以判断基于朴素贝叶斯定位算法的时间迁移适应能力强于基于KNN的定位算法。

图8和图9所示为6组训练样本情况下，两种定位算法的时间迁移适应能力对比。通过对比可发现，基于朴素贝叶斯的定位算法在3, 6和10类子空间情况下随着时间迁移，定位精确度相对稳定。其中，在3类子空间中，定位准确率基本维持在65%以上；在6类子空间中，定位准确率基本维持在68%以上；在10类子空间条件下，定位准确率基本维持在70%左右；在36类子空间中，在时间迁移小于20天时，定位准确率基本维持在70%以上，但在时间漂移至27天时，定位精度又急剧下降。与此相对，基于KNN的定位算法在3, 6, 10和36类子空间中，定位准确率均有较大波动。整体而言，基于朴素贝叶斯定位算法的时间迁移适应能力优于基于KNN的定位算法。

图6 单训练样本下KNN算法时间迁移适应能力

图7 单训练样本下朴素贝叶斯算法的时间迁移适应能力

图8 6组训练样本下KNN算法时间迁移适应能力

图9 6组训练样本下朴素贝叶斯算法的时间迁移适应能力

4.3 朴素贝叶斯算法的适用性分析

实验分析证明在多训练样本情况下，基于朴素贝叶斯算法比KNN算法具有更好的定位准确率和时间迁移能力，该结论符合朴素贝叶斯定位算法的特性。关于朴素贝叶斯定位算法对本文位置指纹数据分类的适用性分析描述为：

(2)从表1中可知G1和H1(靠近电源线插座)节点的信号较强，即电源线附近节点具有较高的宽频信号强度，在越靠近电源线的位置，出现高强度的宽频信号概率越大。因此，以条件概率为基础的朴素贝叶斯算法将具有较高宽频信号强度的节点分类到靠近电源线的区域。

综上所述，由于朴素贝叶斯算法基于条件概率进行决策的特性和宽带高频信号在基于电源线的室内定位系统中信号强度分布的特点，不仅从整体上提高了该算法的定位准确率，而且较高的定位准确率也有效保证了朴素贝叶斯算法稳定的时间迁移能力。因此，朴素贝叶斯算法对基于电源线和位置指纹分类具有较强的适用性。

5 结束语

本文将室内环境不可或缺的电源线作为天线，通过在电源线上注入宽带高频信号构造室内空间的位置指纹，设计实现了基于朴素贝叶斯的定位算法，实现室内空间的精确定位。同时，实验分析证明基于朴素贝叶斯的室内定位算法在多训练样本情况下，比KNN算法有更高的定位准确率和时间迁移适应能力。下一步，课题组将设计开发电源线上传输的宽带高频信号接收模块；探索应用支持向量机(SVM)、人工神经网络(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 的无线传感器网络节点自身定位算法[J]. 计算机研究与发展, 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年生，副教授，研究方向为嵌入式软件与系统和普适计算.

万志江： 男，1989年生，硕士生，研究方向为嵌入式软件与系统和室内定位.

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)资助课题