面向無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的移動錨節(jié)點(diǎn)路徑規(guī)劃

牛龍生,張 瑞,郭瑛

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,山東 青島 266061)

在無線傳感器網(wǎng)絡(luò)中,只有傳感器節(jié)點(diǎn)的位置已知,節(jié)點(diǎn)采集的數(shù)據(jù)才有意義[1]。然而,受限于傳感器節(jié)點(diǎn)的成本,為每一個節(jié)點(diǎn)配置GPS設(shè)備是不現(xiàn)實(shí)的[2]。通常,待定位的傳感器節(jié)點(diǎn)將少量配有GPS裝置、位置已知的錨節(jié)點(diǎn)視為參考節(jié)點(diǎn)[3],通過與錨節(jié)點(diǎn)間的通信估計(jì)或計(jì)算自身位置[4-5]。錨節(jié)點(diǎn)的成本高,部署位置對于定位精度影響較大,采用移動錨節(jié)點(diǎn)可以有效的降低部署的成本,提高定位精度。

按照錨節(jié)點(diǎn)的移動路徑不同,可分為基于靜態(tài)路徑的定位算法和基于動態(tài)路徑的定位算法[6]。在基于靜態(tài)路徑的算法中,錨節(jié)點(diǎn)循著靜態(tài)路徑對整個部署區(qū)域進(jìn)行全局掃描。典型的靜態(tài)路徑包括SCAN[7]、HILBERT[7]、Z-Curve[8]、M-Curve[9]等。其中SCAN 路徑簡單但存在信標(biāo)分布的共線性問題;HILBERT、Z-Curve、M-Curve解決了這個問題而增大了路徑長度。在實(shí)際環(huán)境中,傳感器節(jié)點(diǎn)部署不均勻,且分布受外力影響[10]。這時,錨節(jié)點(diǎn)無法避開空白區(qū)域,從而發(fā)送無效信標(biāo),消耗了能量。

移動錨節(jié)點(diǎn)動態(tài)路徑規(guī)劃的基本原理是利用網(wǎng)絡(luò)中局部鄰居信息來決定錨節(jié)點(diǎn)的下一步前進(jìn)方向。FU等[11]基于人工勢場法,利用6個定向天線,選擇虛擬力最大的那個方向作為下一步的移動方向;WEI等[12]同樣使用虛擬力機(jī)制,設(shè)計(jì)了基于未知節(jié)點(diǎn)密度權(quán)重的改進(jìn)虛擬力模型及回退方案,并討論了最優(yōu)的移動步長。算法總是可以使每個未知節(jié)點(diǎn)周圍的三個信標(biāo)節(jié)點(diǎn)呈正三角形分布,定位誤差較小;李洪峻等[13]利用圖論,將路徑規(guī)劃問題轉(zhuǎn)化為圖的遍歷問題,他們提出了一種寬度優(yōu)先(BRF)算法和回溯貪心(BTG)算法,將通信范圍內(nèi)的節(jié)點(diǎn)劃分為內(nèi)部節(jié)點(diǎn)和邊緣節(jié)點(diǎn),在生成樹的建立過程中只考慮邊緣節(jié)點(diǎn),這減小了路徑長度但也導(dǎo)致部分內(nèi)部節(jié)點(diǎn)無法定位;LI等[14]提出了一種啟發(fā)式運(yùn)動策略和局部最小生成樹的優(yōu)化技術(shù),并進(jìn)一步研究了多移動信標(biāo)協(xié)作定位。這些算法都使用了生成樹的深度優(yōu)先遍歷(depth-first traversal,DFT),回溯代價較大。李松生等[15]提出了一種動態(tài)選擇前進(jìn)方向的策略,但定位率不高。ABDULLAH等[16]應(yīng)用模糊邏輯,綜合考慮未知節(jié)點(diǎn)的RSSI、鄰居的數(shù)量,選出下一步的前進(jìn)方向,而這對錨節(jié)點(diǎn)的計(jì)算能力有更高的要求。

