三維無線傳感器網(wǎng)絡(luò)壽命和動(dòng)態(tài)路由算法*

李 超，韓江洪，2

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009;2.安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，安徽 合肥230009)

0 引 言

三維無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是由部署在三維空間中執(zhí)行一定感知任務(wù)的傳感器節(jié)點(diǎn)組成的無線網(wǎng)絡(luò)系統(tǒng)［1］。如用于空氣質(zhì)量監(jiān)測(cè)的傳感器網(wǎng)絡(luò)，負(fù)責(zé)煤礦井下安全的傳感器網(wǎng)絡(luò)、部署在建筑物各層的傳感器網(wǎng)絡(luò)等［2～5］。由于地形起伏，即便是布設(shè)在地面上的傳感器網(wǎng)絡(luò)也并非如理論假設(shè)那樣處在同一個(gè)平面上［6］。

部署在野外或大型建筑物各層的無線傳感器網(wǎng)絡(luò)因長(zhǎng)期工作在無源環(huán)境，主要能量來源是一次性電池供電，導(dǎo)致無線傳感器網(wǎng)絡(luò)所能工作的時(shí)間是非常有限的［7］。

無線能量傳輸(wireless energy transmission，WET)技術(shù)的發(fā)展和應(yīng)用使定期對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量補(bǔ)給提供了可能。早在1901 年，Nikola Tesla 就開始研究無線能量轉(zhuǎn)化技術(shù)［8］。Kurs A 于2007 年發(fā)表在《Science》雜志上的研究使通過強(qiáng)耦合磁共振方式進(jìn)行零損失的無線能量傳輸變?yōu)榭赡埽?］。

在三維空間內(nèi)，有源基站B 周圍隨機(jī)分布若干無線傳感器節(jié)點(diǎn)。基站B 負(fù)責(zé)接收各傳感器節(jié)點(diǎn)發(fā)來的信息。與基站B 歐氏距離小于ε 的節(jié)點(diǎn)由基站對(duì)其進(jìn)行無線充電。無線充電設(shè)備(wireless charging device，WCD)負(fù)責(zé)給網(wǎng)絡(luò)中的其他節(jié)點(diǎn)進(jìn)行充電。WCD 從維護(hù)站S 出發(fā)，以一定的順序遍歷三維無線傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，為三維無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行充電，WCD 遍歷完所有節(jié)點(diǎn)后就回到維護(hù)站S 休整。本文以WCD 最大駐站時(shí)間比(WCD 休整時(shí)間與運(yùn)行一個(gè)周期的比值)為優(yōu)化目標(biāo)建立最優(yōu)化模型，獲取最優(yōu)的WCD 的遍歷路徑、充電策略和路由方案，提高整個(gè)三維無線傳感器網(wǎng)絡(luò)的壽命。

1 連續(xù)時(shí)變模型

假設(shè)被監(jiān)測(cè)的三維空間內(nèi)隨機(jī)分布N 個(gè)傳感器節(jié)點(diǎn)，記為集合N，集合U 表示與中心基站B 的歐氏距離小于或等于ε 的所有節(jié)點(diǎn);集合T 表示所有與中心基站B 歐氏距離大于ε 的節(jié)點(diǎn)。每個(gè)傳感器節(jié)點(diǎn)的電池容量為Emax，節(jié)點(diǎn)正常工作所需的能量最小值為Emin。

假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)i(i∈N)產(chǎn)生監(jiān)測(cè)數(shù)據(jù)的速率為Ri。t 時(shí)刻節(jié)點(diǎn)i 向節(jié)點(diǎn)j 和基站B 發(fā)送的數(shù)據(jù)速率分別為dij(t)和diB(t)，那么，在t 時(shí)刻網(wǎng)絡(luò)中的任意節(jié)點(diǎn)i(i∈N)應(yīng)滿足

節(jié)點(diǎn)i(i∈N)發(fā)送信息或接收信息都需要消耗的能量。記Pi(t)為節(jié)點(diǎn)i 在t 時(shí)刻消耗的功率，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)i(i∈T)有

在式(2)中，ρ 為節(jié)點(diǎn)接收單位數(shù)據(jù)消耗的能量，Cij和CiB分別為節(jié)點(diǎn)i 向節(jié)點(diǎn)j 或者基站B 發(fā)送單位數(shù)據(jù)所消耗的能量。WCD 從S 出發(fā)，移動(dòng)速度為v，以恒定功率P 向節(jié)點(diǎn)i 進(jìn)行充電，充電時(shí)長(zhǎng)為τi，然后移動(dòng)至下一個(gè)節(jié)點(diǎn)。令WCD 在維護(hù)站的時(shí)間為τvac，行走時(shí)間為τisp，網(wǎng)絡(luò)中所有節(jié)點(diǎn)一次完整充電周期為τ。

對(duì)于T 集合中的任意節(jié)點(diǎn)i，剩余能量最低和最高分別出現(xiàn)在ti和ti+τi時(shí)刻。此時(shí)，有

綜合約束條件(1)～(5)和優(yōu)化目標(biāo)max τvac/τ 可得網(wǎng)絡(luò)的連續(xù)時(shí)變模型OPT—A。

仔細(xì)觀察OPT—A 可以發(fā)現(xiàn)，各約束條件中節(jié)點(diǎn)來自不同的集合。為了簡(jiǎn)化OPT—A 的約束問題，引入位置指代參數(shù)zi，OPT—A 中的式(2)、式(3)、式(4)可以簡(jiǎn)化為

此時(shí)，連續(xù)時(shí)變模型OPT—A 就簡(jiǎn)化了以max τvac/τ 為優(yōu)化目標(biāo)，以式(1)、式(5)～式(8)為約束條件的簡(jiǎn)化連續(xù)時(shí)變模型OPT—B。

2 連續(xù)時(shí)變模型的簡(jiǎn)化

2.1 離散T+1 階段非線性模型

在一個(gè)充電周期內(nèi)，WCD 有行走、駐站和充電三種狀態(tài)。在充電狀態(tài)，將一個(gè)充電周期τ 分為T+1 個(gè)階段。前T 個(gè)階段分別對(duì)應(yīng)對(duì)網(wǎng)絡(luò)中T 個(gè)節(jié)點(diǎn)進(jìn)行充電的過程，第T+1 階段對(duì)應(yīng)行走和駐站狀態(tài)，令Ω={1，2，…，T+1}，表示在一個(gè)充電周期內(nèi)所有階段的集合，令dij(ω)，diB(ω)分別為第ω 階段節(jié)點(diǎn)i 向節(jié)點(diǎn)j 或基站B 發(fā)送數(shù)據(jù)的速率;pi(ω)為節(jié)點(diǎn)i 在第ω 階段消耗的功率;τω為第ω 階段經(jīng)歷的時(shí)間。可以證明:dij(t)，diB(t)，pi(t)不隨時(shí)間變化，對(duì)OPT—B 的優(yōu)化結(jié)果不會(huì)造成影響，所以，有

定理 OPT—C 問題最優(yōu)解對(duì)應(yīng)的WCD 的最優(yōu)遍歷路徑構(gòu)成三維空間內(nèi)最短Hamilton 回路。

對(duì)定理的證明采用反證法，假設(shè)OPT—C 問題的一個(gè)最優(yōu)解對(duì)應(yīng)的WCD 遍歷路徑不構(gòu)成三維空間內(nèi)最短Hamilton 回路，然后構(gòu)造一個(gè)新的可行解，其對(duì)應(yīng)的最優(yōu)路徑構(gòu)成三維空間Hamilton 回路，最后證明構(gòu)造的可行解的優(yōu)化目標(biāo)值要優(yōu)于先前假設(shè)的最優(yōu)解的優(yōu)化目標(biāo)值，即與假設(shè)矛盾，定理成立。

2.2 離散T+1 階段線性模型

仔細(xì)觀察優(yōu)化問題OPT—C 可以發(fā)現(xiàn)，OPT—C 并不是線性規(guī)劃問題。對(duì)于乘積項(xiàng)zidki(ω)，ziCijdij(ω)來說，被監(jiān)測(cè)的三維空間內(nèi)傳感器節(jié)點(diǎn)布撒完成后，距離指代參數(shù)zi的 值 為 定 值，對(duì) 于 比 例 項(xiàng)，令，并代入優(yōu)化問題OPT—C 得

經(jīng)過上述運(yùn)算和推導(dǎo)，OPT—C 問題已經(jīng)變?yōu)橐允?14)～式(17)為約束條件，max θvacω 為優(yōu)化目標(biāo)的離散T+1 階段線性規(guī)劃模型OPT—D。

3 系統(tǒng)仿真

3.1 仿真參數(shù)

在1 000 m×1 000 m×1 000 m 的正方體區(qū)域內(nèi)，隨機(jī)布撒20 個(gè)傳感器節(jié)點(diǎn)構(gòu)成三維無線傳感器網(wǎng)絡(luò)。其中，整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)i(i∈N)的數(shù)據(jù)產(chǎn)生速率Ri為1～20 kbit/s 的隨機(jī)整數(shù)。維護(hù)站S 的位置為坐標(biāo)原點(diǎn)，基站坐落于正方體區(qū)域的幾何中心處，其他仿真參數(shù)如下［10］:Emax=1.2 V×2.5 A×3 600 s=10.8 kJ，ε=10 m，Emin=5%Emax=540 J，v=20 m/s，U=20 W，ρ=540 nJ/bit，(φ1=540 nJ/bit，φ2=0.001 3 pJ/(bit·m4))。

3.2 仿真結(jié)果

通過遺傳算法求解獲得此20 個(gè)節(jié)點(diǎn)的最短Hamilton回路。為了使三維路徑更加直觀，將三維路徑圖標(biāo)注在含有等高線的二維圖中，WCD 的最佳遍歷路徑如圖1 所示。

