新型的熱點(diǎn)簇中心定位算法及其應(yīng)用

周少武，黃博微，曾照福，周明輝，詹杰

（湖南科技大學(xué) 信息與電氣工程學(xué)院，湖南 湘潭 411201）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)定位算法有測(cè)距（range-based）定位法和非測(cè)距（range-free）定位法。測(cè)距定位法需要利用節(jié)點(diǎn)上的傳感器測(cè)量移動(dòng)節(jié)點(diǎn)與交換節(jié)點(diǎn)之間的距離或角度信息，然后用三邊測(cè)量法等[1]計(jì)算移動(dòng)節(jié)點(diǎn)的位置。而非測(cè)距定位法則無(wú)需測(cè)量移動(dòng)節(jié)點(diǎn)與交換節(jié)點(diǎn)之間的距離或角度，僅需根據(jù)網(wǎng)絡(luò)連通性、信號(hào)強(qiáng)度等信息實(shí)現(xiàn)節(jié)點(diǎn)的定位[2]。雖然一般來(lái)說(shuō)測(cè)距定位法在定位的精確性上要高于非測(cè)距定位法，不過(guò)這種精確性是建立在高成本的硬件設(shè)備的基礎(chǔ)上的，而且，礦山井下環(huán)境復(fù)雜多變，在各種復(fù)雜的地形或者空氣中的不同成分、不同濕度的影響下測(cè)量的參數(shù)越多越容易因信號(hào)的衰減和多徑效應(yīng)[3]而引入誤差。在這點(diǎn)上，非測(cè)距定位法卻有著極大的優(yōu)勢(shì)，由于不需要測(cè)得精確的距離，硬件設(shè)備的成本將大大降低，方便于大面積安裝，而定位的精度也可以由算法來(lái)提高。目前，常用的非測(cè)距定位算法有凸規(guī)劃[4]、DV-Hop[5]、MDS-MAP[6,7]等。但是，凸規(guī)劃算法要求定位網(wǎng)絡(luò)中發(fā)出廣播信號(hào)的參考節(jié)點(diǎn)位于網(wǎng)絡(luò)邊緣，否則節(jié)點(diǎn)位置估算會(huì)向網(wǎng)絡(luò)中心偏移。這個(gè)要求對(duì)礦山井下復(fù)雜地形中的網(wǎng)絡(luò)布設(shè)十分不利；而DV-Hop算法則僅在各項(xiàng)同性的密集網(wǎng)絡(luò)中才能正確地進(jìn)行定位[8]。所謂各項(xiàng)同性，就是指信號(hào)強(qiáng)度不因?yàn)闇y(cè)定的方向不同而改變，而在礦山井下因?yàn)闅怏w濃度，巖層成分等的影響，各項(xiàng)同性這個(gè)條件是難以保證的。而MDS-MAP要求整個(gè)網(wǎng)絡(luò)有很好的連通性，而且在網(wǎng)絡(luò)中必須有能進(jìn)行高強(qiáng)度計(jì)算的節(jié)點(diǎn)。在礦山井下各個(gè)工作面之間的節(jié)點(diǎn)通信很難保證，而且要在每一個(gè)工作面配置高性能節(jié)點(diǎn)，成本將會(huì)非常高。由于井下的工作人員或器械的運(yùn)動(dòng)速度一般比較慢，故本文與移動(dòng)節(jié)點(diǎn)的定位[9]情況不同，為靜態(tài)節(jié)點(diǎn)的定位。在無(wú)線技術(shù)的選擇方面，比起用于長(zhǎng)距離識(shí)別，且需要固定安裝的有源RFID系統(tǒng)[10]和用于高速運(yùn)動(dòng)中通信，耗能高且網(wǎng)絡(luò)規(guī)模不大的ad hoc[11]技術(shù)，ZigBee[12]技術(shù)具有組網(wǎng)方便，低功耗，網(wǎng)絡(luò)規(guī)模大等優(yōu)勢(shì)，更適合煤礦井下人員定位，故選擇基于ZigBee技術(shù)構(gòu)建定位算法。JIN M H等[13]提出了一種基于 ZigBee的最大簇中心定位算法（MCCS, maximal-cluster centered scheme），該算法利用節(jié)點(diǎn)信號(hào)強(qiáng)度信息，確定所有的定位輔助線位置，再由定位輔助線的分布確定定位區(qū)域中全部的簇，找出權(quán)重最大的簇，并以其質(zhì)心位置作為移動(dòng)節(jié)點(diǎn)的位置，但該算法存在定位計(jì)算量過(guò)大和定位盲點(diǎn)等問(wèn)題。

