一種虛擬力導(dǎo)向遺傳算法的無線傳感器網(wǎng)絡(luò)優(yōu)化部署策略

崔頻，王敏（江蘇科技大學(xué) 電信學(xué)院，江蘇鎮(zhèn)江212003）

一種虛擬力導(dǎo)向遺傳算法的無線傳感器網(wǎng)絡(luò)優(yōu)化部署策略

崔頻，王敏
（江蘇科技大學(xué) 電信學(xué)院，江蘇鎮(zhèn)江212003）

為了優(yōu)化無線傳感器網(wǎng)絡(luò)節(jié)點部署性能，在遺傳算法的基礎(chǔ)上結(jié)合虛擬力方法，同時考慮目標區(qū)域能耗平均的特點，提出了一種虛擬力導(dǎo)向遺傳算法的能耗均衡部署策略。構(gòu)建了節(jié)點的概率感知模型，通過網(wǎng)格劃分的方法計算覆蓋率，該策略通過遺傳算法來控制傳感器哪些節(jié)點需要移動，而節(jié)點的移動又反過來影響進化，從而能以更快速度達到所要求的網(wǎng)絡(luò)覆蓋率。仿真結(jié)果表明，與單純使用虛擬力算法與遺傳算法相比，在網(wǎng)絡(luò)生存期和部署時間等方面都具有更好的性能。

無線傳感器網(wǎng)絡(luò)；部署；虛擬力；遺傳算法

無線傳感器網(wǎng)絡(luò)節(jié)點部署是傳感器網(wǎng)絡(luò)進行工作的第一步，是網(wǎng)絡(luò)正常工作的基礎(chǔ)。只有把傳感器節(jié)點在目標區(qū)域布置好，才能進一步進行其它的工作和優(yōu)化[1-2]。虛擬力算法是主要的無線傳感器網(wǎng)絡(luò)動態(tài)部署方法之一[3-5]。

文獻[6]提出了一種基于節(jié)點間虛擬力的移動節(jié)點部署方法，利用節(jié)點之間的虛擬人工勢場產(chǎn)生的作用力來控制節(jié)點的運動，提高無線傳感器網(wǎng)絡(luò)的整體性能。文獻[7]建立了一個多目標非線性規(guī)劃問題的數(shù)學(xué)模型，提出了一種基于節(jié)省能耗的虛擬力優(yōu)化算法。很多應(yīng)用證明虛擬力算法在移動傳感器節(jié)點自組織動態(tài)部署優(yōu)化上效果明顯[8]，但在節(jié)能、重復(fù)覆蓋和覆蓋均勻性上存在不足之處。

本文結(jié)合虛擬力算法、遺傳算法、能耗均衡，研究了一種虛擬力導(dǎo)向遺傳算法的無線傳感器網(wǎng)絡(luò)優(yōu)化部署策略，實現(xiàn)了傳感器網(wǎng)絡(luò)在節(jié)能、收斂速度和部署時間上的優(yōu)化[9]。

1 無線傳感器網(wǎng)絡(luò)覆蓋模型

1.1 問題描述

為了獲得較高的無線傳感器網(wǎng)絡(luò)（wireless sensor networks,簡記為WSN）覆蓋率，最常用方法是增加節(jié)點的部署密度。但是大量使用傳感器節(jié)點首先使得網(wǎng)絡(luò)成本的上升，還會使網(wǎng)絡(luò)的數(shù)據(jù)傳輸沖突成指數(shù)倍增加，浪費了網(wǎng)絡(luò)能量，造成網(wǎng)絡(luò)的提前失效的結(jié)果。

根據(jù)無線傳感器網(wǎng)絡(luò)的特點[10]，本文有以下假設(shè)：

1）網(wǎng)絡(luò)中的節(jié)點可以自由的在工作和休眠兩種狀態(tài)之間任意轉(zhuǎn)換，中心節(jié)點具有較強的數(shù)據(jù)處理和計算能力；

