基于Cell_ID的区域定位方法的研究与实现

王雪靖，戴亚丽

(1. 北京邮电大学网络技术研究院，北京市 100876；2. 上海欣方智能系统有限公司北京分公司，北京市 100085)

基于Cell_ID的区域定位方法的研究与实现

王雪靖1，戴亚丽2

(1. 北京邮电大学网络技术研究院，北京市 100876；2. 上海欣方智能系统有限公司北京分公司，北京市 100085)

传统区域监控系统一般具有成本高、灵活度低，监控信息可视化程度低等缺点。为了克服这些缺点，提出了一种基于Cell_ID定位技术的区域监控方法，并详细阐述了通过对监控区域（圆形、多边形）划定最大最小经纬度组合这种方式来减少获取Cell_ID集合的时间。通过对方法的编程验证，表明该方法确实能提高区域定位的效率。

Cell_ID；区域定位

本文著录格式：王雪靖，戴亚丽. 基于Cell_ID的区域定位方法的研究与实现[J]. 软件，2016，37（11）：110-113

0 引言

当前社会对于区域监控系统的需求日益显现，区域监控技术也随之迅速发展。在区域监控领域，国内应用比较广泛的是硬件视频设备和软件平台相结合的视频监控系统[1]，但视频监控系统监控区域受视频监控硬件设备限制，其成本高、灵活度不高；并且无法获取监控区域内人群详细信息，监控效果不够可视化，实时性不强。Cell-ID是基站小区识别码，Cell-ID定位是通过识别信令中标识基站的Cell-ID实现的。基于Cell-ID的定位技术可以通过识别网络中传输用户呼叫的小区信息，并将包含Cell-ID的小区信息翻译成纬度和经度来确定用户位置[2]。Cell-ID定位技术相较于其他定位技术成本较低，且不受限于移动终端的位置，因此占有较重要的地位[3]。

Cell-ID定位技术的定位过程是：每个小区都有自己特定的小区识别码(Cell-ID)，当移动终端进入某一小区时，移动终端要在当前小区进行注册，位置业务平台中的数据就会有相应的小区ID标识。位置业务平台根据采集到的移动终端所处小区的标识号来确定移动终端用户的位置。在这样一个综合背景下，本文提出一种区域定位方法，通过将Cell_ID定位技术反向应用得到某划定区域内所有Cell_ID的集合，为进一步获取用户信息做准备。

1 基于Cell_ID的区域定位方法

提出的区域定位方法的思想可描述如下：

a）需要划定待定位的区域，区域形状可以是圆形或者多边形，若为圆形则要求指定圆中心点的经纬度坐标和圆半径，若为多边形则要求给出多边形各个顶点的经纬度坐标；

b）根据上一步中给点的区域信息计算得出所划定区域的经纬度范围；

c）遍历基站信息表，根据表中的基站信息、Cell_

ID和基站经纬度等信息，根据基站经纬度坐标初步判定该基站是否可能处于划定区域内，从而得到初选Cell_ID集合；

d）最后遍历初选Cell_ID集合，根据基站经纬度坐标计算各基站是否在划定区域内，确定最终的Cell_ID集合。

下面根据划定区域形状的不同，详细介绍得到Cell_ID集合的具体步骤。

1.1 圆形区域定位方法

划定区域形状为圆形时，通过遍历基站信息表，计算筛选出符合要求的Cell_ID，最终得到Cell_ID集合。筛选的条件是判定基站是否在圆内，即通过地球上两点间距离的公式计算基站位置和划定区域中心点之间的距离L与划定区域圆的半径做比较。

方法示意图如图1所示，详细的步骤可描述如下：

图1 圆形区域方法示意图

a）计算得到最大、最小经纬度组合：在二维平面上，要快速判断散列点是否在一个圆内，优化的方法是找出圆的最大坐标点和最小坐标点，做一个圆的外切正方形。通过比较X轴和Y轴坐标判断，如果点在外切正方形外，则该点一定不在圆内，如果点在外切正方形内，则该点可能在圆内，需要再根据距离公式通过计算进一步判断点在是否在圆内；类比到本方法中，要判断地球上某一点是否在圆内，就要得到圆的经纬度范围。已知同一经度上，纬度每隔一度相差111km[3]，同一纬度上，经度每隔一度相差 111*cos（该点纬度）km，则根据中心点经纬度和设定区域的半径，地球半径及经纬度之间的关系估算得到划定范围的最大的经纬度组合Max(Lng_max,Lat_max)及最小的经纬度组合Min(Lng_min,Lat_min)；

