空中無(wú)線傳感網(wǎng)復(fù)雜路徑自主部署技術(shù)研究①

焦瑤瑤 譚 勵(lì) 蘇維均 楊明華 胡計(jì)鵬

?

空中無(wú)線傳感網(wǎng)復(fù)雜路徑自主部署技術(shù)研究①

焦瑤瑤②譚 勵(lì) 蘇維均 楊明華 胡計(jì)鵬

(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 北京 100048)

為了能夠完成對(duì)真實(shí)環(huán)境中復(fù)雜目標(biāo)路徑的監(jiān)測(cè)，提出了一種基于虛擬力的三維空中無(wú)線傳感器網(wǎng)絡(luò)復(fù)雜路徑自主部署算法，該算法創(chuàng)新性地采用由復(fù)雜路徑產(chǎn)生的“引力曲線”構(gòu)建虛擬力場(chǎng)，使無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠自適應(yīng)地完成對(duì)復(fù)雜目標(biāo)路徑的覆蓋。仿真實(shí)驗(yàn)表明，與傳統(tǒng)的虛擬力算法相比，該算法的部署過(guò)程更為迅速，路徑覆蓋率、均勻度均有較大提升。

空中無(wú)線傳感器網(wǎng)絡(luò)(AWSN)， 三維部署， 復(fù)雜路徑， 虛擬力

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)技術(shù)伴隨著通信技術(shù)、嵌入式計(jì)算等技術(shù)的成熟而得到迅猛快速發(fā)展。無(wú)線傳感器網(wǎng)絡(luò)借助具有無(wú)線通信能力的傳感器節(jié)點(diǎn)，將其感知和采集的環(huán)境信息通過(guò)自組織方式所形成的多跳網(wǎng)絡(luò)進(jìn)行傳輸，使人們可以不受時(shí)間、地點(diǎn)和環(huán)境的限制，通過(guò)傳感器節(jié)點(diǎn)便可獲得大量真實(shí)可靠的物理世界信息，非常適用于條件惡劣或人類無(wú)法親身到達(dá)的環(huán)境。目前，無(wú)線傳感器網(wǎng)絡(luò)已廣泛應(yīng)用于工業(yè)、軍事、農(nóng)業(yè)、醫(yī)療、環(huán)境監(jiān)測(cè)等領(lǐng)域，應(yīng)用前景十分廣闊[1-3]。

微小型飛行器與具有感知和通信能力的無(wú)線傳感器網(wǎng)絡(luò)結(jié)合構(gòu)成了空中無(wú)線傳感器網(wǎng)絡(luò)(aerial WSN，AWSN)。與傳統(tǒng)的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署不同，空中無(wú)線傳感網(wǎng)的節(jié)點(diǎn)不再是靜態(tài)的，其節(jié)點(diǎn)由微小型飛行器組成，不僅具有感知能力，而且還兼有自主飛行能力，因而能夠根據(jù)實(shí)際環(huán)境，更加及時(shí)準(zhǔn)確地獲取目標(biāo)區(qū)域數(shù)據(jù)信息[4-6]。近幾年，發(fā)生在人口密集地區(qū)的地質(zhì)災(zāi)難給人類生命、財(cái)產(chǎn)造成了重大損失，非常重要的原因之一是發(fā)生災(zāi)害期間道路、橋梁被毀，各類通信手段遭到毀滅性破壞，導(dǎo)致災(zāi)區(qū)內(nèi)外溝通不暢，外界一時(shí)無(wú)法了解災(zāi)區(qū)情況，災(zāi)區(qū)幾乎霎時(shí)成了“信息孤島”,各種救援一時(shí)難以展開，由此而錯(cuò)過(guò)了“黃金救援時(shí)間”。AWSN可以實(shí)現(xiàn)快速部署和近距離偵察，能夠及時(shí)準(zhǔn)確地為實(shí)現(xiàn)有效的救援獲取災(zāi)區(qū)的第一手現(xiàn)場(chǎng)數(shù)據(jù)，從而提高救援的成功率。因?yàn)楹玫腁WSN部署算法可以節(jié)省大量部署時(shí)間、節(jié)約節(jié)點(diǎn)能量、獲得更準(zhǔn)確的現(xiàn)場(chǎng)數(shù)據(jù)，所以部署算法的研究一直是研究的熱點(diǎn)。面對(duì)災(zāi)難救援中復(fù)雜搜索路徑進(jìn)行三維空間節(jié)點(diǎn)部署則更具挑戰(zhàn)性。本研究提出了一種基于“引力曲線”的空中復(fù)雜路徑自主部署算法，該算法能夠根據(jù)應(yīng)急救援中路徑搜索的實(shí)際需要，實(shí)現(xiàn)對(duì)三維空間復(fù)雜路徑的自主部署。

