王昌征　毛劍琳　付麗霞　郭寧　曲蔚賢

摘要：

針對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)隨機(jī)部署節(jié)點(diǎn)產(chǎn)生的覆蓋重疊區(qū)和盲區(qū)的問題，提出了一種基于粒子群優(yōu)化（PSO）算法面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法（PSOTDH）。該算法在建立新的三維有向感知模型的基礎(chǔ)上，在模型中引入三維重疊質(zhì)心、三維有效質(zhì)心和三維邊界質(zhì)心的概念，通過PSO算法對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)進(jìn)行三維覆蓋重疊區(qū)域優(yōu)化和三維邊界節(jié)點(diǎn)優(yōu)化處理，使節(jié)點(diǎn)的主傳感方向發(fā)生改變，從而使三維重疊質(zhì)心、三維有效質(zhì)心和三維邊界質(zhì)心分布更加均勻，進(jìn)而達(dá)到提高覆蓋率的目的。仿真結(jié)果表明，該算法經(jīng)過25次優(yōu)化以后可以提高網(wǎng)絡(luò)覆蓋率約27.82%。由此可見，該算法能夠快速、有效地提高網(wǎng)絡(luò)的覆蓋率。

關(guān)鍵詞：

有向異構(gòu)傳感器網(wǎng)絡(luò)；三維有向感知模型；粒子群優(yōu)化算法；覆蓋優(yōu)化

中圖分類號：

TP393.0；TP391.9

文獻(xiàn)標(biāo)志碼：A

Abstract：

For the problem of coverage overlapping areas and blind spots that nodes deployed randomly in threedimensional directional heterogeneous networks， a Particle Swarm algorithm based coverage Optimization algorithm for ThreeDimensional directional Heterogeneous network （PSOTDH） is introduced in this paper. Through involving the concepts of threedimensional overlapping centroid， threedimensional effective centroid and threedimensional boundary centroid， threedimensional overlap region， threedimensional effective region and threedimensional boundary region are optimized in threedimensional directional heterogeneous networks based on a threedimensional directed perception model and the particle swarm optimization algorithm. The sensing direction of nodes is changed by this algorithm. Thus， the distribution of threedimensional overlapping centroid， threedimensional effective centroid and threedimensional boundary centroid is became more uniform， and the purpose of improving coverage is achieved. Simulation results show that the proposed algorithm can improve coverage rate approximately 27.82% by 25times optimization. Therefore， the proposed algorithm can improve the coverage rate quickly and effectively.

Concerning the coverage overlapping areas and blind spots caused by random deployment of nodes in threedimensional directional heterogeneous network， a Particle Swarm Optimization （PSO） based coverage optimization algorithm for threedimensional directional heterogeneous network， namely PSOTDH， was proposed. Through involving the concepts of threedimensional overlapping centroid， threedimensional effective centroid and threedimensional boundary centroid， threedimensional overlapping area， and threedimensional boundary nodes were optimized in a new threedimensional directed perception model by using PSO. The sensing directions of the nodes were changed by PSOTDH， which made the distribution of threedimensional overlapping centroids， threedimensional effective centroids and threedimensional boundary centroids more uniform， and achieved the purpose of improving coverage. Simulation results show that the proposed algorithm can improve coverage rate by about 27.82% after 25 iterations， which means the proposed algorithm can improve the coverage rate quickly and effectively.

英文關(guān)鍵詞Key words：

directional heterogeneous sensor network； threedimensional directed perception model； Particle Swarm Optimization （PSO） algorithm； coverage optimization

0引言

隨著微電子制造業(yè)技術(shù)的發(fā)展，由大量不同的具有感知能力、計(jì)算能力和通信能力的微型傳感器節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）技術(shù)也迅速發(fā)展[1]。WSN在軍事領(lǐng)域、民用領(lǐng)域的應(yīng)用非常廣泛，比如環(huán)境監(jiān)測、工業(yè)監(jiān)測、戰(zhàn)場監(jiān)測、智能家居和醫(yī)療監(jiān)測等[2-3]。覆蓋問題是所有傳感器網(wǎng)絡(luò)的基本問題，反映出無線傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量[4]，體現(xiàn)了無線傳感器網(wǎng)絡(luò)的性能。在工作環(huán)境比較復(fù)雜的區(qū)域，無線傳感器網(wǎng)絡(luò)大多采用隨機(jī)部署傳感器節(jié)點(diǎn)的方式進(jìn)行網(wǎng)絡(luò)的初始部署，這樣就會產(chǎn)生大量的節(jié)點(diǎn)覆蓋重疊區(qū)域和盲區(qū)，導(dǎo)致網(wǎng)絡(luò)的覆蓋率偏低。此外，由于傳感器節(jié)點(diǎn)的體積較小、電池不易更換等特點(diǎn)，導(dǎo)致傳感器節(jié)點(diǎn)的能量非常有限[5]。因此，如何通過提高網(wǎng)絡(luò)的覆蓋率來提高節(jié)點(diǎn)能量的利用率就顯得尤為重要。

