基于Amorphous的無線傳感器網(wǎng)絡(luò)定位算法研究

北京信息科技大學(xué)自動化學(xué)院，北京 100101

一、引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks）[1-3]作為一種全新的信息獲取和處理技術(shù)，是當(dāng)前在國際上備受關(guān)注的、涉及多學(xué)科高度交叉的前沿?zé)狳c研究領(lǐng)域。

無線傳感器網(wǎng)絡(luò)的關(guān)鍵支撐技術(shù)之一是定位問題，定位問題也是無線傳感器網(wǎng)絡(luò)應(yīng)用以及其他研究的基礎(chǔ)，如地理環(huán)境監(jiān)測、軍事偵察、交通路況監(jiān)測、搶險救災(zāi)、醫(yī)療衛(wèi)生中對病人的跟蹤等，所獲取的監(jiān)測數(shù)據(jù)需要有相應(yīng)的位置信息，否則，這些數(shù)據(jù)就是不確切的，甚至?xí)ゲ杉瘮?shù)據(jù)的意義。

全球定位系統(tǒng)（GPS）可以為地球表面絕大部分地區(qū)（98%）提供準(zhǔn)確的定位。但是受到成本、功耗、體積等因素的限制，在大規(guī)模的無線傳感器網(wǎng)絡(luò)中，為每個傳感器節(jié)點都安裝GPS設(shè)備是不太實際的方法。所以現(xiàn)有的一些定位方法中只是讓少數(shù)傳感器節(jié)點配備有GPS設(shè)備，然后通過一些數(shù)學(xué)的方式來估算未知傳感器節(jié)點的位置。

根據(jù)定位過程中是否測量實際節(jié)點間的距離，定位算法可分為：距離相關(guān)(Range-based)定位算法和距離無關(guān)(Range-free)定位算法。其距離相關(guān)的定位算法需要測量相鄰節(jié)點間的絕對距離或方位，并利用節(jié)點間的實際距離來計算位置節(jié)點的位置，定位精度高，但對節(jié)點本身硬件要求較高。距離無關(guān)的定位算法是根據(jù)網(wǎng)絡(luò)連通性等信息，利用節(jié)點間的估計距離計算節(jié)點位置，成本低、功耗小、抗噪能力強且硬件設(shè)備簡單。Amorphous定位算法就是一種距離無關(guān)的定位算法。

Amorphous定位算法是由麻省理工大學(xué)的Radhika Nagpal等人提出的[4]。此算法是通過計算未知節(jié)點與錨節(jié)點之間的跳數(shù)，估計平均每跳距離，用未知節(jié)點與錨節(jié)點之間的跳數(shù)乘以平均每跳距離來計算未知節(jié)點到錨節(jié)點的距離，再利用最小二乘法來計算位置節(jié)點的未知。Amorphous定位算法簡單，無需測距，實現(xiàn)容易。

現(xiàn)階段對Amorphous定位算法的改進方法主要有：跳數(shù)修正[5]；將已定位的未知節(jié)點轉(zhuǎn)化為錨節(jié)點來幫助其他節(jié)點進行定位[6]；而對Amorphous定位算法本身的參數(shù)優(yōu)化研究較少。

本文詳細分析了Amorphous定位算法本身的參數(shù)，并通過仿真對參數(shù)進行優(yōu)化。仿真結(jié)果表明，通過參數(shù)優(yōu)化可以有效的提高Amorphous定位算法的定位精度。

二、Amorphous定位算法步驟

Amorphous[4-6]定位算法計算未知節(jié)點的位置的過程可以分為下面三個步驟：

1、計算未知節(jié)點到各個錨節(jié)點的跳數(shù)

網(wǎng)絡(luò)中的錨節(jié)點周期性的向鄰居節(jié)點發(fā)送攜帶位置信息的跳數(shù)數(shù)據(jù)包，并且在初始化時將跳數(shù)值設(shè)置為0，當(dāng)錨節(jié)點的鄰居節(jié)點首次收到此廣播信息后，首先更新自身到錨節(jié)點的最小跳數(shù)和對應(yīng)的錨節(jié)點的信息，然后再將更新后的信息轉(zhuǎn)發(fā)給其鄰居節(jié)點，直到檢測區(qū)域內(nèi)所有待定位的節(jié)點都得到其到各錨節(jié)點的最小跳數(shù)。然后利用下式計算未知節(jié)點到各錨節(jié)點的跳數(shù)：

其中，s(i, k)—未知節(jié)點i到錨節(jié)點k的跳數(shù)；

h(j, k)—未知節(jié)點j到錨節(jié)點的k的最小跳數(shù)；