圖1 20 節(jié)點(diǎn)WCD 三維最短Hamilton 回路圖Fig 1 WCD 3D the shortest Hamilton loop for 20 nodes

通過求解OPT—D 問題得到WCD 移動(dòng)的路徑長(zhǎng)度Dλ=6 719.6 m，充電周期τ=8 343.23 s，駐站時(shí)間τvac=4 907.92 s，駐站比θvac=58.83%。在充電周期(1)內(nèi)，WCD經(jīng)三維空間內(nèi)最短Hamilton 路徑到達(dá)12#節(jié)點(diǎn)時(shí)，此節(jié)點(diǎn)的剩余電量?jī)H為542.98 J，已逼近最小值Emin=540 J，所以，12#節(jié)點(diǎn)為網(wǎng)絡(luò)中的瓶頸節(jié)點(diǎn)。

通過求解OPT—D 問題發(fā)現(xiàn)，網(wǎng)絡(luò)在不同階段所采用的路由策略不同。網(wǎng)絡(luò)的第1 階段的路由信息如圖2(a)所示。在第1 階段，12#節(jié)點(diǎn)向距基站B 距離小于10 m 的20#節(jié)點(diǎn)發(fā)送數(shù)據(jù)。在第12 階段12#節(jié)點(diǎn)直接向基站B 發(fā)送監(jiān)測(cè)數(shù)據(jù)。盡管向20#節(jié)點(diǎn)發(fā)送數(shù)據(jù)會(huì)節(jié)省部分能量，但在第12 階段12#節(jié)點(diǎn)正在進(jìn)行充電，有足夠的能量向基站B 發(fā)送數(shù)據(jù)。

圖2 20 節(jié)點(diǎn)三維無線傳感器網(wǎng)絡(luò)路由信息示意圖Fig 2 3D WSNs routing information for 20 nodes

通過仿真結(jié)果可以看出:雖然網(wǎng)絡(luò)中確實(shí)存在瓶頸節(jié)點(diǎn)，但由于WCD 周期地利用WET 技術(shù)對(duì)瓶頸節(jié)點(diǎn)能量的及時(shí)補(bǔ)充，可使瓶頸節(jié)點(diǎn)在能量快速恢復(fù)的同時(shí)獲得更強(qiáng)的數(shù)據(jù)發(fā)送能力，確保3D 無線傳感器網(wǎng)絡(luò)持續(xù)工作。

4 結(jié)束語

本文將WET 技術(shù)應(yīng)用于三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量補(bǔ)給的問題中，提出了連續(xù)時(shí)變的最優(yōu)化問題模型OPT—A，并簡(jiǎn)化為離散T+1 階段線性問題模型OPT—D。證明WCD 遍歷網(wǎng)絡(luò)中節(jié)點(diǎn)的最優(yōu)路徑為最短三維Hamilton 回路。仿真結(jié)果表明:本文給出的最優(yōu)充電策略和路由方案可使三維無線傳感器網(wǎng)絡(luò)持續(xù)工作。

［1］ Villas L A，Guidoni D L，Ueyama J.3D localization in wireless sensor networks using unmanned aerial vehicle［C］∥2013 12th IEEE International Symposium on Network Computing and Applications(NCA)，IEEE，2013:135－142.

［2］ Chaurasiya V K，Jain N，Nandi G C.A novel distance estimation approach for 3D localization in wireless sensor networks using multi dimensional scaling［J］.Information Fusion，2014，15:5－18.

［3］ Aziz A A，Sekercioglu Y A，F(xiàn)itzpatrick P，et al.A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks［J］.Communications Surveys＆Tutorials，IEEE，2013，15(1):121－144.

［4］ Pan M S，Tsai C H，Tseng Y C.Emergency guiding and monitoring applications in indoor 3D environments by wireless sensor networks［J］.International Journal of Sensor Networks，2006，1(1):2－10.

［5］ Culler D E，Mulder H.Smart sensors to network the world［J］.Scientific American，2004，290(6):84－91.

［6］ 劉華峰，金士堯.三維傳感器網(wǎng)絡(luò)空間結(jié)構(gòu)及其覆蓋特性［J］.計(jì)算機(jī)應(yīng)用，2007，27(4):909－912.

［7］ 陳正宇，楊 庚，陳 蕾，等.基于壓縮感知的WSNs 長(zhǎng)生命周期數(shù)據(jù)收集方法［J］.電子與信息學(xué)報(bào)，2014，36(10):2343－2349.

［8］ Issa A F，Messer J，Tobias J M.Methods and systems for wireless energy and data transmission:US，7，960，867［P］.2011—06—14.

［9］ Kurs A，Karalis A，Moffatt R，et al.Wireless power transfer via strongly coupled magnetic resonances［J］.Science，2007，317(5834):83－86.

［10］Zimmerling M，Dargie W，Reason J M.Energy－efficient routing in linear wireless sensor networks［C］∥IEEE Internatonal Conference on Mobile Ad－Hoc and Sensor Systems，MASS 2007，IEEE，2007:1－3.