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, . 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]