h(i, k)—未知節(jié)點i到錨節(jié)點k的最小跳數(shù)；

nbrs(i) —未知節(jié)點i的鄰居節(jié)點的集合；

|nbrs( i)|—未知節(jié)點i的鄰居節(jié)點的數(shù)目。

2、估算平均每跳距離

Amorphous算法是離線計算網(wǎng)絡(luò)每跳距離的，它需要在網(wǎng)絡(luò)部署之前就知道網(wǎng)絡(luò)的平均連通度，下式可以離線計算網(wǎng)絡(luò)平均連通度：

其中，nlocal—網(wǎng)絡(luò)的平均連通度；

n—節(jié)點總數(shù)；

S—檢測區(qū)域的面積；R—節(jié)點的通信半徑。

然后，用下式計算平均每跳距離：

其中，HopSize—平均每跳距離；

nlocal—網(wǎng)絡(luò)的平均連通度；

R—節(jié)點的通信半徑。

Amorphous算法根據(jù)未知節(jié)點到各個錨節(jié)點的跳數(shù)和平均每跳距離來計算未知節(jié)點到各個錨節(jié)點的距離，計算公式如下：

其中，d(i,k)—未知節(jié)點i到錨節(jié)點k的距離；

HopSize—平均每跳距離；

s(i, k)—未知節(jié)點i到錨節(jié)點k的跳數(shù)；

3、計算未知節(jié)點的位置。

當(dāng)未知節(jié)點獲得到至少3個錨節(jié)點的距離時，可以通過最小二乘法來計算未知節(jié)點的坐標(biāo)。未知節(jié)點X=(x，y)T的坐標(biāo)可以通過下面的公式計算得到：

其中，(xn , yn) —表示第n個錨節(jié)點的坐標(biāo)；

dn—表示未知節(jié)點到第n個錨節(jié)點的距離。

分別用公式（5）前(n-1)個方程減去最后一個方程，得：

式（6）的線性方程可以表示成

未知節(jié)點X 的坐標(biāo)可以用標(biāo)準(zhǔn)的最小均方差估計方法得到，計算公式如下：

三、Amorphous算法的參數(shù)分析

1、錨節(jié)點的數(shù)目

Amorphous算法中，未知節(jié)點的位置是通過求解AX=b得到的。因為所有節(jié)點都是隨機分布的，當(dāng)有些錨節(jié)點的位置重疊或者距離很近，或者有些錨節(jié)點分布在一條直線上時，使得包含錨節(jié)點位置信息的矩陣A在求逆矩陣的時候出現(xiàn)奇異矩陣或者NAN等情況，進而影響未知節(jié)點的定位精度。

2、節(jié)點的通信半徑

因為節(jié)點的跳數(shù)和節(jié)點的通信半徑是有關(guān)系的，節(jié)點的通信半徑發(fā)生變化時，節(jié)點之間的跳數(shù)也會發(fā)生變化。如圖1所示，虛線圓表示1號節(jié)點的通信半徑，圖1（a）的節(jié)點通信半徑大于圖1（b）的節(jié)點通信半徑，1號節(jié)點和2號節(jié)點的跳數(shù)在圖1（a）中是1跳，在圖1（b）中是兩跳。而Amorphous算法正是利用未知節(jié)點與錨節(jié)點的跳數(shù)來計算未知節(jié)點的位置，所以節(jié)點的通信半徑對定位精度有著很大的影響。

3、總節(jié)點的數(shù)目

如圖2所示，虛線圓表示黑色未知節(jié)點的通信半徑，從圖2中可以看出，當(dāng)圖2（a）和圖2（b）的節(jié)點通信半徑相同時，黑色未知節(jié)點的鄰居節(jié)點數(shù)目不同，那么根據(jù)式（1）計算得出的黑色未知節(jié)點到錨節(jié)點k的跳數(shù)就會不同。進而最終得到的未知節(jié)點的定位精度就會不同。

四、仿真結(jié)果與分析

在100m×100m的無線傳感器網(wǎng)絡(luò)監(jiān)測范圍內(nèi)，節(jié)點隨機的分布，利用MATLAB 仿真工具，給出了當(dāng)錨節(jié)點個數(shù)、節(jié)點通信半徑和總節(jié)點數(shù)發(fā)生變化時，利用Amorphous算法得到的節(jié)點的定位誤差的變化，仿真中給出的每一個數(shù)值都是50次仿真結(jié)果求得的平均值，并且給出了仿真結(jié)果分析。

當(dāng)總節(jié)點個數(shù)為100，錨節(jié)點個數(shù)從3～30變化時，分別對節(jié)點通信半徑R為20m、30m、40m時節(jié)點的定位誤差進行了仿真。仿真結(jié)果如圖3所示。

