虛擬力導向群聚智能優化的無線傳感器網絡覆蓋策略*

關志艷，耿 巖

(山西大學 商務學院 信息學院，山西 太原030001)

0 引 言

覆蓋是網絡獲取物理環境信息的能力，為了有效獲取整個任務區域信息，所有節點應能夠覆蓋整個任務區域［1］。文獻［2］使用Delaunay 三角化和Voronoi 圖來決定最佳性能覆蓋和最壞性能覆蓋，文獻［3］提出了三種算法來定位移動節點，通過移動節點來填補覆蓋漏洞。Zou Yi等人［4］提出了一種虛擬力算法，初始節點隨機部署后，利用虛擬人工勢場產生的作用力尋求節點的受力平衡來自動完善網絡覆蓋性能，該算法近年來得到廣泛關注。文獻［5］提出了一種基于節能的虛擬力算法，建立了一個多目標非線性規劃模型來改善節點分布。以上基于虛擬力算法的移動無線傳感器網絡(WSNs)的覆蓋方案大多是在基于同構節點的基礎上，若在既有固定節點又有移動節點的網絡中，固定節點對移動節點的虛擬力可能會限制無線傳感器網絡的全局優化。

針對以上研究的不足，本文結合虛擬力算法和群聚智能思想，提出了一種虛擬力導向群聚智能優化的異構移動網絡覆蓋策略。把調整后距離閾值的虛擬力作用于群聚智能算法的速度和位置的更新過程中，使微粒向擴大覆蓋率和目標檢測率的方向進化，仿真實驗表明:虛擬力導向群聚智能策略能有效地實現異構無線傳感器網絡節點布局優化，提高網絡覆蓋率，且收斂速度快。

1 問題與假設

假設檢測區域A 為二維平面，有兩種不同類型的傳感器節點，一類稱為普通節點，一類稱為骨干節點。普通節點攜帶能量少，計算能量和存儲空間有限，主要任務是感知、轉發數據，感知半徑為rs，位置坐標為(x，y)，根據算法移動位置坐標。骨干節點能量不受限制，通信能力強，位置坐標固定，構成一個可靠的轉發骨干網。而普通節點則通過多跳路由與骨干網相連，從而簡化本模型中關于連通的問題，即區域A 中任一節點都至少有一條轉發連通路徑，全網連通。所有節點可通過GPS 或某些定位算法準確獲得自身位置信息。移動節點根據本文算法能準確完成位置遷移，但移動距離不超過傳感器節點最大移動距離。

無線傳感器網絡覆蓋研究中，最重要的一個評價覆蓋的標準是網絡覆蓋率，但目前大部分文獻研究的都是整個區域的網絡覆蓋率，而不是單個節點的有效覆蓋率。本文討論了針對節點的有效覆蓋率的計算。

定理1 在三角點陣的節點排列中，節點的有效覆蓋率最大，為82.7%。

三角點陣分布是獲取節點數量最優的部署方式［6］，分布中任意兩個直接相鄰位置點的距離滿足，如圖1 所示，圖中節點Si，其有效覆蓋率為Ci=Di/Ai，Di為節點Si的非重疊面積，Ai為節點Si的感知圓形面積，在三角點陣分布中，節點的有效覆蓋率是最大的

圖1 三角點陣分布Fig 1 Triangular lattice distribution

2 虛擬力導向群聚智能優化策略基本原理

2.1 虛擬力算法基本原理

虛擬力算法假設傳感器節點、障礙物和熱點區域均可對傳感器節點施加引力或斥力。在無線移動網絡中，各節點根據其所受合力的大小和方向移動，多次循環達到布局優化。因為本文研究環境是由骨干節點與普通節點組成的移動傳感器網絡，虛擬力主要是骨干節點對普通節點的熱點引力和普通節點間的引斥力，先分析其受力公式如下:

1)移動節點受到周圍節點的引力、斥力

