單個錨節(jié)點(diǎn)的路徑規(guī)劃機(jī)制及定位方法研究

王茂臣，樊秀梅

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)技術(shù)中的關(guān)鍵技術(shù)之一，正確定位是傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)確定感知的事件發(fā)生位置的前提．節(jié)點(diǎn)定位一般是已知錨節(jié)點(diǎn)的位置信息，通過測量其與待定位節(jié)點(diǎn)的距離或者跳數(shù)信息，或者通過確定待定位節(jié)點(diǎn)的所在區(qū)域來實(shí)現(xiàn)定位．為提高定位精度，降低定位成本，利用少量甚至單個錨節(jié)點(diǎn)在待定位節(jié)點(diǎn)的區(qū)域中進(jìn)行移動來獲得待定位節(jié)點(diǎn)的位置信息，研究人員已經(jīng)進(jìn)行了許多基于移動錨節(jié)點(diǎn)的路徑規(guī)劃機(jī)制與定位算法研究．

錨節(jié)點(diǎn)的路徑規(guī)劃機(jī)制按照路徑是否預(yù)先設(shè)定可以分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃．靜態(tài)路徑規(guī)劃是指錨節(jié)點(diǎn)的移動路徑預(yù)先設(shè)定，在定位過程中移動路徑不再改變．Koutsonilas等[1]提出了 SCAN、Double-SCAN及HILBERT的靜態(tài)路徑規(guī)劃機(jī)制，適用于在節(jié)點(diǎn)分布均勻的情況下對節(jié)點(diǎn)進(jìn)行定位，但是存在信標(biāo)點(diǎn)共線性的問題．Huang等[2]通過引入S型路徑代替直線路徑，解決了信標(biāo)點(diǎn)共線性的問題，但是仍然只適用于節(jié)點(diǎn)分布均勻的情況．

由于靜態(tài)路徑規(guī)劃機(jī)制的錨節(jié)點(diǎn)移動路徑預(yù)先設(shè)定，無法適應(yīng)節(jié)點(diǎn)無規(guī)則分布的情況．西南交通大學(xué)的梁甲金[3]提出單個移動錨節(jié)點(diǎn)的動態(tài)路徑規(guī)劃機(jī)制，即禁忌搜索路徑規(guī)劃機(jī)制，使錨節(jié)點(diǎn)可以根據(jù)未知節(jié)點(diǎn)的分布情況實(shí)時改變移動路徑．

在單個移動錨節(jié)點(diǎn)的定位機(jī)制中，將錨節(jié)點(diǎn)的停留點(diǎn)作為信標(biāo)點(diǎn)，信標(biāo)點(diǎn)距離待定位節(jié)點(diǎn)越近，定位就會越準(zhǔn)確．本文在禁忌搜索路徑規(guī)劃機(jī)制的基礎(chǔ)上引入分簇機(jī)制，提出單個移動錨節(jié)點(diǎn)的禁忌搜索與分簇相結(jié)合的動態(tài)路徑規(guī)劃機(jī)制．如果多個待定位節(jié)點(diǎn)之間距離較近，可以作為一簇，錨節(jié)點(diǎn)根據(jù)分簇信息確定簇頭作為錨節(jié)點(diǎn)的目標(biāo)點(diǎn)，即優(yōu)先選擇從一群集中點(diǎn)的中心通過，從而在盡量不增加錨節(jié)點(diǎn)移動距離的情況下，縮短錨節(jié)點(diǎn)與待定位節(jié)點(diǎn)的距離，提高定位的精度．

針對單個移動錨節(jié)點(diǎn)在禁忌搜索與分簇相結(jié)合的路徑規(guī)劃機(jī)制下移動，本文還研究了利用 RSSI測距[4]與 AOA 角度測量[5]相結(jié)合的定位方法，該方法可以定位全部的待定位節(jié)點(diǎn)，定位誤差小于常用的質(zhì)心算法[6]和 DV-HOP 算法[7]．

1 禁忌搜索與分簇相結(jié)合路徑規(guī)劃機(jī)制

