On location of relay facilities to improve connectivity of multihop wireless networks

A multihop wireless network connects a pair of terminals by a path consisting of other terminals and wireless links; however, if terminals are randomly distributed, every pair of terminals is not always connected. Then, introducing special facilities called relay facilities to a multihop network has been proposed to improve connectivity. The relay facilities are used only for relaying terminals. This paper assumes that we have n relay facilities, and each of the relay facilities must be allocated at one of designated points given in advance. Under this assumption, this paper considers how to select n from the given designated points to improve connectivity between terminals.