田文利

?

基于關(guān)鍵數(shù)字特征遞歸機(jī)制的無線傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法

田文利

摘 要：為解決當(dāng)前無線傳感網(wǎng)關(guān)鍵點(diǎn)搜尋算法因無法規(guī)避背景噪聲干擾而導(dǎo)致其定位精度不高，且搜索效率不佳等問題。提出了基于關(guān)鍵數(shù)字特征遞歸機(jī)制的無線傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法，首先通過關(guān)鍵數(shù)字特征遞歸機(jī)制對關(guān)鍵點(diǎn)的能量狀態(tài)進(jìn)行估計(jì)，然后采取遞歸關(guān)鍵點(diǎn)射頻信息的能量對無線傳感網(wǎng)關(guān)鍵點(diǎn)進(jìn)行搜索；隨后對關(guān)鍵數(shù)字特征值進(jìn)行了指紋鑒定，完成對關(guān)鍵點(diǎn)的精確估計(jì)與定位。仿真實(shí)驗(yàn)表明:與WSN-Div算法相比。所提出的算法具有較高的關(guān)鍵點(diǎn)搜索成功率，以及更低的數(shù)據(jù)定位開銷及搜索誤差度。

關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；關(guān)鍵點(diǎn)搜索；射頻信息；數(shù)字特征遞歸；指紋鑒定

0 引言

隨著互聯(lián)網(wǎng)3.0節(jié)奏的不斷推進(jìn)，特別是互聯(lián)網(wǎng)在無線傳感領(lǐng)域的不斷運(yùn)用，各種基于無線技術(shù)的傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法也層出不窮［1］。采用一定的關(guān)鍵點(diǎn)搜索算法實(shí)現(xiàn)對網(wǎng)絡(luò)中節(jié)點(diǎn)的精確定位，成為了當(dāng)前無線傳感網(wǎng)定位領(lǐng)域的一大熱點(diǎn)［2］。然而無線傳感網(wǎng)在進(jìn)行關(guān)鍵點(diǎn)搜索過程中需要傳感節(jié)點(diǎn)能夠通過射頻信號來進(jìn)行關(guān)鍵點(diǎn)的搜索，該過程往往需要消耗大量的能量，一旦該節(jié)點(diǎn)的能量因耗盡而難以正常工作時，整個網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn)也將受到極大的影響［3］。因此使用合適的措施降低搜索過程中的能量損耗，就成為該領(lǐng)域的非常重要的研究方向［4］。如Georges［5］等提出了一種基于強(qiáng)度遞歸思想的傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法，采用關(guān)鍵信號能量遞歸的機(jī)制，大大降低了搜索過程中因關(guān)鍵點(diǎn)信號強(qiáng)度較弱而導(dǎo)致的定位精度不高的問題，實(shí)踐意義很強(qiáng)。然而，由于該算法遞歸的時間復(fù)雜度較高，當(dāng)關(guān)鍵點(diǎn)分布不均衡時，其搜索成本較大。LI Bin等提出了基于立體映射定位模型的關(guān)鍵點(diǎn)搜索算法，通過將無線傳感網(wǎng)拓?fù)浣Y(jié)構(gòu)映射為球面，將關(guān)鍵點(diǎn)映射為球體結(jié)構(gòu)的重心，降低了搜索過程中的時間復(fù)雜度。但是該算法需要將拓?fù)浣Y(jié)構(gòu)由平面映射為球面結(jié)構(gòu)，當(dāng)關(guān)鍵點(diǎn)比較集中時，該算法會導(dǎo)致各個關(guān)鍵點(diǎn)在球面結(jié)構(gòu)上出現(xiàn)重疊，降低了關(guān)鍵點(diǎn)搜索的準(zhǔn)確度。朱烜璋［6］等提出了一種基于水波擴(kuò)散機(jī)制的關(guān)鍵點(diǎn)搜索精度提升算法，采用鄰居節(jié)點(diǎn)擴(kuò)散的方式，實(shí)現(xiàn)了對網(wǎng)絡(luò)中各個關(guān)鍵點(diǎn)的搜索與歸納。但是由于水波擴(kuò)散機(jī)制屬于間接搜索機(jī)制，整個算法的精度會隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化呈現(xiàn)劇烈變化的態(tài)勢，從而削弱了本算法的適用范圍。

對此，本文提出了一種基于關(guān)鍵數(shù)字特征遞歸機(jī)制的無線傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法。首先通過對關(guān)鍵點(diǎn)射頻信息進(jìn)行關(guān)鍵數(shù)字特征搜索，對關(guān)鍵點(diǎn)實(shí)現(xiàn)初步定位。隨后通過對該數(shù)字特征進(jìn)行指紋鑒定，從而實(shí)現(xiàn)了對關(guān)鍵點(diǎn)定位的進(jìn)一步精確估計(jì)。最后采取NS2仿真平臺對本文算法進(jìn)行了仿真驗(yàn)證，證實(shí)了本文算法的有效性。

