Continuous Data Collection Capacity of Wireless Sensor Networks under Physical Interference Model

Data collection is a common operation of Wireless Sensor Networks (WSNs). The performance of data collection can be measured by its achievable network capacity. However, most existing works focus on the network capacity of unicast, multicast or/and broadcast, which are different communication modes from data collection, especially continuous data collection. In this paper, we study the Snapshot/Continuous Data Collection (SDC/CDC) problem under the Physical Interference Model (PhIM) for randomly deployed dense WSNs. For SDC, we propose a Cell-Based Path Scheduling (CBPS) algorithm based on network partitioning. Theoretical analysis shows that its achievable network capacity is Ω(W) (W is the data transmitting rate, i.e. bandwidth, over a channel), which is order-optimal. For CDC, we propose a novel Segment-Based Pipeline Scheduling (SBPS) algorithm that significantly speeds up the CDC process, and achieves a surprising network capacity, which is at least √(n/ log n) or n/log n times better than the current best result.

I. Introduction

Wireless Sensor Networks (WSNs) are mainly used for collecting data from the physical world. Data gathering can be categorized as data aggregation [1], which obtains aggregated values from WSNs, e.g. maximum, minimum or/and average value of all the data, and data collection [2] [17] [30], 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 [2] [4]. The problem of collecting one snapshot is called snapshot data collection (SDC). The problem of collecting multiple continuous snapshots is called continuous data collection (CDC). To evaluate the network performance, network capacity, which can reflect the achievable data transmission rate, is usually used [2]–[32]. For unicast, multicast and broadcast, we use unicast capacity, multicast capacity, and broadcast capacity to denote the network capacity, respectively. Particularly, for a data collection WSN, we use the data receiving rate at the sink, referred to as data collection capacity, to measure its achievable network capacity, i.e. data collection capacity reflects how fast data is collected by the sink¹

Without confusion, we use data collection capacity and network capacity interchangeably in the following of this paper.

[2] [4].