林威建　郝泳濤

摘要：針對基于移動節(jié)點的無線傳感器網(wǎng)絡覆蓋優(yōu)化問題。該文根據(jù)傳感器以及感知區(qū)域的特性建立了不規(guī)則的感知模型，并以覆蓋率最大、節(jié)點移動距離最小為目標建立了無線傳感器網(wǎng)絡覆蓋優(yōu)化模型。同時結(jié)合虛擬力算法，設(shè)計并實現(xiàn)了基于虛擬力的動態(tài)調(diào)整線性加速因子的粒子群算法，彌補虛擬力算法在局部搜索方面的不足。

關(guān)鍵詞： 無線傳感器網(wǎng)絡；覆蓋優(yōu)化；粒子群算法；虛擬力算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）28-0036-04

Research on Coverage Optimization Algorithm of Wireless Sensor Network Based on Particle Swarm Optimization

LIN Wei-jian，HAO Yon-tao

（CAD Resaerch Center of Tongji University， Shanghai 201804， China）

Abstract：The main research of works in the paper is the coverage optimization problem of wireless sensor network based on the mobile node. Firstly， establish irregular sense model according to the characteristics of sensors and sensing region， and establish a wireless sensor network coverage optimization model based on and maximum coverage with minimum node moving distance. Combined the particle swarm optimization （PSO） with the virtual force algorithm， we proposed particle swarm algorithm based on changing acceleration factor particle swarm optimization based on virtual force（VFCAPSO）. Comparison and analysis the results of the algorithm， we found the algorithm changing acceleration factor particle swarm optimization based on virtual force （VFCAPSO） is best.

Key words：WSN； coverage control； particle swarm optimization； virtual force

無線傳感器網(wǎng)絡（wireless sensor network，WSN）是由一組小功率受限且具備傳感和通信功能的節(jié)點組成。在無線傳感器網(wǎng)絡的各種應用中，網(wǎng)絡覆蓋是一個重要的衡量標準，它決定了傳感器網(wǎng)絡對覆蓋區(qū)域的監(jiān)測效果。合理的節(jié)點部署策略，不僅能夠提高對目標區(qū)域的覆蓋效果，也能有效利用傳感器網(wǎng)絡的資源，提高能量利用率，延長網(wǎng)絡壽命。

在實際的應用過程中，可以通過部署可移動的節(jié)點來應對地形環(huán)境、部署方式等限制。當檢測到網(wǎng)絡未達到預定的覆蓋效果時，計算一個新的位置并將節(jié)點移動到該位置，彌補覆蓋漏洞從而提高覆蓋率。同時，考慮到傳感器節(jié)點一旦部署，往往很難獲得可靠連續(xù)的能量供應，如何通過優(yōu)化部署策略，減少移動過程中的能量消耗也是重要的一個方面。本文針對包含移動節(jié)點的無線傳感器網(wǎng)絡，設(shè)計一種優(yōu)化的部署策略，使得無線傳感器網(wǎng)絡在多種因素的制約之下，能夠合理的部署無線傳感器節(jié)點的位置。這對于優(yōu)化資源分配，最大限度的覆蓋目標區(qū)域，保障網(wǎng)絡正常高效工作，延長網(wǎng)絡的使用壽命具有非常重要的意義。

1 研究現(xiàn)狀

國內(nèi)外許多學者相繼提出了針對移動傳感器網(wǎng)絡的覆蓋優(yōu)化問題算法：Howard， Zhou等人首度將勢場理論應用于傳感器網(wǎng)絡的覆蓋控制，通過假設(shè)虛擬勢場和虛擬受力，利用物理學定律指導網(wǎng)絡的布局優(yōu)化過程[1]。在傳感器經(jīng)過最初的隨機放置之后，使用虛擬力算法（VFA）作為傳感器部署策略，可以以提高覆蓋面。文獻[2]提出了一種用于無線傳感網(wǎng)絡布局優(yōu)化的粒子群優(yōu)化策略。該策略采用概率測量模型評價網(wǎng)絡測量性能，以網(wǎng)絡有效覆蓋率為優(yōu)化目標，通過粒子群算法搜索全局最優(yōu)布局方法。文獻[3]將粒子群算法和混沌算法相結(jié)合，求解以移動傳感節(jié)點位置為輸入?yún)?shù)網(wǎng)絡覆蓋面積為目標的無線傳感器網(wǎng)絡覆蓋優(yōu)化問題。文獻[4]提出了一種基于遺傳算法的移動無線傳感器網(wǎng)絡中節(jié)點再部署方法，利用多目標優(yōu)化對網(wǎng)絡的覆蓋率和節(jié)點的移動距離進行優(yōu)化，從而延長了網(wǎng)絡的生命周期。