本文針對(duì)已有定位算法存在的問(wèn)題和礦山復(fù)雜的工況條件，提出了一種基于 ZigBee的熱點(diǎn)簇中心定位算法（HSCCS, hot spot cluster centered scheme），數(shù)值仿真的結(jié)果表明了該算法的有效性。

2 最大簇中心定位算法原理及存在的問(wèn)題

2.1 MCCS定位原理

MCCS算法[13]中包含3種節(jié)點(diǎn)：交換節(jié)點(diǎn)、參考節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)。其中，交換節(jié)點(diǎn)和參考節(jié)點(diǎn)的位置是固定且已知的。交換節(jié)點(diǎn)周期性廣播含有自己ID數(shù)據(jù)分組，參考節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)接收并檢測(cè)該廣播信號(hào)的強(qiáng)度，再將包含此信號(hào)強(qiáng)度數(shù)據(jù)和自己的ID的數(shù)據(jù)分組發(fā)送給交換節(jié)點(diǎn)，這里假設(shè)無(wú)線信號(hào)覆蓋區(qū)域?yàn)橐粋€(gè)正圓。MCCS定位系統(tǒng)的結(jié)構(gòu)原理如圖1所示，圖1(a)為MCCS算法以一個(gè)交換節(jié)點(diǎn)為中心的結(jié)構(gòu)原理圖?！け硎緟⒖脊?jié)點(diǎn)，□表示移動(dòng)節(jié)點(diǎn)，表示交換節(jié)點(diǎn)，是等信號(hào)圓，表示能接收到與移動(dòng)節(jié)點(diǎn)接收到交換節(jié)點(diǎn)信號(hào)強(qiáng)度相同的位置。按上述規(guī)則，當(dāng)定位區(qū)域中存在3個(gè)交換節(jié)點(diǎn)時(shí)，情況如圖 1(b)所示。根據(jù)無(wú)線信號(hào)的傳播規(guī)律，所有交換節(jié)點(diǎn)所產(chǎn)生的定位輔助線（處于等信號(hào)圓兩側(cè)的 2個(gè)參考節(jié)點(diǎn)，用一根短實(shí)線連接，這就是定位輔助線）越靠近移動(dòng)節(jié)點(diǎn)就變得越密集。MCCS算法認(rèn)為，定位輔助線會(huì)在移動(dòng)節(jié)點(diǎn)四周形成一個(gè)封閉的矩形簇。雖然在定位區(qū)域的其他部分也有可能會(huì)形成封閉的矩形簇，但是移動(dòng)節(jié)點(diǎn)附近的定位輔助線一定是最密集的。其判斷方法為，2個(gè)參考節(jié)點(diǎn)之間的定位輔助線每出現(xiàn)一次，它的權(quán)重加1，簇的權(quán)重等于組成它的定位輔助線的權(quán)重之和。

圖1 MCCS定位系統(tǒng)的結(jié)構(gòu)和原理

MCCS算法的定位機(jī)理為：利用節(jié)點(diǎn)信號(hào)數(shù)據(jù)，確定所有的定位輔助線位置，再由定位輔助線的分布確定定位區(qū)域中全部的簇，找出權(quán)重最大的簇，并以其質(zhì)心位置作為移動(dòng)節(jié)點(diǎn)的位置。

2.2 MCCS定位存在的問(wèn)題

雖然MCCS算法邏輯清晰簡(jiǎn)潔，且對(duì)硬件的依賴小，但是該算法存在定位計(jì)算量過(guò)大和定位盲點(diǎn)等問(wèn)題，需要進(jìn)一步改進(jìn)和完善。

1) 歸類算法計(jì)算復(fù)雜度過(guò)大

MCCS算法在進(jìn)行定位時(shí)，會(huì)分別對(duì)每一個(gè)交換節(jié)點(diǎn)所產(chǎn)生的全部定位輔助線的權(quán)重進(jìn)行計(jì)算。由于定位輔助線在定位區(qū)域中分布廣泛，這就相當(dāng)于對(duì)所有的參考節(jié)點(diǎn)進(jìn)行反復(fù)的計(jì)算，而實(shí)際中其實(shí)關(guān)系到移動(dòng)節(jié)點(diǎn)定位的定位輔助線只有其中很小的一部分。MCCS算法消耗了很多不必要的計(jì)算量，非常耗時(shí)耗能，嚴(yán)重影響了定位的實(shí)時(shí)性和定位設(shè)備的壽命。

2) 定位盲點(diǎn)

