INFOCOM2014：传感器网络中流数据的ε近似压缩算法

需积分: 10 155 浏览量更新于2024-07-25 收藏 799KB PDF 举报

本篇文章是INFOCOM2014技术报告的一部分，主要探讨了传感器网络中时间序列数据的ε-近似压缩问题。随着处理器、内存和无线通信技术的快速发展，小型、廉价的传感器节点能够进行感知、计算和无线通信，这推动了分布式传感器网络的发展。然而，由于传感器网络有限的通信带宽和资源约束，实时、高效地压缩由传感器节点生成的时间序列数据成为一项重要且实用的需求。传统上，已经有许多数据压缩算法被提出以减少数据体积，但它们通常是离线处理或者具有超线性的时间复杂度，因此不适用于实时处理传感器节点产生的大量时间序列数据。为了克服这些不足，本文作者Guohua Li、Jianzhong Li和Hong Gao来自哈尔滨工业大学计算机科学技术学院，他们提出了一个名为GDPLA（Optimal Online Algorithm for Disconnected Piecewise Linear Approximation）的优化在线算法。GDPLA旨在构造一个非连接的分段线性近似表示，以保证在有限资源下提供精确的时间序列数据压缩，并实现高效的实时处理。 GDPLA算法的核心目标是设计一种能够在有限的时间复杂度内，针对传感器节点生成的数据流进行动态调整的压缩策略。它可能包括以下几个关键步骤： 1. **实时数据收集**：传感器节点实时收集环境数据并将其发送到中央处理单元。 2. **在线分析**：GDPLA算法在接收到数据时即时处理，避免了离线算法需要预先存储所有数据的缺点。 3. **分段线性模型**：通过将连续的时间序列分割成多个可管理的部分，每个部分采用线性模型来近似，降低了复杂性。 4. **精度控制**：通过ε-近似保证，算法在保持数据精度的同时尽可能减少数据量。 5. **动态调整**：算法能够根据新数据和资源状况实时更新模型，以适应不断变化的网络环境。总结来说，这篇技术报告为解决传感器网络中时间序列数据的在线压缩问题提供了新的解决方案，这对于能源效率、延迟敏感应用和资源受限环境下的数据处理具有重要意义。通过GDPLA算法，研究者们希望能够提高传感器网络的效率，使得其在大规模实时数据处理中发挥更大的作用。

(a) Only u

intersects polygon(1, 2).

(b) Both u

and l

intersect

polygon(1, 2).

intersects polygon(1, 2). (d) polygon(1, 3) is included in

band(4).

Fig. 2. The possible relationship between band( j+ 1) and polygon(i, j) when

band( j + 1) ∩ polygon(i, j) , Ø.

When the ﬁrst data point (1, x[1]) arrives, in order to satisfy

the error-bounded requirement for (1, x[1]), we have

x[1] − ε ≤ a · 1 + b ≤ x[1] + ε, (4)

where f (t) = a · t + b is the representation function for the

current segment, and the area described by Equation (4) is

band(1), as shown in Figure 1(a). When (2, x[2]) arrives, for

guaranteeing that the vertical distance of (1, x[1]), (2, x[2]) to

the representation function f (t) = a · t + b are within ε, we

obtain

(

x[1] − ε ≤ a · 1 + b ≤ x[1] + ε,

x[2] − ε ≤ a · 2 + b ≤ x[2] + ε.

(5)

The area represented by the above two inequalities (

polygon(1, 2)) is bounded by a parallelogram (as shown in

Figure 1(b)), and the equations of four edges on the parallel-

ogram are as follows.











a + b = x[1] − ε,

a + b = x[1] + ε,

2a + b = x[2] − ε,

2a + b = x[2] + ε,

(6)

When (3, x[3]) arrives, we check whether band(3) intersects

polygon(1, 2). If so, it means that the three data points

(i, x[i]), 1 ≤ i ≤ 3 can be approximated by a representation

function. If not, it means that the three data points (i, x[i]), 1 ≤

i ≤ 3 cannot be approximated by a representation function. For

the former, there are three cases shown as follows.

1) Only the line u