2 無線傳感器網(wǎng)絡模型

2.1無線傳感器網(wǎng)絡節(jié)點感知模型

常用的節(jié)點感知模型包括以下三種：二元感知模型、概率感知模型[5]和不規(guī)則感知模型 [6]。針對基于移動節(jié)點的傳感器網(wǎng)絡優(yōu)化部署，為了更加貼近無線傳感器網(wǎng)絡的實際工作情況，本文采用文獻[6]提出的不規(guī)則感知模型，采用如下定義計算傳感器節(jié)點的感測概率：

[Ss，p=0，dsi，p>Rpe-ξds，p-Rc，Rc≤dsi，p≤Rp1，dsi，p

式中[ξ]表示衰減因子，視具體的部署場景以及傳感器功率和類型而定。[Rc]表示可信半徑，在此半徑內(nèi)能夠100%地監(jiān)測到物理事件。[ai]為節(jié)點在第[i]方向上可變半徑系數(shù)。[Rp]表示最大半徑，大于[Rp]則無法感測到物理事件。[dsi，p]表示[Si]和[P]之間的歐幾里得距離，即傳感器[Si]部署在點[xi，yi]上，[x，y]中的任意點[P]，[dSi，P=xi-x2+yi-y2]。

不規(guī)則感知模型在某些特殊情況下可以轉(zhuǎn)換為二元感知模型和概率感知模型。當[Ri=Rp]時，不規(guī)則感知模型退化成了二元感知模型，檢測半徑[x=Ri=Rp]。而當設(shè)置所有感測方向上的不規(guī)則感知半徑為理論最大感測半徑，即上述[ai=1，i=1，2，3…n]時，不規(guī)則感知模型退化成了簡單的概率感知模型。

2.2無線傳感器網(wǎng)絡覆蓋優(yōu)化模型

2.2.1度量標準

1） 覆蓋率度量

覆蓋率定義為受到檢測的區(qū)域大小與整個目標區(qū)域大小的比值。關(guān)于覆蓋率的計算，我們通過網(wǎng)格來實現(xiàn)：將受檢測區(qū)域劃分為大小相等的網(wǎng)格，計算每個網(wǎng)格點受到檢測的概率，統(tǒng)計檢測概率大于某一值的網(wǎng)格數(shù)量進而計算出目標區(qū)域的覆蓋率。

對于某個網(wǎng)格，我們將它被整個監(jiān)測區(qū)域中的所有傳感器節(jié)點檢測到得概率定義為聯(lián)合檢測概率[13，15]，網(wǎng)格P的聯(lián)合檢測概率如下公式所示：

[CpSall，p=1-i=n1-CpSi，p]

式中[Sall]表示測量目標點的傳感器節(jié)點集合，[CpSi，p]為傳感器[Si]對目標點[p]的感知概率。

令[Cth]為目標點能夠被檢測到的概率閾值，則目標點能被有效檢測到的條件為：

[minxpypCpSall，p≥Cth]

若網(wǎng)格點i被覆蓋，則令標志位[Cov_flagi=1]，否則[Cov_flagi=0]。則算法覆蓋率定義如下：

[Cov=i=1NGCov_flagi/NG]

NG 為在感興趣區(qū)域劃分的網(wǎng)格總數(shù)[7]。

2）節(jié)點移動距離度量

在移動過程中需要考慮目標區(qū)域中所有節(jié)點的移動總能耗。假設(shè)節(jié)點變換位置時都按照直線方式移動，而移動能耗與移動距離成正比，因此該問題轉(zhuǎn)化成了節(jié)點的移動距離之和?？梢詫⒍攘繕藴时硎救缦耓3]：

[Dis=i=1kdi]

其中[di]表示傳感器節(jié)點[Si]從初始部署位置移動到最終位置的距離。

2.2.2優(yōu)化目標函數(shù)

本文提出的綜合考慮覆蓋率和移動距離的目標函數(shù)如下：

[E=maxf1?Cov+f2?1DisNL+1]

