基于虛擬力算法的無線傳感器網絡節點部署方案

劉 琛

（江蘇警官學院，江蘇 南京 210031）

0 引 言

無線傳感器網絡[1-3]（Wireless Sensor Network, WSN）是一種由大量傳感器節點以自組織和多跳方式構成的無線網絡。由于無需固定的通信設施，無線傳感器網絡靈活性高，在氣象監測、搶險救災、目標跟蹤等領域具有重要的應用價值[4-6]。

網絡監測質量很大程度上取決于傳感器節點的部署[7-9]。一個良好的節點部署方案可以減少網絡形成的時間，提高目標區域的覆蓋率，并延長網絡生存時間。按照傳感器節點是否可以移動，無線傳感器網絡節點部署方案可以分為靜態部署和動態部署兩類。其中，靜態部署又包括確定性部署和隨機性部署。確定性部署通常應用于環境已知、比較安全或網絡狀態相對穩定的區域，部署規模一般較小。而隨機部署常應用于環境惡劣或人工無法到達的監控環境中，如戰爭、洪水、森林火險等災害監測，部署規模較大。考慮到成本及網絡通信等因素，動態部署通過對移動節點位置實施優化，能夠在有限的節點數量下實現較高的網絡覆蓋率，具有十分重要的理論意義與實用價值。本文提出了一種基于虛擬力算法的無線傳感器網絡動態部署方案，該方案采用布爾探測模型，考慮2種典型的虛擬力，并根據節點密度預先調整距離閾值。仿真實驗表明，與隨機部署相比，本方案可以有效提高監測區域的覆蓋率，減少覆蓋空洞與覆蓋冗余，具有良好的部署性能。

1 基于虛擬力算法的節點部署方案

虛擬力算法將傳感器節點看成電勢場中的粒子，節點與節點、節點與覆蓋區域之間存在虛擬的電場力作用，受力方向由預先設置的距離閾值決定。傳感器節點在虛擬力的作用下不斷調整位置信息，直到滿足網絡覆蓋率的要求。文獻[10]中的虛擬力模型考慮了3種虛擬力，分別是覆蓋區域與節點的吸引力、節點與節點的吸引力以及節點與節點之間的排斥力。由于節點之間既包含吸引力又包含排斥力，因此該算法容易產生局部節點過于密集的問題。為解決上述問題，本文只考慮被監測區域對節點的吸引力以及節點之間的排斥力。首先，當被監測區域未被節點覆蓋時，區域對臨近節點的吸引力占主導作用，使節點盡快向未被覆蓋的區域移動，減少覆蓋空洞。其次，對于已被多個臨近節點同時覆蓋的區域，節點間的排斥力占主導作用，通過移動距離過近的節點來減少覆蓋冗余。

1.1 布爾感知模型

本文選用布爾感知模型實現相關功能，即傳感器節點以自身坐標為圓心，以感知半徑為半徑構成其感知范圍。感知范圍內的區域認為被有效覆蓋，感知范圍外的區域認為未被覆蓋。被監測區域的覆蓋率可以表示為傳感器節點已覆蓋區域的面積As與監測區域總面積A的比值，定義為q=As/A。

1.2 虛擬力模型

被監測區域未被節點覆蓋時，區域對臨近節點的吸引力占主導作用。這一虛擬力使節點盡快向未被覆蓋的區域移動，從而減少覆蓋空洞。被監測區域對傳感器節點的吸引力可以由公式（1）表示：

式中：ωa為吸引力系數，表征被監測區域的重要程度，對于處處均勻的被監測區域，ωa為常數；dki為被監測區域標識點K(xk, yk)與節點Si(xsi, ysi)的距離；Rc與Rs分別為傳感器節點的通信半徑與感知半徑。根據連通性原理，通信半徑與感知半徑滿足Rc≥2Rs。Rs＜dki表示被監測區域標識點處于節點Si的感知范圍外，此時需要移動節點實現覆蓋。dki≤Rc表示對于被監測區域標識點而言，只有處于通信半徑范圍內的傳感器節點才會受到標識點的吸引力。這樣的設定可以保證被監測區域總是優先考慮臨近傳感器節點的覆蓋，避免傳感器節點長距離移動。

對于已被多個臨近節點同時覆蓋的區域，節點間的排斥力占主導作用。此作用力通過移動距離過近的節點來減少覆蓋冗余。傳感器節點間的排斥力可以由公式（2）表示：

式中：ωR是排斥力系數，表征節點間排斥的程度；dij為節點Si(xsi, ysi)與節點Sj(xsj, ysj)的距離；dth為預先設定的距離閾值。僅當dij＜dth時，節點Si與節點Sj的感知范圍發生重疊，節點間存在排斥力。可以看出，dij決定了節點的聚集程度。相關研究表明[11-12]，dth合適的取值范圍為1.7Rs≤dth≤2Rs。

1.3 節點移動位置的計算

節點位置的更新由每一步節點所受虛擬力作用計算得到，可以用公式（3）表示：

式中：Fi是傳感器節點Si受到的合力；Fx，Fy是合力分解在x軸和y軸上的分力；(xold, yold)是傳感器節點的原坐標；(xnew,ynew)是傳感器節點的新坐標；dmax是傳感器單次移動的最大距離。

1.4 算法流程

第一步：給定被監測區域范圍、節點信息參數以及預期覆蓋率指標，初始化模擬環境；

第二步：計算被監測區域的覆蓋率，判斷是否達到預期指標，未達標轉第三步，否則轉第五步；

第三步：由公式（1）和公式（2）計算節點所受虛擬力的大小及方向，根據公式（3）計算節點移動位置，并更新節點坐標；

第四步：判斷算法是否達到設定的循環次數，若達到轉第五步，否則轉第三步；

第五步：將節點移動到最終位置并輸出結果。

2 仿真結果與討論

在MATLAB R2014平臺上對算法進行仿真實驗。被監測區域為100×100，傳感器節點數量N為40，節點感知半徑Rs為10，通信半徑Rc為20，節點單次最大移動步長dmax為0.1，算法迭代次數為100次，節點排斥距離閾值為dth=1.7Rs。

如圖1所示，節點首先采用隨機拋灑方式部署。圖中圓點為傳感器節點位置，數字為節點序號，藍色圓形區域為傳感器節點的感知范圍，初始覆蓋率為70%。

圖1 節點初始分布情況

經過算法100次迭代之后，圖2給出了調整后的傳感器節點在被監測區域的位置分布情況。可以看到，節點已基本覆蓋被監測區域，此時覆蓋率為91%。

圖2 算法運行后節點分布情況

在監測區域和節點感知半徑不變的情況下，本文研究了覆蓋率隨節點個數的變化情況。如圖3所示，隨著節點個數的增多，覆蓋率呈現同步增大趨勢。當節點個數超過30之后，覆蓋率增幅開始降低。這是由于理論上需要N=A/(πRs2)個節點即可實現覆蓋，按照本文采用的參數A=100×100，Rs=10，對應的數值約為32。因此，節點個數小于32時，節點間的重疊部分較小，單位節點覆蓋效率較高。當節點個數超過32時，節點間重疊部分逐漸增多，單位節點覆蓋效率降低，導致總覆蓋率增幅下降。

圖3 覆蓋率與節點個數的關系

3 結 語

本文針對無線傳感器網絡節點部署問題，以虛擬力算法思想為基礎，提出一種基于虛擬力算法的部署方案。本方案相比于隨機部署，可以有效提高覆蓋率，減少覆蓋盲區與覆蓋冗余。