MOBILITY AND COMMUNICATION IN WIRELESS
ROBOT AND SENSOR NETWORKS
By
Yuanteng Pei

A DISSERTATION
Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Computer Science
2011

ABSTRACT
MOBILITY AND COMMUNICATION IN WIRELESS
ROBOT AND SENSOR NETWORKS
By
Yuanteng Pei

Mobility is a primary goal of many wireless communication systems. In recent years, mobile
multi-hop wireless networks, such as mobile wireless sensor networks and wireless robot networks,
have attracted increased attention and have been extensively studied. However, most current research does not consider the interdependence of communication and mobility and much assume
an obstacle-free environment in their problem modeling and solving process.
In this dissertation, we discuss several research topics relevant to the above two issues of communication and mobility in wireless robot and sensor networks. First, we present multi-robot
real-time exploration, which calls for the joint consideration of mobility and communication: it
requires video and audio streams of a newly explored area be transmitted to the base station in a
timely fashion as robots explore the area. Simulations show that our mobility model has achieved
both improved communication quality and enhanced exploration efﬁciency.
Second, we further investigate the above problem with two critical and real-world network
conditions: (1) heterogeneous transmission ranges and link capacities, and (2) the impact of interference. The conditions increase the model complexity but signiﬁcantly inﬂuence the actual
available bandwidth and the required node size in placement. We jointly consider the relay placement and routing with these two critical conditions.

Third, we introduce an online relay deployment paradigm to support remote sensing and control
when mobile nodes migrate farther from the base station in a cost-effective system of mobile
robots, static sensors and relays. A novel multi-robot real-time search method called STAtic Relay
aided Search (STARS) is presented to allow robots to search in a known environment. Its solution
is based on our near-optimal solution to a new variation of the multi-traveling salesman problem:
precedence constrained two traveling salesman (PC2TSP).
Fourth, we propose a heterogenous multi-robot exploration strategy with online relay deployment for an unknown environment called Bandwidth aware Exploration with a Steiner Traveler
(BEST). In BEST, a relay-deployment node (RDN) tracks the FNs movement and places relays
when necessary to support the video/audio streams aggregation to the base station. This problem inherits characteristics of both the Steiner minimum tree and traveling salesman problems.
Extensive simulations show that BEST further enhances the exploration efﬁciency.
While the ﬁrst four topics deal with communication and mobility issues in powerful but expensive robotic systems, the ﬁfth topic focuses on a special type of low cost, limited capability
mobile sensors called hopping sensors, whose unique method of movement makes them suitable
for rugged terrains. We present (1) a distributed message forwarding model called Binary Splitting Message Forwarding (BSMF) and (2) a grid based movement model unique to these hopping
sensors. Simulation shows that our scheme signiﬁcantly reduces the communication overhead and
achieves relatively constant total energy consumption with varying amount of obstructions.
Finally, we discuss the future work directions of this research work. We believe that a heterogeneous mobile platform to support real-time stream transmission by mobile robots, static sensor and
communication devices, have great potential in various civilian and military applications, where
the communication quality of service is critically important, as well as the mobility efﬁciency.

ACKNOWLEDGMENTS
I would like to express my thanks and deep appreciation to my advisor Professor Dr. Matt W.
Mutka. This dissertation cannot be completed without his years of inspiring guidance and encouragement, his major impact on rigorous research attitude, his valuable insights in many discussions,
his generous ﬁnancial support, and his efforts in careful review of paper manuscripts. The Ph.D.
study under Dr. Mutka was part of the most creative and treasured time in my life.
I am also thankful to Dr. Abdol-Hossein Esfahanian, Dr. Ning Xi and Dr. Li Xiao, for their
insightful comments on this dissertation and efforts in serving in my Ph.D. Guidance Committee.
Besides, I am grateful to the computer science and engineering department, the graduate school of
Michigan State University for providing the teaching assistantship and fellowship to support the
research and study.
At a personal level, I am indebted to my parents Xiaoge Pei and Weiwei Ma, for their continuous encouragement to pursue graduate study. Their attitude towards integrity, science, knowledge,
and education signiﬁcantly impact my life. Special thanks go to my wife Wenting Zeng, for all of
her continuous support and encouragement. It was my fortune to meet her here, at the Michigan
State University.

iv

TABLE OF CONTENTS

LIST OF TABLES

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

1

Introduction . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Background . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Wireless Mobile Networks . . . . . . . . . .
1.1.2 Network Quality of Service . . . . . . . . .
1.2 Challenges and Motivations . . . . . . . . . . . . . .
1.2.1 Network QoS Provision in Mobile Networks
1.2.2 Relay Deployment to Maintain Connectivity
1.2.3 Sensor Relocation in Rugged Terrains . . . .
1.3 Structure of the Content . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

1
2
2
4
5
5
7
8
8

2

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 Mobility Models in Wireless Mobile Networks . . . . . . . . . .
2.2 Multi-Robot Coverage and Exploration . . . . . . . . . . . . . .
2.2.1 Multi-Robot Coordination . . . . . . . . . . . . . . . . .
2.2.2 Communication in Multi-Robot Exploration . . . . . . . .
2.3 Teleoperation and Remote Sensing in Robotics . . . . . . . . . .
2.4 Relay Placement in Wireless Networks . . . . . . . . . . . . . . .
2.5 Static Relay Deployment for Multi-Robot Search and Exploration
2.6 Relocations in Wireless Mobile Networks . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

10
10
11
12
13
15
17
18
20

3

Connectivity and Bandwidth Aware Real-Time Exploration in
works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Preliminaries and Motivations . . . . . . . . . . . . . . . . .
3.2 System Model and Problem Formulation . . . . . . . . . . . .
3.2.1 System Model . . . . . . . . . . . . . . . . . . . . .
3.2.2 Problem Formulation . . . . . . . . . . . . . . . . . .
3.3 Connectivity and Bandwidth Aware eXploration (CBAX) . . .
3.3.1 CBAX Overview . . . . . . . . . . . . . . . . . . . .
3.3.2 Frontier Robot Placement . . . . . . . . . . . . . . .
3.3.3 Relay Robot Placement with Routing Path Selection .
3.3.4 Position Assignment And Path Generation . . . . . . .
3.3.5 CBAX Enhancement . . . . . . . . . . . . . . . . . .
3.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . .
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

Mobile Robot Net. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

22
22
25
26
29
30
30
34
36
49
52
55
59

4

Stream Aggregation in Heterogeneous Range and Rate Mobile Robot Networks
4.1 Preliminaries and Motivations . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Key Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Environment Model . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Mapping of Range and Rate . . . . . . . . . . . . . . . . . . . . . . .
4.2.4 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Relay Placement and Routing . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 General Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Evaluating Flow Aggregation’s Impact on Relay Number . . . . . . . .
4.4.3 Flow Aggregation in Sending Terminals SN . . . . . . . . . . . . . .
4.4.4 New Layer Relay Placement with Flow Aggregation . . . . . . . . . .
4.4.5 Upper Bound of Approximation Ratio . . . . . . . . . . . . . . . . . .
4.4.6 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Channel Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1 Comparing to Minimum Spanning Tree based Relay Placement . . . .
4.6.2 Comparing to Uniform Range and Rate Relay Placement . . . . . . . .
4.6.3 Evaluating HBSR’s Impact on Mobility Efﬁciency . . . . . . . . . . .
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

62
62
64
65
65
66
67
69
70
71
72
72
73
79
80
85
87
88
89
89
94
95
99

5

STARS: Static Relays for Multi-Robot Real-time Search and Monitoring
5.1 Preliminaries and Motivations . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Main Contribution . . . . . . . . . . . . . . . . . . . . . . . .
5.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 STARS: STAtic Relay aided Search . . . . . . . . . . . . . . .
5.4 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Identify Sensing Positions . . . . . . . . . . . . . . . . . . . .
5.4.2 Identify Relay Positions . . . . . . . . . . . . . . . . . . . . .
5.4.3 Assign the Precedence Constraint . . . . . . . . . . . . . . . .
5.5 Tour Generation by PC2TSP . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Cluster Visiting Positions . . . . . . . . . . . . . . . . . . . . .
5.5.2 Obtain Optimal Single Robot Tour . . . . . . . . . . . . . . . .
5.5.3 Prune and Balance Tours . . . . . . . . . . . . . . . . . . . . .
5.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1 Search with a single or more than two robots . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

100
100
104
105
107
109
110
113
113
114
116
117
118
118
120
126
127

vi

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

5.6.2
5.6.3

5.7
5.8

Enable constant monitoring with static sensor deployment . . . . . . . .
Consider a non-uniform search and transmit interval and relay deploying
time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.4 Leverage pre-existing relays . . . . . . . . . . . . . . . . . . . . . . . .
5.6.5 Leverage extra carried relays to reduce dependency . . . . . . . . . . . .
Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. 128
.
.
.
.
.

128
129
129
130
138

6

Steiner Traveler: Relay Deployment for Remote Sensing in Heterogeneous MultiRobot Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.1 Preliminaries and Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.1.1 Key Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.3 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.3.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.4 BEST: Bandwidth-aware Exploration with a Steiner Traveler . . . . . . . . . . . . 151
6.4.1 BEST with Sufﬁcient Bandwidth . . . . . . . . . . . . . . . . . . . . . . . 151
6.4.2 BEST with Constrained Bandwidth . . . . . . . . . . . . . . . . . . . . . 153
6.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.5.1 Simulation Setup and Parameters . . . . . . . . . . . . . . . . . . . . . . 155
6.5.2 Exploration Efﬁciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.5.3 Comparing to a Solution with Known Environments . . . . . . . . . . . . 160
6.6 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.6.1 Extension with Multiple Relay-deploying Robots . . . . . . . . . . . . . . 161
6.6.2 Towards Traveling Path Aware Relay Deployment . . . . . . . . . . . . . 161
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

7

Hopping Sensor Relocation in Rugged Terrains
7.1 Preliminaries . . . . . . . . . . . . . . . .
7.2 Motivation . . . . . . . . . . . . . . . . . .
7.3 System Model . . . . . . . . . . . . . . . .
7.4 Matching Process . . . . . . . . . . . . . .
7.4.1 Message Forwarding Process . . . .
7.4.2 Path Optimization . . . . . . . . .
7.5 Sensor Migration . . . . . . . . . . . . . .
7.5.1 Grid Based Movement Model . . .
7.5.2 Energy Computation . . . . . . . .
7.6 Performance Evaluation . . . . . . . . . . .
7.7 Summary . . . . . . . . . . . . . . . . . .

vii

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

164
164
166
171
173
173
178
178
178
179
183
184

8

Summary and Proposed Future Research Work . . . . . . . . . . . . . . . . . . . . 185
8.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.2 Proposed Future Research Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

viii

LIST OF TABLES
3.1

Notations in CBAX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2

Notations in Algorithm 1-7 in CBAX. . . . . . . . . . . . . . . . . . . . . . . . . 35

4.1

Modulation rate vs. link bandwidth (capacity) vs. transmission range in 802.11a [1]. 68

4.2

Notations in HBSR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.1

Notations in STARS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.1

Notations in BEST. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

ix

LIST OF FIGURES
1.1

Static and mobile sensors. For interpretation of the references to color in this and
all other ﬁgures, the reader is referred to the electronic version of this dissertation.

3

1.2

Pioneer 3 mobile robot [2]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1

Data ﬂow in a usage scenario of robotic teleoperation [3]. . . . . . . . . . . . . . . 16

3.1

Exploration snapshot of the Garden environment given in Section 3.4. (Nodes are
scaled larger for illustration purpose.) . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2

Robot status in one iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3

Example of bandwidth-constrained relay node placement and routing (Step 1 and
2 out of 4 total steps). (γ=3) Edge weight denotes |FSe | . . . . . . . . . . . . . . . 42

3.4

Example of bandwidth-constrained relay node placement and routing (Step 3 and
4 out of 4 total steps). (γ=3) Edge weight denotes |FSe | . . . . . . . . . . . . . . . 43

3.5

Aggregate ﬂows to nodes with maximal number of fully covered neighbors ﬁrst to
conserve RNs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.6

Simulation results on exploration time. . . . . . . . . . . . . . . . . . . . . . . . . 57

3.7

Environments and exploration time. . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.8

Simulation results on communication quality. . . . . . . . . . . . . . . . . . . . . 60

4.1

Star and the reduction index illustration. In δ(S), the underlined “-1” will be applied when the center is an extra relay we need to place: in placing the new layer
node. It will not be applied when the center is an existing node: in aggregation in
SN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.2

Illustration of relay node placement. (Uniform sending rate rs =3Mbps) . . . . . . 76

4.3

Illustration of relay node placement (Continued). (Uniform sending rate rs =3Mbps) 77

4.4

(a)-(b): Compare relay number to bandwidth aware S-MST: Varied ﬂow sending
rate rs of 2-3Mbps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.5

(a): Compare relay number to bandwidth aware S-MST: Varied ﬂow sending rate
rs of 4Mbps. (b): Obstructive environments. . . . . . . . . . . . . . . . . . . . . . 91

4.6

(a)-(b): Compare relay number to uniform range and rate relay placement (UR2 ):
varied |SN| and distance to BS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

x

4.7

(a)-(b): Compare exploration efﬁciency to UR2 based exploration by total number
of iterations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.8

Stream aggregation for area exploration. . . . . . . . . . . . . . . . . . . . . . . . 96

4.9

Channel sizes in exploration; |FN| as exploration proceeds. . . . . . . . . . . . . . 98

5.1

Two robots search the environment and deploy static relays as they travel along
the paths. The left robot transmits streams to the base station via the center relay
deployed by the right robot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.2

Multiple choices of precedence constraints. . . . . . . . . . . . . . . . . . . . . . 123

5.3

Shared relay pruning and vertex transfer. . . . . . . . . . . . . . . . . . . . . . . . 123

5.4

Invalid cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

5.5

Compare the search time with optimal under varying width regions (widths: 25-35m).131

5.6

(a) Compare the search time with optimal under varying width regions (widths:
45m). (b) Varied obstacle density from 0% to 25% for 35*50 case. . . . . . . . . . 132

5.7

(a) Search time in larger regions. (b) Number of visiting positions and relays. . . . 133

5.8

Compare the search time with varying communication ranges and sensing ranges
(50m*75m region). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

5.9

Compare the search time with optimal under varying STI and relay deploying time. 135

6.1

A relay deploying robot supports the stream aggregation for remote control of
frontier nodes in exploration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

6.2

Merge border relay’s pathToBS to new relays. . . . . . . . . . . . . . . . . . . . . 154

6.3

Exploration time compared to CBAX with varying (a) region sizes (b) number of
robots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

6.4

(a) Exploration time compared to CBAX with varying obstacle ratios. (b) Impact
of varying bandwidth constraints on the number of deployed relays. . . . . . . . . 157

6.5

(a)-(b): Number of deployed relays and traveled path length by RDN in BEST,
compared to those results computed with aid of a known environment. . . . . . . . 158

7.1

Hopping sensors we designed deployed near a construction area [4]. . . . . . . . . 166

7.2

Coordinate frame for slope plane. . . . . . . . . . . . . . . . . . . . . . . . . . . 168

7.3

Energy ratio for 0◦ ≤ β ≤ 75◦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

xi

7.4

Binary splitting message forwarding. . . . . . . . . . . . . . . . . . . . . . . . . . 175

7.5

Movement path optimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

7.6

PMM vs. GBMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

7.7

Simulation results: broadcast vs. binary splitting matching. . . . . . . . . . . . . . 181

7.8

Simulation results: number of cells in matching and number of hops in movement. 182

xii

CHAPTER 1
Introduction
Mobility is a primary goal of many wireless communication systems. In the last decade, mobile
multi-hop wireless networks, such as mobile wireless sensor networks and wireless robot networks,
have drawn increased attention and have been extensively studied. However, little current research
has investigated in-depth the inﬂuence of a speciﬁc controllable mobility model on the network
quality of service (QoS), especially when all nodes are highly mobile. In addition, mobility and
communication models in much current research work often assume an obstacle-free environment
where the obstacles can have a signiﬁcant impact on mobility.
This dissertation aims to jointly consider mobility and communication in wireless mobile networks to improve the network quality of service as well as to enhance the mobility effectiveness
and efﬁciency in an obstructive environment. In this chapter, we ﬁrst introduce the background of
wireless mobile networks. Then we present the challenges and motivations for quality communication and effective and efﬁcient mobility in these networks.

1

1.1
1.1.1

Background
Wireless Mobile Networks

Recent decades have witnessed the widespread use of mobile and portable devices, which are likely
to popularize wireless mobile networks. Such networks do not require any wired infrastructure
and its nodes intercommunicate through single hop and multi-hop paths [5]. A mobile node can
be a sensor, a robot or any other mobile device. A sensor is small and relatively inexpensive. It
has limited processing and computing resources. Sensor nodes can sense, measure, and gather
information from the environment. With some local decision process, they are able to transmit the
sensor data to the users [6]. Fig.1.1(a) shows a typical sensor node: a Mica2 mote. It cannot move
by itself, but will have mobility when equipped with additional wheels. Another type of mobile
sensors is called hopping sensors, whose mobility design is more adaptable for rugged terrains or
difﬁcult areas where wheeled mobility cannot perform well. Fig. 1.1(b) shows hopping sensors
in jumping actions. Compared to these limited capability sensor nodes, a robot is usually more
powerful but has higher cost. Equipped with accessories such as robot arms, laptop computers,
laser range ﬁnders, sonars, and cameras, they are able to be teleoperated and perform a range
of complicated tasks such as remote monitoring, reconnaissance, search and rescue in dangerous
terrains. Fig. 1.2 shows a wheel drive Pioneer 3 robot equipped with (i) a robot arm and (ii) a
camera and a laser range ﬁnder.
We categorize wireless mobile networks into two categories: (i) Mobile Ad Hoc Networks
(MANETs) and (ii) Mobile Coordinated Networks (MCNs). A MANET is a collection of mobile
nodes forming a temporary network on the ﬂy, without relying on any ﬁxed infrastructure such as
a base station [8]. MANETs are mostly featured by lack of central coordination, unpredictable and
2

(a) A Mica2 sensor mote [7].

(b) Hopping sensors in jumping action [4].

Figure 1.1. Static and mobile sensors. For interpretation of the references to color in this and all
other ﬁgures, the reader is referred to the electronic version of this dissertation.

(a) Pioneer 3 mobile robot
with a camera and a laser
range ﬁnder.

(b) Pioneer 3 mobile robot with a robot
arm.

Figure 1.2. Pioneer 3 mobile robot [2].

3

varying network topology, and limited available resources. Because it is difﬁcult to characterize
mobility pattern in a speciﬁc way, only general mobility models such as random waypoint have
been proposed.
Mobile Coordinated Networks (MCNs), in contrast to MANETs, are the multi-hop mobile
networks that solely rely on the wireless communication but can be coordinated and controlled by
a ﬁxed base station. While MANETs have been extensively studied, mobile coordinated networks
are relatively new in the network research community. However, MCNs has been the underlying
network model for a number of multi-robot systems in the robotics research community. These
multi-robot systems have extensive applications in surveillance, reconnaissance, search and rescue
missions. As human operators at the base station often need to monitor the powerful and expensive
robot team’s behavior in real-time, and to coordinate the robot team’s actions, MCNs emerges to
be a new paradigm with wide applications in wireless mobile networks.
A crucial advantage of MCNs over MANETs is that the coordination and topology control in
MCNs facilitates QoS provision, which will be discussed in the Section 6.3.1.

1.1.2

Network Quality of Service

Network quality of service (QoS) is a term that speciﬁes the performance level of a service offered
by the network to the user. The aim of QoS provision is to obtain a more deterministic network behavior, for better delivering the information carried by the network and better utilizing the network
resources [8]. Most multimedia and other time or error sensitive applications have QoS requirements. The parameters to characterize the quality of service includes: (i) bandwidth: the rate at
which an application’s trafﬁc must be carried by the network, (ii) latency: the delay that an appli-

4

cation can tolerate in delivering a data packet, (iii) jitter: the variation in latency, and (iv) loss: the
percentage of data loss [9].

1.2
1.2.1

Challenges and Motivations
Network QoS Provision in Mobile Networks

In the recent years, video and audio content has been increasingly popular in today’s digital networks. With proliferation of portable mobile devices such as inexpensive HD camcorders, iPhone
like WiFi-enabled video-chatting phones, and iPad like tablets, efﬁcient and reliable communication for bandwidth consuming and real-time multimedia content in multi-hop wireless network
becomes increasingly interesting, especially when most nodes are highly mobile.
Most current research on QoS provision for mobile networks focuses on the MANETs. Several
QoS aware routing protocols have been proposed to provide assured throughput. However, due to
MANETs’s dynamic and unpredictable nature, it is usually a challenging task. QoS and best effort
routing can only be successfully achieved if the network is “combinatorially stable”: Nodes cannot
move faster than routing updates propagate [10].
There is a more fundamental issue that challenges the QoS provision in mobile network. The
issue has not been addressed by most current work: the mobility pattern and its resulting topology
are usually unpredictable and uncontrollable, even though they have a profound impact on the
QoS. They are often the essential causes for failures to meet QoS requirements and only applying
certain networking measures cannot solve the problem. For example, movement can easily result in
a topology having all broken links to a destination or an over-saturated shared link as a bottleneck.

5

No matter what TDMA allocation method or routing metric a protocol uses, there is little chance
to solve it: the problem is caused by the mobility. However, current QoS provision schemes in
MANETs have no control on the mobility and topologies, which are critical to communication
quality. These schemes cannot make the mobility patterns to have QoS awareness.
Given the signiﬁcance of mobility control over QoS provision, our research improves QoS by
designing QoS-aware mobility patterns in mobile coordinated networks. Multi-robot real-time exploration presents a complex and coordinated mobility model on top of MCNs, where the base
station can control and coordinate a team of mobile robots in a multi-hop fashion. It is complex in
that it has strong requirements for both mobility efﬁciency and communication quality: it requires
bandwidth consuming real-time video and audio streams of a newly explored area be transmitted
to the base station in a timely fashion as robots explore the area. With such communication constraints, the exploration should be completed in minimum time. These requirements calls for joint
consideration of mobility and communication: we need to provide a QoS aware mobility model
that is also efﬁcient in mobility efﬁciency.
Furthermore, multi-hop wireless communication always faces the challenges in dealing with
(1) heterogeneous transmission ranges and link capacities; ii) the impact of interference. These
conditions increase the model complexity but signiﬁcantly inﬂuence the actual available bandwidth
and mobility patterns. Successfully tackling these conditions is critical in obtaining QoS provision
in a coordinated mobile situation.

6

1.2.2

Relay Deployment to Maintain Connectivity

Given the nature of the applications such as reconnaissance, search and rescue missions in earthquake, radioactive, and other dangerous or hostile regions, prior relay deployment or infrastructure
networks are often infeasible when the environment is unknown and relays have to be placed at
the same time as the exploration. However, as robots migrate farther from the base station, smooth
communication to the base station remains a key requirement. Solely relying on mobile robots
to serve as relays may not be a cost-effective approach. Online relay deployment by the mobile
robots (at the same time as robots migrate), is an effective alternative to support the remote sensing
and control.
All robots or a partial of the robot team may have the ability to deploy relays. When all robots
move to search with ability to deploy the robots, the relay deployment introduces the precedence
requirement: the needed relays for stream transmission must be deployed prior to the stream transmission. Therefore, it is possible that one robot’s video transmission will rely on the relay deployed
by another robot, introducing the dependency between the robots. An efﬁcient motion planning
for multiple robots satisfying the precedence and dependency constraint is then challenging.
It is also possible that only one or a partial team of robots has the ability to deploy relays. The
relay deploying robots must track the movement of other frontier robots and effectively deploy
new relays considering the previously deployed relays and the possible bandwidth constraints on
transmitting via both the new relays and/or the previous relays to the base station. An efﬁcient
motion planning for the relay deploying robots is then interesting and challenging since we need
to ﬁrst deﬁne the visiting positions constrained by the communication requirements.

7

1.2.3

Sensor Relocation in Rugged Terrains

Besides QoS provision and motion planning, coping with obstructive environment in mobile networks is another important topic in this dissertation. In a vast array of military and civilian applications, most environments are not obstacle free. Regarding the network composed of mobile robots,
we have focused on the exploration problems to search in an unknown obstructive environment.
Other than the powerful but expensive mobile robots, the other most common devices in wireless
mobile networks are the sensors. In fact, mobile sensor networks have increased in interest to serve
a broad range of applications with their ability to monitor large scale real-world phenomena. In
this dissertation, we focus on hopping sensors, a promising type of sensors whose unique method
of movement is designed to ﬁt the obstructive environment, or rugged terrains.
Hopping sensors is more adaptable for rugged terrains or difﬁcult areas that are challenging
for wheeled mobility. (Figure 7.1). In addition, their diminishing cost enables these inexpensive
sensors to be deployed in large numbers. The applications of hopping sensor networks working in
such areas include weather sensing, environment monitoring, disaster management, and battleﬁeld
surveillance [11]. Along with the beneﬁts of hopping sensor networks there are several challenges
such as imprecise movement, limited power and occasional failure owing to problems regarding
the node, link and global maintenance and communication [12].

1.3

Structure of the Content

The remainder of this dissertation is organized as follows: In Chapter 2 we review the related work.
Chapter 3 introduces the connectivity and bandwidth aware real-time exploration in mobile robot
networks. We discuss the stream aggregation in heterogeneous range and rate mobile robot net8

works in Chapter 4. In addition, Chapter 5 presents the STARS framework, or STAtic Relay aided
Search, to enable online relay deployment for remote sensing in multi-robot real-time search and
monitoring in a known environment. Chapter 6 presents the BEST framework, or the Bandwidthaware Exploration with a Steiner Traveler, to employ a relay deployment node (RDN) to “chases”
a ﬁxed number of frontier robots movement and places relays when necessary to support stream
aggregation in a heterogeneous robot team. Last, in Chapter 7, we propose a hopping sensor relocation scheme in rugged terrains. Finally, a summary and proposed future research work are given
in Chapter 8.

9

CHAPTER 2
Related Work
In this chapter, we ﬁrst survey some general mobility models in MANETs. In the mobile coordinated networks, we then present some existing work related to the controllable mobility model
of multi-robot coverage and exploration. As the mobility model for exploration is pertinent to
teleoperation and remote sensing in robotics, the related work in these topics is also discussed. In
addition, we also reviewed the existing work on relay placement in wireless networks. Besides,
the relevant work of multi-robot search with online relay and sensor deployment to support remote
sensing is presented. Last, mobility issues for relocation purpose in wireless sensor networks are
brieﬂy reviewed.

2.1

Mobility Models in Wireless Mobile Networks

Numerous general mobility models have been proposed for performance evaluation in the dynamic
and uncoordinated MANETs. Three common ones are (i) the random walk mobility model based
on random directions and speeds, (ii) random waypoint mobility mode with pause times between

10

changes in destination and speed, (iii) random direction mobility model that makes mobile nodes
to move to edge of the area before changing direction and speed [13]. Such models have two
major drawbacks. First, the randomness in these models leads to signiﬁcant topology changes as
the nodes migrate, which poses a severe threat in network QoS control. Second, such mobility
models do not ﬁt all mobile applications. They are primarily designed for ad hoc networks where
mobility is unpredictable.

2.2

Multi-Robot Coverage and Exploration

Area coverage is a fundamental topic for mobile robots with extensive real-world applications such
as ﬂoor cleaning, tracking hostile targets, monitoring, and search and rescue missions [14]. In these
problems, a robot or multiple robots are given a bounded area that may have obstacles. Each robot
is equipped with a tool of a shape corresponding to the robot’s sensor or actuator range. The range
should cover all the area. The area coverage has been categorized as a static or a dynamic problem
in [15]. The static version is to converge to a static conﬁguration so that every point in the area
is under the robots “sensing shadow” with minimum number of robots. By contrast, the dynamic
coverage is solved by exploring and covering the environment with motion over time. It requires a
coverage path planning algorithm to have the robots’ footprint (detector range) along the coverage
path yields an area same to the target region in minimum amount of time [16]. By the deﬁnition
of robotic exploration given in [17, 18], the problem of exploration is the same as dynamic area
coverage: the problem of mobile robots to sweep or cover the working area with their sensing area
in minimum amount of time. In this dissertation, we primarily focus on the robotic exploration, or
the dynamic coverage problem.

11

2.2.1

Multi-Robot Coordination

Using multiple robots for exploration signiﬁcantly improves efﬁciency but coordination becomes
essential to avoid visiting duplicate regions. Yamauchi [19] presented a distributed exploration
algorithm and introduces the concept of frontier cells, which are the ones on the border between the
known and unknown regions. In this method, robots independently move to the closest cells, rather
than in a coordinated fashion. Burgard et al. show a frontier cell based coordinated exploration.
The scheme trades off the utilities of unexplored areas and the cost of relocating to the areas. The
coordination is achieved by reducing the utilities based on the number of robots that already headed
towards that area [18]. Although the protocol considers limited communication range, it has no
guarantee on connectivity. Among the above schemes, none of them consider coordination with
QoS awareness.
Another important category of coordination is based on bidding or auction. Simmons et al.
propose a scheme where a central agent is to evaluate the bidding from other robots for the highest
gain. Besides, a market economy based exploration strategy is given in [20] with similar bidding mechanism. Nonetheless, their negotiation procedure is complex. The goal generation is as
well complicated compared with the frontier based one. A spanning tree based dynamic coverage
algorithm is presented in [21] and [14]. A survey of market and bidding based coordination is
presented in [22]. According to the survey, this type approach faces the challenges of effectively
sharing information among all team members and responding quickly to dynamic conditions of the
network.
Coordination for area coverage and exploration is also studied from the control perspective [23–27]. However, none of these schemes has bandwidth awareness or the speciﬁc goal of

12

area exploration. Novel research for coordinating robots and maintaining connectivity of mobile
networks from a distributed control viewpoint is presented in [23, 24]. The authors apply algebraic
graph theory to verify link deletions regarding to connectivity. Tan et al. present a distributed
model for cooperative multi-robot system [25]. With Voronoi diagram and Delaunay triangulations, an autonomous deployment is achieved based on control law to maximize the area coverage.
Additionally, Ogren et al. show a distributed and stable control method to perform a gradient
climbing task for a mobile robot network.

2.2.2

Communication in Multi-Robot Exploration

Communication in multi-robot systems has drawn increased attention [3, 23, 24]. In [28], four
types of routing protocols are compared in an experiment of one mobile robot with several stationary relay nodes. In addition, Dantu et al. [29] incorporated mobility metrics such as directional and
location cue to the Optimized Link State Routing (OLSR) protocol to provide more stable routes.
However, they do not have bandwidth constraints and they do not have control on the mobility.
Furthermore, a network architecture is developed for large mobile robotic environment [30]. However, it is an overlay network based on existing organizational wired network and Internet with
additional mobile robot nodes.
While the problem of multi-robot exploration has been widely studied in [31–36] and various
exploration strategies are compared in [37], little prior work considers the bandwidth constraints
and only some schemes assume limited communication range and attempt to maintain connectivity.
Distributed local random graph, segmentation and hill-climbing based methods in [31–33] explore
the area efﬁciently but provide only intermittent connectivity or assume robots are always in range.

13

To maintain connectivity, “nearest measure” is applied in [34] to let robots tend to stay close
to each other but it cannot be guaranteed. A concept of “comfort zone” is proposed in [35, 38, 39],
where each node monitors the distance to its neighbor and keeps it in a safe range. When the
distance is beyond a safe threshold, the node will change its behavior into tracking the neighbor to
retain connectivity. Such schemes lack systematical analysis of how to share relay robots for placing more frontier ones to enhance efﬁciency. Also, with communication latency and non-uniform
velocities of robots, the “detect and chase” method may lead to a sequence of trace movement and
the resulting topologies need to be proved deadlock-free and invariably-connected.
In addition, an iterative motion planning method in [40] maintains connectivity by rejecting
trajectories that break tree edges in the distributedly-computed minimum spanning tree. However,
its exploration model is different from ours without a base station and may not need to consider
the bandwidth constraint. Besides, a centralized scheme in [36] guarantees connectivity by solely
selecting fully-connected topologies with detecting and recovering from deadlock. Nevertheless,
it only allows nodes to move to their immediate four-neighbor positions in each step and does
not attempt to optimally place relay nodes to improve efﬁciency. In [41], a simple and practical
method on maintaining connectivity is presented and demonstrated in a complex real environment.
However, it does not aim to maintain the connectivity to a particular base station while expending
the team, nor does it try to minimize the exploration efﬁciency.
The problem of relay node placement studied in [42, 43] is also pertinent to maintaining connectivity. Authors in [42] employ bipartite-graph to cover maximum number of mobile nodes using
ﬁxed number of relay nodes in one tier. In [43], the relay sensor placement problem is modeled
as a variant of Steiner tree problem and improved approximation ratio algorithms are provided for
this NP-hard problem without bandwidth consideration. A measurement study in [44] shows a
14

testbed of wireless camera networks. Nevertheless, nodes are static without optimized placement
to reduce relay nodes.
We are not aware of previous work on using node placement in a controlled mobility model to
ensure bandwidth adequacy and connectivity while considering realistic conditions such as interference and heterogeneous communication range and rate.

2.3

