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

王雪靖，戴亞麗

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

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

王雪靖1，戴亞麗2

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

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

Cell_ID；區(qū)域定位

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

0 引言

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

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

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

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

a）需要?jiǎng)澏ùㄎ坏膮^(qū)域，區(qū)域形狀可以是圓形或者多邊形，若為圓形則要求指定圓中心點(diǎn)的經(jīng)緯度坐標(biāo)和圓半徑，若為多邊形則要求給出多邊形各個(gè)頂點(diǎn)的經(jīng)緯度坐標(biāo)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果三角形面積和等于多邊形面積，表示該基站在劃定區(qū)域內(nèi)。由于在實(shí)際計(jì)算中三角形面積和多邊形面積只作為中間值來(lái)判斷是否相等，因此在利用已知多邊形頂點(diǎn)坐標(biāo)求多邊形面積時(shí)無(wú)需進(jìn)行坐標(biāo)轉(zhuǎn)換求真實(shí)面積值，只求相對(duì)面積值即可。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

[5] 董璇. 應(yīng)用高中數(shù)學(xué)知識(shí)推導(dǎo)地球上兩點(diǎn)間距離公式[J].數(shù)學(xué)教學(xué)與研究2015, 91: 65-66.

[6] 高志軍, 王繼堯. 基于三角形的多邊形內(nèi)點(diǎn)自動(dòng)生成算法[J]. 地質(zhì)學(xué)刊, 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-)，女，碩士研究生，主要研究方向?yàn)檐浖O(jiān)控。