Distributed Heuristics for Maintaining Connectivity in Mobile Networks (SRNTN-54)

Abstract

In a packet radio network, a packet radio (PR) can establish links to any other PR within hearing range, but, if too many PRs are nearby, its link table may overflow. To maintain connectivity and keep their link-table sizes feasible it is necessary for PRs to choose a subset of all possible links. This selection problem resembles the problem of finding spanning trees in a distributed manner. We develop a distributed heuristic for choosing which links should be retained to keep the network connected. Since the heuristic uses only local information, it cannot guarantee to keep the network connected in those cases that require more global information. The heuristic is of interest because it requires less coordination, less information and, therefore, lower communications overhead than algorithms that guarantee to maintain connectedness. Packet switching; Radio links; Heuristic methods; Algorithms; Decision rules.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1986
Accession Number
ADA219586

Entities

People

  • Robert Willis

Organizations

  • BBN Technologies

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Cellular Networks
  • Chain Reactions
  • Chemical Reactions
  • Communication Networks
  • Computations
  • Computer Communications
  • Computer Programming
  • Computers
  • Convergence
  • Corporations
  • Geographic Regions
  • Guarantees
  • Heuristic Methods
  • Indicators
  • Mobile Phones
  • Networks

Fields of Study

  • Computer science

Readers

  • Computer Networking