當(dāng)移動(dòng)節(jié)點(diǎn)移動(dòng)到定位區(qū)域中某些特定區(qū)域時(shí)，MCCS算法會(huì)無(wú)法正確找出移動(dòng)節(jié)點(diǎn)所在的簇，這樣的現(xiàn)象稱為歸類錯(cuò)誤。MCCS算法用簇這個(gè)概念對(duì)定位區(qū)域進(jìn)行了劃分，一類是移動(dòng)節(jié)點(diǎn)可能存在的區(qū)域，就是存在簇的區(qū)域；另一類是移動(dòng)節(jié)點(diǎn)不可能存在的區(qū)域，這些區(qū)域沒(méi)有簇存在。然后比較每個(gè)簇的權(quán)重，找到權(quán)重最大的簇，并計(jì)算出定位結(jié)果。但是，有時(shí)也會(huì)出現(xiàn)例外的情況，如圖 2所示。在參考節(jié)點(diǎn)的位置，無(wú)線信號(hào)的強(qiáng)度，外界的干擾等因素的共同作用下，移動(dòng)節(jié)點(diǎn)附近的定位輔助線可能無(wú)法全部正確生成。移動(dòng)節(jié)點(diǎn)左邊和右邊的都沒(méi)有封閉的矩形區(qū)域形成，這樣一來(lái)，MCCS算法中簇的生成條件無(wú)法滿足，使得定位無(wú)法正確進(jìn)行，這樣就出現(xiàn)了盲點(diǎn)。同樣也是由于簇的歸類，當(dāng)移動(dòng)節(jié)點(diǎn)處于距離某一參考節(jié)點(diǎn)比較近的位置時(shí)，雖然沒(méi)有簇能很好地包含移動(dòng)節(jié)點(diǎn)所處的區(qū)域，但是MCCS算法依然會(huì)把移動(dòng)節(jié)點(diǎn)的位置定位到某個(gè)簇的質(zhì)心。這樣的情況下，定位雖然能夠進(jìn)行，但會(huì)造成很大的定位誤差。

圖2 MCCS定位歸類錯(cuò)誤

上述原因限制了 MCCS算法的工程應(yīng)用，因此，在此基礎(chǔ)上研究一種改進(jìn)的定位算法是十分必要的。

3 熱點(diǎn)簇中心定位算法（HSCCS）

為克服 MCCS算法存在的定位計(jì)算量過(guò)大和定位盲點(diǎn)等問(wèn)題，在MCCS算法的基礎(chǔ)上，提出了一種新型的熱點(diǎn)簇中心定位算法（HSCCS）。

3.1 HSCCS算法定位原理

HSCCS算法為了實(shí)現(xiàn)更精確、更高效、更節(jié)能的定位，設(shè)計(jì)了3個(gè)主要的定位階段。MCCS算法中的歸類錯(cuò)誤是由簇的劃分不正確引起的。在HSCCS算法中，為修正這個(gè)錯(cuò)誤，規(guī)定定位區(qū)域中所有只包含4個(gè)參考節(jié)點(diǎn)的矩形區(qū)域都是簇。這樣一來(lái)，即使定位輔助線不能圍成封閉的矩形，這個(gè)區(qū)域在定位時(shí)也不會(huì)被忽略，在全部的簇中找出權(quán)重最大的簇的定位階段，稱為簇匹配。MCCS算法中的定位盲點(diǎn)是由于定位時(shí)只考慮區(qū)域性定位，沒(méi)有考慮定位區(qū)域中獨(dú)立的點(diǎn)。在HSCCS算法中，將每個(gè)參考節(jié)點(diǎn)本身的位置信息作為一個(gè)直接定位依據(jù)用于定位過(guò)程，這樣就可以用點(diǎn)定位過(guò)程來(lái)彌補(bǔ)區(qū)域性定位對(duì)特殊點(diǎn)定位的誤差，這個(gè)階段稱為點(diǎn)匹配。MCCS算法中過(guò)大的計(jì)算量是因?yàn)槎ㄎ粫r(shí)總是把整個(gè)定位區(qū)域中的所有數(shù)據(jù)全部帶入定位計(jì)算。在HSCCS算法中，當(dāng)定位計(jì)算開始時(shí)，會(huì)在定位區(qū)域中預(yù)先劃定一個(gè)移動(dòng)節(jié)點(diǎn)可能存在的區(qū)域，這樣劃分就省去了對(duì)定位區(qū)域中移動(dòng)節(jié)點(diǎn)根本不可能存在的區(qū)域的定位計(jì)算，降低了計(jì)算復(fù)雜度，這個(gè)階段稱為劃分熱點(diǎn)區(qū)。

