Distributed Clustering and Closest-Match Motion Planning Algorithms for Wireless Ad-Hoc Networks with Movable Base Stations

In this paper algorithms for modelling dynamic reconfiguration of ad-hoc wireless networks with movable base stations in presence of obstacles are proposed. This problem is considerably harder than the one treated in [1] where base stations were organized in a starred network and no obstacles were present. In these models nodes communicate through a clusterehead gateway switching routing protocol. In [1] both host clustering and base stations repositioning computations were performed by the center of the star. Here movable base stations are organized in an Ad-Hoc Network. Clustering, center computation and repositioning are performed in a distributed fashion among the base stations. The amount of transmitted information is proportional to the number of base stations. Obstacles which may interfere with hosts clustering and base stations motion are present. Repositioning is performed by a fast motion planning algorithm based on an extension of the bottleneck matching computational geometry technique to visibility graphs