FOOTLOOSE NETWORKING
by Gunnar Karlsson

Abstract:
Wireless enables mobile communication. But mobility also disrupts wireless
communication when people roam into areas that are not covered by a cellular
infrastructure, and when a population forming an ad hoc network disperses. My
proposal is to design systems for mobile communication that scale gracefully
with the degree of connectivity and, hence, allow networking to be
footloose. There are two aspects to this. The first is to leverage the
mobility for supporting the communication; the second is to assist the
evolution of the infrastructure so that it swiftly extends to cover the most
trodden trails of the mobile nodes. Realistic mobility modeling is vital for
the evaluation of both aspects.

Mobile nodes that come in contact may support one another by carrying and
forwarding messages. A challenge is to make the arbitrarily short contacts
useful for communication. Brief contacts mean that the handshaking between two
nodes must be instantaneous and that the transmission capacity must be high to
maximize the transferred volume of data. For example, Bluetooth takes 10
seconds or more to establish a connection, and it might be followed by
handshaking at higher layers. Hence, a connection establishment would consume
much of the contact time between two pedestrian nodes that move in opposing
directions. Cross-layered design can give solutions for quick connection
establishment at all protocol layers simultaneously. Another challenge is to
make a useful service out of a chain of intermittent contacts, where data are
delivered in random order, sporadically and incompletely. Artificial ordering
constraints in the protocols may be removed [1], and flow and error controls
must be re-thought [2].

The second aspect of supporting footloose mobile communication concerns a
mechanism that drives the evolution of the infrastructure to extend its
coverage. The mechanism is based on reports from mobile nodes and access
points. As users roam around, their devices may record where there is network
coverage and where not. The number of reports from uncovered areas indicates
the traffic demand that has been missed due to lack of a network
infrastructure. The access points can report on traffic load and whether the
traffic comes from the rim or the center of the cell [3]. These reports are
gathered in a central or distributed database that can be consulted to
determine good locations for deploying new cells. This reporting system,
together with the network operators who put up access points, form a feedback
system that drives the deployment towards saturated coverage in the shortest
possible time.

Capturing mobility in all its facets is essential for the evaluation of the
design of the mobile communication system as well as the mechanism to expedite
the infrastructure growth. Although mobility is an integral part of personal
communication, the people are conspicuously missing in much research on mobile
communication. The Swedish geographer Torsten Hägerstrand wrote an essay in
1970 entitled by a question: What about people in regional science? In the
essay he put forth the idea of a space-time geography that captures not only
the topography of a space but also the flow of people there [4]. A person’s
life becomes a path in this space-time geography. As a geographer he saw the
space as a landscape and the flow of people as constrained not only by the
landscape but also in terms of capability, coupling and authority. Capability
constraints are given by speed of movement for instance; the coupling
constraints refer to where, when and for how long an individual joins the
space-time paths of others (at a meeting for instance); constraints ordained
by authority relate to the control in space-time that an individual or group
of individuals may pose on others to restrict their mobility (curfew is an
example). Contrast Hägerstrand’s mobility model with the flat-earth
world view exposed by so many evaluations of mobile communication systems with
no landscape, no people and no constraints.

We must now take up Hägerstrand’s idea and progress on the inclusion of
mobility in our evaluations. There are promising advances—such as
CanuMobiSim [5], UDel Models [6] and the random-trip mobility model [7]—but
there is still need for research on large-scale mobility modeling to include
wide-area landscapes, constraints, and populations of hundreds of thousands to
millions of mobile users. Such a model needs to provide more than measures
over the collective of mobile nodes; it needs to report also on the view of a
single node. For instance, the frequency and durations of underflow of a
play-out buffer in a node may indicate whether the user is satisfied with a
streaming service in a given area. To study the growth mechanism for the
infrastructure, the dynamicity of the space-time geography must be captured
were the infrastructure evolves along the trails of the people, and the number
of users and their communication increase with the expanding
infrastructure. The models must be supplemented by measurements to establish
parameter values for the simulations. Finally to select among designs, our
community must establish benchmark tests for systems, protocols and
mechanisms. These should be based on a few simulation scenarios with given
topographies and mobility patterns.

The research program for footloose networking is in summary based on three
activities: The development of mobility models that capture how people
actually move; the design of mobile communication systems that can utilize
arbitrarily short and rare contact opportunities and that will profit when the
connectivity improves; the design of a feedback system that promotes the
growth of the infrastructure so that the connectivity improves also for those
how would like to be footloose.  References

[1] D. C. Feldmeier, “A Data Labelling Technique for High-performance
Protocol Processing and Its Consequences,” Proc. of ACM SIGCOMM, Ithaca,
N.Y., 1993, pp. 170-181. 
[2] K. Fall, “A Delay-Tolerant Network Architecture for Challenged
Internets,” Technical Report IRB-TR-03-003, Intel Research Berkeley,
February 2003. 
[3] H. Velayos Muñoz, Autonomic Wireless Networking, Ph.D. Thesis, KTH, 2005. 
[4] T. Hägerstrand, “What about people in regional science?” Papers
of the Regional Science Association, 24:7-21, 1970. 
[5] I. Stepanov, P. Marron and K. Rothermel, “Mobility Modeling of Outdoor
Scenarios for MANETs,” Proc. of 38th Annual Simulation Symposium (ANSS 38),
San Diego, USA, April 2005.
[6] J. Kim, V. Sridhara and S. Bohacek, “Realistic Mobility Simulation of
Urban Mesh Networks,” Submitted 2006, URL
http://udelmodels.eecis.udel.edu/publications1.php 
[7] J.-Y. Le Boudec and M. Vojnovic, “Perfect Simulation and Stationarity
of a Class of Mobility Models,” Proc. IEEE Infocom 2005, Miami, FL, 2005 

Gunnar Karlsson
School of Electrical Engineering
KTH, Royal Institute of Technology
10044 Stockholm, Sweden
gk@ee.kth.se