专利摘要

专利摘要

本发明提出一种基于NSGA‑II算法的iBeacon基站空间布局优化及室内定位方法。本发明针对iBeacon发送射频信号受环境如遮挡物干扰大，且不稳定的缺点，采用遗传优化算法，设计空间布局优化的iBeacon基站部署方案，最大限度的弥补信号不稳定导致的定位精度下降。本发明实现的室内定位计算方法，采用4个基站数据计算待测点，比传统的3个基站计算具有更加稳定、更加精准的优势。本发明具有定位精度高、成本低、实施简单、可推广性强的优点，并且可通过选择经优化后的设备部署方案，在最低的部署成本下满足不同的定位精度需求。

权利要求

1.一种基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法，该方法具体包括以下步骤：

步骤一：将室内待部署iBeacon基站的区域，按1米×1米划分成网格，每个网格按行列编上编号(i,j)，区域平面图最左上角的网格编号为(0,0)，其余的依次累加“1”，每个网格内都有可能部署一个iBeacon基站；

步骤二：将整个区域的网格利用二进制编码，转换成NSGA-II算法的基因序列，序列中“1”代表部署iBeacon基站，“0”代表没有部署；随机初始化iBeacon基站的部署方案，以待测点与基站平均最短距离和部署成本为优化目标进行优化，最终生成iBeacon基站的部署方案最优集；

其中，步骤二包括：

(1)将室内待部署iBeacon基站1米×1米网格区域，视为二维数组，将其按行转化为一维数组，作为遗传算法二进制编码的基因序列，同时记录每个基因在二维数组中的行列编号(i，j)；

(2)以随机法进行种群初始化，即基因序列中随机函数生成“0”、“1”，“1”代表部署iBeacon基站，“0”代表没有部署；

(3)以待测点与iBeacon基站的平均距离越短，收到的信号越强，从而获得待测点位置的精度越高为假设前提，确定iBeacon基站的部署方案的优化目标，或者以部署方案的成本最小化为假设前提，确定确定iBeacon基站的部署方案的优化目标；

(4)生成的种群中每个个体由优化目标计算评价后，利用快速非支配排序算法进行排序，按次序使个体两两配对进行交叉变异，从而生成下一代种群；

(5)根据步骤(4)不断进行遗传进化，直至达到设定的迭代终止条件，最终获得的新一代种群即为最优集；步骤三：根据部署精度、成本等需求，从最优集中选择相应的iBeacon基站部署方案，将所有iBeacon设备的Minor号设置成唯一的编号，同时记录iBeacon设备所在网格的编号，即坐标数据，这些iBeacon设备的Minor号、坐标数据等属性存储在数据服务器中；

步骤四：用户携带装有iBeacon信号接收处理App的智能手机，进入待定位区域，智能手机通过App识别周围iBeacon基站发送的广播帧，基于广播帧中的信号强度进行排序，选取信号最强的4个iBeacon基站，根据经验模型将这4个iBeacon基站信号强度转换成待定位点与对应基站的距离d1,d2,d3,d4；

步骤五：待定位点坐标计算，可以分为两种方式：一是以智能手机将计算出的4个距离d1,d2,d3,d4，发送至服务器端，由服务器按照一定的计算方式进行计算，获得待定位点的坐标，然后发送至智能手机端，在App地图中显示；二是通过App打包下载服务器端有关iBeacon基站的属性数据，以及4个距离d1,d2,d3,d4，用于计算待定位点坐标，直接通过App在手机端计算，计算方式与服务器上的计算方式相同，然后在App地图中显示。

2.如权利要求1所述的基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法，其特征在于：所述步骤二的具体过程如下：

以待测点与iBeacon基站的平均距离越短，收到的信号越强，从而获得待测点位置的精度越高为假设前提，确定iBeacon基站的部署方案的一个优化目标，待测点与基站平均最短距离的计算方式如下：

其中，Fxd是整个区域中所有待测点与基站平均距离，n是这个区域的待测点个数，Fd是区域中某个待测点与基站平均距离，m是待测点周围一定范围内的iBeacon基站个数，m大于或等于4，d是待测点与其周围某个基站之间的距离，(x′，y′)为某基站的坐标，(x，y)为待测点坐标；

另一个优化目标为部署方案的成本最小化，其计算方式如下：

min(Fcost)＝min(k×a)(4)

其中，k表示部署方案中的iBeacon基站个数，a表示部署单个iBeacon基站的成本。

