張江山 熊哲源

(江西警察學(xué)院安全管理系 江西南昌 103003)

無線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是由部署于所監(jiān)控區(qū)域內(nèi)的大量微小傳感器構(gòu)成，可把采集到的監(jiān)控信息發(fā)送給外部終端監(jiān)測人員[1]。無線傳感網(wǎng)絡(luò)的應(yīng)用非常廣泛，現(xiàn)已是一個國內(nèi)外關(guān)注比較多的領(lǐng)域，網(wǎng)絡(luò)覆蓋是影響無線傳感網(wǎng)絡(luò)工作效率主要因素之一。目前，市場上已有很多種類的無線傳感節(jié)點(diǎn)如視頻傳感器節(jié)點(diǎn)、圖像傳感器節(jié)點(diǎn)、超聲波傳感器節(jié)點(diǎn)、紅外線傳感器節(jié)點(diǎn)等具有強(qiáng)感知的方向性[2]。如果能研究一種方法來控制這些全向傳感器的方向，增強(qiáng)網(wǎng)絡(luò)覆蓋范圍將有一定的現(xiàn)實(shí)意義。

該文對多媒體傳感網(wǎng)絡(luò)的有向傳感器感知方向控制方法進(jìn)行了深入研究探討，在節(jié)點(diǎn)之間假設(shè)存在萬有引力和排斥庫倫力叫作擬物力，提出一種改進(jìn)的粒子群算法?；诹Ｗ尤核惴由蠑M物力的算法對傳感網(wǎng)的有向傳感器感知方向和位置進(jìn)行計(jì)算控制，能有效地提高無線傳感網(wǎng)絡(luò)覆蓋率。

1 覆蓋優(yōu)化流程

1.1 網(wǎng)絡(luò)覆蓋定義

目前，常用來衡量傳感器網(wǎng)絡(luò)覆蓋性能的指標(biāo)主要有：覆蓋率、覆蓋效率、覆蓋均勻性和覆蓋度[3]。該文把提高的網(wǎng)絡(luò)覆蓋率作為網(wǎng)絡(luò)增強(qiáng)覆蓋算法的追求。覆蓋率的定義如下。

其中，Si、S、N分別表示一只傳感器節(jié)點(diǎn)覆蓋面積、監(jiān)測區(qū)域總面積、網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)量。P的取值為[0，1]。

1.2 覆蓋增強(qiáng)優(yōu)化流程

網(wǎng)絡(luò)覆蓋優(yōu)化增強(qiáng)分3 個階段：網(wǎng)絡(luò)初始化階段劃分連通子網(wǎng)、改進(jìn)粒子群優(yōu)化算法計(jì)算控制方向最優(yōu)值、調(diào)節(jié)節(jié)點(diǎn)感知方向，覆蓋優(yōu)化流程如圖1 所示。組網(wǎng)的有向傳感器隨機(jī)部署后，由匯聚節(jié)點(diǎn)啟動整個網(wǎng)絡(luò)的工作初始化節(jié)點(diǎn)位置、感知半徑、感知方向等。利用優(yōu)先遍歷算法根據(jù)節(jié)點(diǎn)的感知半徑和位置信息將整個無線網(wǎng)絡(luò)劃分成若干個連通子圖，運(yùn)用改進(jìn)式粒子群優(yōu)化算法對傳感連通子網(wǎng)的各個有向傳感器感知方向進(jìn)行最優(yōu)計(jì)算，算出各傳感節(jié)點(diǎn)的最佳感知方向，各子網(wǎng)的匯聚節(jié)點(diǎn)通過多跳無線通信方式將感知方向值派發(fā)到各自的節(jié)點(diǎn)，網(wǎng)絡(luò)中各節(jié)點(diǎn)根據(jù)接收的計(jì)算結(jié)果自發(fā)調(diào)整感知方向，從而實(shí)現(xiàn)了整個網(wǎng)絡(luò)覆蓋增強(qiáng)。

