...

Mobility and Routing in a Delay-tolerant Network of Unmanned Aerial Vehicles by

by user

on
1

views

Report

Comments

Transcript

Mobility and Routing in a Delay-tolerant Network of Unmanned Aerial Vehicles by
Linköping Studies in Science and Technology
Thesis No. 1356
Mobility and Routing in a Delay-tolerant Network of
Unmanned Aerial Vehicles
by
Erik Kuiper
Submitted to Linköping Institute of Technology at Linköping University in partial
fulfilment of the requirements for the degree of Licentiate of Engineering
Department of Computer and Information Science
Linköpings universitet
SE-581 83 Linköping, Sweden
Linköping 2008
Mobility and Routing in a Delay-tolerant Network of
Unmanned Aerial Vehicles
by
Erik Kuiper
April 2008
ISBN 978-91-7393-937-9
Linköping Studies in Science and Technology
Thesis No. 1356
ISSN 0280-7971
LiU-Tek-Lic-2008:14
ABSTRACT
Technology has reached a point where it has become feasible to develop unmanned aerial
vehicles (UAVs), that is aircraft without a human pilot on board. Given that future UAVs can
be autonomous and cheap, applications of swarming UAVs are possible. In this thesis we
have studied a reconnaissance application using swarming UAVs and how these UAVs can
communicate the reconnaissance data. To guide the UAVs in their reconnaissance mission we
have proposed a pheromone based mobility model that in a distributed manner guides the
UAVs to areas not recently visited. Each UAV has a local pheromone map that it updates
based on its reconnaissance scans. The information in the local map is regularly shared with a
UAV’s neighbors. Evaluations have shown that the pheromone logic is very good at guiding
the UAVs in their cooperative reconnaissance mission in a distributed manner.
Analyzing the connectivity of the UAVs we found that they were heavily partitioned which
meant that contemporaneous communication paths generally were not possible to establish.
This means that traditional mobile ad hoc network (MANET) routing protocols like AODV,
DSR and GPSR will generally fail. By using node mobility and the store-carry-forward
principle of delay-tolerant routing the transfer of messages between nodes is still possible. In
this thesis we propose location aware routing for delay-tolerant networks (LAROD). LAROD
is a beacon-less geographical routing protocol for intermittently connected mobile ad hoc
networks. Using static destinations we have shown by a comparative study that LAROD has
almost as good delivery rate as an epidemic routing scheme, but at a substantially lower
overhead.
This work has been supported by LinkLab, a research center for future aviation systems,
established by Saab and Linköping University, and the KK foundation through the industrial
graduate school SAVE-IT.
Department of Computer and Information Science
Linköpings universitet
SE-581 83 Linköping, Sweden
Acknowledgements
First I want to thank Saab, and then especially Anders Pettersson and Gunnar
Holmberg, for giving me this opportunity to pursue a PhD. With this thesis I
should be half way. Without the connection to a practically applicable
problem domain I would probably not have chosen to pursue a PhD. I also
want to thank my industrial advisor Mats Ekman. I might not have sought
your advice that extensively, but the discussions we had gave me some things
to think about.
To my academic advisor and supervisor Simin Nadjm-Tehrani I would like to
extend a thank for guiding me to this point. You especially taught me how to
write for an academic audience and not only to report my findings. I might
not entirely agree with the anatomy of academic articles, but hopefully I now
understand it reasonably well.
I also want to thank the other members of RTSlab for your friendship and
valuable comments. You helped me to become aware of some of the
assumptions I hade made and you pushed me to clarify and further
investigate some issues. I hope you will continue to take a coffee break at
three even after I am gone.
I am grateful to SAVE-IT and the KK foundation for partially funding my
research. You might not be in my thoughts every day, but without you this
research might never have been done.
Finally I want to thank my friend C. Without you I might never have selected
to work for Saab, and then this would never have happened.
Erik Kuiper
v
vi
Contents
1
Introduction .................................................................................................... 1
1.1
Mobile Ad-hoc Networks ..................................................................... 1
1.2
Intermittently connected MANETs..................................................... 3
1.3
Problem Description.............................................................................. 4
1.4
Contributions ......................................................................................... 6
1.5
Thesis Outline ........................................................................................ 7
2
Background ..................................................................................................... 9
2.1
Mobility Models..................................................................................... 9
2.1.1
Synthetic Mobility Models............................................................. 10
2.1.2
Real-World Mobility Models......................................................... 14
2.2
Routing.................................................................................................. 17
2.2.1
DTN Routing in Opportunistic Networks................................... 18
2.2.2
Beacons-less Routing ...................................................................... 20
3
Reconnaissance Mobility............................................................................ 23
3.1
Scenario................................................................................................. 23
3.2
Random Mobility Model .................................................................... 24
3.3
Distributed Pheromone Repel Mobility Model ............................... 25
3.4
Evaluation............................................................................................. 29
3.4.1
Scan Coverage ................................................................................. 30
3.4.2
Scan Characteristic.......................................................................... 34
3.4.3
Communication............................................................................... 37
4
Routing in DTNs.......................................................................................... 41
4.1
LAROD ................................................................................................. 41
4.2
Broadcast Delay-tolerant Routing (BDTR) ....................................... 46
4.3
Broadcast Routing (BR)....................................................................... 48
4.4
Evaluation............................................................................................. 48
4.4.1
Node density ................................................................................... 50
4.4.2
Node speed...................................................................................... 52
4.4.3
Time to live ...................................................................................... 53
4.4.4
Network load................................................................................... 55
5
Conclusions and Future Work ................................................................... 57
5.1
Conclusions .......................................................................................... 57
5.2
Future Work ......................................................................................... 58
6
Acronyms....................................................................................................... 59
7
References ..................................................................................................... 61
vii
viii
List of Figures
Figure 1.
Figure 2.
Figure 3.
Figure 4.
Figure 5.
Figure 6.
Figure 7.
Figure 8.
Figure 9.
Figure 10.
Figure 11.
Figure 12.
Figure 13.
Figure 14.
Figure 15.
Figure 16.
Figure 17.
Figure 18.
Figure 19.
Figure 20.
Figure 21.
Figure 22.
Figure 23.
Figure 24.
Figure 25.
Figure 26.
Figure 27.
Figure 28.
Figure 29.
Figure 30.
Figure 31.
Figure 32.
Figure 33.
Figure 34.
Figure 35.
Figure 36.
Change of average direction near the edges. ................................. 12
Forwarding areas............................................................................... 21
Local pheromone map after 3600 seconds of simulation. ............ 26
Global pheromone view after 3600 seconds of simulation. ......... 26
Local pheromone map after 7200 seconds of simulation. ............ 27
Global pheromone view after 7200 seconds of simulation. ......... 27
Pheromone search pattern................................................................ 28
Pheromone mobility coverage with global pheromone map. ..... 31
Pheromone mobility coverage with 100% transfer probability. .. 32
Pheromone mobility coverage with 50% transfer probability..... 32
Pheromone mobility coverage with 10% transfer probability..... 32
Pheromone mobility coverage with 0% transfer probability....... 33
Random mobility coverage .............................................................. 33
Random Waypoint mobility coverage............................................ 33
Comparison of average coverage. ................................................... 34
Pheromone mobility with global pheromone map. ...................... 35
Pheromone mobility with 100% transfer probability.................... 35
Pheromone mobility with 50% transfer probability...................... 36
Pheromone mobility with 10% transfer probability...................... 36
Pheromone mobility with 0% transfer probability. ...................... 36
Random mobility............................................................................... 37
Random Waypoint mobility............................................................. 37
Pheromone mobility with global pheromone map. ...................... 38
Pheromone mobility with 100% transfer probability.................... 39
Pheromone mobility with 50% transfer probability...................... 39
Pheromone mobility with 10% transfer probability...................... 39
Pheromone mobility with 0% transfer probability. ...................... 40
Random mobility............................................................................... 40
Random Waypoint mobility............................................................. 40
LAROD forwarding areas. ............................................................... 42
Illustration of vectors used for delay time computations. ........... 44
LAROD pseudo code. ....................................................................... 45
BDTR pseudo code............................................................................ 47
Delivery ratio for different node densities..................................... 51
Overhead for different node densities............................................ 51
Delay for different node densities................................................... 51
ix
Figure 37.
Figure 38.
Figure 39.
Figure 40.
Figure 41.
Figure 42.
Figure 43.
Figure 44.
Figure 45.
Delivery ratio for different node speeds. ....................................... 52
Overhead for different node speeds. .............................................. 53
Delay for different node speeds. ..................................................... 53
Delivery ratio for different packet life times.................................. 54
Overhead for different packet life times. ....................................... 54
Delay for different packet life times................................................ 55
Delivery ratio for different network loads. .................................... 56
Overhead for different network loads............................................ 56
Delay for different network loads. .................................................. 56
x
List of Tables
Table 1.
Table 2.
Table 3.
Table 4.
Table 5.
Table 6.
Table 7.
Table 8.
Table 9.
Table 10.
Table 11.
Table 12.
Table 13.
Random waypoint parameters ........................................................ 11
Gauss-Markov parameters. .............................................................. 12
Scenario parameters .......................................................................... 24
Random action table.......................................................................... 24
Pheromone map parameters. ........................................................... 25
Pheromone parameter definition. ................................................... 28
UAV pheromone action table. ......................................................... 29
Never scanned area........................................................................... 35
LAROD parameter definitions. ....................................................... 44
BDTR parameter definitions. ........................................................... 46
Scenario parameters .......................................................................... 49
LAROD parameter values................................................................ 49
BDTR parameter values.................................................................... 49
xi
1
1 Introduction
The sharing of information is vital for many tasks and the faster information
can be disseminated the sooner or better a task can be completed. With the
development of cheap wireless technologies like GSM and Wi-Fi information
is often available anytime and anywhere. The limitation of these technologies
is that they require an infrastructure of base stations to function. In
environments such as disaster areas or during wartime this type of
infrastructure is generally not available, but information exchange is still
desired. An option to communicate in these environments is to use long
range radios that enable point-to-point communication. The problems with
these are that they are often expensive, bulky and only provide low
bandwidth communication.
At the other end of the spectrum there are cheap, small, low power, high
bandwidth, but short range radio technologies. If a lot of nodes were
equipped with this type of radio then they could automatically form a
network and cooperate to forward messages for each other. These types of
networks that are cooperatively formed and do not rely on any infrastructure
are often called ad-hoc networks. To create local ad-hoc networks there exist
technologies like Bluetooth [45] and ZigBee [56], but the creation of larger adhoc networks is still in the research domain.
1.1 Mobile AdAd-hoc Networks
A mobile ad-hoc network (MANET) is a self-organizing network where
nodes with wireless radios cooperate to provide network connectivity. The
opposite of an ad-hoc network is a managed network where network
connectivity is provided by dedicated wireless access points. These access
points are generally non-mobile fixed installations and they are
preconfigured to efficiently share the wireless medium. Examples of
managed networks are GSM and Wi-Fi hotspots.
2
1
A basic service required from any network is the ability to route messages
from source to destination. In wireline networks, such as the internet, routing
is performed by dedicated equipment that exchange information with each
other to build up a view of the network links between routers and end
stations. This works well since links are stable and change infrequently. In
MANETs links are less stable due to mobility, interference and fading. This
means that the network layout is constantly changing and this has to be
handled by the routing protocol. These constant network changes are
challenging since it becomes practically impossible to distribute a consistent
view of the network to all nodes.
In IP based networking the IP address is both a machine unique identifier and
a hierarchical location identifier. This means that the address is the mean to
locate the node. In a network of mobile nodes hierarchical addressing is not
practical since nodes would constantly have to change address due to node
mobility. This means that each node will have to be a separate entry in a
routing table resulting in large routing tables for large networks.
The routing protocols suggested for MANETs can be classified into the two
dimensions proactive–reactive and topological–geographic. Proactive
protocols constantly maintain routing tables in the nodes while reactive
protocols only acquire routing information when it is actually needed.
Topological protocols build a view of the network based on how the nodes
can communicate with each other while geographical protocols route
information based on the geographical location of the nodes.
The most widely accepted topology based routing protocols for MANETs are
those accepted by the Internet Engineering Task Force (IETF). They have
published two proactive routing protocols (Optimized link state routing
(OLSR) [9], Topology dissemination based on reverse-path forwarding
(TBRPF) [35]) and two reactive protocols (Ad hoc on-demand distance vector
routing (AODV) [38], Dynamic source routing (DSR) [23]). They are currently
working on replacing these protocols with one proactive and one reactive
protocol.
There have been some published reports on the relative performance of these
protocols [8][18] and though far from conclusive they find that OLSR does
1
In this thesis the words message and packet are generally used interchangeably. If there is a
separation then a message is some coherent data that needs to be transmitted and a packet is the
physical format of (a part of) a message that is transmitted in the network.
3
not perform well in mobile environments compared to AODV and DSR
(TBRPF is not evaluated). The main reason is the functioning of the proactive
OLSR. With mobile nodes the protocol has to spend a lot of effort trying to
update the routing tables, tables that never will be accurate.
To remove the need to maintain routing information in routing tables
geographical routing protocols have been suggested where Greedy perimeter
stateless routing (GPSR) [24] is the most widely known. Instead of
maintaining a route to a destination a geographical routing protocol forwards
packets to the geographical location of the destination by locally at each hop
selecting a node that will reduce the distance to the destination. This
generally means that no global routing information needs to be maintained
by the nodes which it is good for highly dynamic environments. The Achilles
heel of geographical routing is how to distribute node positions in the
network so the sources know where the destinations are. For this there need
to be a location service the sources can access. A main problem with location
services is how to balance between the overhead of distributing the location
information to location servers and the cost of a location query [10]. A related
problem that has to be managed is node position errors in packets due to
node movement.
1.2 Intermittently connected MANETs
The routing protocols described in the previous section all assume that the
node density is high enough to guarantee the existence of a contemporaneous
path between any sender and receiver. A contemporaneous path is a
sequence of wireless links between two communicating nodes such that they
can communicate with each other instantaneously if the bandwidth was
infinite and there were no transmission delays. If such a path does not exist
they will fail to deliver messages. This does not mean that it is impossible to
route messages in the absence of contemporaneous paths, only that other
principles need to be used.
An intermittently connected MANET is a network where the nodes are so
sparse or moving in such a way that there exists at least two groups of nodes
for which there is no contemporaneous path between the nodes. If the node
movement is such that the intercontact times are unknown and unpredictable
then the node contacts are called opportunistic. The enabler to route in
intermittently connected networks is node mobility. To overcome
communication gaps messages are stored in nodes and carried until they can
4
be forwarded. A consequence of this store-carry-forward principle is that
2
delivery times will be longer than if a contemporaneous path existed .
Due to the long delays in these networks the connectivity assumptions made
in most networks are no longer valid. As a consequence the responsibility for
reliable transfers should be moved from the source-destination pair to a
system of custodians. The reason to not use the source-destination pair as is
normally done is that this generally requires many round-trip exchanges,
exchanges that take much time. Instead the responsibility of reliably
transferring a message is moved to the network and a system of custodians.
In such a system a message is transferred between custodians that take over
delivery responsibility of the message.
The most straightforward method to send a packet to a node whose location
is unknown and where the best path to reach it is unknown is to send it to all
nodes in the network. This is done by Epidemic Routing [51]. The problem
with this method is that it requires much bandwidth and storage resources.
The other extreme is to keep the packet in the source node until the source
node meets the destination node due to mobility as is done by Direct
Transmission (no relaying) [13]. To be able to better guide a packet to the
destination several routing protocols have been proposed that use historical
encounter data to decide how to forward a packet. Examples are Utilitybased Routing [46], MaxProp [3] and Context-aware routing (CAR) [30].
As for MANETs geographical routing can also be done in intermittently
connected networks if the nodes are aware of their geographical position.
Two examples of protocols that perform geographical routing in
intermittently connected MANETs are Disruption-tolerant geographic
routing for wireless ad hoc networks (DTGR) [27] and Motion vector (MoVe)
[26].
1.3 Problem Description
A challenging aspect in the study of routing algorithms is that the node
mobility pattern affects the routing performance [21][28][41][55]. This means
that a routing protocol should be tested in an environment that as close as
possible resembles the environment it will be deployed in. To verify that a
2
This assumes that the transfer rate using wireless transfers (wireless transfer rate * distance) is
much higher than the rate using node mobility (speed * message size).
5
routing protocol is suitable for general use it should be tested under several
reasonable, but characteristically different, environments.
As the main scenario under which to evaluate routing we have chosen a
reconnaissance mission in which a group of unmanned aerial vehicles
(UAVs) shall detect units on the ground by regularly scanning all parts of a
specified area. Since it is probable that the units on the ground do not want to
be detected by the UAVs there may not be any apparent pattern to when a
UAV scans a particular area. The same type of requirements can be found on
the searching behavior in the FOPEN (Foliage Penetration) scenario reported
in the work by Parunak et al. [37]. Since most mobility models used in
MANET research are either synthetic [4] or based on human mobility
[20][25][41][49] we have had to develop a mobility model for this scenario.
Depending on used node density and communication range the nodes
moving under our mobility model will form an opportunistic intermittently
connected network. The challenge is then to route messages in a reliable
manner while limiting the use of system resources, such as storage, power
and wireless bandwidth, in the realistic mobility scenarios envisioned. Since
UAVs are location aware due to navigational requirements this could be used
to perform geographical routing if the position of the destination is known.
To conserve bandwidth and to make it possible to use our routing algorithm
in energy-constrained systems we will explore the viability of beacon-less
geographical routing in opportunistic intermittently connected MANETs.
Beacons are regularly transmitted special messages that are used by many
routing algorithms to determine a node’s neighbors. The reason to evaluate
beacon-less routing is that beacons as commonly used by routing protocols
have the following problems [15]:
• They consume a lot of bandwidth
• The consume energy from nodes even if they are not performing any
routing.
• Beacon information may not accurately represent actual communication
possibilities due to node mobility since beacon reception and due to
fading.
6
1.4 Contributions
The main contributions in this thesis are twofold; the study of mobility
models and a proposed geographical routing algorithm for intermittently
connected MANETs.
A distributed pheromone mobility model for reconnaissance applications
To evaluate our suggested routing protocol we have used a military
reconnaissance scan scenario. The objective in the scenario is that a group of
UAVs shall cooperatively scan an area regularly to detect units on the
ground. Since it is probable that the units on the ground do not want to be
detected by the UAVs they should not move in a deterministic pattern.
To coordinate the UAVs we have designed a distributed pheromone mobility
model. By using pheromones and localized search the UAVs are guided to
areas not recently visited by other UAVs. When a UAV moves around it
places pheromones on the areas it has scanned. Since it is not possible to place
these pheromones in the environment as would have be done in a natural
system the UAV places them in a local pheromone map. To share this
pheromone information with the other UAVs each UAV regularly broadcasts
a local area pheromone map. All UAVs that receive the broadcast merge this
information into their pheromone map.
The distributed pheromone mobility results presented in this thesis extends
the results presented in the following paper:
Erik Kuiper, Simin Nadjm-Tehrani. Mobility Models for UAV Group
Reconnaissance Applications. Proceedings of International Conference on Wireless
and Mobile Communications. July 2006. IEEE
A beacon-less geographical routing protocol for intermittently connected
networks
Most routing protocols use beacons to know who their neighbors are. While it
is a quite simple and effective method it has the problem of creating a lot of
overhead, and the information gathered by beacons is always to some extent
out of date.
In this thesis we present location aware routing for delay-tolerant networks
(LAROD). LAROD forwards messages using greedy geographical routing
without the use of beacons and employs the store-carry-forward principle
when a message cannot be forwarded due to network partitions.
7
LAROD is previously presented in:
Erik Kuiper, Simin Nadjm-Tehrani, Geographical Routing in Intermittently
Connected Ad Hoc Networks. The First IEEE International Workshop on
Opportunistic Networking. March 2008. IEEE
1.5 Thesis Outline
This thesis is organized as follows. In Chapter 2 other work relating to
mobility models and routing in intermittently connected MANETs are
presented. In Chapter 3 our distributed pheromone model is described and
evaluated. In Chapter 4 LAROD is described and evaluated. Finally Chapter 5
presents our conclusions and ideas for future work.
8
9
2 Background
This chapter gives an overview of the current state regarding mobility models
for MANET research and routing in intermittently connected MANETs.
2.1 Mobility Models
A natural way to simulate wireless networks is to place all the nodes in a
Euclidian space and simulate the radio communication based on the nodes’
placement using a radio model. To control the placement and mobility of the
nodes a model or real-world mobility trace is used. The mobility models used
in ad hoc network research are usually synthetic constructs [4], but recently
some mobility models have been suggested that are based on data from
mobility traces [25][54]. The choice of mobility description is important in
MANET routing research since it has been shown that the mobility affect the
performance of routing protocols [21][28][32][41][55].
Even if a real-world trace has the actual movement of the nodes under study
the problem is that a trace only represents one possible movement pattern. To
be able to statistically verify a routing protocol more data is generally needed
than traces can give. To provide this a mobility model is needed that can
generate traces with the same properties as real collected traces would have.
Such a model can then generate as many traces as needed providing
statistical diversity while still maintaining realistic properties. Any mobility
model claiming to model real-world mobility should be verified against realworld traces as done by Kim et al. [25] and Zhang et al. [54]. Even though the
mobility models used by Marfia et al. [28] have not been validated against
real traces the routing results reported illustrate the impact small differences
in mobility can have on routing results.
Another aspect of mobility models is if they are intended to be descriptive or
prescriptive. A descriptive mobility model tries to describe how nodes move
in some kind of environment. A prescriptive mobility model on the other
hand describes how a node should move. The main difference between the
two types is how they are verified. A descriptive model needs to be verified
10
against the real mobility it tries to describe. A prescriptive model on the other
hand needs to be verified against what the nodes try to achieve with their
mobility. A good example of descriptive mobility models are the vehicle
models used by Marfia et al. in [28]. The pheromone models used by Sauter et
al. [42] are on the other hand prescriptive since they are used to control how
the nodes move to achieve a mission objective.
2.1.1 Synthetic Mobility Models
Since it is difficult, costly and not always possible to obtain real-world
mobility traces from which mobility models can be created researchers have
developed synthetic mobility models. These models range from the very
abstract random waypoint mobility model [22] to more realistic node
movement like the obstacle mobility model [21] and vehicular mobility [32].
Many of the used mobility models are entity mobility models which mean
that the nodes move independently. In reality the decision by a node of how
to move is often influenced by other nodes. This fact has made people design
mobility models like the reference point group mobility model [17] and
pheromone based models like the ones suggested by Sauter et al. [42].
A survey of different mobility models used in MANET research can be found
in [4]. In the following subsection some synthetic mobility models are
described that have been used in the evaluations or influenced the mobility
models used in this thesis.
2.1.1.1
Random waypoint
The most widely used mobility model is MANET research is the random
waypoint mobility model [22]. In random waypoint a node randomly selects
a destination and speed and then moves in a straight line to the selected
destination. When the destination is reached the node optionally pauses for
some random time until the process is restarted. The random values used are
normally drawn from a rectangular distribution.
The simplicity of the model and its widespread use means that it has
maintained its popularity, but there are problems with the model. Without
reflecting too much on the properties of the mobility model many researchers
initialize a simulation by distributing nodes randomly over the simulation
area using a rectangular distribution. The problem with this is that the
stationary distribution is not rectangular. In [33] Navidi and Camp showed
that the stationary distribution is actually according to equation (1) assuming
11
a rectangular simulation area of unit size, no pause times and rectangular
distributions in selecting speed and destination.
[
k (x 2 − x1 ) + ( y 2 − y1 )
g ( x) = 2∫ ∫ ∫ ∫
x 2 − x1
0 x 0 0
k ≈ 1.9179
x 1 1 1
]
2 1/ 2
2
dy1 dy 2 dx1dx2
(1)
The node speeds are not uniform either, but instead distributed according to
equation (2) with the same assumptions. The parameters of the equations are
defined in Table 1.
1


