CONCURRENCE PROBABILITIES FOR A LOCALLY SLOTTED PACKET RADIO NETWORK BY COMBINATORIAL METHODS

Locally time-synchronized slot systems for broadcast communication in packet radio networks are considered. In slot systems for broadcast, a fixed clock period is subdivided into slots of fixed length, and an individual station uses one slot to broadcast a packet in the clock period. Global synchronization of clocks over all stations allows the assignment of slots to stations uniquely, so that packet transmissions do not collide. When mobile radio stations are spread over a large terrain, however, it has been proposed in practice to employ local synchronization only, for stations within broadcast range of each other, to avoid the difficulty of global time coordination over a large area. When synchronization of stations is only local, two (or more) groups of internally coordinated mobile stations can be meet and overlap in transmission. To evaluate the performance of such systems, we investigate in this case the probability of colliding slots. The problem is reduced to the combinatorial question of determining the number of ways to choose k out of n objects with exactly l sequences of consecutive members. In an appropriate probabilistic model, the throughput of the channel is obtained, and this leads to a complete closed form representation of the system performance.