基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法

張琳娜

(陜西國防工業(yè)職業(yè)技術學院　西安　710300)

?

基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法

張琳娜

(陜西國防工業(yè)職業(yè)技術學院西安710300)

為解決無線傳感網(wǎng)鏈路定位過程中定位閾值確定困難,數(shù)據(jù)鏈路隨定位精度存在遷移過度等問題。論文提出了基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法。首先,采取區(qū)域自遞歸方式,構建節(jié)點定位自旋閾值,并根據(jù)該閾值進行節(jié)點定位,從而實現(xiàn)簇區(qū)域內(nèi)節(jié)點的穩(wěn)定搜尋,然后針對數(shù)據(jù)傳輸過程的特點,采取流量穩(wěn)定機制實現(xiàn)對數(shù)據(jù)傳輸?shù)膬?yōu)化選擇,從而實現(xiàn)數(shù)據(jù)的高效匯聚傳輸。仿真實驗表明:與SWF算法相比,論文算法的鏈路穩(wěn)定代價更低,可實現(xiàn)數(shù)據(jù)的優(yōu)化傳輸和節(jié)點的精確定位。

無線傳感器網(wǎng)絡; 節(jié)點定位; 自旋閾值; 區(qū)域自遞歸; 流量穩(wěn)定機制

Class NumberTP393

1　引言

隨著網(wǎng)絡定位技術的不斷推進,基于無線傳感節(jié)點特性定位的技術也得到很大的發(fā)展[1]。由于網(wǎng)絡節(jié)點定位技術是許多網(wǎng)絡技術如采集、識別、監(jiān)控等領域的基礎性技術,因此成為當前研究過程的熱點技術[2]。通過采用一定的算法提高定位過程中的準確性,降低定位過程中能量開支及提高無線傳感節(jié)點在收發(fā)信號時的信噪比,成為了當前無線傳感網(wǎng)定位技術中重要的研究熱點[3]。

針對當前研究領域中存在的這些問題,人們采取了多種方式盡量提高各種算法的計算性能。GAO C等[3]提出可利用節(jié)點自身坐標遞歸特性,實現(xiàn)了在初步定位后采用線性收斂方程組的收斂特性,實現(xiàn)了節(jié)點的精確定位。但是,由于該種算法對初步定位的精確程度要求不高,導致方程組收斂的時間較長,影響了定位精度的進一步提高。CHEN D等[4]提出了一種基于多節(jié)點的聯(lián)合定位方法,通過預先針對多個錨節(jié)點同時定位的方式,實現(xiàn)了網(wǎng)絡中任意節(jié)點坐標的精確獲取。然而,該算法需要預先對錨節(jié)點坐標進行存儲,且錨節(jié)點的分布需滿足均勻分布,當某個節(jié)點難以獲得錨節(jié)點坐標或錨節(jié)點不滿足均勻分布條件,則節(jié)點定位的精確程度將大大降低。Hao Xiaochen等[5]提出了一種基于自定位機制的節(jié)點定位算法,通過預先構建各個節(jié)點間的關聯(lián)順序,實現(xiàn)了在錨節(jié)點已知的情況下對節(jié)點的實時定位。但是,該節(jié)點需要通過sink節(jié)點對各個節(jié)點之間相對距離進行計算,在背景噪聲復雜時定位的精確度也隨之降低,此外由于該算法的定位效率較低,當網(wǎng)絡中節(jié)點個數(shù)較多時將難以以高效的方式實現(xiàn)對節(jié)點坐標的精確捕獲。

對此,本文提出了一種基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法,通過構建節(jié)點定位自旋閾值,實現(xiàn)對節(jié)點的初步定位,同時采取流量穩(wěn)定機制,實現(xiàn)數(shù)據(jù)在網(wǎng)絡中的高效匯聚。最后通過NS2仿真平臺對本文算法進行了仿真。

2　網(wǎng)絡模型假設

由于當前的定位技術主要依托于無線傳感網(wǎng)的定位性能而實現(xiàn),因此當網(wǎng)絡出現(xiàn)異常時將難以實現(xiàn)節(jié)點的精確定位,特別是當節(jié)點能量耗盡時將無法進行正常的定位過程[6],據(jù)此本文無線傳感網(wǎng)做如下的假設:

1) 網(wǎng)絡節(jié)點的分布滿足均勻分布,即整個節(jié)點分布均不受人為因素的影響,處于自然分布狀態(tài)[7];

2) 傳感器節(jié)點由電池供電,當電源耗盡時整個定位過程也將終止[8];

