Computer Science ›› 2020, Vol. 47 ›› Issue (7): 250-256.doi: 10.11896/jsjkx.190700059

• Computer Network • Previous Articles     Next Articles

Approximate Algorithm for Minimum Virtual Backbone in 3D Wireless Ad Hoc Networks

YI Meng, LIANG Jia-rong, QIN Bin   

  1. School of Computer and Electronics Information,Guangxi University,Nanning 530004,China
    Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China
  • Received:2019-07-06 Online:2020-07-15 Published:2020-07-16
  • About author:YI Meng,born in 1995,postgraduate,is a member of China Computer Federation.Her main research interests include wireless network and so on.
    LIANG Jia-rong,born in 1966,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include generali-zed control system,network fault diagnosis and mobile network computing.
  • Supported by:
    This work was supported by the Natural Science Foundation of China (61862003,61761006) and Natural Science Foundation of the Guangxi Zhuang Autonomous Region of China (2018GXNSFDA281052,2017GXNSFAA198276)

Abstract: In homogeneous wireless ad hoc networks,the size of VB (Virtual Backbone) is an important factor to measure the quality of ad hoc networks,the smaller the virtual backbone,the less the network routing overhead.The problem of minimum virtual backbone can be abstracted into the problem of minimum connected dominating set.There have been a lot of research achievements on the problem of minimum connected dominating set in UDG (Unit Disk Graphs,UDG) on two-dimensional wireless sensor networks,but in some practical cases,unit disk graphs cannot accurately abstract the network.So how to construct high quality CDS(Connected Dominating Set,CDS) in UBG (Unit Ball Graph,UBG) is proposed.In this paper,an optimal upper bound of the number of independent nodes in UBG is given,and the performance ratio of CDS is obtained by using the upper bound.In the proposed algorithm ST-CDS,the method of constructing minimum steiner tree with minimum number of steiner nodes is mainly used to optimize the connecting parts between nodes.Theoretical analysis shows that the performance ratio of ST-CDS algorithm is 11.8080+ln11,which is the best result among all known researches in this direction.Simulation results also verify the feasibility of the proposed algorithm ST-CDS.

Key words: 3D Wireless ad hoc Network, Connected dominating set, Rhombic dodecahedron, Steiner tree, Virtual backbone

CLC Number: 

  • TP393
[1]SUN E J,NIETO A,ZHANG X K.The Wireless Sensor Network (WSN) Based Coal Ash Impoundments Safety Monitoring System[J].IOP Conference Series Earth and Environmental Science,2017,51(1):012010.
[2]AGARWAL Y,JAIN K,KARABASOGLU O.Smart VehicleMonitoring and Assistance Using Cloud Computing in Vehicular Ad Hoc Networks[J].International Journal of Transportation Science and Technology,2017,7(1):60-73.
[3]MICHELETTO M,PETRUCCI V,SANTOS R,et al.FlyingReal-Time Network to Coordinate Disaster Relief Activities in Urban Areas[J].Sensors,2018,18(5):1662.
[4]PIÓRO,MICHA,TOMASZEWSKI A,et al.Maximization ofMulticast Periodic Traffic Throughput in Multi-hop Wireless Networks with Broadcast Transmissions[J].Ad Hoc Networks,2018,77:119-142.
[5]EPHREMIDS A,WIESELTHIER J E,BAKERD J.A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling[J].Proceedings of the IEEE,1987,75(1):56-73.
[6]LLU B,WANG W,KIM D,et al.On Approximating Minimum 3-Connected m-Dominating Set Problem in Unit Disk Graph[J].IEEE/ACM Transactions on Networking,2016,24(5):2690-2701.
[7]WANG W,LIU B,KIM D,et al.A New Constant Factor Approximation to Construct Highly Fault-Tolerant Connected Dominating Set in Unit Disk Graph[J].IEEE/ACM Transactions on Networking,2017,25(1):18-28.
[8]HI Y,ZHANG Z,MO Y,et al.Approximation Algorithm forMinimum Weight Fault-Tolerant Virtual Backbone in Unit Disk Graphs[J].IEEE/ACM Transactions on Networking,2017,25(2):925-933.
[9]GONZALEZ A,ÓSCAR L,VAZ S.Deploying and Experimenting Wireless Ad Hoc Networks in Mountainous Regions for Broadband Multimedia Service Access[C]//Proceedings of the 5th International ICST Mobile Multimedia Communications Conference.ICST,2009.
[10]TAN D D,KIM D S.Cooperative Transmission Scheme forMulti-hop Underwater Acoustic Sensor Networks[J].IJCNDS,2015,14(1):1-18.
[11]WU W,DU H,JIA X,et al.Minimum Connected DominatingSets and Maximal Independent Sets in Unit Disk Graphs[J].Theoretical Computer Science,2006,352(1):1-7.
[12]VAHDATPOUR A,DABIRI F,MOAZENI M,et al.Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks[C]//International Symposium on Distributed Computing.Springer,2008.
[13]KIM D,ZHANG Z,LI X,et al.A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs[J].IEEE Transactions on Mobile Computing,2010,9(8):1108-1118.
[14]GAO X,LI J,CHEN G.A Better Approximation for Constructing Virtual Backbone in 3D Wireless Ad-hoc Networks[J].Theoretical Computer Science,2015,607(P3):363-380.
[15]MIN M,DU H,JIA X,et al.Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks[J].Journal of Global Optimization,2006,35(1):111-119.
[16]HUANG H,RICHA A W,SEGAL M.Approximation Algo-rithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks[J].Mobile networks & applications,2004,9(2):151-161.
[17]BUTENKO S,KAHRUMAN-ANDEROGLU S,URSULENKO O.On Connected Domination in Unit Ball Graphs[J].Optimization Letters,2011,5(2):195-205.
[18]BABEAA S,JAHROMI B H,AJDARI A,et al.MechanicalProperties of Open-cell Rhombic Dodecahedron Cellular Structures[J].Acta Materialia,2012,60(6/7):2873-2885.
[19]WANG Z C.Analysis and Exploration of Spatial Filling of Re-gular Polyhedron[J].Spatial Structures,2016,22(1):16-24.
[1] HAN Bing-qing, CHEN Yi-fei. Heterogeneous Chain Dominating Set Algorithm in Wireless Ad Hoc Networks [J]. Computer Science, 2018, 45(9): 135-140.
[2] MA Chen-ming, WANG Wan-liang and HONG Zhen. Improved Energy Efficient Data Gathering Protocol in Wireless Sensor Network [J]. Computer Science, 2015, 42(2): 65-69.
[3] . Cluster-based Distributed Consensus Algorithms Based on Connected Dominating Set in WSN [J]. Computer Science, 2012, 39(Z11): 55-57.
[4] . Algorithms for Dominating Set Problems in OTIS Networks [J]. Computer Science, 2012, 39(3): 93-97.
[5] . Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone [J]. Computer Science, 2012, 39(3): 83-87.
[6] ZHENG Ying,WANG Jian-xin,CHEN Jian-er. Survey of Steiner Tree Problem [J]. Computer Science, 2011, 38(10): 16-22.
[7] GUO Pan-hong, YANG Yang,LI Xin-you. Backbone for Heterogeneous Ad hoc Networks and their Performance Analysis [J]. Computer Science, 2009, 36(10): 101-103.
[8] . [J]. Computer Science, 2007, 34(9): 181-182.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!