從圖3中可以看出，節(jié)點通信半徑不同時，當(dāng)錨節(jié)點個數(shù)為10時，定位誤差能達到較小值；當(dāng)錨節(jié)點個數(shù)從3～8變化時，節(jié)點定位誤差迅速減少；當(dāng)錨節(jié)點個數(shù)繼續(xù)增加時，定位誤差趨于平緩。說明通信半徑不同，當(dāng)錨節(jié)點達到一定數(shù)量時，其對節(jié)點定位誤差的影響將減小。

當(dāng)節(jié)點通信半徑為30m，錨節(jié)點個數(shù)從3～30變化時，分別對總節(jié)點數(shù)n為100、250、400時節(jié)點的定位誤差進行了仿真。仿真結(jié)果如圖4所示。

從圖4中可以看出，總節(jié)點數(shù)目不同時，當(dāng)錨節(jié)點個數(shù)為10時，定位誤差能達到較小值；當(dāng)錨節(jié)點個數(shù)從3～8變化時，節(jié)點定位誤差迅速減少；當(dāng)錨節(jié)點個數(shù)繼續(xù)增加時，定位誤差趨于平緩。說明總節(jié)點數(shù)目不同，當(dāng)錨節(jié)點達到一定數(shù)量時，其對節(jié)點定位誤差的影響將減小。

從圖3和圖4可以看出，當(dāng)節(jié)點通信半徑和總節(jié)點個數(shù)發(fā)生變化時，錨節(jié)點個數(shù)為10時，節(jié)點的定位誤差能降到較小值。因為錨節(jié)點自身的成本比一般節(jié)點要高，所以在100m×100m的監(jiān)測區(qū)域中，利用Amorphous算法進行定位時，取10個錨節(jié)點即可。

當(dāng)總節(jié)點個數(shù)為100，通信半徑從14～50變化時，分別對錨節(jié)點個數(shù)為7、10、13時節(jié)點的定位誤差進行了仿真。仿真結(jié)果如圖5所示。

從圖5中可以看出，當(dāng)通信半徑從14～20m變化時，節(jié)點定位誤差迅速減小，并且在通信半徑為23m時定位誤差達到了最小值，當(dāng)通信半徑繼續(xù)增加時，節(jié)點的定位誤差呈上升的趨勢。說明在總節(jié)點個數(shù)為100，錨節(jié)點個數(shù)不同時，存在最優(yōu)的通信半徑。

由圖3、4和5可以得出，在100m×100m的監(jiān)測區(qū)域中，總節(jié)點個數(shù)為100時，隨機分布10個錨節(jié)點，節(jié)點通信半徑為23m時，定位誤差可以達到較小值。

當(dāng)錨節(jié)點個數(shù)為10且通信半徑發(fā)生變化的情況下，對總節(jié)點個數(shù)為100、250、400時節(jié)點的定位誤差進行了仿真。仿真結(jié)果如圖6所示。

從圖6中可以看出，總節(jié)點個數(shù)不同時，節(jié)點的最優(yōu)通信半徑也不同。當(dāng)總節(jié)點個數(shù)為100時，在通信半徑為23m時，節(jié)點定位誤差可以達到較小值。當(dāng)總節(jié)點個數(shù)為250時，在通信半徑為16m時，節(jié)點定位誤差可以達到較小值。當(dāng)總節(jié)點個數(shù)為400時，在通信半徑為13m時，節(jié)點定位誤差可以達到較小值。

五、結(jié)論

本文對基于Amorphous的無線傳感器網(wǎng)絡(luò)定位算法進行了研究。 仿真結(jié)果表明，在100m×100m的無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域內(nèi)，當(dāng)錨節(jié)點個數(shù)連續(xù)變化時，在不同的總節(jié)點數(shù)目和通信半徑下，錨節(jié)點數(shù)目達到一定數(shù)量時，其對節(jié)點定位誤差的影響將減??；當(dāng)通信半徑連續(xù)變化時，總節(jié)點數(shù)目為100時，在不同的錨節(jié)點個數(shù)下，存在最優(yōu)通信半徑使定位誤差達到最小值；當(dāng)通信半徑連續(xù)變化時，錨節(jié)點個數(shù)為10時，在不同的總節(jié)點個數(shù)下，存在不同的最優(yōu)節(jié)點通信半徑使定位誤差達到最小值。所以利用最優(yōu)節(jié)點通信半徑使定位誤差達到最小值。所以利用Amorphous算法進行定位時，由于傳感器節(jié)點本身能量的限制和錨節(jié)點成本較高的原因，可以選擇較優(yōu)的參數(shù)來降低節(jié)點的定位誤差。