计算机网络论文无线传感器网络数据收集问题

　　摘要：数据收集问题研究外界用户如何通过无线传感器网络从监控区域收集感知数据。传感器节点通过自组织方式构成网络，数据收集问题就是寻找高效可靠的方式将感知数据通过多跳的方式传输给用户进行分析和处理。近几年对数据收集问题的研究非常广泛，主要包含减少数据收集过程中的数据传输量、数据收集协议和大规模网络数据收集调度等问题。从以上几方面对数据收集问题进行综述。

　　关键词：无线传感器网络,数据收集,路由协议,调度

　　0引言

　　无线传感器网络，通常包括传感器，汇聚节点和基站。传感器节点数据经过多个节点后最终到达Sink节点，其后再通过Internet网络或卫星网络传输给用户。用户处理数据后，通过sink节点向网络发送控制命令以及调度命令。传感器节点由电池供电，其节点能量有限[4]。无线传感器网络具有动态性强、监测数据量大、但其通信能力、供电能力和计算能力均属有限等特点。现实中的无线传感器网络主要应用在工业控制[5]、智能家居[6]、医疗护理[7]、农业和环境监测[8]以及目标跟踪[9]和物流管理[10]等方面。

　　在传感器网络的很多应用中，数据收集需要传输大量的感知数据。大量感知数据在网络中传输，会产生大量通信开销。通信开销是传感器网络最重要的能量消耗方式。据统计，数据传输消耗的能量占整个传感器网络能量消耗的80%。减少数据传输量，即能够降低能量开销，从而延长网络生命周期。数据收集算法中，有多种方法可以减少数据传输量。例如，基于采样的数据收集方法，基于数据压缩的数据收集方法以及基于数据共享的数据收集方法。

　　传感器网络数据收集问题的覆盖范围非常广泛，从数据收集协议、到多信道调度，从静态网络、到可移动网络数据收集等，都存在着大量的研究问题。本文将从如何减少数据收集过程中的数据传输量、数据收集协议和大规模网络数据收集调度等几方面对数据收集问题进行系统分析和专题介绍。

　　1基于采样的数据收集方法

　　文献[11]提出一种大规模传感器网络中近似K-中位数计算方法。K-中位数是指，给定一个集合S，在集合S中找出第K小的值，n为S集合的大小。文献[12]提出基于采样的（ε，δ）-近似聚集算法。通过采样，可使得到的结果误差在ε界限内的概率不大于δ。文献[13]则在对一小部分传感器节点数据采样至融合中心后，再估计感知环境，并指导网络资源分配。具体地讲，融合中心根据估计的感知环境情况，有选择地激活某些节点，从而满足一定的误差界限。这种动态采样方法可以有效节省能量开销。文献[14]提出一种在线算法，在给定能量开销上界的情况下最小化近似比误差。该种算法是基于区域采样，将网络划分为多个不重叠的区域，并通过计算近似聚集结果来满足事先设定的能量预算。文献[15]采用基于卡尔曼滤波的估计方法来自动动态地调整采样速率，从而降低传输量，提高估计精度。文献[16]提出一种近似随机的采样方法。这种方法只采样与网络规模成比例的部分节点，由此而达到接近随机采样方法的效果及精度。

　　2基于数据聚集的数据收集方法

　　文献[17]研究了数据聚集操作对于网络性能的影响。文献[18]总结了数据压缩的几种方式。其中，最为常见的是通过聚集的方式尽量更少地传输数据。聚集操作只是在根据特定查询的应用中较为有效，在一般的数据收集方法中却并不适用。文献[19]研究了传感器网络数据空间相关性对数据压缩的影响。文献[20]又提出一种分布式的基于数据空间相关性的数据压缩方法。文献[21]则研究了无结构的数据聚集方法。通常，数据聚集方法都基于树状或其它固定结构，该文提出了两种无结构的数据聚集方法。此外，文献[22]研究稀疏网络中的数据聚集方法，而文献[23]研究了传感器网络数据聚集方法中的安全问题。