1 相關(guān)工作

針對(duì)動(dòng)態(tài)節(jié)點(diǎn)部署問(wèn)題，最早的研究始于對(duì)機(jī)器人的路徑規(guī)劃。近年來(lái)，研究學(xué)者已提出了多種方法和策略，Wang等[7]提出了多種應(yīng)用計(jì)算幾何方法實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)自主部署的算法，Du等提出了一種基于網(wǎng)格密度的部署算法[8]。

1986年Khatib提出了人工勢(shì)場(chǎng)(artificial potential field，APF)法，該方法在機(jī)器人控制及路徑規(guī)劃領(lǐng)域被廣泛使用[9]，由于該方法可使傳感器節(jié)點(diǎn)根據(jù)實(shí)際環(huán)境生成路徑，系統(tǒng)的適應(yīng)性得到顯著提高，避障性能大大增強(qiáng)。Howard等[10]在2002年率先提出應(yīng)用人工勢(shì)場(chǎng)方法實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)的自部署，這種部署可使每個(gè)移動(dòng)節(jié)點(diǎn)都受到其他節(jié)點(diǎn)的作用力及環(huán)境中的障礙物的斥力，類似靜電場(chǎng)中帶電粒子運(yùn)動(dòng)時(shí)的受力，在各個(gè)力的共同作用下，節(jié)點(diǎn)得以在部署環(huán)境中擴(kuò)散展開。

在人工勢(shì)場(chǎng)理論基礎(chǔ)上發(fā)展起來(lái)的虛擬力(virtual force，VF)算法[11]能夠自動(dòng)使初始階段聚集的移動(dòng)節(jié)點(diǎn)快速分散，自適應(yīng)地動(dòng)態(tài)調(diào)整節(jié)點(diǎn)疏密情況，該方法已經(jīng)成為當(dāng)前用于移動(dòng)節(jié)點(diǎn)部署優(yōu)化的典型策略。Zou 等在文獻(xiàn)[12]中提出了虛擬力算法的概念，整個(gè)部署過(guò)程模擬了物理學(xué)中的分子間作用力——范德華力。陶丹等[13]應(yīng)用虛擬力算法，提出了一種基于虛擬勢(shì)場(chǎng)的有向節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法。該算法通過(guò)引入質(zhì)心的概念，使傳感器節(jié)點(diǎn)在虛擬力作用下做擴(kuò)散運(yùn)動(dòng)，消除了網(wǎng)絡(luò)中的感知重疊區(qū)和盲區(qū)，進(jìn)而增強(qiáng)了整個(gè)有向節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋。相對(duì)地，Zhao等[14]進(jìn)一步完善了虛擬力算法，引入了負(fù)質(zhì)心的概念。周浦城等[15]提出了一種基于虛擬力的無(wú)線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法。該算法是在人工勢(shì)場(chǎng)思想的基礎(chǔ)上進(jìn)行改進(jìn)，將運(yùn)動(dòng)圖式理論與人工勢(shì)場(chǎng)理論相結(jié)合，通過(guò)節(jié)點(diǎn)間作用力和部署邊界斥力共同作用，調(diào)整整個(gè)網(wǎng)絡(luò)的形態(tài)。

空中無(wú)線傳感網(wǎng)(AWSN)一直受到帶載平臺(tái)穩(wěn)定性、能量、負(fù)載額度等條件的限制，但伴隨著相關(guān)技術(shù)的發(fā)展，空中無(wú)線傳感網(wǎng)已在環(huán)境監(jiān)測(cè)方面取得了巨大進(jìn)步。例如，奧地利亞德里亞綜合大學(xué)的 Wischounig-Strucl 等[16]利用空間傳感器網(wǎng)絡(luò)構(gòu)建了區(qū)域視頻監(jiān)控系統(tǒng)；Watai等[17]應(yīng)用空中無(wú)線傳感網(wǎng)系統(tǒng)監(jiān)測(cè)大氣中的二氧化碳濃度，以便對(duì)突發(fā)的異常情況做出緊急響應(yīng)。

如上所述，以上算法在實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)自主部署方面都有積極的貢獻(xiàn)，但每一種方法都存在其優(yōu)缺點(diǎn)和適用條件。同時(shí)，大部分方法都是針對(duì)以區(qū)域空間為探測(cè)目標(biāo)所提出的，對(duì)于節(jié)點(diǎn)覆蓋目標(biāo)是一條路徑的情況，上述算法很難進(jìn)行精確的部署。為此，本文結(jié)合災(zāi)難救援的需要，在現(xiàn)有虛擬力算法的基礎(chǔ)上提出了一種適于空中無(wú)線傳感器網(wǎng)絡(luò)的能夠?qū)θS空間復(fù)雜路徑進(jìn)行精確覆蓋的自主部署算法，簡(jiǎn)稱三維空間復(fù)雜路徑自主部署算法。

