Topology Control for Multihop Packet Radio Networks

Abstract

A novel, distributed topology-control algorithm has been developed for each node in a packet radio network (PRN) to control its transmitting power and logical neighbors in order to construct a reliable high-throughput topology. The algorithm first constructs a planar triangulation from locations of all nodes as a starting topology. Then, the minimum angles of all triangles in the planar triangulation are maximized by means of edge switching to improve connectivity and throughput. The resulting triangulation at this stage is called the Delaunay triangulation, and it can be determined locally at each node. Finally, the topology is modified by negotiating among neighbors to satisfy a design requirement on the nodal degree parameter. Simulations show that 1) the 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. © 1993 IEEE