WSN中基于流网络的K连通算法

doi:10.11959/j.issn.2096-3750.2019.00110

物联网学报 ›› 2019, Vol. 3 ›› Issue (3): 11-17.doi: 10.11959/j.issn.2096-3750.2019.00110

WSN中基于流网络的K连通算法

胡洁¹,詹杰¹,任保全²

¹ 湖南科技大学物理与电子科学学院，湖南湘潭 411201
² 中国电子设备系统工程公司研究所，北京 100141

修回日期:2019-04-20 出版日期:2019-09-30 发布日期:2019-10-14
作者简介:胡洁（1985- ），女，湖南株洲人，湖南科技大学物理与电子科学学院硕士生，主要研究方向为无线传感器网络。|詹杰（1973- ），男，湖南常德人，博士，湖南科技大学物理与电子科学学院教授，主要研究方向为无线传感网络、嵌入式系统和近距离无线通信技术。|任保全（1974- ），男，陕西周至人，博士，中国电子设备系统工程公司研究所高级工程师，主要研究方向为复杂环境下物联网技术及应用。
基金资助:
湖南省自然科学基金(2018JJ2132);湖南科技大学基金(KJ1711)

K connectivity algorithm based on flow network in wireless sensor networks

Jie HU¹,Jie ZHAN¹,Baoquan REN²

¹ School of Physics and Electronics,Hunan University of Science and Technology,Xiangtan 411201,China
² Institute of Chinese Electronic Equipment System Engineering Corporation,Beijing 100141,China

Revised:2019-04-20 Online:2019-09-30 Published:2019-10-14
Supported by:
Hunan Natural Science Foundation(2018JJ2132);Hunan University of Science and Technology Foundation(KJ1711)

摘要/Abstract

摘要：

无线传感器网络（WSN）的连通性是保证网络容错性的重要途径。常规的多路由算法往往存在共同路径，这些共同路径会因为节点损坏、通信链路中断等故障导致整个WSN 的连通性过早失效。针对共同路径问题提出了一种解决方案，通过节点分裂的方式在共同路径上生成多条路径，以支持WSN 的容错，保证每个传感器节点都有K条长度有界的、到汇聚节点的不相交最短路径。仿真结果验证了本算法能提供更好的容错性，保证网络的连通性。

关键词: 无线传感器网络, 流网络, K连通算法, 不相交路径路由

Abstract:

Wireless sensor networks(WSN) connectivity is an important way to ensure network fault tolerance.Conventional multi-routing algorithms often have common paths,which will lead to premature connectivity failure of the whole WSN due to node damage,communication link interruption and other faults.Aiming at the common path problem,a solution was proposed to generate multiple paths on the common path through node splitting to support fault tolerance of WSN and ensure that each sensor node has K disjoint shortest paths of bounded length to the sinks.The simulation results show that the algorithm can provide better fault tolerance and ensure network connectivity.

Key words: wireless sensor networks, flow network, K connected algorithm, disjoint path routing

中图分类号:

TN925

胡洁,詹杰,任保全. WSN中基于流网络的K连通算法[J]. 物联网学报, 2019, 3(3): 11-17.

Jie HU,Jie ZHAN,Baoquan REN. K connectivity algorithm based on flow network in wireless sensor networks[J]. Chinese Journal on Internet of Things, 2019, 3(3): 11-17.

图/表 12

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 23

[1]	JENNIFER Y , BISWANATH M , DIPAK G . Wireless sensor network survey[J]. Computer Networks, 2008,52(12): 2292-2330.
[2]	KUAAKOWSKIHG P , CALLE E , MARZO J L . Performance study of wireless sensor and actuator networks in forest fire scenarios[J]. International Journal of Communication Systems, 2013,26(4): 515-529.
[3]	EMEKA E E , ABRAHAM O F . A survey of system architecture requirements for healthcare-based wireless sensor networks[J]. Sensors, 2011,11(5): 4875-4898.
[4]	FEMANDO L , ANTONIO-JAVIER G , FELIPE G ,et al. A comprehensive approach to WSN—based ITS applications:a survey[J]. Sensors, 2011(11): 10220-10265.
[5]	于磊磊 . 无线传感器网络不相交多路径容错路由研究[D]. 济南:山东大学, 2014.
	YU L L . Study on disjoint multipath fault-tolerant routing of wireless sensor networks[D]. Jinan:Shandong University, 2014.
[6]	BHANDARI R , . Optimal physical diversity algorithms and survivable networks[C]// Second IEEE Symposium on Computers and Communications. IEEE, 1997.
[7]	白森 . 基于图论的区域覆盖与点集覆盖问题研究[D]. 长春:吉林大学, 2016.
	BAI S . Research on regional coverage and point set coverage based on graph theory[D]. Changchun:Jilin University, 2016.
[8]	FOWLER R J , PATERSON M S , TANIMOTO S L . Optimal packing and covering in the plane are NP-complete[J]. Information Processing Letters, 1981,12(3): 133-137.
[9]	LLOYD E L , XUE G . Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers, 2007,56(1): 134-138.
[10]	LIN G H , XUE G . Steiner tree problem with minimum number of steiner points and bounded edge-length[J]. Information Processing Letters, 1999,69(2): 53-57.
[11]	于江龙, 陈光亭, 张燕翠 . 双层无线传感器网络 3-覆盖 3-连通问题[J]. 杭州电子科技大学学报, 2011,31(2): 89-92.
	YU J L , CHEN G T , ZHANG Y C . 3-coverage 3-connectivity problem of two-layer wireless sensor network[J]. Journal of Hangzhou Univer-sity of Electronic Science and Technology, 2011,31(2): 89-92.
[12]	MA C , LIANG W , ZHENG M . PSH:a pruning and substitution based heuristic algorithm for relay node placement in two-tiered wireless sensor networks[J]. Wireless Personal Communications, 2017,94(3): 1491-1510.
[13]	GEORGE J , SHARMA R M . Relay node placement in wireless sensor networks using modified genetic algorithm[C]// International Conference on Applied and Theoretical Computing and Communication Technology. IEEE, 2017.
[14]	张亚强 . 启发式算法求解无线传感器网络多移动节点路径规划问题[D]. 武汉:中国地质大学, 2017.
	ZHANG Y Q . Heuristic algorithm for path planning of wireless sensor networks with multiple mobile nodes[D]. Wuhan:China University of Geosciences, 2017.
[15]	LI P , LIU G . Research on wireless sensor networks fault-tolerant coverage algorithm base on particle swarm optimization[C]// Wireless Sensor Network,International Conference on IET. IEEE, 2010: 286-290.
[16]	TANG J , HAO B , ARUNABHA S . Relay node placement in large scale wireless sensor networks[J]. Computer Communications, 2004,29(4): 490-501.
[17]	JING Y L , REN S K . Grid-based directional minimum cost routing for massively dense wireless sensor networks[C]// International Conference on Information Networking. IEEE, 2014.
[18]	陈娟 . 基于网格的k覆盖多连通WSN节点部署研究[D]. 苏州:苏州大学, 2014.
	CHEN J . Research on deployment of grid-based k-covered mul-ti-connected WSN nodes[D]. Suzhou:Suzhou University, 2014.
[19]	朱明 . 基于虚拟网格的无线传感器网络节点部署研究[D]. 大连:大连理工大学, 2016.
	ZHU M . Research on node deployment of wireless sensor network based on virtual grid[D]. Dalian:Dalian University of Technology, 2016.
[20]	苗春雨, 陈丽娜, 戴国勇 ,等. 面向数量最少化的双层WSN中继节点部署算法[J]. 通信学报, 2016,37(4): 139-148.
	MIAO C Y , CHEN L N , DAI G Y ,et al. A two-layer WSN relay node deployment algorithm for minimizing the number of nodes[J]. Journal on Communications, 2016,37(4): 139-148.
[21]	张娜娜, 赵作鹏, 李晓波 . 采用半贪心优化的节点非均匀分布路由协议[J]. 计算机工程与应用, 2017,53(23): 60-66.
	ZHANG N N , ZHAO Z P , LI X B . Non-uniform node distribution routing protocol based on semi-greedy optimization[J]. Computer En-gineering and Application, 2017,53(23): 60-66.
[22]	LI N , HOU J C . FLSS:a fault-tolerant topology control algorithm for wireless networks[C]// International Conference on Mobile Computing and Networking. ACM, 2004: 275-286.
[23]	FORD L R , FULKERSON D R . Flows in networks[M]. Princeton: Princeton University PressPress, 1962.

WSN中基于流网络的K连通算法

K connectivity algorithm based on flow network in wireless sensor networks

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 23

相关文章 6

Metrics

推荐阅读 0

[1]	朱开磊, 孙爱晶. 基于布谷鸟优化K均值的WSN分簇路由算法[J]. 物联网学报, 2022, 6(1): 73-81.
[2]	赵小强, 吴帅, 高传义, 李宁, 李波东, 杨小勇. 基于测距修正及改进灰狼优化器的DV-Hop定位算法研究[J]. 物联网学报, 2021, 5(4): 62-70.
[3]	赵小强, 任少亚, 翟永智, 权恒, 杨婷. 基于模拟退火算法和改进灰狼优化器的异构无线传感器网络路由协议[J]. 物联网学报, 2021, 5(2): 97-106.
[4]	杨金凤,王骥. 精准农业无线传感器网络协议研究[J]. 物联网学报, 2020, 4(4): 62-69.
[5]	何鹏举,刘刚易,刘寺意. 基于WSN和盲源分离的多目标识别方法研究[J]. 物联网学报, 2019, 3(1): 45-50.
[6]	罗小娟,朱煜,黄如. 无线传感器网络病毒传播动力学模型研究[J]. 物联网学报, 2017, 1(2): 63-67.