位置感知的移動節(jié)點聚集檢測方法研究

郭曉雷，秘建寧，張宇，張欣海

(中國電子科學(xué)研究院，北京　100041)

?

工程與應(yīng)用

位置感知的移動節(jié)點聚集檢測方法研究

郭曉雷，秘建寧，張宇，張欣海

(中國電子科學(xué)研究院，北京100041)

移動節(jié)點聚集檢測是無線網(wǎng)絡(luò)應(yīng)用的一項新內(nèi)容。為提高大規(guī)模目標(biāo)區(qū)域內(nèi)節(jié)點聚集檢測的效率和準(zhǔn)確度，提出一種基于位置感知和密度聚類的移動節(jié)點聚集檢測方法。首先，通過無線定位技術(shù)來獲取移動節(jié)點的位置坐標(biāo)，此過程中，有偏最小二乘法可用于降低距離估計誤差對定位的影響；其次，在將目標(biāo)區(qū)域進(jìn)行網(wǎng)格劃分的基礎(chǔ)上，采用密度聚類方法搜索節(jié)點聚集簇，并對相鄰網(wǎng)格的節(jié)點相鄰聚集簇進(jìn)行合并；最后，輸出節(jié)點聚集簇的區(qū)域及其包含的節(jié)點信息。仿真試驗驗證了方法在實際應(yīng)用中的可行性和有效性。

節(jié)點聚集檢測；無線定位；聚類分析

0　引　言

隨著無線通信、微機(jī)電系統(tǒng)、數(shù)字電子等技術(shù)的發(fā)展，各種移動無線網(wǎng)絡(luò)的研究和應(yīng)用呈現(xiàn)出高速增長的態(tài)勢，目前最廣泛應(yīng)用的有移動通信網(wǎng)、無線局域網(wǎng)(WLAN)和各類自組織(Ad hoc)網(wǎng)絡(luò)。這些網(wǎng)絡(luò)除了提供最基本的無線通信和網(wǎng)絡(luò)接入功能外，還衍生出多種典型應(yīng)用，例如定位跟蹤、實時監(jiān)控、智能家居、交通管理、物流調(diào)配等[1,2]。

移動節(jié)點聚集檢測技術(shù)作為無線網(wǎng)絡(luò)研究的一項新內(nèi)容，對于無線網(wǎng)絡(luò)應(yīng)用的豐富和擴(kuò)展有著重要意義。例如，在公共安全領(lǐng)域[3]，基于手機(jī)與使用者之間普遍存在的“人機(jī)一體”現(xiàn)象，利用手機(jī)聚集檢測技術(shù)，可實現(xiàn)對重要場所人群的實時監(jiān)測和有效管理，自動判斷人群聚集情況并及早發(fā)現(xiàn)人群行為異常的預(yù)兆，從而及時采取解決措施，避免災(zāi)禍的發(fā)生；在城市交通管理領(lǐng)域，結(jié)合車聯(lián)網(wǎng)技術(shù)[4]，道路上行駛的每輛車可以看作是一個移動節(jié)點，這樣車聯(lián)網(wǎng)移動節(jié)點聚集檢測技術(shù)可用于對道路交通流量的實時監(jiān)測，及時發(fā)現(xiàn)擁堵路段，協(xié)助管理部門進(jìn)行交通疏導(dǎo)，并可為駕駛員提供合理行車路線；在動物習(xí)性研究中，研究人員將特定的傳感器節(jié)點安裝在研究對象上，通過節(jié)點間的相互協(xié)作組成移動傳感網(wǎng)[5](一種特殊的Ad hoc網(wǎng)絡(luò))，這樣通過判斷傳感網(wǎng)節(jié)點的聚集狀態(tài)可以迅速確定生物種群的棲息地點，并實時監(jiān)測種群的運動狀態(tài)和各種生理信息。上述應(yīng)用中，行人、車輛和動物本質(zhì)上都是無線節(jié)點的移動載體，它們聚集狀態(tài)監(jiān)測可通過移動節(jié)點聚集檢測技術(shù)來實現(xiàn)。

