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

胡洁; 詹杰; 任保全

doi:10.11959/j.issn.2096-3750.2019.00110

您当前的位置：

首页 >

文章列表页 >

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

理论与技术 | 更新时间：2024-06-05

- WSN中基于流网络的K连通算法
- K connectivity algorithm based on flow network in wireless sensor networks
- 物联网学报 2019年3卷第3期页码：11-17
- 作者机构：
  
  1. 湖南科技大学物理与电子科学学院，湖南湘潭 411201
  2. 中国电子设备系统工程公司研究所，北京 100141
- 作者简介：
  
  [ "胡洁（1985- ），女，湖南株洲人，湖南科技大学物理与电子科学学院硕士生，主要研究方向为无线传感器网络。" ]
  [ "詹杰（1973- ），男，湖南常德人，博士，湖南科技大学物理与电子科学学院教授，主要研究方向为无线传感网络、嵌入式系统和近距离无线通信技术。" ]
  [ "任保全（1974- ），男，陕西周至人，博士，中国电子设备系统工程公司研究所高级工程师，主要研究方向为复杂环境下物联网技术及应用。" ]
- 基金信息：
  
  湖南省自然科学基金;Hunan Natural Science Foundation(2018JJ2132);湖南科技大学基金;Hunan University of Science and Technology Foundation(KJ1711)
- DOI：10.11959/j.issn.2096-3750.2019.00110
  中图分类号： TN925
- 纸质出版日期：2019-09-30，
  
  网络出版日期：2019-09，
- 稿件说明：
移动端阅览
胡洁, 詹杰, 任保全. 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.
胡洁, 詹杰, 任保全. WSN中基于流网络的K连通算法[J]. 物联网学报, 2019,3(3):11-17. DOI： 10.11959/j.issn.2096-3750.2019.00110.

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. DOI： 10.11959/j.issn.2096-3750.2019.00110.

摘要

无线传感器网络（WSN）的连通性是保证网络容错性的重要途径。常规的多路由算法往往存在共同路径，这些共同路径会因为节点损坏、通信链路中断等故障导致整个WSN 的连通性过早失效。针对共同路径问题提出了一种解决方案，通过节点分裂的方式在共同路径上生成多条路径，以支持WSN 的容错，保证每个传感器节点都有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.

关键词

无线传感器网络流网络K连通算法不相交路径路由

Keywords

wireless sensor networksflow networkK connected algorithmdisjoint path routing

references

JENNIFER Y, BISWANATH M, DIPAK G . Wireless sensor network survey[J]. Computer Networks, 2008,52(12): 2292-2330.

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.

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.

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.

于磊磊 . 无线传感器网络不相交多路径容错路由研究[D]. 济南:山东大学, 2014.

YU L L . Study on disjoint multipath fault-tolerant routing of wireless sensor networks[D]. Jinan:Shandong University, 2014.

BHANDARI R, . Optimal physical diversity algorithms and survivable networks[C]// Second IEEE Symposium on Computers and Communications. IEEE, 1997.

白森 . 基于图论的区域覆盖与点集覆盖问题研究[D]. 长春:吉林大学, 2016.

BAI S . Research on regional coverage and point set coverage based on graph theory[D]. Changchun:Jilin University, 2016.

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.

LLOYD E L, XUE G . Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers, 2007,56(1): 134-138.

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.

于江龙, 陈光亭, 张燕翠 . 双层无线传感器网络 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.

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.

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.

张亚强 . 启发式算法求解无线传感器网络多移动节点路径规划问题[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.

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.

TANG J, HAO B, ARUNABHA S . Relay node placement in large scale wireless sensor networks[J]. Computer Communications, 2004,29(4): 490-501.

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.

陈娟 . 基于网格的k覆盖多连通WSN节点部署研究[D]. 苏州:苏州大学, 2014.

CHEN J . Research on deployment of grid-based k-covered mul-ti-connected WSN nodes[D]. Suzhou:Suzhou University, 2014.

朱明 . 基于虚拟网格的无线传感器网络节点部署研究[D]. 大连:大连理工大学, 2016.

ZHU M . Research on node deployment of wireless sensor network based on virtual grid[D]. Dalian:Dalian University of Technology, 2016.

苗春雨, 陈丽娜, 戴国勇 ,等. 面向数量最少化的双层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.

张娜娜, 赵作鹏, 李晓波 . 采用半贪心优化的节点非均匀分布路由协议[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.

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.

FORD L R, FULKERSON D R . Flows in networks[M]. Princeton: Princeton University PressPress, 1962.

浏览量

297

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据