圖1 覆蓋增強(qiáng)流程圖

2 粒子群算法優(yōu)化

2.1 PSO算法優(yōu)化

粒子群算法優(yōu)化（Particle Swarm Optimization，PSO）是一種基于自然界鳥類尋覓食物的仿生搜索算法[4]，此前，已有很多學(xué)者對其進(jìn)行了研究和分析，此算法具有參數(shù)少容易實(shí)現(xiàn)，簡單高效的優(yōu)點(diǎn)。

在粒子群優(yōu)化算法中，群被稱為粒子群，群中的個體稱為一個粒子，用來表示優(yōu)化問題的一個解向量。有N個粒子，每個粒子都一個有D維位置向量和一個D 維速度向量，Xi=(Xi1，Xi2，…，XiD)表示粒子位置向量，Vi=(Vi1，Vi2，…，ViD)表示粒子速度向量。算法初始每個粒子隨機(jī)產(chǎn)生位置和速度，然后進(jìn)行迭代更新，每個粒子第K+1次更新位置和速度的公式為

式中，C1和C2是學(xué)習(xí)因子，是兩個正常數(shù)取值為2，R1和R2為（0，1）區(qū)間的隨機(jī)數(shù)。Vid(K+1)和xid(k+1)是第K+1 次迭代粒子i第D維的速度和位置。每個粒子有一個適應(yīng)值，式（1）中的第一部分W是慣性權(quán)重因子，用于算法控制搜索步長；第二部分表示粒子不斷地趨向的自己最好位置；第三部分表示粒子會趨向整個網(wǎng)絡(luò)的傳感節(jié)點(diǎn)的最佳位置。粒子群中的每個粒子在解空間內(nèi)不斷迭代計(jì)算，改變調(diào)整自己的速度和位置，并逐漸趨向全局最佳位置和方向，直到最大迭代次數(shù)達(dá)到規(guī)定值或滿足規(guī)定的誤差標(biāo)準(zhǔn)時算法結(jié)束。

2.2 POS優(yōu)化算法不足

粒子群算法雖然具有簡單易實(shí)現(xiàn)、控制參數(shù)少、具有并行性等優(yōu)點(diǎn)，但同其他優(yōu)化算法一樣也有些固有的缺點(diǎn)，具體為：（1）在后期階段收斂速度比較慢；（2）當(dāng)問題解空間維度比較高時，容易出現(xiàn)“早熟收斂”現(xiàn)象，陷入局部最優(yōu)；（3）控制參數(shù)少，但對算法的精度和效率影響很大，在不同的應(yīng)用環(huán)境不同的優(yōu)化問題，參數(shù)的最優(yōu)設(shè)置值需要通過大量實(shí)驗(yàn)或憑經(jīng)驗(yàn)確定。

2.3 擬物力算法

擬物算法也是從自然界中得以啟發(fā)而學(xué)來的一種優(yōu)化算法[5]，可以用于解決復(fù)雜程度不確定性的問題。該文提出把擬物力算法和粒子群優(yōu)化算法結(jié)合在一起優(yōu)化網(wǎng)絡(luò)覆蓋的想法，利用兩種算法相結(jié)合來改進(jìn)粒子的位置與速度更新迭代過程，使喚粒子改變移動方向、收斂加快，擬物力算法可以更好地調(diào)整粒子間的距離，使得無線傳感網(wǎng)絡(luò)更有效地覆蓋監(jiān)控區(qū)域。與基本粒子群算法比較，融入了擬物力算法后的粒子群算法有更強(qiáng)的全局搜索能力，無線傳感網(wǎng)絡(luò)收斂更快，能更早達(dá)到全局最優(yōu)狀態(tài)，降低算法耗時與冗余覆蓋也降低了。擬物力[6]算法主要包括擬萬有引力和擬庫侖力。

