關(guān)志艷，耿 巖

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

0 引 言

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

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

1 問(wèn)題與假設(shè)

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

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

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

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

圖1 三角點(diǎn)陣分布Fig 1 Triangular lattice distribution

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

2.1 虛擬力算法基本原理

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

1)移動(dòng)節(jié)點(diǎn)受到周圍節(jié)點(diǎn)的引力、斥力

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

2)移動(dòng)節(jié)點(diǎn)受到熱點(diǎn)區(qū)域的引力

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

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

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

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

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

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

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

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

3 算法仿真與性能分析

假設(shè)在邊長(zhǎng)為50 m 的正方形監(jiān)測(cè)區(qū)域內(nèi)布置兩種傳感器節(jié)點(diǎn)，一種固定骨干節(jié)點(diǎn)，數(shù)量為16 個(gè)，組成骨干轉(zhuǎn)發(fā)網(wǎng)，連通涵蓋覆蓋;一種是普通節(jié)點(diǎn)rs=4，據(jù)文獻(xiàn)［8］三角點(diǎn)陣分布下達(dá)到理想無(wú)縫覆蓋所需節(jié)點(diǎn)最少數(shù)量為n=60，實(shí)驗(yàn)初始60 個(gè)普通節(jié)點(diǎn)隨機(jī)分布，節(jié)點(diǎn)分別在虛擬力算法、群聚智能算法及虛擬力導(dǎo)向群聚智能優(yōu)化策略的作用下，進(jìn)行位置更新。虛擬力算法的參數(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é)點(diǎn)，三種算法分別作用于每個(gè)節(jié)點(diǎn)上，因此將每個(gè)節(jié)點(diǎn)上相關(guān)的二項(xiàng)式運(yùn)算轉(zhuǎn)換為矩陣來(lái)表達(dá)。如圖3 所示，圖3(a)為60 個(gè)節(jié)點(diǎn)隨機(jī)分布圖，圖3(b)為在虛擬力算法作用后節(jié)點(diǎn)分布情況，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)固定節(jié)點(diǎn)對(duì)普通節(jié)點(diǎn)的熱點(diǎn)引力限制了節(jié)點(diǎn)的移動(dòng)，使節(jié)點(diǎn)出現(xiàn)局部堆積的現(xiàn)象，在這部分實(shí)驗(yàn)中削減了熱點(diǎn)引力系數(shù)，緩解了局部節(jié)點(diǎn)堆積，網(wǎng)絡(luò)的平均有效覆蓋率達(dá)到80.12%。圖3(c)為節(jié)點(diǎn)經(jīng)過(guò)群聚智能算法后節(jié)點(diǎn)的分布效果，全局優(yōu)化效果不明顯，網(wǎng)絡(luò)的平均覆蓋度達(dá)到83.62%。圖3(d)為節(jié)點(diǎn)經(jīng)過(guò)虛擬力導(dǎo)向群聚智能優(yōu)化后的分布效果，區(qū)域的覆蓋盲區(qū)范圍減少，說(shuō)明兩種算法結(jié)合對(duì)網(wǎng)絡(luò)均勻覆蓋起到有效的作用，網(wǎng)絡(luò)覆蓋率達(dá)到89.33%。

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

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

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

4 結(jié)束語(yǔ)

虛擬力導(dǎo)向群聚智能優(yōu)化的傳感網(wǎng)絡(luò)覆蓋策略在原群聚智能算法位置進(jìn)化公式中加入虛擬力影響因子，來(lái)提高網(wǎng)絡(luò)覆蓋率并加快算法收斂。通過(guò)大量實(shí)驗(yàn)驗(yàn)證，在隨機(jī)部署節(jié)點(diǎn)后分別應(yīng)用三種算法，結(jié)果表明:虛擬力導(dǎo)向群聚智能優(yōu)化策略的網(wǎng)絡(luò)覆蓋率最高，且收斂也最快。但是由于本實(shí)驗(yàn)環(huán)境部署的節(jié)點(diǎn)數(shù)量是理想狀態(tài)下所需最少節(jié)點(diǎn)，在網(wǎng)絡(luò)覆蓋率方面沒(méi)有達(dá)到很高，且節(jié)點(diǎn)初始部署情況和公式應(yīng)用中參數(shù)的設(shè)置對(duì)實(shí)驗(yàn)結(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］ 田一鳴，陸 陽(yáng)，魏 臻，等.無(wú)線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制及節(jié)能優(yōu)化研究［J］.電子測(cè)量與儀器學(xué)報(bào)，2009，23(11):65－71.

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

［7］ 關(guān)志艷，馮秀芳.基于虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法［J］.計(jì)算機(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)移動(dòng)網(wǎng)絡(luò)覆蓋策略［J］.儀器儀表學(xué)報(bào)，2011，32(5):1043－1049.