ABSTRACT
CONTENTS 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 10.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
10.2.1 Capacity for Single-radio Single-channel Wireless Networks 224 10.2.2 Capacity for Multi-channel Wireless Networks . . . . . . . . . . . . . 227 10.2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
10.3 Network Model and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10.3.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10.3.2 Routing Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 10.3.3 Vertex Coloring Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
10.4 Capacity of SDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 10.4.1 Scheduling Algorithm for SDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 10.4.2 Capacity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 10.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.5 Capacity of CDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
. . . . . 10.5.2 Pipeline Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 10.5.3 Capacity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
10.6 Simulations and Results Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.6.1 Performance of MPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 10.6.2 Performance of PS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 10.6.3 Impacts of N and M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
10.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
10.1 Introduction Wireless sensor networks (WSNs) are mainly used for collecting data from the physical world. Data gathering can be categorized as data aggregation [17]-[113], which obtains aggregated values from WSNs, e.g., maximum, minimum or/and average value of all the data, and data collection [1]-[10], which gathers all the data from a network without any data aggregation. For data collection, the union of all the sensing values from all the sensors at a particular time instance is called a snapshot [171, 11, 10]. The problem of collecting all the data of one snapshot is called snapshot data collection (SDC). Similarly, the problem of collecting multiple continuous snapshots is called continuous data collection (CDC). Different from wired networks, WSNs suffer from the interference problem, which degrades the network performance. Consequently, network capacity, which can reflect the achievable data transmission rate, is usually used as an important measurement to evaluate network performance. Particularly, for a data collection WSN, we use the average data receiving rate at the sink during the data collection process, referred to as data collection capacity [171, 11, 10], to measure its achievable network capacity, i.e., data collection capacity reflects how fast data are collected to the sink. In this chapter, we study the snapshot and continuous data collection problems, as well as their achievable capacities for WSNs.
