分享到:

研發圖
聯絡我們 | 訪客留言 |
論 文 專 利 著 作 項 目 ZigBee 與 Uwb動態 技術FAQ
 
 

 

WSN中一種基于移動信標檢測的定位算法

金純1,2, 王升剛1, 尹遠陽1
(1.重慶郵電大學 無線傳輸技術研究所,重慶 400065;2. 重慶金甌科技發展有限責任公司,重慶 400041)
該論文發表于《傳感器與微系統》2014年第33卷第2期
刊號為:ISSN 1001-3695

摘要:信標節點在無線傳感器網絡定位技術中起著重要的作用,它作為參考節點決定著被定位目標的位置。在無線傳感器網絡的實際環境應用中,信標節點可能會因為各種原因發生移動成為不可靠的信標節點,此時依賴不可靠信標節點來定位的未知節點將可能產生較大的定位誤差,甚至失去了利用價值。針對信標節點發生移動的問題,提出了一種定位前期的基于可用信標的移動信標檢測方案(BAB-BMD)——在節點定位之前,對定位節點收到的所有信標進行檢測并對移動信標重定位計算其可靠度。然后,依據信標可靠度選擇可用信標用于定位,即基于可用信標的信標擇優定位算法(BAB-BOS)。實驗結果表明,BAB-BMD具有較好的檢測正確度,同時采用BAB-BOS定位算法定位準確度要高于未進行移動信標檢測的定位準確度和丟棄移動信標的定位準確度。

關鍵詞:無線傳感器網絡;移動信標檢測;節點定位;信標可信度; 中國分類號:TP277 文獻標識碼:A







An Algorithm for Localization Based on the Beacon Movement Detection in WSN
Chun Jin 1, 2, Sheng-gang Wang 1, Yuan-yang Yin1

(1. Wireless transmission technology research institute Chongqing University of Posts and Telecommulacations, Chongqing, 400065, China; 2. Chongqing Jinou Science&Technology Development Co., Ltd, Chongqing, 400041, China)


Abstract:Beacon nodes are playing an important role in wireless sensor network localization, which are used as the reference nodes to calculate the target position. But, the unnoticed changes of locations of some beacons may occur because of various reasons in the actual environment of wireless sensor network applications. So, the moved beacons may become unreliable nodes and at this time if we depend on the moved beacon nodes to locate the unknown node may affect the localization accuracy, and even lost the use value. An algorithm of beacon movement detection based on the available beacon was proposed for the problem of beacon movement (BAB-BMD) before localization. This algorithm detects all the beacon nodes and calculates reliability for each beacon which is received by the unknown nodes before the localization. Then select available beacon by the reliability of beacon for localization, which is beacon optimal selection based on the available beacon (BAB-BOS). Experiment results show that BAB-BMD has good detection for beacon movement. At the same time, BAB-BOS also has a better positioning accuracy compared with no detection of beacon movement and discard the moved beacon.

Keywords:wireless sensor network; beacon movement detection; node localization; beacon reliability

1.前言

    在無線傳感器網絡中定位技術在確定事件發生的位置中起著極其重要的作用。現有的傳感器網絡常見的定位機制有基于測距的定位方法和無需測距的定位方法,如信號強度定位法、到達時間及時間差定位法、DV-Hop、Amorphous算法等[1][2]。以上所有定位算法都是在網絡中信標節點實時位置的可靠度得到保證的前提下,才能定位出未知的節點的可靠坐標。正常情況下信標節點布設完成后其位置并不會發生改變,然而,在類似井下傳感網、環保監測傳感網環境中可能由于煤礦事故或動物破壞導致某些信標節點位置發生改變。因此,如何在定位之前檢測傳感網中的移動信標顯得十分必要。

    文獻[3]提出了無線傳感器網絡中的信標移動問題,并利用一個功能強大的節點重新設置那些移動過的信標,例如在每個節點上安裝GPS。但是,考慮到GPS的價格成本并不適合將其安裝到數量龐大的傳感器網絡中。

    文獻[4]中提出了信標移動檢測概念(Beacon Movement Detection),并設計了相應的移動信標檢測算法。但是該算法由于存在誤差傳遞和判定移動信標的二義性其定位精度并不是很高,并且對移動信標進行丟棄降低了信標節點數量同樣會降低定位準確度。文獻[5]在以上基礎上對文獻[4]進行了改進提出了基于區域劃分的信標節點移動檢測算法和擇優定位算法,相對提高了對移動信標的檢測正確率和定位準確度。以上算法都是對網絡中所有信標進行檢測,本文提出了一種更加高效的有選擇性的判斷信標是否移動的算法——基于可用信標的移動信標檢測。

2. 基于可用信標的移動信標檢測算法

