基于Voronoi算法的無線多媒體傳感器網(wǎng)絡(luò)覆蓋控制研究

霍海平，曾建潮，趙 靜

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

?

基于Voronoi算法的無線多媒體傳感器網(wǎng)絡(luò)覆蓋控制研究

霍海平，曾建潮，趙 靜

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

無線多媒體傳感器網(wǎng)絡(luò)(Wireless Multimedia Senor Networks，WMSNs)的覆蓋控制技術(shù)是傳感器網(wǎng)絡(luò)研究的關(guān)鍵問題，只有合理的部署傳感器節(jié)點，才能達到對目標(biāo)區(qū)域的全面監(jiān)測。Voronoi圖具有良好的區(qū)域劃分性質(zhì)，可以將監(jiān)測區(qū)域劃分成多個小的區(qū)域。所以，提出一種基于Voronoi算法的無線多媒體傳感器網(wǎng)絡(luò)的覆蓋策略。通過Voronoi圖形尋找新增傳感器節(jié)點的坐標(biāo)，計算出節(jié)點的質(zhì)心點坐標(biāo)，調(diào)整節(jié)點的方向。實現(xiàn)用比較少的節(jié)點，獲得較高的覆蓋率。

無線多媒體傳感器網(wǎng)絡(luò)；Voronoi算法；質(zhì)心；覆蓋率

伴隨著信息技術(shù)、微型計算機控制技術(shù)和新型傳感器技術(shù)的不斷發(fā)展，生產(chǎn)出來了能夠進行環(huán)境感知、數(shù)據(jù)處理和信息通信的智能化傳感器。而由這些傳感器節(jié)點可以組成一個智能化的傳感器網(wǎng)絡(luò)，在該網(wǎng)絡(luò)所覆蓋的區(qū)域中，每個節(jié)點可以感知、收集和處理各類數(shù)據(jù)信息，并將這些信息發(fā)布給需要這些信息的用戶[1]。而多媒體傳感器網(wǎng)絡(luò)(Wireless Multimedia Senor Networks，WMSNs)一方面繼承了無線傳感器網(wǎng)絡(luò)(WSNs)的原有特點，同時又具備了上述所說的各項功能。因此，WMSNs也日益成為了一個新興的研究領(lǐng)域。

網(wǎng)絡(luò)覆蓋是設(shè)計傳感器網(wǎng)絡(luò)的關(guān)鍵環(huán)節(jié)，對于WSNs而言，節(jié)點的感知模型為圓形感知模型，網(wǎng)絡(luò)覆蓋算法也非常成熟[2]。但是，對于無線多媒體傳感器網(wǎng)絡(luò)而言，節(jié)點的模型不在是圓形感知模型，而是有向的扇形模型。因此，針對多媒體傳感器網(wǎng)絡(luò)節(jié)點的特點，提出新的網(wǎng)絡(luò)覆蓋控制算法。文獻[3]還討論了通過網(wǎng)絡(luò)的合理部署來討論延長網(wǎng)絡(luò)壽命等問題。文獻[4]討論了在隨機部署和網(wǎng)格部署下，節(jié)點的能耗與部署方式的關(guān)系。所以，網(wǎng)絡(luò)覆蓋是研究WMSNs的基本問題。

