第1章 绪论 1
1.1传感器网络 1
1.2传感器网络的计算几何方法 2
1.2.1边界识别 4
1.2.2骨架提取 5
1.2.3网络分解 7
1.3传感器网络计算几何方法的应用 9
1.3.1网络定位 9
1.3.2网络路由 11
1.3.3网络导航 13
1.3.4信息存储与检索 14
参考文献 16
第一篇 二维传感器网络的骨架提取 27
第2章 基于完全边界信息的骨架提取 27
2.1骨架与角点 28
2.1.1骨架 28
2.1.2角点 28
2.2基于边界划分的骨架提取算法 30
2.2.1角点识别与边界划分 31
2.2.2骨架节点识别 33
2.2.3骨架弦与粗糙骨架 34
2.2.4优化骨架 35
2.3算法分析 36
2.3.1算法复杂度 36
2.3.2多尺度骨架 37
2.3.3无角点的骨架提取 37
2.3.4基于骨架的网络分割 38
2.3.5基于骨架的路由协议 38
2.4仿真实验 41
参考文献 45
第3章 基于距离变换的骨架提取 52
3.1距离变换 54
3.2基于距离变换的骨架定义 55
3.3 DIST算法 56
3.3.1距离变换的建立 56
3.3.2关键骨架节点识别 57
3.3.3粗糙骨架 59
3.3.4优化骨架 62
3.4骨架在边界识别和网络分解中的应用 62
3.4.1基于骨架的边界识别 62
3.4.2基于骨架的网络分解 64
3.5算法评价 66
3.5.1实验配置 66
3.5.2基于骨架的路由协议性能评价 67
3.5.3仿真实验结果 68
3.6算法分析与讨论 74
3.6.1复杂度分析 74
3.6.2边界不完全程度对DIST算法的影响及参数选择 74
3.6.3算法正确性的有关证明 75
参考文献 76
第4章 无边界信息的骨架提取 78
4.1基于中心度的骨架识别 78
4.1.1连续情形下的骨架性质 79
4.1.2传感器网络的骨架节点识别 81
4.1.3算法实现 83
4.1.4仿真实验 87
4.1.5讨论 90
4.2基于网络Reeb图的骨架提取 91
4.2.1连续域中的骨架性质 91
4.2.2无线传感器网络的骨架识别 92
4.2.3算法实现 93
4.2.4仿真实验 95
参考文献 96
第二篇 三维传感器网络的线骨架与面骨架 101
第5章 三维传感器网络的线骨架提取 101
5.1理论基础 102
5.1.1二维/三维物体的线骨架性质 103
5.1.2二维/三维物体线骨架识别 105
5.1.3线骨架点的重要度 106
5.2传感器网络的线骨架提取通用算法 108
5.2.1骨架点识别 109
5.2.2重要度计算与骨架树构建 110
5.2.3骨架优化 111
5.2.4复杂网络的骨架提取 113
5.2.5复杂度分析 113
5.3三维传感器网络中基于线骨架的路由协议 114
5.4仿真实验 115
5.4.1实验配置 116
5.4.2实验结果分析 116
参考文献 121
第6章 三维传感器网络的面骨架提取及其在数据存储中的应用 126
6.1分布式存储算法 126
6.2面骨架 129
6.2.1连续域中的面骨架 129
6.2.2传感器网络的面骨架 130
6.3算法描述 132
6.3.1面骨架节点识别 133
6.3.2面骨架的建立 134
6.3.3复杂度分析 135
6.3.4网络动态对算法的影响 135
6.4面骨架的应用 137
6.4.1基于面骨架的数据存储与检索协议 137
6.4.2基于面骨架的线骨架提取 138
6.5仿真实验 139
6.5.1对网络形状的鲁棒性 140
6.5.2对网络密度的稳健性 140
6.5.3算法在非均匀分布网络中的性能 140
6.5.4算法在QUDG模型下的性能 141
6.5.5算法在动态网络中的性能 142
6.5.6面骨架在数据存储中的应用 142
参考文献 144
第三篇 二维传感器网络的凸分解 151
第7章 基于凸分解的定位算法 151
7.1网络近似凸分解与定位 152
7.1.1近似凸分解 152
7.1.2网络凹度与定位的关系 154
7.1.3传感器网络的凹度 155
7.2 ACDL：基于网络近似凸分解的定位算法 156
7.2.1凹/凸点识别与边界划分 156
7.2.2网络近似凸分解 159
7.2.3局部坐标图 161
7.2.4全局坐标图 164
7.3实验分析 165
7.3.1不同网络场景下的算法性能 166
7.3.2通信模型对ACDL算法的影响 170
7.3.3网络节点分布对ACDL算法的影响 170
7.3.4 ACDL算法对参数的敏感性分析 171
7.3.5 ACDL算法对网络密度的敏感性分析 172
7.3.6低密度网络下的算法性能比较 172
参考文献 174