Transcript Resource Allocation in Wireless Networks

Announcements

Homework 2 due Friday (flexible).

Graded Paper 2 summaries ready.

HW 1 and solutions ready this week.

Third paper summary on ad-hoc
networks due today (flexible).

Final project reports due by noon next
Tuesday (inflexible). Post to website.

Extra credit assignment: Read the final report
for the project you originally gave comments
on. Send an email critique to the authors with
a copy to me (by midnight Tuesday).
Ad-Hoc Wireless
Networks

Main Characteristics







Each node generates independent data
Any node can communicate with any other.
No centralized controller (self-configuring)
Data transmitted in (short) packets
Links typically symmetric.
Nodes may be mobile and/or power constrained.
Typically a large number of nodes
What has changed
since 1985?

Better, cheaper, low power DSPs

Advanced communication techniques
 Powerful channel codes and decoders.
 Equalization/SS/Multicarrier
 High level modulation
 Diversity/MUD/smart antennas

Advances in routing

Signal strength measuring techniques
available in radios.

Adaptive radios.
How would we leverage these developments
to make better ad-hoc networks?
Sensor Networks

Sensor Networks









Energy is the driving constraint.
Data highly correlated in time and space.
Node location information critical
Low homogeneous rates.
Links typically asymmetric.
Data flows to centralized location.
1000-100,000 Nodes
Have a common mission.
Very different from typical ad-hoc networks
Link Layer Design

Fundamental limits
 “Shannon capacity” versus energy

Processing to reduce transmit power
 Diversity (multinode combining)
 Coding
 Adaptive modulation (probing)
 Adaptive framing
 Beamforming
 Processing vs. transmitting bits

Data Processing
 Compression via local decisions
 Data prioritization
 Data distribution (“need-to-know”)

Variable node alertness
 Sleep modes
 Hierarchical power conservation modes
Network Layer Design

Network Capacity

Routing



Topology





Delay/throughput/energy tradeoffs
Distributed control
Dense deployment
How many hops per connection?
Effect of adaptive link techniques
Supernodes vs. homogeneous nodes
Adaptive Techniques



Multiple access.
Link adaptation to maximize
throughput
Network optimization versus link
optimization.
Application Design

Design Optimization



What is the “mission” of the network.
Tradeoff between longevity and
capability.
Longevity driven by application

Data Prioritization

Collective Data Processing





Can compensate for node limitations
Compression and clustering
Requires additional communication
between nodes
Multiuser game theoretic approaches
Energy optimization:

minimize total energy (between
processing and communication)
required for mission success
Network Capacity

Capacity limits of ad-hoc 2D
networks.


Measured as throughput of each node
to another randomly selected node
Assumptions






n users uniformly distributed over the interior
of a unit cube.
Each user communicates with another user
randomly chosen among all users.
Nodes communicate at fixed rate W or when a
minimum threshold SIR is met.
Interference from nodes outside a disk around
receiving node negligible
Alternate SIR model (iuterference as AWGN)
No channel division or diversity
Capacity Bounds

Capacity Definition:


Average rate (bps) transmitted by any
user to another randomly selected user.
Lower Bound
 W



 ( n)   

 n log n 


Based on deterministic routing scheme and
partition of network area.
Upper Bound
W 

 n
 (n)   


Uses convexity and aggregate rate
In 3D, bounds proportional to 1/n1/3
Capacity goes to zero as n increases
Summary and
Open Problems

Multiple Access Techniques

Capacity

Random Access

Cellular System Design

Cellular Capacity and ASE

Power Control

Dynamic Resource Allocation

Ad-Hoc Networks

Sensor/Energy Efficient Networks

Wireless impact on higher level
protocols
Multiple access
techniques

TD, FD, and orthogonal CD
support same number of users

DS spread spectrum typically
supports fewer users
 capacity flexible (soft capacity)
 Improved by MUD, activity, etc.

FH not typically used alone as a
MAC technique
 Averages out-of-cell interference

Open Problems
 Tradeoffs
 Tradeoffs
in wideband channels.
without perfect CSI
Capacity (1 cell)

User capacity


Computed for DSSS systems
Inherent assumptions needed


Shannon capacity




Obtained for fading broadcast and
MAC channels
Optimizes resource allocation
TD and FD equal, CD best or same as
TD depending on MUD
Outage capacity




BER, channel, voice activity, etc.
Keeps rate constant over all fading
Optimizes resource allocation
Useful for delay-constrained data
Open Problems



Wideband channels/Imperfect CSI
Combined Shannon/outage capacity
Capacity with multiple antennas
Random Access

ALOHA inefficient

Channel sensing ineffective

Busy tones work well in some
topologies, but not ad-hoc nets

Reservation protocols inefficient
for short messaging

Different media types require
different access techniques

Open Problems:


Multimedia techniques
Satisfying QOS/delay constraints
Cellular System
Design

Minimize reuse distance and cell size

Optimal access technique is in the
eyes of the beholder (stockholder).



Interference reduction is good!!!





User capacity calculations skewed
Tradeoffs in complex systems hard to
assess - implementation considerations
Sectorized/Smart antennas
Power control
Dynamic resource allocation
Multiuser detection
Open Problems
Optimizing/implementing interference
reduction techniques
 Impact of multiple antennas
 Impact of packet data and multimedia

Cellular Capacity and
ASE

Preliminary Shannon capacity results
Simple channel model
 TD scheme
 Base station coordination (uplink)


ASE general formula (bps/Hz/Km2)




Based on MAC or broadcast channel
capacity region
Interference treated as noise
No base station coordination
Open Problems (Lots!!!)

Expand exisiting capacity/ASE results



Channels, multiple antennas, coordination, ...
Propose new capacity/ASE definitions
Develop outage capacity results
Power Control

Extremely powerful tool







Increases battery life
Maintains link SIR
Reduces interference
Component of resource allocation
Aids in smooth handoff
Reduces delays
Increases capacity/throughput

Distributed vs. Centralized

Active link protection


Combine with channel access
Open Problems
Impact of estimation errors
 Throughput/delay/power optimization
 Impact of noncooperative users
 Group vs. individual optimization

Dynamic Resource
Allocation

Optimally assigns available resources
based on traffic, user conditions, etc.





Optimal dynamic channel allocation
(MP) is NP hard





Channels (time, codes, BW)
Power (for transmission or processing)
Rate
Antennas
Heuristics often used (work well)
Little exact analysis - some bounds
FCA optimal at high loads
Optimal resource allocation NP harder.
Open Problems (Lots!!!)



Combinations (e.g. power/channels)
Antenna allocation
Processing power allocation
Ad-Hoc Networks

Wide open design issues at all layers
of the protocol stack
Access
 Channel allocation/freq. reuse
 Power adaptation
 Connectivity and Routing
 QOS


Synergies across layers should be
exploited

Performance measures and capacity

Open Problems (Everything!!!)
Sensor and Energy
Efficient Networks

Network optimization for energyconstrained nodes
Power tradeoffs for processing vs.
transmitting bits
 Longevity vs. network function
 Energy-conserving modes


Collective data processing

Diffuse routing

Open Problems (Everything!!)
Wireless impact on
higher layers

Routing must take user mobility
into account



Network protocols react to errors
using congestion control



Mobile IP not designed for rapid
movement
Base stations may not be available for
handoffs
Does not correct for link failures due to
fading
Significantly slows down network when
links fade
Open Problems

Design of protocols that take wireless
channel into account without breaking
the great features of current protocols