2.3.1 擬萬有引力

將每一個傳感器節(jié)點(diǎn)看作為一個規(guī)則的半徑為r的圓盤[7]，如果兩個圓盤之間距離小于通信距離的就會產(chǎn)生引力，稱擬萬有引力，大于通信距離的節(jié)點(diǎn)不會產(chǎn)生引力，“擬萬有引力”可表達(dá)如下。

2.3.2 擬庫侖力

節(jié)點(diǎn)的圓盤會產(chǎn)生交疊覆蓋情況，要增強(qiáng)網(wǎng)絡(luò)覆蓋就應(yīng)盡量減少節(jié)點(diǎn)圓盤交。擬庫侖力就是如果兩個圓盤之間的距離小于圓盤距離閾值就會相互之間有排斥力，每個節(jié)點(diǎn)圓盤排斥與自己距離過近的其他圓盤，以便減少交叉覆蓋。根據(jù)庫侖力定理，無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)圓盤間的斥力勢表達(dá)式為

式（3）（4）中，fij表示節(jié)點(diǎn)圓盤之間虛擬力（吸引力或排斥力）；dij為節(jié)點(diǎn)之間的歐拉距離；RC為節(jié)點(diǎn)通信距離；wb為排斥力系數(shù)；wa為引力系數(shù)。

2.4 算法的覆蓋優(yōu)化方案設(shè)計(jì)

為了改善粒子群算法收斂慢和早熟收斂的問題，該文提出了擬物力和基本粒子群優(yōu)化算法相融的算法方案，根據(jù)擬物力作用策略，改進(jìn)基本粒子群算法的速度迭代公式，后面加上擬物力算法式子，位置的迭代方式不變，速度迭代表達(dá)式如下。

式（6）中w、c1、R1、c2、R2和式（1）中的相關(guān)解釋式相同。c3、c4分別為擬萬有引力系數(shù)和擬庫侖力系數(shù)；r3、r4為兩個隨機(jī)數(shù)（0～1）；f1ij(n)、f2ij(n)為節(jié)點(diǎn)受到的擬萬有引力合力和庫侖力合力，計(jì)算每個傳感器節(jié)點(diǎn)受到的其他節(jié)點(diǎn)的萬有引力合力和庫倫力合力并水平和縱向分解，然后計(jì)算各節(jié)點(diǎn)分解力水平和縱向的萬有引力和昆侖力的合力。

把擬萬有引力和擬庫侖力影響項(xiàng)加入基本粒子群算法中后，網(wǎng)絡(luò)冗余覆蓋可以減少，收斂速度也加快，有效覆蓋率增加，算法如下。

第一步，初始化，設(shè)置好監(jiān)控區(qū)域，算法中各參數(shù)進(jìn)行初始，在監(jiān)控區(qū)域邊界內(nèi)隨機(jī)產(chǎn)生N個粒子的初始位置xid、初始速度vid，計(jì)算覆蓋率初始值。

第二步，按照（1）式基于本粒子群算法迭代更新粒子的速度和位置并計(jì)算蓋率。

第三步，將更新后的粒子位置覆蓋率與個體最優(yōu)位置的覆蓋率進(jìn)行比較，更新粒子個體最優(yōu)位置和最優(yōu)覆蓋率。

第四步，比較各個粒子個體最位置的覆蓋率大小，設(shè)置全局最優(yōu)位置值和全局最優(yōu)覆蓋率。

第五步，計(jì)算判斷覆蓋率變化率是否為“零”，若是則按式（5）“擬物力”一次。

第六步，判斷滿足結(jié)束條件終止迭代輸出結(jié)果，否則返回從第二步繼續(xù)進(jìn)行迭代更新計(jì)算。

3 算法仿真

