農(nóng)田環(huán)境無線傳感器網(wǎng)絡(luò)無錨節(jié)點定位算法

1、農(nóng)田環(huán)境無線傳感器網(wǎng)絡(luò)無錨節(jié)點定位算法*郭建全，趙偉，黃松嶺（清華大學(xué)電機(jī)系電力系統(tǒng)國家重點實驗室北京100084）摘要：無錨節(jié)點定位算法不需要添加額外硬件，無需錨節(jié)點或少量參考節(jié)點，僅利用自身的無線收發(fā)器即可實現(xiàn)整個網(wǎng)絡(luò)的節(jié)點定位，使定位成本大大降低，是解決由大量廉價節(jié)點組成大規(guī)模網(wǎng)絡(luò)定位問題的較好方法。以農(nóng)田應(yīng)用為背景，提出一種無錨節(jié)點定位算法。該算法從普通節(jié)點中選取基準(zhǔn)節(jié)點以形成坐標(biāo)系，其他未知節(jié)點根據(jù)自己到基準(zhǔn)節(jié)點的距離計算出自身坐標(biāo)，最終得到所有節(jié)點的相對位置。還以實測求平均方法解決了無錨節(jié)點定位算法的累積誤差問題。算法具有分布式特點，實現(xiàn)過程簡單，實用性強(qiáng)。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；

2、無錨節(jié)點定位；跳數(shù)梯度；累積誤差中圖分類號：TP393.05文獻(xiàn)標(biāo)識碼：A國家標(biāo)準(zhǔn)學(xué)科分類代碼：510.99Anchor-free location algorithm for wireless sensor networksin the application of farmland Guo Jianquan, Zhao Wei, Huang Songling（State Key Lab of Power Systems, Dept. of Electrical Engineering, Tsinghua University, Beijing 100084, China）Abstract：

3、Anchor-free location algorithm needs no anchor or only a few of reference nodes and realizes the location of the nodes in wireless sensor networks only using the wireless receiver equipped on each node without adding any other equipment or hardware, which is very applicable to the large scale wirele

4、ss sensor networks made up by many low-cost nodes. This paper proposes an anchor free location algorithm taking farmland application as a background. The algorithm first chooses some reference nodes as “anchors” from ordinary nodes according to certain criteria to form a coordinate system, based on

5、which other unknown nodes can calculate their coordinates. The algorithm calculates the average hop distance according to the actual size of the farmland and solves the problem of the accumulated error. The algorithm proposed in this paper has distributed feature, and is easy to be implemented and a

6、pplicable.Key words：wireless sensor network; anchor-free location; hop gradient; accumulated error1引言收稿日期：2008-10Received Date：2008-10 *基金項目：國家高新技術(shù)發(fā)展規(guī)劃“863”課題基金 (2007AA10Z241) 資助項目節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)重要的服務(wù)支撐技術(shù)。由于無線傳感器網(wǎng)絡(luò)節(jié)點成本、功耗和硬件條件的限制，如何實現(xiàn)低成本、低功耗和高精度定位是無線傳感器網(wǎng)絡(luò)技術(shù)的研究重點之一。根據(jù)定位算法是否需要通過物理測量獲取節(jié)點間的距離或角度信息，可將定位算法

7、分為基于測距和非基于測距的定位算法。基于測距的定位算法一般利用測量得到節(jié)點相互間的距離或角度信息來實現(xiàn)位置計算，測量距離的方法有1：利用信號達(dá)到的時間差（TOA）、利用兩種不同信號到達(dá)的時間差（TDOA）、利用角度（AOA）及利用無線信號的衰減度（RSSI），其中，RSSI法無需添加額外硬件，只利用自身攜帶的測量無線電信號強(qiáng)度指示功能，據(jù)經(jīng)驗公式計算兩節(jié)點間的距離，但誤差較大；TOA、TDOA和AOA方法均需依賴大量昂貴且消耗能量的硬件。非基于測距的定位算法是通過一定方法估計節(jié)點間的距離或確定包含未知節(jié)點的可能區(qū)域，實際上，仍需要被定位節(jié)點與參考節(jié)點的距離信息，只不過距離信息是通過其他方式間接

