徐行健,紀(jì)兆華,孟繁軍

(1.內(nèi)蒙古師范大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院,內(nèi)蒙古 呼和浩特 010022; 2.北京信息職業(yè)技術(shù)學(xué)院 計算機(jī)與通信學(xué)院,北京 100000)

0 引 言

由于近年來射頻技術(shù)、嵌入式制造工藝、微電子技術(shù)的發(fā)展,無線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)的應(yīng)用范圍更加廣闊,被廣泛運(yùn)用于各種探測任務(wù),如搜索、營救、災(zāi)后重建、環(huán)境監(jiān)測、目標(biāo)跟蹤[1-2],其中包括了大量的民用和軍用項目。與傳統(tǒng)的無線網(wǎng)絡(luò)相比,無線傳感器網(wǎng)絡(luò)有如下不同:① 一般情況下,它比傳統(tǒng)的無線網(wǎng)絡(luò)包含了更多的節(jié)點;② 因為各個節(jié)點主要采取電池供電,所以它們在設(shè)計的時候,必須考慮節(jié)能的問題;③ 節(jié)點所處的環(huán)境不確定性往往很大,在一些設(shè)計用途中甚至可以說是惡劣的,這就導(dǎo)致定位信號可能存在一些誤差。無線傳感器網(wǎng)絡(luò)的主要特點有[3]:① 規(guī)模大。有大量的節(jié)點被部署在廣大的范圍內(nèi),這有利于增加系統(tǒng)的高可用性,同時也減少了監(jiān)測盲區(qū)。②自組織。無線傳感器網(wǎng)絡(luò)由其內(nèi)節(jié)點自主創(chuàng)建,不存在或無法進(jìn)行人工干預(yù)。③ 高動態(tài)。出現(xiàn)故障或者電池用完的節(jié)點會自動退出網(wǎng)絡(luò)系統(tǒng),同時也可以根據(jù)任務(wù)情況,實時添加新節(jié)點到網(wǎng)絡(luò)中。

只有在精確定位了傳感器位置的前提下,人們才能有效利用傳感器傳回的數(shù)據(jù),而那些被定位錯誤的傳感器傳回的信息往往都是無效的。因此無線傳感器網(wǎng)絡(luò)中的一項基礎(chǔ)研究就是傳感器的定位問題。目前定位算法主要分為基于測距技術(shù)的定位算法和無需測距技術(shù)的定位?；跍y距技術(shù)的定位算法主要利用了三角法或者最大似然法求得節(jié)點坐標(biāo),如AHLOS、RSSI、TOA[4],而無需測距技術(shù)的定位算法主要利用了傳感器網(wǎng)絡(luò)的連通性來求解坐標(biāo),如APIT、DV-HOP[5],其中基于測距技術(shù)的算法使用場景更為廣泛[6-7]。

然而傳統(tǒng)的無線傳感器定位算法存在著較多問題,如定位精度不夠高、算法運(yùn)行時效率較低等缺點。為了克服這些缺點,近年來效果較好的方法是采用元啟發(fā)式搜索[8-9]。元啟發(fā)式算法的主要思想是:在很難獲得最優(yōu)解或者求最優(yōu)解的算法復(fù)雜度太高的情況下,放棄求最優(yōu)解,轉(zhuǎn)而在短時間內(nèi)去求得一個次優(yōu)解[4]。如果算法設(shè)計得當(dāng)、參數(shù)合理的話,那么元啟發(fā)式算法可以在一個很短的時間內(nèi)求得一個極為逼近最優(yōu)解的次優(yōu)解。

