Analytical Model for Initialization of Single Hop Packet Radio Networks

Recent studies have shown that packet radio networks (PRNET) can easily be saturated and become unstable unless efficient routing and flow control algorithms are used. To enable point-to-point packet transportation, network stations assign a code (label) to each repeater; the process of assigning such labels is referred to as "network initialization." The initialization procedure assumes that the network topology is not known a priori and is changing with time. Thus, the initialization procedure involves mapping of network topology, determining network structure (labels for repeaters), and transmitting labels to the repeaters. Although many authors have developed analytical models to study channel access schemes, no one has yet addressed directly the initialization issue. In this paper we present two models which enable one to estimate the optimal rates at which repeaters and stations must transmit connectivity information to minimize the network initialization time in a one-hop network. The first model assumes complete interference (all repeaters can communicate directly with each other), while the second (but more complex) model can provide initialization time under partial interference pattern. With these models we illustrate the effects of varying repeater and station transmission rates for small networks. Our most important results are that the network initialization time is relatively insensitive to the station transmission rate, but the repeater transmission rate must be carefully chosen to achieve rapid initialization.