Internet DRAFT - draft-wang-roll-adaptive-data-aggregation

draft-wang-roll-adaptive-data-aggregation







ROLL WG                                                          C. Wang
Internet-Draft                                         Tongji University
Intended status: Informational                          October 18, 2015
Expires: April 20, 2016


              Design of Adaptive Data Aggregation Schemes
            draft-wang-roll-adaptive-data-aggregation-00.txt

Abstract

   Data aggregation is a key energy saving functionality in wireless
   sensor networks (WSNs) for both data gathering applications and
   event-based applications, since the communication cost is often the
   higher order of the computation cost.  Through data aggregation, we
   can reduce the scale of data while maintaining the correctness of
   data for a set of symmetric functions called divisible perfectly
   compressible (DPC) functions.  Also the achievable minimum data rate
   among all sensor nodes is limited for random WSNs if we insist data
   from ALL sensors should be collected.  Hence we use gathering
   efficiency to indicate the number of nodes whose data are gathered.
   It is intuitive that there exists a tradeoff between the aggregation
   throughput and gathering efficiency.  This document introduces
   adaptive data aggregation schemes for WSN to consider the tradeoffs
   between the aggregation throughput and gathering efficiency.
   Specifically, the adaptive data aggregation schemes includes two
   protocols, Single-Hop-Length (SHL) Scheme and Multiple-Hop-Length
   (MHL) Scheme, for different gathering efficiency requirements.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on April 20, 2016.






Wang                     Expires April 20, 2016                 [Page 1]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


Copyright Notice

   Copyright (c) 2015 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Requirements Language . . . . . . . . . . . . . . . . . . . .   3
   3.  Terminology and Notation  . . . . . . . . . . . . . . . . . .   4
   4.  System Model  . . . . . . . . . . . . . . . . . . . . . . . .   4
     4.1.  Network Model . . . . . . . . . . . . . . . . . . . . . .   4
     4.2.  Scheme Lattice  . . . . . . . . . . . . . . . . . . . . .   4
   5.  Single Hop Length (SHL) Scheme  . . . . . . . . . . . . . . .   4
     5.1.  Local Aggregation . . . . . . . . . . . . . . . . . . . .   5
     5.2.  Horizontal Backbone Aggregation . . . . . . . . . . . . .   5
     5.3.  Vertical Backbone Aggregation . . . . . . . . . . . . . .   5
   6.  Multiple Hop Length (MHL) Scheme  . . . . . . . . . . . . . .   6
     6.1.  Selection . . . . . . . . . . . . . . . . . . . . . . . .   6
     6.2.  Local Aggregation . . . . . . . . . . . . . . . . . . . .   7
     6.3.  Draining Aggregation  . . . . . . . . . . . . . . . . . .   7
     6.4.  Horizontal Backbone Aggregation . . . . . . . . . . . . .   7
     6.5.  Vertical Backbone Aggregation . . . . . . . . . . . . . .   7
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .   7
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   7
   9.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .   7
   10. Normative References  . . . . . . . . . . . . . . . . . . . .   7
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Introduction

   Data aggregation is an effective technique for conversing
   communication energy in low-power and lossy wireless sensor network.
   In wireless sensor networks, the communication cost is often several
   orders of magnitude larger than the computation cost.  Because of the
   redundancy in raw data collected from sensors, data aggregation can
   often reduce the communication cost by removing the redundancy and
   the left information would be compressed compared with the raw data.



