计算机科学 ›› 2018, Vol. 45 ›› Issue (9): 135-140.doi: 10.11896／j.issn.1002-137X.2018.09.021
韩冰青, 陈一飞
HAN Bing-qing, CHEN Yi-fei
摘要： 首先给出无线Ad Hoc网络的异构圆盘图模型HDG,并分析HDG模型的不同形态;然后设计出一种新的节点双向链表结构,在此基础上,提出一种基于链表结构的异构连通支配集算法C-LDS。该算法通过双向链表结构管理支配集,并通过节点引用的方式来提高支配集节点增加、删除及修改的时间效率,从而得到优化的连通支配集。将C-LDS算法与其他支配集算法进行对比测试,结果表明:在均匀分布以及随机分布的网络场景中,C-LDS所生成的支配集尺寸是最小的;在随机移动的网络场景中,C-LDS的分组投递率是最高的,展现出了较好的异构连通性并且提高了支配集节点的生成效率。
中图分类号:
| [1]MALEKI E N,MIRJALILY G.Fault-tolerant interference--aware topology control in multi-radio multi-channel wireless mesh networks[J].Computer Networks,2016,110:206-222. [2]KONG S S,LIU L F,CHEN H.Low Delay Topology Control Algorithm Based on Delivery Ratio Constraint in Wireless Sensor Networks[J].Computer Science,2016,43(2):144-147.(in Chinese) 孔姗姗,刘林峰,陈行.基于送达率约束的无线传感器网络低时延拓扑控制算法研究[J].计算机科学,2016,43(2):144-147. [3]GHASEMI V,HASHEMI S N,MOZAFFARI M.Connected Dominating Set Construction Using an Efficient Pruning Me-thod in Ad Hoc Networks[C]∥Proceeding of the 5th Annual ICST Wireless Internet Conference(WICON).Singapore,2010:1-8. [4]DHAWAN A,TANCO M,SCOVILLE N.A distributed greedy algorithm for constructing connected dominating sets in wireless sensor networks[C]∥Proceedings of the 3rd International Conference on Sensor Networks.Lisbon,Portugal,2014:181-187. [5]QURESHI H K,RIZVI S,SALEEM M,et al.Poly:a reliable and energy efficient topology control protocol for wireless sensor networks[J].Computer Communications,2011,34:1235-1242. [6]JALLUA R K,PRASADB P R,DASA G K.Distributed con-struction of connected dominating set in unit disk graphs[J].Journal of Parallel and Distributed Computing,2017,104:159-166. [7]WIGHTMAN P,LABRADOR M.A3:a topology control algorithm for wireless sensor networks[C]∥Proceedings of IEEE Global Communications Conference(GLOBECOM).New Or-leans,USA,2008:1-6. [8]RIZVI S,QURESHI H K,KHAYAM S A,et al.A1:an energy efficient topology control algorithm for connected area coverage in wireless sensor networks[J].Journal of Network and Computer Applications,2012,35(2):597-605. [9]NAMSU A,PARK S.An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks[J].Wireless Networks,2015,21(3):783-792. [10]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 Transactions on Networking,2017,25(1):18-28. [11]ZHANG Z,ZHOU J,MO Y C,et al.Performance-Guaranteed Approximation Algorithm for Fault-Tolerant Connected Dominating Set in Wireless Networks[C]∥IEEE INFOCOM.2016:1-8. [12]BUCHANAN A,SUNG J S,BUTENKO S,et al.An integer programming approach for fault-tolerant connected dominating sets[J].Informs Journal on Computing,2015,27(1):178-188. [13]JIN W L,CHEN G S.Improved broadcasting scheduling algorithm in cognitive radio networks[J].Application Research of Computers,2015,32(3):860-865.(in Chinese) 金伟林,陈国顺.认知无线电网络中一种改进的广播调度算法[J].计算机应用研究,2015,32(3):860-865. [14]KAMEI S,IZUMI T,YAMAUCHI Y.An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs[J].Theoretical Computer Science,2016,615:102-119. [15]DHAWAN A,TANCO M,YEISER A A.Randomized algo-rithms for approximating a Connected Dominating Set in Wireless Sensor Networks[C]∥International Conference on Computing and Network Communications(CoCoNet).2015:589-596. |
| [1] | 李跃新,朱明. 基于无线自组网络分时发送协议的路由汇聚容量 Study on Capacity of Route Aggregate Networks Based on Slotted Transmission Protocol 计算机科学, 2015, 42(8): 101-105. |
| [2] | 马晨明,王万良,洪榛. 无线传感器网络中一种改进的能效数据收集协议 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 |
| [3] | 陈亮,徐阳. 基于限速的Ad hoc网络混合流拥塞控制研究 Research on Ad hoc Network Hybrid Flow Congestion Control Based on Rate-limiting 计算机科学, 2014, 41(12): 86-90. https://doi.org/10.11896/j.issn.1002-137X.2014.12.019 |
| [4] | 陈辉,巨永锋. 无线自组网基于移动预测和能量均衡的拓扑控制算法研究 Mobility Prediction and Energy-balance Topology-control Algorithm for Ad hoc Networks 计算机科学, 2013, 40(4): 111-114. |
| [5] | 何文才,杜敏,刘培鹤,陈志伟,郑钊. 基于Paillier同态的无线自组网组密钥管理方案 Wireless AD-hoc Network Group Key Management Scheme Based on Paillier Homomorphic 计算机科学, 2013, 40(10): 114-118. |
| [6] | 江亮 刘建 鲜明 肖顺平. WSN中一种基于连通支配集的分簇一致性算法 Cluster-based Distributed Consensus Algorithms Based on Connected Dominating Set in WSN 计算机科学, 2012, 39(Z11): 55-57. |
| [7] | 向永香，叶慧，李旻，陈卫东. OTIS网络的支配集问题算法研究 Algorithms for Dominating Set Problems in OTIS Networks 计算机科学, 2012, 39(3): 93-97. |
| [8] | 贺毅朝，田海燕，张新禄，高锁刚. 基于相邻矩阵快速构建虚拟主干网的近似算法 Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone 计算机科学, 2012, 39(3): 83-87. |
| [9] | 陈亮，张宏. Ad-hoc网络PSD拥塞控制算法 PSD Congestion Control Algorithm in Ad-hoc Network 计算机科学, 2011, 38(6): 45-48. |
| [10] | 孙玉星,赵燕飞,李娅,谢立. 基于概率博弈的无线自组网信任推荐激励策略的研究 On Incentive Strategies for Trust Recommendations in Wireless Ad Hoc Networks with Probability Game 计算机科学, 2011, 38(4): 65-71. |
| [11] | 郭攀红,杨扬,李新友. 异构Ad hoc网络骨干网络的建立与性能分析 Backbone for Heterogeneous Ad hoc Networks and their Performance Analysis 计算机科学, 2009, 36(10): 101-103. |
| [12] | . 能量优先分级变化的多路径路由选择算法 计算机科学, 2007, 34(8): 45-48. |
| [13] | . 无线自组网的拓扑控制策略研究进展 计算机科学, 2007, 34(10): 70-73. |
| [14] | 庞博 徐雷鸣 向勇 史美林. 一种基于TD-SCDMA的无冲突自组网MAC协议 计算机科学, 2005, 32(1): 13-18. |
| [15] | 徐洁 魏正曦 夏梦芹. 一种无线自组网的路由实现方法 计算机科学, 2004, 31(1): 42-45. |
|
||
首页