田文利

?

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

田文利

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

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

0 引言

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

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

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

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

由于在進(jìn)行關(guān)鍵點(diǎn)搜索過(guò)程中需要通過(guò)對(duì)關(guān)鍵點(diǎn)的射頻信號(hào)進(jìn)行遞歸，而對(duì)于任意關(guān)鍵點(diǎn)而言。其能量發(fā)射強(qiáng)度較之其他節(jié)點(diǎn)將具有顯著的能量強(qiáng)度優(yōu)勢(shì)［7］，此外對(duì)于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 ］。因此，可以通過(guò)將CPEE指標(biāo)作為關(guān)鍵數(shù)字特征，以便實(shí)現(xiàn)對(duì)關(guān)鍵點(diǎn)的搜索。

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

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

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

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

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

整個(gè)遞歸過(guò)程如下所示：

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

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

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

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

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

圖1 算法流程圖

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

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

表1 仿真參數(shù)表

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

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

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

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

（2）定位開(kāi)銷(xiāo)

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

圖3 兩種算法的定位開(kāi)銷(xiāo)測(cè)試

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

（3）搜索誤差度

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

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

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

（4）搜索時(shí)間

本文算法與WSN-Div算法在搜索時(shí)間上的對(duì)比如圖5所示：

圖5 兩種算法的搜索時(shí)耗測(cè)試

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

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

3 總結(jié)

為解決無(wú)線傳感網(wǎng)關(guān)鍵點(diǎn)搜索中難以實(shí)現(xiàn)關(guān)鍵點(diǎn)精確搜索且搜索效率較低的問(wèn)題，本文提出了基于關(guān)鍵數(shù)字特征遞歸機(jī)制的無(wú)線傳感網(wǎng)關(guān)鍵點(diǎn)搜索算法，引入了關(guān)鍵點(diǎn)的數(shù)字特征遞歸機(jī)制。通過(guò)計(jì)算能量與坐標(biāo)之間的關(guān)系，實(shí)現(xiàn)了對(duì)關(guān)鍵點(diǎn)坐標(biāo)的準(zhǔn)確獲取，隨后通過(guò)精度提升機(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)搜索成功率、定位開(kāi)銷(xiāo)、搜索誤差度、搜索時(shí)間上具有明顯的優(yōu)勢(shì)，具有很強(qiáng)的實(shí)際部署價(jià)值。

參考文獻(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ú)線傳感網(wǎng)關(guān)鍵點(diǎn)定位技術(shù)［J］.廈門(mén)大學(xué)學(xué)報(bào)， 2013， 06（32）: 739-743.

［4］ 歐陽(yáng)丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無(wú)線傳感器網(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］ 徐彤陽(yáng). NLOS誤差模型下的無(wú)線傳感網(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

中圖分類(lèi)號(hào)：TP393

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

文章編號(hào)：1007-757X（2016）05-0065-03

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

收稿日期:（2016.01.26）