　　无线传感器网络中，有关数据聚集操作已经产生了许多的研究成果[24-29]。聚集操作一般包括求最大值、最小值、和、均值、中值以及计数等。计数操作的方法包括基于采样的方法[30-31]、基于压缩感知的方法[32]、基于蒙特卡罗的方法[33]以及基于统计分析的方法[34-35]等。而根据不同的应用场景，对象检测技术也将有所不同。聚集算法则可分为集中式算法和分布式算法。集中式算法多是需要得到全网的信息，其通信开销量一般并不适于传感器网络应用中。人们更大程度上用的是分布式聚集算法。分布式聚集算法包括基于分簇的算法、基于多路径的算法以及基于聚集树的算法[36]。第1期方效林，等：无线传感器网络数据收集问题综述智能计算机与应用第4卷

　　3基于多任务数据共享的数据收集方法

　　多应用共享传感器网络可以提高网络的利用率[37-40]。但是多任务共享一个传感器网络却会增加网络的计算和通信开销，从而降低网络的生命周期。传输尽量最少的数据满足多应用的查询要求是一种降低通信开销的有效方法。文献[41]研究多任务数据共享问题。但在其所研究的问题中，每个任务只是需要在各自的周期内采集一个数据。

　　无线传感器网络中数据共享问题的研究目标是在多任务共享的传感器网络中，采集最少的数据，从而满足所有任务的需求。传感器网络中查询优化问题也需要收集尽量最少的数据满足各个查询的要求[42-43]。但其中需要解决的问题通常是如何在网内进行分布式调度，再通过数据聚集来减少数据量。

　　数据库系统中涉及到的多查询优化问题也有需要减少数据量的情况[44-45]。但是这类问题更多的是强调如何最大化公共表达式，再通过限制查询量来减少数据量。多查询优化问题可通过寻找SQL公共表达式减少不必要的重复子查询。Krishnamurthy等人研究数据流系统中聚集查询的数据共享问题[46]。研究者们主要解决处理诸如min、max、sum以及count等聚集查询。在其所研究的问题中，数据流至少需要被扫描一次，并分成多个碎片。只有被多个查询重叠覆盖的碎片才可以得到共享。

　　4数据收集过程中路由协议问题的研究

　　无线传感器网络（WirelessSensorNetworks）通过大量部署在监测区域内的传感器节点采集网络覆盖区域内感知对象的信息，并通过多跳的无线通信方式将收集处理后的信息提供给终端用户。路由算法是数据收集的基本问题，所有数据都需要通过路由方法发送至基站进行相关处理。传感器网络中具有多种路由协议，包括Gossiping协议[47]、SPIN协议[48]、DirectedDiusion协议[49]、Rumor协议[50]、LEACH协议[51]等等。在数据收集过程中，使用较多的路由协议作为树状路由和地理路由等。而在无线传感器网络中，地理路由协议则使得数据包可以通过多跳无线传输到达指定地理位置附近的节点，因而具备了广泛的应用前景。目前，已经实现了很多关于地理路由算法的研究工作，其基本过程大体一致，都是在贪心模式失败时转入周边模式。

　　5数据收集过程中调度问题的研究

　　在传感器网络的众多应用中，数据收集需要传输大量的感知数据。大量感知数据通过路由方法转发给sink节点，必然引起数据冲突。数据冲突不但会导致重传，从而降低吞吐量，而且还会导致数据丢失。TDMA方法是一种能够在高负载网络中避免冲突，提高吞吐量的有效方法[52-54]。现今已经涌现了许多关于TDMA的工作，这些工作的目的都在于如何减少TDMA时间槽数或者设计分布式TDMA算法[55-57]。但是这些研究工作却都是针对一般数据通信而设计的TDMA算法。文献[58]研究基于TDMA的数据收集问题。给定一棵路由树及其对应的干扰图，每个节点都要向基站发送数据，目标是找到最小的时间槽数，使得所有节点数据都能发送到基站。文献[58]证明了这个问题的复杂性，并给出两个算法。一个是基于节点的调度算法，另一个是基于分层的调度算法。该文献还对提出的算法进行了分析，但并未给出近似比。此外，减少数据冲突，提高网络吞吐量的另一个有效方法则是采用多信道技术。多信道通信中，不同的信道将互不干扰。通过多信道机制，尽可能地使得多个链路在同一时间进行通信，从而提高网络的吞吐量。现在已经获得了大量多信道调度问题的研究工作成果。文献[59-61]研究聚集操作的多信道调度问题。文献[62-64]探讨了多信道MAC协议。文献[65]实现了在网络中建立多棵树，每棵树使用不同的信道，以此来提高网络的吞吐量。文献[66]则研究了多信道快速数据收集过程的吞吐量与延时的权衡问题。

