《无线传感器网络移动数据收集》阐述了无线传感器网络移动数据收集的基础理论、关键技术和*新研究成果，详细介绍了将多用户多输入多输出 (multiple-input multiple-output, MIMO)技术、空分多路复用（space division multiple access, SDMA）技术、并发数据上传技术等现代通信技术应用到无线传感器网络的移动数据收集，深入讨论了在网络连通或不连通、低传输延迟、收集代价*小、有界中继跳数等情况下的无线传感器网络移动数据收集。

目录
第1章绪论1
1.1无线传感器概述1
1.1.1无线传感器网络体系的结构1
1.1.2无线传感器网络的特点2
1.1.3无线传感器网络的研究热点3
1.2无线传感器网络的数据收集4
1.2.1数据收集模式及收集方法分类4
1.2.2数据收集中存在的问题与挑战5
1.3移动数据收集6
1.3.1移动数据收集的背景6
1.3.2移动汇聚型无线传感器网络7
1.4本书的架构10
参考文献12
第2章连通及不连通WSN的移动数据收集机制15
2.1引言15
2.2相关工作17
2.3连通WSN的移动数据收集18
2.3.1负载平衡19
2.3.2运动路径：确定拐点21
2.3.3沿着运动路径的分段进行分簇23
2.3.4寻找移动路径：分而治之24
2.3.5Sencar移动环的确定26
2.3.6感知现场的障碍避免26
2.4不连通WSN的移动数据收集27
2.4.1不连通网络的分簇27
2.4.2簇间的运动路径规划28
2.5性能评价30
2.5.1在一个有障碍的区域内寻找移动路径31
2.5.2网络寿命32
2.5.3与TSP解的比较33
2.5.4不连通网络移动环的确定34
2.6本章小结35
参考文献35
第3章WSN中移动数据收集的路径规划37
3.1引言37
3.2预备知识40
3.3单跳数据收集42
3.4单跳数据收集问题的启发式算法44
3.5带多个移动收集器的数据收集46
3.6性能评价49
3.6.1单个数据收集器的路径长度49
3.6.2网络寿命52
3.6.3多个移动收集器的数据收集53
3.7本章小结55
参考文献55
第4章基于有界中继跳数的移动数据收集58
4.1引言58
4.2基于有界中继跳数的移动数据收集问题62
4.2.1问题概述62
4.2.2问题刻画63
4.3BRH-MDG问题的集中式算法66
4.4BRH-MDG问题的分布式算法70
4.5性能评估73
4.5.1与*优解的比较73
4.5.2SPT-DGA和PB-PSA的性能比较75
4.6本章小结80
参考文献80
第5章基于多用户MIMO技术的移动数据收集83
5.1引言83
5.2基于多用户MIMO技术的无线传感器网络84
5.3基于MIMO技术的移动数据采集86
5.3.1原理及架构概述87
5.3.2传感器层：负载均衡分簇89
5.3.3簇头层：簇头组之间的连通性95
5.3.4Sencar层：移动路径规划98
5.4性能评价101
5.4.1传感器节点数变化对网络性能的影响102
5.4.2传感器节点距离变化对性能的影响103
5.5本章小结105
参考文献105
第6章基于空分多路复用的有效移动数据收集107
6.1引言107
6.2SDMA：线性去相关器策略111
6.3带单一Sencar与SDMA技术的移动数据收集113
6.3.1MDG-SDMA问题描述113
6.3.2MDG-SDMA问题的公式化116
6.4MDG-SDMA问题的启发式算法118
6.4.1*大匹配对算法118
6.4.2*小覆盖生成树算法121
6.5带多个Sencar和SDMA技术的数据收集126
6.5.1MDG-MS问题描述127
6.5.2区域划分和路径规划算法128
6.6性能评价132
6.6.1MDG-SDMA的算法评价132
6.6.2MDG-MS算法的评价137
6.7本章小结139
参考文献139
第7章基于优化的分布式移动数据收集算法143
7.1引言143
7.2系统模型和问题形式化146
7.2.1系统模型146
7.2.2NUM-FT问题公式化148
7.2.3NUM-VT问题公式化149
7.3NUM-FT问题的分布式算法150
7.3.1Lagrange函数及其对偶问题150
7.3.2速率控制子问题151
7.3.3路由子问题155
7.3.4Lagrange乘子更新156
7.3.5原问题的解156
7.4NUM-VT问题的分布式算法157
7.4.1NUM-VT问题的分解157
7.4.2低层*优化158
7.4.3高层*优化160
7.5性能评价162
7.5.1网络配置及参数设置162
7.5.2收敛性163
7.5.3NUM-FT和NUM-VT的性能比较167
7.5.4与其他策略的性能比较168
7.6本章小结170
参考文献170
第8章基于代价*小化的移动数据收集算法173
8.1引言173
8.2系统模型和问题公式化175
8.3问题分解和基于代价的算法178
8.4Sensor处的局部代价*小化184
8.5性能评价187
8.5.1收敛性187
8.5.2网络代价190
8.6本章小结192
参考文献192
第9章基于并发数据上传的移动数据收集架构195
9.1引言195
9.2系统模型和问题公式化197
9.2.1网络模型和假设197
9.2.2数据流量守恒约束199
9.2.3能量约束200
9.2.4链路容量约束200
9.2.5兼容性约束201
9.2.6跨层*优化模型202
9.3DaGCM问题的*优化算法204
9.3.1拉格朗日对偶分解204
9.3.2数据控制子算法206
9.3.3路由子算法207
9.3.4功率控制和兼容性子算法208
9.3.5逗留时间分配子算法210
9.3.6数据分割子算法210
9.4性能评估213
9.4.1收敛性和性能分析213
9.4.2性能比较217
9.4.3在NS-2中的仿真结果219
9.5本章小结221
参考文献221
第10章基于SINR的低延迟数据收集算法225
10.1引言225
10.2系统模型和问题刻画228
10.2.1网络模型与定义228
10.2.2数据收集与链路调度约束229
10.2.3SINR约束230
10.2.4问题刻画231
10.2.5NP难问题233
10.3启发式算法233
10.3.1基于功率的增强干扰图234
10.3.2数据收集树的构造234
10.3.3链路调度与功率分配236
10.4性能评价240
10.5本章小结243
参考文献243

