移動傳感網絡在3D場景中的最小耗能移動策略

吳月菲+徐向華

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

摘 要： 結合3D場景中移動傳感網絡的能耗模型和視距概率傳感器模型，研究了在滿足目標覆蓋要求時移動傳感網絡的最小能耗移動問題，分析了窮舉法、貪心算法和模擬退火算法各自的優劣。模擬實驗結果表明，近似最優解可以在可接受的時間內得到。

關鍵詞： 移動傳感網絡； 視距傳感模型； 概率傳感模型； 3D場景

中圖分類號：TP393.0 文獻標志碼：A 文章編號：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 引言

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

本文結合視線傳感器的探測特性和實際的地理情況，提出了一種在能夠保證目標檢測要求的同時，使得移動傳感網絡的總能耗最小的移動方案。

1 問題模型

1.1 問題場景模型

本文研究的問題是，初始給定N個隨機部署的可移動的視距概率傳感器，移動它們，從而對M個目標進行檢測。并且，在保證對目標的檢測率不小于預設值θ時，使得移動傳感網絡的總能耗E最小。

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

2 解決方案

2.1 兩點間的最小能耗

我們為地理模型建立一張有向加權圖：①為每一個數據點建立一個頂點；②為每對相鄰的數據點之間添加一對有向邊；③每條有向邊的權值為從一個數據點移動到另一個數據點的移動能耗。那么，從一個區域移動到另一個區域所需的最小移動能耗問題，就轉化為有向加權圖中的最短路徑的問題。本文使用Dijkstra算法求解這個問題。

2.2 求近似最優解

當整個區域中存在一些目標時，根據式⑸，可以計算出區域中每個數據點對這些目標的檢測概率。

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

使用能耗矩陣求解最優解時，需要從n個傳感器中選取m個，來分別覆蓋m個不同的目標。因此，求解的復雜度為。這是一個無法在多項式時間內得到最優解的NP問題。當傳感網絡更為復雜，如一個目標可以同時被多個傳感器共同檢測時，最優解的求解也會變得更加復雜。

因此，在問題規模較小時，本文求出最優解，但當問題規模較大時，則選擇求出移動能耗盡量小的近似解。另外，本文只考慮在傳感器與目標一一對應時的情況。

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