三维无线传感器网络寿命和动态路由算法*

李 超，韩江洪，2

(1.合肥工业大学 计算机与信息学院，安徽 合肥230009;2.安全关键工业测控技术教育部工程研究中心，安徽 合肥230009)

0 引 言

三维无线传感器网络(wireless sensor networks，WSNs)是由部署在三维空间中执行一定感知任务的传感器节点组成的无线网络系统［1］。如用于空气质量监测的传感器网络，负责煤矿井下安全的传感器网络、部署在建筑物各层的传感器网络等［2～5］。由于地形起伏，即便是布设在地面上的传感器网络也并非如理论假设那样处在同一个平面上［6］。

部署在野外或大型建筑物各层的无线传感器网络因长期工作在无源环境，主要能量来源是一次性电池供电，导致无线传感器网络所能工作的时间是非常有限的［7］。

无线能量传输(wireless energy transmission，WET)技术的发展和应用使定期对无线传感器网络节点能量补给提供了可能。早在1901 年，Nikola Tesla 就开始研究无线能量转化技术［8］。Kurs A 于2007 年发表在《Science》杂志上的研究使通过强耦合磁共振方式进行零损失的无线能量传输变为可能［9］。

在三维空间内，有源基站B 周围随机分布若干无线传感器节点。基站B 负责接收各传感器节点发来的信息。与基站B 欧氏距离小于ε 的节点由基站对其进行无线充电。无线充电设备(wireless charging device，WCD)负责给网络中的其他节点进行充电。WCD 从维护站S 出发，以一定的顺序遍历三维无线传感器网络中的每个节点，为三维无线传感器网络中的节点进行充电，WCD 遍历完所有节点后就回到维护站S 休整。本文以WCD 最大驻站时间比(WCD 休整时间与运行一个周期的比值)为优化目标建立最优化模型，获取最优的WCD 的遍历路径、充电策略和路由方案，提高整个三维无线传感器网络的寿命。

1 连续时变模型

假设被监测的三维空间内随机分布N 个传感器节点，记为集合N，集合U 表示与中心基站B 的欧氏距离小于或等于ε 的所有节点;集合T 表示所有与中心基站B 欧氏距离大于ε 的节点。每个传感器节点的电池容量为Emax，节点正常工作所需的能量最小值为Emin。

假设网络中的节点i(i∈N)产生监测数据的速率为Ri。t 时刻节点i 向节点j 和基站B 发送的数据速率分别为dij(t)和diB(t)，那么，在t 时刻网络中的任意节点i(i∈N)应满足

节点i(i∈N)发送信息或接收信息都需要消耗的能量。记Pi(t)为节点i 在t 时刻消耗的功率，对网络中的节点i(i∈T)有

在式(2)中，ρ 为节点接收单位数据消耗的能量，Cij和CiB分别为节点i 向节点j 或者基站B 发送单位数据所消耗的能量。WCD 从S 出发，移动速度为v，以恒定功率P 向节点i 进行充电，充电时长为τi，然后移动至下一个节点。令WCD 在维护站的时间为τvac，行走时间为τisp，网络中所有节点一次完整充电周期为τ。

对于T 集合中的任意节点i，剩余能量最低和最高分别出现在ti和ti+τi时刻。此时，有

综合约束条件(1)～(5)和优化目标max τvac/τ 可得网络的连续时变模型OPT—A。

仔细观察OPT—A 可以发现，各约束条件中节点来自不同的集合。为了简化OPT—A 的约束问题，引入位置指代参数zi，OPT—A 中的式(2)、式(3)、式(4)可以简化为

此时，连续时变模型OPT—A 就简化了以max τvac/τ 为优化目标，以式(1)、式(5)～式(8)为约束条件的简化连续时变模型OPT—B。

2 连续时变模型的简化

2.1 离散T+1 阶段非线性模型