2）網(wǎng)絡(luò)中每個節(jié)點都有獲取自己位置信息的能力并且能通過數(shù)據(jù)傳輸位置信息給中心節(jié)點；

3）網(wǎng)絡(luò)中的每個節(jié)點有相同的初始能量、感知半徑、通信半徑，且通信半徑設(shè)置為感知半徑的2倍。

4）可移動傳感節(jié)點夠根據(jù)計算結(jié)果準確的到達所需位置，完成網(wǎng)絡(luò)部署優(yōu)化工作。

1.2 節(jié)點檢查模型

2種主要的傳感器的感知模型：布爾感知模型和概率感知模型。布爾感知模型（即0-1模型）過于簡單，不能適應(yīng)傳感器的感知能力隨著傳輸距離增加而降低的特點。因此，考慮到實際檢測環(huán)境的復(fù)雜性，概率模型較布爾模型更能合理的表示傳感器節(jié)點的感知特性。本文將采用以下概率感知模型[11][12][13]：假設(shè)節(jié)點x（i）的坐標為（xi，yi），其感知半徑為RS（主程序中為r），不確定感知長度為Re，目標點Pj的坐標為（xx1(j，1)，yy1（j，1）），則節(jié)點x（i）與目標點Pj之間的距離d（x（i），Pj）可表示成表達式

目標點Pj被節(jié)點x（i）感知的概率是

其中，Re是傳感器節(jié)點不確定檢測能力的一個度量，α1=Re-Rs+d（x（i），Pj），α2=Re+Rs-d（x（i），Pj），λ1，λ2，β1，β2是與節(jié)點特性相關(guān)的參數(shù)。整個檢測區(qū)域內(nèi)所有傳感器節(jié)點Pj對目標節(jié)點的聯(lián)合檢測概率為：

其中，xall為檢測目標網(wǎng)格點的所有傳感器集合，Cth令是目標網(wǎng)格點能夠被檢出的閾值概率，當min {Cpj（xall，Pj）}≥Cth時，目標網(wǎng)格點能夠被檢出。

2 基于遺傳算法的虛擬力部署策略的基本原理

2.1 虛擬力原理

虛擬力方法是將移動傳感器網(wǎng)絡(luò)假設(shè)為一個虛擬物理系統(tǒng)，傳感節(jié)點、障礙物和熱點區(qū)域均可對傳感節(jié)點施加引力或斥力，節(jié)點移動方向和距離取決于該節(jié)點自身質(zhì)量、所處位置、剩余電量，以及所受網(wǎng)格點、鄰居節(jié)點的引力與斥力的合力，節(jié)點移動直至達到受力平衡或可移動距離的極限。

Fx、Fy為某一節(jié)點與其所有鄰居節(jié)點的距離之差的和，并且在節(jié)點與其鄰居節(jié)點之間的距離小于時候才有此虛擬的斥力。

節(jié)點由于虛擬力的作用，則位置（xold，yold）由位置更新公式[14[15]移動至新位置（xnew，ynew）：

其中，F(xiàn)xy是施加于傳感節(jié)點的虛擬力的合力，F(xiàn)x、Fy是虛擬力的x軸和y軸方向分量，MaxStep是傳感節(jié)點單跳移動的最大距離。從式（4）、（5）和式（6）可以看出，最終節(jié)點分布的最終位置取決于工作節(jié)點初始位置，單步移動的最大距離，部署區(qū)域大小，傳感器感知半徑大小。

2.2 遺傳算法

遺傳算法[16]（Genetic Algorithm，GA）是模擬生物界進化過程中，以“優(yōu)勝劣汰，適者生存”為法則的一種全局優(yōu)化概率搜索方法。

2.2.1 選擇操作

選擇操作是遺傳算法產(chǎn)生優(yōu)良后代的主要方式，是一種優(yōu)勝劣汰過程，可以產(chǎn)生比前一代更優(yōu)群體。本文采用輪盤賭選擇方式進行選擇操作。

2.2.2 交叉操作

交叉操作是遺傳算法的核心過程，通過2個父代基因組的交叉，產(chǎn)生新的個體。

2.2.3 變異操作

對交叉后的染色體，采取概率PMutation對其進行變異操作，變異的概率一般是相當?shù)男?，產(chǎn)生少量的新個體。