異構(gòu)傳感器網(wǎng)絡(luò)的異構(gòu)性分為節(jié)點(diǎn)異構(gòu)、鏈路異構(gòu)和網(wǎng)絡(luò)協(xié)議異構(gòu)三個(gè)方面，其中節(jié)點(diǎn)異構(gòu)對網(wǎng)絡(luò)的覆蓋控制影響最大。節(jié)點(diǎn)的異構(gòu)又可以分為通信能力、感知能力、計(jì)算能力等方面的異構(gòu)。目前，有很多學(xué)者已經(jīng)對有向傳感器網(wǎng)絡(luò)、異構(gòu)傳感器網(wǎng)絡(luò)和三維平面上的傳感器網(wǎng)絡(luò)的覆蓋性能進(jìn)行了研究。文獻(xiàn)[6]在傳感器網(wǎng)絡(luò)的覆蓋控制增強(qiáng)問題中，首次引入了虛擬勢場的方法來解決問題；文獻(xiàn)[7]通過自主調(diào)節(jié)技術(shù)，對網(wǎng)絡(luò)的覆蓋問題進(jìn)行了優(yōu)化；文獻(xiàn)[8]通過引入質(zhì)心的概念，提出了基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法（virtual field based coverage algorithm for directional sensor network， PCAFD），對有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的往復(fù)運(yùn)動、覆蓋盲區(qū)和重疊區(qū)進(jìn)行了優(yōu)化；文獻(xiàn)[9]在分析節(jié)點(diǎn)主感知方向可調(diào)模型的基礎(chǔ)上，設(shè)計(jì)微粒適應(yīng)值函數(shù)和種群進(jìn)化策略，提出覆蓋優(yōu)化算法提高了有向傳感器網(wǎng)絡(luò)的覆蓋率；文獻(xiàn)[10]基于鄰居節(jié)點(diǎn)運(yùn)動構(gòu)建有向強(qiáng)柵欄模型，提出覆蓋優(yōu)化算法提高了有向傳感器網(wǎng)絡(luò)的覆蓋率。文獻(xiàn)[11]改進(jìn)了虛擬力算法，而且加入了計(jì)算幾何，提出了一種虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法；文獻(xiàn)[1]受簡單隨機(jī)抽樣理論和最優(yōu)化算法的啟發(fā)，提出了一種異構(gòu)無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化算法，大幅度提高了網(wǎng)絡(luò)覆蓋程度；文獻(xiàn)[12]在異構(gòu)無線傳感器網(wǎng)絡(luò)中引入超級節(jié)點(diǎn)和普通節(jié)點(diǎn)的概念，對普通節(jié)點(diǎn)進(jìn)行狀態(tài)輪轉(zhuǎn)的覆蓋控制算法，提高了網(wǎng)絡(luò)的覆蓋率和連通率；文獻(xiàn)[5]在三維空間下，考慮最優(yōu)覆蓋節(jié)點(diǎn)集和低能耗，提出了一種三維傳感器網(wǎng)絡(luò)低能耗覆蓋算法；文獻(xiàn)[13]提出了三維傳感器節(jié)點(diǎn)的感知模型，在三維空間中結(jié)合空間幾何理論對網(wǎng)絡(luò)的覆蓋問題進(jìn)行了研究；文獻(xiàn)[14]構(gòu)建節(jié)點(diǎn)三維感知模型，通過調(diào)節(jié)主感知方向，提出了面向三維感知的多媒體傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法（ThreeDimensional Perception Based CoverageEnhancing Algorithm， TDPCA）；文獻(xiàn)[15]結(jié)合概率和網(wǎng)絡(luò)最壞覆蓋的K覆蓋方法來提高網(wǎng)絡(luò)覆蓋率。以上方法，有的只是在二維平面上針對有向傳感器網(wǎng)絡(luò)，或者是針對異構(gòu)傳感器網(wǎng)絡(luò)進(jìn)行覆蓋控制研究；還有只是針對三維空間上的全向感知的傳感器網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)覆蓋率的研究。針對三維空間的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問題進(jìn)行的研究很少。而事實(shí)上，隨機(jī)部署的傳感器節(jié)點(diǎn)處于現(xiàn)實(shí)的三維空間中，傳統(tǒng)算法很難實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋率的提高。

