An Algorithm for Evaluation of Throughput in Multihop Packet Radio Networks with Complex Topologies

1 July 1987

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications

Vol. 5 (6) , 1003-1012
https://doi.org/10.1109/jsac.1987.1146614

Abstract

The problem of analyzing the thoughput of packet radio networks with realistic topologies is considered. We present an algorithm for the solution of this problem and show that both the memory requirements and running time of this algorithm in practice grow polynomially with the size of the problem. Although in theory both can grow exponentially in the worst case, we offer computational experience with the procedure and show that for realistic topologies where connectivity is related to distance, the rate of growth is quadratic in the number of links. Even for regular grids, which are pathological in their symmetry, the rate of growth is only cubic in the number of links. We thus conclude that the procedure is effective for realistic topologies with up to several hundred nodes.

Keywords

This publication has 2 references indexed in Scilit:

Throughput Analysis in Multihop CSMA Packet Radio Networks
IEEE Transactions on Communications, 1987
Packet Switching in Radio Channels: Part II--The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution
IEEE Transactions on Communications, 1975