杜鵑搜索在無線傳感器網(wǎng)絡定位問題中的應用

徐行健,紀兆華,孟繁軍

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

0 引 言

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

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

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

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

1 方 法

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

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

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

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

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

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

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

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

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

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

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

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

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

8.END IF

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

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

11.隨機生成一個點代替最壞點bad,更新相應的fbest;

12.END IF

13.END FOR

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

OUTPUT target-cal。

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

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

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

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

(1)

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

Pnew=Pold+stepsizePmorm

(2)

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

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

圖1 本文算法對目標點的逼近

2 驗 證

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

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

圖2 模擬實驗的結果

2.1 定位結果的評價

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

GPR=Ngood/Nl

(3)

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

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

通過算法的分析可以知道,巢中蛋的數(shù)目n只要不是很少,對算法定位效率的影響不明顯,這和粒子群算法中得出的結論一致。保持算法的其他參數(shù)不變,只改變參數(shù)n的大小,得到的實驗結果見表1所列。當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)的結果,絕大多數(shù)的點都得到了精確定位。迭代次數(shù)過少會使算法過早收斂,迭代次數(shù)過多則浪費時間。通過算法的時間復雜度分析可知,算法的時間復雜度是O(Nn-gen),N為目標節(jié)點的個數(shù)。下文的模擬實驗中,使用的迭代次數(shù)統(tǒng)一為2 000。

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

2.4 隨機行走步值stepsize對算法的影響

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

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

2.5 干擾值noise對算法的影響

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

(4)

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

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

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

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

(a) 好點率

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

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

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

3 結 語

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