2 復(fù)雜路徑自主部署算法模型

2.1 假設(shè)與定義

首先做出如下假設(shè)和定義：

假設(shè)1：通過(guò)算法可以計(jì)算出每個(gè)節(jié)點(diǎn)自身的位置，并得到確定的坐標(biāo)信息。

假設(shè)2：節(jié)點(diǎn)的通信半徑為Rc，當(dāng)兩個(gè)節(jié)點(diǎn)間的直線距離dij小于或等于節(jié)點(diǎn)本身的通信半徑Rc時(shí)，這兩個(gè)節(jié)點(diǎn)互為彼此的鄰居節(jié)點(diǎn)，互相之間可以通信。

假設(shè)3：通信半徑Rc內(nèi)能量連續(xù)，通信半徑外通訊能量為0。

定義1：節(jié)點(diǎn)模型為[O(x, y, z), Rm，Rk，Rc，F(xiàn)max]。其中O(x, y, z)為節(jié)點(diǎn)部署在空間中的三維坐標(biāo)值，x、y、z分別為直角坐標(biāo)系中X軸、Y軸、Z軸的坐標(biāo)值；Rm為節(jié)點(diǎn)間產(chǎn)生相互碰撞的最小半徑，簡(jiǎn)稱為最小半徑；Rk為平衡半徑，當(dāng)兩個(gè)節(jié)點(diǎn)間的直線距離等于平衡半徑時(shí)，節(jié)點(diǎn)受到對(duì)方的作用力為0；Rc為通信半徑；Fmax為節(jié)點(diǎn)間距離小于最小半徑Rm時(shí)所受到的最大的斥力。

定義2：節(jié)點(diǎn)覆蓋目標(biāo)路徑曲線模型為[f(x, y, z)LimD P(x, y, z)]，式中，f(x, y, z)為曲線的一般方程，Lim表示曲線在空間區(qū)域的x、y、z軸坐標(biāo)的極大和極小值的集合{xmaxxminymaxyminzmaxzmin}，用以限定所有節(jié)點(diǎn)的最大部署范圍。d為任一節(jié)點(diǎn)到達(dá)目標(biāo)曲線內(nèi)所有數(shù)據(jù)元素的距離集合，設(shè)其中最短的距離為D，在目標(biāo)路徑上得到最短距離所對(duì)應(yīng)點(diǎn)的坐標(biāo)則為P。

2.2 作用力模型

空中無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)受到三種類型的作用力，下面進(jìn)行簡(jiǎn)要分析。

首先，基于群體智能思想，將可移動(dòng)的空中無(wú)線傳感器節(jié)點(diǎn)看作是帶電的微粒，物理學(xué)中的帶電微粒之間存在引力和斥力。將無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)假設(shè)為電場(chǎng)中的微粒，那么節(jié)點(diǎn)之間就存在電場(chǎng)力的作用，其受力類型取決于兩個(gè)節(jié)點(diǎn)之間的距離。節(jié)點(diǎn)間的受力表現(xiàn)為引力時(shí)，說(shuō)明兩個(gè)節(jié)點(diǎn)間的距離過(guò)遠(yuǎn)；相反，如果兩個(gè)無(wú)線傳感器節(jié)點(diǎn)間的受力表現(xiàn)為斥力時(shí)，說(shuō)明節(jié)點(diǎn)間的距離過(guò)近。

其次，在實(shí)際應(yīng)用環(huán)境中必定存在障礙物，節(jié)點(diǎn)會(huì)受到障礙物對(duì)它的作用力，為了避免節(jié)點(diǎn)與障礙物發(fā)生碰撞而引起設(shè)備損壞或網(wǎng)絡(luò)癱瘓，設(shè)定監(jiān)測(cè)目標(biāo)區(qū)域中的障礙物對(duì)節(jié)點(diǎn)產(chǎn)生斥力。

最后，目標(biāo)路徑會(huì)對(duì)節(jié)點(diǎn)產(chǎn)生作用力。為了能夠使節(jié)點(diǎn)準(zhǔn)確地覆蓋在目標(biāo)路徑上，本文提出了“引力曲線”的概念，將目標(biāo)路徑轉(zhuǎn)變成一條具有引力作用的曲線。這樣既保證了節(jié)點(diǎn)不會(huì)因過(guò)分偏離目標(biāo)路徑而無(wú)法實(shí)現(xiàn)覆蓋作用，同時(shí)也能夠提高覆蓋率的準(zhǔn)確度，更好地完成信息監(jiān)測(cè)任務(wù)。