3.如权利要求1所述的基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法，其特征在于：所述步骤四中，计算iBeacon基站信号强度转换成待定位点与对应基站的距离d1,d2,d3,d4，其计算方式如下：

d＝10[|RSSI|-A)/(10×N](5)

其中,d是计算所得距离，RSSI是接收信号强度，A是发射端和接收端相隔1米时的信号强度，N是环境衰减因子。

4.如权利要求1所述的基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法，其特征在于：所述步骤五中的待测点定位计算方式，具体过程如下：

(1)按照改进的加权质心定位算法，对4个iBeacon基站，任选3个进行组合，共有组，即每次取3个基站进行定位计算，计算公式如下：

其中，(x，y)是待测点坐标，(x1，y1)，(x2，y2)，(x3，y3)是3个基站的坐标，d1,d2,d3分别是待测点到3个基站的距离；

(2)根据步骤(1)得到4组待测点坐标，假设分别是(x1,y1)、(x2,y2)、(x3,y3)、(x4,y4),通过加权平均，都到最后待测点的坐标(x,y)，计算公式如下：

说明书

技术领域

本发明涉及一种基于多目标遗传算法NSGA-II算法对iBeacon基站进行空间布局优化技术，并且利用iBeacon基站和智能手机实现的室内定位方法，是一种通过在室内利用优化算法优化部署位置信息已知的iBeacon设备以及利用智能手机实现室内定位的方法。

背景技术

在城市中生活的人们，不可避免地光顾各种商场、机场、医院、停车场等陌生的公共场所，而这些公共场所的室内环境复杂而且陌生，因此，人们对于室内精确导航定位服务的需求日益强烈。例如，当用户在购物中心购物时需要寻找某个商铺、或者在火车站低下停车场寻找停车位或反向寻车、或者在机场需要寻找走失的同伴时，都需要室内定位技术的支持。

目前，已经提出的室内定位技术包括红外定位技术、超声波定位技术、蓝牙定位技术、W1-Fi定位技术、zigbee定位技术、磁场定位技术、计算机视觉定位技术等。这些室内定位技术由于定位精度低、成本高、定位速度慢、商业运营困难等各种原因，没有得到大规模的推广应用。蓝牙(Bluetooth)是一种短距离无线通信技术，可实现固定设备、移动设备之间的短距离数据交换。蓝牙4.0是2012年采用了蓝牙低功耗技术(BLE)的最新蓝牙版本，传输距离最远可达100米，且智能手机基本都内置了蓝牙4.0模块，其应用前景非常广阔。

iBeacon是苹果推出一项基于蓝牙4.0的精准微定位技术，其工作原理是：iBeacon基站不断向四周发送蓝牙信号，待满足iBeacon技术标准的蓝牙模块的智能设备进入设定区域时，就能够收到信号，通过三点定位算法、信号强度指示(RSSI)等方式可计算出用户位置。由于iBeacon设备发送的是2.4GHz频段的射频信号，该信号传播受环境如遮挡物干扰大，且不稳定，因此，基于该原理的测距精度难以保证，需要在室内有多个(大于3个)iBeacon基站，通过算法互相验证纠正，并且这些iBeacon基站的空间布局要合理，才能达到比较好的室内定位效果，同时保证成本的低廉。综上所述，基于iBeacon的室内地位技术当前面临如何优化iBeacon基站空间布局，以保证定位精度和部署成本。

发明内容

鉴于现有技术存在的上述技术问题，本发明提出了一种基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法。本发明通过NSGA-II算法优化部署iBeacon基站的空间布局，以及利用智能手机即可实现室内定位，具有定位精度高、成本低、实施简单、可推广性强的优点，并且可通过改变设备部署密度，在最低的部署成本下满足不同的定位精度需求。其具体技术方案如下：

一种基于NSGA-II算法的iBeacon基站空间布局优化及室内定位方法，该方法具体包括以下步骤：

步骤一：将室内待部署iBeacon基站的区域，按1米×1米划分成网格，每个网格按行列编上编号(i,j)，区域平面图最左上角的网格编号为(0,0)，其余的依次累加“1”，每个网格内都有可能部署一个iBeacon基站。

步骤二：将整个区域的网格利用二进制编码，转换成NSGA-II算法的基因序列，序列中“1”代表部署iBeacon基站，“0”代表没有部署。随机初始化iBeacon基站的部署方案，以待测点与基站平均最短距离和部署成本为优化目标进行优化，最终生成iBeacon基站的部署方案最优集。

