基于WiFi定位的美团应用
基于WiFi的室内定位原理
1）为提供Wi-Fi服务，室内会部署有热点（AP），每一个无线AP都有一个全球唯一的MAC地址,并且一般来说无线AP在一段时间内是不会改变的。
2）设备可以程序控制扫描并收集周围的AP信号，无论是否加密，是否已连接，甚至信号强度不足以显示在无线信号列表中,都可以获取到AP广播出来的MAC地址。
3）对应每个AP，这里有两个重要数据，AP的MAC地址和信号强度，MAC地址可以决定是哪个AP；信号强度理论上是和AP之间的距离有函数关系的，就是根据信号强度可以算出和AP的距离。
4）设备将这些数据发送到位置服务器，服务器就可以用一个算法计算出设备的地理位置并返回到用户设备。
5）定位的精度取决于AP的个数，信号的稳定程度，以及算法的选择。
美团总部WIFI部署情况
美团总部于2014年1月搬入了望京科技园3期，新的办公室地上共4层，建筑面积一万多平米，共部署有86台无线AP，覆盖很充分，没有死角，这为良好的定位效果打下了基础。
无线无线AP使用的是，ArubA AP-135，这是一款优秀的商用无线路由器，2.4-GHz/5-GHz双频
基本数据测绘
第一步，建立AP的基础数据库是关键，至少需要如下信息：
1）AP的MAC地址，这里是双频的AP。就是有2个无线MAC地址。
2）AP的物理位置
关于AP的物理位置，这里因为范围太小，加之无法找到足够精度的参考点，所有AP的物理位置无法使用GPS坐标，只能使用自定义坐标系，这里有2种选择：
1）以建筑的东南角为参考点（坐标原点），这样就可以测绘AP相对原点的坐标，包含Z轴，单位是米
2）以测绘图的图片为参考，以AP在图中的像素位置为坐标，单位是1像素点
但是很不幸，这里的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，则接收端的接受功率Pr可表示为：
其中Pt为发射功率；Gt和Gr分别为发射和接收天线增益；λ为电波波长，Pt和 Pr的单位是瓦特；Gt和Gr无量纲。由上式可以看出，在自由空间中，接受功率和距离d2,成反比。
在实际环境中，由于存在多径、障碍物、绕射等随机因素，无线电传播损耗与上市相比还是有较大变化的，此时，常采用对数-常态分布模型更为合理：
其中Pr单位为dBm，d0一般取1.在一般室内定位中，考虑到成本、环境、定位精度要求等因素，所使用的RSSI 测距信号衰减模型进一步简化为：
D为定位节点与参考点之间的距离，单位m,A为定位节点与参考点之间的距离d为1m时测得的RSSI值；n为信号衰减因子，范围一般为2-4.
在美团的环境中，我们取A为-50，n为2.1
这样根据信号强度，就能估算设备和AP之间的距离。
定位方法一般是根据几个模型建立方程，然后求解方程得到节点坐标。
这里考虑一般的情况：
考虑一般的情况，设有n个AP，AP1，AP2，...，APn，坐标是（xi,yi)。目标点到这n个AP的距离是di。
设目标点的坐标是（X，Y），则可列一个方程组，有n个等式：
大家都减第一个等式，就消去了二次项，得到另一个方程组，有n-1个等式：
常数项换个名字，得到：
等式除以X的系数ai，变量换个名字，得到：
等式有n-1个，现在问题变成了：已知一组点（ui，vi）满足p+uq=v，求最合适的系数p，q，这是典型的最小二乘法
Java里可以用Apache Commons Math3这个library来解决最小二乘法，文档见 SimpleRegression
这里还有一个问题，AP的坐标（xi，yi）是像素坐标,那di相应的需要是像素距离，需要做一个比例尺变换
比例很容易算，相关代码：
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); //信号最强的那个apfor (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();
}