On constructing 2-connected 2-dominating set using two centralized algorithms

doi:10.3778/j.issn.1002-8331.2009.15.031

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (15): 107-110.DOI: 10.3778/j.issn.1002-8331.2009.15.031

• 网络、通信、安全 • Previous Articles Next Articles

On constructing 2-connected 2-dominating set using two centralized algorithms

SUN Li-shan,ZHANG Rui-hong,WU Wen-bin

Department of Electrical Engineering，Harbin Institute of Technology，Harbin 150001，China

Received:2008-03-25 Revised:2008-06-12 Online:2009-05-21 Published:2009-05-21
Contact: SUN Li-shan

2-连通2-支配集的集中式构造

孙立山,张瑞宏,武文斌

哈尔滨工业大学电气工程及自动化学院，哈尔滨 150001

通讯作者: 孙立山

Abstract

Abstract: In wireless sensor networks，a connected dominating set is used to construct a virtual backbone network for layered routing.It is necessary to construct a connected dominating set as a virtual backbone network to balance efficiency and fault tolerance in some important occasion.In this thesis two centralized algorithms to construct 2-connected 2-dominating set are proposed，and they are First-Loop Second-Domination（FLSD） and First-Domination Second-Loop（FDSL） respectively.In FLSD，it begins with loop formation using dominating nodes，and then based on previous formed loop，the looping-in will continue until each non-dominating node’s being dominated by at least two dominating nodes.However，in FDSL，each non-dominating node being dominated by at least two dominating nodes is achieved before the loops with all dominating nodes are formed.

Key words: wireless sensor network, connected dominating set, centralized algorithm, 2-connected graph

摘要： 在无线传感器网络中，通常采用连通支配集来构成一个虚拟骨干网进行分层路由，对重要的目标或环境需要构造容错性高，可靠性好的虚拟骨干网。提出构造网络2-连通2-支配集的两种集中式算法，分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路，然后以此回路为基础不断地扩充此回路，直到不在回路中的节点为2-被支配为止；后一种算法是首先保证每个非支配点都要变成2-被支配点，然后再使图中所有支配点构成回路。

关键词: 无线传感器网络, 连通支配集, 集中式算法, 2-连通图

SUN Li-shan,ZHANG Rui-hong,WU Wen-bin. On constructing 2-connected 2-dominating set using two centralized algorithms[J]. Computer Engineering and Applications, 2009, 45(15): 107-110.

孙立山,张瑞宏,武文斌. 2-连通2-支配集的集中式构造[J]. 计算机工程与应用, 2009, 45(15): 107-110.

[1]	SHENG Jianhui, FAN Yinting, XIA Minjie. Physical Layer Security Performance Analysis for Wireless Sensor Network [J]. Computer Engineering and Applications, 2021, 57(8): 91-95.
[2]	GONG Junhui, HU Xiaohui, DU Yongwen. Research on Selection of Optimal Defense Strategy Based on Evolutionary Game [J]. Computer Engineering and Applications, 2021, 57(13): 116-123.
[3]	SUN Zeyu, DONG Hanlei, SU Yanchao, XU Chen, NIE Yalin, LI Chuanfeng. MDR：Multi-parameter Data Reconstruction Method Based on Energy Efficient in Sensor Networks [J]. Computer Engineering and Applications, 2021, 57(11): 103-110.
[4]	GONG Bencan, ZHOU Feng, CHEN Peng, REN Dong. Routing Protocol Based on Path Quality in Wireless Sensor Networks [J]. Computer Engineering and Applications, 2020, 56(6): 99-104.
[5]	ZHOU Fei, LUO Xiaoyong, LIU Yunping. Real-Time Correction of IMM Target Tracking Algorithm Based on Probability Model [J]. Computer Engineering and Applications, 2020, 56(21): 85-92.
[6]	ZHENG Zupeng, WANG Zumin, PENG Yang, JI Changqing, QIN Jing. Survey of MAC Protocols for Energy Harvesting Sensor Networks [J]. Computer Engineering and Applications, 2020, 56(15): 24-29.
[7]	YANG Feiyue, TAO Yang. Node Anomaly Detection Algorithm Based on Spatial-Temporal Cooperation in WSNs [J]. Computer Engineering and Applications, 2019, 55(7): 127-131.
[8]	ZHU Ruijin, GONG Xuejiao, TANG Bo. Distributed Hybrid Compressive Sensing for Wireless Sensor Network Data Collection [J]. Computer Engineering and Applications, 2019, 55(6): 73-80.
[9]	QIAO Ran, YAN Jiangyu, TANG Liangrui. Multidimensional Gaussian Based Wireless Sensor Network Localization Algorithm [J]. Computer Engineering and Applications, 2019, 55(23): 99-104.
[10]	WANG Yanjiao, TANG Qi. Improved Routing Energy Algorithm for Heterogeneous Wireless Sensor Networks [J]. Computer Engineering and Applications, 2019, 55(22): 80-85.
[11]	HAN Yulao. Low-Delay Reliable Data Gathering Algorithm for Band-Type Wireless Sensor Network [J]. Computer Engineering and Applications, 2019, 55(21): 104-109.
[12]	LIU Xiaochen, GAO Yuanyuan, XI Heping, ZHOU Mi. Secure Energy Efficiency Optimization for RF-Powered Wireless Sensor Networks [J]. Computer Engineering and Applications, 2019, 55(21): 122-128.
[13]	ZHANG Yuanyuan, WU Huafeng, XIAN Jiangfeng, MEI Xiaojun. Adaptive Clustering Algorithm in Ocean Wireless Sensor Network Under Double Constraints [J]. Computer Engineering and Applications, 2019, 55(19): 128-133.
[14]	ZOU Shanhua, GAO Yi, PENG Li. Research and Design of Event-Driven Control Strategy for Stochastic Systems [J]. Computer Engineering and Applications, 2019, 55(17): 100-106.
[15]	LI Daoquan, WEI Yanting, ZHANG Yuxia, LIU Wenjing. Energy Balanced Routing Algorithm for Wireless Sensor Networks Based on Ant Colony Optimization [J]. Computer Engineering and Applications, 2019, 55(17): 117-124.

On constructing 2-connected 2-dominating set using two centralized algorithms

2-连通2-支配集的集中式构造

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics