摘  要： DV-Hop算法適用于礦下節(jié)點(diǎn)分布不均勻的環(huán)境,，現(xiàn)有對(duì)DV-Hop算法的改進(jìn)大多數(shù)是為了減少定位過(guò)程中的誤差。提出了一種在DV-Hop算法基礎(chǔ)上用縮小定位范圍的方法來(lái)提高定位精度的方法,，該算法保留了DV-Hop算法節(jié)點(diǎn)間通信量少的優(yōu)點(diǎn),，適合礦下的網(wǎng)絡(luò)場(chǎng)景。仿真結(jié)果表明,，改進(jìn)后的算法大大提高了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位精度,。
關(guān)鍵詞： DV-Hop；無(wú)線傳感器網(wǎng)絡(luò),；煤礦,；人員定位

    隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，通信技術(shù)及無(wú)線定位技術(shù)也迅速發(fā)展起來(lái),。伴隨信息時(shí)代的到來(lái),，無(wú)線定位技術(shù)被廣泛應(yīng)用于人員定位、救援等領(lǐng)域,。我國(guó)礦難頻繁發(fā)生,，這為國(guó)家和人民帶來(lái)了巨大的損失，所以礦下救援成為國(guó)家和煤礦企業(yè)非常重視的一個(gè)問(wèn)題,。礦下救援主要是對(duì)礦下人員的救援,，其過(guò)程主要是確定礦下人員的準(zhǔn)確位置。無(wú)線定位技術(shù)的發(fā)展為礦下救援帶來(lái)了方便,，它能大大加快救援速度?，F(xiàn)有的定位技術(shù)在實(shí)際應(yīng)用中還有待研究，為了進(jìn)一步改善其技術(shù),，定位算法的選擇至關(guān)重要?，F(xiàn)有的定位算法有基于距離的算法（RSSI,、TOA/TDOA和AOA）和非基于距離的算法（質(zhì)心、DV-Hop,、APIT,、Amorphous、凸規(guī)劃）,。
    DV-Hop節(jié)點(diǎn)定位算法由于對(duì)信標(biāo)節(jié)點(diǎn)比例要求較少,，定位精度較高，從而可大大降低網(wǎng)絡(luò)的布置成本,。以往對(duì)DV-Hop算法的改進(jìn)有：結(jié)合ZigBee技術(shù)來(lái)組建無(wú)線通信網(wǎng)絡(luò),；與加權(quán)質(zhì)心相結(jié)合；與RSSI算法結(jié)合等,。文本在分析DV-Hop算法的誤差成因后,，在保留其算法簡(jiǎn)單、不依賴于測(cè)距誤差優(yōu)點(diǎn)的基礎(chǔ)上對(duì)其進(jìn)行了改進(jìn),。本文根據(jù)礦上地理位置進(jìn)行劃分范圍,，以縮小查找未知節(jié)點(diǎn)的單位來(lái)提高定位精度。
1 DV-Hop定位算法
1.1 DV-Hop算法的基本思想
    DV- Hop算法由Niculescu等人提出,，其基本思想是將未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的距離用兩者之間的跳數(shù)和最近錨節(jié)點(diǎn)的平均跳距的乘積表示, 當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或更多錨節(jié)點(diǎn)的距離時(shí)進(jìn)行三邊測(cè)量定位,。其具體過(guò)程分為以下三步：
    (1)通過(guò)節(jié)點(diǎn)之間的信息交換，使網(wǎng)絡(luò)中的每個(gè)未知節(jié)點(diǎn)獲取到信標(biāo)節(jié)點(diǎn)的最小跳數(shù),。
    (2)在已知信標(biāo)節(jié)點(diǎn)的位置和它們到未知節(jié)點(diǎn)的最小跳數(shù)后，利用式（1）計(jì)算出網(wǎng)絡(luò)中平均每跳的距離,，然后計(jì)算未知節(jié)點(diǎn)到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離,。
    


1.3 現(xiàn)有改進(jìn)的DV-Hop算法
    參考文獻(xiàn)[2]中，王新生等人提出了使用多個(gè)錨節(jié)點(diǎn)估算的平均跳距并且采用加權(quán)平均跳距代替?zhèn)鹘y(tǒng)算法中的平均跳距的改進(jìn)算法,。參考文獻(xiàn)[3]中,，沈明玉等提出了一種基于平均跳距和估計(jì)距離的改進(jìn)的DV-Hop算法。該算法考慮了未知節(jié)點(diǎn)到參考節(jié)點(diǎn)的路徑與參考節(jié)點(diǎn)間的路徑可能存在重合或部分重合這一特性,對(duì)平均跳距進(jìn)行修改,并利用誤差對(duì)距離進(jìn)行修正,。參考文獻(xiàn)[4]～[5]中,，周小波、呂振等提出了基于RSSI的改進(jìn)型DV-Hop算法,。