2.1 可用信標檢測的思想

    在傳感網絡的所有的信標節點布設完成后,每個信標節點依據各自的信號強度,計算出一跳通信范圍內與所有信標節點的距離,最終形成整個傳感網絡的信標節點之間的距離關系矩陣 。未知節點根據自身的通信范圍,可以確定 時刻能與之通信的信標節點并形成距離關系矩陣 。然后,從 中選出對應的可用信標原始矩陣 ,依據 和 判斷出可用信標節點是否發生移動。該算法相比文獻[5]與文獻[6]在檢測效率和判斷準確度上得到了進一步提高。

2.2 基于可用信標的移動信標檢測算(BAB-BMD)

    算法的主要流程,首先計算網絡初始矩陣作為信標移動檢測判定的參考。其次,未知節點發送定位請求并記錄傳感網絡中收到請求的信標節點(可用信標)。然后,形成初始判定矩陣并將初始判定矩陣與網絡初始矩陣進行比較,判定出可用矩陣中的移動信標。最后,利用初始矩陣對移動信標進行定位并計算其可靠度。

2.2.1 初始矩陣和判定矩陣的初始化

    初始矩陣即為0時刻信標節點剛剛布設完成后,信標節點之間依據彼此接收到的RSSI值,計算得到的鄰居信標之間的距離矩陣,記為 。判定矩陣為網絡在t時刻時的可用信標依據RSSI值形成的距離矩陣與對應的初始矩陣之間的差異矩陣。其初始化步驟如下:

    (1)從網絡初始矩陣中選擇位置節點的可用信標形成未知節點的初始矩陣 ;

    (2)在時刻將檢測到未知節點的信標節點之間的RSSI通過路徑損耗模型轉化成距離監測矩陣 ;

    (3)計算判定矩陣 。將 時刻的監測矩陣減去可用信標的初始矩陣,然后在取絕對值得到判定矩陣如下式所示:

    其中, 為可用信標的個數,矩陣中的每一行為可用信標在 時刻與初始時刻距離的差值。

2.2.2 移動信標檢測算法的設計

    可疑移動信標檢測:

    定義 為在判定矩陣中判定信標節點是否移動的臨界值。根據臨界值將式(1)中的信標節點劃分為兩部分移動信標節點集合和未移動信標節點集合。若 則認為節點 、 的相對位置發生了改變。

    依次對判定矩陣中的所有值進行判定,并記錄每一行中值大于 元素的個數。例如第 行元素中有3個元素值大于 ,則記為 。 越大說明信標節點 發生移動的可能性越大。對于可用信標中的每一個信標節點 ,若 ,則判定信標節點 為可疑移動信標,并將其加入可疑移動信標集合 ,其中 , 為節點移動的概率根據文獻[5]未知情況下可取0.2。反之,將其加入未移動信標集合 。

    確定可疑移動信標是否為移動信標:

    對于可疑信標采用 和0時刻坐標對比方法進行確認其是否移動。考慮到信號強度不穩定性引起的誤判,首先定義 為判定信標是否移動的容忍半徑。如果 和0時刻的坐標距離小于 則認為信標沒有發生移動,否則信標已經移動。根據集合 中的信標節點是否可以對集合 中節點定位,分兩種情況來處理。若 能定位 中信標節點,利用 集合中的信標對 集合中信標進行定位。若 中節點數,無法滿足 中節點定位要求,首先根據 中信標節點ID查詢0時刻的鄰居矩陣,根據式(1)和可疑移動信標檢測方法排除可疑信標后在對 中的信標節點進行定位。當 中的信標節點判定完成后,利用可靠度公式分別計算 中信標節點的可靠度。

2.2.3 移動信標檢測算法的設計

    信標節點坐標的準確度直接影響著定位的精度,為了減少信標檢測過程中產生的定位誤差,對每個信標節點計算其可靠度。可靠度的計算分為移動可用信標和未移動可用信標。

    未移動可用信標可靠度的計算:

    式中, 為檢測到沒有發生移動的信標節點 可靠度; 為判定信標是否移動的容忍半徑; 和 分別為可用信標總數和移動信標個數; 和 為未移動信標節點 和 在 和0時刻之間的距離;由式(2)可知信標節點之間距離變化越小可靠度越高,理想情況下可靠度為1。

    移動可用信標可靠度的計算:

    式中, 為移動可用信標節點 的可靠度; 為 時刻移動信標坐標與0時刻坐標的距離; 為參與移動信標定位的未移動信標可靠度 。由式(3)可知,移動距離越大可靠度越低,參與定位的信標節點可靠度越高,最終計算的移動信標的可靠度也越高。

3.基于可用信標移動檢測的定位算法

