Wireless networking technology will
play a key role in future communications and the choice of the network
architecture model will strongly impact the effectiveness of the applications
proposed for the mobile networks of the future. Broadly speaking, there
are two major models for wireless networking: *single-hop* and *multi-hop*.
The single-hop model, based on the cellular network model, provides one-hop
wireless connectivity between mobile hosts and static nodes known as *base
stations*. This type of networks relies on a fixed backbone infrastructure
that interconnects all base stations by high-speed wired links. On the
other hand, the multi-hop model requires neither fixed, wired infrastructure
nor predetermined interconnectivity. *Ad hoc *networking is the most
popular type of multi-hop wireless networks because of its simplicity:
Indeed, an *ad hoc* wireless network is constituted by a homogeneous
system of *mobile* stations connected by wireless links. In ad hoc
networks, to every station is assigned a transmission range: The overall
range assignment determines a transmission (directed) graph since one station
*s*
can transmit to another station *t* if and only if *t* is within
the transmission range of *s*. The range transmission of a station
depends, in turn, on the energy power supplied to the station: In particular,
the power *P_s* required by a station *s* to correctly transmit
data to another station *t* must satisfy the inequality

*P_s / d(s,t)^alpha > gamma*

where *d(s,t)* is the Euclidean
distance between *s* and *t*, *alpha>1* is the *distance-power
gradient*, and *gamma>1* is the *transmission-quality* parameter.
In an ideal environment (i.e. in the empty space) it holds that *alpha=2*
but it may vary from 1 to more than 6 depending on the environment conditions
of the place the network is located.

The fundamental problem underlying any phase of a dynamic resource allocation algorithm in ad-hoc wireless networks is the following: Find a transmission range assignment such that (1) the corresponding transmission graph satisfies a given property (P), and (2) the overall energy power required to deploy the assignment (according to Equation above) is minimized.

In this talk, we will consider some well-studied cases of the above problem by choosing (P) respectively as:

i) The transmission graph has to
be strongly connected.

ii) The transmission graph has
to have a diameter bounded by a fixed parameter *h*.

iii) The transmission graph has
to contain a spanning tree from a fixed source node.

The computational complexity of
each of such versions will be investigated by providing both hardness results
and/or efficient approximation algorithms.

**Related papers:**

- The Minimum Range Assignment Problem on Linear Radio Networks (work by A. Clementi, A. Ferreira, P. Penna, S. Pérennes and R. Silvestri)
- On the Power Assignment Problem in Radio Networks (work by A. Clementi, P. Penna and R. Silvestri)
- A Worst-Case Analysis of an MST-Based Heuristic to Construct Efficient Broadcast Trees in Wireless Networks (work by A. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca)