随着定位技术的快速发展，人们开始将目光转向室内定位，室内环境下的位置服务可以应用于定位长者照看、超市导航、物联网等场景中，同时在某些特殊场景(火场救援等紧急突发事件)中，室内定位也发挥着极其重要的作用^[1-2]，为了提高室内定位精度，合理的网元布局尤为重要.

当前室内定位技术有很多种，虽然基于蓝牙、WiFi^[3]、UWB^[4]、红外等定位技术容易达到很好的定位效果，但是在复杂建筑环境下大规模部署的成本难以接受.在即将到来的5G时代，异构蜂窝网的通信导航网络一体化被业界认为是室内定位的重要发展趋势^[5].由于室内建筑环境的非视距特性，用户可能接收不到足够多的网元定位信号，导致定位误差增大，甚至不能为用户提供定位需求.针对以上情况，笔者提出一种考虑微网元的布局优化方法，进而提高室内定位信号覆盖率和定位精度.

1 相关工作

目前，网元布局被视为一个优化问题.现有的网元布局优化算法是在满足通信网络建设的前提下，将信号覆盖范围、通信质量和成本等因素组合在一起进行优化，得到最优布局，但是室内复杂的场景可能导致目标区域存在定位信号覆盖漏洞.覆盖漏洞是指定位所需要的4个网元不能同时覆盖待定位区域.为满足定位需求，可以在智能优化算法对宏网元布局的基础上增补微网元^[6].

在室外网元布局方面，Agapie等^[7]利用遗传算法来解决无线网络的规划问题，但是遗传算法并没有可行的反馈机制，在某些情况下会产生大量的冗余迭代，造成效率低等问题. Han等^[8]利用蚁群算法对网元进行布局，主要将网元部署的成本和覆盖作为布局目标，但是在蚁群算法搜索的初期阶段，存在很少甚至没有可用信息的情况，因此蚁群算法收敛速度缓慢^[8-10].

微网元布局目前大都应用在无线传感器网络中. Jain等^[11]提出了一种在室内环境下摆放微网元的方法，最大化用户服务质量，并同时考虑一定的能效因素. Bais等^[12]提出了一种新的毫微微蜂窝接入点规划策略，其优化目标是最大化信号覆盖，提高了网络连接质量. Lin等^[13]利用正交设计方法减少基站配置参数组合的数量，扩大了信号的覆盖范围，但是没有考虑非视距环境对信号的影响以及在室内定位中的应用.朱思峰等^[14-15]提出了一种基于免疫算法的微网元布局算法，在传统网络下引入微网元形成异构网络. Chen等^[16]研究了微网元的几种几何布局方式，并提出了一种正方形的微网元布局方法，且证明了正方形布局的性能，但是正方形布局一定程度会造成资源浪费^[17].当前的微网元布局主要应用于无线传感器网络和异构网络中的中继网元，无线传感器网络中微网元布局没有考虑室内复杂场景.

通过以上研究和分析，在基于融合算法对室外宏网元布局的基础上，笔者提出了一种基于菱形布局的微网元增补算法，从而进一步提高目标区域的定位效果.

2 具有微网元增补的网元布局模型

在面向室内定位的网元布局模型中，首先对室外宏网元进行布局，使定位信号对室内环境产生一定的覆盖；其次在室内空间中增补微网元，从而进一步提高室内定位精度.室内定位网络下微网元增补场景如图 1所示.

2.1 问题的描述

网元布局优化是在一定的区域内，合理地摆放N个网元，使得室内环境的整体定位精度达到最优，并考虑到室内定位的覆盖问题.因此，网元布局需要满足以下3个原则.

1) N个网元要摆放在指定的区域内；

2) N个网元要保证室内环境达到一定的覆盖率；

3) 使得室内环境的整体定位精度达到最优.

2.2 网元部署

