Transcript Introduction - Adaptive Systems Lab

Introduction






In recent years, the explosive deployment of Wireless
LANs worldwide has brought the entire gamut of Web
Applications to our fingertips.
Although existing systems provide a wide range of
services, they are highly inefficient.
The main goal of our ongoing research is to optimally
allocate resources among users in Wireless Networks.
Bandwidth and Energy are primary resources of interest.
Our framework studies a general multi-hop network.
Cellular and Access networks are special cases.
Applications of our Work



Data Services in Cellular Networks, similar to
IEEE802.11, HDR etc.
Access Networks: Existing WLANs can greatly
benefit by use of multiple hops to the base-station.
Sensor Networks:


Military Applications: Scatter smart devices over a field. Devices
configure themselves to form a high speed network. An instant platform
for communications in rough terrain.
Commercial Applications: Use sensor nodes to gather information about
traffic conditions, volcanoes, earthquakes etc.
Problem Scenario
Decentralized Control
Notations and Definition







N user network.
Routes between users are given.
A directed link e = {i,j} is a valid signal transmission from
node i to node j. Total of L links in the network.
A subset of L links is called a transmission mode.
There are 2^N transmission modes for a N user system.
Link Scheduling Policy: The time fractions associated with
each transmission mode constitutes a scheduling policy.
Power Control Policy: The power used by each node in
each slot constitutes a power control policy.
User Objective Vs Network Objective




User Objective: Each user would like to get the highest
possible rate while using a limited amount of energy.
Network Objective: The network may choose to maximize
the total data transferred for a given amount of energy
used.
Alternately, a network may choose to minimize the total
amount of power consumed while meeting minimum rate
guarantees per user.
We assume that the connections supported are long enough
and users always have data to transmit. E.g. file transfers,
video/audio streaming etc. For short-life connections we
could employ lightweight heuristics instead.
Current Approaches


Most approaches decouple link scheduling from power
control policy. We propose an integrated approach.
Links are scheduled such that the interference experienced
by the scheduled link is negligible (~ ambient noise).





Theme: Schedule nodes that are far away from each other
simultaneously.
Such approaches allow users to transmit at peak power.
These approaches exploit spatial diversity by allowing
multiple transmissions concurrently.
Sub-optimal with respect to system capacity maximization.
They do not exploit spatial diversity optimally.
Overhead: Require limited processing of topology
information but compute the link schedule using a
centralized entity.
Conflict-Free Link Scheduling Policies





Graph Theoretic Approach.
If a node is transmitting is a slot, nodes in its vicinity
cannot transmit in that slot.
The underlying assumption in most link scheduling
algorithms is to limit interference to a very small value (~
ambient noise)
For a N node multi-hop network: The problem of
computing the transmission schedules with optimal
throughput is NP-complete Computing a Maximum
Independent Set in a Graph.
Polynomial time approximation algorithms have been
proposed.
Previous Work on Link Scheduling








Work Done by: Victor Li & Ji-Her Ju
Consider a single channel TDMA network with N mobiles.
The TDMA frame consists of q sub-frames each q slots
long.
Each user is allocated q slots, one in each sub-frame.
Problem: Maximize the worst-case throughput of the
network such that all users have at least 1 slot in each subframe to transmit.
Throughput : Defined as number of conflict-free
transmissions in a frame.
Collision occurs when 2 or more nodes within a 1-hop
distance in connectivity graph transmit simultaneously.
A central controller allocates q slots per user so that there
are at most k collisions between any two users in a frame.
Work on Link Scheduling Cont…

Inputs to the Algorithm are:





N : total number of nodes
D : Maximum Degree of any node in the network
Given N and D, the algorithm finds a suitable q and k so
that the worst-case Tput, (q – k D)/(q^2) is maximized.
A centralized entity computes the schedule and broadcasts
it to all the nodes in the network.
Pros
Cons
Maximizes the Worst-case
Throughput.
Simple to compute Schedules
Schedules can be updated
infrequently

Scheduling policy is Centralized.
Blind to Changing Channel
Conditions.
Fails to exploit the peak wireless
channel, unlike our approach, HDR
Topology Immune Algorithm: N and D are slowly varying quantities, but
assumes worst case scenario.
Joint Link and Packet Scheduling







Work done by: Timely Research Group, UIUC.
Proposed a suite of Wireless Fair Queuing (WLFQ)
algorithms to achieve packet level fairness in Cellular
Networks.
WLFQ algorithms assumed that users could transmit in
every slot, not the case in the multi-hop scenario.
Extend the notion of Wireless Fair Queuing to the multihop network paradigm.
They incorporate the effects of spatial diversity into
fairness.
Link Schedules are determined based on a simple heuristic.
The WLFQ algorithm is augmented to account for link
schedules.
Joint Link and Packet Scheduling Cont…