圖3為定位原理圖，在圖3中，·是參考節(jié)點(diǎn)，A、B、C是交換節(jié)點(diǎn)，熱點(diǎn)簇區(qū)域用▲表示，M1和M2是待定位的移動(dòng)節(jié)點(diǎn)，虛線是參考節(jié)點(diǎn)相對(duì)于各個(gè)交換節(jié)點(diǎn)的等信號(hào)圓。HSCCS算法主要階段的原理如下。

圖3 HSCCS定位算法定位原理

1) 劃分熱點(diǎn)區(qū)。在定位開始后，首先利用信號(hào)強(qiáng)度（RSSI值）檢測(cè)所有交換節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)的距離。如圖3(a)所示，距離移動(dòng)節(jié)點(diǎn)最近的C為核心交換節(jié)點(diǎn)，距離移動(dòng)節(jié)點(diǎn)最遠(yuǎn)的交換節(jié)點(diǎn)A為界標(biāo)交換節(jié)點(diǎn)。因?yàn)榫嚯x移動(dòng)節(jié)點(diǎn)最近的交換節(jié)點(diǎn)的等信號(hào)線在定位區(qū)域中經(jīng)過(guò)的簇是最少的，所以令被核心交換節(jié)點(diǎn)C等信號(hào)線經(jīng)過(guò)的簇區(qū)域稱為熱點(diǎn)簇。又因?yàn)?，如果移?dòng)節(jié)點(diǎn)不在定位區(qū)域中，如M2所在的位置，那么界標(biāo)交換節(jié)點(diǎn)A的等信號(hào)線完全不會(huì)經(jīng)過(guò)熱點(diǎn)簇。這個(gè)依據(jù)用來(lái)判斷移動(dòng)節(jié)點(diǎn)是否處于定位區(qū)域外。

2) 點(diǎn)匹配。在簇匹配之前，先比較熱點(diǎn)簇區(qū)域中每一個(gè)參考節(jié)點(diǎn)接收到交換節(jié)點(diǎn)的信號(hào)強(qiáng)度與移動(dòng)節(jié)點(diǎn)接收到的交換節(jié)點(diǎn)的信號(hào)強(qiáng)度，如果能找到唯一的參考節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)完全匹配，或者，當(dāng)移動(dòng)節(jié)點(diǎn)接收到交換節(jié)點(diǎn)的信號(hào)強(qiáng)度與某個(gè)參考節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度足夠近似時(shí)，就認(rèn)為移動(dòng)節(jié)點(diǎn)在這個(gè)參考節(jié)點(diǎn)的位置，具體實(shí)現(xiàn)方法如圖3(b)所示。這里說(shuō)的信號(hào)強(qiáng)度足夠近似，其實(shí)就是移動(dòng)節(jié)點(diǎn)與某個(gè)參考節(jié)點(diǎn)距離很近，設(shè)這個(gè)距離為dv。那么在以移動(dòng)節(jié)點(diǎn)M為圓心，以dv為半徑的這個(gè)“接近圓”中如果有參考節(jié)點(diǎn)，則點(diǎn)匹配成功。確定“接近圓”的方法如下：使各交換節(jié)點(diǎn)的等信號(hào)線圓向外擴(kuò)展dv，再向內(nèi)收縮dv，那么這幾個(gè)交換節(jié)點(diǎn)等信號(hào)圓變化后的圓環(huán)所圍的公共區(qū)域，可以近似等于“接近圓”，這個(gè)公共區(qū)域稱為點(diǎn)匹配區(qū)域。由IEEE 802.15.4[14]給出的信號(hào)傳播模型，可以從移動(dòng)節(jié)點(diǎn)接收到某個(gè)交換節(jié)點(diǎn)的信號(hào)強(qiáng)度推算出，這個(gè)參考節(jié)點(diǎn)與交換節(jié)點(diǎn)之間的距離增加dv和減少dv后的信號(hào)強(qiáng)度值，就是點(diǎn)匹配的上下門限值。為了使點(diǎn)匹配區(qū)域盡可能小于等于“接近圓”，選擇參考節(jié)點(diǎn)接收到界標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度值來(lái)計(jì)算上下門限值。通過(guò)比較所有的參考節(jié)點(diǎn)接收到交換節(jié)點(diǎn)的信號(hào)強(qiáng)度值與移動(dòng)節(jié)點(diǎn)接收到相應(yīng)的交換節(jié)點(diǎn)的信號(hào)強(qiáng)度值之差是否在上下門限值范圍內(nèi)，就可以判斷這個(gè)參考節(jié)點(diǎn)是否足夠接近移動(dòng)節(jié)點(diǎn)，從而完成點(diǎn)匹配任務(wù)。