其中，Cov表示覆蓋率計算公式，Dis表示傳感器節(jié)點移距離，N表示目標區(qū)域部署的傳感器節(jié)點數(shù)量，L 表示目標區(qū)域為L*L的矩形區(qū)域的邊長，F(xiàn)1表示覆蓋率優(yōu)化目標所占的權(quán)重，F(xiàn)2表示移動距離優(yōu)化目標所占的權(quán)重。

實驗證明，該公式能夠適應覆蓋范圍以及節(jié)點數(shù)目的變化，在目標范圍變化后不需要調(diào)整權(quán)重就能達到預先設(shè)置的優(yōu)化目標。

3 粒子群算法解決無線傳感器網(wǎng)絡覆蓋優(yōu)化問題

3.1粒子群算法介紹

粒子群算法（particle swarm optimization， PSO）是由Kennedy和 Eberhart于1995 年提出的一種優(yōu)化算法[8，9]。PSO算法中每個粒子代表了解空間中的一個解，粒子依據(jù)同伴及自己的搜索經(jīng)驗來動態(tài)調(diào)整自己的搜索位置和速度。

在一個規(guī)模為N的粒子群中，粒子i（i=1，2，…，N）將根據(jù)下面的公式來更新自己的速度和位置[10]：

[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi），Xi=Xi+Vi，]

式中[xi]表示第[ii=1，2，3…N]個粒子的當前位置，[Vi]表示第[ii=1，2，3…N]個粒子的當前速度，pBest[i]表示粒子i所經(jīng)歷過的歷史最優(yōu)位置，pBest[g]表示網(wǎng)絡中所有粒子經(jīng)歷過的最優(yōu)位置，rand（）、Rand（）表示[0，1]上的隨機數(shù)，[ω]表示慣性權(quán)重（inertia weight），取值為0.8，c1、c2是個兩個常數(shù)，稱為學習因子。本文設(shè)置c1=c2=1，使得粒子具有相同的全局和局部搜索能力。

3.2粒子編碼

在實際應用當中，粒子的編碼分為兩部分，一部分是粒子的位置，一部分是粒子的速度。假設(shè)傳感器網(wǎng)絡中有N個節(jié)點，每個節(jié)點都有X、Y兩個位置坐標，網(wǎng)絡對目標區(qū)域的覆蓋率作為決策變量，也就是說傳感器節(jié)點最優(yōu)部署位置的維數(shù)空間為2N，所以將粒子編碼設(shè)計成一個大小為2N的向量。向量中的每一個分量表示某個傳感器節(jié)點的X或Y方向的位置。

單個粒子位置的編碼設(shè)計為：

[X=X1，Y1，X2，Y2……Xn，Yn]

那么單個粒子在空間中的飛行速度編碼的設(shè)計為：

[V=VX1，VY1，VX2，VY2，……VXn，VYn]

整個粒子群中所有粒子采用相同的位置和速度編碼，并且每個粒子的位置和速度向量單獨計算。

3.3適應度函數(shù)

以覆蓋率最大并且節(jié)點移動距離最小為目標函數(shù)的優(yōu)化方案，其適應度函數(shù)為：

[fitness=f1?Cov+f2?1DisNL+1]

3.4算法流程

第一步 初始化各個參數(shù)

根據(jù)配置初始化算法參數(shù)、模型參數(shù)以及傳感器節(jié)點屬性。

第二步 初始化粒子群

初始化粒子群的方法：目標區(qū)域的范圍[posMin，posMax]內(nèi)，選取2N隨機數(shù)構(gòu)成N個傳感器節(jié)點的初始位置（x，y），并以這個初始位置構(gòu)成的向量初始化整個粒子群中所有粒子的位置向量。粒子群中所有粒子的位置向量均為[X=X1，Y1，X2，Y2……Xn，Yn]。對于粒子的速度來說，粒子速度的初始化值均為0。粒子群中所有粒子的速度向量均為[V=VX1，VY1，VX2，VY2，……VXn，VYn]。

第三步 根據(jù)粒子適應度函數(shù)計算各粒子的適應度值

使用上文提到的適應度計算方法計算某個粒子的適應度函數(shù)值。

第四步 迭代更新粒子的速度和位置

