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

doi:10.11959/j.issn.2096-3750.2019.00110

Abstract

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

CLC Number:

TN925

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.

Figures/Tables 12

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

K connectivity algorithm based on flow network in wireless sensor networks

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 23

Related Articles 1

Metrics

Recommended 0