INFOCOM2014：传感器网络中流数据的ε近似压缩算法
需积分: 10 87 浏览量
更新于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
B
C
D
(a) Only u
3
intersects polygon(1, 2).
A
B
C
D
(b) Both u
3
and l
3
intersect
polygon(1, 2).
A
B
C
D
(c) Only l
3
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 first 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
3
(3a + b = x[2] + ε) intersects
polygon(1, 2), as shown in Figure 2(a).
2) Only the line l
3
(3a + b = x[2] − ε) intersects
polygon(1, 2), as shown in Figure 2(c).
3) Both u
3
and l
3
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)
L
0
Fig. 3. v
1
, v
3
and v
4
are all the vertices of polygon(i, j), and v
3
, v
4
are two
vertices adjacent to v
1
.
as shown in Figure 2(d). When subsequent data points arrives,
we cannot find the fifth different case for band( j + 1) ∩
polygon(i, j). Therefore, there are at most four different 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 different sides on the line u
3
or
l
3
, 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 first present two special points
shown as follows.
Definition 3 (Upper Vertex). Given the boundary of
polygon(i, j), a vertex v
1
is the upper vertex(UV) of
polygon(i, j), if it satisfies that the b-coordinate of v
1
is greater
than that of any other vertex of polygon(i, j).
Definition 4 (Lower Vertex). Given the boundary of
polygon(i, j), a vertex v
2
is the lower vertex (LV) of
polygon(i, j), if it satisfies that the b-coordinate of v
2
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
v
1
and the lower vertex v
2
of polygon(i, j). Then, when ( j +
1, x[ j + 1]) arrives, for a line L
0
: b = −a( j + 1) + m (when
m = x[ j + 1] + ε, L
0
= u
j+1
; m = x[ j + 1] − ε, L
0
= l
j+1
) in
ab-coordinate system, if m increases from −∞ to +∞, then
v
1
is the f irst point that L
0
encounters in polygon(i, j), and
v
2
is the last point that L
0
encounters in polygon(i, j), and
therefore we have
L
0
∩ polygon(i, j) , Ø ⇔ L
0
∩ v
1
v
2
, Ø, (7)
where v
1
v
2
is the line segment connecting v
1
and v
2
.
Proof: It is easy to show that polygon(i, j) is a convex
polygon by mathematical induction. Then, if m increases from
剩余15页未读，继续阅读
2014-09-25 上传
180 浏览量
2010-09-12 上传
2013-02-27 上传
2013-07-18 上传
2021-02-12 上传
2021-02-22 上传
lghhit
- 粉丝: 5
- 资源: 3
我的内容管理
展开
最新资源
- IEEE 14总线系统Simulink模型开发指南与案例研究
- STLinkV2.J16.S4固件更新与应用指南
- Java并发处理的实用示例分析
- Linux下简化部署与日志查看的Shell脚本工具
- Maven增量编译技术详解及应用示例
- MyEclipse 2021.5.24a最新版本发布
- Indore探索前端代码库使用指南与开发环境搭建
- 电子技术基础数字部分PPT课件第六版康华光
- MySQL 8.0.25版本可视化安装包详细介绍
- 易语言实现主流搜索引擎快速集成
- 使用asyncio-sse包装器实现服务器事件推送简易指南
- Java高级开发工程师面试要点总结
- R语言项目ClearningData-Proj1的数据处理
- VFP成本费用计算系统源码及论文全面解析
- Qt5与C++打造书籍管理系统教程
- React 应用入门：开发、测试及生产部署教程
