無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化技術(shù)研究

張江山 熊哲源

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

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

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

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

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

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

其中，Si、S、N分別表示一只傳感器節(jié)點(diǎn)覆蓋面積、監(jiān)測(cè)區(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 個(gè)階段：網(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)啟動(dòng)整個(gè)網(wǎng)絡(luò)的工作初始化節(jié)點(diǎn)位置、感知半徑、感知方向等。利用優(yōu)先遍歷算法根據(jù)節(jié)點(diǎn)的感知半徑和位置信息將整個(gè)無(wú)線網(wǎng)絡(luò)劃分成若干個(gè)連通子圖，運(yùn)用改進(jìn)式粒子群優(yōu)化算法對(duì)傳感連通子網(wǎng)的各個(gè)有向傳感器感知方向進(jìn)行最優(yōu)計(jì)算，算出各傳感節(jié)點(diǎn)的最佳感知方向，各子網(wǎng)的匯聚節(jié)點(diǎn)通過(guò)多跳無(wú)線通信方式將感知方向值派發(fā)到各自的節(jié)點(diǎn)，網(wǎng)絡(luò)中各節(jié)點(diǎn)根據(jù)接收的計(jì)算結(jié)果自發(fā)調(diào)整感知方向，從而實(shí)現(xiàn)了整個(gè)網(wǎng)絡(luò)覆蓋增強(qiáng)。

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

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

2.1 PSO算法優(yōu)化

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

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

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

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

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

2.3 擬物力算法

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

2.3.1 擬萬(wàn)有引力

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

2.3.2 擬庫(kù)侖力

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

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真

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

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

優(yōu)化算法仿真運(yùn)行結(jié)果見(jiàn)圖2～圖4，“*”號(hào)表示傳感器節(jié)點(diǎn)中心所在位置，圓來(lái)表示傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域夠中覆蓋的范圍。初始傳感器節(jié)點(diǎn)覆蓋情況見(jiàn)圖2，運(yùn)行基本粒子群算法后傳感節(jié)點(diǎn)覆蓋情況見(jiàn)圖3，基于擬物力粒子群結(jié)合擬物力算法傳感器節(jié)點(diǎn)覆蓋情況見(jiàn)圖4。初始在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)撒布45個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，分別用基本粒子群算法和結(jié)合擬物力算法后的基本粒子群算法對(duì)傳感器節(jié)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)覆蓋優(yōu)化[8]。對(duì)比與分析3張傳感節(jié)點(diǎn)覆蓋圖，可以看出，相同初始條件下，基本粒子群算法加入擬物力算法后，粒子位置分布相對(duì)均勻些，在監(jiān)測(cè)區(qū)域范圍內(nèi)覆蓋情況得到一定程度上的改善。而僅僅是基本粒子群算法，則是粒子分布不均勻存在很多重疊覆蓋區(qū)域和大量的未覆蓋區(qū)；從兩種粒子算法覆蓋變化曲線圖（見(jiàn)圖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)覆蓋率變化曲線圖。仿真曲線趨勢(shì)表明，基本粒子群算法在經(jīng)198次迭代后就趨于收斂了，覆蓋率為81.32%。然而，加上擬物力影響項(xiàng)的粒子群算法，由于有擬萬(wàn)有引力和擬庫(kù)倫力的作用使得節(jié)點(diǎn)根據(jù)距離相互排擠或吸引。在迭代220次后，節(jié)點(diǎn)覆蓋突破92%，在迭代600次后，達(dá)到了94%的覆蓋程度。

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

4 結(jié)語(yǔ)

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