基于Wi-Fi的室内定位在美团总部的实践和应用（上）

室内定位技术的商业化必将带来一波创新高潮，尤其是在O2O领域，各种基于此技术的应用将出现在我们的面前。我们可以想象一些比较常见的应用场景，比如在大型商场里面借助室内导航快速找到目标商铺，商店根据用户的具体位置向用户推送更多关于商品的介绍等等，这些应用会极好的服务于O2O，提高用户体验。

目前室内定位技术有很多，如A-GPS、蓝牙、超声，红外、信标、射频、Wi-Fi、计算机视觉等，这些技术综合比较，其中以基于Wi-Fi的室内定位技术最为突出，无论从硬件投入、软件投入、实施难度、可控性，还是定位效果方面考察，都是有优势的。

本文描述了作者在美团总部从零开始构建基于Wi-Fi的室内定位系统的过程，具有广泛的借鉴意义。

基于Wi-Fi的室内定位原理

为提供Wi-Fi服务，室内会部署有热点（AP），每一个无线AP都有一个全球唯一的MAC地址,并且一般来说无线AP在一段时间内是不会改变的。
设备可以程序控制扫描并收集周围的AP信号，无论是否加密，是否已连接，甚至信号强度不足以显示在无线信号列表中,都可以获取到AP广播出来的MAC地址。
对应每个AP，这里有两个重要数据，AP的MAC地址和信号强度，MAC地址可以决定是哪个AP；信号强度理论上是和AP之间的距离有函数关系的，就是根据信号强度可以算出和AP的距离。
设备将这些数据发送到位置服务器，服务器就可以用一个算法计算出设备的地理位置并返回到用户设备。
定位的精度取决于AP的个数，信号的稳定程度，以及算法的选择。

美团总部Wi-Fi部署情况

美团总部于2014年1月搬入了望京科技园3期，新的办公室地上共4层，建筑面积一万多平米，共部署有86台无线AP，覆盖很充分，没有死角，这为良好的定位效果打下了基础。

无线AP使用的是，ArubA AP-135，这是一款优秀的商用无线路由器，2.4-GHz/5-GHz双频。

基础数据测绘

第一步，建立AP的基础数据库是关键，至少需要如下信息：

AP的MAC地址，这里是双频的AP，就是有2个无线MAC地址
AP的物理位置

关于AP的物理位置，这里因为范围太小，加之无法找到足够精度的参考点，所以AP的物理位置无法使用GPS坐标，只能使用自定义坐标系。这里有2种选择：

以建筑的东南角为参考点（坐标原点），这样就可以测绘AP相对原点的坐标，包含Z轴，单位是米
以测绘图的图片为参考，以AP在图中的像素位置为坐标，单位是1像素点

这里选用了后一种方法，因为后一种方法容易测绘，大部分工作在电脑上操作即可；前一种方法需要更多的实地测绘工作。

关于AP的MAC地址，从IT那里要到了一个列表，如图所示：

但是很不幸，这里的MAC地址是路由器的WAN口的MAC地址，而我们需要的是两个无线模块的MAC地址。这里只能自己测绘了，我写了一小段android程序，可以排序出最近的AP的MAC地址，然后挨个跑到各个AP下，运行程序，记下两个MAC地址；同时记录下AP的真实物理位置。

WifiManager wm = (WifiManager) getSystemService(Context.WIFI_SERVICE);
wm.startScan();  //开始扫描AP
//等待一段时间，时间可长可短
List<ScanResult> results = wm.getScanResults();  //拿到扫描的结果
Collections.sort(results,this);  //this是个Comparator，按照level排序
//去掉非sankuai的SSID
//在UI线程中，显示到界面上
int max=Math.min(30,results.size());
for(int i=0;i<max;i++) {
    ScanResult one = results.get(i);
    text1.append("\n"+one.BSSID+"\t\t"+one.level);
}

图中信号最强的就是当前AP的MAC地址，然后地址与它相近的是这个AP另一个频段的MAC地址，两个MAC地址都是0结尾，尾数相差1，容易辨认。 MAC地址后面的数字是信号强度，单位是dBm，是个负数。

然后在底图中标注好AP的准确的物理位置，图中红色圆点即是AP位置，其圆心的像素坐标当作AP的坐标。

测绘的数据应该存入数据库，这里设计了一个POJO，服务器端程序可以使用：

public class MtApLoc {

    private int id;        //数字ID    人工定，有一定含义
    private String id1;    //字符串ID  从IT给表中来
    private String mac1;   //WAN MAC地址，有线口的
    private String sn;     //AP的 SN  从IT给表中来
    private String sku;    //资产编号 N  从IT给表中来
    private String mac2;  //无线MAC 1 ，测绘得来
    private String mac3;  //无线MAC 2 ，测绘得来
    private int pn;       //图号  对应楼层
    private float x;      //物理坐标 x  自定义坐标系中
    private float y;      //物理坐标 y  自定义坐标系中

}

然后将测绘的数据录入数据库，最后得到的数据如：