本文針對面向三維的節(jié)點(diǎn)感知半徑異構(gòu)的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署時(shí)產(chǎn)生的覆蓋重疊和覆蓋盲區(qū)問題，提出了基于粒子群優(yōu)化算法面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法（Particle Swarm Optimization based coverage optimization algorithm for ThreeDimensional directional Heterogeneous network， PSOTDH），通過粒子群優(yōu)化算法對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)進(jìn)行三維覆蓋重疊區(qū)域優(yōu)化和邊界節(jié)點(diǎn)優(yōu)化處理，提高網(wǎng)絡(luò)的覆蓋率。

1有向異構(gòu)傳感器網(wǎng)絡(luò)三維有向感知模型與覆蓋問題三維有向感知模型及覆蓋問題描述

1.1三維有向感知模型

二維有向感知模型[7]是一個(gè)扇形的感知區(qū)域，以節(jié)點(diǎn)位置為扇形的圓心，以感知半徑為扇形的半徑。它能通過調(diào)節(jié)扇形區(qū)域的主感知方向，使感知區(qū)域覆蓋到不同的地方。

與二維有向感知模型不同，三維有向感知模型[16]是由傳感器節(jié)點(diǎn)的空間坐標(biāo)、感知半徑、傳感器視角方向向量的水平方向向量及垂直方向向量組成的圓錐體區(qū)域。它能通過調(diào)節(jié)圓錐體區(qū)域的主感知方向，使感知區(qū)域繞圓錐區(qū)域的頂點(diǎn)切換到不同的方向。三維有向感知模型可以用一個(gè)五元組（Mi（xi，yi，zi），Bi（t），α，θi，Ri）來表示（如圖1），其中：Mi（xi，yi，zi）為節(jié)點(diǎn)的空間坐標(biāo)，也就是圓錐區(qū)域的頂點(diǎn)；單位向量Bi（t）表示傳感器節(jié)點(diǎn)t時(shí)刻的有向感知方向；α表示傳感器節(jié)點(diǎn)的感知夾角，大小為方向向量Bi（t）在xoy面上的垂線的夾角；θi表示有向傳感器節(jié)點(diǎn)的感知方向，大小為Bi1（t）與x軸正向的夾角（如圖2）；Ri表示傳感器節(jié)點(diǎn)的感知半徑，也就是圓錐區(qū)域的母線長度。特別地，Si（xs，ys，zs）為圓錐區(qū)域底面圓圓心的空間坐標(biāo)。三維全向感知模型是三維有向感知模型的一個(gè)特例，當(dāng)α=π時(shí)，三維有向感知模型就變成了一個(gè)三維全向感知模型。

半徑異構(gòu)的有向異構(gòu)傳感器網(wǎng)絡(luò)滿足半徑相同的三維有向感知模型，只是有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的感知半徑Ri不是一個(gè)確定的值。

1.2三維有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋問題描述

在對本文的面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋問題進(jìn)行研究之前，為了研究方便，首先作如下假設(shè)：

1）本文研究的為半徑不同的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，但有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)滿足三維有向感知模型；

2）有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)初始部署采用隨機(jī)部署，且節(jié)點(diǎn)一旦初始部署完成節(jié)點(diǎn)的位置固定不變；

3）節(jié)點(diǎn)可以獲取自身的位置坐標(biāo)和感知方向等信息；

4）節(jié)點(diǎn)可以通過繞自身轉(zhuǎn)動的方式來改變節(jié)點(diǎn)的主感知方向。

如果有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)滿足以上假設(shè)，在三維空間區(qū)域U中隨機(jī)部署N個(gè)有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)集可以表示為Mi={M1，M2，…，MN}。當(dāng)一個(gè)傳感器節(jié)點(diǎn)i正常工作時(shí)，傳感器網(wǎng)絡(luò)的覆蓋區(qū)域?yàn)閂i=13AiHi，其中，Ai為圓錐體的底面積，Hi為圓錐體的高。當(dāng)N個(gè)傳感器節(jié)點(diǎn)正常工作時(shí)，傳感器網(wǎng)絡(luò)的覆蓋區(qū)域?yàn)椤萅i=1Vi，則面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率可以表示為：

P1（Vi）=（∪Ni=1Vi）/VU×100%（1）

由于三維空間的網(wǎng)絡(luò)覆蓋率計(jì)算比較復(fù)雜，實(shí)現(xiàn)難度大。本文把網(wǎng)絡(luò)覆蓋率的計(jì)算簡化為：在x、y、z三個(gè)方向上等間隔地選取離散點(diǎn)，從而將上文提到的面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率簡化為離散點(diǎn)的計(jì)算模型，由此，可以得到簡化的面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋率的定義為：

定義1在三維空間區(qū)域U中，隨機(jī)部署N個(gè)正常工作的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，三維空間區(qū)域U中離散的點(diǎn)集合為Ω，任意一個(gè)節(jié)點(diǎn)i覆蓋區(qū)域的點(diǎn)集合為Ωai，N個(gè)節(jié)點(diǎn)覆蓋區(qū)域的點(diǎn)集合為Ωa。那么，簡化的面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率P2（Vi）為N個(gè)節(jié)點(diǎn)覆蓋區(qū)域的點(diǎn)集合與三維空間區(qū)域U中離散的點(diǎn)集合的比值，即：

Ωa=∪1≤i≤NΩai（2）

P2（Vi）=‖Ωa‖/‖Ω‖×100%（3）

其中：（B1（t），B2（t），…，Bi（t），BN（t））為N個(gè)節(jié)點(diǎn)的感知方向組成的一個(gè)感知方向向量組。提高網(wǎng)絡(luò)的覆蓋率就是找到一組N個(gè)節(jié)點(diǎn)感知方向的向量組（B1（t），B2（t），…，Bi（t），BN（t）），使N個(gè)節(jié)點(diǎn)覆蓋區(qū)域的點(diǎn)集合為Ωa最大，進(jìn)而使函數(shù)P2（Vi）達(dá)到最大值。

2PSOTDH算法

在三維空間中隨機(jī)部署有向異構(gòu)傳感器節(jié)點(diǎn)后，節(jié)點(diǎn)初始部署以后，傳感器節(jié)點(diǎn)的位置就固定不變，只能通過改變節(jié)點(diǎn)的主感知方向來提高網(wǎng)絡(luò)的覆蓋性能。而且，初始部署以后產(chǎn)生了大量的三維覆蓋重疊區(qū)域和三維邊界節(jié)點(diǎn)，這就導(dǎo)致了網(wǎng)絡(luò)的覆蓋率偏低。此外，大多二維平面的覆蓋優(yōu)化算法在三維空間中對網(wǎng)絡(luò)覆蓋性能的優(yōu)化效果不好。

因此，針對以上問題，把網(wǎng)絡(luò)覆蓋率作為優(yōu)化函數(shù)，在三維有向感知模型中引入三維重疊質(zhì)心、三維有效質(zhì)心和三維邊界質(zhì)心的概念，通過粒子群優(yōu)化算法對三維重疊覆蓋區(qū)域、三維有效覆蓋區(qū)域和三維邊界節(jié)點(diǎn)的分布進(jìn)行優(yōu)化，以提高面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率。

2.1重疊覆蓋區(qū)域優(yōu)化

為了研究方便，本文作以下定義：

定義2在三維研究區(qū)域U中，異構(gòu)節(jié)點(diǎn)i和j的距離為：dis=（xi-xj）2+（yi-yj）2+（zi-zj）2。

定義3兩個(gè)異構(gòu)節(jié)點(diǎn)之間，僅考慮通信距離，若兩個(gè)異構(gòu)節(jié)點(diǎn)i和j的距離小于2Ri（Ri≤Rj，Ri、Rj分別為節(jié)點(diǎn)i和j的感知半徑）時(shí)，則兩個(gè)節(jié)點(diǎn)是可以相互通信的，稱節(jié)點(diǎn)i和j為互為異構(gòu)鄰居節(jié)點(diǎn)。

定義4若節(jié)點(diǎn)i和j為互為異構(gòu)鄰居節(jié)點(diǎn)，那么節(jié)點(diǎn)i的三維覆蓋區(qū)域?yàn)棣竌i和節(jié)點(diǎn)j的三維覆蓋區(qū)域?yàn)棣竌j的交集為兩個(gè)節(jié)點(diǎn)的三維重疊覆蓋區(qū)域，即Ωai∩Ωaj。其中，把節(jié)點(diǎn)的三維重疊覆蓋區(qū)域的質(zhì)心稱為三維重疊質(zhì)心。

定義5若節(jié)點(diǎn)i和j為互為異構(gòu)鄰居節(jié)點(diǎn)，節(jié)點(diǎn)i三維覆蓋區(qū)域的集合去掉節(jié)點(diǎn)的三維重疊覆蓋區(qū)域，就稱為節(jié)點(diǎn)i的三維有效覆蓋區(qū)域，即Ωai-∩Nj=1， j≠iΩai。其中，把節(jié)點(diǎn)i的三維有效覆蓋區(qū)域的質(zhì)心稱為三維有效質(zhì)心。

如圖3，節(jié)點(diǎn)i和j為互為異構(gòu)鄰居節(jié)點(diǎn)。不同的研究區(qū)域有不同的質(zhì)心，則異構(gòu)節(jié)點(diǎn)i的三維有效覆蓋區(qū)域?yàn)棣竌i1，異構(gòu)節(jié)點(diǎn)j的三維有效覆蓋區(qū)域?yàn)棣竌j1；異構(gòu)節(jié)點(diǎn)i和j的三維重疊覆蓋區(qū)域?yàn)棣竌ij。則節(jié)點(diǎn)i的三維有效質(zhì)心為O（Ωai1），三維重疊質(zhì)心為O（Ωaij）。

在三維空間U中，指定的質(zhì)心是離散分布的。其中，指定的質(zhì)心的坐標(biāo)O（x，y，z）可以通過離散方法求得，公式如下：

O（x，y，z）=O1num∑numi=1xi，1num∑numi=1yi，1num∑numi=1zi（4）

其中：xi為離散的粒子的x軸坐標(biāo)；yi為離散的粒子的y軸坐標(biāo)；zi為離散的粒子的z軸坐標(biāo)；num為離散的粒子數(shù)目。

通過粒子群優(yōu)化算法優(yōu)化三維重疊質(zhì)心和三維有效質(zhì)心的分布，使三維重疊質(zhì)心和三維有效質(zhì)心分布更加均勻，以達(dá)到提高網(wǎng)絡(luò)覆蓋率的作用。設(shè)初始隨機(jī)部署N個(gè)有向異構(gòu)傳

感器網(wǎng)絡(luò)節(jié)點(diǎn)，產(chǎn)生了m個(gè)三維重疊質(zhì)心或者三維有效質(zhì)心，m個(gè)三維重疊質(zhì)心粒子或者三維有效質(zhì)心粒子組成了一個(gè)群體。各個(gè)三維重疊質(zhì)心或者三維有效質(zhì)心在三維空間中的坐標(biāo)可以表示為Mi（Mi1，Mi2，…，Mid，MiD）（D=3）。三維重疊質(zhì)心或者三維有效質(zhì)心i（i=1，2，…，m）的速度表示為νi=（νi1，νi2，…，νid，νiD）（D=3）。在每次優(yōu)化迭代中，三維重疊質(zhì)心或者三維有效質(zhì)心通式（5）、（6）來更新位置和速度：

νid=ωνid+c1r1（pbestid-Mid）+c2r2（gbestid-Mid）（5）

Mid=Mid+νid（6）

其中：pbestid為個(gè)體i此時(shí)的最優(yōu)解；gbestid為整個(gè)種群找到的最優(yōu)解；ω為慣性權(quán)重，通常取ω=1；c1和c2為學(xué)習(xí)因子，通常取c1=c2=2；r1和r2取值為[0，1]范圍內(nèi)的隨機(jī)數(shù)。

2.2邊界節(jié)點(diǎn)優(yōu)化

在三維區(qū)域U中，初始隨機(jī)部署完成以后，普遍會產(chǎn)生一些到邊界的距離小于感知半徑的節(jié)點(diǎn)，這些節(jié)點(diǎn)就被稱為三維邊界節(jié)點(diǎn)。三維邊界節(jié)點(diǎn)大部分的覆蓋區(qū)域在研究區(qū)域的邊界以外，因此三維邊界節(jié)點(diǎn)的存在導(dǎo)致了網(wǎng)絡(luò)的覆蓋率偏低，尤其是在有向異構(gòu)傳感器網(wǎng)絡(luò)中，三維邊界節(jié)點(diǎn)的半徑可能會很大，這樣就造成了網(wǎng)絡(luò)資源的極大浪費(fèi)。針對以上問題，PSOTDH提出了面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)三維邊界節(jié)點(diǎn)優(yōu)化方法，以解決三維邊界節(jié)點(diǎn)帶來的覆蓋問題。

圖4為三維邊界區(qū)域示意圖。節(jié)點(diǎn)i為三維邊界節(jié)點(diǎn)，三維邊界節(jié)點(diǎn)的覆蓋區(qū)域分為兩個(gè)部分：三維邊界區(qū)域Ωai1和三維有效覆蓋區(qū)域Ωai2。其中，三維邊界區(qū)域的質(zhì)心稱為三維邊界質(zhì)心，如圖4中O（Ωai1）；O（Ωai2）則為三維有效質(zhì)心。

類比2.1節(jié)提出的三維重疊區(qū)域優(yōu)化分析，通過粒子群優(yōu)化算法對三維邊界質(zhì)心和三維有效質(zhì)心的分布進(jìn)行優(yōu)化，使三維邊界質(zhì)心分布到邊界以內(nèi)，且使三維邊界質(zhì)心和三維有效質(zhì)心的分布更加均勻，提高網(wǎng)絡(luò)的覆蓋率。此外，三維邊界節(jié)點(diǎn)優(yōu)化以后，不再參加其他優(yōu)化。設(shè)l三維邊界質(zhì)心或者三維有效質(zhì)心。l個(gè)三維邊界質(zhì)心粒子或者三維有效質(zhì)心粒子組成了一個(gè)群體，各個(gè)三維邊界質(zhì)心或者三維有效質(zhì)心在三維空間中的坐標(biāo)可以表示為Mi（Mi1，Mi2，…，Mid，MiD）（D=3）。三維邊界質(zhì)心或者三維有效質(zhì)心i（i=1，2，…，l）的速度表示為νi=（νi1，νi2，…，νid，νiD）（D=3）。在每次優(yōu)化迭代中，三維邊界質(zhì)心或者三維有效質(zhì)心通過式（5）、（6）來更新位置和速度。

2.3PSOTDH描述

通過上文的闡述，本文將粒子群優(yōu)化算法引入到面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問題中。PSOTDH主要包括兩個(gè)部分：三維重疊區(qū)域優(yōu)化和三維邊界節(jié)點(diǎn)優(yōu)化。其具體描述如下。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)數(shù)、位置坐標(biāo)信息、半徑信息、感知方向信息和感知夾角信息。

輸出：各個(gè)面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)最后的感知方向。

1）

初始化面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)，設(shè)置優(yōu)化次數(shù)t=0，獲取節(jié)點(diǎn)Mi（xi，yi，zi）的位置坐標(biāo)信息、半徑信息、感知方向信息和感知夾角信息，計(jì)算網(wǎng)絡(luò)的初始覆蓋率P0；

3仿真結(jié)果與分析

3.1算法實(shí)例仿真

在Matlab R2012a環(huán)境中，對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋進(jìn)行優(yōu)化仿真。仿真參數(shù)設(shè)定如表1所示。

在Matlab R2012a中，根據(jù)表1進(jìn)行仿真，得到面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)70個(gè)節(jié)點(diǎn)的初始覆蓋圖，如圖5所示，以及網(wǎng)絡(luò)的初始覆蓋率P0=41.13%。如圖6所示，經(jīng)過PSOTDH算法1次優(yōu)化以后，網(wǎng)絡(luò)的覆蓋率提高到P1=47.25%；經(jīng)過PSOTDH算法5次優(yōu)化以后，網(wǎng)絡(luò)的覆蓋率提高到P5=53.89%；經(jīng)過PSOTDH算法10次優(yōu)化以后，網(wǎng)絡(luò)的覆蓋率提高到P10=61.43%；經(jīng)過PSOTDH算法25次優(yōu)化以后，網(wǎng)絡(luò)的覆蓋率提高到P25=68.95%。從初始覆蓋率P0=41.13%，經(jīng)過1次優(yōu)化后覆蓋率提高幅度為6.12%，優(yōu)化效果很明顯。分別經(jīng)過5次、10次、25次優(yōu)化以后，提高幅度分別為12.76%、20.30%、27.82%。隨優(yōu)化次數(shù)的增加，覆蓋率的提高幅度變緩。25次迭代以后，有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率提高了27.82%，覆蓋達(dá)到最優(yōu)。

表格（有表名）