A Centralized entity takes as input the flow weights at each
node, and the set of neighbors to compute link schedules.
How do nodes communicate with the centralized entity?





A commonly proposed technique to communicate update
information to a central entity is to maintain a minimum spanning
tree among the N nodes
Nodes in the vicinity (2-hop) of each other have an edge in
the flow contention graph G(V,E).
Packets whose deadlines are about to expire are scheduled
first. The rest of the links are chosen based on MIS.
If flow i* has been picked based on WLFQ, the remaining
flows are picked such that they form a Maximum
Independent Set (MIS) in the sub-graph G – N(i*), where
N(i*) is the set of nodes in the vicinity of flow i*.
Computing an MIS is an NP-complete problem.
Maximum Independent Set








They resort to a polynomial time approximation algorithm
to compute the MIS of the graph.
Given a graph G(V,E), a independent set S of a graph is a
set of nodes in V such that if nodes {i,j} is an edge in the
graph, then either i or j belong to S.
MIS: Independent set with the highest cardinality.
Choose initial set of links L_i based on packet deadlines
assigned by WLFQ at different nodes.
For each node i, pick node with the minimum degree in the
sub-graph G – N(i) for concurrent transmission.
The final set is the set of concurrent scheduled
transmissions.
Approximation ratio :(D + 2)/3
Runtime: O(N^2)
System Model






N user network.
Slotted CDMA multiple access network.
Routes between users are given.
A link e = {i,j} is a valid signal transmission from node i to
node j. Total of L links in the network.
A subset of L links is called a transmission mode.
Nodes can transmit and receive in the same slot.



A node can transmit to multiple receivers at the same time.
Nodes can receive data from multiple transmitters concurrently.
Total amount of bandwidth available: W
System Model Contd…





Path-loss from node i to node j is G(i,j).
Assume a slow fading channel. i.e. G(i,j) changes slowly
with time (frame length).
The power of signal transmission of node i to node j : P(i,j)
The signal to interference-plus-noise ratio for node i’s
transmission at node j is: SIR(i,j)
The link capacity characterization: C(i,j)



Shannon Capacity: C(i,j) = log(1 + SIR(i,j) )  is not delay
limited, assumes interference has a gaussian distribution.
We consider linear characterization: C(i,j) = W’ SIR(i,j)
Our characterization of capacity: Loss-rate bounded and Delay
limited and thus practical. This characterization is widely used in
the research world.
System Model Contd.




Rate of link e = {i, j} : X(i,j) = C(i,j)
The rate for link e in slot k is Xk(i,j) = W’ SIRk(i,j)
The weight associated with link e is Ø(e)
Refer to the *.pdf file for the continuation of this slide.
Mobile Ad Hoc Networks
Autonomous Distributed Systems
All mobile nodes, all wireless connections
What we have done?



Problem A: Find a link scheduling and power control
policy that maximizes the average multi-hop network
capacity subject to peak power constraint per node and
average power constraint per node (link).
Problem B: Find a link scheduling and power control
policy that minimizes the total power consumed in the
multi-hop network subject to peak power constraints per
node and minimum average rate guarantees per node
(link).
We have developed algorithms to solve both the above
problems
Observations

Some observations:






Problem A and Problem B have objective functions with at most
2^N variables and N+1 constraints.
Solving problems of such size is hard, we use convex duality
approach to solve the above problem.
The complexity of our algorithm is a low order polynomial in M:
where M is the number of allowed transmission modes. Algorithm
converges in a finite number of steps.
Complexity of our algorithm can be further reduced if we assume
that: Nodes cannot transmit and receive at the same time.
The number of optimal transmission modes is typically (<= N+1).
As the level of ambient noise increases, the number of concurrent
transmissions increases as well.
Cellular Network Paradigm






Highly Practical for Cellular Networks: For an N-user Kbase station system with a total of M transmission modes
per base station, the worst-case complexity of our
algorithm is O(MK).
The average case (more realistic) complexity is
significantly less.
Our algorithm is exactly the same for both uplink and
downlink communications.
Alternately, one could use a powerful decoding scheme,
Successive Interference Cancellation (SIC) to get high
rates.
SIC is only effective if interference has a Gaussian
distribution.
This is however not practical for multi-hop networks.
Simulation Environment




Six user single cell network.
Users have an average power = Peak Power/4
Compare simulations with respect to K-TDMA policy.
K-TDMA transmission policy





The total number of concurrent transmissions is equal to K.
Each transmission mode gets to transmit for equal amounts of
time.
This policy meets the average power constraint with equality.
HDR is a 1-TDMA policy
Our policy outperforms all other polices for all values of
ambient noise (external interference).
Simulation Results
Simulation Results Cont…
A Note on Energy Efficiency

