無線傳感網絡覆蓋優化技術研究

張江山 熊哲源

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

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

該文對多媒體傳感網絡的有向傳感器感知方向控制方法進行了深入研究探討，在節點之間假設存在萬有引力和排斥庫倫力叫作擬物力，提出一種改進的粒子群算法。基于粒子群算法加上擬物力的算法對傳感網的有向傳感器感知方向和位置進行計算控制，能有效地提高無線傳感網絡覆蓋率。

1 覆蓋優化流程

1.1 網絡覆蓋定義

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

其中，Si、S、N分別表示一只傳感器節點覆蓋面積、監測區域總面積、網絡中傳感器節點數量。P的取值為[0，1]。

1.2 覆蓋增強優化流程

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

圖1 覆蓋增強流程圖

2 粒子群算法優化

2.1 PSO算法優化

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

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

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

2.2 POS優化算法不足

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

2.3 擬物力算法

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

2.3.1 擬萬有引力

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

2.3.2 擬庫侖力

節點的圓盤會產生交疊覆蓋情況，要增強網絡覆蓋就應盡量減少節點圓盤交。擬庫侖力就是如果兩個圓盤之間的距離小于圓盤距離閾值就會相互之間有排斥力，每個節點圓盤排斥與自己距離過近的其他圓盤，以便減少交叉覆蓋。根據庫侖力定理，無線傳感網絡節點圓盤間的斥力勢表達式為

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

2.4 算法的覆蓋優化方案設計

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

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

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

第一步，初始化，設置好監控區域，算法中各參數進行初始，在監控區域邊界內隨機產生N個粒子的初始位置xid、初始速度vid，計算覆蓋率初始值。

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

第三步，將更新后的粒子位置覆蓋率與個體最優位置的覆蓋率進行比較，更新粒子個體最優位置和最優覆蓋率。

第四步，比較各個粒子個體最位置的覆蓋率大小，設置全局最優位置值和全局最優覆蓋率。

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

第六步，判斷滿足結束條件終止迭代輸出結果，否則返回從第二步繼續進行迭代更新計算。

3 算法仿真

該文監控區域設置為邊長100 m 正方形，節點數為45 個，節點感知半徑為10 m，仿真是利用MATLAB平臺工具，結果與標準粒子群算法進行了比較。仿真參數具體見表1。

表1 算法仿真參數

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

圖2 傳感器節點分布初始覆蓋情況

圖3 基本粒子群算法后節點分布覆蓋情況

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

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

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

在仿真參數相同的情況下，仿真數據結果表明，基于擬物力的粒子群算法相比基于粒子群算法，對監測區域無線傳感網絡優化具有覆蓋面積更大，覆蓋效果更好的優勢。

4 結語

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