Master of Computer Science 1 - MOB Mobile Internet and Surrounding
1/12 Baey, Fladenmuller – Subject 5
MOB Subject 5 –Access methods
Static and dynamic access techniques
1. Static access techniques
1.1 Space-division multiple-access (SDMA)
When one seeks to cover a broad territory by a whole of cells of the same dimension, one
considers that the traffic is uniformly distributed, that the propagation law is the same and that the
power of all the equipment is constant. The same number of carrier will have thus to be allocated to
each basic station.
One will often use a hexagonal paving to cut out the zone has to cover, the hexagon being the
polygon nearest to the circle which allows paving the plan. One calls cluster, a set of adjacent cells
which uses the unit of carriers one and only one time. This cluster is repeated on all surface has to
cover.
Arithmetic and geometrical considerations allow showing that a cluster having a given number
of carrier is optimal if it is regular. For a hexagonal paving, the size K of cluster verifies the relation:
K = i
2
+ ij + j
2
(1)
with i and j entries positive natural or null.
The paving of the zone has to cover is realized of iterative manner in leaving of a cluster given
of K cells. From one cells of this cluster, one moves vertically i cells to one of its sides, then j cells
in a direction forming an angle of +60 degrees with the initial direction. The arrival point defines
then the "homologous" cell of adjacent cluster. By repeating this process for the set of cells of the
cluster chosen at the origin while keeping these same directions, one defines an adjacent cluster.
One repeats then this process for the five other possible directions (other dimensions of the cell) to
find the set of adjacent clusters. In proceeding secondly little by little on the cluster, one then builds
a paving of the cover zone.
Each cell of a cluster is seen allocated a subset of the carrier which is own for it. The homologous
cells of all the cluster use the same carrier. The minimal distance between two cells (homologous)
using the same carrier is called reuse distance. The size K of the cluster also constitutes the reuse
factor of the carrier.
1. What is the principle of the reuse of frequencies in the domain of the cellular networks?
In a cellular network, the space is divided into cells, each served by a base station (i.e a cell is
a portion of the territory covered by a base station).
It was affecting to each cell (i.e at each base station), a number of carriers of the total
bandwidth available based on estimated traffic in this cell.
It is possible to reuse one even at the same carrier in different cells if they are sufficiently
remote. The reuse of frequencies thus allows an operator has to cover an unlimited
geographic area by using a frequency band width limited.
2. Discuss the advantages and disadvantages to use of cells of small size, in comparing with
cells of big size in the cellular networks.
Advantages:
- greater reuse of frequencies: optimization of bandwidth;
- increase battery life because the power of emission decreases;
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
2/12 Baey, Fladenmuller – Subject 5
- if a cell is malfunctioning or cluttered, possibility to switch to a neighboring cell.
Disadvantages:
- Roaming Management heavier if mobility;
- Increasing the level of interference between cells.
3. List several manners to increase the capacity of a cellular network:
- Adding new carriers: usually when a system is implemented in a region, all carriers are not
used. Growth can then be managed using these carriers.
- Borrowing frequency: in the simplest case, cells are over-used carrier will temporarily
borrow the adjacent sub-cells used. The carriers may also be dynamically allocated to cells.
- The severing of cells: in practice, the traffic distribution and extent dansune cell are not
uniform. The cells can be very busy subdivided into smaller cells.
- Sectorized cells: this is to divide the cell into sectors, each possessing its own set of
carriers. Typically we can consider three or six sectors per cell. Each sector is assigned a
distinct subset of carriers. Directional antennas at the access points or base stations are used
to concentrate the signal in the region of the sector and reduce the interference and
"inter-sector".
- Microcells: for cellular networks with larger cells, the antennas must be placed on top of
hills or tall buildings. When cells become smaller, the antennae can be placed on buildings or
even less high peaks of the streetlights. The reduction of cell size accompanied by a
reduction of the power radiated by both points of access by mobile devices. The microcells
may be used in congested areas, such as certain city streets, highways, the interior of large
public buildings
4. Factor of reuse K.
a) Give the first entries which verify the equation (1). What do these values of K
correspond to?
i j K
1 0 1
1 1 3
2 0 4
2 1 7
3 0 9
2 2 12
3 1 13
4 0 16
3 2 19
4 1 21
5 0 25
The first K values are: 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, These values correspond
to the sizes of possible reasons.
b) Show on the figure 1 the cluster for reuse for K = 19.
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
3/12 Baey, Fladenmuller – Subject 5
Figure 1: Hexagonal clusters
Figure 2: Hexagonal clusters with K = 19
Figure 3: Hexagonal clusters with K = 3
5. An analog cellular system has 33 MHz of band-width and uses two channels simplex of 25
kHz to provide a transfer service of full-duplex trace and the indication necessary.
a) What is the number of full-duplex channels available by cell for a reuse factor K = 4, K =
7, K = 12?
The number of available channels is N = 33,000 / 50 = 660.
For a frequency reuse factor of K, each cell has N
cel
= N / K full-duplex channels
With K = 4, N
cel
= N / K = 660 / 4 = 165 full-duplex channels
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
4/12 Baey, Fladenmuller – Subject 5
With K = 7, N
cel
= N / K = 660 / 7 = 94 full-duplex channels
With K = 12, N
cel
= N / K = 660 / 12 = 55 full-duplex channels
b) If one supposes that 1 MHz is dedicated to the control channels and that only a control
channel is necessary by cluster, determine a reasonable distribution of the voice channels
for each cell, for the 3 reuse factors given previously.
32 MHz are dedicated to voice traffic, a total of 640 full-duplex channels.
For K = 4, we can have 160 voice channels (4 160 = 640).
For K = 7 then 640 / 7 = 91,4 which is not an integer. It then looks for x number of cells
with 91 voice channels and y the number of cells with 92 voice channels. One solves the
system of equations has two unknowns: x 91 + y 92 = 640 and x + y = 7.
We get x = 4 and y = 3.
We can have 4 cells with 91 voice channels and 3 cells with 92 voice channels, remember
(4 91 + 3 92 = 640).
For K = 12, we can have 8 cells with 53 voice channels and 4 cells with 54 voice channels
(8 53 + 4 54 = 640)
1.2 Frequency-division multiple access (FDMA)
1. A cellular system uses the FDMA, with a spectrum allocation of 12,5 MHz in each direction,
a guard band of 10 kHz of each end of the allocation spectrum and a width of 30 kHz for
each channel. Which number of users can one have in maximum?
416
1030
)1010(2105,12
3
36
2. The spectral efficacy of the FDMA for a cellular system is defined by: with
B
c
the band-width of the channel, N
T
the total number of trace channels in the covered zone,
and B
w
the band-width in a direction. What is the maximum limit of η
a
?
The amount of bandwidth allocated to voice channels (BcNt) must be no greater than the
total bandwidth (Bw). Therefore η
a
1.
1.3 Time Division Multiple Access (TDMA)
In the traditional local networks, a physical support is sharing between several users. It is thus
important to define the access rules of the media for the frames emission. Two families of solutions
are possible: the static solutions and the dynamic solutions.
1. Let a network be constituted of N connected stations on the same support. Let T be the average
stay time of a frame expressed in seconds, C the channel capacity in bits per second and M the
arrival rate of frames on the channel, expresses in frames per second. It is supposed that the
inter-arrival distribution of frames is exponential. The size of a frame is distributed according
to an exponential law, of average L bits. The digital values of these parameters are C = 64 kbits,
M = 10, L = 4 kbits.
a) What is the value of T?
To calculate the average time of stay, we consider a system has queue. The
frames of the stations are served one after the other in their order of arrival (FIFO
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
5/12 Baey, Fladenmuller – Subject 5
discipline). It has a single server.
Each frame with a size distributed according to an exponential distribution and the
capacity of the channel being constant service time of a frame has an exponential
distribution of average L/C or rate = C/L.
Finally, the distribution is exponential interarrivals frames, rate = M.
It was therefore a M/M/1 queue. The theory of the waiting can calculate the average
time of stay:
T =
1
T =
M
L
C
1
T =
s
6
1
10
4
64
1
b) The channel is divided in static way of N sub channels independent. The traffic of the
stations is distributed in a uniform way on these various sub channels. What becomes
the average stay time of a frame?
Each sub-channel has a capacity of C / N bits per second. The service time of a frame
has an exponential distribution of average L / (C / N), or rate = C / (N L).
The distribution of inter-arrivals frames on each sub channel is exponential, rate =
M/N.
The average residence time is identical on each sub-channels. Using the model has
M/M/1 queue, we obtain:
s
M
L
C
N
N
M
LN
C
T
static
6
4
10
4
64
41
c) What do you deduce from?
For multiplexing static, the average time of stay T is N times greater than if all the
frames had been ordered, as in a single queue using the single channel globally. The
static solutions are simple to introduce, but suffer from a very low yield. You lose the
multiplexing gain!
3. Dynamic access techniques
Pure Aloha: the principle of Aloha is to let talk to everyone when he wants it and without discrete
the moments when one can start to emit.
Discrete Aloha: the principle is the same but with a discrete time i.e. the moments when one can
start to emit are spaced out.
CSMA (Carrier Sense Multiple Access): CSMA protocols used in the wire networks allow to
improve the output of the ALOHA protocol because they bring the certainty that the stations
will be careful not to emit if they note that another station is emitting. Another improvement
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
6/12 Baey, Fladenmuller – Subject 5
consists in introducing a mechanism allowing, in the event of collision, stopping immediately
the continuation of transmission of a frame. In others words, the transmitting stations seeing
that the frame between collision ceases to emit. They will start again the transmission (if the
support is free) after a random duration. This cannot nevertheless be set up in wireless
networks.
One distinguishes two types of persistent CSMA and non-persistent CSMA.
Persistent CSMA: This is about the first CSMA protocol called also "1-persistent” because the
station which wants to emit maintains the listening of the channel and emits as soon as it notes
that it became free (without carrier).
Non-persistent CSMA: The station listens to the channel before emitting. If the channel is free,
one emits directly its frame. If the channel is already in use, the station does not remain in
listening permanent the station, it waits a random time then repeats the procedure since the
beginning.
p-persistent CSMA: The time is divided into intervals, like "Discrete Aloha". When a station
wants to emit, it listens to the channel. If the channel is free, it emits its frame with a probability
p and thus delays the emission at the next slot with a probability 1 p. One repeats this
procedure as long as the frame was not emitted correctly and that another station does not
occupy the channel. If another station emits, a random time is waited. If at the beginning, the
channel was occupied, the station awaits the next slot.
Collision detection CSMA (CSMA/CD): One functions with 3 types of slots: idle slots, when no
station is emitting, busy slots, when a station is emitting its frame, contention slots when there is
a possible collision. Once a station can emit, it sends its frame but it listens to the channel while
it emits, which returns the channel half-duplex considered that the controller uses already its
ability of reception to control that there is no collision which occurs.
MACA and MACAW:
- MACA (Multiple Access with Collision Avoidance) the idea consists in asking the
authorization to the receiver to send the data. This is done by the sending of a small frame to
confirm that one can send the data frame. One uses RTS (Request To Send) and CTS (Clear
to Send) frames.
- MACAW (MACA for Wireless) One added to MACA the settlement to be able detect the
lost frames.
1. Pure Aloha
In order to determine performances of this access method of the simple Aloha protocol, one
will suppose that the frames are of length fixed t and one ignores the propagation time on the
support.
Poisson process
A Poisson stochastic process of parameter
, is generally used to model the arrivals of clients
in a system;
is then the average rate of arrivals of clients in the system. By definition, the
probability that k clients arrive during x (between t and t + x) is independent of time t and the
"pass" process (it is the priority "without memory" of the Poisson process which makes that it
is largely used), and is given by:
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
7/12 Baey, Fladenmuller – Subject 5
(2)
One can then easily calculate the average number of clients who arrive in duration x:
(3)
a) If a machine starts to emit a frame at a moment t
0
, what is the vulnerability period (time
interval for which it should not be emission on behalf of other stations in order to avoid a
collision)?
This frame is properly issued when the time t
0
+ t (and therefore properly received by the
other stations are currently neglected or propagation time) if no other machine begins to
issue during the time interval [t
0
, t , t
0
+ t]. This "period of vulnerability" in length 2t.
b) If one suppose that the frames are generated in according to a Poisson process (of rate ),
what is the average number G of frames emitted for duration of frame t?
It is therefore gives gives G = E[N(t)] = t
c) Calculate the probability q that no frame is emitted for the vulnerability period.
The probability that no frame is emitted during a period of vulnerability is given by:
q = P[N(2t) = 0] = e
2t
= e
2G
d) Deduce the average number S of frames emitted successfully for duration of frame t.
The latter relation makes it possible to connect the parameter S associated to the useful
flow of support (an average number of frames transmitted successfully by time unit = S/t )
to the parameter G associated with traffic on the support (an average number of frames
emitted in total by time unit = G/t ). The curve giving S according to G is represented on
the figure 4.
It is given by : S = Gq = G e
2G
e) Comment this curve.
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
8/12 Baey, Fladenmuller – Subject 5
Figure 4: Useful charge S according to the total charge G
f) Which value Gmax is the flow S maximum with?
Just calculate the derivative of S with respect to G and how to find, Gmax, it vanishes:
GGG
G
eGGee
dG
dGe
222
2
)21(2
This implies Gmax = 0.5.
The maximum of S is attained when G = 0,5, that is to say when computers emit, on
average, one frame every two units of time t
g) Deduce the efficacy of the pure Aloha protocol.
The flow rate is maximum for G = Gmax = 0,5 and is Smax =
e
0,5
0,184.
Up to 36% of frames are successfully issued (as a length equal to 100t, a maximum of 18
frames on 50 will be issued with success), using only 18,4% of transmission time.
h) Which disadvantages do you see with the use of the pure ALOHA technique?
- Lack of efficiency: Just as the last bit of a frame coincides with the first bit of a frame so
that there is collision and thus transmission of two frames.
- The frame transmission is not interrupted by collisions.
- The flow becomes very weak as the number of communications increases.
i) A group of N stations share a pure ALOHA channel of 56 kbit/s. Each station emits in
average a frame of 1000 bits for every 100 seconds; even if the preceding one was not
sent (it is stored by the station to be retransmitted). By taking again the results obtained
for S
max
, determine the maximum value of N that one can have?
With pure Aloha technique, the "usable bandwidth” is 0,184 56 Kbps = 10.3 Kbps.
Each station requires 1000bit / 100s = 10 bps The maximum number of stations that can
share the channel is equal to N = 10300/10 = 1030 stations.
2. Slotted Aloha Variant
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
9/12 Baey, Fladenmuller – Subject 5
An improvement of the pure ALOHA protocol consists in defining intervals of repetitive
times (slots) and not in authorizing the transmitting stations that in beginning of each interval.
This protocol is known under the name of discrete ALOHA protocol.
a) Calculate the vulnerability period of the discrete ALOHA protocol.
It can reduce the period of vulnerability in half (compared to pure ALOHA, the latter
from 2t to t) and thus increase the efficiency of access to the media. transmissions can
take place only moments precise: 0, 1, 2, , n, n +1, : A packet that arrives during the
interval (n-1, n) begins its transmission at time (n) and ends at the moment (n + 1) a
packet arriving in a slot given do not undergo collisions if no other package arrived on the
same slot.
b) Do you see a constraint imposed by this system?
It requires synchronization between the various stations which are connected.
c) Calculate the probability p that a package is emitted successfully.
Always with the assumption of Poisson: p = e
G
d) Explain S according to G and of p.
S = Gp = Ge
G
e) Calculate the maximum efficacy of the Slotted Aloha protocol.
The maximum efficient U is obtained by canceling the derivative of S with respect to G.
For G = 1, then U = 1/e = 36%.
Note: node tries to transmit all its transmissions are successful and the efficiency is
100%. This situation is not captured by our model! The Poisson assumption is true only
when the traffic G is an aggregated traffic, generated by a large number of
stations. Therefore, the efficiency of 36% corresponds to the case or a large number of
stations with comparable flow rates and sharing a common channel with Slotted Aloha
protocol.
3. Aloha Reservation
In the Aloha Reservation variant, the protocol alternates reservation phases with transmission
phases. During the reservation phase, the nodes use the Slotted Aloha protocol to try to reach
the channel: a node which succeeds to reach the channel diffuses a reservation while emitting
a package containing its identification number. At the end of the reservation phase, the
transmission phase starts during which the nodes having made a reservation emit their
package and this in the order of their reservation. At the end of the transmission phase, a new
reservation phase starts, etc. One notes T
res
the duration of a reservation slot, T
transm
the
transmission time of a package; it is supposed that T
res
= 0, 05. T
transm
.
a) How many slots of reservation are necessary in average to succeed a reservation?
We wish to calculate the maximum efficiency of the protocol, that is to say, the maximum
fraction of time during which packets can be issued successfully, or Smax
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
10/12 Baey, Fladenmuller – Subject 5
b) Calculate the efficacy U of the Slotted Aloha protocol.
Aloha Reservation Aloha Protocol A. uses:
- phases of reservation, with 36% efficiency which also means that each slot has a
probability of 0.36 to be used successfully! This also means that a reservation takes on
average 1 / 0, 36 slots reservation
- phases with a transmission efficiency of 100%. The efficiency is then given by Aloha:
U = T
transmit
/ (T
res
/0,36) + T
transmit
) = 1 / (1 + 2,8 T
res
/ T
transmit
) = 0,871559633
Assuming that the length of a slot reservation is 5% of the length of the transmission of a
packet, we obtain U = 1 / (1 + 2,8 5 / 95) = 0,871559633 88%
4. CSMA and its derivatives
a) What are the protocols Carrier Sense sensitive in to the delays of propagation?
Carrier Sense Protocols are very sensitive to the propagation time. In eect, if a station
starts to issue, it is very unlikely that another station starts to issue just after but if the
propagation time of the frame is long enough, it may be another station listens to the
channel to send a frame, the channel is free (for her) and it emits its frame, which has the
effect of creating a collision.
b) Which conditions can a local network without wireless use a CSMA/CD protocol under?
If the issuer is able to detect a collision and that all radio transmitters are within reach of
each other.
c) Explain how a 1-persistent CSMA protocol functions.
Prior to emit a frame, the station listens to whether the channel is free. If so, it emits its
frame, otherwise it will listen until the channel is free and it becomes free, it emits its
frame. If the frame emitted has created a collision, the station waits a random time before
retry to emit its frame in a same way the. We call 1-persistent because when the channel is
free, the station emits with a probability of 1.
d) Discus the performances of the non-persistent adjournment in comparing with the
1-persistent.
The nonpersistent better use of bandwidth but increases latency compared to the
1-persistent. Idea: If the two stations were willing to issue more patient there would be
fewer collisions. The non-persistent CSMA protocol agrees to be deliberately emit less
press than its frame protocol 1-persistent.
e) When a station wishes to emit, it listens to the trace. If during a fixed delay baptized DIFS
("Distributed Inter Frame Spacing") no other station emits, the station starts to emit the exit
of DIFS delay. If a station has already started to emit, the station in listening defers its
transmission (1) and awaits the end of the transmission in progress. At the exit of this
waiting, it waits in more a random delay then transmits if no transmission takes place
before the expiration of its delay, otherwise it waits defers its new transmission and passes
by again into (1). Is this about a persistent or non-persistent adjournment?
non-persistent
Master of Computer Science 1 - MOB Mobile Internet and Surrounding
11/12 Baey, Fladenmuller – Subject 5
5. Read the extract of the article published in "In Proc. ARRL/CRRL Amateur Radio 9th
computer Networking Conference, 1990, pp. 134 140." and explains the impact of this access
method for the problem of the hided terminal and of the exposed terminal.
MACA - A New Channel Access Method for Packet Radio
Phil Karn
[ ]
Turning CSMA/CA into MACA
Hidden and exposed terminals abound on simplex packet radio channels, and this makes them very
different from Localtalk and most other types of local area networks. When hidden terminals exist,
lack of carrier doesn’t always mean it’s OK to transmit. Conversely, when exposed terminals exist,
presence of carrier doesn’t always mean that it’s bad to transmit. In other words, the data carrier
detect line from your modem is often useless. So I’ll make a radical proposal: let’s ignore DCD ! In
other words, let’s get rid of the CS in CSMA/CA. (It’s too hard to build good DCD circuits
anyway )
Instead we’ll extend the CA part of what we’ll call MA/CA (or just plain MACA). The key to
collision avoidance is the effect that RTS and CTS packets have on the other stations on the channel.
When a station overhears an RTS addressed to another station, it inhibits its own transmitter long
enough for the addressed station to respond with a CTS. When a station overhears a CTS addressed
to another station, it inhibits its own transmitter long enough for the other station to send its data.
The transmitter is inhibited for the proper time even if nothing is heard in response to an RTS or
CTS packet.
[ ] Station Z cannot hear X’s transmissions to Y, but it can hear Y’s CTS packets to X. If Z
overhears a CTS packet from Y to X, it will know not to transmit until after Y has received its data
from X.
But how does Z know how long to wait after overhearing Y’s CTS? That’s easy. We have X, the
initiator of the dialogue, include in its RTS packet the amount of data it plans to send, and we have
Y, the responder, echo that information in its CTS packet. Now everyone overhearing Y’s CTS
knows just how long to wait to avoid clobbering a data packet that it might not even hear.
As long as the link between each pair of stations in the network is reciprocal (i.e., all the stations
have comparable transmitter powers and receiver noise levels), the receipt of a CTS packet by a
station not party to a dialogue tells it that if it were to transmit, it would probably interfere with the
reception of data by the responder (the sender of the CTS). MACA thus inhibits transmission when
ordinary CSMA would permit it (and allow a collision), thus relieving the hidden terminal problem.
(Collisions are not totally avoided; more on this point later.)
Conversely, if a station hears no response to an overheard RTS, then it may assume that the intended
recipient of the RTS is either down or out of range. An example is shown in figure 4. Station X is
within range of Y, but not Z. When Y sends traffic to Z, X will hear Y’s RTS packets but not Z’s
CTS responses. X may therefore transmit on the channel without fear of interfering with Y’s data
transmissions to Z even though it can hear them. In this case, MACA allows a transmission to
proceed when ordinary CSMA would prevent it unnecessarily, thus relieving the exposed terminal
problem. (Because modems have a capture effect, hearing a CTS doesn’t always mean that you’d
cause a collision if you transmit, so the problem isn’t yet completely solved. More on this point
later.)
Không có nhận xét nào:
Đăng nhận xét