一般采用矢量表示節(jié)點(diǎn)所受到的作用力，節(jié)點(diǎn)所受到的合力就是各個(gè)作用力的矢量疊加?？罩袩o(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)在合力的作用下實(shí)時(shí)對(duì)自己的位置進(jìn)行移動(dòng)和調(diào)整，當(dāng)節(jié)點(diǎn)受力等于零或者達(dá)到移動(dòng)距離上限時(shí)，節(jié)點(diǎn)則停止移動(dòng)。節(jié)點(diǎn)在三種類型的受力作用下，實(shí)現(xiàn)自主部署，完成對(duì)目標(biāo)路徑的有效覆蓋。

2.2.1 節(jié)點(diǎn)間作用力

將空中無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的集合假設(shè)為一個(gè)包含力F和質(zhì)量m等參數(shù)的虛擬物理系統(tǒng)，各個(gè)節(jié)點(diǎn)之間均可以產(chǎn)生引力或斥力，每個(gè)節(jié)點(diǎn)i受到來(lái)自鄰居節(jié)點(diǎn)j的作用力。節(jié)點(diǎn)i移動(dòng)的方向和距離取決于該無(wú)線傳感器節(jié)點(diǎn)的自身位置、自身的質(zhì)量mi及其所受鄰居節(jié)點(diǎn)的引力與斥力的合力Fi等參數(shù)。節(jié)點(diǎn)間距離在通信半徑Rc范圍之內(nèi)的節(jié)點(diǎn)間存在相互作用力，包括斥力和引力。斥力和引力的大小則取決于節(jié)點(diǎn)間的距離，距離決定力的性質(zhì)。存在一距離Rk，當(dāng)節(jié)點(diǎn)間距離大于Rk時(shí)它們之間的作用力表現(xiàn)為引力，使得節(jié)點(diǎn)相互靠近；當(dāng)節(jié)點(diǎn)間距離小于Rk時(shí)它們之間的作用力表現(xiàn)為斥力，使得節(jié)點(diǎn)相互遠(yuǎn)離；當(dāng)節(jié)點(diǎn)間距離恰好等于Rk時(shí)，節(jié)點(diǎn)間作用力等于0。這樣的設(shè)定能夠使節(jié)點(diǎn)之間的距離收斂于距離Rk。而距離Rk在此算法中設(shè)定為節(jié)點(diǎn)的平衡半徑。

如圖1所示，空間三維圖中有節(jié)點(diǎn)A到節(jié)點(diǎn)F共6個(gè)節(jié)點(diǎn)。其中，A節(jié)點(diǎn)最小半徑為Rm，平衡半徑為Rk，通信半徑為Rc。

圖1 節(jié)點(diǎn)間距離關(guān)系與受力圖

任意兩個(gè)節(jié)點(diǎn)間距離與受力分析如下：

(1) 圖1中的節(jié)點(diǎn)A和B間的距離滿足dAB=Rm(最小半徑)時(shí)，兩節(jié)點(diǎn)即將發(fā)生碰撞，此時(shí)節(jié)點(diǎn)間的作用力表現(xiàn)為斥力且達(dá)到最大為Fmax。

(2) 圖1中的節(jié)點(diǎn)A和C間的距離滿足Rm

(3) 圖1中的節(jié)點(diǎn)A和D間的距離滿足dAD=Rk時(shí)，節(jié)點(diǎn)間的引力和斥力相等，合力為0。

(4) 圖1中的節(jié)點(diǎn)A和E間的距離滿足Rk

(5) 圖1中的節(jié)點(diǎn)A和F間的距離滿足dAF>Rc時(shí)，兩節(jié)點(diǎn)間的作用力為0，認(rèn)為不存在引力和斥力。

節(jié)點(diǎn)間所受引力Fα和斥力Fτ的公式如下：

(1)

(2)

其中，Rm為最小半徑；Rk為平衡半徑；Rc為通信半徑，通常設(shè)Rm≤Rk≤ Rc；α=10， β=12( α, β為增益系數(shù)，為獲得最大增益，根據(jù)經(jīng)驗(yàn)，取α=10, β=12)。

2.2.2 障礙物作用力