Teleoperation and Remote Sensing in Robotics

The idea of remotely controlling mobile robots is not new. Cen et al. [45] deﬁne the information
in a real-time teleoperation system as “Supermedia”, which includes video, audio, haptic, temperature, control commands and other media. Supermedia is distinct from the traditional multimedia
in that certain types of new media are notably sensitive to network delay. The same authors provide a framework for QoS management in teleoperating robotics over overlay networks. Multipath
routing is employed to reduce the transmission latency. However, it is based on wired network
(Internet) for a single robot [46] rather than a multi-hop wireless network.
Additionally, a networking framework for teleoperation in safety, security and rescue robotics
in unstructured environments is given in [3]. Fig. 2.1 shows the data ﬂow are transmitted among
robots, operators, and the control center. The ﬂow has a wide range of contents, priorities, and
bandwidth requirement. The authors argue that teleoperation of mobile robots requires wireless
communication with complex transmission of heterogeneous data. In addition, three levels of
teleoperation are deﬁned: (i) motion level of direct mapping between operator inputs (e.g. joystick)
and robot’s motions, (ii) behavior level: command for short-time functions, (iii) mission level:
high-level goals for a long time autonomy.

15

LRF
gas s and pos
e
enso
r dat
a

po
int
LR
Vid F an
Th eo d p
erm s o
al trea se
im m
ag
es

Robot C

W
ay

l

tro

on

ta
da ose
im p m
ct d ea
Vi F an str
LR ideo
V

kc

tic

ys

Jo

Victim da
ta
map

LRF and pose

Robot A

se
se

po

LRF and pose

po

n

Fa

LR

Robot B

nd
Fa

se

o
dp

LR

Fa

LR

nd
Fa

LR

ose

p
nd

Victim data
map
Mission goals
Control center

Operator station

Figure 2.1. Data ﬂow in a usage scenario of robotic teleoperation [3].
16

2.4

Relay Placement in Wireless Networks

Relay placement has been extensively studied [43, 47–53]. However, there is little previous work
on bandwidth-aware relay placement with the heterogeneous range and rate.
Misra et al. [47] presented a rigorous relay placement framework and gave lower bounds where
relay candidate positions are constrained and sensor/relay range may differ. However, their work’s
aim is to achieve connectivity and survivability. Authors use existing Steiner tree approximation
algorithm based on minimum spanning tree (MST) as input without a heterogeneous bandwidth
constraint for each link based on distance. Besides, a bandwidth aware cooperative relay placement
is given in [53]. However, it does not aim to minimize the number of relays, nor considers more
than two hop relaying or the heterogenous range and rate.
Wang et al. [49] presented an interesting trafﬁc aware relay placement scheme. However,
their work has a different goal of reducing energy consumption rather than satisfying bandwidth
sufﬁciency; the problem is modeled by Euclidean Steiner Minimum Tree problem to reduce the
sum of edge length rather than the number of relays. Similar to [49], a minimum cost pipe network
is computed in [54] to connect many sources to a sink. Their goal is to minimize the total pipe
length cost rather than the number of relays. Besides, there is no capacity limit for each link.
Yang et al. [50] presented a relay placement to improve the network capacity in WiMax networks with heterogeneous ranges. However, the scheme considers only a single hop of relays
between the base station and subscriber stations, which is different from our problem that may
need multi-hop relays. Besides, relays are used differently for cooperative communication, without considering the heterogeneous bandwidth constraint based on ranges for simultaneous stream
aggregation. In [51], a relay placement algorithm was presented to achieve fault tolerance with

17

more than one vertex-disjoint path with heterogeneous range. Similar to other work, bandwidth is
not taken into account.
In [52, 55], a bandwidth aware relay placement is modeled as the Steiner tree problem with γinﬂow constraint to support multi-robot exploration. However, it assumes uniform communication
range and rate. In [56], a joint single base station placement and routing approximation solution is
proposed. However, it has a different goal and does not consider the relay placement problem.
Real-time video and voice stream aggregation has been investigated in multi-hop wireless sensor and camera networks [44,57] to collect rich information about the environments. These systems
have extensive applications in coal mine monitoring [58], search and rescue missions in dangerous
areas, and security surveillance [52]. In [57], real-time voice streams are sent from 20 static sensor
nodes to a sink in a wireless sensor network. In [44], real-time video streams are sent from 15 static
camera nodes to a sink in a wireless mesh network. However, these systems do not particularly
tackle the relay placement problem.

2.5

Static Relay Deployment for Multi-Robot Search and Exploration

A survey on multi-traveling salesman (mTSP) is given in [59] to describe various problem formulations, solution procedures, and real-life applications of mTSP, such as school bus routing,
interview scheduling and mission planning. However, mTSP is to minimize the sum of the traveler tours rather than the maximum of them. Also, mTSP does not consider the precedence or
the dependency between travelers. A comparative analysis of several linear programming formu-

18

lations for asymmetric (single) traveling salesman problem is given in [60]. In [61], extended
formulations for the precedence constrained (single) asymmetric traveling salesman problem are
presented. In [62], a multiple depot, multiple traveling salesman problem is solved by transformation into single asymmetric TSP problem. However, this problem does not have the precedence
constraint. In summary, none of the above work attempts to solve the multiple traveling salesman
with the precedence constraints.
Balas et al. present a class of polynomially solvable (single) traveling salesman problem with
precedence constraints [63]. However, their precedence constraint does not ﬁt our application and
is notably stricter than ours. In [63], a node i must be prior to all i + k nodes given an initial
order, whereas we only require i precedes a subset of nodes. Similarly unnecessary and stricter
precedence constraint is imposed in the multiple traveling salesman problem with time windows
(m-TSPTW) [64]. Besides, we do not have a predeﬁned time window for each node.
There is little previous work on using online relay deployment to support remote sensing and
surveillance with mobile robots and static sensors. Mobile robot search and exploration have been
extensively studied without the consideration of online relay deployment [31–36, 52, 55, 65–69].
Besides, hybrid static sensor and mobile robot systems have been studied in [70–74]. In [73],
authors deploy static mote sensors, RFID (Radio-frequency identiﬁcation) tags, and mobile robots
to guide ﬁre ﬁghters in burning buildings. However, the static sensors are deployed ahead by
humans. Sensors are not used as relays for real-time operation control. In [71], a single robot is
used to assist the sensor network deployment and data collection. However, sensors are not used
to transmit streams from the robot.
An interesting paper by Tan et al. [75] uses both mobile and static sensors to improve the target
detection accuracy. The authors develop a scheduling for movement to minimize average moving
19

distance. However, they have a different goal compared with our problem. The movement path
in [75] is markedly simpler: each mobile sensor moves on a straight line toward a known target
place in the center. One of the most relevant research work is presented in [74], where robots carry
sensors as payload with online deployment. However, sensors are uniformly deployed. They serve
as the navigation guides rather than transmission relays. Similar ideas of using sensors to navigate
robot movement are presented in [70, 72].

2.6

Relocations in Wireless Mobile Networks

Sensor relocation problems are extensively studied in [76–81]. When a sensor node depletes its
energy or fails, sensor coverage holes evolve. Areas with redundant sensors can supply sensors to
be relocated to these holes to maintain coverage.
Grid-based solutions for sensor relocation have been widely proposed [77, 80–82]. Wang,
et al. [80] introduced two kinds of nodes, the grid head and its members, in their model and
adopted a Grid-Quorum approach. Their scheme makes use of some notations. A quorum is
mentioned in [83] as an element in a subset of a given set. In [84], a quorum system is deﬁned
as a collection of sets such that the intersection of any two sets is always non-empty. Grid cells
with redundant sensors are identiﬁed as suppliers. They send an advertisement message to form a
supply quorum. Consumers are grid cells in need of sensors, which send a request message to form
a consumer quorum. However, with the presence of obstructions, supply and consumer quorum
are not guaranteed to intersect on the grid for the matching between the supplier and consumer
cells.
Similarly, [76] deals with the matching and relocation for hopping sensors. However, the issue

20

that potential obstructions hamper the relocation process also remains unsolved. In [85], the problem of clustering sensors under obstructive and inhospitable conditions is addressed. However,
matching and relocation are not speciﬁcally tackled. In Chapter 7, we propose a simple and distributed Grid-Quorum based solution to effectively cope with obstructive environment like rugged
terrains with hopping sensors.
At the same time of our work [86] and thereafter, several related research have been proposed
for relocation of hopping sensors in rugged terrains [87,88]. Kim et. al [87] argues that the shortest
path based scheme suffers from repeated use of sensors in speciﬁc areas, leading to occurrence of
new sensor holes. They propose a new multipath relocation scheme to evenly and fairly distributing
sensor to provide the requested ones to a sensing hole consumer. In addition, the deﬁnition of
regularity is introduced in [88] to depict the ratio of obstructive regions in the whole area. With
regularity deﬁned, the authors proposed a reliability based scheme to relocate sensors.

21

CHAPTER 3
Connectivity and Bandwidth Aware
Real-Time Exploration in Mobile Robot
Networks

3.1

Preliminaries and Motivations

Exploring an environment is one of the fundamental problems in mobile robotics. Recently, multirobot exploration has received increased attention for its notable beneﬁt for enhanced efﬁciency
and robustness [32, 34]. Many application domains of multi-robot exploration, such as surveillance, reconnaissance, search and rescue missions in dangerous areas require robot’s bandwidthconsuming video/audio information from newly-explored area to be reliably and quickly sent back
to an operator at the base station [36].
The reasons for the above transmission requirement are threefold. First, human operators often
need to monitor the robot team’s action and obtain the sensed information immediately. Second,
22

as the current robotic sensing ability is not sufﬁcient to accurately detect complex targets, such
a process should be simultaneously augmented with human recognition [38]. In fact, the use of
human operators as “perceptual sensors” to process camera video is a standard practice for both
UAVs and ground robotics [89]. Third, operators may even need to teleoperate robots promptly
after target discovery or under exceptional circumstances. For instance, when a robot ﬁnds a victim
partially covered by earthquake debris, the operator may teleoperate the robot to move closer to the
target and control the robot arm to remove the obstacle and telediagnose the victim. Thus, limited
robot intelligence may need to be augmented with an operator as a necessary and effective way
to monitor and control a robot team. Reliable and smooth communication is essential in such a
process. Hence, such Multi-Robot Real-Time eXploration (MRRTX), is critical.
MRRTX can be described as follows: A team of n homogenous robots are sent from the base
station (BS) to explore an unknown area. Each robot communicates with limited range by forming
a multi-hop network with all robots and the BS. The question is: how to design a coordinated
exploration strategy for the robot team to explore the area in a minimum amount of time under
the following two constraints? (1) The network is always connected when data is transmitted. ii)
The aggregated consumed bandwidth of data ﬂows from the frontier nodes cannot exceed the link
bandwidth (capacity) when transmitting back to the BS. In fact, many types of real-time streaming
data such as video/audio have a stream ﬂoor rate [46], or a minimum rate to make the stream workable. For example, a typical DVD-quality video stream requires about 5 Mbps of throughput [90].
A link should always provide adequate bandwidth for each ﬂow to meet the ﬂoor rate requirement.
Without these two constraints, disconnected nodes can evolve and the aggregated data ﬂows may
exceed the link bandwidth, leading to considerable data loss and control disturbance.

23

FN

Unexplored
Area

Frontier
Nodes

Relay
RN
Nodes

FN
FN
Explored
Area
FN

RN

Base
Station

RN

FN

Obstacle
(Wall)

Figure 3.1. Exploration snapshot of the Garden environment given in Section 3.4. (Nodes are scaled larger for illustration purpose.)
24

To solve MRRTX, we present Connectivity and Bandwidth Aware eXploration (CBAX). Differing from existing approaches, CBAX is an iterative exploration that divides the problem of the next
round movement path generation and message routing into three subproblems, which are modeled
and solved accordingly by variations of algorithmic and graph-theoretic problems, such as the set
cover problem, the Steiner tree problem, and the linear bottleneck assignment problem (LBAP).
When we solve the bandwidth-constrained relay node placement, we model it as a new variation,
or one with the γ-inﬂow constraint, of the Steiner Minimum Tree Problem with Minimum Number
of Steiner Points and bounded edge length (SMT-MSP) [43,91]. CBAX not only reduces the exploration time compared with recent work [32,36], but also guarantees the adequacy of link bandwidth
and enhances the communication quality. In Fig. 3.1, CBAX is illustrated by an exploration snapshot obtained from our simulation program with the Garden environment given in Section 3.4. The
ﬁgure describes that 4 frontier nodes with 2 relay nodes have explored 56.3% of the area in their
fourth iteration of movement, where all robots with the BS are connected and frontier nodes send
non-overﬂow streams to the base station by the routing paths CBAX generates.
The outline of this chapter is as follows. Related work is described in Section 2. Section 3.2
introduces the system model and the problem formation. In Section 3.3, CBAX’s general procedure
is given, along with the three subproblems and optimizations on the model. Performance evaluation
is in Section 3.4 while Section 3.5 summarizes the chapter.

3.2

System Model and Problem Formulation

Before presenting our solution, the system model and problem formulation are introduced as follows.

25

3.2.1

System Model

Robot Model: Each robot has traveling, communication, and sensing capability. It scans the environment using cameras and acoustic sensors with sensing range rs and communicates with other
nodes with communication range rc by a 802.11 radio, where rc > rs .
Environment and Exploration Model With a Base Station: The exploration begins with the
operator selecting a targeting area, all of whose borders are reachable when robots form a straight
line from BS. The area is modeled by the 2D occupancy map composed of grid cells. The cell size
equals that of a robot. The states of a cell are unvisited, exploring, and explored. An explored cell
can be either free or obstructed. An obstacle does not affect communication but blocks the sensing
range. An unvisited cell denotes the area that has not been reached by the sensing range of robots.
Arriving at their target positions, all nodes are synchronized and start simultaneously to sense the
area and transmit streams back to BS for a ﬁxed sensing and transmitting interval (STI). In STI,
the unvisited grid cells within the range of rs of a node and not blocked by obstacles are changed
to exploring status. After STI, these cells change to explored status since the operator has observed
and detected the targets in STI. The cells that are explored but have at least an unvisited neighbor
cell are called frontier cells and denoted as FC. We mainly focus on how to efﬁciently explore the
area and the issues after the target discovery, i.e., potential teleoperation tasks, are not discussed
here.
Coordinated exploration is executed in an iterative and synchronized way controlled by the BS.
At iteration t, M apt denotes the explored map and T t gives the total time elapsed. Each robot
t
i has a position Pi and is dynamically classiﬁed as a relay node (RN) or a frontier node (FN).

A FN explores a new area while a RN maintains connectivity for FNs with the BS. The robot

26

team size is n with nf n number of FNs and nrn number of RNs. We deﬁne the information
gain of node i in iteration t, or IGt , as the number of unvisited cells that can be explored with
i
a new position Pit . A position conﬁguration is the array of positions of the n robots. Speciﬁcally,
t t
t
pCGt , the position conﬁguration at iteration t is deﬁned as: pCGt = {P1 , P2 , ...Pn }. The set

of all possible pCGt is denoted as P CGt . Each pCGt is associated with a total information
gain, or tIGt , which is the total number of non-overlapped unvisited cells that can be explored
with a new position Pit for each node i. A valid position conﬁguration is the one that satisﬁes
the Constraint I deﬁned below. Besides, P atht is the migrating path of node i from iteration
i
t-1 to t and P atht is the set of P atht for each node i. Similar to [23], we deﬁne a dynamic
i
graph G(t)={V, E(t)} where V denotes the sets of vertices indexed by the set of robots with BS
and E(t) is the edge set representing the time varying set of bi-directional communication links
t
of vertices and (i, j) ∈ E(t) iff dist(Pit , Pj ) ≤ rc (dist(i, j) denotes the straight-line distance

between i and j.)
In addition, we deﬁne a routing conﬁguration by the path array from all FNs back to BS where
the streams traverse. Speciﬁcally, rCGt , the routing conﬁguration at iteration t is deﬁned as
rCGt = {RLt , RLt , ...RLt }, where RLt is the route list, or the sequence of nodes on the routn
1
2
i
ing path from FN i to BS in iteration t. A valid routing conﬁguration is the one satisfying the
Constraint II, or Equation 3.2 deﬁned below. Combining both position and routing conﬁgurations,
we deﬁne the conﬁguration at iteration t as CGt = {pCGt , rCGt }. A valid conﬁguration is the
one that satisﬁes Constraints I & II given below and CGt denotes the set of all valid conﬁgurations
v
in iteration t.
Wireless Communication Model: We analyze the wireless communication in area exploration
with the following properties: (1) The unit-disk communication model is adopted and two nodes
27

i, j can communicate as long as dist(i, j) ≤ rc . (2) All links have a uniform link capacity
Rcapacity and a FN has a uniform ﬂow sending rate Rs for its video/audio streams not less
than their stream ﬂoor rate in STI, where a ﬂow is the combined video and audio streams from a
FN to BS. (3) Streams are sent in a single selected path rather than multiple paths. (4) Interference
between nodes will be analyzed in future work.
Terms

Deﬁnitions

BS
FN, RN
n, nf n , nrn
STI
Flow
rc ,rs
FC
Pit
G(t)
M apt
P atht , P atht
i

Base station.
Frontier node and relay node. FN, RN represent their set.
Number of all robots, number of FN and number of RN.
Sensing and transmitting interval.
Combined video and audio streams from a FN to BS.
Communication range and sensing range.
Set of Frontier cells.
Position of node i in iteration t.
Dynamic graph, G(t) = {V, E(t)}.
Explored map in iteration t.
Moving path of node i and set of all robots moving path from iteration t-1 to t.
Position conﬁguration, array of node positions in iteration t.
Routing conﬁguration, path set of data ﬂows from FN to BS.
Conﬁguration, CGt = {pCGt , rCGt }.
Set of all valid conﬁgurations in iteration t.
Information gain of node i in iteration t: Number of unvisited cells
to be explored.
Total information gain.
Total time elapsed after iteration t; Migration time in iteration t.
Bandwidth ratio.
A uniform maximum link rate.
A uniform ﬂow sending rate from FN.

pCGt
rCGt
CGt
CGt
v
IGt
i
tIGt
T t , mT t
γ in Eq. 3.2
Rcapacity
Rs

Table 3.1. Notations in CBAX.

Constraints I & II: In the STI of each iteration t:
1. Constraint I. The robot team with BS’s network G(t) is connected.

28

2. Constraint II. The aggregated consumed bandwidth cannot exceed the link capacity on each
link of the path from FNs to BS, which can also be expressed as:
e
Rcapacity ≥

f ∈Fe

e
Rconsumed(f )

(3.1)

f represents a ﬂow and Fe denotes all the ﬂows passing through link e. With the properties in our
wireless communication model, equation 3.1 is rewritten as:
e
Rcapacity ≥ γ · Rs

(3.2)

An integer γ, or the bandwidth ratio, denotes the maximum number of ﬂows that can pass through
link e without overﬂowing the link, e.g., γ = 3 when Rs =450KB/s with 11Mbps link; γ = 5 when
Rs =128KB/s with 5Mbps link.
Illustration: When iteration t begins, BS computes CGt and sends Pit and P atht to each node
i
i. When receiving them, i will migrate to the targeting position Pit by path P atht from Pit−1
i
and send the acknowledgement back to the BS when it arrives. mT t , or the migration time in
iteration t is determined by the bottleneck, or the longest moving time among all nodes. After
the BS receives acknowledgements from all nodes, it informs all FNs to enter STI and starts the
stream transmission to the BS by the routes deﬁned in rCGt . Then the human operator can start
to identify targets in STI by monitoring the video/audio sent from FNs. An iteration adjourns with
the completion of STI. Fig. 3.2 also illustrates a robot’s states in exploration.

3.2.2

Problem Formulation

Based on the system model, the major problem is how to explore the whole area for a robot team
with minimum time under the communication constraints I & II. Although the problem can be

29

Migrating
(Waiting for other nodes)
FN: Sensing and transmitting streams
RN: Transmitting streams
Figure 3.2. Robot status in one iteration.
difﬁcult to solve as a whole, our solution leverages a heuristic answer to a subproblem. The
subproblem becomes more tractable but remains non-trivial, since it is further divided into variants
of two NP-hard problems and a polynomially-solvable problem. This subproblem is to ﬁnd a local
optimal conﬁguration in iteration t, or CGt , which has maximal total number of cells explored
lopt
in unit migration time. Formally, the subproblem is: given pCGt−1 , ﬁnd CGt such that:
lopt
tIGt
t
CGlopt = argmax (
t)
CGt ∈CGt mT
v

3.3
3.3.1

(3.3)

Connectivity and Bandwidth Aware eXploration (CBAX)
CBAX Overview

Generally, CBAX attempts to enhance efﬁciency by maximizing the explored area by placing more
robots in frontier areas, while reserving less robots as relay nodes. Additionally we endeavor to
reduce the bottleneck longest distance that robots travel, as it also directly impacts the exploration
time. The problem of ﬁnding CGt in Section 3.2.2 is largely divided into three subproblems:
lopt
• Frontier node placement: Where to place nf n number of FNs in FC to cover maximum
amount of unexplored area? The distances from current positions to new ones are also con30

sidered and modeled in the utility function.
• Relay node placement with routing path selection: How to place minimum number of RNs
in explored area to satisfy the Constraint I,II and select which paths to route ﬂows from FNs
to BS?
• Position assignment and path generation: How to assign each robot with its target position
and generate movement paths to minimize the bottleneck time mT t ?

31

Algorithm 1: General Procedure of CBAX
Input: pCGt−1 , M apt−1 , T t−1 , Robot team size n
Output: CGt , P atht , mT t , T t , M apt
1 nf n ← n

// “tmp” means “temporary” throughout this dissertation

2 while nf n > 0 do
3

FNt ← placeFN(M apt−1 , nf n )

// in Alg. 2

4

rCGt , RNt , nrn ← placeRN selectRoutingPath(FNt )

// in Alg. 3

5

if nf n + nrn ≤ n then
if nf n + nrn < n then

6

pCGt ← placeRemainNode(pCGt−1 , pCGt )

7

// in Alg. 8

break

8

else

9
10

reset FNt , RNt , rCGt , nrn

11

nf n ← nf n − 1

12 Generate migration paths with time: mT t , T t , P atht ← genPath(pCGt−1 , T t−1 ) // in Alg.
7
13 M apt ← search(M apt−1 , CGt )

Alg. 1 illustrates the general procedure of CBAX for each iteration. Initially, nf n is set as
the team size because more FNs normally can cover more area. Given FN positions computed in
line 3, RNs are placed accordingly with routing to relay FNs with BS and nrn is decided. Line
5 checks whether required number of robots nf n + nrn exceeds the ﬁxed team size. If yes, the
algorithm reduces nf n and places FNs and RNs again until it ﬁnds the required number of robots

32

can be satisﬁed. If nf n + nrn < n, then the remaining nodes may be able to move to frontier areas
to explore extra areas where RNs can support the additional ﬂows. In line 12, function genPath is
called to assure that bottleneck distance is minimized when generating movement paths for each
node to reach its target. The map will be updated after nodes arrive at their new positions and enter
STI.
CBAX is a centralized scheme. Although it takes time to synchronize and transmit control
messages to the BS, it ﬁts our model as global topology information is requested by the operator
at the BS anyway for remote monitoring, control, and even teleoperation. More notably, it facilitates graph theoretic modeling and methodically solving the problem. Furthermore, a distributed
approach usually suffers from local suboptimal results, large amount of local data exchange [40],
and non-trivial waiting time for other nodes to broadcast better results [34]. Therefore, CBAX
computes robot’s trajectories at the powerful base station in a safe area to ensure effective control
and monitoring.

33

3.3.2

Frontier Robot Placement

Algorithm 2: Frontier Node Placement placeFN()
Input: M ap as a copy of M apt−1 ; i as a copy of nf n
Output: FNt
1 while i > 0 do
2

q ∗ ← argmaxq∈FC U (q)

3

FNt .add(q ∗ )

4

M ap ← updateLocalMap(q ∗ , M ap)

5

FC ← updateFrontierPosSet(M ap, FC)

6

i←i−1

Our utility function is deﬁned as follows:
U (q) = IGt · e
q
where

d(q) =

θ = max{θ0 · (1 − δ), θth }

(δ =

min

i∈pCGt−1

−

d(q)
θ ,

(3.4)

d(q, i),

size(M apt−1 )
)
size(M aptotal )

Where δ is the exploration ratio, or explored area over total area. Empirically, θ0 is set as 20
and θth (the threshold) is set as 12. When θ → ∞, distance is not considered and FNs are greedily
placed as the positions that cover most. On the other hand, when θ → 0 the distance is weighed
heavily so the frontier cell closest to the current positions pCGt−1 is selected. Thus, θ deﬁned in
equation 3.4 enhances performance with initial emphasis on coverage while focusing on migrating
time in the end to avoid unnecessary ﬂuctuating moves. This approach resembles the candidate
evaluation method in [92] but shows disparities in setting θ dynamically to adjust the distance’s
weight and deﬁning distance as the minimum from one point to a set of positions.
34

This problem can also be viewed as a variant of the well-known NP-hard Set Cover problem
[93] when θ → ∞. In the set cover problem, the minimum number of sets are selected so that
all elements are contained, while in our problem a ﬁxed number of sets are selected with the goal
that the maximum of elements are covered when assuming a set is the unvisited cell set by each
frontier cell and an element as an unvisited cell. It is not difﬁcult to prove that our problem is no
easier than the set cover (thus is also NP-hard) because a polynomial solution to ours, if it ever
exists, will lead to a polynomial solution to the set cover. To sum up, our solution inherits a greedy
approximation of set cover, along with dynamic cost modeling of migrating distance.
Terms

Deﬁnitions

δ
Gf (t)
dist(i, j)
path(i, j)
Lcur , Lnew
Ni

Exploration ratio. Explored area compared with total area.
Hybrid ﬂow graph, Gf (t) = {V, E(t) ∪ E(t)}.
Straight line distance from i to j.
Shortest obstacle-aware migrating path from i to j.
The current layer and the new layer.
Node i’s Neighbor node set excluding Lnew , j is a neighbor of i
when dist(i,j)≤ rc .
Cluster head, vector of CH of current layer, and cluster head node i.

CH,
CHcur , ich
FSe , FSi
CFi , FCNi
RLt
i
N−
BS
nremain

Vector of carried and to-be relayed Flow Source passing through
edge e and node i.
Covered Flows (CF) and Fully Covered Nodes (FCN) of node i.
|CFi | ≤ γ.
Route List. Sequence of nodes on routing path from FN i to BS in
iteration t.
Unsaturated 1-hop Neighbors to the BS.
Number of remaining nodes.
Table 3.2. Notations in Algorithm 1-7 in CBAX.

35

3.3.3

Relay Robot Placement with Routing Path Selection

Now that FNs are placed, we need to ﬁnd (1) whether the rest (n-nf n ) nodes are adequate to relay
BS and FNs and how to place them; (2) If the nodes are abundant, then how to route the streams
from each FN to BS. We present two solutions with respect to situations considering different
bandwidth ratio γ deﬁned in equation 3.2.
Algorithm 3:
Relay Node Placement

With

Routing

Selection

plac-

eRN RoutingPathSelection()
Input: pCGt
Output: CGt , nrn
1 if isBandwidthSufﬁcient then
2

nrn , pCGt ← SteinerizedMST(FNt )

3

rCGt ← BFS RoutingPath(pCGt )

// in Alg. 4

4 else
5

CGt , nrn ← ConstrainedSteinerTree Routing(FNt )

// in Alg. 5

• When γ is sufﬁciently large, the ﬁrst problem can also be viewed as a decision version of
Steiner Minimum Tree Problem with Minimum Number of Steiner Points and bounded edge
length (SMT-MSP) where FNs and BS are the terminal points and RNs are the Steiner points.
The routing problem can be easily solved afterwards.
• When γ is small and the bandwidth of aggregated ﬂows may exceed link capacity, we model
the problem as a decision version of SMT-MSP with the γ-inﬂow constraint and present our
solution.

36

Bandwidth-Sufﬁcient Relay Node Placement and Routing
The problem is modeled as the NP-hard problem of SMT-MSP, which was introduced and investigated in [43, 91]. First we build a complete graph1 Gcomp of BS and FNs. In the next step, our
solution is built on the well-known approximation algorithm called Steinerized Minimum Spanning
Tree for SMT-MSP, with an approximation ratio of 4 [91]. Interested readers may try more sophisticated schemes in [43] with ratio of 3 and 2.5. Since the ratio is only an upper bound compared
with the optimal, the improvement in our application may not be that signiﬁcant. When the RN is
placed at an obstructed cell, A* search [94] is adopted to compute the obstacle-aware shortest path
from one end (starting point) to the other end (goal) of the edge (line 7 in Alg. 4) and the RN is
placed again on the new path. We use the straight-line distance to the goal as the admissible2 and
consistent heuristic function h(n) that never overestimates the distance to goal. A* search guarantees the same optimal result as Dijkstra while reducing the searching space. With RNs placed and
tree constructed, the shortest routing path (in terms of number of hops) from each FN to BS can be
obtained by breath-ﬁrst search (BFS) (line 3 in Alg. 3). We are able to use BFS because only the
1A complete graph is a simple graph in which every pair of distinct vertices is connected by an

edge.
2Most admissible h(n) are also consistent. Details of the proof of consistency is in [94].

37

number of intermediate nodes counts while the weight of each edge is not considered.
Algorithm 4: Bandwidth-Sufﬁcient Relay Node Placement: Steinerized Minimum Spanning
Tree SteinerizedMST()
Input: FNt
Output: pCGt
1 Construct a complete graph Gcmp from {FNt ∪ BS}
2 Construct a MST Tmst from Gcmp , T ← Tmst
3 RNt .add( non-leaf nodes in T )
4 foreach edge e in T whose length l(e) > rc do
5

Cut long edge e into l(e)/rc shorter ones of equal length by placing l(e)/rc − 1
Steiner points {sp}e on e

6

if ∃i(i ∈ {sp}e ∧ Pi =obstructed) then

7

Update e by: e ← A∗ Search(e)

8

Place Steiner points again on e and update {sp}e

9
10

RNt .add({sp}e )
Replace edge e with |{sp}e |+1 shorter edges

11 nrn ← |RNt |
12 pCGt ← FN + RN

Bandwidth-Constrained Relay Node Placement and Routing
When bandwidth ratio γ is small, the problem is modeled as SMT-MSP with the constraint that
each node can admit no more than γ ﬂows from FNs (FNs may also relay ﬂows). Alternatively, if
we deﬁne a node as saturated when it carries γ ﬂows and as over-saturated when it carries more
38

than γ ones, the problem becomes SMT-MSP without over-saturated nodes when ﬂows transmit
from n − 1 terminal points to one terminal point (BS). The problem is as hard as SMT-MSP (thus
is also NP-hard) since if we can ﬁnd a polynomial algorithm for it and we set γ → ∞, SMT-MSP
would be polynomially solvable.
The solution’s central theme is to reduce unnecessary RNs by aggregating ﬂows and the following deﬁnitions relevant to ﬂow aggregation are introduced. First, on top of the dynamic graph
G(t) of FNs and BS, a hybrid ﬂow graph Gf (t)= {V, E(t) ∪ E(t)} is deﬁned where an undirected edge e denotes nodes in communication range while a directed edge e represents not only
connected vertices, but also directed ﬂow(s) from FNs to BS. Second, the Vector of carried Flow
Source for each e, or FSe , denotes the vector of sources of the ﬂows passing through this edge.
For each node i, FSi gives the carried and to-be relayed Flows Source vector (Sources here are
the FNs which produce ﬂows). Third, Lcur gives the current layer of nodes and Lnew gives the
new layer. Fourth, a cluster head CH is deﬁned as the node that aggregates ﬂows in each layer
and CHcur denotes the cluster head vector of current layer nodes. Last, but not least, path(i, j)
denotes the shortest obstacle-aware migrating path from i to j and Ni is node i’s neighbor node set
excluding Lnew (j is a neighbor of i when dist(i, j) ≤ rc ).
Additionally, we deﬁne CFi as the Vector of Covered Flow of i, in which each element is a
linked list that begins with the node ID j ∈ Ni ∪ i as the head and continues with sources from
FSj (An example has been provided in Fig. 3.5. Note that CFi depicts the potential ﬂows that
may be carried where FSi describes the ﬂows that have already been carried. A node j ∈ Ni ∪ i is
fully covered by node i when all of j’s ﬂows can be aggregated by i. FCNi denotes the vector of
i’s Fully Covered Nodes (j ∈ FCNi iff j ∈ Ni ∪ i ∧ FSj ⊆ CFi ). Note that |CFi | ≤ γ and |CFi |
only counts the source nodes. Each node must ﬁrst carry its own ﬂow if it is in Lcur , or its parent’s
39

ﬂow if it is a RN in Lnew . Then |FCNi | − 1 denotes the number of extra RNs can be saved with
such aggregation using the remaining capacity.
Flow aggregation: To minimize RN size, ﬂow aggregation is executed in an order with maximal
|FCNi | ﬁrst. The problem of ﬁnding maximal |FCNi | is solved optimally by greedily covering
minimal |FSi | node ﬁrst. For example, in Fig. 3.5, new layer RN node n can maximally cover two
extra nodes, or save two RNs immediately otherwise needed by node 3 and 4. n can aggregate all
ﬂows from them: n’s FCNn = {3, 4} with the remaining capacity 9-4=5 after it obtains its parent
node 1’s four ﬂows.
Major strategy with illustration: RN placement and routing path selection are solved jointly
in a layer-based approach, which is also described in Alg. 5 and illustrated in an example in Fig.
3.3 and 3.4. First, FNs FNt are set as Lcur and covered nodes/ﬂows are computed for each node
i ∈ Lcur based on FSi , which is initialized as itself being the only element since a node carries its
own ﬂow (line 3). With Lcur , the algorithm is to compute Lnew as new RN until all current layer
nodes are in range of BS, which is the terminating condition gives in line 4.
Computing Lnew is executed in two steps: (1) Clustering nodes and aggregating ﬂows in Lcur
with CH selection and RN placement. (2) Aggregating ﬂows into Lnew with Lnew RN ﬁltering,

40

which are given in line 5-12, 13-22 respectively.
Algorithm 5: Bandwidth-Constrained Relay Node Placement With Routing Path Selection
ConstrainedSteinerTree Routing()
Input: FNt
Output: CGt , nrn
1 Lcur ← FNt , Lnew ← ∅

// FNs as current layer

2 foreach i ∈Lcur do
3

initialize(FSi ), setCoveredFlow Node(i, Ni ∪ i, false)

4 while ∃ node i(i ∈ Lcur ∧ dist(i, BS) > rc ) do
5
6
7
8
9
10
11

tmp

Lcur ←Lcur
tmp
while Lcur = ∅ do

14
15
16
17
18

// Select cluster head

tmp
CHcur .add(ich ), Lcur .remove(FCNi )
ch

updateFlow Route (ich )
placeRN along path (ich )

// in Alg. 6
// Generate Lnew in Alg. 6

tmp
foreach i ∈ Lcur do

setCoveredFlow Node(i, Ni ∪ i, false)

12
13

tmp

ich ← max |FCNi | node i ∈ Lcur with min dist(i, BS)

// in Alg. 6

tmp

Lnew ←Lnew
tmp
foreach i ∈Lnew do setCoveredFlow Node(i, Ni , true)
tmp
while Lnew = ∅ do
i† ← max |FCNi | node i ∈ Lnew with max |CFi |
tmp

| = 0 then Lnew .remove(i† )
if |FS †
i .parent

// Filtered

Lnew .remove(i† )
tmp

19

updateFlow Route (i† )

20

foreach i ∈ Lnew do setCoveredFlow Node(i, Ni , true)

tmp

21

Add Lnew to RNt

22

Set Lnew as Lcur ; Clear Lnew

23 nrn ← |RNt |, pCGt ← FNt + RNt
24 foreach i do rCGt .add(RLt )
i
25 CGt ← pCGt ∪ rCGt

In the ﬁrst step, we repeatedly select cluster heads CH in Lcur and inserts them into CHcur

41

h

a
b
d
c

=3
Obs.
a FN
1 RN
e

BS

f

g
(a) With FNs and BS only.

h

a

1
3

1
b

5

1
c

1

d

=3
Obs.
a FN
1 RN

3

e

1

1
2

BS

4

2

f

1

g

(b) Placing 1st layer RNs.
Figure 3.3. Example of bandwidth-constrained relay node placement and routing (Step 1 and 2
out of 4 total steps). (γ=3) Edge weight denotes |FSe |

42

h

a

1

1
b

5

3

1

1

1
8

1

c

d

=3
Obs.
a FN
1 RN

3

7

e

1

1

3
BS

2

3

6

2

f

1

g

1
4
(a) Placing 2nd layer RNs.

h

a

1

1
b

5

3

1

1

1
8

c

1

d

=3
Obs.
a FN
1 RN

3
2

e

1

1

3
BS

3

3

6

2

2

f

1

g

1
4
(b) Final placement.
Figure 3.4. Example of bandwidth-constrained relay node placement and routing (Step 3 and 4
out of 4 total steps). (γ=3) Edge weight denotes |FSe |

43

2(i,j)
4
2(g,h)
3

n

4

1(a)
3(b,c,d)
1*

2(e,f)
2 3(k,l,m)

BS

=9
Obstacle Vcfn : |Vcfn|=9
1*
n.Parent 1 a b c d
4 Fully cover
4
i
j
2
Lcur 3 g h
n

Lnew

2

e

Figure 3.5. Aggregate ﬂows to nodes with maximal number of fully covered neighbors ﬁrst to
conserve RNs.

44

to aggregate ﬂow in the cluster in the order of “maximal |FCNi | ﬁrst” (Choose minimum distance
to BS if |FCNi | are equal since the shorter distance indicates fewer needed RNs). Moreover, we
place RNs when needed to form Lnew in the paths from CHcur to BS and A* search is used
similarly as in Alg. 4 to avoid obstacle. Note that ich is set as the new RN’s parent. Function
updateFlow Route (i) (line 15-19 in Alg. 6) describes how a node i aggregates ﬂows by moving
elements in neighbor node j’s FSj to FSi following i’s covered ﬂow CFi . Moreover, source s’s
RLt is updated with the new RN appended. For instance, in Fig. 3.3(a), FN c is chosen as cluster
s
head since it is the closest to BS among the ones with maximal |FCNi | = 3. FSc is updated as

45

{c,b,d} and c is added in RLt and RLt for sources b and d.
d
b
Algorithm 6: Supporting Functions for Algorithm 5
// Obtain (pre)knowledge on covered ﬂows (CF) and fully covered nodes (FCN); not to
transmit ﬂows yet.
1 setCoveredFlow Node (node i, node set S, bool isNewRN):
2 CFi .clear(), FCNi .clear()
3 if isNewRN =true then
4

S.remove(i.parent)

5

CFi .add(i.parent → FSi.parent ), FCNi .add(i.parent)// Obtain all of its parent’s ﬂows

6 else
7

S.remove(i)

8

CFi .add(i → FSi ), FCNi .add(i)

// Obtain all of its own ﬂows

9 while |CFi | < γ ∧ (∃ node k ∈ S whose |FS| = 0) do
10

j ← such node k with min |FS|

11

S.remove(j)

12

while |CFi | < γ do

13
14

CFi .add(j → distinct source k ∈ FSj )
if FSj ⊆ CFi then FCNi .add(j)

// CFi .j → {k}
// Fully covered node

// To transmit ﬂows.
15 updateFlow Route (node i):

// Function begins

16 foreach neighbor (head in CF) j ∈ CFi . ∗ ∧j = i do
17
18
19

foreach FN s ∈ source nodes for ﬂows carried by j do
Add i as a relay for FN s in RLs
Transmit j’s ﬂows from j to i by updating their FS

20 placeRN along path (i):

// Function begins
// Place RN if needed

21 if dist(i,BS)> rc then
22

Place relay rn at dist(rn, i) = rc on the obstacle aware path from i to BS generated by
A* search(i, BS)

23

Set rn’s parent as i; Add rn to Lnew .
In the second step, CBAX executes ﬂow aggregation with the same order of “maximal |FCNi |
46

ﬁrst” (Choose maximum size of covered ﬂows if |FCNi | are equal) for Lnew and attempts to
remove unnecessary nodes by ﬁltering the new layer nodes whose parent’s ﬂows have all been
carried by others. To illustrate in Fig. 3.4(a), new layer RN 8 is ﬁrst to aggregate ﬂows with
|FCNRN 8 | = 2 and then RN 7 has |FSRN 3 | = 0 and is consequently ﬁltered.
tmp

A layer placement ends when Lnew is empty (line 15). Then Lnew becomes Lcur and a new
round starts. To conclude, the ﬂows, denoted by FSi for node i , are aggregated in CH in Lcur and
then in Lnew with best endeavor to reduce the number of RNs.
Update ﬂow information: In the beginning of the algorithm and after both ﬂow aggregation in
the two steps, function setCoveredFlow Node (line 1-14 in Alg. 6) is called to update the covered
tmp

ﬂows and fully covered node information. Furthermore, rest of the nodes still in Lnew are updated
in line 20 and these updates are necessary for the next round computation. With γ → ∞, this ﬂow
aggregation based relay placement algorithm also ﬁts the sufﬁcient bandwidth situation.
Upper bound of approximation ratio: We derive the upper bound of the approximation ratio of
the bandwidth-constrained relay placement algorithm.
First we deﬁne some notations.

A maximum degree in a graph G is:

Δ(G) =

max{degG (v)|v ∈ V (G)}. We denote n, ns , nd , and nopt are the respective relay size obtained
by: (i) ﬂow constrained relay placement algorithm; (ii) S-MST without the ﬂow constraint; (iii)
DT: direct tree, or a simple aggregation tree (star graph with center BS) where all ﬂows from FNs
are directly relayed to BS without aggregation; and (iv) Topt : An optimal Steiner tree with ﬂow
constraint and minimum number of RN.
In addition, MST denotes the minimum spanning tree for FNs and BS. DT and MST are two
very simple tree structures easily obtained when given the input of FNs and BS. We deﬁne κ =

47

nd /ns =

e∈E(DT ) e/rc /

e∈E(M ST ) e/rc , where κ is the ratio of relays size for DT over

that of MST. Hence, κ is related to FN and can be directly obtained from input.
Lemma 1. Every Steiner tree satisﬁes the ﬂow constraint must have its maximum degree Δ(T ) ≤
1 + γ.
Proof. For a vertex, its incoming degree is constrained by γ, the number of incoming ﬂows for
aggregation. With only one out-coming link, the total degree is at most Δ(T ) ≤ 1 + γ.
Lemma 2. There exists a shortest optimal Steiner tree Topt whose maximum degree is less than
or equal to ﬁve, i.e., Δ(Topt ) ≤ 5, in an obstacle free area or obstructive area where triangular
inequality holds.
Proof. When the obstacle distribution does not impact the triangular inequality: with A* obstacle
aware paths, the shortest side is still across from the smallest angle. Then we can prove two edges
meeting at a vertex in a Topt form an angle of at least 60 degree, by the proof similar to that in [91]
on an Euclidean plane. Besides, authors in [91] also proved that a six degree tree can be modiﬁed
to a 5 degree one. Therefore, Δ(Topt ) ≤ 5.
Theorem 1. The approximation ratio of bandwidth constrained relay placement algorithm is no
greater than κ·(1+γ). In an environment where obstacle distribution does not affect the triangular
inequality, the ratio is no greater than κ · min{5, 1 + γ}.
Proof. With an optimal tree Topt , we duplicate each edge and build an Eulerian tour such that
every Steiner point appears at most Δ(Topt ) times in the tour while each terminal point appears
exactly once. Removing one (or more) edge in the tour will give a spanning tree T where Steiner
points have degree at most two. Its Steiner point size n(T ) is no more than Δ(Topt ) times in Topt .
48

Because ns is from S-MST: a minimum spanning tree, we have:
ns ≤ n(T ) ≤ Δ(Topt ) · nopt

(3.5)

With κ = nd /ns and the fact that ﬂow aggregation guarantees n ≤ nd , we have:
n ≤ nd ≤ κ · Δ(Topt ) · nopt

(3.6)

n/nopt ≤ κ · Δ(Topt )

(3.7)

With Lemma 3 and 4, Δ(Topt ) = min{5, 1 + γ} in obstacle free area or obstructive area where
triangular inequality holds. Otherwise: Δ(Topt ) = 1 + γ. Replacing Δ(Topt ) concludes the
proof.

3.3.4

Position Assignment And Path Generation

With current positions pCGt−1 from the execution of last iteration of n robots and the computed
n next positions pCGt , there is a problem with how to assign each robot to go to which newly
computed position, so that mT t , which is decided by the bottleneck longest distance of all pairs, is
minimum. We formally model this problem as the linear bottleneck assignment problem (LBAP)
[95]. LBAP can also be viewed as ﬁnding a perfect matching in a weighted bipartite graph that
minimizes the maximum weight of all matched edges [96]. Mathematically, LBAP is:
mT t =

min

max

xij ∈{0,1} i,j

cij xij ,

n

xij = 1,

j = 1, ..., n,

xij = 1,

subject to

i = 1, ..., n,

i=1
n
j=1

xij ∈ {0, 1},

49

i, j = 1, ..., n

(3.8)

Where {cij }n×n is the cost matrix and cij is the cost as the length of shortest obstacle-aware path
by A* from node i to position j. Moreover, {xij }n×n is the resulting binary matrix where xij =1
iff the node i is assigned to position j. We adopt the algorithm in [97] with expected running
time O(n2 ), which generates the optimal result. Its general procedure is as follows: (1) From
the original bipartite graph, a subgraph with 2n ln n minimum-cost edges is selected. (2) In this
subgraph, LBAP is solved by scheme in [98]. (3) If a perfect matching is not found with a low
probability then, the matching is done in the original graph. According to [96, 99], it is one of the

50

most efﬁcient algorithms for LBAP.
Algorithm 7: LBAP Based Position Assignment and Path Generation with Collision Avoidance genPath()
Input: pCGt−1 , pCGt , T t−1
Output: mT t , T t , P atht
1 Construct complete bipartite graph Gcb = (pCGt−1 + pCGt , E)
// update edge weight as obstacle-aware ones
2 foreach e ∈ EG

cb

do e ← A* search(e)

// Call bipartite graph and perfect matching based LBAP() in [97]
3 mT t , P atht ← graphBasedLBAP(Gcb )
4 mT t , P atht ← avoidCollision(mT t , P atht )
5 T t ← T t−1 + mT t

// Algorithm ends

6 avoidCollision(mT t , P atht ):

// Function begins

7 if IntersectionExists(P atht ) then
8
9

if SameTimeIntersectionExists(P atht ) then
mT t ← RescheduleCollisionNodes(mT t )

Since the paths obtained may not be collision free, we adopt a simple scheduling to avoid
collision (line 6-9 in Alg. 7). First we check whether intersection points of the paths exist. If true,
then we will check whether the intersection is reached by different nodes simultaneously. If true
again, collision may occur and different nodes may wait different amounts of time, e.g. node i
waits i second(s) before reaching the intersection place to avoid such collision.

51

3.3.5

CBAX Enhancement

Besides the major steps above in CBAX, we improve the control message transmission and use
remaining nodes for placement to further enhance CBAX’s performance.

Filter Based Control Message Transmission
In each iteration, a node needs to notify BS by sending an “arrived” control message when arriving
at the target position. Since a node in movement indicates it will send to BS its “arrived” message
in the future, the communication overhead can be reduced by not forwarding packets to BS if a
moving node j receives the ”arrived” message from a stopped (arrived) node i. When j also arrives
at the targeting position, j can append i’s information in j’s “arrived” message. The completion of
the last mobile node’s movement indicates the completion of all nodes in one iteration. Besides, it
is possible that when an arrived node sends the message, the intermediate nodes on the path back
to the BS are still moving. They may be out of reach of the sender and therefore not able to relay
the message. Under such occasions, the arrived node will retransmit the packet on timeout until
the BS sends acknowledgement to conﬁrm it has received the message.

Remaining Node Placement
When nf n + nrn < n (line 6-7 in Alg. 1), we need to identify the remaining node positions
to maximize the exploration efﬁciency. Generally, we attempt to place nodes as FNs using the
unsaturated paths to carry ﬂows to the BS. First, we identify the unsaturated 1-hop neighboring
nodes of BS N− which have extra capacity not yet used. A node i is unsaturated when |FSi | < γ.
BS
Second, to place remaining nodes as FNs, we collect cells in FC which are in range of the ﬂow
source nodes of N− to form FC∗ . The remaining node positions are selected as the cell with the
BS
52

maximum gain in FC∗ . When there are no unsaturated paths, we place the remaining node using
the previous iteration position in pCGt−1 which is closest to the nearest node in pCGt . Such
placement avoids the remaining node relocation to be the bottleneck in assignment. Alg. 8 shows

53

the procedure in detail.
Algorithm 8: Remaining Node Placement placeRemainNode()
Input: pCGt−1 , pCGt
Output: pCGt
1 nremain ← n − (nf n + nrn )
// Put unsaturated and close to BS’s nodes in pCGt to N−
BS
2 foreach i ∈ pCGt ∧ dist(i, BS) ≤ rc ∧ |FSi | < γ do N− .add (i)
BS
3 while |N− | = 0 ∧ nremain > 0 do
BS
4

FC∗ ← Frontier cells that are in range of ﬂow sources of N−
BS

5

foreach q ∈ FC do Store corresponding node pair (i, j) of BS’s neighbor i and ﬂow
source j: {i, j|i ∈ N− , j ∈ FSi ∧ dist(q, j) ≤ rc }
BS

6

q ∗ ← argmaxq∈FC∗ U (q); add q ∗ to pCGt .

7

i∗ , j ∗ ← q ∗ ’s corresponding i, j

8

M ap ← updateLocalMap(q ∗ , M ap)

9

FC ← updateFrontierPosSet(M ap, FC)

10

Add j ∗ ∪ RLt ∗ to q ∗ ’s route list
j

11

for k ∈ RLt ∗ do update FSk
q

12

if |FSi∗ | = γ then N− .remove(i∗ )
BS

13

nremain ← nremain − 1

14 while nremain > 0 do

// No unsaturated paths

15

q ∗ ← node q ∈ pCGt−1 with min distance to nearest node in pCGt

16

pCGt .add (q ∗ )

54

3.4

Performance Evaluation

We evaluate CBAX’s performance using a multi-robot simulator in C++ and compare CBAX with
two recent schemes that consider limited communication range: (1) A distributed “Sensor-based
Random Graph” (SRG) scheme in [32], which is more efﬁcient but does not guarantee connectivity; (2) A centralized “Possible Moves Sampling” (PMS) approach in [36] that assures connectivity
but is less efﬁcient. The metrics for comparison include exploration efﬁciency and communication
quality. We use the total exploration time as the primary criteria for efﬁciency. If not stated otherwise, the time is measured from a clustered start at the left-bottom corner to a state with over 95%
of explored area. Also, the constant STI in each iteration is not included in the measured time for
the three schemes. To evaluate the communication quality, the Non-Overﬂow Transmission Time
ratio (NO TT), or the percentage of transmission time for not over-saturated ﬂows divided by the
total transmission time, is used. Besides, the percentage of iterations in which all robots maintain
connected with BS and within the robot team, or fully-Connected Time ratio with the Base Station
(CT BS) and within the Robot Team (CT RT), are also measured. Two environments, the Open
and Garden in Fig. 3.7(a), are used to compare the schemes.
The parameters are set to make the comparisons fair. We obtain the results and parameters
from SRG’s sample video in [100] and simulate CBAX using the same set of parameters (with
proper scaling) and the same Garden environment. While teams with only 4,6,8 robots are tested
in SRG, we simulate PMS and compare with CBAX on 6-12 robots to obtain results for more
complex topologies using the Open environment. Speciﬁcally, the grid cell and robot size are 1m,
the robot’s moving velocity is 1m/s, and the accelerating/decelerating time is ignored. Map sizes
for the Open and Garden environments are 45m×45m and 48m×48m and (rc , rs ) are (10m,7m)

55

and (21m,7m) respectively. All experiments are run ﬁve times to obtain the average. For CBAX,
two relay placement strategies are evaluated: BS-CBAX: CBAX with Bandwidth-Sufﬁcient relay
placement; BC-CBAX: CBAX with Bandwidth-Constrained relay placement (γ=3).
Exploration efﬁciency: Compared with PMS, BS-CBAX and BC-CBAX reduce explore time
on average by 40.9% and 39.7% respectively as shown in Fig. 7.7. The improvement is more
signiﬁcant when team size increases. With 12 robots, the improvement are 54.7% and 45.3%. The
major reason is that CBAX expends nodes promptly and systematically places nodes to reduce
relay robots while in PMS, nodes are expended slowly especially when number of nodes increase.
In addition, Fig. 7.8(b) shows that CBAX is more efﬁcient than PMS with different percentages of
explored area. Compared with SRG, CBAX remains the more efﬁcient approach, even though SRG
is a distributed and efﬁcient scheme maintaining neither connectivity nor bandwidth adequacy.
BS-CBAX and BC-CBAX decrease explore time on average by 15.9% and 13.0% respectively
as shown in Fig. 7.8(a). With 8 robots, the improvement are 27.4% and 22.2%. In most cases,
BC-CBAX is slightly more efﬁcient than BS-CBAX when n is small but is less efﬁcient when
more robots are in the team. The reasons are: (1) Our ﬂow aggregation based solution is more
efﬁcient than the general SMT based approximation algorithm. (2) The ﬂows are less likely to
be overﬂowed (γ=3) when node number is small. With more robots, however, the impact of the
constraint is more noticeable, resulting in longer exploration time with more RNs placed.
Communication quality: Compared with PMS that only guarantees connectivity, CBAX futher
assures the real-time data ﬂow of being under link capacity. In PMS, overﬂow transmissions occur
in 21.5% of the iterations on average, in which 31.5% of data is lost. While CBAX always maintains connectivity and ensures no overﬂow occur, SRG with 4 robots shows that only in 20.7% of
iterations all nodes are (through multi-hops) connected to BS and 48.3% of iterations all nodes are
56

200
BS−CBAX
BC−CBAX
PMS in [3]

Seconds

150

100

50

0

6Rbts 8Rbts 10Rbts 12Rbts

(a) Exploration time: CBAX vs. PMS in [36] with 6,8,10,12 of robots in
the open environment.

Seconds

200

BS−CBAX
BC−CBAX
SRG in [1]

150

100

50

4Rbts

6Rbts

8Rbts

(b) Exploration time: CBAX vs. SRG in [32] with 4,6,8 robots in the
garden environment.
Figure 3.6. Simulation results on exploration time.

57

connected within the robot team. Note that video available online is only with 4 robots. However, the results with 6/8 robots are similar since SRG is not aware of connectivity and bandwidth.
Besides, in 79.3%3 of iterations overﬂow transmission occurs and 83.7% of data is lost in such
overﬂow sessions. Fig. 3.8 also depicts the results.

(a) The Open and Garden environments where black parts denote
obstacles.

200

Seconds

150

BS−CBAX
BC−CBAX
PMS in [3]

100
50
0
70

80
90
100
Explored Area Percentage %

(b) Exp. time: CBAX vs. PMS in [36] with varying percentages
of explored area (10 Robots).
Figure 3.7. Environments and exploration time.
3We deﬁne a disconnected link has link capacity 0 bit/sec.

58

Discussion: A mobile multi-hop wireless network’s quality of service (QoS) is a complex
issue affected by various factors such as underlying MAC protocol, interference, channel quality, scheduling, congestion control, and routing path selection. Besides, the contention based
CSMA/CA MAC protocol in 802.11 may not guarantee an absolute link rate and throughput.
However, topology and node movement signiﬁcantly inﬂuence the performance of the network
protocol in mobile ad hoc networks [101] and with our QoS-aware mobility model, we provide
the most fundamental assurance of bandwidth adequacy. To further enhance rate control, we can
employ the Time Division Multiple Access (TDMA) based scheduling to guarantee the required
bandwidth for each ﬂow on a certain link.

3.5

Summary

In this chapter, we have proposed a scheme for multi-robot exploration called Connectivity and
Bandwidth Aware eXploration (CBAX), which is an efﬁcient iteration based real-time exploration.
CBAX divides the problem into frontier node placement, relay node placement with routing path
selection, and matching of each robot with its target position. Moreover, we model bandwidthconstrained relay node placement into a new variant of the Steiner Minimum Tree problem and
present our solution. While reducing the exploration time, CBAX maintains the network’s connectivity and ensures the aggregated data ﬂows are under the link capacity in transmission. Simulation shows that CBAX outperforms two recent exploration schemes qualitatively by demonstrating
major improvement in terms of non-overﬂow transmission time and fully-connected transmission
time. With enhanced communication quality, CBAX still reduces the exploration time, on average,
by 40% and 15% respectively. In moderately dense scenarios, CBAX even decreases time by 50%

59

100
CBAX
PMS in [3]

Percent %

90
80
70
60
50

6Rbts 8Rbts 10Rbts 12Rbts

(a) NO TT: CBAX vs. PMS in [36] with 6,8,10,12 of robots in the open
environment.

100
CBAX
SRG in [1]

Percent %

80
60
40
20
0

CT_BS CT_RT NO_TT

(b) CT BS, CT RT, and NO TT: CBAX vs. SRG in [32] with 4 robots
in the garden environment.
Figure 3.8. Simulation results on communication quality.

60

and 25%. In the next chapter, we will consider the heterogeneous communication ranges and data
rates along with the impact of interference.

61

CHAPTER 4
Stream Aggregation in Heterogeneous
Range and Rate Mobile Robot Networks

4.1

Preliminaries and Motivations

In the previous chapter, when we cope with the key component of the exploration process, i.e.,
relay placement in each iteration, we have assumed uniform link capacity and transmission range
(UCR). (We use link capacity to refer to the actual bandwidth or achievable throughput while the
modulation rate refers to the much higher theoretical data rate that neglects numerous factors such
as MAC overhead [102].) We modeled the problem by a variant of the Steiner Minimum Tree
Problem with Minimum Number of Steiner Points (SMT-MSP) with integer inﬂow constraints. It
assumes: (1) uniform disk models with homogenous link capacity and transmission range; (2) the
impact of interference is minimal and is therefore neglected. While such assumptions are common
and make the problem be easily analyzed and solved, they are inconsistent with real 802.11 network
conditions.
62

In this chapter, however, we consider two new conditions, or HCRI2 : (1) the Heterogeneous
link Capacities and transmission Ranges (HCR); (2) the Impact of Interference (I2 ). The motivation of considering HCRI2 is threefold. First, as multimedia streams demand high bandwidth, it
is also important to consider the tradeoff between link capacity and transmission range. There is a
fundamental tradeoff between data rate and range as higher modulation rates increase the link capacity (throughput) but decrease the range at which the transmission can be successfully decoded
as signal power and channel capacity decrease with distance.
Second, similar to our communication task’s strong dependence on mobility, the tradeoff between link capacity and transmission range also reﬂects such dependence if we regard link capacity
as the critical communication metric and transmission range variance as the result of movement.
Since such tradeoff interestingly has the same property of tight connection of mobility and communication as our task, we would like to explore whether the tradeoff can be leveraged in favor
of our task’s goal. Third, as interference signiﬁcantly impacts the relations of transmission ranges
with rates and undermines the communication quality, we consider interference as well.
Third, HCRI2 reﬂects the central characteristic of wireless communication in real-world settings although it makes the node placement more complex: The transmitter and receiver’s distance
and I2 cause the link capacity to be dynamic. To our best knowledge, no prior work takes advantage of the tradeoff in distance and bandwidth to ensure bandwidth adequacy with controlled
mobility.
UCR based relay placement cannot take advantage of HCR. Besides, I2 is also detrimental
to bandwidth adequacy. To solve the problem with HCRI2 , we propose a multi-channel dual
radio network architecture with dynamic TDMA scheduling to minimize interference. A channel
assignment scheme, modeled by bandwidth coloring, tackles out-of-band (OOB) emission [103]
63

in the same node by limiting the minimum channel distance. The details of the multi-channel dual
radio network architecture and the channel assignment scheme are presented in Section 4.2 and
Section 4.5 respectively.
Similar in CBAX, we also consider the relay placement and routing jointly because routing
decides the path on which a stream traverses; and the bandwidth sufﬁciency depends on both
supply (the link capacity) and demand (which streams use the link given the routing paths). We
model the stream aggregation problem as the relay placement and routing for bandwidth sufﬁciency
(R2 BS) with HCRI2 , which can be described as follows: Given a set of stream sending nodes (SN)
and a base station (BS), how to place a minimum number of relay nodes (RN) in a set of candidate
positions and choose the routing paths from each SN to BS, such that (1) all SN are connected with
the BS with the help of relays; (2) the aggregated consumed throughput by the streams is under the
link capacity, considering heterogeneous range and rate in transmission. R2 BS may be classiﬁed
as a single-tiered and constrained relay placement according to [47]. It is single-tiered in that SN
also forward packets. It is constrained because there are forbidden areas where relays cannot be
placed.

4.1.1

Key Contributions

• To the best of our knowledge, this work is the ﬁrst of its kind to jointly consider relay
placement and routing to achieve bandwidth sufﬁciency for multimedia real-time stream
aggregation considering the heterogeneous range and rate and impact of interference.
• To solve R2 BS, we formulate the problem as a new variant of the Steiner tree problem called
the heterogeneous bandwidth Steiner routing (HBSR). We prove the problem NP-hard and

64

present an efﬁcient heuristic with 44% reduced relay number compared to the widely used
minimum spanning tree based approximation algorithm for relay placement. We also show
the upper bound of the algorithm’s approximation ratio in the Appendix.
• We also found that considering heterogeneous range and rate is beneﬁcial in relay placement.
Compared to the uniform range and rate bandwidth-aware placement algorithm, our scheme
reduces the number of relays by 25%-39%.
• We propose the “expected relay count” to quantify the ﬂow aggregation’s impact on relay
reduction number. With expected relay count, we evaluate different aggregation cases and
select the ones with maximum reduction, resulting in signiﬁcant reduced number of relays.

The rest of the chapter proceeds as follows. Section 4.2 introduces the system model. In
Section 4.3, we formulate the problem and discuss the challenges. Section 4.4 presents the main
solution of relay placement and routing. Section 4.5 gives the channel assignment. Performance
evaluation is in Section 4.6. Section 4.7 gives the summary of the chapter.

4.2
4.2.1

System Model
Environment Model

We apply a 2D occupancy map with grid cells to represent the environment as a rectangular region
R = X × Y . A subset of cells are marked as “obstacles” to be excluded from the candidate
positions for the relays.

65

4.2.2

Network Model

We consider a static wireless network, or a mobile wireless network where nodes are static when
streams are in transmission. The network has 3 types of entities: (1) stream sending nodes (SN),
(2) stream relay nodes (RN), and (3) the base station (BS). Each SN has a uniform ﬂow sending
rate rs for its streams. We relax rs to be non-uniform in the Appendix.
A link with a sender u and a receiver v is denoted by a directed edge e(u, v) ∈ E in the graph
G(V = {SN, RN, BS}, E). The edge length is the physical distance between u and v. Given
its edge length, a link e’s bandwidth Be is the maximum allowed link bandwidth mapped to the
distance no smaller than its edge length. e’s link utilization ratio Ue is e’s carried ﬂow rate divided
by its bandwidth. A routing path, or path(V)=(v0 , v1 ,...,vn ), gives an ordered vector of positions.
Due to the complex impact of interference on link bandwidth, a multi-channel dual-radio with
local TDMA scheduling model is adopted to eliminate interference. Note that the effectiveness and
validity of the model has been demonstrated by previous testbeds [1, 103–105]. In future work, we
will consider the complex interference impact under CSMA/CA.
• We adopt a multi-channel dual-radio network model to eliminate interference. The channel
assignment scheme is presented in Section 4.5. Our model uses the 802.11a band because of
its (1) high bandwidth, (2) 24+ non-overlapping channels for assignment: original 12 channels
and another 12 channels approved in 5.47 to 5.725 GHz Band [106].
• Each node is equipped with two radios with one for transmitting (sending) data while the other
for receiving data. A testbed of such multi-channel and dual-radio wireless network is given
in [104].
• When multiple nodes send streams to one receiving node, the channel contention is eliminated

66

by the time division multiple access (TDMA) based scheduling, where the bandwidth is dynamically allocated to the senders. Contention based 802.11 CSMA/CA reduces the achievable
bandwidth and also makes bandwidth estimation difﬁcult. A testbed with similar local TDMA
scheduling is presented in [105].
• Similar to the 15-radio testbed in [103], the BS has adequate radios to support streams aggregated from SN.
• We adopt a coarse-grained piecewise mapping function between distance and link bandwidth
based on the modulation rate, because a precise mapping is often inaccurate in practice due to
multi-path fading and attenuation variation.
The BS is able to collect the current SN positions and the obstacle distribution in the environment, which enables our centralized solution to R2 BS. Similar to previous centralized relay
placement schemes [43, 47, 49, 51–53], such an approach facilitates graph theoretic modeling. It
also avoids the local data exchange and local suboptimal results in a distributed manner. Besides,
it ﬁts the multi-robot search and rescue applications of our problem in mobile networks for video
aggregation: the BS will remotely control robots and collect position and obstacle information
anyway [55].

4.2.3

Mapping of Range and Rate

We present a coarse-grained piecewise mapping function between distance and link bandwidth (capacity) based on the modulation rate, given that (1) the TDMA scheduling eliminates interference
between multiple senders to the same receiver; (2) the multi-channel and dual-radio framework
eliminates the interference between different links.

67

A simple measurement in the targeted placement environment can tell the minimum link bandwidth and the maximum range for each modulation rate. The link bandwidth and the range should
sustain at least 85% (a safety ratio) of the total measurement time. In a more dynamic environment,
this ratio is set higher to be more conservative. Due to limited space we leave the analysis on its
optimal value in future work.
We adopt the measured data in Table 4.1 from a real testbed measurement conducted by Atheros
researchers in [1] with Atheros 802.11a in an ofﬁce environment. Because the data describes the
averaged performance, we also conservatively adjusted the safe ranges as 85% of the original ones.
Different settings and hardware require remeasurement, which only affects the data in Table I but
not the proposed algorithm.
Hence, given a link e(u, v) with sender u and receiver v, the function ω(B) = R maps link
bandwidth from range while ω −1 (R) = B gives the inverse mapping. Additionally, B and R
denote the link bandwidth (capacity) vector and range vector in the table respectively.
Modulation
rm (Mbps)
6
12
18
24
36
48
54

Rate,

Minimum Link Bandwidth
(Capacity), B(Mbps)

Safe Transmission Range,
R(ft), α = 0.85

5
6
10
17
18
23
25

191
148
115
75
72
24
20

Table 4.1. Modulation rate vs. link bandwidth (capacity) vs. transmission range in 802.11a [1].

68

4.2.4

Discussions

The above measurement should be conducted in the target environment; In this paper, the obstacles
are the ground level ones mainly serving as the forbidden areas for relay placement, therefore
having little impact on the mapping so that the mapping is effective in the relay placement. In
future work, we would like to cope with the impact of different obstacles to this mapping with two
proposed solutions. The ﬁrst one is based on a recent work [107] which uses pure measurement
to predict effectively the best modulation rate and achievable link capacity in their testbed. To
tackle the frequency-selective fading due to multipath, the authors in [107] employed the subcarrier
channel state information (CSI) to compute the total bit error rate (BER). Here, we can measure
the difference of CSI with and without a typical obstacle, e.g. a wall. Because CSI can predict the
link performance and the obstacle distribution is known, we can adjust the new mapping with the
obstacle’s impact before the relay placement. A similar idea of modeling obstacle effect to predict
signal attenuation is presented in [108].
The second proposed solution is to adjust the relay positions after placement if the measured
link capacity is deviated from the mapping. This solution is more appropriate when relays are
mobile devices such as mobile sensors or robots. When mobile relays move towards the computed
initial relay positions, they can keep sending measurement packets as they move and collect CSI to
maintain a database for link capacity with positions along the paths. Relays can update the target
positions to adjust for radio irregularity and other dynamics.

69

4.3

Problem formulation

Given the system model, we model R2 BS by a new variant of the Steiner tree problem called
heterogeneous bandwidth Steiner routing problem (HBSR) with minimum Steiner points. HBSR
can be described as follows. Given
• a region RG with an obstacle-cell subset;
• a ﬁnite set of n terminal points including one base terminal (BS) and n − 1 sending terminals
(SN) with a uniform ﬂow sending rate rs to the BS;
• mappings of allowed ﬂow sizes (link bandwidth) inversely proportionate to edge lengths;
• bandwidth constraint: the sum of link utilization ratios of all incoming edges at each SN or RN
is less than one;
• placement constraint: no relay is placed on obstacles;
to ﬁnd a directed Steiner tree T (VT = {SN ∪ RN ∪ BS}, ET ) that uses Steiner points (RN) to
connect all sending terminals to the BS with a valid routing path from each SN to the BS, such that
the number of Steiner points in T is minimized. Mathematically, HBSR is

70

Minimize |RN|,
S.T. ∃ path(V ), V = (i, v1 , ..., vn , BS), ∀i ∈ SN, vi ∈ N,
dist(vj , vj+1 ) ≤ max{Ri }, ∀vj ∈ V, j ≤ n,

(4.1)
(4.2)
(4.3)

Be = ω −1 (min{Ri }), Ri ≥ dist(e),

(4.4)

Ue =

(4.5)

rs (f )/Be , ∀ ﬂow f on e,
f

Ue ≤ 1, ∀v ∗ ∈ N, ∀e ∈ ET ∧ v = v ∗ ,

(4.6)

e(u,v)

position(i) = obstacle, ∀i ∈ RN,
∀Ri ∈ R,

∀e ∈ ET ,

(4.7)
(4.8)

Where N = SN ∪ RN. Equations (2) and (3) show the a valid routing path from each SN to the
BS with relays under the communication range. Equations (4)-(6) give the bandwidth constraint.
Equation (7) provides constraints so that the relays cannot be placed at the obstacle cells.

4.3.1

Challenges

We ﬁrst prove that the HBSR problem is NP-hard.
Theorem 2. The HBSR problem is NP-hard.
Proof. We prove the theory by contradiction. Suppose we have a polynomial solution to this problem, by relaxing the constraint by giving an inﬁnite link capacity and a single transmission range,
the problem becomes the Steiner minimum tree Problem with minimum number of Steiner points

71

(SMT-MSP) [43], which will then be polynomially-solvable by our solution. This contradicts the
fact that SMT-MSP is NP-hard [43], and this completes the proof.
Another challenge is to solve the problem that the heterogeneous range and rate adds to the
relay placement’s complexity and substantially increases the solution space for possible relay positions. We need to determine whether we should place relays on SN’s direct paths to the BS or
select some other positions to let SN share relays with aggregated ﬂows. With uniform range and
rate, the relay placement in [52] greedily aggregates ﬂows at the earliest possible time, enabling
multiple senders to share relays to reduce the relay number.
Such a method is no longer feasible due to the following two reasons. First, with only one radio
for incoming trafﬁc, ﬂow aggregation can cause disconnections by reduced transmission ranges resulting from the increased link capacity requirement. Second, the ﬂow aggregation’s effect on the
number of relays becomes complex: Aggregated ﬂows demand more bandwidth, which reduces
the effective transmission range and leads to a denser relay placement that compromises its beneﬁt. Hence, ﬂow aggregation does not necessarily reduce the relay number and it is important to
evaluate its impact.

4.4
4.4.1

Relay Placement and Routing
General Procedure

We present an efﬁcient polynomial-time heuristic that places relays layer by layer such as the
breadth-ﬁrst search (BFS) from SN to iteratively approach the BS. First, we obtain the ﬁrst layer
nodes from SN with the ﬂow aggregations expected to reduce the number of relays (refer to Sec-

72

tion 4.4.3).
Second, with the ﬁrst layer nodes as the current layer, we call Alg. 10 for placing the new layer
nodes to approach the BS (refer to Section 4.4.4). Similar to BFS, we only place the single-hop
relays for all current layer nodes to be the next layer, rather than placing multiple relays for a single
node. The new layer nodes not in range of the BS will become the next round current layer. We
continue the loop of: (1) calling Alg. 10 to generate the next layer; and (2) using the new layer
to replace the current layer. The loop breaks when the current layer becomes empty. In addition,
routing paths are generated when the ﬂows are aggregated or forwarded to the next layer.

4.4.2

Evaluating Flow Aggregation’s Impact on Relay Number

Basic Idea: Rather than greedily aggregating ﬂows, we now evaluate whether aggregation is expected to reduce the relay number under the bandwidth constraints. We conduct aggregation only
when the aggregation is expected to reduce relay number. We ﬁrst give the following three deﬁnitions.
Deﬁnition 5.1: The bandwidth-sufﬁcient (communication) range to support k ﬂows R(k) is the
maximum range mapping to the (minimum) link bandwidth more than k · rs :
R(k) = ω(min{Bi }),

∀Bi ∈ B ∧ Bi ≥ k · rs

(4.9)

Note that Eq. 4 and Eq. 4.9 are not in a loop of computing range and rate. Eq. 4 is used to compute
the expected bandwidth when an edge length is known. Eq. 4.9 is used to compute the expected
edge length when its carried ﬂow rate is known.
Deﬁnition 5.2: We propose a metric called expected relay count (denoted by X). X(v, k)
predicts the relay number from v to BS when carrying k number of ﬂows. In an obstacle free or
73

sparse region, an approximate prediction is:
X(v, k) =

d(v, BS)
R(k)

(4.10)

We can obtain a more accurate X(v, k) by using A∗ search to ﬁnd the shortest obstacle-aware path
and use its length to replace d(v, BS).
Deﬁnition 5.3: We deﬁne a star (denoted by Si (i, Li )), or a star subgraph structure, to serve as
the unit for ﬂow aggregation. A star graph Si (i, Li ) is a complete bipartite graph K1,|L | , or a tree
i

with one center vertex i and the remaining vertices to be the leaves Li .
We deﬁne that the star leaves are the stream senders and the star center is the stream receiver
or the aggregation destination in the star. Star Si = (i, Li ) has |Li | number of leaves sending ﬂow
to center i, the aggregation point.
Recall in the system model that TDMA scheduling eliminates the interference inside a star
when leaves share a channel in transmission. We say two stars Si and Sj are compatible, iff they
have distinct leaves and centers. The channel assignment scheme ensures no interference between
stars.
Deﬁnition 5.4: Given the star subgraphs and expected relay count, we propose the reduction
index (denoted by δ(S)) to be the expected reduced number of relays per leaf by a star aggregation.
Namely, to compute (α − β)/|L(i)| in Si :
• α: Expected number of relays used when relays are placed on individual path to the BS without
aggregation: sum of the star leaves expected relay count.
• β: Expected number of relays used when relays are placed on the aggregation path: potential
“denser” placement due to increased carried ﬂow size.
An aggregation on star S is beneﬁcial when it is expected to reduce the relay number (δ(S) > 0).
74

A precise description of δ computation is given in the following sections. Besides, an illustration
of the star and δ is given in Fig. 4.1.

Star Center

δ(S)=(∑

-∑

-1)/|L(i)|

Star Leaf

Star
S(i,L(i))

Aggr. Relay
Non-Aggr. Relay
Aggr. Path
Non-aggr. Path
BS

BS

Figure 4.1. Star and the reduction index illustration. In δ(S), the underlined “-1” will be applied
when the center is an extra relay we need to place: in placing the new layer node. It will not be
applied when the center is an existing node: in aggregation in SN.

75

SN
RN

0

6

Obstacle

Bandwidth
Allowed
Leaf:

0
4

2

11

3

9

14
BS

2
Leaf:

4

12

Candidate
Leaf:

1

3

1

8
13

10

5
5

(a) Relay placement example: ﬂow aggregation in SN.

(b) Leaf selection.

Figure 4.2. Illustration of relay node placement. (Uniform sending rate rs =3Mbps)
76

0

SN

2Mbps

8Mbps

RN
4

Obstacle

7

m

8

n

9

p

2
1

11

Current Layer
BS

New Layer

(a) Select new layer position as star center for aggregation.

13

15

14

12

10

6

BS
(b) Relay placement example: new layer relay placement.

Figure 4.3. Illustration of relay node placement (Continued). (Uniform sending rate rs =3Mbps)
77

3

Terms

Deﬁnitions

HBSR
SN, SN
RN, RN
rs
Be
Ue

The problem of heterogeneous bandwidth Steiner routing.
Sending terminals (stream sending nodes).
Steiner points (relay nodes).
A uniform single ﬂow sending rate at each SN.
Achievable bandwidth based on distance of link e.
e’s link utilization ratio: its carried ﬂow rate divided by its bandwidth.
Bandwidth-sufﬁcient range for k number of ﬂows.
link bandwidth, communication range vectors and their mapping
function from Table I.
Expected relay count for v with k ﬂows.
A star with center i and leaves L(i). Leaves are the stream senders
and the center is the stream receiver.
(Relay) reduction index by a star S.
The star vector in SN, the candidate star vector, the ﬁnal compatible star vector for channel assignment.

R(k)
R, B, ω
X(v, k)
S(i, L(i))
δ(S)
Ssn ,Sc ,S

Table 4.2. Notations in HBSR.

78

4.4.3

Flow Aggregation in Sending Terminals SN

Algorithm 9: Selecting leaves for a node i with maximum reduction index.
1 Input: Node i. Output: Leaves L(i) with reduction index δ(S(i, L(i)).
2 Form an i’s candidate leaf set by node j in current layer satisfying: (1) farther from BS than
i. (2) j is in the bandwidth-sufﬁcient range of i.
3 Compute bandwidth Be for each link whose sender is in the candidate leaf set and the
receiver is i using Eq. 4.
4 Sort the candidate leaf set by distance to i in ascending order.
5 Add each node j ∈ i’s candidate leaf set to a bandwidth-allowed leaf set BL(i) in order,
until the sum of eji ’s link utilization ratio is greater than 1: Eq. 6 is violated. Each time
when a new node is added: update reduction index by computing δ(S(i, BL(i))) as in
Eq. 4.11.
6 i’s leaves Li is set as the BLi when it has the maximum reduction index.
Main Procedures
• For each i ∈ SN not in 1-hop bandwidth-sufﬁcient range of the BS, we form a star with center
i, select its leaves and compute the reduction index δ by calling Alg. 9 to evaluate how much
“beneﬁt” we can obtain if using i as the aggregation point to aggregate ﬂows with different
leaves.
• Given all the possible star candidates, we have a loop of selecting the star with the maximum
reduction index and conduct aggregation until the reduction index of the star is negative. (With
non-negative reduction index, aggregation never increases the number of relays).
• The remaining nodes not from the selected stars, along with selected star centers, serve as the

79

ﬁrst layer node. They will be the input of Alg. 10 for the next step. All selected stars are
inserted into a star vector in SN, or Ssn .
• For each selected star with center i, we also transfer the ﬂows from leaves to i and insert i to
the routing path (relay path) for each leaf.
In Alg 9, the reduction index δ(S(i, BLi )) is computed by:

δ(S(i, BLi )) =

j∈BLi ∪i

X(j, 1) − X(i, |BLi | + 1)
|BLi |

(4.11)

Example of Leaf Selection: We illustrate reduction index computation with Fig. 4.2(b). For n1 ,
its candidate leaf set has 5 nodes: {n4 , n0 , n2 , n3 , n5 }, which are farther from the BS than n1 is.
By greedily selecting nodes from the candidate set in ascending order to the BS, only three nodes
are allowed before the capacity is full. Besides, we discover that δ reaches its maximum as 0.5
when only the ﬁrst two leaves are used. Therefore, Ln1 ’s ﬁnal leaf set has two nodes: n2 and n4 .
Example of Aggregation: We illustrate the ﬂow aggregation in SN in Fig. 4.2(a). Each node
computes leaves and the reduction index δ. The node with maximum δ node n5 is chosen (δn5 = 2)
to be aggregated with ﬂow from n3 . With n5 and n3 eliminated, δ is recomputed for the rest nodes.
Node n4 with maximum δn4 = 1 is selected as the destination for ﬂows from n0 and n2 . The
aggregation terminates as the rest of nodes n1 and n6 have maximum δ < 0.

4.4.4

New Layer Relay Placement with Flow Aggregation

Overview: Given the ﬁrst layer node as the current layer, the next layer nodes are placed to approach the BS. A new layer node is placed at the aggregation point to approach the BS if the
ﬂow aggregation is expected to reduce relays. Otherwise it is placed to be closer to the BS by its

80

bandwidth-sufﬁcient range, on the direct path from the current layer node to the BS. The major
steps are in Alg. 10. Alg. 10 calls Alg. 11 to compute the next layer candidate relay positions.
They are the potential aggregation destinations given the current node pairs.
Select Compatible Stars with Maximum Sum of Reduction Index: In Alg. 10, given the candidate star vector Sc computed by calling Alg. 11, we need to select a subset of stars with the
maximum sum of star’s reduction index to form a ﬁnal star vector S. A new layer relay will be
placed in the center at each star in S. The stars in S must be compatible because they cannot
share leaves or centers since a ﬂow can only be aggregated to one destination under the bandwidth
constraints.
The problem is modeled as the NP-hard [109] maximum weighted set packing problem, which
is deﬁned as follows: Given a ﬁnite set and a list of subset, ﬁnd the disjoint subsets with maximum
sum of weight. In our problem, the ﬁnite set is the set of all the leaves of stars in Sc . Each star is a

81

subset including its two leaves, and the star’s reduction index is the weight of the subset.
Algorithm 10: New layer relay placement with ﬂow aggregation.
1 Input: Current layer nodes. Output: New layer nodes; routing paths.
2 Form a candidate star vector Sc by a hypothetical placement of center vertex as destination
for each pair of nodes in current layer. Call Alg. 11 k times (k is the number of nodes in
2
current layer). Use each node pair to be Alg. 11’s input.
3 Select a ﬁnal star vector S with the maximum sum of reduction index from Sc : Iterate
through Sc ’s powerset, ﬁlter out the incompatible subsets, and obtain the compatible subset
with maximum of the sum of reduction index. Denote the resulting star vector S.
4 New layer is set by the following two types of nodes: (1) Centers in S; (2) New nodes
placed for non-aggregated ﬂows for rest of the current layer nodes at bandwidth-sufﬁcient
range on the obstacle-aware paths to the BS by A* search.
5 Flows and routing paths are updated similar to the procedure in Section 4.4.3.
6 Links with non-aggregated ﬂows (a star with 1 center and 1 leaf) are also inserted into S.
Besides, Ssn is appended to S.

82

Algorithm 11: Choose new layer node position for aggregation.
1 Input: Leaf positions m, n. Output: A candidate star S with center position p and
reduction index δ(S(p, L(p))) , where L(p) = {m, n}.
2 Obtain range vectors Rm ⊆ R, Rn ⊆ R constrained by their bandwidth requirement for the
carried ﬂow sizes.
3 Compute Bandwidth Be for links with length equal to each range R ∈ Rm ∪ Rn by Eq. 4.
4 Test each pair < i, j > ∀i ∈ Rm , j ∈ Rn . When (1) total ﬂows do not exceed the shared
bandwidth: Eq. 6 is not violated; and (2) valid overlapping area exists for range disks m and
n: The closest position p to the BS in the overlapping area is saved as a candidate star
center for this pair.
5 Final center p is the closest position to the BS among all candidate centers. Form S(p, Lp )
with leaves Lp = {m, n}.
6 Compute reduction index by Eq. 4.12. Add S(p, Lp ) to the candidate star vector Sc if
δ(S(p, Lp )) > 0 (Not beneﬁcial stars cannot be candidates: aggregation never increases the
number of relays).
Due to the NP-hard nature of this problem, we compute the powerset to try all possible cases to
obtain the optimal result when the input size is less than a threshold k: |Sc | ≤ k. (The powerset of
a set is the set of all its subsets.) If |Sc | > k, we iteratively greedily select stars with the maximum
reduction index to form S . In the simulation process, we set k = 12 and ﬁnd that all our test cases
have |Sc | < k and the results are computed efﬁciently.
Choose the New Layer Node Position for Aggregation: In Alg 11, the reduction index

83

δ(S(i, Li )) is computed by:
X(j, |fj |) − 1 − X(i,
δ(S(i, Li )) =

j∈Li

|fj |)
j∈Li

|Li |

(4.12)

where fj is the ﬂow size carried by j. Note that the ﬂexible position of the star center is the main
difference compared to the aggregation in SN. The star center p is generally the closest position to
the BS in the overlapping area of range disks of i, j. Note that it is possible all range combinations
fail to provide bandwidth adequacy after aggregation. In addition, the formed star S is added to Sc
only when beneﬁcial: δ(S) > 0.
Example of Choosing New Layer Node Position for Aggregation: Fig. 4.3(a) illustrates Alg. 11.
Given a pair of current layer nodes m, n with fm =8Mbps, fn =2Mbps, the range sets Rm , Rn are
known. Each pair of ranges for m, n are tested until we ﬁnd the ﬁnal position p. Note that p is
m
n
not placed in m’s out-most disk because the maximum ranges for Rmax = 115ft, Rmax = 191ft

cannot be used together: They exceed the bandwidth with sum of link utilization ratio

U =

8/10 + 2/5 = 1.2 > 1.0.
Example of Aggregation: Fig. 4.3(b) illustrates placing new layer relays with ﬂow aggregation.
While n0 and n4 are too far apart to be aggregated, n7 and n8 are in range to aggregate each of its
ﬂow 3Mbps to n9 with 6Mbps. In addition, n1 ’s 6Mbps ﬂow, including that from n2 , is aggregated
with n3 ’s 3Mbps ﬂow to n6 .
Example of Relay Density Variance: Both Fig.4.2(a) 4.3(b) show relay density variation among
paths with different ﬂow sizes. In Fig. 4.3(b), more relays are placed on path from n6 than that
from n9 to the BS. Likewise, relays are placed more sparsely for a single ﬂow in path from n6 to
the BS compared with other paths in Fig. 4.2(a). To sum up, ﬂows are aggregated when they are
expected to reduce relay number in placement.
84

4.4.5

Upper Bound of Approximation Ratio

We derive the upper bound of the approximation ratio of our solution to HBSR. First we deﬁne
some notations. R gives the transmission range corresponding to a single ﬂow rate rs from each
SN. Furthermore, Bm represents the maximum link bandwidth Bm = maxB ∈B {Bi }, i.e., Bm =
i
25Mbps according to Table 4.1. A maximum degree in a graph G is: Δ(G) = max{degG (v)|v ∈
V (G)}. A degree of a vertex v is the times v is used as an end vertex of an edge in the graph.
We denote n, ns , nd , and nopt are the respective relay number obtained by: (1) algorithm
for HBSR; (2) S-MST: the Steinerized minimum spanning tree [91] with a uniform range R not
considering the ﬂow constraint; (3) DT: direct tree, or the simple aggregation tree (star graph with
center BS) where all ﬂows from SN are directly relayed to BS without aggregation; and (4) Topt :
An optimal Steiner tree with ﬂow constraint and heterogeneous ranges that requires minimum
number of relays. All four schemes except (2) satisfy our problem statement.
Besides, we use MST to denote the minimum spanning tree for SN and BS. Note that DT and
MST are two very simple tree structures easily obtained when given the input of SN and BS. We
deﬁne κ = nd /ns =

e∈E(DT ) e/R /

e∈E(M ST ) e/R , where κ is the ratio of relays size

for DT over that of MST with uniform range R. Thus, κ is relevant to SN and can be directly
obtained from the input of HBSR.
Theorem 3. The approximation ratio of our relay placement algorithm is no greater than κ · (1 +
Bm /rs ). In an environment where obstacle distribution does not affect the triangular inequality,
the ratio is no greater than κ · min{5, 1 + Bm /rs }.
Proof. With an optimal tree Topt , we duplicate each edge and build an Eulerian tour such that
every Steiner point appears at most Δ(Topt ) times in the tour while every terminal point appears
85

exactly once. Removing one (or more) edge in the tour will give a spanning tree T where Steiner
points have degree at most two. Its Steiner point size n(T ) is no more than Δ(Topt ) times in Topt .
Because ns is from S-MST: a minimum spanning tree with relays on uniform non-shortened edges
for single ﬂows. Clearly, we have:

ns ≤ n(T ) ≤ Δ(Topt ) · nopt

(4.13)

With κ = nd /ns and the fact that ﬂow aggregation guarantees n ≤ nd , we have:

n ≤ nd ≤ κ · Δ(Topt ) · nopt

(4.14)

n/nopt ≤ κ · Δ(Topt )

(4.15)

Lemma 3. Every Steiner tree that satisﬁes the ﬂow constraint must have its maximum degree
Δ(T ) ≤ 1 + Bm /rs .
Proof. For a vertex, its incoming degree is the same as the number of incoming ﬂows for aggregation, which is constrained by the maximum link bandwidth Bm . As we allow only one outgoing
link, the total degree is at most Δ(T ) ≤ 1 + Bm /rs .
Lemma 4. There exists a shortest optimal Steiner tree Topt whose maximum degree is less than
or equal to ﬁve, i.e., Δ(Topt ) ≤ 5, in an obstacle-free area or obstructive area where triangular
inequality holds [91].
From Lemma 3 and 4, Δ(Topt ) = min{5, 1 + Bm /rs } in obstacle free area or obstructive
area where triangular inequality holds. Otherwise: Δ(Topt ) = 1 + Bm /rs . Replacing Δ(Topt )
concludes the proof.

86

4.4.6

Extension

Theorem 4. Our solution to HBSR is extensible to deal with non-uniform ﬂow sending rates rs
from SN.
Proof. In the current solution, the ﬂow aggregation in SN assumes each ﬂow sending rate is uniform, while the new layer node placement already assumes different ﬂow sizes after possible aggregations in SN. The major changes to support non-uniform sending rates rs are as follows. (1)
Change from the number of carried ﬂows to the sum of all ﬂow rates on a link in Eq. 4.11 and 4.12.
(2) The expected relay count needs to be updated with a new bandwidth sufﬁcient range in Eq. 4.9
mapping to the minimum link bandwidth more than

rs rather than k · rs . (3) The sorting in step

3 in Alg. 9 is now based on the ascending order of link utilization ratio rather than the distance to
BS. These changes enable the reduction index computation with heterogeneous sending rates and
this completes the proof.

87

4.5

Channel Assignment

Algorithm 12: Channel assignment.
1 Input: Star vector S. Output: A channel assigned for each S ∈ S.
2 Construct star reduced graph (SRG) Gsrg (V, E) from S.
3 Construct link contention graph (LCG) Glcg (V, E) ← Gsrg (L(V ), L(E)).
4 Compute channel distances for each e and update E in Glcg .
5 Vertices Vtmp ← V in Glcg .
6 while Vtmp is not empty do
7

i∗ ← argmaxi∈V

8

Assign least unused channel ID to Si∗ . Remove i∗ from Vtmp .

tmp

j∈Vtmp ∧∃eij weighteij .

Although relays are placed with selected ﬂow aggregation and varying distances according to
different ﬂow sizes, bandwidth adequacy cannot be satisﬁed without proper channel assignment
to eliminate the inter-star interference. We model the channel assignment problem as the NPhard bandwidth coloring problem [110] for a minimum total number of channels. Here, a channel
represents the color. Bandwidth coloring problem generalizes the classical vertex coloring problem
with the edge weight constraints on color distances of adjacent vertices. Such modeling enables
us to tackle the problem of out-of-band (OOB) emission (or the adjacent channel interference with
power leakage when radios are placed very close (less than 1m) [103]). To overcome this problem,
we double the channel distance for the two radios at the same node, which is modeled by the
doubled weight. A greedy algorithm is designed to choose the vertex with the maximum sum of
adjacent edge weights (Detailed procedures are in Alg. 12).

88

4.6

Performance Evaluation

Summary
• To evaluate the quality of the proposed method (for simplicity, we call our method HBSR),
we compare HBSR to the widely used minimum spanning tree based approximation for relay
placement.
• To evaluate the beneﬁt of considering heterogeneous range and rate, we compare HBSR to the
uniform range and rate based relay placement.
• In addition, we also apply HBSR to a coordinated mobility model where fewer relays can
enable more robots to conduct search and thus increase the mobility efﬁciency. The mobility
model is a multi-robot area exploration strategy with video aggregation [52].
We use a C++ simulation program with the Open and Garden environments as in Fig. 4.5(b),
where obstacles are denoted by black cells. Both environments are represented by 150 × 150 grid
cells with cell edge length of 6ft.
Due to the exponential nature of HBSR, and the highly complex linear programming formulation for heterogeneous ranges and rates, we did not directly compare the results with the optimal
or its lower bound. Instead we provided the upper bound of the approximation ratio to the optimal.
We will carry out the direct comparison to optimal in future work.

4.6.1

Comparing to Minimum Spanning Tree based Relay Placement

First, we compare the required relay number to a heterogeneous range and data placement scheme
satisfying the bandwidth requirement. It is built upon a widely used approximation algorithm
called the Steinerized Minimum Spanning Tree [91] (for simplicity we call this scheme S-MST)
89

Number of Relays

30

HBSR
S−MST

25
20
15
10
5
0

9

10
11
12
Num. of Sending Terminals

(a) S-MST fails when |SN| >12. rs =2Mbps.

Number of Relays

30

HBSR
S−MST

25
20
15
10
5
0

5

6
7
8
Num. of Sending Terminals

(b) S-MST fails when |SN| >8. rs =3Mbps.
Figure 4.4. (a)-(b): Compare relay number to bandwidth aware S-MST: Varied ﬂow sending rate
rs of 2-3Mbps.

90

Number of Relays

30

HBSR
S−MST

25
20
15
10
5
0

3

4
5
6
Num. of Sending Terminals

(a) S-MST fails when |SN| >6. rs =4Mbps.

(b) Open and Garden environment.
Figure 4.5. (a): Compare relay number to bandwidth aware S-MST: Varied ﬂow sending rate rs
of 4Mbps. (b): Obstructive environments.

91

25
HBSR

Number of Relays

UR2−6Mbps
UR2−12Mbps

20

UR2−18Mbps
15

10

5

4

6
8
10
Number of Sending Terminals

12

(a) Varying |SN|: 4-12.

35
HBSR
UR2−6Mbps

Number of Relays

30

UR2−12Mbps
UR2−18Mbps

25
20
15
10
5

360

450
540
630
720
Distance from SNs to BS (feet)
(b) Varied distance. |SN|=10.

Figure 4.6. (a)-(b): Compare relay number to uniform range and rate relay placement (UR2 ):
varied |SN| and distance to BS.
92

80

Number of Iterations

HBSR
UR2−6Mbps

70

UR2−12Mbps
UR2−18Mbps

60
50
40
30

12

14
16
Total Number of Robots

18

(a) Garden environment.

80

Number of Iterations

HBSR
70

UR2−6Mbps

60

UR2−18Mbps

UR2−12Mbps

50
40
30

12

14
16
Total Number of Robots

18

(b) Open environment.
Figure 4.7. (a)-(b): Compare exploration efﬁciency to UR2 based exploration by total number of
iterations.

93

for relay placement. We choose S-MST for comparison because there is no existing algorithm
exactly match our problem statement, but many solutions to the Steiner tree problem variants are
based on the minimum spanning tree [43, 47, 91, 111].
In S-MST, relay are added on the longer than R edges in MST to connect all terminals according to different ﬂow sizes (R is the bandwidth-sufﬁcient range). S-MST has a severe weakness of
overﬂow that our scheme does not have: When all ﬂows are aggregated to one SN and transmitted
to BS via a single edge on the MST, ﬂows may exceed the maximum link capacity (e.g. 25Mbps in
Table 4.1). Because of overﬂow and our interest to observe situations where bandwidth’s impact
is non-trivial, we test on relay number with a ﬁxed range of distance to the BS and use the highest
four numbers of SN below overﬂow with varying sending rate rs from 2-4Mbps.
All relay number tests in Section 4.6.1,4.6.2 are run 200 times to obtain the average in the
Garden environment. We found that our algorithm is efﬁcient and no instance runs more than one
second. The 95% conﬁdence interval is shown by the error bars. We use the polar coordinate
(R, θ) to represent SN positions with the BS at (0, 0◦ ). R is random uniformly distributed in
[R0 −β, R0 +β]. When comparing with S-MST, we set R0 =480ft and β=240ft, and θ is uniformly
distributed in [0◦ , 90◦ ]. Fig. 4.4 and 4.5 show HBSR reduces the number of relays by 53.1%,
41.0%, and 38.6% on average. For the situations with the highest two SN numbers before overﬂow,
the relay number reduction is more notable, which is 60.4% on average.

4.6.2

Comparing to Uniform Range and Rate Relay Placement

Second, we compare the number of relays to the uniform range and rate (UR2 ) scheme in
[52] with two test sets: (1) Varying size of 4-12 SN with ﬁxed range of distance to the BS

94

(R0 =480ft and β=240ft). (2) Fixed size of 10 SN with varying ranges of distance to the BS
(R0 ∈ {360, 480, 600, 720} (ft)); rs is set as 3Mbps hereafter. As shown in Fig. 4.6(a) 4.6(b), our
scheme reduces the number of relays on average by 25.4%-39.0% and 25.5%-36.3% respectively
in the two test sets compared to UR2 schemes with range corresponding to 6-18Mbps modulation
data rates. (UR2 with rates above 18Mbps are not compared as they need notably more relays.)
These results demonstrate the beneﬁt of considering heterogeneous range and rate in relay placement because of its ﬂexibility in adapting to different bandwidth and range requirements.

4.6.3

Evaluating HBSR’s Impact on Mobility Efﬁciency

95

Unexplored
Area

Frontier
FN Nodes

FN
RN

Relay
Nodes

FN
Explored
Area

RN
FN
RN

RN

Obstacle
(Wall)

RN
Base
Station

Figure 4.8. Stream aggregation for area exploration.
96

We also apply HBSR to a coordinated multi-robot exploration strategy with video aggregation
[52]. An screenshot of the exploration with HBSR is shown in Fig. 4.8. Relay placement is a
critical component in its iterative mobility model. In each round, a portion of the robots will be the
relays and the remaining will be the “frontier” robots to explore the area. Less relays can enable
more frontier robots to conduct search and thus increase the mobility efﬁciency. We compare the
exploration-efﬁciency difference when using (1) HBSR vs. (2) UR2 to be the relay placement
component. The S-MST is not evaluated here due to its overﬂow problem.
We measured the number of iterations for exploration from a clustered start to 95% of explored area. Each robot has a sensing range of 48ft. Fig. 4.7(a) 4.7(b) demonstrate that the decrease in movement iteration number is on average 18.9%-32.1% and 20.1-34.3% compared to
UR2 6-18Mbps for the garden and open environments respectively given the total robot number
of 12,14,16,18. Note that the improvement is also inﬂuenced by this speciﬁc exploration model
in [52]. In future work, it is desirable to devise a heterogeneous mobile robot exploration model to
fully exploit HBSR’s beneﬁt.
The ﬁgures also show that a single range and rate choice has the least number of movement
iterations for a certain total robot number; however, exploration with this range and rate may not
have the least iterations for other total robot numbers. This fact also demonstrates that a single
transmission range based placement lacks the ﬂexibility to adapt to different node densities and the
total bandwidth demands.
Furthermore, Fig. 4.9(b) shows the FN numbers in the exploration progress with 18 robots.
With less relays, we successfully place more FNs than UR2 -12Mbps version in 21 out of 33 iterations (63%), which effectively completes the exploration at 33rd round, 10 rounds earlier than
UR2 -12Mbps. Besides, Fig. 4.9(a) shows the average/maximum number of channels assigned in
97

Number of Channels

18
Garden−Average
Garden−Max
Open−Average
Open−Max

16
14
12
10
8

12

14
16
Total Number of Robots

18

Number of Frontier Robots

(a) Assigned channel sizes in exploration process.

12
11
10
9
8
7
6
5
4
3
2
0

HBSR
UR2−12Mbps

5

10 15 20 25 30 35 40 45
Iteration Number
(b) |FN| as exploration proceeds.

Figure 4.9. Channel sizes in exploration; |FN| as exploration proceeds.

98

exploration for the two environments. Different environments do not have a signiﬁcant impact on
the channel size. The average/maximum number of channels is approximately 3 or 1 less than the
total node number, respectively.

4.7

Summary

In this chapter, we consider the heterogeneous link capacity and transmission range in the real-time
multimedia aggregation for mobile robot networks.
We formulate the problem as a new variant of the Steiner tree problem called the heterogeneous bandwidth Steiner routing problem (HBSR). We show HBSR’s NP-hardness and the upper
bound of our solution’s approximation ratio. Our solution to HBSR places relay nodes iteratively
and aggregates ﬂows when the aggregation is predicted to reduce the number of relays, reducing
relay number by an average of 44% compared to the widely used minimum spanning tree based
algorithm.
We also found that considering heterogeneous range and rate is beneﬁcial in relay placement
and signiﬁcantly reduces the number of relays compared to the uniform range and rate placement.
A single range and rate lack the ﬂexibility to adapt to different stream demands of rates and ranges.
Besides, HBSR improves the mobility efﬁciency in the multi-robot exploration task. In the next
chapter, we will introduce an alternative paradigm of online relay deployment to support remote
sensing and control in mobile wireless networks.

99

CHAPTER 5
STARS: Static Relays for Multi-Robot
Real-time Search and Monitoring

5.1

Preliminaries and Motivations

In the previous chapters, we attempt to reduce the the number of relaying robots to have more
frontier robots to explore the area, aiming to improve the efﬁciency in area exploration. However,
using expensive and powerful robots to merely serve as simple relays may not be a cost-effective
approach. Besides, it is extra cost for an increasing number of robots to “retreat” from frontier
areas to approach the base station to serve as relays. Furthermore, given a ﬁxed number of robots,
an increasing number of relay robots will ﬁnally prevent the frontier robots from moving forward.
In this chapter, we present a novel approach of using online relay deployment (deploying relays
at the same time as robots migrate) by mobile robots to support stream transmission to the base
station given a known environment. The motion planning to support transmission to the base
station with relay deployment heavily relies on a new variation of the traveling salesman problem.
100

Therefore, we ﬁrst introduce the theoretical problem. Then, we show its application in the tour
generation in the multi-robot search problem.
The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem with extensive applications. A variation of TSP that we address here is the minimum time
precedence constrained two traveling salesman (PC2TSP) from a given city. We ﬁrst introduce
the problem and then show its application.
PC2TSP can be stated as follows. Given 1) a ﬁnite set of cities C = {1, 2, ..., n} with each
city marked as a consumer, a supplier, or both, and each consumer city has its supplier city set,
2) the cost cij of traveling time between each pair of cities i, j ∈ C, cij and cji may differ, 3)
the precedence constraint that the arrival time plus waiting time at each consumer city is no earlier
than the arrival time of all its supplier cities, to ﬁnd two non-overlapping tours that allow waiting
time at cities and both start from the base city 1 to visit each of the remaining cities exactly once,
such that the maximum of the two tour times is minimized.
The problem is more challenging than other variants of multi-traveling salesman problem
(mTSP) in that a consumer city and some of its supplier cities may be visited by different travelers. Therefore, it is possible that a traveler arriving at a consumer city i must wait for the other
traveler to visit i’s supplier cities, introducing the dependency between travelers.
One interesting application of PC2TSP in mobile surveillance systems is the problem of minimum time two-robot real-time search with relay deployment (2RSRD), which is described as
follows: Given two robots, or mobile sensors, with ability of deploying relays as they search the
area, how to compute the moving paths for robots and the proper time and positions to deploy
relays along the movement path, so that i) robots can efﬁciently search the area with minimum
amount of time; ii) video streams from robots at any sensing position can be successfully transmit101

ted back to the base station (BS). Figure 5.1 illustrates the two robots in the search process. Any
stream transmission at the sensing positions is relayed by a subset of two relays in the middle.

Stream
Path
Relay
Position
Sensing
Position
Moving
Path
Base
Station
BS
BS
Figure 5.1. Two robots search the environment and deploy static relays as they travel along the
paths. The left robot transmits streams to the base station via the center relay deployed by the right
robot.

Similar to PC2TSP, 2RSRD implies a precedence constraint: When a robot conducts search and
video transmission at sensing locations, supporting relays must be deployed prior to the robot’s
video transmission, so that streams can always be transmitted back to the BS on a valid path.
Now that 2RSRD resembles PC2TSP, we model 2RSRD in part by PC2TSP as follows. The
mobile robots become the travelers. The sensing positions for robots to conduct search become
the consumer cities and the positions at which relays are deployed become the supplier cities.
102

For each sensing position modeled as a consumer city, its corresponding supplier city set is all of
its supporting relay positions that form a valid path to the BS. Therefore, as long as we have 1)
identiﬁed sensing and relay positions, and 2) assigned the precedence constraint that choose the
relay set for each sensing position as a valid path to BS, we can use PC2TSP to solve 2RSRD as
the ﬁnal step to generate tours.
By modeling in part by PC2TSP, we present STAtic Relay aided Search (STARS) to solve
2RSRD. STARS enables remote robotic sensing and control. It has extensive applications such
as reconnaissance, surveillance, search and rescue missions in dangerous and hostile areas. One
example is the robotic teleoperation and remote search tasks in the recent Japan earthquake debris
and radioactive environments. STARS substantially reduces cost by replacing expensive robots
by low cost static relays, compared to a homogeneous mobile robot system where robots have to
be the relays to transmit streams. Another beneﬁt is that STARS also enables the deployment of
static sensors to monitor the “suspicious areas” where the human operator and the computer system
decide that the targets may (re)appear after the robots migrate away. The details of how STARS
supports constant monitoring by static sensors is described in Section 5.6.2.
With this heterogeneous system of mobile robots, static sensors and relays, STARS has the
merits of both static sensors and mobile robots. Sensors are relatively inexpensive devices that are
good at constantly monitoring regions, but they require large quantities in deployment to cover the
area. Robots are more powerful to perform complex tasks but are considerably more expensive.
They are better suited for situations requiring a single time search and exploration process. Compared with homogeneous static sensor networks, the proposed method saves unnecessary sensors
because sensors only need to be placed as the suspicious area rather than the whole area. Compared with homogeneous mobile robot networks, our scheme has notably less cost but can monitor
103

suspicious area constantly thanks to the deployed sensors.
To the best of our knowledge, STARS is the ﬁrst of its kind to leverage online relay deployment
as a communication backbone to support real-time communication, remote control and sensing
with mobile robots and static sensors. The problem is motivated but has many challenges. We
discuss these challenges in Section 5.3.1.

5.1.1

Main Contribution

• We ﬁrst present a problem called precedence constrained two traveling salesman (PC2TSP).
We propose a near-optimal heuristic to PC2TSP to generate tours by clustering points, generating optimal single-traveler tours, and tour pruning and balance.
• To solve PC2TSP, we propose the tour validation and dependency checking scheme to detect
deadlock and self-ﬂipped cases that are invalid. It also checks the dependency on two tours
and adds necessary waiting time.
• To solve 2RSRD, we propose STARS, which divides the problem into two subproblems: 1)
preprocessing: identify visiting positions and assign the precedence constraint, which are
modeled by set cover, Steiner connected dominating set, and breadth-ﬁrst search; 2) tour
generation, which is modeled by PC2TSP.
To maintain consistency and show a valid application of PC2TSP, we present the solution of
PC2TSP in the context of STARS as tour generation. However, it can be used as a stand alone
solution to PC2TSP with minor changes given in Section 5.5. The rest of the paper proceeds as
follows. Section 5.2 introduces the system model. In Section 5.3, we formulate the problem and
discuss the challenges. Section 5.4 and 5.5 give the preprocessing and tour generation. Then,
104

several extensions are discussed in Section 5.6. Performance evaluation is in Section 5.7. Section
5.8 concludes the chapter.

5.2

System Model

Environment Model: We use a 2D occupancy map to model the environment as an unsearched
rectangle region R = X × Y with grid cells similar to that in [55]. The cell size equals to
the footprint size of the robot. A cell status includes searched, unsearched, and obstructed. An
obstacle cell cannot be visited by the robots nor can a relay be deployed on. Obstacles do not
affect communication but block the sensing range. We assume the obstacle distribution in the
environment is known. We would like to tackle the unknown or inaccurate obstacle distribution
in the future work. Base station BS is the control center where the human operator can remotely
monitor and potentially operate the robots if necessary.
Robot Model: The number of robots in our model is limited as two because the goal is to use
low cost static relays to replace high cost mobile robots. The two robots are denoted as a and
b. The solution is extensible to more than two robots, which will be discussed in Section 4. The
robots move at a constant speed where the acceleration and deceleration time is not considered.
Each robot has traveling, communication, and sensing capability. It scans the environment using
cameras and acoustic sensors with sensing range rs and communicates with other nodes with
communication range rc by a 802.11 radio, where rc >= rs . We denote the communication to
sensing range ratio as θ = rc /rs . Since only 2 robots are sending streams, we assume bandwidth
is adequate in transmission. The unit disk model is used for sensing and communication. As
robot’s sensing devices, such as laser ﬁnder and cameras, are more powerful than those in limited

105

capability sensors, the sensing range is more stable. A more sophisticated model may not be
necessary.
Search with Relay Deployment Model: The robots search the region by visiting a sensing position SP, where the robots stop and enter the search and transmit interval (STI) and the unsearched
cells in its covered area with radius rs will be marked as searched. The STI is for the robots to
sense the area and send video streams back to the BS. The ratio of searched cells out of total nonobstacle cells is denoted as θs . The completion of search is deﬁned by θs ≥ δs , where δs is a
search complete threshold, e.g. 99%. SP is the set of SPs whose visit complete the search. SP
includes the BS.
The robots deploy relays by visiting a relay position RP in the search tour. A relay is a nonmobile device with 802.11 for transmitting streams from a robot with same communication range
rc . A robot has a maximum carrying capacity of nr relays. We assume STI and relay deploying
time are negligible.
SP(a) and SP(b) denote the vector of SPs robot a and b need to visit; RP(a) and RP(b) denote the
vector of RPs a and b need to visit. Pa , Pb denote the ordered vector of sensing and relay positions
a and b traverse: Pa = SP (a) ∪ RP (a), Pb = SP (b) ∪ RP (b). Ta , Tb denote the tour a and
b traverse, or the vector of position and the waiting time w at each position: Ta = {Pa , w(Pa )},
Tb = {Pb , w(Pb )}. A path denoted by path(V) gives a route with an ordered vector of positions
of V=(v0 , v1 ,...vn ). ta and tb give the tour time in seconds, or the total time needs to traverse all
positions in Pa or Pb including the possible waiting time. t(i) gives the start of search time for
position i.
We compute the tour off line with the information of the environment before the actual search
starts. We do not model robots to come back to the BS immediately after the search is complete.
106

Because robots should remain in the frontier area for remote sensing.
Discussions: Due to its high complexity, the problem is modeled as above and we focus on the
tour generation. The model is easily extensible to consider a non-trivial STI and relay deploying
time, which will be discussed in Section 4. In the future, we would like to tackle: 1) the bandwidth
aware relay placement, 2) the probability based communication model, and 3) the online tour
adjustment with inaccurate initial obstacle distribution. Note that the ﬁrst two changes and most
parameters in the model only affect the ﬁrst subproblem in STARS and have no impact on the
solution to the second subproblem of tour generation. For the third change, we may recompute the
tour by updating the new data of obstacles as input.

5.3

Problem formulation

Given the system model, we formulate the problem and explain the basic idea.
Minimum time two-robot real-time search with relay deployment (2RSRD): Given a region R,
two robots a and b each with relay carrying capacity of nr , compute tours Ta , Tb to obtain the
minimum search time tab such that:
Minimize tab = max{ta , tb },

(5.1)

Subject to SP = SP (a) ∪ SP (b),

(5.2)

∃path(V ), V = (BS, rp0 , ..., rpn , i), ∀i ∈ SP,

(5.3)

dist(vj , vj+1 ) ≤ rc ,

∀vj ∈ V, j ≤ n + 1,

t(rpj ) ≤ t(i),
|RP (a)| ≤ nr ,

(5.4)

∀j ∈ 0, ...n,

(5.5)

|RP (b)| ≤ nr ,

(5.6)

107

Notations

Deﬁnitions

PC2TSP

Precedence constrained two traveling salesman:
the theoretical problem.
Two-robot real-time search with relay deployment:
the robotic search problem.
STAtic Relay-aided Search: our solution to
2RSRD, where the tour generation subproblem is
modeled by PC2TSP.
Search region.
Precedence constraint matrix.
Sensing position, relay position; their set.
The two mobile robots.
Base station.
The ordered vector of sensing and relay positions
a and b traverse.
Tours of robot a and b.
Tour times in seconds of robot a and b.
Relay deploying time at the relay positions.
The start of search time for position i.
Search and transmit interval when robots stops at
the sensing positions.
Steiner connected dominating set.
Robot’s relay carrying capacity.
Distance between i and j.
Communication and sensing range, and their ratio.

2RSRD
STARS

R
P
SP, RP, SP, RP
a, b
BS
Pa , Pb
T a , Tb
t a , tb
trd
t(i)
STI
S-CDS
nr
dist(i, j)
rc , rs , θ

Table 5.1. Notations in STARS.

108

Where rpi is a relay position in the path (rpi ∈ RP (a) ∪ RP (b)). Equation (2) indicates the
search is complete. Equations (3)-(5) give that for each sensing position i in a or b’s tours, there is
a valid path back to the BS at the time of t(i). Equation (6) gives the carrying capacity constraint.

5.3.1

Challenges

We ﬁrst prove 2RSRD is NP-hard and then show other challenges to directly solve the problem.
Theorem 5. 2RSRD is NP-hard.
Proof. Given an instance of a square region, we can exactly duplicate the region and put the duplicated copy on the right of the original one. With the BS on the bottom center of duplicated region,
minimum tab is achieved when both a and b traverse on its own half region the same way. This is
because any traverse on the other half part will increase tab . Therefore, a polynomial time solution in 2RSRD will lead to a polynomial solution to a single precedence constrained asymmetric
traveling salesman problem (PCATSP) on the positions. It contradicts to the fact that PCATSP is
NP-hard [112], and this completes the proof.
There are other challenges to directly solve 2RSRD other than its NP-hardness. First, the robots
may need to wait for each other if one relies on the other’s not deployed relay to transmit streams.
There is a dependency between both robots: One may have to wait for the other to deploy the
supporting relays. The dependency and waiting time make it challenging to directly apply linear
programming formulation to solve the problem.
Second, search time tab is affected by the robot’s relay carrying capacity and whether to have
a goal of reducing relay size. Suppose that relays are sufﬁcient, carrying capacity is inﬁnite,
and robots place a relay at every SP. As long as robots travel on consecutive SPs, the stream
109

transmission requirement is always met (recall rc ≥ rs ). The relay requirement will have little
impact on the tour generation. The problem is then simpliﬁed and less interesting to solve. On
the other hand, if RPs are only placed selectively (such as at only S-CDS positions as in Section
5.4.2), the tour computation is constrained by visiting the relay positions ﬁrst before visiting other
sensing positions that are supported by these relays.
Third, the precedence constraint is uncertain compared with that in PCATSP, where position i
preceding j is explicitly stated. 2RSRD requires that at least one valid relay path has been deployed
at the searching time on any SP. However, multiple sets of relays can fulﬁl this requirement. To
illustrate, there are 4 RPs as shown in Figure 5.2. When search starts at SP, at least one pair of RPs
(1,3),(2,4),(1,4),(2,3) is required to be deployed. The uncertainty makes the problem more difﬁcult
to deal with.
Therefore, to solve 2RSRD optimally, which is to ﬁnd all possible: 1) SPs that complete coverage, 2) RPs that cover all SPs (which is a S-CDS as we deﬁne below), 3) precedence constraints
that ensure the stream relay requirement, 4) partitioning of visiting positions, 5) permutation of
tours, and 6) adding waiting time for each pair of tours when dependency occurs.

5.3.2

STARS: STAtic Relay aided Search

Due to the problem’s high complexity, we propose a high quality heuristic called STARS, or the
STAtic Relay aided Search. It divides the problem into two subproblems: 1) preprocessing: identify
visiting positions and assign the precedence constraint, 2) tour generation, which is modeled by
PC2TSP.
We present a valid solution for the ﬁrst subproblem. We also show how our near-optimal so-

110

lution to PC2TSP is applied to solve the second subproblem of tour generation. Such division
separates the key tour generation problem from a speciﬁc region with different visiting position
selections, precedence constraints and robot carrying capacities. In future work, the tour generation is important to evaluate different schemes of selecting visiting positions and precedence
constraints, making it possible to ﬁnd the optimal visiting positions and precedence constraint.
The formulation for each part of the subproblems is as follows:
Problem 1a: Identify sensing positions: Given a region R, how to place a minimum number of
sensing positions SP that completes the search (Coverage requirement: searched cell ratio θs ≥
δs ):
Minimize |SP|,
Subject to
i∈SP

(5.7)

cellsearched (i) ≥δs · |cellnonobstacle R |

Problem 1b: Identify relay positions: As the robots visit all sensing positions, the area will
be fully searched. However, the video streams cannot be transmitted back to the BS unless a
path formed by relays always exists. RP forms a communication backbone. Without worrying
about the visiting sequence at this step, the backbone must at least “cover” all SP including the
BS. We assume the user would like to save relays and with such an attempt the carrying capacity
constraint is satisﬁed (Satisfying Eq.(6)). An extension to take advantage of extra relays under the
carrying capacity (difference of carrying capacity and the computed minimum number of relays)
is presented in Section 5.6.5. Hence, the problem is: given R and SP, how to place a minimum
number of relay positions RP that satisﬁes 1) each SP is either in RP or a neighbor of RP; 2) RP

111

includes the BS, and RP is connected:
Minimize |RP|,
s.t. i ∈ RP||dist(i, j) < rc ,

(5.8)
∀i ∈ SP, ∃j ∈ RP,

∃ path(V ), V = (v0 , ..., vn−1 ),
dist(vk , vk+1 ) ≤ rc ,

∀v0 , vn−1 ∈ SP,

∀vk ∈ V, k < |V | − 1,

BS ∈ RP
In addition, a simple extension to leverage the pre-existing relays is presented in Section 5.6.4.
Problem 1c: Assign the precedence constraint: Given R, SP, and RP, how to deﬁne a precedence constraint matrix P : pij , ∀i, j ∈ SP ∪ RP:
⎧
⎪
⎪
⎪1 position i precedes j
⎨
pij =
⎪
⎪
⎪
⎩0 otherwise
Validity: Matrix P is valid if and only if any tours on SP, RP satisfying P meet the constraints
deﬁned in Eq.(3)-(5).
Problem 2: Tour generation: Given R, SP, RP, how to ﬁnd two minimum time tours Ta , Tb
that satisfy P:
Minimize tab = max{ta , tb },

(5.9)

Subject to Pa ∪ Pb = SP ∪ RP,
t(i) ≤ t(j),

∀pij = 1

Rationale: Problem 1a is formulated by minimum |SP| as a heuristic because less visiting
positions may lead to a shorter total tour. Problem 1b is formulated to reduce the number of relays.

112

Problem 1c is to remove the uncertainty of precedence constraints for the tour generation. With
the result of problems 1a,1b,1c as input, the problem 2 is formulated to generate the tours.

5.4
5.4.1

Preprocessing
Identify Sensing Positions

Recall the problem formulation 1a in Section 5.3.2. We formulate the problem as the well-known
NP-hard set cover problem, which is to select a minimum number of sets so that the union of the
sets contains all the elements in the universe. Here, the search region is divided into grid cells.
With each cell as an element, all the non-obstacle cells become the universe. Each SP’s sensing
area is a set that contains some elements within sensing range, rs . Since the problem is NP-hard,
we leverage a heuristic modiﬁed from the triangle lattice pattern (TLP), which is proven optimal in
terms of the number of sensing disks to obtain full coverage [113] if the region is free of obstacle.
Alg. 13 describes the procedure.
Algorithm 13: Identify sensing positions for full region coverage.
Input: A region R.
Output: SP.
1 Follow the triangle lattice pattern to place SP on non-obstacle cells.
2 While θs < δs do greedily select a position i to cover a maximum number of uncovered
cells. Insert i into SP.
3 With an equal coverage, the position with minimum distance to the nearest SP neighbor is
selected.

113

5.4.2

Identify Relay Positions

Recall the problem formulation 1b in Section 5.3.2. We model the problem as the minimum Steiner
connected dominating set (S-CDS) problem.
Connected Dominating Set (CDS) problem is a classical problem in combinatorial optimization
with the following deﬁnition: Given a graph G = (V, E), ﬁnd the smallest subset S of vertices
that induce a connected subgraph and each vertex in V − S is adjacent to at least one vertex in S.
S-CDS is a generation of CDS where only a speciﬁed set R ⊆ V of required vertices has to be
dominated by a connected dominating set [114]. Given all non-obstacle cells in R as V . RP only
needs to cover SP, which is a subset of V . We require RP induce a connected subgraph because
streams from any vertex in SP is sent to the BS.
Differing from those formulations in previous chapters, this relay placement problem is not
modeled as the Steiner Minimum Tree with the Minimum Steiner Point (SMT-MSP) problem. The
reason is that a terminal point can always also serve as a Steiner point to connect to other terminal
points in SMT-MSP. However, in our application, the robots only pass the sensing positions once.
A sensing position (terminal point) cannot serve as a Steiner point (relay) unless a real relay is

114

deployed.
Algorithm 14: Steiner-CDS algorithm to identify relay positions
Input: SP.
Output: RP.
// 1. Obtain the dominating set (DS) on SP.
1 if |SP| < δds then
2

Obtain DS by the optimal DS ﬁnder.

3 else
4

Obtain DS by the greedy set cover with maximum nodes.
// 2. Apply Steiner tree approximation algorithm to connect DS.

5 Call Steinerized Minimum Spanning Tree [91] to connect DS. The newly added nodes are
RP2
6 Return RP = DS ∪ RP2 .
The basic idea is simple. First ﬁnd the minimum dominating set which may not be connected,
then add vertices to connect the dominating set. The details of the algorithm are shown in Alg. 14.
The algorithm is similar to the Steiner-CDS algorithm in [114]. The three major differences are:
First, we use an optimal dominating set (DS) ﬁnder (ﬁnding DS is NP-hard) when the size is
smaller than a threshold δds = 70 and use the greedy heuristic as in [114] when the input size is
larger. Leveraging a recursive algorithm with techniques such as node ordering, branch and bound,
and backtracking, the DS ﬁnder can compute up to 70 vertices to optimal in less than 1 minute on
a regular notebook, improving the S-CDS quality. DS is the overlapping set: DS= SP ∩ RP.
The second difference is that RP2 are placed on the shortest obstacle-aware paths computed
by A* search between its end vertices when necessary to avoid obstacles. A* search guarantees

115

the same optimal result as Dijkstra but is more efﬁcient. Because it reduces the searching space
compared to BFS using an admissible and consistent heuristic function which does not overestimate the distance to the goal [55]. Third, we always include the BS in DS because the BS belongs
to the backbone: BS ∈ RP.

5.4.3

Assign the Precedence Constraint

Algorithm 15: Assign parentIDs and the precedence constraint
Input: SP, RP.
Output: P.
// 1. Assign parentIDs. The BS has an invalid parentID(-1).
1 Breadth-ﬁrst search on RP to obtain the RPlevel in BFS. Assign a parentID in BFS for each
relay according to BFS queueing order.
2 For each i ∈ SPpure , insert all i’s 1-hop RP neighbors into its parent candidate set.
3 Loop through i ∈ SPpure , if i has a single parent candidate j then
4

i.parentID← j

5 else
6

i.parentID← minimum RPlevel node j.

7 j.chilren.push back(i). End loop.
// 2. Assign values in the precedence matrix P
8 For each j ∈ SP, get ancestors of j by recursively backtracking its parentID until root. Set
pij = 1 when i is an ancestor of j.
Recall the problem formulation 1c in Section 5.3.2. We ﬁrst deﬁne notations, then present our
solution and prove its validity. We deﬁne the pure sensing positions SPpure = SP\DS (‘\’ means
116

substraction), and visiting positions VP = SP ∪ RP.
Alg. 15 shows the procedure of assigning the precedence constraint by ﬁrst assigning a single
parentID for each node in VP. Assigning parentIDs is important because we can always backtrack
a node’s parentID recursively to the BS, forming a valid path for communication. The procedure
builds a precedence tree to ﬁnd parentIDs on VP. The tree has 1) the non-leaf backbone as RP, 2)
leaf nodes as SPpure , 3) BS as the root.
Theorem 6. The precedence constraint matrix P obtained by Alg. 15 is valid.
Proof. Each node in VP has a single parentID. Because SP ⊆ VP, each node in i ∈ SP has a
single parentID. For each i, its ancestors form a valid path back to the root BS, being part of the
backbone. Because P is deﬁned that all ancestors of i are required to be visited before visiting i, P
is valid, and this completes the proof.

5.5

Tour Generation by PC2TSP

Recall the problem formulation 2 in Section 5.3.2. We model the problem as PC2TSP. By a similar
proof of Theorem 5 we can prove PC2TSP is NP-hard. Therefore, we provide a near-optimal
heuristic that 1) clusters the nodes (with possible overlapping of shared relays) into two parts, 2)
solves them individually by PCATSP optimally, and 3) prunes the shared relays and balances the
two tours.
The tour generation procedure can be used as a stand alone solution to PC2TSP with the
changes as follows. 1) Change robots, sensing positions, relay positions, and the BS to travelers, consumer cities, supplier cities, and the base city. 2) Change ones ancestors and parentID to

117

its supplier cities in tour validation and dependency checking. 3) Values in the cost matrix cij and
whether to have the conversion from Hamiltonian path depend on the application.

5.5.1

Cluster Visiting Positions

We ﬁrst cluster each nodes i ∈ SP according to its x coordinate and insert it accordingly to either
Pa or Pb : assign to robot a or b by whether the position is on the left or right of the center line. A
center line X = xR /2 is a vertical line to partition the region in the middle. Then, the supporting
relays, or the ancestors of each i ∈ SP are assigned accordingly to the same cluster as i. Therefore,
position sets Pa and Pb include the sensing positions and their supporting relays. Relays may be
(partially) shared by Pa and Pb . The motivation of such clustering is to make a tour self-reliant
without need of waiting for relays from the other tour.
We have tried more advanced schemes such as K-means and also attempted to balance the two
sets to have similar amount of nodes such that ||Pa | − |Pb || ≤ 1, however they do not improve the
performance. Although the initial Pa and Pb may be unbalanced, our tour pruning and balance in
Section 5.5.3 work effectively in balancing the tours.

5.5.2

Obtain Optimal Single Robot Tour

Given the positions Pa and Pb for robot a and b to traverse, and the precedence constraint in P
relevant to each part, we need to compute the precedence constrained shortest Hamiltonian path
starting at BS for a and b individually. We ﬁrst convert the Hamiltonian path problem to the
traveling salesman problem, then model the problem as (single) PCATSP [115].
Conversion: In our system model, robots will not immediately return to the BS after the search

118

completes. Therefore, the shortest Hamiltonian path problem with a given starting city should be
ﬁrst converted to an asymmetric TSP by setting the distance on the arcs from all vertices to BS as
zero [116]. It forces the evaluation of all possible paths starting with BS and disregards the way
back to the BS in the tour.
Mathematically, precedence constrained asymmetric (single) traveling salesman problem
(PCATSP) is:
n

n

cij xij ,

Minimize

(5.10)

i=1 j=1,j=i
n

xij = 1,

∀j = 1, ..., n,

xij = 1,

Subject to

∀i = 1, ..., n,

i=1,i=j
n
j=1,j=i

pij ≥ xij ,
pij + pji = 1,
pij + pjk + pki ≤ 2,
pij = 1,

∀i, j = 2, ..., n,
∀i, j = 2, ..., n,

i = j,

∀i, j, k = 2, ..., n,
∀j = 2, ..., n,

i = j,

i = j = k,

∀i ∈ SP Cj

Where cij is the traverse time from i to j based on the obstacle aware path length by A* search
and a traverse velocity. cij forms the cost matrix C. xij and pij are binary and xij = 1 indicates
position i precedes j immediately while pij = 1 means position i precedes j not necessarily
immediately in the tour. SP Cj gives the subset of positions in {2, ..., n} that are required to
precede j.
Solving PCATSP by branch and cut method with the above integer linear programming formulation is relatively fast for a reasonable size despite its NP-hardness. Real-world instances with

119

200 nodes PCATSP have been solved optimally in a few minutes [117].

5.5.3

Prune and Balance Tours

Pruning shared relays
Algorithm 16: Path pruning
Input: Ta , Tb .
Output: updated Ta , Tb .
// Obtain shared relays and divide into segments if |SR| > k
1 Obtain shared relays SR from Ta , Tb in order. Divide it into |SR|/k segments, each with
k nodes (except the last).
2 foreach segment i do
3

Get powerset of i: P S(i), |P S(i)| ≤ 2k

4

foreach j ∈ P S(i), j = i\j do

5

Get temp tours by Ta = Ta \j, Tb = Tb \j . Update search time.

6

Call Alg. 17 to check dependency and obtain the true time tab by adding wait time
(if it exists) on Ta , Tb .

7

Save jmin , jmin with minimum tab and then update tours: Ta = Ta \jmin ,
Tb = Tb \jmin .
Tour balance is to minimize the total search time tab , which is dominated by the longer tour.

The two paths by PCATSP are self-reliant but may have visited duplicate relay positions. Our
goal is to reduce tab by reducing duplicate RPs, considering the possibility and cost of introducing

120

dependency with waiting time.
Algorithm 17: Tour validation and dependency checking
Input: Local copies of any tours Ta , Tb .
Output: tab , updated Ta , Tb with waiting time, isValid.
1 isDeadlock=false, isValid=true.
2 if isFlipped(Ta ) || isFlipped(Tb ) then return tab =FLT MAX, isValid=false.
3 Iterators ita , itb at the beginning of Ta , Tb . ta = 0, tb = 0
4 repeat
5
6

repeat
ita keeps on proceeding to the next position ++ita in Ta . At each new position ita ,
ﬁrst to update time by cij : ta + = c{∗(ita − 1), ∗ita }, and then make sure the robot
waits for its parent: ta = max(ta , t(parentID(∗ita ))), update wait time vector
w(Pa ). update the visited time at t(ita ) = ta , mark ita as visited.

7

until ita is blocked when its parent is not visited.

8

Same repeat procedure as above for itb , which keeps on proceeding until it is blocked.

9

if Both ita , itb are blocked then isDeadlock=checkDeadlock(ita , itb ).

10 until ita , itb reach the end of Ta , Tb || isDeadlock
11 if isDeadlock then return tab =FLT MAX, isValid=false.
The pruning strategy has shown in Alg. 16. With |SR| number of shared relays, we try all
possible ways of allocating them to robot a and b by computing the powerset. (A powerset of a
set S is the set of all subsets of S.) Due to the exponential nature, we set the maximum segment
length k = 12 and to divide SR into segments to limit the powerset size. For each segment, we
compute the best allocation of new tour cost by ﬁrst computing the time based on paths from cij .

121

Then the dependency checking is called in line 7 to check whether dependency occurs and to add
waiting time, if it exists. Figure 5.3(a) illustrates the idea. Denote the two shared relays as SR 1
and 2. They are divided by each tour evenly after evaluating P S({1, 2}) = {∅, {1}, {2}, {1, 2}}.
Validate tours and check dependency: With the path positions Pa , Pb , we needs to verify
whether they are feasible by checking whether self-ﬂipped and deadlock cases occur. Then, we
compute the true search time considering dependency.
Deﬁnitions: A tour is self-ﬂipped if and only if it has a position i whose ancestors are visited
after i. A self-ﬂipped tour is invalid because by itself it violates the precedence constraint. A
position i is blocked when it has its parent not visited at time t(i). i has a missingID as its parentID.
Two tours Ta , Tb are in deadlock status when there exist i ∈ Ta , j ∈ Tb whose missingIDs are
after i, j in the other tour: missingID(i) in Tb after j, missingID(j) in Ta after i. A deadlock tour
is invalid because both robots cannot proceed. Figure 5.4 illustrates the two invalid cases. Figure
5.4(a) shows the robot arrives at a SP that requires a not yet deployed relay. Figure 5.4(b) shows
robot a needs the relay to be deployed by b and vice versa.
The basic idea is to traverse Ta , Tb again and one tour is blocked when the needed relay is
not yet visited in the other tour. At each position i, the tour time t is updated not only from the
cost matrix cij , but also considers the waiting time for i’s parent: update t as the maximum of
its parent’s visited time and itself. Note that when a parent is visited, all ancestors must have
been visited, because an unvisited parent will immediately block its children. In addition, when
self-ﬂipped and deadlock cases occur, we mark the tours invalid and set the tour time to be a very
large number, i.e., FLT MAX, making the tour not selected in its parent function. The detailed
procedure is shown in Alg. 17.

122

SP

RP3

RP4

RP1

RP2

BS

Figure 5.2. Multiple choices of precedence constraints.

a
b
Shared
New
(a) Shared relay pruning.

Longer
Shorter
New
(b) Vertex transfer.
Figure 5.3. Shared relay pruning and vertex transfer.

123

Cannot
transmit

Not yet
deployed

Moving
Path
Stream
to BS

BS
BS
(a) Self-ﬂipped.

Not yet
deployed
by b

Cannot
transmit
Robot a
Moving Stuck
Path: a

Stream
to BS

Robot b
Stuck
Not yet
deployed
by a

Cannot
transmit
Stream
to BS

(b) Deadlock.
Figure 5.4. Invalid cases.

124

Moving
Path: b

Balance with vertex transfer
While pruning is only effective on shared relays, vertex transfer attempts on any node and further
balances tours to reduce tab . The basic idea is to try transferring a position on the longer tour and
inserting it into the shorter one. We greedily choose the best pair of removal and insertion position
until no further reduction is found. For each pair of newly modiﬁed tours, Alg. 17 is called to add
waiting time when it is applicable. The detailed procedure is presented in Alg. 18. As illustrated
in Figure 5.3(b), the black visiting position in the middle is transferred to the shorter white one,

125

where black positions are those on the longer tour and the white ones are those on the shorter tour.
Algorithm 18: Balance with vertex transfer
Input: Ta , Tb .
Output: updated Ta , Tb
1 repeat
2

Mark the longer and shorter tours of Ta , Tb as Tl , Ts .

3

foreach i ∈ Tl do

4
5

foreach j ∈ Ts , j = i do
Get new tours Tl ← (Tl with removed i), Ts ← (Ts with inserted i after position
of j).

6

Call Alg. 17 to validate tours and check dependency. Obtain the true time tls by
adding wait time (if it exists) on Tl , Ts .

7

Get min tab min from all tab , record corresponding imin , jmin

8

if tab < tab then executes transfer: Remove imin from Tl and insert imin at position
after jmin in Ts . Update Ta , Tb .

9 until there is no improvement: tab ≥ tab

5.6

Extensions

The previous sections provide the basic procedures to describe how STARS solves the 2RSRD
problem. In this section, we present several extensions to STARS, such as (1) dealing with more
than two-robot scenarios, (2) placing static sensors to enable constant area monitoring, (3) considering a non-uniform search and transmit interval and relay deploying time, (4) leveraging pre-

126

existing relays, (5) leveraging extra carried relays to reduce dependency. These extensions make
STARS adaptive to more general conditions and varying user requirements.

5.6.1

Search with a single or more than two robots

STARS trivially supports a single robot search since tour generation is simpliﬁed as PCATSP. In
STARS, the solution to the ﬁrst subproblem is irrelevant to the number of robots and is always
valid. Therefore, STARS is extensible to search with more than two robots as long as PC2TSP is
extensible to deal with more than two travelers.
Theorem 7. Our solution to PC2TSP is extensible to deal with more than two travelers.
Proof. We ﬁrst illustrate the changes with n=3 robots of R0 , R1 , R2 and then extend it with n > 3.
The sensing positions are clustered by 3 − 1 = 2 vertical lines X = Rx /3, X = 2 · Rx /3
to evenly partition the region. Pruning is ﬁrst conducted the same as before to relays only shared
by two robots SR01 , SR02 , SR12 . The shared relays of all 3 robots SR012 , if they exist, are
then partitioned and evaluated by a recursive powerset computation. In tour validation, deadlock
checking needs to consider the additional cases with 3-robot interdependency. Finally, vertex
transfer between each robot pair (0,1),(0,2),(1,2) is executed until the search time cannot be reduced
any further.
Cases with n > 3 are similarly extended. SP are clustered by n − 1 lines. The shared relays
are evaluated with

n
n
λ
i=2 i · 2 different cases, where λ is the number of shared relays between

that set of robots. Up to n interdependencies are checked for deadlocks. Besides, vertex transfer
between n pairs of robots is evaluated.
2
When n > 5, the procedure of shared relay pruning may be simpliﬁed due to high computation
127

cost. However, with the goal of replacing robots by relays and the strategy of partitioning areas,
we believe n ≤ 5 is sufﬁcient in most cases.

5.6.2

Enable constant monitoring with static sensor deployment

Search paths and relay deployment positions are computed ofﬂine before search starts. During the
search process, additional sensors may be deployed at SPsusp ⊆ SP to cover suspicious areas
when they are identiﬁed during the search and transmission interval (STI), when human and/or
computational analysis is conduct on the video streams at the base station. With the communication
backbone to cover SP, the sensor deployed at any sensing position has a valid path back to the BS.
Such sensor deployment signiﬁcantly reduces the number of sensors compared to a full sensing
coverage deployment. In addition, it adds on a constant monitoring on suspicious areas, compared
to the single-time area scan and pass by the homogeneous mobile robots.

5.6.3

Consider a non-uniform search and transmit interval and relay deploying time

We may deﬁne a non-uniform STI time tST I (i) for each i ∈ SP and a relay deploying time trd (j)
for each j ∈ RP. The time only affects the cost matrix cij ∈ C in Eq. 5.10 for each edge
ij. Besides the current value based on obstacle aware traverse path from i to j, any edge with a
destination vertex of j ∈ RP will add the value of trd (j), cij + = trd (j), to consider the extra
time of relay deployment. To take into account of the time for search and transmission interval,
any edge with a starting vertex of i ∈ SP will add the value of tST I (i), cij + = tST I (i).

128

5.6.4

Leverage pre-existing relays

The applications of the multi-robot search and monitoring include rescue and reconnaissance missions in radioactive, earthquake, and battleﬁeld environments. Therefore, pre-deployed relays and
infrastructure networks are often not available. However, STARS can take advantage of the preexisting relays gracefully with a simple modiﬁcation. The basic idea is to use them to cover the
nearby sensing positions. Recall the Algorithm 14 in Section 5.4.2. Given the set of pre-existing
relays Rexist , we may ﬁrst use them to dominate (cover) their neighboring sensing positions. Then
we call the DS ﬁnder to dominate the rest of the uncovered sensing positions. A union of Rexist
and the DS by the DS ﬁnder is the ﬁnal dominating set for all sensing positions. The rest of
procedure remains the same.

5.6.5

Leverage extra carried relays to reduce dependency

Recall the Problem 1b in Section 5.3.2, we assume our attempt to minimize relay number by SCDS will satisfy the robot carrying capacity constraint. It is also possible that each robot’s relay
carrying capacity nr is larger than the computed relay number. Under such a condition, we may
take advantage of the remaining carried relays to reduce the search time when dependency and
waiting time between robots exist. The basic idea is as follows. On robot a’s travel path, check the
sensing positions relying on the relays deployed by robot b (or vice versa). When the dependency
occurs and the waiting time is not zero, we attempt to deploy additional relays on robot a’s own
path to “skip” such relays and remove the dependency. This approach is mostly effective when
the relay deploying time (added new cost) is notably smaller than the saved waiting time. Alg. 19

129

describes the algorithm in detail.
Algorithm 19: Leverage extra relays to reduce dependency and waiting time.
Input: Robots migration paths and ki number of extra relays for each robot i.
Output: Enhanced traveled paths.
1 Compute the traveling paths and search time for both robots using the current algorithms.
2 Obtain all the sensing positions SPwait relying on the relays deployed by the other robot
Rother with a non-zero waiting time.
3 foreach sp ∈ SPwait and its corresponding ro ∈ Rother do
// Check whether the k extra relays are sufﬁcient to build a path back to the BS.
Call breadth-ﬁrst search from sp to ﬁnd the minimum number of hops on robot’s sensing

4

positions to skip ro to reach the BS.
Evaluate the time-saving effectiveness by the average saved waiting time per extra relay.

5

6 Greedily adding the extra relays in the order of maximum time-saving effectiveness until
extra relays run out or no extra relays can reduce the search time.

5.7

Performance Evaluation

We use a C++ simulation program to evaluate STARS search efﬁciency. PCATSP is computed in
part by IBM ILOG CPLEX Optimizer V12.2. The region is represented by the grid-map model
with X × Y cells. Cell edge length is 1 meter, and the BS is located at the bottom center of the
region. The robots travel at a constant speed of 1m/sec. rs =10m and rc =20m. Obstacle cells are
generated randomly each time with an obstacle ratio ro as the parameter. All tests are run 200
times to obtain the average. The error bars in the ﬁgures show the 95% conﬁdence interval.

130

Search time(sec)

120
110
100
90
80
70
60
50
40
30
20
10
0

Pre−prune
Final
Optimal

25*30 25*40 25*50 25*60 25*70
Region size(square meter)

Search time(sec)

(a) Extra-narrow region.

150
140
130
120
110
100
90
80
70
60
50
40
30
20
10
0

Pre−prune
Final
Optimal

35*30 35*40 35*50 35*60 35*70
Region size(square meter)
(b) Narrow region.

Figure 5.5. Compare the search time with optimal under varying width regions (widths: 25-35m).

131

Search time(sec)

160
150
140
130
120
110
100
90
80
70
60
50
40
30
20
10
0

Pre−prune
Final
Optimal

45*25 45*30 45*35 45*40 45*45
Region size(square meter)

Search time(sec)

(a) Wide region.

110
100
90
80
70
60
50
40
30
20
10
0

Pre−prune
Final
Optimal
5%

10% 15% 20%
Obstacle ratio(%)

25%

(b) Varied obstacle density.
Figure 5.6. (a) Compare the search time with optimal under varying width regions (widths: 45m).
(b) Varied obstacle density from 0% to 25% for 35*50 case.

132

Search time(sec)

500
475
450
425
400
375
350
325
300
275
250
225
200
175
150
125
100
75
50
25
0

Pre−prune
Final

30*45 40*60 50*75 60*90 70*105
Region size(square meter)

Num. of relays

(a) Search time in larger regions.

50
45
40
35
30
25
20
15
10
5
0

Num. of visiting positions
Num. of relays

30*45 40*60 50*75 60*90 70*105
Region size(square meter)
(b) Number of visiting positions and relays.

Figure 5.7. (a) Search time in larger regions. (b) Number of visiting positions and relays.

133

Search time(sec)

300
275
250
225
200
175
150
125
100
75
50
25
0

Pre−prune
Final

20
25
30
35
Comm. Range(m) (50*75)

Search time(sec)

(a) Varying communication ranges. rs =10m.

300
275
250
225
200
175
150
125
100
75
50
25
0

Pre−prune
Final

8

10
12
14
Sens. Range(m) (50*75)

(b) Varying sensing ranges. rc =20m.
Figure 5.8. Compare the search time with varying communication ranges and sensing ranges
(50m*75m region).

134

150

Search time(sec)

125
100
75
50

Pre−prune
Final
Optimal

25
0

2

4
6
STI(sec) (35*50)

8

(a) Varying STI time. trd =2sec.

150

Search time(sec)

125
100
75
50

Pre−prune
Final
Optimal

25
0

2
4
6
8
Relay dep. time(sec) (35*50)
(b) Varying relay deploying time. tST I =2sec.

Figure 5.9. Compare the search time with optimal under varying STI and relay deploying time.

135

First, we compare the search time with the optimal result in different shapes of regions with
widths of 25m, 35m, and 45m respectively as shown in Figures 5.5(a), 5.5(b), 5.6(a) (ro =0.15).
The optimal result generator tries all possible tours with the same visiting positions and precedence
constraint as STARS. Due to the high computation cost of the optimal result, we limit the region
size where up to 18 visiting positions need to be traversed. The average difference of our heuristic
from optimal is 1.94%, 1.98%, and 1.91% for the above 3 cases. Also, tour pruning and balance
effectively reduce search time by 25% on average.
Figure 5.6(b) shows the 30*50 grid cell case with varying densities of obstacles (ro ={0.05, 0.1,
0.15, 0.2, 0.25}). As ro increases from 5% to 25%, the optimal tour time increases from 88.6 to
90.8 seconds (2.4%). The difference of our heuristic from optimal increases slightly from 0.8%
to 3.7%. We believe the near optimal results are in no small part contributed by (1) the optimal
single robot tour by linear programming, (2) the effective post-pruning: reducing shared relays and
vertex transfer.
We focus on narrow regions because a clear separation of two robots is then challenging. Also,
the dependency between robots is likely to occur; the two robots tours are likely to be mixed
together rather than clearly separated. (Recall that the robots start searching from BS at the bottom
center of the region.) In wider regions, it is possible to assign each robot a sub-area to search,
converting the problem into a simpler single robot search problem.
Second, we show the search time trend with larger regions of 30*45, 40*60, 50*75, 60*90,
70*105 grid cells in Figure 5.7(a) where optimal results are too slow to be obtained. Results show
the two robot tours are well-balanced. The differences between tours are only 6.8% 7.4% 4.1%
3.1% 2.2% respectively, as compared to the longer tour. Well-balanced tours do not guarantee near
optimal performance but most optimal tours we observed are well-balanced. Figure 5.7(b) shows
136

the number of visiting positions and relays in the above cases. The ratio of relays to visiting positions is 28.1%, 36.5%, 36.4%, 36.0%, and 35.1% respectively, which shows that approximately
one third of the positions need to be deployed relays.
Third, we investigate on the impact of varying communication ranges and sensing ranges on
the search time. Figure 5.8(a) demonstrates the search time modestly reduces 8.15% from 199.9
to 183.6 seconds with an increased communication range from 20m to 35m, in 50m*75m regions.
The sensing range is set at 10m and the obstacle ratio is 15%. At the same time, the number
of relays notably decreases 65.4% from 8.82 to 3.05. These results ﬁrst show that an increased
communication range has a direct impact on the number of relays. However, a reduced number
of relays does not necessarily reduce the ﬁnal search time. The reason is that the removed relays
may be exactly on the robot traveling paths. Therefore, whether or not to have these relays does
not affect the search time (assuming a zero relay deploying time).
Figure 5.8(b) shows the search time notably reduces 41.0% from 226.5 to 133.6 seconds with
an increased sensing range from 8m to 14m, in 50m*75m regions. The communication range is set
at 20m and the obstacle ratio is 15%. While an increased communication range may only remove
the relays that are already on the traveling paths, reduced sensing ranges will affect all sensing
positions and therefore more notably change the ﬁnal tours. We did not compare the varied sensing
and communication range results with optimal because the node number exceeds 18 under many
cases, and the exponential computation for optimal is then formidable.
In the above evaluation, we assume a zero second search and transmit interval(STI) at the
sensing positions and a zero second relay deploying time at relay positions. Now, we evaluate the
impact of varying STI and relay deploying time on search time. Figure 5.9(a) shows the search
time increases 21.1% from 100.9 to 127.9 seconds when STI increases from 2 to 8 seconds in the
137

35m*50m regions. A constant relay deploying time is set at 2 seconds. The search time difference
of STARS from optimal ranges from 1.25% to 2.23% in Figure 5.9(a).
In addition, Figure 5.9(b) shows the search time increases 6.83% from 100.9 to 108.3 seconds
when relay deploying time increases from 2 to 8 seconds with a constant STI of 2 seconds. The
search time difference of STARS from optimal ranges from 2.23% to 4.42% in Figure 5.9(b). We
found search time increases more notably with increased STI compared to relay deploying time
since there are more sensing positions than relay positions. We also found the our ﬁnal search time
is less inﬂuenced by the increased STI or relay deploying time, compared to the pre-pruned values.

5.8

Summary

In this chapter, we ﬁrst present a problem called precedence constrained two traveling salesman
(PC2TSP). A near-optimal heuristic to PC2TSP is presented with 1.94% average difference from
optimal, which is in part contributed by optimal single tour computation, dependency handling, and
effective pruning and balance. Leveraging PC2TSP, we propose a real-time search and monitoring
scheme called STARS, which builds on a heterogeneous and cost-effective platform of mobile
robots, static relays and sensors. Mobility of robots enables relay deployment on the ﬂy to form
a communication backbone at carefully selected locations. The backbone facilitates the robots to
transmit streams to the base station for remote sensing and control. STARS signiﬁcantly reduces
cost by replacing mobile robots by static relays and enables constant area monitoring by sensor
deployment only at speciﬁc suspicious areas rather than a full coverage. In the next chapter, we will
introduce an exploration strategy with online relay deployment when the environment is unknown.

138

CHAPTER 6
Steiner Traveler: Relay Deployment for
Remote Sensing in Heterogeneous
Multi-Robot Exploration

6.1

Preliminaries and Motivations

The previous chapter presents STARS, or the STAtic Relay aided Search to support remote sensing in a known environment when all robots may deploy relays. In this chapter, we will present
a new heterogeneous exploration model based on the online relay deployment for an unknown
environment with a single or a partial team of robots that may deploy relays. We call the approach Bandwidth-aware Exploration with a Steiner Traveler (BEST). BEST has a heterogeneous
robot team with a ﬁxed number of frontier nodes (FN) to sense the area iteratively. In addition, a
relay-deployment node (RDN) “chases” the (FN) movement and places relays when necessary to
support the video/audio streams aggregation to the base station. This exploration model is illus139

trated in Fig. 6.1. We show BEST is extensible with multiple RDNs in Section 6.6.

140

Front.Node
(FN)

Unexplored
Area

Relay Depl.
Node
(RDN)

FN
FN
RDN

Relay
(R)
RDN Travel Path
(1: 1st iteration)
Stream Trans.
Path
Base
Station

R

2
R

2
1

R

FN

Explored
Area

Obstacle
R

1

Figure 6.1. A relay deploying robot supports the stream aggregation for remote control of frontier nodes in exploration.
141

This approach is motivated by the following four reasons. First, as mentioned in Chapter 1,
prior relay deployment is often infeasible when the environment is unknown and relays have to
be placed at the same time as the exploration. Second, the FN become “worry-free” of the relay
deployment with the clear separation of relay and search robot. Therefore, it is ﬂexible for the FN
to concentrate on exploration and use any existing exploration scheme.
Third, we may markedly save cost and improve efﬁciency compared to the homogeneous robot
approach where all the robots have to be equipped with relay deployment devices or move backwards from frontier areas to merely serve as relays for the streams. Fourth, BEST does not have
the drawback of hard limit on exploration range comparing to a homogeneous robot team. When a
homogeneous robot team tries to explore farther away and maintain connectivity to the BS, more
robots have to retreat from frontier areas to serve as relays. With a ﬁxed number of robots, increasing number of relay robots will ﬁnally prevent the frontier robots from moving forward. In BEST,
on the other hand, a constant number of FN are not restrained from the increased distance from the
BS.
The key problem is to compute the minimum path for the RDN to travel and ﬁnd a minimum
number of positions to deploy necessary relays to support the stream aggregation in each movement
iteration. This problem inherits characteristics of both the traveling salesman and Steiner Minimum
Tree with Minimum Steiner Points (SMT-MSP) [43] problems. We model the novel problem as
the minimum velocity Flow constrained Steiner Traveler problem (FST),
FST is described as follows: Given (1) a ﬁxed number of FN to explore an unknown environment in a synchronized iterative (round by round) fashion with a traveling time and a constant
velocity, (2) a relay deploying node (RDN) with a relay deploying time td , (3) a transmission
constraint that when all FN arrive at their destinations in each round, a transmission path formed
142

by relays from each FN to the BS always exists, (This also implies a precedence constraint that
needed relays must be deployed by RDN before FN arrive), (4) a ﬂow constraint that the number of
ﬂows for each relay never exceeds an upper limit K, to ﬁnd the traveling path for the RDN and the
positions to deploy the relays such that the average traveling velocity for the RDN is minimized.
We minimize the velocity in order to reduce the energy cost. Because velocity is related to
both traveling path length and the traveling time, we need to (1) reduce the number of relays for
deployment time to increase the RDN travel time; (2) reduce the traveling path length. Therefore,
a joint consideration on the number of Steiner points and the traveling paths is needed in this
problem.

6.1.1

Key Contributions

• To the best of our knowledge, BEST is the ﬁrst of its kind to (1) jointly consider traveling salesman with ﬂow-constrained Steiner Tree to achieve bandwidth sufﬁciency and (2)
present a heterogenous exploration scheme with relay deployment for unknown environment
achieving signiﬁcant efﬁciency improvement.
• To solve R2 BS, we formulate the problem as the minimum velocity Flow constrained Steiner
Traveler problem (FST). We present an efﬁcient heuristic that takes advantage of existing
relays that have unsaturated paths to the BS to reduce number of relays.
• Designing exploration schemes for an unknown environment, we also wonder what will be
the impact of a known global map on performance? Considering the two metrics (1) RDN
traveling path length and (2) the number of deployed relays, we ﬁnd the traveling path length
notably beneﬁts from a global map while the number of deployed relays only has marginal

143

improvement.
The rest of the chapter proceeds as follows. Section 6.2 introduces the system model. In Section
6.3, we formulate the problem and discuss the challenges. Section 6.4 presents the BEST scheme.
Performance evaluation is in Section 6.5. Section 6.6 discusses the future work and Section 6.7
concludes the chapter.

6.2

System Model

Robot Model: A robot team includes |FN| number of FN and a single RDN. In future work, we will
consider the extension of multiple RDNs, which is discussed in Section 6.6.1. FN have traveling,
communication, and sensing capability while the RDN can travel, communicate and deploy static
relays with a maximum carrying capacity and a deploying time td . We assume BEST satisﬁes
this carrying capacity constraint since it attempts to use a minimum number of relays. Both FN
and RDN have a communication range rc and a sensing range rs where rc ≥ rs . FN move at a
t
constant velocity vf n in all iterations and RDN moves at a changing velocity vrdn in each iteration

t. The acceleration and deceleration time is not considered.
Environment Model: A 2D occupancy map is adopted to model the environment as an unknown
rectangle region R = X ×Y with grid cells similar to that in [52]. The cell size equals to the largest
robot size. A cell status include unexplored, exploring, and explored. An explored cell is marked
as either free or obstructed. An obstacle cell blocks the traveling path. Such cells cannot be visited
by the robots or placed relays. We assume the obstacle distribution in the environment is unknown.
A base station is the control center where the human operator remotely monitor and potentially
operate the robots when necessary.
144

Iterative Exploration Model: A ﬁxed number of FN explores an unknown environment in a
t
synchronized and iterative (round by round) fashion with a traveling time Tf n in iteration t. After

all FN arrive at their target positions, FN and also RDN will receive FN’s next iteration target
positions and then enter a ﬁxed length sensing and transmitting interval (STI) Tsti to sense the area
and mark cells as searched. RDN must ﬁnish deploying all necessary relay in round t (denoted as
Rt ) before STI starts because the relays are essential to support the transmission. Since the RDN
t
receives FN’ target positions before last round STI, the total time for RDN to travel Trdn in round

t is:
t
t
Trdn = Tf n + Tsti − |Rt | · Td

(6.1)

t
t
We assume Tf n + Tsti − |Rt | · Td > 0. We may ﬁnd that Trdn is increased with the decreased

number of deployed relays. It is especially signiﬁcant when the deploying time Td is lengthy. All
FN and RDN start traveling from the BS. After the RDN completes the relay deployment in each
t
iteration t, it will stop as the last relay deployment position Rstop ,

Note that BEST is compatible with any iterative FN movement strategies for area exploration
or other purposes. FN movements can be controlled by a computer program or a human operator
at the BS. Under either case, FN can only move to sensed (known) areas because of the unknown
obstacles in unknown areas. In BEST, we apply the frontier cell based strategy to maximize sensing
gain as in [52].
Wireless Model: The unit-disk model where two nodes i, j can communicate as long as
dist(i, j) ≤ rc . dist(i, j) gives the distance from i to j. We will consider a probability based
communication range in future work. Similar to [52], each FN has a uniform ﬂow sending rate,
ratesend and a link capacity, ratecapacity . A bandwidth factor K deﬁnes how many ﬂows can a

145

relay maximally carries before exceeding its capacity:
K=

ratecapacity
ratesend

(6.2)

In addition, path(V ) gives the transmission (routing) path by a vector of nodes V , where all adjacent pair of nodes have a distance less than rc . We assume the powerful BS have multiple radios
to have sufﬁcient bandwidth for ﬂow aggregation. A similar 15-radio testbed is shown in [103].
The interference between nodes can be resolved by a multi-channel dual radio strategy with proper
channel assignment.

6.3

Problem formulation

With the system model the formal formulation of the minimum velocity Flow constrained Steiner
Traveler problem (FST) is as follows: Given
• a vector of FNt positions, a FN travel time TF N , a (partially) explored region RGt with an
obstacle-cell subset in each iteration t = {1, ..., nit } with a total number of iterations nit .
• a constant FN velocity vf n , FN STI time Tsti and a RDN relay deploying time td ,
• a transmission constraint that when all FN arrive at their destinations in each round, a transmission path formed by relays from each FN to the BS always exists, (This also implies a
precedence constraint such that needed relays must be deployed by RDN before FN arrive),
• a ﬂow constraint that the number of ﬂows for each relay never exceeds a bandwidth factor
K,
• placement constraint: no relay is placed on obstacles;
146

To ﬁnd (in each iteration t)
• new relay positions Rt (or its subset) in each iteration t, along with (a subset of) existing
relays R1..n−1 , to form a directed Steiner tree to connect FN to the BS.
t−1
• a RDN Hamiltonian path patht
rdn starting from last round stop position(Rstop ) to travel

each position in Rt exactly once,
such that the average RDN travel velocity vrdn is minimized. vrdn depends on both the travel path
length and travel time:
vrdn =

nit
t
t=1 pathrdn
nit t
t=1 Trdn

(6.3)

Mathematically, FST is
Minimize vrdn ,
S.T. ∃ path(V ), V = (i, v1 , ..., vn , BS), ∀i ∈ FN, vi ∈ R1..t ,
dist(vj , vj+1 ) ≤ rc , ∀vj ∈ V, j ≤ n,

(6.4)
(6.5)
(6.6)

|f | ≤ K, ∀j ∈ R1..t ,

(6.7)

position(i) = obstacle, ∀i ∈ R1..t ,

(6.8)

i∈FN∪R1..t

ij

∀t = 1, ..., nit

(6.9)

Where (5) and (6) shows there is a valid routing path formed by existing and newly deployed
relays from each FN to the BS via deployed relays under the communication range. (7) gives the
bandwidth constraint. (8) gives that the relays cannot be placed at the obstacle cells.
In each iteration t, the computation of the Hamiltonian path for RDN patht is formulated
rdn
by the asymmetric traveling salesman problem (TSP). A simple conversion to TSP is achieved by
147

t−1
setting the distances on the arcs from all nodes to position Rstop as zero [116]. Then, we apply

the integer linear programming (ILP) formulation for asymmetric TSP in [115] as below:
n

n

cij xij ,

Minimize

(6.10)

i=1 j=1,j=i
n

xij = 1,

∀j = 1, ..., n,

xij = 1,

Subject to

∀i = 1, ..., n,

i=1,i=j
n
j=1,j=i

yij ≥ xij ,
yij + yji = 1,
yij + yjk + yki ≤ 2,
yij = 0,

∀i, j = 2, ..., n,
∀i, j = 2, ..., n,
∀i, j, k = 2, ..., n,

i = j,
i = j,
i = j = k,

∀i, j = 2, ..., n

Where cij is the obstacle-aware path length computed by A* search from position i to j. xij and
yij are binary and xij = 1 shows position i is before j immediately in the tour. It is reasonably
fast to solve TSP by a branch and cut method with the ILP formulation. Instances with 200 nodes
is computed optimally in a couple of minutes [117].
Note that we describe FST using the robotic notations to illustrate our application. A theoretical and general description of FST is made possible with following term changes: (1) FN and
BS become the terminal points where FN are the sending terminals and BS is the base terminal. (2) Existing and current iteration relays become existing and new Steiner points respectively.
t−1
t−1
(3)Rstop ∪ Rt becomes the set of cities where Rstop is the starting city for the traveling salesman.

148

6.3.1

Challenges

There are two major challenges to solve FST. First, FST combines two NP-hard problems: Steiner
minimum tree and traveling salesman. The traveling path generation depends on the locations and
the number of relays deployed. There is also a trade-off of the number of relays and the traveling
path length. To minimize the RDN velocity, both the number of relays and the traveling path
need to be reduced. However, it is possible that a relay placement with a least relay number but
improper positions will lead to a longer travel path. Besides, the importance of the two factors
may vary with different parameter settings. The importance of a shorter path outweighs that of the
t
number of relays with a sufﬁcient lengthy FN traveling time Tf n and a small deploying time Td

(recall Eq. 6.1 and Eq. 6.3). On the other hand, the relay size reduction is more important than
t
generating a shorter path when Tf n is small and Td is large.

Second, the possible usage of existing Steiner points increases the complexity of the problem.
Many related work models the minimum relay placement by SMT-MSP [43, 52, 91], Compared to
SMT-MSP, a major difference is that when we place relays (new Steiner points) in each iteration t,
existing relays may be used. It brings a new problem of whether and how to use them. Note that the
existing Steiner points are not modeled as the terminal points because not necessarily all previous
relays will be on the transmission paths, especially when the FN positions vary considerably in
each iteration.

149

Terms

Deﬁnitions

FN, RDN, R,
FN, R, BS

Frontier nodes, relay-deploying node, deployed relays, and base station. FN, R represent FN and relay set. |FN| gives the number of
FN.
Existing relays deployed before iteration t, relays deployed in iteration t, and their union.
A ﬂow from i to j with the sending rate ratesend .

R1..t−1 ,
R1..t
f

Rt ,

ij

rc ,rs
t
t
Trdn , Tf n

Communication range and sensing range.
The RDN and FN travel time in iteration t.

Td , Tsti

f , |f |

A constant relay deploying time for RDN; A sensing and transmitting interval for FN.
Traveling path by RDN in iteration t.
A uniform FN travel velocity, a RDN travel velocity in iteration t,
and RDN’s average velocity.
Total number of iterations in the iterative movement model.
Bandwidth ratio: maximum number of allowed carried ﬂows per relay.
The ﬂows on edge from i to j, the number of ﬂows.

dist(i, j)
path{V }
BRN

The distance from i to j.
A transmission path by a vector of nodes V .
The border RN set.

patht
rdn
t
vf n ,
vrdn ,
vrdn ,
nit
K in Eq. 6.2
ij

ij

Table 6.1. Notations in BEST.

150

6.4

BEST: Bandwidth-aware Exploration with a Steiner Traveler

We ﬁrst present BEST’s simpler version when the bandwidth ratio K is sufﬁcient large, then we
show how we deal with the extra constraint of bandwidth. Before presenting the solution, we ﬁrst
give the deﬁnitions.
Deﬁnition 5.1: A ﬂow aggregation point is the point to which sending terminals send ﬂows.
1..t−1 for a FN i ∈ FN is an existing relay with the shortest
Deﬁnition 5.2: A border relay BRi

distance to i compared to other existing relays. A BR is qualiﬁed to be an aggregation point if
there is an unsaturated path from the BR to the BS.

6.4.1

BEST with Sufﬁcient Bandwidth

As discussed in Sec. 6.3.1, the major difference of FST from SMT-MSP is the availability of
existing Steiner points. Note that effectively using R1..t−1 in the Steiner tree does not add to the
“cost”, we design our strategy as follows.
Basic Idea: We cluster FN to nearby qualiﬁed border relay. For each FN cluster, we compare
the relay number needed to reach its two potential aggregation points, the border relay and the
BS. The border relay is only used when expected to reduce relays. We compute the traveling path
afterwards. The detailed algorithm is given in Alg. 20.
We attempt to minimize the deployed relay number and only deploy relay when immediately
needed. As a result, there is always a valid path from an existing relay to the BS since it was
previously used to send streams. Therefore, all ﬂows sent to the border relays will reach the BS. To

151

consider the impact of relay placement on traveling path, we place relays as far as possible from
the existing ones with the room for adjustment: when distance divided by rc yields a fractional
number.
With Rt and patht for each iteration t, the RDN average velocity is then computed.
rdn
Algorithm 20: Bandwidth Sufﬁcient Steiner Traveler.
t−1
Input: FN, R1..t−1 , Rstop in each iteration t

Output: New relays Rt and RDN traveling path patht
rdn
1 For each i ∈ FN ∧ dist(i, BS) > rc , add its closest existing RN j to the border RN set
BRN. Add i to j’s FN cluster FNj .
2 foreach relay j ∈ BRN and its FN cluster FNj do
3

Call MST-MSP relay placement in [52] to compute relay positions for connecting (1)
FNj to j; (2) FNj to BS. Denote their resulting candidate relays as (1) Rbrn−temp and
(2) Rbs−temp .

4
5
6
7

