第 26 卷 第 10 期
Vol. 26 No. 10
控 制 与 决 策
Control and Decision
2011 年 10 月
Oct. 2011
三维传感器网络部署、覆盖和连接问题研究
文章编号: 1001-0920 (2011) 10-1447-05
钟永信, 黄建国, 韩 晶
(西北工业大学 航海学院,西安 710072)
摘 要: 针对三维传感器网络中节点最优部署问题进行研究. 通过分析常用规则多面体(如立方体和截顶八面体
等)在三维空间的填充特点, 提出了网络节点按规则多面体部署时, 单位节点最大有效体积的计算方法; 同时利用该
方法得到了网络区域保持充分覆盖且邻节点相连接时所需的最少节点数; 最后通过仿真比较了不同规则多面体的部
署性能, 进而给出了在各种 𝑟
𝑐
/𝑟
𝑠
(𝑟
𝑐
为通信范围, 𝑟
𝑠
为感测范围) 情况下的最优部署模式, 提高了网络节点的部署效
率.
关键词: 三维传感器网络;覆盖;连接;多面体;最大有效体积
中图分类号: TP393 文献标识码: A
Research on deployment, coverage and connectivity in three dimensional
sensor networks
ZHONG Yong-xin, HUANG Jian-guo, HAN Jing
(College of Marine Engineering,Northwestern Polytechnical University,Xi’an 710072,China.Correspondent:
ZHONG Yong-xin,E-mail:yongxin zhong@126.com)
Abstract: To solve the problem of optimal deployment of nodes in three dimensional sensor networks, an algorithm of
maximal efficient volume per node is presented by analyzing some popular deployment patterns of space-filling polyhedrons
such as cube and truncated octahedron. This algorithm can calculate the minimal number of sensors needed to achieve both
full coverage and connectivity of networks. Finally, the deployment performances of regular polyhedrons are compared by
some simulations. Optimal deployment patterns under the condition of different values of 𝑟
𝑐
/𝑟
𝑠
are obtained, where 𝑟
𝑐
is
communication range and 𝑟
𝑠
is sensing range, and the deployment efficiency of networks is improved.
Key words: three dimensional sensor networks;coverage;connectivity;polyhedrons;maximal efficient volume
1 引引引 言言言
部署、覆盖和连接是传感器网络研究的一项重
要课题, 对网络中的节点进行合理有效的部署可以
降低网络的成本, 提高网络的覆盖能力, 保持节点
的连通性, 增强网络的可操作性以及改善网络的性
能
[1]
. 在二维传感器网络中, 研究了规则多边形的最
优部署模式
[2-3]
, 当传感器节点通信范围 𝑟
𝑐
和感测范
围 𝑟
𝑠
的比值大于且等于
√
3 时, 部署节点在正六边形
的中心 (相当于部署节点在正三角形的顶点) 具有最
优的覆盖和连接效果, 即以最少的节点数覆盖和连接
一个平面; 而当 𝑟
𝑐
/𝑟
𝑠
<
√
3 时, 部署节点在其他一些
规则多边形 (如正方形、正三角形和菱形) 的中心可达
到最优的覆盖和连接效果.
随着传感器网络的快速发展, 二维传感器网络
在某些特定的场合不再适用, 如大气监测传感器网
络和水声传感器网络通常以三维网络为背景
[4]
. 文
献 [5] 针对随机部署的三维传感器网络, 提出了覆盖
漏洞的填补算法. [6] 致力于三维传感器网络覆盖冗
余节点的发现和减少. [7] 提出了分布式部署方法, 通
过调整节点的位置深度来减少节点的交叠区域, 从
而达到网络的最大覆盖. [8] 基于对 Reuleaux 四面体
的研究, 得到网络 𝑘- 覆盖 (𝑘 ⩾ 4) 的最小空间节点密
度并衡量网络的连接性. 而对于规则多面体的最优
部署模式, [9] 考虑了三维网络的充分覆盖和连接的
问题, 通过计算和比较常用多面体的“体积商”得知:
当 𝑟
𝑐
/𝑟
𝑠
⩾ 4/
√
5 时, 截顶八面体的覆盖效果要优于立
收稿日期: 2010-05-13;修回日期: 2010-07-01.
基金项目: 国家自然科学基金项目(60972152);中国博士后科学基金项目(20080441183).
作者简介: 钟永信(1980−), 男, 博士生, 从事水声传感器网络的研究;黄建国(1946−), 男, 教授, 博士生导师, 从事水声
通信、传感器网络等研究.