A Neighbor Discovery Algorithm for UAV Networking Based on Directional Antennas

一种基于定向天线的蜂群组网邻居发现算法

¹ School of Cyberspace Security, Northwestern Polytechnical University, Xi'an 710072, China
² Science and Technology on Communication Networks Laboratory, Shijiazhuang 050081, China

Received: 12 March 2019

Abstract

Using directional antennas in Unmanned Aerial Vehicle (UAV) swarm has many advantages, such as longer transmission range, spatial reuse, anti-jamming and low probability of intercept. Neighbor discovery is a crucial step in the initialization of UAV networking. We introduce a neighbor discovery algorithm based on iterative common neighbors (ICN-ND), which can reduce the time of neighbor discovery process and the networking delay. To avoid the huge exchange-data quantity, we use the orientation and distance to represent the neighbor's location instead of latitude and longitude. Compared with the scan-based algorithm, the ICN-ND has better performance on the time to complete the neighbor discovery process and the convergence speed, which is validated the practicality by QualNet simulations.

摘要

采用定向天线进行蜂群组网，具有空间复用度高、信号传输距离远、抗干扰以及低截获的先天优势。无人机蜂群在编队前期，需要快速发现相邻节点进行组网，因此邻居发现是组网的必要前提，对MAC层和网络层的相关设计有着重要的影响。针对采用定向天线的组网模式，在基于扫描方式的邻居发现规划型算法（scan-base algorithm-deterministic，SBA-D）的基础上，提出了基于邻居交集迭代发现的方案（neighbor discovery algorithm based on iterative common neighbors，ICN-ND），充分利用已知的邻居信息，在相邻节点之间寻找邻居集合中的交集，利用公共邻居来提高邻居发现的效率，加快邻居发现的过程，进而降低无人机前期组网的时延，此外为了降低邻居信息交互的数据量，对表征邻居位置的数据结构进行了优化。最后的仿真实验表明，在不同节点密度和不同天线波束宽度下，ICN-ND算法收敛速度以及发现全部邻居所需时隙数远远优于SBA-D。

1. Singh P J, Silva R D. SEHER I[J]. Comparison of Communication Protocols for UAVs and VANETs[C]//2016 International Conference on Computing, Communication and Automation, Noida, 2016: 616–619 [Article] [Google Scholar]
2. Park M, Jung J. An Analysis of Communication Performance According to Antenna Directionality in UAV Operation Environment[C]//2010 2nd IEEE International Conference on Network Infrastructure and Digital Content, Beijing, 2010: 854–857 [Google Scholar]
3. Pottinger T, Yousefi'Zadeh M, White A. Integrating Directional Links with Omni-Directional Tactical MANET Stack: an Experimental Analysis[C]//MILCOM 2006-2006 IEEE Military Communications Conference, Washington, DC, 2006: 1–7 [Article] [Google Scholar]
4. Tehrani A S, Molisch A F, Caire G. Directional Zigzag: Neighbor Discovery with Directional Antennas[C]//58th IEEE Global Communications Conference, San Diego, CA, United states, 2015 [Article] [Google Scholar]
5. Li Guihua. Status and Trend of Foreign Military Data Link for Unmanned Aerial Vehicles[J]. Telecommunication Engineering, 2014, 54(6): 851–856 [Article] (in Chinese) [Google Scholar]
6. 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 Trans on Networking, 2017, 25(4): 1982–1993 [Article] [CrossRef] [Google Scholar]
7. Ramanathan R, Redi J, Santivanez C, et al. Ad Hoc Networking with Directional Antennas: a Complete System Solution[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(3): 496–506 [Article] [CrossRef] [Google Scholar]
8. Du J, Kranakis E, Ponce O M, et al. Neighbor Discovery in a Sensor Network with Directional Antennae[J]. Adhoc & Sensor Wireless Netowrks, 2016, 30(4): 261–286 [Article] [Google Scholar]
9. Zhang Z, Li B. Neighbor Discovery in Mobile Ad Hoc Self-Configuring Networks with Directional Antennas: Algorithms and Comparisons[J]. IEEE Trans on Wireless Communications, 2008, 7(5): 1540–1549 [Article] [CrossRef] [Google Scholar]
10. Cai H, Wolf T. On 2-Way Neighbor Discovery in Wireless Networks with Directional Antennas[C]//2015 IEEE Conference on Computer Communications, 2015: 702–710 [Article] [Google Scholar]
11. Zhao S, Liu Y, Yang T, et al. 3-Way Multi-Carrier Asynchronous Neighbor Discovery Algorithm Using Directional Antennas[C]//2016 IEEE Wireless Communications and Networking Conference, Doha, 2016: 1–6 [Article] [Google Scholar]
12. Vasudevan S, Towsley D, Goeckel D, et al. Neighbor Discovery in Wireless Networks and the Coupon Collector's Problem[C]//Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, 2009: 181–192 [Article] [Google Scholar]
13. Zhenshang Z. Performance of Neighbor Discovery Algorithms in Mobile Ad Hoc Self-Configuring Networks with Directional Antennas[C]//MILCOM 2005, 2005: 3162–3168 [Article] [Google Scholar]
14. Zhang D, He T, Liu Y, et al. Poster: Neighbor Discovery with Distributed Quorum System[C]//International Conference on Embedded Networked Sensor Systems, Seattle, WA, USA, 2011: 369–370 [Article] [Google Scholar]
15. An X, Hekmat R. Self-Adaptive Neighbor Discovery in Ad Hoc Networks with Directional Antennas[C]//2007 16th IST Mobile and Wireless Communications Summit, 2007: 1–5 [Article] [Google Scholar]
16. Tian F, Liu B, Cai H, et al. Practical Asynchronous Neighbor Discovery in Ad Hoc Networks with Directional Antennas[J]. IEEE Trans on Vehicular Technology, 2016, 65(5): 3614–3627 [Article] [CrossRef] [Google Scholar]
17. Khamlichi B E, Nguyen D H J, Abbadi J E, et al. Learning Automaton Based Neighbor Discovery for Wireless Networks Using Directional Antennas[J]. IEEE Wireless Communications Letters, 2018, 8(1): 69–72 [Article] [CrossRef] [Google Scholar]