單志龍 劉蘭輝 張迎勝 黃廣雄
?
一種使用灰度預(yù)測模型的強(qiáng)自適應(yīng)性移動節(jié)點定位算法
單志龍 劉蘭輝*張迎勝 黃廣雄
(華南師范大學(xué)計算機(jī)學(xué)院 廣州 510631)
定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù),而關(guān)于移動節(jié)點的定位又是其中的技術(shù)難點。該文針對移動節(jié)點定位問題提出基于灰度預(yù)測模型的強(qiáng)自適應(yīng)性移動節(jié)點定位算法(GPLA)。算法在基于蒙特卡羅定位思想的基礎(chǔ)上,利用灰度預(yù)測模型進(jìn)行運(yùn)動預(yù)測,精確采樣區(qū)域,用估計距離進(jìn)行濾波,提高采樣粒子的有效性,通過限制性的線性交叉操作來生成新粒子,從而加快樣本生成,減少采樣次數(shù),提高算法效率。仿真實驗中,該算法在通信半徑、錨節(jié)點密度、樣本大小等條件變化的情況下,表現(xiàn)出較好的性能與較強(qiáng)的自適應(yīng)性。
無線傳感網(wǎng)絡(luò);定位;移動節(jié)點;灰度預(yù)測
集成了傳感器、微機(jī)電系統(tǒng)和網(wǎng)絡(luò)3大技術(shù)的無線傳感器網(wǎng)絡(luò)(WSN)是一種全新的信息獲取和處理技術(shù)[1],它由大量部署在監(jiān)控區(qū)域的傳感器節(jié)點組成,通過無線通信方式形成一個多跳自組織網(wǎng)絡(luò)系統(tǒng),協(xié)作感知、采集和處理相關(guān)監(jiān)控信息。WSNs 技術(shù)被眾多重要組織和機(jī)構(gòu)預(yù)測為可以改變世界的核心科技力量[2],其中定位技術(shù)[3]是無線傳感器網(wǎng)絡(luò)的關(guān)鍵支撐技術(shù)。無線傳感器網(wǎng)絡(luò)定位算法主要分為測距算法和非測距算法兩大類。測距算法依賴額外硬件測量節(jié)點間的距離信息,如接收信號強(qiáng)度(RSSI)[4],信號的角度差(AOA)[5],信號到達(dá)時間差(TDOA)[6]等;非測距算法主要根據(jù)節(jié)點的連通性實現(xiàn)節(jié)點定位,定位成本較低,例如質(zhì)心算法[7],APIT算法[8],DV-Hop算法[9],MDS-MAP算法[10]等。
上述定位算法在靜態(tài)網(wǎng)絡(luò)中有較好的效果,但在移動定位中則表現(xiàn)不佳,目前移動定位應(yīng)用最廣泛的是GPS[11]定位,但在WSNs中給傳感器節(jié)點配置GPS模塊由于價格耗費問題使其并不實際,設(shè)計更有效的移動節(jié)點定位算法也成為一個熱點研究問題。Hu等人[12]基于蒙特卡羅算法隨機(jī)化采樣的思想提出了適用于移動傳感器網(wǎng)絡(luò)節(jié)點定位跟蹤的MCL(Monte Carlo Localization)算法,提供了一種很好的研究思路。在此算法的基礎(chǔ)上,李敏等人[13]提出了一種MCLAS算法:采樣時通過參考節(jié)點選擇模型,選取離定位節(jié)點較近且分布均勻的參考節(jié)點構(gòu)成采樣盒,并利用權(quán)重來進(jìn)行位置估計,提高定位精度。王潔等人[14]提出減少采樣區(qū)域提高M(jìn)CL算法的樣本質(zhì)量,同時用遺傳交叉的思想加快生成樣本。劉志華等人[15]提出根據(jù)運(yùn)動的連續(xù)性,利用最小二乘曲線擬合的方法,推算出未知節(jié)點下一時刻可能的位置區(qū)域,進(jìn)行快速抽樣和樣本過濾。朱海平等人[16]提出通過構(gòu)建接收信號強(qiáng)度指示測距模型來限制樣本區(qū)域以提高采樣效率。
本文提出的使用灰度預(yù)測模型的強(qiáng)自適應(yīng)性移動節(jié)點定位算法(strong self-adaptive Localization Algorithm based on Gray Prediction model for mobile node, GPLA)在基于MCL的思想上提出了不同的解決方案:首先,為確定更加精準(zhǔn)的采樣區(qū)域,減少重復(fù)采樣計算量,本文通過記錄待定位節(jié)點前幾個時刻的位置信息利用灰度預(yù)測模型估算出當(dāng)前的運(yùn)動速度和方向,確定大致運(yùn)動區(qū)域,精確采樣空間。然后,使用錨節(jié)點與定位節(jié)點之間的估計距離信息來濾除粒子,提高粒子質(zhì)量和有效性,從而提高定位精度。最后利用限制性的線性交叉來擴(kuò)展粒子數(shù)目,通過粒子團(tuán)防止采樣收斂,形成采樣粒子的多樣性,在減少采樣時間的同時,加快高質(zhì)量樣本生成,達(dá)到更快,更準(zhǔn)確的定位。
蒙特卡羅定位算法的核心思想是:在貝葉斯濾波位置估計的基礎(chǔ)上,把待定節(jié)點可能出現(xiàn)的位置用加權(quán)樣本集的形式表示,用個帶有權(quán)重的離散采樣來估計節(jié)點位置。主要通過預(yù)測階段和濾波階段實現(xiàn)節(jié)點定位。
與其它定位算法相比,蒙特卡羅方法具有其特性:MCL定位算法計算簡單,復(fù)雜性低。定位過程中的收斂速度和粒子采樣對定位環(huán)境依賴性低。算法隨機(jī)性強(qiáng),適合解決節(jié)點運(yùn)動的無規(guī)律問題。定位精度受節(jié)點移動性影響不大,而定位過程中充分利用了節(jié)點移動特性和與其它節(jié)點的連通特性。能夠在節(jié)點存儲空間非常有限、錨節(jié)點分布密度較低的情況下實現(xiàn)移動節(jié)點的定位。這些特性使MCL算法思想很適合應(yīng)用到節(jié)點移動定位中,具有較大的發(fā)展?jié)摿?。在?jīng)過不斷的研究后,會更大程度地提高節(jié)點定位精度。
GPLA算法通過灰度預(yù)測模型預(yù)測未知節(jié)點的運(yùn)動狀況,提高采樣的準(zhǔn)確性,通過估計距離進(jìn)行濾波增加定位精度,在限制性的線性交叉操作下,生成有效性粒子,減少采樣次數(shù),整個算法環(huán)環(huán)相扣,具有較強(qiáng)的自適應(yīng)性,在提高定位精度的同時減少定位時間。
傳感器節(jié)點的移動過程大多數(shù)情況下都是與前面幾個時刻的位置有關(guān)聯(lián)的,在某種程度上可以看作是基于時間序列短暫連續(xù)的。假設(shè)節(jié)點的運(yùn)動平滑、連續(xù),則可以借助前面幾個時刻的位置信息預(yù)測當(dāng)前時刻的運(yùn)動狀況?;疑A(yù)測[17]通過鑒別因素之間發(fā)展趨勢的相異程度,對原始數(shù)據(jù)進(jìn)行生成處理來尋找系統(tǒng)變動的規(guī)律,生成有較強(qiáng)規(guī)律性的數(shù)據(jù)序列,然后建立相應(yīng)的微分方程模型,從而預(yù)測事物未來發(fā)展趨勢。它可以解決信息貧乏的不確定性、隨機(jī)性強(qiáng)問題,且對環(huán)境因素的依賴性較小,這非常適合移動節(jié)點定位時的時序性和隨機(jī)性,且只需要記錄前面幾個時刻的數(shù)據(jù)信息,再通過微分方程模型來預(yù)測當(dāng)前時刻數(shù)據(jù),這樣不會增加節(jié)點負(fù)載和計算量。
(1)通過歷史記錄信息,對數(shù)據(jù)累加構(gòu)造累加生成序列:
(2)構(gòu)造數(shù)據(jù)矩陣和數(shù)據(jù)向量:
(3)計算參數(shù):
符合上述條件的采樣集合可描述為
在時刻,預(yù)測位置也必然會處于它偵聽到的所有錨節(jié)點估計距離范圍內(nèi),如果不在該相交區(qū)域,則該采樣點不符合條件,要去除掉。如果采樣粒子不在上述區(qū)域,分布概率()0,在區(qū)域則為1,分布概率則表述為
當(dāng)滿足濾波條件的采樣粒子達(dá)到一定數(shù)目(/4~/2)后進(jìn)行限制性線性交叉操作:在通過濾波條件的采樣粒子群內(nèi)選取粒子對,并在其內(nèi)部連線上按交叉因子產(chǎn)生新的粒子,新粒子必然位于粒子對之間,也必定是符合濾波條件的,就不再需要重新濾波驗證,這樣在加快樣本生成的同時,也減少了計算量,另外,為了避免采樣局部化,通過劃分粒子團(tuán)來限制粒子對的生成次數(shù),由同一粒子和其產(chǎn)生的新粒子視為一個團(tuán),以此來限制多次交叉后粒子弱化。具體操作如下:
在滿足濾波條件的粒子集合中選取權(quán)值較高的一部分作為初始集群,從中隨機(jī)選擇兩個粒子進(jìn)行線性交叉操作:
其中(x,y), (x,y)為樣本粒子坐標(biāo),為交叉因子,取值范圍為[0.2,0.8], (x,y)為新粒子坐標(biāo)。
采用線性交叉時,同一對粒子與它們交叉生成的新粒子歸為一個粒子團(tuán),團(tuán)內(nèi)進(jìn)行2~3次交叉后將不再進(jìn)行交叉,即團(tuán)內(nèi)最多只能生成3個新粒子,然后再與其它團(tuán)的粒子組成新粒子對進(jìn)行交叉操作。這樣可以減緩交叉的收斂速度,保持樣本的多樣性。如圖2所示,圓點表示采樣粒子,四角形表示節(jié)點真實位置,三角形是遺傳交叉新生成的粒子,橢圓形內(nèi)是團(tuán),團(tuán)與團(tuán)之間可以進(jìn)行交叉,經(jīng)過限制性線性交叉方法生成的粒子都是符合濾波條件的,不用再進(jìn)行驗證操作。限制性線性交叉方式使樣本生成不再容易收斂,同時能保持粒子的多樣性,快速生成樣本集,大幅度地降低算法的運(yùn)算時間和復(fù)雜度。
最后統(tǒng)計的樣本數(shù)如果還是不足,就需要重復(fù)從預(yù)測階段開始,將角度擴(kuò)大一倍在新區(qū)域重新采樣并執(zhí)行后續(xù)操作,反復(fù)直至達(dá)到樣本點的數(shù)目。此時,可計算出移動節(jié)點在時刻的位置:
節(jié)點位置誤差計算公式為
其中,表示節(jié)點通信半徑,(x,y)表示當(dāng)前時刻的估計位置,(,)表示粒子的實際位置。er越小則估計位置越精確。
算法的實驗仿真在MATLAB平臺下進(jìn)行,并同原始MCL算法和EMCL[13]算法進(jìn)行了比較。仿真區(qū)域設(shè)置為250 m×250 m,節(jié)點移動模型采用隨機(jī)waypoint模型,錨節(jié)點的移動速度在[0~5 m/s]之間隨機(jī)選取。默認(rèn)條件的仿真參數(shù)為:節(jié)點總數(shù)CN=250,錨節(jié)點數(shù)CA=50,通信半徑=35 m,未知節(jié)點最大速度max=10 m/s,樣本=25。未知節(jié)點在移動的過程中取20個時間周期進(jìn)行定位,重復(fù)運(yùn)行20次后,取平均獲得仿真結(jié)果。
在移動節(jié)點定位中,通信半徑是對定位精度影響比較大的因素。如圖3所示,隨著半徑的增大,3種算法的定位誤差都在減小,因為節(jié)點通信半徑增大,獲得的觀測信息也增多,能夠排除一些非有效性的粒子。在半徑達(dá)到45 m之后,定位精度開始穩(wěn)定,在整個過程中,GPLA算法的定位誤差比另兩種算法要低,這是因為它充分利用了觀測信息和歷史位置信息,在灰度預(yù)測后的預(yù)測區(qū)域采樣,用估計距離信息代替通信半徑范圍信息進(jìn)行濾波,能夠更進(jìn)一步提高粒子的有效性,因而其定位精度優(yōu)于另兩種算法。
當(dāng)錨節(jié)點數(shù)變化時未知節(jié)點得到的觀測信息也會發(fā)生變化,進(jìn)而會影響濾波環(huán)節(jié)得到的采樣粒子的好壞程度,從圖4可看出,當(dāng)錨節(jié)點數(shù)較少時,GPLA算法和EMCL算法的定位誤差相差不大,因為錨節(jié)點太少時能獲得的觀測信息會減少,在這種情況下,用通信半徑和用估計距離信息進(jìn)行濾波效果相當(dāng),當(dāng)錨節(jié)點增加時,兩種濾波方法的區(qū)別就比較明顯了,GPLA算法中未知節(jié)點根據(jù)與錨節(jié)點的估計距離進(jìn)行濾波,粒子的有效性增加,估計位置就越接近未知節(jié)點的真實位置。
在節(jié)點數(shù)變化對定位誤差影響實驗中,錨節(jié)點始終保持著20%的比例。如圖5所示,3種算法隨著節(jié)點數(shù)增多變化較為平緩,定位精度穩(wěn)步增長。GPLA算法略占優(yōu)勢,由于它在運(yùn)動預(yù)測時運(yùn)用了灰度預(yù)測模型,確定了大致的采樣區(qū)域,相較其它兩種算法的采樣,這種方法產(chǎn)生的粒子有效性更大,總體能保持定位精度上的優(yōu)勢。在結(jié)果中還可以看到3種算法的定位誤差差異基本保持穩(wěn)定,說明節(jié)點數(shù)對算法性能差異影響不大。
圖3 通信半徑與平均定位誤差關(guān)系
圖4 錨節(jié)點數(shù)與平均定位誤差關(guān)系
圖5 節(jié)點數(shù)與平均定位誤差關(guān)系
樣本數(shù)直接影響定位算法的精度,從圖6中可以看出,當(dāng)樣本為25時3種算法的定位誤差趨向于穩(wěn)定,樣本繼續(xù)增加也不會太多地提高定位精度。GPLA算法和EMCL算法隨著樣本增加定位誤差越來越接近,是因為樣本越大,其中包含的有效性粒子也會越多,兩種算法的差異反而越小。樣本的數(shù)量直接影響定位時間,選取合適的樣本數(shù)對移動定位非常關(guān)鍵。
樣本數(shù)對定位時間的影響非常大,實驗對采用不同樣本數(shù)時3種算法的定位時間做了對比。定位時間隨著樣本數(shù)的變化如圖7所示,樣本數(shù)較小時,3種算法定位時間相差不大,樣本數(shù)超過30之后,就有明顯區(qū)別了,GPLA算法用限制性的線性交叉,減少了重采樣的時間消耗,比MCL算法要快很多,限制性線性交叉免去了重濾波的計算時間,因此比EMCL算法稍快。
實驗還對未知節(jié)點在20個時間周期內(nèi)的定位誤差進(jìn)行了對比,1個時間周期為1個步長,為了排除某些參數(shù)的影響,根據(jù)上述實驗的結(jié)果,選取了接近穩(wěn)定時的參數(shù)項,實驗參數(shù)設(shè)置為:CN=250, CA=50,=50 m,=25,max=10 m。結(jié)果如圖8所示。初始定位時,由于缺少先驗值,3種算法定位誤差都比較大,隨著節(jié)點移動,GPLA算法在觀測值增多和自我調(diào)節(jié)適應(yīng)的情況下,很快達(dá)到較好的定位精度,由于它的強(qiáng)自適應(yīng)性,可以保持較好的穩(wěn)定性。另外兩種算法則有不同程度的波動。此外,因為累積誤差的影響,在后續(xù)定位中會使定位誤差小幅度上升。
本文提供了一種針對移動節(jié)點定位的解決方案,其核心是基于蒙特卡羅定位算法的思想,通過灰度預(yù)測模型對節(jié)點運(yùn)動狀態(tài)進(jìn)行預(yù)測、利用估計距離濾波、采用限制性線性交叉加快生成樣本集,提高定位精度的同時,加強(qiáng)節(jié)點定位的自適應(yīng)性,更接近于一種智能化的定位模式。最后通過在通信半徑、錨節(jié)點數(shù)、節(jié)點數(shù)、樣本數(shù)等條件變化的前提下,與其它算法進(jìn)行了誤差對比與分析,結(jié)果表明,GPLA算法在定位精度和定位時間上都有不同程度的提高,說明GPLA算法在某些條件下具有它的價值和優(yōu)勢,當(dāng)然還有需要完善之處,比如如何減少累積誤差的影響,如何使它更適合于稀疏網(wǎng)絡(luò)等,都還需要更多的研究。
圖6 樣本數(shù)與平均定位誤差關(guān)系
圖7 樣本數(shù)與定位時間關(guān)系
圖8 步長與定位誤差關(guān)系
[1] 任豐原, 黃海寧, 林闖. 無線傳感器網(wǎng)絡(luò)[J]. 軟件學(xué)報, 2003, 14(7): 1282-1290.
Ren Feng-yuan, Huang Hai-ning, and Lin Chuang. Wireless sensor networks[J]., 2003, 14(7): 1282-1290.
[2] 錢志鴻, 王義君. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報, 2013, 35(1): 215-227.
Qian Zhi-hong and Wang Yi-jun. Internet of things-oriented wireless sensor networks review[J].&, 2013, 35(1): 215-227.
[3] 彭宇, 王丹. 無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J]. 電子測量與儀器學(xué)報, 2011, 25(5): 389-399.
Peng Yu and Wang Dan. A review: wireless sensor networks localization[J]., 2011, 25(5): 389-399.
[4] Kaltiokallio O and Bocca M. Real-time intrusion detection and tracking in indoor environment through distributed RSSI processing[C]. 2011 IEEE 17th International Conference at Toyama, 2011: 61-70.
[5] 毛永毅, 張穎. 非視距傳播環(huán)境下的AOA定位跟蹤算法[J]. 計算機(jī)應(yīng)用, 2011, 31(2): 317-319.
Mao Yong-Yi and Zhang Ying. AOA location and tracking algorithm in non-line-of-sight propagation environment[J]., 2011, 31(2): 317-319.
[6] Zhang Weile, Yin Qinye, Xue Feng,.. Distributed TDOA estimation for wireless sensor networks based on frequency-hopping in multipath environment[C]. 2010 IEEE 71st, Taipei Vehicular Technology Conference (VTC 2010-Spring), 2010: 16-19.
[7] 程偉, 史浩山, 王慶文, 等. 基于差分修正的傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J]. 系統(tǒng)仿真學(xué)報, 2012, 24(2): 389-393.
Cheng Wei, Shi Hao-shan, Wang Qing-wen,.. Weighted centroid localization algorithm based on difference correction for sensor networks[J]., 2012, 24(2): 389-393.
[8] Cheng W, Li J, and Li H. An improved APIT location algorithm for wireless sensor networks[J].,2012, 139(1): 113-119.
[9] 肖麗萍, 劉曉紅. 一種基于跳數(shù)修正的DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報, 2012, 25(12): 1726-1730.
Xiao Li-ping and Liu Xiao-hong. DV-Hop localization algorithm based on hop amendment[J]., 2012, 25(12): 1726-1730.
[10] Sun Xiao-ling, Chen Tao, Li Wei-qin.. Perfomance research of improved MDS-MAP algorithm in wireless sensor
networks localization[C]. Computer Science and Electronics Engineering (ICCSEE), Hangzhou, 2012: 587-590.
[11] Drawil N M, Amar H M, and Basi O A. GPS localization accuracy classification: a context-based approach[J].2013, 14(1): 262-273.
[12] Hu Ling-xuan and Evans D. Localization for mobile sensor networks[C]. Proceedings of MobiCom 2004, Philadelphia, Pennsylvania, USA, 2004: 45-57.
[13] 李敏, 羅挺, 徐華. 一種基于參考節(jié)點選擇模型的無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報, 2011 24(2): 264-268.
Li Min, Luo Ting, and Xu Hua. Localization algorithm based on anchor node select model for wireless sensor networks[J], 2011, 24(2): 264-268.
[14] 王潔, 王洪玉, 高慶華, 等. 一種適用于移動傳感器網(wǎng)絡(luò)的增強(qiáng)型蒙特卡羅定位跟蹤算法[J]. 電子與信息學(xué)報, 2010, 32(4): 864-868.
Wang Jie, Wang Hong-yu, Gao Qing-hua,. Enhanced monte carlo localization and tracking algorithm for mobile wireless sensor network[J].&, 2010, 32(4): 864-868.
[15] 劉志華, 李改燕. 基于最小二乘法的蒙特卡羅移動節(jié)點定位算法[J]. 傳感技術(shù)學(xué)報, 2012, 25(4): 541-544.
Liu Zhi-hua and Li Gai-yan. Monte-Carlo mobile node localization algorithms based on least squares method[J]., 2012, 25(4): 541-544.
[16] 朱海平, 于紅丞, 鐘小勇, 等. 動態(tài)無線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法[J]. 傳感技術(shù)學(xué)報, 2012, 25(9): 1284-1288.
Zhu Hai-ping, Yu Hong-cheng, Zhong Xiao-yong,.. An improved monte carlo localization algorithm for mobile wireless sensor networks[J]., 2012, 25(9): 1284-1288.
[17] 劉思峰, 郭天榜, 黨耀國, 等. 灰色系統(tǒng)理論及其應(yīng)用[M]. 北京: 科學(xué)出版社, 1999: 44-63.
Liu Si-feng, Guo Tian-bang, Dang Yao-guo,.. Grey System Theory and Its Application[M]. Beijing: Science Press, 1999: 44-63.
單志龍: 男,1976 年生,博士,教授,碩士生導(dǎo)師,研究方向為物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)、無線通信網(wǎng)絡(luò)等.
劉蘭輝: 女,1989年生,碩士生,研究方向為無線傳感器網(wǎng)絡(luò).
張迎勝: 男,1988年生,碩士生,研究方向為無線傳感器網(wǎng)絡(luò).
黃廣雄: 男,1988年生,碩士生,研究方向為無線傳感器網(wǎng)絡(luò).
A Strong Self-adaptivity Localization Algorithm Based on Gray Prediction Model for Mobile Nodes
Shan Zhi-long Liu Lan-hui Zhang Ying-sheng Huang Guang-xiong
(,,510631,)
Localization of sensor nodes is an important issue in Wireless Sensor Networks (WSNs), and positioning of the mobile nodes is one of the difficulties. To deal with this issue, a strong self-adaptive Localization Algorithm based on Gray Prediction model for mobile nodes (GPLA) is proposed. On the background of Monte Carlo Localization Algoritm, gray prediction model is used in GPLA, which can accurate sampling area is used to predict nodes motion situation. In filtering process, estimated distance is taken to improve the validity of the sample particles. Finally, restrictive linear crossover is used to generate new particles, which can accelerate the sampling process, reduce the times of sampling and heighten the efficiency of GPLA. Simulation results show that the algorithm has excellent performance and strong self-adaptivity in different communication radius, anchor node, sample size, and other conditions.
Wireless Sensor Networks (WSN); Localization; Mobile node; Gray prediction
TP393
A
1009-5896(2014)06-1492-06
10.3724/SP.J.1146.2013.01171
劉蘭輝 lanhuilui1989@gmail.com
2013-08-02收到,2014-01-06改回
國家自然科學(xué)基金(61102065),廣州市科技計劃項目(12C42091555),廣州市珠江科技新星專項(2011J2200083) 和廣東省教育部產(chǎn)學(xué)研結(jié)合項目(2011B090400520)資助課題