新型的熱點簇中心定位算法及其應用

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

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

1 引言

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

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

2 最大簇中心定位算法原理及存在的問題

2.1 MCCS定位原理

MCCS算法[13]中包含3種節點：交換節點、參考節點和移動節點。其中，交換節點和參考節點的位置是固定且已知的。交換節點周期性廣播含有自己ID數據分組，參考節點和移動節點接收并檢測該廣播信號的強度，再將包含此信號強度數據和自己的ID的數據分組發送給交換節點，這里假設無線信號覆蓋區域為一個正圓。MCCS定位系統的結構原理如圖1所示，圖1(a)為MCCS算法以一個交換節點為中心的結構原理圖。·表示參考節點，□表示移動節點，表示交換節點，是等信號圓，表示能接收到與移動節點接收到交換節點信號強度相同的位置。按上述規則，當定位區域中存在3個交換節點時，情況如圖 1(b)所示。根據無線信號的傳播規律，所有交換節點所產生的定位輔助線（處于等信號圓兩側的 2個參考節點，用一根短實線連接，這就是定位輔助線）越靠近移動節點就變得越密集。MCCS算法認為，定位輔助線會在移動節點四周形成一個封閉的矩形簇。雖然在定位區域的其他部分也有可能會形成封閉的矩形簇，但是移動節點附近的定位輔助線一定是最密集的。其判斷方法為，2個參考節點之間的定位輔助線每出現一次，它的權重加1，簇的權重等于組成它的定位輔助線的權重之和。

圖1 MCCS定位系統的結構和原理

MCCS算法的定位機理為：利用節點信號數據，確定所有的定位輔助線位置，再由定位輔助線的分布確定定位區域中全部的簇，找出權重最大的簇，并以其質心位置作為移動節點的位置。

2.2 MCCS定位存在的問題

雖然MCCS算法邏輯清晰簡潔，且對硬件的依賴小，但是該算法存在定位計算量過大和定位盲點等問題，需要進一步改進和完善。

1) 歸類算法計算復雜度過大

MCCS算法在進行定位時，會分別對每一個交換節點所產生的全部定位輔助線的權重進行計算。由于定位輔助線在定位區域中分布廣泛，這就相當于對所有的參考節點進行反復的計算，而實際中其實關系到移動節點定位的定位輔助線只有其中很小的一部分。MCCS算法消耗了很多不必要的計算量，非常耗時耗能，嚴重影響了定位的實時性和定位設備的壽命。

2) 定位盲點

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

圖2 MCCS定位歸類錯誤

上述原因限制了 MCCS算法的工程應用，因此，在此基礎上研究一種改進的定位算法是十分必要的。

3 熱點簇中心定位算法（HSCCS）

為克服 MCCS算法存在的定位計算量過大和定位盲點等問題，在MCCS算法的基礎上，提出了一種新型的熱點簇中心定位算法（HSCCS）。

3.1 HSCCS算法定位原理

HSCCS算法為了實現更精確、更高效、更節能的定位，設計了3個主要的定位階段。MCCS算法中的歸類錯誤是由簇的劃分不正確引起的。在HSCCS算法中，為修正這個錯誤，規定定位區域中所有只包含4個參考節點的矩形區域都是簇。這樣一來，即使定位輔助線不能圍成封閉的矩形，這個區域在定位時也不會被忽略，在全部的簇中找出權重最大的簇的定位階段，稱為簇匹配。MCCS算法中的定位盲點是由于定位時只考慮區域性定位，沒有考慮定位區域中獨立的點。在HSCCS算法中，將每個參考節點本身的位置信息作為一個直接定位依據用于定位過程，這樣就可以用點定位過程來彌補區域性定位對特殊點定位的誤差，這個階段稱為點匹配。MCCS算法中過大的計算量是因為定位時總是把整個定位區域中的所有數據全部帶入定位計算。在HSCCS算法中，當定位計算開始時，會在定位區域中預先劃定一個移動節點可能存在的區域，這樣劃分就省去了對定位區域中移動節點根本不可能存在的區域的定位計算，降低了計算復雜度，這個階段稱為劃分熱點區。

圖3為定位原理圖，在圖3中，·是參考節點，A、B、C是交換節點，熱點簇區域用▲表示，M1和M2是待定位的移動節點，虛線是參考節點相對于各個交換節點的等信號圓。HSCCS算法主要階段的原理如下。

圖3 HSCCS定位算法定位原理

1) 劃分熱點區。在定位開始后，首先利用信號強度（RSSI值）檢測所有交換節點與移動節點的距離。如圖3(a)所示，距離移動節點最近的C為核心交換節點，距離移動節點最遠的交換節點A為界標交換節點。因為距離移動節點最近的交換節點的等信號線在定位區域中經過的簇是最少的，所以令被核心交換節點C等信號線經過的簇區域稱為熱點簇。又因為，如果移動節點不在定位區域中，如M2所在的位置，那么界標交換節點A的等信號線完全不會經過熱點簇。這個依據用來判斷移動節點是否處于定位區域外。

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

3) 簇匹配。簇匹配的方法與最大簇中心定位算法基本相同，在熱點簇中找到權重最大的簇，以這個簇的質心為移動節點位置。但是，當找到的最重簇為2個有公共邊的等重簇時，根據中心極限法則，認為這2個等重簇組成的矩形的質心為移動節點位置。

3.2 HSCCS算法設計

在定位過程中，當某一個移動節點需要定位時，該移動節點將定位請求與自身可能接收到的各個交換節點的信號強度發給距離該節點最近的交換節點，定位過程如下。

