薛 霞，孫 勇

(1.西北大學(xué) 信息學(xué)院，陜西 西安710127;2.北京理工大學(xué)電子安全工程系，北京100081)

0 引言

我國(guó)煤礦安全技術(shù)與裝備水平低，事故隱患多。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)可應(yīng)用于布線(xiàn)和電源供給困難的區(qū)域、人員不能到達(dá)的區(qū)域和一些臨時(shí)場(chǎng)合［1～4］。因此，本文將WSNs應(yīng)用于煤礦安全監(jiān)測(cè)，這將有效地提高了煤礦安全生產(chǎn)的監(jiān)測(cè)水平，并且減少了事故隱患［5］。在煤礦安全監(jiān)測(cè)中，需要知道采集的數(shù)據(jù)信息所對(duì)應(yīng)的具體區(qū)域位置，如對(duì)瓦斯突出，只有快速確認(rèn)瓦斯突出的具體地點(diǎn)，才能及時(shí)采取相應(yīng)的措施，防止事故發(fā)生。因此，研究節(jié)點(diǎn)定位是WSNs的一項(xiàng)重要支撐技術(shù)。

1 WSNs在煤礦安全監(jiān)測(cè)中的基本定位機(jī)制

節(jié)點(diǎn)定位是依靠傳感器網(wǎng)絡(luò)中少量錨節(jié)點(diǎn)的位置信息確定監(jiān)測(cè)區(qū)域中其他未知節(jié)點(diǎn)的位置坐標(biāo)，在傳感器節(jié)點(diǎn)間建立起一定的空間關(guān)系。根據(jù)節(jié)點(diǎn)是否已知自身的位置，把傳感器節(jié)點(diǎn)分為錨節(jié)點(diǎn)和未知節(jié)點(diǎn)。在WSNs中，錨節(jié)點(diǎn)(anchor node)是已知自身精確的位置，且能夠協(xié)助未知節(jié)點(diǎn)進(jìn)行定位;未知節(jié)點(diǎn)(unknown node)是需要進(jìn)行定位的節(jié)點(diǎn)。在一個(gè)節(jié)點(diǎn)的通信半徑內(nèi)，直接通信的節(jié)點(diǎn)稱(chēng)為鄰居節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)擁有的鄰居節(jié)點(diǎn)數(shù)量稱(chēng)為網(wǎng)絡(luò)連通度。

根據(jù)定位機(jī)制的不同，將WSNs自身定位算法分為兩類(lèi):基于測(cè)距(range-based)的定位方法和無(wú)需測(cè)距(rangefree)的定位方法［6］。前者需要測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離或者角度信息，然后使用三邊測(cè)量法、三角測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的位置。后者無(wú)需距離或角度信息，僅根據(jù)網(wǎng)絡(luò)的連通性、跳段估算距離等信息來(lái)確定節(jié)點(diǎn)的位置，具有低功耗、低成本的優(yōu)勢(shì)，且不需硬件支持［7，8］。NiculescuD等人提出的DV-Hop節(jié)點(diǎn)定位算法［9，10］不需要提供額外的硬件，節(jié)點(diǎn)間的通信量低。在煤礦中，WSNs節(jié)點(diǎn)通常按需隨機(jī)分布，因此，節(jié)點(diǎn)的分布不均勻，且不能保證節(jié)點(diǎn)的密度。故在煤礦安全監(jiān)測(cè)中，采用DV-Hop節(jié)點(diǎn)定位算法是一個(gè)可選的方案。本文通過(guò)對(duì)DV-Hop算法的進(jìn)一步改進(jìn)，使得改進(jìn)后的DV-Hop節(jié)點(diǎn)定位算法成為煤礦安全監(jiān)測(cè)的一個(gè)理想方案。

圖1為WSNs的煤礦安全監(jiān)測(cè)區(qū)域，陰影節(jié)點(diǎn)表示未知節(jié)點(diǎn)，空心節(jié)點(diǎn)表示錨節(jié)點(diǎn)，錨節(jié)點(diǎn)個(gè)數(shù)至少必須是3。未知節(jié)點(diǎn)根據(jù)附近的錨節(jié)點(diǎn)或已定位的未知節(jié)點(diǎn)之間的通信，使用某種定位算法計(jì)算自己的坐標(biāo)位置。