2 改進(jìn)DV-Hop算法
    對(duì)提高定位精度的一個(gè)有效方法就是縮小查找范圍,，從而減小定位誤差。以往的算法應(yīng)用于整個(gè)區(qū)域,，而本文是將所有的節(jié)點(diǎn)進(jìn)行分類,，將查找的區(qū)域分成多塊，再在未知節(jié)點(diǎn)所在的那塊區(qū)域應(yīng)用DV-Hop算法來(lái)確定未知節(jié)點(diǎn)的位置,。具體步驟如下：
    (1)將礦下整個(gè)區(qū)域看成是一個(gè)長(zhǎng)方形,，那么未知節(jié)點(diǎn)就在這個(gè)長(zhǎng)方形范圍內(nèi),。把信標(biāo)節(jié)點(diǎn)均勻分布在這個(gè)長(zhǎng)方形區(qū)域內(nèi)，使其整個(gè)區(qū)域都能被信號(hào)覆蓋(此區(qū)域內(nèi)的每個(gè)節(jié)點(diǎn)至少能接收到1個(gè)信標(biāo)節(jié)點(diǎn)廣播的信號(hào)),。
    (2)導(dǎo)致DV-Hop算法定位精度不高的一個(gè)主要原因就是對(duì)平均跳距的計(jì)算存在很大的誤差,，本文利用RSSI測(cè)距技術(shù)來(lái)計(jì)算平均跳距。
    未知節(jié)點(diǎn)收集鄰節(jié)點(diǎn)信息,，選出RSSI最小值并確定此值所屬的信標(biāo)節(jié)點(diǎn),。如果這個(gè)信標(biāo)節(jié)點(diǎn)在邊界上，則另外選出與這個(gè)信標(biāo)節(jié)點(diǎn)最相鄰的3個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)成一個(gè)新的區(qū)域,；如果這個(gè)信標(biāo)節(jié)點(diǎn)在其內(nèi)部,，則選出與這個(gè)信標(biāo)節(jié)點(diǎn)最相鄰的4個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)成一個(gè)新的四邊形區(qū)域。
    (3)以9個(gè)信標(biāo)節(jié)點(diǎn)為例,，位置分別在長(zhǎng)方形的頂點(diǎn),、中心和四邊的中點(diǎn)處,如圖2所示。如果測(cè)出RSSI最小值信標(biāo)節(jié)點(diǎn)是1,，則選擇1,、2、8,、9或1,、7、8,、9四個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)成四邊形區(qū)域(一般礦下是非常窄的通道,，選1、7,、8,、9比較合理)；如果是2,，則選取1,、3、9三個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)成三角形區(qū)域,；如果是9,，則選取2、4,、6,、8這樣的信標(biāo)節(jié)點(diǎn)構(gòu)成四邊形區(qū)域。

    (4)對(duì)已知坐標(biāo)的節(jié)點(diǎn)進(jìn)行歸類,。歸類方法：判定已知節(jié)點(diǎn)是否在新構(gòu)成的多邊形區(qū)域內(nèi),，若在，則保留這個(gè)節(jié)點(diǎn)作為新的信標(biāo)節(jié)點(diǎn),；否則放棄,。如圖2所示,，可以把已知節(jié)點(diǎn)歸類到A、B,、C,、D四個(gè)區(qū)域中。
    (5)在未知節(jié)點(diǎn)所在的區(qū)域中,，把已知信息的未知節(jié)點(diǎn)當(dāng)做信標(biāo)節(jié)點(diǎn),，采用基本DV-Hop算法來(lái)確定未知節(jié)點(diǎn)的位置。