在网元布局过程中，用s_i(x_i, y_i, z_i)表示第i(i=1, 2, …, N)个网元的坐标.在室内环境采集M个节点表示用户，第m个用户的坐标为p_m(a_m, b_m, c_m)，第m个用户的测量坐标为${\hat p_m}\left({{{\hat a}_m}, {{\hat b}_m}, {{\hat c}_m}} \right)$，并且假设每个定位节点的请求定位概率相同.定义S、P和$\hat P$为(s₁, s₂, …, s_N)、(p₁, p₂, …, p_M)和(${{\hat p}_1}, {{\hat p}_2}, \cdots, {{\hat p}_M}$). S表示N个网元的布局方案，P表示室内环境下M个用户的所有点的位置，${\hat P}$表示室内环境下M个用户的所有点的测量位置.所描述的目标函数为

$ {\rm{Erro}}\left( S \right) = {\rm{min}}f\left( S \right), S \notin D $

(1)

式(1)描述了网元布局优化的原则3)，f(S)表示定位的平均误差，D表示网元布局在非法区域，如街道、地下管道等空间.在室内定位中至少需要同时接收到4个网元的信号才能够定位，因此，当用户接收到网元信号的个数大于等于4时才认为得到了有效的覆盖.网元布局满足一定信号覆盖的条件下，最大化定位精度，即满足网元布局优化的原则1)和原则2).

在网元布局S的情况下，在室内环境下M个用户的平均定位误差为

$ f\left( S \right) = \frac{1}{M}\sum\limits_{m = 1}^M {{\rm{Err}}{{\rm{o}}_m}\left( S \right)} $

(2)

其中Erro_m(S)表示第m个用户的定位误差，即

$ {\rm{Err}}{{\rm{o}}_m}(S) = \sqrt {{{({a_m}-{{\hat a}_m})}^2} + {{({b_m}-{{\hat b}_m})}^2} + {{({c_m}-{{\hat c}_m})}^2}} $

(3)

在网元布局问题中采用基于测距的三维到达时间和到达时间差定位算法，通过测量网元与用户之间的距离进行定位.在理想条件下，即测距误差为0时，通过测量得到用户p_m与第i个网元s_i之间的距离为R_i，即

$ {R_i} = \sqrt {{{({x_i}{\rm{-}}{a_m})}^2} + {{({y_i}{\rm{-}}{b_m})}^2} + {{({z_i}{\rm{-}}{c_m})}^2}\;} $

(4)

那么，以4个网元为圆心，R_i为半径，则4个球体的交点即为用户p_m的位置.对于式(4)，当i=1, 2, 3, 4时可获得用户的位置p_m(a_m, b_m, c_m).实际测量信号从用户到网元之间一定存在误差，用户到第i个网元之间的测量距离为${{\hat R}_i}$，最终计算获得的用户的测算位置${{\hat P}_m}$为$\left({{{\hat a}_m}, {{\hat b}_m}, {{\hat c}_m}} \right)$，则

$ {{\hat R}_i} = \sqrt {{{({x_i}-{{\hat a}_m})}^2} + {{({y_i}{\rm{-}}{{\hat b}_m})}^2} + {{({z_i}{\rm{-}}{{\hat c}_m})}^2}} $

(5)

当i=1, 2, 3, 4时可获得用户的测算位置${{\hat p}_m}\left({{{\hat a}_m}, {{\hat b}_m}, {{\hat c}_m}} \right)$从而计算定位精度，进而对网元布局的好坏进行评价，通过调整布局方案最终获得相对最优的宏网元布局结果.

2.3 微网元的布局

根据以上布局结果，在室内空间中增补微网元.在面向室内定位的微网元增补过程中，用s'_t(x'_t, y'_t, z'_t)表示第t个微网元的坐标，共有N'个微网元进行布局.室内布局微网元增补模型中采集的用户节点与2.2节相同.令S'为(s'₁, s'₂, …, s'_N')，S'表示N'个微网元的布局方案.

微网元增补的目标是提高目标区域的平均定位精度，其目标函数为

$ {\rm{Erro}}\left( {S'} \right) = \mathop {{\rm{min}}}\limits_{S'} f\left( {S'} \right) $

(6)

其中：f(S')函数是求解在当前网元布局下目标区域的平均定位误差，S'是微网元布局，其布局的区域首先被宏网元覆盖，每一个采集的用户节点均受到一定程度的定位信号覆盖.用户位置测算公式与式(5)同.

获得宏网元布局结果S"，其中包括N个网元，设定第i个网元s"_i的坐标为(x"_i, y"_i, z"_i).目标区域中采集M个用户节点，第m用户节点(a_m, b_m, c_m)受到N₁个宏网元覆盖.根据目标区域定位情况，摆放N'个微网元.第m个节点定位获得的测量位置坐标为(a'_m, b'_m, c'_m)，其定位误差Erro'_m(S", S')的定义为

$ \begin{array}{l} \;\;\;\;\;{\rm{Erro}}{'_m}\left( {S", S'} \right) = \\ \sqrt {{{({a_m}{\rm{-}}a{'_m})}^2} + {{({b_m}{\rm{-}}b{'_m})}^2} + {{({c_m}{\rm{-}}c{'_m})}^2}\;} \end{array} $

(7)

对于每个用户节点的定位过程中，基于测距的定位算法需要4个网元信号，因此需要在宏网元和微网元中至少选取4个网元，其中宏网元覆盖中选择N′₁个，微网元覆盖中选择N′₂个，N′₁+N′₂≥4.

3 算法设计

主流网元优化算法均存在一些问题，每种智能优化算法之间的融合能够互补各算法短处^[18].

首先使用遗传算法与蚁群算法融合的网元布局算法(以下称融合算法)对室外宏网元优化布局，然后根据对宏网元的信号覆盖的目标区域进行微网元增补，进而提高室内定位精度.融合算法分为遗传算法与蚁群算法两部分，并对遗传算法部分参数做了改进.

3.1 融合算法中参数改进 3.1.1 遗传算法参数改进

1) 交叉算子

传统的交叉概率是常数，基于自适应遗传算法的思想，对遗传算法中交叉概率进行了改进，随着算法的迭代，交叉概率也随之变化，能够为遗传算法的后期提供一定的反馈信息.遗传算法的交叉概率计算公式为

$ {P_{\rm{c}}} = \left\{ \begin{array}{l} {P_{{c_0}}}{\rm{, }}\;\;\;\;\omega \le \bar \omega \\ {\rm{ }}{P_{{{\rm{c}}_1}}}{\left( {\frac{{{P_{{{\rm{c}}_0}}}}}{{{P_{{{\rm{c}}_1}}}}}} \right)^I}{\rm{, }}\;\;\omega > \bar \omega \end{array} \right.{\rm{ }} $

(8)

其中

$ I = {\left( {\frac{{({\omega _{{\rm{max}}}}{\rm{-}}\omega )}}{{({\omega _{{\rm{max}}}}{\rm{-}}\bar \omega )}}} \right)^M} $

(9)

P_c0为较大的交叉概率；P_c1为较小的交叉概率；ω为当前个体的适应度；ω_max为最大适应度；ω为种群中的平均适应度，ω≤ω_max；M用来调节交叉概率反馈的大小，本算法M取值为1，在实验过程中可以根据情况进行调节.

2) 变异算子

采用均匀变异的方式对遗传算法的变异概率进行了更改，使其随着算法的迭代而改变，为遗传算法提供反馈信息.遗传算法的变异概率计算公式为

$ {P_{\rm{m}}} = \left\{ \begin{array}{l} {P_{{{\rm{m}}_0}}}, \;\;\;\omega \le \bar \omega \\ {P_{{{\rm{m}}_1}}}{\left( {\frac{{{P_{{{\rm{m}}_0}}}}}{{{P_{{{\rm{m}}_1}}}}}} \right)^I}{\rm{, }}\;\;\;\;\omega > \bar \omega \end{array} \right. $

(10)

其中

$ I = {\left( {\frac{{({\omega _{{\rm{max}}}}{\rm{-}}\omega )}}{{({\omega _{{\rm{max}}}}{\rm{-}}\bar \omega )}}} \right)^M}\; $

(11)

P_m0为较大的变异概率；P_m1为较小的变异概率；M用来调节变异概率反馈的大小，本算法对于M取值为1.

3.1.2 蚁群算法参数改进

信息素常量Q影响着蚁群算法的表现，传统蚁群算法的更新适应度强度的信息量Q是一个常量，为了减少蚁群算法陷入局部最优解的风险，将Q改为一个自适应的变量.基于此，将蚁群的更新过程描述为

$ {\tau _{ij}}\left( {t + n} \right) = \left( {1{\rm{-}}\rho } \right){\tau _{ij}}\left( t \right) + \rho \Delta {\tau _{ij}}\left( t \right)\; $

(12)

$ \Delta {\tau _{ij}}\left( t \right) = \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k\left( t \right)} $

(13)

$ \tau _{ij}^k\left( t \right) = \left\{ \begin{array}{l} Q{F_k}{\rm{, }}\;\;\;\left( {i, j} \right) \in {T^k}\\ 0{\rm{, }}\;\;\;{\rm{其他}} \end{array} \right.\; $

(14)

$ Q = {Q_0}\left( {1{\rm{-}}\frac{{{\omega _Q}{N_t}}}{{{N_{{\rm{max}}}}}}} \right) $

(15)

其中：ρ为路径上的蒸发系数，ρ∈[0, 1]；Δτ_ij为搜索过程中网元i与网元j之间路径上的信息素增量；Δτ_ij^k为第k只蚂蚁在网元i与网元j之间路径上留下的信息素量；F_k为第k只蚂蚁本次寻觅的适应度；T^k为第k只蚂蚁从一个网元到另一个网元运动的路径；Q₀是初始值；ω_Q为当前代自适应权值；N_t为当前的迭代数量；N_max为蚁群算法最大迭代次数.

图 2为基于融合算法的网元布局方法流程图.

3.2 基于菱形布局的微网元增补算法的设计 3.2.1 目标区域几何划分

当每个微网元能够覆盖目标区域时，不进行区域划分，而且此时最多只需要布局4个网元便能够满足基本的定位需求.但是当目标区域较大时，每个微网元不能覆盖整个目标区域，需要对目标区域进行几何划分.

微网元布局的几何策略中正方形是比较理想的几何布局策略^[16-17]，它能确保采集的用户节点得到有效的覆盖，同时保证任意3个网元不共线^[16].但是室内建筑物的形状不一，将每个目标区域划分为正方形比较困难^[17].首先将整个目标区域划分为多个矩形，如图 3所示.矩形表示整个目标区域所划分的子区域，十字表示每个子区域中采集的用户节点，圆点表示微网元；然后每个微网元部署在矩形4个边的中点，将中点连线构成一个菱形.为方便起见，将每个区域的4个位置从左到右分别标识为1号、2号、3号和4号位置.

目标区域划分首先要获取到目标区域的长L′、宽W′和高H′，对于非规则图形的目标区域需要转化为矩形，然后根据微网元的覆盖半径R′进行区域划分.因此，每个区域长和宽的最大值R′_max＝$2\sqrt {R{'^2} -H{'^2}} $，因为微网元的覆盖半径R′相当于直角三角形的斜线，目标区域的高H′相当于直角三角形的直角边.将目标区域划分为M′N′(M′=ceil$\left({\frac{{L'}}{{R{'_{\max }}}}} \right)$，N′=ceil$\left({\frac{{W'}}{{R{'_{\max }}}}} \right)$，ceil函数表示向上取整)个区域，如图 4所示.

3.2.2 微网元增补算法

室外网元部署后由于各种原因会导致覆盖漏洞，增补微网元旨在提高信号覆盖率.

面向室内定位的覆盖大致可以分为3种类型：点覆盖、栅栏的覆盖和区域的覆盖方式.相比后2种覆盖，点覆盖具有操纵灵活、计算量小等特点，因此采用点覆盖的覆盖方式.在室内定位环境下，基于测距的定位算法定位一个节点至少需要4个网元，因此当一个用户节点接收到至少4个网元的信号时，便认为该用户节点获得了有效的定位信号覆盖.基于以上分析，提出了一种微网元布局优化方法.

1) 在微网元布局之前，室外网元已经对室内环境有一定的信号覆盖.首先要对目标区域进行覆盖分析，计算每个用户节点接收室外网元信号的情况，绘制定位信号覆盖图，如图 5所示.黑色的节点表示已经接收到有效覆盖的用户节点，即用户节点的定位精度达到期望标准；白色的节点表示没有接收到有效覆盖的用户节点.

2) 对微网元产生的定位信号进行预处理，用一个微网元遍历所有目标区域，并对每一次遍历所产生的定位信号信息进行存储.

3) 目标区域的划分，首先需要确定目标区域的大小以及微网元的覆盖半径，然后通过计算将目标区域划分为M′×N′个区域.

4) 将所有区域按照从左到右，从上到下的顺序编号，并设置迭代器H=0.

5) 对第H个区域计算评分Score.首先统计第H个区域的定位信号数据，接收到至少0个信号的节点个数为L₀，接收到至少1个信号的节点个数为L₁，接收到至少2个信号的节点个数为L₂.同上定义L₃、L₄，节点总数为L.如果网元布局的覆盖率要求至少为C，评分Score根据当前分区定位数据情况计算.当$\frac{{{L_4}}}{L} \ge C$时Score设定为4，当$\frac{{{L_3}}}{L} \ge C$时Score设定为3，以此类推设置Score.

6) 在目标区域执行算法1.

算法1   AddMicroNetEle

when Score > = 4

No need to increase micro network element

when Score = = 3

Select one of four locations to meet the coverage requirements to supplement the micro network element when Score = = 2

Add 2 micro network element

when Score = = 1

Add 3 micro network element

finally

Micro network elements are added at four locations respectively

7) 在第H区域摆放微网元后，某些节点接收到的定位信号个数可能增多，需要对其覆盖区域内的节点接收到信号个数进行修改.