目前，關(guān)于移動節(jié)點聚集狀態(tài)監(jiān)測的傳統(tǒng)方法主要有人工統(tǒng)計、機(jī)械統(tǒng)計、電子計數(shù)、射頻識別等[6]，但這些方法普遍存在應(yīng)用范圍受限、實時性較差、系統(tǒng)建設(shè)成本高等問題，不適用于節(jié)點數(shù)目較多或目標(biāo)區(qū)域開放的情況。近年來，基于圖像識別的群體密度識別方法[7]逐漸興起，理想情況下這種方法可以實現(xiàn)群體密度全天時和全覆蓋統(tǒng)計，但實際中其受環(huán)境條件的影響較大(例如晚間判定效果較差)，且存在選點布控復(fù)雜、設(shè)施投資較大、實時性差、計算復(fù)雜度高等問題，此方法的工程化應(yīng)用前景有待進(jìn)一步探討。

為解決現(xiàn)有方法存在的問題，提高移動節(jié)點聚集檢測的效率和準(zhǔn)確度，本文提出一種基于位置感知的移動節(jié)點聚集檢測方法，在利用無線定位技術(shù)獲得節(jié)點位置的基礎(chǔ)上，通過網(wǎng)格劃分和密度聚類的方式對節(jié)點的聚集狀態(tài)進(jìn)行檢測，當(dāng)存在節(jié)點數(shù)目較多的聚集簇時，可快速輸出節(jié)點聚集區(qū)域的位置信息。本方法計算復(fù)雜度低、準(zhǔn)確度高且實時較好，可滿足多種應(yīng)用領(lǐng)域?qū)σ苿庸?jié)點聚集狀態(tài)監(jiān)測的需求。

1　無線定位技術(shù)

在進(jìn)行節(jié)點聚集狀態(tài)或范圍檢測之前，首先需要收集目標(biāo)區(qū)域內(nèi)節(jié)點的位置信息，而移動節(jié)點位置的感知可借助無線定位技術(shù)來實現(xiàn)。無線定位技術(shù)主要利用無線信號的某些參數(shù)特征來判斷節(jié)點的絕對/相對位置，根據(jù)定位結(jié)果類型的不同，可分為物理定位和符號定位兩種[8]，前者需要得到被定位目標(biāo)具體的物理位置，如(39°55′45.79″N, 116°26′27.56″E)，后者僅需得到定位目標(biāo)的符號位置或相對位置，如“某個節(jié)點在工人體育場中”或者“某個節(jié)點在場館正門前方10米處”。在實際應(yīng)用中，兩種定位結(jié)果可以相互轉(zhuǎn)化，例如在人群聚集監(jiān)測(交通監(jiān)測)中，可根據(jù)高密度人群(車輛)所處的物理位置，迅速確定人群聚集(交通擁堵)發(fā)生的建筑物(街區(qū))，從而協(xié)助相關(guān)人員進(jìn)行快速響應(yīng)。

根據(jù)定位過程中所使用的無線信號參數(shù)特征的不同，定位技術(shù)也可分為基于接收信號強(qiáng)度(Received Signal Strength Indication, RSSI)的定位、基于到達(dá)時間(Time of Arrival, TOA)的定位、基于到達(dá)時間差(Time Difference of Arrival, TDOA)的定位、基于到達(dá)角度(Angle of Arrival, AOA)的定位等。前面三種定位技術(shù)首先需要通過RSSI、TOA或TDOA方法估計出節(jié)點間的距離，當(dāng)然待定位節(jié)點可以獲得自身到3個(二維定位)或4個(三維定位)參考節(jié)點(自身位置已知的節(jié)點)的距離后，就可以采用一定的數(shù)學(xué)方法計算出自身的位置坐標(biāo)。在某些場合下，當(dāng)待定位節(jié)點測距范圍內(nèi)的參考節(jié)點數(shù)量不足時，可采用節(jié)點間的最小多跳距離來代替歐式距離[9]。以圖1為例，待定位節(jié)點O可直接測量出自身到參考節(jié)點A、B、C的距離分別為do1、do2和do3，由于參考節(jié)點D不在節(jié)點O的測距范圍內(nèi)，兩者之間的距離do4可通過OE和ED的距離和(多跳距離)來近似，即do4≈doe+ded。

圖1　節(jié)點定位示意圖

記參考節(jié)點A、B、C、D的位置坐標(biāo)分別為X1, X2, X3, X4，這樣可建立求解待定位節(jié)點坐標(biāo)Xo的歐式方程組(其中n= 4)：

(1)

求解上述方程組采用最廣泛的方法是最小二乘(Least Square, LS)算法，LS算法在節(jié)點間的距離估計誤差服從均值為0的高斯分布時，所得到的估計值是的極大似然最優(yōu)估計。當(dāng)距離估計誤差分布的均值不為0(有偏差)時[10]，可采用有偏最小二乘法來計算待定位節(jié)點的坐標(biāo)估計值：

(2)

其中，n為參考節(jié)點的數(shù)目，b為距離估計誤差分布的均值。

2　節(jié)點聚集檢測方法

當(dāng)獲得目標(biāo)區(qū)域內(nèi)移動節(jié)點的位置信息后，可借鑒基于網(wǎng)格和密度的聚類方法[11, 12]來檢測節(jié)點的聚集狀態(tài)；如果存在密度較高的節(jié)點聚集簇時，則輸出節(jié)點聚集的區(qū)域范圍。具體方法包括三個主要步驟：

步驟一、對目標(biāo)區(qū)域進(jìn)行網(wǎng)格劃分。首先，確定長方形子網(wǎng)格長度和寬度取值，基于此將目標(biāo)區(qū)域均勻劃分為J子網(wǎng)格Gk(j=1, 2, …,J)；當(dāng)目標(biāo)區(qū)域不規(guī)則時，可根據(jù)其邊界坐標(biāo)將其擴(kuò)展為一個規(guī)則的長方形區(qū)域，然后再對其進(jìn)行網(wǎng)格劃分；在此過程中，將不足一個網(wǎng)格面積的子區(qū)域當(dāng)作一個子網(wǎng)格；最后，統(tǒng)計并記錄每個子網(wǎng)格中的移動節(jié)點ID和位置信息。

步驟二、通過密度聚類方式搜索每個子網(wǎng)格中的節(jié)點聚集簇。首先，統(tǒng)計出每個子網(wǎng)格中節(jié)點的密度信息(每個節(jié)點鄰域內(nèi)包含的其他節(jié)點數(shù)目)，找出核心節(jié)點(自身密度不低于閾值T的節(jié)點)和次核心節(jié)點(處于核心節(jié)點鄰域內(nèi)但自身密度小于閾值T的節(jié)點)；然后，從任意核心節(jié)點開始，通過密度聚類的方式找出一個完整的節(jié)點聚集簇；當(dāng)核心節(jié)點遍歷完全后，輸出子網(wǎng)格中所有節(jié)點聚集簇的信息。具體步驟如下：

① 設(shè)定節(jié)點鄰域半徑ε和密度閾值T；

② 計算目標(biāo)區(qū)域內(nèi)所有節(jié)點Na的密度ma；當(dāng)Na處于子網(wǎng)格邊界附近時，需要同時統(tǒng)計其所處子網(wǎng)格和相鄰子網(wǎng)格中的所有相鄰節(jié)點來計算密度ma；如果ma≥T，則Na為核心節(jié)點，并將Na標(biāo)記為未處理的核心節(jié)點；設(shè)定迭代次數(shù)j= 1；

③ 對于子網(wǎng)格Gj，取Gj中節(jié)點聚集簇數(shù)目Fj=0；

④ 判斷子網(wǎng)格Gj中是否存在未處理的核心節(jié)點；如果Gj中存在未處理的核心節(jié)點，取Fj=Fj+ 1，轉(zhuǎn)到下一步；如果不存在未處理的核心節(jié)點，轉(zhuǎn)到步驟⑨；

⑤ 取子網(wǎng)格Gj中的任意未處理的核心節(jié)點Na，將Na和其鄰域內(nèi)的所有節(jié)點歸于同一個簇CFj，并將Na標(biāo)記為已處理的核心節(jié)點；

⑥ 搜索簇CFj中未處理的核心節(jié)點，將其鄰域內(nèi)的所有節(jié)點添加到簇CFj中；

⑦ 重復(fù)步驟⑥，直到簇CFj中的所有核心節(jié)點都被標(biāo)記為已處理的核心節(jié)點；

⑧ 完成簇CFj的擴(kuò)展，轉(zhuǎn)到步驟④；

⑨ 完成子網(wǎng)格Gj的搜索；如果Fj>0，輸出Gj的所有節(jié)點聚集簇及聚集簇數(shù)目Fj；

⑩ 取j=j+1，如果j≤J，轉(zhuǎn)到步驟③；否則，結(jié)束子網(wǎng)格中節(jié)點聚集簇的搜索。

