计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (3): 306-317.doi: 10.11896/jsjkx.240600108

• 计算机网络 • 上一篇    下一篇

定向无线自组网中的邻居发现算法综述

李想1, 朱小军2, 冯斯梦1, 董超1, 张磊1   

  1. 1 南京航空航天大学电子信息工程学院 南京 211106
    2 南京航空航天大学计算机科学与技术学院 南京 211106
  • 收稿日期:2024-06-17 修回日期:2024-09-17 出版日期:2025-03-15 发布日期:2025-03-07
  • 通讯作者: 董超(dch@nuaa.edu.cn)
  • 作者简介:(lx717@nuaa.edu.cn)
  • 基金资助:
    国家自然科学基金重点项目(61931011);国家自然科学基金面上项目(62372230)

Overview of Neighbor Discovery Algorithms in Directional Wireless Ad Hoc Networks

LI Xiang1, ZHU Xiaojun2, FENG Simeng1, DONG Chao1, ZHANG Lei1   

  1. 1 College of Electronic and Information Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
    2 College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
  • Received:2024-06-17 Revised:2024-09-17 Online:2025-03-15 Published:2025-03-07
  • About author:LI Xiang,born in 2001,postgraduate.His main research interest is UAV beehive networking.
    DONG Chao,born in 1980,Ph.D,professor.His main research interests include UAV cluster intelligent network and low-altitude intelligent network.
  • Supported by:
    Key Program of the National Natural Science Foundation of China(61931011) and Surface Project of the National Natural Science Foundation of China(62372230).

PDF (PC)

180

摘要： 对当前无线定向自组网领域中的定向邻居发现算法的相关研究成果进行了系统性总结。首先,从定向自组网在无线通信中的重要性出发,介绍了相关背景知识和基本概念,指出其在无线通信领域的研究前景。然后,依据不同的技术标准,对定向邻居发现算法进行了多个维度的分类和比较,分别深入探讨了各种算法在不同应用场景下的适用性和局限性,具体分类包括基于扫描序列设计的确定性和随机性算法、同步和异步算法、纯定向和全向辅助发现算法、全盲和半盲算法,以及直接和间接邻居发现算法。接着,结合提出的分类方法以及算法的实际应用情况,详细阐述了部分重要定向邻居发现算法的设计原理及其收敛过程,包括确定及随机性邻居发现算法、异步邻居发现算法,以及利用机器学习技术的优化算法。最后,探讨了定向邻居发现算法的未来研究方向及应用趋势。

关键词: 邻居发现, 定向天线, 定向自组网, 无线网络, 扫描序列, 异步算法

Abstract: A systematic summary is provided for the research achievements in directional neighbor discovery algorithms within the current domain of wireless directional ad hoc networks.Initially,stemming from the crucial significance of directional ad hoc networks in wireless communication,relevant background knowledge and fundamental concepts are introduced,delineating its research prospects in the realm of wireless communication.Subsequently,based on distinct technical standards,directional neighbor discovery algorithms are categorized and compared across multiple dimensions,delving into various applicable scenarios and associated limitations.Specific classifications include deterministic and random algorithms based on scanning sequence design,synchronous and asynchronous algorithms,purely directional and omnidirectional-assisted discovery algorithms,blind and semi-blind algorithms,as well as direct and indirect neighbor discovery algorithms.Moreover,by integrating the proposed classification methodology with the practical application scenarios of algorithms,the design principles and convergence processes of significant directional neighbor discovery algorithms are elaborately elucidated,including deterministic and random neighbor discovery algorithms,asynchronous neighbor discovery algorithms,and optimization algorithms utilizing machine learning techniques.Lastly,the future research directions and application trends of directional neighbor discovery algorithms are deliberated upon.

Key words: Neighbor discovery, Directional antenna, Directional ad hoc network, Wireless network, Scanning sequence, Asynchronous algorithm

中图分类号: 

  • TN827+.4