杜鵑搜索算法[10]是近來提出的一類元啟發(fā)式算法,它模仿了自然界中杜鵑繁衍的過程:杜鵑會將自己的蛋放到別的鳥的蛋巢里,而且杜鵑的蛋會盡量模仿該蛋巢中其他蛋的樣子;當(dāng)該蛋巢的鳥回巢后,有一定概率會將蛋巢內(nèi)最不像自己種類的蛋踢出蛋巢,而最像的蛋會得到優(yōu)先撫育。因為杜鵑搜索算法是一種基于群體的元啟發(fā)式算法(類似遺傳算法或者粒子群算法)[11-12],同時也引入了一些其他類型啟發(fā)式搜索算法的優(yōu)點,所以杜鵑搜索算法被認(rèn)為是一種極具潛力的最優(yōu)解尋找算法[13]。本文基于杜鵑搜索算法,設(shè)計和實現(xiàn)了一套新的無線傳感器定位算法,經(jīng)過實驗驗證,其有著更加優(yōu)秀的定位精度與運(yùn)行時效率。

1 方 法

無線傳感器網(wǎng)絡(luò)有很多種構(gòu)建模式,本文算法是基于如下一種常見的傳感器網(wǎng)絡(luò)設(shè)計的，即監(jiān)測域中部署了大量的節(jié)點,但是這些節(jié)點的具體位置坐標(biāo)是不可知的。因為人工定位節(jié)點是不現(xiàn)實的,所以利用GPS的方式來獲取節(jié)點位置。由于GPS模塊價格較高,并不能給所有的節(jié)點都搭載GPS定位模塊,而是給網(wǎng)絡(luò)中的一部分節(jié)點搭載。通常稱這些搭載GPS的節(jié)點為錨定節(jié)點(anchor node),其他需要利用錨定節(jié)點來定位自身的節(jié)點成為目標(biāo)節(jié)點(target node)。目標(biāo)節(jié)點可以通過和錨定節(jié)點進(jìn)行通信,來估算出自己和錨定節(jié)點間的距離,進(jìn)一步通過不同的算法在監(jiān)測域中進(jìn)行準(zhǔn)確定位。

在基于距離的定位算法中,傳感器節(jié)點有2個參數(shù)比較重要,一個是傳感器定位信號的精度,另一個是傳感器信號的傳播范圍。這2個參數(shù)一般呈反比,精度高的傳感器其信號傳播范圍較短,而信號傳播范圍較廣的傳感器其精度一般較低。定位信號的精度直接影響了算法定位的準(zhǔn)確性,本文在模擬實驗部分也會討論這一點。而信號的傳播范圍,決定了監(jiān)測域內(nèi)所要投放的錨定節(jié)點的數(shù)目。一個目標(biāo)節(jié)點只有成功地與3個或者3個以上的錨定節(jié)點成功通信,得到相應(yīng)的距離后,才能被算法定位,因此信號范圍越廣,目標(biāo)節(jié)點就會成功地聯(lián)系到更多的錨定節(jié)點。

本文設(shè)計和實現(xiàn)的算法是基于SCIPY[14]編寫的,SCIPY是一個Matlab的開源免費(fèi)替代軟件。利用偽代碼算法可以求得一個目標(biāo)節(jié)點的坐標(biāo)。對傳感器網(wǎng)絡(luò)中所有節(jié)點利用如下算法進(jìn)行逐個定位后,即得到了各個節(jié)點的估計位置,完成定位任務(wù)?；诙霹N搜索的無線傳感器定位算法如下：

輸入:標(biāo)節(jié)點和錨定節(jié)點的距離數(shù)組m-target。

輸出:目標(biāo)節(jié)點的估計坐標(biāo)target-cal。

1.初始化一個n×2的矩陣nest保存n個點的二維坐標(biāo);

2.初始化一個n維數(shù)組fbest保存nest中每個點的目標(biāo)函數(shù)值;

3.FOR迭代循環(huán)n-gen次

4.根據(jù)fbest里最小值出現(xiàn)的位置選擇當(dāng)前的最佳點a;

5.隨機(jī)選擇一個不同于點a的點b;

IF點c的目標(biāo)函數(shù)值小于點b的目標(biāo)函數(shù)值 THEN

6.在點a周圍利用隨機(jī)行走的方法生產(chǎn)點c;