步驟三、對節(jié)點相鄰聚集簇進(jìn)行合并。統(tǒng)計出每個子網(wǎng)格中的節(jié)點聚集簇之后，根據(jù)簇中核心節(jié)點間的連通度關(guān)系確定相鄰子網(wǎng)格中的節(jié)點相鄰聚集簇，并對其進(jìn)行合并。其中，節(jié)點相鄰聚集簇是指存在連通核心節(jié)點的一對節(jié)點聚集簇，而連通核心節(jié)點是指自身鄰域包含對方且自身又處于對方鄰域內(nèi)的一對核心節(jié)點。

最后，輸出目標(biāo)區(qū)域內(nèi)節(jié)點數(shù)目大于一定閾值的節(jié)點聚集簇Ck的區(qū)域信息[XCk,lCk,wCk] (k= 1, 2, …,K)及Ck所包含節(jié)點的ID。其中，XCk表示聚集簇Ck所在的長方形區(qū)域的中心坐標(biāo)，lCk和wCk分別表示此區(qū)域的長度和寬度。

3　仿真驗證

本部分通過仿真試驗來驗證論文方法的有效性。如圖2所示，在1000×1000的目標(biāo)區(qū)域內(nèi)部署200個移動節(jié)點(節(jié)點ID分別為1-200)，所有節(jié)點在某一時刻的位置坐標(biāo)可通過無線定位技術(shù)來獲得，本試驗主要在位置已知的情況下對節(jié)點的聚集狀態(tài)進(jìn)行檢測。試驗中，目標(biāo)區(qū)域被劃分的子網(wǎng)格數(shù)目J=4，即子網(wǎng)格{Ga, Gb, Gc, Gd}的邊長都為500；密度聚類時，取節(jié)點鄰域半徑ε=50和密度閾值T=4。

圖2　節(jié)點分布示意圖

在圖2所示的節(jié)點分布情況下，各子網(wǎng)格共檢測到6個節(jié)點聚集簇(長方形子區(qū)域)，記作{C1, C2, C3, C4, C5, C6}，如圖3所示。在子網(wǎng)格Ga中，檢測到1個節(jié)點聚集簇C1，其區(qū)域信息為[(477.9, 521.6) ,40.8, 39.7]，包含8個節(jié)點；在子網(wǎng)格Gb中，檢測到2個節(jié)點聚集簇C2和C3，區(qū)域信息分別為[(535.2, 542.2), 83.4, 59.4]和[(592.7, 744.3), 61.9, 61.8]，分別包含9個和5個節(jié)點；在子網(wǎng)格Gc中，檢測到的2個節(jié)點聚集簇C4和C5的區(qū)域信息分別為[(26.2, 408.7), 70.3, 38.5]和[(458.6, 471.8), 55.4, 77.0]，分別包含5個和20個節(jié)點；在子網(wǎng)格Gd中，僅檢測到1個節(jié)點聚集簇C6，區(qū)域信息為[(524.9, 446.4) ,105.3, 46.9]，包含19個節(jié)點。

圖3　各子網(wǎng)格檢測到的節(jié)點聚集簇示意圖

當(dāng)檢測出每個子網(wǎng)格中的節(jié)點聚集簇后，可對相鄰子網(wǎng)格中的節(jié)點相鄰聚集簇進(jìn)行合并。在圖3中，節(jié)點聚集簇C1, C2, C5和C6的地理位置相鄰，且之間存在連通核心節(jié)點，因此，可將這四個簇合并成一個大簇Cfinal(如圖4所示)，其他兩個簇C3和C4保持不變。Cfinal所在區(qū)域的中心為(492.5, 488.8)，接近目標(biāo)區(qū)域的中心，區(qū)域的長度和寬度分別約為190.1和144.8。圖5為Cfinal所在區(qū)域的放大圖，這個簇共包括56個節(jié)點，其ID分別為{1, 3, 14, 18, 22, 27, 29, 32, 34, 38, 44, 46, 47, 49, 52, 55, 58, 61, 65, 67, 68, 70, 75, 78, 79, 91, 95, 96, 101, 104, 111, 112, 113, 114, 117, 119, 126, 127, 131, 132, 136, 140, 141, 142, 144, 147, 148, 160, 165, 169, 170, 171, 175, 184, 185, 194}。

圖4　節(jié)點相鄰聚集簇合并結(jié)果圖

圖5　節(jié)點聚集區(qū)域示意圖

4　結(jié)　語