在一个充电周期内，WCD 有行走、驻站和充电三种状态。在充电状态，将一个充电周期τ 分为T+1 个阶段。前T 个阶段分别对应对网络中T 个节点进行充电的过程，第T+1 阶段对应行走和驻站状态，令Ω={1，2，…，T+1}，表示在一个充电周期内所有阶段的集合，令dij(ω)，diB(ω)分别为第ω 阶段节点i 向节点j 或基站B 发送数据的速率;pi(ω)为节点i 在第ω 阶段消耗的功率;τω为第ω 阶段经历的时间。可以证明:dij(t)，diB(t)，pi(t)不随时间变化，对OPT—B 的优化结果不会造成影响，所以，有

定理 OPT—C 问题最优解对应的WCD 的最优遍历路径构成三维空间内最短Hamilton 回路。

对定理的证明采用反证法，假设OPT—C 问题的一个最优解对应的WCD 遍历路径不构成三维空间内最短Hamilton 回路，然后构造一个新的可行解，其对应的最优路径构成三维空间Hamilton 回路，最后证明构造的可行解的优化目标值要优于先前假设的最优解的优化目标值，即与假设矛盾，定理成立。

2.2 离散T+1 阶段线性模型

仔细观察优化问题OPT—C 可以发现，OPT—C 并不是线性规划问题。对于乘积项zidki(ω)，ziCijdij(ω)来说，被监测的三维空间内传感器节点布撒完成后，距离指代参数zi的 值 为 定 值，对 于 比 例 项，令，并代入优化问题OPT—C 得

经过上述运算和推导，OPT—C 问题已经变为以式(14)～式(17)为约束条件，max θvacω 为优化目标的离散T+1 阶段线性规划模型OPT—D。

3 系统仿真

3.1 仿真参数

在1 000 m×1 000 m×1 000 m 的正方体区域内，随机布撒20 个传感器节点构成三维无线传感器网络。其中，整个网络中节点i(i∈N)的数据产生速率Ri为1～20 kbit/s 的随机整数。维护站S 的位置为坐标原点，基站坐落于正方体区域的几何中心处，其他仿真参数如下［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 仿真结果

通过遗传算法求解获得此20 个节点的最短Hamilton回路。为了使三维路径更加直观，将三维路径图标注在含有等高线的二维图中，WCD 的最佳遍历路径如图1 所示。

图1 20 节点WCD 三维最短Hamilton 回路图Fig 1 WCD 3D the shortest Hamilton loop for 20 nodes

通过求解OPT—D 问题得到WCD 移动的路径长度Dλ=6 719.6 m，充电周期τ=8 343.23 s，驻站时间τvac=4 907.92 s，驻站比θvac=58.83%。在充电周期(1)内，WCD经三维空间内最短Hamilton 路径到达12#节点时，此节点的剩余电量仅为542.98 J，已逼近最小值Emin=540 J，所以，12#节点为网络中的瓶颈节点。

通过求解OPT—D 问题发现，网络在不同阶段所采用的路由策略不同。网络的第1 阶段的路由信息如图2(a)所示。在第1 阶段，12#节点向距基站B 距离小于10 m 的20#节点发送数据。在第12 阶段12#节点直接向基站B 发送监测数据。尽管向20#节点发送数据会节省部分能量，但在第12 阶段12#节点正在进行充电，有足够的能量向基站B 发送数据。

图2 20 节点三维无线传感器网络路由信息示意图Fig 2 3D WSNs routing information for 20 nodes

通过仿真结果可以看出:虽然网络中确实存在瓶颈节点，但由于WCD 周期地利用WET 技术对瓶颈节点能量的及时补充，可使瓶颈节点在能量快速恢复的同时获得更强的数据发送能力，确保3D 无线传感器网络持续工作。

4 结束语

本文将WET 技术应用于三维无线传感器网络节点能量补给的问题中，提出了连续时变的最优化问题模型OPT—A，并简化为离散T+1 阶段线性问题模型OPT—D。证明WCD 遍历网络中节点的最优路径为最短三维Hamilton 回路。仿真结果表明:本文给出的最优充电策略和路由方案可使三维无线传感器网络持续工作。

［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，Fitzpatrick 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］ 刘华峰，金士尧.三维传感器网络空间结构及其覆盖特性［J］.计算机应用，2007，27(4):909－912.

［7］ 陈正宇，杨 庚，陈 蕾，等.基于压缩感知的WSNs 长生命周期数据收集方法［J］.电子与信息学报，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.