1 本文無線傳感網(wǎng)絡(luò)關(guān)鍵點(diǎn)搜索算法

1.1 關(guān)鍵數(shù)字特征的遞歸

由于在進(jìn)行關(guān)鍵點(diǎn)搜索過程中需要通過對關(guān)鍵點(diǎn)的射頻信號進(jìn)行遞歸，而對于任意關(guān)鍵點(diǎn)而言。其能量發(fā)射強(qiáng)度較之其他節(jié)點(diǎn)將具有顯著的能量強(qiáng)度優(yōu)勢［7］，此外對于sink節(jié)點(diǎn)而言，其接收到的關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度（CPEE）與兩點(diǎn)間的距離具有明顯的反比例關(guān)系，即sink節(jié)點(diǎn)與關(guān)鍵點(diǎn)之間的距離越大，則sink節(jié)點(diǎn)接收到的關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度（CPEE）將越弱［8 ］。因此，可以通過將CPEE指標(biāo)作為關(guān)鍵數(shù)字特征，以便實(shí)現(xiàn)對關(guān)鍵點(diǎn)的搜索。

其中，公式（2）的參數(shù)同公式（1），顯然為了降低搜索的誤差程度，可以通過調(diào)節(jié)關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度（CPEE）的方式，降低公式（2）所得到的搜索誤差。

上述兩個模型反映了無線傳感網(wǎng)在進(jìn)行關(guān)鍵點(diǎn)搜索過程中，待搜索的關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度與搜索誤差之間的數(shù)值關(guān)系。通過公式（2）可以看到，顯然關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度（CPEE）越大，則定位誤差越低。但是由于傳感網(wǎng)節(jié)點(diǎn)具有能量受限特性，因此需要綜合考慮節(jié)點(diǎn)性能與坐標(biāo)誤差兩個因素，以便得到最佳的定位精度。

根據(jù)公式（1）所示，計(jì)算出覆蓋區(qū)域內(nèi)全部的關(guān)鍵點(diǎn)，得到這些關(guān)鍵點(diǎn)的全部坐標(biāo)，并取其平均值，可以得到關(guān)鍵點(diǎn)的平均坐標(biāo)滿足如下的表達(dá)式如公式（3）：

由于各個關(guān)鍵點(diǎn)在進(jìn)行信號發(fā)射時，最終其能量將收斂于0［10］，因此公式（3）可以寫成如下的形式如公式（4）：

公式（6）和公式（7）的參數(shù)同公式（1）和公式（2）

整個遞歸過程如下所示：

Step 1：首先在網(wǎng)絡(luò)中搜尋任意一個節(jié)點(diǎn)，統(tǒng)計(jì)CPEE并按照公式（1）、（2）所示計(jì)算出相關(guān)的坐標(biāo)和誤差；

1.2 坐標(biāo)精度提升

在進(jìn)行完關(guān)鍵數(shù)字特征的遞歸之后，可以計(jì)算出某個關(guān)鍵點(diǎn)精確的坐標(biāo)及相應(yīng)的誤差，然而由于關(guān)鍵點(diǎn)搜索過程中往往僅能夠依據(jù)接收帶寬B進(jìn)行搜尋，因此通過公式（7）計(jì)算得到的誤差可以根據(jù)接收帶寬B進(jìn)行精度提升：

對公式（7）進(jìn)行微分處理可得公式（8）：

從公式（9）可知對于關(guān)鍵點(diǎn)能量發(fā)射強(qiáng)度（CPEE）而言，當(dāng)某個關(guān)鍵點(diǎn)與其周圍關(guān)鍵點(diǎn)的發(fā)射功率與接收功率處于相等狀態(tài)時，該關(guān)鍵點(diǎn)的定位精度也將越高，且接收帶寬B在數(shù)值上與CPEE相同時，公式（7）取最小值，整個網(wǎng)絡(luò)搜尋過程中消耗能量最少，取得的關(guān)鍵點(diǎn)坐標(biāo)及相關(guān)誤差也最為精確。整個算法的流程如圖1所示：

圖1 算法流程圖

2 仿真實(shí)驗(yàn)

本文采用NS2仿真平臺對本文算法進(jìn)行仿真，為驗(yàn)證本文算法的有效性，將其與當(dāng)前廣泛使用的WSN-Div關(guān)鍵點(diǎn)搜尋算法［10］進(jìn)行對比，在關(guān)鍵點(diǎn)搜索成功率、定位開銷、搜索誤差度、搜索時間四個指標(biāo)上進(jìn)行對比。具體仿真參數(shù)如表1所示：