3.1 基于信標可靠度的定位算法設計

    1. 網絡初始化后,依據信號傳播模型計算 時刻信標節點之間的距離矩陣 。

    2. 未知節點發送定位請求數據包。

    3. 收到定位請求數據包的節點,將其加入可用信標節點集合 , 。

    4. 通過移動信標檢測算法檢測集合 中的可用信標是否發生移動并計算每個可用信標的可靠度。

    5. 集合 中的可用信標節點周期性的單播發送自身信息數據包,數據包格式如下:


其中,ID為信標節點的物理標識; 為信標節點的坐標; 為信標節點的可靠度;MB為信標節點的移動標志,如何信標節點被檢測為移動信標,則 ;否則為0;

    6. 未知節點收到應答請求后,根據收到數據包的信息優先選擇其中三個可靠度高的節點作為定位信標節點,并檢測三個信標節點是否共線。若共線重新選擇保證最終使用的信標節點不共線。然后利用三邊測量法計算未知節點的位置。

    7. 檢查網絡中所有未知可定位節點是否完成定位,若沒有繼續第三步,直至完成所有可用信標節點的定位。

4.算法的Matlab仿真與分析

    利用Matlab對所提算法進行仿真,為了與文獻[5]進行比較,設定傳感區域為100*100的二維平面。其中信標節點的數量設定為25個,設定相鄰信標節點間距離大于15m并隨機布設在傳感區域中。信標節點發生移動的概率為 。為了模仿現實環境中的無線傳播的不規則性,選用DOI傳播模型[7]:


式中, 為平均接收信號功率, 為發送信號功率, 為參考距離 的路徑損耗功率, 為路徑損耗因子, 為不同傳播方向上的路徑損耗協同系數,計算方法為[8]:
其中, 為單位方向上最大路徑損耗百分比變化程度,仿真時取0.015。

    利用Matlab對所提算法進行仿真,為了與文獻[5]進行比較,設定傳感區域為100*100的二維平面。其中信標節點的數量設定為25個,設定相鄰信標節點間距離大于15m并隨機布設在傳感區域中。信標節點發生移動的概率為 。為了模仿現實環境中的無線傳播的不規則性,選用DOI傳播模型[7]:


式中, 為平均接收信號功率, 為發送信號功率, 為參考距離 的路徑損耗功率, 為路徑損耗因子, 為不同傳播方向上的路徑損耗協同系數,計算方法為[8]:
其中, 為單位方向上最大路徑損耗百分比變化程度,仿真時取0.015。

    由于接收的信號強度,會受到服從高斯分布的噪聲的影響,所以距離 處的實際接收信號強度 服從以下分布:

其中, 為高斯分布標準差取值為4到12。因此,由式(4)、(5)、(6)可推算出節點間的估算距離為:

4.1 BAB-BMD算法仿真

    為了探討BAB-BMD算法在移動信標檢測中的性能,根據文獻[4]利用檢測準確度對算法進行衡量,并與其中的LB、SSB算法在不同信標節點移動比例下進行比較。檢測準確度的定義如下:


式中, 為檢測準確度; 為可用信標節點總個數; 為信標發生了移動并檢測到該信標發生了移動的信標個數;為 信標未發生移動并檢測到信標未發生移動的信標個數。

圖 1 不同算法間的檢測準確度比較

    不同算法的仿真結果如圖1所示,可以看出,LB算法的檢測準確度最高,而BAB算法的檢測準確度在LB和SSB算法之間。當信標節點的移動比例為0.1時三種算法的檢測準確度相差不大,但是當移動比例超過0.2時三種算法的檢測準確度出現明顯差距。這是因為LB算法是通過比較定位前后坐標進行判定,影響準確度的因素只有RSSI引起的定位誤差。SSB算法除此之外還存在算法的二義性問題是其檢測準確度相對較低的主要原因。BAB算法利用可用信標進行判定,可用信標的距離相距較近RSSI值較穩定,并且判據矩陣相比SSB算法元素減少進一步減少了SSB算法的二義性問題,因此BAB算法具有較好的檢測準確度。

4.2 BAB-BOS算法仿真

    可用信標檢測的最終目的是用于最終的精確定位。因此,需要對BAB-BOS算法的定位性能進行仿真驗證。為了突出算法的性能,以未進行移動信標檢測、檢測并移除移動信標、檢測并定位移動信標三種情況作為對比。

    未進行移動信標檢測表示網絡中存在一定數量的移動信標,但并不考慮其位置已發生改變,直接利用定位算法對未知節點進行定位。

    檢測并移除移動信標表示在定位前,檢測可用信標是否發生移動并舍棄發生移動的信標然后在對未知節點進行定位。

    檢測并定位移動信標表示在定位前,檢測可用信標是否發生移動并對發生移動的信標進行定位,然后計算可用信標的可靠度,最后優先選用可靠度高的節點(BAB-BOS)對未知節點進行定位。