if |Rbrn−temp | ≤ |Rbs−temp | then
Add Rbrn−temp to new relays Rt .
else
Add FN cluster FNj to FN set FNdirect .
// For FNs not beneﬁt from connecting to existing relays.

8 Call MST-MSP relay placement in [52] to compute relay positions for FN set FNdirect with
BS as the aggregation point. Add resulting relays to Rt .
t−1
9 Compute Hamiltonian path patht by the ILP formulation in Eq. 6.10 for Rstop ∪ Rt .
rdn
t
Mark the stoping position Rstop for next iteration use.

152

6.4.2

BEST with Constrained Bandwidth

Previous work [52] handles bandwidth constrained relay placement without existing RNs. It guarantees bandwidth adequacy when directly aggregating ﬂows to the BS or the part from FN to the
border relays. The only unchecked part for bandwidth sufﬁciency is from the border relays to the
BS. Hence, before selecting border relays, we need to check whether there are unsaturated paths
back to the BS. The problem resembles the maximum ﬂow problem with vertex capacities. The
difference are: (1) We not necessarily need to obtain the “maximum” ﬂow but simply need to
check the existence of an unsaturated path (which is also called an argument path in maximum
ﬂow). (2) Because the relays are placed by our algorithm, we are able to keep track of a path from
each relay to the BS. This is different from the EdmondsCKarp algorithm for maximum-ﬂow to
use Breadth-ﬁrst search (BFS) to ﬁnd the argument path each time.
The major modiﬁcations on Alg. 20 to support the constrained bandwidth are as follows.
1. Add structures to save path and ﬂow infomation. We maintain a vector of pathToBS for each
relay to save the ordered node list on the path from the relay to the BS. It is updated each time we
add new relays to maintain history information.
We ﬁrst enhance the ﬂow constrained relay placement to save the path from each FN to the
aggregation point. When aggregating to border relays, pathToBS from BR is appended to the new
relays. For example, in Fig. 6.2, the BR’s pathToBS is appened to that on R4 and R3.
Besides, another vector of carriedFNﬂow is deﬁned for existing relays. It shows those FN
whose ﬂow passes this relay in the current iteration. carriedFNﬂow is reset and cleared at the end
of each iteration.
2. Check unsaturated path. Before selecting an existing relay to be a border relay, we check its

153

FN1Æ R4ÆR3
FN
t
R
1..t-1
R

R1
BS

R1

FN1
R4
R4ÆR3ÆR2ÆR1
R3 R3
ÆR2ÆR1
Border
Relay
R2ÆR1
R2

Figure 6.2. Merge border relay’s pathToBS to new relays.
qualiﬁcation by checking whether the path back to the BS is still unsaturated: For each node i ∈
in its pathToBS, carriedFNﬂow(i).size() is less than K. Unqualiﬁed border relays cannot be used
as aggregation points. When we run out of qualiﬁed border relays, all remaining FN will connect
to the BS without using existing relays.
3. Update carried ﬂows. After we verify using BR as the aggregation point reduces the relay
number, the carriedFNﬂow on the pathToBS is updated: For each node i ∈ pathToBS(BR), the
cluster of FNs for this BR is pushed back to carriedFNﬂow(i).

6.5

Performance Evaluation

Summary
• We evaluate the exploration efﬁciency with varying region sizes, number of robots and ob-

154

stacle ratios.
• We also evaluate the performance difference of BEST (given an unknown environment) compared to the solution where a global obstacle distribution is known and thus relay positions
and traveling paths can be globally optimized.
• In addition, the impact of bandwidth constraints on number of deployed relays are investigated with respect to different K values.

6.5.1

Simulation Setup and Parameters

We develop a simulation program in C++ for robot exploration. The traveling salesman problem
is solved in part by IBM ILOG CPLEX V12.2. The unknown exploration region is represented
by the grid-map model with X × Y cells. Each cell has an edge length of 1 meter, and the BS
is located at the left-bottom center of the region. Obstacles are randomly generated with the ratio
(percentage of obstructed cells out of total cells) given by the input. A default bandwidth factor K
is set at 3 and obstacle ratio is set at 10%, unless speciﬁed otherwise. The communication range
rc is 12m and the sensing range rs is 6m. The relay deploying time td is set as 1 second and FN’s
Tsti is set as 3 seconds. FN has a constant travel velocity of 0.5m/sec. All results are the average
obtained by running tests 30 times with different environments of randomly generated obstacles.
The 95% conﬁdence interval is shown by the error bars.

6.5.2

Exploration Efﬁciency

Among the current exploration strategies with connectivity and bandwidth awareness for an unknown environment, the connectivity and bandwidth aware exploration (CBAX) [52, 55] uses less
155

Exploration time(sec)

2500
2250
2000
1750
1500
1250
1000
750
500
250
0

BEST
CBAX

60*60 70*70 80*80 90*90100*100
Region size(square meter) (12 Robots)

Exploration time(sec)

(a) Exploration time in varying region sizes.

1200
1100
1000
900
800
700
600
500
400
300
200
100
0

BEST
CBAX

5/10
6/12
7/14
8/16
Total number of robots (70*70 Region)

(b) Exploration time in varied number of robots. (BEST uses half the
number of robots of CBAX.)
Figure 6.3. Exploration time compared to CBAX with varying (a) region sizes (b) number of
robots.
156

Exploration time(sec)

1200
1100
1000
900
800
700
600
500
400
300
200
100
0

BEST
CBAX

5%
10%
15%
20%
Obstacle ratios (12Rbts/70*70Region)

(a) Exploration time with varying obstacle ratios.

Number of relays deployed

80
70
60

BEST (Sufficient Band.)
BEST (K=3)
BEST (K=2)

50
40
30
20
10
0

40*40 50*50 60*60 70*70 80*80
Region size(square meter) (12 Robots)

(b) Number of deployed relays with varying bandwidth constraints.
Figure 6.4. (a) Exploration time compared to CBAX with varying obstacle ratios. (b) Impact of
varying bandwidth constraints on the number of deployed relays.

157

Number of relays deployed

24
22
20
18
16
14
12
10
8
6
4
2
0

BEST
Known Env.

40*40 45*45 50*50 55*55 60*60
Region size(square meter)

Travel path length (m)

(a) Number of deployed relays in BEST compared to a S-CDS based
solution in known environment.

300
275
250
225
200
175
150
125
100
75
50
25
0

BEST
Known Env.

40*40 45*45 50*50 55*55 60*60
Region size(square meter)

(b) Traveled path length by RDN in BEST compared to solution in known
environment.
Figure 6.5. (a)-(b): Number of deployed relays and traveled path length by RDN in BEST, compared to those results computed with aid of a known environment.
158

exploration time compared to strategies in [32, 36], therefore we choose CBAX as the comparison
counterpart on exploration efﬁciency rather than those in [32, 36]. CBAX explores the unknown
environment iteratively and dynamic selects and places a minimum subset of robots to be the relays in each iteration while the remaining robots to be frontier nodes, given a ﬁxed total number of
robots.
The exploration time is computed from the start to the time when 95% of the non-obstructed
region has been searched. Fig. 6.3(a) shows the exploration time with varying region sizes from
60m*60m to 100m*100m. BEST reduces the exploration time by 62.0% on average compared to
CBAX given a ﬁxed number of twelve total robots. The exploration time reduction is slightly more
signiﬁcant with larger regions. The reduction increases from 44.1% in 40m*40m regions to 69.0%
in 100m*100m regions. The major reason is that more robots move backwards to the BS to serve
as relays in CBAX, while BEST uses constant number of robots to explore the area.
The average RDN travel velocity in the ﬁve regions is 1.07m/sec, 1.14m/sec, 1.13m/sec,
1.01m/sec, 0.95m/sec respectively, approximately 2 times the FN travel velocity. Applying multiple RDN will help to relieve the workload of a single RDN and therefore decrease the travel
velocity.
Besides, Fig. 6.3(b) demonstrates BEST with half the number of robots (e.g., a four-robot team
including 1RDN+3FNs in BEST compared to eight node team in CBAX) stills outperforms CBAX
in exploration efﬁciency. In a 70m*70m region, a half number team in BEST remains 24.1% faster
than CBAX on average.
In addition, we evaluate the impact of different obstacle ratios on the exploration efﬁciency.
Fig. 6.4(a) shows BEST performances similarly to CBAX with regard to increased ratio of obstacles. An increase from 5% to 20% of obstacle ratio results in a climb of 18.6% for CBAX and a
159

rise of 20.4% for BEST in exploration time.

6.5.3

Comparing to a Solution with Known Environments

A known environment and obstacle distribution enables optimization of the relay placement and
traveling paths under a global view. BEST is designed for exploring an unknown environment.
Although only a partial (local) map is exposed for the BS to compute the relay positions and
traveling paths in each iteration, it is desirably to know the how much we may improve if a global
view were provided.
The solution to FST given a known environment is brieﬂy described here. It is a simpliﬁed
and partial version of the “STARS” solution for a known environment in [118]. Given the obstacle
distribution, we compute the sensing positions, relay positions and traveling paths by modeling
using set cover, Steiner connected dominating set (S-CDS), and traveling salesman problems (all
are NP-hard), respectively.
Fig. 6.5(a) shows BEST uses only an average of 4% more relays compared to the S-CDS based
solution (both given sufﬁcient bandwidth conditions). It shows that inaccessibility to a global
map does not hurt much for deploying relay placement. On the other hand, the extra traveled
path length compared to the S-CDS solution is a more notable 30.7% on average, according to
Fig. 6.5(b). An explanation is that the global map will help to choose the shortest paths globally,
leading to signiﬁcant saves in path length. For the relay placement, however, a local placement,
which attempts to“stretch out”: sparsely placing relays to be as far as possible to existing ones,
performs similar to a global S-CDS to connect the BS to any sensing position, which together
covers the whole region.

160

Fig. 6.4(b) shows the bandwidth constraint’s impact on the number of relays deployed. The
number of relays rises 82.8% for K = 3 and another 68.9% for K = 2 on average respectively
compared to the bandwidth sufﬁcient case. The results demonstrate the signiﬁcant impact of QoS
on the number of relays: when there is no unsaturated path, new relays are deployed.

6.6
6.6.1

Future Work
Extension with Multiple Relay-deploying Robots

In the future, we will enhance BEST with multiple RDN to reduce the work load of each RDN
and make the solution more scalable with increase in |FN| and ﬂow sending rate. Multiple relay
deploying robots are a natural consideration when a single RDN has a high workload of relay
deployment and a lengthy traveling path to keep track a large number of FN.
With n number of RDN, we may dynamically partition the FN to different clusters and assign
the RDN to its closest cluster of FNs. The partition’s objective may be set to (1) achieve a work
load balance for each RDN: minimize the largest difference of vrdn among RDNs; (2) reduce the
total energy cost: minimize the sum of all vrdn among RDNs.

6.6.2

Towards Traveling Path Aware Relay Deployment

Currently BEST solves FST problem by ﬁrst computing the relay positions. With the relay positions as input, the traveling path is obtained by computing the Hamiltonian path. In a more
integrated approach, it is desirable that the relay placement outputs a set of candidate positions
where the next step can further evaluate which candidates are better. The uncertainty of the posi-

161

tions for the traveler to travel resembles the Generalized TSP problem [119], where the position
set G is partitioned into clusters and the objective is to ﬁnd the shortest cycle in G which passes at
least one position in each cluster.
Modeling: We may model the FST problem in part by Generalized TSP since there is ﬂexibility
and “room” for the relay placement between any two end positions. (e.g. Given distance of 5m
and communication range of 2m, two relays can be placed in a set of positions as long as any two
neighboring nodes has a distance of no more than 2m.) Therefore, the relay placement will output
a candidate set of positions for each relay, which will be the input for Generalized TSP to further
reduce the path length compared with ﬁxed positions.
Discussions: In the future, we would like to implement BEST with traveling path-aware relay
deployment to observe its impact on the performance and verify different possible impacts discussed below. It is possible that we may not beneﬁt from the Generalized TSP based solution
when the relay deploying time is large and obstacle ratio is low. The reason is that relays may be
placed more densely and closer to the existing ones, in order to reduce the local travel path given
the ﬂexibility of relay positions. This measure, however, may not help from a global view.
On the other hand, it is also possible performance may be improved when the obstacle ratio is
high and the relay deploying time is low. The reason is that the reduction in traveling paths may
outweigh the increased number of relays. With densely random obstacles, placing relays sparsely
to be “as far as possible” from existing relays may not be optimal.

162

6.7

Summary

In this chapter, we propose BEST, or the Bandwidth-aware Exploration with a Steiner Traveler for
an unknown environment. BEST computes the relay deployment positions and traveling paths for
the relay-deploying robot to keep track of a group of frontier robots. BEST enables bandwidthaware real-time multimedia transmissions to support remote sensing and control of a group of
robots. In addition, we show BEST is extensible with multiple RDNs in Section 6.6.
We model the problem by the minimum velocity Flow constrained Steiner Traveler problem
(FST). FST combines two of the most important combinatorial optimization problems: the traveling salesman and the Steiner minimum tree problems. Our solution to FST places new relays to
connect to existing ones with unsaturated paths rather than to the BS when using existing relays
can reduce the number of relays.
BEST signiﬁcantly reduces the exploration time by 62% compared to existing homogeneous
robot exploration strategies. BEST also reduces the cost by achieving 24% better exploration
efﬁciency with only half the number of robots compared to its comparison counterpart. We also
ﬁnd a marginal improvement in relay number but a notable traveling path length reduction, if a
global obstacle distribution were known. In the next chapter, we will focus on coping with mobility
and communication in rugged terrains with the other type of mobile nodes: sensors with hopping
capability.

163

CHAPTER 7
Hopping Sensor Relocation in Rugged
Terrains

7.1

Preliminaries

Besides the QoS provision and mobile control for teleoperation discussed in the previous four
chapters, another major topic in this dissertation is to deal with obstructive environment. The
motivation is that the environments are not obstacle free in most applications of mobile networks
such as weather sensing, environment monitoring, disaster management, and battleﬁeld surveillance. For the network whose nodes are mobile robots, we have tackled the exploration problems
to search in an unknown obstructive environment. Besides the powerful robots, the other most
common devices in mobile networks are the sensor nodes. In this chapter, we focus on hopping
sensors, whose distinctive movement approach is designed to ﬁt the rugged terrains.
In addition to the inadequacies of hopping sensors such as imprecise movement and limited
power mentioned in Section 1.2.1, rugged terrains may also adversely affect their behaviors.
164

Rugged terrains are the areas that are largely inaccessible to wheeled vehicles, where hopping
sensors may operate by trading-off movement accuracy. We model the rugged terrains with two
characteristics. The ﬁrst one is their unevenness with diverse slope patterns. Due to such diversity
and arbitrary nature of the terrains we did not model them with slopes in the relocation process.
However, we ﬁnd that hopping sensors are more energy efﬁcient when moving on certain slope
ground by comparing their energy consumption with the wheeled ones.
The second feature is the existence of great obstructions in the ﬁeld that can signiﬁcantly inﬂuence the sensor relocation. To illustrate, water, huge rocks, and other obstructions are inaccessible
areas to deploy sensors. It is critical to design a movement scheme that can wisely avoid or circumnavigate these obstructions to reach the expected position. Given an initial sensor deployment,
the proposed solution is to match and relocate a redundant sensor to the needed position in an
obstructed environment. Furthermore, it must also consider the limited number of hops per sensor
and the incapability of sensors landing at a precise location. To tackle these problems, we present
(i) a distributed message forwarding model called Binary Splitting Message Forwarding (BSMF)
and (ii) a grid based movement model unique to these hopping sensors.
The rest of the chapter is organized as follows. In Section 7.2, the motivation for using hopping
sensors is presented. A description of our system model is in Section 7.3. The matching scheme
is in Section 7.4. Section 7.5 deﬁnes the Grid Based Movement Model. Section 7.6 provides
simulations and performance analysis. Summary is presented in Section 7.7.

165

Figure 7.1. Hopping sensors we designed deployed near a construction area [4].

7.2

Motivation

The motivation of using hopping sensors over wheeled ones in rugged terrains is twofold. The
ﬁrst one is that hopping sensors can access many difﬁcult areas whereas wheeled sensors cannot.
Second, for certain types of slopes, which frequently exist in rugged terrains, hopping sensors are
more energy efﬁcient. In this section, we focus on the second motivation to compare the energy
consumption for two cases: ﬂat plane and slope. To make the comparison reasonable, only the
energy used to drive the sensor is considered.
We ﬁrst conduct an analysis on a ﬂat plane. Under ideal condition, the hopping sensor’s trajectory is a projectile motion. In [76], wind inﬂuence is modeled as a predictable and stable parameter,
which is a strong assumption due to its dynamic nature. Here we assume a negligibly weak wind
setting and no sliding occurs during initial state of hoping. Given the sensor’s mass m, the initial
velocity v, the takeoff angle α, and the distance traveled by the sensor d, the energy per hop will

166

be:
1
mgd
Eh = mv 2 =
2
2 sin 2α

(7.1)

For wheeled sensors, we suppose they have the same weight and need to traverse the same
distance. Let the rolling friction coefﬁcient for the ﬂat plane be μ and the sensor run at a constant
speed. Then energy for traversing such a distance is:
Ew = μmgd

(7.2)

Ew
= 2μ sin 2α
Eh

(7.3)

To compare:

The rolling friction coefﬁcient between wheels and land is generally less than 0.1 [120], therefore Ew /Eh < 0.2, which means Eh > Ew . Therefore, for ﬂat plane, the wheeled sensor is more
energy efﬁcient. This is because part of the energy for hopping sensors is converted to the potential
energy for hopping height.
Now suppose both sensors need to traverse the same distance along a slope with an inclination
angle β. For hopping sensors, with the same assumption in the ﬂat plane, the jumping distance
along the slope can be found from the intersection of the projectile trajectory and the slope. Establish a coordinate frame as shown in Fig. 7.2, where O is the starting point. Then the x coordinate
for the intersection point is:
x = d(1 − cot α tan β)

(7.4)

Thus d = x/ cos β. The energy for hopping sensors to travel d is the same as traveling d on
the ﬂat plane.

167

Figure 7.2. Coordinate frame for slope plane.

168

For wheeled sensors, using the same assumption for ﬂat plane, the energy consumption of
traversing d along the slope is:
Ew = d(μmg + mg tan β)(1 − cot α tan β)

(7.5)

Ew
= 2 sin 2α(μ + tan β)(1 − cot α tan β)
Eh

(7.6)

To compare:

Typically, the rolling friction coefﬁcient for car tire on concrete is between [0.01, 0.015] [120].
Let μ = 0.0125. Given α = 75◦ , the takeoff angle of the hopping sensor we have developed [4]
(Figure 1.1(b)), we derive the diagram in Fig. 7.3 from equation (7.6) to show the change of above
energy ratio with respect to slope angle 0◦ ≤ β ≤ 75◦ .
As we can see from the ﬁgure, when 30◦ < β < 72◦ (the curve between two vertical lines),
Eh < Ew . The ratio decreases after about 62◦ because d becomes increasingly smaller as the
inclination angle is close to the takeoff angle, resulting in less energy consumed by wheeled sensor.
The energy per hop for hopping sensors, however, remains the same. This explains why the ratio
decreases. Nevertheless, most wheeled sensors can only move along slope with an angle less than
45◦ [121]. Hence we can neglect the declining part after approximately 62◦ , and conclude the
hopping sensor is more energy-efﬁcient than the wheeled sensor for slope angle greater than 30◦
for takeoff angle 75◦ . In fact, with different takeoff angles, a critical angle always exists when a
hopping sensor consumes less energy than a wheeled one.

169

2

w

E /E

h

1.5

1

0.5

0

10

20

30 40 50
β (degree)

60

Figure 7.3. Energy ratio for 0◦ ≤ β ≤ 75◦ .

170

70

7.3

System Model

Now that we have shown the hopping sensors are energy efﬁcient on uneven ground, in this section
we discuss the system model. A grid-based architecture is a natural solution in a network where
nodes are relatively regularly deployed. Each grid cell is controlled by a gateway sensor which
is capable of communicating with its peers in its immediate four neighbors (North, South, East,
West). The gateway sensors can retrieve their absolute positions and have a larger sensing range
than other sensor nodes. Sensor nodes within a grid cell register to the cell gateway and perform
their required tasks.
The width (size) of a square grid cell is deﬁned by: Wc = Rg /k, where Rg is the effective
communication range of the gateway and k is the coverage factor. Assuming the gateway located
at the center of the cell and given k=1.41 or k=1.5, 88.4% or 97.2% of 4-neighbor area can be
covered respectively for effective inter-gateway communication. Due to space limitation we leave
the analysis of the optimal grid cell size in future work.
When a sensor dies, a redundant sensor needs to be relocated to cover the sensing hole area. A
redundant sensor can be easily identiﬁed on a given cell by the gateway. To maintain the sensor
coverage when sensor holes appear, two major steps remain. In the ﬁrst step, a match is needed between the supplier and consumer cell. Note that more than one supplier may exist. The consumer
decides which supplier is selected. Then, a viable path from the supplier to the consumer needs to
be computed for the movement. Second, the consumer triggers the relocation process by notifying
the selected supplier, which in turn selects one of its redundant sensors and commands it to reallocate to the neighbor cell included in the path. We mainly focus on single sensor relocation. The
problem of multiple sensor relocation can be easily solved by executing the scheme repeatedly.

171

The principal objective of this work is to provide an optimized matching path between a consumer and a supplier cell, involving the least amount of intermediate cells possible. A matching
process is fundamentally important to the actual sensor movement and must remain workable in
presence of obstructions. In our model, obstructions are represented as non-functional grid cells
in which a gateway is hard to be placed, or if it exists, it fails to communicate with neighboring
cells. These obstructed cells, with high probability, will not allow an intersection cell to match
consumer and supplier cell. To overcome this problem, centralized or decentralized algorithms
can be considered.
A centralized solution usually inherits the single-point-of-failure weakness, which is less faulttolerant in hostile environment or a rugged terrain where adverse circumstances are frequent. In
addition, it is a strong assumption that a single node has adequate energy and computation capability to communicate with all the other sensor nodes and to ﬁnd the optimized path for relocation.
Since the existence of supplier and consumer is ad hoc and the relocation should be executed efﬁciently, the latency incurred by gathering supplier and consumer information becomes a drawback.
To be more fault-tolerant, less susceptible to the impact of mobility, and to reduce message
overhead and latency in the process of collecting information [122], our algorithm should depend
only on local information collected by each gateway to establish the matching path between the
supplier and the consumer. To make it more practical, gateway communication is restricted to be
with the four-neighboring gateways, and between gateway and managed sensors in the cell.

172

7.4
7.4.1

Matching Process
Message Forwarding Process

Previous Grid-Quorum relocation would fail if there are obstructions in the middle of the supplier
or consumer quorum. We propose Binary Splitting Message Forwarding (BSMF) to cope with
obstructions. The algorithm provides a matching path for a consumer and supplier cell, and it
considers previously known and newly appearing obstructions.
When a gateway receives an advertisement or request message, it veriﬁes whether it satisﬁes
the demand or needs to forward the message. Before forwarding messages, gateways check the
availability of the succeeding neighbor. Succeeding neighbors will vary depending on the message
type. Advertisement messages are forwarded to neighbor grid cells in a grid row manner (EastWest), while request messages are forwarded in a grid column manner (North-South). When a
gateway in a grid cell receives both the advertisement and the request message, the cell becomes
an intersection node and the gateway in it will be responsible to match the request to the advertisement. Without obstructions, it is ensured by geographic relations that an intersection is made [80].
If a known or a new obstruction is detected in the next forwarding grid cell, this gateway will
change the course by modifying message forwarding behavior in an effort to successfully forward
the message. Given an obstruction, a request message may attempt to be forwarded to the EastWest grid cell neighbors, while an advertisement message may be forwarded to the North-South
neighbors. However, they will return to their default (initial) directions whenever it is possible.
If both of the intended grid cell destinations are obstructed or visited before, the message will be
forwarded in a direction opposite to the default until one available grid cell is found. Algorithm

173

BSMF gives a step representation of this procedure.
Algorithm 21: Binary splitting message forwarding (BSMF).
Input: Current cell’s gateway G receives an incoming message with i) default forward
direction Df w ; ii) message traversed path
Output: Destination neighbor cell(s) {N Cd } of the message
1 Begin: Supplier and consumer cells have sent row advertisement or column request
messages respectively
// Set opposite and two perpendicular directions of Df w
2 Dopp , Dlef t , Dright ← Df w
// N C denotes a ”neighbor cell”
3 if N C on Df w is available ∧ unvisited then
4

{N Cd } ← N C

// On default whenever possible

5 else
6

{N Cuv av } ← unvisited ∧ available N C on Dlef t , Dright

7

if {N Cuv av } = ∅ then

8
9

{N Cd } ← {N Cuv av }
else

10

if N C on Dopp is available then

11

{N Cd } ← N C on Dopp

12
13

else
{N Cd } ← N C from which the message was sent

14 foreach i ∈ {N Cd } ∧ i is out of border do {N Cd } ← {N Cd }\i
15 The message is forwarded to {N Cd }
16 if both advertisement and request messages are found then
17

The advertisement of the closest supplier with the request are forwarded to {N Cd } on
the path to the consumer

Figure 7.4 illustrates an example of BSMF. A supplier S(7,0) sends the advertisement message

174

0
0
1
2
3
4

1

2

3

4

I

5

I

6

7

8

9

S

x
xx
x x

5
X
I
C
S

6
7

C

8
9

Obstacles
Intersections
Consumer
Supplier
SupplierQuorum
ConsumerQuorum

Figure 7.4. Binary splitting message forwarding.

175

in the ﬁrst row (X,0) while the consumer C(2,7) initiates the request message in column (2,X).
When the gateway at (2,5) receives the request message, it sends a message to check grid cell (2,4)
availability. As (2,4) fails to reply, it indicates a new obstacle. Consequently the message is split
to (2,5) West and East neighbors (1,5) and (3,5). The message continues to be forwarded in the
column of (1,X), while in (3,4), the gateway ﬁnds the targeting grid cell (3,3) is an obstructed one.
It attempts to ask its East-West neighbors to help forwarding but they do not respond. The gateway
at (3,4) sends the message back to (3,5). The gateway at (3,5) will try to split the message but
since it ﬁnds that (2,5) has been visited it forwards the message to (4,5) only. As (4,4) contains
an obstacle, (4,5) will forward the message to (5,5) as well, which then is able to forward in an
upward direction. Finally the intersections I(1,0) and I(5,0) are made. Both of them will forward
the path information to the consumer. The consumer in (0,7) calculates the length of the two paths
gathered as 15 and 13 and selects the path with length 13. It then triggers the movement process
by notifying the supplier.
When multiple suppliers exist, the consumer selects the supplier by the following rules. (i)
An intersection cell informs the consumer of the advertisement from the closest suppliers. An
intersection cell formed by immediate neighboring supplier does not continue to forward the advertisement in the same row. (ii) A consumer cell waits for a predetermined time after receiving
the ﬁrst supplier quorum to allow the arrival of other existing quorums. (iii) The level of sensor
redundancy breaks the tie when multiple supplier paths are of equal distance. A supplier cell with
more sensors is chosen.

176

0
0

1

2

3

4

5

I

6

7

8

9

I S

1
2
3
4
5

x
xx
x x
x
x

6
7

X
I
C
S

C

8
9

Obstacles
Intersections
Consumer
Supplier
SupplierQuorum
ConsumerQuorum
Actual Movement Path

Figure 7.5. Movement path optimization.

177

7.4.2

Path Optimization

The matching process of the sensor supplier and consumer lays a foundation for the actual sensor
movement. With the presence of obstructions, the path in the matching process may include some
redundant cells that can be eliminated from the actual relocation process. Such an optimization
can further reduce the movement time in the relocation process, which is deﬁned by two additional
rules below to check the cells in the matching process. Figure 7.5 also illustrates the idea.
• Rule 1 (Remove dead-end routes): The cell sending a backward message is removed. (e.g.,
In Fig.7.5, cell (3,4) is removed.)
• Rule 2 (Remove non-straight neighboring routes): The nodes between two adjacent neighboring path nodes are removed. (e.g., In Fig.7.5, cells (3,5), (4,5) are removed.)

7.5
7.5.1

Sensor Migration
Grid Based Movement Model

Having obtained the matching path between the consumer and supplier cells, we need to determine
how to move the sensor to the target location. There are typically two migration methods:
• Direct movement: transfer the sensor from supplier to consumer directly;
• Cascaded movement: using intermediate nodes as relaying ones.
Nevertheless, both methods are based on Precise Movement Model (PMM) [80], which uses
a sensor to exactly replace another one. In [76], although the authors assume that the sensors can
reach the destination if they hop into the target cluster, this is also PMM since the clusters are
178

treated as points. Thus each sensor’s target is also precise. Due to the inaccurate nature of hopping
sensors, we propose a Grid Based Movement Model (GBMM), in which the sensor is only required
to move to the target grid cell. Such a pattern ﬁts hopping sensors better since it is not easy for
them to be relocated to the exact position and the gateway can easily manage the sensors within its
grid cell. Moreover, relaying sensors can move concurrently to save time.
Using GBMM, the most energy efﬁcient way is to transfer the sensor closest to the border
between its current cell and the neighboring target cell. The main idea of PMM and GBMM is
shown in Fig. 7.6. In Fig. 7.6(a), the predecessor is to move to the successor’s position to replace it
until the last sensor arrives at the destination. Fig. 7.6(b) illustrates the GBMM. As long as a sensor
enters its destination cell, its relocation is accomplished. When the path is the same, it is easy to
observe that GBMM can consume less energy compared with PMM because of the decrease of the
path length for each transfer.

7.5.2

Energy Computation

Using the hopping model in [76] and given the average distance per hop for the sensor as r, the
ﬁnal landing point is subjected to a two dimensional normal distribution Δr ∼ N (0, δ 2 I), where I
is the 2×2 identity matrix. Note that we assume the independence of the two dimensions because
the ﬁnal landing point is independent of the directions. Assuming the acceptable landing area is
within 3δ (this can ensure most of the jumps land in the target area), the number of hops to traverse
a distance l satisﬁes:

l
l
≤N ≤
r + 3δ
r − 3δ

179

(7.7)

X

X

X

Gateway

X

Sensor Node

X

Destination

(a) Precise Movement Model.

X

X

Gateway

X

Sensor Node
X

X

Destination

(b) Grid Based Movement Model.
Figure 7.6. PMM vs. GBMM.

180

Number of Cells involved in Matching

2500
Broadcast
Binary Split

2000
1500
1000
500
0
0

500
1000 1500 2000
Number of Cells in Network

2500

Figure 7.7. Simulation results: broadcast vs. binary splitting matching.
We use the ﬂoor on the left and ceil on the right to ensure that the robot can travel the distance
l. Assume the number of cells along the path is n + 1 including the starting and destination cell,
then the number of cell crossing is n. Suppose the distance from the closest sensor in each cell i
to the border is li , (i = 1, · · · , n) (this can be maintained or computed by the gateway), then total
hops H for GBMM is between:
n
i=1

li
≤H≤
r + 3δ

n
i=1

li
r − 3δ

(7.8)

If the energy for each hop is E, then we can get the upper bound and lower bound for the energy
as EH for migration. We can also estimate the maximum energy as:
En

Wc
r − 3δ

because li is always less than the width of grid cell Wc .

181

(7.9)

Number of Cells involved in Matching

1500

1000

No Obstructions
5% Obstructions
10% Obstructions
15% Obstructions

500

0
0

500 1000 1500 2000
Number of Cells in Network

2500

(a) Number of cells in matching with varying obstructions.

Number of Hops

250
200
150
100
50
0
0

No Obstructions
5% Obstructions
10% Obstructions
15% Obstructions
500
1000 1500 2000
Number of Cells in Network

2500

(b) Number of hops in movement with varying obstructions.
Figure 7.8. Simulation results: number of cells in matching and number of hops in movement.

182

7.6

Performance Evaluation

To validate the correctness and effectiveness of our algorithm and proposed models, we simulated
the hopping sensor network with random positioned supplier and consumer cells. Scenarios were
designed with grid sizes of 10 ∗ 10, 20 ∗ 20, 30 ∗ 30, 40 ∗ 40 and 50 ∗ 50 grid cells. Each grid
cell, with 3-5 hopping sensors randomly distributed, represents an area of 60 ∗ 60 square meters,
which allowed us to represent ﬁelds areas up to 9km2 . Hopping sensors are assumed to have a
hopping range with a landing precision radius varying from 2.1 to 3.9 meters. Each hop is modeled
to consume a random time between 2 and 5 seconds. Obstructions are randomly distributed in the
network and are simulated as non-functional grid cells. Simulations also compared varying number
of obstructions with: 0%(no obstructions), 5%, 10%, 15% of obstruction ratio to the total number
of grid cells. For each simulation, experiments are run 50 times to calculate average values.
The ﬁrst two simulations are to evaluate the performance in the matching process by measuring
network load (grid cells involved in packet forwarding). As shown in Figure 7.7, BSMF has
a much fewer number of grid cells involved in the matching process with 5% obstruction ratio
compared to the broadcast approach which guarantees a matching if it ever exists. The conventional
quorum-based matching fashion is not compared as it fails with presence of obstructions. In the
extreme case, BSMF involves only 9.4% cells to participate compared with broadcast. In Figure
7.8(a), the performance of BSMF for varying grid sizes and amount of obstacles is tested and
veriﬁed. On average, BSMF involves 80.2% less cells compared to the broadcast approach. Fewer
amounts of involved cells indicate much lower total energy consumption, considerably less packet
transmission and network trafﬁc generated in the process.
The third simulation evaluates the number of hops and time in the sensor movement process.