Energy Efficiency Quotient = (total data
transferred/ total power consumed):




Solutions of Problem A and Problem B: Near Optimal
Energy Efficient.
Use the solution of Problem A as inputs to Problem B
Solution to Problem B is optimally energy efficient
with respect to the network in the real sense of the
word.
The final solution also maximizes system capacity,
meets average minimum rate guarantees and average
power constraints per node (link).
Conclusions








Solved two resource allocation problems in the realm of
wireless networks.
Performs better than HDR for dense networks.
Unified Link Scheduling and Power Control Approach:
first known results.
Developed a suite of low-complexity near optimal
heuristics.
Developed an online routing policy, not mentioned here.
General Idea: Opportunistic in the short-term (slot-level),
fair in the long term (frame or sub-frame-level).
Identified a number of applications for our results.
Would like to better understand the dynamics of the
wireless channel using a real test-bed.
Current work on test-bed implementation





Monarch at Carnegie Mellon were the first to
implement a multi-hop network test-bed.
They implemented dynamic source routing
(DSR) for nodes in a multi-hop network.
Insignia at Columbia Univ. integrated an adaptive
QoS module with Monarch’s DSR module.
Code for both implementations is freely available
for BSD Unix.
We must use their work to our advantage.
What we propose to do?





Set up a programmable test bed with a few laptops
with IEEE802.11 cards.
Set up a few access-points campus wide.
Implement our integrated routing, link/packet
scheduling and power control policy.
Short-term objective: Study a network of
stationary nodes.
Long-Term objective: Study a network of mobile
nodes.
Monarch Project


Among the first university-based multi-hop network test
bed implementations.
Setting: Outdoor Environments, Mobile nodes.


8 node multi-hop network


2 stationary nodes, 5 mobile nodes and 1 roving node that monitors
the others.
8 Laptops equipped with




Constant topology changes causes need for dynamic routing
policies.
Lucent Wavelan-1 cards.
GPS receiver to track position: Accurate to 1 meter.
Laptops and accessories racked up in rented cars.
Implement Dynamic Source Routing Module on all
laptops.
How does DSR Work?







Route Discovery and Route Maintenance.
A source node S queries its neighbors with a Route
Request packet.
Neighbors with a route to destination D, send all path
information from themselves to D, with a Route Reply
packet.
Node S chooses one of many paths arbitrarily, but caches
the all of them.
If no path can be found to node D, the query is flooded
into the network.
If a route to D is then found, node S and all intermediate
nodes cache this route.
The gateway also checks if D lies within its subnet or not.
How does DSR Work? Cont…



If the gateway finds a route to D, it replies back to node S.
Else, it sends a Route Error packet to S.
How do nodes know who their neighbors are?







Through IEEE802.11’s Link-layer ACK mechanism.
By reading GPS information embedded in data packets
periodically.
If a path breaks due to node mobility, a Route Error
message is sent to node S.
DSR: On-Demand Routing.
Packets used the IPv6 extension header processing
framework.
Aggressive querying of neighbor’s cache limits Route
Request propagation.
Can be greatly improved with power control.
In-Lab Network Emulation

A useful tool for network emulation was a MAC-filter.







MAC-filter: a filter that only processes legitimate packets.
Drops packets if their source IP addr. matches any on the
forbidden src IP addr. list.
Nodes used a trace file of routing table entries and MACfilter lists to perform their respective route discovery
operations.
Enabled routing of physically close nodes through an
intermediate node.
Allowed them to emulate a multi-hop network in a single
room.
Enabled easier testing of a wide range of scenarios.
Easier debugging and validation of their code.
Logging and Support Utilities

Visualization Tools: Track nodes using GPS and view 1second interval snapshots at the field office.



Nodes use tcpdump() to record per-packet information.




Helpful in spotting unpredictable behavior.
Sieve out packet losses due to channel errors from those due to
routing errors in post-run analysis.
They record signal strength (SIR) and signal quality (Frame
error rate) for each received packet.
Packet arrival times and sequence numbers are also recorded.
Post-processing: Compute the goodput of the system after
each test-run.
Bottom Line: Knowledge of node positions is necessary to
diagnose network dynamics in real-time and non-real-time.
Lessons Learned

Lack of route diversity with 8 nodes.



Multi-level priority queues are worth implementing.





Control Information should be given higher priority over data.
In-lab testing is critical for success.


Hard to construct multiple routes between nodes.
Our solution to that: Use Power Control.
Use of MAC-filter enabled them to test diverse scenarios.
Use of GPS receivers, provided valuable insight about the
goings-on during test-runs.
Visualization tools aided in on-line and off-line diagnosis.
Wireless propagation: not what you would expect.
Personnel management was not trivial.
The Insignia Project
Provides something better than best effort service
for some flows, e.g., video, voice.
Hard QoS guarantee not possible in MANET
 Adaptive QoS
 Service Differentiation
