第19卷 第2期 太赫兹科学与电子信息学报Vo1．19，No．2 2021年4月 Journal of Terahertz Science and Electronic Information Technology Apr．，2021
文章编号：2095-4980(2021)02-0224-05
WSNs中优化移动信宿路径的数据收集算法
吕 虹
(贵州广播电视大学(贵州职业技术学院)信息工程学院，贵州贵阳 550001)
摘要：收集数据是部署无线传感网络(WSNs)的根本目的。采用移动信宿策略可有效缓解 WSNs的能耗问题，信宿的移动路径是该策略的关键。为此，提出基于伪驻留点的数据收集(VRDC)
算法。VRDC算法先依据驻留点规划信宿路径，再依据路径选择伪驻留点(VRPs)。VRPs可通过一跳
直接向移动信宿传输数据，而其他的节点则将数据传输至最近的VRPs，进而减少传输跳数，降低
能耗。仿真结果表明，提出的VRDC算法能有效降低能耗，并平衡节点间的能耗。
关键词：无线传感网络；数据收集；路径规划；伪驻留点；能耗
中图分类号：TN926；TP393 文献标志码：A doi：10.11805/TKYDA2019493
Data collection algorithm for optimizing mobile accommodation path in WSNs
LYU Hong
(Electronic and Computer Engineering，Guizhou Radio & TV University，Guiyang Guizhou 550001，China)
Abstract：Data collection is the fundamental purpose of deploying Wireless Sensor Networks(WSNs).
The adoption of mobile accommodation strategy can effectively alleviate the problem of energy
consumption of WSNs. The mobile path is the key of the strategy. Therefore, Virtual Rendezvous points
-based Data Collecting(VRDC) algorithm is proposed in this paper. The VRDC algorithm first plans
lodging paths based on the host Points, and then selects Virtual Rendezvous Points(VRPs) based on the
host Points. VRPs can transmit data directly to the mobile address via one hop, while other nodes can
transmit data to the nearest VRPs, thereby reducing the number of transmission hops and energy
consumption. Simulation results show that VRDC algorithm can effectively reduce energy consumption and
balance energy consumption among nodes.
Keywords：Wireless Sensor Networks；data collection；path planning；Virtual Rendezvous Points；
energy consumption
无线传感网络(WSNs)[1]已在多个应用范围内使用，如军事监测、环境勘察、智慧农业、智能家居、康复医疗等。每个节点具有感测、处理数据的能力，并以多跳方式将所感测的数据传输至信宿[2]。在多跳通信中，由于靠近信宿的节点承担了更多的数据转发任务，它们的能量消耗速度更快[3-4]，容易形成能量空洞。一旦出现能量空洞，网络就被分割。因此，平衡节点间的能耗是避免能量空洞的关键。
通过信宿的移动能有效平衡网络能耗[5-6]，而规划信宿的移动路径是该策略的关键。最简单的方法就是遍历每个节点，进而直接接收感测数据[7]。但该方法并没有解决巡回售货员问题(Traveling Salesman Problem，TSP)[8]。TSP问题就是如何以最短的路径遍历所有节点。然而，随着网络规模的增加，节点数剧增，得到最短的路径是一项不小的挑战；同时，遍历网络内每个节点是非常耗时的。为减少遍历时间，移动信宿(Mobile Sink，MS)只遍历网络内部分点，这些点称为驻留点(Rendezvous Points，RPs)[8-11]。移动信宿沿着RP移动，并在每个RP位置收集数据。文献[9-10]提出伪驻留点(VRPs)概念，VRPs是指位于RPs附近的节点，这些VRPs通过一跳直接将数据传输至MS，而剩下的节点将数据传输至最近的VRP。通过减少通信跳数，降低数据包丢失率，构建最优的VRPs，能够提高能量效率。但如何依据RPs集规划路径，并构建最优的VRPs仍是一项挑战。而三维WSNs又加大了这项工作的难度。
收稿日期：2019-11-25；修回日期：2020-01-13
基金项目：贵州省高等学校人文社会科学研究基地资助项目(2018jd113)
作者简介：吕虹(1986-)，女，硕士，副教授，主要研究方向为无线传感网络、数据收集，路由、算法设计分析，信息处理等。email:*****************
第2期 吕 虹等：WSNs 中优化移动信宿路径的数据收集算法
225
文献[11-12]研究了三维WSNs 的MS 路径规划问题，但这些算法的复杂度较高。文献[10]提出一个低复杂度的路径规划策略，但其移动路径长，增加了网络时延。为此，针对三维WSNs ，提出基于VRPs 的数据收集算法(VRDC)。VRDC 算法利用RPs 集产生最优路径，并在RPs 附近产生VRPs 。MS 沿着所规划的路径移动，再从这些VRPs 位置收集数据。仿真结果表明，提出的VRDC 算法有效减少了能耗，提高了网络寿命。
1 系统模型
1.1 约束条件
假定n 个节点随机分布于l ×l ×l 立体区域内。这n 个节点构成节点集{}123,,,,n S s s s s = ，其中s 0为信宿。所有节点具有相同的通信半径。令r 表示节点的通信半径，MS 为能够移动的自主车，其自身能够收集节点数据，且其能量不受限。
依据文献[10]的簇构建算法，将n 个节点划分为多个
簇，并将每个簇的中心位置作为RP 。假定网络内形成m 个RPs ，这m 个RP 构建RPs 集：{}12,,,m M RP RP RP = 。如图1所示，其中BS 表示；ME 表示移动信宿；ND 表示传感节点；CH 表示簇头。VRDC 算法需解决的问题，就是如何依据这m 个RPs 规划MS 移动的最优路径，同时，构建最优的VRPs ，进而以低的能耗收集网络内感测数据。
1.2 能耕模型
传感节点的多数能量消耗于发送数据和接收数据。引用文献[13]的自由空间能耗模型，节点s i 向节点s j 传输
β比特数据所消耗的能量()tx ,E i j 为：
()tx tx fs ,ij E i j d γ
βααβ=⨯+⨯⨯ (1)
式中：tx α,fs α分别为发送、处理单位比特数据所消耗的能量；d ij 为节点s i 与节点s j 间的欧式距离；γ为衰落指数，一般[]2,4γ∈[9]。
令()rx ,E i j 表示节点s i 接收β比特数据所消耗的能量：
()rx rx E i βα=⨯ (2)
因此，可依式(3)计算节点s i 所消耗能量E i ：
()()()tx rx ,i i i i E E j i u E i u ϑ=⨯++⨯ (3)
鲁智深的故事式中：i ϑ为节点s i 所产生的比特数；u i 为节点s i 从孩子节点所接收的比特数，其定义如式(4)所示：
级别工资,if 0,otherwise
i j i j i u ξϑξΦ
∈⎧≠⎪=⎨⎪⎩∑ (4)
式中：ξi 为节点s i 的孩子节点集；j ϑ为节点s j 向节点s i 传输的比特数。
2 VRDC 算法
2.1 移动信宿的路径规划
为有效提高数据收集效率，VRDC 算法要求MS 遍历网络内所有RPs 。执行路径规划的步骤如下：
1) 先将0S 加入RP 集，即0M M S ← 。
2) 在x 轴平台上寻最左、最右和中间的RP 节点，分别表示1ℜ,2ℜ和3ℜ。计算由1ℜ,2ℜ和3ℜ构成距离矩阵Q (3×3)， (,),,1,2,3i j j i j ⎡⎤=ℜ-ℜ=⎣⎦Q 。再判断矩阵Q 的行列式()det Q 值，如果()det 0≤Q ，则将{}123,,ℜ=ℜℜℜ加入集A (最初A 集apple id 密码修改
为空)，即A ←ℜ；否则，将ℜ加入集B (最初B 集为空)。随后，将已处理的3个RP 节点从M 集中删除，即M M ←-ℜ。重
复上述过程，直至M 集为空。
3) 将形成的集A 和集B 进行排序。在集A 内对RPs 按x 轴坐标升序排序；而在集B 内对RPs 按x 轴坐标降序排序。然后将A 和B 加入ϕ集。ϕ集表示由RPs 构建的路径点。最后，对ϕ再进行循环移动，直至S 0成为第 一个MS 到达的位置。最终，MS 依据ϕ中的RPs 进行移动。
ND
CH VH九九重阳节的来历
ME track
cluster range
CH她组词 二年级
ME BS
R
r
226
太赫兹科学与电子信息学报 第19卷
2.2 VRPs 的构建
VRPs 是实际的数据收集点，MS 直接从VRPs 收集数据，而其余的节点将数据传输至离自己最近的VRP 。因此，构建最近的VRPs 成为数据收集的关键。
对于ϕ集内任意2个RPs 点(假定为1ℜ,2ℜ)，节点s i 离1ℜ,2ℜ连线的距离表示为d (s i )。如果d (s i )小于节点的通信半径r ，则将节点s i 作为VRP 。
最初由点1ℜ,2ℜ和点P 构成一个三角形，其中点P 表示节点
s i 的位置。令a ,b 和c 分别表示该三角形三边的长度：
()()()1221,,,a d b d P c d P =ℜℜ⎧⎪
=ℜ⎨⎪=ℜ⎩
(5) 再依据式(6)计算点P 离12ℜℜ线段的距离d (s i )：
()i d s b
τ
=
(6)
式中()()()s s a s b s c τ=⨯-⨯-⨯-，()/3s a b c =++。
图2为数据收集示例，菱形表示VRPs ，三角形表示RPs ，圆点为传感节点。当MS 沿着路径移动时，就从路径附近的VRPs 收集数据。
3 性能分析
3.1 仿真环境
为更好地分析VRDC 算法性能，利用Matlab 软件建立仿真平台。在300 m×300 m×300 m 区域内部署100至400个节点，具体的仿真参数如表1所示。
选择能效路径选择策略(Energy-Efficient Path Selection ，EEPS)算法[9]、基于移动信宿和簇的混合数据收集(Hybrid Data Collection Approach ，HDCA)算法[10]
和ACO 的移动信宿路径决策(ACO-based Mobile sink Path Determination ，AMPD )算法[12]作为参照，对比分析VRDC 算法的节点平均能耗、网络寿命以及能耗的均衡性。其中节点平均能耗是指MS 移动一轮内，所有节点的能耗平均值；网络寿命是指从部署节点开始至第一个能耗殆尽节点出现的轮数。用公平指标(Fairness Index ，FI)表述能耗的均衡性：
e m
u 21FI E E λ⎛⎫
⨯=- ⎪-⎝⎭ (7)
式中：λe 为传感节点能耗的标准差；E m ,E u 分别为最大的能耗和最小能耗。λe 定义为：
e λ= (8) 3.2 节点平均能耗
首先分析节点平均能耗随网络内节点数的变化情况，如图3所示。从图3可知，节点数的增加加大了节点平均能耗。原因在于：节点数越多，网络内要传输的数据包越多，这加大了节点传输数据的负担，最
终增加了节点平均能耗。相比于EEPS 算法、AMPD 算法和HDCA 算法，提出的VRDC 算法有效控制了能耗。相比于EEPS 算法，VRDC 算法的能耗下降约26%。如，当节点数为400时，VRDC 算法的平均能耗约32 mJ ，而EEPS 算法的平均能耗约58 mJ 。
VRPs RPs
SN
MS range
MS path
MS data collection
range
Fig.3 Average energy consumption
公益广告用语图3 节点平均能耗 100 150 200 250 300 350 400
number of sensor nodes VRDC HDCA AMPD EEPS
605550454035302520
第2期 吕
虹等：WSNs 中优化移动信宿路径的数据收集算法
227
3.3 网络寿命
分析VRDC 算法的网络寿命，如图4所示。从图4可知，节点数的增加，使网络寿命呈下降趋势。相比于
EEPS 算法、EAPC 算法和NDCMC 算法，VRDC 算法网络寿命下降速度缓慢。
此外，VRDC 算法的网络寿命也远高于EEPS 算法、AMPD 算法和HDCA 算法的网络寿命，分别高了近556轮、517轮和435轮。这与图3的能耗数据相对应。VRDC 算法通过均衡节点间能耗，避免个别节点能量枯竭，进而延长了网络寿命。
3.4 能耗均衡
分析EEPS 算法、AMPD 算法、HDCA 算法和VRDC 算法的能耗均衡性能。图5为4种算法的能耗公平指标，其定义见式(7)。从图5可知，最初FI 指标为1，随着执行轮数的增加，FI 逐步下降。但VRDC 算法下降的速度变缓，相比之下，EEPS 算法、AMPD 算法和HDCA 算法下降速度很快。如，当执行至150轮时，VRDC 算法的FI 约0.85，AMPD 算法、HDCA 算法的FI 分别为0.55,0.65，而EEPS 算法在执行至120轮时，它的FI 指标就降至0.55。这些数据表明，VRDC 算法有效均衡了节点的能耗，使网络内多数的能耗速度保持相对一致。
4 结论
通过信宿在网络内移动，可有效减少节点传输数据的跳数，并平衡节点间的能耗。为此，提出VRDC 算法。VRDC 算法先依据驻留点规划信宿的最优移动路径，再依据此路径产生VRPs 。信宿从VRPs 收集数据，进而缩短了移动路径，并平衡了节点间的能耗。仿真数据表明，相比于同类算法，VRDC 算法有效缓解了能耗速度，延长了网络寿命。
参考文献：
[ 1 ] 李柳雅，贾宗璞. 基于CFSFDP 聚类算法的WSN 高能效分簇路由算法[J]. 计算机应用研究, 2018,35(3):884-888.
(LI Liuya,JIA Zongpu. Energy -efficient clustering routing algorithm based on CFSFDP clustering algorithm in WSN[J]. Application Research of Computers, 2018,35(3):884-888.)
[ 2 ] 尚亚丽. WSNs 中基于能效感知的任播路由[J]. 太赫兹科学与电子信息学报, 2019,17(6):1012-1016. (SHANG Yali.
An energy -efficient Anycast routing in Wireless Sensor Networks[J]. Journal of Terahertz Science and Electronic Information Technology, 2019,17(6):1012-1016.)
[ 3 ] 陶建林，方凯，苗春雨，等. 一种能耗优先的WSN 路由空洞修复方法研究[J]. 传感技术学报, 2019,32(5):762-768.
(TAO Jianlin,FANG Kai,MIAO Chunyu,et al. A WSN routing void repair method based on energy consumption priority[J]. Chinese Journal of Sensors and Actuators, 2019,32(5):762-768.)
[ 4 ] 马忠彧，马宏锋，彭琳茹，等. 面向环境监测的WSN 中基于定向传输的高能效路由算法[J]. 传感技术学报, 2018,31(2):
297-303. (MA Zhongyu,MA Hongfeng,PENG Linru,et al. Energy -efficient routing algorithm based on directional transmission in WSN network for environmental monitoring[J]. Chinese Journal of Sensor
s and Actuators, 2018,31(2):297-303.)
(下转第249页)
Fig.4 Network lifetime 图4 网络寿命
100 150 200 250 300 350 400
number of sensor nodes
1 2001 1001 000900800700600500
400
n e t w o r k l i f e t i m e /r o u n d s
VRDC HDCA AMPD EEPS
Fig.5 Fairness Index 图5 能耗均衡的公平指标
VRDC HDCA AMPD EEPS
0 50 100 150
number of rounds
第2期郝艳阳等：基于树莓派的嵌入式时钟发生器249
[ 9 ] 郭鹏飞，温志渝，周颖，等. 基于树莓派的远程水质监测系统设计[J]. 重庆理工大学学报(自然科学), 2018,32(4):186-192.
(GUO Pengfei,WEN Zhiyu,ZHOU Ying,et al. Design of remote water quality monitoring system based on Raspberry Pie[J].
Journal of Chongqing University of Technology(Natural Science), 2018,32(4):186-192.)
[10] 薛霏. 基于树莓派的储热式电锅炉自动控制系统研制[D]. 石家庄：石家庄铁道大学, 2019. (XUE Fei. Development of
automatic control system for thermal storage electric boiler based on Raspberry Pi[D]. Shijiazhuang,China:Shijiazhuang Tiedao University, 2019.)
[11] 戴巍，霍亚，马尚昌，等. Qt下基于组件的嵌入式软件框架设计及实现[J]. 计算机应用, 2016,36(Z1):257-261. (DAI Wei,
HUO Ya,MA Shangchang,et al. Design and implementation of component-based embedded software framework by Qt[J].
Journal of Computer Applications, 2016,36(Z1):257-261.)
[12] LEWIS A J,CAMPBELL M,STAVROULAKIS P. Performance evaluation of a cheap,open source,digital environmental monitor
based on the Raspberry Pie[J]. Measurement, 2016(87):228-235.
[13] 林志伟，徐冠华，吴森洋. 基于树莓派的三维打印上位机控制系统[J]. 实验技术与管理, 2019,36(6):114-118. (LIN Zhiwei,
XU Guanhua,WU Senyang. 3D printing controlling system for upper computer based on Raspberry Pi[J]. Experimental Technology and Management, 2019,36(6):114-118.)
[14] 田磊. 嵌入式Linux系统中基于QT库的应用程序设计[J]. 实验室研究与探索, 2014,33(5):84-86,115. (TIAN Lei.
Design of application program of embedded Linux system based on QT[J]. Research and Exploration in Laboratory, 2014, 33(5):84-86,115.)
[15] 于志强，温志渝，谢瑛珂，等. 基于树莓派的多参数水质检测仪控制系统[J]. 仪表技术与传感器, 2015(6):20-23,27.
(YU Zhiqiang,WEN Zhiyu,XIE Yingke,et al. Control system for multi-parameter water quality monitor based on Raspberry Pi[J]. Instrument Technique and Sensor, 2015(6):20-23,27.)
(上接第227页)
[ 5 ] GHARAEI N,BAKAR K A,HASHIM Z M,et al. Collaborative mobile sink sojourn time optimization scheme for cluster-based wireless sensor networks[J]. IEEE Sensors Journal, 2018,18(16):6669-6676.
[ 6 ] WANG Y,CHEN K. Efficient path planning for a mobile sink to reliably gather data from sensors with diverse sensing rates and limited buffers[J]. IEEE Transactions on Mobile Computing, 2018,3(7):23-31.
[ 7 ] MA M,YANG Y. Data gathering in wireless sensor networks with mobile collectors[C]// 2008 IEE
E International Symposium on Parallel and Distributed Processing. Miami,FL,USA:IEEE, 2008:1-9.
[ 8 ] ARORA S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems[J].
Journal of The ACM, 1998,45(5):753-782.
[ 9 ] SALARIAN H,CHIN K,NAGHDY F. An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J].
IEEE Transactions on Vehicular Technology, 2014,63(5):2407-2419.
[10] ZHANG R,PAN J,XIE D,et al. NDCMC:a hybrid data collection approach for large-scale WSNs using mobile element and
hierarchical clustering[J]. IEEE Internet of Things Journal, 2016,3(4):533-543.
[11] TARACHAND A,JANA P K. Energy-aware routing algorithm for wireless sensor networks[J]. Computers and Electrical
Engineering, 2015,41(8):357-367.
[12] KUMAR D P,TARACHAND A,RAO A C,et al. ACO-based mobile sink path determination for wireless sensor networks
under non-uniform data constraints[J]. Applied Soft Computing, 2018,69(9):528-540.
[13] WEN W,ZHAO S,SHANG C,et al. EAPC:energy-aware path construction for data collection using mobile sink in wireless
sensor networks[J]. IEEE Sensors Journal, 2018,18(2):890-901.
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论