A distributed protocol for reducing neighborhood size in radio networks

Author

Shacham, Nachum ; Beyer, David

Author_Institution

SRI Int., Menlo Park, CA, USA

fYear

1988

fDate

12-15 June 1988

Firstpage

458

Abstract

A distributed protocol which specifies how modes select at random a subset of their adjacent link is described. The protocol results in a routing topology with nodal degree that does not exceed a predetermined limit, and allows late entries to be incorporated into the network and partitioned networks to be reconstituted. Simulation of the protocol has demonstrated a threshold effect for global network connectivity with respect to the average nodal degree. Moreover, if nodes are allowed to operate with their degree above the threshold, the probability that the protocol results in a connected routing graph is very close to one. That probability decreases sharply to zero as the nodal maximum degree drops below the threshold. Specifically, the threshold has been found to be between 3 and 7 for a large variety of network configuration and protocol conditions.<>

Keywords

packet switching; protocols; radio networks; connected routing graph; distributed protocol; global network connectivity; neighbourhood size reduction; nodal degree; packet radio; packet switching; partitioned networks; radio networks; routing topology; threshold effect; Contracts; Directive antennas; Intelligent networks; Network topology; Packet switching; Radio network; Radio networks; Receivers; Routing protocols; Spread spectrum communication;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, 1988. ICC '88. Digital Technology - Spanning the Universe. Conference Record., IEEE International Conference on

Conference_Location

Philadelphia, PA, USA

Type

conf

DOI

10.1109/ICC.1988.13608

Filename

13608