滕志軍，徐苗苗，張　力

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

?

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

滕志軍，徐苗苗，張力

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

1.2IRVFA優(yōu)化算法

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

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

圖2　輔助虛擬引力線

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

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

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

(4)

2實驗結(jié)果及分析

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

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

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

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

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

3結(jié)論

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

參考文獻

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

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

[3]金仁成，韋寧，徐浩，王立鼎.基于虛擬力的無線傳感器網(wǎng)絡(luò)分簇部署策略[J].東北大學(xué)學(xué)報：自然科學(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ǎng)絡(luò)能量有效路由算法研究[J].傳感技術(shù)學(xué)報，2011，24(11)：1632-1638.

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

[7]張文愛，劉麗芳，李孝榮.基于粒子進化的多粒子群優(yōu)化算法[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

基金項目：國家自然科學(xué)基金(51277023)

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

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

中圖分類號：TN915

文獻標(biāo)識碼：A