當算法運行到第n次迭代時，比較所有粒子搜索到的歷史最優(yōu)位置pBest[i]，i=1，2，…N，并取最好位置來更新全局最優(yōu)位置gBest。在第k+1次迭代，所有粒子的位置和速度按照位置更新方程和速度更新方程進行更新。在更新的過程中，粒子在每一維上的飛行速度的上下限為Vmax和Vmin；粒子在每一維上的位置的上下限位posMax和posMin。

第五步 循環(huán)迭代，判斷是否滿足終止條件

滿足終止條件時，停止迭代，輸出全局最優(yōu)位置；否則，循環(huán)迭代，轉(zhuǎn)入第三步。一般設(shè)置最大迭代次數(shù)作為算法的終止條件。

4 改進的粒子群算法解決無線傳感器網(wǎng)絡覆蓋優(yōu)化問題

文獻[11]通過類比的手法，引入物理學中的庫倫力和萬有引力的模型，提出了一種基于虛擬力的覆蓋優(yōu)化方法。但是此算法并不適合于網(wǎng)格模型：當網(wǎng)格面積過小且數(shù)量很多，即感知精度較高的時候，往往會使得某塊未覆蓋的區(qū)域內(nèi)包含過多的小網(wǎng)格，每個網(wǎng)格都對附近的節(jié)點產(chǎn)生引力，從而使得傳感器節(jié)點收到的引力過大導致過快的運動，錯過了需要覆蓋的區(qū)域。

本文針對不規(guī)則感知模型的復雜性，在上述虛擬力算法的基礎(chǔ)上進行了改進，避免了因網(wǎng)格面積過小而網(wǎng)格數(shù)量過大產(chǎn)生的引力疊加問題，并成功與粒子群算法相結(jié)合，提出了一種基于虛擬力的粒子群算法來求解無線傳感器網(wǎng)絡覆蓋優(yōu)化問題。

4.1改進虛擬力模型

首先，目標區(qū)域被分成許多個面積相等的小網(wǎng)格，將目標區(qū)域的覆蓋轉(zhuǎn)化為對小網(wǎng)格的覆蓋，未覆蓋的小網(wǎng)格對附近的傳感器節(jié)點具有吸引力，使算法能夠?qū)⒐?jié)點移到未覆蓋的區(qū)域，增加覆蓋率。將未覆蓋點對傳感器的吸引力定義為：