基于邊界的方法[17-18]是機(jī)器人環(huán)境探索領(lǐng)域的一種重要方法,其中邊界指的是已知與未知區(qū)域的邊界。NAGALAJU等[19]首次在無線傳感器網(wǎng)絡(luò)中使用該方法進(jìn)行區(qū)域探測和節(jié)點(diǎn)定位,是一種比較新的視角。受此影響,本工作首先設(shè)計(jì)了錨節(jié)點(diǎn)和傳感器節(jié)點(diǎn)之間的通信過程,并引入了兩種新的數(shù)據(jù)結(jié)構(gòu),邊緣點(diǎn)與探索點(diǎn),不僅提高了定位率,而且避免了對生成樹的逐層回溯,提高了算法的效率。進(jìn)而提出了一種動態(tài)、靜態(tài)路徑相結(jié)合的錨節(jié)點(diǎn)移動方案:錨節(jié)點(diǎn)采用正六邊形軌跡或菱形軌跡來覆蓋某一局部區(qū)域,這使得該局部區(qū)域內(nèi),節(jié)點(diǎn)接近完全定位;覆蓋完一個區(qū)域后根據(jù)局部鄰居信息動態(tài)選擇并移動到下一個覆蓋區(qū)域。相比靜態(tài)路徑,這種路徑因可以避開空白區(qū)域而更加靈活;相比傳統(tǒng)的動態(tài)路徑方案,這種路徑方案通過區(qū)域覆蓋定位局部子區(qū)域的大部分節(jié)點(diǎn),也大大減少了對同一子區(qū)域的重復(fù)訪問,從而避免不必要的能量消耗。仿真結(jié)果表明本設(shè)計(jì)的路徑較短,基于這種路徑的定位算法定位率更高。

1 通信過程設(shè)計(jì)

錨節(jié)點(diǎn)和普通的傳感器節(jié)點(diǎn)存在功能、制作成本等方面的差異,因此可以有不同的通信范圍。能量優(yōu)化是無線傳感器網(wǎng)絡(luò)研究中最重要的問題之一。有研究表明,使兩種節(jié)點(diǎn)的通信范圍保持一致可以建立雙向連接并節(jié)省能量[20]。因此在本工作的設(shè)計(jì)中,令錨節(jié)點(diǎn)和普通的傳感器節(jié)點(diǎn)通信范圍相同。

錨節(jié)點(diǎn)在其移動過程中發(fā)送包含自身當(dāng)前位置的信標(biāo)。當(dāng)錨節(jié)點(diǎn)移動到一個新位置時,其通信范圍內(nèi)的節(jié)點(diǎn)分為3類:未定位節(jié)點(diǎn)、新定位的節(jié)點(diǎn)、先前已定位節(jié)點(diǎn)。其中新定位節(jié)點(diǎn)指的是通過錨節(jié)點(diǎn)這次移動引入的新的位置信息而完成定位的那些節(jié)點(diǎn);先前已定位節(jié)點(diǎn)指的是已經(jīng)完成定位的節(jié)點(diǎn),錨節(jié)點(diǎn)這次新的移動沒有改變它的已定位狀態(tài);未定位節(jié)點(diǎn)指的是在錨節(jié)點(diǎn)這次移動后依然無法完成定位計(jì)算的節(jié)點(diǎn)。隨著錨節(jié)點(diǎn)的移動、定位的進(jìn)行,每個節(jié)點(diǎn)都會由未定位狀態(tài)變成新定位狀態(tài),之后再由新定位狀態(tài)變成先前已定位狀態(tài)。不同的狀態(tài)下傳感器節(jié)點(diǎn)需要處理的數(shù)據(jù)包也不盡相同。新定位的節(jié)點(diǎn)需要與其一跳鄰居以及錨節(jié)點(diǎn)通信:收集鄰居的信息,然后回復(fù)錨節(jié)點(diǎn);先前定位的節(jié)點(diǎn)回復(fù)新定位的節(jié)點(diǎn)的詢問消息;而未定位的節(jié)點(diǎn)只與錨節(jié)點(diǎn)進(jìn)行通信。