設所需要定位的移動節點為X，令B={b1,…,bn}是X所能檢測到的全部的交換節點，X接收到對應這些交換節點的信號強度為＜μ1,…,μn＞，D={d1,…,dn}是定位區域中的所有的參考節點，對于任意dx∈D所接受到這些交換節點的信號強度為＜μ(b1,dx),…,μ(bn,dx)＞，已知一般距離——衰減模型[15]如下：

其中，Pa(l)為經過距離l后交換節點信號的衰減量，Pa(l0)為經過參考距離l0后交換節點的信號強度，n為路徑衰減因子，表征衰減量隨距離的增加而增長的速度，x為遮蔽因子，是個零均值的高斯隨機變量。與交換節點相距l的某一節點接收到交換節點的信號強度Pr(l)則可表示為

其中，Pt為交換節點發射信號強度。在已知節點接收到交換節點的信號強度Pr(l)時，距離l可由式（3）計算。

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

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

1) 確定2個關鍵的交換節點。如果當i=1,…,n時，有μopt＞μi,μopt∈＜μ1,…,μn＞，那么對于移動節點來說，bopt為核心交換節點；當i=1,…,n時，有μwst＜μi,μwst∈＜μ1,…,μn＞，那么對于移動節點來說，bwst為界標交換節點，并計算出點匹配上下門限值U(μwst)和D(μwst)，設接近圓半徑為參考節點行列間距Ld的一半Ld/2，那么有：

2) 確定定位區域中的所有熱點。當bopt對定位區域中任意一組du,dv有：

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

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

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

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

5) 進行熱點簇權重的計算。對所有的du,dv,du∈HD,dv∈HD，且i=1,…,n時有：

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

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

4 仿真實驗

4.1 定位效果實驗

假定定位區域為一塊50m×50m的正方形平面區域，參考節點均勻布散，間隔為 5m，交換節點處在定位區域的4個頂點處，信號強度值（RSSI）由IEEE 802.15.4給出的簡化信道模型式（2）進行計算。各種條件下定位效果仿真數據如表1所示。

表1 各種條件下定位效果仿真數據

數值仿真結果表明：HSCCS算法可以精確地定位處于特殊位置的移動節點（如圖4（a）和圖4（b）所示），有效地消除定位盲點；同時也能準確分辨處于定位區域之外的移動節點（如圖4（d）所示）。

4.2 定位精度和能耗分析

為了比較MCCS算法與HSCCS算法的定位精度和能耗，在第4.1節定位效果數值仿真實驗環境下，將一定數量的參考節點均勻散布在這個區域中，在每一種散布狀況下移動節點隨機移動 500次。對比使用3個交換節點時新舊2種算法的定位誤差與定位所需的節點采樣次數（節點采樣次數大小反映算法能耗的大小）。對比實驗結果如圖5所示。

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

5 HSCCS算法在井下環境中的工程實現

在煤礦井下環境的無線傳感器網絡定位中，最大的問題就是無線信號的傳播會受環境的影響，衰減快、多徑效應等都是這種影響的具體體現。而井下環境對無線信號最大的影響就是巖壁會完全阻斷無線信號的傳播，這種情況在信號發射功率很低的ZigBee網絡中體現的尤為明顯。

圖4 HSCCS算法的定位仿真結果

圖5 定位精度和能耗實驗結果對比

對于信號的衰減和多徑效應問題，目前常用的解決方案就是多次測量信號強度，并取平均值，事實證明這種方法非常簡便而且在消除這類影響方面是非常有效的[15,16]。但是，巖壁對信號的阻斷是無法直接解決的。常規的無線局域網定位算法一般都是把定位區域作為一個整體進行定位，而這種方式在井下環境中是基本不可能實現的。所以，本文對HSCCS算法在井下環境中的工作模式設計如下。

如圖6所示，圖中陰影部分表示煤礦井下巖壁，空白區域為礦道；黑色圓點代表交換節點，六角形點表示ZigBee網絡協調器。借助于HSCCS算法的熱點區域劃分和移動節點所在區域判別特性，可以把礦道區域分成A、B、C3個區域分別進行局部定位。每個區域中的交換節點在所在區域中使用HSCCS算法對移動節點進行相對定位，再利用自己的絕對坐標把定位出的相對坐標轉化為整個井下區域中的絕對坐標。這樣，就可以在交換節點信號無法覆蓋整個定位區域時進行定位了。

圖6 HSCCS井下應用

在節點的部署問題上，如圖6所示，每個定位區域中都必須有交換節點能與其他區域中的交換節點進行直線通信，如此一來，不同區域中的節點定位數據就可以由這些交換節點逐跳地傳輸給ZigBee網絡協調器，并最終傳輸給上位機。而且，區域與區域交界處的交換節點必須盡量密集的布設，預留一定數量的冗余節點，以應對大量的數據通信及其帶來的能量消耗。

6 結束語

本文設計了一種熱點簇中心定位算法。這種算法對移動節點的定位只需要依據無線電信號的強度，所需要的設備簡單，定位無盲點，且定位精度和定位時間都可由用戶自行調整。只要保證定位區域始終被 2個以上交換節點的信號覆蓋，定位就可以進行。本文所提出的定位算法已應用于煤礦井下人員定位系統中。

[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] 張治斌, 徐小玲, 閻連龍.無線傳感器網絡人員定位算法[J].煤炭學報, 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] 馬震, 劉云, 沈波. 分布式無線傳感器網絡定位算法 MDSMAP(D)[J]. 通信學報, 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] 王福豹, 史龍, 任豐原. 無線傳感器網絡中的自身定位系統和算法[J].軟件學報, 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] 曾凡仔, 孫正章, 羅娟等. 無線傳感器網絡的節點定位方法[J].通信學報, 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網絡的定位跟蹤研究與實現[D]. 上海：同濟大學, 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.