移動(dòng)傳感網(wǎng)絡(luò)在3D場景中的最小耗能移動(dòng)策略

吳月菲+徐向華

DOI：10.16644/j.cnki.cn33-1094/tp.2016.07.003

摘 要： 結(jié)合3D場景中移動(dòng)傳感網(wǎng)絡(luò)的能耗模型和視距概率傳感器模型，研究了在滿足目標(biāo)覆蓋要求時(shí)移動(dòng)傳感網(wǎng)絡(luò)的最小能耗移動(dòng)問題，分析了窮舉法、貪心算法和模擬退火算法各自的優(yōu)劣。模擬實(shí)驗(yàn)結(jié)果表明，近似最優(yōu)解可以在可接受的時(shí)間內(nèi)得到。

關(guān)鍵詞： 移動(dòng)傳感網(wǎng)絡(luò)； 視距傳感模型； 概率傳感模型； 3D場景

中圖分類號(hào)：TP393.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）07-08-04

Minimum energy mobile strategy of mobile sensor networks in 3D scene

Wu Yuefei， Xu Xianghua

（College of Computer Science and Technology， Hangzhou Dianzi University， Zhejiang Provincial Key Lab of Data Storage and Transmission Technology， Hangzhou， Zhejiang 310037， China）

Abstract： Combined with the energy consumption model and the sight-probabilistic sensor model of mobile sensor networks in 3D scene， the minimum mobile energy consumption in mobile sensor networks after meeting the target coverage requirements is studied. The exhaustive method， greedy algorithm and simulated annealing algorithm are analyzed for the respective advantages and disadvantages. The simulation results show that the approximate optimal solution can be obtained within an acceptable time.

Key words： mobile sensor network； sight sensing model； probabilistic sensing model； 3D scene

0 引言

無線傳感網(wǎng)絡(luò)廣泛應(yīng)用于軍事、智能交通、環(huán)境監(jiān)控等多個(gè)領(lǐng)域。其中，傳感器的能量是一個(gè)亟待解決的問題。如果要使無線傳感網(wǎng)絡(luò)的工作時(shí)間最大化，就必須減少無線傳感網(wǎng)絡(luò)的能量消耗。雖然，目前已經(jīng)有很多關(guān)于概率傳感器的模型[1-3]，但是，考慮實(shí)際應(yīng)用時(shí)傳感網(wǎng)絡(luò)產(chǎn)生移動(dòng)能耗的文章并不多。文獻(xiàn)[4-6]研究了移動(dòng)傳感器在二維平面下的移動(dòng)能耗問題，但是沒有考慮到在實(shí)際中傳感器移動(dòng)時(shí)重力勢(shì)能的影響。

本文結(jié)合視線傳感器的探測特性和實(shí)際的地理情況，提出了一種在能夠保證目標(biāo)檢測要求的同時(shí)，使得移動(dòng)傳感網(wǎng)絡(luò)的總能耗最小的移動(dòng)方案。

1 問題模型

1.1 問題場景模型

本文研究的問題是，初始給定N個(gè)隨機(jī)部署的可移動(dòng)的視距概率傳感器，移動(dòng)它們，從而對(duì)M個(gè)目標(biāo)進(jìn)行檢測。并且，在保證對(duì)目標(biāo)的檢測率不小于預(yù)設(shè)值θ時(shí)，使得移動(dòng)傳感網(wǎng)絡(luò)的總能耗E最小。

假定，所使用的視線傳感器都安裝在可移動(dòng)設(shè)備（如履帶小車）上，它們距離地面有一定高度zs。我們使用符號(hào)Si（xi，yi，zi+zs）表示第i個(gè)傳感器的信息，其中（xi，yi，zi+zs）為第i個(gè)傳感器的三維坐標(biāo)位置。S={S1，S2，…，Sn}表示傳感網(wǎng)絡(luò)中所有傳感器的集合。Tj（xj，yj，zj）表示第j個(gè)目標(biāo)的信息，其中（xj，yj，zj）為第T個(gè)目標(biāo)的實(shí)際位置。T={T1，T2，...，Tm}表示所有目標(biāo)的集合。

2 解決方案

2.1 兩點(diǎn)間的最小能耗

我們?yōu)榈乩砟Ｐ徒⒁粡堄邢蚣訖?quán)圖：①為每一個(gè)數(shù)據(jù)點(diǎn)建立一個(gè)頂點(diǎn)；②為每對(duì)相鄰的數(shù)據(jù)點(diǎn)之間添加一對(duì)有向邊；③每條有向邊的權(quán)值為從一個(gè)數(shù)據(jù)點(diǎn)移動(dòng)到另一個(gè)數(shù)據(jù)點(diǎn)的移動(dòng)能耗。那么，從一個(gè)區(qū)域移動(dòng)到另一個(gè)區(qū)域所需的最小移動(dòng)能耗問題，就轉(zhuǎn)化為有向加權(quán)圖中的最短路徑的問題。本文使用Dijkstra算法求解這個(gè)問題。

2.2 求近似最優(yōu)解

當(dāng)整個(gè)區(qū)域中存在一些目標(biāo)時(shí)，根據(jù)式⑸，可以計(jì)算出區(qū)域中每個(gè)數(shù)據(jù)點(diǎn)對(duì)這些目標(biāo)的檢測概率。

若考慮一個(gè)目標(biāo)只被一個(gè)傳感器檢測的情況，由上一小節(jié)的計(jì)算結(jié)果和式⑸所解得的傳感器所處位置對(duì)目標(biāo)的檢測概率的大小，可以求出傳感器Si在保證對(duì)目標(biāo)Tj的檢測概率不低于預(yù)設(shè)值θj時(shí)，所需的移動(dòng)最小能耗MinEij。那么，我們可以得到一個(gè)N行M列的能耗矩陣，行列號(hào)分別代表傳感器和目標(biāo)的序號(hào)。

使用能耗矩陣求解最優(yōu)解時(shí)，需要從n個(gè)傳感器中選取m個(gè)，來分別覆蓋m個(gè)不同的目標(biāo)。因此，求解的復(fù)雜度為。這是一個(gè)無法在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解的NP問題。當(dāng)傳感網(wǎng)絡(luò)更為復(fù)雜，如一個(gè)目標(biāo)可以同時(shí)被多個(gè)傳感器共同檢測時(shí)，最優(yōu)解的求解也會(huì)變得更加復(fù)雜。

因此，在問題規(guī)模較小時(shí)，本文求出最優(yōu)解，但當(dāng)問題規(guī)模較大時(shí)，則選擇求出移動(dòng)能耗盡量小的近似解。另外，本文只考慮在傳感器與目標(biāo)一一對(duì)應(yīng)時(shí)的情況。

本文提出三種求可行解的方案：①窮舉所有可行解，得出最優(yōu)解；②使用貪心算法得出可行解；③使用模擬退火算法求近似解。