圖1 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中煤礦監(jiān)測(cè)的的錨節(jié)點(diǎn)和未知節(jié)點(diǎn)Fig 1 Anchor nodes and unknown nodes of WSNs for coal mine safety monitoring

2 DV-Hop算法及其改進(jìn)

2.1 基本的定位算法

DV-Hop算法，是美國(guó)路特葛斯大學(xué)(Rutgers University)的Niculescu D等人利用距離矢量路由(distance vector routing)和GPS定位原理，提出的其中一種分布式定位算法，它由3個(gè)階段組成。

第1階段，利用距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得自己到錨節(jié)點(diǎn)的跳數(shù)(distance in hops)。錨節(jié)點(diǎn)向距離自己跳數(shù)為1的鄰居節(jié)點(diǎn)廣播自身坐標(biāo)信息與跳數(shù)信息(初始跳數(shù)值為0)。接收節(jié)點(diǎn)僅記錄自己到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。

第2階段，獲得了其他錨節(jié)點(diǎn)坐標(biāo)信息和它們之間的跳距信息，錨節(jié)點(diǎn)計(jì)算平均每跳距離，然后，將這個(gè)跳距矯正值(correction)廣播到網(wǎng)絡(luò)中。錨節(jié)點(diǎn)i的平均每跳距離為

其中，錨節(jié)點(diǎn) i，j的坐標(biāo)分別為(xi，yi)，(xj，yj)，hij為錨節(jié)點(diǎn)i與j(i≠j)之間的跳數(shù)。

錨節(jié)點(diǎn)將平均每跳距離廣播至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的第1個(gè)平均每跳距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。未知節(jié)點(diǎn)接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，可以計(jì)算出到每個(gè)錨節(jié)點(diǎn)的距離。

第3階段，當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或3個(gè)以上錨節(jié)點(diǎn)的距離時(shí)，利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)位置。

圖1所示的情形推廣到了更一般的情況，極大似然估計(jì)法是三邊測(cè)量法的推廣。假設(shè)有n個(gè)錨節(jié)點(diǎn)，其位置坐標(biāo)為(xi，yi)(i=1，2，...，n)，未知節(jié)點(diǎn)坐標(biāo)為(x，y)，要求錨節(jié)點(diǎn)數(shù)n≥3;di為第i個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離，根據(jù)平面內(nèi)兩點(diǎn)間的歐式距離公式，得到以下方程組為

在式(2)中，將前n－1個(gè)等式分別減去第n個(gè)等式，整理成Ax=b的線(xiàn)性方程組形式。其中

使用標(biāo)準(zhǔn)最小二乘法，求得未知節(jié)點(diǎn)坐標(biāo)x的估計(jì)^x。

2.2 改進(jìn)后的定位算法

DV-Hop算法用錨節(jié)點(diǎn)之間的平均每跳距離代替未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的平均每跳距離，未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的距離用每跳跳距×跳數(shù)表示。對(duì)未知節(jié)點(diǎn)進(jìn)行定位時(shí)，只考慮了離未知節(jié)點(diǎn)最近的一個(gè)錨節(jié)點(diǎn)估計(jì)的平均每跳距離，然而單個(gè)錨節(jié)點(diǎn)估計(jì)的平均每跳距離值無(wú)法準(zhǔn)確地反映整個(gè)網(wǎng)絡(luò)的實(shí)際平均每跳距離。為了減小誤差、進(jìn)一步提高定位精度，對(duì)上面算法進(jìn)行了改進(jìn)。改進(jìn)后的定位算法由以下4個(gè)步驟組成:

1)通過(guò)路由協(xié)議，每個(gè)錨節(jié)點(diǎn)采用廣播方式，將其錨節(jié)點(diǎn)的位置、跳數(shù)以及到錨節(jié)點(diǎn)的每跳距離和廣播給其他節(jié)點(diǎn)。當(dāng)某個(gè)錨節(jié)點(diǎn)接收到其他錨節(jié)點(diǎn)的信息時(shí)，便可根據(jù)兩者的位置計(jì)算出兩者之間的實(shí)際距離。根據(jù)實(shí)際距離與每跳距離和的差值，計(jì)算錨節(jié)點(diǎn)i，j之間的總距離誤差校正值Eij。

設(shè)錨節(jié)點(diǎn)i的平均每跳距離為HopDisi，錨節(jié)點(diǎn)i，j(i≠j)之間總共有n跳，dij表示錨節(jié)點(diǎn) i，j間的每跳距離和，Dij表示錨節(jié)點(diǎn)i，j間的實(shí)際距離。計(jì)算總距離誤差校正值Eij

其中，dij=HopDisi×n ，

2)各個(gè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離不同，距離誤差也不同。因此，應(yīng)該采用不同的誤差校正值進(jìn)行計(jì)算。設(shè)錨節(jié)點(diǎn)i，j間的跳數(shù)為n，計(jì)算i到j(luò)的平均每跳誤差校正值eij

各個(gè)錨節(jié)點(diǎn)在網(wǎng)絡(luò)中廣播自己到其他錨節(jié)點(diǎn)的跳數(shù)和距離誤差校正值。因此，錨節(jié)點(diǎn)獲得了其他所有錨節(jié)點(diǎn)的總距離誤差校正值和平均每跳誤差校正值。每個(gè)接收到此數(shù)據(jù)的節(jié)點(diǎn)將此信息記錄到一張表中，然后繼續(xù)向其鄰居廣播(重復(fù)的數(shù)據(jù)包丟棄)。經(jīng)過(guò)了總距離誤差校正和平均每跳誤差校正后，意味著找到了一條到達(dá)錨節(jié)點(diǎn)的更短路徑。

3)經(jīng)過(guò)步驟1和步驟2的廣播，未知節(jié)點(diǎn)得到了距離自己最近的3個(gè)錨節(jié)點(diǎn)的距離誤差校正值，利用這些校正值，獲得自己到錨節(jié)點(diǎn)的距離和計(jì)算自己到各個(gè)錨節(jié)點(diǎn)的實(shí)際距離。

設(shè)未知節(jié)點(diǎn)u在錨節(jié)點(diǎn)i與j之間，N表示未知節(jié)點(diǎn)u到錨節(jié)點(diǎn)i的跳數(shù)，未知節(jié)點(diǎn)u到錨節(jié)點(diǎn)i的每跳距離和用HopDisi×N表示，eij表示i到j(luò)的平均每跳誤差校正值(公式(4))。計(jì)算未知節(jié)點(diǎn)u到錨節(jié)點(diǎn)i的實(shí)際距離Dui為

4)利用三邊測(cè)量法計(jì)算自己的位置坐標(biāo)。

通過(guò)以上的改進(jìn)算法，鄰居節(jié)點(diǎn)只接收節(jié)點(diǎn)轉(zhuǎn)發(fā)的一個(gè)具有最小跳數(shù)的信息，同時(shí)丟棄其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息。因此，丟棄的這些節(jié)點(diǎn)無(wú)法進(jìn)行定位計(jì)算，從而減少了平均定位誤差。

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

利用Matlab7.0對(duì)DV-Hop算法和本文算法進(jìn)行了仿真實(shí)驗(yàn)。假設(shè)某一煤礦安全監(jiān)測(cè)局部無(wú)線(xiàn)傳感器網(wǎng)絡(luò)區(qū)域?yàn)?00m×200m的正方形區(qū)域，隨機(jī)分布400個(gè)節(jié)點(diǎn)，其中，錨節(jié)點(diǎn)數(shù)為30，節(jié)點(diǎn)通信距離為15 m。每種性能的仿真都隨機(jī)運(yùn)行20次，然后取其平均值。

3.1 錨節(jié)點(diǎn)數(shù)與平均定位誤差

在仿真區(qū)域內(nèi)隨機(jī)分布了400個(gè)節(jié)點(diǎn)，如圖2所示，錨節(jié)點(diǎn)數(shù)量較小時(shí)，誤差較大;錨節(jié)點(diǎn)數(shù)增加后，定位誤差快速降低。仿真結(jié)果顯示，在錨節(jié)點(diǎn)數(shù)量較少的情況下，平均定位誤差大約降低了30%。改進(jìn)算法的平均定位誤差小于DV-Hop算法，因?yàn)楦倪M(jìn)算法隨著錨節(jié)點(diǎn)數(shù)的增加，節(jié)點(diǎn)的距離誤差得到了校正。

圖2 錨節(jié)點(diǎn)數(shù)與平均定位誤差Fig 2 Number of anchor nodes and average localization error

3.2 錨節(jié)點(diǎn)數(shù)與定位覆蓋

