Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (3): 306-317.doi: 10.11896/jsjkx.240600108

• Computer Network • Previous Articles     Next Articles

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

CLC Number: 

  • 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.
[1] LU Yanfeng, WU Tao, LIU Chunsheng, YAN Kang, QU Yuben. Survey of UAV-assisted Energy-Efficient Edge Federated Learning [J]. Computer Science, 2024, 51(4): 270-279.
[2] ZHAO Luo-cheng, QU Zhi-hao, XIE Zai-peng. Study on Communication Optimization of Federated Learning in Multi-layer Wireless Edge Environment [J]. Computer Science, 2022, 49(3): 39-45.
[3] GUO Yi-shan, LIU Man-dan. Anomaly Detection Based on Spatial-temporal Trajectory Data [J]. Computer Science, 2021, 48(6A): 213-219.
[4] HE Quan-qi, YU Fei-hong. Review of Low Power Architecture for Wireless Network Cameras [J]. Computer Science, 2021, 48(6A): 369-373.
[5] PENG Da-chuan, YANG Xi-min, TANG Wan, ZHANG Xiao, FAN Lei. Dual-NIC Mutual Backup Scheme for Access Point Handoff in Software Defined Wireless Networks [J]. Computer Science, 2021, 48(6A): 427-431.
[6] QIAN Guang-ming, YI Chao. Real Time Wireless Connection Scheme for Multi-nodes [J]. Computer Science, 2021, 48(11A): 446-451.
[7] YANG Zhang-lin, XIE Jun, ZHANG Geng-qiang. Review of Directional Routing Protocols for Flying Ad-Hoc Networks Based on Directional Antennas [J]. Computer Science, 2021, 48(11): 334-344.
[8] JI Xiao-xiang, SHEN Hang, BAI Guang-wei. Non-orthogonal Multiple Access Enabled Scalable Video Multicast in HetNets [J]. Computer Science, 2021, 48(11): 356-362.
[9] CAO Su-e, YANG Ze-min. Prediction of Wireless Network Traffic Based on Clustering Analysis and Optimized Support Vector Machine [J]. Computer Science, 2020, 47(8): 319-322.
[10] TAO Yang,JI Rui-juan,YANG Li,WANG Jin. Study on Dynamic Priority Admission Control Algorithm in Heterogeneous Wireless Networks [J]. Computer Science, 2020, 47(3): 242-247.
[11] LIANG Tao, WANG Tong-xiang, LIU Jian-wei, YANG Jing. Modeling of Jamming Attack and Performance Analysis in Multi-hop Wireless Network [J]. Computer Science, 2019, 46(11A): 414-416.
[12] GUO Bin, YU Dan-dan, LU Wei, HUANG Ming-he, ZENG Ya-lin. Selective Network Coding Strategy Based on Packet Loss Prediction [J]. Computer Science, 2019, 46(11A): 399-404.
[13] YAO Xin-wei, ZHANG Meng-na, WANG Wan-liang, YANG Shuang-hua. Optimal Energy Allocation Algorithm with Energy Harvesting and Hybrid Energy Storage for Microscale Wireless Networks [J]. Computer Science, 2018, 45(8): 75-79.
[14] HAN Xiu-ping, WANG Zhi, PEI Dan. Study on Wi-Fi Fingerprint Anonymization for Users in Wireless Networks [J]. Computer Science, 2018, 45(8): 7-12.
[15] XU Wen-hao, SHEN Hang and BAI Guang-wei. Link Burstiness-aware Opportunistic Routing Protocol in Wireless Networks [J]. Computer Science, 2018, 45(5): 83-88.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.