如圖6所示，經(jīng)過PSOTDH算法的25次優(yōu)化以后，面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率得到了大幅度的提升。特別是前15次優(yōu)化以后，網(wǎng)絡(luò)的覆蓋率就達(dá)到了65.83%，提升幅度達(dá)到了24.70%，說明PSOTDH算法的優(yōu)化速度很快。而且從第15次優(yōu)化以后，網(wǎng)絡(luò)覆蓋率的提升變緩，但依然有緩慢的提升，說明PSOTDH算法具有良好的收斂性。

3.2仿真結(jié)果對比

在Matlab R2012a中，根據(jù)表1中的參數(shù)值進(jìn)行仿真。將在表1參數(shù)情況下將本文的算法PSOTDH和以前研究中提出的算法PCAFD[8]、TDPCA[14]進(jìn)行性能的對比。如圖6，是在規(guī)定的三維研究區(qū)域中隨機(jī)部署70個(gè)無線傳感器節(jié)點(diǎn)，三種算法PCAFD、 TDPCA、PSOTDH優(yōu)化25次網(wǎng)絡(luò)覆蓋率的變化趨勢。從圖6中可以清楚地看出，本文提出的PSOTDH算法在第一次優(yōu)化就可以大幅度地提高面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率，而且整個(gè)過程的優(yōu)化效果比PCAFD、TDPCA算法的優(yōu)化效果提高明顯要好。

在規(guī)定的三維研究區(qū)域隨機(jī)部署50、70、90、110個(gè)無線傳感器節(jié)點(diǎn)，感知半徑Ri為[50，80]范圍內(nèi)30、50、70、90個(gè)隨機(jī)數(shù)，其他仿真參數(shù)仍如表1所示，可以得到不同傳感器個(gè)數(shù)下，經(jīng)過三種算法PCAFD、 TDPCA、PSOTDH各25次優(yōu)化以后網(wǎng)絡(luò)的傳感器數(shù)目對覆蓋率的影響，如圖7所示。從圖7可以看出，無論傳感器個(gè)數(shù)部署的多少，經(jīng)過25次優(yōu)化以后，算法PSOTDH對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問題的優(yōu)化效果都要好于其他兩種算法。

通過對三種算法PCAFD、 TDPCA、PSOTDH的仿真結(jié)果的對比，能夠看出本文提出的針對面向三維的有向異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋問題的算法PSOTDH能夠大幅地提高面向三維的有向異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋率，而且具有良好的優(yōu)化速度和收斂性。

4結(jié)語

本文針對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)隨機(jī)部署節(jié)點(diǎn)后產(chǎn)生的覆蓋重疊區(qū)和盲區(qū)問題，受到粒子群優(yōu)化算法的啟發(fā)，在建立新的三維有向感知模型的基礎(chǔ)上，引入三維重疊質(zhì)心、三維有效質(zhì)心和三維邊界質(zhì)心的概念，提出了基于粒子群優(yōu)化算法面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法PSOTDH；然后通過Matlab仿真驗(yàn)證了算法的有效性，最后通過與以前算法進(jìn)行仿真對比，證明了本文算法的先進(jìn)性。與PCAFD和TDPCA的對比顯示，本文提出的PSOTDH，能夠大幅度提高面向三維的有向異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋率，而且具有良好的優(yōu)化速度和收斂性。本文沒有考慮覆蓋區(qū)域里有障礙物的情況，但是在現(xiàn)實(shí)生活中面向三維的有向異構(gòu)傳感器往往部署在具有障礙物的環(huán)境中，在后期的工作中，應(yīng)該對面向三維的有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋控制進(jìn)行研究的基礎(chǔ)上，考慮障礙物的影響。后期工作中將進(jìn)一步對此進(jìn)行討論和研究。

參考文獻(xiàn)：

[1]

杜曉玉，孫力娟，郭劍，等.異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報(bào)，2014，36（3）：696-702.（DU X Y， SUN L J， GUO J， et al. Coverage optimization algorithm for heterogeneous WSNs [J]. Journal of Electronics and Information Technology， 2014， 36（3）： 696-702.）

[2]

KHEDR A M， OSAMY W. Minimum perimeter coverage of query regions in a heterogeneous wireless sensor network [J]. Information Sciences， 2011， 181（15）： 3130-3142.

[3]

BAI X， YUN Z， DONG X， et al. Notice of violation of IEEE publication principles optimal multiplecoverage of sensor networks [C] // INFOCOM 2011： Proceedings of the 30th IEEE International Conference on Computer Communications， Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ： IEEE， 2011： 2498-2506.

[4]