2.3 能量均衡

根據(jù)各個不同區(qū)域正在移動與總節(jié)點的比例調(diào)得到能耗均衡系數(shù)，從而得到能耗均衡值，而影響到適應(yīng)度，由遺傳算法的選擇、交叉、變異操作決定哪些節(jié)點移動，進而影響網(wǎng)絡(luò)部署覆蓋效率[17]。

3 部署算法設(shè)計

3.1 初始部署

在網(wǎng)絡(luò)部署的初始階段，為了能夠使監(jiān)測區(qū)域中的事件監(jiān)測到的概率達到既定要求，需要實現(xiàn)對監(jiān)測區(qū)域的合理布局。具體步驟如下：

1）在一定面積的二維平面中，隨機拋灑一定數(shù)量的無線傳感器節(jié)點，并盡量使其均勻分布。

2）對區(qū)域進行離散化，在x、y方向設(shè)置相同步長的網(wǎng)格，如果網(wǎng)格點的監(jiān)測達到0.9及以上，就認為該網(wǎng)格點是可檢測的。

3）計算初始覆蓋率和初始時的適應(yīng)度值。適應(yīng)度的值是有覆蓋率（ω1），下次循環(huán)之前不能移動的節(jié)點所占的比例（ω2），能耗均衡值（ω3）共同決定。具體的，參數(shù)分別設(shè)置為0.1、0.05、0.85。這樣是基于移動的目的是防止某個區(qū)域節(jié)點過于集中，因此偏重于能耗權(quán)重。

3．2 基于虛擬力的重部署

在本無線傳感器部署方法中，為了節(jié)省能量，每次不是所有傳感器都移動，而是通過遺傳算法，根據(jù)當前的覆蓋率，本次不移動的節(jié)點所占的比例，能耗均衡值，決定哪些節(jié)點移動。

基于虛擬力的思想，本文傳感器節(jié)點可以受到監(jiān)測區(qū)域中3類不同對象施加的作用力：網(wǎng)格點對節(jié)點的作用力、節(jié)點之間的相互作用力，邊界對節(jié)點的作用力。各個傳感器節(jié)點由于受到力的大小、方向不同而移動相應(yīng)的距離，直到達到平衡點或者達到邊界臨界點?，F(xiàn)在具體分析這3種力：

1）網(wǎng)格點對節(jié)點的作用力

沒有被覆蓋的網(wǎng)格點對移動的傳感器節(jié)點作用力，當且僅當沒有覆蓋的網(wǎng)格點到移動節(jié)點的距離大于感知半徑而小于通信半徑才有力的作用，在大于通信半徑時候，說明距離過遠，為保證覆蓋率不需移動，而小于感知半徑，說明該網(wǎng)格點正是在該節(jié)點的感知范圍之內(nèi)。網(wǎng)格點對傳感器節(jié)點的作用力主要表現(xiàn)為引力作用。

2）節(jié)點之間的作用力

移動無線傳感器節(jié)點之間，當其距離過小時候（仿真時設(shè)置閾值為1.4倍的感知半徑，d≤1.4r），就會在力的作用下發(fā)生移動，傳感器之間的相互作用力主要表現(xiàn)為斥力。

3）邊界對傳感器的約束作用力

由于我們是在一定面積之內(nèi)進行的模擬，故設(shè)置節(jié)點不能出邊界，必須在一定的坐標范圍之內(nèi)。

4 仿真結(jié)果分析

