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

一、引言

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

無線傳感器網(wǎng)絡(luò)的關(guān)鍵支撐技術(shù)之一是定位問題，定位問題也是無線傳感器網(wǎng)絡(luò)應(yīng)用以及其他研究的基礎(chǔ)，如地理環(huán)境監(jiān)測、軍事偵察、交通路況監(jiān)測、搶險(xiǎ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ò)中，為每個(gè)傳感器節(jié)點(diǎn)都安裝GPS設(shè)備是不太實(shí)際的方法。所以現(xiàn)有的一些定位方法中只是讓少數(shù)傳感器節(jié)點(diǎn)配備有GPS設(shè)備，然后通過一些數(shù)學(xué)的方式來估算未知傳感器節(jié)點(diǎn)的位置。

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

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

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

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

二、Amorphous定位算法步驟

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

1、計(jì)算未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的跳數(shù)

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

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

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

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

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

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

2、估算平均每跳距離

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

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

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

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

然后，用下式計(jì)算平均每跳距離：

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

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

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

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

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

HopSize—平均每跳距離；

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

3、計(jì)算未知節(jié)點(diǎn)的位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、結(jié)論

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