圖 2 移動信標比例不同時定位誤差

圖 3 不同移動比例信標下可定位節點比例

當網絡中移動信標的比例不同時,算法的性能如圖 2 移動信標比例不同時定位誤差、圖 3 不同移動比例信標下可定位節點比例所示。由圖 2 移動信標比例不同時定位誤差可以看出,檢測并定位移動信標的平均定位誤差相對較低,這是因為移動信標的實時位置得到了更正并充分利用了可用信標。當移動信標的比例較小時三種情況下的平均定位誤差相差不大,但隨著移動信標的比例不斷增大,未進行移動信標檢測的平均定位誤差急劇增大,這是因為移動信標參與了定位降低了定位精度。由于檢測并移除移動信標降低了可用信標的數量但卻舍棄了不可靠的移動信標所以平均定位誤差處于中間。在圖 3 不同移動比例信標下可定位節點比例中由于檢測并移除移動信標減少了網絡中的信標節點數量,所以隨著移動信標節點的比例增加可定位的節點比例逐漸減少。相比其他兩種算法由于并未丟棄移動信標,故可定位節點比例并未發生改變。
圖 4 不同信標節點數下定位誤差

圖 5 不同信標節點數下的可定位節點比例

    考慮到信標節點數量對定位的影響,分別作了如圖 4 不同信標節點數下定位誤差、圖 5 不同信標節點數下的可定位節點比例情況下的仿真。在圖 4 不同信標節點數下定位誤差中可以看出三種情形下的平均定位誤差都有所降低,但未進行移動信標的平均定位誤差明顯高于其余兩種情形。當信標節點數目小于35時檢測并定位移動信標的平均定位誤差明顯低于丟棄移動信標的情形,但當大于35時檢測并定位移動信標并未有明顯優勢甚至略高于丟棄移動信標的情形。這是由于檢測并定位移動信標需要對移動信標定位此時也會產生一定的誤差,當對未知節點定位時會有一定的誤差累積,而由于信標節點的數目足夠滿足定位需求,丟棄個別移動信標并未對定位精確度產生較大影響。

5. 結束語

本文針對無線傳感器網絡應用中,存在部分位置發生改變的信標節點影響定位準確度的問題,提出了一種基于可用信標移動檢測的定位算法(BAB-BMD)并結合此算法設計出一種基于可用信標的信標擇優定位算法(BAB-BOS)。仿真實驗表明,提出的基于可用信標移動檢測的定位算法具有較好的檢測準確度。另外,基于可用信標的定位算法的在平均定位誤差、可定位節點比例、以及算法的穩定性上同樣具有良好的性能。

參考文獻
[1] Song W, Wang B, Zhou Y B, Technology and application of wireless sensor network [M]. BeiJing : The Electronics Industrial Publisher , 2007.
[2] 高守瑋, 吳燦陽. ZigBee技術實踐教程[M]. 第一版. 北京: 北京航空航天大學出版社, 2011: 391-393.
[3] Edwin Olson, John Leonard, and Seth Teller. Robust Range-Only Beacon Localization[J]. IEEE Journal of Oceanic Engineering, 2006, 31(4) : 949-958.
[4] Sheng-Po Kuo, Hsiao-Ju Kuo, Yu-Chee Tseng. The Beacon Movement Detection Problem in Wireless Sensor Networks for Localization Application[J]. IEEE Transaction on mobile computing, 2009, 8(10) : 1326-1338.
[5] 何文秀,夏明,趙小敏等. WSN中信標節點移動情況下的定位方法研究[J]. 小型微型計算機系統,2011,32(11) : 2259-2262.
[6] Sheng-Po Kuo, Hsiao-Ju Kuo, Yu-Chee Tseng. The Beacon Movement Detection Problem in Wireless Sensor Networks for Localization Application[J]. IEEE Transaction on mobile computing, 2009, 8(10) : 1326-1338.
[7] Yuanfang Chen, Lei Shu, Mingchu Li, Ziqi Fan. The Insights of DV-based Localization Algorithms in the Wireless Sensor Networks with Duty-cycled and Radio Irregular Sensors[C]. International Conference on Communications, 2011: 1-6.
[8] 許紅艷, 王經卓, 董自健等. MDS-MAP算法在不同傳播模型中定位誤差的比較[J]. 淮海工學院學報(自然科學版), 2012, 21(1): 15-19.

作者簡介:
金純 (1966—) 博士、教授、研究生導師 主要研究方向:無線通信、計算機軟件、物聯網等
尹遠陽 (1986—) 碩士研究生 研究方向:無線通信,無線傳感器網絡等 通信地址:重慶市南岸區崇文路重慶郵電大學通信與信息工程學院,無線傳輸重點實驗室,無線傳輸三班(400065) (尹遠陽)

 

北京南城搬家公司