第1章　绪论
　　1.1　无线传感器概述
　　无线传感器网络(wireless sensor network，WSN)通常由数百或数千个传感器节点通过无线连接来执行感知、数据传送任务。随着嵌入式技术的蓬勃发展，各种功能的传感器模块被置入单个节点上，并通过无线通信技术连接，形成了*初的无线传感器网络[1]。21世纪初，无线传感器网络曾经被《美国周刊》评为*有发展前景的十大新兴技术之一。
　　1.1.1　无线传感器网络体系的结构
　　在无线传感器网络中，传感器通常随机分布在没有配置基础设施的空间中，每个传感器都具备监测环境、收集数据及将数据路由传输到数据接收器的能力。典型的无线传感器网络体系架构如图1.1所示。无线传感器网络通常由大量的传感器节点、固定或移动的汇聚(sink)节点、外部网络(互联网或蜂窝网络)和客户端组成。无线传感器节点主要负责从检测环境中感知数据，并将感知到的数据以单跳或多跳的方式进行传输；汇聚节点是连接外部网络和无线传感器网络的网关，具有较多的能量和较大的内存空间；外部网络借助互联网或蜂窝网络来实现长距离的数据传输和通信；客户端则借助外部网络通过电脑或智能手机向传感器网络发送控制命令和接收来自传感器网络的数据。
　　图1.1　无线传感器网络体系架构
　　无线传感器节点具有体积小、智能化、易于扩展、成本低廉、安装部署方便的特性，这使其组成的无线传感器网络具有较好的经济性能并得到了广泛应用。但是，无线传感器节点在能量供应、计算、存储和通信方面的能力十分有限，这也给无线传感器网络的研究带来了巨大挑战。和其他类型的网络相比，无线传感器网络的瓶颈主要是资源有限，特别是能耗方面，所以在设计硬件和路由协议时需要*先考虑。因此，考虑到无线传感器节点在硬件资源上的限制，要求应用到无线传感器网络的算法和路由协议必须是特定的、轻量级的，所以不宜直接移植其他类型网络已有的算法和协议。
　　1.1.2　无线传感器网络的特点
　　无线传感器网络在当前社会中有着极为广泛的应用[2]，如环境监测、智能家居等。作为一个面向应用的网络，其主要任务就是通过收集相应的数据来检测网络部署区域内事件发生的状况。相比传统的无线局域网络，无线传感器网络表现出很多自身固有的特性，主要体现在以下几个方面[3]。
　　(1)以数据为中心且数据冗余度高：传统的无线局域网络以地址为中心，网络中的每个节点在进行数据传输时以目的地址为根据，而无线传感器网络却不同，它以数据为中心，终端用户只对传感器节点所感知的数据感兴趣，而对感知数据的某个传感器节点并不关心。例如，用户在查询某个区域的事件时，返回给用户的结果是事件本身，而不是监测到该事件的某个传感器节点的编号。另外，由于无线传感器网络的节点数量较多，因此在一定区域范围内的节点所监测到的数据通常具有较高的冗余度。
　　(2)网络规模庞大且传感器节点分布随机：通常情况下，无线传感器网络中的节点数目庞大，在不同的应用场景下，数目由几百到几千个，甚至几万个，并且这些节点多数情况下是随机部署的。
　　(3)节点的资源及能力受限：一般情况下，传感器节点的资源是受限的，节点由自身携带的微型电池供电，如果电池的电量耗尽，那么该节点便成为死亡节点。一旦有节点死亡，便很有可能出现“能量空洞”现象[4]。另外，受到资源及制造工艺的限制，无线传感器节点通常只具备有限的计算能力、存储能力和通信能力。所以，一般不会将很复杂的计算任务交给传感器节点执行，而是将其交给汇聚节点。
　　(4)节点具备自组织能力且网络拓扑结构易变：传感器节点具备自组织能力，能够自动进行组织和管理，构成一个分布式多跳任务型网络。由于在很多应用场景下，传感器节点被部署于自然气候条件非常恶劣的地域中，因此传感器节点很容易发生故障或损坏，节点的可靠性较差。当节点发生故障时，会导致网络的拓扑结构发生变化，因此无线传感器网络的拓扑结构是易变的。
　　(5)无线传感器网络具备很强的应用相关性：无线传感器网络是面向任务的自组织分布式网络，因此它是应用相关的。针对不同的应用场景或需求，整个网络在硬件层面和软件层面的设计上也有不同的要求和偏重。例如，在对海洋温度勘测的应用中，需要周期性地将数据返回给终端用户，而在火灾监测的应用场景下，应用对实时性的要求较高，需要及时将事件信息发送给终端用户。
　　1.1.3　无线传感器网络的研究热点
　　虽然无线传感器网络在众多领域的广泛应用给生产及生活带来了极大的便利，但是传感器节点的能量受限问题却给无线传感器网络的发展带来了一定程度的制约。因此，不同于传统无线局域网络，无线传感器网络的研究一般都围绕能耗这个主题，以下列举了该领域内的一些研究热点。
　　1. 数据收集
　　数据收集是无线传感器网络的基础问题，也是热点问题。监测区域内的传感器节点感知外部环境并依照设定的数据收集方式将产生的感知数据传输到基站。当前学术界提出了大量旨在节省传感器节点能量、延长网络寿命的数据收集方法。总体上，传统的方法可分为四大类：原始数据收集、基于数据融合的数据收集、基于时空相关性的数据收集和基于数据压缩的数据收集。
　　2. 数据传输与路由协议
　　数据传输同样是无线传感器网络的基础研究问题。传感器节点收集数据后，通过单跳或多跳的方式，将数据传输到汇聚节点。因为传感器网络中大多节点的冗余度较高，因此在满足覆盖率和连通度的前提下，剔除不必要的无线连接，构建一个精简的传输路径，是数据传输的主要研究内容。数据传输所涉及的研究内容非常广泛：网络拓扑控制、路由协议设计、媒体访问控制(media access control，MAC)层协议设计等。其中以节能为目的的路由协议、MAC层协议一直是学术界研究的热点[4]。常见的路由协议可分为传感器信息协商协议(sensor protocol for information via negotiation，SPIN[5])、定向扩散(directed diffusion，DD[6])路由协议和低能耗自适应聚类层次(low energy adaptive clustering hierarchy，LEACH[7])协议、阈值敏感节能传感器网络(threshold sensitive energy efficient sensor network protocol，TEEN[8])协议、基于链状结构的传感器信息系统能量高效聚集(power-efficient gathering in sensor information systems，PEGASIS[9])路由协议。
　　3. 拓扑管理
　　对自组织的无线传感器网络而言，网络拓扑控制对网络性能的影响很大。其拓扑结构受很多因素(如节点的传输能量、天线角度、信号干扰等)的影响，动态性很强。拓扑结构是设计链路层和网络层协议的基础，是网络性能的重要保障。研究表明，良好的拓扑管理可以提高路由和链路层协议的效率及网络吞吐量，同时减少网络干扰，节约节点资源，从而达到延长网络生命周期的目的。
　　还有一些关键技术，如数据融合[2]、时钟同步[3]、节点定位[4]、数据管理[10]、网络安全[11]等也是无线传感器网络的研究热点。鉴于篇幅，在此不进行逐一讨论。
　　1.2　无线传感器网络的数据收集
　　数据收集是获取物理世界状态的重要方式，也是实现各种复杂无线传感器网络应用的基础。高效的数据收集对于无线传感器网络具有重大意义。*先，数据收集是实现无线传感器网络功能的关键。只有高效可靠地获取物理世界感知的信息，我们才能够准确地了解当前物理世界的状态，为后期的数据分析、知识挖掘和决策反馈提供真实可靠的依据。其次，作为无线传感器网络的基本功能，高效的数据收集方法是延长网络寿命的重要途径。高效的数据收集方法可以根据实际的应用需求挖掘全网内部的数据特点，合理调度数据采集并准确恢复全网感知数据，在减少节点能量消耗的同时满足实际应用的数据质量需求。
　　1.2.1　数据收集模式及收集方法分类
　　无线传感器网络中的数据收集模式可以分为：①持续的数据收集，网络中每个传感器节点周期性地产生感知数据并传输到基站；②基于查询的数据收集，网络中拥有符合用户查询所需求数据的传感器节点时，才会被触发并传输感知数据到基站；③基于事件驱动的数据收集，只有在网络中检测到用户感兴趣的特定事件的传感器节点才会将其感知的数据回传到基站。
　　如前所述，总体上，数据收集的方法可分为四大类：原始数据收集、基于数据融合的数据收集、基于时空相关性的数据收集和基于数据压缩的数据收集。
　　(1)原始数据收集的方法是传感器节点不对其采集的数据进行处理，直接传输原始数据。这种方法经常因传感器节点的密集部署而使网络内部的数据流量大且分布不均匀，基站附近传感器节点的能量消耗过快，从而引发“热点问题”，进而影响网络效率。
　　(2)基于数据融合的数据收集方法能够获得监测区域内高度概括的感知状况(如整个监测区域感知数据的*大值和*小值)，但这并不能满足大部分实际应用中对细粒度感知的需求。
　　(3)基于时空相关性的数据收集。传感器节点的感知数据存在较为明显的时空相关性，借助数据的时空相关性，数据收集方法可在数据精度和能量节省之间保持平衡。在减少实际应用需求的基础上牺牲一定的数据精度，同时可实现传感器节点大量节能的目的。
　　(4)基于数据压缩的数据收集方法是利用传感器节点感知数据的相关性对数据进行编码以消除信息冗余，从而减少数据传输量。该类方法依据网内数据编码方式又可分为基于传统压缩编码的数据收集方法、基于分布式信源编码(distributed source coding，DSC)[12]的数据收集方法和基于压缩感知(compressive sensing，CS)[13]的数据收集方法。
　　1.2.2　数据收集中存在的问题与挑战
　　数据收集的目标在于结合实际应用需求和无线传感器网络本身的特点来设计高效的数据收集方法，以保证所收集数据的能量有效性、可扩展性及动态适应性等。虽然无线传感器网络中有关数据收集的研究已经持续了很多年并取得了大量的研究成果，但是随着无线传感器网络应用的多样化发展，新的应用特点和需求不断被提出，已有的数据收集方法也需进一步改善。
　　1. 能量有效性
　　无线传感器网络软件及硬件设计的一个核心原则即能量有效性，这是出于传感器节点的资源限制和无线传感器网络长期运行的需求。从数据收集的角度出发，提高能量有效性的方法主要包括以下两方面。一方面需要尽可能地减少传感器节点的能量消耗。研究表明，在传感器节点的各项活动中，通信是传感器节点能量消耗*多的环节。因此，在数据收集过程中有效降低数据通信量是节省传感器节点能量的重要途径，而如何利用网络中感知数据的时空相关性来抑制冗余数据传输是关键。另一方面需要保证网络能量消耗均衡，这样可使得所有传感器节点的能量消耗同步，避免因局部能耗热点造成网络空洞而缩短网络的有效工作寿命。虽然，当前已有的数据收集方法提出了不同的措施来提高传感器节点的能量有效性或平衡全网节点能耗，但是综合考虑传感器节点层面和网络层面中能量有效性的数据收集方法仍有待研究。
　　2. 可扩展性
　　数据收集方法需要具有较好的可扩展性以满足不同应用场景下不同规模的无线传感器网络对数据收集的需要。无线传感器网络可能包含成百上千个传感器节点，所以有效容纳如此多的节点来完成大范围的数据收集就需要设计扩展性强的数据收集方法，保证数据收集过程中的计算操作或信息交换在节点本地或局部小范围内进行，避免泛洪(flooding)等不必要的涉及全网节点参与的操作。传统的数据收集方法因数据量过大等而具有较差的可扩展性，故只适合小规模的无线传感器网络。集中式的数据收集方法在大规模网络中的可扩展性较差，因此需要设计一套分布式的数据收集相关机制与方法来有效