其中，k1，k2分別為虛擬力的引力系數和斥力系數，m為節點質量，dij為節點間距離，dth為調整傳感節點間作用力的距離閾值，文獻［7］通過分析節點最佳布局情況下，dth=，本文也采用此距離閾值，γ1，γ2為引力增益系數和斥力增益系數，αij為兩個節點間的方位角。

2)移動節點受到熱點區域的引力

設骨干節點對普通節點的引力等效于來自熱點區域Hotpotw 引力作用，則引力可表示成

其中，k3為節點受到熱點區域的引力系數，dihot為節點與熱點區域中心的距離，γ3為增益系數。一個節點所受力既有來自鄰居節點的引斥力，也有來自熱點骨干節點的引力，最終受力是所有在其作用力的合力

完成虛擬力分析后，設定受力閾值，各節點將原位置更新為新位置，文獻［8］詳細討論了坐標更新計算方法。但值得注意的是，節點通過虛擬力移動位置，移動之后的疏密程度dth起了很大的作用，實際要找到最合適的dth，需要在實驗中不斷測試靠經驗取值。如圖2 所示，在50 m×50 m 的監測區域內，部署rs=5 的節點，部署60 個rs=5 的普通節點，16 個固定位置的骨干節點，骨干節點均勻分布，采用虛擬力算法進行普通節點適度移動，經過40 次循環后的結果如圖2(b)所示，由于骨干節點對普通節點的引力，節點主要分布于固定節點附近或朝著節點密集的區域集中，這樣無法實現全局優化。

圖2 虛擬力作用前后對比圖Fig 2 Comparison diagram before and after VFA

2.2 虛擬力導向群聚智能優化過程

群聚智能的研究始于意大利學者Dorigo 開發的蟻群算法。Kenmedy J 等人［8］通過觀察鳥群的協作覓食，開發出粒子群算法。就優化而言，群聚智能已包括蟻群優化(ACO)算法和粒子群優化(PSO)算法。本文側重于應用PSO，將每個傳感器節點看做空間中的一個沒有質量的微粒，在搜索空間中以一定的速度飛行，這個速度依據其本身和同伴的飛行經驗進行動態調整。文獻［9］詳細討論了群聚智能算法中，節點微粒的最佳位置與速度，取決于節點初始隨機產生的位置與速度和進化公式。由于虛擬力算法能有效指導移動節點的分布過程，群聚智能優化策略又有很強的全局優化能力，因此，本文在群聚智能算法的進化公式中加入虛擬力的影響，其進化公式如下

其中，粒子群規模為m，vij(t)為第t 代微粒i 在第j 維的速度，w(t)為慣性權重，c1，c2為加速常數，c3為用來調節虛擬力影響的加速因子，rand()，Rand()，fj(t)為3 個在［0，1］范圍內變化的隨機函數，隨迭代次數增加應逐漸減小，pi為微粒i 經歷的最佳位置，Pg為群體中所有微粒經歷的最佳位置的索引號，w(t)的計算公式為

其中，max Number 為截止代數，t 為迭代次數。由于本文是在二維空間的基礎上進行研究，當j=1 即表示橫向，j=2 即表示縱向，節點微粒i 的第j 維元素在虛擬力作用下的距離Vij(t)為其中，max Step 為傳感器節點最大移動距離，為作用在節點微粒i 上的虛擬力節點微粒i 在x 軸、y 軸上的虛擬力分量，Fth為虛擬力閾值。

3 算法仿真與性能分析

假設在邊長為50 m 的正方形監測區域內布置兩種傳感器節點，一種固定骨干節點，數量為16 個，組成骨干轉發網，連通涵蓋覆蓋;一種是普通節點rs=4，據文獻［8］三角點陣分布下達到理想無縫覆蓋所需節點最少數量為n=60，實驗初始60 個普通節點隨機分布，節點分別在虛擬力算法、群聚智能算法及虛擬力導向群聚智能優化策略的作用下，進行位置更新。虛擬力算法的參數為k1=1，k2=10，k3=2，γ1=－1，γ2=γ3=1，m=1 kg，L=4 m，dth=7.46 m，max Step=4 m。群聚智能算法的參數為c1=c2=c3=1，max Number=100，微粒的速度區間［vminvmax］=k［xminxmax］=0.2×［0 50］=［0 10］。