表1 仿真參數(shù)表

（1）關(guān)鍵點(diǎn)搜索成功率

本文算法與WSN-Div算法的關(guān)鍵點(diǎn)搜索成功率測試結(jié)果如圖2所示：

圖2 各算法的關(guān)鍵點(diǎn)搜索成功率測試

從圖2可知，隨著節(jié)點(diǎn)初始能量的不斷增加，本文算法與WSN-Div算法的關(guān)鍵點(diǎn)搜索成功率均呈現(xiàn)增加的態(tài)勢，但是本文算法的關(guān)鍵點(diǎn)搜索成功率始終高于對照組算法。這是因?yàn)殡S著節(jié)點(diǎn)初始能量增加，關(guān)鍵點(diǎn)的射頻信號覆蓋范圍也呈現(xiàn)增加的態(tài)勢，因此被成功搜索到的可能性也大大增加。然而本文算法將關(guān)鍵點(diǎn)的射頻信號作為數(shù)字特征，采取了坐標(biāo)精度提升的方式，能夠在同等條件下更為精確的搜尋到關(guān)鍵點(diǎn)。而WSN-Div算法由于僅采用一次搜索機(jī)制，導(dǎo)致精度不夠，使得搜索關(guān)鍵點(diǎn)的成功率上要低于本文算法。

（2）定位開銷

本文算法與WSN-Div算法的定位開銷上測試數(shù)據(jù)如圖3所示：

圖3 兩種算法的定位開銷測試

由圖3易知，隨著節(jié)點(diǎn)信號通信半徑的不斷增加，本文算法與WSN-Div算法的定位開銷均出現(xiàn)上升的情況，這是由于隨著節(jié)點(diǎn)信號通信半徑的不斷增大，關(guān)鍵點(diǎn)的射頻信號覆蓋范圍也不斷增大，覆蓋范圍內(nèi)的節(jié)點(diǎn)個數(shù)也隨之增多，關(guān)鍵點(diǎn)為了獲取準(zhǔn)確的定位坐標(biāo)需要盡量對全部節(jié)點(diǎn)進(jìn)行定位，因此定位開銷也隨之增大。然而本文算法由于能夠?qū)唧w節(jié)點(diǎn)的數(shù)字特征進(jìn)行遞歸，因此僅需要對數(shù)字特征強(qiáng)烈的節(jié)點(diǎn)進(jìn)行定位，因此本文算法的定位開銷比WSN-Div算法具有一定的優(yōu)勢。

（3）搜索誤差度

本文算法與WSN-Div算法的搜索誤差度測試，如圖4所示：

圖4 兩種算法的搜索誤差度

由圖4易知，隨著節(jié)點(diǎn)緩存大小的不斷增加，本文算法與WSN-Div算法均出現(xiàn)了搜索誤差度下降的現(xiàn)象。這是由于隨著節(jié)點(diǎn)緩存大小的不斷增加，節(jié)點(diǎn)進(jìn)行計(jì)算時可用的計(jì)算資源也隨之增加，能夠?qū)⒏嗟墓?jié)點(diǎn)定位數(shù)據(jù)存儲在內(nèi)存中進(jìn)行運(yùn)算，因此降低了搜索誤差度。但是對照組算法在進(jìn)行搜索之后，得到的關(guān)鍵點(diǎn)坐標(biāo)無法根據(jù)新的數(shù)據(jù)進(jìn)行更新。而本文算法由于采用了精度提升機(jī)制，能夠?qū)﹃P(guān)鍵點(diǎn)坐標(biāo)進(jìn)行實(shí)時更新，且可以降低坐標(biāo)誤差精度，因此本文算法在搜索誤差度上要好于WSN-Div算法。

（4）搜索時間

本文算法與WSN-Div算法在搜索時間上的對比如圖5所示：

圖5 兩種算法的搜索時耗測試

從圖5中可以看到，本文算法與WSN-Div算法在搜索時間上均隨著節(jié)點(diǎn)布設(shè)密度的增加而增加，這是由于隨著節(jié)

點(diǎn)布設(shè)密度的增加，關(guān)鍵點(diǎn)數(shù)量也隨之增加。由于其他節(jié)點(diǎn)的數(shù)量增長速度要高于關(guān)鍵點(diǎn)的增長速度，因此增加了無線傳感網(wǎng)對關(guān)鍵點(diǎn)的搜索難度。但是由于本文算法能夠針對各個關(guān)鍵點(diǎn)的數(shù)字特征不同實(shí)現(xiàn)高精度搜索，無需對背景節(jié)點(diǎn)逐一甄別，因此本文算法的搜索時間要大大低于對照組算法，具有明顯的優(yōu)勢。

