NDLI: Neighbor discovery in wireless networks and the coupon collector's problem

Please wait, while we are loading the content...

Dynamic spectrum access in DTV whitespaces: design rules, architecture and algorithms

SAM: enabling practical spatial multiple access in wireless LAN

Capacity of large-scale CSMA wireless networks

Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links

Neighbor discovery in wireless networks and the coupon collector's problem

A scalable micro wireless interconnect structure for CMPs

SurroundSense: mobile phone localization via ambience fingerprinting

OpenLIDS: a lightweight intrusion detection system for wireless mesh networks

Mining spectrum usage data: a large-scale spectrum measurement study

Order matters: transmission reordering in wireless networks

Scheduling partition for order optimal capacity in large-scale wireless networks

Compressive data gathering for large-scale wireless sensor networks

Frequency-aware rate adaptation and MAC protocols

Glia: a practical solution for effective high datarate wifi-arrays

Fine-grained I/O access control of the mobile devices based on the Xen architecture

On the effectiveness of secret key extraction from wireless signal strength in real environments

A quorum-based framework for establishing control channels in dynamic spectrum access networks

Design, implementation and evaluation of an efficient opportunistic retransmission protocol

Mobility increases the connectivity of K-hop clustered wireless networks

Data fusion improves the coverage of wireless sensor networks

Optimal beam scheduling for multicasting in wireless networks

Link layer behavior of body area networks at 2.4 GHz

A fundamental scalability criterion for data aggregation in VANETs

Localization with snap-inducing shaped residuals (SISR): coping with errors in measurement

Throughput-efficient sequential channel sensing and probing in cognitive radio networks under sensing errors

Esense: communication through energy sensing

Lifetime and coverage guarantees through distributed coordinate-free sensor activation

Challenge: ultra-low-power energy-harvesting active networked tags (EnHANTs)

CENTAUR: realizing the full potential of centralized wlans through a hybrid data path

Hiding stars with fireworks: location privacy through camouflage

Neighbor discovery in wireless networks and the coupon collector's problem

Content Provider	ACM Digital Library
Author	Towsley, Donald Goeckel, Dennis Khalili, Ramin Vasudevan, Sudarshan
Abstract	Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical {\em Coupon Collector's Problem}. Consequently, we show that each node discovers all its \$n\$ neighbors in an expected time equal to \$ne (\ln n + c)\$, for some constant \$c\$. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a \$\ln n\$ improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing \$n\$ results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.
Starting Page	181
Ending Page	192
Page Count	12
File Format	PDF
ISBN	9781605587028
DOI	10.1145/1614320.1614341
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-09-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Initialization Sensor networks Randomized algorithms Ad hoc networks Neighbor discovery
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Neighbor discovery in wireless networks with multipacket reception

Efficient algorithms for neighbor discovery in wireless networks

PHED: Pre-Handshaking Neighbor Discovery Protocols in full duplex wireless ad hoc networks

Neighbor Discovery in Multichannel Wireless Clique Networks: An Epidemic Approach

Efficient Algorithms for Neighbor Discovery in Wireless Networks

Energy-Efficient Neighbor Discovery in Mobile Ad Hoc and Wireless Sensor Networks: A Survey

Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks

Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Table of Figures Figure 1.1. One-‐hop Model

Maximal Weight Topology Discovery in Ad hoc Wireless Sensor Networks

Neighbor discovery in wireless networks and the coupon collector's problem

Similar Documents

Neighbor discovery in wireless networks with multipacket reception

Efficient algorithms for neighbor discovery in wireless networks

PHED: Pre-Handshaking Neighbor Discovery Protocols in full duplex wireless ad hoc networks

Neighbor Discovery in Multichannel Wireless Clique Networks: An Epidemic Approach

Efficient Algorithms for Neighbor Discovery in Wireless Networks

Energy-Efficient Neighbor Discovery in Mobile Ad Hoc and Wireless Sensor Networks: A Survey

Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks

Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Table of Figures Figure 1.1. One-­‐hop Model

Maximal Weight Topology Discovery in Ad hoc Wireless Sensor Networks

Neighbor discovery in wireless networks and the coupon collector's problem

Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Title: Initialization Algorithms for Wireless Ad-hoc Networks Table of Figures Figure 1.1. One-‐hop Model