7.用點c代替點b存儲在nest中,更新fbest中對應(yīng)的目標(biāo)函數(shù)值;

8.END IF

9.IF生成了一個在[0,1]區(qū)間內(nèi)的小于常數(shù)pa的隨機(jī)數(shù) THEN

10.根據(jù)fbest里最大值出現(xiàn)的位置選擇當(dāng)前的最壞點bad;

11.隨機(jī)生成一個點代替最壞點bad,更新相應(yīng)的fbest;

12.END IF

13.END FOR

14.根據(jù)fbest里最小值出現(xiàn)的位置選擇當(dāng)前的最佳點target-cal;

OUTPUT target-cal。

上述算法主要有以下3個要點。

(1) 迭代次數(shù)n-gen。迭代次數(shù)是影響算法最后能否收斂的主要因素之一。如果迭代次數(shù)過小,算法還沒有收斂就已經(jīng)結(jié)束,那么得到的定位值不準(zhǔn)確;如果迭代次數(shù)過大,會讓算法再收斂后繼續(xù)迭代,那么使運(yùn)行時間顯著增加,造成不必要的浪費(fèi)。迭代次數(shù)的取值必須根據(jù)經(jīng)驗確定,下文的模擬實驗中會詳細(xì)討論。

(2)目標(biāo)函數(shù)f(x,y)。目標(biāo)函數(shù)的作用是評價每個估計坐標(biāo)點的好壞程度,如果一個坐標(biāo)能讓目標(biāo)函數(shù)擁有更小的值,那么這個坐標(biāo)就更加接近于目標(biāo)節(jié)點真實的坐標(biāo)。

本文算法采用的目標(biāo)函數(shù)為：

(1)

(3) 隨機(jī)行走。用隨機(jī)行走的方法來產(chǎn)生一個最佳點附近的點。隨機(jī)行走方法可以選擇基于正態(tài)分布的隨機(jī)行走,也可以選擇基于Levy飛行的隨機(jī)行走。在實際的測試當(dāng)中,發(fā)現(xiàn)對于無線傳感器定位問題,采用基于正態(tài)分布的隨機(jī)行走,效果更加。因此本算法采用基于正態(tài)分布的隨機(jī)行走，即

Pnew=Pold+stepsizePmorm

(2)

其中:stepsize為隨機(jī)行走步值;Pnew為新生成的點;Pold為起始點;Pnorm為一個從二維正態(tài)分布中隨機(jī)抽取的點。

模擬實驗的結(jié)果如圖1所示,其中：“□”表示目標(biāo)節(jié)點的實際位置；“×”表示算法定位出的目標(biāo)節(jié)點位置；實心“·”表示錨定節(jié)點的位置。該次試驗中用4個錨定節(jié)點去定位12個目標(biāo)節(jié)點,每次定位迭代了2 000個循環(huán)(n-gen),從圖1可以看出效果比較好,1個點被定位出來。對于每個目標(biāo)節(jié)點,算法從(0,0)開始逼近目標(biāo)節(jié)點的真實坐標(biāo),最后收斂于目標(biāo)節(jié)點,中間迭代過程中產(chǎn)生的估計點也被繪制在圖中,產(chǎn)生了一條點跡線,據(jù)此可以直觀地看到算法是如何收斂的。

圖1 本文算法對目標(biāo)點的逼近

2 驗 證

本文的仿真模擬實驗基于SCIPY開發(fā),所有實驗都是在同一臺計算機(jī)(CPU是Intel Xeon E3 1230v2, 4核心8線程, 3.4 GHz主頻, 16 G內(nèi)存)上進(jìn)行的。模擬了一個邊長為R=140(具體的距離量綱在實驗中無關(guān)緊要)的正方形監(jiān)測域,其中每個節(jié)點的信號傳播半徑是r=10,也就是說,如果目標(biāo)節(jié)點和錨定節(jié)點的直線距離在r以內(nèi)的情況下,目標(biāo)節(jié)點可以聯(lián)系到錨定節(jié)點,從而被測距。R為r的1.4倍,這是一個實踐中得出的比較好的經(jīng)驗公式[15-16]。每次試驗總共有目標(biāo)節(jié)點數(shù)n-targets=100,錨定節(jié)點是目標(biāo)節(jié)點的10%,即n-anchors=10,這個百分比也是實踐中經(jīng)常采用的一個數(shù)值。如果錨定節(jié)點過少,會造成大量的目標(biāo)節(jié)點聯(lián)系不到3個或3個以上的錨定節(jié)點,造成無法定位。