本文所討論的三種算法，由于涉及大量節點，三種算法分別作用于每個節點上，因此將每個節點上相關的二項式運算轉換為矩陣來表達。如圖3 所示，圖3(a)為60 個節點隨機分布圖，圖3(b)為在虛擬力算法作用后節點分布情況，通過實驗發現固定節點對普通節點的熱點引力限制了節點的移動，使節點出現局部堆積的現象，在這部分實驗中削減了熱點引力系數，緩解了局部節點堆積，網絡的平均有效覆蓋率達到80.12%。圖3(c)為節點經過群聚智能算法后節點的分布效果，全局優化效果不明顯，網絡的平均覆蓋度達到83.62%。圖3(d)為節點經過虛擬力導向群聚智能優化后的分布效果，區域的覆蓋盲區范圍減少，說明兩種算法結合對網絡均勻覆蓋起到有效的作用，網絡覆蓋率達到89.33%。

圖3 三種算法分布對比圖Fig 3 Distribution comparison of three algorithms

若從節點的平均移動距離來分析算法的收斂速度，當經過多次循環后節點的平均移動距離趨于0，就說明節點的移動已非常小，算法達到收斂。如圖4 所示，經過實驗比較，其中虛擬力導向群聚智能優化策略收斂速度最快，當循環迭代約至15 代時節點平均移動距離已穩定，而群聚智能算法需要迭代至30 代左右節點分布穩定，虛擬力算法循環至40 次左右節點分布穩定，所以，虛擬力導向群聚智能優化策略收斂性最好。

圖4 算法收斂性比較Fig 4 Comparison of convergence of algorithm

4 結束語

虛擬力導向群聚智能優化的傳感網絡覆蓋策略在原群聚智能算法位置進化公式中加入虛擬力影響因子，來提高網絡覆蓋率并加快算法收斂。通過大量實驗驗證，在隨機部署節點后分別應用三種算法，結果表明:虛擬力導向群聚智能優化策略的網絡覆蓋率最高，且收斂也最快。但是由于本實驗環境部署的節點數量是理想狀態下所需最少節點，在網絡覆蓋率方面沒有達到很高，且節點初始部署情況和公式應用中參數的設置對實驗結果都有一定的影響。

［1］ Kumar S，Lai T H，Arora A.Barrier coverage with wireless sensor［C］∥Proceedings of the 11th Annual International Conference on Mobile Computing and Networking，New York:ACM，2005:284－298.

［2］ Meguerdichian S，Koushanfar F，Potkonjak E，et al.Coverage problem in wireless Ad Hoc sensor networks［C］∥Proceedings of the 20th Annual Joint Conference of the IEEE Communications Societies，New York:IEEE，2001:1380－1387.

［3］ Wang G L，Gao G H，Porta F L.Movement－assisted sensor deployment［J］.IEEE Transations on Mobile Computing，2006，5(6):640－652.

［4］ Zou Yi，Chakrabarty K.Sensor deployment and target localization in distributed sensor networks［J］.ACM Trans on Embedded Computing Systems，2004，3(1):6191.

［5］ 田一鳴，陸 陽，魏 臻，等.無線傳感器網絡虛擬力覆蓋控制及節能優化研究［J］.電子測量與儀器學報，2009，23(11):65－71.

［6］ 劉麗萍，王 智，孫優賢.無線傳感器網絡部署及其覆蓋問題研究［J］.信息學報，2006，28(9):17521757.

［7］ 關志艷，馮秀芳.基于虛擬力的異構節點網絡覆蓋增強算法［J］.計算機工程，2009，5(5):103－107.

［8］ Kennedy J，Eberhart R.Particle swarm optization［C］∥Proc of IEEE Int’l Conf on Neural Networks，Perth，1995:1942－1948.

［9］ 李 明，石為人.虛擬力導向查分算法的異構移動網絡覆蓋策略［J］.儀器儀表學報，2011，32(5):1043－1049.