f ( s ) =  s log(v1 / v0 )

0
v0 < s < v1
otherwise
Table 1.
Parameter
x1, x2 ,y1 ,y2
k
s
v0
v1
(2)
Random waypoint parameters
Description
Path end points.
Constant to get a total density of 1.
Node speed.
Node minimum speed.
Node maximum speed.
These results mean that if a simulation is initialized by placing the nodes
using a rectangular distribution the statistical mobility properties will
continuously change until the steady state distribution is reached. This means
that simulation results obtained from the beginning of the simulation will be
different compared to results obtained late in a simulation. In [33] Navidi and
Camp also derived expressions for the speed and x- and y-coordinates with
pausing.
2.1.1.2
Gauss-Markov
Instead of determining the destination of a node you could regularly update
the direction in which the node is moving. The Gauss-Markov mobility model
[50][4] does this by updating the speed and direction of a node at fixed
intervals. Equations (3) and (4) describe the updates and the parameters are
defined in Table 2.
12
sn = αs n −1 + (1 − α )s +
d n = αd n −1 + (1 − α )d +
(1 − α )s
2
(3)
xn −1
(1 − α )d
2
Table 2.
(4)
x n−1
Gauss-Markov parameters.
Parameter
sn
Description
Speed at step n.
s
Average speed.
sx
Random variable from a Gaussian distribution.
dn
Direction at step n.
d
dx
Average direction.
α
Randomness factor. 0 ≤ α ≤ 1
Random variable from a Gaussian distribution.
To ensure that a node does not move outside the simulation area the average
direction is changed when the node approaches the edge according to Figure
1.
315º
270º
0º
45º
Figure 1.
225º
180º
90º
135º
Change of average direction near the edges.
13
2.1.1.3
Pheromone Based Mobility Models
Animals like ants use pheromones to guide them to the locations they need to
go to like food resources. The distributed nature of pheromone based systems
and the observation that complex behavior can emerge from the simple
control logic of the agents have made pheromone controlled mobility
interesting to study. The viability of the principle has been shown by
simulation and practical tests [12][37][42].
Sauter et al. [42] show by simulation that pheromone logic can be used for
several types of surveillance and target acquisition and tracking scenarios.
They have also shown by practical demonstration that the technique works in
practice. To guide the vehicles several types of pheromones are used, both
repulsive and attractive. Repulsive pheromones will make a vehicle avoid an
area where attractive pheromones will encourage vehicles to come to an area.
For the basic surveillance scenario two types of pheromones are used, one
repulsive and one attractive. In their scenario the area to be surveyed
generates attractive pheromones. When an area is visited the attractive
pheromones are removed and no new pheromones are generated for some set
time. To avoid that two vehicles try to survey the same area a vehicle places
repulsive pheromones in the next place it plans to move to. The pheromones
placed diffuse, that is slowly spread in the local environment. This creates
pheromone gradients that the vehicles use to guide their movement. There
are two main issues with their model. The first is that there seems to be a
global pheromone map that all agents can access. This might closely simulate
the real-life insect pheromone systems, but in a mechanical system where
pheromones need to be placed in a virtual map this means that there is a
central node managing the map. This design makes the system sensitive to
the failure of that node and all vehicles require good communication to this
node. Another issue is that they do not discuss how a vehicle determines
where to go. That it is based on the pheromone map is clear, but the areas
evaluated in order to select where to go are not described.
Parunak et al. [37] propose two approaches to perform target localization and
imaging. In the entity (individualistic) approach the UAVs use offline
determined paths to guide their movement. In the group (team) approach
visitation pheromones are used to deter UAVs from visiting areas recently
visited. To produce a distributed and robust solution each vehicle maintains
its own pheromone map. When a UAV passes through an area it updates its
internal map and broadcasts its position, which makes it possible for all
14
UAVs within communication range to update their maps. When a UAV shall
decide on its movement it randomly selects a location, where the probability
is inversely proportional to the distance to the location and the pheromone
concentration in the location. Unfortunately the paper does not provide any
evidence of the performance of the localization and imaging approaches,
which makes them difficult to evaluate.
Gaudiano et al. [12] test several control principles for an area-coverage
mission. From the tested approaches the pheromone one was the best. The
problem with their pheromone strategy is that is seems to rely on a global
pheromone map, giving the same problem as with the Sauter et al. solution.
Additionally, the pheromones do not fade with time (dissipate) in the simple
reconnaissance scenario, a property that they do use in a suppression mission
scenario also presented in the paper. In the suppression mission the UAVs
search for mobile targets and when found they try to destroy them.
2.1.2 Real-World Mobility Models
To better resemble real-world behavior, mobility models can be designed
based on observed real-world movement. Researchers have essentially used
three types of mobility information to create mobility models based on realworld data.
• Actual node movement
• Node connections
• Node connections to a base station
To be able to create a mobility model based on observed behavior the system
to be described must actually exist. If that is not the case then synthetic
modeling is the only option.
Due to the cost and difficulty of collecting traces the trace data will generally
not be enough to run the amount of simulations needed to get enough
confidence in the performance of tested routing protocols. For this reason it is
generally good to build a synthetic model based on trace data. The model can
then generate an infinite number of traces with the same statistical mobility
properties as the real-world nodes have.
15
2.1.2.1
Position Based Traces
The best traces are those that collect the actual node mobility. Unfortunately
these are very difficult and expensive to collect since a large number of nodes
need to be equipped with position tracing equipment. For this reason large
scale position based traces have not been collected by the research
community. In [41] Rhee et al. collected traces from in total 44 individuals at
five different sites. While this is a relatively small population they found that
all walks had statistical features similar to those of Levy walks [43].
Instead of actually collecting node movement Hsu et al. [19] have performed
surveys on the USC campus and have constructed a model mobility where
nodes move between popular locations. They found that people tend to
aggregate at popular locations and that ad hoc network connectivity between
these locations is poor due to the low concentration of nodes between the
popular locations.
2.1.2.2
Node Connection Based Traces
Instead of collecting node positions it is generally easier to collect node inter
contact times (ICTs). As with collecting position based traces all nodes need
to be equipped with measuring devices, but instead of measuring where a
node is the times at which the nodes are in communication range are
measured. From these traces it is generally not possible to create a mobility
model in the Euclidian space, but instead an inter contact model is created.
The limit of such a model is that radio interference is generally difficult to
represent in simulations using inter contact models.
Examples of collected ICT traces are the studies by Su et al. [49] and Hui et al.
[20][6]. Both groups recorded the ICTs of humans carrying specially prepared
Bluetooth devices. The traces were collected from ten to fifty persons. A
consequence of the small populations in the traces is that the routing options
are much more limited than if a larger population would have been used. Su
et al. performed some routing experiments on the collected traces. They got a
median latency of just under three days with a delivery ratio of 86% with
epidemic routing. For most practical applications these results are not good
enough, but the authors expect that the results would be vastly improved
with a larger population, that is a denser network.
Hui et al. found that the inter contact times exhibited a power law
distribution with a coefficient of less than one. Analyzing what a power law
distribution meant for routing they found that with a coefficient of less than
16
one all naive routing algorithms (including epidemic routing) had an infinite
expected delay. Since normally used mobility models like random waypoint
do not exhibit this type of ICTs there is a need to investigate routing
performance under this type of mobility.
At the University of Massachusetts, Amherst, a testbed composed of 30
busses has been constructed [3]. Each bus is equipped with a computer with
two IEEE 802.11b interfaces and a GPS receiver. From this testbed they have
collected actual contacts and transfer possibilities. This means that the traces
contain the actual amount of data that can be transferred at each contact. The
GPS traces collected contained several gaps where contact with the satellites
had been lost due to placement constraint of the GPS receiver. To be able to
use the GPS data the missing parts had to be reconstructed [2].
2.1.2.3
Base Station Based Traces
In networks with base stations the connection and disconnections of nodes to
the base stations can be measured. The advantage compared to the two
previously presented methods is that the nodes do not need any
instrumentation and the connection information is normally collected anyway
by the base stations. The disadvantage is that only approximate node location
and node inter contact information is available. Two publicly available data
sets from Wi-Fi base stations are from UCSD [29] and Dartmouth College
[16].
In [44] Song et al. used the Dartmouth traces to create a connection trace with
the assumption that all nodes connected to a base station can communicate
with each other, but with no other nodes. This is a very rough model since it
does not take interference into account and it makes very simplifying
assumption regarding the nodes that can communicate with each other. Two
nodes connected to the same base station might not be able to communicate if
they are located at opposite ends and two nodes connected to different base
stations should be able to communicate if the nodes are located close to each
other.
If the locations of the base stations are known and if some node movement
properties are known then a mobility model from the base station traces can
be created. In [25] Kim et al. have used traces from Wi-Fi phone users at the
Dartmouth College to create a mobility model for these users. Combining
syslog data from the base stations and with the knowledge of the locations of
the base stations they created a mobility model for Wi-Fi phone users. The
17
model was validated against walks from users holding both a phone and a
GPS receiver.
2.2 Routing
Routing in connected mobile ad hoc networks has been studied extensively
and routing protocols like AODV [38], DSR [23] and GPSR [24] have been
suggested. All these protocols assume the existence of a contemporaneous
path between sender and receiver. In networks without contemporaneous
paths, but where node mobility can overcome partitions, a different type of
routing algorithm is required.
In RFC 4838 [5] Cerf et al. describe an architecture for delay-tolerant and
intermittently connected networks (DTNs). Their architecture is designed for
heterogeneous networks that are subject to long delays and/or discontinuous
end-to-end connectivity. The architecture is based on asynchronous
messaging and uses postal mail as a model of service classes and delivery
semantics. The architecture makes the following three assumptions:
• That storage is available and well distributed throughout the network.
• That storage is sufficiently persistent and robust to store data until
forwarding can occur.
• That the “store-and-forward” model is a better choice than attempting to
effect continuous connectivity or other alternatives.
Due to the long delays and disconnections in DTNs end-to-end reliability
methods like acknowledgements and timed out retransmissions are not
suitable for DTNs. To be able to offer reliable transfers in DTNs RFC 4838
provide custody transfer. In custody transfer a message is moved between
custodians that take responsibility for reliable delivery of the message. In
essence the network guarantees that a message is not lost.
The mobility of the nodes does mean that the network topology will
constantly change and that nodes constantly come in contact with new nodes
and leave the communication range of others. In RFC 4838 Cerf et al. classify
the contacts based on their predictability into scheduled, predicted and
opportunistic contacts. With scheduled contacts the nodes know when they
will be able to communicate with a specific peer. If nodes can estimate likely
meeting times or meeting frequencies you have a network with predicted
contacts. If no information is available on node contacts then the contacts are
18
opportunistic. In this thesis we will study routing in DTNs with opportunistic
contacts.
An overview of different routing strategies in delay-tolerant networks can be
found in Zhang’s survey [53].
2.2.1 DTN Routing in Opportunistic Networks
Routing in DTNs with opportunistic contacts is challenging since contact
times and durations are not known in advance. The challenge for the routing
protocol is to determine if a packet shall be handed over to a peer or not
when they meet. Factors that influence this decision are probability that the
peer can move the packet closer to the destination, available buffer spaces in
the two nodes and relative priority to forward this packet compared to other
packets the node holds. If nodes are location aware then the relative position
and direction of the nodes can be used to influence the forwarding decision.
Three examples of location unaware routing protocols for this environment
are Randomized Routing [46], Epidemic Routing [51] and Spray and Wait
[47].
In Randomized Routing only a single copy of a packet is present in the
network. When two nodes meet a packet is handed over to the other node at
some set probability. This means that a packet randomly walks around in the
network until it reaches the destination. This routing principle is better than
keeping a packet at the source node until it comes in contact with the
destination provided that the transmission speed is faster than the mode
movement or if node movements are local.
In Epidemic Routing (ER) all packets are distributed to all nodes in the
network (or at least a considerably large subset of nodes) giving a high cost in
both transfer and storage overhead. When two nodes meet they exchange
information on the messages stored in the nodes. Each node then decides on
the messages it wants to receive and request these from the other node. If a
node’s buffer space becomes full it drops the oldest messages first to make
place for new messages. A major problem with ER is that some messages
might not be transmitted in an overload situation since there is no
prioritization regarding transmission or drop order. Due to the epidemic
spread of messages in ER the network will be overloaded even at relatively
low transmission rates. To better handle transmission in an overload situation
Ramanathan et al. have proposed prioritized epidemic routing (PREP) [39].
The addition PREP does to ER is that it prioritizes packets when it comes to
19
transmission and deletion. By this it ensures that the packet that has the most
to gain on being transferred gets transmitted first and when a packet needs to
be dropped the packet expected to suffer the least from being removed is
dropped first. By these simple mechanisms PREP manages a good delivery
ratio even when the network is overloaded.
In Spray and Wait a packet is distributed to a limited number of nodes who
hold on to the packet until they meet the destination. The recommended
initial distribution method is to use binary spraying. When a node with more
than one copy of the packet meets a node that has not seen the packet then
half of the packets are handed over to the new node. With Spray and Wait a
destination close to the source will probably receive the packet during the
spraying phase. Destinations further away will have to wait until node
mobility moves a node that stores the packet within communication distance
to the destination. A strength of Spray and Wait is that the transmission
overhead of each generated packet is bounded. Spray and Wait can be an
efficient protocol if the nodes that carry the packet cover a large part of the
network with their mobility. To improve Spray and Wait Spyropoulos et al.
[48] have suggested to only spray to nodes that are more likely to encounter
the destination. Each node has then a utility value and only nodes with a
good enough utility value will be selected for spraying.
If the nodes are location aware and the (approximate) location of the
destination is known then the packets can be forwarded by geographic
routing. Li et al. [27] have modified GPSR [24] to better handle temporary
disruptions in relatively sparse networks (55 nodes/km² compared to our
even sparser scenario that has 10-30 nodes/km²). By using temporary storage
(up to 2 seconds) and having a set of possibly reachable neighbors they
substantially increased the delivery ratio compared to GPSR. Their approach
is geared towards handling short temporary disruptions due to obstructions,
node mobility or interference, and not intended to handle substantial
disconnections.
LeBrun et al. [26] have performed geographical routing in a very sparse (0.34.4 nodes/km²) delay-tolerant network with a stationary destination. In their
motion vector (MoVe) routing algorithm a message is handed over to a peer
if, given their current directions, the peer is expected to come closer to the
destination than the holder of the packet. To limit the overhead MoVe uses a
request-response mechanism. This means that only nodes holding a message
transmit HELLO messages. When another node hears a HELLO message it
20
responds with a RESPONSE message. When a link is established using this
exchange the nodes start to exchange information to determine if the message
shall be handed over or not.
2.2.2 Beacons-less Routing
Most routing protocols require knowledge of a node’s neighbors to make
their routing decisions. This information is generally gathered by the use of
beacons, messages broadcasted regularly that will be heard by all nodes
within communication distance. Knowledge of your neighbors makes more
informed routing decisions possible, but beacons have their drawbacks. In
[15] Heissenbüttel et al. describe the problems with beacons and present
some remedies. The main problems with beacons are:
• Energy is consumed to transmit, receive and process the beacons.
• The beacons interfere with data transmissions.
• Neighbor information can be inaccurate due to node mobility.
The main problem with inaccurate neighbor information is that transmissions
are attempted to nodes that have moved out of range. These transmissions
will cost a lot of energy and bandwidth. Given these problems with beacons
alternatives to beaconing should be evaluated to see if better solutions can be
found.
There have been several suggestions for beacon-less routing protocols:
• Beacon-less routing (BLR) [14]
• Implicit geographical forwarding (IGF) [1]
• Geographic random forwarding (GeRaF) [57][58]
• Contention-based forwarding (CBF) [11]
• Priority-based stateless geographical routing (PSGR) [52]
• Guaranteed delivery beacon-less forwarding (GDBF) [7].
They all do geographical routing which means that the nodes have to be
location aware and to select the forwarding node they use broadcasts and
timers. Instead of selecting the forwarder from a list of neighbors and sending
the data packet to the selected node, as done by most geographical routing
protocols, they broadcast the data packet or a ready/request to send (RTS) to
all neighbor nodes. All nodes in a defined forwarding area are eligible
forwarders and set timers based on how good they are as forwarders where
the best forwarder gets the shortest time. When a timer expires a node either
21
broadcasts the data packet or a clear to send (CTS). The eligible forwarders
that overhear such a transmission generally abort their timer.
The protocols use one of two transfer principles. They either use a RTS/CTS
exchange followed by an acknowledged point-to-point data message transfer
(IGF, PSGR, GDBF) or the data message is broadcasted and successful
transfer is acknowledged upon previous holder overhearing the forwarder
rebroadcast the message (BLR, CBF). GeRaF does not model on the
transmission layer and can use both principles. The rationale for choosing
either method is not discussed in any of the papers. An argument for using
the RTS/CTS is that the RTS and CTS messages are relatively short and it
makes it possible to transmit the (long) data message using a point-to-point
transfer with reliability mechanisms such as acknowledgements and
resending. An argument for directly sending the data message is that the
RTS/CTS sequence consumes relatively much bandwidth compared to the
data packet due to message spacing times of the MAC protocol. We hope to
be able to investigate this tradeoff in the future under realistic transmission
models where interference and transmission errors are well modeled.
The forwarding area used is often of limited size so that all nodes in the area
can hear the transmissions of all other nodes in the area assuming a constant
radio range. Commonly used shapes of the forwarding area are a 60º circle
sector, a Reuleaux triangle or a circle (see Figure 2a-c). The longest distance
for all the shapes is normally the assumed communication distance. BLR, IGF
and CBF use these types of forwarding areas.
Holder
Holder
Sector
(a)
Holder
Reuleaux
(b)
Figure 2.
Holder
Circle
(c)
Progress
(d)
Forwarding areas.
In GeRaF, PSGR and GDBF all nodes that provide progress are eligible
forwarders (see Figure 2d). The fact that overhearing between all nodes is not
possible is treated differently by the protocols. GeRaF has not dealt with the
issue since it is only simulated using a high level simulator. GDBF assumes
that overhearing the CTS sent by the forwarder and data packet sent by the
holder is enough. PSGR treats collisions between CTS packets in great detail
and tries to ensure that no collisions between CTS packets occur.
22
The different protocols use different criteria for the characteristics of a good
forwarding node. CBF, GeRaF, PSGR and GDBF all prioritize long steps, that
is the forwarder should be as close to the destination as possible. BLR on the
other hand prioritizes short steps. The reason for this is that BLR alternates
between finding a path (and transmitting the first packet) using a geographic
beacon-less strategy and sending packets through the found path using pointto-point transfers. If the nodes can adjust their transmission power to the
minimum required to make a reliable transfer then short hops consume less
system bandwidth than long hops. IGF considers both the power available in
the nodes and the progress made. With equal energy nodes closer to the
destination are selected, but as energy is depleted the timer is increased
which means that nodes with low energy are less likely to be selected as
forwarders.
23
3 Reconnaissance
Mobility
Since the performance of routing algorithms will change depending on the
scenario and scenario parameters [21][28][55] it is important to carefully select
a mobility model that represents the environment a routing protocol is
intended to work in. We have chosen to create a mobility model that could
represent how UAVs move when performing reconnaissance of an area.
3.1 Scenario
The main scenario used to evaluate the suggested routing protocols is a
military reconnaissance scan scenario. The objective is to scan an area
regularly using multiple UAVs. Since it is probable that the units on the
ground do not want to be detected by the UAVs there may not be any
apparent pattern to when a UAV will scan a particular area. The same type of
requirements can be found on the searching behavior in the FOPEN (Foliage
Penetration) scenario reported in the work by Parunak et al. [37].
To collect the reconnaissance data the UAVs have a camera directed
downwards covering a rectangular image centered at the UAV. The images
captured are then processed by the UAV. If something of interest is detected
then this information needs to be sent to a unit that can act on the
information. For the routing simulations in chapter 4 we have used four
stationary receivers, but other configurations are conceivable including
mobile receivers.
A fixed wing aircraft is limited in its movement in that it has a minimum and
maximum air speed and that an instantaneous change of direction is not
possible. As we are mainly interested in the behavior of the system of UAVs a
coarse description of the movements of the individual UAVs (as opposed to a
detailed kinematic model) has been used. The UAVs’ movements are
described using a 2D model with fixed speed, constant radius turns, and no
collisions. The reason to use a 2D model is that all UAVs are flying at about
24
the same altitude and there is no need to model start and landing. A fixed
speed is relatively realistic in a reconnaissance scenario. There should be a
speed drop during turns, but the benefit of modeling that is expected to be
minor. The reason to use constant radius turns is that it is much easier to
model, and a more realistic progressive turn model is not expected to add
any major value to the simulation. The reason that collisions do not have to be
modeled is that it is assumed that the UAVs can make altitude adjustments to
avoid collisions. For the scenario we envision the real-world parameters
according to Table 3. The parameters are based on reasonable assumptions
made by domain experts.
Table 3.
Radio range
UAV flight speed
UAV flight altitude
UAV turn radius
Camera coverage area
Scenario parameters
8000 m
150 km/h (81.0 knots)
3500 m (11 000 feet)
500 m
2000x1000 m
3.2 Random Mobility Model
As a comparative baseline for the main mobility model described in the next
section we have created a simple random mobility model. The random model
is a Markov process [36] where the UAVs regularly decide whether to go
straight ahead, turn right or turn left. For our simulations this decision is
taken every other second with the probabilities given in Table 4. If a UAV
moves closer than the turn radius to an edge then it turns towards the centre
of the search area until it has reached a randomly chosen direction -45° to 45°
related to the normal of the edge of the search area. Compared to the GaussMarkov model in [50][4] this model has no mean direction and the directional
change is given as three discrete values, not a continuous distribution.
Table 4.
Last action
Straight ahead
Turn left
Turn right
Random action table.
Probability of action
Turn left
Straight
Turn right
ahead
10%
80%
10%
70%
30%
0%
0%
30%
70%
25
3.3 Distributed Pheromone Repel Mobility
Model
To produce a mobility control algorithm that is robust and random we have
designed a distributed pheromone repel model. By using pheromones and
localized search the UAVs are guided to areas not recently visited by other
UAVs.
When a UAV moves around it places pheromones on the areas it has scanned
with its camera. Since it is not possible to place these pheromones in the
environment as would be done in a natural system the UAV places them in a
local pheromone map. The pheromone map is a grid where each element
contains a timestamp representing the last time the element was scanned.
Since timestamps are used pheromones placed will slowly fade away. To
share this pheromone information with the other UAVs each UAV regularly
broadcasts a local area pheromone map. All UAVs that receive the broadcast
merge this information into their pheromone map. The broadcast frequency
and size of the map broadcasted needs to be adjusted to limit the bandwidth
required for the transfer of the pheromone information. The actual
parameters used can be found in Table 5.
Table 5.
Pheromone map parameters.
Grid element size
Transfer map size
Transfer interval
100 m
5000x5000 m
10 seconds
Figure 3 to Figure 6 illustrate the difference between the local pheromone
map held in a UAV and the total pheromone data present in the system. In
the figures black represents fresh pheromones and white represents no
pheromone information or pheromones older than the time out of one hour.
Also drawn on the maps is the path of the UAVs whose local pheromone map
is shown. The pheromone maps are taken from simulations where the
probability of a successful transfer of pheromone data was set to 50%.
As we will show in the evaluations in section 3.4 there is no real benefit for a
UAV to have access to the global pheromone map. The important thing is to
have a reasonably accurate pheromone map in the UAVs vicinity.
26
Figure 3.
Figure 4.
Local pheromone map after 3600 seconds of simulation.
Global pheromone view after 3600 seconds of simulation.
27
Figure 5.
Figure 6.
Local pheromone map after 7200 seconds of simulation.
Global pheromone view after 7200 seconds of simulation.
28
As with the random model a UAV decides to turn left or right or go straight
ahead every other second. But instead of making this decision with fixed
probabilities, the probabilities are based on the pheromone smell in three
evaluation areas. Each area is a circle and they are placed as shown in Figure
7. To get the pheromone smell from the time stamps stored in the pheromone
map the times are scaled so that the current time gives maximum intensity
and the smell is then linearly reduced to zero at the fade away time. The
computation is done according to equation (5) with parameters as defined in
Table 6. The smell zero at time zero is needed to handle elements that have
never been scanned since the elements in the pheromone map are initialized
to zero.
2000
Left
Center
Right
1500
1000
500
Scan area
UAV
0
−500
−1000
Figure 7.
Table 6.
Parameter
sarea
stotal
selement
telement
t
dtime_out
−500
0
500
1000
Pheromone search pattern.
Pheromone parameter definition.
Description
Total smell in an area (left, center, right)
sleft + scenter + sright
Smell in a pheromone map element
Timestamp in a pheromone map element
Current time
Pheromone fade away time
sarea = ∑ selement
area
selement
0

