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

王茂臣，樊秀梅

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

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

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

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

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

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

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

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

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

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

while g 不為空

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

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

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

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

if d＜＝2*R

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

end

end

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

shuliang＝size(g)

end

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

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

(3)選擇運動方向前方(即與前進方向的方向向量夾角不超過 90°的區(qū)域)的邊緣節(jié)點作為目標點．如圖1所示，錨節(jié)點在b點，錨節(jié)點的前進方向為正右方，為了不重復覆蓋已經經過的區(qū)域，應該選擇右側的點作為目標點，如圖中的 a點．這些可能目標點與錨節(jié)點形成的方向向量與原運動方向的夾角最大為90°．

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

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

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

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

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

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

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

1.2 禁忌搜索與分簇相結合路徑規(guī)劃仿真實驗

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

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

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

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

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

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

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

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

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

2.1 原理

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

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

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

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

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

2.2 仿真實驗

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

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

從表中可以看到質心定位算法定位的節(jié)點數(shù)量較少，主要是因為可作為信標點的錨節(jié)點經過點的數(shù)量少，所以可定位的節(jié)點數(shù)量較少，計算量下降，用時較少．DV-HOP算法雖然將錨節(jié)點覆蓋的節(jié)點都定位了，但是定位誤差大，且定位所需時間較長，主要是因為算法所需循環(huán)較多，復雜度較高．

在不考慮RSSI測距誤差和AOA測角度誤差的情況下，相比較質心定位算法和DV-HOP算法，本文方法的定位誤差要?。欢覍崿F(xiàn)對所有錨節(jié)點覆蓋節(jié)點定位的用時最少，主要是因為其依靠定位設備來進行定位，算法中循環(huán)少，復雜度低．

3 結 語

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

［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é)點的無線傳感器網絡定位技術研究[D]. 成都：西南交通大學，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.