移動節(jié)點聚集檢測技術(shù)在公共安全、交通管理、生物監(jiān)測等領(lǐng)域具有廣闊的應(yīng)用前景。隨著無線網(wǎng)絡(luò)技術(shù)的發(fā)展，無線定位技術(shù)逐漸成熟。利用無線定位技術(shù)所提供的位置估計信息，提出一種基于網(wǎng)格劃分和密度聚類的一種移動節(jié)點聚集感知方法。節(jié)點位置能否準(zhǔn)確感知對本方法有效性的影響較大，為提升無線定位的精度，可采用有偏最小二乘法來計算節(jié)點坐標(biāo)的估計值。本方法計算復(fù)雜度低、速度快且準(zhǔn)確度較高，在目標(biāo)區(qū)域較大或移動節(jié)點數(shù)目較多的應(yīng)用場景下具有更顯著的優(yōu)勢。如何降低無線定位誤差對于本方法的影響是下一階段研究要考慮的問題之一。

[1]汪濤. 無線網(wǎng)絡(luò)技術(shù)導(dǎo)論[M]. 北京: 清華大學(xué)出版社, 2008.

[2]胡杰, 張興, 王文博. 無線網(wǎng)絡(luò)中的業(yè)務(wù)行為及業(yè)務(wù)容量—概念、模型及發(fā)展[J]. 中國電子科學(xué)研究院學(xué)報, 2012, 7(2): 168-173.

[3]張仕學(xué), 李石君, 余偉, 等. 突發(fā)事件人群異常聚集熱點區(qū)域預(yù)測[J]. 中國安全科學(xué)學(xué)報, 2015, 25(9): 159-164.

[4]汪成亮, 張晨. 面向車聯(lián)網(wǎng)的交通流參數(shù)檢測[J]. 2012, 48(23): 212-218.

[5]孫利民, 李建中, 陳渝等. 無線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005.

[6]胡成, 李偉, 姚曉暉. 為了這樣的災(zāi)難不再發(fā)生—城市人群聚集風(fēng)險的監(jiān)測與預(yù)警[J]. 科技智囊, 2011, 1: 74-79.

[7]常慶龍, 夏洪山. 利用歸一化前景和二維聯(lián)合熵的人群聚集檢測方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2013, 9(38): 1126-1130.

[8]Hightower J, Boriello G. Location Systems for Ubiquitous Computing. Computer, 2001, 34(8): 57-66.

[9]Niculescu D, Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems, 2003, 22(1/4): 267-280.

[10]Picard J S, Weiss A J. Localization of Networks Using Various Ranging Bias Models[J]. Wireless Communications and Mobile Computing, 2008, 8(5): 553-562.

[11]賀玲, 吳玲達(dá), 蔡益朝. 數(shù)據(jù)挖掘中的聚類算法綜述[J]. 計算機(jī)應(yīng)用研究, 2007, 1: 10-13.

[12]Han J, Kamber M, Pei J. Data Mining: Concepts and Techniques, Third Edition[M]. Burlington: Morgan Kaufmann, 2011.

郭曉雷(1983—)，男，河北人，博士，主要研究方向為網(wǎng)絡(luò)與信息系統(tǒng)等；E-mail：guoxiaolei247@hotmail.com

秘建寧(1979—)，男，河北人，博士，主要研究方向為信息系統(tǒng)總體設(shè)計技術(shù)等；

張宇(1987—)，男，吉林人，主要研究方向為通信網(wǎng)絡(luò)仿真等；

張欣海(1975—)，男，遼寧人，高級工程師，主要研究方向為數(shù)據(jù)挖掘技術(shù)等。

Study on the Location-aware Based Mobile Node Aggregation Detection Method

GUO Xiao-lei, BI Jian-ning, ZHANG Yu, ZHANG Xin-hai

(China Academy of Electronics and Information Technology, Beijing 100041, China)

Mobile node aggregation detection is a new application of wireless networks. To improve the efficiency and accuracy of node aggregation detection in large area, a location-aware and density clustering based detection method is proposed. Firstly, the location coordinates of mobile nodes are obtained by wireless localization technology, in which, the biased least square method can be used to reduce the effect of distance estimation errors on localization. Secondly, the target area is divided into several sub-grids. On the basis, density clustering approach is utilized to search node aggregation clusters. Then, the aggregation clusters with neighboring core nodes in adjacent grids are merged into a bigger one. Finally, the regional information and relevant nodes of aggregation clusters are outputted as detection results. Simulation experiments demonstrate the effectiveness and application feasibility of the proposed method.

Node Aggregation Detection；Wireless Localization；Cluster Analysis

10.3969/j.issn.1673-5692.2016.04.016

2016-06-09

2016-07-20

TP393

A

1673-5692(2016)04-425-05