Wang                     Expires April 20, 2016                 [Page 2]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


   Various data aggregation schemes have been proposed, e.g., cluster-
   based structures and tree-based structures.  In data gathering
   applications, such as environment and habitat monitoring, sensors
   periodically send the sensed data to the sink.  When the traffic
   pattern and network topology are assumed to be invariable, the
   structure-based methods need low-maintenance overhead and are thus
   applicable for such application scenarios.

   It's obvious that the number of sensor nodes whose data are collected
   makes difference to the performance of aggregation throughput.  The
   achievable minimum data rate among all sensor nodes is severely
   limited for random WSNs if we insist data from ALL sensors should be
   collected.  Here, we denote the gathering efficiency to the ratio of
   the number of the sensor nodes whose data are gathered successfully
   to the total number of sensor nodes in the network.  A high gathering
   efficiency means most of sensor nodes' data are collected.
   Collecting data from a subset of sensor nodes is reasonable because
   of the potential spatial correlations among sensed environment.
   There is a tradeoff between aggregation throughput and gathering
   efficiency.

   In this document, we design adaptive structure-based aggregation
   schemes for WSNs to achieve the optimal tradeoffs between the
   aggregation throughput and gathering efficiency.  In our protocol,
   for the neighborhood of every node, we will approximately select a
   portion of nodes and aggregate their data to the sink.  Such a
   sampling scheme will achieve high aggregation throughput while
   maintaining the spatial coverage by the sampled sensors.
   Specifically, we design two schemes, Single-Hop-Length (SHL) Scheme
   and Multiple-Hop-Length (MHL) Scheme, to improve the tradeoffs
   between throughput and gathering efficiency.  Both propsed
   aggregation schemes are based on lattices.Section 4 will give the
   details of scheme lattice.  And the details of two schemes will be
   coverd in Section 5 and Section 6, respectively.

   This document is organized as follows: Section 3 defines the
   Terminalogy and Notation in this document.  Section 4 will give the
   network model used in this document and the concept of lattice in two
   schemes.  Section 5 and Section 6 give the details of two schemes.

2.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].






Wang                     Expires April 20, 2016                 [Page 3]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


3.  Terminology and Notation

   This document uses the following additional terms: DPC, SHL, MHL.

   o  DPC functions

      For data gathering, we focus on an important set of symmetric
      functions called divisible perfectly compressible (DPC) functions,
      such as the mean, max, and kinds of indicator functions that will
      be used to compute the data aggregation.

   o  SHL

      Single-Hop-Length Scheme, in which the routing is nonhierarchical
      and consists of the links with similar lengths.  Selected sensors
      are at most one hop away from the adjacent nodes.  The details
      will be covered in Section 5.

   o  MHL

      Multiple-Hop-Length Scheme, in which the routing is hierarchical
      and consists of the links with various lengths.  Backbone stations
      are at most one hop away from the adjacent nodes, however other
      sensors with a long link to the backbone station should be
      removed.  The details will be covered in Section 6.

4.  System Model

4.1.  Network Model

   We consider a random WSN, where sensors are deployed on the
   2-dimension plane according to a Poisson point process of density r
   with r belongs [1, n] where n is the number of randomly placed
   sensors.

4.2.  Scheme Lattice

   Both proposed aggregation schemes are based on lattices.  Definition
   of Scheme Lattice: Partition a square region A = [0, a] * [0, a] into
   a lattice consisting of square cells of side length L, we call the
   produced lattice scheme lattice.

5.  Single Hop Length (SHL) Scheme

   We design the scheme Single-Hop-Length Aggregation Scheme based on
   scheme lattice where a = sqrt(n/r).  In SHL scheme, The routing is
   nonhierarchical and consists of the links with similar lengths.  By
   selecting a certain number of sensors in local regions depending on



Wang                     Expires April 20, 2016                 [Page 4]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


   the given lower bound on gathering efficiency, we can improve the
   aggregation throughput by deliberating the bottleneck produced by the
   second limitations, i.e., dense components.  Specifically, there are
   three steps in SHL scheme, local aggregation, horizontal backbone
   aggregation, and vertical backbone aggregation.  Bellow illustrates
   the SHL scheme:



     +---------+---------+---------+
     | o   o   |  o  o   |  o      |
     |   x -------> x -----> X  o  |
     |  o   o  | o     o |   ^ o   |
     +---------+---------+---|-----+
     |  o   o  |   o     |   |  o  |
     |   x -------> x -----> x     |
     |  o  o   |   o  o  |   ^ o   |
     +---------+---------+---|-----+
     |   o o   |  o    o |   | o   |
     |   x -------> x -----> x     |
     | o o     |   o  o  | o   o   |
     +---------+---------+---------+




