List of Figures |
|
xv | |
List of Tables |
|
xix | |
Preface |
|
xxi | |
Authors |
|
xxiii | |
Contributors |
|
xxv | |
Section I: Background |
|
1 | (8) |
|
|
3 | (6) |
|
1.1 Wireless Sensor Networks |
|
|
3 | (2) |
|
|
3 | (1) |
|
1.1.2 Deterministic Wireless Sensor Networks and Probabilistic Wireless Sensor Networks |
|
|
4 | (1) |
|
1.2 Topology Control in Wireless Sensor Networks |
|
|
5 | (6) |
|
|
5 | (1) |
|
1.2.2 Options for Topology Control |
|
|
5 | (2) |
|
1.2.3 Measurements of Topology Control Algorithms |
|
|
7 | (2) |
Section II: Management And Performance |
|
9 | (166) |
|
2 Greedy-based Construction of Load-balanced Virtual Backbones in Wireless Sensor Networks |
|
|
11 | (28) |
|
|
12 | (4) |
|
|
16 | (2) |
|
2.2.1 Centralized Algorithms for CDS |
|
|
16 | (1) |
|
2.2.2 Distributed Algorithms for CDS |
|
|
16 | (1) |
|
2.2.3 Other Algorithms for CDSs |
|
|
17 | (1) |
|
2.2.4 Other Load-balancing Related Work |
|
|
17 | (1) |
|
|
18 | (1) |
|
|
18 | (2) |
|
|
19 | (1) |
|
|
19 | (1) |
|
|
20 | (1) |
|
|
20 | (2) |
|
2.4.1 Algorithm Description |
|
|
20 | (1) |
|
2.4.2 Example Illustration |
|
|
21 | (1) |
|
|
22 | (1) |
|
2.5 Load-balanced Allocation of Dominatees |
|
|
22 | (9) |
|
|
22 | (3) |
|
2.5.2 Algorithm Description |
|
|
25 | (4) |
|
2.5.2.1 Centralized Algorithm |
|
|
26 | (1) |
|
2.5.2.2 Distributed Algorithm |
|
|
27 | (2) |
|
|
29 | (2) |
|
2.6 Performance Evaluation |
|
|
31 | (6) |
|
2.6.1 Scenario 1 - Data Aggregation Communication Mode |
|
|
31 | (3) |
|
2.6.1.1 Simulation Environment |
|
|
31 | (1) |
|
2.6.1.2 Simulation Results |
|
|
31 | (3) |
|
2.6.2 Scenario 2 - Data Collection Communication Mode |
|
|
34 | (9) |
|
2.6.2.1 Simulation Environment |
|
|
35 | (1) |
|
2.6.2.2 Simulation Results |
|
|
35 | (2) |
|
|
37 | (2) |
|
3 Load-balanced CDS Construction in Wireless Sensor Networks via Genetic Algorithm |
|
|
39 | (24) |
|
|
40 | (3) |
|
|
43 | (3) |
|
3.2.1 Centralized Algorithms for CDSs |
|
|
44 | (1) |
|
3.2.2 Subtraction-based Distributed Algorithms for CDSs |
|
|
44 | (1) |
|
3.2.3 Addition-based Distributed Algorithms for CDSs |
|
|
44 | (1) |
|
|
45 | (1) |
|
|
46 | (1) |
|
|
46 | (3) |
|
|
46 | (1) |
|
|
46 | (2) |
|
|
48 | (1) |
|
|
49 | (9) |
|
|
49 | (1) |
|
3.4.2 Representation of Chromosomes |
|
|
49 | (2) |
|
3.4.3 Population Initialization |
|
|
51 | (1) |
|
|
52 | (1) |
|
|
52 | (1) |
|
|
52 | (3) |
|
|
53 | (2) |
|
|
55 | (1) |
|
|
55 | (1) |
|
|
56 | (2) |
|
3.5 Performance Evaluation |
|
|
58 | (2) |
|
3.5.1 Simulation Environment |
|
|
58 | (1) |
|
3.5.2 Simulation Results and Analysis |
|
|
58 | (2) |
|
|
60 | (3) |
|
4 Approximation Algorithms for Load-balanced Virtual Backbone Construction in Wireless Sensor Networks |
|
|
63 | (28) |
|
|
64 | (3) |
|
|
67 | (2) |
|
4.2.1 Subtraction-based Algorithms for CDS-based VBs |
|
|
68 | (1) |
|
4.2.2 Addition-based Algorithms Using Single Leader for CDS-based VBs |
|
|
68 | (1) |
|
4.2.3 Addition-based Algorithms Using Multiple Leader for CDS-based VBs |
|
|
68 | (1) |
|
|
69 | (1) |
|
|
69 | (1) |
|
|
69 | (2) |
|
|
69 | (1) |
|
|
70 | (1) |
|
4.4 Load-balanced Virtual Backbone Problem |
|
|
71 | (7) |
|
4.4.1 INP Formulation of MDMIS |
|
|
72 | (1) |
|
4.4.2 Approximation Algorithm |
|
|
73 | (4) |
|
4.4.3 Connected Virtual Backbone |
|
|
77 | (1) |
|
4.5 MinMax Valid-degree Non-backbone Node Allocation |
|
|
78 | (5) |
|
4.5.1 ILP Formulation of MVBA |
|
|
80 | (1) |
|
4.5.2 Randomized Approximation Algorithm |
|
|
80 | (3) |
|
4.6 Performance Evaluation |
|
|
83 | (5) |
|
4.6.1 Simulation Environment |
|
|
84 | (1) |
|
4.6.2 Scenario 1: Change Total Number of Nodes |
|
|
84 | (2) |
|
4.6.3 Scenario 2: Change Side Length of Square Area |
|
|
86 | (2) |
|
4.6.4 Scenario 3: Change Node Transmission Range |
|
|
88 | (1) |
|
|
88 | (3) |
|
5 A Genetic Algorithm with Immigrants Schemes for Constructing a-Reliable MCDSs in Probabilistic Wireless Sensor Networks |
|
|
91 | (26) |
|
|
92 | (3) |
|
|
95 | (3) |
|
|
95 | (2) |
|
5.2.1.1 Centralized Algorithms for CDSs |
|
|
96 | (1) |
|
5.2.1.2 Subtraction-based Localized Algorithms for CDSs |
|
|
96 | (1) |
|
5.2.1.3 Distributed Algorithms for CDSs |
|
|
96 | (1) |
|
5.2.2 Related Literature about PNM Model |
|
|
97 | (1) |
|
|
97 | (1) |
|
|
98 | (3) |
|
|
98 | (1) |
|
|
98 | (2) |
|
|
100 | (1) |
|
|
100 | (1) |
|
|
101 | (11) |
|
|
101 | (2) |
|
5.4.2 Representation of Chromosomes |
|
|
103 | (1) |
|
5.4.3 Population Initialization |
|
|
103 | (3) |
|
|
106 | (1) |
|
5.4.5 Selection (Reproduction) Scheme |
|
|
107 | (2) |
|
|
109 | (4) |
|
|
109 | (2) |
|
|
111 | (1) |
|
5.4.6.3 Replacement Policy |
|
|
112 | (1) |
|
5.5 Genetic Algorithms with Immigrants Schemes |
|
|
112 | (1) |
|
5.6 Performance Evaluation |
|
|
113 | (2) |
|
5.6.1 Simulation Environment |
|
|
114 | (1) |
|
|
114 | (1) |
|
|
115 | (2) |
|
6 Constructing Load-balanced Virtual Backbones in Probabilistic Wireless Sensor Networks via Multi-Objective Genetic Algorithm |
|
|
117 | (28) |
|
|
118 | (3) |
|
|
121 | (2) |
|
6.2.1 CDS-based VBs under DNM |
|
|
121 | (1) |
|
6.2.2 Related Literature about PNM Model |
|
|
122 | (1) |
|
6.2.3 Literature Review of MOGAs |
|
|
122 | (1) |
|
|
122 | (1) |
|
6.3 Network Model and Problem Definition |
|
|
123 | (5) |
|
|
123 | (1) |
|
|
123 | (1) |
|
|
124 | (4) |
|
|
128 | (1) |
|
|
128 | (12) |
|
|
129 | (2) |
|
6.4.1.1 Multi-objective Problem (MOP) Definitions and Overview |
|
|
129 | (1) |
|
|
129 | (1) |
|
|
130 | (1) |
|
6.4.2 Design of LBVBP-MOGA |
|
|
131 | (7) |
|
6.4.2.1 Representation of Chromosomes |
|
|
131 | (1) |
|
6.4.2.2 Population Initialization |
|
|
132 | (1) |
|
|
132 | (1) |
|
6.4.2.4 Selection Scheme and Replacement Policy |
|
|
133 | (2) |
|
6.4.2.5 Genetic Operations |
|
|
135 | (3) |
|
6.4.3 Convergence Analysis |
|
|
138 | (2) |
|
6.5 Performance Evaluation |
|
|
140 | (2) |
|
6.5.1 Simulation Environment |
|
|
140 | (1) |
|
|
141 | (1) |
|
|
142 | (3) |
|
7 Constructing Load-balanced Data Aggregation Trees in Probabilistic Wireless Sensor Networks |
|
|
145 | (30) |
|
|
146 | (4) |
|
|
150 | (2) |
|
7.2.1 Energy-efficient Aggregation Scheduling |
|
|
150 | (1) |
|
7.2.2 Minimum Latency Aggregation Scheduling |
|
|
150 | (1) |
|
7.2.3 Maximum Lifetime Aggregation Scheduling |
|
|
151 | (1) |
|
|
152 | (1) |
|
7.3 Network Model and Problem Definition |
|
|
152 | (4) |
|
|
152 | (1) |
|
|
153 | (1) |
|
|
153 | (3) |
|
|
156 | (1) |
|
7.4 Connected Maximal Independent Set |
|
|
156 | (8) |
|
7.4.1 INP Formulation of LBMIS |
|
|
156 | (2) |
|
7.4.2 Approximation Algorithm |
|
|
158 | (3) |
|
|
161 | (2) |
|
7.4.4 LBPNA for Non-leaf Nodes |
|
|
163 | (1) |
|
7.5 Load-balanced Data Aggregation Tree |
|
|
164 | (5) |
|
7.5.1 ILP Formulation of LBPNA for Leaf Nodes |
|
|
164 | (1) |
|
7.5.2 Randomized Approximation Algorithm |
|
|
165 | (4) |
|
7.6 Performance Evaluation |
|
|
169 | (5) |
|
7.6.1 Simulation Environment |
|
|
169 | (1) |
|
7.6.2 Scenario 1: Change side length of square area |
|
|
169 | (4) |
|
7.6.3 Scenario 2: Change node transmission range |
|
|
173 | (1) |
|
7.6.4 Scenario 3: Change total number of nodes |
|
|
173 | (1) |
|
|
174 | (1) |
Section III: Applications |
|
175 | (146) |
|
8 Reliable and Energy Efficient Target Coverage for Wireless Sensor Networks |
|
|
177 | (18) |
|
|
178 | (1) |
|
|
179 | (2) |
|
|
180 | (1) |
|
|
180 | (1) |
|
|
181 | (1) |
|
8.3 Network Model and Related Definitions |
|
|
181 | (5) |
|
|
181 | (1) |
|
8.3.2 Related Definitions |
|
|
182 | (3) |
|
8.3.3 Problem Formulation |
|
|
185 | (1) |
|
8.4 Our Proposed Algorithm |
|
|
186 | (3) |
|
8.4.1 a-RMSC Heuristic Algorithm Overview |
|
|
187 | (1) |
|
8.4.2 Contribution Function |
|
|
187 | (2) |
|
8.4.3 Relation between MSC and a-RMSC |
|
|
189 | (1) |
|
8.5 Performance Evaluation |
|
|
189 | (4) |
|
8.5.1 Simulation 1: Control Failure Probability |
|
|
189 | (2) |
|
8.5.2 Simulation 2: Comparison between a-RMSC and MSC |
|
|
191 | (2) |
|
|
193 | (2) |
|
9 CDS-based Multi-regional Query Processing in Wireless Sensor Networks |
|
|
195 | (26) |
|
|
196 | (2) |
|
|
198 | (2) |
|
9.2.1 Periodic Query Scheduling |
|
|
198 | (1) |
|
9.2.2 Dynamic Query Scheduling |
|
|
199 | (1) |
|
|
200 | (1) |
|
|
200 | (5) |
|
|
200 | (1) |
|
9.3.2 Multi-regional Query |
|
|
201 | (1) |
|
|
202 | (3) |
|
9.4 Multi-regional Query Scheduling |
|
|
205 | (10) |
|
9.4.1 Construction of MRQF |
|
|
205 | (2) |
|
|
207 | (4) |
|
9.4.2.1 Scheduling Initialization |
|
|
207 | (1) |
|
9.4.2.2 Scheduling Algorithm |
|
|
207 | (4) |
|
9.4.3 Performance Analysis |
|
|
211 | (4) |
|
9.5 Performance Evaluation |
|
|
215 | (3) |
|
9.5.1 Simulation Environment |
|
|
215 | (1) |
|
|
215 | (3) |
|
|
218 | (3) |
|
10 CDS-based Snapshot and Continuous Data Collection in Dual-radio Multi-channel Wireless Sensor Networks |
|
|
221 | (38) |
|
|
222 | (2) |
|
|
224 | (4) |
|
10.2.1 Capacity for Single-radio Single-channel Wireless Networks |
|
|
224 | (3) |
|
10.2.2 Capacity for Multi-channel Wireless Networks |
|
|
227 | (1) |
|
|
227 | (1) |
|
10.3 Network Model and Preliminaries |
|
|
228 | (4) |
|
|
228 | (1) |
|
|
229 | (2) |
|
10.3.3 Vertex Coloring Problem |
|
|
231 | (1) |
|
|
232 | (8) |
|
10.4.1 Scheduling Algorithm for SDC |
|
|
232 | (5) |
|
|
237 | (2) |
|
|
239 | (1) |
|
|
240 | (10) |
|
10.5.1 Compressive Data Gathering (CDG) |
|
|
240 | (2) |
|
10.5.2 Pipeline Scheduling |
|
|
242 | (1) |
|
|
243 | (7) |
|
10.6 Simulations and Results Analysis |
|
|
250 | (7) |
|
10.6.1 Performance of MPS |
|
|
253 | (1) |
|
|
253 | (2) |
|
10.6.3 Impacts of N and M |
|
|
255 | (2) |
|
|
257 | (2) |
|
11 CDS-based Distributed Data Collection in Wireless Sensor Networks |
|
|
259 | (34) |
|
|
260 | (3) |
|
|
263 | (2) |
|
11.2.1 Data Collection Capacity |
|
|
263 | (1) |
|
11.2.2 Multicast Capacity |
|
|
263 | (1) |
|
11.2.3 Uni/Broadcast Capacity |
|
|
264 | (1) |
|
11.2.3.1 Uni/Broadcast Capacity for Random Wireless Networks |
|
|
264 | (1) |
|
11.2.3.2 Uni/Broadcast Capacity for Arbitrary Wireless Networks |
|
|
264 | (1) |
|
11.2.3.3 Unicast Capacity for Mobile Wireless Networks |
|
|
265 | (1) |
|
|
265 | (1) |
|
|
265 | (1) |
|
11.4 Carrier-sensing Range |
|
|
266 | (5) |
|
11.5 Distributed Data Collection and Capacity |
|
|
271 | (9) |
|
11.5.1 Distributed Data Collection |
|
|
271 | (2) |
|
|
273 | (7) |
|
11.6 14-PCR-based Distributed Data Aggregation |
|
|
280 | (3) |
|
11.7 Data Collection and Aggregation under Poisson Distribution Model |
|
|
283 | (2) |
|
|
285 | (6) |
|
11.8.1 DDC Capacity versus R0 and α |
|
|
286 | (2) |
|
11.8.2 Scalability of DDC |
|
|
288 | (1) |
|
11.8.3 Performance of DDA |
|
|
288 | (3) |
|
|
291 | (2) |
|
12 CDS-based Broadcast Scheduling in Cognitive Radio Networks |
|
|
293 | (28) |
|
|
294 | (2) |
|
|
296 | (2) |
|
12.2.1 Broadcast Scheduling in Traditional Wireless Networks |
|
|
296 | (1) |
|
12.2.2 Broadcast Scheduling in CRNs |
|
|
297 | (1) |
|
|
298 | (1) |
|
12.3 System Model and Problem Definition |
|
|
298 | (2) |
|
|
298 | (1) |
|
12.3.2 Interference Model |
|
|
299 | (1) |
|
12.3.3 Problem Definition |
|
|
300 | (1) |
|
12.4 Broadcasting Tree and Coloring |
|
|
300 | (3) |
|
12.4.1 CDS-based Broadcasting Tree |
|
|
300 | (2) |
|
12.4.2 Tessellation and Coloring |
|
|
302 | (1) |
|
12.5 Broadcast Scheduling under UDG Model |
|
|
303 | (10) |
|
12.5.1 MLBS under UDG Model |
|
|
303 | (4) |
|
12.5.2 Analysis of MBS-UDG |
|
|
307 | (6) |
|
12.5.2.1 Broadcast Latency of MBS-UDG |
|
|
307 | (6) |
|
12.5.2.2 Broadcast Redundancy of MBS-UDG |
|
|
313 | (1) |
|
12.6 Broadcast Scheduling under PrIM |
|
|
313 | (2) |
|
12.6.1 Redundancy of MBS-PrIM |
|
|
315 | (1) |
|
12.7 Simulation and Analysis |
|
|
315 | (5) |
|
12.7.1 Broadcast Latency of MBS |
|
|
316 | (2) |
|
12.7.2 Broadcast Redundancy of MBS |
|
|
318 | (2) |
|
|
320 | (1) |
References |
|
321 | (22) |
Index |
|
343 | |