步骤三：根据部署精度、成本等需求，从最优集中选择相应的iBeacon基站部署方案，将所有iBeacon设备的Minor号设置成唯一的编号，同时记录iBeacon设备所在网格的编号，即坐标数据，这些iBeacon设备的Minor号、坐标数据等属性存储在数据服务器中。

步骤四：用户携带装有iBeacon信号接收处理App的智能手机，进入待定位区域，智能手机通过App识别周围iBeacon基站发送的广播帧，基于广播帧中的信号强度进行排序，选取信号最强的4个iBeacon基站，根据经验模型将这4个iBeacon基站信号强度转换成待定位点与对应基站的距离d1,d2,d3,d4。

步骤五：待定位点坐标计算，可以分为两种方式。一是以智能手机将计算出的4个距离d1,d2,d3,d4，发送至服务器端，由服务器按照一定的计算方式进行计算，获得待定位点的坐标，然后发送至智能手机端，在App地图中显示。二是通过App打包下载服务器端有关iBeacon基站的属性数据，以及4个距离d1,d2,d3,d4，用于计算待定位点坐标，直接通过App在手机端计算，计算方式与服务器上的计算方式相同，然后在App地图中显示。

所述步骤二的具体过程如下：

(1)将室内待部署iBeacon基站1米×1米网格区域，视为二维数组，将其按行转化为一维数组，作为遗传算法二进制编码的基因序列，同时记录每个基因在二维数组中的行列编号(i，j)。

(2)以随机法进行种群初始化，即基因序列中随机函数生成“0”、“1”，“1”代表部署iBeacon基站，“0”代表没有部署。

(3)以“待测点与iBeacon基站的平均距离越短，收到的信号越强，从而获得待测点位置的精度越高”为假设前提，确定iBeacon基站的部署方案的一个优化目标，待测点与基站平均最短距离的计算方式如下：

其中，Fxd是整个区域中所有待测点与基站平均距离，n是这个区域的待测点个数，Fxd是区域中某个待测点与基站平均距离，m是待测点周围一定范围内(如5米)的iBeacon基站个数，m应大于或等于4，d是待测点与其周围某个基站之间的距离。

另一个优化目标为部署方案的成本最小化，其计算方式如下：

min(Fcost)＝min(k×a)(4)

其中，k表示部署方案中的iBeacon基站个数，a表示部署单个iBeacon基站的成本。

(4)生成的种群中每个个体由优化目标计算评价后，利用快速非支配排序算法进行排序，按次序使个体两两配对进行交叉变异，从而生成下一代种群。

(5)根据步骤(4)不断进行遗传进化，直至达到设定的迭代终止条件，最终获得的新一代种群即为精英集。

所述步骤四中，计算iBeacon基站信号强度转换成待定位点与对应基站的距离d1,d2,d3,d4，其计算方式如下：

d＝10[(|RSSI|-A)/(10×N)](5)

其中,d是计算所得距离，RSSI是接收信号强度(负值)，A是发射端和接收端相隔1米时的信号强度，N是环境衰减因子。由于所处环境不同，每台发射源(蓝牙设备)对应参数值都不一样，因此，公式里的每项参数都应该做实验(校准)获得。

所述步骤五中的待测点定位计算方式，具体过程如下：

(1)按照改进的加权质心定位算法，对4个iBeacon基站，任选3个进行组合，共有 组，即每次取3个基站进行定位计算，计算公式如下：

其中，(x，y)是待测点坐标，(x1，y1)，(x2，y2)，(x3，y3)是3个基站的坐标，d1,d2,d3分别是待测点到3个基站的距离。

(2)根据(1)得到4组待测点坐标，假设分别是(x1,y1)、(x2,y2)、(x3,y3)、(x4,y4),通过加权平均，都到最后待测点的坐标(x,y)，计算公式如下：

本发明的有益效果：

1、本发明针对iBeacon发送射频信号受环境如遮挡物干扰大，且不稳定的缺点，采用遗传优化算法，设计空间布局优化的iBeacon基站部署方案，最大限度的弥补信号不稳定导致的定位精度下降。

2、本发明采用的多目标遗传算法，在优化iBeacon基站空间布局的同时，能够最小化部署成本。

3、本发明实现的室内定位计算方法，采用4个基站数据计算待测点，比传统的3个基站计算具有更加稳定、更加精准的优势，且计算可以在服务器端和智能手机端两种方式实现，根据不同的环境，选择合适的方式，例如手机信号不好时，选择在手机端计算和定位。