首先,網(wǎng)絡(luò)中所有節(jié)點(diǎn)經(jīng)歷一個鄰居發(fā)現(xiàn)過程,每個傳感器節(jié)點(diǎn)廣播一條自身是否已被定位的消息,過程中傳感器節(jié)點(diǎn)廣播后只被動的接收信號,而不轉(zhuǎn)發(fā)。這樣每個傳感器節(jié)點(diǎn)都只獲得它的一跳鄰居信息。此信息包含了鄰居的數(shù)目以及某個鄰居是否已經(jīng)完成定位。每個節(jié)點(diǎn)都維護(hù)一個“未定位鄰居列表”{unloc_nb_num,nb_id1,nb_id2,…},其中第一項(xiàng)是未定位鄰居的數(shù)量,后面的項(xiàng)是其鄰居的id集合。

隨著錨節(jié)點(diǎn)的移動并發(fā)出信標(biāo),引入了新的位置信息,一些未定位節(jié)點(diǎn)可以通過計(jì)算確定自身位置,這些節(jié)點(diǎn)的狀態(tài)變成了新定位狀態(tài)。每個新定位的節(jié)點(diǎn)會廣播一條消息,告知其所有的一跳鄰居節(jié)點(diǎn)自身已定位。對于這個新定位節(jié)點(diǎn)的每個一跳鄰居節(jié)點(diǎn),在收到此消息后,把這個新定位的節(jié)點(diǎn)id從它們的未定位鄰居列表中刪除,并且相應(yīng)的unloc_nb_num減1。如果這個鄰居節(jié)點(diǎn)為已定位狀態(tài),則向新定位的節(jié)點(diǎn)回復(fù)最新的unloc_nb_num信息,否則不回復(fù)消息。

錨節(jié)點(diǎn)維護(hù)兩個列表,邊緣列表和探索列表。如果節(jié)點(diǎn)已定位,但其unloc_nb_num不為零,則稱之為邊緣點(diǎn)。這樣的節(jié)點(diǎn)組成了邊緣列表。探索列表記錄所有探索點(diǎn),探索點(diǎn)存儲了未定位節(jié)點(diǎn)通信范圍內(nèi)的一個信標(biāo)發(fā)出點(diǎn)位置,用來標(biāo)記那些還未定位、但曾經(jīng)接收到至少一個信標(biāo)的節(jié)點(diǎn)。邊緣點(diǎn)定義為{node_id,cal(x),cal(y),NFP(x),NFP(y),unloc_nb_num},探索點(diǎn)定義為{node_id,ref_beacon(x),ref_beacon(y)}。其中,cal(x)和cal(y)表示計(jì)算出的節(jié)點(diǎn)坐標(biāo),NFP主要用于推斷局部區(qū)域哪一側(cè)尚未訪問,將在2.2.3節(jié)介紹的過程中用到。ref_beacon是未定位節(jié)點(diǎn)接收到的第一個信標(biāo)的信標(biāo)發(fā)出點(diǎn)位置。

新定位節(jié)點(diǎn)向錨節(jié)點(diǎn)的回復(fù)消息定義為{node_id,cal(x),cal(y),unloc_nb_num,Map}。這里定義了一個鍵值映射,它的鍵是先前定位的鄰居節(jié)點(diǎn)的id,值是相應(yīng)的未定位鄰居數(shù)unloc_nb_num。node_id表示新定位的節(jié)點(diǎn)id。在每個信標(biāo)發(fā)送位置,錨節(jié)點(diǎn)需要停留一小段時間以接收新定位節(jié)點(diǎn)的回復(fù)消息。通過與新定位節(jié)點(diǎn)的這次通信,錨節(jié)點(diǎn)便可及時更新先前已定位節(jié)點(diǎn)的未定位鄰居數(shù)目信息,從而更新或移除(當(dāng)unloc_nb_num變?yōu)?)一些邊緣點(diǎn)。每次移動后,錨節(jié)點(diǎn)會檢測新定位的節(jié)點(diǎn)是否存在于探索點(diǎn)列表中,存在則移除相應(yīng)的探索點(diǎn)。通過上述通信過程,邊緣列表和探索列表都可以有效地更新,這樣就不會有過多的重復(fù)訪問。另外這兩個列表存儲的一些信息是避開DFT 中逐層回溯的關(guān)鍵。