杜春龍，石為人，石欣，等.虛擬力導(dǎo)向粒子群有向傳感網(wǎng)絡(luò)覆蓋增強(qiáng)算法研究[J].計(jì)算機(jī)應(yīng)用研究，2015，32（8）：2450-2453.（DU C L， SHI W R， SHI X， et al. Study on virtual forcedirected particle swarm coverageenhancing algorithm for directional sensor networks [J]. Application Research of Computers， 2015， 32（8）： 2450-2453.）

[5]

薛文濤，王丁章.基于半徑可調(diào)的三維無線傳感器網(wǎng)絡(luò)覆蓋控制[J].微電子學(xué)與計(jì)算機(jī)，2013，30（9）：106-109.（ XUE W T， WANG D Z. Coverage control for 3D wireless sensor networks based on the adjustment of sensing radius [J]. Microelectronics and Computer， 2013， 30（9）： 106-109.）

[6]

HOWARD A， MATARIC M J， SUKHATME G S. Mobile sensor network deployment using potential fields： a distributed scalable solution to the area coverage problem [C]// Proceedings of the 6th International Conference on Distributed Autonomous Robotics Systems. Berlin： Springer， 2002： 299-308.

[7]

PODURI S， SUKHATME G S. Constrained coverage for mobile sensor networks [C]// ICRA 04： Proceedings of the 2004 IEEE International Conference on Robotic and Automation. Washington， DC： IEEE Computer Society， 2004，1： 165-171.

[8]

戴寧，毛劍琳，付麗霞，等.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：905-907.（DAI N， MAO J L， FU L X， et al. Virtual potential based coverage optimization algorithm for directional sensor networks [J]. Application Research of Computers， 2014， 31（3）： 905-907.）

[9]

孫力娟，杜鵬玲，肖甫，等.基于微粒群優(yōu)化的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].計(jì)算機(jī)研究與發(fā)展，2010，47（S2）：22-25.（SUN L J， DU P L， XIAO F， et al. Coverageenhancing algorithm for directional sensor networks based on particle swarm optimization [J]. Journal of Computer Research and Development， 2010， 47（S2）： 22-25.）

[10]

任勇默，范興剛，車志聰，等.一種有向傳感器網(wǎng)絡(luò)柵欄覆蓋增強(qiáng)算法[J].傳感技術(shù)學(xué)報(bào)，2015，28（7）：1051-1057.（ REN Y M， FAN X G， CHE Z C， et al. An distributing scheme for directional barrier coverage enhancing in DSN [J]. Chinese Journal of Sensors and Actuators， 2015， 28（7）： 1051-1057.）

[11]

馮秀芳，關(guān)志艷，全欣娜.基于虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].計(jì)算機(jī)工程，2009，35（5）：103-105.（ FENG X F， GUAN Z Y， QUAN X N. Coverageenhancing algorithm for nonisomorphic node network based on virtual force [J]. Computer Engineering， 2009， 35（5）： 103-105.）

[12]

權(quán)建國，王國軍，邢蕭飛.無線傳感器網(wǎng)絡(luò)中基于異構(gòu)節(jié)點(diǎn)的覆蓋控制算法[J].傳感技術(shù)學(xué)報(bào)，2010，23（6）：863-867.（QUAN J G， WANG G J， XING X F. A coverage control algorithm based on heterogeneous nodes in wireless sensor networks [J]. Chinese Journal of Sensors and Actuators， 2010， 23（6）： 863-867.）

[13]

ORTIZ C D， PUIG J M， Palau C E， et al. 3D wireless sensor network modeling and simulation [C]// SENSORCOMM 07： Proceedings of the 2007 International Conference on Sensor Technologies and Applications. Washington， DC： IEEE Computer Society， 2007： 307-312.

[14]

肖甫，王汝傳，孫力娟，等.一種面向三維感知的無線多媒體傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].電子學(xué)報(bào)，2012，40（1）：167-172.（ XIAO F， WANG R C， SUN L J， et al. Coverageenhancing algorithm for wireless multimedia sensor networks based on threedimensional perception [J]. Acta Electronica Sinica， 2012， 40（1）： 167-172.）

[15]

王麗，苗鳳娟，陶柏睿，等.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)三維K覆蓋控制方法[J].河南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，33（3）：333-338.（WANG L， MIAO F J， TAO B R， et al. A improved threedimensional Kcoverage control method for sensor network [J]. Journal of Henan Polytechnic University （Natural Science）， 2014， 33（3）： 333-338.）