Multi-Access Channels
Download
Report
Transcript Multi-Access Channels
CPSC 689: Discrete Algorithms
for Mobile and Wireless Systems
Spring 2009
Prof. Jennifer Welch
Lecture 5
Topics:
Multiple Access Channels
Sources:
Gallager paper
Komlos & Greenberg paper
MIT 6.885 Fall 2008 slides
Discrete Algs for Mobile Wireless Sys
2
Gallager, A Perspective on Multi-access
Channels, 1985.
Classical paper for multi-access channels.
Discusses:
Coding techniques and limitations on their achievable reliability.
Collision resolution
Simpler setting than general mobile ad hoc networks:
S
Static, several senders and one receiver.
Problems: Noise, interference.
S
R
Messages arrive at senders at random times.
Can be used to model:
Uplink for satellite.
S
Traffic to a central node in a telephone network.
Traffic to one receiver in a fully-connected wireless radio network.
Focus on collision resolution, emphasizing the modeling
assumptions.
Gallager’s Assumptions
Assumes messages arrive from external
sources randomly, sometimes in bursts.
Assumes (typical for theory papers):
If exactly one sender transmits at some time
(slot), the message succeeds.
If more than one transmits, a collision
happens and communication fails.
This oversimplifies:
Collisions aren't the only cause of
communication failure: this ignores noise and
other aspects of real communication.
Sometimes colliding messages can be
recovered.
S
S
S
R
Gallager’s Formal Assumptions
Assumption 1: Slotted system, with message
transmission time = slot length.
S
Senders synchronized, on slot boundaries.
Relies on synchronized clocks.
Precludes considering strategies involving
combinations of long and short packets.
Precludes carrier-sense strategies in which
sender could start transmitting at any time
(even in the middle of a slot).
S
S
R
Gallager's Formal Assumptions
Assumption 2: Receiver-side information: collision or perfect reception,
(0,message,c).
If no one sends, receiver learns this (0).
If exactly one sends, receiver receives message with no errors (message).
If more than one sends, a collision occurs; the receiver gets no information
about the messages sent, but learns that a collision happened (receives
special collision indicator c).
In particular, receiver can distinguish idle slot from
collision.
These assumptions hide noise and communication
aspects of the model/problem.
Not completely realistic:
Not always clear how a receiver can distinguish idle slot
from collision.
Receiver sometimes receives a packet when two senders
transmit.
Can lead to unrealistic solutions.
S
S
S
R
Gallager's Formal Assumptions
Assumption 3: Infinite set of senders.
Each new packet arrives at a completely new sender.
Avoids queueing issues.
Precludes use of TDM.
S
S
Assumption 4. Poisson packet arrivals, rate .
Assumption 5. Sender-side information: (0,1,c) immediate feedback.
Each sender learns immediately whether 0, 1, or >1 packets were sent.
Assumes transmitters are always listening for feedback, when they are
transmitting and when when they are idle.
Many algorithms designed for this assumption can be extended to the
case where feedback is delayed.
R
Nonadaptive Conflict Resolution
[Komlos & Greenberg, 1985]
Multiple-access channel: way for
geographically dispersed computing
entities to communicate
coaxial cable (Ethernet)
fiber optic
packet radio
satellite transmission
Discrete Algs for Mobile Wireless Sys
8
Mathematical Model
n stations (computing nodes)
synchronized steps (times when stations
can transmit data)
if k > 0 stations transmit at same step:
if k = 1, then every station gets the data
if k > 1 (collision), then no station gets the data
at end of step, each station gets feedback
0, 1 or 2+, indicating how many stations
tried to transmit => collision detection
Discrete Algs for Mobile Wireless Sys
9
General Approach
Schedule (re)transmissions so that each station
that wants to transmit eventually gets a step
where it is the sole transmitter
Algorithm identifies a query set at each step, a
subset of the stations
At each step, a station transmits if
it is in the query set and
it was involved in the collision trying to be resolved but
has not yet been successful
Discrete Algs for Mobile Wireless Sys
10
Categorizing Such Algorithms
Does k, the number of stations involved in the
collision, need to be known (hard-coded into the
algorithm)?
Does the query set at each step depend on the
feedback from the previous set (adaptive) or not
(nonadaptive)?
adaptive: each station must monitor feedback at each
step
nonadaptive: each station only needs to monitor
feedback at steps when it transmits, to see if it can
"drop out"
Discrete Algs for Mobile Wireless Sys
11
Previous Work
Tree algorithm [2,3,11,17]
deterministic
resolves conflicts among k nodes in
(k + k log(n/k)) steps
does not require knowledge of k
is adaptive
k steps are obviously necessary
If k is (n), then bound is (k) = (n)
If k is (1), then bound is (log n)
Discrete Algs for Mobile Wireless Sys
12
Previous Work
[10] gave a lower bound on worst-case
time for any deterministic conflict resolution
scheme of (k (log n)/(log k))
Shows that the tree algorithm is
approximately time-optimal
Can we do as well with a nonadaptive
algorithm?
Discrete Algs for Mobile Wireless Sys
13
This Paper
Gives a nonadaptive algorithm with time
(k + k log(n/k))
Requires k be known (hard-coded into
algorithm)
Non-constructive result:
prove that such an algorithm must exist
but do not explicitly describe the algorithm
Discrete Algs for Mobile Wireless Sys
14
Nonconstructive Results
A drawback from a practical perspective
Still of some interest:
proves such an algorithm exists, so it is not
pointless to keep searching for an explicit one
there may be ways to convert non-constructive
proofs into constructive ones
ideas of proof may be helpful in constructing a
randomized algorithm that has the good
running time with high probability
Discrete Algs for Mobile Wireless Sys
15
Adaptiveness and Knowledge of k
Suppose you don't know exactly how many
nodes are contending, but you know an
upper bound on this number
k' : number actually contending
k : upper bound on number contending
Can use any nonadaptive algorithm for
fixed k to construct an adaptive algorithm
for (unknown) k'.
If k' << k, this can be useful.
Discrete Algs for Mobile Wireless Sys
16
Adaptiveness and Knowledge of k
Algorithm:
Run fixed-k algorithm with k = 2
Finish with a step in which the query set is all the stations.
If all the conflicting stations succeeded, then there are no
transmissions at the last step and we are done
Otherwise, run the fixed-k algorithm with k = 4 (doubling k)
Continue at most log n times (until k = n)
Adaptive because stations must listen at the end of each
"subroutine call" to see if they need to continue with next
value of k
Running time is asymptotically same as subroutine's.
Discrete Algs for Mobile Wireless Sys
17
The Challenge
Goal is a list of queries (sets of stations allowed to
transmit at each step) that isolates every
conflicting station (there is a step at which it is the
only one to transmit)
Difficulties:
don't know in advance which subset of stations want to
transmit; must handle all possibilities
Try to be time-efficient, so that if number contending is
small, then number of steps to isolate all is small
Discrete Algs for Mobile Wireless Sys
18
Overview of Nonconstructive Proof
consider a list of k/2 queries chosen
randomly
prove that with high probability the list
isolates at least a constant fraction of any
input of size k
use this result to prove that certain lists of
desired length must exist
use such lists to construct the desired list
Discrete Algs for Mobile Wireless Sys
19
Key Notation
Q1, Q2, Qt is a list of queries (subsets of the n stations)
I0 = I
original set of colliding stations
I1 = I0 - Q1 if I0 and Q1 intersect in exactly one id;
I1 = I0 otherwise
set of stations still contending after contending stations in Q1
transmit simultaneously
I2 = I1 - Q2 if I1 and Q2 intersect in exactly one id;
I2 = I1 otherwise
set of stations still contending after contending stations in Q2
transmit simultaneously
Etc.
Discrete Algs for Mobile Wireless Sys
20
Key Notation
A list of queries is (,k,n)-universal if for all
inputs of size k, the list isolates at least *k
of the colliding stations
We want a list with = 1, isolates all the
stations
Proof will use as building blocks lists with
smaller values of
Assume k divides n
Discrete Algs for Mobile Wireless Sys
21
Random Queries
Let Q1, …, Qp be a list of queries where
p is approx k/2
each query is of size n/k
each query is chosen uniformly at random from
the C(n,n/k) possibilities
Lemma 1: Each Qj isolates one member of
the input with probability > 1/2e2, no matter
the result of previous queries.
Discrete Algs for Mobile Wireless Sys
22
Proof of Lemma 1
Suppose k = 1.
Then we have one query, of size n/1 = n.
Since only one station is contending, this query isolates it.
Suppose k = n.
Then we have n/2 queries, each of size n/n = 1, so each
query consists of one station.
At least half the stations are still contending at each
query.
So probability that the station chosen in Qj is still
contending is at least 1/2 > 1/2e2.
Discrete Algs for Mobile Wireless Sys
23
Proof of Lemma 1
Intermediate values of k: Pick some Qj. Let x =
|Ij-1|, number of colliding stations still to be
resolved.
worst case: x = k
best case: This is last query and all the previous ones
isolated a station: x = k - (p-1)
What is probability that Qj isolates a member of Ij1 (stations that are still contending)?
Discrete Algs for Mobile Wireless Sys
24
Proof of Lemma 1
Consider a particular element z of Ij-1.
Number of queries (sets of size n/k) that contain z
but no other element of Ij-1 is C(n-x,n/k-1), the
number of ways to choose the remaining n/k-1
elements of the query (after choosing z) from the
n-x stations not in Ij-1.
There are x (size of Ij-1) different choices for z.
Probability that a randomly chosen query is one of
these is x*C(n-x,n/k-1)/C(n,n/k).
Calculations show this expression is > 1/2e2.
Discrete Algs for Mobile Wireless Sys
25
Behavior of Series of Queries
Lemma 2: The list of queries isolates at
least c*k members of the input with
probability > 1 - 1/ebk
c is a constant strictly between 0 and 1
b is a positive constant
Proof relies on repeated invocations of
Lemma 1 plus more probability and
calculations.
Discrete Algs for Mobile Wireless Sys
26
Converting Probabilities Into
Certainties
Theorem 1: For all k and n, there is a (c,k,n)universal list of length (k + k*log(n/k))
c is the constant from Lemma 2
Proof: Suppose we have a list Q1,…,Qt of
queries, each of size n/k, each chosen uniformly
at random.
Let random variable X be the number of inputs on
which the list isolates < c*k members.
Show that EX < 1: there exists a list that isolates
< c*k members on less than 1 (i.e., no) inputs.
This is the desired (c,k,n)-universal list!!
Discrete Algs for Mobile Wireless Sys
27
Proof of Theorem 1
Represent X as the sum of indicator random
variables, one for each input:
XI = 0 if list isolates ≥ c*k members of I
XI = 1 if list isolates < c*k members of I
Claim: If number of queries is large enough, then
EXI < 1/C(n,k) for all inputs I
EXI = Pr(list isolates < c*k members of I)
probability goes to 0 as list length increases
so there is some value, call it t, such that EXI < 1/C(n,k)
Discrete Algs for Mobile Wireless Sys
28
Proof of Theorem 1
EX = ∑I EXI < ∑I 1/C(n,k)
= C(n,k)*1/C(n,k) = 1
Recall there are C(n,k) choices for I.
How big does t (list length) have to be?
Break query list into m groups of size p (same p
from before, about k/2).
Apply Lemma 2 to each group:
prob of isolating < c*k members at the end of each
group is < 1/ebk
actually probability is even smaller, since some
members have already succeeded and dropped out
Discrete Algs for Mobile Wireless Sys
29
Proof of Theorem 1
Since groups are independent, prob that all
m groups isolate < c*k members is < 1/ebkm
To ensure 1/ebkm < 1/C(n,k), set
m = ln(C(n,k))/bk + 1
t = m*p = ln(C(n,k))/(2b) + k/2
= (k + k*log(n/k))
use Stirling's formula for last step
Discrete Algs for Mobile Wireless Sys
30
Creating Final List
Use lists from Theorem 1 as building blocks and
combine them together to get desired list.
Theorem 2: For all k and n, there is a (1,k,n)universal list of length (k+k*log(n/k)).
Proof: For appropriate value of p (TBD), apply
Theorem 1 p times to get p query lists L0, …, Lp,
where
Li is (c,k(1-c)i,n)-universal
Li has length (k(1-c)i + k(1-c)i log(n/(k(1-c)i))
Let the final list be L = L0, L1, …, Lp-1.
Discrete Algs for Mobile Wireless Sys
31
Final List Isolates All Stations
Show L is (1,k,n)-universal.
Consider any input I of size k.
Applying L0 to I isolates at least c*k elements, by Theorem
1, leaving a set J1 of size at most k - c*k = k(1-c).
Applying L1 to J1 isolates at least c*k(1-c) elements, leaving
a set J2 of size at most k(1-c) - c*k(1-c) = k(1-c)2.
…
Applying Lp-1 to Jp-1 isolates at least k*c(1-c)p-1 elements,
leaving a set Jp of size at most k(1-c)p.
To ensure that size of Jp < 1, choose p so that
k(1-c)p ≤ 1-c, i.e., p is log, base 1-c, of (1-c)/k.
Discrete Algs for Mobile Wireless Sys
32
How Long is Final List?
It is the sum of the lengths of L0, L1, …, Lp.
Do some algebra to verify that the sum is
(k + k log(n/k)).
k
k/2
k/4
k/8 k/16
Lengths of the lists decrease in a geometric progression
Sum of the lengths is only a constant multiple greater than length of first list
Concatenated list isolates enough stations so that < 1 remains, meaning it
isolates all stations
Discrete Algs for Mobile Wireless Sys
33
Observations
Can extend the previous analysis to show that a
random list of c(k + k log(n/k)) queries resolves k
conflicts with high probability, for appropriate
constant c.
This provides a nonadaptive algorithm: just
choose that number of queries at random,
regardless of the feedback.
Future work:
constructive proof (find an algorithm)
close gap between upper and lower bounds
Discrete Algs for Mobile Wireless Sys
34