無(wú)線傳感器網(wǎng)絡(luò)中的一種虛擬力算法研究

胡 汀

（湖南廣播電視大學(xué)信息學(xué)院 湖南 長(zhǎng)沙 410004）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network,WSN）是由大量靜止或移動(dòng)的傳感器以自組織和多跳的方式構(gòu)成的無(wú)線網(wǎng)絡(luò)，實(shí)現(xiàn)了數(shù)據(jù)的采集、處理和傳輸三種功能，被廣泛應(yīng)用于軍事、救災(zāi)、工農(nóng)業(yè)生產(chǎn)等領(lǐng)域[1]。無(wú)線傳感器網(wǎng)絡(luò)內(nèi)傳感器節(jié)點(diǎn)主要有三種部署方式：確定位置的節(jié)點(diǎn)部署、隨機(jī)拋灑且位置固定不定的節(jié)點(diǎn)部署和隨機(jī)拋灑且節(jié)點(diǎn)可移動(dòng)的部署。目前，采用隨機(jī)拋灑且節(jié)點(diǎn)可移動(dòng)部署的無(wú)線傳感器網(wǎng)絡(luò)最多，因?yàn)檫@種無(wú)線傳感器網(wǎng)絡(luò)使用靈活，適用面廣。但是，這種部署方式卻存在節(jié)點(diǎn)不均勻、容易形成覆蓋空洞等問題。

Zou等[2]最早提出虛擬力算法（virtual force algorithm，VFA），將虛擬力的概念應(yīng)用于節(jié)點(diǎn)的動(dòng)態(tài)分析，節(jié)點(diǎn)之間的受力取決于節(jié)點(diǎn)之間的距離，卻沒有考慮節(jié)點(diǎn)的移動(dòng)出界等問題。Howard等[3]把勢(shì)能概念運(yùn)用到虛擬力的分析中，實(shí)現(xiàn)了惡劣環(huán)境下的網(wǎng)絡(luò)覆蓋，卻沒有充分考慮網(wǎng)絡(luò)的連通和算法的收斂。Chen等[4]提出了改進(jìn)的虛擬力算法，對(duì)傳統(tǒng)虛擬力模型進(jìn)行了一定程度上的改進(jìn)，卻沒有考慮傳感器網(wǎng)絡(luò)范圍內(nèi)的障礙物問題。REN等[5]比較了四種虛擬力模型，對(duì)各個(gè)參數(shù)進(jìn)行了性能測(cè)試，也沒有考慮傳感器網(wǎng)絡(luò)范圍內(nèi)的障礙物問題。針對(duì)以上虛擬力模型與算法的研究，本文提出了一種改進(jìn)的虛擬力模型，確保無(wú)線傳感器節(jié)點(diǎn)不會(huì)移動(dòng)出界。

2 虛擬力算法的基本原理

虛擬力算法在無(wú)線傳感器網(wǎng)絡(luò)中的使用，是將物理學(xué)力學(xué)勢(shì)場(chǎng)中的萬(wàn)有引力概念引用至無(wú)線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)抽象成力學(xué)勢(shì)場(chǎng)中的粒子，那么傳感器節(jié)點(diǎn)之間將存在著虛擬作用力（以下簡(jiǎn)稱虛擬力）的作用，虛擬力可能是兩種不同的力，即：（1）吸引力；（2）排斥力。

在網(wǎng)絡(luò)部署優(yōu)化過程中，節(jié)點(diǎn)依據(jù)自身受力情況不斷移動(dòng)，直到受力平衡或到達(dá)邊界時(shí)為止。

3 虛擬力算法

3.1 基本假設(shè)

（1）監(jiān)測(cè)區(qū)域?yàn)槎S矩形平面，監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)隨機(jī)部署且可移動(dòng)，每個(gè)節(jié)點(diǎn)的傳感范圍都是半徑為Rs的圓，所有的傳感器節(jié)點(diǎn)性能相同，都有相同的傳感半徑Rs和通信半徑Rc。（2）傳感器節(jié)點(diǎn)利用GPS或者其他定位算法獲取節(jié)點(diǎn)自身的坐標(biāo)信息，也可以獲得相鄰節(jié)點(diǎn)之間的距離關(guān)系。（3）每個(gè)節(jié)點(diǎn)包含一個(gè)移動(dòng)執(zhí)行器，可以保證節(jié)點(diǎn)在移動(dòng)區(qū)域內(nèi)自由移動(dòng)。每個(gè)節(jié)點(diǎn)包含相同的初始能量，節(jié)點(diǎn)在移動(dòng)過程中也會(huì)消耗一定量的能量。

3.2 節(jié)點(diǎn)感知模型

在二維矩形監(jiān)測(cè)區(qū)域內(nèi)，若源節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)t的位置坐標(biāo)分別為和，節(jié)點(diǎn)感知半徑為Rs，則目標(biāo)節(jié)點(diǎn)t被源節(jié)點(diǎn)s感知到的概率為[6]

式中，d(s,t)是源節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)t之間的歐式距離，可表示為

節(jié)點(diǎn)感知模型見圖1，目標(biāo)節(jié)點(diǎn)1t位于圓內(nèi)，則，源節(jié)點(diǎn)s能感知到目標(biāo)結(jié)點(diǎn)t1；目標(biāo)節(jié)點(diǎn)t2位于圓外，則p(s,t2)=0，源節(jié)點(diǎn)s不能感知到目標(biāo)結(jié)點(diǎn)t2。

圖1 節(jié)點(diǎn)感知模型

3.3 改進(jìn)虛擬力算法

3.3.1 傳統(tǒng)虛擬力模型

在Zou等提出的傳統(tǒng)虛擬力模型中，傳感器節(jié)點(diǎn)i感知范圍內(nèi)的相鄰節(jié)點(diǎn)集合為S1，假設(shè)傳感器節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離dij大于事先規(guī)定的閾值Dth時(shí)，互相吸引；而時(shí)，互相排斥。則兩個(gè)節(jié)點(diǎn)之間的受力公式[7]為：

其中，dij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的歐式距離；αij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的方向角；wα表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的虛擬吸引力；wγ表示排斥參數(shù)；Dth是根據(jù)實(shí)際網(wǎng)絡(luò)運(yùn)行狀況設(shè)置的距離閾值[8]。

如圖2所示，當(dāng)覆蓋率 1α＜ 時(shí)，監(jiān)測(cè)區(qū)域沒有被傳感器節(jié)點(diǎn)完全覆蓋。此時(shí)，距離閾值的計(jì)算公式為：

圖2 距離閾值

當(dāng)覆蓋范圍α≥1 時(shí)，整個(gè)監(jiān)測(cè)區(qū)域被完全覆蓋，距離閾值的計(jì)算公式可表示為：

3.3.2 區(qū)域邊界對(duì)節(jié)點(diǎn)的排斥效應(yīng)

從傳統(tǒng)虛擬力模型可以看出，網(wǎng)絡(luò)中的節(jié)點(diǎn)在不同的力的作用下有可能會(huì)移出監(jiān)測(cè)區(qū)域，形成無(wú)用的節(jié)點(diǎn)，這也是傳統(tǒng)虛擬力算法最主要的缺陷。

因此，在上述傳統(tǒng)虛擬力模型的基礎(chǔ)上，加入?yún)^(qū)域邊界對(duì)節(jié)點(diǎn)的排斥效應(yīng)，以保證監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)不會(huì)移動(dòng)出界。假設(shè)節(jié)點(diǎn)之間沒有排斥，則存在邊界b對(duì)節(jié)點(diǎn) 的虛擬力：

其中，dib表示節(jié)點(diǎn)i與區(qū)域邊界b的距離；wb表示表示邊界b的斥力參數(shù)；Dth?b表示節(jié)點(diǎn)i與區(qū)域邊界b之間的距離閾值（一般設(shè)置為Dth/2）。

前面已假設(shè)監(jiān)測(cè)區(qū)域?yàn)槎S矩形平面，因此，節(jié)點(diǎn)會(huì)受到二維矩形平面4個(gè)邊界作用力，4個(gè)邊界區(qū)域的集合為S2，令x1、x2、y1、y2分別表示x軸與y軸的4個(gè)方向，傳感器節(jié)點(diǎn)i受到的4個(gè)邊界斥力的合力為：

3.3.3 障礙物對(duì)節(jié)點(diǎn)的虛擬力

實(shí)際使用中的無(wú)線傳感器網(wǎng)絡(luò)并不能避免障礙物的存在，所以定義障礙物對(duì)節(jié)點(diǎn)的虛擬力為排斥力，保證節(jié)點(diǎn)碰到障礙物時(shí)能主動(dòng)避讓。假設(shè)傳感器節(jié)點(diǎn)i感知范圍內(nèi)的障礙物集合為S3，則障礙物obj對(duì)傳感器節(jié)點(diǎn)i的排斥力計(jì)算公式為：

式（8）中，wob表示障礙物obj對(duì)傳感器節(jié)點(diǎn)i的排斥力系數(shù)；s(i)是傳感器節(jié)點(diǎn)i的坐標(biāo)；s(obj)是障礙物obj的坐標(biāo)；di?obj是障礙物obj與傳感器節(jié)點(diǎn)i之間的垂直距離；Dob障礙物obj與傳感器節(jié)點(diǎn)i之間的距離閾值。

3.3.4 改進(jìn)虛擬力算法

改進(jìn)虛擬力算法在考慮相鄰傳感器節(jié)點(diǎn)j與節(jié)點(diǎn)i之間虛擬力的基礎(chǔ)上，引入式（7）所示的區(qū)域邊界斥力，以及式（8）所示的障礙物對(duì)傳感器節(jié)點(diǎn)i的虛擬力，則傳感器節(jié)點(diǎn)i所受到的x方向合力為：

式（9）中，F(xiàn)ij_x表示相鄰傳感器節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i在x方向上的作用力，F(xiàn)ib_x表示邊界斥力合力對(duì)節(jié)點(diǎn)i在x方向上的作用力，k表示相鄰節(jié)點(diǎn)的數(shù)目，m表示相鄰障礙物的數(shù)目，F(xiàn)i?obj_x表示障礙物obj對(duì)傳感器節(jié)點(diǎn)i在x方向上的作用力。

傳感器節(jié)點(diǎn)i所受到的y方向合力為：

式（10）中，F(xiàn)ij_y表示相鄰傳感器節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i在y方向上的作用力，F(xiàn)ib_y表示邊界斥力合力對(duì)節(jié)點(diǎn)i在y方向上的作用力，k表示相鄰節(jié)點(diǎn)的數(shù)目，m表示相鄰障礙物的數(shù)目，F(xiàn)i?obj_y表示障礙物obj對(duì)傳感器節(jié)點(diǎn)i在y方向上的作用力。

傳感器節(jié)點(diǎn)i所受到的虛擬力合力計(jì)算公式為：

4 節(jié)點(diǎn)移動(dòng)與位置更新

傳感器節(jié)點(diǎn)i在上述虛擬力合力的作用下，不斷移動(dòng)，直到受力平衡時(shí)，傳感器節(jié)點(diǎn)達(dá)到穩(wěn)定狀態(tài)。節(jié)點(diǎn)i移動(dòng)到的新位置在x方向和y方向上投影為：

其中，Xiold表示節(jié)點(diǎn)i移動(dòng)前的位置在x方向上的投影；Fi_X表示節(jié)點(diǎn)i所受到的虛擬力合力在x方向的投影；Fi_Y表示節(jié)點(diǎn)i所受到的虛擬力合力在y方向上的投影；Fi表示節(jié)點(diǎn)i所受到的虛擬力合力；Maxdis表示節(jié)點(diǎn)的單位最大移動(dòng)距離。

5 改進(jìn)虛擬力算法流程

改進(jìn)虛擬力算法主要流程如圖3。

圖3 虛擬力算法流程圖

6 結(jié)論

在傳統(tǒng)虛擬力模型中，由于沒有對(duì)節(jié)點(diǎn)移動(dòng)出界的邊界條件進(jìn)行限制，節(jié)點(diǎn)有可能在虛擬力作用下移動(dòng)出界，對(duì)傳感器的能耗造成巨大的浪費(fèi)。本文在傳統(tǒng)虛擬力模型的基礎(chǔ)上，引入了監(jiān)測(cè)區(qū)域邊界對(duì)傳感器節(jié)點(diǎn)的排斥力，確保傳感器節(jié)點(diǎn)不會(huì)出界，一定在傳感區(qū)域內(nèi)。同時(shí)，本文在改進(jìn)虛擬力算法時(shí)考慮了障礙物的存在，因?yàn)閷?shí)際應(yīng)用過程中有可能會(huì)出現(xiàn)障礙物，導(dǎo)致網(wǎng)絡(luò)性能的下降。如何對(duì)改進(jìn)虛擬力算法進(jìn)行仿真分析是下一階段研究的重點(diǎn)。