ON OBLIVIOUS NEIGHBOR DISCOVERY IN DISTRIBUTED WIRELESS NETWORKS WITH DIRECTIONAL ANTENNAS: THEORETICAL FOUNDATION AND ALGORITHM DESIGN
Neighbor discovery, one of the most fundamentalbootstrapping networking primitives, is particularly challengingin decentralized wireless networks where devices have directionalantennas. In this paper, we study the following fundamentalproblem, which we term oblivious neighbor discovery: Howcan neighbor nodes with heterogeneous antenna conﬁgurationsdiscover each other within a bounded delay in a fully decentralisedmanner without any prior coordination or synchronisation?We establish a theoretical framework on the obliviousneighbor discovery and the performance bound of any neighbordiscovery algorithm achieving oblivious discovery. Guided by thetheoretical results, we then devise an oblivious neighbor discoveryalgorithm, which achieves guaranteed oblivious discovery withorder-minimal worst case discovery delay in the asynchronousand heterogeneous environment. We further demonstrate howour algorithm can be conﬁgured to achieve a desired tradeoffbetween average and worst case performance.
we formulate the following oblivious neighbordiscovery problem. How can neighbor nodes with heterogeneousantenna beamwidth discover each other within abounded delay in a fully decentralised manner without anyprior coordination or synchronisation? Particularly, the followingrequirements should be satisﬁed:• Bounded and minimum worst-case discovery delay;• Discovery oblivity, the capability of guaranteeing discoveryregardless of the antenna beamwidth and the relativepositions of nodes. This requirement is particular in theneighbor discovery with directional antennas.As summarized in Section II, no existing work to ourknowledge can satisfy the above requirements simultaneously.Aiming at providing a comprehensive investigationon oblivious neighbor discovery, we articulate our work asfollows:• Theoretical framework. We establish a theoretical frameworkon oblivious neighbor discovery and establish theperformance bound of any oblivious neighbor discoveryalgorithm. Our theoretical results not only shed light onthe structure of the problem, but also serve as designguidelines for oblivious neighbor discovery algorithms.• Algorithm design. Guided by the theoretical results,we further design an oblivious neighbor discovery algo-rithm and prove that it achieves guaranteed obliviousdiscovery with order-minimal worst-case discovery delayin the asynchronous and heterogeneous environment.We further demonstrate how the algorithm can be conﬁguredto achieve a desired trade-off between average andworst-case performance.
As discussed in Section I, designing efﬁcient neighbordiscovery algorithms for devices with directional antennas isparticularly challenging. A natural approach to contour thechallenge is to use omni-directional antennas in the neighbordiscovery process for major neighbor discoveryalgorithms with omni-directional antennas). The maindisadvantages of this approach is two-fold. Firstly, it requiresan additional omni-directional antenna; Secondly, the discoveredneighbor set using the omni-directional antenna can besigniﬁcantly different from that using the directional one.Neighbor discovery algorithms using purely directionalantennas can be categorised into two classes, probabilisticand deterministic algorithms. In probabilistic approache, each node randomly chooses a direction tosteer its antenna. Probabilistic algorithms have the advantagesof being memoryless and stationary and thus are especiallyrobust and suitable in decentralised environments where noprior coordination or synchronisation is available. The maindrawback of them is the lack of performance guarantee interms of discovery delay. This problem is referred to as thelong-tail discovery latency problem in which two neighbornodes may experience extremely long delay before discoveringeach other. Deterministic algorithms, whereeach node points its antenna based on a predeﬁned sequence,are proposed to provide guaranteed upper-bound on the worstcasediscovery delay. However, existing deterministic neighbordiscovery solutions with directional antennas either fail toachieve bounded discovery delay, or require time synchronisationamong nodes, which may be not be practical in manyapplications or require prior coordination among nodes.
We have formulated and studied the oblivious neighbor discoveryproblem. We have established the performance boundof any neighbor discovery algorithm achieving oblivious discovery.Guided by the theoretical results, we have designedan oblivious discovery algorithm and proved that it achievesguaranteed oblivious discovery with order-minimal worst-ase discovery delay in the asynchronous and heterogeneousenvironment. We have then studied how our algorithm canbe conﬁgured to achieve a desired trade-off between averageand worst-case performance. In future research, we plan toinvestigate the energy-constrained case where nodes stay indormant state most of time while only wakes up periodically.
 L. Chen, Y. Li, and A. V. Vasilakos, “Oblivious neighbor discoveryfor wireless devices with directional antennas,” in Proc. INFOCOM,Apr. 2016, pp. 1–9.
 R. Ramanathan, J. Redi, C. Santivanez, D. Wiggins, and S. Polit,“Ad hoc networking with directional antennas: A complete systemsolution,” IEEE J. Sel. Areas Commun., vol. 23, no. 3, pp. 496–506,Mar. 2005.
 R.A.Santosa,B.-S.Lee,C.K.Yeo,andT.M.Lim,“Distributedneighbor discovery in ad hoc networks using directional antennas,” inProc. IEEE CIT, Sep. 2006, p. 97.
 M. J. McGlynn and S. A. Borbash, “Birthday protocols for low energydeployment and ﬂexible neighbor discovery in ad hoc wireless networks,”in Proc. MobiHoc, 2001, pp. 137–145.
 S. Vasudevan, D. Towsley, D. Goeckel, and R. Khalili, “Neighbordiscovery in wireless networks and the coupon collector’s problem,”in Proc. MobiCom, 2009, pp. 181–192.
 P. Dutta and D. Culler, “Practical asynchronous neighbor discovery andrendezvous for mobile sensing applications,” in Proc. Sensys, 2008,pp. 71–84.
 A. Kandhalu, K. Lakshmanan, and R. Rajkumar, “U-connect: A lowlatencyenergy-efﬁcient asynchronous neighbor discovery protocol,” inProc. IPSN, 2010, pp. 350–361.
 M. Bakht, M. Trower, and R. H. Kravets, “Searchlight: Won’t you bemy neighbor,” in Proc. MOBICOM, 2012, pp. 185–196.
 T. Meng, F. Wu, and G. Chen, “On designing neighbor discoveryprotocols: A code-based approach,” in Proc. INFOCOM, 2014,pp. 1689–1697.
 L. Chen, K. Bian, and M. Zheng, “Heterogeneous multi-channel neighbordiscovery formobile sensing applications: theoretical foundationandprotocol design,” in Proc. MobiHoc, 2014, pp. 307–316.