在Matlab R2012a中，在800℃*800℃的任務(wù)區(qū)域，采用遺傳算法進行仿真實驗，傳感器的感知距離Rs設(shè)為80℃，節(jié)點通信半徑為2Rs=Rc。在格點作用下的最大移動步長值為2.5℃，在傳感器節(jié)點作用下的最大移動步長3.5℃。檢測模型參數(shù)λ1=1，λ2=0，β1=1，β2=1.5，ω1、ω2、ω3的權(quán)值分別為 0.1、0.05、0.85，網(wǎng)絡(luò)覆蓋率閾值Cth=0.9，交叉概率0.8，變異概率0.2，種群數(shù)為30，最大迭代次數(shù)為50。

圖1 基于虛擬力的隨機部署

圖1中傳感器的最初位置是隨機的，并且沒有考慮覆蓋重疊和節(jié)點失效，而且移動中也沒有考慮到每次移動能量的消耗，是比較理想的情況下的結(jié)果。圖3中節(jié)點在僅有一半左右的節(jié)點在移動，大大節(jié)省了能量，并且考慮了各個區(qū)域的能量平衡，達到所要求的覆蓋率條件下而提高網(wǎng)絡(luò)的生存期。

無論是圖1還是圖3，雖然只進行了50次迭代，但已達較高覆蓋率，程序中的設(shè)置，出于節(jié)省能量考慮，每次移動的最大步長較小，且迭代次數(shù)并不是足夠的多，所以最后仍有沒有被覆蓋的區(qū)域。

圖3中，（a）是50個傳感器節(jié)點隨機部署，以節(jié)點的初始位置為圓心，以80℃（感知半徑）為半徑畫圓所得，（b）是所有節(jié)點在50次的迭代過程中的位置移動情況，（c）分別是網(wǎng)絡(luò)覆蓋率隨迭代次數(shù)的增加變化情況，（d）是傳感器節(jié)點最終位置和感知范圍。

圖2 虛擬力導(dǎo)向遺傳算法的優(yōu)化部署流程圖

圖3 使用了遺傳算法和能耗均衡的虛擬力移動部署

根據(jù)需要，如果側(cè)重網(wǎng)絡(luò)覆蓋率，則可以增加網(wǎng)絡(luò)覆蓋權(quán)重，減少其他兩項權(quán)重，如果側(cè)重網(wǎng)絡(luò)的能耗及其平衡，則可以增加能耗均衡權(quán)重。

表1 仿真結(jié)果

從表1可以很清晰的看出，使用遺傳算法之后，每次移動的節(jié)點個數(shù)僅為只使用虛擬力時的一半左右，對于很難補給能量或者不能補給能量的傳感器節(jié)點來說很重要，但是覆蓋率卻有所提高。

由于表1內(nèi)容僅僅只是顯示了迭代次數(shù)為10、20、30、40和50時候的能耗均衡值和系數(shù)，難免片面。圖4更加詳細的顯示了能耗均衡系數(shù)及其變化規(guī)律。

圖4 能量均衡系數(shù)

5 結(jié)束語

傳感器節(jié)點覆蓋優(yōu)化可以增強無線傳感器網(wǎng)絡(luò)的性能，提高傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量。因此較少的工作節(jié)點和節(jié)省能耗是延長網(wǎng)絡(luò)生存期的重要方法之一，基于虛擬力的傳感器網(wǎng)絡(luò)部署，并結(jié)合能量均衡策略和遺傳算法，能在保持一定覆蓋率的基礎(chǔ)上，最大限度延長網(wǎng)絡(luò)壽命。虛擬力導(dǎo)向遺傳優(yōu)化算法減少了不必要的能耗，增強了網(wǎng)絡(luò)性能，在僅移動部分節(jié)點的情況下，較快達到理想覆蓋率。但是本文并沒有考慮網(wǎng)絡(luò)的魯棒性，節(jié)點在什么情況下失效，以及怎么在一定數(shù)量的節(jié)點失效后，怎么樣提高網(wǎng)絡(luò)的覆蓋率。

[1]Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey [J].Computer Networks，2008，52 （12）：2292-2330.