8、取得的。典型的非基于測距的定位算法有質(zhì)心算法2、APIT算法3、DV-Hop算法4、Amorphous算法5-6等。質(zhì)心算法和APIT算法依賴高密度的錨節(jié)點，使每個傳感器節(jié)點都能接聽幾個錨節(jié)點的信號。DV-Hop算法和Amorphous算法依靠洪泛協(xié)議，由到錨節(jié)點的跳數(shù)信息計算距離。對于少錨節(jié)點和無錨節(jié)點的傳感器網(wǎng)絡(luò)，因大部分節(jié)點沒有能力與足夠數(shù)量的錨節(jié)點直接通信，如何有效實現(xiàn)節(jié)點定位極具挑戰(zhàn)性。現(xiàn)有的無錨節(jié)點定位算法有AFL算法7、KPS算法8和ABS算法9。AFL算法是無錨節(jié)點、完全分布式的定位算法，它先用啟發(fā)式原理得到一個無折疊布局，使之結(jié)構(gòu)大致接近于實際布局圖，然后基于質(zhì)點彈簧模型優(yōu)化

9、算法修正和平衡定位誤差，使對應(yīng)于位置的能量函數(shù)達(dá)到最小。KPS算法是根據(jù)事先假定的節(jié)點分組配置模型，每個節(jié)點觀察鄰節(jié)點所在組的成員節(jié)點個數(shù)，并根據(jù)預(yù)先假定的分組配置模型實現(xiàn)自身定位。ABS算法則是利用節(jié)點間的通信連接關(guān)系，按順序一次計算一個未知節(jié)點坐標(biāo)，不斷經(jīng)修正和冗余計算減少定位誤差。但這3種無錨節(jié)點定位方法均還存在問題。如：AFL算法并未明確給出單跳跳距的計算方法；KPS算法是基于一個分組布置的概率模型前提；而ABS算法需已知4個錨節(jié)點坐標(biāo)，或要事先設(shè)定4個節(jié)點的坐標(biāo)。而且，這3種算法由于各自固有的特點，都存在嚴(yán)重的誤差累加現(xiàn)象，故往往導(dǎo)致定位結(jié)果不可用。應(yīng)用無線傳感器網(wǎng)絡(luò)實現(xiàn)農(nóng)業(yè)典型危害

10、動物的數(shù)字化聲防，對提高我國農(nóng)業(yè)的精細(xì)耕作、集約化經(jīng)營水平具有重要現(xiàn)實意義。針對農(nóng)田環(huán)境的特殊應(yīng)用背景，本文提出一種適用于大規(guī)模農(nóng)田環(huán)境的無錨節(jié)點定位算法。該算法首先從大量同質(zhì)傳感器節(jié)點中選出基準(zhǔn)節(jié)點，根據(jù)農(nóng)田尺寸信息賦予基準(zhǔn)節(jié)點相對坐標(biāo)值，建立相對坐標(biāo)系；然后以每個基準(zhǔn)節(jié)點為“錨節(jié)點”，利用改進(jìn)的Amorphous算法得到各節(jié)點到每個基準(zhǔn)節(jié)點的距離；最后，每個未知節(jié)點計算出自己在這個坐標(biāo)系中的坐標(biāo)。該算法是一種分布式定位算法，實用性強(qiáng)、實現(xiàn)簡單、定位精度較高，解決了農(nóng)田環(huán)境中無線傳感器網(wǎng)絡(luò)節(jié)點的低成本、高精度定位問題。2本文算法要解決的關(guān)鍵問題在沒有錨節(jié)點存在情況下，為實現(xiàn)節(jié)點定位，首先要選

11、擇一些節(jié)點作為“錨節(jié)點”。為區(qū)分于其他基于已知錨節(jié)點的定位算法，本文將從普通節(jié)點中選出的“錨節(jié)點”稱為“基準(zhǔn)節(jié)點”。利用基準(zhǔn)節(jié)點建立坐標(biāo)系，其他節(jié)點可根據(jù)到基準(zhǔn)節(jié)點的距離得到自身在此坐標(biāo)系中的位置。對于常見的矩形農(nóng)田，首選其4個角的節(jié)點作為基準(zhǔn)節(jié)點。如何通過算法實現(xiàn)基準(zhǔn)節(jié)點的選取，是本文首先要解決的問題。無錨節(jié)點定位算法簡單易行，無需額外添加硬件，但與其他有昂貴硬件支持的定位算法相比，其定位精度不高。產(chǎn)生較大誤差的最主要原因是誤差累加嚴(yán)重。在Amorphous算法5-6,10中，通過建立以基準(zhǔn)節(jié)點為原點的跳數(shù)梯度場得到各節(jié)點到基準(zhǔn)節(jié)點的跳數(shù)距離（式（1），跳數(shù)距離乘以平均跳距（式（2）即可得到