　　已有的多信道研究中都选择信道间频距足够大的信道，以保证信道间正交无干扰。但是这种选择却会导致可利用的信道数减少。有研究表明，适当减小频距，增加可用的信道数，能够提高网络的吞吐量。在数据收集过程中，一般均以树状路由进行数据传输。研究中需要考虑如何进行TDMA以及多信道调度，使得网络中所有节点的数据能够以最短的时间到达树根的问题。同时，还需考虑信道间发生干扰时，如何使得因信道间干扰而造成的数据丢失最少的问题。

　　已有大量的工作表明多信道复用可以极大提高网络的吞吐量[67-69]。近年来已开发了很多的多信道传输协议，例如MCMAC[70]，TMMAC[71]，MMSN[63]等。然而，这些工作使得为网络中每一条链路分配时间槽，实现彼此之间互不干扰成为可能。其实针对数据聚集网络中的多信道调度问题，只需要对所构建路由树上的链路，而不是网内所有链路进行时间槽分配即可实现与完成。

　　全网数据收集与数据聚集问题表现了一定的相关性[72]，但是并不完全相同。全网数据收集算法的目标是收集网内所有节点的原始数据，而数据聚集算法却是收集聚集结果。最小化延时是数据收集问题的一个研究内容[102-103]。Gandham等人提出一调度算法[73]，算法实现需要3N个时间槽。其中，N为节点个数。Yu等人提出另一调度算法[74]，实现需要24D+6Δ+16个时间槽。其中，D是网络的直径，Δ是最大节点度数。这些工作的目标都是减少延时，使得数据最早发送到基站。Wu等人又提出一多信道数据收集协议TMCP（Tree-basedMulti-ChannelProtocol）[65]。该协议将网络划分成多个子树，树间使用不同的信道，而树内使用相同的信道。其目标是减少树内的干扰。

　　文献[60]中，算法首先建立一棵路由树；其次为每个节点分配信道，使其下的所有孩子节点都以这个信道发送数据；为树内链路分配时间槽，使得彼此之间互不干扰。在分配信道过程中，算法优先分配信道给那些干扰最严重的节点，这一分配方式是集中式的，并不适合在传感器网络中应用。文献[60]中，算法的上界为maxΔ2+1，其中Δ2是网络形成的图中2跳内邻居节点的个数。令Δ（G）为图的度，则文献[60]中的算法上界为O（Δ（G）2）。

　　文献[66，71]针对UDG网络和非UDG网络提出两种调度算法。算法中，针对UDG网络所提出的算法上界为8μαΔ（T）。其中，μα是与方格大小有关的函数，Δ（T）是所构建路由树的度。针对非UDG网络所提出的算法上界为O（Δ（T）logn）。其中，（T）是所构建路由树的度，n是网络中的节点个数。这两种算法都是集中式的。

　　多信道调度的研究工作还包括多电台多信道调度的研究[75-77]。多电台多信道网络中每个节点包含多个收发装置，每个收发装置可以独立地进行数据收发工作，如此即可进一步提高数据传输能力。

　　6结束语

　　用户进行区域监测、事件发现、事件挖掘以及事件预测等操作，都需要将网络中的传感器数据收集到基站进行处理，因此数据收集问题成为传感器网络中的焦点研究内容之一。本文从如何减少数据收集过程的数据量、如何减少数据聚集过程的数据量以及数据收集过程中的路由协议和调度问题几方面对数据收集问题进行了阐述，介绍了当前数据收集问题的研究工作，并针对相关研究工作分别进行了分析和介绍。参考文献：

　　[1]李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展[J].软件学报，2003，14（10）：1717–1727.

　　[2]孙利民，李建中，陈渝.无线传感器网络[M].北京：清华大学出版社，2005.