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