一種虛擬力導向遺傳算法的無線傳感器網絡優化部署策略

崔頻，王敏（江蘇科技大學 電信學院，江蘇鎮江212003）

一種虛擬力導向遺傳算法的無線傳感器網絡優化部署策略

崔頻，王敏
（江蘇科技大學 電信學院，江蘇鎮江212003）

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

無線傳感器網絡；部署；虛擬力；遺傳算法

無線傳感器網絡節點部署是傳感器網絡進行工作的第一步，是網絡正常工作的基礎。只有把傳感器節點在目標區域布置好，才能進一步進行其它的工作和優化[1-2]。虛擬力算法是主要的無線傳感器網絡動態部署方法之一[3-5]。

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

本文結合虛擬力算法、遺傳算法、能耗均衡，研究了一種虛擬力導向遺傳算法的無線傳感器網絡優化部署策略，實現了傳感器網絡在節能、收斂速度和部署時間上的優化[9]。

1 無線傳感器網絡覆蓋模型

1.1 問題描述

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

根據無線傳感器網絡的特點[10]，本文有以下假設：

1）網絡中的節點可以自由的在工作和休眠兩種狀態之間任意轉換，中心節點具有較強的數據處理和計算能力；

2）網絡中每個節點都有獲取自己位置信息的能力并且能通過數據傳輸位置信息給中心節點；

3）網絡中的每個節點有相同的初始能量、感知半徑、通信半徑，且通信半徑設置為感知半徑的2倍。

4）可移動傳感節點夠根據計算結果準確的到達所需位置，完成網絡部署優化工作。

1.2 節點檢查模型

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

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

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

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

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

2.1 虛擬力原理

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

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

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

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

2.2 遺傳算法

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

2.2.1 選擇操作

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

2.2.2 交叉操作

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

2.2.3 變異操作

對交叉后的染色體，采取概率PMutation對其進行變異操作，變異的概率一般是相當的小，產生少量的新個體。

2.3 能量均衡

根據各個不同區域正在移動與總節點的比例調得到能耗均衡系數，從而得到能耗均衡值，而影響到適應度，由遺傳算法的選擇、交叉、變異操作決定哪些節點移動，進而影響網絡部署覆蓋效率[17]。

3 部署算法設計

3.1 初始部署

在網絡部署的初始階段，為了能夠使監測區域中的事件監測到的概率達到既定要求，需要實現對監測區域的合理布局。具體步驟如下：

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

2）對區域進行離散化，在x、y方向設置相同步長的網格，如果網格點的監測達到0.9及以上，就認為該網格點是可檢測的。

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

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

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

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

1）網格點對節點的作用力

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

2）節點之間的作用力

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

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

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

4 仿真結果分析

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

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

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

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

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

圖2 虛擬力導向遺傳算法的優化部署流程圖

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

根據需要，如果側重網絡覆蓋率，則可以增加網絡覆蓋權重，減少其他兩項權重，如果側重網絡的能耗及其平衡，則可以增加能耗均衡權重。

表1 仿真結果

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

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

圖4 能量均衡系數

5 結束語

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

[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]張云亞，紀志成.虛擬力導向多粒子群算法的WSNs部署策略[J].江南大學學報：自然科學版，2012（4）：428-431.

[5]李明，石為人.虛擬力導向差分算法的異構移動傳感網絡覆蓋策略[J].儀器儀表學報，2011（5）：1043-1050.

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

[7]田一鳴，陸陽，魏臻，等.無線傳感器網絡虛擬力覆蓋控制及節能優化研究[J].電子測量與儀器學報，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]王昌征，林琳.無線傳感器網絡虛擬力覆蓋控制與協議能耗研究[J].通訊世界，2015（13）：142.

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

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

[12]羅強.水下無線傳感器網絡的部署研究[D].長沙：國防科學技術大學，2011.

[13]王一楠.水下無線傳感器網絡的節點部署策略和算法的研究[D].南京：南京郵電大學，2013.

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

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

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

[17]王冰.基于能量均衡的無線傳感器網絡覆蓋算法[D].長春：吉林大學，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—），女，河南永城人，碩士研究生。研究方向：水下無線傳感器網絡。