  Wireless mesh networks appear as an appealing solution to reduce the digital
divide between rural and urban regions. However the placement of router nodes
is still a critical issue when planning this type of network, especially in
rural regions where we usually observe low density and sparse population. In
this paper, we firstly provide a network model tied to rural regions by
considering the area to cover as decomposed into a set of elementary areas
which can be required or optional in terms of coverage and where a node can be
placed or not. Afterwards, we try to determine an optimal number and positions
of mesh router nodes while maximizing the coverage of areas of interest,
minimizing the coverage of optional areas and ensuring connectivity of all mesh
router nodes. For that we propose a particularized algorithm based on
Metropolis approach to ensure an optimal coverage and connectivity with an
optimal number of routers. The proposed algorithm is evaluated on different
region instances. We obtained a required coverage between 94% and 97% and a
coverage percentage of optional areas less than 16% with an optimal number of
routers nr_max2 =1.3*nr_min , (nr_min being the minimum number of router which
is the ratio between the total area requiring coverage and the area which can
be covered by a router).
