An Energy-Efficient Transmission Power Control Protocol for
Cooperative Robotics
Except where reference is made to the work of others, the work described in this
thesis is my own or was done in collaboration with my advisory committee. This
thesis does not include proprietary or classifled information.
Arthi Kothandaraman
Certiflcate of Approval:
Stuart Wentworth
Associate Professor
Electrical and Computer Engineering
Thaddeus Roppel, Chair
Associate Professor
Electrical and Computer Engineering
Shiwen Mao
Assistant Professor
Electrical and Computer Engineering
George T. Flowers
Dean
Graduate School
An Energy-Efficient Transmission Power Control Protocol for
Cooperative Robotics
Arthi Kothandaraman
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
December 19, 2008
An Energy-Efficient Transmission Power Control Protocol for
Cooperative Robotics
Arthi Kothandaraman
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Arthi Kothandaraman, daughter of A. Kothandaraman and S. Lavanya Veena,
was born on October 11th, 1984, in Madras, India. She entered Anna University
in June 2002, and graduated First Class with a Bachelor of Engineering degree in
Electronics and Communication Engineering in May 2006. In August 2006, she began
working towards a Master of Science degree in the Department of Electrical and
Computer Engineering at Auburn University.
iv
Thesis Abstract
An Energy-Efficient Transmission Power Control Protocol for
Cooperative Robotics
Arthi Kothandaraman
Master of Science, December 19, 2008
(B.E., Anna University, 2006)
63 Typed Pages
Directed by Thaddeus Roppel
Severe energy constraints inherent in multi-robot networks dictate that com-
munication be performed as e?ciently as possible to enable longer network lifetime
and successful task execution. Therefore, energy-aware communication protocols are
necessary for network longevity. A number of energy-oriented protocols for mobile
ad-hoc networks (MANETs) are proposed in the literature. However, the compu-
tational intensity and generic nature of these protocols render them unsuitable for
cooperative robotic networks. In this thesis, a Transmission Power Control Protocol
(TPCP) to enhance the energy e?ciency and network lifetime of an IEEE 802.11g-
based cooperative robotic ad-hoc network is presented. The proposed protocol varies
the transmission range of a node to exclusively accommodate an independent node?s
neighbor set. Such a scheme is simple, preserves connectivity, and allows low power
transmissions. Simulations were performed to compare the energy consumption of
the network with the conventional flxed transmission range and TPCP approaches.
v
Simulation results indicate that the proposed algorithm increases network lifetime by
more than 20%.
vi
Acknowledgments
I am deeply indebted to Dr. Roppel for his time, advice, understanding and
patient encouragement through the winding journey towards this thesis. I owe many
thanks to Dr. Agrawal, Dr. Wentworth and Dr. Mao for their guidance and accep-
tance to serve on my thesis committee. I would like to express my heartfelt gratitude
to all the people who have made the completion of this thesis possible: Chris Wilson,
for the long hours he spent in bringing me up to speed on the CRR SARA project.
Yogesh Kondareddy, for his invaluable pointers on the technical aspects of this work.
Sandeep Neeli, for being there for me through it all. My family, for their unwavering
faith in me and for their steadfast support in all my endeavors. And last, but never
the least, a flnal word of thanks to the Almighty for guiding me thus far.
vii
Style manual or journal used Institute of Electrical and Electronic Engineers
Journal Style (together with the style known as \aums").
Computer software used Matlab 7:0, Microsoft Word 2003, LATEX.
viii
Table of Contents
List of Figures xi
1 Introduction 1
2 Literature Review 4
2.1 Communication in Cooperative Robotic Networks . . . . . . . . . . . 4
2.1.1 Inter-robot communication issues . . . . . . . . . . . . . . . . 5
2.1.2 Mobile ad-hoc networks . . . . . . . . . . . . . . . . . . . . . 6
2.2 Transmission power control in ad-hoc networks . . . . . . . . . . . . 8
2.2.1 Trade-ofis in transmission power control . . . . . . . . . . . . 8
2.2.2 Transmission power control in the literature . . . . . . . . . . 10
2.2.3 Limitations of current approaches . . . . . . . . . . . . . . . . 13
2.3 Cooperative Robotics Research at Auburn University . . . . . . . . . 14
2.3.1 Laboratory environment . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Robot design . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.3 Cooperative operation . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4 Communication network . . . . . . . . . . . . . . . . . . . . . 16
3 The Transmission Power Control Protocol 17
3.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Transmission Power Control Protocol (TPCP) . . . . . . . . . . . . . 19
3.2.1 Basic concept . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 Description of the proposed algorithm . . . . . . . . . . . . . 22
4 Experimental Results 26
4.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5 Conclusions 39
5.1 Contribution to the Field of Communication in Cooperative Robotics 40
5.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . 40
Bibliography 41
Appendices 45
ix
A Matlab Source Code 46
A.1 Immobile Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.2 Mobile Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
A.3 Energy Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
A.4 Discretized Energy Function . . . . . . . . . . . . . . . . . . . . . . . 50
x
List of Figures
2.1 Network Connectivity (a) Low transmission range (b) High transmission
range. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Limitations of the PARP/PARO approaches. . . . . . . . . . . . . . . . 11
2.3 Connex 400xm-bt motherboard and wiflstix used for communication . . . 15
3.1 Linear topology of four nodes with flxed transmission range. . . . . . . . 20
3.2 Linear topology of four nodes with adjusted transmission range. . . . . . . 21
3.3 Position of C every ?t seconds. . . . . . . . . . . . . . . . . . . . . . . 21
3.4 Snapshot of Node A?s transmission range every ?t seconds. . . . . . . . . 22
3.5 Flowchart of TPCP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1 Variation of the aggregate energy in a stationary network. . . . . . . . . . 28
4.2 Variation of aggregate network energy with time in a mobile network with
flxed transmission range and TPCP approaches. . . . . . . . . . . . . . . 29
4.3 Variation of the aggregate energy in a mobile network. . . . . . . . . . . 30
4.4 Variation of the aggregate energy in a mobile network with difierent radio
propagation models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.5 Histogram of critical transmission ranges in a 50-node stationary network. 32
4.6 Histogram of critical transmission ranges in a 20-node mobile network. . . 33
4.7 Histogram of discrete critical transmission ranges in a 20-node mobile network. 34
4.8 Variation of aggregate network energy with node density in a mobile network
with flxed transmission range and flve-level discrete critical transmission
range approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
xi
4.9 Five-level discrete transmission ranges. . . . . . . . . . . . . . . . . . . . 36
4.10 Variation of aggregate network energy with node density in a mobile network
for difierent levels of discretization. . . . . . . . . . . . . . . . . . . . . 37
4.11 Variation of aggregate energy spent with number of transmitted packets in
a mobile network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
xii
Chapter 1
Introduction
The past few decades have seen a sea change in the way telecommunications takes
place. Advancement of wireless communications, coupled with the evolution of sensor
technology, has aided the growth of a new fleld of robotics research termed as mobile
robotics. Mobile robots have a plethora of applications ranging from lunar sample
collection [17] to carpet cleaning [21]. Of these, multi-robot exploration of unknown
environments is a very interesting fleld of research. Such multi-agent systems not
only speed-up complex tasks, but also increase robustness and eliminate single-point
failures.
A recent development in mobile robotics is that of teams of autonomous robots
collaborating to accomplish a pre-determined task. Such a network of autonomous
robotic nodes is referred to as a collaborative or cooperative robotic network. These
autonomous robot networks might be deployed for tasks that vary in complexity
and dangerousness from simple surveillance or target location to building composite
systems or traversing landmines. This thesis focuses on search and rescue operations
by a multi-agent robot network.
The dictionary deflnes collaboration as two or more entities working together
with a common objective, while sharing information and aiding each other in achiev-
ing the common end goal. Often, collaborative endeavors of distributed systems prove
to be more successful and satisfactory than dedicated purpose-oriented attempts of
1
centralized systems with little or no information exchange [20]. This makes cooperat-
ing multi-robot systems a popular choice for exploratory applications such as military
reconnaissance [11] or search and rescue operations [12]. Cooperative robot networks
ofier the possibility to handle diverse capability. The inherent system redundancy in
multi-agent network increases their robustness, and their potential for parallel task
execution paves way for superior performance. The design of such multi-robot sys-
tems is not a trivial task because there are many trade-ofis involved in the flnal design
solution.
E?cient, reliable communication is one such signiflcant component of a good
cooperative robot network because exchange of information is essential to the success
of collaborative missions. Search and rescue operations on an unknown terrain that
may or may not have a communication infrastructure call for a network on-the- y or
a mobile ad-hoc network (MANET). In an autonomous robot network, the deployed
robots form an ad-hoc network among themselves. Each robot in the network acts
both as a host and a router, performing information processing as well as forwarding
information. Such robotic nodes usually have severely restricted power supply and
communication bandwidth. Therefore, energy awareness becomes a necessary feature
in any communication protocol considered for such networks.
There has been extensive research on the topic of energy-aware protocols for com-
munication over MANETs in recent times. Nevertheless, the protocols proposed in
the literature fail to take into account the special properties of a multi-robot network
such as cooperative communication and potentially predictable mobility. Moreover,
the proposed protocols tend to overhaul entire chunks of existing infrastructure or are
highly complex to implement. Such implementation is neither practical nor feasible in
2
a mobile robotic node where there is constant tug-of-war between power resources al-
located for task execution and communication. Another unacceptable tradeofi made
in typical power-e?cient protocols is network connectivity. In a cooperative robot
network that might span a wide area, connectivity of nodes is crucial to successful
task completion. In order to meet the unique requirements of a cooperative robot
network, this thesis presents a simple energy-e?cient Transmission Power Control
Protocol (TPCP) to improve the network lifetime, while maintaining the connectiv-
ity in an IEEE 802.11g-based ad-hoc cooperative robot network.
The remainder of this thesis is organized as follows: Chapter Two gives an
overview of communication in cooperative robotic networks. The TPCP algorithm
is described in Chapter Three. Chapter Four discusses the experiments performed
and the results obtained. A summary of the thesis, conclusions, and suggestions for
future work are presented in Chapter Five.
3
Chapter 2
Literature Review
\...cooperative mobile robotic systems have the potential for reducing the
need for human presence in dangerous applications" [30]
\...multiple-robot systems can accomplish tasks that no single robot can
accomplish, since ultimately a single robot, no matter how capable, is
spatially limited." [5]
2.1 Communication in Cooperative Robotic Networks
A cooperative robotic communication network is one in which a team of robots
perform locally optimal actions and collaborate via information exchange to arrive at
a globally optimal task completion state. In [23], the authors experimentally demon-
strate that task-sharing improves performance signiflcantly. A simple box-pushing
task that is di?cult for a single robot becomes relatively easier for two autonomous
cooperating robots equipped with sensing, control and communication behaviors. [24]
explores cooperative communication in the context of robot exploration. The authors
deflne cooperative communication in terms of improving quality of wireless commu-
nication in the network. They present a comparison of average power consumption in
4
a standard and a cooperative wireless network of robots and suggest that cooperating
networks might in fact, have better network performance.
Cao et al [5] characterize three major types of robotic interaction, namely, in-
teraction via environment, sensing and communications. Robotic communication is
typically categorized as explicit or implicit [29]. Implicit communication is usually the
result of an individual robot?s perception of its environment. Explicit communication
on the other hand, is the efiect of deliberate transmission and reception of informa-
tion over a communication network. Explicit communication relies on an underlying
wireless communication mechanism [35] such as the IEEE 802.11 family of wireless
local area network (WLAN) standards [27].
2.1.1 Inter-robot communication issues
In the early days of robotics research, wireless communication on robots consisted
of infrared (IR) technology owing to its low cost. Infrared systems were plagued
by several deflciencies such as poor communication rate and quality (rain efiect),
short communication range and inability to pass through obstacles. A more preferred
communication mobile robot communication design involves Radio Frequency (RF)
technology, using which robots can communicate over point-to-point wireless links
or broadcast over the entire network. The frequency hop spread spectrum (FHSS)
and direct sequence spread spectrum (DSSS) modulation technologies are utilized at
the license-free Industrial Scientiflc Medical (ISM) band (2.4 GHz). The advent of
Internet-like networks has incited researchers to explore wireless LAN (IEEE 802.11),
Bluetooth standards, and ad-hoc networking mode in mobile robot systems [41].
5
Wang et al.[41] discuss the relative merits of ad-hoc networking for mobile robots
and analyze some performance metrics. Multiple mobile robots deployed for dis-
tributed sensing and exploration would typically have low power wireless transceivers
whose range is only su?cient to allow direct communication with their immediate
neighbors. This means that the information packet would need to traverse multiple
hops before reaching its destination. Also, a single centralized point of control leads to
poor fault tolerance and low robustness. Infrastructure for a mobile communication
system might be unavailable or destroyed in the unpredictable and unknown envi-
ronment that the mobile robots are deployed in. These constraints render multi-hop
ad-hoc networks the obvious choice for collaborative mobile robots.
2.1.2 Mobile ad-hoc networks
A mobile ad-hoc network (MANET) is an autonomous collection of wireless mo-
bile nodes that communicate over bandwidth-constrained wireless links. The network
is decentralized and all network activity including topology discovery and message
delivery must be executed by the nodes themselves. The distinctive features of a
MANET are:
Autonomous mobile terminal Each mobile terminal in a MANET has basic pro-
cessing capabilities like a host, but it can also perform switching functions as a
router.
Distributed operation In the absence of an infrastructure for the central control
of the network operations, the control and management of the network is dis-
tributed among the terminals.
6
Multihop routing In a MANET, data packets can be delivered from a distant
source to the appropriate destination even when the destination is out of the
direct wireless transmission range of the source. The data packets are forwarded
from source to destination via one or more intermediate nodes which are also a
part of the network.
Dynamic network topology The mobility of nodes in a MANET may cause the
network topology and connectivity to change rapidly and unpredictably with
time. MANET should adapt to the tra?c conditions as well as the mobility
patterns of the mobile nodes. The mobile nodes in the network dynamically
establish routing among themselves as they move about, forming their own
network on the  y.
Fluctuating link capacity Therelativelyhighbit-errorratesofwirelesslinksmight
be more profound in a MANET. The wireless channel over which the nodes com-
municate is subject to noise, fading, and interference, and has less bandwidth
than a wired network.
Light-weight terminals In general, the nodes in a MANET are mobile devices with
little CPU processing capability, small memory size, and low power capacity.
Such devices need optimized algorithms and mechanisms that implement the
computing and communicating functions without much overhead in terms of
data exchange or power loss.
In summary, MANETs are self-organizing and self-conflguring networks that are
inherently distributed. They have no single point of failure and are capable of re-
routing around congested links. Their capability of sending packets of data over short
7
hops helps conserve power. Owing to their several attractive features, MANETs have
become the preferred choice for autonomous mobile robot systems.The IEEE 802.11
standard in ad-hoc mode is the most prevalent MAC protocol for MANETs today
[18].
2.2 Transmission power control in ad-hoc networks
The average MANET today works on a common-range transmission control [4].
That is, the transmission power of the transceiver is preset to a default value regard-
less of the node topology or network conditions. The distance over which the signal
can be heard depends upon the value of transmission power. Consequently, a higher
transmission power enables wireless nodes to communicate over longer distances. The
optimal reception range of a wireless transceiver is not a flxed number. Transmission
range plays a major role in determining the reception range. Efiective transmission
power control is a critical issue in the design and performance of inter-robot commu-
nication.
2.2.1 Trade-ofis in transmission power control
From a network coverage point of view, it might seem that longer transmission
range is better. This does not necessarily hold true. Admittedly, a longer transmission
range reduces the number of hops that a packet needs to transverse in an ad-hoc
network. But it also reduces network capacity and efiectively increases access delay
by increasing the number of nodes that locally compete on the shared channel. In
contrast, short transmission range allows better frequency reuse and longer battery
lifetime [16]. Also, more transmissions can occur in difierent areas of the network at
8
the same time, thereby improving the network throughput for a shorter transmission
range [38]. Since the power consumed by the radio frequency (RF) power amplifler
in a wireless module is directly proportional to the power of the transmitted signal,
the node lifetime is greatly increased by lowering the energy required for transmission
[18].
Figure 2.1: Network Connectivity (a) Low transmission range (b) High transmission range.
There is the caveat that, for a low transmission range, the chances of a network
being partitioned increase. As illustrated in Fig. 2.1, there might be a situation where
a node in one part of the network is unable to reach a destination node in another
part of the network, irrespective of the number of hops. Such network division is
detrimental to the ultimate application of the network.
From the above discussion, it follows that the key is to choose an optimal value
of transmission power such that the network performance is improved in terms of
energy-e?ciency and throughput, while avoiding network partition. The next section
9
provides examples of the various approaches for transmission power control in the
literature.
2.2.2 Transmission power control in the literature
The topic of power control in MANETs has been extensively researched in recent
times. The main objective of transmission power control has been to minimize energy
expenditure for data delivery or to maximize network throughput by channel reuse
mechanisms. Since the focus of this thesis is energy e?ciency, only the literature on
transmission power control for energy conservation will be discussed.
Network scientists primarily target two layers of the OSI model for energy-saving
techniques- the Network Layer and the Data Link Layer [18]. At the Network Layer,
Power-Aware Routing Protocols (PARPs) use energy-based metrics for route selec-
tion. Energy-aware path selection metrics include network connection longevity, node
power variance, per-packet energy consumption, cost per packet and maximum node
cost [39]. Proactive shortest path selection algorithms were the basis of the flrst gener-
ation PARPs. Nevertheless, such algorithms are more suited to stationary networks
due to the control overhead incurred by proactive exchange of routing and power
information with local neighbors.
Alternatively, on-demand routing techniques consume less power by avoiding
such control data exchange overhead. One on-demand routing protocol that used
power consumption to calculate link-weight is Power Aware Routing Optimization
(PARO) [9]. Although PARO minimizes the overall transmission power consumed by
the network, it fails to balance energy consumption among participating nodes.
10
Directional antennas are proposed in [31] to increase network lifetime and con-
serve energy. The scheme uses a metric based on \minimum energy consumed per
packet" to build routes and then schedules node transmissions by maximum weight
matching. Althoughthisschemeisclaimedtobemoreenergy-e?cientwhencompared
to shortest path routing under omni-directional antennas, the single-beam directional
antennas prove to be inadequate for time-sensitive applications as redirection of par-
ticipating antennas cause large delays and increased energy consumption.
Though the PARP/PARO approaches result in energy conservation, their short-
est path selection does not aim for optimality in route selection, leading to below-par
network throughput. For instance, in Fig. 2.2, suppose node A wants to reach B.
According to PARP, the packets meant for B are force-routed via the shortest next
hop, node C, despite B being within the maximum transmission range of A. Also, the
PARP approach does not take into account C?s neighbors that might wish to trans-
mit. This leads to C?s neighbor nodes deferring their transmission until the channel
is free again.
Figure 2.2: Limitations of the PARP/PARO approaches.
11
Although the transmission power is varied in the PARP/PARO approaches, their
drawback is that, at the network layer level, it is not possible to change the channel
reservation. The MAClayeris the obvious choice to enable a powercontrolled medium
access solution. The literature shows that there are two ways in which such a solution
might be achieved. The flrst is a topology control-based approach that aims to reduce
the degree of the node while preserving connectivity. [42] proposes a distributed
algorithm to increase the transmission power based on directional information till a
neighbor node is found in every direction.
In [34], a distributed dual-phase position-based topology control algorithm is pre-
sented. A sparse enclosure graph is built based on broadcasted position information
in the flrst phase. In the next phase, \optimal" links are determined from the value of
a power consumption cost metric that is assigned to the links in the enclosure graph.
[38] et al undertake a graph theoretic approach to compute the critical trans-
mission range for a wireless network, assuming that the locations of the nodes are
known. This model, while allowing full network connectivity, is centralized, rendering
it less practical for implementation in an ad-hoc network.
On the downside, topology control protocols rely on CSMA/CA for shared wire-
less channel reservation and access, signiflcantly reducing throughput, delay and gen-
eral network performance due to the infamous hidden terminal problem [18]. To deal
with this lack of a channel reservation scheme, a second approach to MAC level power
control is the more reflned interference-awareness scheme [18]. Alternative approaches
to transmission power control are clustering [19], joint clustering/TPC protocol [15],
joint scheduling and power control [7].
12
2.2.3 Limitations of current approaches
In summary, contemporary transmission power control approaches utilize one of
the following principles:
x88 Shortest path calculation with the weight of each link in the path being a
function of a power-based metric [31] [15].
x88 Modiflcation of existing MANET MAC protocols to promote lower transmission
power levels in order to increase network capacity and network throughput
[36][26].
x88 Algorithmically or mathematically determining an optimal transmission range
for a given allowable power consumption [7] or connectivity [6, 1, 37, 25].
Despite their apparent advantages, there are some inherent drawbacks in the ap-
proaches described in the literature. Though there are protocols that claim to satisfy
atleastoneofthemostimportantnetworkperformanceimprovementmetrics, namely,
energy conservation or throughput enhancement or network connectivity, there are
none that aim to achieve all three goals. Moreover, most of the approaches are based
on speciflc routing protocols or are dependent on certain underlying mechanisms and
fail to deliver as a standalone solution. Finally, to the author?s knowledge, there
is no transmission range control protocol that caters speciflcally to mobile robotic
networks, whose unique characteristics merit investigation.
13
2.3 Cooperative Robotics Research at Auburn University
The work presented in this thesis is part of the Search And Rescue Algorithms
(SARA) project at Auburn University. This section brie y describes the on-going
project at the Cooperative Robotics Research Laboratory at Auburn University and
its relevance to this thesis.
2.3.1 Laboratory environment
A collaborative team of six robots has been implemented in the laboratory. The
functionality includes on-board processing, mobility and wireless capability. The
laboratory experiment is carried out in a grid of dimensions 16 ft ?8 ft (? 5 m
?2:5 m), with boundaries of cardboard walls. The 5 m long aisle is  anked by three
rooms on either side with openings to serve as doorways. A simple room scenario
was designed for this project. The robots are deployed in predetermined positions at
one end of the room. That is, the initial pose of the robot is assumed to be known.
Maps are exchanged thereafter to update each robot of the location of every other
robot in the network. A stationary target cone is deployed at a random position
when required. The robots perform a collaborative search of the environment for the
stationary target. The robots use two 2800 mAh /7:2 V batteries for operation and
are capable of motion at the rate of 0:5 inch per second (? 0:0381 m/s).
2.3.2 Robot design
On the hardware side, the robots are designed with the following capabilities.
They consist of an on-board Linux OpenEmbedded platform built on a Gumstix
14
Connex 400xm-bt motherboard based on the 400MHz Intel XScale PXA255 processor.
The motherboard features a 64 MB SDRAM and 16 MB Flash Memory. Wireless
connectivity is enabled by a wiflstix expansion board that connects to the Connex
motherboard via the 92-pin bus header. The wiflstix FCC (with wifl antenna) uses
standard 3.5V- 6V input. The on-board Marvell 88W8385 chipset provides IEEE
802.11a/b/g WLAN capability. (The 88W8385 enjoys embedded CPU and on-chip
memory). Fig. 2.3 shows the equipment used in the labarotary.
Figure 2.3: Connex 400xm-bt motherboard and wiflstix used for communication
2.3.3 Cooperative operation
The objective of the robot team is to reconnoiter the area and locate the station-
ary target. Both exploration of the environment and location of the target require
collaboration among the robots. The robots use SONAR to scan the area in order to
identify and avoid obstacles (walls and fellow-robots). A search-and-rescue algorithm
[32] was designed by the CRR team for this purpose. Servo motors control movement
and coordination.
15
2.3.4 Communication network
The six gumstix robots are part of a WLAN (Wireless Local Area Network) with
the flxed server acting as Base Station or Access Point. Due to processing power
constraints, the robots are currently designed to communicate with only the BS and
notpeer-to-peer. Collaborativeroboticscallsforregularcommunicationandexchange
of information between the robots. Since an ad-hoc design is more suitable for real-
world collaborative search-and-rescue operation, an ad-hoc peer-to-peer network is
used in the experimental simulations. When modeling a robotic sensor network, it
is important to note the environmental aspects in terms of communication features
required. Key characteristics of the above scenario can be summarized as follows:
x88 Limited number of robotic nodes.
x88 The nodes need to be fully mobile.
x88 Since the robots are equipped with wi-fl modules capable of operating IEEE
802.11a/b/g, the best technology should be chosen depending on energy con-
straints and other properties of the network.
For the sake of generalization, a random deployment is considered in this work. Keep-
ing in mind that the eventual implementation would be in an outdoor environment,
a more general rectangular area is considered for our experimental purposes.
16
Chapter 3
The Transmission Power Control Protocol
3.1 Objective
According to [2], the fundamental issues that need to be addressed in inter-robot
communication are:
x88 Is communication necessary?
x88 Over what range do we need to communicate?
x88 What information do we need to convey?
x88 Is the communication guaranteed?
Of these, the second issue is the most pertinent to this thesis. Thus, a key issue
in providing cost efiective communication for a mobile robotic network is to flnd a
?su?cient? value of transmission power for each robot to be able to communicate
e?ciently with every other robot in the network.
We have seen in earlier sections that varying the transmission power has two-
pronged efiects. Increasing the transmission power usually results in lesser number
of hops between the sender and the receiver. But this increased connectivity comes
at the price of causing more contention for an already-shared medium and increased
energy consumption [18] [28]. Lowering the transmission power has the opposite
17
efiect of reducing the interference seen by other potential transmitters and lower
power consumption in general, but results in a higher number of hops from source
to destination. Consequently, the usual solution is to flnd an acceptable tradeofi
between connectivity and energy consumption. Connectivity, however, is a critical
issue in cooperative robotics, and cannot be taken for granted.
Hence, the goal is to provide a simple method of variable transmission power con-
trol to conserve energy without sacriflcing connectivity. Moreover, the algorithm put
forth in this thesis is protocol-independent, rendering interoperability and backward-
compatibility a non-issue. Most importantly, the proposed transmission power con-
trol protocol exploits two distinguishing characteristics of collaborative mobile robotic
networks:
Cooperative communication In a collaborative robotic network, the robots re-
ceive frequent updates of each other?s location and position information. This helps
the robots build a global map of the environment based on the individual local maps.
In the context of this thesis, cooperative communication between robots will be de-
flned as data exchange between multiple robots that facilitates better performance of
a task than when performed by an individual robot.
Predictablemobility Collaborativerobotsareusuallydeployedonmission-oriented
tasks. This implies that the mobility is planned to a certain extent and is fairly pre-
dictable. The inherent cooperative communication also helps in estimating the future
position of any single robot. Contrastingly, in common MANETs, mobility models
based on statistical or random patterns are used for evaluating protocols.
18
To the author?s knowledge, no communication protocol aimed at energy conser-
vation via transmission power control takes these unique features of a collaborative
mobile robot network into consideration.
Lastly, mobile robot applications have limited on-board computational capacity,
combined with a severe restriction of power resources. Thus, any communication
model designed for mobile robotic networks need to be simple and easy to implement
without hogging memory, power or computing resources.
3.2 Transmission Power Control Protocol (TPCP)
In this section, the proposed algorithm is explained and the simulation results
are presented. The mobile robots are referred to as nodes frequently in the rest of
the discussion. The basic concept behind the Transmission Power Control Protocol
(TPCP) is presented flrst, followed by a more detailed explanation of the proposed
algorithm.
3.2.1 Basic concept
The proposed algorithm is completely distributed, enabling each robot to vary
its transmission power autonomously. There is no infrastructure or centralized point
of control involved, eliminating the problem of a single point of failure.
Initially, for any topology of ad-hoc networks, each node transmits at a default
power level to achieve the maximum transmission range. This range is set to ensure
maximum connectivity of nodes. Fixing the transmission to the maximum possi-
ble value, however, may not be the most energy-e?cient way to communicate in a
collaborative robot network.
19
Consider Fig. 3.1, where we have assumed a simple linear topology of four im-
mobile nodes. In this scenario, B lies in the transmission radius of A. Hence, B is a
neighbor of A. Similarly, since A and C are within the transmission range of B, they
are considered B?s neighbors. The neighbor set of a node is deflned as the set of all
single-hop neighbors of a node.
Figure 3.1: Linear topology of four nodes with flxed transmission range.
The transmission power level of all four nodes in Fig. 3.1 is set to the default
value, enabling them to cover the same maximum transmission radii. It is obvious
that, strictly speaking, if A reduces its transmission power to, say half its original
value, it can still communicate efiectively with its neighbor, B. By a similar logic, D
can communicate with C with a much smaller fraction of power. Such a scenario is
shown in Fig. 3.2, where A and D have reduced their transmission ranges suitably. It
is important to note that in Fig. 3.2, both A and D still boast the same connectivity
and neighbor set as before. More signiflcantly, the two nodes now use much lesser
energy than before, owing to the lower power levels required for the new contracted
transmission ranges.
It can be argued that the linear topology with stationary nodes used above is
too simplistic to be applicable to real-world scenarios. Therefore, in the following
discussion, movement of nodes is considered. Fig. 3.3 depicts a 3-node topology in
20
Figure 3.2: Linear topology of four nodes with adjusted transmission range.
which C is mobile. Node C moves away from A with a specifled velocity along the
indicated path. Suppose that A is aware of C?s velocity and direction of motion and
that A updates its transmission range every ?t seconds. Node A predicts the location
of C every ?t seconds as shown in Fig. 3.3.
Figure 3.3: Position of C every ?t seconds.
Node A?s initial transmission range is shown in Fig. 3.3. When A wants to
update its transmission range at time t, it calculates the positions of all its neighbors
at t + ?t seconds. Node A then modifles its transmission radius to encompass its
farthest neighbor after ?t seconds. Fig. 3.4 illustrates this mechanism.
Successive snapshots of the network topology and the updated transmission range
of A at t, t + ?t and t + 2?t are shown in Fig. 3.4 (a), (b) and (c) respectively. In
21
Figure 3.4: Snapshot of Node A?s transmission range every ?t seconds.
(a), A has proactively lowered its transmission range just enough to cover position
2 of node C. This is because, the next transmission range update will occur only
after ?t seconds. After ?t seconds, when node A wants to update its transmission
range again, it predicts that C will move out of its transmission range in the next
?t seconds. So, A expands its transmission radius to the maximum possible value
to accommodate C?s movement till C?s departure from A?s coverage area, as shown
in (b). After C has moved out, A contracts the transmission radius to flt only its
now-farthest neighbor, node B, as shown in (c).
This simple strategy to conserve transmission power without losing connectivity
forms the nucleus of the proposed algorithm. The details of the Transmission Power
Control Protocol (TPCP) for Collaborative Robotic Networks are put forth in the
next section.
3.2.2 Description of the proposed algorithm
Before the Algorithm is described it is important to understand the difierent
Phases and the assumptions made in this protocol.
22
Initialization Phase To begin with, all the robotic nodes are deployed either ran-
domly or strategically in the target area. No node has prior information about its
neighbors. Each node broadcasts its initialization data on the network to advertize
its ready-state.
Reconnaissance Phase Each robot scans its surroundings to build a local map
depicting its immediate environment. This map, consisting of the node?s current
position data and perceived environment information, is then broadcast to the group.
Map-building Phase The node then processes the received information to build
a global map, incorporating the relative positions of the other nodes in the network.
This procedure serves to identify a speciflc node?s neighbor set. These maps are
exchanged among all the nodes periodically. At the end of the Map-building Phase
all the nodes would be receiving the maps from their neighbors periodically. This is
called Steady State of the Network. The proposed algorithm is implemented in the
Steady State of the Network. The following steps illustrate the algorithm in detail:
Step 1 In the Map-building Phase, the initial transmission power is set according to
the transmission range speciflcations of 802.11g for a data rate of 54 Mbps. Suppose
that the default transmission range of 802.11g is Tr and the power corresponding to
Tr is PTr. The transmission range is updated every tU seconds.
Step 2 Each node deduces the current coordinates of its neighbors from the most
recently received map. It then calculates the distance between itself and its neighbors
using the location information from the map. Let N represent the set of nodes, NNi
23
represent the set of neighbors of node Ni and dij represent the distance between node
Ni and node Nj. Distance dij is calculated as
dij =
q
(xi ?xj)2 +(yi ?yj)2
where (xi,yi) and (xj,yj) are the coordinates of the sender and receiver node respec-
tively.
Step 3 Obtain the position information of the neighbors from the exchanged map
data. Predict the velocity and direction of motion and calculate the relative velocity
of the neighbors.
Step 4 Recalculate the Efiective Distances, dE of each neighbor from the source
node. Efiective distance, dE is sum of the current distance, d, and the distance a
node?s neighbor would travel in the next tU seconds. The distance travelled in tU
seconds is represented as dU.
dEij = dij +dUij
where dEij represents the efiective distance between Ni and Nj.
Step 5 Choose the maximum distance dEij for each node and calculate the corre-
sponding transmission range. Then calculate the transmission power corresponding
to that transmission range.
24
Step 6 Change the transmission power to the calculated power and repeat the pro-
cess after tU seconds. If a node does not have any neighbors, then set the transmission
power to the default transmission power, PTr corresponding to the range Tr.
A  owchart illustrating TPCP is given below:
Figure 3.5: Flowchart of TPCP.
25
Chapter 4
Experimental Results
In this chapter, the Transmission Power Control Protocol (TPCP) is compared
with the conventional method of flxed transmission range for all the nodes and the
energy e?ciency of the proposed algorithm is studied.
4.1 Simulation Setup
The performance evaluation of the TPCP algorithm is made via simulations using
MATLAB 7.0. In the initial set of experiments, the nodes (robots) are considered
to be stationary. The nodes are randomly deployed in a 1000 m ?1000 m area.
The number of nodes is varied from 1 to 50 in the simulations. Each point on the
graphs is an average of 100 experiments in order to average out the randomness.
In the second set of experiments mobile nodes are considered. To account for the
mobility of the robots, the Random Waypoint Mobility Model is used. The Random
Waypoint Mobility Model is written in MATLAB, the code of which is available in
Appendix A. The velocity of nodes is flxed to be 5 m/s in the experiments. The
option to use variable velocity for each node is also embedded in the code for the
sake of completeness. The transmission power is changed every one second. This
is a variable which can be adjusted according to the situation, the efiect of which
is analyzed later in this section. The default transmission range is considered to be
250 m as it is in the case of IEEE 802.11 nodes. The power corresponding to the
26
Table 4.1: Simulation Parameters
Parameters Value
Area 1000 m ?1000 m
Number of Nodes Varies from 1 to 50
Default Transmission Range 250 m
Mobility Model Random Way Point
Velocity Fixed speed of 5 m/s
Pause time 0 s
Transmission Range Update Interval (?t) 1 s
default transmission range is 281:83 mW. The power required by TPCP is termed as
Critical Transmission Power (CTP). The efiect of external factors has been neglected
in calculating the CTP for a given transmission range so that the desired relation
between transmission power and the value under consideration is highlighted. The
parameters used in the simulation are summarized in Table 4.1.
4.2 Results and Analysis
Fig. 4.1 shows the aggregate energy spent in a stationary network as the number
of nodes is increased. Aggregate energy is deflned as the total energy spent by all nodes
if every node broadcasts one 1000 byte packet with its allocated transmission power.
From the graph, it is clear that the aggregate energy consumed in the TPCP case is
less than when the nodes are broadcasting using the conventional flxed transmission
power approach. As expected, the energy consumed by the flxed transmission range
approach increases linearly with node density. On the other hand, the energy savings
by TPCP is small initially, but increases substantially for higher node densities. In
27
fact, as the number of nodes in the network increases, there is an energy savings of
up to 20%.
0 10 20 30 40 500
0.5
1
1.5
2
2.5x 10
?3
Number of Nodes
Energy (Joules)
Fixed
TPCP
Figure 4.1: Variation of the aggregate energy in a stationary network.
Inthenextsetofexperiments, nodemovementisconsidered. Forasetof20nodes
moving with a constant node velocity of 5 m/s according to the Random Waypoint
Mobility Model, Fig. 4.2 shows the time evolution of the energy consumed in the
simulations. The straight line at about 2:08 mJ is the constant energy consumed
by the flxed transmission power model. It is interesting to note that the chaotic
pattern of energy consumption in TPCP caps at a maximum of 1:90 mJ in this
experiment. Although it is bounded, the TPCP energy consumption seems to have
chaos characteristics; so time evolution does not provide much information about the
process. As the nodes are moving in and out of the transmission ranges of other nodes
28
in the network in a random fashion, it is natural that, according to TPCP, the CTP
changes with the minimum coverage area required to maintain connectivity.
0 200 400 600 800 10001.65
1.7
1.75
1.8
1.85
1.9
1.95
2
2.05
2.1
2.15x 10
?3
Time (Sec)
Energy (Joules)
Fixed
TPCP
Figure 4.2: Variation of aggregate network energy with time in a mobile network with flxed
transmission range and TPCP approaches.
The variation of energy consumption in TPCP with the number of nodes in a
random mobile network is shown in Fig. 4.3. The trend is observed to be similar
to that of a stationary network. This is because the network topology at any given
instant of time in a stop-and-go robotic network is essentially a stationary snapshot
of the nodes between motion. Thus, the energy consumption behavior with varying
number of nodes at any given instant of time is similar in stationary and mobile
networks. It is observed that the energy consumption of the TPCP approach is lesser
than the flxed transmission range approach.
A comparison of TPCP performance using two most popular open-space radio
propagation models is shown in Fig. 4.4. The graph shows the variation of aggregate
29
0 10 20 30 40 500
0.5
1
1.5
2
2.5x 10
?3
Number of Nodes
Energy (Joules)
Fixed
TPCP
Figure 4.3: Variation of the aggregate energy in a mobile network.
energy in a mobile network for the conventional flxed transmission approach and two
difierent radio propagation models. The results indicate that TPCP has better energy
savings with the two-ray ground propagation model (Pr / Pt=d4) than the free-space
propagation model (Pr / Pt=d2) .This can be explained as follows. Suppose that the
transmission range is halved using TPCP. In this case, for a required level of received
signal power with the two-ray and free-space models, the tranmission power need only
be one-sixteenth and one-fourth, respectively. Hence, TPCP gives difierent energy
savings depending on the radio propagation model used.
Fig. 4.5 shows a histogram of the TPCP transmission range with 50 nodes ran-
domly deployed in a 1000 m ? 1000 m area. The histogram indicates that several
nodes could reduce their transmission ranges below the default transmission range of
250 m without compromising network connectivity.
30
0 10 20 30 40 500
0.5
1
1.5
2
2.5x 10
?3
Number of Nodes
Energy (Joules)
Fixed transmission approach
TPCP in Free space model
TPCP in Two ray ground propagation model
Figure 4.4: Variation of the aggregate energy in a mobile network with difierent radio
propagation models.
The critical transmission radius in the simulation of Fig. 4.5 ranges between
150 m and 250 m. This is because the simulation is of a stationary network of
nodes deployed in a uniformly random fashion. As a result, the nodes are spread
out over an area of 1000 m2, conflning the critical transmission radius to a bounded
range determined by the simulation. This prevents TPCP from exploring much lower
values.
In a mobile network, the continuous movement of nodes ensures that neighboring
nodes undergo extremes of proximity with time. That is, there is a possibility that
nodes move much closer or much father than the default transmission radius. This
enables the TPCP mechanism to dynamically change the CTP to much lower values.
For example, in Fig. 4.6, critical transmission radii in the order of tens of meters are
utilized. Fig. 4.6 is a 1000 second simulation run for 20 mobile nodes in which the
31
140 160 180 200 220 2400
2
4
6
8
10
12
Transmission Range (meter)
Frequency
Figure 4.5: Histogram of critical transmission ranges in a 50-node stationary network.
critical transmission range was updated every 1 second resulting in the corresponding
frequency distribution.
The frequency histogram of discrete transmission range levels for a simulation
of 20 mobile nodes for 1000 seconds is shown in Fig. 4.7. The histogram indicates
that, on an average, 25% of the neighbor set existed between 150 m and 200 m. In
fact, 30% of all neighboring nodes required a transmission range lesser than 150 m.
This implies that for all those nodes utilizing 100 m more than strictly necessary,
the energy consumed would be much higher than that required by using TPCP.
In addition, those nodes transmitting over a longer distance would be potentially
increasing the interference seen by other nodes in the network.
The simulations of Fig. 4.6 and 4.7 assume a continuum of transmission ranges.
Generally, varying transmission power levels over a continuous range is not practical.
32
0 50 100 150 200 2500
0.05
0.1
0.15
0.2
0.25
0.3
0.35
Transmission Range (meters)
Frequency
Figure 4.6: Histogram of critical transmission ranges in a 20-node mobile network.
In a real-world environment, it would be more practical to consider discrete trans-
mission power levels. This led to another set of experiments where discrete levels of
CTP are chosen. Here, flve equidistant discrete levels of CTP were chosen between
0 m and 250 m and the node density was varied between 0 and 50. A graph was
plotted between the number of mobile nodes and aggregate energy consumption. It
is noted that though this graph is similar in trend to the one obtained for continuous
variation of CTP Fig. 4.2, the energy consumption using TPCP is slightly more than
it was previously.
The discretization of CTP levels in TPCP causes a slight decrease in power
savings. Consider Fig. 4.8 where the node A has flve discrete CTP levels of 50, 100,
150, 200and250metersrespectively. SupposenodeBhasmovedintothetransmission
region of node A. Here, though B is located at a distance of only 151 m from A, A
33
Figure 4.7: Histogram of discrete critical transmission ranges in a 20-node mobile network.
would still have to increase its transmission radius to 200 m because the discrete CTP
level of 150 m would not be su?cient for communication.
In order to optimize TPCP performance, two difierent degrees of discretization
were considered. In Fig. 4.10, the node density is plotted against energy consumption
with flve and ten difierent levels of CTP. It is observed that the energy consumption
decreases for a higher degree of discretization. It is necessary to flnd an optimal
value of discretization levels. Discretization of critical power transmission levels is
also dependent on the hardware used and the mobility of the nodes in the network.
Hence, the degree of discretization should be chosen such that the power savings has
a signiflcant advantage for the hardware and network under consideration. Also, in
Fig. 4.10, the CTP was updated every ?t = 1 s. Frequent variation of CTP is not
34
0 10 20 30 40 500
0.5
1
1.5
2
2.5x 10
?3
Number of Nodes
Energy (Joules)
Fixed
TPCP
Figure 4.8: Variation of aggregate network energy with node density in a mobile network
with flxed transmission range and flve-level discrete critical transmission range approaches.
a practical option as it is bound to drain more energy than it saves. Care should be
taken while choosing the value of ?t.
The viability of a communication protocol is judged by its applicability in a
real-world scenario. The simulations performed thus far were for the transmission
of a single 1 kbyte packet. To model the utility of the Transmission Power Control
Protocol proposed in this thesis, the robot built at the Cooperative Robotics Research
Laboratory at Auburn University was considered.
In Fig. 4.11, the number of packets sent over the network is plotted against the
energy consumed. As the number of packets of data sent over the network increases, it
is observed that the energy consumed drops signiflcantly; suggesting that power sav-
ings with TPCP is substantial when considered for a longer period of communication.
Each robot in the cooperative robot network has one 2800 mAh battery capped at
35
Figure 4.9: Five-level discrete transmission ranges.
5 V dedicated to SONAR and on-board computer. The wireless network transceiver
can typically use 15 ? 30% of the power of a mobile computer [33]. Suppose 20%
of the total battery power were to be used solely for communication purposes. Also,
assume data is transmitted continuously at a tra?c rate of 54 Mbps. This implies
that 6750 1 kB packets can be sent per second.
Total energy available for communication is (560?10?3 ?5?3600) J = 10080 J.
From the graph, it is observed that the conventional flxed transmission power ap-
proach can support transmission of 12:1?106 data packets with this energy.
On the other hand, using the TPCP approach, a transmission of 15:6 ? 106 data
packets can be sustained by the same battery power.
In other words, the TPCP approach can efiectively support transmission of 3:5?106
data packets more than the conventional approach. This implies, for the assumed
tra?c rate, network lifetime is increased by 28:9%.
The assumed tra?c rate of 54 Mbps is much higher than practical values. Thus, it is
36
0 10 20 30 40 500
0.5
1
1.5
2
2.5
Number of Nodes
Energy (Joules)
Fixed
5 Levels
10 Levels
Figure 4.10: Variation of aggregate network energy with node density in a mobile network
for difierent levels of discretization.
expected that the TPCP will yield even better results in real-world scenarios.
37
Figure 4.11: Variation of aggregate energy spent with number of transmitted packets in a
mobile network.
38
Chapter 5
Conclusions
A simple yet e?cient method to compute and control the energy used for com-
munication in a cooperative robotic network has been presented. The Transmission
Power Control Protocol, referred to as TPCP, was based on the variation of the trans-
mission power of the autonomous nodes in a cooperative robot network. It was shown
that the algorithm supports mobility, preserves connectivity and reduces interference
seen by other nodes in the network.
The transmission range of the nodes was varied according to the position of their
neighbor nodes in the network, making it essetially a proactive protocol. When a
node has a set of neighbors, the transmission range takes the value of its farthest
neighbor, but no more. If the node has no neighbors, the transmission range is
set to the maximum possible value. The transmission power is regularly adjusted
to meet the above transmission range requirement resulting in frequent low power
transmissions. This algorithm reduces the energy usage of the nodes while ensuring
the same connectivity as the conventional approach.
The TPCP has been simulated in Matlabusing the Random Waypoint Mobility
Model to model the node movements. The results suggest that there is above 20% en-
ergy conservation when compared to the conventional approach of flxed transmission
ranges.
39
5.1 Contribution to the Field of Communication in Cooperative Robotics
This thesis has presented, to the author?s knowledge, a novel energy-e?cient
protocol for transmission power control in cooperative robot networks implemented
using Matlab 7.0. There have been few instances in the literature where energy-
awarecooperativerobotcommunicationistreatedfromthestandpointoftransmission
range variation.
This algorithm is difierent from previous algorithms for transmission power con-
trol in that it achieves energy e?ciency without compromising network connectivity
or burdening the on-board processor of a mobile robot with complex computations.
5.2 Suggestions for Future Work
x88 Study the efiect of difierent mobility models on the Transmission Power Control
Protocol (TPCP).
x88 Implement TPCP on the CRR laboratory?s mobile robots.
40
Bibliography
[1] E. Althaus, G. Calinescu, I.I. Mandoiu, S. Prasad, N. Tchervenski and A. Ze-
likovsky, \Power E?cient Range Assignment in Ad-hoc Wireless Networks,"
IEEE Wireless Communications and Networking Conference, New Orleans, USA,
March 2003.
[2] Behavior-based Robotics by Ronald C. Arkin, with a foreword by Michael Arbib,
Intelligent Robots and Autonomous Agents series, MIT Press, Cambridge, Mass.,
1998.
[3] Tucker Balch and Ronald C. Arkin. \Communication in reactive multiagent
robotic systems," Autonomous Robots, 1(1):1{25, 1994.
[4] J. Gomez and A.T. Campbell, \Using Variable-Range Transmission Power Con-
trol in Wireless Ad Hoc Networks," IEEE Transactions on Mobile Computing,
vol. 6, no. 1, pp. 87-99, January, 2007.
[5] Y.U. Cao, A.S. Fukanaga, \Cooperative Mobile Robotics: Antecedents and di-
rections," Autonomous Robots, vol. 4, no. 1, pp. 7-27, March 1997.
[6] Q. Dai and J. Wu, \Computation of Minimal Uniform Range in Ad Hoc Wireless
Networks," Cluster Computing, no. 8, pp. 127-133, 2005.
[7] T. A. Elbatt, S. V. Krihnamurthy, D. Connors and S. Dao, \Power Management
for Throughput Enhancement in Wireless Ad-Hoc Networks," IEEE Interna-
tional Conference on Communications, pp. 1506-1513, 2000.
[8] J. Gomez, \Energy-E?cient Routing and Control Mechanisms for Wireless Ad
Hoc Networks," Ph.D. Thesis, Columbia University, New York, December 2002.
[9] J. Gomez et al., \PARO: Supporting Dynamic Power Controlled Routing in
Wireless Ad Hoc Networks," ACM/Kluwer J. Wireless Networks, vol. 9, no. 5,
pp. 443-60, 2003.
[10] Gumstix Home Page: http://www.gumstix.com/
[11] Hougen, D., Benjaafar, S., Bonney, J., Budenske, J., Dvorak, M., Gini, M.,
et al., \A miniature robotic system for reconnaissance and surveillance," IEEE
international conference on robotics and automation, ICRA, pp. 501-507, 2000.
41
[12] Jennings, J., Whelan, G., and Evans, W., \Cooperative search and rescue with
a team of mobile robots," Proceedings of the IEEE International Conference on
Advanced Robotics, ICAR, pp. 193-200, 1997.
[13] E. S. Jung and N. H. Vaidya, \A Power Control MAC Protocol for Ad Hoc Net-
works," Proceedings of ACM MOBICOM Conference, vol. 1, pp. 36-47, Septem-
ber 2002.
[14] Sun J., \Mobile Ad Hoc Networking: An Essential Technology for Pervasive
Computing," Proceedings of International Conferences on Info-tech and Info-
net, Beijing, China, pp. 316-321, 2001.
[15] Kawadia, V.; Kumar, P.R., \Power control and clustering in ad hoc networks,"
INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Com-
puter and Communications Societies. IEEE , vol.1, no., pp. 459-469 vol.1, 30
March-3 April 2003.
[16] Kawadia, V.; Kumar, P.R., \A cautionary perspective on cross-layer design,"
Wireless Communications, IEEE , vol.12, no.1, pp. 3-11, Feb. 2005.
[17] Klarer P., \Small scale intelligence for lunar exploration," Control Engineering
Practice, vol. 5, no. 6, pp. 859-863, 1997.
[18] M. Krunz, A. Muqattash and S. J. Lee, \Transmission Power Control in Wireless
Ad Hoc Networks: Challenges, Solutions, and Open Issue", IEEE Network, Vol.
18, pp.08, Sept./Oct. 2004.
[19] T.-J. Kwon and M. Gerla, \Clustering with Power Control," Proceedings of IEEE
MILCOM Conference, pp. 1424-28, 1999.
[20] Zheng Liu; Ang, M.H., Jr.; Seah, W.K.G., \Reinforcement learning of cooper-
ative behaviors for multi-robot tracking of multiple moving targets," Intelligent
Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Confer-
ence on , vol., no., pp. 1289-1294, 2-6 Aug. 2005.
[21] C. Luo, S. X. Yang, \A Real-Time Cooperative Sweeping Strategy for Multiple
Cleaning Robots," International Symposium on Intelligent Control, pp. 660-665,
2002.
[22] MANET. IETF mobile Ad-hoc Network Working Group, MANET.
http://www.ietf.org/html.charters/manet-charter.html.
[23] M.J. Mataric, M. Nilsson, and K.T. Simsarian, \Cooperative multi-robot box-
pushing," IEEE/RSJ IROS, pp. 556{561, 1995.
42
[24] McLelland, M.K. Emamian, V. , \Beneflts of Cooperative Communication Ap-
plied to Robot Exploration," Southwest Res. Inst., San Antonio; Aerospace Con-
ference, 2007 IEEE, pp.1-5, 3-10 March 2007.
[25] S. Narayanaswamy, V. Kawadia, R. S. Sreenivas and P. R. Kumar, \Power Con-
trol in Ad-hoc Networks: Theory, Architecture, Algorithm and implementation
of the COMPOW Protocol," Proceedings of the European Wireless. Next Gen-
eration Wireless Networks: Technologies, Protocols, Services and Applications,
pp. 156-162, 2002.
[26] W. Navidi and T. Camp, \Stationary Distributions for the Random Waypoint
Mobility Model," IEEE Transaction on Mobile Computing, vol. 3, n. 1, January-
March 2004. 2007.
[27] O?Hara, B. and Petrick, A. 1999 The IEEE 802.11 Handbook: a Designer?s
Companion. Standards Information Network IEEE Press.
[28] F.J. Ovalle-Martinez, I. Stojmenovic, F. Gracia-Nocetti and J. Solano-Gonzalez,
\Finding minimum transmission radii for preserving connectivity and construct-
ing spanning trees in ad-hoc and sensor networks," Journal of Parallel and Dis-
tributed Computing, Vol. 65, No. 2, pp. 132-141, Feb. 2005.
[29] Parker L. E., \Current state of the art in distributed autonomous mobile
robotics," in Distributed Autonomous Robotic Systems 4, Springer-Verlag
Tokyo, pp 3-12, 2000.
[30] Parker L. E., \ALLIANCE: An architecture for fault tolerant multi-robot coop-
eration," in IEEE Transactions on Robotics and Automation, vol. 14, no. 2, pp
220-240, 1998.
[31] A. Spyropoulos and C. Raghavendra, \Energy E?cient Communications in Ad
Hoc Networks Using Directional Antennas," Proceedings of IEEE INFOCOM,
New York, USA, 2002.
[32] Ray, A., \Cooperative Robotics Using Wireless Communication," M.S. Thesis,
Auburn University, Dec. 2005.
[33] Redi, J. Welsh, B., \Energy-conservation for tactical robot networks," Proc.
IEEE MILCOM 1999, pp. 1429-1433.
[34] Rodoplu, V.; Meng, T.H., \Minimum energy mobile wireless networks," Selected
Areas in Communications, IEEE Journal on , vol.17, no.8, pp.1333-1344, Aug
1999.
[35] Rooker, M. N., Birk, A., \Multi-robot exploration under the constraints of wire-
less networking," Control Engineering Practice, vol. 15, no. 4, pp 435-445, April
2007.
43
[36] D. Saha, S. Roy, S. Bandyopadhyay, T. Ueda and S. Tanaka, \A Power-E?cient
MAC Protocol with Two-Level Transmit Power Control in Ad Hoc Network
Using Directional Antenna ," 5th International Workshop on Distributed Com-
puting, IWDC, India, December 2003.
[37] P. Santi, \The Critical Trasmitting Range for Connectivity in Mobile Ad Hoc
Networks," IEEE Transactions on Mobile Computing, Vol. 4, No. 3, pp. 310-317,
May/June 2005.
[38] M. Sanchez, P. Manzoni, and Z. J. Haas, \Determination of critical transmis-
sion range in ad-hoc networks" Multiaccess Mobility and Teletra?c for Wireless
Communications Workshop, October 1999.
[39] S. Singh, M. Woo, and C. S. Raghavendra, \Power Aware Routing in Mobile Ad
Hoc Networks" Proceedings of ACM MobiCom Conference, pp. 181-90, 1998.
[40] H. Takagi and L. Kleinrock, \Optimal transmission ranges for randomly dis-
tributed packet radio terminals," IEEE Trans. On Commun., vol. 32, no. 3, pp.
246-257, March 1984.
[41] Zhigang Wang, MengChu Zhou, and Ansari, N., \Ad-hoc robot wireless commu-
nication," Systems, Man and Cybernetics, 2003. IEEE International Conference
on , vol.4, no., pp. 4045-4050 vol.4, 5-8 Oct. 2003.
[42] Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M., \Distributed topology con-
trol for power e?cient operation in multihop wireless ad-hoc networks," INFO-
COM 2001.
44
Appendices
45
Appendix A
Matlab Source Code
The MATLAB programs used to simulate the Transmission Power Control Pro-
tocol (TPCP) are presented here.
A.1 Immobile Nodes
This is the code to implement a random scenario of immobile nodes and vary their
transmission range according to the Transmission Power Control Protocol (TPCP)
and plot the graph of actual energy of the network versus the optimal energy of the
network. It also plots the histogram of the critical transmission ranges.
1 clear all;
2 for Number of Nodes = 1:50;
3 % Number of Nodes = 100;
4 % Define the area
5 x max = 1000;
6 y max = 1000;
7
8 % Assign random positions for each node
9 node x axis = ceil(rand(1,Number of Nodes)*x max);
10 node y axis = ceil(rand(1,Number of Nodes)*y max);
11
12 %Initialize the neighbors of all nodes to Zero
13 node neighbors = zeros(Number of Nodes,Number of Nodes,2);
14
15 % Find the neighbors of each node
16 for i = 1:Number of Nodes
17 for j = 1:Number of Nodes
18 distance = sqrt((node x axis(i)?node x axis(j))?2 ...
19 + (node y axis(i)?node y axis(j))?2);
20
21 if(distance<250)
22 node neighbors(i,j,1) = 1;
23 node neighbors(i,j,2) = distance;
24 end
25 end
26 end
27
46
28 % scatter(node x axis,node y axis);
29 node transmission range = zeros(1,Number of Nodes);
30
31 % Find the minimum transmission ranges
32 node transmission range = max(node neighbors(:,:,2),[],2);
33
34 % Set the transmission range of neighborless nodes to zero
35 node transmission range((node transmission range==0)) = 250;
36 % figure(1);
37 % hist(node transmission range,50);
38
39 p = (281*10??3)*((1000*8)/(54*10?6));
40
41 actual node energy = zeros(Number of Nodes,1)+p;
42 optimal node energy = ((node transmission range.?2))*p/(250?2);
43 % optimal node energy = node transmission range*(281*10??3)*
44 %((1000*8)/(54*10?6))/250;
45
46 actual total energy(Number of Nodes) = sum(actual node energy);
47 optimal total energy(Number of Nodes) = sum(optimal node energy);
48
49 end
50 Number of Nodes = 1:50;
51 figure(1);
52 plot(Number of Nodes, actual total energy,Number of Nodes,...
53 optimal total energy);
54 % a = hist(node transmission range,20);
55 % hist(node transmission range,20)
A.2 Mobile Nodes
This is the code to implement a random scenario of mobile nodes using Random
Way Point Mobility model. The transmission range of the nodes are varied according
to the Transmission Power Control Protocol (TPCP) and the graph of actual energy
of the network versus the optimal energy of the network is plotted. This program
uses the user deflned functions, energy function.m and energy function discretized.m
to calculate the optimal energy of the network in continuous as well as discretized
scenarios. These functions are presented later in this section.
1 % Random Way Point Model
2 clear all;
3
4 for temp =1:50
5
6 temp
7 % Specify the Dimensions of the Grid
8 x max = 1000;
47
9 y max = 1000;
10
11 %Specify the Number of Nodes
12 Number of Nodes = temp;
13
14 %Specify the maximum speed
15 Speed Max = 10;
16
17 n = Number of Nodes;
18 final x = ceil(rand(1,n)*x max);
19 final y = ceil(rand(1,n)*y max);
20
21 x axis next = final x;
22 y axis next = final y;
23 % h = plot(x axis next,y axis next,'.');
24 % axis([0 x max 0 y max])
25 % axis square
26 % grid off
27 % set(h,'EraseMode','xor','MarkerSize',5,'Marker','o')
28 status = zeros(1,n);
29 step = 1;
30 k = 1;
31 for i = 0:step:999
32 %Delay
33 %for j = 1:1:10000 end
34 for j = 1:n
35 if (status(j) < step)
36 x axis old(j) = final x(j);
37 y axis old(j) = final y(j);
38 final x(j) = ceil(rand(1,1)*x max);
39 final y(j) = ceil(rand(1,1)*y max);
40 distance(j) = sqrt((final x(j)?x axis old(j))?2 ...
41 + (final y(j)?y axis old(j))?2);
42 % speed(j) = ceil(rand(1,1)*Speed Max); % For Random velocity
43 speed(j) = 5; % For Random velocity
44 status(j) = (distance(j)/speed(j));
45 slope(j) = (final y(j)?y axis old(j))/...
46 (final x(j)?x axis old(j));
47 ? t(j) = 0;
48 end
49 end
50 ? d = ? t.*speed;
51 tempx = x axis next;
52 tempy = y axis next;
53 x axis next = x axis old + (? d).*sqrt(1./(1+slope.?2));
54 y axis next = slope.*(x axis next ? x axis old) + y axis old;
55
56 for j =1:n
57 if ( ((x axis next(j) > x axis old(j)) && ...
58 (x axis next(j) > final x(j))) jj ...
59 ((x axis next(j) < x axis old(j)) && ...
48
60 (x axis next(j) < final x(j))) jj ...
61 ((y axis next(j) > y axis old(j)) && ...
62 (y axis next(j) > final y(j))) jj ...
63 ((y axis next(j) < y axis old(j)) && ...
64 (y axis next(j) < final y(j))) )
65
66 x axis next(j) = x axis old(j) ? ...
67 (? d(j))*sqrt(1/(1+slope(j)?2));
68 y axis next(j) = slope(j)*(x axis next(j) ? ...
69 x axis old(j)) + y axis old(j);
70 end
71 end
72 [a(k) b(k)] = energy function(Number of Nodes, ...
73 x axis next, y axis next);
74
75 k=k+1;
76 ? t = ? t + step;
77 status = status ? step;
78 % drawnow
79 % set(h,'XData',x axis next,'YData',y axis next)
80 end
81 actual energy(temp) = sum(a)/size(a,2);
82 optimal energy(temp) = sum(b)/size(b,2);
83 end
84
85 xx = 1:temp;
86 plot(xx,actual energy,xx,optimal energy);
A.3 Energy Function
1 function [actual total energy, optimal total energy] = ...
2 energy function(n, node x axis, node y axis)
3
4 % clear all;
5 Number of Nodes = n;
6 % Define the area
7 x max = 1000;
8 y max = 1000;
9
10 %Initialize the neighbors of all nodes to Zero
11 node neighbors = zeros(Number of Nodes,Number of Nodes,2);
12
13 % Find the neighbors of each node
14 for i = 1:Number of Nodes
15 for j = 1:Number of Nodes
16 distance = sqrt((node x axis(i)?node x axis(j))?2 + ...
17 (node y axis(i)?node y axis(j))?2);
18 if(distance<250)
49
19 node neighbors(i,j,1) = 1;
20 node neighbors(i,j,2) = distance;
21 end
22 end
23 end
24
25 node transmission range = zeros(1,Number of Nodes);
26
27 % Find the minimum transmission ranges
28 node transmission range = max(node neighbors(:,:,2),[],2);
29
30 % Set the transmission range of neighborless nodes to zero
31 node transmission range((node transmission range==0)) = 250;
32
33 p = (281*10??3)*((1000*8)/(54*10?6));
34
35 actual node energy = zeros(Number of Nodes,1)+p;
36 optimal node energy = ((node transmission range.?2))*p/(250?2);
37
38 actual total energy = sum(actual node energy);
39 optimal total energy = sum(optimal node energy);
A.4 Discretized Energy Function
1 function [actual total energy, optimal total energy] = ...
2 energy function discretized(n, node x axis, node y axis,levels)
3
4 % clear all;
5 Number of Nodes = n;
6 % Define the area
7 x max = 1000;
8 y max = 1000;
9
10 %Initialize the neighbors of all nodes to Zero
11 node neighbors = zeros(Number of Nodes,Number of Nodes,2);
12
13 % Find the neighbors of each node
14 for i = 1:Number of Nodes
15 for j = 1:Number of Nodes
16 distance = sqrt((node x axis(i)?node x axis(j))?2 + ...
17 (node y axis(i)?node y axis(j))?2);
18 if(distance<250)
19 node neighbors(i,j,1) = 1;
20 node neighbors(i,j,2) = distance;
21 end
22 end
23 end
24
25 node transmission range = zeros(1,Number of Nodes);
50
26
27 % Find the minimum transmission ranges
28 node transmission range = max(node neighbors(:,:,2),[],2);
29
30 % Set the transmission range of neighborless nodes to zero
31 node transmission range((node transmission range==0)) = 250;
32 % Discretization
33 c = 0;
34 for i = 1:levels
35 c = c+(node transmission range>i*(250/levels))*(250/levels);
36 end
37 node transmission range = c+(250/levels);
38 p = (281*10??3)*((1000*8)/(54*10?6));
39
40 actual node energy = zeros(Number of Nodes,1)+p;
41 optimal node energy = ((node transmission range.?2))*p/(250?2);
42
43 actual total energy = sum(actual node energy);
44 optimal total energy = sum(optimal node energy);
51