該文監(jiān)控區(qū)域設(shè)置為邊長100 m 正方形，節(jié)點(diǎn)數(shù)為45 個，節(jié)點(diǎn)感知半徑為10 m，仿真是利用MATLAB平臺工具，結(jié)果與標(biāo)準(zhǔn)粒子群算法進(jìn)行了比較。仿真參數(shù)具體見表1。

表1 算法仿真參數(shù)

優(yōu)化算法仿真運(yùn)行結(jié)果見圖2～圖4，“*”號表示傳感器節(jié)點(diǎn)中心所在位置，圓來表示傳感器節(jié)點(diǎn)在監(jiān)測區(qū)域夠中覆蓋的范圍。初始傳感器節(jié)點(diǎn)覆蓋情況見圖2，運(yùn)行基本粒子群算法后傳感節(jié)點(diǎn)覆蓋情況見圖3，基于擬物力粒子群結(jié)合擬物力算法傳感器節(jié)點(diǎn)覆蓋情況見圖4。初始在監(jiān)測區(qū)域內(nèi)隨機(jī)撒布45個無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，分別用基本粒子群算法和結(jié)合擬物力算法后的基本粒子群算法對傳感器節(jié)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)覆蓋優(yōu)化[8]。對比與分析3張傳感節(jié)點(diǎn)覆蓋圖，可以看出，相同初始條件下，基本粒子群算法加入擬物力算法后，粒子位置分布相對均勻些，在監(jiān)測區(qū)域范圍內(nèi)覆蓋情況得到一定程度上的改善。而僅僅是基本粒子群算法，則是粒子分布不均勻存在很多重疊覆蓋區(qū)域和大量的未覆蓋區(qū)；從兩種粒子算法覆蓋變化曲線圖（見圖5）可以明顯看出，基本粒子群算法加入擬物力項(xiàng)式改進(jìn)后的區(qū)域覆蓋程度相比基本粒子群算法改善近10%。

圖2 傳感器節(jié)點(diǎn)分布初始覆蓋情況

圖3 基本粒子群算法后節(jié)點(diǎn)分布覆蓋情況

圖4 基本粒子群結(jié)合擬物力算法后覆蓋情況

圖5 兩種粒子算法覆蓋變化曲線

圖3和圖4是兩種粒子算法迭代1 000次后的仿真結(jié)果圖，圖5 是兩種算法后傳感器節(jié)點(diǎn)覆蓋率變化曲線圖。仿真曲線趨勢表明，基本粒子群算法在經(jīng)198次迭代后就趨于收斂了，覆蓋率為81.32%。然而，加上擬物力影響項(xiàng)的粒子群算法，由于有擬萬有引力和擬庫倫力的作用使得節(jié)點(diǎn)根據(jù)距離相互排擠或吸引。在迭代220次后，節(jié)點(diǎn)覆蓋突破92%，在迭代600次后，達(dá)到了94%的覆蓋程度。

在仿真參數(shù)相同的情況下，仿真數(shù)據(jù)結(jié)果表明，基于擬物力的粒子群算法相比基于粒子群算法，對監(jiān)測區(qū)域無線傳感網(wǎng)絡(luò)優(yōu)化具有覆蓋面積更大，覆蓋效果更好的優(yōu)勢。

4 結(jié)語

該文探討了無線傳感網(wǎng)絡(luò)的覆蓋增強(qiáng)優(yōu)化方法，對粒子群優(yōu)化算法進(jìn)行了研究并提出了改進(jìn)方法。將擬物力算法作為多項(xiàng)式的一項(xiàng)加入基本粒子群算法中影響算法搜索。迭代過程中，在基本粒子群算法進(jìn)入局部收斂覆蓋率不變時啟動擬物力算法加入。仿真結(jié)果充分說明對基本粒子群算法加入擬物力算法改進(jìn)后相比基本粒子算法，有效覆蓋率更高，避免算法早熟陷入局部最優(yōu)的問題也有所改善，無線傳感器網(wǎng)絡(luò)部署的有效性也提高了。