[1]JAHIR Y,ATIQUZZAMAN M,REFAI H,et al.Routing protocols and architecture fordisaster area network:A survey[J].Ad Hoc Networks,2019,82:1-14.
[2]PAPAKOSTAS D,ESHGHI S,KATSAROS D,et al.Energy-aware backbone formation in military multilayer ad hoc networks[J].Ad Hoc Networks,2018,81:17-44.
[3]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,2018,7(1):60-73.
[4]OJHA T,MISRA S,RAGHUWANSHI N S.Wireless sensornetworks for agriculture:The state-of-the-art in practice and future challenges[J].Computers and Electronics in Agriculture,2015,118:66-84.
[5]WU J J,ZHU X J,DONG C,et al.Research on Spectrum Sampling Performance for UAV Spectral Reconnaissance [J].Radio Communications Technology,2023,49(3):438-446.
[6]SORRIBES J V,LLORET J,PEÑALVER L.Analytical models for randomized neighbor discovery protocols based on collision detection in wireless ad hoc networks[J].Ad Hoc Networks,2022,126:102739.
[7]CHEN L,BIAN K.Neighbor discovery in mobile sensing applications:A comprehensive survey[J].Ad Hoc Networks,2016,48:38-52.
[8]HUANG H J,ZHOU T,WANG G C.Study on Energy Con-sumption of ZigBee Networks Based on Distributed Neighbor Discovery Mechanism[J].Computer Science,2016,43(5):67-72,112.
[9]YANG Z L,XIE J,ZHANG G Q.Review of Directional RoutingProtocols for Flying Ad-Hoc Networks Based on Directional Antennas[J].Computer Science,2021,48(11):334-344.
[10]WU Z M,QIU Z L.A Survey on Directional Antenna Networking[C]//2011 7th International Conference on Wireless Communications,Networking and Mobile Computing.2011:1-4.
[11]DAI H,NG K,LI M,et al.An overview of using directional antennas in wireless networks[J].International Journal of Communication Systems,2013,26(4):413-448.
[12]JIALIANG Z,SOUNG C L.Capacity Improvement of Wireless Ad Hoc Networks with Directional Antennae[C]//2006 IEEE 63rd Vehicular Technology Conference.2006:911-915.
[13]WANG J Y,MA Y,LU R R,et al.Hovering UAV-based FSO communications:Channel modelling,performance analysis,and parameter optimization[J].IEEE Journal on Selected Areas in Communications,2021,39(10):2946-2959.
[14]INTERNET ENGINEERING TASK FORCE.RFC 8161:benchmarking the neighbor discovery protocol[S].Los Ange-les:IETF,2017.
[15]HUGHES L E.Third Generation Internet Revealed:Reinventing Computer Networks with IPv6[M].A Press,2022.
[16]STEENSTRUP M.Neighbor discovery among mobile nodes equipped with smart antennas[J/OL].https://api.semanticscholar.org/CorpusID:59889440.
[17]VASUDEVAN S,KUROSE J,TOWSLEY D.On neighbor discovery in wireless networks with directional antennas[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.2005:2502-2512.
[18]BAKHT M,TROWER M,KRAVETS R H.Searchlight:won’t you be my neighbor?[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.2012:185-196.
[19]MAEKAWA M.A √N Algorithm for Mutual Exclusion in Decentralized Systems[J].ACM Trans.Compute.Syst.,1985,3(2):145-159.
[20]YU-CHEE T,CHIH-SHUN H,TEN-YUENG H.Power-saving protocols for IEEE 802.11-based multi-hop ad hoc networks[C]//Proceedings Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.2002:200-209.
[21]LAI S,RAVINDRAN B,CHO H.Heterogenous Quorum-Based Wake-Up Scheduling in Wireless Sensor Networks[J].IEEE Transactions on Computers,2010,59(11):1562-1575.
[22]KHATIBI S,ROHANI R.Quorum-based neighbor discovery in self-organized cognitive MANET[C]//21st Annual IEEE International Symposium on Personal,Indoor and Mobile Radio Communications.2010:2239-2243.
[23]MCGLYNN M J,BORBASH S A.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[C]//Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking & Computing.2001:137-145.
[24]CHEN L,BIAN K.Neighbor discovery in mobile sensing applications:A comprehensive survey[J].Ad Hoc Networks,2016,48:38-52.
[25]PANDEY S,SHUKLA P,KALWANI D.Birthday Protocol for Efficient Node Deployment and Neighbor Discovery in Wireless Sensor Network[C]//2021 Third International Conference on Intelligent Communication Technologies and Virtual Mobile Networks(ICICV).2021:189-195.
[26]ZHANG Z.Pure directional transmission and reception algo-rithms in wireless ad hoc networks with directional antennas[C]//IEEE International Conference on Communications.2005:3386-3390.
[27]LI K,AKBAS M I,TURGUT D,et al.Reliable positioning with hybrid antenna model for aerial wireless sensor and actor networks[C]//2014 IEEE Wireless Communications and Networking Conference(WCNC).2014:2904-2909.
[28]PARK H,KIM Y,SONG T,et al.Multiband Directional Neighbor Discovery in Self-Organized mmWave Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2015,64(3):1143-1155.
[29]WEI Z,LIU X,HAN C,et al.Neighbor Discovery for Un-manned Aerial Vehicle Networks[J].IEEE Access,2018,6:68288-68301.
[30]ZHU L B,WANG S C,WEI H X,et al.A potential neighbordiscovery algorithm in directional UAV ad hoc networks based on collaboration[J].Radio Engineering,2023,53(6):1438-1443.
[31]LIANG X Y.Research on Neighbor Discovery and Resource Allocation in Directed Ad Hoc Networks[D].Chengdu:University of Electronic Science and Technology of China,2021.
[32]DING C,PEI D,SALOMAA A.Chinese Remainder Theorem:Applications in Computing,Coding,Cryptography[M].World Scientific,1996.
[33]HONG L,LUO P T,YAN X,et al.A Neighbor Discovery Algo-rithm for UAV Networking Based on Directional Antennas[J].Journal of Northwestern Polytechnical University,2020,38(1):191-198.
[34]ZHANG W,PENG L X,XU R H,et al.Neighbor Discovery in Radar Communications Ad Hoc Networks[J].Communications Technology,2017,50(4):701-706.
[35]ZHANG Z,LI B.Neighbor discovery in mobile ad hoc self-configuring networks with directional antennas:algorithms and comparisons[J].IEEE transactions on wireless communications,2008,7(5):1540-1549.
[36]PARK J S,CHO S W,SANADIDI M Y,et al.An analyticalframework for neighbor discovery strategies in ad hoc networks with sectorized antennas[J].IEEE Communications Letters,2009,13(11):832-834.
[37]CAI H,WOLF T.On 2-way neighbor discovery in wireless networks with directional antennas[C]//2015 IEEE Conference on Computer Communications(INFOCOM).2015:702-710.
[38]NUR F N,SHARMIN S,HABIBM A,et al.CollaborativeNeighbor Discovery in Directional Wireless Sensor Networks[C]//2016 IEEE Region 10 Conference(TENCON).2016:1097-1100.
[39]LIU L,PENG L,XU R,et al.A Neighbor Discovery Algorithm for Flying Ad Hoc Network Using Directional Antennas[C]//2019 28th Wireless and Optical Communications Conference(WOCC).2019:1-5.
[40]SONG Y,ZENG L,LIU Z,et al.Cross-Layer Optimization Spatial Multi-Channel Directional Neighbor Discovery with Random Reply in mmWave FANET[J].Electronics,2022,11(10):1566.
[41]ZHANG W,PENG L,XU R,et al.Neighbor discovery in three-dimensional mobile ad hoc networks with directional antennas[C]//2016 25th Wireless and Optical Communication Confe-rence(WOCC).2016:1-5.
[42]WU Q,WEI Z,PAN C,et al.Joint Neighbor Discovery and Positioning for Unmanned Aerial Vehicle Networks[C]//2021 IEEE 94th Vehicular Technology Conference(VTC2021-Fall).2021:1-5.
[43]XIA Q,JORNET J M.Expedited Neighbor Discovery in Directional Terahertz Communication Networks Enhanced by Antenna Side-Lobe Information[J].IEEE transactions on vehicular technology,2019,68(8):7804-7814.
[44]BAI W,XU Y,WANG J,et al.Cognitive Neighbor DiscoveryWith Directional Antennas in Self-Organizing IoT Networks[J].IEEE Internet of Things Journal,2021,8(8):6865-6877.
[45]STEENSTRUP M.Neighbor discovery among mobile nodes equipped with smart antennas[C]//ADHOC’03.Los Angles:IEEE Press,2003:120-129.
[46]ZHANG Z.DTRA:directional transmission and reception algorithms in WLANs with directional antennas for QoS support[J].IEEE Network,2005,19(3):27-32.
[47]ZAHNG Z.Performance of neighbor discovery algorithms inmobile ad hoc self-configuring networks with directional antennas[C]//2005 IEEE Military Communications Conference.2005:3162-3168.
[48]XIONG W,LIU B,LIN G.Neighbor Discovery with Directional Antennas in Mobile Ad-Hoc Networks[C]//2011 IEEE Global Telecommunications Conference.2011:1-5.
[49]CAI H,LIU B,GUI L,et al.Neighbor discovery algorithms in wireless networks using directional antennas[C]//2012 IEEE International Conference on Communications(ICC).2012:767-772.
[50]YANG A,LI B,YAN Z,et al.A Bi-Directional Carrier SenseCollision Avoidance Neighbour Discovery Algorithm in Directional Wireless Ad Hoc Sensor Networks[J].Sensors,2019,19(9):2120.
[51]LAN H,LIU G,WANG W,et al.Three-dimensional scan-based algorithm for directional neighbor discovery in ad hoc networks[J].International Journal of Communication Systems,2023,36(10):e5496.
[52]KHATIBI S,DEHGHAN M,POORMINA M A.Quorum-based pure directional neighbor discovery in self-organized ad hoc networks[C]//2010 5th International Symposium on Telecommunications.2010:476-481.
[53]JEHN-RUEY J,YU-CHEE T,CHIH-SHUN H,et al.Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks[C]//2003 International Conference on Parallel Processing.2003:257-264.
[54]CHEN L Y,YAN B S,ZHANG J Y,et al.Neighbor discovery algorithm in mobile low duty cycle WSNs[J].Journal of Software,2014,25(6):1352-1368.
[55]ZHANG D,HE T,YE F,et al.Neighbor Discovery and Rendezvous Maintenance with Extended Quorum Systems for Mobile Applications[J].IEEE Transactions on Mobile Computing,2017,16(7):1967-1980.
[56]ZHANG D,HE T,YE F,et al.EQS:Neighbor Discovery andRendezvous Maintenance with Extended Quorum System for Mobile Sensing Applications[C]//2012 IEEE 32nd Interna-tional Conference on Distributed Computing Systems.2012:72-81.
[57]CAI H,WOLF T.Self-Adapting Quorum-Based Neighbor Discovery in Wireless Sensor Networks[C]//IEEE INFOCOM 2018－IEEE Conference on Computer Communications.2018:324-332.
[58]XIA Z,GAO Z,LIU A,et al.AQND:An asymmetric quorum-based neighbor discovery protocol for reducing delay in sensor based systems[J].Information Sciences,2024,654:119820.
[59]DUTTA P,CULLER D.Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications[C]//SenSys ’08.New York,NY,USA,2008:71-84.
[60]CHEN L,LI Y,VASILAKOS A V.On Oblivious Neighbor Discovery in Distributed Wireless Networks With Directional Antennas:Theoretical Foundation and Algorithm Design[J].IEEE/ACM Transactions on Networking,2017,25(4):1982-1993.
[61]HONG X,LV N,REN Z.Oblivious neighbor discovery algo-rithms in airborne networks with directional multi-antenna[J].Ad Hoc Networks,2023,141:103074.
[62]MURAWSKI R,FELEMBAN E,EKICI E,et al.Neighbor discovery in wireless networks with sectored antennas[J].Ad Hoc Networks,2012,10(1):1-18.
[63]YANG W,BO L,LIN G.Adaptive Scan-based AsynchronousNeighbor Discovery in wireless networks using directional antennas[C]//2013 International Conference on Wireless Communications and Signal Processing.2013:1-6.
[64]WANG Y,ZHANG T,MAO S,et al.Directional neighbor discovery in mmWave wireless networks[J].Digital Communications and Networks,2021,7(1):1-15.
[65]ZHOU Z H.Machine Learning[M].Beijing:Tsinghua University Press,2016.
[66]HUANG S,LI M,ZHAO L.An intelligent neighbor discovery algorithm for Ad Hoc networks with directional antennas[C]//Proceedings 2013 International Conference on Mechatronic Sciences,Electric Engineering and Computer(MEC).2013:302-305.
[67]LI M,ZHAO L.Simulation of Neighbor Discovery Algorithm for Directional Antenna Ad Hoc Networks Based on OPNET [J].Journal of System Simulation,2018,30(5):1707-1714.
[68]KHAMLICHI B E,ABBADI J E,ROWE N W,et al.Adaptive Directional Neighbor Discovery Schemes in Wireless Networks[C]//2020 International Conference on Computing,Networking and Communications(ICNC).2020:332-337.
[69]WANG Y,PENG L,XU R,et al.A Fast Neighbor Discovery Algorithm Based on Q-learning in Wireless Ad Hoc Networks withDirectional Antennas[C]//2020 IEEE 6th International Conference on Computer and Communications(ICCC).IEEE,2020:467-472.
[70]GAO J,TANG H,SUI C,et al.Adaptive Neighbor Discovery Scheme for Directional Ad Hoc Network[C]//ICCBN’21.New York,NY,USA,2021:222-226.
[71]JIANG J,WANG S,HAN G,et al.Reinforcement-Learning-Based Adaptive Neighbor Discovery Algorithm for Directional Transmission-Enabled Internet of Underwater Things[J].IEEE Internet of Things Journal,2023,10(10):9038-9048.
[72]EL KHAMLICHI B,NGUYEN D H N,EL ABBADI J,et al.Learning Automaton-Based Neighbor Discovery for Wireless Networks Using Directional Antennas[J].IEEEWireless Communications Letters,2019,8(1):69-72.
[73]LOEVENICH J F,RETTORE P H L,LOPES R R F,et al.A Bayesian Inference Model for Dynamic Neighbor Discovery in Tactical Networks[J].Procedia Computer Science,2022,205:28-38.
[74]WANG X,LI J,NING Z,et al.Wireless powered mobile edgecomputing networks:A survey[J].ACM Computing Surveys,2023,55(13s):1-37.
[75]WEI Z,LIANG Y,MENG Z,et al.Fast neighbor discovery forwireless ad hoc network with successive interference cancellation[J].IEEE Transactions on Vehicular Technology,2024,73(1):1322-1336.
[76]IVANOV V,TERESHONOK M.Cross-Layer Methods for Ad Hoc Networks－Review and Classification[J].Future Internet,2024,16(1):29.
[77]PUHL Z T,GUO J.Securing IPv6 Neighbor Discovery Address Resolution with Voucher-Based Addressing[J].2024,4(3):338-366.
[78]SHAH S M,SUN Z,ZAMAN K,et al.Advancements in neighboring-based energy-efficient routing protocol(NBEER) for underwater wireless sensor networks[J].Sensors,2023,23(13):6025.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发