8) 更新迭代器，H=H+1.

9) 判断是否满足结束条件，如果H大于区间个数M′×N′，则结束迭代，保存微网元布局信息；反之，则继续步骤5).

4 仿真实验 4.1 仿真场景设置

初始仿真场景如图 6所示，网元数量为12个，分两层摆放，每一层按正六边形排布，同一六边形相邻网元之间的距离为200 m.室内仿真场景为两层建筑，如图 6所示，建筑物的长度为116 m，宽度为58 m，高度为6.3 m，墙体厚度为0.3 m，地板与天花板的厚度为0.3 m，楼梯宽度为2 m.每层设置3个房间，供人行走平台宽为2.5 m.在场景中布设12个网元，分别对应场景中的节点A(150, 76.7, 3)、B(50, 250, 3)、C(150, 198.2, 3)、D(350, 198.2, 3)、E(450, 250, 3)、F(350, 76.7, 3)、G(150, 76.7, 6)、H(50, 250, 6)、I(150, 198.2, 6)、J(350, 198.2, 6)、K(450, 250, 6)、L(350, 76.7, 6).其x轴的范围是192~308 m，y轴的范围是221~279 m，z轴的范围是0~6 m.对目标区域共采集2万个用户节点，其中建筑物的第1层采集1万个节点，建筑物的第2层采集1万个节点，以下实验参数相同.