3) 傳感器節(jié)點的定位過程由無線射頻信號作為定位介質(zhì),當僅當周圍背景噪聲的頻率與無線射頻信號頻率近似時才產(chǎn)生嚴重的干擾效應[9];

4) 整個網(wǎng)絡的核心成員為一具有無限處理能力的sink節(jié)點,該節(jié)點的緩存無限,電源能量不受限制[10]。

3　本文無線傳感網(wǎng)節(jié)點定位算法

基于上述網(wǎng)絡模型假設,本文提出了基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法,整個算法由節(jié)點自旋閾值確認和優(yōu)化傳輸兩個部分所構成。

3.1節(jié)點自旋閾值確認

無線傳感節(jié)點在定位過程中,任意一節(jié)點的自旋閾值主要由其周圍節(jié)點到自身的位置關系決定的。對于某個節(jié)點而言,若該節(jié)點在進行旋轉(zhuǎn)時與周圍節(jié)點之間存在密切的信息交互關系,則該節(jié)點通過自旋獲取的周圍節(jié)點的信息也就越多,當獲取信息的節(jié)點數(shù)量到達一定程度時,定位精確程度可以達到較高的水平。因此如果想通過基于無錨技術實現(xiàn)對節(jié)點的定位,則需要對待定位節(jié)點與周圍節(jié)點間的關系特別是拓撲位移關系進行推斷,綜合考慮各個節(jié)點拓撲位移對待定位節(jié)點進行定位確認,可以計算得到待定位節(jié)點的精確坐標位置。

設i為某個待計算的節(jié)點,其周圍兩跳范圍內(nèi)的節(jié)點個數(shù)為ωi,則ωi滿足如下的關系:

(1)

其中D為與i相鄰的節(jié)點j的集合,顯然i的孤立程度(即兩跳范圍內(nèi)節(jié)點個數(shù))越低,則ωi對應的數(shù)值也就越高。

不妨設i的初始坐標為ηij,則ηij滿足如下的關系:

(2)

模型(2)計算得到的坐標反映了待定位節(jié)點與兩跳范圍內(nèi)的節(jié)點之間的信息交互關系,當待定位節(jié)點不斷以旋轉(zhuǎn)方式對周圍節(jié)點進行掃描時,可以通過模型(2)所示的公式實現(xiàn)對初始坐標的計算。然而由于單純采用模型(2)對節(jié)點坐標進行計算有較大的局限性,特別是當前節(jié)點經(jīng)過一次旋轉(zhuǎn)掃描將難以實現(xiàn)對兩跳范圍內(nèi)節(jié)點全覆蓋時,所得的初始坐標將具有較大的誤差。因此本文引入自旋閾值,采用該閾值對模型(2)所示的坐標進行修正,以便提高精確度。

待定位節(jié)點再進行一次掃描時,首先選取兩跳范圍內(nèi)信號強度最強的節(jié)點作為基準節(jié)點,當待定位節(jié)點掃描其它節(jié)點時,將通過無線信號對比的方式獲取各個節(jié)點到本節(jié)點的自旋閾值,采用排序的方式對各個閾值進行對比,自旋閾值E(r)通過模型(3)計算得到:

(3)

其中,T為待定位節(jié)點掃描周期,r為定位節(jié)點最大掃描頻率,PC為待定位節(jié)點掃描出錯概率,Pr為當前節(jié)點坐標精確度,ηij定義同模型(2)。

則節(jié)點i在經(jīng)過r輪掃描之后的坐標μij滿足如下表達式:

μij=ηijE(r-2)+E(r-1)

(4)

模型(2)也需要根據(jù)模型(3)進行修正,則更新之后的節(jié)點坐標滿足:

(5)

相應參數(shù)同模型(1)、(2)所定義。

綜合模型(4)、(5)可得待定位誤差ψi滿足如下的表達式:

(6)

顯然通過模型(6)計算得到的定位誤差ψi與掃描輪數(shù)呈現(xiàn)反比例關系,當掃描輪數(shù)較少時,將能有效地降低定位誤差。對模型(6)求偏導數(shù)可得:

(7)

當僅當r=1時ψi取得最小值0,從模型(7)可以得到本文算法僅需要通過一輪掃描即可以將精度誤差控制在0左右,大大降低了定位誤差。

3.2優(yōu)化傳輸

當定位誤差降低在可控范圍內(nèi)之后,執(zhí)行算法的數(shù)據(jù)優(yōu)化傳輸,其詳細步驟如下:

Step 1:統(tǒng)計節(jié)點的數(shù)據(jù)發(fā)送周期T,若在發(fā)送周期內(nèi)均在sink節(jié)點的覆蓋范圍內(nèi)掃描,則在每一次收到sink節(jié)點發(fā)送的數(shù)據(jù)上傳指令后,啟動兩跳之內(nèi)節(jié)點的搜尋并轉(zhuǎn)Step 2;否則,轉(zhuǎn)Step 3;

Step 2:按照模型(7)分別搜尋最佳中繼節(jié)點,若計算所得位置未發(fā)生改變,則在下一刻收到sink數(shù)據(jù)分組之前將繼續(xù)按照當前上傳鏈路匯聚數(shù)據(jù);否則,回到Step 1,并按模型(6)更新后的精度進行定位并發(fā)送數(shù)據(jù),重新轉(zhuǎn)Step 1;

Step 3:若節(jié)點的數(shù)據(jù)發(fā)送周期內(nèi),節(jié)點失效,則在節(jié)點失效前前重啟定位過程的確認,算法結(jié)束。

4　仿真實驗

本文采用NS2仿真平臺對本文算法進行仿真,為驗證本文算法的有效性,將與當前廣泛使用的SWF節(jié)點定位算法[11～12]進行對比,在定位消息誤差率、定位數(shù)據(jù)重啟發(fā)送頻率、掃描鏈路抖動時間、定位精度誤差四個指標上進行對比。具體仿真參數(shù)如表1所示。

表1　仿真參數(shù)表

1) 定位消息誤差率

圖1顯示了本文算法同對照組算法在定位消息誤差率測試結(jié)果,從圖中可以看到本文算法的對照組算法隨著網(wǎng)絡節(jié)點數(shù)量的增加均呈現(xiàn)不斷增加的趨勢,但是本文算法的定位消息誤差率始終要低于對照組算法,這是因為本文算法引入了自旋閾值機制,能夠通過多輪掃描有效的控制定位消息誤差,因此能夠降低定位消息傳輸過程中的出錯概率,而對照組算法僅采取廣播機制進行消息傳輸,當消息出現(xiàn)錯誤時將難以通過對錯誤的糾正實現(xiàn)對定位消息誤差上的控制。

圖1　兩種算法的定位消息誤差率測試結(jié)果

2) 定位數(shù)據(jù)重啟發(fā)送頻率

圖2顯示了本文算法同對照組算法在定位數(shù)據(jù)重啟發(fā)送頻率測試結(jié)果,從圖中可以看到本文算法的重啟發(fā)送頻率始終要低于對照組算法,這是因為本文算法通過對兩跳之內(nèi)的節(jié)點均采用自旋掃描方式實現(xiàn)初步定位,一次定位的精度很高,因此無需通過多次重啟定位數(shù)據(jù)發(fā)送的方式實現(xiàn)定位,而對照組算法由于對定位坐標的獲取僅僅基于一個基準節(jié)點,需要通過多次定位實現(xiàn)數(shù)據(jù)重啟發(fā)送,因而提高了算法的數(shù)據(jù)重啟頻率。

3) 掃描鏈路抖動時延

圖3顯示了本文算法同對照組算法在掃描鏈路抖動時延測試結(jié)果,從圖中可以看到本文算法的掃描鏈路抖動時延始終要低于對照組算法,這是因為本文算法通過優(yōu)化上傳機制實現(xiàn)了最佳鏈路的篩選,因此能夠有效的掃描過程中鏈路因背景噪聲影響而發(fā)生的抖動效應,而對照組算法未引入任何抖動校驗機制,當定位出現(xiàn)錯誤時難以有效降低掃描鏈路抖動時間。

圖2　各算法的定位數(shù)據(jù)重啟發(fā)送頻率測試

圖3　兩種算法的定位消息傳輸時延測試

4) 定位精度誤差

圖4顯示了本文算法同對照組算法在定位精度誤差上的對比,從圖中可以看到本文算法的定位精度誤差始終要低于對照組算法,這是因為本文算法通過引入掃描輪數(shù)實現(xiàn)了定位誤差的精確化,因此能夠有效的改善定位精度,而對照組算法的定位誤差基于一次掃描成型,當定位出現(xiàn)錯誤時難以實現(xiàn)實時糾正導致定位精度誤差高于本文算法。

圖4　各算法的定位精度測試

5　結(jié)語

