虛擬力導(dǎo)向群聚智能優(yōu)化的無線傳感器網(wǎng)絡(luò)覆蓋策略*

關(guān)志艷，耿 巖

(山西大學(xué) 商務(wù)學(xué)院 信息學(xué)院，山西 太原030001)

0 引 言

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

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

1 問題與假設(shè)

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

無線傳感器網(wǎng)絡(luò)覆蓋研究中，最重要的一個評價覆蓋的標(biāo)準是網(wǎng)絡(luò)覆蓋率，但目前大部分文獻研究的都是整個區(qū)域的網(wǎng)絡(luò)覆蓋率，而不是單個節(jié)點的有效覆蓋率。本文討論了針對節(jié)點的有效覆蓋率的計算。

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

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

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

2 虛擬力導(dǎo)向群聚智能優(yōu)化策略基本原理

2.1 虛擬力算法基本原理

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

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

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

2)移動節(jié)點受到熱點區(qū)域的引力

設(shè)骨干節(jié)點對普通節(jié)點的引力等效于來自熱點區(qū)域Hotpotw 引力作用，則引力可表示成

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

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

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

2.2 虛擬力導(dǎo)向群聚智能優(yōu)化過程

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

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

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

3 算法仿真與性能分析

假設(shè)在邊長為50 m 的正方形監(jiān)測區(qū)域內(nèi)布置兩種傳感器節(jié)點，一種固定骨干節(jié)點，數(shù)量為16 個，組成骨干轉(zhuǎn)發(fā)網(wǎng)，連通涵蓋覆蓋;一種是普通節(jié)點rs=4，據(jù)文獻［8］三角點陣分布下達到理想無縫覆蓋所需節(jié)點最少數(shù)量為n=60，實驗初始60 個普通節(jié)點隨機分布，節(jié)點分別在虛擬力算法、群聚智能算法及虛擬力導(dǎo)向群聚智能優(yōu)化策略的作用下，進行位置更新。虛擬力算法的參數(shù)為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。群聚智能算法的參數(shù)為c1=c2=c3=1，max Number=100，微粒的速度區(qū)間［vminvmax］=k［xminxmax］=0.2×［0 50］=［0 10］。

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

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

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

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

4 結(jié)束語

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

［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］ 田一鳴，陸 陽，魏 臻，等.無線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制及節(jié)能優(yōu)化研究［J］.電子測量與儀器學(xué)報，2009，23(11):65－71.

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

［7］ 關(guān)志艷，馮秀芳.基于虛擬力的異構(gòu)節(jié)點網(wǎng)絡(luò)覆蓋增強算法［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］ 李 明，石為人.虛擬力導(dǎo)向查分算法的異構(gòu)移動網(wǎng)絡(luò)覆蓋策略［J］.儀器儀表學(xué)報，2011，32(5):1043－1049.