本发明公开了基于接收信号强度和参考点位置双聚类的室内定位方法，主要解决现有室内定位方法参考点聚类不准确，定位精度差的问题。其实现步骤为：(1)选择参考点，测量接收信号强度，存入数据库；(2)按照接收信号强度对所有参考点进行第一次聚类；(3)对第一次聚类得到的簇按照位置进行第二次聚类；(4)计算第二次聚类得到的簇之间的距离，合并距离小的簇为一簇；(5)测量待定位点的接收信号强度，粗定位匹配簇；(6)利用粗定位匹配的簇，通过压缩感知精确定位。本发明减小了定位误差，提高了定位精度，可用于Wi‑Fi接收机的室内定位。
1.基于接收信号强度和参考点位置双聚类的室内定位方法，包括两个阶段：
1a)选择一个布设有Wi-Fi接入点APs的区域；
1b)在此区域内选择N个参考点RPs，并测量这N个参考点在四个方向上接收的来自周围接入点的接收信号强度RSS，存到数据库X(o)中；
1c)按照接收信号强度RSS对所有参考点RPs，采用吸引子传播算法AP进行第一次聚类；
1d)对第一次聚类得到的每个簇，再按照地理位置采用吸引子传播算法AP进行第二次聚类；
1e)判断第二次聚类的簇数量：如果第二次聚类得到的簇数量是大于等于2的正整数，则求出这些簇的两两之间的距离，将距离小于4米的簇合并为一簇，将聚类结果记录到数据库中，否则，直接将聚类结果记录到数据库中，完成指纹数据库的构建；
2a)在待定位点测得来自周围L个接入点APs的接收信号强度RSS向量：χr＝[χ1,r,...,χk,r,...,χL,r]T，其中{χk,r,k＝1,2,...,L}是移动设备在任意一个方向上采集的来自第k个接入点APs的数据；
求出待定位点的接收信号强度RSS向量χr与指纹数据库中各个簇的聚类中心的接收信号强度RSS向量之间的相似度，相似度被定义为：其中 为第j个簇的聚类中心在方向o上的接收信号强度RSS向量，H为所有簇的聚类中心的集合，O＝{0°,90°,180°,270°}；
将相似度s(r,j)(o)大于阈值α的簇作为粗定位匹配的簇；
2c)精确定位：随机选取8个接入点APs，利用这8个接入点APs和粗定位匹配得到的簇成员接收信号强度RSS，通过压缩感知算法求出待定位点的精确位置，完成待定位点的定位。
2.根据权利要求1所述的基于接收信号强度和参考点位置双聚类的室内定位方法，其特征在于，步骤1b)中的数据库X(o)表示为:其中 是在第j个参考点RPs处于方向o上采集的来自第i个接入点APs的接收信号强度RSS的平均值， 表示第τ次采集的接收信号强度RSS，q表示每个参考点上的总采集次数，i＝1,2,...,L，j＝1,2,...,N，o∈O＝{0°,90°,180°,270°}，L是能被检测到的接入点APs的总个数，N是参考点的总数。
3.根据权利要求1所述的基于接收信号强度和参考点位置双聚类的室内定位方法，其特征在于，步骤1c)中按照参考点RPs的接收信号强度RSS进行的第一次聚类，按如下步骤进行：
1c1)利用所有参考点RPs的接收信号强度RSS向量计算参考度p(o)；
1c2)利用参考度p(o)和参考点接收信号强度RSS向量迭代求出聚类中心，每个聚类中心代表一个簇；
1c3)将所有参考点划分到相应的簇中，完成第一次吸引子传播算法AP聚类。
4.根据权利要求1所述的基于接收信号强度和参考点位置双聚类的室内定位方法，其特征在于，步骤1e)中的两个簇之间的距离，为一个簇的所有成员与另一个簇的所有成员的欧氏距离的平均值。
5.根据权利要求3所述的基于接收信号强度和参考点位置双聚类的室内定位方法，其特征在于，步骤1c1)中利用所有参考点RPs的接收信号强度RSS向量计算参考度p(o)，其计算公式为：其中γ(o)是一个由实验确定的实数，s(i,j)(o)为第i个参考点和第j个参考点的接收信号强度RSS向量的相似度，N为参考点RPs的总数，o∈O＝{0°,90°,180°,270°}，median表示求中位数运算。
6.根据权利要求3所述的基于接收信号强度和参考点位置双聚类的室内定位方法，其特征在于，步骤1c2)中利用参考度p(o)和参考点接收信号强度RSS向量迭代求出聚类中心，按如下步骤进行：首先，令s(i,i)(o)＝p(o)，创建N行N列的吸引度矩阵r(o)和N行N列的归属度矩阵a(o)，其中i＝1,2,...,N，两个矩阵初始元素全部为零；
接着，更新计算吸引度矩阵r(o)和归属度矩阵a(o)的元素值：其中，j＝1,2,...,N，i'＝1,2,...,N，j'＝1,2,...,N，r(i,j)(o)为吸引度矩阵r(o)的第i行第j列的元素，a(i,j)(o)为归属度矩阵a(o)的第i行第j列的元素，s(i,j)(o)为第i个参考点和第j个参考点的接收信号强度RSS向量的相似度；
然后，定义N维向量c，计算向量c的第i个元素的值：c(i)＝a(i,i)(o)+r(i,i)(o)，判断c(i)的大小：如果c(i)>0，则第i个参考点为聚类中心，否则，第i个参考点不是聚类中心；
最后，判断聚类结果是否收敛：如果收敛，则直接进入步骤1c3)，否则，更新计算吸引度(o) (o)矩阵r 和归属度矩阵a 的元素值，直至聚类结果收敛或达到预设的最大迭代次数，然后进入步骤1c3)。
基于接收信号强度和参考点位置双聚类的室内定位方法
技术领域
[0001] 本发明属于无线通信技术领域，更进一步涉及室内定位领域，可用于覆盖Wi-Fi信号的室内环境，完成当前位置的定位。
背景技术
[0002] 当前，随着无线网络的发展和无线局域网的广泛部署，基于Wi-Fi的室内定位技术受到广泛重视。在覆盖Wi-Fi网络的室内环境下，通过测量来自接入点APs的接收信号强度RSS，结合采集好的信号强度数据库求解，确定移动用户的位置。这种基于位置指纹的定位算法因其定位精度高、可充分利用现有设施、升级和维护对用户影响小等优点而得到广泛应用。为了提高定位精度和效率，需要对采集的位置指纹数据进行预处理。普遍使用的预处理方法是对参考点RPs进行聚类运算，得到若干个聚类中心及其类成员。
[0003] 现有的应用比较多的聚类方法包括两种，一是K-means聚类，另一种是吸引子传播聚类。K-means算法首先随机选择K个对象初始的代表聚类中心，再对剩下的每个对象根据其与各个聚类中心的距离将它重新赋给最近的类，然后重新计算每个类的中心作为下一次迭代的聚类中心。不断重复这个过程，直到各聚类中心不再变化时终止。吸引子传播聚类算法相比K-means算法，不需要初始化聚类中心，而是通过设定一个实数值将每一个参考点都当成一个潜在的聚类中心。接着，两个参考点之间相互传递近邻信息，参考点根据近邻信息选择哪一个参考点作为聚类中心，直到聚类中心以及相关的类产生。但由于受到接入点布局、建筑结构以及人的走动等外界因素的影响，离得较远的参考点可能有相似的RSS，导致聚类时同属一簇，或者在采集RSS时会出现扰动，导致有的参考点的RSS出现较大误差，在聚类时可能被归于不恰当的簇。直接导致到定位精度下降。
发明内容
[0004] 本发明的目的在于针对上述已有技术的不足，提出一种基于接收信号强度聚类和参考点位置聚类的室内定位方法，以提高室内定位的精度。
[0005] 实现本发明目的地技术思路是：通过采用接收信号强度聚类和参考点位置聚类的双聚类技术，对参考点进行有效的聚类，形成一定数量聚类中心及其类成员，以此减少定位阶段计算量，提高定位精度。其实现方案如下：
[0006] 1)离线阶段：
[0007] 1a)选择一个布设有Wi-Fi接入点APs的区域；
[0008] 1b)在此区域内选择N个参考点RPs，并测量这N个参考点在四个方向上接收的来自周围接入点的接收信号强度RSS，存到数据库Χ(o)中；
[0009] 1c)按照接收信号强度RSS对所有参考点RPs，采用吸引子传播算法AP进行第一次聚类；
[0010] 1d)对第一次聚类得到的每个簇，再按照地理位置采用吸引子传播算法AP进行第二次聚类；
[0011] 1e)判断第二次聚类的簇数量：如果第二次聚类得到的簇数量是大于等于2的正整数，则求出这些簇的两两之间的距离，将距离小于4米的簇合并为一簇，将聚类结果记录到数据库中，否则，直接将聚类结果记录到数据库中，完成指纹数据库的构建；
[0012] 2)在线阶段：
[0013] 2a)在待定位点测得来自周围L个接入点APs的接收信号强度RSS向量：
[0014] χr＝[χ1,r,...,χk,r,...,χL,r]T，
[0015] 其中{χk,r,k＝1,2,...,L}是移动设备在任意一个方向上采集的来自第k个接入点APs的数据；
[0016] 2b)粗定位：
[0017] 求出待定位点的接收信号强度RSS向量χr与指纹数据库中各个簇的聚类中心的接收信号强度RSS向量之间的相似度，相似度被定义为：
[0018]
[0019] 其中 为第j个簇的聚类中心在方向o上的接收信号强度RSS向量，H为所有簇的聚类中心的集合，Ο＝{0°,90°,180°,270°}；
[0020] 设置阈值： 其中α1+α2＝1；
[0021] 将相似度s(r,j)(o)大于阈值α的簇作为粗定位匹配的簇；
[0022] 2c)精确定位：随机选取8个接入点APs，利用这8个接入点APs和粗定位匹配得到的簇成员接收信号强度RSS，通过压缩感知算法求出待定位点的精确位置，完成待定位点的定位。
[0023] 本发明与现有技术相比具有以下优点：
[0024] 第一，由于本发明采用了接收信号强度聚类和参考点位置聚类的双聚类技术，且将原来一个簇中地理位置离其它簇成员较远的成员独立的分为一个簇，避免了地理位置离的较远但接收信号强度RSS接近的参考点被聚为同一个簇的情况；
[0025] 第二，由于本发明采用了接收信号强度聚类和参考点位置聚类的双聚类技术，且将本不应被拆开的簇再合并成一个簇，完成奇异点处理的同时能够保证原来簇的完整性，从而达到更好的聚类效果。
附图说明
[0026] 图1是本发明的实现流程图；
[0027] 图2是本发明中的实验区域示意图；
[0028] 图3是本发明中在实验区域进行参考点第一次聚类的结果图；
[0029] 图4是本发明中的第二次聚类结果图；
[0030] 图5是本发明在第二次聚类中将一个簇正确拆分成两个簇的结果图；
[0031] 图6是本发明在第二次聚类中在簇中找出奇异点的结果图；
[0032] 图7是本发明在第二次聚类中将一个不该拆分的簇拆分的结果图；
[0033] 图8是本发明在第二次聚类后将不该拆分的簇合并为一个簇的结果图；
[0034] 图9是本发明与现有未改进的室内定位方法的定位误差概率分布曲线图。
具体实施方式
[0035] 下面将结合附图，对本发明的优选实例进行详细的描述。
[0036] 参照图1，本发明的实施步骤分为离线阶段和在线阶段，在离线阶段建立指纹数据库，在线阶段用于实时定位，具体实现步骤如下：
[0037] 步骤1，离线阶段建立指纹数据库。
[0038] 1a)选择一个布设有Wi-Fi接入点APs的区域，本实例区域为西安电子科技大学主楼II区部分区域，长约21米，宽约8米，如图2所示；
[0039] 1b)在图2区域内选择N＝37个参考点RPs，如图3所示，并测量这37个参考点在四个方向上接收的来自周围L＝36个接入点APs的接收信号强度RSS，存到数据库中，这个数据库表示为Χ(o)：
[0040]
[0041] 其中 是在第j个参考点RPs处于方向o上采集的来自第i个接入点APs的接收信号强度RSS的平均值，i＝1,2,…,36，j＝1,2,…,37，o∈Ο＝{0°,90°,180°,
270°}，q＝25表示每个参考点上的采样次数，每秒钟采样一次；
[0042] 1c)按照接收信号强度RSS对所有参考点RPs采用吸引子传播算法AP进行第一次聚类：
[0043] 所述吸引子传播算法AP，参照文献Clustering by Passing Messages Between Data Points，Frey，Brendan J.1，Dueck，Detbert1，该算法是根据数据点之间的相似度进行聚类，不需要事先指定聚类得到的簇数量，相反，它将所有的数据点都作为潜在的聚类中心。聚类的簇数量受到参考度的影响，如果取输入数据的相似度的中位数作为参考度的值，则聚类得到簇数量是中等的，如果参考度取较小值，聚类得到的簇数量就较少。该算法通过迭代过程不断更新所有数据点的吸引度和归属度的数值，如果某个数据点的归属度和吸引度之和大于预设的某个数值，则这个数据点是聚类中心，否则不是聚类中心，迭代至聚类结果收敛或达到预设的最大迭代次数时，聚类完成。其具体步骤如下：
[0044] 1c1)利用所有参考点RPs的接收信号强度RSS向量计算参考度p(o)；
[0045] 1c2)利用参考度p(o)和参考点接收信号强度RSS向量迭代求出聚类中心，每个聚类中心代表一个簇：
[0046] 1c2-1)，利用所有参考点RPs的接收信号强度RSS向量计算参考度p(o)，其计算公式为：
[0047]
[0048] 其中γ(o)是一个由实验确定的实数，本实例取γ(o)＝0.95，s(i,j)(o)为第i个参考点和第j个参考点的接收信号强度RSS向量的相似度，N为参考点RPs的总数，本实例为37，o∈Ο＝{0°,90°,180°,270°}，median表示求中位数运算。
[0049] 1c2-2)，令s(i,i)(o)＝p(o)，创建N行N列的吸引度矩阵r(o)和N行N列的归属度矩阵a(o)，其中i＝1,2,...,N，两个矩阵初始元素全部为零；
[0050] 1c2-3)，更新计算吸引度矩阵r(o)和归属度矩阵a(o)的元素值：
[0051]
[0052]
[0053] 其中，j＝1,2,…,N，i'＝1,2,…,N，j'＝1,2,…,N，r(i,j)(o)为吸引度矩阵r(o)的第i行第j列的元素，a(i,j)(o)为归属度矩阵a(o)的第i行第j列的元素，s(i,j)(o)为第i个参考点和第j个参考点的接收信号强度RSS向量的相似度；
[0054] 1c2-4)，定义N维向量c，计算向量c的第i个元素的值：c(i)＝a(i,i)(o)+r(i,i)(o)，判断c(i)的大小：如果c(i)>0，则第i个参考点为聚类中心，否则，第i个参考点不是聚类中心；
[0055] 1c2-5)，判断聚类结果是否收敛：如果收敛，则直接进入步骤1c3)，否则，更新计算吸引度矩阵r(o)和归属度矩阵a(o)的元素值，直至聚类结果收敛或达到预设的最大迭代次数，然后进入步骤1c3)。
[0056] 1c3)将所有参考点划分到相应的簇中，完成第一次吸引子传播算法AP聚类，聚类结果如图3所示，图3中相同形状的点属于同一个簇，37个参考点被聚成了6个簇。可以看出，菱形代表的那个簇在地理位置上被分成了两个部分，星形代表的那个簇最下方的点是一个奇异点；
[0057] 1d)对第一次聚类得到的每个簇，再按照地理位置采用吸引子传播算法AP进行第二次聚类：
[0058] 1d1)利用第一次聚类得到的每个簇的参考点RPs的接收信号强度RSS向量计算参(o)考度pd ；
[0059] 1d2)利用参考度pd(o)和参考点接收信号强度RSS向量迭代求出聚类中心，每个聚类中心代表一个簇，按如下步骤进行：
[0060] 1d2-1)，利用第一次聚类得到的每个簇的参考点RPs的接收信号强度RSS向量计算参考度pd(o)，其计算公式为
[0061]
[0062] 其中γd(o)是一个由实验确定的实数，本实例取γd(o)＝1.2，d(i,j)(o)为第i个参考点和第j个参考点的地理位置欧式距离的相反数，M为需要聚类的参考点RPs的数量，o∈Ο＝{0°,90°,180°,270°}，median表示求中位数运算。
[0063] 1d2-2)，令s(i,i)d(o)＝pd(o)，创建M行M列的吸引度矩阵rd(o)和M行M列的归属度矩阵ad(o)，其中i＝1,2,...,M，两个矩阵初始元素全部为零；
[0064] 1d2-3)，更新计算吸引度矩阵rd(o)和归属度矩阵ad(o)的元素值：
[0065]
[0066]
[0067] 其中，j＝1,2,…,M，i'＝1,2,…,M，j'＝1,2,…,M，r(i,j)d(o)为吸引度矩阵rd(o)的第i行第j列的元素，a(i,j)d(o)为归属度矩阵ad(o)的第i行第j列的元素，s(i,j)d(o)为第i个参考点与第j个参考点的地理位置欧式距离的相反数；
[0068] 1d2-4)，定义M维向量cd，计算向量cd的第i个元素的值：cd(i)＝a(i,i)d(o)+r(i,i)d(o)，判断cd(i)的大小：如果cd(i)＞0，则第i个参考点为聚类中心，否则，第i个参考点不是聚类中心；
[0069] 1d2-5)，判断聚类结果是否收敛：如果收敛，则直接进入步骤1d3)，否则，将参考度pd(o)变为原来参考度的1.5倍，更新计算吸引度矩阵rd(o)和归属度矩阵ad(o)的元素值，直至聚类结果收敛，然后进入步骤1d3)。
[0070] 1d3)将所有参考点划分到相应的簇中；
[0071] 1e)判断第二次聚类得到的簇数量：如果第二次聚类得到的簇数量是大于等于2的正整数，则求出这些簇两两之间的距离，两个簇之间的距离为一个簇的所有成员与另一个簇的所有成员的欧氏距离的平均值。合并距离小于4米的簇为一簇，完成第二次吸引子传播算法AP聚类，聚类结果如图4所示。
[0072] 在第二次聚类过程中产生的部分结果如图5至图8所示，其中：
[0073] 图5为第二次聚类过程中产生的两个簇，其距离为7.9615米，不进行合并；
[0074] 图6为第二次聚类得到的簇中的奇异点，即图6中三角形点，被成功找出，这个奇异点单独划为一个簇；
[0075] 图7为第二次聚类过程中得到的两个簇，其距离为2.9566米，合并为一个簇，[0076] 图8为图7中两个簇合并的结果图；
[0077] 将聚类结果记录到数据库中，指纹数据库构建完成。
[0078] 步骤2，在线阶段实时定位。
[0079] 2a)在待定位点测得来自周围L＝36个接入点APs的接收信号强度RSS向量：
[0080] χr＝[χ1,r,...,χk,r,...,χL,r]T
[0081] 其中{χk,r,k＝1,2,...,36}是移动设备在任意一个方向上采集的数据。
[0082] 2b)求出待定位点的接收信号强度RSS向量χr与指纹数据库中各个簇的聚类中心的接收信号强度RSS向量之间的相似度，相似度被定义为：
[0083]
[0084] 其中 为第j个簇的聚类中心在方向o上的接收信号强度RSS向量，H为所有簇的聚类中心的集合，Ο＝{0°,90°,180°,270°}；
[0085] 设置阈值： 其中α1+α2＝1，本实例α1＝0.95；
[0086] 将相似度s(r,j)(o)大于阈值α的簇作为粗定位匹配的簇；
[0087] 2c)精确定位：随机选取8个接入点APs，利用这8个接入点APs和粗定位匹配得到的簇的簇成员的接收信号强度RSS，通过压缩感知算法求出待定位点的精确位置，完成待定位点的定位。
[0088] 本发明的效果可通过以下实验进一步详细说明。
[0089] 用本发明与现有的Wi-Fi室内定位技术进行定位。
[0090] 现有Wi-Fi室内定位技术为：
[0091] 在离线阶段采集参考点的接收信号强度RSS指纹数据，根据接收信号强度RSS对参考点进行一次聚类，构建指纹数据库，而不进行第二次聚类；在线阶段进行实时定位，采集待定位点处的接收信号强度RSS，粗定位阶段匹配若干个簇，精确定位阶段利用粗定位阶段匹配得到的簇，通过压缩感知算法得出待定位点的位置。
[0092] 选取10个待定位点，每个点采用本发明和现有技术分别定位10次，记录待定位点实际位置和每次定位的结果，计算定位误差，定位误差为待定位点的实际位置和定位结果之间的欧氏距离。计算本发明和现有技术的平均定位误差，并统计其误差的概率分布，结果如图9所示。
[0093] 从图9可以看出：除了最初1米，带圈实线远在带星花实线之上，说明在同样环境条件下，本发明的定位精度明显高于现有技术的定位精度。
[0094] 从图9还可以看出：现有技术定位误差在3米以内的概率为0.5，而本发明定位误差在3米以内的概率为0.7；现有技术定位误差在4米以内的概率为0.66，而本发明定位误差在4米以内的概率为0.88；现有技术的最大定位误差约11米，而本发明的最大定位误差约为5米。
[0095] 通过计算得知，现有技术的平均定位误差为3.2919米，本发明的平均定位误差为2.4225米。
[0096] 综上，本发明的定位精度高于现有技术的定位精度。