3 總結(jié)

為解決無線傳感網(wǎng)關(guān)鍵點(diǎn)搜索中難以實(shí)現(xiàn)關(guān)鍵點(diǎn)精確搜索且搜索效率較低的問題，本文提出了基于關(guān)鍵數(shù)字特征遞歸機(jī)制的無線傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法，引入了關(guān)鍵點(diǎn)的數(shù)字特征遞歸機(jī)制。通過計(jì)算能量與坐標(biāo)之間的關(guān)系，實(shí)現(xiàn)了對關(guān)鍵點(diǎn)坐標(biāo)的準(zhǔn)確獲取，隨后通過精度提升機(jī)制，計(jì)算得到了關(guān)鍵點(diǎn)精度最佳情況下的CPEE取值，從而大大提高了關(guān)鍵點(diǎn)的坐標(biāo)精度。仿真實(shí)驗(yàn)表明：與當(dāng)前廣泛運(yùn)用到的WSN-Div算法相比，本文算法在關(guān)鍵點(diǎn)搜索成功率、定位開銷、搜索誤差度、搜索時間上具有明顯的優(yōu)勢，具有很強(qiáng)的實(shí)際部署價值。

參考文獻(xiàn)

［1］ LI Bin， WANG WenJie， YIN QinYe. A distributed localization in w ireless sensor networks utilizing AOD estimation and synthetically uniform circular array ［J］. Science China （Information Sciences）.2015， 06（17）:105-115.

［2］ Jack. An Efficient Algorithm for Mobile Localization in Sensor Networks ［J］.International Journal of Automation and Computing.2012， 06（78）:594-599.

［3］ 張?jiān)捶澹?程恩. 基于可控制粒子群優(yōu)化的無線傳感網(wǎng)關(guān)鍵點(diǎn)定位技術(shù)［J］.廈門大學(xué)學(xué)報， 2013， 06（32）: 739-743.

［4］ 歐陽丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.計(jì)算機(jī)科學(xué)， 2011， 07（16）: 46-50.

［5］ Georges M. Arnaout， Shannon Bow ling. A Progressive Deployment Strategy for Cooperative Adaptive Cruise Control to Improve Traffic Dynam ics ［J］. International Journal of Automation and Computing， 2014， 01（11）:10-18.

［6］ 朱烜璋. 基于水波擴(kuò)散機(jī)制的關(guān)鍵點(diǎn)搜索精度提升算法［J］.計(jì)算機(jī)工程與應(yīng)用， 2013， 14（35）:88-91.

［7］ 徐彤陽. NLOS誤差模型下的無線傳感網(wǎng)定位方法與仿真［J］.計(jì)算機(jī)工程與設(shè)計(jì)， 2013， 08（118）: 2680-2684.

［8］ Guo-Jin Feng， James Gu， Dong Zhen. Implementation of Envelope Analysis on a Wireless Condition Monitoring System for Bearing Fault Diagnosis ［J］. International Journal of Automation and Computing， 2015， 01（21）:14-24.

［9］ ChenLee. An Efficient A lgorithm for Mobile Localization in Sensor Networks ［J］. International Journal of Automation and Computing， 2012， 06（32）:594-599.

［10］ Yang Guoning， Feng Xiufang， Fan Liujuan. A multi sensor data fusion algorithm based on optimal fusion ［J］. Journal of software， 2012， 23（11）: 134-140.

Research on Key Point Searching Algorithm of W ireless Sensor Networks Based on Key Digital Feature Recursion M echanism

Tian Wenli
（Shanxi Vocational College of Finance and Economics， Xianyang 712000， China）

Abstract:The unavoidable background noise jamm ing results in the poor positional accuracy and search efficiency in the current key searching algorithm of the wireless sensor networks. In order to solve these problems， this paper proposes a point searching algorithm of wireless sensor network based on key digital feature recursion mechanism. Firstly， it evaluates the energy state of the key point by using the key digital feature recursion mechanism， and then collects the energy of the recursion key points' radio frequency information to search for the key point of w ireless sensor network. After that， it makes the fingerprint identification to the key digital feature value， and completes the precise estimation and positioning to the key points. The simulation results show that compared with the existing WSN-Div algorithm， the algorithm proposed in this paper has a high search success rate of the key points， as well as lower data location overhead and search error.

Key words:Wireless Sensor Networks； Key Point Search； Radio Frequency Information； Digital Feature Recursion； Fingerprint Identification

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號：1007-757X（2016）05-0065-03

作者簡介：田文利（1980-），女，寶雞人，陜西財經(jīng)職業(yè)技術(shù)學(xué)院，講師，碩士，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用、網(wǎng)絡(luò)信息安全，咸陽，712000

收稿日期:（2016.01.26）