4.本发明的应用广泛，例如可用于行人定位、车辆定位等，而且具有成本低廉、部署简单、维护成本低下、可推广性强的优点。

附图说明

图1为本发明中基于NSGA-II算法的iBeacon基站空间布局优化示意图。

图2为本发明中待部署iBeacon基站的室内平面网格图。

图3为本发明中改进的加权质心定位方法原理图。

图4为本发明中数据库中数据表结构示意图。

图5为本发明中利用iBeacon基站和智能手机实现室内定位的示意图。

具体实施方式

为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。

本发明涉及一种基于多目标遗传算法NSGA-II算法对iBeacon基站进行空间布局优化技术，并且利用iBeacon基站和智能手机实现的室内定位方法。因此，本发明主要包括两部分：一是iBeacon基站空间布局优化技术；二是利用空间布局优化的iBeacon基站实现室内定位的技术，以提高定位的精度和降低iBeacon基站部署的成本。

iBeacon基站空间布局优化技术基于多目标遗传算法NSGA-II算法，以待测点与基站平均最短距离和部署成本为优化目标进行优化，最终生成iBeacon基站的部署方案最优集，方法的流程图见图1。

(一)以室内停车场车辆实时定位为例，iBeacon基站空间布局优化分为以下步骤：

(1)待部署区域网格划分。将停车场平面图待部署iBeacon基站的区域标识出来，按1米×1米划分成网格，每个网格按行列编上编号(i,j)，即坐标，以及一个唯一标识ID号，从1开始到n，n是区域划分的网格数。

(2)iBeacon基站部署优化。将这些网格的坐标数据与唯一标识ID号保存到数据库表中，遗传算法以ID号构建基因序列，初始化种群，种群规模为200。然后以待测点与基站平均最短距离和部署成本为优化目标进行优化，在本例中部署成本计算的公式(3)中，部署单个基站的成本定为30元。循环迭代n次，如1000次，算法终止，从而获得最优方案集。

(3)iBeacon基站的部署。从最优方案集中，如根据项目实施的实际可用成本，选择相应成本下的最优方案，进行部署。部署高度一般可将设备部署在室内天花板上，这样可以减少遮挡物对信号的干扰。如果天花板高度超过了5m，为了保证蓝牙信号传输质量，可以考虑将设备部署在立柱上，高度以3m左右为宜。

(二)利用空间布局优化的iBeacon基站和智能手机，实现停车场室内定位技术分为以下步骤：

(1)建立ibeacon基站数据库。如图4所示，在离线建立数据库时，需要将设备的真实坐标通过Minor号与iBeacon设备一一对应存入数据库中的一张表中，Minor号的设置可以使用官方的APP设置。同时iBeacon设备发送的广播帧中的Major信息可以用来区分设备所在不同区域。例如，在进行多层建筑中的定位功能实现时，可以使用Major号来对设备进行分组，不同楼层中的设备属于不同的分组，系统根据Major号判定用户所在楼层。

(2)信号获取和距离计算。装有本发明相应App的智能手机进入待定位区域，获取信号强调最强4个基站信息(包括设备的Major、Minor号等)，计算iBeacon基站信号强度按照公式(5)转换成待定位点与对应基站的距离d1,d2,d3,d4，公式(5)中，A是发射端和接收端相隔1米时的信号强度，经实测约57，N是环境衰减因子，本例中取值为2。这个计算过程在手机端App中实现。

(3)待定位点坐标的计算。如图5所示，分两种方式：一是服务器端实现(在线方式)，二是手机端App实现(离线方式)。服务器端实现过程如下：手机端将4个基站信息(设备的Major、Minor号等)，以及待定位点与对应基站的距离d1,d2,d3,d4，发送到服务器端，服务器在数据表中查找设备的Major号(所在楼层)、Minor号(设备编号)，找到相应基站的网格坐标，按照公式(6)、公式(7)、公式(8)、公式(9)进行计算，将计算结果反馈给手机端，在App地图中显示待测点坐标。手机端App实现过程如下：首先在App安装时，下载停车场室内iBeacon基站属性数据表，包括所有网格坐标和ID号；手机端将4个基站信息(设备的Major、Minor号等)，以及待定位点与对应基站的距离d1,d2,d3,d4，App在数据表中查找设备的Major号(所在楼层)、Minor号(设备编号)，找到相应基站的网格坐标，按照公式(6)、公式(7)、公式(8)、公式(9)进行计算，计算结果在App地图中显示待测点坐标。

一种iBeacon基站空间布局优化及室内定位方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。