In the paper, we address wireless communication infrastructure building by relay placement based on approaches utilized in wireless network sensors. The problem is motivated by search and inspection missions with mobile robots, where known sensing ranges may be exploited. We investigate the relay placement, establishing network connectivity to support robust food-based communication routing. The proposed method decomposes the given area into Open space and Corridor space where specific deployment patterns allow for guaranteed k-connectivity, making the resulting network redundant while keeping channel utilization bounded. In particular, a hexagonal tesselation coverage pattern with 3-connectivity is investigated in Open space and a linear 4-connectivity pattern in Corridor space, respectively. The proposed approach is empirically evaluated in a realistic scenario, and based on the reported results, it is found superior compared to the existing stochastic randomized dual sampling schema.