基于Cell_ID的區(qū)域定位方法的研究與實現(xiàn)

王雪靖，戴亞麗

(1. 北京郵電大學網(wǎng)絡技術研究院，北京市 100876；2. 上海欣方智能系統(tǒng)有限公司北京分公司，北京市 100085)

基于Cell_ID的區(qū)域定位方法的研究與實現(xiàn)

王雪靖1，戴亞麗2

(1. 北京郵電大學網(wǎng)絡技術研究院，北京市 100876；2. 上海欣方智能系統(tǒng)有限公司北京分公司，北京市 100085)

傳統(tǒng)區(qū)域監(jiān)控系統(tǒng)一般具有成本高、靈活度低，監(jiān)控信息可視化程度低等缺點。為了克服這些缺點，提出了一種基于Cell_ID定位技術的區(qū)域監(jiān)控方法，并詳細闡述了通過對監(jiān)控區(qū)域（圓形、多邊形）劃定最大最小經(jīng)緯度組合這種方式來減少獲取Cell_ID集合的時間。通過對方法的編程驗證，表明該方法確實能提高區(qū)域定位的效率。

Cell_ID；區(qū)域定位

本文著錄格式：王雪靖，戴亞麗. 基于Cell_ID的區(qū)域定位方法的研究與實現(xiàn)[J]. 軟件，2016，37（11）：110-113

0 引言

當前社會對于區(qū)域監(jiān)控系統(tǒng)的需求日益顯現(xiàn)，區(qū)域監(jiān)控技術也隨之迅速發(fā)展。在區(qū)域監(jiān)控領域，國內應用比較廣泛的是硬件視頻設備和軟件平臺相結合的視頻監(jiān)控系統(tǒng)[1]，但視頻監(jiān)控系統(tǒng)監(jiān)控區(qū)域受視頻監(jiān)控硬件設備限制，其成本高、靈活度不高；并且無法獲取監(jiān)控區(qū)域內人群詳細信息，監(jiān)控效果不夠可視化，實時性不強。Cell-ID是基站小區(qū)識別碼，Cell-ID定位是通過識別信令中標識基站的Cell-ID實現(xiàn)的?；贑ell-ID的定位技術可以通過識別網(wǎng)絡中傳輸用戶呼叫的小區(qū)信息，并將包含Cell-ID的小區(qū)信息翻譯成緯度和經(jīng)度來確定用戶位置[2]。Cell-ID定位技術相較于其他定位技術成本較低，且不受限于移動終端的位置，因此占有較重要的地位[3]。

Cell-ID定位技術的定位過程是：每個小區(qū)都有自己特定的小區(qū)識別碼(Cell-ID)，當移動終端進入某一小區(qū)時，移動終端要在當前小區(qū)進行注冊，位置業(yè)務平臺中的數(shù)據(jù)就會有相應的小區(qū)ID標識。位置業(yè)務平臺根據(jù)采集到的移動終端所處小區(qū)的標識號來確定移動終端用戶的位置。在這樣一個綜合背景下，本文提出一種區(qū)域定位方法，通過將Cell_ID定位技術反向應用得到某劃定區(qū)域內所有Cell_ID的集合，為進一步獲取用戶信息做準備。

1 基于Cell_ID的區(qū)域定位方法

提出的區(qū)域定位方法的思想可描述如下：

a）需要劃定待定位的區(qū)域，區(qū)域形狀可以是圓形或者多邊形，若為圓形則要求指定圓中心點的經(jīng)緯度坐標和圓半徑，若為多邊形則要求給出多邊形各個頂點的經(jīng)緯度坐標；

b）根據(jù)上一步中給點的區(qū)域信息計算得出所劃定區(qū)域的經(jīng)緯度范圍；

c）遍歷基站信息表，根據(jù)表中的基站信息、Cell_

ID和基站經(jīng)緯度等信息，根據(jù)基站經(jīng)緯度坐標初步判定該基站是否可能處于劃定區(qū)域內，從而得到初選Cell_ID集合；

d）最后遍歷初選Cell_ID集合，根據(jù)基站經(jīng)緯度坐標計算各基站是否在劃定區(qū)域內，確定最終的Cell_ID集合。

下面根據(jù)劃定區(qū)域形狀的不同，詳細介紹得到Cell_ID集合的具體步驟。

1.1 圓形區(qū)域定位方法

劃定區(qū)域形狀為圓形時，通過遍歷基站信息表，計算篩選出符合要求的Cell_ID，最終得到Cell_ID集合。篩選的條件是判定基站是否在圓內，即通過地球上兩點間距離的公式計算基站位置和劃定區(qū)域中心點之間的距離L與劃定區(qū)域圓的半徑做比較。

方法示意圖如圖1所示，詳細的步驟可描述如下：

圖1 圓形區(qū)域方法示意圖

