On Expected Neighbor Discovery Time With Prior Information: Modeling, Bounds and Optimization
Open Access
- 27 October 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Wireless Communications
- Vol. 17 (1) , 339-351
Abstract
Neighbor discovery (ND) is an essential prerequisite for any peer-to-peer communication. In general, minimizing the discovery time is the goal for ND schemes. In this paper, we study the average discovery time for directional random ND when nodes have prior information about their set of possible neighbors, which also helps identify the performance limits of random ND schemes. Typically, discovery time analysis is done for assumptions that simplify the network structure, such as uniform neighbor relations for all nodes. However, with prior information the directional transmission probabilities depend on the node and the direction. This complicates the analysis of the expected discovery time. We first provide a closed-form expression for the expected discovery time based on the non-uniform coupon collector problem. Next, we identify directional transmission probabilities of each node that achieve a small discovery time. Due to the mathematical complexity, we provide a lower and an upper bound on the expected discovery time, which allows us to write the problem as a convex optimization problem. Through simulations, we demonstrate the performance gain due to prior knowledge with the proposed methods as compared with when no prior information is available, as well as the impact of uncertainty in the prior knowledge.Keywords
Funding Information
- 5G program of Intel Corporate Research
- National Science Foundation (CNS-1457340 (in the WiFiUS program), CCF-1423140)
This publication has 29 references indexed in Scilit:
- New Results on a Generalized Coupon Collector Problem Using Markov ChainsJournal of Applied Probability, 2015
- On 2-way neighbor discovery in wireless networks with directional antennas2015
- Energy-Efficient D2D Discovery for Proximity Services in 3GPP LTE-Advanced Networks: ProSe Discovery MechanismsIEEE Vehicular Technology Magazine, 2014
- Device-to-Device Discovery for Proximity-Based Service in LTE-Advanced SystemIEEE Journal on Selected Areas in Communications, 2014
- Enabling D2D Communications Through Neighbor Discovery in LTE Cellular NetworksIEEE Transactions on Signal Processing, 2014
- Neighbor Discovery in Wireless Networks with Multipacket ReceptionIEEE Transactions on Parallel and Distributed Systems, 2014
- What Will 5G Be?IEEE Journal on Selected Areas in Communications, 2014
- COUPON COLLECTINGProbability in the Engineering and Informational Sciences, 2008
- Majorization and Schur Convexity—I2005
- Birthday paradox, coupon collectors, caching algorithms and self-organizing searchDiscrete Applied Mathematics, 1992