在国家重大专项项目“面向亚米级位置服务的5G异构网络融合技术”的支持下，联合ZTE开发高精度地面无线定位仿真系统，将网元优化结果输入此仿真系统，即可分析定位误差统计结果.

4.2 仿真实验目的

实验1  验证融合算法的性能以及基于菱形的微网元增补的有效性.对3种方法的网元布局结果进行分析，对比在目标区域进行微网元增补前后的各项指标.

实验2  验证微网元增补算法的性能.将所提出的微网元增补算法与朱思峰等^[15]提出的基于免疫算法的微网元增补算法进行对比.

4.3 仿真内容与分析

实验1   验证融合算法的性能以及基于菱形的微网元增补的有效性.

1) 验证融合算法的性能

根据4.1节所设置的仿真场景，实验测量的目标区域如图 6所示.比较基于遗传算法、蚁群算法与融合算法的网元布局优化算法后目标区域的定位情况，3种算法的参数设置如表 1所示.定位误差的统计结果如图 7所示.

由图 7中数据可以看出，在0~1 m、1~2 m以及2~3 m的定位误差区间上基于融合算法的网元布局算法布局后定位误差占比相对较大，在3~4 m和4~5 m的定位误差区间相比其他2种算法的定位误差占比较小.

表 2所示为3种网元布局算法布局后目标区域的定位情况.在平均定位精度方面，融合算法相对蚁群算法和遗传算法进行网元布局效果要好，平均定位误差更小.在对目标区域的覆盖率方面，融合算法相比蚁群算法提升了3.2%，相比遗传算法提升了6.9%.