3) 簇匹配。簇匹配的方法與最大簇中心定位算法基本相同，在熱點(diǎn)簇中找到權(quán)重最大的簇，以這個(gè)簇的質(zhì)心為移動(dòng)節(jié)點(diǎn)位置。但是，當(dāng)找到的最重簇為2個(gè)有公共邊的等重簇時(shí)，根據(jù)中心極限法則，認(rèn)為這2個(gè)等重簇組成的矩形的質(zhì)心為移動(dòng)節(jié)點(diǎn)位置。

3.2 HSCCS算法設(shè)計(jì)

在定位過(guò)程中，當(dāng)某一個(gè)移動(dòng)節(jié)點(diǎn)需要定位時(shí)，該移動(dòng)節(jié)點(diǎn)將定位請(qǐng)求與自身可能接收到的各個(gè)交換節(jié)點(diǎn)的信號(hào)強(qiáng)度發(fā)給距離該節(jié)點(diǎn)最近的交換節(jié)點(diǎn)，定位過(guò)程如下。

設(shè)所需要定位的移動(dòng)節(jié)點(diǎn)為X，令B={b1,…,bn}是X所能檢測(cè)到的全部的交換節(jié)點(diǎn)，X接收到對(duì)應(yīng)這些交換節(jié)點(diǎn)的信號(hào)強(qiáng)度為＜μ1,…,μn＞，D={d1,…,dn}是定位區(qū)域中的所有的參考節(jié)點(diǎn)，對(duì)于任意dx∈D所接受到這些交換節(jié)點(diǎn)的信號(hào)強(qiáng)度為＜μ(b1,dx),…,μ(bn,dx)＞，已知一般距離——衰減模型[15]如下：

其中，Pa(l)為經(jīng)過(guò)距離l后交換節(jié)點(diǎn)信號(hào)的衰減量，Pa(l0)為經(jīng)過(guò)參考距離l0后交換節(jié)點(diǎn)的信號(hào)強(qiáng)度，n為路徑衰減因子，表征衰減量隨距離的增加而增長(zhǎng)的速度，x為遮蔽因子，是個(gè)零均值的高斯隨機(jī)變量。與交換節(jié)點(diǎn)相距l(xiāng)的某一節(jié)點(diǎn)接收到交換節(jié)點(diǎn)的信號(hào)強(qiáng)度Pr(l)則可表示為

其中，Pt為交換節(jié)點(diǎn)發(fā)射信號(hào)強(qiáng)度。在已知節(jié)點(diǎn)接收到交換節(jié)點(diǎn)的信號(hào)強(qiáng)度Pr(l)時(shí)，距離l可由式（3）計(jì)算。

在IEEE 802.15.4給出的信號(hào)傳播模型中，Pt、Pa(l0)、l0、x都為已知，所以，信號(hào)強(qiáng)度和距離都可估算出來(lái)。

在HSCCS算法設(shè)計(jì)中，信號(hào)強(qiáng)度μ可用式(2)計(jì)算（用函數(shù)μ=RSSI(L)表示），L為兩點(diǎn)之間的距離，距離L可用式(3)計(jì)算（用函數(shù)L=Length(μ)表示），du,dv為 2個(gè)相鄰的參考節(jié)點(diǎn)，du∈D,dv∈D,HD={hd1,…,hdn}，為熱點(diǎn)參考節(jié)點(diǎn)，HD?D，S={s1…sn}，為所有連接du,dv的定位輔助線，其權(quán)重表示為Ws={ws1,…,wsn}，C={c1,…,cn}為定位區(qū)域中所有由4個(gè)參考節(jié)點(diǎn)構(gòu)成的最小矩形區(qū)域，這里把 它們 都作 為簇 ，ci=＜Di,Si＞,Di?D,Si?S,HC={hc1,…,hcn}，為熱點(diǎn)簇，HC?C，其權(quán)重表示為WHC={whc1,…,whcn}。

