Research Questions and Platforms for the Next-Generation Wireless Internet
by Brad Karp, University College London 

Abstract:
In this document, I share rough thoughts on which research questions
are most pressing for the next-generation wireless Internet, and which
platforms hold promise to allow our community to investigate these
questions. It would be helpful to first define the scope of
"next-generation wireless Internet." For the purposes of this
document, I include under this umbrella mesh networking (fixed nodes
that form a multi-hop network at the Internet's edges, used to carry
users' commodity Internet traffic) and sensor networks (fixed,
resource-constrained nodes that form a multi-hop network used
primarily to collect measured data). I've explicitly chosen to leave
mobility outside the scope of this (brief!) document, as I do *not*
believe it to be one of the more pressing challenges facing wireless
systems.

Before considering currently pressing questions and platforms, though,
it is instructive to briefly review aspects of the past 10 years of
wireless networking research, to attempt to extract lessons from
experience. The reader is no doubt aware that perhaps the single
greatest research focus in the broad wireless networking community has
been on routing. Much of this work falls under "ad hoc routing," where
most or all nodes are mobile, and the topology of the network changes
rapidly. After DSDV and DSR, a slew of other routing protocols were
proposed. Later designs focused increasingly on scalability:
geographically inspired routing schemes such as GSPR/CLDP and NoGeo
kept routing state at each node to be O(1-hop neighbors), rather than
O(N) in an N-node network. BVR was simpler and more robust than NoGeo,
and kept only a bit more routing state: O(1-hop neighbors * B), where
B grows extremely slowly with N. Only in the past year, VRR and S4
have been proposed, both of which keep O(sqrt(N)) routing state per
node, and offer very low stretch (the latter, provably so). We
evaluate such routing schemes using metrics including packet delivery
success rate (for routing only, factoring out link-level loss),
routing protocol overhead, path stretch, and (in protocols after DSDV
and DSR) state per node.

   Claim: we've no need for another routing algorithm for multi-hop
   wireless systems!

VRR and S4 are now approaching stretch/state
tradeoffs that we know to be the best achievable, according to the
theory of compact routing; we have now reached the point of quibbling
about constants. What's more, the *practical need* for highly scalable
routing systems (for very large N) in wireless systems is in greater
doubt than ever. Sensornets, for example, hardly ever need any-to-any
routing; trees suffice for the vast majority of data-collection
applications. Discoveries of theoretical capacity limits also make
wireless systems with paths of more than a few hops seem of limited
importance. Gupta and Kumar's famous result shows that per-node
capacity falls as network diameter in hops increases, for *all*
wireless systems, when flow endpoints are uniformly distributed
throughout the network (modulo Grossglauser's result for mobile
networks, provided delivery latency requirements are loose).

History has further taught us that simulation-based evaluation for
wireless systems is often misleading. From 1997-2002, the wireless
extensions to ns-2 were a boon to the area, in that they provided a
common environment for apples-to-apples protocol comparison, and
lowered the barrier to begin working in the area. Alas, the ascendancy
of the 802.11 implementation in ns-2 in the wireless community set the
community back, too. The models of radio propagation (and more
generally, wireless channel behavior) fall so far short of the nuance
found in the physical world, simulations are extremely poorly
predictive (see the paper on CLDP for a painful lesson--at least to
the authors--on just how poorly).

More recent history, from roughly 2002 onward, however, has seen
testbed-based evaluation on the rise. MIT's Roofnet (now the startup
Meraki) used COTS 802.11bg radios and omnidirectional antennas, as a
ca. 40-node, single-channel Internet access network in an urban
environment. UC Berkeley's mote devices (the most recent generation of
which uses 802.15.4 radios) are used by the sensornet community in
many dozens of testbeds. Building systems has reinvigorated the
wireless research community, and this trend must continue.

   Claim: the CS networking community's reliance on inflexible COTS
   radios is limiting the progress of wireless research.

Today's 802.11 and 802.15.4 radios' MAC protocols are nearly entirely
fixed in hardware or firmware not readily modifiable by
researchers. Mote radios allow software control of link-layer ACKs,
and enabling/disabling CSMA (CCA), but don't allow changing of channel
coding (bit-rate). The rigidity of radio hardware limits research
systems in many ways, e.g., Roofnet often chooses bit-rates with high
packet-loss rates, because only bit-rates at powers of two are
available; ExOR must resort to batching of data packets to amortize
the high cost of user-generated ACKs on 802.11 radios; and WiLDNET
drives stock 802.11 radios on directional antennas to make links tens
of km long, and encounters highly time-varying loss rates--presumably
because the channel coding used by 802.11 performs poorly in this
scenario (one radically different than those envisioned by the 802.11
PHY's designers). There's no doubt that COTS hardware makes it
possible to build a testbed quickly, and we need to be able to build
real systems to advance the area. But how can we achieve more
flexibility for the systems we build?

I believe that improving the *practical* capacity and throughput
achieved in multi-user, multi-hop wireless networks is one of the most
pressing research questions we now face. And I believe that we need
more flexibility than COTS hardware affords to produce the best
answers to this question. An oversimplification of EE wisdom about
wireless capacity is: "small cells and low-power transmissions promote
spatial reuse, and thus give rise to increased total capacity." The
recent work on COPE/XOR in the CS community responds, "*overhearing*
allows enhanced inter-packet coding at layer 3, and thus gives rise to
increased capacity." These two arguments are at least partly in
opposition.  Reducing transmit power reduces overhearing, but
increases reuse, and so enables more concurrent transmissions. But
increasing channel bit-rate (at the PHY layer) often reduces
overhearing, yet *increases* capacity for one (or more)
sender-receiver pair(s).

What should the platform for building experimental wireless systems to
investigate the practical capacity conundrum look like? Perhaps the
most important property of a platform is software-controlled
flexibility: to vary channel coding and bit-rate, transmit power, and
the *entirety* of the MAC protocol. Generality of the hardware
platform is also highly desirable, as it allows sharing of
experimental infrastructure. For example, one could envision using the
same 200 instances of radio hardware both for separate sensornet and
Internet-access mesh network experiments (with radically different
software controlling the radio for each). Finally, the platform should
be easy to use for "layer 3 and up" researchers; this desirable
property suggests the need for a "library" of link types and MACs that
can be used as starting point, but are "hackable."

Given these desiderata, one promising platform (which I've begun
using) is software radio, an example of which is the Ettus Research
USRP radio hardware, driven by the GNU Radio software. The USRP is
highly modular: a single main board supports daughterboards for many
frequency bands. And the USRP is incredibly flexible: both the channel
coding and MAC are fully in software. The hardware is, however,
expensive: it is today ca. $1000 per radio, e.g., for 2.4-GHZ-ready
hardware. Software radio is CPU-hungry, too: it saturates a 3 GHz box
to receive 802.11b at 1 Mbps using the USRP and a (not-yet-public)
software 802.11 RX implementation developed at BBN. The flexibility of
the platform would seem to far outweigh its cost,
however. particularly if we are looking to build a shared
infrastructure for our community that will support the most diverse
range of experiments.

I close with one challenge unique to building a shared wireless
research platform: the physical environment is crucial to radio
propagation behavior. Thus, a naive "Internet in a rack" approach will
only allow experiments of, e.g., how a mesh network behaves in a rack
in a machine room. The cost of deploying one testbed in each physical
environment of interest is prohibitive, but each environment often
yields radically different results. Determining how to emulate
different physical environments with only one physical deployment of a
wireless research platform is itself an open research problem. A
promising avenue is that of wireless link emulators, like Glenn
Judd's; building on his initial prototype would be a valuable
contribution.