禁忌搜索路徑規(guī)劃機(jī)制的基本思想是假定移動錨節(jié)點(diǎn)比未知節(jié)點(diǎn)的通信距離遠(yuǎn)，以網(wǎng)絡(luò)中任意未知點(diǎn)作為起始點(diǎn)向未知節(jié)點(diǎn)移動，其傳播半徑2/3范圍內(nèi)的節(jié)點(diǎn)劃入禁忌集，禁忌集以外的傳播范圍內(nèi)的節(jié)點(diǎn)為邊緣節(jié)點(diǎn)．邊緣節(jié)點(diǎn)將自己通信范圍內(nèi)的禁忌集以外的未知節(jié)點(diǎn)的數(shù)量作為自己的權(quán)重，錨節(jié)點(diǎn)將自己的運(yùn)動前方權(quán)重最大的點(diǎn)作為自己的移動目標(biāo)，如果在運(yùn)動前方找不到邊緣點(diǎn)，就將禁忌集中的次優(yōu)節(jié)點(diǎn)作為移動的目標(biāo)點(diǎn)，從而使錨節(jié)點(diǎn)移動較短的距離覆蓋盡量多的未知節(jié)點(diǎn)，減少了系統(tǒng)開銷．

1.1 禁忌搜索與分簇相結(jié)合路徑規(guī)劃

單個錨節(jié)點(diǎn)的禁忌搜索與分簇相結(jié)合的路徑規(guī)劃機(jī)制的算法步驟是：

(1)在錨節(jié)點(diǎn)進(jìn)入未知區(qū)域進(jìn)行定位之前，未知節(jié)點(diǎn)之間相互通信以確定簇頭．設(shè)簇半徑為 R，每一個節(jié)點(diǎn)計算周圍 R半徑范圍內(nèi)的未知節(jié)點(diǎn)的數(shù)量．若某節(jié)點(diǎn)的周圍節(jié)點(diǎn)數(shù)量多于規(guī)定的數(shù)量 n，則分成一簇，此節(jié)點(diǎn)作為簇頭．將所有簇頭節(jié)點(diǎn)按照各簇內(nèi)節(jié)點(diǎn)數(shù)量從多到少進(jìn)行排序，并放入節(jié)點(diǎn)矩陣 g中．在兩個簇相交叉的情況下，保留節(jié)點(diǎn)數(shù)量多的簇的簇頭．選擇簇頭的程序偽代碼如下：

while g 不為空

i＝1//g中的數(shù)量最多的節(jié)點(diǎn)的編號

cutou＝cutou＋g(i)//將 g中第一個節(jié)點(diǎn)的坐標(biāo)放入簇頭集合cutou中

for j＝2：shuliang //shuliang 為 g 中簇頭節(jié)點(diǎn)的數(shù)量

dis＝distance(g(i)，g(j))//求出剩余節(jié)點(diǎn)與第一個節(jié)點(diǎn)的距離

if d＜＝2*R

g＝g－g(j)//將g(j)點(diǎn)從g中刪除

end

end

g＝g－g(i)//將g(i)點(diǎn)從g中刪除

shuliang＝size(g)

end

經(jīng)過以上程序處理后 cutou中便包含了所有節(jié)點(diǎn)數(shù)量最多且不交叉的簇的簇頭節(jié)點(diǎn)．

(2)確定禁忌集與邊緣集．錨節(jié)點(diǎn)進(jìn)入要定位的區(qū)域，將錨節(jié)點(diǎn)傳播半徑范圍內(nèi)距離錨節(jié)點(diǎn)較近的一定區(qū)域內(nèi)的節(jié)點(diǎn)放入禁忌集，禁忌集以外的覆蓋范圍內(nèi)的節(jié)點(diǎn)為邊緣節(jié)點(diǎn)．為了既能夠?qū)㈠^節(jié)點(diǎn)前方的節(jié)點(diǎn)放入禁忌集，又能夠保證邊緣集中有足夠可選的邊緣點(diǎn)作為目標(biāo)點(diǎn)，應(yīng)該使禁忌集與邊緣集面積相差不大，可以將錨節(jié)點(diǎn)傳播半徑的2/3區(qū)域內(nèi)的節(jié)點(diǎn)劃入禁忌集[3]．

(3)選擇運(yùn)動方向前方(即與前進(jìn)方向的方向向量夾角不超過 90°的區(qū)域)的邊緣節(jié)點(diǎn)作為目標(biāo)點(diǎn)．如圖1所示，錨節(jié)點(diǎn)在b點(diǎn)，錨節(jié)點(diǎn)的前進(jìn)方向?yàn)檎曳剑瑸榱瞬恢貜?fù)覆蓋已經(jīng)經(jīng)過的區(qū)域，應(yīng)該選擇右側(cè)的點(diǎn)作為目標(biāo)點(diǎn)，如圖中的 a點(diǎn)．這些可能目標(biāo)點(diǎn)與錨節(jié)點(diǎn)形成的方向向量與原運(yùn)動方向的夾角最大為90°．