當(dāng)n-gen=2 000時,本算法的仿真實驗結(jié)果如圖2所示,從圖2可以看出大多數(shù)目標(biāo)節(jié)點都被準(zhǔn)確定位。仿真實驗表明,當(dāng)R為1.4r時,投放目標(biāo)節(jié)點數(shù)10%的錨定節(jié)點就可以很好地定位出絕大部分目標(biāo)節(jié)點,定位率(可定位目標(biāo)節(jié)點數(shù)和總目標(biāo)節(jié)點數(shù)的比值)達(dá)到了99.14%。

圖2 模擬實驗的結(jié)果

2.1 定位結(jié)果的評價

本文主要使用好點率(good points ratio,GPR)來評價定位結(jié)果的精度，計算公式為:

GPR=Ngood/Nl

(3)

其中:Nl為該次模擬實驗中總共被定位出的點(也就是處于3個或3個以上錨定節(jié)點信號范圍以內(nèi)的點)的總數(shù);Ngood為好點的總數(shù)。若某點算法定位出的坐標(biāo)和該點真實坐標(biāo)間的歐幾里得距離小于節(jié)點信號范圍0.001[3],則稱算法定位出了一個好點(GP)。根據(jù)無線傳感器的通訊原理,隨著傳感器信號范圍的變大,其本身的定位信號被干擾的程度就會越大。若好點率過小,則說明大多數(shù)無線傳感器都沒有被精確地定位到,因此好點率直接反應(yīng)了算法定位的好壞。

2.2 鳥巢中蛋的數(shù)目n對算法的影響

通過算法的分析可以知道,巢中蛋的數(shù)目n只要不是很少,對算法定位效率的影響不明顯,這和粒子群算法中得出的結(jié)論一致。保持算法的其他參數(shù)不變,只改變參數(shù)n的大小,得到的實驗結(jié)果見表1所列。當(dāng)n=20時,好點率就已經(jīng)穩(wěn)定在97%左右。因此下文中其他的模擬實驗統(tǒng)一選擇n=20。

表1 蛋的數(shù)目n對算法的影響(基于10次實驗)

2.3 迭代次數(shù)n-gen對算法的影響

迭代次數(shù)n-gen是影響算法定位效果的主要因素之一。箱線圖如圖3所示，從圖3可以看出，n-gen在2 000和3 000的時候好點率的均值和方差都取得了較優(yōu)的結(jié)果,絕大多數(shù)的點都得到了精確定位。迭代次數(shù)過少會使算法過早收斂,迭代次數(shù)過多則浪費(fèi)時間。通過算法的時間復(fù)雜度分析可知,算法的時間復(fù)雜度是O(Nn-gen),N為目標(biāo)節(jié)點的個數(shù)。下文的模擬實驗中,使用的迭代次數(shù)統(tǒng)一為2 000。

圖3 n-gen對算法好點率的影響

2.4 隨機(jī)行走步值stepsize對算法的影響

隨機(jī)行走步值也會影響算法定位。如果步值過小,那么在有限的迭代循環(huán)里,收斂過慢；如果過大,那么有更大的概率錯過最優(yōu)解,算法的收斂也很慢。步值stepsize對算法好點率的影響如圖4所示，從圖4可以看出,在迭代次數(shù)為2 000的時候,步值為0.5的效果比較好。

圖4 步值stepsize對算法好點率的影響