如前文所述，空中無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅受到節(jié)點(diǎn)間作用力的影響，在實(shí)際應(yīng)用環(huán)境中還會(huì)受到監(jiān)測(cè)目標(biāo)區(qū)域內(nèi)障礙物對(duì)節(jié)點(diǎn)的作用力。由于在節(jié)點(diǎn)部署的路徑之中不可避免地會(huì)有一些不可預(yù)知的障礙物影響節(jié)點(diǎn)的運(yùn)動(dòng)，倘若節(jié)點(diǎn)與障礙物發(fā)生相撞則會(huì)引起不必要的損失，因此將障礙物的作用力定義為斥力。設(shè)定障礙物會(huì)對(duì)所有節(jié)點(diǎn)產(chǎn)生斥力，斥力的大小也由節(jié)點(diǎn)與障礙物之間的距離決定[10]。示意圖如圖2所示。

圖2 節(jié)點(diǎn)障礙物斥力示意圖

障礙物O擁有其本身的斥力場(chǎng)范圍，當(dāng)節(jié)點(diǎn)A運(yùn)動(dòng)至該范圍之內(nèi)時(shí)，會(huì)受到由障礙物O指向節(jié)點(diǎn)A的斥力，斥力的大小由下式計(jì)算得出：

(3)

其中，dAO為節(jié)點(diǎn)與障礙物之間的距離，L為障礙物斥力場(chǎng)范圍半徑，即節(jié)點(diǎn)受到障礙物斥力作用的有效距離；通常，α定義為大于10的整數(shù)；β=12，使節(jié)點(diǎn)在部署中和障礙物之間能夠保持相對(duì)安全的距離。

2.2.3 目標(biāo)路徑的作用力

為了實(shí)現(xiàn)節(jié)點(diǎn)對(duì)目標(biāo)路徑的有效覆蓋率，提出“引力曲線”的概念，即目標(biāo)路徑會(huì)對(duì)每一個(gè)節(jié)點(diǎn)產(chǎn)生引力，在此引力的作用下使得節(jié)點(diǎn)自主向目標(biāo)路徑移動(dòng)，實(shí)現(xiàn)對(duì)目標(biāo)路徑的覆蓋。

對(duì)任意一節(jié)點(diǎn)A，總能夠找到一條到達(dá)目標(biāo)路徑的最短路徑，其最短距離定義為D。最短路徑所對(duì)應(yīng)的目標(biāo)路徑上的點(diǎn)，定義為節(jié)點(diǎn)在曲線上的投影點(diǎn)P。為此，對(duì)目標(biāo)路徑曲線進(jìn)行有限點(diǎn)分割，搜索距離節(jié)點(diǎn)A最近的分割點(diǎn)設(shè)定為投影點(diǎn)P，投影點(diǎn)P與節(jié)點(diǎn)A間存在引力作用，且引力由投影點(diǎn)P指向節(jié)點(diǎn)A。投影點(diǎn)對(duì)節(jié)點(diǎn)產(chǎn)生引力作用，使得節(jié)點(diǎn)在移動(dòng)過(guò)程中能夠始終沿“最短路徑”不斷接近目標(biāo)路徑，最終完成對(duì)目標(biāo)路徑的覆蓋，示意圖如圖3所示。

圖3 目標(biāo)路徑對(duì)節(jié)點(diǎn)的作用力計(jì)算示意圖

節(jié)點(diǎn)受到引力曲線的引力的大小由下式計(jì)算得出：

(4)

其中，dAP為節(jié)點(diǎn)與垂足點(diǎn)之間的距離，D為節(jié)點(diǎn)到達(dá)目標(biāo)的“最短路徑”；通常，α定義為大于10的整數(shù)；β=12，使節(jié)點(diǎn)能夠最終到達(dá)目標(biāo)路徑。

3 三維空間復(fù)雜路徑自主部署算法

基于上述建立的算法模型，建立三維空間復(fù)雜路徑自主部署算法。該算法是一個(gè)分布式算法，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都并發(fā)執(zhí)行相同的算法，且節(jié)點(diǎn)的移動(dòng)是同步并發(fā)進(jìn)行的。該算法描述如下：

初始化節(jié)點(diǎn)i部署區(qū)域范圍{xmaxxminymaxyminzmaxzmin}；

初始化移動(dòng)距離步長(zhǎng)△d，時(shí)間步長(zhǎng)△t；

獲得目標(biāo)路徑的曲線方程φ(x, y, z)；

While(1)

{

搜索節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)；

按式(1)，式(2)計(jì)算節(jié)點(diǎn)i所受鄰居節(jié)點(diǎn)的引力的合力Fai，所有斥力合力Fri；

搜索節(jié)點(diǎn)i附近的所有障礙物；

按式(3)計(jì)算節(jié)點(diǎn)i所受所有障礙物的斥力的合力Foi；

計(jì)算節(jié)點(diǎn)i的投影點(diǎn)Pi；

按式(4)計(jì)算節(jié)點(diǎn)i受到的投影點(diǎn)引力Fpi；

計(jì)算節(jié)點(diǎn)i所受所有作用力的合力

