基于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-)，女，碩士研究生，主要研究方向為軟件監控。