= 0
t
 element − t + d time _ out
t element = 0
t element ≤ t − d time _ out
otherwise
(5)
29
Since a UAV should go to places not recently visited it should prefer areas
with a low pheromone smell. For that reason the probability of action is
defined as specified in Table 7. If no pheromone smell is reported for any
direction then a random direction is chosen as in the random model. If the
center and either the left or right has no smell then a random direction is
chosen between these two. The area outside the search area is given a high
pheromone smell (higher than the ordinary full intensity) for the UAVs to
avoid it. A special rule has been added to handle the case when a UAV flies
directly into a corner of the search area. If only guided by the pheromones
then a UAV flying into a corner would get very high smells in the left and
right areas and a low smell in the center area. This would mean that the UAV
would be guided straight into the corner. To counter this problem a UAV
turns right if both the right and left areas have a smell intensity that indicate
that parts of the evaluation area is outside the search area.
Table 7.
Turn left
(stotal – sleft) /
(2 * stotal)
UAV pheromone action table.
Probability of action
Straight ahead
(stotal – scenter) /
(2 * stotal)
Turn right
(stotal – sright) /
(2 * stotal)
3.4 Evaluation
As described in section 3.1 the main objective of the reconnaissance scenario
is to scan all parts of an area regularly. If the area is large and the requirement
of how often each part of the area shall be scanned is low the several UAVs
have to cooperate to perform the scanning. For the evaluations we have set
the requirement that each part of the reconnaissance area should be scanned
at least once every hour. To reflect this the pheromone fade time was set to
one hour for the pheromone mobility model.
The area over which reconnaissance should be performed was set to a 90x90
km square and 90 UAVs were used. Initially all UAVs started from the center
of the south edge moving north. This start will challenge the mobility model
to get the UAVs to spread out over the entire reconnaissance area.
In addition to the two mobility models presented in sections 3.2 and 3.3 the
scenario was also run with the random waypoint mobility model with no
wait times. The reason to include random waypoint is that it is the most
commonly used mobility model in ad-hoc networking research. The mobility
30
models were tested by performing 50 independent runs per model where
each run simulates 3 hours.
To evaluate the robustness of the pheromone logic the distributed pheromone
mobility model was tested with several data transfer probabilities and
compared to an ideal case where a global pheromone map was accessible to
all UAVs. The transfer probabilities used were 100%, 50%, 10% and 0%. This
simulates a range of cases from perfect transmission capability (100%) to the
absence of radio communication (0%). A transfer probability of 0% will mean
that a UAV is only guided by its own pheromones.
To evaluate the main scanning objective we have looked at the scan coverage,
that is the percentage of the area scanned the last hour. A secondary
requirement was to scan in an unpredictable pattern. To evaluate this
property we have studied the probability distribution of the time between
scans. Finally we also looked at the wireless connectivity to determine the
viability for ad hoc routing in the evaluated setting.
3.4.1 Scan Coverage
Initially the UAVs shall scan the area as fast as possible. When the initial scan
is completed the UAVs need to continuously monitor the area by rescanning
every part at least once per hour. The coverage data from the different runs
are presented in Figure 8 to Figure 14. The figures show the average coverage
from the 50 runs and the 95% confidence interval. In Figure 15 the averages
from some of the runs are collected for easier comparison.
The absolute maximum scan speed is 0.083 km²/second/UAV according to
equation (6) and the data from section 3.1. Given the area of 8100 km² and 90
UAVs the fastest time to cover the whole area (which is in practice
impossible) is 18 minutes (1056 seconds). Adding the overhead of turning and
additional requirements like randomness a coverage time of 40 minutes (2400
seconds) should be feasible. Extrapolating the steepest part of the coverage
curve of the pheromone and random waypoint mobility models the coverage
time is a little more than 40 minutes.
Scan speed = UAV speed * scan area width
(6)
Comparing Figure 8 and Figure 9 we see that using a global pheromone map
does not give any better results than using a distributed pheromone map.
This means that the UAVs manage to distribute the local information needed
for the mobility decisions. Looking at Figure 10 we see that if only 50% of the
31
transmitted pheromone maps are received then the UAVs still have enough
information to efficiently scan the area. When the transfer probability drops
to 10%, Figure 11, then it takes substantially more time to reach a steady state
and a slightly lower steady state coverage is achieved. But considering the
large loss of information the result is still good.
In Figure 13 we see the problem with not having pheromones that can guide
the nodes to previously uncovered areas. With the random mobility model it
takes much time for the UAVs to become evenly spread out over the area. In
simulations with a smaller area, but with the same node density the random
mobility model achieved a steady state coverage of about 90±8% with a 95%
confidence interval. Adding only local pheromone information as reported in
Figure 12 the coverage improves, but not enough to provide acceptable
results.
In Figure 14 the properties of the random waypoint mobility model becomes
relatively clear. The initial coverage rate is good since the nodes move out
from the start position to different points in the area. The reason that the
coverage stabilizes around 84% is due to the steady state distribution of the
nodes. Since more nodes are present in the central parts of the reconnaissance
area than at the edges the areas close to the edges do not get scanned
regularly enough.
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 8.
Pheromone mobility coverage with global pheromone map.
32
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 9.
Pheromone mobility coverage with 100% transfer probability.
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 10.
Pheromone mobility coverage with 50% transfer probability.
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 11.
Pheromone mobility coverage with 10% transfer probability.
33
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 12.
Pheromone mobility coverage with 0% transfer probability.
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 13.
Random mobility coverage
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 14.
Random Waypoint mobility coverage
34
1
0.9
0.8
Coverage
0.7
0.6
0.5
0.4
0.3
0.2
Pheromone 100%
Pheromone 10%
Pheromone 0%
Random Waypoint
0.1
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 15.
Comparison of average coverage.
3.4.2 Scan Characteristic
The random and pheromone mobility models have been designed to produce
unpredictable scanning patterns. The randomness of the scanning can be
investigated by looking at the probability distribution of the time between
scans. In Figure 16 to Figure 22 the average probability distributions and the
95% confidence interval of the three models are shown. The area under the
curve between two time points is the probability that the next scan will occur
during this time period after the current scan.
The question is then; what is the desired distribution? To this question there
is no definite answer, but a uniform distribution (the horizontal dashed line
from 0 to 2160 seconds) should be an attractive result. This would mean that
the probability of the next scan is evenly distributed over some time period.
The only firm requirement on the distribution function is that it shall be zero
after one hour to meet the one hour rescan requirement. What is very obvious
from these graphs is that as long as the nodes can exchange some pheromone
information the pheromone model manages quite well to avoid rescanning a
recently scanned area (does not peak for low time between scans). As we saw
in the scan coverage graph no model manages to achieve 100% coverage. This
is here seen by that the function is not zero after one hour.
The limitation of the probability distribution graphs is that they do not
include the areas never scanned or only scanned once. To see the capability of
the models to scan the complete area at least once during the three hours the
maximum, median and minimum uncovered area for the 50 runs are shown
in Table 8. These numbers clearly show the ability of the pheromone model to
35
cover the complete area. The concentration of the nodes to the central parts of
the area by the random waypoint mobility model is exhibited by the
relatively large values for the never scanned area.
Table 8.
Never scanned area
Max
0.04%
0.07%
0.09%
3.66%
13.52%
29.76%
6.79%
Pheromone global
Pheromone 100%
Pheromone 50%
Pheromone 10%
Pheromone 0%
Random
Random Waypoint
Median
0.01%
0.01%
0.01%
0.18%
4.73%
20.50%
5.20%
Min
0.00%
0.00%
0.00%
0.02%
1.93%
13.21%
3.80%
−4
Probability density
15
x 10
10
5
0
500
0
1000
1500
2000
2500
3000
3500
4000
4500
5000
Time until next scan (seconds)
Figure 16.
Pheromone mobility with global pheromone map.
−4
Probability density
15
x 10
10
5
0
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Time until next scan (seconds)
Figure 17.
Pheromone mobility with 100% transfer probability.
36
−4
Probability density
15
x 10
10
5
0
500
0
1000
1500
2000
2500
3000
3500
4000
4500
5000
Time until next scan (seconds)
Figure 18.
Pheromone mobility with 50% transfer probability.
−4
Probability density
15
x 10
10
5
0
500
0
1000
1500
2000
2500
3000
3500
4000
4500
5000
Time until next scan (seconds)
Figure 19.
Pheromone mobility with 10% transfer probability.
−4
Probability density
15
x 10
10
5
0
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Time until next scan (seconds)
Figure 20.
Pheromone mobility with 0% transfer probability.
37
−4
Probability density
15
x 10
10
5
0
500
0
1000
1500
2000
2500
3000
3500
4000
4500
5000
4500
5000
Time until next scan (seconds)
Figure 21.
Random mobility.
−4
Probability density
15
x 10
10
5
0
0
500
1000
1500
2000
2500
3000
3500
4000
Time until next scan (seconds)
Figure 22.
Random Waypoint mobility.
3.4.3 Communication
Reconnaissance data has no value if it cannot be transmitted to where it is
needed and nodes can only transmit data between each other if they are
within radio range. With the used node density of 0.011 nodes/km²
communication would be impossible if the nodes were evenly distributed in a
regular grid since they then would have a distance of about 9.5 km to their
closest neighbor which is larger than the radio range of 8 km.
In Figure 23 to Figure 29 the average number of partitions and 95%
confidence interval for the three mobility models are illustrated. A partition
consists of the UAVs that can pair-wise establish a contemporaneous path
with each other, either directly or via peers.
38
In Figure 23 to Figure 26 we see that the pheromone mobility manages to
spread the nodes well since we have a high number of partitions. With the
low (10%) transfer probability it just takes some more time to reach the
spread. In Figure 28 we again observe that the UAVs moving under the
random mobility model have not yet reached a steady state. The same
conclusion is also valid for nodes moving under the pheromone mobility
model but where no pheromone data is exchanged between the nodes (see
Figure 27). For the random waypoint mobility model the increased density of
nodes in the central parts of the simulation area leads to a lower number of
partitions compared to the pheromone mobility model as shown in Figure 29.
With an average of about 30 partitions for configurations with good coverage
the existence of a contemporaneous path between two random nodes is not
likely. To be able to send the information to any selected peer delay-tolerant
routing principles need to be used. This is the topic of the next chapter where
delay-tolerant routing on nodes that move under the pheromone mobility
model is further studied.
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 23.
Pheromone mobility with global pheromone map.
39
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 24.
Pheromone mobility with 100% transfer probability.
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 25.
Pheromone mobility with 50% transfer probability.
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 26.
Pheromone mobility with 10% transfer probability.
40
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (seconds)
Figure 27.
Pheromone mobility with 0% transfer probability.
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
9000
10000
Time (seconds)
Figure 28.
Random mobility.
50
45
40
Partitions
35
30
25
20
15
10
5
0
0
1000
2000
3000
4000
5000
6000
7000
8000
Time (seconds)
Figure 29.
Random Waypoint mobility.
41
4 Routing in DTNs
Routing in opportunistic DTNs is challenging since it is generally not possible
to establish a contemporaneous path between source and destination. Using
the store-carry-forward principle it is possible to transfer messages between
nodes by exploiting node mobility. The main difficulty is then to decide when
and to whom to forward a message that a node is carrying.
In this chapter we describe and evaluate our proposed routing algorithm
LAROD (location aware routing for opportunistic delay-tolerant networks).
LAROD is evaluated against two other routing protocols described in
sections 4.2 and 4.3.
4.1 LAROD
LAROD is a geographical routing protocol for DTNs that combines the
geographical beacon-less routing with the store-carry-forward principle. In its
essence LAROD uses greedy packet forwarding when possible. When greedy
forwarding is not possible the node holding the packet (the custodian) waits
until node mobility makes it possible to resume greedy forwarding.
To reduce system wide overhead LAROD uses the same basic beacon-less
routing strategy as BLR [14] and CBF [11] (see section 2.2.2). Instead of
forwarding a packet to a neighbor based on location data received from
beacons a custodian simply broadcasts a message when it wants to transmit
it. The “best” forwarding node receiving the message then forwards the
message in the same manner. The custodian that sent the message will
overhear this transmission and conclude that the forwarder has taken over
custody of the packet. If no such transmission is heard the node regularly
broadcasts the message until a forwarder becomes available due to node
mobility.
42
Forwarding area
Circle
Custodian
Destination
(a)
Figure 30.
Forwarding area
Progress
Custodian
Destination
(b)
LAROD forwarding areas.
To select the “best” node to forward a message among all nodes receiving it a
forwarding area and timer delay function is used. The nodes that are eligible
to forward a packet are determined by a forwarding area related to the node
performing the broadcast. In [14] Heissenbüttel et al. recommended a circle as
the best forwarding area (see Figure 30a). Our simulations have shown that
this area is too small due to the low density of nodes we use. Instead all
nodes that provide some minimum progress (dprogress) towards the destination
are eligible as forwarders (see Figure 30b). An implication of using this larger
forwarding area is that multiple copies of a packet can be active since all
nodes in the forwarding area might not hear the broadcast made by the best
forwarder. This should not be seen as a problem, since it enables exploration
of multiple paths to the destination.
All nodes receiving the packet in the forwarding area are tentative
forwarders and to select the best forwarder they all set a delay timer when to
rebroadcast the packet. The node with the timer that expires first will
rebroadcast the packet. This broadcast will be heard by the old custodian and
most of the other tentative forwarders. Overhearing the transmission they
will relinquish custody of the packet. Since the forwarding area chosen is
larger than the transmission range it is possible that several nodes take over
custody of the packet.
The delay function that computes the actual delay (tdelay) is defined in equation
(7) with the equation parameters defined in 0. The vectors and distances used
in the equation are illustrated in Figure 31. Depending on the relative position
of the receiver, custodian and destination the delay is computed based on one
of three cases. The delay for all three cases has a linear component and a
random component. When the custodian is so close to the destination that the
destination should have received the packet all tentative forwarders calculate
the linear delay based on the distance between the tentative forwarder and
the destination (first row in equation (7)). In all other cases the delay is based
on the distance from the custodian along the line connecting the custodian
43
and destination. Nodes not on the line get their distance by perpendicularly
projecting their position on to the line. Nodes with a computed distance of
less than dzero have a linear component with a maximum delay (tlmax) at the
custodian and zero delay at dzero (last row in equation (7)). The dzero distance
should be set close to the expected radio range. For nodes with a distance of
more than dzero the linear component is zero (line two in equation (7)). The
reason to have this case is that due to radio propagation factors nodes further
away than the expected radio range can receive a packet. To prevent
simultaneous transmission from nodes whose linear delay is zero all cases
add a small random delay (0 to trmax) to the computed linear delay. trmax should
be set much smaller than tlmax to make the impact of the random factor small
on the linear factor. To be able to calculate the delays all LAROD data packets
contain the position of the source, destination and last forwarder (custodian).
For BLR Heissenbüttel et al. recommended the inverse function, that is short
steps. This was done to be able to transmit at low power in the unicast phase
to increase total system bandwidth. Since there is no unicast phase in LAROD
it exploits the benefits of long steps.
In the case that the custodian does not hear a rebroadcast it will perform a
new broadcast after some time (trebroadcast). To stop transmission when a packet
has reached its destination the destination broadcasts an acknowledgement
packet. This packet is rebroadcasted by all custodians and tentative
custodians hearing it will stop their retransmissions. All nodes hearing an
acknowledgement packet will store the packet until the packet times out (tTTL).
If a node receives a packet for which it previously has received an
acknowledgement then it broadcasts an acknowledgement to stop the
transmission of the packet.
To prevent that a packet indefinitely tries to find a path to its destination all
packets have a time to live (TTL) expressed as a duration (tTTL). When the TTL
expires a packet is deleted by its custodian. For a full description of the
routing protocol see Figure 32.
LAROD is based on the principle that the custody of a packet is moved to the
most recent node that accepted the packet. This means that the protocol is not
robust to node loss. If a node fails for some reason then all packets that the
node holds will be lost unless they happened to be duplicated due to
diverging paths.
44
Table 9.
LAROD parameter definitions.
Parameter
tdelay
Description
Delay until node shall broadcast received message.
tlmax
Maximum linear delay.
trmax
Maximum random delay.
tTTL
Delay until node shall rebroadcast a message for which
it has not overheard a transmission by a forwarder.
Maximum time a packet is permitted to live.
dzero
Distance from custodian to have zero linear delay.
dprogress
r
n
r
d
r
r
Minimum progress required to be an eligible forwarder.
X
Uniform random variable in range [0, 1].
trebroadcast
t delay
Vector from sender to potential custodian.
Vector from sender to destination.
Vector from potential custodian to destination.
 r
 r ⋅t