Fi=Fai+ Fri +Foi +Fpi；

if (Fi==0)

StopandWait(△t);//本輪不移動(dòng)

else

按合力方向移動(dòng)一個(gè)步長(zhǎng)距離△d；

}

其中，節(jié)點(diǎn)i所受鄰居節(jié)點(diǎn)作用力計(jì)算過(guò)程如圖4所示。

圖4 節(jié)點(diǎn)受鄰居節(jié)點(diǎn)作用力計(jì)算過(guò)程

4 實(shí)驗(yàn)仿真與結(jié)果分析

為了檢驗(yàn)本算法的有效性，本節(jié)采取兩組實(shí)驗(yàn)來(lái)進(jìn)行驗(yàn)證，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。第一組實(shí)驗(yàn)?zāi)繕?biāo)路徑為一條較為簡(jiǎn)單的正弦曲線，第二組實(shí)驗(yàn)的目標(biāo)路徑為一條較為復(fù)雜空間螺旋曲線。每組實(shí)驗(yàn)中，首先利用未加入“引力曲線”的基礎(chǔ)虛擬力算法對(duì)目標(biāo)路徑進(jìn)行部署，然后利用加入“引力曲線”的部署算法對(duì)目標(biāo)路徑進(jìn)行節(jié)點(diǎn)覆蓋，最后對(duì)比分析算法的有效性。

本文采用具有代表性的部署性能度量指標(biāo)：路徑覆蓋率和路徑均勻度。

路徑覆蓋率的定義是：所有節(jié)點(diǎn)覆蓋路徑的總面積與目標(biāo)路徑面積的比值，該值一般小于或等于1，其計(jì)算公式如下

(5)

其中Ai代表節(jié)點(diǎn)i的感知覆蓋范圍；Rs為節(jié)點(diǎn)的感知半徑，一般取2Rs≤Rk；A代表整個(gè)覆蓋區(qū)域的面積，n表示節(jié)點(diǎn)數(shù)。

均勻度用以衡量節(jié)點(diǎn)部署的均衡性，起到了平衡能量負(fù)載的作用。一般由節(jié)點(diǎn)間距離的標(biāo)準(zhǔn)差表示，標(biāo)準(zhǔn)差越小，均勻度越小，即節(jié)點(diǎn)覆蓋的均勻性越好，其計(jì)算公式如下：

(6)

其中Ki代表節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù)，Dij表示節(jié)點(diǎn)i和j的距離，Mi表示節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)的平均距離，n表示節(jié)點(diǎn)數(shù)。

4.1 在正弦曲線上的部署仿真

4.1.1 仿真實(shí)例

在本組實(shí)驗(yàn)中，在三維空間內(nèi)隨機(jī)產(chǎn)生30個(gè)節(jié)點(diǎn)，部署目標(biāo)路徑為一條正弦曲線。圖5(a)是節(jié)點(diǎn)初始狀態(tài)，圖5(b)為節(jié)點(diǎn)最終部署狀態(tài)，圖5(c)為算法部署過(guò)程(其中藍(lán)色線表示節(jié)點(diǎn)的移動(dòng)路徑，粉色圓球表示節(jié)點(diǎn)初始位置，紅色圓球表示節(jié)點(diǎn)最終部署位置)。

(a) 節(jié)點(diǎn)初始部署狀態(tài)

(b) 節(jié)點(diǎn)最終部署狀態(tài)

(c) 節(jié)點(diǎn)的移動(dòng)路徑

4.1.2 性能分析

圖6所示為正弦曲線在節(jié)點(diǎn)個(gè)數(shù)不同時(shí)，通過(guò)基礎(chǔ)虛擬力算法(以下簡(jiǎn)稱未改進(jìn)算法)和加入了“引力曲線”的算法(以下簡(jiǎn)稱改進(jìn)算法)所得到仿真結(jié)果的路徑覆蓋率曲線和路徑均勻度曲線。

如圖6(a)所示，改進(jìn)算法所達(dá)到的節(jié)點(diǎn)覆蓋率明顯優(yōu)于未改進(jìn)算法。特別是在改進(jìn)算法的仿真中當(dāng)節(jié)點(diǎn)個(gè)數(shù)等于10時(shí)，覆蓋率值高達(dá)為1，雖然隨著節(jié)點(diǎn)數(shù)目的增加覆蓋率有所減小，但整體覆蓋效果良好，覆蓋率值較高并趨于穩(wěn)定；未改進(jìn)算法則因只通過(guò)節(jié)點(diǎn)間虛擬力的作用完成部署，最終導(dǎo)致節(jié)點(diǎn)充斥在整個(gè)空間區(qū)域，不能準(zhǔn)確地覆蓋目標(biāo)路徑，造成覆蓋率較低。隨著節(jié)點(diǎn)數(shù)目的增加覆蓋率稍有提高，原因是空間區(qū)域內(nèi)節(jié)點(diǎn)覆蓋目標(biāo)路徑的隨機(jī)性概率增大。

