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: