MAC for MANET's

Example 3: Medium access control in mobile ad-hoc networks

Consider the following model of a decentralized medium access control (MAC) in mobile ad-hoc networks (MANET's):

A random set of users distributed in space and sharing a common Hertzian medium.
Users constitute ad hoc networkthat is in charge of transmitting information far away via several hops.
Decentralized MAC: users independently switch between emitter and receiver modes with p being medium access probability (MAP).
Multi-hop transmissions: Emitter sends a packet in some given direction far away via several hops. The packet is received by some number (possibly 0) of neigbouring receivers. An optimal receiver among them is in charge of forwarding this packet in (one of) his next emission time-slots. In the case of no reception, emitter re-emits the packet next authorized time.
Successful reception: Emitter sends a packet emitting some power. Transmission distance attenuates the emitted power. Emitted power causes interference at all receivers. Reception is successful if the Signal to Interference Ratio (SIR) at the receiver is large enough (as in the sir SINR covarage model ).

Note that in contrast to classical Aloha scheme several simultaneous transmissions are possible if they are separated in space. This is called spatial reuse effect. For this reason we call the MAC protocol in question the Spatial-Reuse Aloha (SR-Aloha).

The optimal receiver maximizes the progress; i.e,. the effective distance traversed toward the destination.

A static stochastic-geometry formalization of the above model consist in a Poisson point process on the plane with independent marking (e,S), where e describes instantaneous MAC status of a ginven node (e=0 for receiver and e=1 for emitter, with P(e=1)=p) and S is (random) emited power used by the node if its MAC e=1. Path loss is modeled by a continuous attenuation function of the distance.


The optimal receiver maximizes the progress; i.e,. the effective distance traversed toward the destination.

In the case of exponential emitted powers, the theory of additive and extremal Poisson shot-noise allows for explicit expression of the distribution function of some (modified) progress done by a packet in one hop. Moreover, by a spatial Campbell formula one gets the spatial density of (modified) progress that is the mean total effective distance traversed in one hop by all transmissions initialized in some unit area. In the case of a general distribution of the emitted power, the scale-invariant property of the distribution of the Poisson point process combined with the polynomial form of the path-loss function allows for qualitative analysis of the spatial density.

What kind of problems can be addressed by such a model?

Note that for a given density of nodes there is the following trade-off in MAP p=Pr(e=1) between the spatial density of communications and the range of each transmission. For a small p, there are few emitters only per unit area, but they can likely reach very remote receiver as a consequence of little interference. On the other hand, a large p means many emitters per unit area that create interference and thus prevent each other from reaching a remote receiver. Another feature associated with large p is the paucity of receivers, which makes the chances of a jump in the right direction smaller. The stochastic-geometry model allows to find MAP p that maximizes the transport capacity; i.e., the amount of packets pumped per unit time and and per unit area of network, (modeled by the spatial density of modified progress).

The optimal transport capacity in our decentralized MAC scales up with the square root of the density of nodes, that is the ultimate upper bound found by Gupta & Kumar.

Density of progress for the model with exponential emitted powers, polynomial attenuation function (path-loss exponent 3) and required SINR ratio, respectively, 10, 13 and 15dB. The optimal MAP's values can be recognized.


Density of progress for the model with exponential emitted powers, polynomial attenuation function (path-loss exponent 3) and required SINR ratio, respectively, 10, 13 and 15dB. The optimal MAP's values can be recognized.

Matern hard core process as a model of CSMA

By the Carrier Sense Multiple Access (CSMA) we understand a MAC protocol where each communication within a targeted transmission range R is protected by the exclusion disc centered at the transmitter with radius R_cs > R. In order to model this protocol we assume again a random Poisson network. We suppose that the radius of the carrier sense range R_cs is set such that there will be no collision for a receiver in a radius of range R if the transmitters in the network are on a triangular regular network with neighboring transmitters separated by R_cs. It is in a triangular regular network that the density of nodes being at least at R_cs away is maximum. It follows that in a random Poisson network, whatever the pattern of simultaneous emitters respecting the CSMA rule with R_cs, a transmission to a receiver within radius R will always be collision free.

The aim is now to compute the intensity of an extracted point process (a subset of the initial Poisson point process) satisfying the CSMA exclusion rule. Of course the intensity of this process will depend on the selection algorithm. An intuitive algorithm consists in picking nodes randomly and adding them to the CSMA transmission set if they are not in the carrier sense range of an already selected node. This algorithm is close to the effective behavior of a simple CSMA system. However this model does not seem to be easily tractable mathematically. Another selection algorithm is that based on the Matern hard core process. This process is a thinning of the initial Poisson point process in which points are selected according to random marks. A point of the process is selected if its mark is larger than all marks in a radius of range R_cs. It is easy to check that the selected points follow the CSMA rule. The spatial intensity of the Matern hard-core process can be obtained in explicit function of the spatial intensity of the initial Poisson point process. This allows, for a tentative comparison of transport capacities between SR-Aloha and CSMA protocol.

Comparison of the spatial density of transmissions for CSMA (Matern hard core model), SR-Aloha and the regular triangular mesh network for required SINR=10dB.


Comparison of the spatial density of transmissions for CSMA (Matern hard core model), SR-Aloha and the regular triangular mesh network for required SINR=10dB.

Bibliography

: Baccelli, F., Blaszczyszyn, B. and Mühlethaler, P. (2004). An Aloha protocol for multihop mobile wireless networks. In Proc. of ITC Specialist Seminar on Performance Evaluation of Wireless and Mobile Systems. Antwerp, Belgium. early version in Proceedings Allerton Conference 03.
[ bib | .ps | .pdf | Abstract ]
: Gupta, P. and P. R. Kumar (2000). The capacity of wireless networks. IEEE Transactions on Information Theory IT-46, 388-404.
[ bib | .ps ]