如圖6(b)所示，改進(jìn)算法所獲得的路徑均勻度明顯優(yōu)于未改進(jìn)算法，且不會(huì)由于節(jié)點(diǎn)數(shù)目的變化而影響其穩(wěn)定性，始終保持在0.1左右。未改進(jìn)算法的均勻度會(huì)隨著節(jié)點(diǎn)個(gè)數(shù)的增多而越來(lái)越小，原因是個(gè)數(shù)的增多使得每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)密度變大，增大了相互之間的虛擬力作用，從而使節(jié)點(diǎn)可以較為均勻地部署在目標(biāo)區(qū)域。

(a) 路徑覆蓋率曲線

(b) 路徑均勻度

圖7所示為正弦曲線在節(jié)點(diǎn)數(shù)量固定在30個(gè)時(shí)，未改進(jìn)算法和改進(jìn)算法所得到的路徑覆蓋率隨節(jié)點(diǎn)部署時(shí)長(zhǎng)的變化曲線。結(jié)果顯示改進(jìn)算法明顯優(yōu)于未改進(jìn)算法，且會(huì)在較短時(shí)間內(nèi)快速得到較優(yōu)覆蓋率，響應(yīng)速度較快。

圖7 路徑覆蓋率隨時(shí)間變化曲線

4.2 在螺旋曲線上的部署仿真

4.2.1 仿真實(shí)例

在本組實(shí)驗(yàn)中，在三維空間內(nèi)設(shè)置隨機(jī)產(chǎn)生100個(gè)節(jié)點(diǎn)，部署目標(biāo)為一條螺旋曲線。圖8(a)是節(jié)點(diǎn)初始狀態(tài)，圖8(b)為節(jié)點(diǎn)最終部署狀態(tài)，圖8(c)為算法部署過(guò)程 (其中藍(lán)色線表示節(jié)點(diǎn)的移動(dòng)路徑，粉色圓球表示節(jié)點(diǎn)初始位置，紅色圓球表示節(jié)點(diǎn)最終部署位置)。

4.2.2 性能分析

圖9所示為螺旋曲線在節(jié)點(diǎn)個(gè)數(shù)不同時(shí)，未改進(jìn)算法和改進(jìn)算法所得到仿真結(jié)果的覆蓋率曲線和均勻度曲線。

如圖9(a)所示，改進(jìn)算法的節(jié)點(diǎn)覆蓋率值接近等于1，基本實(shí)現(xiàn)對(duì)目標(biāo)路徑的完全覆蓋，覆蓋效果遠(yuǎn)遠(yuǎn)好于未改進(jìn)算法。

如圖9(b)所示，改進(jìn)算法所獲得的節(jié)點(diǎn)均勻度優(yōu)于未改進(jìn)算法，雖然目標(biāo)路徑復(fù)雜使得節(jié)點(diǎn)覆蓋均勻性有所降低，但隨著節(jié)點(diǎn)個(gè)數(shù)的增加覆蓋效果有所提高。

圖10所示為空間螺旋曲線在節(jié)點(diǎn)個(gè)數(shù)固定在50個(gè)時(shí)，未改進(jìn)算法和改進(jìn)算法所得到的路徑覆蓋率隨節(jié)點(diǎn)部署時(shí)長(zhǎng)的變化曲線。對(duì)比圖7可以看出，改進(jìn)算法在復(fù)雜曲線的節(jié)點(diǎn)覆蓋響應(yīng)速度慢于簡(jiǎn)單曲線，但是也可以在得到較高覆蓋率。

(a) 節(jié)點(diǎn)初始部署狀態(tài)

(b) 節(jié)點(diǎn)最終部署狀態(tài)

(c) 節(jié)點(diǎn)的移動(dòng)路徑

(a) 路徑覆蓋率對(duì)比

(b) 路徑均勻度對(duì)比

圖10 路徑覆蓋率隨時(shí)間變化曲線

5 結(jié) 論

本文提出了一種基于“引力曲線”的空中無(wú)線傳感器網(wǎng)絡(luò)復(fù)雜路徑自主部署算法，與只適用于區(qū)域空間部署的傳統(tǒng)的虛擬力算法相比，該算法針對(duì)應(yīng)急救援中路徑搜索的實(shí)際需要，實(shí)現(xiàn)了對(duì)三維空間復(fù)雜路徑的自主部署。仿真實(shí)驗(yàn)結(jié)果表明，該算法可明顯改善部署性能。