一般來說,發(fā)送信號的能量消耗遠(yuǎn)遠(yuǎn)大于接收信號,所以這里主要考慮上述通信過程中每個節(jié)點(diǎn)發(fā)送信號的能量消耗。首先每個節(jié)點(diǎn)在鄰居發(fā)現(xiàn)階段都要經(jīng)歷一次廣播。定位開始后,每個節(jié)點(diǎn)在第一次收到信標(biāo)時回復(fù)錨節(jié)點(diǎn);在新定位時廣播消息、向錨節(jié)點(diǎn)回復(fù)鄰居的信息;以及作為先前已定位節(jié)點(diǎn)向其新定位的鄰居節(jié)點(diǎn)回復(fù)消息。先前已定位狀態(tài)下回復(fù)新定位鄰居的次數(shù)與網(wǎng)絡(luò)的連通度有關(guān)。節(jié)點(diǎn)度[21]是衡量網(wǎng)絡(luò)連通度的重要指標(biāo),指的是網(wǎng)絡(luò)中節(jié)點(diǎn)的平均連接數(shù),定義如下,

其中V_links指的是網(wǎng)絡(luò)中的總連接數(shù),V_nodes指總的節(jié)點(diǎn)數(shù)。假設(shè)網(wǎng)絡(luò)的節(jié)點(diǎn)度為n,這樣,每個節(jié)點(diǎn)需要進(jìn)行2次廣播和(n+2)次單播。

2 移動錨節(jié)點(diǎn)路徑規(guī)劃

2.1 定位方法

假設(shè)錨節(jié)點(diǎn)的通信范圍為R,則其發(fā)出的信標(biāo)的覆蓋區(qū)域?yàn)橐粋€圓,該圓以錨節(jié)點(diǎn)的當(dāng)前位置為中心,R為半徑。對于定位問題,常用的方法是三邊測量法。在此方法中,節(jié)點(diǎn)通過3個非共線信標(biāo)的坐標(biāo)與到它們的距離計(jì)算自身位置,即

其中,(xi1,yi1),(xi2,yi2)和(xi3,yi3)是節(jié)點(diǎn)收到的3個信標(biāo)的發(fā)出點(diǎn)坐標(biāo),d1,d2,d3是到它們的距離?！时硎静灰?guī)則信號傳輸引起的誤差。求解此線性方程組,即可得待定位節(jié)點(diǎn)的坐標(biāo)。

2.2 移動路徑設(shè)計(jì)

2.2.1 初始覆蓋(Initialize)

李石堅(jiān)等[22]指出,為了保證完全定位,錨節(jié)點(diǎn)所發(fā)出的各個信標(biāo)的分布應(yīng)滿足對部署區(qū)域達(dá)到三重覆蓋。即當(dāng)錨節(jié)點(diǎn)沿某一路徑移動時,該路徑需要使得部署區(qū)域中任意點(diǎn)均至少可以接收到3個不同的信標(biāo)數(shù)據(jù)包,這樣可以保證無論節(jié)點(diǎn)如何分布均可進(jìn)行定位[22]。前面說明,信標(biāo)的通信范圍在二維平面上是一個圓,那么部署區(qū)域的任意子區(qū)域都需要被至少3個圓覆蓋。圖1為三重覆蓋問題與初始覆蓋軌跡圖,對于中間的圓,所有子區(qū)域都被3個圓覆蓋,這樣這個圓就達(dá)到了三重覆蓋,處于這個圓內(nèi)任何位置的節(jié)點(diǎn)均可被定位。

圖1 三重覆蓋問題與初始覆蓋軌跡Fig. 1 3-coverage problem and initial trajectory

圖1中,為保證中間圓的三重覆蓋,每個圓心都要作為一個信標(biāo)發(fā)出點(diǎn),連接所有圓心,便得到了初始覆蓋軌跡。顯然,這類正六邊形型軌跡的六邊形邊長為R。

2.2.2 步進(jìn)(Step by step)

初始覆蓋后,位于這個初始覆蓋區(qū)域內(nèi)的節(jié)點(diǎn)都被定位了,這樣產(chǎn)生了一批已定位節(jié)點(diǎn)。之后,錨節(jié)點(diǎn)將選擇向unloc_nb_num最大的已定位的一跳鄰居的方向移動,在該方向上,錨節(jié)點(diǎn)移動長度R,移動后的位置將作為下一個覆蓋區(qū)域的中心。圖2為步進(jìn)圖,以圖2(a)為例,在圓1的初始覆蓋之后,它發(fā)現(xiàn)了當(dāng)前覆蓋區(qū)域內(nèi)有一個節(jié)點(diǎn)Q0,該節(jié)點(diǎn)unloc_nb_num最大。因此沿著的Q0方向,錨點(diǎn)移動到Q1,并且Q1被確定為下一覆蓋區(qū)域圓2的中心。