2.5 干擾值noise對算法的影響

在上面的實驗中,均沒有模擬測距信號被干擾時的情況(即干擾值為0)。本組模擬實驗中,按照(4)式產(chǎn)生了定量的干擾，即

(4)

其中:d為目標(biāo)節(jié)點和錨定節(jié)點間的歐幾里得距離;noise為干擾值；randnorm為一個服從標(biāo)準(zhǔn)正態(tài)分布中隨機(jī)采樣得到的隨機(jī)值。通過(4)式,可以產(chǎn)生了一個被干擾后的距離。干擾值noise對算法好點率的影響見表2所示，從表2可以看出,當(dāng)干擾過高時,好點率顯著降低。

表2 干擾值noise對算法好點率的影響(基于10次實驗)

2.6 本文方法和其他方法的比較測試

各個方法的好點率和運(yùn)行時間的比較如圖5所示。

(a) 好點率

(b) 運(yùn)行時間圖5 各個方法好點率和運(yùn)行時間的比較

本文的方法(CUCK迭代次數(shù)為2 000,步值為0.5)和以往的幾個具有代表性的方法進(jìn)行比較。選取用來對比的方法有三角測量法(TRI)[6]、最大似然法(ML)[6]、基于遺傳算法的定位方法(GA)[9]。三角測量法和最大似然法在相應(yīng)的參考文獻(xiàn)中均有可以直接使用的程序用來測試,而基于遺傳算法的定位方法,并沒有直接可用的測試程序,因此根據(jù)參考文獻(xiàn)中的偽代碼實現(xiàn)一個測試程序。為了使各個算法的差異表現(xiàn)得更加顯著,本次實驗對在邊長為1 400的正方形檢測域分布的1 000個節(jié)點(其中有100個已知坐標(biāo)的錨定節(jié)點)進(jìn)行了定位,每個方法重復(fù)進(jìn)行20次,模擬測試數(shù)據(jù)的干擾值設(shè)置為0.001。本次測試主要對各個方法的好點率以及所需時間進(jìn)行了比較。

從圖5可以看出,本文的方法在定位精度(好點率)方面和經(jīng)典的基于距離的定位方法較為相似,而在運(yùn)行時間上,大幅度領(lǐng)先三角測距法和最大似然法。和遺傳算法相比,運(yùn)行時間雖然略差,但是定位精度卻有所提高。這充分體現(xiàn)了元啟發(fā)式搜索在短時間內(nèi)尋找次優(yōu)解的強(qiáng)大優(yōu)勢。傳統(tǒng)的最大似然法雖然定位精度非常高,但是求解過程需要進(jìn)行大量的迭代優(yōu)化計算,所需運(yùn)行時間太長,導(dǎo)致這種方法在實時性要求比較嚴(yán)格的環(huán)境下應(yīng)用受到很大限制,而本方法只需極短的時間就可以得出一個和最大似然法相差不大的定位結(jié)果。

3 結(jié) 語

本文基于杜鵑搜索,設(shè)計和實現(xiàn)了一套新型無線傳感器定位算法；該算法具有定位準(zhǔn)確、結(jié)果穩(wěn)定和運(yùn)行時效率高等特點。通過一系列的模擬仿真實驗,相比于其他基于測距的無線傳感器定位算法,本文提出的算法在無線傳感器網(wǎng)絡(luò)定位問題中有著更加良好的表現(xiàn)。在實驗驗證的基礎(chǔ)上,給出了算法中各個主要參數(shù)的最佳參考值,可以提供給其他科研或者工程人員使用。本算法的并行化程度很高,在接下來的工作中,可以對該算法并行化,達(dá)到一個更加優(yōu)秀的并行加速比[17],從而進(jìn)一步提高算法的效率?？梢钥紤]采用GPU編程[18]或者諸如Hadoop[19]這種分布式計算的方式,應(yīng)用到超大傳感器網(wǎng)絡(luò)中,實現(xiàn)節(jié)點的快速高精度定位。