[ 1] Pakzad S N, Fenves G L, Kim S, et al. Design and implementation of scalable wireless sensor network for structural monitoring. American Society of Civil Engineers, 2014, 14(1):89-101

[ 2] Nadeem A, Hussain M A, Owais O, et al. Application specific study, analysis and classification of body area wireless sensor network applications. Computer Networks, 2015, 83: 363-380

[ 3] Anisi M H, Abdul-Salaam G, Abdullah A H. A survey of wireless sensor network approaches and their energy consumption for monitoring farm fields in precision agriculture. Precision Agriculture, 2014, 16(2):216-238

[ 4] Costa F G, Ueyama J, Colombo A, et al. The use of unmanned aerial vehicles and wireless sensor networks for spraying pesticides. Journal of Systems Architecture, 2014, 60(4):393-404

[ 5] Ueyama J, Freitas H, Faical B S, et al. Exploiting the use of unmanned aerial vehicles to provide resilience in wireless sensor networks. IEEE Communications Magazine, 2014, 52(12):81-87

[ 6] Ahmed N, Kanhere S S, Jha S. Link characterization for aerial wireless sensor networks. In: Proceedings of the 2011 IEEE GLOBECOM Workshops (GC Wkshps), Houston, USA, 2011.1274-1279

[ 7] Wang X W, Shen Y, Wu J R, et al. A k-coverage algorithm in three dimensional wireless sensor networks. In: Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology (IC-BNMT), Beijing, China, 2010. 1089-1093

[ 8] Du X, Lin F. Improving sensor network performance by deploying mobile sensors. In: Proceedings of the 24th IEEE International Conference on Performance, Computing and Communications, Phoenix, USA, 2005. 67-71

[ 9] 方華京, 魏然. 人工勢(shì)場(chǎng)法在多機(jī)器人運(yùn)動(dòng)中的研究. 控制工程, 2007, 14(2): 115-117

[10] Howard A, Mataric M J, Sukhatme G S. Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In: Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems, Fukuoka, Japan, 2002. 299-308

[11] Zou Y, Charkrabarty K. Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems, 2014, 3(1): 61-91

[12] Zou Y, Chakrabarty K. Sensor deployment and target localization based on virtual forces. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, San Francisco, USA, 2003, 2: 1293-1303

[13] 陶丹,馬華東,劉亮. 基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法. 軟件學(xué)報(bào), 2007,18(5): 1152-1163

[14] Zhao J, Zeng J C. A virtual potential field based coverage algorithm for directional networks. In: Proceedings of the 21st Annual International Conference on Chinese Control & Decision Conference, Guilin, China, 2009. 4590- 4595

[15] 周浦城,崔遜學(xué),王書敏等. 基于虛擬力的無(wú)線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法. 系統(tǒng)仿真學(xué)報(bào), 2009 (5): 1416-1419

[16] Wischounig-Strucl D, Quartisch M, Rinner B. Prioritized data transmission in airborne camera networks for wide area surveillance and image mosaicking. In: Proceedings of the 2011 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), Colorado Springs, USA, 2011. 17-24

[17] Watai T, Machida T, Ishizaki N, et al. A lightweight observation system for atmospheric carbon dioxide concentration using a small unmanned aerial vehicle. Journal of Atmospheric & Oceanic Technology, 2006, 23(5):700-710

Research on complex path self-deployment for aerial wireless sensor networks

Jiao Yaoyao, Tan Li, Su Weijun, Yang Minghua, Hu Jipeng

(School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048)

To realize the monitoring of the complex path of a target in a real environment, a virtual force based three-dimensional complex path self-deployment algorithm for aerial wireless sensor networks was proposed. The algorithm innovatively adopts the “gravity-curve” generated by the complex path to build the virtual force field, thus the nodes in a wireless sensor network can accomplish the coverage of the target path adaptively. The simulation results showed that, compared with traditional virtual force algorithms, the proposed algorithm achieved the faster deployment process as well as the higher path coverage faster, and reach and evenness.

aerial wireless sensor network (AWSN), three-dimensional deployment, complex path, virtual force

10.3772/j.issn.1002-0470.2016.01.012

① 國(guó)家自然科學(xué)基金(61402022)，北京市自然科學(xué)基金(4132025)，北京市青年英才計(jì)劃(YETP1448)和北京市哲學(xué)社科規(guī)劃(14JGB033)資助項(xiàng)目。

2015-07-01)

② 女，1991年生，碩士生；研究方向：無(wú)線傳感網(wǎng)技術(shù)；聯(lián)系人，E-mail:jiaoyaoyao11@126.com(