b）计算得到初选Cell_ID集合：遍历基站信息表，筛选出经纬度处于计算所得区域经纬度范围内的基站加入初选Cell_ID集合，即Lng_min

c）遍历第一步得到的初选Cell_ID集合，判断各基站是否在划定区域圆内，若是则将该Cell_ID加入最终的Cell_ID集合。针对某一具体经纬度坐标来判断是否在划定形区域圆内根据的是地球上两点间距离[3]的公式即：

其中，r为地球半径，均值为6370km。A、B点经纬度坐标为（x_1，y_1）、（x_2，y_2），东经、北纬为正，西经、南纬为负。A为圆心，B为任意一点，R为划定区域圆的半径，L为Cell-ID对应的经纬度点和划定区域中心点之间的距离即AB的距离。L与R比较，若L小于R，则该Cell-ID对应经纬度点在划定区域内，即B点在圆内。

1.2 多边形区域定位方法

若划定区域形状为多边形，则需要根据点在多边形内部，则该点与多边形所持相邻顶点组成的三角形面积和为多边形面积，反之不成立[3]。这一结论来判断某一基站是否处于划定区域内，即计算该基站与多边形所持相邻顶点组成的三角形面积与多边形面积和作比较，若三角形面积和等于多边形面积，表示该基站处于划定多边形区域内部，故将该基站对应的Cell_ID加入Cell_ID集合。通过遍历基站信息表，最终得到Cell_ID集合。

方法示意图如图2所示，详细的步骤可描述如下：

图2 多边形形区域方法示意图

a）计算得到最大、最小经纬度组合：根据区域的各顶点经纬度坐标计算得到所划定区域的最大的经纬度组合Max(Lng_max,Lat_max)及最小的经纬度组合Min(Lng_min,Lat_min)；

b）计算得到初选Cell_ID集合：遍历基站信息表，筛选出经纬度处于计算所得区域经纬度范围内的基站，并将其对应的Cell_ID加入初选Cell_ID集合；

c）判断基站是否在划定多边形区域内：遍历初选Cell_ID集合，判断各Cell_ID对应的基站是否在划定多边形区域内，若是则将该Cell_ID加入最终

的Cell_ID集合。针对某一具体基站判断是否在划定多边形区域内的方法如下：首先根据三角形面积公式，计算该基站和多边形各相邻顶点组成的三角形面积之和S△，公式如下：

根据多边形面积公式再计算多边形面积S，公式如下：

如果三角形面积和等于多边形面积，表示该基站在划定区域内。由于在实际计算中三角形面积和多边形面积只作为中间值来判断是否相等，因此在利用已知多边形顶点坐标求多边形面积时无需进行坐标转换求真实面积值，只求相对面积值即可。

2 区域定位方法验证

2.1 圆形区域定位方法验证

在地图上选定点（Lng，Lat）与半径长度R做一个圆，为监控区域。选取1200基站信息放入基站信息表中，其中400个基站在划定区域内，400个基站不在划定区域内，但在最大、最小区域经纬度组合内，最后400个基站在最大、最小经纬度组合外；计算用区域定位方法而得到指定区域内基站Cell_ID集合的时间T1和不使用方法进行直接比较来得到基站Cell_ID集合的时间T2。重复这个过程20次，验证结果为表1所示。

若要判断一个点是否在圆内，方法是计算该点和圆心之间的距离并与圆的半径作比较，根据两点间距离公式即公式1，可以看出计算机做了两次乘法运算。而单独一省的基站信息表中数据可达2万多条，若通过对每一基站都详细计算的方式来得到Cell_ID集合，那么至少要做4万多次乘法运算，计算机处理乘法得指令又相对复杂，明显会有较大的时间消耗。而区域方法是预先计算出划定区域的最大和最小经纬度组合，即所划定区域的经纬度范围，通过一次遍历初步筛选出经纬度同时处在该范围内的基站，并将其对应的Cell_ID加入初选Cell_ID集合，再针对初选Cell_ID逐个根据两点间距离公式判断Cell_ID是否在圆内。通过这样的方式降低了乘法运算的次数，从而降低时间消耗，提高了区域定位方法的效率。