[2]Baronti P，Pillai P，Chook V W C.Wirelesssensor networks：A survey on the state of the art and the 802.15.4 and ZigBee standards[J].Computer Communications，2007，30 （7）：1655-1695.

[3]Zou Y，Chakrabarty K．Sensor deployment and target localization based on virtual forces［C］// IEEE Infocom.Piscataway： IEEEPress，2003：1293-1303．

[4]張云亞，紀志成.虛擬力導(dǎo)向多粒子群算法的WSNs部署策略[J].江南大學(xué)學(xué)報：自然科學(xué)版，2012（4）：428-431.

[5]李明，石為人.虛擬力導(dǎo)向差分算法的異構(gòu)移動傳感網(wǎng)絡(luò)覆蓋策略[J].儀器儀表學(xué)報，2011（5）：1043-1050.

[6]周彤，洪炳镕，樸松昊.基于虛擬力的混合感知網(wǎng)節(jié)點部署[J].計算機研究與發(fā)展，2007（6）：965-972.

[7]田一鳴，陸陽，魏臻，等.無線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制及節(jié)能優(yōu)化研究[J].電子測量與儀器學(xué)報，2009（11）：65-71.

[8]Wang X，Wang S，MaJ J.Dynamic deployment optimization in wireless sensor networks［J］. Lecture Notes in Controland Infor-mation Sciences，2006（1）：182-187．

[9]王昌征，林琳.無線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制與協(xié)議能耗研究[J].通訊世界，2015（13）：142.

[10]王建華，史明岳，馮友兵.基于遺傳算法的能量均衡覆蓋控制策略[J].計算機仿真，2012（2）：105-108.

[11]劉維亭，范洲遠.基于混沌粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化 [J].計算機應(yīng)用，2011（2）：338-340，361.

[12]羅強.水下無線傳感器網(wǎng)絡(luò)的部署研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2011.

[13]王一楠.水下無線傳感器網(wǎng)絡(luò)的節(jié)點部署策略和算法的研究[D].南京：南京郵電大學(xué)，2013.

[14]李賢，何啟麗，唐秋玲，等.一種基于網(wǎng)格劃分的虛擬力部署算法的研究[J].廣西大學(xué)學(xué)報：自然科學(xué)版，2012（6）：1164-1169.

[15]錢開國，王偉，申時凱，等.基于蜂窩網(wǎng)格錨點的虛擬力導(dǎo)向節(jié)點部署算法[J].計算機測量與控制，2014（6）：1839-1841.

[16]王小平，曹立民.遺傳算法——理論、應(yīng)用與軟件[M].西安：西安交通大學(xué)出版社，2002.

[17]王冰.基于能量均衡的無線傳感器網(wǎng)絡(luò)覆蓋算法[D].長春：吉林大學(xué)，2013.

An optimal deployment strategy for wireless sensor networks based on virtual force oriented Genetic Algorithm

CUI Pin，WANG Min

（College of Telecommunication，Jiangsu University of Science and Technology，Zhenjiang 212003，China）

order to optimize the performance of wireless sensor network node deployment，combined with the virtual force method based on the genetic algorithm，considering the characteristics of the target area average energy consumption，energy balance presents a virtual force oriented Genetic Algorithm deployment strategy.Construct the probability perception model of nodes，through the method of grid computing coverage，the strategy adopted by the the genetic algorithm to control the sensor nodes which need to move，and the mobile node in turn affects evolution，which can more quickly reach the required network coverage.The simulation results show that with the simple use of virtual force algorithm compared with the genetic algorithm，it has better performance on network lifetime and deployment time.

Wireless Sensor Networks（WSN）；coverage；energy balance；Genetic Algorithm（GA）

TP393

A

1674－6236（2017）07-0087-05

2016-04-02稿件編號：201604019

崔 頻（1986—），女，河南永城人，碩士研究生。研究方向：水下無線傳感器網(wǎng)絡(luò)。