圖2 步進(jìn)圖Fig. 2 Map of step

在圓2中,與圓1相交區(qū)域中的節(jié)點(diǎn)已被覆蓋和定位。為了覆蓋圓2的剩余區(qū)域,設(shè)計(jì)了菱形軌跡,菱形邊長也為R。在設(shè)計(jì)的路徑中,稱正六邊形的中心或菱形的起點(diǎn)為前進(jìn)點(diǎn),如圖2(a)中P7和Q1。上一個前進(jìn)點(diǎn)、當(dāng)前前進(jìn)點(diǎn)及其在菱形中的對點(diǎn)三點(diǎn)共線。

與六邊形軌跡類似,菱形的每個頂點(diǎn)也都是一個信標(biāo)發(fā)出點(diǎn)。顯然位于菱形內(nèi)的所有節(jié)點(diǎn)都可以接收到3個信標(biāo)并定位,而對于圓2中剩余的未覆蓋區(qū)域,可以通過結(jié)合前后兩個圓中的部分信標(biāo)來進(jìn)行定位。這樣,對于圓2也可以實(shí)現(xiàn)近似的完全定位。若某個節(jié)點(diǎn)收到的信標(biāo)不足以完成定位,則第1節(jié)所述的通信過程保證了該節(jié)點(diǎn)附近的一個信標(biāo)發(fā)出點(diǎn)一定在探索列表中,算法保證如果某個探索點(diǎn)對應(yīng)的節(jié)點(diǎn)沒有定位,則該探索點(diǎn)在后面的過程一定會被訪問。

由第1節(jié)通信過程可以推出,錨節(jié)點(diǎn)在訪問第4個頂點(diǎn)后獲得的信息足以涵蓋所有對當(dāng)前覆蓋范圍內(nèi)已定位節(jié)點(diǎn)的更新,于是在這個信標(biāo)發(fā)出點(diǎn)處錨節(jié)點(diǎn)便可以決定下一步移動方向了。這樣,錨節(jié)點(diǎn)可以直接從第4個頂點(diǎn)移動到新的前進(jìn)點(diǎn),而無需重訪菱形第一個頂點(diǎn)。以圖2(b)為例,錨節(jié)點(diǎn)可以從Q4移動到N1,無需通過Q1中轉(zhuǎn)。

只要當(dāng)前覆蓋區(qū)域內(nèi)存在一個unloc_nb_num不為零的已定位節(jié)點(diǎn),本節(jié)所述的過程會重復(fù)執(zhí)行下去。在每一步中,都會由當(dāng)前覆蓋區(qū)域內(nèi)的一個已定位節(jié)點(diǎn)確定方向,錨節(jié)點(diǎn)沿著該方向移動到下一個前進(jìn)點(diǎn),并開始新一步的菱形覆蓋。

2.2.3 跳轉(zhuǎn)(Jump)

在前進(jìn)過程中,每一步選擇一個已定位鄰居節(jié)點(diǎn)來確定方向,而其他unloc_nb_num不為零的已定位節(jié)點(diǎn)則存儲在邊緣列表中。當(dāng)當(dāng)前覆蓋區(qū)域內(nèi)沒有unloc_nb_num不為零的節(jié)點(diǎn)時,則從邊緣列表中選擇v最小的邊緣點(diǎn)。式(3)中定義了V。

其中Vdist_to_it表示錨節(jié)點(diǎn)的當(dāng)前位置與邊緣點(diǎn)之間的距離,也就是說錨節(jié)點(diǎn)這時傾向于選擇未定位鄰居數(shù)目多而距離當(dāng)前位置近的邊緣點(diǎn)。選擇完成后,錨節(jié)點(diǎn)將直接移動到所選邊緣點(diǎn)的位置(即(cal(x),cal(y)))并執(zhí)行前一節(jié)的步進(jìn)過程。這里,邊緣點(diǎn)定義中的NFP被視為上一個前進(jìn)點(diǎn)的所在位置,用于判斷哪一側(cè)尚未訪問,以便計(jì)算出新菱形的四個頂點(diǎn)位置,然后可將該邊緣點(diǎn)從邊緣列表中刪除。