12、以長度單位衡量的距離值。 (1) (2)式中：si為局部平均跳數(shù)；表示節(jié)點i與基準(zhǔn)節(jié)點間的最小跳數(shù)；表示節(jié)點i信號輻射半徑內(nèi)的所有節(jié)點。為平均跳距；r為通信半徑；為平均鄰居節(jié)點數(shù)（通信半徑內(nèi)的平均節(jié)點數(shù)）。式（2）的計算過于復(fù)雜，難以在節(jié)點上實現(xiàn)。另外，通信半徑r是一個與節(jié)點周圍環(huán)境有關(guān)的量，不同周圍環(huán)境（如土壤濕度、植被、氣象條件等）對應(yīng)著不同的值，故用經(jīng)驗公式計算無疑會出現(xiàn)誤差；再有，節(jié)點局部密度的變化也會產(chǎn)生誤差。這些誤差均會隨跳數(shù)距離的增加而累積增大，往往使最終計算結(jié)果不可用。但根據(jù)農(nóng)田尺寸，可利用算法得到較精確的平均跳距，從而使計算精度大大提高。得到各節(jié)點到基準(zhǔn)節(jié)點的距離后，由基準(zhǔn)節(jié)

13、點的坐標(biāo)即可求出各節(jié)點自身的坐標(biāo)。由于定位算法得到的各節(jié)點到基準(zhǔn)節(jié)點的距離值存在誤差，因此節(jié)點最佳坐標(biāo)的求取是一個尋優(yōu)過程。綜上所述，本文定位算法需要解決的關(guān)鍵問題有3個：1)基準(zhǔn)節(jié)點的選??；2)平均跳距的求??；3)未知節(jié)點坐標(biāo)的求取。3基準(zhǔn)節(jié)點的選取對于常見的矩形農(nóng)田，其4個角的節(jié)點作基準(zhǔn)節(jié)點是首選。本文利用節(jié)點到已有基準(zhǔn)節(jié)點的跳數(shù)距離值來選擇新的基準(zhǔn)節(jié)點。如圖1所示，從邊界上某一點（通常為sink節(jié)點，如圖1中的A點）觸發(fā)開始，發(fā)送導(dǎo)標(biāo)信號，執(zhí)行距離矢量路由交換協(xié)議，將建立以節(jié)點A為“源”，距離這個節(jié)點的跳數(shù)值遞增的跳數(shù)梯度場。在跳數(shù)梯度場中，位于對角的C點顯然屬于跳數(shù)值最大的那一環(huán)的節(jié)點

14、集合中。因此，還需根據(jù)一定準(zhǔn)則從這個集合中選出合適的節(jié)點作為基準(zhǔn)節(jié)點?；鶞?zhǔn)節(jié)點B、D也可按照同樣道理選出。圖1基準(zhǔn)節(jié)點選取示意圖Fig.1 Selection of the reference nodes以圖1為例，基準(zhǔn)節(jié)點C滿足關(guān)系，此處，s的含義與式（1）同，i為網(wǎng)絡(luò)中的任意節(jié)點。由于每個節(jié)點只能得到鄰居節(jié)點的信息，如何利用局部信息實現(xiàn)整體目標(biāo)是需要解決的問題。假定傳感器節(jié)點隨機(jī)均勻分布，在給定面積為a的范圍內(nèi)存在k個節(jié)點的概率滿足泊松分布：式中：，表示節(jié)點密度，即節(jié)點總數(shù)N除以總面積S。易知，在給定面積a中分布的節(jié)點個數(shù)的期望值為a。因此，如果節(jié)點位于矩形農(nóng)田的角上，其鄰居節(jié)點個數(shù)的期望

15、值為，r為通信半徑。于是，可設(shè)定一個閾值，包含C的節(jié)點集合中的節(jié)點滿足關(guān)系： (3)通常，滿足式（3）的節(jié)點不止一個。必須通過sink節(jié)點來確定哪個才是所要的基準(zhǔn)節(jié)點。實現(xiàn)的方法是，當(dāng)節(jié)點發(fā)現(xiàn)自己滿足式（3）時，首先跟鄰居節(jié)點比較跳數(shù)值，以確保自己的跳數(shù)值最大。然后，再發(fā)送一個包含節(jié)點編號和平均跳數(shù)值的信息給sink節(jié)點。sink節(jié)點將比較接收到的所有信息中的值，取其最大的一個作為基準(zhǔn)節(jié)點C，并將包含的確認(rèn)信息廣播到網(wǎng)絡(luò)中。同理，可以選出基準(zhǔn)節(jié)點B和D，基準(zhǔn)節(jié)點B滿足且；基準(zhǔn)節(jié)點D滿足。4平均跳距的確定平均跳距的計算精度直接影響最終定位結(jié)果的精度。由第3節(jié)可知，基準(zhǔn)節(jié)點選取過程中，已得到了基準(zhǔn)

16、節(jié)點之間以跳數(shù)表示的距離值，現(xiàn)在只需利用網(wǎng)絡(luò)的尺寸大小，直接得到平均跳距，避免了用經(jīng)驗公式計算造成的誤差累積，以提高定位精度。但是，對于在給定面積上分布的節(jié)點，選取的基準(zhǔn)節(jié)點的間距是節(jié)點分布密度的函數(shù)，因此，需首先求出基準(zhǔn)節(jié)點間距與節(jié)點分布密度之間的關(guān)系。以圖2為例，節(jié)點P、Q為選取的基準(zhǔn)節(jié)點，在基準(zhǔn)節(jié)點的選取過程中，已得到了SpQ的值，下面求取節(jié)點P、Q之間距離PQ的表達(dá)式。圖2 對角線基準(zhǔn)節(jié)點間距期望值求取原理示意Fig. 2 Calculation of the expected distance between two diagonal reference nodes由基準(zhǔn)節(jié)點的選取過

17、程可知，基準(zhǔn)節(jié)點P、Q為最靠近“角”的節(jié)點，即在它們與“角”之間存在一個沒有節(jié)點分布的區(qū)域（如圖2中的近似為三角形的CEF陰影部分）。對于節(jié)點分布密度為（節(jié)點數(shù)/單位面積）的二維均勻分布網(wǎng)絡(luò)，由概率知識可知，在給定面積為S的范圍內(nèi)有k個節(jié)點的概率滿足泊松分布，分布概率可表示為：設(shè)二維平面內(nèi)沒有任何傳感器節(jié)點存在的面積為。的概率分布可表示為：F(s)=Pr(S<s)=Pr(在s上有1個節(jié)點)+Pr(在s上有2個節(jié)點)+=1-Pr(在s上有0個節(jié)點)=1-e-s計算的數(shù)學(xué)期望：由于對角線基準(zhǔn)節(jié)點之間距離較遠(yuǎn)，可按三角形來處理。因此，由于梯度形成的形狀，由基準(zhǔn)節(jié)點的選取過程和幾何相似關(guān)系（理論

18、推導(dǎo)過程略）可知，三角形的形狀跟矩形的尺寸有關(guān)，如果，有。因此可求出：，從而有：可求出平均跳距：需要說明，從的推導(dǎo)過程可知，對傳感器節(jié)點均勻分布的情況，這里所得平均跳距是統(tǒng)計意義上的期望值。5計算節(jié)點坐標(biāo)各節(jié)點在得到與基準(zhǔn)節(jié)點之間的距離值后，開始求取自身的坐標(biāo)值。坐標(biāo)的求取過程是一個尋優(yōu)過程。設(shè)待求節(jié)點的坐標(biāo)為，節(jié)點利用跳數(shù)梯度算法估得到的到基準(zhǔn)節(jié)點的距離為，實際距離為；則節(jié)點的坐標(biāo)的最優(yōu)估計值應(yīng)滿足：節(jié)點i的坐標(biāo)的最優(yōu)值可用牛頓迭代法求取，每次迭代，坐標(biāo)值更新的大小正比于總平方差對坐標(biāo)分量的偏導(dǎo)：坐標(biāo)的更新公式為：和式中：為迭代步長。迭代初始值的選擇非常關(guān)鍵，它直接關(guān)系著迭代是否收斂和迭代的

19、快慢。如圖3所示，假定節(jié)點E到基準(zhǔn)節(jié)點X、Y、Z和W的距離分別為d1、d2、d3和d4，設(shè)基準(zhǔn)節(jié)點X為坐標(biāo)原點，因為，迭代的初始值可按幾何比例關(guān)系，求平均值得到： (4)圖3未知節(jié)點坐標(biāo)的計算Fig. 3 Calculation of the coordinates of the unknown nodes顯然，選擇的初始值已經(jīng)很接近真實值，只要進(jìn)行較少次迭代，即可達(dá)到滿意的精度。6定位算法的實現(xiàn)過程本文提出的無錨節(jié)點定位算法整個實現(xiàn)過程的主要步驟為：步驟 1 ：各個節(jié)點初始化變量。與本文算法相關(guān)的主要變量有：IfRefNode:節(jié)點狀態(tài)（是否是基準(zhǔn)節(jié)點），初始化值為0（表示普通節(jié)點）。Coo

20、rdinate1×2：節(jié)點的坐標(biāo)，各元素初始化值為0。HopToRef1×5：到sink節(jié)點及各基準(zhǔn)節(jié)點的平均跳數(shù)值。各元素的初始化值要足夠大。SingleHopDis: 平均跳距，初始化為0。CorOfRef4×2:4個基準(zhǔn)節(jié)點的坐標(biāo)，各元素初始化值為0。DisToRef1×4: 到sink節(jié)點及其4個基準(zhǔn)節(jié)點的距離，各元素初始化值應(yīng)足夠大，以便在跳數(shù)梯度形成過程中滿足更新條件。步驟 2 ：sink節(jié)點觸發(fā)定位過程和第一個基準(zhǔn)節(jié)點（假定為節(jié)點n1）的選取。sink節(jié)點廣播一個跳數(shù)初值為1的信標(biāo)，鄰居節(jié)點收到此信標(biāo)后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給它們的鄰居節(jié)點。

21、每個接收到此信標(biāo)的鄰居節(jié)點會把跳數(shù)加1，并向鄰居節(jié)點發(fā)送包含跳數(shù)加1后的信標(biāo)。每個節(jié)點只記錄跳數(shù)的最小值而忽略包含較大跳數(shù)值的信標(biāo)，如此，便阻止了信標(biāo)的反向傳播。照此進(jìn)行下去，會形成從基準(zhǔn)節(jié)點向外擴(kuò)展的跳數(shù)梯度場。最終，節(jié)點保留了到sink節(jié)點的最小跳數(shù)值。然后，所有節(jié)點收集鄰居節(jié)點的最小跳數(shù)值，并根據(jù)式（1）計算出平均跳數(shù)值，保存到HopToRef1×5的第1個元素中。根據(jù)第2節(jié)方法選出第1個基準(zhǔn)節(jié)點n1，并賦予坐標(biāo)值。節(jié)點n1將變量IfRefNode賦值為1，在下一輪基準(zhǔn)節(jié)點選取過程中，將充當(dāng)已有的基準(zhǔn)節(jié)點，建立跳數(shù)梯度場。步驟 3：按照第2節(jié)中的方法選出其他3個基準(zhǔn)節(jié)點n2、n

22、3 、n4。 步驟 4：根據(jù)第3節(jié)中的方法計算出平均跳距，并廣播到網(wǎng)絡(luò)中，這個值將被保存到各節(jié)點的變量SingleHopDis中。步驟 5：計算未知節(jié)點的坐標(biāo)。未知節(jié)點根據(jù)HopToRef1×5和SingleHopDis計算出自己到各基準(zhǔn)節(jié)點的距離值，保存到變量DisToRef1×4中，根據(jù)第4節(jié)中的方法計算出自身的坐標(biāo)，將其存放在變量Coordinate1×2中，整個定位過程結(jié)束。7仿真實驗7.1各節(jié)點到基準(zhǔn)節(jié)點距離的求取利用MATLAB仿真，設(shè)1 000個傳感器節(jié)點均勻分布在1 000 m×1 000 m的農(nóng)田面積上。首先，基準(zhǔn)節(jié)點建立以自身為“源”