183

Its objective is to measure the total amount of hops taken by sensors to perform the relocation
movement after obtaining the relocation path by BSMF. As presented in Figure 7.8(b), the varying
number of obstacles has little impact on the number of hops in our model, which demonstrates that
the movement spends almost a constant amount of energy, regardless of the amount of obstacles in
the movement process. The nearly constant number of hops is contrasted by the trend of network
trafﬁc in the second simulation. This result can be explained as the movement is only related to
the quorum with the “optimized” intersection, while the matching process is to generate all the
possible routes to link the consumer and supplier.

7.7

Summary

In this chapter, we address the problem of relocating the capability-constrained hopping sensors
in an obstructive environment. We propose an enhanced Quorum-Grid solution with Binary Splitting Message Forwarding (BSMF), which is decentralized and can detect both existing and newly
appearing obstructions in the supplier and consumer cells matching process. Furthermore, a gridbased movement model is introduced for the hopping sensors. Simulation shows that our scheme
signiﬁcantly reduces the communication overhead and achieves relatively constant total energy
consumption with varying amount of obstructions. In the next chapter, we summarize the schemes
in previous chapters and show our proposed future research work.

184

CHAPTER 8
Summary and Proposed Future Research
Work

8.1

Summary

As mobile devices have been increasing popular in the last decade, supporting multi-hop mobile
wireless networks have attracted increased attention. In this dissertation, ﬁrst, we argue that it
is of vital importance to consider the impact of mobility on the network QoS in wireless mobile
networks. As topology is the core element in wireless networks inﬂuencing their performance,
mobility should be more thoroughly analyzed even controlled because it is the mobility pattern
that changes the topology all the time. While mobility patterns for humans and many other objects
are highly unpredictable and uncontrollable, the patterns in many applications for mobile sensors
and robots are not uncommon to be predictable even controllable with a certain constraint. The
model of mobile coordinated networks has not yet received adequate attention. However, it enables
coordination and control on mobility patterns, and is therefore a promising new paradigm for QoS
185

provision in wireless mobile networks.
Second, we argue that mobility and communication are two critical and inter-dependent topics
and we believe that jointly considering the two aspects is essential in many research ﬁelds. An
interdisciplinary research from both networking and robotics perspective is necessary for solving
our problem in Chapter 3. From the mobile robotics viewpoint, we leverage algorithmic and
graph-theoretic tools to systematically solve the connectivity and bandwidth-aware multi-robot
exploration problem. CBAX in Chapter 3 achieves both improved efﬁciency in exploration time
and enhanced quality for communication. From the multi-hop mobile network perspective, CBAX
demonstrates how a pragmatic coordinated mobility model can ensure the network connectivity
and enhance its quality of service.
Third, we believe the extensive applications in mobile robot networks endow us with new opportunities of exploring the tight interdependence and connection of mobility and communication.
Multi-robot real-time exploration exhibits such interdependence: On one hand, the aggregated
video/audio streams at the BS reveals the global obstacle distribution and guides the robot placement and mobility pattern. On the other hand, the robot movement and proper placement impact
the quality of the stream aggregation. As such interdependence is also reﬂected in the tradeoff of
link capacities and transmission ranges, we leverage the tradeoff in the exploration task to significantly reduce the RN size while guarantee the connectivity and bandwidth adequacy for stream
aggregation. In addition, interference is tackled by the multi-channel multi-radio architecture with
dynamic TDMA scheduling. Our framework in Chapter 4 has broad applications in area exploration, stream aggregation, and teleoperation tasks with remote sensing and control.
Fourth, we propose a novel online relay deployment paradigm to support remote sensing and
control in multi-robot target search, environmental monitoring, and area exploration. With a more
186

cost-effective heterogenous system composed of mobile robots, sensors, and relay nodes, the online relay deployment gives much larger freedom for robots to travel in the area while satisfying
the connectivity and bandwidth requirement for remote sensing and control from the base station.
Fifth, we ﬁnd that the well known combinatorial problems, such as the traveling salesman and
the Steiner minimum tree problems have wide applications when we jointly consider mobility and
communication for mobile wireless networks. In this dissertation, several new variations of these
classic problems have been formulated to model the coordinated mobility patterns and communication requirements, such as (1) Steiner minimum tree problem with minimum Steiner points
and γ-inﬂow constraint, (2) heterogeneous bandwidth Steiner routing (HBSR), (3) minimum time
precedence constrained two traveling salesman problem (PC2TSP) from a given city, and (4) minimum velocity ﬂow constrained Steiner traveler problem (FST). Formulation of the problem (4)
FST combines both the traveling salesman and the ﬂow constrained Steiner tree problems, further
demonstrates the need of jointly considering the (i) tour generation, node placement (mobility),
and (ii) bandwidth constraints (communication). These new problems and their solutions facilitate
us to improve the mobility efﬁciency and communication quality in mobile wireless networks.
Last, we argue that the obstructive environment such as rugged terrains is non uncommon
in many applications and a special type of low cost mobile sensors effective in such environment is highly desirable. Therefore, we studied the sensor relocation considering obstructions and
proposed an enhanced Quorum-Grid relocation solution with an optimized BSMF algorithm in
Chapter 7. The proposed algorithm is decentralized and can detect new obstructions in the sensor supplier and consumer matching process. Furthermore, the grid-based movement model is
developed and studied with energy computation, suitable for imprecise-movement hopping sensors. The relocation cost has been taken into account, by implementing a path optimization during
187

matching process execution. Simulation with different grid sizes, random distribution of hopping
sensors, and varying amount of obstructions shows that our scheme reduces the involved number
of cells in the matching process by 80.2% on average compared to the broadcast approach and
achieves relatively constant total energy consumption by evaluating total number of hops in the
actual movement.

8.2

Proposed Future Research Work

In the future work of this research, the proposed methods to jointly consider mobility and communication to improve the network quality of service as well as to enhance the mobility effectiveness
and efﬁciency can be further enhanced and veriﬁed. In particular, we propose the following major
directions below in the future research work.
• We plan to build a real multi-robot platform to evaluate the effectiveness and efﬁciency of
coordinated mobility control and path planning scheme, QoS in video and audio stream
aggregation, and interference elimination of multi-radio channel assignment schemes presented in Chapter 3, 4. With the popularity of 802.11n devices, we would like to evaluate
the improvement in link capacity when mobile nodes are equipped with 802.11n communication chips. The testing environment will be (i) outdoor, i.e., the garden with pathways and
obstacles close to the engineering building of Michigan State University, (ii) indoor, i.e., the
hallway of engineering building. Collaborating with the hopping sensor development team
at Robotics and Automation Laboratory in Electrical and Computer Engineering Department
at Michigan State University, we would like to build a small scale (i.e., 3-10 nodes of hopping sensors) to test on the energy consumption and hopping accuracy when relocating in
188

both artiﬁcial and real rugged terrains.
• It is promising to further reﬁne the multi-robot real-time exploration for remote sensing
and control. It is desirable to test the real-time aggregation under 802.11n environment.
Also, with the proliferation of 3G/4G networks, it is also interesting to observe a hybrid
use of 802.11 and 3G/4G network for bandwidth-consuming real-time data transmission. In
addition, some other issues, such as search with control from multiple base stations, handling
fault sensors and relays, and coping with dynamic bandwidth requirements due to changing
tasks of teleoperation, are also interesting and worthy of further investigation.
• Online relay deployment with precedence constrained multi-robot motion planning provides
an alternative method to support remote sensing and control in search targets and monitor
environments . In the future, it would be interesting to (1) evaluate the impact of different
relay sizes, relay deployment strategies, and carrying capacities on search time, (2) ﬁnd the
optimal precedence constraint assignment or solving the contrained tour generation problem
with uncertain precedence constraints, (3) ﬁnd the optimal precedence constraint assignment
or solving the problem with uncertain precedence constraints, (4) apply probability based
sensing and communication ranges.
• The hopping sensors are a promising type of mobile sensor for relocating in rugged terrains.
In the future, we will (1) model and analyze the unevenness and patterns of the rugged
terrain; (2) enhance the BSMF algorithm to cope with newly appearing obstructions during
the sensor movement process; (3) compute the optimal grid cell size for the grid structure.

189

BIBLIOGRAPHY

190

BIBLIOGRAPHY

[1] A. C. I. Chen, James C., “Measured performance of 5-GHz 802.11a wireless
LAN systems, 2001, available online,” http://epsﬁles.intermec.com/eps ﬁles/eps wp/
AtherosRangeCapacityPaper.pdf.
[2] M. Inc., “Research robots: Pioneer 3 mobile platform,” http://mobilerobots.com/
ResearchRobots/ResearchRobots/P3AT.aspx.
[3] A. Birk, S. Schwertfeger, and K. Pathak, “A networking framework for teleoperation in
safety, security, and rescue robotics - [wireless communications in networked robotics],”
Wireless Communications, IEEE, vol. 16, no. 1, February 2009.
[4] J.G. Zhao, R.G. Yang, N. Xi, B.T. Gao, and X. G. Fan, “Development of a miniature selfstabilization jumping robot,” Intelligent Robots And Systems, IROS 2009. IEEE/RSJ Int.
Conf. on, 2009.
[5] P. Mohapatra, J. Li, and C. Gui, “Qos in mobile a hoc networks,” Wireless Communications,
IEEE, vol. 10, no. 3, pp. 44 – 52, 2003.
[6] “Wireless sensor network survey,” Computer Networks, vol. 52, no. 12, pp. 2292 – 2330,
2008.
[7] Crossbow, “Mica2 and micaz motes,” http://www.xbow.com.
[8] “Quality of service provisioning in ad hoc wireless networks: a survey of issues and solutions,” Ad Hoc Networks, vol. 4, no. 1, pp. 83 – 124, 2006.
[9] M. TechNet, “Quality of Service technical white paper, chapter 2 - what is network QoS,”
http://technet.microsoft.com/en-us/library/bb742481.aspx.
[10] L. Hanzo-II and R. Tafazolli, “A survey of qos routing solutions for mobile ad hoc networks,” Communications Surveys Tutorials, IEEE, vol. 9, no. 2, pp. 50 –70, 2007.
[11] K. Sohraby, D. Minoli, and T. Znati, Wireless Sensor Networks - Technology, Protocols and
Applications. John Wiley & Sons, 2007.
[12] M. Ringwald and K. R¨ mer, “Deployment of sensor networks: Problems and passive ino
spection,” in 5th Workshop on Intelligent Solutions in Embedded Systems. WISES 2007,
2007.
[13] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for ad hoc network research,” Wireless Communications & Mobile Computing (WCMC): Special issue on Mobile
Ad Hoc Networking: Research, Trends and Applications, vol. 2, pp. 483–502, 2002.
191

[14] “On redundancy, efﬁciency, and robustness in coverage for multiple robots,” Robotics and
Autonomous Systems, vol. 56, no. 12, pp. 1102 – 1114, 2008, towards Autonomous Robotic
Systems 2008: Mobile Robotics in the UK, 10th British Conference on Mobile Robotics Towards Autonomous Robotic Systems (TAROS 2007).
[15] M. A. Batalin and G. S. Sukhatme, “Coverage, exploration and deployment by a mobile
robot and communication network,” Telecommunication Systems, vol. 26, pp. 181–196.
[16] H. Choset, “Coverage for robotics a survey of recent results,” Annals of Mathematics and
Artiﬁcial Intelligence, vol. 31, pp. 113–126.
[17] C. Trevai, Y. Fukazawa, H. Yuasa, J. Ota, T. Arai, and H. Asama, “Cooperative exploration
path planning for mobile robots by reaction-diffusion equation on graph,” in Industrial Technology, 2002. IEEE ICIT ’02. 2002 IEEE International Conference on, vol. 2, 2002, pp.
1266 – 1271 vol.2.
[18] W. Burgard, M. Moors, C. Stachniss, and F. Schneider, “Coordinated multi-robot exploration,” Robotics, IEEE Transactions on, vol. 21, no. 3, pp. 376–386, June 2005.
[19] B. Yamauchi, “Frontier-based exploration using multiple robots,” in Proceedings of the second international conference on Autonomous agents, ser. AGENTS ’98, 1998, pp. 47–53.
[20] R. Zlot, A. Stentz, M. Dias, and S. Thayer, “Multi-robot exploration controlled by a market
economy,” in Robotics and Automation, ICRA 2002. IEEE International Conference on,
2002.
[21] N. Hazon, F. Mieli, and G. Kaminka, “Towards robust on-line multi-robot coverage,” in
Robotics and Automation. ICRA 2006. IEEE International Conference on, May 2006, pp.
1710 –1715.
[22] M. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot coordination: A survey
and analysis,” Proceedings of the IEEE, vol. 94, no. 7, pp. 1257 –1270, 2006.
[23] M. Zavlanos and G. Pappas, “Distributed connectivity control of mobile networks,”
Robotics, IEEE Transactions on, vol. 24, no. 6, Dec. 2008.
[24] N. Michael, M. M. Zavlanos, V. Kumar, and G. J. Pappas, “Maintaining connectivity in
mobile robot networks,” in International Symposium on Experimental Robotics, ISER 2008.,
Athens, Greece, 2008.
[25] J. Tan, N. Xi, W. Sheng, and J. Xiao, “Modeling multiple robot systems for area coverage
and cooperation,” in Robotics and Automation. ICRA 2004. IEEE International Conference
on, 2004.
[26] S. Poduri and G. Sukhatme, “Constrained coverage for mobile sensor networks,” in Robotics
and Automation. Proceedings. ICRA 2004. IEEE International Conference on, 2004.
192

[27] P. Ogren, E. Fiorelli, and N. Leonard, “Cooperative control of mobile sensor networks:adaptive gradient climbing in a distributed environment,” Automatic Control, IEEE
Transactions on, vol. 49, no. 8, pp. 1292 – 1302, 2004.
[28] F. Zeiger, N. Kraemer, and K. Schilling, “Commanding mobile robots via wireless ad-hoc
networks - a comparison of four ad-hoc routing protocol implementations,” Robotics and
Automation. ICRA 2008. IEEE International Conference on, May 2008.
[29] K. Dantu and G. Sukhatme, “Connectivity vs. control: Using directional and positional cues
to stabilize routing in robot networks,” in Robot Communication and Coordination, 2009.
ROBOCOMM ’09. Second International Conference on, 31 2009.
[30] D. Moraes, P. Coelho, E. Cardozo, T. Johnson, F. Atizani, and E. Guimaraes, “A network
architecture for large mobile robotics environments,” in Robot Communication and Coordination, 2009. ROBOCOMM ’09. Second International Conference on, 31 2009.
[31] K. Wurm, C. Stachniss, and W. Burgard, “Coordinated multi-robot exploration using a
segmentation of the environment,” in Intelligent Robots and Systems, 2008. IROS 2008.
IEEE/RSJ International Conference on, Sept. 2008.
[32] A. Franchi, L. Freda, G. Oriolo, and M. Vendittelli, “The sensor-based random graph
method for cooperative robot exploration,” Mechatronics, IEEE/ASME Transactions on,
vol. 14, no. 2, April 2009.
[33] R. Rocha, F. Ferreira, and J. Dias, “Multi-robot complete exploration using hill climbing
and topological recovery,” in Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ
International Conference on, Sept. 2008.
[34] W. Sheng, Q. Yang, J. Tan, and N. Xi, “Distributed multi-robot coordination in area exploration,” Robotics and Autonomous Systems, vol. 54, no. 12, 2006.
[35] J. Vazquez and C. Malcolm, “Distributed multirobot exploration maintaining a mobile network,” in Intelligent Systems, 2004. 2nd International IEEE Conference on, vol. 3, June
2004.
[36] M. N. Rooker and A. Birk, “Multi-robot exploration under the constraints of wireless networking,” Control Engineering Practice, vol. 15, no. 4, 2007.
[37] F. Amigoni, “Experimental evaluation of some exploration strategies for mobile robots,” in
Robotics and Automation. ICRA 2008. IEEE International Conference on.
[38] H. Sugiyama, T. Tsujioka, and M. Murata, “Coordination of rescue robots for real-time exploration over disaster areas,” in Object Oriented Real-Time Distributed Computing, ISORC
2008. 11th IEEE International Symposium on, May 2008.

193

[39] A. Mosteo, L. Montano, and M. Lagoudakis, “Multi-robot routing under limited communication range,” Robotics and Automation. ICRA 2008. IEEE International Conference on,
May 2008.
[40] K. E. Bekris, K. I. Tsianos, and L. E. Kavraki, “A distributed protocol for safe real-time
planning of communicating vehicles with second-order dynamics,” in Robot Communication and Coordination. RoboComm 2007. 1st International Conference on, 2007.
[41] J. Reich, V. Misra, D. Rubenstein, and G. Zussman, “Connectivity maintenance in mobile
wireless networks via constrained mobility,” in INFOCOM, 2011 Proceedings IEEE, april
2011, pp. 927 –935.
[42] W. Guo and X. Huang, “Mobility model and relay management for disaster area wireless
networks,” in Wireless Algorithms, Systems, and Applications, WASA 2008. 3rd International Conference on, 2008.
[43] X. Cheng, D.-Z. Du, L. Wang, and B. Xu, “Relay sensor placement in wireless sensor
networks,” Wireless Networks, vol. 14, no. 3, 2008.
[44] N. Li, B. Yan, and G. Chen, “Measurement study on wireless camera networks,” in Distributed Smart Cameras. ICDSC 2008.
[45] Z. Cen, M. W. Mutka, D. Zhu, and N. Xi, “Supermedia transport for teleoperations over
overlay networks,” in NETWORKING 2005, ser. Lecture Notes in Computer Science,
R. Boutaba, K. Almeroth, R. Puigjaner, S. Shen, and J. P. Black, Eds. Springer Berlin,
Heidelberg, 2005, vol. 3462, pp. 1409–1412.
[46] Z. Cen, M. Mutka, Y. Liu, A. Goradia, and N. Xi, “Qos management of supermedia enhanced teleoperation via overlay networks,” in Intelligent Robots and Systems, 2005. IROS
2005. 2005 IEEE/RSJ International Conference on, Aug. 2005.
[47] S. Misra, S. D. Hong, G. Xue, and J. Tang, “Constrained relay node placement in wireless
sensor networks: Formulation and approximations,” Networking, IEEE/ACM Transactions
on, vol. 18, no. 2, 2010.
[48] D. Yang, S. Misra, X. Fang, G. Xue, and J. Zhang, “Two-tiered constrained relay node placement in wireless sensor networks: Efﬁcient approximations,” in Sensor Mesh and Ad Hoc
Communications and Networks (SECON), 2010 IEEE Communications Society Conference
on.
[49] F. Wang, D. Wang, and J. Liu, “Trafﬁc-aware relay node deployment for data collection
in wireless sensor networks,” in Sensor Mesh and Ad Hoc Communications and Networks
(SECON), 2009 IEEE Communications Society Conference on.

194

[50] D. Yang, X. Fang, G. Xue, and J. Tang, “Relay station placement for cooperative communications in wimax networks.”
[51] X. Han, X. Cao, E. Lloyd, and C.-C. Shen, “Fault-tolerant relay node placement in heterogeneous wireless sensor networks.”
[52] Y. Pei, M. Mutka, and N. Xi, “Coordinated multi-robot real-time exploration with connectivity and bandwidth awareness,” in Robotics and Automation, ICRA 2010. IEEE International
Conference on.
[53] B. Lin, P.-H. Ho, L.-L. Xie, X. Shen, and J. Tapolcai, “Optimal relay station placement in
broadband wireless access networks,” Mobile Computing, IEEE Trans. on, vol. 9, no. 2, feb.
2010.
[54] G. Xue, T. P. Lillys, and D. E. Dougherty, “Computing the minimum cost pipe network
interconnecting one sink and many sources,” SIAM J. on Optimization, vol. 10, 1999.
[55] Y. Pei, M. Mutka, and N. Xi, “Connectivity and bandwidth aware real-time exploration in
mobile robot networks,” in Wiley Wireless Communications and Mobile Computing Journal,
WCMC, (in press).
[56] D. Yang, S. Misra, and G. Xue, “Joint base station placement and fault-tolerant routing in
wireless sensor networks.”
[57] L. Li, G. Xin, L. Sun, and Y. Liu, “Qvs: Quality-aware voice streaming for wireless sensor
networks,” in Distributed Computing Systems, 2009. ICDCS 2009. 29th IEEE International
Conference on.
[58] M. Li and Y. Liu, “Underground structure monitoring with wireless sensor networks,” in
Information Processing in Sensor Networks, 2007. IPSN 2007. 6th International Symposium
on.
[59] T. Bektas, “The multiple traveling salesman problem: an overview of formulations and
solution procedures,” Omega, Int. J. Management Sci., vol. 34, no. 3, 2006.
[60] T. Oncan, I. K. Altinel, and G. Laporte, “A comparative analysis of several asymmetric
traveling salesman problem formulations.” Computers & Operations Research.
[61] L. Gouveia and P. Pesneau, “On extended formulations for the precedence constrained
asymmetric traveling salesman problem,” Networks, vol. 48, no. 2, pp. 77–89, 2006.
[Online]. Available: http://dx.doi.org/10.1002/net.20122
[62] P. Oberlin, S. Rathinam, and S. Darbha, “A transformation for a heterogeneous, multiple
depot, multiple traveling salesman problem,” in American Control Conference, 2009. ACC
’09., june 2009, pp. 1292 –1297.

195

[63] E. Balas and N. Simonetti, “Linear time dynamic-programming algorithms for new classes
of restricted TSPs: A computational study,” INFORMS J. on Computing, vol. 13, no. 1,
2000.
[64] “The multiple TSP with time windows: vehicle bounds based on precedence graphs,” Operations Research Letters, vol. 34, no. 1, 2006.
[65] A. Haumann, K. Listmann, and V. Willert, “Discoverage: A new paradigm for multi-robot
exploration,” in Robotics and Automation, ICRA 2010. IEEE International Conference on.
[66] P. Brass, F. Cabrera-Mora, A. Gasparri, and J. Xiao, “Multirobot tree and graph exploration,”
Robotics, IEEE Transactions on, no. 99, 2011.
[67] J. Yuan, Y. Huang, T. Tao, and F. Sun, “A cooperative approach for multi-robot area exploration,” in Intelligent Robots and Systems, 2010. IROS 2010. IEEE/RSJ International
Conference on.
[68] P. Mukhija, K. Krishna, and V. Krishna, “A two phase recursive tree propagation based
multi-robotic exploration framework with ﬁxed base station constraint,” in Intelligent
Robots and Systems, 2010. IROS 2010. IEEE/RSJ International Conference on.
[69] A. Marjovi, J. Nunes, L. Marques, and A. de Almeida, “Multi-robot exploration and ﬁre
searching,” in Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International
Conference on.
[70] M. Batalin and G. Sukhatme, “The design and analysis of an efﬁcient local algorithm for
coverage and exploration based on sensor network deployment,” Robotics, IEEE Transactions on, vol. 23, no. 4, 2007.
[71] Y. Wang and C.-H. Wu, “Robot-assisted sensor network deployment and data collection,”
in Computational Intelligence in Robotics and Automation, 2007. CIRA 2007. International
Symposium on.
[72] P. Corke, R. Peterson, and D. Rus, “Localization and navigation assisted by networked
cooperating sensors and robots,” International Journal of Robotic Research, 2005.
[73] V. Kumar, D. Rus, and S. Singh, “Robot and sensor networks for ﬁrst responders,” Pervasive
Computing, IEEE, vol. 3, no. 4, 2004.
[74] G. Fletcher, X. Li, A. Nayak, and I. Stojmenovic, “Back-tracking based sensor deployment
by a robot team,” in Sensor Mesh and Ad Hoc Communications and Networks (SECON),
2010 IEEE Communications Society Conference on.
[75] R. Tan, G. Xing, J. Wang, and H. C. So, “Exploiting reactive mobility for collaborative
target detection in wireless sensor networks,” Mobile Computing, IEEE Transactions on,
vol. 9, no. 3, pp. 317 –332, 2010.
196

[76] Z. Cen and M. W. Mutka , “Relocation of hopping sensors,” in Robotics and Automation.
ICRA 2008. IEEE Int. Conf. on, May 2008.
[77] S. Chellappan, X. Bai, B. Ma, and D. Xuan, “Sensor networks deployment using ﬂip-based
sensors,” in Mobile Adhoc and Sensor Systems. MASS 2005. IEEE Int. Conf. on, 2005.
[78] A. Howard, M. J. Mataric, and G. S. Sukhatme, “Mobile sensor network deployment using potential ﬁelds: A distributed, scalable solution to the area coverage problem,” in Distributed Autonomous Robotics Systems. DARS 2002. Int. Symposium on, 2002.
[79] G. Wang, G. Cao, and T.L. Porta, “Movement-assisted sensor deployment,” INFOCOM
2004. 23rd Conference of the IEEE Computer and Communications Societies, vol. 4, 2004.
[80] G. Wang, G. Cao , T.L. Porta, and W. Zhang , “Sensor relocation in mobile sensor networks,”
INFOCOM 2005. 24th Conference of the IEEE Computer and Communications Societies,
vol. 4, 2005.
[81] J. Wu and S. Yang, “Smart: a scan-based movement-assisted sensor deployment method in
wireless sensor networks,” INFOCOM 2005. 24th Conference of the IEEE Computer and
Communications Societies, vol. 4, 2005.
[82] R. Akl and U. Sawant, “Grid-based coordinated routing in wireless sensor networks,” Consumer Communications and Networking Conference. CCNC 2007. IEEE, 2007.
[83] G. Cao and M. Singhal, “A delay-optimal quorum-based mutual exclusion algorithm for distributed systems,” Transactions on Parallel and Distributed Systems. T.PDS, vol. 12, no. 12,
2001.
[84] J.-R. Jiang, Y.-C. Tseng, C.-S. Hsu, and T.-H. Lai, “Quorum-based asynchronous powersaving protocols for ieee 802.11 ad hoc networks,” Mobile Networks and Applications,
vol. 10, no. 1-2, 2005.
[85] M. Younis, P. Munshi, G. Gupta, and S. Elsharkawy , “On efﬁcient clustering of wireless sensor networks,” Dependability and Security in Sensor Networks and Systems. DSSNS
2006. IEEE.
[86] Y. Pei, F. Cintron, M. Mutka, J. Zhao, and N. Xi, “Hopping sensor relocation in rugged
terrains,” in Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, 2009, pp. 3856 –3861.
[87] M. Kim and M. Mutka, “Multipath-based relocation schemes considering balanced assignment for hopping sensors,” in Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ
International Conference on, 2009, pp. 5095 –5100.

197

[88] M. Kim, M. Mutka, and H. Choo, “On relocation of hopping sensors for rugged terrains,”
in Computational Science and Its Applications (ICCSA), 2010 International Conference on,
2010, pp. 203 –210.
[89] M. Lewis, H. Wang, P. Velagapudi, P. Scerri, and K. Sycara, “Using humans as sensors in
robotic search,” in Information Fusion. FUSION 2009. 12th Int. Conference on, 2009.
[90] “Key performance beneﬁts of 802.11n, available online,” http://www.cisco.com/en/US/
solutions/collateral/ns340/ns394/ns348/ns767/white paper c11-513840.html.
[91] D. Du and X. Hu, Steiner Tree Problems In Computer Communication Networks.
Scientiﬁc Publishing Co., 2008, pp. 177–193.

World

[92] H. H. Gonzales-Ba.nos and J.-C. Latombe, “Navigation strategies for exploring indoor environments,” International Journal of Robotics Research, vol. 21, no. 10-11, 2002.
[93] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd
Edition. The MIT Press, 2001, pp. 1056–1061.
[94] S. Russell and P. Norvig, Artiﬁcial Intelligence: A Modern Approach, 2nd Edition.
Prentice-Hall, 2003, pp. 97–101.
[95] R. Burkard, M. Dell’Amico and S. Martello, Assignment Problems.
Industrial and Applied Mathematics, 2009, pp. 172–191.

SIAM: Society for

[96] P. Krokhmal and P. P.M., “Random assignment problems,” European Journal of Operational
Research, vol. 194, no. 1, 2009.
[97] U. Pferschy, “The random linear bottleneck assignment problem,” RAIRO-Operations Research, vol. 30, no. 2, 1996.
[98] H. Gabow and R. Tarjan, “Algorithms for two bottleneck assignment problems,” Journal of
Algorithms, vol. 9, no. 3, 1988.
[99] R. Burkard and E. Cela, “Linear assignment problems and extensions,” Handbook of Combinatorial Optimization, vol. A (Suppl.)., 1999.
[100] “SRG-based video clips from a cluster start with 4 robots,” http://www.dis.uniroma1.it/
∼labrob/research/multiSRG.html.
[101] A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, and S. Suri, “Towards realistic mobility
models for mobile ad hoc networks,” in Mobile Computing and networking, MobiCom 2003.
9th ACM International conference on, 2003.

198

[102] A. Wijesinha, Y. tae Song, M. Krishnan, V. Mathur, J. Ahn, and V. Shyamasundar,
“Throughput measurement for UDP trafﬁc in an IEEE 802.11g WLAN,” in Software Engineering, Artiﬁcial Intelligence, Networking and Parallel/Distributed Computing, 2005 and
First ACIS International Workshop on Self-Assembling Wireless Networks. SNPD/SAWN
2005. Sixth International Conference on.
[103] S. Kakumanu and R. Sivakumar, “Glia: a practical solution for effective high datarate wiﬁarrays,” in Mobile Computing and networking, MobiCom 2009. ACM International conference on.
[104] R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks,” in Mobile Computing and networking, MobiCom 2004. ACM International conference on.
[105] P. Huang, C. Wang, L. Xiao, and H. Chen, “RC-MAC: A receiver-centric medium access
control protocol for wireless sensor networks,” in Quality of Service (IWQoS), 2010 18th
International Workshop on.
[106] “FCC 15.407 as of august 8, 2008 - hallikainen.com, available online,” http://sujan.
hallikainen.org/FCC/FccRules/2008/15/407/.
[107] D. Halperin, W. Hu, A. Sheth, and D. Wetherall, “Predictable 802.11 packet delivery from
wireless channel measurements,” in SIGCOMM 2010: Proceedings of the ACM SIGCOMM
conference on Data communication.
[108] P. Barsocchi, S. Lenzi, S. Chessa, and G. Giunta, “Virtual calibration for RSSI-based indoor
localization with IEEE 802.15.4,” in Communications, 2009. ICC 2009. IEEE International
Conference on.
[109] P. Crescenzi and V. Kann, “A compendium of NP optimization problems,” p. 52, 1998.
[110] E. Malaguti and P. Toth, “A survey on vertex coloring problems,” in International Transactions in Operational Research, 2010.
[111] F. Wang and J. Liu, “Networked wireless sensor data collection: Issues, challenges, and
approaches,” Comm. Surveys Tutorials, IEEE, 2010.
[112] C. Moon, J. Kim, G. Choi, and Y. Seo, “An efﬁcient genetic algorithm for the traveling
salesman problem with precedence constraints,” European J. of Operational Res., vol. 140,
no. 3.
[113] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai, “Deploying wireless sensors to achieve
both coverage and connectivity,” in MobiHoc 2006: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing.

199

[114] S. Guha and S. Khuller, “Approximation algorithms for connected dominating sets,” Algorithmica, vol. 20, no. 4, pp. 374–387, 1998.
[115] S. C. Sarin, H. D. Sherali, and A. Bhootra, “New tighter polynomial length formulations
for the asymmetric traveling salesman problem with and without precedence constraints,”
Operations Research Letters, vol. 33, no. 1, pp. 62 – 70, 2005.
[116] K. Hornik and M. Hahsler, “TSP–infrastructure for the traveling salesperson problem,” J. of
Statistical Software, vol. 23, no. i02, 2007.
[117] N. Ascheuer, M. J¨ nger, and G. Reinelt, “A branch & cut algorithm for the asymmetric
u
traveling salesman problem with precedence constraints,” Comput. Optim. Appl., vol. 17,
2000.
[118] Y. Pei and M. Mutka, “STARS: Static relays for multi-robot real-time search and monitoring,” in Distributed Computing in Sensor Systems (DCOSS), 2011 International Conference
on, June 2011, pp. 1–8.
[119] G. Gutin, A. Punnen, A. Barvinok, E. K. Gimadi, and A. I. Serdyukov, “The traveling
salesman problem and its variations,” 2002.
[120] T. E. Toolbox, “Friction and coefﬁcients of friction,” http://www.engineeringtoolbox.com/
rolling-friction-resistance-d 1303.html.
[121] http://www.mobilerobots.com/.
[122] N. Li, J. Hou, and L. Sha, “Design and analysis of an mst-based topology control algorithm,”
INFOCOM 2003. 22nd Conference of the IEEE Computer and Communications Societies.
IEEE, vol. 3, 2003.

200