Abstract
In a distributed mobile packet radio network (DMPRN), terminals (radio units) are scattered over plane, movable, and the network is distributedly controlled. Having minimal spanning trees of the terminals is useful since the communication between terminals can be carried through the channels on the spanning tree, and the management of the network is flexible. Besides, when one terminal wishes to broadcast packets to other terminals, the packets can be broadcasted along the channels of the spanning tree such that the communication cost is as less as possible. Since the terminals in a DMPRN are movable, the minimal spanning tree of the DMPRN may be changed frequently. In this paper, we propose a distributed protocol which can dynamically construct the minimal spanning tree of the terminals in a DMPRN. For a DMPRN containing N terminals, the total number of packets required by our protocol is at most 3NlogN+N+1. The time complexity of our protocol takes O(N) time units.