通过表1结果所示，使用区域方法的时间要低于不使用区域方法的时间，效率提高了41.85%。这个结果与理论分析结果相符合。

表1 圆形区域方法时间对比表

2.2 多边形区域定位方法验证

在地图上选定多个点（Lng，Lat）做一个多边形，为监控区域。选取1200基站信息放入基站信息表中，其中400个基站在多边形区域内，400个基站不在多边形区域内，但在最大、最小区域经纬度组合内，最后400个基站在最大、最小经纬度组合外；计算用多边形区域定位方法而得到指定区域内基站Cell_ID集合的时间T1和不使用方法进行直接比较来得到基站Cell_ID集合的时间T2。重复这个过程20次，验证结果为表2所示。

若要判断一个点是否在多边形区域内，不使用区域方法的过程是遍历每一个点与多边形顶点组成的三角形面积和是否与四边形面积相等，如果相当则在多边形内。根据公式2可以看出，若多边形顶点为n个，地理位置点为m个，则为判断点在多边形区域内一共要做3m*n次乘法；使用区域方法时，只对在最大最小经纬度组合内的点做乘法判断三角形面积和是否等于四边形面积，从根本上降低了m的大小，从而提高了效率。

通过表2结果所示，使用区域方法的时间要低于不使用区域方法的时间，效率提高了37.36%。这个结果与理论分析结果相符合。

表2 边形区域方法时间对比表

3 结束语

根据Cell_ID定位技术提出了区域定位方法，阐述了得到划定区域内Cell_ID集合的方法思想。它可以应用于多种场景，如在自然灾害预警时气象台要向指定区域的人员发送预警通知，可以使用此方法得到灾害区域的Cell_ID集合，再根据数据库内Cell_ID与手机号码等信息的对应关系表最后得出划定区域的所有人员信息并向其发送通知。另外本方法还可以应用在区域监控上，如实时监控指定域内都有哪些人员，或者查询指定区域内在过去的某段时间内曾有哪些人员出现，前者可以使用圆形区域定位方法，因为实时监控对时间要求较高，而后者可以使用多边形区域定位方法，因为历史查询对时间要求不高，而对精准度要求较高。两者在得到区域的Cell_ID集合后，根据对应关系表，就可以得出区域内的人员信息。本方法还可以应用于区域人员分析上，例如在指定区域内，一天中哪个时间段人流量最大，一年中哪个季节人流量大等。综上总结，基于Cell_ID的区域定位方法适用于多种区域定位场景，可以灵活的划定区域，不需要复杂硬件设备，实现简单，快速达到区域定位人员的目标。

[1] 赵露名. 基于位置视频监控系统前台展示交互的设计与实现[J]. 软件, 2014, 35(10): 91-94.

[2] 林炜杰. CDMA无线定位技术与组网方案的理论探讨[J].中国新通信, 2013, 15: 2-3.

[3] 沈泽, 雒江涛, 周云峰, 林举厅, 舒忠玲. 基于移动网络信令的区域人群属性分析的研究与应用[J]. 计算机应用研究, 2014, 03: 756-759.

[4] 黎珍惜, 黎家勋. 基于经纬度快速计算两点间距离及测量误差[J]. 测绘工程, 2013, 11: 235-236.

[5] 董璇. 应用高中数学知识推导地球上两点间距离公式[J].数学教学与研究2015, 91: 65-66.

[6] 高志军, 王继尧. 基于三角形的多边形内点自动生成算法[J]. 地质学刊, 2007, 31(3): 251-253.

Research and Implementation of Zone Location Method Based on Cell_ID Positioning

WANG Xue-jing1, DAI Ya-li2
(1. Network Technology Research Institute, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. Shanghai Cintel Intelligent System Co., Ltd. Beijing Branch, Beijing 100085, China)

The traditional regional monitoring system has the disadvantages of high cost, low flexibility, low visibility of monitoring information. In order to overcome these shortcomings, it proposes a regional monitoring method based on Cell_ID, and elaborated by the surveillance area (circular, polygonal) designated the maximum and minimum longitude combined in such a way as to reduce the access time of the Cell_ID collection. By programming the method, it is proved that the method can improve the efficiency of the regional positioning.

Cell_ID; Zone location

TP311

A

10.3969/j.issn.1003-6970.2016.11.024

王雪靖(1990-)，女，硕士研究生，主要研究方向为软件监控。