e.g., QoS insensitive flows can be serviced in best effort manner: e-mail
QoS sensitive flows should be treated in better than best effort manner
INSIGNIA Features
Approach
• Adaptive QoS approach
• Service Differentiation via packet prioritization
To provide adaptive QOS
 Fast Reservation
 Fast Restoration
 QoS reporting – a feedback mechanism
 Adaptation according to network conditions
INSIGNIA Principles
In band signaling
 to be responsive
- requires only single packet on new path to initiate the restoration after rerouting
- explicit out-of-band signaling is not responsive enough and often fails to reach
the target mobile nodes
Soft-state
 for management and maintenance of resource reservations
 first packet on new path create states (if necessary) and
subsequent packets refresh the previous associated reservations en-route
 outstanding reservations and states automatically time out
(i.e., typically in seconds range.)
INSIGNIA IP option
SERVICE
MODE
PAYLOAD BANDWIDTH
INDICATOR INDICATOR
RES/BE
BQ/EQ
BW_IND
1 bit
1 bit
1 bit
BANDWIDTH
REQUEST
MAX
MIN
16 bits
SERVICE MODE : adaptive (RES) service / best effort service
PAYLOAD INDICATOR : base quality (BQ) packet / enhanced quality (EQ) packet
BANDWIDTH INDICATOR : reflects the resource availability en route
BANDWIDTH REQUEST : indicates the max/min BW requirements
Reservation Set-up
M2
MS
MD
M1
M3
M4
QOS report : MAX reservation established
Packets Received at Destination Mobile Node
RES
BQ
MAX
Max_BW
Min_BW
RES
EQ
MAX
Max_BW
Min_BW
Legend
RES/BQ packet
RES/EQ packet
BE
packet
MAX reserved link
MIN reserved link
Re-routing / Restoration
M2
MS
M2
MD
M1
M3
Rerouting
Rerouting
M4
immediate restoration
Legend
RES/BQ packet
RES/EQ packet
BE
packet
MAX reserved link
MIN reserved link
Re-routing / Degradation
EQ degradation
: degraded to minimum service
M3
MS
M1
M3
MD
M5
Rerouting
Rerouting
bottleneck
M4
node
Packets Received at Destination Mobile Node
RES
BQ
MIN
Max_BW
Min_BW
BE
EQ
-
Max_BW
Min_BW
M5
Legend
RES/BQ packet
RES/EQ packet
BE
packet
MAX reserved link
MIN reserved link
Adaptation : Scale Up
Packets sent by Source Mobile Node in MIN service
RES
BQ
MAX
Max_BW
Min_BW
MAX service re-initiated
MS
constant resource availability
detected
resource now available
MD
M1
M5
bottleneck
bottleneck
M4
node
node
Pkts Received at Destination in MIN service
QOS
RESreport
BQ : Scale
MAX Up
Max_BW
Min_BW
Legend
RES/BQ packet
RES/EQ packet
BE
packet
MAX reserved link
MIN reserved link
INSIGNIA Summary
INSIGNIA performs
 fast resource reservation
 responsive restorations and,
 timely adaptations.
QoS reports function as
- notification of flow set up completion,
- report for on-going service quality and
- also used for triggering adaptation process.
In band nature allows INSIGNIA to be responsive enough to deal with the
frequent rerouting
Soft state approach guarantees the release of outstanding reservations on
old path
How to Improve Network Performance








Monarch and Insignia are implemented on a IEEE802.11
WLAN.
The above projects test their network under light-tomoderate loads.
IEEE802.11 does not scale well with the number of users.
In dense neighborhoods, high contention for data slots
results in frequent collisions in the reservation slots.
IEEE802.11 uses the point coordination function,
servicing one node at a time under such circumstances.
We need the same functionality in a multi-hop network, i.e.
link scheduling by the access point.
Our resource allocation policies achieve substantial
improvements in network capacity, theoretically.
We would like to verify the profundity of our results in a
real network.
Our Proposal

Implement Power Control.



Implement a variety of link and packet scheduling
policies. This requires nodes in the network to be in sync
with each other.





Nodes can change their power levels depending on the population
density around them.
Power control can be done using certain WLAN cards. e.g. 3Com
cards.
Nodes in an IEEE802.11 network are already synchronized to
their Access Point (AP).
AP’s beacon the correct time to all the nodes in their domain.
AP’s could choose to flood the network with the correct time. This
method might not be accurate enough.
Alternately, GPS receivers at nodes can synchronize them to
desired accuracy (sub-millisecond).
Implement alternative routing strategies.