Distributed algorithms for packet radio networks
Limin Hu · 1991
Packet radio networks (PRNs) provide an attractive alternative to wire networks because of their mobility, flexibility, and easy installation. But the sharing of a common radio channel in PRNs poses a serious challenge for system analysis and design. Distributed algorithms for topology control, CDMA code assignments, and packet routing, having the ability to cope with network dynamics and provide high network capacity for packet delivery, need to be developed. We have developed a novel, distributed topology-control algorithm for each node in a PRN to control its transmitting power and logical neighbors in order to construct a reliable, high-throughput topology. Simulations show that (1) the triangulation-based, final topology is degree-bounded, (2) it has a rather regular and uniform structure, and (3) its throughput and reliability are greater than that of a number of alternative topologies. We have devised two-phase algorithms to assign and re-assign spread-spectrum codes to transmitters, to receivers and to pairs of stations in CDMA (Code-Division Multiple Access) PRNs. The purpose of the code assignments is to spatially reuse spreading codes to reduce the possibility of packet collisions and to react dynamically to topological changes. The two-phase algorithms minimize the time complexity in the first phase and minimize the number of control packets needed to be exchanged in the second phase. A new pairwise code-assignment scheme is proposed to assign codes to edges. Simulations based on well-controlled topologies (sparse topologies) show that the proposed scheme requires much fewer codes than transmitter-based or receiver-based code assignment, while maintaining throughput performance. Routing algorithms that are based on strictly hierarchical structures to cope with the rapidly changing topology of a large PRN usually suffer from the heavy traffic around clusterheads and the overhead to maintain the hierarchy. We have developed a two-level road-map routing scheme to improve the throughput performance of a large PRN and reduce the traffic of control packets. This scheme requires fewer message exchanges than a hierarchical routing scheme, and the congestion problem which often occurs at clusterheads is alleviated.