其中的x，y是此AP在对应楼层的测绘图的图片中的坐标。

MAC2和MAC3是AP的两个MAC地址（这里没有区分2.4G和5G），和上面的测绘客户端的截图比较，能看出当时我是站在AP7下的。

把所有86个AP的物理位置和MAC地址测绘收集全后，测绘过程完成。

Android客户端示例

这里写了一个Demo用的android客户端，来测试定位结果，先看客户端运行截图：

点击定位按钮，系统会扫描AP，然后把结果请求到服务器。

HttpPost post = new HttpPost(BaseUrl + "/gar/locate/ap-locate.html");
List<NameValuePair> parameters = new ArrayList<NameValuePair>();
for (ScanResult result : results) {
    parameters.add(new BasicNameValuePair("mac", result.BSSID.toUpperCase()));
    parameters.add(new BasicNameValuePair("rssi", String.valueOf(result.level)));
}
post.setEntity(new UrlEncodedFormEntity(parameters, "UTF-8"));
String res;
synchronized (hc) {
    HttpResponse response = hc.execute(post);
    res = EntityUtils.toString(response.getEntity(), "UTF-8").trim();
}
Log.w(TAG, res);

服务器返回其所在位置，是一个JSON字符串

{"accuracy":0.0,"message":"ok Least Squares","pn":1,"status":0,"x":237.97249473061038,"y":1241.8270604002646}

然后客户端显示pn对应的底图，然后在底图的x，y位置上显示定位到的标志，即图中跳动的红心。客户端大部分代码都是UI相关代码，这里不贴出了。

定位算法

常见的室内定位的算法主要分为两类：基于测距技术的定位算法和距离无关的算法。基于测距技术的算法一般是通过节点之间的距离或者角度来计算出未知节点的位置，实际运用中常见的有：基于接收信号强度指示算法（RSSI）、到达角度算法（AOA）、到达时间算法（TOA）等。距离无关的算法有：质心法、APIT算法、凸规划算法等。这些算法都是利用节点之间的邻近关系实现定位的。一般来说，基于测距技术的算法比无需测距的精度要高，这里适合采用。

首先确定一个信号强度和距离之间的关系，这需要了解电波传播模型。在自由空间环境中，不考虑阻挡和多径传播，设发射端与接收端的距离为d，则接收端的接收功率P_r可表示为：

其中P_t为发射功率；G_t和G_r分别为发射和接收天线增益；λ为电波波长；P_t和P_r的单位是瓦特；G_t和G_r无量纲。由上式可以看出，在自由空间中，接收功率与距离d²成反比。

在实际环境中，由于存在多径、障碍物、绕射等随机因素，无线电传播损耗与上式相比还是有较大变化。此时，常采用对数-常态分布模型更为合理：

其中P_r单位为dBm ，d₀一般取1。在一般室内定位中，考虑到环境、成本、定位精度要求等因素，所使用的RSSI测距信号衰减模型进一步简化为：

d为定位节点与参考点之间的距离，单位m；A为定位节点与参考点之间的距离d为1m时测得的RSSI值；n为信号衰减因子，范围一般为2～4。

在美团的环境中，我们取A为-50，n为2.1。

这样根据信号强度，就能估算设备和AP之间的距离。

定位方法一般是根据几何模型建立方程，然后求解方程得到节点坐标。只有一个AP的情况：

这里目标点坐标只能取AP的坐标，精度取半径

两个AP的情况：

这里取AB的中间位置，精度取AB的长度。

三个AP的情况：

这里取三个圆的一个共同交点。

不过实际没有这么简单，因为距离都有误差，两个AP时，可能是这种情况：

三个AP可能是这种情况

甚至这种：

这只是三个AP，有更多AP时怎么办？

这里考虑一般的情况：

考虑一般的情况，设有n个AP，AP₁，AP₂，…，AP_n，坐标是（x_i,y_i)。目标点到这n个AP的距离是d_i。设目标点的坐标是（X，Y），则可列一个方程组，有n个等式：

大家都减第一个等式，就消去了二次项，得到另一个方程组，有n-1个等式：

常数项换个名字，得到：

等式除以X的系数a_i，变量换个名字，得到：

等式有n-1个，现在问题变成了：已知一组点（u_i，v_i）满足p+uq=v，求最合适的系数p，q，这是典型的最小二乘法

Java里可以用Apache Commons Math3这个library来解决最小二乘法，文档见 SimpleRegression

这里还有一个问题，AP的坐标（x_i，y_i）是像素坐标,那d_i相应的需要是像素距离，需要做一个比例尺变换

比例很容易算，相关代码：

public double getPicLen(double rssi) {
    double f=(-rssi-50)/22.0;
    return 41.785*Math.pow(10,f);
}

服务器端代码示例

通过上面的描述，服务器端代码就很容易写了，这里给出主要代码：

private String[] macs;  //输入mac地址
private float[] rssis;  //输入信号强度
private int pn;     //输出，楼层
private double x,y,accuracy;  //输出，定位到的坐标 和 精度

List<MtApLoc> aps=new ArrayList<>(map.keySet());
MtApLoc first=aps.get(0);  //信号最强的那个ap
for (MtApLoc one : aps) {   //以信号最强的ap的楼层作为最终楼层，因为可能搜到其它楼层的信号
    if(one.getPn()!=first.getPn()) {  //干掉其它楼层的ap
        map.remove(one);
    }
}
aps.clear();
aps.addAll(map.keySet());
size=aps.size();
this.pn=first.getPn();
if(size==1) {
    setStatus(0);
    setMessage("ok one point");
    this.x=first.getX();
    this.y=first.getY();
    this.accuracy=getPicLen(map.get(first).floatValue());
    return JSON;
} else if(size==2) {
    setStatus(3);
    setMessage("to impl");
} else {
    float minRssi=-65;  //信号强大要达到 -65 才参与运算
    int min=4;    //至少需要4个ap，这个条件比上个条件优先
    size=0;
    for(Iterator<MtApLoc> it = aps.iterator();it.hasNext();) {
        MtApLoc ap = it.next();
        if(map.get(ap).floatValue()<minRssi && size>=min) {
            it.remove();
        } else {
            size++;
        }
    }
    //map的key之前是信号强度，现在变为 像素距离
    aps.forEach(ap -> map.put(ap,getPicLen(map.get(ap).floatValue())));
    double[][] ps=new double[size-1][4];  //看 size-1
    double r1=map.get(first).doubleValue();
    r1=r1*r1;
    double r2=first.getX()*first.getX()+first.getY()*first.getY();
    int n=0;
    for (MtApLoc ap : aps) {  //生成数据
        if(ap!=first) {
            ps[n][0]=ap.getX()*ap.getX()+ap.getY()*ap.getY()-r2;
            ps[n][1]=2*(first.getX()-ap.getX());
            ps[n][2]=2*(first.getY()-ap.getY());
            double r=map.get(ap).doubleValue();
            ps[n][3]=r*r-r1;
            n++;
        }
    }
    assert n==(size-1);
    for(int i=0;i<n;i++) {  //生成数据
        double k=ps[i][1];
        ps[i][1]=(ps[i][3]-ps[i][0])/k;
        ps[i][0]=ps[i][2]/k;
    }
    SimpleRegression reg=new SimpleRegression(true);  //最小二乘法
    reg.addData(ps);
    setStatus(0);
    setMessage("ok Least Squares");
    this.x=reg.getIntercept();
    this.y=reg.getSlope();
}

效果检验

系统完成了，这里需要检验一下定位效果。为了简化过程，我是这样操作的：我选择了一个固定点，就是我的座位（上面客户端截图中跳动的红心所在的位置），然后用手机客户端做100次定位操作，同时服务器做log记录下100次的定位结果，然后做分析。

我座位这个点被3个AP包围着，定位效果应该不错，所以结论可能会偏乐观，实际应该选择不同的点。不过选择不同的点要记录真实的点的坐标，稍显麻烦。后面做进一步改进和测试时，可以选择不同的点做测试，这算作一个todo。然后就得到100个定位结果，然后可以计算和真实点的偏差，结果如：

其中x、y是定位到的坐标，单位是像素坐标，diff是计算出的偏差，单位是米。

然后按距离排序，得到如下表，是全部数据：

从这个表可以大致分析定位效果：

100个点中，误差小于1米的有4个点
大部分点误差在1米到4米，有93个点，大致呈均匀分布态势
误差大于4米的有3个点，而且误差极大，明显属于失败的噪声点

去掉3个失败的点，剩下的97个点，可以用excel画一个分布图：

分析上面数据，以及实际测试过程，能发现，这个系统应该有一个系统误差。就是测试中，定位结果总是分布在距我大概2米处的某一点周围，应该是系统编码某个地方缺陷造成的。

这是待改进的To Do，预计找到问题解决后，重复上面的测试过程，定位效果能达到95%的点误差小于2米的水平。

另外上面我选的点应该属于定位效果较好的点，一般情况的点的定位精度，得进一步详细测试得出。这里我拍脑袋估计，系统应该在90%的点误差小于5米的水平。

进一步工作，改进与设想

整个系统正在应用到移动组开发的一个找会议室的手机应用“会议室”中，为其增加定位自身的功能。为了完善系统，现在能想到的改进有：

找到并改进上面说到的系统误差
完善后，做进一步的评测
考虑2.4G和5G信号的定位差别，目前是不区分的
信号强度和距离的公式的系数做进一步精确
核心定位算法目前采用的是最小二乘法，目前在考虑用更智能的一个方法，叫“位置指纹”，这个算法预计效果更好，也容易实施
目前坐标系统用的自定义的坐标系，这个不利于使用者使用，考虑用更好的坐标系
光有定位接口是不够的，还应该有坐标和地址相互转换的接口；还应该有导航的接口
推广应用到更多实际的系统中

这些改进，会逐步完善，敬请期待本系列的（下）篇。