圖1 錨節(jié)點(diǎn)的運(yùn)動方向說明圖Fig.1 Diagram of the movement of the anchor node

(4)確定簇頭點(diǎn)作為錨節(jié)點(diǎn)移動的目標(biāo)點(diǎn)．先在cutou中剔除已經(jīng)被錨節(jié)點(diǎn)覆蓋的簇頭節(jié)點(diǎn)．對cutou中剩余的簇頭點(diǎn)，按順序計算其分別與搜索到的前進(jìn)方向范圍內(nèi)的每一個邊緣點(diǎn)的距離．如果cutou中有簇頭點(diǎn)與前進(jìn)方向范圍內(nèi)的某一個邊緣點(diǎn)的距離小于或等于 R，則將其作為一個可能的目標(biāo)點(diǎn)．如果有兩個或兩個以上這樣的簇頭節(jié)點(diǎn)，則將簇內(nèi)節(jié)點(diǎn)數(shù)量最多的簇頭點(diǎn)作為錨節(jié)點(diǎn)移動的目標(biāo)點(diǎn)；如果多個簇頭節(jié)點(diǎn)的簇內(nèi)節(jié)點(diǎn)數(shù)量最多且相同，則將它們坐標(biāo)的平均值作為錨節(jié)點(diǎn)移動的目標(biāo)點(diǎn)．

(5)如果邊緣集內(nèi)沒有簇內(nèi)點(diǎn)，則按照一般禁忌搜索的方法將在邊緣節(jié)點(diǎn)通信范圍內(nèi)但在錨節(jié)點(diǎn)禁忌集之外的節(jié)點(diǎn)數(shù)量作為每個邊緣節(jié)點(diǎn)的權(quán)重，權(quán)重最大的邊緣節(jié)點(diǎn)作為錨節(jié)點(diǎn)的運(yùn)動目標(biāo)．如果有多個邊緣節(jié)點(diǎn)的權(quán)重最大且相同，則取這些邊緣節(jié)點(diǎn)坐標(biāo)的平均值作為錨節(jié)點(diǎn)移動的目標(biāo)點(diǎn)．

(6)如果沒有合適的邊緣節(jié)點(diǎn)，則將當(dāng)前錨節(jié)點(diǎn)禁忌集中的節(jié)點(diǎn)劃入邊緣集，重復(fù)(3)、(4)、(5)步驟.

(7)如果禁忌集中也沒有合適的節(jié)點(diǎn)作為目標(biāo)點(diǎn)，則沿原方向繼續(xù)向前移動一定距離 k，然后重復(fù)(2)、(3)、(4)、(5)步驟．

(8)如果錨節(jié)點(diǎn)在沒有覆蓋設(shè)定的節(jié)點(diǎn)數(shù)量之前已要移動出設(shè)定的區(qū)域，則假定剩余的節(jié)點(diǎn)坐標(biāo)的平均值為下一步移動的目標(biāo)點(diǎn)，向該目標(biāo)點(diǎn)移動 2k距離，以防止錨節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)區(qū)域外時一直向前運(yùn)動而形成死循環(huán)．

將錨節(jié)點(diǎn)在步驟(7)、(8)發(fā)生的移動稱為錨節(jié)點(diǎn)的“自救”移動．

1.2 禁忌搜索與分簇相結(jié)合路徑規(guī)劃仿真實(shí)驗(yàn)

采用 Matlab7.10軟件進(jìn)行仿真．根據(jù)經(jīng)驗(yàn)[3]，禁忌搜索路徑規(guī)劃機(jī)制和禁忌搜索與分簇相結(jié)合的路徑規(guī)劃機(jī)制都比較適用于待定位節(jié)點(diǎn)分布相對集中的區(qū)域，而不適合于待定位節(jié)點(diǎn)均勻分布的情況．為了減少回環(huán)路徑造成的巨大誤差，在200,m×200,m的網(wǎng)絡(luò)區(qū)域內(nèi)選定一“C”型區(qū)域，如圖2所示．利用函數(shù) rand隨機(jī)生成的待定位節(jié)點(diǎn)分布于“C”型區(qū)域.

設(shè)待定位節(jié)點(diǎn)個數(shù)為N，移動錨節(jié)點(diǎn)的通信距離為 Rm＝60,m，待定位節(jié)點(diǎn)的通信半徑為 R1＝40,m，簇半徑為 R＝20,m，k＝10,m．每個簇的簇頭周圍最少的節(jié)點(diǎn)數(shù)量n＝5，初始坐標(biāo)為(200，0)．