針對節(jié)點的模型是扇形感知模型的特點，提出了幾種不同的網(wǎng)絡(luò)覆蓋策略。文獻[5]戴寧等提出了在目標(biāo)區(qū)域中，采用重疊質(zhì)心和節(jié)點的質(zhì)心來調(diào)整傳感器節(jié)點，在虛擬勢場力的作用下調(diào)整節(jié)點方向，以此提高了網(wǎng)絡(luò)覆蓋率。文獻[6]彭玉旭等人提出了“質(zhì)心Voronoi圖”的概念，調(diào)整整個傳感器網(wǎng)絡(luò)中節(jié)點的方向。文獻[7]提出了有關(guān)最大覆蓋面積(MDAC)的問題，定義了要調(diào)整方向的節(jié)點與其鄰居節(jié)點所對應(yīng)的圓形覆蓋下的交點或切點為候選點，之后再根據(jù)節(jié)點間的位置關(guān)系來調(diào)整方向。文獻[8]采用虛擬勢場的方式，對于有向傳感器節(jié)點通過虛擬勢場力來調(diào)整節(jié)點方向。另外有些研究通過采用傳統(tǒng)的貪心算法或改進的貪心算法，進行網(wǎng)絡(luò)的局部優(yōu)化，通過多次迭代來完成節(jié)點的調(diào)整和部署[9-11]。利用Voronoi圖形可以將監(jiān)測區(qū)域分成多個小的監(jiān)測區(qū)域，之后再放置節(jié)點。所以，根據(jù)Voronoi圖的特點，尋找合理的位置放置傳感器節(jié)點，完成部署任務(wù)[12-13]。在監(jiān)測區(qū)域中，首先部署大量節(jié)點之后，得到相應(yīng)的Voronoi圖，利用凸耳消元法消去任意點[14]。在區(qū)域監(jiān)控過程中，由于障礙物的存在，網(wǎng)絡(luò)中可能存在漏洞點，可以利用Voronoi圖和delaunay三角剖分，來對網(wǎng)絡(luò)進行優(yōu)化[15]。這些研究多數(shù)是針對隨機部署，之后再調(diào)整節(jié)點和優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)，這也只能提高局部位置上的覆蓋率。有些采用貪心算法進行迭代部署，這樣有可能會使得算法過于復(fù)雜。這些研究也很少涉及到確定性部署的問題，同時也未必能夠使用比較少的節(jié)點，獲得較高的覆蓋率。

本文采用基于Voronoi圖的原理，結(jié)合不可轉(zhuǎn)動的有向扇形模型，來完成節(jié)點的部署任務(wù)。在目標(biāo)區(qū)域中，首先放置少量節(jié)點，之后得到相應(yīng)的Voronoi圖形。分析圖形特點，尋找合適位置準(zhǔn)備下一輪的部署。由于節(jié)點是有向感知模型，所以，采用“質(zhì)心”來確定節(jié)點的感知方向，最終實現(xiàn)使用比較少的節(jié)點，獲得較高的覆蓋率。

1 基于Voronoi算法的WMSNs覆蓋研究

1.1 概念及節(jié)點模型

1)Voronoi圖是指：由在平面上的任意相鄰的多個點(a1,a2,…an)，其垂直平分線所組成的不規(guī)則多邊形的集合[16]。如圖1所示，在目標(biāo)區(qū)域中，將少量傳感器節(jié)點放置到個別關(guān)鍵位置上，得到對應(yīng)的Voronoi圖形。

圖1 初始化節(jié)點位置

Fig.1 Initial nodes location

2)在圖1中所示，A、B、C點稱之為Voronoi圖邊上的頂點。

3)質(zhì)心的概念

針對有向的扇形模型，其質(zhì)心點的位置距節(jié)點的位置的長度為：L=2Rsinα/3α，且位于方向軸上。其中：α表示扇形模型的感知范圍、R表示感知半徑。為了調(diào)整有向傳感器節(jié)點的方向，假設(shè)扇形節(jié)點的質(zhì)心繞節(jié)點可以旋轉(zhuǎn)[7]。

4)有向的扇形模型

在有向的節(jié)點模型中，其模型假設(shè)為：2α=900，α=450為感知范圍；R=80 m為感知半徑；V表示節(jié)點的方向；(xi,yi)表示節(jié)點坐標(biāo)。

如圖2所示，根據(jù)上述的節(jié)點模型，在初始化階段，放置了13個傳感器節(jié)點，每個節(jié)點的模型為有向的扇形模型。

圖2 初始化13個扇形感知模型

Fig.2 Initial 13 sector perceptual models

1.2 算法描述

1.2.1 尋找合理的新增節(jié)點的位置

