计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 250-256.doi: 10.11896/jsjkx.190700059
易梦, 梁家荣, 覃斌
YI Meng, LIANG Jia-rong, QIN Bin
摘要： 在均质无线自组织网络中,虚拟骨干(Virtual Backbone,VB)的大小是衡量无线自组织网络质量的一个重要因素,虚拟骨干越小,网络路由开销越少。最小虚拟骨干的求取问题能够抽象为最小连通控制集问题。针对二维无线自组织网络上的单位圆盘图(Unit Disk Graph,UDG)中最小连通控制集问题,目前已有很多研究成果,但是在现实中的某些情况下,单位圆盘图并不能准确地抽象网络。因此,文中提出了在单位球图(Unit Ball Graph,UBG)中构建高质量的连通控制集(Connected Dominating Set,CDS)的算法ST-CDS,给出了单位球图中独立节点个数的一个优化上界,并进一步利用该优化上界得到连通控制集的性能比。所提算法主要运用构造最小斯坦纳节点的斯坦纳树(Steiner Tree with Minimum Number of Steiner Nodes)方法来优化节点之间的连通部分。理论分析表明,ST-CDS算法的性能比为11.8080＋ln11,是目前已知该方向研究中最好的结果。仿真结果也验证了ST-CDS算法的可行性。
中图分类号:
| [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] | 马晨明,王万良,洪榛. 无线传感器网络中一种改进的能效数据收集协议 Improved Energy Efficient Data Gathering Protocol in Wireless Sensor Network 计算机科学, 2015, 42(2): 65-69. https://doi.org/10.11896/j.issn.1002-137X.2015.02.014 |
|
||
首页