23、的跳數(shù)梯度場，各節(jié)點利用式（1）計算出它們到基準(zhǔn)節(jié)點的以跳數(shù)表示的距離；然后，利用兩個基準(zhǔn)節(jié)點間的跳數(shù)距離，根據(jù)網(wǎng)絡(luò)的尺寸得到較精確的平均跳距。各節(jié)點到基準(zhǔn)節(jié)點的距離，即可通過跳數(shù)值乘以平均跳距得到。圖4（a）為以坐標(biāo)原點為基準(zhǔn)節(jié)點建立的跳數(shù)梯度場示意圖，跳數(shù)值為奇數(shù)次的節(jié)點用“·”表示，為偶數(shù)次的用“*”表示。跳數(shù)梯度場為以基準(zhǔn)節(jié)點為圓心，向外環(huán)狀擴(kuò)展的形狀，每個節(jié)點都位于某個環(huán)上，如果某個節(jié)點位于第h跳的環(huán)上，則除邊界節(jié)點外，它的通信半徑內(nèi)一般都包含有h-1跳、h跳和h+1跳的節(jié)點。利用式（1）可計算出各節(jié)點到基準(zhǔn)節(jié)點的平均跳數(shù)。圖4（b）是平均跳距用式（2）計算得到的到基準(zhǔn)節(jié)點

24、的測距效果。圖4（c）為利用本文提出的算法，直接求取平均跳距后的效果。節(jié)點位置的計算值由“·”表示，其上連接的短線，表示計算的位置與實際位置間的誤差。為更清晰地說明問題，圖4（b）和圖4（c）均只考慮節(jié)點到基準(zhǔn)節(jié)點之間距離的變化，即假定所有節(jié)點只在到基準(zhǔn)節(jié)點的連線方向上移動?？梢钥闯觯帽疚姆椒ㄋ愠龅钠骄?，消除了由于周圍環(huán)境影響和局部節(jié)點密度不均勻造成的累計誤差，得到的測距效果明顯優(yōu)于理論公式計算的結(jié)果。(a)跳數(shù)梯度場的建立過程(a)The process of establishing the hop gradient(b)用理論公式計算平均跳距的測距效果(b) The av

25、erage hop distance calculated by theoretical formula(c)用本文方法計算平均跳距的測距效果(c) is the average hop distance calculated by the proposed algorithm圖4各節(jié)點到基準(zhǔn)節(jié)點距離的求取Fig.4 Calculation of the distance between each nodeand the reference node.圖5是不同節(jié)點密度（用通信半徑內(nèi)平均節(jié)點個數(shù)N_averager表示）下，用理論公式計算和本文方法計算得到的平均測距誤差的對比，平均測距誤差為所

26、有節(jié)點的測距誤差的平均值。圖5用理論公式和本文方法得到的平均測距誤差對比Fig.5 Comparison of average calculated distance errors usingtheoretical formula and the proposed algorithm誤差的總趨勢是節(jié)點密度越小誤差越大，這是由算法的固有特性決定的，可見，在任何情況下，本文方法的平均測距誤差均小于理論公式計算的結(jié)果。7.2計算未知節(jié)點的坐標(biāo)采用與7.1節(jié)相同的仿真環(huán)境，圖6為按照第4節(jié)中的方法，經(jīng)過100次迭代的計算結(jié)果，迭代初始值按照式（4）計算?！?#183;”表示節(jié)點位置的計算值，連線表示節(jié)

27、點位置的計算值與實際值之間的誤差。計算結(jié)果表明，總的平均定位誤差為節(jié)點通信半徑的11%。可以看出，邊界處的節(jié)點相對于中間位置的節(jié)點而言，定位誤差要大些。這是因為，各節(jié)點定位誤差的大小不但與節(jié)點到各基準(zhǔn)節(jié)點的測距誤差大小有關(guān)，而且還與基準(zhǔn)節(jié)點自身坐標(biāo)的誤差及各節(jié)點與基準(zhǔn)節(jié)點的相對位置有關(guān)。圖6本文算法得到的定位效果.Fig.6 The effect of location using the proposed algorithm如果傳感器節(jié)點分布面積給定，定位誤差主要受節(jié)點個數(shù)多少和節(jié)點通信半徑大小影響。假定定位誤差以所有節(jié)點的計算位置到其實際位置之間距離的平均值表示。改變仿真環(huán)境中節(jié)點的個數(shù)和

28、通信半徑的大小，節(jié)點個數(shù)分別取值為1 000、950、800、750、700450、400、300、200，總共13組；通信半徑大小從130遞減到30，間隔為10，總共11組。得到的定位誤差如圖7所示。圖7中，不同深淺度顏色對應(yīng)著不同大小的誤差等級?？梢钥吹?，節(jié)點個數(shù)越多，通信半徑越大，總誤差越??；反之誤差越大。圖7中左下角的區(qū)域和右上角近似三角形的區(qū)域之間有一條明顯的分隔帶。如果用輻射半徑內(nèi)節(jié)點的平均個數(shù)表示節(jié)點的密度，這個分隔帶對應(yīng)的節(jié)點密度約為5，即通信半徑內(nèi)節(jié)點個數(shù)低于5時誤差會明顯增大。這是由于當(dāng)局部節(jié)點分布不均勻時，如果節(jié)點密度過低，一些節(jié)點就會與其他節(jié)點失去聯(lián)系（特別是在角落附近

29、），致使在跳數(shù)梯度的建立過程中出現(xiàn)較大局部誤差。因此，為得到較滿意的計算精度，在利用本文算法實現(xiàn)節(jié)點定位過程中，應(yīng)保證通信半徑內(nèi)的平均節(jié)點個數(shù)大于5。圖7總的平均誤差特性Fig.7 The characteristic of the total average error8結(jié)論本文以農(nóng)田應(yīng)用為背景，提出一種大規(guī)模網(wǎng)絡(luò)無錨節(jié)點定位算法。該算法首先從網(wǎng)絡(luò)的所有普通節(jié)點中選取基準(zhǔn)節(jié)點，再利用所選基準(zhǔn)節(jié)點建立坐標(biāo)系，利用跳數(shù)梯度場得到未知節(jié)點到基準(zhǔn)節(jié)點的距離，未知節(jié)點根據(jù)到基準(zhǔn)節(jié)點間的距離算出自身在網(wǎng)絡(luò)中的相對位置。為解決無錨節(jié)點定位算法誤差累積問題，針對農(nóng)田的特殊情況，本文采用實測求平均法得到平均跳

30、距，提高了計算精度。本文提出的定位算法具有分布式的特點，具有較強(qiáng)的實用性和可擴(kuò)展性，非常適用于由大量低成本節(jié)點組成的大規(guī)模無線傳感器網(wǎng)絡(luò)。本文提出的定位算法雖以農(nóng)田環(huán)境為背景，但其基本思想在其他應(yīng)用場合仍然具有借鑒價值。如：對于不同的網(wǎng)絡(luò)形狀，只要恰當(dāng)?shù)剡x擇基準(zhǔn)節(jié)點以建立適合于該網(wǎng)絡(luò)形狀的坐標(biāo)系，即可按照本文的方法得到其他未知節(jié)點的相對坐標(biāo)。另外，必須指出，本文提出的定位算法未考慮障礙物存在的情況。障礙物的存在，可能使得建立的跳數(shù)梯度場與沒有障礙物時的情況有一定甚至是較大差別，但直覺上，通過分析基于不同基準(zhǔn)節(jié)點建立的跳數(shù)梯度場之間的約束關(guān)系，仍然可以計算未知節(jié)點的相對位置，這也是今后值得深入研

31、究的方向。參考文獻(xiàn)1 BIAZ S, JI Y. A survey and comparison on localization algorithms for wireless ad hoc networksC. International Journal of Mobile Communications (IJMC), 2005, 3(4): 374-410.2 BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devicesJ. IEEE Personal Commu

32、nications Magazine, 2001, 7(5):28-34.3 HE T, HUANG G, BLUM B, et al. Range-free location schemes in large scale sensor networksA. Proceedings of The 9th Annual International Conference on MobileComputing And Network (MobiCom 03 )C. San Diego, 2003(3):81-95.4 NICULESCU D, NATH B. DV based positioning

33、 in Ad Hoc networksJ. Journal of Telecommunication Systems, 2003, 22(14): 267-280.5 NAGPAL R. Organizing a global coordinate system from local information on an amorphous computer: Report of AI memoR. MIT Artificial Intelligence Laboratory, 1999.6 NAGPAL R, SHROBE H, BACHRACH J. Organizing a global

34、coordinate system from local information on an Ad hoc sensor networkC. Proceeding of Workshop on Information Processing In Sensor Networks. April 2003: 333-348.7 PRIYANRHA N, BALAKRISHNAN H, DEMAINE E, et al. Anchor-free distributed localization in sensor networksR. Technical Report TR-892, MIT Laboratory for Computer Science, April 2003.8 FANG L, DU W, NING