《并发数据上传的分布式优化框架.doc》由会员分享，可在线阅读，更多相关《并发数据上传的分布式优化框架.doc（20页珍藏版）》请在金锄头文库上搜索。
1、陈文渊 译一种无线传感器网络中并发数据上传的移动数据采集的分布式框架优化郭松涛，杨元元摘要在本文中，我们考虑在无线传感器网络中使用具有多个天线的移动采集器进行移动数据采集。考虑到无线链路容量和每个传感器的功率控制的弹性性质，我们首先提出具有并发数据上传功能的一个数据采集成本最小化(DaGCM)框架，它是由流守恒、能量消耗、链路容量、传感器兼容性和移动采集器在所有锚点的总逗留时间约束。其中，该框架的主要特点是，它允许从传感器到移动采集器并行上传数据，由于使用了多个天线和空分多址技术(SDMA)，从而大幅缩短数据采集延迟和显著降低能源消耗。然后，我们使用拉格朗日二元化松弛DaGCM问题，并用梯度迭
2、代算法求解。此外，我们提出了一个分布式算法，它由跨层数据控制、路由、功率控制和具有显式消息传递的兼容性决心子算法组成。我们还给出了子算法用于求出移动采集器在不同锚点的最佳停留时间。最后，我们提供的数值结果表明，在数据采集延迟和能量消耗方面，该DaGCM算法的收敛性及其优点超过了没有并发数据上传和功率控制的算法。关键词移动数据采集 凸优化 数据采集成本 分布式算法 无线传感器网络I.简介 最近的传感器技术和无线通信技术的发展使得无线传感器网络在广泛的应用中发挥着越来越重要的作用，如远程栖息地监控和战场监控。在这样的应用中，成百上千的低成本传感器通常配备能量有限的电池分散在监控区域中，而这些节点自
3、组织成一个无线网络，每个传感器节点定期报告其感知数据到汇聚节点。因此，如何以最低能耗有效地聚合分散的传感器的感知数据，是对大规模资源有限的传感器网络的应用的一个最重要的挑战，它激励我们的工作。近年来,许多研究工作一直在致力于无线传感器网络的高效数据采集和在大规模传感器网络中提出各种类型的数据采集机制。其中大部分集中在基于高效中继路由23和分层基础设施45 的静态数据采集。中继路由的核心理念是，数据包在传感器中通过单个或多个跳继电器转发到数据接收器。在分层的基础设施中，一个分层或基于集群路由的方法通常是采用被组织成簇和簇头的传感器负责转发数据到外部数据接收器。虽然这两种方法在某些应用程序中可以有
4、效的执行数据转发，但这些方法的主要缺点是，他们诱导和增加了传感器之间的能耗的不均匀性。因此，数据接收器的邻近节点会发生高度拥堵和包丢失，从而严重降低了网络性能。为了克服这两种机制的缺点，移动数据采集方案被提出在6-15。移动数据采集方法的想法是部署一种特殊类型的移动节点(通常称为移动采集器)以低成本通过短程通信网络收集来自传感器的数据。移动采集器可能是移动机器人或配备强大收发器(天线)和电池的车辆，本文称之为SenCar。这种方法的优点是，它可以减少能源消耗和交通负荷，消除靠近数据接收器的传感器节点的负担，提高网络的生命周期，采集连通网络和不连通网络的数据。这些现有的移动数据采集方案可以在无线
5、传感器网络中执行有效的数据采集，但效率不高。具体地说，一些移动数据采集方案可能导致很长的数据采集延迟，这部分是由于移动采集器一次只从一个传感器使用单个天线采集数据。实际上，一个移动采集器可以配备多个收发器或天线，使得移动收集器能够同时接收来自多个传感器的数据。显然，这可以极大地缩短数据采集时间。此外，尽管移动数据采集优化的链路容量约束被讨论在 11-15,但它被认为是一个常数。事实上, 链路容量是“有弹性的”，因为它取决于传输功率和无线信道条件，如链接收益和热噪声。因此，这些方案不适合衰落信道的无线传感器网络。此外，这些方案是通过改善数据包的路由路径或减少采集的数据量来节约能源，而不是考虑功率
6、控制。实际上，功率控制可以通过要求每个传感器给予一个恒定的信干噪比(SINR)来降低整体的传输功率。这些观察结果进一步激励我们通过考虑多个天线和集成功率控制去设计一个并发数据上传的低延迟移动数据采集方案。在本文中，为了减少和平衡传感器之间的能耗和缩短数据上传时间，我们在某些特定位置（即锚点）用两根天线部署SenCar来采集传感器的数据，在传感领域逗留的一段时间内，利用空分多址(SDMA)技术安排数据传输。通过共同使用两个天线的SenCar和SDMA技术，我们首先通过对每个传感器考虑链路容量和功率控制的弹性性质提出一个数据采集成本最小化(DaGCM)框架，这是14、15和本次工作的一个主要差异。
7、数据采集的成本(能源消耗成本)可以被视为一个传感器在锚点的逗留期间上传到移动采集器的数据量的一个函数。然后，通过引入辅助变量，我们将原来的非凸DaGCM问题转化为一个凸的问题。最后，我们将凸DaGCM问题分解为多个独立的优化子问题，提供最优算法和解决方案给数据控制、路由、功率控制和逗留时间分配子问题，这是15和本次工作的另一个主要区别。在15中，虽然使用了SDMA技术，但只给出了启发式算法和近似解，这是因为移动数据采集问题被制定成一个NP难的整数线性问题。据我们所知，我们的工作是第一个给并发数据上传的移动数据采集问题提供最优解决方案。本文的贡献和发现简要总结如下:l 我们采用两个天线的SenC
8、ar 和SDMA技术，使得来自传感器的数据能并发的上传到SenCar，从而缩短数据采集延迟和消除传感器之间能耗的不均匀性。l 我们提出一个DaGCM优化框架，它集成了流守恒、能源消耗、弹性链路容量和使用SDMA技术绑定在所有锚点的总逗留时间所要求的兼容性约束。l 我们提供数据控制的分布式跨层优化子算法、路由和对每个传感器的功率控制和通过求解非凸DaGCM问题来分配SenCar的逗留时间。l 我们的数值结果表明，相比没有并发数据上传和功率控制得算法，该DaGCM算法能收敛到最优，显著降低数据采集时间和总体能源消耗。本文的提示组织结构如下。第二部分介绍了相关工作。第三部分概述了DaGCM框架并将非
9、凸DaGCM转换成凸的。第四部分提出了分布式DaGCM算法，第五部分提供了数值结果。最后，第六部分总结本文。II.相关工作在这一部分中，我们将回顾一些最近在无线传感器网络中移动汇聚节点进行数据采集的研究。在7中，Luo和Hubaux研究应该如何调整路由以改善移动采集器的轨迹。为使移动采集器获得更加灵活的数据采集过程，Ma和Yang在8中提出了一种启发式算法，用于规划移动采集器的移动路径和在多跳网络中平衡流量负载。此外，9中将单跳数据采集问题(SHDGP) 制定为混合整数规划问题，并且为移动采集器提出了一个启发式过程规划算法。为了减少数据采集延迟，10中提出了一个基于会合点的移动数据采集机制，在
10、多跳路由路径中最小化距离，使得在给定移动采集器的旅行长度范围下做到局部数据聚合。对于节点密度更高的无线传感器网络，Sharifkhani和Beaulieu 在11中提出了一种传输调度算法来优化一个权衡传输功率和可靠性之间的度量。在12中，Sugihara和Gupta将最小化数据延迟的问题制定为位置和时间约束下的调度问题。在13和15中, M. Zhao等人提供了基于优化的数据采集分布式算法，算法的背景为移动采集器在每个锚点逗留一段时间，通过多跳通信从邻近的传感器收集数据。在14中，移动数据采集问题被制定为成本最小化问题，受到通道容量、从每个传感器收集的最低数据量和在所有锚点的总逗留时间限制。然
11、而，这项工作没有考虑从传感器利用并发数据上传到SenCar。III.系统模型和问题公式化A. 网络模型和假设考虑一个无线传感器网络由一组静态传感器（用N表示）和一组锚点（用A表示）组成。我们假设SenCar表示为s，配备两根天线，而每个传感器只有一根天线且静态分散在整个传感领域。当SenCar移动到锚点a处时，它会呆在锚点处逗留一段时间采集数据，而邻近节点则以以多跳的形式上传数据。在锚点覆盖地区的所有传感器形成了锚点的相邻集，如图1所示。有几种方法来确定SenCar访问锚点的顺序，如16中简单的沿着递增的锚点标识符的顺序或17中使移动旅程总长度最小化的顺序。我们提出的算法能够工作在任何给定的访
12、问顺序。 我们模拟SenCar位于一个锚点a(aA) 的传感器网络为一个有向图=(,)，其中=N为节点集,包括所有的传感器节点和SenCar所处的锚点a（）。代表传感器和SenCar间的定向链路集。如果，则一个定向链路(i,j)存在，其中表示节点i和节点j之间的距离，表示传感器节点的传输范围。每条链路与参数=有关, 是链路(i,j)每单位流的能耗。所有的链路都认为是对称的，即=。此外，代表了在锚点a时通过链路(i,j)的流量。当SenCar移动到锚点a时，传感器iN以的速率生成数据给SenCar。在这里，速度矢量和流矢量被认为是可以调节最小化优化目标的变量。 我们假设每个传感器i实现数据采集的
13、成本函数为，对于在数据采集的过程中从传感器i收集的总数据量，它是两次可微，递增和严格凸的（如）。成本函数可以被视为在数据采集的过程中的能量消耗或传感器i向SenCar上传数据的适宜性14。本文我们的工作旨在通过动态调整传感器i的数据率、链路(i,j)的流速和在不同锚点的逗留时间来最小化数据采集成本，它受流守恒、能源消耗、链接容量和传感器之间的兼容性约束。下面,我们将详尽说明这些约束。B. 流守恒约束转发任何传感器的数据流有两个来源：从其他传感器传入流量和传感器本身感知的数据。对于在锚点aA的每个节点i，总传出流量必须等于传感器i产生的数据流和聚合的传入流量的总和，即， iN，aA (1)流守恒
14、约束确保流出和流入的平衡。C. 能量约束为了更好地了解SDMA的好处，确保并发数据流的数量不超过天线的数量是必要的。由于SenCar配备了两根天线，最多允许两个传感器同时发送数据到SenCar。因此，如果具有相同的锚点两个传感器希望同时上传他们的数据给SenCar，他们须能够兼容并且这两个节点被称为一个兼容对，将在章节III-E中正式定义。假定传感器i的电池能源是不可再生的，为保证一个特定的网络生命周期,我们加入一个传感器i的能耗预算，即传感器在数据采集过程中所消耗的最大能源。让(i,m)表示兼容对(i,m)的时间花费率或孤立的传感器i和m上传数据到锚点a位置的SenCar的逗留时间。请注意，
15、节点i和m是靠近SenCar并能以单跳方式上传数据到SenCar的传感器，而不是锚点a位置的SenCar的邻近集的所有传感器。传感器i传输数据所消耗的能量假定为。很明显, 兼容对(i,m)在锚点a的能耗不会超过它们的能源预算，即 （2） （3）D. 链路容量约束衰落信道的容量被定义为在信道上传输的最大速率。让表示分配给链路(i,j)的传输功率, 且，和分别表示最小和最大传输功率, 为链路(i,j)的信干噪比（SINR）。为使链路(i,j)成功传输， 节点j接收到的信号必定不是由不涉及节点i和j的其他节点并发传输。为描述不干涉的条件，链路(i,j)的平均信干噪比18为 （4）其中，是链路(i,j)的热噪声功率，表示传输功率向量，为传送器i和接收器j间的链路增益，表示传输时可能会干扰链路(i,j)接收器的传感器节点的集合，是正交因子。 此外，链路(i,j)的容量能够被决定为 （5）其中，为信干噪比间隙，反映了一个特定的调制和编码方案，我们假定=1.B是