5.1.  Local Aggregation

   In each cell, log2(n) sensors are selected, if applicable.  Suppose
   that each sensor has an associated block of L readins.  Then L rounds
   of measurements from those sensors are aggregated to the aggregation
   stations by a single hop; all transmissions are scheduled by a 4-TDMA
   scheme.

5.2.  Horizontal Backbone Aggregation

   L rounds of data held by each aggregation station are aggregated to
   the adjacent aggregation stations in the order from left to right in
   a pipelined fashion; all transmissions are scheduled by a 9-TDMA
   scheme.

5.3.  Vertical Backbone Aggregation

   L rounds of data held by each aggregation station are aggregated to
   the adjacent aggregation stations in the order from bottom to top in
   a similar pipelined fashion; all transmissions are sheduled by a
   3-TDMA scheme.




Wang                     Expires April 20, 2016                 [Page 5]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


6.  Multiple Hop Length (MHL) Scheme

   We design another aggregation scheme MHL scheme based on the scheme
   lattice where a=sqrt(n/r) and there exists a minimum angle that
   equals to pi/4 between the boundaries of A and the sides of cells.
   Choose randomly a sensor from each nonempty cell, called aggregation
   station, then, we can build the aggregation backbones based on the
   gathering efficiency required to get the optimal aggregation
   throughput.  The backbone stations, i.e., the stations on the
   aggregation backbones, are connected by only short links, whereas
   every peripheral station, i.e., the stations other than backbone
   stations, can access a specific backbone station node in one-hop
   transmission.  However, the distance between peripheral stations and
   backbone stations should not exceed a constraint computed to get a
   high aggregation throughput.  Specifically, there are five steps,
   i.e., Selection, Local Aggregation, Draining Aggregation, Horizontal
   Backbone Aggregation, and Vertical Backbone Aggregation, to implement
   MHL scheme.  Bellow illustrates MHL scheme:



     +---------+---------+---------+
     | o   o   |  o  o   |  o      |
     |   x     |    x    |      o  |
     |  o \    | o     o |     o   |
     +---- \ --+---------+---------+
     |  o   \  |   o     |      o  |
     |       ------ x ------ x     |
     |  o  o   |    | o  |   | o   |
     +---------+----|----+---|-----+
     |   o     |  o |  o |   | o   |
     |         |    x        x     |
     | o       |   o  o  | o   o   |
     +---------+---------+---------+




6.1.  Selection

   Choose a subset of cells that contain aggregation stations, denoted
   by C, in which the aggregation stations are at a certain distance to
   the corresponding aggregation backbones.  The distance is computed
   based on the gathering efficiency and to get the optimal aggregation
   throughput






Wang                     Expires April 20, 2016                 [Page 6]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


6.2.  Local Aggregation

   In each cell in C, choose randomly a number of sensors; L rounds of
   measurements from those chosen sensors are aggregated to the
   aggregation station by a single hop; all transmissions are scheduled
   by a 4-TDMA scheme.

6.3.  Draining Aggregation

   All peripheral stations in C drain the L rounds of data into the
   corresponding backbone stations by a single hop of a certain
   distance.

6.4.  Horizontal Backbone Aggregation

   L rounds of data held by each backbone station are horizontally
   aggregated to the adjacent backbone stations in the order from left
   to right in pipelined fashion, until the data are aggregated into the
   backbone stations on the backbones passed through by the sink node;
   all transmissions are scheduled by a 9-TDMA scheme.

6.5.  Vertical Backbone Aggregation

   L rounds of data held by each backbone station in the backbone are
   aggregated to the adjacent aggregation stations in the order from
   bottom to top in a similar pipelined fashion; all transmissions are
   scheduled by a 3-TDMA scheme.

7.  Security Considerations

   This document has not conducted its security analysis.

8.  IANA Considerations

   This document does not specified its IANA considerations, yet.

9.  Acknowledgments

10.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/
              RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.







Wang                     Expires April 20, 2016                 [Page 7]

Internet-Draft      Adaptive Data Aggregation Schemes       October 2015


Author's Address

   Cheng Wang
   Tongji University
   4800 Cao'an Road, Jiading District
   Shanghai
   China

   Email: cwang@tongji.edu.cn










































Wang                     Expires April 20, 2016                 [Page 8]