a）計算得到最大、最小經(jīng)緯度組合：在二維平面上，要快速判斷散列點是否在一個圓內，優(yōu)化的方法是找出圓的最大坐標點和最小坐標點，做一個圓的外切正方形。通過比較X軸和Y軸坐標判斷，如果點在外切正方形外，則該點一定不在圓內，如果點在外切正方形內，則該點可能在圓內，需要再根據(jù)距離公式通過計算進一步判斷點在是否在圓內；類比到本方法中，要判斷地球上某一點是否在圓內，就要得到圓的經(jīng)緯度范圍。已知同一經(jīng)度上，緯度每隔一度相差111km[3]，同一緯度上，經(jīng)度每隔一度相差 111*cos（該點緯度）km，則根據(jù)中心點經(jīng)緯度和設定區(qū)域的半徑，地球半徑及經(jīng)緯度之間的關系估算得到劃定范圍的最大的經(jīng)緯度組合Max(Lng_max,Lat_max)及最小的經(jīng)緯度組合Min(Lng_min,Lat_min)；

b）計算得到初選Cell_ID集合：遍歷基站信息表，篩選出經(jīng)緯度處于計算所得區(qū)域經(jīng)緯度范圍內的基站加入初選Cell_ID集合，即Lng_min

c）遍歷第一步得到的初選Cell_ID集合，判斷各基站是否在劃定區(qū)域圓內，若是則將該Cell_ID加入最終的Cell_ID集合。針對某一具體經(jīng)緯度坐標來判斷是否在劃定形區(qū)域圓內根據(jù)的是地球上兩點間距離[3]的公式即：

其中，r為地球半徑，均值為6370km。A、B點經(jīng)緯度坐標為（x_1，y_1）、（x_2，y_2），東經(jīng)、北緯為正，西經(jīng)、南緯為負。A為圓心，B為任意一點，R為劃定區(qū)域圓的半徑，L為Cell-ID對應的經(jīng)緯度點和劃定區(qū)域中心點之間的距離即AB的距離。L與R比較，若L小于R，則該Cell-ID對應經(jīng)緯度點在劃定區(qū)域內，即B點在圓內。

1.2 多邊形區(qū)域定位方法

若劃定區(qū)域形狀為多邊形，則需要根據(jù)點在多邊形內部，則該點與多邊形所持相鄰頂點組成的三角形面積和為多邊形面積，反之不成立[3]。這一結論來判斷某一基站是否處于劃定區(qū)域內，即計算該基站與多邊形所持相鄰頂點組成的三角形面積與多邊形面積和作比較，若三角形面積和等于多邊形面積，表示該基站處于劃定多邊形區(qū)域內部，故將該基站對應的Cell_ID加入Cell_ID集合。通過遍歷基站信息表，最終得到Cell_ID集合。

方法示意圖如圖2所示，詳細的步驟可描述如下：

圖2 多邊形形區(qū)域方法示意圖

a）計算得到最大、最小經(jīng)緯度組合：根據(jù)區(qū)域的各頂點經(jīng)緯度坐標計算得到所劃定區(qū)域的最大的經(jīng)緯度組合Max(Lng_max,Lat_max)及最小的經(jīng)緯度組合Min(Lng_min,Lat_min)；

b）計算得到初選Cell_ID集合：遍歷基站信息表，篩選出經(jīng)緯度處于計算所得區(qū)域經(jīng)緯度范圍內的基站，并將其對應的Cell_ID加入初選Cell_ID集合；

c）判斷基站是否在劃定多邊形區(qū)域內：遍歷初選Cell_ID集合，判斷各Cell_ID對應的基站是否在劃定多邊形區(qū)域內，若是則將該Cell_ID加入最終

的Cell_ID集合。針對某一具體基站判斷是否在劃定多邊形區(qū)域內的方法如下：首先根據(jù)三角形面積公式，計算該基站和多邊形各相鄰頂點組成的三角形面積之和S△，公式如下：

根據(jù)多邊形面積公式再計算多邊形面積S，公式如下：

如果三角形面積和等于多邊形面積，表示該基站在劃定區(qū)域內。由于在實際計算中三角形面積和多邊形面積只作為中間值來判斷是否相等，因此在利用已知多邊形頂點坐標求多邊形面積時無需進行坐標轉換求真實面積值，只求相對面積值即可。

2 區(qū)域定位方法驗證

2.1 圓形區(qū)域定位方法驗證

在地圖上選定點（Lng，Lat）與半徑長度R做一個圓，為監(jiān)控區(qū)域。選取1200基站信息放入基站信息表中，其中400個基站在劃定區(qū)域內，400個基站不在劃定區(qū)域內，但在最大、最小區(qū)域經(jīng)緯度組合內，最后400個基站在最大、最小經(jīng)緯度組合外；計算用區(qū)域定位方法而得到指定區(qū)域內基站Cell_ID集合的時間T1和不使用方法進行直接比較來得到基站Cell_ID集合的時間T2。重復這個過程20次，驗證結果為表1所示。

若要判斷一個點是否在圓內，方法是計算該點和圓心之間的距離并與圓的半徑作比較，根據(jù)兩點間距離公式即公式1，可以看出計算機做了兩次乘法運算。而單獨一省的基站信息表中數(shù)據(jù)可達2萬多條，若通過對每一基站都詳細計算的方式來得到Cell_ID集合，那么至少要做4萬多次乘法運算，計算機處理乘法得指令又相對復雜，明顯會有較大的時間消耗。而區(qū)域方法是預先計算出劃定區(qū)域的最大和最小經(jīng)緯度組合，即所劃定區(qū)域的經(jīng)緯度范圍，通過一次遍歷初步篩選出經(jīng)緯度同時處在該范圍內的基站，并將其對應的Cell_ID加入初選Cell_ID集合，再針對初選Cell_ID逐個根據(jù)兩點間距離公式判斷Cell_ID是否在圓內。通過這樣的方式降低了乘法運算的次數(shù)，從而降低時間消耗，提高了區(qū)域定位方法的效率。

通過表1結果所示，使用區(qū)域方法的時間要低于不使用區(qū)域方法的時間，效率提高了41.85%。這個結果與理論分析結果相符合。

表1 圓形區(qū)域方法時間對比表

2.2 多邊形區(qū)域定位方法驗證

在地圖上選定多個點（Lng，Lat）做一個多邊形，為監(jiān)控區(qū)域。選取1200基站信息放入基站信息表中，其中400個基站在多邊形區(qū)域內，400個基站不在多邊形區(qū)域內，但在最大、最小區(qū)域經(jīng)緯度組合內，最后400個基站在最大、最小經(jīng)緯度組合外；計算用多邊形區(qū)域定位方法而得到指定區(qū)域內基站Cell_ID集合的時間T1和不使用方法進行直接比較來得到基站Cell_ID集合的時間T2。重復這個過程20次，驗證結果為表2所示。

若要判斷一個點是否在多邊形區(qū)域內，不使用區(qū)域方法的過程是遍歷每一個點與多邊形頂點組成的三角形面積和是否與四邊形面積相等，如果相當則在多邊形內。根據(jù)公式2可以看出，若多邊形頂點為n個，地理位置點為m個，則為判斷點在多邊形區(qū)域內一共要做3m*n次乘法；使用區(qū)域方法時，只對在最大最小經(jīng)緯度組合內的點做乘法判斷三角形面積和是否等于四邊形面積，從根本上降低了m的大小，從而提高了效率。

通過表2結果所示，使用區(qū)域方法的時間要低于不使用區(qū)域方法的時間，效率提高了37.36%。這個結果與理論分析結果相符合。

表2 邊形區(qū)域方法時間對比表

3 結束語

根據(jù)Cell_ID定位技術提出了區(qū)域定位方法，闡述了得到劃定區(qū)域內Cell_ID集合的方法思想。它可以應用于多種場景，如在自然災害預警時氣象臺要向指定區(qū)域的人員發(fā)送預警通知，可以使用此方法得到災害區(qū)域的Cell_ID集合，再根據(jù)數(shù)據(jù)庫內Cell_ID與手機號碼等信息的對應關系表最后得出劃定區(qū)域的所有人員信息并向其發(fā)送通知。另外本方法還可以應用在區(qū)域監(jiān)控上，如實時監(jiān)控指定域內都有哪些人員，或者查詢指定區(qū)域內在過去的某段時間內曾有哪些人員出現(xiàn)，前者可以使用圓形區(qū)域定位方法，因為實時監(jiān)控對時間要求較高，而后者可以使用多邊形區(qū)域定位方法，因為歷史查詢對時間要求不高，而對精準度要求較高。兩者在得到區(qū)域的Cell_ID集合后，根據(jù)對應關系表，就可以得出區(qū)域內的人員信息。本方法還可以應用于區(qū)域人員分析上，例如在指定區(qū)域內，一天中哪個時間段人流量最大，一年中哪個季節(jié)人流量大等。綜上總結，基于Cell_ID的區(qū)域定位方法適用于多種區(qū)域定位場景，可以靈活的劃定區(qū)域，不需要復雜硬件設備，實現(xiàn)簡單，快速達到區(qū)域定位人員的目標。

[1] 趙露名. 基于位置視頻監(jiān)控系統(tǒng)前臺展示交互的設計與實現(xiàn)[J]. 軟件, 2014, 35(10): 91-94.

[2] 林煒杰. CDMA無線定位技術與組網(wǎng)方案的理論探討[J].中國新通信, 2013, 15: 2-3.

[3] 沈澤, 雒江濤, 周云峰, 林舉廳, 舒忠玲. 基于移動網(wǎng)絡信令的區(qū)域人群屬性分析的研究與應用[J]. 計算機應用研究, 2014, 03: 756-759.

[4] 黎珍惜, 黎家勛. 基于經(jīng)緯度快速計算兩點間距離及測量誤差[J]. 測繪工程, 2013, 11: 235-236.

[5] 董璇. 應用高中數(shù)學知識推導地球上兩點間距離公式[J].數(shù)學教學與研究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-)，女，碩士研究生，主要研究方向為軟件監(jiān)控。