[Fik=riskdik2，ri

其中，[Fik]為第K個未覆蓋的網(wǎng)格對傳感器節(jié)點i產(chǎn)生的引力，[dik]為兩者之間的距離，[ri]定義為傳感器節(jié)點的可靠感知半徑，[Ri]為傳感器節(jié)點的通信半徑，而[Sk]為第K個未覆蓋的網(wǎng)格的面積。

為避免多個傳感器節(jié)點的覆蓋區(qū)域產(chǎn)生重合，定義了兩個節(jié)點之間具有斥力。將兩個傳感器節(jié)點之間的虛擬力定義為：

[Fij=rirjdij2，dij

其中[dij]為傳感器節(jié)點之間的距離，[Ri，Rj]為兩個傳感器的通信半徑，[ri，rj]為兩個傳感器的感知半徑，兩個傳感器收到大小相等方向相反的作用力與反作用力。

4.2結(jié)合粒子群算法

粒子編碼同標準粒子群算法一致，唯一不同的是為每個傳感器增加了虛擬力。通過將粒子群算法中單個粒子的速度和位置更新公式改進如下，使得粒子群算法和虛擬力算法相結(jié)合：

[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi）+c3*Fi，Xi=Xi+Vi，]

速度更新公式的前半段和標準粒子群一樣，主要不同是增加了虛擬力部分c3*Fi，可以理解為使用粒子受力產(chǎn)生的加速度來更新粒子的運動速度。其中c3為虛擬力加速因子，與c1、c2的值比較接近，c3過大很有可能導致粒子受力過大飛過未覆蓋點，F(xiàn)i為節(jié)點i受到的X或Y方向上的合力，Vi為該粒子的第i維速度。本文中c3取值為0.4。

由于虛擬力對粒子更新位置有積極的指導作用，所以算法收斂速度較快，但是在算法后期由于虛擬力的存在，粒子在進行局部搜索的時候會被虛擬力阻礙，往往無法搜索到更優(yōu)的解。因此本文對上述虛擬力加速因子c3進行動態(tài)調(diào)整，在算法初期保持c3具有較大的一個值，并隨著迭代次數(shù)的增加，c3逐漸減小。其更新公式為：

[c3=c3begin+g×c3end-c3begingmax]

c3在開始的時候取值為0.5，在結(jié)束的時候取值為0.2。在算法前期主要發(fā)揮虛擬力算法的優(yōu)勢，使得算法盡快地進行收斂，粒子單獨搜索整個解空間，在算法后期減小虛擬力的影響，發(fā)揮粒子群算法的優(yōu)勢，重點對全局最優(yōu)解附近的解空間進行精確搜索，找到更優(yōu)解。

仿真結(jié)果顯示，結(jié)合虛擬力的動態(tài)線性調(diào)整慣性權(quán)值和加速因子的粒子群算法（VFCAPSO）迭代速度以及最大覆蓋率均優(yōu)于標準粒子群算法，取得了比較好的效果。

5 算法仿真和測試

本節(jié)使用的不規(guī)則感知模型參數(shù)設(shè)置如下：

傳感器節(jié)點可靠感知半徑為18，最大可感區(qū)域為30，通信半徑為40，節(jié)點一共有180個方向，每個方向上在可靠感知半徑和最大可感區(qū)域內(nèi)被分成10塊區(qū)段，衰減因子為0.05。

相關(guān)設(shè)置以及節(jié)點的效果圖具體如圖1所示：

算法的運行結(jié)果如圖3，分別為適應度每代最大，以及每代適應度最大所對應的節(jié)點移動距離，每代適應度最大所對應的覆蓋率。

6 結(jié)束語

本文采用了文獻[6]中提出的不規(guī)則感知模型，并建立了綜合考慮覆蓋率和移動距離為目標的數(shù)學模型，驗證了以覆蓋率和移動距離為目標的數(shù)學模型能夠在保證覆蓋率的前提下有效減少節(jié)點的移動距離。將粒子群算法應用到無線傳感器網(wǎng)絡覆蓋優(yōu)化問題中去，并對已有的算法進行了改進，成功地將自適應調(diào)整慣性因子的粒子群算法（APSO）、混沌粒子群算法（CPSO）、線性調(diào)整加速因子的粒子群算法（CAPSO）應用到無線傳感器網(wǎng)絡覆蓋優(yōu)化中去，并結(jié)合虛擬力算法提出了基于虛擬力的動態(tài)調(diào)整線性加速因子的粒子群算法（VFCAPSO）、基于虛擬力的粒子群算法（VFPSO）和基于虛擬力的遺傳算法（VFGA）算法，經(jīng)過仿真實驗驗證了新算法的有效性。通過比較分析，有效的驗證了虛擬力算法對算法性能的提升，同時驗證了本文提出的三種結(jié)合虛擬力算法中VFCAPSO性能最好，同時適用于覆蓋率最大為目標和綜合考慮覆蓋率和移動距離為目標的優(yōu)化模型。

參考文獻：

[1] Zou Y， Chakrabarty K. Sensor deployment and target localization based on virtual forces[J].IEEE societies，2003，2（1）：293-303.

[2] 林祝亮，馮遠靜.基于粒子群算法的無線傳感網(wǎng)絡覆蓋優(yōu)化策略[J].計算機仿真，2009，26（4）：190-193.

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

[4] 南國芳，陳忠楠.基于進化優(yōu)化的移動感知節(jié)點部署算法[J].電子學報，2012，40（5）：1017-1022.

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

[6] 趙小敏，毛科技，何文秀，等.感測范圍不規(guī)則情況下無線傳感器網(wǎng)絡節(jié)點部署算法[J].軟件學報，2012，23（1）：59-68.

[7] 王偉，林鋒，周激流.無線傳感器網(wǎng)絡覆蓋問題的研究進展[J].計算機應用研究，2010，27（1）：32-35.

[8] Shi Y， Eberhart R. A modified particle swarm optimizer[C]. In： IEEE World Congress on Computational Intelligence，1998：69-73.

[9] 馮翔，陳國龍，郭文忠.粒子群優(yōu)化算法中加速因子的設(shè)置與試驗分析[J].集美大學學報：自然科學版，2006，11（2）：146-150.

[10] SEAPAHN MEGERIAN， FARINAZ KOUSHANFAR， GANG QU， GIACOMINO VELTRI， MIODRAG POTKONJAK. Exposure in Wireless Sensor Networks： Theory and Practical Solutions[J].Wireless Networks，2002（8）：443-454.

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