(3a + b = x[2] + ε) intersects

polygon(1, 2), as shown in Figure 2(a).

2) Only the line l

(3a + b = x[2] − ε) intersects

polygon(1, 2), as shown in Figure 2(c).

3) Both u

and l

intersect polygon(1, 2), as shown in

Figure 2(b).

When ((4, x[4])) arrives, there exists the fourth case except

the above three similar cases, that is, polygon(1, 3) ⊂ band(4)

Fig. 3. v

, v

and v

are all the vertices of polygon(i, j), and v

, v

are two

vertices adjacent to v

as shown in Figure 2(d). When subsequent data points arrives,

we cannot find the ﬁfth diﬀerent case for band( j + 1) ∩

polygon(i, j). Therefore, there are at most four diﬀerent cases

when band( j + 1) ∩ polygon(i, j) , Ø. For the previous three

cases, as shown in Figures 2(a), 2(b) and 2(c), we observe

that when checking whether the FSS for (3, x[3]) intersects

polygon(1, 2), we only decide whether the points A and D (as

shown in Figure 2(a)) are on diﬀerent sides on the line u

, where the point A and D are both vertices of polygon(1, 2),

and A is the vertex with the maximum b-coordinates of the

vertices of the parallelogram ABCD, while D is the vertex with

the minimum b-coordinates of the vertices of the parallelogram

ABCD. Based on the above observation, we have a guess that

we only need to check two points A and D to decide whether

the newly arrived data point can be compressed together with

the data points seen so far but not compressed, where A is

the vertex with the maximum b-coordinates of the vertices of

the polygon R (the boundary of the FSS for the data points

seen so far but not compressed), and D is the vertex with

the minimum b-coordinates of the vertices of the polygon R.

Before validating our guess, we ﬁrst present two special points

shown as follows.

Deﬁnition 3 (Upper Vertex). Given the boundary of

polygon(i, j), a vertex v

is the upper vertex(UV) of

polygon(i, j), if it satisﬁes that the b-coordinate of v

is greater

than that of any other vertex of polygon(i, j).

Deﬁnition 4 (Lower Vertex). Given the boundary of

polygon(i, j), a vertex v

is the lower vertex (LV) of

polygon(i, j), if it satisﬁes that the b-coordinate of v

is less

than that of any other vertex of polygon(i, j).

For the upper vertex and the lower vertex with respect to

polygon(i, j), we have the following lemma.

Lemma 2. Given the polygon(i, j) (i < j), the upper vertex

and the lower vertex v

of polygon(i, j). Then, when ( j +

1, x[ j + 1]) arrives, for a line L

: b = −a( j + 1) + m (when

m = x[ j + 1] + ε, L

= u

j+1

; m = x[ j + 1] − ε, L

= l

j+1

) in

ab-coordinate system, if m increases from −∞ to +∞, then

is the f irst point that L

encounters in polygon(i, j), and

is the last point that L

encounters in polygon(i, j), and

therefore we have

∩ polygon(i, j) , Ø ⇔ L

∩ v

, Ø, (7)

where v

is the line segment connecting v

and v

Proof: It is easy to show that polygon(i, j) is a convex

polygon by mathematical induction. Then, if m increases from

剩余15页未读，继续阅读

lghhit

粉丝: 5
资源: 3

INFOCOM2014：传感器网络中流数据的ε近似压缩算法

DCRNN在INFOCOM会议的研究文章压缩包

InfoCom CEMS食堂消费管理系统配置指南

Infocom Z-Engine Java 解释器开源项目分析

INFOCOM2014包

INFOCOM 2010

infocom2013 paper

INFOCOM 2012 content

infocom-sources：Infocom驱动器中的原始源文件

infocom论文模板 latex

INFOCOM 2010 (3)

最新资源