1) 確定2個(gè)關(guān)鍵的交換節(jié)點(diǎn)。如果當(dāng)i=1,…,n時(shí)，有μopt＞μi,μopt∈＜μ1,…,μn＞，那么對(duì)于移動(dòng)節(jié)點(diǎn)來(lái)說(shuō)，bopt為核心交換節(jié)點(diǎn)；當(dāng)i=1,…,n時(shí)，有μwst＜μi,μwst∈＜μ1,…,μn＞，那么對(duì)于移動(dòng)節(jié)點(diǎn)來(lái)說(shuō)，bwst為界標(biāo)交換節(jié)點(diǎn)，并計(jì)算出點(diǎn)匹配上下門限值U(μwst)和D(μwst)，設(shè)接近圓半徑為參考節(jié)點(diǎn)行列間距Ld的一半Ld/2，那么有：

2) 確定定位區(qū)域中的所有熱點(diǎn)。當(dāng)bopt對(duì)定位區(qū)域中任意一組du,dv有：

如果連接這組du,dv的定位輔助線為sx，那么所有的cx?sx都是熱點(diǎn)簇，所有的hdx?cx都是熱點(diǎn)參考節(jié)點(diǎn)，對(duì)定位區(qū)域中所有的du,dv用式(6)判斷，就可得出定位區(qū)域中的HD和HC。

3) 驗(yàn)證X是否在定位區(qū)域中。若對(duì)任意一組du,dv,du∈HD,dv∈HD，有：

那么X在定位區(qū)域中，定位繼續(xù)；若沒(méi)有一組du,dv,du∈HD,dv∈HD符合式(7),那么X不在定位區(qū)域中，定位結(jié)束。

4) 進(jìn)行點(diǎn)匹配。若有U(μwst)+Δ＜|μ(bi,dx)-μi|＜D(μwst)+Δ,hdx∈HD，那么hdx的位置就是移動(dòng)節(jié)點(diǎn)的位置，定位結(jié)束，反之，定位繼續(xù)。這里Δ是一個(gè)誤差修正量，用來(lái)平衡井下環(huán)境因素干擾給定位造成的影響，可根據(jù)不同的井下環(huán)境，干擾因素的大小進(jìn)行不同的修正。

5) 進(jìn)行熱點(diǎn)簇權(quán)重的計(jì)算。對(duì)所有的du,dv,du∈HD,dv∈HD，且i=1,…,n時(shí)有：

式(8)成立了k次，那么連接這組du,dv的定位輔助線sx的權(quán)重wsx=k，利用式(8)計(jì)算出所有的S?HC,的權(quán)重，又由whc=∑S?HCws，計(jì)算出所有的WHC。

6) 進(jìn)行簇匹配。若有唯一的whcx＞whci,i=1,…,n，那么這個(gè)最重簇hcx的質(zhì)心就是移動(dòng)節(jié)點(diǎn)的位置，定位結(jié)束；如有whcx=whcy＞whci, i=1,…,n，且whcx與whcy為有公共邊的相鄰兩簇，那么取這2個(gè)簇組成的矩形的質(zhì)心為移動(dòng)節(jié)點(diǎn)的位置，定位結(jié)束。

4 仿真實(shí)驗(yàn)

4.1 定位效果實(shí)驗(yàn)

假定定位區(qū)域?yàn)橐粔K50m×50m的正方形平面區(qū)域，參考節(jié)點(diǎn)均勻布散，間隔為 5m，交換節(jié)點(diǎn)處在定位區(qū)域的4個(gè)頂點(diǎn)處，信號(hào)強(qiáng)度值（RSSI）由IEEE 802.15.4給出的簡(jiǎn)化信道模型式（2）進(jìn)行計(jì)算。各種條件下定位效果仿真數(shù)據(jù)如表1所示。

表1 各種條件下定位效果仿真數(shù)據(jù)

數(shù)值仿真結(jié)果表明：HSCCS算法可以精確地定位處于特殊位置的移動(dòng)節(jié)點(diǎn)（如圖4（a）和圖4（b）所示），有效地消除定位盲點(diǎn)；同時(shí)也能準(zhǔn)確分辨處于定位區(qū)域之外的移動(dòng)節(jié)點(diǎn)（如圖4（d）所示）。

4.2 定位精度和能耗分析

為了比較MCCS算法與HSCCS算法的定位精度和能耗，在第4.1節(jié)定位效果數(shù)值仿真實(shí)驗(yàn)環(huán)境下，將一定數(shù)量的參考節(jié)點(diǎn)均勻散布在這個(gè)區(qū)域中，在每一種散布狀況下移動(dòng)節(jié)點(diǎn)隨機(jī)移動(dòng) 500次。對(duì)比使用3個(gè)交換節(jié)點(diǎn)時(shí)新舊2種算法的定位誤差與定位所需的節(jié)點(diǎn)采樣次數(shù)（節(jié)點(diǎn)采樣次數(shù)大小反映算法能耗的大小）。對(duì)比實(shí)驗(yàn)結(jié)果如圖5所示。