2.2.4 重置(Reset)

當(dāng)錨節(jié)點(diǎn)的當(dāng)前覆蓋范圍內(nèi)沒有unloc_nb_num不為零的節(jié)點(diǎn)并且邊緣列表也為空時,如果探索列表不為空,將從探索列表中選擇(按照距離的遠(yuǎn)近,類似2.2.3節(jié)dist_to_it)一個探索點(diǎn)。探索點(diǎn)存儲的是距離某個待定位節(jié)點(diǎn)最近的信標(biāo)發(fā)出點(diǎn)位置。在這一步中,需要進(jìn)行一次六邊形覆蓋過程。六邊形軌跡以ref_beacon為中心,可以確保該區(qū)域中所有節(jié)點(diǎn)完全定位?？梢娺@一步驟包含了探索點(diǎn)選擇過程以及在選定的探索點(diǎn)附近的六邊形覆蓋過程。

這個過程結(jié)束后,也從探索列表中刪除所選探索點(diǎn),然后進(jìn)入2.2.2節(jié)的步進(jìn)過程。當(dāng)錨節(jié)點(diǎn)的當(dāng)前覆蓋范圍內(nèi)沒有unloc_nb_num不為零的節(jié)點(diǎn)且邊緣列表與探索列表均為空時,算法結(jié)束。算法的偽代碼描述如下:

算法描述

在求解式(2)時,其中兩個信標(biāo)之間相距太近會使計(jì)算誤差過大。為了提高定位精度,可以消除節(jié)點(diǎn)接收到的一些相距太近的信標(biāo)。探索列表保證了每個節(jié)點(diǎn)總能接收至少3個合適的定位信標(biāo)。

定理1對于一個連通的網(wǎng)絡(luò),本算法可以保證完全定位。

證明(反證法)如果算法執(zhí)行結(jié)束,還有一個節(jié)點(diǎn)未定位,根據(jù)連通性的定義,它一定有一個知道這一信息的鄰居,記為A。當(dāng)錨節(jié)點(diǎn)對A進(jìn)行定位時,A會將此信息發(fā)送給移動錨節(jié)點(diǎn)。A要么作為一個邊緣點(diǎn)加入邊緣列表,要么是下一步前進(jìn)方向。對于前者,邊緣列表不為空,算法會繼續(xù)執(zhí)行;對于后者,這時錨節(jié)點(diǎn)在A周圍進(jìn)行菱形覆蓋,節(jié)點(diǎn)可能通過這次覆蓋直接完成定位,否則節(jié)點(diǎn)收到的第一個信標(biāo)發(fā)出點(diǎn)位置會被添加到探索列表中,(只有該節(jié)點(diǎn)完成定位時,才能從探索列表中移出)探索列表不為空,算法也將繼續(xù)執(zhí)行。在兩種情況下,都與原假設(shè)矛盾(即算法執(zhí)行結(jié)束)。證畢。

3 仿真

3.1 設(shè)置

本節(jié)使用Matlab R2020a對本算法的表現(xiàn)進(jìn)行驗(yàn)證。若干個節(jié)點(diǎn)分布在1 000 m*1 000 m區(qū)域內(nèi),通信范圍R為150 m。假設(shè)距離的測量值遵循實(shí)際距離為平均值,實(shí)際距離的2%[23]為標(biāo)準(zhǔn)差的正態(tài)分布。節(jié)點(diǎn)的數(shù)量由網(wǎng)絡(luò)的節(jié)點(diǎn)度確定。

