2018年第37卷第10期
传感器与微系统(Transducer and Microsystem Technologies）
153
DOI:10.13873/J.10009787( 2018 )10-015304
基于最小Spanning树的中继节点部署算法
沈俊鑫'，南金秀'，张经阳”
（1.昆明理工大学管理与经济学院，云南昆明650093；2.钦州学院经济管理学院，广西钦州535001）摘要：在能量受限的无线传感器网络（WSNs)中，部署中继节点成为确保通信覆盖的常用方法。提出基于最小Spanning树的中继节点部署算法（MST-DRN）。MST-DRN算法引用基于无线充电的能量模型。再依据节点的能量采集率计算边权值。依据边权值的图模型构建最小Spanning树（MST）。检测MST中不满足生存条件的非支叶节点，在节点附近部署中继节点，维持网络连通。实验数据表明：提出的MST-DRN
关键词：无线传感器网络；中继节点；最小Spanning树；能量采集率；无线充电
中图分类号：TN929.5
文献标识码：A
文章编号：1000-9787(2018）10-0153-04
MinimumSpanningtree-baseddeployingrelay
nodes algorithm
SHEN Jun-xin', NAN Jin-xiu', ZHANG Jing-yang
(1.Facultyof ManagementandEconomics,KunmingUniversityof ScienceandTechnology,Kunming650093,China:
2.Faculty of Economics and Management,Qinzhou UniversityQinzhou535001,China)
Abstract: In energy-constrained wireless sensor networks( WSNs ), deploying relay nodes( RNs )is a normal way to ensure communication coverage. Minimum spanning tree-based deploying relay nodes( MST-DRN )algorithm is proposed. Energy model used in MST-DRN is appropriate to wireless charging. The weights are calculated using harvesting capacity of node. The minimum spanning tree( MST )is constructed edge weighted graph model. Test non-leaf nodes in MST that cannot meet the defined survivability condition relay nodes RNs are added around these nodes to maintain network connected. Experimental results show that MST-DRN ensures connectivity of network and lower cost, that is reduce number of RNs and increase packet transmission rate.
Keywords : wireless sensor networks( WSNs ); relay nodes( RNs ); minimum spanning tree energy; harvesting capacity ; wireless charging
0引言
随着环保概念日益深入，绿色通信已受到广泛关注。从环境资源采集能量成为解决无线传感器网络（wireless sensornetworks，WSNsy1.21的能量受限间题的有效方案，如电磁波、太阳能、风能等[3.4]。因此，在WSNs中补充具有能量采集的中继节点（relaynodes，RNs），进而弥补能量消耗始尽的节点在WSNs空缺，提高网络覆盖率，目的是确保网络连通率，并使RNs数目最小，降低成本。本文考虑了周期性数据流，即每个节点周期向基站传输数据流。同时，节点具有绿色能量采集能力。由于节点自身硬件、位置的不同，其能量采集率不同。
本文针对能量采集率不同的节点，提出了基于最小收稿日期：2017-11-08
Spanning树的中继节点部署算法（minimumspanningtree based deploying relay nodes，MST-DRN)算法，其目的在于以最少的RNs数，满足网络连通率，并保证数据传输成功率。 MST-DRN算法基于节点的能量采集容量，计算每个节点的权值，再计算边权值，然后依据边权值，并利用Kruskal算法构成最小Spanning树（minimumspanningtree，MST）。最后，检测MST的非叶节点的能量是否满足数据流的传输要求：若不满足，则成为低能量节点（nodeswith lowenergy capacity，Ns-LEC）。Ns-LEC需要RNs的协助，从而保证网络连通。实验数据表明：提出的MST-DRN算法能够以最小的RNs节点维持网络连通，降低了成本，也提高了数据包的传输成功率。
*基金项目：国家自然科学基金资助项目（61303234，61263022）：教育部人文社会科学研究项目（14YJC630107）；云南省省院省校人文社会科学研究项目（SYSX201809）；云南省哲学社会科学研究基地重点项目（JD2016ZD02）；云南省应用基础研究面上项目（2013FB033）；昆明理工大学培育项目（SKPYPY201645）