數(shù)值仿真實(shí)驗(yàn)結(jié)果表明：1）MCCS定位算法的定位誤差大約是HSCCS定位算法的2倍左右（如圖5(a)所示），在參考段數(shù)很少的情況下尤為明顯；2）在相同交換節(jié)點(diǎn)的情況下HSCCS定位算法的定位誤差小于MCCS定位算法（如圖5(b)所示）；3）在參考段數(shù)相同的情況下，HSCCS定位算法的節(jié)點(diǎn)采樣次數(shù)遠(yuǎn)小于MCCS定位算法（如圖5(c)所示）；4）隨著交換節(jié)點(diǎn)數(shù)量的增加，HSCCS定位算法采樣點(diǎn)數(shù)會(huì)同步上升（如圖5(d)所示）。從以上數(shù)值仿真中可以發(fā)現(xiàn)，HSCCS算法無(wú)論從定位的精度還是定位的能耗上都要優(yōu)于MCCS算法。

5 HSCCS算法在井下環(huán)境中的工程實(shí)現(xiàn)

在煤礦井下環(huán)境的無(wú)線傳感器網(wǎng)絡(luò)定位中，最大的問(wèn)題就是無(wú)線信號(hào)的傳播會(huì)受環(huán)境的影響，衰減快、多徑效應(yīng)等都是這種影響的具體體現(xiàn)。而井下環(huán)境對(duì)無(wú)線信號(hào)最大的影響就是巖壁會(huì)完全阻斷無(wú)線信號(hào)的傳播，這種情況在信號(hào)發(fā)射功率很低的ZigBee網(wǎng)絡(luò)中體現(xiàn)的尤為明顯。

圖4 HSCCS算法的定位仿真結(jié)果

圖5 定位精度和能耗實(shí)驗(yàn)結(jié)果對(duì)比

對(duì)于信號(hào)的衰減和多徑效應(yīng)問(wèn)題，目前常用的解決方案就是多次測(cè)量信號(hào)強(qiáng)度，并取平均值，事實(shí)證明這種方法非常簡(jiǎn)便而且在消除這類影響方面是非常有效的[15,16]。但是，巖壁對(duì)信號(hào)的阻斷是無(wú)法直接解決的。常規(guī)的無(wú)線局域網(wǎng)定位算法一般都是把定位區(qū)域作為一個(gè)整體進(jìn)行定位，而這種方式在井下環(huán)境中是基本不可能實(shí)現(xiàn)的。所以，本文對(duì)HSCCS算法在井下環(huán)境中的工作模式設(shè)計(jì)如下。

如圖6所示，圖中陰影部分表示煤礦井下巖壁，空白區(qū)域?yàn)榈V道；黑色圓點(diǎn)代表交換節(jié)點(diǎn)，六角形點(diǎn)表示ZigBee網(wǎng)絡(luò)協(xié)調(diào)器。借助于HSCCS算法的熱點(diǎn)區(qū)域劃分和移動(dòng)節(jié)點(diǎn)所在區(qū)域判別特性，可以把礦道區(qū)域分成A、B、C3個(gè)區(qū)域分別進(jìn)行局部定位。每個(gè)區(qū)域中的交換節(jié)點(diǎn)在所在區(qū)域中使用HSCCS算法對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行相對(duì)定位，再利用自己的絕對(duì)坐標(biāo)把定位出的相對(duì)坐標(biāo)轉(zhuǎn)化為整個(gè)井下區(qū)域中的絕對(duì)坐標(biāo)。這樣，就可以在交換節(jié)點(diǎn)信號(hào)無(wú)法覆蓋整個(gè)定位區(qū)域時(shí)進(jìn)行定位了。

圖6 HSCCS井下應(yīng)用

在節(jié)點(diǎn)的部署問(wèn)題上，如圖6所示，每個(gè)定位區(qū)域中都必須有交換節(jié)點(diǎn)能與其他區(qū)域中的交換節(jié)點(diǎn)進(jìn)行直線通信，如此一來(lái)，不同區(qū)域中的節(jié)點(diǎn)定位數(shù)據(jù)就可以由這些交換節(jié)點(diǎn)逐跳地傳輸給ZigBee網(wǎng)絡(luò)協(xié)調(diào)器，并最終傳輸給上位機(jī)。而且，區(qū)域與區(qū)域交界處的交換節(jié)點(diǎn)必須盡量密集的布設(shè)，預(yù)留一定數(shù)量的冗余節(jié)點(diǎn)，以應(yīng)對(duì)大量的數(shù)據(jù)通信及其帶來(lái)的能量消耗。

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

