基于能量预测的分簇可充电无线传感器网络充电调度

引用本文

董颖, 崔梦瑶, 吴昊, 王雨后. 基于能量预测的分簇可充电无线传感器网络充电调度[J].吉林大学学报（工学版）, 2018,48(4): 1265-1273
DONG Ying, CUI Meng-yao, WU Hao, WANG Yu-hou. Clustering wireless rechargeable sensor networks charging schedule based on energy prediction[J]. Journal of Jilin University Engineering and Technology Edition, 2018,48(4): 1265-1273 复制到剪切板

Doi:10.13229/j.cnki.jdxbgxb20170524
Permissions

基于能量预测的分簇可充电无线传感器网络充电调度

董颖, 崔梦瑶, 吴昊, 王雨后

吉林大学通信工程学院,长春 130012

作者简介:董颖(1971-),女,副教授,博士.研究方向:无线传感器网络.E-mail:dongying@jlu.edu.cn

基金:国家自然科学基金项目(61107040); 吉林省科技发展计划项目(20180101042JC).

摘要

为及时对可充电无线传感器网络中的“饥饿”节点补充能量,提出了一种基于预测的分簇低能量路径移动充电算法(CLP)。网络采用非均匀分簇的多跳路由协议,每个簇选取能量最低的节点作为簇头节点,移动充电车仅为簇头节点充电并收集簇内节点的能量信息。每次充电调度完成后,移动充电车将所收集的能量信息发送至基站,基站根据马尔科夫模型预测各簇内节点的能耗,以优化选取下一次的充电目标。仿真结果表明,采用CLP算法比旅行商问题(TSP)算法的网络效用提高约20%,数据传输能力提高约17%。

关键词: 通信技术; 可充电无线传感器网络; 能量预测; 非均匀分簇; 马尔科夫模型

中图分类号:TN92 文献标志码:A 文章编号:1671-5497(2018)04-1265-09

Clustering wireless rechargeable sensor networks charging schedule based on energy prediction

DONG Ying, CUI Meng-yao, WU Hao, WANG Yu-hou

College of Communication Engineering, Jilin University, Changchun 130012, China

Abstract

To timely complete the energy supply for the “hungry” sensors in Wireless Rechargeable Sensor Networks (WRSNs), a cluster and low-energy route mobile charging algorithm, called Clustering Low-energy access Prediction (CLP), is proposed based on energy prediction. The WRSN adopts the unequal clustering and multiple-hops routing protocol, and it chooses the node with the lowest energy in each cluster as the head node of that cluster. The mobile charger provides energy just for the cluster head nodes and collects the energy information of sensors of each cluster. After each round of the charging schedule, the mobile charger sends the energy message to the base station, and the base station adopts the Markov model to forecast the energy consumption of the sensors in each cluster in order to optimize the selection of charging target for next new charging schedule. Compared with TSP algorithm network, the results of the simulation show that CLP algorithm can improve the network utility by nearly 20%, and the ability of data transmission of nodes is increased by nearly 17%.

Keyword: communication technology; wireless rechargeable sensor networks(WRSNs); energy prediction; unequal clustering; Markov model

文章图片

0 引言

近年来, 无线传感器网络(Wireless sensor networks, WSNs)由于其优越的感知、计算和通信能力在环境检测、目标追踪、灾害救援等领域得到了迅速的发展^[1]。传统WSNs中使用的是电池能量有限且不可补充的传感器节点, 以往的研究经常是通过改进能量路由协议^[2]、MAC协议^[3]或拓扑控制^[4]等方法来降低节点的能耗, 并不能从根本上解决WSNs的能量问题。阻碍WSNs长期工作的首要因素依旧是由于大量节点能量耗尽而导致网络死亡。

为了弥补节点能量受限方面的缺憾, 各国研究学者采用了多种能量获取方案来实现对传感器节点能量的补充, 例如从太阳、风、潮汐和周围环境的无线电中获取能量等^[5], 但是这些能量的获取方式不可人为控制, 而且较低的充电效率并不能保证网络的长期运行。2007年麻省理工学院的Kurs等^[6]证明了磁耦合共振方式实现无线能量传输的可行性, 这为WSNs能量获取问题的解决带来一线曙光。伴随着无线能量传输技术的日益成熟, 越来越多的学者陆续加入到对可充电无线传感器网络(Wireless rechargeable sensor networks, WRSNs)的可行性研究中^[7]。有学者提出可以利用移动充电车(Mobile charger, MC)以磁耦合共振的方式为部署在复杂环境下的传感器节点提供稳定且持续的能量供给, 来维持WRSNs的长时间运行^[8]。由于网络内MC的充电能力往往受限, 一次充电调度中可携带的能量需要满足自身移动的能耗及对其他传感器节点无线充电的能耗之和, 充电任务需要权衡充电节点的个数和充电路径的长度, 因此合理地安排充电调度对提高MC的充电效率起着至关重要的作用。

