基于无线通信基站的室内三维定位问题
(研究生数学建模竞赛2016年C题)
1. 背景介绍
随着无线通信网络和移动互联网的蓬勃发展，提供基于地理位置信息的服务（Location Based Service，简称LBS）已经成为最具市场前景和发展潜力的业务之一。从传统的GPS导航，到大众点评、微信等基于地理位置的消费信息服务和社交软件，实现其功能的基础就是要通过手机、导航仪等终端设备收发信号，来获得距离、角度等测量信息，并利用定位算法将这些测量信息转换成坐标信息。
基于无线移动通信网络的定位是以获取用户手持终端（包括手机或者平板等设备）的位置为目标。而达成这一目标的手段是通过测量无线电信号的强度、传播时间、到达角等物理指标，并将其转化成终端与基站之间的距离、角度等信息，最终利用定位算法将距离、角度等信息转化成终端的坐标信息。
虽然商用GPS已经随着智能手机的发展而得到了广泛的应用，但是，在诸如室内、地下、高楼林立的市区等诸多场景中，GPS定位性能较差。由于在覆盖广度和深度上，基于无线网络基站的定位系统相比GPS存在优势，因此，越来越得到运营商和新兴创业公司的重视。
此外，对于大数据感兴趣的IT公司，通过统计大规模匿名用户的连续地理位置信息，可以获得用户的移动轨迹，以及在相应轨迹上的APP流量使用情况，甚至在特殊位置搜索和关注的关键词等信息。因此，诸如Google、百度等搜索引擎公司也开始提供室内定位和室内地图导航的服务。这类服务，一方面可以弥补传统的GPS在室内定位性能较差，且不能分辨用户所在楼层等问题，另一方面，也为商场、博物馆等应用场景提供了为用户提供基于室内实时地理位置信息服务的可能。
目前从事室内定位和导航服务的方法，大多基于室内密集分布的WiFi设备与手机之间的通信方式。这类方法存在两个明显的劣势：首先，从技术上，WiFi设备的覆盖范围有限，并且WiFi设备收发信号所在的频段容易受到干扰；其次，从业务模型上看，用户对于接入陌生WiFi设备的戒备心理，以及WiFi设备的投资如何回收等，都存在较大的商业模式上的不确定性。
与之相对的，使用基于运营商无线通信基站的方式对手机进行定位，则可以规避上述问题。商用基站的覆盖范围、信号质量均优于WiFi，而且，用户也期望自己的手持终端能够随时保持对基站设备的接入。同时，运营商推进定位服务的盈利模式清晰，在基础的数据服务之外，还可以通过为用户提供增值服务而促进运营商的业务发展。总之，基于无线通信基站的定位技术有着广阔的应用前景和巨大的商业价值。
手持终端设备如何基于基站的测量信息，计算或确定终端在三维空间中的位置坐标，也就是三维定位问题，被认为是现代商用通信网络中对于定位系统真正具有技术难度的挑战。而高精度三维定位也预期能为客户提供更大的价值，在智能仓储、智能工厂、固定资产追踪等对于三维坐标信息敏感的垂直行业，以及传统运营商感兴趣的商场、办公楼中基于位置信息的室内导航、人群流量分析，以及基于精确三维地理位置信息的业务推送等服务提供基础性技术。
从技术角度来看，现代商用通信网络对于三维定位的需求，是使用尽可能少的基站完成对终端设备的定位、算法收敛速度快、对于干扰和噪声具有鲁棒性等优点。
相比于GPS等商用卫星定位系统，基于通信基站的定位问题，具有如下特殊性：
首先，通信基站的目标区域是GPS等卫星定位系统无法实现定位的场景。在高楼林立的城区，建筑物内部、地下停车场等区域，GPS等系统是无法满足定位需求的。而这些应用场景基站、终端密集，是基站定位可以实现突破的地方。
其次，通信基站所处的电磁信号环境较之GPS等系统更加复杂。以室内环境为例，无线电信号的传播过程中会经过墙面的多次反射、室内物体的折射和吸收等。这些物理因素会导致通信基站测量得到的诸如距离、角度等信息存在噪声。如何基于这些有噪声的测量，得到对于位置信息的准确估计，也是通信基站实现对终端定位需要解决的问题。
基于通信基站的定位问题研究，在科研和工业界都吸引了极高的关注。一方面，定位问题与统计信号处理、最优估计理论、优化算法等诸多领域都有密切的联系，诸如数据拟合、最小二乘估计、半正定规划、流形学习等诸多数学工具都能够被用于求解上述问题。另一方面，工业界对于如何高精度地在现有通信设备上完成上述功能也表现出了浓厚的兴趣，我国除了业已广泛部署商用的北斗导航系统之外，也在积极推进基于室内室外融合定位的羲和导航系统。我们相信，基于通信基站的定位系统，将会成为羲和导航系统有力的技术手段。
求解分析基站定位相关问题的有创新性和可实现性强的算法，都将有可能被快速部署到现代商业通信网络中，带来巨大的社会和经济效益。
2. 基础知识
2.1 无线电信号的视距（LOS）与非视距（NLOS）传播
无线电信号在大气中从A点向B点传播时，如果传播过程中存在一个没有遮挡的直达路径，那么，这种传播环境被称为视距传播环境（Line Of Sight propagation，简称LOS）。这种传播环境如图 1中的左图所示。如果在传播过程中，由于建筑物或树木的遮挡、反射、折射等物理现象，使得从A点到B点之间存在多条无线电信号的传播路径，这种环境被称为非视距传播环境（Non-Line Of Sight，简称NLOS）。需要注意的是，在NLOS传播环境中，仍然可能存在着无线电波的直达路径，只不过相比于LOS传播环境，在NLOS环境下因为遮挡、反射和吸收等损耗，信号强度会在传播过程中变得较弱。
图 1 LOS径与非LOS径示意图
图片来源 https://sites.google.com/site/sanaeeg473/wimax-architecture
2.2 无线电信号的到达时间（TOA）测量
当无线电信号在基站与用户手持终端之间互相传播时，就可以计算基站与手持终端之间的距离，一种常用的测量方式是记录无线电信号从手持终端发出，直到基站接收到信号为止的无线电信号传播时间，将时间乘以无线电信号的传播速度，即得到基站与终端之间沿某条路径的距离。其中，信号在基站与终端之间的传播时间，被称为无线电信号的到达时间（Time Of Arrival，简称TOA）。
图 2 TOA示意图
准确测量TOA所需的前提条件是基站计时与终端计时所使用的时钟是同步的。以图 2为例，当基站与终端在同一个“时间坐标系”里，真实TOA等于接收时刻$t_1$减去发送时刻$t_0$。由于电子器件的工艺原因，基站与终端的时钟可能是不同步的。可以将终端与基站想象成分别使用北京时间和伦敦时间，那么TOA就会在信号真实传播时间上叠加了时区之差。
2.3 影响测量精度的可能因素
基站测量得到的时间或者距离信息往往存在误差，在建模的过程中，工业上一般会着重考虑如下两个因素的影响：
- 使用基站测量的终端信号时，需要考虑的一个很重要因素就是基站侧接收到的信号干扰比值（SINR），定义为： $$ SINR=\frac{\hbox{有用信号强度}}{\hbox{干扰信号强度}+\hbox{噪声信号强度}} $$
- 室内环境下，由于反射频繁发生，会形成无线电波的多径传播（multi-path propagation），从而导致虽然距离很近接收到的信号强度却波动剧烈。
3. 赛题要求
在本题中，需要解决如下四个方面的问题：
- 给定10组LOS或NLOS传播环境下从手持终端到基站的TOA测量数据和所有基站的三维坐标（对应附录中编号为case001_input.txt到case010_input.txt的文件），请根据这些测量数据计算出终端的三维坐标。（请给出详细的建模分析，建模过程中建议考虑测量模型、误差分析等内容。）
- 给定10组TOA测量数据和所有基站的三维坐标（对应附录中编号为case011_input.txt到case020_input.txt的文件），请设计算法，使用尽可能少的基站数目，实现近似最优的三维定位精度。
- 给定5组对处于移动过程中的终端采集到的TOA数据（对应附录中编号为case021_input.txt到case025_input.txt的文件），请设计算法计算出终端的运动轨迹。（此时，编号为case021_input.txt到case025_input.txt的文件中，只记录一个终端的TOA数据，并且是这一个终端在运动轨迹中多个位置上的TOA数据。）
- 在前述3问中，都是假设给定区域内终端到每一个基站的距离都是可知的，但事实上，基站的通信半径是有限的，因此，只有在基站通信半径覆盖范围内的终端才有可能测到自身到基站的距离。而一个终端只有获得它与足够数目的基站之间的距离测量值，才能完成定位。假设每个基站的通信半径为200米（超过范围虽然有测量数据，但无效）。请根据给定的5组测量信息数据集（对应附录中编号为case026_input.txt到case030_input.txt的文件），设计算法寻找出可以被基站定位的所有终端。进一步，回答如下问题：每一个场景中（对应着case026_input.txt到case030_input.txt五个文件中的一个），定义终端的平均“连接度数”$\lambda$为 $$ \lambda=\frac{\hbox{所有可以被定位终端到基站之间的连接数}}{\hbox{终端数}},$$ 请建立模型分析连接度数$\lambda$与定位精度之间的关系。
4. 数据集描述
4.1 基本数据
输入：
- 每一个基站的三维（某些场景下会退化为二维，在文件中通过标识位给出）坐标，其中，第$j$个基站$A_j$的三维坐标记为$(x_j,y_j,z_j)$。
- 矩阵$\Phi=\left[\begin{array}{ccc} &\vdots&\\ \cdots&TOA(u_i,A_j)&\cdots \\&\vdots&\end{array}\right]_{M\times N}$。 矩阵$\Phi$中$i$行$j$列元素表示标号为$i$的终端（记为$u_i$）到标号为$j$的基站（记为$A_j$）之间的TOA测量值，记为$TOA(u_i,A_j)$。假设网络中有$M$个终端，$N$个基站，则矩阵$\Phi$的维度为$M\times N$。
- 输入文件的格式为txt。
- 请特别注意输入文件的具体物理意义： 第1行为基站个数$N$，第2行为终端个数$M$，第3行为标识位，（2表示二维场景，3表示三维场景），第4到第$(N+3)$行为基站坐标，第$(N+4)$行到第$(N+M+3)$行为$TOA$矩阵$\Phi$。
输出：
$M\times3$维矩阵，第$i$行表示第$i$个终端的三维坐标（部分场景下是$M\times2$维矩阵），存放在txt文件中。
4.2 补充说明
4.2.1 关于TOA数据的说明
在实际场景中，受带宽、信噪比、时钟同步以及NLOS传播环境的影响，TOA测量会产生不同的误差。给定的TOA数据也不例外。
由于时钟不同步问题引起的误差在200ns以内，由于NLOS导致的时延最高可能超过400ns。
4.2.2 关于无线电信号测量的说明
当无线电波沿直线传播时，估计无线电波从发送点到接收点之间真实传播时间，从数学形式上，即如下等式中对于$x$的估计问题： $$ \hat x=x+\omega, (*) $$
$(*)$式中，$x$表示真实的传播时间，$\omega$表示测量噪声，$\hat x$表示对于传播时间的观测。这时，测距问题就等价于根据观测值$\hat x$来获取（在某一个指标意义下）尽可能准确的x。而如果无线电波传播环境比较复杂时，观测值可以表示为 $$ \hat x=f(x,\omega) (**)$$
此时的观测量$\hat x$中包含一些依赖于$x$以及函数$f$的因素。这时需要解决的仍然是如何依据观测值$\hat x$在某个恰当的指标意义下估计$x$的问题。一般而言，场景不同，函数$f$不同，算法思想可以相同也可以有所不同，我们的目标就是要能够在任意的场景下，自适应地选择与场景匹配的模型预算法，并且根据测量数据迅速对终端进行准确定位。
从物理意义上说，根据式$(**)$中描述的情况，对于$x$的估计相对式$(*)$来说会变得困难，但是数值解通常是容易得到的。
4.2.3 关于物理常数的说明
无线电信号的传播速度统一取$3\times10^8m/s$。
4.2.4 关于输出格式的说明
1. 赛题最终输出文件格式应命名为output_case_xyz.txt。其中xyz与赛题给定的input case编号一致，比如input case 1的输出文件格式应为output_case_001.txt。
2. 输出文件中的第i行对应着标号为i的终端的2维或者3维坐标。
4.2.5 关于数据读取方式的说明
选手可以自行选择软件对txt文件进行读取。需要注意的是在windows下使用记事本打开txt文件无法体现数据格式，建议使用Notepad++等文本编辑器打开。
5. 测试用例
针对赛题第3部分要求的第1和2两个子问题，提供了5组测试数据，供选手验证算法性能。测试数据的输入信息文件命名为sample_case001_input.txt等，对应的正确的终端位置信息文件命名为sample_case001_ans.txt。
为了与实际应用场景相吻合，测试数据是在LOS或者NLOS环境下测量得到，未予说明。