為方便表述,這里取2.2節(jié)4個步驟對應(yīng)英文單詞的首字母作為本算法的名稱,即ISJR(Initialize,Step by step,Jump,Reset)。與基于靜態(tài)路徑的M-Curve[9]、基于虛擬力的VFMS[12]和基于啟發(fā)式運(yùn)動的DREAMS[14]進(jìn)行了比較。M-Curve使用靜態(tài)路徑,后兩種使用動態(tài)路徑。定位方法均采用三邊測量法。分別比較了這4種算法的定位率、平均定位誤差、路徑長度以及信標(biāo)數(shù)量。其中定位率為算法結(jié)束后已定位節(jié)點(diǎn)的數(shù)目與總節(jié)點(diǎn)數(shù)目的比值。定位誤差定義為節(jié)點(diǎn)的估計(jì)位置與實(shí)際位置的歐幾里得距離。平均定位誤差為所有已定位節(jié)點(diǎn)的定位誤差的算術(shù)平均值。錨節(jié)點(diǎn)的路徑長度是指錨節(jié)點(diǎn)在整個定位過程中的總移動距離。信標(biāo)數(shù)目指的是定位過程中錨節(jié)點(diǎn)需要發(fā)出信標(biāo)的數(shù)量。因?yàn)樵诓煌墓?jié)點(diǎn)度下,不同的算法定位率不同,這對路徑長度及信標(biāo)節(jié)點(diǎn)的數(shù)目也造成影響。為部分抵消這種影響,路徑長度及信標(biāo)節(jié)點(diǎn)的數(shù)目的仿真結(jié)果都除以對應(yīng)算法的定位率作為該指標(biāo)的最終值。

圖3 錨節(jié)點(diǎn)的生成路徑Fig. 3 Generated path of anchor

3.2 仿真結(jié)果與分析

3.2.1 定位率與平均定位誤差

本節(jié)比較了C型分布時的定位率與定位誤差,如圖4所示。M-Curve是靜態(tài)路徑,對區(qū)域進(jìn)行全局掃描,因此總能夠定位區(qū)域內(nèi)所有節(jié)點(diǎn)。ISJR 及另外兩種基于動態(tài)路徑的算法受到網(wǎng)絡(luò)連通性的影響,在節(jié)點(diǎn)度低時無法實(shí)現(xiàn)完全定位。

圖4 定位率與定位誤差Fig. 4 Localization ratios and localization errors

在節(jié)點(diǎn)度較低時,網(wǎng)絡(luò)不連通,包含多個連通的子網(wǎng)。由1.1節(jié)的通信過程可知,如果一個待定位節(jié)點(diǎn)到某個信標(biāo)發(fā)出點(diǎn)的距離小于通信范圍,那么這個待定位節(jié)點(diǎn)就會作為未定位節(jié)點(diǎn)與錨節(jié)點(diǎn)進(jìn)行通信,這個信標(biāo)發(fā)出點(diǎn)的位置會作為一個探索點(diǎn)并存入探索列表。在定位一個子網(wǎng)時,可能另一個子網(wǎng)的某個傳感器節(jié)點(diǎn)與錨節(jié)點(diǎn)的某個信標(biāo)發(fā)出點(diǎn)之間的距離小于通信范圍。這樣,在完成當(dāng)前子網(wǎng)的定位過程后,探索列表不為空,算法將繼續(xù)執(zhí)行,從而可進(jìn)一步定位另一個連通的子網(wǎng)。結(jié)合定理1,ISJR確保至少可完全定位一個連通的子網(wǎng),并且有機(jī)會通過某個探索點(diǎn)進(jìn)一步發(fā)現(xiàn)另一個子網(wǎng),因此在定位率方面多次運(yùn)行的平均表現(xiàn)好于VFMS和DREAMS。

4種算法均采用三邊測量法進(jìn)行定位計(jì)算,定位精度的差異主要源于信標(biāo)發(fā)出點(diǎn)的分布。ISJR、M-Curve和VFMS 在定位誤差方面差距不大。VFMS總是可以使信標(biāo)分布均勻,有最佳的定位精度,隨之而來的是該算法錨節(jié)點(diǎn)移動不夠靈活、路徑較長,這將在下一小節(jié)中展示。

3.2.2 路徑長度與信標(biāo)數(shù)量