目前, 大多数研究采用单MC的充电方案, 通过设计合理的充电调度来最大化网络效用或最小化充电代价。文献[9]采用一种基于能量循环再生的充电调度, 以最大化无线充电车(Wireless charging vehicle, WCV)在每个充电周期中的休息比例为目标, 并证明了最短哈密顿回路可作为WCV的最佳旅行路径。在此基础上, 作者进一步提出了联合优化问题, 通过约束每个节点的数据流量和充电时间对优化问题进行求解, 最终该问题被确定为NP难问题。文献[10]在能量补给设备兼任数据采集设备的情况下, 提出了一种基于时变动态拓扑模型的充电调度方案, 并在此基础上以最大化能量补给设备的驻站时间比为目标提出了最优化问题。Xie等^[11]在蜂窝结构的充电网络中通过先离散化后线性化的数学方法, 联合优化了旅行路径、节点流量控制以及充电时间等问题, 并求解出最佳的调度安排。

此外, 可充电网络也可采用多MC同时充电的工作方式, 这些MC之间相互配合以实现最小化充电代价。文献[12]中首次提出了一种新的充电模式:协同移动充电。在一维的WRSNs中, 多个MC不仅可以为传感器节点充电, MC之间也可进行能量的传递。作者以最小化MC移动消耗的能量为目标, 证明了在固定数目的移动节点条件下, 协作式的充电方式可以覆盖更多的充电节点。文献[13]在文献[12]的实验基础上进一步构造了最小权重的哈密顿回路, 并将其应用到二维的WRSNs中。

在现有关于WRSNs充电调度的文献中, 一般MC在网络中周期性地按既定路径访问, 实现了最短的访问路径和较少的旅行时间。然而在动态监测网络中由于传感器节点工作状态不一致, 其能耗速率也不完全相同, 在规定路径上可能会访问到一些能量充足的节点, 这不仅加重了MC的充电任务, 也延长了能耗较快的节点的充电等待时间以及MC最终将能耗消息发送至基站的时延。本文为合理安排网络内的充电调度以实现最大化网络效用, 在每一次调度中只对最亟需能量的传感器节点充电, 提出一种基于预测的分簇低能量路径移动充电算法(Clustering low energy access prediction, CLP)。算法首先对整个WRSNs网络进行非均匀分簇, 同时选取网络中的“ 饥饿” 节点— — 能耗最快的簇头节点作为充电目标。之后, MC按节点能量从低到高的顺序依次对节点充电。最后, 在新的充电调度开始之前, 基站采用马尔科夫模型对MC充电离开之后节点的能耗做出预测, 并规划出新的充电路径。

1 网络模型

1.1 WRSNs网络结构

图1为采用CLP算法的WRSNs网络结构图。网络内包括若干个可充电传感器节点, 负责从周围环境中采集并传输数据; 一个移动充电车MC, 为节点提供能量并收集节点的能量信息; 监测区域外有一个位置已知且固定的基站(Base station, BS), 作为网络中的sink节点负责管理所有节点产生的数据, 安排网络的充电调度以及对MC进行充电维护。

	Figure Option View Download New Window
	图1 采用CLP算法的WRSNs网络结构图Fig.1 WRSNs network structure adopted CLP algorithm

假设作为sink节点的BS能够准确地掌握网络中所有节点的位置信息, 每个传感器节点定期生成监测数据, 并以多跳方式发送数据至sink节点。为提高WRSNs中BS的管理效率, 网络采用非均匀分簇结构, 距离BS较近的簇的簇半径小, 包含的节点也较少; 距离BS较远的簇的簇半径大, 包含的节点也较多, 且每个簇内均以能量最低的节点作为簇头节点。

1.2 CLP算法的基本工作过程

图2为CLP算法的工作流程图。在每一次充电调度开始之前, BS负责将所有簇的簇头节点按能量由低到高的顺序进行排序。MC从BS出发按照已规划好的充电路径遍历每个簇开展充电服务, 并在各个簇内收集节点的能量信息。当一次充电调度完成后, MC返回BS接受充电维护, 并将所收集到的能量信息发送至BS。为准确地找出下一次充电调度中的充电目标, BS采用马尔科夫模型预测MC离开充电节点后簇内各节点的能量消耗。BS根据MC提供的能量信息和各节点的预测能耗计算出下一次的充电规划路径, 并准备开始下一次充电。文中假设MC在新的调度开始时携带充足的能量, 可满足一次调度中的充电需求和自身消耗, 并且MC从基站出发前已获知待充电节点的位置信息和能量信息。

	Figure Option View Download New Window
	图2 CLP算法工作流程图Fig.2 Flow chart of CLP algorithm

1.3 无线能量传输

当MC移动至待充电的簇头节点处为其进行能量补充, 网络中无线能量的传输依据Friis能量传输方程, 如式(1)所示:

$P_{r} = \{\begin{array}{l} \frac{τ}{{(d + β)}^{2}}, d \leq D \\ 0, d > D \end{array}$ (1)

$τ = \frac{G_{s} G_{r} η}{L_{p}} {(\frac{λ}{4 π})}^{2} p_{0}$ (2)

式中: $P_{r}$ 为传感器节点接收到的充电功率; $d$ 为传感器节点与充电器之间的距离; $D$ 为MC可实现充电的最远距离; $τ$ 为常量, 由传感器以及环境的硬件条件决定; $β$ 为短距离传输时Friis自由空间方程的补偿参数, β =0.2316^[5]; $G_{s}$ 为充电器的发射天线增益; $G_{r}$ 为传感器节点的接收天线增益; $η$ 为整流器效率, η =0.125^[5]; $L_{p}$ 为极化损失; $λ$ 为波长; $p_{0}$ 为充电器的充电功率。

2 CLP移动充电算法

2.1 网络非均匀分簇

网络的分簇划分可以保证其能够高效地运行, 如图3所示, 但由于距离sink节点较近的簇头节点承担了更多的数据转发任务, 导致其能耗较快而形成“ 热区” , 非均匀分簇是解决“ 热区” 问题的有效途径^[14]。非均匀分簇是指距离sink节点较近的簇的簇面积较小, 簇头节点承担较少的搜集数据任务; 相对而言, 距离sink节点较远簇的簇面积就相对较大, 可以承担较多的搜集数据任务。

	Figure Option View Download New Window
	图3 CLP算法网络非均匀分簇流程图Fig.3 Flow chart of unequal clustering network adopted CLP algorithm

本文中所采用的非均匀分簇过程如图3所示。网络中的节点采用分布式的竞争算法成簇, 首先依概率在网络中选出部分节点成为候选簇头节点, 参与竞争的普通节点成为簇头节点的概率为 $T, T$ 是预先设定的一个阈值; 未参与竞争的节点进入睡眠状态直到簇头竞争过程结束。竞争节点 $S_{i}$ 根据自身到sink节点的距离计算出以自己为簇头的簇半径, 在竞争过程中, 若某节点 $S_{i}$ 宣布自己竞争获胜, 则在其覆盖范围内的所有其他候选簇头节点就退出竞争, 且不能成为簇头节点, 只能成为普通簇内节点。

2.1.1 簇半径的确定

在网络部署初期, sink节点以固定的功率向网络中所有的传感器节点广播信号; 各节点根据收到信号的强度计算出到sink节点的距离 $d_{r};$ 并由该 $d_{r}$ 值决定拟加入簇的簇半径大小。为保证节点不会因能量消耗过快而死亡, 设定网络中各簇的簇半径大小与 $d_{r}$ 值成正相关, 即越靠近sink节点的簇的簇规模越小, 对应的簇也是由较少量的传感器节点构成。这可以在一定程度上减少簇头节点在本簇内通信和数据融合方面的能量消耗, 从而使其主要负责转发来自于其他簇的信息。

节点 $S_{i}$ 的簇半径 $R_{c}^{i}$ 的计算方法如式(3)所示:

$R_{c}^{i} = (1 + c \frac{d_{r} - d_{\min}}{d_{\max} - d_{\min}}) R_{c}^{0} J$ (3)

式中: $d_{r}$ 代表节点 $S_{i}$ 到sink节点的距离; $d_{\max}$ 和 $d_{\min}$ 分别代表网络中所有节点到sink节点距离的最大值和最小值; $R_{c}^{0}$ 代表候选簇头半径的最小值; $c$ 是控制取值范围的参数, 表示网络预计最大簇半径与最小簇半径的比值, 当 $c = 0$ 时, 就成为均匀分簇, 本文中c=0.6。

2.1.2 簇头节点的确定

在WRSNs中, 对簇头节点的选择至关重要, 它决定着节点的数据收集效率和网络的能量供给效率。每个候选簇头节点都需要维护一个邻簇头集合, 并在这个集合内根据当前各节点剩余能量的高低竞争选出最终的簇头节点, 候选簇头 $S_{i}$ 的邻簇头集合由式(4)确定。

$S_{CH}^{i} = \{S_{j} |S_{j} 是候选簇头, 且 d (S_{i}, S_{j}) < R_{c}^{i}\}$ (4)

在簇头的竞争算法中, 每个节点均以与 $R_{c}^{i}$ 相配合的功率发送广播消息。广播的消息中包括节点 $ID 、$ 竞争半径 $R_{c}^{i}$ 和当前的剩余能量 $RE 。$ 每个节点根据自己收到的广播消息构建自己的邻簇头集合 $S_{CH}^{i},$ 节点根据其邻簇头集合中所有节点的能量做出决策, 然后才能确定自己是否能够担任簇头节点。

为提高网络能量的补充效率, 选举能量最低的候选簇头节点作为最终簇头节点(若簇内能量最低的节点有多个, 则优先选取 $ID$ 最小的节点)。具体做法是, 当候选簇头节点 $S_{i}$ 发现它的剩余能量比其邻簇头集合 $S_{CH}^{i}$ 中其他所有节点的剩余能量都低, 则它将赢得竞选, 并广播获胜消息通知其邻簇头节点。即:当 $S_{j}$ 收到来自 $S_{i}$ 的获胜消息, 且 $S_{i}$ 是 $S_{CH}^{i}$ 中的一个元素, 则 $S_{j}$ 立即退出竞争; 当 $S_{i}$ 收到来自 $S_{j}$ 的退出消息, 且 $S_{j}$ 是 $S_{CH}^{i}$ 中的一个元素, $S_{i}$ 就把 $S_{j}$ 从 $S_{CH}^{i}$ 中删除。

当簇头节点确定后, 未参加竞争的节点从睡眠状态苏醒, 竞争产生的簇头节点向全网广播其竞争获胜的消息, 普通节点选择簇内通信代价最小的簇头节点向其发送加入消息, 通知该簇头节点加入该簇。这样就实现了整个网络的非均匀分簇, 保证了离sink节点近的簇的簇半径小, 离sink节点远的簇的簇半径大。每个簇的簇头节点负责收集本簇内的数据, 并以多跳的形式发送数据至sink节点。

为保证充电时能量的供给效率, 每次都只为簇内能量最低的节点补充能量, 本文算法采用簇头轮换机制, 即MC到达某簇为其簇头节点充满能量之后, 该簇内开始簇头轮换, 选取当前能量最低的节点担任新的簇头。

2.1.3 簇间移动充电

当MC移动到某簇并为簇头节点充电时, 它在该簇的停留时间由待充电节点的初始能量、当前剩余能量和Friis能量传输方程决定。假设网络内的节点都具备相同的初始能量 $E_{0},$ 唯一的 $ID$ 号, 且节点部署之后将不可移动。MC接到充电指令从BS出发开始一次的充电调度, 当到达簇 $C_{j}$ 内为节点 $N_{i}$ 补充能量时, MC在节点 $N_{i}$ 处的停留时间为^[15]:

$α_{i} = \frac{E_{0} - E_{R} (N_{i})}{P_{r} (d_{i})}$ (5)

式中: $E_{0}$ 为节点的初始能量; $E_{R} (N_{i})$ 为MC到达 $N_{i}$ 时节点当前的剩余能量; $d_{i}$ 代表 $N_{i}$ 与MC之间的充电距离; $P_{r} (d_{i})$ 是由Friis能量传输方程得到MC为节点 $N_{i}$ 充电的功率。

当某簇的充电节点 $N_{i}$ 的电量恢复至 $E_{0}$ 时, 该簇内的全部节点向MC发送当前剩余能量信息 $b_{k}$ , MC携带收集到的能量信息移动至下一簇。

2.2 低能量路径访问机制

为及时地对能量较低的“ 饥饿” 节点补充能量, 本文采用低能量路径访问机制来配合MC的簇间移动充电, 以完成每次的充电任务。

首先, 确定待充电节点的充电顺序。在每个已形成的簇内, 簇头节点作为能量最低的节点加入到MC的充电目标序列 $S = {S (1), S (2), \dots, S (n)}$ 中。 $S$ 中的节点按能量由小至大的顺序重新排序, 从而得到待充电节点的充电序列 $S' = {S' (1), S' (2), \dots, S' (n)}$ (若节点电量相同则按 $ID$ 值由小到大的顺序访问)。

