>>>> Poster
Random graphs associated with the Poisson Boolean model and
percolation properties of these graphs have been considered
in [1] for analyzing
the connectivity of ad hoc networks (see also
here).
Within this context, the Poisson Boolean model assumes
that the stations are located according to a planar Poisson point
process, and that each station has an independent random power,
identically distributed for all stations.
A more physical model based on the signal to
interference ratio was used within the context of ad hoc networks
in [2]. In this last paper,
which departs from a deterministic
and finite population setting, all stations are assumed to
have the same power, and some attenuation function is given.
Station A can receive a signal from station B if the ratio
of the power it receives from B to the total
power received from all other stations is above a threshold.
The same physical model was analyzed
in [3] in
the infinite plane case under Poisson assumptions within the
context of CDMA networks. The corresponding coverage process is
related to Poisson shot noise processes.
The aim of the present project is to bring all these approaches
together and to study the connectivity of infinite ad hoc
networks under the physical model alluded to above. The
parametric setting will be that of an homogeneous Poisson point
process. Our main goal within this context is to learn whether
the percolation phenomenon that was established
in [1] for the case
without interference still holds
within this more realistic context.
We consider a multi-hop ad-hoc network where nodes are
distributed according to a Poisson point process of constant
spatial intensity l. Depending on its location, number of
neighbors, and battery level, each node i will adjust its
emitting power Pi within a given range [0,P],
where P is the maximal power of a node. The power of the
signal emitted by Node i and received by Node j is
Pi L(xi -xj),
where xi and xj
are the positions of Node i and j in the plane, respectively,
and L(x) is the attenuation function in the wireless
medium.
We assume that Node i can transmit data to Node j if the
signal received by j is strong enough, compared to the sum of the thermal
noise and the interferences. The interferences are computed as the sum of all signals
received by j that do not come from Node i, weighted by a factor g. This
factor stands for the inverse of the processing gain of the CDMA system
(g=1 in a narrow band system without CDMA).
In this model, the existence of a link between two nodes does not
only depend on their position, but also on the position of every other
node. Furthermore, one can show that when g>0
the degree of each node (i.e. the number of links starting or ending at that node)
is bounded, at the contrary of the Boolean model, where the node degree
is a Poisson random variable.
The figures below show the effect of interferences on connectivity.
The first figure illustrates a standard super-critical boolean model.
In the second figure, we introduce interferences with a small factor g; the network
is split into several small clusters, and does not percolate anymore.
Our main result is that under attenuation functions
with finite support, percolation holds under conditions similar to
those of the Boolean model of [1]
provided the orthogonality factor g is small enough. In this sense,
connectivity of ad hoc networks scales well with the size of the network even
in the case of models that take interferences into account. The
question whether this also holds for attenuation functions over an infinite support
is still open.
The figure below shows an example of a super-critical graph with interferences.
It has been obtained from the previous graph by increasing the emitting power of
all the nodes by the same amount to overcome interferences. One can observe that
compared to the Boolean
model, most of long range links survive whereas redundant short links are removed.
It leads to a well connected graph with fewer links than in the Boolean model, but
that requires more power.
People
// MICS
// External collaborator
Publications
O. Dousse, F. Baccelli and P. Thiran, `Impact of Interferences on Connectivity in Ad Hoc Networks,' Proc. INFOCOM 2003
Java applet
Play the Connectivity Game!
References
[1] O. Dousse, P. Thiran and M. Hasler, 'Connectivity in ad-hoc and hybrid networks,' in Proc. INFOCOM, New York, June 2002. (PDF)
[2] P. Gupta and P. R. Kumar, `The Capacity of Wireless Networks,' IEEE Transactions on Information Theory, pp. 388-404, vol.~IT-46(2) March 2000. (PDF)
[3] F. Baccelli and B. Blaszczyszyn. 'On a Coverage
Process Ranging from the Boolean Model to the Poisson Voronoi Tessellation, with Applications to Wireless Communications,' Adv. Appl. Prob., 33(2), 2001. (PS)