3 實(shí)驗(yàn)及仿真結(jié)果
    為了驗(yàn)證本文算法的可行性,，使用Matlab7.0作為仿真工具進(jìn)行仿真,，并對(duì)仿真結(jié)果進(jìn)行分析。仿真環(huán)境是在100 m×100 m的正方形范圍內(nèi)[6],，隨機(jī)產(chǎn)生191個(gè)未知傳感器網(wǎng)絡(luò)節(jié)點(diǎn)和9個(gè)確定的信標(biāo)節(jié)點(diǎn),，節(jié)點(diǎn)的通信距離為15 m。仿真結(jié)果數(shù)據(jù)取自20次仿真的平均值,。初始節(jié)點(diǎn)分布圖如圖3所示,。
    縮小范圍后，節(jié)點(diǎn)分布圖如圖4所示,。

    節(jié)點(diǎn)分類后,，保留4個(gè)固定的信標(biāo)節(jié)點(diǎn)，其余54個(gè)未知節(jié)點(diǎn)隨機(jī)分布,。其中,，也可將在其范圍內(nèi)的已知節(jié)點(diǎn)當(dāng)做新的信標(biāo)節(jié)點(diǎn)，這樣可大大提高對(duì)未知節(jié)點(diǎn)的定位精度,。
    當(dāng)把隨機(jī)給出的未知節(jié)點(diǎn)分類后,，得出54個(gè)未知節(jié)點(diǎn)，在其范圍內(nèi)隨機(jī)定義5個(gè)已知的鄰節(jié)點(diǎn)和4個(gè)固定的信標(biāo)節(jié)點(diǎn)作為新的信標(biāo)節(jié)點(diǎn),。圖5所示為在縮小的范圍內(nèi)當(dāng)有9個(gè)信標(biāo)節(jié)點(diǎn)、54個(gè)未知節(jié)點(diǎn)時(shí),，每個(gè)未知節(jié)點(diǎn)的誤差,。

    圖6是在通信距離為50 m時(shí)的平均定位誤差圖,，從圖中可以看出隨著信標(biāo)節(jié)點(diǎn)的增加,，未知節(jié)點(diǎn)的定位誤差會(huì)相對(duì)減少,。與原始的DV-Hop算法相比,，改進(jìn)后的算法定位誤差減少了近20%。改進(jìn)后將4個(gè)固定節(jié)點(diǎn)當(dāng)做是信標(biāo)節(jié)點(diǎn),，然后隨著隨機(jī)增加信標(biāo)節(jié)點(diǎn)來(lái)確定定位誤差,。以信標(biāo)節(jié)點(diǎn)占全部節(jié)點(diǎn)的比例作為圖中的橫坐標(biāo)，以未知節(jié)點(diǎn)的平均誤差作為縱坐標(biāo),。

    介于礦下的特殊環(huán)境，本文介紹了一種基于DV-Hop的改進(jìn)后的節(jié)點(diǎn)定位算法,，在保留傳統(tǒng)DV-Hop算法計(jì)算簡(jiǎn)單、通信開(kāi)銷小的優(yōu)點(diǎn)的基礎(chǔ)上,，用縮小定位范圍的方法來(lái)提高定位精度。本文先對(duì)未知節(jié)點(diǎn)進(jìn)行模糊定位,，確定未知節(jié)點(diǎn)在哪塊區(qū)域內(nèi),，再把已知坐標(biāo)的節(jié)點(diǎn)當(dāng)成信標(biāo)節(jié)點(diǎn)進(jìn)行分類,，最后在縮小定位范圍內(nèi)使用DV-Hop算法對(duì)未知節(jié)點(diǎn)進(jìn)行定位。實(shí)驗(yàn)結(jié)果證明,，此方法大大提高了定位精度，很適合于煤礦快速查找人員所在的位置,。
參考文獻(xiàn)
[1] 倪海燕，應(yīng)祥岳,，簡(jiǎn)家文,，等.無(wú)線傳感器網(wǎng)絡(luò)的自身定位算法研究[J].寧波大學(xué)學(xué)報(bào)，2009,，22(1)：7-11.
[2] 王新生，趙衍靜,，李海濤.基于DV-Hop定位算法的改進(jìn)研究[J].計(jì)算機(jī)科學(xué),，2011，38(2)：76-78.
[3] 沈明玉,，張寅.基于改進(jìn)的平均跳距和估計(jì)距離的DV-Hop定位算法[J].計(jì)算機(jī)應(yīng)用研究,，2011,，28(2)：648-650.
[4] 周小波，喬鋼柱,，曾建潮.無(wú)線傳感器網(wǎng)絡(luò)中基于RSSI的加權(quán)DV-HOP定位方法[J].計(jì)算機(jī)工程與應(yīng)用,，2011,，18(4)：93-96.
[5] 呂振,，李亞杰，孫延飛,，等.基于DV-Hop的修正和改進(jìn)定位算法[J].傳感器與微系統(tǒng)，2008,，29(8)：31-33.
[6] 楊小瑩，張萬(wàn)禮,，房愛(ài)東.一種改進(jìn)的DV-Hop定位算法[J].宿州學(xué)院學(xué)報(bào)，2011,，18(4)：23-25.