2) 验证基于菱形的微网元增补的有效性

基于室外网元布局的结果，使用基于菱形布局的微网元增补算法，对目标区域进行微网元增补.通过比较使用微网元增补算法前后目标区域的定位情况，得到定位误差的统计结果如图 8所示.

由图 8中的数据可以看出，微网元布局前的定位误差主要集中在2~4 m这个区间中，其中2~3 m的定位误差占比较大.通过使用微网元增补算法对网元进行布局后，定位误差主要集中在0~2 m这个区间中，相比微网元布局前0~2 m区间的定位误差，占比增加了38.64%，而2~5 m区间的定位误差占比明显减少.

表 3展示了微网元布局前后目标区域的定位情况，通过对室内微网元进行布局，目标区域的平均定位误差有所下降而覆盖率有所提升.其中，定位误差从2.534 m下降到1.86 m，下降了26.5%；目标区域覆盖率从81.3%提升到94.2%，提升了12.9%.

由图 9可以看出，微网元布局前目标区域的平均定位误差可以控制在4.4 m以内，而微网元布局后目标区域的平均误差可以控制在3.6 m以内.而且，保证了小于2 m的定位误差80%以上，小于1 m的定位误差30%以上.从而说明基于微网元的布局优化算法提升目标区域定位效果的有效性.

实验2   验证微网元增补算法的性能.

根据4.1节所设置的仿真场景，在目标区域中布设9个微网元.通过比较使用基于菱形布局的微网元增补算法和朱思峰等^[15]提出的基于免疫算法的微网元布局算法后目标区域的定位情况，得到定位误差的统计结果如图 10所示.在0~2 m的平均定位误差范围内基于菱形布局的微网元增补算法占比较多，而在2~5 m的平均定位误差范围内基于免疫算法的微网元布局算法占比较多.

表 4展示了2种微网元布局后目标区域的定位情况.基于免疫算法的微网元增补算法相比实验1的结果平均定位误差下降了24.4%，覆盖率提高了9%.

由图 11可以看出，使用2种微网元布局算法后目标区域的平均定位误差可以控制在4 m以内，使用基于免疫算法的微网元布局算法后目标区域的平均定位误差3 m以内的占比达到了80%，2 m以内的达到了50%，1 m以内的达到了20%.而使用基于菱形布局的微网元增补算法后，目标区域平均定位误差在2.5 m以内的占90%左右，比基于免疫算法的微网元布局算法高10%以上.

4.4 部署代价分析

融合算法可以有效解决实际问题，但是运行过程中的时间开销比单一算法的时间开销要大.

微网元类似WiFi，接入点成本低、功耗低，使用免费频段，避免了频谱占用冲突，且覆盖范围小，可以有效降低对宏网元的干扰.

微网元的增补是以“以宏为主，以微为辅”的，在不减少宏网元的基础上，使用微网元来解决宏网元信号覆盖漏洞的问题，微网元的数目可控，由于微网元成本低，微网元增补的成本代价是可以接受的.

5 结束语

提出了一种基于菱形布局的微网元增补算法，在室外宏网元布局的基础上，将微网元与宏网元相结合作为宏网元的一种有力补充，通过菱形几何区域划分算法增补微网元，弥补目标区域信号覆盖漏洞.微网元具有成本低、功耗低、体积小等特点，使得在选址和工程部署上投资小.在相同的室内场景中，通过仿真实验，该算法与微网元布局前比较，定位误差缩小了26.5%，目标区域覆盖率提高了12.9%.在微网元布局方面，使用基于菱形布局的微网元增补算法后，目标区域的平均定位误差90%左右在2 m以内，比基于免疫算法的微网元布局算法高10%以上.