基于IRVFA算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署

滕志軍，徐苗苗，張　力

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

?

基于IRVFA算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署

滕志軍，徐苗苗，張力

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

摘要：針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)再部署中網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)的有效利用率低問(wèn)題，提出基于IRVFA算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略，建立了節(jié)點(diǎn)分布最佳模型，同時(shí)在RVFA算法的基礎(chǔ)上，引入虛擬引力線，使得網(wǎng)絡(luò)節(jié)點(diǎn)能夠快速均勻的分布在整個(gè)目標(biāo)區(qū)域內(nèi)，該策略可以實(shí)現(xiàn)同時(shí)提高網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)的有效利用率。實(shí)驗(yàn)中通過(guò)將IRVFA算法與VFA算法、RVFA算法相比較，其在網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)的有效利用率方面有明顯優(yōu)勢(shì)，網(wǎng)絡(luò)性能得到很大提升。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；虛擬引力線；網(wǎng)絡(luò)覆蓋率；有效利用率

近年來(lái)專家學(xué)者在節(jié)點(diǎn)部署優(yōu)化領(lǐng)域已開(kāi)展了大量卓有成效的研究[1-2]。金仁成等提出了基于虛擬力算法(Virtual Force Algorithm，VFA)的無(wú)線傳感器網(wǎng)絡(luò)分簇部署策略，提高了網(wǎng)絡(luò)覆蓋率，算法增加了網(wǎng)絡(luò)能量消耗，沒(méi)能最大化網(wǎng)絡(luò)生存周期[3]。Novella等提出了改進(jìn)的虛擬力算法，該算法使得個(gè)別節(jié)點(diǎn)受到外界入侵損壞時(shí)，剩余節(jié)點(diǎn)依然能保證整個(gè)網(wǎng)絡(luò)的覆蓋率，但增加了節(jié)點(diǎn)數(shù)目和算法的復(fù)雜度[4]。傳統(tǒng)的粒子群算法容易提前進(jìn)入部署優(yōu)化的極大值，限制了粒子搜索范圍，趙娜等提出了改進(jìn)的粒子群算法，能夠?qū)崿F(xiàn)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的最佳布局，該算法的收斂速度慢，節(jié)點(diǎn)需要多次移動(dòng)，導(dǎo)致能量過(guò)快消耗[5]。

本文提出一種基于優(yōu)化的可信度虛擬力算法(Improved Reliability-Based Virtual Force Algorithm，IRVFA)的節(jié)點(diǎn)部署策略，其適用于節(jié)點(diǎn)數(shù)目固定、初始隨機(jī)中心部署的情況，如在監(jiān)測(cè)區(qū)域中心初始隨機(jī)拋灑一定數(shù)量的節(jié)點(diǎn)，然后通過(guò)該優(yōu)化算法把節(jié)點(diǎn)快速有效地?cái)U(kuò)散到整個(gè)目標(biāo)區(qū)域中。

1數(shù)學(xué)模型及算法描述

假設(shè)所有的傳感器節(jié)點(diǎn)均具有相同的通信半徑rc，當(dāng)兩節(jié)點(diǎn)間的歐式距離小于它們的通信半徑rc時(shí)，兩個(gè)傳感器節(jié)點(diǎn)就可以相互通信[6]；當(dāng)目標(biāo)區(qū)域中的任意點(diǎn)p與節(jié)點(diǎn)vi的歐式距離小于節(jié)點(diǎn)的感知半徑rs時(shí)，點(diǎn)p能被節(jié)點(diǎn)vi感知覆蓋。

1.1覆蓋率及節(jié)點(diǎn)有效利用率度量

覆蓋率是傳感器網(wǎng)絡(luò)部署優(yōu)化問(wèn)題中的一個(gè)重要性能指標(biāo)[7-8]，定義覆蓋率為每一個(gè)傳感器節(jié)點(diǎn)所覆蓋區(qū)域的并集與整個(gè)監(jiān)測(cè)區(qū)域面積的比值。節(jié)點(diǎn)的有效利用率為每一個(gè)傳感器節(jié)點(diǎn)所覆蓋區(qū)域的并集與所有傳感器節(jié)點(diǎn)所覆蓋區(qū)域的代數(shù)和的比值。

假設(shè)目標(biāo)區(qū)域中傳感器節(jié)點(diǎn)vi的位置坐標(biāo)是Pi=(xi，yi)，Ci為傳感器節(jié)點(diǎn)vi在目標(biāo)區(qū)域T中的覆蓋范圍，目標(biāo)區(qū)域的面積為A，目標(biāo)區(qū)域中節(jié)點(diǎn)總數(shù)為N，則所有傳感器節(jié)點(diǎn)總的覆蓋范圍可以表示為：

(1)

目標(biāo)區(qū)域的覆蓋率可表示為：

(2)

目標(biāo)區(qū)域中節(jié)點(diǎn)的有效利用率可表示為：

(3)

1.2IRVFA優(yōu)化算法

RVFA算法雖然提高了網(wǎng)絡(luò)的覆蓋率，降低了網(wǎng)絡(luò)的移動(dòng)能耗，但在滿足一定覆蓋率的條件下，所使用的節(jié)點(diǎn)數(shù)不是理論上的最小數(shù)目，也就是節(jié)點(diǎn)的有效利用率并不高。

圖1　正六邊形節(jié)點(diǎn)覆蓋模型

圖2　輔助虛擬引力線

以提高節(jié)點(diǎn)利用率為目的，建立正六邊形節(jié)點(diǎn)覆蓋模型，每個(gè)正六邊形都是單個(gè)傳感器節(jié)點(diǎn)的感知區(qū)域的內(nèi)接正六邊形，也即是每個(gè)正六邊形的中心就是傳感器節(jié)點(diǎn)的位置，如圖1所示。

在目標(biāo)區(qū)域的邊界處假設(shè)存在虛擬的主導(dǎo)引力線，如圖2中虛線所示，該引力線對(duì)目標(biāo)區(qū)域內(nèi)的各節(jié)點(diǎn)具有引力作用，吸引各節(jié)點(diǎn)往邊界靠攏，同時(shí)，由于該主導(dǎo)引力線的引力作用，也能有效地防止節(jié)點(diǎn)移出目標(biāo)區(qū)域。從監(jiān)測(cè)區(qū)域的一邊到另一邊將正六邊形中心用直線連接起來(lái)，這樣正六邊形都是分布在直線上的。由于正六邊形是各傳感器節(jié)點(diǎn)感知區(qū)域的內(nèi)接正六邊形，所以相當(dāng)于傳感器節(jié)點(diǎn)分布在直線上。假設(shè)這些直線為虛擬存在的輔助引力線，這些輔助引力線對(duì)傳感器節(jié)點(diǎn)也具有一定的引力作用，同時(shí)同一引力線上和相鄰引力線上的節(jié)點(diǎn)具有一定的斥力作用，這樣可以促使節(jié)點(diǎn)快速均勻的分布在各引力線上。只要傳感器節(jié)點(diǎn)能均勻分布在輔助引力線上，理論上可以實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的無(wú)縫覆蓋，同時(shí)最大化節(jié)點(diǎn)利用率，虛擬引力線的構(gòu)造如圖2所示。

在IRVFA算法中，節(jié)點(diǎn)vi所受合力大小如公式(4)所示。

(4)

2實(shí)驗(yàn)結(jié)果及分析

在保證網(wǎng)絡(luò)連通且節(jié)點(diǎn)數(shù)目相同的情況下，本文從網(wǎng)絡(luò)覆蓋率、節(jié)點(diǎn)的有效利用率方面，利用MATLAB仿真平臺(tái)對(duì)IRVFA算法、RVFA算法和 VFA算法進(jìn)行仿真對(duì)比分析。

在100×100 m2的無(wú)障礙目標(biāo)區(qū)域中，隨機(jī)中心拋撒140個(gè)節(jié)點(diǎn)。傳感器節(jié)點(diǎn)的感知半徑為8 m，依次執(zhí)行IRVFA算法、RVFA算法和 VFA算法40次，所得各算法在相同迭代次數(shù)下的平均覆蓋率和節(jié)點(diǎn)的平均有效利用率分別如圖3和圖4所示。

圖3 平均覆蓋率圖4 節(jié)點(diǎn)平均利用率

從上圖可以看出IRVFA算法在平均網(wǎng)絡(luò)覆蓋率方面均高于VFA算法和RVFA算法。由此可以看出，IRVFA算法使得監(jiān)測(cè)區(qū)域的網(wǎng)絡(luò)覆蓋率得到很大優(yōu)化。

從上圖可以看出IRVFA算法在節(jié)點(diǎn)的平均利用率方面均高于VFA算法和RVFA算法。由此可以看出，IRVFA算法使得監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)有效利用率得到很大優(yōu)化。

3結(jié)論

本文在通過(guò)深入研究RVFA算法的基礎(chǔ)上，提出一種基于優(yōu)化的可信度虛擬力算法(IRVFA算法)，針對(duì)節(jié)點(diǎn)部署中網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)節(jié)點(diǎn)的有效利用率方面存在的不足之處，建立了節(jié)點(diǎn)分布最佳模型，同時(shí)在RVFA算法的基礎(chǔ)上，引入虛擬引力線，使得網(wǎng)絡(luò)節(jié)點(diǎn)能夠快速均勻的分布在整個(gè)目標(biāo)區(qū)域內(nèi)。為了驗(yàn)證該算法是否適應(yīng)課題的要求，使用MATLAB仿真軟件平臺(tái)分別對(duì)該算法、RVFA算法和VFA算法進(jìn)行仿真，通過(guò)實(shí)驗(yàn)結(jié)果的比對(duì)和分析，可以看出相比于RVFA及VFA算法，該優(yōu)化算法在相同節(jié)點(diǎn)數(shù)目情況下對(duì)目標(biāo)區(qū)域的覆蓋率和網(wǎng)絡(luò)節(jié)點(diǎn)的有效利用率方面具有一定的提升。

參考文獻(xiàn)

[1]李建坡，鐘鑫鑫，徐純.無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào)，2015，35(1)：52-58.

[2]李建坡，鐘鑫鑫，徐純.無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào)，2015，35(2)：73-82.

[3]金仁成，韋寧，徐浩，王立鼎.基于虛擬力的無(wú)線傳感器網(wǎng)絡(luò)分簇部署策略[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，35(5)：640-644.

[4]Novella Bartolin，Giancarlo Bongiovanni，Thomas F.La Porta，Simone Silvestri.On the Vulnerabilities of the Virtual Force Approach to Mobile Sensor Deployment[J].IEEE Transactions on Mobile Computing，2014，13(11)：2592-2605.

[5]童孟軍，俞立，鄭立靜等.基于蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)能量有效路由算法研究[J].傳感技術(shù)學(xué)報(bào)，2011，24(11)：1632-1638.

[6]方偉，宋鑫宏.基于Voronoi圖盲區(qū)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J].物理學(xué)報(bào)，2014，63(22)：220701.

[7]張文愛(ài)，劉麗芳，李孝榮.基于粒子進(jìn)化的多粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(7)：51-53.2011，24(11)：1632-1638.

[8]Cheng-Chih Yang，Jyh-Horng Wen.A Hybrid Local Virtual Force Algorithm for Sensing Deployment in Wireless Sensor Network[C].2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing.

Nodes Deployment in Wireless Sensor Networks Based on Improved Reliability Virtual Force Algorithm

TENG Zhi-jun，XU Miao-miao，ZHANG Li

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：In this paper，we propose an improved reliability-based virtual force algorithm for solving the low coverage and low effective utilization of node deployment in wireless sensor network，the best model of node distribution is established，At the same time，the virtual gravity line is introduced，based on the RVFA algorithm，which enables the network nodes to distribute in the entire target area quickly and evenly.This method can improve the network coverage and the effective utilization of the nodes.The simulation results show that IRVFA algorithm has obvious advantages compared with RVFA algorithm and VFA algorithm in coverage rate and effective utilization of the nodes，network performance is improved significantly.

Key words：Wireless sensor network；Virtual gravity line；Coverage；Effective utilization

收稿日期：2016-01-12

基金項(xiàng)目：國(guó)家自然科學(xué)基金(51277023)

作者簡(jiǎn)介：滕志軍(1973-)，男，吉林省吉林市人，東北電力大學(xué)信息工程學(xué)院教授，博士，主要研究方向：無(wú)線通信技術(shù).

文章編號(hào)：1005-2992(2016)02-0086-04

中圖分類號(hào)：TN915

文獻(xiàn)標(biāo)識(shí)碼：A