Topological Methods of Gr Theory

cover-large.tif......Page 1
front-matter.pdf......Page 2
Book Origin and Overview......Page 6
About the Authors......Page 8
Contents......Page 10
Part I Introduction to Wireless Sensor Networks and Topology Control......Page 14
Introduction......Page 15
Wireless Sensor Device Architecture......Page 16
Network Architectures......Page 18
Challenges and the Need for Energy Saving Mechanisms......Page 19
Wireless Propagation Models......Page 22
The Log-Distance Path Model......Page 23
Energy Dissipation Model......Page 25
The Independent Error Model......Page 26
The Two-State Markov Error Model......Page 27
Sensing Models......Page 29
The Probabilistic Sensing Model......Page 30
The Medium Access Control Sub-layer......Page 31
Common MAC Protocols......Page 33
MAC Protocols for WSNs......Page 36
The Logical Link Control Sub-layer......Page 40
Error Control......Page 41
Performance Analysis of LLC Protocols......Page 43
Energy Analysis of LLC Protocols......Page 46
Introduction......Page 50
Topology Aware Routing Protocols......Page 51
Topology Unaware Routing Protocols......Page 53
Introduction......Page 60
Wireless Sensor Network Applications......Page 61
Single Packet-Low Reliability Applications......Page 62
Multiple Packet-Low Reliability Applications......Page 64
Multiple Packet-High Reliability Applications......Page 65
Congestion Control in Wireless Sensor Networks......Page 66
The Use of TCP and UDP in Wireless Sensor Networks......Page 67
Introduction......Page 69
Energy Conservation......Page 70
Collision Avoidance......Page 71
Increased Network Capacity......Page 72
Design Guidelines......Page 73
Definition of Topology Control......Page 74
Topology Control Taxonomy and Road Map......Page 76
Part II Topology Construction......Page 79
Centralized Topology Construction: The Critical Transmission Range (CTR) Problem......Page 80
Centralized Topology Construction: The Range Assignment (RA) Problem......Page 87
Algorithms from Computational Geometry......Page 89
Location-Based Techniques......Page 91
Direction-Based Techniques......Page 95
Neighbor-Based Techniques......Page 100
Routing-Based Techniques......Page 105
Heterogeneous Topology Construction......Page 106
Introduction......Page 112
Backbone-Based Techniques......Page 113
Growing a Tree......Page 114
Connecting Independent Sets......Page 116
Pruning-Based Techniques......Page 119
Cluster-Based Techniques......Page 120
Adaptive Techniques......Page 123
Hybrid Techniques......Page 126
Part III Topology Maintenance......Page 130
Definition of Topology Maintenance......Page 131
Scope of Topology Maintenance......Page 132
Triggering Criteria......Page 133
Design Issues......Page 134
Synchronizing Radios......Page 135
Performance Evaluation......Page 137
Introduction......Page 139
Performance Evaluation of Static Global Topology Maintenance Techniques......Page 140
Sparse Networks......Page 141
Dense Networks......Page 143
Other Static Techniques......Page 144
Introduction......Page 146
Sparse Networks......Page 147
Dense Networks......Page 148
Performance Evaluation of Dynamic Local Topology Maintenance Techniques......Page 150
Sparse Networks......Page 152
Dense Networks......Page 153
Other Dynamic Local Technique......Page 154
Performance Evaluation of a Hybrid Global Topology Maintenance Technique......Page 157
Sparse Networks......Page 158
Comparison of Topology Maintenance Techniques......Page 159
Time-Based Analysis......Page 162
Energy-Based Analysis......Page 164
Density-Based Analysis......Page 165
Introduction......Page 168
The Main Simulator Thread - The the_sim Class......Page 169
The Protocol Manager - The NodeHandler Class......Page 170
The Display Manager - The newpanel Class......Page 171
The Atarraya.element Package......Page 172
The Atarraya.event Package......Page 173
Sending Messages......Page 174
Programming a Timeout......Page 175
State Labels......Page 176
Initialization of Nodes and the Initial Events - The init_nodes and the initial_event Methods......Page 177
The HandleEvent Method......Page 178
SimpleTree: An Example of a Topology Construction Protocol......Page 184
Selection of the Protocols......Page 186
Other Protocols......Page 188
Energy and Communications Model......Page 189
Type of Experiments......Page 190
Structure of a Topology......Page 191
Structure of the Nodes......Page 192
Simulation Results......Page 195
Future of Atarraya......Page 200
References......Page 201
Index......Page 208