本節(jié)評估了在C 型分布和矩形分布時關(guān)于這兩個指標(biāo)的各個算法的表現(xiàn)。圖5 為C 型與矩形分布時不同節(jié)點(diǎn)度下錨節(jié)點(diǎn)路徑長度,在C 型分布時,當(dāng)節(jié)點(diǎn)度為5時,定位率較低,VFMS和DREAMS算法運(yùn)行時的生成樹是一棵包含少數(shù)已定位節(jié)點(diǎn)的生成樹,樹的高度較低,除以定位率進(jìn)行的修正不過是對這種短路徑的簡單加和,因而這時表現(xiàn)為路徑短,但這于該算法的實(shí)際效果并無意義;當(dāng)節(jié)點(diǎn)度進(jìn)一步增加時,這些算法定位率接近100%,這時VFMS和DREAMS生成樹變高,造成回溯的成本增加。ISJR 利用邊緣列表和探索列表存儲了需要回溯的節(jié)點(diǎn)位置,這部分是直線移動,相比DREAMS和VFMS的逐層回溯,有更高的效率、路徑也更短。M-Curve是靜態(tài)路徑,不能避開空白區(qū)域,在這種分布下表現(xiàn)不如ISJR和DREAMS。

圖5 C型與矩形分布時不同節(jié)點(diǎn)度下錨節(jié)點(diǎn)路徑長度Fig. 5 Path lengths under C-type and rectangle distribution

如果傳感器節(jié)點(diǎn)均勻分布在矩形區(qū)域,對整個區(qū)域進(jìn)行全局掃描是合理且高效的,圖5(b)顯示了此時M-Curve路徑長度最短。矩形分布下這些算法的定位率都接近100%,路徑長度方面本工作算法表現(xiàn)優(yōu)于VFMS 和DREAMS 而稍差于MCurve,長度約比M-Curve高15%?？梢哉f在傳感器節(jié)點(diǎn)矩形內(nèi)均勻分布的場景,本工作提出的路徑方案提供的結(jié)果也是可接受的。

信標(biāo)數(shù)目和錨節(jié)點(diǎn)的路徑長度基本上是呈正相關(guān)的。圖6顯示了這4種算法完成定位時錨節(jié)點(diǎn)所需要發(fā)送的信標(biāo)數(shù)量。M-Curve是靜態(tài)路徑,在不同的網(wǎng)絡(luò)節(jié)點(diǎn)分布下需要發(fā)出的信標(biāo)數(shù)目固定,路徑上也存在一些冗余信標(biāo)。VFMS 回溯時需要重復(fù)發(fā)出信標(biāo),同時受網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)度的影響明顯,有較大起伏,而總體上處于較高的水平。DREAMS采取啟發(fā)式移動的策略,需要不斷地發(fā)出信標(biāo)試錯,同時也存在DFT 的回溯過程,因此信標(biāo)數(shù)目較高。在這個指標(biāo)上,本算法采取動態(tài)、靜態(tài)路徑相結(jié)合的路徑方案,所需的信標(biāo)數(shù)目總能維持在一個較低的水平。

圖6 C型與矩形分布時不同節(jié)點(diǎn)度下的信標(biāo)數(shù)目Fig. 6 Number of beacons under C-type and rectangle distribution

4 結(jié)語

提出了一種新的錨節(jié)點(diǎn)路徑規(guī)劃算法用于節(jié)點(diǎn)定位。首先設(shè)計(jì)了錨節(jié)點(diǎn)與待定位節(jié)點(diǎn)間的通信過程,并分析了通信負(fù)載。在定位過程中,錨節(jié)點(diǎn)每次前進(jìn)的方向都是基于局部鄰居信息實(shí)時確定的,而對于某個局部區(qū)域,算法采用類菱形軌跡或正六邊形軌跡進(jìn)行覆蓋,這使得一個局部區(qū)域中,大部分節(jié)點(diǎn)可以被定位,這樣盡可能地避免重復(fù)訪問同一區(qū)域。同時引入了邊緣點(diǎn)和探索點(diǎn)兩種數(shù)據(jù)結(jié)構(gòu),避免了DFT 的回溯,也提高了定位率。本工作的路徑方案是一個動態(tài)、靜態(tài)路徑相結(jié)合的方案:錨節(jié)點(diǎn)動態(tài)的從一個子區(qū)域移動到另一個子區(qū)域,這樣可以高效避開空白區(qū)域;在子區(qū)域內(nèi)部的靜態(tài)路徑(菱形軌跡、六邊形軌跡)提升了算法的穩(wěn)定性。在未來的工作中,將考慮在實(shí)際環(huán)境中驗(yàn)證本工作的算法。