Computer Science ›› 2018, Vol. 45 ›› Issue (9): 135-140.doi: 10.11896/j.issn.1002-137X.2018.09.021

• Network & Communication • Previous Articles     Next Articles

Heterogeneous Chain Dominating Set Algorithm in Wireless Ad Hoc Networks

HAN Bing-qing, CHEN Yi-fei   

  1. School of Technology,Nanjing Audit University,Nanjing 211815,China
  • Received:2017-07-21 Online:2018-09-20 Published:2018-10-10

Abstract: Firstly,the heterogeneous disk model HDG of Ad Hoc network was presented,and different forms of HDG model were analyzed.Secondly,a new two-way chain table structure was designed.Based on the chain structure,a connected dominating set algorithm C-LDS was proposed,which manages dominating set through two-way chain table structure,and improves the time efficiency of inserting,deleting and modify the dominating node through the node refe-rence way.Thus,the connected dominating set of Ad Hoc network is optimized.Finally,the C-LDS algorithm was compared with other dominating set algorithms.The simulation results show that C-LDS algorithm generates minimal CDS size in both uniform and random scenarios,and can achieve highest packet delivery ratio in mobile network scenarios,which showsgood heterogeneous connectivity and improves the efficiency yeneration of dominating set node.

Key words: Ad Hoc network, Connected dominating set, Heterogeneous disk, Two-way chain table

CLC Number: 

  • TP393
[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] ZHANG Geng-qiang, XIE Jun, YANG Zhang-lin. Accelerating Forwarding Rules Issuance with Fast-Deployed-Segment-Routing(FDSR) in SD-MANET [J]. Computer Science, 2022, 49(2): 377-382.
[2] YI Meng, LIANG Jia-rong, QIN Bin. Approximate Algorithm for Minimum Virtual Backbone in 3D Wireless Ad Hoc Networks [J]. Computer Science, 2020, 47(7): 250-256.
[3] XIONG Ling, LI Fa-gen, LIU Zhi-cai. Conditional Privacy-preserving Authentication Scheme Based on Blockchain for Vehicular Ad Hoc Networks [J]. Computer Science, 2020, 47(11): 55-59.
[4] HUANG De-ling,YAN Yu-song,PENG Da-qin. Geographic Routing Protocol Based on Prediction for Urban Vehicular Ad Hoc Networks [J]. Computer Science, 2019, 46(7): 74-80.
[5] WANG Qing-long, QIAO Rui, DUAN Zong-tao. Security Analysis on VANETs Authentication Schemes:CPAV and ABV [J]. Computer Science, 2019, 46(4): 177-182.
[6] HUO Shi-wei,ANG Wen-jing,LI Jing-zhi,SHEN Jin-shan. New Identity-based Authentication and Key Agreement Scheme in Ad hoc Networks [J]. Computer Science, 2018, 45(6A): 380-382.
[7] SUN Hai-feng and SONG Li-li. Intersection-relay-assisted Routing Scheme in VANETs [J]. Computer Science, 2018, 45(5): 75-78.
[8] YUE Xiao-han, HUI Ming-heng, WANG Xi-bo. Forward Security Anonymous Authentication Protocol Based on Group Signature for Vehicular Ad Hoc Network [J]. Computer Science, 2018, 45(11A): 382-388.
[9] CHENG Xiao, DONG Chao, CHEN Gui-hai, WANG Wei-jun, DAI Hai-peng. Communication and Networking Techniques for Formation Control in UAV Ad Hoc Networks [J]. Computer Science, 2018, 45(11): 1-12.
[10] CHEN Shao-hua, FAN Xiao-guang, CONG Wei, HUANG Jin-ke and SUN Xian-ming. Grid-based Identity Signcryption Algorithm and Application in Ad Hoc Network [J]. Computer Science, 2017, 44(6): 168-173.
[11] GUO Ping, FU De-sheng, ZHU Jie-zhong and CHENG Ya-ping. Lightweight and Shifted CA Architecture for MANET [J]. Computer Science, 2017, 44(3): 145-149.
[12] LIU Jian-ming and LIN Dao-wei. Research on Network Performance Based on Nomadic Group Mobility Model [J]. Computer Science, 2017, 44(2): 140-146.
[13] HU Chang-jun and YUAN Shu-jie. Node Forwarding Strategy with Collision Estimation in Urban Vehicular Ad Hoc Networks [J]. Computer Science, 2017, 44(10): 113-116.
[14] QI Quan, WANG Ke-ren and DU Yi-hang. Cooperative Spectrum Sensing Based on Reputation Mechanism in Cognitive Ad hoc Networks [J]. Computer Science, 2017, 44(10): 103-108.
[15] WANG Wei, WANG Jia-jun, WANG Ming-ming, ZHANG Wen-jing and CHEN Jin-guang. Defense Technology Based on Dynamic Space-Time Performance for Flooding Attacks in Mobile Ad Hoc Networks [J]. Computer Science, 2017, 44(1): 159-166.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!