如圖3所示，兩個節(jié)點的連線與Voronoi圖形的邊相垂直，垂足為C點。同時，節(jié)點與Voronoi圖形的邊距離最小的點也是C點，也是覆蓋最強的地方。從C出發(fā)點沿著Voronoi的邊到達頂點處(A、B點)，監(jiān)測的范圍與節(jié)點的距離拉大，因此，節(jié)點的監(jiān)控覆蓋逐漸減弱。所以，A點或B點成為覆蓋監(jiān)測過程中比較薄弱的位置[12]。

同理，針對扇形感知模型覆蓋時，Voronoi圖形邊上的頂點同樣也是覆蓋最薄弱的環(huán)境，所以，任然可以考慮將頂點坐標(biāo)作為新增節(jié)點的坐標(biāo)位置。

1.2.2 明確扇形節(jié)點的感知方向

針對扇形節(jié)點的特點，即：節(jié)點是有向的感知模型。如何放置節(jié)點就成為了提高網(wǎng)絡(luò)覆蓋率的一個關(guān)鍵環(huán)節(jié)。第一步，根據(jù)上述方法，找到放置節(jié)點的坐標(biāo)位置。第二步，要確定扇形節(jié)點的感知方向。這時，引用質(zhì)心的概念來明確節(jié)點的方向，使用比較少的節(jié)點，獲得較高的覆蓋率。

圖3 根據(jù)Voronoi圖的特點尋找新增節(jié)點的位置

Fig.3 the location of the new nodes to be found according to the features of Voronoi diagram

在監(jiān)測區(qū)域中，不同的節(jié)點之間可能會彼此相互影響。當(dāng)兩節(jié)點之間的距離小于節(jié)點的通信半徑時，才可能會出現(xiàn)覆蓋重疊的情況。所以，當(dāng)出現(xiàn)上述情況時，可以認為兩節(jié)點間會彼此影響，同時存在相互作用力[18]。當(dāng)滿足上述條件的節(jié)點，就稱之為鄰居節(jié)點。

在兩個相鄰節(jié)點之間，其質(zhì)心之間的作用力大小，定義如下：

(1)

如果質(zhì)心點Ci與質(zhì)心點Cj的距離不小于2倍感知半徑時，對應(yīng)的節(jié)點間的作用力為0.反之，則存在作用力。同理，當(dāng)質(zhì)心點Ci受到周圍多個質(zhì)心點的作用力時，當(dāng)節(jié)點受力平衡時，節(jié)點就會固定在一個確定的位置。

如圖4中所示，由節(jié)點S1、S2、S3、S4的坐標(biāo)值，能夠計算出S1與S2的距離L12、S1與S2的距離L13和S1與S4的距離L14，可以判斷出L12和L13小于節(jié)點的通信半徑、L14大于節(jié)點的通信半徑。所以，S1同時會受到S2、S3的影響，而不會受到S4的影響。F12表示：質(zhì)心點C2對C1的作用力,F13表示：質(zhì)心點C3對C1的作用力。當(dāng)F12和F13中沿著質(zhì)心圓切線方向的分力不平衡時，質(zhì)心會沿著質(zhì)心圓的軌跡來調(diào)整節(jié)點的方向。通過微調(diào)節(jié)點的角度，如果沿著切線方向的受力平衡時，將節(jié)點調(diào)整到了合適的位置上。

圖4 節(jié)點與其鄰居節(jié)點

Fig.4 Nodes and its neighbor nodes

綜上所述，在尋找節(jié)點的方向時。第一步，以節(jié)點為圓心，以節(jié)點與質(zhì)心點之間的距離為半徑畫圓，此圓為質(zhì)心圓。第二步，根據(jù)節(jié)點的坐標(biāo)值，可以計算出節(jié)點間的距離，就可以判斷出那些節(jié)點是鄰居節(jié)點。第三步，當(dāng)找到鄰居節(jié)點之后，假設(shè)該節(jié)點周圍有k個鄰居節(jié)點，方向角是：(α1,α2…,αk).可以令：αi=(α1+α2+…+αk)/k為初始角，來放置新增節(jié)點并得到相應(yīng)的質(zhì)心圓。第四步，根據(jù)鄰居節(jié)點的質(zhì)心位置，進行受力分析，沿著質(zhì)心圓來微調(diào)節(jié)點的方向。當(dāng)質(zhì)心點所受外力平衡時，此時就是新增的最終方向。

通過部署比較少的節(jié)點，獲得較高的覆蓋率。如圖5所示，在初始化覆蓋的基礎(chǔ)上，繼續(xù)尋找新增節(jié)點的位置，給該節(jié)點初始化一個方向，再根據(jù)上述的方法來調(diào)整其方向，之后進行迭代部署，就得到了第1次的覆蓋情況。

圖5 第1次覆蓋

Fig.5 The first coverage

2 仿真與分析

實驗是在MATLAB R2012a的環(huán)境下進行的，對所提出的算法進行仿真。在仿真實驗中，令：α=450為節(jié)點感知范圍，R=80 m為感知半徑，在500×500 m2的目標(biāo)區(qū)域中完成節(jié)點的部署。

在初始化階段，在關(guān)鍵位置上放置13個節(jié)點，如圖1和圖2所示。之后，找到新增節(jié)點的坐標(biāo)位置，給新增節(jié)點初始化一個方向角并且計算出質(zhì)心坐標(biāo)，調(diào)整節(jié)點方向。如圖5所示，第一輪覆蓋的情況，覆蓋率為32.1%.如圖6、7分別是第2次部署和第3次部署，覆蓋率為45.71%和55.94%，使用節(jié)點數(shù)量分別是23個和29個。如圖8所示，當(dāng)通過10次的部署之后，使用62個節(jié)點，最終達到94.52%的覆蓋率。

圖6 第2次覆蓋

Fig.6 The 2nd coverage

圖7 第3次覆蓋

Fig.7 The 3rd coverage

圖8 第10次覆蓋

Fig.8 The 10th coverage

在初始化部署階段，其P0=26.13%.不斷部署節(jié)點，覆蓋率逐漸增加。當(dāng)通過10次的部署之后，使用了62個節(jié)點，可以達到P10=94.52%.所以，通過Voronoi圖形進行確定性部署，先來判斷那些位置上可能是最大的覆蓋漏洞點，之后選擇合適的位置作為新增節(jié)點的坐標(biāo)，利用質(zhì)心來調(diào)整節(jié)點的方向，降低覆蓋重疊度，能夠合理的部署節(jié)點。最終達到使用比較少的節(jié)點，獲得較高的覆蓋率。

3 結(jié)束語

本文提出一種基于Voronoi圖的WMSNs的覆蓋控制策略，研究對象主要是不可轉(zhuǎn)動的節(jié)點模型，采用確定性部署方案，通過迭代來完成網(wǎng)絡(luò)覆蓋任務(wù)，研究了如何能夠獲得較高的覆蓋率。確定節(jié)點的坐標(biāo)，計算節(jié)點的質(zhì)心坐標(biāo)，調(diào)整每個節(jié)點的方向，使得節(jié)點轉(zhuǎn)到一個較為合理的方向上，降低重疊度，最后通過仿真實驗來驗證算法的合理性。接下來要討論的是針對節(jié)點可以轉(zhuǎn)動的情況下，如何完成節(jié)點的部署任務(wù)；以及有關(guān)網(wǎng)絡(luò)的連通性與網(wǎng)絡(luò)覆蓋的關(guān)系。

[1] MA HUA-DONG,TAO DAN.Multimedia Sensor Network and Its Research Progresses[J]. Journal of Software,2006,17(9):2013-2028.

[2] 張璐.無線多媒體傳感器網(wǎng)絡(luò)覆蓋技術(shù)研究[M].西安:西安電子科技大學(xué),2014.

[3] ZHU CHUAN.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks[J].Journal of Network and Computer Applications,2012(35):619-632.

[4] MONICA. Comparative Study of Energy Consumption for Wireless Sensor Network Based on Random and Gird Deployment Strategies[J]. International Journal of Computer Applications, 2010,1(6):28-35.

[5] 戴寧，毛劍琳.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計算機應(yīng)用研究,2014,31(3):905-907.

[6] 彭玉旭.有向傳感器網(wǎng)絡(luò)覆蓋增強研究[J].計算機工程,2011,37(2):100-104.

[7] TSAI CHIH-HUNG.Coverage Enhancing Algorithms in Directional Sensor Networks with Rotatable Sensors[J].Asia-Pacific Service Computing Conference,2011,15(12):377-383.

[8] Jing Z. A Virtual Potential Field Based Coverage Algorithm for Directional Networks[J]. Control and Decision Conference.Chinese，2009(6):4590-4595.

[9] Jing LI,WAND RU-CHUANG. Voronoi-Based Coverage Optimization for Directional Sensor Networks[J].Wireless Sensor Network,2009(1):417-424.

[10] 陸克中,馮禹洪.有向傳感器網(wǎng)絡(luò)覆蓋增強問題的貪婪迭代算法[J].電子學(xué)報,2012,40(4):687-694.

[11] 溫俊,蔣杰.公平的有向傳感器網(wǎng)絡(luò)方向優(yōu)化和節(jié)點調(diào)度算法[J].軟件學(xué)報,2009,20(3):644-659.

[12] 楊海靂,趙靜. 基于Voronoi圖的無線傳感器網(wǎng)絡(luò)覆蓋算法研究[J].信息通信, 2015(7):28-31.

[13] 秦澤峰.基于Voronoi圖的無線傳感器網(wǎng)絡(luò)覆蓋算法研究[J].太原科技大學(xué)學(xué)報,2013,34(3):185-190.

[14] 秦志霞,沈煒. 二維Voronoi圖刪除任意生成點算法研究[J].浙江理工大學(xué)學(xué)報，2010:27(3):421-425.

[15] MEYSAM ARGANY.Voronoi-Based Approaches for Geosensor Networks Coverage Determination and Optimisation:A Survey[J].International Symposium on Voronoi Diagrams in Science and Engineering(ISVD),2010(6):115-123.

[16] 鄧俊輝.計算幾何-算法與應(yīng)用[M].北京:清華大學(xué)出版社,2006.

[17] 陰成軍.無線多媒體傳感器網(wǎng)絡(luò)覆蓋增強算法研究[D].太原:太原理工大學(xué),2008.

[18] 張賢鳳.有向傳感器網(wǎng)絡(luò)覆蓋算法研究[D].長沙:長沙理工大學(xué),2011.

[19] 趙靜,曾建潮.無線多媒體傳感器網(wǎng)絡(luò)感知模型與數(shù)量估計[J].軟件學(xué)報,2012,23(8):2104-2114.

Research on Coverage in Wireless Multimedia Senor Networks Based on Voronoi Algorithm

HUO Hai-ping, ZENG Jian-chao, ZHAO Jing

(School of Electronic and Information Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Coverage technology of Wireless Multimedia Senor Networks(WMSNs) is the key problem of sensor network research. Only the rational deployment of sensor nodes can achieve full detection of the target areas. Voronoi diagram has good characteristics of regional division, and monitoring areas can be divided into some smaller areas. This paper presents a method based on Voronoi diagram coverage strategy in wireless multimedia sensor networks, the coordinates of the new nodes by Voronoi graph can be found. Then, the centroid coordinates of its node can be calculated and the direction of nodes can be adjusted, and maximum coverage rate can be achieved by using a few nodes as possible.

wireless multimedia senor networks, voronoi algorithm, centroid point, coverage rate

1673-2057(2016)06-0438-05

2016-01-08

山西省自然科學(xué)基金(2014011019-2)；校博士后科研啟動基金( 20142023).

霍海平(1988-)，男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)。

TP393

A

10.3969/j.issn.1673-2057.2016.06.004