DV-Hop定位算法和改進(jìn)算法的覆蓋率如圖3所示。隨著錨節(jié)點(diǎn)數(shù)的增加，改進(jìn)算法的定位覆蓋范圍快速達(dá)到了100%。在DV-Hop算法中，當(dāng)錨節(jié)點(diǎn)數(shù)較少時(shí)，有的節(jié)點(diǎn)由于不能找到至少3個(gè)錨節(jié)點(diǎn)，故不能用三邊測(cè)量法計(jì)算坐標(biāo)位置，因此，覆蓋率只有63%左右。從圖中可以看出:改進(jìn)算法在定位覆蓋率方面明顯高于DV-Hop算法。

圖3 定位覆蓋率Fig 3 Localization coverage rate

3.3 錨節(jié)點(diǎn)數(shù)與通信量

在仿真區(qū)域內(nèi)隨機(jī)分布了400個(gè)節(jié)點(diǎn)，如圖4所示，隨著錨節(jié)點(diǎn)數(shù)的增加，2種算法的數(shù)據(jù)包總量都增大，但改進(jìn)算法的增長(zhǎng)低于DV-Hop算法，是因?yàn)椴豢啥ㄎ还?jié)點(diǎn)沒(méi)有參與計(jì)算，從而大大降低了節(jié)點(diǎn)之間的通信開(kāi)銷(xiāo)。

圖4 錨節(jié)點(diǎn)數(shù)量與數(shù)據(jù)包總量Fig 4 Number of anchor nodes and total quantity data pack

3.4 節(jié)點(diǎn)數(shù)與平均定位誤差

在仿真區(qū)域內(nèi)，隨機(jī)分布了1000個(gè)節(jié)點(diǎn)，取30個(gè)為錨節(jié)點(diǎn)。在不同節(jié)點(diǎn)數(shù)的情況下，觀(guān)察DV-Hop算法和改進(jìn)算法的平均定位誤差。如圖5所示:本文算法的平均定位誤差小于DV-Hop算法。在節(jié)點(diǎn)數(shù)量為1000的情況下，本文算法的定位誤差大約是DV-Hop算法的55%左右。平均定位誤差降低，是因?yàn)楸疚乃惴ㄖ械牟豢啥ㄎ还?jié)點(diǎn)不會(huì)參與定位計(jì)算。

圖5 節(jié)點(diǎn)數(shù)與平均定位誤差Fig 5 Number of nodes and average localization error

4 結(jié)論

本文介紹了一種改進(jìn)后的WSNs節(jié)點(diǎn)定位算法。實(shí)際距離用節(jié)點(diǎn)間的跳數(shù)×平均每跳距離代替，通過(guò)引入距離誤差校正值，并且考慮了跳數(shù)的影響，同時(shí)在路徑上實(shí)行距離校正，實(shí)現(xiàn)了節(jié)點(diǎn)的精確定位。改進(jìn)后的DV-Hop算法不僅降低了平均定位誤差，同時(shí)也提高了定位覆蓋率。仿真實(shí)驗(yàn)證明了該方法的有效性。這種新的WSNs節(jié)點(diǎn)定位方法解決了類(lèi)似煤礦這種場(chǎng)景的定位需求，為煤礦的瓦斯突出問(wèn)題提出了一種新的理想解決方案。

［1］Akyildiz IF，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102－114.

［2］尚志軍，曾 鵬，于海斌.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問(wèn)題［J］.計(jì)算機(jī)科學(xué)，2004，31(10):35－38.

［3］Langendoen K，Reijers N.Distributed localization in wireless sensor networks:A quantitative comparison［J］.Computer Networks，2003，43(4):499－518.

［4］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self-organization of a wireless sensor network［J］.IEEE Personal Communications，2000，7(5):16－27.

［5］楊 維，馮錫生，程時(shí)昕，等.新一代全礦井無(wú)線(xiàn)信息系統(tǒng)理論與關(guān)鍵技術(shù)［J］.煤炭學(xué)報(bào)，2004，29(4):506－509.

［6］He T，Huang C D，Blum B M.Range-free localization schemes in large scale sensor networks［C］∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.San Diego:ACM Press，2003:81－95.

［7］王福豹，史 龍，任豐原.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16(5):857－868.

［8］彭 剛，曹元人，孫利民.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位機(jī)制的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40(35):27－29.

［9］Niculescu D，Nath B.Ad Hoc positioning systems［J］.IEEE Communications Society，2001，5:2926－2931.

［10］Niculescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Journal of Telecommunication Systems，2003，22(1/4):267－280.