+ Χ ⋅ t rmax
 d zero lmax

= Χ ⋅ t rmax
r

r
 d zero − nprojd
⋅ t lmax + Χ ⋅ t rmax

d zero

r
d ≤ d zero
r
r
n projd ≥ d zero
(7)
otherwise
Receiver
→
n
→
r
Custodian
Destination
→
→
n proj d
→
d
dprogress
dzero
Figure 31.
Illustration of vectors used for delay time computations.
45
Source node at data packet generation
Broadcast data packet
Set up timer for rebroadcasting packet to trebroadcast
Destination node at data packet reception
The packet is received for the first time
Deliver data packet to application
Broadcast ack packet
A duplicate data packet is received
Broadcast ack packet
All intermediate (non-destination) nodes at data packet
reception
If an ack has been received for the packet
Broadcast ack packet
Else if the node is in the forwarding area
If the node does not have an active3 copy of the packet
Set up timer for rebroadcast to tdelay
If the node has an active copy of the packet
Do nothing
Else
Remove active copy if it has one
At ack packet reception
If the node has an active copy of the packet
Remove active copy
Broadcast ack packet
Else
Do nothing
When a data packet rebroadcasting timer expires
If the packet’s TTL has expired (tTTL)
Remove packet
Else
Broadcast data packet
Set up timer for rebroadcasting the packet to trebroadcast
Figure 32.
3
LAROD pseudo code.
A node has an active copy of a packet if it has a copy of the packet waiting on a timer to be
rebroadcasted.
46
4.2 Broadcast DelayDelay-tolerant Routing
(BDTR)
To be able to estimate the delivery rate of a delay-tolerant routing protocol
which searches all possible paths to a destination we propose BDTR. BDTR is
a flooding based routing protocol that limits the flooding to an area centered
round the source and destination. In contrast to epidemic routing [51] it does
not use beacons to find its neighbors. Instead it uses the same principle as
LAROD does, when it has something to send is simply broadcasts the
message. All nodes within the flooding area that receive the message will
rebroadcast it after a short random delay. By this mechanism all nodes in the
partition of the source node should quickly receive a copy of the message and
if there is a contemporaneous path to the destination in the broadcast area the
packet will soon reach the destination. To overcome partitions all nodes in the
flooding area regularly rebroadcast the data packet. When the packet reaches
the destination an acknowledgment packet is sent and it is in turn
rebroadcasted by all nodes that have received the data packet. As for LAROD
a node will store the acknowledgement packet until the data packet times out
(tTTL) and if a node receives a data packet for which it has received an
acknowledgement packet it will broadcast an acknowledgement packet. For a
full description of the routing protocol and the parameters see Figure 33 and
Table 10.
Table 10.
Parameter
tdelay
trebroadcast
tTTL
BDTR parameter definitions.
Description
Delay until node shall broadcast received message.
Delay until node shall rebroadcast a message for which
it has not overheard a transmission by a forwarder.
Maximum time a packet is permitted to live.
For the simulations the flooding area used was a circle with a diameter
slightly larger than the distance between source and destination. This area
means that not all possible paths are searched, but it gives a good balance
between search space size and limiting the overhead. Tests with the complete
simulation area as broadcast area have shown that the overhead was
prohibitive and that it affected the ability to search all paths even at the low
loads used in our simulations.
47
BDTR is a simple protocol and robust in the sense that several nodes have an
individual packet and try to forward it to the destination. This means that
failure of a single node does not impact the routing to a great degree. The
rebroadcast and resend strategies used by BDTR means that it will quickly
saturate the wireless medium in dense networks or networks that transmit
large amounts of data. This means that BDTR by design in not suited for
these environments.
Source node at data packet generation
Broadcast data packet
Set up timer for rebroadcasting packet to trebroadcast
Destination node at data packet reception
The packet is received for the first time
Deliver data packet to application
Broadcast ack packet
A duplicate data packet is received
Broadcast ack packet
All intermediate (non-destination) nodes at data packet
reception
If an ack has been received for the packet
Broadcast ack packet
Else if the node is in the flooding area
If the node does not have an active4 copy
Set up timer for initial rebroadcast to tdelay
If the node has an active copy
Do nothing
Else
Do nothing
At ack packet reception
If the node has an active copy of the packet
Remove active copy
Broadcast ack packet
Else
Do nothing
When a data packet rebroadcasting timer expires
If the packet’s TTL has expired (tTTL)
Remove packet
Else
Broadcast data packet
Set up timer for rebroadcasting the packet to trebroadcast
Figure 33.
4
BDTR pseudo code.
A node has an active copy of a packet if it has a copy of the packet waiting on a timer to be
rebroadcasted.
48
4.3 Broadcast Routing (BR)
To evaluate how often a contemporaneous path exists between a sourcedestination pair a simple broadcast routing scheme was used. BR is identical
to BDTR except that the nodes do not continuously resend packets, they are
only re-broadcasted once. For BR we have used the entire simulation area as
broadcast area.
4.4 Evaluation
The above routing protocols have been implemented in a modified version of
ns2 2.30 [34]. The main changes to the simulator are:
(1) addition of the main algorithm LAROD, and the new baselines (BDTR
and its instance BR),
(2) addition of the pheromone repel mobility model,
(3) support for application level broadcasts,
(4) an application to generate and consume events.
As wireless communication technology we use IEEE 802.11 as implemented
in ns2 2.30 with default parameters using the two-ray ground radio
propagation model.
For the evaluation we use the scenario described in section 3.1 but we have
scaled the parameters to match the default radio range in ns-2. In Table 11 the
parameters are given both as the values used in the simulations and what
they correspond to in the scale used in section 3. The scale change makes
comparison with other studies easier since they generally use ns-2 with
default parameters. When scanning the area a UAV flies over it may detect
something that needs to be communicated to a ground unit that can act on it.
In the current simulations we have had four stationary ground units. The
generation of detect events and selection of receiver are both random
functions.
For the routing experiments we are interested in the performance when the
nodes are at the mobility model’s steady state. For this reason the UAVs are
initially randomly distributed over the reconnaissance area. The simulation is
then run for 1 hour without detect-event packets being generated to populate
the pheromone repel model with data. The detect events are then enabled for
1 hour and the simulation ends after all detect-event packets have timed out.
In the evaluations each data point is the average result of ten simulations.
49
Table 11.
Parameter
Reconnaissance area
Placement of ground units
Node density
UAV speed
Packet time to live (tTTL)
Detect data generation rate
Radio range
Scenario parameters
ns-2
2000x2000 meters
Center of each quadrant
2
10-30 (20) nodes/km
0.8-2.0 (1.4) m/s
200-600 (400) seconds
12-120 (36) pkt/hour/UAV
250 meters
Real-world
64x64 kilometers
2
0.010-0.029 (0.020) nodes/km
92-230 (161) km/h
8000 meters
The node speed used in our simulations might seem low compared to the
node speeds in other MANET papers [24][27], but it is actually close to the
average speed used in most simulations. The speed presented in most papers
is the top speed for the random waypoint mobility model. According to the
equations in [33] for a top speed of 20 m/s and minimum speed of 0.1 m/s
with no pause time 49.8% of the nodes would on average move slower than
1.4 m/s. Adding the fact that most simulations use pause times this means
that they have large number of relatively stable nodes that can be used to
create stable routes.
In Table 12 and Table 13 the parameter values used for LAROD and BDTR
are given. BR uses the same initial rebroadcast delay as BDTR. For values
where a range is given the actual value used is randomized in the range using
a rectangular distribution.
Table 12.
LAROD parameter values.
Parameter
tlmax
trmax
trebroadcast
dzero
dprogress
Table 13.
Parameter
tdelay
trebroadcast
Flooding area diameter
Value
1.0 seconds
0.2 seconds
8.0-12.0 seconds
240 meters
10 meters
BDTR parameter values.
Value
0.8-1.2 seconds
8.0-12.0 seconds
Source-destination distance + 100 meters
50
The goal of the evaluations is to measure the ability of LAROD to efficiently
and reliably perform routing in a mobile and intermittently connected
network. We have measured the delivery ratio (proportion of packets
delivered to the destination) and overhead (average number of packet
transmissions per generated data packet) for the different protocols while
changing the node density, node speed, packet life time and network load. To
gain further insight in the delivery properties we also study the accumulated
delivery ratio against delivery delay for some selected data points.
4.4.1 Node density
The higher the node density the more connected the network will be and the
easier it is to find a path between two nodes. As can be seen from the delivery
ratio of BR in Figure 34 the node density has a dramatic impact on the
existence of contemporaneous paths between source and destination. By
using store-carry-forward both LAROD and BDTR can overcome
communication gaps and they significantly improve the delivery ratio
compared to BR.
Even if LAROD and BDTR give about the same delivery ratio the overhead of
BDTR is much higher as can be seen in Figure 35. At low node densities a
BDTR packet is only receive by a few nodes since fewer nodes are in the
broadcast area. Additionally the clusters of connected nodes (partitions) will
contain fewer nodes. Both these factors result in fewer transmissions
generated at low node densities. As the node density increases more nodes
will receive a BDTR packet and the number of transmissions increases. The
reason the transmissions fall at higher node densities is that packets will be
delivered faster to the destination due to increased connectivity. This means
that the packet will live a shorter time in the network, reducing the number of
transmissions. For LAROD increased density means that fewer rebroadcasts
are required to overcome partitions and thus the overhead is lower for higher
node densities.
Studying the delay curves in Figure 36 we see that even with similar eventual
delivery ratio LAROD and BDTR have different delay properties. For higher
node densities the wider search of BDTR results in lower average delivery
delay since BDTR finds paths that LAROD does not. At low node densities,
on the other hand, there are so few paths available that both BDTR and
LAROD seem to find similar paths.
51
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
LAROD progress
BDTR circle
BR all
0.1
0
18
16
14
12
10
20
24
22
26
28
30
Node density (nodes/km2)
Figure 34.
Delivery ratio for different node densities.
300
LAROD progress
BDTR circle
BR all
Transmissions per data packet
250
200
150
100
50
0
10
12
18
16
14
20
24
22
26
28
30
Node density (nodes/km2)
Figure 35.
Overhead for different node densities.
1
0.9
0.8
Delivery ratio
0.7
LAROD 30 nodes/km2
LAROD 20 nodes/km2
0.6
LAROD 10 nodes/km2
0.5
BDTR 30 nodes/km2
0.4
BDTR 10 nodes/km2
BDTR 20 nodes/km2
0.3
0.2
0.1
0
0
50
100
150
200
250
300
350
Delay (s)
Figure 36.
Delay for different node densities.
400
52
4.4.2 Node speed
A higher node speed should give a higher delivery ratio since the increased
mobility will change the network topology at a higher pace enabling
messages to bridge communication gaps faster. In Figure 37 we see that this is
the case for both LAROD and BDTR. It is interesting to note that the delivery
ratio for BR increases somewhat with higher mobility. This probably comes
from the fact that BR has a short random delay between message reception
and the resending of a packet. During this time the nodes will move making
it possible to reach nodes that were not reachable at packet reception.
In Figure 38 we see that increased node speed decreases the overhead for
BDTR and LAROD. This is a natural consequence of the improved delivery
ratio at higher node speeds. Since most packets will be delivered before their
expiry time fewer packets will be active in the network at higher delivery
ratios and thereby reducing the number of rebroadcasts.
Looking at the delay curves for LAROD and BDTR in Figure 39 we see that
LAROD essentially has the same delivery ratio independent of speed after 10
seconds. This is essentially the delivery of packets to nodes with a
contemporaneous path from the source. After that node mobility is required
to close partition gaps which is done faster at higher speeds. For BDTR the
initial delivery ratio (first 10 seconds) is significantly affected by the node
speed. The reason is probably that with higher node speeds nodes receiving a
packet do scatter a bit more before a packet is rebroadcasted than with lower
speeds resulting in less interference. As for the node density DBTR has a
slightly better delivery ratio due to that more paths are searched.
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
LAROD progress
BDTR circle
BR all
0.1
0
0.8
1
1.2
1.4
1.6
1.8
2
Node speed (m/s)
Figure 37.
Delivery ratio for different node speeds.
53
300
LAROD progress
BDTR circle
BR all
Transmissions per data packet
250
200
150
100
50
0
2
1.8
1.6
1.4
1.2
1
0.8
Node speed (m/s)
Figure 38.
Overhead for different node speeds.
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
LAROD 2.0 m/s
LAROD 1.4 m/s
LAROD 0.8 m/s
BDTR 2.0 m/s
BDTR 1.4 m/s
BDTR 0.8 m/s
0.2
0.1
0
0
50
100
150
200
250
300
350
400
Delay (s)
Figure 39.
Delay for different node speeds.
4.4.3 Time to live
Increasing packet life time should increase the delivery ratio since more time
is allowed for node mobility to bridge network voids. A longer life time will
on the other hand also mean that the overhead will increase since more
rebroadcasts will occur due to that packets will try to reach the destination
for a longer time.
In Figure 40 we see the expected delivery rate improvement for both LAROD
and BDTR. Since BR is not affected by packet life time the delivery rate is
basically constant. In Figure 41 we see a significant increase in the overhead
for BDTR as the packet life time is increased. The overhead using LAROD
also increases, but at a much lower rate.
54
Studying the accumulated delivery ratio related to delivery delay LAROD
have essentially identical curved independent of time to live (TTL) value. For
BDTR the impact of the higher network load associated with a high TTL
value is obvious in Figure 42. This means that even if the eventual delivery
ratio is higher for a TTL of 600 seconds than 200 seconds the time to deliver a
packet will generally be longer.
As TTL is a tunable protocol parameter the question is which value to choose.
For data with a clear freshness requirement the TTL should match the
requirement if it does not result in an unacceptably high network load. For
other types of data the main limitation on a high TTL is acceptable network
load and resource consumption to deliver a packet.
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
LAROD progress
BDTR circle
BR all
0.1
0
200
250
300
350
400
450
500
550
600
Packet life time (s)
Figure 40.
Delivery ratio for different packet life times.
350
Transmissions per data packet
300
250
200
150
LAROD progress
BDTR circle
BR all
100
50
0
200
250
300
350
400
450
500
550
600
Packet life time (s)
Figure 41.
Overhead for different packet life times.
55
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
BDTR 200 s
BDTR 400 s
BDTR 600 s
0.1
0
0
100
200
300
400
500
600
Delay (s)
Figure 42.
Delay for different packet life times.
4.4.4 Network load
To investigate the scalability of the routing protocols when it comes to
network load different event generation rates were tested. Ideally a fully
scalable protocol will give the same result independent of network load. In
Figure 43 we see that the delivery ratio of BDTR drops as the load increases
while it stays constant for LAROD. The problem for BDTR is that the network
becomes congested and that several transmissions fail due to collisions. This
clearly shows that the broadcast strategy of BDTR has scalability issues. For
LAROD the critical load level is not yet reached and as a result the delivery
ratio is stable. In Figure 44 we see the consequence of the lower delivery ratio
on the load for BDTR. As the delivery ratio decreases and delivery times
increases the packets live longer in the network and as a result the per packet
overhead increases.
As LAROD has not reach a point where congestion becomes a problem all
LAROD delay curves are essentially identical to the 20 nodes/km² curve in
Figure 36. For BDRT on the other hand the effect of congestion is very
obvious in the delay curves in Figure 45. As the load increases more collisions
will occur and delivery takes more time.
56
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
LAROD progress
BDTR circle
BR all
0.1
0
120
100
80
60
40
20
Load (pkt/hour/UAV)
Figure 43.
Delivery ratio for different network loads.
350
Transmissions per data packet
300
LAROD progress
BDTR circle
BR all
250
200
150
100
50
0
120
100
80
60
40
20
Load (pkt/hour/UAV)
Figure 44.
Overhead for different network loads.
1
0.9
0.8
Delivery ratio
0.7
0.6
0.5
0.4
0.3
0.2
BDTR 12 packets/hour/UAV
BDTR 72 packets/hour/UAV
BDTR 120 packets/hour/UAV
0.1
0
0
50
100
150
200
250
300
350
Packet delivery latency (s)
Figure 45.
Delay for different network loads.
400
57
5 Conclusions
Conclusions and Future
Work
5.1 Conclusions
Routing in mobile ad hoc networks is challenging since the network layout is
constantly changing and constant distribution of the current network layout
to all nodes in the network is generally too costly. For this reason
geographical routing protocols are generally well suited for MANETS since
they are essentially stateless. The ability to use geographical routing does rely
on the nodes being location aware and that the (approximate) location of a
destination is known.
Depending on node density and node movement groups of nodes may be
separated from each other so that communication between nodes in different
partitions using contemporaneous paths is not possible. Due to node mobility
communication is still feasible by utilizing the store-carry-forward principle.
When message progress is not possible by wireless transfer the message is
stored in a suitable node until node mobility provides opportunities for
further wireless progress.
In this thesis we have studied communication in a reconnaissance scenario in
which a group of UAVs cooperatively shall detect units on the ground. To
guide them in a distributed and robust way we have designed a distributed
pheromone model where the UAVs are guided by virtual pheromones. This
model has been shown to provide good search coverage even when
communication between UAVs is poor. What the model also showed was that
with the assumed system parameters the connectivity between the UAVs was
low. This means that regular MANET routing protocols do not work since
they assume the existence of contemporaneous paths.
Since the UAVs are location aware we have explored the feasibility of
combining greedy geographical routing with the store-carry-forward
principle. To avoid position inaccuracies introduced by beacon based
58
geographical protocols we used the ideas from beacon-less geographical
routing protocols from MANET research and designed a routing protocol for
intermittently connected networks, LAROD. Our simulations have shown
that the delivery rate of LAROD is close to the delivery rate of an epidemic
routing protocol under the overload limit, that is the best possible result
achievable. Moreover, we have shown that the overheads measured in terms
of transmissions are considerably lower even under high load scenarios.
5.2 Future Work
A main constraint in our work is that we have assumed that the destinations
are static and that their positions are known to all sources. We wish to
remove this limitation by introducing a distributed location service in the
network. By this service the nodes can acquire a position or position estimate
of a node. Due to propagation delays, especially noticeable in intermittently
connected networks, the geographical routing needs to be able to handle
incorrect position information. One option could be to dynamically update
the positions in the packets as more accurate information of node location is
available at forwarders closer to the destination.
Another aspect we want to explore is how a UAV determines the nodes that
are interested in the intelligence it gathers. By some kind of publish subscribe
system the destinations should be able to inform UAVs of the data they are
interested in.
On the radio level we wish to explore the difference between broadcast
transmissions as used by LAROD and CTS/RTS with reliable data transfer.
What we are interested in exploring is how the reliable data transfer in the
CTS/RTS scheme affects the transfer probability. To properly explore the
tradeoffs the currently used two ray-ground radio model probably needs to
be replaced by a more realistic model like Nakagami [31] or log-normal
shadowing [40].
To become widely accepted a routing protocol should work well in a wide
range of environments. For this reason we intend to evaluate our suggested
routing algorithms under several different mobility models. At the same time
we will also continue to develop our scenario to become as realistic as
reasonably possible.
59
6 Acronyms
Acronym
AODV
BDTR
BLR
BR
CAR
CBF
CTS
DSR
DTGR
DTN
ER
FOPEN
GDBF
GeRaF
GPS
GPSR
GSM
ICT
IEEE
IETF
IGF
LAROD
OLSR
MANET
MoVe
PREP
PSGR
RFC
RTS
TBRPF
TTL
UAV
Description
Ad hoc on-demand distance vector routing
Broadcast delay-tolerant routing
Beacon-less routing
Broadcast routing
Context-aware routing
Contention-based forwarding
Clear to send
Dynamic source routing
Disruption-tolerant geographic routing for wireless ad hoc
networks
Delay-tolerant network, Disruption-tolerant network
Epidemic routing
Foliage penetration
Guaranteed delivery beacon-less forwarding
Geographic random forwarding
Global positioning system
Greedy perimeter stateless routing
Global system for mobile communications
Inter contact time
Institute of electrical and electronics engineers
Internet Engineering Task Force
Implicit geographical forwarding
Location aware routing for delay-tolerant networks
Optimized link state routing
Mobile ad-hoc network
Motion vector
Prioritized epidemic routing
Priority-based geographical forwarding
Request for comment
Ready/request to send
Topology dissemination based on reverse-path forwarding
Time to live
Unmanned aerial vehicle
60
61
7 References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
B. Blum, T. He, S. Son, J. Stankovic. IGF: A State-Free Robust
Communication Protocol for Wireless Sensor Networks. Technical
Report CS-2003-11, University of Virginia. 2003
B. Burns, O. Brock, B.N. Levine. MORA routing and capacity building
in disruption-tolerant networks. Ad Hoc Networks. 2007. Elsevier.
Article in press. doi:10.1016/j.adhoc.2007.05.002
J. Burgess, B. Gallagher, D. Jensen, B.N. Levine. MaxProp: Routing for
Vehicle-Based Disruption-Tolerant Networks. Proceedings of 25th
IEEE International Conference on Computer Communications
(INFOCOM). 2006. IEEE
T. Camp, J. Boleng, V. Davies. A survey of mobility models for ad hoc
network research. Wireless Communications and Mobile Computing.
Volume 2, Issue 5, 2002. John Wiley & Son
V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall,
H. Weiss. Delay-tolerant networking architecture. RFC 4838. April
2007. RFC Editor (ftp://ftp.rfc-editor.org/in-notes/rfc4838.txt)
A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, J. Scott. Pocket
Switched Networks: Real-world mobility and its consequences for
opportunistic forwarding. Technical Report UCAM-CL-TR-617. 2005.
University of Cambridge, Computer Laboratory
M. Chawala, N. Goel, K. Kalaichelvan, A. Nayak, I. Stojmenovic.
Beaconless Position-based Routing with Guaranteed Delivery for
Wireless Ad hoc and Sensor Networks. Acta Automatica Sinica.
Volume 32, Number 6, 2006. Elsevier
J.-M. Choi, Y.-B. Ko. A Performance Evaluation for Ad Hoc Routing
Protocols in Realistic Military Scenarios. Proceedings of the 9th
International Conference on Cellular and Intelligent Communications.
2004
T. Clausen, P. Jacquet. Optimized Link State Routing Protocol (OLSR).
RFC 3626. October 2003. RFC Editor (ftp://ftp.rfc-editor.org/in-notes/
rfc3626.txt)
62
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
S.M. Das, H. Pucha, Y.C. Hu. Performance Comparison of Scalable
Location Services for Geographic Ad Hoc Routing. Proceedings of 24th
Annual Joint Conference of the IEEE Computer and Communications
Societies (INFOCOM). 2005. IEEE
H. Füßler, J. Widmer, M. Käsemann, M. Mauve, H. Hartenstein.
Contention-based forwarding for mobile ad hoc networks. Ad Hoc
Networks. Volume 1, Issue 4, 2003. Elsevier
P. Gaudiano, B. Shargel, E. Bonabeu, B. T. Clough. Swarm Intelligence:
a New C2 Paradigm with an Application to Control of Swarms of
UAVs. Proceedings of 8th ICCRTS Command and Control Research
and Technology Symposium. 2003. Office of the Assistant Secretary of
Defense for Networks and Information Integration
M. Grossglauser, D.N.C. Tse. Mobility Increases the Capacity of Ad
Hoc Wireless Networks. IEEE/ACM Transactions on Networking.
Volume 10, Number 4, 2002. IEEE/ACM
M. Heissenbüttel, T. Braun, T. Bernoulli, M. Wälchi. BLR: beacon-less
routing algorithm for mobile ad hoc networks. Computer
Communications. Volume 27, Issue 11, 2004. Elsevier
M. Heissenbüttel, T. Braun, M. Wälchi, T. Bernoulli. Evaluating the
Limitations of and Alternatives in Beaconing. Ad Hoc Networks.
Volume 5, Issue 5, 2007. Elsevier
T. Henderson, D. Kotz, I. Abyzov. The changing usage of mature
campus-wide wireless network. Proceedings of the 10th annual
international conference on Mobile computing and networking
(MobiCom), 2004, ACM
X. Hong, M. Gerla, G. Pei, c. Chiang. A group mobility model for as
hoc wireless networks. Proceedings of the 2nd ACM international
workshop on Modeling, analysis and simulation of wireless and mobile
systems (MSWiM). 1999. ACM
J. Hsu, S. Bhatia, K. Tang, R. Bagrodia, M.J. Acriche. Performance of
Mobile Ad Hoc Networking Routing Protocols in Large Scale
Scenarios. Proceedings of Military Communications Conference
(MILCOM). 2004. IEEE
W.-J. Hsu, K. Merchant, H.-W. Shu, C.-H. Hsu, A. Helmy. Weighted
Waypoint Mobility Model and its Impact on Ad Hoc Networks. Mobile
Computing and Communications Review. Volume 9, Number 1, 2005.
ACM
P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, C. Diot. Pocket
Switched Networks and Human Mobility in Conference Environments.
63
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant
networking (WDTN). 2005. ACM
A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, S. Suri. Towards
Realistic Mobility Models for Mobile Ad Hoc Networks. Proceedings of
the 9th annual international conference on Mobile computing and
networking (MobiCom). 2003. ACM
D. Johnson, D. Maltz. Dynamic source routing in ad hoc wireless
networks. Mobile Computing, The Springer International Series in
Engineering and Computer Science, Volume 353. 1996. Springer
D. Johnson, Y. Hu, D. Maltz. The Dynamic Source Routing Protocol
(DSR) for Mobile Ad Hoc Networks for IPv4. RFC 4728. February 2007.
RFC Editor (ftp://ftp.rfc-editor.org/in-notes/rfc4728.txt)
B. Karp, H.T. Kung. GPSR: Greedy perimeter stateless routing for
wireless networks. Proceedings of the 6th annual international
conference on Mobile computing and networking (MobiCom). 2000.
ACM
M. Kim, D. Kotz, S. Kim. Extracting a mobility model from real user
traces. Proceedings of 25th IEEE International Conference on
Computer Communications (INFOCOM). 2006. IEEE
J. LeBrun, C. Chuah, D. Ghosal, M. Zhang. Knowledge-Based
Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks.
Proceedings of IEEE 61st Vehicular Technology Conference (VTC).
2005. IEEE
Y. Li, T.H. Lai, M.T. Liu, M. Sun, J. Yang. DTGR: Disruption-tolerant
geographic routing for wireless ad hoc networks. Simulation. Volume
82, Number 6, 2006. Sage
G. Marfia, G. Pau, E. De Sena, E. Giordano, M. Gerla. Evaluating
Vehicle Network Strategies for Downtown Portland: Opportunistic
Infrastructure and the Importance of Realistic Mobility Models.
Proceedings of the 1st international MobiSys workshop on Mobile
opportunistic networking (MobiOpp). 2007. ACM
M. McNett, G.M. Voelker. Access and mobility of wireless PDA users.
Technical report, Computer Scinece and Engineering, UC San Diego.
2004
M. Musolesi, S. Hailes, C. Mascolo. Adaptive Routing for
Intermittently Connected Mobile Ad Hoc Networks. Proceedings of
Sixth IEEE International Symposium on a World of Wireless Mobile
and Multimedia Networks (WoWMoM). 2005. IEEE
64
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
M. Nakagami. The m-distribution, a General Formula of Intensity
Distribution of the Rapid Fading. Statistical Methods in Radio Wave
Propagation (editor W. G. Hoffman). 1960. Pergamon Press
V. Naumov, R. Baumann, T. Gross. An Evaluation of Inter-Vehicle Ad
Hoc Networks Based on Realistic Vehicular Traces. Proceedings of the
7th ACM international symposium on Mobile ad hoc networking and
computing (MobiHoc). 2006. ACM
W. Navidi, T. Camp. Stationary Distributions for the Random
Waypoint Mobility Model. IEEE Transactions on Mobile Computing.
Volume 3, Number 1, 2004. IEEE
http://nsnam.isi.edu/nsnam/index.php/Main_Page
R. Ogier, F. Templin, M. Lewis. Topology Dissemination Based on
Reverse-Path Forwarding (TBRPF). RFC 3684. February 2004. RFC
Editor (ftp://ftp.rfc-editor.org/in-notes/rfc3684.txt)
A. Papoulis. Probability, Random Variables, and Stochastic Processes.
1991. McGraw-Hill
H. V. D. Parunak, S. A. Brueckner, J. J. Odell. Swarming Coordination
of Multiple UAV’s for Collaborative Sensing. Proceedings of 2nd AIAA
Unmanned Unlimited Systems Technologies and Operations
Aerospace land and Sea Conference and Workshop & Exhibit. 2003.
American Institute of Aeronautics and Astronautics
C. Perkins, E. Belding-Royer, S. Das. Ad hoc On-Demand Distance
Vector (AODV) Routing. RFC 3561. July 2003. RFC Editor
(ftp://ftp.rfc-editor.org/in-notes/rfc3561.txt)
R. Ramanathan, R. Hansen, P. Basu, R. Rosales-Hain, R. Krishnan.
Prioritized Epidemic Routing for Opportunistic Networks. Proceedings
of the 1st international MobiSys workshop on Mobile opportunistic
networking (MobiOpp). 2007. ACM
T.S. Rappaport. Wireless Communications, 2nd edition. 2002. Prentice
Hall
I. Rhee, M. Shin, S. Hong, K. Lee, S. Chong. On the Levy-walk Nature
of Human Mobility. Proceedings of The 27th Conference on Computer
Communications (INFOCOM). 2008. IEEE. To be published
J. A. Sauter, R. Matthews, H. V. D. Parunak, S. A. Brueckner.
Performance of Digital Pheromones for Swarming Vehicle Control.
Proceedings of the fourth international joint conference on
Autonomous agents and multiagent systems (AAMAS). 2005. ACM
65
[43]
[44]
[45]
[46]
[47]
[48]
[49]
[50]
[51]
[52]
[53]
[54]
M.F. Shlesinger, J. Klafter, Y.M. Wong. Random walks with infinite
spatial and temporal moments. Journal of Statistical Physics. Volume
27, Number 3, 1982. Springer
L. Song, D.F. Kotz. Evaluating Opportunistic Routing Protocols with
large Realistic Contact Traces. Proceedings of the second workshop on
Challenged networks (CHANTS). 2007. ACM
Specification of the Bluetooth system Version 2.1 + EDR, 26 July 2007,
Bluetooth SIG, available from
http://bluetooth.com/Bluetooth/Learn/Technology/Specifications/
T. Spyropoulos, K. Psounis, C.S. Raghavendra. Single-copy routing in
intermittently connected mobile networks. Proceedings of First Annual
IEEE Communications Society Conference on Sensor and Ad Hoc
Communications and Networks (SECON). 2004. IEEE
T. Spyropoulos, K. Psounis, C.S. Raghavendra. Spray and wait: an
efficient routing scheme for intermittently connected mobile networks.
Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant
networking (WDTN). 2005. ACM
T. Spyropoulos, T. Turletti, K. Obraczka. Utility-based Message
Replication for Intermittently Connected Heterogeneous Networks.
Proceedings of IEEE International Symposium on a World of Wireless,
Mobile and Multimedia Networks (WoWMoM). 2007. IEEE
J. Su, A. Goel, E. de Lara. An Empirical Evaluation of the Student-Net
Delay Tolerant Network. Proceedings of Third Annual International
Conference on Mobile and Ubiquitous Systems: Networking & Services
(MobiQuitous). 2006. IEEE
V. Tolety. Load Reduction in Ad Hoc Networks Using Mobile Servers.
Master’s thesis. 1999. Colorado School of Mines
A. Vahdat, D. Becker. Epidemic Routing for Partially-Connected Ad
Hoc Networks. Tech. Rep. CS-2000-06, Duke University. 2000
Y. Xu, W.-C. Lee, J. Xu, G. Mitchell. PSGR: Priority-based Stateless
Geo-Routing in Wireless Sensor Networks. Proceedings of IEEE
International Conference on Mobile Adhoc and Sensor Systems
(MASS). 2005. IEEE
C. Zhang. Routing in Intermittently Connected Mobile Ad Hoc
Networks and Delay tolerant networks: Overview and Challenges.
IEEE Communications Surveys & Tutorials. Volume 8, Issue 1, 2006.
IEEE
X. Zhang, J. Kurose, N. Levine, D. Towsley, H. Zhang. Study of a Busbased Distruption-Tolerant Network: Mobility Modeling and Impact
66
[55]
[56]
[57]
[58]
on Routing. Proceedings of the 13th annual ACM international
conference on Mobile computing and networking (MobiCom). 2007.
ACM
B. Zhou, K. Xu, M. Gerla. Group and Swarm Mobility Models for Ad
Hoc
Network
Scenarios
Using
Virtual
Tracks.
Military
Communications Conference (MILCOM). 2004. IEEE
ZigBee Specification, 1 December 2006, ZigBee Standards Organization
M. Zorzi, R.R. Rao. Geographic Random Forwarding (GeRaF) for Ad
Hoc and Sensor Networks: Energy and Latency Performance. IEEE
Transactions on Mobile Computing. Volume 2, Number 4, 2003. IEEE
M. Zorzi, R.R. Rao. Geographic Random Forwarding (GeRaF) for Ad
Hoc and Sensor Networks: Multihop Performance. IEEE Transactions
on Mobile Computing. Volume 2, Number 4, 2003. IEEE
Datum
Date
Avdelning, institution
Division, department
Institutionen för datavetenskap
LINKÖPINGS UNIVERSITET
Språk
Language
Department of Computer
and Information Science
Rapporttyp
Report category
Svenska/Swedish
X Engelska/English
X Licentiatavhandling
Examensarbete
C-uppsats
D-uppsats
ISBN
ISRN
2008-04-14
978-91-7393-937-9
LiU-Tek-Lic- 2008:14
Serietitel och serienummer
Title of series, numbering
ISSN
0280-7971
Övrig rapport
Linköping Studies in Science and Technology
URL för elektronisk version
Thesis No. 1356
Titel
Title
Mobility and Routing in a Delay-tolerant Network of Unmanned Aerial Vehicles
Författare
Author
Erik Kuiper
Sammanfattning
Abstract
Technology has reached a point where it has become feasible to develop unmanned aerial vehicles (UAVs), that is
aircraft without a human pilot on board. Given that future UAVs can be autonomous and cheap, applications of
swarming UAVs are possible. In this thesis we have studied a reconnaissance application using swarming UAVs and
how these UAVs can communicate the reconnaissance data. To guide the UAVs in their reconnaissance mission we
have proposed a pheromone based mobility model that in a distributed manner guides the UAVs to areas not recently
visited. Each UAV has a local pheromone map that it updates based on its reconnaissance scans. The information in
the local map is regularly shared with a UAV’s neighbors. Evaluations have shown that the pheromone logic is very
good at guiding the UAVs in their cooperative reconnaissance mission in a distributed manner.
Analyzing the connectivity of the UAVs we found that they were heavily partitioned which meant that
contemporaneous communication paths generally were not possible to establish. This means that traditional mobile
ad hoc network (MANET) routing protocols like AODV, DSR and GPSR will generally fail. By using node mobility
and the store-carry-forward principle of delay-tolerant routing the transfer of messages between nodes is still
possible. In this thesis we propose location aware routing for delay-tolerant networks (LAROD). LAROD is a
beacon-less geographical routing protocol for intermittently connected mobile ad hoc networks. Using static
destinations we have shown by a comparative study that LAROD has almost as good delivery rate as an epidemic
routing scheme, but at a substantially lower overhead.
Nyckelord
Keywords
mobility models, routing, ad hoc networks, delay-tolerant networks
Department of Computer and Information Science
Linköpings universitet
Linköping Studies in Science and Technology
Faculty of Arts and Sciences - Licentiate Theses
No 17
No 28
No 29
No 48
No 52
No 60
No 71
No 72
No 73
No 74
No 104
No 108
No 111
No 113
No 118
No 126
No 127
No 139
No 140
No 146
No 150
No 165
No 166
No 174
No 177
No 181
No 184
No 187
No 189
No 196
No 197
No 203
No 212
No 230
No 237
No 250
No 253
No 260
No 283
No 298
No 318
No 319
No 326
No 328
No 333
No 335
No 348
No 352
No 371
No 378
No 380
No 381
No 383
No 386
No 398
Vojin Plavsic: Interleaved Processing of Non-Numerical Data Stored on a Cyclic Memory. (Available at:
FOA, Box 1165, S-581 11 Linköping, Sweden. FOA Report B30062E)
Arne Jönsson, Mikael Patel: An Interactive Flowcharting Technique for Communicating and Realizing Algorithms, 1984.
Johnny Eckerland: Retargeting of an Incremental Code Generator, 1984.
Henrik Nordin: On the Use of Typical Cases for Knowledge-Based Consultation and Teaching, 1985.
Zebo Peng: Steps Towards the Formalization of Designing VLSI Systems, 1985.
Johan Fagerström: Simulation and Evaluation of Architecture based on Asynchronous Processes, 1985.
Jalal Maleki: ICONStraint, A Dependency Directed Constraint Maintenance System, 1987.
Tony Larsson: On the Specification and Verification of VLSI Systems, 1986.
Ola Strömfors: A Structure Editor for Documents and Programs, 1986.
Christos Levcopoulos: New Results about the Approximation Behavior of the Greedy Triangulation, 1986.
Shamsul I. Chowdhury: Statistical Expert Systems - a Special Application Area for Knowledge-Based Computer Methodology, 1987.
Rober Bilos: Incremental Scanning and Token-Based Editing, 1987.
Hans Block: SPORT-SORT Sorting Algorithms and Sport Tournaments, 1987.
Ralph Rönnquist: Network and Lattice Based Approaches to the Representation of Knowledge, 1987.
Mariam Kamkar, Nahid Shahmehri: Affect-Chaining in Program Flow Analysis Applied to Queries of Programs, 1987.
Dan Strömberg: Transfer and Distribution of Application Programs, 1987.
Kristian Sandahl: Case Studies in Knowledge Acquisition, Migration and User Acceptance of Expert Systems, 1987.
Christer Bäckström: Reasoning about Interdependent Actions, 1988.
Mats Wirén: On Control Strategies and Incrementality in Unification-Based Chart Parsing, 1988.
Johan Hultman: A Software System for Defining and Controlling Actions in a Mechanical System, 1988.
Tim Hansen: Diagnosing Faults using Knowledge about Malfunctioning Behavior, 1988.
Jonas Löwgren: Supporting Design and Management of Expert System User Interfaces, 1989.
Ola Petersson: On Adaptive Sorting in Sequential and Parallel Models, 1989.
Yngve Larsson: Dynamic Configuration in a Distributed Environment, 1989.
Peter Åberg: Design of a Multiple View Presentation and Interaction Manager, 1989.
Henrik Eriksson: A Study in Domain-Oriented Tool Support for Knowledge Acquisition, 1989.
Ivan Rankin: The Deep Generation of Text in Expert Critiquing Systems, 1989.
Simin Nadjm-Tehrani: Contributions to the Declarative Approach to Debugging Prolog Programs, 1989.
Magnus Merkel: Temporal Information in Natural Language, 1989.
Ulf Nilsson: A Systematic Approach to Abstract Interpretation of Logic Programs, 1989.
Staffan Bonnier: Horn Clause Logic with External Procedures: Towards a Theoretical Framework, 1989.
Christer Hansson: A Prototype System for Logical Reasoning about Time and Action, 1990.
Björn Fjellborg: An Approach to Extraction of Pipeline Structures for VLSI High-Level Synthesis, 1990.
Patrick Doherty: A Three-Valued Approach to Non-Monotonic Reasoning, 1990.
Tomas Sokolnicki: Coaching Partial Plans: An Approach to Knowledge-Based Tutoring, 1990.
Lars Strömberg: Postmortem Debugging of Distributed Systems, 1990.
Torbjörn Näslund: SLDFA-Resolution - Computing Answers for Negative Queries, 1990.
Peter D. Holmes: Using Connectivity Graphs to Support Map-Related Reasoning, 1991.
Olof Johansson: Improving Implementation of Graphical User Interfaces for Object-Oriented KnowledgeBases, 1991.
Rolf G Larsson: Aktivitetsbaserad kalkylering i ett nytt ekonomisystem, 1991.
Lena Srömbäck: Studies in Extended Unification-Based Formalism for Linguistic Description: An Algorithm
for Feature Structures with Disjunction and a Proposal for Flexible Systems, 1992.
Mikael Pettersson: DML-A Language and System for the Generation of Efficient Compilers from Denotational Specification, 1992.
Andreas Kågedal: Logic Programming with External Procedures: an Implementation, 1992.
Patrick Lambrix: Aspects of Version Management of Composite Objects, 1992.
Xinli Gu: Testability Analysis and Improvement in High-Level Synthesis Systems, 1992.
Torbjörn Näslund: On the Role of Evaluations in Iterative Development of Managerial Support Sytems,
1992.
Ulf Cederling: Industrial Software Development - a Case Study, 1992.
Magnus Morin: Predictable Cyclic Computations in Autonomous Systems: A Computational Model and Implementation, 1992.
Mehran Noghabai: Evaluation of Strategic Investments in Information Technology, 1993.
Mats Larsson: A Transformational Approach to Formal Digital System Design, 1993.
Johan Ringström: Compiler Generation for Parallel Languages from Denotational Specifications, 1993.
Michael Jansson: Propagation of Change in an Intelligent Information System, 1993.
Jonni Harrius: An Architecture and a Knowledge Representation Model for Expert Critiquing Systems, 1993.
Per Österling: Symbolic Modelling of the Dynamic Environments of Autonomous Agents, 1993.
Johan Boye: Dependency-based Groudness Analysis of Functional Logic Programs, 1993.
No 402
No 406
No 414
No 417
No 436
No 437
No 440
FHS 3/94
FHS 4/94
No 441
No 446
No 450
No 451
No 452
No 455
FHS 5/94
No 462
No 463
No 464
No 469
No 473
No 475
No 476
No 478
FHS 7/95
No 482
No 488
No 489
No 497
No 498
No 503
FHS 8/95
FHS 9/95
No 513
No 517
No 518
No 522
No 538
No 545
No 546
FiF-a 1/96
No 549
No 550
No 557
No 558
No 561
No 563
No 567
No 575
No 576
No 587
No 589
No 591
No 595
No 597
Lars Degerstedt: Tabulated Resolution for Well Founded Semantics, 1993.
Anna Moberg: Satellitkontor - en studie av kommunikationsmönster vid arbete på distans, 1993.
Peter Carlsson: Separation av företagsledning och finansiering - fallstudier av företagsledarutköp ur ett agentteoretiskt perspektiv, 1994.
Camilla Sjöström: Revision och lagreglering - ett historiskt perspektiv, 1994.
Cecilia Sjöberg: Voices in Design: Argumentation in Participatory Development, 1994.
Lars Viklund: Contributions to a High-level Programming Environment for a Scientific Computing, 1994.
Peter Loborg: Error Recovery Support in Manufacturing Control Systems, 1994.
Owen Eriksson: Informationssystem med verksamhetskvalitet - utvärdering baserat på ett verksamhetsinriktat och samskapande perspektiv, 1994.
Karin Pettersson: Informationssystemstrukturering, ansvarsfördelning och användarinflytande - En komparativ studie med utgångspunkt i två informationssystemstrategier, 1994.
Lars Poignant: Informationsteknologi och företagsetablering - Effekter på produktivitet och region, 1994.
Gustav Fahl: Object Views of Relational Data in Multidatabase Systems, 1994.
Henrik Nilsson: A Declarative Approach to Debugging for Lazy Functional Languages, 1994.
Jonas Lind: Creditor - Firm Relations: an Interdisciplinary Analysis, 1994.
Martin Sköld: Active Rules based on Object Relational Queries - Efficient Change Monitoring Techniques,
1994.
Pär Carlshamre: A Collaborative Approach to Usability Engineering: Technical Communicators and System
Developers in Usability-Oriented Systems Development, 1994.
Stefan Cronholm: Varför CASE-verktyg i systemutveckling? - En motiv- och konsekvensstudie avseende arbetssätt och arbetsformer, 1994.
Mikael Lindvall: A Study of Traceability in Object-Oriented Systems Development, 1994.
Fredrik Nilsson: Strategi och ekonomisk styrning - En studie av Sandviks förvärv av Bahco Verktyg, 1994.
Hans Olsén: Collage Induction: Proving Properties of Logic Programs by Program Synthesis, 1994.
Lars Karlsson: Specification and Synthesis of Plans Using the Features and Fluents Framework, 1995.
Ulf Söderman: On Conceptual Modelling of Mode Switching Systems, 1995.
Choong-ho Yi: Reasoning about Concurrent Actions in the Trajectory Semantics, 1995.
Bo Lagerström: Successiv resultatavräkning av pågående arbeten. - Fallstudier i tre byggföretag, 1995.
Peter Jonsson: Complexity of State-Variable Planning under Structural Restrictions, 1995.
Anders Avdic: Arbetsintegrerad systemutveckling med kalkylkprogram, 1995.
Eva L Ragnemalm: Towards Student Modelling through Collaborative Dialogue with a Learning Companion, 1995.
Eva Toller: Contributions to Parallel Multiparadigm Languages: Combining Object-Oriented and Rule-Based
Programming, 1995.
Erik Stoy: A Petri Net Based Unified Representation for Hardware/Software Co-Design, 1995.
Johan Herber: Environment Support for Building Structured Mathematical Models, 1995.
Stefan Svenberg: Structure-Driven Derivation of Inter-Lingual Functor-Argument Trees for Multi-Lingual
Generation, 1995.
Hee-Cheol Kim: Prediction and Postdiction under Uncertainty, 1995.
Dan Fristedt: Metoder i användning - mot förbättring av systemutveckling genom situationell metodkunskap
och metodanalys, 1995.
Malin Bergvall: Systemförvaltning i praktiken - en kvalitativ studie avseende centrala begrepp, aktiviteter och
ansvarsroller, 1995.
Joachim Karlsson: Towards a Strategy for Software Requirements Selection, 1995.
Jakob Axelsson: Schedulability-Driven Partitioning of Heterogeneous Real-Time Systems, 1995.
Göran Forslund: Toward Cooperative Advice-Giving Systems: The Expert Systems Experience, 1995.
Jörgen Andersson: Bilder av småföretagares ekonomistyrning, 1995.
Staffan Flodin: Efficient Management of Object-Oriented Queries with Late Binding, 1996.
Vadim Engelson: An Approach to Automatic Construction of Graphical User Interfaces for Applications in
Scientific Computing, 1996.
Magnus Werner : Multidatabase Integration using Polymorphic Queries and Views, 1996.
Mikael Lind: Affärsprocessinriktad förändringsanalys - utveckling och tillämpning av synsätt och metod,
1996.
Jonas Hallberg: High-Level Synthesis under Local Timing Constraints, 1996.
Kristina Larsen: Förutsättningar och begränsningar för arbete på distans - erfarenheter från fyra svenska företag. 1996.
Mikael Johansson: Quality Functions for Requirements Engineering Methods, 1996.
Patrik Nordling: The Simulation of Rolling Bearing Dynamics on Parallel Computers, 1996.
Anders Ekman: Exploration of Polygonal Environments, 1996.
Niclas Andersson: Compilation of Mathematical Models to Parallel Code, 1996.
Johan Jenvald: Simulation and Data Collection in Battle Training, 1996.
Niclas Ohlsson: Software Quality Engineering by Early Identification of Fault-Prone Modules, 1996.
Mikael Ericsson: Commenting Systems as Design Support—A Wizard-of-Oz Study, 1996.
Jörgen Lindström: Chefers användning av kommunikationsteknik, 1996.
Esa Falkenroth: Data Management in Control Applications - A Proposal Based on Active Database Systems,
1996.
Niclas Wahllöf: A Default Extension to Description Logics and its Applications, 1996.
Annika Larsson: Ekonomisk Styrning och Organisatorisk Passion - ett interaktivt perspektiv, 1997.
Ling Lin: A Value-based Indexing Technique for Time Sequences, 1997.
No 598
No 599
No 607
No 609
FiF-a 4
FiF-a 6
No 615
No 623
No 626
No 627
No 629
No 631
No 639
No 640
No 643
No 653
FiF-a 13
No 674
No 676
No 668
No 675
FiF-a 14
No 695
No 700
FiF-a 16
No 712
No 719
No 723
No 725
No 730
No 731
No 733
No 734
FiF-a 21
FiF-a 22
No 737
No 738
FiF-a 25
No 742
No 748
No 751
No 752
No 753
No 754
No 766
No 769
No 775
FiF-a 30
No 787
No 788
No 790
No 791
No 800
No 807
Rego Granlund: C3Fire - A Microworld Supporting Emergency Management Training, 1997.
Peter Ingels: A Robust Text Processing Technique Applied to Lexical Error Recovery, 1997.
Per-Arne Persson: Toward a Grounded Theory for Support of Command and Control in Military Coalitions,
1997.
Jonas S Karlsson: A Scalable Data Structure for a Parallel Data Server, 1997.
Carita Åbom: Videomötesteknik i olika affärssituationer - möjligheter och hinder, 1997.
Tommy Wedlund: Att skapa en företagsanpassad systemutvecklingsmodell - genom rekonstruktion, värdering och vidareutveckling i T50-bolag inom ABB, 1997.
Silvia Coradeschi: A Decision-Mechanism for Reactive and Coordinated Agents, 1997.
Jan Ollinen: Det flexibla kontorets utveckling på Digital - Ett stöd för multiflex? 1997.
David Byers: Towards Estimating Software Testability Using Static Analysis, 1997.
Fredrik Eklund: Declarative Error Diagnosis of GAPLog Programs, 1997.
Gunilla Ivefors: Krigsspel coh Informationsteknik inför en oförutsägbar framtid, 1997.
Jens-Olof Lindh: Analysing Traffic Safety from a Case-Based Reasoning Perspective, 1997
Jukka Mäki-Turja:. Smalltalk - a suitable Real-Time Language, 1997.
Juha Takkinen: CAFE: Towards a Conceptual Model for Information Management in Electronic Mail, 1997.
Man Lin: Formal Analysis of Reactive Rule-based Programs, 1997.
Mats Gustafsson: Bringing Role-Based Access Control to Distributed Systems, 1997.
Boris Karlsson: Metodanalys för förståelse och utveckling av systemutvecklingsverksamhet. Analys och värdering av systemutvecklingsmodeller och dess användning, 1997.
Marcus Bjäreland: Two Aspects of Automating Logics of Action and Change - Regression and Tractability,
1998.
Jan Håkegård: Hiera rchical Test Architecture and Board-Level Test Controller Synthesis, 1998.
Per-Ove Zetterlund: Normering av svensk redovisning - En studie av tillkomsten av Redovisningsrådets rekommendation om koncernredovisning (RR01:91), 1998.
Jimmy Tjäder: Projektledaren & planen - en studie av projektledning i tre installations- och systemutvecklingsprojekt, 1998.
Ulf Melin: Informationssystem vid ökad affärs- och processorientering - egenskaper, strategier och utveckling, 1998.
Tim Heyer: COMPASS: Introduction of Formal Methods in Code Development and Inspection, 1998.
Patrik Hägglund: Programming Languages for Computer Algebra, 1998.
Marie-Therese Christiansson: Inter-organistorisk verksamhetsutveckling - metoder som stöd vid utveckling
av partnerskap och informationssystem, 1998.
Christina Wennestam: Information om immateriella resurser. Investeringar i forskning och utveckling samt
i personal inom skogsindustrin, 1998.
Joakim Gustafsson: Extending Temporal Action Logic for Ramification and Concurrency, 1998.
Henrik André-Jönsson: Indexing time-series data using text indexing methods, 1999.
Erik Larsson: High-Level Testability Analysis and Enhancement Techniques, 1998.
Carl-Johan Westin: Informationsförsörjning: en fråga om ansvar - aktiviteter och uppdrag i fem stora svenska
organisationers operativa informationsförsörjning, 1998.
Åse Jansson: Miljöhänsyn - en del i företags styrning, 1998.
Thomas Padron-McCarthy: Performance-Polymorphic Declarative Queries, 1998.
Anders Bäckström: Värdeskapande kreditgivning - Kreditriskhantering ur ett agentteoretiskt perspektiv,
1998.
Ulf Seigerroth: Integration av förändringsmetoder - en modell för välgrundad metodintegration, 1999.
Fredrik Öberg: Object-Oriented Frameworks - A New Strategy for Case Tool Development, 1998.
Jonas Mellin: Predictable Event Monitoring, 1998.
Joakim Eriksson: Specifying and Managing Rules in an Active Real-Time Database System, 1998.
Bengt E W Andersson: Samverkande informationssystem mellan aktörer i offentliga åtaganden - En teori om
aktörsarenor i samverkan om utbyte av information, 1998.
Pawel Pietrzak: Static Incorrectness Diagnosis of CLP (FD), 1999.
Tobias Ritzau: Real-Time Reference Counting in RT-Java, 1999.
Anders Ferntoft: Elektronisk affärskommunikation - kontaktkostnader och kontaktprocesser mellan kunder
och leverantörer på producentmarknader,1999.
Jo Skåmedal: Arbete på distans och arbetsformens påverkan på resor och resmönster, 1999.
Johan Alvehus: Mötets metaforer. En studie av berättelser om möten, 1999.
Magnus Lindahl: Bankens villkor i låneavtal vid kreditgivning till högt belånade företagsförvärv: En studie
ur ett agentteoretiskt perspektiv, 2000.
Martin V. Howard: Designing dynamic visualizations of temporal data, 1999.
Jesper Andersson: Towards Reactive Software Architectures, 1999.
Anders Henriksson: Unique kernel diagnosis, 1999.
Pär J. Ågerfalk: Pragmatization of Information Systems - A Theoretical and Methodological Outline, 1999.
Charlotte Björkegren: Learning for the next project - Bearers and barriers in knowledge transfer within an
organisation, 1999.
Håkan Nilsson: Informationsteknik som drivkraft i granskningsprocessen - En studie av fyra revisionsbyråer,
2000.
Erik Berglund: Use-Oriented Documentation in Software Development, 1999.
Klas Gäre: Verksamhetsförändringar i samband med IS-införande, 1999.
Anders Subotic: Software Quality Inspection, 1999.
Svein Bergum: Managerial communication in telework, 2000.
No 809
FiF-a 32
No 808
No 820
No 823
No 832
FiF-a 34
No 842
No 844
FiF-a 37
FiF-a 40
FiF-a 41
No. 854
No 863
No 881
No 882
No 890
FiF-a 47
No 894
No 906
No 917
No 916
FiF-a-49
FiF-a-51
No 919
No 915
No 931
No 933
No 938
No 942
No 956
FiF-a 58
No 964
No 973
No 958
FiF-a 61
No 985
No 982
No 989
No 990
No 991
No 999
No 1000
No 1001
No 988
FiF-a 62
No 1003
No 1005
No 1008
No 1010
No 1015
No 1018
No 1022
FiF-a 65
Flavius Gruian: Energy-Aware Design of Digital Systems, 2000.
Karin Hedström: Kunskapsanvändning och kunskapsutveckling hos verksamhetskonsulter - Erfarenheter
från ett FOU-samarbete, 2000.
Linda Askenäs: Affärssystemet - En studie om teknikens aktiva och passiva roll i en organisation, 2000.
Jean Paul Meynard: Control of industrial robots through high-level task programming, 2000.
Lars Hult: Publika Gränsytor - ett designexempel, 2000.
Paul Pop: Scheduling and Communication Synthesis for Distributed Real-Time Systems, 2000.
Göran Hultgren: Nätverksinriktad Förändringsanalys - perspektiv och metoder som stöd för förståelse och
utveckling av affärsrelationer och informationssystem, 2000.
Magnus Kald: The role of management control systems in strategic business units, 2000.
Mikael Cäker: Vad kostar kunden? Modeller för intern redovisning, 2000.
Ewa Braf: Organisationers kunskapsverksamheter - en kritisk studie av ”knowledge management”, 2000.
Henrik Lindberg: Webbaserade affärsprocesser - Möjligheter och begränsningar, 2000.
Benneth Christiansson: Att komponentbasera informationssystem - Vad säger teori och praktik?, 2000.
Ola Pettersson: Deliberation in a Mobile Robot, 2000.
Dan Lawesson: Towards Behavioral Model Fault Isolation for Object Oriented Control Systems, 2000.
Johan Moe: Execution Tracing of Large Distributed Systems, 2001.
Yuxiao Zhao: XML-based Frameworks for Internet Commerce and an Implementation of B2B
e-procurement, 2001.
Annika Flycht-Eriksson: Domain Knowledge Management inInformation-providing Dialogue systems,
2001.
Per-Arne Segerkvist: Webbaserade imaginära organisationers samverkansformer: Informationssystemarkitektur och aktörssamverkan som förutsättningar för affärsprocesser, 2001.
Stefan Svarén: Styrning av investeringar i divisionaliserade företag - Ett koncernperspektiv, 2001.
Lin Han: Secure and Scalable E-Service Software Delivery, 2001.
Emma Hansson: Optionsprogram för anställda - en studie av svenska börsföretag, 2001.
Susanne Odar: IT som stöd för strategiska beslut, en studie av datorimplementerade modeller av verksamhet
som stöd för beslut om anskaffning av JAS 1982, 2002.
Stefan Holgersson: IT-system och filtrering av verksamhetskunskap - kvalitetsproblem vid analyser och beslutsfattande som bygger på uppgifter hämtade från polisens IT-system, 2001.
Per Oscarsson:Informationssäkerhet i verksamheter - begrepp och modeller som stöd för förståelse av informationssäkerhet och dess hantering, 2001.
Luis Alejandro Cortes: A Petri Net Based Modeling and Verification Technique for Real-Time Embedded
Systems, 2001.
Niklas Sandell: Redovisning i skuggan av en bankkris - Värdering av fastigheter. 2001.
Fredrik Elg: Ett dynamiskt perspektiv på individuella skillnader av heuristisk kompetens, intelligens, mentala
modeller, mål och konfidens i kontroll av mikrovärlden Moro, 2002.
Peter Aronsson: Automatic Parallelization of Simulation Code from Equation Based Simulation Languages,
2002.
Bourhane Kadmiry: Fuzzy Control of Unmanned Helicopter, 2002.
Patrik Haslum: Prediction as a Knowledge Representation Problem: A Case Study in Model Design, 2002.
Robert Sevenius: On the instruments of governance - A law & economics study of capital instruments in limited liability companies, 2002.
Johan Petersson: Lokala elektroniska marknadsplatser - informationssystem för platsbundna affärer, 2002.
Peter Bunus: Debugging and Structural Analysis of Declarative Equation-Based Languages, 2002.
Gert Jervan: High-Level Test Generation and Built-In Self-Test Techniques for Digital Systems, 2002.
Fredrika Berglund: Management Control and Strategy - a Case Study of Pharmaceutical Drug Development,
2002.
Fredrik Karlsson: Meta-Method for Method Configuration - A Rational Unified Process Case, 2002.
Sorin Manolache: Schedulability Analysis of Real-Time Systems with Stochastic Task Execution Times,
2002.
Diana Szentiványi: Performance and Availability Trade-offs in Fault-Tolerant Middleware, 2002.
Iakov Nakhimovski: Modeling and Simulation of Contacting Flexible Bodies in Multibody Systems, 2002.
Levon Saldamli: PDEModelica - Towards a High-Level Language for Modeling with Partial Differential
Equations, 2002.
Almut Herzog: Secure Execution Environment for Java Electronic Services, 2002.
Jon Edvardsson: Contributions to Program- and Specification-based Test Data Generation, 2002
Anders Arpteg: Adaptive Semi-structured Information Extraction, 2002.
Andrzej Bednarski: A Dynamic Programming Approach to Optimal Retargetable Code Generation for
Irregular Architectures, 2002.
Mattias Arvola: Good to use! : Use quality of multi-user applications in the home, 2003.
Lennart Ljung: Utveckling av en projektivitetsmodell - om organisationers förmåga att tillämpa
projektarbetsformen, 2003.
Pernilla Qvarfordt: User experience of spoken feedback in multimodal interaction, 2003.
Alexander Siemers: Visualization of Dynamic Multibody Simulation With Special Reference to Contacts,
2003.
Jens Gustavsson: Towards Unanticipated Runtime Software Evolution, 2003.
Calin Curescu: Adaptive QoS-aware Resource Allocation for Wireless Networks, 2003.
Anna Andersson: Management Information Systems in Process-oriented Healthcare Organisations, 2003.
Björn Johansson: Feedforward Control in Dynamic Situations, 2003.
Traian Pop: Scheduling and Optimisation of Heterogeneous Time/Event-Triggered Distributed Embedded
Systems, 2003.
Britt-Marie Johansson: Kundkommunikation på distans - en studie om kommunikationsmediets betydelse i
affärstransaktioner, 2003.
No 1024
No 1034
No 1033
FiF-a 69
No 1049
No 1052
No 1054
FiF-a 71
No 1055
No 1058
FiF-a 73
No 1079
No 1084
FiF-a 74
No 1094
No 1095
No 1099
No 1110
No 1116
FiF-a 77
No 1126
No 1127
No 1132
No 1130
No 1138
No 1149
No 1156
No 1162
No 1165
FiF-a 84
No 1166
No 1167
No 1168
FiF-a 85
No 1171
FiF-a 86
No 1172
No 1183
No 1184
No 1185
No 1190
No 1191
No 1192
No 1194
No 1204
No 1206
No 1207
No 1209
No 1225
No 1228
No 1229
No 1231
No 1233
No 1244
No 1248
No 1263
FiF-a 90
No 1272
Aleksandra Tešanovic: Towards Aspectual Component-Based Real-Time System Development, 2003.
Arja Vainio-Larsson: Designing for Use in a Future Context - Five Case Studies in Retrospect, 2003.
Peter Nilsson: Svenska bankers redovisningsval vid reservering för befarade kreditförluster - En studie vid
införandet av nya redovisningsregler, 2003.
Fredrik Ericsson: Information Technology for Learning and Acquiring of Work Knowledge, 2003.
Marcus Comstedt: Towards Fine-Grained Binary Composition through Link Time Weaving, 2003.
Åsa Hedenskog: Increasing the Automation of Radio Network Control, 2003.
Claudiu Duma: Security and Efficiency Tradeoffs in Multicast Group Key Management, 2003.
Emma Eliason: Effektanalys av IT-systems handlingsutrymme, 2003.
Carl Cederberg: Experiments in Indirect Fault Injection with Open Source and Industrial Software, 2003.
Daniel Karlsson: Towards Formal Verification in a Component-based Reuse Methodology, 2003.
Anders Hjalmarsson: Att etablera och vidmakthålla förbättringsverksamhet - behovet av koordination och
interaktion vid förändring av systemutvecklingsverksamheter, 2004.
Pontus Johansson: Design and Development of Recommender Dialogue Systems, 2004.
Charlotte Stoltz: Calling for Call Centres - A Study of Call Centre Locations in a Swedish Rural Region,
2004.
Björn Johansson: Deciding on Using Application Service Provision in SMEs, 2004.
Genevieve Gorrell: Language Modelling and Error Handling in Spoken Dialogue Systems, 2004.
Ulf Johansson: Rule Extraction - the Key to Accurate and Comprehensible Data Mining Models, 2004.
Sonia Sangari: Computational Models of Some Communicative Head Movements, 2004.
Hans Nässla: Intra-Family Information Flow and Prospects for Communication Systems, 2004.
Henrik Sällberg: On the value of customer loyalty programs - A study of point programs and switching costs,
2004.
Ulf Larsson: Designarbete i dialog - karaktärisering av interaktionen mellan användare och utvecklare i en
systemutvecklingsprocess, 2004.
Andreas Borg: Contribution to Management and Validation of Non-Functional Requirements, 2004.
Per-Ola Kristensson: Large Vocabulary Shorthand Writing on Stylus Keyboard, 2004.
Pär-Anders Albinsson: Interacting with Command and Control Systems: Tools for Operators and Designers,
2004.
Ioan Chisalita: Safety-Oriented Communication in Mobile Networks for Vehicles, 2004.
Thomas Gustafsson: Maintaining Data Consistency im Embedded Databases for Vehicular Systems, 2004.
Vaida Jakoniené: A Study in Integrating Multiple Biological Data Sources, 2005.
Abdil Rashid Mohamed: High-Level Techniques for Built-In Self-Test Resources Optimization, 2005.
Adrian Pop: Contributions to Meta-Modeling Tools and Methods, 2005.
Fidel Vascós Palacios: On the information exchange between physicians and social insurance officers in the
sick leave process: an Activity Theoretical perspective, 2005.
Jenny Lagsten: Verksamhetsutvecklande utvärdering i informationssystemprojekt, 2005.
Emma Larsdotter Nilsson: Modeling, Simulation, and Visualization of Metabolic Pathways Using Modelica,
2005.
Christina Keller: Virtual Learning Environments in higher education. A study of students’ acceptance of educational technology, 2005.
Cécile Åberg: Integration of organizational workflows and the Semantic Web, 2005.
Anders Forsman: Standardisering som grund för informationssamverkan och IT-tjänster - En fallstudie
baserad på trafikinformationstjänsten RDS-TMC, 2005.
Yu-Hsing Huang: A systemic traffic accident model, 2005.
Jan Olausson: Att modellera uppdrag - grunder för förståelse av processinriktade informationssystem i transaktionsintensiva verksamheter, 2005.
Petter Ahlström: Affärsstrategier för seniorbostadsmarknaden, 2005.
Mathias Cöster: Beyond IT and Productivity - How Digitization Transformed the Graphic Industry, 2005.
Åsa Horzella: Beyond IT and Productivity - Effects of Digitized Information Flows in Grocery Distribution,
2005.
Maria Kollberg: Beyond IT and Productivity - Effects of Digitized Information Flows in the Logging
Industry, 2005.
David Dinka: Role and Identity - Experience of technology in professional settings, 2005.
Andreas Hansson: Increasing the Storage Capacity of Recursive Auto-associative Memory by Segmenting
Data, 2005.
Nicklas Bergfeldt: Towards Detached Communication for Robot Cooperation, 2005.
Dennis Maciuszek: Towards Dependable Virtual Companions for Later Life, 2005.
Beatrice Alenljung: Decision-making in the Requirements Engineering Process: A Human-centered
Approach, 2005
Anders Larsson: System-on-Chip Test Scheduling and Test Infrastructure Design, 2005.
John Wilander: Policy and Implementation Assurance for Software Security, 2005.
Andreas Käll: Översättningar av en managementmodell - En studie av införandet av Balanced Scorecard i ett
landsting, 2005.
He Tan: Aligning and Merging Biomedical Ontologies, 2006.
Artur Wilk: Descriptive Types for XML Query Language Xcerpt, 2006.
Per Olof Pettersson: Sampling-based Path Planning for an Autonomous Helicopter, 2006.
Kalle Burbeck: Adaptive Real-time Anomaly Detection for Safeguarding Critical Networks, 2006.
Daniela Mihailescu: Implementation Methodology in Action: A Study of an Enterprise Systems Implementation Methodology, 2006.
Jörgen Skågeby: Public and Non-public gifting on the Internet, 2006.
Karolina Eliasson: The Use of Case-Based Reasoning in a Human-Robot Dialog System, 2006.
Misook Park-Westman: Managing Competence Development Programs in a Cross-Cultural OrganisationWhat are the Barriers and Enablers, 2006.
Amra Halilovic: Ett praktikperspektiv på hantering av mjukvarukomponenter, 2006.
Raquel Flodström: A Framework for the Strategic Management of Information Technology, 2006.
No 1277
No 1283
FiF-a 91
No 1286
No 1293
No 1302
No 1303
No 1305
No 1306
No 1307
No 1309
No 1312
No 1313
No 1317
No 1320
No 1323
No 1329
No 1331
No 1332
No 1333
No 1337
No 1339
No 1351
No 1353
No 1356
Viacheslav Izosimov: Scheduling and Optimization of Fault-Tolerant Embedded Systems, 2006.
Håkan Hasewinkel: A Blueprint for Using Commercial Games off the Shelf in Defence Training, Education
and Research Simulations, 2006.
Hanna Broberg: Verksamhetsanpassade IT-stöd - Designteori och metod, 2006.
Robert Kaminski: Towards an XML Document Restructuring Framework, 2006
Jiri Trnka: Prerequisites for data sharing in emergency management, 2007.
Björn Hägglund: A Framework for Designing Constraint Stores, 2007.
Daniel Andreasson: Slack-Time Aware Dynamic Routing Schemes for On-Chip Networks, 2007.
Magnus Ingmarsson: Modelling User Tasks and Intentions for Service Discovery in Ubiquitous Computing,
2007.
Gustaf Svedjemo: Ontology as Conceptual Schema when Modelling Historical Maps for Database Storage,
2007.
Gianpaolo Conte: Navigation Functionalities for an Autonomous UAV Helicopter, 2007.
Ola Leifler: User-Centric Critiquing in Command and Control: The DKExpert and ComPlan Approaches,
2007.
Henrik Svensson: Embodied simulation as off-line representation, 2007.
Zhiyuan He: System-on-Chip Test Scheduling with Defect-Probability and Temperature Considerations,
2007.
Jonas Elmqvist: Components, Safety Interfaces and Compositional Analysis, 2007.
Håkan Sundblad: Question Classification in Question Answering Systems, 2007.
Magnus Lundqvist: Information Demand and Use: Improving Information Flow within Small-scale Business
Contexts, 2007.
Martin Magnusson: Deductive Planning and Composite Actions in Temporal Action Logic, 2007.
Mikael Asplund: Restoring Consistency after Network Partitions, 2007.
Martin Fransson: Towards Individualized Drug Dosage - General Methods and Case Studies, 2007.
Karin Camara: A Visual Query Language Served by a Multi-sensor Environment, 2007.
David Broman: Safety, Security, and Semantic Aspects of Equation-Based Object-Oriented Languages and
Environments, 2007.
Mikhail Chalabine: Invasive Interactive Parallelization, 2007.
Susanna Nilsson: A Holistic Approach to Usability Evaluations of Mixed Reality Systems, 2008.
Shanai Ardi: A Model and Implementation of a Security Plug-in for the Software Life Cycle, 2008.
Erik Kuiper: Mobility and Routing in a Delay-tolerant Network of Unmanned Aerial Vehicles, 2008.
Fly UP