本文提出了一種基于節(jié)點自旋閾值確認機制的無線傳感網(wǎng)節(jié)點定位算法,在節(jié)點進行定位過程中采取掃描的方式對2跳范圍內(nèi)的節(jié)點進行閾值對比,實現(xiàn)對節(jié)點的一次定位。隨后通過自旋閾值的引入,采取基于數(shù)值分析的方式對最佳掃描輪數(shù)進行了討論,精確的計算出當定位誤差精度很低時所需要的最佳掃描輪數(shù),最后采取優(yōu)化匯聚的方式,實現(xiàn)了數(shù)據(jù)的優(yōu)化匯聚。仿真實驗表明:與當前廣泛使用的算法相比,本文算法在定位消息誤差率、定位數(shù)據(jù)重啟發(fā)送頻率、掃描鏈路抖動時間、定位精度誤差上具有明顯的優(yōu)勢,對實踐具有一定的指導意義。

下一步將通過引入立體定位機制,對多層網(wǎng)絡節(jié)點的定位過程的誤差精度進行控制,努力提高本文算法的適用范圍,實現(xiàn)基于平面-立體綜合定位的聯(lián)合定位。

[1] ZHANG X, ZHU J. Identifying influential nodes in complex networks with community structure[J]. Knowledge-Based Systems,2013,42(13):74-84.

[2] 鄔厚民.無線傳感網(wǎng)絡中能量和距離改良的節(jié)點定位算法[J].中國測試,2012,38(5):62-66.

WU Houming. Improved energy and distance improved node localization algorithm in Wireless Sensor Networks[J]. China Test,2012,38(5):62-66.

[3] GAO C, LAN X, ZHANG XG. A bio-inspired methodology of identifying influential nodes in complex networks[J]. PloS One,2013,8(6):667-732.

[4] CHEN D, LV L, SHANG M S, et al. identifying influential nodes in complex networks[J]. Physical A: Statistical Mechanics and its Applications,2011,391(4):1777-1787.

[5] Hao Xiaochen, Jia Nan, Liu Bin. Multi-path optimizing routing protocol based on predicting congestion for wireless sensor network[J]. Journal of Electronics & Information Technology,2011,33(5):1261-1265.

[6] Wang L, Geng X. A Community-driven Hierarchical Message Transmission Scheme in Opportunistic Networks[J]. Smart Computing Review,2011,1(1):85-94.

[7] Wang D, Zhang Q, Liu J C. Partial network coding: theory and application for continuous sensor data collection[C]//Proc. of the 14th IEEE International Workshop on Quality of Service,2012,35(10):93-101.

[8] ZHOU C, HE JW. A robust active queue management scheme for network congestion control[J]. Computers and Electrical Engineering,2013,39(1):285-293.

[9] 王文吉.基于能量因素的無線傳感網(wǎng)絡關鍵節(jié)點定位算法[J].電子與信息學報,2014,36(7):1728-1734.

WANG Wenji. Key node localization algorithm for wireless sensor networks based on energy factor[J]. Journal of Electronics and Information,2014,36(7):1728-1734.

[10] Habib M Ammari, Sajal K Das. A study of K-coverage and measures of connectivity in wireless sensor networks[J]. IEEE Transactions on Computers,2013,59(2):258-267.

[11] HA Le, Lijin, Yuanguo. A TCP Performance Enhancement Scheme in Infrastructure based on Vehicular Networks[J]. China Communications,2015,6(13):73-84.

Node Localization Algorithms for Wireless Sensor Network Node Based on Spin Threshold Confirmation Mechanism

ZHANG Linna

(Shaanxi Defence Vocational & Technical College, Xi’an710300)

In order to solve that the localization threshold in wireless sensor network link location process is difficult to determine, data link with the positioning accuracy of the exist problems such as excessive migration, this paper proposes a node localization algorithm for WSN node threshold confirmation mechanism based on the mechanism of spin. First, regional self recursive construction of node localization stability threshold, and node localization according to the threshold, in order to achieve the stability of the nodes in the cluster region search, then according to the characteristics of the process of data transmission, stable flow mechanism of choice for the optimization of data transmission, data in order to achieve efficient transmission convergence. Simulation experiments show that the algorithm in this paper can reduce the link stability consideration, to achieve the precise position of the optimization of data transmission, the node.

wireless sensor network, node localization, spin threshold, regional self recursion, stable flow mechanism

2016年2月7日,

2016年3月26日

張琳娜,女,碩士,講師,研究方向:無線傳感器網(wǎng)絡與數(shù)學模型。

TP393

10.3969/j.issn.1672-9722.2016.08.033