其次, 确定充电路径。根据待充电节点的充电序列 $S' = {S' (1), S' (2), \dots, S' (n)},$ 确定MC的充电路径为 $P = {S (0), S' (1), S' (2), \dots, S' (n), S (0)}$ 。其中 $S (0)$ 代表BS, $S' (i) (1 \leq i \leq n)$ 代表路径上第 $i$ 个待充电的节点, 则充电路径的总长度 $D_{p}$ 由式(6)给出。根据此充电路径的长度即可确定MC的旅行能耗。

$D_{p} = D_{S (0) S' (1)} + \overset{n - 1}{\sum_{m = 1}} D_{S' (m) S' (m + 1)} + D_{S' (n) S (0)}$ (6)

式中: $D_{S (0) S' (1)}$ 表示BS至 $S' (1)$ 节点之间的距离; $D_{S' (m) S' (m + 1)}$ 表示节点 $S' (m)$ 至 $S' (m + 1)$ 之间的距离; $D_{S' (n) S (0)}$ 表示节点 $S' (n)$ 至BS之间的距离。

2.3 马尔科夫能量预测模型

待每一次的调度任务完成, MC携带收集的能量信息返回并汇报至BS, 此时网络内节点仍在工作并消耗能量, 此时BS所收到的能量信息并不准确。为了有效地找出下一次调度中的充电目标, 进而获取新的充电路径, 本文采用马尔科夫预测模型^{[16, 17]}预测MC离开充电节点之后的节点能耗。

本文所建立的马尔科夫预测模型中利用马尔可夫链对传感器节点进行预测, 节点的不同工作状态对应马尔可夫链的不同状态。设节点有3种工作模式:

(1)感知模式:当节点处于感知模式的on状态时可以搜集周围环境数据; off状态时不搜集周围环境数据。

(2)通信模式:当节点处于通信模式的receiving状态时可以接收其他节点发送的数据; 处于sending状态时可以发送数据给其他节点; 处于off状态时既不发送数据也不接收数据。

(3)充电模式:当节点处于充电模式的on状态时对节点充电; off状态时不对节点充电。

网络中节点的工作状态如表1所示。当网络中的传感器节点并未开启感知模式时, 节点不会搜集周围环境中的数据, 此时处于X₁状态即最低能耗的休眠状态; 当某些节点开启通信模式时, 负责转发或者接收来自其他节点的感知数据, 分别对应表1中的 $X_{2} 和 X_{3}$ 状态, 此时在单位时间步长内所消耗的能量达到2 nJ; 当MC到达某簇并为簇头节点补充能量时, 该节点即开启充电模式(X₄), 此时在单位时间步长内消耗的能量为0.1 nJ; 当网络中的传感器节点开启感知模式(X₅)时, 就开始搜集周围环境中的数据, 此时在单位时间步长内所消耗的能量为1 nJ; 经过一段固定的时间间隔t之后, 簇头节点查询簇内节点所搜集的信息, 簇内节点接收到查询消息后即做出回复, 将搜集到的信息上传给簇头节点。此时传感器节点同时工作在感知模式和通信模式(X₆和X₇)下, 其单位时间步长内所需的能耗为[3 nJ, 3 nJ]; 当某节点是簇头节点且MC为其充电时, 它同时工作在感知模式和充电模式(X₈)下, 其单位时间步长内所需能耗为1.1 nJ。

表1 节点状态表 Table 1 State of nodes

假设网络中的每个节点都有 $M$ 种工作状态, 因此可以运用马尔科夫链的 $M$ 种状态进行模拟, 此时 $M = {1, 2, \dots, 8} 。$ 在建立的网络模型中, 每个节点在一个单位时间步长内都只能处于一种工作状态, 用 $X_{0}, X_{1}, X_{2}, \dots$ 表示。如果 $X_{n} = i$ 表示节点在第 $n$ 个时间步长时处于状态 $i 。$ 那么假设节点在某个时间步长处于状态 $i,$ 则节点会以一定的概率 $P_{ij}$ 在下一时间步长转化为状态 $j 。$ 这个概率就定义为传感器节点的一步状态转移概率, 用 $P_{ij} = P {X_{m + 1} = j | X_{m} = i}$ 表示。那么, 整个网络的状态转移矩阵可以表示为:

$P_{ij} = |\begin{array}{l} P_{11} & P_{12} & \dots & P_{1 M} \\ P_{21} & P_{22} & \dots & P_{2 M} \\ ︙ & ︙ & ︙ \\ P_{M 1} & P_{M 2} & \dots & P_{MM} \end{array}|$

设 $n$ 步转移概率为当某节点处于状态 $i,$ 经过 $n$ 次状态转移后, 转变状态 $j$ 的为概率 $P_{ij}^{(n)} :$

$P_{ij}^{(n)} = \overset{M}{\sum_{k = 1}} P_{ik}^{r} P_{kj}^{n - r}, 0 < r < n$ (7)

如果某节点处于状态 $i$ , 则它在未来的 $K$ 个时间步长内处于状态 $s$ 的时间步长数为 $\overset{K}{\sum_{t = 1}} P_{is}^{(t)}$ 。

设 $E_{s}$ 为节点在处于状态 $s$ 一个时间步长时所消耗的能量, 因此在 $K$ 个时间步长内预计消耗总能量为:

$E^{K} (i) = \overset{M}{\sum_{s = 1}} (\overset{K}{\sum_{t = 1}} P_{is}^{t}) \times E_{s}$ (8)

式中: $M$ 表示节点的 $M$ 种工作状态, 本文中M=8。

利用式(8), 每个传感器节点均可得出自己的能量消耗率 $Δ E = E^{T} (i) / T, Δ E$ 表示在 $T$ 个时间步长内, 平均每个时间步长节点所消耗的能量。

3 仿真实验与分析

3.1 参数设置

本文采用Matlab软件仿真验证了CLP算法的性能, 表2为网络环境的参数表。在100 m× 100 m的正方形仿真区域内随机布置100个传感器节点, 且不可移动, 所有节点具有相同的初始能量 $E_{0};$ 一个移动充电车MC, 基站每间隔TROUND时间开始一次新的充电调度, MC以速度 $V$ 在网络中完成充电和收集节点能量信息的任务。

表2 网络环境参数表 Table 2 Network environment parameter

参数	含义
area	仿真区域/m	100× 100
$N$	可充电传感器节点个数	100
E₀	节点初始能量/J	0.5
R	节点通信半径/m	15
PacketLength	数据包大小/bit	4000
ctrPacketLength	控制包大小/bit	500
Time-step	单位时间步长/s	0.1
V	MC移动速度/(m· s^-1)	1
TROUND	MC充电维护时间/s	600
Time	运行轮数/轮	1000

表2 网络环境参数表 Table 2 Network environment parameter

实验中分别与EEUC算法和TSP算法^[18]进行了网络效用和数据传输能力的对比分析; 同时深入探讨了CLP算法在几种不同规模网络中完成充电调度所需历经的时长和MC可以达到的充电效率。

3.2 仿真结果分析

3.2.1 网络效用

网络效用:表示经过一定的运行时间后, 当前网络总剩余能量占初始网络总能量的百分比。网络效用值越大表示网络的可利用率越高。

图4为网络效用对比图。从图4可见, EEUC算法在运行至900轮时节点全部死亡, 网络效用降低至0。TSP算法与CLP算法均未出现节点死亡情况, 且各自的网络效用均以较缓慢的速率下降。但是在CLP算法中由于采用了非均匀分簇结构和多跳的路由转发方式, 有效地平衡网络负载, 网络效用下降得更为缓慢; 同时, 在对充电节点的选择方面, BS采用马尔科夫能量预测模型, 保证了MC能够及时地为能量较少的节点充电, 减少了“ 饥饿” 的等待时间, 从而降低网络整体能量的消耗速率。与TSP算法相比, CLP算法的网络效用提高了约20%。

	Figure Option View Download New Window
	图4 网络效用对比图Fig.4 Network utility contrast

3.2.2 数据传输能力

数据传输能力是衡量网络能否长期有效运行的关键指标, 指sink节点随着时间变化所接收到的数据包的个数。图5为CLP和TSP的数据传输能力对比图。从图5可见, 在相同运行轮数的情况下, 采用CLP算法比TSP算法网络所接收数据包数提高约17%。这是由于在CLP算法中采用了簇头轮换机制和低能量路径充电机制, 及时为能量最低的簇头节点补充能量, 从而有效地提高了网络传输数据的能力。由于在WRSNs中采用了TSP算法和CLP算法, 节点的可充电特性保证了网络长时间的正常运行, 因此在上述两种充电网络内sink节点不断地接收来自各簇头节点多跳传输的数据, 即随着时间的增加, sink节点接收数据包的数量保持着线性增长。

	Figure Option View Download New Window
	图5 数据传输能力对比图Fig.5 Data transmission capacity contrast

3.2.3 充电调度时长

图6为3种不同网络环境下MC的充电调度时长对比。从图6可见, 随着网络规模的扩大, 网络内形成簇的数量开始增加, MC的充电任务也随之加重, 即需要访问更多的簇并为簇头节点补充能量, 因此完成一次充电调度需要的时间更长。当网络中有100个节点时, 至多需要约400 s完成一次充电调度, 最少也需要约210 s, 平均需要315 s。而当网络增加到150个节点, 一次调度的时长明显增加至890 s左右, 此时单MC完成整个网络的充电任务已显得力不从心。因此, 随着网络规模的扩大, 需要多MC才能完成充电调度。

	Figure Option View Download New Window
	图6 充电调度时长对比图Fig.6 Time of charging schedule contrast

3.2.4 充电效率

充电效率Q表示在一次充电调度中MC为网络内节点补充的总能量占其自身旅行消耗的能量与为网络补充的总能量之和的百分比。Q值越大, MC的充电效率越高。

$Q = \sum E_{supply} / E_{consume} + \sum E_{supply}$ (9)

式中: $\sum E_{supply}$ 表示在一次充电调度中MC补给网络的总能量; E_consume为MC在一次调度中其自身消耗的能量。

图7为在3种网络环境下MC的充电效率对比图。从图中可见随着网络规模的不断扩大, MC的Q值越小, 这是因为在大规模的网络中MC需要访问更多的簇头节点为其补充能量, 但是由于充电路径的延长而导致MC自身的能耗也在不断增加, 因而降低了MC的充电效率。在100个节点的充电网络中, Q值最高约为67%, 最低约为61%, 平均可达到的充电效率Q为65%。这也说明, 随着网络规模的增大, BS需要分配更多的MC为节点补充能量。

	Figure Option View Download New Window
	图7 MC的充电效率对比图Fig.7 Charging efficiency of MC contrast

4 结束语

本文提出了一种适用于WRSNs的移动充电算法CLP, 通过采用网络非均匀分簇、低能量路径选择和节点能耗预测等方法为单MC分配合理的充电调度。为评价CLP算法的性能, 分别与TSP算法和EEUC算法进行了对比仿真实验。实验结果表明, CLP算法比TSP算法的网络效用提高约20%, 数据传输能力提高约17%。同时也对不同网络规模下的CLP算法作出分析, 当节点数量增加至150个时, 完成一次充电调度所需时长明显增加、其相应的充电效率也显著下降, 说明单MC不能满足较大规模网络的充电需求。下一步将展开对多MC充电调度的研究。

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	Tsai C W, Hong T P, Shiu G N. Metaheuristics for the lifetime of WSN: a review[J]. IEEE Sensors Journal, 2016, 16(9): 2812-2831. [本文引用:1]
[2]	董颖, 苏真真, 周占颖, 等. 一种基于节点剩余能量和位置的LEACH 改进算法[J]. 四川大学学报: 工程科学版, 2015, 47(2): 136-141. Dong Ying, Su Zhen-zhen, Zhou Zhan-ying, et al. An improved LEACH algorithm based on nodes' remaining energy and location[J]. Journal of Sichuan University (Engineering Science Edition), 2015, 47(2): 136-141. [本文引用:1]
[3]	董颖, 周占颖, 苏真真, 等. 基于路由信息的WSN跨层MAC协议[J]. 吉林大学学报: 工学版, 2017, 47(2): 647-654. Dong Ying, Zhou Zhan-ying, Su Zhen-zhen, et al. Cross-layer MAC protocol based on routing information for WSN[J]. Journal of Jilin University (Engineering and Technology Edition), 2017, 47(2): 647-654. [本文引用:1]
[4]	赵继军, 谷志群, 薛亮, 等. WSN中层次型拓扑控制与网络资源配置联合设计方法[J]. 自动化学报, 2015, 41(3): 646-660. Zhao Ji-jun, Gu Zhi-qun, Xue Liang, et al. A joint design method of hierarchical topology control and network resource allocation for wireless sensor networks[J]. Acta Automatica Sinica, 2015, 41(3): 646-660. [本文引用:1]
[5]	He S, Chen J, Jiang F, et al. Energy provisioning in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2013, 12(10): 1931-1942. [本文引用:3]
[6]	Kurs A, Karalis A, Moffatt R, et al. Wireless power transfer via strongly coupled magnetic resonances[J]. Science, 2007, 317(5834): 83-86. [本文引用:1]
[7]	Xie L, Shi Y, Hou Y T, et al. Wireless power transfer and applications to sensor networks[J]. IEEE Wireless Communications, 2013, 20(4): 140-145. [本文引用:1]
[8]	Li K, Luan H, Shen C C. Qi-ferry: energy-constrained wireless charging in wireless sensor networks[C]∥IEEE Wireless Communications and Networking Conference, Shanghai, China, 2012: 2515-2520. [本文引用:1]
[9]	Shi Y, Xie L, Hou Y T, et al. On renewable sensor networks with wireless energy transfer[C]∥Proceedings of IEEE INFOCOM, Shanghai, China, 2011: 1350-1358. [本文引用:1]
[10]	丁煦, 韩江洪, 石雷, 等. 可充电无线传感器网络动态拓扑问题研究[J]. 通信学报, 2015, 36(1): 129-141. Ding Xu, Han Jiang-hong, Shi Lei, et al. Problem of the dynamic topology architecture of rechargeable wireless sensor networks[J]. Journal on Communications, 2015, 36(1): 129-141. [本文引用:1]
[11]	Xie L, Shi Y, Hou Y T, et al. On renewable sensor networks with wireless energy transfer: the multi-node case[C]∥The 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, Seoul, South Korea, 2012: 10-18. [本文引用:1]
[12]	Zhang S, Wu J, Lu S. Collaborative mobile charging for sensor networks[C]∥IEEE 9th International Conference on Mobile Ad hoc and Sensor Systems(MASS), Las Vegas, USA, 2012: 84-92. [本文引用:2]
[13]	Nikoletseas S, Yang Y Y, Georgiadis A. Wireless Power Transfer Algorithms, Technologies and Applications in Ad Hoc Communication Networks[M]. New York: Springer, 2016. [本文引用:1]
[14]	李超良, 胡春华. 无线传感器网络中面向动态多跳的非均匀分簇路由[J]. 中南大学学报: 自然科学版, 2011, 42(7): 226-231. Li Chao-liang, Hu Chun-hua. A dynamic multi-hop non-uniform clustering routing protocol in wireless sensor networks[J]. Journal of Central South University (Science and Technology), 2011, 42(7): 226-231. [本文引用:1]
[15]	Lin C, Wu G, Obaidat M S, et al. Clustering and splitting charging algorithms for large scaled wireless rechargeable sensor networks[J]. Journal of Systems and Software, 2016, 113: 381-394. [本文引用:1]
[16]	Lin K, Xu T, Hassan M M, et al. An energy-efficiency node scheduling game based on task prediction in WSNs[J]. Mobile Networks and Applications, 2015, 20(5): 583-592. [本文引用:1]
[17]	Shen W, Han G, Shu L, et al. A new energy prediction approach for intrusion detection in cluster-based wireless sensor networks[C]∥International Conference on Green Communications and Networking, Berlin, Heidelberg, 2011: 1-12. [本文引用:1]
[18]	Ren X, Liang W, Xu W. Maximizing charging throughput in rechargeable sensor networks[C]∥The 23rd International Conference on Computer Communication and Networks (ICCCN), Shanghai, China, 2014: 1-8. [本文引用:1]

2016

0.0

... 0 引言近年来,无线传感器网络(Wireless sensor networks, WSNs)由于其优越的感知、计算和通信能力在环境检测、目标追踪、灾害救援等领域得到了迅速的发展^[1] ...

2015

0.0

. 2015, 47(2):136-141 DOI:doi:10.15961/j.jsuese.2015.02.021

An improved LEACH algorithm based on nodes' remaining energy and location

一种基于节点剩余能量和位置的LEACH 改进算法

Dong Ying , Su Zhen-zhen , Zhou Zhan-ying

董颖, 苏真真, 周占颖

针对典型的分簇路由协议LEACH随机选择簇头和成簇后没有考虑簇内成员节点位置的问题,提出了LEACH-ED算法。该算法对簇头的选择机制进行了优化,既考虑了节点能量,又能同时判断簇内成员节点与sink节点的距离。当某些簇内成员节点与sink节点距离较近时,不需经过簇头节点,而是直接和sink节点进行信息传递。仿真结果表明,改进的LEACH-ED算法网络生命周期与LEACH协议相比提高了近50%,同时网络中节点传输数据的能力也得到大幅度提高。

... 传统WSNs中使用的是电池能量有限且不可补充的传感器节点,以往的研究经常是通过改进能量路由协议^[2]、MAC协议^[3]或拓扑控制^[4]等方法来降低节点的能耗,并不能从根本上解决WSNs的能量问题 ...

2017

0.0

. 2017, 47(2):647-654 DOI:doi:10.3969/j.issn.1000-3428.2009.17.040

Cross-layer MAC protocol based on routing information for WSN

基于路由信息的WSN跨层MAC协议

Dong Ying , Zhou Zhan-ying , Su Zhen-zhen

董颖, 周占颖, 苏真真

针对MAC协议无法解决节点能耗和网络性能之间矛盾的问题,在AS-MAC协议的基础上,基于跨层的方法提出CLR-MAC协议。该协议利用路由层的路由表信息改变AS-MAC协议的控制帧格式,解决AS-MAC协议中因"强迫唤醒"造成的能量浪费问题,以延长网络寿命。理论分析和仿真实验证明,该协议随网络密度的增加,节能增益呈线性增加。

2015

0.0

. 2015, 41(3):646-660

A joint design method of hierarchical topology control and network resource allocation for wireless sensor networks

WSN中层次型拓扑控制与网络资源配置联合设计方法

Zhao Ji-jun , Gu Zhi-qun , Xue Liang

赵继军, 谷志群, 薛亮

2013

0.0

... 为了弥补节点能量受限方面的缺憾,各国研究学者采用了多种能量获取方案来实现对传感器节点能量的补充,例如从太阳、风、潮汐和周围环境的无线电中获取能量等^[5],但是这些能量的获取方式不可人为控制,而且较低的充电效率并不能保证网络的长期运行 ...

... 2316^[5] ...

... 125^[5] ...

2007

0.0

... 2007年麻省理工学院的Kurs等^[6]证明了磁耦合共振方式实现无线能量传输的可行性,这为WSNs能量获取问题的解决带来一线曙光 ...

2013

0.0

... 伴随着无线能量传输技术的日益成熟,越来越多的学者陆续加入到对可充电无线传感器网络(Wireless rechargeable sensor networks,WRSNs)的可行性研究中^[7] ...

2012

0.0

... 有学者提出可以利用移动充电车(Mobile charger,MC)以磁耦合共振的方式为部署在复杂环境下的传感器节点提供稳定且持续的能量供给,来维持WRSNs的长时间运行^[8] ...

2011

0.0

... 文献[9]采用一种基于能量循环再生的充电调度,以最大化无线充电车(Wireless charging vehicle,WCV)在每个充电周期中的休息比例为目标,并证明了最短哈密顿回路可作为WCV的最佳旅行路径 ...

2015

0.0

. 2015, 36(1):129-141

Problem of the dynamic topology architecture of rechargeable wireless sensor networks

可充电无线传感器网络动态拓扑问题研究

Ding Xu , Han Jiang-hong , Shi Lei

丁煦, 韩江洪, 石雷

... 文献[10]在能量补给设备兼任数据采集设备的情况下,提出了一种基于时变动态拓扑模型的充电调度方案,并在此基础上以最大化能量补给设备的驻站时间比为目标提出了最优化问题 ...

2012

0.0

... Xie等^[11]在蜂窝结构的充电网络中通过先离散化后线性化的数学方法,联合优化了旅行路径、节点流量控制以及充电时间等问题,并求解出最佳的调度安排 ...

2012

0.0

... 文献[12]中首次提出了一种新的充电模式:协同移动充电 ...

... 文献[13]在文献[12]的实验基础上进一步构造了最小权重的哈密顿回路,并将其应用到二维的WRSNs中 ...

2016

0.0

... 文献[13]在文献[12]的实验基础上进一步构造了最小权重的哈密顿回路,并将其应用到二维的WRSNs中 ...

2011

0.0

. 2011, 42(7):226-231

A dynamic multi-hop non-uniform clustering routing protocol in wireless sensor networks

无线传感器网络中面向动态多跳的非均匀分簇路由

Li Chao-liang , Hu Chun-hua

李超良, 胡春华

针对无线传感器网络中因均匀分簇而导致任务重的簇过早耗尽能量、整个网络失效的问题,提出一种自适应的动态多跳非均匀分簇方法,将传感器网络中的簇根据实际需要进行不均匀划分,承担任务较轻的簇划分得较小,而承担任务较重的簇则较大.通过均衡簇能量与其所承担的任务,有效地延长网络的生命周期.然后,将该方法应用于2种典型的路由算法LEACH和HEED.研究结果表明:在采用这种非均匀的分簇算法后,传感器网络的生存时间平均减小5％左右.

... 问题的有效途径^[14] ...

2016

0.0

... MC接到充电指令从BS出发开始一次的充电调度,当到达簇 Cj内为节点 Ni补充能量时,MC在节点 Ni处的停留时间为^[15]: ...

2015

0.0

... 为了有效地找出下一次调度中的充电目标,进而获取新的充电路径,本文采用马尔科夫预测模型^[16,17]预测MC离开充电节点之后的节点能耗 ...

2011

0.0

... 为了有效地找出下一次调度中的充电目标,进而获取新的充电路径,本文采用马尔科夫预测模型^[16,17]预测MC离开充电节点之后的节点能耗 ...

2014

0.0

... 实验中分别与EEUC算法和TSP算法^[18]进行了网络效用和数据传输能力的对比分析 ...