本文設(shè)計(jì)了一種熱點(diǎn)簇中心定位算法。這種算法對(duì)移動(dòng)節(jié)點(diǎn)的定位只需要依據(jù)無(wú)線電信號(hào)的強(qiáng)度，所需要的設(shè)備簡(jiǎn)單，定位無(wú)盲點(diǎn)，且定位精度和定位時(shí)間都可由用戶自行調(diào)整。只要保證定位區(qū)域始終被 2個(gè)以上交換節(jié)點(diǎn)的信號(hào)覆蓋，定位就可以進(jìn)行。本文所提出的定位算法已應(yīng)用于煤礦井下人員定位系統(tǒng)中。

[1] HIGHTOWER J, BORRIELLO G. Location Sensing Techniques.Technical Report UW CSE 2001-07-30[R]. Seattle: Department of Computer Science and Engineering, University of Washington, 2001.

[2] 張治斌, 徐小玲, 閻連龍.無(wú)線傳感器網(wǎng)絡(luò)人員定位算法[J].煤炭學(xué)報(bào), 2009, 34(1):125-128.ZHANG Z B, XU X L, YAN L L. Personnel localization algorithms for wireless sensor networks[J]. Journal of China Coal Society, 2009,34(1):125-128.

[3] NERGUIZIAN C, DESPINS C L. Radio-channel characterization of an underground mine at 2.4 GHz[A]. IEEE Wireless Communications[C]. 2005. 2441-2453.

[4] DOHERTY L, PISTER K S J, GHAOUI L E. Convex position estimation in wireless sensor networks[A]. Anchorage:IEEE Computer and Communications Societies[C]. 2001. 1655-1663.

[5] NICULESCU D, NATH B.DV based positioning in ad hoc networks[J].Journal of Telecommunication Systems, 2003, 22(1/4): 267-280.

[6] SHANG Y, RUML W, ZHANG Y,et al. Localization from mere connectivity[A]. Proc of the 4th ACM Int’l Symp on Mobile Ad Hoc Networking & Computing[C]. 2003. 201-212.

[7] 馬震, 劉云, 沈波. 分布式無(wú)線傳感器網(wǎng)絡(luò)定位算法 MDSMAP(D)[J]. 通信學(xué)報(bào), 2008, 29(6):57-62.MA Z, LIU Y, SHEN B. Distributed locating algorithm for wireless sensor networks-MDS-MAP(D)[J]. Journal on Communications, 2008,29(6):57-62.

[8] 王福豹, 史龍, 任豐原. 無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào), 2005, 16(5): 857-868.WANG F B, SHI L, REN F Y. Self-localization systems and algorithms for wireless sensor networks[J]. Journal of Software, 2005,16(5): 857-868.

[9] 曾凡仔, 孫正章, 羅娟等. 無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位方法[J].通信學(xué)報(bào), 2008, 29(11):62-66.ZENG F Z, SUN Z Z, LUO J,et al. Improved node localization algorithm for wireless sensor network[J]. Journal on Communications,2008, 29(11):62-66.

[10] HIGHTOWER J, BORIELLO G, WANT R. SpotON: an Indoor 3D Location Sensing Technology Based on RF Signal Strength[R]. Technical Report UW CSE 2000-02-02, Seattle: Department of Computer Science and Engineering, University of Washington, 2000.

[11] NICOLESCU D, NATH B. Ad hoc positioning systems (APS)[A].Proc of the 2001 IEEE Global Telecommunications[C]. SanAntonio,2001. 2926-2931.

[12] ZigBee Alliance. ZigBee Document 053474r13[S]. 2006.

[13] JIN M H, WU E H K, LIAO Y B,et al.802.11-based positioning system for context aware applications[A]. GLOBECOM 2003[C]. 2003. 929-933.

[14] ZigBee Alliance. ZigBee Specification[S]. 2008.

[15] 張潔穎.基于ZigBee網(wǎng)絡(luò)的定位跟蹤研究與實(shí)現(xiàn)[D]. 上海：同濟(jì)大學(xué), 2007.ZHANG J Y. The Research and Implementation of Localization and Tracking in the ZigBee Network[D]. Shanghai: Tongji University,2007.

[16] GON?ALO G, HELENA S. Indoor location system using ZigBee technology[A]. Third International Conference on Sensor Technologies and Applications[C]. 2009. 152-157.