取待定位節(jié)點(diǎn)個數(shù)分別為 80、100、120、140、160、180、200．利用 Matlab隨機(jī)生成函數(shù) rand各隨機(jī)生成50次待定位節(jié)點(diǎn)網(wǎng)絡(luò)．

圖2 節(jié)點(diǎn)分布示意圖Fig.2 Diagram of node distribution

雖然設(shè)定待定位節(jié)點(diǎn)的分布區(qū)域?yàn)椤癈”型區(qū)域，但是因?yàn)榇ㄎ还?jié)點(diǎn)隨機(jī)分布，要定位所有的節(jié)點(diǎn)，錨節(jié)點(diǎn)的移動路徑仍會有很多回環(huán)，造成結(jié)果無效．所以假定最終未定位的節(jié)點(diǎn)的數(shù)量不能等于或多于待定位節(jié)點(diǎn)總數(shù)的20%．

記錄分別用禁忌搜索路徑規(guī)劃和禁忌搜索與分簇相結(jié)合路徑規(guī)劃機(jī)制覆蓋這些節(jié)點(diǎn)時，每一個待定位節(jié)點(diǎn)與距其最近的信標(biāo)點(diǎn)的距離和與平均距離，并剔除因?yàn)殄^節(jié)點(diǎn)發(fā)生“自救”移動而使路徑回環(huán)嚴(yán)重時的結(jié)果，求 N為每一個數(shù)值時距離和與平均距離平均值，結(jié)果見圖3．

圖3 兩種路徑規(guī)劃機(jī)制仿真結(jié)果比較Fig.3 Comparison of simulation results using two different planning mechanisms

從圖中可以直觀的看出，在待定位節(jié)點(diǎn)數(shù)量少時，兩種規(guī)劃機(jī)制下的結(jié)果相差不大．隨著待定位節(jié)點(diǎn)的數(shù)量增多，本文提出的禁忌搜索與分簇相結(jié)合的路徑規(guī)劃機(jī)制優(yōu)勢明顯．主要是因?yàn)椋?jié)點(diǎn)數(shù)量較多時簇的數(shù)量較多，錨節(jié)點(diǎn)可以有更多機(jī)會選擇簇頭作為目標(biāo)點(diǎn)，使錨節(jié)點(diǎn)從節(jié)點(diǎn)群的中心經(jīng)過，錨節(jié)點(diǎn)經(jīng)過的信標(biāo)點(diǎn)距離待定位節(jié)點(diǎn)更近，從而錨節(jié)點(diǎn)對待定位節(jié)點(diǎn)的觀測更精確．

2 RSSI測距與 AOA角度測量相結(jié)合的定位方法

2.1 原理

RSSI測距與 AOA角度測量方法相結(jié)合定位方法的原理如圖4所示．

圖4 RSSI測距與AOA角度測量相結(jié)合的定位示意圖Fig.4 Combination positioning schema of RSSI measurement and AOA angle positioning

錨節(jié)點(diǎn)在圓心位置，假定錨節(jié)點(diǎn)的天線測量角度沒有誤差，RSSI測距不產(chǎn)生誤差，待定位節(jié)點(diǎn)總是可以直接或間接向錨節(jié)點(diǎn)發(fā)送信號．錨節(jié)點(diǎn)依次向周圍發(fā)送功率不斷增大的信號，功率小的傳播距離近，功率大的傳播距離遠(yuǎn)．圖中不同半徑的圓表示各種功率的信號的傳播范圍．且這些探測信號的半徑是按從小到大依次等大小遞增，將錨節(jié)點(diǎn)的覆蓋半徑Rm等分成 p份．待定位節(jié)點(diǎn)能夠接收到剛剛超過其與錨節(jié)點(diǎn)的距離的功率圓信號，待定位節(jié)點(diǎn)將這個信號發(fā)送給錨節(jié)點(diǎn)．錨節(jié)點(diǎn)根據(jù)信號可以知道待定位節(jié)點(diǎn)的距離介于兩個功率圓半徑之間．錨節(jié)點(diǎn)利用AOA技術(shù)測得錨節(jié)點(diǎn)到待定位節(jié)點(diǎn)的方向角度為α，可以計算出經(jīng)過錨節(jié)點(diǎn)沿此方向的射線與距離待定位節(jié)點(diǎn)最近的兩個功率圓的交點(diǎn)e與f．

設(shè) l為兩個相鄰功率圓的半徑差，(x，y)為圖 4中圓心坐標(biāo)，e 的坐標(biāo)為(xe，ye)，f 的坐標(biāo)為(xf，yf)，待定位的節(jié)點(diǎn)坐標(biāo)設(shè)為(xo，yo)，則有

通過以上公式可以求得e、f兩點(diǎn)的中點(diǎn)坐標(biāo)，作為待定位節(jié)點(diǎn)的估計坐標(biāo)．

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

假定一200,m×200,m區(qū)域分布著200個待定位節(jié)點(diǎn)，Rm＝60,m，R1＝40,m，R＝15,m，n＝3，k＝10,m．將錨節(jié)點(diǎn)的每一個目標(biāo)點(diǎn)作為一個固定的錨節(jié)點(diǎn)．錨節(jié)點(diǎn)以禁忌搜索與分簇相結(jié)合的路徑規(guī)劃機(jī)制移動．在待定位節(jié)點(diǎn)隨機(jī)分布的情況下進(jìn)行 50次仿真，測得質(zhì)心定位算法、DV-HOP算法與本文方法各自的誤差、定位節(jié)點(diǎn)數(shù)及定位所需時間，并分別求平均值，結(jié)果見表1．

表1 不同定位方法的結(jié)果比較Tab.1 Comparison of different positioning methods

從表中可以看到質(zhì)心定位算法定位的節(jié)點(diǎn)數(shù)量較少，主要是因?yàn)榭勺鳛樾艠?biāo)點(diǎn)的錨節(jié)點(diǎn)經(jīng)過點(diǎn)的數(shù)量少，所以可定位的節(jié)點(diǎn)數(shù)量較少，計算量下降，用時較少．DV-HOP算法雖然將錨節(jié)點(diǎn)覆蓋的節(jié)點(diǎn)都定位了，但是定位誤差大，且定位所需時間較長，主要是因?yàn)樗惴ㄋ柩h(huán)較多，復(fù)雜度較高．

在不考慮RSSI測距誤差和AOA測角度誤差的情況下，相比較質(zhì)心定位算法和DV-HOP算法，本文方法的定位誤差要小；而且實(shí)現(xiàn)對所有錨節(jié)點(diǎn)覆蓋節(jié)點(diǎn)定位的用時最少，主要是因?yàn)槠湟揽慷ㄎ辉O(shè)備來進(jìn)行定位，算法中循環(huán)少，復(fù)雜度低．

3 結(jié) 語

本文提出了禁忌搜索與分簇相結(jié)合路徑規(guī)劃機(jī)制，可以使錨節(jié)點(diǎn)在覆蓋待定位節(jié)點(diǎn)時距待定位節(jié)點(diǎn)更近，便于錨節(jié)點(diǎn)對待定位節(jié)點(diǎn)的觀測．對于單個錨節(jié)點(diǎn)的節(jié)點(diǎn)定位問題，本文提出了RSSI測距與AOA角度測量相結(jié)合的方法，可以實(shí)現(xiàn)對所有錨節(jié)點(diǎn)所覆蓋節(jié)點(diǎn)的定位，且定位精度很高．但是，這種節(jié)點(diǎn)定位方法是在不考慮RSSI測距誤差和AOA測角度誤差的情況下得到的，還需要結(jié)合實(shí)際進(jìn)行檢驗(yàn)和改進(jìn)．

［1］ Koutsonilas D，Das S M，Hu Y Charlie. Path planning of mobile landmarks for localization in wireless sensor networks[J]. Computer Communication，2007，30(13)：2577–2592.

［2］ Huang Rui，Gergely V Z. Static path planning for mobile beacons to localize sensor networks[C]//Proceeding of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops. Piscataway：IEEE，2007：323–330.

［3］ 梁甲金. 基于移動錨節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D]. 成都：西南交通大學(xué)，2010.

［4］ Wu R H，Lee Y H，Tseng H W，et al. Study of characteristics of RSSI signal[C]// Proceedings of the IEEE International Conference on Industrial Technology. Piscataway：IEEE，2008：1–3.

［5］ Niezgoda G H，Ho K C. Geolocalization by combined range difference and range rate difference measurements[C]// Proceedings of the IEEE international Conference on Acoustics，Speech and Signal Processing. Piscataway：IEEE，1994：357–360.

［6］ Bulusu，N Heidemann J，Estrin D，et al. GPS-less low cost outdoor location for very small devices[J]. IEEE Personal Communications，2000，7(5)：28–34.

［7］ Niculescu D，Nath B. DV based positioning in ad hoc networks[J]. Telecommunication Systems，2003，22(1)：267–280.